sisteme de operare -...

SISTEME DE OPERARE

2009—2010

Conf.dr. Teodor-Florin FortișCursul #5

Introducere

Fire de executie

after A.S.Tanenbaum, Modern Operating Systems, 3rd edition

Fire de executie

Introducere. Modelul clasic


Procesele clasice sunt caracterizate prin executii unice, urmand un singur fir (sau directie) de executie. Acestsingur fir ofera un model simplu, secvential.

Firele de executie ofera o extensie a modelului clasic al proceselor, prin implementarea de executii paralelecare pot fi realizate in spatiul unui singur proces, acestefire avand de asemenea un anumit grad de independenta.

Firele de executie folosesc o cantitate limitata de informatii, definite in contextul procesului “gazda”. Aceasta limitare se refera doar la informatii care suntstrict legate de executia curenta.

Fire de executie



(a) Trei procese, cu cate un fir de executie. (b) Un singur proces cu trei fire de executie.

Fire de executie



Firele de executie ruleaza in contextul unui anumitproces, mostenind o parte dintre proprietatile acestuia. Uneori este folosit termenul de “proces usor” pentru a face referire la fire de executie.

Se presupune ca firele de executie sunt orientate maidegraba catre executii (calcul), in locul gestiuniiresurselor existente (si partajate) in contextul procesuluicurent.

Procesele clasice sunt puternic orientate atat catreidentificarea si gruparea resurselor, cat si spreexecutie.

Fire de executie



Fiecare fir de executie are o stiva proprie.

Fire de executie


Spatiul de adrese

Variabile globale

Fisiere deschise

Procese copil

Alarme in asteptare

Semnale si handlereasociate

Informatii de “contabilitate”

Contorul program

Stiva

Registrii

Starile.


Informatii partajate de toate firelede executie dintr-un proces

Informatii private pentru fiecarefir

Fire de executie

Introducere


Exista un inalt grad de interdependenta intre firele de executie. Aceasta se datoreaza faptului ca firele de executie ruleaza in acelasi spatiu proces, si au un accesuniform catre resursele disponibile procesului “gazda”.

Fiecare fir de executie poate interactiona cu executiaunui alt fir de executie.

Nu exista niciun mecanism de protectie la nivel de fir. Acest tip de protectie nu este necesar, avand in vederecaracteristicile principale ale firelor:

Oferirea de executii paralele pentru a rezolva (colaborativ) problemele in acelasi spatiu cu procesul gazda.

Fire de executie

Introducere


Spre deosebire de multi-tasking, multi-threadingul se bazeaza pe presupunerea ca diferitele fire ale aceluiasi proces pot partaja diferite resurse logice care sunt utilizate de catre proces.

Multi-threadingul nu implica neaparat suportul pentru multi-tasking din partea sistemului de operare.

Multi-threadingul este oferit intr-o maniera similara cu multi-programarea: alternarea executiilor diferitelorfire printr-o permanenta comutare intre firele care se executa.

Mecanismul de comutare poate fi coordonat de catresistemul de operare insusi, sau poate fi “comandat” de catreun proces, functie de modelul pentru fire de executie utilizat.

Starile firelor de executie

Fire de executie


Fire de executie



Pentru firele de executie poate fi imaginat un model similar cu cel pentru procese, cu stari de baza si tranzitiisimilare:

Fire “pregatite pentru executie”, orice fir care este capabilsa fie executat, indata ce firul este planificat pentruexecutie.

Fir “in executie”, este singurul fir activ, firul care controleazaprocesul curent.

Fire “blocate”, sunt fire care asteapta anumite evenimente. Totusi, un fir poate fi blocat si la cererea unui alt fir!

Fire “incheiate”, sunt fire care si-au terminat activitatea, siasteapta raportarea rezultatelor executie (prin mecanismuljoin).

Fire de executie



In cazul modelului Windows 2000, exista urmatoarele sase stari:

Pregatit: aceasta stare precizeaza un fir care poate fi planificat pentruexecutie. Micro-nucleul va lua decizia asupra firului care va fi planificatefectiv.

Standby: stare care specifica faptul ca firul a fost ales pentru executiepe un procesor. Firul ramane in aceasta stare pana cand procesorul estepregatit pentru a-l suporta.

In executie: acesta este firul activ. Executia sa se incheie la terminarefirului, blocarea acestuia, expirarea feliei de timp sau evacuarea firului.

In asteptare: un fir in asteptarea unei operatii I/O, unei sincronizari sauun fir care a fost suspendat.

