inup blog

운영체제(Operating System) - 7. 고전적인 동기화 문제

@inup· May 06, 2025 · 17 min read
운영체제
책

SERIES: 운영체제 (7)

View More (+2)

content

본 포스팅은 Abraham Silberschatz 저 『Operating System Concepts』(9th Edition)의 내용을 개인 학습 목적으로 요약·정리한 글입니다.

7.1 유한 버퍼 문제 (Bound-Buffer Problem)

  • 생산자-소비자 문제(Producer-Consumer Problem)로도 불린다.

  • 각각에 하나의 아이템을 저장할 수 있는 n개의 버퍼로 구성된다.

    img1 daumcdn

    • 생산자의 목적은 소비자를 위해서 버퍼를 가득 채우는 것이 목표이다.
    • 소비자의 목적은 아이템을 소비하여 버퍼를 비우는 것이 목표이다.

공유 데이터 구조

  • mutex (초기값 = 1)

    • 버퍼 공간에 접근하는 동안 다른 프로세스가 접근하지 못하게 상호 배제를 제공
    • 초기값: 1 (mutex = 0 : 접근 불가능, mutex = 1 : 접근 가능함)

  • empty : 비어있는 버퍼의 개수를 의미하는 세마포어 (초기값 = n)

    • empty = 0 : 버퍼가 가득찼다는 의미
    • empty = n : 버퍼가 비어있다는 의미

  • full : 차있는 버퍼의 개수를 의미하는 세마포어 (초기값 = 0)

    • full = 0 : 버퍼가 비어있다는 의미
    • full = n : 버퍼가 가득찼다는 의미
    int n;
semaphore mutex = 1;
sepaphore empty = n;
semaphore full = 0

각 프로세스의 구조

  • 생산자 프로세스 구조

    while(true){
	...
    // produce an item in next producer
    ...
    wait(empty);
    wait(mutex);
    ...
    // add next producer to buffer
    ...
    signal(mutex);
    signal(full);
}

  • 소비자 프로세스 구조

    while(true){
    wait(full);
    wait(mutex);
	...
    // remove an item from buffer to next consumer
    ...
    
    signal(mutex);
    signal(empty);
    ...
    // consume the item in next consumer
    ...
 }

Bound-Buffer Problem의 문제 유형

  • wait(mutex)를 먼저 호출한 다음 wait(empty)(또는 wait(full))를 호출하면,

    • 데드락 발생

    image

Bound-Buffer Problem의 해결 방안

  • 데드락 문제의 해결이 필요하다.

    • 다음 챕터(Chap 8. Deadlocks) 에서 해결 방안을 모색

7.2 독자-저자 문제 (Readers-Writers Problem)

  • 하나의 데이터셋(dataset)이 여러개의 프로세스들이 동시에 수행된다.
  • Readers 프로세스들은 공유 데이터를 읽기만 한다.

  • Writers 프로세스들은 공유 데이터를 읽기 / 쓰기를 수행한다.

    • 예를 들어 데이터베이스는 여러개의 프로세스들에 의해서 공유된다.
    • 어떤 프로세는 SELECT만 수행하는 프로세스가 있을 수 있다.(로그인 등) 이러한 프로세스는 Reader 프로세스로 간주한다.
    • 어떤 프로세스는 UPDATE만 수행하는 프로세스가 있을 수 있다.(비밀번호 변경 등) 이러한 프로세스는 Writer 프로세스로 간주한다.

  • 두개 이상의 프로세스가 접근하는 경우는 다음과 같이 나뉠수 있다.

    • Case 1 : 두개 이상의 Reader 프로세스들이 동시에 공유 데이터에 접근한다면 문제는 발생하지 않을 것이다.
    • Case 2 : 만약 1개의 Writer 프로세스와 또다른 프로세스(Reader 또는 Writer 프로세스)가 동시에 데이터베이스에 접근한다면 데이터 불일치가 발생할 것이다.

공유 데이터 구조

  • read_count

    • 현재 몇 개의 프로세스가 데이터셋을 읽고 있는지 카운트한다.

  • mutex

    • read_count를 갱신할 때 상호 배제를 보장
    • 초기값: 1 (접근 가능함 = 1, 접근 불가능함 = 0)

  • rw_mutex

    • 라이터(writer)를 위한 상호 배제 세마포어
    • 초기값: 1

