Semaphore and Common Concurrency Problem

Semaphore: A definition

 

#include <semaphore.h>
sem_t s;
sem_init(&s, 0, 1); // initialize s to the value 1
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 vlaue of semaphore s by one
    if there are one or more threads waiting, wake one
}

 

sem_t 에 대한 객체 s는 integer value 를 가지고 있으며 sem_wait(), sem_post() 으로 조작이 가능하다.

 

(1) sem_init : semaphore s에 대한 초기화 작업이 이뤄지는데 값 1으로 초기화를 한다.

      두번째 argument 으로 설정된 0은 동일 process 내에서 쓰레드들 사이에 공유된 semaphore 를 나타낸다.

(2) sem_wait : semaphore의 값이 1 또는 그 이상일 경우에 호출될 때 decrement 한 값을 바로 return 한다.

      그리고 semaphore 의 값이 0 이하일 경우 decrement 할 때 음수가 되므로 subsequent post 를 기다리는

      상태가 되며 실행을 중단하는 상태가 된다. (Sleeping)

      이때 값이 음수일 때, 음수의 절댓값이 쓰레드들이 Sleeping 한 갯수이다.

(3) sem_post : semaphore의 값을 1 증가시켜주며 만약 쓰레드가 Sleeping 상태일 경우 그 중에 하나의 

      쓰레드를 wake up 해준다.

 

Binary Semaphores (Locks)

 

sem_t m;
sem_init(&m, 0, X); // initialize semaphore to X; what should X be?
sem_wait(&m);
// critical section here
sem_post(&m);

 

초기 X는 1으로 설정하여 semaphore의 value를 1으로 초기화 해주도록 해야 한다.

그리고 sem_wait, sem_post 사이에 critical section을 protection 가능하다.

 

두가지 case를 고려해보도록 한다. (Thread 0, 1 으로 총 2개의 쓰레드 존재)

case 1 :  Thread 0에서만 작업이 이뤄지는 경우 (Non-Context switch)

 

Simple 하게 semaphore의 값이 0으로 decrement 하여 변화 없이(Sleeping x) 작업이 이뤄진다.

 

case 2 :  Thread 0에서 sem_wait이 호출되는 순간 Thread 1으로 넘어가는 경우 (Context switch)

 

 

OS Scheduler가 timer interrupt 를 걸어서 Thread 1으로 넘어간 상태이다. (이때 Semaphore value = 0)

sem_wait() 을 호출하게 되면 이제서야 -1 의 값을 가지게 되는데 Sleeping 상태로 된다.

context switch가 일어나서 Thread 0으로 넘어가고 critical section을 실행하다가 sem_post()를

실행시킴으로써 semaphore 값이 0으로 increment 한다.

즉, Sleeping 중인 Thread 1 을 wake up 하고 또 다시 timer interrupt 가 걸려서 Thread 1으로 넘어가는 

그런 구조임을 알 수 있다.

 

 

Semaphores As Condition Variables

 

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;
}

 

X값은 0으로 초기화 해줘야 한다.

그리고 위 코드에 대한 예상 결과는 다음과 같다.

 

parent: begin
child
parent: end

 

왜 위와 같은 결과가 출력되는지 위 코드에 대한 Flow를 살펴보도록 한다.

먼저 이 코드 또한 2가지 case가 존재한다.

case 1 : 자식 쓰레드를 만들고 sem_wait을 하는 경우 (Non-Context switch)

 

위에서 봤던 case와 동일하게 wait을 호출하면 semaphore의 값이 -1으로 decrement 하면서

부모 쓰레드가 Sleeping 하게 되고 자식 쓰레드에서 post를 호출하여 부모 쓰레드를 깨우는 방식이다.

 

case 2 :  자식 쓰레드를 만들자 마자 자식 쓰레드가 실행되는 경우 (Context switch)

 

위에서 봤던 case와 동일하게 sem_post를 호출하지만 semaphore value가 0 이상이므로 즉, 음수값이 

아니므로 Sleeping 중인 thread가 없어서 semaphore 값만 increment 하게 된다.

