Programação Concorrente - Introdução

Prévia do material em texto

PROGRAMAÇÃO CONCORRENTE – Prof. Simão Toscani 1 
(Do livro Sistemas Operacionais e Programação Concorrente, Toscani S.S., Oliveira R.S. e Carissimi A.S. 
Editora Sagra-Luzzatto, 2003) 
PROGRAMAÇÃO CONCORRENTE 
 
A programação concorrente foi usada inicialmente na construção de sistemas operacionais. 
Atualmente, ela é usada para desenvolver aplicações em todas as áreas da computação. Este tipo 
de programação tornou-se ainda mais importante com o advento dos sistemas distribuídos e das 
máquinas com arquitetura paralela. Neste capítulo serão apresentados os conceitos básicos e os 
mecanismos clássicos da programação concorrente. Maiores detalhes podem ser encontrados no 
livro [TOS03]. 
 
1 Definição 
 
A grande maioria dos programas escritos são programas seqüenciais. Nesse caso, existe 
somente um fluxo de controle (fluxo de execução, linha de execução, thread) no programa. Isso 
permite, por exemplo, que o programador realize uma "execução imaginária" de seu programa 
apontando com o dedo, a cada instante, o comando que está sendo executada no momento. 
Um programa concorrente pode ser visto como se tivesse vários fluxos de execução. 
Para o programador realizar agora uma "execução imaginária", ele vai necessitar de vários dedos, 
um para cada fluxo de controle. 
O termo "programação concorrente" vem do inglês concurrent programming, onde 
concurrent significa "acontecendo ao mesmo tempo". Uma tradução mais adequada seria 
programação concomitante. Entretanto, o termo programação concorrente já está solidamente 
estabelecido no Brasil. Algumas vezes é usado o termo programação paralela com o mesmo 
sentido. 
É comum em sistemas multiusuário que um mesmo programa seja executado 
simultaneamente por vários usuários. Por exemplo, um editor de texto. Entretanto, ter 10 
execuções simultâneas do editor de texto não faz dele um programa concorrente. O que se tem 
são 10 processos independentes executando o mesmo programa seqüencial (compartilhando o 
mesmo código). Cada processo tem a sua área de dados e ignora a existência das outras 
execuções do programa. Esses processos não interagem entre si (não trocam informações). Um 
programa é considerado concorrente quando ele (o próprio programa, durante a sua execução) 
origina diferentes processos. Esses processos, em geral, irão interagir entre si. 
 
2 Motivação 
 
A programação concorrente é mais complexa que a programação seqüencial. Um programa 
concorrente pode apresentar todos os tipos de erros que aparecem nos programas seqüenciais e, 
adicionalmente, os erros associados com as interações entre os processos. Muitos erros dependem 
do exato instante de tempo em que o escalonador do sistema operacional realiza um chaveamento 
de contexto. Isso torna muitos erros difíceis de reproduzir e de identificar. 
Apesar da maior complexidade, existem muitas áreas nas quais a programação 
concorrente é vantajosa. Em sistemas nos quais existem vários processadores (máquinas paralelas 
ou sistemas distribuídos), é possível aproveitar esse paralelismo e acelerar a execução do 
programa. Mesmo em sistemas com um único processador, existem razões para o seu uso em 
vários tipos de aplicações. 
PROGRAMAÇÃO CONCORRENTE – Prof. Simão Toscani 2 
(Do livro Sistemas Operacionais e Programação Concorrente, Toscani S.S., Oliveira R.S. e Carissimi A.S. 
Editora Sagra-Luzzatto, 2003) 
Considere um programa que deve ler registros de um arquivo, colocar em um formato 
apropriado e então enviar para uma impressora física (em oposição a uma impressora lógica ou 
virtual, implementada com arquivos). Podemos fazer isso com um programa seqüencial que, 
dentro de um laço, faz as três operações (ler, formatar e imprimir registro). 
Arqu iv o Proces s o Im pres s o ra
fís i ca
 
Figura 1 - Programa seqüencial acessando arquivo e impressora. 
 
Inicialmente o processo envia um comando para a leitura do arquivo e fica bloqueado. O 
disco então é acionado para realizar a operação de leitura. Uma vez concluída a leitura, o 
processo realiza a formatação e inicia a transferência dos dados para a impressora. Como trata-se 
de uma impressora física, o processo executa um laço no qual os dados são enviados para a porta 
serial ou paralela apropriada. Como o buffer da impressora é relativamente pequeno, o processo 
fica preso até o final da impressão. O disco e a impressora nunca trabalham simultaneamente, 
embora isso seja possível. É o programa seqüencial que não consegue ocupar ambos. 
Vamos agora considerar um programa concorrente como o mostrado na figura 2 para 
realizar a impressão do arquivo. Dois processos dividem o trabalho. O processo leitor é 
responsável por ler registros do arquivo, formatar e colocar em um buffer na memória. O 
processo impressor retira os dados do buffer e envia para a impressora. É suposto aqui que os dois 
processos possuem acesso à memória onde está o buffer. Este programa é mais eficiente, pois 
consegue manter o disco e a impressora trabalhando simultaneamente. O tempo total para realizar 
a impressão do arquivo vai ser menor. 
Arq u iv o
Pro ce s s o
Im p re s s o ra
fís i ca
Pro ce s s o
L e i to r
Im p re s s o r
B u ffe r
 
