교착상태(Deadlock)

<교착 상태(Deadlock)>
- 시스템 측면에서 자원의 요구가 뒤엉킨 상태
  - 한 스레드 집합 내의 모든 스레드가 그 집합 내의 다른 스레드에 의해서만
    발생될 수 있는 사건을 서로 무한히 기다리는 상황

- 다중 프로그래밍 환경에서
  - 둘 이상의 스레드가
  - 서로 상대방의 작업을 끝나기만을 기다리기에
  - 결과적으로 아무것도 하지 못하는 상태

- 병행 처리 기술과 자원 공유에 따른 일종의 부작용



<Bridge Crossing Example>
- 교각을 자원에 비유
- 교착상태가 발생하면 한쪽의 차가 후진해야 해결될 수 있음
  - 때로는 몇몇의 차가 모두 후진해야 할 수도
- 기아 상태가 가능
- 대부분의 OS에서 교착상태를 완전히 예방해주지는 못함




<교착상태의 발생과 처리>
- 커널 내에서는 거의 발생하지 않음
  - 매우 정교하게 작성되기 때문
 
- 멀티 스레드 app에서 주로 발생
  - 정교하지 못한 코딩에서 비롯됨

- 교착상태를 막도록 운영하는 컴퓨터 시스템은 거의 없다
  - 많은 시간과 공간의 비용이 들기 때문
  - 교착 상태 허용 -> app 갖에 종료 혹은 재시작




<전형적인 멀티 스레드 교착 상태 사례>
- 2개의 스레드가 각각 락을 소유하고 있으면서 상대가 가진 락을 요청하고 기다릴 때
- ex)
void* thread1(void*a)
{
...
pthread_mutex_lock(&LockA);  //교착상태 발생 가능
...
pthread_mutex_lock(&LockB); //교착상태 발생 가능
...
pthread_mutex_unlock(&LockB);
...
pthread_mutex_unlock(&LockA);
}

void* thread2(void*a)
{
...
pthread_mutex_lock(&LockB);  //교착상태 발생 가능
...
pthread_mutex_lock(&LockA);  //교착상태 발생 가능
...
pthread_mutex_unlock(&LockA);
...
pthread_mutex_unlock(&LockB);
}






<교착 상태 발생 예>
#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>

int x = 0; //공유 변수
int y = 0; //공유 변수
pthread_mutex_t lock1; //x를 위한 뮤텍스 락 변수
pthread_mutex_t lock2; //y를 위한 뮤텍스 락 변수

void* worker1(void* arg); //void*어떤 변수든지 받을 수 있는 범용 return
void* worker2(void* arg);

int main(void){
char* name[] = {"황기태", "이찬수"};
pthread_t_tid[2];

pthread_mutex_init(&lock1, NULL); //뮤텍스 락 변수
pthread_mutex_init(&lock2, NULL); //뮤텍스 락 변수

pthread_create(&tid[0], NULL, worker1, name[0]); //worker1 스레드 생성
pthread_create(&tid[1], NULL, worker2, name[0]); //worker1 스레드 생성

pthread_join(tid[0], NULL);
pthread_join(tid[1], NULL);

pthread_mutex_destory(&lock2);
pthread_mutex_destory(&lock1);

printf("x = %d, y = %d\n", x, y);

return 0;
}
-----------------------------------------------------------------------------
void* worker1(void* arg) //스레드 코드
{
pthread_mutex_lock(&lock1); //x를 독점 사용하기 위해 lock1 잠그기
printf("%s lock1 잠금\n", (char*)arg);
x++;
sleep(2); //2초 잠자기

pthread_mutex_lock(&lock2); //y를 독점 사용하기 위해 lock2 잠그기
printf("%s lock2 잠금\n", (char*)arg);
y++;
pthread_mutex)unlock(&lock2); //lock2 풀기
printf("%s lock2 해제\n", (char*)arg);

pthread_mutex_unlock(&lock1); //lock1 풀기
printf("%s lock1 해제\n", (char*)arg);
}

