Aritoni Ovidiu Sisteme de operare 1 Introducere

B. Implementarea proceselor

Pentru a implementa modelul de proces, sistemul de operare menţine un tabel (un tabel de structuri) numit process table, cu o intrare la fiecare proces. Această intrare conţine informaţii despre starea procesului, programul de contabilizare, pointeri de stivă, alocarea memoriei, starea fişierelor deschise, informaţiile de organizare, şi orice altceva despre proces ce trebuie salvat când procesul este schimbat de la starea de runnig la starea de ready, astfel încât să poată fi repornit mai târziu ca şi cănd nu ar fi fost niciodată oprit. În MINIX administrarea proceselor, administrarea memoriei şi administrarea fişierelor sunt fiecare tratate de module separate din interiorul sistemului. Astfel tabelul de procese este partiţionat cu fiecare modul menţinând cânpurile de care are nevoie. Fig 2.4. are câteva dintre cele mai importante câmpuri. Câmpurile din prima coloană sunt sigurele relevante pentru acest capitol. Celelalte două coloane sunt furnizate doar pentru a da o idee a ce informaţii sunt necesare altundeva în sistem. Acum când că ne-am uitat la tabelul de porcese este posibil să explicăm puţin mai mult despre felul cum iluzia proceselor multiple secvenţiale este menţinută pe o maşină cu un singur procesor si mai multe dispozitive de intrare-ieşire. Ceea ce urmează este din punct de vedere tehnic o deschidere a felului cum administratorul (scheduler) din figura 2.3. lucrează în MINIX, dar majoritarea SO moderne lucrează în linii mari în acelaşi fel. Asociat cu fiecare clasă de dispozitive de I/O (diskete, hard-diskuri, timeri si terminale) este o locaţie lângă memoria principală numită interrupt vector. Vectorul de întrurupere (interrupt vector) conţine adresele procedurii serviciului de întrerupere. Să presupunem că procesul user 3 rulează când o întrerupere de disk are loc. Programul de contabilizare, programul de stare al proceselor, şi probabil unul sau mai multe registre sunt împinse în stiva curentă de hard. Computerul sare apoi la adresa specificată în vectorul de întrerupere. Aceasta este tot ce face hardware-ului. De aici înainte totul depinde de soft. Procedura începe salvând toate registrele în intrarea tabelului de procese pentru procesul curent. Numărul procesului curent şi un pointer pentru intrarea sa sunt ţinute în variabile globale astfel încât să fie găsite rapid. Apoi informaţia depozitată de vectorul de întrerupere este mutată din stivă, iar pointerul stivei este stabilit la o stivă temporară folosită de administratorul de procese. Acţiuni ca salvarea registrului şi stabilirea pointerului de stivă nici măcar nu pot fi exprimate în C aşa că ele sunt executate de un mic limbaj de asamblare de rutină. Când această rutină se termină apelează o procedură de tip C pentru a face restul muncii.

Comunicare dintre procese în MINIX este via mesaje aşa că următoarea treaptă este să construim un mesaj pentru a fi trimis la procesul disk care va fi blocat aşteptându-l. Mesajul spune că o întrerupere a avut loc pentru a-l distinge de mesajele de la procesele user cerând locuri de disk pentru a fi citite şi lucruri ca acesta. Starea procesului disk este acum schimbată de la starea blocată la starea ready iar schedulerul este apelat. În MINIX diferite procese au diferite priorităţi pentru a da servicii mai bune controlorilor de dispozitive I/O decât procesele user. Dacă procesul disk este acum procesul rulabil de cea mai mare prioritate, va fi programat să ruleze. Dacă procesul care a fost întrerupt este la fel de important sau mai mult va fi programat să ruleze din nou, şi procesul disk va trebui să aştepte puţin timp. În oricare situaţie procedura C apelată de codul de întrerupere a limbajului de asamblare se returnează şi codul limbajului de asamblare încarcă registrele şi harta memoriei pentru procesul curent şi îl porneşte să ruleze. Controlorul şi organizatorul de întreruperi sunt schiţate în figura 2.5. Nu are nici o importanţă că detaliile variază uşor de la un sistem la altul.

