Zadanie 1

Rozważmy pamięć wirtualną ze stronicowaniem na żądanie. Tablica stron jest przechowywana w rejestrach. Obsługa przerwania braku strony zajmuje 8 milisekund, gdy jest dostępna pusta ramka lub strona usuwana z pamięci nie była modyfikowana i 20 milisekund, gdy usuwana strona była modyfikowana. Czas dostępu do pamięci wynosi 1 mikrosekundę.

Załóżmy, że 70% usuwanych stron to strony, które były modyfikowane. Jaki jest maksymalny akceptowalny współczynnik przerwań braku strony, aby efektywny czas dostępu do pamięci nie przekraczał 2 mikrosekund?

Rozwiązanie


2 mikrosekundy >= (1 - p) * 1 mikrosekunda + p * (0.3 * 8 milisekund + 0.7 * 20 milisekund)
p <= 0.00006

Zadanie 2

Rozważmy następujący ciąg odwołań do stron: 


    4, 5, 3, 1, 4, 5, 2, 4, 5, 3, 1, 2

Zakładając, że dostępna dla procesów pamięć fizyczna składa się z:

  1. 3 ramek,
  2. 4 ramek

które początkowo są wolne, podaj, które strony i w jakiej kolejności zostaną usunięte oraz jaka jest w każdej chwili zawartość pamięci przy zastosowaniu następujących strategii usuwania stron:

  1. LRU,
  2. FIFO,
  3. Algorytm optymalny.

Rozwiązanie

  1. Przypadek 3 ramek:

    1. Algorytm LRU (10 błędów braku strony): 
      
    4  5  3  1  4  5  2  4  5  3  1  2
    *  *  *  *  *  *  *        *  *  *
    4  5  3  1  4  5  2  4  5  3  1  2
       4  5  3  1  4  5  2  4  5  3  1
          4  5  3  1  4  5  2  4  5  3
    2. Algorytm FIFO 9 błędów braku strony): 
      
    4  5  3  1  4  5  2  4  5  3  1  2   
    *  *  *  *  *  *  *        *  *   
    4  4  4  1  1  1  2  2  2  2  2  2
       5  5  5  4  4  4  4  4  3  3  3
          3  3  3  5  5  5  5  5  1  1
    3. Algorytm optymalny (7 błędów braku strony): 
      
    4  5  3  1  4  5  2  4  5  3  1  2
    *  *  *  *        *        *  *  
    4  4  4  4  4  4  4  4  4  4  1  1
       5  5  5  5  5  5  5  5  3  3  3
          3  1  1  1  2  2  2  2  2  2

  2. Przypadek 4 ramek:

    1. Algorytm LRU (8 błędów braku strony): 
      
    4  5  3  1  4  5  2  4  5  3  1  2    
    *  *  *  *        *        *  *  *
    4  5  3  1  4  5  2  4  5  3  1  2
       4  5  3  1  4  5  2  4  5  3  1
          4  5  3  1  4  5  2  4  5  3
             4  5  3  1  1  1  2  4  5
    2. Algorytm FIFO (10 błędów braku strony): 
      
    4  5  3  1  4  5  2  4  5  3  1  2
    *  *  *  *        *  *  *  *  *  *
    4  4  4  4  4  4  2  2  2  2  1  1
       5  5  5  5  5  5  4  4  4  4  2
          3  3  3  3  3  3  5  5  5  5
             1  1  1  1  1  1  3  3  3

      Anomalia Belady'ego: wystąpiło więcej błędów braku strony mimo, że jest więcej dostępnej pamięci.

    3. Algorytm optymalny (6 błędów braku strony): 
      
    4  5  3  1  4  5  2  4  5  3  1  2    
    *  *  *  *        *           *
    4  4  4  4  4  4  4  4  4  4  1  1
       5  5  5  5  5  5  5  5  5  5  5
          3  3  3  3  3  3  3  3  3  3
             1  1  1  2  2  2  2  2  2

Zadanie 3

Pewien proces wygenerował następujący ciąg odwołań do stron: 


     1, 4, 1, 2, 5, 3, 1, 2, 6, 4, 3, 2