void* worker1(void* arg) //스레드 코드
{
pthread_mutex_lock(&lock2); //x를 독점 사용하기 위해 lock2 잠그기
printf("%s lock2 잠금\n", (char*)arg);
y++;
sleep(2); //2초 잠자기

pthread_mutex_lock(&lock1); //x를 독점 사용하기 위해 lock1 잠그기
printf("%s lock1 잠금\n", (char*)arg);
x++;
pthread_mutex)unlock(&lock1); //lock1 풀기
printf("%s lock1 해제\n", (char*)arg);

pthread_mutex_unlock(&lock2); //lock1 풀기
printf("%s lock2 해제\n", (char*)arg);
}



 

<스레드의 자원 이용 절차>
- 시스템 호출에 의해 이루어짐
  - 요청
    - 필요한 자원을 요청
    - 요청이 즉시 받아들여지지 않으면 대기함
  - 사용
    - 요청한 자원을 사용
  - 해제
    - 자원 사용을 마친 후 할당 받은 자원을 반환

- OS는 스레드가 자원 요청시 할당 받을 수 있도록 항상 확인하고 기록함




<교착상태를 유발시킬 수 있는 잠재적 요인>
- 공유자원
  - 소프트웨어 자원 : 뮤텍스, 스핀락, 세마포어, 파일락 등
  - 하드웨어 자원 : 메모리, 프린터, 프로세서 등

- 한 스레드가 여러 자원을 동시에 필요로 할 때
  - 다수의 스레드가 자원을 동시 사용하려 할 때
 
- 한 번에 하나씩 자원을 할당하는 OS의 정책

- 자원의 비선점




<교착상태 발생 필요충분 조건 : 코프만 조건>
- 다음 네 조건이 동시 성립 때 발생
  - 상호 배제(mutual exclusion)
    - 최소 하나 이상의 자원이 비공유 모드로 점유되어야 한다
 
  - 점유하며 대기(hold-and-wait)
    - 최소한 자원 하나를 점유한 채, 다른 스레드에 의해 점유된 자원을 추가로 얻기 위해 대기

  - 비선점(no preemption)
    - 점유된 자원은 다른 스레드에 의해 선점될 수 없다

  - 순환(환형)대기(circular wait)
    - 스레드들이 체인을 구성하여 자원을 상호 요청




<자원 할당 그래프(Resource-Allocation Graph, RAG)>
- 교착상태를 보다 정확히 기술하는 방법
  - 자원에 대한 시스템의 상태를 나타내는 방향성 그래프

- G = (V, E)
  - 정점(vertex)의 집합 V와
    - 시스템 내의 모든 활성 스레드들의 집합 P
      - P = {P1, P2, ..., Pn} //원으로 표현
    - 시스템 내의 모든 자원 유형의 집합 R
      - R = {R1, R2, ..., Rm} //사각형으로 표현

  - 간선(edge)의 집합 E로 구성
    - 요청 간선(Request edge) : Pi -> Rj
    - 할당 간선(Assignment edge) : Rj -> Pi




<자원 할당 그래프의 예>
- 그래프가 사이클을 포함하지 않으면 어느 프로세스도 교착상태가 아니다
  - 집합
    P = {P1, P2, P3}
    R = {R1, R2, R3, R4}
    E = {P1->R1, P2->R3, R1->P2, R2->P2, R2->P1, R3->P3}

  - 프로세스 상태
    - 프로세스 P1은 자원 R2의 한 개를 점유하고 자원 R1을 기다린다
    - 프로세스 P2는 자원 R1과 R2를 각각 한개씩 점유하고 자원 R3을 기다린다
    - 프로세스 P3은 자원 R3을 점유하고 있다




<교착상태의 자원 할당 그래프>
- 각 자원 유형이 단 하나의 인스턴스만 가지면,
  - 하나의 사이클은 교착상태를 발생을 암시

- 각 자원 유형이 여러 개의 인스턴스를 가지면
  - 사이클은 교착상태가 존재하는 필요조건일 뿐 충분조건은 아님
  - ex) P3 -> R2를 가정할 때
    - 두 개의 사이클이 존재하고 
    - 교착상태 




<사이클은 있으나 교착상태가 아닌 경우>
- 자원할당 그래프에서 사이클이 없다면 시스템은 교착상태가 아니다
- 사이클이 있다면 시스템은 교착상태일 수도 있고, 아닐 수도 있다





