[OS] 세마포어

장선규·2023년 9월 18일
OSOSTEPSemaphoresconcurrency병행성세마포어운영체제
0

[OS] OSTEP Study

목록 보기
21/28

세마포어

다양한 범주의 병행성 문제 해결을 위해서는 락과 조건 변수가 모두 필요하다. 이번 장에서는 세마포어(semaphore) 라는 동기화 기법에 대해 알아볼 것이다. 세마포어는 락과 컨디션 변수로 모두 사용할 수 있다.

핵심 질문: 세마포어를 어떻게 사용하는가

  • 락과 컨디션 변수 대신에 세마포어를 사용하는 방법은 무엇인가?
  • 세마포어의 정의는 무엇인가?
  • 이진 세마포어는 무엇인가? 락과 컨디션 변수를 사용하여 세마포어를 만드는 것이 가능한가?
  • 그 반대로 세마포어를 사용하여 락과 조건 변수를 만드는 것이 가능한가?

1. 세마포어: 정의

세마포어: 정수 값을 갖는 객체이며, 공유자원에 제한된 개수의 프로세스 또는 쓰레드만 접근할 수 있도록 하는 객체.

  • sem_wait()와 sem_post() 두 개의 루틴으로 조작할 수 있다.
  • 세마포어 초기화
    #include <semaphore.h>
sem_t s;
sem_init(&s, 0, 1); // 세마포어 변수 s를 1로 초기화
    • 첫번째 인자에는 세마포어 변수가 들어가고, 세번째 인자로 세마포어 변수를 초기화한다.
    • 두번째 인자는 다른 프로세스 간의 동기화 시 사용
  • sem_wait()와 sem_post()
    int sem_wait(sem_t *s) {
    decrement the value of semaphore s by one; // 세마포어 값 1 감소
    if(value of semaphore s is negative)
    	wait; // 세마포어가 음수면 대기
}
int sem_post(sem_t *s) {
    increment the value of semaphore s by one; // 세마포어 값 1 증가
    if (there are one or more threads waiting) 
    	wake one; // 하나 이상의 쓰레드가 대기중이면, 그 중 하나 깨우기
}
    • 이 루틴들은 다수 쓰레드들에 의해 동시에 호출되는 것을 가정한다.
    • sem_wait(): 세마포어의 값이 1 이상이면 즉시 리턴, 아니면 해당 세마포어 값이 1 이상이 될 때까지 호출자를 대기시킨다.
      • 다수의 쓰레드들이 이 함수를 호출할 수 있으므로, 대기큐에는 다수의 쓰레드가 존재할 수 있다.
      • 대기하는 방법에는 회전(spin)과 재우기(sleep)의 두 가지 방식이 있다.
    • sem_post(): 세마포어 값을 증가시키고 대기 중인 쓰레드 중 하나를 깨운다 (대기하지 않는다).
    • 세마포어가 음수라면 값은 현재 대기 중인 쓰레드의 개수와 같다.
    • 일단은 이 두 함수가 원자적으로 실행된다고 가정한다.

2. 이진 세마포어 (락)

이제 세마포어를 사용할 준비가 되었다. 우리가 처음으로 세마포어를 적용할 곳은 이미 친숙한 “락” 이다.

