Resumo P2 - Quilula-2014.2

Prévia do material em texto

Índice 
● Capítulo 4 (Monitores) 
○ Definição 
■ synchronized, notify e notifyAll 
■ monitores em java 
○ Simulando “Contando Semáforo” 
■ “Normal” 
■ “Melhorado” 
○ Simulando Semáforos Binários 
○ Jantar de Filósofos com Monitor 
○ Leitores e Escritores com Monitor 
○ Tipos de sinal (Signaling disciplines) 
■ SU 
■ SC 
■ SE 
○ Usando semáforos para implementar Monitores 
○ Caixa de ferramentas de monitores para java (4.8) [TODO] 
○ Chamada de monitor aninhada (4.9) [TODO] 
○ Técnicas de teste para monitor (4.10) [TODO] 
● Capítulo 5 (Passagem de mensagens) 
○ Objetos “canal” 
○ Rendezvous 
○ Espera seletiva 
○ 5.4 ­ solução baseada em troca de mensagens para programação 
concorrente [TODO] 
○ 5.5 //parcial, até um tópico antes da testagem deterministica  [TODO] 
● Capítulo 6 (Passagem de mensagens em programas distribuídos) 
○ TCP Sockets [TODO] 
○ Java TCP Canais [TODO] 
○ 6.2 //não tudo [TODO] 
○ 6.3 //até 6.35 [TODO] 
○ 6.4 //alguns problemas {bufferLimitado} [TODO] 
 
 
 
 
 
 
 
Monitores 
É uma técnica para sincronizar duas ou mais tarefas que compartilham um recurso em                           
comum. Com um modelo de concorrência baseado em monitores, o compilador ou o                         
interpretador podem inserir mecanismos de exclusão mútua transparentemente em vez do                     
programador ter acesso às primitivas para tal, tendo que realizar o bloqueio e desbloqueio de                             
recursos manualmente. Ou seja, não é mais necessário implementar os métodos V() e P(). 
Propriedades: 
● O monitor encapsula as variáveis compartilhadas e suas operações, além de qualquer                       
sincronização requerida para acessar a variável; 
● possui construtores separados para exclusão mutua e sincronização; 
○ A exclusão mutua é fornecida automaticamente pela implementação do                 
monitor. 
● um monitor é um objeto de sincronização que é uma instância de uma classe especial                             
monitor: 
○ uma classe monitor define variàveis privadas e uma série de métodos publicos                       
e privados. 
● as variáveis de um monitor representam os dados compartilhados; 
● threads se comunicam chamando os métodos do monitor que acessam as variáveis                       
compartilhadas. 
● possui uma fila de entrada mais uma fila associada com cada variável de condição: 
○ por exemplo, considere uma classe “buffer” que extenda monitor. Suponha que                     
ela tenha duas condições: cheio e vazio. Esta classe possuirá duas filas de                         
saída; 
 
 
Exclusão mutua ­ uma ou mais threads estão liberadas para executar dentro de um                           
monitor, mas o programador não é responsável por garantir que haja a exclusão mútua. Esta                             
é garantida pelo pela implementação do monitor. 
Condição de sincronização 
● É guardada usando variáveis de condição e as operações wait() e signal(): 
○ uma variável de condição denota uma fila de threads que estão esperando por                         
uma condição específica se tornar verdadeira; 
● variavelCondicao.wait() ­ operação análoga à operação P(). É usado para bloquear                     
uma thread; 
○ método chamado quando uma thread está executando um método do monitor; 
○ ao ser executado, libera outra thread a entrar no monitor e bloqueia a thread                           
que está no final da fila para variavelCondicao: 
■ podemos considerar que as threads bloqueadas em uma               
variavelCondicao estão fora do monitor; 
■ se uma thread que está bloqueada em uma variavelCondicao nunca é                     
“acordada” por outra thread, ocorre um deadlock; 
 
 
● variavelCondicao.signal() ­ desbloqueia uma thread e é análoga à operação V(); 
○ se nenhuma thread está bloqueando a variavelCondicao, a operação signal                   
não terá nenhum efeito; 
○ se alguma thread estiver bloqueando, a operação desperta a thread do topo da                         
fila para variavelCondicao 
■ depois da thead executar o sinal (no caso, signal­and­continue) para                   
acordar a thead que está esperando, a thead continua sendo executada                     
no monitor e a thead acordada é movida para a entrada da fila. Ou seja,                             
a thead que acabou de ser “acordada” entra novamente no monitor                     
imediatamente. 
■ quando sinais do tipo SC são usadas, as theads sinalizadas possuem a                       
mesma prioridade que as theads que estão tentando entrar no monitor                     
via chamada de métodos públicos. 
● variavelCondicao.signalAll() ­ acorda todas as theads que estão bloqueadas na                   
variavel de condição.  
● variavelCondicao.empty() ­ retorna true se a fila para variavelCondicao está vazia e                       
false caso contrário. 
● variavelCondicao.length() ­ retorna o tamanho atual da fila para variavelCondicao. 
 
