logo

TechCodeview

Vispirms īsākais atlikušais laiks (preventīvs SJF) plānošanas algoritms

Īsāko darbu vispirms (SJF) plānošanas preemptīvā versija tiek saukta par visīsāko atlikušo laiku vispirms (SRTF). SRTF tiek izvēlēts palaišanai process, kura pabeigšanai ir atlicis vismazākais laiks. Darbības process turpinās, līdz tas beidzas vai tiek parādīts jauns process ar īsāku atlikušo laiku, nodrošinot ātrāko pabeigšanas procesu vienmēr par prioritāti.

SJF algoritma piemērs:

1. scenārijs: procesi ar vienādu ierašanās laiku

Piemērs: Apsveriet šo tabulu par ierašanās laiku un sērijveida laiku trim procesiem P1 P2 un P3 .

Process Pārraušanas laiks Ierašanās laiks
 P1   6 ms0 ms
 P2 8 ms0 ms
 P3 5 ms0 ms

Soli pa solim izpilde:



  1. Laiks 0-5 (P3) : P3 darbojas 5 ms (kopējais atlikušais laiks: 0 ms), jo tam ir atlicis mazākais atlikušais laiks.
  2. Laiks 5-11 (P1) : P1 darbojas 6 ms (kopējais atlikušais laiks: 0 ms), jo tam ir atlicis mazākais atlikušais laiks.
  3. Laiks 11-19 (P2) : P2 darbojas 8 ms (kopējais atlikušais laiks: 0 ms), jo tam ir atlicis mazākais atlikušais laiks.

Ganta diagramma:


iestatīt atdalītāju java

Tagad aprēķināsim vidējo gaidīšanas laiks un apgriezties laiks:

Kā mēs zinām

  • Apgriezienu laiks = Pabeigšanas laiks - ierašanās laiks
  • Gaidīšanas laiks = Apgriešanas laiks — sērijveida uzņemšanas laiks
Process  

Ierašanās laiks

(AT)

Pārraušanas laiks

(BT)

Pabeigšanas laiks (CT)Apgriešanas laiks (TAT)Gaidīšanas laiks (WT)
 P1  

atšķirība starp vakariņām un vakariņām

6

1111-0 = 1111-6 = 5
 P2

8

kā virkni pārvērst par int
1919-0 = 1919-8 = 11
 P3

5

55-0 = 55-5 = 0

Tagad 

  • Vidējais apgriešanās laiks = (11 + 19 + 5)/3 = 11,6 ms
  • Vidējais gaidīšanas laiks = (5 + 0 + 11 )/3 = 16/3 = 5,33 ms

2. scenārijs: procesi ar atšķirīgu ierašanās laiku

Apsveriet šādu tabulu par ierašanās laiku un sērijveida laiku trim procesiem P1 P2 un P3.

Process Pārraušanas laiks Ierašanās laiks
 P1   6 ms0 ms
 P2 3 ms1 ms
 P3 7 ms2 ms

Soli pa solim izpilde:

  1. Laiks 0-1 (P1) : P1 darbojas 1 ms (kopējais atlikušais laiks: 5 ms), jo tam ir atlicis mazākais atlikušais laiks.
  2. Laiks 1–4 (P2) : P2 darbojas 3 ms (kopējais atlikušais laiks: 0 ms), jo tam ir atlicis mazākais atlikušais laiks starp P1 un P2.
  3. Laiks 4–9 (P1) : P1 darbojas 5 ms (kopējais atlikušais laiks: 0 ms), jo tam ir atlicis mazākais atlikušais laiks starp P1 un P3.
  4. Laiks 9-16 (P3) : P3 darbojas 7 ms (kopējais atlikušais laiks: 0 ms), jo tam ir atlicis mazākais atlikušais laiks.

Ganta diagramma:

kandidāta atslēga

Tagad aprēķināsim vidējo gaidīšanas laiks un apgriezties laiks:

Process  

Ierašanās laiks (AT)

Pārraides laiks (BT)

Pabeigšanas laiks (CT)Apgriešanas laiks (TAT)Gaidīšanas laiks (WT)
 P1  

6

99-0 = 99-6 = 3
 P2

1

javascript apgriešana

3

44-1 = 33-3 = 0
 P3

2

7

1616-2 = 1414-7 = 7
  • Vidējais apgriešanās laiks = (9 + 14 + 3)/3 = 8,6 ms
  • Vidējais gaidīšanas laiks = (3 + 0 + 7)/3 = 10/3 = 3,33 ms

SRTF algoritma ieviešana

1. darbība: Ievadiet procesu skaitu ar ierašanās laiku un sērijveida laiku.
2. darbība: Inicializēt atlikušos laikus (sērijveida sērijas), pašreizējais laiks = 0 un skaitītāji.
3. darbība: Katrā laika vienībā pievienojiet procesus, kas ir ieradušies gatavības rindā.
4. darbība: Atlasiet procesu ar visīsāko atlikušo laiku (iepriekš veiciet, ja pienāk īsāks).
5. darbība: Izpildiet atlasīto procesu 1 vienībai, samaziniet atlikušo laiku un palieliniet pašreizējo laiku.
6. darbība: Ja process ir pabeigts:

  • Apgrozījuma laiks = pabeigšanas laiks - ierašanās laiks
  • Gaidīšanas laiks = Turnaround Time - Burst Time

7. darbība: Atkārtojiet 3.–6. darbību, līdz visi procesi ir pabeigti.
8. darbība: Aprēķiniet vidējo gaidīšanas laiku un izpildes laiku.
9. darbība: Parādiet katra procesa pabeigšanas gaidīšanas un izpildes laikus kopā ar vidējiem rādītājiem.

Koda ieviešana

Programma Īsākā atlikušā laika ieviešanai vispirms ir šāda:

C++ 
#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; }
Java 
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);  } }
Python 
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)

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

SRTF priekšrocības Plānošana

  1. Samazina vidējo gaidīšanas laiku : SRTF samazina vidējo gaidīšanas laiku, piešķirot prioritāti procesiem ar īsāko atlikušo izpildes laiku.
  2. Efektīva īsiem procesiem : īsāki procesi tiek pabeigti ātrāk, uzlabojot vispārējo sistēmas atsaucību.
  3. Ideāli piemērots laika kritiskām sistēmām : Tas nodrošina, ka laika jutīgie procesi tiek ātri izpildīti.

SRTF trūkumi Plānošana

  1. Ilgstošu procesu badošanās : ilgāki procesi var tikt aizkavēti uz nenoteiktu laiku, ja turpina ienākt īsāki procesi.
  2. Grūti paredzēt pārrāvuma laikus : Precīza procesa sērijveida laika prognozēšana ir sarežģīta un ietekmē plānošanas lēmumus.
  3. Augstas pieskaitāmās izmaksas : Bieža konteksta maiņa var palielināt izmaksas un palēnināt sistēmas veiktspēju.
  4. Nav piemērots reāllaika sistēmām : reāllaika uzdevumi var tikt aizkavēti biežu priekšlaicīgu pasākumu dēļ.
Izveidojiet viktorīnu