[OS] 6. 프로세스 동기화 - Mutual Exclusion SW Solution

어떻게 하면 상호배제가 잘 작동하는 알고리즘을 만들 수 있을까? 

Mutual Exclusion Solutions

• SW solutions
  
  • Dekker’s algorithm (Peterson’s algorithm)
  • Dijkstra’s algorithm , Knuth’s algorithm, Eisenberg and McGuire’s algorithm, Lamport’s algorithm
• HW solution
  
  • TestAndSet (TAS) instruction
• OS supported SW solution
  
  • Spinlock
  • Semaphore
  • Eventcount /sequencer
• Language Level solution
  
  • Monitor

 

Dekker’s Algorithm

Two process일 때 ME(상호배제) 을 보장하는 최초의 알고리즘

앞서 프로세스 동기화에서 flag과 turn을 하나만 사용해서 상대편에서 CS를 점유할 것인지 알려주었다.

이렇게 하면 ME primitive를 만족하지 못한다

이를 해결하고자 하는 방법이 Dekker 알고리즘이다.

1. P0에서 CS를 점유하고 싶다고 flag[0] = True로 변경함
2. while문에서 상대편이 깃발을 들고 있다면(flag[1]==True) 조건문 참이므로 while문으로 진입
3. P1이 깃발을 안 들고 있다면? P1은 일을 하지 않음을 알고 P0가 CS에 들어갈 것이다
4. P1이 깃발을 들고 있다면? P0은 while문으로 진입한다.
5. 상대편 턴이라면? turn=1
6. 내 깃발(flag[0]을 내림)
7. 상대편이 CS에서 나오면서 flag[1]로 변경을 하고 P0은 flag[0]이 true가 되었으므로 while을 벗어나서 CS에 진입하게된다. 

이 알고리즘은 어디에서 Preemption이 걸려도 ME에 위배되지 않음.

 

Peterson’s Algorithm

Dekker’s algorithm 보다 축약해서 간단하게 구현할 수 있다.

P1이 실행되지 않으면 P0는 while문을 만족하지 않으므로 CS에 바로 진입하게 된다. P1도 마찬가지..

아래의 경우는 P0이 Turn = 1 에서 preemption이 걸렸을 때 어떻게 알고리즘이 작동되는지 살펴봄.

1. P0이 CS에 진입하기전에 flag[0] =  True, Turn = 1로 만든다. 
2. P0은 while문에 진입하기전 preemption이 걸림.
3. P1이 CS에 진입할 때 flag[1] = true, turn =0으로 만듦.
4. P1은 flag[0] = true, turn=0이므로, while문을 만족하므로 계속 대기하게됨.
5. preemption으로 멈춰있던 P0가 다시 작업을 수행함. flag[1] = true, turn = 0이므로 while문을 만족하지 않음
6. P0은 CS에 진입함.
7. CS에 벗어난 P0은 flag[0] = false로 만듦.
8. while문을 돌고있던 P1은 flag[0]이 false가 되므로 while문을 만족하지않음
9. P1은 CS에 진입하고 flag[1] = false로 만들고 종료됨.

마찬가지로 이 알고리즘은 Dekker’s algorithm와 마찬가지로 어디에서 Preemption이 걸려도 ME에 위배되지 않음.

 

만약 여러개의 ME를 해결하기 위해 어떤 알고리즘을 사용해야 할까?

• 다익스트라 Dijkstra
  
  • 최초로 프로세스 n 개의 상호배제 문제를 소프트웨어적으로 해결
  • 실행 시간이 가장 짧은 프로세스에 프로세서 할당하는 세마포 방법 , 가장 짧은 평균 대기시간 제공
• 크누스 knuth
  
  • 이전 알고리즘 관계 분석 후 일치하는 패턴을 찾아 패턴의 반복을 줄여서 프로세스에 프로세서 할당
  • 무한정 연기할 가능성을 배제하는 해결책을 제시했으나 , 프로세스들이 아주 오래 기다려야 함
• 램포트 lamport
  
  • 사람들로 붐비는 빵집에서 번호표 뽑아 빵 사려고 기다리는 사람들에 비유해서 만든 알고리즘 (Bakery algorithm)
  • 준비 상태 큐에서 기다리는 프로세스마다 우선순위를 부여하여 그 중 우선순위가 가장 높은 프로세스에 먼저 프로세서를 할당함
• 핸슨 brinch Hansen
  
  • 실행 시간이 긴 프로세스에 불리한 부분을 보완하는 것
  • 대기시간과 실행 시간을 이용하는 모니터 방법
  • 분산 처리 프로세서 간의 병행성 제어 많이 발표

여러 알고리즘 기법들이 있지만 해당 포스트에서는 다익스트라 알고리즘에 대해 정리하였다.

 

Dijkstra’s Algorithm

앞서 두 알고리즘에서는 flag라는 깃발을 들거나 내리는 정의밖에 없는데 이 알고리즘에서는 3개의 값을 가지고 있다.

 

Dijkstra 알고리즘의 flag[] 변수

flag[] 값	의미
idle	프로세스가 임계 지역 진입을 시도하고 있지 않을
want-in	프로세스의 임계 지역 진입 시도 1 단계일 때
in-CS	프로세스의 임계 지역 진입 시도 2 단계 및 임계 지역 내에 있을 때

1. 1단계에서는 CS에 들어가고 싶다고 의사를 표현한다.
2. turn이 내가 아니면 기다린다. (현재 턴을 가지고 있는 프로세스가 idle이 될 때까지 while문에서 기다림)
3. 끝나는 순간 turn을 내꺼로 가져오고 while문을 벗어나고 2단계로 진입함.
4. turn을 뺐었는데 2단계로 진입하기 전에 다시 뺐길 수 있다. 그러면 또 while문을 반복하게됨.
5. 여러 프로세스가 2단계로 들어오면 while문을 만족하지 않아 J값이 n보다 작아지게 되고 1단계로 돌아감
6. 만약 프로세스 1개가 in-CS에 존재한다면 j는 계속 값이 증가해서 j가 n보다 커지게 되고 CS에 들어가게됨.

• 결국 2단계에서 in-CS에 1프로세스만 들어가는 것을 보장 할 수 있어 ME 문제가 해결되었다.
• 그렇다고 in-CS에 아예 못들어가지 않기 때문에 Bounded wating을 어기지 않는다.
• 아무도 없다면 들어갈 수 있기 때문에 Progress조건도 성립함

SW solution 들의 문제점과 단점

• 다익스트라 알고리즘을 보면 서로 CS에 들어갈것인지 확인하고 많은 프로세스가 들어가려고 한다면 1, 2단계 반복이 많이 일어난다 => 속도가 느림 (비효율적임)
• 구현이 복잡하다
• 위의 과정들은 instruction 하나가 다 실행된다는 가정하에 실행된 것임. ME primitive 실행 중 preemption 될 수 있음.. (while 조건문에 조건문을 확인하는 과정에서 멈출 수 있음..) => 해결하는 방법은 공유 데이터 수정 중은 interrupt 를 억제 함으로서 해결 가능 => 오버헤드 발생함..
• 기다리는데 1,2단계 계속 반복함 => Busy waiting (비효율적인 것처럼 보인다)

 

---

본 포스트는 KOREATECH의 HPC LAB. Duksu Kim 교수님 OS강의를 기반으로 정리한 내용입니다.

상업적 의도가 아닌 공부한 것을 정리해 놓은 목적으로 게시한 포스트입니다. 

아래의 출처에서 자세한 내용을 수강하실 수 있습니다.

https://www.youtube.com/playlist?list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN

---