Process Synchronization

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

일관성(consistency)를 위해 협력프로세스간의 실행순서를 정해주는 메커니즘이 필요

Race Condition

여러 프로세스들이 동시에 데이터에 접근하는 상황에서, 어떤 순서로 데이터에 접근하느냐에 따라 결과 값이 달라질 수 있는 상황

→

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

Race condition을 막고 일관성을 유지하기 위해서는 협력 프로세스 간의 실행 순서를 정해주는 메커니즘인동기화(Synchronization)가 필요.

1. 커널모드 running 중 interrupt가 발생하는 경우

커널모드 running 중 interrupt 가 발생하여 인터럽트 처리루틴이 수행

해결책 : 커널 모드의 수행이 끝나기 전에는 인터럽트를 받지 않도록 하는 방법(disable/enable)으로 문제를 해결

2. 프로세스가 시스템 콜을 호출해서 커널 모드로 수행 중인데 Context switch가 발생하는 경우

시스템 콜을 수행하는 동안에는 둘 다 커널 주소 공간의 데이터를 접근한다.
커널 주소 공간에서 작업을 수행하는 도중에 CPU를 빼앗으면 race condition이 발생한다.

해결책: 커널 모드를 수행 중일 땐 CPU가 preempt 되지 않도록 하고, 커널 모드에서 유저 모드로 돌아갈 때 preempt 되도록한다.

3. 멀티 프로세서에서 공유 메모리 내의 커널 데이터에 접근하는 경우

멀티 프로세서의 경우 interrupt enable/disable로 해결되지 않는다.

해결책 1) 한번에 하나의 CPU만이 커널에 들어갈 수 있게 하는 방법

→ 비효율적, 두 프로세서가 서로 다른 데이터에 접근하여 Race condition의 가능성이 없음에도 불구하고 한 번에 한 CPU만 커널에 들어갈 수 있음

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

**Critical Section**

임계 영역이란 프로세스간에 공유자원을 접근하는데 있어서 문제가 발생하지 않도록 한번에 하나의 프로세스만 이용하게끔 보장해줘야 하는 영역

Critical Section으로 인해 발생하는 문제들을 해결하기 위해서는 다음 조건들을 만족해야 한다.

1. Mutual Exclusion (상호 배제)

• 하나의 프로세스가 임계 영역에 들어가 있다면 다른 프로세스는 들어갈 수 없어야 한다.

2. Progress (진행)

• 임계 영역에 들어간 프로세스가 없는 상태에서 들어가려 하는 프로세스가 여러개라면 어느 것이 들어갈지 결정해주어야 한다.

3. Bounded Waiting (한정 대기)

• 다른 프로세스의 Starvation을 방지하기 위해서 한 번 임계 영역에 들어간 프로세스는 다음 번 임계 영역에 들어갈 때 제한을 두어야 한다.

Critical Section problem 해결 알고리즘

1. Algorithm 1

현재 Critical Section에 들어갈 프로세스가 어떤 프로세스인지를 한 변수로 나타내어 일치하는 프로세스만 진입하도록 하는 방법

Process 0

do {
   while(turn != 0);    // my turn?
   critical section
   turn = 1;
   remainder section  // now it's your turn
} while(1)

Process1

do { 
   while(turn != 1); // my turn?
   critical section 
   turn = 0;
   remainder section  // now it's your turn
} while(1)

Mutual Exclusion은 만족하지만 Progress는 만족하지 못한다.

예를 들어 P0의 remainder section 수행 시간이 매우 길어서 여전히 remainder section에서 수행 중이고, P1가 수행을 한번 마치고 다시 Critical Section으로 진입하려고 한다면 turn == 0이기 때문에 진입할 수 없다.

따라서 Critical Section에 아무런 프로세스가 존재하지 않게 된다.

2. Algorithm 2

특정 프로세스가 Critical Section에 진입할 준비가 되었다는 것을 나타내는 변수(flag)를 두어, 다른 프로세스가 Critical Section에 진입하려고 한다면 현재 프로세스는 기다리는 방법

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

Mutual Exclusion은 만족하지만 Progress는 만족하지 못한다.

