오퍼레이팅시스템 10주차/ 12.Mutual Exclusion and Synchronization

Terminologies

 

동기화

프로세스 또는 스레드가 동시에 실행될 때, 이들의 실행순서를 제어하여(접근순서나 타이밍에 따라 달라지는 것을 방지하고) 일관성있는 결과를 얻도록 하는 것

 

Process/Thread Synchronization

같은 근본적인 문제를 다룸. -> 차이점은 공유자원의 범위와 특성에 있다.

동기화의 목적 : 공유자원에 접근시의 정확성 보장. 동시실행단위들 간의 실행 순서 보장

 

Thread Synchronization

같은 프로세스 내에서 자원을 공유하므로 프로세스보다 더 자주 공유자원에 접근하게 된다.

만약 쓰레드들이 동시에 공유 자원에 접근하면? 잘못된 결과가 발생할 수 도 있고 이를 경쟁 조건(race condition)이라고 한다. 

 

Mutual Exclusion

프로세스/쓰레드가 동시에 공유 자원에 접근하지 못하도록 막는 기법이다. 뮤텍스 , 세마포어

 

Condition Varialbe

특정조건이 충족 될 때 까지 프로세스/쓰레드를 기다리게 하거나 다시 실행시키는데 사용된다. wait/signal

Race Condition

다수의 프로세스나 쓰레드가 동시에 공유자원에 접근하고 결과가 실행순서에 따라 달라지는 상황

경쟁조건이 존재하는 경우 결과의 특징:

실행결과가 매번 달라짐, 같은 입력으로 실행해도 항상 같은 결과가 나오지 않음.

실행타이밍에 따라 결과가 달라짐 >> 예측 불가능한 요소 :

단일프로세서 : 비동기인터럽트로 인해 실행순서가 섞일 수 있음.

다중프로세서 : 각 CPU의 실행 타이밍이 달라질 수 있음.

Critical Section

한 번에 최대 한 프로세스만 사용해야하는 자원 / 임계자원 : counter

임계자원에 접근하는 코드를 임계영역이라고 한다. / counter++

 

문제 해결 조건

1) Mutual Exclusion 상호배제 : 프로세스 A가 임계영역을 실행 중이라면, 다른 프로세스는 임계영역에 실행할 수 없다.

2) Progress 진행 : 임계영역을 실행 중인 프로세스가 없고 임계영역에 들어가기를 기다리는 프로세스가 있다면 대기하지 말고 실행하게 한다.

3) Bounded Waiting 한정 대기 : 프로세스가 임계영역을 실행하기 위해 대기하면서 다른 프로세스가 임계영역을 실행하는 횟수에 제한이 있다. (영원히 대기 X, limit이 존재한다)

Mutual Exclusion (상호배제)

한 프로세스가 임계 구역에 있는 동안, 다른 프로세스는 해당 임계구역에 진입하지 못하고 대기함.

entercritical로 자원 잠금 → exitcritical로 해제 / 이렇게 함으로써 동시성 문제, 경합조건 방지

 

"프로세스/스레드 동기화는 경합 조건(race condition)을 피하거나 올바른 실행을 보장하기 위해, 임계 구역 내에서 상호 배제를 제공하는 메커니즘이다."

SW approach - Peterson

-1)naive approach(단순한 접근법)

1. P0에서 if (flag == 0) 조건을 만족하고 flag = 1을 실행하기 바로 직전에 문맥 전환 (context switch) 발생

 

2. P1도 똑같이 flag == 0이라고 보고 flag = 1 실행

 

3. 결과적으로 P0와 P1 모두 임계 구역에 동시에 들어감

 

➡️ Mutual exclusion이 깨짐

 

 

 

 

 

-2) SW approach (1) - 상호배제 만족, Progress 만족 못함.

 

•  
• P0 → flag[0] = TRUE;
• P1 → flag[1] = TRUE;
• P0 → while(flag[1]); → TRUE → 대기 상태
• P1 → while(flag[0]); → TRUE → 대기 상태

