Systemprogrammierung - Exam

Aufgabe 1)

Erstellung und Terminierung von Prozessen: Prozesserstellung und -beendigung in Betriebssystemen werden hauptsächlich durch die folgenden Systemaufrufe realisiert:

• Erstellung: fork() erzeugt einen Kindprozess.
• Initialisierung: exec() lädt ein neues Programm in den Adressraum des Prozesses.
• Beendigung: exit() beendet den Prozess.
• Prozesszustände: neu, bereit, laufend, wartend, beendet.
• Warteschlange und Planung: Der Scheduler und Kontextwechselprozesse.
• Wichtige Systemaufrufe: fork(), exec(), wait(), exit().
• Zustandstransitionen werden durch den Scheduler bestimmt.

a)

a) Implementiere ein kurzes Programm in C, das einen Elternprozess erstellt, der einen Kindprozess erzeugt und auf dessen Beendigung wartet. Verwende die Systemaufrufe fork(), exec() und wait(). Der Kindprozess soll ein externes Programm ausführen (beispielsweise /bin/ls) und der Elternprozess soll eine geeignete Nachricht ausgeben, sobald der Kindprozess beendet ist.

 #include <stdio.h>  #include <sys/types.h>  #include <sys/wait.h>  #include <unistd.h>   int main() {     pid_t pid;      pid = fork();     if (pid < 0) {       perror('Fehler beim Forken');       return 1;     } else if (pid == 0) {       execl('/bin/ls', 'ls', (char *) NULL);       perror('Fehler beim Exec');       return 1;     } else {       int status;       wait(&status);       if (WIFEXITED(status)) {         printf('Kindprozess beendet mit Status %d', WEXITSTATUS(status));       } else {         printf('Kindprozess wurde abnormal beendet');       }     }     return 0;  } 

Lösung:

Erstellung und Terminierung von Prozessen: Prozesserstellung und -beendigung in Betriebssystemen werden hauptsächlich durch die folgenden Systemaufrufe realisiert:

• Erstellung: fork() erzeugt einen Kindprozess.
• Initialisierung: exec() lädt ein neues Programm in den Adressraum des Prozesses.
• Beendigung: exit() beendet den Prozess.
• Prozesszustände: neu, bereit, laufend, wartend, beendet.
• Warteschlange und Planung: Der Scheduler und Kontextwechselprozesse.
• Wichtige Systemaufrufe: fork(), exec(), wait(), exit().
• Zustandstransitionen werden durch den Scheduler bestimmt.

Löse die folgende Teilaufgabe:

a) Implementiere ein kurzes Programm in C, das einen Elternprozess erstellt, der einen Kindprozess erzeugt und auf dessen Beendigung wartet. Verwende die Systemaufrufe fork(), exec() und wait(). Der Kindprozess soll ein externes Programm ausführen (beispielsweise /bin/ls) und der Elternprozess soll eine geeignete Nachricht ausgeben, sobald der Kindprozess beendet ist.

 #include <stdio.h>  #include <sys/types.h>  #include <sys/wait.h>  #include <unistd.h>   int main() {     pid_t pid;      pid = fork();     if (pid < 0) {       perror('Fehler beim Forken');       return 1;     } else if (pid == 0) {       execl('/bin/ls', 'ls', (char *) NULL);       perror('Fehler beim Exec');       return 1;     } else {       int status;       wait(&status);       if (WIFEXITED(status)) {         printf('Kindprozess beendet mit Status %d', WEXITSTATUS(status));       } else {         printf('Kindprozess wurde abnormal beendet');       }     }     return 0;  } 

b)

b) Erkläre die verschiedenen Prozesszustände (neu, bereit, laufend, wartend, beendet) und ihre möglichen Zustandsübergänge. Wie werden diese Zustandsübergänge durch den Scheduler gesteuert und welche Rolle spielen dabei die Systemaufrufe fork(), exec(), wait() und exit()? Erstelle eine Zustandsübergangstabelle, die jeden Zustand und die möglichen Übergänge beschreibt.

Lösung:

Erstellung und Terminierung von Prozessen: Prozesserstellung und -beendigung in Betriebssystemen werden hauptsächlich durch die folgenden Systemaufrufe realisiert:

• Erstellung: fork() erzeugt einen Kindprozess.
• Initialisierung: exec() lädt ein neues Programm in den Adressraum des Prozesses.
• Beendigung: exit() beendet den Prozess.
• Prozesszustände: neu, bereit, laufend, wartend, beendet.
• Warteschlange und Planung: Der Scheduler und Kontextwechselprozesse.
• Wichtige Systemaufrufe: fork(), exec(), wait(), exit().
• Zustandstransitionen werden durch den Scheduler bestimmt.