Reader-Writer Problem의 문제 유형

  • 모든 문제들은 우선순위와 연관되어 있다.

  • 독자가 우선권을 가질 때

    • “Reader가 현재 읽고 있는데, Writer가 기다린다고 해서 Reader를 멈출 필요는 없다”는 요구를 만족시키려 할 때

      • 즉, 기존에 읽기 중인 Reader가 있거나, 다른 Reader가 대기 중일 때는 Writer보다 Reader가 우선권을 갖고 계속 들어오게 허용한다.
    • Reader가 많으면 Writer는 영원한 대기, 즉 저자 기아 상태(Writer starvation)에 빠질 수 있다.

  • 저자가 우선권을 가질 때

    • “Writer가 기다리고 있거나 이미 쓰고 있는 동안에는, 새로운 Reader는 절대 들어오면 안 된다”는 요구를 만족시키려 할 때

      • 즉, Writer의 요청이 감지되는 순간부터, 또는 Writer가 임계 구역에 들어간 순간부터 추가적인 Reader 진입을 차단

    • Writer는 Reader가 끝나기만을 기다렸다가 순식간에 입장 → Writer starvation은 막지만,

      • 반대로 Reader가 계속 몰려들면 일부 Reader가 영원히 대기, 즉 독자 기아 상태(Reader starvation)에 빠질 수 있다.

  • 2가지 변형 모두 기아(Starvation) 현상이 발생할 수 있다.

    image1

Reader-Writer Problem의 해결 방안

Reader-Writer 문제의 “해결 방안”은 한마디로 다음의 세 가지 요소를 조합해서

  1. 현재 읽고 있는 Reader 수를 세는 read_count
  2. read_count 갱신 자체를 보호하는 mutex 세마포어
  3. Writer 전용 상호 배제를 위한 rw_mutex 세마포어

를 이용해

  • 첫 번째 Reader가 들어올 때 rw_mutex를 잠그기(Writer 진입 차단)
  • 마지막 Reader가 나갈 때 rw_mutex를 풀기(Writer 대기 해제)
  • Writer는 항상 rw_mutex만 잡고 읽기/쓰기를 수행

하도록 한다.

  • Reader 프로세스

    c
코드 복사
wait(mutex);             // 1) read_count 보호용 락 획득
    read_count++;
    if (read_count == 1) // 첫 번째 Reader라면
        wait(rw_mutex);  //   ⇒ Writer 진입 차단
signal(mutex);           // 2) read_count 락 해제

// === 임계 구역: 읽기 작업 수행 ===

wait(mutex);             // 3) 다시 락 획득
    read_count--;
    if (read_count == 0)// 마지막 Reader라면
        signal(rw_mutex);//   ⇒ Writer에게 락 반환
signal(mutex);           // 4) 락 해제

  • Writer 프로세스

    c
코드 복사
wait(rw_mutex);   // 1) Writer 전용 락 획득 (Reader들 진입도 차단)
    // === 임계 구역: 쓰기 작업 수행 ===
signal(rw_mutex); // 2) 락 해제

  • mutex로 read_count 변수 업데이트를 안전하게 보호하면서,

    • 동시에 여러 Reader는 mutex만 잠깐 쓰고 바로 풀기 때문에 공유 데이터에는 동시 읽기가 가능하고,
    • Writer는 rw_mutex로만 들어오기 때문에 Reader 전체 또는 다른 Writer 전체 와 완전 배타적(mutual exclusion)이 보장된다.
  • 이 구조가 바로 “첫 번째 Readers–Writers 문제”의 전형적 해결책이며, Java 등의 고수준 언어에서는 이 패턴을 ReentrantReadWriteLock 같은 Reader-Writer Lock 클래스로 추상화해 제공한다.

  • 독자-저자 문제는 데드락 문제가 아니다.

    • 데드락은 서로가 서로에게 락을 넘겨주며 영원히 기다리는 순환 대기(circular wait) 상황
    • 위에서 설명한 Reader/Writer 알고리즘(첫 번째 해결안)은 이런 순환 대기가 발생하지 않도록 설계되어 있다.

