PROTOCOLO DE CHECKPOINTING - TCC - CAUAN KASPER

UNIVERSIDADE FEDERAL DA GRANDE DOURADOS

CAUAN GARCIA LEO KASPER

PLUGIN FRAMEWORK PARA VISUALIZAO DO

COMPORTAMENTO DE PROTOCOLOS DE

CHECKPOINTING

DOURADOS-MS

2014




CHECKPOINTING

Trabalho de Concluso de Curso de graduao

apresentado para obteno do ttulo de Bacharel

em Sistemas de Informao.

Faculdade de Cincias Exatas e Tecnologia

Universidade Federal da Grande Dourados

Orientador: Prof. M.Sc. Rodrigo Porfrio da Silva Sacchi

Dados Internacionais de Catalogao na Publicao (CIP)

Biblioteca Central da UFGD, Dourados, MS, Brasil

K192p Kasper, Cauan Garcia Leo.

Plugin framework para visualizao do

comportamento de protocolos de checkpointing / Cauan

Garcia Leo Kasper Dourados-MS : UFGD, 2014. 46 f.

Orientador: Prof. Me. Rodrigo Porfrio da Silva

Sacchi.

Trabalho de concluso de curso (Graduando em

Sistemas de Informao) Universidade Federal da

Grande Dourados.

1. Plugin framework. 2. Protocolo de checkpointing.

I. Sacchi, Rodrigo Porfrio da Silva. II. Ttulo.

CDD: 004

Responsvel: Vagner Almeida dos Santos. Bibliotecrio - CRB.1/2620




CHECKPOINTING

Trabalho de Concluso de Curso aprovado como requisito parcial para

obteno do ttulo de Bacharel em Sistemas de Informao na Universidade

Federal da Grande Dourados, pela comisso formada por:

Orientador: Prof . Me. Rodrigo Porfrio da Silva Sacchi

FACET-UFGD

Prof . Dr. Wellington Lima dos Santos

FACET-UFGD

Profa. Ma. Carla Adriana Barvinski

FACET-UFGD

Dourados, 19 de Fevereiro de 2014.

Resumo

Este trabalho tem como objetivo o desenvolvimento de um Plugin Framework que permite visu-

alizar histricos de comunicao e de checkpoints vindos de aplicaes distribudas para analisar

protocolos de checkpointing. Para tanto, ele apresenta conceitos sobre o comportamento de pro-

tocolos de checkpointing e sobre o simulador ChkSim, ambos necessrios para a implementao

do plugin framework. A visualizao destes histricos facilitar o entendimento de protocolos

implementados no ChkSim atravs de diagramas espao-tempo. O plugin framework proposto

desenvolvido usando a linguagem de programao Java e um conjunto de suas API s grcas,

que inclui a manipulao de ferramentas grcas disponibilizadas. Alm disso, o plugin fra-

mework traz a oportunidade de exportar seus resultados grcos para arquivos no formato SVG

(Scalable Vector Graphics), de modo que essas imagens sejam analisadas em qualquer ambiente

computacional com suporte a este tipo de arquivo.

Palavras-chave: Protocolos de Checkpointing, ChkSim, Diagramas Espao-Tempo

Sumrio

1 Introduo 8

1.1 Objetivos Gerais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.2 Objetivos Especcos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.3 Metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.4 Cronograma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.5 Estrutura do Texto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2 Checkpointing 15

2.1 Modelo Computacional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.1.1 Eventos de comunicao . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.1.2 Eventos internos: Checkpoints . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.2 Checkpoints Globais Consistentes . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.2.1 Precdencia causal e Ordenao de Eventos . . . . . . . . . . . . . . . . . 17

2.2.2 Cortes Consistentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.2.3 Consistncia Entre Checkpoints . . . . . . . . . . . . . . . . . . . . . . . . 19

2.2.4 ZigZag Paths e Z-Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.3 Abordagens Para Checkpointing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.3.1 Sncrona . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

SUMRIO 7

2.3.2 Assncrona . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.3.3 Quase-sncrona . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3 ChkSim 26

3.1 Arquitetura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.2 Gerador de Cargas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3.3 Wrapper . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3.4 O Plugin Framework proposto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

4 Resultados 34

4.1 Resultados Obtidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

4.2 Comparao com a ferramenta Lupa . . . . . . . . . . . . . . . . . . . . . . . . . 41

4.2.1 Vantagens e Desvantagens em comparao ao Lupa . . . . . . . . . . . . . 42

5 Consideraes Finais 43

5.1 Concluses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

5.2 Diculdades Encontradas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

5.3 Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

Captulo 1

Introduo

A computao distribuda formada por um conjunto de n processos {P0...Pn1} que executameventos e se comunicam atravs da troca de mensagens. Neste modelo de sistema no existem

estruturas denidas para a execuo de tarefas usando o compartilhamento de memria, acesso

e sincronizao de relgios bem como informaes referentes diferena de velocidade entre

os processos, com isto a utilizao de comunicao atravs de mensagens se torna essencial

para o funcionamento da aplicao. Esta comunicao realizada basicamente utilizando canais

unidirecionais entre dois processos e todos os processos comunicam entre si diretamente ou atravs

de processos intermedirios. A computao distribuda representada atravs de diagramas de

espao-tempo, como representado na Figura 1.1. Esta Figura contm quatro processos (P0, P1,

P2 e P3), em que setas na horizontal representam o tempo decorrido da execuo da aplicao

distribuda em cada processo e as demais setas representam a troca de mensagens entre os

processos.

Figura 1.1: Diagrama espao-tempo entre os processos e as mensagens.

9Para garantir que as mensagens sejam enviadas e recebidas de acordo com a relao causal

denida por Lamport (4), necessria a criao de pontos de recuperao durante a execuo

da aplicao distribuda. Estes pontos de recuperao so denominados checkpoints e podem

ser apresentados gracamente como na Figura 1.2. Nesta Figura, checkpoints so representados

por pequenos quadrados preenchidos em um diagrama espao-tempo, na qual cada checkpoint cji

corresponde ao j-simo checkpoint do processo Pi.

Figura 1.2: Checkpoints em uma aplicao distribuda.

Em uma aplicao distribuda, podem ocorrer dois tipos de checkpoints, aqueles denomi-

nados checkpoints bsicos, normalmente instrumentados manualmente em uma aplicao, princi-

palmente por seu desenvolvedor, ou automaticamente inseridos na aplicao, por exemplo atravs

de tcnicas de compilao (13). Enquanto que checkpoints forados so retirados utilizando heu-

rsticas para garantir a consistncia da aplicao e entre checkpoints. A tcnica da retirada de

checkpoints chamada de checkpointing. A ilustrao de checkpoints forados em processos

apresentada na Figura 1.3.

Figura 1.3: Exemplo de checkpoints forados em uma aplicao.

Este trabalho visa o desenvolvimento de um plugin framework para permitir a visualizao

grca de diagramas espao-tempo contendo ilustraes de mensagens trocadas entre os proces-

sos e de checkpoints retirados nesses processos, com ou sem o uso de protocolos de checkpointing.

Nesse caso, o perl do usurio deve ser de algum j habituado com conceitos de protocolos de

checkpointing para que ele seja capaz de entender o comportamento de protocolos de checkpoin-

ting de interesse atravs dos padres de comunicao e de checkpointing gerados pelos protocolos

10

e apresentados como diagramas espao-tempo no plugin framework.

Uma ferramenta semelhante que props-se a desenvolver, o Projeto Lupa (10). Ele um

Framework de demonstrao grca de aplicaes em sistemas distribudos que proporciona ao

usurio a visualizao de um ambiente distribudo atravs de diagramas de espao-tempo com-

postos pelas sequncias de eventos de comunicao e de checkpoints. A Figura 1.4 um screenshot

retirado do Lupa referente a visualizao de diagramas para a comparao de checkpoints.

Figura 1.4: Dois diagramas visualizados para permitir comparao.

A principal desvantagem do Lupa a obrigatoriedade de que uma aplicao distribuda uti-

lize mtodos disponibilizados na camada de checkpointing implementados no Lupa, exigindo que

o programador insira grande quantidade de cdigo especco na aplicao j existente, tornando-

a dependente de uma linguagem de programao, da plataforma e das prprias caractersticas

do Lupa. Usando a execuo do ChkSim, uma ferramenta porttil para simular a execuo de

algoritmos checkpointing em aplicaes distribudas, (19) para cada protocolo, possvel evitar

essa insero de cdigo adicional, pois a criao do diagrama espao-tempo estar relacionada

somente execuo do ChkSim.

Alm disso, o Lupa possui um nmero reduzido de protocolos de checkpointing imple-

mentados em relao ao ChkSim. Por exemplo, os protocolos de checkpointing RDT-Minimal

(5), Lazy-HMNR (17), FINE (7) e alguns protocolos do tipo NBS (Sncronos no-bloqueantes)

