📖데드락(Deadlock)

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

• 시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생

프로세스1과 2가 자원1, 2를 모두 얻어야 한다고 가정

1. 프로세스1이 자원1을 얻음 / 프로세스2가 자원2를 얻음
2. 프로세스1은 자원2를 기다림 / 프로세스2는 자원1을 기다림
3. 현재 서로 원하는 자원이 상대방에 할당되어 있어서 두 프로세스는 무한정 wait 상태에 빠짐

프로세스가 자원 사용하는 절차

1. 자원 요청 (Request) : 프로세스가 자원을 요청 (다른 프로세스가 자원을 사용하고 있어 받을 수 없다면 대기)
2. 자원 받음 (Allocate)
3. 자원 사용 (Use) : 프로세스가 받은 자원을 사용
4. 자원 해제 (Release) : 프로세스가 자원을 해제
   🔖 Deadlock은 모든 프로세스가 Request 상태가 되어 있는 상황

📖발생 조건

• 4가지 조건이 동시에 성립할 때 발생
• 4가지 조건이 동시에 성립하지 않는다면 데드락(Deadlock)을 해결 가능

1. 상호 배제(Mutual Exclusion)

한 번에 프로세스 하나만 해당 자원을 사용할 수 있음

2. 점유 대기(Hold and wait)

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

3.비선점(No Preemption)

다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없음

4. 순환 대기(Circular wait)

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

📖처리 방법

📎예방(Prevention)

교착 상태 발생 조건 중 하나를 제거해 예방하는 방법

Note

• 상호배제 부정 : 여러 프로세스가 공유 자원 사용
• 점유대기 부정 : 프로세스 실행전 모든 자원을 할당
• 비선점 부정 : 자원 점유 중인 프로세스가 다른 자원을 요구할 때 가진 자원 반납
• 순환대기 부정 : 자원에 고유번호 할당 후 순서대로 자원 요구

• 자원 낭비가 심함
• 시스템의 처리량이나 효율성을 떨어트릴 수 있음

📎회피(Avoidance)

Deadlock 발생을 피해나가는 방법

Safe Sequence와 Safe State

Safe State : 시스템의 프로세스들이 요청하는 모든 자원을 Deadlock을 발생시키지 않으면서도 순서대로 모두에게 할당할 수 있는 상태

• Safe Sequence가 하나라도 존재하면 Safe State

Unsafe State : 데드락 발생 가능성이 있는 상황 Safe Sequence : 특정한 순서로 프로세스들에게 자원을 할당할 때 Deadlock이 발생하지 않는 순서

• 자원을 할당한 후에도 시스템이 항상 Safe State에 있을 수 있도록 하여 Deadlock을 회피

1. Banker’s Algorithm (은행원 알고리즘)

어떤 자원의 할당을 허용하는지에 관한 여부를 결정하기 전에, 미리 결정된 모든 자원들의 최대 가능한 할당량을 가지고 시뮬레이션 해서 Safe State에 들 수 있는지 여부를 검사하는 알고리즘

• 프로세스가 자원을 요구할 때, 프로세스에 자원을 할당한 후에도 시스템이 Safe State로 남아있게 되는지 사전에 검사하여 회피
• Safe State라면 자원 할당, Unsafe State라면 다른 프로세스들이 자원 해지까지 대기

2. Resource-Allocation Graph Algorithm (자원 할당 그래프 알고리즘)

자원과 프로세스에 대해 요청 간선과 할당 간선을 적용하여 Deadlock를 회피하는 알고리즘

• 프로세스가 자원을 요구 시 요청 간선을 할당 간선으로 변경 했을 시 사이클이 생성 되는지 확인
• 사이클이 생성된다 하여 무조건 교착상태인 것은 아니다
• 사이클이 생성된다고 해서 무조건 Deadlock은 아니지만, 사이클을 생성하지 않으면 자원을 할당

📎탐지(Detection)

Deadlock이 발생했는지 여부를 탐지하는 방법

• Allocation, Request, Available 등으로 탐지 (현재 시스템의 자원 할당 상태를 가지고 파악)
• 자원 할당 그래프를 통해 탐지

📎회복(Recovery)

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

1. 프로세스 종료 방법

• 교착 상태의 프로세스를 모두 중지
• 교착 상태가 제거될 때까지 하나씩 프로세스 중지

2. 자원 선점 방법

• 교착 상태의 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스에게 할당 (해당 프로세스 일시정지 시킴)
• 우선 순위가 낮은 프로세스나 수행 횟수 적은 프로세스 위주로 프로세스 자원 선점

📎무시(Ignorance)

Deadlock을 시스템이 책임지지 않는 방법

• 대부분의 현대 운영체제가 채택

현대 운영체제에서는 Deadlock을 처리하지 않는 이유

1. 빈번히 발생하는 이벤트가 아니기 때문에 사전에 방지하기 위해 많은 오버헤드를 들이는 것이 더 비효율적이라고 판단
2. 현대 시스템의 복잡성으로 인해 Deadlock을 완전히 방지하기는 불가능
3. 만약 발생할 시, 시스템이 비정상적으로 작동한 것을 사람이 느낀 다음 직접 프로세스를 죽이는 방법으로 대처