[운영체제]chapter 08. Deadlock_#01 교착상태의 이해

Deadlocks #1 교착상태의 이해: 교착상태 방지 (Deadlock Prevention)

1. 시스템 모델 (System Model)

교착상태(Deadlock)이란 무엇인가?

• 교착상태란 어떤 다른 프로세스데 의해서 발생된 이벤트에 의해서 모든 프로세스가 대기하는 현상
• 요청한 자원을 다른 대기중인 쓰레드가 점유하고 있기 떄문에 자원을 요청한 대기중인 쓰레드(또는 프로세스)는 다시는 쓰레드 상태를 변경할 수 없다.

여러개의 경쟁하는 쓰레드 사이에 분배가 될 유한한 수의 자원으로 구성된 시스템을 고려해 본다

 

자원의 종류는 몇가지 동일한 인스턴스로 구성된다. 예를 들어 CPU 싸이클, 파일, 입출력 기기 (프린터, 드라이브 등)이 있다.

CPU 사이클이 4개의 코어로 구성되었다면 한번의 4개의 쓰레드를 수행할 수 있고 그 이후의 쓰레드는 대기해야 함

만약 어떤 한 쓰레드가 동일한 자원 유형의 인스턴스를 요청한다면 어떤 인스턴스의 할당이 요청을 만족하면 된다.

 

어떤 한 쓰레드는 자원이 필요할때  "자원 요청 -> 자원 사용 -> 자원 해제" 와 같은 순서로 사용할 수 있다. 여기서 자원의 사용은 임계 영역(Critical Section)을 의미하여 임계 영역에는 여러개의 자원을 사용하는 것을 의미함

 

2. 멀티 쓰레딩 어플리케이션의 교착상태

교착상태 Deadlocks는 어떻게 발생하는가?

교착상태의 대표적인 사례는

1. 어떤 한 프로세스가 A라는 자원을 점유한 상태에서 B라는 자원을 점유하고자 할때 발생

2. B 자원을 가지고 있는 프로세스가 A자원을 점유하고자 할때  발생

위 상황을 코드로 표현하면,

pthread_mutex_t first_nutex;
pthread_mutex_t second_nutex;

pthread_mutex_init(&first_nutex, NULL);
pthread_mutex_init(&second_mutex, NULL);

/* thread_one runs in this function */
void* do_work_one(void* param)
{
	pthread_mutex_lock(&second_nutex);
    pthread_mutex_lock(&first_mutex);
    pthread_exit(0);
}
/* thread_two runs in this function */
void* do_work_two(void* param)
{
	pthread_mutex_lock(&second_mutex);
    pthread_mutex_lock(&frist_mutex);
    /* Do Some work */
    pthread_mutex_unlock(&first_mutex);
    pthread_mutex_unlock(&second_mutex);
    pthread_exit(0)
}

• 쓰레드 A는 do_work_one 함수를 수행하고 쓰레드 B는 do_work_two 함수를 수행한다고 가정한다
• 만약 쓰레드 A가 first_mutex lock을 가지고 쓰레드 B가 second_mutex lock을 가진다고 가정한다
• 그리고 쓰레드 A는 second_mutex의 lock을 가지고자 second_mutex Lock이 해제될때까지 대기한다
• 쓰레드 A,B 서로 가지고 있는 lock이 해제되기를 바라면서 대기하게 되며 교착상태가 발생한다.

3. 교착 상태의 특징

교착 상태 발생 조건 4가지

다음과 같이 교착 상태가 발생하기 위해서는 4가지 조건을 만족해야한다.

1. 상호배제(Mutual Exclusion)

    - 최소 한개의 자원이 임계 영역에서 점유 됨

2. 점유와 대기 (Hold and Wait)

    - 어떤 한 쓰레드가 최소 한개의 자원을 점유하고 다른 쓰레드가 가지고 있는 추가적인 자원을 얻고자 대기하게 되면 교착상태 발생 조건을 만족한다.

3. 선점 불가 (No preemption)

    - 자원들이 선점이 불가능할 때 교착상태 발생 조건을 만족한다.

    - 자원들의 종류에는 cpu 사이클, 파일, 입출력 기기들이 존재한다.

