[CS] Process Synchronization and Mutual Exclusion #3

이 포스팅은 한국기술교육대학교 김덕수 교수님의 운영체제 강의를 참고하여 작성되었습니다.

 

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 솔루션이 있을 수 있다.

Spinlock 솔루션은 OS가 지원하는 함수(P(S), V(S))를 통해 중간에 Preemption 되지 않고 작업을 수행하는 것이 보장된다.

그래서 상호 배제 문제가 간단하게 해결된다.

 

하지만, Spinlock은 멀티 프로세서 시스템에서만 사용가능하다.

Busy waiting 문제가 있다.

 

Semaphore

1965년 Dijkstra가 제안

Busy waiting 문제 해결

음이 아닌 정수형 변수(S)

- 초기화 연산, P(), V() 로만 접근 가능

임의의 S변수 하나에 ready queue 하나가 할당됨

(Spinlock과의 차이점)

 

 

Binary semaphore

S가 0과 1 두 종류의 값만 갖는 경우

상호 배제나 프로세스 동기화의 목적으로 사용

 

Counting semaphore

S가 0 이상의 정수 값을 가질 수 있는 경우

Producer-Consumer문제 등을 해결하기 위해 사용

 

초기화 연산 : S 변수에 초기값을 부여하는 연산

P() 연산 : 물건이 있으면 꺼내간다, 없으면 while ready queue에서 대기한다.

V() 연산 : ready queue를 확인하고, 그중 하나를 wakeup 한다. 없다면 물건을 넣어주고 끝낸다.

모두 indivisible 연산 : OS support, 전체가 한 instruction cycle에서 수행

https://docs.oracle.com/cd/E19683-01/816-5042/auto32/index.html

 

busy wait 없다. 김덕수 교수님 운영 체제 강의자료 中

세마포어를 이용해서 프로세스의 순서를 지정할 수 있다. 김덕수 교수님 운영 체제 강의자료 中

생산자 - 소비자 문제, single buffer, 김덕수 교수님 운영 체제 강의자료 中

 

생산자 - 소비자 문제, n-buffer, 김덕수 교수님 운영 체제 강의자료 中

reader preference solution, 김덕수 교수님 운영 체제 강의자료 中

세마포어의 가장 큰 특징은 '대기실'이 있다는 것이다.

Busy wating 문제가 해결된다.

하지만, wake-up 순서는 비결정적이다.

Starvation problem이 발생할 수 있다.

 

 

 

 

긴 글 읽어주셔서 감사드립니다.

22.12.16