Deadlocks1 : Prevention, Avoidance

ㅎㅎ·2023년 7월 25일

운영체제, 반효경

목록 보기

13/19

Deadlock: 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태
Resource(자원): HW, SW 등을 포함하는 개념 ex) I/O device, CPU cycle, memory space, semaphore 등
프로세스가 자원을 사용하는 절차: Request ⇒ Allocate ⇒ Use ⇒ Release
Deadlock Example1
- 시스템에 2개의 tape drive가 있음
- 프로세스 p1과 p2 각각이 하나의 tape drive를 보유한 채 다른 하나를 기다리고 있음
Deadlock Example2

Deadlock Prevention: 자원 할당 시 Deadlock의 4가지 필요조건 중 어느 하나가 만족되지 않도록 하는 것
Deadlock Avoidance
- 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당
- 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당
Deadlock Detection and Recovery: Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견시 recover
Deadlock Ignorance
- Deadlock을 시스템이 책임지지 않음
- UNIX를 포함한 대부분의 OS가 채택
- 문제가 발생하면 사용자가 프로세스를 종료하는 등 알아서 처리
- Deadlock 처리 알고리즘을 이용하는 것이 자원 활용도 등의 측면에서 비효율적이기 때문

Mutual Exclusion
- 공유해서는 안되는 자원의 경우 반드시 성립해야 함
Hold and Wait
- 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다
- 방법1: 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법
- 방법2: 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청
No preemption
- process가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨
- 모든 필요한 자원을 얻을 수 있을 때 그프로세스는 다시 시작된다
- State를 쉽게 save하고 restore 할 수 있는 자원에서 주로 사용(CPU, memory) -> why..?
Circular Wait
- 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당
- 예를 들어 순서가 3인 자원 Ri를 보유 중인 프로세스가 순서가 1인 자원 Rj을 할당받기 위해서는 우선 Ri를 release해야 한다
문제점: Utilization 저하, throughput 감소, starvation

Deadlock avoidance
- 자원 요청에 대한 부가정보를 이용해서 자원 할당이 deadlock으로 부터 안전한지를 동적으로 조사해서 안저난 경우에만 할당
- 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별
  "최대 사용량을 미리 선언"하도록 하는 방법임
safe state
- 시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태
safe sequence

Resource Allocation Graph Algorithm
- 자원별 instance가 1개 일때 사용
- Claim edge를 포함하여 자원 요청 수락 시 cycle이 생기지 않는다면 요청을 수락
Banker's Algorithm
- 자원별 instance가 여러 개 일때 사용
- 뱅커스 알고리즘은 safe sequence가 존재하는지 확인하지 않음
- 요청한 프로세스의 MAX 요청을 Available 자원 가지고 감당 가능한지만 확인하고 요청을 수락할지 거절할지 결정함 ⇒ 즉 해당 프로세스가 추가로 최대로 요청하더라도 Available 자원으로 충족시켜줄 수 있다면 해당 프로세스는 언젠가 수행을 끝내고 자원을 반납할 수 있음. 이러한 방식으로 safe sequence가 존재한다면 deadlock이 발생하지 않으므로 safe한 상태임.
Q. 왜..? 저것만 파악하면 sequence가 존재하는지 아닌지 알 수가 있기 때문이겠지?
- 우선 어떤 프로세스의 MAX 요청 값이 최대 Available보다 크다면 할당이 불가 ⇒ unsafe 상태
- 어떤 프로세스의 MAX 요청 값이 현재 Availalble보다 크다면 그 프로세스의 어떤 요청도 허용 X, 만약 허용한 후에 MAX 값을 요청하게 되면 hold & wait 상태로 기다릴 것이고 deadlock이 발생하는 것이 불가피하기에 ?

뭔가 머릿속 모순이 정리가 안 된다. 공룡책을 참고해서 다시 공부해봐야겠다.
safe state와 unsafe state의 정의가 뭔지, deadlock이 발생할 수 있는 상황이 존재하냐 안하냐, safe sequence가 존재하냐 안 하냐 뭐가 기준인지, 둘은 뭐가 다른지
뭔가 강의에서 전달한 건 max 자원을 avaiable로 충족할 수 있는 프로세스의 요청이면 그 요청을 수락하고 나서 그 후에 프로세스가 정상적으로 종료될 수 있음을 보장하기 때문에(max가 충족 가능하기 때문에) 그 프로세스가 종료하고 반납한 자원을 가지고 다른 프로세스들을 똑같이 실행시킬 수 있으면 safe sequence가 존재하고 그래서 요청을 수락할 수 있다 이말인 거 같긴 한데, 이때 safe sequence라는 존재를 확인하기보다는 이러한 요청 수락 로직에 의해 각각의 프로세스가 정상적으로 수행될 수 있는지 확인하기 때문에 max 값을 avaiable이 감당 가능한지만 확인하면 된다고 한 거 같고

Hello World