ruo10102

OS ch8. deadlocks.

Deadlock 은 한 프로세스가 특정 resoucre를 소유한 상태에서
다른 프로세스가 소유한 resource를 요청 시에 발생할 수 있다.

위에 적었듯이 프로세스가 하나일 땐 데드락이 발생하지 않습니다. 포괄적으로 말하면 프로세스와 리소스 사이의 관계에 의해 발생 가능하고, 특히 프로세스는 한 개가 아니라 여러 개일 때 일어납니다.

📌 Bridge crossing example

데드락을 설명 시에 가장 대표적인 예시입니다. 자동차를 프로세스, 도로를 리소스라고 가정해봅시다.

왼쪽(->)에서 오고있는 자동차는 1차선의 왼쪽을 차지하고 있는 상태이고,

오른쪽(<-)에서 오고있는 자동차는 1차선의 오른쪽을 차지하고 있는 상태입니다. 

이때 서로의 도로(리소스)를 요청하고 있는 상황이고, 이는 두 차 모두 진행될 수 없기 때문에 데드락 상황입니다.

Solve this problem

1. Kill the process - 데드락을 없애기위해 프로세스를 삭제하는 방법
2. Back the car up ( 후진 ) - preempt the resource and rollback. : 이전 상태중 특정상태로 돌아가는 방법 ( 데드락을 피하기 위해)

+ checkpoint : 라인 바이 라인으로 코드를 수행하는데 특정상태로 돌아가는 것은 매우 힘듭니다. 그래서 특정 상황에서 그때의 상태가 담긴 "context"를 저장해야하고 그 저장하는 공간을 checkpoint 라고 합니다. 따라서, 2번의 방법을 사용하기 위해선 주기적으로 checkpoint를 둬서 context를 저장해야만합니다. 저장을 해놓았다면 그 특정 부분으로 돌아가는 것이 가능합니다.

이제 앞으로 배울 간단한 목차에 대해서 설명하면

1. Deadlock detection : 데드락을 어떻게 검출할 것인지
2. Deadlock avoidance : 데드락이 예상된다면 데드락을 만나기 전에 회피하는 것
3. Deadlock recovery : 데드락이 발생했다면 어떻게 없앨것인지.
4. Deadlock prevention : 데드락을 어떻게 예방할 것인지

등을 배울 예정입니다.

그전에

📌 Resource Allocation Graph = (RAG) = 자원할당 그래프

: deadlock이 발생했는지 알아보기 위해 사용.

리소스가 프로세스에게 어떻게 할당되는지 그래프 형태로 그림을 그린 것.

사용이유? deadlock을 쉽게 detect 할 수 있음.

- 동그라미는 Process, 네모는 Resource. 네모 안의 네모는 자원의 수를 나타내는 instance

- Assignment edge : 자원 -> 프로세스 (이 프로세스가 해당 자원을 가지고 있다.)

- Request edge : 프로세스 -> 자원 (이 프로세스가 해당 자원을 요청. 아직 획득하진 못함)

>> Deadlock의 필요조건 : "Hold & Wait " : 자원을 하나 가지고 있고 다른 프로세스가 소유한 다른 자원을 달라고 요청하는 상황

📌Deadlock Necessary Condition

1. Mutual exclusion : 오직 하나의 프로세스만 특정 리소스 소유 가능
   • mutual exclusion 을 보장 안한다면 wait 할 상황이 없다..! 그냥 여러 프로세스가 자원 공유해서 쓰면 됨.
2. Hold and wait : 한 리소스를 hold한 상태에서 이미 다른 프로세스가 소유한 리소스를 요청하면 wait >> hold&wait
3. No preemption : 먼저 실행된 프로세스가 자발적으로 리소스를 놓아야 다른 프로세스가 사용가능
   • preemption 이 된다면 critical section 에 프로세스 여러 개 들어가는 상황. 1번과 유사하게 데드락 발생 가능성 제로
4. Circular wait : Hold & wait 의 좁은 개념. 리소스를 wait 하는 상황이 싸이클을 이루는 것

>> 이 조건이 다 만족했다고 데드락이라는 것이 아닌 데드락이 발생하면 이 조건들은 모두 만족해야한다.!!

따라서 1.3번은 당연하고 2번은 4번의 큰 개념이므로 4번이 있는지만 체크하면 데드락의 가능성을 체크할 수 있는 것!!

