Synchronization Example

Bounded-Buffer Problem – Semaphore 방식

• 기존의 Bound Buffer 알고리즘은 count, in, out이 전역변수이므로 보호해야함
• Semaphore를 3가지 사용: mutex, empty, full
• mutex는 count, in, out을 전체로 보호하는 semaphore
• produce: empty는 데이터를 추가하면 wait(empty);하며 empty--;이후 작업을 다하면 signal(full);을 하며 full++;
• consume: full은 데이터를 소모하면 wait(full);하며 full--;이후 작업을 다하면 signal(empty);을 하며 empty++;
• full이 N이면 buffer가 꽉찬 뜻, empty가 N이면 buffer가 빈 뜻

Bounded-Buffer Problem – MutexLock + condition variable 방식

• Condition Variable를 2가지 사용: not_full, not_empty
• mutex는 공유자원(ConditionVariable, count, in, out)을 보호
• produce
  while(count==N): 이미 buffer가 꽉 찼는데 데이터를 produce하려고하면 not_full조건에 대기 시킴 / 꽉 차지 않아서 데이터를 추가하게 되었다면 not_empty의 프로세스에게 signal 보냄
• consume
  while(count==0): 이미 buffer가 비어있는데 데이터를 consume하려고하면 not_empty조건에 대시 시킴 / 비지 않아서 데이터를 소모하게 되었다면 not_full의 프로세스에게 signal 보냄

Readers-Writers Problem

• readcount: 읽는 사람의 수인 정수 / Semaphore를 2가지 사용: mutex, wrt
• mutex는 Reader프로세스에서 공유자원인 readcount를 보호하기 위해 사용
• wrt: 1→write를 아무도 하지않는 상태, 0→write중인 상태의 semaphore
• Writer
  파일을 써야하므로 처음에 wait(wrt)하고 다 썼다면 signal(wrt)
• Reader
  1. 읽는 사람 수를 readcount++로 먼저 증가시킴
  2. if(readcount==1) 최초로 파일을 읽은 프로세스에 한해서 wait(wrt)를 함으로써 Write를 할 수 없도록 방지
  3. 다 읽었다면 읽는 사람 수인 readcount--
  4. if(readcount==0) 마지막으로 읽는 프로세스가 작업을 마무리했다면 Write를 할 수 있도록 signal(wrt)
• readcount를 도입하지 않으면 Reader가 여럿일 때, wait(wrt)가 계속 되어서 DeadLock에 빠짐
• 최초로 실행하는 친구가 문을 닫고, 마지막으로 실행을 마치는 친구가 문을 열어줘야함

Dining Philosopher – simple solution

• 원탁에 철학자가 앉아있고 젓가락이 사람 사이에 한 개씩만 존재
• 양쪽의 젓가락을 하나씩 가져와서 밥을 먹어야 할 때
• 언젠가는 DeadLock이 반드시 걸리게 되는데 이를 해결하는 알고리즘
  
• 왼쪽은 chopstick[i], 오른쪽은 chopstick[(i+1)%N] semaphore취급
• BUT! N명의 철학자(프로세스)가 거의 동시에 실행되어 왼쪽을 다같이 집으면 오른쪽은 영원히 못집어서 다같이 DeadLock

Dining Philosopher – DeadLock-Free version

• semaphore를 젓가락이 아닌 각 철학자의 상태(not eating은 0 eating은 1)로 정의하고 각 철학자가 HUNGRY인지 THINKING인지를 state[N]저장
• philosopher
  • 각 철학자는 think(), pickup(i), eat(), putdown(i) 반복
  • i는 철학자의 인덱스
• test
  1. 철학자의 state가 HUNGRY이고 왼쪽과 오른쪽 철학자가 EATING이 아니라면 = 내가 배고프고 양쪽이 먹는중이 아니라면
  2. state를 EATING으로 변경하고 내가 eating을 한다는 뜻으로 s[i] semaphore를 1로 설정 = 난 식사를 시작하고 signal을 준다
• pickup
  1. 젓가락을 든다는 것은 배고프다는 것이므로 state[i]= HUNGRY
  2. test(i)로 식사 로직 가동
  3. state는 공유자원이므로 mutex로 보호
  4. wait(s[i])를 통해 test가 실행이 되었었다면 빠져나가고 test가 실행이 되지 않았다면 wait에 걸림
• putdown
  1. 젓가락을 내려놓는 것은 다 먹었다는 것이므로 state[i]=THINGKING
  2. 왼쪽과 오른쪽 철학자를 test시킴
  3. state는 공유자원이므로 mutex로 보호

Dining Philosopher – Java Monitor

자바는 Monitor로 공유자원 보호하므로 MutexLock, Semaphore를 사용하지 않음

• test
  (i+4)%5 왼쪽사람과 (i+1)%5 오른쪽 사람이 EATING중이고 i인 내가 HUNRY상태면 i의 상태를 EATING으로 바꾸고, i 스스로에게 signal을 보냄
• pickup
  1. 배고파서 젓가락을 드는 것이므로, state[i] = HUNGRY
  2. test(i)를 실행
  3. i의 양옆사람이 젓가락을 사용중이라 EATING상태가 아니라면 i는 wait()
  4. i의 양옆사람이 젓가락을 사용 안한다면 i는 test를 통해 signal을 보냄
• putdown
  밥을 다먹고 THINKING상태로 변경후 양쪽 사람들을 test()

Synchronization Tools in Real World

POSIX

• Semaphore: sem_init, sem_wait, sem_trywait, sem_post..
• MutexLock: pthread_mutex_init, pthread_mutex_lock, pthread_mutex_unlock..
• Condition Variable: pthread_cond_init, pthread_cond_wait, pthread_cond_signal..

Java

Monitor이외에도 synchronized 키워드를 통해 공유자원에 접근을 통제할 수 있음