[운영체제] 06 Process Synchronization

gramm·2021년 1월 29일

운영체제

목록 보기

6/14

내용 출처

KOCW 반효경 교수님 <운영체제> 강의

반효경 교수님의 <운영체제> 강의 내용을 기반으로 정리했으며,

이 포스팅의 모든 이미지는 <운영체제> 강의에서 가져왔습니다.

Process Synchronization (프로세스 동기화) = Concurrency Control (병행 제어)

데이터의 접근

데이터가 저장된 위치를 Storage Box, 연산이 되는 위치를 Execution Box라고 하자. Storage Box에서 연산할 데이터를 읽어와서 Execution Box에서 연산을 한 뒤, 연산한 결과의 값을 Storage Box에 돌려준다.

E-box	S-box
CPU	Memory
컴퓨터 내부	디스크
프로세스	그 프로세스의 주소 공간

문제는 하나의 Storage Box를 여러 Execution Box가 공유하는 경우, Race Condition의 가능성이 있다는 것이다. 하나의 Execution Box가 A라는 데이터를 읽어간 사이에, 또 다른 Execution Box가 A라는 데이터를 읽어가면 이러한 문제가 발생할 수 있다. (아래에서 더 자세히 다룸.)

OS에서 race condition이 발생하는 경우

1. Kernel 수행 중 인터럽트 발생 시

count 변수를 CPU로 불러들인 상태에서 인터럽트가 들어왔을 때, 이 작업을 잠시 멈추고 인터럽트 처리 루틴으로 넘어가서 인터럽트 핸들러가 실행된다. 여기서 count 변수에 1을 빼고 다시 커널로 들어간다. 하지만 커널에는 1을 빼기 전의 count 변수값이 저장되어 있으므로, 원래 count값에 1을 더한 값을 count 변수에 저장하게 된다. count-- 계산이 무의미해지는 것이다.

문제 해결 방법 : 변수의 값을 건드리는 동안에는 인터럽트가 들어오더라도 인터럽트 처리 루틴으로 넘기지 않는다. 인터럽트를 disable 상태로 두었다가, 변수에 대한 작업이 끝난 다음에 인터럽트 처리루틴으로 넘긴다.

1. 프로세스가 시스템 콜을 하여 커널 모드로 수행 중인데, 문맥 교환이 일어나는 경우

두 프로세스의 주소 공간 간에는 data sharing이 없다.
그러나 시스템 콜을 하는 동안에는 커널 주소 공간의 데이터에 접근하게 된다.
이 작업 중간에 CPU를 preempt(선점)해가면 race condition이 발생한다.

해결 방법 : 커널 모드에서 수행 중일 때는 할당 시간이 끝나도 CPU를 빼앗지 않는다.

1. 멀티 프로세서에서 shared memory 내의 커널 데이터

이 경우 인터럽트 enable/disable로는 해결되지 않는다.

해결 방법 1 : 한번에 하나의 CPU만이 커널에 들어갈 수 있게 한다.

해결 방법 2 : 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대한 lock/unlock를 하는 방법

프로세스 동기화 문제

공유 데이터(shared data)의 동시 접근(concurrent access)은 데이터의 불일치 문제를 발생시킬 수 있다.

일관성 유지를 위해서는 협력 프로세스 간의 실행 순서를 정해주는 매커니즘이 필요하다.

Race Condition

여러 프로세스들이 동시에 공유 데이터를 접근하는 상황
데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라진다.

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

The Critical-Section Problem

n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우
각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section이 존재한다.
문제 : 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다.

do {
    entry section
    critical section
    exit section
    remainder section
} while (1);

critical section : 공유 데이터에 접근하는 코드
remainder section : 공유 데이터가 아닌 데이터에 접근하는 코드

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

1. Mutual Exclusion (상호 배제)
프로세스 Pi가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안된다.
2. Progress (진행)
아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다.
3. Bounded Waiting (유한 대기)
프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다. (starvation이 생기지 않도록 해야 한다.)
가정
- 모든 프로세스의 수행 속도는 0보다 크다.
- 프로세스들 간의 상대적인 수행 속도는 가정하지 않는다.

Critical-Section 문제를 해결하는 알고리즘

1. Algorithm 1

// Synchronization Variable (동기화 변수)
int turn;
initially turn = 0;
// Pi can enter its critical section if (turn == i)


// Process 0

do {
    while (turn != 0);  // My turn?
    critical section
    turn = 1;           // Now It's your turn
    remainder section
} while (1);

// Process 1

do {
    while (turn != 1);  // My turn?
    critical section
    turn = 0;           // Now It's your turn
    remainder section
} while (1);

문제 : Progress 조건을 만족하지 못한다. turn의 값이 1인 상태에서 프로세스 1이 critical section에 들어가지 않는 경우, 프로세스 0도 critical section에 들어가지 못한다.

