0번. 다음은 교착상태에 대한 설명입니다 빈칸을 채워주세요
충분한 한정된
교착상태란 프로세스에게 ___자원이 분배되었을 때 프로세스들이 자원의 부족으로 더이상 실행할 수 없어 끝낼수도 없으며, 자원이 프로세스에게 묶여 다른 작업을 시작하는 것도 불가능한 상태를 말한다.
1번. 프로세스는 다음 순서로만 자원을 사용할 수 있습니다. 간단하게 채워주세요
- 요청 :
- 사용 :
- 방출 :
📄 답지
0번.
다음은 교착상태에 대한 설명입니다 빈칸을 채워주세요
충분한 한정된
교착상태란 프로세스에게 한정된자원이 분배되었을 때 프로세스들이 자원의 부족으로 더이상 실행할 수 없어 끝낼수도 없으며, 자원이 프로세스에게 묶여 다른 작업을 시작하는 것도 불가능한 상태를 말한다.
1번. 프로세스는 다음 순서로만 자원을 사용할 수 있습니다. 간단하게 채워주세요
- 요청 : 쓰레드의 자원 요청, 요청이 혀용되지 않으면 대기
- 사용 : 자신의 임계구역에 접근해 작업을 수행함
- 방출 : 자원 방출
문제 1
다음 코드를 보고 질문에 답하세요. (필요한 경우 보기를 참고하세요)
//mutex 락 생성
pthread_mutex_t first_mutex;
pthread_mutex_t second_mutex;
//mutex 락 초기화
pthred_mutex_init(&first_mutex,NULL);
pthred_mutex_init(&second_mutex,NULL);
//thread_one
void *do_work_one(void *param)
{
pthread_mutex_lock(&first_mutex);
pthread_mutex_lock(&second_mutex);
/**
* Do some work
*/
pthred_mutex_unlock(&second_mutex);
pthred_mutex_unlock(&first_mutex);
}
//thread_two
void *do_work_two(void *param)
{
pthread_mutex_lock(&second_mutex);
pthread_mutex_lock(&first_mutex);
/**
* Do some work
*/
pthred_mutex_unlock(&first_mutex);
pthred_mutex_unlock(&second_mutex);
}<보기>
first_mutex,second_mutex
1) first_mutex, 2) second_mutex
1) second_mutex, 2) first_mutex
-
위 코드에서 thread_one은
_________________________순서로 mutex 락을 획득하려고 하고 동시에 thread_two는_________________________순서로 mutex 락을 획득하려고 한다. -
thread_one이
____________를 획득하고 thread_two가____________를 획득하면 교착 상태가 가능하다. -
위 코드에서 교착 상태가 발생하지 않는 경우는 어떤 경우인가요?
문제 2
-
다음 코드가 라이브락으로 이어질 수 있도록 (A), (B), (C)를 채워주세요.
<보기>
done,True,False,first_mutex,second_mutex//thread_one void *do_work_one(void *param) { int done = 0; while (!👉👉🏻👉🏼👉🏽👉🏾👉🏿(A)👈🏿👈🏾👈🏽👈🏼👈🏻👈) { pthread_mutex_lock(&first_mutex); if (pthread_mutex_trylock(&👉👉🏻👉🏼👉🏽👉🏾👉🏿(B)👈🏿👈🏾👈🏽👈🏼👈🏻👈)) { /** * Do some work */ pthred_mutex_unlock(&second_mutex); pthred_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 (!👉👉🏻👉🏼👉🏽👉🏾👉🏿(A)👈🏿👈🏾👈🏽👈🏼👈🏻👈) { pthread_mutex_lock(&second_mutex); if (pthread_mutex_trylock(&👉👉🏻👉🏼👉🏽👉🏾👉🏿(C)👈🏿👈🏾👈🏽👈🏼👈🏻👈)) { /** * Do some work */ pthred_mutex_unlock(&first_mutex); pthred_mutex_unlock(&second_mutex); done = 1; } else pthread_mutex_unlock(&second_mutex); } pthread_exit(0); }
📄 답지
문제 1
다음 코드를 보고 질문에 답하세요. (필요한 경우 보기를 참고하세요)
//mutex 락 생성
pthread_mutex_t first_mutex;
pthread_mutex_t second_mutex;
//mutex 락 초기화
pthred_mutex_init(&first_mutex,NULL);
pthred_mutex_init(&second_mutex,NULL);
//thread_one
void *do_work_one(void *param)
{
pthread_mutex_lock(&first_mutex);
pthread_mutex_lock(&second_mutex);
/**
* Do some work
*/
pthred_mutex_unlock(&second_mutex);
pthred_mutex_unlock(&first_mutex);
}
//thread_two
void *do_work_two(void *param)
{
pthread_mutex_lock(&second_mutex);
pthread_mutex_lock(&first_mutex);
/**
* Do some work
*/
pthred_mutex_unlock(&first_mutex);
pthred_mutex_unlock(&second_mutex);
}<보기>
first_mutex,second_mutex
1) first_mutex, 2) second_mutex
1) second_mutex, 2) first_mutex
-
위 코드에서 thread_one은
1) first_mutex, 2) second_mutex순서로 mutex 락을 획득하려고 하고 동시에 thread_two는1) second_mutex, 2) first_mutex순서로 mutex 락을 획득하려고 한다. -
thread_one이
first_mutex를 획득하고 thread_two가second_mutex를 획득하면 교착 상태가 가능하다. -
위 코드에서 교착 상태가 발생하지 않는 경우는 어떤 경우인가요?
답
thread_two가 락을 획득하려고 시도하기 전에 thread_one이 first_mutex와 second_mutex를 획득하고 방출할 수 있다면 교착 상태는 발생하지 않는다.
문제 2
-
다음 코드가 라이브락으로 이어질 수 있도록 (A), (B), (C)를 채워주세요.
<보기>
done,True,False,first_mutex,second_mutex답
(A) done
(B) second_mutex
(C) first_mutex
//thread_one void *do_work_one(void *param) { int done = 0; while (!👉👉🏻👉🏼👉🏽👉🏾👉🏿(A)done👈🏿👈🏾👈🏽👈🏼👈🏻👈) { pthread_mutex_lock(&first_mutex); if (pthread_mutex_trylock(&👉👉🏻👉🏼👉🏽👉🏾👉🏿(B)second_mutex👈🏿👈🏾👈🏽👈🏼👈🏻👈)) { /** * Do some work */ pthred_mutex_unlock(&second_mutex); pthred_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 (!👉👉🏻👉🏼👉🏽👉🏾👉🏿(A)done👈🏿👈🏾👈🏽👈🏼👈🏻👈) { pthread_mutex_lock(&second_mutex); if (pthread_mutex_trylock(&👉👉🏻👉🏼👉🏽👉🏾👉🏿(C)first_mutex👈🏿👈🏾👈🏽👈🏼👈🏻👈)) { /** * Do some work */ pthred_mutex_unlock(&first_mutex); pthred_mutex_unlock(&second_mutex); done = 1; } else pthread_mutex_unlock(&second_mutex); } pthread_exit(0); }
교착상태가 발생되기 위해서는 다음의 네가지 조건이 전부 성립해야 한다.
-
_________: 하나의 자원을 두개 이상의 스레드가 자원을 점유할 수 없다.
-
_________: 스레드가 특정 자원을 점유하고 있는 상태에서 새로운 자원을 요청할 때 기존 자원을 보유하면서 대기한다.
-
_________: 자원들을 선점할 수 없다. 즉 자원이 강제적으로 방출될 수 없고 스레드가 종료될 때 스레드에 의해 자발적으로만 방출된다.
-
__________: T1-> R1->T2->R2->T1 과 같은 식으로 스레드와 자원들이 서로 꼬리에 꼬리르 물고 있어야 한다.
-
다음 그림이 데드락인지 아닌지 판단해 주세요(네모박스안에 점이 없는경우 리소스가 1개입니다)
1번그림:
2번그림:
3번그림:
4번그림:
📄 답지
-
상호 배제(mutual exclusion): 하나의 자원을 두개 이상의 스레드가 자원을 점유할 수 없다.
-
점유하며 대기(hold-and-wait): 스레드가 특정 자원을 점유하고 있는 상태에서 새로운 자원을 요청할 때 기존 자원을 보유하면서 대기한다.
-
비선점(no preemption): 자원들을 선점할 수 없다. 즉 자원이 강제적으로 방출될 수 없고 스레드가 종료될 때 스레드에 의해 자발적으로만 방출된다.
-
순환 대기(circular wait): T1-> R1->T2->R2->T1 과 같은 식으로 스레드와 자원들이 서로 꼬리에 꼬리르 물고 있어야 한다.
-
다음 그림이 데드락인지 아닌지 판단해 주세요(네모박스안에 점이 없는경우 리소스가 1개입니다)
1번그림: 데드락 아님,싸이클이 없음
2번그림: 데드락, 싸이클이 형성되어 있고 r3를 미혜스레드가 획득하지 못함
3번그림: 데드락 아님, 싸이클이 있지만 P3가 점유하고 있는 r2를 반환하면 p1이 r2를 획득하면서 데드락이 아니게 됨
4번그림: 데드락, p2가 제일 오른쪽 위 리소스를 할당받지 못함
1. 교착 상태 문제를 처리하는 4가지 방법 중 하나인 "Deadlock Ignorance 교착상태 무시(교착 상태가 시스템에서 절대 발생하지 않는 척하기" 는 Windows, Linux가 사용하는 방법이다. (O/X)
2. 스레드가 평생 요구하고 사용할 자원에 대한 부가적인 정보를 미리 제공할 것을 요구하여, 스레드가 기다려야 할지 아닐지를 결정하는 방식은 교착상태 회피avoidence / 예방prevention 방식이다.
3. 상호배제, 점유하며 대기, 비선점, 순환 대기 4가지의 필요조건 중 적어도 하나가 성립하지 않도록 보장하는 방식은 교착상태 회피avoidence / 예방prevention 방식이다.
4. Deadlock Detection and recovery는 데드락(교착상태) 발생은 허용하되 그에 대한 감지Detection 루틴을 두어 발견시 회복시키는 방법이다. (O/X)
📄 답지
교착 상태가 발생하는 조건은 앞 8.3에서 살펴본 4가지 필요 조건이 있습니다.
이 4가지 조건은 무엇이었나요?
📄 4가지
네! 바로
Mutual Exclusion(상호배제), Hold & Wait(점유 대기), No Preemption(비선점), Circular Wait(순환 대기) 입니다.
교착상태에 빠지는 조건을 알았으니 빠지지 않으려면 4가지 필요조건과 반대(!(필요조건))되면 됩니다 그 방법은 무엇일까요? 보기를 참고하여 짝지어 주세요!
[보기]
1. 여러 개의 프로세스가 공유 자원을 사용할 수 있도록 한다.
2. 자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 점유하고있는 자원을 모두 반납하고 요구한 자원을 사용하기 위해 대기한다.
3. 자원에 교유한 번호를 할당하고, 프로세스에게 자원의 번호 순서대로 자원을 요구하라고 한다.
4. 프로세스가 실행되기 전에 필요한 모든 자원을 할당한다.
- 정답
- 상호배제 -
- 점유 대기 -
- 비선점 -
- 순환대기 -
- 상호배제 -
📄 답지
교착 상태가 발생하는 조건은 앞 8.3에서 살펴본 4가지 필요 조건이 있습니다.
이 4가지 조건은 무엇이었나요?
📄 4가지
네! 바로
Mutual Exclusion(상호배제), Hold & Wait(점유 대기), No Preemption(비선점), Circular Wait(순환 대기) 입니다.
교착상태에 빠지는 조건을 알았으니 빠지지 않으려면 4가지 필요조건과 반대(!(필요조건))되면 됩니다 그 방법은 무엇일까요? 보기를 참고하여 짝지어 주세요!
[보기]
1. 여러 개의 프로세스가 공유 자원을 사용할 수 있도록 한다.
2. 자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 점유하고있는 자원을 모두 반납하고 요구한 자원을 사용하기 위해 대기한다.
3. 자원에 교유한 번호를 할당하고, 프로세스에게 자원의 번호 순서대로 자원을 요구하라고 한다.
4. 프로세스가 실행되기 전에 필요한 모든 자원을 할당한다.
- 정답
- 상호배제 - 1
- 점유 대기 - 4
- 비선점 - 2
- 순환대기 - 3
<보기>
saffy, safe, saint, unsafe, unstable, safe sequalizer, safe sequence
최소필요량, 햄최몇, 최대사용량
문채원 알고리즘, 은행원 알고리즘, 자원봉사그래프 알고리즘, 자원할당그래프 알고리즘
- [1-1] 교착상태 회피(Deadlock Avoidance)는 쉽게 말해 시스템이
- [1-2] 이 때 사용되는 안전하냐(safe/unsafe)는 개념은 시스템 내의 프로세스들에 대한
- [1-3] 가장 일반적인 방법은 프로세스들이 필요로 하는 각 자원별
- [1-4] 자원의 종류별로 하나의 인스턴스만 있다면 사용하는 알고리즘은
- [1-5] 자원의 종류별로 여러 개의 인스턴스만 있다면 위의 알고리즘을 사용할 수 없고,
- [1-6] 만약 시스템이 safe 상태라면 절대 deadlock이 아니다.
(O / X) - [1-7] 만약 시스템이 unsafe 상태라면 무조건 deadlock이다.
(O / X)
- 실선 (assignment edge)
- 프로세스가 해당 자원을 점유함
- 점선 (claim edge)
- 프로세스 Pᵢ가 자원 Rᵢ를 미래에 요청할 수 있음을 뜻함.
- 실제 요청시 실선으로 바뀜
- [2-1] 다음 그림은 데드락 상태일까요? 그 이유는 무엇일까요?
- 답변 :
- 답변 :
- [2-2] 그렇다면 다음 그림은 데드락 상태일까요? 그 이유는 무엇일까요?
- 답변 :
- 답변 :
- [2-3] 프로세스가 n개일 때 사이클 생성여부 조사 시간복잡도는 얼마일까요? :
O( )
- 다익스트라 알고리즘을 개발한 다익스트라가 개발한 알고리즘
- 프로세스는 시작할때 필요한 자원의 총 개수를 종류별로 미리 신고해야 함
- 자원을 요청했을 때 그 요청을 받아들일 것인지 결정
- '지금 몇 개 요청했느냐'가 아니라 '최대요청이 현재 가용자원으로 할당가능한지'로 판단함
- 최대요청할 것을 걱정해 자원이 남아도는데도 안주는 것이기 때문에 비효율적임
- 은행원 알고리즘에 따라 아래 그림에서 추가요청이 받아들여질 프로세스를 모두 골라주세요 (+111,111점)
process_jehong, process_daelee, process_yeosong, process_kukim, process_taelee
📄 답지
<보기>
saffy, safe, saint, unsafe, unstable, safe sequalizer, safe sequence
최소 필요량, 최햄몇, 최대 사용량
문채원 알고리즘, 은행원 알고리즘, 자원봉사그래프 알고리즘, 자원할당그래프 알고리즘
- [1-1] 교착상태 회피(Deadlock Avoidance)는 쉽게 말해 시스템이
unsafe상태가 되지않도록 보장하는 방법이다. - [1-2] 이 때 사용되는 안전하냐(safe/unsafe)는 개념은 시스템 내의 프로세스들에 대한
safe sequence유무로 결정된다. - [1-3] 가장 일반적인 방법은 프로세스들이 필요로 하는 각 자원별
최대 사용량을 미리 선언하도록 하고, 이 정보로 자원할당이 안전한지 동적으로 조사해서 안전한 경우에만 할당하는 방식이다. - [1-4] 자원의 종류별로 하나의 인스턴스만 있다면 사용하는 알고리즘은
자원할당그래프 알고리즘이다. - [1-5] 자원의 종류별로 여러 개의 인스턴스만 있다면 위의 알고리즘을 사용할 수 없고,
은행원 알고리즘을 사용한다. - [1-6] 만약 시스템이 safe 상태라면 절대 deadlock이 아니다.
(O) - [1-7] 만약 시스템이 unsafe 상태라면 무조건 deadlock이다.
(X)- deadlock 가능성이 있는 것일 뿐 반드시 deadlock인 것은 아님
- 실선 (assignment edge)
- 프로세스가 해당 자원을 점유함
- 점선 (claim edge)
- 프로세스 Pᵢ가 자원 Rᵢ를 미래에 요청할 수 있음을 뜻함.
- 실제 요청시 실선으로 바뀜
- [2-1] 다음 그림은 데드락 상태일까요? 그 이유는 무엇일까요? (+111점)
데드락이 아니다. 사이클이 형성되지 않았기 때문이다.
- [2-2] 그렇다면 다음 그림은 데드락 상태일까요? 그 이유는 무엇일까요? (+111점)
반드시 데드락 상태인 것은 아니고, 데드락 상태일 수 있다. 사이클이 형성되었기 때문이다.
- [2-3] 프로세스가 n개일 때 사이클 생성여부 조사 시간복잡도는 얼마일까요? :
O(n²)
- 은행원 알고리즘에 따라 아래 그림에서 추가요청이 받아들여질 프로세스를 모두 골라주세요 (+111,111점)
process_daelee, process_kukim
