Programação Concorrente na Linguagem Vale 4

View
232
Download
0
Category

Documents

Preview:

Citation preview

Programação Concorrente Programação Concorrente na Linguagem Vale 4na Linguagem Vale 4

Pontifícia Universidade Católica do Rio Grande do Sul Pontifícia Universidade Católica do Rio Grande do Sul –– PUCRSPUCRSCentro Universitário Centro Universitário LaLa SalleSalle –– UNILASALLEUNILASALLE

porpor

Simão Sirineo ToscaniSimão Sirineo Toscani

VII Simpósio Brasileiro de VII Simpósio Brasileiro de Linguagens de ProgramaçãoLinguagens de Programação

SBLP 2003SBLP 2003Ouro PretoOuro Preto, MG, , MG, BrasilBrasil

Introdução (1)Introdução (1)

• Iremos apresentar• Uma linguagem de programação para uso acadêmico• Construída usando software livre (SWI-Prolog)• Que pode ser instalada em qualquer microcomputador• Os exemplos são programas completos, prontos para

serem executados.

• O ambiente de programação V4É formado por• um compilador• uma máquina virtual

Trata-se de um ambiente completo para construção e depuração de programas concorrentes.

Introdução (2)Introdução (2)

Programa concorrenteÉ um programa que origina processos concorrentes (paralelos) durante sua execução. Estes processos interagem através de mecanismos apropriados, normalmente implementados no kernel do SO.

• A técnica da programação concorrente foi usada originalmente na construção de sistemas operacionais.

• Hoje em dia seu uso está difundido em todas as áreas.

Motivação para a criação da linguagem (1)Motivação para a criação da linguagem (1)

• Os profissionais da computação devem dominar as técnicas e ferramentas usadas na construção de programas concorrentes.

• Não há uma linguagem adequada para esse tipo de ensino.

• O ideal seria que o estudante pudesse aprender a solucionar os problemas clássicos usando todas as ferramentas descritas na literatura.

Motivação para a criação da linguagem (2)Motivação para a criação da linguagem (2)

• Os problemas clássicos:1. Produtor-consumidor (relação de cooperação)2. Jantar dos filósofos (relação de competição)3. Barbeiro dorminhoco (relação cliente-servidor)4. Leitores e escritores (situação comum em banco de dados)

• As principais ferramentas:1. Semáforos2. Monitores3. Operações send e receive4. Rendezvous

A linguagem Vale 4A linguagem Vale 4

• Implementa quase todas as ferramentas e paradigmas da programação concorrente

• Sintaxe simples(*) e semântica clara• Facilidades para depuração (visualização da

execução)• É implementada por

• um compilador• uma máquina virtual

(*) Baseada na sintaxe “livre” usada nas notas de aula do autor.

O compilador V4O compilador V4

•• TraduTraduçãção dirigida por sintaxe.o dirigida por sintaxe.

•• O resultado da compilaO resultado da compilaçãção o éé::•• Uma tabela de sUma tabela de síímbolos (TS) embolos (TS) e

•• Um cUm cóódigo de mdigo de mááquina virtual.quina virtual.

O simulador V4O simulador V4

• A partir da TS, o simulador da máquina virtual gera estruturas e faz a execução do código.

• Estruturas de dados:• Variáveis inteiras, variáveis booleanas• Arrays de até duas dimensões• Registros descritores de processos • Filas, semáforos• Filas de monitores, variáveis tipo condition• Filas de espera para rendezvouz, etc.

O ambiente de execução V4O ambiente de execução V4

O compilador:O compilador:repeat,repeat,

leToken(X),leToken(X),colocaNaPilhacolocaNaPilha(X),(X),trataPilhatrataPilha

until until X = X = ‘‘endprogramendprogram’’

O simulador:O simulador:gera estruturas de dados,gera estruturas de dados,repeat,repeat,

selecionaThread(T),selecionaThread(T),if T>0if T>0 thenthen executa Texecuta T

untiluntil T = T = --1,1,writewrite('FIM DA EXECU('FIM DA EXECUÇÃÇÃO')O')

OsOs tokenstokens da linguagem V4da linguagem V4

