cs/운영체제
7강-1. Deadlock 1
Tomato_Coffee
2023. 11. 6. 22:13
- Deadlock : 각자 일부 자원을 가지고 있고 자원을 주지 않으면서, 상대방의 자원을 요구하는 경우
- Deadlock 문제
- example 1) 프로세스가 하려는 일 : 하나의 테이프 드라이버에서 읽어서 다른 테이프 드라이버로 copy 하는 것.(하드웨어 자원을 기다리면서 deadlock이 생긴 일.)
- 두 프로세스가 각각 테이프 2개를 점유해야 작업이 가능하다.
- 상대방의 자원을 요구하면 deadlock 발생
- example 2) 2개의 프로세스가 lock을 거는 semaphore를 획득해서 일을 하고 싶어 함.(소프트웨어 자원을 기다리면서 deadlock 발생)
- 프로세스 0 : A를 먼저 획득한 다음에 B를 획득하려는 상황에서 cpu를 빼앗김
- 프로세스 1 : B를 먼저 획득한 다음에 A를 획득하려는데, 이미 A는 프로세스 0 이 가지고 있다.
- 이 상황에서는 cpu 가 어느 누구에게 가더라도 둘 중에 하나는 획득이 안되기 때문에 deadlock 발생
데드락의 4가지 조건은 시험에 자주 나오니 잘 알아두자.
- 자원(□)에서 프로세스(○)로 향하는 화살표의 의미는 해당 자원이 프로세스에 속해있다는 의미이다.
- 즉, 프로세스가 자원을 가지고 있다는 의미
- 프로세스(○)에서 자원(□)으로 향하는 화살표는 지금 이 프로세스가 자원을 요청한 것을 의미하고 아직 자원을 얻지 못한 상태를 의미한다.
- 아래 사각형 안에 있는 점들은 자원의 인스턴스를 의미한다.
- 그래프에 사이클이 없으면 deadlock이 아니다.
- 자원 할당 그래프에 사이클이 있으면 deadlock인가?
- deadlock 일 수도 있고 아닐 수도 있다.
- 자원 당 인스턴스가 하나씩만 있을 경우 : 사이클은 곧 데드락을 의미한다.
- 자원의 인스턴스가 여러 개 있을 경우
- deadlock 일 경우
- deadlock 아닐 경우
- deadlock 일 수도 있고 아닐 수도 있다.
deadlock은 빈번히 발생하는 이벤트가 아니기 때문에 미연에 방지하기 위해서 훨씬 더 많은 오버헤드를 감수하는 것은 비효율적이기 때문에 대부분의 OS는 deadlock를 생기든 말든 놔둔다.
Deadlock Prevention : 데드락이 발생하는 4가지 조건 중에 하나를 원천적으로 차단해서 deadlock에 들어가지 못하게 하는 방법.
- Mutual Exclusion
- 이건 막을 수 있는 조건은 아니다.
- 왜냐하면 자원을 한 번에 여러 프로세스가 공유해서 쓸 수 있는 그런 자원이면 애초에 deadlock에 대한 말이 안 나왔을 것이다.
- Hold and Wait
- deadlock이 생기는 이유는 프로세스가 가진 자원은 보유하고 내놓지 않고 있으면서, 다른 자원을 기다리기 때문에 데드락이 생긴다.
- solution
- 자원을 기다려야 하는 상황에서는 자원을 보유하고 있지 않아야 함.
- 아래 방법 1,2
- 자원을 기다려야 하는 상황에서는 자원을 보유하고 있지 않아야 함.
- solution
- deadlock이 생기는 이유는 프로세스가 가진 자원은 보유하고 내놓지 않고 있으면서, 다른 자원을 기다리기 때문에 데드락이 생긴다.
- 방법 1 : 비효율적이다.
- wait 할 일이 없어서 deadlock이 생기지 않는다.
- 이렇게 되면 프로세스가 종료할 때까지 모든 자원을 쓰는 게 아니라, 매 시점마다 필요로 하는 자원이 다른데
- 미리 보유하고 있으면 자원에 대한 비효율성이 생김.
- 방법 2 : 필요할 때 자원을 할당받는다.
- 만약에 어떤 프로세스가 자원을 hold 하고 있는데, 다른 자원을 wait 해야 하는 상황에서는 이미 hold 한 자원을 전부 뱉어낸 다음에 기다린다.
- 지금 당장 필요한 자원을 얻거나 || 자원을 뱉어내서 아무것도 없거나
- 누군가는 필요로 하는 자원을 얻어서 일을 진행할 수 있다.
- No Preemption
- 이 조건에서 deadlock이 생기는 이유는 자원을 뺏어올 수 없기 때문이다.
- 따라서 자원을 preemption 할 수 있게 하면 deadlock이 안 생김.
- 자원을 아무렇게 빼앗으면 문제가 발생하기도 한다.
- 따라서 자원의 현재 사용 상태를 save, restore 할 수 있는 자원에서 주로 사용한다. (CPU, memory)
- 어떤 자원은 중간에 빼앗아오면 문제가 생기는 작업일 경우에 Preemption을 허용하기 어렵다.
- Circular Wait
- 필요한 자원들이 꼬리를 물면서 사이클이 생성된 경우를 말한다.
- 이걸 막기 위해서는 어떻게 해야 할까?
- 자원마다 순서를 정한다.
- 정해진 순서대로 자원을 할당해야 한다.
- 이렇게 하면 deadlock이 안 생긴다.
결론 : 위에서의 4가지의 Deadlock Prevention은 원천적으로 deadlock을 막을 수 있지만
1. 이용률이 나빠짐, 2. 성능이 나빠짐, 3. 기아 문제가 발생할 수도 있다.
생기지도 않을 deadlock을 생각해서 제약 조건을 많이 달아 놓기 때문에 상당히 비효율적이다.
- Deadlock avoidance 동작방식
- 프로세스가 시작돼서 종료될 때까지, 그때그때 상황마다 쓸려는 자원의 수나 종류가 다르다.
- 그래서 deadlock avoidance는 보통 프로세스가 시작될 때 평생에 쓸 자원의 최대량을 미리 알고 있다고 가정하고 그리고 deadlock을 피해 간다.
- 어떤 프로세스가 자원 요청을 했을 때, 혹시 내가 자원을 할당해주면 deadlock이 생길 가능성이 있겠다면 자원의 여분이 있다 하더라도 자원을 안 준다.
- 이전에 보여준 자원할당그래프와 다른 점은 점선이 있다는 것이다.
- 점선 : 항상 프로세스로부터 자원에게 가는 화살표만 있다.
- 점선의 의미 : 이 프로세스가 평생에 적어도 한 번은 이 자원을 사용할 일이 있다.
- 이 상황에서 P2가 R2에 대한 자원을 요청했다면 점선이 실선으로 변경된다.
- R2 자원은 아무도 가지고 있지 않기 때문에 요청한 프로세스에게 줄 수 있다.
- 3번째 그림은 데드락이 아니다
- 왜냐하면 아직 남은 점선은 지금 아직 요청한 상황은 아니다.
- 점선 : 항상 프로세스로부터 자원에게 가는 화살표만 있다.
- Deadlock avoidance는 최악의 상황을 가정한다.
- Deadlock의 가능성이 있는 자원의 요청에 대해서는 애초부터 받아들이지 않고 그냥 둔다.
- 만약 1번 프로세스(P1)가 자원(R2)을 요청했을 경우
- 그때는 자원을 준다
- 사이클이 생길 염려가 없기 때문이다.
- 그때는 자원을 준다
Deadlock Avoidance는 사용 가능한 자원이 있다 하더라도 deadlock의 위험성이 있다고 하면
애초부터 자원을 주지 않는다.
cf) Resource Allocation Graph Algorithm은 자원당 인스턴스가 1개만 있는 경우에만 사용
- 이 상황에서는 남아있는 자원은 줄 수 있지만, 무조건 주는 게 아니다.
- 문제가 생길 수 있으면 자원이 남아있어도 안 준다.
- Need : 자원을 추가 요청 할 수 있는 양
- Need와 Available을 비교한다.
- Need <= Available : true이다.
- 자원을 할당해 준다.
- Need > Available : false
- 요청한 자원수에 해당하는 자원이 여유가 있더라도 자원을 할당해 주지 않는다.
- 왜냐하면 최대 요청을 할 때, 가용 자원만으로는 처리가 안되기 때문이다.
- 언제가 다른 프로세스들이 처리가 끝나서 종료가 돼서 자원을 반납할 때 Available이 늘어나서
- Need <= Available을 충족을 시키면 프로세스에게 자원을 나눠준다.
- Need <= Available : true이다.
- Need와 Available을 비교한다.