Deadlock
일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상을 교착 상태(deadlock)이라고 한다. 만약 프로세스 A는 자원 a를 점유한 채 자원 b를 기다리고, 프로세스 B는 자원 b를 점유한 채 자원 a를 기다리는 상대방이 가진 자원을 기다리기만하다가 실행 한번 못하는 상황을 말한다.
자원할당그래프(Resource Allocation Graph)
교착 상태를 표현하는 방법으로, 어떤 프로세스가 어떤 자원을 사용하고 기다리는지를 표현하는 그래프이다. 프로세스는 원으로, 자원의 종류는 사각형으로 표현하며, 사용할 수 있는 자원의 개수는 사각형 내에 점으로 표현한다. 프로세스가 어떤 자원을 할당받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시하고, 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시한다.
필요조건 4가지
상호배제: 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 경우
점유와 대기: 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 경우
비선점: 해당 자원을 이용하는 프로세스의 작업이 끝나아만 비로소 이용할 수 있는, 다른 프로세스의 자원을 강제로 빼앗지 못하는 경우
원형 대기: 자원 할당 그래프에서 프로세스들과 자원이 원의 형태를 이루는 경우\
예방
교착 상태 발생 필요 조건 4가지 중 하나를 충족하지 못하게 하는 방식
상호 배제를 없애는 경우: 모든 자원을 공유 가능하게 만듬 -> 이론적으로만 가능하며 현실적으로 무리
점유와 대기를 없애는 경우: 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분함 -> 자원의 활용률이 낮아질 우려, 자원을 많이 사용하는 프로세스는 적게 사용하는 프로세스에 비해 동시에 자원을 사용할 타이밍을 확보하기 어려움
비선점 조건을 없애는 경우: 이용 중인 프로세스로부터 해당 자원을 빼앗을 수 있게 만듬 -> 모든 자원이 선점 가능한 것이 아니므로 범용성이 떨어짐
원형 대기 조건을 없애는 경우: 모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당(=식사하는 철학자 문제에서 원형 식탁이 아닌 사각형 식탁에서 일렬로 앉아 식사하는 상황) -> 수많은 자원에 번호를 붙이는 일은 어려우며, 각 자원에 어떤 번호를 붙이는지에 따라 자원의 활용률이 떨어질 수 있음
교착 상태의 발생 조건을 원천적으로 제거하여 교착 상태를 사전에 방지하는 예방 방식은 교착 상태가 발생하지 않음을 보장할 수는 있지만 여러 부작용이 발생!
회피
교착 상태가 발생하지 않을 정도로만 조심하게 자원을 할당하는 방식
안전 순서열(safe sequence): 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
안전 상태(safe state): 교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태(안전 순서열대로 프로세스에 자원을 배분하여 교착 상태가 발생하지 않음)
불안전 상태(unsafe state): 교착 상태가 발생할 수도 있는 상황(안전 순서열이 없음)
Banker’s Algorithm: allocation, max, needs, available한 자원의 개수를 표로 나타내고, 가능한 프로세스 먼저 완료해 안전한 상태로 만들어주는 것이다. 모든 프로세스가 안전 상태로 완료되면 교착 상태가 발생하지 않으며, 불안전 상태가 있다면 교착 상태가 발생한다.
회복
예방과 회피는 교착 상태 발생을 막기 위한 노력이라면, 이는 교착 상태 발생을 인정하고 사후에 조치하는 방식
선점을 통한 회복: 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식
프로세스 강제 종료를 통한 회복: 교착 상태에 놓인 프로세스를 모두 강제 종료할 수 있고(프로세스들 작업 내용 잃음), 교착 상태가 없어질 때까지 한 프로세스씩 강제 종료할 수도 있음(오버헤드 문제 발생)
Last updated