Algorytm szeregowania

Algorytm_szeregowania
Algorytm szeregowania (ang. scheduler - planista) to algorytm rozwiązujący jedno z najważniejszych zagadnień informatyki - jak rozdzielić czas procesora i dostęp do innych zasobów pomiędzy zadania, które w praktyce zwykle o te zasoby konkurują.Najczęściej algorytm szeregowania jest implementowany jako część wielozadaniowego systemu operacyjnego, odpowiedzialna za ustalanie kolejności dostępu zadań do procesora. Oprócz systemów operacyjnych dotyczy w szczególności także serwerów baz danych.Za najwcześniejsze prace kładące podwaliny pod teorię algorytmów szeregowania można uznać wprowadzenie linii teoria_kategorii .php'>produkcyjnej przez Henry'ego Forda. Następnym krokiem milowym był algorytm Jacksona, stworzony w roku 1955. Ten algorytm również powstał w odniesieniu do planowania teoria_kategorii .php'>produkcji przemysłowej Algorytm szeregowania n zadań stanowiących zbiór jest to takie przydzielanie zadań procesorowi (lub procesorom), że każde zadanie jest przetwarzane do momentu zakończenia. Jednakże przetwarzanie danego zadania może być przerywane na bliżej nieokreślony czas.Dla jednego procesora jest to funkcja:, taka że:Zgodnie z tą definicją jest to funkcja, która dzieli czas na matematyka .php'>przedziały i każdemu matematyka .php'>przedziałowi przyporządkowuje jedną wartość naturalną będącą numerem procesu, który ma się w tym matematyka .php'>przedziale czasu wykonywać. Przyjęte jest, że przyporządkowanie wartości równej 0 oznacza procesor w stanie bezczynności. Numer nie musi mieć związku z priorytetem zadania.Chociaż wyjaśnienie wydaje się proste, zaprojektowanie i implementacja dobrego algorytmu szeregowania nastręcza wielu trudności.Zwykle implementacja algorytmu jest umieszczana w jądrze systemu, jednak nie zawsze. Ponieważ jego celem jest jedynie ustawianie listy zadań kierowanych do wykonywania a nie samo ich kierowanie, może być jednym ze zwykłych zadań, spełniającym usługę dla jądra Taką sytuację można spotkać w systemach opartych o mikrojądro.Planista musi także uwzględniać priorytety procesów i ich gotowość do wykonania oraz przeciwdziałać zagłodzeniu procesu poprzez przedłużający się brak dostępu do zasobów oraz tzw. inwersji priorytetów.Większość praktycznych rozwiązań oparta jest o nadawanie zadaniom priorytetów. Jednak już samo określanie priorytetu jest problemem nietrywialnym i nie można rozpatrywać go niezależnie od co najmniej kilku czynników:W praktyce pod względem czasu na jaki realizowane jest planowanie kolejki zadań, można wyróżnić dwa typy planistów:Problem szeregowania zadań powinien być rozpatrywany wielopłaszczyznowo i zwykle nie można go sprowadzić wyłącznie do rozdziału czasu procesora. Implementacja w typowym systemie powinna uwzględniać również takie elementy jak na przykład:W systemach operacyjnych codziennego użytku łatwo dokonać podziału na zadania interaktywne i nieinteraktywne. Zadania interaktywne przez większość czasu pozostają w stanie oczekiwania na reakcję użytkownika. Gdy taka reakcja nastąpi, powinny szybko przejść do stanu wykonywania aby ich użytkownik nie miał wrażenia, że program "zacina się". Problemem jest tu nieprzewidywalny moment, w którym do wykonywania powinno być skierowane zadanie interaktywne. Należy jednocześnie zapewnić jak najmniejsze opóźnienia w realizowaniu zadań nieinteraktywnych.Większość współcześnie spotykanych rozwiązań opiera się na wymuszaniu oddania kontroli czyli wielozadaniowości z wywłaszczaniem. Systemy dobrowolnego oddawania kontroli (wielozadaniowość oparta na współpracy) są rzadziej spotykane, gdyż pojedynczy źle zaimplementowany lub wrogi proces potrafi w takim wypadku zdestabilizować pracę całego systemu. Dość często stosuje się też rozwiązania mieszane - wymuszanie wobec zadań (realizowanych zwykle jako procesy) a współpraca wewnątrz zadania czyli zwykle między wątkami.Trzy wymienione wyżej algorytmy są stosowane najczęściej. Jednak lista algorytmów szeregowania jest bardzo długa i znajdują się na niej między innymi jeszcze takie algorytmy jak:W systemach operacyjnych czasu rzeczywistego (stosowanych m. in. w automatyce) najważniejszym zadaniem algorytmu szeregowania jest zapewnienie, by wykonanie danego procesu zakończyło się przed upływem zdefiniowanych dla niego ograniczeń czasowych. Opracowano w tym celu deterministyczne algorytmy szeregowania takie jak:Działania planisty zwykle muszą być skonsolidowane z całością systemu. Dlatego w praktycznie używanych algorytmach szeregowania pojawiają się dodatkowe cechy, takie jak: