Chapter 8. 교착 상태 - 1부

안녕하세요 파피몬입니다! 운영체제 8단원에 대해 공부해 보았습니다. 1부입니다!

Abraham Silberschatz의 Operating System Concepts 10th edition과 학부 수업을 듣고 정리한 내용입니다. 오개념이 있다면 알려주세요~~

 

다중 프로그래밍 환경에서는 여러 스레드들이 한정된 자원을 사용하기 위해 경쟁할 수 있다. 앞서 살펴본 세마포 같은 경우엔 자원을 할당해 줄 수 없다면 해당 스레드를 대기 상태로 변경해 저장해 두고 있었다. 

 

하지만 여기서 문제가 발생하는데, 대기 중인 스레드들이 평생 대기해야 한다면 어찌해야 할까? 한 스레드가 요청한 자원들이 다른 스레드들에 의해 점유되어 있고, 그들 역시 다른 스레드가 점유 중인 자원을 대기 중이라면, 아주 단단히 꼬인 상황이 발생한다. 이를 Deadlock이라고 한다. 

 

<교착 상태>

교착 상태란, 한 스레드 집합 내의 모든 스레드가 그 집합 내의 다른 스레드에 의해서만 발생될 수 있는 이벤트를 기다리는 상황을 뜻한다. 

 

교착 상태가 발생하는 경우는 다음의 조건들이 모두 일어났을 때 발생할 수 있다. 이 조건들은 필요조건임으로, 이 조건들이 다 만족된다 하더라도 교착상태가 일어나지 않을 수도 있다. 

 

  1. Mutual Exclusion: 최소한 하나의 자원이 비공유 모드로 점유되어야 한다. 한 스레드가 해당 자원을 요청하면, 요청한 스레드는 무조건 그 자원이 방출될 때까지 대기해야 한다. 

 

  2. Hold-and-Wait: 스레드는 최소한 하나의 자원을 점유한 채, 현재 다른 스레드에 의해 점유된 자원을 추가로 얻기 위해 대기해야 한다. 

 

  3. No Preemption: 이미 다른 스레드가 사용 중인 자원은 선점할 수 없다. 

 

  4. Circular Wait: 대기하고 있는 스레드의 집합들이 서로 물고, 물리는 관계로 대기하고 있다. 

 

자원 할당 그래프를 통해서 교착 상태를 조금 더 직관적으로 이해할 수 있다. 

 

<자원 할당 그래프>

자원 할당 그래프를 통해, 어떤 프로세스가 어떤 자원을 사용 중이고, 어떤 자원을 요청했는지를 알 수 있다. 

프로세스는 파란색 원으로, 자원은 회색 사각형으로 표시한다. 그 안에는 해당 자원이 몇 개나 사용 가능한지 검은 점으로 표현되게 된다. 

만약 자원 할당 그래프에 Cycle이 있다(서로 물고 물리는 부분)면 Deadlock을 의심해 보아야 한다. 하지만 Cycle이 있다고 필수적으로 Deadlock이 되는 것은 아니다. 말로는 이해가 힘드니, 예시를 보자. 

 

왼쪽 - Deadlock 없음 / 오른쪽 - Deadlock 있음

자원 할당 그래프 2가지를 가져왔다. 둘 모두 Cycle이 있음을 알 수 있다. 하지만 왼쪽 친구는 Deadlock이 없고, 오른쪽 친구는 Deadlock 상태에 빠진다. 차이가 무엇일까?

 

왼쪽 그래프 같은 경우는 P3가 자신의 연산을 마무리하면, 들고 있던 R3를 내려놓고 소멸하게 된다. R3 만 바라보며 대기 중이었던 P2는, 그때 비로소 자신의 연산을 진행한다. P2가 마무리되면 P1이 목 빠지게 기다리고 있던 R1이 방출될 것이고, 모두가 수행되는 아름다운 마무리가 된다. 

 

오른쪽 그래프를 보자. 아주 해결하기 어려운 상태에 있다. P3 입장에서는 R2가 간절한데, P1, P2가 꽉 잡고 있다. P1 입장에서는 R1이 간절한데 P2가 꽉 잡고 있다. P2 입장에서는 R3가 간절한데 P3가 이를 또 꽉 잡고 있다. 그 누구도 놔주지 않으면서 놓기만을 기다리는 이 상황을 Deadlock이라고 하며, 자원 할당 그래프를 통해 조금 더 직관적으로 파악할 수 있다. 

 

<교착 상태 처리 방법>

교착 상태에 빠지면 우선 시스템이 큰일 나는 것은 알겠다! 문제 해결을 위해 본 책은 다음과 같은 솔루션을 제시한다. 

  1. 교착 상태에 절대 빠지지 않도록, 예방prevention/회피avoidance 방식 도입

  2. 교착 상태에 빠지게 된다면, 탐지detection/복구recovery 방식 도입

  3. 마치 아무 일도 없던 것처럼 행동 - 대부분의 운영체제가 채택. 교착 상태 사용자가 처리하게 유도

 

본 책에서는 교착 상태 처리 방법을 위한 예방, 회피, 탐지, 복구 방법을 하나씩 소개한다. 나도 소개하겠다. 호호

 

<교착 상태 예방>

위에서 살펴본 교착상태에 빠지는 필요조건 4가지 중 하나라도 성립하지 않게 한다면 교착상태에 빠질 일이 없을 것이다. 교착 상태 예방은 이에 중점을 둔다. 

 

  1. Mutual Exclusion: 상호 배제를 거부하는 것은 자원의 속성을 공유하지 않는 작전이다. 프린터에 동시에 두 가지 문서가 인쇄돼서 나오면 사용자는 그 컴퓨터를 다시는 쓰지 않을 것이다. 이건 놔두자. 

  

  2. Hold-and-Wait: 두 가지 방법이 있다. 

    2-1. 스레드는 시작 전 모든 자원을 요청하고 할당받는다

      * 자원 요청 동적 특성으로 인해 실용적이지 않다. 

    2-2. 스레드가 전혀 자원을 갖고 있지 않을 때만 요청할 수 있게 한다. 

      * Low 자원 utilization, Starvation 발생 가능성

 

  3. No Preemption: 만약 자원을 점유하고 있는 스레드가 즉시 할당할 수 없는 자원을 요청하면, 현재 점유하고 있는 모든 자원이 선점된다 (방출된다는 뜻). 스레드가 요청 중인 새로운 자원을 할당받고, 대기 중에 선점되었던 모든 자원을 회복할 때에만 다시 시작할 수 있다. 

      * CPU 레지스터, DB 트랜잭션처럼 상태 쉽게 저장/복원되는 자원에 적용

      * 뮤텍스 락, 세마포에서는 적용될 수 없다. 

 

  4. Circular Wait: 가장 실용적인 방법으로, 모든 자원 유형에 전체적인 순서를 부여해, 각 프로세스가 열거된 순서대로 오름차순으로 자원을 요청하도록 요구하는 것