C. Thread-uri

Într-un proces tradiţional de tipul pe care tocmai l-am studiat există un singur fir de control şi un singur program de contabilizare în fiecare proces. Oricum în anumite sisteme de operare moderne suportul este furnizat pentru fire de control multiple în interiorul procesului.

fig 2-5. Schema cu functiile sistemului de operare de nivel inferior si momentul cand apare o intrerupere

Aceste fire de control sunt de obicei numite thread, sau ocazional lightweit processes (procese cu greutate uşoară). În figura 2.6. se remarcă 3 procese tradiţionale. Fiecare are propriul său spaţiu de adrese şi un singur fir de control (thread). Deşi în ambele cazuri noi avem 3 threaduri în figura 2.6 (a) fiecare din ele lucrează într-un spaţiu de adrese diferit în timp ce în figura 2.6 (b) fiecare împart acelaşi spaţiu de adrese.


fig 2-6. (a) Trei procese fiecare cu cate un thread

(b) Un proces cu trei thread

Ca exemplu unde ar putea fi folosite threaurile multiple, să considerăm un proces server-fişier. El primeşte cereri pentru a citi şi a scrie fişiere şi trimite înapoi datele cerute şi acceptă datele updatate. Pentru a îmbunătăţi eficienţa serverul menţine o listă a fişierelor recent folosite în memorie, cititind din listă şi scriind în listă oricân este posibil. Situaţia se modelează bine cu modelul din figura 2.6 (b). Când o cerere vine este înmânată unui thread pentru procesare. Dacă acel thread se blochează aşteptând pentru un transfer de disk alte threaduri sunt încă capabile să ruleze, aşa că serverul poate continua procesarea noilor cererilor chiar şi în timp ce diskul de intrare-ieşire are loc .Modelul din figura 2.6. (a) nu este potrivit deoarece este esenţial ca toate threadurile server să acceseze aceeaşi listă. Cele trei threaduri din figura 2.6 (b) nu împart acelaşi spaţiu de adrese şi nu pot astfel împărţi aceeasşi listă din memorie. Alt exemplu unde sunt folosite threaduri este în browserele pentru web ca de exemplu NETSCAPE şi MOSAIC. Paginile web conţin mai multe pagini mici. Pentru fiecare imagine de pe o pagină web browserul trebuie să stabilească o conectare separată între home-site şi cererea imaginii. O mare cantitate de timp este irostită stabilind şi eliberând aceste legături. Având multiple threaduri între un browser, multe imagini pot fi cerute în acelaşi timp, în cele mai multe cazuri, mărind considerabil eficienţa din moemnt ce cu imaginile mici timpul stabilit este factorul limită nu viteza liniilor de transmitere. Când multiple threaduri sunt prezente în acelaşi spaţiu de adrese câteva din câmpurile din figura 2.4. nu sunt per proces, ci per thread, aşa că un tabel separat de thread-uri este necesar, cu o singură intrare per thread. Printre elementele atribuite fiecărui thread sunt programul de contabilitate, registrul şi starea. Programul de contabilizare este necesar deoarece thread-urile ca şi procesele pot fi suspendate şi rezumate. Regiştrii sunt necesari pentru ca atunci când threadurile sunt suspendate registrii lor trebuie salvaţi. În cele din urmă threadurile ca şi procesele pot fi în starea runnig, ready sau blocked. În anumite sisteme, sistemele de operare nu sunt conştiente de threaduri cu alte cuvinte sunt administrate în întregime în spaţiul user. Cân un thread este pe punctul de a se bloca alege şi porneşte succesorul lui înainte de a se opri. Câteva pacehete de threaduri user- level sunt în uz, inclusiv P-threadurile POSIX şi C-threadurile.

