6장 Process Synchronization

 

reference: kocw의 반효경 교수님 강의와 권진욱 교수님 강의(대학 정규 수업)
수업을 듣고나서 강의 교재를 타이핑하고 필기한 부분을 추가적으로 정리하였습니다.
웹뷰에서 toc를 제공합니다.
github의 md 파일로 보는 게 편하시다면, 여기로 이동해주시면 됩니다.

---

1 Race Condition란?

컴퓨터에서 연산을 할 때는 항상 데이터를 읽어와서 연산하고, 그 결과를 다시 어딘가 저장해두도록 되어있다.

race condition이란 하나의 공유 data에 여럿이 접근하려고 할 때, 즉 연산할 수 있는 주체가 여러 개일 때 발생하는 문제를 말한다.

Storage-box를 공유하는 E-box가 여럿 있는 경우, race condition의 가능성이 있다.

Storage-box : Execution-box의 관계는

메모리 : CPU(multiprocessor system),

Address Space : Process 에서 성립할 수 있다.

2 언제 race condition이 발생해?

(2-0. 공통적으로...)

Q. 프로세스들 간에는 거의, 일반적으로 주소 공간을 공유하지 않는다. 그렇다면 언제 race condition 문제가 발생할까?

A. 공통적으로 운영체제에 들어가서 작업을 처리할 때 발생한다. 운영체제에서 작업을 하면 일종의 공유 데이터를 갖게 되기 때문이다.

조금 더 자세히 살펴보겠다.

2-1. kernal 수행 중 interrupt 발생 시

커널(OS) 모드에서 수행 중(running)인데 더 긴급한, 중요한 interrupt가 발생하여 interrupt 처리 루틴이 수행하도록 cpu를 넘길 때이다.

양쪽 다 커널 코드이므로 kernal address space를 공유한다.

위 사진의 경우, count 감소 전에 register에 count 값을 읽어들였기에 감소 연산은 반영되지 않을 것이다.

 

Q. 어떻게 해결할 수 있을까?

A. count 변수를 건드리기 전에 interrupt disable 시켜둔다 (= 변수 건드리는 도중에는 interrupt를 받지 않겠다.) 일반적인 시스템에서는 불과 instruction 한 두개 더 처리하는 동안에 문제가 생길만큼 긴급한 일은 발생하지 않는다.

2-2. Process 가 system call을 하여 kernal mode 로 수행 중인데 context switch가 일어나는 경우

프로세스 A와 B 는 각각의 주소 곤강을 사용하기에 data sharing이 없다. 하지만 system call을 하는 동안에는 kernal address space의 data를 access하게 된다. 즉 데이터를 공유하게 된다. 이 작업 중간에 cpu를 빼앗기게 되면 race condition이 발생한다.

더 자세히 그림을 설명하자면, 프로세스 A의 할당 시간이 끝나 B에게 넘어가면서 context switch가 발생한다. 현재 문맥을 저장하게 되는데, 이 때 count의 값을 이미 cpu에서 register로 읽어들였다. 이후 프로세스 B에서 count++ 연산을 하지만, 다시 A로 문맥 교환이 일어날 때 B 작업 이전의 count 값이 register에 저장되어 있고 이 값으로 이어서 ++의 연산을 한다. 그러므로 B의 작업은 적용이 되지 않는다. 2번이 아닌 1번만 count 값이 증가한다.

 

Q. 어떻게 해결할 수 있을까?

A. 커널 모드에서 수행 중일 때는 CPU를 빼앗지 못하도록 한다.

2-3. Multiprocessor에서 shared memory 내의 kernal data

Q. 어떻게 해결할 수 있을까?

해결 방법 1. 한번에하나의 cpu만이 커널에 들어갈 수 있게 한다. 가장 간단한 방법이지만 굉장히 큰 overhead를 발생시킨다.

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

3 동기화 문제의 SOL: Algorithm

3-0. 프로그램적 해결법의 충족 조건

가정: 모든 프로세스의 수행 속도는 0보다 크다, 프로세스들 간의 상대적인 수행 속도는 가정하지 않는다.

