🚕교착 상태란
🍖식사하는 철학자 문제
모든 철학자가 포크를 집어 식사를 하면 누구도 식사를 할 수 없다.
- 철학자 : 프로세스 혹은 스레드
- 포크 : 자원
- 생각하는 행위 : 자원을 기다리는 것
- 교착 상태
일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상
- 교착 상태를 해결하기 위해서
- 교착 상태가 발생했을 때의 상황을 정확히 표현
- 교착 상태가 일어나는 근본적인 이유 이해
📊자원 할당 그래프
- 어떤 프로세스가 어떤 자원을 사용하고 있고, 어떤 자원을 기다리고 있는지를 표현하는 그래프
교착 상태는 자원 할당 그래프를 통해 단순하게 표현 가능하다.
자원 할당 그래프 그리는 규칙
- 프로세스는 원으로, 자원의 종류는 사각형으로 표현한다.
- 사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현한다.
- 프로세스가 어떤 자원을 할당받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시
- 프로세스가 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시
예시
- SSD 자원 3개, CPU 자원 2개, 프린터 1개
- A는 SS를, B와 C는 CPU를, D는 프린터를 할당받아 사용 중
- E는 프린터를, F는 CPU의 할당을 기다리고 있다.
철학자 문제 자원 할당 그래프
교착 상태가 발생한 상황은 자원 할당 그래프가 원의 형태를 띄고 있다.
🧩교착 상태 발생 조건
-
상호 배제
한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태 -
점유와 대기
자원을 할당받은 상태에서 다른 자원을 할당 받기를 기다리는 상태 -
비선점
어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 상태 -
원형 대기
프로세스들이 원의 형태로 자원을 대기하는 상태
원의 형태를 띈다고 해서 반드시 교착 상태가 발생하는 것은 아니다.
🚒교착 상태 해결 방법
💉교착 상태 예방
- 애초에 교착 상태가 발생하지 않도록 하는 방법
- 교착 상태 발생 조건 중 하나를 없애버리기
상호 배제를 없애기
- 모든 자원을 공유하게 만든다는 말과 같다.
- 이론적으로는 가능하지만 현실적인 방법은 아니다.
점유와 대기를 없애기
-
특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분한다.
-
단점
- 자원의 활용률을 낮출 수 있는 방식
- 많은 자원을 필요로 하는 프로세스의 기아 현상 야기할 수 있음
비선점 조건을 없애기
- 선점이 가능한 자원(CPU 등)에 한해 효과적이다.
하지만 모든 자원이 선점 가능한 것은 아니다.
원형 대기 조건을 없애기
-
자원에 번호를 붙이고 오름차순으로 할당하면 원형 대기 발생X
-
철학자 예시
낮은 포크에서 높은 포크 순으로 집도록 하면 된다.
-
단점
- 모든 자원에 번호를 붙이는 것은 어려운 작업
- 어떤 자원에 어떤 번호를 붙이느냐에 따라 활용률이 달라진다.
-
이렇듯 예방 방식은 교착 상태가 발생하지 않음을 보장할 수 있지만 여러 부작용이 따른다.
📌교착 상태 회피
- 교착 상태를 한정된 자원의 무분별한 할당으로 인해 발생하는 문제로 간주
- 교착 상태가 발생하지 않을 정도로만 조심 조심 자원 할당하는 방식
- 배분할 수 있는 자원의 양을 고려해 교착 상태가 발생하지 않을 정도의 양만큼만 자원을 배분하는 방법
- 안전 순서열
교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
- 안전 상태
교착 상태 없이 모든 프로세스가 자원 할당 받고 종료될 수 있는 상태
안전 순서열이 있는 상태
- 불안전 상태
교착 상태가 발생할 수도 있는 상태
안전 순서열이 없는 상태
예시
-
총 12개의 자원
-
프로세스 P1, P2, P3가 5개, 2개, 2개의 자원을 할당받아 실행 중
→ 남은 자원은 3개 -
프로세스 P1, P2, P3는 최대 10개, 4개, 9개 자원 요구 가능
이 상태는 안전상태다.
P2→P1→P3라는 안전 순서열이 존재 -
프로세스들이 최대로 자원 요구한 상황
각각 5개, 2개, 7개의 자원 추가로 요구
- P2에게 자원 배분
작업 끝내면 가지고 있던 자원 반환
- P1에 자원 할당
- P1이 작업 마친 후 남은 자원을 P3에 할당
즉 안전 순서열대로 할당하면 모든 프로세스 실행 가능하다.
- 초기 상태가 다르다면?
P2의 작업을 끝내더라도 다른 프로세스의 요구를 들어줄 수 없다.
- 안전 상태에서 안전 상태로 움직이는 경우에만 자원을 할당하는 방식
- 항시 안전 상태를 유지하도록 자원을 할당하는 방식
🎻교착 상태 검출 후 회복
- 교착 상태의 발생을 인정하고 사후에 조치하는 방식
- 프로세스가 자원을 요구하면 일단 할당, 교착 상태 검출되면 회복
선점을 통한 회복
- 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식
프로세스 강제 종료를 통한 회복
-
교착 상태에 놓인 프로세스 모두 강제 종료
→ 작업 내역을 읽게 될 가능성이 있다. -
교착 상태 없어질 때까지 한 프로세스씩 강제 종료
→ 교착 상태 여부 확인 과정에서 오버헤드 야기
- 교착 상태를 무시하는 방법도 있다 : 타조 알고리즘
미션
p. 363의 확인 문제 1번 풀고 인증하기
4번 : 세마포를 이용하면 반드시 바쁜 대기를 해야 합니다.
-> 반드시(X) 대기 상태가 되는 것도 가능하다.
Ch.12(12-1) 임계 구역, 상호 배제 개념을 정리하기
- 임계 구역
동시에 실행하면 문제가 발생하는 자원에 접근하는 코드 영역
책에 나온 것처럼 탈의실로 생각하면 이해가 쉽다.
- 상호 배제
동시에 접근할 수 없는 영역(탈의실)에 하나의 프로세스만 접근 가능하도록 하는 것