Figura 2 - Programa concorrente acessando arquivo e impressora. 
 
O uso da programação concorrente é natural nas aplicações que apresentam paralelismo 
intrínseco, ditas aplicações inerentemente paralelas. Nessas aplicações pode-se distinguir 
facilmente funções para serem realizadas em paralelo. Este é o caso do spooling de impressão, 
exemplo que será apresentado a seguir. Pode-se dizer que, em geral, a programação concorrente 
tem aplicação natural na construção de sistemas que tenham de implementar serviços que são 
PROGRAMAÇÃO CONCORRENTE – Prof. Simão Toscani 3 
(Do livro Sistemas Operacionais e Programação Concorrente, Toscani S.S., Oliveira R.S. e Carissimi A.S. 
Editora Sagra-Luzzatto, 2003) 
requisitados de forma imprevisível [DIJ65]. Nesse caso, o programa concorrente terá um processo 
para realizar cada tipo de serviço. 
A seguir é considerado um servidor de impressão para uma rede local. A figura 3 ilustra 
uma rede local na qual existem diversos computadores pessoais (PC) utilizados pelos usuários e 
existe um computador dedicado ao papel de servidor de impressão. O servidor usa um disco 
magnético para manter os arquivos que estão na fila de impressão. 
PCPC PC
Usuários Servidor de Impressão 
Figura 3 - Rede local incluindo um servidor de impressão dedicado. 
 
É importante observar que o programa "servidor de impressão" possui paralelismo 
intrínseco. Ele deve: (1) receber mensagens pela rede; (2) escrever em disco os pedaços de 
arquivos recebidos; (3) enviar mensagens pela rede (contendo, por exemplo, respostas às 
consultas sobre o seu estado); (4) ler arquivos previamente recebidos (para imprimí-los); (5) 
enviar dados para a impressora. Todas essas atividades podem ser realizadas "simultaneamente". 
Uma forma de programar o servidor de impressão é usar vários processos, cada um responsável 
por uma atividade em particular. Obviamente, esses processos vão precisar trocar informações 
para realizar o seu trabalho. 
A figura 4 mostra uma das possíveis soluções para a organização interna do programa 
concorrente "servidor de impressão". Cada círculo representa um processo. Cada flecha 
representa a passagem de dados de um processo para o outro. Essa passagem de dados pode ser 
feita, por exemplo, através de variáveis que são compartilhadas pelos processos envolvidos na 
comunicação. 
Vamos agora descrever a função de cada processo. O processo "Receptor" é responsável 
por receber mensagens da rede local. Ele faz isso através de chamadas de sistema apropriadas e 
descarta as mensagens com erro. As mensagens corretas são então passadas para o processo 
"Protocolo". Ele analisa o conteúdo das mensagens recebidas à luz do protocolo de comunicação 
suportado pelo servidor de impressão. É possívelque seja necessário a geração e o envio de 
mensagens de resposta. O processo "Protocolo" gera as mensagens a serem enviadas e passa-as 
para o processo "Transmissor", que as envia através de chamadas de sistema apropriadas. 
Algumas mensagens contêm pedaços de arquivos a serem impressos. É suposto aqui que o 
tamanho das mensagens tenha um limite (alguns Kbytes). Dessa forma, um arquivo deve ser 
dividido em várias mensagens para transmissão através da rede. Quando o processo "Protocolo" 
identifica uma mensagem que contém um pedaço de arquivo, ele passa esse pedaço de arquivo 
para o processo "Escritor". Passa também a identificação do arquivo ao qual o pedaço em questão 
pertence. Cabe ao processo "Escritor" usar as chamadas de sistema apropriadas para escrever no 
disco. Quando o pedaço de arquivo em questão é o último de seu arquivo, o processo "Escritor" 
passa para o processo "Leitor" o nome do arquivo, que está pronto para ser impresso. 
PROGRAMAÇÃO CONCORRENTE – Prof. Simão Toscani 4 
(Do livro Sistemas Operacionais e Programação Concorrente, Toscani S.S., Oliveira R.S. e Carissimi A.S. 
Editora Sagra-Luzzatto, 2003) 
Receptor Transmissor
Protocolo
Escritor
Leitor Impressor
 
Figura 4 - Servidor de impressão como programa concorrente. 
 
