상호배제 방법들(알고리즘)

🌞 데커 알고리즘

🌞 피터슨 알고리즘

• flag 변수와 turn 변수를 and 연산을 통해서 while문에 들어가게 만들어 주었다. 이렇게 함으로써 만약에 flag, turn 중이 하나라도 통과하지 못하면 while문을 통과하게 된다. 즉 turn값이 while문을 들어가는 것을 막는다 하더라도 flag가 false라면 임계영역에 들어 갈 수 있게 된다.

🌞 다익스트라 알고리즘

• 최초로 프로세스 n개의 상호배제 문제를 소프트웨어적으로 해결함

• 가장 짧은 평균 대기 시간을 제공한다.

• 하지만 한정대기의 문제를 해결하지 못하였다. 누군가는 굶는 상태를 가진다.

🌞 기타

• Knuth's Algorithm for n processes

• Debrujin's Algorithm for n processes

🌞 Lamport's bakery algorithm

• 베이커리(빵집) 알고리즘

• 준비 상태 큐에서 기다리는 프로세스마다 번호표를 주고 번호표 순으로 프로세서를 할당한다.

• 프로세스는 i번째의 순서표를 가지고 있는 녀석이 임계영역을 차지하기를 바란다. 이 경우에 들어갈 수 있는 경우는 number 영역을 모두 살펴 봤을 때, 내가 순번이 가장 작거나 나머지 애들이 모두 0 인경우이다. 이를 while문과 for문을 통해서 해결한다.

• 바쁜대기의 문제를 해결하지는 못하였다.

🌞 TAS 명령어

• 검사와 수정을 원자적으로 하는 하드웨어 명령어 if문 lock변수의 값을 atomic하게 검사를 하여 while문을 통과하는 프로세스가 하나가 되게끔 한다.

• 한정대기가 불가능 하다. / busy waiting 존재

• 한정대기가 불가능한 문제를 기아 상태라고 한다.