[운영체제] 7. 교착상태

해당 내용은 공룡책(Operating System Concepts 10th Ed: Abraham Silberschatz, Peter Baer Galvin, Greg Gagne)과 대학 강의를 기반으로 재구성하여 정리한 공부 내용입니다.
+) 6장부터는 사자책(명품 운영체제: 황기태)에 더 중점을 두고 전개됩니다.

1. 교착상태 문제 제기

식사하는 철학자 문제

- 두 철학자가 양쪽 포크를 모두 들 수 있을 때는 아무 문제 X

- 2~4명이 동시에 식사하는 경우, 포크에 대한 충돌이 발생해 누군가의 대기는 필요하지만 무한 대기가 발생하지는 않음

- 5명이 동시에 식사하지만 포크를 잡는 순간이 약간씩 다른 경우, 위와 같이 잠깐씩 대기하면 식사 가능

- 5명이 모두 동시에 왼쪽 포크를 잡은 경우, 모든 철학자가 자신의 오른쪽 포크를 무한정 기다려 아무도 먹지 못하고 영원히 대기하는 교착상태에 빠짐

 

철학자들의 교착상태 원인: 환형 요청/대기(circular request/wait) - 대기가 환형 고리를 형성하고 있으며 스스로 해체 불가함

해결: 환형 요청/대기가 생기지 않게 규칙 변경 - ex. 5명 중 1명은 오른쪽 포크를 먼저 잡도록 하면 환형 요청이 생기지 않음

 

컴퓨터 시스템에서 발생하는 교착상태를 설명

철학자 - 스레드

포크 - 자원

스파게티 - 스레드가 처리할 작업

 

해결책

모니터 사용

철학자가 양쪽 포크를 모두 얻을 수 있을 때만 포크를 집을 수 있다는 조건을 제한

 

2. 교착상태

교착상태(deadlock): 자원을 소유한 스레드들 사이에서 각 스레드는 다른 스레드가 소유한 자원을 요청하여 모든 스레드가 무한정 대기하는 현상 (=풀지 못하는 포옹(deadly embrace))

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

 

전형적인 멀티스레드 교착상태 사례

두 스레드가 임계구역에 진입하기 위해 2개의 락 LockA와 LockB가 모두 필요한데 각 스레드가 락을 하나씩 소유한 상태에서 상대 스레드가 소유한 락을 요청하는 경우

 

교착상태는 CPU 개수와 상관없이 락이나 자원에 대한 멀티스레드 경쟁이 있는 한 발생할 수 있다.

교착상태는 커널 코드 내에서는 거의 발생하지 않고 사용자 응용프로그램 내에서 주로 발생한다.

 

컴퓨터 시스템에 잠재된 교착상태 유발 요인

• 자원 - 자원은 교착상태의 발생지
• 자원과 스레드 - 한 스레드가 동시에 여러 개의 자원을 필요로 하는 경우
• 자원과 운영체제 - 운영체제는 한 번에 하나씩 자원을 할당
• 자원 비선점 - 할당된 자원은 스레드가 자발적으로 내놓게 전에 강제로 뺏지 못함

 

교착상태 모델링

자원 할당 그래프(RAG, resource allocation graph)를 이용하여 교착상태를 표현하고, 교착상태 예방, 회피, 감지 등을 운용함

자원 할당 그래프: 컴퓨터 시스템에 존재하는 자원과 스레드들의 상태를 나타내는 방향성 그래프

꼭짓점(vertex), 간선(edge)으로 구성

꼭짓점: 스레드 - 원, 자원 - 사각형으로 표현

간선: 할당 간선(자원 to 스레드, 스레드가 자원 소유 중)과 요청 간선(스레드 to 자원, 스레드가 자원을 기다리는 중)으로 표현

 

정점 V는 시스템 내 모든 활성 스레드 집합 T와 시스템 내 모든 자원 유형의 집합 R로 구별

T→R: 스레드 T가 자원 유형 R의 인스턴스 하나를 요청하는 것(reqeust edge). 현재 이 자원을 기다리는 상태

R →T: 자원 유형 R의 한 인스턴스가 스레드 T에 할당된 것(assignment edge).

컴퓨터 시스템에 실행 중인 전체 스레드와 자원

각 자원의 총 인스턴스 개수와 할당 가능한 인스턴스 개수

각 스레드가 할당받아 소유하고 있는 자원의 인스턴스 개수

각 스레드가 실행에 필요한 자원 유형과 인스턴스 개수

 

스레드들이 교착상태에 있으면: 자원 할당 그래프에 스레드와 자원들을 연결하는 간선들의 환형 고리가 나타남

환형 고리에 포함되는 스레드들이 모두 교착상태에 걸려있는 것

(사이클이 있으면서 교착 상태가 아닌 그래프도 존재하기는 함!)

 

3. 교착상태 해결

코프만 조건

: 교착상태를 유발할 수 있는 4가지 필요조건

