Grundlagen der Systemprogrammierung - Exam

Aufgabe 1)

Du bist als Systemadministrator verantwortlich dafür, ein neues Betriebssystem in einem wissenschaftlichen Umfeld zu konfigurieren. Deine Aufgabe besteht darin, die Grundkomponenten des Betriebssystems zu analysieren und die entsprechenden Aspekte zu implementieren. Dabei sollst Du den Kernel konfigurieren, eine geeignete Shell wählen und die wichtigsten Systembibliotheken integrieren.

a)

Beschreibe detailliert die Hauptaufgaben des Kernels in einem Betriebssystem und erläutere deren Wichtigkeit für die Systemstabilität. Gehe dabei speziell auf die Verwaltung des Arbeitsspeichers und die Prozesssteuerung ein. Verwende dabei Beispiele aus der Praxis, um Deine Erläuterungen zu unterstützen.

Lösung:

In der Rolle des Systemadministrators musst Du ein umfassendes Verständnis der Hauptaufgaben des Kernels in einem Betriebssystem haben. Der Kernel ist das Herzstück jedes Betriebssystems und übernimmt eine Vielzahl wesentlicher Funktionen, die sowohl für die Systemstabilität als auch für die Effizienz kritisch sind. Hier sind die Hauptaufgaben des Kernels im Detail beschrieben, wobei speziell auf die Verwaltung des Arbeitsspeichers und die Prozesssteuerung eingegangen wird:

• Verwaltung des Arbeitsspeichers:
  • Der Kernel ist für die Verwaltung des physikalischen und des virtuellen Arbeitsspeichers verantwortlich.
  • Er sorgt dafür, dass jeder Prozess ausreichenden Speicher erhält und dass dieser Speicher effizient genutzt wird.
  • Ein zentrales Konzept hierbei ist das Paging, bei dem der Arbeitsspeicher in kleine, gleichmäßige Einheiten, sogenannte Pages, unterteilt wird. Dies ermöglicht es, den Speicher sowohl flexibel als auch effizient zu verwalten.
  • Ein Beispiel aus der Praxis ist die Nutzung von Swapping, bei dem speicherintensive Anwendungen auf die Festplatte ausgelagert werden, wenn der physische Arbeitsspeicher erschöpft ist. Dies kann die Systemstabilität bewahren und die Leistung verbessern.
• Prozesssteuerung:
  • Der Kernel steuert die Erstellung, Ausführung und Terminierung von Prozessen.
  • Er stellt sicher, dass jeder Prozess ausreichend CPU-Ressourcen erhält und verhindert, dass ein einzelner Prozess das gesamte System monopolisiert.
  • Dies wird durch Scheduler realisiert, die nach bestimmten Algorithmen wie Round-Robin, Priority Scheduling oder Multilevel Queue Scheduling arbeiten.
  • Ein praktisches Beispiel ist die Verwaltung von serverbasierten Anwendungen, bei denen mehrere Prozesse parallel laufen müssen. Der Kernel sorgt hier dafür, dass alle Anfragen effizient und ohne Verzögerungen bearbeitet werden.
• Weitere wichtige Aufgaben des Kernels:
  • Hardware-Abstraktion: Der Kernel agiert als Vermittler zwischen der Hardware des Computers und den Softwareanwendungen. Er stellt Treiber für verschiedene Hardwarekomponenten bereit und ermöglicht so die Kommunikation zwischen Hardware und Software.
  • Dateisystemverwaltung: Der Kernel organisiert die Speicherung, Verwaltung, und den Zugriff auf Dateien. Dies umfasst die Verwaltung von Dateisystemen, wie NTFS, ext4 oder FAT32.
  • Sicherheits- und Berechtigungsmanagement: Der Kernel kontrolliert den Zugriff auf Systemressourcen, um sicherzustellen, dass nur autorisierte Prozesse und Nutzer Zugriff auf bestimmte Daten oder Funktionen erhalten.
  • Inter-Prozess-Kommunikation (IPC): Der Kernel stellt Mechanismen zur Verfügung, durch die Prozesse untereinander kommunizieren und sich synchronisieren können.

Die Hauptaufgaben des Kernels sind eng miteinander verbunden und tragen wesentlich zur Gesamteffizienz und Stabilität des Systems bei. Eine gut konfigurierte Kernel-Umgebung gewährleistet, dass wissenschaftliche Anwendungen in einem stabilen, sicheren und performanten System operieren können.

b)

Als Systemadministrator musst Du zwischen verschiedenen Shells wählen, die dem Benutzer zur Verfügung stehen. Vergleiche eine Kommandozeilen-Shell mit einer grafischen Shell hinsichtlich ihrer Vor- und Nachteile in einem wissenschaftlichen Umfeld. Bewerte anhand von Kriterien wie Benutzerfreundlichkeit, Skripting-Fähigkeiten und Systemressourcenbedarf.

Lösung:

Als Systemadministrator musst Du in einem wissenschaftlichen Umfeld entscheiden, ob Du eine Kommandozeilen-Shell oder eine grafische Shell für die Benutzer zur Verfügung stellst. Beide Optionen haben ihre eigenen Vor- und Nachteile, die je nach den Anforderungen und Erwartungen der Benutzer unterschiedlich gewichtet werden können. Hier sind die Hauptkriterien für den Vergleich:

• Benutzerfreundlichkeit:
  • Kommandozeilen-Shell: Die Kommandozeilen-Shell (z.B. Bash, Zsh) kann zu Beginn relativ unzugänglich wirken, insbesondere für Benutzer, die wenig Erfahrung mit der Arbeit im Terminal haben. Jedoch bietet sie eine hohe Flexibilität und Kontrolle, sobald die Benutzer sich mit den Befehlen und Skripten vertraut gemacht haben.
  • Grafische Shell: Eine grafische Shell (z.B. GNOME, KDE) ist intuitiver und benutzerfreundlicher, insbesondere für neue Benutzer und diejenigen, die weniger technische Erfahrung haben. Sie bietet eine visuelle Schnittstelle, die das Navigieren, Öffnen von Anwendungen und das Verwalten von Dateien erleichtert.
