Systemy operacyjne
Główna  Spis treści  Kontakt  O stronie 
:::.:..
Poniżej przedstawiono zadania z egzaminu końcowego (rok 2002/2003). Czas przeznaczony na rozwiązanie zadań wynosił 120 min.
  1. 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

  2. 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

  3. 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

  4. 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

  5. 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.

  6. 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).

  7. 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.


Valid HTML 4.01! Valid CSS!
Copyright © 2001-2003 Zakład systemów informatycznych
Wszelkie prawa zastrzeżone.
Ostatnia aktualizacja:
09/02/2004