1) 상호배제(Mutual Exclusion) - 자원은 한 번에 한 스레드에게만 할당

2) 소유하면서 대기(Hold&Wait) - 스레드가 자원을 소유하면서 다른 자원 대기

3) 강제 자원 반환 불가(No Preemption) - 스레드에게 할당된 자원을 강제로 빼앗지 못함

4) 환형 대기(Circular Wait) - 한 그룹의 스레드들에서 각 스레드가 다른 스레드가 소유한 자원을 요청하는 환형 고리 형성

 

4가지 조건을 모두 가진 컴퓨터 시스템에서는 언제든 교착상태가 발생할 수 있음

→ 4가지 중 하나라도 성립되지 않게 한다면 교착상태에 빠지지 않음

→ 4가지 중 하나만 만족해도 교착상태가 발생하지 않을 것

 

교착상태 해결 방법

1. 교착상태 예방(prevention): 4가지 조건 중 하나 이상 조건이 아예 불성립하도록 시스템을 설계하고 구성하는 것

2. 교착상태 회피(avoidence): 운영체제가 자원을 할당할 때 교착상태에 빠지지 않을 것이라고 확신하는 경우에만 자원을 할당하여 교착상태가 되지 않도록 하는 것; 자원 할당 시마다 교착상태 가능성을 검사하므로 시스템 성능을 저하시킴

3. 교착상태 감지 및 복구(detection and recovery): 교착상태 예방이나 회피 전략을 사용하지 않고 운영체제가 교착상태를 감지하는 별도 프로그램을 백그라운드로 구동시킴 → 교착상태에 빠진 스레드 그룹을 발견하면 교착상태로부터 해체하는 방법; 감지 작업이 주기적으로 실행되어야 해서 시스템 부담 큼

4. 교착상태 무시(ignore and reboot): 아무런 대비책 없이 교착상태가 발생하도록 내버려 두는 것. 대부분 범용 운영체제에서 사용. 웬만해서 발생하지 않고 발생해도 큰 문제가 생기지 않으며 1~3번 방법이 많은 시공간을 필요로 해 시스템 성능을 떨어뜨리기 때문. 교착상태 무시 알고리즘으로 타조 알고리즘이 사용됨.

 

교착상태 예방

1. 상호배제 문제 → 상호배제 없애기

: 2개 이상 스레드가 동시에 자원을 허용할 수 있게 허용하면 됨 → 불가능

 

2. 소유하면서 대기 문제 → 기다리지 않게

: 스레드가 필요한 자원을 처음부터 모두 가지게 하면 됨

1번 방안 - 스레드 실행 전에 OS가 스레드가 필요한 자원을 모두 알고 있어, 스레드 실행 시작과 함께 모든 자원을 할당해줘 실행 중에 자원 요청으로 대기할 일이 없게 함. (불가능한 경우 애초에 스레드 실행 자체를 대기시킴)

2번 방안 - 자원 소유 상태로 새로운 자원이 필요해지면 현재 할당받은 모든 자원을 반환하고 필요한 모든 자원을 모두 요청하게 함. all or nothing 전략

→ 기아 현상이 나타날 수 있다.

 

3. 자원 강제 반환 불가 문제 → 자원 선점 허용

: 스레드가 대기해야 하는 상황이면 현재 점유하고 있는 모든 자원이 선점되는 방식. 회수!

어려움

 

4. 환형 대기 문제 → 환형 대기 제거

: 모든 자원에 번호를 매기고 스레드에게 자원 번호 순으로 자원을 할당받게 함

가장 일반적인 해결책

 

교착상태 회피

자원이 어떻게 요청될지에 대한 추가 정보를 시스템에 제안하도록 요구

가장 단순하고 유용한 모델은 각 스레드가 자신이 필요로 하는 각 유형의 자원마다 필요한 최대 수를 선언하도록 요구하는 것

 

자원할당 알고리즘을 이용하여 교착상태를 방지하는 방법

자원할당 알고리즘: 자원 할당을 요청받았을 때 앞으로 환형 대기가 발생하지 않는다는 확신이 서는 경우에만 자원을 할당

이때 자원 할당 상태는 가용 자원의 수, 할당된 자원의 수, 스레드들의 최대 요구 수에 의해 정의

(자원 할당 시마다 환형 대기 발생을 판단해야 한다는 문제점 존재)

 

Safe State

시스템의 상태가 항상 안전 상태를 떠나지 않도록 고수함

요청한 자원을 즉시 승낙해주는 경우는 시스템의 상태가 안전 상태에서 안전 상태로 옮길 때 뿐이다.

 

시스템이 안전한 상태: 시스템이 safe sequence를 찾을 수 있는 상태 = 모든 스레드에 대해 스레드가 요청하는 자원을 시스템에 현재 남아있는 자원과 앞에서 수행을 마칠 모든 스레드들이 반납하는 자원들로 만족시켜 줄 수 있음을 의미

