<Deadlock의 개념적 정의>
• 어떤 집합 내에 있는 모든 프로세스가 대기 상태이고, 각 프로세스가 이 집합 내의 다른 프로세스가 갖고 있는 자원을 기다리고 있으면 교착상태에 있다고 한다.
<Deadlock의 정의 조건 4가지>
• Mutual exclusion 상호배제
-오직 한 프로세스만 자원 사용 가능
• No preemption 비선점
-점유된 자원은 강제 해제 불가
• Hold and wait 점유와 대기
-프로세스는 최소 하나의 자원을 점유하고 있고, 다른 프로세스가 점유 중인 다른 프로세스를 기다리고 있어야 함
• Circular wait 원형 대기
-프로세스의 집합 {P,P,...,P}이 존재, 순환적으로 대기
-자원 할당 그래프
<Deadlock 처리>
① 데드락 예방/회피 –> 애초에 발생 안 하도록
-OS가 데드락 발생 상황 미리 예견해서 발생하지 않도록 자원 할당
-자원을 보수적으로 할당. 예측이 틀릴 수도. 데드락 발생 가능성이 있으면 자원을 안 주니까 자원 이용률이⇩⇩
② 데드락 detection and recovery – 탐지, 해결
<Deadlock 교착상태 예방>
-
상호배제 막기 –>특성 자체를 바꾸므로 어려움.
• 불가능
-어떤 자원은 근본적으로 공유할 수 없다. -
비선점 막기 –>특성 자체를 바꾸므로 어려움.
• 선점적으로. 중간에 멈추고 다른 애가 사용하도록
-중지된 프로세스는 처음부터 다시 시작해야 하는 등 부가적인 문제 발생 가능. (프린트 예시 – 다시 프린트) -
점유와 대기 막기
• 실행되기 전에 필요한 모든 자원을 점유하는 방법
-대기할 일이 없음.
-어떤 자원이 필요한지 미리 아는 것이 어려움.
-필요할 것 같은 자원을 다 가져오고, 그런 자원을 오래 사용하지 않을 수 있으므로 자원의 사용 효율⇩⇩
-기아 발생 가능성(자원 할당 영구적으로 대기) -
순환 대기 막기
• 각 자원에 번호를 부여해 낮은 번호의 자원부터 순서대로 할당
-한 방향이므로 0으로 다시 돌아오지 않음
-자원이 하드웨어마다 달라서 순서 부여가 어려움.
⇨완벽하게 예방 불가능.
⇨적당히 방지하고, 발생 후 recovery하는 것이 좋다.
일반적으로는 코드가 잘 작동하다가,
특정한 상황에 우연적으로 동시에 진행된다거나 하는 때에 데드락이 발생한다. 그래서 알아차리기가 어렵다.
<교착상태 회피(Deadlock Avoidance)>
점유와 대기 막기를 약간 변형해서 적당히 방지하기.
a prior information이 필요. 미리 필요한 자원 알기.
데드락이 발생할지 안 할지 예측할 수 있음.
• resource-allocation state: 현재 이용가능한 자원 개수, 할당되어있는 자원 개수, 프로세스가 얼마만큼 앞으로 요청할지 maximum(최대 수요 개수) 등의 정보
<Banker’s Algorithm 은행가 알고리즘>
• 일반적인 경우 사용가능한 교착상태 회피 알고리즘
• 유동성이 없는 상태. 요구되는 자원을 이미 빌려 가고, 추가적인 자원을 더 줘야 되돌려 받을 수 있는 상태.
[은행가 알고리즘 조건]
n개의 프로세스
m개의 자원 (자원의 유형 수)
-각각의 프로세스는 미리 maximum use를 선언해야 함.
-프로세스는 자원을 요청 후 기다릴 수 있어야 함.
-프로세스는 자원을 다 얻으면 유한한 시간 내에 사용 후 반환해야 함.
[안전상태] - 교착상태를 회피한 상태
Safe state: Safe sequence가 하나라도 있는 상태.
Safe sequence: 시스템에서 안전상태에 들게 하는 자원 할당의 특정한 순서
Unsafe: 데드락이 발생할 수도 있는.
• 안전상태는 교착상태가 될 수 없는 상태
• 교착상태는 안전상태의 반대인 위험 상태에만 존재
• 모든 위험 상태가 교착상태는 X
• 시스템은 초기에 안전상태
① Available[1:m]
•이용가능한 자원 유형의 개수
② Max[1:n, 1:m]
•각 프로세스가 요구하는 최대 개수
③ Allocation[1:n, 1:m]
•현재 할당된 각각의 자원 유형의 개수
④ Need[1:n, 1:m]
•앞으로 요청할 자원
•Max[i, j] = Allocation[i, j] + Need[i, j]
[뱅커스 알고리즘 종류]
‣1. Safety 알고리즘
-현재 상태가 safe인지 판별
‣2. Resource-Request 알고리즘
-어떤 요청이 들어왔을 때 이 요청을 처리해도 되는지
-변경된 상태에 Safety 알고리즘 해보기
[Safety Algorithm]
•Safe sequence: <P1, P3, P4, P2, P0> 존재
[Resource-Request Algorithm]
<Banker’s 알고리즘 단점>
• 실제로는 사용하기 어려움. 이론을 제안하는 것.
• 프로세스마다 필요한 자원의 수를 미리 알기가 어려움.
• 시스템에서 사용가능한 자원 수가 일정하지 않음.
• 보수적으로 자원을 할당하여 자원 이용도가 낮음.
• 성능이 낮아짐. 오버헤드가 큼.(nm번의 search 필요)
• 이런 회피가 쉽지 않아 detection한다.
<Deadlock 교착상태 탐색 Detection/복구 Recovery>
-데드락 prevention은 비싸고 비효율적.
-Detection도 여전히 비싸고, 복구가 불가능할 수도.
• 적합하지 않은 상황 – 완전히 미리 예방해야 함.
① Single instance (단일 인스턴스)
-현재 상황만 보고 판단
-순환 고리 사이클이 생기면 deadlock
② Multiple instances
-deadlock detection algorithm이 필요함
<① 각 리소스 유형의 Single instance>
• wait-for 그래프 이용 (리소스가 하나씩이므로.)
-상태를 시스템에서 유지함.
• 주기적으로 판단 알고리즘 호출 – 순환 있으면 데드락
• 그래프에서 cycle을 탐지하는 알고리즘:O(n^2). n=정점
<② Multiple instances> = max가 필요XX
• request = 요청했지만 아직 할당받지 못한 자원의 수
• finish[i]=false인 게 하나라도 있으면, 데드락 발생
<Deadlock Recovery 복구>
• 프로세스 termination종료 – 대부분 프로그램의 경우
‣모두 종료: 너무 과함. 비효율적.
‣하나씩 종료시켜보기: 일반적으로는 덜 중요한 프로세스부터 종료시키기 / 또는 남은 시간 많이 남은 애 / 자원을 많이 점유하고 있는 애 / 얼마나 더 요구 고려 / 등등
• 리소스 선점 preemtive – 종료하면 안되는 경우
‣자원을 점유하기 이전 상태로 되돌리기
-희생자 선택 필요 /rollback 어느 시점으로 /기아 고려
