[혼자 공부하는 컴퓨터구조+운영체제] Chapter 13 교착 상태

Chapter 13 교착 상태

1. 교착 상태란

교착 상태/ 식사하는 철학자 문제/ 자원 할당 그래프/ 교착 상태 발생 조건

식사하는 철학자 문제(dining philosophers problem)

교착 상태의 발생을 보여주는 예시

철학자 사이에 식사에 필요한 포크/ 식사는 2개의 포크로 먹을 수 있는 음식

 

철학자 식사 순서

1. 계속 생각을 하다 L 포크 사용 가능하면 집어듬
2. 계속 생각을 하다 R 포크 사용 가능하면 집어듬
3. L, R 포크 모두 집어들면 정해진 시간동안 식사를 함
4. 식사 시간 끝나면 R 포크 내려놓음
5. R 포크 내려놓은 뒤 L 포크 내려놓음
6. 다시 1번부터 반복

=> 모든 철학자 동시에 포크 집어 식사 -> 어떤 철학자도 식사 X 영원히 생각만 하는 상황 발생

모든 철학자 L 포크 집어들면 모두 R 포크 집어들 수 X

-> 모든 철학자는 다른 철학자가 포크 내려놓을 때까지 기다림

철학자: 프로세스 or 스레드/ 포크: 자원/ 생각하는 행위: 자원을 기다리는 것
포크는 한 번에 하나의 프로세스 or 스레드만 접근할 수 있음 = 임계 구역

 

교착 상태(deadlock)

• 일어나지 않을 사건을 기다리며 무한히 대기하는 현상
• 교착 상태 해결
  1. 교착 상태 발생했을 대의 상황 정확히 표현
  2. 교착 상태가 일어나는 근본적인 이유에 대해 알아야 함

---

자원 할당 그래프(resource-allocation graph)

• 어떤 프로세스가 어떤 자원을 사용하고 있고, 어떤 자원을 기다리고 있는지를 표현하는 간단한 그래프
• 교착 상태를 표현할 수 있음
• 규칙
  1. 프로세스 - 원/ 자원의 종류 - 사각형
  2. 사용할 수 있는 자원의 개수 - 자원 사각형 내에 점으로 표현
  3. 프로세스가 어떤 자원을 할당받아 사용 중: 자원 -> 프로세스(화살표 표시)
  4. 프로세스가 어떤 자원 기다리고 있음: 프로세스 -> 자원(화살표 표시)

현재 사용 가능한 SSD 자원 3개/ CPU 자원 2개/ 프린터 1개
프로세스 A) SSD 할당받아 사용 중
프로세스 B, C) CPU 할당받아 사용 중
프로세스 D) 프린터 사용 중
프로세스 E) 프린터 자원, 프로세스 F) CPU 할당 기다리고 있음

---

교착 상태 발생 조건

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

• 상호 배제(mutual exclusion): 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없을 때
• 점유와 대기(hold and wait): 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태
• 비선점(nonpreemptive): 자원을 이용하는 프로세스의 작업이 끝나야만 이용할 수 있음
  = 어떤 프로세스도 다른 프로세스의 자원 강제로 빼앗지 못함
• 원형 대기(circular wait): 프로세스들이 원의 형태로 자원을 대기
  원의 형태를 띈다고 해서 반드시 교착 상태 발생하는 것 X

---

2. 교착 상태 해결 방법

교착 상태 예방/ 교착 상태 회피/ 교착 상태 검출 후 회복

교착 상태 예방

교착 상태 발생 조건 4가지(상호 배제/ 점유와 대기/ 비선점/ 원형 대기) 중 하나 충족하지 못하게 하는 방법

• 상호 배제 없애기
  • 모든 자원을 공유 가능하게 만듦 
  • (-) 이론적으로는 교착 상태 없앨 수 있지만, 현실적으로 모든 자원의 상호 배제 없앨 수 X
• 점유 대기 없애기
  • 한 프로세스에 필요한 자원 몰아주고, 다른 프로세스에 필요한 자원 몰아줘야 함
  • 당장 자원 필요해도 대기, 사용 X 오랫동안 할당되는 자원 ↑
  • (-) 자원 활용률 ↓
  • (-) 자원 ↑ 프로레스가 자원 ↓ 프로세스에 비해 동시에 자원 사용할 타이밍 확보하기 어려움
    => 자원 ↑ 프로세스 무한정 대기 -> 기아 현상 야기 우려
• 비선점 조건 없애기 
  • CPU는 프로세스들이 선점할 수 있는 대표적인 자원
    -> 한 프로세스 CPU 이용하다가 일정 시간 지나면 작업이 끝나지 않아도 다른 프로세스 CPU 할당받아 사용 O
  • But, 모든 자원이 선점 가능 X
    • ex. 한 번에 하나의 프로세스만 이용 가능한 프린트 자원
    • 한 프로세스가 프린트 이용하는 돚우에 다른 프로세스가 프린트 자원 빼앗아 사용 X
  • (-) 범용성 ↓
