[OS] 공룡책_8 교착상태

다중 프로그래밍 환경에서 대기중인 스레드가 요청한 자원을 함께 대기중인 스레드가 점유하고 있으며, 그 관계가 사이클을 형성하는 경우를 교착상태라고 한다.

8.1 시스템 모델

자원

• 시스템은 경쟁하는 스레드들 사이에 분배되어야 할 유한한 수의 자원들로 구성된다.
• 자원은 동등한 다수의 인스턴스로 구성된다.
• 스레드가 인스턴스를 요청하면 동일 유형 자원의 임의의 인스턴스를 할당함으로써 요청이 충족된다.

프로세스 작동 순서

1. 요청: 스레드가 자원을 요청, 즉시 허용되지 않으면 대기

2. 사용: 자원에 대해 작업

3. 방출: 자원을 방출

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

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

교착상태가 일어나는 예시는 다음과 같다.

	void *do_work_one(void *param)
    {
    	pthread_mutex_lock(&first_mutex);
        pthread_mutex_lock(&second_mutex);
        /* work */
        pthread_mutex_unlock(&second_mutex);
        pthread_mutex_unlock(&first_mutex);
    }
    
    void *do_work_two(void *param)
    {
    	pthread_mutex_lock(&second_mutex);
    	pthread_mutex_lock(&first_mutex);
        /* work */
        pthread_mutex_unlock(&first_mutex);
        pthread_mutex_unlock(&second_mutex);
    }

스레드 두개가 각각 do_work_one, do_work_two 함수를 실행할 때,
thread1이 first_mutex를 획득하고, thread2가 second_mutex를 획득한 상태는 교착상태이다.

하지만 이렇게 구성한다고 해서 교착상태가 늘 일어나는 것은 아니다. thread1이 thread2보다 먼저 mutex를 모두 획득하고 방출한다면 교착상태는 일어나지 않는다. 이러한 이유 때문에 교착상태 식별 및 검사 작업이 어렵다.

8.2.1 라이브락 (Livelock)

라이브락은 또 다른 형태의 라이브니스 장애이다.

• 스레드가 실패한 행동을 계속해서 시도할 때 발생한다.
• 복도를 지나갈 때 서로 피하기 위해 같은 방향으로 움직이는 현상과 유사하다.
• 실패한 행동을 재시도하는 시간을 무작위로 정하여 회피한다.

8.3 교착상태 특성

8.3.1 필요조건들

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

1. 상호배제(mutual exclusion): 최소 하나의 자원이 상호배제를 만족하며 점유되어야 한다.

2. 점유대기(hold-and-wait): 스레드가 최소 하나의 자원을 점유한 채, 다른 추가 자원을 대기해야 한다.

3. 비선점(no preemption): 자원들을 강제로 방출할 수 없다. 사용중인 스레드에 의해 자발적으로만 방출될 수 있다.

4. 순환대기(circular wait): 대기하고 있는 스레드간의 관계 그래프를 그렸을 때 사이클이 형성된다.

8.3.2 자원 할당 그래프(Resource-Allocation Graph)

스레드를 T, 자원을 R이라고 할 때

• 요청 간선: T->R
• 할당 간선: R->T

교착상태인 경우

사이클이 있으면서 교착상태가 아닌 경우

• 자원할당 그래프에서 사이클이 없다면 교착상태로부터 안전하다.
• 사이클이 있다고 해서 교착상태가 발생하는 것은 아니다. 자원할당 그래프의 사이클만으로는 자원의 인스턴스 개수를 고려할 수 없다.

8.4 교착 상태 처리 방법

1. 교착 상태를 무시한다.
2. 결코 교착상태가 되지 않도록 보장하기 위해 교착 상태를 예방하거나 회피하는 프로토콜을 사용한다.
3. 교착상태가 되도록 허용한 후 교착상태 발생 시 복구한다.

• 1번 해결안이 대부분의 운영체제가 사용하는 방법이다.
• 데이터베이스 같은 일부 시스템은 3번 해결안을 채택한다.

교착상태를 무시하는 것은 점차 시스템 성능을 저하시키고 시스템을 정지하게 만들 수 있다. 하지만 교착상태의 발생확률은 매우 작은 편이다. 따라서 교착상태를 무시하는 것이 다른 처리 방법과 비교해 비용이 적게 든다.

8.5 교착 상태 예방

교착상태의 예방은 교착상태가 발생하는데 필요한 조건 4가지 중 최소 하나가 성립하지 않음을 보장함으로써 이뤄진다.

