| i. | Direkte Adressierung | ||
| ii. | Relocation | ||
| iii. | Virtuelle Speicherverwaltung | ||
| Segmentierung | Paging | ||
| Seiten- oder Segmentwechsel-Algorithmen | |||
Der Arbeitsspeicher (Hauptspeicher, Memory) ist ein Betriebsmittel, ohne das kein Programm zur Ausführung kommen kann. Eine zentrale Aufgabe eines jeden Betriebssystems ist deshalb die Speicherverwaltung. Sie organisiert die Zuweisung von Hauptspeicher an Benutzeraufträge bzw. Tasks, und zwar sowohl Programmspeicher als auch Datenspeicher. Sie muss darüber Buch führen, welche Speicherbereiche gerade frei und welche belegt sind.
Vom Beginn der Rechnergeschichte bis heute kann das Phänomen beobachtet werden, daß der Bedarf an Arbeitsspeicher immer größer ist als der verfügbare physische ("physikalische") Speicher. Fast immer ist der verfügbare Speicher zu klein, um ein großes Programm oder mehrere Programme gleichzeitig aufzunehmen. Im Lauf der verschiedenen Rechnergenerationen wurden eine Reihe von Lösungen für dieses Problem entwickelt.
Die moderneren Methoden gehen dabei von der Tatsache aus, dass zu einem beliebigen Zeitpunkt nur auf wenige Speicherplätze tatsächlich zugegriffen wird, während die anderen nur für einen späteren Zugriff (der u.U. nie erfolgt) bereitstehen. Die Grundidee ist also eine Erweiterung der Speicherkapazität unter Zuhilfenahme externer Massenspeicher (Festplatten), von denen bei Bedarf die benötigten Informationen in den Arbeitsspeicher geladen werden. In diesem Fall muss die Speicherverwaltung in der jeweiligen Situation festlegen, welche Programmabschnitte geladen werden sollen und welche auf dem "Hintergrundspeicher" (d.h. auf der Festplatte) bleiben sollen. Insbesondere beim Multitasking-Betrieb entstehen für die Speicherverwaltung vielfältige Aufgaben, denn es müssen sich mehrere unabhängige Programme im Hauptspeicher befinden, die u.U. häufig aus- und eingelagert werden müssen.
Noch komplizierter wird es, wenn sich mehrere CPUs einen gemeinsamen Speicher teilen.Zu den Aufgaben der Speicherverwaltung gehört es auch, Mechanismen für den Schutz vor unbefugten Speicherzugriffen aus anderen Programmen bereitzustellen. Die folgende Auflistung von Speicherverwaltungsprinzipien beginnt mit den einfachsten - meist älteren und endet bei den heute üblichen Methoden des "Memory-Management" in Universalrechnern.
Einfache universelle Betriebssysteme für den Einprogrammbetrieb verwalten den gesamten Speicher zumeist als einen Block, der aus einem Systembereich für das Betriebssystem und einem Benutzerbereich besteht. Das aktuelle Programm belegt einen zusammenhängenden Teil des Benutzerbereichs. Der restliche Speicher ist frei: "Zusammenhängende Einzelzuteilung" oder "single contiguous allocation".
Es gilt:
Ein Prozess darf den Speicherbereich anderer Prozesse nie beeinflussen. Zu diesem Zweck sind Hard- und Softwaremaßnahmen nötig (Speicherschutz). Der Mehrprogrammbetrieb erhöht zudem die CPU-Auslastung. Wenn ein Prozess auf das Ende einer E/A-Operation wartet, läuft die CPU im Einprogrammbetrieb leer. Im Mehrprogrammbetrieb können in dieser Zeit andere Prozesse rechnen.
Der einfachste Weg ist die Aufteilung in feste Teile (=Partitionen), die nicht notwendig gleich groß sein müssen. Zusätzlich zur Partitionierung sind Maßnahmen zur Relokation (Verschiebung) der Programme beim Laden und zum Speicherschutz notwendig (siehe unten).
Prozesse dürfen nur auf Bereiche innerhalb der Partition zugreifen (gilt für Code und Daten!), da sonst andere Prozesse unzulässig beeinflusst werden könnten. Die Speicherverwaltungseinheit muss also entsprechende Schutzfunktionen besitzen und Zugriffe auf "verbotene" Bereiche an den Betriebssystem-Kern melden. Eine Lösung besteht beispielsweise in zwei zusätzlichen Registern des Prozessors, Base- und Limit-Register. Das Baseregister enthält die Startadresse der dem aktiven Prozess zugeordnenten Partition und das Limitregister deren Länge. Alle Adressierungsvorgänge im Programm erfolgen relativ zum Base-Register. Eine Änderung der beiden Register erfolgt durch den Scheduler.
Bei der "Zusammenhängenden Einzelzuteilung" entsteht ein Adressierungsproblem für evtl. mitzuladende Bibliotheksroutinen wenn die Benutzerprogramme unterschiedlich lang sind, denn dann kommen diese Bibliotheksprogramme an unterschiedlichen Adressen zu liegen. Eine mögliche Lösung ist ein eigener fester Bereich für diese Routinen, was jedoch dazu führt, daß der Speicher zerstückelt wird und damit unnötig viel nicht genutzter Speicher entsteht.
Die flexiblere Lösung besteht darin, die Bibliotheksroutinen so aufzubereiten, dass die Festlegung der von ihnen benötigten Speicherplätze bis zum Ladezeitpunkt aufgeschoben werden kann. Man benötigt dazu einen "verschiebenden Lader" (Relocating Loader), der dann auch gleich zum Laden der Benutzerprogramme verwendet werden kann.
Die Aufbereitung der Programme besteht darin, die Adressteile der Maschinenberfehle als absolute bzw. relative Adressen zu kennzeichnen. Somit besteht die Aufgabe des verschiebenden Laders darin, zu den relativen Adressangaben nur noch einen konstanten Offset zu addieren (die Lade-Startadresse des Programms) und diese nun absolute Adressangabe abzuspeichern; Voraussetzung ist natürlich, dass die Programme so geschrieben sind, als würden sie immer ab Adresse Null im Speicher zu liegen kommen.
Es wird also zum Ladezeitpunkt jede relative Adresse in eine absolute umgeformt, wodurch der Ladevorgang mehr Zeit in Anspruch nimmt. Das geladene Programm kann nicht mehr verschoben werden, wenn es sich im Hauptspeicher befindet.
Eine weitere Steigerung der Flexibilität ist dann gegeben, wenn die Umsetzung in effektive Adressen nicht zum Ladezeitpunkt, sondern erst unmittelbar bei Ausführung des Befehls vorgenommen wird. Voraussetzung dafür ist ein Prozessor, der entsprechende Adressierungsarten der Befehle erlaubt. Dazu muss ein Adressrechenwerk im Prozessor vorhanden sein, das entweder den Inhalt eines Basisadressregisters (geladen durch das Ladeprogramm; "Basisregister-relative Adressierung") oder den Inhalt des Program-Counters addiert ("position independent code", "relocatable code" durch "PC-relative Adressierung"). Die Adressangaben bei den Befehlen werden also nicht mehr vom Lader modifiziert, der Ladevorgang läuft wesentlich schneller ab. Das Programm kann nach dem Laden noch im Speicher verschoben werden.
Man spricht von virtueller Speichertechnik (virtual memory), wenn der Speicheradressraum, auf den sich die Befehle des Prozessors beziehen, getrennt ist vom realen Adressraum des Arbeitsspeichers, in dem sich das Programm bei der Abarbeitung befindet.
Der Adressraum, auf den sich die Programmbefehle beziehen, ist der logische Adressraum. Der Adressraum des realen Arbeitsspeichers ist der physikalische Adressraum. Programme können unabhängig vom physikalischen Adressraum geschrieben werden. Der logische Adressraum beschreibt einen gedachten, nicht real vorhandenen Arbeitsspeicher, den man als virtuellen Speicher bezeichnet.
Normalerweise ist der logische Adressraum größer als der physikalische Adressraum (meist sogar sehr viel größer). Der virtuelle Speicher wird auf der Platte abgebildet. Zur Ausführung muss ein Programm in den Arbeitsspeicher geladen werden. Wegen der sequenziellen Abarbeitung werden innerhalb eines bestimmten Zeitintervalls nicht alle Teile des Programms und analog auch nicht der gesamte Datenbereich des Programms benötigt.
Es reicht also aus, nur die jeweils benötigten Programm- und Datenbereichs-Teile (= "working set") 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.
Zur Abarbeitung der einzelnen Befehle des Programms ist eine Transformation (d.h. Abbildung) der logischen Adressen in physikalische Adressen erforderlich.
Die logische Adresse in den Befehlen bleibt auch nach dem Laden in den Arbeitsspeicher unverändert erhalten. Die Transformation erfolgt erst bei der Befehlsausführung: es liegt eine dynamische Adresstransformation vor. Befindet sich eine Adresse in einem Programm- oder Datenabschnitt, der nicht im Arbeitsspeicher liegt, wird der entsprechende Abschnitt nachgeladen.
Zur Realisierung der vituellen Speicherverwaltung muss eine Kombination aus Hard- und Software eingesetzt werden. Das Nachladen der Programm- und Datenabschnitte besorgt ein speziell konzipiertes Betriebssystem. Grundvoraussetzung für die Realisierung ist die Fähigkeit der CPU, einen laufenden Befehl zu unterbrechen (beim Nachladen) und nach erfolgtem Nachladen den begonnenen Befehl erneut aufzusetzen und dann vollständig auszuführen. Die virtuelle Speichertechnik ist für den Anwender vollkommen transparent. Sowohl das Nachladen von Programm- und Datenabschnitten als auch die Adressumsetzung geschieht automatisch und braucht bei der Anwendungsprogrammierung nicht berücksichtigt zu werden.
Der logische Adressraum wird in Abschnitte variabler Größe gemäß den logischen Einheiten des Programms (Unterprogramme, Datenbereiche, etc.) unterteilt. Die Abschnitte nennt man Segmente. Die minimale/maximale Segmentgröße hängt vom jeweiligen System ab (typisch: 256 Byte bis 64 KByte). Diese Art der Speicherorganisation wird vor allem von Prozessoren der Firma Intel unterstützt.
Die logische Adresse besteht aus 2 Teilen:
Für die in den Arbeitsspeicher geladenen Segmente ist in einer Segmenttabelle die jeweilige reale Anfangsadresse des Segments festgehalten (Basisadresse des Segments). Im Multiprogramming-Betrieb werden für die verschiedenen "Jobs" meist jeweils eigene Tabellen bereitgestellt, damit zwischen den Segment-Nummern verschiedener Jobs keine Verwechslung möglich ist. Somit muss vor dem Segmenttabellenzugriff noch der Inhalt eines jobspezifischen Segmenttabellenregisters zur Segmentnummer addiert werden.
Bei jedem Umschalten der Jobs (Context-Switch) muss deshalb auch das Segmenttabellenregister umgeladen werden. Im Allgemeinen enthält die Segmenttabelle auch Angaben über die Größe der Segmente (Angabe der letzten physikalischen Adresse des Segments oder der Segmentgröße direkt). Dadurch können fehlerhafte Zugriffe, die aus dem Segment herausführen, erkannt und verhindert werden.
Weiterhin sind in der Segmenttabelle jedem Segment noch Zustands- und Zugriffsinformationen zugeordnet (Erkennen nicht geladener Segmente, Verhinderung unberechtigter Zugriffe). Das Segment ist die kleinste Austauscheinheit. Falls kein Speicherplatz zum Nachladen mehr frei ist, muss ein vorhandenes, derzeit nicht benötigtes Segment entfernt werden ("demand segment swapping").
Probleme (gleichzeitig Nachteile der Segmentierung):
Logischer und physikalischer Adressraum werden in Abschnitte gleicher Länge eingeteilt, die man Seiten (Pages) nennt (typische Seitengrößen: 512 Bytes bis 4 KBytes). Eine Seite stellt die kleinste Austauscheinheit dar. Das Laden bzw. Nachladen einer Seite erfolgt bei Bedarf, d.h. wenn eine in dieser Seite liegende Adresse referiert wird ("demand paging"). Falls noch physische Seiten frei sind, wird einer neu zu ladenden logischen Seite die nächste freie physische Seite zugewiesen. Sind alle physischen bereits besetzt, muss eine logische Seite ausgelagert werden (Seitenwechsel). Verantwortlich hierfür ist das Betriebssystem-Programm "Page-Supervisor". Ein Programm kann seitenweise gestückelt im Arbeitsspeicher stehen, also ohne Rücksicht auf irgendwelche logischen Grenzen an Seitengrenzen geteilt.
Die logische Adresse wird zerlegt in
Die Wortadresse ist die relative Adresse zum Seitenanfang. Sie kann unverändert in die physische Adresse übernommen werden. Die physische Adresse besteht auch aus zwei Teilen:
Wegen der festen Seitengröße liegt auch die Grenze zwischen Wortadresse und Seitennummer immer an der gleichen Stelle. Die physische Seitennummer muss mittels der Adresstransformation aus der logischen Seitennummer ermittelt werden.
Die Adresstransformation findet erst zum Zeitpunkt der Ausführung eines Befehls statt, man spricht deshalb von einer dynamischen Adressumsetzung. Sie geschieht i.a. unter Verwendung einer Adressumsetzungstabelle (Adressumsetzungsspeicher, translation buffer), die für die im Arbeitsspeicher befindlichen Seiten die Zuordnungspaare (logische Seitennummer, physische Seitennummer) enthält.
Besonders vorteilhaft für diesen Zweck sind sogenannte Assoziativspeicher (= CAM, Content Addressable Memory), deren Zugriff nicht über eine Adresse, sondern über Zelleninhalte erfolgt. Es wird ein Suchwort (Schlüssel) anstatt der Adresse angelegt und als Ergebnis erhält man eine Trefferanzeige, u.U. auch keinen Treffer. Der Schlüssel ist in diesem Fall die logische Seitennummer, 'Treffer' bedeutet, es existiert ein entsprechender Eintrag in der Tabelle, im speziellen Fall der Adressumsetzung: die gesuchte logische Seite ist geladen, die eigentliche Information des Tabelleneintrags, die physische Seitennummer, wird ausgelesen.
Meldet der Assoziativspeicher keinen Treffer, d.h. die Seite befindet sich nicht im Arbeitsspeicher ("Page Fault"), so wird das Laden dieser Seite eingeleitet (Seitenwechsel und Eintrag in die Tabelle!).
Vorteile des Paging-Verfahrens (gegenüber Segmentierung):
Fazit: Paging ist für die Realisierung eines virtuellen Speicher-Systems geeigneter als die Segmentierung.
Kennzeichen der virtuellen Speichertechnik ist das Laden bzw. Nachladen von Programmabschnitten (Seiten bzw. Segmente) bei Bedarf während der Programmausführung. Grundvoraussetzung ihrer Realisierung ist deshalb die Fähigkeit der CPU, einen laufenden Befehl zu unterbrechen (bei erforderlichem Nachladen einer Seite bzw. Segments) und nach erfolgtem Nachladen den begonnenen Befehl erneut aufzusetzen und dann ganz auszuführen. Für die Auswahl derjenigen Seite (bzw. Segment), die bei einem Seitenwechsel aus dem Arbeitsspeicher entfernt werden soll, gibt es verschiedene Strategien.
 |
 |
 |
