[Operating System] Synchronization Examples

Classic Problems of Synchronization

The Bounded-Buffer-Problem

• producer and consumer processes가 공유하는 자료 구조들 :
  - int n;
  - semaphore mutex = 1 : Buffer에 하나의 프로세스만 접근 가능
  - semaphore empty = n,
  - semaphore full = 0 : empty, full semaphore의 수를 세준다.
  
  
• 둘이 대칭적이다 -> producer는 consumer를 위해 fulled buffer를 제공, consumer는 producer를 위해 empty buffer를 제공한다고 생각해도 된다.

The Readers-Writers Problem

• 여러 프로세스가 shared 데이터베이스에 접근해서 read, write를 할 경우에 대한 문제이다.
• 각각을 reader, writer라고 칭한다.
• reader만 여러 명 있을 경우 문제가 되지 않지만, writer가 다른 reader나 writer와 같이 있는 경우 문제가 생긴다.
• 여러 variation이 존재한다.
  • first readers-writers problem : writer가 shared object에 대한 권한을 얻기 전까지 reader는 기다리지 않는다. 즉, writer가 ready이고 기다리고 있다고 할지라도 이미 실행중이지 않는 한 reader는 바로 실행된다.
  • second readers-writers problem : writer가 ready되면, writer는 가능한 한 빨리 write를 수행하게 된다. 즉, writer가 기다리고 있을 때 새로운 reader는 읽기 시작하지 않는다.
• 둘 다 starvation이 발생한다.
  • first : writer가 굶게 된다.
  • second : reader가 굶게 된다.
• first readers-writers problem의 해결책
  • reader process는 다음 자료구조들을 공유한다.
    - semaphore rw_mutex = 1 : reader, writer 모두에게 공유됨. writer의 경우 mutual exclusion을 위해 쓰이고, critical section에 출입하는 first or last reader에게도 쓰인다. (이미 reading중이라면 그냥 읽으면 되지만, reading이 아닐 경우에는 writing중인지 확인해야 하고, reading을 다 끝마치면 writing에게 기회를 넘겨주어야 하기 때문임.)
    - semaphore mutex = 1 : read_count 값을 변경할 때 쓰이는 mutex.
    - int read_count = 0 : reading중인 프로세스의 수.
    
    
• readers-writers problem과 solution은 일반화되어 reader-writer lock이라는 것이 생겨나게 되었다.
  • read mode, write mode가 존재해서 다음과 같이 쓰일 수 있다.
    • shared data를 접근할 때 read하기만 하는 프로세스와 write하기만 하는 프로세스를 구별하기 쉬운 경우.
    • readers가 writers보다 더 많은 경우 : 일반적으로 semaphore나 mutex에 비해 복잡해서 overhead가 발생하지만, 동시에 read를 하는 경우를 통해 상쇄한다.

The Dining-Philosophers Problem

• Semaphore Solution
  

  • 각 젓가락을 semaphore로 표현한다.
    -> shared data : semaphore chopstick[5];
    chopstick의 element는 모두 1로 초기화되어 있다.
    • 이웃한 사람들끼리는 동시에 먹지 않는 것을 보장하지만, deadlock이 발생할 수 있다.
    • 5명이 동시에 배고파져서 모두 왼쪽 젓가락을 집었다면, 오른쪽 젓가락을 집으려고 하지만 이미 집혀진 상태이므로 영원히 먹지 못하게 된다.
    • 몇 가지 deadlock problem을 위한 해결책
      • 최대 4명까지 테이블에 동시에 앉게 한다.(동시에 배고픈 사람이 최대 4명)
      • 양쪽 젓가락이 모두 사용가능할 때에만 젓가락을 들어올린다. (집어올리는 행동 자체가 critical section이 되어야 한다.)
      • asymmetric solution : 홀수번째는 왼 -> 오 순서로 들어올리고, 짝수번째는 오 -> 왼 순서로 들어올린다.

