Semaphore

1. Semaphore의 정의

Semaphore는 정수 값을 가진 객체이다.
우리는 sem_wait()과 sem_post()를 이용하여 조작할 수 있다. sem_init의 두 번째 매개변수 0의 의미는 semaphore가 같은 프로세스 내 스레드간 공유 된다는 의미이고, 세 번째 매개변수 1은 초기값을 뜻한다.

• sem_wait()
  • 만약 sem_wait()이 호출되었을 때 semaphore의 값이 1이거나 더 크다면 즉시 리턴한다.
  • sem_wait이 호출되면 caller가 post를 기다리며 실행을 중지한다.
  • 음수일때, 세마포어의 값은 waiting하고 있는 스레드의 수와 같다.
    
    
• sem_post()
  • 단순히 세마포어의 값을 증가시킨다.
  • 만약 깨어나길 기다리는 스레드가 있다면, 그 중 하나를 깨운다.
    
    

2. Binary Semaphores (Locks)

Locks의 기능을 세마포어로 구현하기 위해 초기값은 1로 설정되어야 한다.
다음은 두 개의 스레드가 세마포어를 사용하는 것을 보여준다.
초기 세마포어 값은 1이고, Thread0이 wait을 호출하면 세마포어 값은 0이되고 critical section을 수행한다. critcial section을 수행 중 context switch가 발생하여 Thread1이 수행되어 sem_wait()을 호출하고 값을 확인한다. 이 때 -1로 0보다 작으므로 sleep하게 된다.
이후 Thread1이 critical section을 마치고 sem_post를 호출하여 세마포어 값을 증가시키고 Thread1을 깨운다.
이제 Thread1에서 semaphore의 값을 확인하고 음수가 아니므로 sem_wait을 리턴하고 critical section에 진입한다.

3. Semaphore As Condition Variables

Condition Variables로서 세마포어를 사용하기 위해 초기 값을 0으로 설정해야 한다.
다음 두 가지 경우를 보자.

1. 자식이 sem_post()를 call하기 전에 부모가 sem_wait()을 call하는 경우.

2. 자식이 부모가 sem_wait()을 call하기 전에 먼저 끝나는 경우. 이 경우 문제가 생길 것 같지만 다음과 같이 세마포어의 값이 Condition Variables 역할을 잘 해주면서 문제가 발생하지 않는다!

4. The Producer/Consumer (Bounded-Buffer) 문제

• Producer: put() interface
  • 데이터를 버퍼에 넣기 위해 버퍼가 빌 때까지 기다린다.
• Consumer: get() interface
  • 버퍼를 사용하기 전에 버퍼가 찰 때까지 기다린다.
    
    위 코드에서 MAX가 1보다 크다고 가정하자.
    만약 다수의 producers가 있다면, line f1에서 race condition이 발생할 수 있다. f1과 f2사이에 context switch가 발생할 경우 fill에 값을 채운 뒤 fill을 증가시키지 않는다. 따라서 현재 buffer의 fill에 값이 overwrite되는 문제가 생길 수 있다.
    => mutual exclusion 문제: buffer를 채우는 것과 버퍼의 index값을 증가시키는 것은 critical section이다.

일반적으로 mutual exclusion이 보장되지 않으면 race condition이 발생한다._

Adding Mutual Exclusion

위 mutual exclusion 문제를 해결하기 위해 lock을 위한 세마포어를 추가하였다.

• 하나의 producer와 하나의 consumer 스레드를 생각해보자.
  • c0 line에서 consumer는 mutex를 얻는다. (초기 값이 1이므로 즉시 리턴하여 mutex 흭득)
  • c1 line에서 consumer는 full 세마포어에서 sem_wait()을 call한다. (초기 값이 0이므로 wait하면 음수가 되어 sleep)
  • consumer는 blocked되고 CPU를 yield한다. 하지만 mutex는 가지고 있다.
  • line p0에서 producer는 mutex에서 sem_wait()을 call한다.
  • producer는 계속해서 waiting한다. 전형적인 deadlock 형성

• DeadLock: 두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태

Working Solution

mutex와 empty에 대한 wait의 위치를 바꾸면 해결된다!

5. Reader-Writer Locks

삽입과 단순히 검색하는 것을 포함하는 여러 동시 작업 리스트가 있다고 생각해보자.
삽입은 리스트의 상태를 변경한다. 즉 전통적인 critical section이 맞다.

검색하는 것은 단순히 데이터를 읽는 것으로, 많은 검색이 동시에 이루어 질 수 있다.

이와 같이 특별한 타입의 lock인 reader-writer lock이 있다.

• 오직 하나의 writer만 lock을 얻을 수 있다.
• 일단 reader가 read lock을 얻으면
  • 더 많은 reader가 read lock을 얻는 것을 허용한다.
  • writer는 reader들이 다 읽을때 까지 기다려야한다. => starvation 문제

코드를 살펴보자. acquire_readlock에는 reader를 증가시키고, 최초의 reader라면 write lock을 wait하는 코드를 포함한다. release_readlock에는 reader를 감소시키고, 마지막 reader이면 write lock을 post하는 코드를 포함한다. wirter는 일반적인 semaphore의 lock을 얻는 과정과 동일하다.

reader-writer locks은 fairness 문제를 가진다.

• 상대적으로 reader가 writer를 굶기기 쉽다.
• 어떻게 writer가 waiting하고 있으면 reader가 들어오는 것을 막을 수 있을까?
  => critical section을 기다리는 writer가 있으면 더 이상 reader를 받지 않는 방식으로 해결

6. The Dining Philosophers

다음과 같이 5명의 철학자가 테이블에 앉아있다고 가정하자. 각 철학자 사이에는 하나의 포크가 있다.
철학자들은 포크가 필요없는 생각하는 시간과, 왼쪽 오른쪽 양쪽 모두의 포크가 필요한 먹는 시간이 있다. 이 포크에 대한 contention이 발생에 대한 문제이다.

주요 쟁점으로는

• dead lock이 없어야 한다.
• 어떤 철학자도 굶어선 안되고 먹지 못해서는 안된다.
• Concurrency가 높아야 한다.

만약 fork에 대한 sem_t fork[5]와 같이 세마포어를 사용하고 다음과 같이 코드를 작성한다면 Deadlock이 발생한다. 만약 모든 철학자가 오른쪽 포크를 잡기전에 그들의 왼쪽 포크를 잡는다면, 모두 왼쪽 포크를 하나씩 들고 오른쪽 포크를 계속 기다릴 것이다. (모두 다른 철학자가 포크를 내려놓기만을 기다리고 있음)

해결책으로는 포크를 흭득하는 방식을 바꿔서 의존성을 없애는 방법이 있다. 예를 들면 위와 같이 4번째 철학자만 포크를 흭득하는 순서를 바꾼다. 이렇게 하면 모든 철학자가 하나의 포크를 잡고 반대쪽 포크를 기다리는 일이 없어진다. (The cycle of waiting is broken)

7. Semaphore의 구현

Zemaphores라고 불리는 우리의 semaphores를 구성해보자. (condition variables 이용) 값이 0이하인지 확인하고 0보다 큰 경우만 value값을 1 감소시킨다. => semaphore처럼 값이 음수가 되는 경우 존재하지 않음.

• 값은 0보다 작을 수 없다.
• 이것은 구현하기 쉽게 만들고 현재 리눅스 구현과 일치한다.

여기까지 운영체제의 큰 주제중 하나인 Concurrency에 대해 끝이 났습니다.
다음 글부터는 persistence에 대해 공부해 보겠습니다.