운영체제 [deadlock 해결방법]

Deadlock prevention 

 

Deadlock이 발생하지않게 조건발생을 막음

모든 자원의 공유 허용-->불가능 

모든 자원 선점 허용--> 불가능 or 매우 비효율적 

필요한 자원 한번에 모두 할당--> starvation 현상 발생, 자원 낭비 발생 

circular wait 조건 제거--> 자원 낭비 발생 

Deadlock prevention--> 심각한 자원낭비--> 현실적으로 불가능 

Deadlock avoidance 

-시스템의 상태를 계속감시
- Deadlock 발생 가능성이 있는 자원 요청에 대해 요청 보류
- Safe state를 유지 

Safe state

- 모든 프로세스가 정상 종료가 가능한 상태
- safe sequence를 유지 

Unsafe state 

-Deadlock 발생 가능 한 상태
- 반드시 발생 x 

Deadlock avoidance 방법 

Banker's Algorithm

- safe sequence가 존재하는지 확인 

(각 프로세스에게 자원을 할당하고 돌려받는것을 가정했을 때 safe state릉 만족하는지)

Habermann's algorithm

- Banker's Algorithm의 확장
- 여러종류의 자원 고려

Deadlock Avoidance 특징

- 시스템 항상 감시--> high overhead
- Low resource utilization
- 비효율적

Deadlock Detection & Recovery

Detection

- 주기적으로 deadlock 발생 확인

Graph reduction 

- Resource Allocation Graph(RAG)를 이용
- 주어진 RAG에서 edge를 하나씩 지워가는 방법 
- edge가 모두 지워지면, deadlock X
- High overhead

Deadlock Recovery

 

Process termination

- Deadlock 상태인 프로세스 중 일부 종료
- cost를 기준으로 cost가 작은 프로세스를 종료

Resource preemption

- Deadlock 상태 해결을 위해 선점할 자원 선택
- 해당 자원을 가지고 있는 프로세스를 종료 시킴
- cost를 기준으로 자원을 선점

Checkpoint-restart method

-프로세스의 수행 중 특정 지점마다 context를 저장
- Rollback을 위해 사용