2. Algorithm 2

Algorithm 1을 보완한 것이다.

// Synchronization Variable
boolean flag[2];
initially flag[all] = false;  // no one is in Critical Section


// Process i

do {
    flag[i] = true;     // Pretend I am in
    while (flag[j]);    // Is he also in? then wait
    critical section
    flag[i] = false;    // I am out now
    remainder section
} while (1);

문제 : Progress 조건을 만족하지 못한다. 둘 다 while문까지 수행 후 끊임 없이 양보하는 상황이 발생할 수 있다.

3. Algorithm 3 (Peterson’s Algorithm)

Combined synchronization variables of algorithms 1 and 2

// Process i

do {
    flag[i] = true;   // My intention is to enter ....
    turn = j;         // Set to his turn
    while(flag[j] && turn == j);  // wait only if ....
    critical section
    flag[i] = false;
    remainder section
} while (1);

3가지 요구 조건 (mutual exclusion / progress / bounded waiting)을 모두 만족한다.

문제 : Busy Waiting (spin lock)

프로세스 하나가 lock을 걸고 critical section에 들어간 경우, 다른 프로세스는 쓸데없이 while문에서 조건 검사를 반복하면서 CPU와 메모리를 낭비한다.

Synchronization HardWare

하드웨어적으로 하나의 명령만 주어지는 경우 critical section의 문제는 간단하게 해결된다. critical section의 문제가 생겼던 이유는 데이터를 읽고 쓰는 것을 하나의 명령으로 처리할 수 없기 때문이었다. 그런데 만약 하나의 명령으로(atomic하게) 데이터를 읽는 동시에 쓸 수 있다면(test & modify), 문제가 간단하게 해결된다.

참고 링크

Test_and_set(a) : a라는 데이터의 현재값을 읽어내고 이 값을 1로 바꾸어 준다.

// Synchronization Variable
boolean lock = false;

// Process Pi

do {
    while (Test_and_Set(lock));
    critical section
    lock = false;
    remainder section
} while (1);

Semaphores

앞의 방식들을 추상화시킨 것 (일종의 추상 자료형)

Semaphore S

integer variable
(변수의 값이 자원의 개수)
아래의 2가지 atomic 연산에 의해서만 접근 가능하다.

P(S)는 semaphore 값을 획득하는 과정, V(S)는 반납하는 과정이다.
위 연산에서도 busy-waiting의 문제는 발생한다.

[Critical Section of n Processes]

// Synchronization Variable
Semaphore mutex;  // initially 1 : 1개가 CS에 들어갈 수 있다

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

busy-waiting(spin lock)은 효율적이지 못하다.

Block & WakeUp 방식의 구현 (= sleep lock)

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

typedef struct
{
    int value;          // semaphore
    struct process *L;  // process wait queue
} semaphore;

block과 wakeup을 다음과 같이 가정한다.
Block
커널은 block을 호출한 프로세스를 suspend시킨다.
이 프로세스의 PCB를 semaphore에 대한 wait 큐에 넣는다.
WakeUp(P)
block된 프로세스 P를 WakeUp시킨다.
이 프로세스의 PCB를 ready 큐로 옮긴다.

Semaphore 연산이 이제 다음과 같이 정의된다.

// P(S)
S.value--;        // prepare to enter
if (S.value < 0)  // negative, I cannot enter
{
    add this process to S.L;
    block();
}

// V(S)
S.value++;
if (S.value <= 0)
{
    remove a process P from S.L;
    wakeup(P);
}

s.value가 음수라면, 누군가 자원을 기다리고 있음을 의미한다. 따라서 S.L에서 프로세스 하나를 깨워야(wakeup) 한다. 반면 s.value가 양수라면, 자원에 여분이 있어서 이미 누군가 쓰고 있음을 의미한다. 따라서 이 경우에는 프로세스를 깨울 필요가 없다.

[Busy Waiting VS Block/WakeUp]

critical section의 길이가 긴 경우 block/wakeup이 적당하다.
critical section의 길이가 매우 짧은 경우 block/wakeup 오버헤드가 busy-wait 오버헤드보다 더 커질 수 있다.
일반적으로는 block/wakeup 방식이 더 효율적이다.

Two Types of Semaphores

Counting Semaphore
- 도메인이 0 이상인 임의의 정수값
- 주로 resource counting에 사용한다. (자원의 개수가 여러 개일 때)
Binary Semaphore
- 0 또는 1 값만 가질 수 있는 semaphore
- 주로 mutual exclusion (lock/unlock)에 사용한다. (자원의 개수가 하나일 때)

Deadlock and Starvation

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

해결 : 아래와 같이 자원을 획득하는 순서를 하나로 통일한다.

