Semaphores

방법

• integer 변수 S
• Atomic 연산에 의해서 접근
  • P(s) : 자원 획득 s--
    • busy-wait 문제 : 계속 wait 상태
      ➡️ block/wakeup로 구현

      P : s<0 -> block(); 어차피 아무것도 못하니 block
      V : s<=0 -> wakeup(p);

  • V(s) : 반납 s++

Classical Problems

Bounded-Buffer Prob

Producer-Consumer Problem

발생하는 문제

여러 Process가 동시에 같은 빈 버퍼에 데이터 접근하여 넣음
해결 ➡️ 접근시 Lock 걸기
Shared data : buffer, buffer 조작 변수 (empty, full buffer 시작 위치)
Synchronization variables: resource count(empty, full buffer), mutual exclusion(binary semaphore)

• Producer : 공유 버퍼에 넣는 역할, 비어있는 버퍼 count 필요
  1. empty buffer 기다리기 P(empty)
  2. Shared data에 lock을 건다. P(mutex)
  3. empty buffer에 데이터 입력 (버퍼 조작)
  4. Lock 풀기 V(mutex)
  5. full buffer++ V(full): 소비자 입장에서 자원 반납
• Consumer : 버퍼에 들어있는 데이터 소비 역할
  1. full buffer 기다리기 P(full)
  2. Shared data에 lock 걸기 P(mutex)
  3. full buffer에서 데이터 꺼내기 (버퍼 조작)
  4. lock 풀기 V(mutex)
  5. empty buffer++ V(empty) 빈 것 반납 생산자 입장에서 자원 반납

Readers-Writers Problem

발생하는 문제

write은 오직 한 process만, read는 동시에 여럿이 해도 됨 ➡️ 둘 다 lock을 해도 되지만 비효율적이다.
해결
➡️ 대기 중인 reader가 없을 때 writer 접근 허용
➡️ 접근 중일 때만 DB lock
➡️ reader 포함 모든 process 접근 금지
Shared data : DB, readcount(현재 접근 중인 Reader의 수)
Synchronization variables: db(binary semaphore), mutex(readcount를 접근하는 코드) ➡️ lock 걸기 위함

• writer
  1. db에 lock 걸기 P(db)
  2. DB 조작
  3. db에 lock 풀기 V(db)
• reader
  1. readcount에 lock 걸기 P(mutex)
     • readcount++
     • if readcount==1: P(db) : 도중에 writer가 값을 바꾸면 안되니깐 최초 reader일 때 db에 락을 걺.
  2. readcount lock 풀기 V(mutex)
  3. DB 읽기
  4. readcount lock 걸기 P(mutex)
     • readcount--
     • if readcount==0: V(db) : writer은 대기 중인 reader가 없을 때 db 접근이 가능하므로 이 사실을 writer에게 알리기 위함
  5. readcount lock 풀기 V(mutex)

Dining-Philosophers Problem

철학자가 하는 일은 생각하기와 밥먹기인데, 밥먹을 때 문제 발생

발생하는 문제

젓가락 좌우를 모두 잡아야 식사가 가능한데, 모두 동시에 왼쪽만 집은 경우 등 Deadlock의 가능성이 있다.
해결
1. 4명의 철학자만이 동시에 앉도록
2. 두개를 모두 집을 수 있는 경우에만 먹을 권한 주기 ➡️ 밥을 먹을 때만(먹을 수 있을 때만 권한 가능성을 줌)
3. 비대칭 : 짝수 철학자는 왼쪽, 홀수 철학자는 오른쪽 먼저 집도록 한다.

variables
enum {thinking, hungry, eating} state[5];
semaphore self[5]=0; : binary(0,1) : 권한을 줄지 말지에 대한 변수
semaphore mutex=1 : lock을 위한 변수

putdown(i) : thinking state로 바꾸고, 좌우에게 권한을 줄지 말지를 정하기 위해 양 옆을 직접 test 진행
pickup(i) : hungry state로 바꾸고, 본인이 잡을 수 있는지 check 후 P(self[i])를 통해 1이면 양옆이 알아서 줌
test(i) : 양 옆이 eating state가 아니어야 하고, 본인은 hungry 상태여야 함. 조건 충족 한다면 eating state로 바꾸고, 권한을 준다.

➡️ 해당 방식은 monitor 방식과 더 유사하다.

Monitor

공유 데이터에 대해 알아서 자동으로 처리

Semaphore의 문제점

