Sop Progconctext

PROGRAMAO CONCORRENTE
A programao concorrente foi usada inicialmente na construo de sistemas operacionais.

Atualmente,elausadaparadesenvolveraplicaesemtodasasreasdacomputao.Estetipo
deprogramaotornouseaindamaisimportantecomoadventodossistemasdistribudosedas
mquinascomarquiteturaparalela.Nestecaptuloseroapresentadososconceitosbsicoseos
mecanismosclssicosdaprogramaoconcorrente.Maioresdetalhespodemserencontradosno
livro[TOS03].
1 Definio
A grande maioria dos programas escritos so programas seqenciais. Nesse caso, existe
somenteumfluxodecontrole(fluxodeexecuo,linhadeexecuo,thread)noprograma.Isso
permite,porexemplo,queoprogramadorrealizeuma"execuoimaginria"deseuprograma
apontandocomodedo,acadainstante,ocomandoqueestsendoexecutadanomomento.
Um programaconcorrente podeservistocomosetivessevriosfluxosdeexecuo.
Paraoprogramadorrealizaragorauma"execuoimaginria",elevainecessitardevriosdedos,
umparacadafluxodecontrole.
O termo "programao concorrente" vem do ingls concurrent programming, onde
concurrent significa "acontecendo ao mesmo tempo". Uma traduo mais adequada seria
programao concomitante. Entretanto, otermo programao concorrente jestsolidamente
estabelecidonoBrasil.Algumasvezesusadootermo programaoparalela comomesmo
sentido.
comum em sistemas multiusurio que um mesmo programa seja executado
simultaneamente por vrios usurios. Por exemplo, um editor de texto. Entretanto, ter 10
execuessimultneasdoeditordetextonofazdeleumprogramaconcorrente.Oquesetem
so10processosindependentesexecutandoomesmoprogramaseqencial(compartilhandoo
mesmo cdigo). Cada processo tem a sua rea de dados e ignora a existncia das outras
execuesdoprograma.Essesprocessosnointeragementresi(notrocaminformaes).Um
programaconsideradoconcorrentequandoele(oprprioprograma,duranteasuaexecuo)
originadiferentesprocessos.Essesprocessos,emgeral,irointeragirentresi.
2 Motivao
A programao concorrente mais complexa que a programao seqencial. Um programa
concorrentepodeapresentartodosostiposdeerrosqueaparecemnosprogramasseqenciaise,
adicionalmente,oserrosassociadoscomasinteraesentreosprocessos.Muitoserrosdependem
doexatoinstantedetempoemqueoescalonadordosistemaoperacionalrealizaumchaveamento
decontexto.Issotornamuitoserrosdifceisdereproduziredeidentificar.
Apesar da maior complexidade, existem muitas reas nas quais a programao
concorrentevantajosa.Emsistemasnosquaisexistemvriosprocessadores(mquinasparalelas
ou sistemas distribudos), possvel aproveitar esse paralelismo e acelerar a execuo do
PROGRAMAO CONCORRENTE Prof. Simo Toscani

(Do livro Sistemas Operacionais e Programao Concorrente, Toscani S.S., Oliveira R.S. e Carissimi A.S.
Editora Sagra-Luzzatto, 2003)
programa.Mesmoemsistemascomumnicoprocessador,existemrazesparaoseuusoem
vriostiposdeaplicaes.
Considereumprogramaquedevelerregistrosdeumarquivo,colocaremumformato
apropriadoeentoenviarparaumaimpressorafsica(emoposioaumaimpressoralgicaou
virtual, implementada comarquivos). Podemos fazerissocom umprograma seqencial que,
dentrodeumlao,fazastrsoperaes(ler,formatareimprimirregistro).
Arquivo
Processo
Impressora
fsica
Figura1Programaseqencialacessandoarquivoeimpressora.
Inicialmenteoprocessoenviaumcomandoparaaleituradoarquivoeficabloqueado.O
disco ento acionado para realizar a operao de leitura. Uma vez concluda a leitura, o
processorealizaaformataoeiniciaatransfernciadosdadosparaaimpressora.Comotratase
deumaimpressorafsica,oprocessoexecutaumlaonoqualosdadossoenviadosparaaporta
serialouparalelaapropriada.Comoobufferdaimpressorarelativamentepequeno,oprocesso
ficapresoatofinaldaimpresso.Odiscoeaimpressoranuncatrabalhamsimultaneamente,
emboraissosejapossvel.oprogramaseqencialquenoconsegueocuparambos.
Vamosagoraconsiderarumprogramaconcorrentecomoomostradonafigura2para
realizar a impresso do arquivo. Dois processos dividem o trabalho. O processo leitor
responsvel por ler registros do arquivo, formatar e colocar em um buffer na memria. O
processoimpressorretiraosdadosdo buffer eenviaparaaimpressora.supostoaquiqueos
doisprocessospossuemacessomemriaondeesto buffer. Esteprogramamaiseficiente,
poisconseguemanterodiscoeaimpressoratrabalhandosimultaneamente.Otempototalpara
realizaraimpressodoarquivovaisermenor.
Arquivo
Processo
Leitor
Buffer
Processo
Impressor
Impressora
fsica
Figura2Programaconcorrenteacessandoarquivoeimpressora.
Ousodaprogramaoconcorrentenaturalnasaplicaesqueapresentamparalelismo
intrnseco, ditas aplicaes inerentemente paralelas. Nessas aplicaes podese distinguir
facilmentefunesparaseremrealizadasemparalelo.Esteocasodospoolingdeimpresso,
exemploqueserapresentadoaseguir.Podesedizerque,emgeral,aprogramaoconcorrente
temaplicaonaturalnaconstruodesistemasquetenhamdeimplementarserviosqueso
requisitados de forma imprevisvel [DIJ65]. Nesse caso, o programa concorrente ter um
processopararealizarcadatipodeservio.
Aseguirconsideradoumservidordeimpressoparaumaredelocal.Afigura3ilustra
umaredelocalnaqualexistemdiversoscomputadorespessoais(PC)utilizadospelosusuriose
existeumcomputadordedicadoaopapeldeservidordeimpresso.Oservidorusaumdisco
magnticoparamanterosarquivosqueestonafiladeimpresso.
PC
Usurios
PC
PC
Servidor de Impresso
Figura3Redelocalincluindoumservidordeimpressodedicado.
importante observar que o programa "servidor de impresso" possui paralelismo

