OS이야기 - 분산 조정

상호 배제

상호 배제 구현을 위한 알고리즘들에 대해 알아본다.

중앙 집중식 접근

하나의 프로세스가 임계 구역으로의 진입을 조정하는 역할을 전담하도록 함으로써 상호 배제를 구현한다.

조정자는 요청 메세지를 받으면, 임계 구역에 다른 프로세스가 있는지를 검사한다. 임계구역을 실행중인 프로세스가 없으면, 조정자는 응답 메세지를 바로 보낸다. 그렇지 않으면 요청은 메세지 큐에서 대기해야 한다. 조정자가 해제 메시지를 받으면 큐에서 대기중인 요청들 중 하나를 제거한 후 그 요청의 해당 프로세스에게 응답 메세지를 보낸다. 대기중인 요청들 중 하나늘 선택하는 작업은 스케줄링 알고리즘을 따른다.

완전 분산형 접근

프로세스 P1가  임계 구역에 들어가고자 할 때, 그 프로세스는 새로운 타임스탬프 TS를생성하고, 자신을 포함한 시스템 내의 모든 프로세스에게 request(P2,TS) 메시지를 보낸다. 프로세스는 요청 메시지를 받게 되면 즉시 응답을 하거나 또는 자신이 이미 임계 구역 안에 있으면 응답을 보류한다. 

1. p1이 임계구역에 잇으면, p2에 대한 응답을 보류한다.

2. p1이 임계구역에 없으면, p2에 즉시 응답을 보낸다.

3. p1이 임계구역에 접근하려고 할때, p2도 접근하려고 하려면, TS를 비교한다.

두 단계 확약 프로토콜 (Two-Phase Commit Protocol)

-