💻 [OS 오퍼레이팅시스템] #13 | Deadlocks | 데드락, 뱅커스 알고리즘, 교착상태

 

 

---

💻 데드락 (교착상태)

 - 데드락 
- 시스템 자원을 두고 경쟁하거나 서로 통신하는 프로세스의 집합의 영구적 차단

- 집합의 각 프로세스가 다른 block된 프로세스에 의해서만 발생될 수 있는 이벤트를 대기하면서 block되면 프로세스 집합은 데드락

- 더이상 이벤트들이 발생할 수 없는 상태여서 두 개 이상의 프로세스가 더이상 진행될 수 없는 상황

두 개 이상의 프로세스에 의한 자원 요구의 충돌을 수반한다.

데드락 cycle

 

 - Resources (자원) 
[ 비선점 자원(non preemtable) ]

- 빼앗을 수 없는 자원

- 보통 데드락이 비선점자원을 수반한다.

- 비선점 자원 종류 2가지 : reusable and consumable

 

[ 1) 재사용 자원(reusable) ]

- 사용해서 사라지지 않고, 한번에 한 프로세스만 사용될 수 있다.

- 자원 이용 과정 : 1)요청 -> 2)Lock(할당) -> 3)사용-> 4)Unlock(release)

- e.g. 프로세서, 메모리, 디바이스, 프린터, 파일, 세마포어 등

 

[ 2) 소비되는 자원(consumable) ]

- 생성되고 사라진다. 

- e.g. interrupts, signals, messages, I/O 버퍼의 information 등

 

 - Resource Allocation Graphs  

유향그래프.

Vertices : P는 프로세스(동그라미로 표시), R은 리소스(사각형으로 표시)

Edges : 프로세스에서 리소스로 향하는 edge는 요청한다는 의미, 리소스에서 자원으로 향하는 edge는 점유한다는 의미

 

cycle 없으면 데드락 X

cycle 있는데 one instance면 데드락 0, multi instances면 데드락 있을 수도 없을 수도(보통 없다)

데드락 사이클

---

💻 식사하는 철학자 문제 (동기화 문제)

 - 식사하는 철학자 

다익스트라에 의해 소개된 개념. 보통 5명의 철학자(프로세스)와 5개의 음식(자원)각 철학자는 먹기위해 2개의 포크가 필요하다. 동시에 포크 사용 불가하며 자신의 왼쪽 포크와 오른쪽 포크를 사용한다.목표 : 데드락(굶어죽음)을 예방하고 포크는 상호배제 해준다.getforks() -> eat() -> putforks() -> think() 반복하는게 기본 틀이다.

<구현 코드>

리눅스에서 세마포어로 구현

자바에서 구현 (위와 동일한 실행 코드)

 

---

💻 데드락 발생 조건 

 - 상호 배제 Mutual Exclusion 

(필요조건) 한번에 한 프로세스만 자원 사용 보장

 

 - 비선점 No preemption 

(필요조건) 프로세스가 작업 완료한 뒤, 리소스는 프로세스에 의해서만 자발적으로 풀어질 수 있다.

 

 - 점유한 상태에서 대기 Hold and Wait  

(필요조건) 하나 이상의 리소스를 점유한 프로세스가 다른 프로세스에 의해 점유된 다른 리소스를 획득하기 위해 대기 중인 상태

 

 - 순환 대기 Circular Wait  

(필요충분조건) 프로세스0이 프로세스1에 의해 점유된 자원을 기다리고, 프로세스1이 프로세스2에 의해 점유된 자원을 기다리고 ... 프로세스n이 프로세스0에 의해 점유된 자원을 기다리는 서로가 다른 서로의 자원을 기다리는 cycle

---

💻 식사하는 철학자 해결법

 - 1) 4명만 식사할 수 있게 하자 

room이라는 세마포어 변수 추가(공유자원이므로 상호배제 필요)

단졈 : concurrency 손해

C 구현 코드

자바 구현 코드

 

 - 2) 점유대기 제약

자바로 구현

 

 - 3) 순환대기 제약 

자바로 구현

---

💻 데드락 예방 (조건 방지)

 - 데드락 예방 

데드락 발생 조건 4가지 중 하나에 제약을 걸자.상호 배제와 비선점은 상대적으로 제약 걸기 어렵다.

 

- 점유 대기 제약 : 프로세스가 모든 요청된 자원을 한번에 요청하고, 모든 요청이 동시에 승인될 수 있을 때까지 프로세스를 블로킹한다.점유 대기 제약 단점 : 비효율적, 프로세스 속도 저하 및 불필요하게 리소스 접근 거부. 점유 상태에서 대기 불가

 

- 순환 대기 제약 : 리소스에 번호매김으로써 순서화(linear ordering) 각  프로세스는 오름차순으로 자원 요청. 순환 대기 제약 단점 : 편리하지 않고 복잡하고 자원 요청 오름차순으로밖에 못하는 제약

---

💻 데드락 회피 (승인/거절)

 - 데드락 회피 

단점 : low device utilization, less concurrency, difficulty of resource use  

 

 - Resource-Allocation-Graph 알고리즘 

 

 

 - (Banker's) 뱅커스 알고리즘 

 

---

💻 데드락 핸들링 

 - 핸들링 종류 

1) 데드락 예방 : 데드락 발생 조건 4가지 안가지도록 제약, concurrency, utilization이 희생 될 가능성 존재

2) 데드락 회피 : 데드락 발생 가능성 있으면 자원 사용을 회피 (추가적인 미래 정보가 필요)

3) 데드락 탐지와 회복 : 데드락 가정하고 주기적으로 데드락을 체크, 프로세스 종료 또는 자원 회수로 회복시킨다.

4) 그냥 무시 : 위의 3가지 방법 cost 커서 아무것도 안하는게 성능 좋을 수도. 데드락은 어차피 잘 안일어나는 일이니 그냥 무시하는  방법