dr inż. Grażyna KRUPIC
SKA
[e-mail]
D-10 pokój 227
WYKA
AD 6
WST
P DO INFORMATYKI
Systemy operacyjne
2
System operacyjny jest zbiorem ręcznych
i automatycznych procedur, które pozwalają
grupie osób na efektywne współdzielenie
urządzeń maszyny cyfrowej
Per Brinch Hansen
Systemy operacyjne
3
System operacyjny (nadzorczy, nadrzędny, sterujący)
jest to zorganizowany zespół programów, które
pośredniczą między sprzętem a użytkownikami,
dostarczając użytkownikom zestawu środków
ułatwiających projektowanie, kodowanie,
uruchamianie i eksploatację programów oraz w tym
samym czasie sterują przydziałem zasobów dla
zapewnienia efektywnego działania.
Alen Shaw
Systemy operacyjne
4
System operacyjny jest programem, który działa
jako pośrednik między użytkownikiem komputera
a sprzętem komputerowym.
Zadaniem systemu operacyjnego jest tworzenie
środowiska, w którym użytkownik może
wykonywać programy w sposób wygodny
i wydajny.
Abraham Silberschatz
Systemy operacyjne
5
System operacyjny jest warstwÄ… oprogramowania
operującą bezpośrednio na sprzęcie, której celem
jest zarzÄ…dzanie zasobami systemu
komputerowego i stworzenie użytkownikowi
środowiska łatwiejszego do zrozumienia
i wykorzystania.
Andrew Tanenbaum
Systemy operacyjne
6
Użytkownik Użytkownik Użytkownik Użytkownik
&
1 2 3 n
Edytor
Baza
Asembler
Kompilator
tekstu
danych
Programy systemowe i użytkowe
SYSTEM OPERACYJNY
Sprzęt komputerowy
Zadania systemu
operacyjnego
7
Definicja interfejsu użytkownika
Udostępnianie systemu plików
Udostępnianie środowiska do wykonywania
programów użytkownika
żð mechanizm Å‚adowania i uruchamiania programów
żð mechanizmy synchronizacji i komunikacji
procesów
Sterowanie urządzeniami wejścia-wyjścia
Obsługa podstawowej klasy błędów
ZarzÄ…dzanie zasobami
Zasoby zarzÄ…dzane przez
system operacyjny
8
Procesor  przydział czasu procesora
Pamięć
żð alokacja przestrzeni adresowej dla procesów
żð transformacja adresów
Urządzenia zewnętrzne
żð udostÄ™pnianie i sterowanie urzÄ…dzeniami pamiÄ™ci masowej
żð alokacja przestrzeni dyskowej
żð udostÄ™pnianie i sterownie drukarkami, skanerami itp.
Informacja (system plików)
żð organizacja i udostÄ™pnianie informacji
żð ochrona i autoryzacja dostÄ™pu do informacji
Klasyfikacja SO ze względu
na sposób przetwarzania
9
Systemy przetwarzania bezpośredniego (ang. on-line processing
systems)  systemy interakcyjne
żð wystÄ™puje bezpoÅ›rednia interakcja pomiÄ™dzy użytkownikiem
a systemem,
żð wykonywanie zadania użytkownika rozpoczyna siÄ™ zaraz po
przedłożeniu.
Systemy przetwarzania pośredniego (ang. off-line processing
systems)  systemy wsadowe
żð wystÄ™puje znaczÄ…ca zwÅ‚oka czasowa miÄ™dzy przedÅ‚ożeniem
a rozpoczęciem wykonywania zadania,
żð niemożliwa jest ingerencja użytkownika w wykonywanie zadania
żð operator Å‚Ä…czyÅ‚ zadania o podobnych wymaganiach w tzw.
wsady (ang. batch).
żð system operacyjny byÅ‚ bardzo prosty, wczytywanie kolejnych
zadań i uruchomienie ich.
Spooling
10
Spooling  (ang. simultaneous peripherial operation on-line).
żð nowe zadania sÄ… wczytywane przez czytnik(i) kart
i zapisywane na dysku
żð procesor pobiera kolejne zadania z dysku, wykonuje je
i zapisuje wyniki na dysku
żð wyniki zakoÅ„czonych zadaÅ„ sÄ… drukowane
żð nowe zadanie systemu operacyjnego - synchronizacja
wczytywania zadań, wypisywania wyników oraz
zarzÄ…dzanie informacjami magazynowanymi na dysku.
Klasyfikacja SO ze względu
na liczbę wyk. programów
11
Systemy jednozadaniowe  niedopuszczalne jest
rozpoczęcie wykonywania następnego zadania
użytkownika przed zakończeniem poprzedniego.
Systemy wielozadaniowe  dopuszczalne jest istnienie
jednocześnie wielu zadań (procesów), którym zgodnie
z pewnÄ… strategiÄ… przydzielany jest procesor. Zwolnienie
procesora następuje w wyniku
żð żądania przydziaÅ‚u dodatkowego zasobu,
żð zainicjowaniu operacji wejÅ›cia-wyjÅ›cia,
żð przekroczenia ustalonego limitu czasu (kwantu czasu)
Systemy wielozadaniowe
12
Nowe zadania systemu operacyjnego
żð zarzÄ…dzanie pamiÄ™ciÄ… i pilnowanie, aby jeden proces nie
ingerował w obszar pamięci przydzielonej innym
procesom,
żð przydzielanie urzÄ…dzeÅ„ zewnÄ™trznych procesom,
żð jeÅ›li procesor jest bezczynny, to należy wybrać jeden
z procesów, które znajdują się w pamięci i są gotowe
do wykonania; jest to tzw. szeregowanie
krótkoterminowe,
żð jeÅ›li zwalnia siÄ™ pamięć operacyjna i można wczytać
z dysku kolejne zadanie oczekujÄ…ce na wykonanie, to
należy wybrać jedno z oczekujących zadań; jest to
tzw. szeregowanie długoterminowe.
Klasyfikacja SO ze względu
na liczbę użytkowników
13
Systemy dla jednego użytkownika  zasoby
przeznaczone są dla jednego użytkownika (komputery
osobiste), nie ma mechanizmów autoryzacji dostępu,
a mechanizmy ochrony informacji sÄ… ograniczone.
Systemy wielodostępne  wielu użytkowników
może korzystać z zasobów systemu komputerowego,
a system operacyjny gwarantuje ich ochronÄ™ przed
niepowołaną ingerencją.
Systemy z podziałem czasu
14
Nowe zadania systemu operacyjnego
żð pozwoliÅ‚ na interaktywnÄ… pracÄ™ wielu użytkowników
z komputerem - czytniki kart perforowanych zostały
zastąpione terminalami, przy których mogli pracować
użytkownicy.
żð system plików  indywidualizacja zasobów dyskowych
Inne rodzaje
systemów operacyjnych
15
Systemy czasu rzeczywistego (ang. real-time systems) 
zorientowane na przetwarzanie z uwzględnieniem czasu
zakończenie zadania, tzw. linii krytycznej (ang. deadline).
Systemy sieciowe i rozproszone (ang. network and
distributed systems)  umożliwiają zarządzanie zbiorem
rozproszonych jednostek przetwarzających, które są
zintegrowane siecią komputerową i nie współdzielą
fizycznie zasobów.
żð niezawodność
żð współdzielenie zasobów
żð zwiÄ™kszenie mocy obliczeniowej
żð nowe usÅ‚ugi
Struktura systemu
operacyjnego
16
W typowym systemie operacyjnym wyróżniamy
następujące podsystemy:
żð podsystem zarzÄ…dzania procesami
" tworzenie i usuwanie procesów
" szeregowanie, wstrzymywanie i wznawianie procesów
" mechanizmy synchronizacji i komunikacji między
procesami, oraz obsługi zakleszczeń
Struktura systemu
operacyjnego
17
W typowym systemie operacyjnym wyróżniamy
następujące podsystemy:
żð podsystem zarzÄ…dzania procesami
żð podsystem zarzÄ…dzania pamiÄ™ciÄ…
żð podsystem systemu plików
żð podsystem wejÅ›cia/wyjÅ›cia
żð podsystem pamiÄ™ci pomocniczej
żð podsystem usÅ‚ug sieciowych
żð podsystem ochrony
żð interpreter poleceÅ„ i programy użytkowe
Usługi systemu operacyjnego
18
System operacyjny tworzy środowisko udostępniające
pewne usługi użytkownikom oraz ich programom:
żð operacje wejÅ›cia/wyjÅ›cia
żð operacje na systemie plików
żð przydzielanie zasobów
żð komunikacja
żð ochrona
żð wykrywanie bÅ‚Ä™dów
żð rozliczenia
Funkcje systemowe
19
Programy użytkowników mają dostęp do usług systemu
operacyjnego poprzez tzw. funkcje systemowe.
żð operacje na procesach - tworzenie nowych procesów, przerwanie,
zawieszanie, wznawianie działania procesu, pobranie informacji o procesie,
oczekiwanie na określone zdarzenie, przydzielanie i zwalnianie pamięci.
żð operacje na plikach - utworzenie pliku, usuniÄ™cie pliku, otwarcie pliku,
odczyt z pliku, zapis do pliku, pobranie lub zmiana atrybutów pliku.
żð operacje na urzÄ…dzeniach - zamówienie i zwolnienie urzÄ…dzenia,
odczyt z i zapis do urządzenia, pobranie lub zmiana atrybutów urządzenia,
(logiczne) przyłączenie lub odłączenie urządzenia.
żð informacje systemowe - pobieranie i/lub ustawianie najrozmaitszych
informacji systemowych, w tym: czasu i daty, wersji systemu operacyjnego,
atrybutów użytkowników.
żð komunikacja - przekazywanie informacji miÄ™dzy procesami.
Struktura systemu Unix
20
Użytkownicy
Planowanie
Powłoki i polecenia
przydziału procesora
Kompilatory i interpretery
Zastępowanie stron
Biblioteki systemowe
Stronicowanie
na żądanie
Interfejs funkcji systemowych jÄ…dra
Pamięć wirtualna
Planowanie
Sygnały
System plików
przydziału procesora
Obsługa terminali
Wymiana
Zastępowanie stron
System znakowego I/O
System blokowego I/O
Stronicowanie
Moduły sterujące
Moduły sterujące
na żądanie
terminali
dysków i taśm
Pamięć wirtualna
Interfejs między jadrem a sprzętem
Sterowniki terminali Sterowniki urządzeń Sterowniki pamięci
Terminale Dyski i taśmy Pamięć operacyjna
(kernel)
JÄ…dro systemu
Koncepcja procesu
21
Proces (nazywany też czasem zadaniem) to wykonujący się
program. Każdy proces ma własny licznik instrukcji, który wskazuje
następną instrukcję do wykonania, oraz własny obszar przydzielonej
mu pamięci operacyjnej.
Proces jest elementarną jednostką pracy (aktywności) zarządzaną
przez system operacyjny, która ubiega się o zasoby systemu
komputerowego w celu wykonania programu.
Procesem jest cały ten kontekst niezbędny do wykonania programu.
żð program  definiuje zachowanie procesu,
żð dane  zbiór wartoÅ›ci przetwarzanych oraz wyniki,
żð zbiór zasobów tworzÄ…cych Å›rodowisko wykonawcze,
żð blok kontrolny procesu (PCB, deskryptor)  opis bieżącego stanu procesu.
Koncepcja zasobu
22
Zasobem jest element sprzętowy lub programowy systemu
komputerowego, którego brak może potencjalnie zablokować
wykonywanie programu
Zasoby takie często określa się jako wirtualne, np. plik. Pliki
udostępnia system operacyjny. Na poziomie maszynowym
pojęcie takie nie istnieje  można co najwyżej mówić o
sektorach dysku, w których składowana są dane.
Koncepcja zasobu
23
Pamięć operacyjna zwykle jest podzielona na cztery
części (nazywane segmentami):
żð segment kodu -- zawiera instrukcje wykonywanego
programu,
żð segment danych -- zawiera zmienne globalne programu,
żð stos -- jest używany do wywoÅ‚ywania procedur,
przekazywania parametrów i wyników, oraz
przechowywania zmiennych lokalnych,
żð sterta -- z tego obszaru przydzielana jest pamięć dla
zmiennych dynamicznych.
Procesy i zasoby
24
Ze względów pojęciowych lub projektowych fragmenty kodu
jądra związane z obsługą procesów i zasobów wyodrębnia się
w postaci zarządców.
Zarządca procesów (ang. process manager) 
kontroluje stany procesów w celu efektywnego i bezpiecznego
wykorzystania współdzielonych zasobów systemu.
Zarządca zasobów (ang. resource manager) 
realizuje przydział zasobów stosownie do żądań procesów,
aktualnego stanu systemu oraz ogólnosystemowej polityki
przydziału.
Stany procesu
25
żð nowy - wÅ‚aÅ›nie utworzono.
żð aktywny- jest wÅ‚aÅ›nie wykonywany przez procesor.
żð czekajÄ…cy - czeka na zajÅ›cie jakiegoÅ› zdarzenia
żð gotowy - czeka na przydzielenie mu procesora.
żð zakoÅ„czony - zakoÅ„czyÅ‚ dziaÅ‚anie.
Diagram przejść stanu
procesów
26
zakończony
nowy
przyjęcie
przerwanie
wyjście
gotowy
aktywny
decyzja planisty
obsłużenie zdarzenia
lub operacji I/O
oczekiwanie na zdarzenie lub
czekajÄ…cy
na wykonanie operacji I/O
Process control block - PCB
27
Informacje związane z każdym procesem :
żð Stan procesu
żð Licznik rozkazów
żð Rejestry procesora
żð Informacje o planowaniu przydziaÅ‚u procesora
żð Informacje o zarzÄ…dzaniu pamiÄ™ciÄ…
żð Informacje do rozliczeÅ„
żð Informacje o stanie wejÅ›cia-wyjÅ›cia
Planowanie procesów
28
Planowanie procesów polega na wskazywaniu procesu,
któremu ma być w danej chwili przydzielony procesor
(gotowy ®ð aktywny)
W systemie w każdej chwili może być aktywnych co tyle
procesów, ile jest procesorów.
Procesy nieaktywne czekają na przydział procesora
w kolejkach.
żð Kolejka zadaÅ„ - wszystkie procesy w systemie
żð Kolejka gotowych - gotowe do wykonania
żð Kolejka do urzÄ…dzenia - dla każdego urzÄ…dzenia wejÅ›cia-
wyjścia odrębna taka kolejka
Planowanie
29
Kolejka procesów
CPU
gotowych
Kolejka operacji Zamówienie
I/O
I/O operacji I/O
Zużycie kwantu
czasu
Powołanie
Proces
procesu
potomny
potomnego
Czekanie na
WystÄ…pienie
przerwanie
przerwania
Planista
30
Selekcji procesu, który ma przejść do stanu aktywny, dokonuje
odpowiedni proces systemowy planista (ang. scheduler). Możemy
wyróżnić dwa rodzaje planistów:
żð Planista dÅ‚ugoterminowy (albo planista zadaÅ„) decyduje o tym,
który z procesów ma być załadowany do pamięci i gotowy do
wykonania. Kontroluje on poziom wieloprogramowości, czyli
liczbę współbieżnie wykonywanych procesów.
żð Planista krótkoterminowy (albo planista procesora) decyduje o
tym, który z procesów gotowych ma być wykonywany na
procesorze. Swoje działania podejmuje stosunkowo często
(np. co 10-100 milisekund), żeby użytkownik miał wrażenie
płynnej współbieżności wszystkich działających procesów. Jest to
szczególnie ważne w systemach interakcyjnych z podziałem
czasu.
Planista
31
Decyzje planisty sÄ… podejmowane jedynie :
żð przejÅ›cie procesu aktywnego do stanu oczekiwania,
żð zakoÅ„czenie procesu,
to planowanie nazywamy niewywłaszczeniowym
Jeżeli decyzje planisty ć podejmowane są także:
żð przejÅ›cie procesu ze stanu oczekiwania do stanu gotowoÅ›ci,
żð przejÅ›cie procesu aktywnego do stanu gotowoÅ›ci.
to planowanie nazywamy wywłaszczeniowym
Kryteria jakości planowania
32
Możliwe kryteria oceny strategii planowania :
żð Wykorzystanie procesora
żð Przepustowość
żð Czas oczekiwania
żð Czas obrotu
żð Czas reakcji
Synchronizacja procesów
33
Przyczyny, dla których konieczna jest synchronizacja
współpracujących procesów:
żð Procesy współdzielÄ… pewnÄ… strukturÄ™ danych 
problem sekcji krytycznej.
żð Wyniki dziaÅ‚ania jednego procesu stanowiÄ… dane
dla innego procesu - problem producenta-
konsumenta.
żð Procesy korzystajÄ… z pewnej wspólnej puli zasobów
- problem pięciu filozofów.
Synchronizacja procesów za
pomocą wspólnych zmiennych
34
Problem producenta-konsumenta
żð Mamy dane dwa procesy: producenta i konsumenta.
żð Oba procesy dziaÅ‚ajÄ… w nieskoÅ„czonej pÄ™tli.
żð Producent wytwarza jednostki jakiegoÅ› produktu, a konsument
konsumuje je.
żð Jednostki wyprodukowane, ale jeszcze nie skonsumowane sÄ…
umieszczane w buforze.
żð Bufor może pomieÅ›cić maksymalnie n jednostek produktu.
żð Jeżeli bufor jest pusty, to konsument musi zaczekać, aż producent
wyprodukuje kolejnÄ… jednostkÄ™ produktu.
żð Jeżeli bufor jest peÅ‚ny, to producent musi zaczekać, aż konsument
pobierze jednostkÄ™ produktu z bufora.
Przykład :
buforowanie znaków naciskanych na klawiaturze
wysyłanie wydruków na drukarkę
Problem producenta-
konsumenta
35
PRODUCENT KONSUMENT
repeat
repeat
wyprodukuj jednostkÄ™ produktu;
pobierz z bufora jednostkÄ™ produktu;
wstaw wyprodukowanÄ… jednostkÄ™ do
skonsumuj pobranÄ… jednostkÄ™
bufora
until false
until false
var
bufor: array [0..n-1] of produkt;
BUFOR
pierwszy: 0..n-1;
licznik: 0..n;
Problem producenta-
konsumenta
36
repeat
wyprodukuj jednostkÄ™ produktu;
while licznik = n do
bufor [(pierwszy+licznik) mod n] := wyprodukowana jednostka;
licznik := licznik + 1
rejestr1 := licznik;
until false
rejestr1 := rejestr1 + 1;
licznik := rejestr1;
rejestr1 := licznik;
rejestr2 := licznik;
rejestr2 := rejestr2 - 1;
repeat
licznik := rejestr2;
while licznik = 0 do
rejestr1 := rejestr1 + 1;
pobrana jednostka := bufor [pierwszy];
licznik := rejestr1 ;
pierwszy := (pierwszy + 1) mod n;
rejestr2 := licznik;
licznik := licznik - 1;
rejestr2 := rejestr2 - 1;
skonsumuj pobranÄ… jednostkÄ™
licznik := rejestr2;
until false
Problem producenta-
konsumenta
37
żð RozwiÄ…zaniem problemu jest "zatomizowanie"
operacji pobierania i wkładania jednostek produktu
z i do bufora.
żð Należy zapewnić, aby w trakcie gdy jeden proces
zmienia zawartość bufora drugi nie mógł robić tego
równocześnie.
żð Operacje wkÅ‚adania i wyjmowania z bufora powinny
tworzyć tzw. sekcję krytyczną.
Problem sekcji krytycznej
38
żð Sekcja krytyczna, to fragment(y) kodu lub operacje, które
nie mogą być wykonywane współbieżnie.
żð Sekcja krytyczna jest otoczona dodatkowym kodem
synchronizującym przebywanie procesów wejściowych --
przed wejściem do sekcji krytycznej każdy proces musi
przejść przez sekcję wejściową, a wychodząc przechodzi
przez sekcję wyjściową.
żð Wzajemne wykluczanie: tylko jeden proces na raz może
przebywać w sekcji krytycznej.
Problem sekcji krytycznej
39
RozwiÄ…zanie problemu sekcji krytycznej polega na
podaniu implementacji sekcji wejściowej i wyjściowej.
żð algorytmy z aktywnym oczekiwaniem
" zmienna wejścia/wyjścia
" algorytm Dekkera
" algorytm piekarniany
żð mechanizmy synchronizacji
" Semafory
" Kolejki komunikatów
" Monitory
żð SprzÄ™towe mechanizmy synchronizacji
Zakleszczanie
40
Zakleszczenie to zbiór procesów będących w impasie
wywołanym przez to, że każdy proces należący do tego
zbioru przetrzymuje zasoby potrzebne innym procesom
z tego zbioru, a jednocześnie czeka na zasoby
przydzielone innym procesom.
Zakleszczanie
(Warunki Cofmanna)
41
Wzajemne wykluczanie
żð W jednej chwili z jednego zasobu może korzystać co najwyżej jeden
proces.
Przetrzymywanie i oczekiwanie
żð Proces przetrzymujÄ…cy co najmniej jeden zasób czeka na przydziaÅ‚
dodatkowych zasobów, które są przydzielone innym procesom.
Brak wywłaszczania
żð Procesy zwalniajÄ… zasoby dobrowolnie po zakoÅ„czeniu swojego
zadania. Nie można odebrać procesowi przydzielonego zasobu,
którego ten nie ma ochoty zwolnić.
Czekanie cykliczne
żð Istnieje zbiór czekajÄ…cych procesów {P(1), P(2), ..., P(n)}, takich, że:
" proces P(i-1) czeka na zasób przydzielony procesowi P(i),
" proces P(n) czeka na zasób przydzielony procesowi P(1).
Graf przydziału zasobów
42
Graf przydziału zasobów jest skierowany.
Wierzchołkami tego grafu są procesy działające w
systemie P(1), P(2), ..., P(n) oraz zasoby systemowe Z(1),
Z(2), ..., Z(m).
Krawędz
żądania od procesu P(i) do zasobu Z(j) oznacza,
że proces P(i) zażądał przydzielenia zasobu Z(j).
Krawędz
przypisania od zasobu Z(j) do procesu P(i)
oznacza, że zasób Z(j) jest przydzielony procesowi P(i).
Graf przydziału zasobów
43
Proces P(i) Pi
Zasób Z(j) (4  egzemplarzowy)
Proces P(i) może żądać jednego zasobu Z(j)
Pi
Zj
Zasób Z(j) jest przydzielony procesowi P(i))
Pi
Zj
Proces P(i) żąda jednego zasobu Z(j)
i na niego czeka
Pi
Zj
Graf przydziału zasobów
44
P(2) P(2)
Z(1) Z(1)
P(1) P(1)
Z(2) Z(2)
Metody obsługi zakleszczeń
45
Zapobieganie zakleszczeniom
żð Polega na zaprzeczeniu co najmniej jednemu z czterech
warunków koniecznych zakleszczenia.
Unikanie zakleszczeń
żð Gdy stosujemy tÄ™ metodÄ™ wszystkie warunki konieczne
występowania zakleszczeń są prawdziwe. Nie dopuszczamy do
zakleszczeń poprzez badanie stanu systemu przed każdym
żądaniem przydziału zasobów i niekiedy odrzucamy żądanie
mimo wolnych zasobów.
Wykrywanie zakleszczeń i odtwarzanie
żð Dopuszczamy powstawanie zakleszczeÅ„, ale umiemy je
wykrywać, likwidować i przywracać normalne działanie
systemu po tym zabiegu.
Zapobieganie
zakleszczeniom
46
Zapobieganie zakleszczeniom polega na zaprzeczeniu
co najmniej jednemu z czterech warunków
koniecznych zakleszczenia.
1. Brak wzajemnego wykluczania
2. Brak przetrzymywania i oczekiwania
3. Wywłaszczanie
4. Wykluczenie czekania cyklicznego
Unikanie zakleszczeń
47
Øð W algorytmie unikania dynamicznie bada siÄ™ stan
przed każdym żądaniem i sprawdza się, czy jego
spełnienie może doprowadzić do czekania cyklicznego.
Øð Stan bezpieczny  stan w którym istnieje ciÄ…g
bezpieczny
Ciąg procesów P(1), P(2), ..., P(n) nazywamy
bezpiecznym, gdy dla i=1, 2, ..., n maksymalne potrzeby
każdego procesu P(i) mogą być zaspokojone za pomocą
obecnie dostępnych zasobów i zasobów będących
w posiadaniu procesów P(1), P(2), ..., P(i-1).
Algorytm grafu przydziału
zasobów
48
Øð Zanim proces P(i) rozpocznie dziaÅ‚anie, wszystkie jego krawÄ™dzie
deklaracji muszą pojawić się w grafie przydziału zasobów.
Øð Zamówienie może być speÅ‚nione tylko wtedy, gdy zamiana
krawędzi zamówienia P(i)  > Z(j) na krawędz
przydziału Z(j)  >
P(i), nie spowoduje utworzenia cyklu w grafie przydziału zasobów.
Øð Sprawdzenie bezpieczeÅ„stwa polega na użyciu algorytmu
wykrywania cyklu w tym grafie. Liczba operacji algorytmu
wykrywania cykli w grafie jest rzędu n , jeśli n jest liczbą procesów
w systemie.
Øð JeÅ›li nie ma żadnego cyklu, to przydziaÅ‚ zasobu pozostawi system w
stanie bezpiecznym.
Algorytm grafu przydziału
zasobów
49
Z(1) Z(1)
P(1) P(1)
P(2) P(2)
Z(2) Z(2)
Algorytm bankiera
50
Øð Algorytm grafu przydziaÅ‚u zasobów nie nadaje siÄ™ do
systemu przydzielania zasobów, w którym każdy typ
zasobu ma wiele egzemplarzy.
Øð Gdy proces wchodzi do systemu, musi zadeklarować
maksymalną liczbę egzemplarzy każdego typu zasobu,
które będą mu potrzebne.
Øð Kiedy użytkownik zamawia zbiór zasobów, wtedy
system musi określić, czy ich przydzielenie pozostawi
system w stanie bezpiecznym. Jeśli tak, to zasoby
zostanÄ… przydzielone; w przeciwnym razie proces
będzie musiał poczekać, aż inne procesy zwolnią
wystarczającą ilość zasobów.
Algorytm bankiera
51
Øð Algorytm bankiera opiera sie na analogii z systemem
bankowym.
Øð Różne rodzaje zasobów to różne, wzajemnie nie
wymienialne między sobą waluty.
Øð Klienci to procesy dziaÅ‚ajÄ…ce w systemie, a bank to
system.
Øð Åšrodki pieniężne jakimi dysponuje bank to wolne
zasoby, a pieniądze pożyczone klientom to zasoby
przydzielone procesom.
Øð Maksymalne iloÅ›ci potrzebnych zasobów deklarowane
przez procesy, to wysokości limitów określone
w umowach kredytowych.
Algorytm bankiera
52
Algorytm bankiera  autorem jest
Edsger Dijkstra. Algorytm ten był po raz
pierwszy wykorzystany w systemie
operacyjnym zwanym THE, a opisany
został w języku niderlandzkim w książce
pt. "Een algorithme ter vooikoming van
de dodelijke omarming .
Algorytm bankiera
53
Øð Jeżeli w danym stanie system może doprowadzić do
zakończenia wszystkich procesów, to może to również
zrobić wykonując i kończąc te procesy w pewnej kolejności,
po jednym na raz.
Øð Aby móc zakoÅ„czyć jakiÅ› proces, musimy mięć w systemie
tyle wolnych zasobów, żeby zaspokoić jego potrzeby.
Øð W najgorszym przypadku ilość potrzebnych zasobów jest
równa różnicy między maksymalną zadeklarowaną liczbą
potrzebnych zasobów, a ilością aktualnie przydzielonych
zasobów.
Algorytm bankiera
54
Øð Po zakoÅ„czeniu procesu w systemie może tylko przybyć wolnych
zasobów, gdyż wszystkie zasoby przydzielone procesowi są
zwalniane.
Øð Aby odpowiedzieć na pytanie czy sytuacja jest bezpieczna, musimy
stwierdzić, czy istnieje taka kolejność, w której możemy wykonywać
i kończyć kolejne procesy dochodząc do stanu początkowego - gdzie
wszystkie zasoby będą zwrócone, czyli czy istnieje ciąg bezpieczny.
Øð TakÄ… kolejność możemy konstruować w sposób zachÅ‚anny - jeżeli
istnieje taka kolejność i wolne w danej chwili zasoby wystarczają do
zakończenia procesu P, to istnieje również taka kolejność
zaczynajÄ…ca sie od P.
Øð Algorytm ten ma zÅ‚ożoność O(n2m), gdzie n jest liczba procesów, a
m liczbą typów zasobów.
Wykrywanie zakleszczeń i odtwarzanie
55
W systemie, w którym nie stosuje się algorytmu
zapobiegania zakleszczeniom ani ich unikania, może
dojść do zakleszczenia. W takiej sytuacji w systemie
musza, istnieć:
żð algorytm sprawdzajÄ…cy stan systemu w celu wykrycia, czy
wystąpiło zakleszczenie;
żð algorytm likwidowania zakleszczenia.
Wykrywanie zakleszczeń
i odtwarzanie
56
Graf oczekiwania - Jeśli wszystkie zasoby mają tylko po
jednym egzemplarzu, to można zdefiniować algorytm
wykrywania zakleszczenia korzystajÄ…cy z odmiany grafu
przydziału zasobów, nazywanej grafem oczekiwania. Graf
ten powstaje z grafu przydziału zasobów przez usunięcie
węzłów reprezentujących typy zasobów i złączenie
uwolnionych w ten sposób końców krawędzi.
żðWierzchoÅ‚kami tego grafu sÄ… procesy dziaÅ‚ajÄ…ce w systemie
P(1), P(2), ..., P(n).
żðKrawÄ™dz
oczekiwania od procesu P(k) do procesu P(l)
oznacza, że proces P(k) czeka na zwolnienie zasobu przez
proces P(l).
Wykrywanie zakleszczeń i odtwarzanie
57
Po wykryciu zakleszczenia należy je zlikwidować.
Kryteria, z których można skorzystać przy wyborze
procesu do przerwania:
żð Priorytet procesu.
żð Czas dziaÅ‚ania procesu i przewidywany czas do jego
ukończenia.
żð Zasoby przydzielone procesowi.
żð Zasoby potrzebne procesowi do zakoÅ„czenia dziaÅ‚ania.
żð Ile procesów trzeba bÄ™dzie zakoÅ„czyć?
żð Czy proces jest wsadowy, czy interakcyjny?
Zarządzanie pamięcią
58
Øð Proces, ma dostÄ™p tylko do pamiÄ™ci przydzielonej mu przez system
operacyjny.
Øð System operacyjny tworzy na potrzeby procesu obraz przydzielonej mu
pamięci, który nie zmienia się gdy zawartość pamięci przydzielonej
procesowi jest przemieszczana w pamięci fizycznej. Pamięć, taką jak ją
widzi dany proces, nazywamy pamięcią logiczną.
Øð Adresy, którymi posÅ‚ugujÄ… siÄ™ procesy nazywamy adresami logicznymi.
Øð Pamięć logiczna jest realizowana przez mechanizm, który jest również
odpowiedzialny za ochronę pamięci. Mechanizm ten jest realizowany
sprzętowo przez jednostkę zarządzania pamięcią
(ang. memory management unit, MMU), która:
żð sprawdza, czy używane przez proces adresy logiczne sÄ… poprawnymi adresami,
tzn. czy odnoszą się do przydzielonej procesowi pamięci
żð tÅ‚umaczy adresy logiczne, na odpowiadajÄ…ce im adresy fizyczne.
Zarządzanie pamięcią
59
Øð PrzydziaÅ‚ ciÄ…gÅ‚y - MMU zawiera dwa
programowalne rejestry. Rejestr przemieszczenia
zawiera poczÄ…tkowy adres fizyczny przydzielonego
obszaru. Rejestr graniczny zawiera wielkość
przydzielonego obszaru.
Zarządzanie pamięcią
60
Øð PrzydziaÅ‚ ciÄ…gÅ‚y - MMU zawiera dwa
programowalne rejestry. Rejestr przemieszczenia
zawiera poczÄ…tkowy adres fizyczny przydzielonego
obszaru. Rejestr graniczny zawiera wielkość
przydzielonego obszaru.
Zarządzanie pamięcią
61
Øð Segmentacja - pamięć wykorzystywana przez
proces, nie stanowi jednego spójnego obszaru.
Zwykle składa się z kilku segmentów:
żð kod programu
żð zmienne globalne
żð stos
żð sterta
Øð System operacyjny może wiÄ™c przydzielać
procesom pamięć nie w postaci jednego spójnego
bloku, ale kilku takich bloków, segmentów.
Zarządzanie pamięcią
62
Øð Segmentacja - pamięć wykorzystywana przez
proces, nie stanowi jednego spójnego obszaru.
Zwykle składa się z kilku segmentów:
żð kod programu
żð zmienne globalne
żð stos
żð sterta
Øð System operacyjny może wiÄ™c przydzielać
procesom pamięć nie w postaci jednego spójnego
bloku, ale kilku takich bloków, segmentów.
Zarządzanie pamięcią
63
Øð Stronicowanie - proces widzi spójny obszar pamiÄ™ci logicznej, ale
nie tworzy ona spójnego obszaru w pamięci fizycznej. Zarówno
pamięć logiczna, jak i pamięć fizyczna jest podzielona na kawałki
równej wielkości.
Øð W odniesieniu do pamiÄ™ci logicznej mówimy o stronach, a w
odniesieniu do pamięci fizycznej mówimy o ramkach.
Øð PodziaÅ‚ pamiÄ™ci logicznej na strony nie jest widoczny dla procesu.
Øð Odpowiednia liczba bardziej znaczÄ…cych bitów w adresie okreÅ›la
stronę, a pozostałe mniej znaczące bity określają pozycję w obrębie
strony.
Øð MMU musi sprawdzić, czy numer strony jest poprawny i która
ramka zawiera daną stronę. Służy do tego tzw. tablica stron.
Tablica ta jest indeksowana numerami stron. Dla danej strony
zawiera ona numer ramki, w której znajduje się dana strona.
Zarządzanie pamięcią
64
Øð Stronicowanie - proces widzi spójny obszar pamiÄ™ci logicznej, ale
nie tworzy ona spójnego obszaru w pamięci fizycznej. Zarówno
pamięć logiczna, jak i pamięć fizyczna jest podzielona na kawałki
równej wielkości.
Øð W odniesieniu do pamiÄ™ci logicznej mówimy o stronach, a w
odniesieniu do pamięci fizycznej mówimy o ramkach.
Øð PodziaÅ‚ pamiÄ™ci logicznej na strony nie jest widoczny dla procesu.
Øð Odpowiednia liczba bardziej znaczÄ…cych bitów w adresie okreÅ›la
stronę, a pozostałe mniej znaczące bity określają pozycję w obrębie
strony.
Øð MMU musi sprawdzić, czy numer strony jest poprawny i która
ramka zawiera daną stronę. Służy do tego tzw. tablica stron.
Tablica ta jest indeksowana numerami stron. Dla danej strony
zawiera ona numer ramki, w której znajduje się dana strona.