Systemy operacyjne cz.2





Komunikaty


System komunikatów umożliwia procesom wzajemną komunikację bez wykorzystywania wspólnej pamięci.
Komunikacja bezpośrednia (z wykorzystaniem ID)
• symetryczna (dokładnie 1 łącze między dokładnie 2 procesami)
• nadaj komunikat do procesu X
• odbierz komunikat od procesu Y
• asymetryczna
• nadaj komunikat do procesu X
• odbierz komunikat od dowolnego procesu. Identyfikator procesu zostanie uzupełniony po odebraniu.
• nadaj komunikat do skrzynki S
• odbierz komunikat ze skrzynki S
Komunikacja pośrednia (z wykorzystaniem skrzynek pocztowych)
• Dwa procesy komunikują się przez wspólną skrzynkę
• Z tej samej skrzynki może korzystać więcej procesów
• Każda para łączy może mieć kilka łączy (=skrzynek)
• Łącza jedno i dwukierunkowe)
Komunikaty - buforowanie
Kolejka komunikatów przypisanych do łącza
• Pojemność zerowa – łącze nie dopuszcza by czekały w nim jakieś komunikaty – nadawca czeka aż odbiorca odczyta komunikat
• Pojemność ograniczona do n komunikatów. Jeżeli nadawca chce nadać n+1 komunikat, to musi czekać na zwolnienie miejsca.
• Pojemność nieograniczona – brak wstrzymywania nadawcy. Odbiorca czeka na komunikat, a nadawca zakończył już działanie – proces odbiorca „wisi”. Konieczna interwencja SO. Analogicznie gdy nadawca czeka na potwierdzenie odbioru od zakończonego odbiorcy.
Utrata komunikatów (lub zniekształcenie)
• SO odpowiada za wykrywanie utraty i za ponowne nadanie komunikatu
• Nadawca odpowiada za opiekę nad komunikatami i ich ponowne przesłanie (jeśli istnieje taka konieczność)
• SO odpowiada za wykrycie utraty komunikatu i informuje o tym nadawcę. Nadawca wysyła ponownie komunikat (wg własnych potrzeb)


Przydział procesora


Kiedy decyzja o przydziale procesora:
1. Proces przeszedł od stanu aktywności do stanu czekania
2. Proces przeszedł od stanu aktywności do stanu gotowości
3. Proces przeszedł od stanu czekania do stanu gotowości
4. Proces zakończył działanie
Gdy planowanie odbywa się wyłącznie w przypadku 1 i 4 przydzielamy procesor nowemu procesowi z kolejki (o ile istnieje) – nie ma możliwości wyboru– niewywłaszczeniowy schemat planowania (Windows). Dla 2 i 3 można dokonać wyboru – wywłaszczeniowy schemat planowania.

Kryteria planowania:


• Wykorzystanie procesora (optymalnie pomiędzy 40% - 90%)
• Przepustowość – liczba procesów kończonych w jednostce czasu
• Czas cyklu przetwarzania – całkowity czas pomiędzy nadejściem procesu a momentem jego zakończenia
• Czas oczekiwania – suma czasów oczekiwania w kolejce procesów gotowych do działania
• Czas odpowiedzi – czas pomiędzy wysłaniem żądania a pierwszą odpowiedzią – najczęściej uzależniony od prędkości we-wy.
Algorytmy planowania:
FCFS (first-come first-served).
Algorytm niewywłaszczający. Średni czas może być bardzo długi!
(0+24+27)/3=17 ms
(6+0+3)/3=3ms
Efekt konwoju – wszystkie procesy czekają na zwolnienie procesora przez jeden duży proces
Dla FCFS (0+6+14+21)/
4=10,25ms
Najpierw najkrótsze zadanie SJF (shortest-job-first)
Algorytm optymalny – problem z określeniem długości następnej fazy procesora – jedynie szacowanie.
(3+16+9+0)/4=7 ms
Algorytm wywłaszczający lub nie. Jeżeli tak, to długi proces aktualnie uruchomiony proces może zostać usunięty z procesora, jeżeli nowy jest krótszy.
Najpierw najkrótsze zadanie SJF (shortest-job-first)
Dla SJF z wywłaszczeniem ((10-1)+(1-1)+(17-2)+(5-3))/4=6,5 ms
Proces- Czas przybycia- Czas trwania
P1- 0-8
P2- 1- 4
P3- 2- 9
P4- 3- 5
Dla SJF bez wywłaszczenia 7,75 ms
Priorytety
8,2 ms
Proces- Czas trwania- fazy Priorytet
P1- 10- 3
P2- 1- 1
P3- 2- 3
P4- 1- 4
P5- 5- 2
Głodzenie (nieskończone blokowanie).
Postarzanie (zwiększ priorytet o 1 co 15 min (0-127))
Rotacyjne
Kwant procesora co 4 ms
Proces- Czas trwania
P1- 24
P2- 3
P3- 3

