[OS] CH31_Semaphores: lock과 condition variables을 대신해서 어떻게 semaphores을 쓸까?

출처: http://pages.cs.wisc.edu/~remzi/OSTEP/threads-sema.pdf

 

The crux: lock과 condition variables을 대신해서 어떻게 semaphores을 쓸까?

 

31.1 Semaphores: A definition

semaphore: 우리가 두 개의 루틴으로 조작할 수 있는 정수 값을 가진 객체

POSIX 표준에서는 이 루틴은 sem_wait(), sem_post()이다

 

semaphore의 초기화 값은 이것의 행동을 결정하므로 초기화 필수

 

1. semaphore 초기화

sem_init(&s, 0, 1); // semaphore가 같은 프로세스 내에서 thread를 공유 

                    ㄴ 초기화 값은 1이면 critical section을 보호하는 lock처럼 사용가

 

2. sem_wait(), sem_post() 중에서 하나의 함수를 호출

* 두 함수를 여러 thread가 호출한다면 critical section을 관리 해줘야 함

 

인터페이스의 중요한 측면

- sem_wait(): semaphore 값을 1 감소 시키고, 그 값이 음수가 되면 wait함

 

- sem_post(): sem_wait()와 달리 특정 조건을 잡기 위해 기다리지 않는다 

  semaphore의 값을 증가시키고, 만약 깨어나길 기다리는 thread가 있으면 깨운다

 

- semaphore 값이 음수이면 기다리는 thread의 수와 같다.

  이 값은 semaphore 사용자에게 보이지 않는다 (semaphore가 어떻게 작동되는지 기억하는데 도움)

 

 int sem_wait(sem_t *s) {
	decrement the value of semaphore s by one
 	wait if value of semaphore s is negative
 }

 int sem_post(sem_t *s) {
	 increment the value of semaphore s by one
	 if there are one or more threads waiting, wake one
}
sem_t m;
sem_init(&m, 0, X); // initialize to X; what should X be?

sem_wait(&m);
// critical section here
sem_post(&m);

ㄴ A binary semaphore

-> atomic하게 수행하므로 race condition 걱정할 필요 없음

 

31.2 Binary Semaphores (Locks)

lock은 held, not held 두가지 상태가 있어서 lock을 사용하는 semaphore을 binary semaphore라고 부름

 

ex1) Single thread using a semaphore

처음 semaphore초기화 할 때 value=1

첫번째 thread인 thread0이 sem_wait()을 호출 했다고 하자

thread0은 semaphore의 값을 감소 시킴 -> semaphore값은 0이 됨 

값이 음수면 기다림

sem_wait()는 리턴하고 호출한 thread가 계속된다. 

thread0은 이제 critical section에 들어간다.

만약 thread0이 critical section에 있는 동안, lock을 얻으려고 시도하는 다른 thread가 없다면, sem_post() 호출할 때, 이것은 semaphore의 값을 1로 복구시킨다.

   

ex2) Two threads using a semaphore

thread0이 sem_wait()호출하고 sem_post() 호출하기 전에

다른 thread인 thread1이 sem_wait()을 호출하면 semaphore 값은 -1이 되므로 기다림 ( 스스로 sleep하고, 프로세서 포기)

다시 thread0이 작동하면서 sem_post() 호출하게 되고, semaphore 값이 0으로 증가됨

그리고 기다리는 중인 thread인 thread1을 깨움

thread1이 끝나면 semaphore의 값을 다시 증가시킨다. -> 값 1됨

 

31.3 Semaphores for ordering

semaphore은 동시에 발생하는 프로그램에서 이벤트를 정렬하는데도 사용됨

semaphore을 0으로 초기화  -> parent thread 기다리는 동안 child thread 먼저 실행하게 하려고 

sem_t s;

 void *child(void *arg) {
   printf("child\n");
   sem_post(&s); // signal here: child is done
   return NULL;
 }

 int main(int argc, char *argv[]) {
   sem_init(&s, 0, X); // what should X be?
   printf("parent: begin\n");
   pthread_t c;
   Pthread_create(&c, NULL, child, NULL);
   sem_wait(&s); // wait here for child
   printf("parent: end\n");
   return 0;
 }

Child가 먼저 post하지 않으면 semaphore값은 0이여서 parent는 무조건 sleep함 

 

 

 

31.4 The producer/consumer (Bounded buffer) problem

문제 해결

1. empty, full semaphores

-> buffer entry가 비어있거나 꽉 차있을 때, 나타내는데 사용

 

생산자는 데이터를 넣기 위해서, 버퍼가 비기를 기다린다.

소비자는 데이터를 사용하기 전에, 버퍼가 차기를 기다린다.

 

in a single cpu

ex1) 문제1

MAX=1이라고 해보자. 두 개의 thread, producer와 consumer이 있다.

consumer가 먼저 작동한다고 가정하자.

그럼 sem_wait(&full)를 호출하게되고, 그럼 full--된다 (full==-1) -> consumer은 block되고 다른 thread가 sem_post()를 호출하기를 기다린다.

