16강 Deadlocks 1

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

반효경 [운영체제] 16. Deadlock 1

 

데드락 : 한국말로 교착상태이다.

 

뭐 어떻게든 방법이없게 막혀있는 상황이다 도로보면 뭐 방법이없다.

기존에 데드락 상황을 보면 서로 젓가락 한짝씩 잡고 밥먹겠다고 하는 상황이다.

 

데드락: 일련의 프로세스들이 서로 자원을 쥔상태에서 상대가 가진 자원을 요구해서 서로 아무일도 하지못하는 교착상태이다.

자원은 하드웨어 자원일수도, 소프트웨어 자원일수도 있다.

 

하드웨어

프로세스가 할작업은 A하드에서 B하드에 옮기는 작업인데

각 프로세스들이 A랑 B를 각각 가져간다면 그상태로 둘다 잠들어 버릴것이다. 얻지 못하니까

-> 어느누구도 계속 진행할수 없다.

 

소프트웨어 

-> 공유데이터에서  세마포어 변수 A B를 서로 가져간다면 마찬가지로 진행이안된다.

 

 

프로세스가 자원을 요청하는 절차는 크게 4단계가 있다

1.request(요청)

2.allocate(획득)

3.use(사용)

4.release(반납)

 

이제 각 단계 별로 어떻게하면 데드락을 막을수 있는지 살펴본다함.

 

데드락이 발생하는 조건 4가지

이 4가지 조건에 다 들어간경우 데드락이 발생한다.

 

1.mutual exclusion (상호배제)

각 자원이 뮤텍스일때이다. -> 공유 불가한 자원(lock 걸리는 자원)

2.No preemption (비선점)

이제 자원을 빼앗기지 않는 상황이다 혼자 내놓는 상황만 있는것이다.

3.hold and wait(보유대기)

이미 내가 가진자원은 놓지않고 추가적인 자원을 구하는 상황

4.circular wait(순환대기)

각각 서로가 가져야하는 것들을 이상하게 하나씩 찢어서 가지고있는 상황일때

 

이4가지 조건중 하나라도 만족하지 않으면 데드락이 발생하지 않는다.

 

데드락이 발생했는지 알기위해서 자원할당 그래프라는것을 그려서 알아낸다

 

자료를 보면 동그라미가 프로세스이고 사각형이 자원이다.

화살표는 자원의 이동을 뜻하는데

자원에서 프로세스 방향의 화살표는 그 프로세스사 자원을 가지고있다는 뜻이고

프로세스 에서 자원방향은 프로세스가 자원을 요청(아직 획득은 못한상태) 를 나타낸다.

사각형안의 점의 수는 자원의 수를 나타낸다 -> 자원이 여러개일수 있으니까

 

이 그림을 보면 어떤상태인지 알수있다.

 

프로세스1 은 2번자원을 가지고있으면서 1번자원을 요구

프로세스 2는 1,2번 자원을 가지고있으면서 3번 자원을 요구

프로세스3은 3번 자원을 가지고있는 상태이다.

-> 사이클이 없으므로 데드락이 아니다.

 

그래프를 보고 데드락인지 판단하려면

1.그래프 내에 사이클이 없으면 데드락이 아니다.

위의 자료보면 첫번쨰 그래프는 사이클이 두개나 있다.

이런식이다 사이클을 보는것.

 

2.자원당 인스턴스가 하나밖에 없으면 데드락이다.

3.여러개의 자원이 있더라도 데드락일수도 아닐수도 있다.

 

위의 그림 예시를 보면 

1번째 그림은 데드락이다 보면 자원이 2개라도 각각 사이클 2개에 물려있기 때문에 진행이 불가하다

 

2번째 그림을 보면 데드락은 아니다 여분의 자원이있고 다른 2번 4번 프로세스들이 데드락과 관여 없기 때문에 자원을 내려놓을수 있기 때문이다.

 

데드락의 처리방법

크게 4가지를 살펴볼것이다.

데드락의 처리방법으로 위로 갈수록 더 강한방법이다

위쪽 두 방법은 미연에 데드락이 발생하지 않도록 예방하는 것이다.

마지막 방법은 데드락을 그냥 무시하는건데 현대의 운영체제들은 데드락을 걍 무시한다. ㅋㅋㅋㅋㅋ(뭐 어쩌라고)

근데 관여를 안하면 어캐 데드락을 해결하느냐? 운영체제가 관리안하면 프로세스가 느려지든 맛이가든 하면 사람이 알아서 껏다 키는 방법이다. 

 

데드락이 자주생기는일이 아니므로 미연의 방지하는것이 현대적인 시스템에서 오히려 오버헤드가 커서 방치한다.

 

1. Deadlock Prevention(데드락을 막는 가장 강력한방법)

데드락에 들어가는 조건 4가지중 하나를 원천적으로 차단해서 데드락에 들어가지 못하도록함

 

1.Mutual Exclusion 은 막을수가 없음 당연히 생각해보면 lock을 걸어야하니까

 

2.Hold and wait 

이 방법을 배제하려면 자원을 기다리는 상황에서는 자원을 안 갖고있도록 처리하면된다

세부적인 방법으로는 2가지가 있는데 

-방법1 : 프로세스가 시작시 애초에 필요한 자원을 다 할당받게하는것

    -> 자원의 비효율성이 미칠것임

-방법2 : 자원을 기다려야하는경우 이미 잡아놓은 자원들을 일단 다 뱉어내고 대기한다.

 

3. no Preemption

비선점형이라 문제가 되는것이므로

