Programator

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare
Schema unui planificator

Planificatorul (în planificatorul italian sau managerul de procese ), în informatică , este o componentă a unui sistem de operare sau a unui program care implementează un algoritm de planificare (în algoritmul de planificare italian) care, având în vedere un set de cereri de acces la o resursă ( de obicei accesul la procesor printr-un proces care urmează fie executat ), stabilește o ordine temporală pentru executarea acestor solicitări, privilegiindu-le pe cele care respectă anumiți parametri în conformitate cu o anumită politică de planificare , pentru a optimiza accesul la această resursă și astfel permite performanța a serviciului / instrucțiunii sau procesului dorit.

Atenția acordată unor parametri, mai degrabă decât altora, diferențiază așa-numita politică de planificare în cadrul managementului procesului, dând naștere la cozi prioritare : de exemplu, planificatorul poate executa cereri pe baza ordinii lor de sosire ( FIFO ) sau le poate acorda prioritate celor care utilizează resursa pentru mai puțin timp ( SNPF ); pot exista politici care se bazează pe principii statistice sau pe predicții pentru a identifica o ordonare a cererilor cât mai aproape de cea optimă.

Descriere

În general, scopul programării este:

  • maximizați debitul , adică productivitatea întregului sistem, minimizând timpul în care resursa este inactivă;
  • căutați ordonarea cererilor care minimizează relația dintre timpul de serviciu (adică timpul necesar unei cereri pentru a fi satisfăcută) și timpul de „schimbare” (intervalul de timp dintre momentul în care este generată solicitarea și cel în care cererea este este satisfacut);
  • evita fenomenele nedorite precum foametea sau „așteptarea eternă” a unor cereri, verificabile în anumite condiții;
  • oferind utilizatorului sistemului percepția că solicitările sunt satisfăcute în același timp.

De fapt, există multe cerințe care pot fi luate în considerare, de asemenea, în funcție de problema specifică pe care programatorul trebuie să o gestioneze: există planificatoare care se ocupă cu împărțirea timpului de utilizare a procesorului la un proces, planificatoare care gestionează cererile de citire / scriere. un periferic, chiar și algoritmii de înlocuire a paginii de memorie trebuie să fie considerați planificatori .

Procesor de planificare pe termen scurt (dispecer)

Este o componentă fundamentală a sistemelor de operare multiproces și, cu siguranță, cel mai răspândit și critic exemplu de planificator . Este capabil să facă procesorul unui computer să execute mai multe procese ( sarcini ) concomitent prin operația de planificare cu același nume prin diferite politici de planificare. Prin urmare, reprezintă managerul multitaskingului prin criterii de alocare a resurselor de stocare / procesare diferitelor procese și implementate la rândul lor prin diferite tipuri de algoritmi de planificare.

De fapt, calculatoarele cu procesor sunt în general capabile să execute un program odată, astfel încât, pentru a coexista mai multe sarcini, este necesar să utilizați un programator . În detaliu, planificatorul se ocupă de avansarea unui proces întrerupând temporar altul, realizând astfel o comutare a contextului în cadrul ciclului procesorului . Există diferiți algoritmi de planificare care vă permit să alegeți cât mai eficient ce sarcină să continuați: de exemplu, nucleul Linux din versiunea 2.4 are un planificator O (n) , în timp ce de la versiunea 2.6 are un algoritm de complexitate O (1) , care este capabil să determine într-un timp constant ce proces trebuie executat, indiferent de numărul de procese care așteaptă.

Există diferite modele de planificare:

  • Model cu o singură mașină.
  • Flow-shop (modelul lui Johnson).
  • Algoritm euristic Campbell, Dudek și Smith.
  • Magazin de locuri de muncă .

Programarea procesorului

Programarea este o operațiune foarte importantă pentru funcționarea corectă și eficientă a calculatorului. De fapt, nu numai că vă permite să rulați mai multe programe simultan, ci vă permite și să îmbunătățiți utilizarea procesorului. De exemplu, atunci când este necesară o operație de I / O, procesorul nu poate continua procesarea procesului în curs de desfășurare până când procesul nu este finalizat. Deoarece operațiunile I / O sunt mult mai lente decât procesorul, ar fi o risipă inutilă de resurse dacă procesorul ar rămâne blocat până la finalizare. Pentru a evita acest lucru, operațiile I / O sunt gestionate numai de sistemul de operare care, între timp, atribuie utilizarea procesorului unui alt proces. Acest lucru maximizează utilizarea resurselor sistemului.

