교착 상태 : 자원을 소유한 채, 모두 상대방이 소유한 자원을 기다리면서 무한 대기

식사하는 철학자 문제

철학자들의 교착상태 원인과 해결

• 교착상태 원인 - 환형 요청/대기(circular wait)
  - 5명 모두 왼쪽 포크를 가지고 오른쪽 포크를 요청하는 환형 고리
  - 환형 고리는 스스로 인식이나 해체 불가
• 교착 상태 해결 - '환형 대기'가 생기지 않도록
  - 마지막 철학자(5번)만 오른쪽 포크를 먼저 잡고 왼쪽을 잡도록 규칙 수정
  

식사하는 철학자 문제는 교착 상태 문제를 비유

• 교착상태는 다중프로그래밍 시스템 초기에 노출된 문제점
  - 철학자 : 프로세스
  - 포크 : 자원
  - 스파게티 : 프로세스가 처리할 작업
  

교착상태

1) 교착상태(deadlock)

• 자원을 소유한 스레드들 사이에서, 각 스레드는 다른 스레드가 소유한 자원을 요청하여 무한정 대기하고 있는 현상
  - deadly embrace : 풀지 못하는 포옹
  - 교착상태 문제는 1965년 Dijkstra의 banker's algorithm research 에서 처음 제기
  2) 교착상태 발생 위치
• 사용자가 작성한 멀티스레드 응용프로그램에서 주로 발생
  - 정교하지 못한 코딩에서 비롯
• 커널 내에서도 발생
  - 거의 발생하지 않음, 매우 정교하게 작성되기 때문
• 교착상태를 막도록 운영하는 컴퓨터 시스템은 거의 없는 실상
  - 막는데 많은 시간과 공간의 비용이 들기 때문
  - 교착상태가 발생하도록 두고, 교착상태가 발생한 것 같으면, 시스템 재시작, 혹은 의심스러운 몇몇 프로그램 종료

3) 교착생태의 전형적인 발생 상황

• 2개의 스레드가 각각 락 소유, 상대가 가진 락 요청하고 기다릴 때
  - 단일 CPU/ 다중 CPU 모두에서 발생, T1과 T2가 서로 다른 CPU에서 실행될 때도 발생
• 락과 자원에 대한 경쟁이 있는 한 교착상태는 언제든 발생 가능

교착상태를 유발시킬 수 있는 컴퓨터 시스템의 잠재적 요인

1. 자원

• 교착상태의 발생지
  - 교착상태는 멀티스레드가 자원을 동시에 사용하려는 충돌이 요인
• 컴퓨터 시스템에는 많은 자원 존재
  - 소프트웨어 자원 - 뮤텍스, 스핀락, 세마포, 파일, 데이터베이스, 파일 락
  - 하드웨어 자원 - 프린터, 메모리, 프로세스 등
  

2. 자원과 스레드

• 한 스레드가 여러 자원을 동시에 필요로 하는 상황이 요인

3. 자원과 운영체제

• 한 번에 하나씩 자원을 할당하는 운영체제 정책이 요인

4. 자원 비선점

• 할당된 자원은 스레드가 자발적으로 내놓기 전에 강제로 뺏지 못하는 정책이 요인
  - 운영체제는 스레드가 가진 자원을 강제로 뺏지 못함
  - 만일 강제로 빼앗을 수 있다면? 교착상태가 발생하지 않게 할 수 있다.
  

교착상태 모델링

1) 자원 할당 그래프(Resource Allocation Graph, RAG)

• 그래프의 요소
  - 꼭지점 - 스레드, 자원
  - 간선 - 소유/요청 관계. 할당 간선과 요청 간선
  1) 할당 간선 : 자원에서 스레드로 향하는 화살표. 할당 받은 상태 표시
  2) 요청 간선 : 스레드에서 자원으로 향하는 화살표. 요청 표시
  
• 자원에 대한 시스템의 상태를 나타내는 방향성 그래프
  - 컴퓨터 시스템에 실행 중인 전체 스레드와 자원의 개수
  - 각 자원의 총 인스턴스 개수와 할당 가능한 인스턴스 개수
  - 각 스레드가 할당받아 소유하고 있는 자원의 인스턴스 개수
  - 각 스레드가 실행에 필요한 자원 유형과 인스턴스 개수

2) 자원할당 그래프를 통해 교착상태 판단

• 교착상태 예방, 회피, 감지를 위한 알고리즘 개발에 필요

교착상태가 발생하는 프로그램 만들기

