운영체제#16
LeeMir, 31 May 2021
6강 - Deadlock
Deadlock
- 한 집단의 프로세스들이 서로 이벤트가 끝나길 기다리는 상황이 발생해 무한 대기에 빠지는 현상
- Deadlock에 걸리는 상황은 자원 공유뿐 아니라 여러 이벤트가 존재함
- Deadlock의 4 조건
- Mutual exclusion condition(상호 배제 기능이 있을 때)
- Hold and wait condition(독점적으로 자원을 사용할 때)
- No preemption condition(문맥교환 같은 경우가 아니라 한 번 이벤트를 시작하면 끝날때까지 중단할 수 없을 때)
- Circular wait condition(프로세스들이 꼬리에 꼬리를 물면서 hold and wait에 빠질 때)
- 조건을 모두 달성했다고 해서 Deadlock이 반드시 발생하지는 않고, 각 프로세스를 어떤 순서로 실행하느냐에 따라 발생할 수도 있음
- Deadlock Modeling
- 사각형 : 자원, 동그라미 : 프로세스
- Deadlock 해결책
- 타조 전략(문제를 무시하고 그냥 재부팅을 권함)
- 운영체제의 주기적인 Deadlock Detection
- utilization이 많이 떨어진 프로세스가 있을 경우 Deadlock으로 의심
- Deadlock이면 프로세스를 죽임
- Deadlock 회피
- 자원을 할당해 줄 때 Deadlock 발생 가능성을 검사해 발생 가능성이 있으면 자원 할당을 하지 않음
- Prevention(예방)
- Deadlock의 4 조건을 없애버림
Deadlock Detection
- 각 타입의 자원이 하나만 존재할 때
- 자원할당 그래프를 그린 후, 사이클이 존재하는지 검사
- 각 타입의 자원이 여러개 존재할 때
- Bankus 알고리즘
- Allocate Table과 Require Table을 만듦
- Table을 탐색하면서, 현재 쓸 수 있는(Available) 자원으로 처리할 수 있는 프로세스부터 끝냄
- 한 프로세스가 끝나고 자원을 반납하면 쓸 수 있는 자원이 늘어나 처리할 수 있는 프로세스가 또 생김
- 만약 프로세스가 살아있는데 현재 쓸 수 있는 자원으로 처리할 수 있는 프로세스가 하나도 없을 경우 Unsafe 상태로 판단
- Deadlock 회피를 적용한다면, 할당할 때부터 할당해주면 Unsafe가 될 수 있는지 검사해 가능성이 있으면 할당하지 않음
- Bankus 알고리즘
Recovery from Deadlock
- Deadlock을 Detect했다면 Recovery가 필요함
- preemption
- 자원이 preemption이 가능하다면 프로세스를 일시정지해서 자원을 다른 프로세스에게 줌
- rollback
- 프로그래밍 기법 중 하나
- 체크포인트를 기록해뒀다가 Deadlock이 발생하면 rollback
- killing processes
- 대부분의 경우 프로세스를 희생해야 함
- Deadlock에 걸려있는 프로세스 중 하나를 죽이고 그 자원을 다른 프로세스에게 부여
Deadlock Avoidance
- 자원을 할당할 때, Deadlock이 발생하지 않을 것 같을 때에만 할당해주는 기법
Deadlock Prevention
- Attacking the Circular Wait Condition
- Circular Wait가 생기는 이유 : 프로세스들이 임의의 순서로 자원을 요구하기 때문
- 따라서 자원을 할당받는 순서를 통일하면 Circular Wait을 예방할 수 있음
- 자원의 종류가 너무 많아 이를 모든 프로세스에 요구하기에는 까다로움
- Attacking the No Preemption
- CPU나 메모리의 경우에는 기본적으로 Preemption이 가능
- printer의 경우 원래 Preemption이 불가능한데, 스풀링 같은 기법을 사용하면 Preemption이 가능해짐
- Attacking the Mutual Exclusion
- 운영체제를 잘 설계하면 Deadlock이 발생하지 않게 상호 배타적인 디바이스들을 상호 배타하지 않게 할 수 있음
- 한 프로세스가 하드디스크 전체를 독점하지 않음
- 하드디스크 안에 파일 단위로 나뉘어있어 여러 프로세스가 하드디스크를 공유해서 쓸 수 있음
- 스풀링 기법
- Attacking the Hold and Wait
- 프로세스가 여러 자원을 요구할 때 순차적으로 요구하게 하는게 아니라, 한꺼번에 다 받아오고 시작하게 함
- 자원 효율이 많이 떨어짐
- 자원을 많이 요구한 프로세스는 꽤 오래 기다려야할 수 있어 Starvation이 발생할 수 있음
- 현실성이 많이 떨어지는 기법
Intergrated Deadlock Strategy
- 운영체제에서는 Deadlock의 발생 가능성을 줄이고자 모든 방법을 동원하고 있음
- Swappable space : 처음에 Swap 영역을 할당할 때 나중에 더 요구하는 경우가 없게 여유롭게 할당해 줌
- Process resource : resource ordering을 해서 deadlock을 예방하거나 deadlock 회피
- Main memory : preemption을 통한 예방
- Internel resource : resource ordering을 해서 deadlock을 예방함
Other Issue
- Two-phase locking
- lock의 순서가 엇갈려 deadlock이 발생하는 것을 막는 방법
- 하나를 lock하는 데 성공하고 다른 하나를 lock하려는데 이미 lock이 되어있는 상태(다른 프로세스에서 사용중인 상태)라면 처음에 lock했던 것을 unlock하고 기다림
- Communication Deadlocks
- 통신에서 송신 버퍼와 수신 버퍼가 일치할 경우 각 호스트에서 송신을 위해 송신 버퍼를 채우는데, 우연히 동시에 송신을 위해 버퍼를 꽉채울 경우 상대의 버퍼가 비어있지 않아 송신을 할 수 없고 Deadlock에 빠짐
- Livelock
- 겉으로는 실행되는 것처럼 보이지만 서로 폴링하고 있는거라 사실상 Deadlock과 같은 상태
- CPU를 소비하는 거라 Deadlock보다 더 안좋음
- Starvation
- Deadlock이 발생해 하나의 프로세스를 희생했는데, 그 이후 그 프로세스가 실행되었을 때 다시 Deadlock이 발생했고 또 그 프로세스가 희생되는 반복에 빠짐