Löse die folgende Teilaufgabe:

b) Erkläre die verschiedenen Prozesszustände (neu, bereit, laufend, wartend, beendet) und ihre möglichen Zustandsübergänge. Wie werden diese Zustandsübergänge durch den Scheduler gesteuert und welche Rolle spielen dabei die Systemaufrufe fork(), exec(), wait() und exit()? Erstelle eine Zustandsübergangstabelle, die jeden Zustand und die möglichen Übergänge beschreibt.

Die verschiedenen Prozesszustände sind:

• Neu: Der Prozess wurde gerade erstellt, aber noch nicht zur Ausführung bereitgestellt. Dies geschieht durch den fork()-Aufruf.
• Bereit: Der Prozess ist bereit zur Ausführung und wartet darauf, vom Scheduler ausgewählt zu werden. Dies erfolgt nach dem ersten Schritt von fork(), wenn der Kindprozess vom Scheduler in die Bereit-Warteschlange gestellt wird.
• Laufend: Der Prozess wird aktuell von der CPU ausgeführt. Dies geschieht, wenn der Scheduler den Prozess auswählt und ihm die CPU zuteilt.
• Wartend: Der Prozess wartet auf ein Ereignis (z.B. I/O-Betrieb). Dies kann durch einen wait()-Aufruf oder durch Wartung auf ein externes Ereignis passieren.
• Beendet: Der Prozess hat seine Ausführung abgeschlossen und gibt die CPU sowie andere Ressourcen frei. Dies geschieht durch einen exit()-Aufruf oder wenn der Prozess normal endet.

Die Zustandsübergänge und die Rolle der Systemaufrufe können wie folgt beschrieben werden:

Zustand	Übergang nach	Aktion/Systemaufruf
Neu	Bereit	Der Prozess wurde durch fork() erstellt und ist zur Ausführung bereit.
Bereit	Laufend	Der Scheduler wählt den Prozess zur Ausführung aus und weist ihm die CPU zu.
Laufend	Wartend	Der Prozess führt einen I/O-Operation aus oder führt einen wait()-Aufruf aus.
Laufend	Bereit	Der Scheduler führt einen Kontextwechsel durch, um einem anderen Prozess die CPU zuzuweisen.
Laufend	Beendet	Der Prozess führt einen exit()-Aufruf aus oder endet normal.
Wartend	Bereit	Das Ereignis, auf das der Prozess wartet (z.B. I/O), tritt ein und der Prozess ist wieder bereit zur Ausführung.

Der Scheduler spielt eine zentrale Rolle, indem er entscheidet, welcher Prozess von 'Bereit' nach 'Laufend' wechselt oder wann ein laufender Prozess unterbrochen wird und in den Zustand 'Bereit' zurückkehrt.

Aufgabe 2)

Ein Systemarchitekt designiert ein Computerprogramm für ein Bankensystem, welches aus mehreren Prozessen besteht. Der Hauptprozess ist verantwortlich für die Verwaltung der Datenbanktransaktionen, während sekundäre Prozesse sich um spezifische Aufgaben wie Kundenanfragen und Buchkartenverwaltung kümmern. Der Hauptprozess muss Daten empfangen und senden können sowie sicherstellen, dass alle Prozesse ordnungsgemäß synchronisiert werden, um Datenkonsistenz zu gewährleisten. Beachte, dass auf dem System Unix/Linux läuft.

a)

Beschreibe drei verschiedene Mechanismen der Interprozesskommunikation (IPC), die in diesem Bankensystem verwendet werden könnten, um Nachrichten zwischen dem Hauptprozess und den sekundären Prozessen effizient zu senden und zu empfangen. Für jeden Mechanismus diskutiere dessen Vorteile und potenzielle Nachteile in diesem spezifischen Anwendungsfall.

Lösung:

Mechanismen der Interprozesskommunikation (IPC) für das Bankensystem:

• Pipes (Rohrleitungen):
  • Vorteile:
    • Pipes sind einfach zu implementieren und verwenden.
    • Sie bieten eine unidirektionale Kommunikation, die für einfache Datenübertragungen geeignet ist.
    • Nahtlose Integration in Unix/Linux-Systeme, da Pipes im Betriebssystemkern unterstützt werden.
  • Nachteile:
    • Pipes sind nur für die Kommunikation zwischen verwandten Prozessen (z.B. Eltern-Kind-Prozess) geeignet.
    • Der Unidirektionalität wegen können sie komplexer zu verwenden sein, wenn eine bidirektionale Kommunikation erforderlich ist.
    • Begrenzte Puffergröße kann dazu führen, dass der Schreibprozess blockiert, wenn der Puffer voll ist.
