OS - Semaphore

#Semaphore

    -> Semaphore는 어따쓰나? 공유 자원을 여러 프로세스가 접근할수 있게 하며 상호 배제를 보장 -> 순번대로 처리(공유자원이 개별자원화)

    -> 프로세스간 공유변수 이용 시 충돌 방지

 

 

- semaphore는 1965년 다익스트라가 발명 -> 일반화된 잠금 메커니즘(주머니 속의 돌), 일종의 카운터

- 세마포어는 두 개의 atomic 연산, P/wait and V/siginal 지원

- 세마포어는 1로 초기화(Binary)  or Counting semaphore의 경우 초기값이 1보다 큼

- 임계 영역에 들어가기 전에 스레드는 “P semaphore” 또는 “wait semaphore”를 호출

- 임계 영역을 떠난 후에는 스레드가 V semaphore 또는 signal semaphore 호출

- 양수 s = 임계 영역에 들어갈 수 있는 쓰레드 수

- 음수 s = blocked 상태인 쓰레드 수(임계 영역에 들어가길 기다리는 쓰레드)

 

 

#Semaphore Example(동작 과정)

ex) t1, t2가 모두 한 코드에 거의 동시에 접근을 시도 하면

 

1. t1이 접근, s=1 -> s=0

2. t2가 접근 s=0 -> s=-1 -> 리소스가 없으므로 waiting queue로 이동(== blocked), 누군가 깨워주지 않으면 영원히 sleep

3. t1이 코드 수행 하고 돌 반납 s=-1 -> s=0 -> 주머니를 확인 -> s<=0 이므로 누군가 기다린다는 것을 확인 -> waiting 

   queue에서 sleep중인 t2를 깨워서 ready queue로 이동시킴

4. 리소스 확보한 t2가 코드 수행 후 돌 반납 s=0 -> s=1

5. 주머니 확인, s>0 이므로 종료

* 돌 반납 후 주머니 확인할 수도, 확인 후 반납할 수도 있음. 코드만 살짝 수정하면 됨

 

 

#The Coke Machine(Bounded-Buffer Producer-Consumer)

- 초기 fullSlot = 0(자판기에서 꽉 찬 칸), emptySlot = 100(빈 칸)

- 한번에 한 사람만 기계에 접근할 수 있음: semaphore mutex = 1

코드 동작:

- mutex = 채우는사람, 먹는사람이 동시에 기계에 접근하지 못하게 함. 0이라면 대기해야 한다는 뜻

- 콜라를 채우면 emptySlot -> P() : -1

- 콜라를 먹으면 emptySlot -> V() : +1

 

* semaphore 안에 두개의 개념이 혼재: block, 쓰레드간 통신(short-term scheduler와 비슷)

 

#Two Versions of Semaphores

- 위에서 설명한 것은 간단하게 설명한 것

- 원래 Semphore는 다음과 같다

#Implementing Semphores

- 다음 알고리즘은 block이 없음. 아무것도 안할 뿐임 -> overhead가 없어 가벼워짐

평가:

1. 블록 큐가 없음(가벼워짐)

2. 대기중인 쓰레드는 busy-waiting상태여서 CPU time만 사용하면서 아무것도 안함(자원 낭비)

3. s 변수도 임계영역임. 이게 보호되지 않음. -> 충돌 가능성

 

#보완 1

- interrupt를 disable 시켜서 해결함

- Context switching을 방지함 -> 자신이 실행 중에 다른 스레드가 침입하지 못하게 함

* context switching이란 timmer interrupt임. 그것을 비활성화 시키는

 

평가:

1. waiting queue 지원 x(장점)

2. CPU time 낭비

3. Multi processor에서는 동작하지 않을수도

4. 타이머를 사용하는 다른 Application에 영향을 미칠 수 있음(interrupt를 disable 시키기 때문)

5. OS는 수행 가능하지만, User는 불가 -> Interrupt able, disable은 커널에서 일어남. 사용자가 직접 조작할 수 없음

 

#보완 2

- test&set()이란? 

    > 

- 동작 원리

1. Lock "lk"는 초기값으로 0 가짐

2. "lk"가 비어있는 경우 (lk=0), test&set 명령어 실행

    > 0을 읽은 후, 1로 값을 설정하고 0을 반환 : 자기가 lock 획득

    > 루프 테스트가 거짓이기 때문에, lock이 현재 사용중임을 의미

3. "lk"가 사용중인 경우 (lk=1). test&set 명령어 실행

    > 1을 읽은 후, 1로 값을 설정하고 1을 반환 : 누군가 lock을 사용중

    > 루프 테스트가 참이기 때문에, 누군가 lock을 해제할 때 까지 루프가 돌아감

