개념
- 프로세스는 실행을 위해 CPU, 메모리, 파일 등 여러 하드웨어 자원이 필요
- 운영체제는 프로세스가 요구하는 자원을 적절하게 배분
- 프로세스가 자원을 요청 했을 때 해당 자원을 사용할 수 없는 상황이 발생하면 프로세스가 대기상태로 변경
- 대기 상태의 프로세스들이 실행 상태로 변경될 수 없는 상황을 데드락(Deadlock, 교착상태)라고 부름
- 한번 교착상태에 빠지면 프로세스가 무한 루프에 빠져 수행하지 못하고 해당 프로세스가 가지고 있는 자원에 대해 아무도 사용하지 못하게 되므로 전체 컴퓨터 환경에 매우 치명적인 문제가 됨
교착상태의 필요조건
개요
- 교착상태가 발생하기 위한 필요 조건 4가지 존재
- 필요조건이기 때문에 4가지 모두 해당한다고 반드시 교착상태가 일어나는 것은 아님
- 4가지 조건에 해당할 때 교착상태가 발생할 확률이 생김
필요조건
상호배타(Mutual exclusion)
- 한 프로세스가 자원을 사용하고 있다면 다른 프로세스는 해당 자원을 사용하지 못함
- 공유 불가능한 자원의 동시 사용을 피하기 위해 특정 알고리즘 사용
- 데커의 알고리즘, 피터슨의 알고리즘, 램퍼드의 베이커리 알고리즘 등
- 공유 불가능한 자원이란 프로그램 간의 통신에 사용되는 비트 단위의 플래그, 계수기, 큐 등의 자원을 의미
보유 및 대기(Hold and wait)
- 한 프로세스가 자원을 점유한 상태에서 다른 프로세스에 할당되어 있는 자원을 추가로 점유하기 위해 대기하는 경우
비선점(No Preemption)
- 다른 프로세스에 할당된 자원은 사용이 끝날 때 까지 강제로 빼앗을 수 없음
- 비선점 스케줄링 방식 사용때 발생
- 프로세스는 자원을 스스로 반납할 때까지 자원 사용 불가능
필요충분조건
환형대기(순환대기, Circular wait)
- 점유 대기 조건과 비선점 조건 만족 시 순환대기 조건 발생
- 교착상태의 경우 무조건 환형대기 상태를 만족하게 된다
- 프로세스가 요구하는 자원의 방향이 원형을 이루는 경우
- 대기중인 프로세스 집합에서 순환 형태로 자원을 대기하는 경우
교착상태 처리
교착상태 방지(Deadlock Prevention)
개요
- 교착상태를 방지하기 위해서 필요조건 4가지 중 최소 한가지를 만족 시키지 않도록 만드는 것
- 가장 현실적인 방법은 보유 및 대기나 환형대기의 조건을 방지하는 것이나 두 방법 모두 자원를 비효율적으로 사용하게 됨
- 군사, 우주, 의료 산업과 같은 크리티컬한 곳에서 사용
상호배타
- 자원을 공유가능하게 하여 상호배타 문제 해결
- 현실적으로 불가능한 경우가 많음
보유 및 대기
- 프로세스가 자원을 가지고 있는 상태에서 다른 자원을 기다리느라 대기상태에 빠지지 않도록 함
- 여러개의 자원이 필요한 프로세스는 필요한 모든 자원을 얻을 수 있는 경우에만 해당 자원들에 대해 요청할 수 있도록 처리
- 필요한 자원 중 일부만 가지고 있는 경우 할당 받은 자원을 모두 운영체제에 반납하도록 처리
- 자원의 활용률을 저하시키고 Starvation 현상이 발생
- 프로세스가 요구하는 자원을 파악하는 비용, 자원에 대한 내용을 저장하고 복원하는 비용 발생
- 무한 대기 문제 발생
※ 기아 상태(Starvation)
- 특정 프로세스의 우선순위가 낮아 원하는 자원을 계속 할당 받지 못하는 상태
- 여러 프로세스가 부족한 자원을 점유하기 위해 경쟁할 때 특정 프로세스는 영원히 자원할당이 안되는 경우
- SJF 나 SRT, 우선순위 스케줄링 등 우선순위와 관련 있는 스케줄링 기법 사용 시 기아 상태 발생 가능
- 우선순위를 계속해서 변경해 모든 프로세스가 높은 우선순위를 가질 수 있는 기회를 제공하여 해결 가능
- 오래 기다린 프로세스의 우선순위를 높이는 기법으로 해결 가능(aging 기법)
- 우선 순위가 아닌 요청 순서대로 처리하는 FIFO 기반 요청 큐 사용으로 해결 가능
비선점
- 선점이 가능하도록 처리
- 자원을 점유중인 프로세스가 다른 자원을 요구할 때 자신이 가진 자원을 반납하도록 처리
- 대부분의 자원에서는 불가능한 방식
환형대기(순환대기)
- 대표적인 예시로 모든 자원에 번호를 부여해 번호에 대한 오름차순으로 자원 요청하는 방식
- 자원의 활용률을 저하시키는 단점
교착상태 회피(Deadlock Avoidance)
개요
- 교착상태에 대해 교착상태 방지와는 다른 시점으로 접근
- 교착상태 회피에서는 교착상태를 자원 요청에 대한 잘못된 승인으로 판단
- 대표적인 교착상태 회피 기법 → 은행원 알고리즘
은행원 알고리즘
- 운영체제는 안전상태를 유지할 수 있는 요청만 수락
- 불안전상태를 초래할 사용자의 요청은 안전상태를 유지할 수 있을 때까지 거절
- 은행원 알고리즘의 단점
- 할당할수 있는 자원 수가 일정해야함
- 사용자 수가 일정해야함
- 불안전상태를 방지해야하기 때문에 자원 이용도가 낮음
- 최대 자원 요구량을 미리 알아야함
- 프로세스들이 유한한 시간안에 자원을 반납해야함
- 은행원 알고리즘은 매우 복잡하고 최대 자원 요구량을 미리 알아야 하기 때문에 현재 채택하는 방식이 아님
※ 안전상태
- 교착상태에 빠지지 않으면서 프로세스가 요구한 최대 요구량 만큼 필요한 자원을 할당 해줄 수 있는 상태
- 안전순서열이 존재하는 상태
※ 불안전상태
- 안전 순서열이 존재하지 않는 상태
- 교착상태는 불안전상태에서만 발생 가능
※ 안전 순서열
- 자원을 순서대로 주고 받을 수 있는 순서
교착상태 검출 및 복구(Deadlock Detection & Recovery)
개요
- 교착상태가 발생하는 것을 허용
- 교착상태 발생 시 이를 인식하고 복구
- 교착상태 발생을 감지하기 위해 운영체제 내부에서 주기적으로 교착상태 발생 여부 검사
- 검사 주기가 짧으면 오버헤드가 커지고 길어지면 오버헤드는 줄어들지만 복구 가능성이 낮아짐
복구 방식
- 교착상태가 발생하는지 주기적으로 검사
- 메모리 상태를 주기적으로 메모리에 저장
- 교착상태 발생 시 메모리에 저장된 메모리 상태를 바탕으로 복구 시작
- 그 외 일부 프로세스 강제 종료, 자원을 강제로 선점해 프로세스에 할당해주는 방식 존재
단점
- 복구가 제대로 이루어 지지 않는 경우 존재
- 검출을 위해서 추가적인 오버헤드 발생
교착상태 무시
개요
- 교착상태는 매우 드문 상황이기 때문에 이를 위해 오버헤드를 감수하는 것은 비효율적
- 교착상태에 대한 아무런 조치를 하지 않는 방식
- 현재 채택되는 방식
식사하는 철학자 문제
개요
- 5명의 철학자가 원탁에 앉아서 식사
- 철학자 사이에는 포크가 하나씩 위치
- 철학자들의 식사과정
- 왼쪽 포크가 사용 가능할 때까지 대기(사용 가능하다면 잡기)
- 오른쪽 포크가 사용 가능할 때까지 대기(사용 가능하다면 잡기)
- 양쪽 포크를 잡으면 일정 시간 만큼 식사 시작
- 오른쪽 포크 내려 놓기
- 왼쪽 포크 내려놓기
- 1번 행동부터 7번 행동까지 반복
- 일정 시간 생각
- 모든 철학자들이 왼쪽 포크를 잡는 다면 오른쪽 포크가 사용 가능해 질 때까지 대기하므로 계속해서 3번 상태에서 더이상 진행할 수 없게 되어 교착상태에 빠지게 됨
해결방안 1
- 왼쪽 포크와 오른쪽 포크를 동시에 들을 수 있을 때가 아니면 포크를 모두 내려놓기
- 모든 철학자가 왼쪽 포크를 들었을 때 남는 포크가 없기 때문에 내려놓고 다시 왼쪽 포크를 드는 행위를 반복
- 계속해서 반복하는 행위만 발생하기 때문에 결국 기아문제 발생
해결방안 2
- 왼쪽 포크를 잡고 나서 오른쪽 포크를 확인한 뒤 오른쪽 포크가 없다면 모든 포크를 내려 놓고 랜덤한 시간동안 기다린 후 다시 왼쪽포크와 오른쪽 포크를 확인하기
- 모두가 동시에 왼쪽 포크를 집는다고 하더라도 서로 대기하는 시간이 다르기 때문에 식사가 가능
- 낮은 확률로 기아문제가 발생할 수 있어 원자력 발전소나 비행기의 프로그램 처럼 완벽을 요구하는 프로그램에는 부적합
해결방안 3
- 이진 세마포어(mutex)를 사용하여 임계구역 설정
- 포크를 들어 식사를 하기 위해서는 mutex의 제어를 받게 되어 같은 시간대에 한 철학자만이 포크를 들 수 있음
- mutex를 사용해 임계구역 설정 시 하나의 철학자가 임계구역에 있다면 다른 철학자들은 모두 임계구역 밖에서 대기
- 포크가 5개이기 때문에 다른 철학자 한명도 식사가 가능하지만 임계구역에 철학자가 들어가 있기 때문에 식사 불가능
- mutex 외에 프로세스 별로 세마포어를 따로 두어 최대한 많은 사람들이 식사가 가능하도록 설계
참고자료
[운영체제]교착상태 처리방법(Handling deadlocks) 예방법, 해결방안
'CS > 운영체제' 카테고리의 다른 글
| Interrupt (0) | 2022.09.20 |
|---|---|
| PCB와 Context Switching (0) | 2022.09.20 |
| 페이지 교체 알고리즘 (0) | 2022.09.20 |
| Memory (1) | 2022.09.20 |
| Monitor (0) | 2022.09.20 |