Tehnica Monoprogramãrii. Tehnica Multiprogramării.

Tehnici de exploatare a sistemelor de calcul

Tehnica de exploatare a unui sistem de calcul se referã la modalitãţile utilizate de sistemul de operare pentru planificarea execuţiei programelor şi pentru gestionarea resurselor solicitate.

Trebuie avute în vedere urmãtoarele aspecte legate de execuţia programelor:

• resursele sistemului sunt folosite neuniform în timpul execuţiei unui program: în orice moment al execuţiei unui program vor exista resurse neutilizate de cãtre acesta;
• caracterul secvenţial al execuţiei unui program impune o anumitã ordine în utilizarea resurselor; rezultã cã, la un moment dat, execuţia unui program poate fi condiţionatã de existenţa şi de disponibilitatea unei resurse solicitate;
• diferitele componente ale sistemului de calcul, care concurã la executarea unui program, au viteze de lucru diferite; asta înseamnã cã activitatea unei componente hardware poate sã fie temporizatã de viteza de lucru a alteia, cu care colaboreazã în timpul execuţiei programului (de exemplu, preluarea datelor de pe un suport de memorie externã este mult mai lentã decât prelucrarea lor, de exemplu utilizând UAL).

Rezultã cã, în general, se poate obţine o utilizare mai eficientã a resurselor în condiţiile partajãrii resurselor între mai multe programe care se executã concurent. În aceste condiţii se poate obţine o reducere a timpilor de neutilizare pentru fiecare resursã din sistem şi o micşorare a timpului total de execuţie, pentru acelaşi volum de lucrãri executate.

Din acest motiv, s-au dezvoltat mai multe tehnici de exploatare a sistemelor de calcul, care sã asigure execuţia cât mai eficientã a programelor. Fiecare tehnicã de exploatare a sistemelor de calcul se particularizeazã prin obiectivele pe care şi le propune, în funcţie de care sunt definite componentele sistemului de operare cu rol în gestionarea resurselor, care fac parte din componenta de comandã şi control a sistemului de operare.

1. Tehnica Monoprogramãrii

Monoprogramarea este o tehnică de gestiune a lucrărilor ce presupune execuţia secvenţială a lucrărilor solicitate a se prelucra pe un sistem de calcul.

Caracteristicile acestei tehnici se concretizează în următoarele aspecte:

o       planificarea lucrărilor se realizează strict secvenţial intr-o ordine prestabilită;

o       fiecare lucrare are la dispoziţie toate resursele sistemului de calcul in momentul execuţiei;

o       fiecărei lucrări i se asociază un singur proces la un moment dat, astfel că pe durata operaţiilor de intrare/ieşire (care durează mult comparativ cu durata de execuţie a unităţii centrale de prelucrare), unitatea centrală de prelucrare aşteaptă terminarea acestor operaţii, conducand la creşterea duratei de execuţie a lucrărilor.

Obiectivul urmărit în cadrul acestei tehnici îl constituie reducerea timpului mediu petrecut de lucrare în system (automatizarea lansãrii în execuţie a lucrãrilor (programelor), pentru aceasta, lucrãrile sunt organizate secvenţial, în loturi de lucrãri şi lansate automat în execuţie).

Lansarea în execuţie a unei lucrãri se face, în cadrul lotului din care face parte, secvenţial, adicã respectând condiţiile:

• lucrare se lanseazã în execuţie numai dupã încheierea execuţiei lucrãrii care o precede;

• ordinea de lansare în execuţie a lucrãrilor este strict ordinea în care se aflã lucrãrile în lotul de lucrãri;
• la un moment dat, toate resursele sistemului sunt puse la dispoziţia lucrãrii aflate în execuţie.

Putem spune, deci, cã planificarea execuţiei lucrãrilor se face prin intermediul lotului de lucrãri. Acest mod de organizare a prelucrãrilor se numeşte prelucrare batch (pe loturi sau pachete), iar sistemele de operare care utilizeazã aceastã tehnicã de exploatare se numesc sisteme de operare batch (BPS - Batch Processing Systems).

Execuţia lucrărilor in monoprogramare

Lansarea în execuţie a lucrãrilor din lotul de lucrãri se face automat, sub controlul componentei sistemului de operare numitã monitor de înlãnţuiri.

Un program solicită pe parcursul execuţiei operaţii de intrare/ieşire; operaţiile sunt supervizate de către un procesor de comunicaţii numit canal, care transferă conţinutul intre memoria internă şi dispozitivele periferice de intrare/ieşire.

Dacă unitatea centrală de prelucrare întalneşte o instrucţiune de citire, atunci iniţiază execuţia unui proces de intrare către procesorul de comunicaţie, continuand-şi activitatea de prelucrare fără a se interfera cu activitatea canalului. Procesele de intrare/ieşire fiind mai lente, unitatea centrală de prelucrare va aştepta transferul datelor solicitate in vederea prelucrării lor ulterioare; dacă procesul de intrare s-a incheiat, unitatea centrală de prelucrare va fi sesizată de canal printr-o intrerupere.