:= : ; , ( ) [ ] { } ' + - * / mod& and | or ¬ not % /* */ integer boolean init queue semaphore array procedure returns while do forever if then elseloop endloop exit when inline process task thread fork join quit mutexbegin mutexend block wakeup P V yield hold monitorcondition priority wait signal initially empty count first insert send receive entry accept read write nl tab debug1 debug2 nodebug pausenothing myself getId random clockTime endidentificadores const_inteiras const_booleanas

Os comandos da linguagemOs comandos da linguagem•• Var := EA • P ( Sem )• if EL then C1 else C2 • V ( Sem )• while EL do C • yield• do forever C • hold ( Time )• loop C1; C2; ... ; Cn endloop • wait ( Cond )• { C1; C2; ... ; Cn } • wait ( Cond , Prior )• read ( Var ) • signal ( Cond )• write ( Var ) • send ( ProcessId, Msg )• nl • nb_send ( ProcessId, Msg )• tab ( K ) • receive ( ProcessId, Msg )• nothing • id := fork• mutexbegin • id := new Pname ( arg1, arg2, ..., argN)• mutexend • join ( id )• lock • quit• unlock • debug1• insert ( id , Q ) • debug2• insert ( id , Q, Prior ) • nodebug• id := first ( Q ) • pause• block • exec ( Nome )• wakeup ( id ) (Total de 40• accept Et ( arg1:T1; arg2:T2; ... ; argN:TN ) returns T when EL do C comandos)

As instruções da máquina virtualAs instruções da máquina virtualcall NomeProc[n, lista]returnnothingyieldholdforkjoinquitmutexbeginmutexendblockwakeup Pfirst Qinsert P , Qis_empty Qcount Q

if X oprel Y goto Egoto E read Xwrite Xpush Xpop Xaddsubmultdivmodjump Ejzer Ejpos Ejneg Ejsub Eret

P SV Sentermonitor Mleavemonitor Mwait Cwait C, Priorsignal Crndzvs Entryaccept Entrygive_up_rndzvssend Id,Msgreceive Id,Msgend procedend processend monitorend taskend accept

myselfgetId PclockTimerandom Nnltab Xdebug1debug2nodebugpauseexec X

(Total de 62instruções)

As versões da linguagemAs versões da linguagem

Didaticamente, a linguagem oferece 6 versões:V40 : processos, variáveis globais e procedimentos

V41 : V40 com operações mutexbegin/mutexend e block/wakeup(p)

V42 : V40 com semáforos

V43 : V40 com monitores

V44 : processos com operações send/receive

V45 : tasks com threads e rendezvous.

Formas de criar processosFormas de criar processos

• Especificação de processos individuais

• Especificação de array de processos

• Especificação de modelo (template) de processo

(Nos dois primeiros casos, a criação é estática)

Especificação de processos (1)Especificação de processos (1)% Especificação individualV4program

process p;k: integer init 0;while k < 10 do { write(1);

k:= k+1};process q; k: integer init 0;while k < 10 do{ write(2);

k:= k+1}

endprogram

Especificação de processos (2)Especificação de processos (2)

% Array de processosV4program

process p(i:= 1 to 2);k: integer init 0;while k < 10 do { write(i);

k:= k+1}

endprogram

Especificação de processos (3)Especificação de processos (3)

% Modelo de processoV4program

process type p(i: integer);k: integer init 0;while k < 10 do { write(i);

k:= k+1};process qqnome; { new p(1);

new p(2)}

endprogram

Uso de um procedimentoUso de um procedimento

% Especificação individual e uso de procedimentoV4program

procedure imprime(n: integer);k: integer init 0;while k < 10 do { write(n);

k:= k+1};process p; imprime(1);process q; imprime(2)

endprogram

Código gerado para o programa anteriorCódigo gerado para o programa anterior============== TABELA DE SIMBOLOS ==============IND NOME TIPO V_INIC AGRUP INSIDE0 imprime routine 0 n_arg(1) global 1 n integer 0 none proced(imprime)2 k integer 0 none proced(imprime)3 p process 9 none global4 q process 12 none global

