Scheduler Activations in Windows 2003 Server

Despre User Level Threads si Kernel Level Threads si Apeluri Sistem

La ora actuala cea mai cunoscuta metoda de a crea aplicatii paralele este prin utilizarea Thread-urilor.Spre deosebire de aplicatiile clasice,unde avem un singur fir de control(un singur “flow”) ,o aplicatie care utilizeaza thread-uri poate avea mai multe fire de control,fiecare fir(thread) isi executa propriile functii,iar toate aceste fire se vor executa in paralel.Voi da un exemplu ca sa va fie mai clar:

#include <stdio.h>

//un program multi thread

main(){

functie1();
functie2();
functie3();

printf(“rezultatele procesarii sunt:…….etcn”) ;
//Aici am iesit din program
exit(0) ;
}

Acesta este un program monothread,adica cu un singur fir de executie.Acest fir de executie va excuta functia main().Aceasta functie,main() va apela mai intai functie1(),dupa care va apela functie2(),iar apoi functie functie3(), apoi va afisa rezultatele,dupa care va iesi din program prin apelul exit(0),insa chiarsi daca nu am fi avut acest apel aic,tot am fi iesit din program:-).Ideea e ca executia acestui program incepe de la un anumit punct si se termina la alt punct,adica este un fir(sau path daca vreti) de executie care poate fi urmarit chiar si cu “ochiul liber”(se incepe executia in main,se apeleaza cateva functii dupa care iesim).

Sa dam acum un exemplu de un program ,multithreaded in care avem mai multe path-uri(adica mai multe apeluri de functii se vor apela simultan).

#include <stdio.h>

//un program mono thread

functie1()

{

//Face ceva interesant

}

functie2()

{

//Face ceva interesant

}

functie3()

{

//Face ceva interesant

}

main(){

thread_tthread1,thread2,thread3;

create_thread(thread1,functie1,NULL);
create_thread(thread2,functie2,NULL);
create_thread(thread3,functie3,NULL);

printf(“rezultatele procesarii sunt:…….etc\n”) ;
//Aici am iesit din program
exit(0) ;
}

Dupa cum observati un program unde exista maii multe thread-uri sau fire de executie,nu este prea diferit la prima vedere de unul “normal”.Doar si intr-unul si in celalalt avem apeluri normal de functii…unde este diferenta?

Obeservati ca in functia main am apelat de 3 ori functie create_tread().Ok….Aceasta este o functie care va crea un thread…sau …un obiect de tip thread(by the way am zis obiect dar nu e nici un fel C++ mumbo jumbo aici…Prin obiect in contextul de fata intelegem o mai degraba o structura de date (un typedef struct thread{….}thread_t)Desi se poate implementa o librarie de thread-uri in C++, folosind OOP,insa nu am vazut o asemenea libraire.Majoritatea sunt implementate cu C “chior” fara nici un fel de OOP-eala in ele:P,si asta nu din cauza ca ar fi C++ mai prost decat C,…dar de ce sa nu ai un design simplu,si usor de inteles,in loc sa folosesti contructori /destructori si alte alea care ti-ar putea complica existenta:P).Aceste “obiecte” de tip thread vor avea o functie pe care o vor executa in contextul lor(vom discuta ceva mai incol odespre ce inseamna contextul unui thread).In exemplul de fata avem 3 structuri de tip thread_t(practic avem 3 thread-uri),pe care urmeaza sa le initializam apeland rutina create_thread(….).Aceasta rutina va initializa diverse campuri din cadrul unei structuri thread_t(vom discuta mai incolo despre ce campuri exista cam orice thread,indiferent de sistemul de operare),dupa care va “porni” executia thread-ului respectiv.Astfel cele 3 entitati isi vor executa functia lor(thread1 va executa functia functie1()…samd).Aceste functii se vor executa in paralel.In cazul in care avem un sistem multiprocesor,fiecare thread se va executa pe cate un procesor din cele existente,avand astfel parte de performanta superioara fata de primul program,deoarece cele 3 functii vor fi executate in acelasi timp,in paralel(iar programul se va termina mult mai repede),fata de primul program unude dupa ce se va executa codul din functie1(),vom reveni in main(),pentru a executa functie2(),iar apoi functie3().

Eh… cam asata e toata faza cu thread-urile.Mai pe romaneste un thread reprezinta o structura de date care are asociata “o bucata de cod” pe care o va executa.Aceasta “bucata de cod” este aici reprezentata printr-o functie,care la randul ei poate apela alte 100 de functii care sa faca lucruri utile.Asta este “tot ce se vede” intr-un program multithread.Ce nu se vede este ca fiecare thread are o stiva proprie.De exemplu in primul program unde avem un singur fir de control/executie,avem o singura stiva,folosita pentru apeluri/reveniri din functii…asa cum ati invatat la orele de informatica din liceu:P.Insa in cazul celui de-al doilea program unde avem 3 thread-uri,vom avea 3 stive,cate o stiva pentru fiecare thread din cadrul programului.Astfel fiecare thread isi va apela functia lui,care la randul ei ..asa cum am mai zis poate apela ori cate functii doreste,iar apelurile,respectiv revenirile din functii(asa numitele STACK FRAME-uri) se vor face pe stiva thread-ului respectiv.Astfel la un moment dat,thread-ul 1 dupa ce a apelat functie1(),care aceasta a apelat o functie,sa-i zicem,f1(),in tot acest timp,thread-ul 2 dupa ce a apelat functie2(),care la randul ei a apelat o functie,sa-i zicem,f2(),iar thread-ul 3 dupa ce a apelat functie3(),care la randul ei a apelat o functie,sa-i zicem,f3().Astfel,fiecare thread,are pe stiva sa o anumita “istorie”(a anumita inlantuire de apeluri de functii),independent de ce a facut alt thread in tot acest timp.CAm asta inseamna “Contextul” unui thread.De exemplu daca functia calculeaza_ecuatie_diferentiala() ) ,a fost apelata de catre functia f2(),care la randul,asa cum am mai zis, a fost apelata de catre rutina de start a thread-ului 2..adica de functia functie2(),spunem ca functia calculeaza_ecuatie_diferentiala(),este executata in contextul thread-ului 2.Sper ca cu acest exmplu s-a inteles exact ce inseamna contextul unui thread.Mai pe romaneste,daca “ceva” se executa,iar stiva curenta este a unui anumit thread X,spunem ca acel “ceva” se executa in contextul thread-ului care detine stiva curenta.

Acum dupa ce am terminat cu aceasta scurta introducere despre thread-uri,si despre ce reprezinta ele,cum lucreaza,etc,sa analizam diverse modalitati de implementare si mai ales sa vedem unde pot fi ele implementate.Pentru asta trebuie sa aveti cunostinta despre ce inseamna Ring0 aka Kernel Mode si Ring3 aka UserMode.Nu voi sta sa explic aici ce inseamna asta deoarece este peste scopul acestui articol,si in caz ca m-as pune sa fac asa,articolul ar deveni astfel prea mare si probabil ca m-as pierde in alte detalii decat cele related thread-uri

La ora actuala exista 4 modele existente pe baza carora putem crea aplicatii multithreaded.Aceastea sunt:User Level Threads/Kernel Level Threads/Hybrid Implementation/Scheduler Activations.

Voi incerca se le explic pe toate pentru a vedea exact ce avantaje si dezavantaje au fiecare in parte.

Sa incepem cu User Level Threads vs Kernel Threads.

In sistemele de operare monoprocesor/monoutilizator/monotasking precum MS-DOS,avem un singur program in executie la un moment dat,iar acest program era unul cu un singur fir de executie.Pentru a lansa un alt program in executie,trebuie sa-l terminam pe cel curent.Desi acest mod de implementare ofera foarte multa performanta,din cauza ca se evita toate complicatiile ce apar in sistemele multitasking,datorita faptului ca exista mai multe “bucati de cod”(thread-uri) care se pot executa simultan si pot accesa aceleasi resurse,deci trebe sa ne luam masuri de precautie.Intr-un sistem MS-DOS nu trebuie sa va faceti griji de asa ceva.

Fig1 – Exemplu de sistem MS-DOS

Intr-un sistem precum MS-DOS avem un singur spatiu de adrese(reprezentat prin patrat) in cadrul caruia avem un singur fir de executie(reprezentat prin acea curba).

Pe langa sistemele de tip MS-DOS mai exista si sistemele de tip UNIX,unde avem mai multe procese,iar in cadrul fiecarui proces avem cate un fir de control/executie.

Fig2 – Exemplu de sistem UNIX

