[OS] Process Synchronization(1) - 프로세스 동기화

프로세스 동기화

---

• 프로세스는 독립적으로 수행되면 올바르게 동작하나 공유 변수의 값이 결과에 영향을 주므로 병행으로 수행되면 실행되는 순서에 따라 올바르게 동작하지 않을 수 있다.
• 공유 메모리에 있는 변수 counter의 값이 5일 때, 생산자와 소비자가 각각 "counter++;"와 "counter--;"를 병행으로 수행하면 결과는 5가 되어야 하지만 그렇지 않을 수 있다.

→ 이처럼 병행으로 수행되는 여러 프로세스가 공통된 데이터를 조작할 때 결과가 접근 순서에 의해 결정되면 경합 상태(race condition)가 존재한다고 한다.

 

 

 

임계 구역 문제

---

• 임계 구역(critical section) : 프로세스 코드의 일부분으로서, 다른 프로세스와 공동으로 사용하는 변수, 테이블, 파일 등을 변경하는 부분임계 구역의 실행은 상호배타적(Mutually-Exclusive)으로 실행되어야 한다. 즉, 한 프로세스가 임계 구역을 실행하고 있으면 다른 프로세스는 임계 구역에 진입할 수 없어야 한다.
• 진입 구역(entry section) : 따라서 각 프로세스는 임계 구역에 진입하기 전 허가를 받아야 한다. 이 허가를 요청하는 코드 부분이 진입 구역이다.
• 출구 구역(exit section) : 허가를 받아 임계구역을 실행한 다음에는 다른 프로세스들이 진입할 수 있도록 해주어야 한다. 해당 부분 코드 구역이다.
• 잔류 구역(remainder section) : 진입 구역, 임계 구역, 출구 구역이 아닌 코드 부분

 

 

임계 구역이 포함된 프로세스의 일반구조

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

• 임계 구역 문제를 해결하는 메커니즘은 다음 세 가지 요건을 충족해야한다.

1. 상호 배제(mutual exclusive) : 한 프로세스가 임계 구역에서 실행하고 있으면 어떤 프로세스도 임계 구역에 진입할 수 없어야 한다.
2. 진행(progress) : 임계 구역을 실행하고 있는 프로세스가 없을 때, 몇 개의 프로세스가 임계 구역에 진입하고자 하면 이들의 진입 순서는 이들에 의해서만 결정되어야 한다. 또한 이 선택은 무한정 연기되어서는 안된다.
3. 한계 대기(bounded waiting) : 한 프로세스가 자신의 임계 구역에 진입하고자 요청을 한 후부터 이 요청이 허용될 때까지 다른 프로세스가 그들의 임계 구역에 진입할 수 있는 회수가 제한되어야 한다.

 

 

소프트웨어 접근 방법

---

두 개의 프로세스를 위한 해결책

• 두 개의 프로세스 중 하나를 P(0)라 하고 다른 하나는 P(1)이라 하자. 또한 설명의 편리성을 위해 하나를 P(i)라 하면 다른 하나는 P(j)가 된다.

 

Peterson's Algorithm

• 공유 변수

boolean flag[2];
int turn;

• 초기값

flag[0]=flag[1]=false;
turn = 0; /* or 1 */

포르세스 P(i)의 구조는 다음과 같다.

do{
	flag[i] = true;
    turn = j;
    while(flag[j] && turn == j);
    critical section
    flag[i] = false;
    remainder section
}while(1);

임계 구역에 진입하기 전에 P(i)는 flag[i]를 true로 설정하여 자신이 진입하고자 함을 나타내고, 그 다음 turn의 값을 j로 설정하여 다른 프로세스가 진입하고자 하면 이를 허용한다.

P(i)는 flag[j]가 false이거나 turn이 i일 경우에만 진입할 수 있다.

