[운영체제] KOCW 5.3 - Ch6: Process Synchronization

The Critical-Section Problem

Initial Attempts to Solve Problem

▷ lock/unlock

lock/unlock

• critical section 수행중일 때: lock --> 다른 code는 동일한 공유데이터에 접근하는 critical-section을 수행할 수 없다.
• critical section 수행이 끝났을 때: unlock --> exit section

 

프로그램적 해결법의 충족 조건

• Mutual Exclusion(상호배제): 프로세스 P가 critical section 부분을 수행중이면, 다른 모든 프로세스들은 그 critical section에 들어갈 수 없다.
• Progress(진행): 아무도 critical section에 있지 않은 상태에서, critical section에 들어가고자 하는 프로세스가 있다면 critical section에 들어가게 해주어야 한다.
• Bounded Waiting(유한 대기): 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다. (starvation X)

1) Algorithm 1: turn

Algorithm 1: turn

• Mutual exclusion(상호배제) -- O
• Progress(진행) -- X 

• Problem: 과잉보호 -- 반드시 한 번씩 교대로 들어가야 한다. 그가 turn을 내 차례로 내어주어야만 내가 들어갈 수 있다. --> 만약 특정 프로세스가 더 빈번히 critical section에 들어가야 한다면?

 

2) Algorithm 2: flag

Algorithm 2: flag

• Mutual exclusion(상호배제) -- O
• Progress(진행) -- X 

• Problem: 둘 다 2행까지 수행 후 끊임없이 양보하는 상황 발생 가능(깃발만 계속 드는 상황)

** 깃발을 드는 것(just 의사표현) =/= 수행

▷ i: 깃발을 든다 --> 빼앗긴다 --> j: 깃발을 든다, 상대방의 깃발을 확인 --> j: wait

 

3) Algorithm 3 (Peterson's Algorithm)

Algorithm 3 (Peterson's Algorithm)

▷ Algorithm 2의 깃발만 계속 드는 문제 해결

: turn을 상대방으로 바꾸고, 이때 상대방의 flag도 들려있을 경우에만 wait한다.

• Problem: Busy waiting(계속 CPU와 memory를 쓰면서 wait) --> 비효율적

 

Synchronization Hardware

▷ 하드웨어적으로 해결하면, 알고리즘이 필요하지 않게 된다.

▷ 하드웨어적으로 automic하게(중간에 CPU를 빼앗기거나 쪼개지지 않고, 데이터를 바꾸어 저장하는 것을 한 번에 실행) 수행할 수 있도록 한다.

• Test_and_set (a): Read + TRUE

Test_and_set (a): Read + TRUE

▷ 값을 읽고(Read), 그 값에 상관없이 TRUE로 세팅한다.

 

---

Synchronization 문제 해결 <-- by. 추상적 도구

1. Semaphone
2. Monitor

Semaphore

▶ P(S): 자원 획득

• S < 0: 자원의 여분이 없다 --> wait
• S > 0: 지원의 여분이 있다 -->  S--, enter(자원을 쓴다)

▶ V(S): 자원 반납

• S++

Semaphore 연산

 

1) busy-wait

1) Busy-wait

▷ mutex = 0이면, while문을 계속 돌면서 P를 빠져나가지 못한다.

• Problem: busy-wait는 효율적이지 않다.
• Solution: Block & Wakeup

▶ busy-wait: mutex = 0이면, while문을 계속 돌면서 P를 빠져나가지 못한다.

▶ Block & Wakeup: mutex = 0이면, Blocked 상태에 들어가면서 CPU를 반납한다.

 

2) Block & Wakeup

Semaphore: value, L

Semaphore 연산

▶ P(S): 공유데이터 획득

1. S.value --;
2. if S.value < 0 --> block(S.L: Semaphore list에 넣는다.)

▶ V(S): 공유데이터 반납

1. S.value ++;
2. if S.value <= 0 --> wakeup(S.L: Semaphore list에서 wakeup할 process 찾는다.)

 

Busy-wait vs. Block & Wakeup -- Which is Better?

• Busy-wait: 효율적이지 않다.
• Block & Wakeup: 일반적으로 더 효율적이다.

▶ But... critical section의 경쟁이 치열하지 않은 경우, Block & Wait 오버헤드가 busy-wait 오버헤드보다 커질 수 있다.

 

Two Types of Semaphores

▶ Counting semaphore

• 도메인이 0 이상인 임의의 정수값
• resource counting

▶ Binary semaphore (= mutex)

• 0, 1값만 가질 수 있는 semaphore
• mutual exclusion(상호배제): lock/unlock