교착 상태 : 자원을 소유한 채, 모두 상대방이 소유한 자원을 기다리면서 무한 대기
1) 교착상태(deadlock)
3) 교착생태의 전형적인 발생 상황
1) 자원 할당 그래프(Resource Allocation Graph, RAG)
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;
}
1) 코프만 조건
** 4가지 조건 중 한 가지라도 성립되지 않으면 교착상태 발생 X
교착상태로 인해 시스템 전체가 중단되지는 않는다. 교착상태는 시스템 내에 몇몇 스레드들 사이에서 발생하므로 이들 스레드들만 실행이 중지된 채 대기상태에 머물며, 이들로 인해 시스템 전체가 불능 상태가 되는 것은 아니다. 시스템 관리자나 이들 스레드들을 제거하면 이들의 교착상태는 사라진다. 만일 많은 스레드들이 교착상태에 연루되어 있을 때는 시스템을 재시작 하는 것 좋다.
** 코프만의 4가지 조건 중 최소 하나를 성립하지 못하게 함
1. 상호배제 조건 -> 상호배제 없애기
방법1 : 운영체제는 스레드 실행 전 필요한 모든 자원을 파악하고 실행시 한 번에 할당
-> 당장 사용하지 않는 자원을 스레드에게 묶어 두기 때문에 자원 활용률이 떨어짐
-> 다른 스레드는 필요한 자원을 할당 받지 못하고 실행 대기
방법2 : 스레드가 새로운 자원을 요청하려면, 현재 할당 받은 모든 자원을 반환하고, 한꺼번에 요청하여 할당
=> 방법1이나 방법2 모두 가능하지 않거나 매우 비효율적인 방법
자원 할당 시, 미래에 환형 대기가 발생할 것으로 판단되면 자원 할당을 하지 않는 정책
banker's 알고리즘으로 해결
1) Edsger Dijkstra 에 의해 개발된 알고리즘. 자원 할당 전에 미래에 교착상태가 발생하지 않을 것인지 안전한지 판단하는 알고리즘
- 은행에서의 대출 알고리즘
2) 안전한 상태
- 현재 프로세스들을 어떤 순서로 실행시켰을 때, 모든 프로세스들이 자신이 요청하는 자원을 가지고 실행할 수 있다면 안전한 상태
3) 불안전한 상태
- 환형 대기에 빠질 수 있다면 불안전한 상태
4) 알고리즘
- 각 프로세스가 실행 시작 전에 필요한 전체 자원의 수를 운영체제에게 알림
- 자원을 할당할 때마다, 자원을 할당해주었을 때 교착상태가 발생하지 않을 만큼 안전한 상태인지 판단하여 안전한 상태일 때만 자원할당
- 각 프로세스가 필요한 자원의 개수, 현재 각 프로세스가 할당 받은 자원의 개수, 그리고 시스템 내 할당 가능한 자원의 개수를 토대로 현재 요청된 자원을 할당해도 안전한지 판단
5) 비현실적
- 각 프로세스가 실행 전에 필요한 자원의 개수를 아는 것은 불가능
- 프로세스의 개수도 동적으로 변하기 때문에 미리 프로세스의 개수를 정적으로 고정시키는 것은 불가능
1) 교착상태를 감지하는 프로그램을 통해, 형성된 교착상태를 푼다.
2) 교착상태를 감지하였을 때의 복구 방법
자원 강제 선점
-> 교착상태에 빠진 스레드 중 하나의 자원을 강제로 빼앗아 다른 스레드에게 할당
롤백
-> 운영체제는 주기적으로 교착상태가 발생할 것으로 예측도는 스레드의 상태를 저장하여 두고 교착상태가 발생하면 마지막으로 저장된 상태로 돌아가도록 하고, 다시 시작하면서 자원을 다르게 할당
스레드 강제 종료
-> 교착상태에 빠진 스레드 중 하나 강제 종료
-> 가장 간단하면서도 효과적인 방법
시간과 메모리 공간(rollback의 경우)에 대한 부담이 크기 때문에 잘 사용하지 않음
교착상태 발생위치 - 교착상태는 사용자가 작성한 멀티스레드 응용프로그램에서 주로 발생하며 개발자의 미숙한 멀티스레드 코딩에서 비롯된다. 교착상태는 커널 내에서도 발생할 수 있지만 거의 발생하지 않는다. 커널의 최고의 개발자들에 의해 매우 정교하게 작성되어 있기 때문이다.
1) 교착상태를 해결할 필요가 있을까?
2) 타조알고리즘
3) 주의
이 글이 문제가 된다면 삭제하겠습니다.