În alte cazuri, sistemul de operare este conştient de existenţa threadurilor multiple per proces aşa că atunci când un thread se blochează sistemul de operare alege pe următorul să ruleze fie de la acelaşi proces fie de la unul diferit. Pentru a face organizare Kernelul trebuie să aibă un tabel de threaduri care enumeră toate threadurile din sistem analog cu tabelul proceselor.

Deşi aceste două alternative ar putea părea echivalente în ceea ce priveşte eficienţa ele diferă considerabil. Schimbând threadurile este mult mai rapid când administrarea threadurilor este făcută în spaţiul user decât atunci când un apel kernel este necesar. Acest fapt cere cu putere realizarea administrării în spaţiul user. Pe de altă parte threadurile administrate în întregime în spaţiul user şi un thread se blochează (de exemplu aşteptând pentru I/O sau o greşeală care trebuie rezolvată). Kernelul blochează întregul proces din moment ce numai este conştient că există alte threaduri. Acest fapt cere cu putere realizarea administrării threadurilor în kernel. Ca şi consecinţă ambele sisteme sunt în uz şi de asemenea diferite scheme hibride au fost propuse. (Anderson et al, 1992).

Indiferent dacă threadurile sunt administrate în kernel sau în spaţiul user ele introduc o multţime de probleme care trebuie rezolvate şi care schimbă în mod considerabil modelul programării. Să considerăm efectele apelului sistem fork(). Dacă procesul părinte are threaduri multiple ar trebui ca şi copilul să le aibă. Dacă nu procesul s-ar putea să nu funcţioneze corect din moment ce toate pot fi importante. Oricum dacă procesul-copil obţine la fel demulte threaduri ca şi părintele ce se întâmplă dacă un thread s-a blocat pe un apel ready să zicem de la tastatură. Sunt acum două threaduri blocate de la tastatură? Când o linie este tipărită amândouă threadurile obţin o copie a liniei? Doar părintele?Doar copilul? Aceeaşi problemă există când conectările sunt deschise în reţea. Altă clasă de probleme are legătură cu faptul că threadurile împart multe structuri de date. Ce se întâmplă dacă un thread închide un fişier în timp ce altul încă citeşte din el? Să presupunem că un thread observă că există prea puţină memorie să începe să aloce mai multă memorie. Se întâmplă alocarea o dată sau de 2 ori? Aproape în toate sistemele care nu au fost proiectate cu threaduri, bibliotecile (ca de exemplu procedura de alocare a memoriei) nu sunt reutizabile şi se vor distruge dacă un al doilea apel este făcut în timp ce primul este încă activ.

Altă problemă se referă la raportarea greşelilor. În UNIX, după un apel sistem, starea apelului este pusă într-o variabilă globală „errno”. Ce se întâmplă dacă un thread face un apel sistem şi înainte să fie capabil să citească errno alt thread face un apel sistem ştergând valoarea originală?

Apoi să analizăm semnalele. Anumite semnale sunt din punct de vedere logic threaduri specifice, altele nu. De exemplu dacă un thread apelează ALARM ( ) are sens ca semnalul ce rezultă să meargă la threadul care a făcut apelul. Când Kernelul este conştient de threaduri, pachetul de threaduri trebuie să ţină evidenţa semnalelor (alarmelor). Complicaţie în plus pentru threadurile user-level există când (ca şi în UNIX) un proces poate avea doar un semnal la un anumit timp şi câteva threaduri care apelează semnalul independent.

Alte semnale ca de exemplu întreruperea tastatură nu sunt threaduri specifice. Cine ar trebui să le recepţioneze? Un thread proiectat? Toate threadurile? Un thread nou creat? Toate aceste soluţii au probleme. Mai departe ce se întâmplă dacă un thread schimbă controlorii de semnal, fără să spună altor threaduri.