• Mutual Exclusion(상호 배제) 프로세스 Pi가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안 된다.
• Progress(진행) 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다.
• Bounded Waiting(유한 대기) 프로세스가 cricical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다. 이 말은 starvation은 막아야 한다 란 뜻인데, 여럿이 critical section에 들어가고 싶어서 경합이 일어난 상태에서 설명하는 말이다.

🔎critical section: 각 프로세스의 code segment 중 공유 데이터를 접근하는 코드

3-1. 최초의 시도

아래의 코드는 프로세스들의 일반적인 구조로, 프로세스들은 수행의 동기화를 위해 몇몇 변수를 공유할 수 있다 → synchronization variable

do {
    entry section
    critical section // 앞 뒤로 cs 접근 도중에 끊기지 않도록 조치를 취함.
    exit section
    remainder section
} while (1);

3-2. Algorithm 1

• Synchronization variable
  • int turn;
  • initially turn = 0; => Pi can enter its critical

do {
    while (turn != 0); /* My turn? */
    critical section // 내 차례면 공유 코드 수행
    turn = 1:    /* Now it’s your turn 상대방 차례로 바꿈 */
    remainder section
} while (1);
// 내 차례면 공유 코드 수행
// 상대방 차례로 바꿈

Satisfies mutual exclusion, but not progress

즉, 과잉보호: 반드시 한번씩 교대로 들어가야만 함(swap-turn) 상대방이 turn을 내 값으로 바꿔줘야만 내가 들어갈 수 있음

 

Q. 특정 프로세스가 더 빈번히 cs에 들어가야 한다면?

A. 차례를 돌아가며 주는 알고리즘이기에 더 자주 cs에 들어가는 프로세스는 상대방이 cs를 하지 않으면 진행이 되지 않는다.

3-3. Algorithm 2

• Synchronization variable
  • boolean flag[2]; initially flag [모두] = false; //no one is in CS
  • if (flag [i] == true): "Pi ready to enter its critical section"

do {
    flag[i] = true;    /* Pretend I am in */
    while (flag[j]);   /* ts he also in? then wait, 상대방 깃발이 내려가면 */ 
    critical section // 나 수행
    flag [i] = false;   /* I am out now, 나올 때 깃발 내림 */
    remainder section
) while (1);

// 나 수행
// 나올 때 내 깃발 내림(= 나 필요없어)

내(i)가 깃발만 들고(while 문 이전까지 수행하고) CPU를 빼앗김

상대방이 CPU를 얻어 상대방(j)도 깃발을 들고 다시 CPU를 빼앗음.

나(i)는 상대방(j)을 확인하는데 깃발이 들려있음

→ 둘 다 2행까지 수행 후 끊임없이 양보하는 상황이 발생할 수 있다.

Satisfies mutual exclusion, but not progress requirement.

3-4. Algorithm 3

