OS - Synchronization Examples

Bounded buffer problem

no sybchronization

• 문제점1 : time quantum을 다 사용할 때까지 CPU를 사용하는 Busywating 문제 발생
• 문제점 2: 전역 변수 count의 동기화 문제 발생

Implementation with semaphores

• semaphore를 사용한다.
• mutex를 이용하여 critical section을 보호한다.
• full과 empty를 이용하여 wait상태로 block된 상태로 대기하게 만든다.

Implementation with mutex lock and condition variables

• not_empty/not_full의 condition variable 사용

• condition variable을 기다리는 동안 lock이 풀린다.

Reader and writers problem

• 몇 개의 thread는 쓰기를 하며, 몇 개의 thread는 읽기만을 한다.
• 한 번에 여러 thread가 read할 수 있다
• 한 번에 하나의 thread만 write해야 한다.
• write시에 write/read를 하면 안되며, read시에 write를 하면 안된다.

Implementation with semaphores

Implementation with Mutexlock

void writer()
{
	lock(L);
    // Writing...
    unclock(L);
}

void reader()
{
	if (count == 0) {
    	lock(L);
    }
    lock(L2);
    count++;
    unlock(L2);
    // READING ...
    lock(L2);
    count--;
    unlock(L2);
    if(count == 0)
    	unlock(L);
}

Dining-Philosophers problem (shared resource 문제 / semaphore로 구현)

• 철학자는 thinking / getting hungry / getting 2 chopsticks / eating 상태를 반복한다.

• 위의 상황은 철학자들이 모두 동일한 방향의 젓가락을 잡을 때 deadlock문제가 발생한다.
  • 흔하게 발생하는 상황은 아니다.

deadlock free version

• 철학자 별로 semaphore 구현
• deadlock의 문제는 해결하였지만 starvation문제가 발생할 수 있다.
  • aging기법을 통하여 starvation문제를 해결할 수 있다.

Monitor implementation