Sincronizarea activităţilor dintre unitatea centrală de prelucrare şi procesorul de comunicaţie este redată în fig. 2.1.

Fig.2.1. Sincronizarea activităţilor dintre unitatea centrală de prelucrare ( CPU ) şi procesorul de

comunicaţie ( DMAC ) în monoprogramare

t1 - momentul iniţierii de către CPU a unei operaţii de intrare;

t2 - momentul in care CPU are nevoie de datele solicitate de la dispozitivul periferic de intrare,

pe care nu le are deoarece nu s-a terminat operaţia de citire;

t3 - se termină operaţia de citire şi se reia execuţia programului de către CPU cu datele solicitate;

t4 - momentul incheierii execuţiei programului.
Pentru aprecierea eficienţei utilizării acestor procesoare ( CPU, DMAC), se calculează randamentul de utilizare (în % ):

 

Deşi prezenţa canalului ameliorează productivitatea sistemului datorită simultaneităţii activităţii acestuia cu activitatea CPU (parţial sau total), există intervale de timp impuse de necesitatea sincronizării activităţilor in care CPU este în starea de aşteptare.

Modul de exploatare batch a sistemului de calcul a fost caracteristic perioadei pânã la sfârşitul anilor ’70, când suporţii de memorie externã ofereau, în general, posibilitatea organizãrii secvenţiale a datelor (banda magneticã reprezenta suportul principal de memorie externã).

În prezent, modul de exploatare în loturi poate fi folosit atunci când anumite seturi de prelucrãri se executã periodic, în aceeaşi ordine, şi când nu este necesarã coordonarea interactivã a execuţiei lor.

Exemplu: sub MS-DOS pot fi generate fişiere de comenzi care definesc o secvenţã de programe şi o ordine de execuţie a lor; un astfel de fişier de comenzi defineşte un lot de lucrãri care poate fi executat prin lansarea în execuţie a fişierului de comenzi.

Avantajul utilizãrii modului de prelucrare în monoprogramare este realizarea automatizãrii lansãrii în execuţie a lucrãrilor.

Inconvenientele sunt determinate de:

• timpul mare de rãspuns al sistemului (toţi utilizatorii primesc rezultatul prelucrãrilor numai dupã executarea întregului lot);
• eficienţa scãzutã în utilizarea resurselor sistemului (toate resursele sunt afectate, pe rând, câte unei singure lucrãri în execuţie).

Creşterea eficienţei sistemelor batch se poate realiza prin implementarea unor metode software care sã diminueze decalajul de performanţã între componentele hardware ale sistemului de calcul. De exemplu, pentru micşorarea timpului de aşteptare al UCP în cazul operaţiilor de intrare/ieşire, se pot folosi urmãtoarele soluţii:

• utilizarea bufferelor de intrare/ieşire. Acestea sunt zone din memoria internã dedicate pentru schimbul de informaţii cu echipamentele de intrare/ieşire. Schimbul de date cu echipamentele I/O se realizeazã în doi paşi:
• un pas rapid, între memoria internã şi buffer, sub controlul UCP
• un pas mai lent, la viteza echipamentului I/O, între buffer şi echipamentul I/O, sub controlul unitãţii de canal corespunzãtoare dispozitivului I/O; acest pas nu necesitã controlul UCP care, în acest timp, îşi poate continua activitatea.
• în sistemele moderne, viteza operaţiilor I/O se poate mãri utilizând funcţii cache de citire/scriere. Memoria cache a dispozitivului periferic poate fi o memorie dedicatã sau poate fi o zonã din memoria RAM. Transferul de date cu dispozitivul periferic se face prin intermediul memoriei cache, tot în doi paşi; diferenţa faţã de lucrul cu bufferele I/O constã în faptul cã, în cazul utilizãrii memoriei cache, apare funcţia de predicţie care stabileşte care este volumul de date, din vecinãtatea datelor care se transferã, care are cea mai mare probabilitate de a fi solicitat în urmãtorul interval de timp; aceste date vor fi transferate în avans, între dispozitivul I/O şi memoria cache. Programul care controleazã acest transfer şi care asigurã şi funcţia de predicţie face parte din sistemul de operare.

Exemplu: la MS-DOS, variantele mai mari de 5.0, este programul SMARTDRV; la Windows95 este programul VCache.

3.2. Tehnica Multiprogramãrii

Multiprogramarea este tehnica de exploatare a sistemelor de calcul care permite existenţa simultanã în memoria internã a mai multor programe care se executã concurent, în partiţii fixe de memorie, cu restricţia ca ele sã nu foloseascã în acelaşi timp aceeaşi resursã.

