교착 상태

junto·2024년 3월 14일

operating system

목록 보기

6/13

병행성 관련 문제는 일반적인 패턴을 가지고 있다고 한다. 먼저 비 교착 상태 오류가 과반수를 차지하고 그 중 원자성 위반과 순서 위반 오류가 대부분을 차지한다고 한다. 추가로 교착 상태와 교착 상태 발생 조건, 예방, 처리 방법에 대해서 알아본다.

1. 비 교착 상태 오류

1) 원자성 위반

Thread 1::
if (thd->proc_info) {
	...
	fputs(thd->proc_info, ...);
    ...
}

Thread 2::
thd->proc_info = NULL;

두 번째 쓰레드가 실행되면 필드의 값을 NULL로 설정하기에 fputs 함수는 NullPointerException이 발생한다.
thd->proc_info를 접근할 때 락을 사용하여 첫 번째 쓰레드가 thd->proc_info를 접근할 때 다른 쓰레드가 이를 NULL로 변경할 수 없게 한다.

Thread 1::
pthread_mutex_lock(&lock);
if (thd->proc_info) {
	...
	fputs(thd->proc_info, ...);
    ...
}
pthread_mutex_unlock(&lock);

Thread 2::
pthread_mutex_lock(&lock);
thd->proc_info = NULL;
pthread_mutex_unlock(&lock);

2) 순서 위반 오류

Thread 1::
void init() {
	mThread = PR_CreateThread(mMain, ...);
    ...
}

Thread 2::
void mMain() {
	mState = mThread->State;
    ...
}

쓰레드 1이 먼저 실행되지 않았다면 쓰레드 2를 실행할 때 NullPointerException이 발생한다.
이러한 오류를 수정하는 방법은 순서를 강제하는 것이다. 앞서 알아봤던 컨디션 변수가 적절하다.

Thread 1::
void init() {
	mThread = PR_CreateThread(mMain, ...);
    
	pthread_mutex_lock(&mtLock);
    mInit = 1;
    pthread_cond_signal(&mtCond);
    pthread_mutex_unlock(&mtLock);
    ...
}

Thread 2::
void mMain() {

	pthread_mutex_lock(&mtLock);
    while (mInit == 0)
    	pthread_cond_wait(&mtCond, &mtLock);
    pthread_mutex_unlock(&mtLock);
    
	mState = mThread->State;
    ...
}

2. 교착 상태(Deadlock) 오류

교착 상태는 왜 발생하는가?

아래 코드처럼 사이클(Cycle)이 발생하면 교착 상태가 발생할 수 있다. Thread1이 Lock1을 획득하고, Lock2를 기다리는 상황에서 Thread2는 Lock2를 획득하고 Lock1을 기다리기 때문이다.

Thread 1::               Thread 2::
Lock(L1);                lock(L2);
Lock(L2);                lock(L1);

또한, 캡슐화와 락은 잘 조화되지 않는다. 자바의 Vector 클래스에서 AddAll() 메소드를 살펴보자.

Vector v1, v2;
v1.AddAll(v2);

위의 메소드는 멀티 쓰레드에 안전해야 하므로 내부적으로 v1에 더해지는 벡터뿐만 아니라 인자로 전달되는 v2에 대한 락도 같이 획득해야 한다. 만약 어떤 쓰레드가 v2.AddAll(v1)을 거의 동시에 호출하게 된다면 교착 상태 발생 가능성이 있다.

1) 교착 상태 발생 조건

(1) 상호 배제(Mutual Exclusion)

쓰레드가 자신이 필요로 하는 자원에 대한 독자적인 제어권을 주장한다.

(2) 점유 및 대기(Hold and Wait)

쓰레드가 자신에게 할당된 자원(ex: 이미 획득한 락)을 점유한 채로 다른 자원을 대기한다.

(3) 비 선점(No preemption)

자원을 점유하고 있는 쓰레드로부터 자원을 강제적으로 빼앗을 수 없다.