Algorithm 3 (Peterson's Algorithm)

do {
    flag[i] = true; /* My intention is to enter .... - 의사 표현 */
    turn = j; /* Set to his(상대방) turn */
    while (flag[j] && turn==j); /* 기다려 only if ...*/
    critical section // 상대방이 깃발을 들지 않았거나 들었지만 내 turn인 경우 수행됨
    flag[i] = false; // 나 이제 더 안써
    remainder section
} while (1);

Meets all three requirements solves the critical section problem for two processes.

but Busy Waiting! (=spin lock, 계속 CPU와 memory를 쓰면서(자원낭비) wait)

busy waiting은 뒤에서 더 자세히 설명

4 동기화 문제의 SOL: Semaphores

4-0. Synchronization Hardware

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

* atomic하다: 중간에 cpu를 빼앗기거나 쪼개질 수 없고, 읽어가는 것과 data를 바꿔 저장하는 것을 한꺼번에 반드시 실행함

Synchronization variable:
    boolean lock = false; // 아직 아무도 cs에 들어가지 않음

do {
    while(Test_and_Set(lock)); // lock의 값을 읽고 true로 설정
    critical section
    lock = false;
    remainder section
}

→ 이러한 작업들을 추상화 시킨 것이 Semaphores

4-1. Semaphores

 

앞과 같이 synchronization 해결 방법이 하드웨어 적으로 구현되어 있다고 가정하고 이를 프로그래밍 할 수 있도록 지원하는 추상 자료형.

 

세마포가 지원되면 프로그래머는 대단히 효율적으로 synchronize 문제를 해결할 수 있다.

 

Semaphore S

• Integer Variable (자원의 개수)
• 아래의 두가지 Atomic 연산에 의해서만 접근 가능

공유 data 획득 과정

P(S):
	while (S<=0) do no-op; // 5개 이미 사용하고 있다면 기다림
	S--; 

공유 data 반납 과정

V(S): 
	S++; // 한 개의 자원을 내어놓음.

이로써 (하나의 프로세스만 이 공유 data에 접근할 수 있는) mutual exclusion 문제를 풀 수 있음.

4-2. busy wait

semaphore mutex; // mutex: mutual exclusion의 준말, 1로 초기화 (1개가 CS에 들어갈 수 있다는 뜻)

Process Pi
do {
    P(mutex); // 양수면 들어가고 아니면 계속해서 기다림.
    critical section
    V(mutex);
    remainder section
} while (1);

하지만 busy wait (=spin lock)은 효율적이지 못함.

spin lock의 상황: 만약 누군가 cs에 들어가 있어서 mutex 값이 0이면 P 연산을 빠져나가지 못한다. 다른 친구가 cs를 빠져나가면서 V연산을 통해 mutex값을 1로 복원시키기 전까지는 while문만 돌리면서 쓸데없이 CPU를 낭비한다.

4-3. block and wakeup

semaphore이 다음과 정의됨

// 1. 세마포의 정의
typedef struct
{
    int value; // semaphore
    struct process *L; // process wait queue
}semaphore;


// 2. 세마포의 연산 정의
P(S):
	S.value--; // 일단 -1 !!! 들어갈 준비를 함
	if (S.value < 0) { // 여분이 없다면
        add this process to S.L; // wait queue에 넣고
        block(); // 잠들게 함
    }

V(S): 
	S.value++; // 일단 +1 !!! 한 개의 자원을 내어놓을 준비를 함.
	if (S.value <= 0) { // 누군가 잠들어 있다면
        remove a process P from S.L; // 끄집어내서
        wakeup(P); // 깨움
    }

block 과 wakeup을 다음과 같이 가정

• block: 커널은 block을 호출한 프로세스를 suspend시킴, 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣음
• wakeup(P): block된 프로세스 P를 wakeup시킴, 이 프로세스의 PCB를 ready queue로 옮김

앞선 value와는 다르다. 여분의 개수를 세는 것이 아니다.

0 이하의 값은 자원에 여분이 없어서 누군가 잠들어있다는 뜻이고 양수는 자원이 남아돌고 있다는 뜻이다.

4-4. Busy-wait vs Block/wakeup

Q. 그렇다면 어떤 게 더 나아? Busy-wait vs Block/wakeup

A. 일반적으로는 Block/wakeup 방식이 더 좋아.

 

Critical section의 길이가 긴 경우 (또는 cs의 경합(경쟁)이 높을수록) Block/wakeup 방식이 적당해. 하지만 반대인 경우에는 Block/wakeup 방식의 오버헤드가 Busy-wait 오버헤드보다 더 커질 수 있어.

4-5. semaphores는 2개의 타입으로 분류할 수 있다.

• counting semaphore
  • 도메인이 0이 이상인 임의의 정수값
  • 주로 resource counting 에 사용 - 자원의 개수를 셈
• binary semaphore (=mutex)
  • 0 또는 1의 값만 가질 수 있는 semaphore
  • 주로 mutual exclusion (lock/unlock)에 사용

4-6. 용어 정리: Deadlock and Starvation

Deadlock

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

Starvation

• Infinite blocking : 프로세스가 suspend된 이유에 해당되는 세마포어 큐에서 빠져나갈 수 없는 현상

5 동기화의 고전적인 문제

5-1. Bounded-Buffer Problem (Producer-Consumer Problem)

• Shared data
  • buffer 자체 및 buffer 조작 변수 (empty, full buffer의 시작 위치)
• Synchronization variables
  • mutual exclusion
    • binary semaphore
    • shared data의 mutual exclusion(lock/unlock)을 위해
  • resource count
    • integer(counting) semaphore
    • 남은 full/empty buffer의 수를 표시하기 위해

코드

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

Producer
    
do{ ...
    produce an item in x
    P(empty); // 빈 버퍼를 얻는 과정, 만약 없다면 소바자가 나타나서 빈 버퍼를 만들어줄 때까지 기다림
    P(mutex); // lock
   	...
    add x to buffer
	...
    V(mutex); // unlock
    V(full); // 내용 찬 버퍼 추가, 혹시 소비자가 기다리고 있었다면 깨워서 소비할 수 있도록
} while (1);
-----------------------------------------------------------------------
Consumer

do {
    P(full); // 내용이 들어있는 버퍼 획득
    P(mutex); // 공유 data lock
    ...
    remove anitem from buffer to y
    ...
    V(mutex);
    V(empty); // 빈 버퍼 추가, 혹시 생산자가 기다리고 있었다면 깨워서 생산할 수 있도록
    ...
    consume the item in y
    ...
} while (1);

요약하자면,

 

생산자 프로세스와 소비자 프로세스가 있는데 공유 버퍼에 동시 접근 시 문제 발생 버퍼에 대해 락을 거는 semaphore를 사용하고 생상자 입장에서의 자원인 빈 버퍼와 소비자 입장에서의 자원인 내용이 든 버퍼를 카운팅하기 위해서 카운팅 semaphore 를 사용했다.

 

5-2. Readers-Writers Problem

• 한 process가 db에 write 중일 때 다른 process가 접근하면 안됨
• read는 동시에 여럿이 해도 됨
• solution
  • writer가 db에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기 중인 reader들을 다 db에 접근하게 해준다.
  • writer는 대기 중인 reader가 하나도 없을 때 db 접근이 허용된다.
  • 일단 writer가 db 접근 중이면 reader들은 접근이 금지된다.
  • wrtier가 db에서 빠져나가야지만 reader의 접근이 허용된다.
• Shared data
  • DB 자체
  • readcount : 현재 db에 접근 중인 reader의 수
• Synchronization variables
  • mutex: 공유 변수 readcount를 접근하는 코드(cs)의 mutual exclusion 보장을 위해
  • db: reader와 wirter가 공유 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라는 공유변수에 접근하기 전에 lock
readcount++;
if (readcount == 1) P(db); // reader가 읽기 전에 writer가 쓰지 못하도록 db를 lock
V(mutex); // readcount라는 공유변수 unlock
...
reading DB is performed
...
P(mutex);
readcount--;
if (readcount == 0) V(db); // reader가 읽었기에 writer가 쓸 수 있도록 db를 unlock
V(mutex);

5-3. Dining-Philosophers Problem

대표적인 교착상태 (Dead Lock) 문제이다.

// 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);

• 앞의 solution의 문제점
  • deadlock 가능성이 있다
  • 모든 철학자가 동시에 배가 고파져 왼쪽 젓가락을 집어버린 경우

• 해결 방안
  • 4 명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다
  • 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다
  • 비대칭: 짝수(훌수) 철학자는 왼쪽 (오른쪽) 젓가락부터 집도록

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

void test (int i) {
    if (state[(i+4)%5] != eating && state[i] == hungry && state[(i+1)% 5] != eating) {
    	state[i] = eating;
        V(self[i]);
}
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);
    P(self[i]);
}
    
