교착(Deadlock)상태 개념
Blocked/Asleep state
프로세스가 특정 이벤트를 기다리는 상태
프로세스가 필요한 자원을 기다리는 상태
Deadlock state
프로세스가 발생 가능성이 없는 이벤트를 기다리는 경우
프로세스가 deadlock 상태에 있음
시스템 내에 deadlock에 빠진 프로세스가 있는 경우
시스템이 deadlock 상태에 있음
2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태
아사 상태 vs 교착 상태
아사 상태: 운영체제가 잘못된 정책을 사용하여 특정 프로세스의 작업이 지연되는 문제
교착 상태: 여러 프로세스가 작업을 진행하다보니 자연 발생적으로 일어나는 문제
교착 상태의 발생
시스템 자원
교착 상태는 다른 프로세스와 공유할 수 없는 자원을 사용할 때 발생
공유 변수
교착 상태는 공유변수를 사용할 때 발생
응용 프로그램
데이터베이스 같은 응용 프로그램에서도 교착 상태 발생
데이터베이스는 데이터의 일관성을 유지하기 위해 잠금을 사용하는데, 이때 교착상태가 발생할 수 있음
자원 할당 그래프
자원 할당 그래프
프로세스가 어떤 자원을 사용 중이고 어떤 자원을 기다리고 있는지를 방향성이 있는 그래프로 표현한 것
프로세스는 원으로, 자원은 사각형으로 표현
다중 자원
여러 프로세스가 하나의 자원을 동시에 사용하는 경우
수용할 수 있는 프로세스 수를 사각형 안에 작은 동그라미로 표현
교착 상태 필요 조건
다음 4가지 조건이 모두 발생해야만 교착상태 발생
상호배제
한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 함
비선점
한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 함
점유와 대기
프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야 함
원형 대기
점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 함
교착 상태 해결 방법
교착 상태 예방(prevention) : 교착 상태를 유발하는 네 가지 조건이 발생하지 않도록 무력화하는 방식으로 교착상태 조건 4가지에 대하여 각각의 방법이 존재 함.
교착 상태 회피(avoidance) : 교착상태가 발생하지 않도록 자원 할당량을 조절하여 교착 상태를 회피하는 방식
교착 상태 검출(detection)과 회복(recovery) : 교착 상태 검출은 어떤 제약을 가하지 않고 자원 할당 그래프를 모니터링하면서 교착 상태가 발생하는지 살펴보는 방식으로 만약 교착 상태가 발생하면 교착 상태 회복 단계가 진행됨
교착 상태 예방
상호 배제 예방
시스템 내에 있는 상호 배타적인 모든 자원, 즉 독점적으로 사용할 수 있는 자원을 없애버리는 방법
현실적으로는 모든 자원을 공유할 수 없으며 상호 배제를 적용하여 보호해야 하는 자원이 있음
상호 배제를 무력화하는 것은 사실상 어려움
비선점 예방
모든 자원을 빼앗을 수 있도록 만드는 방법
그러나 아사 현상을 일으켜 비선점 조건을 무력화하기는 어려움
점유와 대기 예방
프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하는 방법
‘전부 할당하거나 아니면 아예 할당하지 않는’ 방식을 적용
자원이 아닌 프로세스의 자원 사용 방식을 변화시켜 교착 상태를 처리한다는 점에서 의미가 있음
단점
프로세스가 자신이 사용하는 모든 자원을 자세히 알기 어려움
자원의 활용성이 떨어짐
많은 자원을 사용하는 프로세스가 적은 자원을 사용하는 프로세스보다 불리함
결국 일괄 작업 방식으로 동작
원형 대기 예방
점유와 대기를 하는 프로세스들이 원형을 이루지 못하도록 막는 방법
모든 자원에 숫자를 부여하고 숫자가 큰 방향으로만 자원을 할당하는 것
단점
프로세스 작업 진행에 유연성이 떨어짐
자원의 번호를 어떻게 부여할 것인지가 문제
교착 상태 예방 정리
교착 상태를 유발하는 네 가지 조건이 일어나지 않도록 제약을 가하는 방법
자원을 보호하기 위해 상호 배제와 비선점을 예방하기 어려움
점유와 대기, 원형 대기는 프로세스 작업 방식을 제한하고 자원을 낭비하기 때문에 사용할 수 없음
교착 상태 회피
교착 상태 회피 개념
프로세스에 자원을 할당할 때 어느 수준 이상의 자원을 나누어주면 교착 상태가 발생하는지 파악하여 그 수준 이하로 자원을 나누어주는 방법
교착 상태가 발생하지 않는 범위 내에서만 자원을 할당하고, 교착 상태가 발생하는 범위에 있으면 프로세스를 대기시킴
즉, 할당되는 자원의 수를 조절하요 교착 상태를 피함
안정 상태와 불안정 상태
교착 상태 회피는 자원의 총수와 현재 할당된 자원의 수를 기준으로 시스템을 안정 상태(safe state)와 불안정 상태(unsafe state)로 나누고 시스템이 안정 상태를 유지하도록 자원을 할당
할당된 자원이 적으면 안정 상태가 크고, 할당된 자원이 늘어날수록 불안정 상태가 커짐
교착 상태는 불안정 상태의 일부분이며, 불안정 상태가 커질수록 교착 상태가 발생할 가능성이 높아짐
교착 상태 회피는 안정 상태를 유지할 수 있는 범위 내에서 자원을 할당함 으로써 교착 상태를 피함
교착 상태 회피의 문제점
프로세스가 자신이 사용할 모든 자원을 미리 선언해야 함
시스템의 전체 자원 수가 고정적이어야 함
자원이 낭비됨
교착 상태 검출
교착 상태 검출의 개념
운영체제가 프로세스의 작업을 관찰하면서 교착 상태 발생 여부를 계속 주시하는 방식
교착 상태가 발견되면 이를 해결하기 위해 교착 상태 회복 단계를 밟음
타임아웃을 이용한 교착 상태 검출
일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여 처리하는 방법
교착 상태가 자주 발생하지 않을 것이라는 가정하에 사용하는 것으로, 특별한 알고리즘이 없어 쉽게 구현할 수 있음
타임아웃이 되면 프로세스가 종료됨
타임아웃 예)
데이터베이스에서 타임아웃의 문제
데이터베이스에서 타임아웃으로 프로세스가 종료되면 일부 데이터의 일관성이 깨질 수 있음
데이터의 일관성이 깨지는 문제를 해결하기 위해 체크포인트와 롤백 사용
체크포인트: 작업을 하다가 문제가 발생하면 저장된 상태로 돌아오기 위한 표시
롤백: 작업을 하다가 문제가 발생하여 과거의 체크포인트로 되돌아가는 것
자원 할당 그래프를 이용한 교착 상태 검출
단일 자원을 사용하는 경우 자원 할당 그래프에 사이클이 있으면 교착 상태
교착 상태 회복
교착 상태 회복
교착 상태가 검출된 후 교착 상태를 푸는 후속 작업을 하는 것
교착 상태 회복 단계에서는 교착 상태를 유발한 프로세스를 강제로 종료
프로세스를 강제로 종료하는 방법
1. 교착 상태를 일으킨 모든 프로세스를 동시에 종료
2. 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료
[참고]
https://drive.google.com/file/d/1jiY1Vivb-J21NKfFRf9S9XJLUEqu3PrD/view
Beginner_Developer