Thesis (B.S.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1982. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING / Includes bibliographical references. / by David Lui. / B.S.

O trabalho em torno do sistema TRIX visa desenvolver um sistema operacional multiprocessado experimental, para servir de base a futuros trabalhos de pesquisa em sistemas operacionais e processamento paralelo. Como características essenciais do sistema tem-se simplicidade, desempenho e compatibilidade com UNIX. Com o sistema operando em vários processadores, pode-se fazer experiências de muitos tipos em processamento paralelo, como por exemplo, ensaios de distribuição de carga, avaliações de desempenho, implementação de linguagens paralelas ou distribuídas, ,bancos de dados, sistemas dedicados, etc. Ao construir o sistema TRIX, decidiu-se usar o código fonte de um sistema já pronto e funcionando, para encurtar o tempo de desenvolvimento. Optou-se pelo MINIX, que é um sistema bem estruturado, dividido em camadas de processos seqüenciais que se comunicam por troca de mensagens. Mais que isso, 0 MEND( a compatível com o UNIX versão 7 e o seu c6digo fonte pode ser usado para fins acadêmicos sem ferir o seu Copyright. Foi necessário porem dotar o MINIX de características distribuídas, para o controle de uma arquitetura multiprocessada. projeto e implementação destas características é o assunto deste trabalho. Inicialmente são avaliados os sistemas operacionais multiprocessados encontrados na literatura, de maneira a auxiliar no projeto do TRIX. Entre os detalhes estudados estão as diferenças entre sistemas paralelos e distribuídos, a comunicação entre seus processos e sua forma de distribuição. São apresentados os microprocessadores do tipo transputer, com seus mecanismos de criação e comunicação de processos implementados em hardware. Também é detalhado o sistema operacional MINIX, com sua construção em camadas, com processos servidores e clientes e suas estruturas de controle. 0 sistema foi projetado tentando maximizar a sua flexibilidade, escalabilidade e disponibilidade e minimizar sua complexidade. Os processos servidores são divididos de forma fixa, controlando as funções de memória localmente e as funções de arquivos remotamente. Os processos de usuário são distribuídos tentando se equalizar a taxa de ocupação dos processadores do sistema. E implementado um mecanismo de identificação global de processos juntamente com um método transparente de comunicação. Isso é feito junto com a criação de um driver suplementar ao sistema, responsável pela comunicação entre processos de processadores distintos. O núcleo original do MINIX recebeu uma serie de alterações para suportar as características distribuídas do novo sistema, de maneira a identificar processos locais e remotos. Foram extraídas do núcleo as funções executadas pelo escalonador em hardware do transputer. Foram inseridas algumas funções novas para tratar de algumas idiosincrasias do transputer, como por exemplo, sua falta de gerencia de memória. Finalmente, foi criado um mecanismo distribuído para controlar a arvore de processos do sistema, mantendo a semântica do UNIX. A escolha do processador para a execução de novos processos 6 feita pelo processador que o estiver criando, através de informações recebidas sobre processadores menos ocupados que estiverem mais próximos. / The TIUX system has been defined as an experimental operating system, to be used in future research on operating systems and parallel processing. The essential characteristics of the system are simplicity, performance and uNix compatibility. With the system running on several processors, several topics can be studied, such as load balancing, performance evaluation, implementation of distributed or parallel programming languages, distributed data bases and embedded systems. While designing the TRix system, it was decided to use the source code of an existing system, to shorten the development time. MINIX was chosen, because it is a well structured system, divided into layers of sequential processes, which communicate via messages. MINIX is compatible with UNIX version 7 and its source code can be used for academic purposes without any copyright infringiment. It had to be extended to control a multiprocessor architecture. The implementation of these characteristics is the main subject of this work. Initially some existing multiprocessor operating systems are evaluated, in order to guide in the development of TRIX. The studied issues are differences between parallel and distributed systems, interprocess communication features and the process distribution policy. The transputer microprocessors are presented, with their hardware implemented devices for process creation and communication. The MINIX operating system layered structure is described, with client and server processes and their control structures. The system is projected as an attempt to maximize flexibility, scalability and availability and to minimize complexity. The server processes are distributed in a fixed layout, controlling the memory and processes locally, and the files remotely. The user processes are distributed with load balancing among the processors. Global identification and transparent communication are implemented. This is achieved with an additional device driver, responsible for communication between processes running on different processors. The original MINIX kernel was changed to support the new distributed features of the system, identifying processes globally. The scheduler functions were stripped off, as they are now performed by the transputer hardware. Some functions were inserted to deal with some transputer problems, as for example, the lack of a memory management unit. Finally, a mechanism to control the global system process tree was created, maintaning strict UNIX semantics. The choice of which processor will hold a newly created process is made by the processor creating it, based on information received about the nearer processor with a low load.

Este trabalho se inicia com uma discussão sobre as principais características dos Sistemas de Arquivos Distribuídos, ou seja, espaço de nomes, localização, cache, consistência, replicação, disponibilidade, escalabilidade, heterogeneidade, tolerância a falhas e segurança. Analisamos diversos sistemas de arquivos existentes quanto a estas características dando especial atenção aos sistemas NFS, Andrew, Coda, Sprite, Zebra, Harp, Frolic e Echo. Descrevemos alguns modelos analíticos para o comportamento de sistemas de arquivos distribuídos e, em seguida, apresentamos um novo modelo para sistemas baseados em leases - um mecanismo para a garantia de consistência em sistemas distribuídos. Finalmente, descrevemos a nossa implementação do sistema de arquivos distribuído SODA - que utiliza leases - apresentando dados sobre o seu desempenho. / We begin with a discussion of some of the main characteristics of Distributed File Systems, namely locality, name space, cache, consistency, replication, availability, scalability, heterogeneity, fault tolerance and security. We analyze several file systems based on these characteristics. We focus mainly on NFS, Andrew, Coda, Sprite, Zebra, Harp, Frolic, and Echo. We then describe some analytical models of the behavior of distributed file systems. After that we present a new model of systems based on leases - a mechanism to assure consistency on a distributed system. Finally we describe our implementation of the SODA distributed file system - which uses leases - presenting some results on its performance.

[pt] A evolução das técnicas de codificação de mídias contínuas vem tornando cada vez mais difundido o uso de aplicações multimídia distribuídas. Esse tipo de aplicação possui requisitos de desempenho que devem ser atendidos de modo fima- fim, funcionalidade somente alcançada se mecanismos de provisão de qualidade de serviço (QoS) forem aplicados a todos os subsistemas participantes do serviço. Esses mecanismos buscam proporcionar algum controle no compartilhamento dos recursos distribuídos, mas a heterogeneidade de recursos e plataformas torna tal gerenciamento uma tarefa muito complexa. A uniformização do acesso aos recursos representa um ponto-chave na solução do problema, ao oferecer abstrações independentes de plataforma e que possam representar não somente um recurso qualquer, mas também a distribuição deles. Deve- se considerar, ainda, a evolução contínua das aplicações, que gera demanda por mecanismos adaptáveis, e a participação de múltiplos atores, que gera demanda por ambientes cooperativos de configuração e manutenção de recursos. O presente trabalho propõe uma técnica de gerenciamento de recursos com suporte a QoS fim-a-fim denominada MDRM (gerenciamento de recursos dirigido por modelos), inspirada nos processos e conceitos de MDSD (desenvolvimento de software dirigido por modelos). Particularmente, MDRM inclui a especificação de um meta modelo próprio, denominado Árvores de Recursos Virtuais (VRT), responsável por oferecer as abstrações necessárias para o preenchimento dos requisitos de uniformização, interoperabilidade, adaptabilidade e cooperação na construção de modelos de gerenciamento de recursos. Os modelos de gerenciamento de recursos são instâncias do meta modelo especificados por meio de uma linguagem de domínio específico (DSL), chamada Pan. Pan é capaz de expressar o formalismo de VRT em código independente de plataforma, oferecendo uma notação de fácil assimilação pelos atores possivelmente presentes em ambientes distribuídos em geral. MDRM prevê, ainda, o projeto de ambientes de modelagem compostos por ferramentas que auxiliam os processos de validação, transformação e implantação de modelos de gerenciamento de recursos. Os construtos da linguagem Pan permitem que as mesmas ferramentas sejam também usadas na manutenção de modelos já instanciados, de forma que ações de adaptação possam ser prontamente refletidas nas plataformas envolvidas. Um framework para suporte a MDRM em sistemas operacionais de propósito geral também é apresentado, no intuito de exemplificar como os conceitos do meta modelo VRT devem ser espelhados internamente às plataformas-alvo. / [en] The evolution of codification techniques for continuous media is making distributed multimedia applications even more popular. This kind of application has performance requirements that must be met in an end-to-end fashion, which can be achieved only if quality-of-service (QoS) provisioning mechanisms are applied on each participant subsystem. These mechanisms try to provide some control on distributed resource sharing, but the heterogeneity of resources and platforms turns management into a very complex task. Uniformization of resource access plays a key role to solve the problem, as it provides platform-independent abstractions that can represent not only a given resource, but also the distribution of them. It is also important to consider the continuous evolution of applications, which creates a demand for adaptable mechanisms, and the participation of multiple actors, which creates a demand for cooperative environments for resource configuration and maintenance. This work proposes a technique for resource management with end-to-end QoS support called MDRM (model-driven resource management), inspired on MDSD´s (model-driven software development) concepts and processes. Particularly, MDRM includes the specification of its own meta model, called Virtual Resource Trees (VRT), which provides the abstractions needed to address uniformization, interoperability, adaptability and cooperation requirements on building resource management models. Resource management models are instances of the meta model specified using a domain-specific language (DSL) called Pan. Pan is able to express the formalism of VRT as platform-independent code, providing an easy to learn notation for any actors possibly present on general distributed environments. MDRM also considers the design of modeling environments composed of tools that help on validation, transformation and deployment of resource management models. The constructs of the Pan language allow the same tools to be used for maintenance of models already instantiated, and thus adaptation actions can be promptly propagated to concerned platforms. A framework for MDRM support on general-purpose operating systems is also presented to illustrate how the concepts of the VRT meta model must be mirrored internally in target platforms.

Our thesis is that operating systems should manage the on-chip shared caches of multicore processors for the purposes of achieving performance gains. Consequently, this dissertation demonstrates how the operating system can profitably manage these shared caches. Two shared-cache management principles are investigated: (1) promoting shared use of the shared cache, demonstrated by an automated online thread clustering technique, and (2) providing cache space isolation, demonstrated by a software-based cache partitioning technique. In support of providing isolation, cache provisioning is also investigated, demonstrated by an automated online technique called RapidMRC. We show how these software-based techniques are feasible on existing multicore systems with the help of their hardware performance monitoring units and their associated hardware performance counters. On a 2-chip IBM POWER5 multicore system, promoting sharing reduced processor pipeline stalls caused by cross-chip cache accesses by up to 70%, resulting in performance improvements of up to 7%. On a larger 8-chip IBM POWER5+ multicore system, the potential for up to 14% performance improvement was measured. Providing isolation improved performance by up to 50%, using an exhaustive offline search method to determine optimal partition size. On the other hand, up to 27% performance improvement was extracted from the corresponding workload using an automated online approximation technique, made possible by RapidMRC.

Our thesis is that operating systems should manage the on-chip shared caches of multicore processors for the purposes of achieving performance gains. Consequently, this dissertation demonstrates how the operating system can profitably manage these shared caches. Two shared-cache management principles are investigated: (1) promoting shared use of the shared cache, demonstrated by an automated online thread clustering technique, and (2) providing cache space isolation, demonstrated by a software-based cache partitioning technique. In support of providing isolation, cache provisioning is also investigated, demonstrated by an automated online technique called RapidMRC. We show how these software-based techniques are feasible on existing multicore systems with the help of their hardware performance monitoring units and their associated hardware performance counters. On a 2-chip IBM POWER5 multicore system, promoting sharing reduced processor pipeline stalls caused by cross-chip cache accesses by up to 70%, resulting in performance improvements of up to 7%. On a larger 8-chip IBM POWER5+ multicore system, the potential for up to 14% performance improvement was measured. Providing isolation improved performance by up to 50%, using an exhaustive offline search method to determine optimal partition size. On the other hand, up to 27% performance improvement was extracted from the corresponding workload using an automated online approximation technique, made possible by RapidMRC.

The explosive growth in networked systems and applications and the increase in device capabilities (as evidenced by the availability of inexpensive multimedia devices) enable novel complex distributed applications, including video conferencing, on-demand computing services, and virtual environments. These applications' need for high performance, real-time, or reliability requires the provision of Quality of Service (QoS) guarantees along the path of information exchange between two or more communicating systems. Execution environments that are prone to dynamic variability and uncertainty make QoS provision a challenging task, e.g., changes in user behavior, resource requirements, resource availabilities, or system failures are difficult or even impossible to predict. Further, with the coexistence of multiple adaptation techniques and resource management mechanisms, it becomes increasingly important to provide an integrated or cooperative approach to distributed QoS management. This work's goals are the provision of system-level tools needed for the efficient integration of multiple adaptation approaches available at different layers of a system (e.g., application-level, operating system, or network) and the use of these tools such that distributed QoS management is performed efficiently with predictable results. These goals are addressed constructively and experimentally with the Q-Fabric architecture, which provides the required system-level mechanisms to efficiently integrate multiple adaptation techniques. The foundation of this integration is the event-based communication implemented by it, realizing a loosely-coupled group communication approach frequently found in multi-peer applications. Experimental evaluations are performed in the context of a mobile multimedia application, where the focus is directed toward efficient energy consumption on battery-operated devices. Here, integration is particularly important to prevent multiple energy management techniques found on modern mobile devices to negate the energy savings of each other.

Aspect-oriented programming, component models, and design patterns are modern and actively evolving techniques for improving the modularization of complex software. In particular, these techniques hold great promise for the development of "systems infrastructure" software, e.g., application servers, middleware, virtual machines, compilers, operating systems, and other software that provides general services for higher-level applications. The developers of infrastructure software are faced with increasing demands from application programmers needing higher-level support for application development. Meeting these demands requires careful use of software modularization techniques, since infrastructural concerns are notoriously hard to modularize. Aspects, components, and patterns provide very different means to deal with infrastructure software, but despite their differences, they have much in common. For instance, component models try to free the developer from the need to deal directly with services like security or transactions. These are primary examples of crosscutting concerns, and modularizing such concerns are the main target of aspect-oriented languages. Similarly, design patterns like Visitor and Interceptor facilitate the clean modularization of otherwise tangled concerns. Building on the ACP4IS meetings at AOSD 2002-2009, this workshop aims to provide a highly interactive forum for researchers and developers to discuss the application of and relationships between aspects, components, and patterns within modern infrastructure software. The goal is to put aspects, components, and patterns into a common reference frame and to build connections between the software engineering and systems communities.

Aspect-oriented programming, component models, and design patterns are modern and actively evolving techniques for improving the modularization of complex software. In particular, these techniques hold great promise for the development of "systems infrastructure" software, e.g., application servers, middleware, virtual machines, compilers, operating systems, and other software that provides general services for higher-level applications. The developers of infrastructure software are faced with increasing demands from application programmers needing higher-level support for application development. Meeting these demands requires careful use of software modularization techniques, since infrastructural concerns are notoriously hard to modularize. Aspects, components, and patterns provide very different means to deal with infrastructure software, but despite their differences, they have much in common. For instance, component models try to free the developer from the need to deal directly with services like security or transactions. These are primary examples of crosscutting concerns, and modularizing such concerns are the main target of aspect-oriented languages. Similarly, design patterns like Visitor and Interceptor facilitate the clean modularization of otherwise tangled concerns. Building on the ACP4IS meetings at AOSD 2002-2009, this workshop aims to provide a highly interactive forum for researchers and developers to discuss the application of and relationships between aspects, components, and patterns within modern infrastructure software. The goal is to put aspects, components, and patterns into a common reference frame and to build connections between the software engineering and systems communities.

The reliability of RFID systems depends on a number of factors including: RF interference, deployment environment, configuration of the readers, and placement of readers and tags. While RFID technology is improving rapidly, a reliable deployment of this technology is still a significant challenge impeding wide-spread adoption. This research investigates system software solutions for achieving a highly reliable deployment that mitigates inherent unreliability in RFID technology. We have considered two different problem domains for large scale RFID deployment. One is item tracking and the other is guidance-monitoring. Item tracking considers applications that have statically placed RFID readers to observe the RFID tagged objects in motion. An airport scenario to observe the tagged baggage or warehouse scenarios to track the tagged goods are examples of item tracking applications. A self guided tour, search and rescue scenario or a visually impaired person looking for direction and guidance in a tagged environment are examples of item location applications. It is observed that there is a notion of path that follows the direction and flow of the mobile items in the item tracking applications and a path gets created along the direction and flow of the mobile object in item location applications. A system level knowledge of the data flow can benefit the system in different aspects such as improved reliability, resource management and real time response. We have designed and implemented an RFID middleware for item tracking: RF²ID (Reliable Framework for Radio Frequency Identification) to organize and support queries over data streams in an efficient manner. We have developed (1) a virtual reader abstraction to improve the potentially error-prone nature of reader generated data (2) a novel path abstraction to capture the logical flow of information among virtual readers. Prototype implementation using both RFID readers and simulated readers using an empirical model of RFID readers show that RF²ID is able to provide high reliability, support path-based object detection and use efficient resource management techniques. We propose a middleware solution that takes into account the data flow information for item location application that requires real time response. The guidance-monitoring scenario considers mobile RFID readers that traverse in a tagged environment. We consider the scenario of an Assisted Living Center for elderly residents as a motivating guidance-monitoring application. The solution for guidance-monitoring system is called GuardianAngel. The application scenario considers a tagged indoor environment with residents having their own RFID readers to provide them with adequate information about the surroundings. The guidance and monitoring requirement can be conflicting. The guidance information requires very fine grain information about the environment to make proper decisions. On the other hand, the monitoring system must not have a fine grain knowledge which can introduce concerns such as privacy concerns. We consider this aspect during the design and implementation. The system is a two layered infrastructure that has the upper layer which is the monitoring layer. This layer is in charge of monitoring of the actors in the environment. The monitoring layer is physically a set of distributed virtual stations that have the knowledge about the environment. The environment itself is equipped with RFID tags. The residents of the environment have the mobile object that has a sensing element and a computing element (e.g., handhold device with a portable RFID reader) - the guidance server runs on this mobile object. The guidance server is in charge of making local decisions to the users. It is resource limited and asks for new information from the virtual stations as needed. The guidance server also provides the monitoring server with the information regarding the status of the mobile object. But the status information is not fine grain information - the guidance server wraps up the information over a period of time and over a larger region to hide the detailed information of the users.The system uses the logical path based abstraction to guide the users. We have implemented the real testbed using grid structured RFID devices along with scalability study using emulated RFID readers. The basic contribution of our work is based on providing novel middleware solution that is able to serve the application taking into account the inherent unreliability of RFID technology. Our path abstraction that uses the physical flow of data as an ally to generate a logical system level flow enhances the performance in many ways.