PLANOWANIE I PRZYDZIAŁ ZASOBÓW

ZAŁOŻENIA WSTĘPNE

1. wzajemne wyłączanie procesów od zasobów niepodzielnych

2. zapobieganie blokadom powstającym w wyniku 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

KATEGORIE ZASOBÓW

• Procesy centralne

• Pamięć operacyjna

• Urządzenia zewnętrzne

• Pamięć pomocnicza

• Pliki

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.

WARUNKI POWSTANIA BLOKADY

1. Zasoby są niepodzielne

2. procesy przetrzymują przydzielone im zasoby podczas oczekiwania na nowe zasoby

3. Zasobów dopóty nie można sobie zawłaszczać, dopóki są użytkowane.

4. Istnieje łańcuch cykliczny procesów, taki, że każdy proces użytkuje zasoby, które na bieżąco zamawia następny proces w łańcuchu.

ZAPOBIEGANIE BLOKADOM

• trzeba wykluczyć spełnienie co najmniej 1 z 4 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

WYKRYWANIE BLOKADY

jeżeli w grafie istnieje łuk prowadzący od węzła A do B, to znaczy, ze istnieje proces, który ma zasoby A i zamawia zasoby B

USUWANIE BLOKADY

• Można usunąć wszystkie procesy uczestniczące w blokadzie

• Można wznowić wykonywania zablokowanych procesów od pewnego pośredniego punktu kontrolnego, jeśli 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.

• ALGORYTM BANKIERA - definicje

• roszczenie procesu o przydział zasobów - max. wielkość każdego zasobu zamawianego podczas trwania procesu.

• Algorytm pozwala przydzielić zamawiane zasoby tylko wtedy, gdy:

• zamówienie + 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.

PLANISTA

• Planowaniem nazywa się ogólnie ustalanie, kiedy można nowe procesy wprowadzić 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

• 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 prace, wtedy sam spowoduje zawieszenie swego działania w wyniku wykonania operacji czekaj na semaforze

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ę, ze 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ą granice, można nie przyjąć zgłoszenia nowego użytkownika.

WYZNACZANIE PRIORYTETÓW

• Kolejność wykonywania procesów jest wyznaczona 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ązanie do właściwego miejsca w kolejce.

• jest ważne, aby planista miał większy priorytet niż inne procesy

ALGORYTM PLANOWANIA

System ograniczony przez procesor.

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łaszczeniem

• narastający priorytet

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 sytemu jest zbyt duże przy danym, ustalonym przedziale czasu, to nagle obniża się wydajność systemu.

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.

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żliwości przyznaje się tez zasoby na następne zamówienia.

• Przydział pamięci w maszynach z pamięcią stronicowaną może być dokonywany zgodnie z zasadami zbioru roboczego.

• Procesom SO powinno się przyznawać takie priorytety, aby odzwierciedlały pilność zadań wykonywanych przez te procesy.

• Procesy obsługi urządzeń zewn. 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

2

---