운영체제 - 데드락

고태희·2022년 2월 23일

운영체제

CS

목록 보기

10/20

개념

정의

두개 이상의 작업이 서로 상대방의 작업이 끝나기만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태.
"교착상태"라고도 한다. 시스템적으로 한정된 자원을 여러 곳에서 사용하고자 할 때 발생

예제

이처럼 P1, P2가 모두 R1, R2를 사용하려고 하는데 서로의 것을 기다리는 상태.

즉, 멀티 프로세스 환경에서 한 프로세스가 자원을 요청했을 때, 동시에 그 자원을 사용할 수 없을 때 발생할 수 있다. 이때 프로세스는 대기상태로 들어감. 이렇게 대기상태로 간 프로세스들이 실핼될 수 없을 때 데드락 발생.

조건

데드락은 다음 4가지 조건을 모두 성립해야 발생한다. 어느 하나라도 만족 못할 시 발생하지 않는다.

상호배제 (Mutual Exclusion)
- 자원을 한번에 하나의 프로세스만이 사용 가능
점유대기 (Hold and Wait)
- 최소한 하나의 자원을 점유하면서 다른 프로세스가 가진 자원을 추가로 점유하기 위해 대기하는 프로세스 존재
비선점 (No Preemption)
- 다른 프로세스에 할당된 자원을 사용이 끝날때까지 강제로 뺏을 수 없음
순환대기 (Circular Wait)
- 순환형태로 자원을 대기하는 경우 ex) A -> B -> C -> A ...
- 순환대기는 위 3가지가 만족되어야 만족된다.

데드락 해결법

데드락 발생을 예방
데드락 발생가능성을 인정하면서도 적정하게 회피
데드락 방생을 허용하지만 탐지 하여 적절히 회복

예방

위 데드락 발생조건 4가지 중 하나라도 발생하지 않게 하면 된다.

상호배제 부정
- 여러 프로세스가 공유자원 사용, (이는 동기화의 문제발생 가능성이 있다.)
점유대기 부정
- 프로세스 실행 전 모든 자ㅏ원을 할당받아 대기조건 생성 x
비선점 부정
- 자원을 점유 중인 프로세스가 다른 자원을 요구할 때 점유하고 있는 자원을 반납하고, 요구한 자원 사용하기 위해 대기
순환대기 부정
- 자원에 고유번호 할당하고, 번호 순서대로 자원 요구

데드락을 예방하는 방법들은 시스템의 처리량이나 효율성을 떨어뜨릴 수 있다는 단점이 발생
회피법은 예방법보다는 덜 제한적인 방법으로 이러한 단점을 일부 해결

회피

Safe State
시스템의 프로세스들이 요청하는 모든 자원을, 데드락을 발생시키지 않으면서도 차례로 모두에게 할당해 줄 수 있는 상태.
Safe Sequence
특정한 순서로 프로세스들에게 자원을 할당, 실행 및 종료 등의 작업을 할 때 데드락이 발생하지 않는 순서를 찾을 수 있다면 그것이 안전순서이다.

회피알고리즘의 기본은 자원을 할당 후에도 시스템이 항상 Safe State에 있을 수 있게 하는 것

은행원 알고리즘

대표적인 회피 알고리즘

어떤 자원의 할당여부를 결정하기 전에, 미리 결정된 모든 자원들의 최대 가능한 할당량을 가지고 simulation해서 Safe State에 들 수 있는지 검사한다.
-> 만약 Safe State이면 자원을 할당, 아니면 다른 프로세스가 자원 반환할 때까지 대기