OS: Semaphore cont.

Semaphore

      --> 큰 개념 두가지: lock, 통신(동기화)

      --> 공유 자원을 여러 스레드에서 사용할 때 충돌을 방지하기 위함

      --> 여러 스레드가 공유자원을 서로 액세스 할 때 문제 발생

 

Bounded-Buffer Producer-Consumer example

위 코드는 자판기를 producer-consumer 문제로 모델링 한 것이다.

      --> 자판기에는 emptySlot 이 100개 있다. (콜라를 담을 수 있는 슬롯)

      --> DeliveryPerson() 은 자판기에 콜라를 넣는다.(emptySlot이 가득 차지 않았을 경우)

      --> DeliveryPerson() 은 콜라를 하나 넣을때 마다 semaphore를 하나 감소. (emptySlot 감소)

      --> ThirstyPerson() 은 콜라를 뽑아 마시는 사람. 

      --> ThirstyPerson() 은 자판기가 비어 있으면 콜라를 얻을 수 없다.

      --> ThirstyPerson() 은 fullSlot semaphore 를 획득하여 자판기에서 콜라를 뽑는다. (콜라를 하나 뽑을때 마다 1 증가)

      --> DeliveryPerson() 과 ThirstyPerson()이 동시에 접근하지 않도록 mutex semaphore 를 사용한다.

      --> DeliveryPerson()이 콜라를 넣을 때, mutex 값을 1 감소 (mutex 값이 음수 이므로 ThirstyPerson() 은 콜라를 뽑을 수 없다)

      --> DeliveryPerson()이 콜라를 다 넣은 후 다시 mutex 값을 증가 (이때부터 ThirstyPerson() 도 콜라를 뽑을 수 있다.)

      --> ThirstyPerson() 은 콜라를 뽑기 전  mutex 값을 1 감소, 뽑은 후 다시 mutex 값을 1 증가 시킨다.

 

 

      --> note: Positive semaphore: number of additional threads that can be allowed into critical section

                    Negative semaphore: number of threads blocked

                    

 

 

Semaphore: 두가지 버젼

Two versions of semaphore

      --> General Semaphore 와 classical semaphore의 가장 큰 차이는 Classical semaphore 에서 s 의 값은 음수가 될 수 없다.

      --> Classical semaphore 는 Binary Semaphore 라고도 불린다. 

      --> Classical Semaphore 는 값이 0 인경우 해당 자원에 대한 접근을 차단. 반대로 값이 1인 경우 자원에 대한 접근 허용.

 

Implementing Semaphores(Busy-Waiting)

      --> 위 코드는 busy-waiting 을 사용해 semaphore를 구현하고 있는데 이 방법의 문제점은 다음과 같다

            > 대기중인 스레드의 큐를 지원 x

            > 대기중인 스레드가 busy-waiting 으로 CPU 자원 낭비

            > Semaphore 의 critical section 이 보호 x

 

Implementing Semaphores(enable interrupts)

      --> 문제점

            > 대기 중인 스레드의 큐 지원 x

            > 대기 중인 스레드가 CPU 자원 낭비

            > 멀티 프로세서에서 작동 x

            > 타이머와 충돌 가능성

            > 사용자가 인터럽트 비활성화 불가

 

Implementing Semaphores(text&set instruction)

      --> 동작과정

            > Lock(lk) 의 초기값 = 0

            > if (lk = 0 ): read 0, set value to 1 & return 0

                  > 루프 테스트가 실패, lock 은 busy

            > if (lk = 1): read 1, ser value to 1 & return 1

                  > 루프 테스트 성공, 누군가 잠금 해제할 때까지 루프 계속

      --> Test & set 은 atomic read-modify-write action 이다

            > RMW 명령은 원자적으로 값을 읽고 변경하고 쓴다.

      --> 장점

            > 멀티 프로세서에서 동작 가능

      --> 단점

            > 대기중인 스레드의 큐 지원 x

            > 대기중인 스레드는 자원낭비

 

 

Semaphore 는 두가지 목적이 있다

      --> Mutual Exclusion: 공유 자원 보호

      --> Synchronization: 이벤트를 시간적으로 조정하여 한 쓰레드가 어떤것을 기다리고 있을 때, 다른 스레드가 이용가능해지면 신호를 보내어 알리는것  

 

Lock은 공유 자원에 mutually exclusive access

      --> 잠금 상태와 해제 상태

      --> binary semaphore 사용하여 간단하게 구현

      --> 규칙

            > 공유자원 접근 전, call Lock::Acquire

            > 접근 후, call Lock::Release()

 

