Betriebssysteme und Betriebssystemtechnik - Exam

Aufgabe 1)

Systemaufrufe und Benutzer-Kernel-InteraktionSystemaufrufe (Syscalls) ermöglichen die Kommunikation zwischen Benutzerprogrammen und dem Betriebssystemkern. Sie sind Schnittstellen, um Dienste des Betriebssystems in Anspruch zu nehmen und erfordern einen Wechsel in den Kernel-Modus. Beispiele für Systemaufrufe sind read(), write(), fork() und exec(). Der Ablauf eines Systemaufrufs kann in mehrere Phasen unterteilt werden, die unter anderem den Übergang vom Benutzerprozess über den Syscall-Handler hin zum Kernel und die Rückgabe an den Benutzerprozess beinhalten.

• Systemaufrufe (Syscalls): Schnittstellen, um Dienste des Betriebssystems zu nutzen.
• Beispiele: read(), write(), fork(), exec()
• Ablauf: Benutzerprozess → Syscall-Handler → Kernel → Rückgabe an Benutzerprozess
• Wichtige Register: eax für Syscall-Nummer, ebx bis edi für Argumente
• Übergang: Von Benutzermodus zu Kernelmodus mittels int- oder sysenter-Befehl

a)

Beschreibe detailliert anhand eines Beispiels den Ablauf eines Systemaufrufs (z.B. read()) von der Ausführung im Benutzerprogramm bis zur Rückkehr der Kontrolle an das Benutzerprogramm. Gehe dabei auf die Registerbelegung und den Moduswechsel ein.

Lösung:

• Systemaufrufe (Syscalls): Systemaufrufe sind die Schnittstellen, die es Benutzerprogrammen ermöglichen, auf Dienste des Betriebssystems zuzugreifen. Sie führen zu einem Wechsel vom Benutzermodus in den Kernelmodus, wodurch der Prozess auf Funktionen zugreifen kann, die normalerweise durch das Betriebssystem vor direktem Zugriff geschützt sind.

• 1. Initiierung des Systemaufrufs: Wenn ein Benutzerprogramm den read()-Aufruf ausführen möchte, wird der entsprechende Systemaufruf-Code in das eax-Register geladen. Beispielsweise könnte eax den Wert 3 (angenommene Nummer für read()) erhalten. Die Argumente, die an den Systemaufruf übergeben werden sollen, werden in die Register ebx, ecx und edx geladen.

•   // Pseudocode-Beispiel  mov eax, 3 // Syscall-Nummer für read()  mov ebx, file_descriptor // Dateideskriptor  mov ecx, buffer // Puffer zum Speichern der gelesenen Daten  mov edx, count // Anzahl der zu lesenden Bytes  

• 2. Moduswechsel: Der Prozess wechselt nun in den Kernelmodus. Dies geschieht durch Ausführung eines speziellen Befehls wie int 0x80 (auf x86-Architekturen), der einen Software-Interrupt auslöst.

•   int 0x80  

• 3. Systemaufruf-Handler: Der Systemaufruf-Handler des Betriebssystems übernimmt die Kontrolle. Der Handler überprüft die in den Registern übergebenen Werte, um zu bestimmen, welcher Dienst angefordert wird. Er ruft die entsprechende Kernel-Funktion auf, um die Arbeit zu erledigen - in diesem Fall das Lesen der Daten aus einer Datei in den angegebenen Puffer.
• 4. Ausführung der Kernel-Funktion: Der Kernel führt die read()-Operation aus, wobei er die Daten vom Dateisystem liest und in den vom Benutzer angegebenen Puffer schreibt.
• 5. Rückkehr zum Benutzerprozess: Nach Abschluss der Leseoperation speichert der Kernel den Status und die Rückgabewerte (z.B. Anzahl der gelesenen Bytes oder Fehlercodes) wieder in den Registern ab und wechselt zurück in den Benutzermodus, indem er den vorherigen Zustand des Benutzerprozesses wiederherstellt.
• Pseudocode für die Rückkehr:

•  // Rückgabewert in eax; hier die Anzahl der gelesenen Bytes  mov eax, num_bytes_read  

• 6. Fortsetzung des Benutzerprogramms: Das Benutzerprogramm empfängt die Kontrolle zurück und kann die Ergebnisse des Systemaufrufs nutzen, z.B. die gelesenen Daten im Puffer weiter verarbeiten.

b)

Erkläre den Unterschied zwischen den Befehlen int und sysenter beim Übergang vom Benutzer- in den Kernelmodus. Welche Vor- und Nachteile bieten die jeweiligen Methoden?

Lösung:

• Übergang vom Benutzer- in den Kernelmodus: Beim Übergang vom Benutzer- in den Kernelmodus kommen spezielle Befehle zum Einsatz. Zwei häufig verwendete Befehle sind int und sysenter. Beide dienen dazu, einen Systemaufruf durchzuführen, jedoch unterscheiden sie sich in ihrer Implementierung und Effizienz.

• int ist ein allgemeiner Befehl zur Ausführung eines Software-Interrupts. Ein Beispiel ist int 0x80, das auf x86-Architekturen oft verwendet wird, um Systemaufrufe zu initiieren.