• 상호 배제(mutual exclusive) : 두 프로세스가 모두 진입하고자 하더라도 진입 구역의 두 번째 문장의 실행 순서에 따라 turn의 값은 i or j 중 하나의 값을 가지게 되므로 두 프로세스 중 하나만 while문을 통과할 수 있다. 또한 다른 프로세스는 임계 구역에 진입한 프로세스가 자신의 flag 값을 false로 설정하기 전까지 임계 구역에 진입할 수 없다.
• 진행과 한계 대기 : P(i)가 진입을 시도하지 않으면 flag[i] 값이 false이므로 P[j]는 임계 구역에 진입할 수 있다. 둘 다 동시에 진입하고자 하면 상호 배제가 충족되므로 어느 하나만 진입할 수 있으며 진입된 프로세서가 임계구역을 빠져나오면 flag값을 false로 바꾸므로 다른 프로세서는 진입할 수 있다. 따라서 최대 다른 프로세스가 한 번 진입한 후에는 진입할 수 있다.

 

 

다중 프로세스를 위한 해결책

---

Bakery Algorithm

• Base Thinking : 가게에 들어오는 손님들은 번호를 하나 받으며, 가장 낮은 번호를 받은 손님 순으로 서비스를 받는다. 그런데 모든 손님이 다른 번호를 받도록 보장할 수 없다. 만약 두 손님이 같은 번호를 받으면 이름 순으로 서비스를 받는다.

* 모두 다른 번호를 받도록 하기 위해서는 번호를 받는 것 자체가 임계 구역이 된다.
* 컴퓨터에서 프로세스는 모두 다른 이름(프로세스 번호)을 가진다.

공유 변수

boolean choosing[n];
int num[n];

choosing은 모두 false로 초기화되며, num은 모두 0으로 초기화된다.

표기법

• (a, b) < (c, d) : a < c이거나 a == c이고 b < d이면 참
• max(a0, a1, ... , a(n-1)) : a(i)[i=0, ..., n-1] 중 가장 큰 값

 

프로세스 P(i)의 구조는 다음과 같다.

do{
    choosing[i] = true;
    num[i] = max(num[0], num[1], ... , num[n-1]) + 1;
    choosing[i] = false;
    for(j=0;j<n;j++){
    	while(choosing[j]);
        while((num[j] != 0 && ((num[j],j) < (num[i],i)));
    }
    
    critical section
    
    num[i] = 0;
    
    remainder section
}while(1);

 

 

 

알고리즘의 정확성

---

• 상호배제
  • P[i]가 번호를 선택한 후에 P[k]가 선택하였다면 (num[i],i) < (num[k],k)가 성립한다. 따라서 P[k]는 P[i]가 임계 구역에 빠져 나오면서 num[i] = 0을 할 때까지 진입할 수 없다.
  • 비슷한 시기에 번호를 받아 같은 번호를 받더라도 두 프로세스의 이름이 같을 수 없으므로 이 중 하나가 먼저 임계구역에 진입하며, 다른 하나는 그 프로세스가 임계 구역에 빠져나올 때까지는 진입할 수 없다.
  • choosing 변수가 필요한 이유 : 같은 번호를 받은 두 프로세스가 둘 다 임계 구역에 진입하는 경우를 제거하기 위해 필요하다. 예를 들어 같은 번호를 받게 되는 두 프로세스 P[i]와 P[k] 중 P[i]는 번호를 받는 도중에 프로세스 스위치가 일어났고, 다른 프로세스는 계속 진행을 하여 for문을 수행하고 있다. 이 경우 while(choosing[j]); 문이 없으면 P[k]는 임계 구역에 아무런 제재 없이 진입하게 된다. P[i]가 다시 실행되면 P[k]와 번호가 같고 이름이 더 작으므로 이 프로세스도 진입하게 된다.
• 진행 : 번호를 선택하고 있지 않는 프로세스는 num[i] = 0이므로 다른 프로세스의 진입을 막지 못한다.
• 한계 대기 : 진입하고자하는 두 프로세스 P[i]와 P[k] 중 P[k]가 먼저 번호를 받아 진입을 하였어도 P[k]가 기다리고 있는 P[i]보다 먼저 다시 진입을 할 수 없다. 즉, P[i]는 최대 각 프로세스가 각 한 번씩 진입한 후에는 진입할 수 있다.