센로그
8. Deadlocks 본문
◆ Deadlock 이란?
둘 이상의 프로세스가 서로가 점유하고 있는 자원을 무한정 기다리고 있는 상황
ex)
데드락 예시를 보자.
다음은 데드락이 발생할 가능성이 있는 코드이다.
S랑 Q라는 세마포어가 있다. 각 세마포어의 초기값은 1이다. (binary semaphore)
P0과 P1이 번갈아가며 한줄씩 실행된다고 하자.
P0은 wait(S) → wait(Q) 순서로, P1은 wait(Q) → wait(S) 순서로 실행될 것이다.
P0에서, 우선 wait(S)는 통과하고 S--를 한다. (S=0)
P1에서도, 우선 wait(Q)는 통과하고, Q--를 한다. (Q=0)
그런데 이때, Q=S=0이 되었으므로,
이제부터 P0는 P1이 홀딩하고 있는 Q를 기다리고, P1은 P0가 홀딩하고 있는 S를 기다리게 된다.
둘이 서로 가지고 있는 리소스를 서로 무한정 기다리면서 아무것도 못하고 있는 것임.
※ 위 코드에서, S, Q 가져가는 순서를 두 프로세스에서 똑같이 하면 데드락 발생 안함
즉 P1에서도 wait(S)를 한 후 wait(Q)를 하면 괜찮다.
◆ Deadlock이 발생할 4가지 조건
다음 네가지 조건이 모두 충족할 때 데드락이 발생한다.
- Mutual exclusion
상호 배제. 즉, 한 공유리소스에 동시에 접근할 수 있는 스레드 수가 하나일 때 - Hold and wait
: 공유 자원이 여러개가 있을 때, 하나를 이미 점유를 하고 다른 자원을 기다릴 때
(식사하는 철학자 문제에서 왼쪽 젓가락을 들고 오른쪽 젓가락을 기다리는 경우) - No preemption
: 리소스를 쥐고 있기만 하고 안 내려놓는 상황. (강제로 빼앗기지 않는 상황)
자발적으로 공유 자원의 점유를 포기 하지 않는 경우 - Circular wait
: 순환적으로 기다리는 경우.
T0은 T1을 기다리고, T1은 T2를 기다리고, ..., Tn은 T0을 기다리는 경우
(식사하는 철학자 문제에서 모두가 동시에 왼쪽 젓가락을 드는 경우.)
→ 4개의 조건 중 하나라도 충족하지 못하게 만들면 데드락이 발생하지 않는다.
◆ Resource Allocation 그래프
자원 할당 그래프.
데드락 상황을 더 잘 이해할 수 있게끔 하는 그래프 표현에 대해 알아보자.
- 동그라미 : 스레드
- 네모 : 리소스
- 네모 안의 점 : 리소스 인스턴스의 개수
- 스레드 → 리소스 : 어떤 스레드가 리소스를 요청하는 경우 (Request Edge)
- 리소스 → 스레드 : 어떤 스레드가 리소스를 할당받은 경우 (Assignment Edge)
- 그림에서, T2는 R1, R2를 사용하고 있고, R3를 기다리고 있다.
- 시간이 지나 T3가 R3의 사용을 끝내서 R3 → T3 엣지가 사라지면,
이제 T2가 R3를 할당받고 R3 → T2 엣지가 생길 것이다.
위 그림에서는 사이클이 없다.
- 그래프에 사이클이 없다면, 항상 데드락이 없는 상태임.
(사이클이 있다 == 어떤 한 노드에서 출발해서 다시 그 노드로 돌아오는 경로가 있다)
※ 사이클이 있다고 해서 항상 데드락이 발생하는 건 아님!
단, 각 리소스마다 인스턴스가 하나씩만 있는 경우, 사이클 있으면 항상 데드락이 발생함
ex)
사이클과 대드락
사이클이 두 개 있다. 데드락 발생함.
사이클이 한 개 있지만, 데드락 발생 안함.
T2와 T4가 서로 의존성이 없으니, 둘중 아무나 리소스 하나를 놓으면 데드락 안 걸림.
◆ Methods for Handling Deadlocks
데드락을 핸들링하는 방법들에 대해 살펴볼 것이다.
1) 애초에 데드락에 빠지지 않도록 하는 방법
: 프로그래머가 데드락 조건 4가지 중 하나를 무효화함으로써 사전에 막는다.
: 운체가 모든 상황을 확인해서 데드락을 회피
2) 데드락에 들어갈 수는 있으나, 빠져나갈 수 있도록 하는 방법
: 운체가 모니터링을 하면서 데드락이 발생했을 때 후속조치(데드락이 발생한 프로세스를 죽이거나 자원 회수)를 해준다.
3) 데드락이 일어났어도 안 일어난 것처럼 동작하는 방법
: 데드락을 무시한다.
◆ Deadlock prevention
자원을 가져가는 순서를 정해서, 데드락 조건(보통 circular wait)을 방지
이전에 봤던 4가지 데드락 조건 중에서, 하나라도 만족 못 시키면 데드락 발생 안함.
4가지 조건 중에, 우리가 건들 만한 것은 "circular wait"을 방지하는 방법이다.
Deadlock prevention - Circular Wait 방지
각 리소스를 가져가는 순서를 정하는 방법이다.
리소스에 인덱스를 부여하고, i번째 리소스인 Ri를 가져가는 순서를 F(Ri)라고 하자.
만약 F(Ri) < F(Rj)라면, Ri를 무조건 Rj보다 먼저 얻도록 하는 방법이다.
예를들면 이런 식.
first_mutex를 second_mutex보다 항상 먼저 얻도록 한다.
이렇듯 자원을 할당하는 순서를 정해놓으면, cycle이 생길 수 없다.
◆ Deadlock Avoidance
운체가 모든 상황을 확인해서 데드락을 회피하는 방식.
만약 잠재적 데드락 발생 가능성이 생기는 상황인 경우, 자원이 충분하더라도 자원을 안 준다.
prevention에서 리소스 할당 방식을 제한하는 방식은 시스템 성능이 떨어질 수 있다.
→ Deadlock avoidance는 비교적 자유롭게 리소스를 이용할 수 있도록 해놓은 것임
우선 리소스가 어떻게 요청되는지에 대한 정보를 가지고있어야 한다.
젤 간단하게는, 각각의 스레드가 각각의 리소스를 최대 얼마만큼 가져갈 것인지 정해놓는 방식을 사용할 수 다.
이를 기준으로 데드락이 발생할 것 같은지 판단해서, 발생할 거 같으면 리소스 할당을 안해주는 것.
이를 구현하기 위해 Safe State 방식이나 Resource-Allocation Graph 방식을 사용할 수 있다.
■ Safe State 방식
우선, 데드락이 발생하지 않는 상태인 safe state를 정의한다.
(unsafe state는 데드락이 발생할 가능성이 있는 상태를 의미)
어떤 리소스 요청이 들어오면, 이 리소스를 할당해줘도 시스템이 계속 safe state에 남아있을 것인지, 아니면 데드락이 발생할 수도 있는 unsafe state로 갈 것인지 판단해준다. 그리고 safe state가 되는 경우에만 할당을 해주는 방식
그러면 safe state인지 아닌지는 어떻게 판단할까?
→ 가능한 스레드 시퀀스 중 Safe State Sequence가 하나라도 존재한다면 Safe State라고 판단한다.
※ 스레드 시퀀스란?
스레드 시퀀스란 스레드 간 자원 할당 순서를 나타낸 시퀀스이다.
T1부터 시작해서 Tn까지 차례대로 자원을 할당하는 경우, <T1, T2, ..., Tn>이라고 적는다.
- 각 스레드는 자신이 사용중인 리소스 양과, 앞으로 얼마나 요청할지에 대한 정보를 가지고 있다.
- 운영체제는 현재 이용 가능한 자원, 현재 각각의 스레드에게 할당되어 있는 자원, 각각의 스레드들이 사용하고 반납할 자원들의 정보를 바탕으로 잠재적 Deadlock의 유무를 판단한다.
- 시스템의 스레드들이 요청하는 모든 자원을, 데드락을 발생시키지 않으면서도 차례로 모두에게 할당해 줄 수 있는 자원할당 순서를 Safe State Sequenece라고 한다. 이것이 존재하는 경우 Safe State라고 할 수 있다.
리소스는 총 12개가 존재한다고 하자.
이 스레드들을 통해 Safe State Sequence를 만들 수 있는지 확인해보자.
1) 우선 현재 12개 중 9개를 현재 사용하고 있으므로, 남은 리소스는 3개이다.
T0이나 T2는 꼴랑 3개의 리소스로는 니즈를 충족시키지 못한다. 따라서 T1부터 2개의 리소스를 할당해주도록 한다.
2) T1이 리소스를 다 사용하면 4개가 반납될 것이다. 그러면 남는 리소스는 5개가 된다.
T2는 꼴랑 5개의 리소스로는 니즈를 충족시키지 못한다. 따라서 이번에는 T0에 5개의 리소스를 할당해준다.
3) T0가 리소스를 다 사용하면 10개의 리소스가 반납될 것이다. 그러면 남는 리소스는 10개가 된다.
이제 T2는 7개의 리소스를 통해 니즈를 충족할 수 있다.
→ 스레드 시퀀스 <T1, T0, T2> 순서로 리소스를 할당하면, 스레드들이 요청하는 모든 자원을, 데드락을 발생시키지 않으면서도 차례로 모두에게 할당해줄 수 있음을 알 수 있다. 따라서 Safe State Sequence이므로, 이제 이 순서대로 자원을 할당해주면 된다.
■ Resource-Allocation Graph 방식
리소스가 싱글 인스턴스인 경우를 가정한다.
Deadlock Avoidance 방식에서 Resource-Allocation 그래프를 활용하려면 한가지 엣지를 추가로 도입해야 한다.
- Claim edge
: 미래에 이 리소스를 요청할 가능성이 있다면 점선으로 표시한다.
만약 실제로 요청을 하여 할당을 받은 경우, 점선(claim edge)을 실선(assignment edge)으로 바꾼다.
이때, 사이클이 생기지 않는 경우에만 할당해줘야 한다. 사이클이 생길 것 같으면 할당해주면 안됨!
이런 과정들을 실행중에 계속 트래킹하면서, 사이클이 없는 상태를 유지하며 자원을 할당하는 것이 이 방식이다.
◆ Deadlock detection and recovery
운영체제가 데드락 발생을 파악하고, 관련된 프로세스들을 죽이는 방식.
데드락이 발생하도록 그냥 놔뒀다가, 발생하면 후속 조치를 취해주는 방식.
그러나 데드락을 수정하려면 어쨌든 데드락이 발생했는지 알아야 함!
이를 위한 알고리즘이 필요하다
→ wait-for 그래프에 사이클이 있으면 데드락이다!
■ Detection
: wait-for 그래프
다음 두 그래프는 같은 상황을 나타낸 그래프이다.
※ 리소스가 싱글 인스턴스인 경우에만 wait-for 방식으로 그릴 수 있음!
기존 resource-allocation 그래프에서는, 스레드가 리소스를 기다리는 것을 엣지로 표시했다.
wait-for 그래프에서는, 스레드가 다른 스레드(기다리는 리소스를 홀딩하고 있는 스레드) 를 기다리는 것을 엣지로 표시하는 것임.
만약 wait-for 그래프에 사이클이 있다면, 데드락이 발생한 것으로 판단하는 알고리즘이다.
(리소스들이 싱글 인스턴스만을 가질 때 순환이 존재한다면 데드락이 발생한 것이다.)
■ Recovery
데드락이 발생하면 결국 복구를 해야 한다.
어떻게 할까?
1) 데드락이랑 연관되어있는 프로세스를 아예 죽여버리는 방법
프로세스를 하나씩 죽여보면서 아직도 사이클 있는지 확인해보거나, 아예 다 죽여버리는 방식으로 복구할 수 있다.
2) 프로세스 전부를 죽이는 게 아니라, 그냥 할당된 리소스를 다시 빼앗아오는 방식.
그러나 고려할 사항 많아서 실제 구현하는게 쉽진 않다.
<고려사항 예시>
- 누구의 리소스를 뺏을 것인가?
- 리소스를 뺏었을 때 생기는 문제는 어떻게 해결할 것인가?
(아예 리소스 할당 전으로 돌리는 등의 조치를 취해야 함)
'CS > 운영체제' 카테고리의 다른 글
| 10. Virtual Memory (0) | 2023.12.04 |
|---|---|
| 9. Main Memory (0) | 2023.12.04 |
| 7. Synchronization Examples (0) | 2023.10.16 |
| 6. Synchronization Tools (0) | 2023.10.14 |
| 5. CPU Scheduling (0) | 2023.09.20 |
