교착상태 Deadlock

https://www.inflearn.com/course/%ED%98%BC%EC%9E%90-%EA%B3%B5%EB%B6%80%ED%95%98%EB%8A%94-%EC%BB%B4%ED%93%A8%ED%84%B0%EA%B5%AC%EC%A1%B0-%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C/dashboard

[지금 무료] 개발자를 위한 컴퓨터공학 1: 혼자 공부하는 컴퓨터구조 + 운영체제 강의 - 인프런

교착상태란 Deadlock?

프로세스들이 실행이 되려면 자원이 필요한데 두 개 이상의 프로세스들이 필요한 자원들을 기다리기만 한다면 어떤 프로세스도 실행되지 못하고 멈춘다. 

상대방이 끝나기만을 기다리는 것.

무한대로 진입이 연기되는, 대기하는 프로세스 아무도 진입하지 못하는 상황

 

 식사하는 철학자 문제

한 두명만 식사하면 식사가 가능하다. 하지만 모두 먹는다면 식사가 불가능하다.

철학자는 프로세스 혹은 스레드, 포크는 필요 자원, 식사는 실행하는 것

 

서로 점거하고 있는 자원을 서로 기다리는 경우 그 어떤 스레드나 프로세스도 끝까지 실행될 수 없다.

 

서로 상대의 자원을 기다리다가 무한정 대기 상태에 빠진다.

 

교착 상태를 해결하기 위해선 :

1. 교착 상태가 발생했을 때의 상황을 정확히 표현해본다

2. 교착 상태가 일어나는 근본적인 이유를 이해한다.

 

교착 상태가 일어나는 상황을 표현하기 위해서

자원 할당 그래프 를 작성한다.

자원 할당 그래프는 교착 상태 발생 조건 파악이 가능하고, 어떤 프로세스가 어떤 자원을 할당 받아 사용 중인지 확인 가능하다. 그리고 어떤 프로세스가 어떤 자원을 기다리고 있는지 확인이 가능하다. 

자원은 여러개가 될 수 있다.

cpu는 a,b로부터 자원을 받아 사용중이다.

프로세스 d는 cpu를 할당받기 위해 기다리는 중이다.

ssd는 3개, cpu는 2개, 

a는 ssd를 할당받아 사용중. 

b, c는 cpu를 할당받아 사용중

d는 프린터를 할당받아 사용 중.

e는 프린터 할당을 기다리는 중

f는 cpu할당을 기다리는 중.

 

자원할당그래프를 사용하면 교착상태가 왜 발생하는지 대략적으로 파악할 수 있다.

교착상태가 발생한 그래프의 특징:  그래프가 원의 형태를 띄고 있다

모든 원 형태의 그래프가 원 형태를 띄는 것은 아니지만, 교착 상태는 원의 형태이다.

 

 

 교착 상태가 발생하는 근본적인 이유:

 

1. 상호배제 : 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태

2. 점유와 대기: 자원을 할당 받은 상태에서 또 다른 자원을 할당 받기를 기다리는 상태

3. 비선점 : 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 형태

4.원형대기 : 프로세스들이 원의 형태로 자원을 대기하는 상태

 

위 네가지 조건 중 하나라도 만족하지 않으면 교착 상태가 발생하지 않는다.

위 네가지 조건을 모두 만족하면 교착 상태가 발생할 수 있다.

 

 교착 상태 해결 방법 : 예방, 회피, 검출 후 회복

예방 : 애초에 발생하지 않게, 교착상태 발생 조건 ( 상호배제, 점유와 대기, 비선점, 원형대기) 중 하나를 없앤다. 교착 상태가 발생하지 않음은 보장하지만 부작용이 따른다.

 

예방방법(위 조건을 없애는 방법)

 

상호배제: 모든 자원을 공유하게 만든다. 현실적인 방법은 아니다.

 

점유와 대기: 특정 프로세스에게 자원을 모두 할당하거나 아예 할당하지 않는 방식

   ex) 철학자들에게 기다릴 거면 왼쪽 포크를 놓고 기다려달라고 부탁.

이론적으론 교착 상태를 아예 발생시키지 않을 수 있다.

  단점 : 자원의 낭비, 활용도 저하, 지금 당장 자원이 필요한데 할당 받지 못할 수 있다. 할당을 받지 못하면서 오랫동안 대기해야하는 프로세스가 있을 수도 있다. 모두 할당을 했는데 사용하지 않을 수도 있다.

 

비선점 조건: 한 프로세스가 다른 프로세스의 자원을 빼앗을 수 있게 만들면 교착 상태는 발생하지 않는다.

   선점이 가능한 자원 (cpu, e.g)에 한해 효과적이다. 모든 자원이 선점 가능한 것은 아니라 범용적인 방법은 아니다.

 

원형대기: 모든 자원에 번호를 붙여 그 번호의 오름차순대로 자원을 할당하면 원형대기가 발생하지 않는다

   단점: 모든 자원에 번호를 부여하는 것은 어려운 작업이다. 번호에 따라 활용률이 달라진다. 많이 활용되는 자원에 낮은 번호가 붙는다면? 자주 쓰이지 않는 자원인데 높은 자원을 할당 받았다면?

사장 현실적인 방법이지만 이러한 단점이 있다.

 

 

 회피 : 

교착 상태를 무분별한 자원 할당으로 인해 발생했다고 간주, 교착 상태가 발생하지 않을만큼만 할당하기.

배분할 수 있는 자원의 양을 고려해 교착 상태가 발생하지 않을 만큼만 자원 배분

 

안전 순서열: 교착 상태 없이 안전하게 프로세스들이 자원을 할당할 수 있는 순서. 할당 순서를 조절한다.

안전 상태: 교착 상태 없이 모든 프로세스가 자원을 할당 받고 종료될 수 있는 상태. 안전 순서열이 없는 상태.

불안전 상태 : 교착 상태가 발생할 수도 있는 상태. 안전 순서열이 없는 상태

 

 

 교착 상태 검출 후 회복

교착 상태의 발생을 인정하고, 사후에 조치하는 방식

프로세스가 자원을 요구하면 일단 할당, 교착 상태가 검출되면 회복

선점을 통한 회복, 프로세스 강제 종료를 위한 회복

 

선점을 위한 회복: 교착 상태가 해결될 때까지 한 프로세스 씩 자원을 몰아주는 형식

프로세스 강제 종료를 통한 회복 : 교착 상태에 놓인 프로세스를 모두 강제 종료 -> 가장 확실하지만 작업 내역을 잃을 가능성이 있다.

교착 상태가 해결될 때까지 한 프로세스씩 강제 종료 : 교착 상태가 해결됐나 계속 봐야해 오버헤드 발생. 하지만 잃는 내역을 최소화할 수 있다.

 

교착 상태를 무시하는 타조 알고리즘도 있다.