Pagina documente » Informatica, Matematica » Sisteme concurente. Evolutia concurentei la nivelul limbajelor de programare

Despre lucrare

lucrare-licenta-sisteme-concurente.-evolutia-concurentei-la-nivelul-limbajelor-de-programare
Aceasta lucrare poate fi descarcata doar daca ai statut PREMIUM si are scop consultativ. Pentru a descarca aceasta lucrare trebuie sa fii utilizator inregistrat.
lucrare-licenta-sisteme-concurente.-evolutia-concurentei-la-nivelul-limbajelor-de-programare


Cuprins

CUPRINS
INTRODUCERE 1
PARTEA I SISTEME CONCURENTE 5
1. EVOLUTIA SISTEMELOR DE CALCUL. APARITIA CARACTERISTICILOR SISTEMELOR CONCURENTE 5
2.ARHITECTURI DE SISTEME CONCURENTE 6
2.1.Clasificarea data de Flynn pentru sistemele de calcul 7
2.2.O clasificare a sistemelor concurente 9
2.2.1.Sisteme inerent concurente 10
2.2.1.1.Sisteme in timp real 10
2.2.1.2.Sisteme de gestiune a bazelor de date si de prelucrare a tranzactiilor 12
2.2.1.3.Sisteme de operare si sisteme de operare distribuite 13
2.2.2.Servere de informare 15
2.2.3.Aplicatii potential concurente 16
2.2.3.1.Replicarea codului. Partitionarea datelor 17
2.2.3.2.Prelucrarea datelor in pipeline 18
2.2.3.3.Algoritmi cu structura arborescenta a spatiului de solutii 18
2.2.3.4.Partajarea datelor 19
2.2.4.Cerinte pentru realizarea aplicatiilor concurente 19
2.3.O alta clasificare a sistemelor concurente 19
3.O DEFINITIE A SISTEMULUI CONCURENT 21
3.1.Proprietatile de atomicitate si granularitate 22
3.2.Proprietatile de siguranta si vivacitate 24
4. ABORDARI COMPARATIVE PENTRU PARADIGMELE: CONCURENT, PARALEL, DISTRIBUIT 24
5.CONCURENTA iN SISTEME DISTRIBUITE 26
PARTEA A II A IMPLEMENTAREA SISTEMELOR CONCURENTE 29
6.PROCESE. FIRE DE EXECUTIE 29
6.1.Conceptul de proces 29
6.1.1.Relatii intre procese 30
6.1.2.Starile unui proces 31
6.1.3.Operatii cu procese 32
6.2.Procese multi-thread 34
6.3.Rolul proceselor in implementarea sistemelor concurente 35
7. EVOLUTIA CONCURENTEI LA NIVELUL LIMBAJELOR DE PROGRAMARE 36
7.1.Concurenta la nivelul limbajelor de programare secventiale 37
7.2.Corutine 38
7.3.Paranteze pentru executie nesecventiala 39
7.4.Suportul proceselor pentru caracterizarea concurentei 40
7.5.Tipuri de threaduri 42
8. PROBLEMATICA CONCURENTEI 44
8.1.Interactiunea proceselor 44
8.1.1.Localizarea proceselor in functie de structura soft a sistemului 45
8.1.2.Cerinte pentru interactiunea proceselor 47
8.2.Comunicarea si sincronizarea in sisteme concurente 49
8.2.1.Comunicarea datelor in sisteme concurente 49
8.2.2.Sincronizarea proceselor in sisteme concurente 50
8.3.Excluderea reciproca 51
8.4.Interblocarea 53
9. PRIMITIVE PENTRU IMPLEMENTAREA CONCURENTEI. MECANISME IPC 54
9.1.Primitive low - level pentru sincronizare 57
9.1.1.Sincronizarea proceselor la nivel de eveniment 588
9.1.2.Sincronizarea pentru acces exclusiv la zone partajate 58
9.1.3.Rezolvarea excluderii mutuale folosind arbitrajul memoriei comune 59
9.1.4.Tipul de date semafor. Facilitati si limite 60
9.2.Primitive de limbaj pentru cazul memoriei partajate 63
9.2.1.Monitoare 64
9.2.2.Excludere pe obiect 65
9.2.3.Sincronizarea la nivelul operatiilor 65
9.2.3.1.Expresii de tip cale 66
9.2.3.2.Obiecte active 66
9.3.Primitive de limbaj fara partajarea memoriei. Transmiterea de mesaje 67
9.3.1.Transmiterea asincrona de mesaje 69
9.3.1.1.Comunicarea prin porturi si canale 71
9.3.1.2.Broadcast si multicast 72
9.3.1.3.Primitive de cerere. Primitive de raspuns 73
9.3.2.Transmiterea sincrona de mesaje 74
9.3.2.1.Invocarea la distanta. Mecanismul rendez-vous 75
9.3.3.Implementarea transmiterii de mesaje 77
9.3.3.1.Canalele occam pentru comunicare sincrona 77
9.3.3.2.Abstractizarea Linda 78
9.3.3.3.Sockets 78
9.4.Suportul Java pentru concurenta 79
10.PROBLEME CLASICE DE CONCURENTA 81
10.1.Problema adunarii concurente 82
10.2.Problema PRODUCATOR-CONSUMATOR 83
10.2.1.Rezolvarea cu semafoare 83
10.2.2.Rezolvarea cu monitoare 85
10.2.3.Rezolvarea cu obiecte active 86
10.3.Problema CITITOR-SCRIITOR 87
10.3.1.Rezolvarea cu semafoare 88
10.3.2.Rezolvarea cu regiuni critice conditionate 90
10.3.3.Rezolvarea cu monitoare 911
10.4.Alte probleme clasice de concurenta 92
LISTA FIGURILOR ------------------------------------------------------------------- 94
BIBLIOGRAFIE ---------------------------------------------------------------------- 95

EXTRAS DIN DOCUMENT

?SISTEME CONCURENTE

{p}

?

INTRODUCERE

Referatul de fata isi propune o abordare generala a tematicii sistemelor concurente, in contextul modern al dezvoltarii sistemelor nesecventiale (paralele, concurente, distribuite). Marea amploare pe care a luat-o dezvoltarea aplicatiilor distribuite in ultimul deceniu ne indreptateste sa consideram aceasta tema de actualitate si de interes pentru cercetarea romaneasca.

Din punct de vedere logic, referatul face parte din stagiul de pregatire pentru elaborarea lucrarii de doctorat care isi propune sa introduca un model formal pentru aplicatii nesecventiale. Acest prim referat este precedat de trei examene cu temele: limbaje formale, paradigme ale programarii (paralel, concurent, distribuit), sisteme distribuite si va fi urmat de un referat care va trata aspecte referitoare la modelarea sistemelor nesecventiale.

Din punct de vedere structural, referatul este organizat in doua parti:

Partea I SISTEME CONCURENTE;

Partea a II-a IMPLEMENTAREA SISTEMELOR CONCURENTE.

Partea intai abordeaza nivelul fizic al sistemelor concurente de o maniera bottom-up. Astfel, primele paragrafe introduc mai multe clasificari ale sistemelor concurente, impreuna cu exemple de sisteme nesecventiale pentru tipologiile introduse. O data facuta legatura cu aplicabilitatea acestor tipuri de sisteme, in capitolul al treilea am propus o definitie a sistemelor concurente. Aceasta definitie este completata in capitolele urmatoare de integrarea concurentei in tematica generala a sistemelor nesecventiale (paralele, concurente, distribuite). Din capitolul al patrulea trebuie remarcata diversitatea opiniilor in ceea ce priveste delimitarea celor trei concepte: paralel, concurent, distribuit.

Partea a doua abordeaza nivelul logic al sistemelor concurente, introducand o serie de mecanisme specifice de implementare a aplicatiilor concurente, mecanismele de comunicare intre procese (IPC). Partea centrala este capitolul opt care ia in discutie principalele caracteristici ale concurentei, dezvoltate si detaliate in capitolele urmatoare. Astfel, mecanismele IPC sunt descrise la cele trei nivele fundamentale: (1) low-level, (2) mecanisme bazate pe partajarea memoriei si (3) transmitere de mesaje (mecanisme fara partajarea memoriei).

In capitolul al zecelea sunt enuntate o serie de probleme clasice (specifice) de concurenta. Dintre acestea, cele mai reprezentative sunt tratate in detaliu: problema adunarii concurente, problema producator-consumator si problema cititor-scriitor.

partea i

sisteme concurente

1. EVOLUTIA SISTEMELOR DE CALCUL. APARITIA CARACTERISTICILOR SISTEMELOR CONCURENTE

Originea problematicii programarii concurente se regaseste la inceputul anilor ’80. Dar, inainte de aceasta, se poate vorbi de aspecte concurente la nivelul sistemului de operare, mai ales odata cu aparitia calculatoarelor paralele si a retelelor de calculatoare.

Cronologic vorbind, primele „simptome” de concurenta s-au manifestat la inceputul anilor ’50, odata cu aparitia sistemelor seriale cu multiprogramare. Acestea au adus nou: (a) tehnica polling (prin care procesorul poate sonda periodic starea perifericelor), (b) lucrul cu intreruperi, (c) canalul de intrare- iesire (un procesor specializat pe efectuarea operatiilor de intrare- iesire) care poate lucra in paralel cu procesorul central.