두 프로세스가 flag = true를 수행하고 나면 두 프로세스 모두 무한히 Critical Section에 진입하지 못하고 기다리는 상황이 발생하게 된다.

3. Algorithm 3(Peterson's Algorithm)

이전의 알고리즘 1과 2를 합쳐놓은 개념

turn 변수와 flag 변수를 동시에 사용

Process Pi

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

Pi는 flag[i] = true로 바꾸면서 Critical Section에 진입하려고 한다.
turn = j로 바꿔주면서 상대방이 들어가게 한다.
만약 상대방이 들어가고 싶고 (flag[j] == true), 현재 상대방이 Critical Section에 들어가 있으면 (turn == j) 기다린다.
그렇지 않으면 Pi가 들어간다.
그리고나서 Critical Section을 빠져나오면 들어가고 싶지 않다고 flag[i] = false로 바꿔준다.

Mutual Exclusion, Progress, Bounded waiting 을 모두 만족

하지만 Critical Section진입을 기다리면서 CPU와 메모리를 계속 사용하는 Busy waiting(=spin lock=loop)의 문제점이 있다.

→하드웨어적으로 Test와 Modify를 atomic 하게(읽기와 쓰기를 한번에(하나의 instruction으로)) 수행할 수 있도록 지원하는 경우 앞의 문제는 간단히 해결할 수 있다.

메모리에서 데이터를 읽으면서 쓰는 것까지 하나의 명령어로 동시에 수행이 가능하다면 코드가 훨씬 간결해지고, 이는 Test_and_Set을 이용하여 아래와 같이 구현된다.

boolean Test_and_Set(boolean *target){
	Boolean rv = *target;
	*target = TRUE;
	return rv;
}

Synchronization variable :
boolean lock = false;

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

instruction 을 한 줄이 아닌 두개의 instruction 으로 지원하여 instruction+flag처리를 한 번에 다룰 경우, 임계영역에 대한 처리가 간단해진다

Semaphores

커널모드에서 공유자원에 대한 동기화를 설정해 주기 위한 기법

공유자원에 접근할 수 있는 Process 혹은 Thread의 갯수를 Counting할 수 있다.

정해진 갯수만큼의 Thread들이 동시에 동기화되는 것을 가능하게 한다.

P(S)는 공유 데이터를 획득하는 연산이고, V(S)는 반납하는 연산이다.

• 종류
  • Counting Semaphore : 정수 값의 범위가 0 이상으로 제한이 없다. 주로 자원의 개수를 세는 데 사용한다.
  • Binary Semaphore : 정수 값이 오직 0 또는 1이다. Mutex lock과 동일한 역할을 갖는다.
• 사용

Synchronization variable
semaphore mutex; // mutual exclusion

do {
   P(mutex);        // if positive, decrement & enter, otherwise, wait
   critical section
   V(mutex);        // Increment semaphore
   remainder section
} while(1);

이 방식은 Busy Waiting이 발생하므로 비효율적

typedef struct{
	int value;         //가용한 자원의 수
	struct process *L;
}semaphore

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

void signal(semaphore S){
	S.value++;
	if(S.value <=0){
		remove a process P from S.L;
		wakeupu(P)
	}
}

• block
  • 커널은 block을 호출한 프로세스를 suspend 시킨다
  • 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣는다
• wakeup(P) :
  • block된 프로세스 P를 wakeup 시킨다
  • 이 프로세스의 PCB를 ready queue로 옮긴다
• signal 함수에서 S.value가 0 '이하'인 이유
  • 이전에 S.value++를 통해 자원을 내놓았는데 아직 0 이하라는 의미가 기다리고 있는 프로세스가 존재한다는 의미이기 때문이다.

critical section 길이가 매우 짧은 경우 Block/wakeup 오버헤드가 busy-wait 오버헤드보다 더 커질 수도 있다

Classical Problems of Synchronization

1. Bounded-Buffer Problem : 공유버퍼 문제 (Producer-Consumer Problem)

생산자 스레드들과 소비자 스레드들이 있고, 사이에 공유 버퍼가 있다고 가정하자.

만약 둘 이상의 생산자가 비어있는 버퍼를 동시에 보고 데이터를 만들어 넣는다면 문제가 발생할 수 있다. 마찬가지로 둘 이상의 소비자가 동시에 동일한 버퍼의 데이터를 사용한다면 문제가 발생할 수 있다. 따라서, 동시에 버퍼에 접근할 수 없도록 락을 걸어줘야 한다.

또, 버퍼가 꽉 찬 상태에서 생산자는 반드시 소비자가 버퍼의 데이터를 사용하기를 기다려야 하고, 버퍼가 빈 상태에서 소비자는 생산자가 버퍼를 채우기를 기다려야 한다.

그러므로 락을 걸고 푸는 용도, 자원의 개수를 카운팅 하는 용도로 세마포어 변수를 사용한다.

발생하는 문제

1) 복수의 생산자 동시접근

