운영체제 - 8장 교착 상태

8장 주제

Mutex 락을 사용할 때 어떻게 교착 상태가 발생할 수 있는지 보여준다.
교착 상태를 특징 짓는 4가지 필수 조건을 정의한다.
자원 할당 그래프에서 교착 상태 상황을 식별한다.
교착 상태 예방을 위한 4가지 방법을 평가한다.
교착 상태 회피를 위해 은행의 알고리즘을 적용한다.
교착 상태 감지 알고리즘을 적용한다.
교착 상태에서 복구하기 위한 접근법을 평가한다

시스템 모델

시스템은 경쟁하는 스레드들 사이에 분배되어야 할 유한한 수의 자원들로 구성된다. $R^{1}, R^{2}, . . ., R^{m}$

자원의 예: CPU 주기, 파일, 입/출력 장치(네트워크 인터페이스, DVD 드라이브 등과 같은)

이들 자원은 다수의 유형( $R^{i}$ )으로 분할되며, 이들 각각은 동등한 다수의 인스턴스( $W^{i}$ )들로 구성된다.

예 : 한 시스템이 4개의 CPU를 가진다면, 자원 유형 CPU는 4개의 인스턴스를 가진다.

정상적인 작동 모드하에서, 프로세스는 다음 순서로만 자원을 사용할 수 있다.

요청
사용
방출

다중 스레드 응용에서의 교착 상태

Pthread 프로그램에서 어떻게 교착 상태가 발생할 수 있는지 보자.

우선 두 뮤텍스 락이 다음과 같은 코드 예제에 의해 생성되고 초기화된다.

pthread_mutex_init () 함수는 가용한 mutex를 초기화한다.
Mutex 락은 각각 pthread_mutex_lock()과 pthread_mutex_unlock() 함수를 이용하여 획득되고 방출된다.
한 스레드가 잠긴 mutex 락을 획득하려고 시도하면, pthread_mutex_lock() 함수 호출은 mutex 락의 소유주가 pthread_mutex_unlock() 함수를 호출할 때까지 이 스레드를 봉쇄한다.

thread_one은 (1) first_mutex, (2) second_mutex 순서로 mutex 락을 획득하려고 하고 동시에 thread_two는 (1) second_mutex, (2) first_mutex 순서로 mutex 락을 획득하려고 한다. thread_one이 first_mutex를 획득하고 thread_two가 second_mutex를 획득하게 되면 교착 상태가 가능하다.

라이브락

스레드가 정체된 상태는 아니지만 계속 시도해도 진행이 안되는 경우를 말한다.

예 : 마주 오던 두 사람이 같은 방향으로 계속 피할 때, 또는 CSMA/CD

교착 상태 특성

필요조건들

교착 상태는 한 시스템에 다음 네 가지 조건이 동시에 성립될 때 발생할 수 있다.

