 |
Mihai BUDIU -- budiu@cs.cornell.edu
decembrie 1996
Subiect: Implementarea thread-urilor fără ajutorul SO.
Cuvinte cheie: thread, proces, stivă, cadru (stack frame), context.
Cunoștințe necesare: limbajul C, funcții recursive, elemente de programare în limbaj de asamblare.
Acest articol își propune să explice unul dintre conceptele esențiale ale sistemelor de operare, ``thread-urile''. (Din păcate nu știu nici un termen românesc foarte convenabil care să fie larg acceptat pentru a traduce ``thread''; numele folosit este de obicei ``fir de execuție'', dar îl găsesc prea lung. Vă rog să tolerați acest barbarism, și probabil și alte cîteva.) Bazîndu-se pe un minim de cunoștințe, constînd în programarea cu funcții recursive și elemente de bază în C, articolul construiește toate conceptele necesare, și apoi și o implementare, a unui pachet de funcții care permite simularea execuției simultane a mai multor programe, fără nici un fel de suport special din partea sistemului de operare.
Din păcate implementarea se bazează pe folosirea în mod neconvențional a unor instrucțiuni standard C (ANSI), și s-ar putea să nu poată funcționa întotdeauna. Am testat programele pe trei sisteme diferite și au mers, dar am avut într-un fel noroc: m-am bazat pe faptul că (pentru că este mai simplu pentru cei care scriu compilatoare) anumite instrucțiuni fac mai mult decît spune manualul că trebuie să facă.
Structura de ansamblu a textului este următoarea: întîi noțiunile de thread și proces sunt explicate, iar modul în care pot fi implementate schițat. Apoi urmează o discuție despre rolul stivei în executarea programelor -- vedem faptul că o parte importantă despre starea unui program este ținută pe stivă.
Explorăm apoi funcționalitatea unor instrucțiuni C standard, dar care se comportă extrem de ciudat; vedem că ele acționează în mod dramatic asupra stivei. Urmează un experiment cu aceste instrucțiuni, a cărui menire este să verifice dacă nu cumva ele își îndeplinesc misiunea într-un mod de care ne putem folosi pentru a implementa thread-uri.
În fine, în caz că experimentul s-a dovedit reușit, trecem la a pune la lucru aceste instrucțiuni pentru a scrie un set de funcții care simulează multi-procesarea.
Programele au fost testate cu succes pe următoarele platforme: Windows NT, folosind compilatorul MS Visual C++ 4.0, SunOS 4.x, și 5.x cu gcc, Linux 2.x cu gcc. Se pare că merg și pe HP-UX.
Extensiile cu ``întreruperi'' ale programelor au fost testate numai pe sistemele Unix (Windows NT nu oferă funcția alarm() pe care ele se bazează).
Practic textul prezintă un mini-nucleu de sistem de operare în esența lui; în orice sistem modern partea care se ocupă de manipularea proceselor are o structură asemănătoare.
``Ce este un program'' probabil că toată lumea știe. Ce este un proces este un pic mai delicat, însă nu greu de înțeles. Cea mai scurtă definiție ar fi: ``un proces este un program în curs de execuție''. E o mică diferență între cele două noțiuni: în timp ce un program este un concept ``static'', imuabil, un proces este un obiect care se schimbă într-una. De exemplu, atunci cînd un program se execută, el modifică valorile variabilelor sale. La fiecare moment de timp procesul deci arată altfel. Distincția este aceeași ca cea dintre un drum trasat pe o hartă (programul) și o excursie reală pe acel traseu (procesul). Nici măcar nu este obligatoriu ca la rulări diferite un același program să parcurgă aceleași faze: execuția lui poate depinde de evenimente externe, care sunt diferite (ca de exemplu interacțiunea cu utilizatorul).
Putem vorbi despre ``starea'' unui proces la un anumit moment de timp. Starea ar trebui să ne spună cam ``în ce fază de execuție a programului am ajuns''. Cum se poate descrie starea unui proces?
Ei bine, starea trebuie să cuprindă o indicație despre următoarea instrucțiune care se va executa. La nivelul programelor în limbaj-mașină instrucțiunea următoare este indicată prin valoarea unui registru special, numit PC de obicei (``Program Counter'') (numai Intel se încăpățînează să-i zică IP - ``Instruction Pointer''), care arată adresa în memorie unde se află următoarea instrucțiune de executat.
PC-ul singur însă nu ajută: dacă suntem în mijlocul unei bucle, PC-ul nu ne poate spune de cîte ori s-a executat bucla. Descrierea starea unui proces mai trebuie să conțină și descrierea valorii tuturor variabilelor cu care operează programul.
Din păcate nici atîta nu ajunge pentru a descrie starea unui proces. Ca să va convingeți iată un exemplu:
int f(int a)
{
/* PC==> */ printf("%d\n", a);
}
int g(int a)
{ f(a); }
int main(void)
{ int x = 5; f(x); g(x); return 0; }
Chiar dacă vă spun că PC-ul punctează unde am pus comentariul, în corpul funcției f(), și vă dau valorile variabilelor, nu veți putea spune ce se va întîmpla mai departe dacă nu știți cine a chemat pe f(): main() sau g()?
O descrierea a stării procesului trebuie să includă deci și istoricul apelurilor de funcții: ce funcții au început să se execute și nu s-au terminat încă. Vom vedea că această informație este de obicei menținută pe o stivă de către calculator.
Să rezumăm: starea unui proces este descrisă de
Calculatoarele moderne țin aceste informații în memorie (cu excepția PC), în zone diferite, astfel:
| Informația | Unde |
| programul | ``segmentul de cod'' |
| variabile | ``segmentul de date'' |
| funcțiile în curs de execuție | ``segmentul de stivă'' |
Practic dacă vreau să execut un program (să-l transform într-un proces), calculatorul trebuie să aloce cîte o zonă de memorie pentru fiecare din aceste părți și să pună în PC adresa primei instrucțiuni.
Partea interesantă este că informația de mai sus este nu numai necesară ci și suficientă pentru a descrie starea unui proces. Mai exact, dacă ``salvăm'' cumva această descriere, stingem calculatorul, și după o săptămînă restaurăm starea așa cum era salvată, procesul își va continua nestingherit execuția din locul în care a fost salvat, ca și cum nimic nu s-ar fi întîmplat.
Tehnica asta este familiară de cînd există congelatoare: o găină pusă la înghețat nu își schimbă starea de loc pînă o scoți de acolo. Toate variabilele care descriu starea ei (de descompunere) sunt înțepenite la valoarea pe care o aveau în momentul congelării.
Pe acest lucru se bazează și sistemele de operare moderne cînd dau impresia executării simultane a mai multor procese: (time-sharing) de fapt ele execută un proces o vreme (cîteva milisecunde), apoi pun deoparte starea procesului, iau starea altui proces, îl execută pe ăsta o vreme, după aceea se întorc din nou la primul și tot așa.
Dacă cele două procese pe care le execuți în ``paralel'' încap simultan în memorie treaba este și mai simplă: nu ai decît de mutat PC de la unul la altul, și un indicator pentru care segment de date și stiva se folosește în momentul curent! Faptul că un proces folosește numai propriile lui zone de memorie asigură faptul că nu îl ``deranjează'' pe celălalt.
În dorința lor de perfecțiune, proiectanții au observat că pot îmbunătăți schema în cazul în care cele două procese execută același program (nu este o presupunere complet absurdă, mai ales dacă pe același calculator pot lucra mai multe persoane simultan). Îmbunătățirea se bazează pe faptul că (practic niciodată) segmentul de cod nu se schimbă. Din cauza asta dacă ai două procese care au același segment de cod, le poți aranja să folosească împreună acea parte de memorie. Observați că asta nu înseamnă că fac exact același lucru la un moment dat: PC-urile lor pot avea valori complet diferite.
Odată ideea asta născută, a fost împinsă și mai departe: datorită faptului că procesele nu au nici un fel de memorie modificabilă în comun, este destul de greu pentru două procese să schimbe informații (trebuie să folosească fișiere, ceea ce e complicat și lent). Ce-ar fi dacă am permite proceselor să aibă și ceva memorie în comun? Ele vor trebui să fie atente să nu se calce pe picioare (să nu modifice fiecare starea altuia cînd nu trebuie), dar ar putea cîștiga mult prin eficiența mare a comunicării.
Așa s-a născut noțiunea de ``thread'': două thread-uri sunt procese care au în comun și segmentul de date, pe lîngă cel de cod. Din cauză că thread-urile au în comun atît de mult, cîteodată conceptual sunt privite ca parte a aceluiași proces, dar care de data asta poate avea mai multe ``fire de execuție'' simultan (traducerea termenului ``thread'' este fir). Pentru utilizator e ca și cum ai scrie un program care poate executa mai multe funcții simultan (de altfel asta vom obține și noi în final).
Distincția dintre un proces și un thread este doar de natură a folosirii în comun a memoriei: practic două procese care execută același program au memorii complet disjuncte, dar două thread-uri care execută același program folosesc segmentul de date în comun.
În secțiunea de față o să ne concentrăm privirea spre una singură din zonele de memorie de care are nevoie un proces (sau thread): stiva. Vom vedea de ce e nevoie de ea, și cum este ea folosită. Vom vedea că unul dintre cele mai utile concepte ale limbajelor de programare moderne, recursia, este implementată folosind mecanismul de stivă.
Să considerăm un exemplu simplu, folosit de toată lumea:
int factorial(int n)
{
if (n == 1)
return 1;
else
return
factorial(n-1) /* <= PC1 */
* n;
}
int main(void)
{
int l;
l = factorial(2); /* <= PC2 */
printf("%d\n", l);
l = factorial(4);
printf("%d\n", l);
return 0;
}
Cum merge? Păi execuția se desfășoară așa: începem cu prima instrucțiune din main(), care este chiar un apel al funcției factorial. Pentru a executa factorial() programul pune bine la păstrare valoarea curentă a lui PC; cînd funcția factorial() va termina valoarea păstrată va fi folosită pentru a continua execuția. (Dacă nu am salva valoarea lui PC cînd chemăm factorial(), nu am putea ști atunci cînd se va termina dacă a fost chemat prima oară, cu argumentul 2, sau a doua oară, cu 4.)
În continuare se procedează astfel: PC-ul este pus să arate la prima instrucțiune din corpul funcției factorial; am început s-o executăm. Valoarea argumentului n este luată din valoarea cu care a fost chemat factorial, 2. Programul se execută de sus în jos, n != 1, deci se execută return-ul după else. Însă return are nevoie de valoarea calculată de factorial(n-1) = factorial(1)! Înainte de a termina prima invocare a funcției factorial, trebuie să începem o a doua. Trebuie să punem deoparte valoarea pe care o are n acum (2), ca factorial(1) să nu o strice. Trebuie să ne amintim și PC-ul curent, ca după ce factorial(1) se termină, să putem face înmulțirea și să terminăm return-ul.
Deja figura se complică: ținem minte locul de unde factorial a fost chemat din main, dar și locul de unde s-a chemat singur, și valorile variabilelor sale locale din acea clipă...Ne încurcăm. Avem nevoie de o structură care să facă ordine.
Observați două proprietăți ale funcțiilor de care vom profita:
De fapt noi folosim același nume pentru o mulțime de obiecte: la un moment dat pot exista multe n-uri.
Funcțiile recursive se implementează folosind cadre (``(stack) frames'' în engleză). Un cadru este o structură de date care ține în ea informațiile necesare executării unei instanțe a unei funcții -- fiecare factorial care se va executa va avea propriul lui cadru.
Un cadru de stivă arată cam așa:
| argument 1 |
| argument 2 |
| ... |
| argument n |
| PC pentru întoarcere |
| variabile locale |
| spațiu de lucru temporar |
Cadrele sunt construite în două etape: prima parte (cea de deasupra liniei) este făcută de funcția care o cheamă pe cea care posedă cadrul; prin această zonă chemătorul și chematul comunică.
Partea a doua este construită de funcția care folosește cadrul cînd începe să se execute. Acolo își pune ea lucrușoarele pe care vrea să le folosească singură.
Ca o consecință a faptului că funcțiile se termină invers de cum au început, putem pune cadrele lor pe o stivă (stiva, țineți minte=ultimul venit-primul ieșit). În fiecare moment funcția care tocmai se execută folosește cadrul din vîrful stivei.
| acțiune | operație pe stiva |
| apel de funcție | se creaza un nou cadru în vîrf |
| return | se distruge cadrul din vîrf |
| execuția funcției | se folosește cadrul din vîrful stivei |
Ca să fie și mai clar, să vedem cum arată stiva în momente succesive, în timpul execuției programului de mai sus:
Figura 4 ne arată stiva in 4 momente succesive: la început, înainte ca main() să cheme factorial(2), după aceea cu cadrul lui factorial(2) construit. Observați cum cadrul lui factorial(2) conține adresa de întoarcere (PC2) în main(). Funcțiile noastre nu au variabile temporare, iar singura variabilă locală este l, în main.
Apoi factorial(2) cheamă factorial(1): cadrul lui factorial(2) continuă să existe, cu n=2, și un nou cadru se crează, în care n=1. Observați că factorial(1) ține minte în cadrul lui că a fost chemat de factorial(2), deci PC-ul după terminare trebuie să fie PC1. Observați și că pe stivă se află două valori ale lui n, una în cadrul lui factorial(1), una în cadrul lui factorial(2). Regulile limbajului C spun că, dacă funcția curentă vrea să știe cît este n, valoarea cu care va lucra este cea din cadrul curent.
factorial(1) se termină repede, returnînd valoarea 1. Cadrul lui factorial(1) este distrus. Cadrul curent devine cel vechi, al lui factorial(2), a cărui execuție se reia de după PC1. Ce se întîmplă apoi: factorial(2) tocmai a aflat cît e factorial(1) (=1), așa că va continua evaluarea expresiei n * factorial(n-1). Valoarea folosită pentru n este 2, deci expresia este 2*1 = 1. Aceasta este și valoarea returnată de factorial(2), care se întoarce la main(), la adresa salvată în cadrul propriu, PC2.
După ce main() tipărește ``2'', se va efectua un șir asemănător de operații, numai că la momentul de vîrf se vor afla pe stivă 4 cadre diferite pentru factorial. Încercați să urmăriți evoluția.
Standardul ANSI pentru limbajul C conține printre instrucțiunile mai mult sau mai puțin ezoterice și cerința ca orice compilator de C regulamentar să implementeze două foarte ciudate ``funcții'', numite setjmp și longjmp. Prototipurile acestor funcții sunt în headerul <setjmp.h>.
Poate cel mai bine ar fi să începem iarăși printr-un exemplu; rulați următorul program:
#include <setjmp.h>
#include <stdio.h>
jmp_buf cadru;
void fun(void)
{
printf("fun se executa\n");
longjmp(cadru, 1);
printf("Nu ajung aici!\n");
}
int main(void)
{
if (setjmp(cadru) == 0) { /* <= PC salvat */
printf("setjmp s-a intors prima oara\n");
printf("Chem acum fun\n");
fun();
printf("Nu ajung aici!\n");
}
else { /* setjmp != 0 */
printf("setjmp s-a intors a doua oara!\n");
}
printf("Gata.\n");
return 0;
}
Acum să vedem cum funcționează...Ca mai întotdeauna în cazul limbajelor de programare, cel mai simplu mod pentru a explica ce face un program este de a explica fiecare instrucțiune componentă.
Instrucțiunea setjmp are ca argument un obiect de tip jmp_buf (tip declarat în headerul setjmp.h). (E mai simplu să ne gîndim la această instrucțiune ca la un macro, nu ca la o funcție.) Execuția lui setjmp(x) pune în structura x următoarele informații:
Instrucțiunea longjmp() are două argumente: unul de tip jmp_buf, în care un setjmp() anterior a scris ceva, și o valoare numerică. Efectul executării lui longjmp(x, v) este:
Să ne uităm la programul de mai sus din nou. El va tipări:
Execuția începe cu setjmp(cadru). Asta salvează în variabila cadru descrierea cadrului funcției curente, main(), și valoarea PC, care punctează la linia cu comentariul. setjmp() întoarce 0, așa că if-ul este ``adevărat''. Prima linie se tipărește acum, ca și a doua.
Se cheamă fun(), care scrie linia a treia.
Partea interesantă începe: se execută longjmp(cadru, 1). Aplicînd definiția de mai sus, asta înseamnă:
Deci if-ul se execută din nou și el, pe ramura else de data asta. Asta cauzează apariția liniei 4.
Linia 5 apare apoi natural.
Interesant, nu?
Practic longjmp face o ``întoarcere în timp'', la situația pe care o avea execuția unui program în momentul cînd a executat setjmp.
Care e folosul unor asemenea instrucțiuni?
setjmp și longjmp au fost create pentru a ușura tratarea erorilor: dacă ceva se întîmplă undeva în adîncurile misterioase ale unor funcții recursive, poți imediat ``ieși la suprafață'' cu un longjmp, fără să trebuiască să scrii fiecare funcție de pe drum în așa fel încît să verifice dacă nu cumva funcțiile pe care le cheamă au produs vreo eroare.
(Modul acesta de a trata erorile poate fi îmbunătățit folosind limbaje care permit definirea și tratarea excepțiilor, care funcționează într-un mod asemănător, dar mai elegant. De altfel compilatorul de C de la Microsoft pentru Windows NT chiar extinde limbajul C pentru a încorpora excepții; însuși sistemul de operare Windows NT ajută la asta).
Să mai observăm că în momentul executării instrucțiunii longjmp cadrul de stivă indicat de jmp_buf-ul dat ca argument lui longjmp trebuie sa existe! (Dacă nu, dezastre se vor întîmpla.) Din această cauză standardul ANSI spune despre longjmp: ``longjmp poate fi executată numai într-o funcție care este un descendent direct din funcția care a executat setjmp''. Datorită modului în care se crează și distrug cadre de stivă, această cerință îndeplinită va garanta existența cadrului la care se sare.
[Cu alte cuvinte nu se poate face așa:
jmp_buf x;
int g()
{ setjmp(x); }
int h()
{ longjmp(x); }
int main()
{ g(); h(); }
pentru că atunci cînd h() face longjmp, cadrul salvat în x, al funcției g() nu mai este pe stivă, pentru că funcția g() și-a terminat execuția -- h() nu este un descendent direct al lui g().]
Am spus mai sus ca longjmp ``șterge'' de pe stiva toate cadrele pîna la cel salvat. De fapt acest lucru este foarte costisitor, și este mult mai simplu pentru longjmp doar să ``mute'' vîrful stivei la cadrul indicat. Este o șansă destul de mare ca stiva între cadrul la care se sare și cel de la care se sare să rămînă neatinsă.
Mai trebuie să vedem și dacă longjmp poate fi ``prostită'' să sară în alte direcții decît scrie la carte; să încercăm următorul program:
#include <setjmp.h>
#include <stdio.h>
jmp_buf b[2];
int setup = 0;
void fun1(void);
void delay(void) { for (long i=0; i < 5000000; i++); }
void fun0(void)
{
if (setjmp(b[0]) == 0)
fun1();
else {
printf("Fun 0\n");
delay();
longjmp(b[1], 1);
}
}
void fun1(void)
{
if (!setup) setjmp(b[1]);
setup=1;
printf("Fun 1\n");
delay();
longjmp(b[0], 1);
}
int main(void)
{
fun0();
return 0;
}
Funcțiile fun0() și fun1() nu au variabile locale și nici argumente; practic cadrele lor nu conțin nici un fel de informații interesante.
Evoluția programului nu este prea greu de urmărit, cel puțin pînă la executarea lui fun1(). Practic main() cheamă fun0(), acesta își salvează cadrul în b[0], fun0() cheamă apoi fun1(), care salvează cadrul lui personal in b[1], și scrie ceva pe ecran.
Partea interesantă începe: fun1() face un longjmp la b[0]; dacă avem noroc, aceasta mută PC la loc în fun0(), care se re-execută. Vom obține pe ecran:
Fun1 Fun0 Fun1 ...
Dacă programul compilat de dumneavoastră nu se comportă astfel, înseamnă că longjmp nu vrea să sară cînd cadrul descris de jmp_buf nu este anterior celui curent pe stivă. Puteți continua să citiți textul mai departe, dar programele pe care le prezentăm nu vor funcționa nici ele; desigur, se pot scrie altfel, fără a folosi setjmp și longjmp, în limbaj de asamblare. Însă detaliile ar deveni mai proeminente decît tabloul însuși.
Presupunînd că
vom implementa acum pas cu pas un set de funcții care simulează multithreading. Ideea centrală este următoarea: pe stivă creăm mai multe cadre, a căror descriere o salvăm într-un vector de jmp_buf. După aceea, să executăm thread-ul 10 înseamnă să facem cadrul din căsuța 10 a vectorului cadrul curent (cu un longjmp). Să întrerupem thread-ul 5 din execuție înseamnă să punem în căsuța 5 a vectorului descrierea cadrului curent (cu un setjmp).
Avem o singură problemă reală: cum facem ca un thread să nu dea cu stiva peste cadrele care se află pe stivă ``sub'' el? (Stiva este una: va trebui să înghesuim pe ea mai multe cadre potențial active simultan.)
Soluția este extrem de ingenioasă și simplă: pentru a crea două cadre la distanță mare pe stivă, între ele trebuie să se afle un cadru (sau mai multe) foarte mari.
Dacă ne uităm puțin mai sus, vom vedea că un cadru conține toate variabilele locale ale unei funcții; deci o funcție de genul:
void f(void) { char c[100000]; }
va avea un cadru de 100000 de octeți cel puțin!
Avem deci la îndemînă următoarele operații pe stivă:
Le putem combina pentru a obține o serie de cadre, pe care să le salvăm, plasate la mari distanțe unele de altele. Codul arată cam așa:
#include <setjmp.h>
#define NR_THREADS 2
#define SPATIU_STIVA 1024
jmp_buf contexte[NR_THREADS];
jmp_buf main_context;
void salveaza(int); /* declaratie forward */
void aloca_stiva(int thread_no)
/* aloca spatiu pe stiva pentru thread-urile thread_no -> NR_THREADS */
{
char space[SPATIU_STIVA]; /* alocare esentiala a stivei */
if (thread_no >= NR_THREADS) /* am terminat? */
longjmp(main_context, 1);
salveaza(thread_no);
}
void salveaza(int thread_no)
/* salveaza contexte pentru thread_no -> NR_THREADS */
{
if (setjmp(contexte[thread_no])) {
/* vom adauga cod aici */
}
else
aloca_stiva(thread_no+1);
}
int main(void)
{
if (!setjmp(main_context))
aloca_stiva(0);
return 0;
}
Desenele 1-5 din figura 5 arată evoluția stivei pe măsură ce aloca_stiva() și salveaza() se execută. Desenul 5 arată starea după execuția lui longjmp(main_context, 1), din funcția aloca_stiva. (Ne vom referi la desenele 6-8 mai tîrziu puțin.)
O descriere sumară a situației: avem 3 cadre ale funcției salveaza descrise de vectorul contexte, și cadrul curent este cel al funcției main(). Dacă am fost norocoși, faptul că am făcut un longjmp la main_context nu a stricat cu nimic cadrele pe care le-am pus la păstrare pe stivă. (Norocoși în sensul că implementarea lui longjmp funcționează ne-distructiv, deși standardul de C nu o obligă!)
Vom vedea că funcția aloca_stiva construiește niște ``cadre de sacrificiu'', pe care le vom folosi pentru a chema alte funcții (spațiul ocupat de cadrele lui aloca_stiva va fi re-folosit).
Mai avem de făcut puțini pași pentru a obține mai multe thread-uri: trebuie ca fiecare din cadrele (salvate în vectorul contexte) ale lui salveaza să poată invoca o altă funcție atunci cînd va fi pornit. Avem mai multe soluții, dar cea mai simplă pare să construim un vector de pointeri spre funcții: cîte unul pentru fiecare cadru salvat. Cînd vom face acel cadru curent, el va invoca funcția respectivă:
/* modificari ale codului precedent */
typedef void (*functie_initiala)(void);
functie_initiala functie_start[NR_THREADS];
void salveaza(int thread_no)
/* salveaza contexte pentru thread_no -> NR_THREADS */
{
if (setjmp(contexte[thread_no])) {
(functie_start[thread_no])(); /* invoca functia */
}
else
aloca_stiva(thread_no+1);
}
int main(void)
{
extern functie_initiala f, g; /* functiile care vor fi
executate de threaduri;
undeva in alt fisier */
if (!setjmp(main_context))
aloca_stiva(0);
functie_start[0] = f;
functie_start[1] = g;
longjmp(contexte[0], 1); /* porneste threadul 0 */
return 0;
}
Am văzut că starea stivei după executarea apelului lui aloca_stiva din main() este cea din figura 5, poza 5. După longjmp-ul din main situația devine cea din poza 6: cadrul curent este cel care a fost creat de salveaza(0) și salvat în contexte[0]. Acum salveaza() va chema funcția din căsuța 0 a vectorului functie_start; asta va transforma starea stivei ca în poza 7.
Primul thread a pornit! Funcția f, care este de fapt cea invocată, poate face acum orice.
Mai trebuie să concepem un mecanism prin care un thread se întrerupe și dă drumul altuia. Asta e deja o sarcină relativ simplă: va implica două acțiuni:
Pentru a fi civilizați vom împacheta operația de ``comutare'' a thread-ului într-o funcție. Vom introduce și o variabilă globală care știe cine este thread-ul curent; se va dovedi foarte utilă:
/* modificari la codul anterior */
int thread_curent;
void sari_la(int th)
{
if (!setjmp(contexte[thread_curent])) {
thread_curent = th;
longjmp(contexte[thread_curent], 1);
}
}
Deja puteți testa pachetul de thread-uri scriind ceva de genul pentru funcțiile inițiale:
void f(void)
{
int x=0;
while (1) {
x++;
printf("Functia f, thread %d, x=%d\n", thread_curent, x);
sari_la(1-thread_curent);
}
}
void g(void)
{
int x=0;
while (1) {
x++;
printf("Functia g, thread %d, x=%d\n", thread_curent, x);
sari_la(1-thread_curent);
}
}
int thread_curent = 0; /* incepem cu thread-ul 0 */
Faptul că în acest program nu se cheamă pur și simplu f() și g() alternativ, ci se continuă execuția lor se vede din faptul că valorile pe care le folosesc pentru x cresc.
Într-un scenariu mai complicat, cu mai multe funcții inițiale mai sofisticate, situația stivei la un moment dat ar putea arăta ca în figura 5, poza 8: practic funcțiile inițiale au chemat alte funcții la rîndul lor (cum f() cheamă printf()), care la un moment dat și-au întrerupt execuția. Cadrele lor sunt salvate (în figură asta este valabil pentru thread-urile 0 și 2). Unul dintre thread-uri tocmai se execută (în figură thread-ul nr. 1), și cadrul lui este cel curent.
De aici încolo nu mai avem mare lucru de făcut; ar fi elegant să concepem un set de funcții care construiește thread-uri noi în mod dinamic (să nu trebuiască să punem cu mîna pointerii la început), funcții care să omoare thread-uri, și poate o funcție care să aleagă cine să se execute.
Pentru a ține mai ușor socoteala despre starea fiecărui thread ar fi bine să strîngem toate informațiile care țin de el într-o singură structură (care va include cadrul și funcția inițială); asta va necesita o ``periere'' a codului anterior, dar mai bine s-o facem acum, cît încă nu e prea mare. Iată declarațiile funcțiilor pe care ni le propunem:
/* threads.h */
#ifndef THREADSH
#define THREADSH
#include <setjmp.h>
#define PUBLIC
#define PRIVAT static
/* cuvintul cheie `static' este folosit in doua sensuri in C
* a) pentru a indica variabile locale ale unei functii care
* nu se aloca pe stiva ci in segmentul de date
* b) pentru a indica faptul ca o definitie dintr-un fisier
* nu este vizibila in exterior
* Definim macro-ul PRIVAT pentru aceasta a doua semnificatie:
* va face programul mai usor de citit
*/
#define MAX_THREADS 10 /* numarul maxim */
#define SPATIU_STIVA (32 * 1024)/* in octeti */
typedef void (*functie_initiala)(void);
struct thread {
jmp_buf context;
jmp_buf context_original; /* contextul din salveaza() */
int stare;
#define THREAD_GOL 0
#define THREAD_GATA 1 /* gata de executie */
#define THREAD_MORT 2
#define THREAD_ASTEAPTA 3 /* nefolosit, deocamdata */
functie_initiala functie_start;
};
void initializeaza(void);
int creaza_thread(functie_initiala);
/* creaza un thread; intoarce un numar (-1 = eroare) */
void omoara_thread(int);
void porneste(int th);
/* porneste executia incepind cu acest thread */
void sari_la(int th);
void alege(void);
/* alege un thread pentru executie si sari la el */
#endif /* THREADSH */
Funcția alege() este ceea ce în engleză se cheamă scheduler(): partea care decide cine cînd se execută. Vom folosi cea mai simplă implementare pentru ea, care în terminologia sistemelor de operare se cheamă ``round-robin'': o coadă circulară.
O implementare ar putea arăta cam așa (am mai modificat și funcțiile vechi pe ici-pe colo):
/* threads.c */
#include "threads.h"
#include <stdio.h> /* pentru printf */
#include <assert.h> /* pentru erori */
#define pt_orice_thread(t) \
for ((t) = tabela_thread; (t) < tabela_thread + MAX_THREADS; (t)++)
#define NU_E_THREAD (tabela_thread + MAX_THREADS)
PRIVAT struct thread tabela_thread[MAX_THREADS];
PRIVAT int thread_curent;
PRIVAT jmp_buf context_main; /* folosit la initializare */
PRIVAT void
panica(char * s, int d)
/* eroare fatala */
{
fprintf(stderr, "** panica: ");
fprintf(stderr, s, d);
fflush(stderr);
exit(1);
}
PRIVAT void
aloca_stiva(int thread_no, int maxthreads)
/* creaza spatiu pe stiva pentru thread_no pina la maxthreads */
{
char space[SPATIU_STIVA]; /* spatiul de pe stiva */
void salveaza(int, int);
if (thread_no >= maxthreads)
longjmp(context_main, 1); /* le-am facut pe toate */
salveaza(thread_no, maxthreads);
}
PRIVAT void
salveaza(int thread_no, int max)
{
char c;
if (setjmp(tabela_thread[thread_no].context)) {
tabela_thread[thread_no].functie_start();
/* daca se ajunge aici functia s-a terminat; omoara-l */
omoara_thread(thread_no);
}
else
aloca_stiva(thread_no+1, max); /* nu se mai intoarce.. */
}
PRIVAT void
copiaza_context(jmp_buf s, jmp_buf d)
/* muta date dintr-un jmp_buf intr-altul
(se bazeaza pe faptul ca sunt vectori:
a se vedea definitia din setjmp.h) */
{
int i;
char *sb, *db;
sb = (char *) s;
db = (char *) d;
for (i = 0; i < sizeof(jmp_buf); i++)
*db++ = *sb++;
}
PUBLIC void
initializeaza(void)
{
struct thread* t;
if (!setjmp(context_main))
aloca_stiva(0, MAX_THREADS);
/* pastram o copie a cadrelor initiale de acum, ca sa le punem
la loc cind moare un thread */
pt_orice_thread(t)
copiaza_context(t->context, t->context_original);
}
PUBLIC int
creaza_thread(functie_initiala start)
/* facem un thread; intoarcem tid */
{
struct thread *t;
/* cautam un loc gol in tabela */
pt_orice_thread(t)
if (t->stare == THREAD_GOL ||
t->stare == THREAD_MORT) break;
if (t == NU_E_THREAD) return -1; /* n-am gasit */
t->functie_start = start;
t->stare = THREAD_GATA;
return t - tabela_thread;
}
#define thread_corect(x) ((x) >= 0 && (x) < MAX_THREADS)
/* verifica daca un thread are un numar corect */
PUBLIC void
omoara_thread(int th)
{
struct thread *t;
if (!thread_corect(th)) {
return;
}
t = tabela_thread + th;
t->stare = THREAD_MORT;
copiaza_context(t->context_original, t->context);
/* contextul acestui thread devine cel original, al functiei
salveaza(th); in acest fel putem construi un nou thread
folosind stiva acestuia */
alege();
}
PUBLIC void
sari_la(int th)
{
struct thread *t, *c;
if (! thread_corect(th)) return;
t = tabela_thread + th;
if (t->stare != THREAD_GATA) return;
assert(thread_corect(thread_curent));
c = tabela_thread + thread_curent;
/* salvam starea curenta */
if (!setjmp(c->context)) {
thread_curent = th;
longjmp(t->context, 1);
}
else {
/* continuam chematorul (asta poate lipsi) */
thread_curent = c - tabela_thread;
}
}
PUBLIC void
alege(void)
{
struct thread *t;
static int ultimul = 0;
int i;
for (i=0; i < MAX_THREADS; i++) {
t = tabela_thread + ultimul;
ultimul = (ultimul+1) % MAX_THREADS;
if (t->stare == THREAD_GATA) break;
}
if (i == MAX_THREADS)
panica("Nu mai e nimeni gata\n", 0);
else sari_la(t - tabela_thread);
/* ne intoarcem la chemator */
}
PUBLIC void
porneste(int th)
{
struct thread *t;
if (! thread_corect(th)) return;
t = tabela_thread + th;
if (t->stare != THREAD_GATA) return;
thread_curent = th;
longjmp(t->context, 1);
}
Deja avem un pachet de funcții prin care putem simula execuția independentă ``paralelă'' a mai multor programe. Singura neplăcere constă din faptul că programele trebuie să-și paseze reciproc controlul, chemînd sari_la() sau alege().
Am dori ca un mecanism extern să se ocupe de asta fără să trebuiască să ne batem capul prea tare. Vom schița în continuare o soluție, dar trebuie să atragem atenția asupra faptului că este practic inutilă.
Cea mai simplă metodă este să avem un ``ceas'' care să întrerupă din timp în timp execuția programului curent și să zică: ``destul: este rîndul altcuiva''. La nivel hardware asta se întîmplă pe orice calculator modern, prin întreruperi.
Pentru sistemul de operare Unix avem la dispoziție toate mecanismele de care avem nevoie: semnale generate de nucleu. Problema cea mare cu folosirea semnalelor este că dacă survin în timp ce procesul execută un apel de sistem (cum ar fi scrierea într-un fișier), ele opresc apelul din execuție. Din cauza asta codul care urmează este util numai pentru a ilustra cum se fac lucrurile în realitate în interiorul nucleului, și nu și pentru a scrie programe reale cu thread-uri care se comută singure. Pentru că programul nu este lipsit de posibile învățăminte, iată cam cum ar arăta:
Fiecare proces are în Unix pentru fiecare semnal asociată o funcție care ``tratează semnalul'' (signal handler). Apariția unui semnal se soldează cu executarea funcției. Mai precis, cînd nucleul sistemului are de trimis un semnal pentru un proces, construiește pe stivă cadrul funcției de tratament, pe care după aceea o execută. Funcția asta se poate executa practic în orice moment, fără a fi chemată de program.
Cu funcția de bibliotecă signal() se declară ``handler''-e.
Unix ne mai pune la dispoziție funcția de bibliotecă alarm(timp), care la timp secunde de la invocare va genera un semnal de tip SIGALRM.
O primă schiță a tratamentului semnalelor ar fi: (indicăm adăugările față de funcțiile existente deja în codul precedent cu /**/)
#include <unistd.h> /* pentru alarm() */
#include <signal.h> /* pentru signal() */
#define CUANTA 1 /* timp in sec. intre doua intreruperi */
/* #definitia trebuie pusa in threads.h */
PRIVAT int tratam_intrerupere;
PRIVAT void
intrerupere(int ignor)
{
if (tratam_intrerupere)
panica("intrerupere in tratament de intrerupere", 0);
tratam_intrerupere++;
alarm(CUANTA);
signal(SIGALRM, intrerupere);
tratam_intrerupere--;
alege();
}
PUBLIC void
porneste(int th)
{
struct thread *t;
if (! thread_corect(th)) return;
t = tabela_thread + th;
if (t->stare != THREAD_GATA) return;
thread_curent = th;
/**/signal(SIGALRM, intrerupere);
/**/alarm(CUANTA); /* intrerupere */
longjmp(t->context, 1);
}
Aceste funcții vor face ca periodic să fie invocat alege(). Din păcate soluția nu este suficient de grijulie, pentru că există riscul ca întreruperea să vină atunci cînd facem ceva important (de exemplu lucrăm în funcția creaza_thread() și am făcut jumătate din schimbări în a pune la punct starea procesului cel nou). În general întreruperile nu trebuie să lase structurile de date ne-consistente.
Există o soluție foarte elegantă pentru asta: funcția intrerupere() va evita să cheme alege() dacă s-a ivit tocmai în mijlocul unei funcții importante, și va ruga chiar funcția importantă să cheme alege() cînd se termină.
Ca să simplificăm povestea, vom face funcțiile sari_la() și alege() private; oricum utilizatorul nu mai are nevoie de ele, pentru că sunt chemate automat.
/* threads.h -- adaugiri sau modificari */ #define CUANTA 2 /* sec */ #if 0 /* functiile astea nu mai sunt publice */ void sari_la(int th); void alege(void); /* alege un thread pentru executie si sari la el */ #endif
Modificările din threads.c sunt indicate cu /**/ (celelalte funcții rămîn neschimbate):
/* threads.c -- adaugiri sau modificari */
#include <unistd.h>
#include <signal.h>
PRIVAT int tratam_intrerupere; /* cind tratam intreruperi != 0 */
PRIVAT int mod_nucleu ; /* in functii importante != 0 */
PRIVAT int realege; /* intrerupere intirziata */
PRIVAT int
creaza_thread(functie_initiala start)
/* facem un thread; intoarcem tid */
{
struct thread *t;
/* cautam un loc gol in tabela */
/**/mod_nucleu++;
pt_orice_thread(t)
if (t->stare == THREAD_GOL ||
t->stare == THREAD_MORT) break;
if (t == NU_E_THREAD) {
/**/ mod_nucleu--;
return -1; /* n-am gasit */
}
t->functie_start = start;
t->stare = THREAD_GATA;
/**/if (realege) alege();
/**/mod_nucleu--;
return t - tabela_thread;
}
PUBLIC void
omoara_thread(int th)
{
struct thread *t;
/**/mod_nucleu++;
if (!thread_corect(th)) {
/**/ mod_nucleu--;
return;
}
t = tabela_thread + th;
t->stare = THREAD_MORT;
copiaza_context(t->context_original, t->context);
alege();
/**/mod_nucleu--;
}
/* PRIVAT void sari_la(int th)... in loc de PUBLIC */
PRIVAT void
alege(void)
{
struct thread *t;
static int ultimul = 0;
int i;
/**/realege=0;
for (i=0; i < MAX_THREADS; i++) {
t = tabela_thread + ultimul;
ultimul = (ultimul+1) % MAX_THREADS;
if (t->stare == THREAD_GATA) break;
}
if (i == MAX_THREADS)
panica("Nu e nimeni gata!\n", 0);
else sari_la(t - tabela_thread);
/* ne intoarcem la chemator */
}
PRIVAT void
salveaza(int thread_no, int max)
{
char c;
if (setjmp(tabela_thread[thread_no].context)) {
/**/ mod_nucleu=0;
tabela_thread[thread_no].functie_start();
omoara_thread(thread_no);
}
else
aloca_stiva(thread_no+1, max); /* nu se mai intoarce.. */
}
PRIVAT void
intrerupere(int ignor)
{
tratam_intrerupere++;
alarm(CUANTA);
signal(SIGALRM, intrerupere);
if (tratam_intrerupere > 1) {
tratam_intrerupere--;
return;
}
/**/if (mod_nucleu) { /* aminam alegerea */
/**/ tratam_intrerupere--;
/**/ realege++;
/**/ return;
/**/}
/**/else {
/**/ tratam_intrerupere--;
/**/ mod_nucleu++;
alege();
/**/ mod_nucleu--;
/**/}
}
Variabila mod_nucleu indică execuția curentă a unei proceduri ne-intreruptibile. O întrerupere venită în acest caz nu va face alege(), dar își va indica prezența prin realege++. Funcțiile importante care pot fi chemate de utilizator creaza_thread() și omoara_thread() vor verifica înainte de a termina dacă nu a venit o întrerupere între timp, și eventual vor chema ele alege().
Am văzut că programele se execută în niște universuri închise, pe care dacă le păstrăm neschimbate, putem întrerupe rularea programelor fără nici un fel de consecințe. Am văzut cum putem folosi acest lucru pentru a executa mai multe programe pe o singură mașină.
Stiva este un mecanism extrem de simplu, de care ne folosim pentru a implementa funcții recursive. Un cadru de stivă este micro-universul în care se execută o funcție.
Limbajul C ne oferă instrucțiuni prin care putem comuta între cadre diferite de pe o aceeași stivă: astfel obținem mai multe thread-uri.
Prezența unui ceas extern ne ajută să comutăm automat între mai multe procese.