4번이 성립하지 않으면 데드락은 없다..! but 4번이 있다고해서 무조건 데드락인건 아니궁!!

위에서 설명한 " 사이클이 있어도 데드락이 발생하지 않는 경우" 에 대해서 설명드리겠습니다.

데드락의 키워드는 어떠한 경우에도 "indefinetly blocking" 입니다. 어떤 해결책이 없이 계속 데드락이 걸리는 상황이어야하는 것입니다. 

위의 그림은 사이클이 있다고 하더라도 리소스를 가지고 있던 프로세스가 리소스를 release하면 원래는 request edge가 assignment edge 로 바뀌면서 사이클이 사라질 수 있습니다. 즉 상황이 지나면 사이클이 사라지기 때문에 사이클이 있다고 해서 무조건 데드락이 있는 것은 아닙니다.

조금 더 자세하게 알아보면, 위의 그림은 리소스의 instance가 여러 개라서 데드락이 발생하지 않았습니다. 

즉, 리소스의 인스턴스 개수에 따라 데드락 발생확률이 다릅니다.

>> 만약 1개의 인스턴스를 가지고 있고 싸이클이 있다면 데드락의 필요충분조건입니다.

>> 만약 여러 개의 인스턴스를 가지고 있고, 싸이클이 있다면, 필요조건입니다.

📌 Methods for Handling Deadlocks

- Deadlock Avoidance : 프로그램을 수행하면 데드락이 발생할 것이 미리 보이면 safe state( 절대 데드락이 발생하지 않을 상태 )까지 프로그램 수행을 멈춤

- Deadlock Prevention : 데드락의 필요조건(4가지)을 없애는 것

- Deadlock Detection, Recover : 데드락이 발생했다면, 데드락이 발생한 것을 탐지(Detection)하고 데드락을 없애기위해 회복절차를 거치는것(recover : kill or rollback)

위에서 설명햇던 네가지를 좀더 자세하게 알아보자.

Deadlock Prevention

: 데드락 발생가능 이유를 제거합니다. 즉 위에서 설명한 필요조건을 한 개를 제거합니다.

조건을 없애는게 불가능하면 infeasibility 하다고 하고, 조건을 없앨 수는 있으나 부작용이 생기는 것을 side effect가 발생할 수 있는 조건이라고 명시하겠습니다. 그러면 데드락의 필요조건 네 가지에 대해 살펴봅시다.

1. Mutual exclusion 
   • mutual exclusion을 없애면 race condition이 발생할 수도 있습니다. 즉 불가능한 조건이므로 " infeasibility " 입니다.
2. Hold and wait
   • 자원을 다른 프로세스가 소유하지 않았을때만 요청을 할 수 있게 하면 됩니다. 그렇게 된다면 request edge 가 바로 assignment edge가 됩니다. 
   • 위의 방식으로 진행하게 되면 낮은 자원 이용률을 야기시키는 " side effect " 가 발생합니다.
     • 예 ) p1 이 r1,r2를 요청하고 싶어합니다. 이때 p2 가 r2를 사용중이라면 p1 은 r1 에게도 r2에게도 요청신호를 보낼 수 없게 되어 자원 이용률이 떨어지는 것입니다. 동시에 p1은 그 어떤 자원도 쓰고 있지 않기때문에 "starvation" 현상도 일어날 수 있습니다.
3. No preemption
   • cpu에서는 preemption 이 가능하나, 프린터는 preemption이 된다면 출력 결과물이 이상하게 출력될 것이다. 즉 infeasible 하다고 볼 수 있다.
4. Circular wait : Hold & wait 의 좁은 개념. 리소스를 wait 하는 상황이 싸이클을 이루는 것
   • 모든 리소스에 우선순위를 매겨서 순서대로만 요청할 수 있도록 한다. 이와같이 리소스 타입에 ordering을 보장하면 circular wait 이 발생할 일이 없다.
     • 예 ) r1 - r2 즉 r1을 먼저 요청해야한다고 가정하자. p1 이 r1을 소유하고 그 다음에 r2를 소유 요청을 할 수 있다. 이때 p1이 r1을 소유한 상태에서 p2는 r1 요청을 보내도 기다려야하고 r1을 먼저 요청한 후 r2를 요청해야하기때문에 r2로는 아예 요청 신호조차 보낼 수 없다.
   • 2번과 마찬가지로 리소스를 활용할 확률이 떨어지기 때문에 side effect로 resource utilization 이 떨어진다고 볼 수 잇다

