Systemy operacyjne

– notatki do wykładu

12

4. Koordynacja procesów

4.1 Sekcje krytyczne



interpretacja przetwarzania współbieżnego dla pojedynczego CPU: proces rozpoczyna się

przed zakończeniem poprzedniego





możliwy konflikt przy operacjach na danych dzielonych (np. nawet instrukcja x:=x=1 to 3

instrukcje (mov AX,x; inc AX; mov x,AX) procesora...



Wniosek: każdy z procesów ma (może mieć) segment kodu nazywany sekcją krytyczną (SK).

SK procesów podlegają wzajemnemu wykluczaniu się w czasie.



Cechy rozwiązania problemu SK:

-

wzajemne wyłączanie SK

-

ograniczone (skończone) czekanie na wejście do SK

-

postęp: kandydują tylko procesy zgłaszające chęć wejścia do SK



np.(ogólna struktura procesu i przykładowe rozwiązanie):

repeat

while x<>0 do nic

(sekcja wejściowa)

<SK> (SK)

x:=1

(sekcja wyjściowa)

<reszta kodu procesu>
until false

(narzucone naprzemienne (czyli nie spełniające warunku postępu) wykonanie SK

dla 2(może być więcej) procesów)



Poprawne rozwiązanie dla 2 procesów:

var flaga: array[o..1] of Boolean

numer: 0..1

repeat

flaga[i]:=TRUE

(chcę wejść)

numer:=j

(założenie, że drugi chce wejść)

while (flaga[j] AND numer:=j)do nic

<SK>

flaga[i]:=FALSE

<reszta kodu procesu>
until false

(bez zmiennej numer możliwe byłoby ustawienie obu flag przez procesy w

dwóch kolejnych instrukcjach procesora (po pechowym przełączeniu kontekstu) i wieczne ich
zapętlenie...)

4.2 Semafory



Semafor ogólne popularne rozwiązanie problemu SK i synchronizacji



Semafor s to zmienna całkowita dostępna po inicjacji za pomocą tylko 2 operacji:

- czekaj(s):

while s <= 0 do nic; s := s-1;

- sygnalizuj(s):

s := s+1;



Interpretacja s: ilość wolnych zasobów; w tym przypadku zasobem jest SK



Operacje na semaforach są NIEPODZIELNE! Implementacja:

- na pojedynczym CPU

– zablokowanie przerwań na czas operacji

- w systemie wieloprocesorowym instrukcja procesora TEST&SET



Użycie:

s:=1
repeat

czekaj(s)

<SK>

sygnalizuj(s)

<reszta kodu procesu>
until false

Systemy operacyjne

– notatki do wykładu

13



Zastosowanie przy synchronizacji (np. gdy operacja1 musi się wykonać po operacji2):

s:=0
1proces:

op1;

2proces:

czekaj(s);

sygnalizuj(s);

op2;



Wada: s wymaga aktywnego czekania (czas procesora!!!)

-

rozwiązanie: po czekaj(s) proces jest blokowany i umieszczany w kolejce związanej z s

-

pobranie procesu z kolejki następuje po sygnalizuj(s)

-

wtedy semafor to rekord (zmienna całk. + lista procesów)

-

algorytm obsługi kolejki nie ma znaczenia dla procesora



Realizacja niepodzielności:

-

1 procesor: blokada przerwań na czas operacji

-

wiele procesorów: np. pojedyncza instrukcja procesora „test&set”

4.3 Blokady.



Stan blokady: każdy proces w zbiorze procesów czeka na zdarzenie, które może być

spowodowane tylko przez inny procesu z tego samego zbioru (zdarzeniem może być np.
przydział lub zwolnienie zasobu).

np.:
Semafory A i B mają wartość 1:
P0: wait(A); wait(B)
P1: wait(B); wait(A)



Przypadek szczególny: tzw. głodzenie – czekanie w nieskończoność pod semaforem – gdy np.

zastosujemy kolejkę LIFO semafora.



Warunki powstania blokady:

1.

Wzajemne wyłączanie (co najmniej 1 zasób musi być niepodzielny)

2.

Przetrzymywanie i oczekiwanie (proces przetrzymujący co najmniej jeden zasób czeka na
przydział dodatkowych zasobów będących w posiadaniu innych procesów).

3.

Nie ma wywłaszczania z zasobów.

4.

Cykliczne czekanie (istnieje zbiór czekających procesów {P0, P1, Pn }, takich że P 0 czeka na
zasób przetrzymywany przez P1 , P1 czeka na zasób przetrzymywany przez P2 , ..., P n czeka
na zasób przetrzymywany przez P0 .



(4 implikuje 2, więc podane warunki nie są niezależne)



Opis blokady:

-

zbiór procesów P, zasobów Z, „graf przydziału zasobów” – dwudzielny (krawędzie łączą
wierzchołki należące do 2 rozdzielnych zbiorów – w tym przypadku zasobów i procesów) graf
skierowany.

-

krawędzie P

i

 Z

j

: krawędź zamówienia

-

krawędzie Z

j

 P

i

: krawędź przydziału



Rysunek:

-

proces p 

kółko,

-

zasób z  prostokąt

-

1 egzemplarz zasobu z 

kropka w prostokącie.

-

krawędź przydziału zaczyna się od kropki



Zdarzenia w systemie:

-

zamówienie z przez p : dodajemy krawędź p  z

-

realizacja zamówienia : dodajemy krawędź z  p, usuwamy p  z

-

zwolnienie zasobu : usuwamy krawędź

Systemy operacyjne

– notatki do wykładu

14









Blokada:

-

jeżeli w grafie nie ma cyklu: nie ma blokady.

-

jeżeli jest cykl a zasoby są pojedyncze to jest blokada

-

jeżlei jest cykl a zasoby są wielokrotne, to może być blokada



Postępowanie z blokadami:

-

zapewnić że nigdy ich nie będzie (odp. protokół przydziału zasobów)

-

pozwalać na wejście w blokadę i potem ją usuwać

-

zign

orować i założyć, że nie wystąpią (np. UNIX i większość popularnych s.o).

4.4 Zapobieganie i unikanie blokad.



Zapobiec spełnieniu jednego z 4 warunków koniecznych wystąpienia blokady:

-

wzajemne wyłącznie: na ogół niemożliwe; niektóre zasoby są z definicji niepodzielne (drukarka,
plik do pisania...)

-

Przetrzymywanie -

trzeba zagwarantować, że gdy proces żąda zasobu, to nie posiada innych

zasobów: pozwalać na zamówienie tylko gdy zwolni wszystkie posiadane (problem: głodzenie i
nieefektywne wykorzystanie zas

obów).

-

Można wymagać, by proces zamawiał i dostawał wszystkie swoje zasoby zanim rozpocznie
działanie lub żądał zasobów wtedy, gdy nie posiada żadnych innych - niskie wykorzystanie
zasobów, możliwość zagłodzenia

-

Brak wywłaszczeń: jeśli proces będący w posiadaniu zasobów żąda zasobu, którego nie
można natychmiast przydzielić, to musi zwolnić wszystkie posiadane zasoby - Wywłaszczone
zasoby dodaje się do listy zasobów, na które czeka proces

-

Cykliczne czekanie: narzuca się uporządkowanie całkowite wszystkich typów zasobów i
wymaga, by proces zamawiał zasoby we wzrastającym porządku ich numerów (metoda
wyklucza powstawanie cykli)



powyższe metody zawsze ograniczają przepustowość systemu...



Unikanie blokad:

-

Wymaga, by system posiadał pewną informację o przyszłym zapotrzebowaniu na zasoby

-

W najprostszym modelu wymaga się, by proces deklarował maksymalną liczbę zasobów
każdego typu, których będzie potrzebował

-

Algorytm unikania blokady dynamicznie bada stan przydziału zasobów, by zapewnić, że nigdy
nie dojdzie do cyklicznego oczekiwania

-

Stan systemu jest określony przez liczbę dostępnych i przydzielonych zasobów oraz przez
maksymalne zapotrzebowanie procesów.

Systemy operacyjne

– notatki do wykładu

15



Stan bezpieczny -

kiedy proces żąda dostępnego zasobu, system musi ustalić, czy

natychmiastowy przydz

iał zasobu zachowa bezpieczny stan systemu



System jest w stanie bezpiecznym, gdy istnieje bezpieczna sekwencja <P1 , P2 , ..., Pn > :

bezpieczna, jeśli dla każdego P i jego potencjalne zapotrzebowanie na zasoby można
zaspokoić przez bieżąco dostępne zasoby oraz zasoby będące w posiadaniu procesów Pk ,
gdzie k < i.

-

Jeśli system jest w stanie bezpiecznym to nie ma blokady

-

Jeśli system nie jest w stanie bezpiecznym to istnieje możliwość blokady. Można unikać
blokady zapewniając, że system nigdy wejdzie do stanu niebezpiecznego.



Algorytm unikania korzystający z grafu przydziału zasobów: (dla zasobów pojedynczych):

-

wprowadzamy krawędzie deklaracji (zapotrzebowania) – rysowane linią przerywaną)

-

szukamy pętli w grafie (złożoność O(n

2

) )

-

jeśli jest pętla – nie przydzielamy zasobu.



Algorytm unikania (dla zasobów wielokrotnych – tzw. alg. bankiera. Por. A Silbershatz i.in.

Podstawy syst. operacyjnych rozdz. 6.4.1 str. 208.):

-

Każdy proces musi a priori złożyć maskymalne zapotrzebowanie na zasoby

-

Proces żądający zasobu być może będzie musiał czekać, mimo że zasób jest dostępny..

-

Gdy proces dostanie wszystkie potrzebne zasoby, to zwróci je w skończonym czasie

-

Po zamówieniu przez proces zasobów system ustala czy ich przydzielenie prowadzi do stanu
bezpiecznego.

Z

ałożenia:

n

– liczba procesów

m

– liczba typów zasobów

int Dostępne[m] – liczba zasobów określonego typu (np. Dostępne[3]=5 to 5 zasobów typu 3)
int Maks[n][m]

– maksymalne żądania procesów

int Przydzielone[n][m]

– przydzielone zasoby

int Potrzebne[n][m]

– potrzebne zasoby (z tym, że Potrzebne[i][j]=Maks[i][j]-Przydzielone[i][j])

int Zamówienia[n][m] – aktualne zamówienia procesu.
Algorytm:
1.

Jeśli Zamówienia[i] <= Potrzebne[i] to wykonaj krok 2. Wpp błąd – proces przekroczył
deklarowane zapotrzebowanie.

2.

Jeśli Zamówienia[i] <= Dostępne wykonaj krok 3. Wpp proces i musi czekać.

3.

System próbuje przydzielić żądane zasoby procesowi i zmieniając stan systemu w następujący
sposób:

Dostępne = Dostępne – Zamówienia[i]

Przydzielone[i] = Przydzielone[i] + Zamówienia[i]

Potrzebne[i] = Potrzebne[i]

– Zamówienia[i]



Jeśli stan po zmianie jest bezpieczny, transakcja dochodzi do skutku. Jeśli nie – proces i

musi czekać...

Algorytm bezpieczeństwa:
1. int Praca[m]; int Koniec[n]
2.

Praca = Dostępne; Koniec[i] = FALSE dla wszystkich i

3.

Znajdujemy i takie że Koniec[i]=FALSE oraz Potrzebne[i] <= Praca; Jeśli nie ma takiego i  do
kroku 5.

4.

Praca = Praca + Przydzielone[i]; Koniec[i] = TRUE; przejdź do kroku 2.

5.

Jeśli Koniec[i] = TRUE dla wszystkich i, to system jest w stanie bezpiecznym...

 Koszt stwierdzenia czy system jest bezp. = m x n

2

4.5 Wykrywanie i wychodzenie z blokady.



W systemach bez zapobiegania i unikania musi być:

-

alg. wykrywania blokady (najczęściej: poszukiwanie cykli w grafie)

-

alg. wychodzenia z blokady

Systemy operacyjne

– notatki do wykładu

16



Kiedy wywoływać algorytm wykrywania blokady:

-

gdy nie można natychmiast przydzielić zasobu

-

raz na ustalony czas (np. 10 min)

-

gdy obciążenie procesora spada poniżej ~40% (blokada dławi przepustowość systemu)



Wychodzenie z blokady (sposoby):

-

Powiadomienie operatora (ro

związuje problem ręcznie)

-

Usunięcie procesu(ów) uczestniczących w blokadzie



całej pętli (znaczny koszt, utrata częściowych wyników)



kolejno (wywołanie szukania cykli po każdym usunięciu)

-

różne kryteria wyboru ofiary (priorytet, typ, posiadane zasoby...)

-

Wywłaszczanie z zasobów (potrzebna gwarancja że nie będzie głodzenia – np. wywłaszczenie
możliwe max. k razy)



Ogólnie (bsługa blokad):

-

zapobieganie, unikanie, wykrywanie, usuwania



We współczesnych systemach: - podział zasobów na klasy:

-

do klas stosujemy zapobieganie cyklom

-

w obrębie klas:

-

zasoby wewnętrzne (bloki kontr. itp...)  uporządkowanie zasobów

-

pamięć głowna 

-

urządzenie i pliki  unikanie blokad

5. Zarządzanie pamięcią

5.1 Założenia wstępne:
-

pamięć mieści cały program (o wyjątkach poniżej)

-

pamięć to tablica poadresowanych słów

-

współpraca z pamięcią polega na pisaniu/czytaniu z/pod adres

-

procesy pobierane są do pamięci z kolejki zadań.

Różne mechanizmy:



Wiązanie:

-

proces może rezydować w dowolnej częsci pamięci; musi istnieć mechanizm wiązania
rozkazów i danych z adresami fizycznymi.

-

wiązanie może nastąpić w czasie:

- kompilacji

(przy założeniu że proces rozpoczyna się od adresu X – np. pliki *.com w dos)

-

ładowania (po przemieszczeniu kodu trzeba przeładować)

- wykonania

(możliwe przemieszczenia)



Ładowanie dynamiczne: podprogramy są na dysku w formie przemieszczalnej i są ładowane

po wywołaniu przez pr. główny. zaleta: nie ładujemy nieużywanego kodu.



Łączenie dynamiczne (bez niego wszystkie programy musza mieć swoje kopie bibliotek

systemowych (np. DLL). W miejscach odwołań znajdują się zakładki (małe fr. kodu, po
wywołaniu podające adres procedury bibliotecznej)



Nakładki (np. *.ovl) – w pamięci jest tylko niezbędny kod, nakładki się wyłączają (na ogół), są

przechowywane

na dysku w postaci bezwzględnego obrazu pamięci.



ponieważ procesy wykonują się wyłącznie w pamięci, nie zawsze wszystkie się mieszczą. Więc:

5.2 Wymiana.



Proces może zostać czasowo wysłany z pamięci głównej do zewnętrznej, a po jakimś czasie

sprowadzony

ponownie do pamięci głównej

Systemy operacyjne

– notatki do wykładu

17



Program wraca w to samo miejsce, chyba że mamy do czynienia z wiązaniem w czasie

wykonania.



Jako pamięć zewnętrzna na potrzeby wymiany służy duży szybki dysk z dostępem

bezpośrednim



Główny narzut: czas transmisji; dla dobrej wydajności czas wykonania musi być długi w

porównaniu z czasem przełączania.



System musi wiedzieć o zapotrzebowaniu na pamięć by pracować efektywnie, przydziału

dokonują funkcje systemowe.



W czasie wymiany nie mogą występować operacje we/wy (operujące na buforach pamięci) 

nie wymienia się procesów we/wy a buforami opiekuje się system.