Verlässliche Echtzeitsysteme - Exam

Aufgabe 2)

Du bist für die Planung eines sicherheitskritischen Echtzeitsystemes verantwortlich, das auf deterministischen Kommunikationsprotokollen beruht. Um ein vorhersehbares Verhalten und garantierte Kommunikationszeiten zu erreichen, sollen keine Kollisionen im Netzwerkverkehr auftreten. TDMA (Time Division Multiple Access) wird als Kommunikationsprotokoll verwendet. Dieses Protokoll teilt die Gesamtzeit in mehrere Zeitschlitze auf, die im festen Rhythmus durch die Teilnehmer des Netzwerks genutzt werden. Die Formel zur Berechnung der Zykluszeit lautet Z = \frac{T}{N}, wobei T die Gesamtzeit und N die Anzahl der Zeitschlitze ist.

a)

a) Angenommen, die Gesamtzeit eines Zyklus in Deinem System beträgt 10 ms, und es gibt 5 Zeitschlitze. Berechne die Zykluszeit Z für einen Teilnehmer.

Lösung:

a) Angenommen, die Gesamtzeit eines Zyklus in Deinem System beträgt 10 ms, und es gibt 5 Zeitschlitze. Berechne die Zykluszeit Z für einen Teilnehmer.

• Die Gesamtzeit, T, beträgt 10 ms.
• Die Anzahl der Zeitschlitze, N, beträgt 5.

Die Zykluszeit Z wird mit der folgenden Formel berechnet:

• \[ Z = \frac{T}{N} \]

Setze die gegebenen Werte in die Formel ein:

• \[ Z = \frac{10 \; \text{ms}}{5} \]

Führe die Division durch:

• \[ Z = 2 \; \text{ms} \]

Die Zykluszeit Z für einen Teilnehmer beträgt somit 2 ms.

b)

b) Erkläre, wie das TDMA-Protokoll sicherstellt, dass keine Kollisionen im Netzwerkverkehr auftreten. Gehe dabei insbesondere auf die Aufteilung der Zeit in Zeitschlitze ein und wie diese verwaltet werden.

Lösung:

b) Erkläre, wie das TDMA-Protokoll sicherstellt, dass keine Kollisionen im Netzwerkverkehr auftreten. Gehe dabei insbesondere auf die Aufteilung der Zeit in Zeitschlitze ein und wie diese verwaltet werden.

Das TDMA (Time Division Multiple Access) Protokoll stellt sicher, dass keine Kollisionen im Netzwerkverkehr auftreten, indem es die gesamte Kommunikationszeit in feste Zeitschlitze unterteilt. Hier wird erklärt, wie dies funktioniert:

• Zeitschlitze: Die Gesamtzeit T wird in mehrere gleich lange Zeitschlitze aufgeteilt. Jeder Zeitschlitz wird einem bestimmten Netzwerkteilnehmer zugewiesen. Ein Teilnehmer darf nur innerhalb seines zugewiesenen Zeitschlitzes kommunizieren.
• Fester Rhythmus: Diese Zeitschlitze wiederholen sich in einem festen Rhythmus. Zum Beispiel, wenn es 5 Zeitschlitze gibt und die Gesamtzeit 10 ms beträgt, erhält jeder Teilnehmer einen 2 ms langen Zeitschlitz.\[ Z = \frac{T}{N} = \frac{10 \, \text{ms}}{5} = 2 \, \text{ms} \]
• Zuweisung von Zeitschlitzen: Jeder Teilnehmer im Netzwerk hat einen bestimmten Zeitschlitz, in dem er senden darf. Dies verhindert, dass zwei Teilnehmer gleichzeitig senden und eine Kollision verursachen. Die Zuweisung bleibt konstant und wiederholt sich im festen Intervall des Kommunikationszyklus.
• Verwaltung der Zeitschlitze: In einem TDMA-System gibt es eine zentrale Instanz oder einen Koordinator, der die Zeitschlitze verwaltet und sicherstellt, dass jeder Teilnehmer weiß, wann er senden darf. Diese zentrale Instanz könnte ein lokales Zeitmanagementsystem oder ein externer Taktgeber sein, der die Synchronisation der Zeitschlitze sicherstellt.

