47. Algorytmy szeregowania zadań
Algorytm szergowania tzw. planista lub z ang. scheduler odpowiada
za przydzielenie
dostępu do procesora dla poszczególnych
procesów, dodatkowo musi uwzględniać priorytety, gotowość do
działania oraz
przeciwdziałać zagłodeniu procesu (czyli
niedopuścić żeby dany proces nigdy nie był wykonany)
W systemach operacyjnych czasu rzeczywistego najważniejsze aby dany
proces skończył
się przed zaplanowanym dla nie go czasem.
Rozróżniamy dwa rodzaje planistów: krótkoterminowy który wybiera
procesy spośród
gotowych do wykonania (musi być bardzo szybki)
oraz długoterminowy który wybiera zadania z pamięci masowej i
ładuje do pamięci
operacyjnej.
Obecne systemy oparte są o wielozadaniowość z wywłaszczeniem
* 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) - 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 start) - 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.
48. Model sekcji krytycznej i warunki jego poprawnego funkcjonowania.
* Sekcja krytyczna to ciąg operacji na pewnym zasobie
współdzielonym (zazwyczaj
pamięci) który musi być
wykonany tylko przez jeden proces z potencjalnie wielu innch.
Proces przed
wejściem do SK musi przejść przez sekcje
wejściową, gdy takowy już jest w SK wówczas inne w sekcji
wejściowej nie
mogą jej przejść i są wstrzymywane do chwili
przejścia procesu z SK do sekcji wyjściowej (która powiadamia ich o
opuszczeniu),
wtedy jeden z procesów z sekcji wejściowej zostanie wpuszczony do SK.
* Sekcji krytycznej musi spełniać kilka warunków aby działać
dobrze:
+ wzajemne wykluczenie - tylko jeden proces może przebywać i
wykonywać sekcje
krytyczną
+ warunek postępu - (ograniczona liczba wejść) tylko procesy w
sekcji wejściowej
mogą kandydować do wejścia w sekcje krytyczną
+ ograniczone czekanie - każdy proces aplikujący do sekcji
krytycznej musi kiedyś
do niej wejść (chyba, że sam zrezygnuje)
* Przykładowy algorytm
+ algorytm piekarniczy, każdy z procesów jest numerowny nazwijmy
ten numer p,
dodatkowo wejścia do sekcji krytycznej są także numerowane nazwijmy je k
wejść może proces o najniższym parze numerów (p, k) jeżeli
sekcja jest wolna. A
dlaczego para? Poniważ możliwe, że dwa procesy dostaną ten sam
numer k (a identyfikator p jest zawsze unikalny). Więc dlaczego
numery k skoro
wystarczą p? Nie każdy z procesów p będzie aplikował do sekcji
krytycznej.
* Znane sposoby realizacji sekcji krytycznej:
+ semafory (binarny, liczbowy)
+ mutexy
+ moniotry (wysoko poziomowe mechanizmy jezyków programowania)
49. Stronicowanie i stronicowanie na żądanie  wsparcie sprzętowe, korzyści
wynikające ze stosowania tych technologii.
* Stronicowanie jest jednym ze sposobów rozwiązania problemu
zewnętrznej
fragmentacji polegającym na dopuszczeniu nieciągłości
logicznej przestrzeni adresowej procesu. Zostało użyte przez
polskiego inżyniera
Jacka Karpińskiego w architekturze komputera K-202.
Podstawowa metoda stronicowania:
" Pamięć fizyczna dzielona jest na bloki stałej długości zwane
ramkami.
" Pamięć logiczna dzielona jest na bloki stałej długości zwane
stronami.
" Rozmiary stron i ramek są identyczne.
" Przy wykonywaniu procesu, strony z pamięci pomocniczej
wprowadzane są w dowolne
ramki pamięci operacyjnej.
W systemach komputerowych podział pamięci na mniejsze obszary o
ustalonej lub
zmiennej wielkości przydzielanie tym blokom adresów fizycznych lub
logicznych.
Historia. Stronicowanie pamięci fizycznej wykonywane było z powodu
ograniczenia
przestrzeni adresowej procesora (stronicowanie fizyczne).
* Stronicowanie na żądanie (angielskie demand paging), popularny
algorytm
stronicowania, opóz
niający sprowadzanie stron z dysku do chwili,
gdy zabraknie ich w wykonywanym procesie (czyli strona
sprowadzana jest z dysku
do pamięci wtedy gdy jest potrzebna);
rzadko stosowany w postaci czystej