Embed Size (px)
Citation preview
0
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
1
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.
2
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.
3
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.
4
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
5
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.
6
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.
7
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.
8
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')
9
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
10
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)
11
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)
12
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.
13
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)
14
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
15
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
16
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
17
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
18
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]
19
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
20
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
21
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
p2
I
F
p1
p3p4
p5
22
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
p2
I
F
p1
p3p4
p5
23
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.
24
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
p2
I
F
p1
p3p4
p5
25
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
26
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>;
27
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
28
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)?
29
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 }
30
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
31
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))
32
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))
33
As facilidades de depuraçãoAs facilidades de depuração
•• debug1debug1•• debug2debug2•• nodebugnodebug•• execexec(Nome)(Nome)•• pausepause•• janelas de visualizajanelas de visualizaçãçãoo
34
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)
35
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.
36
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;
37
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
38
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
39
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;
40
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
