1997년 화성 패스파인더 미션의 우선순위 역전(priority inversion) 버그

참고자료:

웹문서 http://www.cs.cornell.edu/courses/cs614/1999sp/papers/pathfinder.html

세미나 보고서 Mars Pathfinder: Priority Inversion Problem, Report for the Seminar Series on Software Failures, Submitted By Risat Mahmud Patha

 

화성 패스파인더 미션

• 과학적 목표에 집중한 행성 미션을 수행하는 NASA의 디스커버리 프로그램에서 처음으로 완료된 미션이 화성 패스파인더(Mars Pathfinder)이다.
• 이 프로젝트는 1993년 10월에 시작되어 총 2억 6,500만 달러의 비용이 들었으며, 개발 기간은 3년으로 1996년 12월 4일에 발사되어 1997년 7월 4일에 화성에 착륙했다. 마지막 데이터 전송은 1997년 9월 27일로 기록되었다.
• 우주선이 하나의 계측 랜더(lander)와 하나의 자유롭게 움직이는 로버(rover)로 구성되었다. 예상 수명은 랜더의 경우 30일, 로버의 경우 7일이었는데, 랜더와 로버가 예상 수명보다 각각 3배와 12배 이상 생존했다.

 

이슈 발생

• 미션을 시작한 지 며칠 만에 패스파인더 랜더의 컴퓨터가 반복적으로 재부팅(total system resets)되는 현상이 발생하였다.
• 이 현상이 착륙 후 약 6번 정도 발생했으며, 각각 데이터 손실이 발생했다고 언론이 보도했지만 실제로 데이터는 손실되지 않았고 수집이 하루 지연되었다(미션 수명이 제한되어 있기 때문에 이런 지연이 매우 중요한 문제가 됨).
• 중요 태스크의 데드라인을 놓치도록 만드는 ‘우선순위 역전(Priority Inversion)’이 발생한 것이 문제의 원인으로 파악되었다.

  

이슈 진단 – 우선순위 역전(Priority Inversion)

패스파인더의 애플리케이션이 실시간 임베디드 시스템 커널인 VxWorks에 의해 스케쥴링 된다. VxWorks가 쓰레드의 선점형 우선순위 스케줄링(pre-emptive priority scheduling)을 제공하기 때문에, 태스크가 상대적 긴급성에 따라 결정된 우선순위를 가진 쓰레드로 실행이 된다.

 

패스파인더에는 우주선의 여러 컴포넌트 간 정보 전달에 사용되는 공유 메모리 영역으로 생각할 수 있는 "정보 버스"가 포함되어 있다. 패스파인더의 기상 데이터 수집 태스크(the meteorological data gathering task)는 빈도가 낮고 우선순위가 낮은 쓰레드로 실행되며, 정보 버스를 사용하여 데이터를 게시한다. 이 태스크가 데이터를 게시할 때 동기화를 위해 뮤텍스를 획득하고, 버스에 쓰기를 수행하고, 뮤텍스를 해제하는 과정을 거친다. 버스 관리 태스크(the bus management task)는 정보 버스 안팎으로 특정 종류의 데이터를 이동하기 위해 높은 우선순위로 자주 실행되는 태스크이며, 마찬가지로 뮤텍스를 사용하여 정보 버스에 액세스 한다. 또한 우주선에는 중간 우선순위로 실행되는 통신 태스크(the communications task)가 포함되어 있는데, 이것이 장시간의 실행 시간을 가진다.

 

대부분의 경우 이 세 태스크의 조합이 잘 작동했다. 그러나 매우 드물게 (높은 우선순위) 버스 관리 쓰레드가 (낮은 우선순위) 기상 데이터 쓰레드의 뮤텍스를 기다리느라 차단되어 있는 동안 (중간 우선순위) 통신 태스크가 스케쥴링에 끼어드는 인터럽트가 발생하였다. 이 경우 기상 데이터 태스크보다 우선순위가 높은 통신 태스크가 장시간 동안 실행되면서 기상 데이터 태스크의 실행을 방해하는 데, 이는 다시 차단된 상태에 있는 버스 관리 태스크 실행을 방해하는 결과로 이어졌다. 일정 시간 후 워치도그 타이머가 버스 관리 태스크가 한동안 실행되지 않았음을 알아차리고(deadline miss), 무언가 크게 잘못되었다는 결론을 내려 전체 시스템 리셋을 명령했다. 이는 전형적인 우선순위 역전 시나리오이다.

 

