정의
우선순위 역전(priority inversion)은 우선순위가 높은 job이 더 낮은 우선순위 job들에 의해 블로킹되는 현상이다.[1]
이상적으로는 높은 우선순위 job이 시작되는 즉시 낮은 job들을 선점해야 한다. 그러나 두 job이 같은 데이터를 만지면 일관성을 위해 접근을 직렬화해야 하고, 낮은 쪽이 먼저 접근권을 얻은 상태라면 높은 쪽은 그 접근이 끝날 때까지 기다릴 수밖에 없다. 그래서 락으로 임계 구역을 지키는 한 역전 자체는 없앨 수 없다. 문제는 역전이 일어난다는 사실이 아니라 그 길이에 상한이 있느냐다.
역전은 우선순위 기반 스케줄링을 전제로 정의되는 현상이다. 블로킹이 길게 이어지면 낮은 자원 이용률에서도 데드라인을 놓치게 되고, 그래서 상한 없는 역전은 실시간 시스템의 스케줄가능성과 예측 가능성을 함께 해친다.[1]
블로킹의 정의
블로킹(blocking)은 역전의 좁은 형태다. job J가 자기보다 낮은 우선순위 job 의 임계 구역이 끝나기를 기다려야 진행할 수 있을 때, J는 그 임계 구역에 의해 블로킹됐다고 한다. 반대로 더 높은 우선순위 job이나 먼저 도착한 같은 우선순위 job의 실행을 기다리는 것은 블로킹으로 세지 않는다 — 그것은 우선순위 규칙이 의도한 순서대로 밀린 것이기 때문이다.[1]
상한 없이 늘어나는 블로킹
우선순위가 높은 순서로 J1, J2, J3 세 job이 있고 J1과 J3가 이진 세마포어 S가 지키는 자료구조를 공유한다고 하자. J3가 S를 잠그고 임계 구역을 실행하는 중에 J1이 시작되어 J3를 선점하고, 곧 같은 자료구조를 쓰려다 S에서 블로킹된다. 여기까지는 예상 범위다 — J1은 J3의 임계 구역이 끝날 때까지만 기다리면 될 것 같다.
그렇지 않다. J3는 자기 우선순위로 돌아가 실행을 이어가므로, S와 아무 상관 없는 중간 우선순위 job J2가 J3를 선점할 수 있다. J1의 블로킹은 J2와 그 사이 들어온 다른 중간 우선순위 job들이 모두 끝나고 J3가 S를 놓을 때까지 이어진다. 이렇게 되면 블로킹 구간은 임계 구역 길이와 무관해지고 임의로 길어질 수 있다.[1]
임계 구역 안에서는 선점을 금지하는 방법으로 이 상황을 부분적으로 막을 수 있지만, 아주 짧은 임계 구역에만 적절하다. 낮은 우선순위 job이 긴 임계 구역에 들어간 뒤에는 그 자료구조를 쓰지도 않는 높은 우선순위 job까지 불필요하게 막히기 때문이다.
화성 착륙선 사례
Mars Pathfinder는 1997년 7월 4일 화성 표면에 착륙했다.[2]
당시 비행 소프트웨어 팀을 이끈 엔지니어가 공개한 설명에 따르면, 착륙 후 운용 중에 컴퓨터 리셋이 일어나 그날 남은 활동이 다음 날로 미뤄졌고 원인은 우선순위 역전이었다. 1553 버스의 트랜잭션을 8Hz 주기로 설정하는 bc_sched 태스크가 운영체제 내부 태스크를 빼면 시스템에서 가장 높은 우선순위였고, 수집된 데이터를 분배하는 bc_dist 태스크가 세 번째였으며, 기상 관측 장비 데이터를 다루는 ASI/MET 태스크는 그보다 훨씬 낮았다. ASI/MET가 select() 호출 안에서 대기 대상 파일 디스크립터 목록을 보호하는 뮤텍스 세마포어를 넘겨주는 도중에 선점됐고, 여러 중간 우선순위 태스크가 실행되는 동안 bc_dist가 같은 통신 메커니즘으로 데이터를 보내려다 그 뮤텍스에서 블로킹됐다. 다음 주기를 준비하려 깨어난 bc_sched는 bc_dist가 hard 데드라인인 주기 내 완료에 실패한 것을 감지하고 오류를 선언했으며, 시스템은 여기에 리셋으로 반응했다. 해결은 select 서비스가 만드는 세마포어에 우선순위 상속 옵션을 켜도록 전역 설정 변수를 바꾸고 그 변경을 우주선에 반영하는 것이었다.[3]
리셋은 한 번으로 끝나지 않았다. NASA는 1997년 7월 5·10·11·14일 모두 네 차례 리셋이 있었고, 비행팀이 활동을 직렬화해 추가 리셋을 피하려 했다고 밝혔다.[4]
널리 퍼진 “감시(watchdog) 타이머가 리셋을 걸었다”는 설명은 이 사건을 학회 기조연설로 전해 들은 사람이 정리해 돌린 요약에서 비롯됐다.[5] 비행 소프트웨어 팀을 이끈 당사자는 그 연설 전 브리핑에서 자신이 상황을 잘못 전달했다고 밝혔고, 그의 설명에서 데드라인 위반을 감지해 오류를 선언한 것은 감시 타이머가 아니라 bc_sched다.
시험에서 드러나지 않는 이유
이 결함은 ASI/MET 데이터가 수집되는 동시에 중간 우선순위 태스크들이 무겁게 실행될 때만 나타났다. 발사 전 시험은 데이터율과 과학 활동이 최선의 경우인 조건에 한정돼 있었고, 실제 지표면 데이터율이 예상보다 높았던 것이 문제를 키웠다.[3]
대응의 방향
역전을 없앨 수 없다면 남는 목표는 블로킹 시간에 계산 가능한 상한을 두는 것이다. 상한이 있으면 그 값을 스케줄가능성 판정에 항으로 넣을 수 있고, 없으면 넣을 값 자체가 없다.
블로킹된 쪽의 우선순위를 락을 쥔 쪽에 물려주는 방법은 우선순위 상속 프로토콜에서, 자원마다 정한 상한 우선순위로 접근을 통제해 교착까지 함께 막는 방법은 우선순위 상한 프로토콜에서 다룬다. OSEK/VDX OS는 후자를 자원 관리의 규정으로 못 박아 우선순위 역전이 발생하지 않는다고 선언한다.[6]
한편 회전 락을 쓰면 역전이 정지로 이어질 수 있다. 높은 우선순위 흐름이 락을 기다리며 CPU를 계속 점유하면 락을 쥔 낮은 우선순위 흐름이 실행될 기회를 얻지 못하기 때문이다.[7]