Zakładając, że dostępna dla procesów pamięć fizyczna składa się z 4 ramek, które początkowo są wolne, podaj, które strony i w jakiej kolejności zostaną usunięte oraz jaka jest w każdej chwili zawartość pamięci przy zastosowaniu następujących strategii usuwania stron:

  1. LRU,
  2. CLOCK (aproksymacja LRU), czyli algorytm drugiej szansy z cyklicznym przeglądaniem stron (jak w algorytmie FIFO). Po wybraniu strony sprawdza się dodatkowo jej bit odniesienia. Jeżeli jego wartość wynosi 0, to strona jest zastępowana. W przeciwnym przypadku strona dostaje drugą szansę (nie usuwa się jej z pamięci), ale jej bit jest zerowany. Bit odniesienia jest ustawiany na 1 przy każdym odwołaniu do strony.

Rozwiązanie

  1. Algorytm LRU (8 błędów braku strony): 
    
    1  4  1  2  5  3  1  2  6  4  3  2     
    *  *     *  *  *        *  *  *       
    1  4  1  2  5  3  1  2  6  4  3  2   
       1  4  1  2  5  3  1  2  6  4  3   
             4  1  2  5  3  1  2  6  4      
                4  1  2  5  3  1  2  6
  2. Algorytm CLOCK (9 błędów braku strony): 
    
    1  4  1  2  5  3  1  2  6  4  3  2     
    *  *     *  *  *  *     *  *  *
    1. 1. 1. 1. 1. 3. 3. 3. 3. 4. 4. 4.  
       4. 4. 4. 4. 4  1. 1. 1. 1  3. 3.  
             2. 2. 2  2  2. 2. 2  2  2.     
                5. 5  5  5  6. 6  6  6

    . oznacza ustawiony bit

Zadanie 4

Rozważmy następujący ciąg odwołań do stron: 


         2, 4, 3, 4, 4, 4, 3, 4, 2, 1, 5, 2, 5

Podaj zawartość pola roboczego oraz liczbę przerwań braku strony dla wskazanego ciągu odwołań w strategii pola roboczego z okienkiem o rozmiarze:

  1. 3,
  2. 4.

Rozwiązanie

  1. 3 ramki (7 błędów braku strony): 
      
    2  4  3  4  4  4  3  4  2  1  5  2  5                                  
    *  *  *           *     *  *  *     
    2  2  2  4  4  4  4  4  3  4  2  1  5
       4  4  3  3     3  3  4  2  1  5  2
          3                 2  1  5  2
  2. 4 ramki (6 błędów braku strony): 
      
    2  4  3  4  4  4  3  4  2  1  5  2  5                                  
    *  *  *                 *  *  *     
    2  2  2  2  4  4  4  4  4  3  4  2  1
       4  4  4  3  3  3  3  3  4  2  1  5
          3  3              2  2  1  5  2
                               1  5

Zadanie 5

Rozważmy dwuwymiarową tablicę A:


   var A: array [1..page_size] of array [1..page_size] of byte;

Ile przerwań braku strony wygeneruje wykonanie każdego z podanych dwóch algorytmów zerowania tablicy A?


for i:= 1 to page_size do
  for j:= 1 to page_size do
     A[i, j] := 0;

for i:= 1 to page_size do
  for j:= 1 to page_size do
     A[j, i] := 0;

Można założyć, że:

  • Kod pętli zajmuje osobną ramkę i jest na stałe umieszczony w pamięci.
  • Do dyspozycji jest jedna wolna ramka w pamięci operacyjnej.
  • Macierze są alokowane w pamięci wierszami.

Rozwiązanie

Algorytm pierwszy wygeneruje page_size przerwań braku strony, a drugi: page_size2.

Wniosek: struktura programu może mieć istotny wpływ na efektywność wykonywania tego programu w systemie z pamięcią wirtualną.

Zadanie 6

Algorytm WSClock zarządzania pamięcią działa następująco. Jeśli są puste ramki, to przydziela pierwszą wolną. Jeśli nie ma, to przegląda cyklicznie wszystkie ramki (począwszy od miejsca, w którym ostatnio zakończono przeglądanie). Jeśli do strony zapamiętanej w ramce było odwołanie od ostatniego sprawdzenia, to za czas tego odwołania przyjmuje się czas bieżący. Jeśli do strony nie było odwołania od ostatniego sprawdzenia, to można usunąć tę stronę, jeśli od czasu ostatniego sprawdzenia minęło co najmniej T jednostek czasu. Jeśli strona była modyfikowana podczas pobytu w pamięci operacyjnej, to inicjuje się usunięcie strony i szuka się dalej. Jeśli w wyniku przejrzenia wszystkich ramek nie znajdzie się żadnej wolnej, to:

  1. jeśli zostało zainicjowane usunięcie jakiejś strony, to czeka się na zakończenie takiej operacji,
  2. wpp usuwa się jeden z aktywnych procesów.