intrnseco. Ele deve: (1) receber mensagens pela rede; (2) escrever em disco os pedaos de
arquivos recebidos; (3) enviar mensagens pela rede (contendo, por exemplo, respostas s
consultas sobreoseuestado);(4)lerarquivos previamente recebidos (paraimprimlos);(5)
enviardadosparaaimpressora.Todasessasatividadespodemserrealizadas"simultaneamente".
Umaformadeprogramaroservidordeimpressousarvriosprocessos,cadaumresponsvel
porumaatividadeemparticular.Obviamente,essesprocessosvoprecisartrocarinformaes
pararealizaroseutrabalho.
Afigura4mostraumadaspossveissoluesparaaorganizaointernadoprograma
concorrente "servidor de impresso". Cada crculo representa um processo. Cada flecha
representaapassagemdedadosdeumprocessoparaooutro.Essapassagemdedadospodeser
feita,porexemplo,atravsdevariveisquesocompartilhadaspelosprocessosenvolvidosna
comunicao.
Vamosagoradescreverafunodecadaprocesso.Oprocesso"Receptor"responsvel
porrecebermensagensdaredelocal.Elefazissoatravsdechamadasdesistemaapropriadase
descarta asmensagenscomerro.Asmensagens corretas soentopassadasparaoprocesso
"Protocolo".Eleanalisaocontedodasmensagensrecebidasluzdoprotocolodecomunicao
suportadopeloservidordeimpresso.possvelquesejanecessrioageraoeoenviode
mensagensderesposta.Oprocesso"Protocolo"geraasmensagensaseremenviadasepassaas
paraoprocesso"Transmissor",queasenviaatravsdechamadasdesistemaapropriadas.
Algumasmensagenscontmpedaosdearquivosaseremimpressos.supostoaquique
otamanhodasmensagenstenhaumlimite(algunsKbytes).Dessaforma,umarquivodeveser
divididoemvriasmensagensparatransmissoatravsdarede.Quandooprocesso"Protocolo"
identificaumamensagemquecontmumpedaodearquivo,elepassaessepedaodearquivo
paraoprocesso"Escritor".Passatambmaidentificaodoarquivoaoqualopedaoemquesto
pertence.Cabeaoprocesso"Escritor"usaraschamadasdesistemaapropriadasparaescreverno
3
disco.Quandoopedaodearquivoemquestooltimodeseuarquivo,oprocesso"Escritor"
passaparaoprocesso"Leitor"onomedoarquivo,queestprontoparaserimpresso.
Receptor
Transmissor
Protocolo
Escritor
Leitor
Impressor
Figura4Servidordeimpressocomoprogramaconcorrente.
Oprocesso"Leitor"executa umlaonoqualelepegaumnomedearquivo,enviao
contedodoarquivoparaoprocesso"Impressor"eentoremoveoarquivolido.Oenviodo
contedoparaoprocesso"Impressor"feitoatravsdeumlaointernocompostopelaleiturade
umapartedoarquivoepeloenviodessaparte.Finalmente,oprocesso"Impressor"encarregado
deenviarospedaosdearquivoqueelerecebeparaaimpressora.Orelacionamentoentreos
processos"Leitor"e"Escritor"foidescritoantes,noinciodestaseo.
Oservidordeimpressoilustraoempregodaprogramaoconcorrentenaconstruode
umaaplicaocomparalelismointrnseco.Oresultadoumaorganizaointernaclaraesimples
para o programa. Um programa seqencial equivalente seria certamente menos eficiente. O
restantedestecaptulodedicadoaosproblemasestcnicasexistentesparaaconstruode
programasconcorrentescomoesse.
Hojeemdiaexistemvriaslinguagensquepermitemconstruirprogramasconcorrentes
(Java,Ada,PascalConcorrente,Cestendidocombibliotecasparaconcorrncia,etc.).Aquiser
utilizadaumalinguagemapropriadaparaensino,denominadaVale4(V4)[TOS04].
3 Especificao do paralelismo
Para construir um programa concorrente, antes de mais nada, necessrio ter a capacidade de
especificar o paralelismo dentro do programa. Essa especificao pode ser feita de diversas
maneiras. Uma delas utiliza os comandos fork, quit e join [CON63]. Outras maneiras sero
apresentadas na seo 4.

O comando (ou funo) fork pode ser implementado de duas maneiras distintas: ele pode
criar um novo processo ou criar apenas um novo fluxo de execuo dentro de um processo j
existente. A funo fork retorna um nmero inteiro que a identificao do novo processo ou do
novo fluxo criado. Um fluxo de execuo tambm denominado linha de execuo ou thread.
Os comandos quit e join so auxiliares ao fork. Quando o comando quit executado, o
processo (ou thread) que o executa termina imediatamente. O comando join(id) bloqueia quem o
executa at que termine o processo (ou thread) identificado por id.
Primitiva fork no sistema Unix
No sistema operacional Unix a operao fork cria um novo processo que uma cpia idntica
(clone) do processo que executa esta operao. Por exemplo, o comando
id = fork()
cria um filho idntico ao processo que executou a operao (isto , cria uma cpia do processo
original). O processo filho recebe cpias das variveis do processo pai, bem como dos descritores
de arquivos. Os valores iniciais das variveis do filho so iguais aos valores das variveis
correspondentes do pai no momento da execuo da funo fork. Observe que no h
compartilhamento de variveis: as variveis do pai ficam no espao de endereamento1 do pai e as
variveis do filho, no espao de endereamento do filho. Em relao aos valores dessas variveis,
a nica diferena inicial entre o pai e o filho o valor da varivel id, que 0 para o filho e o
valor de retorno da funo fork para o pai. O valor de retorno o nmero de identificao do
processo criado (process identification ou pid). Isto permite que os processos prossigam de
acordo com suas identidades. Normalmente, o comando seguinte ao fork tem a seguinte forma:
if id = 0
then { processamento do filho }
else { processamento do pai }
Um dos processos, por exemplo o filho, pode sobrepor um novo cdigo sobre si, atravs
da operao exec(P), onde P um novo programa para ser executado (novo segmento de cdigo
e de dados para o processo).
Fork, join e quit na linguagem Vale4
Na linguagem Vale4, o funcionamento do comando fork similar ao do Unix, porm com uma
grande diferena: o fork cria uma thread e no um processo. As threads me e filha so idnticas:
executam o mesmo cdigo e compartilham todas as variveis do processo em que so definidas (
justamente nesse compartilhamento que est a diferena para o Unix).
Na linguagem V4, a execuo do comando
id := fork()
faz com que a varivel global2 id receba o valor retornado pela funo fork, que o nmero nico
da thread criada. A thread original (me) e a thread criada (filha) executam em paralelo a partir do
1
Basicamente, o espao de endereamento de um processo formado por um segmento de cdigo e um segmento de