Tranzitie: o stare temporara care specifica fire in asteptare ale carorresurse sunt insa temporar indisponibile.

Terminat: un fir terminat, din unul din motivele: terminare normala, datorata unui alt fir, prin terminarea procesului parinte.

Implementare

Fire de executie


Fire de executie

Crearea firelor de executie


Fiecare proces isi incepe executia ca un proces cu un singur fir.

Firul principal este responsabil cu crearea altorfire. Mai tarziu, fiecare alt fir este de asemeneacapabil sa creeze alte fire.

Tinand seama de caracteristicile firelor, utilizareasi mentinerea unor mecanisme de tip parinte-copileste o sarcina dificila.

Apelul tipic pentru aceasta operatie este de forma thread_create()

Fire de executie

Terminarea firelor de executie


La fel ca pentru proces, terminarea firelor se poaterealiza explicit, printr-un apel thread_exit(), sauimplicit, odata ce firul returneaza si/sau terminaexecutia asociata functiei de fir.

Firele de executie ofera mecanisme proprii de sincronizare, prin utilizarea apelurilor de bazathread_wait() si thread_join(). Pentru a utiliza acest tip de sincronizare, un fir trebuie sa fie in starea joinable.

Mecanismele de sincronizare pot include primitive ale SO, cum ar fi variabilele de conditie (ca mecanism de semnalizare a unor conditii de continuare a executiei), excluderea mutuala (mutex), semafoare, si altele.

Fire de executie

Controlul executiei


Firele sunt executate in spatiul unui singur proces, astfel incatmecanismele de limitare a timpului de executie nu mai sunt efective.

Diferitele fire vor concura permanent pentru rezolvarea sarcinilor in spatiulproces. Pornind de la aceasta idee, este extrem de important ca firele sa fie capabila sa ofere voluntar resursele detinute altor fire.

Firele de executie utilizeaza un apel de forma thread_yield() pentrua oferi controlul catre alte fire; acest apel poate fi utilizat pentruevaluarea unor anumite conditii.

Pentru a concepe un mecanism de control al firelor de executie, pot fi avute in vedere cateva probleme, cum ar fi:

Mostenirea firelor de la procese copil (de regula, acest tip de facilitate nu este oferita de catre sistemul de operare)

(Re)utilizarea resurselor care sunt detinute exclusiv de catre un alt fir, in urma unor evenimente neprevazute (de exemplu, datorate unui alt fir).

Fire de executie

Implementare. FCE in spatiul utilizator


O abordare posibila in cazul sistemelor de operaresimple, cum ar fi SO mono-utilizator, pentru sisteme de operare care nu ofera suport pentru executia firelorsau pentru orice alt sistem de operare.

Executia firelor este realizata doar in spatiul utilizator:

SO nu are niciun fel de informatie despre aceste executii.

Intregul management este rezolvat la nivel de proces, printr-un subsistem specializat de management al firelor.

Acest management este bazat pe o tabela de fire, insotita de decizii similare deciziilor de planificare.

Fire de executie



(a) Fire de executie in spatiul utilizator. (b) Fire de executie in spatiul nucleu.

Fire de executie



Deoarece toate firele sunt executate in spatiulutilizator, activitatea planificatorului de fire trebuiesa fie extrem de rapida.

Contra: la utilizarea apelurilor cu blocare (ex. open, read, alte apeluri cu fisiere) este posibila blocareaintregii aplicatii, nu doar a firului curent.

Contra: un singur fir poate fi executat la un moment dat. Executia altor fire este bazata integral pecorectitudinea firului curent (de exemplu, acest trebuiesa emita apeluri explicite thread_yield() sau similarepentru a renunta la controlul asupra procesului).

Fire de executie

Implementare. FCE in spatiul nucleu


De aceasta data activitatile de management ale firelor sunt“pasate” sistemului de operare.

SO va oferi apeluri sistem specifice pentru gestiunea firelor, si vamentine informatii suplimentare pentru acest scop.

Acum firele blocate nu mai blocheaza intreaga aplicatie

SO este capabil sa planifice de data aceasta alte fire ale aceleiasi aplicatii, daca este cazul.

Crearea si stergerea firelor este insa costisitoare, fiindsimilare cu operatiile pentru procese.

Pentru a trece peste aceasta dificultate, SO poate mentine un set de socluri-fir, iar firele sterse vor fi doar marcate, insa pastrate in sistem pentru a grabi operatii viitoare de creare a firelor noi.

