• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Algorytm szeregowania

    Przeczytaj także...
    Inwersja priorytetów – zjawisko mogące występować w wielozadaniowych systemach operacyjnych takie, że w danej chwili wykonuje się inne zadanie niż powinno się wykonywać zgodnie z regułami algorytmu szeregowania.Przełączanie kontekstu, przełączanie zadań – proces zachowywania i odtwarzania stanu procesora (kontekstu), by wiele procesów mogło dzielić zasoby pojedynczego procesora. Przełączanie kontekstu polega na przydzielaniu procesorowi kolejnych zadań i jest ważną cechą wielozadaniowego systemu operacyjnego. Z reguły przełączanie kontekstu jest zadaniem intensywnym obliczeniowo i wiele czasu przy projektowaniu systemów operacyjnych poświęca się na optymalizację tego zadania.
    Kolejka (ang. queue) – liniowa struktura danych, w której nowe dane dopisywane są na końcu kolejki, a z początku kolejki pobierane są dane do dalszego przetwarzania (bufor typu FIFO, First In, First Out; pierwszy na wejściu, pierwszy na wyjściu).

    Dyspozytor (ang. scheduler), zwany czasami planistą niskopoziomowym (ang. low-level scheduler) – część systemu operacyjnego odpowiedzialna za przydzielanie czasu procesora w ramach przełączania zadań. Decyzja o tym, któremu procesowi przydzielić czas procesora jest podejmowana przez algorytm szeregowania. Do zadań dyspozytora należy m.in. przełączanie kontekstu.

    Earliest Deadline First – optymalny algorytm szeregowania zadań wykorzystywany w systemach czasu rzeczywistego, wykorzystujący kolejkę priorytetową do przechowywania zadań i przydzielania ich do wolnych procesów. Za każdym razem, kiedy w systemie pojawi się niezajęty proces (np. jeden z procesów ukończy swoje zadanie), z kolejki priorytetowej zostanie pobrane zadanie o najwyższym priorytecie (najbliższe do swojego deadlinu), a następnie przekazane do wykonania dla procesu.System operacyjny (ang. Operating System, skrót OS) – oprogramowanie zarządzające systemem komputerowym, tworzące środowisko do uruchamiania i kontroli zadań użytkownika.

    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:

  • Planowanie priorytetowe – wybierany jest proces o najwyższym priorytecie. W tej metodzie występuje problem nieskończonego blokowania (procesu o niskim priorytecie przez procesy o wysokim priotytecie). Stosuje się tu postarzanie procesów, polegające na powolnym podnoszeniu priorytetu procesów zbyt długo oczekujących.
  • Planowanie wielopoziomowe – zadania przypisywane są do kolejek szeregowania w zależności od parametru opisującego każde z zadań jakim w praktyce zwykle jest priorytet. Zadania w danej kolejce są następnie szeregowane określonym algorytmem takim jak na przykład FIFO lub round-robin i kierowane do wykonania. Jeśli w danej kolejce nie ma zadań gotowych do wykonywania, planista ponownie dokonuje analizy kolejki ale dla zadań o niższym priorytecie. Zwykle możliwa jest zmiana kolejki w której szeregowane jest zadanie, poprzez zmianę priorytetu zadania.
  • Planowanie wieloprocesorowe – na jednakowe lub różne procesory a także całe komputery;
  • Planowanie z uwzględnieniem mechanizmów synchronizacji zadań – ze względu na powiązanie zadań różnymi zasobami a nie tylko procesorem, konieczne (w celu uniknięcia problemu zakleszczeń) jest uwzględnienie aspektu dostępu do tych innych zasobów przez szeregowane zadania.
  • Informatyka – dyscyplina nauki zaliczana do nauk ścisłych oraz techniki zajmująca się przetwarzaniem informacji, w tym również technologiami przetwarzania informacji oraz technologiami wytwarzania systemów przetwarzających informację. Początkowo stanowiła część matematyki, później rozwinęła się do odrębnej dyscypliny – pozostaje jednak nadal w ścisłej relacji z matematyką, która dostarcza informatyce podstaw teoretycznych.Jądro systemu operacyjnego (ang. kernel) – podstawowa część systemu operacyjnego, która jest odpowiedzialna za wszystkie jego zadania.

    Algorytm szeregowania[]

    Algorytm szeregowania rozwiązuje jedno z najważniejszych zagadnień informatyki – jak rozdzielić czas procesora i dostęp do innych zasobów pomiędzy zadaniami, 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.

    Procesor (ang. processor), także CPU (ang. Central Processing Unit) – urządzenie cyfrowe sekwencyjne, które pobiera dane z pamięci, interpretuje je i wykonuje jako rozkazy. Wykonuje on ciąg prostych operacji (rozkazów) wybranych ze zbioru operacji podstawowych określonych zazwyczaj przez producenta procesora jako lista rozkazów procesora.Wielozadaniowość – cecha systemu operacyjnego umożliwiająca mu równoczesne wykonywanie więcej niż jednego procesu. Zwykle za poprawną realizację wielozadaniowości odpowiedzialne jest jądro systemu operacyjnego.

    Za najwcześniejsze prace kładące podwaliny pod teorię algorytmów szeregowania, można uznać wprowadzenie linii 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 produkcji przemysłowej.

    Mikrojądro (ang. microkernel) – rodzaj jądra systemu operacyjnego, które zawiera tylko najbardziej niezbędne elementy, takie jak funkcje zarządzania wątkami, komunikacją międzyprocesową, oraz obsługą przerwań i wyjątków.Wywłaszczenie – technika używana w środowiskach wielozadaniowych, w której algorytm szeregujący (scheduler) może wstrzymać aktualnie wykonywane zadanie (np. proces lub wątek), aby umożliwić działanie innemu. Dzięki temu rozwiązaniu zawieszenie jednego procesu nie powoduje blokady całego systemu operacyjnego. W systemach bez wywłaszczenia zadania jawnie informują scheduler, w którym momencie chcą umożliwić przejście do innych zadań. Jeżeli nie zrobią tego w odpowiednim czasie, system zaczyna działać bardzo wolno. Oprócz tego wywłaszczanie umożliwia szczegółowe określanie czasu, w jakim dany proces może korzystać z procesora. Wywłaszczanie w niektórych systemach operacyjnych może dotyczyć nie tylko programów, ale także samego jądra – przykładem takiego systemu jest Linux.

    Definicja[]

    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.

    Round robin (algorytm karuzelowy) to najprostszy algorytm szeregowania dla procesów w systemie operacyjnym, który nadaje każdemu procesowi odpowiednie przedziały czasowe, nie uwzględniając żadnych priorytetów. W związku z tym wszystkie procesy mają ten sam priorytet. W mechanizmach szeregowania używających priorytetów, często mechanizmu round robin używa się w stosunku do procesów o tym samym priorytecie.Henry Ford (ur. 30 lipca 1863 w Dearborn, Michigan, USA, zm. 7 kwietnia 1947 w Detroit) – przemysłowiec amerykański, który założył w Detroit w 1903 spółkę Ford Motor Company.

    Dla jednego procesora jest to funkcja:

    , taka że:

    Zadanie (ang. task) - w informatyce to zbiór instrukcji programu załadowanych do pamięci RAM i wykonywanych przez procesor.Zakleszczenie, blokada wzajemna (ang. deadlock) jest pojęciem opisującym sytuację, w której co najmniej dwie różne akcje czekają na siebie nawzajem, więc żadna nie może się zakończyć. Gracze zdobyli pewne unikatowe warunki niezbędne do wykonania kolejnego ruchu, ale żaden nie ma wszystkich i gra nie może być kontynuowana. Zakleszczenie może być zobrazowane przykładem ludzi rysujących wykresy. Dwie osoby pragną narysować wykres, do czego jest potrzebna linijka i ołówek. W momencie, kiedy jedna z nich zabierze ołówek, druga zaś linijkę dochodzi do sytuacji konfliktowej. Pierwsza osoba potrzebuje linijki, drugi zaś ołówka. Oba żądania nie mogą być spełnione – powstaje zakleszczenie, które to zazwyczaj jest kłopotliwe, gdyż nie ma pewnych i zawsze sprawdzonych rozwiązań, ażeby go uniknąć.

    Zgodnie z tą definicją jest to funkcja, która dzieli czas na przedziały i każdemu przedziałowi przyporządkowuje jedną wartość naturalną będącą numerem procesu, który ma się w tym 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.

    Przełączanie kontekstu, przełączanie zadań – proces zachowywania i odtwarzania stanu procesora (kontekstu), by wiele procesów mogło dzielić zasoby pojedynczego procesora. Przełączanie kontekstu polega na przydzielaniu procesorowi kolejnych zadań i jest ważną cechą wielozadaniowego systemu operacyjnego. Z reguły przełączanie kontekstu jest zadaniem intensywnym obliczeniowo i wiele czasu przy projektowaniu systemów operacyjnych poświęca się na optymalizację tego zadania.Linia produkcyjna albo linia montażowa – zespół stanowisk roboczych (maszynowych, ręcznych lub mieszanych) ugrupowanych według kolejności operacji procesu technologicznego. Na linii produkcyjnej części są łączone w główny produkt o wiele szybciej niż w przypadku produkcji rzemieślniczej. Linie produkcyjne to podstawa produkcji masowej. Zapoczątkował je amerykański koncern Ford.

    Chociaż wyjaśnienie wydaje się proste, zaprojektowanie i implementacja dobrego algorytmu szeregowania nastręcza wielu trudności.

    Implementacja[]

    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.

    Baza danych – zbiór danych zapisanych zgodnie z określonymi regułami. W węższym znaczeniu obejmuje dane cyfrowe gromadzone zgodnie z zasadami przyjętymi dla danego programu komputerowego specjalizowanego do gromadzenia i przetwarzania tych danych. Program taki (często pakiet programów) nazywany jest „systemem zarządzania bazą danych” (ang. database management system, DBMS).System operacyjny czasu rzeczywistego (ang. Real-Time Operating System - RTOS) to komputerowy system operacyjny, który został opracowany tak, by spełnić wymagania narzucone na czas wykonywania zadanych operacji. Systemy takie stosuje się jako elementy komputerowych systemów sterowania pracujących w reżimie czasu rzeczywistego - system czasu rzeczywistego.

    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:

  • Obszaru zastosowania systemu
  • Celu jaki ma osiągnąć każde z zadań
  • Zastosowanego algorytmu szeregowania
  • W praktyce pod względem czasu na jaki realizowane jest planowanie kolejki zadań, można wyróżnić dwa typy planistów:

    Zagłodzenie procesu (eng. process starvation) - w informatyce sytuacja w środowisku wielozadaniowym, w której dany proces nie jest w stanie zakończyć działania, ponieważ nie ma dostępu do procesora lub innego współdzielonego zasobu.Wsadowy system operacyjny (ang. batch operating system) – komputerowy system operacyjny, który na stałe rezyduje w pamięci operacyjnej. System ten najczęściej po wykonaniu jednego zadania przekazuje dane wyjściowe kolejnemu zadaniu, gdzie te dane służą jako dane wejściowe.
  • Planista długoterminowy wybiera procesy z pamięci masowej i ładuje do pamięci operacyjnej.
  • Planista krótkoterminowy odpowiada za ustalanie kolejności wykonywania procesów gotowych do wykonania. Musi być on bardzo szybki, w przeciwieństwie do planisty długoterminowego.
  • 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:

    Automatyka – (ang. automatic control lub control engineering) dziedzina techniki i nauki, która zajmuje się zagadnieniami sterowania różnorodnymi procesami, głównie technologicznymi i przemysłowymi (zwykle bez udziału lub z ograniczonym udziałem człowieka).
  • Korzystanie z zasobów sprzętowych (np. pamięć masowa, sieć)
  • Lokalność pamięci cache
  • Różne wymagania wobec procesów (priorytety, poziom interaktywności)
  • 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.

    Szeregowanie a wywłaszczanie[]

    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.

    Wybrane algorytmy szeregowania[]

    Używane najczęściej[]

  • FIFO – algorytm powszechnie stosowany, jeden z prostszych w realizacji, dający dobre efekty w systemach ogólnego przeznaczenia; zadanie wykonuje się aż nie zostanie wywłaszczone przez siebie lub inne zadanie o wyższym priorytecie;
  • Planowanie rotacyjne (round-robin, znane też jako algorytm karuzelowy) – każde z zadań otrzymuje kwant czasu; po spożytkowaniu swojego kwantu zostaje wywłaszczone i ustawione na końcu kolejki;
  • Planowanie sporadyczne – zadania otrzymują tak zwany "budżet czasu"; ten algorytm pomaga pogodzić wykluczające się reguły dotyczące szeregowania zadań okresowych i nieokresowych; wciąż nie jest implementowany przez wiele systemów, jednak znalazł się w standardzie POSIX;
  • Mniej powszechne[]

    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:

  • FCFS (first come, first serve) – Bardzo podobny do kolejki FIFO – Pierwszy przyjdzie, pierwszy wykonany. Algorytm ten dokonuje najsprawiedliwszego przydziału czasu (każdemu według potrzeb), jednak powoduje bardzo słabą interakcyjność systemu – pojedynczy długi proces całkowicie blokuje system na czas swojego wykonania, gdyż nie ma priorytetów zgodnie z którymi mógłby zostać wywłaszczony. Algorytm ten stosuje się jednak z powodzeniem w systemach wsadowych, gdzie operator ładuje zadania do wykonania, a one wykonują się do skutku.
  • SJF (shortest job first) – Najpierw najkrótsze zadanie. Jest algorytmem optymalnym ze względu na najkrótszy średni czas oczekiwania. W wersji z wywłaszczaniem, stosowana jest metoda: najpierw najkrótszy czas pracy pozostałej do wykonania. Problemem tego algorytmu jest głodzenie długich procesów – może się zdarzyć, że cały czas będą nadchodzić krótsze procesy, a wtedy proces dłuższy nigdy nie zostanie wykonany.
  • Deterministyczne[]

    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:

  • RMS,
  • EDF



  • w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)

    Reklama

    Czas generowania strony: 0.053 sek.