Un sistem UNIX,suporta multitasking,si poate rula pe o masina cu mai multe procesoare.Astfel intr-un sistem UNIX,putem avea mai multe procese,fiecare proces fiind monothread.Evident putem avea mai multe procese decat procesoare,la fel de simplu putem avea mai multe procese si un singur procesor.Kernelul sistemeului de operare,se va ocupa de partajarea timpului,intre procese.Astfel fiecarui proces i se asigneaza o cuanta de timp,iar un algoritm implementat in kernel ,numit algoritm de scheduling,va “darui” un anumit proces,procesorului.Acum procesorul va executa instructiunile din acel proces(spatiu de adrese),pana cand va expira cuanta acestui proces.Cand cuanta(timpul) acestui proces a expirat,se va invoca din nou algorimul de scheduling(planificare) care va selecta un alt proces din sistem,si ii va “darui” acestuia procesorul…si tot asa.Astfel pe un sistem monoprocesor,unde avem mai multe procese,instructiunile din fiecare proces se vor executa intr-o maniera intretesata.Acest tip de paralelism se numeste paralelism logic,deoarece kernelul se foloseste de scheduler pentru a simula executia mai multor procese in paralel.Datorita vitezei cu care un porcesor executa instruciuni,chiar se realizeaza aceasta impresie.Intr-un sistem multiprocesor,evident pe fiecare procesor,se pot executa instruciuni din procese diferite,avand astfel parte de executie in paralel “pe bune”(aici nu se mai simuleaza nimik:P),sau paralelism fizic.

Acum probabil ca va intrebati ce este acela un proces,si care este diferenta dintre un proces si un program.Well now…un proces reprezinta un porgram in exectie.Un program este o entitate statica,adica un fisier in care cineva a scris niste instructiuni,un algoritm intr-un anumit limbaj de programare,dupa care a compilat acel fisier.Asta este un porgram.Atunci cand rulati un program,sistemul de operare se va ingriji sa creeze un nou proces(entitate dinamica),in care sa ruleze respectivul program(imagine).De exemplu..daca aveti un editor de texte,acela reprezinta un porgram,insa daca il deschideti de doua orimatunci sistemul de operare,va crea cate un proces,si in fiecare proces se va rula acelasi program.Intr-un sistem de operare ,un porces este reprezentat printr-un PCB(Process Control Block),adica o structura de date,in care sunt retinute diverse informatii referitoare la procesul respectiv,unele dintre acestea vor fi folosite de scheduler ,pentru planificare(ex:prioritate,afinitate,starea procesului,etc)…pentru mai multe informatii consultati Tanenbaum-Sisteme de Operare Moderne sau William Stallings – Operating Systems Design and Principles

Mai exista si sisteme de tip Windows NT/unde putem avea mai multe procese(spatii de adresa)in cadrul caroara putem avea mai multe thread-uri.

Fig3 – Exemplu de sistem Windows NT

De ce acest fel de implementare ales de cei de la Microsoft pentru Windows NT/XP/2000/2003?….raspunsul este…fiindca este mult mai eficient…In sistemel clasice UNIX,un proces se ocupa in primul rand de gestiunea resurselor asociate acelui proces ca de exemplu spatiul virtual de adrese(de fapt asta este cea mai importamta functie a unui proces in Windows,si anume sa furnizeze un spatiu de adrese in care thread-urile sale,sa se poate executa),precum si alte resurse…tabela de fisiere deschise.Acelasi functii leofera si un proces un window,mai putin pe cea de executie.Astfel in windows s-a realizat aceasta separare,intre gestiunea resurselor si executia unui program in sine.Chiar si un program simplu ca primul programel din acest articol in windows va fi reprezentat printr-un proces cu un singur thread in interiorul sau.

Practic asta reprezinta o abstactizare.In UNIX,un proces reprezinta o abstractizare a unui procesor fizic,sau mai degraba ca sa fiu si mai corect,un porces UNIX reprezinta o abstractizare a unei masini cu memorie si un procesor(unde memoria este reprezentata de spatiul virtual de adrese al procesului,iar procesorul este reprezentat de firul de control din cadrul procesului).Cei de la Microsoft au vrut sa fie mai smecheri si iata ce a iesit…Un proces in cadrul caruia avem mai multe thread-uri,reprezinta o abstractizare a unei masini cu memorie(spatiul virtual de adrese al procesului) cu mai multe procesoare(adica thread-urile din cadrul procesului).De aici se observa ca un thread este o abstractizare a unui procesor.In general se folosesc abstractizari de genul asta .Si ca sa va convingeti ca este corect….Avem un calculator care are 10 procesoare si o memorie partajata intre aceste procesore.Fiecare procesor va executa ceva…acel “ceva” adica acele instructiuni pe care fiecare procesor le va executa vor fi extrase din memoria partajata.La fel ca si in cazul procesului care are mai multe thread-uri….fiecare thread va fi executat pe cate un procesor,sau vor partaja un anumit procesor…iar instructiunile fiecarui thread se gasesc in acelasi spatiu de adrese furnizat de proces.

So…sper ca ati inteles care e faze cu abstractizarile astea…si cu procese /thread-uri….bla bla…acum sa trecem mai departe.Stim ce este acela un proces…. stim ca exista mai multe modalitati de integrare a thread-urilor in procese(UNIX vs WINDOWS)…linsa mai exista ceva…..unde sunt implementate thread-urile?????????

Exista mai multe “locuri” de a implementa thread-urile.De exemplu acestea pot fi implementate in Kernel Space,asa cum se intampla in Windows.Atunci cand din programul dumneavoastra creati un thread,prin intermediul apelului sistem CreateThread() din Win32API,acel thread va fi recunoscut de catre kernel,si in consecinta va fi planificat de catre scheduler(In Windows nu se planifica procesele ca in UNIX,ci thread-urile,fara sa se tina cont din ce proces fac ele parte).Windows-ul mentine o structura de date numita Dispatcher Database,care este de fapt un array cu 32 de intrari,iar fiecare intrare reprezinta capul unei liste dublu inlatuite,unde sunt inlantuite thread-urile de o anumita prioritate.

Fig4 – Exemplu de Dispatcher Database.Un array cu 4 intrari,iar fiecare intrare este capul unei liste care “leaga” toate TCB-urile(Thread Control Block) de o anumita prioritate.Alogorimul de scheduling va cauta un thread in lista cu thread-uri care au cea mai mare prioritate(in exemplul de fata in lista cu thrread-uri de prioritate 4),iar daca va gasi acolo un thread atunci va extrage thread-ul din capul listei si va face un Context Switch la el.Din cand in cand thread-urilor care au o prioritate mai mica trebuie sa li se “creasca” prioritatea,pentru a nu intra in Starvation.

In consecinta Windows,asigeanza o cuanta de timp thread-urilor si nu proceselor.Cand cuanta thread-ului curent a expirat,se va invoca scheduler-ul care va cauta un alt thread de prioritate maxima pentru a face un context switch la el.Daca nu exista nici un thread de prioritate 32,atunci se va cauta un thread de prioritate 31;daca nici asa ceva nu exista se va cauta un thread de prioritate30.. s.a.m.d.In caz ca nu se va gasi nici un thread disponibil,atunci se va face un context switch la un thread special numit IdleThread,semn ca procesorul este acuma in starea Idle.Acuma poate va intrebati cum isi da seama kernelul ca cuanta de timp a thread-ului curent a exepirat,si de fapt ce este aceasta cuanta.In orice calculator exista un timer,care intrerupe procesorul la o anumita frecventa.De exemplu pe un sistem 386..din cate stiu eu….timer-ul sistemului intrerupe procesorul la o frecventa de 50HZ(Hertz)…in traducere romaneasca adica de 50 de ori pe secunda…destul de des =)))).De fiecare data cand acest timer intrerupe procesorul,se va apela handler-ul asociat acestei intreruperi…..(cititi Intel Architecture System Programming Guide….sau orice carte buna de sisteme de operare…nu de alta dar subiectul legat de intreruperile hardware este pretty complex)…acest handler va scadea o anumita valoare predefinita din cuanta thread-ul curent.Deci cuanta unui thread este de fapt un numar intreg…de exemplu in Windows XP cuanta unui thread este egala cu 6,iar la fiecare intrerupere generata de timer-ul sistemului,handler-ul asociat acestei intreruperi va scadea 3 din cuanta thread-ului curent.In consecinta fiecare thread va rula pentru doua ticuri de ceas…..si tinand cont de faptul ca procesorului ii ia aproximativ cateva nanosecunde ca sa execute o instructiune;deci intre cele doua ticaituri de ceas,procesorul va executa suficiente instructiuni ale thread-ului.Datorita faptului ca handler-ul intreruperii de ceas este executat de foarte multe ori intr-o secunda ….intr-o secunda se pot planifica mai multe thread-uri….in exemplul anterior cu un timer ce are o frecventa de 60HZ,adica va intrerupe procesorul de 60 de ori pe secunda,iar un thread se va executa pentru doua ticuri de ceas…deci intr-o secunda vom avea 30 de context switch-uri….impresionant nu?…:P…iar asta se intampla pe un 386…deci un procesor deja antic …in concluzie se creaza iluzia paralelismului de care vorbeam mai devreme.In concluzie scheduler-ul se va apela la fiecare doua tick-uri ale ceasului pentru a cauta alt thread eligibil de executie.Toate aceste actiuni de care am vorbit,au loc in kernel,iar asa cum am spus,un proces poate avea destul thread-uri.Daca de exemplu un thread se blocheaza in kernel datorita unui apels sitem blocant,sau intra intr-o stare de waiting,atunci scheduler-ul poate planifica alt thread,din acelasi proces,sau din alt proces.In concluzie thread-urile care sunt recunoscute de kernel sunt bine integrate in sistem.

