교착상태(Deadlock)
-
일어나지 않을 사건을 기다리며 진행이 멈추는 현상
-
식사하는 철학자 문제 : 교착상태 설명해주는 상황
-
원탁에 다섯명의 철학자가 앉아 있고 철학자 사이에 포크가 있으며 포크를 두개를 사용해야만 음식을 먹을수 있음
→ 다섯명이 동시에 왼쪽 포크를 사용하면 누구도 식사 불가능
→ "교착상태"에 빠졌다 -
철학자 = 프로세스 or 스레드
포크 = 자원
생각하는 것 = 자원을 기다리는 것
포크는 한번에 하나의 스레드에 접근 = 임계구역
-
-
교착 상태를 해결하는 방법
- 교착상태가 발생했을때 상황을 표현하기
- 교착상태가 생기는 근본적인 원인 파악 하기
자원 할당 그래프(Resource allocation graph)
- 어떤 프로세스가 어떤 자원을 활용하고 있는지, 프로세스가 어떤 자원을 기다리고 있는지 표현하는 그래프
- 자원 할당 그래프를 그리는 규칙
- 프로세스는 원, 자원종류는 사각형으로 그리기
- 사용할수 있는 자원의 개수는 사각형내 점으로 표시하기
- 프로세스가 자원을 할당받아 사용중이면 화살표로 표시하기 (예시) 하드디스크 → 프로세스A
- 프로세스가 자원을 기다리고 있으면 화살표로 표시하기
(예시) 하드디스크 ← 프로세스A
교착상태 발생조건
-
교착상태 발생 조건
- 하나라도 만족하지 않으면 교착상태 발생 하지 않음
- 모두 만족되면 교착상태 발생 가능성이 생김
-
상호배제
-
점유와 대기
-
비선점
-
원형 대기
조건 설명 상호배제(mutual exclusion) 자원 이용이 한번에 하나의 프로세스만 가능하기 때문에 교착상태가 발생 프로세스가 사용하는 자원을 다른 프로세스가 사용할수 없어서 교착상태가 발생 -------------------------------------- ----------------------------------------------------------------------------------------- 점유와 대기(hold and wait) 자원을 할당받은 상태에서 다른 자원을 할당 받기를 기다릴때 교착상태 발생 --------------------------------------- ----------------------------------------------------------------------------------------- 비선점(nonpreemptive) 프로세스가 자원을 비선점 하고있어서 교착상태가 발생 어떤 프로세스고 강제로 자원을 뺏지못해서 교착상태가 발생 ---------------------------------------- --------------------------------------------------------------------------------------- 원형 대기(circular wait) 프로세스들과 자원이 원의 형태일 때 발생할 수 있음
교착상태 해결방법
- 교착상태 예방(사전 방법)
- 교착상태 발생 조건에 부합하지 않게 자원을 분배하는 방법
- 교착상태 회피(사전 방법)
- 교착상태 위험이 있을시 자원을 할당하지 않는 방법
- 교착상태 회복(사후 방법)
- 제약없이 자원을 할당하다가 교착상태가 검출될때 교착상태를 회복하는 방법
교착상태 예방
- 교착상태 발생 필요조건을 충족하지 못하게 하는 방법
- 상호배제 제거하기
- 모든 자원을 공유가능하게 만든다
- 이 방법은 현실적으로 사용하기는 어렵다
- 점유와 대기 제거하기
- 운영체제가 특정프로세스에 자원을 모두 할당하거나 전혀 할당하지 않는 방식
- 자원의 활용률이 낮아짐(대기가 길어짐)
- 많은 자원을 활용하는 프로세스가 자원을 사용할 타이밍을 잡기가 어려워 진다
- 비선점 제거하기
- 프로세스가 이용중인 자원을 빼앗아 오는 방법
- 일부자원을 사용할때는 효과가 있으나 모든 자원에 적용할수 없음 (CPU자원을 가능하나 프린터 자원은 어렵다)
- 원형대기 제거하기
- 모든 자원에 번호를 붙이고 오름차순으로 자원할당 하는 방법
- 상호배제, 점유와 대기, 비선점 제거방법보다 현실적임
- 수많은 자원에 번호를 붙이는것은 어려움. 번호를 붙이는 방법에 따라서 자원활용률이 떨어짐
교착상태 회피
-
교착상태가 발생하지 않을 정도로만 자원을 할당하는 방식
-
전제 조건: 자원에 많으면 교착상태가 발생하지 않는다 = 한정된 자원의 무분별한 할당으로 교착상태가 발생
-
교착상태 회피관련 용어
- 안전순서열(safe sequence) : 교착상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
- 안전 상태(safe state)
- 교착상태가 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당받고 종료될수 있는 상태
- 안전순서열대로 프로세스에 자원을 배분한 상태
- 불안전 상태(unsafe state)
- 교착상태가 발생할 수 있는 상황
- 안전 순서열이 없는 상황
-
안전 상태 일때
- 자원사용 방법 : 운영체제에 자원 요청 → 운영체제에게 자원 할당 받음 → 자원사용이 끝나면 자원을 반환
- 자원사용 방법 : 운영체제에 자원 요청 → 운영체제에게 자원 할당 받음 → 자원사용이 끝나면 자원을 반환
-
불안전 상태 일때
- P3에 자원 하나를 줌
- P3에 자원 하나를 줌
교착상태 검출 후 회복
- 교착상태 검출 후 회복 : 교착상태를 인정하고 사후조치하는 방식
- 선점을 통한 회복
- 교착상태가 해결될 때 까지 다른 프로세로부터 자원을 강제로 빼앗아 다른 프로세스에게 자원을 할당하는 방법
- 프로세스 강제 종료를 통한 회복
- 교착상태에 놓인 프로세스를 모두 강제종료 함
→ 여러프로세스의 작업 내용을 잃음 - 교착상태가 없어 질때 까지 한 프로세스를 강제종료 함
→ 교착상태가 없어지는지 계속 확인해야 해서 오버해드가 발생됨
- 교착상태에 놓인 프로세스를 모두 강제종료 함
교착상태 무시
- 타조 알고리즘
- 교착상태를 무시하는 방법
- 가끔생기는 문제로 무시한다
마무리 문제📚
P.374-375
1번 교착상태설명으로 틀린것 고르기 (4)번
1) 교착 상태는 다양한 상황에서 발생할수 있다
2) 교착 상태는 자원 할당 그래프로 표현 할수 있다
3) 교착 상태는 일어나지 않을 사건을 기다리며 무한히 대기하는 현상을 의미한다
4) 식사하는 철학자 문제에서 단 한명의 철학자가 식사해도 교착상태가 발생한다
2번 교착상태가 발생할수 있는 네가지 조건
정답 : 상호배제, 원형 대기, 비선점, 점유와 대기
3번 두가지중 교착 상태가 발생할 위험이 있는 그래프는? (2)번
1)
2)
P.386-387
1번 교착상태를 회복하는 방법에대해 틀린것은? (2)번
1) 교착상태가 발생하는 조건 중 하나를 충족하지 않게하면 교착상태를 예방할수 있다
2) 교착상태가 발생했으면 이를 회복할수 없다
3) 안전상태를 유지할수 있는 경우에만 자원을 할당하면 교착상태를 회피할수 있다
4) 교착상태의 검출 및 회피방식에서 운영체제는 주기적으로 교착상태발생 여부를 검사한다
2번 다음과 같은 상황에서 프로세느 P2에 자원 두개를 나누어 줬다고 가장한다. 프로세스P2가 실행을 올바르게 종료한 뒤 자원을 반납하면 남는 자원은 몇개인가? 5개
| 프로세스 | 요구량 | 현재사용량 |
|---|---|---|
| P1 | 10 | 5 |
| P2 | 4 | 2 |
| P3 | 9 | 2 |
| 할당가능 자원 | 할당한 자원 | 남은자원 |
|---|---|---|
| 12 | 9 | 3 |
3번 교착상태에 대한 대처방법중 타조 알고리즘에대한 설명은?(2)번
1) 교착상태를 회피하는 방법
2) 교차상태를 무시하는 방법
3) 교착상태를 검출하고 회복하는 방법
4) 교착상태를 예방하는 방법
4번 교착상태 예방에 대한 설명을 틀린것은? (4)번
1) 상호배제 조건을 없애므로써 교착상태를 예방할 수 있다
2) 점유와 대기 조건을 없앰으로써 교착 상태를 예방할 수 있다
3) 비선점 조건을 없앰으로써 교착상태를 예방할 수 있다
4) 원형대기 조건을 추가함으로써 교착상태를 예방할 수 있다