<자원 할당 그래프와 교착상태 여부>
- 자원 할당 그래프에,
  - 사이클이 없다면 교착상태는 발생하지 않음
 
  - 사이클이 있다면,
    - 자원마나 하나의 인스턴스만 있다면 교착상태 발생 가능성이 높음
    - 자원마다 다수의 인스턴스가 있다면 교착상태 발생 가능성이 높지 않다




<교착상태 해결 기법>
- 교착상태 예방(Deadlock Prevention)
  - 교착상태 발생 요건 중 하나라도 발생하지 않게 한다

- 교착상태 회피(Deadlock Avoidance)
  - 자원 할당 전에 미리 스레드의 수행 상태를 파악하여 자원이 할당될 경우를 가정하여 교착상태가 발생하면 자원 할당을 중지

- 교착상태 탐지 & 복구(Detection & Recovery)
  - 교착상태가 발생을 탐지하여 시스템에 문제가 발생하지 않도록 조치를 취함

- 교착상태 무시(Ignore) - OS의 일반적 선택
  - 교착상태가 발생하지 않는다 가정




<교착상태 예방(Deadlock Prenvetion) 기법>
- 상호배제 조건 방지?
  - 공유할 수 있는 자원들(ex. 읽기 전용 파일)
    -> 배타적 접근 불필요

  - 공유할 수 없는 자원들(ex. 프린터)
    -> 적절한 사용을 위해선 반드시 배타적 접근 필요

    - 따라서 교착상태를 방지할 목적으로 상호 배제가 일어나지 않게 해서는 안된다


- 방법 1 : 점유와 대기 조건 방지
  - 스레드가 자원을 요청할 때에는 다른 자원들을 점유하지 않음을 보장해야 한다
    - 방법 1-1 : 각 스레드는 실행 전에 필요한 모든 자원을 요청하여 할당 받아야 한다

    - 방법 1-2 : 각 스레드는 실행 위에 일부 자원들만 요철 할 수 있되, 추가적인 자원 요청은 어떤 자원도 갖고 있지 않을 때만 허용
      - 스레드가 자원을 요청하려면 먼저 자신에게 할당된 자원들을 방출해야한다

  - 자원 이용률이 낮고 기아상태 발생 가능
 
- 방법2-1 : 비선점 조건 방지
  1. 스레드가 즉시 할당될 수 없는 자원을 요청하게 되면 이미 자신에게 할당된 자원마저 강제 회수된다
  2. 선점된(강제 회수된) 자원은 현재 스레드가 기다리는 자원 목록에 추가된다
  3. 스레드는 현재 요청한 자원 뿐만 아니라 강제 회수된 자원들까지 다시 획득했을 때 다시 시작 가능
  - 이미 실행한 작업의 상태를 잃을 수 있다
    - 작업 상태를 쉽게 저장/복구 가능할 때나
    - 빈번하게 발생하지 않을 때만 좋은 방법

- 방법 2-2 : 비선점 조건 방지
  - 스레드 Ti가 자원을 요청하면,
    - IF(자원을 할당 가능한가)
      THEN[Ti에 자원을 할당]
      ELSE
IF(추가 자원을 위해 대기하고 있는 다른 스레드에게 할당되었는가)
THEN[Ti가 해당 자원을 선점]
ELSE
   [Ti 대기] //다른 스레드가 선점 자원을 요청하면 해제
ENDIF
         ENDIF

- 방법 2-3
  - 높은 우선순위의 스레드가 자원을 선점할 수 있도록

- 방법 3 : 순환 대기 조건 방지
  - 계층적 요구 기법
    1. 모든 자원에 순서를 부여
      - 각 자원은 고유한 정수 번호를 가진다
    2. 각 스레드들은 열거된 순더대로 자원을 요청하도록 요구
      - 각 스레드는 오름차순으만 자원 요청 가능
      - 모두 방출 후 재요청
  - 순환대기의 가능성을 제거하여 교착상태 예방
  - 자원에 대한 접근을 불필요하게 거부하기에 비효율적
  - 사용자가 손쉽고 편리하게 응용 프로그램 작성하는데 어려움




