자원 할당 그래프
운영체제 자원할당 그래프: 시스템에서 사용 가능한 자원을 표현하는 그래프
-
원 (Circle):
원은 실행 중인 독립적인 프로세스 -
사각형 (Rectangle):
-
자원, Resource
-
안의 작은 점: 자원의 수 표기 가능
-
화살표 (Arrow):
화살표는 자원과 프로세스 간의 할당 또는 관계
원 → 프로세스화살표는 해당 자원이 특정 프로세스에게 할당되었음을 표현
프로세스 → 자원화살표는 해당 프로세스가 특정 자원을 요청하고 있는 상태
- 왼쪽 그래프:
P1은 R2 자원 1개를 할당받았고, P2도 R2 자원 1개를 할당받은 상태. P3이 R2 자원 1개를 요구.
P2는 R3 자원을 요구. R3는 P3에게 할당.
데드락이 발생!
P1은 R1 자원을 요구하고, 이 자원은 P2에게 할당되어 있다. 마찬가지로 P2는 R3 자원을 요구하고, 이 자원은 P3에게 할당되어 있다. 즉, 각 프로세스가 서로가 가진 자원을 대기하고 있으며, 더 이상 진행할 수 없는 상태가 됨. 이렇게 자원을 대기하는 사이클이 존재하므로 데드락이 발생@
- 오른쪽 그래프:
P1은 R2 자원 1개를 할당받았고, P4도 R2 자원 1개를 할당받은 상태. P3가 R2 자원 1개를 요청.
데드락이 발생하지 않음!
P4가 가진 R2 자원을 반납할 수 있다. P3이 이를 할당받을 수 있으므로 프로세스들이 상호 간에 자원을 대기하는 사이클이 없다. 따라서 데드락이 발생하지 않는다!
Deadlock의 처리 방법
Deadlock Prevention(데드락 예방) (미리 조치를 취하는 가장 강력한 방법)
- 자원 할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것
Deadlock Avoidance(데드락 회피)
- 자원 요청에 대한 부가적인 정보를 이용해서
- deadlock의 가능성이 없는 경우에만 자원을 할당
- 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당
Deadlock Detection and recovery(데드락 검출 및 복구)
Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 Deadlock 발견시 recover
Deadlock Ignorance(데드락 무시)
- 데드락이 발생하면 시스템이 어떤 조치도 취하지 않으며 사용자 프로세스나 애플리케이션에서 데드락에서 처리
- Deadlock을 시스템이 책임지지 않음
- UNIX를 포함한 현대의 대부분의 OS가 채택
1. Deadlock Prevention
Mutual Exclusion
공유해서는 안되는 자원의 경우 반드시 성립해야 함
Hold and Wait
프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다.
방법1. 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법
방법2. 자원이 필요한 경우 보유 자원을 모두 놓고 다시 요청
No Preemption
process가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨.
모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다.
State를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용(CPU, memory)
Circular Wait
모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당
예를 들어 순서가 3인 자원 R1를 보유 중인 프로세스가 1인 자원 Rj을 할당받기 위해서는 우선 Rj를 release해야 한다.
=> Utilization 저하, throughput 감소, starvation 문제.
데드락 예방은 강력한 방법이지만, 모든 상황에서 데드락의 발생 조건을 만족시키지 않는 것은 현실적으로 어려울 수 있다. 따라서 데드락 예방과 함께 다른 방법을 조합하여 데드락을 최소화하는 전략을 사용하는 것이 일반적이다.
2. Deadlock Avoidance(데드락 회피)
-
자원 요청에 대한 부가정보를 이용해서 자원 할당이 deadlock으로부터 안전한지 동적으로 조사해서 안전한 경우에만 할당 -> 데드락이 발생하지 않을 경우에만 자원할당
-
가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법임
-
safe state
: 시스템 내의 프로세스들에 대한safe sequence가 존재하는 상태 -
safe sequence
: 프로세스의 sequence <P1, P2, ... , Pn>이 안전하려면 Pi (1 ≤ i ≤ n)의 자원 요청이 “가용 자원 + 모든 Pj (j < i)의 보유 자원”에 의해 충족되어야 함 => 모든 프로세스들이 원활하게 실행될 수 있는 순서 -
조건을 만족하면 다음 방법으로 모든 프로세스의 수행을 보장
Pi의 자원 요청이 즉시 충족될 수 없으면 모든 Pj (j < i)가 종료될 때까지 기다린다.
P(i-1)이 종료되면 Pi의 자원 요청을 만족하여 수행한다.
자원 할당 그래프 알고리즘 (Resource Allocation Graph Algorithm) - 자원의 instance가 1개
Claim edge (예약 간선)Pi → Rj
프로세스 Pi가 자원 Rj를 미래에 요청을 할 수 있음을 뜻함 (점선으로 표시)- 프로세스가 해당 자원 요청 시
request edge(요청 간선)으로 바뀜 (실선으로 표시) - Rj가 반납되면
assignment edge(할당 간선): 실선은 다시 예약 간선으로 바뀐다. - 요청 간선의 할당 간선 변경 시 (점선을 포함하여) 사이클이 생기지 않는 경우에만 요청 자원을 할당한다.
- 사이클 생성 여부 조사시 프로세스의 수가 n일 때
O(n^2)시간이 걸린다.
요청 간선의 할당 간선 변경 시 사이클이 생기지 않는 경우에만 요청 자원을 할당하는 것이 데드락 회피 알고리즘의 핵심 원칙. 시스템은 자원 할당 그래프를 계속 갱신하면서 사이클이 생성되는지 여부를 파악함. 사이클이 생성되지 않으면 자원을 할당하고, 생성되면 데드락을 피하기 위해 요청을 대기.
그러나 사이클 검사는 프로세스의 수가 n일 때 O(n^2) 시간이 걸린다는 단점. 이는 자원 요청과 반납이 발생할 때마다 모든 프로세스의 간선을 검사해야 하기 때문에 시간 복잡도가 높아지기 때문
은행가 알고리즘 (Banker's Algorithm)
: 자원 요청 시 자원을 할당한 뒤에도 데드락이 발생하지 않는지 사전에 판단하는 방법
가정
모든 프로세스는 자원의 최대 사용량을 미리 명시
프로세스가 요청 자원을 모두 할당받은 경우 유한 시간 안에 이들 자원을 다시 반납한다.
방법
기본 개념: 자원 요청시 안전 상태를 유지할 경우에만 할당
총 요청 자원의 수가 가용 자원의 수보다 적은 프로세스를 선택 (그런 프로세스가 없으면 불안전 상태)
그런 프로세스가 있으면 그 프로세스에게 자원을 할당
할당받은 프로세스가 종료되면 모든 자원을 반납
모든 프로세스가 종료될 때까지 이러한 과정을 반복
예시
A 자원: 10개 인스턴스
B 자원: 5개 인스턴스
C 자원: 7개 인스턴스
-
Allocation(현재 할당 정보)은 현재 각 프로세스에 할당된 자원의 수를 뜻한다. -
Max(최대 요청 정보)는 각 프로세스마다 최대로 할당 받고 싶은 자원의 수를 뜻한다. -
Available(현재 가용 자원의 수)은 각 자원이 프로세스에게 추가로 할당 할 수 있는 가용 자원의 수를 뜻한다. -
Need는 각 프로세스가 현재 최대로 필요로 하는 자원의 수를 뜻하며, Max에서 Allocation을 뺀 값이다. -
자원은 현재 가용 자원을 보고, Need만큼 자원을 줄 수 있는 프로세스를 하나도 찾지 못하면 불안전한 상태가 된다. 있다면 해당 프로세스에게 자원을 주고, 프로세스가 끝날 때 모든 자원을 가져온다.
이 과정을 반복하면 <P1, P3, P4, P2, P0>라는 안전 순서열
3. Deadlock Detection and Recovery(데드락 탐지 및 회복)
Deadlock Detection
single instance만약 자원할당 그래프에 cycle이 존재한다면, 데드락이 발생한 것으로 간주.
Multiple instance
- Banker's algorithm과 유사한 방법 활용
Wait-for 그래프 알고리즘 (single instance)
- Wait-for 그래프는 프로세스와 자원 간의 대기 관계를 나타내는 방향 그래프.
- 프로세스만으로 노드를 구성하며, Pj가 가지고 있는 자원을 Pk가 기다리고 있는 경우에는 Pk → Pj로 표시.
- 자원 할당 그래프와 달리, 각 자원 당 하나의 인스턴스만 존재하므로 해당 자원이 사용 중인지 여부를 확인할 필요가 없다.
- 알고리즘은 주기적으로 Wait-for 그래프에 cycle이 존재하는지 조사. 시간 복잡도는
O(N^2)
multiple instance
Request는 현재 실제로 요청한 자원량
safe sequence: <P0, P2, P3, P4, P1>
데드락 회복
회복 방법
-
Process termination
모든 프로세스 강제 종료
데드락이 해소될 때 까지, 하나씩 kill -
Resource Preemption
a. 비용을 최소화할 victim을 선정한다.
b. safe state로 rollback 해서 프로세스를 다시 시작한다.
c. 기아 문제가 발생 가능
- 동일한 프로세스가 계속해서 victim으로 선정되는 경우
- cost factor에 rollback 횟수도 같이 고려
[이화여자대학교 반효경 교수님 운영체제 강의를 정리한 내용입니다.]
