MULTIPROGRAMARE SI MULTITASKING
3.1. Introducere
Timpul constituie una din cele mai importante resurse ale unui sistem de calcul si este resursa esentiala in sistemele de timp real. Pentru a obtine eficienta maxima a unui sistem de calcul este necesar a mentine permanent ocupata unitatea sa centrala de prelucrare. Orice stare de repaus a CPU duce la risipa timpului de calcul.
Pentru maximizarea performantelor sistemelor de calcul s-au dezvoltat tehnici sofisticate, ale caror concepte de baza vor fi examinate in acest capitol. Pentru claritate se vor folosi exemple, indeosebi din domeniul sistemelor cu functionare in timp real, dar si din cel al sistemelor multi-utilizator cu divizarea timpului (multi-user time-sharing systems).
3.1.1. Multiprogramarea in sistemele cu divizarea timpului
In regimul de multiprogramare unitatii centrale de prelucrare i se cere sa execute mai multe programe, scrise de catre programatori diferiti si cu obiective diferite. Un mod naiv de gestiune a CPU este ilustrat de figura 3.1.b. si fig. 3.1.c. Cele trei programe, A, B, si C, sint executate secvential, intrucit nici unul din ele nu poate sa isi inceapa executia daca exista un alt program aflat in curs de executie, dar neterminat. Activitatile ce au loc in sistem pe durata executarii programelor pot fi grupate in doua categorii: activitati de prelucrare si activitati de I/O. Pentru simplificarea desenului perioadele de timp au fost facute mai lungi si mai putin numeroase decit in sistemele de timp real. Timpul total de terminare a celor trei programe este de 340 unitati, din care 210 sint timp CPU. Deci unitatea centrala a fost utilizata in proportie de 62%, risipindu-se 38% din capacitatea de calcul.
Pentru cresterea eficientei se poate considera situatia din figura 3.1.c, in care executia programelor este intercalata. Imediat ce unitatea centrala ar trebui sa intre in repaus (intrucit programul in curs de executie intra in perioada de activitate I/O), aceasta este alocata executiei unui alt program, care nu se afla in faza I/O. Executia primului program este reluata cind si-a terminat faza I/O si cind CPU tinde sa devina inactiva. In aceasta noua schema timpul total de executie este de 240 unitati, iar gradul de utilizare a CPU este de 87,5%. Mai trebuie remarcat faptul ca, desi timpul total de rulare a celor trei programe este mai scurt ca in cazul b, executia fiecaruia din cele 3 programe in cazul c dureaza mai mult decit in cazul b. Altfel spus, timpul de raspuns pentru un utilizator individual creste, dar cresterea este suficient de mica pentru a nu deranja in regim de multiprogramare.
Fig. 3.1. Executia programelor in sistemele cu monoprogramare (a) si multiprogramare (b)
3.1.2. Functionarea multitasking in aplicatiile de timp real
Cu totul altfel se pune problema in sistemele functionind in timp real, in care unele din taskuri nu pot fi intirziate peste anumite limite. O alta diferenta fata de multiprogramare este data de faptul ca taskurile unui sistem in timp real sint coordonate in scopul indeplinirii unor conditii impuse. Diferentele mentionate permit, totusi, folosirea acelorasi mijloace de baza pentru executia intercalata a programelor.
Intercalarea apare ca naturala in sistemele functionind in timp real, deoarece insusi mecanismul de intreruperi ofera o metoda de alternare a executiei programului cu aceea a rutinei de tratare a intreruperilor. Se considera un sistem destinat citirii la intervale constante de timp a esantioanelor unui semnal obtinute cu ajutorul unui convertor analog numeric. La fiecare moment de esantionare rutina care trateaza intreruperea de la convertor (A) trebuie sa testeze incadrarea esantionului intre limite impuse; in caz afirmativ valoarea este memorata intr-un tampon si, la acumularea in acesta a unui numar de 5 esantioane, controlul este transferat rutinei B. B efectueaza calculele necesare asupra acestor esantioane; cind un esantion nu se incadreaza in limitele specificate se activeaza o scurta rutina de alarmare (C), care nu blocheaza celelalte activitati. In fig. 3.2. se poate vedea un exemplu de desfasurare a calculelor. Se observa ca executia rutinei B este intercalata cu executia celorlalte programe.
Fig. 3.2. Executia diferitelor taskuri intr-un sistem in timp real
3.1.3. Mijloace de sprijin pentru multiprogramare.
Din exemplele de mai sus se constata ca executia eficienta a mai multor programe pe acelasi sistem necesita disponibilitatea in cadrul acestuia a urmatoarelor mecanisme:
a) salvarea si restaurarea starii programelor pentru a permite intreruperea si reluarea corecta a executiei,cerute de executiile intercalate;
b) excluderea mutuala, care permite utilizatorilor sa foloseasca in comun o resursa, evitind problemele generate de posesia multipla a resursei;
c) sincroniz 111b17b area, pentru a coordona activitatile taskurilor care interactioneaza ;
d) activarea si dezactivarea taskurilor, permitind pornirea si oprirea unui anumit task.
In cele ce urmeaza se discuta implementarea acestor mecanisme in structurile moderne de microprocesoare.
3.2. Procese si procesoare.
Mecanismele
cerute de executia eficienta a diverselor programe pe acelasi sistem nu pot fi
programate de catre programatorul de aplicatii, deoarece ele trateaza
evenimente impredictibile la momentul compilarii. In astfel de evenimente se
pot include: aparitia de esantioane care nu se incadreaza in gama stabilita,
numarul si caracteristicile celorlalte programe (a caror executie este
intercalata cu executia programului in discutie ) etc. Deci, sistemul de operare este cel care
trebuie sa ofere facilitatile de baza necesare implementarii corecte si comode
a sistemelor cu multiprogramare. Fig. 3.3. prezinta structura sistemului de
operare. Nucleul sistemului de operare (OSK - Operating System Kernel)
este format dintr-o colectie de proceduri care implementeaza cele patru
mecanisme din paragraful anterior, care pot fi utilizate de celelalte taskuri
indicate in figura pentru a realiza coordonarea activitatilor lor. Totusi, nu
toate aceste taskuri sint in mod necesar dedicate implementarii activitatilor
legate de aplicatii. Unele dintre ele fac parte din sistemul de operare (de exemplu
cele destinate gestiunii fisierelor). Cu toate acestea, atit taskurile sistem,
cit si cele de aplicatii folosesc aceleasi functii si doar prioritatile
asociate sint elementele ce le deosebesc in tratarea de catre OSK.
Fig. 3.3. Structura sistemului de operare
In general, taskurile din figura sint numite procese. Fiecare proces este compus din trei parti principale:
a) O baza de date, pastrata, de regula, in memoria principala, care contine toate datele si spatiul de memorie necesare pentru reprezentarea variabilelor programului, ca si celelalte variabile cerute de executarea calculelor aferente.
b) Codul care implementeaza algoritmul executat de catre proces.
c) Mediul in care se executa procesul. Termenul de "mediu" indica o serie de atribute ale procesului, adesea gestionate de catre sistemul de operare, care sint necesare executiei corecte. Exemple de atribute pot fi descriptorii zonelor de memorie rezervate procesului, cu drepturile de acces pentru fiecare din ele. Problema va fi reluata ulterior.
Un numar de procese pot avea parti comune: aceeasi secventa de instructiuni sau parti ale bazelor de date. In prima clasa intra compilatoarele in sistemele cu multiprelucrare, folosite in comun de mai multi utilizatori. In aceste cazuri, in memoria sistemului se incarca o singura copie a compilatorului, iar fiecarui utilizator i se aloca zone de date si medii distincte, fapt ce evita multiplicarea copiilor compilatorului. Procesele care folosesc in comun acelasi cod se numesc "instantanee" sau treceri (instances) ale aceluiasi program. Utilizarea in comun de date de catre mai multe procese se manifesta cind utilizatorul doreste sa implementeze transferul de date intre procese printr-un set de variabile vizibile de catre toate procesele aflate in comunicatie.
Situatia este similara cu cea a variabilelor globale din programele Pascal, care sint vazute din si pot fi utilizate de catre toate procedurile declarate in cadrul acestor programe. In sistemele cu multiprelucrare legarea variabilelor comune nu se face precum in Pascal,ci de catre sistemul de operare cu informatiile continute in directive ale utilizatorului.
3.3. Executia intercalata a proceselor.
Instructiunile ce compun codul unui proces se executa secvential, cite una la anumite momente de timp. Daca sistemul de intreruperi nu este dezactivat, executia procesului curent poate fi intrerupta la sfirsitul unei instructiuni masina pentru a permite comutarea CPU catre rularea unui alt proces. Devine, deci, posibila intercalarea instructiunilor unui proces intre doua instructiuni ale altui proces.
Efectul la nivel macroscopic al intercalarii executiei diferitelor procese consta in senzatia ca unitatea centrala de prelucrare acorda intreaga sa atentie in paralel tuturor proceselor. Utilizind o scala mai fina a timpului se constata, totusi, ca microprocesorul executa, la un moment dat, un singur proces. Pentru asemenea sisteme se mai foloseste si denumirea de pseudoparalele.
De curind, au fost puse pe piata [10],[11] mai multe microcalculatoare destinate utilizarii in configuratii multiprocesor (fig. 3.4). Sistemele, continind mai multe unitati centrale de prelucrare, permit implementarea proceselor cu adevarat paralele (spre deosebire de cele pseudoparalele), intrucit fiecare procesor poate executa un proces in paralel cu alte procesoare. Sistemul nu rezolva problemele excluderii mutuale si ale sincronizarii. De asemenea, chiar si pentru instructiunile multiprocesor exista un anumit grad de pseudoparalelism.
Fig.3.4. Sistem multiprocesor cu magistrala comuna
3.4. Comutarea proceselor
3.4.1. Starile procesului
Pentru a obtine pseudoparalelismul este necesara comutarea CPU intre doua procese. Ea consta din doua faze simetrice : salvarea contextului procesului intrerupt si restaurarea acestuia la terminarea intreruperii. O problema esentiala a implementarii este definirea starii unui proces, care este compusa din toate informatiile necesare reluarii ulterioare corecte a operarii procesului, la un moment cind CPU este din nou alocata procesului suspendat.
Cind s-a definit un proces s-au indicat trei componente. Apare ca naturala divizarea in trei clase a informatiilor ce compun starea unui proces:
a) Valorile datelor ce se salveaza. De obicei acestea sint continuturile registrelor, care se afla intr-o zona considerata nesigura intrucit noul proces, prin utilizarea registrelor, distruge continutul acestora. In clasa registrelor intra, desigur, indicatorul stivei si indicatorii de conditie.
b)Contorul programului, indicind prima instructiune ce trebuie executata la reluarea rularii procesului.
c)Toate registrele care contin informatii ce descriu mediul de executie al procesului, incluzind, eventual, registrele unor dispozitive externe,cum sint unitatea de gestiune a memoriei si coprocesorul matematic.
Toate aceste informatii trebuie salvate intr-o zona de memorie dedicata, rezervata special pentru astfel de scopuri si pentru fiecare proces. Continutul acestei zone descrie starea atinsa de catre procesul asociat cind acesta a fost suspendat. Pentru reluarea corecta a executiei procesului suspendat este suficienta reincarcarea acestor informatii in registrele din care au provenit.
Informatia salvata de suspendarea unui proces constituie o descriere a starii acestuia. Intr-un mediu multitasking mai sint necesare si alte detalii pentru o completa caracterizare a starii procesului. In mod obisnuit, informatiile suplimentare necesare identificarii procesului se adauga la cele continute in registre pentru a forma un bloc compact, care mai contine si parametrii necesari implementarii de catre CPU a unei strategii de planificare. Acest bloc compact, pastrat in memorie, se numeste descriptorul procesului, deoarece el descrie toate caracteris- ticile relevante ale procesului si starea la care au ajuns calculele asociate lui. In fig.3.5 se sugereaza o posibila structurare a unui descriptor de proces. Se remarca structura de lista inlantuita, existind indicator catre descriptorul unui alt proces, fapt ce faciliteaza activitatea planificatorului.
Fig. 3.5 Exemplu de format pentru descriptorul procesului
3.4.2. Salvarea si restaurarea continutului registrelor.
Comutarea procesului (adesea numita si comutarea contextului) este o operatie elementara, dar ea este o componenta importanta a primitivelor complexe dedicate operatiilor de gestiune in sisteme multitasking. Intrucit ea este frecvent folosita in sistemele cu utilizatori multipli, viteza de comutare a contextului este unul din factorii majori in influentarea eficientei unui sistem, indeosebi in aplicatiile in timp real.
Cea mai mare parte a consumului de timp in comutarea contextului se datoreaza transferului continutului registrelor in zona de memorie alocata descriptorului si, reciproc, transferului de date din zona alocata descriptorului in registrele adecvate. In arhitectura microprocesoarelor se impune realizarea compromisului intre viteza de executie a programelor si cea de comutare a contextului.
O unitate centrala de prelucrare cu multe registre ruleaza mai eficient un proces ca urmare a posibilitatii de stocare in CPU a unui numar mai mare de date. Pe de alta parte, timpul consumat la comutarea contextului este, practic, proportional cu numarul de registre. Nici arhitectura fara registre nu pare solutia optima, deoarece lungeste duratele de executie a programelor.
Majoritatea microprocesoarelor moderne au in structura lor 8-16 registre de uz general, al caror continut poate fi salvat sau restaurat cu acelasi tip de instructiune (push - pop).
3.5. Excluderea mutuala
Executia paralela sau pseudoparalela a mai multor procese conduce, in mod inevitabil, la concurenta pentru resursele sistemului, resurse ce pot fi solicitate de mai mult de un proces pentru terminarea taskului ce i s-a asignat. Fenomenul este evident in cazul sistemelor paralele, dar apare ca paradoxal pentru sistemele pseudoparalele.
3.5.1. Concurenta in sisteme pseudoparalele
Se considera doua procese A si B, care au nevoie de o resursa a sistemului. Starea acesteia, libera (free) sau ocupata (busy), este memorata in locatia de memorie X. X = 0 indica resursa libera. Se considera o masina ipotetica, folosind un limbaj de asamblare ipotetic, dar evident ca mnemonica, rulind, pentru fiecare proces, urmatorul cod:
test X; inscrie indicatorul de conditie conform valorii memorate in X
bne after; salt la eticheta after daca resursa este ocupata
set X; inscrie 1 in X pentru a semnala ca resursa a devenit ocupata
S-a presupus ca resursa nu poate fi alocata mai multor utilizatori (cazul imprimantei).
CPU efectueaza comutarea proceselor dupa executia unei instructiuni. Se considera doua procese A si B, care incearca simultan obtinerea resursei a carei stare este reprezentata prin X, X avind valoarea initiala 0.
Procesul A Procesul B Valoarea citita sau inscrisa
-------- ----- ------ ----- ----- ---------------
test X 0
bne after
(A suspendat, B activat)
test X 0
bne after
set X 1
(B suspendat, A activat)
set X 1
In acest exemplu, in care nu exista nici un control privind utilizarea lui X, este posibil ca ambele procese sa considere resursa disponibila, asa ca ea va fi incorect utilizata. Deci, ambele procese se considera drept unicul posesor, cind, de fapt, ele utilizeaza aceeasi resursa in paralel.
Din exemplu rezulta ca este necesar un mecanism de control al accesului la resursele critice. Solutia problemei excluderii mutuale trebuie sa satisfaca urmatoarele criterii:
(1) numai un singur proces poate utiliza, la un anumit moment de timp, resursa in discutie;
(2)cind mai multe procese incearca, simultan, obtinerea resursei, mecanismul de control trebuie sa aloce resursa numai unuia din procese si intr-un timp finit;
(3) cind un proces detine o resursa,timpul de posesie trebuie sa fie limitat; la expirarea lui resursa trebuiesa fie eliberata;
(4) procesele asteptind disponibilitatea resursei trebuie sa nu iroseasca timpul unitatii centrale, deci trebuie suspendate.
Specificarea unor valori finite de timp pentru acordarea si posesia resursei nu este direct legata de excluderea mutuala, dar se introduce pentru evitarea blocarii (deadlock). Conditia (4), cum se va arata, poate fi doar partial satisfacuta, deci ar trebui considerata ca dezirabila si nu ca obligatorie.
3.5.2. Regiuni critice
Problemele anterior mentionate sint produse de executia intercalata a instructiunilor celor doua proceduri atunci cind executa operatii cu elementul critic de date X. Problema excluderii mutuale se solutioneaza daca, pe durata accesului la o resursa critica, nici un alt proces nu mai are acces la aceasta. O constructie clasica utilizata pentru implementarea excluderii mutuale este "regiunea critica", propusa de catre Dijkstra [12].
Unei regiuni critice ii sint asociate un set de declaratii si o variabila, comune tuturor proceselor ce doresc sa utilizeze resursa. Toate regiunile critice referitoare la aceeasi variabila comuna se executa prin excludere mutuala.
Proprietatile regiunii critice sint urmatoarele:
a)cel mult un proces executa declaratiile asociate regiunii critice;
b)un proces care doreste sa execute declaratiile asociate regiunii critice va dobindi acest drept intr-un timp finit;
c)un proces care doreste sa execute declaratiile unei regiuni critice o face intr-un timp finit.
Operatiile ce trebuie efectuate cind un proces doreste sa execute o regiune critica sint simple. In primul rind se testeaza valoarea unei anumite variabile pentru a se determina daca regiunea in discutie este executata de catre un alt proces (caz in care variabila are valoarea 1). Apoi variabila se inscrie cu 1 pentru a indica "regiunea ocupata". (Daca regiunea era gasita ca ocupata, inscrierea cu 1 a variabilei nu are efecte nocive.) Urmeaza executia regiunii, care trebuie sa se termine intr-un timp finit. La iesirea din regiunea critica procesul reseteaza valoarea variabilei comune asociate regiunii critice, fapt ce permite ca alte procese sa obtina, eventual, accesul la regiune. Desi nu se face nici un fel de ipoteza asupra comportarii proceselor care asteapta, criteriul (4) anterior mentionat sugereaza ca procesele in asteptare vor fi blocate pe durata cit regiunea este ocupata si activate la eliberarea ei. Cum numarul de procese care asteapta poate fi mai mare decit unu, este necesara o politica de planificare. Totusi, trebuie subliniat ca notiunea de regiune critica nu include un algoritm anumit de stabilire a prioritatilor, dar, daca acesta exista, el trebuie facut "nepartinitor", pentru ca timpul de asteptare al fiecarui proces sa fie finit.
3.5.3. Mecanismul test-and-set.
Din descrierea de mai sus rezulta ca o regiune critica include alte regiuni critice, mai putin extinse. Dupa cum s-a exemplificat mai inainte, testarea variabilei comune asociate unei regiuni critice se face prin excludere mutuala, deci si ea constituie o regiune critica.
Privita la cel mai coborit nivel, problema de rezolvat este cea din exemplu, care permite implementarea unor regiuni critice de mai mare complexitate cu ajutorul actualizarii prin excludere mutuala a unei singure variabile. Pot aparea probleme, deoarece este posibila comutarea unui proces pe durata secventei de actualizare a variabilei. In conditii de pseudoparalelism cauza comutarii este aparitia unei intreruperi, singurul eveniment capabil de a produce un salt neprevazut (asincron) la o alta rutina.
In sistemele cu microprocesor unic actualizarea prin excludere mutuala se poate implementa prin neacceptarea de intreruperi pe durata acestei operatii. Se pot gindi doua metode, in functie de setul de instructiuni al microprocesorului utilizat. Prima posibilitate se refera la microprocesoarele de 8 biti care nu sint prevazute cu instructiuni special elaborate pentru tratarea situatiei mentionate:
di ;dezactivarea sistemului de intreruperi
move A,X ;copiaza X in A
set X ;inscrie X cu 1
ei ;reactivarea sistemului de intreruperi
test A ;testarea vechii valori a lui X, acum cea a ;variabilei A.
Pentru scurtarea timpului de dezactivare a sistemului de intreruperi testarea valorii lui X a fost scoasa in afara regiunii critice. Deci, X poate fi inscris cu 1 inainte de testare, deoarece valoarea sa finala nu depinde de cea initiala.
A doua metoda foloseste o instructiune speciala, prezenta - in diverse forme - in seturile de instructiuni ale tuturor microprocesoarelor moderne. Aceasta instructiune, adesea numita test-and-set (tas), (testare si inscriere cu 1), efectueaza atit copierea, cit si inscrierea prezentate in metoda anterioara, ca si testarea vechii valori a lui X. Cum cererilor de intrerupere li se da curs la terminarea executiei unei instructiuni, operatiile test-and-set nu pot fi intercalate cu executia rutinelor de tratare a cererilor de intreruperi. Operatia, indivizibila, este indeplinita prin codul
tas A, X; testeaza si inscrie cu 1 pe X,copiaza vechea sa valoare in A.
O alta posibila sursa de probleme este datorata prezentei procesoarelor destinate accesului direct la memorie (DMA), intrucit ciclurile lor de acces la memorie se pot intercala cu ciclurile masina destinate executiei unei instructiuni, deci DMA se poate efectua inainte de terminarea executiei instructiunii curente. Este motivul pentru care executia instructiunii test-and-set dezactiveaza in mod automat posibilitatea executarii de transfer DMA. Oricum, acesta nu indica probleme insurmontabile: de regula, prin DMA se efectueaza transferuri in conjunctie cu perifericele de mare viteza, deci se poate aranja ca variabilele asociate zonelor critice sa nu se afle in zona de memorie alocata tampoanelor folosite in mecanismele DMA.
3.5.4. Functia test-and-set in structuri multiprocesor
Structurile multiprocesor cu magistrala comuna pot prezenta probleme mai complexe. Pentru ilustrare se vor examina mai atent unele operatii, indeosebi legate de magistrala comuna interconectind microprocesoarele cu memoria in care sint stocate variabilele comune.
Folosirea in comun a magistralei se face conform unei anumite strategii de arbitrare in cazul concurentei intre procesoare, care permite alocarea magistralei doar unuia din solicitanti. Deci, insasi magistrala constituie o regiune critica, fiind utilizabila, la un moment anumit, doar de un singur microprocesor. Accesul la magistrala este acordat printr-un mecanism concentrat sau distribuit de arbitrare, care informeaza solicitantul asupra posibilitatii de utilizare a magistralei de indata ce actualul utilizator o elibereaza.
In general, toate magistralele multiprocesor [10], [11], [16] contin o linie a carei stare este determinata de interfata utilizatorului curent al magistralei, indicind daca aceasta este sau nu ocupata. De regula magistrala ramine in posesia unui utilizator pentru timpul necesar efectuarii unui singur ciclu de acces la memorie, dupa care este eliberata. O astfel de tehnica de atribuire a magistralei poate conduce la erori chiar in conditiile existentei instructiunii tas, a carei executie necesita doua cicluri de acces la memorie pentru completare: unul de citire, care copiaza X in A, si un al doilea de inscriere, careinscrie cu1 variabila X. In fig. 3.6. se vede ce se poate intimpla pe o magistrala comuna cind doua procese, unul executat de catre CPU 1, celalalt de catre CPU 2, efectueaza instructiunea test-and-set asupra aceleiasi variabile X. Valoarea 0 a semnalului BBUSY/ indica pentru celelalte interfete starea de "ocupat" a magistralei. (Semnul "/" la sfirsitul numelui unui semnal arata ca acesta este activ in starea logica 0.) Cind BBUSY/ = 1 controlul magistralei poate fi preluat de un nou master. In consecinta, apare pericolul intercalarii intre cele doua cicluri de memorie ale unei instructiuni tas a unui ciclu memorie a altei instructiuni tas, rulata de un alt proces. Situatia este similara cu intercalarea instructiunilor in sistemele cu procesor unic.
Similaritatea situatiilor induce si similaritatea solutiilor: evitarea intercalarii ciclurilor de acces la memorie pe magistrala comuna pe durata executiei operatiilor critice. In acest sens magistrala este pastrata in starea "ocupat" din momentul citirii lui X pina la cel al terminarii inscrierii sale cu 1. (fig. 3.7.)
Intrucit ciclurile citire-modificare-inscriere difera de ciclurile normale pe magistrala, interfata cu magistrala trebuie sa cunoasca daca operatia solicitata de catre microprocesorul local este una normala sau nu. Informatia respectiva poate fi furnizata de insusi microprocesor, printr-o linie a sa speciala, sau printr-o combinatie a semnalelor de stare, care indica efectuarea unei operatii read-modify-write. Aceasta conditie speciala poate fi asociata cu o anume instructiune, a carei executie produce activarea semnalului, sau se poate conecta cu o secventa de instructiuni, pentru care un indicator special in codul operatiei cauzeaza activarea unui cod special de semnalizare a unei operatii indivizibile in cicluri individuale. Pentru microprocesoarele care nu dispun de facilitatile de mai inainte problema se rezolva prin incadrarea instructiunii cu executie indivizibila intre alte doua instructiuni; prima inscrie, iar cea de a doua sterge un indicator al interfetei care permite pastrarea controlului asupra magistralei pe durata de executie a instructiunii ce nu se poate fragmenta. Desigur, metoda conduce la cresterea ineficientei de ansamblu in utilizarea magistralei.
Fig. 3.6. Secvente posibile de cicluri pe magistrala comuna in cazul executiei instructiunii test-and-set indivizibile
Fig. 3.7. Executia unui ciclu indivizibil citire-modificare-inscriere
3.5.5. Implementarea regiunilor critice vaste
Pina in acest punct s-a precizat atitudinea proceselor care, dorind sa execute o regiune critica, o gasesc in starea "ocupat". Precizarea este importanta, deoarece citeriile de caracterizare a unei solutii rezonabile a problemei excluderii mutuale prescriu un timp finit de asteptare si un comsum minim din timpul unitatii centrale de prelucrare. Prima solutie consta in a permite unui proces sa cicleze in jurul aceluiasi test pina la eliberarea regiunii. In tot timpul incercarilor nereusite procesorul este mentinut ocupat, desi ar fi putut fi utlizat pentru scopuri mai lucrative, rulind procese care nu sint in asteptarea intrarii in regiunea critica. Mai mult, solutia nu garanteaza un timp finit de asteptare. Se considera A si B concurind pentru executia regiunii asociate cu X, pe care, la acest moment o executa C. O posibila secventa de instructiuni executate de catre CPU este:
tas A,X
bne loopa
tas A,X
bne loopa
(A este suspendat, B este activat)
tas B,X
bne loopb
tas B,X
bne loopb
(B este suspendat, C este activat)
clear X
.
.
.
(C est esuspendat, B este activat)
tas A,X
bne loopb
(B intra in regiunea critica)
Se constata ca procesul A a fost depasit de catre B, care a ajuns la regiunea critica dupa A. Faptul se datoreaza modului de planificare, bazat pe mecanismul de alternare a proceselor privind rularea de catre CPU. Algoritmul impartial privind timpul de utilizare a CPU, conduce la situatii in care un proces asteapta pe o durata lunga de timp, probabil infinita. Decurge necesitatea de a imagina alt algoritm de planificare pentru regiunile critice, evitindu-se risipirea timpului CPU (busy waiting) si timpi infiniti de asteptare (process starvation).
3.5.6. Regiuni critice conditionate
Baza de date asociata unei regiuni critice este modificata in sensul generarii unei liste de descriptori ai proceselor asteptind accesul in regiunea critica, lista ordonata conform unei anumite scheme de prioritati. La eliberarea regiunii se selecteaza primmul element al listei (in cazul in care aceasta nu este vida) si el este transferat planificatorului CPU. Procesul isi poate continua executia, intrucit regiunea este libera. Celelalte procese inscrise in lista trebuie sa astepte in continuare. In consecinta, CPU nu este fortata sa execute buclele de asteptare descrise anterior, iar accesul la regiunea critica este reglat de un algoritm explicit de planificare, selectat conform cerintelor programatorului.
Si aceasta implementare contine fenomene busy waiting si process starvation, deoarece introducerea si extragerea in lista de descriptori ai proceselor sint, la rindul lor, regiuni critice. Fenomenele mentionate pot fi tolerate pentru aceste regiuni mici, deoarece timpii scurti de executie nu conduc la intirzieri si asteptari prea mari. Pentru regiuni mai vaste sint necesari algoritmi dedicati de planificare.
3.6. Sincronizarea
In cazul excluderii mutuale procesele concureaza pentru utilizarea unei anumite resurse (regiunea critica), iar natura interactiunii permite rularea unui proces fara necesitatea de cunostinte despre celelalte procese, cu care ruleaza in paralel. Acest lucru este posibil deoarece procesul incearca sa obtina resursa, indiferent de starea concurentilor sai.
O alta clasa de intercatiune este cea a cooperarii proceselor, ceruta pentru implementarea unui task complet. In acest caz procesele care sint folosite pentru executarea taskului trebuie sa cunoasca starea celorlalte procese cu care interactioneaza. Fiecare proces este proiectat si realizat prin considerarea numarului si tipului de interactiuni posibile cu alte procese, intrucit procesele nu mai concureaza intre ele, ci coopereaza.
3.6.1. Semafoare
Cel mai simplu tip de informatii vehiculate intre doua procese este un semnal de sincronizare. Semnalele de sincronizare sint cerute de faptul ca vitezele relative ale celor doua procese sint, in general, necunoscute. Intr-un sistem cu procese concurente durata de executie a unei secvente de instructiuni depinde de numarul si caracteristicile celorlalte procese concurente, precum si de evenimente externe, al caror numar si moment al aparitiei sint necunoscute.
Solutia clasica a problemei sincronizarii intre doua sau mai multe procese, fara schimb de date, se bazeaza pe utilizarea semafoarelor. Ele au fost introduse de catre Dijkstra [12], o serie de alti cercetatori continuindu-i lucrarile [13],[14],[15].
In principiu, semaforul este o variabila x, careia i se asociaza doua proceduri: P(x) si V(x) (unii autori le denumesc "signal" si, respectiv, "wait"). O alta caracteristica a semaforului este numarul c(x) maxim de semnale trimise semaforului, dar nerealizate.
Functionarea corecta a semaforului este dictata de regulile numite invariantii comunicatiei (communication invariants). Fie s(x) si r(x) numarul de semnale trimise, respectiv primite de catre semaforul x. O comportare corecta presupune respectarea relatiei
0 <= r(x) <= s(x) <= r(x) + c(x).
Uneori este utila asigurarea unei valori initiale i(x) unui semafor inaintea declansarii operatiilor de sincronizare intre procese. In acest caz invariantul de comunicatie se rescrie astfel:
0 =< r(x) <= s(x) + i(x) =< r(x) + c(x).
Operarea celor doua proceduri asociate P si V trebuie sa satisfaca urmatoarele reguli, care definesc modul in care semaforul sincronizeaza executia procesului:
- operatia V efectuata asupra semaforului pentru care
r(x) < s(x) + i(x)
are ca rezultat incrementarea lui r(x). Suplimentar, daca
s(x) + i(x) = r(x) + c(x)
si exista procese asteptind la semafor, unuia dintre acestea i se permite continuarea si are loc incrementarea lui s(x). Daca procedura se executa cind r(x) = s(x) + i(x), procesul este suspendat si inserat in sirul de asteptare asociat semaforului.
- operatia P efectuata asupra semaforului cind s(x) + i(x) = r(x) + c(x) produce suspendarea procesului si inserarea lui in sirul de asteptare asociat semaforului. Daca s(x) + i(x) < r(x) + c(x), se incrementeaza s(x). Suplimentar, daca exista procese asteptind la semafor, unuia dintre ele i se permite continuarea si are loc incrementarea lui r(x).
3.6.2. Operatii cu semafoare
Pentru implementarea regulilor de sincronizare este necesara o unica valoare intreaga
n(x) = s(x) + i(x) - r(x)
Din invariantii de comunicatie se deduce ca :
0 < n(x) < c(x)
In plus, valoarea initiala a lui n(x) este i(x) pentru a asigura corectitudinea operatiilor. Aceasta regula rezulta din definirea lui n(x) si imprimind s(x) = r(x) = 0. Intrucit sirurile de asteptare sint incluse in regulile de sincronizare, structurile de date utilizind procedurile P si V trebuie sa posede anumite caracteristici necesare implementarii acestor siruri.
Sint necesare doua tipuri de siruri: unul pentru procesele intirziate in timpul executarii operatiei P, iar celalalt pentru procese intirziate in timpul executiei operatiei V. Desi distincte din punctul de vedere logic, cele doua siruri pot fi implementate utilizind o singura structura; este usor de demonstrat ca, daca c(x) = 0, este imposibil a avea doua procese asteptind simultan in ambele siruri. Deci, o singura structura de date poate pastra fie toate procesele intirziate la executarea operatiei P, fie toate acelea intirziate pe durata operatiei V, tipul procesului ce asteapta fiind determinat de starea variabilei n(x). Demonstratia se bazeaza pe analiza conditiilor care determina inserarea proceselor si extragerea lor din sirul de asteptare. Initial cele doua siruri sint vide si ele ramin asa pina cind n(x) devine egal fie cu 0 (adica r(x) = s(x) + i(x)), fie cu c(x) (adica s(x) + i(x) = r(x) + c(x));in primul caz toate operatiile V efectuate vor intirzia procesul corespunzator, in timp ce operatiile P nu o vor face. Daca procesele asteapta pentru ca ele au efectuat o operatie V, atunci valoarea lui n(x) trebuie sa fie 0, deoarece fiecare operatie P va incrementa atit r(x) cit si s(x); deci, doar cind toate procesele care asteapta au fost activate si pot continua, valoarea lui n(x) poate fi incrementata.
Cu motive similare se poate demonstra ca procesele intirziate prin operatiile P pot exista doar cind n(x) = c(x). Situatia in care procesele asteptind la semafor sint intirziate fie de operatii P, fie de operatii V este imposibila, deoarece valoarea contorului n(x) ar trebui sa aiba simultan doua valori distincte, 0 si c(x). Intrucit numai o singura clasa de procese poate astepta la semafor la un anumit moment de timp, nu este necesar a aloca doua sectiuni distincte ale structurii de date in implementarea semaforului. Fig. 3.8. indica o structura de date adecvta implementarii unui semafor. De remarcat utilizarea unei unice liste pentru descriptorii procesului, asa cum s-a subliniat. Cimpul c(x) este inscris la crearea semaforului, intrucit, de la acel moment, el nu mai este modificat.
__________ ______ ____ __________________
I Contor (n) I
I__________ ______ ____ _________________I
I Capacitate (c) I
I__________ ______ ____ _________________I
I Variabila blocare (v) I
I__________ ______ ____ _________________I
I Indicator spre primul proces in asteptare I
I__________ ______ ____ _________________I
Fig. 3.8. Exemplu de structura de date folosita la
implementarea semafoarelor.
Cele doua operatii P si V, folosite pentru a defini un semafor, trebuie inserate intr-o regiune critica, deoarece manipularea necontrolata a cimpului n(x) conduce la situatia din paragraful 3.5.1. Intrucit astfel de operatii nu sint atit de simple pe cit este simpla inscriere a unei variabile, este intelept a controla accesul la regiunea critica a semaforului prin intermediul operatiilor test-and-set, efectuate asupra variabilelei v, si a implementa un sir de procese asteptind accesul la operatia cu semaforul. Mecanismul este similar cu cel sugerat in paragraful 3.5.3. de implemenatre a unor regiuni critice neelementare.
Un proces care incearca efectuarea unei operatii cu semaforul este intirziat de doua ori: prima data - deoarece regiunea critica a semaforului este ocupata, iar a doua oara - intrucit testarea semaforului produce o intirziere a procesului. Totusi, a doua din aceste intirzieri este scurta, ca urmare a simplitatii operatiilor P si V.
Fig. Procedura P(x)
Fig. Procedura P(x)
struct x
3.6.3. Implementarea unui semafor.
In cele ce urmeaza se indica o posibila implementare a operatiilor P si V. Ea se bazeaza pe existenta procedurilor entercr (intrare in regiunea critica) si exitcr (iesirea din regiunea critica). La apelare prima procedura isi termina executia doar dupa executia cu succes a unei operatii test-and-set asupra variabilei transferate ca parametru. In cadrul acestei proceduri este posibila implementarea tuturor mecanismelor necesare unei functionari eficiente. Procedura exitcr reseteaza variabila transferata ca parametru.
Se va folosi structura de date din fig. 3.8, declarata in urmatoarele proceduri scrise intr-un limbaj similar cu Pascal:
type semdata = record
v : lockvar;
n,i: integer;
waitqueue: processdescriptor;
end;
var x : semdata;
procedure P (x:semdata);
begin
entercr (x.v)
if x.c = x.n then
begin
extragerea descriptorului curent al procesului din setul de procese ce se
executa;
inserarea lui in sirul de asteptare;
exitcr (x.v);
realocarea utilizarii CPU;
end
else if x.n = 0 and x.waitqueue <> nil then
begin
extragerea unui proces din sirul de asteptare;
exitcr (x.v);
adaugarea descriptorului extras la setul de procese ce se vor executa;
realocarea (daca este necesar) utilizarii CPU;
end
else
begin
x.n := x.n + 1
exitcr (x.v)
end
end;
procedure V (x:semdata);
begin
entercr (x.v);
if x.n = 0 then
begin
extragerea descriptorului procesului curent din setul de procese ce se
executa;
inserarea lui in sirul asteptare;
exitcr (x.v)
realocarea utilizarii CPU;
end
else if x.c = x.n and x.waitqueue <> nil then
begin
extragerea unui proces din sirul de asteptare;
exitcr( x.v );
introducerea descriptorului extras in multimea
proceselor de executat; realocarea utilizarii CPU.
end
else
begin
x.n := x.n - 1
exitcr (x.v)
end
end;
Cind un proces este extras dintr-un sir de asteptare drept consecinta a unei operatii P sau V, se executa algoritmul de planificare privind alocarea CPU, pentru a decide daca procesul extras are o prioritate superioara celui ce l-a extras. In acest caz, procesul care efectueaza operatia P sau V este suspendat si se executa cel extras. Deci, chiar cind semnaleaza corect la semafor si primeste accesul, un proces poate fi suspendat, intrucit el activeaza unul de prioritate superioara. Totusi, aceasta intirziere este diferita de cea cauzata de receptia la un semafor vid sau semnalizarea la unul plin. Diferenta consta in faptul ca proces blocat de o anumita stare a semaforului nu se va putea executa pina cind semaforul isi schimba starea; un proces intirziat pentru ca a deblocat un altul va fi reluat imediat ce unitatea centrala de prelucrare devine disponibila.
3.7. Comunicatia intre procese
3.7.1. Cutii postale
In unele cazuri interactiunea intre procese cere efectuarea unui schimb de date, suplimentar semnalelor de sincronizare, intre procesele care coopereaza. Solutia clasica a acestor probleme foloseste un tampon pentru mesaje (message buffer), numit si cutie postala (mailbox). Cutia postala reprezinta o extensie a semafoarelor, deoarece ea permite asocierea unui set de date, numit mesaj, fiecarei operatii de semnalizare.
O cutie postala se comporta in acelasi mod cu un semafor, cu exceptia manipularii mesajelor. In consecinta, se folosesc aceleasi reguli de sincronizare si aceiasi invarianti. Operatiile trebuie modificate pentru a se putea manipula mesajele care se transmit sau se receptioneaza. Noile operatii sint send(x,m) si receive(x,m), corespunzind lui P si respectiv, V. x este identificatorul cutiei postale iar m este cel al mesajului.
Cind se efectueaza o operatie de tip send, mesajul se insereaza in cutia postala, daca aceasta nu este plina. Cind se efectueaza o operatie de tip receive se extrage primul mesaj din cutia postala, daca aceasta nu este vida. In mod obisnuit, ordonarea mesajerlor in cutia postala este similara cu cea a unei stive de tip FIFO: operatia receive extrage din stiva cel mai vechi mesaj pe care aceasta il contine. Sint posibile si organizari care asigneaza prioritati mesajelor continute de cutia postala.
3.7.2. Implemenatrea cutiilor postale
Implementarea cutiilor postale este similara cu cea pentru semafoare, la care se adauga facilitatile legate de manpularea mesajelor. In continuare se sugereaza un mod de realizare:
mailbox = record
v : lockvar;
n,i : integer;
buffer: message;
waitqueue: processdescriptor;
end;
procedure send(x:mailbox, m:message);
begin
entercr(x.v);
if x.v = x.c then
begin
introducerea mesajului m in tampon;
extragerea descriptorului procesului curent din multimea proceselor de executat;
inserarea lui in sirul de asteptare;
exitcr(x.v);
realocarea utilizarii CPU;
end
else
begin
if x.c=0 and x.waitqueue<> nil then
begin
extragerea unui descriptor de proces din sirul de asteptare;
asocierea mesajului m cu procesul extern;
exitcr(x.v);
inserarea descriptorului procesului in multimea de procese de executat;
realocarea utilizarii CPU;
end
else
begin
inserarea mesajului m in tampon;
x.c := x.c + 1;
exitcr(x.v);
end
end;
procedure receive(x:mailbox, m:message);
begin entercr(x.v);
if x.c=0 then
begin
extragerea descriptorului procesului curent din setul de procese de executat; inserarea lui in sirul de asteptare;
exitcr(x.v);
realocarea utilizarii CPU;
(aceasta se executa la reluarea procesului,deoarece exista mesaj)
copierea in m a mesajului asociat procesului;
end
else
begin
extragerea mesajului din tampon si copierea lui in m;
if x.c=x.n and x.waitqueue<> nil then
begin
extragerea unui descriptor de proces din sirul de asteptare;
exitcr(x.v);
introducerea descriptorului extras in multimea proceselor de executat;
realocarea utilizarii CPU;
end
else
begin
x.n := x.n - 1;
exitcr(x.v);
end
end;
In cadrul procedurii send mesajul este introdus in cutia postala chiar daca aceasta este considerata plina, deoarece structura de lista inlantuita nu impune o limitare a numarului de measje ce se pot memora. Conditia "buffer full" (tamponul plin) se foloseste doar pentru sincronizarea intre procese.
Un fapt important este acela ca procedura send este asociata cu un mesaj catre un proces atunci cind tamponul este vid. Necesitatea acestei modalitati de lucru este impusa de faptul ca, daca un proces care asteapta un mesaj este activat, executia sa incepe doar dupa o lunga durata de timp, daca prioritatea sa este redusa. In acest caz s-ar putea intimpla ca alte operatii send sa aiba loc intre timp si alte procese, de prioritate superioara, sa fie activate si executate. Deci procesele de prioritate ridicata pot sa isi extraga mesajele inainte ca cele de prioritate redusa sa fie activate. In acest mod, se pastreaza ordinea de receptionare a mesajelor, pentru ca mesajul este extras cind procesul in asteptare este deblocat. Pentru a lega mesajul si procesul se poate folosi un pointer adecvat catre descriptorul procesului. 3.7.3. Sincronizarea proceselor
Se considera o unica linie tehnologica compusa din doua masini unelte, masina 1 si masina 2, si un unic tampon B de capacitate c, plasat intre cele doua masini. Operatia este astfel organizata incit masina 1 primeste o piesa si o prelucreaza. Cind operatia este completa, masina 1 plaseaza piesa in tampon, cu conditia ca acesta sa nu fie plin, dupa care obtine o noua piesa, daca este disponibila, si repeta aceeasi operatie. Cind masina 1 incearca sa plaseze o piesa in tamponul plin functionarea sa este blocata, pentru ca trebuie sa astepte pina cind este spatiu in acesta, ceea ce ii permite sa depuna piesa prelucrata si sa se ocupe de o alta.
In cealalta parte a tamponului, masina 2 se comporta intr-un mod similar. Intii ea incearca sa obtina din tampon o piesa pentru prelucrare. Daca acesta nu este gol, masina 2 extrage o piesa, pe care o prelucreaza; in caz contrar asteapta pina cind tamponul contine cel putin o piesa.
Cele doua masini sint comandate de doua procese diferite, A si B, executate de catre aceeasi unitate centrala de prelucrare. Se pune problema sincronizarii, pe baza continutului tamponului, a functionarii lor.
In exemplul ales, care presupune identitatea pieselor prelucrate, starea tamponului poate fi convenabl reprezentata printr-un numarator indicind numarul de piese pe care le contine. Intrucit ceea ce afecteaza functionarea masinilor sint valorile extreme ale continutului numaratorului, cae mai buna metoda de sincronizare pare aceea folosind semafoare. In continuare se indica o schita de realizare, in acelasi limbaj pseudo-Pascal, in care x este un semafor cu capacitatea k unitati, initializat cu numarul de piese din tampon la inceputul operatiei.
schita procesului A
.
.
.
while true do
begin
obtine o noua piesa;
prelucreaza piesa;
P(x);
pune piesa in tampon;
end;
.
.
.
schita procesului B
.
.
.
while true do
begin
V(x);
obtine o piesa din tampon;
prelucreaza piesa;
pune piesa in tamponul de iesire;
end;
.
.
.
Operatia P blocheaza procesul A cind tamponul este plin, in timp ce operatia V blocheaza procesul B cind acesta este vid. Pe de alta parte, P porneste procesul B cind tamponul este gol si B asteapta sa prelucreze, iar V va porni procesul A cind tamponul este plin si A asteapta sa stocheze o piesa in tampon.
3.7.4. Comunicatia intree procese
Exemplul precedent poate fi modificat pentru a demonstra ca doar semafoarele nu sint suficiente pentru implementarea simpla a sincronizari. In exemplul modificat se considera ca piesele nu sint identice. Ele fac parte din patru clase distincte, identificate prin numerele 1,2,3,4. De asemenea, se impune cerinta suplimentara ca piesele sa fie prelucrate in aceeasi secventa de catre ambele masini.
Sincronizarea presupune si un schimb de date intre procesele care coopereaza, intrucit informatia vehiculata nu indica doar introducerea in tampon a unei piese sau extragerea unei piese din acesta. Orice semnal de inserare trebuie sa contina date identificind tipul piesei, care trebuie citite cind piesa este extrasa.
Aceste considerente recomanda folosirea unei cutii postale, in care mesajele sint intregi indicind tipul piesei asociate. Cele doua schite de proces se modifica si aspectul lor este descris mai jos.
schita procesului A
.
.
.
while true do
begin
obtine o piesa si transcrie in m tipul ei; case m of
1: prelucrare de tip 1;
2: prelucrare de tip 2;
3: prelucrare de tip 3;
4: prelucrare de tip 4;
end;
send(x,m);
pune piesa in tampon;
end;
.
.
.
schita procesului B
while true do
begin
receive(x,m);
case m of
1: prelucrare de tip 1;
2: prelucrare de tip 2;
3: prelucrare de tip 3;
4: prelucrare de tip 4;
end;
pune piesa in tamponul de iesire;
end;
Sincronizarea se efectueaza la fel ca in cazul precedent, dar procesul A transfera catre B informatii privind tipul piesei. Daca organizarea cutiei postale este de tipul FIFO, piesele sint prelucrate in aceeasi secventa de catre ambele masini, deoarece procesul B primeste mesajele in ordinea in care ele au fost emise de catre A.
Nu s-au facut ipoteze privind vitezele relative ale celor doua procese, sau asupra sosirii pieselor la masina 1, element esential in intregul proces de productie. Acest fapt garanteaza ca solutia bazata pe semafoare sau cutii postale este corecta indiferentde viteza de executie.
Mai exista si alte posibile extensii ale exemplului, printre care si considerarea situatiei in care mai multe masini identice executa munca masinii 1 si plaseaza rezultatele in acelasi tampon, din care mai multe masini, operind identic cu masina 2, extrag din tampon in vederea prelucrarii rezultatele existente. In acest caz este suficient a dispune de un singur proces A pentru comanda unei masini de tipul 1, si de un singur proces B pentru comanda masinii de tipul 2. Sincronizarea se poate face, de asemenea, cu ajutorul semafoarelor si a cutiilor postale. Se deduce ca mecanismele descrise functioneaza corect si in cazul unor producatori si consumatori multipli.
3.8. Planificarea proceselor
Gestionarea unitatilor centrale de prelucrare ale unui sistem constituie activitatea esentiala a unui sistem de operare multitasking. Activitatea de planificare a procesorului poate fi divizata in doua clase diferite: planificarea de nivel inalt sau pe termen lung si planficarea pe termen scurt. Prima se ocupa cu introducerea in sistem a programului utilizatorului si cu secventierea diferitelor procese care il compun. Intrucit ea poate fi implementata sub forma unui proces (un proces al sistemului, mai curind decit al utilizatorului), implementarea se face, practic, prin program, si ea nu va fi discutata in cele ce urmeaza. Planificarea de nivel redus se ocupa de secventierea executiei proceselor prezente in sistem la un anumit moment de timp si este cu mult mai apropiata de hardware. Planificarea de nivel inferior constituie subiectul celor ce urmeaza. Termenul "planificarea proceselor" se refera la un astfel de tip de planificare.
3.8.1. Starile unui proces
Modul tipic de abordare a problemei planificarii proceselor se bazeaza pe asocierea unei stari anumite fiecarui proces din sistem. In functie de tipul de calculator si sistem de operare, exista un numar de stari ale procesoarelor, ca si un numar de definitii ale acestor stari. Pentru ilustrare se va utiliza modelul din fig. 3.9., cu urmatoarele definitii:
- In rulare (running): Un proces in aceasta stare este executat de catre CPU sau de catre o CPU a sistemului. De aceea, se considera ca are o prioritate superioara altor procese gata de rulare;
-Gata de rulare (ready): Un proces in aceasta stare este gata de a fi rulat, dar nu este executat, deoarece prioritatea sa este mai mica decit a proceselor aflate in rulaj. In aceasta stare toti parametrii asociati procesului si care influenteaza decizia de planificare sint cunoscuti planificatorului;
-In asteptare (waiting): Un proces aflat in aceasta stare nu poate fi executat, intrucit el asteapta producerea unui eveniment special in sistem, a carui aparitie va pune procesul in starea gata de rulare, in functie de prioritatea procesului;
-Activ (active): Un proces in aceasta stare nu poate fi considerat pentru executie, intrucit el are nevoie de o comanda speciala pentru a trece, in functie de prioritate, fie in starea in rulare fie in starea gata de rulare;
-Inactiv (inactive): Un proces aflat in aceasta stare nu poate fi planificat, pentru ca, desi este prezent in sistem, are nevoie de o comanda explicita din partea unuia dintre procesele care se executa, sau din partea planificatorului, pentru a intra in starea activa si pentru a i se asigura parametrii de planificare.
Fig. 3.9. Diagrama starilor proceselor
Tranzitia intre stari a proceselor poate fi produsa de mai multe evenimente, examinate, in continuare, prin prisma conditiilor ce conduc la intrarea sau parasirea de catre un proces a uneia dintre starile listate.
A. Starea inactiva
Aceasta stare constituie o interfata intre planificatorul pe termen lung si planificatorul pe termen scurt: un proces este creat de catre planificatorul pe termen lung si este introdus in starea inctiva. Un proces poate fi inlaturat dinsistem, prin distrugere, daca planificatorul pe termen lung considera ca nu este necesara prelucrarea de catre sistem a procesului inactiv. Un proces inactiv poate fi activat si i se pot asigura parametrii ceruti de algoritmul de planificare pe termen scurt. Realizarea acestei tranzitii se face la cererea explicita a procesului aflat in rulare sau a planificatorului.
Tranzitia in sens opus se poate face numai cind procesul este in starea activa. In acest caz se emite o cerere explicita de catre procesul aflat in rulaj (eventual - o rutina de planificare), folosita pentru dealocarea intregii structuri de comanda (cum este descriptorul procesului) folosit de catre planificatorul pe termen scurt.
In general, procesele ce revin in starea inactiva sint evacuate din sistem, intrucit ele s-au executat cu succes sau au esuat, asa ca rularea lor nu mai este necesara.
B. Starea activa
Un proces in starea activa are alocata toata structura de comanda ceruta de catre planificator, deci procesul este gata sa concureze pentru obtinerea CPU. Totusi, numai ca urmare a unei comenzi explicite procesul este transpus in starea gata de rulare sau in rualre, dupa cum prioritatea procesului este inferioara sau superioara celei a procesului aflat in rulare.
Cind un proces comuta din starea activa in cea gata de executie si, apoi, in starea de executie, el este executat de la inceput; contorul programului va fi initializat cu adresa punctului de intrare a programului principal executat de catre proces. Daca un proces concureaza de doua ori pentru obtinerea CPU, el este reinitializat de fiecare data cind paraseste starea activa. Acest tip de comutare in starea gata de rulare sau in cea de rulare este diferit de cel de parasire a starii de asteptare, caz in care procesul nu este reinitializat, ci executia sa reluata prin restaurarea starii la momentul la care procesului i s-a luat accesul la CPU. Suplimentar utilizarii ca stare intermediara intre lumea exterioara si concurenta pentru CPU, starea activa poate fi folosita pentru relansarea unui proces care a fost afectat de o eroare reparabila, sau pentru executarea proceselor care necesita mai multe executii.
C. Starea de asteptare
Singurul mod de intrare in starea de asteptare consta in executia unei actiuni de suspendare cind procesul se afla in starea in rulare. Operatiile tipice producind suspendarea procesului sint:
- tentativa de a intra intr-o regiune critica ocupata;
-semnalizarea la un semafor plin; -transmiterea unui mesaj catre o cutie postala plina;
-primirea unui semnal de la un semafor gol;
-primirea unui mesaj de la o cutie postala vida.
Orice proces care incearca sa efectueze una dintre operatiile enumerate nu mai poate continua sa fie executat pina in momentul in care entitatea (regiune critica, semafor sau cutie postala) si-a schimbat starea, ceea ce permite reluarea procesului. Operatiile efectuate de catre procesul in rulare, care ar putea comuta un proces din starea de asteptare in cea gata de rulare sau chiar in starea in rulare, sint:
- iesirea din regiunea critica;
-semnalizarea la un semafor vid;
-transmiterea unui mesaj catre o cutie postala vida;
-primirea unui semnal de la un semafor plin;
-primirea unui mesaj de la o cutie postala plina.
Cind una dintre aceste operatii conduce la extragerea unui proces din starea de asteptare, controlul asupra CPU trece in sarcina planificatorului, astfel incit acesta poate decide daca procesul activat detine prioritatea cea mai inalta. In caz afirmativ, procesul ce iese din starea de asteptare este trecut direct in starea in rulare; in caz contrar el intra in starea gata de rulare.
D. Starea gata de rulare
Tranzitiile in starea gata de rulare reprezinta alternativa la tranzitiile in starea de rulare (cu exceptia acelora spre starea de asteptare), deoarece diferenta intre procesele aflate in cele doua stari este doar o chestiune de prioritate. In consecinta, tranzitiile intre starile gata de rulare si in rulare sint cauzate de modificari de prioritati relative ale proceselor executabile.
Diferenta majora consta in faptul ca procesele in starea gata de rulare nu isi pot modifica ele insele starea, in timp ce procesele in rulare pot efectua tranzitii de stare prin executarea de actiuni corespunzatoare.
E. Starea in rulare
Procesele in starea in rulare sint singurele care pot provoca tranzitii de stare ale altor procese, ca si pentru ele insele. Deci, este posibila parasirea acestei stari drept consecinta a unei actiuni explicite, programata de catre utilizator, cum este terminarea normala a unui proces sau dezactivarea temporara. De asemenea, este posibil ca un proces sa fie fortat sa elibereze CPU drept consecinta a unei actiuni din program care nu a avut destinatia explicita de a produce o tranzitie de stare a procesului. Aceste actiuni se pot imparti in doua clase: acelea care produc tranzitia in starea de asteptare si acelea care produc tranzitia procesului curent in starea gata de rulare. Prima clasa a fost discutata anterior. In cea de a doua intra actiunile care produc activarea sau reluarea altor procese. Cum procesul activat ar putea avea o prioritate superioara celui care l-a activat, pot aparea schimbari in prioritatile relative pentru toate procesele ce indeplinesc conditiile de rulare, caz in care procesul in rulare este trecut in starea gata de rulare.
Un al treilea tip de eveniment care produce parasirea de catre un prroces a starii in rulare este constituit de actiunea declansata de aparitia unor situatii externe sau interne neobisnuite, care nu pot fi prevazute de catre programator. Astfel de evenimente includ intreruperi sau exceptiii fatale ce apar pe durata executiei procesului. Ambele pot fi considerate ca evenimente care activeaza procese speciale, constituite din rutinele de tratare corespunzatoare. Intre cele doua tipuri de evenimente exista, totusi, diferente. Rutinele de tratare a conditiilor fatale de exceptie (overflow, violarea protectiei) se executa ori de cite ori ele sint activate de catre conditiile corespunzatoare, deci au intotdeauna prioritate superioara procesului care le-a generat.
3.8.2. Planificarea in conditiile prezentei intreruperilor
Intreruperile sint folosite pentru a informa CPU asupra unor evenimente importante prin efectele lor asupra activitatii sistemului. De exemplu, o intrerupere anuntind terminarea unui proces I/O efectuat de un periferic lent este mai putin importanta decit una asociata unui dispozitiv mai rapid, deci este important ca prima sa nu intrerupa executia rutinei de tratare a celei de a doua intreruperi.
Este necesara existenta unui mecanism care sa recunoasca doar intreruperile de prioritate ridicata. Cu alte cuvinte, o cerere de intrerupere este confirmata doar daca ea are o prioritate superioara procesului aflat in rulaj. Intreruperile sint evenimente externe si sint gestionate prin mijloace hardware. Deci, cind un proces este trecut in starea de rulare, prioritatea sa trebuie facuta cunoscuta dispozitivului de tratare a cererilor de intrerupere, fapt ce permite dezactivarea intreruperilor cu prioritati egale sau inferioare celei a procesului.
Daca instalarea unui nou proces face ca prioritatea CPU sa scada sub nivelul unei cereri de intrerupere asteptind tratarea, rutina de tratare a cererii mentionate se trece in starea in rulaj, procesul intrerupt trecind in starea gata de rulare. Cind rularea rutinei de tratare a intreruperii se termina, ea apeleaza planificatorul pentru a determina urmatorul proces ce trebuie executat. Decizia planificatorului poate fi infirmata de catre mecanismul de intreruperi in cazul in care intreruperi prioritare asteapta tratarea.
Dispozitivul de tratare a cererilor de intreruperi poate fi considerat drept componenta a planificatorului, implementat sub forma hardware. In acelasi mod, rutinele de tratare a intreruperilor ce asteapta atentia unitatii centrale pot fi considerate ca fiind in starea gata de rulare, intrucit executia lor va incepe imediat ce prioritatea procesului aflat in rulare scade sub cea a cererilor de intreruperi.
3.8.3. Planificarea in sisteme multiprocesor
Mecanismul de planificare descris mai sus poate fi comod implementat, prin mijloace software, la care se adauga un dispozitiv de tratare a intreruperilor in sistemele cu procesor unic. Lucrurile se complica in conditiile unui sistem cu mai multe procesoare. Intr-un sistem multi-procesor fiecare proces in rulare este asignat unei CPU si exista doua posibilitati ca un proces sa fie executat de catre sistem: orice proces poate fi rulat de catre orice CPU sau procesele pot fi grupate in submultimi, fiecare din ele alocata unei CPU. Prima situatie se intilneste in sistemele de uz general, pentru care sistemul este considerat ca un tot unitar. Deci, exista un singur grup de procese pentru fiecare din starile posibile.
Cind un proces este trecut in starea in rulare, oricare dintre CPU poate fi utilizata pentru a-l rula. Totusi, de regula, se selecteaza CPU care ruleaza procesul cu cea mai mica prioritate. Acesta este trecut in starea de asteptare.
A doua varianta de sistem multiprocesor contine un numar de copii ale situatiei sistemului cu procesor unic. Deci, fiecare CPU are propriile sale grupuri de procese in starea gata de rulare, activa sau inactiva, si un singur proces in starea in rulare. Aceste sisteme sint folosite, de regula, in aplicatiile de timp real, pentru care perifericele I/O conectate la fiecare CPU dicteaza locul de executie al fiecarui proces. Diferenta intre acest tip de sistem multiprocesor si un set de sisteme multiutilizator, dar cu un procesor unic, consta in faptul ca procesele rulind pe diferitele CPU se pot sincroniza, pot comunica intre ele sau pot concura pentru resurse comune.
In ambele tipuri de sistem, o operatie efectuata de catre un proces rulind pe CPUi poate face ca CPUj sa comute de la executia procesului A la cea a procesului B. Replanificarea unei CPU necesita un anumit suport hardware pentru transmiterea informatiei de la CPUi la CPUj pentru a indica noile conditii.
Intrucit operatia care produce replanificarea apare pe o alta CPU decit cea care comuta procesul pe care il executa, ea constituie un eveniment extern pentru a doua CPU, fapt ce justifica implementarea cu ajutorul intreruperilor a acestui tip de comunicatie interprocesor.
Revenind la sistemul multiprocesor din fig. 3.4, se pot concepe mai multe metode de implementare a intreruperilor interprocesor. O solutie consta in utilizarea unor celule speciale de memorie in zona comuna de memorie, fiecare generind, cind se scrie in ea, o cerere de intrerupere spre o anumita CPU. In modul acesta o CPU se poate intrerupe prin efectuarea unei operatii de inscriere la o adresa speciala. Datele inscrise in locatiile speciale pot indica sursa intreruperii.
O alta solutie consta in utilizarea unui set de linii speciale in cadrul magistralei comune, rezervate generarii cererilor de intreruperi interprocesor. Un caz particular este cel utilizind o unica linie de difuzare (broadcasting) care transmite serial mesaje de intrerupere. Mesajele includ identificatori privind sursa si destinatia intreruperii, precum si date indicind motivul intreruperii. Tehnica este recomandata de o serie de standarde: Future Bus (IEEE P896), VME, Multibus II [16].
3.9. Concluzii
Din cele de mai sus se poate vedea ca functionarea in regim de multiprogramare sau multitasking nu este doar o problema de software, ea necesitind un minimum de suport hardware. Aceste cerinte sint, pe scurt, urmatoarele:
1.In sistem cu procesor unic:
- posibilitatea de activare/dezactivare a intreruperilor (daca nu se ia in considerare mecanismul DMA);
- instructiuni test-and-set indivizibile (daca se considera mecanismul DMA);
- CPU si dispozitivul de tratare a intreruperilor au posibilitatea de mascare dinamica a intreruperilor cu nivel de prioritate inferior celui al programului in rulare, pentru a permite planificarea corecta.
2.In sistem multiprocesor.
- aceleasi cerinte ca in cazul sistemelor cu procesor unic;
- semnale externe indicind efectuarea de catre CPU a unei secvente indivizibile citire-modificare-insciere, pentru a bloca magistrala comuna, evitindu-se accesul intercalat al aceleiasi variabile de catre CPU distincte;
- facilitati de intreruperi interprocesor, cerute de activitatea corecta de planificare pe diferitele microprocesoare.
Suplimentar fata de aceste cerinte, se pot folosi si alte mecanisme pentru scurtarea timpului de executie cerut de anumite operatii. De ajutor sint instructiunile speciale de salvare si restaurare a starii unui procesor. Operatia este ceruta de comutarea executiei intre mai multe procese. Informatiile de stare pot contine continutul registrelor si tabelele de conversie, continined si drepturile de acces gestionate de catre MMU (unitatea de gestiune a memoriei, ce se va discuta in capitolul urmator). Deci, cresterea vitezei de comutare implica nu numai CPU, ci si circuitele conexe.
Toate procesoarele moderne dispun de astfel de suport hardware, implementat in forme variate. Mai mult, unele din ele implementeaza prin hardware functii de complexitate superioara.
In cadrul sistemului iAPX432 procedurile send si receive sint implementate prin cite o instructiune masina, si aproape toate obiectele legate de multitasking sint recunoscute de catre hardware. Alte microprocesoare, cum este iAPX286, ofera mecanisme hardware pentru manipularea unor structuri de date recunoscute de catre hardware, cum sint descriptorii proceselor. Aceasta facilitate creste viteza operatiilor de planificare.
|