Problemea mare a thread-urilor care sunt recunoscute de kernel este ca fiecare actiune related threads,adica crearea unui thread,distrugerea unui thread,suspendarea,yielding-ul,resuming-ul si scheduling-ul,respectiv sincronizarea thread-urilor prin mutexururi,semafoare,pipe-uri etc sunt actiuni care vor trebui facute in kernel mode.Win32API,pune la dispozitie o gramada de apeluri sistem related threads si sincronizarea intre acestea,insa fiecare apel sistem va necesita trecerea in kernel mode(din nou….cititi Intel Architecture System Programming Guide ca sa vedeti ce implica asta)..deci in aplicatiile unde exista multe thread-uri care interactioneaza foarte mult intre ele(prin primitive de sincronizare sau transmiteri/receptionari de mesaje),tranzitia din user mode in kernel mode respectiv intoarcerea din kernel mode inapoi in user mode reprezinta un overhead destul de mare.

O alta problema legata de thread-urile gestionate de kernel ete faptul ca ele trebuie sa fie cat mai generale…..adica trebuie sa fie “de toate pentru toata lumea”.De exemplu la orice context switch,se va salva si starea FPU(Floating Point Unit),alt overhead destul de mare,cu toate ca anumite thread-uri nu au nevoie de asa ceva.In consecinta thread-urile gestionate de kernele trebuie sa fie general purpose,si sa ofere destule facilitati mergand pe premiza ca cineva va folosi acele facilitati(dar nu toata lumea).

Datorita faptului ca kernel threads,manifesta performanta relativ slaba ,din cauza ca orice este legat de ele trebuie facut in kernel(necesitand cate o translatie in kernel mode la fiecare astfel de actiune)…a fost adoptat un alt model de implementare a thread-urior..si anume in user mode.Cand thread-urile sunt implementate in UserMode,acestea numai sunt cunoscute de catre kernel,deci orice operatie asupra lor(sincronizare/creare/suspendare/planificare/distrugere) vor fi facute in spatiul utilizator fara interventia kernelului.Thread-urile sunt implemnentate in user mode sub forma unei librarii(un DLL de exemplu) partajate intre mai multe procese din sistem.Atunci cand doriti sa va creati propriile thread-uri in programul dumneavoastra,si pe care sa le folositi sa faca diverse chestii,nu va trebui decat sa apelati rutinele din acel DLL sharat.De exemplu crearea unui user level thread(sau lightweight thread) ce va face prin apelul unei functii (cum era create_thread()..in cel de-al doilea programel din articolul asta) care va initializa o structura de tip thread,dupa care va introduce acest TCB intr-o lista(sau un dispatcher database asa cum este in kernelul de Windows) cu thread-uri care sunt “gata pentru executie”(sau in starea READY cum se mai zice).Apoi scheduler-ul (cel din libraria noastra,nu cel din kernel de care am tot vorbit pana acuma) va planifica acest thread(printr-un context switch).Unul dintre cele mai importante campuri din structura de tip thread sunt:un pointer la functia de start a thread-ului(pointer pe care il dam ca parametru functiei de creare a thread-ului),lista de argumente pe care o va primi functia de start a thread-ului(daca avem mai multe argumente pentru funtia de start,putem folosi un pointer la o structura care contina toate aceste argumente…asta din cauza ca functia care creaza si initializeaza un thread nu are de unde sa “stie” cate argumente vrem noi sa transmitem functiei de start,si tot ce cere ea,este un pointer,considerand ca acel pointer va fi singurul argument pe care o sa-l transmitem functiei….iar noi putem sa folosim acest pointer,ca un pointer o structura,ca sa trasmitem prin intermediul sau mai multe argument cool nu?:P).Este posibil ca functia care creaza un thread sa ceara ca parametru si un integer care sa reprezinte dimensiunea stivei thread-ului ,dacu nu…atunci se va considera o dimensiune by default…de obicei doua pagini de 4KB(depinde de libraria respectiva).O librarie ce implementeaza thread-uri in spatiul utilizator mai furnizeaza si primitive de sincronizare(semafoare/mutexuri/spinlock-uri/variabile conditie/bariere/monitoare..etc..si aici depinde de fiecare librarie in parte)..si anume funtii necesare de acquireing si releasing a acestor primitive de sincronizare.Pe langa asta,mai trebuie implementat si codul care gestioneaza wait queues(atunci cand un thread intra intr-o stare de asteptare ..datorata unui semafor spre exemplu…),precum si un algoritm de scheduling.Dupa cum puteti vedea,o asemenea librarie reprezinta de fapt un mic kernel implementat in user mode.Toate acestea vor fi folosite pentru a putea sa creati aplicatii multi thread,fara sa invocati deloc kernelul.Evident ca o aplicatie multithread care foloseste facilitatile puse la dispozitie de o asemenea librarie,va avea parte de viteze de executie mult mai bune decat aceiasi aplicatie care foloseste insa serviciile kernelului.De ce?…..este logic…deoarece aplicatia care foloseste user level threads,pentru a se bucura de multithreading,va face simple apeluri de functii din acea librarie partajata.Pe de alta parte aplicatia care va folosi serviciile kernelului, va trebui ca la fiecare aciune sa invoce kernelul printr-un apel sistem,iar un apel sistem este mult mai costisitor decat un in ciclii de procesor decat un apel de functie.Asta din cauza ca la un apel sistem sistemul de operare va invoca o instructiune speciala a procesorului(int XXX) printr-un trap gate…care va necesita un stack switch(de la stiva din user mode la cea din kernel mode),copierea argumentelor de pe UM stack in KM stack si invocarea dispatcher-ului de apeluri sistem din kernel care va trebui sa invoce o functie interna a kernelului a carui pointer este stocat intr-o tabela (KeSystemServiceTable…asa se cheama in Windows) interna..iar apoi acea rutina sa faca treaba dorita:P..deci este overhead ceva mai mare.Intr-o aplicatie care nu foloseste prea multe thread-uri putem sa folosim kernel threads…deoarece acest overhead nu este deranjant…insa intr-o aplicatie care are multe thread-uri …si unde se folosesc multe si complicate mecanisme de sincronizare este preferabil sa folosim user level threads…pentru a economisi ciclii de procesor,ce urmeaza sa fie folositi in calcule efective in loc sa fie irositi pe intrari si iesiri in/din kernel mode.

Asadar user level threads ofera performanta superioara fata de kernel level threads si mai mult de atat puteti sa folositi orice librarie disponibila pe net sau daca va suparati va puteti face singuri o librarie nou nouta,unde sa folositi ce primitive de sincronizare doriti si exact ce algoritmi de planificare doriti…deci un alt avantaj este faptul ca librariile user level threads sunt customizabile dupa preferintele fiecaruia,spre deosebire de kernel care este acelasi pentru toti .Un alt avantaj il reprezinta faptul ca puteti avea aplicatii multi thread chiar si in sisteme precum MS-DOS.

Insa implementarile thread-urilor in user mode au anumite dezavantaje aproape dezastuoase.Sa vedem exact despre ce este vorba.

Cel mai mare dezavantaj al thread-urlor implementate in user space este faptul ce ele nu sunt cunosctute de catre kernel(nu sunt integrate in sistem).In cazul proceselor UNIX,tot ce cunoaste kernelul sunt procesele(mai precis PCB-urile acestora) ,iar el(kernelul) planifica procese.Se consideram un exemplu:Avem in proces intr-un sistem de tip UNIX,in care am creat 100 de user level threads.Planificarea acestor din urma va fi facuta de noi prin apeluri catre scheduler(thread_yield()…atunci cand thread-ul curent doreste sa lase procesorul si si planifice alt thread)…si un obiect timer(o alarma)pe baza caruia apelam scheduler-ul din librarie.Aceste thread-uri se vor executa atat timp cat procesul in care ele sunt nu i-a expirat cuanta de timp.Cand cuanta a expirat..atunci kernelul va planifica alt proces.pana aici toate bune si frumoase.Insa daca de exemplu o instructiune din cadrul unui user level thread creaza un page fault/sau un apel sistem (open() srpe exemplu) blocant…atunci procesul curent va trebui sa astepte pana cand vin informatii de la dispozitivul I/O…adica pana cand pagina solicitata a fost adusa in RAM,sau fisierul a fost deschis…deci pana atunci kernelul va pune procesul respectiv intr-o coadsa cu procese ce asteapta ceva(in starea de wait)…dece va puna procesul si nu thread-ul respectiv este evident…deoarece cum am mai zis kernelul nu stie ce sunt alea user level threads…el stie doar de procese…deci va interpreta un page fault,ca a fost generat de catre proces…indiferent ce se afla in acel proces(user level threads si ale chestii de genul asta).Asa cum ziceam in acel proces aveam 100 de thread-uri,si iata cum din cauza unui thread care a creat un apel sistem blocant sau un page fault ,si restul de 99 de thread-uri care sunt gata de executie,vor astepta,practic degeaba,deoarece ele nu au nici o vina:P…si este incorect ca si ele sa astepte.