우선순위 역전 예 세 개의 잡(job) J1, J2, J3의 우선순위가 J1>J2>J3이고, J1와 J3은 리소스를 공유하지만 J2는 다른 태스크와 리소스를 공유하지 않는다. 아래 그림이 우선순위 역전 문제를 나타낸다.     잡 J3은 시간 t0에서 정상 실행을 시작하고, 시간 t1에서 공유 리소스에 액세스하고 크리티컬 섹션에서 실행을 시작한다. 시간 t2에서 우선순위가 더 높은 잡 J1이 도착하여 J3 실행을 선점하고, 공유 리소스를 요구하지 않은 채 시간 t3까지 실행한다. 시간 t3에서 J1은 리소스에 액세스를 시도하고, J3이 해당 리소스를 붙잡고 있으므로 차단된다. 이후 J3은 공유 리소스를 사용하여 크리티컬 섹션의 실행을 시작한다. 그러나 시간 t4에서 중간 우선순위 잡 J2가 도착하고, J3을 선점하고 J2의 정상 실행을 시작한다. 이제 중간 우선순위 J2가 실행되는 동안 가장 높은 우선순위 J1이 차단된다. J1이 J2보다 더 높은 우선순위를 갖고 있고 J2와 리소스를 공유하지 않음에도 불구하고 중간 우선순위 J2는 제멋대로 긴 시간 동안 높은 우선순위 J1의 실행을 차단할 수 있다. 즉, J1과 J2의 우선순위가 뒤바뀐 것처럼 되어 버려서 이를 우선순위 역전 문제라고 부른다.

 

 

어떻게 디버깅 하였는가?

VxWorks는 관심 있는 모든 시스템 이벤트(예, 컨텍스트 전환, 동기화 오브젝트 사용, 인터럽트 등)에 대해 전체 추적을 기록하는 모드에서 실행할 수 있다. 문제 발생 후 JPL 엔지니어들은 추적 기능을 켠 채 실험실의 똑같은 복제 우주선에서 시스템을 실행하는 데 오랜 시간을 보냈고, 리셋을 발생시켰다고 생각되는 정확한 조건을 되풀이하려고 시도했다. 엔지니어 한 명을 제외하고 모두가 집에 돌아간 어느 이른 아침, 이 엔지니어가 마침내 복제 우주선에서 시스템 리셋을 재현하는데 성공했고, 추적을 분석한 결과 우선순위 역전이 밝혀졌다.

 

어떻게 수정하였는가?

패스파인더 복제 우주선에서 디버깅한 후 해결책은 ‘우선순위 상속(priority inheritance)’이라는 것이 JPL 엔지니어에게 분명해졌다. 

VxWorks 뮤텍스 오브젝트는 생성 시 우선순위 상속이 뮤텍스에 의해 수행되어야 하는지 여부를 나타내는 부울 패러미터를 허용한다. 문제의 뮤텍스는 성능을 이유로 이 패러미터가 "꺼짐" 상태로 초기화되었다(“데이터 버스 태스크가 매우 자주 실행되고 타임 크리티컬 한데, 우선순위 상속을 수행하기 위해 추가 시간을 소비해서는 안된다"라는 엔지니어의 초기 분석에 따라 이 기능을 껐다고 함). 이게 켜져 있었다면 낮은 우선순위 기상 데이터 쓰레드가 뮤텍스를 얻고자 하는 높은 우선순위 버스 관리 쓰레드의 우선순위를 상속하였을 것이며, 이는 기상 데이터 쓰레드를 중간 우선순위 통신 태스크보다 더 높은 우선순위로 스케쥴링 되도록 하여 우선순위 역전을 방지하였을 것이다. 

VxWorks에는 개발자가 시스템 디버깅 중에 C 표현식과 함수를 런타임 실행할 수 있는 C 언어 인터프리터가 포함되어 있는 데, JPL 엔지니어들이 우연히 이 기능이 켜진 상태로 우주선 발사를 결정했다. 코딩 규칙에 따라 뮤텍스의 초기화 패러미터가 전역 변수(global variables)에 저장되었고, 그 주소가 있는 심볼 테이블이 시작 소프트웨어(launch software)에도 포함되어 C 인터프리터에서 사용 가능했다. 엔지니어들이 짧은 C 프로그램 패치를 우주선으로 업로드했으며, 이게 인터프리터를 통해 뮤텍스 우선순위 상속 패러미터 값을 FALSE에서 TRUE로 변경하면서 더 이상 시스템 리셋이 발생하지 않았다.

 

 

아래 영상은 실시간 운영체제(RTOS)에 대한 강의 중 우선순위 역전을 다룬 것인 데,
화성 패스파인더 사건에 대한 자세한 설명을 포함하고 있다(영상 길이 12분 34초). 

이 영상의 구체적인 아젠다가 아래와 같다.

• 제한된 우선순위 역전(Bounded Priority Inversion)
• 공유 리소스를 전담하는 서비스 태스크 사용 - 제한된 우선순위 역전의 솔루션
• 무제한 우선순위 역전(Unbounded Priority Inversion)
• Arduino ESP32에서 무제한 우선순위 역전 데모
• 우선순위 상한 프로토콜(Priority Ceiling Protocol) - 무제한 우선순위 역전의 솔루션
• 우선순위 상속 프로토콜(Priority Inheritance Protocol) - 무제한 우선순위 역전의 솔루션
• FreeRTOS 뮤텍스로 우선순위 상속 데모

 

제목: Introduction to RTOS Part 11 - Priority Inversion by Digi-Key Electronics

출처: https://www.youtube.com/watch?v=C2xKhxROmhA