[OS] 공유 자원의 접근을 제한하는 Process Synchronization

많은 프로세스들은 자원 혹은 메모리를 공유한다.

ex) 공유 메모리를 사용하는 프로세스들, 커널 내부 데이터를 접근하는 루틴들

Storage-Box: Memory Address Space / Execution-Box: CPU Process

프로세스의 수행은 공유 자원에 변화를 끼치게 되고, 여러 프로세스가 동시에 공유 자원에 접근하면 데이터의 일관성을 보장받을 수 없다.

그래서 프로세스는 특정 공유 자원을 선점할 때 다른 프로세스가 접근할 수 없게끔 제한한다.

하지만 특정 자원에 접근하려는 프로세스가 여러 개 일 경우 Race Condition이 발생할 수 있다

 

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

따라서 consistency 유지를 위해서는 협력 프로세스 간의 자원 처리 순서를 정해주는 메커니즘이 필요하다

 

Race Condition

: 여러 프로세스들이 동시에 공유 데이터를 접근하려 할 때 프로세스의 접근 순서가 데이터의 최종 연산 결과에 영향을 미치는 현상

Race Condition을 막기 위해서는 concurrent process는 synchronize(동기화) 되어야 한다

 

각각의 프로세스는 자원의 배타 선점을 위해 Code segment에 공유 데이터의 접근을 제한하는 Critical Section(임계 구역)을 가지고 있다

즉, 하나의 프로세스가 Critical Section에 있을 때 다른 모든 프로세스는 해당 Critical Section에 접근할 수 없다 ❗❗

 

임계 구역을 이용한 동기화 방식에는 충족해야 할 조건이 몇 가지 있다

• Mutual Exclusion : 프로세스 P가 Critical Section을 수행중이면 다른 모든 프로세스는 그들의 Critical Section에 접근할 수 없다
• Progress : 아무도 Critical Section에 있지 않은 상태에서 들어가고자 하는 프로세스가 있으면 Critical Section에 들어가게 해줘야 한다
• Bounded Waiting : 프로세스가 Critical Section에 들어가려고 한 후 부터 요청이 허용될 때 까지 다른 프로세스들이 Critical Section에 들어가는 회수에 한계가 있어야 한다

 

몇 가지 알고리즘을 살펴보자

 

TestAndSet (Synchronization Hardware)

function TestAndSet(boolean_ref lock) {
    boolean initial = lock
    lock = true
    return initial
}

do {
    while(TestAndSet(&lock))
        ; // do nothing
        // critical section
    lock = false;
        // remainder section
} while(true);

: lock이라는 변수를 두어 처음 진입에 시도하는 프로세스는 임계 구역에 진입한다. 동시에 turn을 1로 set하여 다른 프로세스는 임계 구역에 진입할 수 없다(mutual exclusion).

crititical section영역의 수행을 끝낸 뒤에는 lock을 false로 바꿔 다른 프로세스의 진행을 허용한다(progress).

하지만 bounded waiting 조건을 만족하지 않아, 한 프로세스가 임계 구역에 진입하면 다른 프로세스는 while문 내에서 끊임없이 접근을 시도한다.

 

Peterson's Algorithm

 bool flag[2] // 불린 배열(Boolean array)
 int turn // 정수형 변수
 
 flag[0]   = false // false은 임계 구역 사용을 원하지 않음을 뜻함.
 flag[1]   = true
 turn      = 0 // 0 은 0번 프로세스를 가리킴, 1은 1번 프로세스를 가리킴
 
  P0: flag[0] = true // 임계 구역 사용을 원함
     turn = 1 // 1번 프로세스에게 차례가 감
     while( flag[1] && turn == 1 )
     {
          // flag[1] 이 turn[1] 을 가지고 있으므로
          //현재 사용중임
          // 임계 구역이 사용 가능한지 계속 확인
     }// 임계 구역
     ...
    // 임계 구역의 끝
   flag[0] = false
   
   
   
   
   
   P1: flag[1] = true
    turn = 0
    while( flag[0] && turn == 0 )
    {
         // 임계 구역이 사용 가능한지 계속 확인
    }// 임계 구역
    ...
    // 임계 구역의 끝
    
        flag[1] = false

피터슨 알고리즘은

1. 임계 구역의 진입을 원할 시 turn 변수를 상대 프로세스를 가리키게 해서 우선적으로 대기(자신의 차례가 올 때 까지)한다(상호 배제).

2. 임계 구역을 빠져나오는 프로세스는 자신의 flag를 false로 만들어 다른 프로세스가 접근할 수 있게 한다(진행, 한정 대기).

를 통해 3가지 조건을 만족한다.

하지만 while문을 대기하며 루프에 너무 오래 머무르기 때문에 그 과정에서 CPU와 Memory를 계속해서 소모하여 Busy Waiting을 한다.

✅ Bush Waiting(Sprinning): 어떤 특정 공유 자원에 대해 두 개 이상의 프로세스나 쓰레드가 이용 권한을 획득하고자 접근 가능 여부를 계속해서 확인하는 것

 

Semaphores - 세마포어

세마포어는 앞에 등장한 상호 배제를 위한 병렬 프로그래밍 알고리즘을 추상화한 것 이다. 아래의 두 가지 atomic 연산에 의해 접근할 수 있다. block & wake-up 방식으로 구현한다

P(S) : while(S<=0)
		 do no-op;		//wait
         S--;
// if positive, decrement & enter
         
V(S) : S++;		//반납
// otherwise, wait until positive

Synchronization variable
Semaphore mutex;

Process Pi
	do{
    	P(mutex);
        // critical section
        V(mutex);
        // remainder section
    }while(1);
    
typedef struct{
	int value;
    struct process *L;
}semaphore

 

Block & wake-up ?

block: 커널은 block을 호출한 프로세스를 suspended하고 이 프로세스의 PCB를 세마포어에 대한 wait queue에 넣는다

wakeup(p): blocked된 프로세스 P를 wakeup 시키고 이 프로세스의 PCB를 ready queue로 옮긴다

P(S): 
		S.value--;
        if(S.value<0){
        	add this process to S.L;
            block();
        }
        

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

 

Busy-Wait 🆚 Block & Wake-Up

기본적으로 Block/WakeUp의 overhead와 critical section의 길이로 둘 중 어느 대기 방법을 쓸 지 선택할 수 있다.

• critical section의 길이가 긴 경우 block & wake-up이 적당하다
• critical section의 길이가 매우 잛은 경우 block & wake-up 오버헤드가 busy-wait 오버헤드보다 더 커질 수 있다.
• 일반적으로는 Block&Wake-Up 방식이 더 좋다

 

➕ Starvation(in semaphore): indefinite blocking. 프로세스가 suspend된 이유에 해당하는 세마코어 큐에서 빠져나갈 수 없는 현상