(4) 순환 대기(Circular wait)

각 쓰레드는 다음 쓰레드가 요청한 하나 또는 그 이상의 자원을 갖고 있는 쓰레드들의 순환 고리가 있다.

위 네 조건 중 하나라도 만족시키지 않는다면 교착 상태는 발생하지 않는다고 한다.

2) 교착 상태 예방(Deadlock Prevention)

(1) 상호 배제(Mutual Exclusion)

일반적으로 코드는 임계 영역을 가지고 있기 때문에 상호 배제를 없애는 건 어렵다. 명시적으로 락이 필요 없는 강력한 하드웨어를 사용할 수 있다. 앞서 다룬 CompareAndSwap. 이와 같은 방식은 락을 획득할 필요는 없지만 무한 반복의 위험성은 존재한다.

(2) 점유 및 대기(Hold and Wait)

원자적으로 모든 락을 단번에 획득하도록 하면 교착 상태를 예방할 수 있다.
하지만 캡슐화 문제가 생긴다. 필요한 락들을 정확히 파악하고, 미리 획득하기란 어렵고 굉장히 병행성이 저하되는 문제가 발생할 수도 있다.

(3) 비 선점(No preemption)

락을 이미 보유하고 있는 상태로 다른 락을 대기하는 것은 교착 상태를 유발한다.
trylock()의 경우 락을 획득하거나 현재 락이 점유된 상태이니 락을 획득하기를 원하면 나중에 다시 시도하라는 것을 알리는 -1값을 리턴한다.
- 이를 이용하여 교착 상태 가능성이 없고 획득 순서에 영향을 받지 않는 락 획득 방법을 만들 수 있다. 교착 상태 가능성이 없지만 무한반복(livelock)이라는 새로운 문제가 발생한다.

lock(L1);
if (trylock(L2) == -1) {
	unlock(L1);
    goto top;
}

만약 사용하려는 락이 호출되는 루틴 깊숙한 곳에 존재한다면 처음 부분으로 되돌아가도록 구현하는 것이 어렵다는 문제도 존재한다.

(4) 순환 대기(Circular wait)

가장 간단한 방법은 락 획득을 하는 전체 순서(total ordering)을 정하는 것이다. 복잡한 시스템의 경우 교착 상태를 피하고자 부분 순서(partial ordering)을 제공하여 락 획득 구조를 만들 수 있다.
전체 또는 부분 순서를 제공하기 위해서는 세심하게 락 획득 전략을 설계해야 한다.
락 주소를 사용하여 락 요청 순서를 강제할 수 있다. (락 주소를 내림차순으로 획득하는 방식)

(5) 스케줄링으로 교착 상태 회피하기

여러 쓰레드가 어떤 락을 획득하게 될지 전반적으로 파악하고 있다면, 그것을 바탕으로 스케줄링하여 교착 상태가 발생하지 않도록 할 수 있다.
예를 들어 쓰레드들의 락 요청에 대한 정보가 아래와 같다.
T1과 T2만 동시에 실행하지 않는다면 교착상태가 발생하지 않는다. T3는 하나의 락만 필요하기 때문에 어떤 쓰레드든 함께 실행할 수 있다. (하나의 락만 필요하다면 교착 상태가 발생하지 않음)

Banker's Algorithm

전체 작업에 대한 모든 지식을 알고 있는 임베디드 시스템 같은 제한된 환경에서 유용한 방법이다.
할당 되고 남은 자원 {3, 3, 2}가 있지만, 문제가 생길 수 있을 때는 주지 않는다. 추가 요청 가능량. 가용자원만으로도 다 충분할 때는 주지만, 충분하지 않을 때는 주지 않는다.
그럼 초기값들은 어떻게 채워졌을까 하는 의문이 생길 수 있는데, 초기에는 가용자원으로 만족할 수 있기 때문에 줄 수 있었던 거라고 이해할 수 있다.
스케줄링으로 교착 상태를 회피하는 것은 보편적으로 사용하는 방법이 아니다.