•   int 0x80  

• Vorteile:
  • - Einfachheit: Der int-Befehl ist leicht zu verstehen und zu verwenden.
  • - Flexibilität: Er kann für eine Vielzahl von Interrupts und Ausnahmen verwendet werden, nicht nur für Systemaufrufe.
• Nachteile:
  • - Performance: Der int-Befehl ist relativ langsam, da er zusätzlichen Overhead durch das Speichern und Wiederherstellen vieler Register verursacht.
  • - Komplexität: Die allgemeine Natur des int-Befehls kann zu zusätzlicher Komplexität im Interrupt-Handling-Code führen.

• sysenter ist ein spezieller Befehl, der von modernen Prozessoren (ab der Pentium-II-Generation) bereitgestellt wird, um schneller in den Kernelmodus zu wechseln und Systemaufrufe durchzuführen.

•   sysenter  

• Vorteile:
  • - Performance: sysenter ist optimiert für schnelle Kontextwechsel und reduziert den Overhead im Vergleich zu int-Befehlen.
  • - Effizienz: Der Befehl ist speziell für den Übergang in den Kernelmodus und das Handling von Systemaufrufen konzipiert.
• Nachteile:
  • - Komplexität: Die Implementierung von sysenter kann komplizierter sein und erfordert Unterstützung durch das Betriebssystem und den Prozessor.
  • - Einschränkungen: sysenter ist auf bestimmte Architekturen und Prozessoren beschränkt, wodurch die Portabilität eingeschränkt sein kann.

• int-Befehle bieten einfachere, aber weniger effiziente Methoden zum Übergang in den Kernelmodus für Systemaufrufe, während sysenter eine leistungsfähigere, aber komplexere und spezialisierte Methode bietet.

c)

Angenommen, ein Prozess macht den Systemaufruf fork(), um einen neuen Prozess zu erzeugen. Erkläre, welche Schritte im Kernel unternommen werden, um diesen neuen Prozess zu erstellen. Welche Register und Speicherbereiche sind dabei von Bedeutung und wie werden sie verwendet?

Lösung:

• Systemaufrufe (Syscalls): Systemaufrufe sind Schnittstellen, die es ermöglichen, Dienste des Betriebssystems zu nutzen.
• Beispiele: read(), write(), fork(), exec()
• Ablauf: Benutzerprozess → Syscall-Handler → Kernel → Rückgabe an Benutzerprozess
• Wichtige Register: eax für Syscall-Nummer, ebx bis edi für Argumente
• Übergang: Von Benutzermodus zu Kernelmodus mittels int- oder sysenter-Befehl

• 1. Syscall-Nummer vorbereiten und Übergang zum Kernelmodus: Der Prozess lädt die Syscall-Nummer für fork() in das eax-Register und führt den int 0x80-Befehl oder einen sysenter aus, um in den Kernelmodus zu wechseln.

•  mov eax, fork_syscall_number  // Beispielsweise 2 für fork()  int 0x80  // Oder sysenter 

• 2. Syscall-Handler: Der Syscall-Handler im Kernel übernimmt die Kontrolle. Er entschlüsselt anhand des Werts im eax-Register, dass der fork()-Systemaufruf gewünscht ist.
• 3. Prozessstruktur erstellen: Der Kernel erstellt eine neue Prozessstruktur (Process Control Block, PCB) für den Kindprozess. Diese Struktur enthält Informationen über den Zustand des Prozesses, offene Dateien, Benutzer-ID, etc.
• 4. Speicherbereiche duplizieren: Der Speicher des Elternprozesses wird dupliziert. Dies umfasst den Benutzeradressraum, wie Code-, Daten- und Stack-Segmente. Moderne Betriebssysteme verwenden Techniken wie Copy-on-Write, um Speicher effizient zu nutzen.
• 5. Registerzustand kopieren: Die CPU-Register des Elternprozesses werden in die neue Prozessstruktur kopiert. Dies umfasst Register wie eax, ebx, ecx, edx, esi, edi, esp, ebp, und das EFLAGS-Register.

•  eax, ebx, ecx, edx, esi, edi, esp, ebp, eflags 

• 6. Kind- und Elternprozess differenzieren: Der Kindprozess erhält als Rückgabewert von fork() null in eax, während der Elternprozess die Prozess-ID des Kindprozesses in eax erhält.

•  // Im Kindprozess: eax = 0  // Im Elternprozess: eax = Kind-Prozess-ID 

• 7. Einfügen in die Prozessliste: Der neue Prozess wird in die Prozessliste des Betriebssystems eingefügt und ist somit für die Scheduler verfügbar.
• 8. Rückkehr zum Benutzerprozess: Der Kernel stellt den vorherigen Zustand des Elternprozesses wieder her und gibt die Kontrolle an beide Prozesse zurück. Sowohl der Eltern- als auch der Kindprozess setzen die Ausführung nach dem fork()-Aufruf fort, wobei sie die unterschiedlichen Rückgabewerte verwenden, um ihre Rollen zu erkennen.

Aufgabe 2)

