Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2007. / Submitted by Luis Felipe Souza (luis_felas@globo.com) on 2009-01-09T13:17:21Z No. of bitstreams: 1 Dissertacao_2007_JorgeSchtoltz.pdf: 2102171 bytes, checksum: a4bba0ce43d48ec2f9d4854022bc8eb4 (MD5) / Approved for entry into archive by Georgia Fernandes(georgia@bce.unb.br) on 2009-03-04T14:38:24Z (GMT) No. of bitstreams: 1 Dissertacao_2007_JorgeSchtoltz.pdf: 2102171 bytes, checksum: a4bba0ce43d48ec2f9d4854022bc8eb4 (MD5) / Made available in DSpace on 2009-03-04T14:38:24Z (GMT). No. of bitstreams: 1 Dissertacao_2007_JorgeSchtoltz.pdf: 2102171 bytes, checksum: a4bba0ce43d48ec2f9d4854022bc8eb4 (MD5) / O escalonamento estático de um programa, representado por um grafo dirigido acíclico de tarefas, em um ambiente multiprocessado, tem o objetivo de minimizar o tempo de conclusão do programa. Apesar das pesquisas nesta área terem obtido heurísticas eficientes, encontrar um escalonamento ótimo é um problema NP - Completo. Clusters de workstations podem ser utilizados no processamento paralelo de programas e devido à complexidade de integração entre os programas, o monitoramento e a simulação são efetuados através de ferramentas que gerenciam o cluster e a execução dos programas paralelos. Dentre as ferramentas analisadas, o PM2P, será utilizado como base de estudo devido ao conhecimento da ferramenta. O objetivo deste trabalho é o desenvolvimento e implementação na ferramenta citada um monitoramento periódico para verificar a disponibilidade das máquinas do cluster e re-escalonar os programas se houver necessidade ou ganho de desempenho. Para testar este monitoramento foram implementados, devido à carência de algoritmos na ferramenta, três algoritmos estáticos voltados para o escalonamento de tarefas que possam ser representados por um GDA (Grafo Dirigido Acíclico). Estes algoritmos funcionam de forma similar, gerando uma lista em ordem topológica das tarefas e àquelas pertencentes ao mesmo nível, portanto, concorrentes entre si, são ordenadas pelo maior ou menor tempo de execução. As tarefas são distribuídas de acordo com a disponibilidade das máquinas no cluster e o objetivo do algoritmo de escalonamento é manter o makespan gerado igual ao tempo do caminho crítico do grafo. Os resultados dos testes, as conclusões sobre o monitoramento e re-escalonamento serão demonstradas através de tabelas e mapas de Gantt para facilitar a visualização e o entendimento. Foram testados conjuntos de tarefas distintas que representam aplicações exemplo. Foi observado que aplicações rápidas, que finalizam sua execução concomitante ou logo após o tempo gasto para verificar a disponibilidade das máquinas no cluster, o monitoramento e o reescalonamento não são necessários e neste caso é recomendável o reinício da aplicação. Ao contrário, aplicações que demandam mais tempo para sua execução, o monitoramento e o re-início de algum programa no caso de indisponibilidade de uma máquina são importantes, uma vez que a aplicação continua sua execução com a nova arquitetura de máquinas, a partir do ponto de detecção da falha. Apesar do custo adicional para execução da atividade, conclui-se que há vantagens em se ter um cluster monitorado quando da execução dos programas paralelos utilizando a biblioteca MPI. ______________________________________________________________________________________________________ ABSTRACT / Static scheduling of a program represented by a directed acyclic graph task on a multiprocessor environment to minimize the program completion time is the goal. It is a wellknown problem of concurrent processing. Although the researches in this area already have reached heuristic efficient to find an optimal scheduling is a NP-Complete problem. The Cluster of Workstations can be used to the parallel processing of programs and due to the program interaction complexity, the monitoring and the simulation are made through frameworks that manage the cluster and the parallel program execution. Among the frameworks analyzed, the framework PM2P, will be used as the base study. The objective of this work is the development and implements a periodic monitoring to verify the machines availability at the cluster and rescheduling the programs whether is necessary or to improve the performance. It has been implemented, to test this periodic monitoring due to the framework algorithms lack new three static algorithms toward the scheduling of programs of tasks that could be represented by DAG (Directed Acyclic Graph). These three algorithms working in a similar way, each one create a topological order list of the tasks and they scheduling the tasks that belongs at the same level of the graph and ordering these tasks by the bigger or smaller execution time criteria. The tasks are sorted and distributed through the cluster machines in accordance with the availability of them. The scheduling goal is getting the graph makespan like the critical path time. The tests results, monitoring conclusions and the scheduling algorithms proposals will be demonstrated with tables and Gantt charts to a best exhibition and comprehension. The tests were over sets of different tasks that representing some real application. It was observed that applications with small execution time finish their at the same time or as soon as the framework check the cluster machines availability. In these cases are not necessary to rescheduling the applications and is recommended restart them. By the other hand, applications with big execution time, the programs monitoring and the restart of some program is important if any machine become unavailability. So, the application continues this execution at the restart point using the other workstations. Nevertheless the additional monitoring overhead, the conclusions show that exist advantages of monitoring the cluster when are executing a parallel programs using the MPI library with a big execution time.