Aceste mecanisme au permis introducerea unor tehnici noi de exploatare eficienta a unitatii centrale de prelucrare. Dintre acestea, s-au remarcat utilizarea zonelor de memorie de tip tampon (buffers) si dezvoltarea tehnicii spooling. Bufferele de memorie aveau rolul de a regla diferenta de viteza intre perifericele lente si procesoarele rapide. Tehnica spooling (Simultaneous Peripheral Operation On-Line) se refera pe de o parte la posibilitatea citirii in avans a programelor si pe de alta parte la posibilitatea afisarii asincrone a rezultatelor. Aceste doua directii evidentiau un aspect nou de paralelism, concretizat in posibilitatea suprapunerii in timp a executiei operatiilor de intrare- iesire si a calculelor aritmetice si logice.

Ca o extensie a sistemelor cu multiprogramare s-au impus sistemele interactive si sistemele multitasking. Principalele caracteristici specifice sistemelor interactive sunt: (a) tehnica de deservire a cererilor utilizatorilor in timp partajat (time-sharing), (b) redirectarea si (c) legarea in pipe.

Urmatoarea etapa a fost dezvoltarea sistemelor multiprocesor si a sistemelor multicalculator. Un sistem multiprocesor rezulta din interconectarea a doua sau mai multor procesoare cu memorii si echipament de intrare- iesire comune. Intr-un sistem multicalculator, calculatoarele sunt interconectate intre ele prin linii de comunicare formand o retea de calculatoare. Intr-o retea avem mai multe calculatoare autonome (independente) care pot sau nu sa comunice fiecare cu fiecare. Comparativ cu organizarea unei retele de calculatoare, un sistem multiprocesor este controlat de un acelasi sistem de operare, care asigura interconexiunea intre procesoare si toate componentele care concura la realizarea sarcinilor.

Daca doua sau mai multe calculatoare sau procesoare coopereaza intr?o maniera oarecare atunci putem spune ca totalitatea resurselor lor formeaza un sistem distribuit. De aici sistemele multicalculator, retelele de calculatoare si si sistemele multiprocesor apar ca si cazuri particulare de sisteme distribuite. Retelele locale sunt apreciate ca cele mai adecvate si raspandite organizari fizice pentru sistemele cu prelucrare distribuita.

Exista numeroase asemanari intre sistemele multiprocesor si sistemele multicalculator. Cele mai multe asemanari rezulta din faptul ca ambele tipuri de sisteme suporta operatii efectuate paralel si/sau concurent.

2. arhitecturi de sisteme concurente

In acest paragraf ne vom opri asupra unor clasificari ale sistemelor de calcul in general si ale sistemelor concurente, in special.

O proprietate specifica sistemelor paralele si concurente este granularitatea — care reprezinta numarul de procesoare din sistemul respectiv [Braunl, 1993]. Un sistem cu granularitate fina, fine-grained, contine procesoare multe si nu foarte puternice. Daca proprietatea se refera la o aplicatie paralela sau concurenta, atunci granularitatea masoara numarul de procese, respectiv numarul de operatii elementare asociate unui proces. Astfel, o aplicatie paralela de granularitate fina va lucra cu multe procese, fiecare continand putine operatii elementare.

La nivelele inferioare, low-levels, paralelismul este mai mult fine-grained, in timp ce la nivelele superioare este coarse-grained.

Fiecare nivel lucreaza cu aspecte diferite ale procesului de paralelizare. Metodele si constructorii de la un nivel au aplicabilitate limitata la acel nivel si, in general, nu se pot aplica la alte nivele.

In tabela urmatoare [Braunl, 1993] punem in evidenta patru nivele de abstractizare pentru abordarea conceptului de paralelism. Dintre aceste nivele se remarca nivelul procedura, care corespunde paralelismului asincron, de tip coarse-grained si nivelul expresie, care corespunde paralelismului sincron, de tip fine-grained.

Un element important in tratarea fiecarui nivel este entitatea de calcul care prelucreaza datele. De acest element depinde ulterior programarea aplicatiei pe baza careia functioneaza sistemul paralel respectiv.

Nivelul program. La acest nivel se executa simultan programe complete, cosiderate indivizibile. Calculatorul nu trebuie sa fie unul paralel, dar sistemul de operare trebuie sa fie multitasking, de exemplu implementat in time-sharing.

Nivelul procedura. La acest nivel, sectiuni diferite ale aceluiasi program sunt executate in paralel. Aceste secvente de program in executie sunt numite procese si corespund procedurilor din calculul secvential. La acest nivel problemele sunt impartite in subprobleme, care au intre ele un grad mare de independenta, astfel incat sa se minimizeze schimbul de date intre procese.

Nivel

Entitatea elementara de prelucrare

Exemple de sisteme

Program

Job, task

SO multitasking

Sisteme in timp partajat

Procedura

Proces

MIMD

Expresie

Instructiune

SIMD

Bit

Instructiune interna

SC von Neumann

Tabel 1. Nivele de paralelism