Planung von Prozessen mittels Scheduling-AlgorithmenIn einem Betriebssystem werden Prozesse geplant und zur Ausführung gebracht, wobei verschiedene Scheduling-Algorithmen wie FCFS (First-Come, First-Served), SJF (Shortest Job First) und RR (Round Robin) angewendet werden. Diese Algorithmen bestimmen die Reihenfolge der Prozessausführung und beeinflussen Parameter wie Wartezeit, Durchlaufzeit, Fairness und CPU-Auslastung. Gegeben sei eine Liste von Prozessen mit ihren Ankunftszeiten und Ausführungszeiten, die geplant werden sollen.

• FCFS: Prozesse werden in der Reihenfolge ihres Eintreffens abgearbeitet.
• SJF: Der Prozess mit der kürzesten Ausführungszeit wird zuerst ausgeführt. Nicht-präemptiv.
• RR: Jeder Prozess erhält für eine festgelegte Zeitspanne (Time Quantum) die CPU. Präemptiv, zirkuläres Verfahren.

a)

1. FCFS-Algorithmus Gegeben sei eine Liste von Prozessen mit den Ankunfts- und Ausführungszeiten in folgender Tabelle:

• Prozess A: Ankunftszeit: 0, Ausführungszeit: 4
• Prozess B: Ankunftszeit: 1, Ausführungszeit: 3
• Prozess C: Ankunftszeit: 2, Ausführungszeit: 1
• Prozess D: Ankunftszeit: 3, Ausführungszeit: 2

Bestimme die Reihenfolge der Prozesse, ihre Wartezeiten und die durchschnittliche Wartezeit, wenn der FCFS-Algorithmus verwendet wird.

Lösung:

1. FCFS-Algorithmus Gegeben sei eine Liste von Prozessen mit den Ankunfts- und Ausführungszeiten in folgender Tabelle:

• Prozess A: Ankunftszeit: 0, Ausführungszeit: 4
• Prozess B: Ankunftszeit: 1, Ausführungszeit: 3
• Prozess C: Ankunftszeit: 2, Ausführungszeit: 1
• Prozess D: Ankunftszeit: 3, Ausführungszeit: 2

Bestimme die Reihenfolge der Prozesse, ihre Wartezeiten und die durchschnittliche Wartezeit, wenn der FCFS-Algorithmus verwendet wird.Reihenfolge der Prozesse:Beim FCFS-Algorithmus werden die Prozesse in der Reihenfolge ihres Eintreffens abgearbeitet. Dies bedeutet:

• Prozess A (Ankunftszeit: 0)
• Prozess B (Ankunftszeit: 1)
• Prozess C (Ankunftszeit: 2)
• Prozess D (Ankunftszeit: 3)

Berechnung der Wartezeiten:Die Wartezeit eines Prozesses ist die Zeit, die er in der Warteschlange verbringt, bevor er ausgeführt wird.Die Wartezeiten der einzelnen Prozesse sind:

• Prozess A: Wartezeit = 0 (da er sofort bei Ankunft ausgeführt wird)
• Prozess B: Wartezeit = 4 (Prozess A benötigt 4 Zeiteinheiten)
• Prozess C: Wartezeit = 7 (Prozess A + Prozess B benötigen zusammen 7 Zeiteinheiten)
• Prozess D: Wartezeit = 8 (Prozess A + Prozess B + Prozess C benötigen zusammen 8 Zeiteinheiten)

Berechnung der durchschnittlichen Wartezeit:Die durchschnittliche Wartezeit berechnet sich aus dem Mittelwert der Wartezeiten der Prozesse:

• Wartezeit von Prozess A: 0
• Wartezeit von Prozess B: 4
• Wartezeit von Prozess C: 7
• Wartezeit von Prozess D: 8

Die durchschnittliche Wartezeit ist somit:\[ \text{Durchschnittliche Wartezeit} = \frac{{0 + 4 + 7 + 8}}{4} = \frac{19}{4} = 4.75 \] Also beträgt die durchschnittliche Wartezeit 4.75 Zeiteinheiten.

b)

2. SJF-Algorithmus Verwende dieselbe Tabelle der Prozesse aus dem vorherigen Teil. Bestimme die Reihenfolge der Prozesse, ihre Wartezeiten und die durchschnittliche Wartezeit unter Anwendung des SJF-Algorithmus. Gehe davon aus, dass der Algorithmus nicht präemptiv ist.

Lösung:

2. SJF-Algorithmus Verwendet wird dieselbe Tabelle der Prozesse aus dem vorherigen Teil.

• Prozess A: Ankunftszeit: 0, Ausführungszeit: 4
• Prozess B: Ankunftszeit: 1, Ausführungszeit: 3
• Prozess C: Ankunftszeit: 2, Ausführungszeit: 1
• Prozess D: Ankunftszeit: 3, Ausführungszeit: 2

Bestimme die Reihenfolge der Prozesse, ihre Wartezeiten und die durchschnittliche Wartezeit unter Anwendung des SJF-Algorithmus.Um dies zu lösen, gehen wir schrittweise vor:1. Reihenfolge der Prozesse: Beim SJF-Algorithmus (Shortest Job First) wird der Prozess mit der kürzesten Ausführungszeit zuerst ausgeführt. Da der Algorithmus nicht-präemptiv ist, wird der gesamte Prozess ausgeführt, bevor zum nächsten übergegangen wird.Beachten wir die Prozesse und organisieren sie nach ihrer Ankunftszeit und der kürzesten Ausführungszeit:

• Zu Beginn (t = 0) ist nur Prozess A verfügbar. Daher beginnt Prozess A.
• Nach Abschluss von Prozess A (t = 4) sind Prozesse B, C und D verfügbar. Hier hat Prozess C die kürzeste Ausführungszeit.
• Danach (t = 5, nach Abschluss von Prozess C) sind noch Prozesse B und D verfügbar. Prozess D hat die kürzeste Ausführungszeit.
• Schließlich (t = 7, nach Abschluss von Prozess D) bleibt nur noch Prozess B übrig.

Die Reihenfolge der Prozesse nach dem SJF-Algorithmus ist somit:

• Prozess A (Ankunftszeit: 0, Ausführungszeit: 4)
• Prozess C (Ankunftszeit: 2, Ausführungszeit: 1)
• Prozess D (Ankunftszeit: 3, Ausführungszeit: 2)
• Prozess B (Ankunftszeit: 1, Ausführungszeit: 3)

Berechnung der Wartezeiten:Die Wartezeit eines Prozesses ist die Zeit, die er in der Warteschlange verbringt, bevor er ausgeführt wird.Die Wartezeiten der einzelnen Prozesse sind:

• Prozess A: Wartezeit = 0 (da er sofort bei seiner Ankunft ausgeführt wird)
• Prozess C: Wartezeit = 4 (Prozess A benötigt 4 Zeiteinheiten)
• Prozess D: Wartezeit = 5 (Prozess A + Prozess C benötigen zusammen 5 Zeiteinheiten)
• Prozess B: Wartezeit = 7 (Prozess A + Prozess C + Prozess D benötigen zusammen 7 Zeiteinheiten)

Berechnung der durchschnittlichen Wartezeit:Die durchschnittliche Wartezeit berechnet sich aus dem Mittelwert der Wartezeiten der Prozesse:

• Wartezeit von Prozess A: 0
• Wartezeit von Prozess C: 4
• Wartezeit von Prozess D: 5
• Wartezeit von Prozess B: 7

Die durchschnittliche Wartezeit ist somit:\[ \text{Durchschnittliche Wartezeit} = \frac{{0 + 4 + 5 + 7}}{4} = \frac{16}{4} = 4 \] Also beträgt die durchschnittliche Wartezeit 4 Zeiteinheiten.

c)

3. RR-Algorithmus mit Zeitquantum Angenommen, das Zeitquantum für den RR-Algorithmus beträgt 2 Zeiteinheiten. Bestimme die Reihenfolge der Prozesse, ihre Wartezeiten und die durchschnittliche Wartezeit, unter Anwendung des RR-Algorithmus mit der gegebenen Prozess-Tabelle.

Lösung:

3. RR-Algorithmus mit Zeitquantum Angenommen, das Zeitquantum für den RR-Algorithmus beträgt 2 Zeiteinheiten. Bestimme die Reihenfolge der Prozesse, ihre Wartezeiten und die durchschnittliche Wartezeit, unter Anwendung des RR-Algorithmus mit der gegebenen Prozess-Tabelle.

• Prozess A: Ankunftszeit: 0, Ausführungszeit: 4
• Prozess B: Ankunftszeit: 1, Ausführungszeit: 3
• Prozess C: Ankunftszeit: 2, Ausführungszeit: 1
• Prozess D: Ankunftszeit: 3, Ausführungszeit: 2

Um dies zu lösen, gehen wir schrittweise vor:1. Reihenfolge der Prozesse:Beim RR-Algorithmus (Round Robin) erhält jeder Prozess eine festgelegte Zeitspanne (das Zeitquantum) für die CPU. Ist das Zeitquantum abgelaufen, wird der nächste Prozess in der Reihenfolge bedient. Dies wird so lange fortgesetzt, bis alle Prozesse vollständig abgearbeitet sind. In diesem Beispiel beträgt das Zeitquantum 2 Zeiteinheiten.Zeitschema:Das Zeitplanungsverfahren in Zeiteinheiten:

• t=0: Prozess A beginnt und läuft 2 Zeiteinheiten (Restzeit = 2).
• t=2: Prozess B beginnt und läuft 2 Zeiteinheiten (Restzeit = 1).
• t=4: Prozess C beginnt und läuft 1 Zeiteinheit (Restzeit = 0; abgeschlossen).
• t=5: Prozess D beginnt und läuft 2 Zeiteinheiten (Restzeit = 0; abgeschlossen).
• t=7: Prozess A läuft weiter für 2 Zeiteinheiten (Restzeit = 0; abgeschlossen).
• t=9: Prozess B läuft weiter für 1 Zeiteinheit (Restzeit = 0; abgeschlossen).

Die Reihenfolge der Prozesse im Round Robin Scheduling ist somit:

• A, B, C, D, A, B

