[OS] 컨디션 변수

장선규·2023년 9월 17일
OSOSTEPconcurrencycondition variables병행성컨디션 변수
0

[OS] OSTEP Study

목록 보기
20/28

컨디션 변수

지금까지 락의 개념을 학습하였다. 불행히도 "락"만으로는 병행 프로그램을 제대로 작성할 수 없다.

쓰레드가 계속 진행하기 전에 어떤 조건이 참인지를 검사하는 경우가 많다. 

volatile int done = 0;

void *child(void *arg) {
    printf("child\n");
    done = 1;
    return NULL;
}
int main(int argc , char *argv[]) {
    printf("parent: begin\n");
    pthread_t c;
    Pthread_create(&c, NULL, child, NULL); // 자식 생성
    while (done == 0)
    ; // 회전
    printf("parent: end\n");
    return 0;
}
  • 예를 들어 부모 쓰레드가 자식 쓰레드의 종료를 기다리는 경우
  • 이 방식은 부모 쓰레드가 회전을 하며 CPU를 낭비하므로 비효율적
  • 이 방법 대신 부모 쓰레드가 특정 조건이 참이 될 때까지 잠자면서 기다리는 방법이 더 좋다.

핵심 질문: 조건을 기다리는 법
멀티 쓰레드 프로그램에서는 특정 조건이 참이 되기를 기다리는 것이 유용할 때가 많이 있다. 그렇다면 쓰레드는 어떻게 조건을 기다려야 할까?

1. 정의와 루틴들

컨디션 변수(condition variable): 어떤 실행의 상태(조건)가 원하는 것과 다를 때 조건이 참이 되기를 기다리며 쓰레드가 대대기할 수 있는 큐.

  • 일종의 큐 자료구조이다.

  • 다른 쓰레드가 상태를 변경 -> 대기중인 쓰레드에 시그널을 보내 깨움

  • 사용 방법

    // 컨디션 변수 초기화
pthread_cond_t c = PTHREAD_COND_INITIALIZER;
// wait/signal 연산
pthread_cond_wait(pthread_cond_t *c , pthread_mutex_t *m);
pthread_cond_signal(pthread_cond_t *c);
    • wait(): 락을 해제하고 호출한 쓰레드를 재우는 함수
      • 호출될 때 mutex는 잠겨있다고 가정
      • wait()에서 리턴하기 전에 락을 재획득해야 한다!
      • 만약 락을 재획득 못하면 다시 sleep 상태가 되기 때문이다.
        (경쟁조건 방지 목적)
    • signal(): 조건이 참이 되길 기다리며 잠자고 있던 쓰레드를 깨우는 함수

  • 경쟁조건 방지 예제

    int done = 0;
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t c = PTHREAD_COND_INITIALIZER;

void thr_exit() {
    Pthread_mutex_lock(&m);
    done = 1;
    Pthread_cond_signal(&c);
    Pthread_mutex_unlock(&m);
}
void *child(void *arg) {
    printf("child\n");
    thr_exit();
    return NULL;
}
void thr_join() {
    Pthread_mutex_lock(&m);
    while (done == 0) // if 문을 사용하지 않는다.
        Pthread_cond_wait(&c , &m);
    Pthread_mutex_unlock(&m);
}
int main(int argc , char *argv[]) {
    printf("parent: begin\n");
    pthread_t p;
    Pthread_create(&p , NULL , child , NULL);
    thr_join();
    printf("parent: end\n");
    return 0;
}
    • 경우 1: 부모 쓰레드가 자식 쓰레드를 생성하고, thr_join()을 호출한 후 자식 쓰레드가 끝나길 기다리는 경우
      • 부모가 자식 쓰레드를 생성한다.
      • 부모 쓰레드에서 thr_join()을 실행하여 sleep 상태가 된다.
        (wait()을 호출하고 락을 반납함)
      • 자식 쓰레드에서 thr_exit()을 실행하여 done을 1로 바꾸고 시그널을 보내 잠든 (부모) 쓰레드를 깨운다.
      • 부모 쓰레드가 깨어나 락을 획득한 채로 리턴되고, 최종적으로 락을 해제하고 parent:end 를 출력한다.
    • 경우 2: 부모 쓰레드가 자식 쓰레드를 생성하자 마자 자식 쓰레드가 실행되는 경우
      • 부모가 자식 쓰레드를 생성한다.
      • 생성된 자식 쓰레드가 바로 실행되어 done이 바로 1로 설정되고, 쓰레드를 깨우기 위한 시그널은 보낸다.
      • 자고있는 쓰레드가 없기 때문에 단순히 리턴한다.
      • 이후 부모 쓰레드가 thr_join()을 실행하고, done이 1이므로 대기 없이 리턴한다.
      • 만약 상태변수 done이 없다면 부모 쓰레드가 영원히 잠들게 된다. 부모를 깨워줄 자식 쓰레드도 없고, 자식 쓰레드가 이미 실행되었던 상태인지도 모르기 때문이다.

    참고: 시그널을 보내기 전에 항상 락을 획득하자

    void thr_exit() {
    done = 1;
    Pthread_cond_signal(&c);
}
void thr_join() {
    if (done == 0)
    	Pthread_cond_wait(&c);
}
    • 부모 쓰레드에서 wait()를 수행하기 직전에 인터럽트가 걸렸다고 가정
    • 인터럽트로 자식 쓰레드가 실행되어 done을 1로 바꾸고 시그널을 보낸다.
    • 이후 부모 쓰레드에서 wait()를 수행하지만, 자식 쓰레드는 이미 실행된 상황이라 더이상 부모를 깨워줄 자식이 존재하지 않게 된다.

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

