교착상태

교착 상태(Deadlock)

10분 테코톡을 듣고 작성한 글입니다. 영상링크

바로 직전 학기에 전공과목인 운영체제를 들어서 교착상태에 대해 기억이 아주 생생한 상태! 복습한다고 생각하고 들었당.

교착 상태 개념

프로세스나 쓰레드가 결코 일어날 수 없는 특정 이벤트를 기다리는 상태를 교착 상태라고 말한다. 

실제 시스템에서의 교착상태는 요청이 많이 발생하는 DB에서 흔하게 발생한다. 그 중에서도 MySQL의 상호거래패턴에서 자주 발생한다고 한다. 

• 트랜잭션 1은 A가 B에게 자신의 포인트를 차감하고 상대방에게 전달해준다.
• 트랜잭션 2는 B가 A에게 자신의 포인트를 차감하고 상대방에게 전달해준다.
• 두 트랜잭션이 동시에 실행됐다고 가정해보자.
  • 트랜잭션 1은 A의 포인트를 -10 차감하고 lock(점유)을 건다.
  • 트랜잭션 2은 B의 포인트를 -10 차감하고 lock을 건다.
• 여기서 문제가 발생한다. 이제 상대방의 포인트를 올려주기 위해 접근하면 이미 점유가 되어있기 때문에 무한정 대기하는 현상이 발생하는데 이것을 바로 교착 상태에 빠졌다고 표현한다.

교착 상태 필요 조건

교착 상태가 발생하기 위해서는 4가지 필요조건이 존재한다. 이 조건을 모두 만족해야만 교착상태에 빠진다.

1. 상호 배제 조건(mutual exclusion condition)

• 상호배제란 한 프로세스가 자원을 점유였다면 다른 프로세스가 이 자원에 접근할 수 없도록 막는 것이다.

2. 점유와 대기 조건(hold-and-wait-condition)

• 자원을 최소한 하나 정도 보유, 다른 프로세스에 할당된 자원을 얻으려고 대기하는 프로세스가 있어야한다는 조건이다.

3. 비선점 조건(nopreemption condition)

• 프로세스에서 자원을 할당받으면 작업을 완료할 때까지 자원을 빼앗을 수 없는 것을 말한다.

4. 순환 대기 조건(circular-wait condition)

• 위의 그림에서와 같이 점유와 대기로 인해 순환 대기가 발생하여 빠져나갈 수 없는 상태를 의미한다.

교착 상태 해결법

1. 교착 상태 무시

• 교착 상태가 드물게 발생하는 시스템에서 일반적으로 사용하는 방법
• 교착 상태가 드물게 발생하기 때문에 이를 해결하기 위한 비용이 오히려 더 비효율적
• 윈도우즈, 유닉스 등 많은 운영체제가 이 방법을 사용
• 문제가 발생하면 프로세스를 강제 종료하거나 재부팅 ==> 전체 작업을 잃게 될 수도 있음, 하지만 전체 비용면에서 효율적
• 타조(Ostrich) 알고리즘이라고도 부름

2. 교착 상태 회피

• 교착 상태가 발생할 가능성을 인정하고(4가지 필요조건 허용), 교착 상태가 발생하지 않도록 자원을 할당하는 방법
• 많은 연산 오버헤드가 발생
• 대표적으로 자원 할당을 거부하는 은행원 알고리즘이 있다.
  • 시스템을 안정 상태와 불안정 상태로 구분하고 불안정 상태라면 자원 할당을 대기한다.
    • 여기서 불안정 상태는 무조건 교착상태에 빠지는 것이 아니라 교착 상태가 발생할 수 있는 가능성이 높다는 의미!
• 현실적으로 불가능한 방법(자원을 요청할 때마다 시스템의 상태를 판단해야함)

3. 교착 상태 탐지 및 복구

교착 상태가 자주 발생하는 시스템에서 일반적으로 사용하는 방법으로, 필요한 정보를 유지하고 탐지 알고리즘을 실행시키는 비용뿐 아니라 회복에 필요한 비용까지 발생한다.

탐지

• 교착 상태 존재 여부 및 교착 상태에 연관된 프로세스와 자원을 알아내자는 전략
• 순환 대기 존재 여부에 초점을 맞춤
• 회피와 마찬가지로 시스템의 상태를 검사해야하므로 오버헤드가 발생한다.
  • 일주일마다, 2주마다 주기를 설정

복구

• 순환 대기를 깨서 교착 상태로부터 회복하자는 전략
• 순환 대기가 깨질 때까지 프로세스 종료
  • 이 때 어떤 프로세스를 중단 프로세스로 선정할 것인지는 각 시스템마다 다른 우선순위로 동작한다.(남은 수행시간/자원 유형의 수)
• 순환 대기에 포함된 프로세스의 제어권을 빼앗고 Rollback
  • 처음부터 다시 시작시킬 수도, 일정 시점마다 상태를 저장해놓고 Rollback시킬 수도...
• 시스템이 실행하고 있는 모든 프로세스의 상태 정보를 주기적으로 유지해야하는 부담이 있음.

4. 교착 상태 예방

• 교착 상태는 필요악
  • 교착 상태가 발생하지 않는 환경은 자원을 효율적으로 사용할 수 없다, 즉 교착상태는 발생할 수 밖에 없는 존재
• 교착 상태 4가지 필요 조건 중 하나를 거부하여 교착 상태를 예방한다는 해결법(비용이 크게 소모된다)