Prezentacja zaliczeniowa:

Przedstawienie działania

algorytmów

Prezentacja zaliczeniowa:

Przedstawienie działania

algorytmów

Wykonawca: Bartosz Zawadzki (201066)

Prowadzący: mgr inż. Karol Puchała

Wykonawca: Bartosz Zawadzki (201066)

Prowadzący: mgr inż. Karol Puchała

Dane Procesów:

Nr.

procesu

Czas

trwania

fazy

Czas

przybycia

Priorytet

P10

P11

P12

P13

P14

P15

Algorytm SJF

 Algorytm SJF (ang. shortest-job-first), czyli "najkrótsze zadanie najpierw", opiera swe

działanie na powiązaniu procesu z długością jego najbliższej fazy. Procesor zostaje
przydzielony procesowi, który ma najkrótszą następną fazę procesora. W przypadku,
gdy dwa procesy mają następne fazy procesora równe, stosuje się algorytm FCFS.



Algorytm SJF (ang. shortest-job-first), czyli "najkrótsze zadanie najpierw", opiera swe
działanie na powiązaniu procesu z długością jego najbliższej fazy. Procesor zostaje
przydzielony procesowi, który ma najkrótszą następną fazę procesora. W przypadku,
gdy dwa procesy mają następne fazy procesora równe, stosuje się algorytm FCFS.

Algorytm SJF daje minimalny średni czas dla danego
zbioru procesów. Mówimy, że algorytm SJF
jest optymalny.

 Dużym problemem w algorytmie SJF jest określenie długości następnego zamówienia

na przydział procesora. Przy planowaniu długoterminowym (zadań), za czynnik ten
możemy przyjąć limit czasu procesu, określony przez użytkownika, który zadanie
przedłożył. Algorytm SJF jest więc chętnie używany w planowaniu długoterminowym.
Natomiast w przypadku planowania krótkoterminowego, nie ma sposobu na określenie
długości następnej fazy procesora. Dlatego też oszacowuje się tę wartość, obliczając ją
na ogół jako średnią wykładniczą pomiarów długości poprzednich faz procesora.



Dużym problemem w algorytmie SJF jest określenie długości następnego zamówienia
na przydział procesora. Przy planowaniu długoterminowym (zadań), za czynnik ten
możemy przyjąć limit czasu procesu, określony przez użytkownika, który zadanie
przedłożył. Algorytm SJF jest więc chętnie używany w planowaniu długoterminowym.
Natomiast w przypadku planowania krótkoterminowego, nie ma sposobu na określenie
długości następnej fazy procesora. Dlatego też oszacowuje się tę wartość, obliczając ją
na ogół jako średnią wykładniczą pomiarów długości poprzednich faz procesora.

Diagram Gantta dla zadanych
procesów:

P13

P14

P11

P12

P15

0 21 23 28 33 41 51 64 78 93 108 125 149 173
198 226

Średni czas oczekiwania:

 (0+21+23+28+33+41+51+64+78+93+108+125+149+173+198) : 15=79
 Średni czas oczekiwania wynosi => 79



(0+21+23+28+33+41+51+64+78+93+108+125+149+173+198) : 15=79



Średni czas oczekiwania wynosi => 79

Algorytm RR (Planowania
Rotacyjnego):

 Algorytm planowania rotacyjnego (ang. round-robin - RR) jest oparty na algorytmie

FCFS, jednakże różni się od FCFS faktem, że możliwe jest wywłaszczanie. Algorytm ten
jest chętnie stosowany w systemach z podziałem czasu.



Algorytm planowania rotacyjnego (ang. round-robin - RR) jest oparty na algorytmie
FCFS, jednakże różni się od FCFS faktem, że możliwe jest wywłaszczanie. Algorytm ten
jest chętnie stosowany w systemach z podziałem czasu.

Zasada działania algorytmu jest następująca. Z każdym procesem
powiązany jest kwant czasu, najczęściej 10 do 100 ms.

 Procesom znajdującym się w kolejce (traktowanej jako cykliczna) procesów gotowych

do wykonania, przydzielane są odpowiednie odcinki czasu, nie dłuższe niż jeden kwant
czasu.

 Do implementacji algorytmu, podobnie jak w przypadku FCFS, używa się kolejki FIFO -

brany jest pierwszy proces z wyjścia kolejki, ustawiany jest timer na przerwanie po
upływie 1 kwantu czasu i proces jest wysyłany do procesora. Jeżeli czas trwania fazy
procesu jest krótszy od 1 kwantu czasu, proces sam zwolni procesor i rozpocznie się
obsługiwanie kolejnego procesu z kolejki. Jeżeli proces ma dłuższą fazę od 1 kwantu
czasu, to nastąpi przerwanie zegarowe systemu operacyjnego, nastąpi przełączenie
kontekstu, a proces do niedawna wykonywany, trafi na koniec kolejki procesów
gotowych do wykonania.



Procesom znajdującym się w kolejce (traktowanej jako cykliczna) procesów gotowych
do wykonania, przydzielane są odpowiednie odcinki czasu, nie dłuższe niż jeden kwant
czasu.



Do implementacji algorytmu, podobnie jak w przypadku FCFS, używa się kolejki FIFO -
brany jest pierwszy proces z wyjścia kolejki, ustawiany jest timer na przerwanie po
upływie 1 kwantu czasu i proces jest wysyłany do procesora. Jeżeli czas trwania fazy
procesu jest krótszy od 1 kwantu czasu, proces sam zwolni procesor i rozpocznie się
obsługiwanie kolejnego procesu z kolejki. Jeżeli proces ma dłuższą fazę od 1 kwantu
czasu, to nastąpi przerwanie zegarowe systemu operacyjnego, nastąpi przełączenie
kontekstu, a proces do niedawna wykonywany, trafi na koniec kolejki procesów
gotowych do wykonania.