8.5.1 상호 배제

• 상호배제는 동기화 문제에서 필수적이다.
• 어떤 자원들은 근본적으로 공유가 불가능하다. (ex: mutex lock)

따라서 상호배제 조건을 거부함으로써 교착상태 예방을 하는 것은 불가능하다.

8.5.2 점유 대기

스레드가 자원을 요청할 때는 자원을 점유하고 있지 않은 상태여야 한다. 즉 실행 전 필요한 모든 자원을 요청하고 할당해야 한다.

• 자원이 할당되었지만 장기간 사용되지 않아 자원 이용률이 낮을 수 있다.
  - mutex lock과 같이 일시적으로 사용됨에도 프로그램 전체 실행 시간동안 할당될 수 있다.
• 기아현상이 발생할 수 있다.
  - 인기가 많은 자원을 여러개 필요로 하는 스레드는 모든 자원을 한 번에 얻을 수 있는 가능성이 낮아 기아 현상이 발생할 수 있다.

8.5.3 비선점

• 특정 자원을 점유중인 스레드가 대기해야하는 자원을 추가로 요청하면, 이미 점유중이던 자원을 방출한다.
• 필요로 하는 모든 자원을 회복할 때에만 시작한다.

그냥 딱 봐도 현실적으로 적용하기 힘들 것 같다.

8.5.4 순환 대기

• 자원에 번호를 붙인다. ex) R1,R2...RN
• 스레드가 자원이 필요하면 작은 번호의 자원부터 순서로 요청한다.

락 순서를 설정하는 것은 복잡한 시스템에서는 어려울 수 있다.
하지만 이 방법은 때때로 유용하다. (다른 3가지 예방과 달리.)

8.6 교착 상태 회피

• 교착상태 예방은 장치의 이용률이 저하되고 시스템 총처리율이 감소한다.

• 자원 요청에 대한 추가정보를 이용하여 교착상태를 회피한다.

• 각 스레드의 요청과 방출에 대한 순서를 파악하고 있다면, 각 자원 요청에 대해서 가능한 미래의 교착상태를 피할 수 있다.

• 다양한 회피 알고리즘이 있으며, 각 알고리즘은 필요한 정보의 양과 유형에서 차이가 있다.

8.6.1 안전 상태

• 스레드 집합<T1,T2...,TN>를 특정 순서로 실행했을 때 교착상태를 야기시키지 않고 모두 실행할 수 있다면 그 순서를 안전순서라고 한다.

• 안전순서를 찾을 수 있다면 시스템은 안전상태이다.

시스템이 안전상태라면 교착상태가 아니다. 하지만 불안전 상태라고 해서 교착상태인 것은 아니다.

• 시스템은 안전상태에서 불안전 상태로 전이될 수 있다.

• 시스템은 안전상태를 유지하기 위해 스레드의 자원 요청을 보류할 수 있다. 따라서 스레드가 요청한 자원보다 많은 양을 보유한 상태가 지속될 수 있다. -> 자원의 이용률은 회피를 안 쓸 때에 비해서 낮아질 수밖에 없다.

8.6.2 자원 할당 그래프 알고리즘

• 기존 자원할당 그래프에 예약간선을 추가한다.
  - 예약간선은 T가 R에게 미래에 요청할 것이라는 의미이다.
  
• 예약간선이 요청간선으로 변할 때, 사이클을 형성하지 않아야 안전상태를 유지할 수 있다.

종류마다 자원이 여러개면 사용할 수 없다.

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

자원할당 그래프 알고리즘보다는 효율성이 떨어지지만, 자원의 개수가 여러개여도 사용할 수 있다.

자료 구조

은행원 알고리즘에 사용되는 자료구조
N개의 스레드와 M개의 자원이 존재한다고 가정

• Available[M] : 자원의 종류별로 사용 가능한 개수

• MAX[N][M] : 각 스레드가 최대로 필요로 하는 자원의 종류별 개수

• Allocation[N][M] : 각 스레드에 현재 할당된 자원의 종류별 개수

• Need[N][M] : 각 스레드가 앞으로 필요로 하는 자원의 종류별 개수
  - Need[i][j] = Max[i][j] - Allocation[i][j]

8.6.3.1 안전성 알고리즘

1. Work[][] = Available[][], Finish[i] = false로 초기화 한다.

2. Finish = false이고 Need < Work인 i를 찾는다.

   • 즉, 작업이 완료되지 않은 스레드들 중 현재 가용한 자원으로 작업을 끝낼 수 있는 스레드를 찾는다.
   • 그러한 i값이 없다면 4번으로 간다.

