Poniżej przedstawiono zadania z egzaminu końcowego (rok 2002/2003). Czas przeznaczony na rozwiązanie zadań wynosił 120 min.
- W UNIX'owym systemie plików, w którym: rozmiar bloku wynosi 1KB,
wskaźnik do bloku jest wartością 32-bitową, i-węzeł zawiera 10
bezpośrednich wskaźników do bloków z danymi umieszczono 2 pliki o
rozmiarach 20780B i 544868B.
(a) Ile bloków należy zaalokować w celu przechowania zawartości tych plików?
(b) Ile bajtów przestrzeni dyskowej łącznie pozostanie niewykorzystane w wyniku fragmentacji wewnętrznej?
Rozwiązanie
- W systemie wielozadaniowym zastosowano wywłaszczający priorytetowy
algorytm szeregowania zadań (planowania przydziału procesora).
Priorytet procesu zmienia się liniowo w czasie zgodnie ze
współczynnikiem:
α - podczas oczekiwania procesu w kolejce procesów gotowych na przydział procesora,
β - w stanie aktywności (wykonywania przez procesor).
W chwili wejścia do kolejki procesów gotowych (czyli zawsze w chwili
zmiany stanu na GOTOWOŚĆ) proces otrzymuje priorytet o wartości 0.
Wzrost tej wartości oznacza zwiększenie priorytetu procesu, i tym samym
spadek jego zmniejszenie. Jaki znany algorytm szeregowania uzyskamy,
gdy:
(a) β > α > 0,
(b) α < β < 0?
Rozwiązanie
- Moduł zarządzania pamięcią realizuje w przestrzeni adresowej o rozmiarze 64KB następujący ciąg żądań od procesów aplikacyjnych:
- - przydział bloku A o rozmiarze 15KB,
- - przydział bloku B o rozmiarze 8KB,
- - przydział bloku C o rozmiarze 10KB,
- - przydział bloku D o rozmiarze 12KB,
- - przydział bloku E o rozmiarze 15KB,
- - zwolnienie bloku B
- - zwolnienie bloku D
- - przydział bloku F o rozmiarze 3KB
- - przydział bloku G o rozmiarze 6KB
Czy żądanie przydziału bloku o wielkości 8KB może zostać
zrealizowane jako kolejne, gdy w systemie nie ma możliwości relokacji
bloków i zastosowany został następujący algorytm przydziału:
- (a) pierwsze dopasowanie (first fit),
- (b) najlepsze dopasowanie (best fit),
- (c) najgorsze dopasowanie (worst fit)?
Rozwiązanie
-
Dany jest stan początkowy systemu:
|0 0 2 1 1| |5| |3 5 3 5 3|
A = |2 0 4 0 1| m = |9| C = |2 1 5 9 6|
|1 1 1 2 1| |9| |2 2 4 2 6|
a) Stosując algorytm Holt'a sprawdź, czy stan jest bezpieczny. b)
Zakładając, że konsekwentnie stosowane jest podejście unikania, podaj
sekwencję stanów systemu (zaznaczająąc procesy zawieszone)
odpowiadającą następującego ciągowi żądań zasobów:
- w chwili t1
|0|
ro^a(P2) = |1|
|0|
- w chwili t2>t1
|0|
ro^a(P3) = |1|
|1|
- w chwili t3>t2
|1|
ro^r(P4) = |0|
|1|
Rozwiązanie
-
Zaproponuj rozwiązanie problemu czytelników i pisarzy za pomocą
mechanizmu monitora, przy założeniu, że priorytet mają pisarze. Oznacza
to, że jeśli pisarz czeka na wejście do czytelni zajętej przez
czytelników, to nie wpuszcza już nowych czytelników.
- Przedstaw implementację wielowartościowych operacji semaforowych
P(S,n), V(S,n) oraz operacji inicjującej I(S,n) z użyciem binarnych
operacji semaforowych Pb(B) i Vb(B).
- Pracownicy kamieniołomu układają 3 typy bloków kamiennych na
palecie. Bloki mają ustandaryzowane rozmiary o jednostkowej szerokości
i wysokości. Długości bloków wynoszą 1, 2 lub 3 jednostki. Paleta ma
rozmiar 3x3 jednostki (zob. rys.1). Bloki układane są warstwami. Każda
warstwa musi być zapełniona całkowicie i zabezpieczona izolatorem.
Pracownik sterujący ładowaniem układa izolator po ułożeniu każdej
warstwy. Po ułożeniu 3 warstw gotowa paleta jest wysyłana
transporterem. Rys.2 pokazuje przykładowe wypełnienie, w którym
występują pojedyncze elementy o rozmiarach 3 i 2 oraz 4 elementy o
rozmiarze 1.
| | XXXXXXXX OO|**|**
--+--+-- --+--+-- OO+--+--
| | **|**|OO OO|**|OO
--+--+-- --+--+OO --+--+OO
| | **|**|OO **|**|OO
Rys. 1 Rys. 2 Rys. 3
Dodatkowym ograniczeniem przy układaniu bloków jest ich masa.
Bloki o długościach 1, 2 i 3 mają odpowiednio masę m1=1, m2=3 i m3=5
jednostek. Najniższa warstwa na palecie może mieć maksymalną sumaryczną
masę M1=14 jednostek, warstwa druga M2=13 jednostek, a najwyższa
warstwa M3=11 jednostek. Układ bloków z rys. 2 może więc znaleźć się w
warstwie 1 lub 2, ale nie w 3 (sumaryczna masa
M=1*5+1*3+4*1=12>11=M3). Rys.3 pokazuje przykładowe poprawne
wypełnienie warstwy 3 (M3=11).
Korzystając z możliwości jakie dają semafory występujące w systemach
uniksowych (IPC) przedstaw schematycznie programy modelujące
pracowników ładujących bloki 1, 2, 3 i pracownika sterującego
załadunkiem. Algorytm zapisz za pomocą operacji P(S,x), V(S,x) i I(S,x)
realizujących odpowiednio: opuszczenie, podniesienie semafora S o
wartość x i inicjację semafora.
|