(15, 16) j esto implementados no ChkSim, o que reduz uma quantidade de trabalho para de-

senvolver o plugin framework proposto, agregando implementaes mnimas relacionadas aos

protocolos de checkpointing (insero, se necessrio, de implementaes de outros protocolos no

ChkSim).

1.1. Objetivos Gerais 11

Com a nalidade de dar incio criao de um grupo de pesquisa na rea de Computa-

o Paralela e Distrubuda na Faculdade de Cincias Exatas e Tecnologias, o trabalho proposto

traz como primeira contribuio o desenvolvimento de um plugin framework para a visualizao

do comportamento de protocolos de checkpointing. Essa visualizao ser possvel atravs de

histricos obtidos de execues de aplicaes executadas em ambientes distribudos, indepen-

dentemente da plataforma e linguagem e programao, conjuntamente com simulaes usando o

ChkSim.

1.1 Objetivos Gerais

O objetivo deste trabalho o desenvolvimento de um plugin framework para auxiliar na visuali-

zao de padres de comunicao e de checkpoints, obtidos atravs de histricos da execuo de

aplicaes distribudas que usam tcnicas de troca de mensagens, independentemente da plata-

forma e linguagem de programao usada. O desenvolvimento deste plugin framework, alm da

visualizao do padro de comunicao e de checkpoints, facilita uma anlise mais detalhada do

comportamento dos protocolos de checkpointing em diferentes aplicaes.

1.2 Objetivos Especcos

Para alcanar o objetivo geral, os seguintes objetivos especcos so necessrios:

1. Selecionar tcnicas de programao para representar gracamente o padro de comunicao

e de checkpoints;

2. Estudar os conceitos de checkpointing e o conjunto de protocolos de checkpointing das

classes ZPF e ZCF j implementados no ChkSim;

3. Estudar e analisar a necessidade de implementar novos protocolos de checkpointing no

ChkSim, se necessrio;

4. Redigir o texto do Projeto de Trabalho de Concluso de Curso 1, incluindo toda a funda-

mentao terica necessria para o desenvolvimento do trabalho proposto;

5. Apresentar, para uma pr-banca, o Projeto de Trabalho de Concluso de Curso 1;

6. Desenvolver o Plugin Framework propriamente dito;

7. Validar o Plugin Framework proposto comparando-o com o Lupa;

1.3. Metodologia 12

8. Analisar um subconjunto de protocolos de checkpointing existentes, com base nas visuali-

zaes geradas pelo Plugin Framework proposto;

9. Redigir o texto do Projeto de Trabalho de Concluso de Curso 2, incluindo anlise e

resultados obtidos;

10. Apresentar, para uma banca nal, o o Projeto de Trabalho de Concluso de Curso 2;

11. Entregar a verso nal do Trabalho de Concluso de Curso 2 para a coordenao do Curso.

1.3 Metodologia

No desenvolvimento deste projeto, um ou mais computadores do laboratrio deveria conter sis-

tema operacional Linux, com navegador adequado, IDE NetBeans ltima verso, editores de texto

e interpretador para a linguagem de programao Java, necessrios para o ambiente de progra-

mao, alm do acesso recursos disponibilizados online, via Internet. Para garantir a sintonia

entre as tarefas houve reunies peridicas com o orientador.

Utilizou-se um laboratrio de informtica da Faculdade de Cincias Exatas e Tecnologias

para implementar o Plugin Framework proposto. Ele foi desenvolvido usando a linguagem Java,

com pacotes que suportem ambiente grco para representar o padro de comunicao e de

checkpoint. Este plugin framework tambm suportou a gerao de arquivos SVG (Scalable Vecto-

rial Graphics) atravs dos diagramas espao-tempo criados. Alm disso, ele usou o ChkSim para

obter os histricos desses padres. O ChkSim um simulador de protocolos de checkpointing

(19), no qual recebe como entrada um histrico de comunicao e de checkpoints, podendo este

histrico vir de uma determinada aplicao distribuda executada com o chkmpi ou atravs do

gerador de carga de trabalho do prprio ChkSim.

Utilizou-se os resultados dos histricos gerados pelo ChkSim para executar o plugin fra-

mework proposto e criar os grcos dos padres de comunicao e de checkpoints com ele. Com

isso, foi possvel realizar uma validao parcial. Para complementar esta validao, comparou-se

o comportamento deste plugin framework com o do do ambiente Lupa, identicando as funcio-

nalidades de cada um deles e as principais diferenas, incluindo vantagens e desvantagens.

1.4 Cronograma

As etapas para a concluso do trabalho proposto, referentes ao Trabalho de Concluso de Curso,

esto relacionadas numericamente com os objetivos especcos do trabalho e seu cronograma de

1.4. Cronograma 13

execuo apresentado na Tabela 1.1.

Tabela 1.1: Cronograma de Execuo.

Atividade

2013 2014

Maio Junho JulhoAgosto SetembroOutubroNovembroDezembro FevereiroMaro

1 2 3 4 5 6 7 8 9 10 11

1.5. Estrutura do Texto 14

1.5 Estrutura do Texto

Este trabalho de concluso de curso formado por conceitos na rea de computao distribuda

no que diz respeito a manipulao de protocolos para obter checkpoints globais consistentes em

aplicaes distribudas. A descrio das abordagens de checkpointing e seus protocolos so apre-

sentadas em baixo nvel para uma melhor compreenso do assunto, principalmente porque esses

conceitos sero utilizados na implementao do plugin framework proposto. No Captulo 1 apre-

sentada uma sucinta introduo sobre a computao distribuda e checkpoiting e apresentados

os objetivos do trabalho e a metodologia para a implementao do plugin framework.

O Captulo 2 descreve, em detalhes, os conceitos e denies bsicas sobre checkpointing,

com exemplos atravs de diagramas espaco-tempo. Ao nal deste Captulo as abordagens para

checkpointing e seus protocolos so apresentados resumidamente devido ao elevado nmero de

protocolos existentes, sendo dispendioso explic-los detalhadamente, isto porque o plugin fra-

mework proposto no alterar aqueles j implementados no ChkSim.

O Captulo 3 apresenta o simulador de protocolos de checkpointing denominado ChkSim,

que ser usado para obter informaes para permitir a visualizao de histricos no plugin fra-

mework. A sua arquitetura descrita brevemente e apresentado o seu gerador de cargas,

responsvel por capturar informaes externas que sero inseridas no ChkSim. Finalmente, este

Captulo tambm apresenta umWrapper do ChkSim, responsvel por gerar resultados comparati-

vos entre protocolos. Finalmente neste Captulo apresentado o plugin framework desenvolvido,

o seu funcionamento e interface grca, alm de listar os requisitos funcionais e o casos de usos

elaborados para o desenvolvimento da ferramenta.

O Captulo 4 apresenta os resultados obtidos atravs da execuo da ferramenta desen-

volvida, comparando os protocolos de checkpointing atravs das representaes grcas geradas

pelo plugin framework. Este captulo tambm apresenta as comparaes da ferramenta pro-

posta e com a ferramenta Lupa, descreve as suas funcionalidades e interfaces grcas das duas

ferramentas e determina as vantagens e desvantagens do plugin framework em relao ao Lupa.

O Captulo 5 apresenta as concluses deste Trabalho de Concluso de Curso citando os

resultados obtidos atravs da ferramenta desenvolvida e a utilidade desta ferramenta para a

rea da Tecnologia da Informao. Neste captulo so apresentadas as diculdades encontradas

para a redao do texto e implementao da ferramenta. Alm disto, este captulo apresenta

a idealizao para os trabalhos futuros, como a atualizao para um nova verso com mais

funcionalidades.

Captulo 2

Checkpointing

Este Captulo traz uma condensao sobre conceitos fundamentais de checkpointing e apresenta

uma sucinta reviso sobre suas abordagens. Na Seo 2.1 apresenta-se o modelo computacional

considerado, bem como denies de eventos, checkpoints e intervalos entre checkpoints. Na Se-

o 2.2 descreve-se noes necessrias para introduzirmos o conceito de consistncia global entre

checkpoints, tais como precedncia causal, cortes, consistncia entre um conjunto de checkpoints

e zigzag paths e z-cycles. Na Seo 2.3 apresenta-se uma classicao clssica para esses algo-

ritmos de checkpointing, considerando a sincronia ou no, dentro de trs categorias: sncronos,

assncronos e quase-sncronos.

2.1 Modelo Computacional

Uma aplicao distribuda composta por um conjunto de n processos que se comunicam entre

si, somente atravs da troca de mensagens, com o objetivo de realizar uma determinada ao.

Um processo constitudo de uma sequncia de eventos no qual eji representa o j-simo evento

executado no processo Pi. Os eventos so divididos em dois formatos, os eventos de comunicao,