Fire de executie

Implementare. Abordarea hibrida


De regula SO nu se limiteaza la una dintre cele douaimplementari precizate anterior. O abordare hibridaeste utilizata pentru a combina avantajele firelor in spatiul utilizator cu managementul firelor in spatiulnucleu.

In abordarea hibrida, firele sunt mapate in spatiulnucleu, astfel incat vor putea fi oferite mecanismeletipice pentru gestiunea firelor (si proceselor).

Nucleul SO este insa interesat doar in aceste activitati de management, fara un interes deosebit pentru obiectelegestioante (care acum exista in spatiul utilizator).

Fire de executie

Implementare. FCE in spatiul nucleu


Multiplexarea firelor in spatiul utilizator pe fire in

spatiul nucleu.

Fire de executie

Implementare. Probleme uzuale


Variabilele globale pot ridica probleme serioase cand sunt utilizate in aplicatii multifir. Aceste probleme se datoreaza faptului ca fiecare fir poate accesa orice informatie din spatiul procesului.

Deoarece nu exista mecanisme de protectie bine definite, ar putea fiposibil ca diferitele fire de executie care partajeaza aceleasi informatiiglobale sa fie capabile sa modifice simultan aceste valori, oferind astfelposibilitatea unei utilizari incorecte a acestora.

De exemplu, un executia unui fir s-ar putea baza pe o valoare gestionata de un alt fir. Daca primul fir foloseste aceasta valoare inainte ca celalalt fir sa fi fostcapabil sa-l modifice, ar putea fi posibil un comportament incorect al primuluifir.

Astfel de probleme pot fi evitate astfel:

Evitarea problemei: neutilizarea de informatii globale care pot fi alterate.

Oferirea de vederi private pentru variabilele globale (aceasta informatiepoate fi numita “variabila global-locala”).

Fire de executie



O biblioteca de functii este reentranta daca un alt doilea apel este posibil in timp ce un prim apel este in functiune (nu neaparat din acelasi fir de executie).

Uneori o astfel de functie este numita… thread-safe. Majoritatea bibliotecilor de functii nu sunt, insa, reentrante. Un al doilea apel ar putea lasa diferitelestructuri interne ale acestora intr-o stare inconsistenta.

Solutii pentru aceasta problema includ:

Rescrierea bibliotecii de functii pentru a putea oferi o varianta reentranta;

Interzicerea de apeluri “nesigure” (non-reentrante) in aplicatiile multifir.

Fire de executie



Pentru sistemele de operare cu fire de executie in

spatiul utilizator, cand stiva asociata unui fir este plina,

sistemul de operare nu va reactiona neaparat. Aceasta

situatie ar putea fi posibila datorita lipsei unei cereri

explicite a procesului care detine firul.

Procesul insusi este responsabil cu gestiunea stivelor,

astfel incat subsistemul de gestiune a firelor de executie

ar trebui sa rezolve cererile suplimentare ale firelor de

executie si sa le redirecteze catre sistemul de operare.

Fire de executie

Utilizarea FCE


Printre motivele utilizarii firelor de executie, putemaminti urmatoarele:

Procesare “foreground” si “background”: o aplicatie arputea folosi tehnicile multifir pentru a afisa un meniu, pentru a cauta un document, dar si pentru o activitatede update, realizate in acelasi timp.

Procesari asincrone: activitatile asincrone ar putea fiimplementate intr-o aplicatie folosind diferite fire de executie. De exemplu, o activitate de update, o activitate de auto-salvare a documentelor ar putea ficonsiderate activitati tipic asincrone.

Fire de executie

Utilizarea FCE. Exemple


Imbunatatirea vitezei de executie: diferitele fire ar

putea fi utilizate pentru a realiza suprapunerea

operatiilor.

De exemplu, unul dintre fire ar putea realiza anumite

operatii de calcul, in timp ce un alt fir pregateste

datele pentru calculele urmatoare.

Daca o problema poate fi decompusa si diferitele sub-

probleme pot fi rezolvate simultan, ar putea fi utilizate

mai multe fire de executie pentru a realiza aceste

calcule.

Fire de executie



Exemplu: un procesor de texte cu trei fire de executie.

Fire de executie



Structura modulara a programelor:

Multi-threadingul poate fi utilizat pentru a oferi

mecanisme facile de design si implementare pentru

aplicatiile care realizeaza activitati multiple, cu un

numar mare de surse si destinatii pentru operatiile de

intrare/iesire.

Fire de executie



