( PDF ) Algoritmos Distribuídos para o Problema de Alocação de Múltiplos Recursos em Grids Computacionais

Download PDF

ads:

Universidade Federal Fluminense

HIGOR DE P

ADUA VIEIRA NETO

NITER

OI-RJ

2008

ads:

Livros Grátis

http://www.livrosgratis.com.br

Milhares de livros grátis para download.

Universidade Federal Fluminense

HIGOR DE P

ADUA VIEIRA NETO

Disserta¸c˜ao de Mestrado submetida ao Pro-

grama de P´os-Gradua¸c˜ao em Computa¸c˜ao da

Universidade Federal Fluminense como re-

quisito parcial para a obten¸c˜ao do t´ıtulo de

Mestre.

Area de concentra¸c˜ao: Processa-

mento Paralelo e Distribu´ıdo.

Orientador:

Prof. L´ucia Maria A. Drummond, D.Sc.

NITER

OI-RJ

2008

ads:

Algor itmos Distribu´ıdos para o Problema de Al oca¸c˜ao de M´ultiplo s

Recursos em Grids Computacionais

Higor de P´adua Vieira Neto

Disserta¸c˜ao de Mestrado submetida ao Pro-

grama de P´os-Gradua¸c˜ao em Computa¸c˜ao da

Universidade Federal Fluminense como re-

quisito parcial para a obten¸c˜ao do t´ıtulo de

Mestre.

Area de concentra¸c˜a o: Processa-

mento Paralelo e Distribu´ıdo.

Aprovada por:

Profa. L´ucia Maria A. Drummond, DSc / IC-UFF

(Orientadora)

Prof. Eugene Francis Vino d Rebello, PhD / IC-UFF

Profa. Maria Clicia Stelling de Castro, DSc / IME-UERJ

Niter´oi, 18 de agosto de 2008.

Aos meus pais, por todo o amor, carinho e apoio.

Primeiramente agrade¸co `a Deus, por ter me fortiﬁcado na f´e nos diversos momentos

de diﬁculdade e por ter me dado a luz nos caminhos mais escuros.

A minha fam´ılia que sempre me deu suporte para que eu vencesse todos os meus

desaﬁos, aos quais tamb´em compartilho mais essa vit´oria. Meu pai, minha m˜ae, minha

irm˜a e sobrinhas.

A minha namora da Geisiane, com quem sempre pude contar, sempre esteve ao meu

lado me apoiando e me dando for¸cas para que eu conseguisse alcan¸car meu objetivo.

A minha orientadora, L´ucia Drummond, pela valiosa orienta¸c˜ao, fundamental para

que eu ﬁzesse esse trabalho.

A todos amigos conquistados no IC/UFF, em especial aos amigos Warley (t oca) e

Vinicius com quem compartilhei noites de estudos no laborat´orio, e tamb´em pela grande

parceria e ajuda no desenvolvimento desse trabalho. Ao amigo Jacques pelo empenho em

ajudar provendo alguns dos recursos necess´arios para os testes no laborat´orio.

Aos colegas de trabalho, em nome de Rodrigo C. Fernandes (Petrobr´as), meus sinceros

agradecimentos por toda ajuda e apo io recebidos, imprescind´ıveis para o desfecho desse

trabalho.

Aos velhos amigos da Doctumtec e FIC de Caratinga, que me inspiraram e estiveram

comigo em gr ande parte de minha hist´oria acadˆemica e proﬁssional. Tamb´em ao amigo

e ex-professor/chefe Prof. Dr . Ulisses Leit˜ao que acreditou em mim na hora que precisei

dar esse grande passo em minha carreira.

A todas as pessoas que contribu´ıram direta ou indiretamente, e que ﬁzeram parte

dessa minha trajet´oria, Obrigado!

Tipicamente, uma Grid ´e composta por uma cole¸c˜ao de clusters, cujo n´os s˜ao conectados

por enlaces dedicados de alta velocidade. A comunica¸c˜ao entre n´os de clusters distintos ´e

feita por WANs de baixa velocidade. Assim, ´e desej´avel que os algoritmos de sincroniza¸c˜ao

sejam escal´aveis e considerem t al topologia hier´arquica de rede.

Neste trabalho ´e proposto um algoritmo baseado em token para resolver o problema da

aloca¸c˜ao de m´ultiplos recursos considerando a topologia hier´arquica usual em ambientes

de Grid.

Poucos trabalhos apresentam um algoritmo para exclus˜ao m´utua especiﬁcamente para

Grids. Normalmente, eles consideram o compartilhamento de apenas um ´unico r ecurso.

Por´em, ´e t´ıpico em Grids existir v´arios tipos de recursos compartilhados, incluindo hard-

ware tais como RAM, espa¸co em disco, canais de comunica¸c˜ao e software tais como pro-

gramas, arquivos e dados.

O algoritmo proposto foi comparado com um outro algoritmo baseado em token que

resolve o problema de a loca¸c˜ao de m´ultiplos recursos, mas que n˜ao considera as particu-

laridades dos ambientes de Grid.

A redu¸c˜ao no n´umero de mensagens inter-clusters e no tempo de espera para entrar

na se¸c˜a o cr´ıtica torna o algoritmo proposto bastante atrativo para aplica¸c˜oes de Grid.

Palavras-chave:Algoritmos Distribu´ıdos, Exclus˜ao M´utua, Grades Computacionais, Alo-

ca¸c˜ao Dinˆamica de Recursos.

Typically, a Grid is composed of a collection of clusters, with the nodes within each

cluster being connected by high-speed dedicated links. Communication among nodes in

distinct clusters is performed by much slower WANs. So, it would like to have scalable

synchronization algorithms take into account such hierarchical network topology.

In this work, we propose a token-based algorithm to solve the multiple r esource allo-

cation problem considering the usual hierarchical network topology of Grid environments.

Few papers present a mutual exclusion algorithm speciﬁcally for Grids and usually they

consider the sharing of a unique resource. However, it is typical in Grids to have several

kinds of shared resources, including hardware such as RAM, disk space, communication

channels, and software such as programs, ﬁles and data.

We compared the proposed algorithm with a well known token-based algorithm for sol-

ving the multiple resource allocation problem, which does not consider the particularities

of Grid environments.

The r eduction in the number of inter-cluster messages and the waiting time to enter

a critical section makes the proposed algorithm very attractive for Grid applications.

Keywords: Distributed Algorithms, Mutual Exclusion, Computational Grids, Dynamic

Resource Allocation Problem.

C T : Control Token;

SC : Se¸c˜ao Cr´ıtica;

1.1 Organiza¸c˜ao da Disserta¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.1 Introdu¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2.2 Classiﬁca¸c˜ao dos Algoritmos Distribu´ıdos para Exclus˜ao M´utua . . . . . . 5

2.2.1 Algoritmos Baseados em Permiss˜ao . . . . . . . . . . . . . . . . . . 6

2.2.1.1 Baseados em Votos . . . . . . . . . . . . . . . . . . . . . . 6

2.2.1.2 Baseados em Coterie . . . . . . . . . . . . . . . . . . . . . 7

2.2.2 Algoritmos Baseados em Token . . . . . . . . . . . . . . . . . . . . 7

2.2.2.1 Baseados em Broadcast . . . . . . . . . . . . . . . . . . . 7

2.2.2.2 Baseados em Estruturas L´ogicas . . . . . . . . . . . . . . 8

Baseados em

Arvore: . . . . . . . . . . . . . . . . . . . . . . 8

Baseados em Grafos: . . . . . . . . . . . . . . . . . . . . . . 8

Baseados em Anel: . . . . . . . . . . . . . . . . . . . . . . . 9

2.2.3 Algoritmos H´ıbridos . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.3 Solu¸c˜oes Existentes para Ambientes Hier´arquicos e de Grids . . . . . . . . 9

Sum´ario ix

2.4 Solu¸c˜oes Relacionadas `a Proposta . . . . . . . . . . . . . . . . . . . . . . . 10

2.4.1 Solu¸c˜oes Hier´arquicas . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.4.1.1 Algoritmo de Bertier et al. . . . . . . . . . . . . . . . 11

2.4.2 Solu¸c˜oes para M´ultiplos Recursos . . . . . . . . . . . . . . . . . . . 12

2.4.2.1 Algoritmo de Bouabdallah e Laforest . . . . . . . . . . 12

2.5 Solu¸c˜oes Recentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.1 Introdu¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3.2 Descri¸c˜ao do algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3.2.1 Conﬁgura¸c˜ao Inicial da

Arvore . . . . . . . . . . . . . . . . . . . . . 16

3.2.2 Est´agio 1 - Obten¸c˜a o do Control Token . . . . . . . . . . . . . . . . 17

3.2.2.1 Exemplo de requisi¸c˜ao local de CT . . . . . . . . . . . . . 18

3.2.2.2 Exemplo de requisi¸c˜ao remota de CT . . . . . . . . . . . . 19

3.2.3 Est´agio 2 - Obtendo To kens dos Recursos . . . . . . . . . . . . . . 22

3.3 An´alise de Complexidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

4.1 Rel´ogios L´o gicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.2 Rel´ogios L´o gicos como Estrat´egia de Medi¸c˜ao de Desempenho . . . . . . . 35

5.1 Ambiente de Testes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

5.2 Algoritmo Proposto vs. Bouabdallah-La forest para M´ultiplos Recursos com

Uma Instˆancia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

5.2.1 Varia¸c˜ao da latˆencia entre c l usters . . . . . . . . . . . . . . . . . . 42

5.2.1.1 Compara¸c˜ao dos algoritmos usando Rel´ogios L´ogicos . . . 42

5.2.1.2 Compara¸c˜ao dos algoritmos usando Rel´ogio F´ısico . . . . . 44

Sum´ario x

5.3 Algoritmo Proposto vs. Bouabdallah-La forest para M´ultiplos Recursos com

M´ultiplas Instˆancias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

5.3.1 Varia¸c˜ao da latˆencia entre c l usters . . . . . . . . . . . . . . . . . . 46

5.3.1.1 Compara¸c˜ao dos algoritmos usando Rel´ogios L´ogicos . . . 47

5.3.1.2 Compara¸c˜ao dos algoritmos usando Rel´ogio F´ısico . . . . . 48

5.3.2 Varia¸c˜ao do N´umero de Tipos de Recursos . . . . . . . . . . . . . . 51

5.3.3 Varia¸c˜ao do N´umero Total de Processos . . . . . . . . . . . . . . . 52

5.3.4 Varia¸c˜ao do N´umero de Cl usters . . . . . . . . . . . . . . . . . . . . 53

1.1 Arquitetura Grid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2.1

Arvore de classiﬁca¸c˜ao dos algoritmos distribu´ıdos para exclus˜ao m´utua

[52, 13] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

3.1 Conﬁgura¸c˜ao l´ogica de ´arvore tradicional, segundo [38]. . . . . . . . . . . . 16

3.2 Conﬁgura¸c˜ao l´ogica de uma ´arvore com hierarquia . . . . . . . . . . . . . . 16

3.3 Requisi¸c˜oes de Control Token . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.4 Caminho 1 do Control Token . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.5 Caminho 2 do Control Token . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.6 Estrutura do Con trol Token recebida . . . . . . . . . . . . . . . . . . . . . 23

3.7 Obtem os tokens livres do CT . . . . . . . . . . . . . . . . . . . . . . . . . 24

3.8 Libera tokens n˜ao utilizados ao CT . . . . . . . . . . . . . . . . . . . . . . 24

3.9 Seleciona tokens considerando localiza¸c˜ao . . . . . . . . . . . . . . . . . . . 26

3.10 Seleciona tokens considerando prioridade . . . . . . . . . . . . . . . . . . . 26

3.11 Envia pedidos de r ecursos aos processos selecionados . . . . . . . . . . . . 27

3.12 Recebe as mensagens de ACK1 e ACK2 . . . . . . . . . . . . . . . . . . . 28

4.1 Rela¸c˜ao acon teceu-antes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.2 Rel´ogio de Lamport . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

4.3 Rel´ogio de Vetor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

4.4 Exemplo de Execu¸c˜ao do Rel´ogio L´ogico . . . . . . . . . . . . . . . . . . . 36

4.5 Rel´ogio de Vetor Proposto . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

5.1 Varia¸c˜ao da latˆencia - M´ultiplos Recursos com uma Instˆancia - Rel´ogio L´ogico 43

Lista de Figuras xii

5.2 Varia¸c˜ao da latˆencia - M´ultiplos Recursos com uma Instˆancia - Rel´ogio

F´ısico (Sleep) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

5.3 Varia¸c˜ao da latˆencia - M´ultiplos Recursos com uma Instˆancia - Rel´ogio

F´ısico (NetEm) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

5.4 Varia¸c˜ao da latˆencia - M´ultiplos Recursos com M´ultiplas Instˆancias - Re-

l´ogio L´ogico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

5.5 Varia¸c˜ao da latˆencia - M´ultiplos Recursos com M´ultiplas Instˆancias - Re-

l´ogio F´ısico (Sleep) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

5.6 Varia¸c˜ao da latˆencia - M´ultiplos Recursos com M´ultiplas Instˆancias - Re-

l´ogio F´ısico (NetEm) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

5.7 Varia¸c˜ao do n´umero de tipos de recursos - M´ultiplos Recursos com M´ulti-

plas Instˆancias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

5.8 Varia¸c˜ao do n´umero de t otal de processos - M´ultiplos Recursos com M´ul-

tiplas Instˆancias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

5.9 Varia¸c˜ao do n´umero de clusters - M´ultiplos Recursos com M´ultiplas Instˆancias 55

5.1 Tempos M´edios e Desvio Padr˜ao - Varia¸c˜ao de Latˆencias - M´ultiplos

Recursos com U ma Instˆancia . . . . . . . . . . . . . . . . . . . . . . 46

5.2 Tabela do N´umero de Mensagens Trocadas - Varia¸c˜ao de Latˆencias -

M´ultiplos Recursos com Uma Instˆancia . . . . . . . . . . . . . . . . 46

5.3 Tabela de M´edi a s e Desvio Padr˜ao - Varia¸c˜ao de Latˆencias - M´ulti-

plos Recu rsos com M´ultiplas Instˆancias . . . . . . . . . . . . . . . . 50

5.4 Tabela do N´umero de Mensagens Trocadas - Varia¸c˜ao de Latˆencias -

M´ultiplos Recursos com M´ultiplas Instˆancias . . . . . . . . . . . . 50

5.5 Tabela de M´edias e Desvio Padr˜ao - Varia¸c˜ao do N´umero de Tipos

de Recursos - M´ultiplos Recursos com M´ultiplas Instˆancias . . . 52

5.6 Tabela de M´edias e Des vio Padr˜ao - Varia¸c˜ao do N´umero de Proces-

sos - M´ultiplos Recursos com M´u ltiplas Instˆancias . . . . . . . . . 54

5.7 Tabela de M´edias e Desvio Padr˜ao - Varia¸c˜ao do N´umero de Clusters

- M´ultiplos Recursos com M´ultiplas Instˆancias . . . . . . . . . . . 55

1 - Inicializa¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2 - Requisi¸c˜ao para acesso `a se¸c˜ao cr´ıtica . . . . . . . . . . . . . . . . . . . . 19

3 - Recebe pedido de CT (vers˜ao simpliﬁcada) . . . . . . . . . . . . . . . . . 20

4 - Recebe pedido de CT (vers˜ao estendida) . . . . . . . . . . . . . . . . . . 21

5 - Recebe mensagem de preemp¸c˜ao . . . . . . . . . . . . . . . . . . . . . . 22

6 - Recebe control token . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

7 - Pega os tokens livres no CT . . . . . . . . . . . . . . . . . . . . . . . . . 24

8 - Seleciona os tokens necess´arios . . . . . . . . . . . . . . . . . . . . . . . 25

9 - Atualiza as prioridades dos processos (Processo S

) . . . . . . . . . . . . 27

10 - Recebe pedido de to ken . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

11 - Recebe mensagem de ACK (ACK1 e ACK2) . . . . . . . . . . . . . . . . 28

12 - Libera a se¸c˜ao cr´ıtica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

13 - A¸c˜oes em p para o algoritmo REL

OGIO DE LAMPORT: . . . . . . . . . . . . 34

14 - A¸c˜oes em p para o algoritmo REL

OGIO DE VETOR: . . . . . . . . . . . . . 35

15 - Adapta¸c˜ao do Rel´ogio L´ogico - Processo P

. . . . . . . . . . . . . . . . . 37

Muitas aplica¸c˜oes distribu´ıdas requerem que um recurso seja alocado a somente um

processo por vez. Cada processo possui um segmento de c´odigo, denominado de se¸c˜ao

cr´ıtica (SC), na qual ele acessa os recursos compartilhados. O problema de coordenar a

execu¸c˜ao da se¸c˜ao cr´ıtica ´e resolvido usando o princ´ıpio da exclus˜ao m´utua, que provˆe

acesso exclusivo aos recursos compartilhados em cada tempo.

Algoritmos que r esolvem o problema da exclus˜ao m´utua em sistemas distribu´ıdos

podem ser basicamente divididos em dois grupos: algoritmos baseados em permiss˜ao (tais

como [48], [46], [2 9] e [43]) e algoritmos baseados em token (tais como [17], [38], [36], [8]

e [9]). No primeiro grupo, um processo requer a permiss˜ao de todos os outros processos

ou da maioria deles para entrar em sua se¸c˜ao cr´ıtica. No segundo grupo, um ´unico token

´e compartilhado pelos processos e a posse dele garante o direito de entrar em sua se¸c˜ao

cr´ıtica. Algoritmos baseados em token, em sua maioria, consideram uma estrutura l´ogica

dinˆamica na forma de ´arvore, tornando-os adequados para ambientes hier´arquicos, tais

como Grids. Al´em disso, a maioria desses algoritmos apresenta uma m´edia mais baixa de

tr´afego de mensagens considerando o n´umero de processos quando comparado ao modelo

baseado em permiss˜ao, que apresenta problemas de escalabilidade.

Grids s˜ao ambientes computacionais que possuem uma grande quantidade de n´os es-

palhados sobre uma ampla ´area geogr´aﬁca. Normalment e, uma Grid ´e composta por

uma cole¸c˜a o de clusters, onde os n´os s˜ao conectados atrav´es de enlaces dedicados de alta

velocidade. A comunica¸c˜ao entre n´os de clusters distintos ´e feita por canais WANs, que

geralmente s˜ao muito mais lentos. Assim, para uma sincroniza¸c˜ao de recursos em larga

escala, ´e necess´ario levar em conta ta l topologia hier´arquica [8]. Nesse t r abalho, conside-

ramos a topologia hier´arquica como uma forma de organiza¸c˜ao e divis˜ao dos processos em

1 Introdu¸c˜ao 2

dom´ınios diferentes, com diferentes latˆencias nos canais de comunica¸c˜ao. A Figura 1.1 d´a

uma vis˜ao abstrata de um ambiente Grid tal como foi tratada nesse t rabalho.

Nesta disserta¸c˜ao de mestrado ´e pro posto um algoritmo distribu´ıdo baseado em token

para resolver o problema da aloca¸c˜ao de M recursos, considerando uma topologia t´ıpica

existente em ambientes de Grid. Considere que R = (r

, k

), (r

, k

), . . . , (r

, k

) seja

o conjunto de recursos, tal que para cada r ecurso r

exitam k

instˆancias dele, que s˜ao

compartilhadas pelo conjunto de processos P = P

, P

, . . . , P

. Antes de entrar em uma

se¸c˜a o cr´ıtica, um processo P

solicita um subconjunto de recursos existentes. P

n˜ao pode

continuar sua execu¸c˜ao sem a ntes obter todos os recursos que ele requisitou, evitando com

isso, o problema de deadlock. Na sa´ıda da se¸c˜ao cr´ıtica, esses recursos s˜ao liberados para

outros processos.

Figura 1.1: Arquitetura Grid

Diversos algoritmos baseados em token tˆem sido propostos par a resolver o problema

de exclus˜ao m´utua em ambientes distribu´ıdos. Alguns deles consideram uma topologia

hier´arquica que re´une n´os em grup os. Por exemplo, em [26] e [14] ´e apresentado uma

estrat´egia baseada em grupos priorizados, onde n´os com a mesma prioridade s˜ao r eunidos

em um mesmo grupo. Ambos os trabalhos prop˜oem um modelo h´ıbrido, onde o algoritmo

que ´e executado dentro do grupo ´e diferente do algoritmo executado entre os grup os. Em

[19], ´e proposto um algoritmo baseado em an´eis de clusters, onde cada n´o em um anel

representa um cluster de n´os. Apesar de terem uma abordagem hier´arquica, esses algorit-

mos n˜ao consideram diferentes latˆencias na comunica¸c˜ao entre n´os distantes. Em [8], os

autores apresentam um algoritmo baseado em token, inspirados no trabalho proposto por

Naimi e Trehel [38]. O algoritmo propo sto por estes autores considera diferentes latˆencias

na comunica¸c˜ao entre sites distintos. No entanto, este trabalho ´e limitado a somente a um

´unico recurso compartilhado. Nosso algoritmo usa algumas das estrat´egias hier´arquicas

propostas por Bertier et al. [8]. Al´em disso, nosso algoritmo ´e estendido para resolver o

1.1 Organiza¸c˜ao da Disserta¸c˜ao 3

problema do compartilhamento de m´ultiplos recursos com m´ultiplas instˆancias cada.

E t´ıpico em Grids, existir v´arios tipos de recursos compartilhados, incluindo hardware

tais como CPU, espa¸co em disco, canais de comunica¸c˜ao, e software t ais como progra-

mas, arquivos e dados. Veja em [12] e [23] exemplos detalhados de compartilhamento de

software e hardware em Grids. Neste cen´ario, Maddi [33] apresenta algoritmos baseados

no trabalho introduzido por Raynal [46], que considera a multiplicidade de recursos, mas

apresenta baixo desempenho em um ambiente de larga escala composto por muitos n´os.

Em [9] tamb´em ´e proposto um algoritmo distribu´ıdo para o problema de aloca¸c˜ao dinˆamica

de recursos, por´em, este n˜a o considera a disparidade de latˆencia entre os n´os espalhados

no sistema. No sso algoritmo proposto tamb´em emprega alguns conceitos introduzidos por

Bouabdallah e Laforest [9].

Comparamos o algoritmo proposto com o algoritmo baseado em token, introduzido

por [9], que ´e um algoritmo bastante conhecido para resolver o problema de aloca¸c˜ao de

M recursos, mas que n˜ao considera particularidades de ambientes Grids.

O restante deste trabalho est´a organizado como segue. No Cap´ıtulo 2 apresentamos os

trabalhos relacionados com o problema e os algoritmos propostos que foram utilizados

como base para esta pesquisa. No Cap´ıtulo 3 descrevemos o algoritmo prop osto. No

Cap´ıtulo 4 apresentamos a maneira empregada de medir o desempenho do algoritmo,

utilizando rel´ogio l´o gico. Os resultados experimentais s˜ao apresentados no Cap´ıtulo 5.

Finalmente, no Cap´ıtulo 6 conclu´ımos o trabalho.

O problema da exclus˜ao m´utua ´e um problema utilizado na resolu¸c˜ao de conﬂitos no

acesso aos recursos compartilhados.

E considerado um problema fundamental em Ciˆencia

da Computa¸c˜ao e tem sido amplamente estudado durante muito tempo.

Em sistemas distribu´ıdos, v´arios processos executam seus jobs comunicando-se com

outros processos. Quando estes processos compartilham recursos, eles podem eventual-

mente requerer acesso a determinados recursos ao mesmo tempo. Caso esses recursos

precisem ser acessados de forma mutuamente exclusiva, ´e necess´ario que haja uma ordem

de acesso a eles, pois somente um processo pode executar sua se¸c˜ao cr´ıtica usando os

recursos alocados por vez [28].

Normalmente, sistemas distribu´ıdos podem possuir uma grande quantidade de re-

cursos distint os e disp ersos pelos n´os. Al´em disso, muitos usu´a rio s e aplica¸c˜oes podem

precisar ter acesso a esses recursos em um mesmo tempo. Por esta raz˜ao, ´e necess´ario

que os processos de diferentes n´o s cooperem entre si e se organizem para que eles pos-

sam acessar esses recursos de forma justa e consistente, evitando assim problemas como

starvation e deadlock [49].

Diversos tr abalhos que tratam do problema da exclus˜ao m´utua em sistemas distribu´ı-

dos foram propostos na literatura. Muitos destes trabalhos utilizam diferentes t´ecnicas

para resolver o problema, al´em disso, algumas va ria¸c˜oes do problema tamb´em foram pro-

postas. Grande parte dos algoritmos propostos na literatura se limita a uma varia¸c˜ao do

problema onde apenas uma ´unica instˆancia de recurso ´e compartilhada pelos processos, e

2.2 Classiﬁca¸c˜ao dos Algoritmos Distribu´ıdos para Exclus˜ao M´utua 5

somente um processo pode acess´a-la por vez, por exemplo, [48, 38, 61]. Por´em, existem

casos onde mais de um recurso existe no sistema distribu´ıdo. Assim, alguns trabalhos

consideram a existˆencia de k c´opias idˆenticas de um ´unico recurso compartilhado. Isto

permite que um n´umero limitado de processos executem suas se¸c˜oes cr´ıticas simultane-

amente, cada um com uma ´unica instˆancia de cada recurso. Esse problema ´e conhecido

como k-mutual ex c l usion, k-mutex ou ent˜ao m´ultiplas entradas `a se¸c˜ao cr´ıtica. Alguns