그래서 자식 쓰레드가 전부 실행되면 timer interrupt가 걸려서 부모 쓰레드가 실행되며 wait이 호출되면

semphore value가 1이므로 decrement 하게 되면 0이므로 Sleeping 하지 않는다.

 

 

The Producer/Consumer (Bounded-Buffer) Problem

 

Producer: put() interface

   - data를 put 하기 위해서 buffer가 empty 상태가 됨을 기다린다.

Consumer: get() interface

   - data가 사용되기 전에 buffer가 채워질 경우를 기다린다.

 

int buffer[MAX];
int fill = 0;
int use = 0;

void put(int value) {
    buffer[fill] = value;      // line f1
    fill = (fill + 1) % MAX;   // line f2
}

int get() {
    int tmp = buffer[use];     // line g1
    use = (use + 1) % MAX;     // line g2
    return tmp;
}

sem_t empty;
sem_t full;

void *producer(void *arg) {
    int i;
    for(i = 0; i < loops; i++) {
        sem_wait(&empty);   // line P1
        put(i);             // line P2
        sem_post(&full);    // line P3
    }
}

void *consumer(void *arg) {
    int i, tmp = 0;
    while(tmp != -1) {
        sem_wait(&full);    // line C1
        tmp = get();        // line C2
        sem_post(&empty);   // line C3
        printf("%d\n", tmp);
    }
}

int main(int argc, char *argv[]) {
    // ...
    sem_init(&empty, 0, MAX);
    sem_init(&full, 0, 0);
    // ...
}

 

empty semaphore는 MAX 라는 상수로 값을 초기화 하고 full semaphore는 0으로 초기화 한다.

즉, buffer에 data를 담을 수 있는 size를 MAX라고 지정한 것으로 볼 수 있다.

 

Imagine that MAX is greater than 1.

   - 만약 producers가 여러개 있는 상태라면 line f1 에서 race condition이 발생한다.

   - 즉, old data가 overwrite 될 수 있음을 의미한다.

 

We've forgotten here is mutual exclusion.

   - buffer에 data를 채우고 빼는 것으로 put(i), get() 함수를 호출하는 부분이 곧 critical section 이다.

 

mutual exclusion이 보장이 안되는 상태이다.

이를 해결하기 위한 Solution Code를 보도록 한다.

 

 

A Solution: Adding Mutual Exclusion

 

sem_t empty;
sem_t full;
sem_t mutex; // new!

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

void *consumer(void *arg) {
    int i, tmp = 0;
    while(tmp != -1) {
        sem_wait(&mutex);   // line C0 (new)
        sem_wait(&full);    // line C1
        tmp = get();        // line C2
        sem_post(&empty);   // line C3
        sem_post(&mutex);   // line C4 (new)
        printf("%d\n", tmp);
    }
}

int main(int argc, char *argv[]) {
    // ...
    sem_init(&mutex, 0, 1);
    sem_init(&empty, 0, MAX);
    sem_init(&full, 0, 0);
    // ...
}

 

Imagine two thread: one producer and one consumer

   (1) Consumer는 mutex를 획득한다. (이때 mutex의 semaphore 초기값은 1 => 0)

   (2) Consumer는 sem_wait()을 호출하여 full의 값을 1 감소시킨다. 

   (3) Consumer는 Sleeping 상태에 빠지게 되며 CPU를 yield 하게 된다. 

          여기서 문제점 : 여전히 mutex를 잡고 있는 상태이다.

   (4) Producer는 mutex를 획득한다. (이때 mutex의 semaphore 값 0 => -1)

   (5) 그러나 mutex의 값이 -1으로 됨으로써 Sleeping 상태에 빠진다.

         즉, Consumer도 Producer도 Sleeping 중인 상황으로 이를 classic deadlock 이라고 부른다.

 

 

A Working Solution

 

sem_t empty;
sem_t full;
sem_t mutex;

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

void *consumer(void *arg) {
    int i, tmp = 0;
    while(tmp != -1) {
        sem_wait(&full);    // line C1
        sem_wait(&mutex);   // line C1.5 (new)
        tmp = get();        // line C2
        sem_post(&mutex);   // line C2.5 (new)
        sem_post(&empty);   // line C3
        printf("%d\n", tmp);
    }
}

