Process Synchronization(2)-프로세스 동기화

Initial Attempts to Solve Problem

• 두 개의 프로세스가 있다고 가정 P0, P1
• 프로세스들의 일반적인 구조

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

• 프로세스들은 수행의 동기화(Synchronize)를 위해 몇몇 변수를 공유할 수 있다 → synchronization variable

 

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

*가정

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

• 상호 배제 (Mutual Exclusion)
  • 프로세스 Pi가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안 된다.
• 진행 (Progress)
  • 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다.
  • 당연한 이야기처럼 보이지만, 코드 상의 오류로 인해 여러 개의 프로세스가 동시에 critical section에 들어가는 것을 막으려다 critical section에 아무도 안 들어갔음에도 불구하고 둘 다 못 들어가는 상황이 발생하기도 함.
• 유한 대기 (Bounded Waiting)
  • 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다.
  • 프로세스가 3개 이상이 있을 때, 특정한 두 개의 프로세스가 번갈아가면서 critical section에 들어가기를 반복하며 남은 프로세스가 Bounded Waiting을 충족하지 못하는 상황이 발생하기도 함.

 

Algorithm 1

• Synchronization variable

int turn; //크리티컬 섹션에 들어갈 프로세스의 번호(차례) turn = 0 이면 P0, 1이면 P1 ...
initially turn = 0;

• Process P0

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

• 프로세스 0번 입장에서 보았을 때, 본인 차례가 아닌동안 while문에서 기다리고, 자신의 차례가 되면 critical section에 들어갔다가 turn을 상대방의 차례로 만들어주는 것임
• 문제점
  • 가장 큰 문제점은 프로그램적 해결법의 충족 조건 2번 'Progress'를 만족하지 못함 
  • critical section에 교대로 들어가는 방식이지만, 각 프로세스마다 critical section에 들어가야 하는 빈도 수가 다르기 때문에 발생
  • 예를 들어, P0 → P1 → P2 → P0 순으로 교대한다 했을 때 P2가 critical section에 들어가는 빈도수가 1이라면 그 이후는 P0으로 turn을 바꿔주지 않는다.

 

Algorithm 2

• flag는 프로세스 별로 각각 갖고 있으며 critical section에 들어가고자 하는 의중을 알림
• Synchronization variables

boolean flag[2];
initially flag [모두] = false ; // 둘다 flag가 false이면 아무도 안 들어간 것
//Pi가 critical section에 들어갈 준비가 되면 -> if( flag[i] == true )

• Process Pi

do{
	flag[i] = true;     //나의 flag를 true로 세팅
	while(flag[j]);     //상대방 Pj의 flag를 확인 flag[j]가 true 이면 while로 기다림
	critical section
	flag[i] = false;    //critical section에서 나오면서 내 flag를 false로 바꿈
	remainder section
}while(1);

• Satisfies mutual exclusion, but not progress requirement
• 문제점
  • 둘 다 동시에 critical section에 들어가진 않지만, 둘 다 못 들어가는 경우가 발생 (Progress 미충족)
  • 만약 flag[i]=true까지 수행 후, CPU를 j에게 뺏긴 다면? critial section은 비어있지만 i, j 둘 다 flag가 true 이기 때문에 while문에서 무한 대기. timer interrupt가 일어나더라도 while문을 넘어가지 못하고 끊임없이 양보하는 상황 발생 가능

 

 

 

Algorithm 3 (Peterson’s Algorithm)

• 알고리즘 1과 2의 trun과 flag를 모두 사용한 방법
• Process Pi

do{
	flag[i] = true;     //나의 flag를 true로 세팅
	trun = j; //상대방의 turn을 세팅
	while (flag[j] && turn == j); //상대방의 turn이고 flag까지 true인 경우에만 기다림
	critical section
	flag[i] = false;
	remainder section
} while(1)

• 3가지 조건을 모두 충족함 ( 두 프로세스 간의 critical section 문제를 해결)
• 문제점
  • Busy Waiting (=Spin lock) 
  • 본인의 CPU할당 시간에 다른 프로세스가 critical section에 있다면 의미 없이 while문을 계속 돌며 CPU와 memory를 사용하면서 대기함

 

Synchronization Hardware

• 하드웨어적으로 Test & Modify를 atomic 하게(하나의 instruction으로) 수행할 수 있도록 지원하게 되는 경우 앞의 문제는 간단하게 해결할 수 있음

• 예를 들어, 읽기(1번)와 값 변경(2번)을 Test_and_set(a)처럼 하나의 instruction으로 처리
• Mutual Exclusion with Test & Set

Synchronization variable:
	boolean lock = false;

Process Pi
do{
	while(Test_and_Set(lock)); //lock을 확인하고, lock을 설정하는 것을 수행
	critical section
	lock = false;
	remainder section
}

 

Semaphores

• 앞의 방식들을 추상화시킴
• Semaphore S
  • S는 자원의 개수, S == 0 이면 lock
  • integer variable
  • 아래의 두 가지 atomic 연산(P, V)에 의해서만 접근 가능함
  
• Semaphore를 사용하는 이유
  • lock을 걸고 푸는 것을 Semaphore를 통해 간단하게 프로그래머에게 제공
  • 공유자원을 획득(P연산)하고 반납(V연산)하는 것을 처리
• busy-wait 문제는 그대로 발생함.

 

Critical Section of n Processes

• busy-wait(=spin lock)는 효율적이지 못함
• Block & Wakeup(=sleep lock) 방식으로 구현

*Block & Wakeup(=sleep lock): critical section에 들어가지 못하면 while문을 계속 도는 것이 아니라 block 처리하여 잠들게 함. 프로세스를 block 하는 방식과 비슷함.

 

Block / Wakeup Implementation

• Semaphore를 다음과 같이 정의

• block과 wakeup을 다음과 같이 가정함
  • block
    • 커널은 block을 호출한 프로세스를 suspend 시키고, 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣음
  • wakeup(P)
    • block 된 프로세스 P를 wakeup 시키고, 이 프로세의 PCB를 ready queue로 옮김
    

Implementation(block/wakeup version of P() & V())

• Semaphore 연산이 다음과 같이 정의됨

• P연산에서 S.value의 값을 빼고 시작하기 때문에 V연산에서 S.value ≤ 0이라는 조건을 만족하면, block 된 Process가 있다는 것임

 

Busy-wait Overhead VS Block/Wakeup Overhead

• Busy-wait VS Block/wakeup
• Block/wakeup overhead VS Critical section의 길이
  • Critical section의 길이가 긴 경우 Block/Wakeup이 적당함
  • Critical section의 길이가 매우 짧은 경우 Block/Wakeup의 overhead가 busy-wait overhead보다 더 커질 수도 있음
  • 일반적으로는 Block/Wakeup 방식이 더 좋음

 

Two Types of Semaphores

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

 

Deadlock and Starvation

• Deadlock
  • 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상
• S와 Q가 1로 초기화된 Semaphore
  • P0와 P1이 각각 다른 자원을 서로 갖고 있을 때, 서로 상대방의 자원을 요구하며 deadlock에 걸림
  • P0와 P1이 자원(S, Q)을 얻어야 하는 순서를 동일하게 설정하면 해결 가능
  

• Starvation
  • indefinite blocking. 프로세스가 suspend 된 이유에 해당하는 Semarphore Queue에서 빠져나갈 수 없는 현상
  • 특정 프로세스들만 자원을 사용하게 되면서 남은 프로세스들이 자원을 얻지 못하는 상황

 

출처

KOCW :  이화여대 반효경 교수님 <운영체제, 2014>