프로세스 동기화 & 상호배제 #2 - Mutual Exclusion Solutions(SW solutions - Dekker, Peterson,Dijkstra , HW solution - TAS)

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

 

---

SW solutions

Dekker’s Algorithm

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

• flag : CS에 들어갈지 말지, turn : 일을 수행가능 한지 

1. P0가 일을 수행하기 위해 flag : true
2. P1이 일을 수행 중인지 확인 (P1의 flag 확인)
3. 내가 수행할 수 있는지 확인(turn 확인)
   1. turn이 1인경우 -> flag : false 후 대기
   2. turn이 0이 되면 flag : true 후 수행

 

Peterson’s Algorithm

• Dekker’s algorithm 보다 간단하게 구현

• 일을 수행하기 위해 flag : true , 그리고 상대에게 turn을 넘긴다. ( 먼저 양보한 쪽이 먼저 수행 ) 

 

N-Process Mutual Exclusion

다익스트라Dijkstra

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

크누스knuth

• 이전 알고리즘 관계 분석 후 일치하는 패턴을 찾아 패턴의 반복을 줄여서 프로세스에 프로세서 할당
• 무한정 연기할 가능성을 배제하는 해결책을 제시했으나, 프로세스들이 아주 오래 기다려야 함

램포트lamport

• 사람들로 붐비는 빵집에서 번호표 뽑아 빵 사려고 기다리는 사람들에 비유해서 만든 알고리즘 (Bakery algorithm)
• 준비 상태 큐에서 기다리는 프로세스마다 우선순위를 부여하여 그 중 우선순위가 가장 높은 프로세스에 먼저 프로세서를 할당함

핸슨brinch Hansen

• 실행 시간이 긴 프로세스에 불리한 부분을 보완하는 것
• 대기시간과 실행 시간을 이용하는 모니터 방법
• 분산 처리 프로세서 간의 병행성 제어 많이 발표

 

Dijkstra’s Algorithm

• Dijkstra 알고리즘의 flag[] 변수

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

N개의 프로세스가 있는 경우

1. CS 진입 시도 1단계 : want-in 상태로 변경
   - 내차례가 아니면 대기 ( 현재 turn인 프로세스가 idle이 될 때까지 대기 )
   - 현재 turn 의 프로세스가 idle이 되면 turn을 가져온다.
2. 턴을 가져온 후 CS 진입 시도 2단계 : in-CS 상태로 변경
   - n개의 프로세스들의 상태를 확인(in-CS상태의 프로세스 확인)
   - in-CS상태가 나 혼자인 경우에 CS로 진입( j == n )

 

SW solution들의 문제점

• 속도가 느림
• 구현이 복잡함
• ME primitive 실행 중 preemption 될 수 있음
  • 공유 데이터 수정 중은 interrupt를 억제 함으로서 해결 가능
    -> Overhead 발생
• Busy waiting : 반복문을 돌면서 수행 대기 -> 비효율적

---

HW Solution

Synchronization Hardware

TestAndSet (TAS) instruction

• Test 와 Set을 한번에 수행하는 기계어
• Machine instruction
  • Atomicity, Indivisible
  • 실행 중 interrupt를 받지 않음 (preemption 되지 않음)
• Busy waiting -> Inefficient

 

TAS Instruction

TestAndSet 명령어

• 현재 target의 값을 반환하면서 target의 값을 true로 변경
• 한번에 수행 되는 것을 보장해 줌으로써 간단히 해결 

ME with TAS Instruction

• lock의 초기값이 false 이므로 lock의 값을 true로 변환시키고 CS 진입
• 작업 수행 중에는 lock의 값이 true이므로 false로 변경될 때까지 반복문에서 대기
• 작업 수행 후 lock을 false로 변경

3개 이상의 프로세스의 경우, Bounded waiting 조건 위배

• 대기 중인 프로세스들의 순서가 없으므로 특정 프로세스가 계속 실행되지 않을 수 있다.

 

N-Process mutual exclusion

• waiting : 프로세스 Pi가 기다릴지 결정
• lock의 값이 false인 경우에 ⑤로 진입
• 대기 중인 프로세스가 없으면 lock -> false 
• 대기 중인 프로세스가 있으면 대기중인 프로세스가 CS에 진입할 수 있도록 waiting -> false

 

장점

• 구현이 간단 

단점

• Busy waiting

---

 

강의

www.youtube.com/watch?v=lY43KR3IItw&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=13

www.youtube.com/watch?v=Zps0ckSvKys&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=14