4. 원형 대기 (Circular Wait)

    - 대기중인 쓰레드들의 집합이 종속적인 대기 그래프가 원형이 존재할 때 발생한다.

    - 예를 들어 A 쓰레드가 B쓰레드의 자원을 원하고 B쓰레드가 C쓰레드의 자원을 원한 상태에서 C쓰레드가 A쓰레드의 자원을 원한다면 이와같은 형태를 원형 대기라 한다.

    - 원형 대기는 최소 2개 이상의 쓰레드에서 발생할 수 있다.

 

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

• 자원 할당 그래프는 교착상태를 더 쉽게 이해하기 위한 방향성 그래프
• 자원 할당 그래프는 정점의 집합과 V와 간섭의 집합 E로 구성
• 정점의 두가지 종류
  • T = {T1, T2,T3....Tn}: 시스템에서 활성화 된 쓰레드의 집합
  • R = {R1,R2,,,,,,,Rn}: 시스템에서 모든 자원 유형의 집합
• 방향성 간선: Ti -> Rj (요청 가선)
  • 쓰레드 i가 자원 Rj를 요청한다.
• 방향성 간선: Rj -> Ti (할당 간선)
  • 자원 Rj가 쓰레드 i에게 할당 되는 것을 의미

자원-할당 그래프

• 쓰레드 1에는 first_mutex lock이 할당되어 있고, second_mutex 자원을 요청하는 상태
• 쓰레드 2에는 second_mutex lock이 할당 되어 있고, first_mutex자원을 요청하는 상태
• 자원-할당 그래프를 보아서 어플리케이션이 교착상태가 일어날 가능성이 있는지 파악할 수 있음

자원-할당 그래프를 집합으로 표현

• 다음 집합을 통해서 쓰레드 T1은 R1 자원을 요청하고 T2는 R3 자원을 요청한 상태
• 자원 할당 상황은 T1에는 R2 자원이 할당됨, T2에는 R1,R2 가 할당됨, T3에는 R3가 할당됨
• 쓰레드 T3은 작업을 언젠가 마치고 T2 -> T1 순으로 자원을 할당받게 되어서 수행을 마칠것. 즉, 교착상태가 발생하지 않음

교착상태가 발생하는 자원-할당 그래프

• 핵심은 R2가 T1과 T2에 할당되어 있기 떄문에 원형 대기가 발생하여 교착상태가 발생

교착상태가 발생하지 않는 자원-할당 그래프

 

• T1-> R1 -> T3 -> T2로 원형이 생성되었지만 R1과 R2자원 유형은 인스턴스가 각각2개이다.
• T2와 T4가 작업을 마치고, R1, R2자원을 반환하면서 T3,T1도 작업을 마칠 수 있기 때문에 교착상태가 발생하지 않음

자원 할당 그래프로 보는 교착상태

• 자원 할당 그래프가 원형cycle을 가지고 있지 않다면 교착상태가 확정적으로 발생하지 않음
• 자원 할당 그래프가 원형 cycle을 가지고 있더라도 교착상태가 무조건적으로 발생하지는 않음

4. 교착 상태를 다루기 위한 방법

교착상태를 벗어나기 위한 3가지 방법

1. 문제를 완전히 무시하는 방법
   • 마치 시스템에서 교착 상태가 무조건 발생하지 않는척함
2. 교착 상태를 방지 prevent하거나 회피 Avoid 하는 방식을 사용
   • 교착상태 방지 : 교착 상태로 진입하는 것을 절대로 방지하는 방식. 하지만 교착상태 방지는 거의 불가능한 방법
   • 교착상태 회피: Banker's Algorithm
3. 교착 상태가 발생하는 것을 허용하는 방법
   • 단, 탐색 Detect하고 회복 Recover하는 절차를 수행
   • 교착상태 탐색: 교착상태가 발생하는지 탐색하는 연산
   • 교착상태 회복: 교착상태가 발생하기 이전으로 되돌아가는 연산

5. 교착상태 방지 (Deadlock Prevention)