• 코딩 어려움
• 정확성 입증 어렵다
• 자발적 협력이 필요
• 한번의 실수가 모든 시스템에 치명적 영향
  P를 두번 하거나(Deadlock), P와 V의 순서를 반대로 하거나(breaking mutual exclusion)

➡️ Monitor 등장!
High-level synchronization construct
lock을 걸 필요가 없음
active process 하나만 모니터 접근 가능하도록 함. 아니면 다 queue에서 기다려야 함

• 모니터 내에서 한 번에 하나의 프로세스만
• 동기화 제약 조건을 명시적으로 코딩할 필요 없다.
• 프로세스가 모니터 안에서 기다릴 수 있도록(잠들게 하기 위한 용도) condition variable 이용
• Condition Variable
  wait과 signal 연산에 의해서만 접근 가능
  • x.wait() : x에 가서 줄서기
    wait인 프로세스는 다른 프로세스가 signal을 invoke하기 전가지 suspend된다.
  • x.signal() : x 중 하나를 깨우기
    정확히 하나의 suspend된 프로세스를 resume 하는데 suspend가 없다면 아무 일도 일어나지 않는다.

구조

monitor name
{
	shared variable declarations
    procedure body P1(...){...}
    procedure body P2(...){...}
    procedure body P3(...){...}
	{initialization code}
}

Bounded-Buffer Problem을 monitor로 해결하기

monitor bounded_buffer
{   int buffer[N];
	condition full, empty; // 값을 가지지 않고 자신의 큐에 프로세스를 달아 sleep시키거나 깨우는 역할만 함
    
    void produce(int x)
    {   if there is no empty buffer : empty.wait();
    	add x to an empty buffer
        full.signal() // full을 기다리는 소비자 하나 깨우기
    }
    void consume(int *x)
    {	if there is no full buffer: full.wait()
    	remove an item from buffer and store it to *x
        empty.signal()
    }
}

Semaphore와 차이

• 목적이 다름. (코드는 비슷)
• Lock이 없음
• 값이 아닌 조건 체크

Deadlock 교착 상태

The Deadlock Problem

• Deadlock : 일련의 프로세스들이 서로 가진 자원을 기다리며 block 된 상태
• Resource 자원
  • H/W, S/W 등을 포함하는 개념
  • 프로세스가 자원을 사용하는 절차 : Request, Allocate, Use, Release

example

• 아무도 자원을 내놓지 않지만, 상대방의 자원을 원하고 있는 상태
• binary semaphores로 서로의 것을 탐하는 중

Deadlock 발생 4가지 조건

• Mutual exclusion 상호 배제 : 매순간 독점적으로 하나의 프로세스만 자원 사용 가능
• No preemption 비선점 : 강제로 빼앗기지 않음 (자발적으로 내놓긴 하나 강제로 뺏기지 않음)
• Hold and wait 보유 대기 : 보유하면서 추가적인 것을 기다림. 내놓지 않음 (자발적으로 내놓지 않음)
• Circular wait 순환 대기 : 필요 자원이 꼬리에 꼬리를 물고 있음. cycle이 형성된 것

Resource-Allocation Graph 자원할당그래프

Deadlock 확인 방법
O: 프로세스 / ㅁ: 자원 (single or multi instance)
O->ㅁ: 프로세스가 자원 요청 / O<-ㅁ: 자원이 프로세스에 속함

분류

• cycle X : deadlock X
• cycle O
  • one instance : deadlock O
  • 여러 instance : possibility of deadlock

Deadlock의 처리 방법

위로 갈 수록 강한 방법

Deadlock Prevention

Deadlock 발생 조건 중 하나가 만족되지 않도록 하는 것. 미리 방지하는 방식

• Mutual Exclusion 배제 : 배타적으로 쓰기
  ➡️ 공유 가능한 자원으로 만들기 < 애초에 배제 불가한 조건
• Hold and wait 배제 : 자원을 기다려야 하는 상황에서 자원 보유하지 않기
  1. 프로세스 시작시 필요한 모든 자원 할당 ➡️ 자원에 대한 비효율 발생 (노는 자원 생김)
  2. ⭐️ 자원이 필요한 경우 보유 자원을 모두 자진해서 반납 후 다시 요청
• No Preemption 배제 ???
  다른 프로세스의 보유 자원을 뺏어오는 것
  state를 save 하고 restore할 수 있는 자원에서 주로 사용 (CPU, memory)