• 원형 대기 조건 없애기
  • 모든 자원에 번호 붙이고, 오름차순으로 자원 할당
  • 앞 3가지 보다 실용적
  • (-) 모든 컴퓨터 시스템 내 존재하는 수많은 자원에 번호 붙이는 일 간단 X, 번호 -> 특정 자원의 활용률 ↓ 가능성 O

=> 교착 상태의 발생 조건 원칙적으로 제거 -> 교착 상태 사전에 예방하는 방식 

-> 교착 상태가 발생하지 X 보장 But, 부작용 O

---

교착 상태: 한정된 자원의 무분별한 할당으로 인해 발생하는 문제

=> 프로세스들이 할당할 수 있는 자원 충분한 상황, 프로세스들 한두 개의 적은 자원 요구 -> 교착 상태 발생 X

교착 상태 회피

• 교착 상태가 발생하지 않을 정도만 조심 조심 자원을 할당하는 방식
• 안전 상태를 유지할 수 있는 경우에만 자원을 할당하는 방식
• 프로세스들에 배분할 수 있는 자원의 양을 고려 -> 교착 상태가 발생하지 않을 정도의 양만큼만 자원을 배분하는 방법

안전 순서열(safe sequence): 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서

• 안전 상태(safe state)
  • 교착 상태 발생 X 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태
  • 안전 순서열이 존재하는 상태
• 불안전 상태(unsafe state)
  • 교착 상태가 발생할 수도 있는 상황
  • 안전 순서열이 없는 상태

할당 가능한 자원: 12
할당한 자원(P1, P2, P3 현재 사용량의 총합): 9 (5/ 2/ 2)
남은 자원(할당 가능한 자원 - 할당한 자원): 12 - 9 = 3
=> 안전 순서열(P2 -> P1 -> P3) -> 안전 상태

프로세스 P1, P2, P3이 모두 최대로 자원을 요구한 최악의 상황
할당 가능한 자원: 12
할당한 자원(P1, P2, P3 현재 사용량의 총합): 9 + 2 = 11 (5/ 2 + 2/ 2)
남은 자원(할당 가능한 자원 - 할당한 자원): 3 - 2 = 11
=> P2 정상적으로 작업 끝내고 가지고 있던 자원 반환 

할당 가능한 자원: 12
할당한 자원(P1, P2, P3 현재 사용량의 총합): 11 - 4 = 7 (5/ 0/ 2)
남은 자원(할당 가능한 자원 - 할당한 자원): 1 + 4 = 5 
=> P1에 남은 자원 5개 할당 -> P1 작업 정상적으로 완료

할당 가능한 자원: 12
할당한 자원(P1, P2, P3 현재 사용량의 총합): 12 - 10 = 2 (0/ 0/ 2)
남은 자원(할당 가능한 자원 - 할당한 자원): 0 + 10 = 10

할당 가능한 자원: 12
할당한 자원(P1, P2, P3 현재 사용량의 총합): 10 (5/ 2/ 3)
남은 자원(할당 가능한 자원 - 할당한 자원): 12 - 10 = 2
=> 불안전 상태 = 교착 상태 발생할 위험 있음

프로세스 P1, P2, P3이 모두 최대로 자원을 요구한 최악의 상황
할당 가능한 자원: 12
할당한 자원(P1, P2, P3 현재 사용량의 총합): 10 + 2 = 12 (5/ 2 + 2/ 3)
남은 자원(할당 가능한 자원 - 할당한 자원): 2 - 2 = 0
=> P2 작업을 끝내고 자원을 반환

할당 가능한 자원: 12
할당한 자원(P1, P2, P3 현재 사용량의 총합): 12 - 4 = 8 (5/ 0/ 3)
남은 자원(할당 가능한 자원 - 할당한 자원): 0 + 4 = 4
=> But, P1, P3 요구 들어줄 수 X
= 서로가 보유한 자원 무한정 기다림 = 불안전 상태로 교착 발생

 

프로세스와 스레드 자원 사용

1. 자원을 운영체제에 요청
2. 운영체제로부터 자원 할당 받아 사용
3. 자원의 사용이 끝났다면 자원 반환

---

교착 상태 검출 후 회복

• 교착 상태 발생을 인정하고 사후에 조치하는 방식
• 프로세스들이 자원 요구할 때마다 모두 할당, 교착 상태 발생 여부 주기적으로 검사
• 교착 상태 검출 -> 회복
  • 선점
    • 교착 상태가 해결될 때가지 한 프로세스씩 자원을 몰아주는 방식
    • 다른 프로세스로부터 자원 강제로 빼앗고 한 프로세스에 할당
  • 프로세스 강제 종료
    • 가장 단순하면서 확실한 방식
    • 운영체제) 모두 강제 종류 -> 한 번에 교착 상태 해결 But, 프로세스 작업 내역 잃게 될 가능성 있음
      / 한 프로세스씩 강제 종료 -> 작업 내역 잃는 프로세스 최소화 But, 교착 상태 확인 과정에서 오버헤드 
  • 타조 알고리즘(ostrich algorithm)
    • 발생하는 잠재적 문제를 무시로 대처하는 방식

---

출처

[한빛미디어] 혼자 공부하는 컴퓨터 구조+운영체제