Betriebssystemtechnik - Exam

Aufgabe 1)

Prozesszustände und ZustandsübergängeProzesszustände sind die verschiedenen Phasen, die ein Prozess während seiner Ausführung durchläuft. Zustandsübergänge sind die Wechsel zwischen diesen Phasen aufgrund von Ereignissen oder Aktionen.

• Wesentliche Prozesszustände:
  • Bereit (ready): Prozess ist ausführbar, wartet auf Zuteilung der CPU.
  • Aktiv (running): Prozess wird gerade von der CPU ausgeführt.
  • Blockiert (blocked): Prozess wartet auf ein Ereignis (z.B. Ein-/Ausgabeoperation).
  • Beendet (terminated): Prozess ist abgeschlossen und wird aus dem Speicher entfernt.
• Übergänge zwischen Zuständen:
  • Bereit zu Aktiv: Scheduler weist dem Prozess die CPU zu.
  • Aktiv zu Bereit: Prozess wird präemptiert (z.B. durch einen Zeitscheibenwechsel).
  • Aktiv zu Blockiert: Prozess startet eine blockierende IO-Operation.
  • Blockiert zu Bereit: Das erwartete Ereignis tritt ein.
  • Aktiv zu Beendet: Prozess beendet seine Ausführung.

a)

Erkläre detailliert den Unterschied zwischen den Prozesszuständen 'Bereit', 'Aktiv' und 'Blockiert'. Nenne jeweils ein reales Beispiel aus einem Betriebssystem, das verdeutlicht, wann ein Prozess in diesen Zustand wechselt.

Lösung:

Unterschied zwischen den Prozesszuständen 'Bereit', 'Aktiv' und 'Blockiert'

• Bereit (ready): Ein Prozess befindet sich im Zustand Bereit, wenn er ausführbar ist, jedoch auf die Zuteilung der CPU wartet. Er hat alle notwendigen Ressourcen, um zu laufen, abgesehen von der CPU-Zeit.Reales Beispiel: In einem Multitasking-Betriebssystem wie Windows kann ein Textverarbeitungsprogramm, das geöffnet, aber nicht aktiv verwendet wird, sich im Zustand 'Bereit' befinden. Es wartet darauf, dass der Benutzer eine Eingabe macht oder eine CPU-Zeit von dem Scheduler zugeteilt bekommt.
• Aktiv (running): Wenn ein Prozess im Zustand Aktiv ist, wird er gerade von der CPU ausgeführt. Er hat die CPU-Zeit zugewiesen bekommen und seine Anweisungen werden aktuell verarbeitet.Reales Beispiel: Bei einem Echtzeit-Computerspiel wird der Hauptspielprozess im Zustand 'Aktiv' sein, da er kontinuierlich Eingaben verarbeitet, die Spielumgebung aktualisiert und die Grafiken rendert.
• Blockiert (blocked): Ein Prozess ist im Zustand Blockiert, wenn er auf ein bestimmtes Ereignis oder eine Ressource wartet, wie etwa den Abschluss einer Ein-/Ausgabeoperation. Während dieser Zeit kann der Prozess nicht weiter ausgeführt werden.Reales Beispiel: Ein Webbrowser, der darauf wartet, dass eine Webseite geladen wird, könnte im Zustand 'Blockiert' sein. Er wartet auf die Netzwerkantwort und kann erst dann die weiteren Schritte ausführen, wenn die Daten empfangen wurden.

b)

Beschreibe den Ablauf eines Prozesses, der vom Zustand 'Bereit' in den Zustand 'Beendet' übergeht. Welche Zustandsübergänge und Aktionen sind notwendig, bis dieser Prozess vollständig beendet ist? Nutze ein Flussdiagramm, um den Ablauf grafisch darzustellen.

Lösung:

Ablauf eines Prozesses vom Zustand 'Bereit' in den Zustand 'Beendet'

• Ein Prozess beginnt im Zustand 'Bereit', wenn er auf die Zuteilung der CPU wartet.
• Der Scheduler weist dem Prozess die CPU zu, was zum Zustandsübergang von 'Bereit' zu 'Aktiv' führt.
• Während der Ausführung könnte der Prozess auf eine blockierende IO-Operation stoßen, was zum Übergang von 'Aktiv' zu 'Blockiert' führt.
• Nach Abschluss der IO-Operation wird der Prozess wieder 'Bereit', was zum Übergang von 'Blockiert' zu 'Bereit' führt.
• Der Scheduler weist dem Prozess erneut die CPU zu, und er wechselt wieder von 'Bereit' zu 'Aktiv'.
• Dieser Zyklus (von 'Bereit' zu 'Aktiv' zu 'Blockiert' zu 'Bereit') könnte mehrere Male wiederholt werden, je nach den Anforderungen des Prozesses.
• Schließlich wird der Prozess seine Arbeit komplett abschließen und in den Zustand 'Beendet' übergehen, was den Übergang von 'Aktiv' zu 'Beendet' zur Folge hat.

