Den förebyggande versionen av Shortest Job First (SJF) schemaläggning kallas Shortest Remaining Time First (SRTF). I SRTF väljs processen med minst tid kvar att slutföra. Den pågående processen fortsätter tills den är klar eller en ny process med kortare återstående tid kommer, vilket säkerställer att den snabbaste efterbehandlingsprocessen alltid får prioritet.
Exempel på SJF-algoritm:
Scenario 1: Processer med samma ankomsttid
Exempel: Tänk på följande tabell över ankomsttid och sprängtid för tre processer P1 P2 och P3 .
| Behandla | Burst Time | Ankomsttid |
|---|---|---|
| P1 | 6 ms | 0 ms |
| P2 | 8 ms | 0 ms |
| P3 | 5 ms | 0 ms |
Steg-för-steg-utförande:
- Tid 0-5 (P3) : P3 kör i 5 ms (total tid kvar: 0 ms) eftersom den har kortast återstående tid kvar.
- Tid 5-11 (P1) : P1 kör i 6 ms (total tid kvar: 0 ms) eftersom den har kortast återstående tid kvar.
- Tid 11-19 (P2) : P2 kör i 8 ms (total tid kvar: 0 ms) eftersom den har kortast återstående tid kvar.
Gantt-diagram:
java klassdiagram
Låt oss nu beräkna genomsnittet väntetid och vända tid:
Som vi vet
- Vändningstid = Slutförandetid - ankomsttid
- Väntetid = Vändningstid - sprängtid
| Behandla | Ankomsttid (PÅ) | Burst Time fånga och prova java (BT) | Slutförandetid (CT) | Turn Around Time (TAT) | Väntetid (WT) |
|---|---|---|---|---|---|
| P1 | 6 | 11 | 11-0 = 11 | 11-6 = 5 | |
| P2 | sträng till tecken | 8 | 19 | 19-0 = 19 | 19-8 = 11 |
| P3 | 5 | 5 | 5-0 = 5 | 5-5 = 0 |
Nu
- Genomsnittlig vändningstid = (11 + 19 + 5)/3 = 11,6 ms
- Genomsnittlig väntetid = (5 + 0 + 11 )/3 = 16/3 = 5,33 ms
Scenario 2: Processer med olika ankomsttider
Betrakta följande tabell över ankomsttid och skurtid för tre processer P1 P2 och P3.
| Behandla | Burst Time | Ankomsttid |
|---|---|---|
| P1 | 6 ms | 0 ms |
| P2 | 3 ms | 1 ms |
| P3 | 7 ms | 2 ms |
Steg-för-steg-utförande:
fet text i css
- Tid 0-1 (P1) : P1 kör i 1 ms (total tid kvar: 5 ms) eftersom den har kortast återstående tid kvar.
- Tid 1-4 (P2) : P2 löper i 3 ms (total tid kvar: 0 ms) eftersom den har kortast återstående tid kvar bland P1 och P2.
- Tid 4-9 (P1) : P1 kör i 5 ms (total tid kvar: 0 ms) eftersom den har kortast återstående tid kvar bland P1 och P3.
- Tid 9-16 (P3) : P3 kör i 7 ms (total tid kvar: 0 ms) eftersom den har kortast återstående tid kvar.
Gantt-diagram:
Låt oss nu beräkna genomsnittet väntetid och vända tid:
| Behandla | Ankomsttid (AT) | Burst Time (BT) | Slutförandetid (CT) | Turn Around Time (TAT) | Väntetid (WT) |
|---|---|---|---|---|---|
| P1 | int till char | 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 |
- Genomsnittlig vändningstid = (9 + 14 + 3)/3 = 8,6 ms
- Genomsnittlig väntetid = (3 + 0 + 7)/3 = 10/3 = 3,33 ms
Implementering av SRTF-algoritm
Steg 1: Mata in antal processer med ankomsttid och skurtid.
Steg 2: Initiera återstående tider (skurtider) aktuell tid = 0 och räknare.
Steg 3: Vid varje tidsenhet lägg till processer som har anlänt till färdigkön.
Steg 4: Välj processen med kortast återstående tid (förhindra om en kortare kommer).
Steg 5: Utför den valda processen för 1 enhet minska dess återstående tid och öka aktuell tid.
Steg 6: Om en process slutförs:
- Handläggningstid = Slutföringstid − Ankomsttid
- Väntetid = Handläggningstid − Burst Time
Steg 7: Upprepa steg 3–6 tills alla processer är klara.
Steg 8: Beräkna genomsnittlig väntetid och handläggningstid.
Steg 9: Visa väntetider och handläggningstider för slutförandet för varje process tillsammans med medelvärden.
Kodimplementering
Programmet för att implementera Kortaste återstående tid först är som följer:
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
Fördelar med SRTF Schemaläggning
- Minimerar den genomsnittliga väntetiden : SRTF minskar den genomsnittliga väntetiden genom att prioritera processer med den kortaste återstående körtiden.
- Effektiv för korta processer : Kortare processer slutförs snabbare vilket förbättrar systemets övergripande lyhördhet.
- Idealisk för tidskritiska system : Det säkerställer att tidskänsliga processer exekveras snabbt.
Nackdelar med SRTF Schemaläggning
- Svält av långa processer : Längre processer kan försenas på obestämd tid om kortare processer fortsätter att anlända.
- Svårt att förutsäga sprängtider : Noggrann förutsägelse av processbrottstider är utmanande och påverkar schemaläggningsbeslut.
- Hög overhead : Frekvent kontextväxling kan öka overhead och bromsa systemets prestanda.
- Inte lämplig för realtidssystem : Realtidsuppgifter kan drabbas av förseningar på grund av frekventa förköp.