Deadlock
Deadlock Problem
- 데드락 : 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때 무한 대기에 빠지는 상황 (시스템 자원에 대한 요구가 뒤엉켜 복잡한 상태)
Deadlock Characterization
- 데드락의 발생조건 4가지 중 하나라도 발생하지 않는 것이 데드락을 예방하는 방법 (데드락은 4가지 조건이 모두 만족돼야 발생)
- Mutual exclusion(자원의 상호배제 조건 방지): 한 번에 여러 프로세스가 공유자원을 사용할 수 있게함.
- Hold and wait (점유대기 조건 방지): 프로세스 실행에 필요한 자원을 한꺼번에 요구. 허용할 때까지 작업을 보류함. 따라서 나중에 또다른 자원을 점유하기 위한 대기 조건을 성립하지 않도록 하는게 목적.
- No preemption (비선점 조건 방지): 높은 우선 순위의 프로세스가 자원을 선점할 수 있게함.
- Circular wait (순환 대기 조건 방지): 자원을 순한 형태로 대기 X. 한 쪽 방향으로만 자원을 요구할 수 있도록 함.
Resource-Allocation Graph
- 자원 할당 그래프: 시스템의 자원 할당 상황을 그래프로 그린 것 (데드락 판별을 위해 사용)
- P: 프로세스, R: 시스템 내 자원 유형, 점: 인스턴스
- P->R 화살표 (Request Edge): 프로세스가 해당 자원 요청
- R->P 화살표 (Assignment Edge): 해당 자원이 프로세스 할당 돼있음.
- Resource-Allocation Graph에 Cycle 존재? -> 데드락이 존재할 가능성이 있음.
Resource-Allocation Graph Example
- 데드락 존재. R2에 있는 인스턴스 2개가 P1, P2에 할당됐는데 P3의 자원할당요구(Request Edge)가 들어옴 ->사이클 생성
- 프로세스들이 자신의 Resource를 소유한 채, 다른 프로세스에 할당된 Resource를 요구. 이것이 사이클을 만들어 Deadlock 형성.
- P3가 R2 자원 요청하는 상황. R2자원은 P1 & P4에 할당 ->P3의 자원요청은 이루어지지 않고 데드락 발생
- But, P4가 실행을 끝내고, R2 인스턴스 하나를 반납-> P3는 R2 자원을 가질 수 있고 데드락이 풀림
Deadlock Prevention
-
Mutual Exclusion: 어떤 자원들은 공유 자체가 불가능 (ex 프린터, 키보드). 따라서 Mutual Exclusion은 무조건 보장돼야 함.
-
Hold and wait: process가 어떤 자원을 요구할 때, 모든 자원을 요청/할당 받는다면 프로세스가 필요한 각 자원을 한 번에 요구. 따라서 한 번에 한 프로세스만 자원을 소유하게 됨(All or nothing) -> But 효율성 떨어짐. Starvation 발생 가능성
-
No premption: Preemtion을 허락하는 것이 Deadlock Prevention 위한 가장 현실적 방법. 우선순위 높은 프로세스가 낮은 프로세스에게 자원을 가져오고 점유함.
but) 자원이 뺏긴 프로세스는 현재까지 작업이 무효화 됨 & 자원이 뺏겨 대기하던 프로세스가 다시 작업을 실행하기 위해선 resource를 할당받아야되는데, 이 과정에서 starvation 발생 가능성 존재. -
Circular Wait: 모든 리소스에 번호를 부여. 프로세스 오름차순 순으로 자원을 요구 but 너무 복잡해서 안 쓴다고 함.
Deadlock Avoidance
- 데드락 회피를 위해선 safe state에 있던 프로세스가 Unsafe state로 이동하면, state를 바꾸게 한 원인을 찾아 취소하는 방식으로 safe state로 되돌려야 함.
- safe sequence를 통해 state가 어떤 상황인지 파악 가능.
공부방