• Message Queues (Nachrichtenwarteschlangen):
  • Vorteile:
    • Message Queues ermöglichen die bidirektionale Kommunikation zwischen beliebigen Prozessen.
    • Nachrichten können priorisiert werden, was die dringende Verarbeitung wichtiger Aufgaben ermöglicht.
    • Prozesse müssen sich nicht direkt kennen, um über Message Queues zu kommunizieren.
  • Nachteile:
    • Die Verwaltung von Message Queues kann komplexer sein und erfordert mehr Systemressourcen.
    • Es besteht das Risiko von Nachrichtenverlust oder Verzögerungen unter hoher Last.
    • Erhöhte Komplexität bei der Sicherstellung der Datenkonsistenz und Reihenfolge der Nachrichten.
• Shared Memory (Gemeinsamer Speicher):
  • Vorteile:
    • Shared Memory bietet die schnellste Form der IPC, da Daten direkt im Speicher ausgetauscht werden.
    • Hohe Effizienz bei der Übertragung großer Datenmengen.
    • Ermöglicht die Kommunikation zwischen mehreren Prozessen in beide Richtungen.
  • Nachteile:
    • Der Zugriff auf den gemeinsamen Speicher muss sorgfältig synchronisiert werden, um Datenkonsistenz zu gewährleisten (z.B. mittels Semaphoren oder Mutexen).
    • Komplexere Programmierung im Vergleich zu anderen IPC-Mechanismen.
    • Das Risiko, dass fehlerhafte Prozesse den Speicherbereich anderer Prozesse überschreiben, was zu schwerwiegenden Fehlern führen kann.

Jeder dieser Mechanismen bietet spezifische Vorteile und Nachteile, und die Auswahl des geeigneten Mechanismus hängt von den spezifischen Anforderungen des Bankensystems ab, einschließlich der erforderlichen Leistung, Komplexität und Datenkonsistenz. Beachte, dass für eine optimale Leistung und Zuverlässigkeit möglicherweise eine Kombination dieser IPC-Mechanismen in Betracht gezogen werden sollte.

b)

Ein wesentlicher Bestandteil dieses Bankensystems ist die Synchronisation von Prozessen, um Race Conditions zu vermeiden. Erkläre detailliert, wie Semaphoren verwendet werden könnten, um zwei Szenarien zu behandeln: 1) Synchronisation bei gemeinsamen Schreibzugriffen auf eine Datei; 2) Sicherstellung, dass die Bearbeitung einer Kundenanfrage vollständig abgeschlossen wird, bevor eine neue Anfrage gestartet wird. Formuliere zu jedem Szenario die benötigten Semaphore-Operationen. Nutze dazu möglichst detaillierte Pseudocode-Snippets und mathematische Formeln, wo es sinnvoll ist.

Lösung:

Verwendung von Semaphoren zur Prozesssynchronisation im Bankensystem:Im Kontext des Bankensystems können Semaphoren effektiv eingesetzt werden, um Race Conditions zu verhindern und die Synchronisation zwischen Prozessen sicherzustellen. Hier sind zwei Szenarien detailliert beschrieben:

• Szenario 1: Synchronisation bei gemeinsamen Schreibzugriffen auf eine Datei

Um sicherzustellen, dass mehrere Prozesse nicht gleichzeitig auf dieselbe Datei schreiben und somit Datenkorruption verhindern, kann ein binärer Semaphor (auch Mutex genannt) verwendet werden.Pseudocode:

semaphore mutex = 1 // Binärer Semaphor, initial auf 1 gesetzt// Prozess 1wait(mutex)   // kritischer Abschnitt für Dateizugriff   write_to_file()signal(mutex)// Prozess 2wait(mutex)   // kritischer Abschnitt für Dateizugriff   write_to_file()signal(mutex)

Erklärung:1. wait(mutex) (auch bekannt als P operation) dekrementiert den Semaphor. Wenn der Semaphor bereits 0 ist, blockiert der Prozess, bis er wieder auf 1 gesetzt wird.2. Der kritische Abschnitt beinhaltet den Schreibzugriff auf die Datei. Nur ein Prozess kann den kritischen Abschnitt betreten, wenn der Semaphor auf 1 gesetzt ist.3. signal(mutex) (auch bekannt als V operation) inkrementiert den Semaphor und ermöglicht einem blockierten Prozess, den kritischen Abschnitt zu betreten.