exemplos podem ser vistos em [44, 36, 60, 56, 10].

Considerando a multiplicidade e a diversidade de recursos, uma outra varia¸c˜ao desse

problema, deﬁnida como k-out of -M recursos, permite que um processo solicite um n´u-

mero k de c´opias tendo M r ecursos idˆenticos dispon´ıveis, onde 1 ≤ k ≤ M. Este problema

foi resolvido por [46] e [33]. Por ﬁm, uma vers˜ao generalizada do problema consiste do

compartilhamento de m´ultiplos recursos com m´ultiplas instˆancias cada recurso, isto ´e, um

conjunto de recursos R = (r

, k

), (r

, k

), . . . , (r

, k

), tal que para cada tipo de recurso

existam k

instˆancias equivalentes. Em qualquer momento um processo pode necessi-

tar de v´arias instˆancias de diferentes tipos de recursos para entrar em sua se¸c˜ao cr´ıtica

[46, 33, 9].

Na se¸c˜ao seguinte ´e descrita uma classiﬁca¸c˜ao b´asica utilizada pela maioria dos autores

na literatura.

Os algoritmos para exclus˜ao m´utua dispon´ıveis na literatura, basicamente, podem ser di-

vididos em duas principais classes: baseados em token e baseados em permiss˜ao (segundo

[47]) ou n˜ao-baseados em token (segundo [52]). Ainda segundo [52], estes algoritmos

tamb´em podem ser est´aticos ou dinˆamicos. Algoritmos s˜ao est´aticos quando n˜ao armaze-

nam informa¸c˜ao sobre o estado atual do sistema e nem do hist´orico de execu¸c˜ao da se¸c˜ao

cr´ıtica, por outro lado, algoritmos dinˆamicos podem tomar certas decis˜oes com base na

informa¸c˜ao coletada ao longo de sua execu¸c˜ao.

Diversos algoritmos propo stos focam no aumento de desempenho, de acordo com uma

certa m´etrica de desempenho, como por exemplo tempo de respo sta e n´umero de men-

sagens trocadas. Baseado na t´ecnica utilizada, estes algoritmos podem ser classiﬁcados

diferentemente. Na Figura 2.1, ´e mostrada uma classiﬁca¸c˜ao mais ampla dos algorit-

mos distribu´ıdos para exclus˜ao m´utua desenvolvidos nas ´ultimas d´ecadas. Essa ﬁgura foi

2.2 Classiﬁca¸c˜ao dos Algoritmos Distribu´ıdos para Exclus˜ao M´utua 6

extra´ıda e remontada a partir dos trabalhos de [49, 52, 13].

Algoritmos Distribuídos para Exclusão Mútua

Algoritmos Baseados em Token Algoritmos Híbridos Algoritmos Baseados em Permissão

Baseados em Broadcast Baseados em Estruturas Lógicas

(grafo, árvore, anel)

Baseados em Votos Baseados em Coterie

Estáticos Dinâmicos Estáticos DinâmicosEstáticos DinâmicosEstáticos Dinâmicos

Figura 2.1:

Arvore de classiﬁca¸c˜ao dos algoritmos distribu´ıdos para exclus˜ao m´utua [52,

13]

Em algoritmos baseados em permiss˜ao, geralmente s˜ao necess´arias sucessiva s trocas de

mensagens entre os processos para obter a permiss˜ao de executar a se¸c˜ao critica. Quando

um processo necessita executar sua se¸c˜ao cr´ıtica, ele envia requisi¸c˜oes pedindo permiss˜ao

a todos os outros processos. O processo que recebe essa mensagem, caso n˜ao tenha

interesse na se¸c˜ao cr´ıtica, concede sua permiss˜ao. Caso contr´ario , a decis˜ao ´e obtida

em favor do processo de maior prioridade, sendo esta feita utilizando o timestamp local

deste processo. Existem muitos trabalhos na literatura que prop˜oem resolver o problema

da exclus˜ao m´utua usando o modelo baseado em permiss˜ao, alguns exemplos podem ser

vistos em [48, 46, 29, 43].

Basicamente algoritmos baseados em permiss˜ao podem ser divididos em duas subca-

tegorias, baseados em votos e baseados em coterie.

O modelo baseado em votos consiste de um sistema de vota¸c˜ao, onde cada processo tem

direito a um voto (n˜ao negativo). Um processo recebe permiss˜ao para acesso `a se¸c˜ao

cr´ıtica, se ele obtiver no m´ınimo a maioria dos votos do total de votos realizados no

sistema. Alguns algoritmos que utilizam esta t´ecnica podem ser vistos em [58, 2 2, 4].

2.2 Classiﬁca¸c˜ao dos Algoritmos Distribu´ıdos para Exclus˜ao M´utua 7

Nos algoritmos baseados em coterie como em [48], [34] e [41], utiliza-se o conceito de uma

coterie, que seria uma cole¸c˜ao de conjuntos de processos do sistema. Para a obten¸c˜ao

do acesso `a se¸c˜ao cr´ıtica, um processo necessita de permiss˜ao de cada processo de um

conjunto pertencente a uma coterie.

Al´em dessa classiﬁca¸c˜ao, cada uma dessas duas categorias tamb´em pode ser dividida

nos modelos est´aticos (tais como [58, 22, 21, 48, 34]) e dinˆamicos (tais como [5, 2 7, 51]).

Um estudo mais a pro fundado sobre algoritmos baseados em permiss˜ao pode ser en-

contrado em [49] e [13].

Para se conseguir exclus˜ao m´utua, algoritmos baseados em token utilizam uma mensagem

chamada de token, a qual ´e compartilhada pelos n´os. Um n´o s´o pode entrar em sua se¸c˜ao

cr´ıtica ap´os obter a posse do token que est´a relacionado ao recurso que ele necessita.

Como o token ´e ´unico, a exclus˜ao m´utua ´e ent˜ao garantida.

Algoritmos baseados em token podem ainda ser classiﬁcados em baseados em broad-

casts ou baseados em estruturas l´ogicas, como ´arvores, grafos e an´eis. Esses alg oritmos

tamb´em podem ser est´aticos ou dinˆamicos [13, 52].

Em algoritmos baseados em broadcast, nenhuma estrutura ´e imposta nos n´os e um n´o

envia mensagens requisitando o token para outros n´os em paralelo [52]. Os algoritmos

est´aticos s˜ao caracterizados por n˜ao possu´ırem mem´oria a respeito de execu¸c˜oes na se¸c˜ao

cr´ıtica. Nesses algoritmos, um pedido de token ´e enviado pa ra todos o s n´os do sistema

distribu´ıdo. Alguns exemplos podem ser vistos em [42, 57]. Por outro lado, algoritmos

dinˆamicos como [50] e [61], s˜ao capazes de se lembrar do hist´orico da localiza¸c˜ao do token e

enviam mensagens pedindo token somente para n´os dinamicamente selecionados, os quais

provavelmente estar˜ao com o token.

Em rela¸c˜ao a desempenho, algoritmos baseados em broadcast geralmente possuem

um alto tr´afego de mensagens. Algoritmos est´aticos requerem N mensagens por cada

execu¸c˜ao `a se¸c˜ao cr´ıtica [57], enquanto algoritmos dinˆamicos r equerem N/2 em baixa

carga, chegando a N em alta carga, de acordo com [50].

2.2 Classiﬁca¸c˜ao dos Algoritmos Distribu´ıdos para Exclus˜ao M´utua 8

Em alg oritmos baseados em estruturas l´o gicas, n´os s˜ao organizados em uma conﬁgura¸c˜ao

l´ogica [52]. Essas estruturas basicamente podem ser baseadas em ´arvore, grafo ou em

anel. Estes algoritmos tamb´em podem ser est´aticos ou dinˆamicos.

Em algoritmos baseados em ´arvore, n´os normalmente s˜ao

organizados de forma que os pedidos sejam propagados seq

uencialmente atrav´es dos ca-

minhos entre o n´o que requisita e o n´o que mant´em o token, e da mesma forma tamb´em

para a passagem do token solicitado.

Nos algoritmos est´aticos ba seados em ´arvore [45, 40], a estrutura l´ogica se mant´em

imut´avel e somente a dire¸c˜a o das arestas ´e modiﬁcada durante a passagem dos pedidos

de token pelos caminhos que interligam os n´os at´e a raiz da ´arvore.

Os algoritmos dinˆamicos como, por exemplo, [37], [16] e [38], mant´em-se uma ´arvore

dinˆamica, tal que a raiz dessa ´arvore ´e sempre o ´ultimo n´o a obter o token dentre os pedidos

correntes f eitos por todos os n´os. A estrutura da ´arvor e ´e modiﬁcada dinamicamente `a

medida que uma requisi¸c˜a o de token ´e enviada pelos n´os da ´arvore at´e a raiz. Cada n´o

intermedi´ario po r onde o pedido foi passado, passa a considerar o n´o r equisitante como

um n´o “pai” ou o n´o “prov´avel dono do token”, exceto quando o n´o intermedi´ar io ´e a raiz

da ´arvore. Neste caso, o n´o r equisitant e se torna a nova raiz dessa ´arvore e os pedidos

posteriores s˜ao enviados at´e ele. Quando um pedido chega at´e o n´o raiz, este envia o token

diretamente ao pr´oximo n´o que requisitou para executar sua se¸c˜a o cr´ıtica.

Algoritmos baseados em ´arvores e em grafos geram um baixo tr´afego de mensagens.

Uma estudo extensivo de medi¸c˜ao feito por Raymond [45], mostrou que a constru¸c˜ao

randˆomica de uma ´arvore composta de N n´os, tipicamente possui uma complexidade

m´edia de O(log(N)). Al´em disso, a caracter´ıstica dinˆamica da estrutura l´ogica baseada

em ´arvore, que possibilita que ela seja modiﬁcada em temp o de execu¸c˜ao e o baixo consumo

de mensagens, permitem conseguir grandes vantagens no uso de estrat´egias esp ec´ıﬁcas de

ambientes com diferentes conﬁgura¸c˜oes, tais como ambientes com topologias hier´arquicas

[8].

Nas estruturas baseadas em grafos, n´os s˜ao estruturados na

forma de um grafo direcionado com um sumidouro (sink ) o qual mant´em o token. As

requisi¸c˜oes e a propaga ¸c˜ao do token s˜ao manipuladas da mesma forma que nos algoritmos

2.3 Solu¸c˜oes Existentes para Ambientes Hier´arquicos e de Grids 9

baseados em ´arvore, com a vantagem de serem tolerantes a falhas devido aos m´ultiplos

caminhos entre os n´os, enquanto na ´arvore n˜ao. No entanto, esta estrutura por ser tole-

rante a falhas possui um alto custo de mensagens que s˜ao usadas para prevenir os ciclos

na estrutura do grafo. Veja [15, 24, 59] para mais detalhes.

Em uma estrutura l´ogica usando anel, os n´os s˜ao arranjados

na forma de um anel l´ogico, onde o token circula pelo anel em uma dire¸c˜ao ﬁxa atrav´es

de mensagens ponto a ponto. Nenhum pedido expl´ıcito ´e necess´ario, um n´o que queira

acessar sua se¸c˜ao cr´ıtica precisa apenas aguardar que o token chegue at´e ele. Ao sair da

se¸c˜a o cr´ıtica, o n´o redireciona o token ao seu sucessor no anel. Exemplos de algoritmos

baseados em an´eis podem ser vistos em [3 1], [11] e [33].

Embora v´arios algoritmos distribu´ıdos para exclus˜ao m´utua tenham sido propostos para

minimizar tanto o tr´afego de mensagens quanto o atraso de tempo, nenhum deles pode mi-

nimizar ambos ao mesmo tempo [52, 13]. Por exemplo, o algoritmo de Maekawa [34] reduz

o tr´afego de mensagens para O(

√

N); por´em, possui um grande atraso de tempo em suces-

sivas execu¸c˜oes na se¸c˜ao cr´ıtica quando comparado ao algoritmo de Ricart-Agrawala [48]

que possui O(N) [13]. Nesse contexto, alguns a uto r es propuseram uma estrat´egia h´ıbrida

utilizando diferentes tipos de algoritmos, baseados em token e baseados em permiss˜ao.

Os algoritmos h´ıbridos pa ra exclus˜a o m´utua tˆem sido utilizados no int uito de minimizar

ambo s, o atraso de tempo e a complexidade de mensagem [14]. Alguns exemplos podem

ser encontrados em [14] [26].

Ambientes hier´arquicos, tais como Grids, geralmente s˜ao compostos por diversos pro-

cessos agrupados em clusters, e que s˜ao dispersos geograﬁcamente. Tais clusters s˜ao

interconectados por canais remotos de comunica¸c˜a o, que geralmente s˜ao mais lento s do

que a comunica¸c˜ao local feita por processos dentro de cada cluster.

Neste cen´ario hier´arquico, Housni et al. [26] e Chang et al. [14] propuseram solu¸c˜oes

utilizando o conceito de grupos priorizados, onde os processos, seguindo algum crit´erio,

s˜ao arranjados em grupos. Assim, ´e poss´ıvel priorizar a comunica¸c˜ao local com rela¸c˜ao

2.4 Solu¸c˜oes Relacionadas `a Proposta 10

`a comunica¸c˜ao global. Al´em disso, eles tamb´em utilizam a estrat´egia de algoritmos h´ı-

bridos, onde o algoritmo de exclus˜ao m´utua executado dentro do grupo ´e diferente do

algoritmo executado ent r e os grupos. Apesar de possu´ırem uma abordagem semelhante-

mente hier´arquica, estes trabalhos s˜ao limitados, pois compartilham apenas uma ´unica

instˆancia de recurso. Al´em disso, a estrat´egia hier´arquica proposta nesses trabalhos ainda

n˜ao ´e adequada, pois a maior latˆencia nos canais de comunica¸c˜ao que interconectam os

n´os distantes n˜ao ´e levada em conta. Outra proposta semelhante a estas, ´e feita por Er-

ciyes [19]. O autor utiliza um modelo baseado em an´eis de clusters, onde cada n´o de um

anel representa um cluster de n´os. Assim como no caso anterior, esta proposta tamb´em

n˜ao considera m´ultiplos recursos, e tamb´em n˜ao considera a maior latˆencia nos canais de

comunica¸c˜ao que interlingam os n´os remotos.

Em Bertier et al. [8], os autores apresentam um algoritmo baseado em token, inspira-

dos no trabalho proposto por Naimi e Tr ehel [38]. O algoritmo proposto por estes autores

considera a diferen¸ca de latˆencias na comunica¸c˜ao entre n´os distintos e apresenta estrat´e-

gias para otimizar a troca de mensagens e a passagem do token pelo sistema considerando

a hierarquia. No entant o, este trabalho ´e limitado a somente um recurso compartilhado.

Este trabalho esta melhor discutido na Subse¸c˜ao 2.4.1.1 .

Mais recentemente, em Sopena et al. [55], os autores propuseram um mecanismo que

considera a heterogeneidade da latˆencia na comunica¸c˜a o em ambientes de Grid. Este

algoritmo permite a execu¸c˜ao de algoritmos de exclus˜ao m´utua diferentes, tanto entre

processos dentro do cluster quanto entre os clusters. Esta estrat´egia permite avaliar o

comportamento de diferentes composi¸c˜oes de algor itmos. Por´em, este trabalho tamb´em

n˜ao leva em considera¸c˜ao a existˆencia dos m´ultiplos recursos de ambientes de Grid.

Nesta se¸c˜ao s˜ao descritos separadamente alguns do s principais tr abalhos que nortearam

a constru¸c˜ao do algoritmo proposto. Inicialmente, s˜ao descritas as solu¸c˜oes hier´arquicas

propostas pelo trabalho de [7, 8], bem como, as solu¸c˜oes que contemplam o problema

da exclus˜ao m´utua para m´ultiplos recursos [9], os quais inspiraram o desenvolvimento do

algoritmo proposto.

