[운영체제-김덕수 교수님]프로세스 동기화 & 상호배제(2/7)

상호 배제 로직 구현은 쉽지 않다.

소프트웨어적 솔루션을 배워보자

‏‏‎ ‎

Dekker's Algorithm

두개의 프로세스가 있을 때 상호 배제 구현

앞의 버전은 턴만 쓰거나, 플래그만 썼는데,

두개를 같이 써보자로 출발하였다.

1. 첫 줄에 들어가겠다는 의사 표시
  1-1. 상대가 깃발을 들고 있지 않다면, 바로 진입
  1-2. 상대가 깃발을 들고 있다면 턴을 봐야함.
    1-2-1. 상대 턴이라면 깃발을 내리고, 내 턴을 기다리고 있다.
2. 상대가 일이 끝나면 상대의 깃발을 내리고 턴을 넘긴다.
3. P0 이 일을 한다.

‏‏‎ ‎

• P0 이 뱅뱅돌다가 죽었다?
  • P0 의 플래그가 없다.
  • P1 이 들어갈 수 있다 => Progress 해결
• P0 도 플래그가 세워졌고 P1 도 플래그가 있다?
  • 나의 턴을 기다린다.

‏‏‎ ‎

양보의 개념이 추가되었다. 훈훈하다.

N-Process Mutual Exclusion

두개를 했다면 N 개도 해야 한다. 그것이 공학자니까(_끄덕)

‏‏‎ ‎

‏‏‎ ‎

깃발을 3단계로 쪼개는 개념이다. (idle:: 갈의사 없음, want-in:: 의사 있음, in-CS:: 거의 임박)

idle 에서 want-in 으로 의사표시

턴을 살핀다.

1단계에선 2단계로 올라가기 위해

=> (내가 아니면) 지금 턴인 프로세스가 깃발을 내릴 때까지 기다린다.

• 자기 턴을 만들고 그 다음 루프에서 다음 와일문으로 넘어갈 수 있으므로, 여러 프로세스가 2단계에 있을 수 있다.
• 자신의 깃발을 in-CS로 변경한다.

2단계에선 in - CS 를 일종의 방이라고 생각하면,

• J 가 N보다 작을 때까지 (그리고) ( 나이거나 flag[j] 가 in-CS 가 아니면)
  • J += 1
  • 무슨 로직인지 모르겠다.
  • 결론만 말하면 in-CS 상태에 나혼자 있을 때까지 와일문을 돌린다.

=> in - CS 에 자리하는 프로세스가 여러개 (n 개) 있다고 했을 때, 그 방에서 N개가 자기 자신 (1) 이 될때까지 기다리는 로직이다.

• 요약
  • 운이 없다면 1단계, 혹은 2단계에서 뱅뱅이를 돌 수 있으나, 반드시 한번은 CS에 입장할 수 있다.

‏‏‎ ‎

SW Solution

• 문제점
  • 속도가 느림
  • 구현이 복잡함
  • ME primitive 실행 중 preemption 될 수 있음
    • 공유 데이터 수정은 interrupt를 억제 함으로서 해결 가능
      • overhead
  • Busy waiting
    • 비효율적