• Szenario 2: Sicherstellung, dass die Bearbeitung einer Kundenanfrage vollständig abgeschlossen wird, bevor eine neue Anfrage gestartet wird

Hier kann ein Zähle-Semaphor verwendet werden, um sicherzustellen, dass nur ein Prozess eine Kundenanfrage zur selben Zeit bearbeiten darf.Pseudocode:

semaphore request_sem = 1 // Zähle-Semaphor, initial auf 1 gesetzt// Hauptprozesswhile (true) {   wait(request_sem)   // code to dispatch customer request to a worker process   signal(request_sem)}// Worker Prozesswait(request_sem)   // Bearbeitung der Kundenanfrage   process_request()signal(request_sem)

Erklärung:1. wait(request_sem) dekrementiert den Semaphor. Dadurch wird verhindert, dass ein anderer Prozess eine neue Kundenanfrage bearbeitet, während die aktuelle Anfrage in Bearbeitung ist.2. Der kritische Abschnitt beinhaltet die komplette Bearbeitung der Kundenanfrage.3. signal(request_sem) inkrementiert den Semaphor und ermöglicht dem nächsten Prozess, die nächste Anfrage zu bearbeiten.Durch die Anwendung dieser Semaphore-Operationen kannst Du sicherstellen, dass Race Conditions vermieden werden, indem der Zugriff auf gemeinsame Ressourcen und die Reihenfolge der Aufgaben strikt kontrolliert wird.

Aufgabe 3)

In dieser Aufgabe betrachten wir die Prozesssynchronisation und Deadlock-Behandlung in der Systemprogrammierung. Dazu gehören Mechanismen wie Semaphoren, Monitore und Spinlocks sowie Deadlock-Bedingungen und Strategien zur Deadlock-Behandlung wie Vermeidung, Verhinderung, Erkennung und Behebung. Wir werden uns auch mit dem Banker's Algorithm zur Deadlock-Vermeidung und der Analyse von Warteschlangen-Grafen auseinandersetzen.

a)

Gegeben sei ein System mit vier Prozessen und drei Ressourcenarten. Jedes Systemzustand wird durch einen Warteschlangen-Grafen dargestellt, in dem Knoten Prozesse und Kanten Anforderungen oder Allokationen von Ressourcen repräsentieren.

• Zeichne einen solchen Grafen für einen beliebigen validen Zustand des Systems.
• Wie kannst Du anhand dieses Grafen einen Deadlock identifizieren?
• Gib eine formale Definition der vier notwendigen Bedingungen für einen Deadlock und stelle dar, wie sie sich in deinem Grafen manifestieren würden.

Lösung:

In dieser Aufgabe zur Prozesssynchronisation und Deadlock-Behandlung betrachten wir ein System mit vier Prozessen und drei Ressourcenarten. Ein Wartegraph ist ein hilfreiches Werkzeug, um den Status des Systems zu visualisieren und zu analysieren. Gegeben sei ein Systemzustand, der durch einen solchen Grafen dargestellt wird.

• Zeichne einen solchen Grafen für einen beliebigen validen Zustand des Systems:Hier ist ein Beispieldiagramm eines Warteschlangen-Grafen für einen möglichen Zustand:

                     P1        P2       P3        P4                    |         |          |          |                    R1       R2        R3       R1

  Beschreibung:- P1, P2, P3, P4 repräsentieren die Prozesse 1, 2, 3 und 4.- R1, R2, R3 repräsentieren die drei Ressourcenarten.- Eine Kante von P1 zu R1 bedeutet beispielsweise, dass Prozess P1 die Ressource R1 anfordert.- Eine Kante von R1 zu P1 bedeutet, dass Ressource R1 bereits an Prozess P1 allokiert ist.

Wie kannst Du anhand dieses Grafen einen Deadlock identifizieren?Ein Deadlock ist in einem Warteschlangen-Grafen erkennbar, wenn es Zyklen gibt. Das bedeutet, dass es eine geschlossene Kette von Prozessen und Ressourcen gibt, in der jeder Prozess auf eine Ressource wartet, die von einem anderen Prozess gehalten wird, der wiederum auf eine weitere Ressource wartet, die von einem anderen Prozess gehalten wird usw. Wenn ein solcher Zyklus gefunden wird, liegt ein Deadlock vor.

