교착 상태(DeadLock)
교착 상태(Dead Lock) : 대기 중인 스레드들이 다시는 그 상태를 변경할 수 없는 경우
- 한 스레드 집합 내의 모든 스레드가 그 집합 내의 다른 스레드에 의해
발생될 수 있는 이벤트를 기다린다면, 이는 교착 상태임
- 요청한 자원들이 다른 스레드에 의해 점유되어 있고, 그들도 다 대기 상태에 있기 때문
- 한 스레드가 자원을 요청했을 때, 그 시각에 요청한 자원을 사용할 수 없는 상황
→ 해당 스레드는 대기 상태로 들어간다.
- 교착 상태가 없는 프로그램을 설계하는 것은 전적으로 프로그래머의 책임
시스템 모델(System model)
- 시스템은 경쟁 스레드들 사이에 분배되어야 할 유한한 수의 자원들로 구성됨
- 시스템 자원은 다수의 유형 혹은 클래스로 분할된다.
- 자원 유형 예시 : CPU 주기, 파일, 입/출력 장치, Mutex 락, 세마포
- 분할된 시스템 자원들은 동등한 다수의 인스턴스들로 구성된다.
- 네트워크라는 자원 유형이 2개의 인스턴스를 가질 수 있다.
- 한 스레드가 특정 자원 유형의 인스턴스를 요청
→ 동일 유형 자원의 임의의 인스턴스를 할당함으로써 요청 충족
- 자원은 일반적으로 논리적이다.
- But, 다른 유형의 이벤트도 교착 상태를 만들어 낼 수 있음
- 논리적인 자원 : mutex 락, 세마포 및 파일
- 다른 유형의 이벤트 : 네트워크 인터페이스로부터 읽기, IPC 기능 등
Mutex 락과 세마포
- 현대 시스템에서 가장 일반적인 교착 상태의 발원지
- 락은 일반적으로 특정 자료구조와 연관되어 있음
- 2개의 락이 다르게 쓰일 수 있음
- 하나의 락은 큐에 대한 접근을 보호하는 데 사용
- 다른 하나의 락은 연결 리스트에 대한 접근을 보호하는 데 사용
→ 이러한 이유로 락의 각 인스턴스에는 고유한 자원 클래스가 할당된다.
스레드(프로세스)의 자원 사용
- 스레드는 다른 프로세스의 자원을 사용할 수 있으며, 이에 대한 교착상태 발생 가능
- 스레드는 지정된 task를 수행하기 위해 필요한 만큼의 자원 요청 가능
- But, 요청 자원 수는 시스템 내에서 사용 가능한 전체 자원의 수를 초과할 수 없다.
- 시스템이 한 개의 네트워크 인터페이스밖에 없는데 2개 요청할 수 없음
자원 사용을 위해 스레드(프로세스)가 따라야 하는 순서
요청 : 스레드는 자원을 요청한다.
- 요청이 즉시 허용되지 않으면, 요청 스레드는 자원을 얻을 때까지 대기
- ex : mutex 락을 다른 스레드가 가지고 있는 경우
사용 : 스레드는 자원에 대해 작업을 수행할 수 있다.
- 예 : 자원이 mutex 락이라면, 스레드는 자신의 임계구역에 접근 가능
방출 : 스레드가 자원을 방출한다.
자원 할당 시 운영체제가 하는 일
- 매번 운영체제는 스레드의 자원 요청 및 할당을 확인한다.
- 스레드가 커널이 관리하는 자원을 사용할 때마다 위 과정이 발생
- 시스템 테이블이 각 자원이 가용 상태인지, 할당되었는지 기록
- 만약 할당됐다면, 할당된 자원이 어느 스레드에 할당됐는지도 기록
- 어떤 스레드가 현재 다른 스레드에 할당된 자원 요청 시
→ 그 자원을 기다리는 스레드 큐에 입력될 수 있음
다중 스레드 응용에서의 교착 상태
POSIX에서 교착 상태가 발생할 수 있는 예제
// 2개의 락 생성
pthread_mutex_t first_mutex;
pthread_mutex_t second_mutex;
// 2개의 락 초기화
pthread_mutex_init(&first.mutex, NULL);
pthread_mutex_init(&second.mutex, NULL);
/* thread_one이 실행하는 함수 */
void *do_work_one(void *param)
{
// first -> second 순으로 락을 얻으려고 함
pthread_mutex_lock(&first_mutex);
pthread_mutex_lock(&second_mutex);
/*
* 어떠한 일을 함
*/
pthread_mutex_unlock(&second_mutex);
pthread_mutex_unlock(&first_mutex);
}
/* thread_two이 실행하는 함수 */
void *do_work_two(void *param)
{
// second -> first 순으로 락을 얻으려고 함
pthread_mutex_lock(&second_mutex);
pthread_mutex_lock(&first_mutex);
/*
* 어떠한 일을 함
*/
pthread_mutex_unlock(&first_mutex);
pthread_mutex_unlock(&second_mutex);
}
- thread_one이 first_mutex를 획득, thread_two가 second_mutex 획득하는 경우
→ 교착 상태 발생이 가능함
- thread_two가 락 획득 시도 전에 thread_one이 2개의 락을 다 방출하는 경우
→ 교착상태가 발생하지 않는다.
- 어떤 특정 스케줄링 상황에서만 발생할 수 있는 교착 상태를 식별 및 검사하는 작업은 어려움
라이브락(Livelock)
라이브락(livelock) : 또 다른 형태의 라이브니스 장애
- 2개 이상의 스레드가 진행되는 것을 방해하지만, 진행할 수 없는 이유가 서로 다름
→ 교착 상태와 유사
- 일반적으로 각 스레드가 실패한 작업을 동시에 재시도할 때 발생
- 해결 방법
- 각 스레드가 실패한 행동을 재시도하는 시간을 무작위로 정하면 회피 가능
- 해당 방법은 네트워크 충돌 발생 시 Ethernet 네트워크가 하는 방식
- 교착 상태와 같이 특정 스케줄링 상황에서만 발생할 수 있다.
- 교착 상태만큼 흔히 일어나지는 않음
- But, 병행 프로그램 설계하는 데 있어 어려운 문제
라이브락 예제
// 2개의 락 생성
pthread_mutex_t first_mutex;
pthread_mutex_t second_mutex;
// 2개의 락 초기화
pthread_mutex_init(&first.mutex, NULL);
pthread_mutex_init(&second.mutex, NULL);
/* thread_one이 실행하는 함수 */
void *do_work_one(void *param)
{
int done = 0;
while(!done) {
pthread_mutex_lock(&first_mutex);
if(pthread_mutex_trylock(&second_mutex)){
/*
* 어떠한 일을 함
*/
pthread_mutex_unlock(&second_mutex);
pthread_mutex_unlock(&first_mutex);
done = 1;
}
else
pthread.mutex.unlock(&first_mutex);
pthread_exit(0);
}
/* thread_two이 실행하는 함수 */
void *do_work_two(void *param)
{
int done = 0;
while(!done) {
pthread_mutex_lock(&second_mutex);
if(pthread_mutex_trylock(&first_mutex)){
/*
* 어떠한 일을 함
*/
pthread_mutex_unlock(&first_mutex);
pthread_mutex_unlock(&second_mutex);
done = 1;
}
else
pthread.mutex.unlock(&second_mutex);
pthread_exit(0);
}
pthread_mutex_trylock() : 이 함수는 봉쇄되지 않고 Mutex락을 획득하려고 시도
- 스레드 1이 first_mutex를 획득한 후 thread_two가 second_mutex를 획득하는 경우
→ 라이브락으로 이어질 수 있음
- 이후 각 스레드는
pthread_mutex_trylock()을 호출 실패하고
각자의 락을 해제한 후 동일한 행동을 무한정 반복
교착 상태와 라이브락의 차이점
교착상태(DeadLock)
- 발생 시, 같은 집합의 모든 스레드가 요청한 이벤트를 기다리면서 봉쇄
라이브락(liveLock)