• Skripting-Fähigkeiten:
  • Kommandozeilen-Shell: Die Kommandozeilen-Shell bietet erweiterte Skripting-Fähigkeiten, die in einem wissenschaftlichen Umfeld äußerst nützlich sein können. Benutzer können komplexe Skripte schreiben, um wiederkehrende Aufgaben zu automatisieren, Daten zu verarbeiten und Workflows zu optimieren. Shell-Skripte können leicht in bestehende Workflows integriert und skaliert werden.
  • Grafische Shell: Eine grafische Shell bietet weniger direkte Skripting-Fähigkeiten im Vergleich zur Kommandozeilen-Shell. Zwar können einige Automatisierungsaufgaben durch GUI-basierte Tools und Anwendungen durchgeführt werden, aber diese bieten oft nicht den gleichen Grad an Flexibilität und Kontrolle wie Skripte in der Kommandozeilen-Shell.
• Systemressourcenbedarf:
  • Kommandozeilen-Shell: Eine Kommandozeilen-Shell verbraucht sehr wenige Systemressourcen. Sie ist ideal für Umgebungen, in denen die Rechenleistung und der verfügbare Speicher für wissenschaftliche Berechnungen und Anwendungen maximiert werden sollen.
  • Grafische Shell: Grafische Shells benötigen mehr Systemressourcen wie RAM und CPU-Leistung, um die grafische Benutzeroberfläche und visuelle Effekte darzustellen. In ressourcenintensiven wissenschaftlichen Umgebungen könnte dies ein Nachteil sein, insbesondere wenn die Hardware begrenzt ist.

Basierend auf diesen Kriterien gibt es keine einheitliche Antwort darauf, welche Shell die beste Wahl ist. Vieles hängt von den spezifischen Anforderungen und der Erfahrung der Benutzer im wissenschaftlichen Umfeld ab:

• Für Benutzer, die eine hohe Flexibilität und fortgeschrittene Skripting-Fähigkeiten benötigen, ist die Kommandozeilen-Shell die bessere Wahl.
• Für Benutzer, die mehr Wert auf Benutzerfreundlichkeit legen und weniger technische Erfahrung haben, ist eine grafische Shell vorteilhafter.
• Wenn Systemressourcen knapp sind, bietet die Kommandozeilen-Shell ebenfalls Vorteile aufgrund ihres geringen Ressourcenbedarfs.

Letztendlich könnte eine hybride Lösung, bei der beide Arten von Shells angeboten werden, die beste Wahl in einem wissenschaftlichen Umfeld sein, um sowohl die Anforderungen erfahrener Benutzer als auch die Bedürfnisse weniger erfahrener Benutzer zu erfüllen.

c)

Systembibliotheken sind essenziell für die Teilnehmer des wissenschaftlichen Projekts. Erkläre die Rolle der Systembibliotheken und ihre Bedeutung für die Entwicklung wissenschaftlicher Programme. Zeige auf, wie die Verwendung von Bibliotheken wie libc die Programmierung vereinfacht und warum eine effiziente Implementierung dieser Bibliotheken wichtig ist. Nutze Beispiele, um Deine Ausführungen zu konkretisieren.

Lösung:

Systembibliotheken sind ein entscheidender Bestandteil eines Betriebssystems und spielen eine wesentliche Rolle bei der Entwicklung wissenschaftlicher Programme. Hier sind die wichtigsten Punkte, die die Rolle und Bedeutung der Systembibliotheken verdeutlichen:

• Rolle der Systembibliotheken:
  • Systembibliotheken bieten eine Sammlung vorgefertigter Funktionen und Routinen, die von Programmen genutzt werden können, um häufig benötigte Aufgaben und Operationen durchzuführen.
  • Sie abstrahieren die komplexe Hardware-Interaktion und systemnahe Programmierung, sodass Entwickler sich auf die spezifische Logik ihrer Anwendungen konzentrieren können, ohne sich um die Details des Betriebssystems kümmern zu müssen.
  • Ein Beispiel ist die libc, die Standard-C-Bibliothek, die eine Vielzahl grundlegender Funktionen bereitstellt, wie Datei- und Speicherverwaltung, Zeichenkettenoperationen und mathematische Berechnungen.
• Bedeutung für die Entwicklung wissenschaftlicher Programme:
  • Systembibliotheken ermöglichen eine schnellere und effizientere Entwicklung, da Programmierer auf eine Vielzahl bewährter Funktionen zurückgreifen können, anstatt diese selbst implementieren zu müssen.
  • Sie fördern eine hohe Code-Qualität und Zuverlässigkeit, da diese Bibliotheken in der Regel gründlich getestet und optimiert sind.
  • Beispiel: Die Verwendung von libm, einer mathematischen Erweiterung der libc, ermöglicht es Wissenschaftlern, komplexe mathematische Berechnungen und Funktionen einfach und effizient durchzuführen.
• Vereinfachung der Programmierung durch Bibliotheken wie libc:
  • Standard-Funktionen: libc stellt eine Vielzahl von Standardfunktionen für Aufgaben wie Speicherverwaltung (malloc, free), Dateioperationen (fopen, fread, fwrite), und Zeichenkettenmanipulation (strcpy, strcat) zur Verfügung. Diese Funktionen sparen Zeit und reduzieren den Aufwand für die Entwicklung.
  • Fehlerreduktion: Da die Funktionen der libc gründlich getestet sind, verringert sich das Risiko von Fehlern und Sicherheitslücken in den entwickelten Programmen.
  • Konsistenz und Portabilität: Die Verwendung von Standardbibliotheken wie libc trägt zur Konsistenz des Codes bei und erleichtert die Portabilität der Programme zwischen verschiedenen Plattformen und Betriebssystemen.