그런 다음 producer가 작동한다고 가정해보자.

그럼 sem_wait(&empty)를 호출하게 되고, empty는 처음에 max(1)로 초기화 되어 있었기 때문에, 소비자와 달리 계속 코드 진행됨. (empty==0)

생산자는 데이터를 버퍼의 첫번째 엔트리에 넣는다. 그 후 sem_post(&full)을 호출해서 full++해준다 (full=0)

그리고 소비자 깨운다.

 

문제1. 만약 생산자가 계속해서 작동하면 sem_wait(&empty)가 반복됨

-> empty가 0되면 block되어야 함

 

ex2) 문제2

MAX가 1이상이라고 해보자.여러개의 생산자와 소비자가 있다고 가정해보자.

race condition문제가 생긴다.

만약 두 개의 생산자(Pa and Pb)가 동시에 put()을 호출한다고 해보자

Pa가 먼저 작동했다고 했을 때, 첫번째 버퍼 엔트리가 채워지기 시작한다. (fill=0, buffer[fill]=value;)

Pa가 fill을 증가시키기 전에 interrupt되고 Pb가 작동한다면 이 또한 fill아직 0이므로 buffer의 첫 부분에 값을 넣게된다.

-> 예전 데이터가 덮어씌여짐

 

해결책: Adding mutual exclusion

buffer에 값 넣고, 인덱스 증가시키는 부분을 critical section으로 해서 lock을 더함

-> put()/get() 부분에 lock 씌움

-> 이렇게 하면 잘 작동되지 않음. deadlock 문제 있음

 void *producer(void *arg) {
   int i;
   for (i = 0; i < loops; i++) {
     sem_wait(&mutex); // Line P0 (NEW LINE)
     sem_wait(&empty); // Line P1
     put(i); // Line P2
     sem_post(&full); // Line P3
     sem_post(&mutex); // Line P4 (NEW LINE)
   }
}

생산자 하나, 소비자 하나해서 두 개의 thread가 있다고 해보자

소비자가 먼저 시작하고 mutex를 얻어서 sem_wait()을 호풀한다고 해보자.

아직 데이터가 없기 때문에 consumer은 block되고 cpu를 포기한다. 하지만 소비자는 아직 lock을 가지고 있다

그 후, 생산자가 작동한다. 생산할 데이터가 있고, 작동 가능하지만 lock is held -> 생산자는 계속 기다림

생산자 소비자 둘 다 각 각 서로를 기다림 -> deadlock

 

void *producer(void *arg) {
 int i;
 for (i = 0; i < loops; i++) {
 sem_wait(&empty); // Line P1
 sem_wait(&mutex); // Line P1.5 (MUTEX HERE)
 put(i); // Line P2
 sem_post(&mutex); // Line P2.5 (AND HERE)
 sem_post(&full); // Line P3
 }
}

ㄴ> deadlock 문제 해결

 

31.5 Reader-Writer locks

어떤 thread가 데이터 구조를 업데이트 하려면, 새로운 동기화 연산 쌍을 호출해야한다.

- rwlock_acquire_writelock(): write lock을 얻기 위해

- rwlock_release_writelock(): release하기 위해

이것은 간단히 writelock semaphore을 사용해서 하나의 writer만 lock을 얻을 수 있고 데이터 구조를 업데이트 하기 위해 critical section 들어갈 수 있음을 보장한다.

 

read lock을 얻을 때, reader는 일단 lock을 얻고 얼마나 많은 reader들이 동시에 데이터 구조에 있는지 추적하기 위햇 readers 변수를 증가 시킨다.

- rwlock_acquire_readlock(): reader가 lock 얻을 때

  이 경우에 reader는 writelock semaphore에서 sem_wait()을 호출해서 write lock도 얻는다.

그리고 sem_post()를 호출해서 lock을 풀어준다.

따라서, reader가 일단 read lock을 얻으면 다른 reader들도 read lock 얻을 수 있다. 그렇지만 어떤 thread가 write lock을 얻고 싶어하면 모든 reader들이 끝나기를 기다려야한다. 

 

-> starvation 문제 있음

 

starvation 해결책:

일단 writer가 기다리고 있으면 더 이상 reader가 들어오는 것을 막자

 

 

31.6 The dining philosophers

: 동그란 식탁에 철학자들이 둘러 앉았을 때, 음식을 먹기 위해서는 양쪽에 있는 두 개의 포크를 사용해야할 때 생기는 문제

 

문제점:

모든 철학자가 왼쪽 포크(동일한 어느 한쪽)를 잡을 수는 있지만 오른쪽 포크는 모두 다른 사람이 쥐고 있으므로 계속해서 서로를 기다르는 교착 상태에 빠지게 된다

-> starvation 

 

해결책:

다섯명의 철학자가 있다고 했을 때,

네명은 오른쪽 포크를 잡도록 하고, 마지막 철학자는 왼쪽 포크 먼저 잡게한 후, 오른쪽 포그를 잡는 방식을 총해 교착 상태를 막는다