[OS] 31장: Semaphore

31장: Semaphore

Semaphore API

sem_init(세마포어 변수, 0, 초기값)

• 세 번째 매개변수는 음수가 될 수 없음

sem_t s;
sem_init(&s, 0, 1); // 초기값 1

sem_wait(&s)

• sem 값을 하나 감소 시킴
• 감소시켰는데, 결과가 0 이상이면 바로 반환
• 감소시켰는데 음수이면 0될 때까지 대기
• sem 값이 음수일 때, 절대값은 대기 중인 스레드 수와 같음

sem_post(&s)

• 세마포어 값 하나를 증가시킴
• 대기 중인 스레드가 있다면, 하나를 깨움 (큐로 동작)

이진 세마포어: Lock으로 활용하기

sem_t s;
sem_init(&s, 0, 1);

sem_wait(&m);
// 여기에 임계영역 코드 작성
sem_post(&m);

• 0번 스레드가 wait()하고 임계영역 진입
• 1번 스레드가 wait()하고 임계영역 진입하려 했으나, 음수이므로 대기
• 0번 스레드가 post함
• 1번 스레드가 깨어나서 동작하고 post 함

문제

아래 결과 출력되게 구현하기

sem_t s;

void* child(void* arg) {
        printf("child");
        sem_post(&s);
        return NULL;
}

int main(int argc, char* argv[]) {
        sem_init(&s, 0, 0);
        printf("parent: begin");
        pthread_t c;
        pthread_create(&c, NULL, child, NULL);
        sem_wait(&s);
        printf("parent: end");

        return 0;
}

실행 예 2가지가 있는데,

1. 자식 실행 전에 부모가 먼저 sem_wait(&s)를 호출 한 경우

   s 값이 음수 이므로 부모는 대기함,

   자식이 post 해주면 그때 다시 동작

2. 자식이 먼저 실행되어 종료된 경우

   s 값이 처음에 0인데, 자식이 실행되어 “child” 출력함

   이후 post 호출을 하여 s가 1이 됨

   부모가 sem_wait를 하여 세마포어 사용

프로듀서/컨슈머 문제

생산자는 버퍼에 자리가 비기를 기다려 put() 호출
소비자는 버퍼에 데이터가 오기를 기다려 get() 호출

단순 구현의 문제 발생

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

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

int get() {
        int tmp = buffer[use];
        use = (use + 1) % MAX;

        return tmp;
}    

sem_t empty;
sem_t full;

void* producer(void* arg) {
        for (int i=0; i<loop; i++) {
                sem_wait(&empty);
                put(i);
                sem_post(&full);
        }
}

void* consumer(void* arg) {
        int tmp = 0;
        while (tmp != -1) {
                sem_wait(&full);
                tmp = get();
                sem_post(&empty);
                printf("%d", tmp);
        }
}

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

상호배제 Mutual Exclusion 필요

두 개의 생산자가 동시에 Put할 경우,
첫 번째 세팅한 값이 두 번째에 의해 덮어질 수 있음

MAX 값이 2 이상일 때,

다수의 생산자/소비자가 있을 시 버퍼 접근할 때 경쟁조건이 발생함

== Mutaul Exclusion 필요함

상호배제 Mutaul Exclusion 추가

또 문제 발생

sem_t empty;
sem_t full;
sem_t mutex;

void* producer(void* arg) {
        for (int i=0; i<loop; i++) {
                sem_wait(&mutex); // p1
                sem_wait(&empty); // p2
                put(i);           // p3
                sem_post(&full);  // p3
                sem_post(&mutex); // p4
        }
}

void* consumer(void* arg) {
        for (int i=0; i<loop; i++) {
                sem_wait(&mutex); // c1
                sem_wait(&full); // c2
                int tmp = get();  // c3
                sem_post(&empty);  // c3
                sem_post(&mutex); // c4
                printf("%d", tmp);
        }
}

