Monoprogramarea, Mediul cu multiprogramarea

Planificarea lucrarilor

In acest caz ne referim la notiunea de batch-processing (preluarea pe laturi) in care planificatorul de job-uri primeste controlul pentru a selecta, din multimea lucrarilor (job-urilor) prezente in sistem, urmatoarea lucrare care va incepe. Sa fie executata, in acest caz, se creaza procesele corespunzatoare lucrarii si apoi sunt trecute in starea "pregatit pentru executie" dupa ce lucrarea respectiva primeste resursele de care are nevoie. Planificatorul tine gestiunea lucrarilor din sistem. Pentru aceasta au nevoie de structuri de date - blocul de control al job-urilor.

(Job Control Block)

Structurile de acest fel se creaza in mod dinamic atunci cand lucrarile vin in sistem. Ori de cate ori anumite resurse sunt cerute concurent din mai multe locuri este necesara aplicarea unei politici de planificare. In acest caz, obiectivele urmarite pot fi contradictorii:

Sistemul sa ruleze cat mai multe job-uri (deci se vor rula si vor fi favorizate job-uri scurte)

Procesul sa fie cat mai mult folosit si cat mai optim (in acest caz sunt favorizate job-urile lungi)

Toata lumea sa fie multumita in egala masura, deci trebuie sa se ruleze toate procesele

Obiectivele politicilor de planificare

Disponibilitatea utilizarii in sistem a unor resurse sarace sau scumpe (de ex sunt prioritare lucrarile ce folosesc plotter-ul)

Disponibilitatea resurselor fundamentale ale sistemului (cu cat o lucrare va cere mai multa memorie si mai mult timp pentru ea, va astepta mai mult)

Asigurarea echilibrului sistemului (trebuie sa fie mixate in multiprogramare lucrari ce utilizeaza procesorul intens cu lucrari ce utilizeaza dispozitivile de I/O pentru ca nici procesorul si nici dispozitivele de I/O sa nu fie nefolosite)

Asigurarea unui pret optim al serviciilor

Garantarea serviciilor asigurate de sistem (de ex. daca sistemul dispune de 4 benzi magnetice si se primesc mai multe lucrari care folosesc fiecare o banda magnetica, se va refuza o lucrare care necesita 4 banzi magnetice, dar cand este rulata ca nu se poate rula o alta in sistem, odata acceptata sistemul trebuie sa garanteze executia lucrarilor - indiferent de timpul de asteptare)

Garantarea termenelor de executie a lucrarilor

Monoprogramarea

In acest caz nu se partajeaza resurse cu nimeni. Una din cele mai simple politici de planificare este FCFS (first come, first save).

Se considera urmatorul caz:

Rezultatele sunt sintetizate in tabelul:

In aces caz:  T_FCFS=26 ; T_A=1/A* ΣT_i ; ΣT_i=78.

Operatiile de I/O ale unei lucrari nu pot fi suprapuse cu calculele altei lucrari ca in cazul multiprogramarii. In acest caz procesorul sta. Un criteriu de performante al algoritmului il reprezinta fluxul prin sistem (numarul de job-uri pe unitatea de timp).

Timpul de raspuns poate fi vazut ca o suma intre timpul cat lucrarea a asteptata pana cand a fost luata in considerare si timpul de rulare in unitatea centrala (procesorul a rulat), cat si timpul operatiilor de I/O (cat procesorul a stat blocat).

Media timpului de raspuns reprezinta aprecierea medie a algoritmului de planificare folosit, adica in exemplul nostru:

T_A=1/n * ΣT_i = 78/3 = t_mediu =26

Sa consideram un alt algoritm care are scopul cresterii fluxului prin sistem, in care se ruleaza cel mai scurt job primul (Shortest Job First - SJF). Consideram aceeasi colectie de lucrari ca si in primul caz. Modul de planificare va fi urmatorul:

ΣT_i=72                 T_A=72/3=24<T_FCFS

Sa consideram si cazul in care se presupune ca se cunosc lucrarile care vor veni pentru rulare, caz in care se asteapta 4 unitati de timp pentru sosirea tuturor joburilor in sistem si apoi se ruleaza job-urile cele mai scurte:

T_SJFFK=19,33<T_SJF

Mediul cu multiprogramarea

In acest caz rezultatele vor fi mult mai bune, rulandu-se mai multe programe in paralel. Cand unul face operatii de I/O si se blocheaza, un altul foloseste procesorul. Pe termen scurt algoritmul de planiicare este Round-Robin in care fiecare proces primeste o cuanta de executie si apoi trece in coada. Pe un interval mai mare de timp, toate programele au rulat si si-au impartit timpii in mod egal.

Consideram o colectie de 5 lucrari. Avem:

B=BLOC

Ri=timpul de rulare in monoprogramare

Daca presupunem ca lucrarile ar fi pregatite in ordinea FCFSin monoprogramare avem:

T_FCFS=9,4; W_FCFS=4,06

Atentie! Timpul de raspuns nu este un parametru foarte corect in aprecierea performantelor planificarii. O lucrare care a fost rulata imediat si a durat o ora are timpul de raspuns 1h, o lucrare servita imediat si care a durat 4h are timpul de raspuns 4h dar nu este un parametru corect. Pentru aceasta se foloseste timpul de raspuns ponderat definit ca raportul dintre timpul de raspuns si timpul de rulare.

In cazul multiprogramarii Round-Robin se considera urmatoarele ipoteze:

a)           Resursele sunt infinite (cum vine o lucrare va fi executata imediat)

b)          Operatiile de I/O nu se suprapun cu cele de calcul

Datorita planificarii Round-Robin, daca intr-o ora lucreaza o singura lucrare, ea consuma 1h din timp, daca sunt planificate 2 lucrari, fiecare consuma cate o jumatate de ora.

Head-way = fractiune din timp utilizata efectiv de fiecare lucrare

Rezultatele din diagrama se regasesc in urm tabel:

t_M de raspuns = 9.8; w_M=2.73

Lucrarile cu w mic au fost tratate mai bine

In continuare analizam cazul multiprogramarii cu suprapunere a operatiilor de I/O. Sa consideram 2 lucrari, fiecare ruland in monoprogramare 16 unitati de timp, din care 25% din timp este pierdut cu operatiile de I/O. In acest caz, prima lucrare are timpul de raspuns 16, a doua 32, iar t_M=24 si w=1,5. Daca lucrarile sunt reluate in multiprogramare Round-Robin, vor exista momente cand procesorul va fi nefolosit. Daca pe masina punem sa ruleze un singur job, procesorul va sta nefolosit 25% din timp, daca sunt 2 job-uri, procesorul sta nefolosit 4%, pentru 3 joburi avem 0,4%, iar pentru 5 joburi avem 0%. In procent de 96% procesorul ruleaza 2 lucrari in mod egal, deci fiecare avanseaza cu 48%.

Daca timpul total de unitate centrala este 12 pt fiecare job, atunci timpul de terminare este 12/0,48 = 25; w=1,56.

In monoprogramare, fiecare job are 16 unitati de timp, 4 unitati de I/O si 12 de calcul, deci timpul mediu este 24.

Concluzia este ca multiprogramarea este rea pentru utilizator, dar aduce performante in utilizarea sistemului.

Daca masina are resurse finite acestea se reflecta in timpul de raspuns, performantele scazand. In exemplul de mai sus, presupunem ca imprimanta este virtualizata, iar problemele apar datorita memoriei. Daca consideram ca exista 5 blocuri de memorie disponibila, vom avea:

T_M=10.5

W_M=3.19