logo

TechCodeview

Lyhin jäljellä oleva aika ensin (ennaltaehkäisevä SJF) -aikataulutusalgoritmi

Lyhyin työ ensin (SJF) -aikataulutuksen ennakoivaa versiota kutsutaan nimellä Shortest Remaining Time First (SRTF). SRTF:ssä valitaan suoritettavaksi prosessi, jonka loppuun on vähiten aikaa jäljellä. Käynnissä oleva prosessi jatkuu, kunnes se päättyy tai uusi prosessi, jolla on lyhyempi jäljellä oleva aika, saapuu, mikä varmistaa, että nopein viimeistelyprosessi on aina etusijalla.

Esimerkki SJF-algoritmista:

Skenaario 1: Prosessit, joilla on sama saapumisaika

Esimerkki: Harkitse seuraavaa taulukkoa kolmen prosessin saapumisajasta ja purskeajasta P1 P2 ja P3 .

Käsitellä Burst Time Saapumisaika
 P1   6 ms0 ms
 P2 8 ms0 ms
 P3 5 ms0 ms

Vaiheittainen suoritus:



  1. Aika 0-5 (P3) : P3 toimii 5 ms (yhteensä jäljellä: 0 ms), koska sillä on lyhin jäljellä oleva aika.
  2. Aika 5-11 (P1) : P1 toimii 6 ms (yhteensä jäljellä: 0 ms), koska sillä on lyhin jäljellä oleva aika.
  3. Aika 11-19 (P2) : P2 toimii 8 ms (jäljellä oleva kokonaisaika: 0 ms), koska sillä on lyhin jäljellä oleva aika.

Gantt-kaavio:


merkkijonojen vaihto c

Nyt lasketaan keskiarvo odotusaika ja käänny ympäri aika:

Kuten tiedämme

  • Kääntymisaika = Valmistumisaika - saapumisaika
  • Odotusaika = Kääntymisaika - jaksotusaika
Käsitellä  

Saapumisaika

vuosineljänneksen liiketoiminnassa

(AT)

Burst Time

(BT)

Valmistumisaika (CT)Kääntymisaika (TAT)Odotusaika (WT)
 P1  

6

1111-0 = 1111-6 = 5
 P2

8

1919-0 = 1919-8 = 11
 P3

javalla on seuraava

5

55-0 = 55-5 = 0

Nyt 

  • Keskimääräinen Kääntymisaika = (11 + 19 + 5)/3 = 11,6 ms
  • Keskimääräinen odotusaika = (5 + 0 + 11 )/3 = 16/3 = 5,33 ms

Skenaario 2: Prosessit, joilla on eri saapumisajat

Tarkastellaan seuraavaa taulukkoa kolmen prosessin P1 P2 ja P3 saapumisajasta ja purskeajasta.

Käsitellä Burst Time Saapumisaika
 P1   6 ms0 ms
 P2 3 ms1 ms
 P3 7 ms2 ms

Vaiheittainen suoritus:

  1. Aika 0-1 (P1) : P1 toimii 1 ms (yhteensä jäljellä: 5 ms), koska sillä on lyhin jäljellä oleva aika.
  2. Aika 1-4 (P2) : P2 toimii 3 ms (yhteensä jäljellä: 0 ms), koska sillä on lyhin jäljellä oleva aika P1:stä ja P2:sta.
  3. Aika 4-9 (P1) : P1 toimii 5 ms (yhteensä jäljellä: 0 ms), koska sillä on lyhin jäljellä oleva aika P1:stä ja P3:sta.
  4. Aika 9-16 (P3) : P3 toimii 7 ms (yhteensä jäljellä: 0 ms), koska sillä on lyhin jäljellä oleva aika.

Gantt-kaavio:

Nyt lasketaan keskiarvo odotusaika ja käänny ympäri aika:

staattinen avainsana javassa
Käsitellä  

Saapumisaika (AT)

Sarjakuvausaika (BT)

Valmistumisaika (CT)Kääntymisaika (TAT)Odotusaika (WT)
 P1  

6

99-0 = 99-6 = 3
 P2

1

3

44-1 = 33-3 = 0
 P3

2

lisää taulukkoon java

7

1616-2 = 1414-7 = 7
  • Keskimääräinen Kääntymisaika = (9 + 14 + 3)/3 = 8,6 ms
  • Keskimääräinen odotusaika = (3 + 0 + 7)/3 = 10/3 = 3,33 ms

SRTF-algoritmin toteutus

Vaihe 1: Syötä prosessien lukumäärä saapumisajan ja purskeajan kanssa.
Vaihe 2: Alusta jäljellä olevat ajat (purskeajat) nykyinen aika = 0 ja laskurit.
Vaihe 3: Jokaisella aikayksiköllä lisätään valmiiseen jonoon saapuneet prosessit.
Vaihe 4: Valitse prosessi, jolla on lyhin jäljellä oleva aika (ennakolta, jos lyhyempi saapuu).
Vaihe 5: Suorita valittu prosessi 1 yksikölle, vähennä sen jäljellä olevaa aikaa ja lisää nykyistä aikaa.
Vaihe 6: Jos prosessi on valmis:

  • Käsittelyaika = Valmistusaika − Saapumisaika
  • Odotusaika = läpimenoaika − Sarjakuvausaika

Vaihe 7: Toista vaiheita 3–6, kunnes kaikki prosessit on suoritettu.
Vaihe 8: Laske keskimääräinen odotusaika ja läpimenoaika.
Vaihe 9: Näytä kunkin prosessin valmistumis- ja läpimenoajat sekä keskiarvot.

Koodin toteutus

Lyhyin jäljellä oleva aika ensin -ohjelma on seuraava:

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)

Lähtö 
Enter number of processes: Avg WT: -nan Avg TAT: -nan

SRTF:n edut Ajoitus

  1. Minimoi keskimääräisen odotusajan : SRTF vähentää keskimääräistä odotusaikaa priorisoimalla prosesseja, joilla on lyhin jäljellä oleva suoritusaika.
  2. Tehokas lyhyisiin prosesseihin : Lyhyemmät prosessit valmistuvat nopeammin, mikä parantaa järjestelmän yleistä reagointikykyä.
  3. Ihanteellinen aikakriittisiin järjestelmiin : Se varmistaa, että aikaherkät prosessit suoritetaan nopeasti.

SRTF:n haitat Ajoitus

  1. Pitkien prosessien nälkä : Pidemmät prosessit voivat viivästyä määräämättömäksi ajaksi, jos lyhyempiä prosesseja saapuu jatkuvasti.
  2. Purkausaikoja on vaikea ennustaa : Prosessin purskeaikojen tarkka ennustaminen on haastavaa ja vaikuttaa aikataulupäätöksiin.
  3. Korkea yläraja : Toistuva kontekstin vaihtaminen voi lisätä yleiskustannuksia ja hidastaa järjestelmän suorituskykyä.
  4. Ei sovellu reaaliaikaisiin järjestelmiin : Reaaliaikaiset tehtävät voivat kärsiä viiveistä toistuvien ennakoiden vuoksi.
Luo tietokilpailu