Fig5 – Exemplu de proces in care avem mai multe user level threads gestionate de libraria partajata intre procese(Runtime System).In josul pozei(in kenrel mode) observam tabela cu porcese aflate in starea ready,ce vor fi planificate de catre kernel

Concluzia este ca thread-urile implementate in user space ofera performanta superioara fata de kernel threads si mai multa flexibilitate,insa faptul ca nu sunt cunoscute de catre kernel la face sa fie mai “proaste” decat thread-urile recunoscute de kernel.

Acum ca am vazut ce sunt user level threads,ce suntkernel level threads,si ce avantaje si ce dezavantaje are fiecare din aceste doua modalitati de implementare,sa vedem daca se poate face ceva.Ce ne-am putea dori in acest moment…evident sa avem thread-uri care sa aiba performanta celor implementate in user mode,dar cu un comportament “normal” ca thread-urile din kernel,adica sa nu existe thread-uri blocate aiurea din cauza altui thread.La prima vedere asa ceva pare imposibil…da de fapt este posibil si mai mult de atat fara vreun efort supraomenesc …let’s see.Insa inainte de a trece mai departe ..adica la a explica ce sunt scheduler activations…scopul principal al acestui articol….sa vedem diverse mapari intre user level threads si kernel level threads.

Fig6 – Mapare Many:One(n:1) intre ULT si KLT.Avem mai multe User level threads care se vor executa in contextul unui singur thread recunoscut de kernel .In Windows atunci cand ce creaza un proces automat se va crea si un thread care ruleze codul acelui program.Acel program poate crea mai multe thread-uri(prin apelul CreateThread) sau poate crea mai multe FIBERS(asa se numesc user level threads in Windows 2000/2003/XP).Astfel aceste fibere se vor executa in contextul respectivului thread.Apar aceleasi probleme …daca un fiber se blocheaza in kernel din cauza unui apel sistem sincron(ReadFile de exemplu)…atunci kernelul va interpreta acest lucru in felul urmator…va pune respectivul thread sa astepte pana cand I/O Manager-ul si sistemul de fisiere si-au terminat treaba(atunci cand HDD va intrerupe CPU)…blocandu-se astfel toate fiberele din acel thread.

Fig 7 – Mapare One:One(1:1) intre ULT si KLT…exista cate un kernel thread pentru fiecare user level thread…

Fig8 – Mapare Many:Many(m:n) intre ULT si KLT….Libraria care implementeaza thread-urile in user mode ofera facilitatea de a migra un user level thread de la un kernel level thread la altul.De exemplu in cadrul unui proces avem mai multe user level threads sa zicem in numar de m. si n kernel threads,unde n<m.Astfel fiecare kernel level thread are un pool propriu de user level threads care se vor executa in co9ntextul acelui kernel level thread.Daca un user thread se va bloca in kernel ,sau va produce un page fault,atunci kernelul va pune in waiting respectivul kernel thread si va planifica un alt kernel thread,care are si el propriul pool de user threads.Pe langa aceasta libraria de user level threads mai ofera facilitatea de a face load balancing intre aceste pool-uri de user threads,astfel un user level thread poate fi migrat de la un kernel thread la alt kernel thread,si dupa aceasta el se va executa in contextul acelui kernel thread.Aceasta implementare incearca sa combine sa performanta user level threads si integrarea kernel level threads,insa nici aceasta nu ofera performanta buna datorita faptului ca anutite thread-uri care sunt gata de executie vor fi blocate de un anumit thread care a creat un page fault ,deci in consecinta kernelul va bloca kernel thread-ul in care se executau acele user threads.Aceasta modalitate de implementare se numeste implementrare hibrida si a fost implementata in sistemul de operare SOLARIS produs de firma SUN.

Vom explica acum o metoda foarte buna pentru a beneficia de performanta thread-urilor implementate in spatiul utilizator,dar in acelasi timp sa nu mai avem parte de problemele acestora legate de faptul ca nu sunt cunoscute de catre kernel.Principala abstractizare folosita este scheduler activations,care este un soi de kernel thread,dar care are cateva proprietati interesante.In aceasta noua metoda kernelul este folosit in principal pentru a raporta aplicatiilior care folosesc user level threads,diverse evenimente care ar putea afecta starea,sau ar putea bloca mai multe user level threads.Acest mecanism de notificare folosit de kerenel se numeste UPCALL,asemanator semnalelor din UNIX/LINUX sau a APC-urilor din Windows

salut o sa fie destul matrial:)

salut o sa fie destul matrial:)

Despre User Mode vs Kernel Mode si System Calls

Rolul unui sistem de operare modern este “sa se se poarte” ca un server pentru zecile de aplicatii care ruleaza “peste el”.Ce vreau sa zic cu asta?…Functiile cele mai importante ale unui sistem de operare sunt inglobate in asa numitul KERNEL..care pe langa altele are rolul de a oferi un environment pentru diverse aplicatii.Atunci cand o aplicatie ruleaza,ea are nevoie de diverse servicii,puse la dispozitie de sistemul de operare.Cum poate o aplicatie sa “ceara” un anumit serviciu de la sistemul de operare(kernel)?…prin asa numitele apeluri sistem.Voi incepe o discutie despre apelurile sistem,despre suportul hardware oferit,si despre cum foloseste windows-ul acest suport venit din hardware pentru “a-si face treaba”.

In primul rand sa vedem ce inseamna USER MODE,respectiv KERNEL MODE.

In cel mai simplu fel explicat …kernel mode inseamna modul in care se afla procesorul atunci cand executa codul din kernelul unui sistem de operare,iar user mode este modul in care se afla procesorul atunci cand executa codul unei aplicatii oarecare.Insa ce inseamna acest “mod”….cum trateaza procesorul acest mod si alte chestii de genul asta….

In Familia de procesoare Intel incepand cu procesorul 386,procesoarele pot executa cod in modul protejat,sau in modul real.Vom vorbi despre modul porotejat.Modul protejat reprezinta de fapt o suita de trick-uri ca sa zic asa introduse in arhitectura intel,in scopul de a oferi protectie intre mai multe aplicatii ce se executa simultan pe acelasi calculator.Practic “protected mode” a fost introdus in arhitectura x86 de dragul multitasking-ului.Aceasta inseamna o serie de mecanisme de protectie a memoriei intre aplicatii,precum si protectie in segmentele de memorie ale aceleiasi aplicatii,respectiv suport pentru memorie virtuala prin segmentare si paginare:-)

In modul protejat exista 3 feluri de protectie itre segmentele din memorie:type checking,limit checking si privilege checking.

Pana sa ajungem la astea sa vedem care este faza cu segmentele de memorie.Segmentarea ca mod de gestiune a memoriei a fost introdus de catre Intel la procesorul (nu mai stiu exact care)…cred ca 8086:P.Un segment de meorie reprezinta un spatiu de adresare independent,prectic reprezinta o “bucata” de memorie in care putem stoca anumite informati.Aceste informatii poti fi accesate printr-un selector de segment incarcat intr-un registru segement al procesorului.Acest selector de segment reprezinta adresa de baza,sau adresa primului octet din cadrul segmentului.O aplicatie poate avea mai multe segmente,fiecare segment putand contine diverse informatii.De exmplu pot exista segmente de cod,care contin instructiunile programului,segmente de date,care contin structurile de date,variabile si constantele programului,respectiv stiva programului folosita pentru apelutri de proceduri.In general o aplciatie poate avea unul sau mai multe segmente de cod,unul sau mai multe segmente de date,si cel putin o stiva.Compilatorul este cel care se ocupa de crearea segmentelor.De exmplu fiecare modul dintr-o aplicatie poate fi reprezentat in memorie pentr-un segment de cod,iar fiecare modul care contine definitii de stucturi de date globale poate fi reprezentat printr-un segment de date.

O aplicatie,in modul protejat pe langa toate acestea mai are un segment special nimit LDT(Local Descriptor Table),care contine cate un descriptor de segment pentru fiecare segment al aplicatiei.

In modul real,pentru a accesa o anumita locatie de memorie,ne trebuie doua “componente”:un selector de segment si un offset in cadrul acelui segment.Selectorul de segment ne indica segmentul din memorie,unde se afla locatia pe care noi dorim sa o accesam,iar offset-ul(deplasamentul) in cadrul segmentului,reprezinta adresa in cadrul segmentului unde se afla locatia de memorie pe care dorim sa o accesam.De exemplu 10:23,inseamna locatia de memorie de la adresa 23(al-23-lea octet) din segmentul 10.In modul real aceste doua componente sunt adunate pentru a forma adresa fizica a locatiei dorite.In modul protejat,selectorul de segment,care este incarcat intr-un registru segment nu indica adresa fizica a primului octet din cadrul segmentului,ci reprezinta un offset in cadrul tabelei LDT,catre descriptorul de segment asociat segmentului dorit.Si aici (in modul protejat) exista un offset in cadrul acelui segment,care va fi adunat la adresa de baza a segmentului,ce va fi gasita in descriptorul de segment.Acest mecanism este folosit pentru a oferi protectie intre aplicatii,adica mai multe aplicatii ce exista simultan in memorie poti fi mapate in acelasi spatiu de adrese.In modul real din cadrul unui program putem accesa orice segment,indiferent daca acel segment apartine sa nu programului nostru,pe cand in modul protejat fiecare program nu poate accesa decat segmentele proprii,prin intermediul LDT.Fiercare program are un LDT,cu un anumit numar de descriptori(in functie de aplicatie—cat de “mare” este)iar orice segment de memorie va fi accesat prin LDT-ul curent(cel al aplicatiei)

