유튜브 링크

---

진구

저번 강의의 문제를 해결한 데커 알고리즘과 다익스트라 알고리즘 등장
눈으로 보면 쉬운데 되는 케이스 엣지 케이스 손으로 해보면 더 이해가 잘 될듯

내일 회사에서 쉬는 시간에 한번..?

---

세영

Mutual Exclusion Algorithms

Dekker’s Algorithm

• 2 process mutex를 보장하는 최초의 알고리즘
• bool flag[2], int turn
• Solution
  1. 나 사용할거임 (flag[me] = true)
  2. 상대가 사용하는지? (while flag[other])
     1. 사용중이면 아래 작업 반복
        1. 지금 상대 턴이면 나 사용 안할거임 (flag[me] = false)
        2. 상대 턴 끝날 때 까지 대기 (while turn == other)
        3. 상대 턴 끝나면 다시 나 사용할거임 (flag[me] = true)
     2. 아니면 바로 프로세스 실행
  3. 프로세스 실행… → Critical Section
  4. 다 썼으니 이제 니 턴임 (turn = other; flag[me] = false)
• Simplify (양보하며 살자)
  1. 나 사용할건데 그 전에 양보 한 번 해준다 (flag[me] = true; turn = other)
  2. 상대가 사용 중이고 상대 턴이면 대기 (while flag[other] and turn == other)
     1. 하나라도 만족 안 하면 내가 쓸거임
  3. 프로세스 실행…
  4. 다 썼다 (flag[me] = false)

Dijkstra’s (Mutex) Algorithm

• n process mutex를 보장하는 최초의 알고리즘
• flag state가 3개 (진입 관심 없음(idle), 들어가고 싶다(want-in), 들어간다(in-CS))
• Solution
  1. 나 들어가고 싶어
  2. (임계 지역 진입 시도 1단계) 내 턴이 아니면 지금 사용중인 작업이 idle이 될 때까지 기다림
     1. idle 되면 내 턴임
  3. (임계 지역 진입 시도 2단계) 나 이제 들어간다? (in-CS)
     1. 들어가기 전에 나랑 똑같은 상태(in-CS) 있으면 다시 1번으로 감
  4. 프로세스 실행…
  5. 나 이제 다 썼다 ㅂㅂ

---

지금까지의 문제점

• 반복문이 있어서 느리고, 구현이 쉽지 않음
• 코드는 한 줄이라도 명령어는 여러 줄이 생길 수 있는데, 그러면 값이 정확하지 않을 수 있음
• Busy waiting: while문으로 계속 기다리는 것