IEEE LATIN AMERICA TRANSACTIONS, VOL. 4, NO. 5, SEPTEMBER 2006 373 Modelo de Migração baseado na Avaliação da Carga e Tempo de Vida de Processos em Ambientes Distribuídos Heterogêneos Rodrigo Fernandes de Mello e Luciano José Senger Resumo—Este artigo apresenta um modelo para quantificar impactos na migração de processos em ambientes compostos por computadores de capacidade heterogênea. Esse modelo é composto por equações que resultam em um fator de migração. Esse fator reflete quanto um computador sobrecarregado será aliviado e quanto um computador receptor tornar-se-á carregado em função da migração de processos. Esse fator é utilizado para compor uma heurística de migração de processos como objetivo de balancear a carga no ambiente. Resultados experimentais permitem comprovar as contribuições desse modelo em relação a outros trabalhos relacionados. Essas contribuições referem-se à queda no tempo de resposta dos processos, ou seja, a otimização do desempenho. Palavras chave—migração de processos, balanceamento de carga, computação de alto desempenho. I. INTRODUÇÃO A disponibilidade de microprocessadores de baixo custo e a evolução das redes de computadores viabiliza economicamente o desenvolvimento de sistemas distribuídos baseados em multicomputadores de memória distribuída [1]. Nesses sistemas os processos executam sobre os computadores de uma rede, comunicando-se para a realização de um mesmo trabalho computacional. A distribuição desses processos pode ser feita de forma manual ou automática, por meio de um algoritmo de balanceamento de carga. Esses algoritmos buscam distribuir, de forma eqüitativa, a carga entre todos os computadores do sistema. Krueger e Livny [6] demonstram que os métodos de balanceamento de carga reduzem as médias e desvios padrão dos tempos de resposta dos processos. Baixos tempos de resposta compreendem menor tempo de execução de processos e, conseqüentemente, maior desempenho. Algoritmos de balanceamento de carga são compostos pelas políticas de: transferência, seleção, localização e informação [9], [12]. A política de transferência classifica um computador como emissor ou receptor de processos de acordo com sua Recebido em 2006-07-27 Rodrigo Fernandes de Mello: Universidade de São Paulo. Instituto de Ciências Matemáticas e de Computação. Caixa Postal 668. 13560-970~~São Carlos -- SP. [email protected]. Luciano José Senger: Universidade Estadual de Ponta Grossa. Departamento de Informática. Av. Carlos Cavalcanti, 4748. 84030900~~Ponta Grossa -- PR. [email protected]. ocupação. A política de seleção define o processo que deve ser transferido do computador mais ocupado para o mais ocioso. A política de localização define qual computador deve receber ou enviar processos. Um computador servidor ou emissor oferece processos, pois está sobrecarregado; um computador receptor requer processos, pois está ocioso. A política de informação define quando e como as informações sobre a ocupação dos computadores são atualizadas no sistema. Essas informações são utilizadas pela política de localização. Diversos trabalhos sobre balanceamento de carga foram realizados tanto para ambientes compostos por computadores de capacidade homogênea [5], [10], [12] quanto heterogênea [7], contudo eles não avaliam custos de migração de processos. Esses custos são relacionados às operações de transferência do estado de processos sobre a rede de comunicação e ao reestabelecimento de seus canais de comunicação (tais como arquivos abertos, sockets etc). Tais custos tornam-se mais significativos conforme há aumento na carga de comunicação. Essa situação é comum tratando-se de aplicações paralelas. A migração de processos pode causar perda de desempenho do sistema em casos onde não é realizada uma análise da situação de carga dos computadores. Essa situação se agrava quando processos são transferidos para computadores sobrecarregados, os quais tendem a realizar nova migração. Essas questões relativas à migração de processos motivaram Halchor-Balter e Downey [4] na proposta de um modelo de custo de migração baseado na idade dos processos. Esse estudo conclui que há benefícios na migração de processos com grande tempo de vida. Contudo, esse estudo é incompleto em suas avaliações, pois além da avaliação do tempo de execução dos processos, há a necessidade de avaliar a carga que esses processos impõem sobre o sistema. Processos com longos períodos de execução, mas que apresentam pouca ocupação, quando migrados, não agregam benefícios para o computador emissor. Além disso, esses processos sofrem acréscimo de custo de migração em seu tempo de execução. Observando essas limitações, este artigo apresenta um modelo que permite quantificar os custos e impactos causados na migração de processos em ambientes compostos por computadores de capacidade de processamento heterogênea. Os resultados desse modelo são utilizados para propor uma 374 IEEE LATIN AMERICA TRANSACTIONS, VOL. 4, NO. 5, SEPTEMBER 2006 heurística que decide sobre a viabilidade de migração de processos. Essa heurística visa balancear a carga do ambiente e, conseqüentemente, reduzir o tempo de resposta dos processos. Esse modelo avalia três aspectos: o custo de migração, a carga imposta e o tempo de vida dos processos. Em experimentos utilizando um simulador desse modelo, foi possível comprovar suas contribuições na homogeneização da carga do ambiente, o que, conseqüentemente, gerou maior desempenho das aplicações. O artigo é composto pelas seguintes seções: 2) Modelo de migração baseado no conhecimento sobre o tempo de vida e carga de processos; 3) Tomada de decisão utilizando o modelo proposto; 4) Simulador; 5) Resultados; 6) Conclusões e Referências. II. MODELO DE MIGRAÇÃO DE PROCESSOS BASEADO NO CONHECIMENTO SOBRE O TEMPO DE VIDA E CARGA DE PROCESSOS As limitações do trabalho de Halchor-Balter e Downey [4] motivaram a criação de um modelo que permite quantificar os custos e impactos causados pela migração de processos em ambientes compostos por computadores de capacidade de processamento heterogênea. Os custos compreendem a quantidade de recursos consumida para transferir processos entre computadores. Os impactos compreendem o quanto será afetado o tempo de execução do processo a ser transferido e o balanceamento da carga do ambiente. A transferência de processos não deve ocorrer em casos onde o tempo de execução aumente ou o ambiente seja desbalanceado. O modelo proposto avalia três aspectos: o custo de migração, a carga imposta e o tempo de vida dos processos. Nesse modelo cada processo Pi impõe, durante toda sua execução, uma carga total Li sobre o computador que executa. Essa carga total é caracterizada por uma função f(t) que varia durante o ciclo de vida do processo. execução, no instante t0, até sua idade atual no instante tatual (equação 2). O terceiro parâmetro é a carga sobressalente, ou seja, aquela que falta ser executada para terminar um processo (equação 3). Esse parâmetro é obtido através da integração do instante atual tatual até o instante tfinal, que representa o final da execução de um processo. Para obter a função f(t) são realizadas medições durante a execução do processo e utilizado o modelo de predição de ciclo de vida de processos proposto por Senger et al. [8]. Esse modelo permite prever o tempo de execução de um processo através de um algoritmo de aprendizado baseado em instâncias. L total ³ final 0 D actual 0 f ( t ) i dt i ³ 0 ,i (1) f ( t ) i dt i 0 ³ L exec L ss ,i ³ ,i actual (2) f ( t ) i dt i f ( t ) i dt i ³ final atual f ( t ) i dt i (3) Além dos parâmetros obtidos pela função f(t), o modelo proposto neste artigo requer outros parâmetros. Um desses se refere à caracterização da carga dos computadores do ambiente, que é obtida através da equação 4, onde é realizado um somatório das cargas sobressalentes de cada processo no instante atual tatual. Outro parâmetro utilizado é o custo de migração dos processos, dado pela equação 5, onde: MCfixo representa o custo fixo para salvar o estado de um processo; MCtransfer-memo representa o custo para transferir a memória do processo para o computador destino, apresentada na equação 6; MCreinic-canais representa o custo para reiniciar os canais de comunicação de acesso ao disco rígido e rede. A equação 6 utilizada pela equação 5 é composta por: Pmemo,i que representa a quantidade ocupada de memória (em bytes) pelo processo Pi; CAPlarg-banda representa a largura de banda, ou capacidade de transferência de dados, entre o computador que emite e o que recebe a carga. max CL atual ¦³ p 0 MC i MC fixo final actual p f ( t ) p dt p (4) MC transfer memo ,i MC reinic canais ,i (5) Pmemo ,i CAP l arg banda (6) MC transfer memo ,i Fig. 1. Exemplo da carga imposta por um processo em execução A figura 1 ilustra a carga de um processo durante sua execução. O modelo proposto neste artigo utiliza essa função para definir alguns de seus parâmetros. O primeiro parâmetro é a carga total Ltotal,i de um processo Pi (equação 1), a qual é obtida através da integração do gráfico da função. O segundo parâmetro permite obter a quantidade de carga executada do processo Pi, para isso deve-se integrar do início de sua Utilizando as equações anteriormente apresentadas é proposto um fator de migração (equação 8) para avaliar os custos e impactos na transferência de processos. Quando esse fator é igual a 1, o sistema entra em perfeito equilíbrio, pois cada computador executa uma carga equivalente à sua capacidade de execução. Caso isso não seja possível, pode-se aproximar desse valor através do somatório da carga de n processos enquanto o fator d 1. Caso nenhum processo do FERNANDES DE MELLO AND SENGER : A MIGRATION FACTOR TO DETERMINE THE computador sobrecarregado resulte em um fator de migração Mfator igual ou menor a um, então pode-se optar por um processo que tenha um fator d CAPrec/CAPem. Nesse caso o fator é comparado à diferença percentual de desempenho entre o computador destino (receptor) e fonte (emissor). (7) N ss ,i L ss ,i u CAP em MC N ss ,i fator , i CL em ( CL rec III. (8) N ss ,i CAP rec MC i ) TOMADA DE DECISÃO Esta seção apresenta as decisões que podem ser tomadas à partir de valores do fator de migração (equação 8) de processos. Para caracterizar essas decisões, considere dois computadores C1 e C2 de capacidade heterogênea. O computador C1 tem capacidade igual a 1000 MIPS e o segundo igual a C2 500 MIPS. O computador C1 tem 3 processos em execução com as respectivas cargas P1 = 5, P2 = 2 e P3 = 1, sendo a carga total dos computadores dada pela equação 4, a carga de C1 é igual a 8. O computador C2 tem 1 processo P1 com carga igual a 4, sendo a carga de C2 = 4. Considere que o computador C1 requer transferência de carga, pois observa seu estado de alta carga em relação aos demais computadores do ambiente. Nesse momento os processos de C1 são ordenados pela carga e são obtidos seus fatores de migração segundo a tabela I. TABELA I FATORES DE Processo P1 P2 P3 MIGRAÇÃO DOS PROCESSOS DE C1 Fator de Migração 5 8 ( 4 (( 5 u 1000 ) y 500 )) 0 . 83 2 8 ( 4 (( 2 u 1000 ) y 500 )) lim x o 0 1 8 ( 4 ((1 u 1000 ) y 500 )) 0 .5 2 x f Observando a tabela I pode-se concluir que o fator de migração do processo P1 é igual a -0.83. Observe nesse caso que o computador C1 terá carga igual a 3 após a migração e o computador C2 igual a 14. Esse desbalanceamento não é desejado, por isso qualquer valor negativo no fator de migração representa uma piora de desempenho do computador receptor de processos. Para o processo P2, Mfator = f o que significa que a carga do computador receptor será a mesma carga atual do computador emissor do processo. Nesse caso a migração não traz benefício algum para o ambiente, será apenas realizada uma transferência de carga. Para o processo P3, Mfator = 0.5, isso significa que há benefícios em sua 375 migração, pois há um melhor balanceamento das cargas e cada computador deve executar cargas de acordo com sua capacidade de processamento. Há benefícios sempre que 0 < Mfator,i d CAPrec/CAPem,ou seja, sempre que o fator de migração não prejudique o balanceamento e sobrecarregue o computador receptor (quando Mfator d 0) ou quando apenas ocorre uma transferência da carga sem benefícios para o ambiente (quando Mfator,i > CAPrec/CAPem). A equação do fator de migração (equação 8) pode ser extendida para melhorar o balanceamento de carga através de migração de k processos (equação 9). Por exemplo, considere uma situação onde um computador apresenta diversos processos Pi onde i = 1, 2, 3, ..., n. Nesse caso pode-se somar os fatores de migração de k processos enquanto d CAPrec/CAPem e migrá-los para outro (ou outros) computadores ociosos. k ¦M p 0 factor , i d CAP rec CAP em (9) IV. SIMULADOR Para avaliar o modelo proposto foi construído um simulador. Esse simulador1 é parametrizado com as ocupações de CPU e memória que cada processo causa no sistema, e com a capacidade de cada computador do ambiente. A ocupação de CPU dos processos é definida em MI (milhões de instruções) necessárias para processá-los. A ocupação de memória é definida em bytes. A capacidade de cada computador é definida em MIPS (milhões de instruções por segundo). O simulador implementa uma heurística que toma decisões de balanceamento de carga no ambiente. Essa heurística considera que se a carga de um computador estiver acima da média dos demais, esse é um emissor de processos. Essa avaliação de carga é periódica e pode ser configurada. O computador com menor carga é selecionado e a equação 8 é aplicada para decidir qual o processo ou processos são os mais adequados para migração. Caso processos sejam selecionados para migração, essa etapa é realizada e os custos de transferência são adicionados em seus tempos de execução. Ao final da simulação sabe-se o tempo total de execução de cada processo com todos os custos embutidos. O simulador foi construído em uma linguagem orientada a objetos. Suas classes principais são: 1) Computer -- contém a representação de um computador no ambiente tais como sua capacidade em MIPS, memória e fila de processos. O principal método dessa classe é responsável por um laço de repetição que simula um escalonador selecionando e executando processos. Como esse laço representa o escalonador em um instante de execução t, nele é adicionado código para, periodicamente, avaliar a carga do computador e julgar a necessidade de migração. Caso haja migração dois 1 Simulador disponível em http://www.icmc.usp.br/~mello/outr.html 376 IEEE LATIN AMERICA TRANSACTIONS, VOL. 4, NO. 5, SEPTEMBER 2006 métodos podem ser chamados. O primeiro implementa o modelo de Halchor-Balter e Downey, o segundo o modelo proposto neste trabalho. Dessa forma, pode-se comparar os resultados dos dois modelos; 2) MidProcess -- representa um processo no ambiente. Aplicações multiprocessadas são compostas por várias instâncias dessa classe. Ela contém informações sobre a ocupação total do processo em MI (milhões de instruções), memória, instante inicial e final de execução, e custos decorridos de migrações; 3) Simulator -- inicia o simulador e submete processos para execução de acordo com uma função de distribuição de probabilidades. Após a chegada desses processos ao sistema, eles são atribuídos aos computadores através de uma função distribuição normal. A função de distribuição de chegada de processos ao sistema e seus parâmetros podem ser definidos pelo usuário. São suportadas as funções disponíveis na biblioteca PSOL (The Probability/Statistics Object Library)2 adotada no projeto. O simulador gera resultados de tempos médios de resposta dos processos, em segundos. Experimentos são executados até que o número de amostras seja estatisticamente representativo para calcular um intervalo de confiança de 95%. Para isso são adotadas as equações descritas em [11]. Na equação 10 é calculado o somatório dos tempos de execução T de cada um dos n processos submetidos ao ambiente. A equação 11 calcula o somatório do quadrado dos tempos de execução. Os resultado dessas equações são utilizados para calcular a variância aproximada dos tempos de execução (equação 12). A equação 13 resulta no intervalo de confiança de 95% aproximado dos experimentos. O valor 1,96 é adotado pois representa que 95% dos valores estão contidos dentro de uma distribuição Normal [11]. Caso a média obtida na equação 10 multiplicada por 0,05 seja maior que o intervalo de confiança, pode-se parar os experimentos que o conjuntos de amostras já é estatisticamente representativo para aplicar medidas de resumo tais como média, desvio padrão, variância, intervalo de confiança etc. Isso representa que a amostra apresenta variação inferior a 5% da média. n Sum (10) ¦T i i 1 n Sum 2 ¦T i Ti (11) i 1 s2 ( n Sum 2 ) ( Sum Sum ) n ( n 1) ic 1,96 s2 n (12) (13) na análise de seis traços de execução nos seguintes ambientes de produção: iPSC/860 com 128 nós da NASA Ames; IBM SP1 com 128 nós da Argonne; Paragon com 400 nós da SDSC; Butterfly com 126 nós da LLNL; IBM SP2 com 512 nós da CTC; Paragon com 96 nós da ETH, Zurich. Segundo esse modelo, processos chegam ao ambiente segundo uma distribuição exponencial de média 1500 segundos. Além disso, esse modelo propõem uma distribuição de probabilidades para o número de processos que compõem uma mesma aplicação paralela e para a carga desses processos. Uma implementação desse modelo3 foi adotada para criar arquivos contendo as características de aplicações para simulação. Esses arquivos são lidos e interpretados pelo simulador, que submete processos para execução. Para realizar as simulações foram adotados três ambientes compostos por 8, 32 e 128 computadores com as capacidades de CPU (em MIPS) variando uniformemente entre 500 e 1400 MIPS e memória (em MBytes) variando uniformemente entre 64 e 512 MBytes. As figuras 2, 3 e 4 apresentam os resultados obtidos em tempos médios de resposta (segundos) variando em função do número de aplicações paralelas submetidas. São apresentados resultados em um ambiente sem migração, com migração baseada no tempo de vida dos processos (proposta de Halchor-Balter e Downey) e na heurística que utiliza o modelo proposto neste artigo (Heurística). Esses experimentos exploram a migração de processos em ambientes com diferentes escalas. Resultados obtidos motivam a adoção da nova heurística para otimizar o balanceamento de carga em ambientes distribuídos escaláveis, pois otimiza o tempo de resposta de processos, que, conseqüentemente, executam mais rápido. A otimização deve-se ao fato do modelo proposto considerar a quantidade de carga dos processos sobressalente e como os computadores reagem à transferência desse processamento. Nos experimentos com 8 e 32 computadores a heurística apresenta melhores resultados, seguida pelo modelo baseado no tempo de vida de processos e por ambientes sem migração. Contudo, pode-se notar que o modelo baseado no tempo de vida tem seu desempenho prejudicado, conforme o número de computadores do ambiente aumenta. Isso torna-se ainda mais evidente na figura 4, que apresenta informações sobre um ambiente composto por 128 computadores. Nesse caso, o modelo de tempo de vida apresenta piores resultados que ambientes sem migração de processos, pois cargas são transferidas entre computadores sem considerar o quanto os aliviam ou sobrecarregam. Nos três ambientes adotados, a heurística baseada no modelo proposto neste trabalho apresenta melhores resultados. V. RESULTADOS Para parametrizar o simulador foi estudado o modelo de carga de trabalho de Feitelson [2], [3]. Esse modelo é baseado 2 PSOL é uma biblioteca estatística licenciada sob GNU/GPL e desenvolvida pela Universidade do Alabama -- disponível em http://www.math.uah.edu/psol. 3 Disponível em http://www.cs.huji.ac.il/labs/parallel/workload/models.html. FERNANDES DE MELLO AND SENGER : A MIGRATION FACTOR TO DETERMINE THE Fig. 2. Resultados para o modelo de carga de Feitelson – 8 computadores VI. CONCLUSÕES Este artigo apresentou um modelo que permite quantificar os custos e impactos causados na migração de processos em ambientes compostos por computadores de capacidade de processamento heterogênea. As equações propostas no modelo foram utilizadas para definir uma heurística de migração de processos com o objetivo de balanceamento de carga. Esse modelo analisa a ocupação de cada processos e seleciona os mais adequados para migração. Essa análise e seleção são feitas através de um fator de migração. Esse fator reflete quanto o computador sobrecarregado será aliviado e quanto o computador destino tornar-se-á carregado em função da migração de cada processo. 377 Fig. 4. Resultados para o modelo de carga de Feitelson – 128 computadores Experimentos foram conduzidos utilizando um simulador e três ambientes de diferentes escalas. Esses experimentos comprovam que uma heurística baseada no modelo proposto otimiza o tempo médio de resposta de processos quando comparados ao modelo de migração de processos baseado no tempo de vida [4] e a um ambiente sem migração. O modelo baseado no tempo de vida apresentou resultados piores, conforme aumentou o número de computadores do ambiente. Isso deve-se ao fato desse modelo não considerar quanto a carga de todo o ambiente é afetada ao transferir processos. Esses resultados desmotivam a adoção do modelo de Halchor-Balter e Downey em ambientes escaláveis. AGRADECIMENTOS Os autores agradecem o suporte da Fundação de Amparo à Pesquisa do Estado de São Paulo (processo número 04/024119). REFERÊNCIAS [1] [2] [3] Fig. 3. Resultados para o modelo de carga de Feitelson – 32 computadores [4] [5] [6] [7] R. Buyya. High Performance Cluster Computing-Architecture and Systems, volume1. PrenticeHall, 1999. D. G. Feitelson. Metrics for parallel job scheduling and their convergence. In D. G. Feitelson and L. Rudolph, editors, Job Scheduling Strategies for Parallel Processing, pages 188–205. Springer, 2001. Lect. Notes Comput. Sci. vol. 2221. D. G. Feitelson and M. A. Jette. Improved utilization and responsiveness with gang scheduling. In D. G. Feitelson and L. Rudolph, editors, Job Scheduling Strategies for Parallel Processing, pages 238–261. Springer, 1997. Lect. Notes Comput. Sci. vol. 1291. M. Harchol-Balterand A. B. Downey. Exploiting Process Lifetimes Distributions for Dynamic Load Balancing. ACM Transactions on Computer Systems, 15(3): 253–285, August 1997. C. Hui and S. T. Chanson. Hydrodynamic load balancing. IEEE Transactions on Parallel and Distributed Systems, 10(11): 1118–1137, nov. 1999. P. Krueger and M. Livny. The diverse objectives of distributed scheduling policies. In Seventh Int. Conf. Distributed Computing Systems, pages 242–249, Los Alamitos, California, 1987. IEEE CS Press. R. F. Mello, L. C. Trevelin, M. S. Paiva, and L. T. Yang. Comparative study of theserver-initiated lowest algorithm using a load balancing 378 index based on the process behavior for heterogeneous environment. In Networks, Software Tools and Application, ISSN 1386-7857. Kluwer, 2004. [8] L. J. Senger, M. J. Santana, and R. H. C. Santana. Using runtime measurements and historical traces for acquiring knowledge in parallel applications. In International Conference on Computational Science (ICCS’2004), volume LNCS3036, pages 661–665. Springer Lect. Notes Comput. Sci, 2004. [9] N. G. Shivaratri, P. Krueger, and M. Singhal. Load distributing for locally distributed systems. IEEE Computer, 25 (12):33–44, 1992. [10] M. M. Theimer and K. A. Lantz. Finding idle machines in a workstationbased distributed system. IEEE Transactions on Software Engineering, 15(11): 1444–1458, nov. 1989. [11] W. C. Shefler. Statistics: Concepts and Applications. The Benjamin/Cummings, 1988. [12] S. Zhou and D. Ferrari. An experimental study of load balancing performance. Technical Report UCB/CSD 87/336, PROGRES Report N.o 86.8, Computer Science Division (EECS), Universidade da California, Berkeley, California 94720, jan. 1987. Rodrigo Fernandes de Mello obteve o título de bacharel em tecnologia em processamento de dados em 1997 pela Universidade de Estadual Paulista Júlio de Mesquita Filho, Bauru, São Paulo, Brasil, mestre em ciências da computação em 1999 pela Universidade Federal de São Carlos, São Paulo, Brasil, e doutor em engenharia elétrica em 2003 pela Escola de Engenharia de São Carlos, Universidade de São Paulo, São Carlos, Brasil. Ele é professor doutor da Universidade de São Paulo, revisor de periódico da Atmospheric Environment (1352-2310), revisor de periódico da Revista do CCEI (14152061) e revisor de periódico da Journal of Parallel and Distributed Computing (0743-7315). Dr. Mello tem interesse em pesquisa nos seguintes temas: balanceamento de carga, processamento de alto desempenho, avaliação de desempenho, simulação, clusters e grids computacionais. Luciano José Senger obteve o título de bacharel em informática pela Universidade Estadual de Ponta Grossa, Paraná, Brasil, em 1995, mestre e doutor em ciências de computação e matemática computacional pelo Instituto de Ciências Matemáticas e de Computação, Universidade de São Paulo, São Carlos, São Paulo, Brasil, em 1997 e 2005, respectivamente. Ele atua como professor Adjunto e como pesquisador no grupo de Sistemas Distribuídos da Universidade Estadual de Ponta Grossa desde 1998. Dr. Senger atualmente tem interesse na pesquisa em sistemas distribuídos, algoritmos de escalonamento, redes neurais artificiais e processamento paralelo. IEEE LATIN AMERICA TRANSACTIONS, VOL. 4, NO. 5, SEPTEMBER 2006