Betriebssystemtechnik (V+EÜ) - Exam

Aufgabe 1)

Prozess-Scheduling-Algorithmen: Regeln und Methoden, nach denen ein Betriebssystem CPU-Zeit Prozessen zuweist.

• First-Come, First-Served (FCFS): Prozesse werden in der Reihenfolge ihrer Ankunft abgearbeitet.
• Shortest Job Next (SJN): Prozesse mit kürzester Ausführungszeit werden bevorzugt.
• Round Robin (RR): Prozesse erhalten zyklisch CPU-Zeit (Zeitscheibenverfahren).
• Priority Scheduling: Prozesse mit höherer Priorität werden bevorzugt behandelt.
• Multilevel Queue Scheduling: Prozesse werden in verschiedene Warteschlangen basierend auf Prioritäten oder Prozessarten aufgeteilt.
• Multilevel Feedback Queue: Kombination aus Multilevel Queue und dynamischer Prioritätsanpassung.
• Zeitscheiben (\textit{time quantum}): Dauer einer Prozessorzuteilung in RR und verwandten Algorithmen.

a)

Gegeben sei eine Liste von Prozessen mit ihren Ankunftszeiten und CPU-Burst-Zeiten:

• Prozess P1: Ankunftszeit = 0, CPU-Burst-Zeit = 5
• Prozess P2: Ankunftszeit = 2, CPU-Burst-Zeit = 3
• Prozess P3: Ankunftszeit = 4, CPU-Burst-Zeit = 1
• Prozess P4: Ankunftszeit = 6, CPU-Burst-Zeit = 2

Berechne die Durchschnittswartezeit für diese Prozesse, wenn der First-Come, First-Served (FCFS) Algorithmus verwendet wird.

Lösung:

Durchschnittliche Wartezeit berechnen unter Verwendung des First-Come, First-Served (FCFS) Algorithmus

Definition: In einem FCFS Scheduling-Algorithmus werden Prozesse basierend auf ihrer Ankunftszeit abgearbeitet. Das bedeutet, dass der Prozess, der zuerst ankommt, auch zuerst die CPU zugewiesen bekommt.Gegeben:

• Prozess P1: Ankunftszeit = 0, CPU-Burst-Zeit = 5
• Prozess P2: Ankunftszeit = 2, CPU-Burst-Zeit = 3
• Prozess P3: Ankunftszeit = 4, CPU-Burst-Zeit = 1
• Prozess P4: Ankunftszeit = 6, CPU-Burst-Zeit = 2

Schritte zur Berechnung der Wartezeit:

1. Prozess P1: - Wartezeit: 0 (da P1 sofort startet) - Startzeit: 0 - Endzeit: 0 + 5 = 5
2. Prozess P2: - Wartezeit: Endzeit von P1 - Ankunftszeit von P2 = 5 - 2 = 3 - Startzeit: 5 - Endzeit: 5 + 3 = 8
3. Prozess P3: - Wartezeit: Endzeit von P2 - Ankunftszeit von P3 = 8 - 4 = 4 - Startzeit: 8 - Endzeit: 8 + 1 = 9
4. Prozess P4: - Wartezeit: Endzeit von P3 - Ankunftszeit von P4 = 9 - 6 = 3 - Startzeit: 9 - Endzeit: 9 + 2 = 11

Berechnung der Durchschnittswartezeit:

• P1: 0 Minuten
• P2: 3 Minuten
• P3: 4 Minuten
• P4: 3 Minuten

Durchschnittswartezeit = \ \ \frac{0 + 3 + 4 + 3}{4} = \ \ \frac{10}{4} = 2,5 Minuten

b)

Verwende die gleiche Liste von Prozessen wie in der vorherigen Teilaufgabe, um die Durchschnittswartezeit unter Verwendung des Shortest Job Next (SJN) Algorithmus zu berechnen. Beachte, dass alle Prozesse am Anfang bekannt sind (nicht-präemptiv).

Lösung:

Durchschnittliche Wartezeit berechnen unter Verwendung des Shortest Job Next (SJN) Algorithmus

Definition: Im Shortest Job Next (SJN) Scheduling-Algorithmus werden Prozesse mit der kürzesten Ausführungszeit bevorzugt. Da in dieser Aufgabe alle Prozesse zu Beginn bekannt sind und SJN nicht-präemptiv ist, wird der nächste Prozess erst ausgeführt, wenn der aktuelle Prozess abgeschlossen ist.Gegeben:

• Prozess P1: Ankunftszeit = 0, CPU-Burst-Zeit = 5
• Prozess P2: Ankunftszeit = 2, CPU-Burst-Zeit = 3
• Prozess P3: Ankunftszeit = 4, CPU-Burst-Zeit = 1
• Prozess P4: Ankunftszeit = 6, CPU-Burst-Zeit = 2

Schritte zur Berechnung der Wartezeit:

1. Prozess P1: - Wartezeit: 0 (da P1 sofort startet) - Startzeit: 0 - Endzeit: 0 + 5 = 5
2. Prozess P3: - Wartezeit: Endzeit von P1 - Ankunftszeit von P3 = 5 - 4 = 1 - Startzeit: 5 - Endzeit: 5 + 1 = 6
3. Prozess P4: - Wartezeit: Endzeit von P3 - Ankunftszeit von P4 = 6 - 6 = 0 - Startzeit: 6 - Endzeit: 6 + 2 = 8
4. Prozess P2: - Wartezeit: Endzeit von P4 - Ankunftszeit von P2 = 8 - 2 = 6 - Startzeit: 8 - Endzeit: 8 + 3 = 11

