La versió preventiva de la planificació del treball més curt primer (SJF) s'anomena el temps més curt restant primer (SRTF). A SRTF, es selecciona el procés amb menys temps per acabar. El procés en execució continua fins que s'acaba o arriba un nou procés amb un temps restant més curt, assegurant-se sempre que el procés d'acabat més ràpid tingui prioritat.
Exemple d'algoritme SJF:
Escenari 1: processos amb la mateixa hora d'arribada
Exemple: Considereu la taula següent de temps d'arribada i temps d'explosió per a tres processos P1 P2 i P3 .
| Procés | Temps d'explosió | Hora d'arribada |
|---|---|---|
| P1 | 6 ms | 0 ms |
| P2 | 8 ms | 0 ms |
| P3 | 5 ms | 0 ms |
Execució pas a pas:
- Temps 0-5 (P3) : P3 s'executa durant 5 ms (temps total restant: 0 ms) ja que li queda el temps restant més curt.
- Temps 5-11 (P1) : P1 s'executa durant 6 ms (temps total restant: 0 ms) ja que li queda el temps restant més curt.
- Temps 11-19 (P2) : P2 s'executa durant 8 ms (temps total restant: 0 ms) ja que li queda el temps restant més curt.
Diagrama de Gantt:
composició de la relació
Ara calculem la mitjana temps d'espera i volta temps:
Com sabem
- Gireu el temps = Temps de finalització - hora d'arribada
- Temps d'espera = Temps de volta - temps d'explosió
| Procés | Hora d'arribada (AT) | Temps d'explosió alfabet per nombre (BT) | Temps de finalització (CT) | Temps de volta (TAT) | Temps d'espera (WT) |
|---|---|---|---|---|---|
| P1 | 6 | 11 | 11-0 = 11 | 11-6 = 5 | |
| P2 | format de cadena java llarg | 8 | 19 | 19-0 = 19 | 19-8 = 11 |
| P3 | 5 | 5 | 5-0 = 5 | 5-5 = 0 |
Ara
- Temps mitjà de volta = (11 + 19 + 5)/3 = 11,6 ms
- Temps mitjà d'espera = (5 + 0 + 11 )/3 = 16/3 = 5,33 ms
Escenari 2: Processos amb diferents horaris d'arribada
Considereu la següent taula de temps d'arribada i temps d'explosió per a tres processos P1 P2 i P3.
| Procés | Temps d'explosió | Hora d'arribada |
|---|---|---|
| P1 | 6 ms | 0 ms |
| P2 | 3 ms | 1 ms |
| P3 | 7 ms | 2 ms |
Execució pas a pas:
com imprimir java
- Temps 0-1 (P1) : P1 s'executa durant 1 ms (temps total restant: 5 ms) ja que li queda el temps restant més curt.
- Temps 1-4 (P2) : P2 s'executa durant 3 ms (temps total restant: 0 ms) ja que té el temps restant més curt entre P1 i P2.
- Temps 4-9 (P1) : P1 s'executa durant 5 ms (temps total restant: 0 ms) ja que té el temps restant més curt entre P1 i P3.
- Temps 9-16 (P3) : P3 s'executa durant 7 ms (temps total restant: 0 ms) ja que li queda el temps restant més curt.
Diagrama de Gantt:
Ara calculem la mitjana temps d'espera i volta temps:
| Procés | Hora d'arribada (AT) | Temps de ràfega (BT) | Temps de finalització (CT) | Temps de volta (TAT) | Temps d'espera (WT) |
|---|---|---|---|---|---|
| P1 | taula de reaccions | 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 |
- Temps mitjà de volta = (9 + 14 + 3)/3 = 8,6 ms
- Temps mitjà d'espera = (3 + 0 + 7 )/3 = 10/3 = 3,33 ms
Implementació de l'algoritme SRTF
Pas 1: Introduïu el nombre de processos amb l'hora d'arribada i el temps de ràfega.
Pas 2: Inicialitzar temps restants (temps de ràfega) temps actual = 0 i comptadors.
Pas 3: A cada unitat de temps afegeix processos que han arribat a la cua preparada.
Pas 4: Seleccioneu el procés amb el temps restant més curt (preempreu si n'arriba un de més curt).
Pas 5: Executeu el procés seleccionat durant 1 unitat, reduïu el seu temps restant i incrementeu el temps actual.
Pas 6: Si es completa un procés:
- Temps de resposta = Temps de finalització − Hora d'arribada
- Temps d'espera = Temps de resposta − Temps de ràfega
Pas 7: Repetiu els passos 3-6 fins que s'acabin tots els processos.
Pas 8: Calcula el temps mitjà d'espera i el temps de resposta.
Pas 9: Mostra els temps d'espera i d'execució per a cada procés juntament amb les mitjanes.
Implementació del codi
El programa per implementar el temps més curt restant primer és el següent:
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)
Sortida
Enter number of processes: Avg WT: -nan Avg TAT: -nan
Avantatges de SRTF Programació
- Minimitza el temps d'espera mitjà : SRTF redueix el temps d'espera mitjà prioritzant els processos amb el temps d'execució restant més curt.
- Eficient per a processos curts : Els processos més curts es completen més ràpidament millorant la resposta global del sistema.
- Ideal per a sistemes crítics de temps : Assegura que els processos sensibles al temps s'executen ràpidament.
Inconvenients de SRTF Programació
- Inanició de processos llargs : els processos més llargs es poden retardar indefinidament si continuen arribant processos més curts.
- Difícil de predir els temps d'explosió : La predicció precisa dels temps d'explosió del procés és un repte i afecta les decisions de programació.
- Alt sobrecàrrega : El canvi de context freqüent pot augmentar la sobrecàrrega i alentir el rendiment del sistema.
- No apte per a sistemes en temps real : les tasques en temps real poden patir retards a causa de freqüents preempcions.