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

식사하는 철학자 문제

 

 

1. 일정 시간 생각을 한다.

2. 왼쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.

3. 오른쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.

4. 양쪽의 포크를 잡으면 일정 시간만큼 식사를 한다.

5. 오른쪽 포크를 내려놓는다.

6. 왼쪽 포크를 내려놓는다.

7. 다시 1번으로 돌아간다.

 

만약 모든 철학자들이 동시에 자신의 왼쪽 포크를 잡는다면, 모든 철학자들이 자기 오른쪽의 포크가 사용 가능해질 때까지 기다려야 한다.

그런데 모든 철학자들이 그러고 있다.

이 상태에서는 모든 철학자가 영원히 3번 상태에 머물러있어 아무것도 진행할 수가 없게 되는데,

이것이 교착(Deadlock)상태이다.

 

철학자: 프로세스 / 스레드

포크: 자원 (임계 구역)

생각하는 행위: 자원을 기다리는 것

 

 

 교착 상태란?

-일어나지 않을 사건을 기다리며 진행이 멈춰버리는 현상

= 상대방의 자원을 기다리다가 실행을 못하는 상황

 

 

둘 이상의 프로세스 혹은 스레드들이 서로 상대방이 사용중인 자원을 쓰기 위해 대기하고 있는 상황

 

 

 

 

자원 할당 그래프

 

P: 프로세스

R: 자원의 종류

. : 자원의 개수

 

자원 → 프로세스 : 프로세스가 자원을 할당받아 사용 중

프로세스 → 자원: 프로세스가 자원을 대기 중

 

 

사이클이 존재하면 교착 상태가 발생한다. 

 

 

 

교착 상태 발생 조건

 

네가지 조건이 모두 만족될 때 교착 상태 발생 가능성이 생김

 

1. 상호 배제

한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없을 때

 

2. 점유와 대기

자원을 할당 받은 채 다른 자원을 할당받기를 기다림

 

3. 비선점

프로세스가 다른 프로세스의 자원을 강제로 뺏지 못함

 

4. 순환 대기 

프로세스들이 원(사이클)의 형태로 자원을 대기

 

 

교착 상태 해결 방법

 

1. 예방

 

교착상태의 네가지 조건 중 하나라도 만족하지 못하게 만든다. 

 

1)상호 배제 제거

모든 자원을 공유 가능하게 만든다.

 

2)점유와 대기 제거

프로세스의 자원을 모두 할당 하거나 아예 할당하지 않게 배분한다.

자원의 활용률이 낮아지고 많은 자원을 필요로 하는 프로세스의 기아 현상이 발생 가능하다.

 

3)비선점 제거

이용 중인 프로세스로부터 자원을 뺏을 수 있게 한다.

범용성이 떨어진다.

 

4)순환 대기 조건 제거 

모든 자원에 번호를 매겨 오름차순으로 자원을 할당한다.

특정 자원의 활용률이 떨어질 수 있다. 

 

 

 

2. 회피

 

교착 상태가 발생하지 않을 정도(안전 상태)의 양만큼만 자원을 배분

교착 상태 없이 안전하게 프로세스들에 자원을 할당하는 순서를 안전 순서열이라 하고

안전 순서열대로 프로세스에 자원을 배분한 상태를 안전 상태라 한다.

 

 

 

3. 검출 후 회복(탐지 및 복구)

1. 선점을 통한 회복
2. 교착 상태가 해결될 때까지 다른 프로세스로부터 자원을 뺏어 할당
3. 강제 종료를 통한 회복
4. 교착 상태의 프로세스를 모두 강제 종료 하거나 한 프로세스씩 강제 종료

 

 

---

 

 

책 혼자석 공부하는 컴퓨터 구조 + 운영체제

https://namu.wiki/w/%EC%8B%9D%EC%82%AC%ED%95%98%EB%8A%94%20%EC%B2%A0%ED%95%99%EC%9E%90%20%EB%AC%B8%EC%A0%9C

https://wannabe-gosu.tistory.com/26