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].

Przypisy

1. Algorytmy planowania zadań periodycznych. [dostęp 2016-11-12]. (pol.).
2. Algorytm RMS (Rate Monotonic Scheduling) szeregowania zadań w systemie operacyjnym czasu rzeczywistego. [dostęp 2016-11-12]. [zarchiwizowane z tego adresu (2016-11-13)]. (pol.).
3. Chung Laung Liu, James Layland. Scheduling algorithms for multiprogramming in a hard real-time environment. „Journal of the ACM”. 20 (1), s. 46–61, 1973. DOI: 10.1145/321738.321743.