Programarea preventivă (preemptive) este o metodă de planificare în care sarcinile sunt gestionate în funcție de priorități, iar CPU este alocat unui anumit proces pe o perioadă definită sau până la finalizarea acestuia. În acest tip de metodă, execuția se poate întrerupe pentru a permite altui proces cu prioritate mai mare să ruleze. În contrast, programarea non-preemptivă asigură că, odată ce un proces începe execuția, acesta își continuă rularea până la finalizarea sa, fiind greu perturbată de sosirea altor sarcini.
Textul sursă din lucrarea „F1! Algoritmi și structuri de date” oferă o colecție de articole utile pentru pregătirea olimpiadelor și a concursurilor de informatică, cu scopul de a sprijini elevii și profesorii în drumul către performanță. În contextul programării competitive, această lucrare poate facilita înțelegerea diferențelor dintre metodele de planificare și poate oferi exemple concrete pentru implementare și analiză a performanței.
Definirea și obiectivele planificării pe baza priorităților
Planificarea pe baza priorităților atribuie un nivel de importanță fiecărui proces sau sarcină. În programarea preventivă, CPU-ul este alocat unui proces pentru perioade definite sau până la terminarea sa, iar sosirea unui proces cu prioritate mai mare poate duce la întreruperea execuției curente. Acest lucru permite răspuns rapid la sarcini critice, îmbunătățind performanța în sistemele cu sarcini variate sau în medii cu cerințe de timp real.
În scopul unei comparații clare, iată o descriere directă a diferențelor dintre cele două abordări:
- Programarea preventivă (preemptive): întreruperi regulate sau la sosirea sarcinilor cu prioritate mai mare; CPU poate schimba sarcina în execuție.
- Programarea non-preemptivă: o sarcină, odată ce începe, rulează până la finalizarea sa; sosirea noilor sarcini nu poate perturbă execuția curentă până la terminarea ei.
Exemple ilustrative din descrierea sursei
Pas 1) La ora=1, vine Procesul P3. Dar P4 mai are nevoie de 2 unități de execuție pentru a finaliza. Pas 2) La momentul=2, procesul P1 sosește și este adăugat la coada de așteptare. Pas 3) La momentul=3, procesul P4 își va termina execuția. Se compară timpul de explozie a lui P3 și P1. Pas 4) La ora=4, procesul P5 sosește și este adăugat la coada de așteptare. Pas 5) La ora=5, procesul P2 sosește și este adăugat la coada de așteptare. Pas 6) La momentul=9, procesul P1 își va termina execuția. Se compară timpul de explozie a lui P3, P5 și P2.
Pas 1) Execuția începe cu procesul P1, care are timpul de explozie 4. Aici, fiecare proces se execută timp de 2 secunde. Pas 3) La momentul=4, P2 este preemptat și se adaugă la sfârșitul cozii. Pas 4) La momentul=6, P3 este preemptat și se adaugă la sfârșitul cozii. Pas 5) La time=8, P1 are un timp de explozie de 4. Execuția sa încheiat. Pas 6) P2 are un timp de explozie de 3. S-a executat deja pentru 2 intervale. La momentul=9, P2 finalizează execuția.
Structură de analiză a performanței
Analiza performanței în planificarea pe priorități implică următoarele rezultate-cheie:
- Timpi de răspuns: timpul dintre sosire și începutul execuției pentru fiecare sarcină.
- Timpuri de așteptare: diferența dintre timpul de sosire și timpul efectiv alocat pentru execuție.
- Timpii de finalizare și latența totală: când sarcina își încheie execuția în raport cu sosirea inițială.
- Eficiența CPU-ului: utilizarea CPU-ului pe perioade de timp, numărul de contexte schimbate (preemptări).
Implementare simplificată a planificării preemptive
O implementare de bază poate folosi o listă de sarcini cu proprietăți: prioritate, timp de explozie (burst time), sosire, stare (în așteptare, în execuție, finalizată). Algoritmul poate să:
- Asigure sosirea sarcinilor în coada de așteptare conform timpului de sosire.
- Selecteze în mod repetat sarcina cu prioritatea cea mai mare care poate începe sau continua execuția.
- Gestionare întreruperi în caz de preemptie, adăugând sarcina într-un coada la sfârșitul rândului și reîncărcând curentul conform regulilor de prioritate.
În cazul programării non-preemptive, algoritmul nu poate întrerupe sarcinile în execuție decât după finalizarea lor, deci schimbările de context vor fi mai puține, iar performanțele pot fi diferite în funcție de distribuția sosirilor și de priorități.
Aspecte practice pentru olimpiade și concursuri
Pentru pregătire, este util să se modeleze scenarii de planificare cu seturi de sarcini reprezentative pentru diverse platforme hardware și condiții de timp real. Exemplele din textul sursei oferă un cadru pentru înțelegerea dinamici a preemptării, a cozii de așteptare și a priorităților, utile în implementările competitive.
Este recomandat să se combine prezentarea teoretică cu exemple numerice, să se ofere diagrame de execuție și să se includă evaluări comparative între abordări preemptive și non-preemptive pentru a evidenția compromisurile de performanță în funcție de situație.
O posibilă ilustrare suplimentară este o diagramă de Gantt a unei secvențe de sarcini la sosire și execuție, evidențiind momentele de preemption în timpul planificării.
De asemenea, o diagramă de flux poate clarifica pasii de decizie când se alege sarcina următoare de executat în funcție de prioritate și sosire.
Posibile îmbunătățiri și extensii
Pentru aprofundare, se pot aborda variante precum:
- Planificare cu priorități dinamice (MODIFICĂRILE priorității în timpul execuției, în funcție de metrici de performanță).
- Algoritmi de planificare cu prioritate fixă sau în jur de timpul de răspuns dorit (hard real-time vs. soft real-time).
- Metode hibride preemptive/non-preemptive în funcție de tipul sarcinilor și de penalty-urile asociate.
Lucrarea menționată poate oferi cadrul teoretic și exemplele necesare pentru a înțelege aceste concepte și a le aplica în problemele de concurs și proiecte academice.
What Is the Main Difference Between Preemptive And Nonpreemptive Scheduling
Analiza practică poate fi însoțită de o tabelă cu timpuri de sosire, time slices, priorități, și timpi de finalizare pentru un set simplificat de sarcini, facilitând înțelegerea dinamici a planificării.
| Sarcină | Sosire | Prioritate | Time Slice | Finalizare |
|---|---|---|---|---|
| P1 | 1 | 2 | 2 | 9 |
| P2 | 2 | 1 | 2 | 11 |
| P3 | 3 | 3 | 2 | - |
| P4 | 4 | 2 | 2 | - |
tags: #planificarea #sarcinilor #de #calcul #pe #baza