sem_t m;
sem_init(&m , 0 , X); // X로 세마포어를 초기화하기. 이때 X의 값은?
sem_wait(&m);
// 임계 영역 부분은 여기에 배치
sem_post(&m);
  • 핵심은 세마포어 m의 초기값이다. (X로 초기화 되었다)
  • sem_wait()와 sem_post() 의 정의를 되새겨보면 초기값은 1이 되어야 한다는 것을 알 수 있다.
    • 첫 쓰레드 (쓰레드 0)가 sem_wait()를 호출한다. 먼저 세마포어 값을 1 감소시켜 0으로 만든다.
    • 세마포어의 값이 0이므로 리턴하고 진행할 수 있다.
      (쓰레드는 세마포어 값이 음수인 경우에만 대기한다)
    • 쓰레드 0은 이제 임계 영역에 진입한다.
    • 쓰레드 0이 임계 영역 내에 있을 때 다른 쓰레드가 락을 획득하려고 하지 않는다면, 이 쓰레드가 sem_post()를 불렀을 때 세마포어 값이 다시 1로 설정된다.
      (대기 중인 쓰레드가 없기 때문에, 아무도 깨우지 않는다)
  • 다른 쓰레드가 있는 경우
    • 만약 쓰레드 0이 락을 보유한 상태에서 다른 쓰레드(쓰레드 1)가 sem_wait()를 호출하여 임계 영역 진입을 시도하면, 쓰레드 1이 세마포어 값을 -1로 감수시키고 대기에 들어간다.
    • 즉, 다른 쓰레드가 프로세서를 내어주고 스스로 잠자기에 들어간다.
    • 쓰레드 0이 다시 실행되면 sem_post()를 호출하고, 세마포어 값을 0으로 증가시키고, 잠자던 쓰레드 1을 깨운다.
    • 그러면 쓰레드 1이 락을 획득하고, 작업이 끝나면 세마포어의 값을 다시 증가시켜 1이 되도록 한다.

세마포어를 락으로 쓸 수 있다는 것을 알았다. 락은 두 개의 상태(사용 가능, 사용 중)만 존재하므로 이진 세마포어 (binary semaphore) 라고도 불린다.

3. 컨디션 변수로서의 세마포어

어떤 조건이 참이 되기를 기다리기 위해 현재 쓰레드를 멈출 때에도 세마포어는 유용하게 사용될 수 있다.

  • ex) 리스트에서 객체를 삭제하기 위해 리스트에 객체가 추가되기를 대기

즉, 쓰레드들이 어떤 조건(condition)이 만족되기를 대기하기 때문에, 세마포어를 컨디션 변수처럼 사용할 수 있다.

sem_t s;

void *child(void *arg) {
    printf("child\n");
    sem_post(&s); // 시그널 전달: 자식의 동작이 끝남
    return NULL;
}
intmain(int argc , char *argv[]) {
    sem_init(&s, 0, X); // x의 값은 무엇이 되어야할까?
    printf("parent: begin\n");
    pthread_t c;
    Pthread_create(c, NULL, child, NULL);
    sem_wait(&s); // 자식을 여기서 대기
    printf("parent: end\n");
    return 0;
}
  • 이 프로그램을 통해 다음과 같은 결과를 얻고자 한다면...
    parent: begin
 child
 parent: end
    • 부모 프로세스는 자식 프로세스 생성 후 sem_wait()를 호출하여 자식의 종료를 대기한다.
    • 자식은 sem_post()를 호출하여 종료되었음을 알린다.
  • 그렇다면 이때 세마포어의 초기값은? 0이 되어야 한다
    1. 아직 자식 프로세스가 실행을 시작하지 않은 경우(준비 큐에만 들어 있고 실행 중이 아니다)
      • 자식이 sem_post()를 호출하기 전에 부모가 sem_wait()를 호출할 것이다.
      • 부모는 자식이 실행될 때까지 대기해야 하고, 이를 위해서는 wait() 호출 전에 세마포어 값이 0보다 같거나 작아야 한다.
      • 따라서 0이 초기값이 되어야 한다.
    2. 부모 프로세스가 sem_wait()를 호출하기 전에 자식 프로세스의 실행이 종료된 경우
      • 자식이 먼저 sem_post()를 호출하여 세마포어의 값을 0에서 1로 증가시킨다.
      • 부모가 실행할 수 있는 상황이 되면 sem_wait()를 호출한다. 세마포어 값이 1인 것을 발견할 것이다.
      • 부모는 세마포어 값을 0으로 감소시키고 sem_wait() 에서 대기 없이 리턴한다.

4. 생산자/소비자(유한버퍼) 문제

생산자/소비자 문제 (유한버퍼 문제): 공유 자원의 동기화 문제. 생산자가 자원을 생산할 수 없거나(꽉 참) 소비자가 자원을 소비할 수 없을(비어있음) 수 있다.

