SCHED_DEADLINE

Umiejscowienie harmonogramu procesów w uproszczonej strukturze jądra Linuksa.

SCHED_DEADLINE to harmonogram procesora dostępny w jądrze Linuksa od wersji 3.14, oparty na algorytmach Earliest Deadline First (EDF) i Constant Bandwidth Server (CBS), obsługujący rezerwacje zasobów: każde zadanie zaplanowane w ramach takiej polityki jest powiązane z budżetem Q (aka runtime ) i okres P odpowiadający deklaracji jądra, że ​​zadanie wymaga Q jednostek czasu co P jednostek czasu na dowolnym procesorze. To sprawia, że ​​SCHED_DEADLINE szczególnie nadaje się do czasu rzeczywistego aplikacji, takich jak multimedia czy sterowanie przemysłowe, gdzie P odpowiada minimalnemu czasowi, jaki upływa między kolejnymi aktywacjami zadania, a Q odpowiada najgorszemu czasowi wykonania potrzebnemu do każdej aktywacji zadania.

Podstawowe informacje na temat harmonogramów procesora w jądrze systemu Linux

Jądro Linuksa zawiera różne klasy harmonogramów. Domyślnie jądro używa mechanizmu harmonogramu o nazwie Completely Fair Scheduler (CFS), wprowadzonego w wersji jądra 2.6.23. Wewnętrznie ta domyślna klasa programu planującego jest również znana jako SCHED_NORMAL , a jądro zawiera również dwie zgodne z POSIX klasy planowania czasu rzeczywistego o nazwach SCHED_FIFO ( first-in-first-out w czasie rzeczywistym ) i SCHED_RR (ang. pierwszeństwo przed klasą domyślną. SCHED_DEADLINE _ Klasa planowania została dodana do programu planującego Linuksa w wersji 3.14 głównej linii jądra systemu Linux , wydanej 30 marca 2014 r. i ma pierwszeństwo przed wszystkimi innymi klasami planowania.

Domyślny harmonogram, CFS, bardzo dobrze radzi sobie z różnymi przypadkami użycia. Na przykład podczas łączenia obciążeń wsadowych, takich jak długotrwałe kompilacje kodu lub przetwarzanie liczb, z aplikacjami interaktywnymi, takimi jak aplikacje komputerowe, multimedia i inne, CFS dynamicznie obniża priorytety zadań wsadowych na rzecz zadań interaktywnych. Jednakże, gdy aplikacja wymaga przewidywalnego i precyzyjnego harmonogramu, zwykle musi ona zostać skierowana do jednego z innych programów planujących w czasie rzeczywistym, SCHED_RR lub SCHED_FIFO, które stosują stały priorytet do planowania zadań według priorytetów i których zadania są planowane przed jakimkolwiek zadaniem w klasie SCHED_NORMAL.

Operacja

Podczas mieszania obciążeń w czasie rzeczywistym z heterogenicznymi wymaganiami czasowymi w tym samym systemie dobrze znanym problemem SCHED_RR i SCHED_FIFO jest to, że ponieważ są one oparte na priorytetach zadań, zadania o wyższym priorytecie trwają dłużej niż oczekiwano, mogą arbitralnie opóźniać zadania o niższym priorytecie zadania w sposób niekontrolowany.

W przypadku SCHED_DEADLINE zamiast tego zadania deklarują niezależnie swoje wymagania dotyczące czasu, pod względem czasu wykonywania na zadanie potrzebnego w każdym okresie na zadanie (i należnego w terminie na zadanie od początku każdego okresu), a jądro akceptuje je w harmonogramie po test planowania. Teraz, jeśli zadanie próbuje działać dłużej niż przydzielony budżet, jądro zawiesi to zadanie i odłoży jego wykonanie do następnego okresu aktywacji. Ta , która nie oszczędza pracy, umożliwia mu zapewnienie izolacji czasowej wśród zadań. Powoduje to ważną właściwość, że w systemach jednoprocesorowych lub partycjonowanych systemach wieloprocesorowych (gdzie zadania są podzielone na dostępne procesory, więc każde zadanie jest przypięte do określonego procesora i nie może migrować), wszystkie zaakceptowane SCHED_DEADLINE zadania mają gwarancję, że zostaną zaplanowane na całkowity czas równy ich budżetowi w każdym oknie czasowym tak długo, jak ich okres, chyba że samo zadanie blokuje się i nie musi być uruchamiane. Cechą charakterystyczną algorytmu CBS jest również to, że gwarantuje on czasową izolację również w przypadku blokowania zadań i wznawiania ich wykonania: odbywa się to poprzez resetowanie terminu harmonogramu zadania na cały okres, gdy zadanie budzi się zbyt późno. W ogólnym przypadku zadań, które można swobodnie migrować na procesorze wieloprocesorowym, ponieważ SCHED_DEADLINE implementuje globalne EDF, obowiązuje ogólne ograniczenie opóźnienia dla globalnego EDF, jak wyjaśniono w.

Aby lepiej zrozumieć, jak działa harmonogram, rozważ zestaw zadań SCHED_DEADLINE z potencjalnie różnymi okresami, których termin ostateczny jest równy okresowi. Dla każdego zadania, oprócz skonfigurowanego czasu wykonania i (względnego) okresu, jądro śledzi bieżący czas wykonania i aktualny (bezwzględny) termin . Zadania są planowane na procesorach na podstawie ich bieżących terminów przy użyciu globalnego EDF. Gdy zasady planowania zadań są początkowo ustawione na SCHED_DEADLINE , bieżący termin jest inicjowany na bieżący czas plus skonfigurowany okres, a bieżący budżet jest równy skonfigurowanemu budżetowi. Za każdym razem, gdy zadanie ma zostać uruchomione na dowolnym procesorze, jądro pozwala mu działać co najwyżej z dostępnym bieżącym budżetem, a za każdym razem, gdy zadanie jest anulowane, jego bieżący budżet jest zmniejszany o czas jego wykonywania. Gdy bieżący budżet spadnie do zera, zadanie zostaje zawieszone (zablokowane) do następnego okresu aktywacji, kiedy to bieżący budżet zostanie ponownie uzupełniony do skonfigurowanej wartości, a termin zostanie przesunięty do przodu o wartość równą okresowi zadania.

To nie wystarcza do zagwarantowania czasowej izolacji . Zadanie zawieszające się wkrótce po jego aktywacji, a następnie budzące się blisko bieżącego terminu lub nawet później, obudziłoby się z prawie całym skonfigurowanym budżetem, z bieżącym terminem, który jest bardzo bliski wygaśnięcia lub nawet w przeszłości . W takich warunkach zadanie to zostałoby zaplanowane przed jakimkolwiek innym, a na systemie jednoprocesorowym mogłoby opóźnić wykonanie dowolnego innego zadania terminowego na tyle, na ile pozwalałby mu budżet. Aby uniknąć tego problemu, SCHED_DEADLINE przyjmuje regułę planowania pobudek zdefiniowaną w algorytmie CBS. Kiedy zadanie się budzi, jeśli od zablokowania zadania upłynął stosunkowo krótki czas, poprzedni bieżący termin i budżet pozostają niezmienione dla zadania. Jeśli jednak upłynął zbyt długi czas, jądro resetuje bieżący termin do bieżącego czasu plus okres rezerwacji, a bieżący budżet do przydzielonego budżetu rezerwacji. Aby uzyskać dłuższe wyjaśnienie z przykładami, zob.

W systemie wieloprocesorowym lub wielordzeniowym SCHED_DEADLINE implementuje globalny EDF, dzięki czemu zadania mogą migrować między dostępnymi procesorami. W takim przypadku skonfigurowany budżet to całkowity skumulowany czas, przez jaki zadanie może działać na dowolnym procesorze w każdym okresie. Jednak harmonogram uwzględnia również maski koligacji zadań, dzięki czemu można łatwo tworzyć partycjonowane scenariusze planowania, partycjonowanie zadań w grupach, w których każda grupa jest ograniczona do określonego procesora, lub scenariusze planowania klastrowego, uzyskiwane również przez partycjonowanie procesorów i przypięcie każdej partycji zadań aż do określonej partycji procesorów.

Szczegółowe informacje techniczne dotyczące SCHED_DEADLINE znajdują się w dokumentacji dostępnej w drzewie źródeł jądra. Aby uzyskać więcej informacji na temat CBS i sposobu, w jaki umożliwia on czasową izolację, zapoznaj się z oryginalnym artykułem CBS lub sekcją dotyczącą CBS w tym artykule, która pojawiła się na lwn.net.

Historia

Początkowy pomysł klasy planowania Linuksa opartej na algorytmie Earliest Deadline First (EDF) narodził się w małym kontekście Real-Time Systems (ReTiS) Lab of Scuola Superiore Sant'Anna i jej spin-offowej firmy Evidence Srl. Następnie firma Evidence Srl wykorzystała finansowanie projektu ACTORS, wspieranego przez Komisję Europejską poprzez program ramowy 7PR na finansowanie i promowanie rozwoju pierwszych wersji poprawki. Oryginalna wersja została opracowana przez Dario Faggioli (kontrakt Evidence Srl na opracowanie pierwszych trzech wersji) i Juri Lelli (od czwartej wersji) ze sporadyczną pomocą Michaela Trimarchi i Fabio Checconi. Johan Eker był odpowiedzialny za koordynację w ramach ACTORS i wsparcie ze strony firmy Ericsson. Juri Lelli, Luca Abeni i Claudio Scordino współpracowali przy opracowywaniu funkcji odzyskiwania (tj. GRUB) i skalowania częstotliwości (tj. GRUB-PA).

Łatka była okresowo udostępniana społeczności jądra za pośrednictwem listy mailingowej jądra systemu Linux (LKML). Każde wydanie dostosowywało kod do najnowszej wersji jądra i uwzględniało uwagi otrzymane przy poprzednim zgłoszeniu. Wraz ze wzrostem popularności programu planującego większa liczba programistów jądra zaczęła przekazywać swoje opinie i swój wkład.

Projekt pierwotnie nosił nazwę SCHED_EDF i został zaprezentowany społeczności jądra Linuksa w 2009 roku. Po kilku tygodniach pod tą nazwą został również przedstawiony warsztatowi Real-Time Linux Workshop. Nazwa została następnie zmieniona na SCHED_DEADLINE na prośbę społeczności jądra Linuksa.

Na przestrzeni lat ukazały się następujące wersje:

• Pierwsza wersja programu planującego została przesłana 22 września 2009 r. pod nazwą SCHED_EDF .
• Pierwsza wersja harmonogramu po zmianie nazwy na SCHED_DEADLINE została przesłana do LKML 16 października 2009 r.
• Druga wersja programu planującego została przesłana do LKML 28 lutego 2010 r. i zawierała pierwszą implementację protokołu Deadline Inheritance.
• Trzecia wersja programu planującego została przesłana do LKML 29 października 2010 r. i dodała obsługę globalnego/klastrowego planowania wieloprocesorowego poprzez dynamiczne migracje zadań.
• Czwarta wersja programu planującego została przesłana do LKML 6 kwietnia 2012 r. i zapewnia lepszą obsługę wyboru rq dla dynamicznej migracji zadań oraz lepszą integrację z PREEMPT_RT .
• Piąta wersja harmonogramu została przesłana do LKML 23 maja 2012 r.
• Szósta wersja harmonogramu została przesłana do LKML 24 października 2012 r.
• Siódma wersja programu planującego została przesłana do LKML 11 lutego 2013 r. Wewnętrzna matematyka została ograniczona do rozdzielczości mikrosekund (aby uniknąć przepełnienia), a tag RFC został usunięty.
• Ósma wersja harmonogramu została przesłana do LKML 14 października 2013 r.
• Dziewiąta wersja harmonogramu została przesłana do LKML 7 listopada 2013 r.
• Ostatnia wersja została włączona do głównego jądra Linuksa (numer zatwierdzenia a0fa1dd3cdbccec9597fe53b6177a9aa6e20f2f8) i od tego czasu jest jego stałą częścią.

Artykuły na stronach internetowych Linux Weekly News i Phoronix argumentowały, że SCHED_DEADLINE może zostać włączony do głównego jądra w następnych wydaniach. Wreszcie, po ponad czterech latach i przedłożeniu dziewięciu wydań, łatka została zaakceptowana i włączona do jądra Linuksa 3.14.

Przed SCHED_DEADLINE Laboratorium Systemów Czasu Rzeczywistego (ReTiS) w Scuola Superiore Sant'Anna dostarczyło różne inne implementacje open-source CBS i jego wariantów w jądrze Linuksa, w kontekście innych europejskich projektów badawczych, w tym OCERA, AQuoSA architektura w ramach projektu FRESCOR oraz IRMOS. Jednak te wcześniejsze wysiłki rozpoczęły się od podejścia akademickiego, w którym głównym celem było zebranie wyników eksperymentów dla projektów badawczych, a nie zapewnienie implementacji odpowiedniej do integracji z głównym jądrem. Dzięki IRMOS laboratorium miało pierwszy poważny kontakt z programistami jądra Linuksa.

Od wersji 4.13 jądra SCHED_DEADLINE uzupełnia CBS algorytmem Greedy Reclamation of Unused Bandwidth (GRUB). Wsparcie zostało opracowane przez ReTiS Lab we współpracy z Evidence Srl.

Od wersji jądra 4.16 SCHED_DEADLINE był dalej rozwijany w celu zmniejszenia zużycia energii na platformach ARM poprzez implementację algorytmu GRUB-PA. Prace zostały wykonane przez ARM Ltd. we współpracy z Evidence Srl i Scuola Superiore Sant'Anna.

Wykształcenie

SCHED_DEADLINE został przedstawiony w ramach niektórych warsztatów akademickich, konferencji i czasopism:

• Dario Faggioli, Fabio Checconi, Michael Trimarchi, Claudio Scordino, An EDF sheduling class for the Linux kernel , 11th Real-Time Linux Workshop (RTLWS), Drezno, Niemcy, wrzesień 2009
• Nicola Manica, Luca Abeni, Luigi Palopoli, Dario Faggioli, Claudio Scordino, Schedulable Device Drivers: Implementation and Experimental Results , International Workshop on Operating Systems Platforms for Embedded Real-Time Applications (OSPERT), Bruksela, Belgia, lipiec 2010 r.
• Juri Lelli, Giuseppe Lipari, Dario Faggioli, Tommaso Cucinotta, Wydajna i skalowalna implementacja globalnego EDF w Linuksie , International Workshop on Operating Systems Platforms for Embedded Real-Time Applications (OSPERT), Porto (Portugalia), lipiec 2011.
• Enrico Bini, Giorgio Buttazzo, Johan Eker, Stefan Schorr, Raphael Guerra, Gerhard Fohler, Karl-Erik Arzen, Vanessa Romero Segovia, Claudio Scordino, Zarządzanie zasobami w systemach wielordzeniowych: podejście aktorów , IEEE Micro, tom. 31, nr. 3, s. 72–81, maj/czerwiec 2011.
• Andrea Parri, Juri Lelli, Mauro Marinoni, Giuseppe Lipari, Design and Implementation of the Multiprocessor Bandwidth Inheritance Protocol on Linux , 15th Real-Time Linux Workshop (RTLWS), Lugano-Manno, Szwajcaria, październik 2013 r.
• Luca Abeni, Juri Lelli, Claudio Scordino, Luigi Paolopoli, Greedy CPU reclaiming for SCHED_DEADLINE , Proceedings of 16th Real-Time Linux Workshop (RTLWS), Düsseldorf, Niemcy, październik 2014 r.
• Juri Lelli, Claudio Scordino, Luca Abeni, Dario Faggioli, Planowanie terminów w jądrze Linuksa , Oprogramowanie: praktyka i doświadczenie, 46 (6): 821–839, czerwiec 2016 r.
• Claudio Scordino, Luca Abeni, Juri Lelli, Energy-Aware Real-Time Scheduling in the Linux Kernel , 33rd ACM/SIGAPP Symposium on Applied Computing (SAC 2018), Pau, Francja, kwiecień 2018 r.
• Claudio Scordino, Luca Abeni, Juri Lelli, Efektywność energetyczna w czasie rzeczywistym w systemie Linux: teoria i praktyka , ACM SIGAPP Applied Computing Review (ACR) tom. 18 nr 4, 2018.

Projekt był również prezentowany na Kernel Summit w 2010 roku, na konferencji Linux Plumbers Conference 2012 oraz na konferencji Embedded Linux Conference 2013.

Inne informacje

Projekt ma oficjalną stronę. Przed integracją z główną linią kod był publicznie dostępny na stronie GitHub, która zastąpiła poprzednie repozytorium na Gitorious. Od czasu integracji z linią główną oficjalny kod jest zawarty w drzewie źródłowym jądra Linuksa.

Kilka artykułów ukazało się w Linux Weekly News , Slashdot , OSNews i LinuxToday. Film został również przesłany na YouTube.

Przed integracją z głównym jądrem SCHED_DEADLINE był już zintegrowany z Projektem Yocto . istniało również zainteresowanie włączeniem do Linaro .

Zobacz też

• Całkowicie uczciwy harmonogram