Cel mai scurt loc de muncă (SJF)
La analizarea algoritmilor FCFS și RR, am văzut cât de important este ca ei să comande procese în coada de procese gata pentru execuție. Dacă sarcinile scurte sunt situate în coada mai aproape de începutul ei, atunci performanța generală a acestor algoritmi crește semnificativ. Dacă am fi știut timpul următorului spargere a procesorului pentru procesele în stare gata, am putea alege să nu executăm procesul de la începutul coadajului, ci procesul cu durata minimă de spargere a procesorului. Dacă există două sau mai multe astfel de procese, atunci putem folosi algoritmul deja cunoscut FCFS pentru a selecta unul dintre ele. Nu se aplică cuantizarea timpului. Algoritmul descris a fost numit "cel mai scurt timp de lucru" sau "Shortest Job First" (SJF).
Algoritmul SJF al planificării pe termen scurt poate fi atât preventiv. și non-preemptive. Cu programarea SJF non-preemptivă, procesorul este furnizat procesului selectat pentru tot timpul necesar, indiferent de evenimentele care apar în sistemul de calcul. La înlocuirea planificării SJF, procesele noi din coadă sunt pregătite pentru a fi executate (de la cei nou-născuți sau cei deblocați) în timpul procesului selectat. Dacă explozia CPU-ului unui proces nou este mai mică decât restul procesului de spargere al procesorului, procesul de execuție este înlocuit cu unul nou.
Să luăm în considerare un exemplu de funcționare a algoritmului non-relief SJF. Fie ca patru procese să fie gata în stare gata, p0. p1. p2 și p3. pentru care se cunoaște ora următoarei explozii a procesorului. Aceste vremuri sunt prezentate în Tabelul 3.4. Ca și înainte, presupunem că toată activitatea proceselor este limitată la utilizarea doar a unui singur interval de spargere a procesorului. că procesele nu efectuează operații I / O și că timpul de comutare a contextului poate fi neglijat.
După cum se poate observa, timpul mediu de așteptare pentru algoritmul SJF este (4 + 1 + 9 + 0) / 4 = 3,5 ori. Este ușor de calculat că pentru algoritmul FCFS pentru ordinea proceselor p0. p1. p2. p3, această valoare va fi (0 + 5 + 8 + 15) / 4 = 7 unități de timp, adică va fi de două ori mai mare decât algoritmul SJF. Se poate demonstra că pentru un anumit set de procese (dacă procesele noi nu apar în coadă), algoritmul SJF este optim din punctul de vedere al minimizării timpului mediu de așteptare în clasa de algoritmi care nu eliberează.
Pentru a examina un exemplu de planificare SJF preventivă, luăm o serie de procese p0. p1. p2 și p3 cu timpi de spargere CPU diferiți și momente diferite ale aspectului lor în coada proceselor gata pentru execuție (vezi Tabelul 3.6).
Ora de apariție a următoarei explozii a procesorului
La momentul inițial, sunt disponibile numai două procese, p0 și p3. Timpul mai mic al următoarei explozii a procesorului este în proces p3. deci este selectat pentru execuție (vezi tabelul 3.7.). După 2 unități de timp, procesul p1 ajunge în sistem. Momentul izbucnirii procesorului său este mai mic decât restul procesului de procesare a procesorului p3. care este înlocuită de starea de execuție și este tradusă într-o stare de pregătire. După alte unități de timp de 2 ori, procesul p1 este finalizat, iar procesul p3 este selectat din nou pentru execuție. La momentul t = 6, un proces p2 apare în coada de proces, gata de execuție. dar deoarece are nevoie de 7 unități de timp pentru a lucra și doar 1 unitate de timp rămâne pentru procesul p3, procesul p3 rămâne în starea de execuție. După finalizarea sa la momentul t = 7, procesele p0 și p2 se află în coada de așteptare. din care este selectat procesul p0. În cele din urmă, acesta din urmă va putea executa procesul p2.
Principala dificultate în implementarea algoritmului SJF este incapacitatea de a cunoaște cu precizie durata următoarei explozii a procesorului pentru procesele care rulează. În sistemele lot, cantitatea de timp a procesorului cerută de sarcina de efectuat este indicată de utilizator atunci când creați lucrarea. Putem lua această valoare pentru planificarea SJF pe termen lung. Dacă utilizatorul specifică mai mult timp decât are nevoie, va aștepta rezultatul mai mult decât ar putea, deoarece sarcina va fi descărcată ulterior în sistem. Dacă specifică mai puțin timp, sarcina nu poate fi numărată până la sfârșit. Astfel, în sistemele de loturi, sarcina de estimare a timpului de utilizare a procesorului este deplasată la umerii utilizatorului. Cu o planificare pe termen scurt, putem face doar o prezicere a duratei următoarei explozii a procesorului. pe baza istoriei procesului. Să fie valoarea celei de-a n-a exploziile procesorului. T (n + 1) este valoarea estimată pentru explozia CPN n + 1. - o valoare cuprinsă între 0 și 1.
Definim relația de recurență
T (0) este o constantă arbitrară. Primul termen ia în considerare ultimul comportament al procesului, în timp ce al doilea termen ia în considerare istoricul acestuia. Când oprim monitorizarea celui mai recent comportament al procesului, de fapt,
care este, evaluarea tuturor exploziilor CPU este aceeași, pornind de la o ipoteză inițială.
Punându-l, uităm de fundalul procesului. În acest caz, presupunem că timpul următoarei explozii a procesorului va coincide cu timpul ultimei explozii a procesorului:
Acesta este, de obicei, ales pentru o contabilitate echivalentă a ultimului comportament și fond. Trebuie menționat faptul că această alegere este de asemenea convenabilă pentru organizarea rapidă a calculului estimării T (n + 1). Pentru a calcula o nouă estimare, trebuie să luați vechea estimare, să o adăugați la timpul de spargere a procesorului măsurat și să împărțiți suma rezultată cu 2. De exemplu, deplasați-l cu 1 biți spre dreapta. Estimările obținute de T (n + 1) sunt utilizate ca durata următoarelor intervale de timp pentru utilizarea continuă a procesorului pentru planificarea SJF pe termen scurt.
Articole similare
Trimiteți-le prietenilor: