Die präventive Version der Shortest Job First (SJF)-Planung heißt Shortest Remaining Time First (SRTF). In SRTF wird der Prozess zur Ausführung ausgewählt, dessen Fertigstellung am wenigsten verbleibt. Der laufende Prozess wird fortgesetzt, bis er abgeschlossen ist oder ein neuer Prozess mit kürzerer Restzeit eintrifft, sodass der am schnellsten abgeschlossene Prozess immer Vorrang hat.

Beispiel eines SJF-Algorithmus:

Szenario 1: Prozesse mit gleicher Ankunftszeit

Beispiel: Betrachten Sie die folgende Tabelle mit Ankunftszeiten und Burst-Zeiten für drei Prozesse P1 P2 und P3 .

Schritt-für-Schritt-Ausführung:

1. Zeit 0-5 (P3) : P3 läuft 5 ms (verbleibende Gesamtzeit: 0 ms), da die verbleibende Zeit am kürzesten ist.
2. Zeit 5-11 (P1) : P1 läuft 6 ms (verbleibende Gesamtzeit: 0 ms), da die verbleibende Zeit am kürzesten ist.
3. Zeit 11-19 (P2) : P2 läuft 8 ms (verbleibende Gesamtzeit: 0 ms), da die verbleibende Zeit am kürzesten ist.

Gantt-Diagramm:

Unterschied zwischen Binärbaum und binärem Suchbaum

Berechnen wir nun den Durchschnitt Wartezeit und umdrehen Zeit:

Wie wir wissen

• Wendezeit = Fertigstellungszeit - Ankunftszeit
• Wartezeit = Turn-around-Zeit – Burst-Zeit

Jetzt 

• Durchschnittliche Bearbeitungszeit = (11 + 19 + 5)/3 = 11,6 ms
• Durchschnittliche Wartezeit = (5 + 0 + 11)/3 = 16/3 = 5,33 ms

Szenario 2: Prozesse mit unterschiedlichen Ankunftszeiten

Betrachten Sie die folgende Tabelle mit Ankunfts- und Burst-Zeiten für drei Prozesse P1, P2 und P3.

Schritt-für-Schritt-Ausführung:

1. Zeit 0-1 (P1) : P1 läuft 1 ms (verbleibende Gesamtzeit: 5 ms), da die verbleibende Zeit am kürzesten ist.
2. Zeit 1-4 (P2) : P2 läuft 3 ms (verbleibende Gesamtzeit: 0 ms), da es von P1 und P2 die kürzeste verbleibende Zeit hat.
3. Zeit 4-9 (P1) : P1 läuft 5 ms (verbleibende Gesamtzeit: 0 ms), da es von P1 und P3 die kürzeste verbleibende Zeit hat.
4. Zeit 9-16 (P3) : P3 läuft 7 ms (verbleibende Gesamtzeit: 0 ms), da die verbleibende Zeit am kürzesten ist.

Gantt-Diagramm:

Java 8

Berechnen wir nun den Durchschnitt Wartezeit und umdrehen Zeit:

• Durchschnittliche Bearbeitungszeit = (9 + 14 + 3)/3 = 8,6 ms
• Durchschnittliche Wartezeit = (3 + 0 + 7 )/3 = 10/3 = 3,33 ms

Implementierung des SRTF-Algorithmus

Schritt 1: Geben Sie die Anzahl der Prozesse mit Ankunftszeit und Burst-Zeit ein.
Schritt 2: Verbleibende Zeiten (Burst-Zeiten) initialisieren, aktuelle Zeit = 0 und Zähler.
Schritt 3: Fügen Sie zu jeder Zeiteinheit Prozesse hinzu, die in der Bereitschaftswarteschlange angekommen sind.
Schritt 4: Wählen Sie den Prozess mit der kürzesten verbleibenden Zeit aus (bevorzugen Sie ihn, wenn ein kürzerer Prozess eintrifft).
Schritt 5: Führen Sie den ausgewählten Prozess für 1 Einheit aus, reduzieren Sie die verbleibende Zeit und erhöhen Sie die aktuelle Zeit.
Schritt 6: Wenn ein Prozess abgeschlossen ist:

• Bearbeitungszeit = Fertigstellungszeit − Ankunftszeit
• Wartezeit = Bearbeitungszeit − Burst-Zeit

Schritt 7: Wiederholen Sie die Schritte 3–6, bis alle Prozesse abgeschlossen sind.
Schritt 8: Berechnen Sie die durchschnittliche Wartezeit und Bearbeitungszeit.
Schritt 9: Zeigen Sie die Warte- und Bearbeitungszeiten für die Fertigstellung jedes Prozesses sowie Durchschnittswerte an.

Code-Implementierung

Das Programm zur Implementierung der „Shortest Remaining Time First“ lautet wie folgt:

#include    #include  #include    using namespace std; struct Process {  int id arrivalTime burstTime remainingTime waitingTime turnaroundTime completionTime; }; int main() {  int n currentTime = 0 completed = 0;  cout << 'Enter number of processes: ';  cin >> n;  vector<Process> p(n);    for (int i = 0; i < n; i++) {  p[i].id = i + 1;  cin >> p[i].arrivalTime >> p[i].burstTime;  p[i].remainingTime = p[i].burstTime;  }  while (completed < n) {  int idx = -1;  for (int i = 0; i < n; i++) {  if (p[i].arrivalTime <= currentTime && p[i].remainingTime > 0 && (idx == -1 || p[i].remainingTime < p[idx].remainingTime)) {  idx = i;  }  }  if (idx != -1) {  p[idx].remainingTime--;  currentTime++;  if (p[idx].remainingTime == 0) {  p[idx].completionTime = currentTime;  p[idx].turnaroundTime = currentTime - p[idx].arrivalTime;  p[idx].waitingTime = p[idx].turnaroundTime - p[idx].burstTime;  completed++;  }  } else {  currentTime++;  }  }  double totalWT = 0 totalTAT = 0;  for (auto &proc : p) {  totalWT += proc.waitingTime;  totalTAT += proc.turnaroundTime;  cout << 'P' << proc.id << ' CT: ' << proc.completionTime << ' WT: ' << proc.waitingTime << ' TAT: ' << proc.turnaroundTime << endl;  }  cout << 'Avg WT: ' << totalWT / n << ' Avg TAT: ' << totalTAT / n << endl; } 

import java.util.*; class Process {  int id arrivalTime burstTime remainingTime waitingTime turnaroundTime completionTime;  public Process(int id int arrivalTime int burstTime) {  this.id = id;  this.arrivalTime = arrivalTime;  this.burstTime = burstTime;  this.remainingTime = burstTime;  } } public class SRTF {  public static void main(String[] args) {  Scanner sc = new Scanner(System.in);  int n = sc.nextInt();  Process[] processes = new Process[n];    for (int i = 0; i < n; i++) {  int arrivalTime = sc.nextInt() burstTime = sc.nextInt();  processes[i] = new Process(i + 1 arrivalTime burstTime);  }  Arrays.sort(processes Comparator.comparingInt(p -> p.arrivalTime));  int currentTime = 0 completed = 0;  while (completed < n) {  int idx = -1;  for (int i = 0; i < n; i++) {  if (processes[i].arrivalTime <= currentTime && processes[i].remainingTime > 0 && (idx == -1 || processes[i].remainingTime < processes[idx].remainingTime)) {  idx = i;  }  }  if (idx != -1) {  processes[idx].remainingTime--;  currentTime++;  if (processes[idx].remainingTime == 0) {  processes[idx].completionTime = currentTime;  processes[idx].turnaroundTime = currentTime - processes[idx].arrivalTime;  processes[idx].waitingTime = processes[idx].turnaroundTime - processes[idx].burstTime;  completed++;  }  } else {  currentTime++;  }  }  double totalWT = 0 totalTAT = 0;  for (Process p : processes) {  totalWT += p.waitingTime;  totalTAT += p.turnaroundTime;  System.out.println('P' + p.id + ' CT: ' + p.completionTime + ' WT: ' + p.waitingTime + ' TAT: ' + p.turnaroundTime);  }  System.out.println('Avg WT: ' + totalWT / n + ' Avg TAT: ' + totalTAT / n);  } } 

class Process: def __init__(self id arrival_time burst_time): self.id = id self.arrival_time = arrival_time self.burst_time = burst_time self.remaining_time = burst_time def srtf(processes): current_time completed = 0 0 while completed < len(processes): idx = -1 for i p in enumerate(processes): if p.arrival_time <= current_time and p.remaining_time > 0 and (idx == -1 or p.remaining_time < processes[idx].remaining_time): idx = i if idx != -1: processes[idx].remaining_time -= 1 current_time += 1 if processes[idx].remaining_time == 0: processes[idx].completion_time = current_time processes[idx].turnaround_time = current_time - processes[idx].arrival_time processes[idx].waiting_time = processes[idx].turnaround_time - processes[idx].burst_time completed += 1 else: current_time += 1 def print_results(processes): total_wt total_tat = 0 0 for p in processes: total_wt += p.waiting_time total_tat += p.turnaround_time print(f'P{p.id} CT: {p.completion_time} WT: {p.waiting_time} TAT: {p.turnaround_time}') print(f'Avg WT: {total_wt / len(processes)} Avg TAT: {total_tat / len(processes)}') n = int(input('Enter number of processes: ')) processes = [Process(i + 1 *map(int input(f'Enter arrival and burst time for P{i + 1}: ').split())) for i in range(n)] srtf(processes) print_results(processes) 

Enter number of processes: Avg WT: -nan Avg TAT: -nan 

Vorteile von SRTF Terminplanung

1. Minimiert die durchschnittliche Wartezeit : SRTF reduziert die durchschnittliche Wartezeit, indem es Prozesse mit der kürzesten verbleibenden Ausführungszeit priorisiert.
2. Effizient für kurze Prozesse : Kürzere Prozesse werden schneller abgeschlossen, wodurch die Reaktionsfähigkeit des Gesamtsystems verbessert wird.
3. Ideal für zeitkritische Systeme : Es stellt sicher, dass zeitkritische Prozesse schnell ausgeführt werden.

Nachteile von SRTF Terminplanung

1. Aushungern langer Prozesse : Längere Prozesse können sich auf unbestimmte Zeit verzögern, wenn immer wieder kürzere Prozesse eintreffen.
2. Es ist schwierig, Burst-Zeiten vorherzusagen : Die genaue Vorhersage von Prozessauslastungszeiten ist eine Herausforderung und beeinflusst Planungsentscheidungen.
3. Hoher Overhead : Häufiger Kontextwechsel kann den Overhead erhöhen und die Systemleistung verlangsamen.
4. Nicht für Echtzeitsysteme geeignet : Bei Echtzeitaufgaben kann es aufgrund häufiger Vorbelegungen zu Verzögerungen kommen.