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}⩽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ż:

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