다음으로 살펴볼 동기화 문제는 Dijkstra가 처음 제시한 생산자/소비자(producer/consumer) 문제이다. 유한 버퍼(bounded 버퍼) 문제로도 알려져 있다.

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

  • 생산자 쓰레드는 데이터를 만들어 버퍼에 넣고, 소비자 쓰레드는 데이터를 꺼내어 사용한다.

  • 유한버퍼는 공유 자원이며, 경쟁 조건의 발생을 방지하기 위해 동기화가 필요하다.

  • get/put 함수 정의

    // get/put 함수 정의

int buffer; // 일단 지금은 정수 하나로 정의
int count = 0; // 처음엔 버퍼 비어있음

void put(int value) {
    assert(count == 0); // 비었는지 확인용
    count = 1;
    buffer = value;
}

int get() {
    assert(count == 1); // 찼는지 확인용
    count = 0;
    return buffer;
}
    • 이후 예제에서 반복문으로 버퍼에 값을 넣고 꺼낼 것이다.

  • 생산자/소비자 쓰레드 v1

    // 생산자/소비자 쓰레드 v1

void *producer(void *arg) {
    int i;
    int loops = (int) arg;
    for (i = 0; i < loops; i++) {
    	put(i);
    }
}

void *consumer(void *arg) {
    int i;
    while (1) { // 값을 무한히 추출
        int tmp = get();
        printf("%d\n", tmp);
    }
}
    • 이 코드는 제대로 동작하지 않는다.
    • 락이 없어 공유 자원인 buffer에 대해 경쟁 조건이 발생한다.

불완전한 해답

아래의 예에서 생산자와 소비자가 각각 하나씩 있고, 컨디션 변수 cond와 그것과 연결된 mutex 락을 사용한다.

cond_t cond;
mutex_t mutex;

void *producer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        Pthread_mutex_lock(&mutex);				// p1
        if (count == 1) 						// p2
            Pthread_cond_wait(&cond , &mutex); 	// p3
        put(i); 								// p4
        Pthread_cond_signal(&cond); 			// p5
        Pthread_mutex_unlock(&mutex); 			// p6
    }
}
void *consumer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        Pthread_mutex_lock(&mutex); 			// c1
        if (count == 0) 						// c2
        	Pthread_cond_wait(&cond , &mutex); 	// c3
        int tmp = get(); 						// c4
        Pthread_cond_signal(&cond); 			// c5
        Pthread_mutex_unlock(&mutex); 			// c6
        printf("%d\n", tmp);
    }
}
  • 이번에는 락이 생겼다. 하지만 락의 추가만으로 제대로 동작하지는 않고, 컨디션 변수가 있어야 제대로 동작한다.
  • 1 생산자, 1 소비자인 경우
    • 생산자는 버퍼가 빌때까지 기다린다 (p1~p3)
      소비자도 버퍼가 찰때까지 기다린다 (c1~c3)
    • 위의 코드는 잘 동작한다.
  • 1 생산자, 2 소비자인 경우 (or 여러 소비자인 경우)
    • 소비자 쓰레드: Tc1T_{c1}, Tc2T_{c2}
    • 생산자 쓰레드: TpT_p
    • Tc1T_{c1}가 가장 먼저 실행된다고 가정
    • 실행 과정
      • Tc1T_{c1}가 락을 획득(c1)하고 조건문 검사(c2), 이후 wait()을 호출하여 락을 해제(c3)한다.
      • TpT_p가 실행되어 락을 획득(p1)하고 버퍼가 비었음을 확인(p2)한다.
      • put()으로 넘어가서 버퍼를 채운다(p4).
      • 생산자는 버퍼가 가득 찼다는 시그널을 보낸다(p5).
        • 이때, Tc1T_{c1}이 깨어나 ready queue로 이동한다. 실행할 수 있는 상태이지만, 실행 상태는 아니다.
      • 생산자는 실행을 계속 하고(p6), 루프를 한번 더 돌아 대기 상태로 전이한다(p1~p3).
        (count가 1로 버퍼가 찼기 때문에 대기하는 것)
      • 여기서 문제 발생! 다른 소비자 Tc2T_{c2}가 끼어들어 버퍼 값을 소비한다(c1,2,4,5,6).
      • 이후에 Tc1T_{c1}이 다시 실행되는데, get()을 실행(c4)시키려고 하지만 버퍼가 비어있다...
      • 원인은 Tc1T_{c1}이 깨어나기 전에 유한 버퍼의 상태가 변경되었기 때문이다.
      • 시그널은 상태가 변경되었을 쑤 있다는 힌트에 불과하며, 깨어난 쓰레드가 실제 실행 시점에서 상태가 유지된다는 보장이 없다. (Mesa semantic)