int main(int argc, char *argv[]) {
    // ...
    sem_init(&empty, 0, MAX);
    sem_init(&full, 0, 0);
    sem_init(&mutex, 0, 1);
    // ...
}

 

mutex를 중간으로 삽입해줘야 deadlock, race condition 에 대한 문제를 해결할 수 있다.

 

 

Reader-Writer Locks

 

Imagine a number of concurrent list operations, including inserts and simple lookups.

※ insert :

     - Chane the state of the list.

     - A traditional critical section makes sense.

※ lookup

     - Simply read the data structure.

     - As long as we can guarantee that no insert is on-going, we can allow many lookups

        to proceed concurrently.

 

오직 하나의 writer만이 lock을 잡을 수 있으며 reader는 여러개의 lock을 잡을 수 있다.

그리고 writer가 lock을 잡을 경우 reader는 lock을 잡을 수 없으며,

reader가 lock을 잡을 경우 writer가 lock을 잡을 수 없는 대신에 또 다른 reader가 lock을 잡을 수 있다.

그리고 writer는 lock을 잡기 위해서 모든 reader가 lock을 release 할 때까지 기다려야 한다.

 

typedef struct _rwlock_t {
    sem_t lock;
    sem_t writelock;
    int readers;
} rwlock_t;

void rwlock_init(rwlock_t *rw) {
    rw->readers = 0;
    sem_init(&rw->lock, 0, 1);
    sem_init(&rw->writelock, 0, 1);
}

void rwlock_acquire_readlock(rwlock_t *rw) {
    sem_wait(&rw->lock);
    rw->readers++;
    if(rw->readers == 1)
        sem_wait(&rw->writelock);
    sem_post(&rw->lock);
}

void rwlock_release_readlock(rwlock_t *rw) {
    sem_wait(&rw->lock);
    rw->readers--;
    if(rw->readers == 0)
        sem_post(&rw->writelock);
    sem_post(&rw->lock);
}

void rwlock_acquire_writelock(rwlock_t *rw) {
    sem_wait(&rw->writelock);
}

void rwlock_release_writelock(rwlock_t *rw) {
    sem_post(&rw->writelock);
}

 

The reader-writer locks have fairness problem.

- It would be relatively easy for reader to starve writer.

- How to prevent more readers from entering the lock once a writer is waiting?

 

 

The Dining Philosophers

 

철학자들이 5개의 table에 앉아있다고 상상해보자. (P0, P1, ..., P4)

 

철학자들 사이에 single fork가 놓여있다. (f0, f1,..., f4)

철학자들은 각자 생각하는 시간(time)과 포크(fork)가 필요 없는 시간이 있고 먹는(eat) 시간이 있다.

철학자가 먹기 위해서 2개의 fork를 필요로 한다. (왼쪽, 오른쪽에 놓여진 fork)

즉, fork들에 대한 contention 이 일어난다.

 

Key challenge

- deadlock이 존재하지 않는다.

- philsopher 그 누구도 starvation 이 일어나지 않으며 절대로 eat 하지 못하는 상황이 일어나지 않는다.

- 높은 Concurrency를 보인다.

 

 

Philosopher는 두 개의 fork를 사용한다고 했는데 왼쪽 fork와 오른쪽 fork를 위에서 제공되는

Helper functions의 left(), right() 함수를 이용하여 해결한다.

 

위 코드는 Deadlock을 발생시킨다.

철학자들이 오른쪽 포크를 잡기 전에 전부 왼쪽 포크를 잡게 된다면?
  => 다른 포크(오른쪽 포크)를 기다리며 영원히 갇히게 된다.

 

 

먼저 각 철학자들이 어떻게 동작하는지에 대한 매커니즘을 이해할 필요가 있다.

① 철학자는 고뇌에 빠진다.

② 고뇌에 빠진 철학자는 배가 고파서 포크를 든다.

      이때, 철학자는 왼쪽 포크를 먼저 드는데 다른 철학자가 해당 포크를 들고 있으면 기다린다.

      왼쪽 포크를 들었다면 오른쪽 포크도 든다. (이 또한 다른 철학자가 해당 포크를 들고 있다면 기다림)

