05. Process Synchronization

Race Condition

Race Condition

Race Condition

• 여러 데이터들이 동시에 공유 데이터를 접근하는 상황
• Storage Box (memory, address space) 를 공유하는 Execution Box (CPU Process)가 여러 개 있는 경우 Race Condition이 발생할 수 있다.

 

OS에서 Race Condition이 발생하는 경우

1. kernel 모드 수행 중 인터럽트 발생 시

2. Process가 system call을 하여 kernel 모드로 수행중인데 context switch가 일어나는 경우

• 두 프로세스의 address space간에는 데이터 공유가 없으나 system call을 하는 동안에는 kernel address space의 데이터를 공유하기 때문에 race condition이 발생한다.
• 커널 모드에서 수행 중일 때는 CPU를 preempt하지 않도록 interrupt enable/disable을 사용하거나 커널 모드에서 사용자 모드로 돌아갈 때 preempt할 수 있도록 처리해서 해결

3. Multiprocessor에서 공유 메모리 내의 kernel data

• Multiprocessor의 경우에는 interrupt enable/disable로 해결되지 않음
• 한번에 하나의 CPU만이 커널에 들어갈 수 있게 하는 방법
• 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대한 lock / unlock을 하는 방법

---

Process Synchronization

Process Synchronization

• 공유 데이터의 동시 접근은 데이터 불일치 문제 (inconsistency)를 발생시킬 수 있다.
• 데이터의 일관성 유지를 위해서는 협력 프로세스 간의 실행 순서를 정해주는 매커니즘이 필요하다.

👉 race condition을 막기 위해서 concurrent process는 동기화되어야 한다.

 

Critical-Section Problem

Critical-Section Problem

• n개의 프로세스가 공유 데이터를 동시에 사용하기 원하는 경우, 각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section이 존재

👉 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다.

 

프로그램적 해결법

프로그램적 해결법의 충족 조건

• Mutual Exclusion: 프로세스 P가 critical section을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안된다.
• Progress: 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 들어가게 해주어야 한다.
• Bounded Waiting: 프로세스가 기다리는 시간이 무한이 되지 않도록 해야 한다.

👉 프로세스들은 수행의 동기화를 위해 몇몇 변수를 공유할 수 있다. -> synchronization variable

 

Algorithm 1

• Synchronization variable: int turn Pi can enter its critical section if turn == i

Process P0

do {
    while (turn != 0)
    critical section
    turn = 1
    remainder section
} while (1)

• mutual exclusion O, progress X
• 과잉 양보: 반드시 한 번씩 교대로 들어가야 함 (swap-turn), 특정 프로세스가 더 빈번히 critical section에 들어가야 하는 경우 문제 발생

Algorithm 2

• Synchronization variable: boolean flag[2] initially all false, Pi ready to enter its critical section if flag[i] == true

Process Pi

do {
    flag[i] = true; /* 이 행 이후에 다음행을 실행하기 전에 context switch가 발생한다면 */
    while (flag[j]);
    critical section
    flag[i] = false
    remainder section
} while (1);

• mutual exclusion O, progress X
• 동시에 flag[0] = flag[1] = true 되면 끊임 없이 양보하는 상황 발생 가능

