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^[1][2]. W 1973 roku Chung Laung Liu i James Layland odkryli warunek dostateczny algorytmu:

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

gdzie:

${\displaystyle n}$ – liczba zadań do wykonania,

${\displaystyle T_{i}}$ – okres powtarzania,

${\displaystyle 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ż:

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