운영체제) 교착 상태 (Deadlock)

▣ 자원 (Resource)

- 접근이 허용되는 객체

- 한 순간에 오직 한 프로세스만 사용할 수 있는 유일한 것

▣ 자원의 유형

- preemptable resource ; 언제든지 회수 가능

- nonpreemptable resources ; I/O와 같이 회수 불가능한 것들

§ 교착상태 (Deadlock)

; 프로세스 집합에 있는 각 프로세스가, 모두 같은 집합에 있는 다른 프로세스만이 일으킬 수 있는 이벤트를 기다리고 있다면 이 집합 안에 있는 프로세스들은 교착상태에 있다.

▣ 교착상태의 조건

- 상호배제(mutual exclusion) 

- 보유와 대기(hold and wait)

- 비선점(nonpreemption)

- 순환대기(circular wait)

==> 4가지 조건 모두 충족해야 함

▣ Holt 모델링 (1972)

- directed graphs 이용하여 제시

- 프로세스 ; 원 / 자원 ; 사각형

▣ 교착상태를 다루기 위한 4가지 전략

- 문제를 단순히 무시 ; 문제 무시 --> 껐다 켜라

- 탐지 및 회복 ; 교착상태 탐지 및 회복 --> 선 할당 후조치; 할당해준 후 교착상태 확인 -> 회복이면 교착상태, 진행이면 교착상태 아님

- 자원할당을 통한 회피 ; 교착상태 회피 --> 자원할당을 해주되 교착상태가 일어나지 않게

- 교착상태의 조건들 중 하나를 무효화시켜 예방 ; 교착상태 예방 --> 4가지 조건중 하나를 무효화

§교착상태 무시

▣ 타조 알고리즘 (Ostrich Algorithm)

- 편리함 > 정확성 추구

- 희박한 교착 상태에 대한 문제를 무시하는 방법

§ 교착상태 탐지 및 회복

▣ 사이클 검사 알고리즘

- L을 빈 리스트로 초기화, 모든 화살표를 지움

- 사이클이 존재한다면, 주기가 있다 --> 알고리즘 종료

- 이동 -> 반복

▣ 교착상태 조사 시점

- 자원요구가 발생할 때마다

- 일정시간마다 조사

- CPU 이용률이 한계치 이하로 저하되었을 때만 조사

▣ 교착상태로부터 회복

- 선점을 통한 회복 ; 자원을 강제로 회복

- 롤백을 통한 회복 ; 그 동안 실행했던것들이 문제가 된다

- 프로세스 강제종료를 통한 회복 ; 교착상태 사이클이 깨어질 때까지 프로세스 하나씩 제거

§ 교착상태 회피

▣ 교착상태 회피

- 대부분 시스템에서 자원은 한 번에 하나씩 요구
- 시스템은 자원이 안정적 / 불안정적 상태인지를 검사하여 결정

==> 자원 궤도 ( Resource Trajcetories) --> 순서에 따라 교착상태에 빠질수도 아닐 수도 있음

; 안전한 상태에서의 자원 할당 -> 불안정 상태면 안준다

; 두 프로세스의 자원 궤도

▣ 안전 / 불안전

- 안전 상태 ; 모든 프로세스들이 종료 시점까지 실행될 수 있는 스케줄링 순서가 존재

- 불안전 상태 != 교착상태 
    ==> "불안전 상태는 교착상태에 빠질 수 있다" 는 의미이지, 교착상태인 것은 아니다.

- 시스템이 모든 작업의 완료를 보장할 수 있는가, 없는가의 차이

▣ 은행원 알고리즘

- 다익스트라가 만든 교착상태 회피 알고리즘

- 행렬을 이용

§ 교착상태 예방

▣ 상호배제 조건의 부정

- 사용하지 않을 때는 자원을 release 한다.

- 가능한 적은 수의 프로세스가 자원을 보유하도록

▣ 보유 및 대기 조건의 부정

- 모든 자원이 할당 가능하면 실행 완료 / 그렇지 않으면 wait

▣ 비선점 조건의 부정

- 일반적으로 불가능

▣ 순환 대기 조건의 부정

- 하나의 프로세스가 한 순간에 한 자원만 할당받도록

- 모든 자원 요청에 대해 일련의 전역 순서 번호를 부여 -> 교착상태에 빠지지 않는 순서

▣ 다른 문제들

- 2단계 잠금 (Two-Phase Locking)

- 통신 교착상태 (Communication Deadlocks)

- 라이브락(Livelock) ~ busy waiting

- 기아상태(starvation)