3. Work = Work + Allocation[i], Finish[i] = true

   • 찾은 i번째 작업을 완료했다고 가정하고 가용 자원에 i가 가지고 있던 자원을 추가한다.

4. 모든 i값에 대해 Finish[i] = true이면 시스템은 안전상태에 있다.

M*N^2번의 연산이 필요하다.

8.6.3.2 자원 요청 알고리즘

특정 스레드가 자원을 요청했을 땐, 요청을 받아들였다고 가정하고 안전상태를 확인한다. 안전한 경우 자원을 할당해준다.

1. Request[i] <= Need[i]를 만족하면 2번으로 간다.
   • 그렇지 않은 경우 오류로 처리한다.
2. Request[i][j] <= Available[j]이면 3번으로 간다.
   • 그렇지 않은 경우 가용 자원이 늘어날 때까지 대기한다.
3. 자원을 할당해줬다고 가정하고 시스템 상태 정보를 변경한다.

상태를 바꾼 후 안전성 알고리즘을 통해 안전상태를 확인한다.

8.7 교착 상태 탐지

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

• 자원할당 그래프의 변형을 통해 대기 그래프(wait-for graph)를 구성하고 이를 통해 교착상태를 탐지한다.

• 자원할당 그래프에서 T->R 간선을 Ti->Tj의 형태로 변형한다.
  - i번째 스레드가 j번째 스레드가 가진 자원을 대기하고 있다는 의미이다.
  

• 대기 그래프에서 사이클이 탐지 된다면 교착상태 가능성을 보고한다.

자원할당 그래프와 대기 그래프 차이

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

• 은행원 알고리즘과 유사하다. Need대신 Request행렬을 사용한다.
  - 8.6.3.2 자원 요청 알고리즘과 같은듯 하다.

8.7.3 탐지 알고리즘 사용

8.7.2에서 다룬 탐지 알고리즘을 언제 사용하는지는 다음 사항에 따라 결정된다.

1. 교착상태의 발생 빈도

2. 교착 상태 발생시 규모(몇개의 스레드가 통상 연류되는가)

너무 자주 호출하면 오버헤드가 커진다.

8.8 교착 상태로부터 회복

교착상태를 깨뜨리는 데는 두 가지 방법이 있다.
1. 순환대기를 깨뜨리기 위해 단순히 한 개 이상의 스레드를 중지(abort)시키는 것이다.
2. 두 번째 방법은 교착 상태에 있는 하나 이상의 스레드들로부터 자원을 선점(preempt)하는 것이다.

8.8.1 프로세스와 스레드의 종료

• 교착 상태 프로세스를 모두 중지
  - 확실하게 교착상태를 깨뜨리지만 비용이크다.
  • 프로세스가 오랫동안 연산했을 가능성이 있고, 그 연산 결과를 반드시 폐기 후 다시 계산해야 하기 때문이다.
    

• 교착 상태가 제거될 때까지 한 프로세스씩 중지
  - 중지시킬 때마다 교착상태 탐지 알고리즘을 호출해야 하므로, 오버헤드가 크다.
  

프로세스를 중지시키기는 쉽지 않다. 프로세스가 파일을 갱신하는 도중이었다면, 그 시점에 종료시 파일은 부정확한 상태가 된다.

종료 프로세스 선택시 결정 요인

1. 프로세스의 우선순위가 무엇인지
2. 프로세스가 수행된 시간과 지정된 일을 종료하는데 더 필요한 시간
3. 프로세스가 사용한 자원의 유형과 수
4. 프로세스가 종료하기 위해 더 필요한 자원의 수
5. 얼마나 많은 수의 프로세스가 종료되어야 하는지

8.8.2 자원 선점

교착상태가 깨질 때까지 프로세스로부터 자원을 선점하여 다른 프로세스에 주어야 한다.

선점이 필요할 때 다음 세가지사항을 고려한다.

1. 희생자 선택

   • 비용을 최소화하기 위해 선점의 순서를 결정해야 한다.

2. 후퇴

   • 자원을 선점당한 프로세스는 정상적 실행히 불가능 -> 안전한 상태로 후퇴시키고, 다시 시작한다.

   • 실행하는 모든 프로세스의 상태에 보다 많은 정보를 유지할 것을 필요로 한다.

3. 기아 상태

   • 계속해서 같은 프로세스가 선점된다면 해당 프로세스는 기아상태에 있게 된다.
   • 비용 요소에 후퇴 횟수를 포함하여 해결한다.