Test&set은 원자적인 read-modify-write(RMW) 명령어의 예입니다. ● RMW 명령어는 메모리에서 값을 원자적으로 읽어서 수정하고, 새로운 값을 다시 메모리에 씁니다. n 대부분의 CPU에서는 Test&set을 지원합니다. n Intel x86에서는 Exchange가 지원됩니다. 이는 레지스터와 메모리 간의 값을 교환합니다. n Motorola 68xxx에서는 Compare&swap이 지원됩니다. 이는 값을 읽어서 레지스터 r1의 값과 일치하는 경우, 레지스터 r1과 값을 교환합니다. n 평가: ✔ 다중 프로세서에서도 작동할 수 있지만 캐시 일관성 문제가 발생할 수 있습니다. ✘ 대기중인 스레드의 큐를 지원하지 않습니다. ✘ 대기 중인 스레드가 유휴 상태에서 시간을 낭비하며 (유용하지 않은 작업을 하지 않고 CPU 시간을 낭비합니다).

 

 

#Semaphores (review)

- 세마포어도 몇몇 동기 에러가 일어날 수 있음

해결책: 새로운 언어 구조

1. 조건부 임계 영역

    > region v when B do S;

    > 변수 v는 임계 영역 내에서만 액세스 할 수 있는 공유 변수

    > 부울 표현식 B는 액세스 제어

    > 문장 S(임계)는 B가 참일 때만 실행, 그렇지 않으면 참이 될때까지 차단됨.

2. 모니터

 

#From Semaphores to Locks and ConditionVariables

- 세마포어는 두가지 목적을 제공:

1. 상호 배제(Mutual exclusion) - 공유 데이터 보호

    > 항상 binary semaphore

2. 동기화 - 이벤트를 시간적으로 조정

    > 자판기에서 full, emptySlot 같은 경우

    > binary, counting 둘다

3. 락 - 상호 배제 제공

4. 조건변수 - 동기화 제공

5. 세마포어처럼 락과 조건 변수는 언어에 독립적이며, 많은 프로그래밍 환경에서 사용할 수 있음.

 

#Lock

- 락은 공유 데이터에 상호 배타적인 액세스 제공

    > 락은 locked, unlocked 될 수 있음(busy, free)

- 락 작업(nachos):

1. Lock(*name) - 지정된 이름으로 새로운 락 만듬

2. Lock::Acquire() - 언락 될때까지 대기 후 락을 잠금

3. Lock::Release() - 언락하고 2번에서 대기하고 있는 모든 쓰레드 깨움

- 구현 가능:

1. 이진 세마포어로 쉽게 구현 가능

2. 세마포어가 구현되는 것과 매우 유사한 하위 구조 사용

- Conventions:

1. 공유 데이터에 엑세스 하기 전에 특정 락에서 aquire 호출

    > 스레드가 이미 가지고 있는 락을 획득하려고 하면 ASSERT를 통해 주장

2. 공유 데이터에 액세스 한 후 해당 락에서 Release 호출

    > 락을 획득한 스레드 이외의 스레드가 해제하려고 시도하면 complain

 

#Locks vs ConditionVariables

 

- 큐가 비어있으면 Queue::Remove가 무언가를 제거할 때까지 기다리는것이 더 바람직할 수 있음.

> 그냥 sleep 할 수는 없음 - 락을 보유한 채로 sleep하면, 다른 스레드는 공유 큐에 액세스 할 수 없으며, 깨울 수도 없음

> 해결책: 조건 변수는 스레드가 잠들면서 락을 해제하여 스레드가 임계영역 내에서 잠들 수 있도록 함

* 반드시 자기 전에 락을 해제해라

 

#Condition Variables

- 조건변수는 이벤트를 조율. Nachos 문법에서 조건 변수의 작업은 다음과 같음

1. Condition(*name) - 지정된 이름으로 새로운 Condition 클래스의 조건변수 만듬

    > 새로운 조건을 만든 후, 프로그래머는 해당 조건변수와 연결될 락을 만들기 위해 Lock::Lock() 호출해야 함

 

2. Condition::Wait(conditionLock) - 잠금을 해제하고 sleep. 스레드가 깨어날 때 바로 잠금을 다시 획득하려고 시도함. 스레드가 잠긴 상태에서 조건 변수에서 신호가 발생하지 않으면 다시 대기

 

3. Condition::Signal(conditionLock) - 스레드가 잠근 경우, sleep중인 스레드 중 하나를 깨움. 준비된 목록에 추가. 만약 대기중인 스레드가 없으면 아무것도 하지 않음

 

4. Condition::Broadcast(conditionLock) - 만약 락을 기다리는 스레드가 있다면, 그 스레드들을 '모두' 깨워 ready queue에 넣고, 그렇지 않다면 아무것도 하지 않음

 

*중요: 스레드는 wait, signal, broadcast를 호출하기 전에 락을 보유하고 있어야 함

