Aula do Duó - 05/05/2008

um processo é o coordenador quando no log está registrado o global begin, os demais registram local begin

as ações são gravadas e depois bloqueadas.

se a mensagem não chegar, por timeout ele dá abort e cancela a transação.
Ele só faz o commit se todas as respostas forem ready.

Falhas possíveis

Do agente - se no log dele, ele naum registrou o ready, ele não comete a ação, então o coordenador aborta por timeout. Nesse caso o ag. aborta a transação através do seu log local.
Pode tmb ter havido uma falha de host após a gravação do ready (falta de energia por exemplo). Se o ready foi gravado o log e antes de ser enviado aO coordenador a falha ter ocorrido, o coord. aborta por timeout. Caso ele tenha enviado e logo após, falhado, há a possibilidade do coord. cometer a ação, dependendo das informações enviadas pelos outros agentes.

Do coordenador -
depois de gravar o prepare e antes do global commit: bloqueia a transação até mandar o prepare de novo e recomeçar daú a transação. o agente fica aguardando a volta do coord.
depois do global commit mas antes de completar a transação: também é bloqueante! (os aag, ficam bloqueados aguardando a volta do coord.)
depois de gravar o complete: nada vai ser feito (nem pode). transações completas não podem ter seus dados alterados em virtude de erros posteriores.

Mensagens perdidas:
ready ou abort do ag pro coord: o coord falha por timeout e a transaction eh abortada
prepare do coord pros ag's: o coord aborta por timeout.

Algoritmo de Protocolo de cometimento não-bloqueante de 3 fases:
qdo o coord não manda o commit cria-se uma fase a mais
há uma fase a mais onde ou ele manda um prepare to commit ou prepare to abort
não se tem commit/abort, se tem um preparo para eles.
após tds terem sinalizado q receberam o prepare to commit/abort, finalmente ele envia a msg correspondente. Caso alguém não responda, o coordenador já aborta a ação aí!
esse algoritmo tem uma falha do mal: diante de falha de coordenador, qdo se ocorre algum problema com o coord, os ag's elegem outro coord. Porém qdo ocorre uma falha na rede ond se isolam agentes a ficarem em partições de agentes diferentes, um dos grupos fica sem coordenador e elege mais um, causando um 2º coordenador na ação. pode ocorrer também que cada uma das partições aja de uma maneira sobre a transação

é +seguro aceitar o bloqueio (protocolo de 2 fases, com bloqueio parcial dos hosts) para não ocorrer este problema. a solução é tomar medidas para uma rápida recuperação do coordenador.

Definição de Serialização e "Isolação" (ou visibilidade): Página 37 do PDF

Escalonamento concorrente: as transações sãoexecutadas concorrentemente (intercaladas)
Escalonamento serial: cada transação é executada por vez, criando uma série de execuções por transação

um escalonamento serial por definição é correto.
para haver conflito entre operações concorrentes, pelo menos uma ação tem que ser escrita, sendo de transações distintas. (Read/Write ou Write/Write)

Lock - controla a concorrência p/ realizar a serializabilidade (resolvem conflitos)
IMPORTANTE: Página 49, 1º parágrafo

Aula do Duó - 20/03/2008

Caracteristicas importantes dsobre relogio logico, a arquitetura de rede totalmente

conectada é recomendada, podemos comparar os tokens, que possui 2 algoritmos (um token unico

e dupo token) esses algoritmos foram feitos para arquitetura de anel. O anel duplo é

indicado para deteção de perda. Caracteristica de rede para Token,Duplo token,Relogio

Logico:

#Ultrapassagem de mensagem: nenhum deles permitem essa porra!
#Corrupção de Mensagem: Nenhum deles aceita. Quando da deifeito e troca alguns hints ficando

com valores diferentes.
#Perda de Mensagem:Duplo token é. Token e Relogio não.
#Atraso de Mensagem Finito(não tem tempo definido): Duplo token e relogio.
#Atraso de Mensagem Limitado (tem tempo max. definido): Token (se ele for fazer deteção de erro) por que ele usa time-out