O processo "Leitor" executa um laço no qual ele pega um nome de arquivo, envia o 
conteúdo do arquivo para o processo "Impressor" e então remove o arquivo lido. O envio do 
conteúdo para o processo "Impressor" é feito através de um laço interno composto pela leitura de 
uma parte do arquivo e pelo envio dessa parte. Finalmente, o processo "Impressor" é encarregado 
de enviar os pedaços de arquivo que ele recebe para a impressora. O relacionamento entre os 
processos "Leitor" e "Escritor" foi descrito antes, no início desta seção. 
O servidor de impressão ilustra o emprego da programação concorrente na construção de 
uma aplicação com paralelismo intrínseco. O resultado é uma organização interna clara e simples 
para o programa. Um programa seqüencial equivalente seria certamente menos eficiente. O 
restante deste capítulo é dedicado aos problemas e às técnicas existentes para a construção de 
programas concorrentes como esse. 
Hoje em dia existem várias linguagens que permitem construir programas concorrentes 
(Java, Ada, Pascal Concorrente, C estendido com bibliotecas para concorrência, etc.). Aqui será 
utilizada uma linguagem apropriada para ensino, denominada Vale4 (V4) [TOS04]. 
 
3 Especificação do paralelismo 
 
Para construir um programa concorrente, antes de mais nada, é necessário ter a capacidade de 
especificar o paralelismo dentro do programa. Essa especificação pode ser feita de diversas 
maneiras. Uma delas utiliza os comandos fork, quit e join [CON63]. Outras maneiras serão 
apresentadas na seção 4. 
O comando (ou função) fork pode ser implementado de duas maneiras distintas: ele pode 
criar um novo processo ou criar apenas um novo fluxo de execução dentro de um processo já 
existente. A função fork retorna um número inteiro que é a identificação do novo processo ou do 
novo fluxo criado. Um fluxo de execução também é denominado linha de execução ou thread. 
PROGRAMAÇÃO CONCORRENTE – Prof. Simão Toscani 5 
(Do livro Sistemas Operacionais e Programação Concorrente, Toscani S.S., Oliveira R.S. e Carissimi A.S. 
Editora Sagra-Luzzatto, 2003) 
Os comandos quit e join são 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 operação fork cria um novo processo que é uma cópia idêntica 
(clone) do processo que executa esta operação. Por exemplo, o comando 
 
id = fork() 
 
cria um filho idêntico ao processo que executou a operação (isto é, cria uma cópia do processo 
original). O processo filho recebe cópias das variáveis do processo pai, bem como dos descritores 
de arquivos. Os valores iniciais das variáveis do filho são iguais aos valores das variáveis 
correspondentes do pai no momento da execução da função fork. Observe que não há 
compartilhamento de variáveis: as variáveis do pai ficam no espaço de endereçamento
1
 do pai e 
