목차
데드락(Deadlock, 교착상태)
데드락?
OS에서 데드락이란, 2개 이상의 작업이 서로 상대방의 작업이 끝나기만을 영원히 기달려서 결국 아무것도 하지 못하고 있는 상태입니다. 데드락은 아래 4가지 필요 조건을 다 만족해야지 발생합니다.
1. 상호 배제(Mutual Exclusion) : 한 순간에 오직 하나의 프로세스만 자원을 사용할 수 있어야 합니다.
2. 점유 대기(Hold and wait) : 자원을 적어도 하나 보유하고, 다른 프로세스가 점유하고 있는 자원을 얻기 위해 대기하는 프로세스가 있어야 합니다.
3. 비선점(No preemption) : 비선점 형태로 Task가 끝나야지만 자원을 놓아야 합니다.
4. 순환 대기(Circular wait) : 대기 프로세스의 집합이 순환 형태로 자원을 얻기위해 대기하고 있어햐 합니다.
데드락 해결방법
● 데드락 방지(prevention) : 필요조건 4개 중 적어도 하나 이상 성립하지 않는다면 데드락이 발생하지 않습니다.
● 데드락 회피(avoidance) : 데드락 발생 가능성이 있음을 인정하고 적절히 회피합니다
● 데드락 허용(allow) : 데드락 발생을 허용하지만 데드락을 탐지하여 데드락에서 회복합니다.
● 데드락 무시(ignore) : 데드락이 생겨도 무시합니다. 사실 대부분의 OS가 이 방식을 사용합니다. 왜냐하면 비용이 저렴하기 때문입니다. 유저가 자주쓰는 시스템에서는 그냥 유저가 컴퓨터를 껐다 키는게 빠르고 편합니다.
데드락 방지 (Deadklock Prevention)
- 상호 배제 : 공유자원이 너무 많아서 이 조건을 막는 것은 어렵습니다.
- 점유 대기
① 시작하기 전에 필요한 자원을 한꺼번에 할당하는 방식이 있을 수 있습니다.
② 잡고 있는 자원이 없을 때만 자원을 요청합니다. - 비선점
① 자원 할당이 불가능하면 가지고 있는 자원을 다 내놓을 수 있습니다.
② 대기중인 프로세스의 자원을 반납할 수 있습니다.
③ 자원을 다 할당 받을 수 있을 때 프로세스를 다시 시작합니다. - 순환 대기 :어떤 자원을 요청할 때 그 자원보다 높은 순서의 자원을 가질 수 없게 합니다. 가장 현실적인 방법.
순환대기에서 각 자원에(뮤택스락들) 고유 번호를 지정합니다. 이 번호가 순서가 됩니다.
그러면 이 순서에 맞춰 얻게 한다면 데드락을 막을 수 있고, 순서대로 락을 획득해야하는 규칙을 어기면 데드락이 생길 수 있습니다. 이 예시는 다음과 같습니다.
데드락 회피 (Deadklock Avoidance)
데드락 회피에앞서 안전상태(Safe State)를 먼저 알고 갑니다.
안전 상태(Safe State) : 시스템에 있는 모든 프로세스가 각자 필요한 자원을 사용할 수 있는 실행 순서가 존재할 때, 즉 데드락에 걸리지 않고 실행할 수 있는 순서가 있을 때 시스템은 안전한 상태에 있다고 말합니다.
즉 데드락 회피는 시스템이 안전한 상태를 유지할 수 있을 때만 자원을 할당해 데드락 자체를 회피합니다.
*위 사진과 같이 불안전한 상태라고 해서 반드시 데드락이 발생하는 것은 아닙니다.
단일 인스턴스를 가지는 리소스타입(시스템 내의 자원 유형이 다 단일)은 resource-allocation graph를 사용합니다.
다중 인스턴스를 가지는 리소스 타입은 Banker's Algorithm을 사용합니다.
은행원 알고리즘 (Banker's Algorithm)
각 프로세스는 사용할 자원의 최대치를 사전에 서언해야 합니다. 이 최대치를 가지고 안전 상태를 시뮬레이션 합니다. 프로세스가 원하는 모든 자원을 확보하면 작업을 마친 후에 모두 반납합니다.
현재 쓸 수 있는 여유 자원(Avaulable) 프로세스가 쓸 최대 자원(Max), 프로세스에 현재 할당된 자원(Allocation), 이제 프로세스가 필요한 남은 자원(Need = Max - Allocation)을 가지고 시뮬레이션을 돌립니다.
*자세한 내용은 참고, 예제를 풀면서 다시 알아보는걸로..
데드락 허용(Deadklock Allow)
데드락 탐지하여 회복하는 방식으로, 탐지의 경우 회피와 유사한 형태이지만 차이점이 있습니다.
● 데드락 탐지
데드락 탐지는 사전 정보 즉 최대치가 필요하지 않습니다. 데드락 탐지는 Available, Allocation에 추가로 현재 요청인 Request를 Need로 간주하고 Banker's 알고리즘을 실행합니다. 이 때 불안전 상태라면 데드락으로 간주합니다.
데드락 탐지 알고리즘을 아무 때나 수행하면 데드락을 유발한 스레들를 식별하지 못할 수 있습니다.
반면 자원 요청이 실패할 때 데드락 탐지 알고리즘을 수행하면 데드락을 유발한 스레드를 식별하는데 도움이 됩니다.
● 데드락 회복
○ 단순히 프로세스를 중단시키는 방법이 있습니다. 데드락에 빠진 모든 프로세스를 중단시키거나, 프로세스를 하나 씩 중단시키며 데드락 탐지를 하면서 회복시키는 방법이 있습니다. 단, 프로세스를 강제로 종료하면 시스템 불일치 상태가 발생할 수 있음에 유의해야 합니다.
○자원 선점
① 교착 상태의 프로세스가 가지고 있는 자원을 선점해 다른 프로세스에 주고, 기존 프로세스는 종료시킵니다.
② 최소 비용에 희생자를 선택하여 선점합니다. 이 방식은 롤백(이전에 있단 안전 상태)이 발생하거나 같은 프로세스가
계속 희생하는 기아 상태가 발생할 수 있습니다.
데드락 무시(Deadklock Ignore)
일반적으로 상용 OS 중 일반 유저용은 데드락에 걸리면 그냥 무시합니다. 데드락을 위한 기법을 고민하는 것보다 그냥 유저가 컴퓨터를 껐다 키거나 하는 방식이 비용(cost)가 적기 때문입니다.
하지만 미사일과 같이 데드락을 허용했을 때 엄청나게 비용 피해가 심할 수 있는 분야에서는 데드락을 반드시 막습니다.
결국 방법에 사용 유무는 비용의 차이입니다.
'강의 > OS' 카테고리의 다른 글
OS - 가상 메모리 (0) | 2023.07.22 |
---|---|
OS - 메인메모리(Main Memory) (0) | 2023.07.22 |
OS - 동기화 예시 (0) | 2023.07.17 |
OS - 동기화 툴 (0) | 2023.07.16 |
OS - CPU Scheduling (0) | 2023.07.13 |