개선된, 하지만 아직도 불완전한: if문 대신 while문

위의 문제는 if 문을 while 문으로 바꾸는 것으로 쉽게 해결이 가능하다.

cond_t cond;
mutex_t mutex;

void *producer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        Pthread_mutex_lock(&mutex); 			// p1
        while (count == 1) 						// p2
            Pthread_cond_wait(&cond , &mutex); 	// p3
        put(i); 								// p4
        Pthread_cond_signal(&cond); 			// p5
        Pthread_mutex_unlock(&mutex); 			// p6
    }
}
void *consumer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        Pthread_mutex_lock(&mutex); 			// c1
        while (count == 0) 						// c2
            Pthread_cond_wait(&cond , &mutex); 	// c3
        int tmp = get(); 						// c4
        Pthread_cond_signal(&cond); 			// c5
        Pthread_mutex_unlock(&mutex); 			// c6
        printf("%d\n", tmp);
    }
}
  • 이번에는 소비자 Tc1T_{c1}이 깨어나서(락을 획득한 상태), 즉시 공유 변수의 상태를 재확인한다(c2).
  • 만약 이 시점에 버퍼가 비어 있다면, 소비자는 대기상태로 돌아간다 (c3).

Mesa semantic의 가장 기본적인 법칙은 언제나 while 문을 사용하는 것이다. 이게 안전하다.

그러나 위의 코드도 문제가 있다. Tc1T_{c1}, Tc2T_{c2}이 둘 다 대기 상태에 있을 때 발생한다.

  • 생산자가 버퍼에 값을 넣고 소비자 쓰레드(Tc1T_{c1}) 하나를 깨웠다고 하자.
  • 생산자는 대기상태가 되고, 소비자 Tc1T_{c1}는 리턴을 받아 깨어나고(c3) 조건을 재확인한다(c2).
  • 버퍼가 차있다는 것을 발견하고 값을 소비한다(c4).
  • 이 소비자는 시그널을 전송(c5)하여 대기중인 쓰레드 중 하나를 깨운다.
    • 어느 쓰레드를 깨울 것인가?
      생산자 TpT_{p} ? 아니면 또다른 소비자 Tc2T_{c2} ?
  • 만약 다른 소비자 Tc2T_{c2}가 깨어난다면 버퍼가 빈 것을 확인하고(c2) 대기 상태로 들어간다(c3).
  • 버퍼에 값을 넣어야 하는 생산자 TpT_{p}는 대기중이며, Tc1T_{c1}도 아까 대기상태가 되었다.
    즉, 모든 쓰레드가 대기상태가 된 것이다.
  • 시그널을 보내는 것은 꼭 필요하지만 대상이 명확해야 한다.
    소비자는 생산자를, 생산자는 소비자를 깨워야만 한다.

단일 버퍼 생산자/소비자 해법

cond_t empty, fill;
mutex_t mutex;

