TIL 카테고리의 글은 그날 배운 것을 정리하는 목적으로 포스팅합니다. 내용이 잘못되었다면 댓글로 피드백 부탁드립니다.

Deadlock (교착상태)

요청한 자원을 다른 프로세스가 점유하고 있고 점유하고있는 프로세스도 다른 자원에 대해 대기 상태에 있기 때문에 두 프로세스가 대기 상태에서 벗어날 수 없는 상황

시스템 모델

프로세스가 사용하는 자원(resource)에는 어떤 것들이 있을까?

request
use
release

정상적인 프로세스는 다음 순서로만 자원을 사용할 수 있음.

request

프로세스는 자원을 요청하고, 즉시 허용되지 않는 경우 자원을 얻을 때 까지 대기상태에 놓임

use

프로세스는 자원에 대해 작업을 수행함.

release

프로세스가 자원을 다 사용했다면 방출함.

이러한 경쟁 구도에 놓인 프로세스들은 자원을 요청하는 시점에 해당 자원이 다른 프로세스에 의해 점유되어있으면 대기 상태에 놓이고 각 프로세스와 자원들이 서로 꼬리를 물며 자원을 대기하는 경우를 교착상태에 놓여져있다고 함.

교착상태 발생조건

상호배제 mutual exclusion
- 프로그램들이 공유 자원을 동시에 쓸 수 없는 상황
점유 상태로 대기
- 공유 자원을 점유한 상태에서 다른 자원을 기다리는 것
선점 불가
- 자원을 어떤 프로세스가 점유 중일 때 다른 프로세스가 그 자원을 뺏을 수 없는 것
순환성 대기
- 대기가 꼬리에 꼬리를 문 상황

교착상태가 발생하려면 위 4가지 조건이 반드시 성립되어야함.

교착상태 처리방법

교착상태를 예방하거나 회피.
시스템이 교착상태가 되도록 허용한 다음 이를 회복시키는 방법.
시스템의 교착상태를 무시하고 발생하지 않는 것 처럼 꾸미는 방법(실제 OS에서 사용)

교착상태 예방

상호배제 : 읽기 전용 같은 여러 프로세스가 동시에 접근할 수 있는 파일에는 상호배제가 필요하지 않기 때문에 상호배제가 깨어지게 되어 교착상태를 예방할 수 있음. but 공유 불가능한 데이터에서는 교착 상태를 예방하지 못하는 경우가 발생할 수 있음.
점유하며 대기 : 프로세스가 어떤 자원을 점유하고 있을 때 다른 자원을 요청하지 못하도록 보장해야함. 자기 자신이 아무런 자원을 점유하고 있지 않을 때에만 다른 자원을 요청할 수 있어야함.
- 프로토콜 1 : 프로세스가 실행되기 전에 자신이 필요한 모든 자원을 요청하여 할당 받는 것
  - 많은 자원들이 할당 된 후 오랫동안 사용되지 않아 자원의 이용률이 낮아짐.
  - 필요한 자원 중 최소 하나가 계속 다른 프로세스에게 할당되어 있으면 이 프로세스는 무한정 대기해야하는 가능성이 생김.(기아상태)
- 프로토콜 2 : 프로세스가 자원을 전혀 점유하지 않을 때만 자원을 요청할 수 있도록 하는 것
  - 자원을 동시에 사용해서 어떤 작업을 해야할 때, 비효율적인 동작이 나타나 자원의 이용률이 낮아짐
비선점

이미 할당된 자원이 선점되지 않아야 한다는 것
- 어떤 자원을 점유하고있는 프로세스가 즉시 할당할 수 없는 다른 자원을 요청하면 자신이 점유하고 있는 자원을 강제로 방출시켜 다른 프로세스가 선점하게 함으로써 교착상태를 끊어버림.
- 해당 프로세스는 자신이 요청하고 있는 새로운 자원 + 강제로 방출한 옛 자원을 획득해야만 다시 시작됨
순환 대기 : 모든 자원 유형들에게 전체적인 순서를 부여하여 각 프로세스가 순서대로 자원을 요청하도록 강제함. 모든 자원들은 먼저 할당되는 순서가 정해져 있기 때문에 교착상태가 일어날 수 없음.

교착상태 예방 방법은 자원의 낭비가 심함.