Un server Web multifir simplu.

Fire de executie



O bucata de cod pentru Figura precedenta

(a) Firul Dispatcher.

(b) Firul Worker.

Fire de executie POSIX

Fire de executie


Fire de executie

Recapitulare. Multi-threading

Motive pentru utilizarea FCE

Cost inalt pentru crearea de procese noi (via mecanismulfork()).

FCE necesita mai putina memorie la momentul pornirii.

Acces facil catre informatiile sau datele partajate.

Fiecare proces este compus din unul sau mai multe FCE.Informatiile partajate de toate procesele pot include: Memoria (codul program, datele globale); Fisierele deschise, socketuri deschise; Handlere pentru semnale si semnale emise; Informatii de mediu (e.g. directorul curent, ID utilizator, etc.).


FCE ca procese usoare

Ca in cazul proceselor, fiecare FCE este dotat cu o serie de informatii proprii: Thread ID (integer);

Thread stack, registrii, program counter;

errno (in caz contrar errno ar fi inutil!)

Toate FCE care exista in cadrul aceluiasi proces au acces uniform catre datele globale, precum si catrezonele de memorie partajate. Acestea pot folosimemoria partajata pentru a rezolva cerintele de comunicare.


Caracteristici

POSIX Threads

Un API pentru FCE cu larg suport;

Impementarile sunt disponibile pentru platforme diferite, inclusiv Windows;

Pentru sistemele *NIX, sau UNIX-like, aplicatiile pot fi legate cu biblioteca corespunzatoare intr-o maniera relativ simpla:

E.g. gcc … -lpthread

Nota: compilatorul ar putea fi ajutat utilizand (pe diferitesisteme) versiuni reentrante ale functiilor de bibliotecaexistente, atunci cand acestea sunt disponibile.

E.g. strtok_r () este sigura pentru utilizare in FCE, spre deosebirede strtok ().


Crearea FCE

Crearea FCE

Realizabila printr-un apel pthread_create :

pthread_create(pthread_t *tid, const pthread_attr_t *attr, void

*(*func)(void *), void *arg);

Functia returneaza 0 pentru SUCCESS, o valoarea

pozitiva pentru situatie de eroare (Nota: cu toate

acestea, multe apeluri sistem intorc -1 pentru situatia de

eroare )

Aceasta functie nu seteaza errno in caz de eroare!

Noul FCE returneaza ID-ul prin valoarea “pthread_t *tid.


Crearea FCE

Crearea FCE

Functia func () specificata este functia de fir care urmeaza sa fie apelata.

FCE isi termina existenta indata ce functia de fir se incheie.

Pointerul pthread_attr_t * attr este utilizat pentruprecizarea atributelor FCE, incluzand:

Informatii asupra starii de detasare;

Informatii de planificare.

(Sau precizati NULL pentru valorile implicite)


Crearea FCE

Identificarea FCE:

Fiecare ID de fir este unic in contextul procesului curent.

Un FCE isi poate obtine propriul identificator prin

apelul pthread_self ().

Toti identificatorii sunt de tip „pthread_t‟. Acesta este o

simpla valoare intreaga (deghizata, ca multe alte

tipuri).


Crearea FCE

La crearea FCE pot fi transmise argumente catrefunctia de fir. Acestea pot fi pasate prin parametrul„void * arg‟. Folositi NULL pentru a preciza lipsaargumentelor. Mecanismul implicit se bazeaza pe argumente de tipul

generic „void *‟ pentru functia de fir.

Parametrii complecsi pot fi transmisi printr-o impachetare corespunzatoare (e.g. struct, typedef): Creati structurile necesare si transmiteti adresele acestor

structuri; Nota: deoarece diferitele fire folosesc stive distincte

(fiecare cu date private proprii), nu veti putea utiliza date locale pentru a le transmite prin intermediul argumentelor.


Crearea FCE. Exemplu

#include <pthread.h>

#include <stdio.h>

void *print_num (void *a)

{

int i, odd = *((int *) a), ret ;

for (i=0; i<4096; i++)

{

printf ("%4d ", odd) ;

odd += 2 ;

}

ret = (i*3) ;

pthread_exit (&ret) ;

}

int main ()

{

int i, a=1, b=2, thrRet ;

pthread_t thrID1, thrID2 ;

pthread_create (&thrID1, NULL, &print_num, &a) ;

pthread_create (&thrID2, NULL, &print_num, &b) ;

pthread_join (thrID1, NULL) ;

pthread_join (thrID2, (void *)&thrRet) ;

printf ("\n%d\n", thrRet) ;

return 0 ;

}