void *producer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        Pthread_mutex_lock(&mutex);
        while (count == 1)
            Pthread_cond_wait(&empty , &mutex);
        put(i);
        Pthread_cond_signal(&fill);
        Pthread_mutex_unlock(&mutex);
    }
}
void *consumer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        Pthread_mutex_lock(&mutex);
        while (count == 0)
            Pthread_cond_wait(&fill , &mutex);
        int tmp = get();
        Pthread_cond_signal(&empty);
        Pthread_mutex_unlock(&mutex);
        printf("%d\n", tmp);
    }
}
  • 두 개의 컨디션 변수를 사용
  • 시스템의 상태가 변경되었을 때 깨워야 하는 쓰레드에게만 시그널을 제대로 전달한다.
  • 생산자 쓰레드는 empty에 대해 대기하고 fill에 대해 시그널을 발생시킨다.
  • 소비자 쓰레드는 fill에 대해 대기하고 empty에 대해 시그널을 발생시킨다.
  • 이로써 생산자는 소비자만을, 소비자는 생산자만을 깨운다.

최종적인 생산자/소비자 해법

이제 제대로 동작하는 생산자/소비자 해법을 얻었지만 아직까지는 보편적인 방법은 아니다. 마지막 변경을 통해 병행성을 증가시키고 더 효율적으로 만들 수 있다.

  1. 버퍼 공간을 추가하여 대기 상태에 들어가기 전에 여러 값들이 생산될 수 있도록 한다.
  2. 여러 개의 값이 대기 상태 전에 소비될 수 있도록 한다.
int buffer[MAX];
int fill = 0;
int use = 0;
int count = 0;

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

int get() {
	int tmp = buffer[use];
    use = (use + 1) % MAX;
    count−−;
    return tmp;
}
  • 버퍼를 배열 구조로 바꾸었고, 이에 따라 put/get 함수도 변경하였다.
// 동작하는 최종 해법
cond_t empty , fill;
mutex_t mutex;

void *producer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        Pthread_mutex_lock(&mutex); // p1
        while (count == MAX) // p2
            Pthread_cond_wait(&empty , &mutex); // p3
        put(i); // p4
        Pthread_cond_signal(&fill); // p5
        Pthread_mutex_unlock(&mutex); // p6
    }
}
void *consumer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        Pthread_mutex_lock(&mutex); // c1
        while (count == 0) // c2
            Pthread_cond_wait(&fill , &mutex); // c3
        int tmp = get(); // c4
        Pthread_cond_signal(&empty); // c5
        Pthread_mutex_unlock(&mutex); // c6
        printf("%d\n", tmp);
    }
}
  • 생산자는 모든 버퍼가 현재 가득 차있다면 대기 상태에 들어간다(p2).
  • 마찬가지로, 소비자도 모든 버퍼가 비어 있다면 대기에 들어간다(c2).

3. 컨디션 변수 사용 시 주의점

// 몇 byte나 힙이 비어 있는가?
int bytesLeft = MAX_HEAP_SIZE;
// 락과 컨디션 변수가 필요함
cond_t c;
mutex_t m;

void *allocate(int size) {
    Pthread_mutex_lock(&m);
    while (bytesLeft < size)
    	Pthread_cond_wait(&c , &m);
    void *ptr = . . . ; // 힙에서 메모리를 할당받음
    bytesLeft −= size;
    Pthread_mutex_unlock(&m);
    return ptr;
}
void free(void *ptr , int size) {
    Pthread_mutex_lock(&m);
    bytesLeft += size;
    Pthread_cond_signal(&c); // 시그널 전달 대상은?
    Pthread_mutex_unlock(&m);
}
  • 메모리 할당 코드를 호출하면 공간이 생길 때까지 기다려야할 수 있다.
    반대로, 쓰레드가 메모리 반납시, 사용 가능한 메모리 공간의 발생을 알리는 시그널을 생성할 수 있다.
  • 하지만 이 코드에는 문제가 있다. 어떤 쓰레드가 (하나 이상의 쓰레드가 대기 중일 수 있으므로) 깨어나야 하는가?
  • 예시
    • 현재 빈 공간이 없이 메모리 꽉 찼다고 가정
    • 쓰레드 Ta: allocate(100) 실행
      쓰레드 Tb: allocate(10) 실행
    • 두 쓰레드 Ta, Tb는 대기 상태에 돌입 (메모리 꽉 참)
    • 이 시점에서 Tc가 free(50) 호출
      -> 무조건 Tb가 깨어나야 하지만, 보장 불가능
  • 해법: pthread_cond_signal() 대신 pthread_cond_broadcast()을 사용하여 대기중인 모든 쓰레드를 깨운다.
  • 단점: 아직 깨어나면 안 되는 여러 쓰레드가 불필요하게 깨어날 수도 있다. (포함조건, covering condition)
  • 메모리 할당 문제의 경우 브로드캐스트를 사용하는 것이 자명한 해법이다.
profile
장선규
코딩연습
이전 포스트

[OS] 락 기반의 병행 자료 구조

다음 포스트

[OS] 세마포어

0개의 댓글