• 교착 상태 방지의 아이디언은 교착상태가 발생하는 조건 4가지 (상호배제, 점유와 대기, 선점불가, 원형 대기) 중 하나가 발생하는 것을 막는 방법

상호 배제 (Mutual Exclusion)을 방지하는 방법

• 상호 배제가 발생하는 조건은 최소 하나의 차원이 공유 불가능 해야한다는 점이다
• 반대로 방치하기 위해서는 모든 자원이 공유되면 교착상태를 막을 수 있다는 주장. 하지만 일반적으로 이방법은 대부분의 어플리케이션에 적용할 수 없는 방법이다.
  • 몇몇 자원들은 본질적으로 공유가 되면 안되기 때문,
  • ex) 뮤텍스 락 같은 자원의 경우에는 여러 쓰레드에 의해서 공유되면 안되는 자원이다
• 즉, 상호 배제를 방지하는 방법은 불가능한 방법이다.

점유와 대기(Hold and Wait)을 방지하는 방법

• 점유와 대기를 방지하는 방법은 어떤 한 쓰레드가 자원을 요청할 때 이미 점유하고 있는 자원을 해제한 다음 요청하는 방식이다.
• ex) 어떤 한 쓰레드가 A라는 자원을 요청할 때, B라는 다른 자원을 이미 점유하고 있다면, 점유하고 있는 A자원을 해제하고 요청한 B자원을 얻을떄까지 대기해야한다. 그리고 요청한 B자원을 얻은 다음에 이전에 해제한 A자원을 요청하여 자원을 얻음
• 하지만, 점유와 대기를 방지하는 방법은 대부분의 응용 프로그램에서는 비 실용적이다.

선점불가(No preemption)를 방지하는 방법

• 선점 불가를 방지하는  방법은 자원을 점유하고 있는 쓰레드에 대해서 선점하여  자원을 내려놓게 하는 방법
• ex) 어떤 한 쓰레드가 A라는 자원을  가지고 있는 상태에서 B라는 자원을 요청한다. 그런데 B자원은 다른 쓰레드가 점유하고 있는  상황이라면 다른  쓰레드가 갖고있는 B자원을 해제하게 하여 선점한다
• 점유와 대기를 방지하는 방법과 마찬가지로  이방법은 대부분의 응용 프로그램에서 일반적으로 적용할 수 없다.

원형 대기(circular Wait)를 방지하는 방법 : 가장 실용적인 방법

• 모든 자원 유형들에 순서를 지정
• 그리고 각각의 쓰레드가 자원을 오름차순으로 요청하는 것을 요구
• 내가 점유하고 있는  자원보다 높은 자원 유형들만 요청. 내가 점유하고 있는 자원보다 순서가 낮은 자원들은 요청하는 것을 막음
• 하지만 이와같은 방법은 기아Stravation 발생가능성이  높아지는 단점이 있다
• 교착상태 방지를 보장할 수는 없다.

void transaction(Account from, Account to, double amount)
{
	mutex lock1, lock2l;
    
    lock1 = get_lock(from);
    lock2 = get_lock(to);
    
    acquire(lock1);
    	acquire(lock2);
        	withdraw(from, amount(l
            deposit(to,amount)l
        release(lock2);
    release(lock1); 
}

transactionchecking_account, savings_account, 25.0)
trainsaction(saving_account, checking_account, 50.0)

• 위 transaction연산은 원자적인 연산이기 때문에 다른 쓰레드에 의해서 선점 될 수 없다.
• 하지만 문제가 되는 부분은 첫번째 transaction 연산중 두번째 transaction 연산이 발생하여 교착상태 문제가 발생할 수 있다.

정리

• 교착 상태는 상호배제, 점유와 대기, 선점 불가, 원형 대기인 4가지 조건이 만족하면 발생
• 교착상태를 해결하는 방법에는 무시, 방지,회피, 탐색후  회피가 있음
• 교착상태 방지 방법 중 상호배제, 점유와 대기, 선점 불가를 방지하는 방법은 실용적이지 못하고 원형 대기를 방지하는 방법은 가장 실용적이지만 교착상태를 방지하는 것을 보장하지는 못함

 

 

 

참고 : https://yonghwankim-dev.tistory.com/480