*higher-leve construct로 구현

*세마포어처럼 구현할 수 있음(스레드 생성 후 대기열에 넣고, 필요에 따라 sleep, wakeup 시킴)

*세마포어와 마찬가지로, 낮은 수준의 구조를 사용하여 조심스럽게 구현 가능

 

#Using Locks and Condition Variablese

- lock과 condition variable은 모두 데이터구조와 연관됨*

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

> 만약 데이터 구조가 적절한 상태가 될 때까지 다른 작업이 필요하면, 조건 변수를 사용하여 대기함.

 

#Comparing Semaphores and ConditionVariables

- 둘은 꽤 비슷함. 조건변수를 세마포어로 구현 가능할 것

-> 해당 코드는 동작하지 않음. 우리는 이 condition operation들을 lock 내부에서 사용할 것임.

-> 내부에서 semaphore를 사용한다면?

- Semaphore와 condition variables는 히스토리를 추적하는 측면에서 어떻게 다른가?

세마포어: 작업 수행 전에 값을 감소시키고, 작업 마치면 값을 증가시켜서 작업 수를 추적. 그러므로 현재 세마포어 값 만으로는 작업이 언제 수행되었는지 모름

조건변수: 대기중인 스레드를 추적하고, 대기중인 스레드가 조건을 충족시켜 깨어나는 시기를 정함. 그러므로 조건변수는 스레드가 대기하기 시작한 시간, 꺠어난 시간 등의 정보를 추적함

 

- 세마포어는 값을 가지지만, 조건변수는 아님

- V semaphore를 보내면, 대기중인 스레드가없어도 세마포어 값이 증가함

    > 나중에 P waiting을 하는 스레드가 있다면, 세마포어 값이 감소하고 스레드가 계속됨

- 조건변수 신호를 보낼 때, 대기중인 스레드가 없으면 signal은 효과가 없음

    > 나중에 조건변수 대기를 하는 스레드는 항상 대기

    > 이전에 몇 번의 신호가 있었는지는 중요하지 않음  

 

#Two Kinds of Condition Variables

1. Hoare-style(대부분의 운영체제에서 사용)

> 스레드가 Signal()을 실행하면 락(및 CPU) 방출

    > 대기중인 스레드는 다음으로 실행할 스레드로 선택됨

> 이전 예제는 Hoare-style CV 사용

 

2. Mesa-style(Mesa, Nachos 및 대부분의 실제 운영체제에서 사용)

> 대기중인 스레드는 특별한 우선 순위 없이 ready queue에 넣음

    > 그것이 다음으로 실행할 스레드가 될 것을 보장하지 않음

    > 더 나쁜 경우에는 다른 스레드가 실행되어 락을 획득하기도

> Mesa-style CV를 사용할 때는 항상 Wait()을 while 루프로 둘러싸야 함

 

#Monitors

- 모니터는 데이터에 대한 락과 조건변수를 자동으로 연결하는 프로그래밍 언어 추상화

- 모니터는 비공개 데이터와 atomic operation 세트를 포함

> 한 번에 하나의 스레드만 모니터 코드(어떤 함수든) 실행 가능

> 모니터 함수는 모니터 데이터에만 액세스

> 모니터 데이터는 외부에서 액세스 할 수 없음

- 모니터에는 락과 하나 이상의 조건변수 존재

> 컴파일러는 각 함수의 시작 부분에 acquire 연산(자원이 사용 가능해질 떄까지 기다린 다음 자원을 사용하기 위해 그것을 예약하는 연산)을 자동으로 삽입하고, 끝 부분에는 release 삽입

> 모니터를 지원하는 특수 언어는 80년대 일부 OS 전문가들 사이에서 인기 있었지만 지금은 더이상 사용되지 않음

-> 지금은 대부분의 OS에서 락과 조건변수만 제공

 

#Dining Philosophers

- 5명의 철학자가 같이 살고 대부분의 시간을 생각하고 스파게티를 먹으며 보냄

- 그들은 원형 테이블에 모여 식사를 하며 5개의 접시와 5개의 포크 준비됨

- 그들이 식사를 하기 위해서는 자신의 할당된 자리로 가서 접시 양쪽에 있는 두개의 포크를 사용해 스파게티 먹음.

- 식사를 하지 않을 때는 생각함

-> 문제: 철학자가 식사를 할 수 있는 알고리즘을 개발해야 함.

> 이 알고리즘은 상호 배제여야 함(한 번에 한 명의 철학자만 같은 포크를 사용)

> 데드락을 피해야 함(ex. 모두 왼쪽 포크를 잡고 오른쪽 포크를 기다리는 경우)

> starvation 방지해야 함(즉, 모든 철학자가 언젠가 식사를 해야함)

1. 안됨. 데드락이 걸림

2. 가능

 

해결책: