교착상태
일어나지 않을 사건을 기다리며 무한히 기다리는 현상
게임 프로세스와웹 브라우저 프로세스가동시에 실행 중에 있다고 가정하자두 프로세스는
공유 자원 A와 B를 모두 필요로한다.
게임 프로세스의 자원 필요 순서는A->B,
웹 브라우저 프로세서의 자원 필요 순서는B->A이다.
게임 프로세스는공유자원 A를 Lock 하고
웹 브라우저 프로세스는공유자원 B를 Lock 한다.이후 두 프로세서는 다른 프로세스가 점유하고 있는 공유자원을 필요로 하게되고
Lock 이 풀릴때 까지 대기한다.
서로가 점유하고 있는 공유자원을 필요로 하기 때문에 무한히 기다리게된다.
이러한 현상을
교착상태혹은데드락이라고 한다.
교착 상태 발생 조건
아래 상태가
모두 만족할때 교착 상태가 발생한다.
상호 배제
두 개 이상의 프로세스가
동시에공유 자원을 사용할 수 없는 상태`
점유와 대기
공유 자원을 할당받은 상태에서 다른 공유자원을 할당 받기를 기다리는 상태
비선점
어떤 프로세스도 공유 자원의 소유권을 빼앗을 수 없는 상태
원형 대기
프로세스들이 원의 형태로 자원을 대기하는 상태
교착 상태를 해결하는 방법
교착 상태를 해결하는 방법에는
예방,회피,검출 후 회복,무시가 있다.
예방
교착 상태의 발생 필요 조건 4가지중 하나를 충족하지 못하게 하는 방법
상호 배제
상호 배제를 없앤다는 말은공유 자원에 동시에 접근이 가능하게 만든다라는 말과 같다.현실적으로 불가능하다.
점유와 대기
프로세스가 필요한 공유 자원들의 소유권을 필요할 때마다 받는 것이 아니라
한번에 모두 받게한다.이 방식은 당장 자원이 필요해도 기다릴 수 밖에 없는 프로세스가 생기고
사용되지 않으면서 오랫동안 할당되는 자원이 생겨서 자원의 활용률이 낮다.
비선점
자원을 선점가능하게 한다.하지만 모든 자원이 선점 가능한것은 아니다.
프린터 같은 경우 한번의 하나의 프로세스만 이용이 가능하다.
그렇기 때문에 범용성이 떨어지는 방안이다.
원형대기
모든 자원에 번호를 붙이고 오름차순으로 자원을 할당하면 원형대기는 발생하지 않는다.
5개의 자원이 있다고 가정할때 5번 자원을 쓴 후 1번 자원을 쓸 수 없다.하지만 모든 자원에 번호를 붙이는 것은 간단한 작업이 아니며
각 자원에 어떤 번호를 붙이느냐에 따라 특정 자원의 활용률이 떨어진다.
결론적으로
예방하는 방식은 불가능하거나 여러 부작용이 있다.
회피
프로세스들에 배분할 수 있는 자원의 양을 고려하여
교착 상태가 발생하지 않을 정도의 양만큼만 자원을 배분하는 방법즉 교착 상태를 회피하기 위해서
은행원 알고리즘
각 자원 유형마다 다수의 인스턴스를 갖는 경우 사용할 수 있는 알고리즘
시스템 상태가 안전 상태에서 안전 상태로 움직이는 경우에만 자원을 할당한다.
- 프로세스 시작 시 자신이 필요한 각 자원의 최대(Max) 개수를 미리 선언
- 각 프로세스에서 자원요청이 있을때 요청을 승인하면
시스템이 안전한 상태(safe state)로 유지되는 경우에만 자원을 할당- 불안정 상태(unsafe state)가 예상되면 다른 프로세스가 끝날 때까지 대기
안전 순서열
교착 상태가 발생하지 않게 프로세스들에게 자원을 할당할 수 있는 순서
안전 상태
안전 순서열이 있는 상태
불안전 상태
안전 순서열이 없는 상태, 교착 상태가 발생할 수 있는 위험이 있다.
이 상황에서 어떠한 프로세스에 자원을 몰아준다고 하더라도 프로세스를 완료시킬 수 없다.
자원 할당 그래프 알고리즘
자원 유형마다 인스턴스가 하나 있는 경우 사용할 수 있는 알고리즘
- 자원 할당 그래프에 예약 간선(향후 요청할 수 있는 자원을 점선으로 표시한 간선)을 추가한다.
- 프로세스 시작전에 모든 간선들을 자원할당 그래프에 표시한다.
- 프로세스는 예약 간선으로 설정한 자원에 대해서만 요청할 수 있고 주기가 형성되지 않을 때만 자원을 할당 받는다.
검출 후 회복
교착 상태 발생을 인정하고 사후에 조치하는 방식
선점을 통한 회복
교착 상태가 해결될때 까지 한 프로세스씩 자원을 몰아주는 방식
교착 상태가 해결될때 까지 다른 프로세스로부터 자원을 강제로 빼앗고 한 프로세스에게 할당하는 방식이다.자원 선점에 있어서 다음 사항들을 고려해야한다.
- 최소의 피해를 줄 수 있는 프로세스를 선택한다.
- 선점된 프로세스를 문제 없던 이전 상태로 롤백해야한다.
- 한 프로세스가 계속 선점되어 Starvation 상태를 방지해야한다.
- 이는 우선 순위를 사용해서 선점될 때마다 우선 순위를 높이는 것으로 방지할 수 있다.
프로세스 강제 종료를 통한 회복
가장 단순하면서 확실한 방법교착 상태에 놓인 프로세스를 모두 강제 종료할 수 있고
교착 상태가 없어질때 한 프로세스씩 강제 종료할 수도 있다.하지만 작업 내역을 잃게되리 가능성이 있고
후자는 작업 내역을 잃는 프로세스를 줄일 수 있지만
교착 상태가 없어졌는지 여부를 확인하는 과정에서 오버헤드가 발생한다.
무시
- 교착 상태가 자주 발생하지 않는 경우
- 교착 상태를 복구하는 비용이 그냥 무시하는 것보다 많이 드는 경우
- 교착 상태를 예방하거나 피하기 위한 알고리즘이 복잡하거나 비용이 많이 드는 경우
대신 교착 상태를 복구하기 위한 대비책이 없다.
따라서 이 방법을 사용할때는 시스템이 교착 상태에 바져도 큰 문제가 되지 않는지
평가해야한다.
참고
https://www.youtube.com/watch?v=zQDNXklvdUw
https://yoongrammer.tistory.com/67