2.4 Solu¸c˜oes Relacionadas `a Proposta 11

Bertier et al.

Bertier et al. [7, 8] apresentaram a dapta ¸c˜oes do algoritmo baseado em token proposto

por Naimi e Tr ehel [38] e [36], explorando a topologia hier´arquica de Grid. Assim como

no t r abalho de Naimi-Trehel, no algoritmo proposto em Bertier et al. [8] os autores tam-

b´em consideram um ambiente onde exista apenas um recurso compartilhado, sendo este

representado por um token.

A estrutura l´og ica dinˆa mica herdada de Naimi e Trehel consiste de uma ´arvore com-

posta pelos processos do sistema. Esta estrutura l´o gica e dinˆamica da ´arvore faz com

que o processo que est´a na raiz seja sempre o ´ultimo a receber o token pelas requisi¸c˜oes

correntes.

Por serem estruturas ﬂex´ıveis, podendo ser modiﬁcadas dinamicamente durante a

execu¸c˜ao, e por possu´ırem um menor tr´afego de mensagens comparado a mecanismos

como o de broadcast, as estruturas baseadas em ´arvores escalam melhor, portanto s˜ao

mais adequadas para aplica¸c˜oes em Grid.

Os algoritmos adaptados pelos autores levam em considera¸c˜ao algumas caracter´ısticas

importantes encontradas em Grids, como por exemplo, as diferen¸cas de latˆencias nos

canais que interligam processos de diferentes clusters.

Em seu trabalho, Bertier et al. propuseram algumas vers˜oes do a lg oritmo de Naimi-

Trehel. Em uma delas ´e explorada a localidade dos processos, priorizando pedidos de

tokens feitos dentro do cluster, localmente, em rela¸c˜ao aos pedidos feitos por processos de

clusters remotos. Esse procedimento garante uma melhor utiliza¸c˜ao dos canais remotos,

evitando o uso arbitr´ario desses canais.

Os autores tamb´em modiﬁcaram a forma de inicializa¸c˜ao do algoritmo original de

Naimi-Trehel, fazendo com que os processos inicialmente apontassem para um processo

l´ıder em cada cluster. Assim, no in´ıcio da execu¸c˜ao do algoritmo, os pedidos de recursos

s˜ao direcionados a esses l´ıderes. Desta forma, consegue-se um balanceamento do tr´afego

de mensagens iniciais, pois ao inv´es de todos os processos do sistema enviarem pedidos `a

apenas um processo, eles enviam esses pedidos ao s l´ıderes de seus c l usters.

2.4 Solu¸c˜oes Relacionadas `a Proposta 12

Bouabdallah e Laforest

O problema da aloca¸c˜ao de m´ultiplos recursos aparece quando um processo necessita de

executar sua se¸c˜ao cr´ıtica n˜ao apenas com um ´unico recurso, e sim com um subconjunto

qualquer de recursos distinto s dispon´ıveis. Neste contexto, Bouabdallah e Laforest [9]

propuseram um algor itmo distribu´ıdo baseado em token para aloca¸c˜ao de m´ultiplos re-

cursos. Neste trabalho, os autor es consideram um ambiente onde n˜ao exista diferen¸ca

de latˆencias entre os canais de comunica¸c˜ao do sistema distribu´ıdo, tratando todos os

processos igualmente no sistema. O algoritmo t amb´em utiliza uma estrutura l´ogica de

´arvor e, baseada no algoritmo proposto por Naimi e Trehel [38] e [36], o que permitiu uma

melhor integra¸c˜ao da s estrat´egias utilizadas no algo ritmo proposto.

Uma caracter´ıstica que o diferencia da maioria das propostas ´e a capacidade de alo-

car v´arios recursos simultaneamente, respeitando o acesso exclusivo. Cada instˆancia de

recurso dispon´ıvel no sistema ´e associada a um token. Para que um processo tenha acesso

a sua se¸c˜ao cr´ıtica, ele precisa possuir todos os tokens associados aos recursos que ele

necessita. Para evitar que processos busquem pelos toke ns individualmente, os autores

propuseram uma estrutura l´ogica, denominada de Control Token (CT).

O Control Token exerce o papel de um token centralizador que concede acesso `a

se¸c˜a o cr´ıtica para quem o possuir. Al´em disso, o CT tamb´em armazena informa¸c˜oes a

respeito de cada token no sistema, essas informa¸c˜oes p ermitem saber quais tokens est˜ao

dispon´ıveis, e para o caso de estarem ocupados, permite saber quem ´e o processo prov´avel

dono daquele token.

Diferentemente da proposta de Naimi e Trehel, onde apenas um token ´e trocado entre

os processos, em Bouabdallah e Laforest a estrutura do CT ´e trocada entre os processos.

Somente um processo pode obter o CT de cada vez. Isso implica que somente um processo

pode ler e escrever na estrutura l´ogica naquele tempo, garantindo assim a exclus˜ao m´utua.

Um processo deve solicitar a posse do CT para que ele tenha acesso `as informa¸c˜oes a

respeito dos tokens e possa enviar pedidos aos processos respectivos que possuem ou ir˜ao

possuir cada token que ele necessita.

Os autores Bouabdallah e Laforest tamb´em idealizaram uma generaliza¸c˜ao do algo-

ritmo, no qual considera n˜ao somente o compartilhamento de m´ultiplos recursos, mas

tamb´em m´ultiplas instˆancias para cada tipo de recurso. Esta generaliza¸c˜ao foi implemen-

tada para esta disserta¸c˜ao de mestrado e foi utilizada como base de compara¸c˜ao com o

2.5 Solu¸c˜oes Recentes 13

algoritmo proposto.

Al´em dos trabalhos que utilizam o conceito de algoritmos h´ıbridos para exclus˜ao m´utua

e algoritmos que consideram as diferen¸cas de latˆencias nos canais de comunica¸c˜ao, ou

ainda, algoritmos que consideram a multiplicidade de recursos, existem tamb´em alguns

trabalhos que focam em um conceito a inda n˜ao suportado pelo algoritmo proposto, que

´e a tolerˆancia a falhas. Neste cen´ario, alguns trabalhos podem ser citados p or possu´ırem

um alto grau de relevˆancia e proximidade `a proposta deste trabalho, como um pr´oximo

passo a ser desenvolvido, como po r exemplo [3, 5 4, 53].

O ambiente distribu´ıdo considerado nesta proposta consiste de n processos com um iden-

tiﬁcador ´unico cada, que se comunicam de forma ass´ıncrona por troca de mensagens.

Mensagens s˜ao entregues em um tempo ﬁnito, por´em imprevis´ıvel. Assume-se tamb´em

que falhas n˜ao ocorrem.

O algo r itmo proposto utiliza o modelo baseado em token, onde cada token representa

uma instˆancia de recurso dispon´ıvel no sistema. Uma condi¸c˜ao necess´aria para um pro-

cesso entrar em sua se¸c˜ao cr´ıtica (SC) ´e possuir todos os tokens referentes aos recursos

dos quais ele necessita. O tempo de execu¸c˜ao de cada se¸c˜ao cr´ıtica ´e ﬁnito, po r´em n˜ao

limitado.

A solu¸c˜ao para este problema precisa garantir a propriedade de exclus˜ao m´utua, ou

seja, uma instˆancia de recurso pode somente ser utilizada por no m´aximo um processo

por vez.

E necess´ario tamb´em garantir que n˜ao ocorra o problema de starvation, qualquer

processo que solicitar recursos ir´a obtˆe- lo s em um tempo ﬁnito. Al´em disso, deve se

garantir a ausˆencia de deadl ocks.

Considerando o problema da aloca¸c˜ao de m´ultiplos recursos, o algoritmo proposto ´e

baseado n˜ao somente em tokens que garantem acessos aos recursos, mas tamb´em em uma

estrutura ´unica denominada de Control Token (CT) que ordena os acessos aos recursos.

Essa estrutura foi originalmente propo sta por [9], no ent anto foi adaptada neste trabalho

considerando seu uso em ambientes hier´arquicos, tais como Grid. O CT ´e uma estrutura

l´ogica que mant´em os tokens livres e tamb´em uma vis˜a o para cada token n˜ao livre, do

3.1 Introdu¸c˜ao 15

processo que o possui ou que ir´a possu´ı-lo em um tempo ﬁnito. Um ´unico processo por

vez mant´em o Control Token que consiste de:

• um conjunto A de tokens livres;

• uma lista B de processos, cada um com o conjunto de tokens que ele possui ou

possuir´a;

• uma lista C de recursos, cada um com um processo que possui prioridade de acesso a

esse recurso e um valor associado, representando sua freq

uˆencia de uso pelo processo.

Quando um processo receb e o CT, ele pega todo s os tokens que ele necessita no

conjunto A, adiciona em A os tokens desnecess´arios que ele possui e atualiza a lista B

indicando que ele po ssui ou possuir´a to dos os tokens que ele pegou. Esta ´ultima a¸c˜ao

causa o envio de requisi¸c˜oes de recursos aos pro cessos que os possuem. A lista C ´e usada

para escolher os processos mais apropriados da lista B para enviar tais requisi¸c˜oes. Ao

receber todas as respostas correspo ndentes, o CT pode ent˜ao ser liberado para um pr´oximo

processo.

Este algoritmo tem como objetivo a redu¸c˜ao de mensagens entre clusters diferentes e

na m´edia do tempo esperado na obten¸c˜ao dos recursos. Para reduzir mensagens remotas,

um processo l´ıder ´e eleito em cada cluster para que concentre os pedidos iniciais de CT,

que eventualmente pode estar em outro cluster. Al´em disso, os pedidos locais de CT, ou

seja, pedidos feitos por processos que est˜ao no mesmo cluster, s˜ao priorizados.

Em rela¸c˜ao aos tokens que representa m as instˆancias de recursos, o algoritmo tamb´em

prioriza sua transmiss˜ao aos processos de um mesmo cluster, o que permite ter uma maior

concentra¸c˜ao de mensagens locais, reduzindo assim, a troca de mensagens remotas.

deﬁnido tamb´em, um mecanismo de prioridades para processos em cada recurso. Assim,

pedidos de recursos s˜ao redirecionados aos processos que os utilizam com menos freq

uˆencia.

O algoritmo satisfaz o requisito de exclus˜ao m´utua, visto que um ´unico token ´e as-

sociado a uma ´unica instˆancia de recurso e somente um processo pode o btˆe-lo a cada

momento. Ele tamb´em ´e livre de starvation, pois cada processo ap´os realizar um pedido

de CT ir´a recebˆe-lo em um espa¸co ﬁnito de tempo e, tamb´em, porque cada pro cesso que

necessite dos tokens para executar sua se¸c˜ao cr´ıtica ir´a obtˆe-los tamb´em em um tempo

ﬁnito. As t´ecnicas utilizadas no a lgoritmo proposto for am inspiradas nos algoritmos de

[9] e [8] e suas an´alises, tamb´em, s˜ao v´alidas para essa proposta.

As se¸c˜oes seguintes descrevem estes procedimentos em detalhes.

3.2 Descri¸c˜ao do algoritmo 16

A estrutura l´ogica de ´arvore utilizada ´e baseada em um modelo proposto por [38], a qual

´e constru´ıda de forma em que cada processo no sistema, exceto aquele que possui o CT,

aponte para um processo que de seu conhecimento possui ou po ssuir´a o CT, veja um

exemplo na Figura 3.1. Essa informa¸c˜ao ´e armazenada em uma vari´avel “owner”, que ´e

atualizada dinamicamente todas as vezes que um processo recebe uma requisi¸c˜ao pedindo

o CT. Em cada momento, o ´ultimo processo a pedir o CT ´e sempre a raiz da ´arvore

l´ogica, e quando isso acontece o conte´udo de sua vari´avel owner recebe vazio. Quando o

pedido de um processo chega at´e o processo raiz da ´arvore, ele ´e adicionado em uma ﬁla

distribu´ıda deﬁnida pela vari´avel “next”, que mant´em a ordem na qual o CT ser´a passado

pelos processos que o solicitaram. Os elementos ilustrados na Figura 3.1 s˜ao detalhados

na Subse¸c˜ao 3.2.1.

Figura 3.1: Conﬁgura¸c˜ao l´ogica de ´arvor e tradicional, segundo [38].

Baseado na id´eia proposta por [8], foi feita uma modiﬁca¸c˜ao na conﬁgura¸c˜ao inicial desta

´arvor e como pode ser visto na F igura 3.2. A ﬁgura representa um ambiente hier´arquico

composto por dois clusters, cluster A e cluster B, onde P

, P

e L

pertencem ao

cluster A e P

, P

e L

pertencem ao cluster B.

Figura 3.2: Conﬁgura¸c˜ao l´ogica de uma ´arvore com hierarquia

Em cada cluster, um processo ´e escolhido como l´ıder para o qual ´e enviada a primeira

requisi¸c˜ao de CT de cada processo daquele cluster, no exemplo, L

e L

s˜ao o s l´ıderes.

Processos l´ıderes eventualmente ta mb´em acessam suas se¸c˜oes cr´ıticas. A conﬁgura¸c˜ao

dessa estrutura l´ogica inicial visa concentrar as requisi¸c˜oes iniciais localmente nos clusters,

3.2 Descri¸c˜ao do algoritmo 17

evitando o envio de mensagens remotas. Veja tamb´em no Algoritmo 1, o procedimento de

inicializa¸c˜ao do algoritmo e o processo de conﬁgura¸c˜ao inicial da ´arvore. Observe que um

processo ´e eleito como mantenedor inicial do CT, al´em disso, em cada cluster ´e deﬁnido

um processo l´ıder e todos os outros processos apontam par a ele na ´arvore. As vari´aveis

contidas nesse algoritmo s˜ao descritas no decorrer deste cap´ıtulo.

Algoritmo 1 - Inicializa¸c˜ao

1: requesting ← F ALSO

2: next ← 0

3: remote

owner ← 0

4: num preempt ← 0

5: se NO

ELEIT O ∈ P rocesso Locais ent˜ao

6: se self = N O ELEIT O ent˜ao

7: control

token ← V ERDADE

8: owner ← 0

9: sen˜ao

10: control

token ← F ALSO

11: owner ← NO ELEIT O

12: ﬁm se

13: sen˜ao

14: control

token ← F ALSO

15: se self = Lider

ent˜ao

16: owner ← NO

ELEIT O

17: sen˜ao

18: owner ← Lider

19: ﬁm se

20: ﬁm se

O procedimento de obten¸c˜ao do acesso `a se¸c˜ao cr´ıtica se divide em dois passos. Pri-

meiro, ´e necess´ario obter o CT que garante o direito ao acesso exclusivo `a se¸c˜ao cr´ıtica,

al´em de obter as informa¸c˜oes necess´arias para o segundo passo, que ´e obter os tokens

necess´arios. Esses procedimentos e os detalhes do algoritmo proposto s˜ao mostrados se-

paradamente nas subse¸c˜oes seguintes.

Neste est´agio, basicamente s˜ao utilizadas trˆes tipos de mensagens, Requisicao , Control To-

ken e Preempcao, as quais s˜ao tratadas por procedimentos espec´ıﬁcos no processo receptor,

que s˜ao descritos posteriormente nesta subse¸c˜ao.

Cada processo possui uma lista de tokens dispon´ıveis localmente, ou seja, os tokens

que somente este processo mant´em, no momento. Quando um processo P

necessita de

um conjunto de recursos para entrar em sua se¸c˜ao cr´ıtica, ele primeiro veriﬁca se os tokens

correspondentes est˜ao dispon´ıveis localmente. Se sim, ele trava os tokens e executa sua

se¸c˜a o cr´ıtica. Do contr´ario, ele solicita o CT.

3.2 Descri¸c˜ao do algoritmo 18

A estrutura de dados utilizada na implementa¸c˜ao do CT ´e um vetor de k posi¸c˜o es,

onde k ´e o n´umero tota l de tokens que representam as instˆancias dos tipos de recursos

dispon´ıveis no sistema. Nessa estrutura de dados, os ´ındices k representam os tokens e

suas posi¸c˜oes guardam o identiﬁcador do processo que possui `aquele token ou um valor

vazio, indicando que o token est´a livre. Al´em disso, uma lista auxiliar p rioridades, ´e

acoplada `a estrutura de dados para guardar as informa¸c˜oes referentes `as prioridades dos

processos em cada tipo de recurso.

No in´ıcio o Contro l Token ´e a locado para um dos l´ıderes, que ´e deﬁnido pela constante

ELEIT O, e o s pedidos de outros l´ıderes s˜ao redirecionados a ele. Cada l´ıder mant´em

a identiﬁca¸c˜ao do n´o que realizou a ´ultima requisi¸c˜ao local, evitando transmiss˜oes de

mensagens entre clusters. H´a aqui dois casos a serem considerados que comp˜oem os

exemplos a seguir.

Neste primeiro exemplo, considere um cluster A que n˜ao possui o CT e onde um pro-

cesso P

envia uma requisi¸c˜ao de CT para o processo L

. Se um outro processo local P

anteriormente enviou uma requisi¸c˜ao de CT e L

est´a ciente disso, L

ent˜ao redireciona

a requisi¸c˜ao de P

para P

evitando a transmiss˜ao de uma mensagem para um cluster

remoto. Note que a requisi¸c˜ao original de P

fez com que L

redirecionasse aquela men-

sagem para o l´ıder do cluster que possui o CT. Observe a ordem na qual as requisi¸c˜oes

foram enviadas na Figura 3.3. Quando o CT chega ao cluster A, ele segue o caminho

mostrado na Figura 3.4.

Figura 3.3: Requisi¸c˜oes de Contro l Token

Figura 3.4: Caminho 1 do Control Token

Os detalhes do procedimento referente a uma requisi¸c˜ao de CT podem ser vistos no

3.2 Descri¸c˜ao do algoritmo 19

Algoritmo 2. Seguindo o exemplo acima, a requisi¸c˜ao feita pelo processo P

ao processo L

ilustrada na Figura 3.3, foi feita executando o procedimento Requisicao

SC do algoritmo.

Neste procedimento, inicialmente ´e veriﬁcado se o processo est´a requisitando a se¸c˜ao cr´ıtica

e em seguida se ele j´a possui o CT. Caso ele n˜ao o possua, uma mensagem requisitando o

CT ´e enviada a o processo indicado em sua vari´avel local owner , que armazena o prov´avel

dono do CT. Ap´os isso, ele ﬁca em estado de espera aguardando o recebimento do CT.

Note que nesse momento P

se tornou a atual raiz da ´arvore, atualizando sua vari´avel

owner com 0. Da mesma forma, L

ao receber o pedido de P

o indicou em sua vari´avel

owner, com isso, os pr´oximos pedidos de CT devem ser enviados a P

Algoritmo 2 - Requisi¸c˜ao para acesso `a se¸c˜ao cr´ıtica

1: Re qui sicao SC( )

2: requesting ← V ERDADE

3: se control

token = F ALSO ent˜ao

4: Envia Requisicao, S

 para owner

5: owner ← 0

6: Espera receb e r a mensagem ControlT oken

7: ﬁm se

8: { Parte suprimida }

O Algoritmo 3, apresenta uma vers˜ao simpliﬁcada da a¸c˜ao executada no recebimento

de uma requisi¸c˜ao, que no nosso exemplo ´e executada pelo processo local L

. Observe

entre as linhas 2 e 5 que se caso o processo fosse a raiz da ´arvore, ele a modiﬁcaria

indicando P

como a atual raiz, atualizando a vari´avel owner. Al´em disso P

´e adicionado

a uma ﬁla distribu´ıda representada pela vari´avel next, que ordena o recebimento do CT.

Se caso o CT estivesse livre em L

, ele poderia ser enviado imediatamente a P

(linhas 6

a 10). Por´em, de acordo com o exemplo iniciado na Figura 3.3, o trecho descrito entre

as linhas 11 e 14 ´e executado e L

redireciona a requisi¸c˜ao de P

ao processo P

que de

acordo com o conte´udo de owner ´e o pr´oximo a po ssuir o CT.

No segundo caso, tem-se um cen´ario similar, por´em com o CT no cluster A. Considere

agora que L

receba uma requisi¸c˜ao r emota originada do processo P

de um cluster B,

atrav´es do processo L

. Ent˜ao, L

redireciona sua requisi¸c˜a o para o ´ultimo processo do

cluster no qual tenha requisitado o CT, no exemplo (Figura 3.3) P

, mas continua a

considerar P

como o ´ultimo processo a ter requisitado o CT. Ao receber a requisi¸c˜ao de

pedindo o CT, o processo P

considera ele como o pr´oximo a receber o CT.

Por´em, caso o processo P

receba uma requisi¸c˜ao de um processo local P

, ele insere

a requisi¸c˜ao anterior do processo P

em uma ﬁla de processos remotos, priorizando a

3.2 Descri¸c˜ao do algoritmo 20

Algoritmo 3 - Recebe pedido de CT (vers˜ao simpliﬁcada)