lock

      --> 큐가 비어있을 경우, Queue::Remove() 가 무언가를 제거할 수 있을때까지 대기하는것이 더 좋을수도 잇따

            > 그냥 go to sleep 할 수 없다-- 락을 가진채로 잠든다면 다른 스레드는 공유큐에 접근하여 항목을 추가 하거나 다른 스레드를 깨울 수 없다

            > 해결방안: 조건 변수를 사용하여 쓰레드가 잠들면서 락을 헤제하여 critical section 내에서 슬립

 

Condition Variables

      --> 조건 변수는 이벤트를 조정한다

      --> Nachos 구문

            > Condition(*name): 지정된 이름으로 새로운 클래스 조건변수 인스턴스 생성

            > Condition::Wait(conditionLock): 락을 해제한 후 슬립. 스레드가 깨어나면 다시 락을 획득

            > Condition::Signal(conditionLock): 락이 대기중인 스레드가 있으면 그 중 하나를 깨우고 준비 리스트에 넣음

            > Condition::Broadcast(conditionLock): 락이 대기중인 스레드가 있으면 그 모든 스레드를 깨우고 ready list 에 넣는다

                  >>Wait, Signal, Broadcast 호출전 스레드는 락을 보유해야 한다.

 

 

 데이터 구조에는 락과 조건변수 모두 연관

            --> 프로그램이 데이터 구조에서 작업을 수행하기 전 락 획득

            --> 다른 작업이 데이터 구조를 적절한 상태로 놓을 때 까지 조건변수를 사용하여 대기.

 

Unbounded-buffer producer-consumer

 

Compare Semaphores and Condition Variable

            --> Lock 내에서 semaphore 사용시 데드락 문제 발생 

            --> lock 은 공유 자원에 대한 상호 배제, 즉, 한번에 하나의 스레드만 공유 자원에 액세스 할 수 있다

            --> 하지만 세마포어는 대기열에 있는 스레드를 일시 중지, 다른 스레드가 접근 가능하게

            --> Lock 내에서 semaphore 사용시, 스레드는 잠금을 보유한 상태로 대기하게 되에 다른 스레드 접근 x

           

            --> Semaphore는 이전에 발생한 이벤트에 대한 정보 추적 x, 현 상태만 유지, 이벤트를 놓칠 수도 있음

            --> 조건변수는 신호를 보낸 이벤트를 추적하고 이전에 발생한 이벤트를 놓치지 않도록 보장

            

            --> Semaphore는 값을 가지고 있지만 condition variable 을 없다

            --> Semaphore signal (a V) 가 주어질 시, 아무도 기다리고 있지 않아도 항상 증가한다.

                        > 나중에 semaphore wait(a P)를 하게 되면 semaphore 는 감소되고 스레드는 이어나간다

            --> Conditional variable signal 이 주어질 시, 아무도 대기중이지 않으면 signal은 바뀌지 않는다

                        > 나중에 스레드가 conditional variable wait을 하면 wait 한다

                        > 이전에 얼마만큼의 signal이 주어졌는지는 중요하지 않다

 

Two Kinds of Condition Variable

            --> Hoare-style

                        > 스레드가 Signal()을 할 시, 락을 포기(대기중인 스레드가 다음 스레드)

            --> Mesa-Style

                        > 스레드가 Signal 할 시, 락을 유지 (대기중인 스레드는 reqdy queue로)

                        > 다음 스레드가 다음에 선택된다는 보장 x

                        > 대기중인 스레드가 아닌 다른 스레드가 락을 획득할 수도 있다

 

Monitors

            --> 모니터는 데이터와 락, 조건변수를 자동으로 연관시켜주는 추상화 된 개념

            --> 모니터는 개인 데이터와 원자적 작업(맴버함수)를 포함

            --> 이 함수중 한번에 하나만 실행 가능, 모니터 데이터는 모니터 내에서만

            --> 모니터또한 락을 가지고 있다

 

Dining Philosophers

            --> 5명의 철학자가 같이 살고 대부분의 시간을 생각하고 먹는데 사용

                        > 그들은 하나의 큰 테이블에서 먹는다(set with 5 plates and 5 forks)

                        > 먹기 위해서 각 철학자는 자신의 지정 자리로 가야하며, 두개의 포크를 사용해야 한다

                        > 먹지 않을 때, 철학자는 생각중

            --> 문제점: 5명이 모두 식사도 하고 , 생각도 하게 만들 수 있을까?

                        > Mutual Exclusion을 만족해야하며,

                        > Deadlock을 피해야 하며

                        > Starvation 을 피해야한다(결국 포크를 할당 받아야 한다)

            --> 해결책1: 한번에 4명만 먹는다.