Embed Size (px)
Citation preview
João Vitor Mallmann
Programação Concorrente Segura em Java
Florianópolis
Fevereiro de 2007
João Vitor Mallmann
Programação Concorrente Segura em Java
Trabalho de conclusão de curso apresentadocomo parte dos requisitos para obtenção do graude Bacharel em Ciências da Computação
Orientador:
José Mazzucco Júnior
BACHARELADO EM CIÊNCIAS DA COMPUTAÇÃO
DEPARTAMENTO DE INFORMÁTICA E ESTATÍSTICA
CENTRO TECNOLÓGICO
UNIVERSIDADE FEDERAL DE SANTA CATARINA
Florianópolis
Fevereiro de 2007
Resumo
Com o aumento da complexidade dos sistemas computacionais veio à necessidade da uti-lização softwares que possam agir de forma concorrente, utilizando-se o conceito de threadpara isso. Porém, o sincronismo e o escalonamento das threads de Java são mal especificados,deixando a cargo do sistema operacional a especificação destas regras, gerando desempenhosdiferentes ao utilizar sistemas operacionais distintos. A liberdade da programação concorrenteem Java aumenta o perigo de hazards, deadlock, livelock e starvation, problemas comuns aaplicações multithread. Tais problemas podem ser evitados com a utilização de CTJ, uma bib-lioteca que implementa o conceito de Communicating Seqüencial Process (CSP), uma teoriamatemática para descrição de computação concorrente e distribuída, que garante a ausência dosproblemas citados acima através de regras algébricas. Este trabalho tem como objetivo com-parar aplicações desenvolvidas em Java e aplicações desenvolvidas utilizando-se a bibliotecaCTJ.
Lista de Algoritmos
1 Canal estendendo um linkdriver. . . . . . . . . . . . . . . . . . . . . . . . . p. 24
2 Exemplo de uma classe que implementa a interface de Processo. . . . . . . . p. 25
3 Criando e executando um processo. . . . . . . . . . . . . . . . . . . . . . . p. 26
4 Construtor de composição seqüencial. . . . . . . . . . . . . . . . . . . . . . p. 26
5 Exemplo de uma composição seqüencial. . . . . . . . . . . . . . . . . . . . p. 27
6 Adição de um novo processo à composição seqüencial. . . . . . . . . . . . . p. 27
7 Adição de vários novos processos a composição seqüencial. . . . . . . . . . p. 27
8 Inserção de processo em determinada posição na composição seqüencial . . . p. 27
9 Remoção de processos da composição seqüencial . . . . . . . . . . . . . . . p. 27
10 Construtor de composição Paralelo. . . . . . . . . . . . . . . . . . . . . . . p. 28
11 Exemplo de uma composição Paralela. . . . . . . . . . . . . . . . . . . . . . p. 28
12 Adição de um novo processo a composição Paralela. . . . . . . . . . . . . . p. 28
13 Adição de vários novos processos a composição Paralela. . . . . . . . . . . . p. 28
14 Remoção de processos da composição seqüencial. . . . . . . . . . . . . . . . p. 29
15 Construtor de composição Paralelo com prioridade. . . . . . . . . . . . . . . p. 29
16 Exemplo de uma composição Paralelo com prioridade. . . . . . . . . . . . . p. 30
17 Exemplo de uma construção aninhada da composição Paralela com priori-
dade, aumentando os níveis de prioridade. . . . . . . . . . . . . . . . . . . . p. 31
18 Adição de um novo processo a composição Paralela com prioridade. . . . . . p. 31
19 Adição de vários novos processos a composição Paralela com prioridade. . . p. 31
20 Inserção de processo em determinada posição na composição Paralela com
prioridade. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 32
21 Remoção de processos da composição Paralela com prioridade. . . . . . . . . p. 32
22 Construtor de composição Alternativo. . . . . . . . . . . . . . . . . . . . . . p. 32
23 Exemplo de uma composição Alternativa. . . . . . . . . . . . . . . . . . . . p. 32
24 Inserção de um novo Guard na composição Alternativa. . . . . . . . . . . . . p. 33
25 Inserção de vários Guard na composição Alternativa. . . . . . . . . . . . . . p. 33
26 Remoção de Guard da composição Alternativa. . . . . . . . . . . . . . . . . p. 33
27 Declaração de um objeto da classe PriAlternative. . . . . . . . . . . . . . . . p. 33
28 Exemplo de uma composição Alternativa com prioridade, . . . . . . . . . . . p. 34
29 Adição de um novo guarda a composição PriAlternative. . . . . . . . . . . . p. 34
30 Adição de vários guardas a composição PriAlternative. . . . . . . . . . . . . p. 34
31 Adição de vários guardas a composição PriAlternative. . . . . . . . . . . . . p. 34
32 Adição de vários guardas a composição PriAlternative. . . . . . . . . . . . . p. 35
33 Exemplo de composição aninhada, composição paralela com duas composições
seqüenciais aninhadas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 35
34 Exemplo de composição aninhada, composição alternativa com duas com-
posições aninhadas, uma paralela e outa seqüencial. . . . . . . . . . . . . . . p. 36
35 Criando um objeto da classe Guard. . . . . . . . . . . . . . . . . . . . . . . p. 36
36 Execução condicional de um Guard. . . . . . . . . . . . . . . . . . . . . . . p. 37
37 Declaração de um Guarda condicional. . . . . . . . . . . . . . . . . . . . . . p. 37
38 Declaração de um Guarda incondicional. . . . . . . . . . . . . . . . . . . . . p. 37
39 Parte 1 da classe Mesa, da aplicação Jantar dos filósofos implementada em
CTJ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 47
40 Parte 2 da classe Mesa, da aplicação Jantar dos filósofos implementada em
CTJ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 48
41 Parte 3 da classe Mesa, da aplicação Jantar dos filósofos implementada em
CTJ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 49
42 Classe Filosofo, da aplicação Jantar dos filósofos implementada em CTJ. . . . p. 50
43 Classe JantarDosFilosofos, da aplicação Jantar dos filósofos implementada
em CTJ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 51
44 Classe Mesa, da aplicação Jantar dos filósofos implementada em Java. . . . . p. 52
45 Classe Filosofo, da aplicação Jantar dos filósofos implementada em Java. . . p. 53
46 Classe Main, da aplicação Jantar dos filósofos implementada em Java. . . . . p. 54
Sumário
Lista de Figuras
1 Introdução p. 10
1.1 Tema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 11
1.2 Limitações do tema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 12
1.3 Objetivo geral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 12
1.4 Desenvolvimento do trabalho . . . . . . . . . . . . . . . . . . . . . . . . . p. 12
1.5 Motivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 13
2 Communicating Sequencial Process (CSP) p. 14
2.1 Diferenças entre threads de Java e processos CSP . . . . . . . . . . . . . . . p. 15
2.2 Primitivas de sincronização . . . . . . . . . . . . . . . . . . . . . . . . . . p. 16
3 Processos CTJ p. 18
3.1 Estados de transição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 19
3.1.1 Estados de transição da thread. . . . . . . . . . . . . . . . . . . . . p. 19
3.1.2 Estados de transição de um processo CTJ. . . . . . . . . . . . . . . p. 20
4 Canais CTJ p. 22
4.1 Independente de hardware: . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 23
4.2 Dependente de hardware: . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 23
5 Utilizando CTJ p. 25
5.1 Criando processos em Java . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 25
5.2 Composição de processos . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 26
5.2.1 Construtor de Composição Seqüencial - Sequencial . . . . . . . . . p. 26
5.2.2 Construtor de Composição Paralelo - Parallel . . . . . . . . . . . . . p. 28
5.2.3 Construtor de Composição Paralelo baseado em Prioridade - PriPar-
allel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 29
5.2.4 Construtor de Composição Alternativo - Alternative . . . . . . . . . p. 32
5.2.5 Construtor de Composição Alternativo baseado em Prioridade - Pri-
Alternative . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 33
5.2.6 Construtor de Composição Aninhados . . . . . . . . . . . . . . . . . p. 35
5.3 Guardas Condicionais e Incondicionais . . . . . . . . . . . . . . . . . . . . . p. 36
6 Validação do programas CSP p. 38
7 Comparação entre aplicações utlizando CTJ e Java p. 40
8 Conclusão p. 45
Apêndice A -- Classe MesaCTJ p. 47
Apêndice B -- Classe FilosofoCTJ p. 50
Apêndice C -- Classe JantarDosFilosofosMain p. 51
Apêndice D -- Classe MesaJava p. 52
Apêndice E -- Classe FilosofoJava p. 53
Apêndice F -- Classe MainJava p. 54
Referências p. 55
Lista de Figuras
1 Interface de processo (HILDERINK et al., 1997). . . . . . . . . . . . . . . . . . p. 18
2 Diagrama de transição de estados das threads. . . . . . . . . . . . . . . . . . p. 20
3 Diagrama de transição de estados dos processos (HILDERINK et al., 1997). . . . p. 21
4 Interface de canal CTJ (HILDERINK et al., 1997). . . . . . . . . . . . . . . . . p. 23
5 Arquitetura do cálculo de verificação (KLEBANOV et al., 2005). . . . . . . . . p. 39
6 Rede de processos do Jantar dos Filósofos. . . . . . . . . . . . . . . . . . . . p. 41
7 Duas threads tomando posse de regiões críticas distintas. . . . . . . . . . . . p. 42
8 Deadlock gerado pela tentativa de das thread à regiões críticas bloqueadas. . . p. 42
9 Rede de processos do exemplo de não ocorrência de deadlock em CTJ. . . . . p. 43
10 Processo1 acessando o recurso 1, e o Processo2 acessando o recurso 2. . . . . p. 43
11 Processo1 acessando o recurso 2, e o Processo2 acessando o recurso 1, sem a
ocorrência de deadlock. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 44
10
1 Introdução
Apesar da implementação de aplicações multithread em Java não ser difícil, a sua utilização
de forma correta requer muito esforço. O raciocínio sobre aplicações utilizando threads, pode
ser diferente para cada programa construído. Threads são as principais causas no aumento na
complexidade das aplicações concorrentes. Como resultado, programas multithread são muito
mais suscetíveis a erros.
A sincronização e o escalonamento de Java são mal especificados, gerando um desempenho
de tempo real insatisfatório(HILDERINK et al., 1997). A linguagem Java deixa a cargo do sistema
operacional a especificação das regras para a sincronização e escalonamento, podendo resultar
em desempenhos diferentes ao utilizar sistemas operacionais distintos (SUN, 2006e). O sin-
cronismo, que é baseado em monitores e transferência de dados, é implementado através do
compartilhamento de memória (KLEBANOV et al., 2005).
O núcleo do modelo de threads de Java é derivado dos conceitos tradicionais de multithread-
ing. A literatura sobre threads e sincronização de threads é na maior parte sobre a compreensão
do sistema operacional ou dos conceitos de baixo nível de multithreading (HILDERINK et al.,
1997). A liberdade dada pelas APIs para a utilização de threads aumentam os perigos de cor-
rida de hazards, deadlock, livelock, starvation. O programador deve ter muito cuidado, e deve
aplicar um grande conjunto de regras, normas ou padrões de projeto.
Corrida de hazards (race hazards) é uma das conseqüências da sincronização incorreta,
gerando a disputa de recursos do sistema por múltiplas threads, é o corrompimento dos dados,
onde parte dos dados é modificado por uma thread e parte por outra. Deadlock é uma situação
na qual uma thread é bloqueada para sempre porque está esperando certa condição se tornar
11
verdadeira, mas a condição é impedida de se tornar verdadeira, pois o trecho de código, que está
de posse de um thread, que deveria habilitar está condição também está bloqueado. Um livelock,
diferente do deadlock, acontece quando as threads estão em execução, mas nada acontece, isso
ocorre geralmente quando duas threads então trabalhando com intenções contrarias, o que é
feito por uma thread é desfeito pela outra. Starvation ocorre quando uma thread é bloqueada por
tentar o acesso a um recurso que está sendo utilizado por outra thread, porém a thread bloqueada
nunca irá executar novamente por não ter acesso ao recurso desejado, pois o mesmo não será
liberado pela thread que o detém, ou por outras threads de maior prioridade também tentar o
acesso a esse recurso, starvation é uma conseqüência do fato que as primitivas wait/notify da
linguagem Java não garantem a "sobrevivência" da thread.
Analisar um programa multithread e eliminar os erros de estados das threads pode ser ex-
tremamente difícil utilizando uma interface de programação (API). Métodos teóricos foram
desenvolvidos para analisar o comportamento de aplicações multithread e eliminar os perigos
gerados por ela, porém são pouco eficazes e nada práticos. Para tentar evitar os problemas
gerados pela programação multithread de Java, pode-se utilizar o conceito de Communicating
Seqüencial Process (CSP) (HOARE, 1983).
1.1 Tema
A criação de sistemas de tempo real está cada vez mais em evidência, sendo necessário para
isso a utilização de softwares que possam agir de forma concorrente, utilizando-se o conceito
de threads pra obtêr la.
Com a liberdade e flexibilidade dada pelas APIs, o desenvolvimento de aplicações uti-
lizando processamento multithread ficou simplificado, resultando em sistemas defeituosos, de-
vido ao perigo da ocorrência de condições indesejadas, tais como corridas de hazards, deadlock,
livelock e starvation (negação de serviços infinita).
Desta forma, deve se tomar cuidado com cada tipo de sincronismo utilizado nas threads de
uma aplicação, utilizando um conjunto de regras, normas e padrões de projeto.
12
1.2 Limitações do tema
O trabalho desenvolvido usa o pacote Communicating Threads for Java (CTJ) (HILDERINK,
2006), threads que se comunicam em Java, que implementa o modelo CSP (tex citação car
hoare) em Java, que inclui padrões de threads muito mais simples e confiáveis que o modelo
das threads de Java. O pacote CTJ fornece um pequeno conjunto de padrões de projeto que é
suficiente para programação concorrente em Java. Um importante avanço deste pacote é que
o programador pode usar um grande conjunto de regras para eliminar os hazards, deadlocks,
livelock, starvation etc. durante o projeto e implementação.
A teoria de processos seqüenciais de comunicação (Communicating Sequential Process -
CSP) oferece uma notação matemática pra descrever padrões de comunicação por expressões
algébricas que contém evidências formais para análise, verificando e eliminando as condições
indesejáveis na utilização de threads. Esse modelo foi provado bem-sucedido para criação de
softwares concorrentes para tempo real e sistemas embarcados.
1.3 Objetivo geral
Desenvolver um problema computacional clássico utilizando Java e a teoria de CSP, fazendo
comparações entre a mesma aplicação utilizando apenas Java, verificando a viabilidade da uti-
lização da teoria CSP aliada a Java.
1.4 Desenvolvimento do trabalho
• Pesquisa e buscas de referências na literatura para o estudo da teoria de CSP, de Charles
Antony Richard Hoare.
• Pesquisa e busca de referências na literatura por pacotes que implementam a teoria de
CSP em Java.
• Desenvolvimento de aplicações utilizando o modelo de CSP para Java, para comparações
13
com códigos que utilizam multithread em Java.
1.5 Motivação
Devido à grande disseminação da linguagem Java, e a sua vasta área de atuação, verificar
se a utilização do pacote CTJ, que implementa a teoria de CSP, elimina o grande problema
na utilização de múltiplas threads, que é a geração de hazardas, deadlocks, livelock, starvation
etc. Pretendendo difundir a teoria de CSP, sua funcionalidade na prática, e os custos para a sua
utilização na resolução de problemas computacionais.
14
2 Communicating Sequencial Process(CSP)
Communicating Sequential Processes (CSP) é uma teoria matemática para descrição de
computação concorrente e distribuída, que pode ser usada para desenvolver aplicações multi-
thread que são garantidamente livres dos problemas comuns de concorrência, e o mais impor-
tante, pode ser provado através de regras matemáticas (HOARE, 1983). O seu comportamento é
baseado em teoria matemática, a qual é descrita por um conjunto de regras algébricas.
Um programa CSP é um conjunto de processos que se interconectam através de canais, a
única forma de interação entre processos, utilizando métodos de escrita e leitura para a troca
de informações com o meio de comunicação. A comunicação ocorre de forma síncrona, com
o fluxo direcional da informação. Um processo que executa uma primitiva de comunicação
(escrita ou leitura) é bloqueado até que o processo com o qual está tentando se comunicar
executa a primitiva correspondente. Comandos de escrita e leitura são ditos correspondentes.
A teoria matemática fornece uma definição robusta do conceito de processo, e dos oper-
adores nos quais os processos são construídos. Essas definições são a base para as leis algébri-
cas, para a implementação e a prova das regras que garantem a exatidão das aplicações.
A teoria de CSP especifica inteiramente o comportamento da sincronização e escalona-
mento das threads em alto nível de abstração, que é baseado em processos, em composições e
primitivas de sincronização.
Existem dois pacotes principais que implementam o modelo CSP para a linguagem Java, o
Communicating Sequential Processes for Java (JCSP)(WELCH, 2006) desenvolvido pelo Profes-
15
sor Peter Welch e por Paul Austin na Universidade de Kent, da Inglaterra, e o Communicating
Threads for Java (CTJ)(HILDERINK, 2006) desenvolvido por Gerald Hilderinks na Universidade
de Twente, dos Países Baixos.
Ambos são baseados nas primitivas de CSP, mas possuem diferenças em seus projetos e
objetivos. JCSP foi criado como uma alternativa mais lógica a API de concorrência de Java,
combinando as capacidades de CSP com a aceitação da linguagem Java, utilizado na progra-
mação concorrente em geral. Já CTJ é um pacote criado para o desenvolvimento de aplicações
embarcadas e de tempo real. Ambos têm como objetivo tornar a programação concorrente mais
segura, garantindo um funcionamento adequado da aplicação, porém sem aumentar a sua di-
ficuldade. O pacote CTJ controla diretamente as threads, pois possui seu próprio kernel que
especifica o comportamento do sincronismo e escalonamento das threads, tornando-se indepen-
dente de plataforma e de comportamento previsível (característica de programação tempo real).
Já JCSP usa as construções de concorrência da linguagem, como os métodos wait, notify e a
cláusula synchronized.
Uma vantagem importante é que o programador pode aplicar um conjunto de regras para
eliminar corrida de hazards, deadlock, livelock, starvation, durante o projeto.
O pacote escolhido neste trabalho foi o CTJ, pois especifica o comportamento do escalon-
amento e do sincronismo, assumindo o controle das threads, não mais deixando para o sistema
operacional, e dando uma maior previsibilidade ao programa. Compreender o conceito não re-
quer muito conhecimento sobre a teoria de CSP. O pacote de CTJ constrói uma ponte entre a
teoria e a prática de CSP.
2.1 Diferenças entre threads de Java e processos CSP
Os termos thread e processo são muito próximos. Um processo encapsula seus dados e
métodos, da mesma forma que os objetos, e encapsulam também uma ou mais threads de con-
trole. Ao atribuir uma thread de controle a um objeto passivo será criado um objeto ativo,
tornando-o um processo.
16
Um processo CSP é um objeto ativo cujas instruções são executadas por uma thread de
controle que está encapsulada no processo. Canais são objetos passivos e essenciais entre pro-
cessos, pois são utilizados para o envio e recebimento de mensagens. Variáveis devem ser
mantidas dentro do espaço de memória do processo, e não precisam ser sincronizadas, pois
cada processo possui seu endereçamento. Apenas dados de leitura podem ser compartilhados
entre os processos.
Processos podem iniciar processos, mas não podem controlar diretamente o processo filho.
Além de seguro, a depuração dos processos é menos complexa que seguir a execução de threads
baseadas no modelo utilizado por Java.
O comportamento das threads de Java é pouco específico e fortemente dependente dos
padrões adotados pelo sistema operacional (SUN, 2006e). Então, o comportamento das threads
em diferentes máquinas virtuais Java (JVM) pode variar, enquanto o comportamento dos pro-
cessos de CTJ deverá ser semelhante em qualquer máquina virtual Java, JVM.
A principal diferença entre threads e processos é que os processos são tipicamente indepen-
dentes (espaço de endereçamento diferente), um processo não sabe da existência de qualquer
outro processo, estes interagindo apenas com os mecanismos de comunicação, os canais. Já as
threads tipicamente dividem o mesmo espaço de endereçamento e podem compartilhar objetos
em memória e recursos do sistema diretamente.
2.2 Primitivas de sincronização
Em Java, um objeto pode ter mais de uma thread. Threads que podem operar simultanea-
mente dados compartilhados devem ser sincronizadas para prevenir corrida de hazard, que pode
resultar em dados corrompidos ou estados inválidos (travamento do sistema). O usuário deve
controlar cada thread utilizando vários métodos, os quais devem ser usados de forma apropri-
ada. Esse conjunto de métodos (ver as classes java.lang.Thread (SUN, 2006c) e java.lang.Object
(SUN, 2006a) fornecem um conceito básico e flexível de multithreads. A clausula synchronized
(que nada mais é que a construção de um monitor) protege a região crítica (trecho de código
17
que tem acesso a dados compartilhados e pode ser utilizado por mais de uma thread, permitindo
que apenas uma thread tenha acesso a essa região por vez). Os métodos wait()/notify() fazem o
enfileiramento condicional das threads que necessitam utilizar as regiões críticas em comum. A
construção de um monitor de sincronização envolve manter sob observação um ou mais méto-
dos. Não é fácil determinar quais métodos ou trechos de código devem ser sincronizados. De-
terminados padrões de projeto podem resolver esse problema (HILDERINK et al., 1997), mas eles
podem tornar o programa mais complexo que o necessário. Além disso, inserir sincronização
entre dois métodos corretamente pode ser difícil e suscetível a erros.
Já em CSP, canais são objetos especiais que gerenciam a comunicação entre processos, de
uma forma pré-definida. Canais são objetos passivos situados entre os processos e que contro-
lam a sincronização, o escalonamento, e transferência de mensagens entre processos. Comu-
nicação por canais é considerada thread-safe (trecho de código que pode ser executado com
segurança em um ambiente multithread), mais confiável e rápido. Além disso, o programador
estará livre de implementar a sincronização e o escalonamento. Canais CSP são inicializados
sem buffer e são sincronizados de acordo com o princípio do rendezvous (o processo escritor
espera até que o processo leitor esteja pronto ou o processo leitor espera até que o escritor esteja
pronto). Os canais CTJ permitem zero ou mais buffers, de acordo com as suas necessidades.
A simplicidade de se utilizar canais ao invés de monitores é uma importante motivação para a
utilização do conceito de CSP.
18
3 Processos CTJ
Processos que executam paralelamente não ”vêem” um ao outro. Cada processo enxerga
apenas seus canais, e isso é tudo que eles precisam. Em Java, um processo pai cria um processo
filho e inicia a execução do mesmo com o método run(), não havendo mais nenhuma interação
direta entre os dois. A interface de processo CTJ (HILDERINK, 2006h) é especificada por uma
interface de processo passiva, especificando o método run(), e uma interface de processo ativa,
especificando o conjunto de canais entrada/saída que serão usados pelo processo.
A interface de processo pode ser derivada de modelos data-flow (a comunicação é feita
pela emissão das mensagens aos receptores), que são grafos rotulados e orientados, compostos
pelos processos (nodos) e pelos canais (arestas). Processos são conectados por arestas e elas
especificam a direção das mensagens. A figura 1 mostra um grafo de uma interface de um
processo ativo com um canal de entrada e outro de saída.
Figura 1: Interface de processo (HILDERINK et al., 1997).
19
3.1 Estados de transição
Para cada processador haverá apenas uma thread em execução em um determinado mo-
mento. Um sistema multiprocessador com n processadores poderá ter n threads executando
simultaneamente. Entretanto um sistema uniprocessador pode executar múltiplas threads uti-
lizando um escalonador. Os estados das threads e processos não precisam ser iguais, embora
eles possam rodar no mesmo sistema. A seguir serão mostradas as diferenças entre estados de
transição de threads e processos.
3.1.1 Estados de transição da thread.
Uma thread pode estar em um dos seguintes estados (SUN, 2006d):
• new : a thread foi instanciada, porém ainda não está em execução;
• runnable: thread já em execução, de posse do processador;
• blocked: a thread está bloqueada, esperando ser liberada pelo monitor (método syn-
cronyzed);
• waiting: a thread está esperando indefinidamente que outra thread execute uma ação, um
signal;
• timed waiting: a thread está esperando que outra thread execute uma ação até um deter-
minado tempo;
• terminated (tex): a thread terá terminado sua execução.
O diagrama de transição de estados mostrado na figura 2 na próxima página exemplifica o
modelo de transição das threads.
20
Figura 2: Diagrama de transição de estados das threads.
3.1.2 Estados de transição de um processo CTJ.
Um processo pode estar em um dos seguintes estados (HILDERINK et al., 1997):
• instantiated: o processo pode ter sido criado ou terminou com sucesso, nenhuma thread
está atribuída ao processo;
• running: a thread de controle foi alocada a um processo e então o processo foi ativado;
• preempted: o processo foi preemptado, ou seja, retirado do processador por um de maior
prioridade, o processo está pronto para execução, mas não está executando;
• waiting: a thread de controle está inativa ou bloqueada e está esperando para ser notificada
(voltar ao processador);
• garbage: o processo terminou e não será atribuído a mais nenhuma thread, o garbage
collector de Java excluirá o objeto.
O diagrama de transição de estados mostrado na figura 3 na página seguinte ilustra as transições
de estados de um processo:
21
Figura 3: Diagrama de transição de estados dos processos (HILDERINK et al., 1997).
O diagrama de transição de estados de processo distingue entre escalonadores preemptivos e
não preemptivos. Um processo que é preemptado por um processo de maior prioridade deve ser
temporariamente interrompido e ir para o estado preempted. Um processo preemptado passará
para o estado running caso não exista outro processo com prioridade maior esperando para
executar no estado preempted.
22
4 Canais CTJ
A interface de canais do pacote CTJ (HILDERINK, 2006b) é simples, contendo uma interface
para canais de entrada, que especifica o método read(), e uma interface para canais de saída
que especifica o método write(). Processos comunicam-se com outros processos utilizando
leitura ou escrita nos canais compartilhados invocando os métodos read() e write(). Canais CTJ
permitem também múltiplas escritas e leituras.
Para evitar a perda de dados, os canais de comunicação são sincronizados. Isso significa
que se o emissor envia mensagem antes do receptor estar pronto para receber, o emissor será
bloqueado. Da mesma forma, se o receptor tentar receber antes que o emissor tenha enviado
uma mensagem, o receptor será bloqueado. Quando ambos estão prontos, os dados podem ser
transmitidos. Os Canais do pacote CTJ enviam, por default, mensagem por valor, evitando o
compartilhamento de dados, embora também seja possível enviar mensagem por referencia. O
envio de mensagens por valor faz com que tanto canais de comunicação interna (utilizando o
mesmo disco físico) quanto canais externos (discos físicos diferentes) tenham o mesmo trata-
mento. Os canais do JCSP (P.D.AUSTIN, 2006) enviam mensagens por referência, menos para a
primitiva int, sendo necessário um tratamento especial para a transmissão de dados em canais
externos, pois não compartilham o mesmo espaço de endereçamento.
Comunicação via canais fornece um estrutura independente de hardware e uma estrutura
dependente de hardware. Ambas as estruturas são conectadas por uma interface de canal muito
simples, figura 4 na próxima página.
23
Figura 4: Interface de canal CTJ (HILDERINK et al., 1997).
4.1 Independente de hardware:
A comunicação via canais fornece uma plataforma independente de estrutura, onde os pro-
cessos podem ser alocados no mesmo sistema ou distribuídos em outros sistemas. Os processos
nunca acessam diretamente o hardware, eles podem apenas se comunicar com seu ambiente por
meio dos canais. Como resultado, os processos não sabem quais processos estão do outro lado
do canal e não sabem que hardware está entre os dois.
4.2 Dependente de hardware:
Canais podem estabelecer um link entre dois ou mais sistemas via algum hardware. Ob-
jetos especiais chamados linkdrivers podem ser inseridos no canal. Os linkdrivers controlam
o hardware e são as únicas partes da aplicação que possuem dependência de hardware. A es-
trutura do linkdriver é definida como abstrata, e pode ser estendida conforme a necessidade,
sem influenciar o projeto ou as estruturas independentes de hardware. A estrutura do linkdriver
também fornece tratamento de interrupções.
Todos os processos que não utilizam linkdriver são totalmente independentes de hardware.
Os processos que utilizam linkdrivers podem ser mais ou menos dependentes do hardware, pois
o linkdriver representa diretamente o hardware. A utilização de linkdriver facilita a portabil-
24
idade das aplicações, pois caso haja a necessidade da utilização de outro hardware, as mod-
ificações no projeto serão mínimas, apenas substituindo os atuais linkdrivers por uma versão
estendida para o novo hardware.
Os linkdrivers fazem a comunicação com a arquitetura de hardware, recursos do sistema
e fornecem um comportamento opcional, determinando a forma de comunicação, seja interna
(através da memória utilizando rendezvous ou buffers) ou externa (via periféricos como RS232,
PCI ou TCP/IP). Podem ser inseridos em um canal fornecendo os protocolos de comunicação
para a transferência de dados através do hardware. A combinação entre canais e linkdrivers
é poderosa, pois fornece uma estrutura para comunicação tanto interna como externa. Como
resultado os processos se tornam altamente independentes do meio físico.
Um canal pode facilmente estender um linkdriver, como mostra a algoritmo 1.
Algoritmo 1 Canal estendendo um linkdriver.
25
5 Utilizando CTJ
Essa seção descreve como criar processos e composição de processos em Java, utilizando o
pacote CTJ.
5.1 Criando processos em Java
Um processo é definido pela interface csp.lang.Process (HILDERINK, 2006h). Uma classe
de processo deve implementar à interface csp.lang.Process, que é muito semelhante a interface
java.lang.Runnable (SUN, 2006b). O método run() implementa o corpo runnable do processo,
que será invocado por outro processo e executará uma tarefa seqüencial.
Algoritmo 2 Exemplo de uma classe que implementa a interface de Processo.
O construtor do processo deve especificar os canais de entrada e saída e os parâmetros para
inicialização do processo. Não mais que um processo pode invocar o método run() ao mesmo
tempo. O método run() só poderá começar sua execução se os recursos necessários estiverem
disponíveis, para um funcionamento confiável. Na instanciação de um processo, seu construtor
deve inicializar todos os recursos, como os canais de entrada e saída e os parâmetros, antes que
26
o método run() seja chamado.
Algoritmo 3 Criando e executando um processo.
5.2 Composição de processos
Basicamente, processos são executados quando o método run()(tex) é invocado. O processo
que o chamou espera até o método run() retornar com sucesso.
A teoria de CSP descreve composições comuns nas quais os processos são executados, ou
seja, processos podem executar em seqüência ou em paralelo. Nessa seção serão apresentadas
as seguintes construções de composições: Seqüencial (5.2.1), Paralelo (5.2.2), Pararelo com
prioridade (5.2.3), Alternativo (5.2.4) e Alternativo com prioridade (5.2.5).
5.2.1 Construtor de Composição Seqüencial - Sequencial
O construtor de composição seqüencial executa apenas um processo por vez. O processo
de composição seqüencial terminará quando todos os processos internos forem finalizados. O
construtor de composições seqüencial é criado pela classe Sequential (HILDERINK, 2006g). O
objeto seqüencial é um processo.
Algoritmo 4 Construtor de composição seqüencial.
No algoritmo 4 o argumento processos é um Array de processos. O construtor inicia quando
invocado seu método run().
O algoritmo 5 na página seguinte mostra uma composição seqüencial de três processos.
27
Algoritmo 5 Exemplo de uma composição seqüencial.
O Processo2 será executado após o Processo1 ter finalizado sua execução com sucesso, e o
Processo3 após a execução bem sucedida do Processo2. O processo de composição sequencial
é bem sucedido quando todos os processos foram executados com sucesso.
Novos processos podem ser adicionados no fim lista, como mostra o algoritmo 6:
Algoritmo 6 Adição de um novo processo à composição seqüencial.
ou ainda ...
Algoritmo 7 Adição de vários novos processos a composição seqüencial.
E novos processos podem ser inseridos em uma determinada posição na lista como no
algoritmo 8:
Algoritmo 8 Inserção de processo em determinada posição na composição seqüencial .
Podem ser removidos da lista de processos 9:
Algoritmo 9 Remoção de processos da composição seqüencial .
Os métodos mencionados acima só podem ser executados pela instância que criou o pro-
cesso de composição, quando este não estiver em execução. Essas restrições asseguram a con-
fiabilidade e segurança para o construtor.
28
5.2.2 Construtor de Composição Paralelo - Parallel
O construtor de composição paralelo executa processos em paralelo. O construtor termina
quando todos os processos forem finalizados com sucesso. O construtor é criado pela classe
Parallel (HILDERINK, 2006d), sendo esse objeto um processo.
Algoritmo 10 Construtor de composição Paralelo.
No algoritmo 10 o argumento processos é um Array de processos. O construtor é inicial-
izado quando o método run() é invocado.
O exemplo 11 mostra uma composição em paralelo de três processos.
Algoritmo 11 Exemplo de uma composição Paralela.
Os processos Processo1, Processo2 e Processo3 serão executados em paralelo. Cada um
terá uma thread de controle interno com a mesma prioridade de execução. O processo paralelo
será finalizado com sucesso se todos seus processos internos forem bem sucedidos.
Novos processos podem ser inseridos a lista, algoritmo 12:
Algoritmo 12 Adição de um novo processo a composição Paralela.
ou ainda como no algoritmo 13:
Algoritmo 13 Adição de vários novos processos a composição Paralela.
Da mesma forma, processos podem ser removidos:
29
Algoritmo 14 Remoção de processos da composição seqüencial.
5.2.3 Construtor de Composição Paralelo baseado em Prioridade - Pri-Parallel
O construtor de composição paralela com prioridades (HILDERINK, 2006f) estende o con-
strutor de composição paralela, porém agora com prioridades. A cada processo do construtor
priparalelo será dada uma prioridade, enquanto que os processos do construtor de composição
paralela recebem a mesma prioridade. O primeiro processo da lista receberá a maior priori-
dade, e o último receberá a menor prioridade da lista de processos. O objeto priparalelo é um
processo.
Atualmente, o número máximo de prioridade por objeto priparalelo é 8, onde 7 são para os
processos e um é reservado para as tasks idle, skip e garbage collector (ainda não implemen-
tado). Processos priparalelos podem ser inicializados aninhados (ver 5.2.6 na página 35), assim,
podendo aumentar o número de processos com prioridades.
Os processos são executados por prioridade, tais prioridades são definidas pela ordem de
inserção na lista de processos, não sendo possível fazer a edição das mesmas para os processos
já adicionados.
A classe PriParallel cria um processo paralelo baseado em prioridade.
Algoritmo 15 Construtor de composição Paralelo com prioridade.
O argumento processos(tex) é uma Array(tex) de Process. O construtor é iniciado pela
chamada do método run()(tex).
O exemplo 16 mostra uma composição paralela de três processos com prioridade:
30
Algoritmo 16 Exemplo de uma composição Paralelo com prioridade.
Os processos Processo1, Processo2 e Processo3 serão executados em paralelo com priori-
dades sucessivas. O Processo1 (de índice 0) tem a maior prioridade. Todos os processos da lista
que possuem índice 6 ou maior, compartilham a menor prioridade, 6. O processo priParalelo
termina com sucesso quando todos os processos internos são executados com sucesso. Para au-
mentar o número máximo de prioridades é possível criar novos processos PriParellel aninhados
( 5.2.6 na página 35) ao processo já criado. O exemplo 17 mostra um construtor priparalelo
com 28 níveis de prioridade.
31
Algoritmo 17 Exemplo de uma construção aninhada da composição Paralela com prioridade,
aumentando os níveis de prioridade.
Novos processos podem ser adicionados em tempo de execução:
Algoritmo 18 Adição de um novo processo a composição Paralela com prioridade.
Ou ainda:
Algoritmo 19 Adição de vários novos processos a composição Paralela com prioridade.
Processos podem ser inseridos em determinada posição da lista de processos (recebendo a
prioridade de tal índice):
32
Algoritmo 20 Inserção de processo em determinada posição na composição Paralela com pri-
oridade.
Processos podem ser removidos:
Algoritmo 21 Remoção de processos da composição Paralela com prioridade.
A ordem das prioridades será atualizada com a inserção ou remoção de um processo.
5.2.4 Construtor de Composição Alternativo - Alternative
O construtor de composição alternativa é composto por guardas, sendo cada guarda um pro-
cesso. Assim que um guarda fica pronto, ele é executado pelo processo principal. O construtor
da composição alternativa é definida pela classe Alternative (HILDERINK, 2006a).
Algoritmo 22 Construtor de composição Alternativo.
O argumento guardas é um Array de objetos guardas (ver capítulo 5.3 na página 36). Um
objeto guarda é uma instância da classe Guard (HILDERINK, 2006c). O processo construtor é
iniciado pelo método run().
O exemplo 23 mostra uma composição alternativa para três processos.
Algoritmo 23 Exemplo de uma composição Alternativa.
O processo alternativo espera pelo menos um dos guardas estar pronto, mas termina quando
um dos processos for selecionado e finalizado com sucesso. O guarda que possui o processo de
33
índice X, será selecionado quando o canal espeficado em seu construtor estiver pronto, sendo
este canal o canal de entrada do processo associado ao guarda. Se mais que um guarda estiver
pronto para executar eles serão selecionados se forma randômica.
Novos guardas podem ser inseridos em tempo de execução:
Algoritmo 24 Inserção de um novo Guard na composição Alternativa.
ou ainda:
Algoritmo 25 Inserção de vários Guard na composição Alternativa.
E podem ser removidos também:
Algoritmo 26 Remoção de Guard da composição Alternativa.
5.2.5 Construtor de Composição Alternativo baseado em Prioridade - Pri-Alternative
A classe PriAlternative (HILDERINK, 2006e) cria um construtor de composição alternativo
baseado em prioridade. Ela estende a classe Alternative e substitui o mecanismo de escolha
randômica por um baseado em prioridade. O objeto priAlternativo é um processo. O construtor
prialternativo é semelhante do alternativo...
Algoritmo 27 Declaração de um objeto da classe PriAlternative.
O argumento guardas é um Array de objetos Guarda. Um objeto guarda é uma instância
da classe Guard (HILDERINK, 2006c). O construtor PriAlternativo é inicializado pelo método
run().
34
O algoritmo 28 mostra uma composição PriAlternative para três processos
Algoritmo 28 Exemplo de uma composição Alternativa com prioridade,
O processo priAlternativo espera até pelo menos um guarda estar pronto, mas termina com
sucesso quando um dos processos internos é selecionado e finalizado com sucesso. O guarda
que possui o processo de índice X, será selecionado quando o canal espeficado em seu construtor
estiver pronto, sendo este canal o canal de entrada do processo associado ao guarda, se mais de
um guarda estiver pronto, o guarda de maior prioridade (menor índice) será selecionado. O
processo pertencente ao guarda selecionado será executado.
Um novo guarda pode ser adicionado em tempo de execução, algoritmo 29.
Algoritmo 29 Adição de um novo guarda a composição PriAlternative.
Ou vários guardas podem ser inseridos na composição, algoritmo 30.
Algoritmo 30 Adição de vários guardas a composição PriAlternative.
Um guarda pode ser inserido por índice na composição PriAlternativa, conforme algo-
ritmo 31.
Algoritmo 31 Adição de vários guardas a composição PriAlternative.
35
Sendo a prioridade do guarda inserido igual ao seu índice, e as prioridades dos guardas com
índice maior serão incrementadas.
É possível a remoção de guardas, conforme mostrado no algoritmo 32.
Algoritmo 32 Adição de vários guardas a composição PriAlternative.
5.2.6 Construtor de Composição Aninhados
Os processos de composição Seqüencial ( 5.2.1 na página 26), Paralela ( 5.2.2 na página 28),
Paralela com prioridade ( 5.2.3 na página 29), Alternativa ((5.2.4)) e Alternativa com prioridade
((5.2.5)) aceitam processos de composição aninhados. Duas composições seqüenciais podem
executar em paralelo, como no algoritmo 33.
Algoritmo 33 Exemplo de composição aninhada, composição paralela com duas composições
seqüenciais aninhadas.
Ou uma composição alternativa que optará entre a execução da composição paralela ou
seqüencial, como no algoritmo (34).
36
Algoritmo 34 Exemplo de composição aninhada, composição alternativa com duas com-
posições aninhadas, uma paralela e outa seqüencial.
5.3 Guardas Condicionais e Incondicionais
O objeto guarda é uma instância da classe Guard (HILDERINK, 2006c), que controla um
processo, que estará pronto quando o construtor receber a primeira ocorrência de comunicação
no canal de entrada desse processo. O processo é controlado por entradas, ou seja, apenas os
canais de entrada podem ser monitorados pelos processos. O controle dos canais de saída não
foi implementado porque isso resultaria em uma penalidade na performance do canal.
Um objeto guarda pode ser declarado como no algotimo 35.
Algoritmo 35 Criando um objeto da classe Guard.
O guarda se torna true quando o argumento canal (interface de entrada) está pronto e tem
dados disponíveis para leitura. O guarda em si não é um processo, mas um objeto passivo
que controla os processos. O objeto alternativo (ver 5.2.3 na página 29) verifica se todos os
guardas estão disponíveis e espera pelo menos até que um canal fique pronto, então o processo
que pertence ao guarda ativado pode ser selecionado e executado. Um guarda habilitado que
sempre é executado no construtor alternativo é chamado de incondicional. Um guarda também
37
pode ser condicional, isto é, será habilitado (participará do construtor alternativo) se alguma
condição for verdadeira, ou será desabilitado (não participa do construtor) e o processo não é
executado.
Algoritmo 36 Execução condicional de um Guard.
Se a condição for verdadeira o guarda verificará o canal, porém, se for falsa, o guarda não
executará e o processo não será selecionado. Se o processo for selecionado, deverá ler os dados
do canal.
Um guarda pode ser declarado com uma variável condicional (algoritmo 37).
Algoritmo 37 Declaração de um Guarda condicional.
Ou sem a variável (algoritmo 38).
Algoritmo 38 Declaração de um Guarda incondicional.
A condição de execução do guarda pode ser modificada pelo método setEnabled().
38
6 Validação do programas CSP
O comportamento da linguagem CSP é baseado em teoria matemática, a qual é descrita por
um conjunto de leis algébricas. Sendo assim, o comportamento de uma aplicação CSP pode
ser validado utilizando-se regras matemáticas, garantindo a ausência de problemas comuns a
programação concorrente. Existem várias ferramentas que fazem a validação de aplicações CSP,
uma delas é o Deadlock Checker (MARTIN; JASSIM, 2007), que verifica a existência de deadlock
e livelock a partir da construção de um sistema de transições de toda a rede de processos,
verificando cada estado global em busca de deadlock (MARTIN; JASSIM, 1997).
Já os pacotes que implementam o modelo CSP em Java, apenas o JCSP dá suporte à val-
idação de código, através de um sistema de prova, que estende os cálculos da tecnologia Java
Card (SUN, 2007), que corresponde à linguagem de programação Java sem threads e é usada
para programação de smartcards. Uma parte importante do sistema de prova é o cálculo da
lógica do programa, que é feito através do JavaCard Dynamic Logic (JavaCardDL) que foi
desenvolvido no projeto KeY. A ferramenta KeY é um sistema para verificação de programas
Java Card, podendo também verificar programas Java sem threads (KLEBANOV et al., 2005).
A figura 5 na página seguinte mostra a arquitetura de verificação do sistema, a qual consiste
em quatro componentes. A verificação do código possui quatro passos:
1. O primeiro passo executa instruções JavaCard até encontrar uma chamada para alguma
biblioteca JCSP. Isso é executado pelos padrões de cálculo do programa KeY. Devido à
comunicação entre processos ser através de canais, de forma explicita, não existe interfer-
ência no código seqüencial de um processo. Do ponto de vista CSP, um código seqüencial
39
pode ser visto como um processo que produz apenas eventos internos.
2. A segunda parte, executando em paralelo com a primeira, substitui as bibliotecas JCSP
utilizadas no programa por seus modelos em CSP.
3. O passo 3 reescreve o programa, transformando os processo em uma forma normal que
permite uma dedução mais simples dos passos de um processo.
4. No quarto passo, as asserções são avaliadas segundo os possíveis comportamentos dos
processos.
Figura 5: Arquitetura do cálculo de verificação (KLEBANOV et al., 2005).
Com a forma normal dos processos montada ocorrem duas fases de validação deste código.
Na primeira parte a rede de processos (uma espécie de grafo que possui os processos como
nodos e os canais como arestas) é montada. O segundo passo envolve a execução desta rede
de processos, simulando a troca de mensagens entre os processos. A prova fornece uma boa
representação passo a passo da execução da rede, servindo para a depuração.
40
7 Comparação entre aplicaçõesutlizando CTJ e Java
Para verificar a complexidade (tando na geração de código quanto na execução) da utiliza-
ção do pacote CTJ em aplicações concorrentes, ao invés do modelo de thread utilizado por
Java, foi implementado um problema clássico de concorrência, o Jantar dos Filósofos (MAGEE,
2007).
O Problema do Jantar dos Filósofos apresenta cinco (5) filósofos e cinco (5) garfos. A
idéia central deste problema é que dado os filósofos e os garfos em um jantar, cada filósofo
necessita de dois (2) garfos para comer. Os filósofos podem estar em um destes dois (2) estados:
esperando ou comendo. Se um filósofo está no estado esperando e quer passar para o estado
comendo, ele tenta pegar dois (2) garfos. Se conseguir pegar os dois garfos ele passa para
o estado comendo. Enquanto no estado esperando, o filósofo permanece tentando pegar os
garfos, ou seja, fica esperando a liberação dos garfos.
Foram desenvolvidas duas implentações deste problema, uma utilizando as threads de Java
(ver apêndice A, B e C) e outra utilizando o pacote CTJ (ver apêndice D, E e F).
A rede de processos dessa aplicação está representada na figura 9.
41
Figura 6: Rede de processos do Jantar dos Filósofos.
Os códigos resultantes são semelhantes, embora a versão CTJ necessite de um pouco mais
de lógica para o tratamento das mensagens, tanto no envio quanto no recebimento.
A proteção das regiões criticas na implementação utilizando CTJ é mais simples, pois a
sincronização de CTJ é feita pelos canais de comunicação, não existindo a preocupação de
quais trechos de código será necessária a inserção da clausula synchronized, diferente de Java,
que uma das dificuldades é escolher quais métodos serão sincronizados.
A corrida de hazards é evita em CSP, pois a solicitação de recursos (sejam dados ou propria-
mente recursos do sistema, tais como memória, TCP-IP) é feita através dos canais, com o envio
de uma mensagem ao processo detentor do recurso. O canal assegura que apenas um processo
terá sua solicitação aceita, os demais ficam no aguardo. Já em Java isso deve ser controlado
42
pelos métodos wait e notify e pela cláusula synchronized, como já mencionado, é difícil definir
quais trechos de código serão acessados simultaneamente por mais de uma thread.
Os deadlocks são evitados, pois a comunicação é feita via canais, e não com o compartil-
hamento de trechos de código. Ex.:
Em Java, existem duas regiões críticas e duas threads, sendo que cada thread está de posse
de uma região crítica, ver figura 7.
Figura 7: Duas threads tomando posse de regiões críticas distintas.
Porém, dentro das regiões críticas, as threads tentam o acesso a região que está de posse da
outra thread, sendo assim ambas serão bloqueadas, gerando um deadlock, como na figura 8.
Figura 8: Deadlock gerado pela tentativa de das thread à regiões críticas bloqueadas.
Em CTJ isso não ocorre, pois as regiões críticas se encontram dentro de um processo,
que receberá, através dos canais, as solicitações dos demais processos, não ficando bloqueado
permanentemente, porém apenas quando espera que outro processo esteja pronto para efetuar a
comunicação. Ex.
Dois processos desejam tomar posse de dois recursos, sendo que cada recurso é controlado
por um processo, estes representando as regiões críticas do exemplo anterior. A figura 9 mostra
43
a rede de processos deste exemplo.
Figura 9: Rede de processos do exemplo de não ocorrência de deadlock em CTJ.
A figura 10 mostra o Processo1 enviando uma mensagem ao Processo3, que detém um
recurso 1, e o Processo2 enviando uma mensagem ao Processo4, que detém o recurso 2.
Figura 10: Processo1 acessando o recurso 1, e o Processo2 acessando o recurso 2.
Os processos que controlam os recursos, não serão bloqueados permanentemente, sendo
44
assim, podem continuar a se comunicar com os demais processos, mesmo que seja para informar
que o recurso desejado não está disponível, como mostra a figura 11.
Figura 11: Processo1 acessando o recurso 2, e o Processo2 acessando o recurso 1, sem a ocor-
rência de deadlock.
Porém deadlocks podem ocorrer em CTJ, caso um processo efetue um método de escrita ou
leitura, e o processo que deveria efetuar o método correspondente não o faz, sendo o primeiro
processo bloqueado para sempre.
A execução do jantar dos filósofos em Java no intervalo de um minuto, gerou uma média
de 2058400 acessos aos métodos que são utilizados para o acesso aos dados (são os métodos
pegaGarfo() e devolveGarfo() da classe MesaJava, ver apêndice D), já na versão utilizando CTJ,
com o mesmo intervalo de tempo, ocorreu em media 6250 leituras no canal de entrada da classe
MesaCTJ, ou seja, o número de vezes que a classe MesaCTJ interagiu com um Filósofo.
Essa grande diferença entre o número de interações se deve em parte, ao controle das
threads, que CTJ assume completamente, ao invés de deixá-lo a cargo do sistema operacional
como Java, afetando seu desempenho. A troca de mensagens também é uma das responsáveis
pela queda no desempenho, pois a cada escrita em um canal, o objeto a que se deseja transmitir
é copiado, e a sua copia é enviada ao canal.
45
8 Conclusão
O pacote Communicating Threads for Java (CTJ) é uma implementação do modelo CSP,
resultando em construtores baseados em processos, composições e canais, de uso muito mais
simples e mais confiável que o modelo Java. O pacote CTJ fornece um pequeno conjunto de
padrões de projeto que é suficiente para programação concorrente em Java. Uma importante
vantagem do pacote CTJ é que o programador pode aplicar um conjunto de regras para eliminar
os race-hazards, deadlock, livelock, starvation, etc.
A sincronização e o escalonamento dos processos foi muito simplificado com a comuni-
cação entre canais e construtores compostos, tornando mais fácil a depuração e o acompan-
hamento dos estados do processo.
CTJ possui seu próprio kernel, que faz o escalonamento de suas thread de modo previsível
e claro, porém afetando seu desempenho.
O programador não precisar se preocupar com a teoria matemática de CSP, pois é um con-
ceito maduro, que possui ferramentas para verificação de erros.
Ao desenvolver aplicações utilizando CSP, a decisão de qual plataforma (plataforma mul-
tithread, vários processos rodando em um processador, vários processos sendo executados em
diferentes processadores) será utilizada como base para a aplicação pode ser tomada sem muito
impacto ao código e ao projeto da aplicação.
Usar CSP como base para o seu programa assegura a separação entre processos, pois a
interação entre os mesmo é feita somente através de canais, e não de métodos. Isso também
assegura o encapsulamento dos dados e da lógica de cada processo, sem a interação direta de
46
outro processo sobre estes.
47
APÊNDICE A -- Classe MesaCTJ
Algoritmo 39 Parte 1 da classe Mesa, da aplicação Jantar dos filósofos implementada em CTJ.
48
Algoritmo 40 Parte 2 da classe Mesa, da aplicação Jantar dos filósofos implementada em CTJ.
49
Algoritmo 41 Parte 3 da classe Mesa, da aplicação Jantar dos filósofos implementada em CTJ.
50
APÊNDICE B -- Classe FilosofoCTJ
Algoritmo 42 Classe Filosofo, da aplicação Jantar dos filósofos implementada em CTJ.
51
APÊNDICE C -- Classe JantarDosFilosofosMain
Algoritmo 43 Classe JantarDosFilosofos, da aplicação Jantar dos filósofos implementada em
CTJ.
52
APÊNDICE D -- Classe MesaJava
Algoritmo 44 Classe Mesa, da aplicação Jantar dos filósofos implementada em Java.
53
APÊNDICE E -- Classe FilosofoJava
Algoritmo 45 Classe Filosofo, da aplicação Jantar dos filósofos implementada em Java.
54
APÊNDICE F -- Classe MainJava
Algoritmo 46 Classe Main, da aplicação Jantar dos filósofos implementada em Java.
55
Referências
HILDERINK, Gerald. Communicating Sequential Processes for JavaTM (JCSP). Universityof Twente: [s.n.], Setembro 2006. Disponível em: <http://www.ce.utwente.nl/javapp/>.
HILDERINK, Gerald; BROENINK, Jan; VERVOORT, Wiek; BAKKERS, Andre.Communicating Java Threads. In: BAKKERS, A. (Ed.). Parallel Programming and Java,Proceedings of WoTUG 20. University of Twente, Netherlands: IOS Press, Netherlands, 1997.v. 50, p. 48–76. Disponível em: <citeseer.ist.psu.edu/hilderink97communicating.html>.
HILDERINK, Gerald H. Class Alternative. Setembro 2006. Disponível em:<http://www.cs.bgu.ac.il/ elhadad/advpro/ctj-distribution/ctj-doc/csp/lang/Alternative.html>.
HILDERINK, Gerald H. Class Channel. Setembro 2006. Disponível em:<http://www.cs.bgu.ac.il/ elhadad/advpro/ctj-distribution/ctj-doc/csp/lang/Channel.html>.
HILDERINK, Gerald H. Class Guard. Setembro 2006. Disponível em:<http://www.cs.bgu.ac.il/ elhadad/advpro/ctj-distribution/ctj-doc/csp/lang/Guard.html>.
HILDERINK, Gerald H. Class Parallel. Setembro 2006. Disponível em:<http://www.cs.bgu.ac.il/ elhadad/advpro/ctj-distribution/ctj-doc/csp/lang/Parallel.html>.
HILDERINK, Gerald H. Class PriAlternative. Setembro 2006. Disponívelem: <http://www.cs.bgu.ac.il/ elhadad/advpro/ctj-distribution/ctj-doc/csp/lang/PriAlternative.html>.
HILDERINK, Gerald H. Class PriParallel. Setembro 2006. Disponível em:<http://www.cs.bgu.ac.il/ elhadad/advpro/ctj-distribution/ctj-doc/csp/lang/PriParallel.html>.
HILDERINK, Gerald H. Class Sequential. Setembro 2006. Disponível em:<http://www.cs.bgu.ac.il/ elhadad/advpro/ctj-distribution/ctj-doc/csp/lang/Sequential.html>.
HILDERINK, Gerald H. Interface Process. Setembro 2006. Disponível em:<http://www.cs.bgu.ac.il/ elhadad/advpro/ctj-distribution/ctj-doc/csp/lang/Process.html>.
HOARE, C. A. R. Communicating sequential processes. Commun. ACM, ACM Press, NewYork, NY, USA, v. 26, p. 100–106, 1983. ISSN 0001-0782.
KLEBANOV, Vladimir; RÜMMER, Philipp; SCHLAGER, Steffen; SCHMITT, Peter H.Verification of JCSP programs. In: BROENINK, J.F.; ROEBBERS, H.W.; SUNTER,J.P.E.; WELCH, P.H.; WOOD, D.C. (Ed.). Communicating Process Architectures2005. IOS Press, The Netherlands: IOS Press, 2005. (Concurrent Systems EngineeringSeries, v. 63), p. 203–218. ISBN 1-58603-561-4. ISSN 1383-7575. Disponível em:<http://www.cs.chalmers.se/ philipp/publications/jcsp2005.pdf>.
56
MAGEE, Jeff. Jantar dos Filósofos (Dining Philosophers). Fevereiro 2007. Disponível em:<http://www.doc.ic.ac.uk/ jnm/concurrency/classes/Diners/Diners.html>.
MARTIN, J. M. R.; JASSIM, S. A. A Tool for Proving Deadlock Freedom. In: BAKKERS,A. (Ed.). Parallel Programming and Java, Proceedings of WoTUG 20. University of Twente,Netherlands: IOS Press, Netherlands, 1997. v. 50, p. 1–16.
MARTIN, J. M. R.; JASSIM, S. A. The Deadlock Checker Tool. The University of Kent: [s.n.],Janeiro 2007. Disponível em: <http://wotug.kent.ac.uk/parallel/theory/formal/csp/Deadlock/>.
P.D.AUSTIN. Interface Channel. Setembro 2006. Disponível em:<http://www.cs.kent.ac.uk/projects/ofa/jcsp/jcsp1-0-rc7/jcsp-docs/jcsp/lang/Channel.html>.
SUN. Class Object. Setembro 2006. Disponível em:<http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Object.html>.
SUN. Class Runnable. Setembro 2006. Disponível em:<http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Runnable.html>.
SUN. Class Thread. Setembro 2006. Disponível em:<http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Thread.html>.
SUN. Enum Thread.State. Setembro 2006. Disponível em:<http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Thread.State.html>.
SUN. Threading. Dezembro 2006. Disponível em:<http://java.sun.com/docs/hotspot/threads/threads.html>.
SUN. Java Card Technology. Janeiro 2007. Disponível em:<http://java.sun.com/products/javacard/>.
WELCH, Peter. Communicating Sequential Processes for JavaTM (JCSP). UNI-VERSITY OF KENT At Canterbury: [s.n.], Setembro 2006. Disponível em:<http://www.cs.kent.ac.uk/projects/ofa/jcsp/>.