Gib eine formale Definition der vier notwendigen Bedingungen für einen Deadlock und stelle dar, wie sie sich in deinem Grafen manifestieren würden:

• Mutual Exclusion (Wechselseitiger Ausschluss): Mindestens eine Ressource muss exklusiv von einem Prozess gehalten werden. Dies wird im Grafen dadurch dargestellt, dass eine Ressource R1 nur einen ausgehenden Pfeil zu einem Prozess P1 hat.
• Hold and Wait (Halten und Warten): Ein Prozess, der bereits Ressourcen hält, kann zusätzliche Ressourcen anfordern. Im Grafen manifestiert sich dies durch einen Prozess, der sowohl eingehende Pfeile von Ressourcen, die er hält, als auch ausgehende Pfeile zu Ressourcen, die er anfordert, hat.
• No Preemption (Keine Enteignung): Ressourcen können nur freiwillig von den Prozessen freigegeben werden. Dies bedeutet im Grafen, dass eine Ressource nur dann zu einem anderen Prozess wechseln kann, wenn der aktuelle Prozess sie freigibt (kein direkter Pfeilwechsel).
• Circular Wait (Zirkuläres Warten): Eine zyklische Kette von Prozessen existiert, in der jeder Prozess auf eine Ressource wartet, die vom nächsten Prozess in der Kette gehalten wird. Dies wird im Grafen durch das Vorhandensein eines Zirkels von Kanten dargestellt.

b)

Angenommen, dass ein Deadlock aufgetreten ist, beschreibe detailliert den Algorithmus oder die Algorithmen (einschließlich Pseudocode, wo angebracht), die zur Deadlock-Erkennung und Behebung verwendet werden können. Achte dabei besonders auf die Analyse des Warteschlangen-Grafen und beschreibe ethische Erwägungen bei der Auswahl von Prozessen zum Beenden.

Lösung:

In diesem Abschnitt beschreiben wir detailliert, wie Deadlocks erkannt und behoben werden können:

• Deadlock-Erkennung:Ein gängiger Ansatz zur Deadlock-Erkennung ist die Verwendung eines angepassten Warteschlangen-Grafen und eines Tiefensuchalgorithmus (Depth-First Search, DFS), um Zyklen zu identifizieren. Wenn ein Zyklus im Grafen gefunden wird, liegt ein Deadlock vor.Hier ist ein Pseudocode zur Deadlock-Erkennung:

initialize visited = set() initialize stack = set() function hasCycle(node):  if node in stack:    return True  if node in visited:    return False  add node to visited  add node to stack  for each neighbor in graph[node]:    if hasCycle(neighbor):      return True  remove node from stack  return Falsefunction detectDeadlock(graph):  for node in graph:    if node not in visited:      if hasCycle(node):        return True  return False 

Beschreibung:- Der Pseudocode durchläuft alle Knoten im Graphen.- Die funktion hasCycle verwendet DFS, um zu prüfen, ob ein Zyklus existiert, indem sie rekursiv die Nachbarn eines Knotens besucht und dabei einen Stack zur Zyklusüberprüfung führt.

Deadlock-Behebung:Nachdem ein Deadlock erkannt wurde, ist der nächste Schritt, diesen zu beheben. Es gibt verschiedene Strategien zur Deadlock-Behebung, eine davon ist die Prozessbeendigung. Diese kann allerdings zu Datenverlust führen und sollte daher mit Bedacht angewendet werden.Hier sind die Schritte zur Deadlock-Behebung:

• Abbrechen von Prozessen:Falls mehrere Prozesse involviert sind, könnte man einen oder mehrere Prozesse abbrechen, um den Zyklus zu durchbrechen.
• Ressourcenfreigabe erzwingen:Ein Prozess könnte gezwungen werden, Ressourcen freizugeben. Ein ressourcenfreier Prozess könnte dann wiederkehren und möglicherweise den Deadlock aufheben.

Bei der Auswahl von Prozessen zum Beenden müssen ethische Erwägungen berücksichtigt werden. Dazu gehören:

• Priorität der Prozesse: Prozesse mit niedrigeren Prioritäten könnten für die Beendigung in Betracht gezogen werden, um den Einfluss auf das System zu minimieren.
• Alter und Fortschritt: Prozesse, die kürzlich gestartet wurden und weniger Fortschritt gemacht haben, könnten bevorzugt beendet werden, um aufwändige Rollbacks zu vermeiden.
• Nutzereingaben: Wenn die Beendigung von Prozessen zu einem Verlust von Benutzerdaten führen könnte, sollte dies vermieden oder zumindest dem Benutzer mitgeteilt werden.

