Deadlock 교착상태

소심한 사람 a, 소심한 사람 b가 운동을 하고 있다. a는 스쿼트, 벤치 프레스 순서로, b는 벤치프레스, 스쿼트 순으로 운동을 하려한다. 둘은 너무 소심한 나머지 첫 번째 운동이 끝나고 다음 운동 기구에 있는 사람이 나올 때 까지로 기다리기로 한다. 서로 눈치를 보고 있기 때문에 결과적으로 무한정 대기를 하게 된다.

교착상태란

두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태를 말한다.

예시

• 데이터 베이스에서 트랜잭션
  

트랜잭션이 특정 테이블의 레코드나 테이블을 업데이트할 때 lock을 통해서 자원을 얻게 되는데 동일 테이블이나 레코드에 대해 여러 트랜잭션이 동시에 진행하다 보면 deadlock이 발생할 수 있다.

발생 조건

1. 상호 배제 (mutual exclusion)
   • 하나의 공유 자원에 대해 두 개의 프로세스가 동시에 접근할 수 없다.
2. 점유 대기 (hold and wait)
   • 하나의 자원을 점유하는 프로세스가 다른 프로세스의 자원을 얻기 위해서는 요청을 하고 대기해야 한다.
3. 비선점 (no preemptive)
   • 특정 프로세스가 자원을 사용하고 있는데 해당 자원 사용이 끝나기 전까지 뺏을 수 없다.
4. 순환 대기 (circular wait)
   • 프로세스들 간에 서로 사용하고 있는 자원에 대해 순환적으로 대기하고 있는 형태를 말한다.

위의 4가지 조건을 모두 만족해야 한다.

해결 방법

1. 교착 상태 예방

• 교착 상태가 발생하지 않도록 사전에 예방하는 방법

• 4 가지 발생 조건 중 하나를 제거함으로써 해결하는 방법

  1. 상호 배제 조건 제거

  • 하나의 공유 자원에 대해 두 개의 프로세스가 동시에 접근할 수 있게 만드는 것 -> 관리하는 것이 현실적으로 어려움

  2. 점유 대기 조건 제거

  • 해당 작업에 필요한 자원을 모두 요청하고 할당받은 후 작업을 실행함으로써 제거 가능 -> 자원의 효율성이 매우 떨어짐, 주기적으로 프로세스들이 어떤 자원을 필요로 하는지 파악하는 추가적인 오버헤드 발생

  3. 비선점 조건 제거

  • 다른 프로세스의 자원을 요청하기 위해서 자신이 가지고 있는 자원을 반납해야 한다 -> 프로세스가 작업한 상태를 잃을 수 있다는 부작용 존재

  4. 순환 대기 조건 제거

  • 각각의 자원들에 대해 고유 번호를 할당하고 각 프로세스는 자신이 할당받은 자원의 번호 오름차순(내림차순)으로 요청하는 방식

• 일반적으로 자원 사용 효율성이 떨어지고 비용이 많이 드는 방법이라 잘 사용하지 않는다고 한다.

2. 교착 상태 회피

• 교착 상태 발생 가능성을 검사해서 발생 가능성이 있다면 사전에 회피하는 방식

1. 자원 할당 그래프 알고리즘
   • 그래프 상에 교착 상태를 유발하는 순환 사이클의 존재 유무를 체크
2. 은행원 알고리즘

• 흐름

1. 프로세스가 자원 요청시, 자원을 할당한 후에도 안정 상태로 남아있는지 사전 검사
2. 안정 상태라면 자원을 할당
3. 불안정 상태라면 다른 프로세스가 자원을 해지할 때까지 대기
   -> 자원을 요청할 때마다 시스템 상태를 검사하기 때문에 오버헤드가 크고 은행원 알고리즘의 경우 전제 조건이 많음
   

3. 교착 상태 탐지 및 회복

• 교착 상태를 허용하지만 상태를 탐지하고 회복하는 방식

• 알고리즘을 주기적으로 실행함으로써, 시스템에 발생한 deadlock을 체크하고 회복

• 여기서도 자원 할당 그래프 알고리즘을 사용할 수 있는데, 주기가 너무 짧으면 회피와 같아져 오버헤드가 커지게 됨. 환경과 조건에 맞게 주기를 설정해야 함.

• 탐지 후에 교착 상태를 일으킨 프로세스를 종료하거나, 할당된 자원을 해제함으로써 회복

  1. 프로세스 종료

  • 교착 상태의 프로세스를 모두 중지
    - 가장 쉽고 간단하지만 프로세스가 작업한 내용들이 유실될 수 있음
  • 교착 상태가 제거될 때까지 한 프로세스씩 중지
    - 하나의 프로세스를 중지하고 알고리즘을 통해 교착상태가 해결되었는지 확인하기 때문에 오버헤드가 큼

  2. 자원 선점

  • 교착 상태가 제거될 떄까지 프로세스가 점유한 자원을 선점해 다른 프로세스에게 할당

  회복시 고려사항

• 희생자 선택
  - 회복시 어떤 프로세스를 죽일지, 어떤 프로세스의 자원을 다른 프로세스에게 할당할 것인지.

  • 비용측면에서 판단. (어느 정도 구동되었는지, 자원을 가지고 있는지)
  • 기아상태 발생할 수 있음

• 후퇴 (rollback)
  - 희생자를 골랐다면 해당 프로세스를 어느 정도 수준으로 rollback할 것인지
  -> 아예 죽이고 새로 킬 것인지, 교착상태가 해결될 정도만 할 것인지

• 기아 상태 (starvation)

4. 교착 상태 무시

• 교착 상태 자체를 무시하고, 특별한 조치를 취하지 않는 방법
• 교착 상태의 발생 활률이 낮은 상황에서 주로 사용 (unix, windows)
• 교착상태를 주기적으로 탐지하는 오버헤드보다 무시하는 비용이 적을 때 사용
• 발생 시 시스템을 재부팅하거나, 사용자가 프로세스를 직접 죽이는 방식으로 해결.

참고

https://www.youtube.com/watch?v=Ry_gB34cvwc