Philosopher i
do{ 
    pickup(i);
    eat();
    putdown(i);
    think();
} while(1);

6 동기화 문제의 SOL: Monitor

6-0. 등장 배경: Semaphore의 문제점

• 코딩하기 힘들다
• 정확성(correctness)의 검증, 입증이 어렵다
• 자발적 협력(voluntary cooperation)이 필요하다
• 한번의 실수가 모든 시스템에 치명적인 영향을 준다.

→ process 동기화 문제를 더 쉽게 해결하기 위해 등장한 monitor

6-1. Monitor

동시 수행중인 프로세스 사이에서 추상화 데이터 타입의 안전한 공유를 보장하기 위한 high-level synchronization constructor

 

쉽게 말해, 공유 data에 동시 접근 시 문제가 발생하는 건데, 이 공유 data를 모니터 안에 정의해주고 접근을 모니터 안의 코드 연산만으로 가능하게 한다. 고급 언어 프로그래밍 차원에서 구현된 것이다.

 

• 모니터 내에서는 한번의 프로세스만이 활동 가능
• 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요 없음 !!
• 프로세스가 모니터 안에서 기다릴 수 있도록 condition variable을 사용한다. ex) condition x, y;
• condition variable은 wait와 signal 연산에 의해서만 접근 할 수 있다.
  • x.wait();
    • x.wait()를 invoke한 프로세스는 다른 프로세스가 x.signal()을 invoke하기 전까지 suspend된다.
    • 자원의 여분이 없을 땐 blocked queue에 가서 줄을 서도록 하는데 즉 잠근다.(blocked)
  • x.signal();
    • x.signal()은 정확하게 하나의 suspend된 프로세스를 resume한다.
    • Suspend된 프로세스가 없으면 아무 일도 일어나지 않는다.
    • 자원의 여분이 있을 땐 수행된다.

