Anais WSCAD 2005

Simulação Discreta Por Eventos de Políticas de Escalonamento de Tarefas em Multiprocessadores

Luiz G. H. D. Silveira, Luís F. W. Góes, Carlos A. P. S. Martins Pontificia Universidade Católica de Minas Gerais- Belo Horizonte- Minas Gerais

luizdrumond@gmail. br, lfwgoes@pucminas. br, capsm@pucminas. br

Resumo

Políticas de escalonamento são importantes no desempenho de sistemas computacionais paralelos, pela otimização do tempo de execução de cada tarefa. O problema é a escolha da política mais eficaz para cada tipo de carga de trabalho e arquitetura. Este trabalho propõe e apresenta um "módulo de simulação de políticas de escalonamento " em multiprocessadores no ClusterSim. Além disso, analisamos o desempenho das políticas de escalonamento implementadas. Nossa principal contribuição é a ampliação do módulo de escalonamento de processos em multiprocessadores, possibilitando novas opções de simulação.

1. Introdução

A concorrência entre processos por recursos computacionais gera a necessidade de alocação de recursos de processamento. A parte do sistema operacional que toma essa decisão é chamada escalonador, o algoritmo que ele utiliza é chamado algoritmo de escalonamento (I] (2].

"Nos sistemas de lote com entrada na forma de imagens de cartões em uma fita magnética, o algoritmo de escalonamento era simples (apenas execute o próximo trabalho na fila). Com sistemas de compartilhamento de tempo, o algoritmo de escalonamento tomou-se mais complexo, uma vez que, freqüentemente, múltiplos usuários esperam serviços e pode haver um ou mais fluxos de lote também (ex: o processamento de pedidos em uma companhia de seguro)" [1). Mesmo em computadores pessoais, vários processos podem ser iniciados pelo usuário competindo pelo processador [I) [2).

Atualmente, o processamento paralelo é amplamente utilizado na indústria e no meio acadêmico para a resolução de problemas complexos, que demandam alto desempenho computacional. Normalmente, um sistema computacional paralelo é composto por uma arquitetura paralela (aglomerado de computadores, multiprocessador, etc.) e por uma carga de trabalho (tarefas paralelas, em lote e etc) [3) [4].

Estudar e analisar o desempenho de políticas de escalonamento em máquina paralela real é uma tarefa

226

difícil, principalmente pelo alto custo financeiro e pela grande variedade de máquinas, carga de trabalho e políticas. Por outro lado, a simulação é uma alternativa de menor custo e alta precisão nos resultados.

A motivação para este trabalho foi criar um módulo de simulação de políticas de escalonamento de processos em multiprocessadores que permita o estudo e análise de desempenho com diferentes cargas de trabalho (composta de vários processos) e máquinas. Para desenvolver esse módulo, selecionamos a ferramenta de simulação ClusterSim .

Os objetivos a serem alcançados neste trabalho são a proposta e a implementação de três políticas tradicionais (SJF - Sbort Job First , RR - Round Robin e PSJF - Preemptive Short Job First) no módulo de escalonamento de processos em multiprocessadores, possibilitando novas opções de simulações no ClusterSim e análise de desempenho de algumas aplicações com essas políticas de escalonamento.

Este artigo é organjzado como se segue: na seção 2, apresentamos alguns trabalhos relacionados; na seção 3 mostramos a proposta de melhoria do módulo de escalonamento de processos dos nodos do ClusterSim; na seção 4, os resultados das simulações das políticas implementadas; na seção 5, apresentamos as conclusões e alguns trabalhos futuros; na seção 6, as referências bibliográficas.

2. Trabalhos Relacionados

Dentre os principais trabalhos relacionados destacamos os simuladores SRGSim [5], SOSim (6] e o ClusterSim[3). Estas ferramentas de simulação permitem a simulação de diferentes políticas de escalonamento assim como o nosso módulo de simulação. Além disso, disponibilizam documentação e/ou seu código fonte.

A ferramenta (SRGSim), desenvolvida pelo Schark Group, com características interessantes (escalonamento estático e dinâmico, modelagem da carga de trabalho com distribuições probabilísticas etc.), que simula algoritmos de escalonamento paralelo de tarefas em arquiteturas paralelas. Apesar dessas vantagens, o SRGSim não possui as seguintes

Anais WSCAD 2005

características desejáveis: interface gráfica, enfoque didático, suporte a nodos heterogêneos, descrição estrutural da carga de trabalho etc [6].

O SOSim não possibilita simulações de máquinas reais, ao contrário do ClusterSim, que onde podemos configurar a máquina que deseja-se simular, descrevendo o processador, sua freqüência e número de instruções por segundo, número de processadores e a política de escalonamento que se deseja simular. Além disso, o SOSim permite simulação de apenas uma máquina. [5].

"O ClusterSim (Ciuster Simulation Tool) é uma ferramenta de "simulação paralela discreta por eventos de desempenho de escalonamento paralelo de tarefas", em aglomerados de computadores, baseada em Java. Ele suporta modelagem visual e simulação de aglomerados de computadores e das cargas de trabalho. Os aglomerados são compostos de nodos mono ou multiprocessados, algoritmos de escalonamento paralelo de tarefas, tecnologias e topologias de rede. As cargas de trabalho são representadas por usuários, que submetem tarefas compostas por processos, que são descritos por distribuições de probabilidades e pela sua estrutura interna". [2].

O ClusterSim provê uma simulação mais realista, permitindo criação de nodos heterogêneos e descrição estrutural de cargas, descrição da característica de cada nodo, um ambiente gráfico de fácil entendimento e foi criado em Java, o que permite uma maior "pluralidade" de plataforma. Esta foi a ferramenta escolhida.

3. Proposta

A nossa proposta para esse trabalho consiste em aumentar a abrangência do módulo de simulação de escalonamento de processos nos nodos do Cluster, no ClusterSim, e fazer uma análise de desempenho das políticas de escalonamento de processos implementadas em multiprocessadores.

A nossa principal motivação para a escolha do ClusterSim para a execução deste trabalho é pela extrema facilidade que o ClusterSim disponibiliza para se fazer simulações tanto em cluster como em um simples nodo onde precisa-se escalonar processos.

O ClusterSim pode simular políticas de escalonamento centralizado ou distribuído. Em nossos testes trabalhamos com o ambiente centralizado, uma política para todos os processadores.

Nesta pesquisa, trabalhamos com cinco eventos relacionados ao escalonamento dos processos nos nodos. O jobArriva/Event é responsável pelo tratamento de cada processo quando um "pacote de processos" chega ao nodo. O unblockTaskEvent é responsável pelo tratamento dos processos quando processos quando bloqueados já tenham cumprido a

227

tarefa de bloqueio e já possam retornar à fila de prontos para serem executados novamente. O endOjTaskEvent é responsável pelo tratamento dos processos quando os mesmos já tenham finalizado toda sua execução. O endOJQuantumEvent é responsável pelo tratamento dos processos quanto o tempo designado a eles no processador tenha terminado. Neste evento, outros tratamentos são feitos, como bloquear processos que tenham feito E/S(Entrada ou saída) e comunicação. Este evento tem maior importância nas políticas preemptivas.

O schedule é responsável pela própria alocação de processos aos processadores, ele irá designar qual processo irá a qual processador e verificar se algum processador está sem processos. Este evento acontece sempre quando algum dos outros eventos ocorrem, assim, quando todos os tratamentos tiverem ocorrido, seguindo o conceitos das políticas de escalonamento, o processamento será confiável.

Nós implementamos três políticas para as simulações nos nodos. Uma não preemptiva, SJF (Short Job First) e duas preemptivas Round Robin e PSJF (Preemptive Short Job First). Na política SJF, quando os processos estiverem sendo executados, os processos menores terão prioridade maior nos processadores. O evento mais importante dessa política na nossa implementação é o jobArrivalEvent. A cada chegada de novos processos, esses processos são avaliados para saber o quanto eles precisam de tempo para ser executados e ordenados na fila de prontos.

A política Round Robin possui o conceito de preempção por tempo, ou seja, ela designa uma fatia de tempo do processador para cada processo. No ClusterSim cada fatia de tempo como valor padrão, podendo ser modificado com a necessidade de simulação, já é determinada como sendo cem milhões de nano segundos. O evento mais importante desta política na nossa implementação é o endOJQuantumEvent. Neste evento caso o processo não tenha sido designado para ser bloqueado, o processo é inserido no final da fila de processos prontos no final da sua fatia de tempo.

A política PSJF (Preemptive Short Job First) preemptiva implementada, é uma junção de SJF não preemptiva com Round Robin, ou seja, quando os processos chegam ao nodo o evento jobArrivalEvent é chamado, estes processos são avaliados para saber o quanto eles precisam de tempo para serem executados e ordenados na fila de prontos.