Berechnung der Durchschnittswartezeit:

• P1: 0 Minuten
• P3: 1 Minute
• P4: 0 Minuten
• P2: 6 Minuten

Durchschnittswartezeit = \( \frac{0 + 1 + 0 + 6}{4} \) = \( \frac{7}{4} \) = 1,75 Minuten

c)

Angenommen, die Zeitscheibe (\textit{time quantum}) für den Round Robin (RR) Algorithmus beträgt 2 Zeiteinheiten. Berechne das Gantt-Diagramm für die oben genannten Prozesse und bestimme die Durchschnittswartezeit.

Lösung:

Durchschnittliche Wartezeit und Gantt-Diagramm unter Verwendung des Round Robin (RR) Algorithmus

Definition: Beim Round Robin (RR) Scheduling-Algorithmus erhalten Prozesse zyklisch CPU-Zeit. Die Zeitscheibe (\textit{time quantum}) ist ein festgelegter Zeitraum, den jeder Prozess pro Runde erhält.Gegeben:

• Prozess P1: Ankunftszeit = 0, CPU-Burst-Zeit = 5
• Prozess P2: Ankunftszeit = 2, CPU-Burst-Zeit = 3
• Prozess P3: Ankunftszeit = 4, CPU-Burst-Zeit = 1
• Prozess P4: Ankunftszeit = 6, CPU-Burst-Zeit = 2
• Zeitscheibe = 2 Zeiteinheiten

Gantt-Diagramm:

Um das Gantt-Diagramm zu erstellen, gehen wir in Zeitscheiben von je 2 Einheiten durch:

1. P1 (0-2): Restzeit = 3
2. P2 (2-4): Restzeit = 1
3. P1 (4-6): Restzeit = 1
4. P3 (6-7): Restzeit = 0
5. P4 (7-9): Restzeit = 0
6. P1 (9-10): Restzeit = 0
7. P2 (10-11): Restzeit = 0

Gantt-Diagramm:

P1  P2  P1  P3  P4  P1  P20   2   4   6   7   9   10 11

Berechnung der Wartezeiten:

• P1: Startzeiten: 0, 4, 9 - Wartezeit: 0 + (4 - 2) + (9 - 6) = 5 Min.
• P2: Startzeiten: 2, 10 - Wartezeit: (2 - 2) + (10 - 4) = 6 Min.
• P3: Startzeit: 6 - Wartezeit: 6 - 4 = 2 Min.
• P4: Startzeit: 7 - Wartezeit: 7 - 6 = 1 Min.

Durchschnittswartezeit:

Durchschnittswartezeit = \( \frac{5 + 6 + 2 + 1}{4} \) = \( \frac{14}{4} \) = 3,5 Minuten

d)

Für dasselbe Prozess-Set: Implementiere den Priority Scheduling Algorithmus, wobei die Prioritäten der Prozesse wie folgt sind:

• Prozess P1: Priorität = 3
• Prozess P2: Priorität = 1
• Prozess P3: Priorität = 4
• Prozess P4: Priorität = 2

Berechne die Durchschnittswartezeit, wenn der Algorithmus präemptiv ist.

Lösung:

Durchschnittliche Wartezeit berechnen unter Verwendung des präemptiven Priority Scheduling Algorithmus

Definition: Beim präemptiven Priority Scheduling Algorithmus werden Prozesse mit höherer Priorität bevorzugt behandelt. Ein Prozess kann einen laufenden Prozess unterbrechen, wenn er eine höhere Priorität hat.Gegeben:

• Prozess P1: Ankunftszeit = 0, CPU-Burst-Zeit = 5, Priorität = 3
• Prozess P2: Ankunftszeit = 2, CPU-Burst-Zeit = 3, Priorität = 1
• Prozess P3: Ankunftszeit = 4, CPU-Burst-Zeit = 1, Priorität = 4
• Prozess P4: Ankunftszeit = 6, CPU-Burst-Zeit = 2, Priorität = 2

Beachte, dass niedrigere Zahlen höhere Prioritäten darstellen.

Gantt-Diagramm:

Wir sortieren die Prozesse nach Ankunftszeit und Priorität, wobei Prozesse mit höherer Priorität (niedrigere Zahl) bevorzugt behandelt werden:

1. P1 (0-2): P2 unterbricht bei Ankunft um 2 aufgrund höherer Priorität
2. P2 (2-5): P2 läuft bis zur Beendigung
3. P1 (5-6): P3 läuft bei Ankunft um 4
4. P3 (6-7): P4 läuft bei Ankunft um 6
5. P4 (7-9): P4 läuft bis zur Beendigung
6. P1 (9-11): P1 setzt fort

Gantt-Diagramm:

P1  P2  P1  P3  P4  P10   2   2   5  5  6   7  7  9  9  11

Berechnung der Wartezeiten:

• P1: Startzeiten: 0, 5, 9 - Wartezeit: (5 - 2) + (9 - 5) = 7 Minuten
• P2: Startzeit: 2 - Wartezeit: 0 Minuten
• P3: Startzeit: 6 - Wartezeit: 6 - 4 = 2 Minuten
• P4: Startzeit: 7 - Wartezeit: 7 - 6 = 1 Minuten

Durchschnittswartezeit:

Durchschnittswartezeit = \( \frac{7 + 0 + 2 + 1}{4} \) = \( \frac{10}{4} \) = 2,5 Minuten

