Pamiec

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?


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

Rozważmy system ze stronicowaniem na żądanie. Pomiary wykonane w systemie wskazują na następujące wykorzystanie różnych urządzeń:

Które z następujących czynności (jeśli w ogóle któreś) mają szansę na poprawienie wykorzystania procesora? Dlaczego?

Oczywiście wykonane pomiary wskazują na to, że mamy do czynienia z sytuacją migotania. Jedynym rozsądnym rozwiązaniem jest zatem zmniejszenie poziomu wieloprogramowości bądź zainstalowanie większej pamięci.


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

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


     1, 4, 1, 2, 5, 3, 1, 7, 8, 9, 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 przy zastosowaniu następujacej strategii usuwania stron oraz jaka będzie w każdej chwili zawartość pamięci:


         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:


   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;

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

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:


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.


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 *)

Scenariusz do ćwiczeń 6 Pamięć wirtualna

Scenariusz do ćwiczeń 6
Pamięć wirtualna