[운영체제]데드락(교착상태)

강의: 비전공자를 위한 운영체제

 

 

교착상태란?

교착상태가 발생하는 이유는 공유자원 때문임.

만약, 어떤 자원을 여러 프로세스가 공유하지 않으면 교착상태는 발생하지 않음. 

ex) 교착상태를 설명하는 가장 유명한 철학자 예시

음식을 먹기 위해선 포크 두개를 사용해야 함.

근데 동시에 자기 오른쪽에 있는 포크를 집어버림. 근데 아무도 양보하지 않으면 더이상 식사가 불가능한 교착상태에 빠지게 된다.

교착상태의 필요조건

아래 조건을 모두 충족해야 교착상태가 발생함.

 

1) 상호배제

어떤 프로세스가 한 리소스를 점유했다면, 그 리소스는 다른 프로세스에 공유되지 않는다. 위 철학자 예시에서 포크를 한명이 집으면 그 포크는 동시에 다른 사람이 못 쓰지.

 

2) 비선점

프로세스 a가 리소스를 점유하고 있다면 프로세스 b가 리소스를 빼앗을 수 없다. 위 철학자 예시에서 다른 철학자가 들고 있는 포크를 뺏을 수 없는 것임.

 

3) 점유와 대기

어떤 프로세스가 리소스 a를 가지고 있으면서 리소스 b를 원해야 함. 위 철학자예시에서 오른쪽 손에 포크가 있으면서 왼손으로는 다른포크를 또 원함

 

4) 원형대기

점유와 대기를 하는 프로세스들의 관계가 원형을 이루고 있다는 것. 위 철학자 예시에서 서로가 서로의 포크를 원하는 상황임.

 

 

---

데드락(교착상태) 해결

 

교착상태 회피(예방)

전체 자원의 수와 할당된 자원의 수를 기준으로 안정상태와 불안정상태를 나눔.

ex) 교착상태 회피를 표현한 알고리즘 : 은행원 알고리즘

은행은 처음에 1000달러가 있음. a한테 500, b한테 400을 빌려줌. 이제 a한테 갚으라고 했는데 a가 200달러만 더 빌려주면 그걸로 더 벌어서 갚는다함. 그래서 은행이 b한테 가서 돈달라한담에 빌려주려 했더니 b도 마찬가지로 200만 더 빌려주면 갚는대. 아뉘 이러면 은행은 아무것도 못하는 교착상태에 빠짐.

위 상황을 해결하기 위해 은행의 여윳돈과 사업가들에게 빌려준 돈들을 보고 대출가능한 상황인지 확인하고 빌려줌. 이를 은행원 알고리즘이라고 한다.

-> 운영체제에서 은행원알고리즘 구현하는 방법을 보자

안정상태

1. 운영체제는 프로세스에게 자원을 할당하기 전에 자기가 가지고 있는 전체 자원의 수를 알고 있어야 한다.(총자원)

2. 프로세스들은 각자 자기가 필요한 자원의 최대숫자를 운영체제한테 알려줘야 함(최대요구자원)

위 상태에서 만약 p1이 4개를 요청하면 현재사용가능한 자원은 2개니까 p1의 요청을 거부하고 p2에 응답함. 그럼 p2는 할당된 자원가지고 작업 마친 후 6개를 반납함. 그럼 사용가능한 자원이 6개로 늘어났기 때문에 p1과 p3에 모두 할당가능해짐.

 

불안정상태

지금 아래에선 사용가능한 자원이 1개라서 p1,p2,p3모두에게 자원할당 못함. 이걸 불안정상태라 함.

 

 

은행원알고리즘은 불안정상태를 예방할 수 있지만 비용이 비싸고 비효율적임. 그래서 교착상태 발생자체는 혀용하지만 발생한 담에 이를 해결하는 방식을 연구함.

교착상태 해결

문제 해결할라면 지금 교착상태 상황에 있는지 알아내야 함. 두가지 방식이 있음.

가벼운 교착상태 검출

타이머 이용함. 프로세스가 일정시간동안 작업을 진행하지 않는다면 교착상태에 있다고 간주하고 교착상태를 해결함. 

해결방법은 간단함. 일정시점마다 체크포인트를 저장하고, 교착상태에 빠진것을 확인하면 제일 마지막으로 저장했던 체크포인트로 롤백하는 것임.

 

무거운 교착상태 검출

자원할당 그래프 이용. 현재 운영체제에서 프로세스가 어떤 자원 사용하는지 지켜보는 것임.

아래 그림에서 각각 프로세스들은 화살표방향에다가 다른 프로세스에 자원을 요청하고 있음.

왼쪽 그래프는 순환구조가 없으니가 교착상태가 없고, 오른쪽은 순환구조가 있으니까 교착상태가 있음. 이렇게 교착상태 검출하면 교착상태일으킨 프로세스를 강제종료 시키고 다시 실행할 땐 체크포인트로 롤백시킴.

이 방식은 운영체제가 계속 지켜봐야 하니까 오버헤드 일어남. 단, 가벼운 교착상태 검출방식에서 발생할 수 있는 억울하게 종료되는 프로세스는 발생하지 않음.