responsveis pelo envio e recebimento de mensagem entre os processos e os eventos internos que,

para nossos propsitos, consideraremos apenas checkpoints.

2.1.1 Eventos de comunicao

Os eventos de comunicao so encarregados de realizar a comunicao entre os processos atravs

da troca de mensagem. Uma mensagem denotada comomx, em que x o nmero da mensagem

de envio ou recebimento. Na Figura 2.1 apresentado um diagrama espao-tempo contendo dois

2.1. Modelo Computacional 16

processos (P0 e P1), seus respectivos eventos (e00, e

10, e

20 e e

01, e

11, e

21) e a mensagem m1 enviada

pelo evento e10 e recebida pelo evento e11.

Figura 2.1: Representao dos eventos de comunicao e troca de mensagem.

2.1.2 Eventos internos: Checkpoints

Os eventos internos so formados apenas por checkpoints locais contendo atributos referentes ao

estado do processo. O checkpoint cki denota o k-simo checkpoint do processo Pi. Os processos

realizam a retirada de um checkpoint primrio aps o inicio da execuo e outro checkpoint

antes do encerramento da aplicao. A Denio 1 apresenta a condio de existncia de um

determinado checkpoint.

Denio 1. Um checkpoint cki corresponde ao evento eki tal que, k k.

Na Figura 2.2 os estados salvos dos processos P0 e P1 so representados respectivamente

atravs dos checkpoints (c00, c10, c

20 e c

01, c

11, c

21).

Figura 2.2: Apresentao de checkpoints em uma aplicao distribuida.

Um intervalo entre checkpoints Iki constitudo de um conjunto de eventos entre dois

checkpoints do processo Pi, este intervalo pode ser rotulado de duas maneiras, rotulado esquerda

em que Iki representa o intervalo entre os checkpoints cki e c

k+1i e rotulado direita, no qual o

intervalo Iki corresponde aos checkpoints ck1i e c

ki . Na Figura 2.3 apresentado o intervalo I

10

com rotulao esquerda entre os checkpoints c10 e c20 e o intervalo I

11 com rotulao direita

entre os checkpoints c11 e c01.

2.2. Checkpoints Globais Consistentes 17

Figura 2.3: Intervalo entre checkpoints e suas rotulaes.

2.2 Checkpoints Globais Consistentes

Um checkpoint global composto selecionando um checkpoint de cada processo da aplicao.

Para determinar se um checkpoint global consistente, necessrio analisar a precedncia causal

entre esses checkpoints selecionados e vericar se eles so concorrentes. Nesta Seo conceitua-se

a relao de precedncia causal, deni-se checkpoints global e quando um conjunto de check-

points pode formar uma linha de recuperao na computao distribuda, introduzindo cortes e

a consistncia entre checkpoints.

2.2.1 Precdencia causal e Ordenao de Eventos

A ordenao parcial dos eventos de uma aplicao distribuda necessria para garantir a consis-

tncia da aplicao, que est interligada ao conceito de precedncia causal proposto por Lamport

(4). A caracterizao de um determinado checkpoint global consistente est fortemente conec-

tada a contextualizao de precedncia causal. A Denio 2 expressa a condio de causalidade

entre eventos. Os eventos e e e so concorrentes (e e), se no existir precedncia entre eles(e9 e e e 9 e).

Denio 2. Um evento ea precede um evento eb (e

a eb ) se

i.) a = b e = + 1, ou

ii.) existe uma mensagem m que foi enviada em ea e recebida em eb , ou

iii.) existe um evento ec tal que ea ec ec eb

Neste trabalho usa-se o conceito e a detonao de precedncia causal para representar

causalidade entre checkpoints. Desta forma a precedncia entre os checkpoints (ca cb ) existesomente se o evento ea preceder o evento e

b . Estes eventos reproduzem estados do processo que,

quando armazenados, so denominados de checkpoints ca e cb , ou seja:


ea eb ca cb

Na Figura 2.4 possvel legitimar a Denio 2 em que a condio i representada pela

precedncia entre os checkpoints c00 c10, a condio ii valida a precedncia entre os eventosde comunicao e10 e21 devido ao envio da mensagem m1 entre eles, esta causalidade tambmcomprova a condio iii onde o evento e21 precede o evento e

31, resultando na relao e

10 e21e21

e31 que consequentemente dene a existncia da precedencia e10 e31.

Figura 2.4: Precedncia causal.

2.2.2 Cortes Consistentes

Um corte formado por um subconjunto de eventos locais executados por cada um dos processos

da aplicao. Um corte representado por um conjunto de n nmeros naturais {x0, x1, . . . , xn1}.Os ltimos eventos de cada processo pertencentes a um corte so denominados de fronteira de

corte descritos na seguinte forma {ex00 , ex11 , . . . , exn1n1 } ou seja, todos os eventos esquerda dafronteira de corte constituem o conjunto de um corte. A consistncia de um corte C determinada

aplicando a Denio 3 de causalidade entre quaisquer dois eventos pertencentes ao corte.

Denio 3. Um corte C consistente, para quaisquer dois eventos e e e se, e somente se,

(e C) (e e) e C

Na Figura 2.5 existem dois cortes C e I, em que o corte C, representado por um linha

preenchida, consistente, pois h relaes de precedncia e00 e01, e01 e11 e e11 e02 e asmensagens m1 e m2 so enviadas e recebidas dentro do limite do corte. Contudo, o corte I,

representado pela linha tracejada, inconsistente, porque o evento e10 no precede o evento e12,

alm disso a mensagem m3 est sendo enviada fora do limite do corte corte e recebida dentro do

corte I.


Figura 2.5: Cortes em uma aplicao distribuida.

2.2.3 Consistncia Entre Checkpoints

A consistncia entre checkpoints est relacionada com a precedncia causal de Lamport. Para

determinar essa consistncia, necessria a identicao de um checkpoint global, ou seja, a sele-

o de um checkpoint de cada processo da computao, que obedea a denio de um checkpoint

global consistente. Um checkpoint global () formado por um conjunto de l checkpoints locais,

sendo um checkpoint de cada n processo da aplicao.

Denio 4. Um checkpoint global = {cl00 , . . . , cl1n1} consistente se, e somente se,

i, j : 0 i, j < n : clii 9 cljj

Atravs da denio 4 possvel dizer que um checkpoint global consistente formado

por checkpoints concorrentes entre si (c c) e representa a fronteira de um corte consistente.Na Figura 2.6 demonstrado um corte consistente C, onde a fronteira deste corte formada

pelos checkpoints concorrentes (c10 c11 c12), estes checkpoints correspondem ao um conjuntode checkpoint global consistente = {c10, c11, c12}. O corte I inconsistente devido a relao deprecedncia entre os eventos de comunicao e e e, esta relao implica que o checkpoint c10precede o checkpoint c22 (c

10 c22), resultando na no concorrncia entre estes checkpoints.

Figura 2.6: Corte consistente envolvendo checkpoints.


2.2.4 ZigZag Paths e Z-Cycles

O conceito de zigzag paths (z-path) denido por Netzer e Xu (11) est relacionado anlise

das sequncias de mensagens entre um conjunto de checkpoints, esta analise est baseada na

Denio 5.

Denio 5. Uma sequncia de mensagens m1,m2, . . . ,mk uma z-path[m1,m2, . . . ,mk] que

liga um checkpoint ca a um checkpoint cb se, e somente se:

i.) a mensagem m1 enviada por Pa aps ca e

ii.) a mensagem mx, (x < k), recebida pelo mesmo processo que envia mx+1, mas mx+1 no

pode ser enviada em um intervalo anterior ao que mx foi recebida, e

iii.) mk recebida por Pb antes de cb

Netzer e Xu (11) determinaram que um conjunto de checkpoints forma algum checkpoint

global consistente se, e somente se, no existir uma z-path entre quaisquer dois checkpoints deste

conjunto.

Existem dois tipos de z-path: causais e no causais. Uma z-path causal caso a recepo de

qualquer mensagem mx, seja realizada antes do envio da mensagem mx+1. Na Figura 2.7 contm

uma z -path[m1,m2] causal que interliga os checkpoints c00 e c

12, pois a recepo da mensagem

m1 ocorre antes do envio da mensagem m2.

Figura 2.7: Z-path Path Causal.

Uma z-path no causal caso a recepo de qualquer mensagem mx seja realizada aps o

envio de mx+1. Na Figura 2.8 contm uma z-path[m1,m2] no causal que conecta os checkpoints

c00 e c12, porqu a mensagem m2 enviada antes da recepo da mensagem m1.

2.3. Abordagens Para Checkpointing 21

Figura 2.8: Z-path No Causal.

Uma z-path no causal entre dois checkpoints (ca e cb ) est duplicada causalmente se,

e somente se, existir uma z-path causal neste mesmo intervalo de checkpoints. Esta condio

