Made available in DSpace on 2014-06-12T17:36:05Z (GMT). No. of bitstreams: 2 arquivo7119_1.pdf: 2897021 bytes, checksum: 6c54b56dbdc59f5e101d0042be325a2b (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2011 / Conselho Nacional de Desenvolvimento Científico e Tecnológico / O gerenciamento automático da memória dinâmica, conhecido como coleta de lixo (garbage collection), se tornou uma necessidade na maioria das linguagens de programação em uso atualmente. Dentre as técnicas para realizar o gerenciamento automático da memória, a contagem de referências se mostra vantajosa por uma série de razões, dentre elas o fato de ser uma técnica naturalmente incremental, o que evita a parada completa do processo do usuário para realizar tarefas de administração da memória. A natureza incremental da contagem de referências indica que o algoritmo pode ser adaptado para uma versão em sistemas multiprocessados, mantendo sua característica não suspensiva no programa do usuário. Entretanto, os problemas causados pela necessidade de sincronização entre threads pode anular os ganhos de eficiência obtidos com essa extensão, inviabilizando o uso de um coletor de lixo baseado em contagem de referências em um ambiente multiprocessado. Nesta tese apresenta-se um conjunto de algoritmos eficientes para utilizar a contagem de referências em sistemas com vários processadores, tendo como foco principal o algoritmo para contagem de referências para vários mutadores e um coletor. Este algoritmo foi implementado na máquina virtual Java Jikes RVM e seu desempenho testado em relação a coletores alternativos; os resultados de tais testes indicam que o algoritmo proposto tem desempenho competitivo com outros coletores similares, mas impõe tempos de pausa muito menores ao programa do usuário. A presente tese também apresenta uma prova informal da corretude do algoritmo proposto

FARIAS, P. M. S. O Problema de ordenação de rodadas e problemas de otimização associados. 2014. 127 f. (Doutorado em Ciência da Computação) - Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2014. / Submitted by Daniel Eduardo Alencar da Silva (dealencar.silva@gmail.com) on 2015-01-23T18:15:16Z No. of bitstreams: 1 2014_tese_pmsfarias.pdf: 1600516 bytes, checksum: afaccc349ce6f2d065494cd2601913c0 (MD5) / Approved for entry into archive by Rocilda Sales(rocilda@ufc.br) on 2015-09-23T16:25:51Z (GMT) No. of bitstreams: 1 2014_tese_pmsfarias.pdf: 1600516 bytes, checksum: afaccc349ce6f2d065494cd2601913c0 (MD5) / Made available in DSpace on 2015-09-23T16:25:51Z (GMT). No. of bitstreams: 1 2014_tese_pmsfarias.pdf: 1600516 bytes, checksum: afaccc349ce6f2d065494cd2601913c0 (MD5) Previous issue date: 2013 / This thesis is composed of three well-delineated parts. In the first part, we introduce the round sorting problem (RSP), which models the minimization of the usage of buffer for the temporary storage of packets to be forwarded in TDMA communications of wireless mesh networks. We present a complete foundation for the definition of the RSP, and show that the problem is NP-hard for two theoretical models of radio interference known in the literature. A mixed integer programming formulation is also presented for a purely combinatorial and applicationindependent generalization of the RSP, the SMSP problem. In the second part of the work, we deal with problems about queries on insertions into sequences of numbers. Our main result in this part of the thesis is to show how, after a preprocessing step which runs in linear time on a sequence A of arbitrary real numbers, it is possible to compute in constant time the greatest sum of a (circular or not) contiguous subsequence of the sequence which results from the insertion of a given real number x into a given position p of A. In the third part of the thesis, we use the query algorithms from the second part to obtain an efficient implementation of the GRASP metaheuristic applied to the SMSP problem. An experimental analysis of this implementation is described, in which the values of the solutions returned by the metaheuristic are compared with those of the solutions obtained through the mixed integer formulation, in the case of small instances, and with the available lower bound, in the case of larger instances. / Esta tese é composta de três partes bem-delineadas. Na primeira parte, nós introduzimos o "problema de ordenação de rodadas" (POR), que modela a minimização do uso de memória ("buffer") para o armazenamento temporário de pacotes a serem repassados em comunicações TDMA de redes de rádio em malha. Nós apresentamos uma fundamentação completa para a definição do POR, e mostramos que o problema é NP-difícil para dois modelos teóricos de interferência de rádio conhecidos na literatura. Uma formulação de programação inteira mista é também apresentada para uma generalização puramente combinatória e independente de aplicação do POR, o problema SMSP. Na segunda parte do trabalho, nós abordamos problemas de consulta sobre inserções em sequências de números. O nosso principal resultado nesta parte da tese é mostrar como, após um passo de pré-processamento que executa em tempo linear sobre uma sequência "A" de números reais quaisquer, é possível computar em tempo constante a maior soma de uma subsequência contígua (circular ou não) da sequência que resulta da inserção de dado um número real "x" numa dada posição "p" de "A". Na terceira parte da tese, nós utilizamos os algoritmos de consulta da segunda parte para obter uma implementação eficiente da meta-heurística GRASP aplicada ao problema SMSP. Uma análise experimental dessa implementação é descrita, onde os valores das soluções retornadas pela meta-heurística são comparados com os das soluções obtidas pela formulação inteira mista, no caso de instâncias pequenas, e com o limite inferior disponível, no caso de instâncias maiores.

Orientador : Prof. Dr. Carlos Alberto Maziero / Co-orientador : Prof. Dr. Luís Carlos Erpen de Bona / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 31/08/2015 / Inclui referências : f. 68-72 / Resumo: Recentemente, os discos de estado sólido (SSDs - Solid State Disks) elevaram muito o desempenho no acesso ao armazenamento secundário. Contudo, seu custo e baixa capacidade inviabilizam a substituição integral dos discos rígidos (HDDs - Hard Disk Drives) por SSDs a curto prazo, sobretudo em instalações de maior porte. Por outro lado, é possível aliar o desempenho dos SSDs à capacidade e baixo custo dos HDDs, usando SSDs como cache dos HDDs para os dados mais acessados, de forma transparente às aplicações. Essa abordagem é usada nos discos híbridos, que são HDDs com um pequeno cache interno em estado sólido, geralmente gerenciado pelo firmware do próprio disco. Também é possível usar SSDs independentes como cache de HDDs subjacentes, com o gerenciamento feito pelo sistema operacional. O núcleo Linux oferece dois subsistemas de gerenciamento de caches em SSD, DMCache e BCache, que usam abordagens e algoritmos distintos. Este trabalho avalia estes dois subsistemas em diversas configurações de SSDs, HDDs e RAID, sob diversas cargas de trabalho, com o objetivo de compreender seu funcionamento e definir diretrizes para a configuração de tais subsistemas em ambientes computacionais de médio/grande porte. Dentre os resultados apontados neste trabalho, foi verificado que em workloads mais sequenciais, como em servidores de arquivos, o uso de cache pode alcançar até 72% a mais de desempenho se comparado aos RAIDs de HDDs. Em workloads aleatórios, como em bancos de dados, o uso de caching SSD pode apresentar pouco desempenho diante de custos elevados por GB, chegando a 79%. / Abstract: Recently, Solid State Disks (SSDs) has elevated performance in secondary storage access. However, its high cost and low capacity make it impossible to fully replace Hard Disk Drives (HDDs) for SSDs in a short-term, especially in larger environments. On the other hand, it is possible to combine the performance of SSDs and low cost of HDDs, using SSDs as cache of HDDs for the most accessed data, transparently to applications. This approach is used in hybrid drives, which are HDDs with a small internal solid state cache, usually managed by device firmware itself. You can also use independent SSDs as underlying HDDs cache with the management assigned to operating system. Linux kernel offers two subsystems caches management in SSD, DMCache and BCache, using different approaches and algorithms. This work evaluates these two subsystems in various configurations of SSDs, HDDs and RAID over various arranges and workloads, in order to understand its operation in specific scenarios and set guidelines for setting up such subsystems in computing environments of medium and large scales. Among the presented results, it was found that in most sequential workloads, such as file servers, the use of cache can achieve up to 72% more performance compared to RAID of HDDs. In random workloads, such as databases, the use of SSD caching may have little performance before high costs per GB, which could reach up to 79%.

Made available in DSpace on 2015-04-11T14:02:53Z (GMT). No. of bitstreams: 1 Mauricio Tia Ni Gong Lin.pdf: 636193 bytes, checksum: f576d0b7751120d8c4eaafb2517b1e22 (MD5) Previous issue date: 2006-02-10 / The growth of Linux operating system has taken it to become a worthy competitor to commercial software such as Microsoft s Windows and Sun s Solaris. Although the development and the improvement of several Linux s features, the problem related to Linux out of memory and the current mechanism used to solve it, named as OOM Killer, has brought a long discussion at Linux kernel community. The lack of scientific works related to OOM Killer process selection algorithm motivates this dissertation to propose a mechanism for identifying and classifying memory consumption patterns of Linux applications. Such mechanism is based on a neural network technique known as Self Organizing Maps. The development of a tool based on Self Organizing Maps presented the possibility of applying such approach for memory consumption patterns classification related to Linux applications use cases. / A evolução do sistema operacional Linux possibilitou que o mesmo se tornasse o principal concorrente dos sistemas operacionais do mercado como o Windows da Microsoft e Solaris da Sun. Apesar de diversas funcionalidades e melhorias desenvolvidas no Linux, o problema relacionado à falta de memória e o mecanismo existente de solucioná-lo, chamado de OOM Killer, ainda é motivo de longas discussões na comunidade do kernel Linux. A carência de pesquisas científicas relacionada ao algoritmo de seleção de processos do OOM Killer leva esta dissertação a propor um mecanismo de identificação e classificação de padrões de consumo de memória no Linux baseada no modelo de rede neural auto-organizável. A ferramenta desenvolvida nesta dissertação mostra a possibilidade de utilizar Mapas Auto-Organizáveis para classificar e identificar os padrões de consumo de memória de determinadas aplicações inseridas em contextos de casos de uso.

FARIAS, Pablo Mayckon Silva. O problema de ordenação de rodadas e problemas de otimização associados. 2013. 127 f. Tese (Doutorado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2013. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-20T12:44:36Z No. of bitstreams: 1 2013_tese_pmsfarias.pdf: 1600516 bytes, checksum: afaccc349ce6f2d065494cd2601913c0 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-25T12:05:15Z (GMT) No. of bitstreams: 1 2013_tese_pmsfarias.pdf: 1600516 bytes, checksum: afaccc349ce6f2d065494cd2601913c0 (MD5) / Made available in DSpace on 2016-07-25T12:05:15Z (GMT). No. of bitstreams: 1 2013_tese_pmsfarias.pdf: 1600516 bytes, checksum: afaccc349ce6f2d065494cd2601913c0 (MD5) Previous issue date: 2013 / This thesis is composed of three well-delineated parts. In the first part, we introduce the round sorting problem (RSP), which models the minimization of the usage of buffer for the temporary storage of packets to be forwarded in TDMA communications of wireless mesh networks. We present a complete foundation for the definition of the RSP, and show that the problem is NP-hard for two theoretical models of radio interference known in the literature. A mixed integer programming formulation is also presented for a purely combinatorial and applicationindependent generalization of the RSP, the SMSP problem. In the second part of the work, we deal with problems about queries on insertions into sequences of numbers. Our main result in this part of the thesis is to show how, after a preprocessing step which runs in linear time on a sequence A of arbitrary real numbers, it is possible to compute in constant time the greatest sum of a (circular or not) contiguous subsequence of the sequence which results from the insertion of a given real number x into a given position p of A. In the third part of the thesis, we use the query algorithms from the second part to obtain an efficient implementation of the GRASP metaheuristic applied to the SMSP problem. An experimental analysis of this implementation is described, in which the values of the solutions returned by the metaheuristic are compared with those of the solutions obtained through the mixed integer formulation, in the case of small instances, and with the available lower bound, in the case of larger instances. / Esta tese é composta de três partes bem-delineadas. Na primeira parte, nós introduzimos o "problema de ordenação de rodadas" (POR), que modela a minimização do uso de memória ("buffer") para o armazenamento temporário de pacotes a serem repassados em comunicações TDMA de redes de rádio em malha. Nós apresentamos uma fundamentação completa para a definição do POR, e mostramos que o problema é NP-difícil para dois modelos teóricos de interferência de rádio conhecidos na literatura. Uma formulação de programação inteira mista é também apresentada para uma generalização puramente combinatória e independente de aplicação do POR, o problema SMSP. Na segunda parte do trabalho, nós abordamos problemas de consulta sobre inserções em sequências de números. O nosso principal resultado nesta parte da tese é mostrar como, após um passo de pré-processamento que executa em tempo linear sobre uma sequência "A" de números reais quaisquer, é possível computar em tempo constante a maior soma de uma subsequência contígua (circular ou não) da sequência que resulta da inserção de dado um número real "x" numa dada posição "p" de "A". Na terceira parte da tese, nós utilizamos os algoritmos de consulta da segunda parte para obter uma implementação eficiente da meta-heurística GRASP aplicada ao problema SMSP. Uma análise experimental dessa implementação é descrita, onde os valores das soluções retornadas pela meta-heurística são comparados com os das soluções obtidas pela formulação inteira mista, no caso de instâncias pequenas, e com o limite inferior disponível, no caso de instâncias maiores.

A virtualização é uma tecnologia chave para a computação em nuvem que permite fornecer recursos computacionais, em forma de máquinas virtuais, para o consumo de serviços de computação. Nos ambientes de computação em nuvem, é importante manter sob controle a alocação de máquinas virtuais nos servidores físicos. Uma alocação adequada implica na redução de custos com hardware, energia e refrigeração, além da melhora da qualidade de serviço. Hipervisores recentes implementam mecanismos para reduzir o consumo de memória RAM através do compartilhamento de páginas idênticas entre máquinas virtuais. Esta dissertação apresenta um novo algoritmo de alocação de máquinas virtuais que busca o equilíbrio no uso dos recursos de CPU, memória, disco e rede e, sobretudo, considera o potencial de compartilhamento de memória entre máquinas virtuais. Através de simulações em cenários distintos, verificou-se que o algoritmo é superior à abordagem padrão na questão do uso equilibrado de recursos e que, considerando o compartilhamento de memória, houve um ganho significativo na disponibilidade deste recurso ao final das alocações. / Virtualization is a key technology for cloud computing, it provides computational resources as virtual machines for consumption of computing services. In cloud computing environments it is important to keep under control the allocation of virtual machines in physical servers. A good allocation brings benefits such as reduction costs in hardware, power, and cooling, also improving the quality of service. Recent hypervisors implement mechanisms to reduce RAM consumption by sharing identical pages between virtual machines. This dissertation presents a new algorithm for virtual machines allocation that seeks the balanced use of CPU, memory, disk, and network. In addition, it considers the potential for sharing memory among virtual machines. Simulations on three distinct scenarios demonstrate that it is superior to the standard approach when considering the balanced use of resources. Considering shared memory, there was an appreciable gain in availability of resources.

A crescente demanda por ambientes de virtualização de larga escala, como os usados em datacenters e nuvens computacionais, faz com que seja necessário um gerenciamento eficiente dos recursos computacionais utilizados. Um dos recursos mais exigidos nesses ambientes é a memória RAM, que costuma ser o principal fator limitante em relação ao número de máquinas virtuais que podem executar sobre o mesmo host físico. Recentemente, hipervisores trouxeram mecanismos de compartilhamento transparente de memória RAM entre máquinas virtuais, visando diminuir a demanda total de memória no sistema. Esses mecanismos “fundem” páginas idênticas encontradas nas várias máquinas virtuais em um mesmo quadro de memória física, usando uma abordagem copy-on-write, de forma transparente para os sistemas convidados. O objetivo deste estudo é apresentar uma visão geral desses mecanismos e também avaliar seu desempenho e efetividade. São apresentados resultados de experimentos realizados com dois hipervisores populares (VMware e KVM), usando sistemas operacionais convidados distintos (Linux e Windows) e cargas de trabalho diversas (sintéticas e reais). Os resultados obtidos evidenciam diferenças significativas de desempenho entre os hipervisores em função dos sistemas convidados, das cargas de trabalho e do tempo. / The growing demand for large-scale virtualization environments, such as the ones used in cloud computing, has led to a need for efficient management of computing resources. RAM memory is the one of the most required resources in these environments, and is usually the main factor limiting the number of virtual machines that can run on the physical host. Recently, hypervisors have brought mechanisms for transparent memory sharing between virtual machines in order to reduce the total demand for system memory. These mechanisms “merge” similar pages detected in multiple virtual machines into the same physical memory, using a copy-on-write mechanism in a manner that is transparent to the guest systems. The objective of this study is to present an overview of these mechanisms and also evaluate their performance and effectiveness. The results of two popular hypervisors (VMware and KVM) using different guest operating systems (Linux and Windows) and different workloads (synthetic and real) are presented herein. The results show significant performance differences between hypervisors according to the guest system workloads and execution time.