As políticas que foram implementadas foram políticas preemptivas, aonde se disponibiliza um quantum, tempo no qual um processo terá no processador até ser escalonado, Round Robin e SJF -Short Job First, e não preemptiva SJF. Uti lizou-se também para análise uma política não preemptiva já implementada, FCFS (First Come First Served ).

Anais WSCAD 2005

4. Resultados de Simulação

Na definição da carga de trabalho, pensamos em abranger um maior número de possibilidades. Os processos são compostos de instruções de CPU e de EIS, optamos por uma variação da quantidade de instruções de CPU e E/S. Para efeito de simulação escolhemos processos com tempo de execução igual a I 00 segundos. Para uma maior confiabilidade dos dados da simulação criamos jobs variando a porcentagem de instruções de CPU e EIS, submetendo 30 jobs, e variando a porcentagem de cada tipo de job a ser submetido. Com essa variação de porcentagem de submissão de um job que se deseja obter seu resultado.

' '

Tabela 1: Características da Carga de Trabalho

Jobs - CPU --EJS Porcentagem de Submissão j1 o 100 10% j2 100 o 10% i3 lll 20 10% 14 20 lll 10% j5 60 40 10% j6 40 60 50%

O tipo que se deseja estudar em uma determinada simulação tem a maior porcentagem de submissão, que é 50%, esse valor foi mudado para cada job quando simulado. Com esta carga variada entre instruções de CPU e E/S poderemos ter uma maior confiabi lidade da simulação. Seguindo o exemplo da tabela I , desejamos descobrir como se comporta essa carga de trabalho que possui 40 segundos de CPU e 60 de E/S com 50% de submissão, e como na simulação gostaríamos de saber como se comporta uma carga de trabalho com maior quantidade desta característica, configuramos que esse job terá 50 % de chance de ser submetido dentre as 30 submissões. Nas figs. 2-7, podemos observar o desempenho das políticas de escalonamento para as cargas de trabalho utilizadas.

•FCFS ,t~ • F. ll4IVo Tempo de Reação das Cargas o tJF · ~eetq)t O Raund Robln 8 processadores

400,1111 --350,00

I ... 300,00

1250.00 I 200,00 :--' 150,00 r- - ~ R .. 100.00 rn- r-

f-l-H-1--

50,00 r- 1--0,00

OCPU 100 CPU • 80CPU • 20CPU· 60CPU· ~OCPU· 100 EIS O EIS 20EIS 60EIS 40EIS 60EIS

Proc.uos

Figura 2: Tempo de Reação das cargas com 8 Processadores

De acordo com a fig. 2 podemos notar, que o intervalo entre a submissão e o inicio da execução,

228

nas políticas preemptivas os processos começam as suas execuções mais rápido, sendo assim seu tempo aproximado de zero. E no caso das políticas não­preemptivas o tempo de execução dos processos da política SJF é melhor do que a FCFS, pois como a SJF analisa os processos antes, dando uma prioridade maior aos processos menores, influenciando assim no tempo de reação de todos os processos. No caso da FCFS, se no pacote de processos, um processo com 50% do tamanho do pacote, for executado primeiro exercerá influência direta no tempo de reação dos processos restantes.

Tempo de Resposta das cargas 8 Processadores

OCPU· 100CPU· 80CPU· 20CPU · 60CPU· 40CPU · ~EIS DEIS 20EIS 60EIS 40EIS ~EIS

Processos

Figura 3: Tempo de Resposta das Cargas com 8 Processadores

Slowdown das Cargas 8 Processadores

O CPU • 100 CPU • 80CPU • 20 CPU • 60 CPU • 40 CPU. 100 EIS O EIS 20 EIS 80 EIS 40 EIS 60 EIS

Proceuos

Figura 4: Slowdown das Cargas com 8 Processadores

De acordo com a figura 4, podemos notar que em relação as políticas, as políticas preemptivas diminuem o slowdown(Perda de desempenho devido a concorrência de processos pelos processadores) justamente por causa da fatia de tempo, assim todos os processos terão seu tempo, não afetando tanto o s lowdown. Observando as cargas com O instruções de CPU e 100 de E/S, e 100 de CPU e O de E/S. No caso na que possui mais instruções EIS, não haverá concorrência, por isso o slowdown é baixo, no caso do 100 de CPU, a fatia de tempo disponibilizada pelas políticas preemptivas permitira acesso ao processador a todos diminuindo o slowdown.