교착상태 회피(탐지)

어떤 프로세스가 요청을 할 때 미래에 대한 분석을 통해 나의 요청을 늦추는 방법으로 교착상태를 피할 수 있음.

프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언함.
순환상태가 절대로 있을 수 없게함.

안전상태 Safe State

각 유효 자원의 최대 개수까지 어떤 순서로 요청을 하더라도 교착상태를 야기하지 않고 모두 할당을 잘 해줄 수 있음을 뜻함. 회피 알고리즘은 시스템이 정해진 최대 자원 내에서 시스템이 항상 안전 상태에 있도록 한함.

오직 시스템이 안정상태로 유지될 수 있는 경우에만 즉시 요청을 들어줌.

프로세스가 자원을 요구할 때 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지를 검사하여 교착 상태를 회피함. banker's Algorithm

현재 할당 된 자원의 양(Allocation)을 계산하고 프로세스에게 최대로 할당될 수 있는 자원의 양(MAX)을 계산하고 두 데이터를 통해 추가로 할당해줄 수 있는 자원의 양(Need)을 계산함 (Need=Max-Allocation)
현재 가용할 수 있는 자원의 양(Avaliable)보다 Need 수보다 높으면 할당해주지 않고 요청한 정도가 Need보다 낮더라도 할당해주지 않음. http://asfirstalways.tistory.com/129

교착상태 회복

시스템이 교착상태가 발생하는 것을 허용하고 이를 회복함.

교착상태 회복 방법

한개 이상의 프로세스를 중지
하나 이상의 프로세스들로부터 자원을 선점하는 것

프로세스 종료

교착상태를 해결하기 위해 존재하는 프로세스 하나를 임의로 종료하여 교착 상태를 해결하는 방법

교착 상태 프로세스를 모두 중지
- 교착상태에 가기까지 프로세스들이 진행한 많은 작업들이 중지로 인해 결과가 폐기된다면 다시 계산을 해야하기 때문에 상당히 큰 비용이 들어감
교착 상태가 제거될 때 까지 한 프로세스씩 중지
- 각 프로세스가 중지될 때 마다 아직도 교착 상태에 있는지 매번 살펴봐야하기 때문에 상당한 오버헤드 유발.

자원 선점

교착 상태가 깨어질 때 까지 프로세스로부터 자원을 계속적으로 선점해 다른 프로세스에게 주어야함.

자원 선점 고려 사항

희생자 선택 (selection of a victim)

자원 선점에 앞서 어떤 자원과 어느 프로세스가 선점될 것인가를 고민해야함. 비용을 최소하기 위해서 교착 상태 프로세스가 점유하고 있는 자원의 수, 교착상태 프로세스가 지금까지 실행하는 데 소요한 시간 등을 고려해 희생자를 선택함. minimize cost
롤백 (Rollback)

안전한 상태로 돌아가 해당 상태에 대한 프로세스를 다시 시작

특정 프로세의 자원을 강제로 방출하고 선점했다면 그 프로세스를 어떻게 처리할 것인가의 고민이 필요. 가장 안전한 방법은 프로세스를 중지시키고 재시작하는 것.(롤백)
기아 상태 (starvation)

동일한 프로세스를 항상 희생자로 선택할 수 있음 (평생 실행 X)

계속해서 특정 프로세스의 자원을 강제 방출시켜 선점을 시켜주게 되면 그 프로세스는 계속해서 희생자로 선택될 확률이 높고 그 프로세스는 영원히 실행이 완료되지 못하는 ㅠ_ㅠ 기아 상태에 빠질 수 있음. 그렇기 때문에 프로세스가 한정된 시간에만 희생자로 선정된다는 것을 보장해야함.

refer

Operating System Concepts

[운영체제

교착상태(deadlock)란 무엇인가?](https://frontalnh.github.io/2018/04/05/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-%EA%B5%90%EC%B0%A9%EC%83%81%ED%83%9C-deadlock-%EB%9E%80-%EB%AC%B4%EC%97%87%EC%9D%B8%EA%B0%80/#%EC%8B%9C%EC%8A%A4%ED%85%9C-%EB%AA%A8%EB%8D%B8)

[운영체제] 데드락, 교착상태 해결 (Dead lock)

http://asfirstalways.tistory.com/129