상호 배제 (mutual exclusion) : 최소한 하나의 자원이 공유 불가 상태
점유하며 대기 (hold and wait) : 스레드는 최소한 하나의 자원을 점유한 채, 현재 다른 스레드에 의해 점유된 자원을 추가로 얻기 위해 반드시 대기해야 한다.
비선점 (no preemption) : 자원들은 선점할 수 없어야 한다. 즉, 자원이 강제적으로 방출될 수 없고, 점유하고 있는 스레드가 태스크를 종료한 후 그 스레드에 의해 자발적으로만 방출될 수 있다.
순환 대기 (circular wait) : 대기하고 있는 스레드의 집합 { $T^{0}, T^{1} . . ., T^{n}$ ｝에서 $T^{0}$ 는 $T^{1}$ 이 점유한 자원을 대기하고, $T^{1}$ 은 $T^{2}$ 가 점유한 자원을 대기하고, ..., $T^{n - 1}$ 은 $T^{n}$ 이 점유한 자원을 대기하며, $T^{n}$ 은 $T^{0}$ 가 점유한 자원을 대기한다.

자원 할당 그래프

교착 상태는 시스템 자원 할당 그래프라고 하는 방향 그래프로 더욱 정확하게 기술할 수 있다.

이 그래프는 정점(vertex) $V$ 의 집합과 간선(edge) $E$ 의 집합으로 구성된다.

$V$ 의 집합은 다음 두 가지 유형으로 구별된다.

시스템 내의 모든 활성 스레드의 집합인 $T = {T^{1}, T^{2} . . ., T^{n}}$
시스템 내의 모든 자원 유형의 집합인 $R = {R^{1}, R^{2} . . ., R^{m}}$

스레드에서 자원으로 가는 방향 간선은 요청 간선이라 하고, 자원에서 스레드로 가는 방향 간선은 할당 간선이라 한다.

도식적으로 각 스레는 원으로 자원 유형은 사각형으로 표현한다.

(그래프 프로세스 복습 필요)

만약 그래프에 순환이 없다면 교착 상태는 없다.
만약 그래프가 순환을 포함한다면
- 순환을 포함하고 각 리소스 유형이 유일한 인스턴스를 갖는다면 교착상태이다.
- 순환을 포함하고 각 리소스 유형이 여러 인스턴스를 갖는다면 교착상태가 아닐수도 있다.
  
  교착 상태 처리 방법
  원칙적으로 교착 상태 문제를 처리하는 데는 다음과 같은 세 가지 다른 방법이 있다.
  - 문제를 무시하고, 교착 상태가 시스템에서 절대 발생하지 않는 척한다.
    - 저렴해서 대부분의 OS가 사용
  - 시스템이 결코 교착 상태가 되지 않도록 보장하기 위하여 교착 상태를 예방하거나 회피하는 프로토콜을 사용한다.
    - 교착상태 예방 : 필요조건 4개 중 적어도 하나 이상 성립 안되게 보장
    - 교착상태 회피 : 필요한 자원에 대한 정보를 이용
  - 시스템이 교착 상태가 되도록 허용한 다음에 복구시키는 방법이 있다
    - 데이터베이스 시스템에서 사용
  교착 상태 예방
  네 가지 필요조건 중 최소한 하나가 성립하지 않도록 보장함으로써 교착 상태의 발생을 예방할 수 있다.
  상호 배제
  적어도 하나의 자원은 공유가 불가능한 자원이어야 한다. (ex: read-only files)
  - 공유 자원이 너무 많아서 이 조건을 막는 것은 어렵다.
  점유하며 대기
  스레드가 자원을 요청할 때 마다 다른 자원을 보유하지 않도록 보장해야 한다.
  - 우리가 사용할 수 있는 하나의 프로토콜은 각 스레드가 실행을 시작하기 전에 모든 자원을 요청하고 할당해야 한다.
  - 자원 활용률을 낮추고, 기아 상태를 야기할 수 있다.
  비선점
  - 자원 할당이 불가능하면 가지고 있는 자원을 다 방출한다. (대기 중인 프로세스의 자원을 반납하게 된다.)
  - 선점된 자원들은 그 스레드가 기다리고 있는 자원들의 리스트에 추가된다.
  - 자원을 다 할당 받을 수 있을 때 프로세스를 다시 시작한다.
  순환 대기
  각 프로세스가 열거된 순서대로 오름차순으로 자원을 요청해서, 어떤 자원을 요청할 때 그 자원보다 높은 순의 자원을 가질 수 없게 하는 것이다.
  - 가장 현실적인 방법이다.
  교착 상태 회피
  교착 상태를 회피하는 자원이 어떻게 요청될지에 대한 추가 정보를 제공하도록 요구하는 것이다.
  - 가장 단순하고 제일 유용한 모델은 각 스레드가 자신이 필요로 하는 각 유형의 자원마다 최대 수를 선언하도록 요구하는 것이다.
  - 교착 상태 회피 알고리즘은 동적으로 자원 할당 상태를 검사해서 순환 대기 상태가 절대로 생기지 않도록 보장한다.
  - 자원 할당 상태는 사용 가능한 자원과 할당된 자원의 수, 프로세스의 최대 요구 수로 계산된다.
  안전 상태
  시스템 상태가 안전（safe）하다는 말은 시스템에 있는 모든 프로세스가 각자 필요한 자원을 사용할 수 있는 실행 순서가 존재할 때 우리는 시스템이 안전한 상태에 있는 것이다.
  프로세스가 자원을 요청할 때, 시스템은 즉각적인 자원 할당이 시스템이 안정 상태에서 벗어나는지 판단해야 한다.
  만약 프로세스 시퀸스< $P^{1}, P^{2}, . . ., P^{n}$ >가 시스템 내에 모든 프로세스 존재해야 한다면 시스템은 안정 상태이다.
  
  불안전 상태라고 무조건 교착 상태가 아니다.
  자원 할당 그래프 알고리즘
  만약 각 자원 유형마다 단지 하나의 인스턴스를 갖는 자원 할당 시스템을 갖고 있다면, 우리는 교착 상태 회피를 자원 할당 그래프의 변형을 사용할 수 있다.
  원래 있던 요청 간선과 할당 간선에 예약 간선(claim edge)이라는 새로운 타입의 간선을 도입한다. 방향은 요청 간선과 유사하고 점선으로 표시한다.
  예약 간선 $T^{i}$ —> $R^{j}$ 는 $P^{i}$ 가 미래에 자원 $R^{j}$ 를 요청할 것이라는 의미이다.
  프로세스 $T^{i}$ 가 자원 $R^{j}$ 를 요청하면, 예약 간선 $T^{i}$ —> $R^{j}$ 는 요청 간선으로 변환된다.
  마찬가지로 $T^{i}$ 가 자원 $R^{j}$ 를 방출할 때, 할당 간선 $R^{j}$ —> $T^{i}$ 는 예약 간선 $T^{i}$ —> $R^{j}$ 로 다시 변환된다.
  
  $T^{2}$ 가 $R^{2}$ 를 요청할 때, 이를 할당하면 cycle이 발생하므로 할당하지 않는다.
  
  cycle이 발생하므로 할당하지 않는다.
  은행원 알고리즘
  자원 할당 그래프 알고리즘은 종류마다 자원이 여러 개씩 있게 되면 사용할 수 없다.
  은행원 알고리즘은 자원 할당 그래프 알고리즘보다 아래 알고리즘은 효율성이 다소 떨어지지만, 자원의 인스턴스가 여러개가 있을 때 사용할 수 있다.
  - 이 시스템에서는 스레드가 시작할 때 스레드가 가지고 있어야 할 자원의 최대 개수를 자원 종류마다 미리 신고하여야 한다.
  - 프로세스가 자원을 요청할 때 대기해야 될 수도 있다.
  - 프로세스가 모든 자원을 가져갔다면 유한한 시간내에 자원을 반환해야 한다.
  은행원 알고리즘은 몇 가지 자료구조가 필요하다. 여기서 $n$ 이 스레드의 수이고, $m$ 이 자원의 종류 수라고 하자.
  
  $N e e d = M a x - A l l o c a t i o n$
  안정성 알고리즘
  2-3. 프로세스 $i$ 가 아직 안 끝나고 필요한 자원이 충분히 있으면 작없을 마칠 수 있으니까 종료 후에 자원을 전부 반납한다.
  1. 모든 프로세스의 작업을 마칠 수 있으면 시스템은 안전한 상태에 있다.
  자원 요청 알고리즘
  1. 필요 이상인가?
  2. 충분한가?
  3. 요청한 것을 할당해도 안전한 상태를 유지하나?
  안전하면 할당하고 아니면 대기시킨다.
  예시
  이 알고리즘을 예를 들어 설명하기 위해 시스템에는 다섯 개의 프로세스 $T^{0}$ 부터 $T^{4}$ 까지 있고, A, B, C 세 가지 종류의 자원이 있다고 가정한다. 시스템에는 A 자원이 10개, B 자원이 5개, C 자원이 7개가 있다.
  프로세스 시퀀스 < $P^{1}$ , $P^{3}$ , $P^{4}$ , $P^{0}$ , $P^{2}$ >이 안정성 기준을 만족시키기 때문에 시스템은 안정 상태이다.
  교착 상태 탐지
  예방이나 방지 알고리즘을 사용하지 않는다면, 반드시 교착 상태 검사 알고리즘이나 회복 알고리즘을 사용해야 한다.
  각 자원 유형이 한 개씩 있는 경우
  대기 그래프 (wait-for graph)라고 하는, 자원 할당 그래프(리소스를 뺀 형태)의 변형을 사용해 교착 상태 탐지 알고리즘을 정의할 수 있다.
  노드들을 프로세스로 표기한다.
  대기 그래프에서 $T^{i}$ ,에서 $T^{j}$ 로의 간선은 프로세스 $T^{j}$ 가 가지고 있는 자원들에 대해, 프로세스 $T^{i}$ 가 그 자원이 필요하여 방출하기를 기다리는 것이다.
  간선 $T^{i}$ —> $T^{j}$ 는 해당 자원 할당 그래프가 자원 $R^{q}$ 에 대해 두 개의 간선 $T^{i}$ -> $R^{q}$ 와 $R^{q}$ —> $T^{j}$ 를 포함하는 경우에만 대기 그래프에 존재한다.
  주기적으로 알고리즘을 실행해서 순환 구간을 탐색하고 만약에 순환을 포함한다면 교착 상태가 존재하는 것이다.
  교착 상태 탐지 알고리즘은 $n^{2}$ 의 시간이 걸리고 $n$ 은 그래프 정점의 갯수이다.
  각 유형의 자원을 여러 개 가진 경우
  교착상태 회피 방식과의 차이점
  max가 없는 대신 현재 요청을 need로 간주하고 은행원 알고리즘을 실행한다. -> unsafe state라면 교착 상태로 판정한다.
  탐지 알고리즘 사용
  탐지 알고리즘은 언제 사용하는가는 두 가지 관점에 달려있다.
  - 교착 상태가 얼마나 자주 일어나는가?
  - 교착 상태가 일어나면 통상 몇 개의 스레드가 거기에 연루되는가?
  탐지 알고리즘을 아무 때나 수행하면 교착 상태를 유발한 스레드를 식별하지 못할 수 있다.
  반면에 자원 요청이 실패할 때 탐지 알고리즘을 수행하면 교착 상태를 유발한 스레드를 식별하는데 도움이 된다.
  교착 상태로부터 회복
  교착 상태를 시스템이 자동으로 회복하게 할 수 있는 두 가지 방법이 있다.
  - 한 가지 방법은 순환 대기를 깨뜨리기 위해 단순히 한 개 이상의 스레드를 중지(abort)시키는 것이다.
  - 두 번째 방법은 교착 상태에 있는 하나 이상의 스레드들로부터 자원을 선점(preempt)하는 것이다.
  프로세스와 스레드의 종료
  프로세스 또는 스레드를 중지(abort)시킴으로써 교착 상태를 제거하기 위해 우리는 두 방법의 하나를 사용한다.
  - 교착 상태 프로세스를 모두 중지
  - 교착 상태가 제거될 때까지 한 프로세스씩 중지
  어떤 것을 중지 시킬지에 대한 우선순위도 있다.
  1. 프로세스의 우선순위가 무엇인지
  2. 지금까지 프로세스가 수행된 시간과 지정된 일을 종료하는 데 더 필요한 시간
  3. 프로세스가 사용한 자원 유형과 수(예를 들어, 자원들을 선점하기가 단순한지 여부)
  4. 프로세스가 종료하기 위해 더 필요한 자원의 수
  5. 얼마나 많은 수의 프로세스가 종료되어야 하는지
  자원 선점
  자원 선점을 이용해 교착 상태를 제거하려면, 교착 상태가 깨어질 때까지 프로세스로부터 자원을 계속 선점해 이들을 다른 프로세스에 주어야 한다.
  - 회생자 선택 (selection of a victim) : 프로세스 종료에서와 같이, 비용을 최소화하기 위해 선점의 순서를 결정
  - 후퇴 (rollback) : 프로세스를 안전한 상태로 후퇴시키고, 그 상태로부터 다시 시작
  - 기아 상태 (starvation) : 희생자의 선택이 주로 비용 요인에 근거한 시스템에서는 동일한 프로세스가 항상 희생자로 선택될 수도있다. 대부분의 일반적인 해결 방법은 비용 요소에 후퇴의 횟수를 포함하는 방법이다.

운영체제 study08

운영체제 - 8장 교착 상태

시스템 모델

다중 스레드 응용에서의 교착 상태

라이브락

교착 상태 특성

필요조건들

자원 할당 그래프

교착 상태 처리 방법

교착 상태 예방

상호 배제

점유하며 대기

비선점

순환 대기

교착 상태 회피

안전 상태

자원 할당 그래프 알고리즘

은행원 알고리즘

안정성 알고리즘

자원 요청 알고리즘

예시

교착 상태 탐지

각 자원 유형이 한 개씩 있는 경우

각 유형의 자원을 여러 개 가진 경우

탐지 알고리즘 사용

교착 상태로부터 회복

프로세스와 스레드의 종료

자원 선점

카테고리

댓글 (0)

댓글 작성