[운영체제] 7. 교착상태

교착상태란?

교착상태라는 말은 프로그래밍 이외에서도 자주 사용되는 말이다. 

차가 막혀서 도로에서 이러지도 저러지도 못하는 상황이라던가, 협상의 진전이 없는 상황이라던가 다양한 모습으로 교착상태를 떠올려볼 수 있다. 

 

운영체제에서 교착상태는 자원을 소유한 스레드들 사이에서 각 스레드이 다른 스레드가 소유한 자원을 요청해 모든 스레드가 무한정 대기하는 상황을 말한다. 

 

이는 다중프로그래밍의 고질적인 문제점이라고 할 수 있다. 운영체제는 스레드들에게 자원을 할당해줘아 햐는데 스레드는 하나의 자원만 필요한 것이 아니기 때문이다. 

 

교착상태 예시

 

T1부터 T5까지 다섯 개의 스레드가 5개의 CPU에서 동시에 실행되면서 자원을 한개씩 소유하고 있다고 해보자. 그런데 이 상황에서 다른 스레드가 가진 자원을 요청하게 된다면 이때 교착상태에 빠지게 되는 것이다. 각 스레드들은 다른 스레드들이 자신의 자원에 접근하지 못하도록 일반적으로 락을 걸어두고, 자원을 소유한 상태로 다른 스레드가 소유한 자원을 요청하게 되면 서로 무한정 대기하게 된다. 

 

 

교착상태를 유발하는 잠재적 요인 

교착 상태를 유발하는 요인들은 다음과 같다. 

 

자원

• 교탁상태는 멀티 스레드가 자원을 동시에 사용하려는 충돌에서 발생한다. 
• 소프트웨어/데이터 자원 : 뮤텍스, 스핀락, 세마포어, 파일, 데이터베이스, 파일락...
  하드웨어 자원: 프린터, 메모리, 프로세서 ...

자원과 스레드

• 한 스레드가 동시에 여러 자원을 필요로 하는 경우가 존재한다. 만약 스레드가 한 개의 자원만 소유하게 된다면 교착 상태는 발생하지 않을 것이다. 

 

자원과 운영체제 

• 운영체제는 한번에 하나씩 자원을 할당한다. 

 

자원 비선점

• 대부분의 운영체제는 스레드가 할당 받은 자원을 강제로 빼앗지 못한다. 

 

 

교착상태 해결 

그럼 교착상태를 어떻게 해결할 수 있을까? 

 

코스만조건

컴퓨터 시스템에서 교착상태를 유발할 수 있는 4가지 필요조건에 대해 연구인 코스만 조건이라는 것이 있다. 

코스만이 제시한 4가지 필요조건은 

 

1. 상호배제: 자원을 한번에 한 스레드만 할당한다.

2. 소유하면서 대기: 스레드가 자우너을 소유하면서 다른 자원을 대기한다. 

3. 강제 자원 반환 불가: 스레드에게 할당된 자원을 강제로 빼앗지 못한다.

4. 환형대기: 한 그룹의 스레드들에서 각 스레드가 다른 스레드가 소유하고 있는 자원을 요청하는 환원고리가 형성된다. 

 

이 네 가지 조건을 모두 가진 컴퓨터 시스템은 언제든 교착상태에 빠질 수 있다는 것이다. 

그런데 이는 다른 말로 이 중 하나라도 성립하지 않으면 교착상태에 빠지지 않게 된다는 말이기도 하다. 

 

교착 상태를 해결하기 위해 지금까지 4가지 방법이 제안되어 왔다. 

 

• 교착상태 예방: 4가지 조건중 하나 이상의 조건을 성립하지 않게 하여 교착상태를 예방한다
• 교착상태 회피: 운영체제가 자원할당 시 교착상태가 발생하지 않은 경우에만 자원을 할당한다. 할당시마다 교착상태 발생 여부를 검사해야 하기 때문에 시스템 성능에 안 좋다 
• 교착상태 감지 및 복구: 운영체제가 교착 상태를 감지하는 별도의 프로그램을 백그라운드에서 구동한다. 이는 주기적인 검사를 요하기에 시스템에 부담을 준다. 
• 교착상태 무시: 교착상태를 그냥 무시하는 것이다. 사실 교착상태는 잘 발생하지 않을 뿐더러 일어나게 된다면 그때 강제 종료 등의 조치를 취하면 된다는 것이다. unix, linux, window 등 대부분의 OS에서 채택하고 있는 방법이다. ostrich(타조) 알고리즘이라는 것이 사용된다. 

교착상태 예방 

교착상태 예방은 4가지 조건중 하나 이상을 성립하지 않게 하는 것이다. 

 

상호 배제를 없애기:

사실 근본적으로 불가능한 방법이다. 한 자원을 동시에 2개의 스레드가 사용할 수는 없는 노릇이기 때문이다. 

 

소유하면서 대기하는 문제:

기다리지 않게 하는 것이다. 스레드가 필요한 자원을 처음부터 모두 갖게 한다면 자원을 요청하면서 기다릴 필요가 없지 않겠는가? 이를 실현할 두가지 방법을 생각해볼 수 있다.

