Zhang, Yupeng. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2013. / Includes bibliographical references (leaves 45-48). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts also in Chinese.

O advento dos computadores pessoais e posteriormente das estações de trabalho, somado ao desenvolvimento de hardware de comunicação eficiente e de baixo custo, levou a popularização das redes locais. Entretanto, o software não presenciou o mesmo desenvolvimento do hardware, especialmente devido a complexidade dos sistemas distribuídos. A heterogeneidade das máquinas, sistemas e redes, inerente aos ambientes computacionais modernos, restringe igualmente a integração e cooperação entre os nodos disponíveis. 0 objetivo do presente trabalho é, a partir da análise dos principais aspectos relacionados à distribuição e à heterogeneidade, desenvolver um sistema operacional de rede heterogêneo. Tal sistema, denominado HetNOS (de Heterogeneous Network Operating System), permite o desenvolvimento e validação de aplicações distribuídas homogêneas e heterogêneas de forma rápida e fácil. Os usuários podem concentrar-se nos aspectos de distribuição dos algoritmos, abstraindo detalhes dos mecanismos de comunicação, pois a programação de aplicações distribuídas é baseada em uma plataforma de interface homogênea, fácil de usar e com independência de localidade. Sendo um sistema operacional de rede, o HetNOS atua sobre o conjunto de sistemas operacionais nativos existentes; o ambiente de trabalho e estendido e não substituído. Não há entidades nem informações centralizadas, e os algoritmos são distribuídos, usualmente resultando maior confiabilidade e desempenho. A topologia do sistema é um anel lógico, esquema justificado pela generalidade de tal configuração e pela simplificação do projeto do núcleo distribuído do HetNOS. O paradigma de comunicação entre módulos e a troca de mensagens, mecanismo implementado sobre a interface de programação em rede sockets. Não há compartilhamento de memória em nenhuma instância, tornando o sistema mais legível, manutenível e portável. A interpelação entre módulos fica restrita à interface de mensagens definidas e aceitas por cada módulo. A arquitetura do HetNOS é estruturada e distribuída, pois o sistema é composto de camadas hierárquicas subdivididas em módulos, estes implementados com processos. O nível 1 corresponde ao conjunto de núcleos de sistemas operacionais nativos suportados, sobre o qual é implementado o núcleo distribuído heterogêneo do HetNOS, a DCL (Distributed Computing Layer). O principal serviço fornecido pela DCL (executada no nível 2), é um subsistema de troca de mensagens canônico e independente de localidade. Processos servidores e de usuários podem utilizar as mais variadas formas de comunicação por mensagens, tal como envio, recepção e propagação de mensagens síncronas, assíncronas, bloqueantes e não bloqueantes. No nível 3 estão os servidores do sistema, que estendem e implementam de forma distribuída a funcionalidade do sistema nativo. O Servidor de Nomes é o repositório global de dados, servindo a processos do sistema e de usuários. O Servidor de Autorização implementa o esquema de controle no acesso a recursos do sistema. O Servidor de Tipos permite que aplicações copiem dados estruturados de forma independente de localidade e de arquitetura. Por fim, o Servidor de Arquivos estende os serviços (de arquivos) locais de forma a integrá-los em um único domínio (espaço). No nível 4, arquiteturas e sistemas operacionais são emulados por módulos interpretadores (denominados Emulators). Aplicações de usuários estão espalhadas dos níveis 2 a 5; a camada varia com o tipo de aplicação. Para demonstrar a viabilidade do sistema, implementou-se a estrutura fundamental do HetNOS, incluindo a DCL (um núcleo distribuído heterogêneo), a versões básicas dos módulos servidores, as bibliotecas de procedimentos, além de diversos tipos de aplicações. O sistema conta hoje com mais de 25.000 linhas de código fonte C em mais de 100 arquivos. O desempenho do subsistema de comunicação implementado pela DCL (em avaliações com diferentes configurações de hardware) superou as expectativas iniciais, mas ainda está muito aquém do necessário a aplicações distribuídas. Segundo o que indicam as primeiras experiências realizadas, o HetNOS será bastante útil na prototipação e avaliação de modelos distribuídos, assim como na programação de software distribuído homogêneo e heterogêneo. Projetos de pesquisa do CPGCC envolvendo sistemas distribuídos (p.ex., tolerância a falhas e simulações) podem utilizar o HetNOS como ferramenta para implementação e validação de seus modelos. Futuramente, aplicações distribuídas e paralelas de maior porte poderão ser programadas, como sistemas de gerencia de bases de dados distribuídas, simuladores e sistemas de controle para automação industrial. / The advent of personal computers and, later, of workstations, along with the development of efficient and low-cost communication hardware has led to the popularization of local-area networks. However, distributed software did not experiment the same development of hardware, specially due to the complexity of distributed systems. The machine, system and communication network heterogeneity, inherent to the modern computing environments, is also responsible for the lack of integration and cooperation of available nodes. The purpose of this work is, from the analysis of the main aspects related to distribution and heterogeneity, to design a heterogeneous network operating system. Such system, named HetNOS (which stands for Heterogeneous Network Operating System), allows users to quickly write and validate distributed homogeneous and heterogeneous applications. Users can concentrate their work in the distributed aspects, abstracting communication mechanisms' details, because programming of distributed applications is based on a homogeneous interface platform, easy to use and location-independent. Being a network operating system, HetNOS acts over the set of native operating systems; the environment is extended instead of substituted. There are neither centralized information nor entities, and the algorithms are always distributed, usually yielding more reliability and performance. The HetNOS topology is a logical ring, scheme adopted partly due to the generality of such configuration and partly to simplify the HetNOS distributed kernel design. The communication paradigm between modules is the message exchange, a mechanism implemented over the sockets network application programming interface. There is no shared memory at all, making the system clearer, more manutible and portable. The interrelation between modules is restricted to the message interface defined and accepted by a module. The HetNOS architecture is structured and distributed, as the system is composed of hierarchical layers divided into modules, which in their turn are realized as processes. The layer 1 is the set of native operating system kernels, over which is implemented the distributed heterogeneous HetNOS kernel, namely DCL (states for Distributed Computing Layer). The main service provided by DCL (in layer 2) is a canonical, location-independent, message exchange mechanism. Server and user processes may use multiple forms of message primitives, such as synchronous, asynchronous, blocking and non-blocking send and receive. In the layer 3 are the system servers, which extend and implement in a distributed way the functionality of native systems. The name server is a global data repository, serving other system and user processes. The authorization server implements the security scheme to control the access to the system resources. The type server allows applications to transfer structured data independently of location and architecture. Finally, the file server extends the local (file) services to integrate them into a unique domain (space). In the layer 4, architectures and operating systems are emulated by interpreter modules (named Emulators). User applications are spread over the layers 2 to 5, depending on the application type. In order to prove the system viability, the fundamental HetNOS structure has been implemented, including its distributed heterogeneous kernel, the base of server modules, the procedure libraries, and several types of applications. The system source code has over 25,000 lines of C programming distributed over a hundred files. Although the optimization is an endless process, the performance of the DCL communication subsystem (evaluated using a few different hardware configurations) overestimated initial predictions, but is weak if considered the requirements to distributed processing. Accordingly to the first experiences made, HetNOS will be of great value to evaluate and prototype distributed models, as well as to the programming of homogeneous and heterogeneous distributed software. Local research projects involving distributed systems (e.g., fault tolerance and simulations) may use HetNOS as a tool to validate and implement their models. In the future, more complex distributed and parallel applications will be programmed, such as a distributed database management system, simulators and factory automation control systems.