• Warum eine effiziente Implementierung dieser Bibliotheken wichtig ist:
  • Ressourcenmanagement: Effiziente Systembibliotheken nutzen die verfügbaren Ressourcen optimal und tragen so zur hohen Leistung und Stabilität des Gesamtsystems bei.
  • Performance: Viele wissenschaftliche Anwendungen sind rechenintensiv und arbeiten mit großen Datenmengen. Eine optimierte Implementierung von Systembibliotheken kann die Laufzeit und die Effizienz dieser Anwendungen erheblich verbessern.
  • Speicherverbrauch: Effiziente Bibliotheken helfen, den Speicherverbrauch niedrig zu halten, was besonders in Umgebungen mit begrenzten Ressourcen von großer Bedeutung ist.

Zusammenfassend lässt sich sagen, dass Systembibliotheken wie libc essenziell für die Entwicklung wissenschaftlicher Programme sind. Sie bieten vorgefertigte, optimierte Funktionen, die die Programmierung vereinfachen, die Zuverlässigkeit des Codes erhöhen und die Performance der Anwendungen verbessern. Die effiziente Implementierung dieser Bibliotheken ist entscheidend, um die Ressourcen des Systems optimal zu nutzen und die Anforderungen der wissenschaftlichen Anwendungen zu erfüllen.

Aufgabe 2)

Du hast ein Betriebssystem, das Multitasking unterstützt, und es werden mehrere Prozesse parallel ausgeführt. Jeder dieser Prozesse hat einen zugehörigen Prozesskontrollblock (PCB), der Informationen wie den Prozesszustand, Programmzähler, CPU-Register und Speicherinformationen enthält. Ein Kontextwechsel tritt immer dann auf, wenn die CPU von der Ausführung eines Prozesses zur Ausführung eines anderen übergeht. Dies ist erforderlich, um Multitasking zu ermöglichen, birgt jedoch den Nachteil, dass zusätzlicher Overhead und Zeit benötigt werden, um den Zustand des aktuellen Prozesses zu speichern und den Zustand des nächsten Prozesses zu laden.

a)

(a) Erkläre detailliert die verschiedenen Komponenten eines Prozesskontrollblocks (PCB). Warum ist jede dieser Komponenten unerlässlich für den Kontextwechsel? Wie beeinflussen diese Komponenten die Leistung und Effizienz des Betriebssystems?

Lösung:

(a) Komponenten eines Prozesskontrollblocks (PCB) und deren Bedeutung:Ein Prozesskontrollblock (PCB) ist ein essenzielles Datenpaket, das alle wichtigen Informationen über einen Prozess im Betriebssystem speichert und verwaltet. Ein PCB besteht aus verschiedenen Komponenten, die jeweils eine spezifische Rolle im Kontextwechsel (Context Switch) und Multitasking spielen. Im Folgenden werden die Hauptkomponenten eines PCBs detailliert erklärt:

• Prozesszustand: Dies gibt den aktuellen Zustand des Prozesses an, z. B. bereit, laufend, wartend oder beendet. Der Zustand ist entscheidend, um zu wissen, welche Aktionen als nächstes für den Prozess durchgeführt werden sollen.
• Programmzähler (Program Counter, PC): Der Programmzähler speichert die Adresse der nächsten Anweisung, die vom Prozess ausgeführt werden soll. Beim Kontextwechsel muss der aktuelle PC zur späteren Wiederaufnahme gespeichert und der PC des neuen Prozesses geladen werden.
• CPU-Register: Dies umfasst alle aktuellen Werte der CPU-Register, die der Prozess verwendet. Diese Register müssen während eines Kontextwechsels gespeichert und wiederhergestellt werden, damit der Prozess korrekt fortgeführt werden kann.
• Speicherinformationen: Beinhaltet Basis- und Begrenzungsadressen, die die Speicherbereiche des Prozesses definieren. Es kann auch Informationen über den verwendeten virtuellen Speicher enthalten.
• Prozessnummer (Process ID, PID): Eine eindeutige Kennung, die dem Prozess zugeordnet ist. Sie wird verwendet, um den Prozess innerhalb des Systems eindeutig zu identifizieren.
• Prozesspriorität: Gibt die Priorität des Prozesses an, was entscheidet, wie schnell und wie oft der Prozess CPU-Zeit erhält im Vergleich zu anderen Prozessen.
• Accountinginformationen: Diese Informationen umfassen die verbrauchte CPU-Zeit, die Anzahl der verwendeten Ressourcen und Statistiken zur Prozessausführung.
• Dateideskriptoren: Dies sind Zeiger auf Dateien, die der Prozess geöffnet hat. Sie erleichtern den Zugriff auf Dateisystemressourcen.
• Weitere Ressourceninformationen: Informationen über andere Ressourcen, die dem Prozess zugewiesen sind, wie z. B. Kommunikationspuffer, Netzwerkverbindungen usw.

Bedeutung dieser Komponenten für den Kontextwechsel:Jede dieser Komponenten ist unerlässlich für den erfolgreichen Kontextwechsel, weil:

• Ohne den exakten Zustand (Prozesszustand, CPU-Register, Programmzähler) kann die CPU nicht korrekt zu einem Prozess zurückkehren, wo sie zuvor aufgehört hat.
• Speicherinformationen sind wichtig, um sicherzustellen, dass der Prozess auf seinen zuständigen Speicherbereich zugreift.
• Prozessnummern und Datei-Deskriptoren helfen dabei, den Prozess zu verfolgen und zu identifizieren sowie den Zugriff auf Dateien und Ressourcen sicherzustellen.