7.3 식사하는 철학자들 문제 (Dining-Philosophers Problem)

  • 5명의 철학자들은 생각하기(thinking) 또는 먹기(eating) 중 한 가지 행동을 선택한다.

  • 5명의 철학자들은 한 짝밖에 없는 5개의 젓가락을 공유한다.

    img1 daumcdn1

    • 때때로 철학자들은 배가 고파지면, 자신에게 가장 가까운 두 개의 젓가락을 잡으려고 시도한다.
    • 경우에 따라 한 번에 한 개의 젓가락만 집을 수도 있다.
    • 이미 다른 철학자가 집은 젓가락은 뺏을 수 없다.
    • 식사를 마치면, 젓가락 두 개를 모두 놓고 다시 생각하기 시작한다.

  • 교착상태가 없고 기아현상이 없는 여러개의 프로세스들(철학자들) 사이에서 여러개의 자원을 할당해야 한다.

    • 여기서 각각의 철학자들의 프로세스들은 전부 동일한 성격의 프로세스들이 아닌 네트워크 소켓 프로세스가 될 수 있고 파일 프로세스 일수 있다.
    • 각각의 젓가락의 자원들은 철학자들과 마찬가지로 자원의 성격이 다를 수 있다.

Dining-Philosophers Problem 기본 구현

  • 양 옆 젓가락을 잡고 식사 후 내려놓는다.

    do {
    wait(chopstick[i]);              // 1) 왼쪽 젓가락 집기
    wait(chopstick[(i+1)%5]);        // 2) 오른쪽 젓가락 집기
    // 3) 식사(eat)
    signal(chopstick[i]);            // 4) 왼쪽 젓가락 내려놓기
    signal(chopstick[(i+1)%5]);      // 5) 오른쪽 젓가락 내려놓기
} while (TRUE);

  • 데드락 발생 가능성

    • 모든 철학자가 왼쪽 젓가락만 집은 상태 → 아무도 젓가락 한 쌍을 만들 수 없음

Dining-Philosophers Problem 기본 구현 - 해결 방안

  1. 철학자들의 인원수를 젓가락의 개수보다 1명 적게 배치하기

    • 모든 철학자들이 젓가락을 왼쪽을 집었더라도 하나의 젓가락은 남기 때문에 반드시 1명의 철학자는 밥을 먹고 젓가락을 내려놓을 수 있다.

  2. 젓가락 두 개를 모두 집을 수 있을 때에만 젓가락을 집도록 허용하기

    • ‘집을 수 있는지 확인 → 집기’의 과정이 모두 임계구역 안에서만 허용되어야 한다.

  3. 비대칭적인 해결안을 사용

    • 홀수 번호를 부여받은 철학자들은 왼쪽 젓가락을 집은 다음에 오른쪽 젓가락을 집는다.
    • 짝수 번호를 부여받은 철학자들은 오른쪽 젓가락을 집은 다음에 왼쪽 젓가락을 집는다.
    • 상호 배제 보장으로 인해서 두 철학자가 동시에 젓가락을 집는 것을 허용하지 않기 때문에 이 해결안을 사용할 수 있다.

  4. 해결 방안의 한계점

    • 상호배제와 교착상태를 해결하더라도, 기아(starvation) 현상을 해결할 수 없다.

Dining-Philosophers Problem - 모니터 구현

  • 철학자들은 두 젓가락을 모두 집을 수 있을 때에만 젓가락을 집도록 허용한다.

  • 철학자들의 3가지 상태를 구별한다.

    1. 생각하는 상태(thinking)
    2. 배고픈 상태(hungry)
    3. 먹는 상태(eating)
  • 철학자는 이웃하는 두 젓가락이 eating 상태가 아닌 경우에만 hungry 상태에서 eating 상태로 전환할 수 있다.

  • 모니터를 사용하기 위해서는 조건 변수가 필요하다.

    • 철학자가 배가 고프며 동시에 먹고 있지 못할 때, 조건 변수는 철학자 스스로 대기하는 것을 허용하게 한다.
    • 젓가락은 모니터에 의해서 제어된다 (DiningPhilosopher Monitor)
    • 각각의 철학자는 젓가락을 집을 때 pick()을 호출해야 하고, 젓가락을 내려놓을 때 putdown() 연산을 호출해야 한다.

  • java

    // 모니터 선언