Zakleszczenia procesów


Normalne działanie procesu:
• Zamówienie – jeśli zamówienie nie jest możliwe do spełnienia natychmiast, to proces czeka na zwolnienie zasobu
• Użycie – proces może korzystać z zasobu
• Zwolnienie – proces oddaje zasób
Warunki zakleszczenia:
• Wzajemne wykluczenie – przynajmniej jeden zasób jest niepodzielny – może korzystać z niego jedynie jeden proces
• Przetrzymanie i oczekiwanie – jeden z procesów ma przydzielony co najmniej jeden zasób i czeka jeszcze na dodatkowy, aktualnie zajęty przez inny proces
• Brak wywłaszczeń – proces z własnej inicjatywy oddaje zasób
• Czekanie cykliczne – proces 1 czeka na zasób przetrzymywany przez proces 2, który to czeka na zasób przetrzymywany przez proces 3, który ... Proces n przetrzymuje zasób, z którego chce skorzystać proces n-1, samemu oczekując na zasoby zajmowane przez proces 1
Metody postępowania:
• Stosujemy protokoły, które nigdy nie pozwalają na zakleszczenia
• Pozwalamy systemowi na zakleszczenia ponieważ umie sobie z nimi poradzić
• Zakładamy, że problem nie istnieje – zakleszczenia nigdy nie wystąpią (większość systemów w tym UNIX)
Zapobieganie zakleszczeniom:
• Wzajemne wykluczenie – korzystanie z zasobów dzielonych (plik read only może być jednocześnie czytany przez kilka procesów). Niestety, istnieją zasoby niepodzielne z natury.
• Przetrzymanie i oczekiwanie – aby uniknąć należy zagwarantować, że żaden proces, który zamawia zasoby nie ma innych zasobów
• Zamów wszystkie zasoby przed rozpoczęciem i nie zaczynaj jak nie masz wszystkiego
• Zwolnij posiadany zasób – dostaniesz nowy (CD->dysk- >drukarka)
• Brak wywłaszczeń – proces traci wszystkie posiadane zasoby, jeżeli zamówi proces, którego aktualnie nie może otrzymać.
• Czekanie cykliczne
• definiujemy jednoznaczną funkcję F, która urządzeniu Z przyporządkowuje liczbę N, np.:
F(przewijak taśmy)=1
F(dysk)=5
F(drukarka)=12
• Proces może zamówić dowolną liczbę egzemplarzy Zk. Później może zamówić egzemplarze Zl, jeżeli F(Zl)>F(Zk) Inne podejście – proces może zamówić Zl jeżeli zwolnił zasoby Zk gdzie F(Zk)>=F(Zl)
Unikanie zakleszczeń:
• Niech każdy proces zadeklaruje maksymalną liczbę zasobów każdego typu, które mógłby potrzebować. Można posłużyć się algorytmem, który zapewni, że nigdy nie nastąpi zakleszczenie (algorytm unikania zakleszczeń dead-lock-avoidance)
• Algorytm grafu przydziału zasobów
• Algorytm bankiera
Wykrywanie zakleszczeń:
• System musi umieć sprawdzić stan, aby wykryć czy nastąpiło zakleszczenie
• System musi umieć likwidować zakleszczenia
Likwidowanie zakleszczeń
- zakończenie procesu:
• Zakończenie wszystkich zakleszczonych procesów
- mogą wystąpić straty w procesach
– niektóre będą musiały zacząć obliczenia od nowa.
• Kolejne usuwanie procesów z jednoczesnym badaniem, czy pozostałe procesy są wciąż zagnieżdżone – konieczność optymalnego wyboru (priorytet procesu, ile proces liczy i kiedy skończy, jakie zasoby posiada i czy je łatwo wywłaszczyć, ilu jeszcze zasobów potrzebuje proces do zakończenia, ile procesów trzeba przerwać, czy proces jest interakcyjny czy wsadowy)
- wywłaszczenie zasobów:
• Wybór ofiary, której zabierzemy zasoby
• Wycofanie zasobu do takiego stanu, aby po wznowieniu mógł kontynuować normalne działanie
• Głodzenie – co zrobić, aby wywłaszczenie nie będzie dotyczyć tego samego procesu.