A paradigm is presented for the parallelization of coarse-grain engineering and scientific applications. The coordination framework provides structure and an organizational strategy for a parallel solution in a distributed environment. Three categories of primitives which define the coordination framework are presented: structural, transformational. and operational. The prototype of the paradigm presented in this thesis is the first step towards a programming development tool. This tool will allow non-specialist programmers to parallelize existing sequential solutions through the distribution, synchronization and collection of tasks. The distributed control, multidimensional pipeline characteristics of the paradigm provide advantages which include load balancing through the use of self-directed workers, a simplified communication scheme ideally suited for infrequent task interaction, a simple programmer interface, and the ability of the programmer to use already existing code. Results for the parallelization of SPICE3Cl in a distributed system of fifteen SUN 3 workstations with one fileserver demonstrate linear speedup with slopes ranging from 0.7 to 0.9. A high-level abstraction of the system is presented in the form of a closed, single class, queuing network model. Using the Mean Value Analysis solution technique from queuing network theory, an expression for total execution time is obtained and is shown to be consistent with the well known Amdahl's Law. Our expression is in fact a refinement of Amdahl's Law which realistically captures the limitations of the system. We show that the portion of time spent executing serial code which cannot be enhanced by parallelization is a function of N, the number of workers in the system. Experiments reveal the critical nature of the communication scheme and the synchronization of the paradigm. Investigation of the synchronization center indicates that as N increases, visitations to the center increase and degrade system performance. Experimental data provides the information needed to characterize the impact of visitations on the perfoimance of the system. This characterization provides a mechanism for optimizing the speedup of an application. It is shown that the model replicates the system as well as predicts speedup over an extended range of processors, task count, and task size.

