6. 프로세스 동기화 & 상호배제 (2) - sw solutions

1. Dekker's Algorithm

데커스 알고리즘

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

데커스 알고리즘 : flag와 turn의 개념을 혼합해서 사용함으로써 앞서 언급된 조건 3가지를 모두 부합시킴

• flag, turn을 모두 사용함

[로직]

1. 현재 내 flag를 true로 변경
2. 만약 상대 flag가 True라면, 턴 값을 확인해서 누구의 턴인지 확인
   1. 만약, 상대 턴이면 내 flag를 false로 만들고 상대 턴이 끝나서 trun value가 0이 될 때까지 대기
   2. turn이 0이 되면 flag를 true로 변경하고 CS로 진입
3. 만약 상대 flag가 False라면, 빠로 CS로 진입
4. CS를 빠져나온 후, turn 값 변경 및 flag 변경

2. Peterson's Algorithm

Dekker's algorithm과 다른 점은 서로 양보하는 것

피터슨 알고리즘 : 데커스 알고리즘을 조금 더 간소화 시킴

[로직]

1. 내 flag를 true로 변경
2. turn 값에 상대의 값을 넣음
3. 상대가 끝날 때까지 기다림.
4. 상대가 끝나고 내 turn이 되면 CS 진입
5. CS 빠져나와서 내 flag를 false로 변경

3. 다익스트라(Dijkstra)

N-Process Mutual Exclusion (프로세스가 n개인 경우의 ME)
ex. 다익스트라, 크누스, 램포트, 핸슨이 있지만 ! 다익스트라만 언급하고 넘어가서 ^^ 추후에 찾아서 추가하겠습니다.

• 최초로 프로세스 n개의 상호배제(ME) 문제를 소프트웨어적으로 해결
• 실행 시간이 가장 짧은 프로세스에 프로세서 할당하는 세마포 방법, 가장 짧은 평균 대기시간 제공

(1) Dijkstra 알고리즘의 flag[] 변수

Dijkstra 알고리즘에 사용되는 flag의 경우 3가지 state가 존재함

DIjkstra는 크게 2step으로 나눌 수 있습니다.

4. SW solution들의 문제점

• 속도가 느림, 비효율적 (while문 사용으로 인한 문제)
• 구현이 복잡함
• ME primitive 실행 중 preemption될 수 있음
  • 공유 데이터 수정 중은 interrupt를 억제함으로써 해결 가능
    • overhead 발생
• Busy waiting : 기다리는데 뺑뺑 돌면서 기다리는 것 (while문 사용으로 인한 문제)
  • 비효율적