Programare concurentă
pe platforme Unix, Windows, Java
|
Florian Mircea Boian |
Corina Maria Ferdean |
|
Rareş Florin Boian |
Radu Călin Dragoş |
CUPRINS
1 Nivelele prelucrărilor concurente
1.1 Procesări paralele şi clasificarea
Flynn
1.2 Granularităţi ale paralelismului /
concurenţei
1.4 Procesoare vectoriale şi sisteme cluster
1.5 Paralelism şi concurenţă la
nivelul sistemului de operare
1.6 Evaluare
multiprocesor a expresiilor complexe
1.7 Reorganizarea
succesiunilor de atribuiri
1.8 Paralelizare la nivel de cicluri for
2 Concepte abstracte utilizate în descrierea
concurenţei
2.1 Paradigme de programare
nesecvenţială
2.2 Relaţia procese - thread-uri
2.2.2 Reprezentarea în memorie a unui proces
2.3 Scheme de specificare a programelor
concurente
2.3.2 Specificare FORK-JOIN-QUIT
2.3.3 Specificare PARBEGIN-PAREND
2.4 Situaţii de excepţie generate de
concurenţă
2.5 Mecanisme de control al concurenţei,
comunicare şi sincronizare
2.5.5 Secţiune şi resursă
critică; excludere mutuală
2.5.6 Regiuni critice condiţionale
2.5.7 Conceptul de întâlnire (rendez-vouz)
2.5.8 Limbajul CSP (Communicating Sequential
Processes)
2.6 Mecanisme de control asincron sau
parţial sincron
2.6.4 Evenimente, excepţii, semnale
2.7 Probleme specifice care se rezolvă cu
ajutorul concurenţei
2.7.1 Abordare concurentă în pachete software
standard
2.7.2 Problema producătorilor şi a
consumatorilor
2.7.3 Problema cititorilor şi a scriitorilor
2.7.4 Problema celor 5 filozofi
2.7.6 Înmulţirea a două matrice
3 Programare concurentă la nivel de proces
3.1 Procese Unix,
Windows, Java
3.1.1.1 Structura unui proces Unix
3.1.1.2 Crearea proceselor UNIX. Apelul sistem fork()
3.1.1.3 Apelurile sistem exit, wait
şi waitpid
3.1.1.4 Execuţia unui program extern; apelurile
sistem exec()
3.1.2 Un contraexemplu remarcabil
3.1.3.1 Convenţii de limbaj la programarea
Windows
3.1.3.3 Crearea unui proces Windows
3.1.3.4 Terminarea unui proces Windows
3.1.3.5 Exemplu de creare proces sub Windows
3.1.4 Procese externe lansate din Java
3.2 Comunicarea prin pipe între procese
3.2.1 Enunţurile unor probleme folosite în
exemplele de comunicare
3.2.1.2 Tipărirea de propoziţii una pe linie
3.2.2 Pipe, popen şi FIFO sub Unix
3.2.3.2 Pipe cu nume sub windows
3.3 Comunicarea între procese folosind mecanismul
de memorie partajată
3.3.1 Problema foii de calcul rezolvată prin memorie
partajată
3.3.2 Memorie partajată sub Unix
3.3.2.1 Chei şi drepturi de acces
3.3.2.2 Principii, structuri şi limite
3.3.2.3 Creare, deschidere, ataşare, control
3.3.2.4 Implementarea foii de calcul sub Unix
3.3.3 Comunicarea între procese Windows prin
memorie partajată
3.3.3.1 Fişiere I/O mapate în memorie şi
zone partajate
3.3.3.2 Implementarea foii de calculsub Windows
3.4 Sincronizarea
proceselor folosind semafoare
3.4.1.1 Structura setului de semafoare Unix
3.4.1.2 Crearea unui set şi accesul la un set
existent
3.4.1.3 Operaţii asupra semafoarelor Unix
3.4.1.4 Controlul seturilor de semafoare
3.4.1.5 Exemple de utilizare a semafoarelor Unix
3.4.2 Sincronizarea proceselor prin semafoare
Windows
3.4.2.1 Semafoare cu nume şi anonime;
operaţii
3.4.2.2 Exemple de utilizare a semafoarelor Windows
3.5 Comunicarea prin cozi de mesaje
3.5.1 O problemă cu schimburi de mesaje
3.5.2 Comunicarea între procese Unix prin cozi de
mesaje
3.5.2.1 Structura unei cozi de mesaje
3.5.2.2 Acces şi operaţii asupra cozii
3.5.2.3 Exemple de utilizare a cozilor de mesaje.
3.5.3 Comunicarea între procese Windows prin
Mailslot
3.5.3.2 Programarea folosind mailslot
3.5.3.3 Exemplu de lucru cu mailslot
3.5.4 Java Message Service (JMS)
3.5.4.4 Modelul de programare API al JMS
3.5.4.5 Pregătirea pentru rularea de programe JMS
3.5.4.6 Exemple de aplicaţii punct la punct şi publicare / înscriere
4 Programare concurentă la nivel de
thread-uri
4.1.1 Contextul şi stările unui thread
4.1.2.1 O clasificare a thread-urilor
4.1.2.4 Utilizări combinate de thread-uri
4.1.3 Modele de legare thread-uri user - thread-uri
nucleu
4.1.4 Avantaje şi dezavantaje în utilizarea
thread-urilor
4.2 Exemple de probleme rezolvabile prin
thread-uri
4.2.1 Adunarea în paralel a n numere
4.2.2 Problema producătorului şi
consumatorului
4.2.3 Problema cititorilor şi a scriitorilor
4.3 Thread-uri pe platforme Unix: Posix şi
Solaris
4.3.1 Caracteristici şi comparaţii Posix
şi Solaris
4.3.1.1 Contextul şi stările unui thread
4.3.1.2 Caracteristici ale thread-urilor sub Linux
4.3.1.3 Caracteristici ale thread-urilor sub Solaris
4.3.1.4 Similarităţi şi
facilităţi specifice
4.3.2 Operaţii asupra thread-urilor: creare,
terminare
4.3.2.2 Terminarea unui thread
4.3.2.3 Aşteptarea terminării unui thread
4.3.3 Instrumente standard de sincronizare
4.3.3.1 Operaţii cu variabile mutex
4.3.3.2 Operaţii cu variabile condiţionale
4.3.3.4 Blocare de tip cititor / scriitor (reader /
writer)
4.3.5 Obiecte purtătoare de atribute Posix
4.3.5.1 Iniţializarea şi distrugerea unui
obiect atribut
4.3.5.2 Gestiunea obiectelor purtătoare de
atribute thread
4.3.5.3 Gestiunea obiectelor purtătoare de
atribute mutex
4.3.5.4 Gestiunea obiectelor purtătoare de
atribute pentru variabile condiţionale
4.3.5.5 Purtătoare de atribute pentru obiecte
partajabile reader / writer
4.3.6 Planificarea thread-urilor sub Unix
4.3.6.1 Gestiunea priorităţilor sub Posix
4.3.6.2 Gestiunea priorităţilor sub Solaris
4.3.6.3 Exemplu de planificare manuală a
thread-urilor pe Solaris
4.3.7 Facilităţi speciale ale lucrului cu
thread-uri Unix
4.3.7.1 Execuţie cel mult o dată
4.3.7.2 Asociere date specifice thread-urilor cu chei
4.3.7.3 Operaţii specifice lwp sub Solaris
4.3.8 Exemple clasice de lucru cu thread-uri
4.3.8.1 Adunarea în paralel a n numere
4.3.8.2 Problema producătorilor şi a
consumatorilor
4.3.8.3 Problema cititorilor şi a scriitorilor
4.4 Thread-uri pe platforme Microsoft: Windows
NT, 2000
4.4.1 Caracteristici ale thread-urilor sub Windows
NT
4.4.2 Operaţii asupra thread-urilor: creare,
terminare
4.4.2.2 Terminarea unui thread
4.4.3 Instrumente standard de sincronizare
4.4.3.5 Alte obiecte de sincronizare
4.4.4 Atributele şi planificarea thread-urilor
NT
4.4.4.1 Atributele thread-urilor
4.4.4.2 Priorităţile thread-urilor
4.4.5 Facilităţi speciale ale lucrului cu
thread-uri NT
4.4.5.1 Date specifice thread-urilor
4.4.5.2 Thread-uri utilizator: fibre NT
4.4.5.3 Utilizarea thread-urilor în regim
multiprocesor
4.4.6 Exemple clasice de lucru cu thread-uri
4.4.6.1 Adunarea în paralel a n numere
4.4.6.2 Problema producătorilor şi
consumatorilor
4.4.6.3 Problema cititorilor şi scriitorilor
4.5.1 Elemente de limbaj Java în contextul
thread-urilor
4.5.1.1 Obiecte versus thread-uri
4.5.2 Caracteristici ale Java Threading API
4.5.2.1 Tipuri de thread-uri Java; particularităţi
ale diverselor implementări
4.5.2.2 Stările unui thread Java
4.5.3 Operaţii asupra thread-urilor Java;
creare, terminare
4.5.3.2 Terminarea unui thread
4.5.3.3 Aşteptarea terminării unui thread
4.5.3.4 Exemple de creare / terminare thread-uri
4.5.4 Sincronizarea thread-urilor Java
4.5.4.1 Conceptul de monitor Java; synchronized
4.5.4.2 Mecanismul wait
/ notify
4.5.4.3 O schemă exemplu de sincronizări
4.5.5 Exemple clasice de lucru cu thread-uri
4.5.5.1 Adunarea în paralel a n numere
4.5.5.2 Problema producătorului şi
consumatorului
4.5.5.3 Problema cititorilor şi a scriitorilor
4.5.6 Multithreading folosind JNI
5 Aplicaţii concurente complexe
5.1
Scheme de proiectare a programelor concurente
5.2 Implementarea threadurilor NT în MFC
5.2.1 Creare şi terminare threaduri
5.2.1.1 Crearea thread-urilor folosind mecanismul MFC
5.2.1.2 Crearea thread-urilor user-interface
5.2.1.3 Crearea thread-urilor worker
5.2.1.4 Terminarea thread-urilor
5.2.2 Comunicarea şi sincronizarea
thread-urilor MFC
5.2.3.1 Un exemplu de thread user-interface
5.2.3.2 Un exemplu de thread worker
5.3 Utilizări combinate: threaduri, procese
Unix, semnale
5.3.1.1 Trei threaduri şi un proces fiu
5.3.1.2 Procese fii create din threaduri
5.3.1.3 Utilizarea funcţiei clone
5.3.2 Thread-uri Posix şi semnale Unix
5.3.2.2 Exemple cu semnale livrate procesului de
bază
5.3.2.3 Exemplu cu semnal livrat unui thread
particular
5.4 Utilizarea thread-urilor în appleturi şi
servleturi Java
5.4.1 Thread-uri în applet-uri Java
5.4.2 Thread-uri în servlet-uri Java
5.5 Aplicaţie vizuală multi-threading
sub NT
5.6 Server Java concurent pentru chat
5.7.1 Protocolul FTP (File Transfer Protocol)
5.8 Evaluarea unor performanţe ale
programelor cu thread-uri
5.8.1 Vizualizarea datelor volumetrice
5.8.3.1 Iniţializări pe diverse platforme
5.8.3.2 Generarea imaginilor pe diverse platforme
5.8.3.3 Generarea folosind diverse politici de
planificare
5.8.4 Concluzii privitoare la performanţe
Nu mai este o noutate faptul că domeniul informaticii este extrem de dinamic. Acest dinamism se materializează atât prin diversitatea şi complexitatea noilor aplicaţii, cât şi prin implementarea în pachete software a conceptelor şi a modelor clasice de programare. Paradigma programării concurente se găseşte la intersecţia dintre “clasic” şi “modern”. Astfel, primele aspecte legate de concurenţă au apărut în jurul anilor ’50 în cadrul sistemelor de operare, care ofereau facilităţi de multiprogramare. Apariţia calculatoarelor paralele şi a reţelelor de calculatoare a constituit cadrul fizic adecvat pentru utilizarea facilităţilor de concurenţă în cadrul sistemelor de operare, în mod transparent pentru clienţi.
In ultimii ani, suportul pentru concurenţă din cadrul sistemului de operare a fost extins la nivelul aplicaţiilor program. Aceasta se realizează, de exemplu, prin intermediul bibliotecilor utilizator sau prin apeluri de interfaţă la funcţionalităţile de concurenţă din sistem. Astfel, utilizatorii pot crea şi gestiona în programele proprii entităţi de execuţie care să ruleze simultan.
Lucrarea de faţă îşi propune să prezinte modalitaţile de realizare –la nivelul sistemului de operare- şi utilizare –la nivelul aplicaţiilor program- a suportului pentru implementarea unor aplicaţii concurente. Prezentarea este organizată comparativ, pe sistemele de operare Unix şi Windows, şi pe platforme Java. De ce această abordare? In primul rând pentru că sunt platformele cele mai răspândite astăzi în lume. In al doilea rând, pentru că fiecare dintre ele îşi implementează mecanisme proprii de concurenţă, definite în mod specific, dar cu respectarea unor cerinţe generale de concurenţă. In al treilea rând pentru că se relevă unele diferenţe de utilizare a programării concurente procedurale (de exemplu, în C sub Unix şi Windows) faţă de programarea concurentă orientată obiect (oferită de limbajul Java).
Capitolul 1 conţine o descriere succintă a evoluţiei prelucrărilor concurente, pornind de la nivelul hardware –calculatoare paralele, vectoriale, sisteme cluster, tehnica pipeline-, şi apoi în cadrul sistemelor de operare. Sunt descrise de asemenea modalităţi de paralelizare a expresiilor aritmetice sau a ciclurilor for din programele sursă.
Capitolul 2 prezintă, într-o manieră semi-formală, conceptele de bază necesare pentru descrierea, specificarea şi implementarea mecanismelor de concurenţă. Tot în acest capitol sunt enumerate si specificate pe scurt câteva aplicaţii concurente uzuale şi probleme specifice care se rezolvă cu ajutorul concurenţei.
Capitolul 3 detaliează noţiunea de proces. Este descrisă structura proceselor, precum şi operaţiile de creare, comnunicare şi control ale acestora pe platformele Unix, Windows şi Java.. Ca şi mecanisme de comunicare între procese sunt descrise comunicaţiile prin pipe, prin memorie partajată, prin semafoare şi prin cozi de mesaje.
Capitolul 4 abordează conceptul de thread (fir de execuţie) folosit ca entitate de bază pentru modelarea concurenţei, alternativă la procese. Capitolul debutează cu o prezentare generală a thread-urilor, exemple de probleme care se pretează la o astfel de abordare, avantaje şi dezavantaje. In continuare sunt particularizate caracteristicile şi modalităţile de utilizare ale thread-urilor sub Unix (comparativ variantele Posix şi Solaris), sub Windows şi în Java.
Capitolul 5 ilustrează utilizarea thread-urilor în combinaţie cu alte concepte şi servicii sistem şi/sau utilizator. Mai întâi se face o scurtă descriere a principalelor scheme de proiectare a programelor concurente: boss/worker, peer, pipelining. Urmează tratarea thread-urilor încapsulate în clase MFC, precum şi utilizarea de threaduri şi semnale sub Unix. Sunt apoi prezentate facilităţile de lucru cu procese şi thread-uri în aplicaţii cu un grad mai mare de complexitate: server Java de chat, client FTP concurent şi neinteractiv, vizualizarea datelor volumetrice. Capitolul se încheie cu un studiu privind performanţele aplicaţiilor cu thread-uri.
In lucrare apar foarte multe exemple. Printre cele mai importante amintim: problema producătorilor şi a consumatorilor, problema cititorilor şi a scriitorilor, însumarea în paralel a unui şir de numere, acces concurent la foi de calcul, simulări de acces sincronizat şi nesincronizat la resurse partajabile etc. Exemplele sunt implementate complet în mai multe variante, în funcţie de platformă şi de elementele de sincronizare folosite. Pentru fiecare implementare sunt prezentate programele complete scrise în C, C++ sau Java. Programele sursă sunt numerotate separat în cadrul fiecărui capitol, sub forma: Programul c.n. Intr-o anexă este prezentată lista acestor programe. Autorii au creat o arhivă cu toate sursele programelor descries în lucrare. Doritorii pot să obţină această arhivă apelând anonymous-FTP de la adresa: ftp.ubbcluj.ro. Elementele grafice care însoţesc prezentarea textului sunt numerotate în cadrul fiecărui capitol, începând de la 1, sub forma: Figura c.n. Este anexată o listă a acestor figuri.
Lucrarea se adresează în primul rând informaticienilor: studenţi, programatori, data designeri, project manageri etc. Este de asemenea utilă celor interesaţi să pătrundă în domeniul informaticii neconvenţionale, care include paradigma programării concurente.
Primul autor este profesor la Departamentul de Informatică, de la Facultatea de Matematică şi Informatică a Universităţii “Babes-Bolyai” Cluj. Ceilalţi trei autori au absolvit secţia Informatică de la aceeaşi facultate, în anii: 2000, 1998, 1999. Toţi trei au absolvit secţia de studii aprofundate “Informatică Distribuită”, în anii: 2001, 1999, 2000. In prezent, toţi trei îşi pregătesc tezele de doctorat în România/Franţa, SUA, Irlanda.
Autorii mulţumesc tuturor celor care i-au sprijinit într-un fel sau altul la elaborarea prezentei lucrări. Sunt de asemenea recunoscători tuturor cititorilor care le vor adresa sugestii, observaţii sau întrebări legate de lucrare. Adresele e-mail de contact sunt: florin@cs.ubbcluj.ro, cori@cs.ubbcluj.ro, rares@cs.ubbcluj.ro, bradu@cs.ubbcluj.ro.
Cluj-Napoca, octombrie 2001 Autorii