O ultimă problemă introdusă de threaduri este administrarea stivelor. Multe sisteme când se întâmplă să fie necesare mai multe stive, Kernelul pu şi simplu furnizează mai multe stive. Dacă Kernelul nu este conştient de aceste stive nu poate în mod automat să crească numărul lor. De fapt poate nici măcar nu realizează că greşeala memoriei are legătură cu creşterea stivelor.

Aceste probleme cu siguranţă nu sunt reparabile, dar arată că introducerea, threadurilor într-un sistem existent fără o reproiectare substanţială a sistemului, nu va funcţiona. Sintaxa pelurilor sistem trebuie redefinită şi bibliotecile trebuie să fie rescrise. Toate aceste lucruri trebuie făcute în aşa fel încât să rămână compatibile cu programele existente pentru cazul unui proces cu un singur thread. Pentru mai multe informaţii vedeţi (Hauser et al, 1993, and Marsh et al, 1991).


2. Comunicarea dintre procese
Adesea procesele au nevoie sa comunice intre ele. De exemplu, intr-o instalatie, rezultatul primului proces trebuie sa fie transmis celui de-al doilea, si asa mai departe. Astfel ca exista o nevoie de comunicare intre procese si este preferabil ca acest lucru sa se faca intr-un mod bine structurat, fara intreruperi. In sectiunile urmatoare vom analiza cateva probleme legate de comunicarea interprocesorala sau IPC.

Pe scurt, exista trei probleme. Prima dintre ele se refera la cele mentionate mai sus: modul in care un proces poate sa transmita informatia altui proces. Cea de-a doua problema consta in a ne asigura ca doua sau mai multe procese nu se incurca unul pe celalalt atunci cand incearca sa se angajeze in activitati critice (sa presupunem ca doua procese incearca fiecare sa obtinaultimii 100K de memorie). A treia se ocupa de succedarea corespunzatoare a proceselor atunci cand apare dependenta: daca procesul A produce date si procesul B le printeaza, B trebuie sa astepte pana A a produs cateva date inainte de a incepe sa printeze. Incepand cu sectiunea urmatoare vom analiza toate aceste probleme.

A. Conditiile de concurenta

In unele sisteme de operare procesele care lucreaza impreuna pot sa imparta un depozit pe care fiecare poate sa scrie si sa-l citeasca. Acest depozit comun poate sa se afle in memoria principala sau poate sa fie un fisier in retea; localizarea memoriei comune nu schimba natura comunicarii sau a problemelor care apar. Pentru a vedea modul in care functioneaza, in practica aceasta comunicare interprocesorala, sa luam un exemplu simplu: un spooler de imprimanta. Cand un proces vrea sa printeze un fisier introduce numele fisierului intr-un director de spiralare. Un alt proces, daemon-ul de imprimanta, verifica periodic daca exista fisiere care trebuie printate si daca exista le printeaza si apoi le sterge numele din director.

Imaginti-va ca directorul de spiralare are un numar mare (potential infinit) de slot-uri, numerotate 0, 1, 2…, fiecare capabil sa suporte unnume de fisier; mai inchipuiti-va ca exista doua variabile comune, out, care indica urmatorul fisier care trebuie printat si in, care indica urmatorul slot liber al directorului. Aceste doua variabile ar putea fi stocate intr-un fisier de doua cuvinte accesibil tuturor proceselor. La un moment dat, slot-urile de la 0 la 3 sunt goale (fisierele au fost deja printate), iar slot-urile de la 4 la 6 sunt ocupate (cu numele fisierelor care asteapta sa fie printate). Aproape simultan procesele A si B hotarasc ca vor sa inscrie un fisier pe lista de asteptare pentru printare. Aceasta situatie se vede in fig. 2-7.