dados. O primeiro contm as instrues do processo e o segundo contm as variveis e constantes do processo.
Alm disso, todo processo possui uma pilha que usada para chamadas e retornos de procedimentos.

comando que segue ao fork. As duas threads iro se distinguir atravs da varivel denominada
myNumber3. O valor dessa varivel sempre a identificao de quem a refere (isto , o nmero
nico de quem a refere). Tipicamente, o comando que segue ao fork tem a seguinte forma:
if id = myNumber
then { processamento da filha }
else { processamento da me }
Observe que apenas para a thread filha o myNumber igual ao valor da varivel global id.
Para criar processos (no threads) dinamicamente, a linguagem V4 oferece o comando
new que ser apresentado na seo que segue. Enquanto o comando fork cria uma nova thread, o
comando new cria um novo processo.
O comando join(id) permite que um processo (ou thread) P espere pelo trmino do
descendente imediato (filho ou filha) identificado por id. Se o argumento id no identifica um
processo ou thread, ou se id no corresponde a um descendente imediato de P, ento um erro
reportado (erro de execuo).
O argumento de join pode ser tambm a palavra reservada any, que significa o desejo de
esperar pelo trmino de qualquer um dos descendentes imediatos. Nesse caso, no retorno da
primitiva, a varivel any4 vai conter a identidade do filho ou filha cuja execuo terminou.
Outra peculiaridade da primitiva join(id) que ela pode ser usada como funo ou como
subrotina. Usada como funo, ela retorna o valor que o filho (ou filha) id especificou no
comando quit, ao morrer, conforme explicado a seguir.
O ltimo comando do conjunto o quit, que mata o seu executor. Podem ser usadas as
formas quit ou quit(X). No segundo caso, o argumento X um valor inteiro que o processo ou
thread informa ao seu genitor, ao morrer. Se desejar pegar esse valor, o genitor usar a primitiva
join, como funo.5 A propsito, um quit sem argumento equivale a um quit(0).
Diferena entre thread e processo
O que melhor distingue uma thread de um processo o espao de endereamento. Todas as

threads de um processo trabalham no mesmo espao de endereamento, que a memria lgica
do processo hospedeiro. Isto , quando se tem um conjunto de threads dentro de um processo,
todas as threads executam o cdigo do processo e compartilham as suas variveis. Por outro lado,
quando se tem um conjunto de processos, cada processo trabalha num espao de endereamento
prprio, com um conjunto separado de variveis.
No caso de um processo com N threads, tem-se um nico registro descritor (o registro do
processo hospedeiro) e N mini-descritores de threads. O mini-descritor de cada thread usado
para salvar os valores dos registradores da UCP (PC, PSW, etc.). Adicionalmente, cada thread
possui uma pilha, que usada para as chamadas e retornos de procedimentos.
2
Varivel declarada no processo hospedeiro, compartilhada entre me e filha.

Tudo se passa como se cada processo ou thread tivesse uma varivel local, denominada myNumber, contendo o
nmero nico desse processo ou thread. Na verdade, myNumber, que tambm pode ser referido como myself ou
myID, uma funo primitiva que consulta o registro descritor do processo ou thread para obter o nmero de sua
carteira de identidade e retorna esse nmero.
4
Semelhantemente ao que ocorre com myNumber, tudo se passa como se cada processo ou thread tivesse uma
varivel local, denominada any.
5
No caso de ser usada como subrotina, a primitiva join(id) desconsidera o valor informado pelo descendente id.
3

mais fcil chavear a execuo entre threads (de um mesmo processo) do que entre
processos, pois tem-se menos informaes para salvar e restaurar. Por esse motivo, as threads so
chamadas tambm de "processos leves".
Um exemplo
VamosusaralinguagemV4paraexemplificarousodoscomandosfork,joinequit.Oprograma
mostradonafigura5possuium nicoprocesso.Alinhadeexecuo inicial desseprocesso
executaduasvezesocomando fork,criandoduas threads adicionais (filhas1e2).A thread
originalentoesperaquecadaumadasfilhastermine,escreveumamensagemparacadaumae
terminatambm.Asduasthreadscriadasapenascolocamumamensagemnatelaeterminam.
V4program
process p1;
f1: integer;
f2: integer;
/* identifica filha 1*/

/* identifica filha 2*/
{ write('Alo da mae'); nl;

f1:= fork();
/* Cria filha 1 */
if f1 = myNumber then { write('Alo da filha 1'); nl; quit};

f2:= fork();
/* Cria filha 2 */
if f2 = myNumber then { write('Alo da filha 2'); nl; quit};

join(f1);
write('Filha 1 morreu'); nl;
join(f2);
write('Filha 2 morreu'); nl
}
end program
Figura 5 - Uso de comandos fork, join e quit.

Ocomandowrite(X)escrevenateladoterminaldousurio.OargumentoXpodeseruma
constante,umavarivel,umelementode array ouum string entreapstrofes. O comando nl
(newline)fazcomqueaprximaimpressosejafeitaemumanovalinha. Duaspossveis
sadasparaoprogramaanteriorseriam:
Alo da mae
Alo do filha 1
Alo do filha 2
Filha 1 morreu
Filha 2 morreu
Alo da mae
Alo do filha 1
Filha 1 morreu
Alo do filha 2
Filha 2 morreu

4 Criao esttica e criao dinmica de processos

Os processos de um programa concorrente podem ser criados de forma esttica ou dinmica. No
primeiro caso, o programa contm a declarao de um conjunto fixo de processos, os quais so
ativados simultaneamente, no inicio da execuo do programa. No segundo caso, os processos so
criados dinamicamente, durante a execuo, atravs de instrues especiais para esse fim.
Os mecanismos vistos at aqui (fork, join e quit) realizam criao dinmica (e trmino
dinmico), pois os processos (ou threads) so criados somente quando instrues especiais so
executadas.6
Criao esttica
No caso da criao esttica, os processos so declarados explcitamente7 no programa fonte e

