정의
같은 태스크 집합을 같은 프로세서에 올려도 어떤 규칙으로 실행 순서를 정하느냐에 따라 데드라인을 모두 지키기도 하고 놓치기도 한다. 그래서 알고리즘을 고르는 일이 곧 시간 보장을 설계하는 일이 된다. 이 페이지는 개별 알고리즘 대신 문헌에 자리 잡은 갈래와 그 갈래를 가르는 두 기준 — 스케줄을 언제 확정하는가, 우선순위를 언제 부여하는가 — 을 정리한다. 워크로드와 자원을 어떻게 추상화하는지는 실시간 스케줄링 참조 모델에서 다룬다.
판정 기준
범용 시스템에서 쓰이는 스케줄링 알고리즘도 대부분 우선순위 기반이지만 우선순위를 매기는 근거가 다르다. 범용 쪽이 도착 시각이나 실행 시간을 근거로 삼는 자리에 실시간 스케줄링은 데드라인이나 남은 여유 시간을 넣는다.[2]
근거가 다른 이유는 목표가 다르기 때문이다. 빠른 계산의 목표가 주어진 태스크 집합의 평균 응답 시간을 최소화하는 것인 반면, 실시간 계산의 목표는 각 태스크의 개별 시간 요구를 지키는 것이다. 그래서 동시·분산 시스템을 논할 때 흔히 쓰는 공정성은 실시간이 문제가 되는 순간 프로세스가 스케줄되는 방식을 설명하는 적절한 추상이 아니게 되고, 실시간 시스템에는 데드라인을 지키는 것 말고는 응답 시간을 줄일 유인이 없는 경우가 많다.[3]
성패를 말하는 어휘도 정해져 있다. 알고리즘 A가 어떤 태스크 집합의 시간 제약을 모두 지키게 하면 그 집합은 A로 스케줄 가능하고, 알고리즘 부류 C 안에 그렇게 해 주는 알고리즘이 하나라도 있으면 그 집합은 C 하에서 feasible하다. A가 C에 속하면서 C 하에서 feasible한 모든 집합을 옳게 스케줄하면 A는 C 안에서 최적이다.[4] 최적성은 이렇게 언제나 부류를 전제로 한 상대적인 성질이며, 부류를 밝히지 않은 최적은 의미가 정해지지 않는다. 판정을 실제로 수행하는 절차는 스케줄가능성 분석에서 다룬다.
스케줄을 확정하는 시점
클록 구동 방식은 모든 job의 파라미터를 설계 시점에 안다고 보고 스케줄을 오프라인으로 계산해 저장해 둔다. 런타임의 스케줄링 오버헤드를 최소로 줄일 수 있고 구현도 단순하지만 그만큼 유연하지 않다. 시간에 기반한 활동과 이벤트에 기반한 활동이 섞여 있고 상황 변화에 적응해야 하는 시스템에는 실행 중에 결정을 내리는 쪽이 쓰인다.[2] 오프라인 계산에는 스케줄링 알고리즘 자체의 실행 시간이 문제되지 않으므로, 결과 스케줄이 데드라인만 지킨다면 얼마든지 복잡한 방법을 써도 된다.[5] 이 계열의 대표가 순환 스케줄링이다.
온라인 계열은 반대로 실행 중에 결정을 내린다. 미리 알 수 없는 도착 패턴과 모드 변화를 감당할 수 있는 대신 결정 비용을 런타임에 치른다.
온라인 계열의 두 갈래
가중 라운드로빈은 job마다 가중치를 두고 한 라운드에서 그 가중치만큼의 연속 타임 슬라이스를 준다. 라운드의 길이는 가중치의 합이다.
모든 가중치가 1이면 보통의 라운드로빈과 같다. 정렬된 우선순위 큐가 필요 없어 구현이 단순하고 각 job이 라운드마다 일정한 진행을 보장받지만, 프로세서 시간을 비율로 나눠 주기 때문에 모든 job의 완료가 함께 늦어질 수 있다. 그래서 실시간 시스템에서의 쓰임은 제한적이고 주로 고속 스위칭 네트워크의 실시간 트래픽을 다루는 데 쓴다.[2]
다른 갈래가 우선순위 기반 스케줄링이다. 상용 실시간 운영체제의 다수는 제한된 수의 고정 우선순위 레벨을 바탕으로 만들어져 있어 이 갈래에 속한다. 이 계열 안에서 알고리즘이 갈리는 지점은 결국 준비 큐를 어떤 순서로 유지하는가다 — rate monotonic은 고정된 우선순위 레벨의 내림차순으로, EDF는 절대 데드라인의 오름차순으로 준비 큐를 정렬한다.[6] 그 차이가 커널 연산 비용에 무엇을 남기는지는 EDF 쪽에서 다룬다.
우선순위를 부여하는 시점
우선순위 기반 계열은 우선순위가 얼마나 자유롭게 변할 수 있는지에 따라 다시 세 부류로 나뉜다. 태스크마다 우선순위 하나가 결합되는 정적 부류, 우선순위가 job 단위로 정해지는 부류, 두 job의 상대 우선순위가 언제든 바뀔 수 있는 완전 동적 부류이며, 각각의 대표가 rate monotonic, EDF, 그리고 남은 여유 시간이 가장 적은 job을 고르는 최소 여유 시간 우선이다.[4] 세 부류의 정확한 정의와 포함 관계는 우선순위 기반 스케줄링 쪽에서 다룬다.