데드락

데드락 발생 조건 4가지

아래 4가지를 전부 충족하면 데드락.

• 상호배제(Mutual Exclusion) : 하나의 스레드만 독립적으로 특정 자원을 쓸 수 있다.
• 점유하며 대기(Hold and Wait) : 자원 대기중일 때, 보유중인 자원을 계속 가지고 있는다.
• 비선점(No preemption) : 비선점. 다른 스레드가 보유중인 자원을 선점할 수 없다.
• 순환 대기(Circular wait) : 스레드들의 자원 요청을 화살표로 나타냈을 때, 순환되어야한다. 즉, P0이 필요한 자원을 P1이 선점하고 있고, P1이 필요한 자원은 P0이 선점하고 있는 형태

데드락 해결 방안

• Deadlock Prevention : 데드락 발생 조건 중 하나를 아예 예방해서 데드락이 발생하지 않게 한다.
• Deadlock Avoidance : 프로세스의 자원 요청에 대한 정보를 미리 얻었다고 가정하고, 데드락 발생 가능성이 있으면 자원을 할당하지 않는 방법이다. (최악의 상황을 가정한다.)
• Deadlock Detection And Recovery: 데드락을 허용하되, 데드락을 검사하고 데드락시 복구하는 알고리즘을 설정한다.
• Deadlock Ignorance : 데드락을 허용하고, 아무일도 하지 않는다.

"데드락을 허용하고, 아무일도 하지 않는다."는 무책임해보일 수도 있지만 Linux, Windows등 현대 OS에서 채택하고 있는 방법이다. 데드락이 일어날 확률이 드물기에 데드락에 대응하는 것이 오히려 더 큰 오버헤드를 가져오기 때문이다. 단, 사용자가 데드락을 감지하면 직접 프로세스를 종료할 수 있게 수작업할 수 있는 기능을 반드시 제공해야한다.

Deadlock Prevention

• 상호배제 금지 : 불가능~~~ 상호배제를 무조건 충족해야하는 자원들은 어찌하란 말이냐~
• 점유하며 대기 금지
  • 자원을 모두 할당받을 수 있을 때만 전부 할당받는다. (그러나 특정 순간에만 필요한 자원들이 있을 수 있기에 처음부터 전부 할당받는 것은 굉장히 비효율적)
  • 자원을 요청할 때, 점유중이던 자원을 전부 놓은 다음에 요청한다.
• 비선점 금지
  • 선점할 수 있게해라!!! (ex. P0이 R1을 요청했는데, 대기해야할 경우 P0이 보유중인 모든 자원은 선점 가능하게 된다. -> P1이 P0이 보유중인 자원 R0을 요청했을 때, P0의 자원은 선점 가능한 상태이므로 P1에게 넘어간다.)
  • CPU와 트랜잭션 같이 복구 지점을 기록할 수 있는 자원에게 적합한 방법이다. 하지만 복구 지점을 저장할 수 없는 자원은 무턱대고 선점하기 힘들겠지... 일반적으로 mutex 락과 세마포어 같은 자원에는 적용하기 힘들다.
• 순환 대기 금지
  • 자원들에 순서를 매기고 순서대로 자원을 할당하게 한다.
  • 동일한 자원(순서가 같은 자원)일 경우, 한 번의 요청으로 전부 획득해야 한다.
  • Java의 경우 자원의 hashcode를 순서로 사용하기도...

사실상 순환 대기 금지 외에 세 가지 방법들은 자원 이용률, 성능이 저하되기 때문에 잘 사용되지 않는다고 한다?

순환 대기 금지도 완벽한 방법이 아니다? 순서가 동적으로 할당되면 데드락이 발생 가능하다?

Deadlock Avoidance

주기적으로 데드락 탐지 알고리즘을 돌리고, 데드락이 감지되면 복구하는 방법이다.

보통 주기를 어떻게 설정하는데? 시간단위로 하거나, CPU Utilization이 40%이하일 때 등등...

자원 할당 그래프(Resource Allocation Graph)

Single Instance 일 때 사용할 수 있는 방법 (Single Instance : 자원의 개수가 하나씩만 주어졌을 때)

• P → R : 프로세스 P가 자원 R을 요청함(요청 간선)
• P ⇢ R : 프로세스 P가 자원 R을 요청할 가능성이 있다.
• R → P : 자원 R이 프로세스 P에게 할당됨(할당 간선)

위와 같이 프로세스에게 할당된 자원과, 프로세스의 자원 요청을 그래프로 나타낸다. P가 R을 요청했을 때 P ⇢ R 을 포함하여 간선간에 사이클이 생기면, 데드락 발생 가능성이 있으므로 해당 프로세스에게 자원을 할당해주지 않는다.

사이클이 생겼을 때,

• 자원이 모두 하나씩만 존재하면 데드락
• 자원이 두 개 이상이면 데드락이 아닐 수도 있다.
  

시간복잡도 : O(n^2) 간선의 최대 개수는 n(n-1)이기 때문

Banker's 알고리즘

각 프로세스들이 실행될 동안 보유할 수 있는 자원의 최대치를 알고있다고 가정한다.

• Allocation: 프로세스가 현재 보유중인 자원 개수
• Max:
• Available : 사용 가능한 자원 개수
• Need: 프로세스가 앞으로 보유할 수 있는 최대치 자원 개수(Max - Allocation)

위 정보를 가지고, 자원을 할당할 수 있는 프로세스를 선택한다.

• Available - Need >= 0 이라면 해당 프로세스에게 자원을 할당한다.

위 규칙에 따를 때, 모든 프로세스에게 자원을 할당할 수 있는 safe sequence가 생긴다면 데드락에서 안전하다고 판단하고 프로세스에게 자원을 할당한다.

시간 복잡도 : O(R P^2)
P들을 모두 할당해줘야 함(P) 각 P들이 전부 safe한가? 테스트 필요(R P) = O(R P^2)

• 예시
  

Deadlock Detection And Recovery

Deadlock Detection

Deadlock Detection 방법은 Deadlock Avoidance에서 사용한 자원 할당 그래프와 Banker's 알고리즘을 동일하게 활용한다.

Deadlock Recovery

• Process Termination
  • 해당 프로세스의 모든 자원을 방출
  • 데드락이 풀릴 때까지 프로세스의 자원을 하나씩 방출

    어떤 순으로 방출할까?
    우선순위, 해당 프로세스가 진행된 시간, 종료까지 남은 시간, 몇 개의 자원을 추가적으로 얻으면 프로세스를 끝낼 수 있는지 등을 고려할 수 있다... 응용 개발자 마음대로~

• Resource Preemption
  • 타겟 프로세스(victim)를 지정하고 할당된 자원을 뺏는다.

Starvation 문제가 생길수도 있다.