vo existir desde o incio da execuo do programa concorrente. Normalmente, as linguagens de
programao permitem especificar esses processos de duas maneiras: como processos individuais
ou como um array de processos.
Especificao de processos individuais:
Neste caso, cada processo especificado de forma individual, conforme exemplificado a seguir.
V4program
process P1;
k: integer init 0;
while k < 10 do
{ write(1);
k:=k+1
};
process P2;
k: integer init 0;
while k < 10 do
{ write(2);
k:=k+1
}
endprogram
O programa define 2 processos, denominados P1 e P2, que no compartilham variveis
(no existem variveis globais no programa). Cada processo utiliza uma varivel local,
denominada k. O primeiro imprime 10 vezes o nmero 1 e o segundo, em paralelo, imprime 10
vezes o nmero 2. O resultado da execuo pode ser qualquer seqncia de tamanho 20, contendo
10 vezes o nmero 1 e 10 vezes o nmero 2, embaralhados. Teoricamente, so possveis 20!/(10!
*10!) resultados diferentes.8
Por exemplo, se a execuo no passa por uma determinada instruo fork, ento a thread correspondente no
criada.
7
A declarao explcita consiste em definir, para cada processo do programa, as suas variveis locais e o seu
segmento de cdigo.
8
Combinaes de uma seqncia de 20 escaninhos, escolhidos 10 a 10.

Array de processos
Neste caso, uma nica declarao especifica um grupo de processos semelhantes, que se
distinguem apenas pelo valor de uma varivel local inteira, que especificada no cabealho do
processo, conforme ilustrado a seguir, considerando o mesmo exemplo anterior.
V4program
process P (i := 1 to 2);
k: integer init 0;
while k < 10 do
{ write(i);
k:=k+1
}
endprogram
Para o primeiro processo, a sua varivel local i vale 1 e para o segundo, a sua varivel
local i vale 2. Este programa equivalente ao anterior.
Criao dinmica
possvel declarar explicitamente um modelo (uma "forma") para criar processos durante a
execuo, conforme ilustrado a seguir. Neste caso tem-se o que se denomina criao dinmica
com declarao explcita de processos.
V4program
process type P (i: integer);
k: integer init 0;
while k < 10 do
{ write(i);
k:=k+1
};
process Q;
{ new P(1); new P(2) }
endprogram
Atravs da especificao process type, explicita-se um modelo (template) de processo, o
qual utilizado para criar exemplares (cpias, clones) desse processo durante a execuo. A
criao de um novo exemplar se d atravs do comando new, o qual permite passar parmetros
para o processo criado. No caso da linguagem Vale4, a primitiva new pode ser usada como funo
ou como subrotina; usada como funo ela retorna a identificao interna (pid) do processo
criado.
5 Exemplos de programas concorrentes
Esta seo apresenta programas simples que ilustram caractersticas importantes dos programas
concorrentes. Tratam-se de programas Vale4 completos, prontos para serem compilados e
executados no ambiente V4. Para melhorar a legibilidade dos programas, usada a seguinte
notao: os identificadores declarados (variveis, procedimentos, etc.) so apresentados em
itlico.
Compartilhamento de um procedimento
O mesmo programa que foi utilizado na seo 3.5 para distinguir as diferentes maneiras de
especificar (e criar) processos reescrito para ilustrar o compartilhamento de um procedimento.
V4program
procedure imprime(i: integer);
k: integer init 0;
while k < 10 do
{ write(i);
k:=k+1
};
process P1; imprime(1);
process P2; imprime(2)
endprogram
Cada processo chama imprime fornecendo como argumento o nmero a ser impresso.
Como nos exemplos anteriores, o resultado da execuo desse programa imprevisvel, sendo
10
possveis (teoricamente) C 20
resultados distintos.
Observao sobre as variveis de um procedimento
No exemplo anterior, existem duas execues concorrentes do procedimento imprime, uma

efetuada por P1 e outra por P2. Cada uma dessas execues utiliza variveis i (argumento) e k
(varivel local do procedimento). A observao importante que cada processo utiliza cpias
independentes dessas variveis. O cdigo do procedimento compartilhado pelos dois processos,
mas os dados (variveis i e k) so privativos de cada processo. Isto , cada processo trabalha
sobre um conjunto de dados separado.
No se pode esquecer que, na chamada de um procedimento, os argumentos e as variveis
locais desse procedimento so alocados na pilha do processo chamador. Como cada processo (ou
thread) trabalha com uma pilha prpria, as execues no interferem uma com a outra. Na
programao concorrente sempre assim, todo procedimento automaticamente reentrvel (ou
puro). Isto significa que o mesmo cdigo pode ser executado simultaneamente por vrios
processos sem que haja interferncia entre eles, pois cada processo utiliza um conjunto separado
de parmetros e de variveis locais.
Compartilhamento de uma varivel
O programa a seguir implementa um sistema concorrente onde dois processos compartilham uma
varivel global S. Cada processo incrementa S de uma unidade, 100 vezes.
V4program
S : integer init 0;
process p1;
10
k: integer init 0;
{ loop
S:= S+1;
k:= k+1;
exit when k = 100
endloop;
nl; write('p1'); tab(2); write(S)
};
process p2;
k: integer init 0;
{ loop
S:= S+1;
k:= k+1;
exit when k = 100
endloop;
nl; write('p2'); tab(2); write(S)
}
endprogram
Este programa utiliza os comandos loop e tab(K), os quais so explicados a seguir.
O comando loop
O comando loop implementa um ciclo infinito. No seu interior, o comando exit when <cond>
significa que o ciclo acaba (isto , que a execuo vai para o comando seguinte ao endloop)
quando a condio <cond> verdadeira. Este comando pode substituir todos os demais comandos
iterativos (while, repeat, for, etc.), com a vantagem de, em geral, tornar os programas mais claros.
O comando tab(K)
Este comando escreve K espaos em branco no terminal do usurio, sendo til para formatar a
impresso de resultados.
Observao sobre a inicializao de variveis
Em V4, as variveis no explicitamente inicializadas possuem valor inicial igual a 0, se inteiras, e

