Study/OS

Chapter 06. Process Syncronization and Mutual Exclusion (5of7) - OS supported Sol2 - Semaphore

zzoo-ppaamm 2021. 7. 5. 12:59

Mutual Exclusion Solutions

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

busy waiting을 해결하기 위해

Semaphore

  • (또!) dijkstra가 제안
  • Busy waiting 문제 해결 !!!
  • 음이 아닌 정수형 변수(S)
    • 초기화 연산, P(), V() 로만 접근 가능
    • P: 검사
      V: 증가
  • (여기까지는 SpinLock이랑 똑같은데 ?)
  • :star: 임의의 s변수 하나에 ready queue 하나가 할당됨 :star:

종류

  • Binary Semaphore
    • 0 또는 1만 가짐
    • 상호 배제나 프로세스 동기화 목적으로 사용
  • Counting Semaphore
    • 0이상 정수값
    • Producer-Consumer 문제를 해결하기 위해 사용
// P(S)
if(S > 0)
then S ← S - 1; // 물건이 있으면 하나 뺏김
else wait on the queue Qs; // 물건이 없다면 대기실(Qs)에서 기다림

(Spinlock과의 차이점 : 물건 없을 때 뺑뺑돌면서 기다리지 않고 큐에서 기다림)

// V(S)
// ∃ : 어떤
if(∃ waiting processes on Qs) // 대기실에 기다리는 애가 있다면?
then wakeup one of them; // 한명 깨워줌
else S ← S + 1; //
  • 모두 indivisible 연산
    • OS support 보장
    • 전체가 한 instruction cycle에 수행된다
  • Sempahore로 해결 가능한 동기화 문제들
    • 상호배제 문제
    • 프로세스 동기화 문제
    • 생산자-소비자 문제
    • Reader-writer 문제
    • Dining philosopher 문제
  • Process Synchronization
    • 프로세스들의 실행 순서 맞추기
      • 프로세스들은 병행적이며, 비동기적으로 수행
  • :star:Producer-Consumer problem
    • 생산자 프로세스 ex) 라인 프린터 드라이버, 컴파일러 , 어셈블러
    • 소비자 프로세스 ex) 라인프린터, 어셈블러, 로더
    • (buffer가 하나뿐이다. 생산하기전에 소비하면 안되겠지? 동기화 필요)
    • (두개의 semaphore(consumed, produced)로 해결)
      (생산하기전에 P(consumed) 생산 후 V(produced))
      (소비하기전에 P(produced) 소비 후 V(consumed))
  • Producer-Consumer problem with N-buffer
    • Circular Queue 사용
    • // 생산자
P(mutexP);
P(nrempty);                // cs 공간확인

buffer[in] ← M;            // cs
in ← (in + 1) mod N;    // cs

V(nrfull);                // cs
V(mutexP);
    • // 소비자
P(mutexC);
P(nrfull);                // cs 물건확인

m ← buffer[out];        // cs
out ← (out+ 1) mod N;    // cs

V(nrempty);                // cs
V(mutexC);
  • Reader-Writer problem
    • reader : 데이터에 대해 읽기 연산만 수행
    • writer : 데이터에 대해 갱신 연산을 수행
    • 데이터 무결성 보장 필요
      • reader들은 동시에 데이터 접근 가능
      • writer들이 동시 데이터 접근 시 상호배제(동기화) 필요
    • 해결법
      • reader / writer에 대한 우선권 부여
    • // reader
P(rmutex);
if (nreaders = 0) then
    P(wmutex);
endif;
nreaders ← nreaders + 1;
V(rmutex);    

Perform read operations            

P(rmutex);
nreaders ← nreaders - 1;
if (nreaders = 0) then
    V(wmutex);
endif;
V(rmutex);    
    • // writer
P(wmutex);        

Perform write operations

V(wmutex);
  • 장점
    • :star: No busy waiting
      • 기다려야하는 프로세스는 block(asleep)상태가 됨
    • Semaphore queue에 대한 wake-up 순서는 비결정적
      • Starvation problem (기아현상)