OS를 공부하면서 정리를 한 내용들 입니다.

critical section에 들어가기 전과 나오는 부분의 section에서 어떤 알고리즘을 사용해야 하는가에 대해 알아봅시다.

첫 번째 알고리즘은 접속 하려할 때와 접속이 끝났을 때 건너편의 프로세스가 서로 양보하는 형식의 방식을 사용했습니다.

두 번째 알고리즘에 대해 알아봅니다.

Algorithm 2

이번 방식에서 변수를 하나 사용을 하는데 flag 라는 변수를 사용합니다.

Synchronization variables

boolean flag[2];

초기 flag[전부] = false; /*둘 다 critical section에 있는 상태는 아님*/

Process Pi, Process Pj

do{
    flag[i] = true; /*Pretend I am in*/
    while(flag[j]);  /*Is he alseo in? then wait*/
    critical section
    flag[i] = false; /*I am out now*/
    remainder section
}while(1);

위는 Pi의 입장에서 본 모습입니다.

만약 Pi가 critical section에 들어가고자 한다면 flag[i]를 true로 만듭니다.

그런 다음 상대방 flag를 확인합니다.

상대방의 flag가 true라면 critical section을 사용 중 이거나 사용하려 하는 것을 인지하고 대기 하게 됩니다.

만약 상대방의 flag가 false라면 critical section을 사용합니다.

이후 나오게 된다면 해당 프로세스의 flag[i]를 false로 바꿔줍니다.

알고리즘의 문제점

프로세스 Pi가 본인의 flag를 true로 바꾼 상태입니다.

그런 상황에서 Pi가 CPU를 빼았깁니다.(문제 발생)

Pj의 입장에서 Critical section을 사용하고 싶을 때, flag[j]는 true로 변경하고 나서,

flag[i]는 true인 상태이기에 while문이 동작하는 상태로 대기를 하는데,

다시 Pj에게서 Pi로 CPU가 돌아왔을 때 둘 다 대기하게 됩니다.

즉, flag가 false로 되지 못하는 상황이 되어 문제가 발생하게 됩니다.

Algorithm 3(Peterson’s Algorithm)

해당 방식은 Algorithm 1과 Algorithm 2에서 사용했던 두개의 동기화 변수를 합한 형태입니다.

Process Pi

do{
    flag[i] = true; /*My intention is to enter...*/
    turn = j; /*Set to his turn*/
    while( flag[j] && turn == j );  /*wait only if...*/
    critical section
    flag[i] = false;
    remainder section
}while(1);

flag를 이용해서 CS(critical section)에 들어가겠다는 의사를 표현하고,

turn을 상대방으로 돌려놓습니다.

들어가기전에 확인을 하는데 상대방이 flag를 true로 상태이면서 상대방의 차례인 2 가지를 만족한 상태라면,

상대방이 사용하거나 사용하겠다는 의사고 아니라면 상대방은 관심이 없는 상태입니다.

상대방이 flag를 true라고 했더라도, 차례가 내 차례라면 나는 CS에 들어가게 됩니다.

이 방법은 모든 경우의 수를 따져서 중간에 CPU를 빼앗긴다 하더라도

상호 배제(Mutual Exclusion), 진행(Progress), 유한 대기(Bounded Waiting) 3가지 조건에 모두 만족하게 됩니다.

알고리즘의 문제점

Busy Waiting( = spin lock)

만약 어떤 프로세스가 CS에 들어가 있는 상태에서 CPU를 다른 프로세스에게 빼앗긴다면 while문을 돌게 됩니다.

이때 본인의 CPU 할당 시간동안 계속 확인을 하는데 확인을 계속하더라도 상대방이 바꿔줘야 문제가 해결이 됩니다.

만약 상대방이 바꿔주지 않는다면 할당 시간동안 while문만 돌다가 할당 시간이 끝이나게 됩니다.

-참고 KOCW 이화여자 대학교 반효경 교수님 : 운영체제 강의