[운영체제] Peterson's Algorithm(피터슨의 알고리즘)

Peterson's Algorithm은 1981년 수학자였던 개리 피터슨이라는 사람이 고안한 알고리즘이다. 발표 당시 이 알고리즘에서는 오직 두 개의 프로세스에만 적용 가능하다고 했었지만 지금은 2개 이상의 프로세스들 사이에서도 이 방법이 통용된다. Lock 방식이 지니고 있는 문제점을 해결하기 위해 고안된 알고리즘이라 볼 수 있다.

Peterson's Algorithm 구조

여러 개의 프로세스가 있을 때, i번째 프로세스의 Peterson 알고리즘 구조도

// flag: 신호, 공유자원을 사용하고 싶다라고 표현하기 위한 변수, 임계구역에 들어갈 때는 true, 나올 때는 false로 설정
// turn: 차례, 누구 차례인지를 명시하는 변수, turn = 0 이면, 0번째 프로세스가 임계 구역에 들어가고, 1번째 프로세스가 기다린다.
bool flag[2];
int turn;

while(true) {
    // i번째 프로세스가 공유자원을 사용하고 싶다는 신호를 전달하기 위해 flag를 true로 바꿔준다.
    flag[i] = true;

    // i 번째 프로세스가 쓰기 전에 먼저 쓰고 싶어했던 프로세스가 있는지 확인하고 수행시켜주는 코드
    // 예를 들어 j번째 프로세스가 이 공유 자원을 쓰고 싶어 했으면 i번째 프로세스는 j번째 프로세스에 차례를 양보한다.
    turn = j;

    // busy waits 상태. turn이 j일 경우, 내 차례가 아니고 j가 자원까지 쓰고 싶어하면 나는 spinlock에 머무른다.
    // 이제 내 차례거나 j가 자원을 쓰고 싶지 않은 경우(!flag[j]), spinlock을 빠져나와 임계 구역에 진입할 수 있다.
    //turn과 flag를 통해 동시 접근을 막는다.
    while(flag[j] && turn == j);

    // critical section
    // 임계 구역에 진입해서 작업을 한다.

    flag[i] = false; // 다 썼으면 flag를 false로 바꿔준다.

    //remainder section
}   

Peterson 알고리즘이 임계구역 해결조건 3가지 만족

1. mutual Exclusion(상호 배제) : 각각의 프로세스는 공유 자원에 접근하기 위해 나 외에 다른 프로세스가 기다리지 말거나 자신의 차례여야 한다. 다시 말해서, 자기 순서가 아니면 아무도 접근하지 못한다. Peterson 알고리즘에서 turn 변수를 이용하는데, turn이 i와 동시에 j일 수는 없으니 1번 조건은 만족한다.
2. Progress(진행) : 내 순서가 아니라도 남들이 쓰지 않으면 공유 자원을 쓸 수 있다. Peterson 알고리즘에서 i번째 프로세스는 실행 완료 이후 flag[i]를 false로 만들기 때문에 2번째 조건 역시 만족한다.
3. Bounded-waiting requirement(한정 대기) : 자원을 요청하는 프로세스가 영원히 대기하지 않게 하는 것인데, flag[j]가 0이 되면서 적어도 한번은 i번째 프로세스가 실행할 수 있게 기회를 주는 것이기 때문에 역시 3번째 조건도 만족한다.

참고자료

https://haun25ne.tistory.com/59

11100. 피터슨 알고리즘 : 조건 3개에 맞는거야?

 

https://jhnyang.tistory.com/37?category=815411 

[운영체제]임계영역 해결조건 & Peterson's solution(피터슨 알고리즘)