2022. 3. 23. 15:38ㆍOperatingSystem
1. 피터슨의 해결안(Peterson's Solution)
- 피터슨의 해결안은 임계구역(Critical Section) 문제를 소프트웨어적으로 해결하기 위한 알고리즘입니다.
- 현대 컴퓨터 구조가 load, store와 같은 기본적인 기계어를 수행하는 방식이기 때문에 피터슨의 해결안(소프트웨어적인 방법)은 임계 구역 문제 해결을 보장할 수 없습니다.
- 임계 구역 문제를 해결하기 위한 알고리즘적인 설명을 제공하고 상호 배제, 진행, 한정된 대기의 요구 조건을 중점으로 수행하는 소프트웨어를 설계하는데 필요한 복잡성을 잘 설명하기 때문에 피터슨의 해결안이 제시됩니다.
피터슨의 해결안은 임계 구역(Critical Section)과 나머지 구역(Remainder Section)을 번갈아 가며 실행하는 두개의 프로세스로 한정됩니다.
피터슨의 해결안은 두 프로세스가 공유하는 두개의 데이터를 필요로 합니다.
boolean flag[2];
int turn;- boolean flag[2] : 각각의 프로세스가 임계구역을 사용하고자 하는 표시입니다. 예를 들어 flag[0]==true이면 0번째 프로세스가 임계구역의 자료를 사용하고 싶다는 의미입니다.
- int turn : turn의 값은 프로세스의 차례를 의미합니다. 예를 들어 turn=0이라면 0번째 프로세스의 차례를 의미합니다.
피터슨의 해결안에서 프로세스 i의 구조는 다음과 같습니다.
do{
/* entry section */
flag[i] = true; // i번째 프로세스가 임계구역을 사용하고 싶습니다.
turn = j; // 현재 j번째 프로세스가 임계구역을 사용할 차례입니다.
// 현재 j번째 프로세스가 임계구역을 사용중
// 반복문 탈출 조건
// 1. flag[j]=false or
// 2. turn=i
while(flag[j]==true && turn==j)
{
}
/* critical section */
/* exit section */
flag[i] = false; // i번째 프로세스가 임계구역을 다 사용했기 때문에 false로 저장
/* remainder section */
}while(true)
위와 대칭되게 프로세스 j의 구조는 다음과 같을 것입니다.
do{
/* entry section */
flag[j] = true; // j번재 프로세스가 임계구역을 사용하고 싶습니다.
turn = i; // 현재 i번째 프로세스가 임계구역을 사용할 차례입니다.
// 현재 i번째 프로세스가 임계구역을 사용중입니다.
// 반복문 탈출 조건
// 1. flag[i] == false or
// 2. turn == j
while(flag[i]==true && turn==i)
{
}
/* critical section */
/* exit section */
flag[j] = false; // j번째 프로세스가 임계구역을 다 사용했기 때문에 false로 저장
/* remainder section */
}while(true)
피터슨의 해결안 예제
#include <stdio.h>
#include <pthread.h>
#define true 1
#define false 0
void* producer(void* param);
void* consumer(void* param);
int sum = 0;
int turn;
int flag[2];
int main()
{
pthread_t tid1, tid2;
pthread_create(&tid1, NULL, producer, NULL);
pthread_create(&tid2, NULL, consumer, NULL);
pthread_join(tid1, NULL);
pthread_join(tid2, NULL);
printf("sum = %d\n",sum);
}
void* producer(void* param)
{
for(int k = 0; k < 10000; k++)
{
/* entry section */
flag[0] = true; // producer 일 시작
turn = 1;
// consumer가 사용중
while(flag[1] == true && turn == 1)
{
}
/* critical section */
sum++;
/* exit section */
flag[0] = false; // producer 일 종료
/* remainder section */
}
pthread_exit(0);
}
void* consumer(void* param)
{
for(int k = 0; k < 10000; k++)
{
/* entry section */
flag[1] = true;
turn = 0;
while(flag[0]==true && turn == 0)
{
}
/* critical section */
sum--;
/* exit section */
flag[1] = false;
}
pthread_exit(0);
}실행결과
sum = 0위 실행결과는 0으로도 나올 수도 있지만 완벽한 솔루션은 아니기 때문에 약간씩 다른 값이 나올 수 있습니다. 이는 피터슨의 해결안이 소프트웨적으로 완벽히 동기화를 보장할 수 없다는 것을 알 수 있습니다.
피터슨의 해결안 완벽한 동기화를 제공하지 못하는데 제시되는 이유는 무엇인가?
- 임계 구역 문제를 해결하는 것의 좋은 알고리즘적인 설명을 제공합니다.
- 상호 배제, 진행, 한정된 대기의 요구사항과 관련된 복합적인 개념을 설명할 수 있습니다.
- 개념적으로는 완벽히 상호배제, 진행, 한정된 대기를 해결하기 때문입니다.
2. 피터슨의 해결안 증명
피터슨의 해결안이 올바르게 동작하는 것을 증명하기 위해서는 다음과 같은 사실을 보여야 합니다.
- 상호 배제가 제대로 지켜진다는 사실
- 진행에 대한 요구 조건을 만족한다는 사실
- 대기 시간이 한 없이 길어지지 않는다는 사실
상호 배제(Mutul Exclusion) 조건이란 무엇인가?
2개 이상의 프로세스가 동시에 공유자원에 접근하는 것을 예방하는 것을 의미합니다. 즉, 2개 이상의 프로세스가 임계구역에서 수행되면 안되는 조건을 의미합니다.
진행(Progress, No DeadLock) 조건이란 무엇인가?
임계구역을 이용하는 프로세스가 없고 한 프로세스가 임계구역에 들어가고자 할때 들어가게 해주어야하는 조건입니다. 만약 진행이 되지 않으면 프로세스들끼리 다른 프로세스의 해제를 기다리기 위해 계속 대기하게 됩니다. 이러한 현상을 교착상태(DeadLock)이라고 하며 진행 조건이 만족한다는 의미는 교착상태가 없어야 한다는 의미입니다.
한정된 대기(Bounded-Waiting, No Starvation) 조건이란 무엇인가?
한 프로세스가 대기중일때 우선순위가 높은 다른 프로세스에 의해 선점이 되어 계속 무한 대기를 해서는 안된다. 이렇게 다른 프로세스에게 선점되어 무한 대기하는 현상을 기아(Starvation) 현상이라고 합니다. 즉, 한정된 대기 조건을 만족하기 위해서는 기아 상태가 발생해서는 안됩니다.
두 프로세스의 상호 배제는 turn 변수에 의해서 지켜진다. 예를 들어 프로세스 i가 임게구역에 들어가기 위해서는 flag[j]==false 이거나 turn==i 이어야 한다. 하지만 turn 변수의 값은 0 또는 1이기 때문에 두 프로세스 중 하나는 while문을 통과하지 못하여 상호 배제가 지켜진다.
두 프로세스의 진행이 만족한다는 요구 조건은 두 프로세스의 교착 상태(deadlock)이 없는 상태여야 합니다. 이 역시 while문의 turn 변수에 의해 교착 상태가 없어진다. 이유는 사용하고자 하는 프로세스의 turn은 다른 프로세스의 의해서 결정되기 때문이다. 예를 들어 두 프로세스가 while문 이전에 도달했다면 두 프로세스 중 어느 하나는 turn을 늦게 저장할 것이다. 그렇다면 늦게 저장된 값의 프로세스가 while문을 벗어나 임계구역에서 수행될 것입니다.
두 프로세스의 대기 시간이 한 없이 길어지지 않는다는 사실은 어느 한 프로세스의 기아(starvation)이 없는 상태여야 합니다. 이 요구조건 역시 turn 변수가 다른 프로세스의 의해서 지정되기 때문에 기아 상태가 발생되지 않아 프로세스도 최소한 한번은 임계구역에 들어갈 수 있게 보장됩니다.
References
source code : https://github.com/yonghwankim-dev/OperatingSystem_Study/blob/main/c/chap06_process-synchronization/chap06_00_examples/6.3_peterson.c
Operating System Concepts, 7th Ed. feat. by Silberschatz et al.
[인프런] 운영체제 공룡책 강좌