[운영체제] - Deadlock (교착 상태)

glow_soon·2022년 5월 31일

졸업을 앞두고 있어서 다시 CS 공부중...!! 공부한 내용을 간단히 정리 할 것 이다.
순서가 좀 뒤죽박죽이더라도 양해를 구합니다

Deadlock(교착상태)

시스템 자원에 대한 요구가 뒤엉킨 상태
(둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴때 무한 대기에 빠지는 상황)

Deadlock의 발생 조건

아래 4가지 조건이 모두 만족되는 경우 데드락이 발생할 가능성이 있다. 하나라도 만족하지 않으면 절대 발생하지 않는다.

상호 배제 - 한번에 프로세스 하나만 해당 자원을 사용 가능하다.

점유 대기 - 자원을 최소한 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재하여야 한다.

비선점 - 이미 할당된 자원을 강제로 빼앗을수 없다.

순환 대기 - 대기 프로세스의 집합이 순환형태로 자원을 대기하고 있어야 한다.

해결방법

예방(prevention)하기
적당히 회피(avoidance) 하기
허용하지만 탐지(detection)하여 회복하기

예방(prevention)하기

발생 조건중 하나라도 발생하지 않게한다.

자원의 상호 배제 조건 방지 : 한번에 여러 프로세스가 공유자원 사용 할 수 있게 한다.
점유 대기 방지 : 프로세스 실행에 필요한 모든 자원을 한꺼번에 요구하고, 허용 할 때까지 작업을 보류, 나중에 또 다른 자원을 점유 하기 위한 대기조건을 성립하지 않게한다.
비선점 조건 방지 : 높은 우선순위의 포로세스가 해당자원을 선점 할 수 있게 한다.
순환 대기 조건 방지 : 일정한 방향으로만 자원을 요구한다.

적당히 회피(avoidance) 하기

모든 자원을 Deadlock이 발생하지 않으면서 할당 가능한 상태를 안전 상태(safe state)라 한다. 이처럼 특정한 순서로 프로세스들에게 자원을 할당, 실행 및 종료 등의 작업을 할 때 Deadlock이 발생하지 않는 순서를 찾을 수 있다면, 그것을 안전 순서(safe sequence)라고 한다.

이처럼 회피는 자원을 할당한 후에도 시스템이 항상 safe state에 있도록 하는것이 목적이다. 가장 유명한 알고리즘으로는 banker's algorithm이 있다.

탐지 및 회복

먼저 시스템이 Deadlock 예방이나 회피법을 사용하지 않았을 때, Deadlock이 발생할 수 있으니 여기에서 회복하기 위해 Deadlock을 탐지하고, 회복하는 알고리즘을 사용한다.

탐지 기법

시스템에 데드락이 발생했는지 여부를 탐지한다.

회복 기법

탐지 기법을 통해 Deadlock을 발견했다면, 순환 대기에서 벗어나 Deadlock으로부터 회복하기 위한 방법을 사용한다.

단순히 프로세스를 1개 이상 중단시키기

교착 상태에 빠진 모든 프로세스를 중단시키는 방법 : 계속 연산중이던 프로세스들도 모두 일시에 중단되어 부분 결과가 폐기될 수 있는 부작용이 발생할 수 있다
프로세스를 하나씩 중단 시킬 때마다 탐지 알고리즘으로 데드락을 탐지하면서 회복시키는 방법 : 매번 탐지 알고리즘을 호출 및 수행해야 하므로 부담이 되는 작업일 수 있다.