The shared data-object model as a paradigm for programming distributed systems
Henri E. Bal · Digital Academic REpository of VU University Amsterdam (Vrije Universiteit Amsterdam) · 1989
This thesis discusses a new model for implementing user applications on distributed systems.The proposed model, called the shared data-object model, intends to ease distributed programming by providing a communication mechanism that hides the physical distribution of the underlying system.In this way, it combines the advantages of distributed systems (good price/performance ratio and extensibility) and sharedmemory multiprocessors (relative ease of programming).Also, the thesis describes a new language based on this model and it discusses the implementation, usage, and performance of this language.The thesis first defmes the term "distributed system," to avoid confusion on this controversial point.The systems covered by the defmition include message-passing multicomputers-and collections of workstation connected through a network.Distributed systems can be used for a broad spectrum of applications, for example highperformance parallel applications and fault-tolerant applications.The thesis is mainly concerned with parallel applications.Three issues distinguish programming these systems from programming uniprocessors: the use of multiple processors, the cooperation among the processors, and the potential for partial failure.Programming support for these three issues may either be given by the operating system or by a programming language.In the frrst case, the distributed system is programmed in an existing sequential language extended with library routines that invoke operating system primitives.In Chapter 2, this option is considered.Two parallel applications are implemented in C on top of the Amoeba distributed operating system, using Remote Procedure Call for interprocess communication.The performance of these two programs is described and several important problems with this approach are identified.In the remaining chapters, the second approach, using a language designed for distributed programming, is studied.Chapter 3 gives a survey of the state-of-the-art in research on language support for distributed programming.Chapter 4 describes several important languages in some detail.These two chapters cover a broad spectrum of language primitives, including synchronous message passing, asynchronous message passing, rendezvous, remote procedure call, objects, atomic transactions, functional parallelism, shared logical variables, and distributed data structures.A critical evaluation of these primitives shows they have many shortcomings when used for distributed application programming.The shared data-object model is introduced in Chapter 5.In this model, shared data are encapsulated in data-objects, which are instances of user-defmed abstract data viii SUMMARY ix SAMENVATIING xi asynchrone message passing, rendezvous, remote procedure call, objecten, atomaire transacties, functioneel parallellisme, gedeelde logische variabelen en gespreide datastructuren.Een kritische evaluatie van deze primitieven toont aan dat zij veel tekortkomingen vertonen wanneer ze voor gespreide applicaties worden gebruikt.Het shared data-object model wordt in Hoofdstuk 5 ge'introduceerd.In dit model worden gemeenschappelijke data ingepakt in zogenaamde data-objecten, variabelen van door de programmeur gedefinieerde abstracte data types.Een data-object kan worden gedeeld door het proces dat het object gemaakt heeft en de afstammelingen van dit proces.Elk proces dat toogang heeft tot een object kan de operaties uitvooren die door het type van dat object gedefmieerd zijn.AI deze operaties worden ondeelbaar uitgevoord, zodat mutual exclusion synchronization impliciet gebeurt.Condition synchronization kan uitgedrukt worden door middel van operaties die blok.keren.Een simpele, type-veilige, procedurele taal gebaseerd op dit model wordt ook beschreven in Hoofdstuk 5. Deze taal, Orca genaamd, kent dynamische procescreatie, abstracte data types, een uitbebreide verzameling data structuren en verder generieke types en modulen.De taal is speciaal ontworpen voor gespreid programmeren en integreert de hiervoor benodigde sequentiele en gespreide constructies op een nette manier.De implementatie van de taal wordt behandeld in Hoofdstuk 6. Het belangrijkste aspect van een gespreide implementatie is de efficiente behandeling van gedeelde data-objecten.Het principe hierbij is dat elke object gerepliceerd wordt op die CPUs die het object vaak gebruiken; een operatie die de data van een object leest maar niet verandert, kan dan worden uitgevoord op een lokale kopie van het object, zonder te hooven communiceren met andere CPUs.Een aantal replicatie-strategie en wordt behandeld en protocollen voor het consistent bijwerken van alle replica's worden beschreven.Twee van deze protocollen zijn ge"implementeerd in twee verschillende run time systemen (RTSen).Beide draaien op een gespreid system met een Ethernet netwerk.Ter vergelijking is er ook een derde RTS geschreven dat draait op een niet-gespreid systeem, bestaande uit een aantal verwerkingseenheden met een gemeenschappelijk geheugen.Alle drie de RTSen maken gebruik van dezelfde vertaler, die gebouwd is met behulp van de Amsterdam Compiler Kit.Op de drie RTSen is een aantal parallelle applicaties ontwikkeld.Metingen aan de performance van deze programma's tonen aan dat er voor alle drie de RTSen belangrijke snelheidsverbeteringen gehaald worden.AIs grotere toepassing wordt het oplossen van schaakproblemen kort beschreven.In het laatste hoofdstuk worden enkele conclusies getrokken en mogelijkheden voor toekomstig onderzook aangegeven.De bijlagen van het proefschrift bevatten de broncode van de programma's uit Hoofdstuk 7 en geven meer gedetailleerde informatie over de metingen uit Hoofdstuk 2 en 7. Tenslotte voIgt een uitgebreide literatuurlijst met meer dan 300 verwijzingen.impossible.In any event, it is far beyond the current state-of-the-art in compiler technology.