17강 Deadlocks 2

https://core.ewha.ac.kr/publicview/C0101020140415131030840772?vmode=f 

반효경 [운영체제] 17. Deadlocks 2

 

지난 시간에 봤던 부분부터 다시 시작한다. 

 

 

이제 살펴볼 두가지방법은 데드락을 일단은 나오든 말든 방치하는것이다

-> 데드락은 자주나오는 이벤트가 아니기 때문에 미연에 방지하기위해 비효율적인 방법을 쓰는것이 더 안좋다

 

Deadlock Detention and recovery

일단 데드락이 일어나든 말든 냅뒀다가 데드락이 발생한것 같은경우 이제 데드락을 찾아내서 고쳐주는 방식이다.

 

detection 의 경우

자원이 1개씩 있는경우 그래프를 이용해서 detection을 한다.

a 그래프에서 자원을 생략해서 b 그래프처럼 간소화 시켜서 그려줄수도 있다.

 

자원할당 그래프에서 사이클이 있는경우 deadlock 가 있는 것이다.

 

그래서 wait for graph(자원생략 그래프) 를 보면 사이클이 2개 있다 100%데드락인 것이다.

 

자원할당 그래프에서 데드락을 찾는 오버헤드는 얼마나 될까?

-> O(n^2) 의 시간복잡도이다 겁나 오버헤드가 크다는것이다.

bfs든 dfs든 완전탐색을 해야하니까 이런 시간복잡도가 나온다 .

으으 이런거 싫어 

 

 

자원이 여러개인경우

표를 그려서 찾아내는 방법을 사용한다

보면 프로세스가 5개 있고

자원은 A -> 7개, B -> 2개 C ->6개 가있는 상황이다.

 

그리고 현상황을 나타내는 표를 나타내는것이다.

 

이걸 확인해보면

 현상황에서 요청이 없다는 상황을 가정하고 아예 요청이 없는 프로세스는 자원을 반납한다고 생각하고

반납했을때 돌아갈수있는 상황이라면 데드락이아니다.

 

일단 이거보면 가용자원이 p0,p2의 3,1,3 이렇게 있다고 생각하고 또 다른거에 배분해줘서 또 반납하고 이런식으로 풀리는지 확인해 보는것이다.

 

아까랑 같은 상황인데 p2가 자원요청이있는 경우이다.

그럼 이제 데드락이 걸린다.

 

이런방법으로 데드락이 발견되면 recovery 를 해야하는데

 

recovery방법에는 두가지가 있는데

 

1. 죽여서 해결시키자

    - 데드락과 연루된 모든 프로세스를 다 사살해버린다.

    - 데드락과 연루된 프로세스를 하나씩 죽여보는것이다.

어쩃든 다 죽여서 해결한다.

 

2.데드락과 관련된 프로세스에서 자원을 뻇는다/.

희생양을 하나 찾아서 자원을 다뻇는다.

자원을 뻇으면 문제가 똑같은 패턴이 있어서 starvation 이 올수있는데

뻇는 희생양 패턴을 매번 다르게해서 해결할수 있다 -> 희생양 뽑을떄 비용이 최소인것만 고르는것이아니라 rollback 된 횟수도 고려한다.

 

 

 

Deadlock Ignorance

데드락이 일어나든 안일어나든 무시하는것이다

데드락 관련 뭐할때마다 오버헤드가 크기때문에 운영체제 입장에서 데드락을 무시하는것이다

 

사용자가 알아서 느려지면 종료시키고 이런것들을 하는것이다

현대의 운영체제들은 거의다 이방법을 채택함