7장 교착 상태

 

교착 상태

자원을 소유한 스레드들 사이에서  다른 스레드가 소유한 자원을 요청하여 모든 스레드가 무한정 대기하는 현상이다. 

공유 자원에 대한 동기화 문제중 하나이다.

교착상태는 단일 cpu 환경과 멀티 코어 환경 모두에서 발생 할 수 있는 문제다. 

 

교착상태는 사용자 응용프로그램 내에서 주로 발생한다. 커널은 교착상태를 고려하여 매우 정교하게 잘 작성되어있지만 사용자가 작성한 프로그램은 그렇지 않기 때문이다.  하지만 교착상태를 막도록 운영하는 컴퓨터 시스템은 거의 없다. 

교착상태를 막기 위해서는 많은 시간과 비용이 들기 때문이다. 

 

 

교착 상태 유발 요인 

• 자원
  멀티스레드가 자원을 동시에 사용하려는 충돌에서 발생 

 

• 자원과 스레드 
  스레드가 실행되는 동안 한 개의 자원만 필요한 경우 교착상태가 발생하지 않는다. 하지만 여러 자원을 동시에 소유한채 실행되어야하는 경우 교착 상태가 발생할 수 있다. 

 

• 자원과 운영체제
  자원은 반드시 운영체제에게 할당 받는다. 여러개의 자원이 필요하더라도 한번에 한개씩만 할당 받을 수 있다. 
  만일 스레드가 운영체제로부터 필요한 자원을 한번에 모두 할당 받는다면 교착상태가 발생하지 않을 수도 있다. 

 

• 자원 비선점 
  할당된 자원은 운영체제가 강제로 뻿지 못한다. 만약 강제로 빼앗아 기다리는 스레드에게 줄 수 있다면 교착상태가 발생하지 않는다. 

 

 

교착 상태 모델링

컴퓨터 시스템은 자원 할당 그래프를 이용하여 교착상태를 알아낼 수 있다. 

자원 할당 그래프란 컴퓨터 시스템에 존재하는 자원과 스레드들의 상태를 방향성 그래프로 나타낸것이다.

• 꼭짓점 - 스레드는 원, 자원은 사각형
• 간선 - 할당간선과 요청간선 

 

 

이미지 출처: https://unnokid.github.io/Avoidance/

 

 

 

스레드들이 교착상태에 빠지면 아래와 같이 환형고리가 나타난다. 

 

이미지 출처: https://jongone.com/posts/dead-lock/

 

 

컴퓨터 시스템이 작동하는 동안 계속 자원 할당 그래프를 유지 갱신한다면, 자원 할당 그래프를 검사하여 교착 상태를 발견하거나 교착 상태에 빠진 자원과 스레드들을 알아낼 수 있다. 

 

 

 

 

교착상태 해결방법

코프만 조건 

코프만은  교착상태를 유발 할 수 있는 4가지 필요충분 조건을 제시하였다. 이 4가지 조건이 모두 충족되는 환경에서는 교착상태가 발생할 가능성이 있다는 것이다. 

•  상호배제 - 자원은 한 번에 한 스레드에게만 할당 
• 소유하면서 대기 - 스레드가 자원을 소유하면서 대기 
• 강제 자원 반환 불가 - 할당된 자원은 강제로 빼앗지 못함 
• 환형 대기 - 자원을 소유하면서 다른 자원을 요청하는 환형 고리 

 

달리 말하면, 4가지 조건 중에서 한가지라도 만족하지 않는다면 교착 상태가 일어나지 않는다는 것이다.

 

 

교착 상태를 해결하는 방법에는 4가지가 있다. 

• 교착 상태 예방
• 교착 상태 회피
• 교착 상태 감지 및 복구
• 교착 상태 무시 

 

 

교착 상태 예방

교착 상태 예방은 애초에 교착 상태가 발생하지 못하도록, 코프만 조건 중 1개 이상을 만족 하지 못하도록  시스템을 설계하는 것이다. 

 

• 상호배제 없애기
  자원이 한 스레드에게 독점되는 것을 막는다는 것인데 이는 근본적으로 불가능하다. 

 

