[운영체제] 07 교착 상태 (deadlock)

수업 내용 필기. 

교착 상태가 발생하는 필요 충분 조건  4가지 경우. ( 모두 만족해야 교착 상태 발생) 

1.  상호 배제  : 각 자원은 한번에 하나의 스레드에게만 할당 
2. 스레드가 자원을 소유 하면서 대기 
3.  강제 자원 반환 불가 (비선점 )
4. 환형 대기 

 

 

 

ch 01 교착상태 문제 제기 

 

[ 에드거 다익스트라 ] 

네덜란드 아인트호벤 기술 대학의 동기화 이슈와 병렬처리를 해결하고자 낸 문제. 

 

식사하는 철학자 문제

- 5명의 철학자가 원탁에서 식사 ,식사시간은 서로 다를 수 있음

- 식사를 위해 양 옆 포크를 동시에 들어야 함. (순서 : 왼쪽 들고 오른쪽 들기)

철학자 =스레드 |  포크 = 자원 | 스파게티 = 자원이 처리할 작업.

 

 

문제 상황 ) 무한대기가 발생하는 경우 

→ 다른 경우도 대기는 발생할 수 있지만 영원히 대기하는 상태는 아님.

 

 

교착 상태의 원인 : 환영 요청 / 대기 (circular request/wait)

: 5명 모두 동시에 식사를 하는 경우 = 5명 모두 왼쪽 포크를 가지고 오른쪽을 요청하는 상태

 

교착 상태 해결 : 환형 요청 / 대기가 생기지 않게 규칙 변경 

: 마지막 철학자(5번)만 오른쪽을 먼저 잡고 왼쪽 포크를 잡게 규칙 변경 

 

---

ch 02 교착 상태

: 다중 프로그래밍의 문제점 중 하나, 스레드 동기화 문제 ( 단일 cpu인지 다중 cpu인지는 상관 X = 스케 줄링 문제 .x)

자원을 소유한 스레드들 사이에서  각 스레드는 다른 스레드가 소유한 자원을 요청하여 무한정 대기하는 상태. 

 

교착 상태 발생 )

1. (주로) 멀티 스레드 응용 프로그램에서 발생 (코딩 잘못해서 발생)

2. 커널 내에서 발생 

 

교착 상태 해결 ) 실제로 교착 상태를 막지 않고

발생하도록 두고 시스템 재시작이나 몇몇 프로그램을 종료함. 

 

 

멀티 스레드 교착상태 사례 ) 

 

두개의 스레드(thread1 , thread2) 가 임계 구역에 진입하기 위해서 2개(lock A, lock B)의 락이 모두  필요한 경우. 

각각의 스레드가 한개씩 lock을 소유한 상태에서 다른 lock을 요청 ⭐️

---

 

교착 상태의 잠재적 유발 요인 

1. 자원   : 자원은 교착 상태의 발생지. 

 

2. 자원과 스레드  : 한 스레드가 동시에 여러 개의 자원을 필요로 하는 경우가 있음. 

(스레드가 한개의 자원만 필요로 하면 교착상태를 발생 X) 

 

3. 자원과 운영체제 :  운영체제는 한번에 하나씩 자원을 할당함.

(스레드에 한번에 모든 자원을 할당하면 교착 상태는 발생 X) 

 

4. 자원 비선점      :  할당된 자원은 스레드가 자발적으로 내 놓기 전에 강제로 뺐지 못함. 

---

 

 

자원 할당 그래프 (RAG) : 교착 상태를 판단하는 그래프 

그래프 구성요소		도형
꼭짓점	스레드	원    ⚪️
	자원	사각형 ⬜️
간선	할당 간선	스레드 ⚪️ ←  자원 ⬜️
	요청 간선	스레드 ⚪️→ 자원 ⬜️

 

 

 

 

알수 있는 정보 

- 컴퓨터 시스템에 실행 중인 전체 스레드와 자원 

- 각 자원의 총 인스턴스 개수와 할당 가능한 인스턴스 개수 (가용 인스턴스 개수)

- 각 스레드가 할당받아 소유하고 있는 자원의 인스턴스 개수 (할당 인스턴스 개수)

- 각 스레드가 실행에 필요한 자원 유형과 인스턴스 개수 

 

 

---

ch 03 교착상태 해결

 

코프만 조건 4가지 

교착 상태가 발생하는 필요 충분 조건  4가지 경우. ( 모두 만족해야 교착 상태 발생) 

1.  상호 배제  : 각 자원은 한번에 하나의 스레드에게만 할당 
2. 스레드가 자원을 소유 하면서 대기 
3.  강제 자원 반환 불가 (비선점 )
4. 환형 대기 

 

 

 

교착 상태 해결 방법 

 

1. 교착 상태 예방  : 시스템 구성시 코프만 조건중 하나 이상 성립 안되게 구성

2. 교착 상태 회피 (불가능)

: 지원 할당시 교착 상태 가능성을 미리 검사함_ banker's algorith (다익스트라가 만든 알고리즘)

 

3. 교착 상태 감지 및 복구 : 교착 상태를 감지하는 프로그램을 백그라운드에서 구동 →발견시 교착 상태 해제 

4. 교착 상태 무시 : 대비책 X → 이상하면 재실행 함._ostrich algorithm⭐(현재 방식 ) 

 

 

---

 

3-1 교착 상태 예방 

•  상호배제 없애기 (구현 불가능)  :동시에 2개 이상의 스레드가 자원을 활용할 수 있게
• 스레드가 기다리지 않게 (비효율적) : 실행시 자원 한번에 할당. 
• 선점 허용 (오버헤드 큼) 
• 환형 대기 제거 : 모든 자원에 번호를 매기고  번호 순으로 할당. 

 

 

3-3 교착 상태 감지 및 복구 

 

- 자원 강제 선점 

 

- 롤백 (rollback) 

: 교착 상태가 발생하면 가장 최근 상태로 되돌림. 롤백 이후 실행하면 스케줄링등 여러 이유로 교착 발생 x 

: 시간과 메모리에 대한 부담 때문에 잘 사용 x

 

- 스레드 강제 종료 (kill process) : 데이터 손실 발생 

: 교착 상태에 빠진 스레드 중 하나를 선택하여 강제 종료. (전체가 아님!!! 하나만 ) 

 

17. 교착상태 감지 및 복구 방법에 대한 설명으로 틀린 것은? (3)

(1) 교착 상태가 발생하도록 내버려두는 방법이다. -> 롤백
(2) 백그라운드 프로세스를 이용하여 자원할당그래프로부터 교착상태를 감지하는 방법이다. -> kill process
(3) 사용자나 시스템 관리자가 교착상태를 발생하였다고 생각되면 시스템을 재시작한다. 
(4) 이 방법은 너무 많은 시간과 공간을 소모하므로 별로 사용되지 않는다. -> 롤백

---

 

 

3-4 교착 상태 무시 : ostrich 알고리즘 ⭐⭐

: 교착 상태가 발생하지 않을 거야.. 하고 회피하는 알고리즘. 

(실제로는 교착상태가 발생하지만 그걸 관리하는데 비용이 많이 듦)

 

○  리눅스, 윈도우등 현재 거의 모든 운영체제에서 사용. 

○   스레드 강제 종료나 시스템 재시작하면 큰일 하는 시스템에는 적합하지 않음 (핵 , 비행기, 미사일, 등등) _ 데이터가 소실될 수 있음.