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

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

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

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

    1. Nie posiada żadnej jednostki zasobu R
    2. Nie posiada żadnej jednostki zasobu R, żąda jednej jednostki zasobu R
    3. Posiada jedną jednostkę zasobu R
    4. Posiada jedną jednostkę zasobu R, żąda drugiej jednostki zasobu R
    5. Posiada dwie jednostki zasobu R
    6. Posiada dwie jednostki zasobu R, żąda trzeciej jednostki zasobu R
    7. 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

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

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


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



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