implica na precdencia causal (ca cb ).

Uma z-path pode interligar um checkpoint a ele prprio, este checkpoint considerado um

checkpoint intil e no pertence a um checkpoint global consistente, quando isto ocorre, temos

uma zigzag cycle ou (z-cycle). Na Figura 2.9 ilustrado uma z-cycle[m1,m2,m3] que conecta

o checkpoint c12 a si mesmo, este checkpoint considerado intil devido existencia de uma z-

path[m1,m2] que interliga os checkpoints c00 e c

12 e uma z-path[m3] que conecta os checkpoints c

12

e c10, estas z-paths estabelecem que o checkpoint c12 no pertenca um checkpoint global consistente

formado pelos os checkpoints c00 e c10 resultando em um checkpoint c

12 intil para a aplicacao.

Figura 2.9: Z-Cycle.

2.3 Abordagens Para Checkpointing

Existem trs abordagens para efetuar checkpointings (18): sncrona, assncrona e a quase-

sncrona, com o objetivo principal de criar checkpoints globais consistentes em uma aplicao.

2.3.1 Sncrona

Esta abordagem suspende a execuo da aplicao para que cada um dos processos da computa-

o retirem um checkpoint global. Esta suspenso realizada interrompendo o uxo de mensagens


entre os processos e enviando mensagens de requisio para que os processos da computao sele-

cionem seus checkpoints. A aplicao voltar a ser executada aps o recebimento das mensagens

de conrmao da retirada dos checkpoints de outros processos.

Os checkpoints locais retirados, formam um checkpoint global consistente. Neste mtodo

os checkpoints globais consistentes so determinados instantaneamente, porm o custo da in-

terrupo da execuo da aplicao uma desvantagem, isto porque esta interrupo pode ser

ocasionada por apenas um processo da aplicao, caso este processo tenha um checkpoint rele-

vante.

Na Figura 2.10 a abordagem sncrona est sendo representada os mtodos para a seleo

de checkpoints e a formao do checkpoint global consistente = {c10, c11, c12}. Estes mtodosso realizados aps a retirada do checkpoint c11, no qual mensagens de requisio para a retirada

de checkpoints so enviadas para os processos P0 e P2 e aps o recebimento desta mensagens

os processos executam a retirada dos checkpoints locais c10 e c12 e enviam mensagens de conr-

mao deste armazenamento de checkpoints para o processo P1. As mensagens de requisio e

conrmao da retirada de checkpoints so denominadas de mensagens de controle e esto sendo

representadas por retas tracejadas.

Figura 2.10: Abordagem sncrona.

2.3.2 Assncrona

A abordagem assncrona no determina restries para a retirada de checkpoints, cada processo

da aplicao possui autonomia para a seleo de checkpoints relevantes. Os checkpoints que

no formarem um checkpoint global consistente so considerados checkpoints inteis. Nesta

abordagem no existem garantias da constituio de um checkpoint global consistente atravs dos

checkpoints selecionados em cada processo e a aplicao pode retornar ao incio da computao

em caso de falha, esta situao conhecida como efeito domin (12).

Na Figura 2.11 ilustrado um checkpoint global consistente = {c00, c01, c12} e um checkpoint


inutil c02, pois este checkpoint no faz parte de um checkpoint global consistente. Alm disso na

Figura 2.11 exemplicado o cenrio de efeito domin, no qual em caso de a falha nos processos P0

e P1, a aplicao dever retroceder ao inicio da computao, pois os checkpoints destes processos

que formam o checkpoint global consistente (), so considerados como checkpoints inicias dos

processos.

Figura 2.11: Abordagem assncrona.

2.3.3 Quase-sncrona

A abordagem quase-sncrona (8) a combinao das abordagens sncrona e assncrona, na qual a

seleo de checkpoints forados est associada a padres de checkpointing que utiliza protocolos

baseados na anlise das trocas de mensagens da aplicao. Um checkpoint global consistente nesta

abordagem formado selecionando checkpoints bsicos e forados da computao. Os processos

da aplicao dispem da liberdade de escolher de seus checkpoints, porm devem garantir a

determinao de um checkpoint global consistente.

Na Figura 2.12 representada uma abordagem quase-sncrona para a determinao do um

checkpoint global consistente = {c10, c11, c12} , no qual este checkpoint global consistente formadopelos checkpoins bsicos (c10 e c

12) e pelo checkpoint forado c

11.

Figura 2.12: Abordagem Quase-sncrona.

Os padres de checkpointing na abordagem quase-sncrona so divididos em quatros classes

de protocolos: Strictly Z-Path Free (SZPF), Z-Path Free (ZPF), Z-Cycle Free (ZCF) e Partially


Z-Cycle Free (PZCF), que no ser explorado neste trabalho por no garantir a constituio de

checkpoints globais consistentes. Estes protocolos levam em considerao os conceitos de z-paths e

z-cycles descritos na Seo 2.2.4 para gerar checkpoints globais consistentes. Os protocolos SZPF

garantem que a aplicao esteja livre de z-path no causais entre checkpoints e utilizam rastre-

adores de dependncia baseados nas propriedades de Rollback-Dependency Trackability (RDT)

(2) que tambm utilizado nos protocolos ZPF. Esses protocolos diferem dos protocolos SZPF

por permitir a existncia de z-paths no cauais, porm estas z-paths devem estar duplicadas cau-

salmente. Os protocolos ZCF impedem apenas a existncia de z-cycles, enquanto os protocolos

PZCF no garantem a ausncia total de checkpoints inteis e so considerados simplicaes dos

protocolos ZPF e ZCF. Esta hierarquia entre estes protocolos na representada na Figura 2.13.

Figura 2.13: Classes de protocolos quase-sncronos.

Strictly Z-Path Free (SZPF)

Os protocolos SZPF permitem apenas a existncia z-paths causais. A retirada de checkpoints

forados neste padro est baseada na garantia de precedncia entre os eventos de comunicao

de um determinado intervalo entre checkpoints. Alm disso, estes protocolos asseguram au-

sncia de checkpoints inteis e possibilita o rastreamento de dependncias atravs de vetores de

dependncia ou vetores de relgios. Estes protocolos so especicados com base no ModeloMark-

Receive-Send proposto por Russell (14) em 1980. Na Figura 2.14 o Modelo Mark-Receive-Send

ilustrado no processo Pi.

Figura 2.14: Modelo Mark-Receive-Send.


Z-Path Free (ZPF)

Os protocolos ZPF permitem a existncia de z-paths causais e z-paths no causais, desde que

estas z-paths no causais estejam duplicadas causalmente. Neste padro a retirada de um check-

point forado ocorre antes da recepo de uma mensagem m, duplicando causalmente as z-paths

no causais existentes. Na Figura 2.15 ilustrado o comportamento do protocolo FDI (Fixed-

Dependency-Interval) (21), em que os checkpoints forados c11 e c10 so retirados respectivamente

antes da recepo da mensagens m1 e m2. A z-path[m3,m2] no causal est duplicada causal-

mente pela z-path[m1,m2] causal.

Figura 2.15: Z-Path Free (ZPF) - FDI.

Z-Cycle Free (ZCF).

Os protocolos ZCF permitem a existncia z-paths causais e no causais, contudo so livres de

z-cycles. Estes protocolos garantem a utilidade de todos checkpoints da aplicao. A retirada

de checkpoints forados neste padro menor em comparao os protocolos ZPF descritos an-

teriormente. Na Figura 2.16 existe uma ilustrao do comportamento do protocolo BCS (3), no

qual existe uma z-path[m1,m2] no causal que no duplicada causalmente e a seleo de um

checkpoint forado c12 antes da formao da z-cycle[m1,m2,m3].

Figura 2.16: Z-Cycle Free (ZCF) - BCS.

Captulo 3

ChkSim

Este captulo apresenta o funcionamento ChkSim (19). O ChkSim uma ferramenta porttil

usada para simular a execuo de protocolos de checkpointing atravs de histricos de compu-

taes distribudas e permitir a comparao entre esses protocolos. Na Seo 3.1, a arquitetura

do ChkSim detalhada e as classes que formam esta arquitetura so brevemente explicadas. Na

Seo 3.2 descrita o formato de execuo do gerador de cargas LoadGenerator e suas rami-

caes StatisticLG e LupaLogLG. Na Seo 3.3 contm o funcionamento do Wrapper, responsvel

por gerar os arquivos sada do ChkSim. Seo 3.3 apresentada a ferramenta desenvolvida neste

Trabalho de Concluso de Curso, suas funcionalidades e interface grca e a lista de requisitos

funcionais e casos de uso elaborados para o desenvolvido do plugin framework.

3.1 Arquitetura

A arquitetura do ChkSim suporta a manipulao dos conceitos apresentados no Captulo 2.

