Software Solutions

프로세스 2개의 상호배제

Dekker's Algorithm

Two process ME를 보장하는 최초의 알고리즘

flag 와 turn을 둘 다 사용하는 알고리즘
flag를 들어 작업을 하겠다는 의사를 밝히고,
자신의 turn이 되었을때 작업을 시작한다

Dekker's 알고리즘은 보다 간단하게 구현할 수 있다.
차이점은 2번째줄. turn을 상대에게 양보한다. 즉 늦게 양보한 프로세스가 나중에 처리된다

프로세스 n개의 상호배제

다익스트라 알고리즘

(다익스트라는 여러 알고리즘을 제시한 인물로, 다익스트라 알고리즘이라 할때 이 알고리즘만 명칭하는것이 아님)
최초로 n개 프로세스 상호배제 문제를 소프트웨어로 해결

다익스트라 알고리즘의 flag[]변수

idle: 프로세스가 임계 지역 진입을 시도하고 있지 않을 때
want in: 프로세스의 임계 지역 진입 시도 1단계일 때
in cs: 프로세스의 임계 지역 진입 시도 2단계 및 임계 지역 내에 있을 때

임계 지역 진입 시도 1단계

1. flag를 want in으로 바꿔 임계지역 진입을 원한다고 알림
2. 자신의 turn이 아닐때, 현재 turn인 프로세스가 끝날때까지(flag가 idle이 될때까지) 대기
3. 현재 turn이였던 프로세스가 끝날때, turn을 자신것으로 바꾸고, 2단계로 진입한다.

임계 지역 진입 시도 2단계

1. flag를 in cs로 바꾸어 2단계에 진입하였음을 알린다
2. 루프를 위한 변수 j를 0으로 설정한다.
3. j를 이용하여, 자신을 제외한 다른 프로세스가 in cs가 아닌지 검사한다.
4. 만약 in cs가 자신 혼자뿐이라면, 임계지역 진입. 아니라면 다시 1간계 시작부분으로 돌아간다.

실행 순서에 따라 좀 헤메서 갈 수도 있지만, 상호배제가 보장된다.

SW Solutions들의 문제점

1. 속도가 느림
2. 구현이 복잡함
3. ME primitive(상호배제 기본연산) 실행 중 preemption(선점)될 수 있음
   (공유 데이터 수정 중은 interrupt를 억제함으로서 해결 가능하지만 overhead 발행)
4. busy waiting(반복문을 돌며 기다려야 한다)