1. 소비자가 먼저 동작함

   sem_wait(&mutex)를 통해 락을 얻고,

   sem_wait(&full)을 통해 임계 영역 접근도 얻으려 했으나,

   버퍼가 비어있으므로 대기상태에 빠짐

2. 생산자가 동작하려는데, sem_wait(&mutex)에서 음수가 됨

   lock의 권한이 아직 소비자에게 있기 때문

3. 둘 다 슬립 상태가 됨

최종 구현

sem_t empty;
sem_t full;
sem_t mutex;

void* producer(void* arg) {
        for (int i=0; i<loop; i++) {
                sem_wait(&empty); // p1
                sem_wait(&mutex); // p2
                put(i);           // p3
                sem_post(&mutex); // p3
                sem_post(&full);  // p4
        }
}

void* consumer(void* arg) {
        for (int i=0; i<loop; i++) {
                sem_wait(&full);  // c1
                sem_wait(&mutex); // c2
                int tmp = get();  // c3
                sem_post(&mutex); // c3
                sem_post(&empty); // c4
                printf("%d", tmp);
        }
}

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

Reader-Writer Locks

병행 삽입/검색 연산

상황

• 삽입
  • 리스트의 상태 변경, 임계 영역 필요
• 검색
  • 리스트 변경 없이 읽기만 수행
  • 삽입 연산이 없는 경우, 제한없이 병행 수행 가능

Writer

• 한 번에 하나씩 락 획득
• Reader나 Writer가 있으면 대기

Reader

• Writer 락 사용 중에는 대기
• Reader를 잡은 애가 있다면,
  다수 진입 가능 (병행수행 ㅇㅋ)

writer는 한 번에 하나씩 락 획득

reader 또는 writer가 락을 사용 중이면 획득하지 못함

문제점

Reader가 한 명이라도 읽고 있으면,

Writer는 접근하지 못 하고 기다림

그러나, Reader들은 계속 들어올 수 있음

⇒ Writer는 접근하지 못 하고 기다림

식사하는 철학자

철학자는 생각하거나 먹음
먹으려면 좌우 양쪽 젓가락을 집어야 함

젓가락 = 공유자원, 상호배제 필요

목표

• Deadlock이 없어야 함
• 굶어 죽는 철학자가 없어야 함
• 병행성을 최대로 유지해야 함

세마포어로 관리하기 → 문제 발생

sem_t forks[5]; // 처음에는 For문 1로 초기화

int left(int p) { return p; }
int right(int p) { 
        return (p + 1) % 5; // 5명
}

void getForks() {
        sem_wait(forks[left(p)]);
        sem_wait(forks[right(p)]);
}

void putForks() {
        sem_post(forks[left(p)]);
        sem_post(forks[right(p)]);
}

왼쪽 포크를 잡고, 오른쪽 포크를 잡음

내려 놓을 때도 왼쪽부터 내려놓음

→ Deadlock 발생

= 5명의 철학자가 동시에 젓가락 잡으면 사이클이 발생함

식사하는 철학자 DeadLock 해결

1. 의존성 제거 ⇒ 한 명의 철학자만 포크 집는 순서를 바꿈

   원형 큐로 되어 있으니 마지막 철학자가 right를 잡게하면 됨

        void getForks() {
            if (p == 4) {
                    sem_wait(forks[right(p)]);
                    sem_wait(forks[left(p)]);
            } else {
                    sem_wait(forks[left(p)]);
                    sem_wait(forks[right(p)]);
            }
    }

2. 동시에 먹을 수 있는 철학자 수 제한 (병행성 제한)

   데드락 발생 시 모두 굶어 죽으니 제한해버림 (병행성 떨어짐)

3. 여분의 포크 제공

제마포어 구현

Lock + 조건 변수로 구현

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) // value가 음수가 되지 않음
                Cond_wait(&s->cond, &s->lock);
        s->value--; // 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);
}

세마포어와 다른점

• 세마포어는 초기값에 음수가 불가능

  제마포어는 가능

• 세마포어는 수행중에 값이 음수가 될 수 있음

  제마포어는 0 아래로 내려가면 wait 시킴