Einfluss auf Leistung und Effizienz:Die Komponenten des PCBs beeinflussen die Leistung und Effizienz des Betriebssystems folgendermaßen:

• Je mehr Informationen im PCB gespeichert werden müssen, desto größer ist der Overhead beim Kontextwechsel.
• Effizientes Speichern und Laden der Register und Speicherinformationen sind entscheidend für einen schnellen Kontextwechsel und somit für eine hohe CPU-Auslastung.
• Ein gut strukturiertes PCB erleichtert das Management von Prozessen, was zu einem effizienten Multitasking führt und die Antwortzeiten verbessert.

b)

(b) Angenommen, das Betriebssystem führt einen Kontextwechsel durch. Leite die Zeitaufwände für den Kontextwechsel wie folgt her: Der Prozesszustand benötigt t1 Zeit zum Speichern und Wiederherstellen, der Programmzähler benötigt t2, die CPU-Register benötigen t3 und die Speicherinformationen benötigen t4. Drücke die Gesamtzeit T als Funktion von t1, t2, t3 und t4 aus. Wie würde sich T ändern, wenn ein wichtigeres Register hinzugefügt wird?

Lösung:

(b) Zeitaufwände für den Kontextwechsel herleiten:Um die Gesamtzeit für einen Kontextwechsel zu berechnen, summieren wir die Zeitaufwände für alle Komponenten, die gespeichert und wiederhergestellt werden müssen. Dies umfasst den Prozesszustand, den Programmzähler, die CPU-Register und die Speicherinformationen.Wir bezeichnen:

• t₁ als die Zeit, die zum Speichern und Wiederherstellen des Prozesszustands benötigt wird,
• t₂ als die Zeit, die zum Speichern und Wiederherstellen des Programmzählers benötigt wird,
• t₃ als die Zeit, die zum Speichern und Wiederherstellen der CPU-Register benötigt wird,
• t₄ als die Zeit, die zum Speichern und Wiederherstellen der Speicherinformationen benötigt wird.

Die Gesamtzeit T für den Kontextwechsel ergibt sich somit als: \begin{equation} T = t_1 + t_2 + t_3 + t_4 \end{equation}Einfluss eines zusätzlichen wichtigen Registers:Angenommen, ein weiteres wichtiges Register wird hinzugefügt. Wenn wir die Zeit für das Speichern und Wiederherstellen dieses Registers als t₅ bezeichnen, ändert sich die Gesamtzeit T wie folgt:

• Die neue Gesamtzeit T' wird dann: \begin{equation} T' = t_1 + t_2 + t_3 + t_4 + t_5 \end{equation}

Das bedeutet, dass die Einführung eines zusätzlichen Registers die Gesamtzeit des Kontextwechsels um die Zeit t₅, die für dieses spezifische Register benötigt wird, erhöht.

c)

(c) Angenommen, dass der durchschnittliche Zeitaufwand für einen Kontextwechsel in Deinem Betriebssystem beträgt 5 ms. Wie würde dies die Gesamtleistung des Systems beeinflussen, wenn die CPU alle 50 ms einen neuen Prozess planen muss? Berechne den prozentualen Overhead, der durch die Kontextwechsel verursacht wird. Zeige alle Deine Berechnungen und schlussfolgere, ob diese Anzahl an Kontextwechseln akzeptabel ist, um eine ausgewogene Leistung zu erreichen.

Lösung:

(c) Auswirkung des Kontextwechsels auf die Gesamtleistung des Systems:Um den prozentualen Overhead durch die Kontextwechsel zu berechnen, verwenden wir die angegebenen Werte:

• Durchschnittlicher Zeitaufwand für einen Kontextwechsel: 5 ms
• CPU plant alle 50 ms einen neuen Prozess

Berechnung des prozentualen Overheads:1. Anzahl der Kontextwechsel pro Sekunde:Eine Sekunde hat 1000 Millisekunden. Wenn die CPU alle 50 ms einen neuen Prozess plant:

• \begin{equation} \frac{1000 \text{ ms}}{50 \text{ ms}} = 20 \text{ Kontextwechsel pro Sekunde} \end{equation}

2. Gesamte Zeit für Kontextwechsel pro Sekunde:Jeder Kontextwechsel dauert 5 ms. Die gesamte Zeit, die für Kontextwechsel in einer Sekunde benötigt wird:

• \begin{equation} 20 \text{ Kontextwechsel} \times 5 \text{ ms/Kontextwechsel} = 100 \text{ ms pro Sekunde} \end{equation}

3. Prozentualer Overhead:Der prozentuale Overhead durch die Kontextwechsel ist der Anteil der gesamten CPU-Zeit, die für Kontextwechsel aufgewendet wird:

• \begin{equation} \frac{100 \text{ ms}}{1000 \text{ ms}} \times 100 = 10 \% \end{equation}

Schlussfolgerung:Der prozentuale Overhead durch die Kontextwechsel beträgt 10%. Dies bedeutet, dass 10% der gesamten CPU-Zeit für Kontextwechsel verwendet werden, während die restlichen 90% für die tatsächliche Ausführung der Prozesse zur Verfügung stehen.Bewertung zur ausgewogenen Leistung:Ein Overhead von 10% kann als akzeptabel betrachtet werden, abhängig von den Anforderungen und Erwartungen des Systems:

• Akzeptabel: Wenn das System in der Lage ist, die erwünschte Leistung und Reaktionszeit zu liefern, kann dieser Overhead als akzeptabel angesehen werden.
• Ungünstig: Wenn jedoch höhere Leistungsanforderungen bestehen oder die Anwendungen empfindlich auf Latenz reagieren, könnte ein Overhead von 10% als zu hoch angesehen werden, und es könnte notwendig sein, die Häufigkeit der Kontextwechsel zu reduzieren oder den Kontextwechsel zu optimieren.