#include <stdi.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>

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

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* worker2(void* arg){ //스레드 코드
	pthread_mutex_lock(&lock2); //y를 독점 사용하기 위해 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); //lock2 풀기
    printf("%s lock2 해제\n", (char*)arg);
}

int main(){
	char *name[] = {"황기태", "이찬수"};
    pthread_t tid[2];
    
    pthread_mutex_init(&lock1, NULL); //뮤텍스 락 변수 lock1 초기화
    pthread_mutex_init(&lock2, NULL); //뮤텍스 락 변수 lock2 초기화
    
    pthread_create(&tid[0], NULL, worker1, name[0]); //worker1 스레드 생성
    pthread_create(&tid[1], NULL, worker2, name[1]); //worker2 스레드 생성 
    
    pthread_join(tid[0], NULL);
    pthread_join(tid[1], NULL);
    
    pthread_mutex_destroy(&lock2);
    pthread_mutex_destroy(&lock1);
    
    printf("x = %d, y = %d\n", x, y);
    
    return 0;
}

교착상태 해결

교착상태가 발생하는 4가지 필요충분 조건

1) 코프만 조건

• 교착상태가 발생하는 4가지 필요충분 조건
  - Computing Survey, Vol.3, No.2, June, 1971에 실린 논문
  
• 다음 4가지 상황이 허용되는 시스템은 언제든 교착상태 발생 가능
  1) 상호배제
  - 각 자원은 한 번에 하나의 스레드에게만 할당
  - 자원이 한 스레드에게 할당되면 다른 스레드에게는 할당될 수 없음
  2) 소유하면서 대기(Hold & Wait)
  - 스레드가 한 사원을 소유(lock) 하면서 다른 자원을 기다리기
  3) 강제 자원 반환 불가(No Preemption)
  - 스레드에게 할당된 자원을 강제로 빼앗지 못함
  4) 환형 대기(Circular Wait)
  - 한 그룹의 스레드들에 대해 각 스레드는 다른 스레드가 요청하는 자원을 소유하는 원형 고리 형성
  

** 4가지 조건 중 한 가지라도 성립되지 않으면 교착상태 발생 X

교착상태로 인해 시스템 전체가 중단되지는 않는다. 교착상태는 시스템 내에 몇몇 스레드들 사이에서 발생하므로 이들 스레드들만 실행이 중지된 채 대기상태에 머물며, 이들로 인해 시스템 전체가 불능 상태가 되는 것은 아니다. 시스템 관리자나 이들 스레드들을 제거하면 이들의 교착상태는 사라진다. 만일 많은 스레드들이 교착상태에 연루되어 있을 때는 시스템을 재시작 하는 것 좋다.

교착상태 예방

** 코프만의 4가지 조건 중 최소 하나를 성립하지 못하게 함
1. 상호배제 조건 -> 상호배제 없애기

• 동시에 2개 이상의 스레드가 자원을 활용할 수 있도록 함
• 컴퓨터 시스템에서 근본적으로 적용 불가능한 방법

2. 소유하면서 대기 조건 -> 기다리지 않게

• 방법1 : 운영체제는 스레드 실행 전 필요한 모든 자원을 파악하고 실행시 한 번에 할당
  -> 당장 사용하지 않는 자원을 스레드에게 묶어 두기 때문에 자원 활용률이 떨어짐
  -> 다른 스레드는 필요한 자원을 할당 받지 못하고 실행 대기

• 방법2 : 스레드가 새로운 자원을 요청하려면, 현재 할당 받은 모든 자원을 반환하고, 한꺼번에 요청하여 할당

=> 방법1이나 방법2 모두 가능하지 않거나 매우 비효율적인 방법

3. 강제 자원 반환 불가 조건 -> 선점 허용

• 자원을 강제로 반환하게 된 스레드가 자원을 다시 사용하게 될 때 이전 상태로 되돌아갈 수 있도록 상태를 관리할 필요
• 간단히 않고 오버헤드도 매우 큼

4. 환형 대기 조건 -> 환형 대기 제거

• 모든 자원에게 번호를 매기고, 번호순으로 자원을 할당 받게 함

교착상태 회피

• 자원 할당 시, 미래에 환형 대기가 발생할 것으로 판단되면 자원 할당을 하지 않는 정책

