1. Deadlock
- 1번부터 4번까지의 자동차를 프로세스라고 생각하고 각자 교차로를 빠져나가기 위해 a,b,c,d라는 자원을 획득해야하는 상황을 가정해보자.
- 2번은 3번이 비켜주길 원하고 3번은 4번이 비켜주길 원하면서 네 차량 모두 block된 상태를 Deadlock이라고 한다.
- 즉 서로 다른 프로세스가 서로 작업이 끝나길 기다리면서 나아가지 못 하는 상태를 의미한다.
- 이번에는 프로세스가 메모리를 요청하는 과정에서 Deadlock이 발생하는 경우를 살펴보자
- 총 할당 가능한 메모리 공간은 200KB이다
- 이때 p1, p2가 각각 80KB, 70KB의 메모리를 할당받은 상태에서 각각 또 60KB, 80KB의 메모리를 요청한다고 하면 어느 누구도 메모리를 할당 받지 못하고 서로 메모리 공간을 놓아주기만 기다리게 될 것이다.
- 두 프로세스가 Deadlock에 빠질 수 있는 경우를 그래프로 시각화 해보면 위와 같다.
- 만약 프로세스의 진행이 3, 4번인 경우에는 두 프로세스간의 Deadlock을 피할 수 없게된다.
- Deadlock상태에서는 프로세스들이 자원을 먹지 못하고 계속 굶게 되는데 이런 상태를 starvation이라고 한다.
2. Conditions for Deadlock
- 데드락 상황이 발생하는 이유는 뭘까?
1. 프로세스가 자원을 할당 받으면 자원에 대한 mutual exclusion을 보장해 주기로 했었다.
2. 한 프로세스가 자원을 할당 받으면 나머지는 순서대로 자원을 기다려야 한다.
3. 한번 자원을 할당 받고 나서는 pre-emption이 막혀있기 때문에 스스로 자원을 내려놓기 전까지는 누구도 자원을 뺏어가지 못한다.
4. 이런 조건을 보장하고 있기 때문에 프로세스, 자원간의 할당 관계가 원형 그래프를 만들게 되면 deadlock이 발생하는 것이다.
- 운영체제는 프로세스들의 관리를 담당하는 프로그램이다. 따라서 이렇게 Deadlock 상태에 빠진 프로세스들이 처리될 수 있도록 해주어야 한다.
3. Dealing with Deadlock - Prevention
- Deadlock을 막는 방법중 예방하는 법을 알아보자.
- 위에서 살펴본 데드락 발생 원인을 (mutual exclusion(1), hold&wait(2), non-preemption(3), circular wait(4))을 제거하는 것이다.
- mutual exclusion 제거 : mutual exclusion은 반드시 보장되어야 하는 조건이기에 prevention에서 제거할 수 없다.
- hold&wait 제거 : 프로세스가 수행되기 위해서 필요한 자원이 다 확보 가능하면 일을 하는 것이다. 하지만 프로그램이 얼마나 자원을 사용할지는 예측이 매우 어렵기 때문에 사실상 쉬운 방법은 아니다.
- no-preemption 제거 : a라는 자원을 할당받아서 쓰고 있는데 이어서 b자원을 필요로하는 상태다. 만약 b를 현재 할당 받을 수 없다면 가지고 있던 a를 놓아준다.
- circular wait 제거 : 만약 프로세스와 자원들이 원형 대기하는 상황이 생기면 강제로 프로세스간의 우선순위를 부여해 한 프로세스가 먼저 처리되도록 한다. 그러면 circular wait이 사라지게 된다.
4. Dealing with Deadlock - Avoidance
- 프로세스들이 수행될 때, 동적으로 상황을 봐가면서 deadlock이 생길 가능성이 보인다 싶으면 이를 피해가는 것이다.
- 프로세스들이 수행되는 중에 데드락이 발생할 것 같으면 자원의 할당을 거부하거나 아예 프로세스를 시작하지 않는 등의 조치를 취한다.
- 장점으로는 prevention보다는 덜 제약적이고 preempt(자원 소유를 뺏음)할 필요가 없다.
- 단점으로는 프로세스들이 미래에 어떤 자원을 요청하게 될지를 미리 알고 있어야 하기 때문에 쉽지 않은 방법이다.
- 대표적인 방법으로 banker's algorithm을 살펴보자.
- C는 각 프로세스가 r1~r3의 자원을 몇개 필요로 하는지 나타낸다.
- A는 각 프로세스에게 현재 r1~r3의 자원을 몇개 할당되어 있는지를 나타낸다.
- C-A는 앞으로 프로세스가 몇개의 자원을 요청할 것인지 나타낸다.
- R은 제공할 수 있는 자원들의 수이고 V는 A표만큼 자원을 할당해주고 남아있는 자원을 나타낸다.
- 이 상태에서 P2가 먼저 R3 1개를 할당받아서 일을 처리한 다음 자신이 갖고 있던 자원을 놓아주게 되면 모든 프로세스들이 문제없이 일을 처리할 수 있게 된다.
- 하지만 P1 혹은 P3가 V의 자원을 먼저 요청하게 되면 네 프로세스는 Deadlock에 걸리는 것이다.
- 이런 식으로 safe한 상태를 계속 유지할 수 있도록 프로세스에게 자원을 순차적으로 할당한 것이 banker's algorithm을 활용한 avoidance방식이다.
5. Dealing with Deadlock - Detection
- 프로세스들에게 자원을 할당하되 매순간 Deadlock이 발생했는지 아닌지를 검사하는 것이다.
- 만약 Deadlock이 발생했다면 recovery strategy로 들어가서 문제를 해결한다.
- recovery의 대표적인 방법중 하나는 데드락에 빠진 프로세스들의 자원을 모두 회수하는 것이다.
- 다른 방법으로는 각 프로세스마다 check point를 두어 deadlock이 걸렸을 때 rollback할 수 있도록 하는 것이다.
6. Dining Philosophers Problem
- 세마포어 혹은 모니터를 활용해서 deadlock을 피하는 구현을 살펴보자.
- 식사하는 철학자 문제라고 하며 먼저 문제 상황을 살펴보자.
- 철학자는 왼쪽, 오른쪽 포크를 집어야만 식사를 할 수 있다. 어느 철학자도 식사를 하지 못해서 굶어서는 안된다.
- 모든 철학자가 왼쪽 포크를 집은 상황이라면 어느 누구도 식사를 할 수 없다.
- 5명이 동시에 식사를 하려는 상황에서 deadlock이 발생할 수 있으니 room이라는 공간을 마련해서 4명만 들어갈 수 있도록 한다.
- 4명이 먼저 식사를 시작 하고 식사를 완료한 철학자가 room을 비워주면 다른 철학자가 room으로 들어올 수 있다.
1. wait(room) : room에 들어갈 수 있는지 대기
2. wait(fork[i]) : 왼쪽 포크를 집을 수 있는지 대기
3. wait(fork[(i+1) mod 5]) : 오른쪽 포크를 집일 수 있는지 대기
4. eat(); 왼쪽, 오른족 포크를 집었으므로 식사
5. signal(fork[(i+1) mod 5]) : 오른쪽 포크를 내려놓고 이 포크를 기다리던 철학자에게 신호를 보내 깨워준다.
6. signal(fork[i]) : 왼쪽 포크를 내려놓고 이 포크를 기다리던 철학자에게 신호를 보내 깨워준다.
7. signal(room) : 식사를 마쳤으므로 다른 철학자를 위해 room을 비워준다.
- 이번에는 monitor를 활용해서 식사하는 철학자 문제를 해결해 보자.
- 저번 강좌에서 모니터에는 한 프로세스만 존재함을 보장해준다고 했다.
- get_forks(k)를 하나의 모니터라고 생각하자.
- 그럼 get_fork(k)를 먼저 호출한 철학자가 오른쪽, 왼쪽 포크를 집게 되고 식사 후에 release_forks를 호출한다.
- 즉 모니터를 활용함으로써 철학자가 "왼쪽 오른쪽 둘다 집었다" 또는 "왼쪽만 집었다" 상태로 결정되도록 한다.
- 그럼 식사를 마친 철학자가 오른쪽, 왼쪽 포크를 놓아주면 block되어 있던 철학자가 식사를 할 수 있다.
'ComputerScience > Operating System' 카테고리의 다른 글
| OS - 8.1 Virtual Memory (0) | 2021.07.29 |
|---|---|
| OS 7 - Memory Management (0) | 2021.07.20 |
| OS - 5.2 Concurrency: Mutual Exclusion and Synchronization (0) | 2021.07.14 |
| OS - 5.1 Concurrency: Mutual Exclusion and Synchronization (0) | 2021.07.13 |
| OS - 4 Threads (0) | 2021.07.07 |