Zusammenfassend lässt sich sagen, dass die Deadlock-Erkennung und -Behebung eine Balance zwischen technischer Notwendigkeit und ethischer Verantwortung erfordert. Durch die sorgfältige Analyse des Warteschlangen-Grafen und die Berücksichtigung der genannten Erwägungen können Deadlocks effektiv und verantwortungsbewusst behandelt werden.

c)

Erkläre den Banker's Algorithm und demonstriere seine Anwendung anhand eines Beispiels.

• Gegeben sei ein System mit 5 Prozessen und drei Ressourcenarten. Die Gesamtanzahl der Ressourcenarten sei jeweils 10, 5 und 7. Ein Beispiel-Initialisierungszustand wird definiert wie folgt:

 'AR = [0, 1, 0; 2, 0, 0; 3, 0, 2; 2, 1, 1; 0, 0, 2]' 

__`AF = [7, 4, 3]`__:

Berechne, ob der aktuelle Zustand sicher ist. Falls ja, gebe eine mögliche sichere Sequenz an.

Lösung:

Der Banker's Algorithmus ist ein Deadlock-Vermeidungsalgorithmus, der von Edsger Dijkstra entwickelt wurde. Der Algorithmus stellt sicher, dass ein System in einem sicheren Zustand bleibt, indem er überprüft, ob die Ressourcenanforderungen der Prozesse erfüllt werden können, ohne das Risiko eines Deadlocks einzugehen.

Hier ist eine Schritt-für-Schritt-Erklärung des Banker's Algorithmus:

• Ermittelt den Bedarf jedes Prozesses (Maximalanforderung minus Allokation).
• Überprüft, ob genügend Ressourcen verfügbar sind, um die Anforderungen der Prozesse zu erfüllen, und bestimmt, ob eine sichere Zustandsfolge existiert.

Betrachten wir ein Beispiel mit einem System, das 5 Prozesse (P0 bis P4) und drei Ressourcenarten (R1, R2 und R3) hat. Die Gesamtzahl der verfügbaren Ressourcen ist 10 von R1, 5 von R2 und 7 von R3. Der Ressourcen-Allokationsstatus (AR) und die verfügbaren Ressourcen (AF) sind wie folgt definiert:

AR = [[0, 1, 0], [2, 0, 0], [3, 0, 2], [2, 1, 1], [0, 0, 2]]AF = [7, 4, 3]

Um zu überprüfen, ob der aktuelle Zustand sicher ist, führen wir den Banker's Algorithmus aus:

• Schritt 1: Berechnung des Bedarfs (Need-Matrix)

Max = [[7, 5, 3], [3, 2, 2], [9, 0, 2], [2, 2, 2], [4, 3, 3]]Need = Max - ARNeed = [[7-0, 5-1, 3-0], [3-2, 2-0, 2-0], [9-3, 0-0, 2-2], [2-2, 2-1, 2-1], [4-0, 3-0, 3-2]]Need = [[7, 4, 3], [1, 2, 2], [6, 0, 0], [0, 1, 1], [4, 3, 1]]

Schritt 2: Durchführung der Sicherheitsüberprüfung

initialize Work = [7, 4, 3]initialize Finish = [False, False, False, False, False]repeat:  for each process P in range(5):    if Finish[P] == False and Need[P] <= Work:      Work = Work + AR[P]      Finish[P] = True      add P to safe_sequenceuntil Finish = [True, True, True, True, True]

Verwenden wir den obigen Pseudocode und prüfen, welche Prozesse in welcher Reihenfolge beendet werden können:

• Nehmen wir an, wir überprüfen zuerst P4:Need[4] = [4, 3, 1] und die derzeit verfügbaren Ressourcen (Work) sind [7, 4, 3], die ausreichend sind, um P4's Bedarf zu decken. Folglich (Work = Work + AR[4] = [7, 4, 3] + [0, 0, 2] = [7, 4, 5]).
• Als Nächstes überprüfen wir P0:Need[0] = [7, 4, 3] und Work >= Need[0]. Folglich (Work = Work + AR[0] = [7, 4, 5] + [0, 1, 0] = [7, 5, 5]).
• Dann überprüfen wir P1:Need[1] = [1, 2, 2] und Work >= Need[1]. Folglich (Work = Work + AR[1] = [7, 5, 5] + [2, 0, 0] = [9, 5, 5]).
• Dann überprüfen wir P3:Need[3] = [0, 1, 1] und Work >= Need[3]. Folglich (Work = Work + AR[3] = [9, 5, 5] + [2, 1, 1] = [11, 6, 6]).
• Schließlich überprüfen wir P2:Need[2] = [6, 0, 0] und Work >= Need[2]. Folglich (Work = Work + AR[2] = [11, 6, 6] + [3, 0, 2] = [14, 6, 8]).