Deadlock Avoidance

가정 : 리소스 타입별 리소스 요구량의 최대의 개수가 몇 개인지 알고 있어야한다. 왜냐하면 요청 개수 보다 이용가능한 리소스의 개수가 많다면 그때는 절대 데드락이 일어나지 않는 safe state에 머물기때문에 deadlock avoidance를 할 이유가 없어지기 때문이다.

따라서 우리는 resource-allocation state 를 알고 있어야한다. 여기에는 이용가능한 자원의수, 할당된 자원의 수, 최대 요청 개수에 관련된 정보가 있다.

목표 : 프로세스가 안전하지 못한 상태로 진입하지 않도록 보장하는 것. >> 안전하지 못한 상태이면 데드락의 가능성이 생기기 때문

unsafe state : # of requests <= # of available resources.

기본 로직 : 프로세스 수행 시퀀스를 정해 안전한 상태를 만족하도록 하는 것.

다실 말하자면, 프로세스의 수행 순서를 정하는 것이 핵심이다. 안전한 순서라고 함은 할당된 자원과 추가적으로 요구된 자원이 가용한 자원보다 적거나 같으면 된다. 이때 먼저 수행하고 있던 프로세스가 종료되면 리소스를 반환한다. 종료되는 프로세스가 증가할수록 이용가능한 자원은 증가하게되고 그럴수록 안전한 상태를 유지하는 확률이 높아진다.

이용가능한 자원의 개수가 12개라고 해보자 현재 사용중인 자원의 수는 5+2+2 = 9 개 이므로 이용가능한 자원의 수는 => 3개이다.

이용가능한 자원의 수보다 요청 개수가 작아야하므로  P1을 먼저 수행해야 하는 것이다.

이렇게 되면 현재 이용하고 있는 자원의 수는 11개로 12개보다 작기 때문에 데드락에 걸리지않는다. 이때 P0,P2는 stop 상태여야한다. 

언제까지 ?? p1이 종료될때까지!!

이후 p1의 종료되고 쓰던 자원들을 다 반환 하면 이용중인 자원의수는 5+2 = 7개 로 5개의 자원이 추가로 이용가능하기에 p0 에게 먼저 할당. p2는 stop >> p0 terminate >> p2 에게 할당.

즉 프로세스가 종료되면서 자원들을 반환하기때문에 안전한 순서라고 함은 요청 개수가 작은 프로세스를 먼저 수행하고 나머지 프로세스들은 대기하고 있는 것이다. 이후 자원을 할당받은 프로세스가 종료되고 자원을 반환하면 대기하고 있던 프로세스 중 요청개수가 적은 프로세스에게 할당하는 순서로 진행된다.

이처럼 자원의 개수가 데드락을 결정하는데 중요한 요소이다. 이때 자원의 개수에 따라 조금은 다르게 적용해야한다.

1. single instance of resource type : 모든 리소스 타입이 한개라면 사이클이 있다면 바로 데드락이기 때문에 데드락 탐지가 매우 용이하게 적용된다. RAG 만 이용하면된다.

2. multiple instance of resource type : 인스턴스 개수가 여러개라면 사이클이 발생해도 데드락이 발생하지 않을 수 있어서 

    Banker's Algorithm을 사용할 것이다.

+  Banker's Algorithm : 위에서 설명했던 안전한 상태를 만족시키는 순서를 만드는게 핵심입니다. 즉, 리소스를 적게 요구하는 프로세스를 먼저 실행하는 것. 시간이 지날수록 리소스 수가 많아지니까. 

이용가능한 자원의 수가 1/2/0 인데 이 숫자보다 작게 요청개수를 가진 프로세스는 프로세스 2 이다 (1/1/0) 이므로.

따라서 프로세스2에게 먼저 할당한다. 이후에 프로세스가 종료되고 자원을 반환하면 2/3/0 이 된다.

( 이용가능한 자원의 숫자에 need 자원의 수는 더할 필요 없다. 어차피 available - need + need 이기 때문에..)

가능한 프로세스 넘버가 작은 순서대로 먼저 실행하지만 요청개수가 이용가능한 자원의 수보다 많다면 그 다음 프로세스로 넘어가는것.