Dupa cum vedeti in aceasta imagine,un descriptor are mai multe campuri.De exemplu campul Base Address care reprezinta un camp pe 32 de biti ce contine adresa de baza a segmentului.Mai avem campul Limit(pe 24 de biti) care reprezinta adresa ultimului octet din cadrul segmentului,precum si campuri referitoare la protectia segmentului.Bitul P daca este setat inseamna ca segmentul este in memorie la momentul accesului;daca este resetat,atunci segmentul nu este prezent in memorie,iar orice acces la el va rezulta o exceptie #NP(Not Present).Acest camp este folositor in sisteme care implementeaza memoria virtuala folosind segmente in loc de pagini de 4KB

Campul DPL(Descriptor Privilege Level) reprezinta nivelul privilegiul la care trebuie sa fim pentru a putea accesa acest segment.

Campul Type este pe 4 biti si reprezinta tipul segmentului…de cod de date,precum si ce actiuni avem voie sa facem in cadrul acestui segment.De exemplu ..exista segmente de date care sunt Read-Only,sau segmente de date care pot fi Read-Write.

Bitul S(System) daca este setat inseamna ca este vorba despre un segment al unei aplicatii(de date sau de cod sau stiva….stivele sunt tratate tot ca segmente de date de tip Read-Write…logic:P),iar daca estev reset inseamna ca este vorba de un segment sistem sau de o “poarta” (segment LDT,segment TSS,CALL GATE,TRAP GATE,TASK GATE sau INTERRUPT GATE)

salut…o sa fie destul material:)

Despre Performanta Spinlock-urilor

Un SpinLock este relativ usor de implementat,deoarece cam fiecare procesor are instructiuni speciale pentru citirea si
setarea valorii unui spinlock folosind doar o singura instructiune atomica.De exemplu,avand un spinlock s, intr-un sistem multiprocesor,
si mai multe thread-uri,fiecare executande-se pe cate un procesor,care incearca sa intre in sectiunea lor critica.Fiecare thread
va apela o functie speciala (AcquireSpinLock()) pentru a incerca sa intre in sectiunea critica.aceasta functie va face urmatoarele
:va citi intr-o variabila temporara valoarea spinlock-ului s,si va scrie in s o noua valoare,aceste doua operatii avand loc
in cadrul unei singure instructiuni.De exemplu daca s = 0 atunci spinlock-ul este liber si nici un thread nu este in scetiunea
sa critica,iar s = 1 inseamna ca spinlock-ul este ocupat,adica un thread se afla in sectiunea sa critica.
Dupa executarea acestei instructiuni atomice,vom compara valarea initiala a spinlock-ului cu 1.Daca s era 0 atunci
thread-ul poate intra linistit in sectiunea sa critica,insa daca s era 1 atunci mai incerca odata.Mai pe romaneste,
ceea ce face ruitna AcquireSpinlock(),este sa testeze si sa seteze valoarea lui s,intr-un ciclu atat timp cat s este
“ocupat”( = 1).Cand s este pus pe 0,primul thread care va executa AcquireSpinlock(),va intra in sectiunea critica.

Operatia care citeste valoarea lui intr-o variabila temporara si apoi seteaza valoarea lui s la o alta valoare
poarta numele de “test and set”.O asemenea operatie,pe majoritatea platformelor este furnizata sub forma unei intructiuni,
ca de exemplu instructiunile XCHG(eXCHanGe – interschimb) sau BTS
(Bit Test and Set),din setul de instructiuni a procesoarelor din familia x86.

Un test and set ar putea arata cam asa in pseudocod:

	int TestAndSet(SpinLock* s){
		int temp;
		temp = *s;
		*s = 1;
		return (temp);
	}

…iar o functie de acquireing a unui spinlock care va cicla atat timp cat spinlock-ul este liber,la fiecare pas
testand si setand valoarea sa,arata cam asa:

	void AcquireSpinlock(SpinLock *s){
		while(TestAndSet(s))	;
	}
	

Cam asta e toata logica din spatele unui spinlock,insa exista niste probleme.In primul rand asa cum am spus,TestAndSet,trebuie sa fie o operatie
atomica,o operatie care sa se execute ca un tot unitar.In cazul nostru,ea este o functie,care are doua intructiuni in corpul
(in afara de instructiunea de return).Tinand cont de faptul ca un spinlock trebuie sa functioneze pe un sitem cu mai mult de un procesor,
evident exista riscul ca doua thread-uri ,fiecare executandu-se pe cate un CPU,sa incerce se apeleze rutina AcquireSpinLock.Acest
lucru este posibil,iar cele doua thread-uri,vor testa si seta simultan valoarea lui s,amandoua gasind-ul “liber”,deci
ambele thread-uri vor intra in acelasi timp in sectiunea lor critica,deci avem race condition.In aceasta situatie,
cele doua thread-uri pot modifica simultan,fara nici un fel de constrangere,respectiva resursa critica(de exemplu o variabila partajata)
putand avea parte de un rezultat eronat.Not Good .

Deci….in concluzie un spinlock,desi e simplu de implementat,nu putem sa-l implementam intr-un limbaj ca C/C++.
Pentru asta vom apela la limbajul de asamblare,deoarece asa cum am spus in setul de instructiuni avem cateva instructiuni care
sa testeze si sa seteze valoarea unei variabile.

O posibila implementare in Assembler a functiei AcquireSpinlock().

	AcquireSpinlock proc

		_Acquire:

			mov ax,1
			lock xchg spinlock,ax
			cmp ax,1
			je _Acquire
			ret

	AcquireSpinlock endp
	

Sa vedem ce face aceasta functie.Mai intai va scrie in registrului ax,valoarea 1.
Urmatoarea instructiune este echivalentul lui TestAndSet(Spinlock* s) in limbaj de asamblare.Aceasta instructiune va
interschimba valoarea lui ax,adica 1 cu valoarea spinlock-ului.Aceasta interschimbare se va realiza intr-un singur ciclu de ceas,
nefiind necesare doua sau 3 instructiuni pentru a realiza interschimbarea celor doua locatii(registru – memorie).
In fata acestei instructiuni se afla eticheta lock.Acest lucru ne spune ca in cazul in care mai multe
thread-uri ce ruleaza pe procesoare diferite vor incerca sa apeleze aceasta functie,doar unuia i se va acorda acces sa execute
aceasta instructiune.Acest prefix blocheaza magistrala sistemului pe parcursul executiei sale.Sa presupunem ca avem
3 thread-uri T1,T2 si T3 fiecare ruland pe cate un procesor,T1 ruleaza pe procesorul P1,T2 pe P2,iar T3 pe P3.Si sa
presupunem ca toate cele 3 thread-uri “doresc” sa intre in sectiunea lor critica.
Sa zicem ca resursa critica este o variabila int i,iar sectiunea critica a fiecarui thread
presupune incrementarea variabilei i (i++).Astfel fiecare thread va face urmatoarele actiuni:

	 AcquireSpinlock(s);
	 i++;      			//Sectiune critica
	 ReleaseSpinlock(s);
	 

In sistemul nostru cu 3 procesoare,sa presupunem ca fiecare din cele 3 thread-uri “ajung” simultan la apelul AcquireSpinlock(s).
Fara prefixul lock in fata instructiunii xchg,acel cod in limbaj de asamblare ar fi fost echivalent cu
versiunea scrisa in C,deoarece fiecare din cele 3 thread-uri va executa simultan aceste instructiuni,inclusiv instructiunea xchg,
,deci in concluzie toate cele 3 thread-uri vor intra in sectiunea critica.Insa in cazul de fata instructiunea xchg este precedata
de prefixul lock,iar cand cele 3 thread-uri vor ajunge simultan “in fata” acestei instructiuni,vom avea
certitudinea ca doar unul dintre ele o va executa la un moment dat.Primul thread care va executa lock xchg …
va bloca in acelasi timp si magistrala sistemului,iar celelalte thread-uri vor trebui sa astepte pana cand primul thread va termina de executat
instructiunea xchg.Astfel primul thread care va executa aceasta instructiune va fi si cel care va intra in sectiunea critica,iar
apoi restul de thread-uri vor executa in mod serial instructiunea lock xchg,dupa care vor compara valoarea lui spinlock cu 1.In caz de egalitate,
vor repeta procesul.
Astfel celelalte thread-uri care nu au intrat in sectiunea critica vor cicla de atatea ori pana cand thread-ul care a intrat in sectiunea
critica va elibera spinlock-ul.Cand aceasta se va intampla,aceste thread-uri “vor intra in lupta”,iar primul care va executa testand set-ul
va fi intra in sectiunea critica,si tot asa pana cand toate thread-urile si-au executat codul din cadrul sectiunii critice.

