plik

Systemy operacyjne

– notatki do wykładu

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



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:

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

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).

Nie ma wywłaszczania z zasobów.

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

 Z

: krawędź zamówienia

krawędzie Z

 P

: 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



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



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

) )

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.

ałożenia:

– liczba procesów

– 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.

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

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

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

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

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

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

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



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



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.