igual a false, se booleanas. Quando usada, a clusula initial (ou init) deve ser seguida de um nico
valor inicial. Se o uso na declarao de uma lista de identificadores, ento todos os
identificadores da lista recebem esse nico valor inicial. Se o uso na declarao de um array,
todos os elementos do array recebem esse nico valor especificado.
O problema da excluso mtua
No programa anterior, tem-se 2 processos manipulando a varivel global S. Cada processo

executa 100 vezes o comando S:=S+1. Este comando compilado para a seguinte seqncia de
cdigo de mquina:
push
% coloca o valor de S na pilha
push
$1
% coloca a constante 1 na pilha
add
% soma os dois ltimos valores colocados na pilha

11
pop
% guarda o resultado em S
Como os pontos em que a UCP passa de um processo para outro so imprevisveis, pode
acontecer de um processo perder a UCP no meio da seqncia acima.9 Vamos supor que o valor
de S carregado na pilha seja 10 e que o processo perca a UCP. Nesse caso, quando este processo
receber a UCP de volta, ele vai concluir a seqncia acima e armazenar o valor 11 em S. Todos os
acrscimos a S feitos pelo outro processo nesse nterim so perdidos. Como conseqncia,
embora S inicie com o valor zero e cada processo some 1 a S cem vezes, o valor final de S
dificilmente ser igual a 200. Para o resultado ser 200, deve haver excluso mtua no acesso
varivel S, isto , enquanto um processo estiver manipulando S, o outro no pode acessar S.
A excluso mtua um requisito muito importante nos sistemas concorrentes. Em geral,
necessrio garantir o acesso exclusivo aos dados compartilhados. A excluso mtua s no
necessria quando os dados so compartilhados na modalidade "apenas leitura", isto , quando os
dados no so alterados pelos processos. Os trechos dos processos onde os dados compartilhados
so manipulados, so denominados trechos crticos ou regies crticas.
Criao dinmica de processos
A criao dinmica (e recursiva) de processos ilustrada atravs do problema da torre de Hani,

descrito a seguir. Tem-se 3 torres (pilhas) e n discos de tamanhos diferentes. Inicialmente os n
discos esto empilhados na torre 1, na ordem certa (maior na base, menor no topo). O problema
consiste em movimentar todos os discos para uma determinada torre, sem que nunca um disco
maior fique sobre um disco menor. Os discos devem ser transportados de um em um e a terceira
torre pode ser usada como intermediria nessas movimentaes.
O programa inicia com o processo P criando um filho (escravo) Hanoi para movimentar 3
discos da torre 1 para a torre 2, usando a torre 3 como intermediria. Para movimentar n discos de
a para b, usando c como torre intermediria, um escravo Hanoi faz o seguinte. Se n = 1 (s tem
um disco para movimentar), ento o trabalho fcil e direto: o escravo movimenta o nico disco
de a para b (e mostra essa movimentao). Caso contrrio, o escravo cria um escravo_1 para
movimentar n-1 discos de a para c, usando b como torre intermediria. Quando esse servio
concludo (escravo_1 termina o seu trabalho), o escravo original movimenta o disco que lhe
sobrou (que o maior) de a para b (mostra essa movimentao) e cria um escravo_2 para concluir
o servio, que movimentar n-1 discos de c para b usando a como torre intermediria.
V4program
process type Hanoi(n, a, b, c: integer);
id, m: integer;
if n = 1
then { nl; write(a); write(' --> '); write(b) }
else { m:= n-1;
id:= new Hanoi(m, a, c, b); join(id);
nl; write(a); write(' --> '); write(b);
id:= new Hanoi(m, c, b, a); join(id)
};
9
Sempre que um processo perde a UCP, o seu estado salvo. Mais tarde, a execuo do processo continua, como se
nada tivesse acontecido.

12
process P; new Hanoi(3, 1, 2, 3)

endprogram
O resultado da execuo deste programa ser a ordem em que os discos devero ser
movimentados (movimento por movimento, um disco por vez).
6 Sincronizaes bsicas
comum um processo ter que esperar at que uma condio se torne verdadeira. Para essa espera
ser "eficiente", o processo deve esperar no estado bloqueado (sem competir pela UCP). Dois tipos
de bloqueio so considerados bsicos:
1. bloquear at que um recurso se torne disponvel;10
2. bloquear at que chegue um sinal de outro processo.
Estes bloqueios so caracterizados pelas operaes bsicas lock/unlock e block/wakeup(P),
descritas a seguir. Enquanto o primeiro par (lock/unlock) implementa sincronizao do tipo
excluso mtua, o segundo par implementa uma forma bsica de comunicao.
lock; . . . ; unlock
Um processo s entra num trecho delimitado pelo par lock/unlock se nenhum outro processo est
executando em um outro trecho delimitado dessa maneira. Isto , o primeiro processo que executa
o comando lock passa e tranca a passagem (chaveia a fechadura) para os demais. O comando
unlock deixa passar (desbloqueia) o primeiro processo da fila de processos que esto bloqueados
por terem executado um lock (enquanto a fechadura estava trancada). Se a fila est vazia, a
fechadura destrancada (isto , deixada aberta).
block/wakeup(P)
Quando um processo P executa o comando block, ele se bloqueia at que um outro processo
execute o comando wakeup(P). Este ltimo comando acorda (desbloqueia) o processo
especificado por P. Se wakeup(P) executado antes, o processo P no se bloqueia ao executar o
block. Na linguagem Vale4, o argumento de wakeup pode ser um nome de processo ou um
nmero nico de processo ou thread.
Na verdade, os comandos lock e unlock no formam uma estrutura sinttica (isto , no
precisam estar casados, como se fossem um abre e fecha parnteses), eles so comandos
independentes. Na linguagem Vale4, as operaes lock e unlock tambm podem ser referidas pelos
nomes mutexbegin e mutexend, respectivamente.
7 Semforos
As variveis semforas so variveis especiais que admitem apenas duas operaes, denominadas
P e V.11 Sendo S uma varivel semfora, as operaes P e V tm a seguinte semntica:
P(S) : espera at S ser maior que 0 e ento subtrai 1 de S;
10
O recurso pode ser, inclusive, "o direito de acessar os dados compartilhados".

P e V so as iniciais das palavras holandesas Proberen e Verhogen, que significam testar e incrementar,
respectivamente.
11