→ 서로가 서로를 기다리며 무한 루프에 빠짐
→ 이 상태는 Deadlock(교착 상태) 또는 Livelock이라고도 불립니다

 

 

 

 

 

-3) SW approach(2) - Peterson

 

 

• 둘 다 들어가려 할 때:
  • 두 flag 모두 TRUE
  • turn 값이 상대방을 가리키면 스스로 양보하고 기다림
  • 결국 한 쪽만 임계 구역에 들어감 → Mutual Exclusion 보장
• 공정성 (Progress Condition):
  • 기다리던 프로세스는 상대가 나가고 나면 즉시 진입 가능
    → 무한 대기 없음 (Bounded Waiting 보장)

두 flag가 동시에 TRUE일 수 있지만, turn이 결정권을 가짐

 

한계점 : 그래서 flag[0] = true보다 turn = 1이 먼저 실행될 수도 있음
→ 다른 프로세스(P1)가 이를 보고 "P0가 양보했구나"라고 잘못 판단하고 동시에 진입

HW approach

 

-1) Disabling Interrupt

인터럽트를 끄면 프로세스가 임계 구역에서 방해받지 않고 끝낼 수 있다.

장점 : 단일 CPU환경에서 다른 프로세스로의 전환을 방지할 수 있음

단점 : 멀티프로세서에 부족함 긴 임계구역이 있을 경우 중요한 인터럽트를 너무 오래 지연시킴.

-2) Special Machinde Instruction (CAS)

현재 쓰레드에 저장된 값과 메인 메모리에 저장된 값을 비교하고 일치하는 경우에만 새로운 값으로 수정

 

• 메모리 주소의 값을 읽어서 oldval로 저장
• 그 값이 기대값(testval)과 같으면 → newval로 바꿈
• 같지 않으면 아무 것도 하지 않음
• 항상 기존 값을 리턴

 

Spin Lock

상호배제 만족 : 한번에 한 쓰레드만 임계영역에 들어가게 한다. Lock을 획득할 때까지 루프를 돌며 계속 시도

1. compare_and_swap(bolt, 0, 1) 시도

 

• bolt == 0이면 1로 바꾸고 임계 구역 진입 성공
• bolt == 1이면 다른 프로세스가 이미 사용 중 → 계속 spin-wait

2. 임계 구역 실행 후 bolt = 0으로 락 해제

 >> 구현이 매우 간단하지만, CPU 사용량이 높고 그냥 기다리기만 함(busy waiting)

 

[ fairness (공정성) ]

- 스핀락은 공정성을 보장하지 않아 starvation 발생할 수도 있다.

 

속성	세마포어	스핀락
Resource 관리	여러 개 자원을 동시에 관리 가능 + 상호 배제	한 개 자원만 관리 (상호 배제만 가능)
동작 방식	Block-Awake 방식 (잠들고 깨움)	Busy Waiting 방식 (계속 루프 돌며 기다림)
적합 상황	긴 시간 동안 lock이 유지될 때 (ex: 고부하 상황)	짧은 시간 동안 lock이 필요한 경우에 적합

 

Counting Semaphore

semaphore

운영체제에서 사용하는 일반화된 동기화수단

상호배제 가능, 복수자원 동시관리 가능, 동기화문제 해결 , busy waiting 없음

세마포어는 기다리는 프로세스를 큐(queue)에 넣고 block 상태로 전환시켜 CPU 낭비를 방지함

P(s) = semWait(s) : 자원요청, 세마포어 값 감소

V(s) = semSignal(s) : 자원반납, 세마포어 값 증가

 

-1) Binary Semaphore

0,1 만 가능 , 상호배제

 

-2) Counting Semaphore

0이상의 정수, 여러개의 자원 동시관리

 

 

• 멀티코어 시스템에서는 (a) CAS 방식이 더 안전하고 확장 가능
• 단순한 시스템이나 단일 CPU 환경에서는 (b) 인터럽트 방식이 더 간단하고 실용적

Deadlock 데드락 (교착상태)

두개 이상의 프로세스가 서로 상대방의 자원을 기다리며 영원히 대기 상태에 빠지는 것