Zusammenfassend stellt TDMA sicher, dass keine Kollisionen im Netzwerkverkehr auftreten, indem es die Kommunikation zeitlich in exklusive Zeitschlitze aufteilt, die von den Teilnehmern im festen und synchronisierten Rhythmus genutzt werden.

c)

c) Gegeben sei ein System, bei dem die Durchsatzanforderungen gestiegen sind, sodass zusätzliche Zeitschlitze benötigt werden. Die neue Zahl der Zeitschlitze ist nun 8, bei gleichbleibender Gesamtzeit T. Berechne die neue Zykluszeit und diskutiere, welche Auswirkungen dies auf die Latenz der einzelnen Teilnehmer hat.

Lösung:

c) Gegeben sei ein System, bei dem die Durchsatzanforderungen gestiegen sind, sodass zusätzliche Zeitschlitze benötigt werden. Die neue Zahl der Zeitschlitze ist nun 8, bei gleichbleibender Gesamtzeit T. Berechne die neue Zykluszeit und diskutiere, welche Auswirkungen dies auf die Latenz der einzelnen Teilnehmer hat.

• Die ursprüngliche Gesamtzeit, T, bleibt 10 ms.
• Die neue Anzahl der Zeitschlitze, N, beträgt nun 8.

Berechnen wir die neue Zykluszeit Z:

• \[ Z = \frac{T}{N} \]
• Setze die neuen Werte in die Formel ein:
• \[ Z = \frac{10 \; \text{ms}}{8} \]
• Führe die Division durch:
• \[ Z = 1,25 \; \text{ms} \]

Die neue Zykluszeit Z beträgt also 1,25 ms.

Diskussion der Auswirkungen auf die Latenz:

• Mit der Erhöhung der Anzahl der Zeitschlitze von 5 auf 8 wird jeder Zeitschlitz kürzer. Ursprünglich hatte jeder Teilnehmer 2 ms pro Zeitschlitz, jetzt sind es nur noch 1,25 ms pro Zeitschlitz.
• Reduzierte Latenz: Die kürzere Zykluszeit bedeutet, dass die Daten häufiger pro Zeiteinheit gesendet werden können. Dies kann die Latenz reduzieren, denn die Wartezeit, bis ein Teilnehmer an der Reihe ist, verringert sich.
• Erhöhter Durchsatz: Die Reduktion der Zykluszeit ermöglicht es, dass mehr Datenpakete innerhalb eines bestimmten Zeitraums gesendet werden können, was den Gesamtdurchsatz des Systems erhöht.
• Möglicher Ressourcenbedarf: Jedoch könnte die Zunahme der Anzahl der Zeitschlitze auch den Bedarf an einer effizienteren Taktverwaltung erhöhen, um sicherzustellen, dass die Zeitsynchronisation zwischen den Teilnehmern korrekt bleibt.

Zusammenfassend führt die Erhöhung der Anzahl der Zeitschlitze bei gleichbleibender Gesamtzeit zu einer verkürzten Zykluszeit von 1,25 ms, was die Latenz reduziert und den Durchsatz des Systems erhöht.

d)

d) Diskutiere die Vor- und Nachteile von TDMA gegenüber anderen deterministischen Kommunikationsprotokollen wie TTP (Time-Triggered Protocol) und FlexRay. Gehe dabei auf Aspekte wie Vorhersagbare Latenz, Durchsatz und Anwendungsszenarien ein.

Lösung:

d) Diskutiere die Vor- und Nachteile von TDMA gegenüber anderen deterministischen Kommunikationsprotokollen wie TTP (Time-Triggered Protocol) und FlexRay. Gehe dabei auf Aspekte wie vorhersagbare Latenz, Durchsatz und Anwendungsszenarien ein.

Vor- und Nachteile von TDMA:

• Vorhersagbare Latenz: TDMA bietet eine sehr gute Vorhersagbarkeit der Latenz, da jeder Teilnehmer einen fest zugewiesenen Zeitschlitz innerhalb eines wiederkehrenden Zyklus hat. Dies bedeutet, dass die Latenzzeiten zuvor genau berechnet werden können.
• Durchsatz: Der Durchsatz des TDMA-Protokolls ist begrenzt durch die Anzahl der Zeitschlitze und deren Länge. Da jeder Teilnehmer nur in seinem zugewiesenen Zeitschlitz senden kann, könnte der Durchsatz für Systeme mit hohen Anforderungen an den Datenaustausch eingeschränkt sein.
• Anwendungsszenarien: TDMA eignet sich hervorragend für sicherheitskritische Echtzeitsysteme, in denen vorhersagbare Kommunikationszeiten entscheidend sind, wie in der Luft- und Raumfahrt sowie in industriellen Automatisierungsanwendungen.

Vergleich mit TTP (Time-Triggered Protocol):

• Vorhersagbare Latenz: Ähnlich wie TDMA bietet auch TTP eine sehr gute Vorhersagbarkeit der Latenz mit festgelegten Zeitfenstern für die Kommunikation. TTP geht jedoch noch einen Schritt weiter, indem es zusätzliche Mechanismen für Fehlertoleranz und Systemrobustheit integriert.
• Durchsatz: TTP bietet einen vergleichbaren Durchsatz wie TDMA, ist jedoch durch seine zusätzlichen sicherheitsrelevanten Mechanismen möglicherweise nicht so effizient im Datendurchsatz wie andere Protokolle.
• Anwendungsszenarien: TTP ist besonders geeignet für hochzuverlässige und sicherheitskritische Systeme wie in der Luftfahrt, der Automobilindustrie und der Raumfahrt, wo Fehlertoleranz und Systemintegrität entscheidend sind.

Vergleich mit FlexRay:

• Vorhersagbare Latenz: FlexRay kombiniert statische und dynamische Zeitschlitze, wodurch es sowohl vorhersagbare als auch flexible Zeitfenster zur Verfügung stellen kann. Dies verbessert die Latenzvorhersagbarkeit im Vergleich zu nicht-deterministischen Protokollen erheblich.
• Durchsatz: FlexRay bietet einen wesentlich höheren Datendurchsatz als TDMA und TTP durch die Verwendung von dynamischen Zeitschlitzen und höheren Bitraten. FlexRay arbeitet typischerweise mit Datenraten von bis zu 10 Mbit/s.
• Anwendungsszenarien: FlexRay findet breite Anwendung in der Automobilindustrie, insbesondere in Systemen, die sowohl hohe Datenraten als auch strenge Echtzeitanforderungen kombinieren, wie bei der Fahrzeugsteuerung und in Fahrzeugsicherheitssystemen.

Zusammenfassung: Jedes dieser Protokolle hat seine spezifischen Stärken und Schwächen. TDMA bietet eine einfache, aber effektive Lösung für vorhersagbare Latenzzeiten, während TTP durch zusätzliche Mechanismen für Sicherheit und Fehlertoleranz punktet. FlexRay bietet den höchsten Datendurchsatz und eine Mischung aus festen und flexiblen Zeitfenstern und eignet sich daher besonders für komplexe und datenintensive Systeme. Die Wahl des geeigneten Protokolls hängt letztlich von den spezifischen Anforderungen des jeweiligen Anwendungsszenarios ab.

Aufgabe 3)

Ein autonomes Fahrzeug verwendet Techniken zur Sicherstellung der Systemzuverlässigkeit, wie Fehlertoleranz und Erholungsmethoden, um auch bei Fehlern sicher zu funktionieren. Das Fahrzeug implementiert Redundanz durch doppelte Steuerungskomponenten, Diversität durch verschiedene Navigationsalgorithmen, Checkpointing durch regelmäßige Speicherung des Fahrzeugzustands, Rollback Recovery um zu einem vorherigen sicheren Zustand zurückzukehren, Replikation indem mehrere Steuerungssysteme gleichzeitig laufen und Mehrheitsentscheid indem es die Ergebnisse dieser Systeme miteinander vergleicht.

a)

