Planowanie przydziału procesora Planowanie przydziału procesora leży u podstaw wieloprogramowych systemów operacyjnych. Celem wieloprogramowania jest maksymalizowanie wykorzystania jednostki centralnej przez stałe utrzymywanie w działaniu pewnej liczby procesów. Planowanie jest podstawową funkcją systemu operacyjnego. Użytkowanie niemal wszystkich zasobów komputerowych podlega planowaniu. Sukces w planowaniu przydziału procesora zależy od pewnej, dającej się zaobserwować właściwości procesów. W pamięci operacyjnej znajduje się kilka procesów jednocześnie. Kiedy jakiś proces musi czekać, wtedy system operacyjny odbiera mu procesor i oddaje do dyspozycji innego procesu. Schemat ten jest powtarzany. Zawsze gdy któryś proces musi czekać, inny proces może korzystać z procesora. Cykle faz procesora Wykonanie procesu składa się z następujących po sobie cykli działania procesora i oczekiwania na urządzenia zewnętrzne. Procesy naprzemiennie przechodzą od jednego do drugiego z tych dwu stanów. Wykonanie procesu zaczyna się od fazy procesora. Po niej następuje faza wejścia- wyjścia (ang. l/O burs/), po której proces znów przechodzi do fazy procesora, po czym ponownie do fazy wejścia-wyjścia itd. W końcu, w ostatniej fazie procesora, proces zamiast przejść do następnej fazy wejścia-wyjścia wysyła do systemu żądanie zakończenia swojego działania Proces ograniczony przez wejście-wyjście ma zazwyczaj wiele krótkich faz procesora. Proces ograniczony przez procesor może mieć mało, lecz bardzo długich faz procesora. Ten rozkład może mieć duże znaczenie przy dobieraniu właściwego algorytmu planowania przydziału procesora. Planista przydziału procesora Gdy tylko procesor zaczyna być bezczynny, system operacyjny musi wybrać do wykonywania jakiś proces z kolejki procesów gotowych. Wyboru dokonuje planista krótkoterminowy, czyli planista przydziału procesora. Decyzje o przydziale procesora mogą zapadać w następujących czterech sytuacjach: Proces przeszedł od stanu aktywności do stanu czekania (np. z powodu zamówienia na wejście-wyjście lub rozpoczęcia czekania na zakończenie działania któregoś z procesów potomnych). Proces przeszedł od stanu aktywności do stanu gotowości (np. wskutek wystąpienia przerwania). Proces przeszedł od stanu czekania do stanu gotowości (np. po zakończeniu operacji wejścia-wyjścia). Proces kończy działanie. W sytuacjach l i 4 nie ma możliwości wyboru. Kandydatem do przydziału procesora musi być nowy proces (jeśli taki istnieje w kolejce procesów gotowych). Natomiast w sytuacjach 2 i 3 można dokonać wyboru. Jeśli planowanie odbywa się tylko w warunkach 1 i 4, to mówimy o niewywlaszczeniowym schemacie planowania; w przeciwnym razie algorytm planowania jest wywłaszczeniowy. Program ekspediujący Odrębnym elementem zaangażowanym w planowanie przydziału procesora jest ekspedytor. Ekspedytor jest modułem, który faktycznie przekazuje procesor do dyspozycji procesu wybranego przez planistę krótkoterminowego. Ekspedytor powinien być możliwie jak najszybszy, gdyż jest wywoływany podczas każdego przełączania procesu. Do obowiązków ekspedytora należy:przełączanie kontekstu; przełączanie do trybu użytkownika; wykonanie skoku do odpowiedniej komórki w programie użytkownika w celu wznowienia działania programu. Czas, który ekspedytor zużywa na wstrzymanie jednego procesu i uaktywnienie innego, nazywa się opóźnieniem ekspedycji. Kryteria planowania -cz. I Wykorzystanie procesora: Dąży się do tego, aby procesor był nieustannie zajęty pracą. Wykorzystanie procesora może się wahać w granicach od O do 100%. W rzeczywistym systemie powinno się ono mieścić w przedziale od 40% (słabe obciążenie systemu) do 90% (intensywna eksploatacja systemu). Przepustowość: Jeśli procesor jest zajęty wykonywaniem procesów, to praca postępuje naprzód. Jedną z miar pracy jest liczba procesów kończonych w jednostce czasu, zwana przepustowością. Czas cyklu przetwarzania: Ważnym kryterium dla konkretnego procesu jest czas potrzebny na jego wykonanie. Czas upływający między chwilą nadejścia procesu do systemu a chwilą zakończenia procesu nazywa się czasem cyklu przetwarzania. Jest to suma okresów spędzonych na czekaniu na wejście do pamięci, czekaniu w kolejce procesów gotowych do wykonania, wykonywaniu procesu przez procesor i wykonywaniu operacji wejścia-wyjścia. Kryteria planowania -cz. II Czas oczekiwania:Algorytm planowania przydziału procesora nie ma faktycznie wpływu na czas, w którym proces działa lub wykonuje operacje wejścia-wyjścia; dotyczy on tylko czasu, który proces spędza w kolejce procesów gotowych do wykonania. Czas oczekiwania jest sumą okresów, w których proces czeka w kolejce procesów gotowych do działania. Czas odpowiedzi: W systemach interakcyjnych czas cyklu przetwarzania może nie być najlepszym kryterium. Często bywa tak, że proces produkuje pewne wyniki dość wcześnie i wykonuje następne obliczenia, pod-czas gdy poprzednie rezultaty są prezentowane użytkownikowi. Toteż kolej na miarą jest czas upływający między wysłaniem żądania (przedłożeniem zamówienia) a pojawieniem się pierwszej odpowiedzi. Ta miara, nosząca nazwę czasu odpowiedzi (ang. response time), określa, ile czasu upływa do rozpoczęcia odpowiedzi, ale nie obejmuje czasu potrzebnego na wyprowadzenie tej odpowiedzi. Czas odpowiedzi jest na ogół uzależniony od szybkości działania urządzenia wyjściowego. Planowane metodą FCFS Najprostszym ze znanych algorytmów planowania przydziału procesora jest algorytm „pierwszy zgłoszony - pierwszy obsłużony" (ang. first-come, first--served - FCFS). Według tego schematu proces, który pierwszy zamówi procesor, pierwszy go otrzyma. Implementację tego algorytmu łatwo się uzyskuje za pomocą kolejki FIFO. Algorytm FCFS wykazuje tzw. efektem konwoju polegającym na tym, że wszystkie pozostałe procesy czekają na zwolnienie procesora przez jeden wielki proces. Efekt ten powoduje niniejsze wykorzystanie procesora i urządzeń, niż byłoby to możliwe, gdyby najpierw pozwolono pracować krótszym procesom. Algorytm FCFS jest niewywłaszczający. Po objęciu kontroli nad procesorem proces utrzymuje ją do czasu, aż sam zwolni procesor wskutek zakończenia swego działania lub zamówienia operacji wejścia- wyjścia. Algorytm FCFS jest szczególnie kłopotliwy w systemach z podziałem czasu, w których jest ważne, aby każdy użytkownik dostawał swój przydział procesora w regularnych odstępach. Planowanie metodą SJF Inne podejście do planowania przydziału procesora umożliwia algorytm „najpierw najkrótsze zadanie" (ang. shortest-job-first - SJF). Algorytm ten wiąże z każdym procesem długość jego najbliższej z przyszłych faz procesora. Gdy procesor staje się dostępny, wówczas zostaje przydzielony procesowi mającemu najkrótszą następną fazę procesora. Jeśli dwa procesy mają następne fazy procesora równej długości, to kłopotu pozbywamy się, stosując algorytm FCFS. Można udowodnić, że algorytm SJF jest optymalny, tzn. daje minimalny średni czas oczekiwania dla danego zbioru procesów. Poważną trudność w algorytmie SJF sprawia określenie długości następnego zamówienia na przydział procesora. Dlatego też algorytm SJF jest często używany w planowaniu długoterminowym. Algorytm SJF może być wywłaszczający lub niewywłaszczający. Konieczność wyboru powstaje wówczas, gdy w kolejce procesów gotowych pojawia się nowy proces, a poprzedni proces jeszcze używa procesora. Nowy proces może mieć krótszą następną fazę procesora niż to, co jeszcze pozostało do wykonania w procesie bieżącym. Wywłaszczający algorytm SJF usunie w tej sytuacji dotychczasowy proces z procesora, podczas gdy niewywłaszczający algorytm SJF pozwoli bieżącemu procesowi na zakończenie fazy procesora. Wywłaszczającą metodę SJF przydziału procesora nazywa się czasami planowaniem metodą„najpierw najkrótszy pozostały czas" . Planowanie priorytetowe -cz. I Algorytm SJF (najpierw najkrótsze zadanie) jest szczególnym przypadkiem ogólnego algorytmu planowania priorytetowego. Każdemu procesowi przypisuje się priorytet, po czym przydziela
|
się procesor temu procesowi, którego priorytet jest najwyższy. Procesy o równych priorytetach planuje się w porządku FCFS. Algorytm SJF jest po prostu algorytmem priorytetowym, w którym priorytet (p) jest odwrotnością następnej (przewidywanej) fazy procesora. Im większa jest faza procesora, tym niższy staje się priorytet - i na odwrót. Planowanie priorytetowe może być wywłaszczające lub niewywłaszczające. Priorytet procesu dołączanego do kolejki procesów gotowych jest porównywany z priorytetem bieżąco wykonywanego procesu. Wywłaszczający algorytm priorytetowy spowoduje odebranie procesora bieżącemu procesowi, jeśli jego priorytet jest niższy od priorytetu nowo przybyłego procesu. Niewywłaszczający algorytm priorytetowy ustawi po prostu nowy proces na czele kolejki procesów gotowych do wykonania. Planowanie priorytetowe -cz. II Priorytety mogą być definiowane wewnętrznie lub zewnętrznie. Do wewnętrznego zdefiniowania priorytetu używa się jakiejś mierzalnej właściwości procesu (jednej lub wielu) i na jej podstawie oblicza się priorytet. Mogą to być na przykład: limity czasu, wielkość obszaru wymaganej pamięci, liczba otwartych plików, stosunek średniej fazy wejścia--wyjścia do średniej fazy procesora. Priorytety zewnętrzne są określane na podstawie kryteriów zewnętrznych wobec systemu operacyjnego - takich jak: ważność procesu, rodzaj i kwota opłat ponoszonych za użytkowanie komputera itp, Podstawowym problemem w planowaniu priorytetowym jest nieskończone blokowanie, zwane też głodzeniem. Polega ono na tym, że Algorytm planowania priorytetowego może pozostawić niektóre niskopriorytetowe procesy w stanie nie kończącego się czekania na procesor. Planowanie rotacyjne Algorytm planowania rotacyjnego (RR) zaprojektowano specjalnie dla systemów z podziałem czasu. W algorytmie tym stosuje małą jednostkę czasu, nazywaną kwantem czasu lub odcinkiem czasu. Kwant czasu wynosi zwykle od 10 do 100 milisekund. Kolejka procesów gotowych do wykonania jest traktowana jak kolejka cykliczna. Planista przydziału procesora przegląda tę kolejkę i każdemu procesowi przydziela odcinek czasu nie dłuższy od jednego kwantu czasu. W algorytmie planowania rotacyjnego żaden proces nie otrzyma więcej niż 1 kwant czasu procesora za jednym razem. Jeżeli faza procesora w danym procesie przekracza 1 kwant czasu, to proces będzie wywłaszczony i wycofany do kolejki procesów gotowych. Algorytm planowania rotacyjnego jest wywłaszczający. Wydajność algorytmu rotacyjnego w dużym stopniu zależy od rozmiaru kwantu czasu. W jednym z dwu skrajnych przypadków, gdy kwant czasu jest bardzo długi (nieskończony), metoda rotacyjna (RR) sprowadza się do polityki FCFS. Jeśli kwant czasu jest bardzo mały, to planowanie rotacyjne nazywa się dzieleniem procesora; sprawia ono (teoretycznie) na użytkownikach wrażenie, że każdy z n procesów ma własny procesor działający z 1/n szybkości rzeczywistego procesora. W oprogramowaniu należy jednak wziąć również pod uwagę wpływ przełączania kontekstu na zachowanie algorytmu rotacyjnego. Załóżmy, że mamy tylko jeden proces, którego faza procesora ma długość 10 jednostek czasu. Jeśli kwant czasu wynosi 12 jednostek, to dany proces skończy się w czasie krótszym niż l kwant, nie wymagając dodatkowej obsługi. Jeśli kwant wyniesie 6 jednostek czasu, to proces będzie już potrzebował dwu kwantów, a to spowoduje przełączanie kontekstu. Gdyby kwant czasu wynosił l jednostkę czasu, nastąpiłoby wówczas aż dziewięć przełączeń kontekstu, co musiałoby spowolnić wykonanie procesu. Od rozmiaru kwantu czasu zależy również czas cyklu przetwarzania. Średni czas cyklu przetwarzania zbioru procesów niekoniecznie poprawia się ze wzrostem kwantu czasu. Średni czas cyklu przetwarzania poprawia się na ogół wtedy, kiedy większość procesów kończy swoje kolejne fazy procesora w pojedynczych kwantach czasu. Planowanie wielopoziomowe Osobną klasę algorytmów planowania wytworzono na okoliczność sytuacji, w których jest możliwe łatwe zaliczenie procesów do kilku różnych grup. Na przykład powszechnie rozgranicza się procesy pierwszoplanowe, czyli interakcyjne, oraz procesy drugoplanowe, inaczej - wsadowe. Algorytm wielopoziomowego planowania kolejek rozdziela kolejkę procesów gotowych na osobne kolejki Każda kolejka ma własny algorytm planujący. Do kolejki procesów pierwszoplanowych można zastosować algorytm planowania rotacyjnego, a do kolejki procesów drugoplanowych można zastosować algorytm planowania przydziału procesora metodą FCFS. Ponadto musi istnieć jakieś planowanie między kolejkami, na ogół realizowane za pomocą stało priorytetowego planowania z wywłaszczeniami. Kolejka pierwszoplanowa może na przykład mieć bezwzględny priorytet nad kolejką procesów wsadowych. PW ze sprzężeniem zwrotnym Zazwyczaj w algorytmie wielopoziomowego planowania kolejek proces jest na stałe przypisywany do kolejki w chwili jego wejścia do systemu. Procesy nie mogą przemieszczać się między kolejkami. Planowanie wielopoziomowych kolejek ze sprzężeniem zwrotnym umożliwia w podobnych sytuacjach przemieszczanie procesów między kolejkami. Pomysł polega na rozdzieleniu procesów o różnych rodzajach faz procesora. Jeśli proces zużywa za dużo czasu procesora, to zostanie przeniesiony do kolejki o niższym priorytecie. Postępowanie to prowadzi do po-zostawienia procesów ograniczonych przez wejście-wyjście i procesów interakcyjnych w kolejkach o wyższych priorytetach. Podobnie, proces oczekujący zbyt długo w niskopriorytetowej kolejce może zostać przeniesiony do kolejki o wyższym priorytecie. Taki sposób postarzania procesów zapobiega ich głodzeniu. Planista wielopoziomowych kolejek ze sprzężeniem zwrotnym jest określony za pomocą następujących parametrów: liczby kolejek; algorytmu planowania dla każdej kolejki; metody użytej do decydowania o awansowaniu procesu do kolejki o wyższym priorytecie; metody użytej do decydowania o zdymisjonowaniu procesu do kolejki o niższym priorytecie; metody wyznaczającej kolejkę, do której trafia proces potrzebujący obsługi. Metody czasu rzeczywistego Programowanie w czasie rzeczywistym dzieli się na dwa rodzaje. Do wypełniania krytycznych zadań w gwarantowanym czasie są potrzebne rygorystyczne systemy czasu rzeczywistego. Ogólnie mówiąc, proces jest dostarczany wraz z instrukcją określającą ilość czasu, której wymaga on do zakończenia działania lub wykonania operacji wejścia--wyjścia. Na podstawie tych danych planista akceptuje ów proces, zapewniając jego wykonanie na czas, lub odrzuca zlecenie jako niewykonalne. Określa się to terminem rezerwacji zasobów. Łagodne systemy czasu rzeczywistego (ang. soft real-time systems) są mniej restrykcyjne. Wymaga się w nich, aby procesy o decydującym znaczeniu miały priorytet nad słabiej sytuowanymi. Implementacja łagodnego trybu przetwarzania w czasie rzeczywistym wymaga starannego zaprojektowania planisty i powiązanych z nim elementów systemu operacyjnego. Po pierwsze, system musi mieć planowanie priorytetowe, a procesy działające w czasie rzeczywistym muszą mieć najwyższy priorytet. Priorytety procesów czasu rzeczywistego nie mogą maleć z upływem czasu, niezależnie od tego, że może to dotyczyć priorytetów procesów wykonywanych poza trybem czasu rzeczywistego. Po drugie, opóźnienie ekpediowania procesów do procesora musi być małe. Im będzie ono mniejsze, tym szybciej proces czasu rzeczywistego będzie mógł rozpocząć działanie, poczynając od chwili, w której jest do niego gotowy. |
|
|