Das System befindet sich in einem sicheren Zustand, und eine mögliche sichere Sequenz ist [P4, P0, P1, P3, P2].

d)

Angenommen, ein System nutzt Semaphoren zur Prozesssynchronisation.

• Beschreibe ein Szenario, in dem die Verwendung von Semaphoren zu einem Deadlock führen könnte. Erkläre dieses Szenario detailliert.
• Wie würde man solche Deadlocks durch die Nutzung von Monitore verhindern? Gib Beispielcode in Pseudocode oder einer Programmiersprache deiner Wahl an.

Lösung:

In diesem Teil der Aufgabe betrachten wir, wie die Verwendung von Semaphoren zu einem Deadlock führen kann, und wie Monitore dabei helfen können, solche Deadlocks zu verhindern.

• Szenario, in dem die Verwendung von Semaphoren zu einem Deadlock führen könnte:Betrachten wir zwei Prozesse (P1 und P2) und zwei Ressourcen (R1 und R2), wobei jede Ressource von einem eigenen Semaphore geschützt wird (S1 und S2). Ein Deadlock-Szenario kann wie folgt aussehen:

  1. Initialisierung:Semaphore S1 = 1;Semaphore S2 = 1;2. Prozess P1:P1:    wait(S1);          // P1 sperrt Ressource R1    wait(S2);          // P1 versucht Ressource R2 zu sperren, die von P2 gesperrt ist    // Nutzung von Ressourcen R1 und R2    signal(S2);        // Freigabe von R2    signal(S1);        // Freigabe von R13. Prozess P2:P2:    wait(S2);          // P2 sperrt Ressource R2    wait(S1);          // P2 versucht Ressource R1 zu sperren, die von P1 gesperrt ist    // Nutzung von Ressourcen R2 und R1    signal(S1);        // Freigabe von R1    signal(S2);        // Freigabe von R2

  Hier entsteht ein Deadlock, wenn P1 Ressourcen R1 sperrt und auf R2 wartet, während P2 Ressourcen R2 sperrt und auf R1 wartet. Es entsteht ein Zyklus des Wartens, und keiner der Prozesse kann fortfahren.

Vermeidung von Deadlocks durch die Nutzung von Monitoren:Ein Monitor ist eine Synchronisationsstruktur, die einen sichereren und modularen Weg zur Handhabung des Ressourcenmanagements bietet. Monitore verhinderns Deadlocks, indem sie den Zugriff auf gemeinsam genutzte Ressourcen seriell verwalten.

• Hier ist ein Beispiel in Pseudocode zur Verwendung von Monitoren:

  Monitor ResourceManager:    var R1 = true;                // R1 verfügbar    var R2 = true;                // R2 verfügbar    procedure acquire_resources(& R1, & R2):        while !R1 or !R2:            wait;        R1 = false;        R2 = false;    procedure release_resources(& R1, & R2):        R1 = true;        R2 = true;        signal;Prozess P1 and P2:P1:    call ResourceManager.acquire_resources;    // Nutzung von Ressourcen R1 und R2    call ResourceManager.release_resources;P2:    call ResourceManager.acquire_resources;    // Nutzung von Ressourcen R1 und R2    call ResourceManager.release_resources;

In diesem Fall stellt der Monitor sicher, dass die Ressourcen R1 und R2 seriell und ohne Konflikte erworben und freigegeben werden. Es gibt keine Zyklusbildung, und somit wird ein Deadlock verhindert.

Aufgabe 4)

Paging und virtuelle Speichertechniken:

• Virtueller Adressraum wird in Seiten (Pages) aufgeteilt.
• Physischer Speicher wird in Rahmen (Frames) aufgeteilt.
• Seitentabelle (Page Table) zur Verwaltung der Zuordnungen zwischen Pages und Frames.
• Adressumsetzung durch Hardware: MMU (Memory Management Unit).
• Seitenaustausch über lokale Platte bei Speichermangel.
• Effiziente Nutzung durch Vermeidung von Fragmentierung.
• Formel: Effektive Zugriffszeit (EAT) \( EAT = (1 - p) \times MA + p \times (P + S + MA)\) wobei \( p \) die Fehlerrate, \( MA \) die Speicherzugriffszeit, \( P \) die Swap-Seitenladezeit, und \( S \) die Zeit zum Speichern der Seite ist.

