[운영체제] Deadlock

Deadlock (교착 상태)

Deadlock (교착 상태) : 두 개 이상의 프로세스 혹은 스레드가 서로가 가진 리소스를 기다리는 상태

자원 할당 그래프 (Resource-Allocation Graph)

<이미지 출처>https://kukuta.tistory.com/281

• 어떤 프로세스가 어떤 자원을 사용하고 있고, 또 어떤 프로세스가 어떤 자원을 기다리고 있는지 표현하는 간단한 그래프이다.
• 자원 할당 그래프를 보고 데드락의 발생 여부를 판별할 수 있다.

자원 할당 그래프 규칙

- 프로세스는 원으로, 자원의 종류는 사각형으로 표현
- 사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현
- 프로세스가 어떤 자원을 할당받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시
- 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시

Deadlock을 만드는 4가지 조건

1. Mutual exclusion(상호 배제) : 리소스를 공유해서 사용할 수 없다.

2. Hold and wait(점유와 대기) : 프로세스가 이미 하나 이상의 리소스를 취득한(hold) 상태에서 다른 프로세스가 사용하고 있는 리소스를 추가로 기다린다.(wait)

3. No preemption(비선점) : 리소스 반환(release) 은 오직 그 리소스를 취득한 프로세스만 할 수 있다.

4. Circular wait(원형 대기) : 프로세스들이 순환형태로 서로의 리소스를 기다린다.

Deadlock 해결 방법

데드락 방지 (Deadlock prevention)

• 네 가지 조건 중 하나가 충족되지 않게 시스템을 디자인

- Mutual exclusion :리소스를 공유 가능하게 함

- Hold and wait : 사용할 리소스들을 모두 획득한 뒤에 시작 or 리소스를 전혀 가지지 않은 상태에서만 리소스 요청

- No preemption : 추가적인 리소스를 기다려야 한다면 이미 획득한 리소스를 다른 프로세스가 선점 가능하도록 한다

- Circular wai : 모든 리소스에 순서 체계를 부여해서 오름차순으로 리소스를 요청

데드락 회피 (Deadlock avoidance)

• 실행 환경에서 추가적인 정보를 활용해서 데드락이 발생할 것 같은 상황을 회피하는 것

Safe state : safe sequence(교착상태를 발생시키지 않고 자원을 할당하는 순서)가 존재하며 모든 프로세스가 정상적으로 종료될 수 있는 상태를 의미

Unsafe state : 교착상태가 발생할 가능성이 있는 상태

데드락을 회피하기 위한 알고리즘

①

은행원 알고리즘(Banker's Algorithm) 
: 리소스 요청을 허락해줬을 때 데드락이 발생할 가능성이 있으면 리소스를 할당해도 
  안전할 때 까지 계속 요청을 거절하는 알고리즘
  

- 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래

- 프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 
사전에 검사하여 교착 상태 회피

- 안정 상태면 자원 할당, 아니면 다른 프로세스들이 자원 해지까지 대기

②

자원 할당 그래프 알고리즘(Resource-Allocation Graph Algorithm)
: 자원 할당 그래프에 예약 간선을 추가하여 예약 간선으로 설정한 자원에 대해서만 
  자원 할당을 요청할 수 있고 사이클이 형성되지 않을 때만 자원을 할당받는 알고리즘

데드락 감지와 복구

• 데드락을 허용하고 데드락이 발생하면 복구하는 전략

#감지
자원 할당 그래프를 통해 교착 상태를 탐지함
자원 요청 시, 탐지 알고리즘을 실행시켜 그에 대한 오버헤드 발생함

#복구
사용자 처리
교착상태에 있는 프로세스 중 하나의 프로세스를 사용자가 강제 종료

시스템 처리
①프로세스 중지
데드락에 속해있는 모든 프로세스를 중지
데드락이 해결될 때까지 한 프로세스씩 중지

②자원 선점
프로세스들로부터 자원을 빼앗아 데드락이 해결될 때까지 다른 프로세스들에게 자원을 할당

데드락 무시

• 드물게 발생하는 잠재적 문제를 무시로 대처하는 방식 ➡ 타조 알고리즘 (ostrich algorithm)

참고

• 혼자 공부하는 컴퓨터 구조 + 운영체제 (강민철 지음)
• https://cocoon1787.tistory.com/858
• https://gyoogle.dev/blog/computer-science/operating-system/DeadLock.html