목차
Dedlock에 대해 알아보기 전, 예시부터 알아보자.
Example 1 )
만약 다리만 일차선이라면,
다리에서 교통체증이 발생할 것이다.
이때 다리를 자원(resource)이라고 생각하면,
이때 차들이 모두 다리를 건너기 위해 기다리고 있기 때문에
deadlock이 발생한다고 할 수 있다.
Example 2 ) Dining-Philosophers Problem
다섯명의 철학자가 다 같이 배가 고프고,
책상 위에는 젓가락이 한 짝이 아닌 한 개 씩, 총 5개가 있다고 가정해보자.
각각의 철학자는 왼쪽에 있는 젓가락을 잡았다.
이때 모든 젓가락의 세마포어 (semaphore)는 0이 된다.
이후, 이들이 오른쪽에 있는 젓가락을 잡으려고 한다면,
이들은 누군가가 젓가락을 놓을 때까지 기다려야 한다.
다 같이 기다리는 상황이 발생한다. 이것이 바로 deadlock이다.
Example 3 ) Semaphore
Process1이 Resource1 을 기다리고 있고. Process2가 Resource2를 기다리고 있을 때,
Process2가 Resource2를 기다리고, Process1이 Resource1을 기다린다면, 각 process는 서로의 process를 기다리고 잇으므로
무기한 기다림이 발생한다. 이것이 deadlock이다.
Example 4 ) Deadlock in Multithreaded Application
thread1이 first_mutex를 획득했고 thread2가 second_mutex를 획득했고,
thread1은 second_mutex를 기다리고, thread2는 first_mutex를 기다린다고 가정해보자.
이때 각 thread는 서로가 획득한 mutex를 기다리고 있기 떼문에 이때 또한 deadlock이 발생한다.
Resource Type
다음은 Resource Type에 대해서 알아보자.
자원에는 물리적 자원, 논리적 자원 총 두가지 종류가 있다.
- 물리적 자원 (Physical resource types) 으로는 I/O devices (ex .. 프린터), 메모리 공간, CPU cycle 이 있다.
- 논리적 자원 (Logical resource types) 으로는 semaphores (wait일 때, request로 생각하고, signal일 때, release로 생각하자), mutex locks, 그리고 파일이 있다.
이때, 논리적 자원은 software적인 resource type 이라고 생각하면 이해하는 데 조금 더 도움이 될 것이다.
각각의 자원은 동일한 instance를 가질 수 있고,
process가 resource type의 instance를 사용하기 위해서는 OS에게 요청을 해야하고,
이를 사용한 뒤에는 반드시 release 해줘야 한다.
자원 할당 그래프 (Resource-Allocation Graph)에 대해서 알아보자.
- 방향성을 갖고 있는 그래프다.
- Nodes (V) : 프로세스, 자원을 의미ㅣ한다.
- Edges (E) : Request edge (Process가 Resource를 요청할 때), Assignment edge (Resource type의 instance를 Process가 할당했을 때)
이때, Request edge는 특정 instance를 가리키는 것이 아닌 전체 resource를 가리키는데, 이는 한 resource에 있는 instance들은 모두 동일하기 때문에 어느 instance나 할당 받아도 상관 없다.
만약 그래프가 cycle을 포함하지 않는다면,
-> deadlock에 걸리지 않는다는 것 이고, safe하다는 것이다.
만약 그래프가 cycle을 포함하고,
-> 각 resource 마다 instance가 하나만 존재한다면, deadlock이 걸린다는 것이고, unsafe하다는 것이다.
-> 각 resource 마다 instance가 여러개 존재한다면, deadlock이 걸릴 수도 있고, 안 걸릴 수도 있다.
safe : no deadlocks
unsafe : possibility of deadlock
Deadlock의 특징 (4 necessary conditions for Deadlock) 과 막는 방법 (Prevention)
아래 4가지 조건을 모두 만족해야 deadlock이 발생한다.
또한, 4가지 조건들 중 하나라도 만족하지 못하면, deadlock이 발생하지 않는다.
1. Mutual exclusion
: only one process at a time can use a resource
= 한 번에 한 process만 resource instance를 사용한다.
Prevention
- Make all resources sharable at same time (ex .. read-only file is OK)
= 모든 자원들이 한 번에 공유할 수 있게 해주면 된다. (읽기 전용 파일은 이를 만족한다)
-> 하지만, 실질적으로 mutex lock이나 printer과 같은 자원들은 실질적으로 불가능하다.
2. Hold and Wait
: a process holding at least one resource is waiting to acquire additional resources held by other processes
= 한 resource 를 할당 받고 있을 때, 다른 프로세스가 가지고 있는 resource를 기다리고 있다.
Prevention
: must guarantee that whenever a process requests a resource, it does not hold any other resources
= 프로세스가 자원을 요청할 때 마다 process다른 자원들이 이를 사용하고 있지 않도록 한다.
1) Total allocation : process requests and be allocated all its resources before it begins execution
= 프로세스가 실행을 시작하기 전에 실행에서 필요한 모든 자원들을 할당 받고, 프로세스가 종료하기 전까지 resource를 hold하고 있는다.
2) Request resource only when it holds none
= 자원을 할당받지 않고 있을 때만 다른 자원을 요청한다.
-> 하지만, 이와 같은 방법은 자원이 오랜 기간 동안 사용되지 않으면서 할당되어 있기 때문에 자원의 효율성을 낮춘다. (Low resource utilization)
3. No preemption
: a esource can be released only voluntarily by the process holding it, after that process has completed its task
= resource는 오직 프로세스가 resource를 다 사용했을 때만 release할 수 있다.
Prevention
: Allow preemption
= 현재 process로부터 선점되는 것을 허용한다.
-> 몇 자원들은 일반적으로 불가능하다. race condition이나 다양한 문제가 발생한다.
4. Circlular wait
: Cycle in resource allocation graph
= cycle이 존재해야한다.
Prevention
: 모든 자원에게 순서를 부여하고, 번호 순서대로만 자원을 요청하도록 한다.따라서 마지막 순서인 자원이 첫번째 순서인 자원을 요청할 수 없으므로, 사이클이 발생하지 않는다.
-> 항상 순서에 따라서 자원을 요청해야 하기 때문에 원하는 자원을 사용할 수 없다.
Deadlock Avoidance
Deadlock Avoidance에 대해서 알아보자.
Deadlock Avoidance Method에는 경우에 따라 크게 두가지 방법이 존재한다.
만약 resource type의 instance가 오직 1개라면, Resource-Allocation Graph Algorithm을 사용하고,
resource type의 instance가 여러개라면, Banker Algorithm을 사용한다.
일단, Resource-Allocation Graph Algorithm에 대해서 알아보자.
Resource-Allocation Graph Algorithm
: 미래를 예측하여 Deadlock이 발생할 것이라면, 자원을 할당받지 않고, Deadlock이 발생할 것 같지 않다면, 자원을 할당받는다.
Claim edge : 점선으로 표기하며, process가 미래에 요청할 수 있다는 것을 의미한다. 이는 실제로 자원을 요청할 때, request edge (실선)으로 바뀐다.
예시로 좀 더 자세히 살펴보자
resource type의 instance가 오직 하나이고, 다음 그림과 같은 상황이라고 가정해보자.
safe/unsafe를 판단할 때는 claim edge까지 포함하여 판단하기 때문에 현재는 cycle을 포함하지 않기 때문에 safe 상태이다.
만약 이 상황에서 P1이 R2를 요청하는 claim edge가 request edge로 바뀐다면, 즉 "P1 프로세스가 R2 자원을 요청한다"가 받아들여진다면, cycle을 포함하지 않으므로 safe 상태이다.
따라서, P1 process에게 R2 resource를 할당해줘도 된다.
위 그림과 같은 상황에서 P2 process가 R2 resource를 요청한다면, 다음 그림과 같은 상황은 unsafe 상태이다.
이때. P2 process가 R2 resource를 할당 받으면 다음그림과 같이 cycle이 형성되면서 deadlock에 걸린다.
따라서, P2 process는 resource를 할당 받을 수 없다.
P1 process가 R1 프로세스를 할당받는 것을 종료하면, cycle이 형성되지 않기 때문에 그때 P2 process는 R2 process를 사용할 수 있다.
이와 같이 미래를 예측하여 deadlock이 발생할 것인지 아닌지를 미리 확인한 후, 자원을 할당해주는 방법이 Resource-Allocation Graph Algorithm이다.
다음으로는 Banker's Algorithm에 대해서 알아보자.
Banker's Algorithm
Banker's Algorithm은 몇가지 가정을 전제로 한다.
각 process는 최대 몇개의 자원을 사용할 것인지 claim해줘야 하고, process가 자원을 요청한다면, 기다려야 하는 상황이 존재할 수도 있고, process가 모든 자원을 할당받았을 때 정해진 시간 안에 그 자원들을 release 해줘야 한다.
이는 두가지 sub-algorithm들을 갖고 있다.
Safety Algorithm과 Resource-Request Algorithm이다.
Banker's Algorithm을 사용하기 위해서는 몇가지 자료구조가 필요하다.
n : process의 수, m : 자원의 수 라고 했을 때,
Available : Vector of length m (자원의 길이를 나타내는 벡터 값)
- if Avaliable [j] = k, there are k instances of resource type Rj available.
MAX : n x m matrix (가로가 m이고, 세로가 n인 matrix , n개 process가 m개까지의 resource를 요청할 수 있다)
- if Max [i,j] = k, then process Pi may request at most k instances of resource type Rj.
Allocation : n x m matrix (가로가 m이고, 세로가 n인 matrix , 현재 할당 개수)
- if Allocation[i,j] = k then Pi is currently allocated k instances of Rj
Need : n x m matrix (가로가 m이고, 세로가 n인 matrix, 앞으로 필요할 수 있는 양)
- if Need[i,j] = k, then Pi may need k more instances of Rj to complete its task
Need [i,j] = Max [i.j] - Allocation [i.j] (최대 받을 수 있는 양 - 현재 할당 개수)
Safety Algorithm부터 알아보도록 하자.
Safety Algorithm
: 현재 system의 상태가 safe한지 아닌지를 판단하면서 찾아 나가는 알고리즘
1. Let Work and Finish be vectors of length m and n, respectively.
Initialize ..
Work = Available
Finish[i] = false (for i = 0,1.2. ... , n-1)
2. Find and i such that both:
(a) Finish [i] == false
(b) Need i <= Work
If no such i exists, go step 4
3. Work = Work + Allocation i
Finish [i] = true
go to step 2.
4. If Finish [i] == true for all i, then the system is in a safe state
예시를 들어 살펴보자.
1. (3 3 2) 현재 P1이 실행 가능하므로, P1을 실행하고 A resource가 release 되면서 Work 에서 A Resource를 2만큼 더해준다.
2. (5 3 2) 현재 P2는 Need가 (6 0 0)이므로 실행 불가
P3은 실행 가능하므로, P3을 실행하고 A,B,C Resource가 releeaase 되면서 Work에 ABC Resource들의 Allocation만큼 더해준 다.
3. (7 4 3) P4를 실행 가능하므로, C Resource가 release 되면서 Work에 C Resource를 Allocation 만큼 더해준다.
4. (7 5 5) P2를 실행 가능하므로 , AC Resource가 release 되면서 Work에 AC Resource를 Allocation 만큼 더해준다.
5. (7 4 5) P0를 실행 가능하므로, ABC Resource가 release 되면서 Work에 ABC Resource를 Allocation 만큼 더해준다.
어떠한 순서로 모두 종료되기 때문에 다음 예시는 safe 상태임을 알 수 있다.
이렇게 Safety Algorithm에 대해서 알아보았으니, 이제 Resource-Request Algorithm에 대해서도 알아보자.
Request = request vector for process Pi
Request i [j] = k : Pi wants k instances of resource type Rj
Resource-Requeust Algorithm
1. If Request i <= Need i go to step 2.
Otherwise, raise error condition, since process has exceeded its maximum claim.
2. If Request i <= Available, go to step3.
Otherwise P i must wait, since resources are not available.
3. Preten to allocate requested resources to P i by modifying the state as follows:
Available = Abailable - Requeust i ;
Allocation i = Allocation i + Request i ;
Need i = Need i - Request i ;
-> 바뀐 state이 safe할지 판단
if safe -> the resources are allocated to P i 할당받을 수 있음
if unsafe -> Pi must wait, and the old resource-allocation state is restored 기다려야함
Request 하는 Process에 대하여
Requeust <= Need 인지 확인
Requeust <= Available 인지 확인
이후 safety algorithm에 따라 확인했을 때 일정한 순서로 실행되면 -> safe state -> resources are allocated to process
그렇지 않으면 -> unsafe state -> process must wait
Deadlock Ignorance
: Ignore the problem and preten that deadlocks never occur in the system (Ostrich Algorithm)
- actually used by most operating systems, including Linux and Windows
- up to application developer to handle deadlocks
이렇게 Deadlock에 대한 모든 것을 알아보았다.
'Computer Structure > Operating System' 카테고리의 다른 글
| [운영체제/OS] Page Replacement Algorithms (0) | 2024.05.31 |
|---|---|
| [운영체제/OS] Virtual-Memory Management (0) | 2024.05.31 |
| [운영체제/OS] Memory (0) | 2024.05.31 |