• Monitor Solution
  

  • 양쪽이 모두 available할 때만 젓가락을 들어올린다.
  • 사용되는 자료구조
    • enum{THINKING, HUNGRY, EATING} state[5] : philosopher i는 이웃한 사람들이 모두 먹고있지 않을 때에만 state[i]를 EATING으로 바꿀 수 있다.
    • condition self[5] : hungry상태이지만 chopstick을 집을 수 없어 기다리는 상태를 위한 condition에 해당한다.
  • DiningPhilosophers.pickup(i);
  • eat;
  • DiningPhilosophers.putdown(i);
    의 과정을 통해 진행된다.
  • Deadlock이 일어나지 않음은 보장, but starvation은 해결되지 않는다.

Synchronization within the Kernel

Synchronization in Windows

• 넘기기

Synchronization in Linux

• 2.6버전 이전에 Linux는 nonpreemptive kernel이었음. -> 이후에 fully preemptive가 됨.
• 대다수의 컴퓨터 아키텍쳐가 간단한 수학 연산을 atomic version으로 제공하듯, 리눅스 또한 atomic integer를 data type atomic_t를 이용해서 지원한다. atomic integer를 사용한 모든 수학 연산은 interruption 없이 이루어진다.
• 예를 들어
  atomic_t counter;
  int value;
  가 있다고 하자.
  
  • 이런 식으로 사용될 수 있다.
• Atomic integer는 counter와 같은 정수값이 업데이트되어야 할 때 특히나 효과적이다. locking mechanism을 위한 overhead가 없기 때문.
• 하지만 더 많은 변수가 race condition을 발생시키는 경우와 같이 복잡한 경우에는 locking tools를 사용해야 한다.
• 리눅스에서는 mutex lock, spinlock, semaphore(reader-writer version을 포함해서) 를 kernel에서의 locking을 위해 제공한다.
• SMP machine에서는 fundamental locking mechanism은 spinlock이고, 물론 짧은시간동안 spin하게끔 설계되어 있다.
• single-processor machine에서는 당연히 spinlock은 굉장히 비효율적이다. 그래서 spinlock을 acquire하는 것 대신, kernel preemption을 비활성화하고, spinlock을 release하는 대신 kernel preemption을 활성화한다.
  - 이유(뇌피셜)
  애초에 spinlock이 busy wait을 돈다는 상황 자체가 이미 다른 프로세스에서 lock을 걸고 실행하고 있다는 뜻인데, 그럴 바에는 그냥 kernel에서의 spinlock의 acquire를 preempt_disable()로 하고, release를 preempt_enable()로 바꾼다면 아무런 interrupt를 받지 않고 critical section에서의 작업이 이루어질 수 있으므로 이런식으로 동작하게 되면 busy wait가 발생할 일이 없게 된다.
  
• 리눅스 커널에서는 spinlock과 mutex lock 둘 다 nonrecursive 해서 그 lock을 해제하기 전까지 동일한 lock을 2번째로 acquire할 수 없다. -> 시도 자체가 block된다.
• 리눅스에서 preemption을 설정하는 방법 : system call
  • preempt_disable(), preempt_enable()
• 물론 task가 lock을 holding하고 있다면 not preemptable하다. -> 이를 위해서, 각 task는 thread-info structure를 가지고 있어서 counter인 preempt_count를 통해 현재 task가 holding하고 있는 lock의 수를 기록한다.
  • lock이 acquire되면 preempt_count가 증가, release되면 감소한다.
  • preempt count가 0보다 크다면 kernel을 preempt하면 안 되고, 0이라면 preempt를 해도 괜찮다.
• spinlock은 lock이 짧은 시간동안만 필요한 경우에만 쓰인다. 나머지는 semaphore나 mutex를 사용해야 한다.

참고 자료

• Abraham Silberschatz, Operating System Concepts, 10th edition