Aufgabe 3)

Stelle Dir vor, Du arbeitest als Systemprogrammierer und musst den CPU-Scheduling-Algorithmus für ein neues Betriebssystem-Design auswählen und implementieren. Berücksichtige dabei verschiedene Programmlast-Szenarien mit unterschiedlichen Anforderungen an Effizienz, Fairness, Durchsatz und Wartezeit. Verwende Deine Kenntnisse über die verschiedenen CPU-Scheduling-Algorithmen und deren Vor- und Nachteile, um eine fundierte Entscheidung zu treffen.

a)

(a) Betrachte einen Batch-Verarbeitungsserver, auf dem viele Berechnungsjobs mit ähnlicher Burst-Zeit ausgeführt werden. Welchen CPU-Scheduling-Algorithmus würdest Du empfehlen und warum? Diskutiere insbesondere die Kriterien Effizienz und Durchsatz. Berechne zusätzlich die durchschnittliche Wartezeit für das First-Come-First-Served (FCFS) Verfahren für die folgenden Job-Burst-Zeiten in Millisekunden: [10, 20, 30, 40, 50].

Lösung:

Wenn Du einen Batch-Verarbeitungsserver betrachtest, auf dem viele Berechnungsjobs mit ähnlicher Burst-Zeit ausgeführt werden, ist der Shortest Job First (SJF) Algorithmus zu empfehlen. Dieser stellt sicher, dass immer der Job mit der kürzesten Verarbeitungszeit zuerst bearbeitet wird. Schauen wir uns die Kriterien Effizienz und Durchsatz im Detail an:

• Effizienz: Der SJF-Algorithmus minimiert die durchschnittliche Wartezeit und ist daher sehr effizient. Da die Jobs ähnliche Burst-Zeiten haben, kommt es zu einer optimalen Auslastung der CPU, da immer die kürzesten Jobs zuerst abgearbeitet werden. Dies reduziert die Zeit, in der die CPU untätig ist.
• Durchsatz: Durch das schnelle Abarbeiten der kürzeren Jobs erhöht sich der Durchsatz, das heißt, die Anzahl der verarbeiteten Jobs pro Zeiteinheit steigt. Dies ist besonders wichtig bei Batch-Verarbeitungsservern, die darauf ausgelegt sind, viele ähnliche Jobs in einer bestimmten Zeitspanne zu erledigen.

Ein einfacher, jedoch weniger effizienter Algorithmus ist das First-Come-First-Served (FCFS) Verfahren. Bei diesem Verfahren werden die Jobs in der Reihenfolge ihres Eintreffens abgearbeitet. Schauen wir uns die Berechnung der durchschnittlichen Wartezeit für die gegebene Job-Burst-Zeiten in Millisekunden an: [10, 20, 30, 40, 50].

Die Wartezeit für jeden Job ist die Summe der Burst-Zeiten aller vorherigen Jobs:

• Wartezeit für den ersten Job: 0 ms
• Wartezeit für den zweiten Job: 10 ms
• Wartezeit für den dritten Job: 10 ms + 20 ms = 30 ms
• Wartezeit für den vierten Job: 10 ms + 20 ms + 30 ms = 60 ms
• Wartezeit für den fünften Job: 10 ms + 20 ms + 30 ms + 40 ms = 100 ms

Daher sind die individuellen Wartezeiten: [0, 10, 30, 60, 100].

Die durchschnittliche Wartezeit wird dann berechnet als:

• \[\frac{0 + 10 + 30 + 60 + 100}{5} = \frac{200}{5} = 40 \text{ ms}\]

Die durchschnittliche Wartezeit für das FCFS-Verfahren beträgt daher 40 Millisekunden.

b)

(b) Angenommen, Du entwirfst ein Echtzeitsystem, das eine schnelle Reaktion auf eingehende Sicherheits-Alerts erfordert. Welchen CPU-Scheduling-Algorithmus würdest Du in diesem Fall wählen und warum? Diskutiere hierbei insbesondere die Kriterien Fairness und Wartezeit. Illustrere dies anhand eines Szenarios, in dem Prozesse mit Zeitintervallen von jeweils 5 Millisekunden nacheinander ausgeführt werden müssen.

Lösung:

Für ein Echtzeitsystem, das eine schnelle Reaktion auf eingehende Sicherheits-Alerts erfordert, wäre der Preemptive Priority Scheduling Algorithmus empfehlenswert. Dies stellt sicher, dass Prozesse mit höherer Priorität vor weniger wichtigen Prozessen ausgeführt werden. Schauen wir uns die Kriterien Fairness und Wartezeit im Detail an:

• Fairness: Im Preemptive Priority Scheduling Algorithmus kann es bei einer schlechten Prioritätszuweisung zu Problemen wie dem „Starvation“-Phänomen kommen, bei dem niedrig priorisierte Prozesse niemals ausgeführt werden. Um dies zu vermeiden, kann man eine dynamische Prioritätsanpassung oder einen Aging-Mechanismus einführen, der die Priorität von Prozessen, die lange gewartet haben, schrittweise erhöht.
• Wartezeit: Da in einem Echtzeitsystem die schnelle Reaktion auf wichtige Ereignisse entscheidend ist, ermöglicht der Preemptive Priority Scheduling Algorithmus eine minimale Wartezeit für sicherheitskritische Prozesse mit hoher Priorität. Prozesse mit niedrigerer Priorität können unter Umständen längere Wartezeiten haben, dies ist aber akzeptabel, wenn die Sicherheit im Vordergrund steht.