In jurisdictia in care pot fi aplicate legile lui Murphy s-ar putea intampla urmatorul lucru. Procesul A citeste in si stocheaza valoarea, 7, intr-o variabila locala numita next­­_free_slot. Exact in acel moment apare o intrerupere si procesorul decide ca procesul A a rulat destul si il schimba cu procesul B. procesul B citeste si el in si primeste tot 7, astfel ca stocheaza numele fisierului sau in slot-ul 7 si actualizeaza in pentru a ajunge la 8. apoi se ocupa de alte sarcini.

In cele din urma, procesul A ruleaza din nou, continuand de unde a ramas. Vizualizeaza next_free_slot si gaseste 7, deci isi scrie numele fisierului in slot-ul 7, stergand numele pe care procesul B tocmai l-a pus acolo. Apoi calculeaza next_free_slot+1, care este 8, si seteaza in la 8. directorul de spiralare este acum corespunzator in interior, asa ca daemon-ul de imprimanta nu va constata nici o neregula, dar procesul B nu va obtine nici un rezultat. Situatii asemanatoare in care doua sau mai multe procese citesc sau scriu date comune si rezultatul final depinde de cel care ruleaza in momentul respectiv, se numesc conditii de competitie. Deblocarea unor programe care contin astfel de conditii nu este deloc distractiva. Testele au de cele mai multe ori rezultate bune, dar foarte rar se intampla ceva ciudat si care nu poate fi explicat.


fig 2-7. Doua procese vor sa acceseze aceeasi memorie in acelasi timp

B. Sectiuni critice

Cum evitam conditiile de competitie? Pentru a prevenii situatiile de acest gen si multe altele care implica memoria comuna, fisierele de retea, cea mai buna metoda este este sa gasim un mod de a nu permite decat unui proces sa citeasca si sa scrie date comune. Cu alte cuvinte, avem nevoie de excludere reciproca – un mod de a ne asigura ca daca unul dintre procese utilizeaza o variabila sau un fisier comun, celelalte procese nu vor avea voie sa faca acelasi lucru. Problema de mai sus a aparut datorita faptului ca procesul B a inceput sa utilizeze una dintre variabilele comune inainte ca procesul A sa fi terminat lucrul cu variabila respectiva. Alegerea operatiilor potrivite pentru realizarea excluderii reciproce este o problema de programare majora in orice sistem de operare, precum si un subiect pe care il vom analiza in amanunt in sectiunile urmatoare.

Problema evitarii conditiilor de competitie poate fi formulata si intr-un mod abstract. O bucata de timp, un proces este ocupat cu calculele interne si alte lucruri care nu duc la conditii de competitie. Totusi, uneori se poate ca un proces sa acceseze fisiere sau memoria comuna, sau sa faca alte lucruri critice care pot sa duca la competitie. Acea parte a programului in care este accesata memoria comuna se numeste zona critica sau sectiune critica. Daca am putea aranja lucrurile astfel incat doua procese sa nu se afle niciodata in acelasi timp in zonele lor critice, am putea evita conditile de competitie.

Desi aceasta conditie evita conditiile de competitie, nu este suficienta pentru a avea procese paralele care sa coopereze corect si eficient utilizand date comune. Pentru rezultate bune este necesara indeplinirea a patru conditii:

1. 
   doua procese nu se pot afla in acelasi timp in zonele lor critice
   
2. 
   nu se pot face presupuneri in legatura cu viteza sau numarul de procesoare
   
3. 
   un proces care ruleaza in afara zonei sale critice nu poate bloca alte procese
   
4. 
   nici un proces nu trebuie sa astepte foarte mult pentru a intra in zona sa critica
   

C. Excludere reciproca cu asteptare activa

In aceasta sectiune vom analiza diferite propuneri de realizare a excluderii reciproce, astfel incat in timp ce un proces este ocupat cu actualizarea memoriei comune in zona sa critica, nici un alt proces sa nu intre in zona sa critica si sa faca probleme.