Functia care elibereaza un spinlock este si mai simpla.Ea arata cam asa:

	ReleaseSpinlock proc
		mov spinlock,0
		ret
	ReleaseSpinlock endp
	

Si gata.Asa lucreaza un spinlock.Nimic mai mult.

Desi aceasta solutie este buna,in sensul ca ne garanteaza faptul ca doar un singur thread la un moment dat se va
afla in sectiunea sa critica,evitand astfel problemele cauzate de race conditions,este si cea mai slaba(lipsita de
performanta).De ce?…..pai sa vedem asta printr-un exemplu:

Sa presupunem ca avem un sistem cu 10 procesoare,si la un moment dat avem 10 thread-uri care doresc sa intre in
sectinea lor critica relativa la o anumita resursa(sa zicem o variabila intreaga i).Fiecare thread va rula pe cate un CPU distinct.
Pentru a-si exprima dorinta de a intra in sectiunea critica,fiecare thread va face un apel la functia AcquireSpinlock,pentru
a incerca sa “castige” spinlock-ul asociat resursei i.Evident ca doar unul dintre ele va reusi acest lucru,si anume
primul thread care a “vazut” spinlock-ul liber,il va seta pe 1 si va continua.Celelalte thread-uri is vor incerca si ele norocul,
insa vor “observa” ca spinlock-ul este ocupat,si deci vor incerca din nou.Astfel avem 9 thread-uri care vor incerca sa “castige”
respectivul spinlock,fiind in busy waiting(desi se zice ca ele asteapta,in realitate dupa cum ati si vazut un thread care”asteapta” un la spinlock
cicleaza pana cand acel spinlock devine liber.Cu toate ca face ceva ,adica nu se va alfa intr-o coada de asteptare,
nu va face nimik util,de aceea se mai spune si busy waiting).Asa cum am spus mai devreme,fiecare thread va incerca sa castige spinlock-ul,
iar in incercarea sa va executa si instructiunea xchg cu prefixul lock in fata,deci va bloca magistrala pe parcursul executarii ei.Insa asta nu e
foarte rau deoarece respectiva instuctiune in realitate se executa destul de repede.Insa in cazul de fata avem 9 thread-uri care vor face
asa ceva ,si nu vor face asta doar odata ci de atatea ori pana cand spinlock-ul va fi eliberat.Daca presupunem ca thread-ul 2 va executa de 100 de ori
acel ciclu while,iar thread-ul 3 de 80 de ori,la fiecare executie magistrala sistemului va fi blocata pt o scurta perioada de timp,incetinind astfel si
procesoarele care nu sunt in busy waiting si care “fac” lucruri utile.Si mai mult de atat,am considerat dor doua thread-uri care se afla in
busy waiting,insa in exemplul nostru avem 9:-(.Not Good.Aceasta situatia in care thread-urile care sunt busy waiting incetinesc sau impiedica
celelalte procesoare care fac lucruri utile se numeste HOT SPOT.Situatia e destul de neplacuta,cele 9 thread-uri vor executa in mod serial
instructiunea xchg pt a castiga magistrala ca sa nu interfereze cu alte thread-uri ce s-ar putea sa execute aceiasi instructiune in acelasi timp:-),si
asa cum am mai zis fiecare din cele 9 thread-uri vor executa instructiunea de mai multe ori,asta depinzand de cat de mult timp va sta in sectiunea critica,
thread-ul care a castigat spinlock-ul.Ganditi-va ca acel thread care se afla in sectiunea critica doreste sa scrie niste rezultate
in memorie,deci pentru asta are nevoie de acces la magistrala sistemului;insa s-ar putea sa nu poate sa scrie rezultate in acel timp,
deoarece “cineva” este in cursul executarii unei intructiuni xchg,iar dupa aia poate alt thread aflat in busy waiting,va executa xchg si asa mai departe.
Deci thread-ul care a castigat lock-ul s-ar putea sa astepte destul de mult pana sa scrie un rezultat in memorie.

Exista anumite implementari alternative,care pot elimina aceasta situatie de hot spot,lasand astfel celelalte procesoare sa isi faca treaba
fara sa mai astepte 100 de ani sa scrie un rezultat in memorie atunci cand au nevoie.O alternativa ar fi ca atunci cand un thread
doreste sa intre in sectiunea lui critica,sa execute un xchg,pentru a seta spinlock-ul la valoarea 1,iar apoi in caz de valoarea veche
a spinlock-ul era 0….ne-am scos ….intram in sectiunea critica…in caz ca altcineva inaintea noastra a ocupat spinlock-ul,deci valoarea sa veche este 1,
vom testa intr-un ciclu valoarea spinlock-ul(CACHE SPINING sau SPIN-ON-READ).Ce inseamna asta…ca in loc sa executam instructiunea xchg de atatea ori pana spinlock-ul se elibereaza,
fiindca instructiunea xchg implica si o scriere si o citire,si vom bloca magistrala de atatea ori,o vom executa odata ,iar in caz de esec,vom
testa valoarea variabilei spinlock.O posibila implementare ar arata cam asa:

	void AcquireSpinLock(SpinLock *L){
		while (TestAndSet(L))
			while (*L == 1) ;
	}
			

Care este diferenta dintre prima implementare si aceasta?….fiindca la prima vedere pare ca aceasta implementare
ar aduce un plus de complexitate,deoarece am mai adaugat un ciclu while?….ei bine nu e chiar asa….iar aceasta solutie
pe langa ca faptul ca nu aduce un plus de complexitate fata de prima implementare,ba mai mult e si mai eficienta:P
Pentru a putea intelege exact de ce …voi incerca sa explic cateva chestii legate de memoriile cache al procesoarelor,iar apoi vom reveni la
acest exemplu,ca sa vedem de ce el este mai bun decat primul.

memoriile cache

In general un procesor are urmatoarea misiune:sa ia instructiuni din memoria calculatorului si sa le execute,dupa care
posibil sa scrie niste informatii in registri sau din nou in memorie.Cam asta e ..asa in mare tot ce trebe sa faca un procesor.
Faza in care un procesor “ia” o instructiune din memoria RAM,se numeste FECTCHING,dupa care acea instructiune va fi depusa intr-un buffer
intern al procesorului.Urmeaza apoi faza de DECODING(decodificare),in care procesorul “incearca sa vada” ce fel de instructiune este ea,
si sa “vada” daca acea instructiune este una simpla ,sau are nevoie de un operand din memorie,sau de vreu registru.Dupa ce procesorul se “prinde”
ce vrea sa faca acasta instructiune,incepe efectiv executarea ei de catre unitatea de executie,dupa care posibil sa se scrie un nou rezultat
undeva in memorie sau intr-un registru.Dupa cum vedeti executarea oricarei instructiuni de catre un procesor implica mai multe faze(aici este vorba de FETCHING-DECODING-EXECUTION-WRITE),
insa in fucntie de procesor pot exista mai multe faze.Toate fazele in afara de prima se vor executa de obicei foarte repede.Prima faza
va lua ceva timp deoarece va trebui sa “dialogheze” cu memoria,iar cum memoria RAM lucreaza la o frecventa mult mai mica
decat cea a procesorului,vor interveni niste stari de asteptatre.Adica procesorul va trimite un request catre controller-ul memoriei ram,
comunicand-ui ca ar dori o anumita adresa sau o valoare stocata la o anumita adresa.Apoi procesorul va astepta pana cand acest request va fi satisfacut de
catre memorie,evident la o viteza mai scazuta.

Pentru a minimiza numarul starilor de asteptare,proiectantii au introdus asa numitele memorii cache,care pastreaza in ele
rezultatele cele mai des folosite.De ce?….Deoarece este destul de probabil ca un anumit element din memorie care a fost
folosit de procesor sa fie folosit si in viitorul foarte apropiat.Acest lucru se numeste localizare temporala a referintei.Tot in memoria cache,mai sunt pastrate si locatiile din memorie,adiacente cu
elementul care a fost folosit de catre procesor,si pentru care exista o probabilitate mare,sa fie folosite si ele in viitor.
Se presupune ca daca un element de la o anumita locatie de memorie a fost folosit recent de carte procesor,si elementele aflate
in locatii de memorie succesive cu acesta sa urmeze sa fie folosite de procesor.Acest lucru se numeste localizare spatiala a referintei.Poate ca pare …io stiu….complicat la prima vedere…
insa nu este asa.Iar pentru asata voi da un exemplu pentru a intelege si mai bine:).Ma rog…Faza de fetching a procesorului lucreaza cam asa:Mai
intai se “uita” in memoria cache pentru elementul solicitat,iar daca il gaseste …totul e ok…am putut obtine acea valoare fara sa
asteptam la memoria RAM(evident mult mai mare si mai lenta).Acest lucru se numeste CACHE HIT.In cazul in care un anumit element nu a fost gasit in memoria cache,
il “vom cauta” in memoria RAM,insa va trebui sa asteptam ceva mai mult,asa cum am zis mai devreme.Cand un anumit element solicitat de procesor nu este gasit in cache,vom spune ca am avut parte de un CACHE MISS,si
drept urmare va trebui sa il cautam in RAM.Sa luam un exemplu.Fie:

	for(i = 0 ; i <= 20 ; i++){
		v[i] = i*i;
	}
	

