교착상태의 원리

• 교착상태
  - 프로세스들의 집합이 더 이상 진행을 못하고 영구적으로 블록되어 있는 상태
• 발생시기
  - 시스템 자원에 대한 경쟁 도중
  - 프로세스 간 통신 도중
• 원인
  - 기다리던 사건이 결코 발생하지 않기 때문

대표적 예: Traffic Deadlock

• 공유 자원인 교차로의 네 구역에서 서로의 차가 필요한 구역을 막고 있기 때문에 이러지도 저러지도 못 하는 상황 발생

교착상태가 발생하는 예: 결합 진행 다이어그램(Joint Progress Diagram)

• Get 요청 -> 자원을 요청
• Release 요청 -> 사용한 자원을 반환

• x축은 프로세스 P의 진행, y축은 프로세스 Q의 진행
• x축의 경우 getA와 getB사이 A에 대한 자원을 흭득한 상태
• y축의 경우 getB와 getA사이 B에 대한 자원을 흭득한 상태
• 프로세스P의 경우 다음에 B를 가져와야 하지만 프로세스 Q가 가지고 있으므로 대기하고, 프로세스 Q의 경우 다음에 A를 가져와야 하지만 프로세스 P가 가지고 있으므로 서로 대기하다가 교착 상태 발생

교착상태가 발생하지 않는 예

• 프로세스 P가 A,B 자원을 요청해서 쓰지만 그때그때 사용이 끝날 때마다 바로바로 자원을 반환하여 교착 상태가 일어나지 않음
• P의 getA -> Q의 getB -> P의 ReleaseA -> Q의 getA -> Q의 realeseB -> P의 getB -> P의 releaseB 의 순서대로 가면 교착상태가 일어나지 않음을 알 수 있음 (경로4)

재사용 가능한 자원과 소모성 자원

재사용 가능한 자원

• 프로세스 사용에 의해 없어지지 않는 자원
• 프로세스가 사용한 후 다른 프로세스가 다시 사용할 수 있도록 반납
• 처리기, 입출력 채널, 주/보조 메모리, 장치, 파일이나 데이터베이스나 세마포어와 같은 자료구조 등

재사용 가능한 자원을 위해 경쟁하는 두 프로세스 예

• 다른 프로세스에서 Lock을 걸어놓은 상태에서 서로가 Lock을 걸어놓은 자원에 Request를 하게 되면 교착 상태 발생

• 가용메모리가 200KB라고 가정할 경우 두 프로세서의 요청 모두의 메모리 요청을 처리하기는 어려움
• 두 번째 요청에서 두 프로세서 모두 블록상태가 되고 교착상태 발생

소모성 자원

• 생성되었다가 시간이 지나면 소멸되는 자원
• 개수의 제한이 없음
• 자원이 소비 프로세스에 의해 사용되면 사라짐
• 인터럽트, 시그널, 메시지, I/O 버퍼 정보 등

소모성 자원에서 교착상태의 예

• 각 프로세스는 상대 프로세스로부터 메시지 수신을 기다림
• 메시지 수신 이후 상대 프로세스에게 새로운 메시지 전달
• 수신을 먼저 수행
  - 수신 프리미티브가 블록킹 타입(메시지가 올 때까지 대기)이면 교착 상태 발생
  - 발견하기 어려운 오류

자원 할당 그래프

• 프로세스와 자원 할당 관계를 표현하는데 사용

• 프로세스가 자원을 요청하는 경우
  -

• 자원이 프로세스에게 할당된 경우
  -

• 환형 대기
  - 두 개의 프로세스가 각자 서로 점유하고 있는 자원에 대해 서로 요구할 경우 환형 대기 발생 => 교착 상태로 이어짐
  -

  	- <img src="https://i.imgur.com/B3fEHic.png" width=200/>
  	- 결국 제자리로 돌아오게 되는 **순환의 형태**로 가게 되면 교착 상태 발생

• 교착상태가 아닌 경우
  - 환형 대기와 비슷한 모양이지만 자원 안에 인스턴스가 여러 개가 있어 교착 상태를 방지
  -

교착 상태 조건

• 상호 배제(mutual exclusion) 조건
  - 한 순간에 한 프로세스만이 자원을 사용 가능
• 점유대기(hold and wait) 조건
  - 이미 자원을 보유한 프로세스가 다른 자원을 요청하며 기다림
• 비선점(no preemption) 조건
  - 프로세스에 의해 점유된 자원을 다른 프로세스가 강제적으로 뺏을 수 없음
• 환형 대기(circular wait) 조건
  - 프로세스들 간에 닫힌 연결(closed chain) 존재
  - 닫힌 연결에서 블록된 프로세스가 자원을 점유하고 있는데 이 자원을 체인 내부의 다른 프로세스가 원하며 대기하고 있음

교착사태 가능	교착상태 발생
1. 상호 배제 조건	1. 상호 배제 조건
2. 점유대기 조건	2. 점유대기 조건
3. 비선점 조건	3. 비선점 조건
	4. 환형대기 조건

=> 교착상태를 해결하기 위해 다양한 접근 방법들이 제안

운영체제에서 교착상태 예방, 회피, 발견 기법 정리

접근 방법	자원 할당 정책	구체적인 기법	장점	단점
예방	보수적(자원할당 O, 조건에 따라 가능)	모든 자원을 한번에 요구	순간적으로 많은 일을 하는 프로세스에게 적합 선점(임의의 순간에 문맥교환) 불필요	효율 나쁨 프로세스 시작 지연가능성 사용할 모든 자원 미리 알고 있어야 함
		선점 가능	자원 상태의 저장과 복구가 간단한 자원에 적용 쉬움	선점이 필요보다 자주 일어남
		자원 할당 순서	컴파일 시점에 강제 시스템 설계 시점에 문제 해결 -> 동적 부하 X	점진적인 자원 할당 안됨
회피	예방과 발견의 중간 정도	교착 상태가 발생하지 않는 안전한 경로를 최소한 하나 유지	선점 불필요	자원에 대한 미래 요구량을 미리 알고 있어야 함 오랜 시간 지연 발생 가능성
발견	적극적 (자원 할당이 가능하면 즉시 할당)	주기적으로 교착 상태 발생 여부 파악	프로세스 시작을 지연시키지 않음 온라인 처리 가능	선점에 의한 손실 발생