• banker's 알고리즘으로 해결
  1) Edsger Dijkstra 에 의해 개발된 알고리즘. 자원 할당 전에 미래에 교착상태가 발생하지 않을 것인지 안전한지 판단하는 알고리즘
  - 은행에서의 대출 알고리즘

  2) 안전한 상태
  - 현재 프로세스들을 어떤 순서로 실행시켰을 때, 모든 프로세스들이 자신이 요청하는 자원을 가지고 실행할 수 있다면 안전한 상태

  3) 불안전한 상태
  - 환형 대기에 빠질 수 있다면 불안전한 상태

  4) 알고리즘
  - 각 프로세스가 실행 시작 전에 필요한 전체 자원의 수를 운영체제에게 알림
  - 자원을 할당할 때마다, 자원을 할당해주었을 때 교착상태가 발생하지 않을 만큼 안전한 상태인지 판단하여 안전한 상태일 때만 자원할당
  - 각 프로세스가 필요한 자원의 개수, 현재 각 프로세스가 할당 받은 자원의 개수, 그리고 시스템 내 할당 가능한 자원의 개수를 토대로 현재 요청된 자원을 할당해도 안전한지 판단

  5) 비현실적
  - 각 프로세스가 실행 전에 필요한 자원의 개수를 아는 것은 불가능
  - 프로세스의 개수도 동적으로 변하기 때문에 미리 프로세스의 개수를 정적으로 고정시키는 것은 불가능
  

교착상태 감지 및 복구

1) 교착상태를 감지하는 프로그램을 통해, 형성된 교착상태를 푼다.

• 백그라운드에서 교착상태를 감지하는 프로그램 늘 실행

2) 교착상태를 감지하였을 때의 복구 방법

• 자원 강제 선점
  -> 교착상태에 빠진 스레드 중 하나의 자원을 강제로 빼앗아 다른 스레드에게 할당

• 롤백
  -> 운영체제는 주기적으로 교착상태가 발생할 것으로 예측도는 스레드의 상태를 저장하여 두고 교착상태가 발생하면 마지막으로 저장된 상태로 돌아가도록 하고, 다시 시작하면서 자원을 다르게 할당

• 스레드 강제 종료
  -> 교착상태에 빠진 스레드 중 하나 강제 종료
  -> 가장 간단하면서도 효과적인 방법

• 시간과 메모리 공간(rollback의 경우)에 대한 부담이 크기 때문에 잘 사용하지 않음

교착상태 발생위치 - 교착상태는 사용자가 작성한 멀티스레드 응용프로그램에서 주로 발생하며 개발자의 미숙한 멀티스레드 코딩에서 비롯된다. 교착상태는 커널 내에서도 발생할 수 있지만 거의 발생하지 않는다. 커널의 최고의 개발자들에 의해 매우 정교하게 작성되어 있기 때문이다.

교착상태 무시 : 타조 알고리즘

1) 교착상태를 해결할 필요가 있을까?

• 교착상태에 대한 통계치는 없다.
• 교착상태는 반드시 발생
  - 하지만 교착상태의 발생 가능성이 극히 적고
  - 교착상태를 피하기 위한 비용이 많이 들어감
  

2) 타조알고리즘

• Put your head in the sand 접근법
  - 타조가 머리를 모래 속에 박조 자신이 보이지 않는 척하는 것
  - 교착상태는 발생하지 않을 거야하고 아무 대책을 취하지 않는 접근법
  
• Unix 와 Window 등 현재 거의 모든 운영체제에서 사용
  - 의심가는 스레드를 종료시키거나 시스템 재시작
  - 거의 발생하지 않거나 아주 드물게 발생하는 것에 비해 교착상태 해결에는 상대적으로 비용이 많이 들기 때문

3) 주의

• 핵 시스템, 비행기, 미사일 등 시스템 재시작이 파국을 초래할 hard real-time 시스템이나 환자 감지 시스템 등에서는 적합하지 않음
  - 이런 시스템에서는 자원에 대한 프로세스의 할당 등에 대해 미리 알고 적절한 조치가 필요

교착상태를 다루는 현실적인 방안

• 대부분의 운영체제 : ostrich 알고리즘 사용
• 교착상태가 일어나지 않을 것으로 가정하고, 교착상태에 대한 아무 대책을 세우지 않음
  - 교착상태가 발생할 확률은 극히 작음
• 교착상태 예방, 회피, 감지에는 많은 오버헤드가 소모되므로
• 교착상태가 발생하면 시스템 재시작 혹은 특정 프로세스/스레드 강제 종료
  - 관련된 데이터를 잃어버릴 수 있음
  - 하지만 전체적으로 크지 않은 손실

이 글이 문제가 된다면 삭제하겠습니다.