Multiprogramarea este o tehnică de gestiune a lucrărilor pe sistemele de calcul prin care sunt plasate mai multe lucrări simultan în memoria internă iar CPU comută între ele; din punct de vedere conceptual, multiprogramarea implică simultaneitatea a "n" procesoare pe un singur processor sau existenţa a "n" procesoare virtuale in cadrul unui singur procesor.

Caracteristicile de bază ale acestei tehnici constă în:

• existenţa simultană a mai multor lucrări în memoria internă;
• existenţă unui mecanism de trecere de la un program la altul astfel ca randamentul sistemului să fie ridicat;
• existenţa unui mecanism de protecţie între lucrări care să permită execuţia fiecăreia, fără afectarea celorlalte lucrări existente în memoria internă;
• existenţa unui mecanism pentru gestiunea resurselor fizice şi logice solicitate de către lucrările in execuţie (echipamente periferice, informaţii, etc.).

Obiectivul multiprogramãrii este de a face posibilã execuţia unui numãr mai mare de programe într-un interval de timp, prin optimizarea utilizãrii resurselor sistemului de calcul.

Multiprogramarea se poate aprecia ca o dezvoltare a sistemului de operare, iar folosirea

partajată a CPU de către lucrări, ca o execuţie concurentă (în realitate, partajarea este realizată pe intervale distincte).

Organizarea execuţiei în multiprogramare a lucrãrilor se face dupã urmãtoarele reguli:

• lucrãrile sunt organizate în loturi;
• fiecare lot de lucrãri are afectatã o partiţie fixã în memoria internã;

O partiţie de memorie trebuie sã fie o zonã contiguã de memorie, adicã o zonã de memorie formatã numai din locaţii de memorie adiacente. O partiţie are o anumitã lungime şi o adresã fixã.

• în cadrul fiecãrui lot, lucrãrile sunt executate secvenţial, fiind lansate automat în execuţie; pentru fiecare program lansat în execuţie se genereazã un proces în partiţia corespunzãtoare lotului;
• sub controlul sistemului de operare, UCP comutã de la o partiţie la alta, pentru a realiza executarea concurentã a proceselor; comutarea se face în momentul în care UCP nu este utilizatã de procesul respectiv (de exemplu, UCP aşteaptã terminarea unei operaţii I/O); comutarea între procese se face în urma unor evenimente interne proceselor care se executã (evenimente generate de procese);
• fiecare partiţie are asociatã o prioritate de execuţie;
• resursele sistemului de calcul sunt alocate proceselor, conform solicitãrilor acestora şi în funcţie de disponibilitatea resurselor; în cazul solicitãrii unei resurse care nu este disponibilã, procesul respectiv intrã în aşteptare, pânã la eliberarea resursei; ordinea de alocare a resurselor între procesele care solicitã aceeaşi resursã este determinatã de prioritatea de execuţie determinatã de prioritatea partiţiei (procesele cu prioritate mai mare au acces la aceeaşi resursã înaintea celor cu prioritate mai micã);
• sistemul de calcul dispune de un sistem de întreruperi, prin intermediul cãruia se semnaleazã apariţia unui eveniment care poate fi cauza comutãrii între procese.

Sistemele de calcul ce utilizează tehnica multiprogramării sunt prevăzute cu o componentă a sistemului de operare numită monitor de planificare a lucrărilor, care alege dintr-un grup de programe în ordinea sosirilor, pe acelea potrivit cărora timpul neocupat al CPU să fie minim; există o limită pentru numărul de lucrări ce pot fi executate simultan (dacă acest număr este depăşit, este invocată o procedură pentru selecţia lucrărilor, iar cele neselectate răman în aşteptare) funcţie de memoria afectată utilizatorilor.

Procesul de planificare are două funcţii distincte:

-         asigurarea priorităţii;

-         alocarea resurselor care utilizează prioritatea.

Algoritmii de planificare presupun că lucrările sunt ordonate pe bază de prioritate, sub forma

firelor de aşteptare. Alegerea unui anumit algoritm se va face după obiectivele urmărite; dintre

algoritmii frecvent utilizaţi în multiprogramare se menţionează:

STF Shortest proccessing Time First - lucrarea cu cel mai scurt timp de prelucrare este prima executată, urmăreşte minimizarea timpului de trecere prin sistem a lucrărilor ce durează puţin;

LTF Longest proccessing Time First - lucrarea cu cel mai lung timp de prelucrare este prima executată, urmăreşte reducerea timpului total de execuţie a lucrărilor;

SMF Smallest Memory requirment First - lucrarea ce necesită cel mai mic spaţiu de memorie este prima executată;

LMF Largest Memory requirment First - lucrarea ce necesită cel mai mare spaţiu de memorie este prima executată;

FIFO First Input First Output - lucrările sunt executate in ordinea lansării in execuţie;

