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óź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