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

출처 : https://www.youtube.com/watch?v=lY43KR3IItw&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=13

 

 

 

 

Dekker's Algorithm

 

• Two process ME을 보장하는 최초의 알고리즘
• 이전에 사용했던 턴 과 깃발을 둘 다 사용하는 알고리즘
• 내가 도달하게 되면 깃발을 True로 만든다. 이때, 상대방의 깃발이 False라면 바로 CS에 진입한다.
• 만약 상대방의 깃발이 True라면, 턴이 내 턴인지, 상대방의 턴인지 확인한다. 만약 내 턴이면 CS에 진입한다.
• 만약 상대방의 턴이라면 깃발을 내리고 상대방의 턴이 끝날 때까지 (내 턴이 올때까지) 기다린다. 내 턴이 오면 CS에 진입하고 나온 뒤에 상대방에게 턴을 넘기고 깃발을 내린다.

1. 앞선 version 들에서의 문제점 확인

 

턴이 P0의 턴인데 repeat에서 죽어버린 상황에서 P1이 먼저 도착한다. 그러면 P1의 깃발을 올리고 P0의 깃발이 내려가 있으므로 바로 CS에 진입할 수 있다. 

고로 Progress는 만족한다.

 

또한 둘 다 깃발을 들고 있는 상황에서도 안에서 턴을 한번 더 확인함으로써 Mutual exclusion, bounded wait 문제 또한 해결할 수 있다.

 

 

Peterson's Algorithm

 

• Dekker's algorithm을 보다 간단하게 구현
• 프로세스가 도착하면 상대방에서 턴을 양보한다.
• 고로 늦게 도착한 애가 상대방에서 턴을 양보함으로써 먼저 도착한 프로세스가 먼저 CS에 도착하게 된다.

 

 

여러 개의 프로세스가 있을 때의 Mutual exclusion을 해결하는 많은 기법들이 존재한다.

 

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

 

 

Dijkstra's algorithm

 

3개의 state를 가진 깃발을 사용한다.

 

idle : 프로세스가 임계 지역 진입을 시도하고 있지 않을 때 (CS에 들어갈 생각이 없음)

want-in : 프로세스의 임계 지역 진입 시도 1단계일 때 (CS에 들어가고 싶다는 의사를 밝힘)

in-CS : 프로세스의 임계 지역 진입 시도 2단계 및 임계 지역 내에 있을 때 (거의 진입하기 직전)

 

 

각 프로세스마다 깃발을 가지고 있고 턴이 존재한다.

 

2 단계의 CS 진입시도 단계를 가지고, 이 단계들을 거친 뒤에 CS에 진입하게 된다.

 

1단계

깃발의 state를 want-in으로 변경한다. 그 다음, 턴이 내 턴인지 확인한다. 만약 현재 턴인 프로세스의 깃발의 state가 idle이라면(현재 작업 중인 프로세스의 작업이 끝나면) 내 턴으로 만든다.  즉, 내 턴이 될 때까지 기다리겠다.

 

2단계

여러 프로세스들 또한 2단계에 진입을 할 수도 있으므로 j라는 변수를 만든다.

j = 0에서 출발해서 j가 n이 될 때까지 in-CS상태가 나만 있으면 CS에 진입하고 그렇지 않으면 맨 처음 단계(want-in)로 돌아간다.

 

 

SW Solutions

 

• SW solution들의 문제점
  • 속도가 느림 (계속 반복문을 돌기 때문에 비효율적임)
  • 구현이 복잡함
  • ME primitive 실행 중 preemption 될 수 있음
    • 공유 데이터 수정 중은 interrupt를 억제 함으로서 해결 가능
      • overhead 발생
  • Busy waiting (반복문의 조건문에서 우리는 아무것도 안하고 기다르는 것과 같지만, 실제로는 계속 조건을 확인하면서 반복문을 돌고있다.)
    • Inefficient