Seu funcionamento do ChkSim consiste no processamento, em tempo de execuo, de algoritmos

baseados nos protocolos das abordagens quase-sncrona e sncrona no bloqueante em simulaes

de computaes distribudas geradas manualmente em um arquivo no formato XML, em que este

arquivo representa uma aplicao distribuda, as representaes podem ser articiais, geradas

atravs de informaes pr-denidas que simulam uma aplicao distribuda, ou reais, geradas

atravs de histricos de execuo de uma aplicaao distribuda real. Na Figura 3.1 ilustrada a

arquitetura do ChkSim, no qual as representaes das sequncias de eventos so carregadas atravs

da interface LoadGenerator e so processadas na classe Simulator, a qual contm os algoritmos

implementados nas abordagens quase-sncrona e sncrona no bloqueante.

3.2. Gerador de Cargas 27

Figura 3.1: Arquitetura ChkSim

3.2 Gerador de Cargas

O gerador de cargas LoadGenerator identica e encapsula representaes de sequncias de men-

sagens de computaes distribudas atravs da leitura de um arquivo XML. O arquivo XML pode

conter simulaes de computaes distribudas articiais que so processadas pela classe Statis-

ticLG ou conter histricos de computaes distribudas reais, que so identicadas pelo gerador

de cargas LupaLogLG.

O gerador de cargas StatisticLG identica, atravs da leitura do arquivo XML, os compo-

nentes essenciais para a simulao de uma computao distribuda, como o nmero de processos

e eventos. Estas informaes so encapsuladas no arquivo XML juntamente com um valor que

serve como semente para o gerador de cargas e caractersticas sobre a existncia de simetria ou

no entre os processos. Essa semente permite a criao de eventos de modo determinstico e

a simetria ou no entre os processos permite padronizar a execuo desses eventos dentro de

intervalos entre checkpoints.

O gerador de cargas LupaLogLG, identica informaes de execues de aplicaes dis-

tribudas. Essas informaes so obtidas atravs da substituio da biblioteca OpenMPI pela

biblioteca chkmpi. Nesse caso, o LupaLogLG ignora o valor da semente dada e a quantidade de

eventos a serem gerados, descritos no arquivo XML, pois estas informaes no so usadas por

esse gerador de cargas. As informaes obtidas com a execuo da aplicao distribuda devem

ser incorporadas ao arquivo XML. Com o resultado da execuo de uma aplicao distribuda, so

gerados dois arquivos, contendo o histrico de eventos de comunicao e de checkpoints bsicos

retirados, respectivamente. Cada linha do primeiro arquivo contm os nmeros dos processos

origem e destino e os tempos lgicos de envio e recebimento de mensagens. Cada linha do se-

gundo arquivo contm o nmero do processo e o tempo lgico em que este retirou um checkpoint

bsico.

3.3. Wrapper 28

3.3 Wrapper

O Chksim contm um Wrapper que permite a criao de arquivos de sada, visualizados atravs

da ferramenta GnuPlot. O Wrapper do ChkSim gera dois arquivos sada: um no formato .data,

em que na primeira coluna do arquivo contm a quantidade de processos e nas colunas seguintes

tem-se o nmero mdio de checkpoints retirados por algoritmo especicado no arquivo XML.E

outro arquivo no formato .plot, que visualizado pelo GnuPlot, representa gracamente os dados

gerados no arquivo .data.

Os arquivos de sada so nomeados atravs de um padro e diferem em seus formatos:

-.data e -.plot, em que

representa o nome do arquivo XML executado e a mtrica representa o tipo checkpoint determi-

nado pelo arquivo XML, esta mtrica pode ser de checkpoints forados (Forced) ou de checkpoints

bsicos (Basic).

Na Figura 3.2 contm um screenshot da representao de um arquivo .plot. Esta represen-

tao consiste em um grco dos processos em relao a nmero mdio de checkpoints forados

retirados por processo pelos seguintes protocolos da classe ZCF : BCS (3), BCSAftersend (18),

BCSPartner (18), HMNR (6) e FINE (7).

Figura 3.2: Visualizao de uma sada no formato .plot utilizando a ferramenta GnuPlot.

3.4. O Plugin Framework proposto 29

3.4 O Plugin Framework proposto

O plugin framework da ferramenta ChkSim foi desenvolvido na linguagem de programao Java

para este Trabalho de Concluso de Curso, e consiste em um instrumento para a visualizao

grca, usando diagramas espao-tempo, do comportamento de aplicaes distribudas e anlise

do comportamento de protocolos de checkpointing na abordagem Quase-Sncrona. Na Figura

3.3 contm ilustrada a modelagem de domnio da aplicao, em que so apresentadas as prin-

cipais classes do ChkSim e todas as classes que compem o plugin framework, no qual o pacote

ufgd.edu.br.interfaces contm as classes implementadas para a manipulao grca do plugin fra-

mework e o pacote ufgd.edu.br.entity contm as classes implementadas para a manipulao dos

histricos de comunicao da aplicao distrbuida carregados pelo ChkSim.

Figura 3.3: Modelagem de Domnio - Plugin Framework do ChkSim


Para o desenvolvimento desta ferramenta, houve a necessidade de estudo do cdigo fonte

do ChkSim para encontrar uma maneira de implementar o plugin framework, de tal modo que

no houvesse alterao de cdigo, mas , apenas adies pontuais para a captura de informaes

necessrias para a formao das representaes grcas dos histricos das aplicaes distribudas.

As nicas classes que sofreram adicionamento de cdigo esto contidas na Figura 3.3, contudo

a classe com maior relevncia para o plugin framework a QuasiSynchronousSimulator, pois esta

responsvel por identicar, analisar e executar os protocolos de checkpointing para todos os

eventos da aplicao carregada atravs do arquivo XML.

A execuo do plugin framework segue os padro de execuo do ChkSim, atravs da linha

de comando, no qual informado um arquivo com extenso .XML, que contm informaes sobre

o histrico de uma aplicao distribuda e quais de protocolos de checkpointing sero simulados.

A Figura 3.4 mostra como um arquivo .XML pode ser carregado pelo ChkSim.

Figura 3.4: Execuo do Plugin Framework do ChkSim - Linha de Comando

O tempo de execuo pode variar de acordo com o tamanho do histrico de uma aplicao,

pois as aplicaes maiores tendem a demorar mais para executar e portanto geram histricos

maiores. Para demonstrar a manipulao destes histricos existe um loading que informa ao

usurio a porcentagem que est sendo carregada e quais informaes esto sendo manipuladas

no momento. Esse loading apresentado na Figura 3.5.

Figura 3.5: Carregando o Plugin Framework do ChkSim

Aps carregar todas as informaes necessrias o plugin Framework propriamente dito

apresentado. A Figura 3.6 contm um screenshot do plugin Framework, o qual apresenta a fer-

ramenta sendo executada para um histrico de comunicao de uma aplicao distrbuida com 8

processos e executando o protocolo de checkpointing BCS. A representao grca de uma apli-

cao apresentada atravs de um diagrama espao-tempo, em que cada o processo da aplicao

representado por linhas horizontais pretas, os eventos de comunicao so representados por

crculos em vermelho, as mensagens enviadas e recebidas nos processos atravs de linhas na cor

cinza, os checkpoints bsicos representados por quadrados na cor azul e os checkpoints forados

na cor laranja. As funcionalidades do plugin framework estaro descritas posteriormente na lista

de casos de usos atravs da Tabela 3.2.


Figura 3.6: O Plugin Framework do ChkSim propriamente dito.

As representaes grcas podem ser exportadas para o formato SVG (Scalable Vector

Graphics) atravs da opo Exportar para SVG, permitindo ao usurio visualizar o compor-

tamento da aplicao distribuda atravs de seus histricos de comunicao e de checkpoints

em ambientes com suporte a este tipo de formato. A Figura 3.7 contm uma screenshot da

visualizao de um arquivo SVG exportado da aplicao.

Figura 3.7: Visualizao atravs de um navegador de Internet de um arquivo SVG exportado da

aplicao


Para entender melhor o funcionamento do plugin framework do ChkSim so listados na

Tabela 3.1 o conjunto de requisitos funcionais e os casos de uso existentes so listados na Tabela

3.2.

Os requisitos funcionais listados na Tabela 3.1 para o plugin framework do ChkSim foram

considerados obrigatrios.

RF Descrio

#1 O Plugin Framework deve permitir ao usurio visualizar a representa-

o grca de uma aplicao distribuda contida em um arquivo XML

carregado pelo ChkSim.

#2 O usurio deve ter a opo selecionar o protocolo de checkpointing, n-

mero de processos e o intervalo entre cada checkpoint bsico(adicional)

para a escolha da representao grca.

#3 O usurio deve ter a opo visualizar a representao grca da aplica-

o distribuda com os seguintes opcionais de visualizao: numerao

