Process Synchronization 2: Semaphores, Spin Lock, Mutex

Semaphore

• 추상화된 자료형으로서 앞서 배운 동기화 방법을 추상화시켰다고 보면 된다.
  • 추상화된 자료형이란 object, opretaion으로 이루어진 논리적 정의로서 예를 들어 integer와 같이 정수와 사칙연산으로 이루어진 것을 말한다.
• 정수형 변수 S와 P(), V() 연산으로 이루어진 자료형이 Semaphore다.
• P와 V연산은 atomic하며, 이 연산을 통해서만 Semaphore에 접근 가능하다.
• P연산은 자원을 획득, V연산은 자원을 반납하는 것을 정의
• P 연산은 사용 가능한 자원이 있는지 체크하고, 있으면 while문을 빠져나와 진입
• 변수 S는 자원의 개수를 의미
• 왜 사용하는가?
  • 자원을 획득하고 반납하는 것을 처리해줌: S변수를 + OR - 처리
  • lock & unlock을 프로그래머가 손쉽게 하도록 자료형 제공: S변수가 1⇒0(lock), 0⇒1(unlock)
• Busy Wating 문제는 여전히 발생함 ⇒ Block & Wake up 방식으로 해결

Q.spin lock이 critical section 문제를 해결하기 위한 O.S solution이라고 하는데, 왜 이 강의에서는 busy waiting의 또 다른 표현으로 일컫는거지?

• spin lock은 운영체제에 정의되어 있고 제공되는 동기화 메커니즘의 한 종류가 맞다. 멀티스레드 환경에서 사용되는 동기화 메커니즘이다. 프로세스 동기화에는 다른 메커니즘이 사용된다. 또한 한편으로는 critical section에 진입할 수 없을 때 대기하도록 하는 방식이기 때문에 busy waiting을 일컫는 표현 중 하나로 볼 수 있다.

• 이 강의에서는 굳이 semaphore와 spin lock으로 구분하는 것이 아니라 busy wating 방식의 semaphore(spin lock)과 block & wake-up 방식의 semaphore로 구분해서 설명하고 있는 거 가튼디

  Q.그럼 spin lock은 이 강의에서는 다루지 않고 있는데 어떻게 구현된 메커니즘이야?

  
  

Q.semaphore를 왜 사용하는거지? 그 전에 사용했던 것들과 어떤 차이점이 있지?

• 프로그래머가 추상화된 자료형으로 간단하게 동기화 문제를 처리할 수 있다.

---

Block / Wakeup Implementation

• 정수형 변수 S와 block 상태에서 대기 중인 프로세스의 리스트로 구현한 Semaphore

• P연산: 자원을 사용 가능한지를 나타내는(S.value)를 감소시키고, 사용 가능한 자원이 남았는지 확인, 0 미만이면 이미 모든 자원이 사용중이라는 의미이므로 block을 통해 suspend 상태로 만듦

• V연산: S.value를 증가시키고 만약 해당 값이 0이하이면, 자원이 없는 상태에서 S.value를 감소시킨 다른 프로세스들이 큐에서 대기중인 것을 의미하므로 프로세스를 wake up 시킴

• 여기서 S.value는 자원의 개수가 아니라 자원을 사용 가능한지, 깨울 프로세스가 있는지 확인하는 용도

---

Which is better? busy-wait과 block/wakeup

---

Two Types of Semaphores

• Counting semaphore: 여러 개 자원이 있을 때 사용가능한 자원의 개수를 표현하는 용도로 사용
• Binary semaphore: lock과 unlock을 확인하는(mutual exclusion) 용도로 사용
  

Q. 다시 한 번 semaphore, mutex, counting, spin lock은 각각 어떻게 구분되는가, 개념의 상호 연관성이 어떻게 되는가..?

• GPT의 답변을 보니 세마포어는 Block & Wakeup 방식으로 동작하는 것을 강조한 말이고, Spin Lock은 while문에서 busy-waiting하는 방식을 강조한 말이며, 자원의 개수를 나타내는 counter semaphore와 lock/unlock 상태를 나타내는 binary semaphore를 구분하기 위해 mutex를 사용한 거 같다.

---

Deadlock and Starvation

• 프로세스가 각각 semaphore Q와 S를 모두 필요로 할 때, P0이 S를 획득하고 P1에게 CPU를 빼앗기고, P1이 Q를 획득한 상황이면 둘 모두 서로가 필요한 다른 semaphore를 쥐고 있어 영원히 조건을 충족하지 못하는 dedalock 상태에 빠지게 됨

• 두 프로세스 모두 semaphore를 얻는 순서를 동일하게 한다면 CPU를 빼앗긴다고 해도 deadlock에 빠질 수가 없음

---

Dining-Philosophers Problem

• starvation: 양쪽에서 젓가락을 번갈아 가면서 가져가서 2개 젓가락이 다 있을 때가지 기다려야하는 놈을 죽게 만드는 상황
• deadlock: 5명이 동시에 배가고파져 왼쪽 젓가락을 잡으면 오른쪽 젓가락은 다른 사람이 가지고 있기 때문에 모두 영원히 밥을 먹지 못하는 상황 발생