Im Folgenden siehst Du ein Flussdiagramm, das diesen Ablauf grafisch darstellt:

 +----------+                  +--------------+ |  Bereit  +---------------->  |    Aktiv     | +----------+                  +--------------+       |                                |       |                                |       |                                |       v                                v +--------------+  <-------+   +----------------+ |  Blockiert   |             |     Beendet     | +--------------+  <-------+   +----------------+

Die Pfeile im Flussdiagramm zeigen die möglichen Zustandsübergänge eines Prozesses:

• 'Bereit' zu 'Aktiv': Scheduler weist dem Prozess die CPU zu.
• 'Aktiv' zu 'Bereit': Prozess wird präemptiert (z.B. durch einen Zeitscheibenwechsel).
• 'Aktiv' zu 'Blockiert': Prozess startet eine blockierende IO-Operation.
• 'Blockiert' zu 'Bereit': Das erwartete Ereignis tritt ein (z.B. IO-Operation ist abgeschlossen).
• 'Aktiv' zu 'Beendet': Prozess beendet seine Ausführung.

c)

Eine CPU verwendet Zeitscheiben(Quantum) zur Prozessverwaltung. Der Scheduler wählt einen Prozess aus und alle 100ms wird der Prozess präemptiert. Gegeben sei die Liste der Prozess-IDs: P1, P2 und P3 mit jeweiliger Bearbeitungszeit in ms: 300ms, 500ms und 200ms. Zeige mathematisch und grafisch, wie die Zustandsübergänge der Prozesse aussehen werden, um das Round-Robin Scheduling zu verdeutlichen.

Lösung:

Zustandsübergänge der Prozesse in einem Round-Robin Scheduling

• Wir haben die Prozesse P1, P2 und P3 mit Bearbeitungszeiten von 300ms, 500ms und 200ms.
• Die CPU präemptiert jeden Prozess nach 100ms (Zeitscheibe).

Für den Round-Robin Scheduling-Algorithmus werden die Prozesse zyklisch in 100ms-Intervallen bearbeitet. Hier ist die Berechnung und der Zustand jedes Prozesses zu jedem Zeitpunkt:

• P1: 300ms:100ms im Zustand 'Aktiv' (300 - 100 = 200ms)100ms im Zustand 'Bereit'100ms im Zustand 'Aktiv' (200 - 100 = 100ms)100ms im Zustand 'Bereit'100ms im Zustand 'Aktiv' (100 - 100 = 0ms, abgeschlossen)
• P2: 500ms:100ms im Zustand 'Aktiv' (500 - 100 = 400ms)100ms im Zustand 'Bereit'100ms im Zustand 'Aktiv' (400 - 100 = 300ms)100ms im Zustand 'Bereit'100ms im Zustand 'Aktiv' (300 - 100 = 200ms)100ms im Zustand 'Bereit'100ms im Zustand 'Aktiv' (200 - 100 = 100ms)100ms im Zustand 'Bereit'100ms im Zustand 'Aktiv' (100 - 100 = 0ms, abgeschlossen)
• P3: 200ms:100ms im Zustand 'Aktiv' (200 - 100 = 100ms)100ms im Zustand 'Bereit'100ms im Zustand 'Aktiv' (100 - 100 = 0ms, abgeschlossen)

Hier ist die Zeitlinie für die Prozesse in einem Round-Robin Scheduling:

  |  P1  |  P2  |  P3  |  P1  |  P2  |  P3  | P1  | P2  | P2  |  0    100   200   300   400   500   600   700   800   900  1000  1100 

• P1 läuft von 0 bis 100ms, 300ms bis 400ms, und von 600ms bis 700ms.
• P2 läuft von 100 bis 200ms, 400ms bis 500ms, 700ms bis 800ms, und von 900ms bis 1000ms.
• P3 läuft von 200 bis 300ms und von 500ms bis 600ms.

Alle 100ms wechselt der aktive Prozess in den Zustand 'Bereit', und der nächste Prozess in der Reihenfolge wird 'Aktiv'. Dieser Zyklus wiederholt sich, bis alle Prozesse abgeschlossen sind.

d)

Diskutiere die Auswirkung von blockierenden und nicht blockierenden Ein-/Ausgabeoperationen auf die Zustandsübergänge eines Prozesses. Gib Beispiele für beide Arten der IO-Operation und deren typische Verwendung in modernen Betriebssystemen.

Lösung:

Auswirkungen von blockierenden und nicht blockierenden Ein-/Ausgabeoperationen auf die Zustandsübergänge eines Prozesses

Ein-/Ausgabeoperationen (IO-Operationen) sind ein wesentlicher Teil der Prozessausführung in einem Betriebssystem. Sie beeinflussen maßgeblich die Zustandsübergänge eines Prozesses:

• Blockierende IO-Operationen:

  Wenn ein Prozess eine blockierende IO-Operation startet, wird er in den Zustand 'Blockiert' versetzt und wartet, bis die IO-Operation abgeschlossen ist. Während dieser Zeit kann der Prozess keine weiteren Ausführungen durchführen und die CPU wird anderen Prozessen zugeteilt.

  • Beispiel: Eine typische blockierende IO-Operation ist das Lesen von Daten von einer Festplatte. Der Prozess bleibt blockiert, bis die physische Festplatte die Daten gelesen und an den Hauptspeicher übergeben hat. Dies wird oft in Situationen verwendet, in denen der Prozess ununterbrochene Daten benötigt, um fortzufahren, wie z.B., wenn ein Bildbearbeitungsprogramm eine Bilddatei öffnet.
  • Verwendung: Blockierende IO-Operationen sind in modernen Betriebssystemen bei synchronen Dateizugriffen oder Netzwerkoperationen weit verbreitet, wo die Daten unverzüglich benötigt werden oder wo einfachere Programmiermodelle bevorzugt werden.
• Nicht blockierende IO-Operationen:

  Ein Prozess, der eine nicht blockierende IO-Operation ausführt, bleibt im Zustand 'Aktiv' oder wird in den Zustand 'Bereit' versetzt, je nachdem, ob die CPU-Zeit abläuft. Solche IO-Operationen gestatten es dem Prozess, andere Aufgaben zu erledigen, während er auf das IO-Ereignis wartet. Der Prozess wird über das Eintreten des IO-Ereignisses (z.B. über einen Interrupt oder eine Polling-Schleife) benachrichtigt.

  • Beispiel: Ein Beispiel für eine nicht blockierende IO-Operation ist die Verwendung von asynchronen Lese- und Schreiboperationen in einer Netzwerkkommunikation. Ein Webserver könnte Anfragen und Antworten asynchron verarbeiten, sodass er andere Aufgaben zwischendurch erledigen kann, ohne auf das Ende jeder einzelnen Anfrage warten zu müssen.
  • Verwendung: Moderne Betriebssysteme nutzen nicht blockierende IO-Operationen, um die Effizienz zu erhöhen und die Response-Zeit in Anwendungen zu verbessern, die auf hohen Durchsatz und niedrige Latenz angewiesen sind, wie z.B. in datenintensiven und realzeitkritischen Systemen.

Zusammenfassend:

• Blockierende IO-Operation: 'Aktiv' zu 'Blockiert' und dann 'Blockiert' zu 'Bereit', insgesamt eine höhere Wartezeit, aber einfachere Implementierung.
• Nicht blockierende IO-Operation: 'Aktiv' zu 'Bereit' (ohne 'Blockiert'), insgesamt effizientere Ausnutzung der CPU-Zeit, aber komplexere Implementierung.

Aufgabe 2)

Ein wichtiger Aspekt in der Betriebssystemtechnik ist die Interprozesskommunikation (IPC) und die Synchronisierung von Prozessen. Diese Techniken sind entscheidend für den Austausch von Daten und Steuerinformationen zwischen Prozessen sowie für die geordnete und kontrollierte Ausführung von Prozessen. Die Mechanismen zur Realisierung von IPC umfassen Pipes, Shared Memory, Message Passing und Sockets. Zur Vermeidung von Race Conditions und Deadlocks sind verschiedene Synchronisationstechniken wie Mutex, Semaphore und Monitore von Bedeutung. Zudem spielen die Konzepte kritische Abschnitte, wechselseitiger Ausschluss und Warteschlangen eine zentrale Rolle in Multi-Prozess-Systemen.

a)

a) Erkläre den Unterschied zwischen den verschiedenen Mechanismen für Interprozesskommunikation (IPC): Pipes, Shared Memory, Message Passing und Sockets. Gehe dabei besonders auf die jeweiligen Vor- und Nachteile ein.

Lösung:

Interprozesskommunikation (IPC) und ihre Mechanismen sind zentrale Konzepte in der Betriebssystemtechnik. Hier sind die verschiedenen Mechanismen für IPC und ihre jeweiligen Vor- und Nachteile detailliert erläutert:

• Pipes:
  • Beschreibung: Pipes sind eine einfache Form der IPC und ermöglichen die Kommunikation zwischen Prozessen durch eine unidirektionale Datenflussverbindung. Klassische Pipes sind anonym und oft auf die Kommunikation zwischen verwandten Prozessen beschränkt.
  • Vorteile:
    • Einfache Implementierung und Nutzung.
    • Erzeugen eine einfache und schnelle Methode für die Datenübertragung.
  • Nachteile:
    • Nur unidirektional, es wird also eine zweite Pipe benötigt für bidirektionale Kommunikation.
    • Funktionieren hauptsächlich zwischen Eltern- und Kindprozessen.
    • Begrenzte Puffergröße kann zu Blockierungen führen, wenn der Puffer voll ist.
• Shared Memory:
  • Beschreibung: Shared Memory ermöglicht es mehreren Prozessen, gleichzeitig auf dieselben Daten in einem gemeinsam genutzten Speicherbereich zuzugreifen und diese zu bearbeiten.
  • Vorteile:
    • Sehr hohe Leistung, da keine Datenkopien erforderlich sind und Prozesse direkt auf die Daten zugreifen können.
    • Weniger Overhead im Vergleich zu anderen Methoden, da keine Kontextwechsel erforderlich sind.
  • Nachteile:
    • Bietet keine eingebaute Synchronisationsmechanismen. Es müssen zusätzliche Synchronisationsprimitive wie Mutexe oder Semaphoren verwendet werden, um Race Conditions zu vermeiden.
    • Komplexere Implementierung und Verwaltung.
