Priority Inversion

출처: http://hagis.blog.me/110021051921

 Priority Inversion(우선순위 역전)은 유명한 리얼타임 스케쥴링 문제 중 하나이다. 리얼타임 시스템은 단순히 '정확성'만 보장하는 컴퓨팅과는 달리 '시간'이라는 조건도 보장해주는 특징이 있다. 데스크탑에서는 어떠한 스레드가 어떤 시간 내에 반드시 수행되어야 한다는 조건을 항상 보장 할 수 없다. 아무리 빠른 CPU 덕택에 반응 속도가 높아져도 확실한 보장과는 차이가 있는 것이다. 예를 들어, 리얼타임 운영체제가 사용되는 원자로나 자동차의 ABS 시스템 같은 경우, 중요한 임무를 담당하는 프로세스는 반드시 주어진 시간 내에 작업을 마쳐야 한다. 그렇지 아니하면 그 결과는 상당히 심각해질 수 있기 때문이다. 대부분의 로봇이나 자동차와 같은 임베디드 환경에서는 흔히 말하는 RTOS가 설치되어있다. 그리고 RTOS의 스케쥴링 문제는 데스크탑과는 사뭇 다른 여러 상황을 고려해야 한다.

그림 1. 화성탐사선 – 패스파인더 [1]

 1997년에 화성 탐사선 패스파인더(Pathfinder)는 성공적으로 화성에 착륙한다. 그리고 소저너(Sojourner)라는 작은 소형 로봇이 화성 표면을 직접 돌아다니면서 각종 지질 탐사를 하였다 (지금 화성에서 활동중인 탐사 로봇은 Sprit과 Opportunity라는 녀석들로 2003년에 도착한 것이다). 그러나 이 로봇이 자꾸만 무한 리붓이 되는 버그가 발생하고 만다. 수억 킬로미터 떨어져있는 지구에서 열심히 디버깅을 한 결과, 이 문제는 Priority Inversion으로 밝혀진다.

Priority Inversion 문제를 자세히 살펴보자. 아래 그림과 같이 High, Medium, Low 우선 순위를 각각 가지는 프로세스가 존재한다. 그리고 각 프로세스 사이에는 뮤텍스로 특정 자원을 공유한다.

그림 2. Priority Inversion [2]

먼저, 가장 우선 순위가 낮은 Task L이 스케쥴링이 된다. 그리고 잠시 후 공유자원 S를 쓰기 위해 뮤텍스 잡는다. 잠시 후, 우선 순위가 가장 높은 Task H가 할당이 된다. 그러면 선점형 구조이기 때문에, CPU는 Task H에게 주어진다. 그러나 잠시 후, Task H가 공유자원 S를 접근 하기 위해 뮤텍스를 잡으려고 시도한다. 그러나 이미 이 자원은 Task L이 쥐고 있기 때문에 Task H는 Task L이 뮤텍스를 놓을 때까지 기다릴 수 밖에 없다. 그래서 Task L은 다시 실행되게 된다. 이제 여기서 중간 우선 순위를 가진 Task M이 끼어들면서 문제가 발생한다. Task M이 들어오면 그만 Task L이 가지고 있던 CPU를 빼앗아 자기가 사용하게 된다. 그리고 Task M의 실행이 끝날 때까지 Task L 뿐만 아니라 Task H 역시 계속 기다리는 상황이 벌어지게 된다. 따라서, Task H보다 우선 순위가 낮은 Task M이 먼저 처리가 되는 일이 벌어지게 된다.

실제, 패스파인더 탐사선에서 일어났던 문제는 이러하다 [3]. 탐사선 로봇에는 낮은 우선 순위를 가지는 기상 관측 데이터를 보내는 thread가 있다. 먼저 이 스레드가 실행이 된다. 그리고 데이터를 보내기 위해 공유 자원인 버스를 쓰기 위해 뮤텍스를 잡는다. 그리고 높은 우선 순위를 가지는 'information bus'라는 스레드가 할당이 되는데, 이 스레드도 버스를 사용하기 위해 뮤텍스를 잡으려고 하고, 이미 사용 중이므로 기다리게 된다. 그러나 이 때, 중간 우선 순위를 가지는 통신 작업 스레드가 끼어 들어와 그만 우선 순위 역전 상황을 만들게 된다. 그렇게 되면, 우선 순위가 가장 높은 스레드는 주어진 시간에 작업을 마치지 못하게 되고, 시스템에 심각한 문제가 있는 것으로 판단한다. 결국, 이 문제를 해결하지 못하고 시스템은 리부팅으로 문제를 풀려고 한다. 따라서 계속 된 리부팅이 일어나게 되는 것이다.

 Priority Inversion의 문제 제기와 이것을 해결하는 방법은 이미 1990년에 논문으로 나왔다. 그러나 이렇게 제대로 이 문제를 겪은 적은 Path Finder가 처음이다. 사실, 탐사선 발사 이전, 지상에서 테스트할 때도 이유를 알 수 없는 리부팅 현상이 있었다고, 개발자들이 나중에 고백했다고 한다… 그러나 문제 재현 자체도 무척 어려웠고, 하드웨어 문제겠니 싶어서 넘어갔다고 한다. 그리고 실제 화성에 가서야 제대로 이 문제가 발견 된 것이었다. 

이 문제를 해결하기 위해, 마치 영화 아폴로 13에서 볼 수 있듯이, 지상에 똑같이 있는 복제 시스템에서 열심히 날밤 까며 엔지니어들이 문제를 해결한다. 다행히 탐사선 로봇에는 별도의 디버깅 장치가 장착되어 있었다. 그래서 모든 trace를 찍어서 지구로 가져와 디버깅을 그나마 손 쉽게 할 수 있었다. 만약 이러한 디버깅 장치도 없었다면 정말 수천억이 들어간 프로젝트가 이런 사소한 소프트웨어 실수 때문에 물거품이 되었을 수가 있다 (탐사선이 화성에 도착하는데 만도 7개월이 걸리니 시간 손해도 이만 저만이 아니다.)

그렇다면 이 문제의 해결책은 무엇인가? 많은 방법 가운데 Priority inheritance라는 방법을 살펴보자. 중간 우선 순위의 태스크가 낮은 우선 순위를 선점할 수 없도록, 우선 순위를 상속시키는 것이다. 즉, Task H가 Task L이 가지고 있는 자원 때문에 블락이 될 때, 자신의 높은 우선 순위를 Task L에게 전달해서, Task M이 끼어들지 못하게 하는 것이다.

패스파인더의 이 문제는 정말 디버깅이 무엇인지를 아주 잘 보여주는 대표적인 사례라고 볼 수 있겠다.

참고자료

1. http://en.wikipedia.org/wiki/Mars_Pathfinder
   
2. http://www.netrino.com/Publications/Glossary/PriorityInversion.php
   
3. http://research.microsoft.com/~mbj/Mars_Pathfinder/Mars_Pathfinder.html