de eventos de comunicao, numerao de checkpoints, mostrar apenas

checkpoints bsicos e/ou forados.

#4 O usurio deve ter a opo exportar a representao grca da aplicao

distribuda para um arquivo SVG.

#5 O Plugin Framework deve exibir ao usurio informaes relevantes a res-

peito da representao da aplicao como: protocolo de checkpointing,

nmero de processos, nmero total de eventos, nmero total de check-

points, nmero de checkpoints bsicos e forados, e intervalo entre cada

checkpoint bsico no processo P0 e nos demais processos.

#6 O Plugin Framework deve exibir ao usurio uma legenda para a repre-

sentao grca da aplicao distribuda.

Tabela 3.1: Requisitos Funcionais do plugin framework do ChkSim


Os casos de uso listados na Tabela 3.2 para o plugin framework do ChkSim foram conside-

rados obrigatrios:

Visualizar aplicaes distribudas atravs de diagrama espao-tempo.

UC: 1

Ator: Usurio

Breve Descrio

Permite ao usurio visualizar a aplicao distribuda de acordo com a seleo do nmero de

processos, protocolo de checkpointing e o intervalo entre cada checkpoint bsico(adicional), com

a nalidade de visualizar situaes aplicao distribuda desejada.

Exportar diagramas espao para o formato SVG.

UC: 2

Ator: Usurio

Breve Descrio

Permite ao usurio exportar a representao grca da aplicao distribuda para o formato

SVG. Tem como a nalidade a visualizao da representao gracamente fora do interface da

ferramenta ou em WebSites

Visualizar opcionalmente conceitos de checkpointing no diagrama espao-tempo.

UC: 3

Ator: Usurio

Breve Descrio

Permite ao usurio escolher se deseja visualizar o numerao dos eventos de comunicao, nu-

merao dos checkpoints e checkpoints bsicos e/ou forados. Tem a nalidade de visualizar as

representaes grcas de acordo com a necessidade desejada.

Tabela 3.2: Casos de Uso do plugin framework do ChkSim

O plugin framework do ChkSim denido como uma ferramenta para a visualizao das

representaes grcas de aplicaes distribidas carregadas pelo ChkSim, atravs de diagramas

espao-tempo que permite ao usurio visualizar os histricos de comunicao de uma aplicao

distribuda e bem como entender o comportamento de protocolos de checkpointing.

Captulo 4

Resultados

Este captulo apresenta os resultados obtidos no desenvolvimento do plugin framework do Chk-

Sim e a comparao da ferramenta desenvolvida com a ferramenta Lupa. Pois, o Lupa utiliza

uma distribuio no mais mantida do MPI, denominada LAM-MPI (Local Area Multicomputer-

Message Passing Interface), e o ChkSim utiliza a biblioteca OpenMPI, que o MPI mantido pela

comunidade atual e ainda no tem suporte para algumas funcionalidades do LAM-MPI.

4.1 Resultados Obtidos

Para a realizao dos testes, obtive-se histricos da execuo da aplicao EP, do NAS Parallel

Benchmarks (1), em trs cenrios adaptados para aplicaes distribudas por Vieira e Buzato

(20). A aplicao EP efetua a gerao variveis aleatrias Gaussianas independentes, utilizando

o mtodo polar Marsaglia (9), um mtodo de amostragem de nmero pseudo-aleatrio para

gerar um par de variveis aleatrias normais com padres independentes. Esses trs cenrios so

apresentados a seguir:

SP : Os processos foram coletados em funo de nmero os processos na aplicao. Este

cenrio composto pelo nmero de processos existentes na aplicao e o intervalo de eventos de

comunicao para cada checkpoint bsico denido por 40 para todos os processos.

SI : Os processos foram coletados em funo do tamanho do intervalo de checkpoints. Este

cenrio composto por 8 processos e os intervalos de checkpointing bsicos variam entre 4 e 118

eventos de comunicao para todos os processos.

VA: Os processos foram coletados em funo da diferena assimtrica. Este cenrio

composto por 8 processos e os intervalos de checkpointing bsicos no processo P0 variam 42

4.1. Resultados Obtidos 35

2 eventos de comunicao e os demais processos da aplicao mantm o intervalo de 44 eventos

de comunicao para checkpointing bsicos.

Para a execuo destes trs cenrios foram utilizados os protocolos de checkpointing BCS,

LazyBCS, LazyBCSAftersend, LazyBCSPartner, HMNR, Fine e LazyHMNR da classe ZCF e os

protocolos FDAS, RDTPartner, RDTMinimal, BHMR da classe ZPF.

Considerando o cenrio SP, atravs da visualizao do diagrama espao-tempo gerado

para um nmero de 8 e 16 processos, percebeu-se que os protocolos da classe ZCF, de modo

geral, economizam mais checkpoints forados que os protocolos da classe ZPF. De acordo com os

dados apresentados nas Tabelas 4.1 e 4.2, obtidos atravs da execuo do ChkSim com o plugin

framework, possvel armar que o protocolo LazyHMNR economiza mais checkpoints forados

entre os protocolos ZCF para a aplicao EP.

8 Processos Checkpoints 16 Processos Checkpoints

Algoritmo Bsicos Forados Algoritmo Bsicos Forados

BCS 16 29 BCS 64 258

LazyBCS 16 29 LazyBCS 64 258

LazyBCSAftersend 16 12 LazyBCSAftersend 64 61

LazyBCSPartner 16 12 LazyBCSPartner 64 61

HMNR 16 12 HMNR 64 61

Fine 16 12 Fine 64 61

LazyHMNR 16 11 LazyHMNR 64 51

Tabela 4.1: Aplicao EP no cenrio SP com 8 e 16 processos executando os protocolos de

checkpointing da classe ZCF - Nmero de checkpoints bsicos e forados.

8 Processos Checkpoints 16 Processos Checkpoints

Algoritmo Bsicos Forados Algoritmo Bsicos Forados

FDAS 16 39 FDAS 64 78

RDTPartner 16 39 RDTPartner 64 78

RDTMinimal 16 39 RDTMinimal 64 78

BHMR 16 39 BHMR 64 78

Tabela 4.2: Aplicao EP no cenrio SP com 8 e 16 processos executando os protocolos de

checkpointing da classe ZPF - Nmero de checkpoints bsicos e forados.


Considerando o cenrio SI atravs, da visualizao do diagrama espao-tempo gerado

para o nmero processos xado em 8 e os intervalos de checkpointing bsicos variando 4 at

70 eventos de comunicao, percebeu-se assim como no cnario SP, que o protocolo LazyHMNR

retirou o menor nmero checkpoints forados. Porm o nmero de checkpoints forados retirados

por todos os protocolos da classe ZPF permaneceu igual, variando apenas para cada intervalo

de checkpointing bsico. Alm disso, os protocolos da classe ZPF economizaram checkpoints

forados em relao aos protocolos BCS e LazyBCS da classe ZCF nos intervalos entre 4

28 eventos de comunicao. De acordo com os dados apresentados nas Tabelas 4.3, 4.4, 4.5 e

4.6, obtidos atravs da execuo do ChkSim com o plugin framework, possvel rearmar que

o protocolo LazyHMNR economiza mais checkpoints forados entre os protocolos ZCF, contudo

os protocolos da classe ZPF economizam checkpoints forados em relao aos protocolos BCS e

LazyBCS da classe ZCF nos intervalos entre 4 28 eventos de comunicao.

Intervalo 4-4 Intervalo 10-10 Intervalo 16-16

Checkpoints Checkpoints Checkpoints

Algoritmo Bsicos Forados Bsicos Forados Bsicos Forados

BCS 160 211 64 108 40 0

LazyBCS 160 199 64 108 40 0

LazyBCSAftersend 160 25 64 32 40 0

LazyBCSPartner 160 25 64 32 40 0

HMNR 160 24 64 32 40 0

Fine 160 24 64 32 40 0

LazyHMNR 160 15 64 30 40 0

FDAS 160 30 64 36 40 35

RDTPartner 160 30 64 36 40 35

RDTMinimal 160 30 64 36 40 35

BHMR 160 30 64 36 40 35

Tabela 4.3: Aplicao EP no cenrio SI com 8 processos e os intervalos entre checkpointing

bsicos de 4, 10 e 16 eventos de comunicao executando os protocolos das classes ZCF e ZPF.





BCS 24 59 16 44 16 37

LazyBCS 24 59 16 44 16 37



HMNR 24 25 16 20 16 19

Fine 24 25 16 20 16 19

LazyHMNR 24 24 16 15 16 19

FDAS 24 38 16 38 16 39

RDTPartner 24 38 16 38 16 39

RDTMinimal 24 38 16 38 16 39

BHMR 24 38 16 38 16 39






BCS 16 29 8 8 8 22

LazyBCS 16 29 8 8 8 22