as variáveis do filho, no espaço de endereçamento do filho. Em relação aos valores dessas 
variáveis, a única diferença inicial entre o pai e o filho é o valor da variável id, que é 0 para o 
filho e é o valor de retorno da função fork para o pai. O valor de retorno é o número de 
identificação 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 código sobre si, através 
da operação exec(P), onde P é um novo programa para ser executado (novo segmento de código 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, porém com uma 
grande diferença: o fork cria uma thread e não um processo. As threads mãe e filha são idênticas: 
executam o mesmo código e compartilham todas as variáveis do processo em que são definidas (é 
justamente nesse compartilhamento que está a diferença para o Unix). 
Na linguagem V4, a execução do comando 
id := fork() 
faz com que a variável global
2
 id receba o valor retornado pela função fork, que é o número único 
 
1
 Basicamente, o espaço de endereçamento de um processo é formado por um segmento de código e um segmento de 
dados. O primeiro contém as instruções do processo e o segundo contém as variáveis e constantes do processo. Além 
disso, todo processo possui uma pilha que é usada para chamadas e retornos de procedimentos. 
2
 Variável declarada no processo hospedeiro, compartilhada entre mãe e filha. 
PROGRAMAÇÃO CONCORRENTE – Prof. Simão Toscani 6 
(Do livro Sistemas Operacionais e Programação Concorrente, Toscani S.S., Oliveira R.S. e Carissimi A.S. 
Editora Sagra-Luzzatto, 2003) 
da thread criada. A thread original (mãe) e a thread criada (filha) executam em paralelo a partir 
do comando que segue ao fork. As duas threads irão se distinguir através da variável denominada 
myNumber
3
. O valor dessa variável é sempre a identificação de quem a refere (isto é, o número 
ú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 mãe } 
Observe que apenas para a thread filha o myNumber é igual ao valor da variável global id. 
Para criar processos (não threads) dinamicamente, a linguagem V4 oferece o comando 
new que será apresentado na seção 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 término do 
descendente imediato (filho ou filha) identificado por id. Se o argumento id não identifica um 
processo ou thread, ou se id não corresponde a um descendente imediato de P, então um erro é 
reportado (erro de execução). 
O argumento de join pode ser também a palavra reservada any, que significa o desejo de 
esperar pelo término de qualquer um dos descendentes imediatos. Nesse caso, no retorno da 
primitiva, a variável any
4
 vai conter a identidade do filho ou filha cuja execução terminou. 
Outra peculiaridade da primitiva join(id) é que ela pode ser usada como função ou como 
subrotina. Usada como função, 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 asformas 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 função.
5
 A propósito, um quit sem argumento equivale a um quit(0). 
Diferença entre thread e processo 
 
O que melhor distingue uma thread de um processo é o espaço de endereçamento. Todas as 
threads de um processo trabalham no mesmo espaço de endereçamento, que é a memória lógica 
do “processo hospedeiro”. Isto é, quando se tem um conjunto de threads dentro de um processo, 
todas as threads executam o código do processo e compartilham as suas variáveis. Por outro lado, 
quando se tem um conjunto de processos, cada processo trabalha num espaço de endereçamento 
próprio, com um conjunto separado de variáveis. 
 
3
 Tudo se passa como se cada processo ou thread tivesse uma variável local, denominada myNumber, contendo o 
número único desse processo ou thread. Na verdade, myNumber, que também pode ser referido como myself ou 
myID, é uma função primitiva que consulta o registro descritor do processo ou thread para obter o número de sua 
“carteira de identidade” e retorna esse número. 
4
 Semelhantemente ao que ocorre com myNumber, tudo se passa como se cada processo ou thread tivesse uma 
variável local, denominada any. 
5
 No caso de ser usada como subrotina, a primitiva join(id) desconsidera o valor informado pelo descendente id. 
PROGRAMAÇÃO CONCORRENTE – Prof. Simão Toscani 7 
(Do livro Sistemas Operacionais e Programação Concorrente, Toscani S.S., Oliveira R.S. e Carissimi A.S. 
Editora Sagra-Luzzatto, 2003) 
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. 
É mais fácil chavear a execução entre threads (de um mesmo processo) do que entre 
processos, pois tem-se menos informações para salvar e restaurar. Por esse motivo, as threads são 
chamadas também de "processos leves". 
 
Um exemplo 
 
Vamos usar a linguagem V4 para exemplificar o uso dos comandos fork, join e quit. O programa 
mostrado na figura 5 possui um único processo. A linha de execução inicial desse processo 
executa duas vezes o comando fork, criando duas threads adicionais (filhas 1 e 2). A thread 
original então espera que cada uma das filhas termine, escreve uma mensagem para cada uma e 
termina também. As duas threads criadas apenas colocam uma mensagem na tela e terminam. 
 
 
V4program 
 process p1; 
 f1: integer; /* identifica filha 1*/ 
 f2: integer; /* 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. 
 O comando write(X) escreve na tela do terminal do usuário. O argumento X pode ser uma 
constante, uma variável, um elemento de array ou um string entre apóstrofes. O comando nl 
(“new line”) faz com que a próxima impressão seja feita em uma nova linha. Duas possíveis 
saídas para o programa anterior seriam: 
Alo da mae Alo da mae 
Alo do filha 1 Alo do filha 1 
Alo do filha 2 Filha 1 morreu 
Filha 1 morreu Alo do filha 2 
Filha 2 morreu Filha 2 morreu 
PROGRAMAÇÃO CONCORRENTE – Prof. Simão Toscani 8 
(Do livro Sistemas Operacionais e Programação Concorrente, Toscani S.S., Oliveira R.S. e Carissimi A.S. 
Editora Sagra-Luzzatto, 2003) 
4 Criação estática e criação dinâmica de processos 
 
Os processos de um programa concorrente podem ser criados de forma estática ou dinâmica. No 
primeiro caso, o programa contém a declaração de um conjunto fixo de processos, os quais são 
ativados simultaneamente, no inicio da execução do programa. No segundo caso, os processos 
são criados dinamicamente, durante a execução, através de instruções especiais para esse fim. 
Os mecanismos vistos até aqui (fork, join e quit) realizam criação dinâmica (e término 
dinâmico), pois os processos (ou threads) são criados somente quando instruções especiais são 
executadas.
6
 
 
Criação estática 
 
No caso da criação estática, os processos são declarados explícitamente
7
 no programa fonte e 
vão existir desde o início da execução do programa concorrente. Normalmente, as linguagens de 
programação permitem especificar esses processos de duas maneiras: como processos individuais 
ou como um array de processos. 
 
Especificação 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 não compartilham variáveis 
(não existem variáveis globais no programa). Cada processo utiliza uma variável local, 
denominada k. O primeiro imprime 10 vezes o número 1 e o segundo, em paralelo, imprime 10 
vezes o número 2. O resultado da execução pode ser qualquer seqüência de tamanho 20, contendo 
 
6
 Por exemplo, se a execução não “passa” por uma determinada instrução fork, então a thread correspondente não é 
criada. 
7
 A declaração explícita consiste em definir, para cada processo do programa, as suas variáveis locais e o seu 
segmento de código. 
PROGRAMAÇÃO CONCORRENTE – Prof. Simão Toscani 9 
(Do livro Sistemas Operacionais e Programação Concorrente, Toscani S.S., Oliveira R.S. e Carissimi A.S. 
Editora Sagra-Luzzatto, 2003) 
10 vezes o número 1 e 10 vezes o número 2, embaralhados. Teoricamente, são possíveis 
20!/(10!*10!) resultados diferentes.
8
 
 
Array de processos 
Neste caso, uma única declaração especifica um grupo de processos semelhantes, que se 
distinguem apenas pelo valor de uma variável local inteira, que é especificada no cabeçalho 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 variável local i vale 1 e para o segundo, a sua variável 
local i vale 2. Este programa é equivalente ao anterior. 
 
Criação dinâmica 
 
É possível declarar explicitamente um modelo (uma "forma") para criar processos durante a 
execução, conforme é ilustrado a seguir. Neste caso tem-se o que se denomina criação dinâmica 
com declaração explícita 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 
 Através da especificação process type, explicita-se um modelo (template) de processo, o 
qual é utilizado para criar exemplares (cópias, clones) desse processo durante a execução. A 
criação de um novo exemplar se dá através do comando new, o qual permite passar parâmetros 
para o processo criado. No caso da linguagem Vale4, a primitiva new pode ser usada como8
 Combinações de uma seqüência de 20 escaninhos, escolhidos 10 a 10. 
PROGRAMAÇÃO CONCORRENTE – Prof. Simão Toscani 10 
(Do livro Sistemas Operacionais e Programação Concorrente, Toscani S.S., Oliveira R.S. e Carissimi A.S. 
Editora Sagra-Luzzatto, 2003) 
função ou como subrotina; usada como função ela retorna a identificação interna (pid) do 
processo criado. 
 
5 Exemplos de programas concorrentes 
 
Esta seção apresenta programas simples que ilustram características 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 
notação: os identificadores declarados (variáveis, procedimentos, etc.) são apresentados em 
itálico. 
 
Compartilhamento de um procedimento 
 
O mesmo programa que foi utilizado na seção 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 número a ser impresso. 
Como nos exemplos anteriores, o resultado da execução desse programa é imprevisível, sendo 
possíveis (teoricamente) 1020C resultados distintos. 
Observação sobre as variáveis de um procedimento 
No exemplo anterior, existem duas execuções concorrentes do procedimento imprime, uma 
efetuada por P1 e outra por P2. Cada uma dessas execuções utiliza variáveis i (argumento) e k 
(variável local do procedimento). A observação importante é que cada processo utiliza cópias 
independentes dessas variáveis. O código do procedimento é compartilhado pelos dois processos, 
mas os dados (variáveis i e k) são privativos de cada processo. Isto é, cada processo trabalha sobre 
um conjunto de dados separado. 
Não se pode esquecer que, na chamada de um procedimento, os argumentos e as variáveis 
locais desse procedimento são alocados na pilha do processo chamador. Como cada processo (ou 
thread) trabalha com uma pilha própria, as execuções não interferem uma com a outra. Na 
programação concorrente é sempre assim, todo procedimento é automaticamente reentrável (ou 
puro). Isto significa que o mesmo código pode ser executado simultaneamente por vários 
PROGRAMAÇÃO CONCORRENTE – Prof. Simão Toscani 11 
(Do livro Sistemas Operacionais e Programação Concorrente, Toscani S.S., Oliveira R.S. e Carissimi A.S. 
Editora Sagra-Luzzatto, 2003) 
processos sem que haja interferência entre eles, pois cada processo utiliza um conjunto separado 
de parâmetros e de variáveis locais. 
 
Compartilhamento de uma variável 
O programa a seguir implementa um sistema concorrente onde dois processos compartilham uma 
variável global S. Cada processo incrementa S de uma unidade, 100 vezes. 
V4program 
 S : integer init 0; 
 process p1; 
 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 são 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 execução vai para o comando seguinte ao endloop) 
quando a condição <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 espaços em branco no terminal do usuário, sendo útil para formatar a 
impressão de resultados. 
Observação sobre a inicialização de variáveis 
Em V4, as variáveis não explicitamente inicializadas possuem valor inicial igual a 0, se inteiras, e 
igual a false, se booleanas. Quando usada, a cláusula initial (ou init) deve ser seguida de um 
único valor inicial. Se o uso é na declaração de uma lista de identificadores, então todos os 
PROGRAMAÇÃO CONCORRENTE – Prof. Simão Toscani 12 
(Do livro Sistemas Operacionais e Programação Concorrente, Toscani S.S., Oliveira R.S. e Carissimi A.S. 
Editora Sagra-Luzzatto, 2003) 
identificadores da lista recebem esse único valor inicial. Se o uso é na declaração de um array, 
todos os elementos do array recebem esse único valor especificado. 
 
O problema da exclusão mútua 
No programa anterior, tem-se 2 processos manipulando a variável global S. Cada processo 
executa 100 vezes o comando S:=S+1. Este comando é compilado para a seguinte seqüência de 
código de máquina: 
push S % coloca o valor de S na pilha 
push $1 % coloca a constante 1 na pilha 
add % soma os dois últimos valores colocados na pilha 
pop S % guarda o resultado em S 
 
 Como os pontos em que a UCP passa de um processo para outro são imprevisíveis, pode 
acontecer de um processo perder a UCP no meio da seqüência 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 seqüência acima e armazenar o valor 11 em S. Todos 
os acréscimos a S feitos pelo outro processo nesse ínterim são perdidos. Como conseqüência, 
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 exclusão mútua no acesso à 
variável S, isto é, enquanto um processo estiver manipulando S, o outro não pode acessar S. 
 A exclusão mútua é um requisito muito importante nos sistemas concorrentes. Em geral, 
é necessário garantir o acesso exclusivo aos dados compartilhados. A exclusão mútua só não 
é necessária quando os dados são compartilhados na modalidade "apenas leitura", isto é, quando 
os dados não são alterados pelos processos. Os trechos dos processos onde os dados 
compartilhados são manipulados, são denominados trechos críticos ou regiões críticas. 
 
Criação dinâmica de processos 
A criação dinâmica (e recursiva) de processos é ilustrada através do problema da torre de Hanói, 
descrito a seguir. Tem-se 3 torres (pilhas) e n discos de tamanhos diferentes. Inicialmente os n 
discos estão 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 intermediária nessas movimentações. 
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 intermediária. Para movimentar n discos de 
a para b, usando c como torre intermediária, um escravo Hanoi faz o seguinte. Se n = 1 (só tem 
um disco para movimentar), então o trabalho é fácil e direto: o escravo movimenta o único disco 
de a para b (e mostra essa movimentação). Caso contrário, o escravo cria um escravo_1 para 
movimentar n-1 discos de a para c, usando b como torre intermediária. Quando esse serviço é 
concluído (escravo_1 termina o seu trabalho), o escravo original movimenta o disco que lhe 
 
9
 Sempre que um processo perde a UCP, o seu estado é salvo. Mais tarde, a execução do processo continua, como se 
nada tivesse acontecido. 
PROGRAMAÇÃO CONCORRENTE – Prof. SimãoToscani 13 
(Do livro Sistemas Operacionais e Programação Concorrente, Toscani S.S., Oliveira R.S. e Carissimi A.S. 
Editora Sagra-Luzzatto, 2003) 
sobrou (que é o maior) de a para b (mostra essa movimentação) e cria um escravo_2 para concluir 
o serviço, que é movimentar n-1 discos de c para b usando a como torre intermediária. 
 
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) 
 }; 
 process P; new Hanoi(3, 1, 2, 3) 
endprogram 
O resultado da execução deste programa será a ordem em que os discos deverão ser 
movimentados (movimento por movimento, um disco por vez). 
 
6 Sincronizações básicas 
 
É comum um processo ter que esperar até que uma condição se torne verdadeira. Para essa espera 
ser "eficiente", o processo deve esperar no estado bloqueado (sem competir pela UCP). Dois tipos 
de bloqueio são considerados básicos: 
1. bloquear até que um recurso se torne disponível;10 
2. bloquear até que chegue um sinal de outro processo. 
Estes bloqueios são caracterizados pelas operações básicas lock/unlock e block/wakeup(P), 
descritas a seguir. Enquanto o primeiro par (lock/unlock) implementa sincronização do tipo 
exclusão mútua, o segundo par implementa uma forma básica de comunicação. 
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 estão bloqueados 
por terem executado um lock (enquanto a fechadura estava trancada). Se a fila está vazia, a 
fechadura é destrancada (isto é, é deixada aberta). 
 
10
 O recurso pode ser, inclusive, "o direito de acessar os dados compartilhados". 
PROGRAMAÇÃO CONCORRENTE – Prof. Simão Toscani 14 
(Do livro Sistemas Operacionais e Programação Concorrente, Toscani S.S., Oliveira R.S. e Carissimi A.S. 
Editora Sagra-Luzzatto, 2003) 
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 não se bloqueia ao executar o 
block. Na linguagem Vale4, o argumento de wakeup pode ser um nome de processo ou um 
número único de processo ou thread. 
 Na verdade, os comandos lock e unlock não formam uma estrutura sintática (isto é, não 
precisam estar casados, como se fossem um abre e fecha parênteses), eles são comandos 
independentes. Na linguagem Vale4, as operações lock e unlock também podem ser referidas 
pelos nomes mutexbegin e mutexend, respectivamente. 
 
7 Semáforos 
 
As variáveis semáforas são variáveis especiais que admitem apenas duas operações, denominadas 
P e V.
11
 Sendo S é uma variável semáfora, as operações P e V têm a seguinte semântica: 
• P(S) : espera até S ser maior que 0 e então subtrai 1 de S; 
• V(S) : incrementa S de 1. 
As operações “testar S e subtrair 1 (se S > 0)” e “incrementar S de 1” são executadas de 
forma atômica (indivisível), 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 variável semáfora e um vaso contendo bolitas (bolinhas 
de gude). O valor numérico do semáforo corresponde ao número de bolitas dentro do vaso. Uma 
operação V corresponde a pôr uma bolita no vaso. Cada operação P tenta remover uma bolita; se 
nenhuma está disponível, então a operação bloqueia o processo e o coloca numa fila de espera. 
Quando uma bolita é colocada no vaso (operação V), ela é removida pelo primeiro processo da 
fila de espera, o qual prossegue sua execução. 
Sincronizações básicas com semáforos 
 
As variáveis semáforas permitem implementar os dois tipos básicos de bloqueio, conforme é 
explicado a seguir. 
 
Sincronização tipo lock/unlock: 
A sincronização do tipo exclusão mútua é implementada através de um semáforo com valor 
inicial 1. O acesso exclusivo a n regiões críticas seria implementado como segue: 
 X : semaphore initial 1 
 
11
 P e V são as iniciais das palavras holandesas Proberen e Verhogen, que significam testar e incrementar, 
respectivamente. 
PROGRAMAÇÃO CONCORRENTE – Prof. Simão Toscani 15 
(Do livro Sistemas Operacionais e Programação Concorrente, Toscani S.S., Oliveira R.S. e Carissimi A.S. 
Editora Sagra-Luzzatto, 2003) 
 P1: P2: . . . Pn: 
 . . . . . . . . . 
 P(X); P(X); P(X); 
 REGIÃO CRÍTICA; REGIÃO CRÍTICA; REGIÃO CRÍTICA; 
 V(X); V(X); V(X); 
 . . . . . . . . . 
 
Sincronização tipo block/wakeup(P): 
Este tipo de sincronização é implementado através de um semáforo com valor inicial zero. Por 
exemplo, se a operação B do processo P1 deve ser executada após a operação A do processo P2, 
programa-se da seguinte maneira: 
 Y : semaphore initial 0 
 P1: P2: 
 . . . . . . 
 P(Y); % block . . . 
 B; A; 
 . . . V(Y); % wakeup(P1) 
 . . . . . . 
 
8 Programas clássicos 
 
Esta seção apresenta 4 problemas clássicos da programação concorrente, todos resolvidos através 
do uso de semáforos 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 
posições. 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 relação 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 programação 
desse sistema com buffer de 5 posições e supondo que as mensagens sejam números inteiros, é 
mostrada a seguir. 
 
Variáveis globais: buffer: array[5] of integer; 
 cheios: semaphore initial 0; 
 vazios: semaphore initial 5; 
PROGRAMAÇÃO CONCORRENTE – Prof. Simão Toscani 16 
(Do livro Sistemas Operacionais e Programação Concorrente, Toscani S.S., Oliveira R.S. e Carissimi A.S. 
Editora Sagra-Luzzatto, 2003) 
Processo produtor: Processo consumidor: 
 msg, in : integer; msg, out : integer; 
 loop loop 
 % produz mensagem msg P(cheios); 
 P(vazios); out:= (out mod 5)+1; 
 in:= (in mod 5)+1; msg:= buffer[out]; 
 buffer[in]:= msg; V(vazios); 
 V(cheios) % consome a mensagem 
 endloop endloop 
O semáforo cheios conta o número de buffers cheios e o semáforo vazios conta número de 
buffers vazios. Conforme já foi referido, as variáveis inteiras que não são inicializadas tem seu 
valor inicial igual a zero. 
Observe que a solução não se preocupou em garantir exclusão mútua no acesso ao buffer. 
Isto porque os dois processos trabalham com variáveis locais in, out e msg e, certamente, irão 
acessar sempre posições diferentes do vetor global buffer. 
Jantar dos Filósofos 
 
Este problema ilustra as situações de deadlock e de postergação indefinida que podem ocorrer em 
sistemas nos quais processos adquirem e liberam recursoscontinuamente. 
Existem N filósofos 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 
situação para 5 filósofos. Como a massa é muito escorregadia, ela requer dois garfos para ser 
comida. Na mesa existem N garfos, um entre cada dois filósofos, e os únicos garfos que um 
filósofo pode usar são os dois que lhe correspondem (o da sua esquerda e o da sua direita). O 
problema consiste em simular o comportamento dos filósofos procurando evitar situações de 
deadlock (bloqueio permanente) e de postergação indefinida (bloqueio por tempo indefinido). 
 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
 
Figura 6 - A mesa dos 5 filósofos 
Da definição do problema, tem-se que nunca dois filósofos adjacentes poderão comer ao 
mesmo tempo e que, no máximo, N/2 filósofos poderão estar comendo de cada vez. Na solução a 
seguir, iremos nos concentrar no caso de 5 filósofos. Os garfos são representados por um vetor de 
PROGRAMAÇÃO CONCORRENTE – Prof. Simão Toscani 17 
(Do livro Sistemas Operacionais e Programação Concorrente, Toscani S.S., Oliveira R.S. e Carissimi A.S. 
Editora Sagra-Luzzatto, 2003) 
semáforos e é adotada a seguinte regra: todos os 5 filósofos pegam primeiro o seu garfo da 
esquerda, depois o da direita, com exceção de um deles, que é do contra. Pode ser demonstrado 
que esta solução é livre de deadlocks. Foi escolhido o filósofo 1 para ser do contra. 
O programa a seguir é um programa Vale4 completo, no qual cada filósofo faz 10 
refeições 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); 
 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 
características. A barbearia tem uma sala de espera com N cadeiras e uma cadeira de barbear. Se 
não 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 disponível) ou vai embora (se todas as cadeiras estão 
ocupadas). 
PROGRAMAÇÃO CONCORRENTE – Prof. Simão Toscani 18 
(Do livro Sistemas Operacionais e Programação Concorrente, Toscani S.S., Oliveira R.S. e Carissimi A.S. 
Editora Sagra-Luzzatto, 2003) 
A solução a seguir usa 3 semáforos: clientes, fila e mutex. O semáforo clientes tranca o 
barbeiro, sendo suas “bolitas” produzidas pelos clientes que chegam. O valor desse semáforo 
indica o número de clientes à espera (excluindo o cliente na cadeira do barbeiro, que não está à 
espera). O semáforo fila tranca os clientes e implementa a fila de espera. O semáforo mutex 
garante exclusão mútua. Também é usada uma variável inteira, count, que conta o número de 
clientes à espera. O valor desta variável é sempre igual ao “número de bolitas” do semáforo 
clientes. 
Um cliente que chega na barbearia verifica o número de clientes à espera. Se esse número 
é menor que o número de cadeiras, o cliente espera, caso contrário, ele vai embora. A solução é 
apresentada a seguir, considerando o número de cadeiras na sala de espera igual a 3. 
Inicialmente, o barbeiro executa a operação P(clientes), onde fica bloqueado (dormindo) 
até a chegada de algum cliente. Quando chega um cliente, ele começa adquirindo a exclusão 
mútua. Outro cliente que chegar imediatamente após, irá se bloquear até que o primeiro libere a 
exclusão mútua. Dentro da região crítica, o cliente verifica se o número de pessoas à espera é 
menor ou igual ao número de cadeiras. Se não é, ele libera mutex e vai embora sem cortar o 
cabelo. 
Se tem alguma cadeira disponível, o cliente incrementa a variável count e executa a 
operação V no semáforo clientes. Se o barbeiro está dormindo, ele é acordado; caso contrário, é 
adicionada uma “bolita” no semáforo clientes. A seguir, o cliente libera a exclusão mútua e entra 
na fila de espera. O barbeiro adquire a exclusão mútua, decrementa o número de clientes, pega o 
primeiro da fila de espera e vai fazer o corte. 
Variáveis globais: clientes, fila: semaphore init 0; 
 mutex: semaphore init 1; 
 count : integer initial 0; 
Processo barbeiro: Processo cliente: 
 loop P(mutex); 
 P(clientes); /*dorme, se for o caso*/ if count < 3 
 P(mutex); then { count:= count+1; 
 count:= count –1; V(clientes); /*acorda o barbeiro*/ 
 V(fila); /*pega próximo cliente*/ V(mutex); 
 V(mutex); P(fila); /*espera o barbeiro*/ 
 /*corta o cabelo*/ /*corta o cabelo*/ 
 endloop } 
 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 próximo cliente. Se tem cliente, o barbeiro faz outro corte. Se não tem, 
o barbeiro dorme. 
PROGRAMAÇÃO CONCORRENTE – Prof. Simão Toscani 19 
(Do livro Sistemas Operacionais e Programação Concorrente, Toscani S.S., Oliveira R.S. e Carissimi A.S. 
Editora Sagra-Luzzatto, 2003) 
Leitores e escritores 
 
O problema dos readers and writers [COU71] ilustra outra situação comum em sistemas de 
processos concorrentes. Este problema surge quando processos executam operações de leitura e 
de atualização sobre um arquivo global (ou sobre uma estrutura de dados global). A sincronização 
deve ser tal que vários readers (isto é, processos leitores, que não alteram a informação) possam 
utilizar o arquivo simultaneamente. Entretanto, qualquer processo writer deve ter acesso 
exclusivo ao arquivo. 
 Na solução a seguir é dada prioridade para os processos readers. São utilizadas duas 
variáveis semáforas, mutex e w, para exclusão mútua, e uma variável inteira nr, para contar o 
número de processos leitores ativos. Note que o primeiro reader bloqueia o progresso dos writers 
que chegam após ele, através do semáforo w. Enquanto houver reader ativo, os writers ficarão 
bloqueados. 
Variáveis globais: mutex, w : semaphore initial 1; 
 nr : integer initial 0; 
 Processo leitor: 
 . . . 
 P(mutex); Processo escritor: 
 nr:=nr+1; . . . 
 if nr=1 then P(w); . . . 
 V(mutex); P(w); 
 READ WRITE 
 P(mutex); V(w); 
 nr:=nr-1; . . . 
 if nr=0 then V(w); . . . 
 V(mutex); 
 . . . 
PROGRAMAÇÃO CONCORRENTE – Prof. Simão Toscani 20 
(Do livro Sistemas Operacionais e Programação Concorrente, Toscani S.S., Oliveira R.S. e Carissimi A.S. 
Editora Sagra-Luzzatto, 2003) 
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, 
TechnologicalUniversity, 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. Série didática 
do II-UFRGS, 2004 (3
ª
 edição). 
[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 
Programação Concorrente. Série didática do II-UFRGS, 2003. 
[TOS04] TOSCANI, S. S. Kit de instalação da linguagem VALE4. Disponível em 
www.inf.pucrs.br/~stoscani/V4.