<교착상태 회피(Deadlock Avoidance)기법>
- 교착상태 예방 기법의 문제점
  - 교착상태 예방은 장치의 효율성을 낮추고 시스템 처리량을 감소시킴

- 교착상태 회피 기법
  - 목적 
    - 교착상태의 예방보다 덜 엄격한 조건을 요구함으로써 자원을 좀 더 효율적(병행성 향상)으로 이용
 
- 방법 
  - 교착상태가 일어날 가능성을 인정
  - 교착상태가 일어나려고 할 때 적절히 피함




<교착상태 회피 알고리즘>
- 자원이 어떻게 사용될 지에 대한 추가 정보를 제공토록 요구
  - 각 프로세스는 자신의 필요한 각 유형의 자원들의 최대 수를 선언토록 요구
    - 각 요청과 해제에 대한 정확한 순서를 파악하여 요청에 따른 프로세스 대기 여부를 결정
 
  - 이 값을 바탕으로 교착상태가 발생하지 않을 알고리즘을 만듦
    - 시스템이 순환 대기 조건이 발생하지 않도록 자원 할당 상태를 검사함
      - 사용 가능한 자원의 수, 할당된 자원의 수, 프로세스들의 최대수에 의해 정의




<(교착상태 회피 중)안정 상태 vs. 불안정 상태>
- 안정 상태(Safe State)
  - 프로세스들이 요청한 모든 자원들을 교착상태 발생 없이 할당할 수 있는 상태
   - 안정 순서를 찾을 수 있는 경우
      - 순서 <P1, P2, ..., Pn>의 모든 프로세스들에 대해
        - Pi가 요청하는 자원ㅔ
          - 현재 사용 가능한 자원 + Pj(j<i)가 반납하는 자원으로 만족 가능
          - 즉시 만족할 수 없는 경우 Pi는 Pj가 수행을 마칠 때까지 대기
        - 같은 방식으로 Pi가 끝나면 P(i+1)은 필요한 자원을 얻을 수 있다

- 불안정 상태(Unsafe State)
  - 안정 순서를 찾을 수 없는 경우
    - 이때는 교착상태가 발생 가능





<불안정 상태와 교착상태>
- 시스템이 안정 상태
  - 교착상태는 발생하지 않음

- 시스템이 불안정 상태
  - 교착상태 발생 가능성 존재

- 회피
  - 시스템을 항상 불안정 상태에 들어가지 않게 하여 교착상태를 회피
    - 초기 안정상태에서, 자원 요청 시 자원 할당/대기 여부를 결정
    - 자원 할당 이후에도 안정 상태일 경우에만 할당을 허용





<기본적인 회피 알고리즘 예>
- 12개의 자원과 3개의 프로세스
  Process   T0에서 할당량   Max Needs
------------------------------------------------
  P0              5                    20
  P1              2                    4
  P2              2                    9
- 현재 여유 : 12 - (5+2+2) = 3개

- T0에선 안정 : <P1, P0, P2>
  - P1 : 2+2 == 4 / P0 : 5+1+4 == 10 / P2 : 2+0+10>9

- T1에서 P2가 1개 더 요청한다면
  - 즉시 할당시 불안정
    - P1 : 2+2 == 4
      P0 : 5+0+4<10 -> 교착상태 발생 / P2 : 3+0+4<9 -> 교착상태 발생





<회피 알고리즘>
- 각 자원 유형마다 단 하나의 인스턴스를 갖는 경우 
  - 자원 할당 그래프 이용

- 각 자원 유형마다 다수의 인스턴스를 갖는 경우
  - 은행가 알고리즘(Banker's algorithm) 이용





<자원 할당 그래프 기법>
- 예약 간선(Claim edge) 추가
  - Pi ---> Rj
    - 앞으로 Pi가 Rj를 요청할 것을 의미
    - 점선으로 표시

  - 예약 간선은 Pi가 Rj를 요청하면, 요청 간선은 Pi->Rj으로 변환
  - 요청 간선은 Pi에 Rj가 할당되면, 할당 간선 Rj->Pi으로 변환
  - Pi가 Rj를 방출하면 할당 간선은 다시 예약 간선 Pi->Rj으로 변환