syncronized, notify e notifyAll 
● Synchronized 
○ adicionando esta palavra chave nos métodos, o Java automaticamente garante                   
a exclusão mútua; 
● Notify 
○ “acorda” uma única thread que está esperando; 
○ não garante que a thread que esteja esperando a mais tempo acorde; 
● NotifyAll 
○ “acorda” todas as threads que estão esperando; 
○ não garante que a thread que esteja esperando a mais tempo acorde; 
○ Use notifyAll no lugar de notify a menos que: 
■ todas as threads estejam esperando por uma condição que foi                   
sinalizada pela mesma notificação. Isso significa que se uma condição                   
está sinalizada por uma notificação, a outra condição também estará                   
sinalizada por esta notificação. Normalmente, quando isto acorre, todas                 
as threads estão esperando exatamente pela mesma condição; 
■ cada notificação esteja desejando habilitar exatamente uma thread para                 
continuar. 
● simulando multiplas variáveis de condição 
 
Exemplo de espera limitada: 
class boundedBuffer extends monitor { 
private int fullSlots = 0; 
// number of full slots in the buffer 
private int capacity = 0; 
// capacity of the buffer 
private int[] buffer = null; 
// circular buffer of ints 
private int in = 0, out = 0; 
private conditionVariable notFull = new conditionVariable(); 
private conditionVariable notEmpty = new conditionVariable(); 
public boundedBuffer(int bufferCapacity ) { 
capacity = bufferCapacity;buffer = new int[bufferCapacity]; 
} 
public void deposit(int value) { 
while (fullSlots == capacity) 
notFull.wait(); 
buffer[in] = value; 
in = (in + 1) % capacity; 
++fullSlots; 
notEmpty.signal(); //alternatively:if (fullSlots == 1) notEmpty.signal(); 
} 
public int withdraw() { 
int value; 
while (fullSlots == 0) 
notEmpty.wait(); 
value = buffer[out]; 
out = (out + 1) % capacity; 
--fullSlots; 
notFull.signal();//alternative:if(fullSlots==capacity–1)notFull.signal(); 
return value; 
} 
} 
... 
boundedBuffer bb; 
// executed by Producers 
bb.deposit(...); 
// executed by Consumers 
bb.withdraw(...); 
 
Simulando “Contando Semáforo” 
● “Normal” 
○ Nessa implementação, a thread que está esperando pode ficar eternamente                   
presa em um loop no método P(), caracterizando um starvation. 
○ class countingSemaphore1 extends monitor { 
 private int permits; // The value of permits is never negative. 
private conditionVariable permitAvailable = new 
conditionVariable(); 
 public countingSemaphore1(int initialPermits) { 
 permits = initialPermits; 
 } 
 public void P() { 
 while (permits == 0) 
 permitAvailable.wait();--permits; 
 } 
 public void V() { 
 ++permits; 
 permitAvailable.signal(); 
 } 
} 
// Threads call methods P() and V(): 
countingSemaphore1 s; 
s.P(); 
s.V(); 
● “Melhorado” 
○ Nessa implementação não há problema de starvation. Nesta solução, a thread                     
que chamar P() não pode ficar à frente de threads já sinalizadas e “roubar”                           
suas permissões. 
○ class countingSemaphore2 extends monitor { 
 private int permits; // The value of permits may be negative. 
 private conditionVariable permitAvailable = new conditionVariable(); 
 public countingSemaphore2(int initialPermits) { 
 permits = initialPermits; 
 } 
 public void P() { 
 --permits; 
 if (permits < 0) permitAvailable.wait(); 
 } 
 public void V() { 
 ++permits; 
 permitAvailable.signal(); 
 } 
} 
Simulando semáforos binários 
● Threads em P() ficam esperando a permissão da variável allowP, enquanto 
que threads em V() esperam a permissão da variável allowV. Essa espera 
pode causar um loop infinito nos metodos P() e V() 
● class binarySemaphore extends monitor { 
 private int permits; 
 private conditionVariable allowP = new conditionVariable(); 
 private conditionVariable allowV = new conditionVariable(); 
 public binarySemaphore(int initialPermits) { 
 permits = initialPermits; 
 } 
 public void P() { 
 while (permits == 0) 
 allowP.wait(); 
 permits = 0; 
 allowV.signal(); 
 } 
 public void V() { 
 while (permits == 1) 
 allowV.wait(); 
 permits = 1; 
 allowP.signal(); 
 } 
}   
 
Jantar de filósofos com monitor 
● Solução 1 
○ Um filósofo pega somente dois palitos apenas se os dois estão 
disponíveis. 
○ Um filósofo pode comer se seus dois vizinhos não estão comendo. 
○ Um fisólofo se bloqueia se na variávelCondicao se ele está com fome 
mas não pode comer. 
○ Depois de comer, o filósofo irá desbloquear um vizinho que está com 
fome, que estará habilitado para comer. 
○ Essa solução não possui problema de dead lock, mas ainda permite 
starvation. Entretanto, a possibilidade de entrar em starvation é tão 
pequena, que pode ser ignorada. 
○ class diningPhilosopher1 extends monitor { 
 final int n = ...; 
 // number of philosophers 
 final int thinking = 0; final int hungry = 1; final int eating = 
2; 
 int state[] = new int[n]; 
 // state[i] indicates the state of Philosopher i 
 // philosopher i blocks herself on self[i] when she is hungry 
but unable to eat 
 conditionVariable[] self = new conditionVariable[n]; 
 diningPhilosopher1() { 
 for (int i = 0; i < n; i++) state[i] = thinking; 
 for (int j = 0; j < n; j++) self[j] = new conditionVariable( 
); 
 } 
 public void pickUp(int i) { 
 state[i] = hungry; 
 test(i); 
 // change state to eating if Philosopher i is able to eat 
 if (state[i] != eating) 
 self[i].wait(); 
 } 
 public void putDown(int i) { 
 state[i] = thinking; 
 test((n+i-1) % n); 
 // check the left neighbor 
 test((i+1) % n); 
 // check the right neighbor 
 } 
 private void test(int k) { 
 // if Philosopher k is hungry and can eat, change her state 
and signal her queue. 
 if (( state[k] == hungry) && (state[(k+n-1) % n] != eating ) 
&& (state[(k+1) % n] != eating )) { 
 state[k] = eating; 
 self[k].signal(); // no effect if Philosopher k is not 
waiting on self[k] 
 } 
 } 
} 
 
Philosopher i executes: 
while (true) { 
 /* thinking */ 
 dp1.pickUp(i); 
 /* eating */ 
 dp1.putDown(i) 
} 
 
● Solução 2 
○ Para eliminar a possibilidade de starvation, cada filósofo possui um 
estado adicional. Um filósofo com fome não possui permissão para 
comer se possui algum vizinho nesse estado adicional, mesmo se os 
dois palitos estiverem disponíveis; 
○ Dois vizinhos não possuem permissão para estar em “starving” (o 
estado adicional) ao mesmo tempo. 
○ Um filósofo com fome entra em “starving” se ele não pode comer e 
seus dois vizinhos não estão em “starving” 
○ class diningPhilosopher2 extends monitor { 
 final int n = ...; 
 // number of philosophers 
 final int thinking = 0; final int hungry = 1; 
 final int starving = 2; final int eating = 3; 
 int state[] = new int[n]; 
 // state[i] indicates the state of Philosopher i 
 // philosopher i blocks herself on self[i] when she is hungry, 
but 
 //unable to eat 
 conditionVariable[] self = new conditionVariable[n]; 
 diningPhilosopher2() { 
 for (int i = 0; i < n; i++) state[i] = thinking; 
 for (int j = 0; j < n; j++) self[j] = new 
conditionVariable( ); 
 } 
 public void pickUp(int i) { 
 state[i] = hungry; 
 test(i); 
 if (state[i] != eating) self[i].wait(); 
 } 
 public void putDown(int i) { 
 state[i] = thinking; 
 test((n+i-1) % n); 
 test((i+1) % n); 
 } 
 private void test(int k) { 
                // Determine whether the state of Philosopher k should be 
 //changed to eating or starving. A hungry philosopher is 
               //not allowed to eat if she has a neighbor who’s starving 
              //or eating. 
 if (( state[k] == hungry || state[k] == starving ) 
 && (state[(k+n-1) % n] != eating && state[(k+n-1) % n] != 
starving ) 
 && (state[(k+1) % n] != eating && state[(k+1) % n] 
!=starving)) { 
 state[k] = eating; 
 self[k].signal(); // no effect if Phil. k is not 
waiting on self[k], 
 } 
 // which is the case if test() was called from pickUp(). 
 // a hungry philosopher enters the ‘‘starving’’ state if 
she cannot eat 
 //and her neighbors are not starving 
 else if ((state[k] == hungry) && (state[(k+n-1) % n] != 
starving ) 
 && (state[(k+1) % n] != starving )) { 
 state[k] = starving; 
 } 
 } 
} 
 
Leitores e escritores com monitor 
● Leitores possuem prioridade maior que escritores; 
● Leitores possuem os métodos comecarLer() e terminarLer(), enquanto que 
escritores possuem os métodos comecarEscrever() e terminarEscrever() 
● Escritores são forçados a esperar no método comecarEscrever() se algum 
escritor está escrevendo ou se algum leitor está lendo ou esperando; 
● No método terminarEscrever(), todos os leitores que estão esperando são 
sinalizados. De qualquer modo, um ou mais escritores podem iniciar o método 
de escrita antes que um leitor sinalizado entre novamente no monitor. A 
variável signaledReaderssão são usadas para previnir esta situação. 
● class r_gt_w_1 extends monitor { 
 int readerCount = 0; // number of active readers 
 boolean writing = false; // true if a writer is writing 
 conditionVariable readerQ = new conditionVariable(); 
 conditionVariable writerQ = new conditionVariable(); 
 int signaledReaders = 0; // number of readers signaled in endWrite 
 public void startRead() { 
 if (writing) { // readers must wait if a writer is writing 
 readerQ.wait(); 
 --signaledReaders; // another signaled reader 
                                                     // has started reading 
 } 
 ++readerCount; 
 } 
 public void endRead() { 
 --readerCount; 
 if (readerCount == 0 && signaledReaders==0) 
 // signal writer if no more readers are 
             //reading and the signaledReaders have read 
 writerQ.signal(); 
 } 
 public void startWrite() { 
 // the writer waits if another writer is writing, or a reader is 
 //reading or waiting, or the writer is bargingwhile (readerCount > 0 || writing || !readerQ.empty() || 
                            signaledReaders>0) writerQ.wait(); 
 writing = true; 
 } 
 public void endWrite() { 
 writing = false; 
 if (!readerQ.empty()) { // priority is given to waiting readers 
 signaledReaders = readerQ.length(); 
 readerQ.signalAll(); 
 } 
 else writerQ.signal(); 
 } 
} 
 
 
 