Utilização:

Os dois de token são especificos pra resolução de conflitos, mais pode ser usado também para
O relogio Logico é utilizado pra realizer a ordenação total,usando ele com outro algoritmo ele pode resolver também conflitos. Dado um recurso compartilhado a intenção é evitar, dead lock, starvation, justiça ao acesso de recurso.

Passo a Passo dos Algoritmos passados em sala de aula

Algortimo - Não sei o nome

PROCESSO DE BROADCAST:

cada processo possui um vetor de controle de mensagens e relógio com o mesmo tamanho da quantidade de processos existentes (3 processos = vetor de 3 posições para cada processo) um processo envia o dado, os relógios dos processos são atualizados, um processo envia a requisição (REQ) e o processo seguinte aceita a requisição (ACK - mostra que está ciente do pedido de requisição do processo) registra-se o tempo no ql a msg saiu do processo-origem e o estado de conciência do pedido de requisição (ACK)
Só reigstra um ACK qdo a msg atual do processo está vazia, o valor de relógio do processo é o maior valor entre o relógio do processo que enviou a mensagem e o relógio atual, incrementado de 1.

O envio do REL sobrescreve qlqr informação registrada e envia o relógio para todos os outros processos para que seja comparado e incrementado. Qdo se qr usar o recurso, se muda o estado para U (using), para requerer o recurso, o processo entra em estado A (Acquiring). De resto ele fica num estado N (normal)

NUNCA SOBRESCREVA UM REQ POR UM ACK.

Acessa o recurso qm tiver a menor procedência.

Algoritmo - Ricarter Agrawala

1º Passo - Incrementa relogio de quem vai mandar e muda estado pra Q
2º Passo - MSG {pra td mundo que vai mandar msg}
3º Passo - Registra no vetor C1 = Relogio / M1 = Mensagem recebida.
4º Passo - Todos registram a mensagem enviado no vetor de quem mandou.
5º Passo - Incrementa o relogio de todos de acordo com o maior indice.
6º Passo - Tds que receperam REQ Incrementa o relogio e manda o REP pra pro destino.
7º Passo - Muda o estado de quem mandou para U.

Precedencia: Quando no seu vetor tiver um REQ e o tempo for menor (se for igual o vai o que tem o menor ID), vc não respode um REP. Registra T em D{0,1,2,3 ou 4}

REQ não sobrecrever o REP - Ignora mensagem e incrementa relogio.

Olha sempre o tempo no relogio do vetor referente ao processo.

Liberar recurso: Muda o estado para N, e manda REP pra tds que tiverem com T. Apos isso muda o D para F(false)

"Aula" do Duó - 17/03/2008 - Sist. Distr.

uma mensagem é sempre uma tripla (p/ relógios lógicos)

- identificação do proc. q a mandou
- valor de relógio
- conteúdo da mensagem

segunda ocasião onde se muda o relógio
quando ele recebe uma mensagem
- ele capta o valor de relógio dele e o do processo q enviou a mensagem e incrementa 1 no maior valor e armazena em Ci (valor do seu relógio interno)

porque que o relógio faz isso?
para ordenar o envio da mensagem (como se fosse uma linha de tempo)

Request : Requisição que um processo envia aos outros para dizer que vai utilizar a área crítica do sistema

ack (acknowledge): (páginas 25 e 26 da apostila de Sistemas Distribuídos) como o próprio nome diz, é uma mensagem "conhecedora", isso é o q é utilizado para gerencia o cronograma do tráfego de mensagens entre os processos

Rel (release): mensagem enviada quando o processo qr deixar a área crítica.

Aula do Duó - 10/03/2008

