반응형
본 글은 (KOCW) 운영체제, 이화여자대학교 반효경 교수님의 강의를 듣고 내용을 요약 및 정리했습니다.
스터디를 진행하는 것에 목적이 있으며, 자세한 사항은 여기를 참고하시면 됩니다.
데드락 문제
데드락?
- 일련의 프로세스들이 서로가 가진 자원을 기다리며 block 된 상태
Resource(자원)
- 하드웨어, 소프트웨어 등을 포함하는 개념
- I/O device, CPU cycle, memory space, semaphore 등
- 프로세스가 자원을 사용하는 절차
- Request, Allocate, Use, Release
예시
- EX
- 시스템에 2개의 tape drive가 있다
- 프로세스 P1과 P2 각각 하나의 다른 tape drive를 보유한 채 다른 하나를 기다리고 있다
- EX
- 이진 세마포어 A와 B가 있다
- 프로세스 P1이 A 자원을 얻은 상태에서 Context Switching이 발생하여 P2에게 CPU 제어권이 넘어갔고, P2가 B 자원을 얻었다
- 다시 Context Switching이 발생하여 프로세스 P1에게 CPU 제어권이 넘어갔고, P1이 B자원을 얻고 싶어 하지만 이미 P2가 B 자원을 가지고 있음
- P2가 A자원을 얻고 싶어 하지만 이미 P1이 A 자원을 가지고 있음
- -> 무한히 서로를 기다림
Deadlock 발생의 4가지 조건
- Mutual Exclusion (상호 배제)
- 매 순간 하나의 프로세스만이 자원을 사용할 수 있음
- No preemption (비선점)
- 프로세스는 자원을 내어 놓을 뿐 강제로 빼앗기지 않음
- Hold and wait (보유 대기)
- 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음
- Circular wait (점유 대기)
- 자원을 기다리는 프로세스 간에 사이클이 형성되어야 함
- 프로세스 P0, P1, ..., Pn이 있을 때
- P0는 P1이 가진 자원을 기다림
- P1은 P2가 가진 자원을 기다림
- ...
- Pn은 P0가 가진 자원을 기다림
Resource-Allocation Graph (자원 할당 그래프)
- 정점은 프로세스 혹은 자원을 나타내며, 간선은 자원을 요청하거나 할당한다는 의미
- 자원에서 프로세스로 나가는 화살표: 자원이 프로세스에 속해있다
- 프로세스에서 자원으로 나가는 화살표: 자원을 요청만 하고 얻지 못한 상태
데드락 판단
- 그래프에 cycle이 없으면 데드락이 아니다
- 그래프에 cycle이 있으면
- 자원 당 하나의 인스턴스만 있는 경우에는 데드락이다
- 자원 당 여러 인스턴스가 존재하는 경우에는 데드락 가능성이 있다
- 왼쪽 그래프는 P1에게 R2 자원 1개가 할당되어 있고 P2에게 R2 자원이 할당되어 있는 상황에서 P3가 R2 자원 하나를 요구
- P2는 R3 자원을 요청하고, R3는 P3가 가지고 있다 이때 P1은 R1을 요청하지만, 이것은 P2가 가지고 있으므로 모든 프로세스가 자원을 반납할 수 없음 -> 데드락
- 오른쪽 그래프는 P1에게 R2 자원이 할당되어 있고 P4에게 R2 자원이 할당되어 있는 상황
- P3가 R2 자원을 요구하면 P4가 R2 자원을 반납하면 되므로 문제가 없다 -> 데드락이 아님
데드락의 처리 방법
Deadlock Prevention (데드락 예방)
- 자원 할당 시 데드락의 4가지 필요조건 중 어느 하나가 만족되지 않도록 하는 것
Deadlock Avoidance (데드락 회피)
- 자원 요청에 대한 부가적인 정보를 이용해서 데드락의 가능성이 없는 경우에만 자원을 할당
- 시스템 상태가 원래 상태로 돌아올 수 있는 경우에만 자원 할당
Deadlock Detection and recovery (데드락 탐지 및 회복)
- 데드락 발생은 허용하되, 그에 대한 탐지 루틴을 두어 데드락 발견 시 회복
Deadlock Ignorance (데드락 무시)
- 데드락을 시스템이 책임지지 않음
- UNIX를 포함한 대부분의 OS가 채택
Deadlock Prevention (데드락 예방)
- Mutual Exclusion (상호 배제)
- 공유해서는 안되는 자원의 경우 반드시 성립해야 함
- Hold and wait (보유 대기)
- 프로세스가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨
- 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작됨
- 상태를 쉽게 저장하고 복구할 수 있는 자원에서 주로 사용 (CPU, Memory)
- Circular Wait
- 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원을 할당
- 순서가 3인 자원 Ri를 보유 중인 프로세스가 순서가 1인 자원 Rj를 할당받기 위해서는 우선 Ri를 반납해야 함
=> Utilization 저하, Throughput 감소, Starvation 문제
Deadlock Avoidance (데드락 회피)
- 자원 요청에 대한 부가 정보를 이용해서 자원 할당이 데드락으로부터 안전한 지를 동적으로 조사해서 안전한 경우에만 할당
- 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법
- 시스템이 안전 상태에 있으면 데드락이 아니며, 불안전 상태에 있으면 데드락의 가능성이 있다
- 데드락의 회피는 시스템이 불안전 상태에 들어가지 않는 것을 보장한다
- 자원 유형 당 1개의 인스턴스만 존재
- 자원 할당 그래프 알고리즘
- 자원 유형 당 여러 개의 인스턴스 존재
- 은행원 알고리즘
Safe State(안전 상태)
- 시스템 내의 프로세스들에 대한 safe sequence(안전 순서열)가 존재하는 상태
Safe Sequence (안전 순서열)
- 프로세스의 sequence <P1, P2,..., Pn>이 안전하려면 Pi(1 <=i <=n)의 자원 요청이 "가용 자원 + 모든 Pj(j <i)의 보유 자원"에 의해 충족되어야 함
- 조건을 만족하면 다음 방법으로 모든 프로세스의 수행을 보장
- Pi의 자원 요청이 즉시 충족될 수 없으면 모든 Pj(j<i)가 종료될 때까지 기다린다
- P(i-1)이 종료되면 Pi의 자원 요청을 만족하여 수행한다
자원 할당 알고리즘
- Claim edge (예약 간선) Pi -> Rj
- 프로세스 Pi가 자원 Rj를 미래에 요청을 할 수 있음을 뜻함 (점선으로 표시)
- 프로세스가 해당 자원 요청 시 request edge(요청 간선)으로 바뀜(실선으로 표시)
- Rj가 반납되면 assignment edge(할당 간선)은 다시 예약 간선으로 바뀐다
- 요청 간선의 할당 간선 변경 시 (점선을 포함하여) 사이클이 생기지 않는 경우에만 요청 자원을 할당한다
- 사이클 생성 여부 조사시 프로세스의 수가 n일 때 O(n^2) 시간이 걸린다
은행원 알고리즘
- 가정
- 모든 프로세스는 자원의 최대 사용량을 미리 명시
- 프로세스가 요청 자원을 모두 할당받은 경우 유한 시간 안에 이들 자원을 다시 반납
- 방법
- 기본 개념: 자원 요청 시 안전 상태를 유지할 경우에만 할당
- 총 요청 자원의 수가 가용 자원의 수보다 적은 프로세스를 선택 (그런 프로세스가 없으면 불안전 상태)
- 그런 프로세스가 있으면 그 프로세스에게 자원을 할당
- 할당받은 프로세스가 종료되면 모든 자원을 반납
- 모든 프로세스가 종료될 때까지 이러한 과정을 반복
예제
- A 자원은 10개의 인스턴스 B 자원은 5개의 인스턴스 C 자원은 7개의 인스턴스가 존재
- Allocation은 현재 각 프로세스에 할당된 자원의 수를 뜻한다
- Max는 각 프로세스마다 최대로 할당받고 싶은 자원의 수를 뜻한다
- Available은 각 자원이 프로세스에게 추가로 할당할 수 있는 가용 자원의 수를 뜻함
- Need는 각 프로세스가 현재 최대로 필요로 하는 자원의 수를 뜻하며 Max에서 Allocation을 뺀 값이다
- 자원은 현재 가용 자원을 보고 Need 만큼 자원을 줄 수 있는 프로세스를 하나도 찾지 못하면 불안전한 상태가 된다
- 자원을 줄 수 있는 프로세스가 있다면 해당 프로세스에게 자원을 주고, 프로세스가 끝날 때 모든 자원을 가져옴
- 해당 과정을 반복하면 <P1, P3, P4, P2, P0>라는 안전 순서열을 만들 수 있다
자원이 남아있음에도 불구하고 데드락이 발생할까 봐 프로세스에 자원을 할당하지 않고 가지고 있는 상황이 발생 -> 비효율적, 낭비
Deadlock Detection and Recovery (데드락 탐지 및 회복)
데드락 탐지
- 자원 유형 당 하나의 인스턴스만 존재
- Wait-for 그래프 알고리즘
- 자원 유형 당 하나의 인스턴스만 존재
- Wait-for 그래프
- 자원 할당 그래프의 변형
- 프로세스만으로 node 구성
- Pj가 가지고 있는 자원을 Pk가 기다리고 있는 경우 Pk -> Pj
- 알고리즘
- wait-for 그래프에 cycle이 존재하는지 주기적으로 조사
- O(N^2)
- Wait-for 그래프 알고리즘
- 자원 유형 당 여러 개의 인스턴스가 존재
- 은행원 알고리즘과 유사한 방법 활용
Wait-for 그래프 (자원 당 하나의 인스턴스)
- 자원을 빼 버리고 실선을 이으면 됨
은행원 알고리즘 변형(자원 당 여러 개의 인스턴스)
- Request는 추가 요청 가능량이 아니고 현재 실제로 요청한 자원량을 나타낸다
- <P0, P2, P3, P1, P4>라는 안전 순서열이 존재하므로 데드락이 아니다
- 기존 은행원 알고리즘에 비해 현재를 중시하고 낙관적인 알고리즘이라 볼 수 있다
데드락 회복
- 프로세스 종료
- 모든 데드락 상태인 프로세스를 강제 종료
- 데드락 사이클이 없어질 때까지 하나씩 프로세스를 강제 종료
- 자원 선점
- 비용을 최소화할 희생 프로세스를 선정
- 안전 상태로 롤백하여 프로세스를 재시작
- Starvation 문제
- 동일한 프로세스가 계속 희생 프로세스로 선정되는 경우
- 비용 요소에 롤백 횟수도 같이 고려해야 함 (단순히 비용만 최소화하면 안 된다는 의미)
Deadlock Ignorance (데드락 무시)
- 데드락이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않음
- 데드락이 매우 드물게 발생하므로 데드락에 대한 조치 자체가 더 큰 오버헤드일 수 있음
- 만약, 시스템에 데드락이 발생한 경우 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후 직접 프로세스를 죽이는 등의 방법으로 대처함
- UNIX, Windows 등 대부분의 OS에서 채택하였음
정리
- Deadlock?
- 일련의 프로세스들이 서로가 가진 자원을 기다리며 block 된 상태
- Deadlock이 발생하기 위한 4가지 조건에 대해 설명해 주세요
- Deadlock은 Mutual Exclusion, no Preemption, Hold and wait, Circular wait 4가지 조건을 충족할 때 발생합니다
- 각각의 조건을 설명하면, 하나의 프로세스만 자원을 사용할 수 있으며, 프로세스는 자원을 할당받고 직접 반납하기 전에 빼앗기지 않으며, 자원을 할당받은 프로세스가 다른 자원을 할당받기 위해 대기하는데 자신의 자원을 반납하지 않고 할당받은 상태로 대기하는 상황에 서로 다른 프로세스가 서로의 자원을 요청하며 사이클이 형성되어 있는 상황을 말합니다.
- 3가지만 충족한다면 왜 Deadlock이 발생하지 않을까요? & 예방하는 방법
- 3가지 조건만 충족하게 된다면 언젠가는 자원을 할당받을 수 있게되기 때문입니다
- 각 조건에 대해서 생각해보면, 하나의 프로세스만 자원을 사용하는 게 아니라 여러 프로세스가 자원을 사용할 수 있게 되면 데드락이 발생하지 않습니다. 하지만 공유 자원에 대해 동시에 접근하면 동기화 문제가 발생할 수 있기 때문에 현실적으로 사용되진 않습니다
- 다른 프로세스에 할당된 자원을 빼앗을 수 있게되면 우선순위가 높은 프로세스가 자원을 빼앗아 먼저 처리한 후 대기하던 프로세스가 자원을 할당받아 처리할 수 있게 됩니다. 하지만 우선순위에 따라 기아 상태가 발생할 수 있지만 데드락은 발생하지 않습니다
- 자원을 보유하고 대기하는 것이 아니라 필요한 자원을 모두 할당받을 수 있을 때만 자원을 할당받게 하면 데드락이 발생하지 않습니다
- 자원의 할당에 있어서 서로 할당받고 다음 자원을 할당받기위해 대기하여 사이클이 생기는 게 아니라 순서를 지정하여 사이클이 생기지 않게 한다면 데드락이 발생하지 않습니다
- 왜 현대 OS는 Deadlock을 처리하지 않는가?
- 데드락이 발생하는 것은 드문 경우이기 때문에 데드락을 고려하여 자원을 할당하는 것은 오버헤드가 너무 크기 때문입니다
- 데드락을 감지하고 이에 대한 처리를 개발자가 직접하는 것이 더 효율적이고 비용이 적다고 생각하기 때문입니다
반응형
'CS' 카테고리의 다른 글
| OS - Memory Management2 (0) | 2023.11.01 |
|---|---|
| OS - Memory Management (0) | 2023.11.01 |
| OS - Process Synchronization2 (0) | 2023.10.30 |
| OS - Process Synchronization (1) | 2023.10.30 |
| OS - CPU Scheduling (0) | 2023.10.19 |