생산자/소비자 문제도 세마포어로 해결할 수 있다.

첫 번째 시도

empty와 full이라는 두 개의 세마포어를 사용하여, 버퍼 공간이 비었는지 채워졌는지를 표시한다.

  • put/get 루틴

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

void put(int value) {
    buffer[fill] = value; // f1 라인
    fill = (fill + 1) % MAX; // f2 라인
}
int get() {
    int tmp = buffer[use]; // g1 라인
    use = (use + 1) % MAX; // g2 라인
    return tmp;
}

  • 해법

    sem_t empty;
sem_t full;
void *producer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        sem_wait(&empty); 	// P1 라인
        put(i); 			// P2 라인
        sem_post(&full); 	// P3 라인
    }
}
void *consumer(void *arg) {
    int i , tmp = 0;
    while (tmp != −1) {
        sem_wait(&full); 	// C1 라인
        tmp = get(); 		// C2 라인
        sem_post(&empty); 	// C3 라인
        printf("%d\n", tmp);
    }
}
int main(int argc , char *argv[]) {
    // ...
    sem_init(&empty , 0 , MAX); // MAX 버퍼는 비어 있는 상태로 시작
    sem_init(&full , 0 , 0); // ... 그리고 0이 가득 참
    // ...
}
    • 이 예제에서 생산자는 버퍼가 비워져서 데이터를 넣을 수 있기를 기다리고, 마찬가지로 소비자는 데이터를 꺼내기 위해 버퍼가 채워지기를 기다린다.
    • MAX=1, 생산자/소비자 쓰레드가 각각 하나씩 있는 단일 CPU 상황을 가정하자
      • 소비자가 먼저 실행했다고 치면, 소비자 쓰레드가 C1 라인에 도달하여 sem_wait(&full)을 호출한다.
      • full의 값은 0으로 초기화되었기 때문에 해당 명령으로 인해 full의 값은 -1로 감소되고, 소비자는 대기한다.
      • 이후에 생산자 쓰레드가 실행하여 P1 라인에서 sem_wait(&empty) 루틴을 호출한다.
        • empty 변수가 MAX (이 경우에는 1)로 설정되었기 때문에 소비자와 다르게 생산자는 다음 문장을 계속 실행한다.
      • empty 변수는 감소하여 1에서 0이 되고 생산자가 데이터 값을 버퍼의 첫 번째 공간에 넣는다 (P2 라인).
      • 그런 후에 생산자는 P3 라인의 sem_post(&full)를 호출하여 세마포어의 full의 세마포어의 값을 -1에서 0으로 변경하고 소비자 쓰레드를 깨운다.
        (대기 상태에서 준비 상태로 바뀐다)
    • MAX=10, 여러 생산자/소비자 쓰레드가 있는 경우
      • 경쟁조건이 발생한다.
      • 두 개의 생산자 Pa와 Pb가 있는데, 두 쓰레드가 put()을 거의 동시에 호출하였다고 가정하자.
      • Pa가 먼저 실행되어서 버퍼에 첫 공간에 값을 넣기 시작한다.
        (P1 라인에서 full=0이다)
      • Pa 쓰레드가 full 카운터 변수가 1로 변경하기 전에 인터럽트가 걸렸다.
      • 생산자 Pb가 실행되고 f1 라인에서 마찬가지로 버퍼의 첫 번째 공간에 데이터를 삽입한다.
      • Pa가 기록한 이전의 값은 새로운 값으로 대체된다!

해답: 상호 배제의 추가

위의 문제에서는 상호 배제를 고려하지 않았다. 아래의 코드는 상호배제를 추가했지만 잘못된 방법이다.

sem_t empty;
sem_t full;
sem_t mutex;

