교착 상태 (추후 추가 필요)

교착 상태

컴퓨터에는 한정적인 자원이 있고 프로세스가 이를 서로 경쟁할 수 있다. 한프로세스가 자원을 요청했을 때 사용하지 못하는 상황이 발생할 수 있다. 이처럼 계속해서 대기중이며 다시는 실행될 수 없는 프로세스의 상태를 교착상태라고 한다.  시스템은 경쟁하는 프로세들 사이에 분배되어야 할 유한한 수의 자원들로 구성된다. 자원 타입들은 CPU 주기, 파일, 입출력 장치 등이 있다. 이러한 자원들은 프로세스는 아래와 같은 순서로 진행한다. 

 

 

요청 -> 사용 -> 방출

 

요청: 프로세스는 자원을 요청한다. 

 

사용: 프로세스는 자원에 대해 작업을 수행할 수 있다. 

 

방출: 프로세스가 자원을 방출한다. 

 

이러한 예로는 장치의 request()와 release(), 파일 open(), close()와 메모리 allocate(), free() 시스템 호출이 있다. 

 

교착 상태의 특징

교착상태의 프로세스는 다시는 실행될 수 없으며 시스템 자원이 묶여있기 때문에 다른 작업을 시작하는 것도 불가능하다. 교착 상태는 아래의 네 가지 조건이 동시에 성립될 때 발생한다. 

 

1. 상호배제
   
   최소한 하나의 자원이 비공유 모드로 점유되어야 한다. 다른 프로세스가 자원을 이용하고 있으면 그 자원이 방출될 때까지 기다려야한다. 
   
   
2. 점유하며 대기
   
   프로세스는 최소한 하나의 자원을 점유한 채, 현재 다른 프로세스에 의해 점유된 자원을 추라고 얻기 위해 반드시 대기해야한다. 
   
   
3. 비선점
   
   자원을 선점할 수 없어야한다. 즉 뺐을 수 없어야한다. 
   
   
4. 순환 대기
   
   {P0, P1, P2, P3....}의 프로세스가 있다면 P0은 P1이 점유한 자원을 기다리고 P1은 P2가 점유한 자원을 기다리고 줄줄이 소세지 처럼 계속해서 대기한다. 

자원 할당 그래프

자원 할당 그래프

프로세스가 자원을 요청하는 P -> R은 요청 간선이다. 할당 간선은 R -> P이다. 

 

만일 그래프가 사이클을 포함하지 않으면 시스템 내 어느 프로세스도 교착상태가 아니라는 것을 볼 수 있다. 

교착 상태 예방

네가지 상황중 하나를 제거해서 예방합니다. 자원의 낭비가 심합니다. 

1. 상호 배제
   
   공유가능한 자원들을 만들어서 프로세스가 가져올 수 있게 만든다. 하지만 근본적으로 공유가 불가능한 자원들이 존재하기 때문에 완벽한 예방은 불가능하다. 
   
   
2. 점유하며 대기
   
   각 프로세스가 실행되기 전에 자신의 모든 자원을 요청하고 할당받을 것을 요구한다. 이는 다른 프로세스가 사용할 수 없고 다 가져갈 수 없다. 중간에 필요 없어져도 일단은 가져간다. 
   
   
3. 비선점
   
   자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 점유하고 있는 자원을 반납하고 필요한 자원을 받기 위해 대기한다. 
4. 순환 대기
   
   자원에 고유한 번호를 할당하고 번호 순서대로 자원을 요구할 수 있도록 만듬. 

 

교착 상태 회피

위의 교착상태를 예방할 때 가장 큰 문재는 장치의 이용률이 저하되고 처리율이 감소된다는 점이다. 

안전 상태

현재 시스템이 안전하다는 의미는 어떤 순서로든 프로세스가 자원을 요청해도 교착상태를 야기시키지 않고 처리할 수 있다는 의미이다. 하지만 이렇게 모두 안전하게 처리할 수 있는 순서가 없다는 것은 불안전하다고 한다. 즉 시스템이 불안정하다는 뜻은 앞으로 교착상태로 가게 될 수도 있다는 의미이다. 

 

자원 할당 그래프 알고리즘

사이클 탐지 알고리즘을 이용해 안전성을 검사한 후 사이클이 생기지 않으면 자원을 할당해준다. 

 

교착 상태 회복

교착 상태를 깨버리는 데는 두가지 방법이 잇다. 1. 순환 대기를 깨뜨리기위해 프로세스를 중지시킨다.  2. 교착 상태에 있는 프로세스에 자원을 선점하게 만들어준다. 

 

1-1. 교착상태 프로세스를 모두 종료

 

확실하게 교착상태를 종료하지만 모든 프로세스들이 종료되기때문에 비용이 크다. 왜냐하면 이들 프로세스들이 오랫동안 연산했을 가능성이 있기 때문이다. 종료 후 다시 처음부터 시작해야 할 것이다. 

 

1-2. 교착상태가 종료될 때 까지 한개씩 종료

 

이 방법은 각 프로세스가 중지될 때마다 교착상태 탐지 알고리즘을 호출해 프로세스들이 아직도 교착상태에 있는지 확인하기 때문에 상당히 오버헤드가 크다. 

 

자원 선점

1. 희생자 선택

어느 자원과 어느 프로세스들이 선점될 것인지 비용을 최소하 하며 결정해야한다. 

 

2. 후퇴(Roll Back)

 

실행되지 못하는 프로세스는 자원이 없기 때문에 안전한 상태로 후퇴시키고, 그 상태로부터 다시 시작해야한다.