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.