[10 & 11] Mutual Exclusion & Semaphore

충돌 발생

Sysnchronization Terminology ( 동기화 용어 )

-- Synchronization : 두 개의 thread 가 충돌없이 협력하는 것

-- Mutual exclusion : 한 개의 thread 가 수행되는 동안 해당 thread 만 수행하는 것을 보장, 다른 thread 들은 해당 시점에서는 배제됨,프로세스가 동시에 공유 자원에 접근하는 것을 막음

-- Critical section : 한 thread 가 주어진 시간에 실행할 수 있는 코드

-- Lock : 다른 thread 가 침범하는 것을 막는 것 

: CS : critical section

: thread 가 CS 들어가기 전에 lock -> CS 나올 때 unlock 하면 CS 들어가고 싶어하는 thread 는 unlock 될 때까지 기다려야 함

 

 

Enforcing Mutual exclusion

-- method

: 사용자 -> 스레드 간의 협력이 필요한 상황에서 스레드가 자신의 실행을 중지하고 다른 스레드가 실행할 수 있도록 제어권을 다른 thread 에게 넘김, 스레드 간의 경쟁 상황을 방지하고 안전하게 공유자원을 활용할 수 있음

: OS -> mutual exclusion 보장을 위해 counter 을 이용하여 thread의 접근을 제어

: hardware -> 구조적으로 보장하는데 원자적 명령을 사용함 

: 원자적 명령 : 하나의 CPU 명령어로 수행되며 명령어가 수행되는 중간에 다른 프로세스나 스레드가 접근하지 못하게 함

 

위의 방법들은 해결해야할 문제들이 있는데,

1. 굶어 죽는 걸 피해야한다 

: 한 스레드가 일단 cs 에 엑세스하면 결국엔 스레드는 결국 성공해야 한다. 한 번 실행 후 time quantum 이 끝나 중단되었더라고 스레드 종료를 보장해야 한다, 실행되지 않는 스레드나 프로세스가 있으면 안된다

2. dead lock ( 죽을 떄까지 lock 걸리는 거 ) 를 피해야 한다

: 예를 들어 우선순위가 가장 높은 스레드가 반복적으로 cs에 들어가는데 deadlock 이 걸리면 모든 스레드는 cs 접근이 불가능함

 

Critical Section

: 공공 화장실을 예로 들 수 있다

: 화장실은 개인 혼자 들어가는 private 한 공간인 동시에 여러 사람이 사용하는 공용 공간이다.

: 따라서 화장실 안의 변기는 publlic 자원이고 화장실 칸에 들어가 있는 것은 개인이 private 한 공간에 있는 것이다.

: 만약 화장실칸 안에서 문을 잠그고 잠이 들어버리면 ( block ) 다른 사람들이 화장실을 사용할 수 없으니 잠들면 안된다.

 

Algorithm

1. Igloo

: 칠판이 있는 이글루를 사용하는 방식으로 오직 한 사람만이 들어갈 수 있는 사이즈의 이글루

: 칠판은 오직 하나의 value 만 적을 수 있는 사이즈

: CS 를 실행하기 원하는 스레드는 이글로 안으로 들어가 칠판을 확인하여야 한다

++ 1. 만약 칠판에 스레드 본인 번호가 안 적혀있으면 이글루를 떠나 밖으로 나가 이글루 밖을 달림 

++ 2. 이후에 다시 안으로 들어와 칠판을 다시 확인한다.

++ 3. 이런 "busy-waiting" 은 칠판에 스레드 본인의 번호가 적힐 때까지 계속된다.

: 만약 스레드의 번호가 칠만에 적히면 스레드는 이글루를 떠나 CS 에 들어간다.

: CS에서 스레드가 돌아오면 이글루로 들어가 칠판에 다른 스레드의 숫자를 적는다.

++ 사진 첨부 ++

 

2. 각 스레드들은 자신만의 이글루를 가짐

: 한 스레드가 자신의 칠판을 검사하고 그 칠판을 자신이 변경할 수 있음

