[ 운영체제 ] 20. Deadlock 예방/회피/감지 , Recovery

Deadlock Prevention

https://min-h-study-review.tistory.com/252

 

저번 강의에서 배웠던 Deadlock 이 발생하는 조건 중에

하나만이라도 충족시키지 못하게 만들면 Deadlock을 예방할 수 있지 않은가 하는 아이디어

 

= 교착상태 발생 조건 중 하나를 제거하기

 

 

● Mutual exclusion

: 상호 배제를 없앴다면, 모든 자원을 공유하게 한다.

 

 

하지만, 현실적으로 모든 자원을 공유하는 건 불가능하다.

 

● Hold and wait

: 점유와 대기를 없앤다.

자원을 점유한 상태에서 다른 자원을 기다리는 것을 못하게 한다.

 

= 특정 프로세스에게 자원을 모두 할당 or 아예 할당 X

 

배고픈 철학자 문제에 적용해보면, 포크 기다릴 거면 왼쪽 포크는 내려놓고 기다려라

 

 

하지만, 자원의 활용도가 너무 낮아진다.

 

● No Preemption

: 하나의 프로세스가 자원을 뺏을 수 없으면 기다리거나 순서가 꼬일 일이 없다.

 

 

하지만 모든 자원이 선점 가능한 것이 아니다.

ex) 프린터

 

 

 

● Circular Wait

: 원형 대기 조건을 없앤다.

 

모든 자원에 번호를 할당하고, 그 번호에 대해 오름차순으로 자원을 할당하면

원형대기가 발생하지 않는다.

 

철학자에게 낮은 포크를 먼저 들고 높은 포크를 들 수 있게 한다면 문제가 발생하지 않는다.

 

https://youtu.be/zQDNXklvdUw?si=PL6uFQOVMrvm8v_9

 

 

하지만, 모든 자원에 번호를 붙이는 것이 어려운 작업일 뿐더러

어떤 자원에 어떤 번호를 붙이냐에 따라 활용률이 달라진다.

 

 

 

교착상태 예방은

교착상태가 발생하지 않도록 보장은 해주지만

그 외에 잃는 것들이 너무 많아지는 방식이다.

 

 

---

Deadlock Avoidance

Deadlock의 원인 = 무분별한 자원 할당 으로 간주한다.

 

• 안전 순서열 ( Safe sequence )
  : 교착 상태 없이 안전하게 Process(thread)들에 자원을 할당할 수 있는 순서
  
  
• 안전 상태  ( Safe state )
  : 교착 상태 없이 모든 Process(thread)가 자원을 할당받고 종료될 수 있는 상태
    = 안전 순서열이 있는 상태
  
  
• 불안전 상태 ( Unsafe state )
  : 교착 상태가 발생할 수도 있는 상태 
    = 안전 순서열이 없는 상태

 

 

● Avoidance Algorithm

 

Case1 ) Resource 내의 Instance 가 1개일 때

            = Resource - Allocation Graph 를 그린다.

 

 

 

 

Thread T가 R한테 나중에 자원 할당 요청을 할 예정이라는 뜻이다..

 

- 나중에 떄가 되면 Claim Edge는 Request Edge가 된다.

- 

 

 

Claim edge가 원형이 되어도 Unsafe 상태로 간주한다.

 

---

 

Case2 ) Resource 내의 Instance 가 여러 개일 때

            = Banker's Algorithm 를 사용한다.

 

 

 

알고리즘 시작에 앞서 알아야 하는 정보

 

● Process 를 통해

   - 요구량 

   - 현재 사용량

 

 

● 추가적으로

   - 할당 가능 자원

   - 할당한 자원

   - 남은 자원 ( 할당 가능 - 할당한 )

 

 

이렇게 있다고 했을 때

 

총 할당 가능한 자원: 12개

할당 한 자원 ( = 현재 사용량 총 합 ) = 5+2+2 = 9개

남은 자원 : 3개

 

 

======  Step1  ======

 

현재 남은 자원을 사용해서 자신의 일을 마칠 수 있는 Process는 P2이다.

할당된 2개에, 현재 사용량 3개 중 2개를 추가해서 요구량인 4개를 맞춰준다.

 

그렇게 작업을 마친 P2는 자신이 사용했던 자원 4개를 반환한다.

 

 

할당 한 자원 ( = 현재 사용량 총 합 ) = 5 + 0+2 = 7개

남은 자원 : 5개

 

 

======  Step2  ======

 

그럼 지금 남은 자원 5개로 요구량을 맞출 수 있는 Process는 P1밖에 없다.

