Betriebssysteme (Vorlesung mit Übungen) - Exam

Aufgabe 1)

Angenommen, Du entwickelst ein Multithreading-Programm, um eine Webanwendung zu unterstützen, bei der mehrere Clients gleichzeitig auf den Server zugreifen können. Das Programm besteht aus mehreren Threads, die Client-Anfragen verarbeiten. Diese Threads kommunizieren miteinander, um Daten und Statusinformationen auszutauschen. Beachte auch, dass Du Speicherzugriffsfehler vermeiden musst, da alle Threads den gleichen Adressraum teilen.

a)

Erkläre, wie Du in Deinem Multithreading-Programm sicherstellst, dass die Threads effizient und ohne Speicherzugriffsfehler arbeiten. Beschreibe mindestens zwei verschiedene Synchronisationsmechanismen, die Du verwenden könntest, und erläutere deren Vor- und Nachteile.

Lösung:

Synchronisation in einem Multithreading-Programm

Um sicherzustellen, dass die Threads in Deinem Multithreading-Programm effizient und ohne Speicherzugriffsfehler arbeiten, ist es wichtig, geeignete Synchronisationsmechanismen zu verwenden. Diese Mechanismen helfen dabei, den Zugriff auf gemeinsam genutzte Ressourcen zu steuern und Konflikte zwischen den Threads zu vermeiden.

Hier sind zwei gängige Synchronisationsmechanismen, die Du verwenden könntest:

• Mutexe (Mutual Exclusion Objects)
  • Vorteile:
    • Einfach zu implementieren und zu verwenden.
    • Erlauben es, kritische Abschnitte zu schützen, sodass nur ein Thread zur selben Zeit Zugriff hat.
  • Nachteile:
    • Kann zu Deadlocks führen, wenn mehrere Mutexe in unterschiedlicher Reihenfolge gesperrt werden.
    • Kann ineffizient sein, wenn viele Threads häufig auf die gleiche Ressource zugreifen müssen, da sie warten müssen, bis der Mutex freigegeben wird.
• Condition Variables (Bedingungsvariablen)
  • Vorteile:
    • Ermöglichen es, Threads zu signalisieren, wenn eine bestimmte Bedingung erfüllt ist, und somit effizient auf Ereignisse zu warten.
    • Können in Kombination mit Mutexe verwendet werden, um sicherzustellen, dass Threads nur dann auf Ressourcen zugreifen, wenn bestimmte Bedingungen erfüllt sind.
  • Nachteile:
    • Können komplexer zu implementieren und zu verwenden sein im Vergleich zu Mutexe.
    • Threads müssen auf die Bedingung warten, was zu Wartezeiten und möglicherweise ineffizienten Ausführungen führen kann, wenn die Bedingung selten erfüllt wird.

b)

Berechne die Gesamtnutzungszeit der CPU und den Overhead für Kontextwechsel, wenn Du anstatt eines Multithreading-Ansatzes eine Multitasking-Architektur verwenden würdest. Nimm an, dass der Kontextwechsel zwischen zwei Prozessen 100 Mikrosekunden und der Kontextwechsel zwischen zwei Threads 5 Mikrosekunden dauert. Angenommen, es werden 10 Threads in der Multithreading-Architektur verwendet und die gleiche Anzahl an Prozessen in der Multitasking-Architektur. Jeder Kontextwechsel erfolgt gleichmäßig innerhalb einer Sekunde.

Lösung:

Berechnung der Gesamtnutzungszeit der CPU und des Overheads für Kontextwechsel

Um die Gesamtnutzungszeit der CPU und den Overhead für Kontextwechsel zu berechnen, wenn eine Multitasking-Architektur anstelle eines Multithreading-Ansatzes verwendet wird, müssen wir die Anzahl der Kontextwechsel und die Dauer dieser Kontextwechsel berücksichtigen.

• Multithreading-Architektur: Die Dauer eines Kontextwechsels zwischen zwei Threads beträgt 5 Mikrosekunden. Angenommen, es gibt 10 Threads, und jeder Thread führt Kontextwechsel gleichmäßig innerhalb einer Sekunde durch.

Berechnungen für Multithreading-Architektur:

• Anzahl der Kontextwechsel pro Sekunde: 10 Threads - 1 = 9 Kontextwechsel
• Gesamtzeit für Kontextwechsel pro Sekunde: 9 Kontextwechsel * 5 µs/Kontextwechsel = 45 µs

• Multitasking-Architektur: Die Dauer eines Kontextwechsels zwischen zwei Prozessen beträgt 100 Mikrosekunden. Angenommen, es gibt 10 Prozesse, und jeder Prozess führt Kontextwechsel gleichmäßig innerhalb einer Sekunde durch.

Berechnungen für Multitasking-Architektur:

• Anzahl der Kontextwechsel pro Sekunde: 10 Prozesse - 1 = 9 Kontextwechsel
• Gesamtzeit für Kontextwechsel pro Sekunde: 9 Kontextwechsel * 100 µs/Kontextwechsel = 900 µs

Vergleich der Gesamtnutzungszeit der CPU und des Overheads:

• Multithreading-Architektur: 45 Mikrosekunden Overhead pro Sekunde
• Multitasking-Architektur: 900 Mikrosekunden Overhead pro Sekunde
• Fazit: Der Overhead für Kontextwechsel ist bei einer Multitasking-Architektur um ein Vielfaches größer als bei einer Multithreading-Architektur. Das bedeutet, dass bei Verwendung einer Multithreading-Architektur die CPU effizienter genutzt wird und weniger Zeit für Verwaltungstätigkeiten (Kontextwechsel) aufgewendet wird.

Aufgabe 2)

Prozessscheduling-AlgorithmenZuteilung von CPU-Zeit an Prozesse. Ziel: Maximierung der Effizienz und Fairness der Prozessausführung.

• FCFS: First Come, First Served. Einfache Implementierung, aber lange Wartezeiten möglich.
• SJF: Shortest Job First. Minimalisiert die durchschnittliche Wartezeit, aber schwer vorhersagbar.
• RR: Round Robin. Jeder Prozess erhält eine feste Zeitspanne (Zeitscheibe).
• Prioritätsbasiert: Zuteilung basierend auf Prozesspriorität. Hohe Priorität erhält mehr CPU-Zeit.
• Multilevel Queue: Kombination mehrerer Algorithmen durch Aufteilung in verschiedene Warteschlangen.
• Multilevel Feedback Queue: Prozess kann in eine andere Warteschlange wechseln, dynamische Anpassung der Priorität.

a)

Angenommen ein Betriebssystem setzt den Round Robin-Algorithmus (RR) mit einer Zeitscheibe von 4ms ein. Es gibt drei Prozesse P1, P2 und P3, mit den folgenden Ankunftszeiten und CPU-Burst-Zeiten:

• P1: Ankunftszeit: 0ms, CPU-Burst: 8ms
• P2: Ankunftszeit: 1ms, CPU-Burst: 4ms
• P3: Ankunftszeit: 2ms, CPU-Burst: 9ms

Führe eine Zeitscheibensimulation für diese Prozesse durch und berechne die durchschnittliche Wartezeit sowie die durchschnittliche Turnaround-Zeit. Zeige die Berechnungen und Erklärungen detailliert.

Lösung:

Um den Round Robin-Algorithmus mit einer Zeitscheibe von 4ms zu simulieren, werden die Prozesse in der Reihenfolge ihrer Ankunftszeiten eingereiht und dann abwechselnd für maximal 4ms ausgeführt, bis sie abgeschlossen sind. Hier ist die detaillierte Simulation:

• P1: Ankunftszeit: 0ms, CPU-Burst: 8ms
• P2: Ankunftszeit: 1ms, CPU-Burst: 4ms
• P3: Ankunftszeit: 2ms, CPU-Burst: 9ms

Zeitscheiben-Simulation:

• 0-4ms: P1 (4ms verbraucht, 4ms übrig)
• 4-8ms: P2 (4ms verbraucht, 0ms übrig)
• 8-12ms: P3 (4ms verbraucht, 5ms übrig)
• 12-16ms: P1 (restliche 4ms verbraucht, 0ms übrig)
• 16-20ms: P3 (restliche 5ms verbraucht, 0ms übrig)

Berechnung der Wartezeiten:

• P1: P1 wartete auf Zeitintervalle: Von 4ms bis 12ms (während P2 und P3 an der Reihe waren) Gesamtwartezeit für P1 = 12ms - 0ms (Ankunftszeit) - 8ms (CPU-Burst) = 4ms
• P2: P2 wartete nicht (direkt nach Ankunft bearbeitet): Gesamtwartezeit für P2 = 4ms - 1ms (Ankunftszeit) - 4ms (CPU-Burst) = -1ms (wird auf 0ms angepasst)
• P3: P3 wartete auf Zeitintervalle: Von 8ms bis 16ms (während P1 und P2 an der Reihe waren) Gesamtwartezeit für P3 = 16ms - 2ms (Ankunftszeit) - 9ms (CPU-Burst) = 5ms

Berechnung der Turnaround-Zeiten:

• P1: 0ms (Ankunftszeit) + 8ms (CPU-Burst-Zeit) + 4ms (Wartezeit) = 12ms
• P2: 1ms (Ankunftszeit) + 4ms (CPU-Burst-Zeit) + 0ms (angepasste Wartezeit) = 5ms
• P3: 2ms (Ankunftszeit) + 9ms (CPU-Burst-Zeit) + 5ms (Wartezeit) = 16ms

Durchschnittliche Wartezeit berechnen:

• (4ms + 0ms + 5ms) / 3 = 3ms

Durchschnittliche Turnaround-Zeit berechnen:

• (12ms + 5ms + 16ms) / 3 = 11ms

Zusammenfassung:

• Die durchschnittliche Wartezeit beträgt: 3ms.
• Die durchschnittliche Turnaround-Zeit beträgt: 11ms.

b)

Ein Betriebssystem nutzt den Shortest Job First (SJF) Algorithmus für das Prozessscheduling. Die Ankunftszeiten und CPU-Burst-Zeiten der Prozesse sind wie folgt:

• P1: Ankunftszeit: 0ms, CPU-Burst: 8ms
• P2: Ankunftszeit: 1ms, CPU-Burst: 4ms
• P3: Ankunftszeit: 2ms, CPU-Burst: 9ms

Simuliere die Ausführung der Prozesse und berechne die durchschnittliche Wartezeit. Zeige alle Zwischenschritte und Erklärungen detailliert. Diskutiere zudem die Konsequenzen, falls ein neuer Prozess P4 mit einer Ankunftszeit von 3ms und einer CPU-Burst-Zeit von 3ms hinzukommt. Wie ändert sich die durchschnittliche Wartezeit?

Lösung:

Um den Shortest Job First (SJF) Algorithmus zu simulieren, müssen wir die Prozesse in der Reihenfolge ihrer Ankunftszeiten betrachten und dann der Reihe nach den Prozess mit der kürzesten CPU-Burst-Zeit auswählen:

• P1: Ankunftszeit: 0ms, CPU-Burst: 8ms
• P2: Ankunftszeit: 1ms, CPU-Burst: 4ms
• P3: Ankunftszeit: 2ms, CPU-Burst: 9ms

Da SJF nicht-präemptiv ist, wird ein laufender Prozess nicht unterbrochen. Der Prozess mit der kürzesten verbleibenden Zeit wird zuerst ausgewählt.

Simulation der Prozesse:

• 0-8ms: P1 (da P1 bereits läuft und es keine kürzeren Prozesse gibt)
• P2 (Ankunftszeit: 1ms, CPU-Burst: 4ms)
• P3 (Ankunftszeit: 2ms, CPU-Burst: 9ms)

Nachdem P1 beendet ist, sind P2 und P3 angekommen. P2 wird gewählt, weil es eine kürzere Burst-Zeit hat.

• 8-12ms: P2
• 12-21ms: P3

Berechnung der Wartezeiten:

• P1: Muss nicht warten (es startet sofort): Wartezeit für P1 = 0ms
• P2: P2 wartet von 8ms bis 8ms: Wartezeit für P2 = 8ms - 1ms (Ankunftszeit) = 7ms
• P3: P3 wartet von 12ms bis 12ms: Wartezeit für P3 = 12ms - 2ms (Ankunftszeit) = 10ms

Durchschnittliche Wartezeit berechnen:

• (0ms + 7ms + 10ms) / 3 = 5.67ms

Zusammenfassung:

• Die durchschnittliche Wartezeit beträgt: 5.67ms.

Konsequenzen eines neuen Prozesses P4:

• P4: Ankunftszeit: 3ms, CPU-Burst: 3ms

Die neue Reihenfolge unter SJF wird wie folgt sein:

• 0-3ms: P1 (Beginn)
• 3-6ms: P4 (kürzerer Prozess kommt hinzu)
• 6-14ms: P1 (Rest seines Bursts)
• 14-18ms: P2
• 18-27ms: P3

Neuberechnung der Wartezeiten:

• P1: P1 startet sofort, wartet bis 6ms: Wartezeit = 6ms (Ende von P4) + (8ms (seine eigene Laufzeit) - 8ms (von 6ms)- 0ms (Standby)) = 6ms
• P2: P2 wartet von 3ms bis 14ms: Wartezeit = 14ms - 1ms (Ankunftszeit) = 13ms
• P3: P3 wartet von 14ms bis 18ms: Wartezeit = 18ms - 2ms (Ankunftszeit) = 16ms
• P4: P4 muss nicht warten: Wartezeit = 0ms

Neue durchschnittliche Wartezeit berechnen:

• (3ms + 0ms + 6ms + 16ms) / 4 = 8.33ms

Zusammenfassung:

• Die neue durchschnittliche Wartezeit beträgt: 8.33ms.

Aufgabe 3)

Ein Prozessor-Architektur unterstützt 32-Bit virtuelle Adressen und verwendet ein Paging-Schema mit einer Seitengröße von 4 KB. Es gibt einen physikalischen Speicher von 16 GB. Um die Übertragung von virtuellen zu physischen Adressen zu beschleunigen, verwendet das System einen Translation Lookaside Buffer (TLB) mit einer Kapazität von 128 Einträgen.

a)

Berechne die Anzahl der Einträge in der Page Table für einen Prozess, wenn der gesamte virtuelle Adressraum verwendet wird.

• Die Seitengröße beträgt 4 KB.
• Eine Adresse besteht aus einem seitenspezifischen Offset sowie einem Index in der Page Table.

Lösung:

Lösung des Unterexerzitums

• Die architektonische Spezifikation gibt virtuelle Adressen mit 32 Bit vor.
• Die Seitengröße beträgt 4 KB (Kilobyte), was 2¹² Byte ist.

Schritt-für-Schritt-Ansatz zur Berechnung der Anzahl der Einträge in der Page Table

1. Bestimme die Gesamtanzahl der virtuellen Adressen.

• Da wir 32-Bit-Adressen haben, gibt es insgesamt 2³² verschiedene virtuelle Adressen.

Bestimme die Anzahl der virtuellen Seiten.

• Die Seitengröße beträgt 4 KB. Dies entspricht 2¹² Byte, also werden die unteren 12 Bits einer Adresse als Offset innerhalb der Seite verwendet.
• Die oberen 32-12 = 20 Bits der virtuellen Adresse dienen als Index in der Page Table.
• Daher gibt es 2²⁰ Einträge in der Page Table (2³² virtuelle Adressen / 2¹² Adressen pro Seite).

Berechnungen:

• Virtueller Adressraum: 2³² Adressen
• Seitengröße: 4 KB = 2¹² Bytes
• Anzahl der virtuellen Seiten: 2³² / 2¹² = 2²⁰

• Daher hat die Page Table 2²⁰ = 1.048.576 Einträge.

b)

Gegeben sei eine virtuelle Adresse von 0x41A2B3C8. Unter der Annahme, dass der erste Page Table Level 1024 Einträge hat, berechne die physischen Page-Table-Indizes auf den mehrstufigen Page-Table-Schema. Gehe davon aus, dass der virtuelle Adressraum in zwei Ebenen unterteilt ist und jede Page Table 4-Byte-Einträge enthält.

• Spezifiziere die virtuellen Adressbits, die für die Indexierung auf jeder Stufe verwendet werden.
• Bestimme die Offsets für jede Stufe und den verbleibenden Offset innerhalb der Page.

Lösung:

Lösung des Unterexerzitums