따라서 프로세스 2 -> 프로세스 3 -> 프로세스 4 -> 프로세스 1 순서로 수행될 것이다.

Deadlock Detection

single instance 에서는 사이클 생기면 데드락 발생

multiple instance  에서

avoidance 에서의 need는 미래의 리소스 요청 개수였다면  need = MAX - allocation

여기서는 need는 현재 실제 요청값을 나타낸다. 왜냐하면 detection은 현재 데드락이 발생했는지 보는 것이기 때문.

need = real requests6

Deadlock Recovelry

1. kill the process - 사이클이 없어질때까지

• 어떤 프로세스를 종료시킬지?
  • 관련 모든 프로세스를 종료
  • step by step 으로 사이클이 안보일대까지 종료 ( 우선순위 or. 얼마나 많은 리소스를 추가적으로 요구할건지)

2.  checkpoint & rollback

check point : 문맥을 저장하는 곳. 체크포인트로만 롤백 가능.

💡MONITORS

Problems of semaphore :

• difficult to code
• difficult to prove correctness
• requires volumtary cooperation
• single misuse affects entire system

세마포어를 사용하기에는 사용자 입장에서 코딩하기가 어렵다 보니 보다 쉬운 monitor가 도입된 계기를 만들었다.

monitior

• 응용프로세서가 효과적으로 호출할 수 있도록 하는 동기화 메커니즘
• a high-level abstraction that provides a convenient and effective mechanism for process synchronization

semaphore 사용 시 일어날 수 있는 상황

>> Mutual Exclusion property is violated

: mutex의 값을 증가시키는 signal 함수만 호출되어서

critical section에 여러 개의 process 가 들어와서 mutual exclusion을 위배한다.

>> Deadlock occurs

: mutex의 값을 감소시키는 wait 함수만 호출되어서

어떤 프로세스도 critical section 에 들어갈 수 없고 프로세스들 모두가 wait 함수에서

빠져나오지 못해 deadlock 이 걸리는 상황이 발생한다.

GOAL : Only one process at a time can be active within the monitor

Monitor는 class 와 매우 유사하게 구현하고 있다.

Critical Section에 1개의 process 만 들어오게 하기 위해서 즉 mutual exclusion 을 만족하기 위해서

class에

• Condition Variable 추가
• Wait, Signal 추가 >> condition variable에 접근할 수 있는 함수

1. Condition Variable하나의 프로세스만 active하고, 다른 프로세스는 기다리게 하도록 도입된게 condition 변수 입니다.
   condition 변수가 있어야 mutual exclusion 을 보장할 수 있습니다.
   condition 변수에 접근이 가능한 함수는 오직 wait 과 signal 함수만 가능합니다.
2. wait()
   세마포어의 wait 함수는 while을 문을 만족해야 suspend 상황이 발생하지만
   Monitior의 wait 함수는 호출되면 무조건적인 suspend 상황을 발생시킵니다.
   즉 wait 함수를 호출한 프로세스는 컨디션 변수를 기다리는 큐에 insert 되도록 합니다.
3. singal()
   signal 함수는 wait 함수에 의해 큐에서 기다리고 있는 프로세스를 깨우는 함수입니다.

Monitor Code

1. 공유 변수 busy 는 처음에 false라서 처음 진입하는 프로세스는 조건문에 걸리지 않아 바로 critical section 에 즉 resource에 접근이 가능합니다.

2. 이후 이 프로세스는 busy 를 true로 바꿉니다.

3. 두번째로 오는 프로세스는 if 문에 걸려서 wait 함수를 호출합니다

 >> mutual exclusion 속성 보장을 위해.

위에 사진처럼 monitor는 구현되어 있지만. 사용자는 옆에 사진처럼 함수만 호출하면 되는 아주 편리한 기능을 제공합니다.

즉 acquire() 를 통해 resource를 확보하고,

release()를 통해 리소스를 놓아 줍니다.

💡Liveness

Monitor를 사용 시에 synchronization을 지키기 위해 가장 중요한 함수는 wait 함수 입니다.

즉, 두 번째로 오는 프로세스는 첫 번째 프로세스가 critical section에 있으면 기다리게 됨.

wait 함수를 잘못 사용하게되면 프로세스가 아예 progress를  안하게 되는데 이것을 "DeadLock" 이라고 한다.

