Betriebsysteme (Subject) / Hauptspeicherverwaltung (Lesson)

This lesson was created by UF13.

Learn lesson

back  |  next 1 / 1

• Was ist ein Prozess? Was ist der Unterschied zu einem Programm? Ein Prozess ist die konkrete Ausführung eines laufenden Programmes. Definition lt. Skript: Ein ablaufendes Programm bezeichnet man als Prozess, inklusive des aktuellen Wertes des befehlszählers, der Registerinhalte und der Belegung der Variablen. Ein Programm an sich ist etwas statisches, ein Prozess etwas dynamisches. Vgl. Kuchenback-Analogie von Tanenbaum: Rezept=Programm; Mensch=Prozessor; Vorgang des Backens=Prozess  
• Was st der Unterschied zwischen einer logischen und physischen Adresse? S. 90 Eine physische Adresse ist eine reale Adresse einer Speicherzelle in einem Hauptspeicher. Über die physische Adresse kann jede Speicherzelle einzeln adressiert werden. Eine physische Adresse ist dabei eine ganze Zeit, die in binärer Form mit n Stellen dargestellt wird. Wenn Programme im Benutzermodus ausgeführt werden, werden oft logische Adressen verwendet, die mit Hilfe der MMU (Memory Management Unit) in physische Adressen umgesetzt werden. Der logische Adressraum ist dabei meistens (viel) größer als der physische Adressraum, da der reale Hauptspeicher deutlich teurer ist, als der Plattenspeicher, auf dem der logische Adressraum realisiert wird. Eine logische Adresse ist die relative Position zum Anfang des Programms. Ein Prozess braucht nicht die physischen Adressen bei der Ausführung eines Prozesses zu wissen, weil die logische Adresse mit Hilfe der MMU in die physische Adresse umgesetzt wird, bevor ein Zugriff auf den Hauptspeicher stattfindet. Dir wesentliche Änderung liegt in der Bedeutung der Adressen. Eine physische Adresse ist die Angabe einer bestimmten, festen Position im Hauptspeicher, sie wird auch absolute Adresse genannt. Eine logische Adresse dagegen ist hardware-unabhängig: sie zeigt auf einen Ort unabhängig von der konkreten Zuweisung zwischen Datenbereichen und physischem Hauptspeicher. Vor jedem Zugriff auf eine logische Adresse muss diese zunächst in eine physische Adresse übersetzt werden. Logische Adressen sind auch auf höheren Sprachebenen sichtbar. In Assembler-Programmen werden lediglich anstelle von logischen Adressen Bezeichner verwendet; die Semantik dieser Programme, insb. die Adressberechnungen, basiert jedoch unverändert auf logischen Adressen. Von Vorteil ist folgende Idee: Zur Ausführung muss ein Prozess in den Arbeitsspeicher geladen werden. Wegen der sequentiellen Abarbeitung werden innerhalb eines bestimmten Zeitintervalls nicht alle Teile des Prozesses und analog auch nicht der gesamte Datenbereich benötigt. Es reicht also aus, nur die jeweils benötigten Programm- und Datenbereichs- Teile im Arbeitsspeicher zu halten. Die Programme und Daten werden in einzelne Teilabschnitte zerlegt, die dann nur bei Bedarf (wenn sie von der CPU benötigt werden) in den Speicher geladen werden.
• Was gehört zu einem Prozess? Programmsegment, Stacksegment, Datensegment und Prozesskontrollblock → wird auch als Prozessabbild bezeichnet.
• Mehrfache zusammenhängende Speicherzuweisung MFT und MVT      Jeder Prozess bekommt einen zusammenhängenden Abschnitt des physischen Speichers zugeteilt.      Der logische Hauptspeicher des Prozesses ist zusammenhängend.     Multiple contiguous allocation - (Speicher-) Segmente.     Zwei grundlegende Ansätze zu der Aufteilung von dem gesamten physischen Speicher: 1.MFT multiprogramming with a fixed number of tasks     Der physische Speicher wird beim Starten des Betriebssystems fest in Segmente unterschiedlicher Größe aufgeteilt.     Anzahl und Größe der Segmente ändern sich im laufenden Betrieb nicht.     Wenn ein Segment frei wird, wird aus der Menge der auf Ausführung wartenden Aufträge ein Auftrag ausgewählt,dessen Speicherplatzanforderungen von dem freien Segment erfüllt werden. 2.MVT multiprogramming with a variable number of tasks     Der physische Speicher wird variabel in Segmente aufgeteilt.     Anzahl, Lage und Größe der Segmente ändern sich anhand der Speicherplatzanforderungen von zu startenden Prozessen.
• Fragmentierung     Fragmentierung - der Effekt, dass durch die Aufteilung des physischen Speichers Reste (kleine Speicherbereiche) entstehen, die nicht oder nur schlecht nutzbar sind 1. Interne Fragmentierung - einem Prozess wird ein größeren Speicherbereich zugewiesen, als dies eigentlich benötigt. 2. Externe Fragmentierung - nicht zugewiesene Speicherbereiche sind vorhanden, sind aber einzeln zu klein, um die Speicherplatzanforderungen von auf Zuteilung wartenden Prozessen zu erfüllen.      Annahme: zu Beginn eines auszuführenden Auftragt bzw. vor einem erneueten Einlagern dessen Speicherplatzanforderungen sind bekannt.     Statische Datenstrukturen - genaues Abschätzen.      Eingebedaten o. unvorhersehbare Faktoren - der Benutzer muss für jeden Auftrag eine Schätzung des maximalen Speicherplatzbedarfs angeben.      Um den Prozess nicht abbrechen zu müssen wegen der falschen Schätzung - höher.      Dadurch - interne Fr., schlechte Ausnutzung
• MFT     Der physische speicher wird beim Starten des Betriebssystems fest in Segmente unterschiedlicher Größe aufgeteilt.      Anzahl und Größe der Segmente ändern sich zumindest im laufenden Betrieb nicht.      Wenn ein Segment frei wird, wird aus der Menge der auf Ausführung wartenden Aufträge ein Auftrag ausgewählt, dessen Speicherplatzanforderungen von dem freien Segment erfüllt werden.     Das auszuführende Programm wird dann dorthin geladen und ausgerführt.     Bei ungünstig gewählten Segmentgrößen - sehr viel interne Fragmentierung      Fast unmöglich günstige Segmentgrößen zu finden.      Liegen Tage/Wochen fest, können nur durch einen Operateureingriff vor dem erneuten Starten des Systems verändert werden => Speicheranforderungen kaum Abschätzbar.      Die interne Fragmentierung kann durch geschicktes Scheduling verringert werden.      Best-available-fit => einem Auftrag wird das kleinste ausreichende Segment zugewiesen, sofern mehrere zur Auswahl stehen.      Best-fit-only => ein Segment, das nicht wesentlich größer als benötigt ist. Ein Auftrag muss u.U. warten, obwohl ein ausreichend großes Segment frei ist. => Verzögerung manche Prozesse. Führt zu einer Klassifizierung aller Aufträge nach ihrer Größe und unabhängigen Schedulern für jede Größenklasse. Der Systemdurchsatz - verbessert, die Wartezeit kleiner Aufträge - unnötig verlängert.      Systeme, die mit Basisregistern und virtuellen Adressen arbeiten, können das Segment bei einem Fahler wechseln und ermöglichen deshalb wesentlich flexiblere Reaktionen auf wechselnde Speicherplatzanforderungen der Prozesse.
• MVT      Erhebliche externe Fragmentierung => wie geschickt aus dem freien Speicherplatz die Stücke herausgeschnitten werden. Verwaltung eines von 0...n adressierbaren Array von Speicherzellen => einige Segmente (geschlossene Intervalle der Form [a,b] belegt. Unbelegte - Lücken 1. Ein neues Segment der Länge x angefordert. Gesucht - eine Lücke mit der Länge >= x. Lücke = x, die Lücke der Anforderung zuweisen. Lücke > x => vorne oder hinten ein Stück der Länge x teilen. Der Rest = eine neue, kleinere Lücke. Wenn keine ausreichend große Lücke vorhanden ist, muss mit der Erfüllung der Anforderungen solange gewartet werden, bis durch Freigabe besher belegter Segmente eine ausreichend große Lücke entstanden ist. 2. Ein belegtes Segment wird freigegeben => eine Lücke. Wenn diese vorne oder hinten an eine bereits vorhandene Lücke angrenzt, werden die Lücken vereinigt.      Speicherplatzvergabestrategie: Die Fragmentierung und Verwaltungsaufwand sollen gering sein.      Das akute Vergabeproblem => zu hohe externe Fragmentierung => die Zahl der parallel (ohne Swaping) ausfürbaren Prozesse verkeinert => gesamte Systemleistung reduziert.      Annahmen: Segmentgröße - ein ganzes Vielfaches einer sinnvollen Einheit (1KB). Der angeforderte Platz wier darauf aufgerundet. Nur ein Bruchteil ( i. D. die Hälfte) unbenutzt - interne Fragmentierung - vernachlässigbar. Sehr kleine Lücken werden dadurch vermieden - mit denen kann man nix anfangen. Der zu belegende Teil wird an den oberen oder unteren Rand der Lücke gelegt.
• Welche Speicherzuweisungsstrategien zur Verwaltung des Hauptspeichers gibt es?      Einfach zusammenhängende Speicherzuweisung· wurde so in sehr alten Betriebssystemen verwendet· Es gibt zu jeder Zeit nur einen einzigen Benutzerprozess, und dieser bekommt ein komplettes Stück vom Hauptspeicher.· der gesamte logische Adressraum des Prozesses wird zusammenhängend in einem Stück im physischen Hauptspeicher realisiert· Speicherschutz wird realisiert durch ein Grenzregister welches Adresse zwischen BS-Kern und Prozess enthält· Bei Prozesswechsel wird der aktuelles Programm auf Sekundärspeicher ausgelagert und neuer Prozess eingelagert (Swapping)      Mehrfach zusammenhängende Speicherzuweisung· jeder Prozess bekommt einen zusammenhängenden Abschnitt desphysischen Speichers zugeteilt· der gesamte logische Adressraum des Prozesses wird zusammenhängendin einem Stück im physischen Hauptspeicher realisiert· Es gibt hier aber mehrere solcher Abschnitte im physischen Hauptspeicher(multiple contiguous allocation) diese Abschnitte heißen (Speicher-)Segmente· verhindert/verringert Swapping, da andere rechenbereite Prozesse bereitsim Hauptspeicher liegen (Idealfall)· Speicherschutz wird realisiert durch Basisregister (Startadresse einesSegments) und Grenzregister (Länge des Segments)· MFT (multiprogramming with a fixed number of tasks)     o Der Hauptspeicher wird in feste aber nicht zwangsläufig gleichgroße Segmentgrößen aufgeteilt.     o Hohe interne Fragmentierung kann durch geschicktes Scheduling verhindert werden, jedoch nur auf Kosten einer Verzögerung mancher Prozesse     o best-available-fit
  einem Auftrag wird das kleinste ausreichende Segmentzugewiesen, also kein unnötig großes     o best-fit-only
  einem Auftrag wird nur ein Segment zuwiesen, dass nichtwesentlich (z. B. maximal die Hälfte) größer als benötigt ist Auftrag muss dann u. U. warten, obwohl ein ausreichend großes Segment frei wäre      o falsche bzw. ungünstige Zuordnung eines Segments ist nur dannein Problem, wenn kein Segmentwechsel möglich ist, jedoch gibtes auch Systeme die mit virtuellen Adressen arbeiten(Segmentwechsel nach Swapping möglich)· MVT (multiprogramming with a variable number of tasks)     o Segmentgrößen werden dynamisch gesetzt (es werden Stücke ausdem Hauptspeicher herausgeschnitten)      o Hohe externe Fragmentierung wird verursacht, da beiSpeicherfreigabe ein Lücke entsteht      o First Fit
  es wird die erste verfügbare ausreichend große Lücke genommen
  bei kleinen Adressen entstehen besonders viele kleine Lücken
  die Suche nach großen Lücken dauert lange
  i.d.R. am schnellsten      o Next Fit
  wie First Fit mit dem Unterschied, dass immer hinter der ehem. Lücke weitergesucht wird
  Suche wird erfolglos abgebrochen, wenn der Ausgangspunkt wieder erreicht wird      o Best Fit
  es wird die kleinste ausreichend große Lücke genommen
  Nachteil: Es entstehen viele kleine Lücken, die schwer nutzbar sind      o Worst Fit
  die größte Lücke wird gewählt
  Vorteil: Der Rest kann am Besten wieder verwertet werden
  Nachteil: Wenig Platz für große Segmente      o Buddy
  Hauptziel ist die Vereinfachung der Verwaltung der Segmente
  Der zugewiesene Speicherplatz wird immer auf die nächsthöhere 2er-Potenz aufgerundet welches jedoch zu einer nicht unerheblichen internen Fragmentierung führt
  Die Gesamtgröße des Speichers sei ebenfalls eine 2er-Potenz und wird halbiert und eine obere und untere Hälfte,die man buddies (Kumpel) voneinander nennt.
  Jede Hälfte kann erneut in zwei zueinander gehörige buddies geteilt werden
  Vorstellung am Besten als Binärbaum
  Ein angefordertes Segment der Größe 2x kann sofort gefunden werden
  Bei Freigabe eines Segmentes wird dieses wieder mit seinem buddy zusammengelegt,  sofern dieser auch frei ist
  Vorteil: Anforderungs- und Freigabe-Operationen sind effizient implementierbar
  Nachteil: Erhebliche interne und ggf. externe Fragmentierung Nicht zusammenhängende Speicherzuweisung· Trennung von Programm und Daten   o Anforderungen können dadurch besser befriedigt werden   o jedes Segment besitzt einen eigenen Satz von Schutzregistern· Mehrere Segmente   o Man kann statt zwei auch mehr Segmente unterscheiden, z.B. 16   o virtuellen Adressen werden in einen oberen Teil (z. B. 4 Bit), die Segmentnummer, und einen unteren Teil, die Relativadresse innerhalb eines Segments, geteilt.Paging· Siehe
• Was ist der Unterschied zwischen einer Seite und einem Segment? Die Seite ist eine Einheit in der der logischen Speichers unterteil wird. EinSegment ist die Einhiet in der der physische Speicher unterteilt wird.
• Was ist Paging? Der logische Hauptspeicher wird in Einheiten einer bestimmten Größe unterteilt,die Pages (Seiten) genannt werden. Auch der physische Speicher ist unterteilt -hier nennt man die einzelnen Stücke Page Frame (Seitenrahmen, Segment). Seiteund Seitenrahmen sind gleich groß. Ein Seitenrahmen kann folglich genau eineSeite des logischen Hauptspeichers aufnehmen. Jetzt muss man sich nur nochmerken, in welchen Seitenrahmen welche Seite steht. Diese Übersicht enthält dieSeitentabelle ST. Dementsprechend existiert für jeden Prozess eine derartigeSeitentabelle.
• Advertisement
• Was ist der Unterschied zwischen einer Seite und einem Segment? Die Seite ist eine Einheit in der der logischen Speichers unterteil wird. EinSegment ist die Einhiet in der der physische Speicher unterteilt wird.
• Wie sieht eine logische Adresse bei paging aus? Eine logische Adresse ist beim Paging in Seitennummer s und Offset d aufgeteilt.
• Wie wird eine logische Adresse bei Paging auf eine physische Adresse abgebildet? (Die Seitentabelle macht genau diese Abbildung) Die logische Adresse besteht aus einem Seitenanteil s und einem Anteil d der zurAdressierung innerhalb einer Seite dient. Anhand der Seitentabelle (wird inschnellen Hardwareregistern realisiert) erfolgt eine Zuweisung der logischenSeiten zu den physischen Seitenrahmen.Beispiel: (vergleiche auch Seite 113 im Kurstext)Mit p=4096=2k mit k=12 und einer Adresse v=1738410=1000011111010002bilden die ersten (von rechts) k-bit die relative Adressierung innerhalb einer Seite.Die verbliebenen Bits identifizieren die Seite. Rechnung:s = v div p = 17384 div 4096 = 4,244140625 also befindet sich dieseAdressierung in der 4. Seite. Schaut man sich jetzt die binär Darstellung ab Bit 12an, verbleibt 1002=410d = v mod p = 17384 mod 4096 = 1000 also wird innerhalb der Seite die Adresse1000 referenziert. Schaut man sich jetzt wieder die binär Darstellung der Adressev an und vergleicht, die ersten (von rechts) k-bit folgt: 0011111010002=100010Bei der Adressumsetzung, wird der relative Anteil der Adressierung einfachdurchgereicht, und die Seitennummer als Index für die Seitentabelle benutzt, umdie Seite zum Segment über die Seitentabelle aufzulösen. Die physische Adressesetzt sich dann aus der binär Darstellung der physischen Rahmennummer und desrelativen Anteils, zusammen.
• Wer führt diese Abbildung durch? siehe Abbildung 3.15 imKurstext)Die Memory Management Unit führt diese Abbildung durch
• Was ist MMU? In der MMU (Memory Management Unit) werden logische Adressen in physischeAdressen umgeformt. Physisch ist die MMU entweder in der CPU integriert odernahe angeordnet, logisch gesehen liegt sie zwischen CPU und Hauptspeicher.
• Warum ermöglicht der MMU, dass ein Prozess nur die logischen Adressen zu kennen braucht? Da die MMU die logische Adressen in physische Adressen umformt. Dazubenutzt sie die im PCB gespeicherte Seitentabelle, die zu jeder Seite s dieNummer des Seitenrahmens ST[s] enthält, in dem die Seite s gerade gespeichertist.
• Wie kann eine Seite individuell geschützt werden? (Protection-Bit) Es ist möglich, jede Seite individuell zu schützen. Wenn z.B. Programme undDaten auf verschiedenen Seiten stehen, kann das Programm gegen Schreibengeschützt werden und auf den Daten schreiben erlaubt werden. Hierzu enthält dieSeitentabelle ein Protection-Bit (Schutzbit), welches durch die Hardware beijedem Zugriff geprüft wird. Es können drei Bits benutzt werden, jeweils eines fürLeserecht, Schreibrecht und Ausführungsrecht.Für jeden Seitenrahmen wird ein sog. dirty bit verwendet, welches anzeigt, ob dieSeite seit ihrer Einlagerung in den Hauptspeicher verändert wurde. Dieses bit wirdbei Einlagerung auf 0 gesetzt und beim schreibenden Zugriff auf 1.
• Was ist Shared Memory? Was ist der Vorteil? Gemeinsam von mehreren Prozessen genutzter virtueller Hauptspeicher. Wenn ein Prozess auf eineSeite des Shared Memory schreibt, erscheint der modifizierte Inhalt auch im Hauptspeicher desanderen Prozesses. Dies ist eine effiziente Art, Daten zwischen Prozessen auszutauschen, weil dieDaten im physischen Hauptspeicher nicht mehr kopiert werden müssen.Welche Probleme kann entstehen, wenn mehr als ein Prozess eine Shared Memory modifiziert?(Inkonsistenz, Inkorrekt. Siehe auch die internet-basierte Aufgabe von KE 5.)Was muss gemacht werden, damit diese Probleme vermeiden werden können?(Synchronisierung der Prozesse)
• Wie oft wird der Hauptspeicher mindestens bei paging zugegriffen, wenn ein Wort im Hauptspeicher geholt wird? Wenn ein TLB hit vorliegt, gibt es nur einen Zugriff auf den Hauptspeicher. Beieinem TLB miss nehmen wir an, dass das Wort, auf das zugegriffen wird, schonim Hauptspeicher liegt.· das Wort liegt in einer Seite und hat eine logische Adresse· man muss zuerst die Seite bestimmen, in der das Wort liegt· man muss in der Seitentabelle nach dem Seitenrahmen suchen, der dieSeite im Hauptspeicher aufnimmt· danach bekommt man die physische Adresse der Zelle im Hauptspeicher,in der sich das Wort befindetAlso gibt es mindesten zwei Zugriffe, einer ist der Zugriff auf die Seitentabelleund der andere ist der Zugriff auf die Zelle, in der das Wort liegt (unter derAnnahme, dass wir eine einstufige Seitentabelle haben. Bei mehrstufigenSeitentabellen, dann entsprechend mehr)
• Wie kann der Zugriff eines Worts im Hauptspeicher bei paging mit TLB beschleunigt werden? Die Seitentabelle des gerade ausgeführten Prozesses muss in viel schnellerenund damit auch sehr teuren Speichern untergebracht werden als derHauptspeicher, da sonst die Zugriffe auf die Seitentabelle die CPUGeschwindigkeit beeinträchtigen. Da Programme normalerweise nur auf wenigenSeiten arbeiten, ist es besser aktuell benutzte Einträge der Seitentabelle in einemAssoziativspeicher (Cache) zu halten. Die komplette Seitentabelle wird imphysischen Hauptspeicher abgelegt. Ein Teil der Seitentabelle, also die aktuellbenutzten Einträge, werden in einem schnellen Assoziativspeicher (TLB;Translation Lookaside Buffer) abgelegt. Diese enthalten etwa 8 – 16 Einträge.Wenn im TLB eine gesuchte Seitennummer vorhanden ist (TLB hit), wird diezugehörige Seitenrahmennummer ausgegeben. Dieser Vorgang ist etwa 10malschneller als ein Hauptspeicher-Zugriff. Wenn die gesuchte Seitennummer nichtvorhanden ist (TLB miss), wird die zugehörige Seitenrahmennummer aus derSeitentabelle geholt und in die TLB eingetragen. Hierbei muss i.d.R. ein schonvorhandener Eintrag verdrängt werden. Siehe Abbildung:
• Wie kann man die Seitentabelle verwalten, wenn sie zu groß ist? (mehr stufige Seitentabelle) In der Regel darf eine Seitentabelle maximal so lang sein, wie eine Seite. Sollteman eine größere Tabelle benötigten, bietet sich das Konzept der mehrstufigenSeitentabellen an. Diese Seitentabellen werden nicht nur im realen Speicher,sondern auch im virtuellen Speicher abgelegt (Ein Teil liegt im realen Speicher,ein Teil im virtuellen Speicher). Das bedeutet, dass Seitentabellen genauso wiealle anderen Seiten dem Paging unterliegen. Zweck des ganzen ist, dass nichtmehr die gesamte Seitentabelle im physischen Speicher gehalten werden muss.Tabellen die gerade nicht gebraucht werden, sollten nicht im Speicher liegen. Beieinem zweistufigen Seitentabellen-Verfahren gibt es eine erste Stufe, bei der jederEintrag die Adresse oder Seitenrahmennummer einer Seitentabelle der zweitenStufe enthält. Siehe Abbildung
• Was ist die Idee (das Ziel) des virtuellen Speichers? Was ist die Idee (das Ziel) des virtuellen Speichers?· Schreiben eines Programms ohne Einschränkung der Größe desHauptspeichers· nur der Teil bleibt im Hauptspeicher, der gerade gebraucht wird· Die Trennung zwischen logischen und physischen Adressen und dieUnterstützung von MMU machen Programme verschiebbar und dieRealisierung des Konzepts möglich· unterstützt die Unabhängigkeit der Software von der Hardware· Lokalitätseigenschaft unterstützt die Effizienz des Konzepts· es ist transparent für Benutzer und Benutzerprozesse ist.Die Idee oder das Ziel des virtuellen Speichers ist, logische Adressräumerealisieren zu können, die größer als der physische Speicher sind! Zum Vergleich:bei der zusammenhängenden Speicherzuweisung traten zwar auch schon virtuelleAdressen auf; der logische Adressraum eines Prozesses war aber immervollständig im physischen Hauptspeicher realisiert, wenn der Prozess ausgeführtwurde.
• Was ermöglicht die Realisierung des Konzepts des virtuellen Speichers?      Prozesse arbeiten nur mit logischen Adressen      Die physischen Adressen werden erst zur Ausführungszeit mit Hilfe von Hardware MMU abgebildet, daraus folgt: Relokierbarkeit Demand Paging Auslagerungsbereich im Sekundärspeicher (Swapbereich) Die Lokalitätseigenschaft   
• Was ermöglicht die Realisierung des Konzepts des virtuellen Speichers? Prozesse arbeiten nur mit logischen Adressen, die physischen Adressen werdenerst zur Ausführungszeit mit Hilfe von Hardware MMU abgebildet, daraus folgt:· Relokierbarkeit· Demand Paging· Auslagerungsbereich im Sekundärspeicher (Swapbereich)· Die Lokalitätseigenschaft
• Was wird gebraucht, um das virtuelle Hauptspeicher-Konzept mit paging zu realisieren? (Seitentabelle, Swap-bereich)      Für jeden logischen Hauptspeicher brauchen wir also Platz auf einemHintergrund-Speicher (i.A. einer Festplatte), dem sog. Swap-Bereich, der beimStart des BS reserviert wird.      Weiterhin brauchen wir eine Seitentabelle.
• Was wird gebraucht, um das virtuelle Hauptspeicher-Konzept mit paging zu realisieren? (Seitentabelle, Swap-bereich) Für jeden logischen Hauptspeicher brauchen wir also Platz auf einemHintergrund-Speicher (i.A. einer Festplatte), dem sog. Swap-Bereich, der beimStart des BS reserviert wird." (Skript S. 119 ganz unten). Weiterhin brauchen wireine Seitentabelle.
• Wie sieht eine virtuelle Adresse aus? Eine logische Adresse ist wie beim Paging in Seitennummer s und Offset daufgeteilt.
• Warum ist der virtuelle Hauptspeicher byteweise adressiert? (Abbildungsweise einer virtuellen Adresse) Da der physikalische Speicher auch byteweise adressiert ist und somit eineAbbildung einer logischen Adresse auf einer physischen Adresse möglich macht.D.h. der Offset einer Seite des virtuellen Adressraums, wäre dann gleich demOffset der Seite in einem physischen Seitenrahmen.
• Was muss das Betriebssystem bei der Erzeugung eines Prozesses tun, wenn das virtuelle Hauptspeicher-Konzept mit paging realisiert wird? Bei der Erzeugung eines Prozesses wird ganz allgemein ein Speicherplatz fürProgrammsegment, Datensegment, Stacksegment und Prozesskontrollblock imHauptspeicher reserviert. Wenn wir mit Paging arbeiten, verteilt sich dieseSpeicherreservierung auf physischen und virtuellen Speicher. Bei der Erzeugungeines Prozesses muss man folglich eine Seitentabelle im Hauptspeicherinitialisieren und einen Swap-Bereich im Sekundärspeicher reservieren.
• Was ist ein Seitenfehler? Unter einem Seitenfehler (page fault) versteht man, dass sich eine Seite beimversuchten Zugriff nicht im Hauptspeicher befindet.
• Advertisement
• Was passiert bei einem Seitenfehler? Wie wird ein Seitenfehler erkannt? Was muss das Betriebssystem bei einem Seitenfehler tun?      Der reguläre Programmablauf wird unterbrochen (es wird also ein Trap ausgelöst)und das Betriebssystem übernimmt die Kontrolle um z.B. die fehlende Seiteeinzulagern.       Wenn sich die Seite zum Ausführungszeitpunkt des Prozesses nicht imHauptspeicher befindet, also die angeforderte Seite sich in keinem Rahmenbefindet.       Die Abarbeitung des Befehls wird zunächst einmal abgebrochen und eineUnterbrechung (Trap) wird ausgelöst.      Nun wird die Seite vom Hintergrundspeicher in einen freien Seitenrahmen eingelagert (Wenn alle Seitenrahmen belegt sind, muss vorher eine Seite ausgelagert werden). Da dies u.U. dauert, wird ein Prozesswechsel durchgeführt, falls ein anderer Prozessausführungsbereit ist. Schließlich wird der unterbrochene Prozess fortgesetzt undder abgebrochene Befehl erneut ausgeführt, diesmal ohne Seitenfehler.
• Welche Ladestrategien gibt es? (d.h. wann soll eine Seite in den Hauptspeicher geholt werden?) Es gibt das Demand Paging und das PrePaging.
• Was heißt demand paging? Was heißt prepaging? Beschreibt den Vorgang des Ein- und Auslagerns von Seiten, weil Seiten immererst bei Bedarf eingelagert werden, nie auf Vorrat. Beim prepagaing werden Seiten eingelagert, die aktuell noch nicht, vermutlichaber in Zukunft benötigt werden. Das prepaging erweist sich wegen des damiteinhergehenden Verdrängens schon vorhandener Seiten normalerweise alsnachteilig und wird nur in Ausnahmefällen angewandt.
• Was heißt Lokalität eines Prozesses?      Unter der Lokalität des Zugriffsverhaltens von Prozessen verstehen wir, dassüberwiegend hintereinander stehende Instruktionen oder Schleifen, die nurwenige Seiten umfassen, ausgeführt werden und selten zu weiter entferntliegenden Programmteilen gesprungen wird.      Die Menge von Seiten die über einen Zeitraum wesentlich häufiger als andere Seiten benutzt werden, nennt man die Lokalität des Prozesses. Es ist daher möglich, nur einen Teil des gesamten Programms im physischen Hauptspeicher zu halten.  mehrere Codezeilen werden nacheinander gelesen  Daten werden meistens öfters benötigt
• Was ist die Speichereinblendung von Datei? (Memory-mapped files) Memory-mapped Files bedeutet, dass Seiten einer Datei in den virtuellenHauptspeicher eingeblendet werden. Der Prozess sieht dann im virtuellenHauptspeicher die Daten, die in der Datei stehen. Verändert er diese Daten,verändert er implizit auch den Inhalt der Datei. Es muss allerdings vorausgesetztwerden, daß Dateiseiten und Hauptspeicherseiten gleich groß sind. Dies ist eineAlternative zum klassischen E/A-Verfahren.
• Welche Seitenauslagerungsstrategien gibt es? Eine Seitenauslagerungsstrategie legt fest, welche Seite eines Prozessesausgelagert wird. Es gibt hierfür fünf Strategien:FIFO· First-In-First-Out· leicht implementierbar· deutlich höhere Seitenfehlerrate· Nachteil: FIFO lagert auch laufend intensiv genutzte Seiten aus.Second Chance· FIFO-Erweiterung· Ausgabepuffer· Seiten werden nicht sofort ausgelagert· ineffizientClock-Algorithmus· andere Implementierung von Second-Chance· Schlange wird durch zirkuläre Liste erreicht· Seite eingelagert: R-Bit = 0· Seite benutzt: R-Bit = 1· Auslagerung geschieht wie folgt: Zeiger findet Seite mit R-Bit=1 => RBit=0. Zeiger findet Seite mit R-Bit=0 => AuslagerungLRU· Last Recently Used· eigentlich eine sehr gute Strategie· Problem: effiziente Implementierung· ohne aufwändige Hardware-Unterstützung nicht implementierbar Zugriffsbit· Idee ist ähnlich wie LRU, doch man merkt sich nicht den exaktenZeitpunkt, sondern eine Beobachtungsperiode.· Realisierung über Zugriffsbit (Referenced-Bit; kurz: R-Bit)
• Welche Seitenrahmenzuweisungsstrategien gibt es?      Eine (Seitenrahmen-) Zuweisungsstrategie legt fest, wann einem Prozess wievieleSeitenrahmen zugewiesen bzw. entzogen werden. Es gibt hierfür zwei Strategien: · ArbeitsmengenstrategieSie besteht darin, einem Prozess zu einem bestimmten Zeitpunkt so vielSeitenrahmen zuzuweisen, wie dessen aktuelle Arbeitsmenge groß ist. Beijedem Seitenfehler wird einem Prozess folglich ein weiterer Seitenrahmenzugewiesen. · SeitenfehlerhäufigkeitsstrategieWird mit dem Seitenfehler-Frequenz-Algorithmus (Page FaultFrequency) realisiert. Wenn ein Seitenfehler auftritt, registriert dasBetriebssystem die Zeit t, die seit dem letzten von diesem Prozessverursachten Seitenfehler vergangen ist. Man legt einen Grenzwert T fest.Wenn t <= T, wird dem Prozess noch eine Seite zugeteilt. Wenn t > Twerden alle Seiten mit R-Bit = 0 ausgelagert und zugleich das R-Bit allerverbliebenen Seiten auf 0 gesetzt (siehe auch Skript Kap. 3.6.3.3, Seite131ff).
• Wie viele Seitenrahmen sollten einem Prozess zugewiesen werden?      Es gibt keine feste Zuweisung, da die Zuweisung etwas dynamisches ist. Daherkann zu Beginn keine Zahl festgelegt werden, wie viele Seitenrahmen ein Prozessbekommen sollte.      Weist man weniger Seitenrahmen zu, steigt die Seitenfehlerrate zu hoch an (unabhängig von der Seitenauslagerungsstrategie). Wenig sinnvoll ist es, einem Prozess eine feste Menge von Seitenrahmen zuzuteilen.      Eine Zuweisungsstrategie ist die Arbeitsmengenstrategie: Alle Seiten, die in letzter Zeit benutzt worden sind ist die aktuelle Lokalität oder die Arbeitsmenge (working set) des Prozesses. Es werden einem Prozess zu einem bestimmten Zeitpunkt so viele Seitenrahmen zugewiesen, wie dessen aktuelle Arbeitsmenge groß ist. Bei einem Seitenfehler wird einem Prozess ein weiterer Seitenrahmen zugewiesen. Wenn eine Seite aus der Arbeitsmenge herausfällt, zu lange nicht mehr benutzt wurde, wird dem Prozess ein Seitenrahmen entzogen. Welche Seite nun ausgelagert wird, kann im Prinzip von einer beliebigen Seitenauslagerungsstrategie bestimmt werden. Sinnvol LRU oder deren Approximation.      Gründe: Bei einer festen Zahl von zugeteilten Seitenrahmen ist die Ursache einer Seitenauslagerung immer eine Seiteneinlagerung, die irerseits durch einen Seitenfehler verursacht wurde. Bei der Arbeitsmengenstrategie ist die Ursache einer Seitenauslagerung immer das Herausffallen einer Seite aus der Arbeitsmenge. Es können Seiten eines Prozesses ausgelagert werden, ohne dass dieser Prozess einen Seitenfehler verursacht hätte und ohne dass für diesen Prozess eine neue Seite eingelagert wird.      Abweichungen von der aktuellen Lokalität: Die Arbeitsmenge enthält auch Seiten, die in letzter Zeit nur ein einziges Mal benutzt worden sind und die eigentlich ohne größeres Risiko wieder ausgelagert werden können. Beim Übergang von einer Lokalität zu einer anderen enthält die Arbeitsmenge noch eine Zeitlang Seiten aus der alten Lokalität, die erst nach und nach aus der Arbeitsmenge herausfallen. Umgekehrt ist die neue Lokalität noch nicht vollständig aufgebaut.      Bei jedem Speicherzugriff wird es geprüft ob in diesem Moment irgendeine Seite hinten aus dem Fenster (letzte Zeit) herausfällt, in den letzten n (Fenstergröße) Zugriffen nicht mehr benutzt wurde - Zugriffsbits.      Ein Entwickler braucht keine Rücksicht zu nehmen, wie ein virtueller Speicher realisiert ist. Man kann ihn wie einen physischen Speicher behandeln.      Man kann aber relativ häufig zwischen funktional äquivalenten Programmstrukturen wählen, die zu völlig verschiedenen Arbeitsmengen führen -> indem Datenstrukturen mehr oder weniger verstreut angelegt werden.
• Was ist Seitenflattern? Seitenflattern (auch Trashing genannt) meint eine Systemüberlastung. Dies trittdann auf, wenn die Summe der Arbeitsmengen aller aktiven Prozesse größer alsder verfügbare physische Hauptspeicher ist. Dieselben Seiten werden nun immerwieder ersetzt und neu eingelagert. In einem solchen Zustand ist die CPUAuslastungsehr gering, denn die CPU muss ja ständig auf einzulagernde Seitenwarten.Trashing vermeiden: Jedem Prozess so viele Seiten zuordnen, wie er mindestensbenötigt oder bei Überlastung die Zahl der aktiven Prozesse verringern, indemz.B. Prozesse mit geringer Priorität vorübergehend stillgelegt werden
• Einfach zusammenhängende Speicherzuweisung · wurde so in sehr alten Betriebssystemen verwendet· Es gibt zu jeder Zeit nur einen einzigen Benutzerprozess, und dieser bekommt ein komplettes Stück vom Hauptspeicher.· der gesamte logische Adressraum des Prozesses wird zusammenhängend in einem Stück im physischen Hauptspeicher realisiert· Speicherschutz wird realisiert durch ein Grenzregister welches Adresse zwischen BS-Kern und Prozess enthält· Bei Prozesswechsel wird der aktuelles Programm auf Sekundärspeicher ausgelagert und neuer Prozess eingelagert (Swapping)
• Kompaktifizierung       Wenn die Inhalte von Segmenten verschiebbar sind, kann man in dem Fall, wo die externe Fragmentierung so hoch wird, dass deswegen Speicheranforderungen nicht mehr erfüllt werden können, den gesamten physischen Speicher reorganisieren bzw. kopmaktifizieren - garbage collection.      Der Aufwand ist beträchtlich, muss gegen die Vorteile - höheren Parallelitätsgrad beim multi-programming.      Einfachter Fall - alle belegten Bereiche werden nach vorne geschoben, die Reihenfolge unverändert. Der gesamte freie Speicher - hinten in einer einzigen Lücke verfügbar. Viel Aufwand Man schiebt so lange nach vorne, bis eine ausreichend große Lücke entsteht.Man schieb hinten stehende Segmente in vorne liegende Lücken, wenn diese nur unwesentlich größer sind.Man sucht einen Teil des Speichers, der nur zu einem geringen Teil belegt ist und verschiebt die dort stehenden Segmente in Lücken in anderen Teilen des Speichers.Bei Swapping - umsonst.
• Speicherzuweisungsstrategien bei MVT      FIRST FIT      Am Anfang beginnend durchsucht, die erste verfügbare, ausreichend große Lücke gewählt.      Erste - die Länge der Lücken - sie seien in einer nach Anfangsadressen aufsteigend sortierten Liste organisiert.      Bei den kleinen Adressen besonders viele kleine Lücken entstehen, die Suche nach großen Lücken dauert lange.      NEXT FIT      Wie first-fit + immer hinter der (ehemaligen) Lücke weitergesucht wird, an der die letzte Zuteilung erfolgte. Nach dem Ende der Liste fängt man wieder vorne an. Die Suche wird erfolglos abgebrochen - der Ausgagnspunkt erreicht.      BEST FIT      Die kleinste ausreichend große Lücke gewählt.      Die Lücken werden nach ihrer Größe sortiert, linear oder in einem binären Baum.      Um freigegebene Segmente effizient zusammenlegen zu können => bei jeden belegten oder freien Segment einen Verweis auf das davor- und das dahinterliegende Segmente.      Produziert sehr viele kleine Lücken => können schlecht o. gar nicht mehr zugewiesen werden.      WORST FIT      Die größte vorhandene Lücke wird gewählt.      Motivation - die Restlücke ist auch relativ groß und kann gut wiederverwendet werden.      BUDDY      Linux. Die Verwaltung der Segmente zu Vereinfachen.      Der zugewiesene Speicherplatzt wird auf die nächsthöchere 2-er Potenz aufgerundet.      Extreme interne Fragmentierung.      Die Gesamtgröße des Speichers 2 hoch k. Wird halbiert in untere und obere Hälfte - Buddies (Kumpel).      Jede Hälfte kann erneut in zwei zueinandergehörige Buddies geteilt.      Binäre Baum: der gesamte Speiche auf Ebene 0, dessen Hälften der Größe 2 hoch (k-1) auf Ebene 1, deren Hälften der Größe 2 hoch (k-2) auf Ebene 2 usw.      Die freien Segmente der Größe 2 hoch l fasst man in eine Liste L(l) zusammen.      Ein angefordertes Segment der Große 2 hoch x kann in der Liste L(x) gefunden werden.      Ist diese Liste leer, wird ein Buddy aus Liste L(x+1) halbiert => zwei Buddies der Größe 2 hoch x entstehen. Ist aus L(x+1) leer, teilt man einen Buddy der Größe 2 hoch (x+2).      Bei Freigabe eines Segments wird dieses wieder mit seinem Buddy zusammengelegt, sofern dieser frei ist. Kann sich zu den größeren Buddies hin wiederholen.      Dem Buddy eines Segments kann man anhand der Adresse und der Größe dieses Segment bestimmen.      Die Anforderungs- und Freigabe-Operationen sind sehr effizient implementierbar.      Erhebliche interne und u.U. dadurch verursacht externe Fragmentierung.      Vergleich      Die first-fit - einfachste, beste u. schnellste.      Die next-fit - schlechtere Ergebnisse als ff, ein Block wird am Ende des freien Speichers zugeteilt -> der größte freie Speicherbloch (i.d.R. am Ende des Speichers) - zerfällt in kleine Fragmente.      die best-fit - die schlechteste Wahl - das zurückbleibende Fragment ist so klein wie möglich - der Hauptspeicher ist mit Speicherblöcken übersät, die zu klein sind, um noch irgendwelche Speicheranforderungen zu erfüllen.  

back  |  next 1 / 1