• Eine 32-Bit-virtuelle Adresse ist gegeben, zum Beispiel 0x41A2B3C8.

Schritt-für-Schritt-Ansatz zur Berechnung der physischen Page-Table-Indizes auf zwei Ebenen

1. Analysiere die zweistufige Page Table Struktur.

• Da jede Page Table 1024 Einträge enthält, entspricht das 2¹⁰ Einträgen pro Level.
• Jeder Eintrag in der Page Table hat eine Größe von 4 Byte. Eine Seite ist 4KB groß (2¹² Byte), daher braucht man 12 Bits für den Seiten-Offset, was uns den Seiteninhalt gibt.

Die virtuelle 32-Bit-Adresse (0x41A2B3C8) wird in Segmente aufgeteilt:

• Die ersten 10 Bits werden für den Index des ersten Page Table Levels (L1) verwendet.
• Die nächsten 10 Bits werden für den Index des zweiten Page Table Levels (L2) verwendet.
• Die letzten 12 Bits sind der Offset innerhalb der Page.

• Um dies zu verdeutlichen, konvertieren wir die gegebene virtuelle Adresse (0x41A2B3C8) in Binärformat:

0x41A2B3C8 = 0100 0001 1010 0010 1011 0011 1100 1000

• Teile die Binärzahl in die entsprechenden Segmente:

1. Erste 10 Bits für L1 Index: 0100000110
2. Nächste 10 Bits für L2 Index: 1000101011
3. Letzte 12 Bits für den Seiten-Offset: 001111001000

• Um die indizes in Dezimalform zu erhalten, konvertieren wir die Binärsegmente in Dezimalzahlen:

1. L1 Index: 0100000110 Binär = 262 Dezimal
2. L2 Index: 1000101011 Binär = 555 Dezimal
3. Seiten-Offset: 001111001000 Binär = 968 Dezimal

Zusammenfassung der physischen Page-Table-Indizes:

• L1 Index: 262
• L2 Index: 555
• Seiten-Offset: 968

Daher ergibt die virtuelle Adresse 0x41A2B3C8 die folgenden physischen Indizes im zweistufigen Page Table-Schema:

• Index des ersten Page Table Levels (L1): 262
• Index des zweiten Page Table Levels (L2): 555
• Offset innerhalb der Page: 968

Aufgabe 4)

Du bist als Betriebssystemdesigner beauftragt, ein effizientes Speicherverwaltungssystem zu implementieren, das sowohl Paging als auch Segmentierung verwendet. Deine Aufgabe ist es, eine Reihe von verschiedenen Aspekten dieses Systems zu analysieren und zu berechnen.

a)

(a) PagingEin Prozessor verwendet Paging zur Speicherverwaltung. Gegeben ist eine Seitengröße von 4KB und insgesamt 64MB physikalischer Speicher. Berechne die Anzahl der Einträge in der Seitentabelle. Zeige dafür alle notwendigen Schritte und Formeln auf.

Lösung:

(a) Paging

Um die Anzahl der Einträge in der Seitentabelle zu berechnen, müssen wir den gesamten physikalischen Speicher in Pages (Seiten) unterteilen. Hier sind die Schritte und Formeln:

• Wir kennen die Seitengröße: 4KB. Umgerechnet in Bytes sind das:

1 KB = 1024 Bytes

4 KB = 4 \times 1024 = 4096 Bytes

• Der gesamte physikalische Speicher ist 64MB. Umgerechnet in Bytes sind das:

1 MB = 1024 KB

64 MB = 64 \times 1024 KB = 64 \times 1024 \times 1024 Bytes

• Nun berechnen wir die Anzahl der Pages, indem wir den gesamten physikalischen Speicher durch die Seitengröße teilen:

\frac{{64 \times 1024 \times 1024 \text{{ Bytes}}}}{{4096 \text{{ Bytes}}}} = \frac{{67108864}}{{4096}} = 16384 \text{{ Pages}}

• Da jede Page einen Eintrag in der Seitentabelle benötigt, ist die Anzahl der Einträge in der Seitentabelle ebenfalls 16384.

Die Anzahl der Einträge in der Seitentabelle beträgt also 16384.

b)

