[OS] Deadlock

.🔎 주요 질문

1. Deadlock(교착 상태)가 뭔가요? 발생 조건에 대해 말해보세요

2. 회피 기법인 banker's algorithm이 뭔지 설명해보세요

3. 교착상을 설명하는 식사하는 철학자 문제에 대해 설명해보세요

 

Deadlock이 무엇인가요?

두 개 이상의 프로세스나 스레드가 서로 자원을 얻지 못해서 다음 처리를 하지 못하는 상태

무한히 다음 자원을 기다리게 되는 상태를 말합니다. (결과적으로 아무것도 완료하지 못함)

 

출처 : 위키피디아 (교착 상태)

P1과 P2가 자원 2,1을 모두 얻어야 한다고 가정해보자

t1 : P1이 자원2를 얻음 / P2가 자원1을 얻음

t2 : P1은 자원1을 기다림 / P2는 자원2를 기다림

현재 서로 원하는 자원이 상대방에게 할당되어 있어서 두 프로세스는 무한 Wait상태에 빠짐

-> DeadLock

 

 

Deadlock의 발생조건에 대해 말해보세요

아래와 같은 4가지 조건이 모두 성립해야 Deadlock이 발생하게 됩니다.

1. 상호 배제(Mutual exclusion)

자원은 한번에 한 프로세스만 사용할 수 있음

2. 점유 대기(Hold and wait)

자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고

계속 가지고 있음

3. 비선점(No preemption)

프로세스는 자원을 스스로 내어놓을 뿐 강제로 빼앗기지 않음

4. 순환대기(Circular wait)

자원을 기다리는 프로세스간에 사이클이 형성되어야 함

 

Banker's algorithm

Banker's algorithm에서

운영체제는 안전상태를 유지할 수 있는 요구만을 수락하고 불안전 상태를 초래할 사용자의 요구는

나중에 만족될 수 있을 때까지 계속 거절함

 

가정

- 모든 프로세스는 자원의 최대 사용량을 미리 명시

- 프로세스가 요청 자원을 모두 할당받은 경우 유한 시간 안에 이들 자원을 다시 반납

 

방법

- 기본 개념 : 자원 요청시 safe 상태를 유지할 경우에만 할당

- 총 요청 자원의 수가 가용 자원의 수보다 적은 프로세스를 선택 (그런 프로세스가 없으면 unsafe 상태)

- 그런 프로세스가 있으면 그 프로세스에게 자원을 할당

- 할당받은 프로세스가 종료되면 모든 자원을 반납

- 모든 프로세스가 종료될 때까지 이러한 과정 반납

 

P0는 [7 4 3]이 필요하지만 현재 이용가능한 자원은 [3 3 2]뿐이라 대기해야 함

P1은 [1 2 2]가 필요한데 현재 이용가능한 자원 [3 3 2]이니 할당 가능

할당 후 동작이 끝나면 회수하기 때문에 Available = [5 3 2]가 됨

쭉 진행하다보면 safe sequence는 P1->P3->P4->P2->P0와 같은 순서로 진행된다.

 

식사하는 철학자 문제

5명의 철학자가 원탁에 앉아서 식사를 한다. 철학자들 사이에는 포크가 하나씩 놓여있고,

철학자들은 다음의 과정을 통해 식사를 한다. (포크 뺐기 불가능,각 포크에 대해 한사람만 들 수있음)

 

1. 일정 시간 생각을 한다.
2. 왼쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
3. 오른쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.
4. 양쪽의 포크를 잡으면 일정 시간만큼 식사를 한다.
5. 오른쪽 포크를 내려놓는다.
6. 왼쪽 포크를 내려놓는다.
7. 다시 1번으로 돌아간다.

 

간단하게 생각해, 만약 모든 철학자들이 동시에 자신의 왼쪽 포크를 잡는다면(점유대기), 모든 철학자들이 자기 오른쪽의 포크가 사용 가능해질 때까지 기다려야 한다(순환대기). 그런데 모든 철학자들이 그러고 있다. 이 상태에서는 모든 철학자가 영원히 3번 상태에 머물러있어 아무것도 진행할 수가 없게 되는데, 이것이 교착(Deadlock)상태이다.

각 포크에 대해 한 사람만 들 수 있음(상호 배제), 남의 포크를 뺏어주지 않음(비선점)

 

카운팅 세마포어를 통해 위와 같은 문제를 해결

방에 대한 입장 정원을 카운팅 세마포어로 설계해, 최대 4명만 들어온다면 방 안의 모든 사람들이

왼쪽 포크를 든다 하더라도 DeadLock이 일어나지 않습니다.