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