LIFO Last Input First Output - lucrările sunt executate in ordinea inversă lansării in execuţie;

Round-Robin sau planificarea circulară, fiecare lucrare avand alocată o cuantă de timp (interval de 1-10 ms), după care controlul este comutat la următoarea lucrare.

Sincronizarea activităţii CPU cu activitatea procesorului de comunicaţie este redată în fig. 2.2. presupunand existenţa a trei programe încărcate in memoria internă (P1,P2,P3) la un moment dat, ce sunt executate de CPU conform algoritmului Round-Robin.

Fig.2.2. Sincronizarea activităţilor dintre CPU şi procesorul de comunicaţie in multiprogramare

t1 - momentul iniţierii unei operaţii de intrare/ieşire de către CPU pentru P1;

t2 - momentul cand P1 are nevoie de transferul datelor solicitate la t1 care nu sunt disponibile deoarece nu s-a terminat operaţia de intrare/ieşire, comutand astfel la execuţia programului următor P2;

t3 - terminarea operaţiei de intrare/ieşire pentru P1 (CPU este ocupată cu P2);

t4 - iniţierea operaţiei de intrare/ieşire pentru P2; canalul fiind liber, trece la execuţia solicitată;

t5 - momentul cand P2 necesită datele solicitate; operaţia de intrare/ieşire nu s-a incheiat, deci CPU comută la P3;

t6 - iniţierea unei operaţii de intrare/ieşire de către P3; canalul este ocupat, trece operaţia in aşteptare;

t7 - se termină operaţia de intrare/ieşire iniţiată de P2 şi poate fi lansată operaţia de intrare/ieşire

iniţiată de P3 (t8);

t9 - momentul cand CPU devine liberă de la P3 şi avand datele solicitate de P1 incă de la momentul t3, reia execuţia P1;

t10 - se incheie execuţia P1 şi CPU comută la P2;

t11 - se incheie execuţia P2 şi CPU aşteaptă deoarece nu s-a incheiat operaţia de intrare/ieşire iniţiată de P3;

t12 - se incheie operaţia de intrare/ieşire şi se redă controlul CPU pentru P3;
t13 - sfarşit P3.

Funcţiile pe care le asigurã un sistem de operare în multiprogramare sunt:

• lansarea automatã în execuţie a lucrãrilor unui lot, prin intermediul monitorului de înlãnţuiri, ca la sistemele în monoprogramare;
• gestionarea execuţiei concurente a proceselor încãrcate în cele n partiţii, prin alocarea succesivã a UCP fiecãruia; comutarea între procese are loc la momentele determinate de procese; componenta sistemului de operare care gestioneazã comutarea între procese a UCP este numitã planificator al procesorului (CPU Scheduller);
• gestionarea alocãrii aceleiaşi resurse între mai multe procese, conform prioritãţii partiţiilor;
• asigurarea protecţiei între lucrãrile încãrcate în memoria internã pentru execuţie, astfel încât execuţia unui proces sã nu altereze prezultatele execuţiei celorlalte procese.

Se observã o creştere a complexitãţii sistemului de operare, comparativ cu sistemele de operare în monoprogramare.

Ca efect al utilizãrii multiprogramãrii se poate constata:

• utilizare mai eficientã a resurselor sistemului, în primul rând a resurselor critice: UCP şi memoria internã

• creşterea volumului de lucrãri executate într-un anumit interval de timp.

Numãrul şi dimensiunea partiţiilor din sistem depinde de capacitatea memoriei interne. Rezultã de aici principalul inconvenient al multiprogramãrii: numãrul şi dimensiunea programelor care pot fi executate concomitent este limitat de numãrul şi dimensiunea partiţiilor definite în sistem. Pentru înlãturarea acestui inconvenient se poate recurge la creşterea capacitãţii memoriei (prin utilizarea procedeului de swapping).

Problema 1:

1.      Se consideră un sistem de calcul cu trei grade de multiprogramare. Pentru programele respective se cunosc următoarele:

- duratele de execuţie estimate pentru programele P1, P2, P3 sunt:

t1ex=7c

t2ex=6c

t3ex=9c

- momentele iniţierii operaţiilor de intrare/ieşire:

t1i=4c

t2i=3c

t3i=5c

- duratele operaţiilor de intrare/ieşire:

t1i/o=6c

t2i/o=5c

t3i/o=10c

Între momentul iniţierii operaţiilor de intrare/ieşire şi momentul cand programele respective solicită datele citite o cuantă de timp (1c).

Se cere: să se calculeze randamentele de utilizare a CPU şi canalului pentru următoarele discipline:

a. Round-Robin;

b. planificare cu priorităţi astfel: prioritatea lui P3 > prioritatea lui P1 > prioritatea lui P2;

c. algoritmul SJNE (Short Job Next Executed).