정리하자면, semaphore는 원자적으로 수행하도록 하는 것이지만 monitor는 기본적으로 동시 접근을 아예 막는다. 따라서 프로그래머는 동시 접근 문제를 생각할 필요가 없다. 그냥 빈 버퍼가 있는지 확인한 뒤 기다리거나(잠들게 하거나) 수행하면 된다.

6-2. 예시1 - Bounded-buffer proplem (생산자 소비자 문제)

코딩 방법

05-1의 코드와 비교하면서 보면서 차이점에 집중

monitor bounded_buffer {
	int buffer[N];
	condition full, empty; // 값을 가지지 않고 자신의 큐에서 프로세스를 sleep 또는 signal(깨우는) 역할만 함

    // 생산자
    void produce (int x) {
        if there is no empty buffer
            empty.wait(); // 빈 버퍼가 없으면 프로세스는 잠들어
        add x to an empty buffer; // 빈 버퍼가 있으면 그냥 데이터 넣으면 됨
        full.signal(); // 혹시 잠들어 있으면 깨워라(O), semaphore처럼 condition variable에 반영하진(X)
    }
 
    // 소비자
    void consume (int* x) {
        if there is no full buffer 
            full.wait(); // 내용 들어있는 버퍼 없으면 프로세스는 (내용 들어있는 버퍼를 기다리는 큐에 줄서서) 잠들어 suspend
        remove an item from buffer and store it to *x // 있으면 내용 꺼내가고
        empty.signal(); // 프로세스 깨워
    }
}

6-3. 예시2 - Dining Philosophers

젓가락: 공유 data → 접근을 monitor 안에 정의해두어 해당 코드로만 접근할 수 있다.

/* enter monitor */
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(); // wait here
    }
    
    void putdown(int i) {
    	state[i] = thinking;
        // test left and right neighbors - 먹을 수 있는지
        test((i+4) % 5); // if L is waiting
        test((i+1) % 5);
    }
    
    void test(int i) {
    	// if 왼쪽과 오른쪽 모두 밥을 안 먹고 있으면
    	if ((state[(i+4)%5]!=eating) && (state[i]==hungry) && (state[(i+1)%5]!=eating)) {
        	state[i] = eating;
            self[i].signal(); // wake up Pi
        }
    }
    
    void init() {
    	for (int i = 0; i < 5; t++)
        	state[i] = thinking;
    }
}
------------------------------------------------------------------------
/* monitor 외부 */
Each Philosopher:

{
	pickup(i); // 젓가락 잡기
    eat(); // 먹거나
    putdown(); // 내림
  	think(); // 생각
} while(1);