Este trabalho propõe políticas para servidores Web baseados em sessões, visando ao oferecimento de garantias de qualidade de serviço (Quality of Service - QoS) a seus usuários. Para o fornecimento de QoS, dois tipos de políticas são consideradas: as responsáveis pela diferenciação de serviços e as responsáveis pelo controle de admissão. Alguns algoritmos de escalonamento foram desenvolvidos com o objetivo de oferecer melhores serviços para as sessões prioritárias: o algoritmo de escalonamento baseado em sessão (SBSA) e o algoritmo de escalonamento baseado em sessão com diferenciação de serviços (SBSA-DS). Quanto ao controle de admissão, foram consideradas duas novas políticas, as quais utilizam diferentes parâmetros para a tomada de decisão e têm como objetivo garantir a finalização do maior número de sessões prioritárias. A partir dos resultados obtidos nos experimentos realizados por meio de simulação, constatou-se que o emprego dos algoritmos e das políticas desenvolvidos melhora o atendimento das sessões para as quais deve ser oferecido um serviço preferencial. Portanto, em servidores Web preocupados com a garantia de QoS para seus usuários, os quais interagem com o sistema por meio de sessões, o uso dessas novas técnicas se mostra adequado / This work considers policies for Web servers based on sessions, aiming at the guarantees of Quality of Service (QoS) to the systems users. Two types of policies are considered: the responsible for the differentiation of services and the responsible for the admission control. Some scheduling algorithms had been developed to offer better services for the priority sessions: the Session Based Scheduling Algorithm (SBSA) and the Session Based Scheduling Algorithm with Differentiation of Services (SBSA-DS). In relation to the admission control, two new policies had been considered, which use different parameters to help the decisions and have as objective guarantee the finalization of as many priority sessions as possible. From the obtained results of the experiments realized by mean of simulation, it is evidenced that the use of the developed algorithms and policies improves the attendance of the sessions that deserve preferential service. Therefore, in Web servers worried in the guarantee the QoS for their users, which interact with the system by sessions, the use of these new techniques reveals adequate

Este trabalho apresenta e implementa um algoritmo de escalonamento para a tecnologia Foundation Fieldbus. O algoritmo denominado FFSMART escalona as mensagens de comunicação cíclica ou periódica entre os dispositivos de campo que estão no barramento fieldbus. Trata-se de um algoritmo de escalonamento pré-run-time, que permite atender às restrições de precedência dos blocos funcionais, personalizando e otimizando o uso dos recursos do sistema. O algoritmo foi implementado na linguagem de programação Visual Basic e sua validação ocorreu em um ambiente real de aplicação através de estratégias de configuração, cujos resultados foram satisfatórios. / This dissertation presents and implements a scheduling algorithm for the Foundation Fieldbus technology. The algorithm named FFSMART schedules cyclic or periodic communication messages among field devices connected to a fieldbus. The FFSMART is a pre-runtime scheduling algorithm, which allows meeting the restrictions of precedence from function blocks, customizing and optimizing the use of the system resources. The algorithm was implemented using the Visual Basic programming language and validated in a real application environment using configuration strategies, and the results were satisfactory.

Este trabalho apresenta e implementa um algoritmo de escalonamento para a tecnologia Foundation Fieldbus. O algoritmo denominado FFSMART escalona as mensagens de comunicação cíclica ou periódica entre os dispositivos de campo que estão no barramento fieldbus. Trata-se de um algoritmo de escalonamento pré-run-time, que permite atender às restrições de precedência dos blocos funcionais, personalizando e otimizando o uso dos recursos do sistema. O algoritmo foi implementado na linguagem de programação Visual Basic e sua validação ocorreu em um ambiente real de aplicação através de estratégias de configuração, cujos resultados foram satisfatórios. / This dissertation presents and implements a scheduling algorithm for the Foundation Fieldbus technology. The algorithm named FFSMART schedules cyclic or periodic communication messages among field devices connected to a fieldbus. The FFSMART is a pre-runtime scheduling algorithm, which allows meeting the restrictions of precedence from function blocks, customizing and optimizing the use of the system resources. The algorithm was implemented using the Visual Basic programming language and validated in a real application environment using configuration strategies, and the results were satisfactory.

Este trabalho propõe políticas para servidores Web baseados em sessões, visando ao oferecimento de garantias de qualidade de serviço (Quality of Service - QoS) a seus usuários. Para o fornecimento de QoS, dois tipos de políticas são consideradas: as responsáveis pela diferenciação de serviços e as responsáveis pelo controle de admissão. Alguns algoritmos de escalonamento foram desenvolvidos com o objetivo de oferecer melhores serviços para as sessões prioritárias: o algoritmo de escalonamento baseado em sessão (SBSA) e o algoritmo de escalonamento baseado em sessão com diferenciação de serviços (SBSA-DS). Quanto ao controle de admissão, foram consideradas duas novas políticas, as quais utilizam diferentes parâmetros para a tomada de decisão e têm como objetivo garantir a finalização do maior número de sessões prioritárias. A partir dos resultados obtidos nos experimentos realizados por meio de simulação, constatou-se que o emprego dos algoritmos e das políticas desenvolvidos melhora o atendimento das sessões para as quais deve ser oferecido um serviço preferencial. Portanto, em servidores Web preocupados com a garantia de QoS para seus usuários, os quais interagem com o sistema por meio de sessões, o uso dessas novas técnicas se mostra adequado / This work considers policies for Web servers based on sessions, aiming at the guarantees of Quality of Service (QoS) to the systems users. Two types of policies are considered: the responsible for the differentiation of services and the responsible for the admission control. Some scheduling algorithms had been developed to offer better services for the priority sessions: the Session Based Scheduling Algorithm (SBSA) and the Session Based Scheduling Algorithm with Differentiation of Services (SBSA-DS). In relation to the admission control, two new policies had been considered, which use different parameters to help the decisions and have as objective guarantee the finalization of as many priority sessions as possible. From the obtained results of the experiments realized by mean of simulation, it is evidenced that the use of the developed algorithms and policies improves the attendance of the sessions that deserve preferential service. Therefore, in Web servers worried in the guarantee the QoS for their users, which interact with the system by sessions, the use of these new techniques reveals adequate