b)

Gegeben ist eine Seitentabelle (Page Table) mit folgenden Zuordnungen:

Virtuelle Seite (Page) : Physischer Rahmen (Frame)0x000A : 0x01FF0x000B : 0x02300x000C : 0x02B0...

a. Erläutere den Prozess, wie die Memory Management Unit (MMU) eine virtuelle Adresse in eine physische Adresse umwandelt.

b. Wenn die virtuelle Adresse 0x000A03 eingegeben wird, welche physische Adresse wird diese abbilden?

Lösung:

• Paging und virtuelle Speichertechniken:

• Virtueller Adressraum wird in Seiten (Pages) aufgeteilt.
• Physischer Speicher wird in Rahmen (Frames) aufgeteilt.
• Seitentabelle (Page Table) zur Verwaltung der Zuordnungen zwischen Pages und Frames.
• Adressumsetzung durch Hardware: MMU (Memory Management Unit).
• Seitenaustausch über lokale Platte bei Speichermangel.
• Effiziente Nutzung durch Vermeidung von Fragmentierung.
• Formel: Effektive Zugriffszeit (EAT) \( EAT = (1 - p) \times MA + p \times (P + S + MA) \) wobei \( p \) die Fehlerrate, \( MA \) die Speicherzugriffszeit, \( P \) die Swap-Seitenladezeit, und \( S \) die Zeit zum Speichern der Seite ist.

Löse die folgende Teilaufgabe: Gegeben ist eine Seitentabelle (Page Table) mit folgenden Zuordnungen:

Virtuelle Seite (Page) : Physischer Rahmen (Frame)0x000A : 0x01FF0x000B : 0x02300x000C : 0x02B0...

• a. Erläutere den Prozess, wie die Memory Management Unit (MMU) eine virtuelle Adresse in eine physische Adresse umwandelt.
• b. Wenn die virtuelle Adresse 0x000A03 eingegeben wird, welche physische Adresse wird diese abbilden?

• a. Prozess der Umwandlung einer virtuellen Adresse in eine physische Adresse durch die MMU:

• Seitentabelle: Bei Verwendung einer Seitentabelle wird der virtuelle Adressraum in Seiten (Pages) unterteilt. Jede Seite hat eine definierte Größe (z.B. 4KB). Der physische Speicher wird in Rahmen (Frames) der gleichen Größe unterteilt.
• Virtuelle Adresse aufteilen: Die virtuelle Adresse wird in zwei Teile unterteilt: den Seitenanteil (Page Number) und den Versatz (Offset). Der Seitenanteil wird verwendet, um die entsprechende physische Seite in der Seitentabelle nachzuschlagen.
• Seitentabellenübersetzung: Die MMU verwendet den Seitenanteil der virtuellen Adresse, um in der Seitentabelle den entsprechenden physischen Rahmen (Frame) zu finden.
• Berechnung der physischen Adresse: Nachdem der physische Rahmen gefunden wurde, kombiniert die MMU diesen mit dem Offset, um die vollständige physische Adresse zu berechnen.
• Speicherzugriff: Schließlich verwendet das System die berechnete physische Adresse, um auf die entsprechende Datenstelle im physischen Speicher zuzugreifen.

• b. Berechnung der physischen Adresse für die virtuelle Adresse 0x000A03:
Gegeben:
• Seitentabelle:

Virtuelle Seite (Page) : Physischer Rahmen (Frame)0x000A : 0x01FF0x000B : 0x02300x000C : 0x02B0...

Virtuelle Adresse: 0x000A03

Schritte:

• Virtuelle Adresse 0x000A03 aufteilen: Die ersten 4 Hexadezimalstellen (0x000A) repräsentieren die Seite, während die letzten 2 Hexadezimalstellen (0x03) den Offset angeben.
• Seitentabellenübersetzung: Nachschlagen der Seite 0x000A in der Seitentabelle ergibt den physischen Rahmen 0x01FF.
• Berechnung der physischen Adresse: Kombiniere den physischen Rahmen 0x01FF mit dem Offset 0x03. Dies ergibt die physische Adresse 0x01FF03.

Die virtuelle Adresse 0x000A03 bildet auf die physische Adresse 0x01FF03 ab.