[운영체제] OS 7장 Synchronization Examples

• application process나 thread가 사용하는 모델은 세마포어와 모니터 + mutex lock
• 세마포어는 바이너리와 카운팅이 있는데 바이너리는 mutex lock 형태와 같게 사용할 수 있다.

Classical Problems of Synchronization

---

• Bounded-Buffer Problem
• Readers and Writers Problem
• Dining-Philosophers Problem

Bounded Buffer Problem

• busy-wait을 하게 됨. CPU 낭비. CPU를 사용하지 않고 block 상태로 waiting 하도록 해야 함. 세마포어를 통해 구현
• critical section 보호가 되지 않고 있다.(M.E가 안되고 있음)

• 세마포어 변수 mutex로 critical section 보호 
• busy wait 없애기 위해서 empty변수와 full변수, full이 있어야지만 Consumer가 들어갈 수 있음
• 데이터가 들어가 있는 아이템의 수를 full, 데이터가 비어있는 아이템의 수를 empty
• count가 N일 때까지 루프를 도는 것을 empty라는 세마포어를 이용해서 프로세스 또는 스레드가 세마포어를 wait 하면서 block 된 상태로 존재할 수 있도록 하였다.
• Consumer 입장에서는 busy-wait을 없애기 위해서 full이란 세마포어를 정의하였음
• Consumer가 먼저 수행되었는데 full이란 세마포어가 0 임, wait 시스템 콜을 해서 full이란 세마포어 값을 봤더니 0 그러면 Consumer라는 스레드가 (block) waiting 상태로 바뀌고 Producer가 실행됨.

• mutex lock을 이용
• critical section 안에서 무언가를 기다릴 때 사용하는 것이 condition variable(not empty, not full)
• count==0 이면 큐가 비어있으니까 not empty라는 condition variable을 기다림 그러면 이 순간 프로세스의 상태는 blocked waiting, mutex lock과 condition variable은 같이 쓰이고 이때 잠시 critical section을 보호하는 mutex가 lock이 풀린다. 그러면 Producer가 수행될 수 있어서 count++하고 not empty라는 condition variable에 signal 해준다. 그리고 unlock 하면 기다리고 있던 Consumer가 깨어나서 wait부터 수행하며 이어서 동작한다.(아까 잠시 lock을 풀었던 것이라서 다시 잠근다.)
• producer consumer가 하나씩만 있으면 if로 해도 전혀 문제가 없는데 여러 개 일 경우는 while로 작성해야 안전한 코드가 된다.

Readers-Writers Problem

• 읽는 애도 여러 개 쓰는 애도 여러 개
• 한 명이 읽고 있을 때 다른 애가 읽는 건 상관없음 read는 여러 명이 동시에 해도 됨
• read 하고 있을 때 다른 애가 write 하면 안 된다. 
• write 하고 있을 때 다른 애가 read 하거나 write 하려고 하면 안 된다.

• Read와 Write 부분이 critical section
• readcount라는 변수를 만들어서 현재 read 하고 있는 스레드의 숫자를 계산함
• readcount가 shared data가 되기 때문에 세마포어를 하나 더 선언해서 critical section을 보호해 준다.

Dining Philosopher

• 각각의 철학자들은 생각을 하고 배고파지면 왼쪽과 양쪽의 젓가락을 집어서 밥을 먹고 다 먹고 나면 다시 생각함.
• 젓가락을 옆에 앉은 사람과 공유함
• 한 명이 젓가락을 들게 되면 그 양옆에 있는 사람들은 다 먹을 때까지 기다려야 함