Erkläre, wie das autonome Fahrzeug Checkpointing und Rollback Recovery nutzt, um nach einem Fehlverhalten den Betrieb wiederherzustellen. Welche Herausforderungen könnten dabei auftreten, insbesondere in einem Echtzeitsystem?

Lösung:

Checkpointing und Rollback Recovery im autonomen Fahrzeug

Checkpointing und Rollback Recovery sind essenziell für die Gewährleistung der Systemzuverlässigkeit in autonomen Fahrzeugen. Hier ist, wie sie funktionieren:

• Checkpointing: Regelmäßig speichert das Fahrzeug seinen aktuellen Zustand auf einem stabilen Speichermedium ab. Diese Zustände beinhalten Informationen über die Position, Geschwindigkeit, Systemparameter und andere relevante Daten. Falls ein Fehler auftritt, kann das Fahrzeug zu einem dieser gespeicherten Zustände zurückkehren und den Betrieb von dort aus fortsetzen.
• Rollback Recovery: Wenn ein Fehlverhalten erkannt wird, analysiert das System die Art des Fehlers und entscheidet, welcher gespeicherte Checkpoint am besten geeignet ist, um den Fehler zu umgehen. Es wird dann zu diesem Checkpoint zurückgekehrt, und das System setzt den Betrieb von dort aus fort. Dies minimiert die Störung und die Ausfallzeit.

Herausforderungen in einem Echtzeitsystem

Die Implementierung von Checkpointing und Rollback Recovery in einem autonomen Fahrzeug, insbesondere in einem Echtzeitsystem, bringt einige Herausforderungen mit sich:

• Speicher-und Leistungsoverhead: Das häufige Speichern von Checkpoints verbraucht erhebliche Systemressourcen. Das Management des Speichers und die Geschwindigkeit der Speicherung müssen optimiert werden, um die Systemleistung nicht zu beeinträchtigen.
• Bestimmung des optimalen Zeitpunkts für Checkpoints: Die Intervalle, in denen Checkpoints gesetzt werden, müssen sorgfältig gewählt werden. Zu seltene Checkpoints könnten dazu führen, dass im Fehlerfall zu viel an Arbeit verloren geht, während zu häufige Checkpoints die Systemressourcen belasten.
• Unterbrechungsfreier Betrieb: In einem Echtzeitsystem dürfen Checkpointing- und Rollback-Vorgänge den kontinuierlichen Betrieb des Fahrzeugs nicht stören. Echtzeit-Anforderungen machen es erforderlich, dass diese Vorgänge schnell und effizient sind.
• Koordination und Konsistenz: Alle Teile des Systems müssen bei einem Rollback in einem konsistenten Zustand zurückgesetzt werden. Dies erfordert präzise Koordination, um sicherzustellen, dass keine Inkonsistenzen auftreten, die zu weiteren Fehlern führen könnten.
• Fehlererkennung und Diagnose: Schnell und präzise Fehler zu erkennen und den geeigneten Checkpoint für das Rollback zu bestimmen, ist entscheidend. Falsche Diagnosen können dazu führen, dass das System nicht ordnungsgemäß wiederhergestellt wird.

Die effektive Nutzung von Checkpointing und Rollback Recovery erfordert daher sorgfältige Planung und fortschrittliche Techniken, um die genannten Herausforderungen zu meistern und die Verlässlichkeit des autonomen Fahrzeugs sicherzustellen.

b)

Betrachte die Situation, in der das Fahrzeug wegen eines Hardwareschadens in der Lenkung von den redundanten Steuerungskomponenten abhängig wird. Welche Rolle spielt der Mehrheitsentscheid in diesem Szenario, und wie kann die Diversität der Algorithmen die Systemzuverlässigkeit erhöhen? Diskutiere die Vor- und Nachteile dieser Techniken im gegebenen Kontext.

Lösung:

Die Rolle des Mehrheitsentscheids und die Diversität der Algorithmen im autonomen Fahrzeug

