Rate-monotonic scheduling

Rate-monotonic scheduling (RMS) – optymalny algorytm planowania ze stałymi priorytetami używany w systemach operacyjnych czasu rzeczywistego. Może być stosowany tylko w celu szeregowania zadań, które pojawiają się periodycznie i nie występuje synchronizacja pomiędzy tymi zadaniami w celu komunikacji oraz dostępu do wspólnych zasobów. Priorytety są przypisywane przed rozpoczęciem wykonywania zadań i nie są zmieniane w trakcie działania algorytmu. Są określane na podstawie okresów powtarzania zadań – zadanie z najkrótszym okresem będzie miało najwyższy priorytet. Ponadto algorytm jest wywłaszczający – wykonywane jest zawsze zadanie z najwyższym priorytetem. W 1973 roku Chung Laung Liu i James Layland odkryli warunek dostateczny algorytmu:

$U=\sum _{i=1}^{n}{\frac {C_{i}}{T_{i}}}\leqslant n({2}^{1/n}-1),$

gdzie:

$n$ – liczba zadań do wykonania,

$T_{i}$ – okres powtarzania,

$C_{i}$ – czas wykonania zadania.

Udowodnili także, że zbiór tych zadań okresowych zawsze będzie wykonywany przed terminem, jeżeli współczynnik wykorzystania procesora będzie nie większy niż:

$\lim _{n\to \infty }n({\sqrt[{n}]{2}}-1)=\ln 2\approx 0{,}693147$.