Nehmen wir an, wir haben Prozesse mit den folgenden Zeitintervallen (Burst-Zeiten) in Millisekunden und deren zugehörigen Prioritäten:

• Prozess A: 5 ms, Priorität 1 (höchste Priorität)
• Prozess B: 5 ms, Priorität 3
• Prozess C: 5 ms, Priorität 2
• Prozess D: 5 ms, Priorität 4 (niedrigste Priorität)

Illustration des Preemptive Priority Scheduling:

1. Zuerst wird Prozess A (Priorität 1) ausgeführt.
2. Nach Abschluss von Prozess A wird Prozess C (Priorität 2) ausgeführt, da dieser die nächsthöhere Priorität hat.
3. Nach Abschluss von Prozess C folgt Prozess B (Priorität 3).
4. Abschließend wird Prozess D (Priorität 4) ausgeführt.

Zusammenfassend lässt sich sagen, dass der Preemptive Priority Scheduling Algorithmus in einem sicherheitskritischen Echtzeitsystem von Vorteil ist, da er sicherstellt, dass sicherheitsrelevante Prozesse mit hoher Priorität sofort ausgeführt werden, wodurch die Reaktionszeit verbessert wird, auch wenn dies auf Kosten der Fairness für Prozesse mit niedrigerer Priorität geht.

c)

(c) Ein Betriebssystem verwendet prioritätsbasiertes Scheduling mit Aging, um Starvation zu vermeiden. Definiere Starvation und Aging. Simuliere dann ein Szenario mit drei Prozessen A, B und C, die folgende Eigenschaften haben:

• Prozesse: A (Priorität 3), B (Priorität 1), C (Priorität 2)
• Burst-Zeit: A (10 Millisekunden), B (5 Millisekunden), C (8 Millisekunden)

Veranschauliche, wie Aging in diesem Szenario funktioniert und berechne die Endreihenfolge der Ausführung der Prozesse unter Berücksichtigung, dass der Scheduler jede Millisekunde die Priorität eines wartenden Prozesses um 1 erhöht.

Lösung:

Um das Konzept von Starvation und Aging zu erklären:

• Starvation: Starvation tritt auf, wenn ein oder mehrere Prozesse im System dauerhaft auf die Ressourcenzuteilung warten, weil andere Prozesse mit höherer Priorität ständig bevorzugt werden. Dies kann dazu führen, dass Prozesse mit niedriger Priorität niemals eine Chance zur Ausführung erhalten.
• Aging: Aging ist eine Technik, die verwendet wird, um Starvation zu vermeiden. Sie funktioniert, indem sie die Priorität von Prozessen, die lange im Warteschlange warten, schrittweise erhöht. Dies stellt sicher, dass alle Prozesse schließlich ausgeführt werden, wodurch Starvation vermieden wird.

Betrachten wir das folgende Szenario:

• Prozesse: A (Priorität 3), B (Priorität 1), C (Priorität 2)
• Burst-Zeiten: A (10 Millisekunden), B (5 Millisekunden), C (8 Millisekunden)

Der Scheduler erhöht jede Millisekunde die Priorität eines wartenden Prozesses um 1. Schauen wir uns an, wie die Prozesse ausgeführt werden.

Initiale Prioritäten: A=3, B=1, C=2

1. Millisekunde 0-5: Prozess B hat die höchste Priorität und wird daher zuerst für 5 ms ausgeführt.
2. Millisekunde 6: Prozesse A und C haben jetzt Priorität 3, A startet, da die Burst-Zeit von A vor C ist. A wird für 1 ms ausgeführt.
3. Millisekunde 7-12: Nun hat Prozess C die höchste Priorität (4), C wird für 6 ms ausgeführt.
4. Millisekunde 13: Prozess B hat die höchste Priorität (4), B wird für 5 ms ausgeführt.
5. Millisekunde 14-17: Nun hat Prozess A die höchste Priorität und fährt fort, bis erledigen 3 ms übrig (A, 3+7=10).
6. Millisekunde 14-20: A beendet, und Prozess C startet für 6 ms.
7. Millisekunde 20-28: C beendet.

Szenario

Zusammenfassend:

• Prozess B: Wird 1 am Anfang und 1 am Ende ausgeführt
• Prozess C: wird Problem für 6 ms priorisiert
• Zusammenfassung: Das PrioritätsorBereich: [200, 800 1000

Aufgabe 4)

Virtueller Speicher: Paging und SegmentierungIn dieser Aufgabe wirst Du die Prinzipien der Seiten- und Segmentierungstechniken zur Speicherverwaltung in Betriebssystemen anwenden. Das Ziel dieser Techniken ist es, physischen Speicher effizient zu nutzen und gleichzeitig einen gewissen Schutz zu bieten.

• Paging: Der Speicher wird in gleich große Seiten (z. B. 4KB) unterteilt. Hierbei kommen Seitentabellen zum Einsatz, die seitennummerbasierte Zugriffe ermöglichen. Eine virtuelle Adresse setzt sich aus einer Seitennummer und einem Seitenoffset zusammen.
• Segmentierung: Der Speicher wird in variable Segmente unterteilt (z. B. Code kann in einem anderen Segment sein als Daten). Hierbei kommen Segmenttabellen zum Einsatz, die segmentbasierte Zugriffe ermöglichen. Eine virtuelle Adresse setzt sich aus einer Segmentnummer und einem Segmentoffset zusammen.
• Vorteile Paging: Keine externe Fragmentierung, effiziente Speicherverwaltung
• Nachteile Paging: Interne Fragmentierung, Overhead durch Seitentabellen
• Vorteile Segmentierung: Logische Gruppierung von Speicherbereichen, einfache Zugriffsrechteverwaltung
• Nachteile Segmentierung: Externe Fragmentierung möglich, komplexeres Speicher-Management

