운영체제 - 반효경 7강
Deadlock
- 각자 리소스를 가지고 있으면서 상대방이 가지고 있는 리소스를 필요로함 -> 근데 각 프로세스는 리소스를 내어 놓지 않아 진행이 되지 않는 상태
Deadlock: 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태Resource- 하드웨어, 소프트웨어 등을 포함하는 개념(I/O device, CPU cycle 등)
- 프로세스가 자원을 사용하는 절차 : Request -> Allocate -> Use -> Release
Deadlock 발생의 4가지 조건
Mutual exclusion: 매 순간 하나의 프로세스만이 자원을 사용 가능No preemption: 프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음Hold and wait: 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음Cicrular wait: 자원을 기다리는 프로세스간에 사이클이 형성되어야 함
Resource-Allocation Graph
- 그래프에서 cycle이 없으면 deadlock 아님
- 있으면 그 다음 조건을 확인
- 하나의 자원 당 인스턴스가 하나면 deadlock
- 하나 이상이면 직접 확인 필요
- 1번 그림은 deadlock, 2번은 deadlock 아님
Deadlock의 처리 방법
Deadlock을 미연에 방지
Deadlock Prevention: Deadlock의 4가지 필요 조건 중 어느 하나가 만족되 지 않도록 하는 것Deadlock Avoidance: deadlock이 발생할 가능성이 없는 경우에만 자원을 할당
Deadlock 생긴 후 처리
Deadlock Detection and recovery: 프로그램에 문제가 있을 때 Deadlock이 발생했는지 검사해서 있다면 복구하는 전략- recovery
- Process termination : deadlock 연관 프로세스 모두 termination 혹은 해결될 때 까지 하나씩 termination 하기
- Resource Preemption : 자원을 뺏어 Deadlock 해결 -> safe state로 rollback한 뒤 restart(Starvation 문제)
Deadlock에 대해 신경 X
Deadlock Ignorance
현대에서는 Dealock Ingnorance를 사용 -> 다른 방법들은 오버헤드가 큼
Deadlock Prevention
Mutual Exclusion- 공유해서는 안되는 자원은 반드시 mutual exclusion이 성립해야 함
Hold and Wait프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있어서는 안됨
프로세스 시작 시 모든 필요 자원들을 할당하게 하는 방법
자원이 필요한 경우 보유 자원을 모두 놓고 다시 요청
No preemption- 프로세스가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원을 빼앗음
- 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작
- state를 쉽게 save하고 restore 할 수 있는 자원에서 주로 사용(CPU, memory)
Circular Wait- 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당
하지만 Deadlock Prevention은 Utilization 저하, throughput 감소, starvation 문제 등이 발생한다(비효율적)
Deadlock Avoidance
- 자원 요청에 대한 부가 정보를 이용해 자원 할당이 deadlock으로부터 안전한지 동적으로 조사해 안전한 경우에만 할당
- 인스턴스당 하나의 자원일 때 : Resource Allocation Graph Algorithm 사용 -> DFS, BFS와 같은 알고리즘 사용해서 cycle 여부 확인(O(n^2) 걸림)
- 인스턴스당 하나 이상일 때 : Banker’s Algorithm 사용
출처)
| [운영체제 - 이화여자대학교 | KOCW 공개 강의](http://www.kocw.net/home/cview.do?cid=3646706b4347ef09) |
This post is licensed under CC BY 4.0 by the author.