Aufgabe 2)

Interprozesskommunikation (IPC):Mechanismen zur Datenübertragung und Synchronisation zwischen Prozessen im Betriebssystem.

• Methoden: Speicherbasierte (Shared Memory), Nachrichtenbasierte (Message Passing).
• Shared Memory: Prozesse teilen sich einen Speicherbereich; benötigt Synchronisation wie Semaphoren/Mutex.
• Message Passing: Prozesse kommunizieren über Nachrichten; verwendet Primitive wie Sockets, Pipes, Message Queues.
• Sicherheit und Zugriffskontrolle: Notwendig zur Vermeidung von Konkurrenzbedingungen und Deadlocks.
• Beispiele: Unix-Pipes, POSIX-Shared Memory, Windows Named Pipes.

a)

Aufgabe: Implementiere eine Applikation in C, die es zwei Prozessen erlaubt, durch Shared Memory zu kommunizieren. Diese Applikation soll einen gemeinsamen Speicherbereich einrichten, in dem eine Zeichenkette gespeichert wird. Stelle sicher, dass die beiden Prozesse nicht in Konkurrenz zueinander stehen, indem Du geeignete Synchronisationsmechanismen verwendest. Hinweise:

• Verwende POSIX API für Shared Memory und Synchronisation.
• Stelle sicher, dass Synchronisationsprimitiven wie Semaphoren korrekt implementiert werden.
• Gebe den gesamten Code an, inklusive der Initialisierung und Bereinigung von Ressourcen.

 #include  #include  #include  #include  #include  #include  #include  #include  #include  int main() { // Initialisierung öffentlicher Code... } 

Lösung:

Interprozesskommunikation (IPC):Mechanismen zur Datenübertragung und Synchronisation zwischen Prozessen im Betriebssystem.

• Methoden: Speicherbasierte (Shared Memory), Nachrichtenbasierte (Message Passing).
• Shared Memory: Prozesse teilen sich einen Speicherbereich; benötigt Synchronisation wie Semaphoren/Mutex.
• Message Passing: Prozesse kommunizieren über Nachrichten; verwendet Primitive wie Sockets, Pipes, Message Queues.
• Sicherheit und Zugriffskontrolle: Notwendig zur Vermeidung von Konkurrenzbedingungen und Deadlocks.
• Beispiele: Unix-Pipes, POSIX-Shared Memory, Windows Named Pipes.

Aufgabe: Implementiere eine Applikation in C, die es zwei Prozessen erlaubt, durch Shared Memory zu kommunizieren. Diese Applikation soll einen gemeinsamen Speicherbereich einrichten, in dem eine Zeichenkette gespeichert wird. Stelle sicher, dass die beiden Prozesse nicht in Konkurrenz zueinander stehen, indem Du geeignete Synchronisationsmechanismen verwendest. Hinweise:

• Verwende POSIX API für Shared Memory und Synchronisation.
• Stelle sicher, dass Synchronisationsprimitiven wie Semaphoren korrekt implementiert werden.
• Gebe den gesamten Code an, inklusive der Initialisierung und Bereinigung von Ressourcen.

 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <unistd.h> #include <sys/mman.h> #include <sys/stat.h> #include <fcntl.h> #include <semaphore.h> #include <sys/types.h> #include <sys/wait.h> #define SHARED_MEMORY_NAME "/my_shared_memory" #define SEMAPHORE_NAME "/my_semaphore" #define SHARED_MEMORY_SIZE 256 int main() {     // Initialisierung     int shm_fd;     char *shared_memory;     sem_t *semaphore;     // Erstellen und Öffnen des Shared Memory     shm_fd = shm_open(SHARED_MEMORY_NAME, O_CREAT | O_RDWR, 0666);     if (shm_fd == -1) {         perror("shm_open");         exit(EXIT_FAILURE);     }     // Festlegen der Speichergröße     if (ftruncate(shm_fd, SHARED_MEMORY_SIZE) == -1) {         perror("ftruncate");         exit(EXIT_FAILURE);     }     // Speicherbereich mappen     shared_memory = mmap(NULL, SHARED_MEMORY_SIZE, PROT_READ | PROT_WRITE, MAP_SHARED, shm_fd, 0);     if (shared_memory == MAP_FAILED) {         perror("mmap");         exit(EXIT_FAILURE);     }     // Erstellen des Semaphors     semaphore = sem_open(SEMAPHORE_NAME, O_CREAT, 0666, 1);     if (semaphore == SEM_FAILED) {         perror("sem_open");         exit(EXIT_FAILURE);     }     // Erstellen eines Kindprozesses     pid_t pid = fork();     if (pid == -1) {         perror("fork");         exit(EXIT_FAILURE);     }     if (pid == 0) {         // Kindprozess         // Sperren des Semaphors         sem_wait(semaphore);         // Schreiben in das Shared Memory         const char *message = "Hello from Child";         strncpy(shared_memory, message, SHARED_MEMORY_SIZE);         printf("Child has written to shared memory: %s", message);         // Freigeben des Semaphors         sem_post(semaphore);         // Beenden des Kindprozesses         exit(EXIT_SUCCESS);     } else {         // Elternprozess         // Warten auf Kindprozess         wait(NULL);         // Sperren des Semaphors         sem_wait(semaphore);         // Lesen aus dem Shared Memory         printf("Parent has read from shared memory: %s", shared_memory);         // Freigeben des Semaphors         sem_post(semaphore);         // Bereinigen der Ressourcen         munmap(shared_memory, SHARED_MEMORY_SIZE);         shm_unlink(SHARED_MEMORY_NAME);         sem_close(semaphore);         sem_unlink(SEMAPHORE_NAME);     }     return 0; } 