Dane są następujące deklaracje: 


const lramek = ...;
      maxproc = ...;
      T = ...;

type ramki = 0..lramek-1;
     procesy = 0..maxproc;

function Zegar (i:procesy): real; (* wirtualny zegar procesu *)

procedure UsuńStronę (nrramki: ramki);
(* inicjuje przesłanie strony z danej ramki z pamięci operacyjnej do pomocniczej *)

function CzekajNaRamkę: ramki;
(* wstrzymuje działanie procesu aż do chwili najbliższego zakończenia usuwania
strony z pamięci operacyjnej do pomocniczej - przekazuje numer zwolnionej ramki *)

function UsuńProces: procesy
(* przekazuje numer procesu wyznaczonego do usunięcia *)

Należy zadeklarować wszystkie potrzebne struktury danych oraz napisać procedurę WSClock implementującą strategię zarządzania pamięcią WSClock i przekazującą numer wolnej ramki w pamięci operacyjnej.

Uwaga: jeśli na porządne zapisanie tego algorytmu nie starczy czasu, to przynajmniej należy dokładnie omówić działanie algorytmu WSClock.

Rozwiązanie


type wramki = -1 .. lramek -1; (* wolne ramki; -1 <=> NIL *)

var PaO: array [ramki] of 
            record
              było_odwołanie: boolean;
              czas_odwołania: real;
              modyfikowana: boolean;
              trwa_transmisja: boolean; (* strona jest usuwana, 
                                           była modyfikowana *)
              proces: procesy;
              następna_wolna: wramki;   (* następna wolna *)
            end;
    strzałka: ramki;
    wolna: wramki;      (* wskaĽnik do listy wolnych *)
    usuwane: integer;   (* liczba usuwanych stron zmodyfikowanych;
                           transmisja mogła zostać zainicjowana podczas
                           poprzednich wywołań procedury WSClock *)
    czekający: integer;  (* liczba procesów czekających na stronę *)
    bieżacy_proces: integer;            (* numer bieżącego procesu *)

procedure ZwolnijRamkę (nrramki: ramki);
begin
  PaO[nrramki].następna_wolna := wolna; wolna := nrramki;
  with PaO[nrramki] do
  begin
    proces := 0; trwa_transmisja := false; było_odwołanie := false
  end
end;

procedure WSClock (var nrramki: ramki);
var znaleziono: boolean;
    ostatni: nrramki;
    nrproc: procesy;
begin
  if wolna <> -1 then begin
    nrramki := wolna; wolna := PaO[wolna].następna_wolna
  end
  else begin
    znaleziono := false;
    ostatni := strzałka;
    repeat
      strzałka := (strzałka + 1) mod lramek;
      with PaO[strzałka] do
      if not trwa_transmisja then
        if było_odwołanie then begin
          było_odwołanie := false; czas_odwołania := Zegar(bieżący_proces);
        end
        else if Zegar(bieżący_proces) - czas_odwołania > T then
                if modyfikowana then begin
                  usuwane := usuwane + 1;
                  trwa_transmisja := true;
                  UsuńStronę(strzałka)
                end else begin
                      znaleziono := true;
                      nrramki := strzałka;
                    end
    until znaleziono or (strzałka = ostatni);
  
    if not znaleziono then begin
      if czekający >= usuwane then begin
        nrproc := UsuńProces;
        for ostatni:=0 to lramek-1 do
          with PaO[ostatni] do
          if proces = nrproc then
            if modyfikowana then begin
              trwa_transmisja:=true;
              usuwane := usuwane + 1;
              UsuńStronę(ostatni)
            end
            else ZwolnijRamkę(ostatni);
      end;
      if wolna <> -1 then begin
        nrramki := wolna; wolna := PaO[wolna].następna_wolna
      end
      else begin czekający := czekający + 1; nrramki := CzekajNaRamkę end
    end;
  end
end (* WSClock *)

Dodatkowe pytania:

  1. Dlaczego ta metoda jest jedynie przybliżeniem zasady pola roboczego?
  2. W jakich okolicznościach (w jakich procedurach jądra) będą zmniejszane wartości zmiennych usuwane i czekający?