Un exemplu simplu….fiecare element al vectorului v va lua valoarea i la patrat,unde i este pozitia pe care se afla el.
Acest exemplu foloseste din plin ceea ce se numeste locazizare temporala si spatiala a referentei.Este vorba de un ciclu for.Variabila contor este i.
Mai mult de atat,i va fi accesata la fiecare ciclu din cele 20 de cicluri cate se vor executa,deci avem localizare temporala a referintei.Pentru asta,
variabila i va fi pastrata in memoria cache,astfel incat,atunci cand la un ciclu urmator,procesorul sa nu mai astepte sa o aduca din memorie,
ci o va lua direct din meoria cache,deoarece memoria cache lucreaza la frecventa procesorului,nemaifiind nevoie de stari de asteptate suplimentare.
Mai mult de atat,observam ce elementele vectorului v sunt accesate unul dupa altul,deci avem localizare spatiala a referintei.
Si este natural,ca atunci procesorul,doreste sa obtina adresa lui v[0] pentru a scrie in ea,sa aduca din memoria RAM in memoria cache si urmatoarele locatii de memorie,
pentru ca la urmatoarele accese,procesorul sa nu mai astepte la memoria RAM,fiindca ar fi un timp consumat degeaba:P,ci sa le ia direct din cache la o viteza mult mai mare.

Evident un element ce a fost gasit in cache(cache hit),si care urmeza a fi scris(ca de exemplu v[i] = i*i),va fi scris in cache,iar apoi in memoria RAM,pentru
ca elementele din RAM sa fie intr-o stare consistenta.

Acum ca tot am vb atat de mult despre memoria cache,sa ne intoarcem la exemplul cu spinlock-ul nostru:P

Sa ne mai uitam odata la cele doua implementari:

	void AcquireSpinlock(SpinLock *s){
		while(TestAndSet(s))	;
	}

	void AcquireSpinLock(SpinLock *L){
		 while (TestAndSet(L))
			while (*L == 1) ;
	}

OK….In prima implementare,se va apela functia TestAndSet(),caruia i se va transmite un pointer catre spinlock-ul nostru.Aceasta functie(TestAndSet),asa cum am mai
spus de o mie de ori va face asa:

	int TestAndSet(SpinLock *s){
		int temp = 1;
		__asm{
			mov ax,temp
			mov bp,s
			 lock xchg ax,ds:[bp]
		}
	return (temp);
	}
	

NOTA:
Cam asta face rutina TestAndSet,aici fiind implementata in Visual C++.Am preferat aceasta implementare deoarece este in C iar partea care trebuie neaparat codata in assembler este inserata direct in codul de C,
si nu in Assembler pur asa cum am facut prima oara.Am folosit acea notatie cam urata cu ds:[bp].Ideea e ca noi transmitem functiei un pointer la
spinlock,si nu valoarea lui,deoarece trebuie sa modificam valoarea spinlock-ului,deci folosim apelul prin referinta,asa cum este el in C,folosind pointeri.
In partea de assembler,prin instructiunea mov bp,s registrul bp va contine valoarea lui s(s este pointer la spinlock),adica
adresa de memorie a spinlock-ului.pentru a ne referi la valoarea continuta la o anumita locatie de memorie in mod indirect(adica fara sa stim exact la ce adresa este),in aseembler folosim ceea ce se
numeste adresarea bazata.Ma rog…exista o discutie lunga vis-a-vis de adresarea memoriei in assembler….recomand The Art ofAssembly…e pe departe cea mai buna

Deci acum ca am vazut cum arata TestAndSet scrisa in Visual C++,sa revenim……Deci cum spuneam,in prima implementare,
functia TestAndSet va intoarce in variabila temp valoarea spinlock-ului inainte ca ea sa fi fost setata(valoarea veche).Daca aceasta fost 0,evident conform regulilor din C,
ciclul while nu se mai executa si se va trece mai departe,adica se va intra in sectiunea critica,insa…daca valoarea veche este 1 atunci ciclul se va executa inca odata(tot conform regulilor din C…tot ce este 0 este fals…daca conditia unui if este egala cu 0,atunci corpul if-ului nu se va executa,la fel si pt while sau do…insa daca este 1,se va executa inca odata)
Deci daca valoarea veche a spinlock-ului este 1 ciclul while se va executa pana cand ea va fi pusa pe 0.La fiecare executie,asa cum am mai spus,functia TestAndSet,va executa lock xchg…,care va bloca magistrala creand ceea ce se numeste HOT SPOT.
In cea de-a doua implementare,functia TestAndSet() se va executa doar odata,iar daca valoarea intoarsa este 0 vom intra in sectiunea critica…daca nu…inseamna ca valoarea intoarsa de rutina TestAndSet este 1,deci vom intra in corpul cicluului while
si vom executa ce se afla acolo…adica un alt ciclu while care va testa valoarea spinlock-ului,pointat de catre pointerul L.Ideea din spatelei acestei chestii este ca..acum vom cicla in jurul variabilei pointer pe care procesorul o va gasi in memoria cache,
si pe care o va gasi imediat…si fara sa mai execute lock xchg de fiecare data,blocand astfel magistrala,care ar putea fi folosita de alte procesoare care “fac” lucruri utile:)…eh deja parca ne-am mai linsitit
In exemplu nostru …cel cu 10 procesoare,cele 9 procesoare care vor dori sa intre in sectiunea lor critica,se vor afla in busy waiting,dar de data aceasta vor cicla testand doar valoarea din memorie a spinlock-ul(pe care o vor lua din cache-urile proprii),fara sa mai creeze situatia neplacuta de hot spot.
Procesoarele care fac lucruri utile si care vor dori sa scrie diverse rezultate in RAM cand se afla in sectiunea critica,o vor putea face fara sa existe asteptari prea mari,datorate executarii lui xchg de catre cele 9 procesoare asa cum se intampla in prima implementare:-)

NOTA:Aceasta modalitatate de a testa un spinlock se numeste cache spining,deoarece procesoarele aflate in busy waiting vor lua valoare din memoria cache a variabilei spinlock si o vor testa.Avem localizare temporala a referintei…va mai aduceti aminte?:P

O alta implementare ar mai putea arata asa:

	if(TestAndSet(s)){

		while(*s == 1)
			//nu faem nimik
			;
	}else{
		//totul este ok...adica valoare veche a spinlock-ului intoarsa de rutina TestAndSet 
		//este 0,deci am setat *s pe 1 si mergem mai departe(in sectiunea critica)

		break;
	}

	}
	

Acum o intrebare va vine in minte.Ok…metoda este mai buna decat prima.Dar ce se intampla atunci cand un thread care se afla in sectiunea critica,
elibereaza spinlock-ul?…hmmmm….in sitemele multiprocesor exista ceea ce se numeste coerenta memoriilor cache.
Ce inseamna asta?Asta inseamna ca atunci cand un procesor va modifica o valoare din memorie care se afla in cache-ul altui
procesor,atunci si acea intrare din cache-ul procesorului,fie se va modifica la noua valoare scrisa de celalalt procesor,fie intrarea respectiva va fi invalidata.
Pentru a realiza aceasta,procesorul care va modifica valoarea respectiva din memorie,va trimite un IPI(Inter Processor Interrupt),procesoarelor care detin in memoria lor cache o copie a valorii tocmai modificate,
pentru a le instiinta de faptul ca acea valoare a fost modificata.Atunci cand o procesorul care a primita cel IPI isi va invalida linia din cache care contine
acea variabila recent modificata de un alta procesor din sistem,spunem ca avem un sistem cu coerenta a cache-urilor bazata pe invalidare.In cazul in care procesorul ce a
primit acel IPI,isi va modifica copia variabilei din cache-ul sau la noua valoare scrisa de celalalt procesor,spunem ca avem coerenta a cache-urilor prin scriere distribuita.
Evident ca sistemele cu coerenta a memoriilor cache prin scriere distribuita este mai bun deoarece la urmatoarea accesare a acelei copii din cache nu se va produce un cache miss,ci din contra,aceasta accelerand procesul de regasire a unei variabile direct
in cache-ul procesorului.In cazul in care avem un sistem multiprocesor cu coerenta a cache-urilor prin invalidare de linii,atunci la
urmatoarea accesare a acelei variabile,procesorul o va cauta in cache insa linia pe care se afla este invalidata,producandu-se astfel un cache miss,iar porcesorul respectiv va trebui sa o caute in memoria principala.

