교착상태

서로 물러서지 않고 양보를 하지 않아서 무한히 대기하는 상태

한쪽이 양보를 해야 함(프로세스가 처리를 해줘야 한다)

 

교착상태: 프로세스들이 각자 자원을 점유하고 있음에도 다른 프로세스가 점유한 자원을 요청하여 무한하게 대기하는 상태

하드웨어적 자원: CPU, 기억장치, 입출력 장치

소프트웨어적 자원: 파일, 세마포어

 

각자 자원 유형은 여러개의 instance(사례)를 가질 수 있다

자원을 사용하려면 

요청->사용->해제 순서대로

 

교착상태는 다음 네 조건이 동시에 만족해야 한다.

1. 상호배제 : 오직 한 프로세스만 자원을 점유할 수 있다

2. 점유와 대기 : 하나의 자원을 점유하면서도 다른 자원에 대기하는 것

3. 비선점: 점유된 자원은 강제 반환 X 오로지 프로세스가 작업을 마치고 자발적으로 반환

4. 순환 대기 : 2개 이상이 원형을 이루며 서로의 것을 점유하려고 대기하는 상태

 

정점은 2가지가 있다. 프로세스 or 자원

요청 연결선: 프로세스 -> 자원

할당 연결선: 자원 -> 프로세스

 

 

 

교착 아닌 사례 : 서로가 필요한 만큼 자원을 점유하고 원한다. 

 

교착 상태 사례: 주기 사이클이 존재하며 할당이 부족하다..

 

 

아래와 같이 사이클이 존재한다고 꼭 교착상태는 아니다.

 

 

사이클이 있다는 것은 교착상태 가능성이 있다는 것이다.

자원유형에 하나의 사례만 있으면 교착상태

자원유형에 여러 사례가 있으면 교착상태 가능성

 

---

 

교착상태 처리 방법  3가지 

1. 교착상태가 발생하지 않도록 예방 (prevention)
2. 교착상태를 가능한 회피 (avoidance)
3. 교착상태를 허용하고, 발생을 탐지한 후, 복구 (detection & recovery)

 

 

1, 교착상태 예방

1.  상호배제
   • 공유 가능한 자원은 동시 접근 허용 
   • 한계: 공유 가능한 것만 가능
2. 점유와 대기
   1. 프로세스 실행되기 전 사용할 모든 자원 요청
   2. 자원을 전혀 가지고 있지 않을 때만 자원 요청
   3. 단점: 자원의 낮은 활용률,, 실제로 사용하지 않을 때에도 점유하고 있기에... 기아상태 가능성도 있다
3. 비선점
   1. 자원을 요청하여 대기하게 되면 가지고 있던 자원 반납
   2. 이후, 대기 중인 프로세스는 이전 자원들과 함께 새 자원을 모두 갖게 되면 다시 시작
4. 순환 대기
   1. 일련번호를 부여( 순서를 부여) 하고, 프로세스는 오름차순 정렬을 하여 자원을 요청

 

예방법들은 자원의 사용률을 저하시키는 문제점 존재

 

---

 

교착상태 회피 

자원유형마다 필요한 최대 개수 선언하고, 운영체제는 이 정보를 이용하여 다음과 같이 교착상태가 되지 않게 한다.

안정상태 -> 할당

불안정 상태 -> 할당 x ==> 교착상태 회피

 

안정상태 예시

 

안정상태 예시

 

 

 

교착상태 회피는 시스템이 불안정 상태에 들어가지 않도록 함

 

 

 

 

 

 

 

 

 

 

대표적인 예시 : 은행가 알고리즘

 

 

 

---

교착상태 탐지

 교착상태가 일어나도록 허용함

 교착상태가 발생했는 지를 탐지하는 알고리즘 수행

 교착상태로부터 회복하는 알고리즘 수행

 

'

 

 

탐지 알고리즘 예제

 

교착상태로부터 회복 (recovery)

 시스템 관리자가 수동적으로 처리

 운영체제가 자동적으로 처리

 프로세스 종료

           교착상태에 있는 모든 프로세스를 종료시킴

           교착상태가 해결될 때까지 프로세스를 하나씩 종료

 자원 선점

           프로세스로부터 자원을 빼앗아서 이들을 교착상태가 해결될 때까지 다른 프로세스에게 준다

•