5-1. 교착 상태의 개념과 발생 원인
교착 상태의 개념
- deadlock: 결코 일어나지 않을 event를 기다리는 상태
- 두 프로세스가 사용하는 자원을 서로 기다리고 있는 상황
예시
- spooling 시스템
- 디스크에 할당된 spool공간의 출력을 완료하지 않은 상태에서 다른 작업이 spool공간을 차지
- spooling file의 일정 포화 임계치(saturation threshold)를 설정하여 예방
- disk 공유
- network
- I/O 버퍼 공간이 부족한 네트워크 시스템에 메세지 흐름을 제어하는 protocol이 부재할 경우
발생 조건
- 상호배제
- 자원을 최소 하나 이상 비공유
- 점유와 대기
- 자원을 최소 하나 이상 보유하고 다른 프로세스의 자원을 얻기 위해 대기하는 프로세스가 존재
- 비선점
- 자원 선점이 불가해야 함
- 반드시 프로세스가 끝나야 자원이 해제됨
- 순환(환형) 대기
- 1~3을 만족할 때 발생
5-2. 교착 상태의 해결 방법
Prevention(예방)
- 상호배제 문제를 고려하여 예방해야 함
- 자원 요청을 제한
- 장치의 효율성과 시스템 처리량을 떨어뜨림
1. 자원의 상호배제 조건 방지
- 자원의 비공유가 전제되어야 함
2. 점유와 대기 조건 방지 (hold and wait)
- 자원을 할당할 때 시스템 호출된 프로세스 하나를 실행하는 데 필요한 모든 자원을 우선 할당
- 프로세스가 전혀 자원을 가지고 있지 않을 때에만 자원 요청을 허용
- 자원 효율성이 낮고 기아상태 발생 가능성이 존재
3. 비선점 조건 방지 (non-preemption)
- 전제 조건: 이미 할당된 자원에 선점권이 없어야 함
- 무효화하는 방법
- 다른 자원 요청 시, 대기가 필요하면 프로세스는 가지고 있는 자원을 모두 해제함
- 복구가 쉽거나, 빈번하지 않게 발생할 경우 사용
- 요청한 자원 사용 가능 여부 검사
- 프로세스가 자원 요청을 했을 때, 사용할 수 없다면 대기 프로세스가 자원을 점유하고 있는지 검사
- 대기 프로세스가 자원을 점유하고 있다면, 요청한 자원을 해제해, 요청 프로세스에 할당
- 요청한 자원을 사용할 수 없거나 실행 중인 프로세스가 점유 중이면 요청 프로세스는 대기
- 우선순위
- 두 프로세스에 우선순위 부여
- 우선순위에 따라서 자원을 선점하여 해결
- 복원하기 쉬운 장치에서 사용
4. 순환(환형) 대기 조건 방지
- 모든 자원에 순서를 부여하고, 프로세스가 오름차순으로 자원 요청
- circular wait(순환 대기)의 가능성 제거
- 접근을 불필요하게 거부해서 비효율적
Avoidance(회피)
- 교착 상태가 발생할 가능성을 허용하고 회피하는 것
1. 프로세스의 시작 중단
- 자원 요청량을 수용할 수 있을 때만 새로운 프로세스 수용
- 자원 할당 거부(Banker’s algorithm): 프로세스가 용청한 자원을 할당했을 때, 교착 상태가 발생할 수 있으면 할당X
- 자원 요청 타이밍에 대한 정보가 필요
- 할당할 수 있는지, 프로세스를 대기시킬지
- 각 프로세스에 대한 자원의 요청/해제를 미리 알고 있어야 함
- ex 각 프로세스가 필요한 자원의 최대치를 선언
- 순환 대기 조건이 발생하지 않도록 자원 할당 상태 점검
- 사용 가능한 자원 수, 할당된 자원 수, 프로세스들의 최대 요청 수
- 안정 상태 = 각 프로세스에 최대치까지 자원 할당 가능 + 교착 상태 예방 가능
- 교착 상태는 불안정 상태 / 불안정 상태는 교착 상태가 되기 쉬운 상태
2. 자원 할당 거부 (은행가 알고리즘)
- 다익스트라의 은행가 알고리즘을 사용
- 할당 여부 결정 전, 모든 자원의 최대 가능 할당량을 시뮬레이션하여 안전 여부 검사
- 안정 상태 여부 검사: 대기 중인 모든 활동의 교착 상태 가능성 조사
- 자원 요청을 승낙하는 것이 불안정하다고 판단하면 요청 연기/거부 → 교착상태 예방
- 필요 정보
- 자원 할당 순서 조정을 위해, 각 프로세스가 요청하는 자원 종류의 최대 수
- 각 프로세스가 요청할 수 있는 자원의 양, 보유하고 있는 자원의 양, 시스템이 사용할 수 있는 자원의 양
- 항상 불안정 상태를 방지해서 자원 이용도가 낮음
Detection(탐지)
- 발생한 교착 상태에서 회복하기 위한 알고리즘에는 탐지 알고리즘과, 회복 알고리즘이 필요
- 탐지 알고리즘을 매번 부르면 효율성이 떨어지기 때문에, 호출 빈도를 줄여야함
- 회복은 순환 대기에서 벗어나는 것을 의미
- 프로세스 하나 이상 중단
- 교착 상태의 프로세스들에서 자원을 선점
- 프로세스 중단
- 교착 상태의 프로세스를 모두 중단하면 확실하게 해결되지만 비용이 비쌈
- 하나씩 중단하면 중단할 때 마다 교착 상태 감지 알고리즘을 호출하는 부담이 큼
- 최소 비용(우선 순위, 종료까지 남은 시간, 남은 자원 수, 종료에 필요한 프로세스 수…)으로 프로세스들을 중단해야함
- 자원 선점
- 교착 상태를 해결할 때까지 선점한 자원을 다른 프로세스에 할당해야 함
- 적절한 선점 순서를 결정해야 함
- 프로세스를 안정 상태로 최소한만 복귀시키고 다시 시작해야함
- 동일한 프로세스가 항상 선점하지 않도록 해야함 (ex 비용요소에 복귀 횟수를 포함)
5-3. 기아 상태 (starvation)
- 교착 상태를 예방하려고 자원을 할당할 때 발생하는 기다림
- 식사하는 철학자의 해결 방법
- 4명만 앉힘
- 양쪽 포크를 집을 수 있을 때만 집도록 허용 (임계 영역 안에서)
- 비대칭 해결법 (홀수는 왼쪽, 짝수는 오른쪽 먼저 집게 함)
- 기아 상태의 해결은 기다린 시간을 추적해야 함
- 기아 상태를 발견하면 바로 작업이 대기할 수 있도록 해야함
