Übung zu Seiten-/Seitenrahmenersetzung (1)
gegeben: Main-Programm inclusive Verwaltungsroutinen: 3 KB
Funktion F 3
KB
Funktion FUN 2,5
KB
Speicherbereiche für REAL-Konstanten im
Main: 1KB
Speicherbereiche für REAL-Arrays A,B,C[1..1000]: 12KB
Virtueller
Adressraum insgesamt: 21,5KB
Quelltext-Auszug:
...
X := exp (az); T:=0; S:=0;
for I:=1 to 1000 do
begin
A[I] := F(K,I);
B[I] := FUN(X);
C[I] := 0.;
S := S + A[I];
T := T + B[I];
end;
for I:=1 to 1000 do
begin
A[I] := A[I] / S;
B[I] := B[I] / T;
end;
…
(a) Wieviele
Seitenrahmenersetzungen werden durchgeführt, wenn:
Physikalischer
Adressraum begrenzt auf 4 x 4 KB = 16 KB:
2 Seitenrahmen für Programm-Text
2 Seitenrahmen für Daten,
davon 1 Seitenrahmen für Konstanten
und 1 Seitenrahmen für Arrays
Seitengröße =
Seitenrahmengröße = 4 KB
(b) Wie kann der bezüglich Rechenzeit optimale Programm-Ablauf aussehen, wieviele Seitenrahmenersetzungen gibt es dann noch?
Übung zu
Seiten-/Seitenrahmenersetzung (2)
System mit 4
Seitenrahmen
Zeitpunkt des Ladens,
des letzten Zugriffs und die R und M Bits (Referenz bzw. Modifikation) für die
Seiten 0,1,2,3:
Seite geladen letzte
Referenz R M
0 126
249 0 0
1 230
260 1 0
2 120
272 1 1
3 160
280 1 1
Welche
der Seiten wird unter den folgenden Seitenersetzungsverfahren ersetzt, wenn
eine neue, 4. Seite eingelagert werden soll?
- last-in, first-out,
- first-in, first-out,
- not recently used,
(3)
Rechner mit Adreßraum
65536 Byte für jeden Prozeß,
Aufteilung
in Seiten/Seitenrahmen von 4096 Byte,
einzelnes
Programm mit Textgröße von 32768 Bytes,
mit Datengröße von 16386 Bytes
mit Stackgröße von 15870 Bytes.
Paßt dieses Programm in
den Adreßraum?
Paßt dieses Programm in
den Adreßraum,
falls die Seitengröße 512 Byte betragen würde?
(zur Beachtung: eine
Seite enthält nicht Teile verschiedener Segmente)
typischer Seitentabelleneintrag
|
|
cach |
ref. |
mod. |
secu |
pres/abs |
Seitenrahmennummer |
Größe in vielen Systemen 32 Bit
idealer Seitenersetzungsalgorithmus (nicht
realisierbar):
-
Seiten befinden sich im Speicher
-
Markierung einer referenzierten Seite mit Anzahl der bis
dahin ausgeführten Instruktionen
-
Ersetzung der Seite, die die höchste Markierung hat
è unrealistisch, da erst nach Programm-Durchlauf
bekannt
Statusbits R: Seite referenziert (lesend / schreibend)
M: Seite
wurde geschrieben/verändert
Programm-Start: à alle = 0
periodisch werden R-Bits = 0 gesetzt
(àUnterscheidung:
Seite vorher schon referenziert o. nicht)
Aktualisierung bei jeder Speicheroperation
wenn Bit auf
„1“ gesetzt wurde, bleibt es dort
außer
Betriebssystem setzt es per Software zurück
bei Seitenfehler Einteilung der Seiten in 4 Klassen:
(1) nicht
referenziert, nicht modifiziert
(2) nicht
referenziert, modifiziert
(3)
referenziert, nicht modifiziert
(4)
referenziert, modifiziert
à NRU: zufällige Auswahl einer Seite aus kleinster Klasse und Entfernung
Liste aller Seiten
Beginn der Liste enthält älteste Seitennummer
Ende der Liste enthält Nummer der zuletzt eingelagerten
Seite
bei Seitenfehler:
Entfernung des
ersten Eintrages
Hinzufügen des
neuen Eintrages am Ende der Liste
selten in
reiner Form eingesetzt
Liste aller Seiten
Zeiger zeigt auf älteste Seite
bei Seitenfehler:
Inspektion des
R-Bits:
bei R=0: Seite
auslagern, neue Seite hier einfügen
Zeigerposition
1 vorrücken
bei R=1: setze
R=0,
Zeiger
1 vorrücken
Wiederholung,
bis Seite mit R=0 gefunden
Liste aller Seiten
bei Seitenfehler:
oberster
Listeneintrag analysiert:
bei R=0: Seite
auslagern / löschen,
neue Seite
am Ende einfügen
bei R=1: setze
Seiteneintrag an Listenende
setze
R=0
gehe
wieder zu Listenanfang