HMNR 16 12 8 8 8 10

Fine 16 12 8 8 8 10

LazyHMNR 16 11 8 2 8 10

FDAS 16 39 8 38 8 39

RDTPartner 16 39 8 38 8 39

RDTMinimal 16 39 8 38 8 39

BHMR 16 39 8 38 8 39







BCS 8 22 8 0 8 29

LazyBCS 8 22 8 0 8 29



HMNR 8 11 8 0 8 11

Fine 8 11 8 0 8 11

LazyHMNR 8 8 8 0 8 11

FDAS 8 38 8 38 8 39

RDTPartner 8 38 8 38 8 39

RDTMinimal 8 38 8 38 8 39

BHMR 8 38 8 38 8 39



Considerando o cenrio VA, atravs da visualizao do diagrama espao-tempo gerado com

o plugin framework para o nmero processos xado em 8, e os intervalos de checkpointing bsicos

variando 42 a 2 eventos de comunicao no processo P0 e nos demais processos com o intervalo de

checkpointing bsicos xo em 42 eventos de comunicao, percebeu-se assim como nos cenrios

SI e SP, que o protocolo LazyHMNR retirou o menor nmero checkpoints forados. Alm disto,

todos os protocolos da classe ZPF retiraram 38 checkpoints forados, independente do intervalo

de checkpointing bsicos, e economizaram checkpoints forados em comparao aos protocolos

BCS e LazyBCS para os intervalos de 10, 6 e 2 eventos de comunicao. De acordo com os

dados apresentados nas Tabelas 4.7, 4.8, 4.9 e 4.10, obtidos atravs da execuo do ChkSim com

o plugin framework, possvel rearmar que o protocolo LazyHMNR economiza mais checkpoints

forados entre os protocolos ZCF. Contudo os protocolos da classe ZPF economizam checkpoints

forados em relao aos protocolos BCS e LazyBCS da classe ZCF, nos intervalos de 10, 6 e 2

eventos de comunicao, porm o nmero de checkpoints forados retirados para os protocolos

ZPF permaneceu xo em 38, independente da variao de intervalos de checkpointing bsicos.





BCS 8 15 9 23 9 30

LazyBCS 8 15 9 23 9 30



HMNR 8 9 9 12 9 20

Fine 8 9 9 12 9 20

LazyHMNR 8 5 9 7 9 17

FDAS 8 38 9 38 9 38

RDTPartner 8 38 9 38 9 38

RDTMinimal 8 38 9 38 9 38

BHMR 8 38 9 38 9 38

Tabela 4.7: Aplicao EP no cenrio VA com 8 processos e os intervalos entre checkpointing

bsicos de 42, 38 e 34 eventos de comunicao no processo P0 e 44 eventos de comunicao paraos demais processos, executando os protocolos das classes ZCF e ZPF.




BCS 9 22 10 22 10 29

LazyBCS 9 22 10 22 10 29



HMNR 9 14 10 13 10 19

Fine 9 14 10 13 10 19

LazyHMNR 9 11 10 11 10 18

FDAS 9 38 10 38 10 38

RDTPartner 9 38 10 38 10 38

RDTMinimal 9 38 10 38 10 38

BHMR 9 38 10 38 10 38







BCS 11 36 12 35 15 40

LazyBCS 11 36 12 35 15 40



HMNR 11 28 12 27 15 28

Fine 11 28 12 27 15 28

LazyHMNR 11 24 12 19 15 23

FDAS 11 38 12 38 15 38

RDTPartner 11 38 12 38 15 38

RDTMinimal 11 38 12 38 15 38

BHMR 11 38 12 38 15 38



Intervalo 6-44 Intervalo 2-44

Checkpoints Checkpoints

Algoritmo Bsicos Forados Bsicos Forados

BCS 20 63 47 97

LazyBCS 20 52 47 45

LazyBCSAftersend 20 27 47 25

LazyBCSPartner 20 27 47 25

HMNR 20 33 47 33

Fine 20 27 47 31

LazyHMNR 20 24 47 25

FDAS 20 38 47 38

RDTPartner 20 38 47 38

RDTMinimal 20 38 47 38

BHMR 20 38 47 38


bsicos de 6 e 2 eventos de comunicao no processo P0 e 44 eventos de comunicao para osdemais processos, executando os protocolos das classes ZCF e ZPF.

Atravs da execuo do plugin framework para estes cenrios na aplicao distribuda EP,

foram gerados diagramas espao-tempo, que permitiram analisar as representaes grcas da

aplicao distribuda manualmente em comparao aos histricos de comunicao carregados

pelo ChkSim. Os checkpoints forados retirados gerados nas representaes grcas para os

diferentes protocolos de checkpointing implementados no ChkSim na abordagem Quase-Sncrona

4.2. Comparao com a ferramenta Lupa 41

foram vericados analisando manualmente as heursticas de cada protocolo de checkpointing em

comparao aos resultados gerados nos diagramas espao-tempo pela ferramenta desenvolvida.

4.2 Comparao com a ferramenta Lupa

O plugin framework do ChkSim uma ferramenta similar a ferramenta Lupa, que consistem um

ambiente de visualizao e animao de sistemas distribudos que utiliza o conceito de checkpoints

para construir sequncias de animao de algoritmos atravs de diagramas espao-tempo.

Para validar a ferramenta desenvolvida realizou-se comparaes entre o plugin framework

e ao Lupa am de confrontar suas funcionalidades e as interfaces grcas, para determinar as

vantagens e desvantagens do plugin framework do ChkSim em relao ao Lupa. Estas comparaes

so apresentadas atravs dos dados contidos na Tabela 4.11.

Funcionalidades Plugin Framework Lupa

Apresenta o nmero de

Sim No

processos da aplicao

Apresenta o intervalo

Sim No

entre checkpoints

Visualizao de

Sim Sim

checkpoints bsicos

Visualizao opcional

Sim No

de checkpoints forados

Visualizao do tempo

Sim Sim

lgico dos eventos

Construo de checkpoints

No Sim

globais consistentes

Permite a execuo de uma

No se aplica Sim

aplicao distribuda pela ferramenta

Exporta para formato SVG Sim No

Interfaces grcas Plugin Framework Lupa

Uso de legendas para

Sim No

apresentao das caractersticas

Visualizao do nmero de

Sim Sim

checkpoints bsicos/forados

Tabela 4.11: Comparando o plugin framework do ChkSim com o Lupa.

4.2. Comparao com a ferramenta Lupa 42

4.2.1 Vantagens e Desvantagens em comparao ao Lupa

Atravs dos dados de comparao entre as funcionalidades e as interfaces grcas da ferramenta

proposta e do Lupa apresentados Tabela 4.11, possvel determinar que o plugin framework do

ChkSim exerce vantagens signicativas e uma desvantagem expressiva sobre o Lupa.

No quesito de funcionalidades, a ferramenta proposta permite ao usurio selecionar diferen-

tes protocolos de checkpointing para uma determinada aplicao distribuda, permite ao usurio

selecionar diferentes intervalos de checkpointing bsico, permite ao usurio visualizar opcional-

mente checkpoints forados, alm disto uma vantagem importante, referente a funcionalidade de

exportao dos diagramas espao-tempo para o formato SVG, que permite ao usurio visualizar

as representaes geradas em diferentes ambientes com suporte a este tipo de formato.

No quesito de interfaces grcas, plugin framework do ChkSim exerce uma vantagem sobre

o Lupa, pois a ferramenta desenvolvida apresenta uma legenda para os diagramas espao-tempo,

permitindo aos usurios uma fcil compreenso sobre estes diagramas gerados para uma deter-

minada aplicao distribida.

Contudo uma desvantagem expressiva em relao ao Lupa a no obteno de checkpoints

globais consistentes, na qual a ferramenta Lupa obtm estes checkpoints globais consistentes a

partir da seleo de qualquer checkpoint representado no diagrama espao-tempo gerado pela

prpria ferramenta.

Captulo 5

Consideraes Finais

Este captulo apresenta as concluses sobre o trabalho desenvolvido, as diculdades encontradas

ao longo deste desenvolvimento e sugesto de trabalhos futuros.

5.1 Concluses

Com o desenvolvimento do plugin framework proposto para visualizao do histrico de apli-

caes distribudas, atravs de diagramas espao-tempo, acredita-se que a visualizao grca

dessas aplicaes auxilia de maneira dedigna para entender o comportamento de protocolos

de checkpointing. Alm disso, atravs do plugin framework pode-se facilmente vericar uma

diferena entre os protocolos ZPF e ZCF quando executando a aplicao EP do NAS (1) nos

cenrios apresentados.

Considerando a aplicao EP, conseguiu-se mostrar, atravs de trs cenrios, diagramas

espao-tempo gerados atravs da ferramenta proposta, foi possvel analisar, por meio desses