2) 복수의 소비자 동시접근

3) 버퍼가 꽉 차있을 때 생산자의 접근

4) 버퍼가 비어있을 때 소비자의 접근

2. Readers-Writers Problem : 읽고 쓰기 문제

Readers-Writers Problem은 한 프로세스가 데이터를 수정하는 작업을 수행할 때 다른 프로세스가 접근하면 안 되고, 읽는 작업은 여러 프로세스가 동시에 수행 가능하도록 하는 문제

해결책

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

→Starvation의 가능성이 있다. 계속해서 reader가 들어오거나 writer가 들어오는 경우 한쪽이 계속 수행되지 않을 수 있다. 이는 큐에 우선순위를 부여한다거나, 일정 시간이 지나면 자동으로 write or read가 되도록 하여 해결

3. Dining-Philosophers Problem

각 철학자는 식사를 하기를 원하고, 철학자가 식사를 하기 위해서는 양쪽 젓가락을 모두 집어야 한다.

Deadlock 상태를 방지하기 위한 해결책

• 최대 4명만 동시에 테이블에 앉도록
• 젓가락을 두 개 모두 집을 수 있을 때만 젓가락을 집을 수 있게
• 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록

Monitor

• 세마포어의 문제점은 코딩하기가 힘들고 실수하기 쉬우며, 정확성을 입증하기가 어렵다.
• V와 P 연산 순서에 따라 Deadlock상태에 빠지거나 Mutual Exclusion이 깨질 수 있다.

Monitor(모니터)는 동시 수행 중인 프로세스 사이에서 추상 데이터의 안전한 공유를 보장하기 위한 High-level 동기화 구조

• 공유 데이터를 접근하기 위해서는 모니터의 내부 Procedure를 통해서만 접근할 수 있도록 한다.
• 세마포어가 어셈블리어에 적합한 도구였다면, 모니터는 이보다 더 고급 언어의 동기화 기법
  → Java에서는 모니터를 모든 객체에게 기본적으로 제공
• 사용이 쉽고, 에러 발생 가능성이 낮음
• 세마포어는 프로그래머가 직접 Race condition을 해결해야 하지만 모니터는 자체적인 기능으로 해결할 수 있게 된다.

[Race condition]

이를 방지하기 위해 여러 알고리즘이나 세마포어 같은 도구들을 배웠다.

반면 모니터는 아래와 같이 이루어져 있다.

• 프로세스가 공유 데이터를 사용하기 위해서는 반드시 모니터 내의 Procedure를 통해야 한다. 그리고 동일한 시간엔 오직 한 프로세스나 스레드만 모니터에 들어갈 수 있다.
• 모니터에 진입하려고 했지만 내부에 프로세스가 들어가 있어 진입하지 못한 프로세스들은 모니터 큐(Monitor Queue)에서 기다린다.
• 프로세스가 모니터 내에서 기다릴 수 있게 하도록 조건 변수(Condition variable)가 사용된다.
• 조건 변수는 오직 wait()와 signal() 연산만으로 사용될 수 있다. 세마포어 변수와 유사하지만 변수가 어떤 값을 가지진 않고, 자신의 큐에 프로세스를 매달아서 sleep 시키거나 큐에서 프로세스를 깨우는 역할만 한다.

참고

• 반효경 교수님 운영체제 강의