[운영체제] Day06. Process Synchronization

데이터의 접근

Race Condition (경쟁 상태)

연산부와 저장부의 독립적 존재
여러 연산부가 하나의 저장부를 공유하는 경우 Race Condition(경쟁 상태) 문제 발생 가능
데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 의해 달라진다.

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

2. Process가 System Call을 하여 Kernel Mode로 수행 중인데 Context Switch 발생하는 경우

kernel의 데이터 : 일종의 전역 변수임. (여러 Process가 공유)
한 Process가 kernel의 데이터를 변경하는 중 interrupt 발생 시 문제 발생 가능

해결책 :

• Kernel mode에서 수행 중일 때는 CPU를 빼앗지 않음.
  kernel mode에서 user mode로 돌아갈 때 빼앗음
  즉, kernel mode 시작 시 C/S disable, 종료 시 C/S enable

3. Multi-Processor에서 Shared memory 내의 Kernel Data

위의 문제와 비슷하나 더 복잡하다.
다른 CPU 간의 메모리 데이터 간섭 문제 발생

해결책 :

1. 한번에 하나의 CPU만이 커널에 들어갈 수 있게 하는 방법
   : 상당한 Overhead 발생
2. 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 Lock / UnLock 설정
   : Lock 시 해당 데이터 조작 불가. UnLock 해야 비로소 수행 가능

Process Synchronization

공유 데이터(Shared Data)의 동시 접근(Concurrent Access)는 데이터 불일치 문제(Inconsistency) 발생
일관성(Consistency) 유지를 위해서 협력 프로세스 간 실행 순서를 정해주는 메커니즘이 필요

Critical Section Problem

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

하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 (동일 데이터에 접근하는) critical section에 진입하지 못하도록 한다.

Algorithm 1

Synchronization Variable : turn
critical section 진입 전 turn 여부를 검사
(turn을 통해 차례 검사)

// turn = 0으로 초기화.
// turn == i(자신의 차례면) 면 critical section 진입
int turn = 0;

do {
	while (turn != 0) : 
    critical_section();
    // turn 넘겨 줌
    turn = 1;
	remainder_section();
} while (1);

• Critical Section에는 하나씩 들어감을 보장
• turn을 상대 Process가 바꿔주기만을 하염없이 기다려야함 (아무도 critical section에 진입하지 않았음에도)
• 두 Process가 CPU를 사용하고자 하는 빈도 수 차이가 있을 때

  P1은 100번 쓰고 싶음. P2는 한 번 쓰고 싶음.
  P2 쓰고 P1 넘겨줌, P2 쓰고 P1 넘겨줌. P2는 다 써서 turn 안 넘겨줌.
  -> P2도 놀고 있는 CPU 사용 못함.

• 과잉 양보 문제 발생

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

Mutual Exclusion (상호 배제)

프로세스가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안된다.

Progess (진행)

아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다.

Bounded Waiting (유한 대기)

프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다. (starvation 방지)

가정

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

Algorithm 2

Synchronization Variable : flag
flag 통해서 자신이 critical section 진입 희망을 표현 + 상대방 flag 검사

// turn = 0으로 초기화.
// turn == i(자신의 차례면) 면 critical section 진입
int turn = 0;

do {
	// critical section 진입 희망 
	flag[i] = true;
	// 다른 flag 확인
	critical_section();
    // I'm out
	flag[i] = false;
	remainder_section();
} while (1);

• Critical Section에는 하나씩 들어감을 보장
• flag on, 하지만 CPU 진입 전에 CPU 빼앗기면?
• 끊임 없는 양보 상황 발생 가능

Algorithm 3

Synchronization Variable : turn, flag
위에서 사용한 두 변수 모두 사용
세 가지 조건 모두 충족 가능

// turn = 0으로 초기화.
int turn = 0;

do {
	// critical section 진입 희망 
	flag[i] = true;
    // 턴 넘기기
    turn = j; 
	// flag
    while (flag[j] && turn j) ; 
	critical_section();
    // I'm out
	flag[i] = false;
	remainder_section();
} while (1);

실질적 구현

1. Semaphore

• 일종의 추상 자료형
  앞의 방식들을 추상화 시킴
• Semaphore S :
  Integer variable
  자원의 개수
  아래의 두 가지 atomic 연산(P, V)에 의해서만 접근 가능
• P 연산 : 자원 획득 과정, Lock
  V 연산 : 자원 반납 과정, UnLock
• mutual exclusion을 위해서는 S값을 1로 설정

P(S) :

// 자원 없으면 계속 wait
while (S <= 0) do no-np;
S--;

V(S) :

S++;

• Busy-Wait(spin lock)은 비효율적
  Lock을 걸고 순회하면서 Lock 여부를 조회하는 방식
• Block-Wakeup(sleep lock)

Semephore를 다음과 같이 정의