③ 양쪽 포크를 들었다면 야무지게 식사한다.

④ 배불리 먹은 철학자는 포크를 내려놓고 다시 고뇌에 빠지기 시작한다. (① 으로 다시 돌아감)

 

철학자들이 동시에 배가 고파서 왼쪽 포크를 들게 된다면? 

 

 

오른쪽 포크를 들으려고 했는데 모든 철학자들이 해당 포크를 들고 있는 상태가 되버린다.

따라서 철학자들은 영원히 왼쪽 포크를 계속 들고 있는 상태로 있다가 굶어(starvation) 죽는다.

즉, 이러한 상태를 deadlock 이라 하는데 어떻게 해결해야 할까?

 

 

A Solution: Breaking The Dependency

 

제목 그대로 5번째에 놓여진 철학자만 다르게 행동하도록 하게 하는 것이다.

1, 2, 3, 4 번째 철학자들은 이전과 동일하게 왼쪽 포크를 들고 오른쪽 포크를 들었다면

5 번째 철학자 유일하게 오른쪽 포크를 들고 왼쪽 포크를 든다.

 

 

즉,  동시에 포크를 들은다고 할 때, 5번째 철학자(P4)는 1번째 철학자(P0)가 먹을때까지 기다리는데,

이때 오른쪽 포크를 들 수 있는 철학자는 4번째 철학자(P3) 이다.

따라서 식사하는 과정은 다음과 같이 될 것 같다.

 

① 4번째 철학자(P3)가 식사하고 포크를 내려놓는다.

② 3번째 철학자(P2)가 식사하고 포크를 내려놓는다.

③ 2번째 철학자(P1)가 식사하고 포크를 내려놓는다.

④ 1번째 철학자(P0)가 식사하고 포크를 내려놓는다.

⑤ 이제서야 5번째 철학자(P4)가 오른쪽 포크를 들 수 있는 상태이며 동시에 왼쪽 포크도 들고

     식사한 후에 포크를 내려놓는다.

 

 

Semaphore using condition variable: Zemaphores

 

typedef struct __Zem_t {
    int value;
    pthread_cond_t cond;
    pthread_mutex_t lock;
} Zem_t;

void Zem_init(Zem_t *s, int value) {
    s->value = value;
    Cond_init(&s->cond);
    Mutex_init(&s->lock);
}

void Zem_wait(Zem_t *s) {
    Mutex_lock(&s->lock);
    while(s->value <= 0)
        Cond_wait(&s->cond, &s->lock);
    s->value--;
    Mutex_unlock(&s->lock);
}

void Zem_post(Zem_t *s) {
    Mutex_lock(&s->lock);
    s->value++;
    Cond_signal(&s->cond);
    Mutex_unlock(&s->lock);
}

 

Zemaphore는 Semaphore의 값이 변하지 않는다는 것을 유지하지 않으며 음수일 경우

대기 스레드 수를 반영한다.
   - 값이 0보다 작으면 안 된다.
   - 이러한 behavior는 구현이 더 쉽고 현재 Linux 구현과 일치한다.

 

---

 

Non-Deadlock Bugs

 

Two major types of non deadlock bugs

(1) Atomicity violation

(2) Order violation

 

(1) 에 대한 예제를 살펴보도록 한다.

여러 메모리에 접근하기를 원하는 Serializability가 위반된 경우를 본다.

 

Thread 1에서 fputs 을 하기도 전에 timer interrupt가 걸려서 Thread 2로 가서 NULL로 초기화 되어

다시 Thread 2로 돌아와 fputs 을 하려고 했는데 NULL 인 경우가 발생한 상태이다.

즉, interrupt가 걸려서 NULL로 초기화 하는 부분이 일어나지 않도록 하기 위해서 어떻게 해야 할까?

 

정답은 lock을 잡도록 하는 것이다.

Thread 1에서 lock을 미리 잡아두면 Thread 2에서 NULL로 초기화하는 부분으로 들어가는 일이 

발생하지 않고 Thread 1이 끝나야 이제서야 NULL 로 초기화 하게 된다.

 