Ein autonomes Fahrzeug, das aufgrund eines Hardwareschadens in der Lenkung auf redundante Steuerungskomponenten angewiesen ist, nutzt mehrere Techniken, um die Systemzuverlässigkeit sicherzustellen. Zwei dieser Techniken sind der Mehrheitsentscheid und die Diversität der Algorithmen.

Mehrheitsentscheid:

• Beim Mehrheitsentscheid laufen mehrere Steuerungssysteme gleichzeitig, die unabhängig voneinander Entscheidungen treffen. Diese Entscheidungen werden dann verglichen, und jene Entscheidung, die von der Mehrheit der Systeme getroffen wurde, wird als die korrekte betrachtet.
• Im Kontext des Hardwareschadens an der Lenkung können diese redundanten Steuerungssysteme die Lenkbefehle überwachen und sicherstellen, dass die Lenkung auch weiterhin korrekt funktioniert, selbst wenn eine Komponente ausfällt.
• Der Mehrheitsentscheid bietet eine höhere Zuverlässigkeit, da er fehlerhafte oder abweichende Daten von einer Minderheit der Systeme ignoriert. Dadurch wird das Risiko, dass ein Fehler in einem einzelnen System das Gesamtsystem beeinflusst, erheblich reduziert.

Diversität der Algorithmen:

• Die Diversität der Algorithmen bedeutet, dass unterschiedliche Navigations- und Kontrollalgorithmen verwendet werden, um die gleichen Aufgaben auszuführen. Dies verringert die Wahrscheinlichkeit, dass ein gemeinsamer Fehler oder ein Bug in einem Algorithmus das gesamte System beeinträchtigt.
• Im Falle eines Hardwareschadens an der Lenkung können verschiedene Algorithmen die Situation unterschiedlich interpretieren und somit mehrere Lösungsvorschläge bieten. Dies erhöht die Wahrscheinlichkeit, dass zumindest einer der Algorithmen eine korrekte und funktionierende Lösung bereitstellt.
• Die Diversität der Algorithmen hilft, systematische Fehler zu vermeiden, da verschiedene Ansätze unterschiedliche Fehlertoleranzmethoden beinhalten können.

Vorteile dieser Techniken:

• Erhöhte Zuverlässigkeit: Durch redundante Systeme und Mehrheitsentscheid kann die Zuverlässigkeit verbessert werden, da das Gesamtsystem nicht von einem einzigen Punkt abhängig ist.
• Fehlerresistenz: Durch die Diversität der Algorithmen kann das System besser auf unterschiedliche Fehlerarten reagieren und ist widerstandsfähiger gegenüber Softwarefehlern.
• Kontinuierlicher Betrieb: Wenn ein System ausfällt, können die anderen Systeme weiterhin korrekt arbeiten, was zu weniger Ausfallzeiten führt.

Nachteile dieser Techniken:

• Komplexität: Die Implementierung von Mehrheitsentscheid und diversifizierten Algorithmen erfordert ein komplexeres Systemdesign, was die Entwicklung und Wartung erschwert.
• Ressourcenverbrauch: Redundante Systeme und multiple Algorithmen benötigen mehr Rechenleistung und Speicher, was die Kosten und den Energieverbrauch erhöhen kann.
• Koordination: Es erfordert eine präzise Koordination zwischen den verschiedenen Systemen und Algorithmen, um sicherzustellen, dass sie effizient zusammenarbeiten und keine Inkonsistenzen auftreten.

Insgesamt tragen der Mehrheitsentscheid und die Diversität der Algorithmen wesentlich zur Zuverlässigkeit und Sicherheit eines autonomen Fahrzeugs bei. Trotz der höheren Komplexität und des höheren Ressourcenbedarfs bieten sie erhebliche Vorteile im Umgang mit Hardware- und Softwarefehlern.

Aufgabe 4)

Du bist verantwortlich für die Implementierung eines Echtzeitsystems, das mehrere Aufgaben verwaltet und eine effiziente Nutzung der Prozessorzeit gewährleistet. Die Aufgaben haben unterschiedliche Ankunftszeiten, Ausführungszeiten und Prioritäten. Die Auswahl des geeigneten Scheduling-Algorithmus ist von entscheidender Bedeutung, um die Systemanforderungen zu erfüllen. Du wurdest beauftragt, die Implementierung und Analyse verschiedener Scheduling-Algorithmen vorzunehmen.