void *producer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        sem_wait(&mutex); 	// p0 라인 (추가됨)
        sem_wait(&empty); 	// p1 라인
        put(i); 			// p2 라인
        sem_post(&full); 	// p3 라인
        sem_post(&mutex); 	// p4 라인 (추가됨)
    }
}
void *consumer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        sem_wait(&mutex); 	// c0 라인 (추가됨)
        sem_wait(&full); 	// c1 라인
        int tmp = get(); 	// c2 라인
        sem_post(&empty);	// c3 라인
        sem_post(&mutex); 	// c4 라인 (추가됨)
        printf("%d\n", tmp);
    }
}
int main(int argc , char *argv[]) {
    // ...
    sem_init(&empty, 0, MAX); // MAX 버퍼는 비어 있는 상태로 시작
    sem_init(&full, 0, 0); // ... 그리고 0이 가득 참
    sem_init(&mutex, 0, 1); // 락이기 때문에 mutex=1 (추가됨)
    // ...
}
  • put/get 코드에 락을 추가했지만, 교착상태가 발생한다.
  • 생산자와 소비자 쓰레드가 각 하나씩 있다고 하자.
  • 소비자가 먼저 실행이 되었다고 가정하면, mutex(c0 라인) 를 획득하고 full 변수에 대하여 sem_wait()를 호출한다(c1).
    • 아직 데이터가 없기 때문에 소비자는 대기해야 하고 CPU를 양보해야 하지만, 중요한 것은 소비자가 아직도 락을 획득하고 있다.
  • 생산자가 실행되지만, 이 쓰레드는 먼저 mutex 세마포어에 대해서 sem_wait()를 실행한다(p0 라인).
    • 이미 락은 소비자가 획득한 상태이기 때문에 생산자 역시 대기에 들어간다.
  • 소비자는 mutex를 밖고 있으면서 다른 full 시그널을 발생시키기를 대기하고 있다. full 시그널을 발생시켜야 하는 생산자는 mutex에서 대기중이다.
    -> 생산자와 소비자가 서로를 기다리는 전형적인 교착 상태이다!

최종, 제대로 된 해법

이 문제를 해결하기 위해서는 락의 범위 (scope) 를 줄여야 한다.

sem_t empty;
sem_t full;
sem_t mutex;

void *producer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        sem_wait(&empty); 	// p1 라인
        sem_wait(&mutex); 	// p1.5 라인 (여기로 mutex 이동) <-
        put(i); 			// p2 라인
        sem_post(&mutex); 	// p2.5 라인 (... 그리고 여기) <-
        sem_post(&full); 	// p3 라인
    }
}
void *consumer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        sem_wait(&full); 	// c1 라인
        sem_wait(&mutex); 	// c1.5 라인 (여기로 mutex 이동) <-
        int tmp = get(); 	// c2 라인
        sem_post(&mutex); 	// c2.5 라인 (... 그리고 여기) <-
        sem_post(&empty);	// c3 라인
        printf("%d\n", tmp);
    }
}
int main(int argc , char *argv[]) {
    // ...
    sem_init(&empty, 0, MAX); // MAX 버퍼는 비어 있는 상태로 시작
    sem_init(&full, 0, 0); // ... 그리고 0이 가득 참
    sem_init(&mutex, 0, 1); // 락이기 때문에 mutex=1 (추가됨)
    // ...
}
  • 이번에는 mutex를 획득하고 해제하는 코드를 임계 영역 바로 이전과 이후로 이동하였다.
  • full이나 empty와 관련된 코드는 mutex 밖으로 배치하였다.
  • 결과적으로 멀티 쓰레드 프로그램에서 사용 가능한 유한 버퍼를 만들었다.
    (지금은 이해만 하고 나중에 활용)

5. Reader-Writer 락

또 하나의 고전적인 문제가 있다. 좀 더 융통성 있는 락 기법이 필요하다. 다양한 자료 구조를 접근하는 데 여러 종류의 락 기법이 필요하다.

예를 들어 리스트 삽입/검색에 대한 병행 연산이 여러 개 있다고 하자. 삽입 연산이 없다는 보장만 된다면, 다수의 검색 작업을 동시에 수행할 수 있다.

이와 같은 경우를 위해 만들어진 락이 reader-writer 락이다.

  • 간단한 reader-writer 락

    // rw락 구조체