monitor DiningPhilosophers {
    // 철학자 상태 열거형과 대기용 조건 변수 배열
    enum { THINKING, HUNGRY, EATING } state[5];
    condition self[5];

    // 철학자 i가 젓가락을 집으려 할 때 호출
    void pickup(int i) {
        state[i] = HUNGRY;    // 배고픔 표시
        test(i);              // 주변 철학자 상태 검사
        if (state[i] != EATING)
            self[i].wait();  // 아직 먹을 수 없으면 대기
    }

    // 철학자 i가 식사를 마치고 젓가락을 내려놓을 때 호출
    void putdown(int i) {
        state[i] = THINKING;  // 생각 상태로 돌아감
        // 왼쪽, 오른쪽 철학자 기회 확인
        test((i + 4) % 5);    // 왼쪽 이웃 검사
        test((i + 1) % 5);    // 오른쪽 이웃 검사
    }

    // 상태 검사 및 기회 부여
    void test(int i) {
        // 양옆 이웃이 먹고 있지 않고, 자신이 배고프면
        if (state[(i + 4) % 5] != EATING
            && state[i] == HUNGRY
            && state[(i + 1) % 5] != EATING) {
            state[i] = EATING;   // 식사 허용
            self[i].signal();    // 자신을 깨움
        }
    }

    // 초기화: 모든 철학자 THINKING 상태로
    initialization_code() {
        for (int i = 0; i < 5; i++)
            state[i] = THINKING;
    }
}

  • c언어

    #include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>

#define true 1
#define NUM_PHILS 5 // 철학자들의 인원수

// THINKING : 생각중인  상태
// HUNGRY   : 배고픈    상태
// EATING   : 밥을 먹는 상태
enum {THINKING, HUNGRY, EATING} state[NUM_PHILS];

pthread_mutex_t mutex_lock;
pthread_cond_t cond_vars[NUM_PHILS];

void init();
int leftOf(int i);
int rightOf(int i);
void* philosopher(void* param);
void think(int id);
void eat(int id);
void pickup(int id);
void putdown(int id);
void test(int i);

int main(){

    pthread_t tid;
    init();
    for(int i = 0; i < NUM_PHILS; i++){
        pthread_create(&tid, NULL, philosopher, (void*) &i);
    }
    for(int i = 0; i < NUM_PHILS; i++){
        pthread_join(tid, NULL);
    }
    return 0;
}

void init(){
    for(int i = 0; i < NUM_PHILS; i++){
        state[i] = THINKING;
        pthread_cond_init(&cond_vars[i], NULL);
    }
    pthread_mutex_init(&mutex_lock, NULL);
    srand(time(0));
}

int leftOf(int i){
    return (i + NUM_PHILS - 1) % NUM_PHILS;
}

int rightOf(int i){
    return (i + 1) % NUM_PHILS;
}

void* philosopher(void* param){
    int id = *((int *) param);
    while(true){
        think(id);
        pickup(id);
        eat(id);
        putdown(id);
    }
}

void think(int id){
    printf("%d: Now, I'm thinking...\n", id);
    usleep((1 + rand() % 50) * 10000);
}

void eat(int id){
    printf("%d: Now, I'm eating...\n", id);
    usleep((1 + rand() % 50) * 10000);
}

void pickup(int id){
    pthread_mutex_lock(&mutex_lock);

    state[id] = HUNGRY;
    test(id);
    while(state[id] != EATING){
        pthread_cond_wait(&cond_vars[id], &mutex_lock);
    }

    pthread_mutex_unlock(&mutex_lock);
}

void putdown(int id){
    pthread_mutex_lock(&mutex_lock);

    state[id] = THINKING;
    test(leftOf(id));
    test(rightOf(id));

    pthread_mutex_unlock(&mutex_lock);
}

void test(int i){
    // 만약 철학자 i가 배고픈 상태이고 이웃하는 젓가락이 eating 상태가 아니라면
    // 밥을 먹습니다.
    if(state[i] == HUNGRY &&
       state[leftOf(i)] != EATING &&
       state[rightOf(i)] != EATING){
        state[i] = EATING;
        pthread_cond_signal(&cond_vars[i]);
    }
}

  • 해결 방안의 한계점

    • 상호배제와 교착상태를 해결하더라도, 기아(starvation) 현상을 해결할 수 없다.
Previous Post
운영체제(Operating System) - 6. 프로세스 동기화
Next Post
iSH Shell을 이용하여 옵시디언 iOS-Windows 동기화하기
@inup
언제나 감사합니다 👨‍💻