• Circular Wait 배제 : 할당 순서 정하기
  모든 자원에 할당 순서를 정해 프로세스가 정해진 순서대로 자원을 보유하도록 함

➡️ 미리 방지하는 방법. 하지만 비효율적
자원 이용률(utilization) 낮아지고, startvation, 시스템 성능(throughput) 저하 등 발생
생기지도 않을 deadlock이니 이렇게 미리 방지하는 것은 오버해드

Deadlock Avoidance

자원 요청시 부가 정보를 통해 deadlock의 가능성이 없는 경우에만 자원 할당. 미리 방지하는 방식

• 해당 요청 수행시 deadlock으로부터 안전한지 동적으로 조사 후 안전한 경우만 할당

• 자원별 최대 사용량을 미리 선언해두도록 함

• Safe sequence : 최대 자원 요청이 가용 자원 + 보유자원 안에 들어가도록 일련의 프로세스인 sequence를 구성해야함. 앞 프로세스가 모든 자원을 반납하여 다음 프로세스의 자원 요청을 만족시킨다.

• Safe state 를 유지해야함. by Safe sequence
  ➡️ no deadlock 상태
  반대로 unsafe state은 possibilty of deadlock 상태
  ➡️ deadlock일 수도, 아닐수도 있다.

알고리즘

1. Resource Allocaion Graph Algorithm (ver. Single instance)
   그래프 이용하기. O(n^2) 시간 소요.
   ➡️ 점선으로 표현된 특정 요청이 들어오면 곧장 deadlock으로 빠지는 최악의 상황만 가정하여, 해당 요청이 들어오면 그 자원이 available해도 주지 않음.
   이러한 가정은 미리 최대 자원 요청 정보를 알고 있기에 가능하다.

2. Bancker's Algorithm (ver. Multi instance)
   대단히 보수적이고, 항상 안전한 방식
   가정 : 최대 사용량 미리 명시 && 요청 자원을 할당 받은 뒤 유한 시간 안에 자원 다시 반납

   Allocation: 현재 할당된 것
   Max: 최대 사용량
   Available: Allocation을 제외하고 남은 가용 자원
   Need(Max-Allocaion, 앞으로 해당 프로세스가 필요한 자원들

   특정 프로세스가 자원 요청시, 최대 요청 상황으로 가정하고 Need가 Available을 충족하는지 확인
   가능하면 어느 요청이든 ok, 하지만 불가능하면 절대 내주지 않음
   해당 방법으로 sequence 구성해야함
   ➡️ 대단히 비효율적인 방법. 자원이 놀고 있게 되는 비효율
   

Deadlock Detection and Recovery

루틴을 두어 이상을 detect 후 deadlock 발견시 recover함. 발생 후 해결하는 방법

• single instance 경우 : cycle 발생이 곧 deadlock
  Wait-for graph 알고리즘 이용 : 자원을 제외하고 프로세스끼리 종료를 기다리는 화살표로 표현해 간결
  ➡️ cycle이 있는지 주기적으로 조사. O(n^2) 시간 소요. 최대 사용량을 미리 알릴 필요는 없음.

• multi instacne 경우 : Banker's algorithm 응용
  낙관적으로 보아 반납할 것이라고 가정.
  앞 프로세스가 보유 자원 모두 반납할 시 가동 가능한 프로세스를 찾는다. 그러고 safe sequence를 구성해둠.

• Recovery

  • Process terminaion
    1. Abort all : 데드락에 연루된 모두를 kill
    2. Abort one at a time : 데드락에 연루된 것들을 하나씩 차례대로 kill
  • Resource Preemption
    비용 최소할 victim 선정 후 자원 뺏어버리기 그 후 safe state로 roll back하여 process restart
    • Starvation 문제 : 같은 패턴이 지속될 수 있음
      동일한 문제가 지속되어 victim도 같은 프로세스가 되며서 문제 해결 X
      rollback 횟수를 고려하거나 조금씩 다른 패턴을 적용해야함

Deadlock Ignorance ⭐️

데드락이 일어나지 않는다고 가정 후 아무 조치도 안취함. 발생 후 해..결하는 방법
overhead일수도 있음 : 데드락이 매우 드물게 발생하므로 미리 조치나 해결을 하는 것은 오버
➡️ 만약 시스템에 발생시 시스템은 책임을 지지 않고 비정상적 작동을 사람이 느낀 후 알아서 kill 등 대처하도록 함. 대부분의 범용 os가 채택함