병행 프로세스와 상호배제(2/2)

3. 상호배제 방법들

1. 데커의 알고리즘

데커의 알고리즘은 두 프로세스가 동시에 임계 영역에 진입하려고 시도하면 순서에 따라 오직 하나만 임계 영역에 들어가도록 허용한다. 하지만 프로세스 2개가 동시에 임계 영역에 진입하도록 플래그를 설정하면 교착 상태가 발생할 수 있다.

//프로세스가 공유하는 데이터//
int turn;
bool flags[2];
//////////////////////////////
 
void main()
{
    flags[0] = false;
    flags[1] = false;
    turn = 0;                                            //Shared Variable 0 또는 1
 
    //Process P0                                        //프로세스 P0의 임계 영역 진입 절차
    /*①*/flags[0] = true;                                //P0의 임계 영역 진입 표시
    /*②*/    while (flags[1] == true)                    //P1의 임계 영역 진입 여부 확인
            {                                            
                if (turn == 1)                            //P1이 진입할 차례가 되면
                {
                    /*④*/flags[0] = false;                //플래그를 재설정하여 P1에 진입 순서 양보    
                    /*⑤*/while (turn == 1) {}            //turn을 바꿀 때 까지 대기(바쁜 대기)
                }
                flags[0] = true;                            //P1이 임계 영역에 재진입 시도
            }
    /* ③임계 영역 */
    turn = 1;                                            //P1에 진입 순서 제공
    flags[0] = false;                                    //P0의 임계 영역 사용 완료 지정
    /* 나머지 영역 */                                    //P0의 나머지 영역 수행
 
    //Process P1
    flags[1] = true;
    while (flags[0] == true)
    {
        if (turn == 0)
        {
            flags[1] = false;
            while (turn == 0) {}        
            flags[1] = true;
        }
    }
    /* 임계 영역 */
    turn = 0;
    flags[1] = false;
    /* 나머지 영역 */
}

①에서는 P0은 flags[0]을 true로 설정하고, 자신이 임계 영역으로 들어간다는 사실을 알린다. 그리고 ②에서 while 문을 검사하여 P1의 임계 영역 진입 여부를 확인하다. p1의 flags[1]이 flase이면 ③P0가 임계 영역으로 진입하고, true이면 ④P1이 임계 영역에 진입할 차례라서 플래그를 false로 재설정한 후 ⑤while 문에서 순환하며 대기한다. 여기서 공유변수 turn은 두 프로세스 P0와 P1이 동시에 임계 영역으로 들어가려고 충돌하는 것을 방지한다.

데커의 알고리즘의 특징

• 특별한 하드웨어 명령문이 필요 없다.
• 다른 프로세스들이 임계 영역에 들어가려는 것을 막지 않는다.
• 임계 영역에 들어가기를 원하는 프로세스를 무한정 기다리게 하지 않는다.

2. TestAndSet(TAS) 명령어

메모리 영역의 값에 대해 검사와 수정을 원자적으로 수행할 수 있는 하드웨어 명령어 TestAndSet을 이용하여 간단한 방법으로 임계 영역 문제를 해결할 수 있다. TestAndSet 명령어는 하드웨어에서 명령을 사용하므로 알고리즘이 간단하고 공유 변수를 수정해서 발생하는 경쟁 상황을 해결할 수 있다. 이 알고리즘에는 기계 명령어가 2개 있다. 하나는 원자적 연산 명령어인 TestAndSet이고, 다른 하나는 TestAndSet에 지역변수 lock을 설정하는 명령어이다.

bool lock;
 
//target을 검사고, target값을 true로 설정
bool TestAndSet(bool *target)
{
    bool temp = *target;                        //이전 값을 기록
    *target = true;                                //true로 설정
    return temp;                                //값 변환
}
 
void main()
{
    do
    {
        while (TestAndSet(&lock))            //lock을 검사하여 true이면 대기, false이면 임계 영역 진입
        {}                                        //아무것도 하지 않음
                //임계 영역
        lock = false;                            //다른 프로세스 진입을 허용 할당한다는 의미로 lock을 false로 수정
                //나머지 영역
    } while (true);
}

TestAndSet명령어의 장점과 단점

장점

• 구현이 단순하고 확인이 용이하다.
• 다중 임계영역을 지원한다.  

단점

• 바쁜 대기 발생(바쁜 대기란 while llop에서 P0가 임계영역을 벗어날 때까지 계속 TestAndSet()함수를 체크해야함을 의미)
• 기아 상태 발생: 프로세스가 임계 영역을 떠날 때 프로세스 하나 이상이 대기하는 경우 발생할 수 있다.

3. 세마포(Semaphore)

데커 알고리즘과 TAS알고리즘은 진입 조건이 true가 될 때까지 반복적으로 조사하고 바쁜 대기를 하게 되어 프로세스를 낭비한다. 진입조건을 반복 조사하지 않고 true일 때 프로세스 상태를 확인한다면 프로세서 사이클을 낭비하지 않을 것이다. 다익스트라는 세마포를 제안하여 이 문제를 해결하였고 세마포는 상호배제에 사용될 뿐만 아니라 다양한 연산의 순서를 제어하는 대도 사용된다.

* 세마포의 개념과 동작

세마포 값은 true나 false로, P와 V연산과 관련되어 있다. 네덜란드  P는 검사(Proberen)를 의미하고 V는 증가(Verhogen)를 의미한다. 세마포를 의미하는 S는 표준 단위 연산 P(프로세스를 대기하게 하는 wait 동작으로, 임계 영역으로 진입하는 연산)와 V(대기 중인 프로세스를 깨우려고 신호를 보내는 signal 동작으로, 임계 영역에서 나오는 연산)로만 접근하는 정수변수이다.

* 세마포 P(S), V(S)연산의 정의

//P(S) = wait연산
if (S > 0)
    S = S - 1;
else
    wait on Qs(Queue);

//B(S) = Signal연산
if (∃wating Process on Qs)
    Wake Up One Of Them;
else
    S = S + 1;

세마포가 0일 때 lock 또는 미사용 중이고, 양의 값은 세마포를 사용할 수 있다는 의미이다. 세마포는 음의 값을 가질 수 없다. 임계 영역은 보통 세마포를 사용하여 1(처음 들어가는 프로세스를 위해서)로 초기화한다. 세마포를 0으로 초기화 하면 스케줄링 제한에 사용할 수 있어 모든 프로세스가 wait(S) 호출을 기다리는 동안 차단된다.

*세마포를 프로세스에 적용하는 방법

do
{
    wait(mutex);
        //임계 영역
    signal(mutex);
        //나머지 영역)
}while(1);

* 생산자 - 소비자 문제(Producer-Consumer Problem)

정상적인 경우, 완전히 꽉 찬 경우, 완전히 비어있는 경우를 세마포를 이용하여 통제한다.

//(Shared Variable)
var nrFull        : semaphore = 0;
var nrEmpty        : semaphore = N;
var mutexP        : semaphore = 1;
var mutexC        : semaphore = 1;
var buffer        : array[0, 1, ···, N - 1] of Messages;
var in, out        : 0, 1, ···, N - 1 : 0, 0    //(in과 out의 처음은 0)

//Producer i
Create a New Message M;
P(mutexP);
P(nrEmpty);
buffer[in] <- M;
in <- (in + 1) mod N;
V(nrFull);
V(mutexP);
......
until false;