13
V(S) : incrementa S de 1.
As operaes testar S e subtrair 1 (se S > 0) e incrementar S de 1 so executadas de
forma atmica (indivisvel), no kernel do SO. Se S = 1 e dois processos executam P(S)
simultaneamente, um dos processos vai ficar bloqueado.
Pode-se fazer analogia entre uma varivel semfora e um vaso contendo bolitas (bolinhas
de gude). O valor numrico do semforo corresponde ao nmero de bolitas dentro do vaso. Uma
operao V corresponde a pr uma bolita no vaso. Cada operao P tenta remover uma bolita; se
nenhuma est disponvel, ento a operao bloqueia o processo e o coloca numa fila de espera.
Quando uma bolita colocada no vaso (operao V), ela removida pelo primeiro processo da
fila de espera, o qual prossegue sua execuo.
Sincronizaes bsicas com semforos
As variveis semforas permitem implementar os dois tipos bsicos de bloqueio, conforme

explicado a seguir.
Sincronizao tipo lock/unlock:
A sincronizao do tipo excluso mtua implementada atravs de um semforo com valor inicial
1. O acesso exclusivo a n regies crticas seria implementado como segue:
X : semaphore initial 1
P1:
...
P2:
...
...
Pn:
...
P(X);
P(X);
P(X);
REGIO CRTICA;
REGIO CRTICA;
REGIO CRTICA;
V(X);
...
V(X);
...
V(X);
...
Sincronizao tipo block/wakeup(P):
Este tipo de sincronizao implementado atravs de um semforo com valor inicial zero. Por
exemplo, se a operao B do processo P1 deve ser executada aps a operao A do processo P2,
programa-se da seguinte maneira:
Y : semaphore initial 0
P1:
...
P(Y);
B;
...
...
P2:
...
% block
...
A;
V(Y); % wakeup(P1)
...

14
8 Programas clssicos
Esta seo apresenta 4 problemas clssicos da programao concorrente, todos resolvidos atravs
do uso de semforos e todos escritos de acordo com a sintaxe de Vale4.
Produtor-consumidor com buffer limitado
Este problema pode ser enunciado como segue. Um par de processos compartilha um buffer de N
posies. O primeiro processo, denominado produtor, passa a vida a produzir mensagens e a
coloc-las no buffer. O segundo processo, denominado consumidor, passa a vida a retirar
mensagens do buffer (na mesma ordem em que elas foram colocadas) e a consum-las.
A relao produtor-consumidor ocorre comumente em sistemas concorrentes e o problema
se resume em administrar o buffer que tem tamanho limitado. Se o buffer est cheio, o produtor
deve se bloquear, se o buffer est vazio, o consumidor deve se bloquear. A programao desse
sistema com buffer de 5 posies e supondo que as mensagens sejam nmeros inteiros, mostrada
a seguir.
Variveis globais:
buffer: array[5] of integer;

cheios: semaphore initial 0;
vazios: semaphore initial 5;
Processo produtor:
msg, in : integer;
loop
% produz mensagem msg
P(vazios);
in:= (in mod 5)+1;
buffer[in]:= msg;
V(cheios)
endloop
Processo consumidor:
msg, out : integer;
loop
P(cheios);
out:= (out mod 5)+1;
msg:= buffer[out];
V(vazios);
% consome a mensagem
endloop
O semforo cheios conta o nmero de buffers cheios e o semforo vazios conta nmero de
buffers vazios. Conforme j foi referido, as variveis inteiras que no so inicializadas tem seu
valor inicial igual a zero.
Observe que a soluo no se preocupou em garantir excluso mtua no acesso ao buffer.
Isto porque os dois processos trabalham com variveis locais in, out e msg e, certamente, iro
acessar sempre posies diferentes do vetor global buffer.
Jantar dos Filsofos
Este problema ilustra as situaes de deadlock e de postergao indefinida que podem ocorrer em
sistemas nos quais processos adquirem e liberam recursos continuamente.
Existem N filsofos que passam suas vidas pensando e comendo. Cada um possui seu
lugar numa mesa circular, em cujo centro h um grande prato de spaghetti. A figura 6 ilustra a
situao para 5 filsofos. Como a massa muito escorregadia, ela requer dois garfos para ser
15
comida. Na mesa existem N garfos, um entre cada dois filsofos, e os nicos garfos que um
filsofo pode usar so os dois que lhe correspondem (o da sua esquerda e o da sua direita). O
problema consiste em simular o comportamento dos filsofos procurando evitar situaes de
deadlock (bloqueio permanente) e de postergao indefinida (bloqueio por tempo indefinido).
filsofo 3
garfo 3
filsofo 4
garfo 2
filsofo 2
spaghetti
garfo 1
garfo 4
filsofo 1
filsofo 5
garfo 5
Figura 6 - A mesa dos 5 filsofos

Da definio do problema, tem-se que nunca dois filsofos adjacentes podero comer ao
mesmo tempo e que, no mximo, N/2 filsofos podero estar comendo de cada vez. Na soluo a
seguir, iremos nos concentrar no caso de 5 filsofos. Os garfos so representados por um vetor de
semforos e adotada a seguinte regra: todos os 5 filsofos pegam primeiro o seu garfo da
esquerda, depois o da direita, com exceo de um deles, que do contra. Pode ser demonstrado
que esta soluo livre de deadlocks. Foi escolhido o filsofo 1 para ser do contra.
O programa a seguir um programa Vale4 completo, no qual cada filsofo faz 10 refeies
e morre.
V4program
garfo: array[5] of semaphore init 1;
% array global
procedure getForks(i: integer);

j: integer;
{ j := i-1 ;
% j o garfo da esquerda
if j = 0 then { P(garfo[1]); P(garfo[5]) }
else { P(garfo[j]); P(garfo[i]) }
};
procedure putForks(i: integer);
j: integer;
{ j := i-1 ;
% j o garfo da esquerda
if j = 0 then { V(garfo[1]); V(garfo[5]) }
else { V(garfo[j]); V(garfo[i]) }
};
process filosofo (i:= 1 to 5);
16
k: integer init 10;

while k > 0 do
{ getForks(i);
nl; write(filosofo ); write(i); write( comecou a comer);
putForks(i);
nl; write(filosofo ); write(i); write( parou de comer);
k:=k-1
}
endprogram
Barbeiro dorminhoco
O problema consiste em simular o funcionamento de uma barbearia com as seguintes