Diagram Gantta dla zadanych
procesów z uwzględnieniem kwantu
czasu = 4:

P10 P11 P12 P13 P14 P15

P11

P12

P13

P14

P15

P11

P12

P14

P15

P11

P12

P14

P15

0 4

12 16 20 24 28 32 36 38 42 46 50

54 58

58 62 66 70 74 78 82 83 87 91 95 99 100
104 108

108

112

116

120

124 126 130

134 138 142 146 150

150

154

158 162 166 170 173 175 178

179

183

183 187 191 195

196

200 204 208 209 213

217

221 225

229

230

Czasy oczekiwania:



P1: 0+58-4+108-62+150-112+183-154+204-187+221-208=197



P2: 188



P3: 189



P4: 179



P5: 116



P6: 193



P7: 54



P8: 51



P9: 158



P10: 36



P11: 161



P12: 166



P13: 53



P14: 166



P15: 197



P1: 0+58-4+108-62+150-112+183-154+204-187+221-208=197



P2: 188



P3: 189



P4: 179



P5: 116



P6: 193



P7: 54



P8: 51



P9: 158



P10: 36



P11: 161



P12: 166



P13: 53



P14: 166



P15: 197

Średni czas oczekiwania:

 (197+188+189+179+116+193+54+158+36+161+166+53+166+197) : 15=136,8(6)
 Średni czas oczekiwania wynosi => 136,87



(197+188+189+179+116+193+54+158+36+161+166+53+166+197) : 15=136,8(6)



Średni czas oczekiwania wynosi => 136,87

Algorytm Priorytetowy

 Algorytm planowania priorytetowego jest ogólnym przypadkiem algorytm SJF. Zamiast

długości następnej fazy z algorytmu SJF, procesowi przypisuje się priorytet. Procesy o
wyższym priorytecie mają pierwszeństwo w dostępie do procesora, przed procesami o
priorytecie niższym. Procesom o równych priorytetach przydziela się procesor zgodnie
z algorytmem FCFS.



Algorytm planowania priorytetowego jest ogólnym przypadkiem algorytm SJF. Zamiast
długości następnej fazy z algorytmu SJF, procesowi przypisuje się priorytet. Procesy o
wyższym priorytecie mają pierwszeństwo w dostępie do procesora, przed procesami o
priorytecie niższym. Procesom o równych priorytetach przydziela się procesor zgodnie
z algorytmem FCFS.

Priorytety definiuje się wewnętrznie lub
zewnętrznie

 Wewnętrzna definicja priorytetu opiera się na własnościach procesu, np.: stosunek

średniej fazy we/wy do średniej fazy procesora, wielkość obszaru wymaganej pamięci,
liczba otwartych plików, itp. Do określenia priorytetów zewnętrznych używa się
kryteriów spoza wnętrza systemu, np.: kwota opłat za użytkowanie komputera,
znaczenie procesu dla użytkownika, itp.



Wewnętrzna definicja priorytetu opiera się na własnościach procesu, np.: stosunek
średniej fazy we/wy do średniej fazy procesora, wielkość obszaru wymaganej pamięci,
liczba otwartych plików, itp. Do określenia priorytetów zewnętrznych używa się
kryteriów spoza wnętrza systemu, np.: kwota opłat za użytkowanie komputera,
znaczenie procesu dla użytkownika, itp.

Problem związany z planowaniem priorytetowym
to nieskończone blokowanie (ang. indefinite blocking),
nazywane głodzeniem (ang. starvation).

 Problem wiąże się z odkładaniem możliwości obsługi przez procesor tych procesów,

które mają niski priorytet. W sytuacji, w której system jest bardzo obciążony, może
zdarzyć się, że proces o niskim priorytecie będzie czekał w kolejce procesów gotowych
w nieskończoność. Powoduje to duże opóźnienia wykonania procesu o niskim
priorytecie, a może doprowadzić do niewykonania tego procesu.

 Problem ten jest rozwiązywany poprzez postarzanie (ang. aging) procesów o niskich

priorytetach. Postarzanie procesów o niskim priorytecie, które długo oczekują na
obsługę procesora odbywa się co pewien okres czasu. W ten sposób, z procesu o
niskim priorytecie, tworzy się proces o wysokim priorytecie, który na pewno zostanie
obsłużony w pierwszej kolejności.



Problem wiąże się z odkładaniem możliwości obsługi przez procesor tych procesów,
które mają niski priorytet. W sytuacji, w której system jest bardzo obciążony, może
zdarzyć się, że proces o niskim priorytecie będzie czekał w kolejce procesów gotowych
w nieskończoność. Powoduje to duże opóźnienia wykonania procesu o niskim
priorytecie, a może doprowadzić do niewykonania tego procesu.



Problem ten jest rozwiązywany poprzez postarzanie (ang. aging) procesów o niskich
priorytetach. Postarzanie procesów o niskim priorytecie, które długo oczekują na
obsługę procesora odbywa się co pewien okres czasu. W ten sposób, z procesu o
niskim priorytecie, tworzy się proces o wysokim priorytecie, który na pewno zostanie
obsłużony w pierwszej kolejności.