Algorithm 3 (Peterson's Algorithm)

• Synchronization variable: combine algo1 + algo2

Process Pi

do {
    flag[i] = true;
    turn = j;
    while (flag[j] && turn == j);
    critical section
    flag[i] = false;
    remainder section
} while (1);

• meet all three requirements but Busy Waiting: 계속 CPU와 memory를 사용하며 기다려야 한다 (while)

Synchronization Hardware

• 하드웨어적으로 Test & modify를 atomic하게 수행할 수 있도록 지원하는 경우 앞의 문제는 간단히 해결

---

Semaphore

Semaphore S

• integer variable
• 아래의 두 가지 atomic 연산에 의해서만 접근 가능

P(S)

while (S <= 0) do no-op; // wait
S--;

V(S)

S++;

 

Busy - Wait

• Synchronization variable: semaphore mutex

Process Pi

do {
    P(mutex);
    critical section
    V(mutex);
    remainder section
} while (1);

• Busy-Wait는 효율적이지 못함

 

Block / Wakeup

Semaphore를 다음과 같이 정의한다.

typedef struct
{
    int value; // semaphore
    struct process *L; // process wait queue = 자원의 여분이 없어 기다리고 있는 프로세스 큐
}

• block: 커널은 block을 호출한 프로세스를 suspend시키고 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣는다.
• wakeup(P): block된 프로세스 P를 깨워서 이 프로세스의 PCB를 ready queue로 옮긴다.

P(S)

S.value--;
if (S.value < 0)
{
    add this process to S.L;
    block();
}

V(S)

S.value++;
if (S.value <= 0) { // S.L에 PCB가 대기하고 있는 경우
    remove a process P from S.L;
    wakeup(P);
}

• Critical section의 길이가 긴 경우 Block/Wakeup이 더 효율적
• Critical section의 길이가 매우 짧은 경우 Block/Wakeup 방식의 오버헤드가 Busy-Wait보다 커질 수 있다.
• 일반적으로는 Block / Wakeup 방식이 더 효율적

Two Types of Semaphores

• Counting semaphore: 도메인이 0 이상인 임의의 정수값, 주로 resource counting에 사용
• Binary semaphore (=mutex): 0 또는 1 값만 가질 수 있음, 주로 mutual exclusion (lock/unlock)에 사용

 

Deadlock and Starvation

Deadlock

• 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 이벤트를 무한히 기다리는 현상

Starvation

• Infinite blocking: 프로세스가 semaphore queue에서 빠져나가지 못하는 현상

---

Classical Problems of Synchronization

Bounded-Buffer Problem (Producer-Consumer Problem)

• Producer: 데이터를 만들어 버퍼에 삽입하는 프로세스 <-> Consumer: 버퍼에서 데이터를 꺼내는 프로세스
• 공유 데이터에 접근할 때 interrupt가 발생하면 문제 발생

Solution

• semaphore full = 0, empty = n (size of buffer), mutex = 1;

Producer

do (
    P(empty);
    P(mutex);
    add x to buffer
    V(mutx);
    V(full);
} while (1);

Consumer

do {
    P(full)
    P(mutex);
    remove item from buffer to y
    V(mutex)
    V(empty)
} while (1);

 

Readers-Writers Problem

• 한 프로세스가 DB에 접근해서 write 중일 때 다른 프로세스가 접근하면 안된다.
  • read 작업은 동시에 여러 프로세스가 해도 괜찮다.

Solution

• Writer가 DB에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기중인 Reader들이 DB에 접근 가능
• Writer는 대기 중인 Reader가 하나도 없을 때 DB 접근 허용
• Writer가 DB에 접근 중이면 Reader는 접근 금지

• Shared data: int readcount = 0 (공유데이터를 읽고 있는 process 갯수)
• semaphore mutex = 1, db = 1;

Writer

P(db);
writing DB
V(db);

Reader

P(mutex);
readcount++;
if (readcount == 1) P(db) /* block writer */
V(mutex);

reading DB

P(mutex);
readcount--;
if (readcount == 0): V(db);
V(mutex);

 

👉 Writer에게 starvation 발생 가능

 

Dining-Philosophers Problem

• 여러 프로세스에게 제한된 리소스를 할당하는 상황에서 발생할 수 있는 문제

 

Solution 1

• semaphore chopstick[5]; initially all values = 1

Philosopher i

do {
    P(chopstick[i]) /* 왼쪽 젓가락 */
    P(chopstick[(i+1) % 5]); /* 오른쪽 젓가락 */
    eat();
    V(chopstick[i]);
    V(chopstick[(i+1) % 5]);
    think();
} while (1);

👉 모든 철학자가 동시에 왼쪽 젓가락을 집어버린 경우 -> Deadlock 발생

 

해결 방안

1. 4명의 철학자만 테이블에 동시에 앉을 수 있도록 한다.
2. 젓가락을 두 개 모두 집을 때에만 젓가락을 집을 수 있게 한다.
3. 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록 한다.

2번 해결방안

• enum {thinking, hungry, eating} state[5];
• semaphore self[5] = 0; semaphore mutex = 1;

void putdown(int i) {
    P(mutex)
    state[i] = thinking;
    test((i+4) % 5);
    test((i+1) % 5);
    V(mutex)
}

void pickup(int i) {
    P(mutex)
    state[i] = hungry;
    test(i);
    V(mutex)
}

void test(int i) {
    /* 젓가락 두 개를 모두 집을 수 있는 지 확인 */
    if (state[(i+4)%5] != eating && state[i] == hungry && state[(i+1)%5] != eating) {
        state[i] = eating;
        V(self[i]);
    }
}

Philosopher i

do {
    picku(i);
    eat();
    putdown();
    think();
} while (1);

---

Monitor

Monitor

Semaphore의 문제점

• 코딩이 어렵고 정확성의 입증이 어려움
• 자발적 협력(voluntary cooperation)이 필요하다 -> 프로세스 간 협조 필요
• 한 번의 실수가 모든 시스템에 치명적 영향

Monitor

• 동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization construct
• OOP

monitor monitor-name
{
    shared variable declarations
    procedure body P1 (...) {}
    procedure body P2 (...) {}
    procedure body Pn (...) {}
    {
        initialization code
    }
}

• 모니터 내에서는 한 번에 하나의 프로세스만이 활동 가능
• 프로그래머가 동기화 제약 조건 (semaphore)을 명시적으로 코딩할 필요 없이 객체 자체가 보장함
• 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 condition variable 사용: condition x, y; (x, y: 객체)
• condition variable은 wait 와 signal 연산에 의해서만 접근 가능
  • x.wait(): x.wait()를 invoke한 프로세스는 다른 프로세스가 x.signal()을 invoke하기 전까지 suspend된다. 연산 전에 자원이 가용상태인지 체크하고 가용상태가 아닌 경우에 wait연산을 호출한다.
  • x.signal(): 정확하게 하나의 suspend된 프로세스를 resume한다. suspend된 프로세스가 없으면 아무 일도 일어나지 않는다.

 

Monitor를 활용한 솔루션

Bounded-Buffer Problem

monitor bounded_buffer {
    int buffer[N];
    condition full, empty; /* 데이터 위치를 가리키는 포인터 */
    /* condition variable은 값을 가지지 않고 자신의 큐에 프로세스를 추가해서 sleep 시키거나 큐에서 프로세스를 꺠우는 역할만 담당 */

    void produce (int x)
    {
        if there is no empty buffer: empty.wait();
        add x to an empty buffer
        full.signal()
    }
}

 

 

Dining Philosophers Example

monitor dining_philosopher
{
    enum {thinking, hungry, eating} state[5];
    condition self[5];

    void pickup (int i) {
        state[i] = hungry;
        test(i);
        if (state[i] != eating) {
            self[i].wait();
        }
    }

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

    void init() {
        for (int i=0;i<5;i++) {
            state[i] = thinking;
        }
    }
}

Philosopher:

{
    pickup(i);
    eat();
    putdown(i);
    think();
}