Planowanie i przydział zasobów
Rafał Grzybowski
Rafał Grzybowski
Założenia wstępne
1. wzajemne wyłączanie procesów od
zasobów niepodzielnych;
2. zapobieganie blokadom powstającym w
wyniku zaspokajania zamówień na przydział
zasobów;
3. zapewnianie wysokiego poziomu
wykorzystania zasobów;
4. stwarzanie wszystkim procesom okazji do
pozyskania potrzebnych zasobów w
"rozsądnym" czasie.
Rafał Grzybowski
Kategorie zasobów
Procesory centralne
Pamięć operacyjna
Urządzenia zewnętrzne
Pamięć pomocnicza
Pliki
Rafał Grzybowski
BLOKADA
proces A używa zasobów X i zamawia
zasoby Y; proces B używa zasobów Y i
następnie zamawia zasoby X. Jeżeli
oba zasoby są niepodzielne i żaden
proces nie zwolni tych zasobów, które
użytkuje, powstaje blokada
Rafał Grzybowski
Warunki powstawania blokady
1. Zasoby są niepodzielne.
2. Procesy przetrzymują przydzielone im zasoby
podczas oczekiwania na nowe zasoby.
3. Zasobów dopóty nie można zawłaszczać,
dopóki są użytkowane.
4. Istnieje łańcuch cykliczny procesów, taki że
każdy proces użytkuje zasoby, które bieżąco
zamawia następny proces w łańcuchu.
Rafał Grzybowski
Zapobieganie blokadom
trzeba wykluczyć spełnienie co najmniej
jednego z czterech wymienionych powyżej
warunków koniecznych
 warunek 1 trudno, ale czasami może pomóc
spooler
 warunek 2 łatwo, poprzez wcześniejsze
zamawianie zasobów
 warunek 3 łatwo, zawłaszczanie
 warunek 4 , uporządkowane przydzielanie
zasobów według kolejności typów
Rafał Grzybowski
Wykrywanie blokady
jeżeli w grafie istnieje łuk prowadzący od węzła A do węzła
B, to znaczy, że istnieje proces, który ma zasoby A i
zamawia zasoby B
Rafał Grzybowski
Usuwanie blokady
Można usunąć wszystkie procesy uczestniczące
w blokadzie.
Można wznowić wykonywanie zablokowanych
procesów od pewnego pośredniego punktu
kontrolnego, jeżeli taki istnieje.
Można dopóki istnieje blokada, dopóty usuwać
kolejne procesy biorące udział w blokadzie.
Można dopóki istnieje blokada, dopóty
zawłaszczać zasoby procesów uczestniczących
w blokadzie.
Rafał Grzybowski
Unikanie blokady
Rafał Grzybowski
Algorytm Bankiera - definicje
roszczenie procesu o przydział zasobów -
maksymalna wielkość każdego zasobu
zamawianego podczas trwania procesu;
Algorytm pozwala przydzielić zamawiane
zasoby tylko wtedy, gdy:
 zamówienie plus bieżąco używane zasoby są
razem mniejsze niż roszczenie;
 oraz po spełnieniu zamówienia istnieje ciąg, w
którym procesy mogą być wykonane do końca,
nawet wówczas, gdy zamówienia wszystkich
procesów są równe pełnym ich roszczeniom.
Rafał Grzybowski
Algorytm Bankiera
Rafał Grzybowski
Planista
Planowaniem nazywa się ogólnie
ustalanie, kiedy można nowe procesy
wprowadzać do systemu i w jakiej
kolejności powinny one działać.
Za planowanie i decydowanie o przydziale
zasobów odpowiada jeden proces
systemu operacyjnego - PLANISTA
Rafał Grzybowski
Wprowadzanie nowych procesów
W systemach wsadowych prace czekające na
wykonanie są gromadzone w puli prac;
 W celu osiągnięcia dużej przepustowości systemu,
planista powinien inicjować nowy proces wkrótce po
tym, jak okaże się, że pojemność zasobów jest
dostateczna.
W systemie wielodostępnym procesy są
tworzone wówczas, gdy zgłaszają się do
systemu jego użytkownicy  gdy czas
reagowania na zamówienie osiągnie
dopuszczalną granicę, można nie przyjąć
zgłoszenia nowego użytkownika.
Rafał Grzybowski
Wyznaczanie priorytetów
Kolejność wykonywania procesów jest
wyznaczona albo przez uporządkowanie kolejki
procesora;
Planista jest odpowiedzialny za
przyporządkowanie priorytetów procesom w taki
sposób, aby, kiedy staną się one wykonywalne,
były dowiązane do właściwego miejsca w
kolejce.
jest ważne, aby planista miał większy priorytet
niż inne procesy.
Rafał Grzybowski
Planista  cd.
System wywołuje planistę, gdy:
 nadeszło zamówienie na zasoby;
 zwolniono użytkowane zasoby;
 proces zakończył działanie;
 nowa praca przybyła do puli prac (lub zgłosił się
nowy użytkownik).
Kiedy planista skończy pracę, wtedy sam
spowoduje zawieszenie swego działania w
wyniku wykonania operacji czekaj na semaforze
Rafał Grzybowski
Algorytmy planowania
System ograniczony przez procesor:
Rafał Grzybowski
Algorytm najkrótszej pracy
kolejka jest uporządkowana według
czasu potrzebnego do wykonania
każdego procesu
Algorytm ten pozwala, by wszystkie
procesy wykonywały się do końca
Modyfikacje:
 z zawłaszczaniem
 narastający priorytet
Rafał Grzybowski
Algorytm rotacyjny
Pozwala szybko reagować na krótkie
zamówienia.
Każdemu procesowi w systemie przydziela się
ustalony, jednakowy przedział czasu na
wykonanie zamawianej przez niego usługi.
Po upływie tego czasu proces będzie
przekazany z powrotem na koniec kolejki.
jeżeli załadowanie systemu jest zbyt duże przy
danym, ustalonym przedziale czasu, to nagle
obniża się wydajność systemu
Rafał Grzybowski
Kolejka dwupoziomowa
Odmiana algorytmu rotacyjnego
Procesy, które nie zakończyły się w
ustalonej liczbie przedziałów czasu, są
przenoszone do kolejki drugoplanowej
Kolejka drugoplanowa jest obsługiwana
tylko wtedy, gdy nie ma w systemie innych
procesów z kolejki pierwszoplanowej
Rafał Grzybowski
Ogólny model planowania
Rafał Grzybowski
Kryteria planowania
Procesom, które otrzymały wiele zasobów,
można nadać wysoki priorytet, aby
przyspieszyć ich zakończenie.
Procesom, które otrzymały wiele zasobów, w
miarę możności przyznaje się też zasoby na
następne zamówienia.
Przydział pamięci w maszynach z pamięcią
stronicowaną może być dokonywany zgodnie
z zasadami zbioru roboczego
Rafał Grzybowski
Kryteria planowania
Procesom systemu operacyjnego powinno
się przyznawać takie priorytety, aby
odzwierciedlały pilność zadań wykonywanych
przez te procesy.
Procesy obsługi urządzeń zewnętrznych
powinny mieć wysoki priorytet
Jeżeli w systemie nie korzysta się z metod
zapobiegania blokadom, to do wszystkich
zamówień na zasoby powinno się stosować
algorytm unikania blokady
Rafał Grzybowski
Hierarchia procesów
Rafał Grzybowski
Podsumowanie