Vejam bem, o algoritmo que a gente falar, a gente ta falando expecificamente cap. II, seria
teoricamente 17, bom é... então seria a simetria dessa parte do algoritmo pode estar
aclopado a alguma tarefa diferente, esse algor. que esta usando o token pode ser um não
distribuido. Essa parte pode ser resolvida por simetria textual. É... então eu vo ler
primeiro essa partezinha teorica.
Agora lê a porra da apostila pq ele só sabe fazer isso em aula, e ainda não conhece
pontuação!!!
Starvation - Tenta pegar o recurso, mais nunca consegue! Ocorre quando vc tem processos
lentos competindo com processos muito rapidos.
Anel Logico - Dados circulam de forma unidireccional; - Os sinais sofrem menos distorção e
atenuação no enlace entre as estações, pois há um repetidor em cada estação; - Há um atraso
de um ou mais bits em cada estação para processamento de dados; - Há uma queda na
confiabilidade para um grande número de estações; - A cada estação inserida, há um aumento
de retardo na rede; - É possível usar anéis múltiplos para aumentar a confiabilidade e o
desempenho.

http://gsd.ime.usp.br/~kon/MAC5755/aulas/Aula8.html
http://pt.wikipedia.org/wiki/Topologia_de_rede

Transmitindo Token - Se i = 0 então o valor vai ser valor + 1 mod k. Sempre que chegar no 0
troca o valor do token.
Time-Out tem que ter um tamanho adequado. O que acontece com o processo quando o time-out estourar?
É bem simples, na verdade não tem como afirmar o que vai acontecer. Ele mantem o valor do token. Pra restaurar um token o valor do anterior tem que ser diferente. Se for igual não acontece nada. Dupla regeneração é muito raro. Acontece quando time-out é curto e grande transição de dados.

Matéria do Duó - 03/03/2008

semáforo: um programa qdo vai ser executado recebe uma sinalização (flag) para ser executado, o q dá prioridade para a execução dele
Nos sist. distribuídos não existe memória comum. Os processos se comunicam através de mensagens, sujeitas a atrfaso (delay).(Sistemas paralelos usam memória comum)
Controle de erros: Paralelo: caso haja uma falha na comunicação, como usam memoria comum, caso haja erro nesse caso o problema é mto provavelmente de hardware
Distribuídos: caso haja uma falha (comunicação ou processo) a máquina que apresentou a falha pára, porém as outras continaum a funcionar (inclusive os processos que rodem nela. o processo continua a funcionar, somente perde a comunicação)
uma das soluções baratas é o timeout (evitar colocar timeout pqno, pois a mensagem pode atrasar em sua entrega, caso o timeout esteja pqno ocorre a falsa detecção, onde o erro não ocorreu pois a mensagem foi entregue +trd)
Algoritmo de CRC (caçar + sobre isso!)
Gerenciamento de recursos:Exemplo de recursos: tempo de proc., armazenamento, largura de faixa de comunic., etc...reduz os custos, diminui o tempo do sistema, evita deadlock, starvation
Deadlock: o processo A usa o recurso 1, dpois tenta acessar o recurso 2, porém ele tá ocupado. Em paralelo, o B adquiriu o recurso 2 e está aguardando o 1. (Burrice!) (deadlock por recurso)
Prevenção: sincronismo. trocar mensagens a cada evento no sistema. É uma solução cara!detecção. vc cuida realmente do problema só quando ele acontece (timeout é um exemplo)
Linguagens para Sistemas Distribuídos:Conic, Edges, etc... (Darwin é o ambiente ideal para sistemas distribuídos)Java é extremamente adeqüada para sistemas distribuídos fora do Darwin (Haskell tmb)
Distribuição:Replicação para manter a consistência. cada processo tem que ter uma lista dos demais processos para poder entrar em contato com os outros e replicar os dados.
Correção: preparar algoritmos que de tempos em tempos atualize a lista de processos para cada um deles
Particionamento: Os dados estão em locais distintos (nem precisa explicar partição né galera?)
Um controle descentralizado melhora a resistência a falhas e queda do sistema.
A linguagem distribuida deve suportar concorrência (trheads), comunicação (socket) e sincronização (synchronize).
Chamada de procedimento remoto (Remote Procedure Call - RPC)
"O Java é bom pra classificar os tipos de classe" - Duó