• Message Passing:
  • Beschreibung: Beim Message Passing kommunizieren Prozesse durch das Senden und Empfangen von Nachrichten. Dieses Modell kann sowohl synchron (blockierend) als auch asynchron (nicht blockierend) implementiert werden.
  • Vorteile:
    • Einfach und klar, besonders für verteilte Systeme geeignet.
    • Bietet eingebaute Synchronisation, da der Empfang einer Nachricht oft ein blockierender Vorgang ist.
    • Unabhängigkeit der Prozesse wird erhalten.
  • Nachteile:
    • Niedrigere Leistung im Vergleich zu Shared Memory, da Nachrichtenkopien erforderlich sind.
    • Potenzielle Skalierungsprobleme, wenn viele Nachrichten übermittelt werden müssen.
• Sockets:
  • Beschreibung: Sockets sind Endpunkte für die bidirektionale Kommunikation über ein Netzwerk. Sie unterstützen die Interprozesskommunikation sowohl innerhalb eines einzelnen Rechners (Unix-Domain-Sockets) als auch über Netzwerke hinweg (INET-Sockets).
  • Vorteile:
    • Flexible und leistungsfähige Lösung für Drittanbieter-Kommunikation.
    • Kann sowohl über lokale als auch über Internet-basierte Netzwerke verwendet werden.
    • Unterstützt eine Vielzahl von Protokollen (z.B. TCP, UDP).
  • Nachteile:
    • Komplexität in der Implementierung und Fehlerbehebung, besonders bei Netzwerkkommunikation.
    • Kommunikationslatenzen und Overhead aufgrund von Netzwerkprotokollen.

b)

b) Angenommen, Du hast ein System mit drei Prozessen P1, P2 und P3, die auf eine gemeinsame Ressource r zugreifen müssen. Der Zugriff auf r soll so gestaltet werden, dass keine Race Conditions auftreten. Implementiere eine Lösung unter Verwendung von Semaphoren, die sicherstellt, dass immer nur ein Prozess gleichzeitig auf die Ressource zugreifen kann. Gehe dabei auf die Initialisierung und die notwendigen Operationen (wait/signal) ein.

Lösung:

Um sicherzustellen, dass in einem System mit drei Prozessen (P1, P2, P3) keine Race Conditions auftreten, wenn sie auf eine gemeinsame Ressource r zugreifen, kann man Semaphoren verwenden. Semaphoren bieten eine Möglichkeit, den Zugriff zu synchronisieren und sicherzustellen, dass immer nur ein Prozess gleichzeitig auf die Ressource zugreifen kann.

Folgende Schritte sind notwendig:

• Initialisierung des Semaphors: Der Semaphor wird initial auf den Wert 1 gesetzt, was bedeutet, dass die Ressource r zunächst verfügbar ist.
• Warteschlange (wait) und Signaloperation (signal): Diese Operationen kontrollieren den Zugriff auf die Ressource.
  • wait: Diese Operation verringert den Wert des Semaphors um 1 und blockiert gegebenenfalls den Prozess, wenn der Wert des Semaphors bereits 0 ist.
  • signal: Diese Operation erhöht den Wert des Semaphors um 1 und gibt ggf. einen blockierten Prozess frei.

Hier ist die Implementierung in Python:

# Python-Skript zur Demonstration der Synchronisierung mit Semaphoren import threading import time # Initialisierung des Semaphors mit dem Wert 1sem = threading.Semaphore(1) # Gemeinsame Ressource r = 0 # Funktion, die von jedem Prozess ausgeführt wird def access_resource(process_id):     print(f'Prozess {process_id} versucht, auf die Ressource zuzugreifen...')     sem.acquire()  # wait-Operation     try:         global r         print(f'Prozess {process_id} greift auf die Ressource zu.')         r += 1  # Beispielsweise eine Operation an der Ressource         time.sleep(1)  # Simuliert eine Verarbeitung         print(f'Prozess {process_id} verlässt die Ressource. Neuer Wert von r: {r}')     finally:         sem.release()  # signal-Operation # Erstellen und Starten der Threads für die drei Prozessethreads = [] for i in range(1, 4):     t = threading.Thread(target=access_resource, args=(i,))     t.start()     threads.append(t) # Warten, bis alle Threads beendet sind for t in threads:     t.join()

In diesem Beispiel:

• Die gemeinsame Ressource r wird durch die Funktion access_resource manipuliert.
• Jeder Prozess (Thread) versucht, das Semaphor zu akquirieren (wait).
• Wenn ein Prozess die Ressource erlangt hat, führt er eine Operation (Inkrementieren von r und eine Verzögerung zur Simulation der Verarbeitung) aus.
• Nach der Operation gibt der Prozess das Semaphor wieder frei (signal), womit ein anderer Prozess die Ressource erlangen kann.

Diese Implementierung stellt sicher, dass keine Race Conditions auftreten und immer nur ein Prozess gleichzeitig auf die Ressource zugreift.

Aufgabe 3)