Este important să se facă distincția între programarea cu drept de prim refuz ( programare preventivă ) și programarea fără drept de prim refuz ( programare non-preventivă sau cooperativă). În primul caz, programatorul poate intra în posesia procesorului din proces chiar și atunci când acesta ar putea continua în execuția sa. În al doilea caz, totuși, planificatorul trebuie să aștepte finalizarea procesului sau schimbarea stării sale de la executare la așteptare.

Există diferiți algoritmi de planificare care iau în considerare diverse nevoi și care pot fi mai potrivite în anumite contexte decât în ​​altele. Alegerea algoritmului de utilizat depinde de cinci criterii principale:

  • Utilizarea procesorului: CPU (adică procesorul) trebuie să fie activ cât mai mult posibil, adică posibilele perioade de nefuncționare trebuie să fie reduse la minimum.
  • Transfer: Numărul de procese finalizate într-un anumit timp.
  • Timp de finalizare: timpul care trece între depunerea unui proces și finalizarea executării acestuia.
  • Timp de așteptare: timpul în care un proces gata de rulare așteaptă CPU (timpul de așteptare).
  • Timp de răspuns: timpul care trece între trimiterea procesului și obținerea primului răspuns.

Pentru a analiza algoritmii care vor fi prezentați ulterior, va fi utilizat criteriul timpului mediu de așteptare al proceselor luate în considerare.

Obiective de programare

Un algoritm de planificare are următoarele obiective:

  • Corectitudine : procesele de același tip trebuie să aibă tratamente similare
  • Echilibru : toate părțile sistemului trebuie exploatate

Mai mult, trebuie făcută o distincție între sistemele batch și sistemele interactive . În prima, debitul trebuie maximizat și timpul de întârziere trebuie minimizat. În al doilea sistem interactiv, timpul de răspuns trebuie să fie minim posibil pentru a da utilizatorului ideea de continuitate și proporționalitatea trebuie respectată, adică timpul de răspuns trebuie să fie proporțional cu complexitatea acțiunii.

Model cu o singură mașină (modelul Karg și Thompson)

Pașii algoritmului:

  1. Selectați aleatoriu două lucrări .
  2. Selectați o lucrare nouă și încercați să o aranjați în secvența curentă.
  3. Pentru fiecare poziție testată, calculați setarea generală.
  4. Alocați lucrarea în poziția care garantează cele mai mici timpi de instalare .
  5. Dacă mai sunt lucrări de alocat, treceți la pasul 2, în caz contrar, terminați.

FCFS

Algoritmul FCFS ( primul venit, primul servit ) este un tip de algoritm FIFO : execută procesele în aceeași ordine în care sunt trimise la sistem. Primul proces care se execută este exact cel care necesită mai întâi utilizarea procesorului. Următoarele sunt puse la dispoziție de îndată ce acest lucru și-a terminat execuția și la fel se întâmplă ulterior pentru toate celelalte locuri din coadă. Acest tip de algoritm este foarte simplu de implementat, dar de obicei nu este foarte eficient, cel puțin având în vedere timpul mediu de așteptare.

De fapt, să luăm de exemplu trimiterea în ordinea următoarelor procese cu următoarea durată exprimată în milisecunde:

  • p1: 10
  • p2: 4
  • p3: 2

Acestea vor fi executate în aceeași ordine: p1 → p2 → p3

Procesul p1 nu așteaptă nimic, deoarece începe imediat să ruleze. Procesul p2 așteaptă 10 milisecunde și p3 14. Prin urmare, timpul mediu de așteptare este (0 + 10 + 14) / 3 = 8 milisecunde. Există apoi un efect de convoi, caracterizat prin faptul că mai multe procese scurte așteaptă încetarea unui singur proces mai substanțial. Un rezultat decisiv diferit de cel obținut, sub formă teoretică, de algoritmul optim SJF (Shortest Job First) egal cu (0 + 2 + 6) / 3 = 8/3 milisecunde numai.

