하루에 한 문제
교착상태(Dead Lock) 본문
교착상태는 상호 배제에 의해 나타나는 문제점으로, 둘 이상의 프로세스나 스레드들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상이다.
아래 그림과 같이 자동차(프로세스)들이 현재 위치한 길(자원)을 점유함과 동시에 다른 차가 사용하는 길을 사용하려고 대기하고 있지만 다른 자동차도 마찬가지이기 때문에 누구도 움직이지 못하는 현상이다.
교착상태 발생의 필요 충분 조건은 4가지가 있는데 이 4가지중 하나라도 충족되지 않으면 교착상태는 발생하지 않는다.
1. 상호배제 (Mutual Exclusion)
한번에 한개의 프로세스만이 공유 자원을 사용할 수 있어야 한다.
2. 점유와 대기 (Hold and Wait)
최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용되고 있는 자원을 추가로 점유하기 위해 대기
3. 비선점 (Non-Preemption)
다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 뺴앗을 수 없다.
4. 환형대기(Circular Wait)
공유자원과 공유자원을 사용하기 위해 대기하는 프로세스들이 원형으로 구성되어 있어 자신에게 할당된 자원을 점유하면서 앞이나 뒤에 있는 프로세스의 자원을 요구해야 합니다.
교착상태 해결방법
예방기법(Prevention)
교착상태 예방 기법은 교착상태가 발생하지 않도록 사전에 시스템을 제어하는 방법으로 교착상태 발생의 네 가지 조건 중에서 어느 하나를 부정함으로써 수행되지만 자원의 낭비가 매우매우매우매우 심하다. 이런 방식으로 교착상태를 예방하게 되면 장치의 이용률이 저하되고 시스템 이용률이 감소된다.
상호배제 부정
한번의 여러개의 프로세스가 공유 자원을 사용할 수 있도록 한다.
만약 프로세스가 읽기 전용을 열면 프로세스들은 그 파일에 대한 동시 접근을 보장받고 이 경우 상호배제가 깨지게 되 교착상태를 예방할 수 있다.
하지만 프린터와 같은 경우는 근본적으로 공유가 불가능하기 때문에 교착상태를 예방할 수 없다.
점유 및 대기 부정
프로세스가 실행되기 전 필요한 모든 자원을 할당하여 프로세스 대기를 없애거나 자원이 점유되지 않은 상태에서만 자원을 요구하도록 한다.
이 방법은 자원 이용률이 낮고 기아상태가 발생할 수 있다.
비선점 부정
비선점 이란 이미 할당된 자원이 선점되지 않아야 한다는 것이다 이를 위해서 자신이 점유하고 있는 자원을 강제로 방출시켜 다른 프로세스가 선점하게 함으로써 교착상태를 없애버리는 방법을 생각해 볼 수 있다.
만일 어떤 자원을 점유하고 있는 프로세스가 즉시 할당할 수 없는 다른 자원을 요청하면 현재 그 프로세스가 점유하고 있는 모든 자원이 방출되어 필요로 하는 다른 프로세스에게 선점된다
또 해당 프로세스는 자신이 요청하고 있는 새로운 자원은 물론 현재 강제로 방출한 옛 자원들을 다시 획득할 수 있을 때에만 다시 시작된다.
하지만 자신이 가지고 있던 상태를 읽어버리고 다시 처음부터 진행해야 한다는 단점이 있다.
환형대기 부정
자원을 선형 순서로 분류하여 고유 번호를 할당하고, 각 프로세스는 현재 점유한 자원의 고유 번호보다 앞이나 뒤 어느 한쪽 방향으로만 자원을 요구하도록 하는 것
응용프로그램 작성의 어려움이 따르고, 자원에 대한 접근을 불필요하게 거부하기 때문에 비효율적이다.
회피기법 (Avoidance) - 은행원 알고리즘
교착상태 회피는 데드락이 빠질 가능성이 있는지 없는지 운영체제가 검사하고 빠질 가능성이 없을 경우에만 자원을 할당함으로써 문제 발생을 피하는 방법아다.
교착상태에 빠질 가능성이 있는지, 없는지를 판단하기 위해 상태를 ‘안전 상태’와 ‘불안전 상태’로 나눈다.
그리고 운영체제는 안전상태를 유지할 수 있는 요구만 수락해주고, 나머지 요구들은 안전상태를 만족할 때까지 계속 거절한다.
현재 은행에 남은 25원을 3에게 다 빌려주게 된다면 ??
아무도 해결되지 않아 교착상태에 빠지게 될 것이다..! 즉 불안정 상태라는 뜻이다.
고객 1 - 고객 2 - 고객3
고객 2 - 고객 1- 고객 3
고객 2 - 고객 3 - 고객 1
이런 순서로 돈을 빌려준다면 모든 고객에게 돈을 빌려줄 수 있고 이를 '안전 순서열이 존재'한다고 한다.
발견기법(Detection)
교착상태 발견 기법은 시스템에 교착상태가 발생했는지 점검해 교착상태에 있는 프로세스와 자원을 발견하는 것이다.
교착상태 발견 알고리즘과 자원 할당 그래프 등을 사용할 수 있다.
회복기법(Recovery)
탐지 알고리즘에 의해 시스템에 교착 상태가 발생이 되면 이를 회복하는 여러가지 방법이 있지만 크게 두가지로 나뉜다.
첫번째는 한 개 이상의 프로세스를 중지시키는 것이고, 둘째는 하나 이상의 프로세스들로부터 자원을 선점하는 것이다.
프로세스 종료
교착 상태를 해결하기 위해 존재하는 프로세스 하나를 임의로 종료하여 교착 상태를 해결하는 방법
프로세스를 종료하는데 있어 2가지 방법이 있다.
첫번째는, 교착 상태 프로세스를 모두 중지한다. 이 방법은 상당히 큰 비용이 들어간다. 모두 중지를 하면 그 프로세스들이 모두 새로 시작을 해야 되기 때문이다.
둘째는, 교착 상태가 제거될 때 까지 한 프로세스씩 중지하는 방법이다. 이 방법은 각 프로세스가 중지될 때마다 교착상태가 풀렸는지 확인해봐야 하기 때문에 상당한 오버헤드를 유발한다.
자원 선점
자원 선점을 통해 교착상태를 제거하기 위해서는 교착 상태가 꺠어질 때까지 프로세스로부터 자원을 계속적으로 선점해 다른 프로세스에게 주어야 한다.
자원 선점을 하기 위해서는 아래의 내용을 고려해야 한다.
1. 희생자 선택(selection of a victim)
자원 선점에 앞서 어떤 자원과 어느 프로세스가 선점될것인가 고려해야 한다. 이 때 비용을 최소로 하기 위해 교착 상태 프로세스가 점유하고 있는 자원의 수, 그리고 교착상태 프로세스가 지금까지 실행하는데 소요한 시간등을 판단해서 희생자를 선택해야 한다.
2. 롤백(rollback)
만약 특정 프로세스의 자원을 강제로 방출시키고 선점시켰다면, 그 프로세스를 어떻게 처리 할 것인가에 대한 고민이 필요하다. 가장 안전한 방법은 프로세스를 중지시키고 재식작하는 것, 즉, 롤백하는 것이다.
3.기아 상태(startvation)
자원 선점을 통해 기아상태가 발생할 수 도 있다는 점을 고려해봐야 한다. 계속해서 특정 프로세스의 자원을 강제로 방출시킨다면 그 프로세스는 다음에도 희생자로 선택될 확률이 높고 이 경우 기아상태에 빠질 수 있다. 즉 프로세스가 한정된 시간에만 희생자로 선정된다는 것을 반드시 보장해야 한다.
무시기법(Ignore)
교착상태를 해결할때도 문맥교환에 의한 오버헤드가 발생한다.
교착상태에 의한 성능저하보다 이를 해결할 때의 성능저하가 더 큰 경우 그냥 무시한다.
타조 알고리즘 ( 머리를 땅에 파묻고 모른척한다..)
참고
https://coding-factory.tistory.com/311
https://heavenly-appear.tistory.com/332
https://velog.io/@seorim0801/%EC%9D%80%ED%96%89%EC%9B%90-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98