Tipos de sinal 
● Signal­and­continue (SC) 
○ A thread acordada vai para o final da fila de entrada e a thread que 
sinalizou continua executando no monitor. 
● Signal­and­urgent­wait (SU) 
○ comportamento do método signal(): 
■ Caso haja pelo menos uma thread esperando, a thread que 
executa o signal acorda uma thread que está esperando a 
variávelCondicao e se bloqueia na fila de “reentrada”; 
■ threads na fila de reentrada estão fora do monitor; 
■ a thread sinalizada “reentra“ no monitor imediatamente. 
○ comportameto do método wait(): 
■ Caso a fila de reentrada não esteja vazia, a thread acorda uma 
thread sinalizada desta fila e se bloqueia na fila para 
variavelCondicao; 
■ Caso a fila de reentrada esteja vazia, a thread libera a exclusão 
mútua (para liberar uma nova thread a entrar no monitor) e se 
bloqueia na fila para variavelCondicao. 
○ quando uma thread sai de um método do monitor: 
■ se a fila de reentrada não estiver vazia, ela acorda uma thread 
sinalizada da lista de reentrada; 
■ se a fila de entrada estiver vazia, ela libera a exclusão mútua; 
○ níveis de prioridade: 
■ A (maior prioridade) ­ thread acordada pela operação signal(); 
■ S ­ threads sinalizadas que estão na fila de reentrada; 
■ C (menor prioridade) ­ threads que chamaram um método do 
monitor, mas ainda estão esperando na fila de entrada; 
● Signal­and­exit (SE) ­ caso especial do SU 
○ comportamento do método signal(): 
■ ao invés de entrar na fila de reentrada, a thread sai do monitor 
imediatamente; 
■ estado signal é o último estado de um método ou é seguido 
imediatamente por um estado de retorno; 
■ assim como nos sinais SU, a thread acordada para operação 
signal é sempre a próxima thread a entrar no monitor 
 
Passagem de mensagens 
● Definição de métodos de envio e recebimento de mensagens: 
○ Blocking send ­ o “enviador” fica bloqueado até que a mensagem seja recebida 
(pelo método receive() ); 
○ Buffer­blocking send ­ mensagens são enfileiradas em um buffer limitado. O 
“enviador” só será bloqueado se o buffer estiver cheio; 
○ Nonblocking send ­ mensagens são enfileiradas em um buffer ilimitado; 
○ Blocking receiver ­ o “recebedor” fica bloqueado até uma mensagem estar 
disponível; 
○ Nonblocking receive ­ o “recebedor” nunca é bloqueado. O comando receive 
retorna uma indicação se há ou não uma mensagem recebida; 
● Passagem Assíncrona X Síncrona 
○ Assíncrona ­ ocorre quando uma operação blocking receiver é usada 
juntamente com a operação nonblocking send ou buffer­blocking send; 
○ Síncrona ­ é o termo usado quando as operações de envio e recebimento são 
do tipo “blocking”; 
■ podem ser simuladas usando o modo assíncrono: 
● se um comando blocking send não está disponível, o enviador 
pode enviar um buffer­blocking seguido imediatamente por um 
blocking receive. 
● Objetos Channel 
○ Objetos usados para trocar mensagens entre Threads no mesmo processo. 
○ Há três tipos (todos com versão síncrona e assíncrona): 
■ Mailbox: muitos “enviadores” e muitos “recebedores”; 
■ Port: muitos enviadores mas apenas um recebedor; 
■ Link: apenas um enviador e um recebedor; 
○ síncrono:  
■ as operações send() e receive() são implementadas usando uma 
variável chamada message e dois semáforos binários 
■ Apenas uma thread pode sempre executar a operação receive em um 
objeto port ou link. 
■ uma thread “enviadora” copia sua mensagem para a variável message 
e executa sent.V() para sinalizar que a mensagem está disponível; 
■ a thread “recebedora”executa sent.P() para esperar até que uma 
mensagem seja recebida; 
■ quando uma mensagem está diponível, o recebedor faz uma cópia de 
message e executa received.V() para sinalizar que a mensagem foi 
recebida; 
○ assíncrono: 
■ a implementação da operação send() do buffer­blocking é baseada na 
solução de buffer limitado. send() irá bloquear se o buffer de mensagem 
está cheio. 
■ as mensagens que um thread envia para um canal (especificamente 
um mailbox) particular possuem garantias de serem recebidas na 
ordem em que foram eviadas; 
■ em uma classe link, os métodos send() e receive() devem checar por 
múltiplos “enviadores” e “recebedores”. 
■ em uma classe port, o método receive precisa procurar por multiplos 
“recebedores”.  
○ ver http://dontpad.com/rhb/CompConc/SemafaroComCanal 
 
