Ćwiczenia
1. Co oznacza termin czekanie aktywne? Jakie inne rodzaje czekania występuj+- w systemie operacyjnym? Czy można uniknąć czekania aktywnego w zupełności? Odpowiedź uzasadnij.
2. Udowodnij, że algorytm piekarni ma następującą właściwość: jeśli proces Pi jest w sekcji krytycznej oraz proces Pk (k<>i) ma już wybrany numer[k]<>0, to (numer[i],i) < (numer[k],k).
3. Pierwsze poprawne , programowe rozwi+-zanie problemu sekcji krytycznej jest autorstwa Dekkera. Dwa procesy, P0 i P1, dzielą następujące zmienne
var znacznik: array[0..1] of boolean; (*pocz+-tkowo fałszywe*)
numer:0..1;
Struktura procesu Pi (i=0 lub 1), przy czym Pj (j=1 lub 0) oznacza drugi proces, jest taka:
var j: 0..n;
repeat
    repeat
    znacznik[i] := gotowy;
    j := numer;
    while j<>i
        do id znacznik[j] <> bezczynny
        then j := numer;
        else j := j + 1 mod n;
        znacznik[i] := w-sekcji;
        j := 0;
            while (j < n) and (j = i or znacznik[j] <> w-sekcji) do
            j := j + 1;
    until (j >= n) and (numer = i or znacznik[numer] = bezczynny);
numer := i;

sekcja krytyczna 

j := numer + 1 mod n;
while (znacznik[j] = bezczynny) do j := j + 1 mod n;
numer := j;
znacznik[i] := bezczynny;

reszta
until false

Udowodnij, że ten algorytm spełnia wszystkie trzy wymagania odnośnie do sekcji krytycznej.

4. Problem śpiącego golibrody (ang. The Sleeping-Barber Problem).W zakładzie fryzjerskim jest poczekalnia z n krzesłami i salon z jednym tylko fotelem. Jeśli brakuje klientów, to fryzjer po prostu zasypia. Jeżeli w poczekalni nie ma wolnych miejsc, to nowy klient opuszcza zakład. Gdy fryzjer jest zajęty, ale są wolne miejsca, wówczas klient siada na jednym z nich. Jeśli fryzjer śpi, to klient go budzi. Napisz program koordynujący zachowanie fryzjera i klientów.

5. Problem palaczy tytoniu (ang. The Cigarette-Smokers Problem). Roz­ważmy system z trzema procesami palaczy i jednym procesem-dostawcy. Każdy palacz nieustannie skręca i wypala papierosa. Aby jednak skręcić i zapalić papierosa, palacz potrzebuje trzech rzeczy: tytoniu, papieru i zapałek. Jeden z procesów-palaczy ma papier, drugi ma tytoń, a trzeci - zapałki. Dostawca ma nieograniczone ilości wszystkiego. Dostawca kładzie dwa różne składniki na stole. Palacz, który ma pozostały składnik, robi wówczas skręta, wypala go i sygnalizuje to dostawcy. Wówczas dostawca znów kładzie dwa składniki na stole i cykl się powtarza. Napisz program koordynujący działania dostawcy i palaczy.

6. Wykaż, że monitory, warunkowe regiony krytyczne oraz semafory są równoważne w sensie możliwości rozwiązywania za ich pomocą tych samych typów problemów synchronizacji

7. Napisz monitor obsługujący ograniczone buforowanie, w którym bufory (porcje) są umieszczone w obrębie samego monitora.

8. Ścisłe wzajemne wykluczanie wewnątrz monitora powoduje, że monitor ograniczonego buforowania z ćw. 7 jest przydatny głównie do małych porcji. 
(a) Wyjaśnij, dlaczego to stwierdzenie jest prawdziwe?

(b) Zaprojektuj nowy schemat odpowiedni dla większych porcji

9. Załóżmy, że instrukcja sygnalizuj może wystąpić tylko jako ostatnia instrukcja w procedurze monitora. W jaki sposób może to wpłynąć na uproszczenie implementacji omówionej w p. 6.7?

10. Rozważmy system złożony z procesów P1>_, P2, ..., P", z których każdy ma jednoznaczny numer priorytetu. Napisz monitor, który przydziela tym procesom trzy identyczne drukarki wierszowe, używając numerów priorytetów przy decydowaniu o kolejności przydziału.

11.Plik ma być dzielony przez różne procesy, z których każdy ma jednoznaczny numer. Do tego pliku może mieć dostęp jednocześnie kilka procesów przy następującym ograniczeniu: suma wszystkich jednoznacznych numerów przypisanych procesom, które mają w danej chwili dostęp do pliku, musi być mniejsza od n. Napisz monitor koordynujący dostęp do tego pliku.

12. Załóżmy, że monitorowe operacje czekaj \ sygnalizuj zastępujemy pojedynczą konstrukcją oczekuj(B\ w której B jest ogólnym wyrażeniem boolowskim; operacja ta powoduje, że wykonujący ją proces rozpoczy­na czekanie na spełnienie warunku B.

(a) Napisz monitor implementujący za pomocą tej konstrukcji problem czytelników i pisarzy.

(b) Wyjaśnij, dlaczego w ogólnym przypadku konstrukcji tej nie da się wydajnie implementować.

(c) Jakie ograniczenia należałoby nałożyć na instrukcję oczekuj, aby można ją było zrealizować efektywnie? (Wskazówka: należy ograniczyć ogólność wyrażenia B; Kessels [209]).

13. Napisz monitor implementujący budzik, który pozwala wywołującemu go programowi opóźniać się o określoną liczbę jednostek czasu (tyknieć). Możesz założyć istnienie rzeczywistego zegara sprzętowego, który w regularnych odstępach czasu wywołuje procedurę tik-tak w Twoim monitorze.

14. Dlaczego w systemie Solaris 2 wprowadzono wiele mechanizmów blokowania? W jakich sytuacjach stosuje się czekanie aktywne, blokowanie za pomocą semaforów, zmienne warunkowe oraz blokowanie na czas czytania lub pisania? W jakim celu system korzysta z każdego z tych mechanizmów?

15. Omów różnice między trzema rodzajami pamięci: ulotną, nieulotną i trwałą, biorąc pod uwagę ich koszt.

16. Wyjaśnij mechanizm punktu kontrolnego. Jak często należy wykonywać działania w punktach kontrolnych? W jaki sposób częstość występowania punktów kontrolnych wpływa na:
* wydajność systemu podczas jego bezawaryjnej pracy; 
* czas zużywany na odtwarzanie stanu systemu po awarii; 
* czas zużywany na rekonstrukcję systemu po awarii dysku. 
17. Wyjaśnij zasadę niepodzielności transakcji.

18. Wykaż, że protokół blokowania dwufazowego zapewnia szeregowalność pod względem konfliktów.

19. Wykaż, że istnieją plany możliwe do zrealizowania z użyciem protokołu blokowania dwufazowego, lecz nie nadające się do protokołu ze znacznikami czasu - i na odwrót