b)

Aufgabe: Analysiere die folgenden Szenarien der Prozesskommunikation mittels Message Passing und beschreibe detailliert potenzielle Probleme der Sicherheit und Zugriffskontrolle sowie mögliche Lösungen. Verwende dabei sowohl Sockets als auch Pipes als Kommunikationsmethoden. Szenarien:

• Ein Server-Prozess kommuniziert mit mehreren Client-Prozessen über Unix-Sockets. Wie kann verhindert werden, dass unautorisierte Clients den Server erreichen?
• Zwei Prozesse tauschen große Datenmengen über Named Pipes aus. Wie können Deadlocks vermieden werden?

Lösung:

Interprozesskommunikation (IPC):Mechanismen zur Datenübertragung und Synchronisation zwischen Prozessen im Betriebssystem.

• Methoden: Speicherbasierte (Shared Memory), Nachrichtenbasierte (Message Passing).
• Shared Memory: Prozesse teilen sich einen Speicherbereich; benötigt Synchronisation wie Semaphoren/Mutex.
• Message Passing: Prozesse kommunizieren über Nachrichten; verwendet Primitive wie Sockets, Pipes, Message Queues.
• Sicherheit und Zugriffskontrolle: Notwendig zur Vermeidung von Konkurrenzbedingungen und Deadlocks.
• Beispiele: Unix-Pipes, POSIX-Shared Memory, Windows Named Pipes.

Aufgabe: Analysiere die folgenden Szenarien der Prozesskommunikation mittels Message Passing und beschreibe detailliert potenzielle Probleme der Sicherheit und Zugriffskontrolle sowie mögliche Lösungen. Verwende dabei sowohl Sockets als auch Pipes als Kommunikationsmethoden.

• Ein Server-Prozess kommuniziert mit mehreren Client-Prozessen über Unix-Sockets. Wie kann verhindert werden, dass unautorisierte Clients den Server erreichen?
• Zwei Prozesse tauschen große Datenmengen über Named Pipes aus. Wie können Deadlocks vermieden werden?

Analyse und Lösungen:

• Ein Server-Prozess kommuniziert mit mehreren Client-Prozessen über Unix-Sockets. Wie kann verhindert werden, dass unautorisierte Clients den Server erreichen?
  • Problem: Wenn ein Server-Prozess über Unix-Sockets mit mehreren Client-Prozessen kommuniziert, besteht die Gefahr, dass unautorisierte Clients versuchen, eine Verbindung zum Server herzustellen. Dies könnte zu Sicherheitslücken führen, wie z.B. Datenverlust oder unbefugtem Zugriff.
  • Lösungen:
    • Authentifizierung: Der Server kann Authentifizierungsmechanismen implementieren, um sicherzustellen, dass nur berechtigte Clients eine Verbindung herstellen können. Beispielsweise könnte ein Token-basierter Ansatz verwendet werden, bei dem jeder Client ein eindeutiges Authentifizierungstoken senden muss.
    • Dateizugriffsrechte: Unix-Sockets werden als Dateisystemobjekte behandelt. Es ist möglich, Zugriffsrechte auf den Socket-Dateien mit chmod und chown zu setzen, um unautorisierte Zugriffe zu verhindern. Nur Prozesse, die von einem bestimmten Benutzer oder einer bestimmten Gruppe ausgeführt werden, können auf diese Dateien zugreifen.
    • SSL/TLS Verschlüsselung: Um die Sicherheit auf Transportebene zu gewährleisten, können Unix-Sockets auch mit SSL/TLS verschlüsselt werden. Dadurch wird sichergestellt, dass Daten, die zwischen Server und Clients ausgetauscht werden, nicht abgefangen oder manipuliert werden können.
• Zwei Prozesse tauschen große Datenmengen über Named Pipes aus. Wie können Deadlocks vermieden werden?
  • Problem: Bei der Kommunikation zwischen zwei Prozessen, die große Datenmengen über Named Pipes austauschen, besteht das Risiko von Deadlocks. Deadlocks treten auf, wenn jeder Prozess auf Ressourcen wartet, die vom anderen Prozess gehalten werden, wodurch beide blockiert sind.
  • Lösungen:
    • Timeouts: Durch das Setzen von Zeitlimits (Timeouts) für Lese- und Schreiboperationen können Deadlocks vermieden werden. Wenn eine Operation zu lange dauert, gibt sie einen Fehler zurück, und die Prozesse können geeignete Maßnahmen ergreifen.
    • Puffergrößen: Die Verwendung geeigneter Puffergrößen kann dazu beitragen, Deadlocks zu vermeiden. Zu kleine Puffer können dazu führen, dass Writes blockieren, während sie auf das Lesen warten. Größere Puffer ermöglichen einen besseren Datenfluss und verringern die Wahrscheinlichkeit von Deadlocks.
    • Sperrmechanismen: Implementierung von Sperrmechanismen (Locks), die sicherstellen, dass nur ein Prozess gleichzeitig auf die Pipe zugreift. Mutexe oder Semaphore können verwendet werden, um den Zugang zu den Pipes zu koordinieren.
    • Kommunikationsprotokolle: Die Prozesse sollten ein Kommunikationsprotokoll verwenden, das die Reihenfolge und Sicherheit der Datenübertragung gewährleistet. Durch das Definieren klarer Nachrichtenformate und Handshake-Mechanismen kann sichergestellt werden, dass Daten korrekt und in der richtigen Reihenfolge übertragen werden.

