[운영체제] Process Synchronization(1)

critical section 문제의 프로그램적 해결법

충족조건

1. Mutual Exclusion 상호 배제
   한 프로세스가 critical section에 있으면 다른 프로세스는 들어갈 수 없게 해야 함
2. Progress
   아무도 critical section에 있지 않은 상태에서 들어가고자 하는 프로세스가 있다면 넣어줘야 함
3. Bounded Waiting
   한 프로세스가 critical section에 들어가려고 요청하고, starvation이 일어나지 않도록 해야 함

Algorithm 1

• turn이 0이 아닌 동안 while문을 돌면서 자기 차례를 기다림
• progress 조건을 만족하지 못함
• 반드시 한번 씩 교대로 들어가야하는데, 서로 들어가야 하는 횟수가 다른 경우 progress 조건 만족 못함

Algorithm 2

• 둘 다 2행까지 수행 후 끊임없이 양보하는 상황 발생 가능
• progress 조건 만족 못함

Algorithm3 (Peterson's Algorithm)

• 충족조건 모두 만족
• Busy Waiting(= spin lock) 문제 : 비효율
• 내가 CPU를 잡고 있는 상황에서 의미 없이 while문을 돌며 CPU할당 시간을 낭비

---

Synchronization Hardware

소프트웨어적으로 복잡하게 할 수 밖에 없는 것을 하드웨어의 인스트럭션으로 간단히 해결할 수 있다.
데이터를 읽는 것과 쓰는 것을 하나의 인스트럭션으로 처리할 수 없었기 때문

Test & Set

데이터 a의 현재값을 읽고, 값을 1로 바꾸는 것을 하나의 인스트럭션으로 처리하는 것
a의 값이 0이었으면 0을 읽고 값을 1로 바꿈
1이었으면 1을 읽고 값을 1로 다시 세팅

lock을 읽고 난 뒤 1로 바꿔준다.
만약 처음에 lock의 값이 0이었다면, while문을 탈출하고 lock 값이 1이 된다.
반대로 lock의 값이 1이면 while문에서 갇히고 lock 값은 그대로 1이 된다.

---

Semaphores

• 위의 방식들을 추상화시킴
• Semaphore변수는 P, V 연산으로만 접근 가능
• 공유자원을 획득하고 반납하는 것을 처리
  

• 이 방법을 쓰더라도 누군가 cs에 들어가 있다면 busy wait을 하게 됨
• block&wake up 혹은 sleep lock으로 구현

Block & Wakeup

P(S): 자원을 획득하는 과정. 자원의 여분이 있다면 바로 획득, 없다면 blocked
V(S): 자원을 다 쓰고 나서 반납. 혹시 자원을 기다리고 있는 프로세스가 있다면 그 프로세스를 깨워줌

s.value는 자원의 개수가 아님. 음수 = 누군가 기다리고 있다 / 양수 = 자원의 여분이 있다 = 기다리지 않고 쓰고있는 상황이다

자원의 이용율이 더 좋다
block & wakeup 도 오버헤드 발생할 수 있음

세마포의 종류

Counting semaphore

• 자원의 개수가 여러개인 경우

Binary semaphore

• 0, 1 값만 가질 수 있음
• 자원의 개수가 하나인 경우
• mutual

Deadlock and Starvation

Deadlock

• 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상
  
• 자원 획득 순서를 똑같이 맞춰주면 해결 됨

Starvation

• Infinite blocking
• 프로세스가 suspend된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상
• 특정 프로세스들만 자원을 공유하면서, 다른 프로세스는 영원히 자원을 공유받을 수 없음