Tekst źródłowy strony Rate-monotonic scheduling

'''Rate-monotonic scheduling''' ('''RMS''') – optymalny [[dyspozytor|algorytm planowania]] ze stałymi priorytetami używany w [[system operacyjny czasu rzeczywistego|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<ref>{{cytuj stronę |url = https://sites.google.com/site/systemyczasurzeczywistego/home/zagadnienia-teoretyczne/algorytmy-planowania-zadan-periodycznych| tytuł = Algorytmy planowania zadań periodycznych| język = pl| data dostępu = 2016-11-12}}</ref><ref>{{cytuj stronę| url = http://optimea.lh.pl/air_gruby/39-50/OPRACOWANIE/45.pdf| tytuł = Algorytm RMS (Rate Monotonic Scheduling) szeregowania zadań w systemie operacyjnym czasu rzeczywistego| język = pl| data dostępu = 2016-11-12| archiwum = https://web.archive.org/web/20161113044828/http://optimea.lh.pl/air_gruby/39-50/OPRACOWANIE/45.pdf| zarchiwizowano = 2016-11-13}}</ref>. W 1973 roku Chung Laung Liu i James Layland odkryli warunek dostateczny algorytmu:
:: <math>U = \sum_{i=1}^n \frac{C_i}{T_i} \leqslant n({2}^{1/n} - 1),</math>

gdzie:
: <math>n</math> – liczba zadań do wykonania,
: <math>T_i</math> – okres powtarzania,
: <math>C_i</math> – 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ż:
:: <math>\lim_{n \to \infty} n(\sqrt[n]{2} - 1) = \ln 2 \approx 0{,}693147</math><ref>{{cytuj pismo |nazwisko = Liu| imię = Chung Laung| nazwisko2 = Layland| imię2 = James| tytuł = Scheduling algorithms for multiprogramming in a hard real-time environment| czasopismo = Journal of the ACM| wolumin = 20| wydanie = 1| strony = 46–61| data = 1973| doi = 10.1145/321738.321743}}</ref>.

== Przypisy ==
{{Przypisy}}

[[Kategoria:Algorytmy]]