Speicherallokationsstrategien Die Verwaltung des Speichers in einem Betriebssystem erfolgt häufig über zwei Hauptstrategien: Paging und Segmentierung. Bei Paging wird der Speicher in gleich große Blöcke, sogenannte Seiten, unterteilt. Dies vermeidet externe Fragmentierung; jeder Seite ist eine feste Größe zugeordnet. Bei der Segmentierung wird der Speicher in logische Segmente unterschiedlicher Größe unterteilt, die logische Einheiten wie Code, Daten und Stack unterstützen. Paging verwendet eine Seitentabelle zur Verwaltung der Zuordnung von logischen zu physischen Adressen, während die Segmentierung eine Segmenttabelle nutzt.

a)

Erkläre den Hauptunterschied zwischen Paging und Segmentierung hinsichtlich der Speicherverwaltung. Fokussiere Dich dabei besonders auf die Handhabung der Fragmentierung und die logische Sichtbarkeit durch den Benutzer.

Lösung:

Hauptunterschied zwischen Paging und Segmentierung hinsichtlich der Speicherverwaltung:

• Fragmentierung:Paging und Segmentierung unterscheiden sich signifikant in der Art und Weise, wie sie Fragmentierung handhaben:
• Paging: Speicher wird in gleich große Blöcke, sogenannte Seiten, unterteilt. Dies verhindert externe Fragmentierung, da jede Seite die gleiche Größe hat. Allerdings kann Paging interne Fragmentierung verursachen, wenn die in einer Seite gespeicherten Daten kleiner als die Seitengröße sind.
• Segmentierung: Speicher wird in logische Segmente unterschiedlicher Größe unterteilt. Dies kann externe Fragmentierung verursachen, da benachbarte Segmente möglicherweise unterschiedlich groß sind. Interne Fragmentierung ist in der Regel weniger ein Problem, da Segmente logisch zusammenhängende Einheiten repräsentieren und ihre Größen zur Laufzeit bestimmt werden.
• Logische Sichtbarkeit:Paging und Segmentierung bieten unterschiedliche logische Sichtbarkeitsstrukturen für den Benutzer:
• Paging: Der Speicher ist aus Sicht des Benutzers in gleich große, feste Blöcke unterteilt. Die Zuordnung zwischen logischen und physischen Adressen wird durch eine Seitentabelle verwaltet. Für den Benutzer ist dies oftmals nicht sichtbar, da die Seitentabelle diese Zuordnungen im Hintergrund handhabt.
• Segmentierung: Der Speicher ist aus Sicht des Benutzers in logische Einheiten wie Code, Daten und Stack unterteilt. Diese Struktur ist für den Benutzer besser sichtbar, da Operationen auf logischen Segmenten durchgeführt werden. Die Zuordnung zwischen logischen und physischen Adressen wird durch eine Segmenttabelle verwaltet, was dem Benutzer eine klarere Sicht auf die verschiedenen Speicherbereiche gibt.

b)

Gegeben sei ein System mit einer Seitengröße von 4 KB. Ein Prozess benötigt 10 KB Speicher. Wie viele Seiten sind benötigt und wie wird der Speicher zugewiesen? Stelle sicher, dass Du den Multi-Step-Ansatz verwendest, um die physische Adresse einer Logischen Adresse (z. B. 5000) zu finden.

Lösung:

Gegeben sei ein System mit einer Seitengröße von 4 KB. Ein Prozess benötigt 10 KB Speicher:

• Schritt 1: Bestimmen der Anzahl der benötigten Seiten:
• Die Seitengröße ist 4 KB. Das bedeutet, dass jede Seite 4096 Bytes groß ist.
• Der Prozess benötigt 10 KB.
• Die Anzahl der benötigten Seiten lässt sich wie folgt berechnen:
• \[\text{Anzahl der Seiten} = \frac{\text{Gesamtbedarf}}{\text{Seitengröße}} = \frac{10 \text{ KB}}{4 \text{ KB}} = 2.5\]
• Da ein Prozess keine halben Seiten verwenden kann, wird auf die nächste ganze Zahl aufgerundet, was bedeutet, dass 3 Seiten benötigt werden.
• Schritt 2: Zuweisung des Speichers:
• Dem Prozess werden 3 Seiten im physischen Speicher zugewiesen.
• Jede dieser Seiten ist 4 KB groß, sodass insgesamt 12 KB Speicher zugewiesen werden, obwohl der Prozess nur 10 KB benötigt.
• Diese Zuweisung erfolgt über eine Seitentabelle, die logische Adressen den physischen Seiten zuordnet.
• Schritt 3: Berechnung der physischen Adresse einer logischen Adresse (z.B. 5000):
• Die logische Adresse ist 5000. Wir müssen die Seitennummer und den Offset innerhalb der Seite bestimmen.
• Berechnung der Seitennummer:
• \[\text{Seitennummer} = \frac{\text{Logische Adresse}}{\text{Seitengröße}} = \frac{5000}{4096} \approx 1\]
• Berechnung des Offsets:
• \[\text{Offset} = \text{Logische Adresse} \bmod \text{Seitengröße} = 5000 \bmod 4096 = 904\]
• Die logische Adresse 5000 befindet sich also auf der Seite 1 (zweite Seite) mit einem Offset von 904 Bytes.
• Bestimmen der physischen Adresse:
• Angenommen, dass die physischen Adressen der Seiten im Speicher wie folgt sind:
• Seite 0: Adresse 8000 - 12095
• Seite 1: Adresse 12096 - 16191
• Seite 2: Adresse 16192 - 20287
• Da die logische Adresse 5000 auf der Seite 1 liegt:
• Die physische Adresse kann berechnet werden als:
• \[\text{Physische Adresse} = \text{Basisadresse der Seite 1} + \text{Offset} = 12096 + 904 = 12900\]

