정의
Rate monotonic 우선순위 배정은 요청 주기가 짧을수록, 곧 요청률이 높을수록 높은 우선순위를 주는 고정 우선순위 배정이다. 우선순위는 실행 시간과 무관하게 주기만으로 정해진다.[1]
1973년 Liu와 Layland가 제시한 배정이며, 고정 우선순위라는 부류 안에서 최적임이 함께 증명되었다. 이 페이지는 그 최적성이 정확히 무엇을 뜻하고 어디까지 미치는지를 정리한다. 우선순위 기반 계열 안에서의 자리는 우선순위 기반 스케줄링에서 다룬다.
전제
원 논문의 결과는 몇 가지 가정 위에 서 있다. 요청의 도착 패턴과 태스크 사이의 독립성, 실행 시간을 수 하나로 잡는 부분은 주기 태스크 모델이 그대로 물려받은 가정이고, 그 수를 무엇으로 채우는지는 최악 실행 시간이 다룬다.
배정 규칙이 서려면 여기에 두 가지가 더 필요하다. 데드라인이 다음 요청이 오는 시각과 같아야 하고 — 데드라인이 주기와 같은 데드라인 설정이다 — 스케줄링이 선점 가능한 우선순위 구동 방식이어서 실행 중인 것보다 높은 우선순위 요청이 들어오면 즉시 실행 중인 쪽이 중단되어야 한다.[1]
주기가 짧은 쪽인 이유
주기가 서로 다른 두 태스크만 놓고 보면 답이 바로 나온다. 주기가 긴 쪽에 높은 우선순위를 주고도 스케줄이 성립한다면, 우선순위를 뒤집어 주기가 짧은 쪽을 위로 올려도 스케줄은 여전히 성립한다. 반대 방향은 성립하지 않는다 — 주기가 짧은 쪽을 위에 두어야만 되는 조합이 있다. 그러므로 주기가 짧은 쪽에 높은 우선순위를 주는 편이 손해를 보지 않으며, 실행 시간을 보지 않고 요청률만으로 우선순위를 정하는 규칙이 여기서 나온다.[1]
최적성
최적성 명제는 이렇다. 어떤 태스크 집합에 대해 데드라인을 모두 지키는 고정 우선순위 배정이 하나라도 존재하면, rate monotonic 배정도 그 집합에 대해 데드라인을 모두 지킨다.[1] 대우로 읽는 편이 실무에서는 더 쓸모 있다. rate monotonic으로 스케줄되지 않는 집합은 어떤 고정 우선순위 배정으로도 스케줄되지 않는다.
증명의 얼개는 우선순위 쌍을 맞바꾸는 논증이다. 데드라인을 지키는 임의의 배정에서 우선순위가 인접한 두 태스크를 골랐을 때 위쪽 태스크의 주기가 더 길다면, 둘의 우선순위를 맞바꿔도 배정은 여전히 데드라인을 지킨다. 이런 인접 쌍 교환을 되풀이하면 어떤 배정이든 rate monotonic 순서로 바꿀 수 있으므로, 출발점이 데드라인을 지켰다면 rate monotonic도 지킨다.
최적성이 미치는 범위
최적성은 고정 우선순위 배정들 사이에서의 성질이고 그 밖으로 나가면 성립하지 않는다. 고정 우선순위 방식이 보장할 수 있는 프로세서 이용률의 최소 상한은 태스크 수가 커질수록 2의 자연로그, 곧 약 0.69에 가까워지는 반면, 현재 요청들의 데드라인을 보고 우선순위를 매기면 이용률 1까지 스케줄할 수 있다.[1] 상한값 자체와 그것을 쓰는 판정은 이용률 상한에서 다룬다.
최적의 범위
rate monotonic이 최적이라는 말은 고정 우선순위 배정들 사이에서 최적이라는 뜻이다. 어떤 알고리즘도 스케줄하지 못하는 집합을 이 배정이 스케줄한다는 뜻이 아니며, 우선순위를 job마다 다시 매기는 방식은 rate monotonic이 놓치는 집합도 스케줄할 수 있다.[1]
두 방식이 갈리는 지점
주기 5에 실행 시간 2인 태스크와 주기 7에 실행 시간 4인 태스크를 함께 돌린다고 하자. 이용률은 이다.
rate monotonic은 주기가 짧은 쪽에 높은 우선순위를 주므로, 시각 5에서 첫 태스크의 두 번째 job이 release되면 아직 한 단위가 남은 둘째 태스크를 선점한다. 둘째 태스크는 시각 7의 데드라인까지 남은 몫을 끝내지 못하고 데드라인을 놓친다.
절대 데드라인을 기준으로 삼으면 결과가 달라진다. 시각 5에서 실행 중이던 job의 데드라인은 7이고 새로 release된 job의 데드라인은 10이므로 선점이 일어나지 않고, 둘째 태스크가 시각 6에 완료된 뒤 첫 태스크가 실행되어 두 태스크 모두 데드라인을 지킨다. 이용률이 1 이하이므로 이 집합은 EDF로는 언제나 스케줄 가능하다.[1]
실무에서의 위치
고정 우선순위 레벨만 제공하고 시간 제약을 직접 다루지 않는 상용 커널 위에서도 주기의 역순으로 우선순위 레벨을 매기기만 하면 구현되기 때문에, rate monotonic은 실시간 응용에서 가장 널리 쓰이는 우선순위 배정이다.[2] 데드라인이 주기와 다를 때의 배정을 포함해 우선순위 배정 정책 전반은 고정 우선순위 스케줄링에서 다룬다.