(2) 에 대한 예제를 살펴보도록 한다.

두 메모리 사이에 원하는 순서가 변경되는 경우를 본다.

 

Thread 2는 언뜻 보기에 mThread가 이미 있는 것처럼 mState에 mThread에 대한 State 값을 넣는 것으로

보인다.

즉, Thread1보다 먼저 Thread2가 실행되게 된다면 심각한 오류가 발생할 것으로 보인다.

 

 

정답은 condition variable 을 이용하여 무조건 mThread값이 먼저 초기화하도록 하는 것이다.

global variable인 mtInit을 0으로 설정하여 Thread 2가 먼저 실행된다 하더라도 0일 경우 해당 쓰레드를

wait 시킴으로써 Thread 1에서 정상적으로 mThread를 초기화 할 수 있도록 하는 것이다.

 

 

Deadlock Bugs

 

 

예를 들어서 Thread 1은 L1 lock을 잡고 L2 lock을 잡기 전에 Context switch가 일어나서 Thread 2가

실행된다고 한다면, Thread 2는 L2 lock을 잡고 L1 lock을 잡으려고 했으나 이미 lock이 걸렸으므로 기다린다.

다시 Context switch가 일어나서 Thread 1이 실행되는데 L2 lock을 잡으려고 했으나 이미 lock이 걸렸으므로

기다리는데 결국 무한히 기다리는 상태로 Deadlock 에 걸리고 만다.

 

 

Why Do Dealocks Occur?

 

Reason 1 : In large code bases, complex dependencies arise between components.

Reason 2 : Due to the nature of encapsulation.

   - Hide details of implementations and make software easier to build in a modular way.

   - Such modularity does not mesh well with locking.

 

Locks for both the vector being added to (v1) and the parameter (v2) need to be acquired.

 

 

Conditions for Deadlock

 

deadlock이 발생하는 것을 방지하기 위한 4가지 condition이 존재한다.

 

1. Mutual Exclusion :  쓰레드들이 필요로 하는 자원들의 배타적인 제어권을 요구한다.

2. Hold-and-wait : 쓰레드는 추가 자원들을 기다리는 동안 자신에게 할당된 자워을 보유한다.

3. No preemption : 자원을 보유하고 있는 쓰레드에서 자원을 강제로 제거할 수 없다.

4. Circular wait : 각 쓰레드가 체인의 다음 쓰레드에서 요청하는 자원을 하나 이상 보유하는 순환 쓰레드가 있다.

 

If any of these four conditions are not met, deadlock cannot occur!

 

 

Prevention - Circular Wait

 

lock 획득에 total ordering을 제공한다.

   - 이러한 접근법은 global locking 전략의 조심스러운 설계에 필요로 한다.

 

 

Prevention - Hold-and-wait

 

lock 은 단 한번, atomically 하게 획득 되어야만 한다.

 

This code guarantees that no untimely thread switch can occur in the midst of lock acquisition.

Problem : 

- 루틴 호출 시, 정확히 어떤 lock 을 고정해야 하는지을 알아야 하며 사전에 lock을 확보해야 한다.

- 즉, concurrency를 감소시킨다.

 

 

Prevention - No Preemption

 

많은 lock acquisition은 종종 문제를 일으키는데, 또 다른 lock을 잡고 있는 것을 기다릴 때 일어난다.

trylock()

=> Used to build a deadlock-free, ordering-robust lock acquisition protocol

 

Prevention - No Preemption

 

livelock

- 두 시스템 모두 code sequence를 반복해서 실행하고 있다.
-  따라서, Progress가 되지 않고 있다.
-  Solution : 반복 후, 모든 것을 다시 시도하기 전에 random delay 를 걸어준다.

 

 

Prevention - Mutual Exclusion

 

wait-free

- 강력한 hardware instruction을 사용함

 

 

We now wanted to atomically increment a value by a certain amount

 

 

Repeatedly tries to update the value to the new amount and uses the compare-and-swap to do so.

- lock이 획득되지 않는다.

- deadlock이 발생하지 않는다.

- livelock은 여전히 가능성있다.