1: Re cebe Requisicao(S

2: se owner = 0 ent˜ao

3: se requesting = V ERDADE ent˜ao

4: next ← S

5: owner ← S

6: sen˜ao

7: Envia ControlT oken, CT  para S

8: owner ← S

9: control

token ← F ALSO

10: ﬁm se

11: sen˜ao

12: Envia Requisicao, S

 para owner

13: owner = S

14: ﬁm se

15:

requisi¸c˜ao local de P

. Assim, ele considera P

como o pr´oximo candidato a receber o CT

e em seguida, ent˜ao, envia essa ﬁla para P

, que passa a considerar P

como o pr´oximo

a receber o CT. Essa estrat´egia, a qual denominamos de preemp¸c˜ao foi adotada com o

objetivo de priorizar os atendiment os locais, evitando que o CT ﬁque trafegando entre os

clusters, atrav´es de canais remotos. Observe na Figura 3.5 o caminho a ser seguido pelas

mensagens do CT. Para evitar starvation, ´e utilizado um mecanismo que limita o n´umero

de preemp¸c˜oes realizadas, ou seja, o n´umero de vezes que o envio do CT a um processo

remoto ´e postergado dando lugar a um processo local. Esse valor ´e deﬁnido como um

parˆametro do algoritmo e pode ser conﬁgurado de a cordo com a aplica¸c˜ao.

Figura 3.5: Caminho 2 do Control Token

Para descrever o exemplo de execu¸c˜ao, ´e usada uma vers˜ao estendida da a¸c˜ao Re-

cebe

Requisicao que pode ser vista no Algoritmo 4. As principais modiﬁca¸c˜oes nessa

fun¸c˜ao s˜ao: o procedimento que diferencia processos locais de processos remotos e o pro-

cedimento que realiza preemp¸c˜oes. De acordo com o exemplo, h´a uma ocorrˆencia de uma

requisi¸c˜ao remota originada do processo P

, que primeiramente foi enviada ao processo

l´ıder do cluster B, e ent˜ao redirecionada ao l´ıder do cluster A, no caso L

. Observe

que executando o trecho das linhas 27 a 31 do Algoritmo 4 , L

ao receber uma requisi¸c˜ao

remota, redireciona esta requisi¸c˜ao a P

, e continua mantendo a identiﬁca¸c˜ao de P

sua vari´avel owner. Quando esta mensagem, que foi redirecionada por L

, chega a P

, ele

ent˜ao adiciona P

como o pr´oximo da ﬁla a receber o CT e armazena aquele processo em

3.2 Descri¸c˜ao do algoritmo 21

uma va r i´avel remote owner, indicando que um processo remoto ´e o ´ultimo a obter o CT

at´e o momento. Esse procedimento pode ser visto entre as linhas 4 e 10 do Algoritmo 4.

No entanto, em um outro momento, P

recebe uma requisi¸c˜ao originada de um processo

local P

, atrav´es de um redirecionamento feito por L

. Neste caso, o processo P

ent˜ao

executa o trecho compreendido pelas linhas 11 a 17 do Algoritmo 4, onde P

realiza

uma preemp¸c˜ao, priorizando a r equisi¸c˜ao local de P

, adicionando-o antes de P

. Para

isso, uma mensagem de preemp¸c˜ao ´e enviada ao processo P

, contendo a identiﬁca¸c˜ao

do processo remoto que est´a enﬁleirado e o n´umero total de preemp¸c˜oes r ealizadas. O

n´umero total de preemp¸c˜oes n˜ao deve ultrapassar o limite pr´e-estabelecido pela vari´avel

MAX

P REEMP T , que ´e um parˆametro do algoritmo. Veja na linha 12 do Algoritmo

4 onde ´e feita esta veriﬁca¸c˜ao. Caso este limite seja alcan¸cado, o processo remoto ent˜ao

´e atendido, evitando assim que um processo remoto ﬁque esperando inﬁnitamente, o que

seria um problema de starvation.

Algoritmo 4 - Recebe pedido de CT (vers˜ao estendida)

1: Re cebe Requisicao(S

2: se owner = 0 ent˜ao

3: se requesting = V ERDADE ent˜ao

4: se next = 0 ent˜ao

5: next ← S

6: se S

∈ P rocessos

Locais ent˜ao

7: owner ← S

8: sen˜ao

9: remote

owner ← S

10: ﬁm se

11: sen˜ao

12: se S

∈ P rocessos

Locais e num preempt < MAX P REEM P T ent˜ao

13: num preempt ← num preempt + 1

14: owner ← S

15: Envia P reempcao, num

preempt, next para S

16: next ← S

17: sen˜ao

18: Envia Requisicao, S

 para next

19: owner ← S

20: ﬁm se

21: ﬁm se

22: sen˜ao

23: Envia ControlT oken, CT, num

preempt para S

24: owner ← S

25: control

token ← F ALSO

26: ﬁm se

27: sen˜ao

28: Envia Requisicao, S

 para owner

29: se S

∈ P rocessos

Locais ent˜ao

30: owner = S

31: ﬁm se

32: ﬁm se

O procedimento que trata o recebimento de uma mensagem de preemp¸c˜ao ´e mostrado

3.2 Descri¸c˜ao do algoritmo 22

no Algoritmo 5. No te que, primeiramente, o contador do n´umero de preemp¸c˜oes realizadas

´e atualizado, e logo em seguida ´e propagado (linha 7) at´e chegar ao ´ultimo processo que

recebe o CT localmente (linhas 3 a 5), sendo este o respons´avel por enviar o CT ao

processo remoto em quest˜a o.

Algoritmo 5 - Recebe mensagem de preemp¸c˜ao

1: Re cebe Preempcao(num preempt

, rem ote node):

2: num

preempt ← num preempt + num preempt

3: se next = 0 ent˜ao

4: next ← remote

node

5: remote

owner ← remote node

6: sen˜ao

7: Envia P reempcao, num preempt, remote node para owner

8: ﬁm se

No Algoritmo 6 ´e poss´ıvel ver o procedimento respons´avel pelo evento que trata o

recebimento do C ontrol Token. Al´em da estrutura do CT que ´e passada na mensagem, ´e

enviado tamb´em o n´umero total de preemp¸c˜oes realizadas at´e o momento, para que este

processo atualize seu cont ador local.

Algoritmo 6 - Recebe control token

1: Re cebe ControlToken(CT

, num preempt

2: num preempt ← num preempt + num preempt

3: CT ← CT

4: control

token ← V ERDADE

Note que `a medida que o algoritmo progride, as pr´oximas requisi¸c˜oes de CT de cada

processo s˜ao enviadas ao processo que de seu conhecimento ´e o prov´avel dono do CT. Em

ambo s os casos previamente descritos, uma pr´oxima r equisi¸c˜ao de P

iria ser enviada a

. Mais detalhes deste procedimento podem ser encontrados em [8].

Durante a execu¸c˜ao do algoritmo, um token pode estar tanto no CT quanto na posse de

algum processo. Neste ´ultimo caso, o token pode ser travado, quando o processo est´a

utilizando a instˆancia de recurso correspondente, ou pode estar livre.

Neste est´agio, primeiramente um processo tenta encontr ar todos os tokens necess´arios

no conjunto A do Con trol Token. Para escolher os tokens do conjunto A, um processo

pode considerar diversos crit´erios, tais como localiza¸c˜ao f´ısica dos recursos que os tokens

representam ou suas caracter´ısticas de execu¸c˜ao. Existem diversos trabalhos na literatura

3.2 Descri¸c˜ao do algoritmo 23

que abordam o problema de sele¸c˜ao de recursos para aplica¸c˜oes Grid, veja exemplos em

[32] e [39].

A Figura 3.6 mostra a representa¸c˜ao l´ogica dos clusters e logo acima a estrutura

l´ogica do Control Token recebida pelo processo P

. Nessa ﬁgura o CT ´e ilustrado por um

conjunto de tipos de recursos, onde cada tipo de recurso ´e composto por um conjunto de

tokens que representam as instˆancias dos recursos e os processos que eventualmente os

mantˆem. Tamb´em s˜ao mostradas as informa¸c˜oes referentes aos toke ns necess´arios par a um

processo acessar sua se¸c˜ao cr´ıtica e os tokens que ele possui localmente. Para o exemplo,

considere hipoteticamente que o processo necessite de duas instˆancias do recurso R

, uma

instˆancia de R

e uma de R

para acessar sua se¸c˜ao cr´ıtica. Considere tamb´em que ele

possua uma instˆancia do recurso R

, no caso T 6, que ele n˜ao ir´a utilizar.

Figura 3.6: Estrutura do Control Token recebida

Como existe uma instˆancia livre do recurso R

, a qual o processo P

necessita, ele neste

caso pode obtˆe-la e atualizar o Control Token informando que ele agor a a po ssui. Veja

na Figura 3.7 que ilustra esse procedimento. Observe tamb´em, atrav´es do Algoritmo 7,

que ap´os o bter os tokens livres do Control Token (linhas 2 a 6 ), caso o processo encontre

todos os recursos dos quais ele necessita, ele poder´a ent˜ao acessar exclusivamente sua

se¸c˜a o cr´ıtica (linhas 12 a 15). Do contr´ario, ele invoca um procedimento para sele¸c˜ao dos

recursos dos quais ele ir´a pedir ao s processos que os mantˆem.

Outro procedimento utilizado, ´e o de devolver instˆancias n˜ao utilizadas ao Control

Token, para que um outro processo que obtenha o CT e que necessite de tais tokens, evite

mensagens desnecess´arias de pedido. A Figura 3.8 mostra o momento quando o processo

devolve o token T

referente ao recurso R

. No Algo r itmo 7, linhas 7 a 9, tamb´em ´e

mostrado como esse procedimento ´e realizado.

Quando um processo n˜ao encontra todos o s tokens necess´arios no conjunto A, usando

a lista B ele determina de quais processos ele ir´a requisitar os tokens indispon´ıveis. No

algoritmo proposto, um processo pode escolher outro da lista B para enviar uma requisi¸c˜ao

3.2 Descri¸c˜ao do algoritmo 24

Figura 3.7: Obtem os tokens livres do CT

Figura 3.8: Libera tokens n˜ao utilizados ao CT

Algoritmo 7 - Pega os tokens livres no CT

1: Pega Tokens Livres():

2: para todo token t tal que 0 ≤ t < k fa¸ca

3: se CT [t] = 0 e t ∈ tokens

necessarios ent˜ao

4: tokens locais ← tokens locais ∪ t

5: CT [t] ← self

6: ﬁm se

7: se t /∈ tokens

necessarios e t ∈ tokens locais ent˜ao

8: tokens

locais ← tokens locais −t

9: CT

← 0

10: ﬁm se

11: ﬁm para

12: trava tokens

locais

13: se tokens

necessarios ⊆ tokens locais ent˜ao

14: {Acessa a se¸c˜ao cr´ıtica}

15: sen˜ao

16: Seleciona

Tokens ()

17: ﬁm se

18:

de recurso obedecendo a seguinte ordem de prioridades:

1. um processo local que n˜ao usa freq

uentemente o recurso;

2. um processo local que usa freq

uentemente o recurso;

3. um processo remoto que n˜ao usa freq

uentemente o recurso, e ﬁnalmente;

3.2 Descri¸c˜ao do algoritmo 25

4. um processo remoto que usa freq

uentemente o recurso.

Essa etapa pode ser vista no Algoritmo 8, onde estes crit´erios de sele¸c˜ao s˜ao tratados.

Na fun¸c˜ao Seleciona

Tokens, o Control Token ´e percorrido para cada um dos crit´erios de

sele¸c˜ao, selecionando para cada vez, um eventual conjunto de token s e processos. Essa

informa¸c˜ao ´e a rmazenada em um conjunto tempor´ario de pedidos, para que mais tarde,

o processo possa enviar esses pedidos de token aos respectivos processos que os mantˆem.

Algoritmo 8 - Seleciona os toke ns necess´arios

1: Seleciona Tokens():

2: Conjunto P edido ← ∅

3: Seja a tupla (S

, T ) tal que S

∈ CT e T ⊆ tokens

necessarios

4: para todo S

∈ P rocessos Locais e S

/∈ CT.prioridade fa¸ca

5: Conjunto

P edido ← Conjunto P edido ∪ (S

, T )

6: ﬁm para

7: para todo S

∈ P rocessos Locais e S

∈ CT.prioridade fa¸ca

8: Conjunto

P edido ← Conjunto P edido ∪ (S

, T )

9: ﬁm para

10: para todo S

/∈ P rocessos Locais e S

/∈ CT.prioridade fa¸ca

11: Conjunto

P edido ← Conjunto P edido ∪ (S

, T )

12: ﬁm para

13: para todo S

/∈ P rocessos

Locais e S

∈ CT.prioridade fa¸ca

14: Conjunto P edido ← Conjunto P edido ∪ (S

, T )

15: ﬁm para

16: Atualiza

Prioridades Conjunto P edido

17: para todo tupla (S

, T ) ∈ Conjunto P edido fa¸ca

18: Envia Requisicao T oken, T  para S

19: para todo token t

∈ T fa¸ca

20: CT [t

] ← self

21: ﬁm para

22: ﬁm para

23: Aguarda pelo recebimento dos tokens

24: {...}

25:

Observe na Figura 3.9, que o processo P

selecionou a instˆancia T

do recurso R

que

estava com o processo local P

. O crit´erio considerado aqui, foi devido `a localiza¸c˜ao do

processo P

, que resulta em um menor custo de comunica¸c˜ao em rela¸c˜ao `a outra op¸c˜ao, a

instˆancia mantida pelo pro cesso remoto L

Ainda no pro cedimento de sele¸c˜ao de recursos, na Figura 3.10 ´e adicionada a lista

C ao Control Token, que ´e respons´avel por associar prioridades ao s processos que usam

freq

uentemente certos recursos. No exemplo em quest˜ao, P

precisa selecionar dois dos

trˆes tokens que est˜ao na posse dos processos L

, P

e P

. No entanto, como L

possui

prioridade sobre seu recurso, como pode ser visto na ilustra¸c˜ao da lista C, as op¸c˜oes ent˜ao

passam a ser P

e P

A lista C mant´em para cada recurso, a identiﬁca¸c˜ao do processo priorit´ario e um

3.2 Descri¸c˜ao do algoritmo 26

Figura 3.9: Seleciona tokens considerando localiza¸c˜ao

Figura 3.10: Seleciona tokens considerando prioridade

contador que corresponde ao n´umero de solicita¸c˜oes sucessivas a um mesmo recurso que

este processo realizou. Cada processo tamb´em mant´em localmente um contador que ´e

incrementado cada vez que ele necessita desse mesmo recurso. Assim, quando ele recebe o

CT, ele veriﬁca se possui prioridade sobre algum recurso e se insere no CT como priorit´ario.

Caso o processo veriﬁque que n˜ao precisar´a mais da prioridade sobre o recurso, ele retira

sua identiﬁca¸c˜ao da lista de prioridades no CT e reinicia seu contador local. Um processo ´e

considerado um candidato a ter prioridade sobre um recurso quando tal contador alcan¸ca

um valor pr´e-deﬁnido, que ´e um parˆametro do algoritmo e que pode ser conﬁgurado `a

crit´erio da aplica¸c˜a o.

Ao obter a posse do CT, um processo candidato pode atualizar a lista C em um dos

seguintes casos: quando seu contador local supera o limite m´ınimo pr´e-estabelecido e n˜ao

h´a nenhum processo com prioridade sobre o recurso, quando seu contador local ´e maior

que o valor correspondente encontrado no CT, ou ent˜a o, quando seu contador local ´e

inferior ao valor pr´e- deﬁnido e ele deixa de ter prioridade sobre o recurso. O Algoritmo 9

apresenta os detalhes deste procedimento .

Ap´os selecionar os recursos necess´arios, o processo P

envia os pedidos para os pro -

cessos, os quais est˜ao com os tokens que ele selecionou. Veja na Figura 3.11 o exemplo

3.2 Descri¸c˜ao do algoritmo 27

Algoritmo 9 - Atualiza as prioridades dos processos (Processo S

)

1: Atualiza Prioridades(Conj P edido):

2: para todo token t tal que 0 ≤ t < k fa¸ca

3: se prioridade

local[t] > 0 e t ∈ tokens necessarios ent˜ao

4: prioridade local[t] ← prioridade local + 1

5: sen˜ao

6: prioridade

local[t] ← 0

7: CT [t].prioridade[S

] ← 0

8: ﬁm se

9: se prioridade

local[t] ≥ LIMIT E MINIM O P RIORIDADE ent˜ao

10: CT [t].prioridade[S

] ← prioridade

local[t]

11: ﬁm se

12: para todo processo S ∈ Conj P edido fa¸ca

13: CT [t].prioridade[S] ← 0

14: ﬁm para

15: ﬁm para

16:

desse passo.

Figura 3.11: Envia pedidos de recursos aos processos selecionados

O Algoritmo 10, descreve o recebimento de uma mensagem de pedido de token s. Ao

receber essa mensagem, o processo envia imediatamente t odos tokens requisitados, dos

quais est˜ao livres, em uma mensagem chamada ACK1. Essa mensagem ´e enviada mesmo

estando vazia, ou seja, se n˜ao houver nenhum token livre para enviar. Se alguns dos

tokens requisitados est˜ao travados ou ainda n˜ao est˜ao disp on´ıveis localmente, uma segunda

mensagem chamada ACK2 ´e enviada, contendo o restante dos tokens requisitados, quando

estes estiverem dispon´ıveis.

Observe no Algoritmo 11, que quando um processo recebe todas as mensagens de

ACK1, ele ent˜ao trava os tokens recebidos e passa a estar apto a enviar o CT ao pr´oximo

processo da ﬁla (linhas 5 e 6). Al´em disso, caso ele libere o CT a um processo remoto ele

tamb´em deve atribuir o valor 0 `a vari´avel num

preempt, que ´e o contador de preemp¸c˜oes

realizadas. Se o processo receber nas mensagens ACK1 todos os tokens que ele requisitou,

ele entra em sua se¸c˜a o cr´ıtica (linhas 7 e 8). Caso contr´ario, ele aguarda o recebimento

das mensagens ACK2 que contˆem o restante dos tokens solicitados e em seguida, ele

pode entra r em sua se¸c˜ao cr´ıtica (linhas 10 a 12). Veja tamb´em um exemplo desses

procedimentos na Figura 3.12.

3.2 Descri¸c˜ao do algoritmo 28

Algoritmo 10 - Recebe pedido de token

1: Re cebe Requisicao Token(T, S

2: para todo token t ∈ T fa¸ca

3: se travado(t) = F ALSO e t ∈ tokens

locais ent˜ao

4: ACK1 ← ACK1 ∪ t

5: tokens locais ← tokens locais − t

6: sen˜ao

7: Q ← Q ∪ t

8: ﬁm se

9: ﬁm para

10: se Q = ∅ ent˜ao

11: tokens

devidos ← tokens devidos ∪Q

12: ﬁm se

13: Envia Mensagem ACK, ACK1 para S

14:

Figura 3.12: Recebe as mensagens de ACK1 e ACK2

Algoritmo 11 - Recebe mensagem de ACK (ACK1 e ACK2)

1: Re cebe Me nsagem ACK(ACK, S

2: para todo token t ∈ ACK fa¸ca

3: tokens locais ← tokens locais ∪t

4: ﬁm para

5: trava tokens

locais

6: {L ibera o envio do Control Token em caso de pedidos ...}

7: se tokens

necessarios ⊆ tokens locais ent˜ao

8: {Acessa a se¸c˜ao cr´ıtica}

9: sen˜ao

10: {Aguarda o ACK2 ...}

11: trava tokens

locais

12: {Acessa a se¸c˜ao cr´ıtica}

13: ﬁm se

14:

Ao liberar a se¸c˜ao cr´ıtica o processo executa o procedimento Libera SC(), que pode

ser visto no Algoritmo 12. Caso ainda possua o CT, o processo ent˜ao pode envi´a-lo ao

pr´oximo processo da ﬁla distribu´ıda deﬁnida pela vari´avel next, se ela n˜ao estiver vazia.

Al´em disso, se o processo para o qual o CT est´a sendo enviado for um processo remoto,

ele atualiza a va ri´avel owner com a identiﬁca¸c˜ao desse processo remoto. Por ﬁm, ele envia

as mensagens de ACK2 para todos os processos que est˜ao esperando pelos tokens e marca

localmente que os tokens n˜ao est˜ao mais presente.

3.3 An´alise de Complexidade 29

Algoritmo 12 - Libera a se¸c˜ao cr´ıtica

1: Libera SC():

2: requesting ← F ALSO

3: se control

token = V ERDADE e next = 0 ent˜ao

4: se next /∈ P rocesso Locais ent˜ao

5: num preempt ← 0

6: se owner = 0 ent˜ao

7: owner ← remote

owner

8: ﬁm se

9: remote

owner ← 0

10: ﬁm se

11: Envia ControlT oken, CT, num

preempt para next

12: next ← ∅

13: control token ← F ALSO

14: ﬁm se

15: para todo tupla(S

, ACK2) ∈ tokens

devidos fa¸ca

16: tokens

locais ← tokens locais − ACK2

17: Envia M ensagem ACK, ACK2 para S

18: ﬁm para

19: tokens

devidos ← ∅

20:

A an´alise de complexidade apresentada nesta se¸c˜ao ´e baseada no n´umero total de mensa-

gens trocadas para que um processo obtenha o direito de executar sua se¸c˜ao cr´ıtica.

A complexidade de mensagens obtida pelo algoritmo proposto foi baseada na a n´alise

feita pelos trabalhos de Bertier et al. [8], Boubadallah-Laforest [9] e Naimi-Trehel [38], os

quais se relacionam com o trabalho proposto devido `as t´ecnicas empregadas, inspiradas

nestes trabalhos.

Para que um processo obtenha os recursos necess´arios para acessar sua se¸c˜ao cr´ıtica,

o n´umero total de mensagens que ele precisa trocar, no algoritmo proposto, varia de 0 a

n + 3k, onde k ´e o n ´umero de recursos compartilhados e n ´e o n´umero total de processos

do sistema distribu´ıdo. Por´em, na m´edia, para um valor k constante, a complexidade ´e

O(log(n)).

Para uma an´alise mais detalhada dessa complexidade, considere os seguintes casos.

• Se um processo P

encontra todos os tokens que ele necessita localmente, ou seja,

no seu conjunto tokens

locais

, ent˜a o ele entra em sua se¸c˜ao cr´ıtica sem ter enviado

nenhuma mensagem.

• Se um processo P

n˜ao possui todos os tokens localmente. Ent˜ao, no algoritmo

proposto, o processo precisa solicitar o Control Token usando o mesmo mecanismo

3.3 An´alise de Complexidade 30

de busca de token utilizado por Bertier e t al. [8], que por sua vez foi baseado no

algoritmo de Naimi e Trehel [38]. Como esse processo obtem o Control Token em

um espa¸co ﬁnito de tempo, considere as seguintes possibilidades:

a. Assim como nos trabalhos citados [38, 8], o n´umero de mensagens usadas para

obter o Control Toke n (ou token no caso das referˆencias) varia de 0 a n − 1 e

´e O(log(n)) na m´edia, devido `as caracter´ısticas da estrutura l´ogica em ´a r vore

discutidas anteriormente.

b. Quando o processo P

recebe o Control Token, ele entra em sua se¸c˜ao cr´ıtica se

encontrar todos os tokens necess´arios no conjunto de tokens livres do C o ntro l

Token. Por esta raz˜ao, o n´umero de mensagens utilizadas no total ´e o mesmo

do item a.

c. Caso um subconjunto de tokens necess´arios n˜ao esteja dispon´ıvel no Control

Token, ent˜ao o processo P

enviar´a mensagens solicitando esses tokens aos

processos que os possuem ou que o s possuir˜ao. Assim, ´e po ss´ıvel ainda ocorrer

os casos `a seguir:

[1.] O processo P

precisar´a enviar no m´aximo k mensagens pedindo os to-

kens, que equivalem `as instˆancias de recursos, para os processo s que os mantˆem,

e conseq

uentemente receber no m´aximo k mensagens de ACK1 como resposta,

contendo todos os tokens que ele necessita ou n˜ao. Assim, s˜ao a dicionadas k

mensagens ao resultado do item a.

[2.] Caso o processo P

n˜ao receba todos os tokens necess´arios nas mensa-

gens de ACK1 , ele ent˜ao ir´a recebˆe-los nas mensagens de ACK2, que tamb´em

poder˜ao ser no m´aximo k. Assim, al´em das mensagens utilizadas para obter o

Control Toke n (item a), um processo usa no m´aximo 3k para obter o direito

de executar sua se¸c˜ao cr´ıtica.

O algoritmo distribu´ıdo proposto neste trabalho ´e baseado em um modelo ass´ıncrono

em computa¸c˜ao distribu´ıda. O modelo ass´ıncrono se caracteriza pelos fatos de que cada

processo possui uma base de tempo pr´opria e independente das dos outros processos,

chamada de rel´ogio local, e de que o atraso que uma mensagem sofre para ser entregue

entre dois processos ´e ﬁnito, mas imprevis´ıvel. Este modelo ´e considerado mais realista,

pois reﬂete algumas das caracter´ısticas dos sistemas distribu´ıdos atuais.

Para avaliar a qualidade de um algor itmo ´e ´util medir o seu consumo de recursos.

Quanto menor o consumo, melhor o algoritmo. Dependendo do tipo de computa¸c˜ao, tais

recursos podem incluir a quantidade de mem´oria, ciclos de processador, n´umero de proces-

sadores, n´umero de mensagens enviadas e v´arios outros recursos sobre o s quais a demanda

´e mais relevante. No caso dos algoritmos distribu´ıdos, a avalia¸c˜ao de complexidade consi-

dera, geralmente, as mensagens enviadas e o tempo. As medidas s˜ao expressas na fo r ma

de “pior-caso”, que ´e a maior complexidade de qualquer computa¸c˜ao no algoritmo.

A complexidade de mensagens ´e dada pelo n´umero de mensagens enviadas entre pro-

cessos durante a computa¸c˜ao no pior caso considerando-se varia¸c˜oes poss´ıveis na estrutura

de conex˜ao dos processos e nas execu¸c˜oes do algoritmo, que poderiam produzir diferentes

conjuntos de eventos.

Em um modelo ass´ıncrono, a complexidade de temp o deve somente considerar o tempo

relacionado `a comunica¸c˜ao. Assume-se que a computa¸c˜ao local n˜a o consome tempo e que

o tempo para envio de uma mensagem ´e de uma unidade de tempo. A complexidade

de tempo ent˜ao seria o n´umero de mensagens enviadas na maior cadeia causal da forma

“recebo uma mensagem e envio uma mensagem como conseq

uˆencia” que ocorre em todas a s

execu¸c˜oes do algoritmo e sobre todas as varia¸c˜oes na estrutura de conex˜ao dos processos.

4 Rel´ogios L´ogicos 32

A complexidade de tempo somente considera as mensagens que ocorrem“seq

uencialmente”

relativas a eventos de recebimento e envio que possuem uma dependˆencia causal. Assim,

n˜ao s˜ao consideradas as mensagens relacionadas a eventos concorrentes.

Uma abstra¸c˜ao ´util consiste em modelar a computa¸c˜ao que acontece localmente em um

processo como uma seq

uˆencia de eventos. Associados com um evento est˜ao: a identiﬁca¸c˜ao

do processo onde ele ocorre, o tempo local no qual o evento acontece, assim as poss´ıveis

mudan¸cas no estado local do processo decorrentes ou do envio (recebimento) de mensagens

para (de) vizinhos ou da execu¸c˜ao de uma opera¸c˜ao que n˜ao envolva intera¸c˜ao com outro

processo, chamado de evento interno. Em um evento s´o se pode receber no m´aximo uma

mensagem, embora nenhuma restri¸c˜ao exista em rela¸c˜ao ao n´umero de mensagens enviadas

associadas a este evento. A computa¸c˜ao distribu´ıda que acontece ´e ent˜ao naturalmente

associada com o conjunto de eventos que ocorrem em todos os processos, e que denotamos

por V .

Apesar de o sistema ser totalmente ass´ıncrono, existe uma rela¸c˜ao de interdependˆencia

entre os diversos eventos que constituem a computa¸c˜ao, deﬁnida por Lamport [30].

Considere, por exemplo, que os evento s v

, v

∈ V . Dizemos que v

“aconteceu-antes”

de v

, se e somente se os eventos v

e v

ocorrem no mesmo processo, p

por exemplo,

nos tempos locais t

< t

e nenhum outro evento ocorre naquele mesmo processo em um

instante t



tal que t

< t



< t

. Ou ent˜a o, v

envolve o envio de uma mensagem m recebida

atrav´es de v

, sendo que v

e v

ocorrem em processos vizinhos.

Seja A uma rela¸c˜ao chamada de rela¸c˜ao de causalidade ou “aconteceu-antes” [30, 6],

onde v ∈ V . Se os eventos v

e v

ent˜ao v

. A rela¸c˜ao A ´e transitiva e

irreﬂexiva, f ormando, portanto, uma ordem parcial sobre os eventos de V .

Podemos descrever as ocorrˆencias de eventos sobre o tempo atrav´es de um diagra ma

de tempo. Assim, processos s˜ao representados por eixos de tempos locais, nos quais os

tempos locais crescem da esquerda par a a direita e setas representam mensagens. Esta

representa¸c˜ao ´e utilizada no decorrer deste cap´ıtulo. Na Figura 4.1, s˜ao representados

dois processos, i e j, e podemos observar que v

, v

e v

, segundo a deﬁni¸c˜ao

da rela¸c˜ao de causalidade.

4.1 Rel´ogios L´ogicos 33

❙

❙✇

•

Figura 4.1: Rela¸c˜ao a co nteceu-antes

Para a compreens˜ao adequada da execu¸c˜ao de um programa distribu´ıdo ´e importante

determinar a ordem causal entre os eventos que ocorrem na computa¸c˜ao. A concorrˆencia

entre eventos e o n˜ao-determinismo em programas distribu´ıdos s˜ao quest˜oes importantes

na an´alise, monitora¸c˜ao, depura¸c˜ao e visualiza¸c˜ao destes eventos.

Em computa¸c˜oes distribu´ıdas, os rel´ogio s devem ser deﬁnidos de forma a expressar a

causalidade entre os eventos. A caracteriza¸c˜ao e representa¸c˜a o de rela¸c˜ao de causalidade

entre os eventos n˜a o ´e um problema trivial. Consideramos que um rel´ogio ´e uma fun¸c˜ao

T de eventos para um conjunto ordenado (V , <), tal que vAv



⇒ T (v) < T (v



Caso consider´assemos T (v) o instante de tempo real no qual o evento v ocorre, n˜ao

conseguir´ıamos caracterizar a causalidade entre os eventos, po r que T (v) < T (v



) n˜ao ne-

cessariamente implicaria em vAv



. Um problema adicional ´e que, geralmente, n˜ao est˜ao

dispon´ıveis em sistemas distribu´ıdos um conjunto de rel´ogios locais de tempo real sincro-

nizados.

Lamport [30] apresentou um rel´o gio que atribui a um evento v o comprimento k

da maior seq

uˆencia (e

, e

, ··· , e

) de eventos que satisfaz e

A ···e

= v, tal que

T (e

) < T (e

) < ··· < T (e

O valor de T pode ser calculado para cada evento ocorrido em um processo p pelo

algoritmo distribu´ıdo apresenta do no Algoritmo 13.

No algoritmo apresenta do n˜ao ´e especiﬁcado sob que condi¸c˜oes uma mensagem deve

ser enviada ou como o estado de um processo muda. O rel´ogio ´e um mecanismo suple-

mentar que pode ser acrescentado a qualquer algo ritmo distribu´ıdo para ordenar seus

eventos. A cada execu¸c˜ao de um evento o rel´ogio local do processo ´e incrementado. A

cada mensagem enviada ´e anexado o rel´ogio local do processo. Al´em disso, ao receber

uma mensagem, o processo atualiza o seu rel´ogio local com o valor m´a ximo entre o valor

4.1 Rel´ogios L´ogicos 34

Algoritmo 13 - A¸c˜oes em p pa ra o algoritmo REL

OGIO DE LAMPORT:

(1) Para um estado inicial:

← 0

(2) Regra para envio de mensage m:

← T

+ 1

Envie msg, T

;

Mude o estado

(3) Regra para recebimento de mensagem de um processo i ∈ N

← max(T

, T

) + 1

Mude o estado

(4) Regra para evento interno:

← T

+ 1

Mude o estado

❍

❍❥

✑

✑✸

• •



0 1 2

0 1 4

2 3

Figura 4.2: Rel´og io de Lamport

de rel´ogio recebido e o seu pr´oprio e incrementa de um.

A Figura 4.2 ilustra os valores dos rel´o gios locais dos processos i, j e k no decorrer de

suas execu¸c˜oes.

Em alguns casos, ´e ´util que os rel´ogios expressem n˜ao somente a ordem causal entre os

eventos, mas tamb´em a concorrˆencia entre eles. Uma importante considera¸c˜ao a respeito

do rel´ogio de Lamport, ´e que ele satisfaz a propriedade v → v



⇒ T (v) < T (v



), no entanto

o oposto n˜ao ´e verdadeiro. Observe na Figura 4.2 que T

(v) = 1 < T



) = 2, entretanto

n˜ao se pode dizer que vAv



. Fidge [20] e Mattern[35] propuseram um mecanismo conhecido

como rel´ogio de vetor, que satisfaz a seguinte propriedade: v → v



⇔ T (v) < T (v



). Neste

caso, um vetor ´e associado a cada estado local de cada processo tal que a ordem parcial

dos eventos ´e preservada.

Considere a existˆencia de n processos identiﬁcados por inteiros com valores entre 1

e n. O rel´ogio de vetor T

´e atualizado em um processo p ∈ 1, ··· , n segundo as regras

descritas no Algoritmo 14.

No Algoritmo 14 um processo incrementa seu pr´oprio componente do vetor depois

de cada evento. Al´em disso, ele inclui seu rel´ogio vetor em cada mensagem enviada. Na

recep¸c˜ao de uma mensagem, ele atualiza seu vetor com o m´aximo entre os componentes

4.2 Rel´ogios L´ogicos como Estrat´egia de Medi¸c˜ao de Desempenho 35

Algoritmo 14 - A¸c˜oes em p pa ra o algoritmo REL

OGIO DE VETOR:

(1) Para um estado inicial:

(∀i : (i = p) : T

[i] = 0) ∧(T

[p] = 1)

(2) Regra para envio de mensage m:

[p] ← T

[p] + 1

Envie msg, T

;

Mude o estado

(3) Regra para recebimento de mensagem de um processo i ∈ N

Receba msg, T

;

para j = 1 at´e n fa¸ca

[j] ← max(T

[j], T

[j])

ﬁm para

[p] ← T

[p] + 1

Mude o estado

(4) Regra para evento interno:

[p] ← T

[p] + 1

Mude o estado

❍

❍❥

✑

✑✸

• •



1, 0, 0 2, 0, 0 3, 0, 0

0, 1, 0 0, 2, 0 0, 3, 3

0, 0, 1

0, 2, 0

0, 2, 2 0, 2, 3

0, 2, 3

Figura 4.3: Rel´og io de Vetor

dos vetores e incrementa o elemento correspondente a sua pr´opria posi¸c˜ao.

A Figura 4.3 ilustra a execu¸c˜ao de tal algoritmo. Repare que n˜ao ocorre T

(v) =

(2,0,0) < T



= (0,2,2) nem T



) = (0,2,2) < T

(v) = (2,0,0) e que v e v



s˜ao eventos

concorrentes.

Os rel´ogios de vetores tˆem sido tipicamente empregados em a lg oritmos que auxiliam a

depura¸c˜ao e an´alise de programas paralelos distribu´ıdos. Existem ainda generaliza¸c˜oes da

no¸c˜ao de rel´ogios vetores, chamados rel´ogios matrizes [18], que permitem a representa¸c˜ao

da precedˆencia causal com um n´ıvel maior de profundidade cuja aplica¸c˜ao not´oria pode

ser encontrada na ´area de bancos de dados.

Em ambientes de Grids, o tempo de rel´ogio de parede de duas execu¸c˜oes de um mesmo

programa pode variar dependendo da carga externa nas m´aquinas. Medir o desempenho

4.2 Rel´ogios L´ogicos como Estrat´egia de Medi¸c˜ao de Desempenho 36

em tais a mbientes ´e uma tarefa complexa e n˜ao garante a total conﬁabilidade dos resul-

tados devido a tais varia¸c˜oes de tempo. Por esta raz˜ao, utilizamos o modelo de rel´ogio

l´ogico como uma estrat´egia adicional para medir o desemp enho dos algoritmos.

Assim como sugerido em Drummond e Barbosa [18], foi adaptado neste trabalho um

modelo de rel´ogio l´ogico a ﬁm de medir o tempo de espera para um processo entrar em

sua se¸c˜ao cr´ıtica. O emprego de rel´ogios l´ogicos ´e baseado em rel´ogio de vetores, como

proposto em [20, 35] com alg umas mudan¸cas para reﬂetir a diferen¸ca de latˆencia dos canais

de comunica¸c˜ao em um ambiente de Grid.

Consideramos aqui a maior cadeia com rela¸c˜ao de causalidade para que um processo

obtenha a mensagem que concede a ele o direito de executar sua se¸c˜ao cr´ıtica. A unidade

de tempo contabilizada no rel´ogio l´ogico proposto ´e dada pela latˆencia hipot´etica dos

canais de comunica¸c˜ao que interligam os processos remotos. A latˆencia nos canais que

interconectam processos que est˜ao em um mesmo cluster ´e desconsiderada, para que seja

poss´ıvel medir a inﬂuˆencia das latˆencias nos canais remotos.

Um exemplo desta id´eia ´e ilustrado na Figura 4.4. Observe a cadeia causal formada,

no “pior-caso”, envolvendo os processos que solicitaram o acesso `a se¸c˜ao cr´ıtica, e o retorno

da mensagem onde ´e contabilizado o tempo l´o gico esperado por cada processo.

10ms

80ms

100ms

Mensagens de pedido

Acesso à seção crítica

190ms

180ms

Figura 4.4: Exemplo de Execu¸c˜ao do Rel´ogio L´ogico

O mecanismo de rel´og ios l´o gicos adaptado por esse trabalho foi utilizado estritamente

para medi¸c˜ao de desempenho dos a lg oritmos testados, e n˜ao na sincroniza¸c˜ao ou ordena¸c˜ao

de mensagens como utilizado em [30]. Ou seja, o uso de Rel´ogios L ´ogicos n˜ao altera a

execu¸c˜ao dos algoritmos, apesar de serem utilizadas estruturas acopladas `a s mensagens

para sua monitora¸c˜ao.

No algoritmo pro posto, para executar uma se¸c˜ao cr´ıtica, um processo, a partir do

momento que requisita acesso `a sua se¸c˜ao cr´ıtica precisa esperar pelo Control Token e pelos

tokens dos recursos. O tempo total requerido para um processo entrar em sua se¸c˜ao cr´ıtica

´e obtido pela soma dos tempos de espera. No algoritmo proposto, mensagens de r equisi¸c˜ao

ao Control Token de um processo seguem o mesmo caminho deﬁnido pelas mensagens de

4.2 Rel´ogios L´ogicos como Estrat´egia de Medi¸c˜ao de Desempenho 37

Control Token, possivelmente composto de conex˜oes com diferentes latˆencias. Ent˜ao,

para monitorar a espera ao Control Token, ele precisa somente monitorar a s mensagens

de Control Token. Analogament e, uma requisi¸c˜ao a um token de recurso pode chegar a

um processo que ainda n˜ao o obteve. Por exemplo, um processo que tamb´em espera por

mensagens ACK2 par a entrar em sua se¸c˜ao cr´ıtica e ent˜ao ao sair ele envia as mensagens

ACK2 correspondente, formando uma corrente de mensagens ACK2.

Considerando estes fatos, propusemos um rel´ogio l´ogico que tem como objetivo a cap-

tura do maior caminho encadeado de mensagens de tokens com rela¸c˜ao causal. Ele f oi

constru´ıdo fazendo com que cada processo P

mantivesse n elementos no vetor, V

, coleta-

dos ao longo das mensagens de tokens. Como dois tipos de mensagens s˜ao monitorados,

Control Token e ACKs, dois vetores s˜ao necess´arios, no entanto as regras de atualiza¸c˜ao

deles s˜a o similares.

As regras para atualizar o vetor do Control Token s˜ao descritas no Algoritmo 15.

Algoritmo 15 - Adapta¸c˜ao do Rel´ogio L´o gico - Pro cesso P

1: (R.1) Ao receber uma mensagem de Control Token de um processo P

(Control Token, V

2: controltoken

waiting time ← V

[i];

3: para todo k ∈ V

fa¸ca

4: V

[k] ← max(V

[k],V

[k]);

5: ﬁm para

6: V

[i] ← 0;

2: (R.2) Ao enviar uma mensage m de Control Token a um processo P

em uma conex˜ao

com latˆencia x:

3: para todo k ∈ V

fa¸ca

4: V

[k] ← (V

[k] + x);

5: ﬁm para

6: Envia ControlT oken, V

 para P

Embora os algoritmos para atualiza¸c˜a o do Contro l Token e dos vetores ACKs sejam

os mesmos, os m´etodos para o c´alculo do tempo de espera par a cada token de recurso

e para o Control Token n˜ao s˜ao iguais. No caso de mensagens dos tokens de recursos,

deve-se considerar o maior tempo de espera acumulado das mensagens ACK1 e ACK2.

Assim, no Algoritmo 15, a linha 2 de R.1 ´e substitu´ıda po r :

“resourcetoken waiting time ← max(resourcetoken waiting time,V

[i])”

O resourcetoken

waiting time precisa tamb´em ser comparado com o maior tempo

de espera acumulado de todas mensagens AC K 1 .

Como a cadeia de espera para o Control Token e os tokens de recursos ocorrem

seq

uencialmente, no pior caso o t empo necess´ario para que um processo P

execute

4.2 Rel´ogios L´ogicos como Estrat´egia de Medi¸c˜ao de Desempenho 38

sua se¸c˜ao cr´ıtica, ´e a soma do tempo em controltoken waiting time com o tempo em

resourcetoken

waiting time.

Veja na Figura 4.5 um exemplo envolvendo quatro mensagens trocadas por quatro

processos conectados atrav´es de links com diferentes latˆencias, e os rel´o gios l´ogicos cor-

respondentes. Nessa ﬁgura, quatro processos P

, P

e P

executam o envio de uma

mensagem entre eles. Repare na ﬁgura, que as setas representam uma mensagem com

dependˆencia causal entre os processos. Note que a cada envio da mensagem de um pro-

cesso para o utro, o vetor l´ogico ´e incrementado pela latˆencia do canal que interliga esses

processos. Na ﬁgura, ´e poss´ıvel tamb´em observar para cada processo, uma imagem de seu

vetor atualizado localmente, onde os valores em negrito representam os tempos l´ogicos

utilizados para que a mensagem chegasse at´e ao processo.

❆

❆❯

❆

❆❯

❆

❆❯

✁

✁✕

[0], 0, 0, 0 0, 770, 750, 500

0, 0, 0, 0

10, [10], 10, 10

[780], 770, 750, 500

0, 0, 0, 0

10, 0, 10, 10

30, 20, [30], 30

0, 0, 0, 0

30, 20, 0, 30

280, 27 0, 250, [280]

280, 27 0, 250, 0

10ms

20ms

250ms

500ms

Figura 4.5: Rel´og io de Vetor Proposto

Nos experimentos usando o mecanismo de rel´ogios l´ogicos, consideramos que as mes-

mas instˆancias de recursos s˜ao requisitadas em cada se¸c˜ao cr´ıtica, por´em diferentes para

cada processo.

Este cap´ıtulo apresenta uma an´alise do desempenho dos algoritmos propostos em

rela¸c˜ao aos existentes na literatura. Com o intuito de atestar o bom desempenho dos

algoritmos desenvolvidos neste trabalho, foram utilizados diversos cen´arios com diferentes

parˆametros e conﬁgura¸c˜oes f´ısicas, comparando os algoritmos propostos com o algoritmo

de Bouabdallah-Laforest [9] e uma generaliza¸c˜ao.

Os algoritmos a presentados neste trabalho foram implementados na linguagem Python

vers˜ao 2.5 , usando a ferramenta PyMPI como uma camada de integra¸c˜ao entre o inter-

pretador Python e a biblioteca de troca de mensagens MPI, executando sobre a imple-

menta¸c˜ao LAMMPI (vers˜ao 7.1.4) usada nos testes. A escolha da linguagem Python para

o desenvolvimento do algoritmo foi feita devido `a necessidade de se ter uma linguagem

de desenvolvimento r´apido, com uso de diversos componentes de alto n´ıvel, como estru-

tura de dados e fun¸c˜oes simpliﬁcadas para manipula¸c˜ao de arquivos, al´em de possuir uma

abstra¸c˜ao ´util na integra¸c˜ao com a biblioteca MPI.

Os experimentos apresentados neste traba lho foram executados em dois ambientes

computacionais distintos, que foram:

• Ambiente de testes 1: Neste ambiente, foram utilizadas 24 esta¸c˜oes de trabalho

bi-processadas, com processadores Intel Xeon 3.06 GHz com 512 KB de cache e

AMD Opteron 248 2 .2 GHz e 1024KB de cache. Foram utilizados 6 0 processadores

no to tal, contando com os n´ucleos dos processadores dual core. Todas as esta¸c˜oes

5.1 Ambiente de Testes 40

possuem instalado o sistema operacional GNU/Linux com kernel 2.4.21 compilado

com suporte a SMP ( Symmetric Multi Processor), o que permite que o sistema

operacional gerencie os processadores para que eles sejam utilizados em paralelo.

As esta¸c˜oes est˜ao conectadas a uma rede Ethernet de 1.0 Gbits/s com latˆencia

pr´oxima a zero.

• Ambiente de test es 2: Neste segundo ambiente computacional, utilizamos 24

computadores, cada um com um processador Intel Pentium IV com 2.6 GHz de

freq

uˆencia, 512 MB de mem´oria RAM, sistema operacional GNU/Linux com kernel

2.6.8, conectados por uma rede ethernet de 1.0 Gbits/s.

Nessa disserta¸c˜ao de mestrado s˜a o apresentados dois m´etodos que foram usados para

medi¸c˜ao de desempenho dos alg oritmos distribu´ıdos. O primeiro m´etodo consiste em

medi¸c˜oes utilizando tempo de rel´ogio de par ede ou rel´ogio f´ısico. Este m´etodo ´e usado

para medir o tempo que um processo demora para entrar em sua se¸c˜ao cr´ıtica (SC). O

outro m´etodo utiliza o mecanismo de rel´ogios l´ogicos, seguindo o conceito descrito no

Cap´ıtulo 4.

Inicialmente, para emular um ambiente Grid usando o Ambiente de testes 1, foi

criada uma topologia l´ogica que consiste de 48 processadores divididos entre trˆes clusters

(C0, C1 e C2), contendo em cada cluster 16 processadores. Esta topolog ia l´ogica foi

criada com base no n´umero de processadores f´ısicos dispon´ıveis, o pta ndo assim por alocar

cada processador l´ogico a um processador f´ısico. Para o Ambiente de testes 2, que ´e

composto de 24 processadores f´ısicos, utilizamos a topologia l´ogica de 24 processadores

divididos entre trˆes clusters, contendo 8 processadores em cada cluster. Dessa forma, foi

mantida a estrat´egia de alocar cada processador l´ogico a um processador f´ısico.

Em alguns dos testes realizados, variamos as latˆencias dos canais de comunica¸c˜ao entre

os processadores, simulando processadores distantes geograﬁcamente ou que se comunicam

por canais mais lentos. Para simular estas latˆencias, foram utilizadas duas estrat´egias.

A primeira utiliza a fun¸c˜ao de sleep da linguagem Python, que atrasa a execu¸c˜ao de um

c´odigo de acordo com a quantidade de segundos informados no parˆametro da fun¸c˜ao. A

segunda, utiliza a ferramenta NetEm [1] e [25]. O NetEm ´e uma ferramenta que permite

emular propriedades de redes. Ele trabalha como um m´odulo do kernel, permitindo inserir

atrasos diretamente nos pacotes de ent rada e sa´ıda da rede. A ferramenta NetEm atual-

mente ´e disponibilizada em conjunto com o pacote de ferramentas para redes e controle

de tr´afego iproute2 [2].

5.2 Algoritmo Proposto vs. Bouabdallah-Laforest para M´ultiplos Recursos com Uma Instˆancia41

Os r esultados desta avalia¸c˜ao s˜ao uma m´edia de 10 execu¸c˜oes. Em cada execu¸c˜ao um

processo entra em sua se¸c˜ao cr´ıtica por 10 vezes. Em cada vez, ele solicita um conjunto

de recursos, ao recebˆe- lo , ele entra em sua se¸c˜ao cr´ıtica permanecendo po r um tempo α e

ap´os sair dela, libera os recursos. Em seguida, esse processo a guarda ainda um tempo β

para fazer uma nova solicita¸c˜ao de recursos para entrar novamente em sua se¸c˜ao cr´ıtica.

Para simular os pedidos de recursos feitos pelos processos, foi criado um arquivo com todos

os recursos e instˆancias gerados aleatoriamente. Neste arquivo ´e deﬁnido um conjunto de

recursos e instˆancias que cada processo solicita para entrar em sua se¸c˜ao cr´ıtica. O mesmo

arquivo ´e usado nos testes dos dois algoritmos.

Por ﬁm, no algoritmo proposto, quando um processo remoto solicita o Control Token,

´e criada uma ﬁla de prioridade que faz com que os processos locais posterguem o envio

do Control Token ao n´o remoto pelo n´umero de vezes deﬁnido no parˆametro “Limite de

Preemp¸c˜oes”. Essa estrat´egia permite que processos locais recebam prioridade em rela¸c˜ao

a processos remotos, reduzindo com isso, o envio de mensagens remotas pelos canais de

comunica¸c˜ao. Por´em, atingido o valor limite, as requisi¸c˜oes remotas que est˜ao na ﬁla s˜ao

imediatamente atendidas, evitando assim o problema de starvation. O valor deﬁnido neste

parˆametro equivale a 50% do n´umero de processos em cada clusters.

Nos testes realizados utilizando rel´ogios l´ogicos, n˜ao se contabiliza no tempo l´o gico os

tempos de α e β. Apesar de eles inﬂuenciarem no resultado ﬁnal do algoritmo, estes s´o

tem valor signiﬁcativo nos tempos contabilizados por rel´ogios f´ısicos.

Inicialmente, comparamos a primeira vers˜ao do algoritmo proposto com o algoritmo

de Bouabdallah e Laforest, que resolve o problema de exclus˜ao m´utua com m´ultiplos re-

cursos compartilhados, por´em com uma ´unica instˆancia por cada recurso. Em seguida foi

feita uma adapta¸c˜ao do algoritmo de Bouabda llah e Laforest para atender o caso gene-

ralizado deste mesmo problema, utilizando, por´em, um ambiente com m ´ultiplos recursos

e m´ultiplas instˆancias para cada recurso, assim como proposto em seu artigo [9]. Esta

adapta¸c˜ao foi comparada com a segunda vers˜ao do algoritmo proposto.

Nesta se¸c˜ao est˜ao descritos os resultados dos testes realizados com a primeira conﬁgura¸c˜ao

do algoritmo proposto neste trabalho. Os testes a seguir consideram o problema da

exclus˜ao m´utua para o caso de haver m´ultiplos recursos e apenas uma instˆancia por tipo

5.2 Algoritmo Proposto vs. Bouabdallah-Laforest para M´ultiplos Recursos com Uma Instˆancia42

de recurso. Neste caso, um processo pode entra r em sua se¸c˜ao cr´ıtica a partir da obten¸c˜ao

de um subconjunto qualquer destes recursos. Processos podem entrar simultaneamente

em suas respectivas se¸c˜oes cr´ıticas desde que mantenham o acesso exclusivo.

Este experiment o possui o objetivo de investigar os efeitos da varia¸c˜ao da latˆencia entre

clusters, simulando as mensagens que trafegam pelos canais de comunica¸c˜ao, que interco-

nectam processadores geograﬁcamente distantes, ou que sejam mais lentos.

A varia¸c˜ao da latˆencia ´e representada nas ﬁguras, no eixo das abscissas, variando-se

em 1ms, 250ms, 500ms e 750ms. No eixo das ordenadas, ´e mostrada a m´edia dos tempos

representados em milisegundos. Para as latˆencias de comunica¸c˜ao local, consideramos um

tempo constante para efeito de testes de 1ms.

Para avaliar os algoritmos testados, utilizamos os dois mecanismos de medi¸c˜ao de

desempenho citados anteriormente, e que s˜ao apresentados a seguir.

Os resultados a seguir foram obtidos usando o Ambiente de testes 1.

O uso de rel´ogio s l´ogicos nos testes, como deﬁnido no Cap´ıtulo 4, p ermite que avalie-

mos o tamanho da maior cadeia de mensagens com rela¸c˜ao de causalidade, no pior caso.

Essa cadeia de mensagens representa o tempo l´ogico que um processo leva para obter

acesso `a sua se¸c˜ao cr´ıtica.

Nos testes de rel´ogio l´ogico a seguir, cada processo sempre pede os mesmos recursos

em todas as execu¸c˜oes.

A Figura 5.1(a) ilustra os valores dos tempos m´edios, obtidos atr av´es da soma das

latˆencias dos canais, at´e a obten¸c˜ao do Control Token. Observe que as curvas do gr´a ﬁco

tendem a um crescimento, a medida que a latˆencia entre clusters aumenta. No entanto,

tamb´em podemos ver que na curva referente ao algoritmo proposto, o crescimento obser-

vado ´e muito menor, o que signiﬁca uma redu¸c˜ao no tempo de obten¸c˜ao do Control Token

em compara¸c˜ao com o alg oritmo de Bo ua bdallah-Laforest. Este resultado foi obtido atra-

v´es do mecanismo que prioriza requisi¸c˜oes de processos locais em rela¸c˜ao aos processos

remotos, evitando o envio de mensagens remotas e criando assim, uma ﬁla local por onde

o Co ntro l Token possa ser passado. Veja ta mb´em, na Figura 5.1(b), que a s m´edias da

5.2 Algoritmo Proposto vs. Bouabdallah-Laforest para M´ultiplos Recursos com Uma Instˆancia43

5000

10000

15000

20000

25000

1ms 250ms 500ms 750ms

Tempo Logico (ms)

Latencia (ms)

Variacao de Latencias

Proposto

Bouabdallah-Laforest

(a)

100

200

300

400

500

600

700

800

900

1ms 250ms 500ms 750ms

Tempo Logico (ms)

Latencia (ms)

Variacao de Latencias

Proposto

Bouabdallah-Laforest

(b)

5000

10000

15000

20000

25000

1ms 250ms 500ms 750ms

Tempo Logico (ms)

Latencia (ms)

Variacao de Latencias

Proposto

Bouabdallah-Laforest

(c)

20000

40000

60000

80000

100000

120000

140000

Bouabdallah-Laforest Proposto

Numero de Mensagens

Algoritmos

Locais

Remotas

Total

(d)

Figura 5.1: Varia¸c˜ao da latˆencia - M´ultiplos Recursos com uma Instˆancia: (a) M´edia do

tempo l´ogico para obten¸c˜ao do Con trol Token (b) M´edia do tempo l´ogico para obten¸c˜a o

do ultimo token (c) M´edia da soma dos tempos anteriores (d) N´umero de mensagens

trocadas

soma das latˆencias dos canais para a obten¸c˜ao de cada token, no algoritmo proposto, tam-

b´em s˜ao reduzidas em rela¸c˜ao ao algoritmo concorrente. Isto ocorre pelo procedimento

anterior de obten¸c˜ao do Control Token que faz com que processos locais sejam atendidos

com maior prioridade, mantendo o Control Toke n por mais tempo localmente. Com isso,

tem-se uma concentra¸c˜ao maior dos tokens entre os processos locais, o que gera um menor

custo de obten¸c˜a o dos mesmos. O r esultado apresentado na Figura 5.1(c), foi obtido a

partir da soma das m´edias dos tempos l´ogicos para obten¸c˜ao do Control Token e para

obten¸c˜ao dos tokens que representam os recursos.

O n´umero de mensagens trocadas entre os processos ´e apresentado na Figura 5.1(d).

Esta ﬁgura permite visualizar a rela¸c˜ao entre mensagens remotas e mensagens locais tro-

cadas pelos dois algoritmos em quest˜ao. Observe que o algoritmo proposto reduziu em

cerca de 90% a quantidade de mensagens remotas em rela¸c˜ao a mensagens locais, enquanto

o algoritmo de Bouabdallah-Laforest enviou 47% mais mensagens por canais remotos do

5.2 Algoritmo Proposto vs. Bouabdallah-Laforest para M´ultiplos Recursos com Uma Instˆancia44

que por canais locais, o que enfatiza os resultados o btidos nas ﬁguras anteriores. Mesmo

n˜ao sendo o objetivo da t´ecnica utilizada, houve ainda uma pequena redu¸c˜ao de 4.6% no

n´umero total de mensagens trocadas, utilizando o algoritmo proposto.

Para os testes a seguir, foram utilizados os dois ambientes computacionais apresentados no

in´ıcio deste cap´ıtulo. Essa estrat´egia permite-nos observar o comportamento do algoritmo

em ambientes de testes distintos, usando formas distintas para inserir as latˆencias.

No Ambiente de testes 1, composto por 48 processadores heterogˆeneos, foram

realizados testes inserindo as latˆencias atrav´es da fun¸c˜ao sleep da linguagem Python. O

atraso neste caso ´e inserido no ato do envio de uma mensagem para um canal logicamente

conﬁgurado como distante. O objetivo aqui ´e medir o tempo que um processo leva para

obter acesso a sua se¸c˜ao cr´ıtica a partir do momento que ele a solicita.

Note na Figura 5.2, que o aumento da latˆencia resulta em um maior tempo para

obter acesso `a se¸c˜ao cr´ıtica, para ambos os algoritmos. Por´em, tem-se um ganho de

desempenho no algoritmo proposto, que consome um tempo muito menor de obten¸c˜ao

do que o algoritmo de Bouabdallah-Lafo r est. Veja que o crescimento das curvas em

rela¸c˜ao aos testes anteriores com rel´ogio l´ogicos ´e semelhante, apesar de usarem medidas

diferentes.

110

120

130

140

150

160

170

180

190

200

210

220

1ms 250ms 500ms 750ms

Tempo de Obtencao (s)

Latencia (ms)

Variacao de Latencias

Proposto

Bouabdallah-Laforest

Figura 5.2: Tempo de Obten¸c˜ao - usando Sleep - M´utiplos Recursos com uma Instˆancia

Os valores apresentados na Figura 5.3, foram obtidos dos testes realizados no Am-

biente de testes 2, que consiste em um ambiente com 24 processadores homogˆeneos.

Assim como no teste anterior, foram inseridos atrasos nos canais de comunica¸c˜ao entre

os processos para simula¸c˜ao da latˆencia, no entanto, nesta avalia¸c˜ao foi utilizada a fer-

ramenta NetEm, j´a mencionada no in´ıcio deste cap´ıtulo. Como pode ser observado na

5.3 Algoritmo Proposto vs. Bouabdallah-Laforest para M´ultiplos Recursos com M ´ultiplas Instˆancias45

Figura 5.3, o algoritmo proposto ta mb´em se mant´em mais eﬁciente do que o algoritmo

de Bouabdallah-Laforest, isso porque a curva que representa este ´ultimo, apresentou ter

uma tendˆencia a um crescimento maior do que a curva obtida pelo algoritmo proposto.

Isso mostra que, mesmo em ambientes computacionais diferentes, os resultados s˜ao bem

relacionados.

1ms 250ms 500ms 750ms 1000ms

Tempo de Obtencao (s)

Latencia (ms)

Variacao de Latencias

Proposto

Bouabdallah-Laforest

Figura 5.3: Tempo de Obten¸c˜ao - usando NetEm - M´ultiplos Recursos com uma Instˆancia

Os resultados dos temp os m´edios de obten¸c˜ao e desvio padr˜ao usando rel´ogio l´ogico e

f´ısico (com sleep), s˜ao apresentados na Tabela 5.1. Nessa ta bela, ´e poss´ıvel veriﬁcar que os

valores percentuais do desvio padr˜ao se mantiveram uniformes, n˜ao apresentando grande

varia¸c˜ao em rela¸c˜ao aos valores crescentes nas m´edias dos tempos para obten¸c˜ao da se¸c˜ao

cr´ıtica. A Tabela 5.2, mostra o n´umero de mensagens trocadas em cada varia¸c˜ao realizada

pelos algoritmos. Nessa tabela, ´e po ss´ıvel notar que o algoritmo proposto, em todas as

varia¸c˜oes, r eduziu o n´umero de mensagens remotas em rela¸c˜ao `as mensagens locais. J´a

o algoritmo de Bouabdallah-La forest, enviou em n´umero maior de mensagens por canais

remotos do que por canais locais, o que por conseq

uˆencia, apresentou resultados inferiores.

Pelo n´umero de preemp¸c˜oes mostrado nesta tabela, podemos observar que o mecanismo

de preemp¸c˜oes foi bem utilizado em todas as varia¸c˜oes, este que permite que dado um

limite de atendimentos `a processos locais, processos remotos sejam atendidos, evitando

assim, o problema de starvation.

Nesta segunda parte dos testes, s˜ao apresentado s os resultados obtidos com a segunda

vers˜ao do alg oritmo proposto e com uma generaliza¸c˜ao do algoritmo de Bouabdallah-

Laforest, que consideram um ambiente com m´ultiplos recursos e m´ultiplas instˆancias.

5.3 Algoritmo Proposto vs. Bouabdallah-Laforest para M´ultiplos Recursos com M ´ultiplas Instˆancias46

Tabela 5.1: Tempos M´edios e Desvio Padr˜ao - Varia¸c˜a o de Latˆencias - M´ultiplos

Recursos com U ma Instˆancia

Algoritmos Latˆencias(ms) Rel´ogio F´ısico (s) Rel´ogio L´ogico(ms)

M´edia Desv. Pad (%) M´edia Desv. Pad (%)

1ms 11 6.66 4.77 47.59 0.58

Algoritmo 250ms 119.06 4.96 647.51 1.00

Proposto 500ms 123.12 4.99 1241.35 0.98

750ms 128.37 4.96 1851.61 1.05

1ms 12 7.60 4.27 47.52 0.57

Bouabdallah 250ms 147.70 4.86 8099.20 0.77

Laforest 500ms 177.26 5.85 15945.45 0.81

750ms 210.14 5.55 24409.01 0.67

Tabela 5.2: Tabel a do N´umero de Mensag ens Trocadas - Varia¸c˜ao de Latˆencias -

M´ultiplos Recursos com Uma Instˆancia

Algoritmos Latˆencias(ms) N´umero de Mensagens Preemp¸c˜oes

Remotas Locais

1ms 384.00 4107.14 88

Algoritmo 250ms 376.14 4092.14 85

Proposto 500ms 389.43 4090.00 88

750ms 379.57 4074.43 86

1ms 3 770.14 951.00 -

Bouabdallah 250ms 2806.43 1 917.29 -

Laforest 500ms 2842.00 1823.14 -

750ms 2914.71 1744.71 -

Neste caso, um processo pode entrar em sua se¸c˜ao cr´ıtica com qualquer subconjunto de

recursos e com quantas c´opias desses que achar necess´ario, observando obviamente o acesso

exclusivo destes.

Nessa bateria de testes, tentou-se realizar experimentos a ﬁm de observar o comporta-

mento dos algo r itmos em diversas situa¸c˜oes existentes em ambientes de Grids, explorando

a varia¸c˜ao de parˆametros dos a lgoritmos e conﬁgura¸c˜oes l´og icas. Os principais experimen-

tos foram: varia¸c˜ao da latˆencia entre clusters, varia¸c˜ao do n´umero de tipos de recursos

dispon´ıveis, varia¸c˜ao do n´umero total de processos.

Assim como nos testes apresentados na se¸c˜ao anterior, esta seq

uˆencia de testes tem o

objetivo de veriﬁcar o comportamento e a eﬁciˆencia dos algoritmos, a partir da varia¸c˜ao

da latˆencia dos canais de comunica¸c˜ao que interligam clusters diferent es. Espera- se com

este experimento, que o algoritmo proposto seja mais eﬁciente que o algoritmo concorrente,

reduzindo o tr´afego de mensagens atrav´es de canais remotos, a partir da concentra¸c˜ao de

atendimentos locais a processos que queiram acessar a se¸c˜ao cr´ıtica.

5.3 Algoritmo Proposto vs. Bouabdallah-Laforest para M´ultiplos Recursos com M ´ultiplas Instˆancias47

Os parˆametros utilizados nesta avalia¸c˜ao s˜a o os mesmos utilizados na vers˜ao anterior

deste algoritmo. Lembrando neste caso, que os recursos podem ser de diferentes tipos,

mas cada tipo pode possuir at´e 10 c´opias de recursos, e ainda, um processo pode obter

um subconjunto de quantos tipos e c´opias de recursos ele necessitar. A distribui¸c˜ao desses

recursos pelos processos ´e deﬁnida previamente em um arquivo de entrada.

Como nos testes anteriores, os valores das latˆencias entre clusters, tamb´em, variar am

em 1ms, 250ms, 500ms e 750ms. Para os valores de latˆencias na comunica¸c˜a o local,

consideramos um tempo constante para efeito de testes de 1ms.

E importante salientar

que, os tempos α e β n˜ao s˜ao somados no tempo l´ogico, apesar de inﬂuenciarem no

resultado ﬁnal destes.

As duas estrat´egias de medi¸c˜ao de tempo, usando os dois tipos de rel´ogios, l´ogico e

f´ısico, foram utilizadas nos testes de varia¸c˜ao de latˆencia, que s˜ao a presentados a seguir.

Nos testes utilizando rel´og io s l´ogicos, cada processo sempre pede os mesmos recursos em

todas as execu¸c˜oes. Pa r a esta compara¸c˜ao, foi utilizado o Ambiente de testes 1.

Analisando a Figura 5.4(a), observa-se que o procedimento de obten¸c˜ao do Con trol

Token, apresenta resultados semelhantes ao exp erimento realizado na se¸c˜ao anterior. En-

tretanto, diferencia-se no tempo de obten¸c˜ao, que para esta generaliza¸c˜ao torna-se maior

devido a maior quantidade de recursos espalhados no sistema, o que por conseq

uˆencia

aumenta o tempo total de obten¸c˜ao dos recursos. Com a varia¸c˜a o das latˆencias entre

clusters, podemos notar que houve um crescimento mais acentuado no tempo da ﬁgura

citada, no entanto, sendo bem menor no algoritmo proposto. Isso signiﬁca que com o

aumento da latˆencia entre clusters, torna-se claro o benef´ıcio da prioriza¸c˜ao das men-

sagens locais em rela¸c˜ao `as remotas. De fato, foi o que prejudicou o resultado obtido

pelo algoritmo concorrente, que trata todos os processos indiferentemente de localiza¸c˜ao.

Como um reﬂexo do resultado anterior, vemos tamb´em na Figura 5.4(b) que o algoritmo

proposto continua sendo superior, pois ao selecionar os recursos considera a localiza¸c˜ao

destes recursos, dando preferˆencia aos recursos mais pr´oximos.

A rela¸c˜ao de mensagens trocadas entre processos remotos e locais, se mant´em como o

esperado em rela¸c˜ao `a proposta do algoritmo. Observe na Figura 5.4(d), que o n´umero de

mensagens locais trocadas pelo algoritmo proposto ´e cerca de 80% maior que o n´umero

de mensagens remotas. Observe tamb´em que o contr´ario pode ser visto nos resultados

5.3 Algoritmo Proposto vs. Bouabdallah-Laforest para M´ultiplos Recursos com M ´ultiplas Instˆancias48

5000

10000

15000

20000

25000

30000

1ms 250ms 500ms 750ms

Tempo Logico (ms)

Latencia (ms)

Variacao de Latencias

Proposto

Bouabdallah-Laforest

(a)

200

400

600

800

1000

1200

1400

1600

1ms 250ms 500ms 750ms

Tempo Logico (ms)

Latencia (ms)

Variacao de Latencias

Proposto

Bouabdallah-Laforest

(b)

5000

10000

15000

20000

25000

30000

1ms 250ms 500ms 750ms

Tempo Logico (ms)

Latencia (ms)

Variacao de Latencias

Proposto

Bouabdallah-Laforest

(c)

50000

100000

150000

200000

250000

300000

Bouabdallah-Laforest Proposto

Numero de Mensagens

Algoritmos

Locais

Remotas

Total

(d)

Figura 5.4 : Varia¸c˜ao da la tˆencia - M´ultiplos Recursos com M´ultiplas Instˆancias: (a)

M´edia do tempo l´ogico para obten¸c˜ao do Con trol Token; (b) M´edia do tempo l´ogico para

obten¸c˜ao do ´ultimo token; (c) M´edia da soma dos tempos anteriores, maior cadeia causal

para se obter acesso `a SC; e, (d) N´umero de mensagens trocadas.

do algor itmo de Bouabdallah-Laforest, onde ´e notado um aumento de 47% de mensagens

remotas a mais que as mensagens locais. Como mensagens remotas s˜ao enviadas por

canais com maior custo de comunica¸c˜ao, veriﬁcamos que quanto mais mensagens r emotas

s˜ao trocadas, maior o tempo de espera para obten¸c˜ao da se¸c˜ao cr´ıtica.

Na Figura 5.4(c), ´e mostrada a soma das m´edias dos tempos l´ogicos para se obter

acesso `a se¸c˜ao cr´ıtica. Em virtude dos bons resultados dos testes imediatamente anteriores,

essa ﬁgura reaﬁrma os resultados superiores obtidos com o algoritmo proposto.

Para o teste de tempo de obten¸c˜ao utilizando rel´ogio f´ısico, tamb´em foi utilizado o Am-

biente de testes 1.

5.3 Algoritmo Proposto vs. Bouabdallah-Laforest para M´ultiplos Recursos com M ´ultiplas Instˆancias49

Os resultados que podem ser visualizados na Figura 5.5, atestam que o algoritmo pro-

posto tamb´em se manteve superior ao concorrente utilizando tempo f´ısico como estrat´egia

de medi¸c˜ao, assim como observado nos resultados obtidos no teste com rel´og ios l´ogicos.

Como visto nos testes anteriores, o menor consumo de canais remotos no algo ritmo pro-

posto, resultou em uma curva de tempo de obten¸c˜ao `a se¸c˜ao cr´ıtica menos acentuada do

que a mesma observada no algoritmo concorrente.

Assim como no teste realizado na se¸c˜ao anterior, usando a ferramenta NetEm, os resul-

tados apresentados na Figura 5.6 tamb´em se aproximam bastante dos resultados obtidos

com os outros testes que usam outras f ormas de medi¸c˜ao de desempenho. Essencialmente,

a mudan¸ca mais not´avel est´a relacionada ao s tempos obtidos, que s˜ao menores visto que

para este experimento foi utilizado o Ambiente de testes 2, que possui 24 processa-

dores. No entanto , a estrat´egia da utiliza¸c˜ao da ferramenta NetEm foi de atestar que o

comportamento do algoritmo se mant´em similar usando-se diferentes formas de medi¸c˜ao,

o que foi conseguido.

160

180

200

220

240

260

280

300

320

340

1ms 250ms 500ms 750ms

Tempo de Obtencao (s)

Latencia (ms)

Variacao de Latencias

Proposto

Bouabdallah-Laforest

Figura 5.5: Tempo de Obten¸c˜ao - Tempo F´ısico usando Sleep - M´ultiplos Recursos com

M´ultiplas Instˆancias

100

105

110

115

1ms 250ms 500ms 750ms

Tempo de Obtencao (s)

Latencia (ms)

Variacao de Latencias

Proposto

Bouabdallah-Laforest

Figura 5.6: Tempo de Obten¸c˜ao - Tempo F´ısico usando NetEm - M´ultiplos Recursos com

M´ultiplas Instˆancias

5.3 Algoritmo Proposto vs. Bouabdallah-Laforest para M´ultiplos Recursos com M ´ultiplas Instˆancias50

Tabela 5.3: Tabela de M´edias e Desvio Padr˜ao - Varia¸c˜ao de Latˆencias - M´ultiplos

Recursos com M´ultiplas Instˆancias

Algoritmos Latˆencias(ms) Rel´ogio F´ısico(s) Rel´ogio L´o gico(ms)

M´edia Desv. Pad (%) M´edia Desv. Pad (%)

1ms 16 1.94 4.63 50.57 0.65

Algoritmo 250ms 167.07 4.63 750.79 1.03

Proposto 500ms 177.79 4.63 1456.71 1.02

750ms 189.91 4.47 2169.25 1.06

1ms 20 0.47 3.12 52.17 0.59

Bouabdallah 250ms 237.47 3.27 9083.19 0.80

Laforest 500ms 286.26 4.35 17626.63 0.95

750ms 337.44 3.90 26768.14 0.79

Tabela 5.4: Tabel a do N´umero de Mensag ens Trocadas - Varia¸c˜ao de Latˆencias -

M´ultiplos Recursos com M´ultiplas Instˆancias

Algoritmos Latˆencias(ms) N´umero de Mensagens Preemp¸c˜oes

Remotas Locais

1ms 1 043.00 5276.33 88

Algoritmo 250ms 1053.33 5299.22 91

Proposto 500ms 1063.11 52 74.00 92

750ms 1055.22 5284.44 93

1ms 5 385.78 1779.00 -

Bouabdallah 250ms 4530.67 2 694.00 -

Laforest 500ms 4462.33 2768.22 -

750ms 4497.22 2724.11 -

Os tempos m´edios de obten¸c˜ao e o desvio padr˜ao, obtidos a partir da varia¸c˜ao de

latˆencias, s˜ao apresentados na Tabela 5.3. Estes r esultados mostram que os valores do

tempo de obten¸c˜ao usando o algoritmo Boubdallah-Laforest s˜ao muito maiores do que

usando o algoritmo proposto, tanto usando rel´ogios l´ogicos, quanto usando rel´ogios f´ısicos.

Por´em, utilizando rel´ogios de tempo f´ısico, o tempo m´edio de obten¸c˜ao do algoritmo

proposto foi em torno de 56% do algoritmo concorrente, quando a latˆencia entre clusters

ﬁcou em 750ms. Observa-se que n˜ao houve uma varia¸c˜ao not´avel nos valores de desvio

padr˜ao, para ambo s os testes.

Detalhadamente, podemos ver o n´umero de mensagens trocadas pelos algoritmos na

Tabela 5.4. Veja que, a concentra¸c˜a o das mensagens locais feita pelo algoritmo proposto

´e bem deﬁnida aqui. Isso mostra que, a estrat´egia adotada foi eﬁcient e e resultou na

redu¸c˜ao do tempo de obten¸c˜ao da se¸c˜ao cr´ıtica. O n´umero de preemp¸c˜oes ´e sumarizado

nesta ´ultima tabela, onde o valor assemelha-se com o resultado obtido na primeira parte

dos testes.

5.3 Algoritmo Proposto vs. Bouabdallah-Laforest para M´ultiplos Recursos com M ´ultiplas Instˆancias51

O objetivo deste experimento ´e avaliar o comportamento dos algoritmos envolvidos neste

trabalho, a partir da varia¸c˜ao do n´umero de tipos de recursos dispon´ıveis. A quantidade

de tipo s de recursos variou em 01, 05, 10 e 20. Neste teste, cada processo solicitou

um subconjunto aleat´orio destes recursos para entra r em sua se¸c˜ao cr´ıtica. Atribu´ımos

tamb´em, para cada recurso, um total de 10 instˆancias. Assim, um processo tamb´em pode

solicitar mais de uma c´opia de um mesmo tip o de recurso. Os parˆametros utilizados neste

teste foram deﬁnidos como: β em 500ms, α em 500ms e a latˆencia entre clusters tamb´em

em 500ms. O limite de preemp¸c˜ao fo i deﬁnido com valor de 08.

Para o teste a seguir, foi utilizada somente a medi¸c˜ao de tempo por rel´ogio f´ısico,

sendo este, executado no Ambiente de testes 1.

Analisando a Figura 5.7, ´e poss´ıvel veriﬁcar que o algoritmo proposto conseguiu r eduzir

o tempo de obten¸c˜ao, mesmo com o aumento da varia¸c˜ao de t ipos de recursos. O ponto

de maior eﬁciˆencia observada foi quando a quantidade de tipos de recursos ﬁcou entre 05

e 20, uma vez que ´e quando os recursos ﬁcam mais espalhados pelo sistema. Neste caso, o

algoritmo proposto conseguiu selecionar melhor estes recursos, agrupando-os em pedidos

e gastando menos mensagens, al´em de ter dado maior prioridade a pedidos locais. Not e

que essa estrat´egia mostrou uma diferen¸ca contra o algoritmo de Bouabdallah-Laforest,

que n˜ao possui uma estrat´egia de sele¸c˜ao adequada. Veja tamb´em, que mesmo quando

o n´umero recursos ´e ig ua l a 01, o algoritmo proposto a inda consegue ter um resultado

melhor que o concorrente.

100

150

200

250

300

350

400

01 05 10 20

Tempo de Obtencao (s)

Num. Tipos de Recursos

Variacao de Tipos de Recursos

Proposto

Bouabdallah-Laforest

Figura 5.7: Tempo de Obten¸c˜ao - Teste de varia¸c˜ao do n ´umero de tipos de recursos -

M´ultiplos Recursos com M´ultiplas Instˆancias

Na Tabela 5.5, podemos ver os valores m´edios dos tempos de obten¸c˜ao `a se¸c˜ao cr´ıtica,

juntamente com o desvio padr˜ao de cada valor obtido. Note que o s valores de desvio

5.3 Algoritmo Proposto vs. Bouabdallah-Laforest para M´ultiplos Recursos com M ´ultiplas Instˆancias52

Tabela 5.5: Tabe l a de M´edias e Desvio Padr˜ao - Varia¸c˜ao do N´umero de Tipos de

Recursos - M´ultiplos Recursos co m M´ultiplas Instˆancias

Algoritmos N´um. de Tipos Tempo de Obten¸c˜ao(s) N´um. de Mensagens

de Recursos M´edia Desv. Pad (%) Globais Locais

01 58.04 19.19 160.40 2834.0 0

Algoritmo 05 146.97 5.49 659.40 5 382.60

Proposto 10 173.17 4.75 972.80 5915.40

20 199.02 5.00 1344.40 6387.00

01 87.86 13.97 1410.00 786.40

Bouabdallah 05 217.56 6.19 3565.80 2025.60

Laforest 10 287.61 3.35 4572.80 2675.00

20 361.30 3.40 5751.20 3337.40

padr˜ao foram pr´oximos, com exce¸c˜ao do valor obtido quando o n´umero de tipo s de recursos

foi de apenas 01. Neste caso, como havia somente um tipo de recurso com 10 instˆancias

cada, esses recursos n˜ao puderam ser espalhados pelo sistema. Assim, alguns processos

conseguiram obter todos seus recursos localmente, enquanto outros tiveram que realizar

seus pedidos remotamente, o que gerou uma discrepˆancia nas m´edias do tempo de obten¸c˜ao

de todas as varia¸c˜oes, resultando em um desvio padr˜ao um pouco mais alto .

O experimento a seguir foi feito com intuito de medir a escalabilidade e a eﬁciˆencia dos

algoritmos a partir do crescimento do n´umero de processos.

Neste teste, variou-se o n´umero de processos em 12, 24, 48 e 60. Em todos os casos,

os pro cessos foram divididos igualmente entre 3 clusters. Assim, cada cluster recebeu

a mesma quantidade de processos. Os parˆametros α e β, receberam ambos 500ms. A

latˆencia dos canais de comunica¸c˜ao que interligam os clusters foi ﬁxada em 500 ms. No

parˆametro que limita o n´umero de preemp¸c˜oes, foi utilizado um valor correspondente `a

50% do n´umero de processos que compuseram cada cluster em cada varia¸c˜ao. Foram

utilizados 10 tipos de recursos distintos, com 10 instˆancias cada.

O teste foi executado no Ambiente de testes 1 usando apenas rel´ogio de tempo

f´ısico.

O crescimento do n´umero de processos, resultou em um aumento dos t empos m´edios

para obten¸c˜ao da se¸c˜ao cr´ıtica, como pode ser visto na Figura 5.8. Note no gr´aﬁco que

ambo s os algoritmos apresentaram um crescimento acentuado, entretanto, o crescimento

observado na curva do gr´aﬁco que representa o algoritmo proposto, tende a ser menor

que no algoritmo de Bouabdallah-Laforest, considerando-se o aumento maior do n´umero

5.3 Algoritmo Proposto vs. Bouabdallah-Laforest para M´ultiplos Recursos com M ´ultiplas Instˆancias53

de processos. Analisando o s resultados obtidos, podemos perceber que com o aumento

do n´umero de processos, aumenta-se tamb´em a cadeia de espera de cada processo que

aguarda para obter os recursos em comum.

Os valores das m´edias e desvio padr˜ao podem ser observados na Tabela 5.6, onde os

valores de desvio padr˜a o para os algoritmos n˜a o possuem grande varia¸c˜ao.

Na Tabela 5.6 , tamb´em podemos ter um resultado mais detalhado acerca da troca

de mensagens. Nessa tabela, ´e poss´ıvel ver o s valores de mensagens para cada varia¸c˜ao

diferente. Neste caso, observe que `a medida que o n´umero de processos aumentou, houve

tamb´em um aumento da diferen¸ca entre mensagens remotas e locais. Veja que quando

foram utilizados 12 processos concorrentes, a diferen¸ca de mensagens n˜ao foi t˜ao signiﬁca-

tiva para o algoritmo proposto. Por´em, com o a umento do n ´umero de processos, observe

que essa diferen¸ca foi se tornando mais evidente, pois o n´umero de mensagens remotas foi

diminuindo em rela¸c˜ao `as locais. Basicamente o contr´ario foi observado para o algoritmo

de Bouabdallah-Laforest. O n´umero de preemp¸c˜oes obtido variou de acordo com o cresci-

mento do n´umero de processos, cujo limite de preemp¸c˜oes tamb´em variou de acordo com

o n´umero de processos.

100

150

200

250

300

350

400

12 24 48 60

Tempo de Obtencao (s)

Num. de Processos

Variacao de Processos

Proposto

Bouabdallah-Laforest

Figura 5.8: Tempo de Obten¸c˜ao - Teste de varia¸c˜ao do n´umero de total de processos -

M´ultiplos Recursos com M´ultiplas Instˆancias

O teste a seguir, tem o objetivo de avaliar o comportamento dos algoritmos com a varia¸c˜ao

do n´umero de clusters no ambiente Grid. O n´umero de clusters variou nesse teste, em

01, 03, 06 e 12. Nessa varia¸c˜ao, cada cluster recebeu partes iguais do n´umero total de

processadores, no caso 48. Os parˆametros utilizados neste teste f oram deﬁnidos como:

β em 500ms, α em 500ms e a latˆencia entre clusters tamb´em em 500ms. No parˆametro

5.3 Algoritmo Proposto vs. Bouabdallah-Laforest para M´ultiplos Recursos com M ´ultiplas Instˆancias54

Tabela 5.6: Tabela de M´edias e Desvio Padr˜ao - Varia¸c˜ao do N´umero de Processos

- M´ultiplos Recursos com M´ultiplas Instˆancias

Algoritmos N´um. de Tempo de Obten¸c˜ao(s) N´um. de Mensagens Preemp¸c˜oes

Processos M´edia Desv. Pad (%) Globais Locais

12 53.27 2.79 690.00 846.00 50

Algoritmo 24 95.36 4.57 869.00 22 96.00 52

Proposto 4 8 179.88 3.55 1027.00 5368.00 95

60 217.12 4.64 1 021.00 6866.00 120

12 73.26 2.51 1329.00 376.00 -

Bouabdallah 24 152.65 2.63 2787.00 794.00 -

Laforest 48 307.35 2.70 5647.00 1648.0 0 -

60 379.66 2.69 6 854.00 2287.00 -

de limite de preemp¸c˜oes, foi atribu´ıdo um valor correspondente `a 50% do n´umero de

processos que compuseram cada cluster em cada varia¸c˜ao. Foram utilizados 10 tipos de

recursos com 10 instˆancias cada.

O a mbiente de t estes utilizado, f oi o Ambiente de testes 1, tamb´em foi utilizado

apenas o rel´ogio de tempo f´ısico para a medi¸c˜ao de desempenho.

O crescimento do n´umero de clusters, faz com que a quantidade de processos distri-

bu´ıdos para cada cluster seja menor. Assim, esse ambiente obriga os processos a trocarem

um maior n´umero de mensagens remotas, p ois neste caso, muitos pedidos s˜ao feitos para

processos remotos. O resultado deste teste pode ser visto na Figura 5.9. Observe que o al-

goritmo de Bouabdallah-Laforest foi consideravelmente mais ineﬁciente do que o algoritmo

proposto, este ´ultimo que manteve um tempo linear enquanto o algoritmo comparado che-

gou a dobrar o tempo de obten¸c˜ao, no teste usando 12 clusters. Isso se deu, devido ao

fato do algo r itmo de Bouabdallah-Laforest n˜ao fazer distin¸c˜ao entre processos remotos ou

locais. Al´em disso, a etapa de inicializa¸c˜ao deste algoritmo obriga todos os processos a

solicitarem o Control Token sempre a um mesmo processo, com o aumento do n´umero

de clusters e conseq

uentemente o n´umero de canais remotos, esse procedimento gera um

overhead alto na comunica¸c˜ao de todos os processos para este ´unico processo. J´a no caso

do algoritmo proposto, ´e poss´ıvel ver uma clara estabilidade nas m´edias dos t empos de

obten¸c˜ao. Isso foi poss´ıvel, gra¸cas `as estrat´egias adotadas tanto na etapa de obten¸c˜a o

do Control Token, quanto na etapa de obten¸c˜ao dos recursos. A etapa de inicializa¸c˜ao

utilizada no algoritmo proposto tamb´em foi imp ortante, pois faz com que os processos

sempre fa¸cam pedidos inicialmente a um n´o l´ıder, que ´e local. Al´em disso, na etapa de

pedidos de recursos, ´e feita uma sele¸c˜ao dos recursos, onde recursos locais possuem maior

preferˆencia.

Na Tabela 5.7, podemos ver os valores do resultado obtido na ﬁgura anterior. Ob-

5.3 Algoritmo Proposto vs. Bouabdallah-Laforest para M´ultiplos Recursos com M ´ultiplas Instˆancias55

160

180

200

220

240

260

280

300

320

340

360

01 03 06 12

Tempo de Obtencao (s)

Num. de Clusters

Variacao de Clusters

Proposto

Bouabdallah-Laforest

Figura 5.9: Tempo de Obten¸c˜ao - Teste de varia¸c˜ao do n´umero de clusters - M´ultiplos

Recursos com M´ultiplas Instˆancias

Tabela 5.7: Tabel a d e M´edias e Desv i o Padr˜ao - Varia¸c˜ao do N´umero de Clusters

- M´ultiplos Recursos com M´ultiplas Instˆancias

Algoritm os N´um. de Tempo de Obten¸c˜ao(s) N´um. de Mensagens Preemp¸c˜oes

Clusters M´edia Desv. Pad (%) Globais Locais

01 168.62 3.54 0.00 8137.25 0.00

Algoritmo 03 171.50 4.54 961.75 6029.75 92.75

Proposto 06 174.77 13.41 1674.25 5162.00 151.00

12 174.58 12.54 2304.75 4136.00 214.75

01 193.89 3.28 0.00 7192.75 -

Bouabdallah 03 293.55 3.42 4815.00 2399.50 -

Laforest 06 332.84 3.18 6347.00 905.75 -

12 346.96 3.04 6923.00 302.75 -

serve que, quando se utilizou apenas 01 cl uster, n˜ao houve nenhuma preemp¸c˜ao visto que

tamb´em n˜a o havia nenhum processo remoto. Por outro lado, quando o n´umero de cluster

foi de 12, o n´umero de preemp¸c˜oes foi mais que o dobro em rela¸c˜ao ao teste com 3 clus-

ter. Note tamb´em que os valores de desvio padr˜ao par a o algoritmo proposto ﬁcaram um

pouco mais altos, quando o n´umero de clusters foi de 06 e 12. Com o aumento do n´umero

de clusters, aumentou-se tamb´em o n´umero de canais remotos, e conseq

uentemente, o

custo da cadeia de espera par a se obter acesso `a se¸c˜ao cr´ıtica. Isso fez com que houvesse

uma varia¸c˜ao maior nas m´edias dos tempos de obten¸c˜ao, resultando em um desvio padr˜ao

maior para estes valores.

O trabalho teve como objetivo propor um algo ritmo para resolver o problema da alo-

ca¸c˜ao de m´ultiplos recursos com m´ultiplas instˆancias, que considerasse a heterogeneidade

de latˆencia na comunica¸c˜ao em um a mbiente de Grid. O algoritmo proposto foi comparado

com o algoritmo de Bouabdallah-Laforest [9].

Para a avalia¸c˜ao destes algoritmos, tamb´em foi proposto um rel´ogio l´ogico utilizado

para medir o tempo de espera para um processo obter o C ontrol Tok en e tamb´em os tokens

dos recursos, e conseq

uentemente entrar em sua se¸c˜ao cr´ıtica. Tal rel´ogio l´ogico considera

as diferen¸cas de latˆencias nos canais de comunica¸c˜ao. O modelo de rel´ogio l´ogico utilizado

tamb´em mostrou ser muito ´util, e pode ser empregado na avalia¸c˜ao de desempenho em

diversos o utros tipos de experimentos.

Os testes foram repetidos considerando tamb´em o tempo medido utilizando rel´ogio de

parede, sendo que para isso, foram utilizadas duas estrat´egias diferentes para emular uma

infra-estrutura de Grid.

Os resultados obtidos por estas diferentes formas de avalia¸c˜ao foram bastante se-

melhantes, e atestou que o algoritmo proposto ´e mais eﬁciente do que o algoritmo de

Bouabdallah-Laforest [9] utilizado na compara¸c˜ao.

Por ﬁm, a redu¸c˜ao das mensagens entre clusters e do tempo de espera para entrar

na se¸c˜ao cr´ıtica mostrou que o algoritmo proposto ´e bastante atraente para ambientes

heterogˆeneos tais como Grids Computacionais.

Para trabalhos futuros, sugerimos uma adapta¸c˜ao do algoritmo proposto adicionando

um mecanismo de tolerˆancia a falhas, utilizando alguns conceitos apresentados em [53,

54, 3], os quais acreditamos poder ser facilmente incorporados ao algoritmo proposto de-

6 Conclus˜oes e Trabalhos Futuros 57

vido `a proximidade das t´ecnicas utilizadas por eles. Uma outra sugest˜ao ´e a utiliza¸c˜ao de

algoritmos mais eﬁcientes na sele¸c˜ao dos recursos em conjunto com o algoritmo proposto.

Observamos que no momento no qual o processo obt´em a estrutura do Control Token, ele

possui ali todas as informa¸c˜o es necess´arias para uma escolha mais otimizada dos recursos.

Al´em disso, algoritmos especializados em sele¸c˜ao de recursos tamb´em podem utilizar ou-

tros crit´erios para uma sele¸c˜ao mais adequada desses recursos, como por exemplo o tempo

de utiliza¸c˜ao daquele recurso.

[1] http://www.linux-foundation.org/en/Net:Netem. [Acesso feito em: 2008.03.19 ].

[2] http://www.linux-foundation.org/en/Net:Iproute2. [Acesso feito em:

2008.03.19].

[3] Agrawal, D. e Abbadi, A. E. A token-based f ault-tolerant distributed mutual

exclusion algorithm. Journal of Parallel and Distributed Computing 24, 2 (1995),

164–176.

[4] Ahamad, M., Ammar, M. H. e Cheung, S. Y. Multidimensional voting. ACM

Transactions on C omputer Systems 9, 4 (1991), 399–431.

[5] Barbara, D., Garcia-Molina, H. e Spauster, A. Increasing availability under

mutual exclusion constraints with dynamic vote reassignment. ACM Transactions

on Computer Systems 7, 4 (1989), 394–426.

[6] Barbosa, V. C. An in troduction to distributed algorithms. MIT Press, Cambridge,

MA, USA, 1996.

[7] Bertier, M., Arantes, L. e Sens, P. Hierarchical token based mutual exclusion

algorithms. Em CCGRID’04: Proceedings of the 2004 IEEE International Symposium

on Cluster Computing and the Grid (Washington, DC, USA, 2004), IEEE Computer

Society, pp. 539–546.

[8] Bertier, M., Arantes, L. e Sens, P. Distributed mutual exclusion algorithms for

grid applications: a hierarchical approach. JPDC: Journal of Parall el and Distributed

Computing 66, 1 (2006), 128–144.

[9] Bouabdallah, A. e Laforest, C. A distributed token-based algorithm for the dy-

namic resource allocation problem. SIGOPS Operating Systems Review 34, 3 (2000),

60–68.

[10] Bulgannawar, S. e Vaidya, N. H. A distributed k-mutual exclusion algo-

rithm. Em ICDCS ’95: Proceedings of the 15th International Conf erence on Distri-

buted Computing Systems (Washington, DC, USA, 1 995), IEEE Computer Society,

pp. 153–160 .

[11] Cantarell, S., Datta, A. K., Petit, F. e Villain, V. Token based gro up

mutual exclusion for asynchronous rings (extended abstract). Em ICD CS ’ 01: Pro-

ceedings of the The 21st International Conference on Distributed Computing Systems

(Washington, DC, USA, 2001), IEEE Computer Society, p. 691.

Referˆencias 59

[12] CERN. Large hadron collider, glo bal grid service for lhc computing suc-

ceeds in gigabyte-per-second challenge. http://press.web.cern.ch/Press/

PressReleases/Releases2006/PR03.06E.html, 2006. [Acesso feito em: 2007 .1 1.07].

[13] Chang, Y.-I. A simulation study on distributed mutual exclusion. JPDC: Journal

of Parallel and Distributed Computing 33, 2 (1996), 107–121 .

[14] Chang, Y.-I., Singhal, M. e Liu, M. A hybrid approa ch to mutual exclusion for

distributed systems. Computer Software and Applications Conference, COMPSAC

90 (1990), 289–294 .

[15] Chang, Y.-I., Singhal, M. e Liu, M. T. A fa ult tolerant algorithm for distri-

buted mutual exclusion. Em Proceedings Ninth Symposium on Reliable Distributed

Systems (9th SRDS’90) (Huntsville, Alabama, USA, outubro de 1990), IEEE Com-

puter Society Press, pp. 146–154.

[16] Chang, Y.-I., Singhal, M. e Liu, M. T. An improved O(logn) mutual exclusion

algorithm for distributed systems. Em ICPP International Conference on Parallel

Processing (1990), pp. 295–30 2.

[17] DeMent, N. S. e Srimani, P. K. A new algorithm for mutual exclusions in

distributed systems. Journal of Systems and Software 26, 2 (1994), 179–191.

[18] Drummond, L. M. A. e Barbosa, V. C. On reducing the complexity of matrix

clocks. Parallel Computing 29, 7 (julho de 2003), 895–905.

[19] Erciyes, K. Distributed mutual exclusion algorithms on a ring of clusters. Em

Computational Science and Its Applications - ICCSA 2004, International Confe rence

(2004), A. Lagan`a, M. L. Gavrilova, V. Kumar, Y. Mun, C. J. K. Ta n, e O. Gervasi,

Eds., vol. 3045 of Lecture Notes in Computer Science, Springer, pp. 518–527.

[20] Fidge, C. J. Timestamps in message-passing systems that preserve the partial

ordering. Em Proc. 11th Australian Computer Science Conference (1988), pp. 56–66.

[21] Garcia-Molina, H. e Barbara, D. How to assign votes in a distributed system.

JACM: Journal of the ACM 32, 4 (1985), 841–860.

[22] Gifford, D. K. Weighted voting for replicated data. Em SOSP ’79: Proceedings of

the seventh ACM symposium on Operating systems prin ciples (New York, NY, USA,

1979), ACM, pp. 150–162.

[23] Han, H., Jung, H., Yeom, H. Y., Kweon, H. S. e Lee, J. HVEM g r id: Expe-

riences in constructing an electron microscopy grid. Em Frontiers of WWW Research

and Development - APWeb 2006, 8th Asia-Paciﬁc Web Conference , Harbin, China,

January 16-18, 2006, Proceedings (2006), X. Zhou, J. Li, H. T. Shen, M. Kitsure-

gawa, e Y. Zhang, Eds., vol. 3841 of Lecture Notes in Computer Science, Springer,

pp. 1159–11 62.

[24] Helary, J. M., Plouzeau, N. e Raynal, M. A distributed algorithm for mutual

exclusion in an arbitrary network. The Computer Journal. 31, 4 (1988), 289–295.

[25] Hemminger, S. Network emulation with netem. Tech report, Open Source Deve-

lopment lab, 4 2005. [Acesso feito em: 20 08.03.19].

Referˆencias 60

[26] Housni, A. e Trehel, M. Distributed mutual exclusion token-permission based

by prioritized groups. Computer Systems and Applications, ACS/IEEE International

Conference (200 1), 253–259.

[27] Jajodia, S. e Mutchler, D. Dynamic voting algo r ithms for maintaining the

consistency of a replicated database. ACM Transactions on Database Systems 15, 2

(1990), 230–280.

[28] Kakugawa, H. A Study on Distributed k-Mutual Exclusion Algorithms. Tese de

Mestrado, Hiroshima University, Feb. 1995.

[29] Kakugawa, H., Fujita, S., Yamashita, M. e Ae, T. A distributed k-mutual

exclusion algorithm using k-coterie. Information Processin g Letters 49, 4 (1994 ) ,

213–218.

[30] Lamport, L. Time, clocks, and the ordering of events in a distributed system.

Communications of the ACM 21, 7 (1978), 558–565.

[31] Lann, G. L. Distributed systems – toward a formal approach. Em Proceedings of

the IFIP Congress 77 (1977), pp. 155–160.

[32] Liu, C., Yang, L., Foster, I. e Angulo, D. Design and evaluation of a re-

source selection framework for grid applications. Em HPDC ’02: Proceedings of the

11th IEEE International Symposium on High Performance Distributed Computing

(Washington, DC, USA, 2002), IEEE Computer Society, pp. 63–72.

[33] Maddi, A. Token based solutions to M resources allocation problem. Em SAC ’97:

Proceed i ngs of the 1997 ACM symposium o n Applied computing (New York, NY,

USA, 1997), ACM, pp. 340–344.

[34] Maekawa, M. A O

√

N algorithm for mutual exclusion in decentralized systems.

ACM Transactions on Co mputer Systems 3, 2 (1985), 145–159.

[35] Mattern, F. Virtual time and global states of distributed systems. Em Proc.

Workshop on Parallel and Distributed Algorithms (North-Holland / Elsevier, 1989),

C. M. et al., Ed., pp. 215–226. (Reprinted in: Z. Yang, T.A. Marsland (Eds.), ”Global

States and Time in Distributed Systems”, IEEE, 1994, pp. 123-133.).

[36] Naimi, M. Distributed algorithm for k-entries to critical section based on the directed

graphs. SIGOPS Operating Systems Review 27, 4 (1993), 67–75.

[37] Naimi, M. e Trehel, M. An improvement of the log(n) distributed algorithm for

mutual exclusion. Em ICDCS: 7th International Conference on Distributed Compu-

ting Systems (Berlin, Germany, 1987), pp. 156–172.

[38] Naimi, M., Trehel, M. e Arnold, A. A log (n) distributed mutual exclusion

algorithm based on pat h reversal. JPDC: Journal of Pa rallel and D i s tributed Com-

puting 34, 1 (1996), 1–13.

[39] Nassif, L. N., Nogueira, J. M. e de Andrade, F. V. Distributed resource

selection in g r id using decision theory. Em CCGRID ’07: Proceedin gs of the Seventh

IEEE International Symposium on Cluster Computing and the Grid (Washington,

DC, USA, 2007), IEEE Computer Society, pp. 327–3 34.

Referˆencias 61

[40] Neilsen, M. L. e Mizuno, M. A dag-based algorithm for distributed mutual exclu-

sion. Em Proceedings of the 11th In terna tion al Conference on Distributed Computing

Systems (ICDCS) (Washington, DC, 1991), IEEE Computer Society, pp. 354–360.

[41] Nielsen, M. L. e Mizuno, M. Coterie join algorithm. IEEE Transactions on

Parallel and Distributed Systems 3, 5 (1992), 582–590.

[42] Nishio, S., Li, K. e Manning, E. A resilient mutual exclusion algor ithm for

computer networks. IEEE Transactions on Parallel and Distributed Systems 01, 3

(1990), 344–356.

[43] Raymond, K. A distributed algorithm fo r multiple entries to a critical section. IPL:

Information Processing Letters 30, 4 (198 9), 189–193.

[44] Raymond, K. A distributed algorithm fo r multiple entries to a critical section. IPL:

Information Processing Letters 30, 4 (198 9), 189–193.

[45] Raymond, K. A tree-based algorithm for distributed mutual exclusion. ACM

Transactions on C omputer Systems 7, 1 (1989), 61–77.

[46] Raynal, M. A distributed solution to the k-out of-M resources allocation problem.

Lecture Notes in Computer Science 497 (1991), 599–609.

[47] Raynal, M. A simple taxonomy for distributed mutual exclusion algorithms. SI-

GOPS Operating Systems Review 25, 2 (1991), 47–50.

[48] Ricart, G. e Agrawala, A. K. An optimal algorithm for mutual exclusion in

computer networks. Communications of the ACM 24, 1 (1981), 9–17.

[49] Saxena, P. C. e Rai, J. A survey of permission-based distributed mutual exclusion

algorithms. Computer Standards & Interfaces 25, 2 (2003), 159–181.

[50] Singhal, M. A heuristically-aided algorithm for mutual exclusion in distributed

systems. IEEE Tran s actions on Computers 38, 5 (1989 ) , 651–6 62.

[51] Singhal, M. A dynamic infor matio n-structure mutual exclusion algorithm for dis-

tributed systems. IEEE Transactions on Pa rallel and Distributed Systems 3, 1 (1992),

121–125.

[52] Singhal, M. A taxonomy of distributed mutual exclusion. JPDC: Journal of

Parallel and Distributed Computing 18, 1 (1993), 94–101.

[53] Sopena, J., Arantes, L. e Sens, P. Perfo r mance evaluation of a fair fault-

tolerant mutual exclusion algorithm. Em SRDS ’06 : Proceedings of the 25th IEEE

Symposium on Reliable Distributed Systems (Washington, DC, USA, 2006), IEEE

Computer Society, pp. 225–234.

[54] Sopena, J., Arantes, L. B., Bertier, M. e Sens, P. A fault-tolerant token-

based mutual exclusion algor ithm using a dynamic tree. Em Euro-Par 2005, Pa rallel

Processing, 11th Internationa l Euro-Par Confe rence (Lisbon, Portugal, agosto de-

setembro de 2005), J. C. Cunha e P. D. Medeiros, Eds., vol. 3648 of Lecture Notes in

Computer Science ( LNCS) , Springer-Verlag (New York), pp. 654 –663.

Referˆencias 62

[55] Sopena, J., Legond-Aubry, F., Arantes, L. e Sens, P. A composition appro-

ach to mutual exclusion algorithms for grid applications. Em ICPP ’07: Proceedings

of the 2007 International Conference on Parallel Processing (Washington, DC, USA,

2007), IEEE Computer Society, p. 65.

[56] Srimani, P.K.; Reddy, R. A new a lg orithm for simultaneous multiple entries in

critical section in a distributed system. Em Comp uters and Communications , 1990.

Conference Proceedings., Ninth Annual International Phoenix Conference on (1990),

p. 895.

[57] Suzuki, I. e Kasami, T. A distributed mutual exclusion algorithm. ACM Tran-

sactions on Computer Systems 3, 4 (1985), 344–349.

[58] Thomas, R. H. A majority consensus a pproa ch to concurrency control for multiple

copy databases. ACM Transactions on Database S ystems 4, 2 (1979), 180–209.

[59] van de Snepscheut, J. L. A. Fair mutual exclusion on a graph of processes.

Distributed C omputing 2, 2 (1987), 113–115.

[60] Wang, S. e Lang, S. D. A tree-based distributed alg orithm for the K-entry critical

section problem. Em ICPADS: Proceedings 1994 I nternational Conference on Parallel

and Distributed Systems (19 94), L. M. Ni, Ed., IEEE Computer Society, pp. 592–59 9.

[61] Yan, Y., Zhang, X. e Yang, H. A fast token-chasing mutual exclusion algo-

rithm in arbitrary network topologies. JPDC: Journal of Parallel and Distributed

Computing 35, 2 (1996), 156–172.

Livros Grátis
( http://www.livrosgratis.com.br )
 
Milhares de Livros para Download:
 
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas

Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
 
 