Zusammenfassung:

• Benötigte Seiten: 3
• Physische Adresse für die logische Adresse 5000: 12900

c)

Angenommen, für ein segmentiertes System werden folgende Segmente genutzt:

• Code: Basisadresse 0x4000, Limit: 2000 Bytes
• Stack: Basisadresse 0x6000, Limit: 1000 Bytes
• Daten: Basisadresse 0x8000, Limit: 3000 Bytes

Lösung:

Gegebenes segmentiertes System:

• Code: Basisadresse 0x4000, Limit: 2000 Bytes
• Stack: Basisadresse 0x6000, Limit: 1000 Bytes
• Daten: Basisadresse 0x8000, Limit: 3000 Bytes

Berechnung der physischen Adresse für eine gegebene logische Adresse (Segment-Offset-Paar: Code-Offset: 0x500):

• Schritt 1: Identifiziere das relevante Segment:Das gegebene Segment ist das Code-Segment. Seine Basisadresse ist 0x4000 und das Limit beträgt 2000 Bytes.
• Schritt 2: Prüfen, ob der Offset innerhalb des Segments liegt:
  • Der gegebene Offset ist 0x500 (was gleich 1280 in Dezimal ist).
  • Da das Limit des Code-Segments 2000 Bytes beträgt, liegt der Offset 1280 (0x500) innerhalb des erlaubten Bereichs. (0 ≤ 1280 < 2000)
• Schritt 3: Berechnung der physischen Adresse:
  • Die physische Adresse wird als Summe der Basisadresse des Segments und des Offsets berechnet:

  • \text{Physische Adresse} = \text{Basisadresse} + \text{Offset}

  • \text{Physische Adresse} = 0x4000 + 0x500 = 0x4500

  • \text{In Dezimal:} \text{Physische Adresse} = 16384 + 1280 = 17664

Zusammenfassung:Die physische Adresse für die logische Adresse (Segment-Offset-Paar: Code-Offset: 0x500) ist 0x4500 (Dezimal: 17664).

Zusammengefasst, der Prozess umfasst die Bestimmung des relevanten Segments, die Überprüfung ob der Offset innerhalb des Segment-Limits liegt und die Berechnung der physischen Adresse durch Addition der Basisadresse des Segments und dem Offset.

d)

Nimm an, dass ein Betriebssystem sowohl Paging als auch Segmentierung kombiniert verwendet. Erkläre, wie die beiden Systeme koexistieren können. Illustriere Deine Antwort mit einem Beispiel, bei dem ein Segment in Seiten unterteilt wurde, und beschreibe die Schritte und Tabellen, die zur Adressumsetzung erforderlich sind.

Lösung:

Koexistenz von Paging und Segmentierung:Ein Betriebssystem kann sowohl Paging als auch Segmentierung kombinieren, um die Vorteile beider Speicherallokationsstrategien zu nutzen. Dabei wird der Speicher zunächst in logische Segmente unterteilt (Segmentierung), und dann werden diese Segmente weiter in gleich große Seiten unterteilt (Paging). Dies ermöglicht eine flexible Speicherverwaltung und reduziert die Fragmentierung.

Beispiel und Adressumsetzung:

• Struktur:
  • Angenommen, wir haben folgende Segmente:
    • Code-Segment: Basisadresse 0x4000, Limit: 6000 Bytes
    • Stack-Segment: Basisadresse 0xA000, Limit: 2000 Bytes
    • Daten-Segment: Basisadresse 0xE000, Limit: 8000 Bytes
  • Diese Segmente werden weiter in Seiten unterteilt. Angenommen, die Seitengröße beträgt 4 KB (4096 Bytes).

Schritt 1: SegmentierungDie virtuelle Adresse besteht aus einem Segment-Offset-Paar. Beispielsweise: Virtuelle Adresse: Segment 1, Offset 0x3000 (Das Offset ist innerhalb des Segments und kleiner als das Limit von 6000 Bytes für das Code-Segment).

• Die Segmenttabelle wird verwendet, um die Basisadresse und das Limit des spezifischen Segments zu finden.
  • Basisadresse des Code-Segments = 0x4000
  • Limit des Code-Segments = 6000 Bytes

Schritt 2: Paging

• Das Segment (Code-Segment) wird weiter in Seiten unterteilt.
  • Seitengröße = 4 KB
  • Ein 6000 Bytes großes Segment wird in zwei Seiten aufgeteilt (erste Seite: 0 - 4095 Bytes, zweite Seite: 4096 - 6000 Bytes).