2. Berechnung der Wartezeiten:Die Wartezeit eines Prozesses ist die Zeit, die er in der Warteschlange verbringt, abzüglich seiner Ankunftszeit und der Zeit, bis er das erste Mal ausgeführt wird.

• Prozess A:
  • 1. Periode: Wartezeit = 0
  • 2. Periode: Wartezeit = t=7 - t=4 = 3
  • Gesamtwartezeit = 0 + 3 = 3
• Prozess B:
  • 1. Periode: Wartezeit = t=2 - t=1 = 1
  • 2. Periode: Wartezeit = t=9 - t=4 = 4
  • Gesamtwartezeit = 1 + 4 = 5
• Prozess C: Wartezeit = 4 - 2 = 2
• Prozess D: Wartezeit = 5 - 3 = 2

3. Berechnung der durchschnittlichen Wartezeit:Die durchschnittliche Wartezeit berechnet sich aus dem Mittelwert der Wartezeiten der Prozesse:\[ \text{Durchschnittliche Wartezeit} = \frac{3 + 5 + 2 + 2}{4} = \frac{12}{4} = 3 \] Also beträgt die durchschnittliche Wartezeit 3 Zeiteinheiten.

d)

4. Vergleich der Algorithmen Vergleiche die drei Algorithmen (FCFS, SJF und RR) hinsichtlich der durchschnittlichen Wartezeit, Durchlaufzeit, Fairness und CPU-Auslastung. Welche Vor- und Nachteile bietet jeder Algorithmus in Hinsicht auf die oben genannten Kriterien?

Lösung:

4. Vergleich der AlgorithmenVergleiche die drei Algorithmen (FCFS, SJF und RR) hinsichtlich der durchschnittlichen Wartezeit, Durchlaufzeit, Fairness und CPU-Auslastung. Welche Vor- und Nachteile bietet jeder Algorithmus in Hinsicht auf die oben genannten Kriterien?1. FCFS-Algorithmus (First-Come, First-Served):

• Durchschnittliche Wartezeit: Dies ist die Zeit, die Prozesse in der Warteschlange verbringen. Beim FCFS-Algorithmus kann die durchschnittliche Wartezeit hoch sein, wenn langlaufende Prozesse als Erste eintreffen.
• Durchlaufzeit: Die Durchlaufzeit ist oft unvorhersehbar und kann für spätere Prozesse sehr hoch sein, weil sie auf die Fertigstellung der vorherigen Prozesse warten müssen.
• Fairness: Der Algorithmus ist fair in dem Sinne, dass Prozesse in der Reihenfolge ihres Eintreffens bearbeitet werden.
• CPU-Auslastung: Die CPU wird kontinuierlich mit dem aktuell laufenden Prozess ausgelastet, wodurch keine Overheads für Kontextwechsel entstehen.

Vorteile:

• Einfach zu implementieren.
• Keine Overheads durch Kontextwechsel.

Nachteile:

• Lange Wartezeiten für nachfolgende Prozesse.
• Kann zu „convoy effect“ führen, bei dem ein langer Prozess viele kürzere Prozesse blockiert.

2. SJF-Algorithmus (Shortest Job First):

• Durchschnittliche Wartezeit: Die durchschnittliche Wartezeit ist in der Regel geringer als bei FCFS, da kürzere Prozesse zuerst ausgeführt werden.
• Durchlaufzeit: In der Regel kürzer als bei FCFS, da kurze Prozesse nicht durch lange Prozesse verzögert werden.
• Fairness: Der Algorithmus bevorzugt kürzere Prozesse, was für lange Prozesse unfair sein kann.
• CPU-Auslastung: Relativ hoch, da Prozesse schnell abgearbeitet werden und damit die CPU effizient genutzt wird.

Vorteile:

• Kürzere durchschnittliche Warte- und Durchlaufzeiten.
• Effiziente CPU-Nutzung.

Nachteile:

• Lange Prozesse müssen möglicherweise sehr lange warten.
• Mögliche Ungerechtigkeit gegenüber langen Prozessen.

3. RR-Algorithmus (Round Robin) mit Zeitquantum:

• Durchschnittliche Wartezeit: Abhängig von der Länge des Zeitquantums. Kleinere Zeitquanten können die Wartezeit erhöhen.
• Durchlaufzeit: Kann höher als bei SJF sein, da Prozesse oft unterbrochen werden.
• Fairness: Sehr fair, da jeder Prozess unabhängig von seiner Länge regelmäßig CPU-Zeit erhält.
• CPU-Auslastung: Potsenziell niedriger als bei den anderen Algorithmen aufgrund der Overheads durch häufige Kontextwechsel.

Vorteile:

• Sehr fair gegenüber allen Prozessen.
• Keine Prozessverzögerung aufgrund von langen Prozessen.

Nachteile:

• Kontinuierliche Kontextwechsel können zu hohem Overhead führen.
• Effizienz und Durchlaufzeit können beeinträchtigt werden, insbesondere bei kleinen Zeitquanten.

Zusammenfassend lässt sich sagen:

• FCFS ist einfach, aber kann zu langen Wartezeiten und ineffizienter Verarbeitung führen.
• SJF bietet kürzere Wartezeiten und höhere Effizienz, kann aber unfair gegenüber langen Prozessen sein.
• RR sorgt für Fairness und weniger Verzögerungen durch lange Prozesse, erfordert jedoch eine sorgfältige Wahl des Zeitquantums, um Overheads zu minimieren.

Aufgabe 3)

Speicherallokationsmethoden und deren Effizienz in BetriebssystemenEin Betriebssystem hat die Aufgabe, Speicher effizient zu verwalten und den Prozessen zuzuweisen, sodass diese ordnungsgemäß und effizient ausgeführt werden können. Zu den wichtigsten Methoden gehören Paging und Segmentation. Dies sind Techniken, die den Speicher in unterschiedlichen Weisen organisieren und verwalten.

• Paging: Der Speicher wird in gleich große Blöcke, sogenannte Seiten, unterteilt. Dabei werden virtuelle Adressen in Seitenrahmen umgewandelt.
• Segmentation: Hierbei wird der Speicher in logische Segmente unterschiedlicher Größe unterteilt, die verschiedenen logischen Einheiten entsprechen.
• Virtuelle Adressierung: Dies ermöglicht eine Trennung von logischen (virtuellen) und physischen Adressen.
• Seitenersetzung: Um mit Seitenfehlern umzugehen, kommen Strategien wie FIFO (First-In-First-Out) und LRU (Least Recently Used) zum Einsatz.
• Vorteile: Eine effiziente Speicherverwaltung und geringere Fragmentierung sind wichtige Vorteile dieser Techniken.
• Nachteile: Ein zusätzlicher Verwaltungsaufwand durch Tabellen und mögliche Leistungseinbußen sind Nachteile.

Im folgenden Szenario sollst Du verschiedene Aspekte dieser Techniken und deren Anwendungen analysieren.

a)

A) Ein System nutzt Paging zur Speicherallokation. Gegeben sei eine Seitengröße von 4 KB (4096 Bytes). Ein Programm hat eine Gesamtgröße von 25,700 Bytes.

• a) Berechne die Anzahl der Seiten, die für dieses Programm benötigt werden.
• b) Nenne die Anzahl der externen und internen Fragmentierung.

Lösung:

Subexercise A)

• a) Berechne die Anzahl der Seiten, die für dieses Programm benötigt werden:

Um die Anzahl der Seiten zu berechnen, die für ein Programm mit einer Gesamtgröße von 25,700 Bytes benötigt werden, verwenden wir die Seitengröße von 4 KB (4096 Bytes). Hier sind die detaillierten Schritte zur Berechnung:

• Gesamtgröße des Programms: 25,700 Bytes
• Seitengröße: 4 KB (4096 Bytes)

Die Anzahl der benötigten Seiten berechnet man wie folgt:

• Teile die Gesamtgröße des Programms durch die Seitengröße:\(\frac{25,700}{4096} \approx 6.273\) Seiten
• Da eine Seite nicht in Teile aufgespalten werden kann, runden wir auf die nächste volle Zahl auf: Die Anzahl der Seiten beträgt also 7.

• b) Nenne die Anzahl der externen und internen Fragmentierung:

Externe Fragmentierung: Beim Paging gibt es keine externe Fragmentierung, da jede Seite gleich groß ist und die Speicherblöcke kontinuierlich zugewiesen werden. Interne Fragmentierung: Interne Fragmentierung tritt auf, wenn der Speicher innerhalb einer Seite nicht vollständig genutzt wird. Wir berechnen dies wie folgt:

• Gesamte Speichergröße des Programms: 25,700 Bytes
• Anzahl der benötigten Seiten: 7
• Speicherplatz pro Seite: 4096 Bytes

Interne Fragmentierung in der letzten Seite:

• Berechne die gesamte belegte Speichergröße: 7 Seiten × 4096 Bytes = 28,672 Bytes
• Berechne die interne Fragmentierung:

Interne Fragmentierung = Belegte Speichergröße - Gesamtgröße des Programms = 28,672 Bytes - 25,700 Bytes = 2,972 BytesAlso haben wir eine interne Fragmentierung von 2,972 Bytes. Zusammengefasst:

• Anzahl der benötigten Seiten: 7
• Externe Fragmentierung: Keine
• Interne Fragmentierung: 2,972 Bytes

b)

B) Erläutere das Konzept der virtuellen Adressierung und wie sie durch Paging und Segmentation unterstützt wird. In Deiner Erklärung sollten folgende Punkte erscheinen:

• Definition von virtuellen Adressen und physikalischen Adressen.
• Wie Paging und Segmentation zur Realisierung dieser Adressierung beitragen.

Lösung:

Subexercise B)

• Erläutere das Konzept der virtuellen Adressierung und wie sie durch Paging und Segmentation unterstützt wird.

• Definition von virtuellen Adressen und physikalischen Adressen:Virtuelle Adressen sind die Adressen, die von Programmen und Anwendungen verwendet werden, um auf Speicher zuzugreifen. Diese Adressen sind nicht die tatsächlichen physikalischen Adressen im Arbeitsspeicher, sondern abstrahierte Adressen, die vom Betriebssystem auf physikalische Adressen im Speicher abgebildet werden.Physikalische Adressen hingegen beziehen sich auf die tatsächlichen Speicherorte im RAM (Random Access Memory) des Computers.

• Wie Paging und Segmentation zur Realisierung dieser Adressierung beitragen:Paging:Paging ist eine Technik zur Speicherverwaltung, bei der der virtuelle Speicher in gleich große Blöcke, sogenannte Seiten, unterteilt wird. Diese Seiten können eine feste Größe haben, wie z.B. 4 KB.
  • Jedes Programm hat seine eigenen virtuellen Adressen, die in Seiten organisiert sind. Wenn ein Programm auf eine virtuelle Adresse zugreift, wird diese Adresse durch das Betriebssystem und die Hardware-Memory-Management-Unit (MMU) in eine physikalische Adresse übersetzt, die auf einen Seitenrahmen im RAM zeigt.
  • Die Zuordnung von virtuellen zu physischen Adressen wird in einer Seitentabelle verwaltet. Diese Tabelle enthält Einträge, die die virtuellen Seiten den physischen Seitenrahmen im Speicher zuordnen.
  • Durch die Verwendung von Paging können Programme Adressen verwenden, die größer erscheinen als der tatsächlich verfügbare physikalische Speicher. Dies ermöglicht eine effizientere Nutzung des Speichers und erleichtert das Speichermanagement.
  Segmentation:Segmentation ist eine andere Technik zur Speicherverwaltung, bei der der Speicher in logische Segmente unterschiedlicher Größe unterteilt wird. Diese Segmente entsprechen verschiedenen logischen Einheiten eines Programms, wie z.B. Code, Daten oder Stack.
  • Jedes Segment hat seine eigene Basisadresse und Länge. Wenn ein Programm auf eine Adresse zugreift, gibt es einen Segmentbezeichner und einen Offset innerhalb des Segments an.
  • Die Segmenttabelle enthält Einträge, die die Segmente auf physikalische Speicherbereiche abbilden. Diese Einträge enthalten Informationen über die Basisadresse und die Länge des Segments.
  • Segmentation ermöglicht eine logischere und flexiblere Organisation des Speichers, da verschiedene Teile eines Programms auf unterschiedliche Segmente verteilt werden können.
  Zusammenfassend:Beide Techniken, Paging und Segmentation, tragen zur Realisierung der virtuellen Adressierung bei, indem sie eine Trennung der logischen Adressen, die von den Programmen verwendet werden, von den tatsächlichen physikalischen Adressen im Speicher ermöglichen. Dadurch können Ressourcen effizienter genutzt und die Speicherverwaltung vereinfacht werden. Während Paging die Zuordnung von festen Seiten auf feste Blöcke im Speicher erleichtert, ermöglicht Segmentation eine logischere Organisation, die besser zu den verschiedenen Einheiten eines Programms passen kann.

c)

C) Ein System nutzt eine LRU-Seitenersetzungsstrategie. Angenommen, die Seitentabelle kann 4 Seitenrahmen speichern und folgende Seitenreferenzfolge tritt auf: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. Zeichne die Implementierung der LRU-Seitenersetzungsstrategie und zähle die Anzahl der Seitenfehler.

Lösung:

Subexercise C)

• Ein System nutzt eine LRU-Seitenersetzungsstrategie. Angenommen, die Seitentabelle kann 4 Seitenrahmen speichern und folgende Seitenreferenzfolge tritt auf: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. Zeichne die Implementierung der LRU-Seitenersetzungsstrategie und zähle die Anzahl der Seitenfehler.

LRU (Least Recently Used) Seitenersetzungsstrategie:Die LRU-Strategie ersetzt die Seite, die am längsten nicht verwendet wurde, wenn ein Seitenfehler auftritt und kein freier Seitenrahmen verfügbar ist. Gegeben, dass wir 4 Seitenrahmen haben, zeichnen wir die Implementierung der LRU-Strategie für die gegebene Referenzfolge und zählen die Seitenfehler.

Zugriff	Seitenrahmen	1	2	3	4	Seitenfehler?
1	1	-	-	-	Ja
2	1	2	-	-	-	Ja
3	1	2	3	-	-	Ja
4	1	2	3	4	-	Ja
1	1	2	3	4	-	Nein
2	1	2	3	4	-	Nein
5	1	2	5	4	-	Ja (3 ersetzt)
1	1	2	5	4	-	Nein
2	1	2	5	4	-	Nein
3	1	2	5	3	-	Ja (4 ersetzt)
4	1	2	4	3	-	Ja (5 ersetzt)
5	1	4	5	3	-	Ja (2 ersetzt)

• Gesamtanzahl der Seitenfehler: 9

d)

D) Diskutiere die Vor- und Nachteile von Paging und Segmentation in Bezug auf:

• Speicherverwaltung und Fragmentierung
• Overhead und Leistungsfähigkeit

Gib dabei konkrete Beispiele für Szenarien, in denen jede Methode Vorteile oder Nachteile haben könnte.

Lösung:

Subexercise D)Diskutiere die Vor- und Nachteile von Paging und Segmentation in Bezug auf:

• Speicherverwaltung und Fragmentierung
• Overhead und Leistungsfähigkeit