• 소유하면서 대기 → 기다리지 않게, 모 아니면 도 전략  
  스레드가 자원을 소유하면서 다른 자원을 요청하여 대기하는 상황이 발생하지 않으려면, 처음부터 모든 자원을 소유하고 있으면 된다. 
  필요한 자원을 한번에 할당 받지 못하는 경우 모든 자원이 준비 될때까지 스레드의 실행을 중지시킨다. 
  또는 자원을 소유한 상태에서 새로운 자원이 필요하게 된다면, 현재 가지고 있는 자원을 반환하고 필요한 자원을 한꺼번에 모두 요청하는 방법이 있다. 

 

• 자원 강제 반환 불가 →  자원의 선점을 허용
  한 스레드에게 할당해준 자원을 운영체제가 강제로 빼앗을 수 있도록 한다. 이 경우, 빼앗긴 자원은 빼앗기기 전의 상태로 돌아갈 수 있도록 상태를 관리할 필요가 있다. 

 

• 환형 대기 →  환형 대기 제거
  모든 자원에 번호를 매기고, 반드시 번호순으로 자원을 할당받게 하는 방법이다. 

 

 

 

교착 상태 회피

교착 상태 회피는 시스템적으로는 교착 상태가 발생할 가능성이 있지만, 자원을 할당하기 전 교착 상태에 빠지지 않을 것이라는 확신이 있을때 만 자원을 할당하도록 하는 방법이다. 대표적인 알고리즘으로 은행원 알고리즘이 있다. 

 

이 알고리즘을 사용하기 위해서는 각 스레드가 실행 전 필요한 자원의 개수를 운영체제에게 모두 알려야하는데, 실행 전에 필요한것을 모두 아는 것은 사실상 불가능하므로 비현실적인 알고리즘이다. 또한 자원을 할당할때마다 교착 상태 가능성을 점검해야하므로 시스템의 성능을 많이 저하시킨다. 

 

교착 상태 감지 및 복구 

교착 상태에 대하여 예방이나 회피를 하지 않고, 운영체제가 교착상태를 감지하는 별도의 프로세스를 백그라운드에서 실행하여 교착 상태가 발견되면 그때 적절한 조치를 취하는 방법이다. 교착 상태를 감지하는 작업이 주기적으로 실행되어야하므로 이 또한 시스템에 많은 부담이 된다. 

 

교착 상태를 해제하는 방법에는 아래와 같은 것들이 있다. 

 

• 자원 강제 선점 
  교착 상태에 빠진 스레드중 하나를 선택하여 이 스레드가 소유한 자원을 강제로 빼앗아 다른 스레드에게 할당하는 방법이다. 

 

• 롤백
  교착 상태가 발생할 것으로 예상되는 스레드들에 대해 상태를 저장해두었다가, 교착 상태가 발생하면 이전 상태로 되돌리는 방법이다. 롤백 이후 스레드가 다시 작업을 하게 되면 여러 요인에 의해 자원 할당 순서가 달라지게 되어 교착 상태가 발생하지 않는다.  하지만 주기적으로 스레드들의 상태를 저장해야하므로 공간이 소모되어 시스템 성능 저하를 가져올 수 있다. 
  
  
• 스레드 강제 종료
  교착 상태에 빠진 스레드들중 하나를 강제로 종료시키는 방법이다. 하지만 어떤 스레드를 희생시킬지에 대한 문제가 남아있다. 

 

 

교착 상태 무시

교착 상태 무시란 교착 상태가 발생하도록 내버려두는 방법이다. 문제가 발생하도록 내버려두었다가 문제가 발생하면 그때 대책을 세우면 된다는 것이다. 왜냐하면 범용 시스템에서는 교착 상태가 발생하더라도 파국을 부를 만한 작업을 실행시키지 않기 때문에 그때가서 처리해도 된다는 것이다. 이를 타조 알고리즘 이라고도 한다. 

 

 

 

 

 

 

 

🐸 출처 

https://unnokid.github.io/Avoidance/

https://jongone.com/posts/dead-lock/