Systemy operacyjne materiaªy ¢wiczeniowe
Studia dzienne PJWSTK
WICZENIA XIII
UWAGA!!! Drugie kolokwium z SOP odb¦dzie si¦ 15 VI 2007 w sali 133 odpo-wiednio w godzinach 8:30-10:00 oraz 10:15-11:45. Po wyniki kolokwium, oceny ko«cowe z przedmiotu oraz wpisy do indeksu zapraszam w poniedziaªek 18 VI 2007 do sali 132 od godziny 12:00 do 14:00. W tym samym czasie bedzie mo»na poprawi¢ jedno z dwóch kolokwiów.
Grafy przydziaªu zasobów
Skªadniki grafu
• proces
• zasób n-elementowy
• zamówienie procesu na dany zasób
• pozyskanie danego zasobu przez proces
Przykªad grafu zasobów
Rozwa»my nast¦puj¡cy graf
Stan systemu:
• proces P 1 oczekuje na zasób Z 1,
• proces P 2 oczekuje na zasób Z 2 oraz zasób Z 4,
• proces P 4 oczekuje na zasób Z 2,
• zasób Z 1 zostaª przydzielony do procesu P 3,
• zasób Z 3 zostaª przydzielony do procesu P 1 oraz procesu P 2,
• zasób Z 4 zostaª przydzielony do procesu P 4.
1
c
° Paweª Rembelski
Systemy operacyjne materiaªy ¢wiczeniowe
Studia dzienne PJWSTK
Problem blokady
• je»eli w danym grae zasobów nie wyst¦puje cykl to w modelowanym systemie nie wyst¦puje blokada procesów
• je»eli w danym grae zasobów wyst¦puje cykl i ka»dy zasób jest co najwy»ej jednoelementowy, to w modelowanym systemie wyst¦puje co najmniej jedna blokada procesów
• je»eli w danym grae zasobów wyst¦puje cykl i istnieje co najmniej jeden zasób skªadaj¡cy si¦
z wi¦cej ni» jednego elementu, to w modelowanym systemie mo»e (ale nie musi) wyst¦powa¢ co najmniej jedna blokada procesów
Zadanie
Podaj przykªad grafu dla systemu skªadaj¡cego si¦ zasobów wi¦cej ni» jednoelementowych, gdzie wyst¦-
puje co najmniej jedna blokada procesów.
Zadanie
Podaj przykªad grafu, zawieraj¡cego co najmniej jeden cykl, dla systemu skªadaj¡cego zasobów wi¦cej ni» jednoelementowych, gdzie nie wyst¦puje »adna blokada procesów.
Unikanie blokady algorytm bankiera
Wprowadzenie
• w systemie znajduje si¦ n procesów P 1 , P 2 , . . . , Pn oraz m zasobów Z 1 , Z 2 , . . . , Zm
• wektor D dªugo±ci m okre±la liczb¦ aktualnie dost¦pnych zasobów ka»dego typu, np. D [ Zi] = j oznacza, »e w systemie znajduje si¦ j wolnych zasobów typu Zi
• macierz X o wymiarze n × m okre±la maksymalne zapotrzebowanie danego procesu na dany zasób, np. X [ Pi, Zj] = k oznacza, »e proces Pi wymaga co najwy»ej k zasób typu Zj
• macierz Y o wymiarze n × m okre±la aktualn¡ liczb¦ zasobów danego rodzaju przydzielonych do danego procesu, np. Y [ Pi, Zj] = k oznacza, »e aktualnie proces Pi u»ywa dokªadnie k zasobów typu Zj
• macierz V o wymiarze n×m okre±la liczb¦ zasobów danego rodzaju na jakie zgªasza zapotrzebowanie dany proces, np. V [ Pi, Zj] = k oznacza, »e proces Pi zgªasza zapotrzebowanie na dokªadnie k zasobów typu Zj
• X [ Pi] ≤ X [ Pj] oznacza, »e ∀k ∈ { 1 , 2 , . . . , m} : X [ Pi, Zk] ≤ X [ Pj, Zk], je»eli X [ Pi] ≤ X [ Pj] i X [ Pi] 6= X [ Pj], to X [ Pi] < X [ Pj] (analogicznie dla przypadku Y [ Pi] ≤ Y [ Pj], V [ Pi] ≤ V [ Pj]),
[
]
[
]
np.
4
5
3
2
1
8
≤ 5 9 3 3 7 9
Denicja stanu bezpiecznego
System znajduje si¦ w stanie bezpiecznym wtedy i tylko wtedy gdy istnieje ci¡g procesów Pi , P , . . . , P
1
i 2
in
tego systemu, taki »e
[
]
[
]
j− 1
∑
• ∀j ∈ { 1 , 2 , . . . , n} : X Pi − Y P
≤ D +
Y [ P ]
j
ij
il
l=1
• np. n = 3, m = 1 oraz
X
Z 1
Y
Z 1
D
Z 1
P 1
10
P 1
5
3
P 2
4
P 2
2
P 3
9
P 3
2
zatem
2
c
° Paweª Rembelski
Systemy operacyjne materiaªy ¢wiczeniowe
Studia dzienne PJWSTK
◦ rozwa»my ci¡g P 1 , P 2 , P 3
∗ dla procesu P 1 zachodzi
X [ P 1] − Y [ P 1] ≤ D
[10] − [5] ≤ [3]
[5]
[3]
∗ ci¡g ten nie gwarantuje tego, »e system znajduje si¦ w stanie bezpiecznym
◦ rozwa»my ci¡g P 2 , P 1 , P 3
∗ dla procesu P 2 zachodzi
X [ P 2] − Y [ P 2] ≤ D
[4] − [2] ≤ [3]
[2]
≤ [3]
∗ dla procesu P 1 zachodzi
X [ P 1] − Y [ P 1] ≤ D + Y [ P 2]
[10] − [5] ≤ [3] + [2]
[5]
≤ [5]
∗ dla procesu P 3 zachodzi
X [ P 3] − Y [ P 3] ≤ D + Y [ P 2] + Y [ P 1]
[9] − [2] ≤ [3] + [2] + [5]
[7]
≤ [10]
∗ system znajduje si¦ w stanie bezpiecznym
Algorytm bankiera
Zakªadamy, »e w pewnym systemie proces Pi zgªasza zamówienie zdeniowane w wektorze V
1. je»eli V [ Pi] ≤ X [ Pi] −Y [ Pi], to wykonaj krok 2, w przeciwnym przypadku zgªo± bª¡d przekroczenia deklarowanej maksymalnej liczby zasobów prze proces Pi
2. je»eli V [ Pi] ≤ D, to wykonaj krok 3, w przeciwny przypadku wymu± na procesie Pi przej±¢ w stan oczekiwania na wi¦ksz¡ liczb¦ zasobów
3. wykonaj nast¦puj¡ce przypisania
• D := D − V [ Pi] ,
• Y [ Pi] := Y [ Pi] + V [ Pi] , Je»eli istnieje ci¡g procesów Pi , P , . . . , P implikuj¡cych stan bezpieczny systemu, to zaakceptuj 1
i 2
in
dokonany przydziaª zasobów, w przeciwnym przypadku przywró¢ stan zasobów z przed kroku 3 i wymu± na procesie Pi przej±cie w stan oczekiwania na wi¦ksz¡ liczb¦ zasobów.
Zadanie
Niech wektor D oraz macierze X, Y maj¡ posta¢
X
Z 1
Z 2
Z 3
Z 4
Z 5
Y
Z 1
Z 2
Z 3
Z 4
Z 5
P 1
5
0
0
2
3
P 1
2
0
0
1
0
D
Z 1
Z 2
Z 3
Z 4
Z 5
P 2
3
2
1
3
0
P 2
3
2
0
2
0
2
1
0
1
0
P 3
0
1
1
0
3
P 3
0
0
1
0
3
P 4
6
0
0
2
4
P 4
3
0
0
0
0
P 5
2
3
0
4
2
P 5
0
0
0
0
2
3
c
° Paweª Rembelski
Systemy operacyjne materiaªy ¢wiczeniowe
Studia dzienne PJWSTK
• czy system znajduje si¦ w stanie bezpiecznym?
[
]
• co si¦ stanie, je»eli proces P 4 zgªosi »¡danie wyra»one wektorem V [ P 4] = 0 0 0 1 2 ?
[
]
• co si¦ stanie, je»eli proces P 1 zgªosi »¡danie wyra»one wektorem V [ P 1] = 1 0 0 0 0 ?
[
]
• co si¦ stanie, je»eli proces P 4 zgªosi »¡danie wyra»one wektorem V [ P 4] = 2 0 0 1 0 ?
Sterowanie gªowic¡ dysku
Budowa dysku
• talerz no±niki danych o przekroju koªowym
• ±cie»ka zbiór sektorów równoodlegªych od ±rodka talerza
• sektor element skªadowy ±cie»ki
• gªowica element odczytuj¡cy zawarto±¢ ±cie»ek
• cylinder zbiór ±cie»ek o równej ±rednicy, znajduj¡cych si¦ na wszystkich talerzach dysku wielota-lerzowego
Efektywno±¢ strategii przydziaªu zasobów dyskowych
• Ω ±rednia liczba jednostkowych przesuni¦¢ gªowicy (zespoªu gªowic) wzgl¦dem liczby zrealizowa-nych zamówie« odczytu danego sektora dysku
Strategia FCFS
• skrót od First Come First Serve
• cylindry dysku wybierane s¡ z puli zgªoszonych zamówie« w kolejno±ci zgªosze«
• strategia FCFS nie mo»e prowadzi¢ do zagªodzenia zgªoszenia Strategia SSTF
• skrót od Shortest Seek Time First
• cylindry dysku wybierane s¡ z puli zgªoszonych zamówie« w kolejno±ci minimalizuj¡cej koszt przesuni¦cia gªowicy
• w przypadku gdy istnieje kilka zgªosze« minimalizuj¡cych koszt przesuni¦cia gªowicy, wybierane jest to które zostaªo zgªoszone najwcze±niej
• strategia SSTF mo»e prowadzi¢ do zagªodzenia zgªoszenia
Strategia Scan
• gªowica dysku w¦druje ruchem wahadªowym mi¦dzy pierwszym a ostatnim cylindrem dysku
• cylindry wybierane s¡ w kolejno±ci wyznaczonej przez ruch wahadªowy gªowicy
• strategia Scan nie mo»e prowadzi¢ do zagªodzenia zgªoszenia Strategia C-Scan
• gªowica dysku w¦druje ruchem póªwahadªowym od pierwszego do ostatniego cylindra dysku
• po osi¡gni¦ciu ostatniego cylindra dysku, gªowica przesuwa si¦ (bez przeszukiwania dysku) do cylindra pierwszego
• cylindry wybierane s¡ w kolejno±ci wyznaczonej przez ruch póªwahadªowy gªowicy
• strategia C-Scan nie mo»e prowadzi¢ do zagªodzenia zgªoszenia 4
c
° Paweª Rembelski
Systemy operacyjne materiaªy ¢wiczeniowe
Studia dzienne PJWSTK
Zadanie
Pewien dysk skªada si¦ ze 100 cylindrów. W chwili t w puli zamówie« rozwa»anego dysku znajduj¡ si¦
sektory z nast¦puj¡cych cylindrów uporz¡dkowane zgodnie z kolejno±ci¡ pojawiania si¦ zamówie«: 20, 100, 10, 70, 40. Zasymuluj dziaªanie strategii FCFS, SSTF, Scan oraz C-Scan przy zaªo»eniu, »e realizacja dowolnego zamówienia poci¡ga za sob¡ wygenerowanie w puli zamówie« dysku nowego »¡dania zgodnie z poni»sz¡ tabel¡:
czas
t + 1
t + 2
t + 3
t + 4
t + 5
»¡dany cylinder
80
90
30
50
60
Dla ka»dej strategii wyznacz wspóªczynnik jej efektywno±ci Ω.
5
c
° Paweª Rembelski