Deadlock prevention methods
- 4개의 deadlock 발생 필요 조건 중 하나를 제거
1) Exclusive use of resources 조건 제거
- 모든 자원을 공유 자원으로 사용
- 독립적 실행이 불가능
- 비현실적
2) Non-preemptible resources 조건 제거
- 모든 자원을 선점 가능하게 사용
- 선점 당할 경우 모든 자원 반납하고 다시 처음부터 시작 -> 비효율
- 선점 당할 경우 모든 자원 반납하고 그 지점 저장 -> 복잡해짐
- 비현실적
3) Hold and wait 조건 제거
- 필요한 자원을 한 번에 할당 받기
- 필요하지 않는 상황에도 자원을 가지고 있음
- 자원 낭비
4) Circular wait 조건 제거
- 자원들에게 순서를 부여하여 순서대로 사용
- 사용할 수 있는 자원이 있어도 사용 못함
- 예시 : P1은 R1, R2, R3를 사용할 예정. P2는 R1, R2 사용할 예정. P1이 먼저 R1을 요청 -> P2는 R1을 사용 못하니 대기 -> P2는 R3를 사용할 수 있으나 사용 못하므로 자원 낭비
- 자원 낭비
Deadlock avoidance methods
- 시스템의 상태를 계속 감시
- 시스템을 항상 safe state로 유지
* safe state : 모든 프로세스가 정상적으로 종료 가능한 상태
* unsafe state : deadlock 상태가 될 가능성이 있는 상태
- 가정 상황이 있기 때문에 비실용성
- Avoidance 방법을 위한 4가지 가정
* 프로세스의 수가 고정
* 자원의 종류와 수가 고정
* 프로세스가 요구하는 자원 및 최대 수량을 알고 있음
* 프로세스는 자원을 사용 후 반드시 반납
- 장점
* Deadlock 발생하지 않음
- 단점
* high overhead : 항상 시스템을 감시하기 때문에
* low resource utilization : additional need(아래 표에서)는 무조건 필요한 자원이 아닌 추정 값, 따라서 필요없는 자원을 가지고 있을 수 있어서 자원 활용도가 낮음
1) Banker's algorithm
- 한 종류의 자원이 여러 개 일 때
- 동작
* 자원 종류 : R, 자원 개수: 10, 프로세스 개수: 3
* 현재 자원 할당 상태 : P1 - 1, P2 - 5, P3 - 2
* 여유 자원 상태 : 2
* 방법 : P1이 자원 1개를 요청 -> 자원 1개를 할당한다고 가정했을 때, 이후 나머지 자원으로 safe sequence를 만들 수 있으면 빌려주기, 아니면 빌려주지 않음
- 예시 1
* 자원 종류 : R, 자원 개수: 10, 프로세스 개수: 3
* 현재 자원 할당 상태 : P1 - 1, P2 - 5, P3 - 2
* 여유 자원 상태 : 2
* 실행 종료 순서 : P1 -> P2 -> P3
* 방법 : P1에게 여유 자원 2개를 할당하면, P1은 일을 마치고 자원 3개를 반환 -> P3에게 자원 3개를 할당하면, P3은 일을 마치고 자원 5개를 반환 -> P2 동일
- 예시 2
* 자원 종류 : R, 자원 개수: 10, 프로세스 개수: 3
* 현재 자원 할당 상태 : P1 - 1, P2 - 5, P3 - 2
* 여유 자원 상태 : 2
* 방법 : P1, P2, P3에게 여유 자원 2개를 할당해도 safe sequence를 만들 수 없음 -> deadlock될 가능성
2) Habermann's algorithm
- banker's algorithm의 확장판
- 여러 종류의 자원을 고려
- 동작은 동일
- 예시
* 자원 종류 : Ra, Rb, Rc
* 각각의 자원 개수 : 10, 5, 7
* 프로세스의 개수 : 5
* 방법 : 처음 여유 자원 개수는 각각 2, 3, 0 -> 여유 자원으로 할당할 수 있는 프로세스는 P2와 P4 -> 과정 동일
Deadlock detection and deadlock recovery methods
- 교착 상태 탐지 및 복구
1) Deadlock detection
- Graph reduction : Resource allocation graph(RAG)를 사용해서 주기적으로 deadlock 탐지
* RAG : 방향 그래프를 이용하는 방법
* Node가 많을 경우, 검사 주기가 짧을 경우 high overhead
* 동작
+ unblocked process에 연결된 모든 edge 제거
~ unblocked process : 자원을 요청했을 때 자원을 할당 받을 수 있는 프로세스
+ 위 과정을 반복
+ 모든 edge가 지워지면 deadlock 아님, edge가 남으면 deadlock 상태
2) Deadlock recovery
- deadlock 검출 후 해결하는 과정
- checkpoint-restart method
* 아래 두 방법은 모두 프로세스를 강제 종료하기 때문에 프로세스의 수행 중 특정 지점마다 context 저장
* Rollback을 위해 사용
* 프로세스 강제 종료 후, 가장 최근 checkpoint에서 재시작
(1) Process termination
- deadlock 상태에 있는 프로세스를 강제 종료, 이후 다시 재시작
- termination cost model : 종료 시킬 deadlock 상태의 프로세스 선택
* cost 종류 : 우선 순위, 프로세스 종류, 남은 수행 시간, 종료 비용 등
(2) Resource preemption
- Deadlock 상태 해결 위해 선점할 자원 선택, 이후 자원을 빼앗긴 프로세스는 강제 종료
- termination cost model : 동일
본 내용은 한국기술교육대학교 김덕수 교수님의 유튜브 강의를 듣고 정리한 내용입니다.
'Software Courses > Operating System' 카테고리의 다른 글
| [Memory] Memory allocation : Continuous memory allocation (0) | 2020.12.09 |
|---|---|
| [Memory] Memory Basic (0) | 2020.12.07 |
| [Deadlock] Deadlock and Resources types (0) | 2020.12.04 |
| Process Synchronization and Mutual Exclusion (0) | 2020.12.02 |
| Process Scheduling (0) | 2020.12.01 |