선점형으로 빼앗아 버리면 되는것임

->이러면 안생김 cpu 나 메모리같이 뻇었다 복구가 쉽도록 설계된 자원이니까 쉬움 그래서 cpu 이런문제는 데드락 자체가 없는것임

근데 어떤 자원들은 중간에 뺏어가면 엉망이되서 이렇게 뻇는 방법을 사용하는게 어려울수 있음 그래서 그런경우 이런방법을 적용할수 없음

 

4.circular wait

사이클이 만들어지는것을 막는건데 이것을 막기위해서는 자원에 번호를 매기고 무조건 낮은 번호부터 자원을 획득하는 규칙을 정하는것이다.이러면 이제 낮은번호부터 있으면 데드락이 안걸린다 순차적으로 획득하니까.

 

이렇게하면 데드락은 막을수있지만 자원에대한 이용율이 낮아지고 전체시스템의 성능이 낮아니고 starvation 이 걸릴수도있다

즉 비효율 적이다.

 

 

 

2. Deadlock Avoidance(이것도 데드락 예방)

자원요청시 부가적인 정보 를 통해 데드락의 가능성이 없을때만 할당하는것이다

 

프로세스가 시작되어서 종료될때까지 그때그떄 쓰려는 자원의 종류와 수가 다르다.

deadlock avoidance 의 경우 프로세스가 시작될때 이프로세스가 평생 쓸 자원의 양을 알고있다 가정하고 그 데드락을 피해가는것이다.

 

만약 프로세스가 자원을 요청했을때 자원의 여분이 있더라도 데드락의 가능성이있다면 자원을 할당하지 않는것이다.

 

deadlock avodiance 도 두가지로 나눠서 볼수있다.

 

자원이 한개씩만 있는경우에는 아까봤던 그래프를 사용한 알고리즘을 사용하는것이고

 

여러개의 자원이 있는경우에는 bankers 알고리즘을 사용할수 있다.

 

자원이 하나씩 있는경우의 해결책(자원할당 그래프)

위의 자료를 보면 기존 자원할당 그래프에서 점선 화살표가 추가됐는데

점선 화살표는 프로세스로부터 자원을 향하는 화살표만 있고 의미는 프로세스가 평생동안 적어도 한번은 이자원을 사용할 일이 있다는것이다.(이게 부가정보 프로세스 시작시 어떤자원쓸지 다 파악하니까)

 

만약 실제로 자원을 프로세스가 요청한다면 점선 화살표가 실선으로 바뀔것임

 

이제 위의 자료의 그래프들을 보면 왼쪽에서 오른쪽으로 시간순서로 가는것이다

 

처음에는 2번 자원을 아무도 안가지고 있다가

2번 프로세스가 2번자원을 요청하고 아무도 안가지고있으니까 자원을 할당해서 3번 그래프가 나오게된다.

 

3번 그림을 보면 현재 데드락은 아니다 하지만 데드락이 될수도 있는 가능성이 있는것이다 -> 현시점에서 정상적으로 데드락이 안걸리고 끝날수도 있다.

 

근데 deadlock avoidance 방식은 최악의 상황을 상정하는것이다.

재수없게 3번 상황에서 데드락이 걸릴수도 있기 때문에 2번에서 3번상황으로 자원을 할당하는것을 막아버리는것이다.

 

그래서 1번 프로세스가 이자원을 신청해서 모든자원을 다 사용하고 돌려놨을떄만 2번 프로세스가 쓸수있는 상황이오게 되는것이다.

 

 

자원이 여러개 있는경우의 해결책(뱅커스 알고리즘)

방법은 위의 자료와 같은데 예시를 보고 이해하는것이 더 빠르다.

여기서 보면 예제에서 프로세스가 5개가있고

자원은 A ->10개,B -> 5개 ,C -> 7개 세 종류가 있다.

 

그래서 상황을 보면

Allocation 이 현재 자원을 갖고있는 갯수

max 는 프로세스가 가장 많이 가졌을때의 자원의 갯수  

Avaliable 현재 할당된 자원말고 가용 가능한 자원의 수

need 추가요청 가능양  max 에서 현재 할당받은 양 뺀거 즉 당장 max 에 도달하려면 필요한 자원의양

 

 

이상황에서 프로세스 0번이 자원을 A 1개 C 2개 를 요청했다고 쳐보자

분명 가용자원에서 현재 줄수있는 상태이다. 하지만 need 를 다 줄수있을때만 자원을 할당한다 즉 그냥 max값을 못줄수 있는 상황이면 자원을 안줘버리는것이다.

 

즉 남은 자원으로 need 를 충족 가능할때만 자원을 할당한다.

 

즉 자원요청이 들어왔을때 조건에 따라 자원을 줄것인지 안줄것인지를 결정하는 알고리즘이다.

 

 

 프로세스 0번이 자원을 A 1개 C 2개 를 요청했다고 쳐보자

가용자원에서 현재 줄수있는 상태이다. 또한최대 요청 하는 악수도 가용자원내에 해결되기 때문에 자원을 할당하게된다.

 

 

최종적으로 정리했을때 deadlock Avoidance 는 항상 safe한 상태를 유지한다.

safe한 상태는 가용자원이 최악의 상황이 다가와도 대응할수있는 상황에만 자원을 주는것이다.

 

deadlock avoidance 는 항상 safe 한 상태를 유지하게 하는것이다.

 

그리고 딱히 뭐 자원을 준다고 문제생기지않아도 굉장히 보수적으로 판단해서 준다.

 

딱봐도 다 겁나 비효율 적이다.