- 정리의 기반은 학교 강의 노트와 [Operating System Concepts]를 참고하였습니다.
22-1학기 운영체제를 들으면서 중간고사에 대비하면서 정리해놓은 개념들입니다…ㅎ 다른 핵심 내용이나 기본이라고 생각되는 내용들은 제외하고 제가 시험에서 중요하다고 생각하는 것들만 중구난방으로 정리되어있습니다.
Deadlock
데드락을 알기 전에 System Model이라고 하는 시스템 자원의 구조를 알아야한다.
System Model : 시스템의 자원은 타읍을 가지며 해당 타입은 자원(R)의 실체인 인스턴스(W)를 가진다.
객체지향 프로그래밍에 빗대어서, 자원 = class, 인스턴스는 new class()로 비유할 수 있다.
타입 ex) CPU cycles, Memory Space, I/O Device
발생 조건
아래 4가지의 조건을 모두 충족하여야 데드락이 발생한다.
- Mutual Exclusion : 오로지 하나의 프로세스만이 하나의 자원을 사용
- Hold and Wait : 자원을 최소 한개를 가지고 있으면서 다른 자원을 기다리는 상태
- No Preemption : 프로세스는 작업을 완료한 후에만 소유하고 있던 자원 반납
- Circular wait : 프로세스가 다른 프로세스의 자원을 요구하는 형태가 원형
Cycle이 없으면, 데드락은 발생하지 않는다.
Cycle이 있으면, 데드락이 발생할 “확률”이 생긴다.
Deadlock을 다루는 방법
Prevention : 애초에 데드락이 발생하지 않게
- How?
- Mutual Exclusion 조건 없애기 : 실행 불가능
- Hold and Wait 조건 없애기 : 프로세스가 자원을 요청할 때 항상 어느 자원도 소유하지 않게 하고, 프로세스가 실행되기 전에 필요한 모든 자원을 갖도록
- No Preemption 조건 없애기 : 프로세스가 즉시 할당 받을 수 없는 자원을 요청하면 소유한 자원 모두 반납시켜버리기
- Circular Wait 조건 없애기 : 자원들의 Total Ordering을 반환하는 F()함수 사용 = 프로세스가 현재 소유하고 있는 자원의 타입의 f()함수 우선 순위보다 높은 우선 순위의 자원들만 요청할 수 있고, 소유하고 있는 자원의 우선 순위가 가장 높다면 소유하고 있던 자원 모두 반납.
Avoidance : 데드락 회피
OS에 자원 요청이 들어오면 자원을 할당해주었다고 가정하고 잠재적으로 데드락이 일어나는지 유무를 파악하여 자원 할당 여부 판별
how? 프로세스 간 자원 할당 순서를 조사한다.
- 판별 결과
- unsafe state : 데드락 발생 가능(“꼭” 발생하는 것은 아니라는 뜻)
- safe state : 데드락 x
safe state sequence(데드락이 걸리지 않는 자원 할당 순서)가 하나라도 있으면 safe state이다.
- Avoidance 알고리즘
- 자원의 인스턴스가 1개일 경우 : Resource-allocation 그래프 사용
- 자원의 인스턴스가 여러개일 경우 : Banker’s 알고리즘 + safety 알고리즘 사용 = 뱅커스 알고리즘에서 needs를 파악한 후, safe state sequence 구하는 방법
Detection : 데드락이 발생하면 감지 후 복구
- 지속적으로 검사하고, 데드락이 발생하면 프로그램을 종료 후 다시 시작하므로 비효율적이다.
- 데드락 복구 방법
- 모든 프로세스 일시 종료
- 데드락에 빠진 프로세스들을 하나씩 종료해가며 데드락 탈출
- 자원의 인스턴스가 1개일 경우 : Wait-for-graph 사용하고, 이 그래프에서 사이클이 존재할 경우, 데드락이다.
- 자원의 인스턴스가 여러개일 경우 : 뱅커스 알고리즘과 유사(needs대신 request를 조사하여 사용)
needs : 현재 요청하지 않아도 작업을 끝내기 위해 필요한 자원의 양
request : 현재 요청한 자원