Den forebyggende version af Shortest Job First (SJF) planlægning kaldes Shortest Remaining Time First (SRTF). I SRTF er processen med mindst tid tilbage til at blive valgt til at køre. Den kørende proces fortsætter, indtil den afsluttes, eller en ny proces med en kortere resterende tid ankommer, hvilket sikrer, at den hurtigste efterbehandlingsproces altid får prioritet.
Eksempel på SJF-algoritme:
Scenario 1: Processer med samme ankomsttid
Eksempel: Overvej følgende tabel over ankomsttid og eksplosionstid for tre processer P1 P2 og P3 .
| Behandle | Burst Time | Ankomsttid |
|---|---|---|
| P1 | 6 ms | 0 ms |
| P2 | 8 ms | 0 ms |
| P3 | 5 ms | 0 ms |
Trin-for-trin udførelse:
- Tid 0-5 (P3) : P3 kører i 5 ms (samlet tid tilbage: 0 ms), da den har den korteste resterende tid tilbage.
- Tid 5-11 (P1) : P1 kører i 6 ms (samlet tid tilbage: 0 ms), da den har den korteste resterende tid tilbage.
- Tid 11-19 (P2) : P2 kører i 8 ms (samlet tid tilbage: 0 ms), da den har den korteste resterende tid tilbage.
Gantt-diagram:
java boolesk streng
Lad os nu beregne gennemsnittet ventetid og vend om tid:
Som vi ved
- Vendetid = Gennemførelsestid - ankomsttid
- Ventetid = Vendetid - sprængtid
| Behandle | Ankomsttid (PÅ) | Burst Time gitterlayout (BT) | Gennemførelsestid (CT) | Omløbstid (TAT) | Ventetid (WT) |
|---|---|---|---|---|---|
| P1 | 6 | 11 | 11-0 = 11 | 11-6 = 5 | |
| P2 | hvad er const i java | 8 | 19 | 19-0 = 19 | 19-8 = 11 |
| P3 | 5 | 5 | 5-0 = 5 | 5-5 = 0 |
Nu
- Gennemsnitlig omløbstid = (11 + 19 + 5)/3 = 11,6 ms
- Gennemsnitlig ventetid = (5 + 0 + 11 )/3 = 16/3 = 5,33 ms
Scenarie 2: Processer med forskellige ankomsttider
Overvej følgende tabel over ankomsttid og bursttid for tre processer P1 P2 og P3.
| Behandle | Burst Time | Ankomsttid |
|---|---|---|
| P1 | 6 ms | 0 ms |
| P2 | 3 ms | 1 ms |
| P3 | 7 ms | 2 ms |
Trin-for-trin udførelse:
java dato til streng
- Tid 0-1 (P1) : P1 kører i 1 ms (samlet tid tilbage: 5 ms), da den har den korteste resterende tid tilbage.
- Tid 1-4 (P2) : P2 kører i 3 ms (samlet tid tilbage: 0 ms), da den har den korteste resterende tid tilbage blandt P1 og P2.
- Tid 4-9 (P1) : P1 kører i 5 ms (samlet tid tilbage: 0 ms), da den har den korteste resterende tid tilbage blandt P1 og P3.
- Tid 9-16 (P3) : P3 kører i 7 ms (samlet tid tilbage: 0 ms), da den har den korteste resterende tid tilbage.
Gantt-diagram:
Lad os nu beregne gennemsnittet ventetid og vend om tid:
| Behandle | Ankomsttid (AT) | Burst Time (BT) | Gennemførelsestid (CT) | Omløbstid (TAT) | Ventetid (WT) |
|---|---|---|---|---|---|
| P1 | kan android spille gamepigeon | 6 | 9 | 9-0 = 9 | 9-6 = 3 |
| P2 | 1 | 3 | 4 | 4-1 = 3 | 3-3 = 0 |
| P3 | 2 | 7 | 16 | 16-2 = 14 | 14-7 = 7 |
- Gennemsnitlig omløbstid = (9 + 14 + 3)/3 = 8,6 ms
- Gennemsnitlig ventetid = (3 + 0 + 7)/3 = 10/3 = 3,33 ms
Implementering af SRTF-algoritme
Trin 1: Indtast antal processer med ankomsttid og burst tid.
Trin 2: Initialiser resterende tider (bursttider) aktuel tid = 0 og tællere.
Trin 3: Ved hver tidsenhed tilføjes processer, der er ankommet til klarkøen.
Trin 4: Vælg processen med den korteste resterende tid (foregribe, hvis der kommer en kortere).
Trin 5: Udfør den valgte proces for 1 enhed, reducer dens resterende tid og øg den aktuelle tid.
Trin 6: Hvis en proces afsluttes:
- Ekspeditionstid = Gennemførelsestid − Ankomsttid
- Ventetid = Ekspeditionstid − Burst Time
Trin 7: Gentag trin 3-6, indtil alle processer er afsluttet.
Trin 8: Beregn gennemsnitlig ventetid og ekspeditionstid.
Trin 9: Vis afslutningsvente- og behandlingstider for hver proces sammen med gennemsnit.
Kode Implementering
Programmet til at implementere Korteste Resterende Tid Først er som følger:
C++#include
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)
Produktion
Enter number of processes: Avg WT: -nan Avg TAT: -nan
Fordele ved SRTF Planlægning
- Minimerer den gennemsnitlige ventetid : SRTF reducerer den gennemsnitlige ventetid ved at prioritere processer med den korteste resterende eksekveringstid.
- Effektiv til korte processer : Kortere processer afsluttes hurtigere, hvilket forbedrer den overordnede systemrespons.
- Ideel til tidskritiske systemer : Det sikrer, at tidsfølsomme processer udføres hurtigt.
Ulemper ved SRTF Planlægning
- Udsultning af lange processer : Længere processer kan blive forsinket på ubestemt tid, hvis kortere processer bliver ved med at ankomme.
- Svært at forudsige Burst Times : Nøjagtig forudsigelse af procesbrudtider er udfordrende og påvirker planlægningsbeslutninger.
- Høj overhead : Hyppig kontekstskift kan øge overhead og sænke systemets ydeevne.
- Ikke egnet til realtidssystemer : Realtidsopgaver kan lide forsinkelser på grund af hyppige forkøb.