caractersticas. A barbearia tem uma sala de espera com N cadeiras e uma cadeira de barbear. Se
no tem clientes espera, o barbeiro senta numa cadeira e dorme. Quando chega um cliente, ele
acorda o barbeiro. Se chega outro cliente enquanto o barbeiro est trabalhando, ele ocupa uma
cadeira e espera (se tem alguma cadeira disponvel) ou vai embora (se todas as cadeiras esto
ocupadas).
A soluo a seguir usa 3 semforos: clientes, fila e mutex. O semforo clientes tranca o
barbeiro, sendo suas bolitas produzidas pelos clientes que chegam. O valor desse semforo
indica o nmero de clientes espera (excluindo o cliente na cadeira do barbeiro, que no est
espera). O semforo fila tranca os clientes e implementa a fila de espera. O semforo mutex
garante excluso mtua. Tambm usada uma varivel inteira, count, que conta o nmero de
clientes espera. O valor desta varivel sempre igual ao nmero de bolitas do semforo
clientes.
Geral da acacao de sert
Um cliente que chega na barbearia verifica o nmero de clientes espera. Se esse nmero
menor que o nmero de cadeiras, o cliente espera, caso contrrio, ele vai embora. A soluo
apresentada a seguir, considerando o nmero de cadeiras na sala de espera igual a 3.
Inicialmente, o barbeiro executa a operao P(clientes), onde fica bloqueado (dormindo)
at a chegada de algum cliente. Quando chega um cliente, ele comea adquirindo a excluso
mtua. Outro cliente que chegar imediatamente aps, ir se bloquear at que o primeiro libere a
excluso mtua. Dentro da regio crtica, o cliente verifica se o nmero de pessoas espera
menor ou igual ao nmero de cadeiras. Se no , ele libera mutex e vai embora sem cortar o
cabelo.
Se tem alguma cadeira disponvel, o cliente incrementa a varivel count e executa a
operao V no semforo clientes. Se o barbeiro est dormindo, ele acordado; caso contrrio,
adicionada uma bolita no semforo clientes. A seguir, o cliente libera a excluso mtua e entra
na fila de espera. O barbeiro adquire a excluso mtua, decrementa o nmero de clientes, pega o
primeiro da fila de espera e vai fazer o corte.
Variveis globais:
clientes, fila: semaphore init 0;

mutex: semaphore init 1;
count : integer initial 0;

17
Processo barbeiro:
Loop
P(clientes); /*dorme, se for o caso*/
P(mutex);
count:= count 1;
V(fila); /*pega prximo cliente*/
V(mutex);
Processo cliente:
P(mutex);
if count < 3
then { count:= count+1;
V(clientes); /*acorda o barbeiro*/
V(mutex);
P(fila);
/*espera o barbeiro*/
/*corta o cabelo*/
Endloop
/*corta o cabelo*/
}
else V(mutex)
Quando termina o corte de cabelo, o cliente deixa a barbearia e o barbeiro repete o seu
loop onde tenta pegar um prximo cliente. Se tem cliente, o barbeiro faz outro corte. Se no tem,
o barbeiro dorme.

18
Leitores e escritores
O problema dos readers and writers [COU71] ilustra outra situao comum em sistemas de
processos concorrentes. Este problema surge quando processos executam operaes de leitura e
de atualizao sobre um arquivo global (ou sobre uma estrutura de dados global). A sincronizao
deve ser tal que vrios readers (isto , processos leitores, que no alteram a informao) possam
utilizar o arquivo simultaneamente. Entretanto, qualquer processo writer deve ter acesso exclusivo
ao arquivo.
Na soluo a seguir dada prioridade para os processos readers. So utilizadas duas
variveis semforas, mutex e w, para excluso mtua, e uma varivel inteira nr, para contar o
nmero de processos leitores ativos. Note que o primeiro reader bloqueia o progresso dos writers
que chegam aps ele, atravs do semforo w. Enquanto houver reader ativo, os writers ficaro
bloqueados.
Variveis globais:
mutex, w : semaphore initial 1;

nr : integer initial 0;
Processo leitor:
...
P(mutex);
nr:=nr+1;
if nr=1 then P(w);
V(mutex);
Processo escritor:
...
...
P(w);
READ
P(mutex);
nr:=nr-1;
if nr=0 then V(w);
V(mutex);
WRITE
V(w);
...
...
...

19
EXERCCIOS
1. Um semforo binrio um semforo cujo valor pode ser 0 ou 1. Mostre como um semforo
geral pode ser implementado a partir de semforos binrios.
2. Considere a instruo TS(X,L) que executa o seguinte cdigo de forma indivisvel:
if X then go to L else X:=true;
Mostre como implementar as operaes P e V sobre um semforo binrio usando a instruo
TS.
3. Usando semforos, complete o programa Vale4 a seguir, de maneira que o resultado impresso
seja sempre "AAAAABBBBB" (isto , cada processo s pode imprimir 'B' depois de todos os
outros terem impresso 'A').
V4program
...
process P (i := 1 to 5);
...
{ ...
write('A');
...
write('B');
...
}
endprogram
4. Usando a linguagem V4 e variveis semforas, escreva um programa formado por 6 processos
p1, p2, ..., p6, onde pi (1 i 6) imprime 10 vezes o nmero i. Os processos devem estar
sincronizados de acordo com o grafo de fluxo de processos abaixo:
I
p1
p4
p5
p2
p3
p6
F
5. Explique por que a soluo apresentada no texto para o problema do produtor-consumidor

no suporta mltiplos processos produtores e mltiplos processos consumidores.
6. Implemente uma soluo para o problema do buffer limitado, considerando um processo
produtor e vrios consumidores.
20
7. Descreva o erro na implementao do produtor-consumidor mostrada abaixo. Crie uma

seqncia de eventos que termina em algum comportamento indesejado para o programa.
buffer: array [N] of integer;
proxima_insercao, proxima_remocao: integer init 0;
exclusao_mutua: semaphore init 1;
espera_vaga: semaphore init N;
espera_dado: semaphore init 0;
process produtor;
{ ...
P( exclusao_mutua );
P( espera_vaga );
buffer[ proxima_insercao ] := dado_produzido;
proxima_insercao := ( proxima_insercao + 1 ) % N;
V( exclusao_mutua );
V( espera_dado );
...
};
process consumidor;
{ ...
P( exclusao_mutua );
P( espera_dado );
dado_a_consumir := buffer[ proxima_remocao ];
proxima_remocao := ( proxima_remocao + 1 ) % N;
V( exclusao_mutua );
V( espera_vaga );
...
}
8. Simplifique a soluo para o problema do produtor-consumidor para o caso de existir apenas
uma vaga disponvel no buffer circular.