Aufgabe 3)

Deadlock und deren Vermeidung:Ein Deadlock ist ein Zustand, bei dem mehrere Prozesse auf Ressourcen warten, die von anderen Prozessen gehalten werden, wodurch keiner der Prozesse fortfahren kann.

• Vier notwendige Bedingungen für Deadlocks: Mutual Exclusion, Hold and Wait, No Preemption, Circular Wait
• Strategien zur Deadlock-Vermeidung: Vermeidung, Verhinderung, Erkennung und Behandlung
• Vermeidungsalgorithmen: Banker's Algorithm
• Verhinderungsmethoden: Ressourcenhierarchie einhalten, keine Ressource mehrfach anfordern
• Erkennung: Ressourcen-Allokationsgraph analysieren
• Behandlung: Prozesse forcieren, Ressourcen freigeben, System neu starten

a)

Angenommen, es gibt ein System, das drei Arten von Ressourcen (A, B, und C) hat. Prozesse P1, P2 und P3 greifen auf diese Ressourcen zu. Die aktuelle Verteilung und die maximale Anforderung für jeden Prozess sind wie folgt:

• Ressourcen verfügbar: A = 3, B = 2, C = 2
• P1 hat: A = 1, B = 0, C = 1 und benötigt max: A = 2, B = 1, C = 3
• P2 hat: A = 0, B = 1, C = 0 und benötigt max: A = 2, B = 2, C = 1
• P3 hat: A = 1, B = 1, C = 1 und benötigt max: A = 1, B = 1, C = 2

Beantworte die folgenden Fragen:

• Bestimme, ob das System aktuell in einem sicheren Zustand ist, indem Du den Banker's Algorithm anwendest.
• Wenn das System nicht sicher ist, erkläre, warum es so ist, und beschreibe eine Strategie, um das System in einen sicheren Zustand zu überführen.

Lösung:

Deadlock und deren Vermeidung:Ein Deadlock ist ein Zustand, bei dem mehrere Prozesse auf Ressourcen warten, die von anderen Prozessen gehalten werden, wodurch keiner der Prozesse fortfahren kann.

• Vier notwendige Bedingungen für Deadlocks: Mutual Exclusion, Hold and Wait, No Preemption, Circular Wait
• Strategien zur Deadlock-Vermeidung: Vermeidung, Verhinderung, Erkennung und Behandlung
• Vermeidungsalgorithmen: Banker's Algorithm
• Verhinderungsmethoden: Ressourcenhierarchie einhalten, keine Ressource mehrfach anfordern
• Erkennung: Ressourcen-Allokationsgraph analysieren
• Behandlung: Prozesse forcieren, Ressourcen freigeben, System neu starten

Angenommen, es gibt ein System, das drei Arten von Ressourcen (A, B, und C) hat. Prozesse P1, P2 und P3 greifen auf diese Ressourcen zu. Die aktuelle Verteilung und die maximale Anforderung für jeden Prozess sind wie folgt:

• Ressourcen verfügbar: A = 3, B = 2, C = 2
• P1 hat: A = 1, B = 0, C = 1 und benötigt max: A = 2, B = 1, C = 3
• P2 hat: A = 0, B = 1, C = 0 und benötigt max: A = 2, B = 2, C = 1
• P3 hat: A = 1, B = 1, C = 1 und benötigt max: A = 1, B = 1, C = 2

Beantworte die folgenden Fragen:

• Bestimme, ob das System aktuell in einem sicheren Zustand ist, indem Du den Banker's Algorithm anwendest.
• Wenn das System nicht sicher ist, erkläre, warum es so ist, und beschreibe eine Strategie, um das System in einen sicheren Zustand zu überführen.

Lösung:Um zu bestimmen, ob das System in einem sicheren Zustand ist, wenden wir den Banker's Algorithm an. Der Algorithmus prüft, ob es eine Sequenz gibt, in der alle Prozesse vollständig ausgeführt werden können, ohne dass es zu einem Deadlock kommt.1. Aktueller Zustand:Verfügbare Ressourcen:

• A = 3
• B = 2
• C = 2

Belegte Ressourcen (Summe):

• P1: A = 1, B = 0, C = 1
• P2: A = 0, B = 1, C = 0
• P3: A = 1, B = 1, C = 1

Belegte Ressourcen insgesamt:

• A = 1 + 0 + 1 = 2
• B = 0 + 1 + 1 = 2
• C = 1 + 0 + 1 = 2

Verfügbare Ressourcen nach Abzug der belegten Ressourcen:

• A = 3 - 2 = 1
• B = 2 - 2 = 0
• C = 2 - 2 = 0

2. Bedarf (Need) und Allokation für jeden Prozess:Bedarf = Maximum - Allokation

• P1: Need = [2 - 1, 1 - 0, 3 - 1] = [1, 1, 2]
• P2: Need = [2 – 0, 2 – 1, 1 – 0] = [2, 1, 1]
• P3: Need = [1 - 1, 1 - 1, 2 - 1]= [0, 0, 1]

3. Banker's Algorithm anwenden:

• P3: Need [0, 0, 1] kann erfüllt werden. Verfügbare Ressourcen werden aktualisiert: A = 1 + 1, B = 0 + 1, C = 0 + 1 -> Verfügbar: A = 2, B = 1, C = 1
• P1: Need [1, 1, 2] kann jetzt erfüllt werden. Verfügbare Ressourcen werden aktualisiert: A = 2 + 1, B = 1 + 0, C = 1 + 1 -> Verfügbar: A = 3, B = 1, C = 2
• P2: Need [2, 1, 1] kann jetzt erfüllt werden. Verfügbare Ressourcen werden aktualisiert: A = 3 + 0, B = 1 + 1, C = 2 + 0 -> Verfügbar: A = 3, B = 2, C = 2

Da wir eine Sequenz (P3, P1, P2) gefunden haben, in der alle Prozesse ihre maximalen Anforderungen erfüllen können, befindet sich das System in einem sicheren Zustand.Fazit:Das System befindet sich aktuell in einem sicheren Zustand gemäß dem Banker's Algorithm.

b)

Nimm an, dass ein Prozess (P4) hinzugefügt wird, der zusätzliche Ressourcen benötigt. Die maximale Anforderung des Prozesses P4 ist: A = 1, B = 1, C = 2. Beantworte die folgenden Fragen:

• Berechne, wie sich dies auf den Systemzustand auswirkt, und benutze den Banker's Algorithm, um zu bestimmen, ob das System dann noch sicher ist.
• Diskutiere zwei alternative Strategien zur Verhinderung von Deadlocks im Kontext dieses Beispiels und wie sie angewendet werden könnten, um sicherzustellen, dass keine Deadlocks entstehen.

Lösung:

Deadlock und deren Vermeidung:Ein Deadlock ist ein Zustand, bei dem mehrere Prozesse auf Ressourcen warten, die von anderen Prozessen gehalten werden, wodurch keiner der Prozesse fortfahren kann.

• Vier notwendige Bedingungen für Deadlocks: Mutual Exclusion, Hold and Wait, No Preemption, Circular Wait
• Strategien zur Deadlock-Vermeidung: Vermeidung, Verhinderung, Erkennung und Behandlung
• Vermeidungsalgorithmen: Banker's Algorithm
• Verhinderungsmethoden: Ressourcenhierarchie einhalten, keine Ressource mehrfach anfordern
• Erkennung: Ressourcen-Allokationsgraph analysieren
• Behandlung: Prozesse forcieren, Ressourcen freigeben, System neu starten

Angenommen, es wird ein neuer Prozess P4 hinzugefügt. Die maximale Anforderung des Prozesses P4 ist: A = 1, B = 1, C = 2.Beantworte die folgenden Fragen:

• Berechne, wie sich dies auf den Systemzustand auswirkt, und benutze den Banker's Algorithm, um zu bestimmen, ob das System dann noch sicher ist.
• Diskutiere zwei alternative Strategien zur Verhinderung von Deadlocks im Kontext dieses Beispiels und wie sie angewendet werden könnten, um sicherzustellen, dass keine Deadlocks entstehen.

Lösung:1. Berechne den neuen Systemzustand und benutze den Banker's Algorithm, um die Sicherheit zu prüfen:Die maximalen Anforderungen der Prozesse sind nun wie folgt:

• P1: A = 2, B = 1, C = 3
• P2: A = 2, B = 2, C = 1
• P3: A = 1, B = 1, C = 2
• P4: A = 1, B = 1, C = 2

Die aktuellen belegten Ressourcen und Verfügbarkeiten bleiben wie zuvor:

• Verfügbare Ressourcen: A = 3, B = 2, C = 2
• P1 hat: A = 1, B = 0, C = 1
• P2 hat: A = 0, B = 1, C = 0
• P3 hat: A = 1, B = 1, C = 1
• P4 hat: A = 0, B = 0, C = 0

Berechne den Bedarf (Need) für jeden Prozess:

• P1: Need = [2 - 1, 1 - 0, 3 - 1] = [1, 1, 2]
• P2: Need = [2 – 0, 2 – 1, 1 – 0] = [2, 1, 1]
• P3: Need = [1 - 1, 1 - 1, 2 - 1]= [0, 0, 1]
• P4: Need = [1 - 0, 1 - 0, 2 - 0] = [1, 1, 2]

Wende den Banker's Algorithm an:

• P3: Need [0, 0, 1] kann erfüllt werden. Verfügbare Ressourcen werden aktualisiert: A = 1 + 1, B = 0 + 1, C = 1 + 1 -> Verfügbar: A = 2, B = 1, C = 2
• Es gibt jetzt keinen Prozess, der mit den aktuellen verfügbaren Ressourcen erfüllt werden kann. Daher können wir keine sichere Sequenz finden.

Fazit: Das System befindet sich nicht in einem sicheren Zustand, da der Bedarf von P1, P2 und P4 nicht erfüllt werden kann.2. Diskutiere zwei alternative Strategien zur Verhinderung von Deadlocks:

• Strategie 1: Ressourcenhierarchie einhaltenIn dieser Strategie wird eine totale Ordnungsstruktur (hierarchische Struktur) für das Anfordern von Ressourcen eingeführt. Alle Prozesse müssen Ressourcen in einer vorab festgelegten Reihenfolge anfordern, wodurch zyklische Abhängigkeiten vermieden werden.Beispiel: Angenommen, Ressourcen werden in der Reihenfolge A, B, C angefordert, dann könnte P4 seine Anforderung in der Reihenfolge A zuerst, dann B, und schließlich C stellen, um so Deadlocks zu verhindern.
• Strategie 2: Keine Ressource mehrfach anfordernStelle sicher, dass Prozesse alle benötigten Ressourcen auf einmal anfordern. Wenn nicht alle Ressourcen gleichzeitig zur Verfügung stehen, muss der Prozess alle bereits erhaltenen Ressourcen freigeben und neu anfordern.Beispiel: P4 könnte alle Ressourcen (A=1, B=1, C=2) auf einmal anfordern. Wenn die Anforderung nicht sofort erfüllt werden kann, gibt P4 alle Ressourcen frei und versucht es später erneut. Dies reduziert die Möglichkeit von Deadlocks erheblich, da keine partiellen Zuweisungen existieren.

