교착상태 회피 & 탐지 회복 & 기아

교착상태 회피

항상 안전상태를 떠나지 않도록 고수하기 위함

시스템에 순환대기 상황이 발생하지 않도록 함

자원할당 상태 검사 -> 가용 자원 수, 할당된 자원 수, 프로세스들의 최대 요구 수

 

안전상태 : 시스템이 안전 순서를 찾을수있다면 안전한 상태임(=불안전/교착상태예방가능)

찾을 수 없다면 불안전상태(무조건 교착상태 발생하는 것은 아님)

 

회피 알고리즘

1. 자원이 1개 -> 자원할당 그래프 알고리즘

정점(프로세스 P,  자원 R)과 간선으로 이루어짐

그래프가 사이클을 형성하면 교착상태(자원의 인스턴스가 여러개면 반드시 교착은X)

교착상태

교착상태 아님

 

 

2. 자원이 2개 이상일 경우 -> 은행원 알고리즘

다익스트라 알고리즘 응용하여 사용

프로세스에서 운영체제에 자원을 요청할 때 마다 운영체제에서 실행되는 알고리즘

일단 해당 자원 요청을 허가한다고 가정, 그 이후 교착상태가 발생하지 않는 최적의 케이스가 존재하는지 시뮬레이션

 

구현 알고리즘

• 자원요청 알고리즘

자원요청이 안정한지 아닌지 검사

(프로세스가 자원을 요청하면 우선적으로 남아있는 자원보다 같거나 작게 요청햇는지 확인 후 가상으로 할당. 그 이후 남은 자원을 가지고 시스템 상태를 확인한 후 안전하면 가상으로 할당했던 자원을 실제로 할당.(아니면 반환) )

• 안전 알고리즘

시스템이 안정상태인지 불안정 상태인지 검사

 

단점

• 시스템 과부하가 증가한다.
• 사용자 프로세스가 일정해야 한다.
• 할당 가능한 자원의 일정량을 요구한다
• 자원을 보유한 상태로 끝낼 수 없음
• 자원 이용률이 낮음

 

교착상태 탐지

 

교착상태가 발생하도록 허용함

교착상태인지 검사하는 알고리즘과 회복하는 방식을 필요로 함

 

탐지 알고리즘

1. 하나의 인스턴스를 갖는 시스템 -> 대기그래프(Wait - for graph)

기존 자원할당 그래프에서 자원노드를 제거하여 만든 것

사이클을 형성하면 교착상태임

2. 여러 개의 인스턴스를 갖는 시스템

-> 은행원 알고리즘처럼 시시각각 내용이 달라지는 자료구조 사용

 

탐지알고리즘 실행 시점

고려사항

1. 교착상태가 얼마나 자주 일어나는지
2. 교착상태가 일어나면 통상 몇개의 프로세스가 연루되는지

• 자원요청 때 마다 호출 -> 오버헤드가 너무 큼
• 자원 요청 했는데 즉시 만족 못할 경우

-> 교착상태에 연루된 프로세스 및 누가 유발했는지 알 수 있음

• 지정된 시간 간격

Ex) 한시간에 한번, CPU이용률이 40% 이하일 때…

 

교착상태 회복

교착상태 회복 == 순환대기를 탈피하는 것 => 할당된 자원 해제

1. 프로세스 중지

• 교착상태 프로세스를 모두 중지

장점 : 교착상태의 순환대기를 확실히 해결 할 수 있음

단점 : 자원과 시간의 비용이 크다

  오래 연산했을 가능성이 있는 프로세스의 부분결과를 폐기하고 다시  연산할 수 있다.

• 한 프로세스씩 중지

한 프로세스가 중지될 때 마다 교착상태 탐지하여 확인

단점 : 교착상태 탐지 알고리즘을 호출하는 부담이 큼

 

 

• 부분종료방식

어느 프로세스를 중지시킬지 결정(프로세스 스케줄링과 유사)

최소비용으로 프로세스들을 중지시키는 방법을 찾아야 함

고려사항

• 프로세스들의 우선순위
• 프로세스가 수행된 시간, 앞으로 종료하는데 필요한 시간
• 프로세스 종료를 위해 필요한 자원 수
• 프로세스 종료하는데 더 필요한 프로세스 수
• 프로세스가 대화식인지 일반식인지

2. 자원 선점

프로세스의 자원을 선점하여 교착상태가 해결될 때 까지 선점한 다른 프로세스에 할당하여 이용하는 방법

고려사항 -> 선점 자원 선택, 복귀, 기아

1. 교착상태의 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에 할당, 해당 프로세스는 일시정지
2. 우선순위 낮은 프로세스와 수행횟수 적은 프로세스 등을 위주로 선점

단점 : 기아상태 출현이 있다(비용 문제로)

=> 복귀 횟수로 같은 희생자가 선택되지 않게 함

 

 

기아상태

작업이 결코 사용될 수 없고 계속 기다려야 하는 자원을 할당할 때 발생하는 결과

식사하는 철학자 문제

상황

• 철학자 5명, 포크 5개
• 식사할 때 포크 2개가 필요 => 두명만 동시 식사 가능
• 한번에 포크 하나만 들 수 있음(동시에 2개 집지 못함)

=> 포크를 세마포어로 표시하여 해결

• 철학자 4명만 테이블에 앉도록 함
• 양쪽 포크를 집을 수 있으 때만 포크를 집도록 한다.
• 홀수번째 철학자는 왼쪽 먼저 집은 뒤 오른쪽 포크를, 짝수번째 철학자는 오른쪽을 먼저 집은 뒤 왼쪽 포크를 집도록 한다.