Schritt 3: Ermittlung der Seite und des Offsets:Die logische Adresse 0x3000 im Code-Segment wird in eine Seitennummer und einen Offset zerlegt:

• Seitennummer berechnen:\[\text{Seitennummer} = \frac{\text{Offset}}{\text{Seitengröße}} = \frac{0x3000}{0x1000} = 3 \text{ (ganzzahliger Quotient)}\]
• Offset berechnen:\[\text{Offset} = \text{Logische Adresse} \bmod \text{Seitengröße} = 0x3000 \bmod 0x1000 = 0x0 \]

Schritt 4: Adressumsetzung durch Paging:Die Seitentabelle für das spezifische Segment enthält die Basisadresse der physischen Seite. Angenommen, die Basisadresse der physischen Seite 3 ist 0x7000.

• Physische Adresse berechnen:\[\text{Physische Adresse} = \text{Basisadresse der Seite} + \text{Offset innerhalb der Seite}\]
• \[\text{Physische Adresse} = 0x7000 + 0x0 = 0x7000\]
• \[\text{In Dezimal: } \text{Physische Adresse} = 28672 \]

Zusammenfassung:Die physische Adresse für die logische Adresse (Segment-Offset-Paar: Segment 1, Offset: 0x3000) ist 0x7000 (Dezimal: 28672).

Zusammengefasst umfasst der Prozess die Bestimmung des relevanten Segments, die Zerlegung der logischen Adresse in Seitennummer und Offset, und die Berechnung der physischen Adresse durch Addition der Basisadresse der entsprechenden Seite und des Offsets.

Aufgabe 4)

Cache Management und Swapping: Die Verwaltung von Zwischenspeichern (Caches) und das Austauschen von Daten zwischen RAM und Sekundärspeicher sind wichtige Mechanismen zur Effizienzsteigerung und Optimierung der Systemleistung in Betriebssystemen. Betrachten Sie dabei die Cache-Hierarchie (L1, L2, L3), Konsistenzprotokolle (Write-through vs. Write-back), und die Swapping-Strategien wie LRU (Least Recently Used) und FIFO (First-In-First-Out).

a)

Erkläre die Unterschiede und Funktionen der verschiedenen Cache-Level (L1, L2, L3) in Bezug auf Zugriffsgeschwindigkeit, Größe und Position in der Cache-Hierarchie.

Lösung:

Unterschiede und Funktionen der verschiedenen Cache-Level (L1, L2, L3):

• L1-Cache:
  • Zugriffsgeschwindigkeit: Der L1-Cache ist der schnellste Cache in der Hierarchie. Er bietet die schnellsten Zugriffszeiten, da er sich direkt im Prozessor-Kern befindet.
  • Größe: Der L1-Cache ist der kleinste Cache in der Hierarchie. Er hat typischerweise eine Größe von 32KB bis 128KB pro Kern.
  • Position: Der L1-Cache sitzt direkt im Prozessor-Kern, was sehr schnelle Datenzugriffe ermöglicht. Es gibt oft separate L1-Caches für Daten (L1-D) und Instruktionen (L1-I).
• L2-Cache:
  • Zugriffsgeschwindigkeit: Der L2-Cache ist langsamer als der L1-Cache, aber schneller als der L3-Cache. Er bietet immer noch schnelle Zugriffszeiten, jedoch mit etwas höherer Latenz.
  • Größe: Der L2-Cache ist größer als der L1-Cache, typischerweise zwischen 256KB und 1MB pro Kern.
  • Position: Der L2-Cache befindet sich ebenfalls im Prozessor, jedoch in einer Ebene zwischen dem L1-Cache und dem L3-Cache. Er ist oft gemeinsam genutzte Ressource für einen einzelnen Prozessor-Kern.
• L3-Cache:
  • Zugriffsgeschwindigkeit: Der L3-Cache ist langsamer als die L1- und L2-Caches, aber immer noch schneller als der Hauptspeicher (RAM). Er dient als eine schnelle Zwischenspeicherung für häufig genutzte Daten.
  • Größe: Der L3-Cache ist der größte Cache in der Hierarchie. Die Größe variiert typischerweise zwischen 4MB und 32MB, abhängig von der Architektur und dem Prozessor.
  • Position: Der L3-Cache ist eine gemeinsame Ressource, die von allen Kernen einer CPU gemeinsam genutzt wird. Er befindet sich auf der Ebene des Prozessors, aber außerhalb der einzelnen Kerne.

b)

Beschreibe die Write-through und Write-back Konsistenzprotokolle. Erkläre, wie diese Protokolle die Cache-Konsistenz sicherstellen und vergleiche ihre Vor- und Nachteile.

Lösung:

Write-through und Write-back Konsistenzprotokolle:

• Write-through Protokoll:
  • Funktionsweise: Bei diesem Protokoll werden Daten sofort in den Hauptspeicher geschrieben, sobald sie in den Cache geschrieben werden. Das bedeutet, dass jede Schreiboperation nicht nur die Daten im Cache, sondern auch im Hauptspeicher aktualisiert.
  • Cache-Konsistenz: Da Daten im Hauptspeicher immer aktuell sind, wird die Konsistenz zwischen Cache und Hauptspeicher direkt gewährleistet.
  • Vorteile:
    • Einfachere Implementierung und bessere Konsistenz zwischen Cache und Hauptspeicher.
    • Bei Systemabstürzen bleiben die Daten im Hauptspeicher intakt und aktuell.
  • Nachteile:
    • Langsamere Schreibgeschwindigkeit, da jeder Schreibvorgang sowohl den Cache als auch den Hauptspeicher betrifft.
    • Erhöhte Speicherbandbreitennutzung durch häufige Schreibvorgänge in den Hauptspeicher.
• Write-back Protokoll:
  • Funktionsweise: Bei diesem Protokoll werden Daten beim Schreiben zunächst nur im Cache aktualisiert. Die Daten werden erst dann in den Hauptspeicher geschrieben, wenn sie aus dem Cache verdrängt werden (d.h. wenn sie von neuen Daten überschrieben werden müssen).
  • Cache-Konsistenz: Die Konsistenz wird durch das sogenannte Dirty-Bit gewährleistet, das anzeigt, ob der Cache-Eintrag geändert wurde und in den Hauptspeicher zurückgeschrieben werden muss.
  • Vorteile:
    • Schnellere Schreibgeschwindigkeit, da die meisten Schreibvorgänge nur den Cache betreffen.
    • Reduzierte Speicherbandbreitennutzung, da weniger oft auf den Hauptspeicher zugegriffen wird.
  • Nachteile:
    • Komplexere Implementierung und größere Anforderungen zur Sicherstellung der Datenkonsistenz.
    • Bei Stromausfällen oder Systemabstürzen können Daten verloren gehen, da sie noch nicht in den Hauptspeicher geschrieben wurden.

Vergleich:

• Write-through bietet einfachere Konsistenz und Sicherheit bei Stromausfällen, ist jedoch langsamer und belastet die Speicherbandbreite mehr.
• Write-back bietet eine schnellere Leistung und entlastet die Speicherbandbreite, fordert jedoch eine komplexere Verwaltung und birgt ein höheres Risiko beim Datenverlust bei Systemfehlern.

c)

Angenommen, ein System verwendet die Least Recently Used (LRU) Swapping-Strategie. Erläutere den Algorithmus dieser Strategie und berechne die Anzahl der Page-Faults für die folgende Referenz-Sequenz (gehe von 3 verfügbarer Frames aus):

• Referenz-Sequenz: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2

Lösung:

Least Recently Used (LRU) Swapping-Strategie:

Die LRU-Strategie basiert darauf, dass die Seite, die am längsten nicht benutzt wurde, als nächstes verdrängt wird, wenn neuer Speicherplatz benötigt wird. Dies wird durch das Nachverfolgen der Zugriffszeitpunkte für jede Seite im Speicher erreicht. Wenn eine Seite ersetzt werden muss, wird diejenige Seite ausgewählt, die am längsten nicht benutzt wurde.

Algorithmus der LRU-Strategie:

• Halte eine Liste der Seiten im Speicher und aktualisiere diese Liste bei jedem Zugriff, sodass die zuletzt verwendete Seite an das Ende der Liste verschoben wird.
• Wenn eine neue Seite geladen werden muss und kein freier Speicherplatz vorhanden ist, entferne die Seite am Anfang der Liste (d.h., die Seite, die am längsten nicht benutzt wurde).
• Lade die neue Seite in den frei gewordenen Speicherplatz und füge sie ans Ende der Liste hinzu.

Berechnung der Page-Faults für die gegebene Referenz-Sequenz:

• Referenz-Sequenz: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2
• Anzahl der Frames: 3

Schritte:

1. Initialer Zustand: [ -, -, - ]
2. Referenz: 7 → [ 7, -, - ] (Page-Fault)
3. Referenz: 0 → [ 7, 0, - ] (Page-Fault)
4. Referenz: 1 → [ 7, 0, 1 ] (Page-Fault)
5. Referenz: 2 → [ 2, 0, 1 ] (Page-Fault, 7 wird ersetzt)
6. Referenz: 0 → [ 2, 0, 1 ] (Kein Page-Fault)
7. Referenz: 3 → [ 2, 0, 3 ] (Page-Fault, 1 wird ersetzt)
8. Referenz: 0 → [ 2, 0, 3 ] (Kein Page-Fault)
9. Referenz: 4 → [ 4, 0, 3 ] (Page-Fault, 2 wird ersetzt)
10. Referenz: 2 → [ 4, 2, 3 ] (Page-Fault, 0 wird ersetzt)
11. Referenz: 3 → [ 4, 2, 3 ] (Kein Page-Fault)
12. Referenz: 0 → [ 0, 2, 3 ] (Page-Fault, 4 wird ersetzt)
13. Referenz: 3 → [ 0, 2, 3 ] (Kein Page-Fault)
14. Referenz: 2 → [ 0, 2, 3 ] (Kein Page-Fault)

Anzahl der Page-Faults: 8

Insgesamt gibt es 8 Page-Faults für die gegebene Referenz-Sequenz bei Verwendung der LRU-Strategie mit 3 verfügbaren Frames.