Rate-monotonic scheduling

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

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:

,

gdzie to liczba zadań do wykonania, to okres powtarzania, a to 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ż:

[3].

Przypisy[edytuj | edytuj kod]

  1. Algorytmy planowania zadań periodycznych (pol.). [dostęp 2016-11-12].
  2. Algorytm RMS (Rate Monotonic Scheduling) szeregowania zadań w systemie operacyjnym czasu rzeczywistego (pol.). [dostęp 2016-11-12].
  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.