Cu toate acestea, dacă procesele sunt legate de CPU și sunt lungi, FCFS rămâne cel mai bun algoritm.

RR

Algoritmul de planificare RR ( round-robin ) este un anumit algoritm preventiv care execută procesele în ordinea sosirii, precum FCFS, dar preîntâmpină procesul de execuție, plasându-l la sfârșitul cozii proceselor în așteptare, dacă execuția durează mai mult decât „setul de timp” setat și care permite executarea să continue la următorul proces în așteptare.

De exemplu, presupunând că există următoarele procese în coadă cu o durată relativă în milisecunde și durata stabilită de 20 ms:

  • p1: 30
  • p2: 15
  • p3: 60
  • p4: 45

Acestea vor fi executate în următoarea ordine:

  • p1 (întrerupt după 20 ms, mai rămân încă 10)
  • p2 (își încheie execuția deoarece durează mai puțin de 20 ms)
  • p3 (întrerupt după 20 ms, mai rămân 40)
  • p4 (întrerupt după 20 ms, rămân încă 25)
  • p1 (își încheie execuția deoarece a durat mai puțin de 20 ms)
  • p3 (întrerupt după 20 ms, mai rămân încă 20)
  • p4 (întrerupt după 20 ms, mai rămân încă 5)
  • p3 (își încheie execuția deoarece avea nevoie de exact 20 ms)
  • p4 (își termină propria execuție)

Performanța acestui algoritm este, prin urmare, influențată de timpul mediu de așteptare, deși permite tuturor proceselor să câștige controlul procesorului și astfel se evită problema așteptării nedeterminate ( foamete ).

Impactul schimbărilor de context frecvente trebuie, de asemenea, luat în considerare. Prin urmare, este necesar să se calculeze corect durata optimă a timpului pentru a se asigura că incidența modificărilor de context este destul de limitată, precum și timpii de așteptare. Se poate stabili că, pentru o funcționare optimă, secvențele operațiilor CPU ar trebui să fie mai scurte decât timpul stabilit în aproximativ 80% din cazuri.

În acest caz, discursul mediu este interesant, deoarece este mult mai stabil decât apare în celelalte strategii. În acest caz, media trebuie calculată prin adăugarea celor 4 diferențe dintre momentul final de execuție a procesului și explozia acestuia. Mergând, așadar, să reprezentăm grafic progresul proceselor de la p1 la p4, observăm că p1 se termină la instant 85, p2 la instant 35, p3 la instant 145, p4 la instant 150. Adăugând diferențele pe care le vom avea [(85-30 ) + (35-15) + (145-60) + (150-45)] / 4. Media rezultată este de 66,25 ms (Hold Time).

SJF

Algoritmii SJF ( cea mai scurtă lucrare mai întâi ) pot fi atât non-preventivi (SNPF), cât și preventivi (SRTF).

Nemaiputând cunoaște timpul pentru care jobul va ocupa procesorul (din cauza problemei de oprire ), sistemul de operare va folosi datele procesării anterioare. Pentru a face acest lucru, se folosește formula:

Unde (0 <= α <= 1).

În special:

  • (istoria recentă nu este luată în considerare)
  • (contează doar ultima valoare reală a rafalei CPU)

SNPF

Algoritmul SNPF ( Shortest Next Process First) (SNPF) așteaptă întotdeauna procesul cu cel mai scurt timp de execuție printre cei care așteaptă să ruleze. Să luăm de exemplu faptul că următoarele procese au fost trimise în același timp, cu timpul lor de execuție respectiv în milisecunde:

  • p1: 10
  • p2: 2
  • p3: 6
  • p4: 4

Procesele sunt executate în următoarea ordine: p2 → p4 → p3 → p1

Nu ținând cont de timpul necesar pentru schimbarea contextului , procesul p2 nu așteaptă nimic, deoarece începe să ruleze imediat, p4 așteaptă 2 milisecunde, deoarece începe să ruleze imediat după p2, apoi p3 așteaptă 6 milisecunde și p1 așteaptă 12. Media timpul de așteptare este egal cu (0 + 2 + 6 + 12) / 4 = 5 milisecunde.

