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