Wie und in welcher Form kommt ein Programm in den Hauptspeicher?
Einprägsame Antwort:
Compiler:
Wandelt jede Quell-Datei (z.B. C-Datei) in eine Objekt-Datei um.
Diese Objekt-Datei enthält Maschinencode, aber noch keine endgültigen Speicheradressen.
Linker:
Verbindet die Objekt-Dateien zu einem Lademodul.
Dabei werden alle Adressen auf die Anfangsadresse Null gesetzt (die relativen Adressen).
Loader:
Der Loader nimmt das Lademodul und lädt es in den Hauptspeicher.
Hauptspeicherverwaltung des Betriebssystems entscheidet, wo das Lademodul im Speicher abgelegt wird.
Es erfolgt keine Neuberechnung der Adressen – sie bleiben relativ.
Einfache Antwort:
Compiler erstellt aus Quell-Dateien Objekt-Dateien.
Linker verbindet die Objekt-Dateien zu einem Lademodul.
Loader lädt das Lademodul in den Speicher und setzt es an eine freie Stelle, ohne Adressen neu zu berechnen.
Was ist die Aufgabe der Hauptspeicherverwaltung? Wie funktioniert die Haupt-speicherverwaltung?
Prozess-Kontrollblock (PCB):
Der Prozess-Kontrollblock speichert alle wichtigen Informationen über einen Prozess, z.B. den Befehlszähler und andere Registerinhalte zum Zeitpunkt einer Unterbrechung.
Ziel der Hauptspeicherverwaltung:
Hauptspeicherzuweisung: Den Prozessen wird der Hauptspeicher zugewiesen, und die darin enthaltenen Daten werden auch während Wartezuständen (z.B. Blockierung) beibehalten.
Dynamische Allokation:
Die dynamische Allokation ist verantwortlich für die Zuweisung von Hauptspeicher, insbesondere wenn Programme vom Sekundärspeicher (z.B. Festplatte) in den Hauptspeicher geladen werden.
Der Prozess-Kontrollblock (PCB) speichert wichtige Informationen über einen Prozess.
Die Hauptspeicherverwaltung sorgt für die Zuweisung und Speicherung der Daten während Wartezuständen.
Dynamische Allokation weist Speicher zu, wenn Programme vom Sekundärspeicher in den Hauptspeicher geladen werden.
Was ist eine symbolische Adresse?
Objektmodule verwenden symbolische Adressen, die Adressen vor dem Linken (also vor der tatsächlichen Zuweisung im Speicher).
Eine physische (absolute) Adresse ist eine tatsächliche Speicheradresse im Hauptspeicher, die auf eine bestimmte Speicherstelle verweist und über den Adressbus angesprochen wird.
Objektmodule nutzen symbolische Adressen, bevor der Speicher verlinkt wird.
Eine physische (absolute) Adresse ist eine echte Speicheradresse, die auf eine Stelle im Hauptspeicher verweist.
Was ist eine logische (virtuelle/relative) Adresse?
Logische Adressen sind Verweise auf Speicherstellen, die unabhängig von der aktuellen Speicherbelegung sind (z.B. bei einem Page Fault).
Ein Prozess kennt nur logische Adressen und arbeitet mit diesen, da das Programm auf einem logischen Adressraum basiert.
Die Umrechnung auf physische Adressen passiert während der Laufzeit über die MMU (Memory Management Unit), die den Zugriff auf den Hauptspeicher ermöglicht.
Logische Adressen verweisen auf Speicherstellen und sind unabhängig von der aktuellen Speichernutzung.
Ein Prozess nutzt nur logische Adressen und diese werden erst zur Laufzeit durch die MMU in physische Adressen umgewandelt.
Was ist der logische Adressraum?
Ein Prozess kann mehrere logische Adressräume haben, wenn er Segmentierung nutzt.
Diese Segmente können z.B. sein:
RAM-Daten
Prozesstapel
Programm
Konstanten-Daten
Jedes Segment hat seine eigenen logischen Adressen, was eine bessere Verwaltung und Sicherheit ermöglicht.
Durch Segmentierung kann ein Prozess mehrere logische Adressräume haben, wie z.B. für Daten, Stapel, Programm und Konstanten.
Warum ist die logische/virtuelle Adressierung vorteilhaft?
Programme können ohne Wissen über ihre spätere physische Speicherposition erstellt und gebunden werden – der Code ist relokierbar.
Dies ermöglicht eine dynamische Allokierung und eine flexible Speicherverwaltung.
Die Adressumsetzung von logisch/virtuellen zu physischen Adressen erfolgt zur Laufzeit über die MMU (Memory Management Unit), die mit einem Basisregister und ggf. einem Grenzregister arbeitet.
Das Grenzregister ermöglicht zusätzlich einen Speicherschutz.
Mehrere Prozesse können denselben physikalischen Speicher nutzen, was Effizienz bietet, jedoch zu Auslagerungsaufwand führt.
Programme sind relokierbar und können ohne Kenntnis ihrer physischen Position im Speicher laufen.
Die MMU übersetzt logische in physische Adressen und kann auch Speicherschutz bieten.
So können mehrere Prozesse den Speicher gemeinsam nutzen, aber es kann zu Auslagerungen kommen.
Was ist Segmentierung (segmentation)?
Segmentierung teilt den logischen Adressraum eines Prozesses in mehrere Segmente auf, z.B. für Daten, Code und Stack.
Jeder Adressraum innerhalb eines Segments ist sowohl logisch als auch physisch zusammenhängend.
Bei x86-Architekturen mit Segmentierung + Paging MMU:
Der virtuelle Adressraum wird durch Segmentierung in mehrere logische Adressräume aufgeteilt (jeder beginnt bei 0).
Das hilft bei der Vermeidung von Kollisionen, wenn ein Prozess wächst.
Externe Fragmentierung tritt auf, aber im virtuellen linear adress Adressraum sind diese Löcher oft nicht störend, weil Paging folgt und die physische Adressierung unabhängig von der Segmentierung funktioniert.
Die Segment-Selektion erfolgt durch die höherwertigen Bits der Adresse.
Segmentierung teilt den Prozess-Adressraum in verschiedene Segmente auf (z.B. für Code, Daten, Stack).
Bei x86 hilft die Kombination von Segmentierung und Paging, Kollisionen zu vermeiden, wenn der Prozess wächst.
Externe Fragmentierung wird durch das Paging-System ausgeglichen, wodurch Löcher im virtuellen Adressraum nicht stören.
Was ist die „zusammenhängende Hauptspeicherzuweisung“
Der logische Adressraum eines Prozesses (bzw. der Segment-Adressräume) wird auf einen zusammenhängenden physischen Speicherbereich abgebildet.
Programm-Code und Daten müssen relokierbar gebunden (gelinkt) sein, damit diese Abbildung funktioniert.
Laden eines Prozesses:
Der Langzeit-Scheduler weist dem Prozess einen Hauptspeicherbereich zu, basierend auf einer Allokierungs-Strategie (z.B. first fit, best fit).
Swapping:
Ein ausgelagerter Prozess (z.B. auf der Festplatte) muss zurück in den Hauptspeicher geladen werden, um wieder ausgeführt werden zu können.
Dies muss nicht unbedingt an dem gleichen physischen Speicherbereich erfolgen.
Externe Fragmentierung:
Wenn Prozesse unterschiedliche Segmentgrößen haben, entstehen Speicherlöcher durch das Swapping, die nicht mehr verwendet werden – dies nennt man externe Fragmentierung.
Kompaktifizierung: Durch das Verschieben von Daten können diese Löcher wieder beseitigt und der Speicherbereich nahtlos zusammengefügt werden.
Das „+“ steht für die Abbildung von logischen Adressen auf physische Adressen.
Das „<“ zusammen mit dem „+“ sorgt für den Speicherschutz.
Der logische Adressraum eines Prozesses wird auf einen zusammenhängenden physischen Speicher abgebildet, wobei der Code und die Daten relokierbar sind.
Der Langzeit-Scheduler weist dem Prozess einen Speicherbereich zu.
Beim Swapping wird ein ausgelagerter Prozess wieder in den Hauptspeicher geladen, was zu externer Fragmentierung führen kann.
Kompaktifizierung räumt diese Speicherlöcher auf.
Das „+“ sorgt für die Abbildung der Adressen, das „<“ für den Speicherschutz.
Was ist „Paging“?
Der physische Speicher wird in gleich große Blöcke, sogenannte Seitenrahmen (frames), unterteilt, um das Problem der externen Fragmentierung zu vermeiden.
Interne Fragmentierung kann jedoch noch im letzten Block auftreten, wenn dieser nicht komplett genutzt wird (durchschnittlich eine halbe Blockgröße).
Logischer Adressraum:
Der logische Adressraum ist in Seiten (pages) unterteilt. Jede Seite hat die gleiche Größe wie ein Seitenrahmen im physischen Speicher (z.B. 4k).
Die Seitentabelle bildet logische Seiten auf physische Seitenrahmen ab.
Adressaufbau:
Eine logische Adresse besteht aus einer Seitennummer und einem Offset innerhalb der Seite.
Eine physische Adresse besteht aus einer Seitenrahmennummer und einem Offset innerhalb des Rahmens.
Die Seitentabelle enthält für jede Seite die entsprechende Seitenrahmennummer. Sie darf jedoch nicht auf die Festplatte ausgelagert werden, besonders nicht, wenn sie nur eine einstufige Tabelle ist.
Der physische Speicher wird in gleich große Blöcke (Seitenrahmen) unterteilt, wodurch externe Fragmentierung vermieden wird. Interne Fragmentierung kann im letzten Block auftreten.
Der logische Adressraum besteht aus Seiten, die auf Seitenrahmen im physischen Speicher abgebildet werden.
Eine logische Adresse besteht aus einer Seitennummer und einem Offset, eine physische Adresse aus einer Seitenrahmennummer und einem Offset.
Die Seitentabelle ordnet logische Seiten den physischen Seitenrahmen zu und darf nicht ausgelagert werden.
Wenn die Seitentabelle eines Prozesses auch im Hauptspeicher liegt, bezahlt man dann bei Hauptspeicher-Zugriffen nicht mit einem Performance Verlust um Faktor 2?
Man verwendet einen Adress-Cache (Translation Lookaside Buffer) der allerdings bei jedem Prozesswechsel „geflusht“ werden muß.
Annahme Zugriff HS:100ns, Cache:20ns: 80% Treffer: 0,8 *120ns + 0,2 * (240ns) = 144ns, anstatt 100ns ohne Adressraum-Virtualisierung bzw. 100ns bei absoluten Adressen.
Wer kümmert sich um die Zuteilung des Hauptspeichers und welche Strategien gibt es? Wie erfolgt die Seitenallokation in Linux?
Der Langzeit-Scheduler verwendet eine dynamische Allokierungsstrategie (z.B. first fit oder best fit) zur Zuweisung von Hauptspeicher.
Bei Linux kommt ein Buddy-Zuweiser zum Einsatz, der physisch aufeinanderfolgende Seitenrahmen bereitstellt, und zwar nach der Buddy-Strategie.
Buddy-Strategie:
Zweierpotenzen: Der Speicher wird in Bereiche aufgeteilt, deren Größe eine Zweierpotenz ist (z.B. 1KB, 2KB, 4KB, etc.).
Der kleinste verfügbare Block wird verwendet, der mindestens die benötigte Größe hat. Wenn dieser Block mehr als doppelt so groß ist wie erforderlich, wird er halbiert. Ein Teil wird verwendet, der andere bleibt als „Buddy“ ungenutzt.
Wenn zwei „Buddy“-Blöcke wieder frei werden, werden sie zusammengeführt.
Vorteile:
Schnelle Zusammenfassung von freien Speicherblöcken, da nur die entsprechenden Zweierpotenz-Listen durchsucht werden müssen.
Nachteile:
Externe Fragmentierung kann auftreten.
Interne Fragmentierung: Wenn z.B. ein Prozess 33 Seiten benötigt, aber 64 belegt, entsteht ungenutzter Speicher (Rest bis zur nächsten Zweierpotenz).
Der Langzeit-Scheduler verwendet die Buddy-Zuweisungsstrategie für die Hauptspeicherzuweisung.
Speicher wird in Zweierpotenzen aufgeteilt. Ein Block wird verwendet, der mindestens so groß ist wie der benötigte Bereich. Falls der Block viel größer ist, wird er geteilt.
Schnelles Zusammenführen freier Blöcke.
Externe und interne Fragmentierung: Wenn z.B. 33 Seiten benötigt werden, werden 64 belegt, was zu ungenutztem Speicher führt.
Bei Linux wird die Hauptspeicherzuweisungsstrategie Buddy eingesetzt, wie funktioniert sie? Welche Fragmentierung hat diese Strategie?
Interne Fragmentierung: Wenn ein Prozess 33 Seiten benötigt, aber 64 Seiten belegt, entsteht ungenutzter Speicher (Rest zwischen 33 und 64 Seiten).
Externe Fragmentierung: Auch wenn halbierter Speicher (z.B. durch Buddy-Strategie) wieder frei ist, kann es schwierig werden, einen mittelgroßen Block zu finden, da nur Buddy-Blöcke kombiniert werden können.
Das bedeutet, dass viel Speicher frei sein kann, aber trotzdem keine passende Größe gefunden wird.
Interne Fragmentierung: Ein Prozess braucht 33 Seiten, belegt aber 64, also bleibt ungenutzter Speicher übrig.
Externe Fragmentierung: Obwohl Speicherbereiche frei sind, können sie nicht immer kombiniert werden, um einen mittelgroßen Block zu finden.
Was ist ein virtueller Speicher?
Virtueller Hauptspeicher:
Ein Prozess „glaubt“, er hat die CPU und den Hauptspeicher nur für sich.
Der Programmierer muss sich nicht um die physikalischen Adressen oder die Größe des Hauptspeichers kümmern.
Der Zugriff erfolgt über virtuelle Adressen, die durch MMU (Memory Management Unit) auf physische Adressen abgebildet werden, z.B. durch Paging.
Auslagerung (Swap-Bereich auf dem Sekundärspeicher) erlaubt es, mehr Programme als im tatsächlichen Hauptspeicher unterzubringen.
Ziel: Nur die benötigten Daten werden im Hauptspeicher gehalten, während der Rest ausgelagert wird.
Ein Prozess denkt, er hat den ganzen Speicher für sich. Programme können unabhängig vom physikalischen Speicher geschrieben werden.
Virtueller Hauptspeicher nutzt Paging und Auslagerung auf den Sekundärspeicher, um mehr Programme als im Hauptspeicher möglich wären zu halten.
sWie wird eine logische Adresse auf die physische Adresse abgebildet? Welche Hardware wird bei der Umrechnung gebraucht?
Basis- und Grenzregister (bei zusammenhängender Zuweisung) und Seitentabelle (bei Paging) befinden sich in der MMU (Memory Management Unit).
Diese Hardware-Einheiten verwalten die Umrechnung von virtuellen zu physikalischen Adressen.
MMUs ermöglichen es, die Vorteile von Segmentierung und Paging zu kombinieren (wenn in dieser Reihenfolge geschaltet).
Paging sorgt für einen großen virtuellen Adressraum (linear), der auf physische Adressen abgebildet wird, ohne externe Fragmentierung.
Segmentierung teilt den virtuellen Adressraum in mehrere unabhängige Segmente auf, wobei externe Fragmentierung nur im virtuellen Adressraum auftritt.
MMUs verwenden Basis- und Grenzregister (für zusammenhängende Zuweisung) und Seitentabellen (bei Paging), um virtuelle auf physische Adressen abzubilden.
Durch die Kombination von Segmentierung und Paging kann der Adressraum effizient genutzt werden:
Paging vermeidet externe Fragmentierung.
Segmentierung teilt den virtuellen Adressraum auf, wobei die Fragmentierung nur virtuell auftritt.
Was passiert, wenn eine Seite nicht im Hauptspeicher vorhanden ist?
Ein Prozess wird „rechnend“, auch wenn nicht alle seine Seitenrahmen im Hauptspeicher sind.
Fehlende Seiten im Sekundärspeicher werden über das „present-Bit“ in der Seitentabelle erkannt.
Bei einem Zugriff auf eine fehlende Seite entsteht ein Seitenfehler (page fault).
Die MMU löst eine Software-Unterbrechung aus (Trap), um die fehlenden Daten vom Sekundärspeicher in den Hauptspeicher zu laden.
„Demand paging“ bedeutet, dass Seiten erst bei Bedarf in den Hauptspeicher geladen werden.
Das „prepaging“, also das Vorausladen von Seiten, wäre ineffizienter und aufwendiger.
Ein Prozess wird auch dann aktiv, wenn nicht alle Seiten im Hauptspeicher sind.
Fehlende Seiten erkennt man am „present-Bit“ in der Seitentabelle.
Ein Seitenfehler (wenn eine Seite fehlt) löst eine Software-Unterbrechung aus, die die fehlenden Daten in den Hauptspeicher lädt.
„Demand paging“ lädt Seiten nur bei Bedarf, was effizienter ist als „prepaging“.
Was passiert, wenn der Hauptspeicher voll ist mit den Seiten? Was ist Auslagerung?
Auslagerung von Seiten: Wenn der Hauptspeicher voll ist, müssen alte Daten ausgelagert werden, um Platz für neue zu schaffen.
Optimale Auslagerungsstrategie: Die beste Strategie wäre es, die Seite auszulagern, die am weitesten in der Zukunft benötigt wird (um Seitenfehler zu minimieren).
Leider ist diese Information oft nicht verfügbar.
Least Recently Used (LRU): Eine gängige Strategie, die annimmt, dass die Seite, die am längsten nicht benutzt wurde, am wenigsten wahrscheinlich bald benötigt wird.
Dirty-Bit: Ein „Dirty-Bit“ in der Seitentabelle markiert modifizierte Seiten. Nur diese müssen auf den Sekundärspeicher zurückgeschrieben werden, wodurch unnötige Schreiboperationen vermieden werden.
Wenn der Hauptspeicher voll ist, müssen Daten ausgelagert werden.
Die optimale Strategie wäre, die Seite auszulagern, die am längsten nicht gebraucht wird.
LRU hilft, diese Entscheidung zu treffen, indem die zuletzt verwendete Seite als am wenigsten wichtig angenommen wird.
Ein Dirty-Bit zeigt, ob eine Seite verändert wurde. Nur diese muss auf die Festplatte zurückgeschrieben werden.
Welche Auslagerungsstrategien gibt es?
Optimale Strategie (OPT): Sie würde die Seiten auslagern, die entweder nie mehr oder für eine besonders lange Zeit nicht mehr benötigt werden. Diese Strategie ist jedoch nicht praktikabel, weil wir die zukünftigen Zugriffe nicht vorhersagen können.
LRU (Least Recently Used): Hier wird die Seite ausgelagert, die am längsten nicht verwendet wurde, basierend auf der Annahme der zeitlichen Lokalität (häufig gebrauchte Daten sind bald wieder erforderlich).
LFU (Least Frequently Used): Diese Strategie geht einen Schritt weiter als LRU, indem sie die Seite auslagert, auf die in einem bestimmten Zeitraum am wenigsten häufig zugegriffen wurde.
FIFO (First In First Out): Bei dieser Methode wird die älteste Seite zuerst ausgelagert. Leider führt dies dazu, dass häufig benötigte Seiten unnötig oft ausgelagert werden.
OPT ist theoretisch am besten, weil sie Seiten auslagert, die nie wieder gebraucht werden, aber ist nicht praktisch.
LRU nimmt die Seite, die am längsten nicht genutzt wurde, basierend auf dem Prinzip der zeitlichen Lokalität.
LFU schaut sich an, welche Seite am wenigsten oft genutzt wurde, und lagert diese aus.
FIFO löscht die älteste Seite, was aber dazu führen kann, dass oft genutzte Seiten unnötig ausgelagert werden.
Was limitiert die Größe des Virtuellen- bzw. des Prozess-Adressraums?
Länge/Breite der logischen Adressen:
Die logischen Adressen im Adressregister sind in höherwertige Bits und Segmentselektor-Adress-Bits unterteilt, wenn Segmentierung verwendet wird.
Einträge in der Seitentabelle:
Seitenrahmennummer: Gibt an, wo die Seite im physischen Speicher abgelegt ist.
Present-Bit: Kennzeichnet, ob die Seite im Hauptspeicher oder im Sekundärspeicher (z.B. Festplatte) liegt. Ein Seitenfehler (page fault) tritt auf, wenn dieses Bit für eine angeforderte Seite nicht gesetzt ist.
Dirty-Bit (Modified-Bit): Zeigt an, ob die Seite seit dem letzten Laden geändert wurde, sodass sie bei Bedarf in den Sekundärspeicher zurückgeschrieben werden muss.
Reference-Bit: Gibt an, ob die Seite seit der letzten Überprüfung referenziert wurde, um die Seitenersetzung zu steuern.
Weitere benötigte Informationen vom BS:
Adresse der Seite im Sekundärspeicher: Bei einem Seitenfehler muss das Betriebssystem wissen, wo die Seite im Sekundärspeicher (z.B. Festplatte) abgelegt ist, um sie bei Bedarf zurück in den Hauptspeicher zu laden.
Logische Adressen haben in der Regel höherwertige Bits, die mit Segmentselektoren belegt sein können.
Die Seitentabelle enthält:
Seitenrahmennummer: Wo die Seite im physischen Speicher liegt.
Present-Bit: Gibt an, ob die Seite im Hauptspeicher ist.
Dirty-Bit: Zeigt an, ob die Seite verändert wurde.
Reference-Bit: Zeigt, ob die Seite genutzt wurde.
Um den virtuellen Speicher zu realisieren, muss das Betriebssystem die Adresse der Seite im Sekundärspeicher kennen.
Nach welchen Kriterien könnte man die auszulagernde Seite auswählen?
Z.B. gemäß Least Recently Used (LRU).
LRU (Least Recently Used) ist eine Seitenersetzungsstrategie, bei der die Seite, die am längsten nicht verwendet wurde, aus dem Hauptspeicher entfernt wird, wenn neuer Platz benötigt wird. Dies basiert auf dem Prinzip der zeitlichen Lokalität: Zu den zuletzt verwendeten Seiten wird in naher Zukunft vermutlich wieder zugegriffen.
Wichtige Merkmale von LRU:
Es wird die Seite ausgelagert, auf die am längsten nicht zugegriffen wurde.
Die Referenzierungshistorie wird verwendet, um festzustellen, welche Seiten zuletzt verwendet wurden.
Vorteil: LRU ist ein relativ guter Näherungswert für die optimale Strategie, da es Seiten mit geringerer Zugriffshäufigkeit bevorzugt.
Nachteil: Die Implementierung kann teuer sein, da die Zugriffszeiten für alle Seiten überwacht werden müssen, um zu bestimmen, welche Seite am längsten nicht benutzt wurde.
Kurz gesagt:
LRU entfernt die Seite, die am längsten nicht verwendet wurde.
Welches Kriterium gibt es für Seiten, die ausgelagert werden noch neben der Auslagerungsstrategie?
Werte von Dirty-Bit (Modified-Bit) und Present-Bit.
Die Seitentabelle enthält mehrere wichtige Bits, darunter das Dirty-Bit (auch Modified-Bit) und das Present-Bit. Hier sind ihre Bedeutungen:
Present-Bit:
Wert: 1 oder 0
Bedeutung:
1: Die Seite ist derzeit im Hauptspeicher vorhanden.
0: Die Seite ist nicht im Hauptspeicher und befindet sich im Sekundärspeicher (z. B. Festplatte). Ein Seitenfehler (page fault) wird ausgelöst, wenn versucht wird, auf diese Seite zuzugreifen, und sie muss in den Hauptspeicher geladen werden.
Dirty-Bit (Modified-Bit):
1: Die Seite wurde modifiziert, d. h., sie wurde seit dem letzten Laden oder der letzten Speicherung geändert. Diese Seite muss beim Entfernen oder Auslagern in den Sekundärspeicher zurückgeschrieben werden.
0: Die Seite wurde nicht verändert und muss beim Entfernen oder Auslagern nicht in den Sekundärspeicher geschrieben werden.
Zusammengefasst:
1: Seite im Hauptspeicher.
0: Seite im Sekundärspeicher (Page Fault).
Dirty-Bit:
1: Seite wurde verändert (muss auf die Festplatte geschrieben werden).
0: Seite wurde nicht verändert (keine Speicherung nötig).
Ein Prozess braucht Speicherplatz im Hauptspeicher. Welche Zuweisungsverfahren gibt es?
Hier eine kurze Erklärung der verschiedenen Speichermanagement-Techniken, die du erwähnt hast:
Strategie: Sucht den ersten freien Speicherblock, der groß genug ist, um den angeforderten Bereich aufzunehmen.
Vorteil: Einfach und schnell in der Implementierung.
Nachteil: Kann zu externer Fragmentierung führen, da freie Blöcke zufällig aufgeteilt werden und möglicherweise nicht optimal genutzt werden.
Strategie: Sucht den kleinsten verfügbaren Speicherblock, der groß genug ist, um die angeforderte Speichergröße zu erfüllen.
Vorteil: Bessere Ausnutzung des Speichers als First Fit, da die kleineren freien Blöcke besser gefüllt werden.
Nachteil: Kann zu interner Fragmentierung führen, und die Suche nach dem besten Block kann aufwendig sein. Außerdem bleibt bei vielen kleinen Blöcken viel ungenutzter Speicher übrig.
Kompaktifizierung: Dies ist der Prozess, bei dem der Speicher reorganisiert wird, um die durch Fragmentierung entstandenen Lücken zu schließen und so eine effizientere Nutzung des Speichers zu ermöglichen.
Strategie: Der Speicher wird in Blöcke geteilt, deren Größe eine Zweierpotenz ist (z. B. 1 KB, 2 KB, 4 KB, 8 KB, etc.). Wenn ein Block größer als benötigt ist, wird er in zwei gleich große Blöcke (sogenannte „Buddies“) geteilt. Wenn zwei benachbarte „Buddies“ wieder frei werden, können sie wieder zu einem größeren Block zusammengefasst werden.
Vorteil: Einfache Implementierung, schnelle Reorganisation durch das Zusammenfügen benachbarter Blöcke.
Nachteil: Kann zu interner Fragmentierung führen, wenn die Blockgröße nicht perfekt zu den Anforderungen eines Prozesses passt.
Strategie: Der Hauptspeicher wird in gleich große Blöcke, sogenannte „Seitenrahmen“, unterteilt. Der virtuelle Adressraum eines Prozesses wird in gleich große „Seiten“ unterteilt, die dann über eine Seitentabelle auf die physischen Seitenrahmen abgebildet werden.
Vorteil: Eliminierung externer Fragmentierung, da die Seiten beliebig im Hauptspeicher verteilt werden können.
Nachteil: Es kann interne Fragmentierung innerhalb der Seitenrahmen geben, und das Verfahren erfordert Verwaltungsaufwand für die Seitentabelle.
LRU (Least Recently Used): Ein Algorithmus zur Verwaltung der Seiten, der die Seite auswählt, die am längsten nicht genutzt wurde, um sie bei Bedarf auszulagern (bei einem „Seitenfehler“).
Vorteil: Basierend auf der zeitlichen Lokalität von Programmen, häufig genutzte Seiten bleiben im Speicher.
Nachteil: Kann zu hohem Verwaltungsaufwand führen und erfordert zusätzliche Hardware-Unterstützung, um die „gebrauchten“ Seiten zu verfolgen.
Demand Paging: Seiten werden nur dann in den Hauptspeicher geladen, wenn sie benötigt werden (d.h. bei einem Seitenfehler). Dies spart Speicherplatz und vermeidet das Laden unnötiger Daten.
Vorteil: Spart Ressourcen, indem nur die wirklich benötigten Seiten geladen werden.
Nachteil: Seitenfehler können zu Verzögerungen führen, wenn ständig neue Seiten geladen werden müssen.
OPT (Optimal): Eine theoretische Strategie, bei der die Seite ausgelagert wird, die am weitesten in der Zukunft nicht benötigt wird. Diese Strategie ist ideal, jedoch praktisch nicht umsetzbar, da zukünftige Zugriffe nicht bekannt sind.
Vorteil: Theoretisch optimal, da sie Seitenfehler minimiert.
Nachteil: Praktisch nicht anwendbar, da zukünftige Anforderungen nicht bekannt sind.
Zusammenfassung:
First Fit und Best Fit sind einfache Strategien zur Speicherzuweisung, wobei Best Fit effizienter sein kann, aber auch mehr Aufwand für die Suche nach dem besten Block erfordert.
Das Buddy-System bietet eine effiziente Verwaltung von zusammenhängenden Speicherblöcken, wobei die Blöcke in der Größe einer Zweierpotenz unterteilt werden.
Paging und LRU (Least Recently Used) sind für virtuelle Speicherverwaltung zuständig, um Speicher effizient zu nutzen und die Speicherverwaltung dynamisch anzupassen. Demand Paging sorgt dafür, dass nur benötigte Seiten in den Speicher geladen werden, während OPT eine ideale, aber unpraktische Strategie ist, die nicht umgesetzt werden kann.
Jede dieser Strategien hat ihre eigenen Vor- und Nachteile, die in unterschiedlichen Szenarien und mit verschiedenen Anforderungen an die Systemressourcen abzuwägen sind.
Was sind die Vorteile von Paging?
Hier ist eine detaillierte Erklärung der Merkmale, die du angesprochen hast:
Bedeutung: Externe Fragmentierung tritt auf, wenn es viele kleine ungenutzte Speicherbereiche im Hauptspeicher gibt, die zusammen nicht ausreichen, um neue Anforderungen zu erfüllen, obwohl insgesamt noch genügend freier Speicher vorhanden ist.
Lösung: Bei Paging (insbesondere mit Seitenrahmen und Seitentabellen) gibt es keine externe Fragmentierung, da der Hauptspeicher in gleich große Blöcke (Seitenrahmen) unterteilt wird. Die Seiten des virtuellen Adressraums eines Prozesses können an beliebigen Stellen im physischen Speicher abgelegt werden, ohne dass benachbarte Speicherbereiche erforderlich sind.
Vorteil: Der Speicher wird effizienter genutzt, da freie Blöcke beliebig genutzt werden können.
Bedeutung: Die Verwaltung des Speichers umfasst die Zuordnung und Freigabe von Speicherbereichen, um sicherzustellen, dass Programme korrekt ausgeführt werden können.
Lösung: Paging und das Buddy-System sind Beispiele für Strategien, die eine einfache Verwaltung ermöglichen.
Beim Paging erfolgt die Verwaltung durch Seitentabellen, die das Mapping des virtuellen Adressraums auf den physischen Adressraum ermöglichen. Jede Seite hat einen festgelegten Rahmen im Hauptspeicher, was die Verwaltung vereinfacht und den Overhead durch Fragmentierung reduziert.
Das Buddy-System teilt den Speicher in Blöcke der Größe einer Zweierpotenz, was ebenfalls eine einfache und schnelle Zuweisung und Freigabe ermöglicht.
Vorteil: Die Verwaltung ist schneller und weniger fehleranfällig, da der Speicher in gleich große Einheiten unterteilt wird.
Bedeutung: Virtueller Hauptspeicher ist ein Konzept, das es ermöglicht, mehr Programme im Speicher zu halten, als physisch verfügbar ist. Dies wird durch Auslagerung (Swapping) von Seiten auf den Sekundärspeicher ermöglicht.
Lösung: Bei Paging wird der virtuelle Adressraum eines Prozesses in gleich große Seiten unterteilt, die bei Bedarf im Hauptspeicher abgelegt werden. Wenn der Hauptspeicher voll ist, können Seiten auf den Sekundärspeicher (z. B. Festplatte) ausgelagert werden. Der Seitenfehlermechanismus (page fault) sorgt dafür, dass Seiten bei Bedarf in den Speicher geladen werden.
Vorteil: Der virtuelle Speicher erlaubt die Ausführung von mehr Programmen und größeren Programmen als der verfügbare physische Speicher, da Seiten bei Bedarf nachgeladen werden können.
Bedeutung: Gemeinsamer Speicher (Shared Memory) ermöglicht es mehreren Prozessen, auf denselben Speicherbereich zuzugreifen und Daten auszutauschen, ohne den Speicher jedes Mal kopieren zu müssen.
Lösung: Bei Paging können Prozesse gemeinsam genutzte Seiten verwenden, indem sie dieselben Seitenrahmen im physischen Speicher zugewiesen bekommen. Dies wird durch die Seitentabellen ermöglicht, die mehrere Einträge für den gleichen physischen Seitenrahmen haben können.
Wenn ein Prozess auf eine gemeinsame Seite zugreifen möchte, wird dies über die Seitenrahmennummer in der Seitentabelle realisiert, die den gleichen physischen Speicherbereich auf mehreren Tabellen abbildet.
Vorteil: Gemeinsame Nutzung von Daten zwischen Prozessen ist effizient, da keine unnötige Kopie der Daten vorgenommen werden muss, und es wird nur der physische Speicher genutzt.
Keine externe Fragmentierung: Da der Speicher in feste Seiten unterteilt ist, gibt es keine ungenutzten Lücken im Speicher.
Einfache Verwaltung des Hauptspeichers: Das Paging- und Buddy-System ermöglicht eine effiziente und schnelle Zuweisung und Verwaltung von Speicher.
Virtueller Hauptspeicher: Durch das Paging können Prozesse mehr Speicher nutzen, als tatsächlich im physischen Speicher vorhanden ist, durch Auslagerung auf den Sekundärspeicher.
Gemeinsam genutzte Seiten: Mehrere Prozesse können denselben Speicherbereich teilen, was den Ressourcenverbrauch minimiert und die Kommunikation zwischen Prozessen erleichtert.
Diese Merkmale machen die Paging-Technik und verwandte Speicherverwaltungstechniken äußerst effizient und praktikabel, um die Herausforderungen der Speicherverwaltung zu bewältigen.
Wie viele Zugriffe auf den Hauptspeicher werden bei Paging mindestens benötigt,
wenn ein Wort gebraucht wird?
Seitenadressübersetzung und zusätzlicher Speicherzugriff (Paging)
Problem ohne TLB (Translation Lookaside Buffer):
Bei der Verwendung von Paging muss der logische Speicher in physikalischen Speicher übersetzt werden.
Die Übersetzung erfolgt über eine Seitentabelle.
Ein weiterer Speicherzugriff ist nötig, um den Seiteneintrag zu finden und die physische Adresse zu berechnen.
Ablauf ohne TLB:
Die virtuelle Adresse wird in zwei Teile unterteilt:
Seitennummer (für die Seitentabelle)
Offset (Position innerhalb der Seite)
Die Seitennummer wird in der Seitentabelle nachgeschlagen.
Ein weiterer Zugriff auf den Speicher erfolgt, um die physische Adresse zu berechnen.
Mit TLB (Translation Lookaside Buffer):
Der TLB speichert die letzten Übersetzungen von virtuellen zu physischen Adressen.
TLB-Treffer vermeiden den Zusatzzugriff auf die Seitentabelle und beschleunigen den Prozess.
Ohne TLB: 2 Speicherzugriffe (Seitentabelle + physischer Speicher).
Mit TLB: 1 Speicherzugriff (direkt auf die physische Adresse).
Seitenadressübersetzung (Paging) und Speicherzugriffe:
Ohne TLB:
Zwei Zugriffe:
Zugriff auf die Seitentabelle.
Zugriff auf den physischen Speicher.
Mit TLB:
Der TLB speichert Adressübersetzungen und spart einen Zugriff, da er den Seitentabellenzugriff ersetzt.
Welche Probleme können entstehen, wenn man eine Seite (die Seitengröße) zu groß
oder zu klein wählt?
Klar, hier ist die Antwort in zwei Varianten:
Auswirkungen der Seitengröße auf die Fragmentierung und Seitentabelle
Größere Seiten:
Interne Fragmentierung:
Wenn eine Seite größer ist, besteht die Gefahr, dass mehr Speicherplatz ungenutzt bleibt.
Beispiel: Ein Prozess benötigt 5 KB, eine Seite ist aber 8 KB groß. Die verbleibenden 3 KB sind verschwendet (interne Fragmentierung).
Vorteil: Weniger Seitentabellen-Einträge nötig, weil der virtuelle Speicher mit weniger Seiten abgebildet wird.
Kleinere Seiten:
Geringere interne Fragmentierung:
Kleinere Seiten reduzieren den ungenutzten Speicher innerhalb der Seiten, weil die Seitengröße näher an den tatsächlichen Bedürfnissen des Prozesses liegt.
Beispiel: Ein Prozess benötigt 5 KB, eine Seite ist 4 KB groß. Es bleibt nur 1 KB ungenutzt.
Nachteil: Es wird eine größere Seitentabelle benötigt, da mehr Seiten für den gleichen virtuellen Speicherbereich notwendig sind.
Größere Seiten: Weniger Einträge in der Seitentabelle, aber höhere interne Fragmentierung.
Kleinere Seiten: Weniger interne Fragmentierung, aber mehr Einträge in der Seitentabelle.
Einfluss der Seitengröße auf Fragmentierung und Seitentabelle:
Große Seiten:
Mehr interne Fragmentierung (verwendeter Speicher passt nicht perfekt zur Seitengröße).
Weniger Seitentabellen-Einträge.
Kleine Seiten:
Weniger interne Fragmentierung.
Mehr Seitentabellen-Einträge.
Ich hoffe, das hilft dir weiter! Die Struktur ist so gewählt, dass du die wichtigsten Punkte schnell erfassen kannst. Wenn du etwas noch weiter präzisieren möchtest, lass es mich wissen.
Was ist der Ansatz vom virtuellen Speicher?
Virtueller Hauptspeicher: Vorteile, Nachteile und Lösungen
Der virtuelle Hauptspeicher ermöglicht es, dass Programme unabhängig von der tatsächlichen Größe des physischen Hauptspeichers geschrieben werden können. Nur die Seiten, die aktuell gebraucht werden, befinden sich im Hauptspeicher, während der Rest im Sekundärspeicher (z.B. Festplatte) bleibt. Dies führt zu einigen wichtigen Vorteilen, aber auch zu Herausforderungen, die gelöst werden müssen.
Unabhängigkeit von Programmen und Rechnern: Programme können ohne Wissen über die physische Größe des Hauptspeichers geschrieben werden.
Effiziente Speicherverwaltung: Nur die gerade benötigten Seiten sind im Hauptspeicher, der Rest wird ausgelagert.
Speicher-Zugriffsschutz: Es können Mechanismen wie das Seitenfehler-Handling und der Speicherschutz integriert werden, um den Zugriff auf nicht autorisierte Bereiche zu verhindern.
Zusätzliche Hardwareanforderungen: Die MMU (Memory Management Unit) und die Verwaltung der Seitentabellen erfordern zusätzliche Ressourcen.
Verlangsamung durch Paging: Der häufige Austausch von Seiten zwischen Hauptspeicher und Sekundärspeicher kann die Performance verringern (insbesondere bei Page Faults).
Komplexität der Verwaltung: Die Verwaltung des virtuellen Speichers ist komplexer als die einfache Zuweisung des physischen Hauptspeichers.
Probleme bei der Realisierung des virtuellen Hauptspeichers:
Wann soll eine Seite in den Hauptspeicher geholt werden?
Dies wird durch Demand Paging erreicht, was bedeutet, dass Seiten nur dann in den Hauptspeicher geladen werden, wenn sie tatsächlich gebraucht werden (also bei einem Page Fault).
Welche Seite soll ausgelagert werden, wenn der Hauptspeicher voll ist?
Hier gibt es verschiedene Strategien wie Least Recently Used (LRU) oder Optimal Page Replacement (OPT), die bestimmen, welche Seite die geringste Priorität hat und daher ausgelagert werden sollte.
Zusammenfassung: Der virtuelle Hauptspeicher bietet Vorteile wie Unabhängigkeit von Programmen und Speicher-Zugriffsschutz, bringt aber auch Verlangsamung und Verwaltungsaufwand mit sich. Die beiden wichtigsten Probleme sind:
Wann Seiten in den Hauptspeicher geladen werden: Durch Demand Paging.
Welche Seiten ausgelagert werden, wenn der Speicher voll ist: Hier helfen Algorithmen wie LRU.
Programme benötigen keine Kenntnis der Hauptspeichergröße.
Nur benötigte Seiten sind im Hauptspeicher.
Schutzmechanismen für den Speicherzugriff.
Mehr Hardware- und Verwaltungsaufwand.
Leistungseinbußen durch häufige Page Faults.
Probleme:
Wann Seiten laden? – Mit Demand Paging, wenn sie gebraucht werden.
Welche Seite auslagern? – Durch Algorithmen wie LRU.
Das hilft hoffentlich, die wichtigsten Punkte zu merken! Wenn du noch eine andere Antwortform wünschst oder etwas angepasst haben möchtest, lass es mich wissen.
Was ist ein Seitenfehler? Was passiert, wenn eine Seite nicht im Hauptspeicher
vorhanden ist? Wie wird ein Seitenfehler behandelt? Welche Aktionen gibt es, um die
fehlende Seite in den Hauptspeicher zu holen? Was tut man, wenn alle Seitenrahmen
belegt sind?
Ein Seitenfehler (Page Fault) tritt auf, wenn ein Programm auf eine Seite zugreifen möchte, die sich nicht im Hauptspeicher befindet. In diesem Fall muss das Betriebssystem diese Seite aus dem Sekundärspeicher (z.B. Festplatte) in den Hauptspeicher laden, was als Demand Paging bezeichnet wird. Falls der Hauptspeicher bereits voll ist, muss das Betriebssystem eine Seite verdrängen, um Platz für die neue Seite zu schaffen – häufig unter Verwendung des LRU-Algorithmus (Least Recently Used).
Wie merkt das Betriebssystem, dass eine Seite nicht im Hauptspeicher liegt?
Das Betriebssystem nutzt das Present-Bit in der Seitentabelle des Prozesses.
Wenn das Present-Bit den Wert 0 hat, bedeutet dies, dass die Seite nicht im Hauptspeicher vorhanden ist.
Ein Seitenfehler wird durch diesen Zustand ausgelöst, und das Betriebssystem lädt die Seite aus dem Sekundärspeicher.
Ein Seitenfehler tritt auf, wenn das Betriebssystem feststellt, dass eine benötigte Seite nicht im Hauptspeicher liegt.
Das Present-Bit im Eintrag der Seitentabelle gibt an, ob eine Seite im Hauptspeicher ist. Wenn es auf 0 steht, wird die Seite nachgeladen.
Ein Seitenfehler tritt auf, wenn eine Seite nicht im Hauptspeicher liegt. Das Betriebssystem erkennt dies, wenn das Present-Bit in der Seitentabelle den Wert 0 hat.
Wozu braucht man einen Stack?
Das Sichern von Kontexten bei Unterbrechungen und Funktionsaufrufen ist eine wesentliche Aufgabe in der Speicherverwaltung und Prozesssteuerung. Wenn eine Unterbrechung (Interrupt) oder ein Funktionsaufruf (z.B. durch einen Systemaufruf oder eine Unterroutine) den aktuellen Prozess unterbricht, muss der Prozesskontext (d.h. der Zustand des Prozesses, einschließlich Register und Statusinformationen) gesichert werden, damit der Prozess später an der Stelle fortgesetzt werden kann, an der er unterbrochen wurde.
Dieser Kontext wird häufig in einem speziellen Speicherbereich (z.B. dem Stack) abgelegt und enthält:
Registerwerte: Der Zustand der Register (z.B. Accumulator, Program Counter).
Statusinformationen: Informationen über den aktuellen Zustand des Prozesses.
Stackpointer: Der Punkt, an dem der Stack der aktuellen Funktion oder des Prozesses endet.
Es ermöglicht es dem Betriebssystem oder der Hardware, einen sicheren Kontextwechsel zu vollziehen, ohne dass Daten verloren gehen.
Unterbrechungen (z.B. Hardware-Interrupts) oder Funktionsaufrufe (z.B. bei der Ausführung von Systemfunktionen) können den laufenden Prozess unterbrechen. Der gesicherte Kontext sorgt dafür, dass nach der Rückkehr aus der Unterbrechung oder dem Funktionsaufruf die Ausführung des Programms ohne Datenverlust fortgesetzt werden kann.
Kontext sichern = Speichern der aktuellen Prozessorregister und Statusinformationen.
Ziel: Wiederherstellung des Prozesszustands nach einer Unterbrechung oder Funktionsaufruf, um die Ausführung fortzusetzen.
Das Sichern des Kontextes bei Unterbrechungen und Funktionsaufrufen bedeutet, den aktuellen Zustand des Prozesses zu speichern (z.B. Registerwerte und Status), um die Ausführung später fortzusetzen.
Welche Strategien und Mechanismen „benutzt“ ein Betriebssystem?
Abstraktion und Kapselung:
Abstraktion bedeutet, komplexe Details zu verstecken und nur die relevanten Informationen bereitzustellen. In der Computertechnik können dies virtuelle Geräte oder auch virtuelle Maschinen sein, bei denen die physikalischen Eigenschaften eines Geräts abstrahiert werden, um eine einfachere Nutzung und Portabilität zu ermöglichen.
Kapselung bezieht sich darauf, dass bestimmte Implementierungsdetails verborgen werden, sodass nur die Schnittstellen sichtbar sind. So können Programmierer und Benutzer mit klar definierten Schnittstellen interagieren, ohne sich mit der internen Funktionsweise befassen zu müssen.
Schichtenmodell und Architekturmodell:
Schichtenmodelle (wie das OSI-Modell in der Netzwerkarchitektur) strukturieren die Software oder Hardware in aufeinanderfolgende Schichten, die jeweils eine spezielle Aufgabe übernehmen. Jede Schicht kommuniziert nur mit der angrenzenden Schicht.
Architekturmodelle wie das ISA (Instruction Set Architecture) definieren die grundlegenden Instruktionen und Operationen, die ein Prozessor ausführen kann.
Schnittstellen und Protokolle:
Schnittstellen sind die klar definierten Punkte, an denen verschiedene Softwarekomponenten miteinander kommunizieren. Sie können als Programmierschnittstellen (APIs) oder Benutzerschnittstellen auftreten.
Protokolle legen fest, wie Daten zwischen den verschiedenen Komponenten (wie Geräten oder Softwaremodulen) ausgetauscht werden. Sie sorgen für die korrekte Kommunikation und Handhabung von Daten.
Speicher-Hierarchie und Dateisysteme:
Die Speicher-Hierarchie organisiert Speicher von schnellen, aber teuren (wie Caches) zu langsameren, aber größeren und günstigeren (wie Festplatten). Diese Hierarchie optimiert den Zugang zu Daten.
Dateisysteme ermöglichen die Organisation und Verwaltung von Daten auf einem Speichermedium. Sie bieten eine Struktur für das Speichern und Abrufen von Dateien.
Prozesse und Prozesszustände:
Prozesse sind Programme, die ausgeführt werden, und können verschiedene Prozesszustände wie „laufend“, „bereit“ oder „blockiert“ haben.
Prozess-Synchronisation (z.B. mit Semaphoren) stellt sicher, dass mehrere Prozesse nicht gleichzeitig auf dieselben Ressourcen zugreifen und somit Inkonsistenzen entstehen.
Scheduling-Strategien:
Scheduling-Strategien definieren, wie der Betriebssystem-Prozessor Zeit unter den verschiedenen Prozessen aufteilt. Beispiele: Round-Robin, First-Come-First-Serve (FCFS).
Hauptspeicherverwaltung und virtueller Speicher:
Hauptspeicherverwaltung stellt sicher, dass Programme den verfügbaren RAM effizient nutzen.
Virtueller Speicher gibt dem Benutzer und dem Programmierer den Eindruck, dass mehr Speicher vorhanden ist, als tatsächlich physisch verfügbar ist. Dies wird durch das Auslagern von Seiten auf Festplatten realisiert.
Gerätetreiber:
Gerätetreiber sind Programme, die es dem Betriebssystem ermöglichen, mit spezifischen Hardwarekomponenten zu interagieren. Sie übersetzen allgemeine Betriebssystemaufrufe in hardware-spezifische Befehle.
Rollen und Zielgruppen:
Benutzer: Verwenden Software und Geräte und interagieren mit der Benutzeroberfläche.
Anwendungsprogrammierer: Entwickeln Software, die auf Betriebssystemressourcen zugreift.
Systemadministrator: Verwaltet und konfiguriert das Betriebssystem und die Hardware eines Systems.
Systementwickler: Entwickeln Betriebssysteme, Gerätetreiber und Low-Level-Software.
Abstraktion und Kapselung sorgen für einfache und saubere Schnittstellen.
Schichtenmodelle und Architekturmodelle definieren die Struktur von Software und Hardware.
Schnittstellen, Protokolle, Speicher-Hierarchie und Dateisysteme ermöglichen eine effiziente und organisierte Datenverarbeitung.
Prozesse, Prozesszustände, Synchronisation und Scheduling verwalten die Ausführung von Programmen.
Hauptspeicher und virtueller Speicher optimieren den Zugriff auf Daten.
Gerätetreiber ermöglichen die Kommunikation mit Hardware.
Abstraktion und Kapselung verstecken Details und bieten einfache Schnittstellen.
Schichtenmodelle und Architekturmodelle strukturieren Software und Hardware.
Protokolle und Schnittstellen regeln die Kommunikation zwischen Komponenten.
Speicher-Hierarchie und Dateisysteme optimieren den Datenspeicher.
Prozesse und Scheduling steuern die Programmausführung.
Virtueller Speicher gibt den Eindruck von mehr Speicher, als vorhanden ist.
Gerätetreiber ermöglichen die Interaktion mit Hardware.
Programme brauchen keine Details des Hauptspeichers zu kennen.
Nur benötigte Daten sind im Hauptspeicher.
Sichere Kommunikation zwischen Softwarekomponenten.
Komplexe Verwaltung von Speicher und Prozessen.
Hohe Anforderungen an das Betriebssystem.
Was ist ein Thread? Was sind Threads?
Was sind Threads?
Threads (auch als Fäden bezeichnet) sind leichtgewichtige Prozesse, die im Vergleich zu schwergewichtigen Prozessen eine geringere Systemressourcen benötigen.
Threads teilen sich denselben Adressraum, dasselbe Programm und dieselben Ressourcen (z.B. Dateien), was bedeutet, dass sie auf denselben Speicher zugreifen können.
Zustandswechsel zwischen Threads:
Beim Wechsel zwischen Threads müssen im Vergleich zu Prozessen nur Registerinhalte wie:
Befehlszähler
Status-Register (mit S/U-Modus)
Prozess-Stackpointer
nicht jedoch der Adressraum-Kontext (d.h. keine virtuellen Adress-Caches werden "geflusht")
Dies macht den Kontextwechsel zwischen Threads viel schneller und ressourcenschonender als bei Prozessen, bei denen der gesamte Adressraum ebenfalls gespeichert werden müsste.
Task und Verteilung über Prozessorkerne:
Mehrere Threads, die sich denselben Adressraum teilen und an einer gemeinsamen Aufgabe arbeiten, bilden eine Task.
Eine Task kann über mehrere Prozessorkerne verteilt werden, sodass parallele Ausführung und Optimierung der Nutzung der CPU möglich wird.
Sicherheit zwischen Threads:
Threads innerhalb eines Tasks dürfen sich nicht gegenseitig stören, da sie denselben Adressraum teilen.
Thread-individuelle Daten können nicht durch die MMU (Memory Management Unit) geschützt werden, was bedeutet, dass Daten aus einem Thread theoretisch von anderen Threads eingesehen und verändert werden können, sofern keine zusätzlichen Mechanismen wie Synchronisation angewendet werden.
Threads sind leichtgewichtige Prozesse, die sich denselben Adressraum und dieselben Ressourcen teilen.
Der Zustandswechsel zwischen Threads ist schneller als zwischen Prozessen, da nur Registerinhalte und nicht der gesamte Adressraum gespeichert werden müssen.
Mehrere Threads, die gemeinsam an einer Aufgabe arbeiten, bilden eine Task, die über mehrere Prozessorkerne verteilt werden kann.
Threads können nicht durch die MMU vor Zugriffen durch andere Threads geschützt werden, da sie denselben Adressraum teilen.
Threads sind leichte Prozesse, die denselben Adressraum und dieselben Ressourcen nutzen.
Beim Wechsel zwischen Threads werden nur Register gespeichert, nicht der gesamte Adressraum.
Mehrere Threads an einer Aufgabe bilden eine Task, die auch auf mehreren Kernen laufen kann.
Threads können sich gegenseitig stören, da sie denselben Speicher verwenden.
Schnellerer Kontextwechsel, da nur Register gesichert werden.
Mehrere Threads können parallel arbeiten und Ressourcen teilen.
Threads können sich gegenseitig stören, da sie denselben Speicher teilen.
Woraus besteht der Thread-Kontext?
Wichtige Register und deren Funktion:
Bei Kernel-Threads werden wie bei schwergewichtigen Prozessen die Registerinhalte gespeichert, um den Zustand des Threads zu sichern:
Befehlszähler (Programmzähler): Verfolgt die Adresse des nächsten auszuführenden Befehls.
Status-Register: Hält den Zustand des Threads (z.B. im S/U-Modus).
Prozess-Stapel: Beinhaltet Rücksprungadressen und lokale Daten.
Prozess Control Block (PCB): Enthält Thread-spezifische Informationen wie:
Threadnummer/ID
Priorität
Zustand (z.B. laufend, blockiert, bereit)
Adressräume und geteilte Daten:
Programm- und Daten-Adressräume sind nicht thread-spezifisch, d.h., alle Threads eines Tasks teilen sich den gleichen Adressraum.
Vorteil: Threads innerhalb eines Tasks können gemeinsam auf geteilte Daten zugreifen, was den Datenaustausch und die Kommunikation zwischen den Threads erleichtert.
Nachteil: Zugriffe auf gemeinsame Daten müssen durch Synchronisation geschützt werden, um Konflikte zu vermeiden.
Zugriffs- und Synchronisationsmechanismen:
Thread-eigene Daten sind durch den gemeinsamen Adressraum nicht voneinander getrennt, daher gibt es kein Speicherschutz zwischen den Threads.
Kooperatives Verhalten ist erforderlich, um zu verhindern, dass Threads auf die Daten anderer Threads zugreifen oder sie verändern.
Synchronisationstechniken wie Mutexe, Semaphoren oder Locks sind notwendig, um sicherzustellen, dass Threads nicht gleichzeitig auf dieselben Daten zugreifen und somit Datenkorruption verhindern.
Kernel-Threads speichern wie Prozesse wichtige Registerinhalte wie Befehlszähler, Status-Register, Prozess-Stapel und den Prozess Control Block.
Adressräume sind gemeinsam, was es den Threads ermöglicht, auf gemeinsame Daten zuzugreifen.
Synchronisation ist notwendig, um Zugriffs-Konflikte zu vermeiden.
Kein Speicherschutz zwischen Threads erfordert kooperatives Verhalten zur Vermeidung von Datenzugriffsproblemen.
Kernel-Threads speichern ihre Register und Prozessinformationen wie beim Prozess.
Alle Threads eines Tasks teilen sich Adressräume, was den Datenzugriff erleichtert.
Synchronisation ist notwendig, um Zugriffs-Konflikte auf gemeinsame Daten zu vermeiden.
Threads eines Tasks können gemeinsam auf geteilte Daten zugreifen.
Schnellerer Austausch von Daten zwischen Threads.
Kooperative Synchronisation nötig, um Datenzugriffsprobleme zu verhindern.
Kein Speicherschutz zwischen Threads, daher Gefahr von Zugriffsfehlern.
Was unterscheidet Threads von Prozessen? Was teilen sich Threads und was nutzen
sie exklusiv
Prozess vs. Thread:
Prozess: Hat einen eigenen Adressraum, der geschützt ist, und einen Ausführungspfad, der durch den Befehlszähler bestimmt wird. Ein Prozess kann mehrere Ausführungspfade haben, und jeder dieser Pfade ist ein Thread.
Thread:
Threads teilen sich:
Programm (Code),
Adressräume (z.B. Codesegment, Datensegment),
Dateien.
Jeder Thread hat jedoch:
Eigene Register (einschließlich Befehlszähler, Statusregister, Stack-Pointer).
Eigenen Stack-Bereich.
Gemeinsamer Adressraum und Kommunikation:
Threads eines Tasks teilen sich einen gemeinsamen Adressraum und können direkt über das gemeinsame RAM-Datensegment kommunizieren, was die Kommunikation sehr effizient und unkompliziert macht.
Vergleich Prozess- und Thread-Wechsel:
Der Aufwand beim Wechsel von einem Thread zu einem anderen ist viel geringer als beim Wechsel von Prozessen, weil beim Thread-Wechsel nicht der gesamte Adressraum und andere Daten wie beim Prozesswechsel gesichert werden müssen.
Prozesse: Eigenen Adressraum und Ausführungspfad.
Threads: Teilen sich Adressraum, Programm und Dateien, haben aber eigene Register und Stack.
Kommunikation: Unkompliziert über gemeinsames Datensegment.
Thread-Wechsel ist schneller und weniger aufwendig als ein Prozesswechsel.
Prozess: Eigenes Adressraum und Ausführungspfad.
Thread: Teilt sich Adressraum und Programm, aber hat eigene Register und Stack.
Kommunikation zwischen Threads ist einfach und schnell über das gemeinsame Datensegment.
Threads eines Tasks können über das gemeinsame Datensegment schnell kommunizieren.
Schnellerer Thread-Wechsel im Vergleich zu einem Prozesswechsel.
Threads teilen sich den Adressraum, daher müssen Zugriffe auf gemeinsame Daten gut synchronisiert werden.
Wann verwendet man Threads wann schwergewichtige Prozesse?
Verwendung von Threads:
Quasiparallele Bearbeitung: Wenn eine Aufgabe für verschiedene Clients effizient bearbeitet werden soll (z.B. Web- oder Datei-Server), können Threads genutzt werden. Jeder Thread kann für einen Client arbeiten, was den Parallelismus bei minimalem Aufwand ermöglicht.
Blockierende Aufrufe: Wenn ein Thread auf eine E/A-Operation wartet (z.B. Daten von der Festplatte liest), blockiert dieser Thread. Ein anderer Thread kann jedoch weiterarbeiten, sodass die Arbeit insgesamt nicht gestoppt wird. Dies ist eine der großen Stärken von Threads.
Kernel-Threads: Bei blockierenden Aufrufen, wie etwa E/A-Systemaufrufen, müssen Kernel-Threads verwendet werden, da diese vom Betriebssystem (im Gegensatz zu Benutzer-Threads) geplant und verwaltet werden. Dies sorgt dafür, dass die Effizienz von Quasiparallelität erreicht werden kann, da das Betriebssystem auch blockierte Threads verwalten kann.
Threads vs. Schwergewichtige Prozesse:
Threads sind besonders vorteilhaft, wenn an denselben gemeinsamen Daten im Hauptspeicher gearbeitet wird und eine schnelle Kommunikation über das gemeinsame Datensegment erforderlich ist. Threads bieten eine effizientere Kommunikation als Prozesse, da sie den gleichen Adressraum teilen.
Schwergewichtige Prozesse: Diese sind vorteilhaft, wenn Aufgaben mit geschützten (nicht „shared“) Daten erledigt werden müssen, da jeder Prozess seinen eigenen, isolierten Adressraum hat.
Effizienz und Kontextwechsel:
Threads sind insgesamt effizienter, weil der Kontextwechsel innerhalb eines Tasks viel schneller erfolgt als bei einem vollständigen Prozesswechsel.
Bei schwergewichtigen Prozessen wird der Kontextwechsel durch den separaten Adressraum teurer, aber die Daten sind besser geschützt.
Threads: Ideal für quasiparallele Aufgaben und E/A-blockierende Operationen. Sie teilen sich den Adressraum und können effizient über das gemeinsame Datensegment kommunizieren.
Kernel-Threads sind notwendig, wenn blockierende Aufrufe (wie E/A) auftreten, da sie vom Betriebssystem verwaltet werden.
Schwergewichtige Prozesse: Nützlich bei Aufgaben mit geschützten Daten, wo Daten nicht mit anderen Prozessen geteilt werden sollen.
Threads: Für quasiparallele Aufgaben, E/A-Warten und gemeinsame Datennutzung.
Kernel-Threads: Bei blockierenden Aufrufen, da nur sie vom Betriebssystem verwaltet werden.
Schwergewichtige Prozesse: Bei Aufgaben mit geschützten (nicht geteilten) Daten.
Vorteile von Threads:
Effizienter bei quasiparalleler Bearbeitung.
Schnelle Kommunikation über gemeinsames Datensegment.
Geringerer Kontextwechsel-Aufwand als bei Prozessen.
Nachteile von Threads:
Threads teilen sich Adressraum – Risiko von Synchronisationsproblemen.
Schwergewichtige Prozesse: Nützlich, wenn geschützte (nicht geteilte) Daten notwendig sind.
Was macht der Systemaufruf fork?
Fork-Systemaufruf:
Der Fork-Aufruf erstellt eine exakte Kopie des Elternprozesses. Dies bedeutet, dass alle Registerinhalte, der Befehlszähler, der Adressraum (einschließlich Stack) sowie der Prozess Control Block (PCB) und auch Ressourcenlisten des Elternprozesses in den neuen Prozess (das Kind) kopiert werden.
Copy-on-Write (COW): Um die Effizienz zu steigern, erfolgt das Kopieren der Daten oft nicht sofort. Das heißt, anfangs werden die Daten nicht kopiert, sondern der Eltern- und der Kindprozess teilen sich dieselben Speicherseiten. Erst wenn einer der beiden Prozesse eine Seite verändert (also schreibend darauf zugreift), wird diese Seite kopiert. Dies wird als Copy-on-Write (COW) bezeichnet.
Lazy Copying: Es wird oft nicht sofort jeder einzelne Speicherbereich kopiert. Nur die Bereiche, die tatsächlich verändert werden (z.B. der Stack oder bestimmte Daten), werden bei Bedarf (später) kopiert.
Wichtige Aspekte bei fork:
fork
Adressraum: Der Kindprozess erhält einen identischen Adressraum, jedoch wird dieser später durch das Copy-on-Write-Verfahren angepasst, falls Änderungen vorgenommen werden.
Register & Stack: Der Befehlszähler, Registerinhalte und der Stack des Elternprozesses werden eins zu eins in den Kindprozess kopiert.
Effizienz: Das Copy-on-Write spart Speicher und Zeit, da nur bei einer tatsächlichen Änderung im Kindprozess Speicher kopiert wird.
Fork: Erstellt eine exakte Kopie des Elternprozesses.
Registerinhalte, Befehlszähler, Stack, und PCB werden kopiert.
Copy-on-Write: Nur veränderte Speicherbereiche werden bei Bedarf kopiert.
Lazy Copying: Speicher wird nicht sofort kopiert, sondern erst bei Bedarf.
Fork: Erstellt eine Kopie des Elternprozesses. Speicher wird mit Copy-on-Write kopiert, nur bei Änderungen im Kindprozess.
Effizienz: Lazy Copying sorgt dafür, dass nicht sofort alles kopiert wird.
Fork:
Kopie des Elternprozesses, einschließlich Register, Befehlszähler, Stack und PCB.
Copy-on-Write (COW): Nur bei Änderungen werden Speicherbereiche kopiert.
Lazy Copying: Kopieren geschieht nur bei Bedarf, spart Speicher und Zeit.
Könnte man z.B. einen Datei-Server auch ohne Threads, also nur mit einem
„schwergewichtigen“ Prozess realisieren?
Problemstellung: Blockieren vs. Nicht-Blockieren bei E/A-Funktionen:
Blockierende Aufrufe: Wenn ein E/A-Aufruf blockiert, wartet der gesamte Task oder Auftrag, bis die E/A abgeschlossen ist. Dies führt zu einem Stillstand des gesamten Prozesses, da alle Threads des Tasks blockiert sind.
Nicht-blockierende Aufrufe (Polling): Wenn man nicht-blockierende Aufrufe verwendet, muss der Prozess ständig nachsehen, ob die E/A abgeschlossen ist. Das führt zu einer expliziten Verwaltung der Auftragsstatus und bedeutet mehr Komplexität. Dieser Ansatz entspricht einem Polling-Verfahren, was den Ressourcenverbrauch erhöhen kann.
Problem bei der Verwendung von Benutzer-Threads:
Auch blockierende Systemaufrufe innerhalb von Benutzer-Threads blockieren den gesamten Task, was den gesamten Prozess lahmlegt. Das führt zu einer ineffizienten Nutzung der Ressourcen und einer schlechten Reaktionsfähigkeit des Systems.
Verwendung von schwergewichtigen Prozessen:
Wenn man auf mehrere schwergewichtige Prozesse zurückgreift, um Blockierungen zu vermeiden, entstehen hohe Kontextwechsel-Kosten, da beim Wechsel von Prozessen auch der Adressraum gewechselt werden muss. Dies kann besonders problematisch sein, da der gemeinsame Speicherbereich (z. B. für einen Datei-Server) viel effizienter genutzt werden könnte.
Elegante Lösung mit Threads:
Eine elegantere Lösung ist die Verwendung von mehreren Threads innerhalb eines Prozesses. Während ein Thread aufgrund eines E/A-Aufrufs blockiert, kann ein anderer Thread weiterhin arbeiten. Dadurch wird die Effizienz gesteigert und der E/A-Wartestatus effizienter gehandhabt, ohne den gesamten Prozess zu blockieren.
Blockierende Aufrufe: Blockieren den gesamten Task.
Nicht-blockierende Aufrufe: Erfordern explizite Verwaltung der Auftragsstatus, was Komplexität erhöht.
Schwergewichtige Prozesse: Hoher Kontextwechsel-Aufwand, da der Adressraum ständig gewechselt wird.
Threads: Erlauben parallele Arbeit und verhindern Blockierung des gesamten Tasks. Ideal für E/A-intensive Anwendungen.
Blockieren bei E/A-Aufrufen führt zu Stillstand des gesamten Tasks.
Nicht-blockierende Aufrufe erfordern explizite Statusverwaltung.
Schwergewichtige Prozesse sind teuer wegen häufiger Kontextwechsel.
Threads sind eine bessere Lösung: Einer blockiert, während der andere weiterarbeitet.
Blockieren bei E/A-Aufrufen: Blockiert gesamten Task.
Nicht-blockierende Aufrufe: Erfordern explizite Statusverwaltung (Polling).
Schwergewichtige Prozesse: Hoher Kontextwechsel-Aufwand.
Threads: Können parallel arbeiten – Blockierung wird vermieden. Ideal für E/A-intensive Aufgaben.
Was ist der Unterschied zwischen Benutzer-Threads und Kernel-Threads?
Leichtgewichtige Prozesse:
Kernel-Threads: Diese werden mit der Systemfunktion clone erzeugt. Sie teilen sich den Speicherbereich mit dem Erzeugerprozess (d.h. die Speicherbereiche werden geshared). Kernel-Threads werden vom Betriebssystem verwaltet (mit eigenem PCB) und sind im Wesentlichen wie schwergewichtige Prozesse zu behandeln.
clone
Benutzer-Threads: Diese werden im Anwenderkontext über Bibliotheksaufrufe verwaltet, was bedeutet, dass das Scheduling schnell und flexibel ist. Das Betriebssystem kennt die einzelnen Benutzer-Threads nicht, sondern behandelt den gesamten Task als einen einzigen schwergewichtigen Prozess.
Kernel-Threads: Werden über clone erstellt, teilen sich Speicher und werden vom Betriebssystem wie schwergewichtige Prozesse behandelt.
Benutzer-Threads: Werden über Bibliotheken im Anwenderbereich verwaltet und vom Betriebssystem nicht erkannt – es sieht nur den gesamten Task.
Kernel-Threads: Erzeugt mit clone, teilen sich den Speicher, werden vom Betriebssystem verwaltet.
Benutzer-Threads: Verwaltet im Anwenderbereich, Betriebssystem kennt nur den gesamten Task.
Kernel-Threads: Mit clone erstellt, teilen sich Speicher, vom OS verwaltet, eigenes PCB.
Benutzer-Threads: Im Anwenderbereich verwaltet, OS sieht nur gesamten Task als Prozess.
Was macht der Systemaufruf clone?
Clone eines leichtgewichtigen Prozesses (Kernel-Thread):
Beim Clonen eines Kernel-Threads wird der Programm-Code, das Codesegment, das Datensegment und alle verwendeten Ressourcen des Elternprozesses vererbt.
Wichtig: Der Programmzähler wird nicht geklont. Stattdessen kann ein Funktions-Pointer als Parameter übergeben werden, der auf das selbe Programmsegment zeigt, was eine direkte „Programmvererbung“ ermöglicht.
Clone: Vererbt Programm-Code, Datensegment und Ressourcen.
Kein Klonen des Programmcounters: Stattdessen Funktions-Pointer für direkte Vererbung.
Beim Clone werden Programm-Code, Codesegment und Datensegment vererbt, aber der Programmzähler nicht. Stattdessen zeigt ein Funktions-Pointer auf das gleiche Programm.
Clone: Vererbt Code, Segment und Ressourcen. Kein Klonen des Programmcounters – Funktions-Pointer für Programmvererbung.
Was wäre wenn die Threads eines Tasks sich den Stack teilen würden?
Problem beim Mischen von Thread-Kontexten:
Wenn Thread-Kontexte auf dem Stack miteinander vermischen, könnte es zu einem Prozess-Absturz kommen.
Ein Funktions-Parameter des vormals rechnenden Threads könnte z.B. fälschlicherweise als Rücksprungadresse interpretiert werden, was zu einem Fehler führt.
Vermischte Thread-Kontexte auf dem Stack können dazu führen, dass Funktions-Parameter falsch interpretiert werden und ein Prozess-Absturz auftritt.
Wenn Thread-Kontexte auf dem Stack durcheinander geraten, können Funktions-Parameter fälschlicherweise als Rücksprungadressen genutzt werden, was den Prozess zum Absturz bringt.
Vermischte Thread-Kontexte können dazu führen, dass Funktions-Parameter als Rücksprungadressen interpretiert werden und ein Prozess-Absturz auftritt.
Was sind parallele Prozesse?
Beschleunigung durch parallele Verarbeitung:
Berechnungen können durch Parallele Verarbeitung auf mehrere Prozesse oder Threads verteilt werden.
Diese Prozesse oder Threads greifen auf gemeinsam genutzte Daten (wie gemeinsame Variablen) zu, um die Rechenleistung zu erhöhen.
Durch das Aufteilen von Berechnungen auf mehrere Prozesse oder Threads mit gemeinsam genutzten Daten kann der Rechenprozess deutlich beschleunigt werden.
Parallele Prozesse oder Threads nutzen gemeinsam genutzte Daten und beschleunigen so die Berechnungen.
Parallele Verarbeitung von Berechnungen durch mehrere Prozesse oder Threads mit gemeinsam genutzten Daten kann die Rechenleistung steigern.
Warum herrschen Wettkampfbedingungen (Race Conditions) zwischen Prozessen,
wenn sie auf gemeinsame Daten bzw. die gleiche Variable zugreifen?
Problematik von "Read-Modify-Write"-Zugriffen:
Nicht atomare Operationen: Ein "Read-Modify-Write"-Zugriff besteht aus mehreren Instruktionen, die nicht unteilbar sind.
Inkonsistente Ergebnisse: Wenn mehrere Prozesse oder Threads fast gleichzeitig auf dieselbe gemeinsame Variable zugreifen, kann dies zu verfälschten Werten führen.
Prozesswechsel oder Multicore-Systeme können dies verstärken, indem sie zugleich auf die Variable zugreifen.
Die Reihenfolge der Zugriffe bestimmt, ob und wie die Variable verfälscht wird.
Bei nicht-atomaren Zugriffen auf gemeinsame Variablen können zeitnahe, nicht deterministische Zugriffe zu inkonsistenten Ergebnissen führen, wenn die Zugriffs-Reihenfolge nicht synchronisiert ist.
Mehrere Prozesse oder Threads greifen auf dieselbe Variable zu, und ohne Synchronisation können die Ergebnisse verfälscht werden.
Nicht-atomare "Read-Modify-Write"-Zugriffe auf gemeinsame Variablen können bei zeitgleichen Zugriffen durch mehrere Prozesse oder Threads zu verfälschten Werten führen.
Was ist ein kritischer Abschnitt (critical section)? Was ist Prozess-Synchronisation?
Kritischer Abschnitt und Race Condition:
Ein kritischer Abschnitt ist ein Abschnitt im Programm, in dem mehrere parallele Prozesse auf geteilte Ressourcen (z.B. eine gemeinsame Variable) zugreifen.
Race Condition: Entsteht, wenn parallele Prozesse gleichzeitig auf dieselbe Ressource zugreifen und dabei unteilbare Operationen nicht atomar ausführen. Dadurch kann der Inhalt der gemeinsamen Variablen verfälscht werden.
Vermeidung von Race Conditions:
Um Race Conditions zu verhindern, muss immer nur ein Prozess gleichzeitig auf den kritischen Abschnitt zugreifen.
Dies wird durch Synchronisation und den exklusiven Zugriff erreicht.
Eine Race Condition tritt auf, wenn parallele Prozesse gleichzeitig auf eine gemeinsame Ressource zugreifen und dabei die Atomarität der Operationen verletzt wird. Synchronisation stellt sicher, dass immer nur ein Prozess auf die Ressource zugreift.
Race Condition passiert, wenn mehrere Prozesse gleichzeitig auf dieselbe Ressource zugreifen und dabei die Operationen nicht atomar sind. Dies führt zu verfälschten Daten. Durch Synchronisation kann dies vermieden werden.
Race Condition: Entsteht, wenn parallele Prozesse gleichzeitig auf geteilte Ressourcen zugreifen, ohne die Atomarität zu gewährleisten. Synchronisation sorgt dafür, dass immer nur ein Prozess gleichzeitig darauf zugreift.
Warum kann der Scheduler das nicht bereits berücksichtigen und nur zum richtigen
Zeitpunkt einen Thread unterbrechen?
Scheduler und seine Aufgaben:
Der Scheduler wird aktiv, wenn eine Unterbrechung zu einem Prozesswechsel führt. Diese Unterbrechungen können jederzeit eintreten.
Keine Vorhersage: Der Scheduler hat keine Informationen über das zukünftige Verhalten der Prozesse. Eine Analyse des Programms (statisch oder dynamisch) hilft ihm nicht weiter.
Kein garantierter Ablaufplan: Der Scheduler kann nicht sicherstellen, dass ein Zeitscheiben-basierter Ablaufplan immer korrekt funktioniert.
Synchronisation: Der Scheduler ist nicht für die Synchronisation von Prozessen oder Threads zuständig. Diese Verantwortung liegt bei den Prozessen selbst.
Der Scheduler führt einen Prozesswechsel durch, wenn eine Unterbrechung erfolgt. Er kann nicht vorhersagen, wie sich Prozesse verhalten, und übernimmt keine Synchronisation.
Der Scheduler wird durch eine Unterbrechung aktiv und wechselt den Prozess. Er kann nicht vorhersagen, was als nächstes passiert, und ist nicht für die Synchronisation von Prozessen verantwortlich.
Scheduler: Reagiert auf Unterbrechungen und führt einen Prozesswechsel durch. Er kann keine Vorhersagen machen und ist nicht für die Synchronisation der Prozesse verantwortlich.
Was versteht man unter Synchronisation? Warum ist die Prozess-Synchronisation
wichtig? Wie kann man Prozess-Synchronisation realisieren? Wie funktioniert
Synchronisation?
Race Conditions und Synchronisation:
Race Conditions entstehen, wenn parallele Prozesse unvorhersehbar auf gemeinsame Daten zugreifen, z.B. auf eine gemeinsame Variable.
Problem: Eine atomare Operation (z.B. "Read-Modify-Write") wird durch einen parallelen Zugriff gestört und dadurch inkonsistent ausgeführt, was den Wert der Variablen verfälschen kann.
Lösung: Um race conditions zu vermeiden, muss immer nur ein Thread oder ein kritischer Abschnitt Zugriff auf eine gemeinsame Ressource haben.
Synchronisation: Dies wird durch exklusiven Zugriff erreicht, der verhindert, dass mehrere Threads gleichzeitig in einen kritischen Abschnitt eintreten.
Methoden: Zwei Funktionen - enter_critical_section() und leave_critical_section() - steuern den Eintritt und Austritt aus kritischen Abschnitten.
Race Conditions verhindern: Exklusiver Zugriff auf kritische Abschnitte durch Synchronisation.
Exklusiver Zugriff garantiert, dass nur ein Thread gleichzeitig in einem kritischen Abschnitt arbeitet.
Wenn mehrere Prozesse gleichzeitig auf die gleiche Variable zugreifen, kann es zu Fehlern kommen. Um dies zu verhindern, sorgt die Synchronisation dafür, dass immer nur ein Prozess gleichzeitig auf die Variable zugreift.
Race Condition: Fehler durch parallelen Zugriff auf dieselbe Variable.
Synchronisation: Verhindert race conditions, indem sie exklusiven Zugriff auf kritische Abschnitte garantiert.
Wie kann man unteilbare Operationen bei einem Einprozessorsystem realisieren? Wie
kann man (quasi-)gleichzeitige Zugriffe auf den Hauptspeicher verhindern? Was ist die
Gefahr dabei? Was tun bei Unterbrechungen im kritischen Abschnitt?
Blockierung des Schedulers und Jitter:
Auf Single-Core-Systemen kann der Zeitscheiben-Timer-Interrupt blockiert werden, um zu verhindern, dass der Scheduler während eines kritischen Abschnitts eingreift. Dies verhindert den Prozesswechsel und den damit verbundenen Parallelzugriff auf eine gemeinsame Variable.
Systemrechte erforderlich, um den Interrupt zu blockieren.
Gesamtes Scheduling wird blockiert, was das Echtzeitverhalten des Systems beeinträchtigt.
Es entsteht Jitter, also zeitliches Jittern, da auch hochpriorisierte Prozesse verzögert werden.
Bessere Lösung: Nutzung von atomaren Maschinencode-Instruktionen, die ohne Scheduler-Blockierung direkt auf Variablen zugreifen können.
Zeitscheiben-Interrupt-Blockierung: Verhindert Scheduler-Aufruf, aber blockiert das gesamte Scheduling und führt zu Jitter.
Atomare Maschinencode-Instruktionen: Bessere Lösung, da sie ohne Scheduler-Blockierung und ohne Jitter funktionieren.
Was ist die Synchronisation von Prozessen?
Synchronisation sorgt dafür, dass kritische Abschnitte (z.B. atomare Operationen) auf gemeinsamen Daten (wie einer gemeinsamen Variable) koordiniert und seriell ausgeführt werden.
Ziel der Synchronisation ist es, race conditions zu verhindern, die durch parallel laufende Prozesse entstehen können und Atomaritäts- sowie Konsistenzverletzungen verursachen würden.
Synchronisation: Verhindert race conditions, indem kritische Abschnitte seriell und koordiniert ausgeführt werden.
Welche Probleme können entstehen, wenn z.B. die Prozesse Beobachter und Berichterstatter nicht synchronisiert werden? Welche Probleme gibt es, wenn man die Prozesse Beobachter und Berichterstatter mit einer Synchronisationsvariablen switch synchronisiert? Was passiert, wenn die Variable switch mit Eins initialisiert wird und der Prozess Beobachter eine höhere Priorität beim Scheduling als der Prozess Berichterstatter hat?
Kritische Abschnitte & Deadlock:
Beobachter-Thread:
Der kritische Abschnitt liegt bei der Zeile Zähler := Zähler + 1.
Zähler := Zähler + 1
Problem: Der Berichterstatter könnte den Zähler ausgeben (print(Zähler)) und ihn dann auf 0 setzen, bevor der inkrementierte Wert zurückgeschrieben wird. Der Zähler würde also mit dem Wert 0 überschrieben, obwohl er bereits erhöht wurde.
print(Zähler)
0
Berichterstatter-Thread:
Der kritische Abschnitt umfasst print(Zähler) und Zähler := 0.
Zähler := 0
Problem: Der Beobachter könnte den Zähler zwischen diesen beiden Operationen inkrementieren, aber diese Änderungen gehen verloren, wenn der Zähler danach auf 0 gesetzt wird.
Synchronisation mit einer Variablen (switch):
switch
Eine Synchronisationsvariable sorgt für exklusiven Zugriff, aber:
Sie ermöglicht nur abwechselnden Zugriff, was zu Starvation führen kann (d.h., ein Thread könnte niemals Zugriff erhalten).
Problem: Das "geschäftige Warten" (busy waiting) sorgt dafür, dass der wartende Thread im Berechnungszustand bleibt und nie wirklich Pause macht.
Deadlock-Szenario:
Wenn switch mit 1 initialisiert wird:
1
Der Beobachter hat eine höhere Priorität und wartet aktiv, während der Berichterstatter niemals switch auf 0 setzen kann.
Es entsteht ein Deadlock, bei dem der Beobachter niemals weiterarbeiten kann, da er ständig auf switch wartet.
Beobachter-Thread: Der kritische Abschnitt ist Zähler := Zähler + 1. Der Berichterstatter könnte Zähler zuerst ausgeben und dann auf 0 setzen, bevor der Zähler den neuen Wert behält.
Zähler
Berichterstatter-Thread: Der kritische Abschnitt ist print(Zähler) und Zähler := 0. Der Beobachter könnte Zähler zwischen den beiden Zeilen erhöhen, aber der Wert wird durch Zähler := 0 überschrieben.
Synchronisation mit switch: Eine Synchronisationsvariable sorgt für exklusiven Zugriff, verhindert aber auch, dass ein Thread manchmal Zugriff bekommt (Starvation). Außerdem bleibt der wartende Thread beim „geschäftigen Warten“ aktiv.
Deadlock: Wenn switch auf 1 gesetzt wird und der Beobachter eine höhere Priorität hat, wartet der Beobachter ewig und der Berichterstatter kann nie auf switch setzen, was zu einem Deadlock führt.
Wie wird ein kritischer Abschnitt auf Anwenderebene realisiert?
Race Condition: Entsteht, wenn mehrere Prozesse gleichzeitig auf eine gemeinsame Ressource zugreifen und dabei inkonsistente Ergebnisse produzieren.
Lösung: Um sicherzustellen, dass immer nur ein Prozess auf einen kritischen Abschnitt zugreift, muss der exklusive Zugriff gewährleistet sein.
Methode: Semaphoren sind Synchronisationswerkzeuge, die helfen, den exklusiven Zugriff auf kritische Abschnitte zu steuern. Sie garantieren, dass immer nur ein Prozess gleichzeitig in einen kritischen Abschnitt eintritt.
Race Condition: Tritt auf, wenn mehrere Prozesse gleichzeitig auf dieselbe Ressource zugreifen.
Lösung: Stelle sicher, dass immer nur ein Prozess gleichzeitig in einen kritischen Abschnitt gelangt (exklusiver Zugriff).
Wie? Semaphoren helfen dabei, den exklusiven Zugriff auf kritische Abschnitte zu regeln.
Was ist ein Semaphor?
Semaphor S – Synchronisation im Betriebssystem:
Definition: Ein Semaphor ist eine vom Betriebssystem unterstützte Synchronisationsvariable, die eine Warteschlange verwaltet und die typischen Probleme von einfachen, applikationsseitigen Synchronisationsmechanismen vermeidet.
Funktionalität: Es ist ein Signalisierungskonzept zur Prozesssynchronisation, das ähnlich wie eine Verkehrsampel funktioniert.
Wichtige Merkmale:
Abstrakter Datentyp
Globale Zähl-Variable
Prozess-Warteschlange
Funktionen/Operationen:
init: Initialisiert das Semaphor.
down: Verringert den Zähler (wartet, falls der Zähler null ist).
up: Erhöht den Zähler und gibt ggf. einen wartenden Prozess frei.
Semaphor: Eine vom Betriebssystem unterstützte Synchronisationsvariable, die Prozesse steuert.
Wie funktioniert es? Wie eine Verkehrsampel für Prozesse, die auf eine Ressource zugreifen.
Wichtige Teile:
Zähler zur Steuerung des Zugriffs.
Warteschlange für wartende Prozesse.
Operationen:
down: Wartet oder reduziert den Zähler.
up: Erhöht den Zähler und weckt wartende Prozesse auf.
Was ist ein Semaphor (Kurstext)?
Semaphor: Dijkstra's Lösung für Ressourcenkontrolle
Entwicklung durch Dijkstra: Dijkstra entwickelte das Semaphor zur Lösung von Problemen, bei denen mehrere Prozesse oder Threads auf ein begrenztes Betriebsmittel zugreifen wollen (z.B. Speicherplätze, CPUs oder kritische Abschnitte).
Was ist ein Semaphor? Ein abstrakter Datentyp, der den Zustand eines Betriebsmittels mit einer Zählvariablen (count) und einer Warteschlange (W) verwaltet:
count: Anzahl verfügbarer Ressourcen.
W: Wartende Prozesse, die auf Ressourcen zugreifen wollen, wenn count gleich null ist.
down(S): Ein Prozess fordert eine Ressource an. Wenn keine Ressourcen verfügbar sind (count = 0), wird der Prozess blockiert und in die Warteschlange aufgenommen.
up(S): Ein Prozess gibt eine Ressource frei. Wenn Prozesse in der Warteschlange sind, wird einer von ihnen wieder aktiviert.
Wichtige Details:
Exklusiver Zugriff: Die down- und up-Operationen stellen sicher, dass immer nur ein Prozess auf die Ressourcen zugreift.
Optimierung: Diese Operationen sind atomar und laufen effizient, sodass der Jitter (zeitliche Verzögerung) minimal bleibt.
Warum ist es effektiv?
Die Synchronisation von kritischen Abschnitten wird vom Betriebssystem übernommen, wodurch race conditions vermieden werden.
Semaphor: Ein Semaphor steuert den Zugriff auf begrenzte Ressourcen, wie z.B. Speicher oder CPUs.
Wie funktioniert es?
count: Zeigt an, wie viele Ressourcen verfügbar sind.
W: Warteschlange für Prozesse, die auf eine Ressource warten.
down(S): Prozess fordert eine Ressource an, wird blockiert, wenn keine verfügbar ist.
up(S): Prozess gibt eine Ressource frei und weckt einen wartenden Prozess auf.
Synchronisation:
Semaphoren verhindern, dass mehrere Prozesse gleichzeitig auf die gleiche Ressource zugreifen.
Diese Operationen sind sehr schnell und effizient, was den Jitter minimiert.
Wie kommt ein Prozess wieder aus der Warteschlange eines Semaphors heraus, wenn er bei der Ausführung von down blockiert? Was macht dann der Prozess, der aus der Warteschlange eines Semaphors herauskommt?
Aufwecken eines Wartenden Prozesses durch up()
up()
Prozess im kritischen Abschnitt: Ein Prozess, der gerade den kritischen Abschnitt verlässt, ruft die up()-Operation auf.
Dies weckt den wartenden Prozess auf und versetzt ihn in den Zustand „bereit“.
Zählvariable (count):
Beim Aufwecken wird die Zählvariable um eins verringert, um den exklusiven Zugriff auf die Ressource zu gewährleisten.
Dies sorgt dafür, dass der wartende Prozess sofort in den kritischen Abschnitt eintreten kann, ohne erneut die down()-Operation durchlaufen zu müssen.
Fairness:
Durch diese Lösung wird Fairness garantiert. Ein wartender Prozess wird nicht dauerhaft blockiert, und die Zählvariable bleibt korrekt reserviert, ohne dass ein anderer Prozess ohne Grund bevorzugt wird.
Prozess wecken: Ein Prozess, der den kritischen Abschnitt verlässt, ruft up() auf, um einen wartenden Prozess aufzuwecken.
Zählvariable:
Die Zählvariable wird um eins verringert, sodass der wartende Prozess den kritischen Abschnitt betreten kann.
Diese Lösung stellt sicher, dass der wartende Prozess nicht dauerhaft blockiert wird und Fairness gewährleistet ist.
Welche Synchronisationsverfahren gibt es?
Synchronisationsvariablen vs. Semaphore
Synchronisationsvariablen (busy waiting):
Warten aktiv: Ein Prozess bleibt aktiv im Warteschleifen-Modus und wartet, bis eine Bedingung erfüllt ist.
Abwechselnd: Nur zwei konkurrierende Prozesse wechseln sich ab, was zu ineffizienter Nutzung der Systemressourcen führen kann.
Semaphore (blockierend):
Effizient: Semaphore blockieren Prozesse und lassen sie passiv warten, wodurch weniger Systemressourcen verbraucht werden.
Mehrere Konkurrenten: Ermöglicht den gleichzeitigen Zugriff von mehreren Prozessen (auch mehr als zwei) auf die kritische Ressource.
Synchronisationsvariablen:
Aktives Warten (busy waiting), nur zwei Prozesse wechseln sich ab.
Semaphore:
Blockierend und effizient.
Erlaubt mehreren Prozessen gleichzeitig den Zugriff auf eine Ressource.
Welche Vorteile hat ein Semaphor?
Vorteile von Semaphoren gegenüber Synchronisationsvariablen
Keine „busy waiting“: Wartende Prozesse werden blockiert und verbrauchen keine Ressourcen, anstatt aktiv zu warten.
Keine erzwungene Abwechselndkeit: Im Gegensatz zu Synchronisationsvariablen gibt es keine zwingende Reihenfolge, mit der Prozesse auf Ressourcen zugreifen müssen.
Kürzere kritische Abschnitte: Die kritischen Abschnitte, die durch die Funktionen down und up gesteuert werden, sind schneller, da sie auf Betriebssystem-Ebene implementiert und durch atomare Assembler-Instruktionen oder Interrupts optimiert sind.
Kein aktives Warten: Wartende Prozesse werden blockiert und sparen so Ressourcen.
Keine feste Reihenfolge: Prozesse müssen sich nicht abwechseln.
Schnelle kritische Abschnitte: Diese werden direkt im Betriebssystem und durch schnelle atomare Befehle umgesetzt.
Semaphore haben also auch einen kritischen Abschnitt, wie geht man damit um? Und wie sorgt das OS dafür?
Verhindern von Prozesswechseln in kritischen Abschnitten
Zeitgeber-Interrupt-Sperre (bei Single-Core CPUs): Ein Prozesswechsel während kritischer Abschnitte wird verhindert, um Konsistenz zu gewährleisten.
Atomare „read-modify-write“-Maschinenbefehle: Diese Befehle stellen sicher, dass die Semaphor-Operationen (down und up) ungestört und ohne Unterbrechungen ablaufen.
Interrupt-Sperre: Verhindert, dass der Prozess während kritischer Abschnitte unterbrochen wird.
Atomare Befehle: Sichern, dass die Semaphor-Operationen ohne Störungen laufen.
Enthält down einen kritischen Abschnitt?
Atomare Ausführung in Semaphor-Operationen
Wichtige Zeilen: In der up(S)-Operation müssen die Zeilen „if S.W ist nicht leer“ und „S.count := S.count +1“ zusammen atomar (unteilbar) ausgeführt werden.
up(S)
Wesentlich für die Korrektheit: Auch die „S.count := S.count +1“-Anweisung am Ende muss atomar ausgeführt werden, besonders wenn n > 1.
Die Zeilen „if S.W ist nicht leer“ und „S.count := S.count +1“ müssen als Einheit atomar ausgeführt werden.
S.count := S.count +1 muss ebenfalls atomar ausgeführt werden, besonders wenn mehrere Prozesse (n > 1) beteiligt sind.
Synchronisationsmöglichkeiten kritischer Bereiche mit einem Semaphor Code-Bsp. :
Binäre Nutzung eines Semaphors
Initialisierung: Der Semaphor S.count wird mit 1 initialisiert.
S.count
Synchronisation: Beide kritischen Abschnitte werden durch den Semaphor S synchronisiert.
S
Bedeutung: Der Semaphor wird in diesem Fall binär genutzt, d.h. es gibt nur zwei Zustände: 1 (verfügbar) oder 0 (blockiert).
Der Semaphor S.count startet bei 1.
Beide kritischen Abschnitte werden durch S synchronisiert.
Der Semaphor funktioniert hier binär: 1 für „frei“ und 0 für „blockiert“.
Was ist ein binärer Semaphor?
Binäre Semaphoren & Mutexe
Binäre Semaphoren: Ein Semaphor, der nur die Werte 0 und 1 annehmen kann.
Wird für gegenseitigen Ausschluss (mutual exclusion) genutzt.
Garantiert, dass immer nur ein Prozess gleichzeitig in den kritischen Abschnitt eintreten kann.
Mutexe:
Eine spezialisierte und erweiterte Form des binären Semaphors.
Ein Mutex funktioniert wie ein Schloss:
Der erste Prozess, der in den kritischen Abschnitt eintreten möchte, „schließt“ den Abschnitt (wird gelockt).
Der Prozess behält den Besitz über das Mutex und kann den Abschnitt mehrfach betreten.
Alle anderen Prozesse werden blockiert, bis der besitzende Prozess den Abschnitt wieder verlässt.
Binäre Semaphoren: Semaphoren, die nur 0 oder 1 sind, sorgen für gegenseitigen Ausschluss – nur ein Prozess kann den kritischen Abschnitt gleichzeitig betreten.
Ein Mutex ist wie ein Schloss.
Der erste Prozess, der einen Mutex erhält, kann mehrfach in den kritischen Abschnitt eintreten und blockiert andere Prozesse, bis er ihn verlässt.
Beim Erzeuger-Verbraucher-Problem treten Semaphore auf, deren Zählvariablen größere Werte als Eins annehmen können:
Lösung für Pufferverwaltung mit Semaphoren:
Semaphor „Frei“:
Initialisiert mit der Anzahl der verfügbaren Betriebsmittel (n).
Dient dazu, den Zugriff auf freie Plätze im Puffer zu steuern.
Bei jedem Zugriff des Erzeugers auf „down(Frei)“ und beim Freigeben eines Betriebsmittels „up(Frei)“ verwenden.
Semaphor „Belegt“:
Initialisiert mit 0.
Zählt die belegten Plätze im Puffer und verhindert, dass der Verbraucher mehr entnimmt als vorhanden.
Semaphor „Zugriff“:
Binärer Semaphor (nur 0 oder 1).
Synchronisiert den Zugriff auf den Puffer, sodass immer nur ein Prozess (Erzeuger oder Verbraucher) gleichzeitig auf den Puffer zugreifen kann.
Problem: Deadlock durch falsche Reihenfolge der Semaphore-Operationen:
Fehlerhafte Reihenfolge: Wenn die „Zugriff“-Operation außerhalb von „Frei“ und „Belegt“ platziert wird, könnte es zu einem Deadlock kommen.
Erzeuger-Deadlock: Wenn der Puffer voll ist, blockiert der Erzeuger und verhindert gleichzeitig, dass der Verbraucher entnimmt.
Verbraucher-Deadlock: Wenn der Puffer leer ist, blockiert der Verbraucher und verhindert gleichzeitig, dass der Erzeuger hinzufügt.
Semaphor „Frei“: Zählt die freien Plätze im Puffer und wird mit der Anzahl an Betriebsmitteln (n) initialisiert.
Semaphor „Belegt“: Zählt die belegten Plätze im Puffer und wird mit 0 initialisiert.
Semaphor „Zugriff“: Synchronisiert den Zugriff auf den Puffer, sodass immer nur ein Prozess gleichzeitig zugreift.
Fehler durch falsche Reihenfolge der Operationen:
Bei falscher Reihenfolge kommt es zu einem Deadlock, bei dem der Erzeuger blockiert und den Verbraucher daran hindert, zu entnehmen, oder der Verbraucher blockiert und den Erzeuger am Hinzufügen hindert.
Was ist ein Deadlock?
Deadlock durch falsche Reihenfolge von Semaphoren:
Fehlerhafte Reihenfolge:
Der Erzeuger-Prozess führt folgende Schritte aus:
down(Zugriff) – Zugriff auf den Puffer.
down(Zugriff)
down(Frei) – Freien Platz im Puffer beanspruchen.
down(Frei)
up(Zugriff) – Freigabe des Zugriffs.
up(Zugriff)
Der Verbraucher-Prozess führt aus:
up(Frei) – Freigabe des freien Platzes.
up(Frei)
Problem: Deadlock
Erzeuger: Blockiert in down(Frei), weil der Puffer keinen freien Platz hat.
Verbraucher: Blockiert in down(Zugriff), weil der Zugriff auf den Puffer blockiert ist.
Das führt dazu, dass der Erzeuger wartet, bis der Verbraucher up(Frei) ausführt, aber der Verbraucher wartet, bis der Erzeuger up(Zugriff) ausführt – so entsteht ein Deadlock.
Ursache:
Die Ressource Frei wird erst freigegeben, wenn der Zugriff auf den Puffer (durch Zugriff) verfügbar ist, was zu einer Blockade führt.
Zugriff
Erzeuger blockiert, weil Frei keinen Platz mehr hat und in down(Frei) wartet.
Verbraucher blockiert, weil er down(Zugriff) ausführt, aber der Erzeuger den Zugriff nicht freigibt.
Es entsteht ein Deadlock, weil beide Prozesse aufeinander warten, ohne dass der andere den benötigten Wert freigibt.
Vergleichen Sie Segmentierung mit Paging
Paging vs. Segmentierung:
Beide Methoden:
Bieten Speicher-Zugriffsschutz und Relokierbarkeit.
Unterstützen dynamische Allokierung.
Haben interne Fragmentierung, die jedoch keine signifikanten Auswirkungen hat.
Paging:
Vorteil: Kein Problem mit externer Fragmentierung.
Kein Kompaktifizieren des Hauptspeichers notwendig.
Bietet nur einen Adressraum pro Prozess.
Problem: Kollisionen im logischen Adressraum bei wachsenden Datenblöcken.
Unterstützt gemeinsame Speicherbereiche (Shared Memory) zwischen Prozessen.
Segmentierung:
Nachteil: Führt zu externer Fragmentierung.
Bietet mehrere Adressräume pro Prozess.
Unterstützt gemeinsame Speicherbereiche zwischen Prozessen, z.B. für Interprozesskommunikation oder geteilte Code-Segmente.
Kein Problem mit externer Fragmentierung.
Nur ein Adressraum pro Prozess.
Unterstützt geteilte Speicherbereiche zwischen Prozessen.
Externe Fragmentierung möglich.
Mehrere Adressräume pro Prozess.
Ermöglicht ebenfalls geteilte Speicherbereiche für Kommunikation zwischen Prozessen.
Erklären Sie „down“ und „up“ semantisch:
Semaphor-Operationen:
down-Operation:
Der Prozess fragt, ob er etwas tun darf (wird blockiert, falls nicht).
up-Operation:
Der Prozess meldet, dass die Ressource wieder freigegeben ist.
Verwendung von Semaphoren:
Schutz eines kritischen Abschnitts:
Prozess A: down(S), kritischer Abschnitt, up(S)
down(S)
Abwechselnde Reihenfolge von Operationen garantieren:
Prozess A: down(S1), kritischer Abschnitt von A, up(S2)
down(S1)
up(S2)
Prozess B: down(S2), kritischer Abschnitt von B, up(S1)
down(S2)
up(S1)
down: Der Prozess fragt, ob er etwas tun darf.
up: Der Prozess sagt, dass er fertig ist und die Ressource freigegeben wird.
Beispiel:
Kritischer Abschnitt schützen:
Prozess A führt down(S) aus, dann den kritischen Abschnitt und danach up(S).
Abwechselnde Operationen garantieren:
Prozess A und B wechseln sich bei der Ausführung ab, indem sie jeweils down(S) und up(S) in umgekehrter Reihenfolge ausführen.
Prozess-Synchronisation: Das Problem der dinierenden Philosophen
Problemstellung:
n Philosophen sitzen an einem Tisch und teilen sich n Essstäbchen. Jeder Philosoph benötigt 2 Stäbchen zum Essen.
Nachteil der ersten Lösung:
Deadlock tritt auf, wenn jeder Philosoph das linke Stäbchen nimmt, aber keiner das rechte bekommt, weil er auf das rechte Stäbchen seines Nachbarn wartet. Alle Philosophen blockieren dann gegenseitig.
Lösung:
Mutex-Semaphor:
Ein binärer Semaphor „mutex“ sorgt dafür, dass immer nur ein Philosoph gleichzeitig die Stäbchen nehmen oder zurücklegen kann.
Prozess: Philosoph führt down(mutex) aus, bevor er Stäbchen nimmt oder zurücklegt, und up(mutex), wenn er fertig ist.
down(mutex)
up(mutex)
Hunger-Prüfung:
Jeder Philosoph hat einen Semaphor p[i] (mit Wert 0 initialisiert), der ihn blockiert, wenn ein Stäbchen nicht frei ist.
p[i]
Der Status status[i] verfolgt, ob der Philosoph denkt, hungrig oder isst.
status[i]
Teste(i)-Prozedur:
Jeder Philosoph prüft, ob er essen kann, indem er die teste(i)-Prozedur ausführt, die auch für seine Nachbarn aufgerufen wird, um sicherzustellen, dass keine Kollision im „Essen“ entsteht.
teste(i)
Ziel:
Philosophen essen nur, wenn beide Nachbarn nicht essen. Die Lösung verhindert Deadlock, aber nicht notwendigerweise Fairness.
Problem:
Philosophen brauchen 2 Stäbchen, aber wenn jeder das linke aufnimmt, blockieren sie sich gegenseitig, weil sie nicht das rechte bekommen.
Ein Semaphor sorgt dafür, dass immer nur ein Philosoph gleichzeitig die Stäbchen aufnimmt oder zurücklegt.
Semaphor für Blockierung:
Jeder Philosoph hat einen Semaphor (p[i]), der ihn blockiert, falls ein Stäbchen nicht frei ist.
Status des Philosophs:
Jeder Philosoph hat einen Status (denken, hungrig, essen), der verfolgt, was er gerade macht.
denken
hungrig
essen
Teste-Prozedur:
Die teste(i)-Prozedur prüft, ob der Philosoph essen kann. Sie wird von ihm und seinen Nachbarn aufgerufen.
Philosophen können nur dann essen, wenn ihre Nachbarn nicht essen. Deadlock wird vermieden, aber Fairness ist nicht garantiert.
Was ist ein Dateisystem? Wozu brauchen wir ein Dateisystem?
Ein Dateisystem ermöglicht den Benutzern, mit Dateien auf einer logischen Ebene zu interagieren. Das bedeutet:
Der Benutzer kann Dateien erstellen, öffnen, lesen, schreiben, löschen und ändern, ohne sich um die physische Struktur des Speichers (wie die Festplatte) kümmern zu müssen.
Das Dateisystem versteckt die technischen Details und sorgt dafür, dass die Daten korrekt auf Sekundärspeicher (wie Festplatten) abgebildet werden.
Dies nennt man Transparenz, weil die Nutzer nicht sehen müssen, wie der Speicher tatsächlich verwaltet wird.
Ein Dateisystem sorgt dafür, dass Benutzer mit Dateien arbeiten können, ohne sich um die technischen Details des Speichers kümmern zu müssen. Es kümmert sich darum, die Dateien korrekt auf der Festplatte zu speichern.
Welche Operationen kann eine Festplatte ausführen?
Blockoperationen
Was ist eine Datei?
Aus logischer Sicht ist eine Datei wie ein Array von Bytes oder, in Datenbanken, eine Folge von Datensätzen, die zusammengehörige Informationen speichern.
Jede Datei wird durch einen Index (also eine Nummer) lesbar und beschreibbar.
Physisch gesehen ist eine Datei eine Serie von gleich großen Blöcken auf dem Speicher.
Jede Datei hat einen Namen, und die Erweiterung des Dateinamens (z.B. .txt oder .jpg) wird als Suffix bezeichnet.
.txt
.jpg
Dateien können folgende Aktionen durchlaufen:
Anlegen und Löschen
Öffnen und Schließen
Lesen, Schreiben und Ändern
Einige gängige Befehle:
cp für Kopieren
cp
mv für Verschieben
mv
Eine Datei ist eine Reihe von Bytes oder Datensätzen, die Informationen enthalten. Sie hat einen Namen und eine Erweiterung (Suffix). Man kann eine Datei erstellen, löschen, öffnen, lesen oder ändern. Zum Kopieren einer Datei wird der Befehl cp verwendet, und zum Verschieben mv.
Was ist ein Verzeichnis?
Verzeichnisse fassen Dateien zusammen und sind unter Unix selbst eine Datei.
Ein Verzeichnis enthält Dateinamen und deren Speicherorte (wie die Blocknummern bei FAT oder die Inode-Nummern bei Unix).
Hierarchisches Dateisystem: Es gibt ein Wurzelverzeichnis /, und jedes Verzeichnis kann auf andere Verzeichnisse oder Dateien zeigen.
/
Ein Dateipfad wie z.B. /home/mueller/projekt führt von der Wurzel bis zum Ziel.
/home/mueller/projekt
Hardlinks sind Einträge im Verzeichnis, die den Dateinamen mit einer Inode-Referenz verbinden.
Ein Verzeichnis hat immer mindestens zwei Hardlinks: einen in seinem eigenen Verzeichnis (.) und einen im Eltern-Verzeichnis (..).
Wichtige Befehle:
cd – Verzeichnis wechseln
cd
mkdir – Verzeichnis erstellen
mkdir
rmdir – Leeres Verzeichnis entfernen
rmdir
rm -r – Verzeichnis und Inhalt löschen (Achtung: Sicherheitsproblem!).
rm -r
touch – Datei erstellen oder ändern.
touch
Dateisysteme:
FAT: Verzeichnis speichert Dateinamen und Startblocknummern.
inode: Verzeichnis speichert Dateinamen und Inode-Nummern.
Ein Verzeichnis ist eine Sammlung von Dateien, die unter Unix selbst eine Datei ist. Es speichert die Dateinamen und deren Speicherorte. In einem hierarchischen System gibt es das Wurzelverzeichnis /, und jedes Verzeichnis zeigt auf andere Verzeichnisse oder Dateien. Ein Dateipfad führt von der Wurzel zu einer Datei oder einem Verzeichnis.
Hardlinks verbinden Dateinamen mit Inode-Nummern.
Wichtige Befehle: cd, mkdir, rmdir, rm -r und touch.
FAT speichert Dateinamen und Startblocknummern.
inode speichert Dateinamen und Inode-Nummern.
Was ist ein Hardlink?
Ein Hardlink ist ein Verzeichniseintrag, der aus einem Dateinamen und der Inode-Nummer der Datei besteht.
Jede Datei hat genau einen Inode, der die Dateiattribute und die Blockstruktur der Datei enthält.
Eine Datei kann mehrere Hardlinks haben, die auf denselben Inode verweisen, wobei diese Hardlinks in verschiedenen Verzeichnissen innerhalb des gleichen Dateisystems existieren können.
Um Rekursionen zu vermeiden, sind Hardlinks auf Verzeichnisse nicht erlaubt.
Ein Hardlink verbindet einen Dateinamen mit der Inode-Nummer einer Datei. Jede Datei hat einen Inode, der wichtige Informationen über die Datei speichert. Eine Datei kann mehrere Hardlinks haben, die alle denselben Inode referenzieren. Hardlinks auf Verzeichnisse sind jedoch nicht erlaubt, um Rekursionen zu verhindern.
Welche Informationen gibt es in den Attributen einer Datei (unter Unix)?
Die Anzahl der Hardlinks einer Datei entspricht der Anzahl der Dateinamen, die auf diese Datei verweisen (also die Hardlinks im Dateisystem).
Für ein Verzeichnis ist die Hardlink-Anzahl die Anzahl der eingetragenen Dateinamen in diesem Verzeichnis plus 2 (wegen des Verzeichnisses selbst und des Verzeichnisses des Elternteils).
Eine Datei kann erst gelöscht werden, wenn die Anzahl ihrer Hardlinks im Inode den Wert 0 erreicht hat.
Die Anzahl der Hardlinks einer Datei entspricht der Anzahl der Namen, die auf diese Datei verweisen.
Ein Verzeichnis hat zusätzliche 2 Hardlinks, da es sich selbst und sein Elternverzeichnis referenziert.
Eine Datei kann erst gelöscht werden, wenn ihre Hardlink-Zahl im Inode auf 0 steht.
Wie sehen die Zugriffsberechtigungen einer Datei bei UNIX aus?
Für jede Datei gibt es Zugriffsrechte, die für jede Benutzerklasse individuell festgelegt werden:
user (Besitzer der Datei)
group (Gruppe des Benutzers)
others (alle anderen Benutzer)
Die Zugriffsarten umfassen:
r (lesen)
w (schreiben)
x (ausführen)
Rechte vererben sich nicht automatisch von einer größeren Benutzerklasse auf eine kleinere.
Für jede Datei werden Zugriffsrechte für den Besitzer, die Gruppe und andere Benutzer festgelegt.
Es gibt drei mögliche Rechte: lesen (r), schreiben (w) und ausführen (x).
Rechte werden nicht automatisch vererbt.
Wie werden die Zugriffsrechte ausgewertet, wenn ein Prozess einen Zugriff startet?
Wie werden die Zugriffsrechte bewertet bei einem Zugriff auf eine Datei?
Wer vergibt die Zugriffsrechte?
chmod g+w myprogram
In diesem Beispiel wird der Befehl chmod verwendet, um die Zugriffsrechte für eine Datei zu ändern.
chmod
g+w: Das bedeutet, dass für die Benutzergruppe group das Schreibrecht (write, w) hinzugefügt wird.
w
myprogram: Der Name der Datei, auf die die Änderungen angewendet werden.
Der Eigentümer der Datei oder der Superuser (root) kann die Zugriffsrechte von Dateien ändern. In diesem Fall kann der Eigentümer (oder der Superuser) das Schreibrecht für die Gruppe hinzufügen, wodurch Mitglieder der Gruppe die Datei bearbeiten können.
Dieser Befehl bewirkt also, dass die Gruppe nun Schreibzugriff auf myprogram hat.
Es gibt viele weitere Möglichkeiten, chmod zu verwenden, z.B.:
chmod u-x myprogram: Entfernt das Ausführrecht für den Eigentümer.
chmod u-x myprogram
chmod o+r myprogram: Gibt anderen Benutzern Leserechte für die Datei.
chmod o+r myprogram
chmod 755 myprogram: Setzt die Zugriffsrechte auf rwxr-xr-x für user, group, und others.
chmod 755 myprogram
rwxr-xr-x
Was ist ein Softlink?
Einprägsame Antwort (mit optischer Aufbereitung):
Softlink (symbolischer Link)
Was ist ein Softlink? Ein Softlink ist eine spezielle Datei, die als Verweis auf eine andere Datei dient.
Inhalt eines Softlinks:
Enthält einen Pfad zu der Zieldatei
Kann absolut (vollständiger Pfad) oder relativ (bezogen auf das aktuelle Verzeichnis) sein.
Vergleich:
Ähnlich wie Windows-Datei-Links
Im Unterschied zum Hardlink verweist der Softlink nur auf den Pfad der Ziel-Datei, nicht auf deren Inode.
Eine Datei, die auf den Pfad einer anderen Datei zeigt.
Der Pfad kann absolut oder relativ sein.
Ähnlich wie ein Windows-Datei-Link.
Was ist ein inode?
Inode-System
Ein Inode ist eine Datenstruktur in einem dezentralen Dateisystem, die für jede Datei existiert.
Inhalt eines Inodes:
Enthält Datei-Attribute (z.B. Größe, Berechtigungen, Erstellungszeit)
Enthält die Blockstruktur der Datei (welche Blöcke die Datei verwendet)
Kein Dateiname!
Wichtig zu wissen:
Dateiblöcke werden in logarithmischer Zeit gefunden
Ein Inode wird nur in den Hauptspeicher geladen, wenn er benötigt wird.
Jeder Datei wird ein Inode zugewiesen.
Der Inode enthält Datei-Attribute und die Blockstruktur der Datei.
Kein Dateiname im Inode.
Dateiblöcke werden in logarithmischer Zeit gefunden.
Inodes werden nur bei Bedarf in den Hauptspeicher geladen.
Was steht in einem inode?
Inode-Inhalt:
Datei-Attribute:
Enthält grundlegende Informationen zur Datei (z.B. Berechtigungen, Besitzer, Zeitstempel).
13 Block-Adressen:
Zeigen auf Datenblöcke, die den Inhalt der Datei speichern.
3 n-fach-Indexblock-Referenzen:
Diese Referenzen erlauben den Zugriff auf größere Dateien, indem sie auf zusätzliche Indexblöcke verweisen.
n-fach bedeutet, dass Indexblöcke weiter auf weitere Indexblöcke verweisen können.
Ein Inode enthält:
Datei-Attribute (Berechtigungen, Zeitstempel, etc.)
13 Block-Adressen (Datenblöcke der Datei)
3 n-fach-Indexblock-Referenzen (Verweise auf weitere Indexblöcke, für größere Dateien).
Wie groß ist ein inode?
Inode Speicher und Limitierungen:
Speicherplatz pro Inode:
Ein Inode benötigt wenig Speicher (z.B. 128 Byte in Ext-2).
In einem Festplattenblock können mehrere Inodes gespeichert werden.
Reservierung von Inodes:
Ein Bereich auf der Partition ist für Inodes reserviert.
Anzahl der Inodes wird bei der Formatierung der Partition festgelegt und kann später nicht geändert werden.
Problem der Inode-Beschränkung:
Zu viele belegte Inodes können dazu führen, dass die Platte „voll“ erscheint, obwohl physikalisch noch Platz frei ist.
Keine Übersicht über freie Blöcke:
Das Inode-System bietet keine sofortige Übersicht über freie Blöcke auf der Festplatte.
Ein Inode braucht wenig Speicher (z.B. 128 Byte in Ext-2).
In einem Block können mehrere Inodes gespeichert werden.
Bei der Formatierung wird die Anzahl der Inodes festgelegt und kann später nicht geändert werden.
Dies kann dazu führen, dass die Platte voll erscheint, obwohl noch physisch Platz vorhanden ist.
Es gibt keine Übersicht über freie Blöcke.
Wie funktioniert das Dateisystem inode bei LINUX/UNIX? Was ist die Idee eines inode-Dateisystems?
Inode-System in Ext-2:
Schneller Zugriff auf kleine Dateien.
Effizienter Zugriff auf große Dateien.
Struktur eines Inodes:
Ein Inode in Ext-2 enthält 15 Adressen:
1-12. Adresse:
Zeigen auf Datenblöcke (direkte Adressen).
13. Adresse:
Zeigt auf einen Indexblock:
Der Indexblock enthält x Adressen, jede zeigt auf einen Datenblock.
14. Adresse:
Zeigt auf einen Indexblock, der x Adressen enthält, die auf weitere Indexblöcke zeigen.
15. Adresse:
Referenziert dreifach-indirekt-indizierte Datenblöcke.
Speicherung:
Indexblöcke sind größer als Inodes und werden zusammen mit den Datenblöcken gespeichert.
Ein Inode in Ext-2 hat 15 Adressen:
Die ersten 12 Adressen zeigen auf Datenblöcke.
Die 13. Adresse zeigt auf einen Indexblock, der auf Datenblöcke verweist.
Die 14. Adresse zeigt auf einen Indexblock, der auf weitere Indexblöcke verweist.
Die 15. Adresse verweist auf dreifach-indirekt-indizierte Datenblöcke.
Indexblöcke sind größer als Inodes und werden mit Datenblöcken gespeichert.
Wie viele Zugriffe auf die Festplatte benötigt man höchstens, um einen Datenblock zu lokalisieren, wenn der inode schon im Hauptspeicher liegt?
Dreifach-indirekte „Indizierung“:
Zugriff auf Datenblöcke, die durch dreifach-indirekte Adressen referenziert werden.
Wie es funktioniert:
Dreifach-indirekte Adresse (15. Adresse im Inode):
Diese Adresse verweist auf einen Indexblock, der Adressen zu weiteren Indexblöcken enthält.
Doppelt-indirekter Indexblock:
Jeder Indexblock in der Kette verweist auf noch einen weiteren Indexblock, bis der letzte Indexblock schließlich auf Datenblöcke verweist.
Zugang:
Der Zugriff auf die Daten erfolgt durch das Schichten von Adressen:
Erste Ebene: dreifach-indirekter Indexblock
Zweite Ebene: doppelt-indirekter Indexblock
Dritte Ebene: direkt auf Datenblöcke
Vorteil:
Ermöglicht das Speichern und Zugreifen auf sehr große Dateien mit vielen Datenblöcken.
Die 15. Adresse im Inode zeigt auf einen dreifach-indirekten Indexblock, der:
Erste Ebene: auf doppelt-indirekte Indexblöcke zeigt,
Zweite Ebene: auf Indexblöcke verweist,
Dritte Ebene: schließlich auf Datenblöcke zeigt.
Diese Kettenindizierung ermöglicht das Speichern von sehr großen Dateien.
Wie kann man die maximale Größe einer Datei berechnen, wenn sie durch ein inode beschrieben wird?
Mehrfach Indirekte Indizierung: Die Anzahl der benötigten Blöcke, um eine Datei zu speichern, wird durch mehrfache Indizierung bestimmt. Bei der dreifach-indirekten Indizierung kommen folgende Blöcke zusammen:
12 Datenblöcke:
Direkt adressiert durch die ersten 12 Adressen im Inode.
x Blöcke (erste indirekte Ebene):
Die 13. Adresse im Inode verweist auf einen Indexblock, der auf x Datenblöcke zeigt.
x² Blöcke (zweite indirekte Ebene):
Die 14. Adresse im Inode verweist auf einen Indexblock, der auf x Indexblöcke verweist, die wiederum auf x Datenblöcke zeigen.
x³ Blöcke (dritte indirekte Ebene):
Die 15. Adresse im Inode verweist auf einen Indexblock, der auf x² Indexblöcke verweist, die wiederum auf x Datenblöcke zeigen.
Formel: Die Gesamtzahl der Blöcke ergibt sich also zu: 12 + x + x² + x³
12 Datenblöcke direkt.
x Blöcke für die erste indirekte Ebene.
x² Blöcke für die zweite indirekte Ebene.
x³ Blöcke für die dritte indirekte Ebene.
Gesamte Anzahl der Blöcke: 12 + x + x² + x³.
Ein Dateisystem muß eine Folge von Datensätzen in Blöcke auf dem Sekundär-speicher abbilden. Wie macht das das Dateisystem FAT?
Zentrale File Allocation Table (FAT):
Einträge für alle Festplattenblöcke:
Jeder Block auf der Festplatte hat einen Eintrag in der FAT.
FAT-Index als Blocknummer:
Jeder Index in der FAT stellt die Blocknummer eines Festplattenblocks dar.
FAT-Eintrag als Verweis:
Jeder Eintrag in der FAT zeigt auf den nächsten Block einer Datei oder markiert das Ende der Datei mit EOF oder den Block als frei.
Größe der FAT:
Größe der FAT = Anzahl der Blöcke × Länge einer Blocknummer.
Die FAT enthält für jeden Festplattenblock einen Eintrag.
Jeder Index in der FAT ist die Blocknummer eines Festplattenblocks.
Ein FAT-Eintrag verweist auf den nächsten Block einer Datei.
Die Größe der FAT berechnet sich durch die Anzahl der Blöcke multipliziert mit der Länge der Blocknummer.
Wie groß ist die FAT?
Berechnung der FAT-Größe:
Formel für die FAT-Größe:
FAT-Größe = Anzahl der Blöcke × Länge einer Blockadresse.
Partitionsgröße: 32 GB
Blockgröße: 4 KB
Anzahl der Blöcke = 32 GB / 4 KB = 8 Millionen Blöcke.
Breite eines Eintrags: 23 Bit.
FAT-Größe berechnen:
FAT-Größe = 8 Millionen × 23 Bit = 23 MB.
Die FAT-Größe ergibt sich aus der Anzahl der Blöcke multipliziert mit der Breite der Blockadresse.
Beispiel: Bei einer 32 GB Partition mit 4 KB Blöcken und 23 Bit pro Eintrag ergibt sich eine FAT-Größe von 23 MB.
Wie kann man die Lokalisierung eines Blocks einer Datei auf der Festplatte mit FAT feststellen?
Sequenzielle Suche in der FAT:
FAT bleibt im Hauptspeicher:
Solange das System läuft, wird die FAT im Hauptspeicher behalten, was den Zugriff schneller macht.
Funktionsweise der sequenziellen Suche:
Um den nächsten Block einer Datei zu finden, durchsucht das System nacheinander die FAT-Einträge, beginnend bei dem Startblock der Datei.
Jeder FAT-Eintrag gibt den nächsten Block der Datei oder den Ende-Status (EOF) an.
Schneller Zugriff auf die Datei, wenn die FAT im Hauptspeicher bleibt.
Die FAT bleibt im Hauptspeicher, was schnellen Zugriff ermöglicht.
Bei einer sequentiellen Suche werden die FAT-Einträge nacheinander durchgesehen, um die nächsten Blöcke einer Datei zu finden.
Was ist dann der Nachteil von FAT bei großen Dateien?
FAT und die Probleme mit dem Auffinden von Blöcken:
Auffinden von Blöcken am Dateiende:
Die Suche nach den letzten Blöcken einer Datei ist langsam, da sie eine lineare Suche erfordert.
Vorteil von FAT:
Schnelle globale Übersicht:
FAT bietet eine schnelle Möglichkeit, einen Überblick über z.B. freie Blöcke innerhalb der Partition zu erhalten.
Zusammenhängende und nicht zusammenhängende Speicherung:
Zusammenhängende Speicherung:
Probleme wie externe Fragmentierung und nicht zusammenhängende Speicherung treten auch hier auf.
Nicht zusammenhängende Speicherung:
Diese wird durch verkettete Listen gelöst, aber ohne wahlfreien Zugriff.
Das Auffinden der letzten Blöcke in einer FAT-Datei ist langsam (durch lineare Suche).
FAT bietet jedoch eine schnelle Übersicht über freie Blöcke.
Bei der Speicherung gibt es Probleme mit Fragmentierung und nicht zusammenhängender Speicherung, die durch verkettete Listen gelöst werden, aber ohne wahlfreien Zugriff.
womit befast sich diese Kurseinheit
Die zweite Kurseinheit legt den Fokus auf die wesentlichen Bestandteile von Betriebssystemen, insbesondere Prozesse und Dateisysteme. Es wird behandelt, wie Prozesse erzeugt werden, wie Dateien organisiert sind und wie das Dateisystem in UNIX/Linux strukturiert ist.
Wie kann man die Lokalisierung eines Blocks einer Datei auf der Festplatte mit inode feststellen?
Einprägsame Erklärung:
Start beim Datei-Inode: Der Zugriff auf eine Datei beginnt beim inode, der die grundlegenden Informationen zur Datei enthält.
Indexblöcke und dreifache Indizierung: Wenn eine Datei groß ist, kann der inode auf Indexblöcke verweisen, die selbst weitere Adressen zu Datenblöcken enthalten. Dies kann bis zu dreifacher Indizierung gehen.
Logarithmische Suchzeit: Da beim Zugriff auf große Dateien in einem logarithmischen Muster auf die Datenblöcke zugegriffen wird (durch Indizes), bleibt die Zeit für den Zugriff auf Daten, selbst bei sehr großen Dateien, überschaubar.
Einfache Erklärung:
Der Zugriff auf die Datei startet beim inode.
Bei Bedarf wird die Lage von Indexblöcken berechnet.
Diese Indexblöcke werden dann, je nach Anzahl der Indizierungen, bis zu dreifach geladen.
Die Suchzeit bleibt aufgrund der logarithmischen Struktur der Datei in Bezug auf die Dateigröße konstant.
Last changed4 days ago