"deadlock"은 어떤 경우에도 빠져나갈 수 없는 경우를 말하며 이를 "indefinite block" 이라고도 한다.

💡Deadlock

two or more processes are waiting indefinitely for an event that can be caused by only one of the waiting processes

즉, 두 개 이상의 프로세스가 무한정 수행이 안되는 경우를 의미한다.

1. S와 Q를 1로 초기화 ( == binary semaphore)

2. p1이 wait(Q)를 호출 Q=0 으로 바뀜

3. Context Switch 돼서 P0 가 wait(S)를 호출해서 S가 0으로 바뀜.

4. 다시 context switch 되어 p1이 wait(s) 호출 시에 s=0이므로 밑으로 수행 안됨 즉 wait 함수 빠져나가지 못한다.

5. p0에서도 wait(q) 호출 시 빠져나가지 못함. 

두 개의 프로세스 다 wait함수 빠져나가지 못해 deadlock

+ starvation : indefinite blocking. A process may never be removed from the semaphore queue in which it's suspended 

                      deadlock과의 공통점은 무한정으로 waiting하는 것.

💡Bounded buffer problem

Producer / Consumer process가 따로 있고,

공유 변수는 circular queue로 구현

mutex는 producer와 consumer 모두 circular queue에 접근하기에 필요하다.

• Binary
  mutex의 값이 1이나 0인 경우
• counting
  mutex의 값에 제약 조건 없이 정수 값을 가짐.

ch 3장 에서는 Synchronization을 위해 Spin Lock 을 사용했었음.

Counting 의 경우에는 full 함수는 producer가 차있는 갯수를 나타내고 empty 함수는 비어있는 슬롯의 개수를 나타냅니다.

Full 0으로 초기화 / empty 는 N으로 초기화

• Producer : empty가 0이라면 wait(empty) 에 진입
• Consumer : full이 0이라면 wait(full) 에 진입

1. 버퍼의 크기를 체크하는 것은 wait(empty)로

2. producer가 critical section에 진입했다면 consumer는 진입하지 못하게 설정하기 위해 wait(mutex)로 관리한다.

cf. critical section은 여기서 버퍼를 채우는 영역이다.

3. critical section에서는 buffer에 item을 추가한다.

4. signal(mutex)로 mutex 값을 1로 바꾸고 consumer도 c-s에 진입 가능하게 해준다.

5.signal(full)을 호출로 buffer에 한 개 추가됐다고 설정해준다.

1. wait(full) : buffer에 차 있는 것이 없다면 waiting

2. wait(mutex) : producer가 critical section 에 진입해 있다면 mutex의 값은 0으로 consumer는 waiting

3. signal(mutex)

4. signal(empty) : buffer에 있는 아이템을 사용했기에 비어있는 공간이 늘어났다고 설정해준다.

>> Dining-Philosophers Problem

: 다섯 명의 철학자가 같이 밥을 먹는데 젓가락이 철학자 사이에 하나씩 있고 서로 share한다고 가정한다. 한 사람이 젓가락을 사용하면 옆 사람을 기다려야하는 상황이다.

다섯 명의 동기화를 위해서 spinlock 사용은 복잡하여 semaphore 변수를 사용한다.

chopstick[5]는 다 1로 초기화.

chopstick[i]는 본인 기준 왼쪽 젓가락

chopstick[ (i+1) % 5 ] 는 오른쪽 젓가락

둘 중 하나라도 wait 문을 빠져나오지 못한다면 젓가락 사용 불가.

두 개를 다 확보했더라면

// eat

식사가 끝나면 왼쪽.오른쪽 젓가락에 대한 signal 함수를  호출

semaphore 값 1증가 다른 철학자 식사 가능

문제점 : Deadlock

다들 첫 번째 line인 왼쪽 젓가락을 가지고 있고, 오른쪽 젓가락의 available을 기다리면 아무도 식사 못하는 deadlock 상황.

Solution 1 : 동시에 앉을 수 있는 철학자는 최대 4명으로 설정

Solution 2 : 두 개의 젓가락을 집는 것을 atomic 하게

Solution 3 : 젓가락 집는 순서 명시

    (1) Odd philosopher 는 왼쪽 젓가락 먼저

    (2) Even philosopher 는 오른쪽 젓가락 먼저