a)

Implementiere den First-Come, First-Served (FCFS) Scheduling-Algorithmus in einer Programmiersprache deiner Wahl. Dein Programm sollte folgendes leisten:

• Empfange eine Liste von Aufgaben mit Ankunftszeiten und Ausführungszeiten.
• Simuliere die Ausführung der Aufgaben nach dem FCFS-Algorithmus.
• Gib die Reihenfolge der Aufgaben aus sowie die Start- und Endzeiten jeder Aufgabe.

tasks = [{'arrival_time': 0, 'execution_time': 4}, {'arrival_time': 2, 'execution_time': 3}, {'arrival_time': 5, 'execution_time': 2}]

Lösung:

Um den First-Come, First-Served (FCFS) Scheduling-Algorithmus zu implementieren, verwenden wir Python. Der FCFS-Algorithmus funktioniert nach dem Prinzip, dass die Aufgaben in der Reihenfolge ausgeführt werden, in der sie ankommen. Hier sind die Schritte, um eine solche Simulation zu erstellen:

• Erhalte die Liste der Aufgaben mit ihren Ankunftszeiten und Ausführungszeiten.
• Sortiere die Aufgaben basierend auf ihren Ankunftszeiten.
• Simuliere die Ausführung der Aufgaben und berechne die Start- und Endzeiten für jede Aufgabe.
• Gib die Reihenfolge der Aufgaben sowie die Start- und Endzeiten jeder Aufgabe aus.

 tasks = [{'arrival_time': 0, 'execution_time': 4}, {'arrival_time': 2, 'execution_time': 3}, {'arrival_time': 5, 'execution_time': 2}]  def fcfs_scheduling(tasks):    # Sortieren der Aufgaben nach Ankunftszeit     tasks.sort(key=lambda x: x['arrival_time'])      current_time = 0     schedule = []     for task in tasks:         if current_time < task['arrival_time']:             current_time = task['arrival_time']           start_time = current_time         end_time = start_time + task['execution_time']     schedule.append({'start_time': start_time, 'end_time': end_time})         current_time = end_time     return schedule tasks = [{'arrival_time': 0, 'execution_time': 4}, {'arrival_time': 2, 'execution_time': 3}, {'arrival_time': 5, 'execution_time': 2}] schedule = fcfs_scheduling(tasks) for idx, task in enumerate(schedule):     print(f'Task {idx + 1}: Start Time = {task['start_time']}, End Time = {task['end_time']}')  

In diesem Beispiel werden die Aufgaben basierend auf ihrer Ankunftszeit sortiert und dann in der Reihenfolge ausgeführt, in der sie ankommen. Beginn- und Endzeiten der Aufgaben werden berechnet und in einer Liste gespeichert, die dann ausgegeben wird.

b)

Analysiere die Leistung des FCFS-Algorithmus anhand der folgenden Punkte:

• Berechne die durchschnittliche Wartezeit und die durchschnittliche Turnaround-Zeit für die Aufgaben in deinem Beispiel.
• Vergleiche diese Werte mit denen, die du mit dem Shortest Job Next (SJN) Algorithmus erhalten würdest, und überprüfe, ob der SJN-Algorithmus die Wartezeit tatsächlich minimiert. Gehe dabei davon aus, dass die Aufgaben in der Liste gleich bleiben.

Formeln zur Berechnung:
• \textbf{Wartezeit}: Die Zeit, die eine Aufgabe im Wartezustand verbringt, bevor sie ausgeführt wird. Berechnung: \texttt{Wartezeit[i] = Startzeit[i] - Ankunftszeit[i]}
• \textbf{Turnaround-Zeit}: Die Gesamtlaufzeit einer Aufgabe vom Ankunfts- bis zum Abschlusszeitpunkt. Berechnung: \texttt{Turnaround-Zeit[i] = Endzeit[i] - Ankunftszeit[i]}
• Öffne und schließe mathematische Formeln/Euqations mit Klammern