typedef struct
{
	// semaphore (자원)
	int value; 
    // process wait queue (대기 프로세스 큐)
    struct process *L; 
}

block과 wakeup은 다음과 같이 가정

• block : 커널은 block 호출한 프로세스를 suspend
  이 프로세스의 PCB를 Semaphore에 대한 wait queue에 넣음
• wakeup : block 된 프로세스를 wakeup
  이 프로세스의 PCB를 ready queue로 옮김
  

Impletation

P(S) :

// 일단 빼고 봄
S.value--;
// 뺐더니 음수 (가용 자원 X)
// wait list (일종의 연결 리스트) 추가 후 block
if (S.value < 0) 
{
	block();
}

V(S) :

S.value++;
// 자원 반환 후 S.value가 0 이하라면
// list에서 하나 끄집어서 깨워줘야 함
// CPU 자원을 기다리고 있다는 뜻이므로
if (S.value <= 0) 
{
	wakeup(P);
}

Which is Better ?

Busy-wait vs Block/wakeup

• 일반적으로는 Block/wakeup이 유리
• Busy-wait은 지속적으로 CPU 낭비
• Critical section이 매우 짧은 경우
  Blcok/Wakeup 오버헤드가 Busy-wait 오버헤드보다 커질 수 있다.

Semaphore type

1. Counting Semaphore
   도메인이 0 이상인 임의의 정수값
   주로 resource counting에 사용
2. binary Semephore
   0 또는 1 값만 가질 수 있는 semaphore
   주로 mutual exclusion (Lock / UnLock)에 사용

Deadlock and Starvation

Deadlock

• 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상
• 각각의 Process 입장에서 보면 Starvation 문제

  예시

  S, Q가 1로 초기화된 Semaphore.
  P가 S를 소유, V가 Q를 소유
  P는 Q가 없어서 작업 못함.
  -> Q를 무한히 기다림... S를 무한히 소유함...
  V는 S가 없어서 작업 못함.
  -> S를 무한히 기다림... Q를 무한히 소유함...
  작업이 끝나야지만 자원을 반환하므로 발생하는 문제

• 해결책
  Semaphore를 얻는 순서를 정해준다.
  (Q를 얻기 위해서는 우선 S를 보유해야 함)

Classical Problems of Synchronization

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

• 크기가 유한한 공유 버퍼 존재
  Producer Process : 데이터 생성, Buffer 입력
  Consumer Process : 데이터 소비

• 여러 생산자(소비자) 존재 시 공유 데이터 inconsitency 발생 가능

• 각 Buffer가 공유 자원.

• 자원이 여러 개 (Counting Semaphore)
  Mutex Lock (binary Semaphore)

  Producer 입장
  1. Empty Buffer 존재? (없으면 대기)
  2. 공유 데이터에 LOCK
  3. Empty Buffer 데이터 입력 및 조작
  4. UNLOCK
  5. Full Buffer 증가

  Consumer 입장
  1. Full Buffer 존재? (없으면 대기)
  2. 공유 데이터에 LOCK
  3. Full Buffer 데이터 입력 및 조작
  4. UNLOCK
  5. Empty Buffer 증가

2. Readers-Writers Problem

• 한 process가 DB에 write 중일 때 다른 process가 접근하면 안됨.
• read는 여럿이 해도 됨.
• Shared data : DB, readCount (DB접근 중인 Reader 수)
• Synchronization Variables
  mutex for readCount Locking
• Writer에 대한 Starvation 문제 발생 가능
  (readCount 가 0인 순간에 write 가능하게 코드 작성 시)
• 신호등과 마찬가지로 일정 시간마다의 reader만 허용하고 write를 허용하면 해결 가능

3. Dining-Philosophers Problem

• 젓가락이 한 쪽씩 뿐이다. (젓가락이 Semaphore)
• 철학자는 계속 자원을 소모해야 한다.
  솔루션
• 젓가락을 집고 밥을 다 먹고 젓가락을 내려놓자
• Deadlock 가능성 (여러 철학자가 동시에 배고파진 경우)
  해결방안
• 4명의 철학자만이 테이블에 동시에 앉을 수 있게 한다
• 젓가락을 두 개 모두 잡을 수 있을 때에만 젓가락을 잡게 한다
• 비대칭 : 짝수(홀수) 철학자는 왼쪽(오른쪽) 부터

Monitor

Semaphor의 문제점

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

Monitor

동시 수행중인 프로세스 사이에서 Abstract data type의 안전한 공유를 보장하기 위한 High-level Synchronization Constructs

• 공유 데이터를 중심으로 함수가 정의
• 공유데이터 접근 시 반드시 모니터 내부 함수를 통해서만 접근할 수 있도록
• 모니터 내에서는 한번에 하나의 프로세스만이 활동 가능
• 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요 없음
• 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 condition variable 사용
• condition variable은 wait 과 signal 연산에 의해서만 접근 가능
• wait : process suspend
  signal : suspend 된 process resume