Starvation = Indefinite blocking
프로세스가 suspend된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상

Bounded-Buffer Problem

Bounded-Buffer Problem = Producer-Consumer Problem

producer process (생산자 프로세스)
공유 버퍼에 데이터 하나를 만들어서 집어넣는다.
consumer process (소비자 프로세스)
데이터를 하나씩 꺼내서 쓴다.

문제 1 : 공유 데이터
- 생산자 : 같은 empty 버퍼에 두 생산자 프로세스가 동시에 데이터를 집어넣으면 문제가 발생한다. 그래서 생산자 프로세스는 데이터를 집어넣기 전에, 공유 데이터에 lock를 건었다가, 데이터 입력 및 buffer 조작을 마친 뒤 다시 lock를 푼다. 마지막으로 full 버퍼의 개수 하나를 증가시킨다.
- 소비자 : 같은 full 버퍼에 두 소비자 프로세스가 같이 데이터를 꺼내면 문제가 발생한다. 그래서 소비자 프로세스는 데이터를 꺼내기 전에, 공유 데이터에 lock을 걸었다가, 데이터를 꺼내고 buffer 조작을 한 뒤 lock을 푼다. 마지막으로 empty 버퍼의 개수 하나를 증가시킨다.
문제 2 : 버퍼의 유한성
- 생산자 : 버퍼가 가득 찬 상태에서는 생산자가 도착하더라도 데이터를 집어넣을 empty 버퍼가 없다. 그래서 생산자는 소비자가 와서 데이터를 꺼내갈 때까지 기다려야 한다.
- 소비자 : 버퍼가 완전히 비어있는 상태에서는 소비자가 도착하더라도 데이터를 꺼내 갈 full 버퍼가 없다. 그래서 소비자는 생산자가 와서 데이터를 채울 때까지 기다려야 한다.

[Semaphore가 해야 할 일]

① 두 프로세스가 동시에 공유 버퍼에 접근하지 못하도록 lock을 걸었다가, 접근이 끝나면 lock을 풀어준다.

② 버퍼가 가득 차거나 비었을 때를 대비하여 가용 자원의 수를 세는 counting semaphore의 역할을 한다.

// Synchronization variables
semaphore full = 0, empty = n, mutex = 1;

// Producer

do { ...
    produce an item in x
    ...
    P(empty);
    P(mutex);
    ...
    add x to buffer
    V(mutex);
    V(full);

} while (1);


// Consumer

do {
    P(full);
    P(mutex);
    ...
    remove an item from buffer to y
    ...
    V(mutex);
    V(empty);
    ...
    consume the item in y
    ...
} while (1);

Readers-Writers Problem

읽는 프로세스(Reader process)들과 쓰는 프로세스(writer process)들이 있고, 공유 데이터를 DB라고 칭한다.

한 프로세스가 DB에 write 중일 때 다른 프로세스가 접근하면 안 된다.
read는 동시에 여러 프로세스가 해도 된다.

[해결 방법]

Writer가 DB에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기 중인 Reader들을 다 DB에 접근하게 해준다.
Writer는 대기 중인 Reader가 하나도 없을 때 DB 접근이 허용된다.
일단 Writer가 DB에 접근 중이면 Reader들은 접근이 금지된다.
Writer가 DB에서 빠져나가야만 Reader의 접근이 허용된다.

mutex : 공유 변수 readcount를 접근하는 코드의 mutual exclusion을 보장한다.
db : Reader와 Writer가 공유 DB 자체를 올바르게 접근하게 한다.

// Shared data
int readcount = 0;
DB 자체;

// Synchronization variables
semaphore mutex = 1, db = 1;

// Writer

P(db);
...
writing DB is performed
...
V(db);


// Reader

P(mutex);
readcount++;
if (readcount == 1)  P(db);  // block writer
V(mutex);
...
reading DB is performed
...
P(mutex);
readcount--;
if (readcount == 0)  V(db);  // enable writer
V(mutex);

[문제점]

starvation이 발생 가능하다. Writer 프로세스는 Reader 프로세스가 모두 빠져나갈 때까지 기다려야 한다.

[해결 방법]

Reader 프로세스가 일정 수준 이상 계속되면 접근을 제한하고 Writer 프로세스에게 우선권을 준다.

Dining-Philosophers Problem

설명 : 철학자가 하는 일은 2가지다. 하나는 밥을 먹는 것, 다른 하나는 생각하는 것이다. 철학자가 밥을 먹기 위해서는 자기 양쪽에 있는 젓가락을 사용해야 한다.

// Synchronization variables
semaphore chopstick[5];  // initially all values are 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의 가능성 (ex. 모두가 왼쪽 젓가락을 잡은 경우, 어떤 철학자도 오른쪽 젓가락을 잡을 수 없다.)