Se poate demonstra că acest algoritm este optim, deoarece permite întotdeauna să obțină cea mai mică valoare medie a timpului de așteptare. Din păcate, nu este posibil să-l aplicăm, deoarece nu este posibil să știm în avans cât va dura execuția procesului. Cu toate acestea, se poate încerca să-l prezicem, deoarece este probabil să fie similar cu cele anterioare.

O tehnică frecvent utilizată este utilizarea mediei mobile exponențiale : unde este este estimarea celei de-a n-a execuții a procesului, estimarea actuală e este ponderea care trebuie atribuită trecutului procesului și în general pentru există o aproximare corectă a comportamentului procesului și un rezultat acceptabil.

SRTF

Algoritmul SRTF ( Shortest Remaining Time First ) diferă prin faptul că, atunci când este trimis un nou proces a cărui durată este mai mică decât timpul necesar procesului de execuție pentru a-și încheia sesiunea, programatorul efectuează un comutator de context și atribuie utilizarea procesorului noului proces (algoritm preventiv - preventiv). Avantajul este o gestionare optimă a timpului mediu de așteptare , deoarece procesele cu timpi de execuție scurți sunt executate foarte rapid. Printre dezavantajele potențiale, ca și în cazul SRT, există fenomenul de înfometare a proceselor, deoarece procesele cu timpi de execuție rămași lungi ar putea aștepta la nesfârșit dacă se adaugă continuu procese cu durată rămasă mai scurtă.

HRRN

Algoritmul HRRN ( Higher Responsive Ratio Next ) este utilizat pentru a preveni îmbătrânirea, adică așteptarea excesivă pentru procesele foarte lungi, suprascrise de cele mai scurte prin SNPF și SRTF și se bazează pe timpul de așteptare al unui proces folosind formula unde este este timpul de așteptare și următoarea creștere estimată de CPU (consum de CPU ).

Feedback pe mai multe niveluri

Neputând estima cu exactitate timpul de execuție al unui proces atunci când acesta intră în sistem, există posibilitatea de a estima timpul scurs. Conceptul de feedback este introdus conform căruia procesele care au petrecut cel mai mult timp în sistem sunt penalizate. Planificarea feedback-ului pe mai multe niveluri (sau feedback-ul cu cozi multiple) este o programare bazată pe cuantă în timp și utilizează un mecanism de prioritate dinamică. Când un proces intră în sistem, i se atribuie o prioritate conform unor criterii prestabilite și este plasat într-o coadă cu o durată fixă ​​de timp. Dacă procesul de execuție își încheie cuantumul timpului, acesta este mutat într-o coadă cu un cuantum timp mai mare, dar cu o prioritate mai mică.

Fiecare coadă este tratată prin intermediul algoritmului round-robin , toate, cu excepția ultimei, care este servită prin FCFS. Caracteristici:

  • Favorizează procesele mai scurte;
  • Cu unele precauții este posibil să se evite condițiile de foame .

FSS

Algoritmul FSS ( Fair share scheduling ) colectează procesele în grupuri, deci este posibil să aveți un control mai larg asupra distribuției resurselor de calcul.

Programarea rețelei

În contextul rețelelor de telecomunicații, într-un mod foarte asemănător cu contextul IT, termenul „ planificare ” indică procesul, implementat de planificator la ieșirea unui nod de comutare a pachetelor , pentru a selecta și atribui dreptul potrivit diferitelor priorități posibile transmiterea la diferitele cozi posibile ( tampon ) de pachete în aglomerație, asigurând conformitatea cu parametrii calității serviciului (QoS) care trebuie oferite utilizatorului pentru diferitele tipuri de trafic de intrare.

Bibliografie

  • Sisteme de operare, concepte și exemple (A. Silbershatz, P. Baer Galvin, G. Gagne, 2003, editor Pearson Educational , ISBN 8871921402 ). Sisteme de operare, Management de proces, Management de memorie, I / O.
  • Architecture of Processing Systems, volumul 1 (F. Baiardi, A. Tomasi și Marco Vanneschi, 1988, Franco Angeli Edizioni , ISBN 882042746X ). Fundamente, firmware, arhitecturi paralele.
  • Architecture of Processing Systems, volumul 2 (F. Baiardi, A. Tomasi, Marco Vanneschi, 1987, Franco Angeli Edizioni, ISBN 882042746X ) Sisteme de operare, multiprocesor și distribuite.

Elemente conexe

linkuri externe