Gib dabei konkrete Beispiele für Szenarien, in denen jede Methode Vorteile oder Nachteile haben könnte.

• Paging:

• Speicherverwaltung und Fragmentierung: Vorteile:
  • Reduziert externe Fragmentierung, da der Speicher in gleich große Seiten unterteilt wird.
  • Effiziente Nutzung des gesamten Speichers, da jede Seite unabhängig von physischen Adressen zugewiesen werden kann.
  Nachteile:
  • Erzeugt interne Fragmentierung, wenn der Speicher innerhalb einer Seite nicht vollständig genutzt wird. Zum Beispiel, wenn ein Programm nur 5 KB benötigt und die Seitengröße 4 KB beträgt, werden zwei Seiten verwendet, wobei eine Seite teilweise ungenutzt bleibt.
• Overhead und Leistungsfähigkeit:Vorteile:
  • Paging ist einfach zu implementieren und erfordert keine logische Trennung von Speichersegmenten.
  • Virtuelle Speicherverwaltung ermöglicht größeren virtuellen Speicher als physisch verfügbar.
  Nachteile:
  • Erfordert die Verwaltung von Seitentabellen, was zusätzlichen Overhead erzeugt.
  • Kann zu einer Vielzahl von Seitenfehlern führen, wenn nicht genügend Seitenrahmen verfügbar sind, was die Leistung beeinträchtigen kann.
Beispiel: Ein Betriebsystem verwendet Paging für eine Webanwendung, die mehrere kleine Module (wie Benutzerlogik und Datenbankverbindungen) verwendet. Paging ist effizient, da es den Speicher gleichmäßig aufteilt und die Verwaltung vereinfacht. Die interne Fragmentierung wird durch die Verwendung von weniger RAM-Seiten minimiert, die Gesamtleistung und die Speicherverfügbarkeit werden verbessert.
• Segmentation:
• Speicherverwaltung und Fragmentierung:Vorteile:
  • Erlaubt eine logische Trennung des Speichers in verschiedene Segmente wie Code, Daten und Stack. Dies erleichtert die Organisation und kann die Programmverständlichkeit verbessern.
  • Minimiert interne Fragmentierung durch die Zuweisung von Speichersegmenten passender Größe.
  Nachteile:
  • Kann zu externer Fragmentierung führen, da unterschiedlich große Segmente im physischen Speicher verteilt werden und Lücken entstehen können, die nicht immer für neue Segmente nutzbar sind.
• Overhead und Leistungsfähigkeit:Vorteile:
  • Bietet eine flexiblere Speicherzuweisung und kann Speicher effektiver nutzen, wenn die Anforderungen eines Programms variieren.
  • Erleichtert die Implementierung von Schutzmechanismen, da verschiedene Segmente unterschiedliche Rechte haben können.
  Nachteile:
  • Erfordert komplexere Verwaltungstabellen und Algorithmen, was den Verwaltungsaufwand erhöht.
  • Kann zu einer schlechteren Leistung führen, wenn eine hohe Anzahl von Segmenten häufig neu organisiert werden muss.
Beispiel: Eine große Unternehmensanwendung verwendet Segmentation, um den Speicher in logische Einheiten wie Benutzeroberfläche, Geschäftslogik und Datenbankoperationen zu unterteilen. Dies ermöglicht eine bessere Organisation und einfachere Wartung. Die Flexibilität der Speicherzuweisung reduziert die Gefahr einer internen Fragmentierung, allerdings könnte die Verwaltung und Wartung aufwendiger sein.Zusammenfassung:
• Paging bietet Vorteile bei der Reduzierung der externen Fragmentierung und einer einfachen Implementierung, erfordert jedoch die Verwaltung von Seitentabellen und kann zu interner Fragmentierung führen.
• Segmentation bietet eine logische und flexible Speicherzuweisung und kann interne Fragmentierung vermeiden, hat jedoch den Nachteil einer möglichen externen Fragmentierung und erhöhtem Verwaltungsaufwand.

Aufgabe 4)

Im Rahmen der Vorlesung 'Betriebssysteme und Betriebssystemtechnik' hast Du die Konzepte des virtuellen Speichers und dessen Implementierung kennengelernt. Virtueller Speicher ermöglicht es Programmen, mehr Speicher zu nutzen, als physisch verfügbar ist, indem eine Abstraktionsschicht zwischen physischem Speicher und Anwendungsprozessen geschaffen wird. Zu den Hauptaspekten gehören:

• Trennung von logischen und physischen Adressen.
• Seitentabellen zur Adressübersetzung.
• Paging: der Speicher wird in feste Größen (Seiten) unterteilt.
• Swapping: Austausch von Speicherinhalten zwischen RAM und Festplatte.
• Segmentation: logische Unterteilung des Speichers in Segmente.
• TLB (Translation Lookaside Buffer) zur Beschleunigung der Adressübersetzung.
• Virtuelle Adressen: von der CPU generiert.
• Physische Adressen: beziehen sich auf die Hardware (RAM).
• Demand Paging: Seiten werden bei Bedarf geladen.
• Page Replacement Algorithmen: FIFO, LRU, etc.