[해결 방안]

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

[젓가락을 2개 모두 잡을 수 있을 때에만 젓가락을 집게 한 코드]

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

// Philosopher i

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

void test(int i) {
    /* 1) 왼쪽 철학자도 밥을 먹고 있지 않고,
       2) 오른쪽 철학자도 밥을 먹고 있지 않고,
       3) 내가 지금 배고픈 상태라면 */
    if ( (state[(i + 4) % 5] != eating) && 
         (state[i] == hungry) && 
         (state[(i + 1) % 5] != eating) ) {
        state[i] = eating;
        V(self[i]);
    }
}

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

void putdown(int i) {
    P(mutex);
    state[i] = thinking;
    // 왼쪽 철학자가 나 때문에 밥을 못 먹었다면 먹을 수 있게 해준다
    test((i + 4) % 5);
    // 오른쪽 철학자가 나 때문에 밥을 못 먹었다면 먹을 수 있게 해준다
    test((i + 1) % 5);
    V(mutex);
}

주의) 위 코드는 monitor로 구현한 코드를 semaphore로 바꾼 것이다. 그래서 semaphore의 철학에 맞는 코드는 아니다.

Monitor

Semaphore의 문제점
- 코딩하기 힘들다.
- 정확성의 입증이 어렵다.
- 자발적 협력이 필요하다.
- 한번의 실수가 모든 시스템에 치명적 영향을 끼친다.

Monitor (모니터) : 동시 수행중인 프로세스 사이에서 추상 자료형의 안전한 공유를 보장하기 위한 high-level synchronization construct

monitor monitor-name
{
    shared variable declarations
    // 공유 데이터에 접근하기 위한 함수들
    procedure body P1(...){
    ...
    }
    procedure body P2(...){
    ...
    }
    procedure body Pn(...){
    ...
    }
    {
        initialization code
    }
}

Monitor의 편리함 : Semaphore는 동시 접근을 막기 위해서 항상 P 연산으로 lock을 걸었다가 풀어주는 작업을 프로그래머가 해야 한다. 반면 Monitor는 동시 접근을 허용하지 않기 때문에, 프로그래밍 언어 차원에서 동기 접근의 문제를 자동으로 해결해준다. 따라서 프로그래머가 따로 lock을 걸 필요가 없다.

Monitor 안에서 어떤 코드를 실행하다가, 어떠한 조건을 만족하지 못해 오래 기다려야 할 때 그 프로세스를 잠들게 한다. 이때 어떤 조건을 충족하지 못했는가를 condition variable로 나타낸다. 이때 condition variable은 특정 값을 가지는 변수가 아니라, 프로세스를 잠들게 하고 줄세우게 하기 위한 변수다.

condition variable은 wait, signal 연산에 의해서만 접근 가능하다. wait 연산은 조건을 만족하지 못할 때 잠들게 하는 연산이고, signal 연산은 잠들어 있는 프로세스를 깨우는 연산이다.

x.wait();
- x.wait()을 invoke한 프로세스는 다른 프로세스가 x.signal()을 invoke하기 전까지 suspend된다.
x.signal();
- x.signal()은 정확하게 하나의 suspend된 프로세스를 resume한다. suspend된 프로세스가 없으면 아무 일도 일어나지 않는다.

Monitor 버전의 Bounded-Buffer Problem 구현

monitor bounded_buffer
{
    int buffer[N];
    condition full, empty;
    /* condition var.은 값을 가지지 않고 자신의 큐에 프로세스를
       매달아서 sleep시키거나 큐에서 프로세스를 깨우는 역할만 한다 */

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

    void consume(int *x)
    {
        if there is no full buffer
        full.wait();
        remove an item from buffer and store it to *x
        empty.signal();
    }
}

full : 내용이 들어있는 버퍼를 기다리면서 잠드는 줄
empty : 내용이 빈 버퍼를 기다리면서 잠드는 줄

Monitor 버전의 Dining Philosophers Problem 구현

monitor dining_philosopher
{
    enum {thinking, hungry, eating} state[5];
    condition self[5] = 0;
    
    void test(int i) {
        if ( (state[(i + 4) % 5] != eating && 
              state[i] == hungry && 
              state[(i + 1) % 5] != eating) ) {
            state[i] = eating;
            self[i].signal();  // wake up Pi
        }
    }

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

    void putdown(int i) {
        state[i] = thinking;
        // test left and right neighbors
        test((i + 4) % 5);
        test((i + 1) % 5);
    }
    
    void init() {
        for (int i = 0; i < 5; i++)
            state[i] = thinking;
    }
}

Each Philosopher:
{
    pickup(i);
    eat();
    putdown(i);
    think();
} while (1);