a)

a) Übersetzung der virtuellen Adresse in eine physische AdresseGegeben sei ein Prozess mit einer Seitengröße von 4KB und folgender Seitentabelle:

• Seite 0: Rahmen 5
• Seite 1: Rahmen 3
• Seite 2: Rahmen 7
• Seite 3: Rahmen 8

Berechne die physische Adresse für die virtuelle Adresse 0x1A27. Gehe dabei davon aus, dass die Seitennummer in den oberen 12 Bits der Adresse enthalten ist und die unteren 12 Bits den Offset darstellen.

Lösung:

Übersetzung der virtuellen Adresse in eine physische Adresse:Gegeben sei ein Prozess mit einer Seitengröße von 4KB und folgender Seitentabelle:

• Seite 0: Rahmen 5
• Seite 1: Rahmen 3
• Seite 2: Rahmen 7
• Seite 3: Rahmen 8

Virtuelle Adresse: 0x1A27Seitengröße: 4KB = 4096 ByteSchritte zur Berechnung der physischen Adresse:

• Konvertiere die virtuelle Adresse 0x1A27 in eine binäre Darstellung: 0x1A27 = 0001 1010 0010 0111 (binär)
• Die oberen 12 Bits (die Seitennummer) extrahieren: 0001 1010 0010 = 001A (Hexadezimal) = 6 (Dezimal)
• Die unteren 12 Bits (den Offset) extrahieren: 0010 0111 (binär) = 0x027 (Hex) = 39 (Dezimal)
• Überprüfe die Seitennummer: 6 Die Seitennummer 6 steht nicht in der Seitentabelle, deshalb ist die virtuelle Adresse ungültig.

Schlussfolgerung: Die virtuelle Adresse 0x1A27 ist keine gültige Adresse, da die Seitennummer 6 keine Entsprechung in der Seitentabelle hat. Eine gültige virtuelle Adresse muss eine Seitennummer haben, die in der Seitentabelle vorhanden ist.

b)

b) SegmentierungsberechnungEin System verwendet Segmentierung und folgt folgender Segmenttabelle für einen Prozess:

• Segment 0: Basisadresse = 0x004000, Länge = 16 KB
• Segment 1: Basisadresse = 0x014000, Länge = 8 KB
• Segment 2: Basisadresse = 0x014000, Länge = 32 KB

Berechne die physische Adresse für die virtuelle Adresse mit Segmentnummer 1 und Segmentoffset 0x1200.

Lösung:

Segmentierungsberechnung:Ein System verwendet Segmentierung und folgt folgender Segmenttabelle für einen Prozess:

• Segment 0: Basisadresse = 0x004000, Länge = 16 KB
• Segment 1: Basisadresse = 0x014000, Länge = 8 KB
• Segment 2: Basisadresse = 0x014000, Länge = 32 KB

Virtuelle Adresse: Segmentnummer 1 und Segmentoffset 0x1200Schritte zur Berechnung der physischen Adresse:

• Bestimme die Basisadresse des Segments 1: Basisadresse = 0x014000
• Prüfe, ob der Offset innerhalb der Segmentlänge liegt: Segmentlänge = 8 KB = 0x2000 Segmentoffset = 0x1200 Da 0x1200 < 0x2000, liegt der Offset innerhalb der Segmentlänge.
• Addiere die Basisadresse und den Segmentoffset, um die physische Adresse zu erhalten: Basisadresse = 0x014000 Segmentoffset = 0x1200 Physische Adresse = Basisadresse + Segmentoffset = 0x014000 + 0x1200 = 0x016200

Schlussfolgerung: Die physische Adresse für die virtuelle Adresse mit Segmentnummer 1 und Segmentoffset 0x1200 ist 0x016200.

c)

c) Speicherverwaltungsmethoden vergleichenDiskutiere die Vor- und Nachteile von Paging und Segmentierung. In welchem Szenario wäre Paging einer segmentierten Speicherverwaltung vorzuziehen und umgekehrt? Begründe deine Antwort ausführlich.

Lösung:

Vergleich der Speicherverwaltungsmethoden: Paging und Segmentierung

• Paging:

Vorteile:

• Keine externe Fragmentierung: Da der Speicher in feste Seiten gleicher Größe unterteilt wird, kann kein ungenutzter Speicherbereich zwischen belegten Bereichen entstehen.
• Effiziente Speicherverwaltung: Einfaches Speichermanagement durch gleich große Seiten verbessert die Handhabung und Zuordnung des Speichers.

Nachteile:

• Interne Fragmentierung: Da die Seiten fixe Größen haben, kann es passieren, dass Details am Ende der Seite ungenutzt bleiben, was zu Speicherplatzverlust führt.
• Overhead durch Seitentabellen: Die Verwaltung und Übersetzung virtueller Adressen in physische Adressen erfordert zusätzliche Datenstrukturen (Seitentabellen), die zusätzlich Speicher und Rechenzeit beanspruchen.

• Segmentierung:

Vorteile:

• Logische Gruppierung von Speicherbereichen: Segmentierung ermöglicht es, zusammenhängende Speicherbereiche logisch zu gruppieren, wie zum Beispiel Code, Daten und Stack, was die Organisation des Speichers verbessert.
• Einfache Zugriffsrechteverwaltung: Da Segmente unabhängige Einheiten sind, lassen sich für jedes Segment individuell Zugriffsrechte definieren, was die Sicherheit erhöht.

Nachteile:

• Externe Fragmentierung möglich: Da Segmente unterschiedlich groß sind, kann es zu nicht nutzbarem Speicher zwischen den Segmenten kommen.
• Komplexeres Speicher-Management: Der variable Charakter der Segmentgrößen erfordert komplexere Algorithmen zur Speicherzuordnung und -verwaltung.

