[운영체제] Deadlock 과 Starvation

Deadlock

Deadlock이란 두 개 이상의 작업들이 서로의 작업이 끝나기를 기다리고 있는 무한 대기 상태(교착 상태) 를 의미한다

프로세스와 스레드 모두에서 일어날 수 있으며, 아래의 네가지 조건이 모두 성립될 때 발생한다

• 상호 배제 (Mutual exclusion) : 프로세스들이 필요로 하는 자원에 대해 배타적 통제권을 요구
• 점유 대기 (Hold and wait) : 프로세스가 할당된 자원을 가진 상태에서 다른 자원을 대기
• 비선점 (Non preemption) : 프로세스가 어떤 자원의 사용을 끝낼 때 까지 그 자원을 뺏을 수 없음
• 순환대기 (Circular wait) : 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있음

중요한 것은 이 네가지 조건이 모두 성립해야 문제가 발생한다는 것이다

따라서 Dead lock의 회피는 이 네가지 조건중 한가지를 명시적으로 예방하여 해결한다

교착상태 예방 기법을 적용하기 위해 위의 네가지 조건을 모두 예방하려고 하면 프로세스나 스레드의 작동의 효율성이 떨어질 가능성이 높으므로, 하나의 조건만 예방하는 것이 바람직하다.

• Mutual exclusion 예방 : 프로세스들의 배타적 통제권을 없앤다 (하나의 임계영역에 여러 프로세스 또는 스레드가 들어갈 수 있도록 한다)

  • 이 경우 동기화 문제가 발생할 가능성이 있다

• Hold and wait 예방 : 작업에 필요한 임계영역을 모두 취득할 수 있을 때 까지 기다렸다가 취득한다

• Non preemption 예방 : 다른 작업이 사용중인 임계영역을 필요로 하면 현재 자기가 가지고 있는 임계영역을 반환한 뒤 대기한다

• Circular wait 예방 : 임계영역에 고유한 번호를 할당하고, 번호 순서대로 요구한다