Poniżej przedstawiono zadania z egzaminu końcowego (rok 2003/2004). Czas przeznaczony na rozwiązanie zadań wynosił 140 min.
-
Niech s oznacza semafor dwustronnie ograniczony, który nie może przekroczyć danej wartości smax > 0. Operacje P i V dla tego semafora zdefiniowane są następująco:
- P(s) : czekaj aż s > 0, s := s - 1.
- V(s) : czekaj aż s < smax, s := s + 1
Zaproponuj implementację monitora realizującego takie operacje semaforowe.
Rozwiązanie
-
Udowodnij, że dla procesów Pi i Pj poniższy algorytm (przykład kodu dla procesu Pi) nie gwarantuje zachowania warunku bezpieczeństwa algorytmu wzajemnego wykluczania. Na potrzeby indeksowania tablicy flag przyjęto i = 0, j = 1.
shared flag: array [0..1] of Boolean;
shared turn: integer;
turn := j;
flag[i] := true;
while flag[j] and turn ą i do nic;
//sekcja krytyczna
flag[i] := false;
Rozwiązanie
-
W pewnej parowozowni istnieje M miejsc remontowych (równocześnie może być naprawianych M
lokomotyw). Naprawa taka trwa pewien nieznany, ale skończony okres
czasu, po czym lokomotywa opuszcza parowozownię i rozpoczyna się jej
normalna eksploatacja. Cykl ten powtarza się. Aby wjechać do
parowozowni należy przejechać przez obrotową nastawnię. Do nastawni
prowadzą jedynie dwa tory, którymi można wjechać na teren parowozowni.
Należy zagwarantować, że nie dojdzie do sytuacji, w której na jednym
odcinku toru (2xA, 1xB, MxC) znajdą się 2 lokomotywy, gdyż
grozi to zderzeniem. Należy założyć że pracownik obsługujący nastawnię
posiada wiedzę, która pozwala mu operować nastawnią w ten sposób, iż
wybierane będą, o ile są dostępne, wolne tory prowadzące do parowozowni
lub do bram. Co pewien czas w parowozowni musi zostać przeprowadzony
remont. Decyzję o tym podejmuje szef robót remontowych. On także
decyduje o jego zakończeniu. Dla bezpieczeństwa robotników, w czasie
remontu żadna lokomotywa nie może znajdować się na terenie parowozowni.
Napisz pseudokod procesów lokomotywy i szefa robót remontowych. Do
synchronizacji procesów wykorzystaj semafory uogólnione na których
można wykonać operacje opuszczenia semafora S o wartość x P(S, x) i odpowiednio operację podniesienia V(S, x). Procesy oczekujące na semaforze są obsługiwane w losowej, nieznanej z góry kolejności.
Rozwiązanie
-
Zakładamy, że system składa się z dwóch procesów, P1 i P2,
współdzielących cztery jednostki zasobu R. Każdy z procesów może żądać
co najwyżej 3 jednostek tego zasobu. Procesy mogą znajdować się w
jednym z poniżej podanych stanów:
- Nie posiada żadnej jednostki zasobu R
- Nie posiada żadnej jednostki zasobu R, żąda jednej jednostki zasobu R
- Posiada jedną jednostkę zasobu R
- Posiada jedną jednostkę zasobu R, żąda drugiej jednostki zasobu R
- Posiada dwie jednostki zasobu R
- Posiada dwie jednostki zasobu R, żąda trzeciej jednostki zasobu R
- Posiada trzy jednostki zasobu R
Możliwe są następujące przejścia pomiędzy stanami:
- ze stanu 0 do 1, 2 do 3, oraz 4 do 5 poprzez żądanie jednej jednostki zasobu,
- ze stanu 1 do 2, 3 do 4, oraz z 5 do 6 poprzez uzyskanie jednej jednostki zasobu,
- ze stanów 6 do 4, 4 do 2, oraz 2 do 0 poprzez zwolnienie jednej jednostki zasobu.
Niech Sij oznacza stan systemu, w którym i jest stanem procesu P1, a j
jest stanem procesu P2. Oceń stany systemu wyszczególnione w poniższej
tabeli.
Stan |
Stan bezpieczny |
Stan niebezpieczny |
Stan zakleszczenia |
Stan nieosiągalny |
S32 |
|
|
|
|
S55 |
|
|
|
|
S44 |
|
|
|
|
S46 |
|
|
|
|
S36 |
|
|
|
|
S54 |
|
|
|
|
S51 |
|
|
|
|
Rozwiązanie
-
Dane są dwa systemy plików z przydziałem indeksowym. W jednym z nich - oznaczonym jako FSW - przyjęto strukturę 3-poziomową bloku indeksowego, a w drugim - oznaczonym jako FSL - przyjęto strukturę listową. Niech F1 będzie plikiem o maksymalnej wielkości (wynikającej ze struktury bloku indeksowego) w systemie FSW. Porównaj liczbę bloków dyskowych wymaganych do przechowania pliku F1 w systemie FSW i FSL, oznaczoną odpowiednio NW i NL, a następnie oceń prawdziwość poniższych sformułowań:
|
TAK |
NIE |
(a) NW = 2*NL (liczba bloków dyskowych potrzebnych do przechowania pliku F1 w systemie FSW jest dwa razy większa niż liczba bloków w systemie FSL) |
|
|
(b) NW = NL + 2 |
|
|
(c) NW = NL + 1 |
|
|
(d) NW = NL |
|
|
(e) NW = NL - 1 |
|
|
(f) NW = NL - 2 |
|
|
(g) NW = 0,5 * NL |
|
|
(h) NW = NL2 - 1 |
|
|
(i) NW = log2NL + 1 |
|
|
(j) NW < NL |
|
|
Rozwiązanie
-
W systemie komputerowym wykonane zostały 4 procesy P1, P2, P3 i P4.
Poniższa tabela przedstawia atrybuty tych procesów przy założeniu, że
chwila czasu 0 odpowiada momentowi zgłoszenia do systemu procesu P1.
|
czas zgłoszenia do systemu |
wymagany czas obsługi |
P1 |
0 |
8 |
P2 |
2 |
6 |
P3 |
3 |
3 |
P4 |
9 |
4 |
Oceń prawdziwość następujących sformułowań:
|
TAK |
NIE |
(a) W przypadku zastosowania algorytmu SJF szeregowania zadań czas oczekiwania procesu P3 wynosi 8. |
|
|
(b) W przypadku zastosowania algorytmu SJF szeregowania zadań czas cyklu przetwarzania procesu P2 wynosi 6. |
|
|
(c) W przypadku zastosowania algorytmu SJF szeregowania zadań proces P3 zakończy się przed procesem P1. |
|
|
(d) W przypadku zastosowania algorytmu SJF szeregowania zadań proces P2 zakończy się przed procesem P4. |
|
|
(e) W przypadku zastosowania algorytmu FIFO szeregowania zadań czas oczekiwania procesu P3 wynosi 6. |
|
|
(f) W przypadku zastosowania algorytmu FIFO szeregowania zadań czas cyklu przetwarzania procesu P2 wynosi 12. |
|
|
(g) W przypadku zastosowania algorytmu FIFO szeregowania zadań proces P3 zakończy się przed procesem P4. |
|
|
(h) W przypadku zastosowania algorytmu SJF łączny czas
przetwarzania wszystkich 4 procesów jest mniejszy niż w przypadku
algorytmu FIFO. |
|
|
-
W systemie komputerowym z pamięcią wirtualną dostępnych jest 6 ramek o
rozmiarze 32B każda, ponumerowanych od 1 do 6. W systemie tym działają
2 procesy P1 i P2, synchronizujące swoje działania za pomocą semaforów s1 i s2,
których bieżące wartości wynoszą odpowiednio 0 i 1. Przestrzeń adresowa
każdego z procesów wynosi 256B, z których pierwsze 64B przeznaczone są
na program, a pozostałe 192 na znakową tablicę tab (char tab[192]). Tablica tab
stanowi prywatną część każdego z procesów. Bieżący stan tablicy stron
każdego procesu (wraz z wartością bitu poprawności) oraz wykonywany
przez nie programu przedstawia poniższa tabela. W programie tym każda
instrukcja (odpowiadająca dokładnie jednej linii kodu) zajmuje 4B.
|
proces P1 |
proces P2 |
tablica stron |
nr ramki |
bity |
nr ramki |
bity |
1 |
p |
3 |
p |
|
n |
|
n |
|
n |
|
n |
|
n |
|
n |
|
n |
|
n |
|
n |
|
n |
|
n |
|
n |
|
n |
|
n |
program |
P(s1);
tab[0] = 'a';
tab[1] = 'b';
tab[32] = 'A';
V(s2);
|
P(s2);
tab[0] = 'x';
tab[1] = 'y';
V(s1);
P(s2);
tab[100] = 'x';
tab[1] = 'b';
|
Przyjmując następujące założenia:
- w systemie zastosowano algorytm WS (ang. working set) z rozmiarem okna t = 4,
- zbiory robocze są początkowo puste,
- początkowo system działa w kontekście procesu P1,
- w systemie zastosowano niewywłaszczający algorytm szeregowania procesów,
Oceń prawdziwość poniższych sformułowań:
|
TAK |
NIE |
(a) Pierwszy odniesienie do pamięci spowoduje błąd strony. |
|
|
(b) Łączna liczba błędów strony w systemie w trakcie przetwarzania wyniesie 3. |
|
|
(c) Proces P1 wygeneruje tyle samo błędów strony co proces P2. |
|
|
(d) Liczba operacji zapisu strony na urządzeniu wymiany wyniesie 2. |
|
|
(e) Pierwszy błąd strony pojawi się przy czwartym odniesieniu do pamięci. |
|
|
(f) Łączna liczba błędów strony w systemie w trakcie przetwarzania będzie większa niż 5. |
|
|
|