Dead-Lock
Dead Lock
A프로세스는 자원1을 점유하고, B프로세스는 자원2를 점유 하고 있다고 가정해보겠습니다.
자원 → 하드웨어 소프트웨어 등을 포함하는 개념입니다.
프로세스가 자원을 사용하는 절차 → Request, Allocate, Use, Release
A프로세스는 B프로세스가 점유하고 있는 자원2를 원하고, B프로세스는 A프로세스가 점유하고 있는 자원1을 원할 때, 서로 상대방이 가진 자원을 무한정 기다리게 됩니다. 이 2개의 프로세스는 무한정 기다리게 되면서 실행을 한 번도 못하게 되는 상황이 발생하게 됩니다.
이런 상태를 교착 상태라고 합니다.
교착 상태는 아주 다양한 상황에 발생할 수 있습니다.
이전 포스터에서 배운 뮤텍스, 세마포어 에서도 발생할 수 있습니다.
이런 교착 상태를 해결하기 위해서는 교착 상태가 발생했을 때의 상황을 정확히 표현하고, 교착상태가 일어나는 근본적인 이유에 대해 알아야 합니다.
자원 할당 그래프
교착 상태는 자원할당 그래프를 통해서 단순하게 표현할 수 있습니다.
- 프로세스는 원으로, 자원의 종류는 사각형으로 표현이 됩니다.
- 사용할 수 있는 자원의 개수는 사각형안의 점으로 표현합니다.
- 프로세스가 어떤 자원을 할당 받아 사용중이라면 자원에서 프로세스를 향해 화살표로 표시합니다.
- 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시합니다.
교착 상태에 걸린 그래프는 다음과 같습니다.
교착 상태 발생 조건
교착상태가 발생할 수 있는 조건에 대해 알아보겠습니다.
교착 상태가 발생할 수 있는 조건은 총 4개가 있습니다.
4개의 조건을 다 만족해야 교착 상태가 발생할 가능성이 생깁니다.
이 말은 즉, 발생 조건을 하나라도 만족하지 않으면 교착 상태가 일어나지 않는다는 말 입니다.
상호 배제
한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없을때, 즉 상호 배제 상황에서 교착 상태가 발생할 수 있습니다.
점유와 대기
어떠한 자원을 할당 받은 상태에서 다른 자원을 할당받기를 기다린다면 교착 상태가 발생할 수 있습니다.
즉, 자원을 할당 받은 상태에서 다른 자원을 할당 받기를 기다리는 상태를 점유와 대기라고 합니다.
비선점
어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 상황이면 교착 상태가 발생할 수도 있습니다.
원형 대기
앞서 배운 자원할당 그래프가 원형 형태로 그려지면 교착 상태가 발생할 수 있습니다.
교착 상태 처리 방법
교착 상태를 해결하는 기법은 크게 3가지 방법인 예방, 회피, 검출 후 회복이 있습니다.
운영체제는 애초에 교착 상태가 일어나지 않도록 자원을 분배 하여 교착 상태를 예방할 수 있고, 조금씩 자원을 할당하다가 교착 상태의 위험이 감지되면 자원을 할당하지 않는 방식으로 회피할 수 있습니다. 또한 교착 상태가 검출되면 교착 상태를 회복하는 방법을 취할 수 있습니다.
교착상태 예방
자원 할당 시 교착상태의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 미리 예방하는 기법입니다.
자원의 상호 배제를 제거합니다.
예방하는 방법중 하나는 자원의 상호배제를 제거하는 방법입니다.
즉, 모든 자원이 공유가 가능하게 만드는 말과 같습니다. 하지만 이 방법은 현실적으로 한계가 있기에 사용하기에는 다소 무리가 있습니다.
점유와 대기를 없앱니다.
점유와 대기를 없애면 운영체제는 특정 프로세스에 자원을 모두 할당하거나 할당하지 않을 수 있습니다.
하지만 이런 방법에는 여러 단점이 존재합니다.
먼저, 당장 자원이 필요한 프로세스에게 자원 할당이 되지 않아 무한정 기다릴 수 있습니다. 이 때문에 자원의 활용률이 낮아집니다.
또한 자원을 많이 사용하는 프로세스느 자원을 적게 사용하는 프로세스에 비해 자원을 사용할 타이밍을 잡기가 어려워 무한정 대기할 가능성이 존재합니다.
이는 결국 많은 자원을 필요로 하는 프로세스가 무한정 대기하기 때문에 기아현상을 발생시킬 수 있습니다.
비선점 조건을 제거합니다.
비선점 조건을 제거하면 프로세스는 다른 프로세스의 자원을 빼앗을 수 있게 됩니다.
이처럼 비선점 조건을 제거하면 교착 상태가 발생하지 않기 때문에 선점하여 사용할 수 있는 일부 자원에 대해서는 효과적입니다.
하지만 모든 자원이 이렇게 선점이 가능한 것은 아닙니다.
그렇기에 비선점 조건을 없애 모든 자원을 빼앗을 수 있도록 하여 교착 상태를 예방하는 방법은 다소 범용성이 떨어지는 방안입니다.
원형 대기 조건을 제거합니다.
자원 할당 그래프가 원의 형태를 띄고 있는 모습을 하고 있으면 이는 교착 상태가 발생할 가능성이 존재합니다.
하지만 이런 원형 대기를 없애면 교착 상태는 발생 하지 않습니다.
이런 원형 대기를 없애는 방법은 간단합니다.
먼저 모든 자원에 번호를 붙이고 오름차순으로 자원을 할당하면 원형 대기는 발생하지 않습니다.
이런 방법은 현실적이지만, 단점이 존재합니다.
모든 컴퓨터 시스템 내에 존재하는 수많은 자원에 번호를 붙이는 일은 그리 간단하지 않습니다.
또한 각 자원에 어떤 번호를 붙이는지에 따라 자원의 활용률이 떨어질 수 있습니다.
교착 상태 회피
교착 상태 회피는 교착 상태가 발생하지 않을 정도로만 조금씩 자원을 할당하는 방식입니다.
즉, 프로세스들에 배분할 수 있는 자원의 양을 고려하여 교착 상태가 발생하지 않을 정도의 양만큼만 자원을 배분하는 방법입니다.
교착 상태를 회피하는 방법을 알기 전에 안전 상태, 불안전 상태, 안전 순서열 용어에 대한 뜻을 알고 넘어 가겠습니다.
안전 순서열
교착 상태 없이 프로세스들에 자원을 할당할 수 있는 순서를 의미합니다.
예를 들어서 프로그램 1,2,3 순으로 실행해야 교착상태가 발생 하지 않으면, 안전 순서열은 1,2,3이 됩니다.
안전 상태
안전 순서열이 있는 상태에서 순서열 대로 프로세스들에 자원을 배분하여 교착 상태가 발생하지 않는 상태를 뜻합니다.
불안전 상태
안전 순서열이 없는 상태이기 떄문에 교착 상태가 발생할 가능성이 존재합니다.
예시를 보면서 좀 더 자세하게 이해해 보겠습니다.
프로세스 P1,2,3가 실행중이고, 자원의 한정량은 12라고 가정하겠습니다.
| 프로세스 | 최대 요구량 [ 자원 ] | 현재 사용량 [ 자원 ] |
|---|---|---|
| P1 | 10 | 5 |
| P2 | 4 | 2 |
| P3 | 9 | 2 |
먼저 순서를 보면 P2,1,3 순서로, 이는 안전 순서열이 있기 때문에 안전 상태입니다.
현재 남은 자원량은 [ 12 - 5 - 2 - 2 = 3 ] 3입니다.
- P2은 2개를 사용중이지만, 최대 요구량이 4이기 때문에 남은 3에서 2를 P2에게 할당합니다. [ 남은 자원량 3- 2 = 1 ]
- P2는 정상적으로 작업을 마치고 자원 4개를 반환합니다. [ 남은 자원량 4 + 1 = 5 ]
- P1은 5개를 사용중이지만, 마찬가지로 최대 요구량이 10이기에 남은 자원량 5개를 전부 P1에 할당합니다. [ 남은 자원량 5 - 5 = 0 ]
- P1는 정상적으로 작업을 마치고 자원 10개를 반환합니다. [ 남은 자원량 0 + 10 = 10 ]
- P3도 마찬가지로 2개를 사용중이지만 최대 요구량이 9이기에 자원 7개를 P3에 할당합니다. [ 남은 자원량 10 - 7 = 3 ]
이처럼 안전 순서열 대로 자원을 배분하면 프로세스들이 자원을 모두 할당 받을 수 있기에 교착 상태는 일어나지 않습니다.
하지만 순서대로 자원을 부여하면 안전 순서열이 없기떄문에 불안전 상태가 됩니다.
이렇게 되면 교착 상태가 발생할 가능성이 존재합니다.
예시를 보겠습니다. 아까 처럼 똑같이 자원은 12개 입니다.
| 프로세스 | 최대 요구량 [ 자원 ] | 현재 사용량 [ 자원 ] |
|---|---|---|
| P1 | 10 | 5 |
| P2 | 4 | 2 |
| P3 | 9 | 3 |
P2작업이 정상적으로 종료되어도 결국 남은 자원은 4개 [ 12 - 5 - 4 - 3 + 4 = 4 ] 이기 때문에 P1을 실행할 수 없습니다. [ 요구량이 5개 ] 그러므로 P1과 P3는 서로 무한정으로 바라볼 수 밖에 없어서 교착 상태가 발생하게 됩니다.
이로 인해 운영체제는 항상 안전 상태에서 안전 상태로 움직이는 경우에만 자원을 할당하면 됩니다.
즉, 교착 상태 회피 방식은 항시 안전 상태를 유지하도록 자원을 할당하는 방식입니다.
교착 상태 검출 후 회복
마지막으로 교착 상태 검출 후 회복은, 말 그대로 교착 상태가 발생하면 검출 후, 회복하는 방식입니다.
이 방식에서 운영체제는 프로세스들이 자원을 요구할 때마다 그때 그떄 모두 할당하며, 교착 상태 발생 여부를 주기적으로 검사합니다.
만약에 교착 상태가 발생하면 선점을 통한 회복이나, 프로세스 강제 종료를 통한 회복으로 교착 상태를 해결합니다.
선점을 통한 회복
이 방법은 교착 상태가 해결될 떄까지 자원을 한 프로세스씩 몰아주는 방식입니다.
즉, 교착 상태가 해결 될 떄까지 다른 프로세스로 부터 자원을 빼앗아 한 프로세스에 할당하는 방식입니다.
프로세스 강제 종료를 통한 회복
이 방법은 가장 단순하면서 확실한 방법입니다.
교착 상태에 놓인 프로세스를 모두 종료하거나, 교착 상태가 없어질 때 까지 한 프로세스식 종료하는 방법입니다.
모두 종료를 하게 되면 작업 내용을 잃을 수 있꼬, 한 프로세스씩 종료하면 오버헤드가 커질 가능성이 존재합니다.
Deadlock Ignorance
Deadlock이 발생하여도 시스템은 책임지지 않습니다.