Sa presupunem ca avem un sistem multiprocesor cu coerenta a memoriilor cache prin invalidare de linii.Si sa mai presupunem ca un procesor se afla in sectiunea sa critica,iar celelalte procesoare sunt in asteptare ocupata(busy waiting).
La un moment dat thread-ul care se afla in sectiunea critica,si-a facut “treaba”,si va “dori” sa iasa facand un apel la rutina
ReleaseSpinLock(s),care,cum am mai zis,nu face altceva decat ii atribuie lui *s valoarea 0(spinlock-ul este acum liber,si poate fi castigat de alte thread-uri ce ruleaza pe alte procesoare din sistem).
Cand ReleaseSpinLock() a scris valoarea 0 la adresa de memorie unde se afla spinlock-ul,automat(este garantat prin hardware acest mecanism),procesorul respectiv(cel pe care se executa ReleaseSpinLock),va trimite in o instiintare(o intrerupere interprocesor) celorlalte
procesoare din sistem care au cate o copie a valorii spinlock-ului in memoriile lor cache,rezultand invalidarea acelor linii din cache-urile fiecaruia.
Evident ca la urmatoarea accesare,a valorii spinlock-ului procesoarele vor cauta aceasta valoare in cache si va rezulta un cache miss,urmand ca ele sa caute acea valoare in memoria RAM.Si aici este o mica problema…tot legata de performanta…dar nu foarte costisitoare,deoarece
,cache miss-urile se realizeaza fooooarte repede(chiar si starile de asteptare)…undeva in jurul a cateva nanosecunde…deci extrem de repede…dar oricum e bine de stiut si asta:

Un thread a eliberat spinlock-ul,provocand astfel o invalidare a liniilor din cache-urile procesoarelor ce detin o copie a
valorii acestuia.Fiecare procesor va produce un cache miss cautand valoarea in RAM…primul care a gasit spinlock-ul in RAM il va seta la valoarea 1(conform algoritmului de castigare a unui spin lock,prin ce-a de a doua metoda),
si va intra linistit in sectiunea sa critica.Intre timp alte procesoare mai lenese vor produce un cache miss,urmand si ele sa caute valoarea spinlock-ului in RAM,o vor seta si ele tot pe 1,iar apoi vor testa valoarea veche a spinlock-ului pastratat in variabila temp.Care,evident este tot 1,si in concluzie isi vor rezuma busy waiting-ul.
Problema este ca fiecare procesor care va executa TestAndSet(),va suprascrie valoarea spinlock-ului,generand iar un sir de IPI-iuricare vor invalida copiile din cache-urile procesoarelor ce contrin pe o linie o valoare a lui spinlock.
Astfel se va genera o serie de invalidari pentru o anumita perioada de timp,iar procesoarele vor produce o serie de cache miss-uri.
De exemplu primul thread care a setat valoare spinlock-ului pe 1 si a testat valoarea veche,a vazut ca este 0 deci a intrtat in sectiunea critica.
Al doilea procesor va face acelasi lucru,insa va valoarea veche acuma este 1,deci va ramane in continuare in busy waiting.Al treilea procesor evident va face acelasi lucru,va vedea valoarea veche a lui spinlock ca este 1 deci isi va rezuma busy waiting-ul,insa el a setat spinlock-ul la valoarea 1,provocand astfel o invalidare a liniilor din cache-url celorlalte procesoare,implicit si al procesorului care a testa si
a setat spinlock-ul inaitea sa,ir acesta din urma iar va prioduce un cache miss.Al patrulea procesor va face acelasi lucru(va seta spinlock-ul la 1 si va testa vechea valoare),provocand iar o serie de invalidari de linii din cache.Iar acum cele doua procesoare care au testat si au setat spinlock-ul inaintea sa,vor produce din nou cache miss….si tot asa…
Insa perioada asta de “agitatie” in care procesoarele produc cache miss dupa cache miss va trece foarte repede si oricum va fi invizibila aplicatiei,deoarece se vor realiza intr-un timp foarte rapid.

Alte alternative pentru implementarea spinlock-urilor.(InQueued SpinLock & SpinLock Acquireing with delay)

O alta alternativa pentru implementarea spinlock-urilor este ceea ce se numeste Queueing SpinLock.Ce inseamna asta?
Inseamna ca,daca avem un numar oarecere de procesoare P,care doresc sa intre in sectiunea lor critica,acestea in loc sa cicleze testand valoarea spinlock-ului,vor fi asezate intr-o coada,fiecaruia
dandui-se un flag in jurul caruia sa se “invarta”:).Cand unul din procesoare a ieshit din sectiunea sa critica,ii va da dreptul urmatorului procesor din coada sa intre in sectiunea sa critica.O posibila implementare in
pseudocod a acestui algoritm ar arata cam asa:

	//Constante
	#define OWNER 0
	#define BUSY 1

	typedef struct _KSPIN_LOCK_INQUEUED{

		intultim;
		//Vectorul flags va retine cate o pozitie pentru fiecare procesor
		//doritor de a intra in sectiunea critica.
		//P este numarul total de procesoare din sistem.
		int flags[P];   

	}KSPIN_LOCK_INQUEUED,*PKSPIN_LOCK_INQUEUED;

	KSPIN_LOCK_INQUEUED lock;   //lock este spinlock-ul nostru:-)
	PKSPIN_LOCK_INQUEUED SpinLock = &lock;	 //SpinLock este pointer la spinlock-ul nostru:-)
	SpinLock->ultim = 0;
	SpinLock->flags[0] = OWNER;  

	void AcquireQueuedSpinLock(PKSPIN_LOCK_INQUEUED SpinLock){
		int spin;
		spin = ReadAndIncrement(SpinLock->ultim);
//ReadAndIncrement este o rutina care va implementa
//instructiunea atomica read and increment,care pe
//anumite platforme s-ar putea sa nu fie disponbibila...
//Pe Intel ea se se poate implementa folosind
//instructiunea XADD(eXchange and ADD).

		while(SpinLock->flags[spin] == BUSY) ;
			//Nu facem nimik....just spining:P

	}

	void ReleasequeuedSpinLock(){
		SpinLock->flags[spin] = BUSY;
		SpinLock->flags[spin + 1] = OWNER;
	}

Sa vedem ce facem aici….In prumul rand aici spinlock-ul este implementat sub forma unei structuri care contine o variabila intreaga
numita “ultim”,care la prima vedere are un rol de ciudat,si un array cu un anumit numar de elemente care poate parea si mai ciudat:P.
Sa vedem exact despre ce este vorba.Observati in partea de initializare a spinlock-ului ca ultim ia valoarea 0 iar flags[0] = OWNER.
Avem acele doua #define-uri acolo,OWNER = 0 iar BUSY = 1.Astfel primul element din vectorul flags a fost initializat cu valoarea OWNER(0),iar restul elementelor au fost initializate cu valoarea BUSY(1).
Variabila ultim va fi incermentata la fiecare incercare de acquireing a spinlock-ului.Daca ne uitam in corpul functiei AcquireSpinLock observam,
ca avem o variabila locala spin in care vom depune valoarea lui ultim.Rutina ReadAndIncrement,mai intai va intoarce valoarea veche a lui ultim iar apoi o va incremneta.
La primul apel spin va avea valoarea 0,iar ultim va fi incrementata la valoarea 1.Asa cum stim,…la initializarea spinlock-ului,flags[0] = OWNER,deci acum vom testa valoarea asociata din array-ul flags(valoarea asociata fiind spin)
…deci flags[spin] = 0…intram in sectiunea critica.Celelalte thread-uri vor incerca sa fac acelasi lucru.De exemplu,
al-doilea thread va obtine in variabila sa locala spin valaorea lui ultim care acuma este 1 si o va incrementa(pe ultim) la valoarea 2.
Apoi va executa ciclul while si va “vedea” ca flags[1] = BUSY,si atat timp cat este busy va executa acest ciclu,pana cand va deveni liber.
Deci in concluzie fiecare thread va testa intr-un ciclu while,o anumita valoare.

Rutina care elibereaza un spinlock este chioar simpla.Va pune pe flag-ul personal valoarea busy,si apoi va acorda
controlul urmatorului procesor.

Aceasta implementare este foarte buna din punctul de vedere al performantei,deoarece procesoarele care nu au reusit sa intre in sectiunea
lor critica vor testa valoarea unui flag privat,fara sa interogheze valoarea spinlock-lui.Acest lucru este bun deoarece,fata de prima
implementare,nu avem parte de hot spot-uri,care sa sugrume magistrala sistemului,incetinind astfel si procesoarele care
fac lucruri utile,…aici fiecare procesor va testa valoarea unei variabile locale thread-ului,care se va afla in cache,iar spre deosebire
de prima implementare,atunci cand un thread va parasi sectiunea sa critica,va “lasa” controlul spinlock-ului in “grija” altui thread din coada,
care doarea sa intre in sectiunea sa crtica,nemaiexistand astfel acea “lupta” intre thread-uri..care sa intre primul in sectiunea critica.
Pe langa asta fata de primele doua implementari,unde atunci cand un thread iese din sectiunea sa critica,unul din thread-urile care erau in
busy waiting va inra in sectiunea critica…insa doar acela care va fi mai “rapid”…adica thread-ul care va intra in sectiunea critica este ales intr-un mod aleator,existand
riscul ca anumite thread-uri sa astepte destul de mult.Aici insa avem o coada FIFO,adica primul thread care si-a anuntat dorinta de a intra in sectiunea critica,acela va intra,apoi al doilea…si asa mai departe.