해당 스레드가 요청할 자원들을 즉시 만족시켜줄 수 없을 것으로 판단되면 모든 수행을 마칠 스레드들이 마친 후까지 기다리게 함

기다리게 하더라도 결과적으로 실행할 수 있으면 됨

→ 모든 스레드들을 무사히 마칠 수있는 시퀀스를 찾을 수 있는 상태

 

시스템 상태가 안전하면 교착 상태가 발생하지 않으며, 불안전하다고 해서 반드시 교착 상태가 발생하는 것은 아니다.

 

자원 할당 그래프 알고리즘

단일 인스턴스 자원인 경우

예약 간선(claim edge) 도입

T → R: T가 미래에 자원 R을 요청할 것이라는 의미. 점선으로 표기

실제로 프로세스 T가 자원 R을 요청하면 예약 간선은 요청 간선으로 변환된다. 실선으로 변환

 

스레드가 실행되기 전에 스레드의 모든 예약 간선이 자원 할당 그래프에 표시되어야 한다.

스레드와 연관된 모든 간선들이 예약 간선일 때만 예약 간선 T → R을 그래프에 추가하도록 허용

이때 이를 할당 간선으로 변환해도 자원 할당 그래프에 사이클을 형성하지 않을 때만 요청을 허용한다.

사이클 탐지 알고리즘을 통해 안전성을 검사(n^2 차수의 연산 필요. n은 시스템에 있는 스레드 수)

 

종류마다 자원이 여러 개씩 있게 되면 사용할 수 없음

 

Banker's 알고리즘(은행원 알고리즘)

시스템을 안전한 상태와 불안전한 상태로 나누고, 자원을 할당하였을 때 안전한 상태로 갈 때만 자원을 할당하는 알고리즘

아래를 기반으로 안전한지 판단:

각 스레드가 필요로 하는 자원의 최대 개수(< 자원의 총 보유 수)

현재 실행 중인 각 스레드가 할당 받은 자원의 개수

시스템 내 할당 가능한 자원의 개수

→ 스레드가 자원을 요청하면 그것을 들어주었을 때 시스템이 게속 안전 상태에 머무를 때에만 허용

 

스레드 수 n, 자원 타입의 수 m에 대해

Need[i, j] = Max[i, j] - Allocation[i, j]

각 스레드가 향후 요청할 수 있는 자원의 개수 = 각 스레드가 최대로 필요로 하는 자원의 개수 - 각 스레드에 현재 할당된 자원 개수

Available: 각 종류별로 가용한 자원 개수

 

Request를 스레드 요청 벡터라고 하면,

Available -= Request

Allocation += Request

Need -= Request

를 수행했을 때 안전한지를 판단하여 할당을 결정

 

→ 각 스레드가 실행 전에 필요한 전체 자원의 수를 알아야 하므로 비현실적임!

실행 중인 스레드 개수도 동적으로 변하므로 미리 스레드 개수를 정적으로 고정시키는 것도 불가능

 

교착상태 감지 및 복구

교착상태를 감지하는 백그라운드 프로그램을 상시 실행시켜 교착상태를 감지하고 해제시키는 방법

감지: 자원 할당 그래프에 환형 대기 모양을 가지는 부분이 있는지 판단

→ 감지했다 해도 해제가 어려움

 

해제 방법:

1. 자원 강제 선점(preemption):

교착상태에 빠진 스레드 중 하나를 선택하고 이 스레드가 소유한 자원을 강제로 빼앗아 이 자원을 기다리는 다른 스레드에게 할당하는 방법 → 스레드 환형 대기 고리를 끊음

 

2. 롤백(rollback):

교착상태가 발생할 것으로 예측되는 스레드들에 대해 상태를 주기적으로 저장해두었다가, 교착상태가 발생하면 가장 최근에 저장해둔 상태로 복구시켜 그 상태로 돌아가게 함

롤백 이후 스레드들이 다시 시작하면 자원이 할당되는 순서가 달라져 교착상태를 면하게 됨

→ 주기적으로 스레드 상태가 저장돼야 하기 때문에 시공간을 소모해 성능을 저하시킴

 

3. 스레드 강제 종료(kill process):
교착상태에 빠진 스레드 중 하나를 강제로 종료시키는 방법 → 자원을 기다리는 환형 대기 고리가 끊어져 교착상태에서 벗어남

→ 가장 간단하고 효과적이지만 어떤 스레드를 희생시킬지 결정하는 문제 발생

 

∴ 판단, 해제 방법 모두 시스템 부담이 큼

 

교착상태 무시

: 타조(ostrich) 알고리즘

대부분의 운영체제에서 사용

교착상태가 의심되면 사용자나 관리자가 시스템을 재시작하거나 의심가는 스레드를 강제 종료해 해결함

데이터를 잃어버리는 손실이 있을 수 있어도, 비용 면에서 낫다고 판단함

But 시스템 재시작이나 스레드 강제 종료 등으로 파국을 초래하는 실시간 시스템에는 부적절