프로세스 동기화 & 상호배제 #3 - Mutual Exclusion Solutions(OS supported SW solution : Spinlock, Semaphore)

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

 

---

OS supported SW solution 

Spinlock

• 정수 변수
• 초기화, P(), V() 연산으로만 접근 가능
  • 위 연산들은 indivisible (or atomic) 연산
    • OS support
    • 전체가 한 instruction cycle에 수행 됨

• P연산 -> 꺼내는 연산, V연산 -> 집어넣는 연산

단점

• 멀티 프로세서 시스템에서만 사용 가능
• Busy waiting

---

Semaphore

• 1965년 Dijkstra가 제안
• Busy waiting 문제 해결
• 음이 아닌 정수형 변수(S)
  • 초기화 연산, P(), V() 로만 접근 가능
    • P: Probern (검사)
    • V: Verhogen (증가)
• 임의의 S 변수 하나에 ready queue 하나가 할당 됨

 

Binary semaphore

• S가 0과 1 두 종류의 값만 갖는 경우
• 상호배제나 프로세스 동기화의 목적으로 사용

Counting semaphore

• S가 0이상의 정수값을 가질 수 있는 경우
• Producer-Consumer 문제 등을 해결하기 위해 사용
  • 생산자-소비자 문제

 

• 초기화 연산
  • S 변수에 초기값을 부여하는 연산
• P() 연산, V() 연산
  
  • spinlock과는 다르게 반복문에서 대기하지 않고 waiting queue에서 대기
  • wating queue 에 대기중인 프로세스가 있으면 깨워서 실행

• 모두 indivisible 연산
  • OS support
  • 전체가 한 instruction cycle에 수행 됨

Semaphore in OSs

Windows

• MSDN : docs.microsoft.com/ko-kr/windows/win32/sync/semaphore-objects?redirectedfrom=MSDN

Unix/Linux

• System V : docs.oracle.com/cd/E19683-01/816-5042/auto32/index.html

 

Semaphore로 해결 가능한 동기화 문제들

• 상호배제 문제 : Mutual exclusion
• 프로세스 동기화 문제 : process synchronization problem
• 생산자-소비자 문제 : producer-consumer problem
• Reader-writer 문제
• Dining philosopher problem
• 기타

 

Mutual exclusion

 

Process synchronization

• Process들의 실행 순서 맞추기
• 프로세스들은 병행적이며, 비동기적으로 수행

 

Producer-Consumer problem

• 생산자(Producer) 프로세스
  • 메시지를 생성하는 프로세스 그룹
• 소비자(Consumer) 프로세스
  • 메세지 전달받는 프로세스 그룹

Producer-Consumer problem with single buffer

Producer-Consumer problem with N-buffers

• nrfull : 채워진 buffer 수
• nrempty : 비어있는 buffer 수 
• mutexP, mutexC : 한번에 하나의 프로세스 수행

Producer

• P(nrempty) : buffer의 빈 공간 확인 -> 없으면 대기 (queue)
• buffer[in] <- M : Message를 buffer 공간에 삽입
• in <- (in + 1) mod N : 다음 위치 갱신
• V(nrfull) : 내용 추가

Consumer

• P(nrfull) : buffer의 내용 확인 -> 없으면 대기
• m <- buffer[out] : buffer내용 꺼내기
• out <- (out + 1) mod N : 꺼낼 위치 갱신 
• V(nrempty) : 빈 공간 추가

 

Reader-Writer problem

• Reader
  • 데이터에 대해 읽기 연산만 수행
• Writer
  • 데이터에 대해 갱신 연산을 수행
• 데이터 무결성 보장 필요
  • Reader들은 동시에 데이터 접근 가능
  • Writer들(또는 reader와 write)이 동시 데이터 접근 시, 상호배제(동기화) 필요
• 해결법
  • reader / writer 에 대한 우선권 부여
    • reader preference solution
    • writer preference solution

Reader-Writer problem (reader preference solution)

• wmutex, rmutex : writer와 reader가 하나씩 수행
• nreaders : reader의 수

Writer

• P(wmutex) : CS에 수행중인 프로세스 없으면 수행 있으면 대기
• V(wmutex) : 프로세스 수행 후 wmutex + 1

Reader

• 수행 전 P(rmutex) ~ V(rmutex)
  • reader가 없으면 P(wmutex)(writer사용 X) 후 nreaders + 1 
• 수행 후 P(rmutex) ~ V(rmutex)
  
  • nreaders - 1 후 마지막 reader라면 V(wmutex) : (writer사용 가능)

 

Semaphore

• No busy waiting
  • 기다려야 하는 프로세스는 block(asleep)상태가 됨
• Semaphore queue에 대한 wake-up 순서는 비결정적
  • Starvation problem 발생 가능

---

 

강의

www.youtube.com/watch?v=33OqgesF-mM&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=15

www.youtube.com/watch?v=CitsUz-Dx7A&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=16