: 한 스레드는 다른 스레드의 칠판을 검사할 수 있지만 해당 칠판을 변경할 수 없음

: 칠판에 적혀있는 "true" : 스레드가 CS 에 들어간 상태

: CS 를 원하는 스레드는 다른 스레드의 이글루에 들어가 해당 이글루의 칠판을 검사할 수 있음

: 칠판에 "flase" 가 적혀있으면 다른 스레드가 CS 에 들어가 있지 않은 것을 확인할 수 있음

++ 위와 같은 경우 스레드는 본인 이글루로 들어가 칠판에  "true" 를 작성하고 CS 에 들어감

: CS 가 끝나고 돌아오면 자신의 이글루로 와서 칠판에 "false"로 작성함

 

++ 사진 첨부 겸 코드 설명 ++

3. 심판이 존재 ( Peterson's algorithm )

: 누구의 차례인지 알려주는 심판이 존재하는 알고리즘

: 두 사람이 누구 차례인지에 대해 의견이 다를 때마다 심판에게 질문을 함

: 심판은 priority  를 가질 차례가 누구인지를 기록함

: Deker's algorithm 에 파생된 알고리즘

: N 개의 프로세스인 경우 Lamport's Bakery algorithm 을 사용

++ 만약 한 스레드가 CS 에 들어가려고 하면 해당 스레드의 우선순위는 다른 어떤 스레드보다 우선순위가 높아야 함

++ 즉 스레드의 우선순위 숫자 자체가 가장 작은 스레드가 들어감

++ 만약 두 개의 스레드가 같은 숫자를 가지면 process id 가 작은 수가 들어감

 

++ 사진 첨부 ++ 코드 설명 

 

Semaphores - Mutual exclusion 을 보장하기 위해 OS 가 지원하는 기술

: Dijkstra 에 의해 개발되었고 일반화된 lock mechnism 으로 생각할 수 있음

: 세마포어는 2개의 원자적 연산을 지원

++ 세마포어는 1로 초기화된 값을 가짐

++ thread 가 CS 에 들어가기 전에 P/wait semaphore 를 부름

++ CS 을 나갈 때 thread 는 V/signal semaphore 를 부름

++ 사아진 ++

: 주머니 속에 돌이 하나 있는 것과 같음

: 만약 한 스레드가 CS 에 들어갈 때 돌을 가지고 들어가야 하는 규칙이 있어서 돌을 들고 감 - P/wait semaphore 를 부름

: CS 가 끝나서 나오면 다시 주머니 속에 돌을 반납하고 돌아감 - V/signal semaphore 를 부름

: 만약 주머니 속에 돌이 없으면 주머니를 살펴본 스레드들은 sleep 

: CS 에 들어갔다가 나온 thread 는 돌을 반납하고 sleep 중인 threads 를 깨워 돌이 생긴걸 알려줌

 

위의 이글루를 예로 들면 - 기존의 이글루에서 아주 큰 냉동고가 생긴 상황
( CS에 들어가는 것은 이글루를 나가는 것임 )

Wait

: thread 는 이글루에 들어와서 칠판을 확인하는데 칠판에 적힌 수 ( 돌의 개수 ) 에서 -1 한 수를 칠판에 적음 (like 방명록?)

: 바꿔 적은 후 칠판을 확인했을 때 칠판에 적힌 수가 0 이면 CS 에 들어감

: But, 칠판에 적힌 수가 0 보다 작은 음수이면 아주 큰 냉동고로 들어가 동면, 즉 잠듦

 

Signal 

: CS 가 끝나고 돌아온 thread 가 이글루에 들어와서 칠판에 적힌 수에서 +1 한 수를 칠판에 적음

: 수정된 칠판의 수를 확인했을 때 수가 0 보다 작으면 냉동고에 들어가 잠들어 있는 스레드들이 존재하는 것을 의미

: 해당 thread 는 냉동고로 가서 자고 있는 threads 를 꺠움

++ 사진 내놔아 +++

 

The Coke Machine

++ 사진 & 코드 설명 ++