A legrövidebb munka elsőként (SJF) ütemezés megelőző verziója a legrövidebb hátralévő idő először (SRTF). Az SRTF-ben az a folyamat van kiválasztva, amelynek a legkevesebb ideje van a befejezéshez. A futási folyamat addig folytatódik, amíg be nem fejeződik, vagy egy új folyamat rövidebb hátralévő idővel érkezik, így mindig a leggyorsabb befejezési folyamat élvez prioritást.

Példa az SJF algoritmusra:

1. forgatókönyv: Folyamatok azonos érkezési idővel

Példa: Tekintsük a következő táblázatot az érkezési időről és a sorozatfelvételi időről három folyamathoz P1 P2 és P3 .

Lépésről lépésre történő végrehajtás:

1. Idő 0-5 (P3) : A P3 5 ms-ig fut (teljes hátralévő idő: 0 ms), mivel a legrövidebb hátralévő ideje van hátra.
2. Idő 5-11 (P1) : A P1 6 ms-ig fut (teljes hátralévő idő: 0 ms), mivel a legrövidebb hátralévő ideje van hátra.
3. Időpont 11-19 (P2) : A P2 8 ms-ig fut (teljes hátralévő idő: 0 ms), mivel a legrövidebb hátralévő ideje van hátra.

Gantt diagram:

youtube videó mentése vlc

Most számoljuk ki az átlagot várakozási idő és forduljon meg idő:

Mint tudjuk

• Fordulási idő = Befejezési idő – érkezési idő
• Várakozási idő = Fordulási idő – sorozatfelvételi idő

Jelenleg 

java keverés int

• Átlagos fordulási idő = (11 + 19 + 5)/3 = 11,6 ms
• Átlagos várakozási idő = (5 + 0 + 11 )/3 = 16/3 = 5,33 ms

2. forgatókönyv: Eltérő érkezési időpontú folyamatok

Tekintsük a következő táblázatot a három P1 P2 és P3 folyamat érkezési idejéről és sorozatfelvételi idejéről.

Lépésről lépésre történő végrehajtás:

1. Idő 0-1 (P1) : A P1 1 ms-ig fut (teljes hátralévő idő: 5 ms), mivel a legrövidebb hátralévő ideje van.
2. 1-4. idő (P2) : A P2 3 ms-ig fut (teljes hátralévő idő: 0 ms), mivel a P1 és P2 közül a legrövidebb hátralévő ideje van hátra.
3. Idő 4-9 (P1) : A P1 5 ms-ig fut (teljes hátralévő idő: 0 ms), mivel a P1 és P3 közül a legrövidebb hátralévő ideje van hátra.
4. Időpont 9-16 (P3) : A P3 7 ms-ig fut (teljes hátralévő idő: 0 ms), mivel a legrövidebb hátralévő ideje van hátra.

Gantt diagram:

Most számoljuk ki az átlagot várakozási idő és forduljon meg idő:

• Átlagos fordulási idő = (9 + 14 + 3)/3 = 8,6 ms
• Átlagos várakozási idő = (3 + 0 + 7)/3 = 10/3 = 3,33 ms

SRTF algoritmus megvalósítása

1. lépés: Adja meg a folyamatok számát érkezési és sorozatfelvételi idővel.
2. lépés: A hátralévő idők inicializálása (sorozatfelvételi idők), aktuális idő = 0 és számlálók.
3. lépés: Minden egyes időpontban adja hozzá a megérkezett folyamatokat a készenléti sorhoz.
4. lépés: Válassza ki a legrövidebb hátralévő idővel rendelkező folyamatot (ha rövidebb érkezik, előzze meg).
5. lépés: Végezze el a kiválasztott folyamatot 1 egységig, csökkentse a hátralévő időt és növelje az aktuális időt.
6. lépés: Ha egy folyamat befejeződik:

• Átfutási idő = Befejezési idő − Megérkezési idő
• Várakozási idő = átfutási idő − sorozatfelvételi idő

7. lépés: Ismételje meg a 3–6. lépéseket, amíg az összes folyamat be nem fejeződik.
8. lépés: Számítsa ki az átlagos várakozási időt és az átfutási időt.
9. lépés: Megjeleníti az egyes folyamatok befejezési várakozási és átfutási idejét az átlagokkal együtt.

Kód végrehajtása

A legrövidebb hátralévő idő első végrehajtásának programja a következő:

#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 

Az SRTF előnyei Ütemezés

1. Minimálisra csökkenti az átlagos várakozási időt : Az SRTF csökkenti az átlagos várakozási időt azáltal, hogy előnyben részesíti a legrövidebb hátralévő végrehajtási idővel rendelkező folyamatokat.
2. Hatékony rövid folyamatokhoz : A rövidebb folyamatok gyorsabban fejeződnek be, javítva a rendszer általános válaszkészségét.
3. Ideális időkritikus rendszerekhez : Biztosítja az időérzékeny folyamatok gyors végrehajtását.

Az SRTF hátrányai Ütemezés

1. Hosszú folyamatok éhezése : A hosszabb folyamatok határozatlan időre késlekedhetnek, ha folyamatosan érkeznek rövidebb folyamatok.
2. Nehéz megjósolni a sorozatfelvételi időt : A folyamat sorozatos idők pontos előrejelzése kihívást jelent, és befolyásolja az ütemezési döntéseket.
3. Magas rezsi : A gyakori környezetváltás növelheti a többletköltséget és lelassíthatja a rendszer teljesítményét.
4. Nem alkalmas valós idejű rendszerekhez : A valós idejű feladatok késedelmet szenvedhetnek a gyakori előjegyzések miatt.