교통체증으로 출퇴근길이 막혀본적이 있는가 이런경우 중간에서 통제해주기 전까진 이도저도 못하는 상황이 발생하는데
컴퓨터에선 이것을 어떻게 표현하고 조치하는지 알아보자
교착상태 (Dead Lock)
둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴때 무한 대기에 빠지는 상황을 의미한다. (OS에선 시스템 자원에 대한 요구가 뒤엉켜 이도저도 못하는 상태)
데드락의 발생조건
1.상호배재 - 한번에 프로세스 1개당 해당자원(1개의 자원)만 사용가능하며 다른 프로세스가 사용하려면 요청한 자원이 해제될때까지 기다려야한다.
2.점유대기 - 자원을 1개이상 보유, 타 프로세스에 할당된 자원을 점유하기 위해 대기해야한다.
3.비선점 - 이미 할당된 자원을 강제로 뺏을수 없다
4.순환대기 - 대기 프로세스의 집합이 순환형태로 자원을 대기하고 있어야한다.
(하단의 사진을 참조..)
데드락의 예방
1.자원의 상호 배제조건 방지 - 한번에 여러 프로세스가 공유자원을 사용할수 있게 되어야한다.
2.점유 대기 조건 방지 - 프로세스 실행에 필요한 모든 자원을 한꺼번에 요구하고 허용할때까지 자원을 보류해서 추후 또다른 자원을 점유하기 위한 대기조건을 성립하지 않도록 한다.
3.비선점 조건 방지 - 다른 프로세스에 할당된 자원이 선점권이 없다고 가정할때 높은 우선순위의 프로세스가 해당자원을 선점할수 있도록한다.
4.순환 대기 조건 방지 - 자원을 순환형태로 하지않고 일정한 한쪽 방향으로만 자원을 요구할수 있도록 한다.
단, 이런 조건을 활용해 데드락을 예방할경우 시스템의 처리량 또는 효율성이 떨어질 우려가 있다.
데드락 회피
데드락의 발생 가능성을 OS가 검사하고 문제없을 경우에만 자원을 할당함으로써 문제 발생을 피하는 방법이다.
시스템의 프로세스들이 모든 자원을 데드락의 발생없이 차례로 할당해주는 상태를 안정상태(safe state),데드락 발생의 여지가 있는상태를 불안정 상태라고 표현하는데 항상 안정상태에 있도록 진행해주는 알고리즘이 은행원 알고리즘 이다.
(특정한 순서로 프로세스에게 자원을 할당, 실행, 종료시 데드락이 발생하지 않는 순서를 안전순서(safe sequence)라고 한다.)
은행원 알고리즘
미리 결정된 모든 자원들의 최대 할당가능한 할당량을 갖고 시뮬레이션해서 safe state에 들수 있는지 여부를 검사
은행원 알고리즘은 MAX, Allocated, Available, Need 4개의 요소를 가지며 각 요소의 의미는 다음과 같다.
| 이름 | 설명 |
| MAX (최대로 쓸수 있는 자원량) | 각 프로세스 자원의 최대 요청(요구)량 |
| Allocated (현재 할당된 자원량) | 현재 프로세스에 할당되있는 자원의 수 |
| Available (현재 끌어올수 있는 자원량) | 각 형태별로 사용 가능한 자원의 수 |
| Need (부족한 수량) | 각 프로세스에 더 추가할수 있는 양을 표시. |
은행원 알고리즘의 예시를 참고해보자
(단, 모든 프로세스의 최대사용량(MAX)를 알아야 하며 가용 가능한 수량이 동일해야 하는 전제조건이 필요하다.)
P0은 3개(A - 0, B - 2, C - 1)를 사용중이며 작업완료를 위해선 6개(A - 2, B - 2, C - 2)을 추가로 필요로 한다.
P1은 3개(A - 1, B - 1, C - 1)를 사용중이며 작업완료를 위해선 10개(A - 4, B - 2, C - 4)를 추가로 필요로 한다.
P2는 2개(A - 0, B - 2, C - 0)를 사용중이며 작업완료를 위해선 8개(A - 2, B - 1, C - 5)를 추가로 필요로 한다.
현재 우리가 가져올수 있는 자원(Available)은 총 9개(A - 3, B - 3, C - 3)이며 C를 기준으로 알고리즘을 진행하겠다.
현재 C의 가용가능한 수량이 3개이기에 가능한 프로세스는 P0뿐이다.
P0이 끝나면 C의 가용 가능한 수량은 총 4개가 되며 (기존 3개+P0의 완료로 반환된 1개) 완료 가능한건 P1뿐이다.
P1이 끝나면 C의 가용 가능한 수량은 총 5개가 되며 (상단의 4개+P1의 완료로 반환된 1개) 나머지 P2에 전달하면 문제없이 동작됨을 확인할수 있다. (Safe sequence)
데드락 탐지 및 회복
탐지
Allocation, Request(요청량), Available로 시스템 내에 데드락이 발생했는지 탐색 즉, 은행원 알고리즘과 유사한 방식으로 탐지 자원 할당 그래프를 통한 탐지(단, 탐지 알고리즘을 실행할경우 이에 대한 오버헤드 발생)
회복
1. 교착상태에 빠진 프로세스 전체를 중지 또는 교착상태가 해소될때까지 프로세스를 중지
2. 교착상태에 빠진 프로세스가 점유하고 있는 자원을 선점(빼앗아)해 교착상태가 풀릴때까지 타 프로세스에 할당