introducere în sistemele de operare unix/linux - popirlan.ro · aplică versiunilor comerciale ale...
TRANSCRIPT
Introducere în sistemele de operare UNIX/Linux
UNIX este un sistem de operare multiproces (poate planifica concurent spre execuţie
mai multe procese), multiutilizator (poate suporta simultan sesiuni de lucru pentru mai
mulţi utilizatori), multiecran (pe ecranul calculatorului pot fi afişate rând pe rând mai multe
ecrane virtuale), interactiv. Pe sistemele UNIX mai multe procese se pot execută simultan,
fără să existe restricţii semnificative asupra numărului lor (grad înalt de multiprogramare).
Bazele sistemului de operare UNIX au fost puse în 1968 de către Ken Thompson şi
Denis Ritchie de la laboratoarele Bell. Ei au dezvoltat în 1968 un sistem monoutilizator pe un
calculator POP-7. La transportul sistemului pe o maşina POP 11/20 (în anul 1970) au fost
adăugate o serie de mecanisme de creare de noi procese (fork) şi utilitare. În anul 1973 are loc
prima scriere în limbajul C a sistemului (până atunci se lucrase în limbaj de asamblare), ceea
ce a dus la realizarea unei foarte bune portabilităţi (testată pe maşina INTERDATA 8/32).
Limbajul C a fost conceput special pentru a rescrie nucleul sistemului de operare UNIX. În
1978 laboratoarele Bell comercializează versiunea UNIX v7 (prima versiune comercială a
sistemului) şi tot în acest an se creează Unix Support Group la AT&T.
Distribuit liber în universităţi sub formă de surse, UNIX v7 s-a dezvoltat pe maşini din
familia POP-11 îmbogăţindu-se cu noi facilităţi. Când limitările maşinilor pe 16 biţi au
devenit evidente, linia a continuat pe familia DEC VAX (maşini pe 32 de biţi) cu UNIX 32v.
Sistemele de operare UNIX formează o familie. UNIX este o marcă înregistrată a AT&T Bell
Laboratories. Orice sistem care cuprinde cuvântul UNIX în numele său este considerat ca
autentic. Restul sistemelor sunt clasificate în:
I. Sisteme derivate din UNIX (UNIX based);
II.Sisteme similare cu UNIX (UNIX like);
Sistemele din prima categorie sunt rezultatul adaptării de către constructor pe propria
maşină, a unui UNIX obţinut prin licenţa de la AT&T. Numele cu sufixul NIX, IX, sau X se
aplică versiunilor comerciale ale unor astfel de sisteme. Un rol deosebit îl ocupă sistemele de
operare SunOS şi Solaris ale firmei Sun Microsystems, care fac parte tot din familia UNIX.
LINUX este o versiune de UNIX distribuită liber, dezvoltată în principal de Linus Torvalds la
Universitatea din Helsinki, Finlanda. Mai mulţi programatori dedicaţi (hack-eri de sistem) şi-
au unit forţele prin intermediul Internetului, dând astfel oricărui amator cu destule cunoştinţe
şi pricepere posibilitatea să participe la dezvoltarea şi modificarea sistemului. Nucleul Linux-
ului nu utilizează deloc cod care să fie în vreun fel proprietatea cuiva, mare parte din
programele disponibile pentru Linux fiind dezvoltate în cadrul proiectului GNU al Fundaţiei
pentru Software Liber (Free Software Foundation) din Cambridge, Massachusetts. În plus,
programatorii din întreaga lume au contribuit la software-ul pentru Linux, care este în
continuă creştere şi diversificare.
Astăzi, Linux este o variantă de UNIX completă, capabilă să execute Xwindows,
TCP/IP, Emacs, poştă electronică şi ştiri. Aproape toate pachetele de programe distribuite
liber au fost transportate şi pe Linux, tot mai multe aplicaţii comerciale devenind disponibile
şi pentru acest sistem de operare.
Sistemul UNIX a adus cu sine un număr de concepte interesante care au asigurat
portabilitatea sa pe toată gama de calculatoare existente şi acceptarea sa ca bază pentru
sistemele deschise. Multe din elementele de noutate introduse de UNIX se regăsesc astăzi în
sistemele de operare implementate pe diferite tipuri de arhitecturi (de la MS DOS pentru
calculatoare personale, la HELIOS pentru transputere şi la sistemele de operare pentru
arhitecturi paralele deosebit de puternice).
Linux este compatibil în mare măsură cu un număr de standarde UNIX, incluzând
caracteristicile IEEE POSIX. 1, System V şi BSD, la nivel de sursă. Scopul principal în
timpul dezvoltării acestui sistem de operare a fost acela de a asigura un nivel de
compatibilitate cât mai mare cu restul sistemelor şi aplicaţiilor UNIX. Un număr mare de
programe UNIX, accesibile liber, disponibile prin Internet sau altfel, pot fi compilate imediat
pe Linux. În plus, tot codul sursă al Linux-ului, incluzând nucleul, driverele pentru periferice,
bibliotecile, programele utilizator şi utilitarele de dezvoltare sunt distribuite liber.
Caracteristicile Linux-ului includ controlul execuţiei job-urilor tip POSIX,
pseudoterminalele, suportul pentru versiuni naţionale sau particularizate de tastatură folosind
driverele de tastatură încărcate dinamic şi console virtuale. Nucleul poate emula instrucţiuni
în virgulă mobilă astfel încât toate programele pot fi executate şi pe procesoare fără
coprocesor integrat.
Linux posedă o implementare completă a suitei de protocoale de comunicaţie TCP/IP.
Sunt incluse drivere pentru cele mai răspândite plăci de reţea Ethernet, implementări pentru
SLIP, PLIP şi PPP, sistem de fişiere în reţea (NFS). De asemenea este inclusă gama completă
de servicii client şi server TCP/IP, cum sunt ftp, telnet, smtp, nntp.
Linux utilizează partajarea de memorie între programe cu copiere la scriere. Acest
lucru înseamnă o reducere a necesarului de memorie şi deci o mai bună utilizare globală a
acesteia. În vederea creşterii memoriei disponibile pentru execuţia programelor, Linux
implementează paginarea pe disc, permiţând alocarea a până la 256 MB a spaţiului de swap.
Tot nucleul gestionează întreaga memorie internă atât pentru execuţia programelor cât şi
pentru accesul mai rapid la fişiere, de tip cache. în acest fel, toată memoria disponibilă este
utilizată pentru cache de fişiere. Când se rulează programe mai mari, zona de cache este
diminuată corespunzător.
Programele executabile pot folosi legarea dinamică la bibliotecile partajate: codul
bibliotecii, utilizat în comun, se găseşte într-un unic fişier pe disc. Astfel, programele
executabile pot ocupa mult mai puţin spaţiu. Există şi posibilitatea legării statice, când codul
este introdus în întregime în fişierul executabil, pentru cei care doresc depanarea sau
întreţinerea unor executabile complete.
În Linux mai mulţi utilizatori pot folosi calculatorul în acelaşi timp executând
independent diferite aplicaţii. Un utilizator în sistemul UNIX este oricine care poate
interacţiona cu sistemul prin deschiderea unei sesiuni de lucru, fie de la un terminal, fie din alt
sistem în cadrul reţelei.
Una din contribuţiile importante ale UNIX-ului este încercarea de standardizare a
sistemelor de operare. Pe lângă standardizarea serviciilor sistem şi a comenzilor utilizator, un
efort particular a fost depus şi în domeniul sistemului de fişiere. În cazul Linux-ului, acest
efort s-a concretizat într-un document numit Linux Filesystem Standard (Standardul
sistemului de Fişiere Linux), prescurtat FSSTND, ajuns la versiunea 1.2.
Cea mai importantă caracteristică a sistemului de fişiere Linux este alura sa
arborescentă, cu o rădăcină unică. Partiţia rămâne baza pentru gestiunea spaţiului pe discul
magnetic, aşa cum o cunoaştem din DOS sau alte sisteme de operare. Prin formatare o partiţie
poate fi organizată ca sistem de fişiere, adică poate memora directoare şi fişiere. Structura
fişierelor într-o partiţie este de asemenea arborescentă, posedând. Sub Linux, o partiţie devine
disponibilă utilizatorilor numai prin integrarea în arborele ierarhic de fişiere al unui calculator.
Acest lucru se realizează prin montare. Montarea asociază rădăcina unei partiţii cu o cale din
sistemul de fişiere existent, cale care se numeşte punct de montare.
La pornire, sistemul de operare montează o partiţie în punctul de montare /, rădăcina
absolută a ierarhiei de fişiere a calculatorului. Această partiţie găzduieşte sistemul de fişiere
rădăcină. Sistemul de fişiere rădăcină trebuie să conţină anumite directoare, programe şi
fişiere de configurare necesare pornirii corecte a sistemului. Astfel, Linux permite o
configurare extrem de flexibilă: nucleul Linux şi sistemul de fişiere rădăcină se pot găsi
oriunde: pe o dischetă, pe o partiţie DOS sau în reţea, fără condiţionări reciproce; singura
problemă este ca nucleul să ştie unde este această partiţie.
Accesul primar la calculator se face printr-un program cu aparenţă austeră care
citeşte comenzile de la tastatură, le interpretează şi le execută. Dincolo de această
aparenţă simplă se ascund posibilităţi sofisticate de combinare a programelor, fişiere de
comenzi, monitorizarea şi controlul execuţiei.
Shell-ul este interfaţa primară a utilizatorului cu sistemul de operare. Un shell UNIX
este în primul rând un interpretor de comenzi, permiţând execuţia bogatului set de utilitare
UNIX. În al doilea rând, shell-ul este un limbaj de programare care dă posibilitatea combinării
acestor comenzi în activităţi complexe. El oferă utilizatorului un control complet asupra
programelor: execuţia lor poate fi sincronă sau asincronă, intrările şi ieşirile pot fi
redirecţionate, mediul de execuţie poate fi ajustat după dorinţă. În mod neinteractiv shell-ul
citeşte comenzi dintr-un fişier. Astfel, utilizatorul poate folosi facilităţile de programare ale
shell-ului: variabile, structuri de control (if, while, for), subprograme.
Pe unele sisteme cu resurse reduse (memorie internă, spaţiu pe disc) sistemul de
manuale este înlocuit cu un help mai puţin consumator de resurse, dar cu mai puţine
informaţii.
Pentru editarea fişierelor sursa se poate folosi unul dintre următoarele editoare: vi, joe,
jed. Linux oferă un mediu complet UNIX pentru dezvoltarea de programe şi aplicaţii,
incluzând bibliotecile standard, compilatoarele, depanatoarele şi întregul set de utilitare
software necesar. În mod obişnuit, dezvoltarea de programe pentru UNIX se face în limbajele
C/C++. Compilatorul standard pentru aceste limbaje este compilatorul GNU, gcc pentru C şi
g++ pentru C++.
În afară de C şi C++, multe alte limbaje compilate sau interpretate sunt disponibile sub
Linux, cum ar fi Smalltalk, FORTRAN, Pascal, Lisp, Scheme, JAVA şi Ada. În plus, sunt
disponibile asambloare pentru scrierea de cod în mod protejat pentru i80386. Interpretoare
sofisticate, răspândite în lumea UNIX, cum este Perl sau Tcl/Tk pentru dezvoltarea de
aplicaţii sub Xwindow sunt disponibile şi sub Linux. Depanatorul standard este gdb, care
permite execuţia controlată a unui program sau analiza unui vidaj de memorie. Cu ajutorul
utilitarului Gprof se realizează culegerea de statistici referitoare la execuţia unui program în
scopul ameliorării performanţelor sale. Alte utilitare includ make pentru compilarea
aplicaţiilor mari şi RCS, un sistem pentru întreţinerea versiunilor unui program. Legarea
bibliotecilor se poate face dinamic, permiţând fişiere executabile mici sau înlocuirea de rutine
din bibliotecă cu rutine utilizator. Linux este astfel un mediu ideal pentru dezvoltarea de
programe: modern, standard şi bine echipat. Portabilitatea pe alte sisteme de tip UNIX este
foarte mult uşurată.
Căutarea în biblioteci se face în ordinea specificării opţiunilor -l în linia de comandă.
Bibliotecile sunt fişiere cu extensia .a (archive file pentru biblioteci statice) sau .so (pentru
biblioteci dinamice). Cele mai folosite biblioteci se află în cataloagele /lib , /usr/lib şi
/usr/local/lib, dar pot exista şi în /opt/lib în alte sisteme (dependent de distribuţie).
Utilizatorul are posibilitatea să determine terminarea forţată a unor procese care
lucrează, durează mult, nu evoluează conform aşteptărilor, sunt blocate în aşteptarea unor
condiţii care nu se vor îndeplini niciodată, etc. Comanda kill poate controla într-un mod
mai complex execuţia proceselor, mod dependent chiar de procesele controlate. Procesele
pot primi din exterior semnale şi pot reacţiona la acestea în modul în care programatorul crede
de cuviinţă.
În administrarea sistemului se folosesc frecvent semnalele SIGHUP sau SIGINT pentru a
comunica unor procese server faptul că s-au efectuat modificări în sistem şi acestea vor trebui,
de exemplu, să-şi recitească fişierele de configuraţie. Utilizarea semnalelor în acest scop
depinde de fiecare caz în parte şi este descrisă în documentaţia fiecărui proces în parte.
Procesul este unitatea elementară de execuţie a sistemului de operare UNIX,
gestionată de către modulul de gestiune a proceselor şi procesoarelor din nucleul sistemului.
Un proces este o instanţă de execuţie a unui program. În terminologia UNIX un proces
este execuţia unei imagini, unde prin imagine se înţelege ansamblul elementelor care
constituie contextul de execuţie al procesului. Aceste elemente sunt:
• programul (codul)
• datele asociate programului
• starea fişierelor deschise (tabela descriptorilor de fişiere utilizator)
• catalogul de lucru
La nivelul sistemului UNIX, fiecărui proces i se alocă o intrare într-o tabelă sistem
(tabela de procese). Dimensiunea acestei tabele este dată de constanta sistem NPRCC, iar
numărul maxim de procese active care pot fi asociate unui acelaşi utilizator este
MAXUPROC. Pid-ul este de fapt indicele intrării asociate procesului în tabelă. O intrare în
tabelă conţine informaţii necesare nucleului sistemului de operare, ca de exemplu starea
procesului sau numele utilizatorului care execută procesul.
Spaţiul de adrese al unui proces cuprinde mai multe segmente cu rol diferit, funcţie de natura
informaţiilor pe care le conţin:
• zona antet (numita şi zona user sau zona U), inaccesibilă procesului, conţine structuri
de date importante prin care nucleul gestionează procesul şi-i oferă servicii prin intermediul
apelurilor sistem.
• segmentul de cod pur (text) este protejat la scriere şi adesea partajat; folosind opţiunea
-n, compilatorul poate genera programe având segmente text reentrante. Când acest segment
este partajat de către mai multe procese, el nu suferă operaţia de swapping.
• segmentul de date poate fi scris de către procesul utilizatorului care nu este nici
partajat nici accesibil celorlalte procese; el conţine date alocate static sau dinamic de către
proces; cuprinde zona de date data, zona de rezervări bss (date neiniţializate) şi zona de
alocare dinamică heap.
• segmentul de stivă nu este partajat şi creşte automat în momentul epuizării cantităţii de
memorie pe care o avea la dispoziţie (dacă maşina dispune de mecanisme hardware de
gestiune a memoriei); în caz contrar fişierul executabil trebuie reconstruit, indicându-se o
stivă de dimensiuni mai mari.
Un proces se poate afla într-una din următoarele stări:
• în execuţie (running) - în mod utilizator sau în mod nucleu, dacă procesul execută o
funcţie sistem;
• pregătit pentru execuţie (ready) - aşteaptă atribuirea procesorului de către
planificatorul de procese;
• în aşteptare (waiting) - aşteaptă producerea unor evenimente externe procesului, ca de
exemplu terminarea unei operaţii de I/O.
Un proces poate fi planificat pentru execuţie fără ca el să deţină resursa memorie. Se
lansează procesul de swapping (swapper-ul) care transferă pe suport extern alte procese
pentru a putea aduce în memorie procesul care a primit procesorul. Este transferat pe disc
segmentul de date şi cel de stivă.
Sincronizarea între procese prin semafoare
Conceptual, semaforul este o structură de date partajată de mai multe procese.
Semafoarele sunt folosite, de cele mai multe ori, pentru sincronizarea operaţiilor, atunci când
mai multe procese accesează o resursă comună. De fiecare dată când un proces doreşte
obţinerea resursei, semaforul asociat este testat; o valoare pozitivă diferită de zero arată că
resursa dorită este disponibilă, iar pentru a indica câştigarea resursei procesul decrementează
semaforul. Pentru a se asigura excluderea mutuală, operaţiile de testare şi de decrementare a
semaforului trebuie să fie atomice (instrucţiunea nu poate fi întreruptă şi este indivizibilă).
Dacă semaforul testat are valoarea zero, acesta indică câştigarea resursei de către alt proces şi
procesul care doreşte resursa trebuie să aştepte eliberarea ei. Când procesul care deţinea
resursa o eliberează, acesta trebuie să indice eliberarea ei prin incrementarea semaforului. În
momentul în care resursa a fost eliberată, procesul care aştepta eliberarea ei primeşte un mesaj
de notificare din partea sistemului.
Semafoarele reprezintă un mecanism de sincronizare, care, în principiu, e implementat
de două operaţii primitive: signal şi wait. Acestea sunt funcţii de un argument şi anume
variabila semafor. Variabila de tip semafor este un întreg şi, cu excepţia iniţializării, nu poate
fi accesată şi manipulată decât prin intermediul operaţiilor signal şi wait:
• wait(s)decrementează valoarea argumentului, variabila semafor s; dacă nu este
negativă, odată ce s-a luat decizia decrementării argumentului, această operaţie trebuie să fie
indivizibilă.
• signal(s) incrementează valoarea argumentului, variabila semafor s, ca o operaţie
indivizibilă.
Un semafor a cărui variabilă are numai valorile 0 (ocupat) şi 1 (liber) se numeşte
semafor binar, altfel se numeşte semafor general şi poate lua orice valoare. Pentru
semafoarele binare, logica lui wait(s) trebuie interpretată ca aşteptare până când variabila
semafor s devine egală cu liber, urmată de operaţia sa indivizibilă care o transformă din liber
în ocupat înainte ca controlul să fie returnat celui care a apelat funcţia. De altfel, operaţia wait
implementează faza de negociere din protocolul de excludere mutuală iar operaţia signal, care
setează variabila semafor s ca liber, reprezintă faza de eliberare din protocol.
În cazul sistemelor de tip UNIX, din punct de vedere al implementării, un semafor este
un număr întreg pozitiv care este gestionat de kernel (resursă a sistemului de operare).
Accesul la semafor este realizat printr-o serie de apeluri de sistem. El este implementat sub
forma unei memorii comune între procese. Numărul maxim de semafoare pe un singur ID este
o constantă a sistemului, pe LINUX de obicei el este de 500.
Există mai multe funcţii de sistem care operează asupra semafoarelor din exteriorul
programelor. De exemplu:
• Inter Process Communication Status (apelată ipcs) oferă informaţii asupra
semafoarelor şi memoriei partajate alocate şi utilizate în momentul respectiv în sistem; de
asemenea furnizează ID-ul semaforului sau memoriei partajate pentru următoarea comandă
• Inter Process Communication Remove (apelată ipcrm {<sem> sau <shm>} ID) unde
ID este ID-ul memoriei partajate sau semaforul obţinut cu comanda ipcs.
Folosirea acestor comenzi asigură o dezalocare manuală a semafoarelor create la o
rulare anterioară a programului. Întreruperea neaşteptată a programului nu determină
dezalocarea de către sistem a resurselor create în cadrul programului respectiv, astfel încât la
o rulare ulterioară a aceluiaşi program încercarea de creare a resursei cu acelaşi nume are ca
efect alocarea resursei deja existente. Acest fapt poate determina o comportare neprevăzută a
programului.
Pentru a asigura drepturi de scriere/citire asupra structurilor de date asociate
semafoarelor, valorile anterior descrise se combină prin SAU logic (operator | în C/C++) cu
0666. În caz de insucces funcţia întoarce -1 şi poziţionează variabila globală errno pe un cod
de eroare care indică motivul eşecului:
• EACCES : Există deja o instanţă de semafoare asociată cheii key, dar drepturile
asociate acesteia nu sunt acoperitoare pentru cele descrise de semflg.
• EEXIST : S-a încercat crearea exclusivă a unei instanţe de semafoare (semflg &
IPC_CREAT = true şi semflg & IPC_EXCL=true), dar o astfel de instanţă era deja asociată
cheii key.
• EINVAL : nsems este în afără limitelor acceptate (nsems<=0 sau nsems>limita impusă
de sistem), sau o instanţă de semafoare este deja asociată cheii key, dar numărul de semafoare
al acestei instanţe este mai mic decât nsems.
• ENOENT : S-a încercat alocarea unei instanţe de semafoare asociată cheii key, dar
acea instanţă nu este corectă.
• ENOSPC : În sistem există deja un număr mare de identificatori, crearea unuia nou ne
mai fiind posibilă, sau sistemul conţine deja prea multe semafoare, crearea unora noi ne mai
fiind posibilă.
Se presupune următoarea problemă: se doreşte ca mai multe procese să aibă acces la o
resursă comună, într-o anumită ordine. În acest caz se presupune că resursa comună este un
fişier. Accesul se doreşte a fi în ordinea de lansare a proceselor, presupunând lansarea lor într-
o buclă for. Procesele scriu în fişier numărul de ordine al procesului lansat.
Pentru aceasta fiecare proces va avea asociat un semafor care va fi eliberat de către
procesul anterior, ordinea fiind dată de indicele din vectorul de semafoare. Excepţie face
bineinţeles primul proces (cel cu indicele 0) care va fi eliberat de către procesul părinte.
Programul părinte (cel care lansează toţi fii) face următoarele operaţii:
• Crează vectorul de semafoare cu ajutorul funcţiei semget();
• Deschide fişierul exemplu.txt;
• Lansează fii cu ajutorul funcţiei fork();
• Setează operaţia de incrementare pentru primul fiu şi operează asupra semaforului;
• Aşteaptă toţi fiii;
• Închide fişierul.
Programul fiu face următoarele operaţii:
• Setează operaţia de decrementare şi operează asupra semaforului propriu, deoarece
valoarea semaforului este 0 el se blochează până când va fi eliberat de către procesul creat
înaintea sa;
• Operează asupra fişierului;
• Dacă nu este ultimul proces setează operaţia de incrementare şi operează asupra
semaforului procesului următor.
Dacă este ultimul proces nu mai operează asupra următorului semafor deoarece acesta nu mai
există.
• Închide fişierul (din punctul lui de vedere). Aceasta este o operaţie opţională deoarece
fişierul este oricum închis de către procesul părinte.
Comunicaţia între procese prin segmente de memorie partajată
Memoria partajată permite mai multor procese să-şi partajeze spaţiul virtual de adrese.
Aceasta este cea mai rapidă, dar nu neaparat cea mai uşoară modalitate de comunicare între
procese. În general, un proces crează sau îşi ataşează un segment de memorie partajată.
Mărimea şi modul de acces pentru acest segment sunt fixate în momentul creării. Apoi,
procesul îşi ataşează segmentul de memorie partajată, amplasându-l în spaţiul său de adrese.
Segmentele de memorie partajată reprezintă o altă modalitate de comunicare între procese
oferită de sistemul de operare şi accesibilă utilizatorilor prin apeluri de sistem.
În aplicaţii o zona de memorie partajată este identificată, ca în cazul celorlalte
mecanisme IPC (Inter Process Comunications), printr-o cheie. Pe baza acestei chei sistemul
de operare furnizează în urma unei cereri sistem (shmget) un identificator. Acesta este un
număr întreg pozitiv care identifică în mod unic segmentul de memorie partajată şi pe baza lui
se poate face accesul la structura de date care o descrie.
Apelurile de sistem pentru crearea şi utilizarea segmentelor (zonelor) de memorie partajată
sunt urmatoarele:
• shmget creează o nouă regiune de memorie partajată sau întoarce identificatorul unei
regiuni existente;
• shmctl manipulează parametrii asociaţi cu zona de memorie partajată;
• shmat ataşează o regiune la spaţiul de adrese al unui proces;
• shmdt detaşează o regiune de la spaţiul de adrese al unui proces;
După ataşare memoria partajată devine parte a spaţiului virtual de adrese al procesului,
conţinutul ei poate fi accesat ca şi celelalte date, fără să fie nevoie de apeluri sistem speciale.
Comanda shell ipcs permite obţinerea de informaţii asupra stării segmentelor de
memorie partajată, asupra stării cozii de mesaje şi a vectorilor de semafoare; informaţii
suplimentare se obţin consultând documentaţia on-line ($ man ipcs) .
În fişierele sursă care efectuează apeluri de sistem pentru operaţii cu segmente de
memorie partajată trebuie incluse următoarele fişiere antet:
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/shm.h>
Zona maximă de memorie care poate fi partajată pe Linux este de 4M segment
continuu.
Operaţia de blocare interzice swapper-ului să evacueze (swapp) segmentul de memorie
partajată pe disc, iar în cazul memoriei paginate, la cerere, se interzice mutarea în memorie şi
evacuarea pe disc a mulţimii de pagini rezidente aparţinând regiunii (working set-ului). Este
deci o fixare în memorie.
Comenzile marcate cu [*] pot fi executate cu succes doar de către procesele care
aparţin utilizatorului cu identificatorul egal cu identificatorul superuser-ului, sau cu
identificatorul cuid din structura shmid_ds asociată zonei de memorie partajată, sau cu
identificatorul uid din aceeaşi structură.
În caz de eşec funcţia întoarce valoarea -1 şi poziţionează variabila globală errno
astfel:
• EACCES : cmd este IPC_STAT dar nu este permisă citirea structurii shmid_ds.
• EFAULT : Zona de memorie indicată de buf este ilegală.
• EPERM : cmd are una din valorile IPC_SET sau IPC_RMID însă procesul care
încearcă această operaţie nu aparţine nici superuser-ului nici unuia dintre utilizatorii indicaţi
prin câmpurile uid sau gid ale structurii de date asociată zonei de memorie shmid.
La ataşarea unei regiuni se fac verificări asupra permisiunilor de acces la această
regiune. Segmentul partajat nu trebuie sa se suprapună peste alte segmente mapate în spaţiul
de adrese al procesului. La ataşare, nucleul verifică dacă regiunea partajată încape în spaţiul
de adrese al procesului.
Crearea şi utilizarea thread-urilor POSIX
Thread-urile (fire de execuţie) reprezintă o modalitate software de îmbunătăţire a
performantelor de calcul prin reducerea costului de comutare a proceselor. Un thread este un
proces mai uşor, cu o stare redusă. Reducerea stării se obţine prin gruparea unui număr de
thread-uri corelate intre ele pentru a partaja diferite resurse de calcul, ca de exemplu, memoria
şi fişierele. În sistemele bazate pe thread-uri, thread-ul devine cea mai mică entitate de
planificare, iar procesul serveşte ca un mediu de execuţie a thread-urilor. În astfel de sisteme,
un proces cu un singur thread este identic cu un proces clasic.
Fiecare thread reprezintă un flux separat de execuţie şi este caracterizat prin propria sa
stivă şi stare hardware (registre, flag-uri). De vreme ce toate celelalte resurse, cu excepţia
procesorului, sunt gestionate de către procesul care le înglobează, comutarea între thread-urile
care aparţin aceluiaşi proces, care implică doar salvarea, respectiv restaurarea, stării hardware
şi a stivei, este rapidă şi eficientă. Totuşi comutarea între thread-urile care aparţin unor
procese diferite implică tot costul de comutare a proceselor.
Thread-urile, după implementare, se împart în kernel-space şi user-space. Când thread-
urile sunt implementate în kernel, schimbarea contextului se face de către kernel fără ca
aplicaţia să aibă cunoştinţă de aceasta şi de accea aceste implementări sunt preemptive. În
schimb, când thread-urile sunt implementate în user-space atunci schimbarea contextului se
face de către librăria thread-ului, la nivelul aplicaţiei, şi în cazul acesta thread-urile pot fi
preemptive sau nonpreemptive, sau se pot alege în funcţie de implementare diferite versiuni.
De asemenea e posibilă combinaţia kernel- space şi user-space în momentul în care se
lansează mai multe thread-uri la nivel user-space în interiorul unui thread kernel-space.
Dezavantajul unui thread la nivel user: nu poate beneficia de multiprocesoare.
Thread-urile sunt un mecanism eficient de exploatare a concurenţei programelor. Un
program poate fi împărţit în mai multe thread-uri, fiecare cu o execuţie mai mult sau mai puţin
independentă. Thread-urile comunică între ele prin accesul la spaţiul de adresă a memoriei
procesului, pe care îl partajează. Thread-ul poate fi privit ca o funcţie specială şi astfel toate
caracteristicile funcţiilor din C sunt regăsite şi la thread-uri. În sistemele cu memorie partajată
(multiprocesoare) execuţia fiecărui thread de către un procesor separat (dacă sunt
implementate la nivel de kernel space) asigură accerarea paralelă a programelor. Chiar şi în
sistemele uniprocesor, împărţirea unui program în thread-uri poate aduce îmbunătăţiri prin
execuţia concurentă a mai multor sarcini de calcul (de exemplu, în cazul interfeţelor grafice).
În sistemul de operare Unix tradiţional nu sunt definite thread-uri, fiecare proces conţine un
singur thread, iar alocarea timpului de execuţie al procesorului se face între procesele active,
după diferiţi algoritmi de planificare.
În sistemele de operare derivate din Unix, dezvoltate pentru multiprocesoare şi
multicalculatoare, s-au implementat diferite facilităţi pentru controlul şi partajarea resurselor
multiple (procesoare, memorie), între thread-uri.
Cea mai utilizată modalitate de implementare a thread-urilor în sistemele derivate din
UNIX sau pe sistemele multiprocesoare este aceea definită în standardul POSIX (IEEE
POSIX Standard 1003.4a), care asigură portabilitatea între platformele hardware diferite.
Thread-ul POSIX este denumit pthread.
O aplicaţie cu thread-uri POSIX este un program C care utilizează diferite funcţii din
biblioteca POSIX pentru crearea, definirea atributelor, controlul stărilor (terminare, detaşare)
thread-urilor.
Aceste funcţii sunt definite într-o bibliotecă (libpthread.a), care trebuie adaugată (la
link-are) programului apelant (prin opţiunea de compilare –lpthread).
Un thread POSIX se crează prin apelul funcţiei cu prototipul:
int pthread_create(pthread_t *thread_ID, pthread_attr_t *thread_attr, void
*(*thread_func)(void *), void *thread_param);
Această funcţie arată care sunt datele necesare pentru crearea unui thread:
• Atributele thread-ului (transmise prin argumentul thread_attr).
• Funcţia de execuţie a thread-ului (transmisă prin argumentul void *(thread_func)).
• Parametrul de execuţie a thread-ului (transmis prin argumentul thread_param).
Funcţia pthread_create returnează o valoare de tip int, care este egală cu 0 dacă thread-
ul a fost creat corect şi diferită de zero dacă thread-ul nu a fost creat. De asemenea, în
variabila thread_ID, al cărui pointer este dat ca prim argument al funcţiei pthread_create, se
returnează identificatorul thread-ului nou creat, care este de tipul pthread_t. Procesul apelant
poate folosi identificatorul thread-ului pentru a efectua diferite operaţii asupra thread-ului.
Parametrul thread_attr este un parametru prin care se specifică atributele de creare a unui
thread. Acest parametru este de tipul pthread_attr_t, a cărui formă depinde de implementarea
bibliotecii. Cel mai frecvent, pthread_attr_t este un pointer la o structură de date care
grupează mai multe atribute, ca de exemplu prioritatea, politica de planificare, dimensiunea
stivei.
Pentru a crea un thread, trebuie creat întâi un obiect atribut (de tipul pthread_attr_t), a
cărui adresă este transmisă ca argument funcţiei pthread_create. Un obiect de atribute se
crează prin apelul funcţiei:
int pthread_attr_init(pthread_attr_t *attr);
care alocă spaţiu în memorie obiectului attr creat cu valori implicite ale fiecărui atribut
component. După utilizarea obiectului de atribute pentru crearea unuia sau mai multor thread-
uri, el poate fi distrus prin apelul funcţiei:
int pthread_attr_destroy(pthread_attr_t *attr);
care eliberează zona de memorie ocupată de obiectul respectiv. Distrugerea obiectului de
atribute nu afectează thread- urile deja create pe baza acestuia.
Funcţia de execuţie se trimite ca argument al funcţiei pthread_create printr-un
pointer de tipul: void
*(*thread_func)(void *),
adică este o functie care returnează un pointer la void şi are ca argument un pointer la void.
Funcţia de execuţie are rolul de punct de intrare în execuţia unui thread, deci este echivalenta
funcţiei main a unui proces. Ea este prima funcţie executată de un thread nou creat. Thread-ul
creat se termină automat când se termină funcţia lui de execuţie.
Depinzând de politica de planificare a thread-ului curent şi a celui nou creat, este
posibil ca thread-ul nou creat să înceapă execuţia înainte de terminarea funcţiei
pthread_create. Se poate de asemenea întâmpla ca thread-ul nou creat să se termine înainte de
returnarea din funcţia de creare pthread_create, şi atunci indentificatorul returnat (în
parametrul thread) să fie deja invalid. De aceea este importantă testarea codului de eroare
ESRCH înainte de a folosi indentificatorul unui thread ca parametru pentru alte funcţii. De
aici se poate vedea că nu este indicată transmiterea unui argument care se modifică în timp
foarte scurt thread-ului.
Se poate întampla ca din cauza planificatorului de proces incrementarea din bucla for
să aibă loc înainte de terminarea iniţializării în funcţia thread şi astfel parametrul primit de
funcţia thread să fie incorect.
Thread-ul principal al procesului (care începe execuţia cu funcţia main) creează un
nou thread cu atribute implicite prin apelul funcţiei pthread_create cu argumentul NULL
pentru atribute. Thread-ul creat execută funcţia thread_func, cu parametru un pointer la void
obţinut prin conversia pointerului la variabila de tip întreg val, căreia i-a fost atribuită
valoarea 77. Parametrul funcţiei de execuţie se specifică în cel de-al patrulea argument (in) al
funcţiei pthread_create. În funcţia de execuţie a thread-ului se face conversia inversă, din
pointer la tipul int, după care valoarea parametrului primit poate fi obţinută prin dereferenţiere
şi utilizată corespunzător.
Un thread se poate termina prin terminarea funcţiei sale de execuţie (terminare
normală), sau poate fi oprit de un alt thread (terminare prin anulare).
Terminarea funcţiei de execuţie a unui thread are loc atunci când se ajunge la sfârşitul
funcţiei (punctul de revenire din funcţie) sau prin apelul în orice punct al funcţiei
pthread_exit. Funcţia pthread_exit este echivalentul funcţie exit care termină întregul proces,
inclusiv toate thread-urile create de acesta. Dacă nu se apelează implicit una din funcţiile exit
sau pthread_exit, atunci modul în care se termină un thread depinde de tipul acestuia. Thread-
ul principal al procesului (cel care execută funcţia main) apelează implicit funcţia exit la ieşire
(înainte de returnare), forţând astfel terminarea tuturor thread-urilor pe care le-a creat.
Celelalte thread-uri apelează implicit funcţia pthread_exit la ieşire.
Este posibilă şi functionarea în care un thread oarecare, altul decât cel principal, să
apeleze funcţia exit, forţând astfel terminarea tuturor thread-urilor şi a întregului proces. De
asemenea, dacă thread-ul principal apelează funcţia pthread_exit, el se termină, dar alte
thread-uri ale procesului pot să-şi continue execuţia. Procesul însuşi se va termina atunci când
se termină ultimul dintre thread-urile sale.
Funcţia pthread_exit eliberează toate datele specifice thread-ului apelant, inclusiv
datele din stiva thread-ului, dar nu şterge sau modifică resursele care ar putea fi partajate de
alte thread-uri. De exemplu, nu închide în mod automat fişierele dacă nu au fost apelate
explicit funcţiile de închidere, deoarece acestea ar putea fi folosite de alte thread-uri. În
schimb, datele din stiva unui thread care a executat o funcţie pthread_exit sau exit devin
invalide şi nu mai pot fi folosite. Funcţia exit eliberează toate datele, din stivă sau resurse de
sistem, dar acest lucru este normal, deoarece nici un thread nu mai continuă execuţia dupa un
apel exit, deci nici datele create de thread-uri nu mai sunt necesare.
Un thread poate fi terminat şi prin apelul de către un alt thread a funcţiei:
int pthread_cancel(pthread_t *thread_ID);
Programul următor implementeaza algoritmul cu un număr variabil de thread-uri.
/* matrix-alternat.c */
#include<stdio.h>
#include<stdlib.h>
#include<pthread.h>
#include<sys/time.h>
#include"speedup.c"
int dim; /*dimensiunea matricelor*/
int nr_thread;
float **mata,**matb; /*matricele a şi b*/
float **matc; /*matricea pentru lucrul secvential*/ float **matc1; /*matricea pentru lucrul
paralel*/ pthread_t *vector;
void *thread_calcul(void *in)
{
int where=*(int *)in;
int i,j,k;
/*calcul produs*/
for(i=where;i<dim;i=i+nr_thread)
for(j=0;j<dim;j++)
{
matc1[i][j]=0.0;
for(k=0;k<dim;k++)
matc1[i][j]+=mata[i][k]*matb[k][j];
}
pthread_exit(NULL);
}
int main()
{
int i,j,k; int *index; float *temp;
struct timeval t1s,t2s; /*timpi pentru algoritmul secvential*/
struct timeval t1p,t2p; /*timpi pentru algoritmul paralel*/
printf("Introduceti dim matricei dim=");fflush(stdout);
scanf("%d",&dim);fflush(stdin);
/*alocare de memorie pentru matricile a şi b*/
mata=(float **)calloc(dim,sizeof(float *)); matb=(float **)calloc(dim,sizeof(float *));
matc=(float **)calloc(dim,sizeof(float *)); matc1=(float **)calloc(dim,sizeof(float *));
temp=(float *)calloc(dim*dim,sizeof(float)); for(i=0;i<dim;i++)
{
mata[i]=temp;
temp+=dim;
}
temp=(float *)calloc(dim*dim,sizeof(float));
for(i=0;i<dim;i++)
{
matb[i]=temp;
temp+=dim;
}
/*generarea matricilor a şi b*/
for(i=0;i<dim;i++)
for(j=0;j<dim;j++)
{
mata[i][j]=1.0;/*(float)(15.0*rand()/(RAND_MAX+1.0)); */
matb[i][j]=1.0; /* (float)(15.0*rand()/(RAND_MAX+1.0)); */
}
/*crearea zonei secventiale*/
gettimeofday(&t1s,NULL);
temp=(float *)calloc(dim*dim,sizeof(float));
for(i=0;i<dim;i++)
{
matc[i]=temp;
temp+=dim;
}
for(i=0;i<dim;i++)
{
for(j=0;j<dim;j++)
{
matc[i][j]=0.0;
for(k=0;k<dim;k++)
matc[i][j]+=mata[i][k]*matb[k][j];
}
}
gettimeofday(&t2s,NULL);
/*zona paralela*/
printf("\nIntroduceti nr de thread-uri nr_thread=");
fflush(stdout); scanf("%d",&nr_thread);fflush(stdin); gettimeofday(&t1p,NULL);
/*setari pentru zona paralela*/
temp=(float *)calloc(dim*dim,sizeof(float));;
for(i=0;i<dim;i++)
{
matc1[i]=temp;
temp+=dim;
}
/* vectorul de id-uri*/
vector=(pthread_t *)calloc(nr_thread,sizeof(pthread_t));
index=(int *)calloc(nr_thread,sizeof(int));
/*zona de calcul*/
for(i=0;i<nr_thread;i++)
{
index[i]=i;
pthread_create(&vector[i],NULL,thread_calcul,(void *)&index[i]);
}
for(i=0;i<nr_thread;i++) pthread_join(vector[i],NULL);
gettimeofday(&t2p,NULL);
for(i=0;i<dim;i++)
for(j=0;j<dim;j++)
if((matc[i][j]-matc1[i][j])>1.0e-5)
printf("eroare la elem %f!=%f\n", matc[i][j], matc1[i][j]);
speedup(t1s,t2s,t1p,t2p,nr_thread);
}
În modelul de programare paralelă prin variabile partajate, mai multe procese sau
thread-uri executate concurent, pe procesoare diferite, comunică între ele prin intermediul
variabilelor partajate. Dar accesul nerestricţionat la variabilele partajate de către două sau mai
multe procese concurente poate produce erori de execuţie a căror sursă o reprezintă
inconsistenţa temporară a variabilelor partajate şi propagarea acestei inconsistenţe în sistem.
Dacă fiecare proces ar putea să completeze, fără să fie întrerupt, actualizarea variabilelor
partajate, atunci toate celelalte procese ar vedea numai valori consistente ale variabilelor
partajate.
Mecanismele de sincronizare între procese concurente reprezintă un ansamblu de
protocoale, funcţii de sistem de operare şi funcţii de biblioteci, care permit serializarea
acceselor proceselor concurente la resursele partajate. Aceste mecanisme de sincronizare
(denumite şi obiecte de sincronizare) sunt implementate pe baza suportului hardware de
excludere mutuală (instrucţiuni atomice) disponibile în sistem. În această lucrare vor fi
descrise mecanismele de sincronizare cel mai frecvent utilizate în programarea concurentă:
mutex-uri, semafoare, variabile de condiţie şi bariere pentru sincronizarea thread-urilor
POSIX.
Semafoarele sunt obiecte de sincronizare care controlează:
• accesul mai multor thread-uri la o resursă partajată;
• accesul unui thread la resurse partajate multiple;
Din punct de vedere al implementării, un semafor este un întreg pozitiv care este
gestionat de kernel (resursă a sistemului de operare). Operaţiile de bază efectuate asupra
semafoarelor sunt incrementarea atomică a semaforului şi aşteptarea până când semaforul este
diferit de 0, pentru a-l decrementa atomic.
Paralelismul la nivel de instructiune
Paralelismul al nivel de instructiune este nivelul de programare paralela cu
granularitatea cea mia fina. Modelul unui astfel de program paralel este o succesiune de
regiuni secventiale si regiuni paralele. In regiunile paralele executia programului este
distribuita intre mai multe thread-uri, implicit in numar egal cu numarul de procesoare. In
general, in regiunile paralele sunt distribuite iteratiile unor bucle de calcul paralelizabile, si,
de aceea, paralelismul la nivel de instructiune mai este denumit si paralelism omogen.
Programarea in acest model, adoptat de diferite compilatoare cu multiprocesare, este
mai simpla decit programarea paralela prin crearea explicita a proceselor si thread-urilor, in
primul rind datorita „programului unic”: exista un singur program, care este distribuit
procesoarelor prin distribuirea iteratiilor buclelor. Iteratiile sunt identice ca segment de cod si
diferea doar prin variabila de control a buclei si, implicit, prin varabilelel accesate pentru
scriere si citire.
De asemenea, crearea thread-urilor de executie, amplasarea varabilelor in segmente de
memorie partajata sau locala, crearea obiectelor de sincronizare, toate acestea sunt realizate de
catre compilator, prin interpretarea unor directive de compilare.
Conditia pentru generarea codului paralel de catre compilatoarele cu multiprocesare
este ca buclele care se distribuie sa fie independente, deci paralelizabile. Directivele de
paralelizare se pot introduce numai daca testele de analiza a dependentelor de date in bucle
stabilesc independenta acestora.
Vom face operatia de inmultire a doua matrici patratice folosind directivele for si
parallel. Deoarece directiva for nu ne asigura o anumita ordine, decit daca vom utiliza clauza
ordered, vom a avea o impartire arbitrara a matricii pe linii. Timpul necesar executiei va fi
asfisat in fisierul timp.dat precum si pe ecran. Dupa cometarea directivelor de OpenMP vom
avea un cod C nativ si ca tare va putea fi compilat cu ajutorul gcc-ul standard. Numarul de
thread-uri se va da ca parametru in linia de comanda. Matricea va avea dimensiunea de 1000
dat ca parametru si va fi generata aleator.
Fisierul timeprint.c
double timeprint(struct timeval t1,struct timeval t2,int T,long dim,FILE *fp,int thread)
{
double operand1,operand2,operand;
operand=0.0;
operand1=(double)t1.tv_sec+(1e-6)*t1.tv_usec;operand2=(double)t2.tv_sec+(1e-)*t2.tv_usec;
operand=operand2-operand1;
fprintf(fp,"%ld %lf %d %lf %d\n",dim,operand,thread,operand/T,T);
fflush(fp);
printf("%fs sum of %d executions with %ld equations and %d threads\n", operand, T,
dim,thread);
fflush(stdout);
return operand;
}
#include<stdio.h>
#include<stdlib.h>
#include<omp.h>
#include<sys/time.h>
#include"timeprint.c"
#define dim 1000
double mata[dim][dim],matb[dim][dim],matc[dim][dim];
int main(int argc,char **argv)
{
int i,j,thread; FILE *fp;
struct timeval t1,t2; thread=atoi(argv[1]); for(i=0;i<dim;i++) for(j=0;j<dim;j++)
{
mata[i][j]=rand();
matb[i][j]=rand();
}
gettimeofday(&t1,NULL);
omp_set_num_threads(thread);
#pragma omp parallel for private(j)
for(i=0;i<dim;i++) for(j=0;j<dim;j++) matc[i][j]=mata[i][j]*matb[i][j];
gettimeofday(&t2,NULL); fp=fopen("timp.dat","a"); timeprint(t1,t2,1,1000,fp,thread);
close(fp);
}
Jacobi cu linii dominante
Fisierul timeprint.c
double timeprint(struct timeval t1,struct timeval t2,int T,long dim,FILE *fp,int thread)
{
double operand1,operand2,operand;
operand=0.0;
operand1=(double)t1.tv_sec+(1e-6)*t1.tv_usec;operand2=(double)t2.tv_sec+(1e-)*t2.tv_usec;
operand=operand2-operand1;
fprintf(fp,"%ld %lf %d %lf %d\n",dim,operand,thread,operand/T,T);
fflush(fp);
printf("%fs sum of %d executions with %ld equations and %d threads\n", operand, T,
dim,thread);
fflush(stdout);
return operand;
}
Fisierul bench.c
#include<stdio.h>
#include<stdlib.h>
#include<sys/time.h>
#include<string.h>
#include"timeprint.c"
#include "jacobi.c"
#define numar 10
int main(int argc,char **argv)
{
struct timeval t1,t2;
double **mat,*x,*rez,*temp1,temp,*y;
double err;
int i,l,j; int dim; FILE *fp; int thread;
dim=atoi(argv[1]);
y=(double *)calloc(dim,sizeof(double));
rez=(double *)calloc(dim,sizeof(double));
//here is the parallel zone
mat=(double**)calloc(dim,sizeof(double*));
temp1=(double *)calloc(dim*dim,sizeof(double)); for(i=0;i<dim;i++)
{
mat[i]=temp1;
temp1+=dim;
}
x=(double *)calloc(dim,sizeof(double));
/* create the test matrix */ for(i=0;i<dim;i++) rez[i]=(double)i+1; for(i=0;i<dim;i++)
for(j=0;j<dim;j++){
if(i!=j)
{
}
for(i=0;i<dim;i++)
{
mat[i][j]=20000*rand()/(double)RAND_MAX;
if((rand()/(double)RAND_MAX)<0.5) mat[i][j]=-mat[i][j];
temp=0.0;
for(j=0;j<dim;j++) if(j!=i) temp+=fabs(mat[i][j]);
mat[i][i]=temp+(20000+temp)*rand()/(double)RAND_MAX+0.00001;
if((rand()/(double)RAND_MAX)<0.5) mat[i][i]=-mat[i][i];
}
//generate the free term for(i=0;i<dim;i++)
{
y[i]=0.0; x[i]=0.0;
for(j=0;j<dim;j++) y[i]+=mat[i][j]*rez[j];
}
err=atof(argv[2]); gettimeofday(&t1,NULL); for(l=0;l<numar;l++) jacobi(mat,y,x,dim,err);
gettimeofday(&t2,NULL);
for(i=0;i<dim;i++) {if(fabs(rez[i]-x[i])>1E-5) printf("%lf=%lf\n",rez[i],x[i]); fflush(stdout);}
fp=fopen("time-ser.dat","a");
timeprint(t1,t2,numar,dim,fp,1);
fclose(fp); free(*mat); free(mat); free(rez); free(y); free(x);
return 0;
}
fisierul jacobi.c
/*
JACOBI SERIAL with diagonal ROW dominant
*/
#include<string.h>
#include<math.h>
void jacobi(double **mat,double *ty,double *tx,int dim,double err)
{
double *xn_1; int i,j,k,m; double q,sum;
xn_1=(double *)calloc(dim,sizeof(double));
//JACOBI
for(i=0;i<dim;i++) tx[i]=ty[i]/mat[i][i];
//compute q q=0.0;
for(i=1;i<dim;i++) q+=fabs(mat[0][i]/mat[0][0]);
for(i=1;i<dim;i++)
{
sum=0.0;
for(j=0;j<dim;j++) if(i!=j) sum+=fabs(mat[i][j]/mat[i][i]);
if(q<sum) q=sum;
}
sum=fabs(ty[0]/mat[0][0]);
for(i=1;i<dim;i++) if(sum<fabs(ty[i]/mat[i][i])) sum=fabs(ty[i]/mat[i][i]);
sum=q*sum/(1-q);
while(fabs(sum)>err)
{
memcpy(xn_1,tx,dim*sizeof(double));
for(i=0;i<dim;i++)
{
tx[i]=ty[i]/mat[i][i];
for(j=0;j<dim;j++) if(j!=i) tx[i]-=mat[i][j]/mat[i][i]*xn_1[j];
}
sum=fabs(tx[0]-xn_1[0]);
for(i=0;i<dim;i++) if(sum<fabs(tx[i]-xn_1[i])) sum=fabs(tx[i]-xn_1[i]);
sum=sum*q/(1-q);
}
free(xn_1);
}
Prezentarea implementarii paralele
fisierul bench-omp.c
#include<stdio.h>
#include<stdlib.h>
#include<sys/time.h>
#include<string.h>
#include"timeprint.c"
#include "jacobi_omp.c"
#define numar 10
int main(int argc,char **argv)
{
struct timeval t1,t2;
double **mat,*x,*rez,*temp1,temp,*y,err;
int i,l,j,dim, thread; FILE *fp; dim=atoi(argv[1]);
y=(double *)calloc(dim,sizeof(double));
rez=(double *)calloc(dim,sizeof(double));
//here is the parallel zone
mat=(double **)calloc(dim,sizeof(double *)); temp1=(double
*)calloc(dim*dim,sizeof(double)); for(i=0;i<dim;i++)
{
mat[i]=temp1;
temp1+=dim;
}
x=(double *)calloc(dim,sizeof(double));
/* create the test matrix */ for(i=0;i<dim;i++) rez[i]=(double)i+1; for(i=0;i<dim;i++)
for(j=0;j<dim;j++)
if(i!=j)
{
}
for(i=0;i<dim;i++)
{
mat[i][j]=20000*rand()/(double)RAND_MAX;
if((rand()/(double)RAND_MAX)<0.5) mat[i][j]=-mat[i][j];
temp=0.0;
for(j=0;j<dim;j++) if(j!=i) temp+=fabs(mat[i][j]);
mat[i][i]=temp+(20000+temp)*rand()/(double)RAND_MAX+0.00001;
if((rand()/(double)RAND_MAX)<0.5) mat[i][i]=-mat[i][i];
}
//generate the free term for(i=0;i<dim;i++)
{
y[i]=0.0; x[i]=0.0;
for(j=0;j<dim;j++) y[i]+=mat[i][j]*rez[j];
}
err=atof(argv[2]); thread=atoi(argv[3]); gettimeofday(&t1,NULL);
for(l=0;l<numar;l++) jacobi_omp(mat,y,x,dim,err,thread);
gettimeofday(&t2,NULL);
for(i=0;i<dim;i++) {if(fabs(rez[i]-x[i])>1E-5) printf("%lf=%lf\n",rez[i],x[i]); fflush(stdout);}
fp=fopen("time-par.dat","a");
timeprint(t1,t2,numar,dim,fp,thread);
fclose(fp); free(*mat); free(mat); free(rez); free(y); free(x);
return 0;
}
fisierul jacobi_omp.c
/*
JACOBI OMP with diagonal ROW dominant
*/
#include<string.h>
#include<math.h>
#include<omp.h>
void jacobi_omp(double **mat,double *ty,double *tx,int dim,double err,int thread)
{
double *xn_1, q,sum,temp, *sum_p;
long i,j;
int th;
xn_1=(double *)calloc(dim,sizeof(double));
sum_p=(double *)calloc(thread,sizeof(double));
//JACOBI q=0.0; omp_set_num_threads(thread);
#pragma omp parallel private(th,i)
{
#pragma omp for for(i=0;i<dim;i++)
tx[i]=ty[i]/mat[i][i];
//compute q
#pragma omp for reduction(+:q)
for(i=1;i<dim;i++)
q+=fabs(mat[0][i]/mat[0][0]);
th=omp_get_thread_num();
sum_p[th]=q;
#pragma omp for private(temp,j)
for(i=1;i<dim;i++)
{
temp=0.0;
for(j=0;j<dim;j++) if(i!=j) temp+=fabs(mat[i][j]/mat[i][i]);
if(sum_p[th]<temp) sum_p[th]=temp;
}
#pragma omp single
{
q=sum_p[0];
for(i=1;i<thread;i++) if(q<sum_p[i]) q=sum_p[i];
}
//calcul norma infinit sum_p[th]=fabs(ty[th]/mat[th][th]); for(i=th+thread;i<dim;i=i+thread){
if(sum_p[th]<fabs(ty[i]/mat[i][i])) sum_p[th]=fabs(ty[i]/mat[i][i]);
#pragma omp barrier
#pragma omp single
{
sum=sum_p[0];
for(i=1;i<thread;i++) if(sum<sum_p[i]) sum=sum_p[i];
sum=sum*q/(1-q); //calcul conditie de oprire
}
while(fabs(sum)>err)
{
#pragma omp for for(i=0;i<dim;i++)
xn_1[i]=tx[i];
#pragma omp for private(j)
for(i=0;i<dim;i++)
{
tx[i]=ty[i]/mat[i][i];
for(j=0;j<dim;j++) if(j!=i) tx[i]-=mat[i][j]/mat[i][i]*xn_1[j];
}
//cacul norma infinit a diferentei de vectori sum_p[th]=fabs(tx[th]-xn_1[th]);
for(i=th+thread;i<dim;i=i+thread)
if(sum_p[th]<fabs(tx[i]-xn_1[i])) sum_p[th]=fabs(tx[i]-xn_1[i]);
#pragma omp barrier
#pragma omp single
{
sum=sum_p[0];
for(i=1;i<thread;i++) if(sum<sum_p[i]) sum=sum_p[i];
sum=sum*q/(1-q); //refacere conditie de oprire
}
}
}
free(xn_1);
}