P1에게 남은 자원 5개를 주어서 현재 사용량과 합한 개수인 10개로 요구량을 맞춰준다.

 

그렇게 작업을 마친 P1는 자신이 사용했던 자원 10개를 반환한다.

 

 

할당 한 자원 ( = 현재 사용량 총 합 ) = 0+ 0+2 = 2개

남은 자원 : 10개

 

 

======  Step3  ======

 

그럼 지금 남은 자원 10개로 요구량을 맞춰야 하는 Process는 P3밖에 없다.

P3에게 남은 자원 7개를 주어서 현재 사용량과 합한 개수인 9개로 요구량을 맞춰준다.

 

그렇게 작업을 마친 P3는 자신이 사용했던 자원 9개를 반환한다.

 

 

할당 한 자원 ( = 현재 사용량 총 합 ) = 0+ 0+0 = 0개

남은 자원 : 12개

 

 

 

→ 안전 순서열 : P2 ▶ P1 ▶P3

 

만약 남은 자원으로 어느 프로세스/스레드의 요구를 만족시킬 수 없을 때

교착상태가 일어난다.

 

 

 

 

n = Thread의 개수

m = Resource의 개수

 

Available : 할당 가능한 자원의 수

Allcocation : 현재(이미) 할당한 자원의 수

Max : 요구량

Need : Thread가 더 필요한 자원의 수

 

 

 

예제 1)

 

 

- A는 총 10개 중에서 Allocation에 지금 총 7개가 할당되어 있음 , 3개 사용 가능

  B는 5개 중에서 2개 할당 , 3개 사용 가능

  C는 7개 중에서 5개 할당, 2개 사용 가능

 

 

======  Step1  ======

할당 가능한 개수로 어느 Thread의 요구량을 충족시킬 수 있을까?

현재 A = 3개 , B = 3개 , C=2개

 

T0 = A → 현재 0개 할당, 7개 요구    ▶ 가능 XX

T1 = A  → 현재 2개 할당,3개 요구    ▶ 가능

        B  → 현재 0개 할당,2개 요구    ▶ 가능

        C  → 현재 0개 할당,2개 요구    ▶ 가능

 

 

T1 먼저 할당해서 실행하고 자원 반납받는다.

 

...

 

 

Deadlock Detection

: System이 Deadlock 상태에 들어가게 하는 걸 막지는 않는다.

  대신 교착상태가 일어났을 떄 감지를 하여 대응하는 방식이다.

 

 

프로세스가 자원을 요구 ▶ 일단 할당

                                           if 교착상태 발견 ▶  회복

 

즉, DeadLock을 허용한 채로 돌아가게 하고, 발견되면 처리를 하자는 것이다.

 

 

● 감지 방법

▶  Wait - for graph

: Thread Dependency에 대한 Graph를 그린다. 

 대신 Resource가 아니라 어느 Thread가 먼저 쓰고 그 다음 Thread가 쓰는지만 나타낸다.

 

여기에서 Cycle이 생기면 교착상태가 발생한다.

 

Cycle이 있는지는 DFS로 찾는다. 

O(n^2)

 

 

 

Detection Algorithm 을 언제 돌려야 하냐?

▶얼마나 자주 Deadlock이 일어날 것 같은지

▶ Deadlock이 일어났을 때 얼마나 많은 Thread가 영향을 받을지

 

알아내야 할 때

 

 

주로, 할당 받기 위해 보내는 요청이 즉시 받아들여지지 않을 때

Detection algorithm을 실행하면 된다. 

 

 

 

Recovery from Deadlock

 

: DeadLock 상태에 빠졌을 떄 Recover 하는 방법

 

 

1. Process Termination

   방법1 : Deadlock에 걸린 프로세스를 다 종료한다.

               ▶ 손해가 너무 크다.

 

   방법2 : Deadlock이 사라질 때까지 프로세스 하나씩 종료한다.

              ▶ 프로세스가 사용한 자원 순서로 종료시킨다.  =  종료하는 순서를 정하는 것도 기준이 다르다.

 

 

 

2. Resource Preemption

 

Selecting a Victim : 자원을 뺏었을 때 손해가 가장 적은 희생양 하나 선택해서, 자원을 뺏어서 실행 

                                  ▶ 피해자의 눈물은 무시하는 거냐

 

 

Rollback :프로세스를 safe 상태로 rollback하고, 다시 시작한다. 

 

 

Starvation : Victim의 횟수를 정해서 .정해진만큼만 Victim 당하도록 한다.

 

 

 

 

(출처)

한동대학교 고윤민교수님 - OS