Distributed Shared Memory (DSM) provides programmers with a shared memory environment in systems where memory is not physically shared. Clusters of Workstations (COWs), an often untapped source of computing power, are characterised by a very low cost/performance ratio. The combination of Clusters of Workstations (COWs) with DSM provides an environment in which the programmer can use the well known approaches and methods of programming for physically shared memory systems and parallel processing can be carried out to make full use of the computing power and cost advantages of the COW. The aim of this research is to synthesise and develop a distributed shared memory system as an integral part of an operating system in order to provide application programmers with a convenient environment in which the development and execution of parallel applications can be done easily and efficiently, and which does this in a transparent manner. Furthermore, in order to satisfy our challenging design requirements we want to demonstrate that the operating system into which the DSM system is integrated should be a distributed operating system. In this thesis a study into the synthesis of a DSM system within a microkernel and client-server based distributed operating system which uses both strict and weak consistency models, with a write-invalidate and write-update based approach for consistency maintenance is reported. Furthermore a unique automatic initialisation system which allows the programmer to start the parallel execution of a group of processes with a single library call is reported. The number and location of these processes are determined by the operating system based on system load information. The DSM system proposed has a novel approach in that it provides programmers with a complete programming environment in which they are easily able to develop and run their code or indeed run existing shared memory code. A set of demanding DSM system design requirements are presented and the incentives for the placement of the DSM system with a distributed operating system and in particular in the memory management server have been reported. The new DSM system concentrated on an event-driven set of cooperating and distributed entities, and a detailed description of the events and reactions to these events that make up the operation of the DSM system is then presented. This is followed by a pseudocode form of the detailed design of the main modules and activities of the primitives used in the proposed DSM system. Quantitative results of performance tests and qualitative results showing the ease of programming and use of the RHODOS DSM system are reported. A study of five different application is given and the results of tests carried out on these applications together with a discussion of the results are given. A discussion of how RHODOS’ DSM allows programmers to write shared memory code in an easy to use and familiar environment and a comparative evaluation of RHODOS DSM with other DSM systems is presented. In particular, the ease of use and transparency of the DSM system have been demonstrated through the description of the ease with which a moderately inexperienced undergraduate programmer was able to convert, write and run applications for the testing of the DSM system. Furthermore, the description of the tests performed using physically shared memory shows that the latter is indistinguishable from distributed shared memory; this is further evidence that the DSM system is fully transparent. This study clearly demonstrates that the aim of the research has been achieved; it is possible to develop a programmer friendly and efficient DSM system fully integrated within a distributed operating system. It is clear from this research that client-server and microkernel based distributed operating system integrated DSM makes shared memory operations transparent and almost completely removes the involvement of the programmer beyond classical activities needed to deal with shared memory. The conclusion can be drawn that DSM, when implemented within a client-server and microkernel based distributed operating system, is one of the most encouraging approaches to parallel processing since it guarantees performance improvements with minimal programmer involvement.

Thesis (M.S.)--Mississippi State University. Department of Computer Science and Engineering. / Title from title screen. Includes bibliographical references.

Thesis (M. Phil.)--University of Hong Kong, 2002. / Includes bibliographical references (leaves 63-65).

This dissertation presents techniques for detecting and tolerating faults in distributed systems. Detecting faults in distributed or parallel systems is often very difficult. We look at the problem of determining if a property or assertion was true in the computation. We formally define a logic called BTL that can be used to define such properties. Our logic takes temporal properties in consideration as these are often necessary for expressing conditions like safety violations and deadlocks. We introduce the idea of a basis of a computation with respect to a property. A basis is a compact and exact representation of the states of the computation where the property was true. We exploit the lattice structure of the computation and the structure of different types of properties and avoid brute force approaches. We have shown that it is possible to efficiently detect all properties that can be expressed by using nested negations, disjunctions, conjunctions and the temporal operators possibly and always. Our algorithm is polynomial in the number of processes and events in the system, though it is exponential in the size of the property. After faults are detected, it is necessary to act on them and, whenever possible, continue operation with minimal impact. This dissertation also deals with designing systems that can recover from faults. We look at techniques for tolerating faults in data and the state of the program. Particularly, we look at the problem where multiple servers have different data and program state and all of these need to be backed up to tolerate failures. Most current approaches to this problem involve some sort of replication. Other approaches based on erasure coding have high computational and communication overheads. We introduce the idea of fusible data structures to back up data. This approach relies on the inherent structure of the data to determine techniques for combining multiple such structures on different servers into a single backup data structure. We show that most commonly used data structures like arrays, lists, stacks, queues, and so on are fusible and present algorithms for this. This approach requires less space than replication without increasing the time complexities for any updates. In case of failures, data from the back up and other non-failed servers is required to recover. To maintain program state in case of failures, we assume that programs can be represented by deterministic finite state machines. Though this approach may not yet be practical for large programs it is very useful for small concurrent programs like sensor networks or finite state machines in hardware designs. We present the theory of fusion of state machines. Given a set of such machines, we present a polynomial time algorithm to compute another set of machines which can tolerate the required number of faults in the system. / text

published_or_final_version / Computer Science and Information Systems / Doctoral / Doctor of Philosophy

published_or_final_version / Electrical and Electronic Engineering / Doctoral / Doctor of Philosophy

published_or_final_version / Computer Science and Information Systems / Master / Master of Philosophy