Aufgabe 4)

Du bist als Systemadministrator verantwortlich für die Verwaltung des Speicherplatzes eines Serversystems, das sowohl Partitionierung als auch Paging unterstützt. Die Speicherarchitektur ist darauf ausgelegt, eine optimale Balance zwischen Effizienz und Flexibilität zu bieten.

Das System nutzt eine Seitengröße von 4 KB und jede Partition hat eine variable Größe. Der gesamte physische Speicher beträgt 256 MB. Gegeben ist eine Liste laufender Prozesse mit verschiedenen Speicheranforderungen. Deine Aufgabe ist es, die Notwendigkeit und Umsetzung von Paging und Partitionierung in diesem Szenario zu analysieren.

b)

(b) Diskutiere die Vor- und Nachteile von fester und variabler Partitionierung in diesem Szenario. Berücksichtige dabei mögliche Fragmentierungsprobleme und Implementationsaufwände.

• Wie könnte Fragmentierung bei fester Partitionierung zu Problemen führen?
• Welche Vorteile bietet eine variable Partitionierung gegenüber einer festen?

Lösung:

Um die Vor- und Nachteile von fester und variabler Partitionierung zu diskutieren, betrachten wir die folgenden Aspekte im Kontext des gegebenen Serversystems:

• Feste Partitionierung:
  • Bei fester Partitionierung wird der Speicher in feste, gleichgroße Partitionen aufgeteilt.

• Vorteile von fester Partitionierung:
  • Einfachere Implementierung und Verwaltung, da die Partitionsgrößen statisch sind.
  • Geringerer Verwaltungsaufwand und weniger Overhead bei der Speicherverwaltung.
• Nachteile von fester Partitionierung:
  • Interne Fragmentierung: Wenn der Speicherbedarf eines Prozesses die Größe der festen Partition nicht vollständig ausnutzt, bleibt ungenutzter Speicher innerhalb der Partition, der als interne Fragmentierung bezeichnet wird.
  • Schlechte Speicherplatznutzung: Prozesse mit unterschiedlichem Speicherbedarf können nicht optimal in den festen Partitionen untergebracht werden, was zu einer ineffizienten Nutzung des Speichers führt.

• Variable Partitionierung:
  • Bei variabler Partitionierung wird der Speicher in Partitionen variabler Größe aufgeteilt, die an den Speicherbedarf der einzelnen Prozesse angepasst sind.

• Vorteile von variabler Partitionierung:
  • Bessere Speicherplatznutzung: Der Speicher kann an die tatsächlichen Bedürfnisse der Prozesse angepasst werden, was zu einer effizienteren Nutzung des Speichers führt.
  • Verringerung der internen Fragmentierung: Da die Partitionsgröße an den Bedarf des Prozesses angepasst werden kann, wird weniger Speicherplatz verschwendet.
• Nachteile von variabler Partitionierung:
  • Externe Fragmentierung: Im Laufe der Zeit können kleine, ungenutzte Speicherblöcke zwischen den Partitionen entstehen, was als externe Fragmentierung bezeichnet wird. Dies kann zu einer ineffizienten Nutzung des Speichers führen.
  • Komplexere Implementierung: Die Verwaltung variabler Partitionen erfordert komplexere Algorithmen zur Speicherzuweisung und -freigabe, was den Implementationsaufwand erhöht.
  • Erhöhter Verwaltungsaufwand und Overhead: Die kontinuierliche Anpassung und Verwaltung der unterschiedlich großen Partitionen erfordert mehr Ressourcen und kann den Overhead erhöhen.

• Zusammenfassung:In diesem Szenario, bei dem sowohl Partitionierung als auch Paging unterstützt werden, könnte eine variable Partitionierung flexibler und effizienter sein, um verschiedene Speicheranforderungen der laufenden Prozesse zu erfüllen. Allerdings muss man die Implementationskomplexität und die potenzielle externe Fragmentierung berücksichtigen. Feste Partitionierung bietet eine einfachere Verwaltung, kann jedoch zu einer ineffizienten Nutzung des Speichers aufgrund interner Fragmentierung führen.

c)

(c) Erkläre, wie Seitentabellen (\textit{Page Tables}) genutzt werden, um die Speicherzuteilung effizient zu organisieren. Beschreibe die Rolle von Seitentabellen, und wie sie helfen, die Fragmentierung zu minimieren.

Lösung:

Seitentabellen (\textit{Page Tables}) spielen eine zentrale Rolle in der Speicherverwaltung eines Computersystems. Sie unterstützen die effiziente Organisation und Zuteilung des Speichers und helfen dabei, Fragmentierung zu minimieren. Hier ist eine detaillierte Erklärung ihrer Funktionsweise und Vorteile:

Rolle von Seitentabellen