● Rendevouz 
○ Rendezvous provê sincronização e comunicação entre as 2 threads(cliente e 
servidor). O cliente fica bloqueado até a chamada ser aceita e uma resposta 
ser retornada. O servidor fica bloqueado até a chamada ser feita, que é 
preparada para aceitar 
● Espera seletiva 
○ Uma tarefa no servidor não pode ficar bloqueada enquanto espera alguma 
aceitação. Ela precisa estar livre para aceitar a chamada de duas ou mais 
entradas; 
○ Se o buffer não estiver cheio ou se não estiver vazio, uma entrada será aceita; 
■ se só houver uma, ela será imediatamente aceita. Se houver mais de 
uma entrada, uma delas será selecionada. 
■ Podemos adicionar um delay (timeout) para que seja determinado o 
tempo máximo que um servidor vai esperar por uma entrada 
“aceitável”. Neste caso, definimos um else que indicará as ações que 
serão tomadas se nenhuma entrada for “aceitável”. 
○ A seleção de qual entrada será executada ocorre da seguinte maneira: 
■ Quando a espera seletiva não contém delay e else: 
● choose() irá selecionar uma alternateiva aberta que está 
permitida para ser selecionada que tenha uma chamada de 
entrada esperando; 
● se várias alternativas permitidas estão abertas e possuem 
chamadas de entrada esperando, a alternativa que possui a 
chamada que chegou antes é selecionada; 
● se uma ou mais alternativas permitidas estão abertas, mas 
nenhuma possui uma chamada de entrada esperando, o método 
choose() bloqueia até que uma chamada de entrada chegue 
para uma das alternadas permitidas abertas. 
■ Quando a espera seletiva contém delay ou else: 
● uma alternativa else é executada se todas as alternativas 
permitidas estão fechadas ou todas as alternativas permitidas 
abertas não possuem uma chamada de entrada esperando; 
● uma alternativa delay é selecionada quando seu tempo de 
espera for alcançado. Isso ocorre se nenhuma alternativa 
permitida aberta pôde ser selecionada antes do tempo de 
expiração; 
○ Leitores e escritores: 277; 
○ Simulando a contagem de semáforos ­ 281; 
○ Alocação de recursos ­ 279 
○ http://dontpad.com/rhb/CompConc/Problema5.4 
 
 
Passagem de mensagens em programas distribuídos 
 
 
04/11 
● Pagina 312/313 
● algoritmo “PrintWriter” 
● http://dontpad.com/rhb/CompConc/Socket 
11/11 
● cap 6.3 
 
 
 
 
 
13/11 ­ EXERCÍCIOS 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
GABARITO LIVRO 
 
https://www.dropbox.com/sh/vk6wjjklzf0xow7/AADFyviO5xcsIXGhazKjd­c0a?dl=0 
 
de nada ;D 
 
 
 
 
 
 
Respostas das teóricas da prova de 2013.2 por Rodrigo Barreto 
 
1 ­ Quando usa semáforo, os semáforos acabam sendo variáveis globais que acabam 
se estendendo pelo código, gerando complicações na depuração de códigos grandes. 
Os monitores foram invetados para suprir isso, através do encapsulamento de dados. 
 
2 ­ SC: a thread acordada vai para o final da fila de entrada e a thread que sinalizou 
continua executando no monitor. 
     SU: a thread que sinaliza se bloqueia numa fila de reentrada(essa fila não existeno 
SC) , a thread acordada entra imediatamente no monitor. Threads na fila de reentrada 
tem prioridade sobre as threads da fila de entrada. 
 
3 ­ Usando synchronized nos métodos de uma classe automaticamente coloca uma 
exclusão mútua para as threads acessando os dados de uma instância dessa classe. 
Porém, se algum ou toros os métodos são não synchronized, pode ter um problema de 
corrida. Isso permite muitos tipos de bugs, os quais o monitores clássicos foram feitos 
para eliminar. 
 
 
5 ­ Síncrona: opreções send e receive estáo ambas em blocking 
     Assíncrona: o receive está em blocking porém o send está em buffer­blocking ou 
nonblocking. 
 
 
6 ­ Link: apenas um sender e um receiver podem acessar o objeto 
     Port: muitos senders mas apenas um receiver podem acessar o objeto 
 
 
 
7 ­ Rendezvous provê sincronização e comunicação entre as 2 threads(cliente e 
servido). O cliente fica bloqueado até a chamada ser aceita e uma resposta ser 
retornada. O servidor fica bloqueado até a chamada ser feita, que é preparada para 
aceitar 
 
 
 
Lembrando q isso são anotações q tenho do período passado, podem não estar 100%, 
mas já é algo, bjo fiquem com deus. 
 
(y)