Szenarien der Anwendung:Paging ist vorzuziehen, wenn:

• Es viele Prozesse gibt, die kleinen Speicher brauchen: In Systemen, wo viele kleine Prozesse gleichzeitig laufen, hilft Paging, den Speicher effizient zu nutzen und externe Fragmentierung zu vermeiden.
• Ständige Prozesse: Ständig laufende Systeme wie Betriebssystemkerne profitieren von stabilem und vorhersagbarem Speicherlayout, welches durch Paging gewährleistet wird.

Segmentierung ist vorzuziehen, wenn:

• Die Prozesse große oder gemeinsam genutzte Speicherbereiche haben: Programme, die große Mengen an speicherintensiven Aufgaben bewältigen oder Speicher gemeinsam nutzen müssen, profitieren von der Flexibilität und logischen Speicherorganisation der Segmentierung.
• Sicherheitsanforderungen: Systeme, die hohe Sicherheitsanforderungen haben und spezielle Zugriffsrechte benötigen, sind durch die segmentierten Zugriffsrechte gut bedient.

Fazit:Die Wahl der Speicherverwaltungsmethode hängt von den spezifischen Anforderungen des Systems ab. Paging bietet effiziente und fragmentierungsfreie Speicherverwaltung für viele Prozesse, während Segmentierung eine flexiblere und sicherere Verwaltung für spezialisierte Anwendungen ermöglicht. Ein hybrider Ansatz, der beide Methoden kombiniert, könnte optimale Vorteile beider Systeme bieten und somit die Effizienz und Sicherheit maximieren.

d)

d) Kombinierte SpeicherverwaltungViele moderne Systeme verwenden Kombinationen von Paging und Segmentierung. Erkläre, wie eine kombinierte Paging-Segmentierungstechnik funktionieren könnte, und beschreibe die möglichen Vor- und Nachteile einer solchen Technik. Welche mathematischen Berechnungen wären notwendig, um eine virtuelle Adresse in eine physische Adresse zu übersetzen? Gehe dabei auch auf mögliche Schutzmechanismen ein.

Lösung:

Kombinierte Speicherverwaltung: Paging und SegmentierungViele moderne Systeme nutzen eine Kombination aus Paging und Segmentierung, um die Vorteile beider Techniken zu maximieren und ihre Nachteile zu minimieren. Hier ist wie eine solche kombinierte Technik funktionieren könnte:Funktionsweise:

• Der Speicher ist in Segmente unterteilt, wobei jedes Segment eine bestimmte logische Einheit wie Code, Daten oder Stack repräsentiert.
• Jedes Segment wird weiter in Seiten gleicher Größe unterteilt.
• Die virtuelle Adresse besteht dabei aus drei Teilen: Segmentnummer, Seitennummer und Seitenoffset.

Schritte zur Adressübersetzung:

1. Die Segmentnummer wird verwendet, um in der Segmenttabelle nachzuschlagen. Die Segmenttabelle liefert die Basisadresse und die Länge des Segments.
2. Die Seitennummer innerhalb des Segments wird verwendet, um in der Seitentabelle nachzuschlagen, die die Basisadresse der jeweiligen Seite liefert.
3. Der Seitenoffset wird dann zur Basisadresse der Seite addiert, um die physische Adresse zu erhalten.

Mathematische Berechnungen:

• Virtuelle Adresse: (Segmentnummer, Seitennummer, Seitenoffset)
• Physische Adresse: physische Adresse = (Basisadresse des Segments) + (Basisadresse der Seite) + (Seitenoffset)

Beispiel:Angenommen, wir haben:Segmentnummer: 2Seitennummer: 1Seitenoffset: 0x1200Schritte:

• Segmenttabelle schlägt Segmentnummer 2 nach und liefert Basisadresse 0x014000 und Länge 32 KB
• Seitentabelle innerhalb dieses Segments liefert für Seitennummer 1 die Basisadresse 0x015000
• Die physische Adresse ergibt sich als:physische Adresse = 0x014000 + 0x015000 + 0x1200 = 0x029200

Vorteile:

• Effiziente Speicherverwaltung durch Paging innerhalb von Segmenten
• Logische Organisation und Gruppierung von Speicherbereichen durch Segmentierung
• Feingranulare Zugriffsverwaltung und Schutzmechanismen auf Segment- und Seitenebene

Nachteile:

• Komplexeres Speichermanagement durch die Kombination beider Techniken
• Erhöhter Verwaltungsaufwand und Overhead durch zusätzlich notwendige Tabellenstrukturen
• Erhöhte Komplexität bei der Adressübersetzung, was mehr Rechenzeit in Anspruch nehmen kann

Schutzmechanismen:

• Zugriffsrechte: Für jedes Segment und jede Seite können individuelle Zugriffsrechte wie Lesen, Schreiben oder Ausführen festgelegt werden.
• Speicherschutz: Durch die Trennung von logischen Speicherbereichen kann verhindert werden, dass ein Segment auf Speicherbereiche eines anderen Segments zugreift, was die Systemsicherheit erhöht.
• Interrupts: Bei ungültigen Speicherzugriffen (z. B. Seitenfehler oder Zugriffsverletzungen) können Interrupts ausgelöst werden, die das Betriebssystem benachrichtigen.

Fazit:Eine kombinierte Paging-Segmentierungstechnik nutzt die Vorteile beider Methoden und bietet eine flexible und effiziente Speicherverwaltung. Sie kann jedoch aufgrund der erhöhten Komplexität und des Verwaltungsaufwands anspruchsvoll in der Implementierung sein. Dennoch bietet sie eine robuste Lösung für viele moderne Betriebssysteme, insbesondere in Szenarien mit hohen Anforderungen an Sicherheit und Speicherorganisation.