diagramas que na aplicao EP, o protocolo LazyHMNR da classe ZCF obteve o melhor desem-

penho em comparao aos demais protocolos das classes ZCF e ZPF. Claramente, os protocolos

ZCF retiram menos checkpoints forados que os protocolos ZPF. Para a aplicao EP, esse fato

ocorre porqu os protocolos da classe ZCF permitem a existncia de z-paths causais e z-paths

no causais, no permitindo a existncia z-cycles, garantindo utilidade de todos os checkpoints

da aplicao.

As comparaes realizadas em termos de funcionalidades e interfaces grcas do plugin fra-

mework com o Lupa mostraram que o primeiro exerce uma relevante vantagem sobre o segundo

devido s inmeras funcionalidades existentes na ferramenta proposta, contudo a no represen-

5.2. Diculdades Encontradas 44

tao de checkpoints globais por parte do plugin framework consiste em uma desvantagem em

relao ao Lupa.

Como contribuio, a visualizao grca de histricos de aplicaes distribudas gerados

pelo plugin framework pode ser til para estudantes da rea da Tecnologia da Informao, pois

com isso eles podem compreender este tipo de aplicao e o comportamento de protocolos de

checkpointing.

5.2 Diculdades Encontradas

Primeiramente as diculdades encontradas foram relacionadas aos conceitos de protocolos de

checkpointing. Apesar do conhecimento adquirido no curso de Bacharelado em Sistemas de

Informao, este Trabalho de Concluso de Curso englobou conceitos especcos sobre aplicaes

distribudas, como os conceitos envolvendo checkpointing.

Outras diculdades surgiram na redao do texto, devido ao uso da plataforma L

A

T

E

X,

que no comeo mostrou-se uma ferramenta de gerao de textos complexa. Contudo, aps a

pratica adquirida com o desenvolvimento do Trabalho de Concluso de Curso I, esta ferramenta

mostrou-se mais simples e eciente para a redao de textos.

Finalmente, na implementao do Plugin Framework, as diculdades ocorreram, princi-

palmente, na manipulao das bibliotecas disponveis na linguagem de programao Java para

o desenvolvimento de desenhos geomtricos, exigindo uma lgica e estrutura de programao

relativamente complexa para a gerao automtica das representaes grcas dos histricos das

aplicaes distribudas, alm de um estudo do formato de arquivos SVG, formato este que foi

denido no Trabalho de Concluso de Curso I como ideal para a exportao das representaes

grcas geradas pela ferramenta proposta.

5.3 Trabalhos Futuros

Este Trabalho de Concluso de Curso elencou como prioridade a gerao de representaes gr-

cas de histricos de aplicaes distribudas, os quais so carregadas no ChkSim atravs do gerador

de cargas denominado LupaLogLG, descrito no Captulo 3 (Seo 3.2) e essas representaes gera-

das atravs da ferramenta desenvolvida. Contudo, para o plugin framework gerar representaes

grcas a partir do StatisticLG, necessria a adio e alterao no cdigo-fonte do ChkSim.

Sendo assim, esta uma situao prevista para uma nova verso do plugin framework.

5.3. Trabalhos Futuros 45

Outra proposta de trabalhos futuros permitir ao plugin framework a visualizao das

representaes grcas considerando os protocolos de checkpointing da abordagem Sncrona No-

Bloqueante. Esta variante da abordagem Sncrona no est descrita neste Trabalho de Concluso

de Curso, contudo na ferramenta ChkSim existem protocolos de checkpointing implementados

para esta variante e a manipulao desta abordagem exigir um novo estudo sobre esses proto-

colos de checkpointing e o seu comportamento em aplicaes distribudas, pois esta abordagem

engloba novos conceitos como mensagens de controle entre os processos da aplicao.

Atravs da comparao do plugin framework do ChkSim com a ferramenta Lupa, deniu-se

que para uma nova verso, a ferramenta deve conter a funcionalidade de permitir ao usurio a

obteno de checkpoints globais consistente a partir da seleo de uma determinado checkpoint

contido nos diagramas espao-tempo.

Referncias Bibliogrcas

1 D. H. Bailey, E. Barszcz, J. T. Barton, D. S. Browning, R. L. Carter, L. Dagum, R. A.

Fatoohi, P. O. Frederickson, T. A. Lasinski, R. S. Schreiber, H. D. Simon, V. Venkatakrishnan,

and S. K. Weeratunga. The nas parallel benchmarkssummary and preliminary results.

In Proceedings of the 1991 ACM/IEEE Conference on Supercomputing, pages 158165, New

York, NY, USA, 1991. ACM.

2 Roberto Baldoni, Jean michel Helary, Achour Mostefaoui, and Michel Raynal. A

communication-induced checkpointing protocol that ensures rollback-dependency trackability.

In Proc. IEEE Int. Symposium on Fault Tolerant Computing, pages 6877, 1997.

3 D. Briatico, A. Ciuoletti, and L. Simoncini. A distributed domino-eect free recovery

algorithm. In Symposium on Reliability in Distributed Software and Database Systems 84, pages

207215, 1984.

4 K. Mani Chandy and Leslie Lamport. Distributed snapshots: determining global states of

distributed systems. ACM Trans. Comput. Syst., 3:6375, February 1985.

5 I.C. Garcia and L.E. Buzato. An ecient checkpointing protocol for the minimal

characterization of operational rollback-dependency trackability. In Reliable Distributed

Systems, 2004. Proceedings of the 23rd IEEE International Symposium on, pages 126 135, oct.

2004.

6 J.-M. Hlary, A. Mostefaoui, R.H.B. Netzer, and M. Raynal. Communication-based

prevention of useless checkpoints in distributed computations. Distributed Computing, 13:2943,

2000. 10.1007/s004460050003.

7 Y. Luo and D. Manivannan. Fine: A fully informed and ecient communication-induced

checkpointing protocol for distributed systems. Journal of Parallel and Distributed Computing,

69(2):153167, 2009.

8 D. Manivannan and Mukesh Singhal. Quasi-synchronous checkpointing: Models,

characterization, and classication. IEEE Transactions on Parallel and Distributed Systems,

10:703713, 1996.

9 G. Marsaglia and T. A. Bray. A convenient method for generating normal variables.

j-SIAM-REVIEW, 6(3):260264, 1964.

10 R.M. Menderico. Ambiente pra a visualizao de protocolos de checkpointing.

http://lupa.sourceforge.net/index.html, Fevereiro 2004. ltimo acesso em Setembro de

2012.

REFERNCIAS BIBLIOGRFICAS 47

11 Robert H. B. Netzer and Jian Xu. Necessary and sucient conditions for consistent global

snapshots. IEEE Trans. Parallel Distrib. Syst., 6(2):165169, February 1995.

12 B. Randell. System structure for software fault tolerance. SIGPLAN Not., 10(6):437449,

April 1975.

13 Gabriel Rodrguez, Mara J. Martn, Patricia Gonzlez, Juan Tourio, and Ramn Doallo.

Cppc: a compiler-assisted tool for portable checkpointing of message-passing applications.

Concurrency and Computation: Practice and Experience, 22(6):749766, 2010.

14 David L. Russell. State restoration in systems of communicating processes. In IEEE

tinsactions on Pamllel and Dist n buted Systems, pages 910, 1980.

15 T.C. Sakata and I.C. Garcia. Non-blocking synchronous checkpointing based on

rollback-dependency trackability. In Reliable Distributed Systems, 2006. SRDS '06. 25th IEEE

Symposium on, pages 411420. IEEE Computer Society, October 2006.

16 Tiemi Christine Sakata. Uma Ponte entre as Abordagens Sncrona e Quase-sncrona

para Checkpointing. Tese, Instituto de Computao - Universidade Estadual de Campinas

(UNICAMP), Dezembro 2006.

17 J. Tsai and J.-W. Lin. On the fully-informed communication-induced checkpointing

protocol. In Dependable Computing, 2005. Proceedings. 11th Pacic Rim International

Symposium on, page 8 pages, December 2005.

18 G. M. D. Vieira. Estudo comparativo de algoritmos para checkpointing. Dissertao,

Instituto de Computao - Universidade Estadual de Campinas (UNICAMP), Dezembro 2001.

19 G. M. D. Vieira and L. E. Buzato. Chksim: A distributed checkpointing simulator.

Technical Report IC-05-34, Institute of Computing, University of Campinas, December 2005.

20 Gustavo MD Vieira and Luiz E Buzato. Distributed checkpointing: Analysis and

benchmarks, 2006.

21 Yi-Min Wang. Consistent global checkpoints that contain a given set of local checkpoints.

IEEE Trans. Comput., 46(4):456468, April 1997.

PROTOCOLO DE CHECKPOINTING - TCC - CAUAN KASPER

Documents

Transcript of PROTOCOLO DE CHECKPOINTING - TCC - CAUAN KASPER