1) 운영체제가 스레드를 실행시키기 전에 스레드에게 필요한 자원을 모두 알고 있는 상태에서 스레드를 생성할 때 이를 모두 할당해주는 것이다. 만약 할당해줄 수 없다면 스레드 생성 자체를 대기한다.

2) 스레드가 자원을 소유한 상태로 자원을 요청하지 못하도록 요청시 자신이 가진 모든 자원을 반납하고, 받을 때 필요한 자원을 모두 한번에 받는 all or nothing 방법이 있다. 

 

자원 강제 반환 불가능 문제: 

자원의 선점을 허용해준다. 더 높은 순위의 스레드가 자원을 요청하면 운영체제가 낮은 순위의 스레드의 자원을 빼앗아 할당한다. 

 

환형대기 문제: 

모든 자원에 번호를 매기고, 스레드에게 반드시 번호순으로 자원을 할당받게 하는 방법이다. 

 

환형대기가 발생

위 경우에는 초반에 본 전형적인 환형대기 상황이다. 사실 이 문제는 마지막 T4 스레드가 R4자원과 R1 자원이 요구해서 환형대기가 최초 발생된다. 하지만 번호 순으로 자원을 할당받게 한다면 어떨까? 

 

 

환형대기 발생하지 않음

T4 스레드가 R4와 R1 자원을 모두 필요로 해서 문제가 발생한다고 했는데, 이 때 R1 자원을 먼저 요청하게 된다면 환형대기가 발생하지 않는다. T3 스레드가 R3 스레드와 R4를 모두 할당받고, 자원을 사용한 뒤 T2,T1이 모두 차례로 요청하는 자원을 할당받을 수 있게 된다. 그러면 마지막으로 T4 스레드도 R4와 R1 자원을 모두 할당받을 수 있게 돼 환형대기가 발생하지 않는 것이다. 

 

교착상태 회피 

교착상태 회피는 자원 할당 알고리즘을 사용해 교착 상태 자체를 방지하는 것이다. 

Banker's 알고리즘이라는 것이 유명한데, 이는 시스템을 안전과 비안전 상태로 나누고 시스템이 안전할 때만 자원을 할당해주는 것이다. 

그런데 이를 위해서는 각 스레드가 필요로 하는 자원의 개수, 현재 실행되고 있는 스레드가 할당받은 자원의 개수, 시스템 내 할당 가능한 자원의 개수를 모두 알아야 한다. 하지만 이를 전부 아는 것은 불가능하다. 동적으로 바뀌기 때문이다. 

 

교착상태 감지 및 복구 

교착상태를 운영체제가 주기적으로 감지하고, 교착상태가 발생됟나면 복구시키는 것이다. 

교착상태를 감지하는 프로그램을 주기적으로 구동하는 것만으로도 시스템에 부담을 주지만 교착상태를 복구시키는 것도 쉬운일은 아니다. 

교착상태를 복구시키는 방법에는 

자원 강제 선점하는 방법,  교착 상태 스레드 중 하나를 선택해 소유한 자원을 강제로 빼앗아 다른 스레드에게 할당한다. 

롤백, 교착 상태가 예상되는 스레드의 상태를 주기적으로 기록해두고, 교착상태 발생시 이전 상태로 복구시키는 것이다. 주기적으로 스레드의 상태를 기록해두고, 롤백 시키는 과정에서 시스템 성능의 저하가 발생한다

스레드 강제 종료, 교착 상태의 스레드 중 하나를 강제 종료한다. 

 

교착상태 무시 

교착상태 무시는 대부분의 운영체제에서 사용하고 있는 방법이다. 지금까지 교착상태가 아주 무시무시한 것처럼 말했지만, 사실 교착상태 자체는 생각보다 자주 발생하지 않는다. 또한 커널과 같이 체계적으로 짜여진 코드보다는 시스템 레벨의 프로그램에서 발생되는 경우가 많다. 

즉 굳이 교착 상태를 해결해야 하는가?라는 물음에서 시작된 것이다. 

이를 대표하는 알고리즘이 ostrich 알고리즘인데, 타조가 자신을 숨길때 상대방이 자신의 시야에서 사라지면 자신이 사라졌다고 믿는 것처럼, 교착상태가 발생하면 시스템을 그냥 재시작시키거나 특정 스레드를 강제로 종료해버리는 것이다. 교착상태 자체를 무시한다는 것이 이런 의미이다. 

이 방법은 데이터 손실이 발생할 가능성이 있지만, 앞서 말한 다른 방법들에 비해서 더 효율적이다. 그렇지만 실시간 시스템에서는 부적절한 방법이다. 

 

지금까지 다중 프로그래밍 운영체제서 발생하는 교착상태가 무엇인지, 그리고 교착상태가 왜 발생하고 어떻게 해결할 수 있을지 살펴보았다. 

 

책에서는 '할만한 가치가 있다고 모두 잘할 가치가 있는 것은 아니다.'라는 말을 인용했는데, 이 문장이 내게 와닿았다.

 

문제를 발견했을 때 사실 이를 무작정 해결하려고 하는 경우가 많았던 것 같다.

그런데 어떤 경우에는 그저 그 문제를 무시하는 것도 해결 방법이 될 수 있겠다.

어떤 것에 우선순위를 두는 것이 적절한지 고민함과 동시에 보다 다양한 시각에서 문제를 접근하는 사고를 늘려야할 것 같다.