END CÓDIGO GERADO0 [if,#(2),<,$10,goto,2]1 [return]2 [write, #(1)]3 [push, #(2)] 9 [call, imprime] 4 [push, $1] 10 [1, 1]5 [add] 11 [end, process]6 [pop, #(2)] 12 [call, imprime]7 [goto, 0] 13 [1, 2]8 [end, proced] 14 [end, process]

O mesmo programa anteriorO mesmo programa anterior

% A identificação única (pid)V4program

procedure imprime(n: integer);k: integer init 0;while k < 10 do { write(n);

k:= k+1};process p; imprime(myself);process q; imprime(myself)

endprogram

Ainda o mesmo programaAinda o mesmo programa

% Criação de threads% (qual o resulado da execução?)V4program

process p;k, id: integer init 0;{ id:= fork();

while k < 10 do { write(myself);

k:= k+1}

}endprogram

Grafo de fluxo de processos com Grafo de fluxo de processos com blockblock//wakeupwakeup(p)(p)

V4programprocess P1; { nl; write('p1');

wakeup(P3); wakeup(P4); quit }; process P2; { nl; write('p2');

wakeup(P5); quit }; process P3; { block;

nl; write('p3');wakeup(P5); quit };

process P4; { block;nl; write('p4');wakeup(P5); quit };

process P5; { block; block; block;nl; write('p5'); quit }

endprogram

p3p4

Grafo de fluxo de processos com Grafo de fluxo de processos com threadsthreadsV4program

process p; k2, k4 : integer;{ k2:= fork;

if myself = k2 then {nl; write('p2'); quit};nl; write('p1');k4:= fork;if myself = k4 then {nl; write('p4'); quit};nl; write('p3');join(k2);join(k4);nl; write('p5')

}endprogram

p3p4

Variáveis semáforasVariáveis semáforas

• São variáveis especiais, sobre as quais só podem ser aplicadas duas operações: P e V (Proberen e Verhogen).

• Um semáforo é implementado por um contador (variável inteira) e uma fila de espera.

• Sendo S um semáforo, as operações P e V funcionam da seguinte maneira:P(S): Testa o contador de S; se é zero, coloca o processo na fila de espera (bloqueia o processo); caso contráriodecrementa o contador de 1.V(S): Testa a fila de S; se está vazia, incrementa o contador de 1; caso contrário libera (desbloqueia) o primeiro processo da fila de espera.

Grafo de fluxo de processos com semáforosGrafo de fluxo de processos com semáforos

V4programS3, S4, S5: semaphore initial 0;process P1; { nl; write('p1');

V(S3); V(S4) }; process P2; { nl; write('p2');

V(S5) }; process P3; { P(S3);

nl; write('p3'); V(S5) };

process P4; { P(S4); ; nl; write('p4'); V(S5) };

process P5; { P(S5); P(S5); P(S5);nl; write('p5') }

endprogram

p3p4

O jantar dos filósofos com semáforosO jantar dos filósofos com semáforosV4program

garfo : array[5] of semaphore init 1;process filosofo(i:= 1 to 5); j, k, t: integer;while k =< 10 do{ if i = 1 then { P(garfo[5]); P(garfo[1])}

else {j:= i-1; P(garfo[j]); P(garfo[i])};nl; write('filosofo '); write(i);write(' comecou a comer'); t:=random(5); hold(t);if i=1 then { V(garfo[5]); V(garfo[1])}else {j := i-1 ; P(garfo[j]); P(garfo[i])};nl; write('filosofo '); write(i);write(' parou de comer');k:=k+1

}endprogram

garfo 5 filósofo 1 filósofo 5

garfo 1 garfo 4

filósofo 2 filósofo 4

garfo 2 garfo 3

filósofo 3

spaghetti

Formato de um monitorFormato de um monitormonitor <nome>;| ---------------------------------------------------------------------------------------| | Declaração dos dados compartilhados pelos processos. Exemplo: || | X, Y: integer || | C, D: condition; || ----------------------------------------------------------------------------------------| procedure P(arg1: T1,...,argP: TP);| Declaração das variáveis locais de P;| { . . .| wait(D);| . . .| };| procedure Q(arg1: T1,...,argQ: TQ);| Declaração das variáveis locais de Q;| { . . .| signal(C);| . . .| };| initially {Comandos} % inicialização dos dados (opcional)end <nome>;

O jantar dos filósofos com monitoresO jantar dos filósofos com monitoresV4program

monitor garfos;gLivre: array[5] of integer init 2; ok: array[5] of condition;procedure pega(i:integer);j: integer; k: integer;

{ if gLivre[i] < 2 then wait(ok[i]); j := i-1; if j=0 then j:=5; gLivre[j]:= gLivre[j]-1;k := i+1; if k=6 then k:=1; gLivre[k]:=gLivre[k]-1

};procedure libera(i:integer);j: integer; k: integer;

{ j := i-1; if j=0 then j:=5; gLivre[j]:= gLivre[j]+1; k := i+1; if k=6 then k:=1; gLivre[k]:=gLivre[k]+1; if gLivre[j] = 2 then signal(ok[j]);if gLivre[k] = 2 then signal(ok[k])

} end monitor;

process filosofo(i:=1 to 5); k, t: integer init 0;while k =< 10 do{ garfos.pega(i);

nl; write('filos '); write(i); write(' comendo');t:= random(5); hold(t); % come 0-4 u.t.garfos.libera(i);nl; write('filos '); write(i); write(' pensando');t:= random(5)+6; hold(t); % pensa 6-10 u.t.k:= k+1

}endprogram

Alocação de um recurso de N unidadesAlocação de um recurso de N unidades

V4programmonitor resource;

N: integer init 10; % 10 unidadesC: condition;procedure requisita(k: integer);{ loop

if k =< N then exit;wait(C)

endloop;N := N-k; signal(C)

};procedure libera(k: integer);{ N := N+k; signal(C)}

end resource;

process cliente(i:=1 to 10); { resource.requisita(i);

nl; write('cliente '); write(i);resource.libera(i)

} endprogram

O que acontece se, no procedimento requisita,o signal(C) é colocado logo após o wait(C)?

Formato de uma Formato de uma tasktask

task nome isdeclaração de variáveis;declaração de entries;declaração de procedures;

thread main is{ C1; C2; …; Cn }

end nome

Formato do comando accept:

accept Et (arg1:T1; arg2:T2; ... ; argN:TN) returns T

when expressão_lógica do { C1; C2; …; Cn }

Alocação de um recurso de N unidadesAlocação de um recurso de N unidades

V4programtask resource is

entry requisita(k: integer);entry libera(k: integer);id: integer;N: integer init 10; % recurso tem 10 unidades

thread main is{ id:= fork;

if id = myself then loop % --- thread filha

accept requisita(k: integer) when k <= N do N:= N-k

endloopelse loop % --- thread mãe

accept libera(k: integer) do N:= N+kendloop

}end resource;

process cliente(i:=1 to 10); { resource.requisita(i);

nl; write('cliente '); write(i);resource.libera(i)

} endprogram

As operações As operações sendsend e e receivereceive

•• sendsend(p, (p, msgmsg))

•• receivereceive(q,(q, msgmsg))

•• receivereceive((anyany, , msgmsg))

•• nbnb__sendsend(p, (p, msgmsg))

Comunicação via Comunicação via forkfork, , joinjoin e e quitquit

•• id:= id:= forkfork•• quitquit•• joinjoin(id)(id)

•• quitquit(Valor)(Valor)•• var:= var:= joinjoin(id)(id)•• var:=var:= joinjoin((anyany))

As facilidades de depuraçãoAs facilidades de depuração

•• debug1debug1•• debug2debug2•• nodebugnodebug•• execexec(Nome)(Nome)•• pausepause•• janelas de visualizajanelas de visualizaçãçãoo

Conclusão (1) Conclusão (1)

Instalação do sistema:• Criar a pasta (diretório) “Vale4”

• Fazer download do SWI-Prolog (programa de instalação) a partir do site:http://www.swi-prolog.org/

3. Instalar o SWI-Prolog na pasta “Vale4” (a instalação vai criar o diretório “pl”)

4. Copiar os arquivos V4compiler, V4_1 e V4_2 e programas exemplos para a pasta “Vale4”.

(O sistema é colocado em uso com dois clicks no arquivo V4compiler)

Conclusão (2)Conclusão (2)

•• O sistema está operacional. O sistema está operacional. •• Sua instalação é muito simples.Sua instalação é muito simples.•• V4 é uma ferramenta para treinamento V4 é uma ferramenta para treinamento

(ensino/aprendizagem).(ensino/aprendizagem).•• Não é linguagem para produção de software (não há Não é linguagem para produção de software (não há

preocupação com geração de código otimizado, tampouco preocupação com geração de código otimizado, tampouco com eficiência de execução).com eficiência de execução).

•• A linguagem é usada para ilustrar o livro “Programação A linguagem é usada para ilustrar o livro “Programação Concorrente e Sistemas Operacionais” que será lançado Concorrente e Sistemas Operacionais” que será lançado em breve.em breve.

Barbeiro dorminhoco (Barbeiro dorminhoco (tasktask e e threadsthreads))V4program

task barbershop isk, t, id1, id2: integer;empty_chair: boolean;#chairs: integer initial 3;entry client_in(id: integer);procedure avail_chair() returns boolean;{ mutexbegin;

if #chairs > 0 then { #chairs:= #chairs-1;avail_chair:= true }

else avail_chair:= false;mutexend

};thread main is{ id1:= fork;

if id1 = myself then loop % loop da thread barbeiro

accept client_in(id: integer) do % dorme se não há cliente{ nl; write('client '); write(id);

write(' at time '); write(clockTime);hold(2); #chairs:= #chairs+1 }

endloop;

Barbeiro dorminhoco (continuação)Barbeiro dorminhoco (continuação)loop % thread main gera 20 clientes

id2:= fork;if id2 = myself then { empty_chair:= avail_chair();

if empty_chair then client_in(id2);quit };

t:= random(6); hold(t); % espera um tempo entre 0 e 5 u.t. (média 2.5)k:= k+1;exit when k=20

endloop }

end barbershopend program

Busca do elemento máximo de um vetor por divisão e conquistaBusca do elemento máximo de um vetor por divisão e conquista

V4programtask xmax is

vet: array[10] of integer;Imax: integer init 0; % Índice do maior elemento do vetorprocedure getmax(i:integer; j:integer) returns integer;dif, m, m1, id1, id2, max1, max2: integer;{ dif:=j-i;

if dif=0 then getmax:=ielse if dif=1 then if vet[i]>vet[j] then getmax:=i else getmax:=j

else { m:=(i+j)/2; m1:=m+1;id1:=fork;if id1=myself then {max1:=getmax(i,m); quit};id2:=fork;if id2=myself then {max2:=getmax(m1,j);quit};join(id1); join(id2);if vet[max1] > vet[max2] then getmax:=max1else getmax:=max2

}};thread main is{ vet[1]:=1; vet[2]:=10; vet[3]:=3; vet[4]:=100; vet[5]:=2;

Imax:=getmax(1,5); nl; write('Vobtido = '); write(vet[Imax])}

end xmaxend program

Monitor para o problema dos Monitor para o problema dos readers readers & & writerswritersmonitor ReadersAndWriters;

#readers: integer initial 0;activeWriter: boolean initial false;okToRead, okToWrite: condition;procedure startRead();{ if activeWriter or ¬empty(okToWrite) then wait(okToRead);

#readers:=#readers+1; signal(okToRead)};procedure endRead();{ #readers:=#readers-1; if #readers=0 then signal(okToWrite)};procedure startWrite();{ if #readers>0 or activeWriter then wait(okToWrite);

activeWriter:=true};procedure endWrite();{ activeWriter:=false;

if ¬empty(okToRead) then signal(okToRead)else signal(okToWrite)

}end ReadersAndWriters;

ProdutoresProdutores--consumidores com semáforosconsumidores com semáforosV4program

buffer: array[2] of integer init 0;cheios: semaphore init 0;vazios: semaphore init 2;mutex : semaphore init 1;in,out: integer init 1;process produtor(i:=0 to 1); nextpar: integer init 0;nextimpar: integer init 1;while nextimpar < 20 & nextpar < 20 do{ P(vazios) ;

P(mutex);if i = 0 then { nextpar:= nextpar + 2;

buffer[in]:= nextpar }else { nextimpar:= nextimpar + 2;

buffer[in]:= nextimpar };in:=(in mod 2)+1;

V(mutex);V(cheios)

};

process consumidor(i:=1 to 2); msg: integer; do forever{ P(cheios);

P(mutex);msg:= buffer[out];out:=(out mod 2)+1;

V(mutex);V(vazios);nl; if i = 2 then tab(10);write(msg)

}endprogram

Recommended