[운영체제] 교착 상태(데드락, Deadlock) - 5/5

교착 상태 (데드락, Deadlock)

둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때 무한 대기에 빠지는 상황을 일컫습니다. 교착상태를 해결하는 것도 운영체제의 중요한 역할입니다.

교착 상태가 발생했을 때 해결하기 위해선 두 단계의 작업이 필요합니다. 

1. 교착 상태가 발생했을 때의 상황을 정확히 표현할 줄 알아야 합니다.

2. 교착 상태가 일어나는 근본적인 이유를 확인합니다.

 

교착 상태 상황 확인

자원 할당 그래프 

교착 상태가 왜 발생하는지 대략적으로 파악할 수 있습니다. 

• 어떤 프로세스가 어떤 자원을 할당받아 사용 중인지 확인 가능
• 어떤 프로세스가 어떤 자원을 기다리고 있는지 확인 가능

그리는 방법은 매우 쉽습니다.

첫째, 프로세스는 원으로 자원의 종류는 사각형으로 표현합니다.

둘째, 사용할 수 있는 자원의 개수는 자원 사각형 내 점으로 표현합니다. 

셋째, 프로세스가 어떤 자원을 할당 받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시합니다.

넷째, 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시합니다.

 

그럼 어느경우에 교착 상태가 발생할까요?

✅ 자원 할당 그래프가 원의 형태를 띠고 있을때 교착 상태가 발생합니다. 

교착 상태 발생 원인

교착 상태가 발생할 4가지 조건

• 상호 배제
  • 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태입니다.
• 점유와 대기
  • 자원을 할당받은 상태에서 다른 자원을 할당 받기를 기다리는 상태입니다.
• 비선점
  • 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 상태입니다.
• 원형 대기
  • 프로세스들이 원의 형태로 자원을 대기하는 상태입니다.

 

➡ 위 네 가지 조건을 모두 만족할 시, 교착 상태가 발생할 수 있습니다.

 

⭐교착 상태 해결 방법

• 예방
• 회피
• 검출 후 회복

교착 상태 예방

애초에 교착 상태가 발생하지 않도록 하는 방식입니다. 

교착 상태 발생 조건(상호 배제, 점유와 대기, 비선점, 원형 대기) 중 하나를 만족시키지 않는 방법으로 예방합니다. 

• 상호 배제를 없애보면,
  • 모든 자원을 프로세스들이 공유..... 하게 만들 순 없습니다. 현실적으로 불가능합니다.
• 점유와 대기를 없애보면,
  • 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분합니다.
  • 단점: 자원의 활용률이 낮아짐 
• 비선점 조건을 없애보면,
  • 선점이 가능한 자원에 한해 효과적이나 모든 자원이 선점 가능한 것은 아닙니다.
    • 대표적으로 선점이 가능한 자원 : CPU
• 원형 대기 조건을 없애보면,
  • 자원에 번호를 붙이고 오름차순으로 할당하면 원형대기는 발생하지 않습니다.
  • 1번 포크 → 2번 포크 → 3번 포크..... → 5번 포크에서 다시 1번 포크는 잡지 못합니다.
  • 위 3가지 방식에 비해 현실적인 방식이지만  어떤 자원에 어떤 번호를 붙이느냐에 따라 자원 활용률이 달라지게 됩니다.

 

이렇게 교착 상태 발생 조건(상호 배제, 점유와 대기, 비선점, 원형 대기) 중 하나를 만족시키지 않는 방법을 통해 교착 상태가 발생하지 않음을 보장할 순 있지만 각각의 부작용이 있음을 확인할 수 있었습니다. 

 

교착 상태 회피

여기서는 한정된 자원을 무분별하게 할당해서 교착 상태가 발생했다고 간주합니다. 즉, 교착 상태 회피방식은 배분할 수 있는 자원의 양을 고려해서 교착 상태가 발생하지 않을 만큼만 자원을 배분하는 방식입니다.

 

먼저 이해하고 넘어갈 용어가 있습니다.

• 안전 순서열
  • 교착 상태 없이 안전하게 모든 프로세스들에 자원을 할당할 수 있게하는 순서
• 안전 상태
  • 교착 상태없이 모든 프로세스가 자원을 할당받고 종료될 수 있는 상태
  • 안전 순서열이 있는 상태
• 불안전 상태
  • 교착 상태가 발생할 수도 있는 상태
  • 안전 순서열이 없는 상태

 

➡ 교착 상태 회피는 항시 안전 상태를 유지하며 자원을 할당하는 방식입니다.

대표적인 알고리즘에는 은행원 알고리즘이 있습니다.

 

교착 상태 검출 후 회복

프로세스가 자원을 요구하면 일단 할당 후 교착 상태가 검출(발생)하면 회복하는 방식입니다. 

교착 상태를 회복하는 방식에는 두 가지가 있습니다.

• 선점을 통한 회복
  • 교착 상태가 해결이 될 때까지, 한 프로세스씩 자원을 몰아주는 방식입니다.
• 프로세스 강제 종료를 통한 회복
  • 교착 상태에 놓인 프로세스 모두를 강제 종료하는 방식
    • 단점: 작업 내역을 잃을 위험성 존재
  • 교착 상태가 해결될 때까지 한 프로세스씩 강제 종료하는 방식
    • 단점: 한 프로세스 종료하고 교착 상태가 해결되었는지 확인하는 작업을 반복해야 함 ➡ 오버헤드 발생

 

[참고]
문제 발생의 빈도수나 심각성에 따라서 최대 효율을 추구하기 위해 교착 상태 무시 - 타조 알고리즘을 선택하기도 합니다.

 

 

 

 

 

 

 

---

 

 

 

관련 포스팅:

1. [운영체제] 운영체제는 프로그램이다?! - 1/5

2. [운영체제] 프로세스와 스레드 - 2/5

3. [운영체제] CPU 스케줄링 알고리즘 - 3/5

4. [운영체제] 프로세스와 스레드의 동기화 - 4/5

5. [운영체제] 교착 상태(데드락, Deadlock) - 5/5

 

 

 

 

출처:

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

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