정의
고정 우선순위 스케줄링(fixed priority scheduling)은 태스크마다 정적 우선순위 하나를 배정하고, 그 태스크가 만들어 내는 모든 job이 그 우선순위를 그대로 물려받는 스케줄링 방식이다.[1]
준비된 job 가운데 우선순위가 가장 높은 것을 고른다는 원리는 우선순위 기반 스케줄링 전반에 공통이다. 고정 우선순위가 갈리는 지점은 그 우선순위가 태스크에 붙박이라는 것이다 — job마다 절대 데드라인에서 우선순위를 다시 뽑는 Earliest Deadline First와 대비된다. 상용 실시간 운영체제의 압도적 다수는 EDF가 아니라 이 방식을 구현한다. 구현이 단순하고 런타임 오버헤드가 낮으며, 우선순위 레벨 수를 제한해 두면 준비 큐를 비트맵으로 표현해 넣고 빼는 연산을 상수 시간에 끝낼 수 있기 때문이다.[1]
두 가지 근본 문제
고정 우선순위를 쓰기로 정하고 나면 남는 문제는 둘이다. 하나는 어떤 우선순위를 어느 태스크에 줄 것인가이고, 다른 하나는 그렇게 배정한 결과가 모든 데드라인을 지키는지 어떻게 확인할 것인가다. 뒤쪽은 스케줄가능성 분석이 맡는다.
스케줄링 이론은 우선순위가 태스크에 정적으로 붙어 있다는 것까지만 말하고 그 값을 언제 정하는지는 규정하지 않는다. 차량용 규격에서는 구성 시점이다 — OSEK/VDX는 우선순위를 사용자가 정적으로 배정하며 실행 중에는 바꿀 수 없다고 못박고 그 값은 시스템 통합 단계에서 구성하며[2], AUTOSAR OS는 태스크 우선순위를 pre-compile 시점 구성 파라미터로 규정한다.[3]
앞쪽이 사소한 문제가 아닌 이유는, 같은 태스크 집합이라도 배정에 따라 결과가 달라지기 때문이다. 주기가 2와 5이고 실행 시간이 각각 1인 두 태스크를 생각해 보자. 주기가 짧은 쪽에 높은 우선순위를 주면 긴 쪽의 실행 시간을 2까지 늘려도 데드라인이 지켜지지만, 반대로 배정하면 두 실행 시간 모두 1을 넘기는 순간 지켜지지 않는다.[4]
최적 배정 정책
어떤 배정 정책이 최적이라는 말에는 정확한 뜻이 있다. 주어진 태스크 집합 부류와 스케줄링 알고리즘 부류에 대해, 다른 어떤 우선순위 순서로 스케줄 가능한 집합이 그 정책이 정한 순서로도 빠짐없이 스케줄 가능하면 그 정책을 최적이라고 부른다.[1] 최적 정책을 쓰면 우선순위 순서 때문에 놓치는 집합은 없어지므로, 분석은 배정 탐색이 아니라 판정에만 집중할 수 있다.
데드라인과 주기의 관계에 따라 어떤 정책이 최적인지가 달라진다. 데드라인이 주기와 같은 집합에서는 주기가 짧을수록 높은 우선순위를 주는 rate monotonic 배정이 최적이다.[4] 상대 데드라인이 주기보다 짧을 수 있는 집합에서는 이 규칙이 무너진다 — 주기는 길지만 데드라인이 짧은 태스크가 낮은 우선순위를 받아 버리기 때문이다. 이 경우에는 상대 데드라인이 짧을수록 높은 우선순위를 주는 deadline monotonic 배정이 최적이며, Leung과 Whitehead가 1982년에 보였다.[5]
정책을 정하지 않고 손에 잡히는 대로 우선순위를 주는 것이 왜 손해인지도 최적성의 정의에서 바로 나온다. 임의 배정으로 스케줄되는 집합은 최적 정책으로도 반드시 스케줄되지만 그 역은 성립하지 않으므로, 임의 배정은 결코 이득이 없고 놓치는 집합만 늘린다. 그 손해는 자동차 도메인에서 정량으로 측정된 적이 있다. 메시지 데드라인과 무관하게 CAN 식별자를 관행대로 배정한 차량용 구성 10,000건에서 breakdown utilization은 대체로 35% 이하였던 반면, 최적으로 배정하면 대체로 80% 이상이었다. “CAN은 35% 넘게 못 돌린다”는 업계 통설이 여기서 나왔다.[6]
임의 데드라인에서의 배정
데드라인이 주기보다 길 수도 있는 임의 데드라인 집합에서는 deadline monotonic도 더 이상 최적이 아니다. 그래도 최적 순서를 찾는 길은 있다 — Audsley의 최적 우선순위 배정 알고리즘은 최대 번의 스케줄가능성 판정으로, 스케줄 가능한 순서가 존재하기만 하면 그것을 찾아낸다.[1] 순열을 모두 훑는 데 드는 과 비교하면 배정 문제는 이 지점에서 사실상 닫힌다.
우선순위와 중요도
우선순위는 스케줄 순서를 정하는 수단이지 기능적 중요도의 등급이 아니다. 둘을 겹쳐 놓고 싶은 유혹은 자연스럽다 — 과부하가 나면 낮은 우선순위 태스크부터 데드라인을 놓치므로, 정작 중요한 태스크가 먼저 무너질 수 있기 때문이다. 그래서 중요도 순으로 우선순위를 주거나 중요한 태스크의 데드라인을 인위적으로 줄이는 방법이 떠오르지만, 이 접근은 시스템 전체의 스케줄가능성을 떨어뜨린다.[7]
중요도로 우선순위를 주는 문제
기능적으로 덜 중요한 태스크가 더 높은 우선순위를 갖는 배정이 스케줄가능성에는 유리할 수 있다. 중요한 태스크의 데드라인을 앞당겨 우선순위를 끌어올리는 대신, 그 태스크를 더 짧은 주기로 쪼개 rate monotonic 순서에서 자연히 높은 우선순위를 얻게 하는 주기 변환(period transformation)이 대안으로 제시된다.[7]