Knowledge & Learning

home *** CD-ROM | disk | FTP | other *** search

/ Knowledge & Learning / WISS_LERN.iso / doslern / computer / educard / bs___1.edu < prev next >

Wrap

Text File | 1992-03-19 | 58.7 KB | 2,249 lines

97 BS___1 Diplomprüfung Informatik (Teil 1 von 7) Teilprüfung Betriebssysteme Thema: Speicherverwaltung zusammengestellt von Andreas Smoor Das Programm soll der Kontrolle, nicht der Erarbeitung des Stoffes für die Diplomprüfung Betriebssysteme dienen. Die Fragen wurden mit Hilfe eines Vorlesungsscripts von Martin Kohnen an der UNI Koblenz erstellt. ACHTUNG: Der Menüpunkt "Lexikon - BS-Alphabet" enthält ein Nachschlagewerk mit Begriffen zum Thema Betriebssysteme ! März 1992 Definieren Sie den Begriff Die Abbildung von logischen Variablennamen Mapping ! auf physik. Speicheradressen wird als Mapping bezeichnet. 2 Speicherverwaltung 1 1 Mapping - 1 20000001 Mapping erfolgt in drei Die drei Phasen beim Mapping: Phasen. Welchen ? - Compiler - Linker - Lader 2 Speicherverwaltung 1 1 Mapping - 2 20000002 Welche Aufgabe übernimmt der Der Compiler erzeugt aus den Compiler beim Mapping ? Namen der Datenobjekte relative Adressen. 2 Speicherverwaltung 1 1 Mapping - Compiler 20000003 Welche Aufgabe übernimmt Der Linker fügt einzelne Module zusammen, so daß sich der Linker beim Mapping ? deren Adreßräume nicht mehr überdecken und erzeugt so einen einzigen virtuellen Adreßraum. 2 Speicherverwaltung 1 1 Mapping - Linker 20000004 Welche Aufgabe übernimmt der Der Lader bildet die virtuellen Adressen entweder Lader beim Mapping ? - statisch (im voraus) oder - dynamisch (während der Laufzeit) auf die physikalischen Adressen ab. 2 Speicherverwaltung 1 1 Mapping - Lader 20000005 Geben Sie verschiedene Speichervergabestrategien: a) Einprogrammbetrieb Formen der b) Aufteilung des Speichers in disjunkte Bereiche Speicherverwaltung an ! fester Länge c) wie b) aber verschiebbar d) virtuelle Verwaltung 2 Speichervergabe 1 1 Speichervergabe 20000006 Bei einem virtuellen Speicher Die zweistufige Hierarchie beim virtuellen Speicher ist spricht man von gegeben durch: zweistufiger Hierarchie. - Primärspeicher (Arbeits-) - Sekundärspeicher Wieso ? (Hintergrundspeicher) 2 virtueller Speicher 1 1 virtueller Speicher - 1 20000007 Was sind die zwei Gründe für Die Gründe für die Verwendung von Primär- und Sekundär- die Zweiteilung des speicher liegen in den unter- schiedlichen Zugriffszeiten virtuellen Speichermodells ? (1/1000000 zu 1/100) und der unterschiedlichen Kapazität der Speicher. 2 virtueller Speicher 1 1 virtueller Speicher - 2 20000008 Erklären Sie die Adreß- Adreßberechnung beim virtuellen Speichermodell: berechnung beim virtuellen logische Namen -> virtuelle Adressen (VA) -> Speichermodell. VA des Sekundärspeichers -> dynamische Adressen des Arbeitsspeichers 2 virtueller Speicher 1 1 virtueller Speicher - 3 20000009 Was versteht man bei Page oder Seite ist ein virtueller Adressierung Speicherblock fester Länge. unter dem Begriff Page ? 2 virtueller Speicher 1 1 Page 20000010 Was versteht man bei Segment = virtueller Adressierung logisch zusammenhängender unter einem Speicherblock variabler Segment ? Länge. 2 virtueller Speicher 1 1 Segment 20000011 Virtuelle Adressierung Virtuelle Adressierung stellt eine Abbildung dar: f : virtuelle Adresse -> f : virtuelle Adresse -> ... physikalische Adresse Ergänzen Sie ! 2 virtueller Speicher 1 1 virtuelle Adressierung 20000012 Wie bearbeitet die Zugriff auf virtuelle Adresse - Interrupt erzeugen Speicherverwaltung den - falls Arbeitsspeicher voll Segment oder Seite (SoS) Zugriff auf eine auf Hauptspeicher ablegen - SoS mit a in den AS holen virtuelle Adresse a ? - Prg.Aufnahme, Zugriff auf a 2 virtueller Speicher 1 1 Speicherzugriff 20000013 Was versteht man bei Das Auswahlverfahren, welcher virtueller Adressierung unter Speicherblock vom Arbeits- in den Hauptspeicher abgelegt replacement policy ? wird, wird als replacement policy bezeichnet. 2 virtueller Speicher 1 1 replacement policy 20000014 Was versteht man bei Das Auswahlverfahren, an welche Stelle des Arbeits- virtueller Adressierung unter speichers ein Speicherblock des Hauptspeicher kopiert placement policy ? wird, wird als placement policy bezeichnet. 2 virtueller Speicher 1 1 placement policy 20000015 Was bezeichnet man bei Das Entscheidungsverfahren, virtueller Speicherver- wann ein Segment oder eine waltung als Seite vom Hintergrund- in den Arbeitsspeicher fetch policy ? geladen wird, wird als fetch policy bezeichnet. 2 virtueller Speicher 1 1 fetch policy - 1 20000016 Welche zwei grundsätzlichen fetch policy: fetch-Strategien beim Zugriff Nachladen auf eine virtuelle Adresse a - on demand lassen sich unterscheiden ? bei Zugriff auf a und a nicht im Arbeitsspeicher - on advance auf Verdacht (im voraus) 2 virtueller Speicher 1 1 fetch policy - 2 20000017 Nennen Sie Probleme bei der - Ineffizienz, falls Zugriff auf Seiten in ungünstiger virtuellen Speicher- Reihenfolge geschieht - Ineffizienz beim Nachladen verwaltung ! ausgelagerter Programme - Thrashing (Seitenflattern) - Fragmentierung 2 virtueller Speicher 1 1 virtuelle Speicherverwaltung 20000018 Erläutern Sie den Begriff Unter Thrashing versteht man eine Quasi-System-Stillstand bedingt durch ständiges Ein- Thrashing ! und Auslagern von Seiten (Seitenflattern). Worst: Zugriff immer auf die Seite, die gerade ausgelagert wurde. 2 virtueller Speicher 1 1 Thrashing - 1 20000020 Die Umrechnung der Die virtuelle Adresse bei virtuellen in eine physikal. Segmentierung besteht aus Adresse erfolgt bei Segmen- - Segmentnummer (Index für tierung mit Hilfe einer einen Eintrag der Segment- Segmenttabelle. Die virtuelle tabelle) Adresse besteht aus zwei - relative Adresse im Segment Teilen. Welchen ? (offset, displacement) 2 Speicherorganisation 1 1 Segmentierung - 1 20000021 Die virtuelle Adresse enthält Die Segmenttabelle enthält eine Segmentnummer, die auf - Anfangsadressen der einen Eintrag in der Segment- Segmente im Arbeitsspeicher tabelle verweist. (Basisadresse) - Größe der Segmente Was enthält dieser Eintrag ? - Status (Segment geladen ?) - Zugriffsart ??? 2 Speicherorganisation 0 1 Segmenttabelle 20000022 Nennen Sie zwei Vorteile Segmentierung Vorteile: der Segmentierung gegenüber - Unterstützung der Programmstruktur Paging. - effiziente Speicherausnutzung 2 Speicherorganisation 0 1 Segmentierung - 2 20000023 Beim Paging werden Arbeits- Die Seitengrößen beim und Sekundärspeicher in Paging liegen in einem Seiten der selben Größe ein- Bereich von etwa geteilt. In welchem Größenbereich 256 Byte bis 4 kByte. liegen diese Seiten in der Praxis ? ( ¼ - 4 kByte ) 2 Speicherorganisation 0 1 Paging - 1 20000024 Nennen Sie Vor- und Nachteil Die Verwendung kleiner Seiten beim Paging bringt kleiner Seiten beim - den Vorteil Paging ! geringer Fragmentierung - den Nachteil hoher Seiten-Transfer-Rate 2 Speicherorganisation 0 1 Paging - 2 20000025 Wie nennt man die Die Zerstückelung eines größeren, zusammenhängenden Z e r s t ü c k e l u n g Speicherbereichs in mehrere kleinere Bereiche nennt man des Speichers ? Fragmentierung. 2 Speicherorganisation 0 1 Speicherverwaltung - 1 20000026 Woraus besteht die Paging virtuelle Adresse beim virtuelle Adresse = Paging ? - Seitennummer und - offset (relative Adresse) 2 Speicherorganisation 0 1 Paging - 3 20000027 Nennen Sie Vor- und Nachteil Paging des Paging gegenüber Vorteil: einfache Adreßberechnung der Segmentierung ! Nachteil: größere Fragmentierung 2 Speicherorganisation 1 1 Paging - 4 20000028 Beim Paging wird eine Paging - Seitentabelle Seitentabelle verwendet. - Kachel-Anfangsadresse = Seitenrahmen im Was enthält sie ? Arbeitsspeicher - Status (Page im AS ja/nein) - Zugriffsart ??? 2 Speicherorganisation 0 1 Seitentabelle 20000029 Wie wird der virtuelle Der virtuelle Speicher wird Speicher aufgeteilt, falls aufgeteilt in Segmente, Paging und Segmentierung diese werden in Seiten gleichzeitig verwendet aufgeteilt. werden ? Der Arbeitsspeicher wird in Kacheln (Seitenrahmen) aufgeteilt. 2 Speicherorganisation 0 1 Speicherverwaltung - 2 20000030 Einfügen und Löschen von Einfügen und Löschen von Segmenten kann die Anzahl der Segmenten kann die Anzahl der Löcher im Speicher jeweils - erhöhen Löcher im Speicher jeweils... - unverändert lassen - erniedrigen Ergänzen Sie den Satz ! 2 Speicherorganisation 0 1 Fragmentierung - 2 20000031 Nennen Sie die zwei Voraussetzungen für 50% Regel 1. Speicherverwaltungssystem Voraussetzungen für die erzeugt unregelmäßige Fragmentierung 50 % Regel von Knuth. 2. Speicherverwaltungssystem befindet sich im Gleich- gewicht 2 Speicherorganisation 1 1 50 % Regel - 1 20000032 Eine Voraussetzung der Gleichgewicht bei 50 % Regel: 50 % Regel besagt, daß das 1. Zahl der vom Programm noch Speicherverwaltungssystem verwendeten und die der sich im Gleichgewicht freien Blöcke ist konstant befindet. 2. Speicherzuweisungen und Speicherfreigaben halten Was ist damit gemeint ? sich die Waage 2 Speicherorganisation 0 1 50 % Regel - 2 20000033 Ein Speicherverwaltungssystem Falls p = Wahrscheinlichkeit, enthalte BEL belegte und FREI daß kein passend großer Block freie Speicherblöcke und es für eine Speicheranforderung befinde sich im Gleich- da ist, also ein Block aufge- gewicht. spalten werden müßte, dann ist Zahl der freien Blöcke: Was besagt die 50 % Regel ? FREI ≈ ½ * p * BEL 2 Speicherorganisation 0 1 50 % Regel - 3 20000034 Wie kommt die 50 % Regel Die 50 % Regel heißt so, weil für p = 1 die Zahl der zu ihrem Namen ? freien Blöcke etwa 50 % der der belegten Blöcke beträgt. 2 Speicherorganisation 1 1 50 % Regel - 4 20000035 Die Positionierungsstrategie Positionierungsstrategien: (placement policy) besteht in der Auswahl eines Loches - best fit geeigneter Größe. - worst fit - first fit Nennen Sie vier Strategien ! - buddy system 2 Speicherorganisation 1 1 Positionierungsstrategie 20000036 Was versteht man bei der Jedem Programm wird ein formalen Beschreibung von Referenzstring w zugeordnet, Paging-Strategien unter mit w = r1, r2, ..., rt einem Dabei gibt rt = i den Zugriff auf die Seite i zum Zeitpunkt Referenzstring ? t der Laufzeit des Programmes an. 2 Paging-Strategien 1 1 Referenzstring 22000037 Ein Referenzstring Jeder Speicherzustand Si ist w = r1, r2, ..., rt bestimmt durch die Menge der entspricht einer Folge von Seiten eines Programms, die Speicherzuständen sich zur Zeit t im Arbeits- So, S1, ..., St. speicher befinden. Wodurch wird ein Zustand Si bestimmt ? 2 Paging-Strategien 1 1 Speicherzustand - 1 22000038 Geben Sie die Übergangs- Speicherzustand S(t) = S(t-1) + X(t) - Y(t) funktion für Speicher- X(t) = Menge der neu zustände beim Paging an. geladenen Seiten Y(t) = Menge der ersetzten ( ohne Kontrollzustand ) Seiten 2 Paging-Strategien 1 1 Speicherzustand - 2 22000039 Wozu dient ein Kontroll- Um X(t) und Y(t) zu jedem Zeitpunkt t bestimmen zu zustand Q(t) in einem können, benötigt der Paging- Algorithmus Informationen, Paging-Algorithmus ? die er in den Kontroll- zuständen festhält. 2 Paging-Strategien 1 1 Kontrollzustand 22000040 Ein Paging Algorithmus A Paging Algorithmus: ist definiert durch einen S (t) : Speicherzustand 6-Tupel: Q (t) : Kontrollzustand S (o) : Ausgangszustand von S A = ( S(t), Q(t), S(o), Q(o), Q (o) : Ausgangszustand von Q g, m ) g : Übergangsfunktion Erläutern Sie ! m : Anzahl Seitenrahmen 2 Paging-Strategien 1 1 Paging Algorithmus 22000041 Wann spricht man von einem Bei einem Demand-Paging- Algorithmus werden die Seiten Demand-Paging-Algorithmus ? erst auf Verlangen (on demand) ersetzt. 2 Paging-Strategien 1 1 Demand Paging Algorithmus 22000042 Was besagt die Die Vorwärtsdistanz d(t, x) einer Seite x zum Zeitpunkt t Vorwärtsdistanz ist der zeitliche Abstand zum nächsten Zugriff auf x im Zusammenhang mit Paging ? nach dem Zeitpunkt t. 2 Paging-Strategien 1 1 Vorwärtsdistanz 22000043 Was besagt die Die Rückwärtsdistanz b(t, x) einer Seite x zum Zeitpunkt t Rückwärtsdistanz ist der zeitliche Abstand zum letztmaligen Zugriff auf x im Zusammenhang mit Paging ? vor dem Zeitpunkt t. 2 Paging-Strategien 1 1 Rückwärtsdistanz 22000044 Die Kosten C beim Paging Die Kosten C, die durch einen sind definiert durch einen Paging-Algorithmus A 3-Tupel C (A, m, w). entstehen, der auf einem Referenzstring w arbeitet, Erläutern Sie ! bei einer Speicherkapazität von m Seiten sind festgelegt durch C (A, m, w) 2 Paging-Strategien 0 1 Paging - Kosten 22000045 Wann gilt ein Ein Paging-Algorithmus A ist Paging-Algorithmus als dann optimal, wenn er optimal ? C (A, m, w) für alle m und w minimiert. 2 Paging-Strategien 0 1 Paging Algorithmus, optimaler 22000046 Was wird beim Paging durch F = Seitenfehler- die Wahrscheinlichkeit, bezeichnet die Wahrschein- Seitenfehler- lichkeit, daß eine Seite, auf Wahrscheinlichkeit die zugegriffen werden soll, sich nicht im Arbeitsspeicher ausgedrückt ? befindet. 2 Paging-Strategien 1 1 Seitenfehler-Wahrscheinl. - 1 22000047 Formal ist die Seitenfehler- Die Seitenfehler-Wahrschein- Wahrscheinlichkeit F definiert als lichkeit F ist bestimmt durch C (A, m, w) F (A, m, w) = ───────────── Kosten C, normiert auf die │ w │ Was heißt das ? Länge des Referenzstrings w. 2 Paging-Strategien 1 1 Seitenfehler-Wahrscheinl. - 2 22000048 Nennen Sie Seitenaustausch- Seitenaustausch-Algorithmen: (Ersetzungs-) Algorithmen RANDOM, FIFO, LIFO, LRU, MFU, LFU, Belady und für das Paging. Algorithmus mit Zugriffswahrscheinlichkeit 2 Paging-Algorithmen 1 1 Seitenaustausch-Algorithmen 22000049 Wie groß ist bei einem Bei einem RANDOM-Algorithmus RANDOM-Ersetzungs-Algorithmus ist die Wahrscheinlichkeit P die Wahrscheinlichkeit P dafür, daß eine Seite im dafür, daß eine Seite i im Arbeitsspeicher fehlt: Arbeitsspeicher fehlt ? m m = Anzahl Seitenrahmen P [Seite fehlt] = 1 - ─── n = Seiten des Programms n 2 Paging-Algorithmen 1 1 RANDOM-Algorithmus - 1 22000050 Was bedeutet die Aussage: Lokalität nennt man das Verhalten eines Programmes, "Programme verhalten sich daß während eines Zeitinter- während ihrer Laufzeit valls Zugriffe fast aus- überwiegend lokal." schließlich nur auf eine Teilmenge der Seiten des ? Programms erfolgen. 2 Paging-Algorithmen 1 1 Lokalität - 1 22000051 Warum hat der Der RANDOM-Algorithmus hat einen schlechten Wirkungs- RANDOM-Algorithmus grad, weil kreuz und quer im Speicher herumgesprungen einen schlechten wird, das heißt, Lokalitäten werden nicht beachtet. Wirkungsgrad ? 2 Paging-Algorithmen 1 1 RANDOM-Algorithmus - 2 22000052 Beim FIFO-Algorithmus Der Nachteil beim FIFO- (first in, first out) wird Algorithmus ist, daß nicht die Seite ersetzt, die die auf die Zugriffshäufigkeit längste Zeit im Arbeits- der Seiten geachtet wird. speicher war. Was ist der Nachteil dabei ? 2 Paging-Algorithmen 1 1 FIFO-Algorithmus 22000053 Was versteht man unter der Vergrößert man die Anzahl der Seitenrahmen für ein Programm im Arbeitsspeicher, FIFO-Anomalie ? so erwartet man eine Ver- ringerung der Seitenfehler- Wahrscheinlichkeit. Manchmal erfolgt genau das Gegenteil ! 2 Paging-Algorithmen 1 1 FIFO-Anomalie 22000054 Nennen Sie eine Konsequenz Bei einer Seitenrahmen- kapazität m bleiben die des LIFO-Algorithmus ersten m-1 Seiten ständig im Arbeitsspeicher. (last in, first out) ! 2 Paging-Algorithmen 1 1 LIFO-Algorithmus - 1 22000055 Beschreiben Sie das Beim LRU-Algorithmus (last recently used) wird Prinzip des LRU-Algorithmus. die Seite ersetzt, die die größte Rückwärtsdistanz hat. Merkhilfe: Lange Ruhen -> Uninteressant 2 Paging-Algorithmen 1 1 LRU-Algorithmus 22000056 Erklären Sie das Prinzip Beim MFU-Algorithmus (most frequently used) wird beim MFU-Algorithmus. die Seite ersetzt, auf die am häufigsten zugegriffen wurde. 2 Paging-Algorithmen 1 1 MFU-Algorithmus 22000057 Was ist die Idee beim Beim LFU-Algorithmus (least fequently used) wird LFU-Algorithmus ? die Seite ersetzt, auf die am wenigsten zugegriffen wurde. 2 Paging-Algorithmen 1 1 LFU-Algorithmus 22000058 Was ist die Idee beim Beim Belady-Algorithmus wird die Seite ersetzt, die die Belady-Algorithmus ? größte Vorwärtsdistanz auf- weist. Der Belady-Algorithmus ist optimal. 2 Paging-Algorithmen 1 1 Belady-Algorithmus - 1 22000059 Warum ist der Der Belady-Algorithmus ist praktisch nicht anwendbar, Belady-Algorithmus weil er die genaue Kenntnis des Referenzstrings praktisch nicht anwendbar ? erfordert. Die Analyse der Zukunft (look-ahead) ist aber zu aufwendig. 2 Paging-Algorithmen 1 1 Belady-Algorithmus - 2 22000060 Nennen Sie einen typischen Der LIFO-Algorithmus Referenzstring, bei dem der unterstützt Schleifen. LIFO-Algorithmus optimales Ein Referenzstring Verhalten aufweist. w = abcabcabc würde deshalb bei einer Seitenrahmen- hier LIFO = kapazität von m=2 optimal zuletzt referierte Seite abgearbeitet werden. 2 Paging-Algorithmen 1 1 LIFO-Algorithmus - 2 22000061 Ein Programm zeigt Ein Programm zeigt stationäres Verhalten, stationäres Verhalten, wenn wenn... die Zukunft beim Zugriff auf Seiten genauso aussieht wie Bitte den Satz ergänzen ! die Vergangenheit. 2 Paging-Algorithmen 1 1 stationäres Verhalten - 1 22000062 Welcher Ersetzungs- Da beim stationären Verhalten Ersetzungs-Algorithmus eines Programms gilt, daß ist bei stationärem Verhalten Vorwärts- = Rückwärtsdistanz, eines Programms besonders ist der LRU-Algorithmus hier günstig ? am günstigsten. (Er ist sogar optimal.) 2 Paging-Algorithmen 1 1 stationäres Verhalten - 2 22000063 Beim Ersetzungs-Algorithmus Beim Ersetzungsalgorithmus mit Zugriffswahrscheinlich- mit Zugriffswahrscheinlich- keit werden in einem Zeit- keit wird immer die Seite intervall die Zugriffswahr- mit der scheinlichkeiten gemessen. geringsten Ersetzt wird dann immer Zugriffswahrscheinlichkeit welche Seite ? ersetzt. 2 Paging-Algorithmen 0 1 Zugriffswahrscheinlichkeit 22000064 Zeichnen Sie ein Diagramm, F 1\ das die Seitenfehler-Wahr- │ * \ scheinlichkeit für RANDOM (\) │ * \ und sonstige Algorithmen (*) ½ * \ bei steigender Seitenrahmen- │ * \ kapazität m verdeutlicht. │ * * *\ m └─────½n────────n─────────> 2 Paging-Kosten 1 1 Seitenfehler-Wahrscheinl. - 3 22000065 Es gibt für die Seiten- Wenn die Seitenrahmen- rahmen-Kapazität m eine Kapazität des Arbeits- Untergrenze, unterhalb derer speichers, weniger als die auch der Belady-Algorithmus Hälfte der Seiten des unzumutbar große Seitenfehler Programms umfaßt, gibt es produziert. Wo liegt diese immer unzumutbar große Genze in etwa ? Seitenfehler. 2 Paging-Kosten 1 1 Ersetzungs-Algorithmen 22000066 Wie kann schon der Zum Beispiel, indem er zwei- Programmierer Einfluß auf dimensionale Arrays, die von die Seitenfehler- dem verwendeten Compiler Wahrscheinlichkeit nehmen ? zeilenweise abgespeichert werden, auch zeilenweise durchläuft (und nicht spaltenweise). 2 Paging-Kosten 0 1 Seitenfehler-Wahrscheinl. - 4 22000067 Wie kann schon der Compiler Zum Beispiel, indem er Einfluß auf die Seitenfehler- Programmschleifen so Wahrscheinlichkeit nehmen ? zusammenfaßt, daß sie sich auf möglichst wenige Seiten erstrecken, auch wenn dadurch Platz vergeudet wird. 2 Paging-Kosten 1 1 Seitenfehler-Wahrscheinl. - 5 22000068 Was versteht man unter der Wenn unter dem verwendeten Algorithmus A immer gilt: Einschließungseigenschaft S (A, m, w) ist Teilmenge von S (A, m + 1, w), dann erfüllt von Ersetzungsalgorithmen ? A die Einschließungseigen- schaft. 2 Stackalgorithmen 0 1 Einschließungseigenschaft - 1 22000069 Was folgt direkt aus der Falls die Seite X nicht Element von S (A, m + 1, w), Einschließungseigenschaft so ist sie auch nicht Element von S (A, m, w). Die Seiten- eines Ersetzungsalgorithmus ? fehlerwahrscheinlichkeit F vergrößert sich also nicht bei mehr Seitenrahmen m. 2 Stackalgorithmen 0 1 Einschließungseigenschaft - 2 22000070 Wann nennt man einen Ein Ersetzungsalgorithmus A wird als Stackalgorithmus Ersetzungsalgorithmus einen bezeichnet, wenn die Speicherzustände S für alle m Stackalgorithmus ? und für alle w die Einschließungseigenschaft besitzen. 2 Stackalgorithmen 0 1 Stackalgorithmus - 1 22000071 Nennen Sie einen Wegen der FIFO-Anomalie ist Ersetzungsalgorithmus, der der FIFO-Algorithmus kein keinen Stackalgorithmus Stackalgorithmus. darstellt. 2 Stackalgorithmen 0 1 Stackalgorithmus - 2 22000072 Wozu dient das Das IRM dient zur Bestimmung der Leistung von Ersetzungs- Independent Reference Model algorithmen, die sich in Erwartungswerten für (IRM) ? Seitenfehler ausdrückt. 2 IRM 1 1 IRM - 1 22000073 Beim IRM wird davon ausge- Es gilt, daß für gangen, daß der Referenz- w = r(1)...r(t)... die string w eine Folge unabhän- Wahrscheinlichkeit giger Zufallsvariablen ist, P [r(t) = i] = ß(i) ist, d.h. mit einer konstanten Vertei- die Zugriffswahrscheinlich- lung {ß(1), ß(2), ..., ß(n)}. keit auf die Seite i zum Was gilt für die Verteilung ? Zeitpunkt t ist ß(i). 2 IRM 1 1 IRM - 2 22000074 Sei d(t, X) die Zufalls- P [d(t, X) = K] variable, die die Vorwärts- = P [r(t + 1) <> X] * distanz der Seite X nach dem P [r(t + 2) <> X] * ... * Zugriff r(t) angibt. Es gilt P [r(t + K - 1) <> X] * dann: P [d(t, X) = K] = P [r(t + K) = X] K-1 = (1 - ß(X) hoch (K - 1) * (1 - ß(X)) * ß(X). Wieso ? ß(X) 2 IRM 1 1 IRM - 3 22000075 Wie groß ist die mittlere Beim Independent Reference Model beträgt die mittlere Vorwärtsdistanz beim IRM ? Vorwärtsdistanz _______ 1 d(t, X) = ────── ß(X) 2 IRM 1 1 IRM - 4 22000076 Im IRM läßt sich ein Unter der Voraussetzung, daß Ersetzungsalgorithmus A° die Referenzen der Seiten angeben, der immer die Seite (die Zugriffe auf sie) im Arbeitsspeicher ersetzt, unabhängig voneinander sind, die die größte zu erwartende minimiert A° die Kosten Vorwärtsdistanz aufweist. C (A°, m) für alle m > 0. Wann ist A° optimal ? 2 IRM 1 1 IRM - 5 22000077 Wie groß ist die Seiten- F (A°, m) = fehlerwahrscheinlichkeit F 1 n für den Ersetzungs- B - ─── * Σ ß(i)² algorithmus A° im IRM ? B i=m n m = Anzahl Seitenrahmen mit B = Σ ß(i) n = Seiten eines Programms i=m 2 IRM 1 1 IRM - 6 22000078 Beim Multiprogramming Beim Multiprogramming gibt es (Mehrprogrammbetrieb) wird zu jedem Zeitpunkt t eine der Arbeitsspeicher der Einteilung Z(t) des Speichers Größe M unter den Programmen Z(t) = (Z1(t) Z2(t)...Zn(t)), variabel aufgeteilt. wobei Zi(t) die Menge der Seiten des i-ten Programms Wie ist das gemeint ? angibt. 2 Working-Set 1 1 Multiprogramming - 1 22000079 Welche Bedingungen gelten Bedingungen: 1. Vereinigung aller Seiten immer bei der Aufteilung des der Programme zum Zeitpunkt t ist ≤ M Speichers beim (M = Arbeitsspeichergröße) 2. Die Speicherbereiche der Multiprogramming ? Programme sind disjunkt. 2 Working-Set 1 1 Multiprogramming - 2 22000080 Wie lautet die Der Working-Set W eines Programmes zum Zeitpunkt t Definition für den ist die Menge der Seiten im Arbeitsspeicher, auf die im Working-Set W Zeitintervall [t - T + 1, t] referiert (zugegriffen) eines Programmes ? wurde. 2 Working-Set 1 1 Working-Set - 1 22000081 Wieso spricht man beim Die T heißt Window-Größe, weil man sich den Working-Set Working-Set von einer bildlich als ein Fenster vorstellen kann, durch das "Window-Größe" T ? man auf einen Ausschnitt des Referenzstrings schaut. 2 Working-Set 1 1 Working-Set - 2 22000082 Was kann man sich intuitiv Intuitiv ist der Working-Set die kleinste Menge von Seiten unter einem Working-Set im Arbeitsspeicher, die ausreicht, damit ein Programm vorstellen ? effizient laufen kann. 2 Working-Set 1 1 Working-Set - 3 22000083 Eine charakteristische Größe des Working Sets stellt w (t, T) = │ W (t, T) │ die Anzahl der Seiten w dar, die zum Working Set gehören. Anzahl der Seiten w, die zum Geben Sie die formale Zeitpunkt t zum Working-Set W Schreibweise dafür an. der Window-Größe T gehören 2 Working-Set 0 1 Working-Set - 4 22000084 Eine charakteristische h (z, T) = P [w (t, T) = z] Größe des Working-Sets stellt die Wahrscheinlichkeits- = der Wahrscheinlichkeit, daß funktion h der Größe des sich zum Zeitpunkt t bei Working-Sets dar. einer Window-Größe von T genau z Seiten im Wie ist h definiert ? Working-Set befinden 2 Working-Set 0 1 Working-Set - 5 22000085 Eine charakteristische n Größe des Working-Sets stellt s (T) = Σ z * h (z, T) die mittlere Größe des z=1 Working-Sets s dar. = lim E [w (t, T)] Geben Sie die formale t->∞ Definition für s an. 2 Working-Set 0 1 Working-Set - 6 22000086 Eine charakteristische m (T) = Missing (T) = Größe des Working-Sets stellt die Wahrscheinlichkeit m für lim P [r(t+1) nicht Element das Fehlen einer Seite im t->∞ Working-Set dar. von W (t, T)] Wie ist m definiert ? 2 Working-Set 0 1 Working-Set - 7 22000087 Warum kann man die Es kann vorkommen, daß eine Seitenfehler-Wahrscheinlich- Seite aus dem Working-Set keit mit den Größen des herausfällt, ohne jedoch den Working-Sets nur abschätzen? Arbeitsspeicher verlassen zu haben. 2 Working-Set 0 1 Working-Set - 8 22000088 Mit Hilfe des Working-Sets Die obere Grenze für die läßt sich eine obere Grenze für die zu erwartende Seitenfehler-Wahrscheinlich- Seitenfehler-Wahrscheinlich- keit F angeben. keit F liegt bei m (T). Wo liegt diese Grenze ? 2 Working-Set 0 1 Working-Set - 9 22000089 Was besagt die Aussage s (T) ist nach oben und 1 ≤ s (1) ≤ s (T) unten beschränkt und hat ≤ s (T + 1) ≤ min {n, T + 1} eine Steigung größer gleich in bezug auf den Working-Set? Null. 2 Working-Set 0 1 Working-Set - 10 22000090 Was besagt die Aussage Die Steigung von s (T) ist s (T + 1) - s (T) = m (T) die Wahrscheinlichkeit für in bezug auf den Working-Set? das Fehlen einer Seite im Working-Set m (T). 2 Working-Set 0 1 Working-Set - 11 22000091 Was besagt die folgende Die mittlere Größe ist nach Aussage in bezug auf den oben durch n beschränkt. Working-Set ? Trivial, da nie mehr Seiten lim s (T) = n im Working-Set sein können, T->∞ als das Programm hat. 2 Working-Set 0 1 Working-Set - 12 22000092 Was bedeutet die folgende m (T) ist nach oben und Aussage in bezug auf den Working-Set ? unten beschränkt und hat 0 ≤ m (T+1) ≤ m (T) eine Steigung kleiner ≤ m (0) = 1 gleich Null. 2 Working-Set 0 1 Working-Set - 13 22000093 Bei vielen Multiprogramming- Die Systeme arbeiten bis zu Systemen mit Paging-Speicher- einer im allgemeinen nicht verwaltung beobachtet man festen Grenze von n gleich- ein Phänomen, das man zeitig ablaufenden Programmen Thrashing nennt. effizient. Diese Verhalten ändert sich schlagartig bei Was versteht man darunter ? n + 1 Programmen. 2 Thrashing 1 1 Thrashing - 2 22000094 Wieviel Platz im Die Anzahl der Seiten, die Arbeitsspeicher sollte einem einem Programm i im Arbeits- Programm mindestens einge- speicher zugestanden werden räumt werden, damit es sollte, darf die mittlere einigermaßen effizient Größe des Working-Sets ablaufen kann ? s (i, T) nicht unterschreiten. 2 Wieso ? T ist doch ein rein theoretischer Wert ??? Thrashing 0 1 Thrashing - 3 22000095 Erläutern Sie den Begriff Bei nicht seitenverwalteten Speichersystemen tritt durch dynamische Anforderung und Fragmentierung. Freigabe von Hauptspeicher eine Zerstückelung des Speicherraums auf, die man Fragmentierung nennt. 2 virtueller Speicher 1 1 Fragmentierung - 1 20000019 Nennen Sie drei Gründe dafür, - Instruktionsfolgen sind überwiegend sequentiell. daß Programme während - Schleifen werden vom Compiler auf Seiten ihrer Laufzeit Lokalitäten zusammengefaßt. - Programme sind modular aufweisen. aufgebaut. 2 Working-Set 0 1 Lokalität - 2 22000999 Der jeweilige Kontext zu Bitte probieren Sie es gleich den Fragen wird angezeigt, einmal aus und drücken die wenn man nach der Taste "i", sobald die Beantwortung einer Frage Möglichkeit dazu in der Statuszeile, der untersten die Taste "i" für mehr Zeile, angegeben wird. Information drückt ! 2 Speicherverwaltung 1 1 WICHTIGER HINWEIS ! 0