21
BIBLIOGRAFIA
[CON63] CONWAY, M. E. A Multiprocessor system design. Proc. AFIPS Fall Joint Computer
Conference, pp.139-146. Las Vegas, Nevada, 1963.
[COU71] COURTOIS, P. J., HEYMANS, F.and PARNAS, D. L. Concurrent Control with
Readers and Writers. Comm. ACM 14, No. 10 (October), 667-668, 1971.
[DIJ65]
DIJKSTRA, E. W. Cooperating Sequential Processes. Technical Report EWD-123,

Technological University, Eindhoven, the Netherlands, 1965. Reprinted in: Programming
Languages (F. Genuys, ed.) pp. 43-112. Academic Press, New York, 1968.
[HOA74] HOARE, C. A. R. Monitors: An Operating System Structuring Concept. Comm.

ACM 17, No. 10 (October), 549-557, 1974. Erratum in Comm. ACM 18, No. 2, page
95 (January) 1975.
[OLI04]
OLIVEIRA, R, CARISSIMI, A., TOSCANI, S. Sistemas Operacionais. Srie didtica

do II-UFRGS, 2004 (3 edio).
[SHA84]
SHATZ, S. M. Communication mechanisms for programming distributed systems.

Computer 17, No. 6, pp.21-28, 1984.
[TAF97]
TAFT, S. T. DUFF, R. A. ADA 95 Reference Manual: language and standard

libraries. Springer-Verlag, 1995. (Lecture Notes in Computer Science, Vol 1246).
[TOS03]
TOSCANI, S., OLIVEIRA, R., CARISSIMI, A., Sistemas Operacionais e

Programao Concorrente. Srie didtica do II-UFRGS, 2003.
[TOS04]
TOSCANI, S. S. Kit de instalao da linguagem VALE4. Disponvel em

www.inf.pucrs.br/~stoscani/V4.

22

Sop Progconctext

Enviado por

Direitos autorais:

Formatos disponíveis

Sop Progconctext

Enviado por

Dados do documento

Descrição original:

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

Sop Progconctext

Enviado por

Direitos autorais:

Formatos disponíveis

PROGRAMAO CONCORRENTE

A programao concorrente foi usada inicialmente na construo de sistemas operacionais.

PROGRAMAO CONCORRENTE Prof. Simo Toscani

importante observar que o programa "servidor de impresso" possui paralelismo

PROGRAMAO CONCORRENTE Prof. Simo Toscani

Basicamente, o espao de endereamento de um processo formado por um segmento de cdigo e um segmento de

PROGRAMAO CONCORRENTE Prof. Simo Toscani

O que melhor distingue uma thread de um processo o espao de endereamento. Todas as

Varivel declarada no processo hospedeiro, compartilhada entre me e filha.

PROGRAMAO CONCORRENTE Prof. Simo Toscani

/* identifica filha 1*/

{ write('Alo da mae'); nl;

if f1 = myNumber then { write('Alo da filha 1'); nl; quit};

if f2 = myNumber then { write('Alo da filha 2'); nl; quit};

Figura 5 - Uso de comandos fork, join e quit.

PROGRAMAO CONCORRENTE Prof. Simo Toscani

4 Criao esttica e criao dinmica de processos

No caso da criao esttica, os processos so declarados explcitamente7 no programa fonte e

PROGRAMAO CONCORRENTE Prof. Simo Toscani

No exemplo anterior, existem duas execues concorrentes do procedimento imprime, uma

Em V4, as variveis no explicitamente inicializadas possuem valor inicial igual a 0, se inteiras, e

No programa anterior, tem-se 2 processos manipulando a varivel global S. Cada processo

% coloca o valor de S na pilha

% coloca a constante 1 na pilha

% soma os dois ltimos valores colocados na pilha

PROGRAMAO CONCORRENTE Prof. Simo Toscani

A criao dinmica (e recursiva) de processos ilustrada atravs do problema da torre de Hani,

PROGRAMAO CONCORRENTE Prof. Simo Toscani

process P; new Hanoi(3, 1, 2, 3)

O recurso pode ser, inclusive, "o direito de acessar os dados compartilhados".

PROGRAMAO CONCORRENTE Prof. Simo Toscani

As variveis semforas permitem implementar os dois tipos bsicos de bloqueio, conforme

Sincronizao tipo block/wakeup(P):

PROGRAMAO CONCORRENTE Prof. Simo Toscani

buffer: array[5] of integer;

Figura 6 - A mesa dos 5 filsofos

procedure getForks(i: integer);

k: integer init 10;

O problema consiste em simular o funcionamento de uma barbearia com as seguintes

clientes, fila: semaphore init 0;

PROGRAMAO CONCORRENTE Prof. Simo Toscani

PROGRAMAO CONCORRENTE Prof. Simo Toscani

mutex, w : semaphore initial 1;

PROGRAMAO CONCORRENTE Prof. Simo Toscani

5. Explique por que a soluo apresentada no texto para o problema do produtor-consumidor

7. Descreva o erro na implementao do produtor-consumidor mostrada abaixo. Crie uma

PROGRAMAO CONCORRENTE Prof. Simo Toscani

DIJKSTRA, E. W. Cooperating Sequential Processes. Technical Report EWD-123,

[HOA74] HOARE, C. A. R. Monitors: An Operating System Structuring Concept. Comm.

OLIVEIRA, R, CARISSIMI, A., TOSCANI, S. Sistemas Operacionais. Srie didtica

SHATZ, S. M. Communication mechanisms for programming distributed systems.

TAFT, S. T. DUFF, R. A. ADA 95 Reference Manual: language and standard

TOSCANI, S., OLIVEIRA, R., CARISSIMI, A., Sistemas Operacionais e

TOSCANI, S. S. Kit de instalao da linguagem VALE4. Disponvel em

PROGRAMAO CONCORRENTE Prof. Simo Toscani

Você também pode gostar