Com o aumento do número de processadores, podemos notar de acordo com a fig. 5, que o tempo total de reação das cargas, as políticas não-preemptivas

Anais WSCAD 2005

obtém uma melhora significativa quando aumentamos de 1 até 4 processadores. Quando aumentamos acima de 8 processadores, o grau de paralelização já está no limite para essa pequena carga. Com isso passa-se mais tempo fazendo EIS do que processamento.

Quanto ao intervalo de tempo entre a submissão e a finalização do processo, podemos concluir que no caso das cargas de trabalho com mais instruções de CPU precisam de mais tempo para ser concluídas, levando em conta que elas estarão utilizando o processador para serem processadas, enquanto as de E/S estarão esperando por dados e não estarão utilizando o processador. Em relação as políticas preemptivas, elas são mais eficientes. Tendo um "pacote de processos " para executar todos com políticas preemptivas, pode ser que processos menores sejam executados primeiro, e assim a possibilidade de serem finalizados primeiro, obtendo um tempo de resposta menor.

Com o aumento do número de processadores, de acordo com a figura 6 notamos que, para processar todas as cargas, obtém-se uma melhora significativa até 4 processadores, com 8 processadores o grau de paralelismo já está no limite para essa carga. Com isso passa-se mais tempo fazendo E/S do que processamento, isso para todas as políticas.

Tempo de Reação das Cargas

4500,00 -4000.00 +-:=---------------~ 3500,00

"! 3000.00 &: 2500.oo ~ 2000,00 .. 1500.00

1000,00 500.00

0.00 2 4 8

•FCFS Total de Resposta das Cargas • SJF· ~

OSJF·N .. _.,..,..

9000,00 +-=:-T-r-------==O=R=OIIId=R=ol*l===--' 8000,00 7000,00

- 6000,00 i 5000,00 14000.00 .. 3000,00

2000,00 1000,00

o.oo 2 8

No..,.. PI'MMt.Mefft

Figura 6: Tempo total de resposta das cargas

Com o aumento do número de processadores, podemos notar de acordo com a figura 7 que, para processar todas as cargas, o aumento de processadores para as políticas preemptivas não tem efeito, já que a idéia de preempção designará um espaço de tempo para todos os processos. No caso das políticas não-

229

preemptivas a melhora ocorre até 4 processadores, com 8 o grau de paralelismo já está no limite e passa-se mais tempo fazendo E/S do que processamento.

Slowdown Total das Cargas

8

Figura 7: Slowdown total das cargas

5. Conclusão

Os objetivos alcançados neste trabalho foram a ampliação de um módulo de simulação do ClusterSim com a implementação de 3 políticas tradicionais de escalonamento, e uma avaliação de desempenho das políticas com uma determinada carga de trabalho.

Em relação às políticas, concluímos que as políticas que utilizam preempção são mais eficazes que as não-preemptivas, e que o aumento de processadores é eficaz até um certo limite de acordo com a sua carga de trabalho. Nossa maior contribuição foi a expansão de um módulo de simulação do ClusterSim e uma análise de desempenho das políticas de escalonamento implementadas em multiprocessadores.

Entre os trabalhos futuros, implementaremos um módulo de gerência de memória no ClusterSim para avaliação de desempenho de gerência de memória.

6. Referências

[I] Andrew S. Tanenbaum, Albert S. Woodhull, "Sistemas Operacionais: Projeto e Implementação". [2] Yamin, A.C. "Escalonamento em Sistemas Paralelos e Distribuídos", 1' Escola Regional de Alto Desempenho, Brasil, Gramado, p. 75-126, 200 I. [3) L. F. W. Góes, L. E. S. Ramos, C. A. P. S. Martins, "CiusterSim: A Java-Based Parallel Discrete-Event Simulation Tool for Cluster Computing", IEEE lnternational Conference on Cluster Computing, 2004. [4] Góes, L. F. W., Martins, C. A. P. S., "Escalonamento Paralelo de Tarefas: Conceitos, Simulação e Análise de Desempenho", Workshop de Sistemas Computacionais de Alto Desempenho, Foz do Iguaçu, 2004. [5] Luiz Paulo Maia, "SOSim: Simulador para o Ensino de Sistemas Operacionais", 2003. URL: http://www.training.eom.br/sosirnl [6] H. Bodhanwala, et ai., "A General Purpose Discrete Event Simulator", Symposium on Performance Analysis of Computer and Telecommunication Systems, USA, 200 I.