(b) SegmentationEin Programm verwendet Segmentierung und hat einen Segmenttabelle-Eintrag mit Basisadresse 0x2000 und Segmentlänge 8KB. Wenn der Offset 0x1A3 ist, berechne die physikalische Adresse. Zeige den Rechenweg und die verwendete Formel.

Lösung:

(b) Segmentierung

Um die physikalische Adresse zu berechnen, wenn ein Programm Segmentierung verwendet, müssen wir die Basisadresse und den Offset addieren. Hier sind die Schritte und die Formel:

• Gegeben: Basisadresse: 0x2000 Segmentlänge: 8KB Offset: 0x1A3
• Die Berechnung der physikalischen Adresse erfolgt durch Addition der Basisadresse und des Offsets:

Formel: Physikalische Adresse = Basisadresse + Offset

Setzen wir die Werte ein:

Basisadresse: 0x2000 Offset: 0x1A3

Rechnung:

0x2000 + 0x1A3

Um dies zu berechnen, konvertieren wir die Hexadezimalzahlen in Dezimalzahlen:

Basisadresse (0x2000) ist im Dezimalsystem 8192Offset (0x1A3) ist im Dezimalsystem 419

Berechnung im Dezimalsystem:

8192 + 419 = 8611

Konvertieren wir das Ergebnis zurück ins Hexadezimalsystem:

8611 im Dezimalsystem ist 0x21A3 im Hexadezimalsystem

• Die physikalische Adresse lautet daher 0x21A3.

c)

(c) Kombination von Paging und SegmentierungAngenommen, ein System verwendet eine Kombination aus Paging und Segmentierung. Ein Segment enthält 4 Seiten, jede Seite ist 4KB groß. Ein virtuelle Adresse besteht aus folgenden Bestandteilen: Segmentnummer (6 Bit), Seitennummer (10 Bit), und Seitenoffset (12 Bit). Berechne die physikalische Adresse für die virtuelle Adresse 0x12345678 wenn der Basisadresse des Segments 0x4000 ist (gespeichert in der Segmenttabelle) und die physikalische Adresse der 2. Seite der Seitentabelle 0x8000 ist. Zeige alle Rechenschritte und die verwendete Formel.

Lösung:

(c) Kombination von Paging und Segmentierung

Um die physikalische Adresse in einem System zu berechnen, das sowohl Paging als auch Segmentierung verwendet, müssen wir die verschiedenen Komponenten der virtuellen Adresse zerlegen und die entsprechenden Berechnungen durchführen. Hier sind die Schritte:

• Gegebene Informationen:Segment enthält 4 Seiten, jede Seite ist 4KB groß.Virtuelle Adresse: 0x12345678Basisadresse des Segments: 0x4000Physikalische Adresse der 2. Seite der Seitentabelle: 0x8000
• Die virtuelle Adresse besteht aus:
  • Segmentnummer (6 Bit)
  • Seitennummer (10 Bit)
  • Seitenoffset (12 Bit)

Schrittweiser Rechenweg:

• 1. Zerlege die virtuelle Adresse in ihre Bestandteile:Virtuelle Adresse: 0x123456780x12345678 in Binär: 0001 0010 0011 0100 0101 0110 0111 1000
• 2. Teile die Binäradresse in Segmentnummer, Seitennummer und Seitenoffset:
  • Segmentnummer (erste 6 Bit): 000100 = 0x04
  • Seitennummer (nächste 10 Bit): 1000110100 = 0x234
  • Seitenoffset (letzte 12 Bit): 0101 0110 0111 = 0x567
• 3. Ermittle die Basisadresse des Segments: 0x4000 (aus der Segmenttabelle)
• 4. Ermittle die physikalische Adresse der angegebenen Seite:Seitennummer = 2.Physikalische Adresse der 2. Seite in der Seitentabelle: 0x8000
• 5. Berechne die physikalische Adresse:Formel: Physikalische Adresse = Basisadresse der Seite + Seitenoffset
• 6. Setze die Werte ein:
  • Basisadresse der Seite: 0x8000
  • Seitenoffset: 0x567
• 7. Berechnung der physikalischen Adresse:Physikalische Adresse = 0x8000 + 0x567 = 0x8567

Die endgültige physikalische Adresse lautet daher 0x8567.