Algorithm] 피터슨 알고리즘(Peterson's algorithm) 이해하기

피터슨 알고리즘은 임계 영역을 해결하기 위한 알고리즘인데, 이를 이해하기 위해서는 교착 상태와 임계 영역에 대한 이해가 필요하다.

• 교착 상태 (Dead lock)
  • 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때 무한 대기에 빠지는 상황
  • Ex) A,B = 프로세스(Process) 노트, 연필 = 자원(공유자원, Shared Resource)

• 임계 영역 (Critical Section)
  • 공유자원(Ex. 연필, 노트)에서 문제가 발생하지 않게 독점을 보장해줘야 하는 영역

(위 예시에서는 노트필기)

• 임계 영역의 해결방안
  • 상호 배제 : 한 프로세스가 임계 영역에 들어갔을 때 다른 프로세스는 들어가지 마!
  • 한정 대기 : 그렇다고 한 프로세스가 영원히 못들어가도 안되지,, 대기는 유한하게 해!
  • 진행 or 융퉁성 : 임계 영역에 들어간 프로세스가 없는 상태에서, 들어가려고 하는 프로세스가 여러 개 있다면 어느 것이 들어갈지를 적절히 결정해주어야 하는데,,, 어쩌지?

에서 나온 아이디어들이 바로 데커 알고리즘(Dekker’s algorithm), 피터슨 알고리즘(Peterson’s algorithm) 등등이다. 사실 피터슨 알고리즘은 데커 알고리즘과 비교하면 구분하기 편하지만 여기에서는 피터슨 알고리즘만을 다뤄보도록 하자

Then, What is Peterson’s algorithm?

To be Updated...