Lösung:

Analyse der Leistung des FCFS-Algorithmus

Wir werden die Leistung des FCFS-Algorithmus anhand der folgenden Punkte analysieren:

• Berechnung der durchschnittlichen Wartezeit
• Berechnung der durchschnittlichen Turnaround-Zeit
• Vergleich dieser Werte mit denen des Shortest Job Next (SJN) Algorithmus

Formeln zur Berechnung:

• Wartezeit: Die Zeit, die eine Aufgabe im Wartezustand verbringt, bevor sie ausgeführt wird. Berechnung: Wartezeit[i] = Startzeit[i] - Ankunftszeit[i]
• Turnaround-Zeit: Die Gesamtlaufzeit einer Aufgabe vom Ankunfts- bis zum Abschlusszeitpunkt. Berechnung: Turnaround-Zeit[i] = Endzeit[i] - Ankunftszeit[i]

Implementierung des FCFS-Algorithmus in Python:

 tasks = [    {'arrival_time': 0, 'execution_time': 4},     {'arrival_time': 2, 'execution_time': 3},     {'arrival_time': 5, 'execution_time': 2} ]   def fcfs_scheduling(tasks):    tasks.sort(key=lambda x: x'arrival_time')    current_time = 0    waiting_times = []    turnaround_times = []    schedule = []     for task in tasks:        if current_time < task['arrival_time']:            current_time = task['arrival_time']         start_time = current_time        end_time = start_time + task['execution_time']        schedule.append({'start_time': start_time, 'end_time': end_time})        waiting_times.append(start_time - task['arrival_time'])        turnaround_times.append(end_time - task['arrival_time'])        current_time = end_time     avg_waiting_time = sum(waiting_times) / len(waiting_times)    avg_turnaround_time = sum(turnaround_times) / len(turnaround_times)    return schedule, avg_waiting_time, avg_turnaround_timeschedule, avg_waiting_time, avg_turnaround_time = fcfs_scheduling(tasks) print(f'FCFS - Durchschnittliche Wartezeit: {avg_waiting_time}') print(f'FCFS - Durchschnittliche Turnaround-Zeit: {avg_turnaround_time}') for idx, task in enumerate(schedule):    print(f'Task {idx + 1}: Start Time = {task['start_time']}, End Time = {task['end_time']}')  

Vergleich mit dem Shortest Job Next (SJN) Algorithmus:

Implementierung des SJN-Algorithmus in Python:

  def sjn_scheduling(tasks):    tasks.sort(key=lambda x: (x['arrival_time'], x['execution_time']))     current_time = 0    waiting_times = []    turnaround_times = []    schedule = []     for task in tasks:        if current_time < task['arrival_time']:            current_time = task['arrival_time']        start_time = current_time        end_time = start_time + task['execution_time']        schedule.append({'start_time': start_time, 'end_time': end_time})        waiting_times.append(start_time - task['arrival_time'])        turnaround_times.append(end_time - task['arrival_time'])        current_time = end_time     avg_waiting_time = sum(waiting_times) / len(waiting_times)    avg_turnaround_time = sum(turnaround_times) / len(turnaround_times)    return schedule, avg_waiting_time, avg_turnaround_timeschedule, avg_waiting_time, avg_turnaround_time = sjn_scheduling(tasks) print(f'SJN - Durchschnittliche Wartezeit: {avg_waiting_time}') print(f'SJN - Durchschnittliche Turnaround-Zeit: {avg_turnaround_time}') for idx, task in enumerate(schedule):    print(f'Task {idx + 1}: Start Time = {task['start_time']}, End Time = {task['end_time']}')  

Ergebnisse:

• FCFS - Durchschnittliche Wartezeit:
• FCFS - Durchschnittliche Turnaround-Zeit:
• SJN - Durchschnittliche Wartezeit:
• SJN - Durchschnittliche Turnaround-Zeit:

Wie wir sehen können, wird durch den SJN-Algorithmus die Wartezeit minimiert, indem die kürzesten Aufgaben zuerst ausgeführt werden.