Crearea FCE

Ciclul de viata

Functia de fir, „func()‟, este executata indata ce FCE a fost

creat.

FCE isi termina executia indata ce functia „func()‟ se incheie.

Alternativ, un FCE poate folosi functia pthread_exit() pentru

a cere terminarea executiei.

Cu toate acestea, un FCE se incheie atunci cand functia main

se incheie sau cand exista un apel explicit exit() din orice

alt fir din spatiul procesului.


Starile FCE

Pot fi identificate doua stari (de detasare) : detasat si joinable.

FCE detasate

La terminarea FCE, toate resursele acestuia sunt eliberate de catresistemul de operare. In cazul FCE, acestea nu pot fi “reunite” cu alte fire.

Nu exista niciun mecanism pentru recuperarea valorii returnate de functia de fir (de fapt, nici nu exista valoare de retur :D).

FCE Joinable

La terminarea FCE, ID si starea de terminare sunt salvate de catre sistemulde operare.

Un FCE se poate “reuni” cu un alt fir printr-un apel explicit pthread_join ():

Firul apelant isi suspenda activitatea (se blocheaza) pana cand firul precizat isitermina executia. Totusi, celalalt fir trebuie sa fie in starea joinable!

int pthread_join( pthread_t tid, void **status);

Firul apelant poate, prin acest mecanism, sa recupereze starea de terminare a celuilalt fir.


Date globale

Probleme cu utilizarea FCE: variabile globaleatomic_t counter=0;

void *dummy(void *arg) {

counter++;

printf("Thread %u has counter %d\n",

pthread_self(), counter);

}

void main() {

int i; pthread_t tid;

for (i=0;i<10;i++)

pthread_create(&tid,NULL,dummy,NULL);

}

In acest exemplu simplu, cele 10 FCE pot accesa simultan si pot modifica valoarea „counter‟. Comportamentul la finalulsecventei de fire este dificil de prezis.


Date globale

Probleme cu utilizarea FCE: variabile globale

La utilizarea informatiilor partajate (e.g. acces la variabile

globale), FCE pot utiliza mecanisme tipice IPC pentru a

rezolva eventualele probleme.

Biblioteca pthread ofera suportul necesar pentru mecanisme

de excludere mutuala (mutex).

Prin mutex, diferitele FCE pot controla modul in care se

realizeaza accesul catre informatiile partajate, prin

blocarea temporara a accesului.

De precizat ca acest mecanism nu este impus de catre

sistemul de operare!


Mutex & variabile de conditie. Date globale

O blocare este implementata prin utilizarea unei variabileglobale de tiptype pthread_mutex_t.

pthread_mutex_t lock= PTHREAD_MUTEX_INITIALIZER;

In cazul variabilelor statice, este necesara o initializare explicita cu valoarea PTHREAD_MUTEX_INITIALIZER.

In cazul variabilelor dinamice vor fi disponibile optiuni suplimentare.

Variabile de conditie

pthreads suporta conceptul de variabile de conditie, prin care un FCE

poate astepta aparitia unui eveniment generat de un alt fir.

Prin acest mecanism este posibila evitarea problemelor de asteptare

activa.

pthread_cond_t foo = PTHREAD_COND_INITIALIZER;


Mutex & variabile de conditie. Utilizare

Folosirea mutex.

Mecanismul mutex ofera doua functii cu blocare:

pthread_mutex_lock(pthread_mutex_t &);

pthread_mutex_unlock(pthread_mutex_t &);

Firul apelant se va bloca pana cand este capabil sa

finalizeze actiunea precizata (mutex lock sau unlock).

Folosirea Variabilelor de Conditie

Acestea sunt utilizate doar impreuna cu un mutex.

pthread_cond_wait(pthread_cond_t *cptr, pthread_mutex_t *mptr);

pthread_cond_signal(pthread_cond_t *cptr);


Mutex & variabile de conditie. Exemplu

pthread_mutex_t mutex;

pthread_cond_t cond;

pthread_mutex_lock (&mutex);

while ( !condition )

pthread_cond_wait (&cond, &mutex);

do_something();

pthread_mutex_unlock(&mutex);

pthread_mutex_lock(&mutex);

// make condition TRUE

pthread_mutex_unlock(&mutex);

pthread_cond_signal(&cond);


Standard “waiter” Standard “signaler”

sisteme de operare -...

Documents