• Adressübersetzung: Seitentabellen dienen dazu, logische Adressen, die von Prozessen genutzt werden, in physische Adressen umzuwandeln. Dies ist ein Schlüsselmechanismus in der Speicherverwaltung, um Prozesse voneinander zu isolieren und den verfügbaren Speicher effizient zu nutzen.
• Speicherverwaltung: Eine Seitentabelle enthält Einträge, die beschreiben, wo die Daten eines Prozesses im physischen Speicher abgelegt sind. Jeder Eintrag in der Seitentabelle korrespondiert mit einer Seite im logischen Adressraum des Prozesses.

Funktionsweise von Seitentabellen

• Seitengröße: In diesem System beträgt die Seitengröße 4 KB. Der Speicherbedarf eines Prozesses wird in mehrere Seiten dieser Größe unterteilt.
• Seitenrahmen: Der physische Speicher wird in gleichgroße Seitenrahmen aufgeteilt, die dieselbe Größe wie die Seiten haben (4 KB).
• Adressumsetzung:
  • Eine logische Adresse wird in eine Seitennummer und einen Offset innerhalb dieser Seite aufgeteilt.
  • Die Seitennummer wird als Index verwendet, um die entsprechende Eintragung in der Seitentabelle zu finden.
  • Der Eintrag enthält die physische Adresse des Seitenrahmens, in dem die Seite gespeichert ist.
  • Die physische Adresse wird erstellt, indem der Offset zur Basisadresse des Seitenrahmens hinzugefügt wird.

Minimierung von Fragmentierung

• Externe Fragmentierung: Seitentabellen helfen, externe Fragmentierung zu vermeiden, weil der Speicher in kleine, feste Blöcke (Seiten) unterteilt ist, die flexibel zugewiesen werden können. Das bedeutet, dass verschiedene Prozesse ihre Seiten unabhängig voneinander an beliebigen Stellen im physischen Speicher platzieren können.
• Interne Fragmentierung: Die Verwendung von festen Seitengrößen reduziert auch die interne Fragmentierung. Da jede Seite eine feste Größe hat, bleibt weniger ungenutzter Speicher innerhalb jedes Blocks zurück, im Vergleich zu großen und variablen Speicherblöcken.

Zusammenfassung

• Seitentabellen sind ein essentielles Werkzeug für die Speicherverwaltung, da sie eine effiziente und flexible Zuordnung von Speicher ermöglichen.
• Dank der Umwandlung logischer in physische Adressen können Prozesse isoliert und Speicherplatz optimal genutzt werden.
• Die Minimierung von sowohl externer als auch interner Fragmentierung führt zu einer besseren Speicherplatzausnutzung und verringert die Verschwendung von Speicherressourcen.

d)

(d) Angenommen, ein Prozess benötigt einen Zugriff auf die virtuelle Adresse 0x1234ABCD. Wenn die Basisadresse der relevanten Seitentabelle 0x10000000 und die Seitengröße 4 KB beträgt, bestimme die physische Adresse. Zeige die Berechnungsschritte im Detail:

• Berechne die Seitennummer und den Offset für die angegebene Adresse.
• Bestimme die effektive physische Adresse unter Berücksichtigung der Basisadresse der Seitentabelle.

Lösung:

Um die physische Adresse zu bestimmen, die einem Zugriff auf die virtuelle Adresse 0x1234ABCD entspricht, folgen wir diesen Schritten:

Schritte zur Berechnung

• Seitengröße = 4 KB (4.096 Bytes)
• Virtuelle Adresse = 0x1234ABCD
• Basisadresse der relevanten Seitentabelle = 0x10000000

1. Berechnung der Seitennummer und des Offsets

• Eine Seite hat 4.096 Bytes. Daher entsprechen die unteren 12 Bits (4.096 = 2^12) der Adresse dem Offset innerhalb der Seite.Das bedeutet, dass die Seitennummer in den höheren Bits der Adresse enthalten ist und der Offset die unteren 12 Bits umfasst.
• Um den Offset zu bestimmen, betrachten wir die unteren 12 Bits der virtuellen Adresse 0x1234ABCD:0x1234ABCD = 0b0001 0010 0011 0100 1010 1011 1100 1101Die unteren 12 Bits sind 0b1010 1011 1100 1101 oder 0xABC (D volle Bytes): Daher ist der Offset = 0xBCD.
• Die Seitennummer ergibt sich aus den höheren Bits der Adresse:Virtuelle Adresse ohne die unteren 12 Bits: 0x1234A000 (die niedrigeren 12 Bits auf 0 gesetzt)
• Seitennummer = 0x1234A000 >> 12 = 0x1234A.

2. Bestimmung der effektiven physischen Adresse

• Die Basisadresse der Seitentabelle ist 0x10000000.
• Die physische Adresse kann durch Addition der Basisadresse der Seitentabelle zur entsprechenden Seitenrahmenadresse (oder Seitentabelleintrag) und dem Offset berechnet werden.
• Angenommen, der Seitentabelleneintrag für Seitennummer 0x1234A liefert die physische Seitenrahmenadresse 0x2000F000.Physische Basisadresse der Seite: 0x2000F000
• Füge den Offset zur physischen Basisadresse hinzu:Effektive physische Adresse = 0x2000F000 + 0xBCD = 0x2000FBCD

Zusammenfassung:

• Die Seitennummer für die virtuelle Adresse 0x1234ABCD beträgt 0x1234A.
• Der Offset innerhalb der Seite beträgt 0xBCD.
• Angenommen, der Seitentabelleneintrag gibt die Basisadresse der physischen Seite als 0x2000F000 an, dann ergibt sich die physische Adresse durch Addition des Offsets:Effektive physische Adresse = 0x2000FBCD.