typedef struct _rwlock_t {
sem_t lock; // 이진 세마포어 (기본 락)
sem_t writelock; // 하나의 쓰기 또는 다수의 읽기 락을 위한 락
int readers; // 임계 영역 내에 읽기를 수행중인  reader의 수
} 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); // 읽기용 락이  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); // 마지막으로 읽기용 락이 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);
}
    • 자료구조 갱신 시 (write)
      • 락 획득: rwlock_acquire_writelock()
      • 락 해제: rwlock_release_writelock()
      • rw락 내부적으로 하나의 쓰기 쓰레드만 락을 획득할 수 있도록 한다.
    • 자료구조 검색 시 (read)
      • 락 획득: rwlock_acquire_readlock(), reader 변수 증가
      • 락 해제: rwlock_release_readlock(), reader 변수 감수
      • 중요) 첫 읽기 락 획득 시 쓰기 락을 획득한다.
        • 자료구조를 읽는 도중에 값이 갱신되는 것을 방지한다.
        • 모든 읽기 쓰레드가 끝날 때 까지 쓰리 쓰레드는 대기한다.
        • 쓰기 쓰레드가 불리하다는 공정성 문제가 있다. 쓰기 쓰레드에게 기아 현상이 발생하기 쉽다.
    • 읽기-쓰기 락 기법은 정교하지만 오버헤드가 크다는 단점이 있다.

6. 식사하는 철학자

다익스트라가 제기한 유명한 세마포어 문제이다.

다섯 명의 “철학자”가 식탁 주위를 둘러앉았다. 총 다섯 개의 포크가 철학자와 철학자 사이에 하나씩 놓여 있다. 자신의 왼쪽과 오른쪽에 있는 포크를 들어야 식사를 할 수 있다. 이 포크를 잡기 위한 경쟁과 그에 따른 동기화 문제가 병행 프로그래밍에서 다루려는 식사하는 철학자 문제이다. 여기 각 철학자의 동작을 나타낸 기본 반복문이 있다.

주요 쟁점은 getfork()와 putfork()의 루틴을 작성하되 교착 상태의 발생을 방지해야 하고, 어떤 철학자도 못 먹어서 굶주리면 안되며 병행성이 높아야 한다 (즉,가능한 많은 철학자가 동시에 식사를 할 수 있어야 한다).

  • Pn이 사람, fn이 포크다.
  • 양 옆에 있는 포크를 집는 left, right 함수를 이요하여 getfork/putfork 루틴을 작성해야 한다.
    int left(int p) { return p; }
int right(int p) { return (p + 1) % 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)]);
}
  • 포크가 필요할 때 하나의 "락"을 획득하는 방법
  • 먼저 왼쪽 포크를 잡고, 그 다음에 오른쪽 포크를 잡는다.
  • 그리고 식사가 끝나면 잡은 순서대로 놓는다.
  • 교착상태가 발생한다.
    • 만약 모든 철학자가 자신의 왼쪽 포크를 잡으면, 모든 철학자가 오른쪽 포크를 못잡고 대기한다.

해답: 의존성 제거

가장 간단한 방법은 최소한 하나의 철학자가 다른 순서로 포크를 집도록 하면 된다.

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)]);
    }
}
  • 가장 높은 순번의 철학자 4가 포크를 다른 순서로 획득한다고 가정 (오-왼 순으로 획득)
  • 마지막 철학자가 오른쪽의 포크를 먼저 잡기 때문에 각 철학자가 하나의 포크를 든 채로 다른 포크를 기다리는 대기 상황은 발생하지 않는다.

7. 세마포어 구현

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);
}
  • 위 코드는 세마포어(여기선 제마포어)의 값이 0보다 작아지지 않는다.
    (다익스트라가 정의한 세마포어는 음수 가능)
  • 이 방식이 구현하기 쉽고, 리눅스에 구현된 방식이기도 하다.
profile
장선규
코딩연습
이전 포스트

[OS] 컨디션 변수

다음 포스트

[OS] 병행성 관련 오류

0개의 댓글