• 젓가락이 shared data니까 젓가락을 세마포어로 만들고 1로 초기화함
• 세마포어는 shared resource의 개수
• 젓가락이 5개라고 해서 카운팅 세마포어가 5가 아니고 젓가락이 5개가 있으니까 세마포어가 5개 있는데 젓가락이라는 세마포어가 가질 수 있는 값은 0 또는 1, 0과 1을 반복하는 바이너리 세마포어로 젓가락을 구현할 수 있다.
• i는 철학자의 번호를 나타냄 0,1,2,3,4
• 젓가락도 0,1,2,3,4
• 철학자라는 스레드가 5개가 생긴다.
• wait(chopstick [i])은 왼쪽 젓가락을 가지는 효과, wait(chopstick[(i+1)% N])은 오른쪽 젓가락을 가지는 효과
• 두 개의 젓가락을 갖게 되면 밥을 먹음
• 밥을 다 먹었으면 젓가락을 반환 signal(chopstick [i]), signal(chopstick[(i+1)% N])
• 밥 먹는 철학자는 스레드를 synchronization 하는 것이지 critical section을 보호하는 것이 아니다.
  • 0번 철학자가 양쪽의 젓가락을 다 들고 밥을 먹고 있을 때 1번 철학자가 밥을 먹으려고 한다면 젓가락 1번을 0번 철학자가 사용하고 있기 때문에 밥을 먹을 수 없다. 1번 철학자의 상태가 waiting. 0번 철학자가 밥을 다 먹고 젓가락을 반납하면 1번 철학자가 ready상태가 되고 1번 철학자가 스케줄링되어서 1번 철학자가 밥 먹음.
• deadlock은 언제 발생할까
  • 모든 철학자가 밥을 먹으려고 할 때 모두 동시에 왼쪽 젓가락을 집는 경우 근데 오른쪽은 이미 다른 사람이 집었음 그래서 서로를 계속 기다리는 상황이 발생한다.
  • 0번 철학자가 생각하고 있다가 배고파서 왼쪽 젓가락을 wait 해서 집음 그리고 오른쪽을 집으려고 했는데 그때 interrupt가 발생 1번 철학자가 실행됨 그리고 얘도 왼쪽 젓가락을 wait 해서 집음 여기서 또 interrupt 발생, 2번 철학자도 똑같이 왼쪽 젓가락을 집음... 이런 식으로 하다 보면 결국 모두가 자신의 오른쪽 젓가락 집는 것을 기다리게 됨. deadlock 발생

• 알고리즘적으로 deadlock에 빠질 가능성이 없는 알고리즘으로 만들어보자. 어떻게 하냐면 내가 배고플 때 왼쪽 젓가락과 오른쪽 젓가락을 본다. 둘 다 있으면 두 개를 동시에 집는다. 둘 중 하나라도 없다면 아무것도 잡지 않는다.
• 구현하기 위해서 젓가락 별로 세마포어를 두지 말고 철학자 별로 세마포어를 둔다. 지금 밥 먹을 수 있다 없다를 나타내는 세마포어를 철학자 별로 준 것
• state가 전역변수기 때문에 critical section 보호를 해줘야 함. 세마포어 변수 하나 만들어서 들어갈 때 wait 나갈 때 signal
• starvation이 발생할 수도 있다. 0번이 밥을 먹고 1번은 못 먹고 있을 때 2번이 또 밥을 먹기 시작하면 0번이 그만 먹더라도 1번은 밥을 먹을 수 없다. 이것을 해결하기 위해서 aging 알고리즘을 이용한다.

• 밥 먹는 철학자를 모니터로 구현

• deadlock 해결, 세마포어와 condition variable 이용

Synchronization Tools in Real World

---

POSIX Semaphores

• trywait은 0일 때 -1 해서 안 되는 경우 fail 처리

POSIX Mutex Locks

POSIX Condition Variables

• critical section 안에서 이벤트가 발생할 때 사용하는 게 condition var
• critical section 안에서 가지고 있는 lock을 일시적으로 풀어야 함

Bounded Buffer with POSIX Semaphores

Bounded Buffer with POSIX Mutexes & Cond. Vars

Bounded Buffer with Java Monitor