교착상태란?
2개이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며, 작업을 더이상 진행하지 못하는 상태
교통 체증이 심해서 서로 비켜주기를 기다리며 꼼짝못하는 상태와 같다.
교착상태 발생
- 시스템 자원
교착 상태는 다른 프로세스와 공유할 수 없는 자원을 사용할 때 발생한다. - 공유 변수
- 응용 프로그램
프로세스1과 2가 자원1, 2를 모두 얻어야 한다고 가정해보자
t1 : 프로세스1이 자원1을 얻음 / 프로세스2가 자원2를 얻음
t2 : 프로세스1은 자원2를 기다림 / 프로세스2는 자원1을 기다림
현재 서로 원하는 자원이 상대방에 할당되어 있어서 두 프로세스는 무한정 wait 상태에 빠짐
→ 이것이 바로 DeadLock이다.
- 멀티 프로그래밍 환경에서 한정된 자원을 얻기 위해 서로 경쟁하는 상황 발생
- 한 프로세스가 자원을 요청했을 때, 동시에 그 자원을 사용할 수 없는 상황이 발생할 수 있음. 이때 프로세스는 대기 상태로 들어간다.
- 대기 상태로 들어간 프로세스들이 실행 상태로 변경될 수 없을 때 '교착 상태' 발생
교착상태 발생 필요조건
4가지 모두 성립해야 데드락 발생
(하나라도 성립하지 않으면 데드락 문제 해결 가능)
상호배제(Mutual Exclusion)
한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이여야한다.
-> 자원은 한번에 한 프로세스만, 동시에 사용 불가능
비선점(Non - Preemption)
한 프로세스가 사용중인 자원은 중간에 다른 프로세스가 빼앗을 수 없다.
점유와 대기(Hold and Wait)
프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야한다.
원형 대기(Circular Wait)
점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 한다.
식사하는 철학자 문제의 자원 할당 그래프
-
철학자들은 서로 포크를 공유할 수 없다.
-> 자원을 공유하지 못하면 교착 상태가 발생한다.(상호 배제) -
각 철학자는 다른 철학자의 포크를 빼앗을 수 없다.
->자원을 빼앗을 수 없으면 자원을 놓을 때까지 기다려야 하므로 교착 상태가 발생한다.(비선점) -
각 철학자는 왼쪽 포크를 잡은 채 오른쪽 포크를 기다린다.
-> 자원하나를 잡은 상태에서 다른 자원을 기다리면 교차상태가 발생한다.(점유와 대기) -
자원 할당 그래프가 원형이다.
-> 자원을 요구하는 방향이 원을이루면 양보를 하지 않기 때문에 교착상태가 발생한다.(원형 대기)
교착상태 해결방법 - 예방
교착상태 예방은 교착상태를 유발하는 네가지 조건중 하나라도 발생하지 않도록 막아 교착 상태를 처리하는 방법
-
상호 배제 예방
시스템 내의 모든 자원을 공유하기 -> 사실상 불가능 -
비선점 예방
모든 자원을 빼앗을 수 있도록 만드는 방법 -> 임계구역을 보호하기위해 잠금을 사용하기에 빼앗을 수가 없음
빼앗을 수 있어도, 높은 우선순위가 다 가져가기 때문에 낮은 프로세스는 자원배정을 못받는다. -
점유와 대기 예방
전부 할당하거나, 아니면 아예 할당하지않는다.- 프로세스가 지신이 사용하는 모든 자원을 자세히 알기 어렵다.
- 자원의 활용성이 떨어진다.
- 많은 자원을 프로세스가 적은 자원을 사용하는 프로세스보다 불리하다.
- 결국 일괄 작업 방식으로 동작한다.
-
원형 대기 예방
모든 자원에 숫자를 부여하고 숫자가 큰 방향으로만 자원을 할당한다.- 프로세스 작업 진행에 유연성이 떨어진다.
- 자원의 번호를 어떻게 부여할 것인지가 문제
-> 결론적으로 실현 불가능하거나, 프로세스 작업방식을 제한하고 자원을 낭비하기에 사용할 수 없다.
교착상태 해결방법 - 회피
교착 상태 회피는 프로세스에 자원을 할당할 때 어느 수준이상의 자원을 나누어주면 교착상태가 발생하는지 파악하여 그 수준 이하로 자원을 나누어주는 방법
은행원 알고리즘
-
은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래함
-
프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사하여 교착 상태 회피
-
안정 상태면 자원 할당, 아니면 다른 프로세스들이 자원 해지까지 대기
-
각 프로세스의 기대 자원과 비교하면서 자원이 하나라도 크거나 같으면 자원을 할당
-
가용 자원이 기대 자원 보다 크다는 것은 그 자원을 사용하여 작업을 끝낼 수 있는 프로세스가 있다는 의미 -> 안정상태
-
가용 자원이 어떤 기대 자원 보다 크지 않으면 할당하지 않는다. 가용 자원을 사용하여 작업을 마칠 수 있는 프로세스가 없다는의미 -> 불안정 상태
변수 설명 전체 자원 시스템 내 전체 자원의 수 가용 자원 시스템내 현재 사용할 수 있는 자원의 수 기대 자원 각 프로세스가 앞으로 사용할 자원의 수 할당 자원 프로세스에 현재 할당된 자원의 수 최대 자원 프로세스가 선언한 최대 자원의 수 -
단점
-
프로세스가 자신이 사용할 모든 자원을 미리 선언해야한다.
-> 미리 선언한 자원의 수가 정확하지않으면 교착상태 발생 -
시스템의 전체 자원 수가 고정적이여야함
-> 새로운 차원의 추가나 고장나는 일있으면 안됨 -
자원이 낭비
교착상태 해결방법 - 검출
검출은 운영체제가 프로세스이 작업을 관찰하면서 교착상태여부를 계속 주시하는 방식이다.
-
타임 아웃
일정 시간 동안 작업이 진행되지 않은 프로세스를 교착상태가 발생한 것으로 간주- 엉뚱한 프로세스가 강제 종료될 수 있다.
- 모든 시스템에 적용하기 힘들다.
-> 이런 이유들로 '가벼운 교착 상태 검출'이라고 불리운다.
-
자원 할당 그래프를 이용한 교착 상태 검출
- 자원할당 그래프를 이용
- 자원 요청 시, 탐지 알고리즘을 실행시켜 그에 대한 오버헤드 발생함
- 자원을 요청하거나 할당할 때마다 자원 할당 그래프를 갱신 -> 이때 사이클이 발생하면 교착상태가 검출된 것으로 판단
교착상태 해결방법 - 회복
-
교착 상태를 일으킨 모든 프로세스를 동시에 종료
-> 다시 실행할때 다시 교착상태 일으킬 수 있음
-> 어떤 순서로 실행시킬지 정해야함 -
교착상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료
교착상태를 일으킨 프로세스 하나를 골라 순서대로 종료하면서 나머지 프로세스를 상태를 파악- 우선순위가 낮은 프로세스를 먼저 종료
- 우선순위가 같으면 작업시간이 짧은 프로세스를 먼저 종료
- 위의 두조건이 같은 경우 많이 사용하는 프로세스를 먼저 종료
참고
https://gyoogle.dev/blog/computer-science/operating-system/DeadLock.html
