교착 상태(Deadlock)
- 둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상
- Multi processing 환경에서 다수의 프로세스가 특정 자원의 할당을 무한정 기다리고 있는 상태
교착 상태(Deadlock)와 기아(Starvation)
|
교착상태 (Deadlock) |
기아(Starvation) |
정의 |
다수의 프로세스가 아무일도 하지 못하고 특정 사건 무한대기 |
특정 프로세스가 자원을 할당 받기위해 무한정 대기 상태 |
발생 원인 |
상호배제, 점유와 대기, 비선점, 환형 대기 |
자원의 편중된 분배정책 |
해결방안 |
예방, 회피, 발견, 회복 기법 |
Aging 기법 |
( ※ Aging 기법 : 대기 시간 등에 따라 우선순위를 높여줌으로써 기아현상을 해결하는 방법)
교착상태 발생 조건
- 교착상태는 다음 4가지 조건이 모두 성립시에 발생한다.
- 상호배제 (Mutual Exclusion) - 한 시점에 한 프로세스만이 자원을 사용 할 수 있다. 즉 한 프로세스에 의해 점유된 자원을 다른 프로세스들이 접근할 수 없다.
- 점유와 대기 (Hold-and-wait) - 프로세스가 어떤 자원을 할당 받아 점유하고 있으면서 다른 자원을 요구.
- 비선점 (No Preemption) - 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없으며, 점유하고 있는 프로세스 자신만이 해제 가능
- 환형 대기 (Circular wait) - 프로세스들 간에 닫힌 연결(closed chain)이 존재한다. 즉 자원 할당 그래프에서 환형이 만들어지는 것.
교착상태 해결 방안
- 교착상태 예방
교착상태이 발생하기 위한 4가지 필요충분조건 중에 하나를 배제하는 것
- 상호배제 : 상호 배제 조건은 공유 자원의 일관성을 유지하기 위해 반드시 필요하기 때문에, 상호 배제 조건을 없앨 수는 없다.
- 점유와 대기 : 프로세스가 자신이 사용할 모든 자원을 할당 요청하고, 모든 자원을 할당받을 수 있으면 계속 수행, 하나의 자원이라도 할당받을 수 없다면 할당 받지 않은채 대기한다. 이 방법은 가능하지만 자원의 비효율적이다.
- 비선점 : 자원임시 할당해제 및 원상복구, but 비효율적
- 환형 대기 : 자원들의 할당 순서를 정한다. but 환형대기 조건을 없애는 것은 프로세스의 수행 지연과 불필요한 자원 할당 거부를 야기할 수 있다.
- 교착상태 회피
교착상태 회피를 위한 2가지 기법
1. 프로세스 시작 거부
새로운 프로세스와 기존 프로세스들이 요구하는 자원의 개수가 그 자원의 전체 개수보다 적을 경우에 수행을 허용하는 것이다. 이 정책은 최악의 경우, 즉 모든 프로세스들이 동시에 최대 자원을 요구하여 사용함을 가정하고 있으며, 따라서 효율적이지 않다.
2. 자원 할당 거부 (Banker's algorithm)
OS는 자원의 상태를 감시하고, 프로세스는 사전에 자기 작업에서 필요한 자원의 수를 제시한다. OS는 사용자 프로세스로부터 자원의 요청이 있으면 모든 프로세스가 일정기간 내에 성공적으로 종료될 수 있는 안전한 상태인지 면밀하게 분석해서, 안전한 상태를 유지할 수 있는 요구만을 수락, 그 외의 요구는 만족될 때까지 계속 거절.
- 교착상태 발견
- 시스템의 상태를 감시하는 알고리즘을 통하여 교착상태를 검사하는 알고리즘
- 시스템의 자원할당 그래프로 교착상태 검출
- 교착상태 발생 시 자원할당 소거
- 교착상태 회복
- 교착상태에 포함되어 있는 모든 프로세스들을 중지시킴.
- 교착상태에 포함되어 있는 각 프로세스의 수행을 롤백시킴
- 교착상태게 없어질 때까지 교착상태에 포함되어 있는 프로세스들을 하나씩 종료.
- 교착상태가 없어질 때까지 교착상태에 포함되어 있는 자원을 하나씩 선점시킴.
교착상태 해결을 위한 전체 시스템 설계
- 내부 시스템 자원을 순서화
- PCB, 버퍼, Semaphore 등의 자원 순서화
- 사용자 작업에 대한 주기억장치 선점
- 선점은 Paging, Segmentation, Swapping 시스템에서 가장 효율적인 접근법
- 작업이나 작업단계의 자원필요량 산정
- 교체 가능 공간 사전 할당 - 요구된 기억장치를 사전에 할당
'운영체제' 카테고리의 다른 글
| 커널(Kernel), 마이크로 커널&모놀리식 커널 (0) | 2018.08.28 |
|---|---|
| 캐시 메모리(Cache Memory) (0) | 2018.08.28 |
| 세마포어와 뮤텍스 (Semaphores&Mutex) (0) | 2018.08.26 |
| 병행성과 상호배제&상호배제 알고리즘 (0) | 2018.08.26 |
| Thread (0) | 2018.08.24 |