AITutor

Computer Science Books/Sem6/Dos

intermediate

Computer Science Books/Sem6/Dos

– 1 of 763 –

DISTRIBUTED OPERATING SYSTEMS

– 2 of 763 –

IEEE Press 445 Hoes Lane, P.O. Box 1331 Piscataway, NJ 08855-1331 Editorial Board John B. Anderson, Editor in Chief’ P. M. Anderson A. H. Haddad P. Laplante M. Eden R. Herrick R. S. Muller M. E. El-Hawary G. F. Hoffnagle W. D. Reeve S. Furui R. F. Hoyt D. J. Wells S. Kartalopoulos Dudley R. Kay, Director of Book Publishing John Griffin, Senior Editor Lisa Dayne, Assistant Editor Linda Matarazzo, Editorial Assistant Denise Phillip, Associate Production Editor IEEE Communications Society, Sponsor Tom Robertazzi, C-S Liaison to IEEE Press Technical Reviewers Dr. Walter Kohler, Digital Equipment Corporation Mr. Harold Lorin, The Manticore Consultancy Ms. Celine Vaolt Dr. Wayne Wolf, Princeton University Also from IEEE Press Computer Communications and Networks, Second Edition John Freer Copublished with VeL Press 1996 Hardcover 400 pp IEEE Order No, PC5654 ISBN 0-7803-1179-5 Engineering Networks for Synchronization, CCS 7 and ISDN: Standards, Protocols, Planning, and Testing P. K. Bhatnagar 1997 Hardcover 528 pp IEEE Order No. PC5628 ISBN 0-7803-1158-2 SONET-SDH: A Sourcebook of Synchronous Networking edited by Curtis A. Siller, Jr. and Mansoor Shafi 1996 Hardcover 406 pp IEEE Order No. PC4457 ISBN 0-7803-1168-X

– 3 of 763 –

DISTRIBUTED OPERATING SYSTEMS Concepts and Design Pradeep K. Sinha Centre for Development of Advanced Computing ~ IEEE COMPUTER ~ SOCIETY PRESS ® +. IEEE PRESS ® IEEE Communications Society, Sponsor The Institute of Electrical and Electronics Engineers, Inc., New York

– 4 of 763 –

A NOm TO ras READER This book has been electronically reproduced from digital information storedat John Wiley & Sons, Inc. We are pleasedthat the use oftbis new technology will enable us to keep worksof enduring scholarly value in print as longas there is a reasonable demand for them. The contentof this book is identical to previous printings. This book may be purchased at a discount from the publisher when ordered in bulk quantities. Contact: IEEE Press Marketing Attn: Special Sales 445 Hoes Lane, ~O. Box 1331 Piscataway, NJ 08855-1331 Fax: (732) 981-9334 For more information on the IEEE Press, visit the IEEE home page: http://www.ieee.org/ © 1997 by the Institute of Electrical and Electronics Engineers, Inc., 3 Park Avenue, 17 th Floor, New York, NY 10016-5997 All rights reserved. No part of this book may be reproduced in any form, nor may it be stored in a retrieval system or transmitted in any form, without written permission from the publisher. Printed in the United States of America 10 9 8 7 6 5 4 3 ISBN 0-7803-1119-1 IEEE Order Number: PC470S Library of Congress Cataloging-in-Publication Data Sinha, Pradeep K. (Pradeep Kumar) Distributed operating systemslPradeep K. Sinha. p. em. Includes bibliographical references and index. ISBN 0-7803-1119-1 (cloth) I. Distributed operating systems (Computers) I. Title. QA 76.76.063S568 1996 96..26565 005.4’4–dc20 CIP

– 5 of 763 –

Contents Pr.face xi Acknowledgments xv Abbreviations Qnd Acronyms xvii Chapter 1: Fundamentals 1 1.1 What Is a Distributed Computing System? 1.2 Evolution of Distributed Computing Systems 3 1.3 Distributed Computing System Models 5 1.4 Why Are Distributed Computing Systems Gaining Popularity? 12 1.5 What Is a Distributed Operating System? 16 1.6 Issues in Designing a Distributed Operating System 19 1.7 Introduction to Distributed Computing Environment (DCE) 34 1.8 Summary 38 Exercises 39 Bibliography 41 Pointers to Bibliographies on the Internet 44 v

– 6 of 763 –

vi Chapter I: Computar Networks 46 2.1 Introduction 46 2.2 Networks Types 47 2.3 LAN Technologies 48 2.4 WAN Technologies 59 2.5 Communication Protocols 64 2.6 Intemetworking 83 2.7 ATM Technology 91 2.8 Summary 104 Exercises 105 Bibliography 108 Pointers to Bibliographies on the Internet 112 Chapter 3: Messag_ Passing 114 3.1 Introduction 114 3.2 Desirable Features of a Good Message-Passing System 115 3.3 Isses in IPC by Message Passing 118 3.4 Synchronization 120 3.5 Buffering 122 3.6 Multidatagram Messages 125 3.7 Encoding and Decoding of Message Data 126 3.8 Process Addressing 127 3.9 Failure Handling 130 3.10 Group Communication 139 3.11 Case Study: 4.38SD UNIX IPC Mechanism 153 3.12 Summary 157 Exercises 160 Bibliography 163 Pointers to Bibliographies on the Internet 166 Chapter 4: Remota Procedure Calls 167 4.1 Introduction 167 4.2 The RPC Model 168 4.3 Transparency of RPC 170 4.4 Implementing RPC Mechanism 171 4.5 Stub Generation 174 4.6 RPC Messages 174 4.7 Marshaling Arguments and Results 177 4.8 Server Management 178 4.9 Parameter-Passing Semantics 183 Contents

– 7 of 763 –

Contents vii 4.10 Call Semantics 184 4.11 Communication Protocols for RPCs 4.12 Complicated RPCs 191 4.13 Client-Server Binding 193 4.14 Exception Handling 198 4.15 Security 198 4.16 Some Special Types of RPCs 199 4.17 RPC in Heterogeneous Environments 4.18 Lightweight RPC 204 4.19 Optimizations for Better Performance 4.20 Case Studies: Sun RPC, r)CI~ RPC 4.21 Summary 222 Exercises 224 Bibliography 227 Pointers to Bibliographies on the Internet 187 203 208 212 230 Chapter 5: Distributed Shared Memory 231 233 234 237 281 266 267 270 5.1 Introduction 231 5.2 General Architecture of I)SM Systerns 5.3 Design and Implementation Issues of DSM 5.4 Granularity 235 5.5 Structure of Shared Memory Space 5.6 Consistency Models 238 5.7 Replacement Strategy 262 5.8 Thrashing 264 5.9 Other Approaches to DSM 5.10 Heterogeneous DSM 5.11 Advantages of DSM 5.12 Summary 272 Exercises 274 Bibliography 275 Pointers to Bibliographies on the Internet Chapter 6: Synchronization 282 6.1 Introduction 282 6.2 Clock Synchronization 283 6.3 Event Ordering 292 6.4 Mutual Exclusion 299 6.5 Deadlock 305 6.6 EJection Algorithms 332 6.7 Summary 336

– 8 of 763 –

viii Exercises 337 Bibliography 341 Pointers to Bibliographies on the Internet 345 Contents Chapter 7: “-source MQnQgcament 347 7.1 Introduction 347 7.2 Desirable Features of a Good Global Scheduling Algorithm 348 7.3 Task Assignment Approach 351 7.4 Load-Balancing Approach 355 7.5 Load-Sharing Approach 367 7.6 Summary 371 Exercises 372 Bibliography 374 Pointers to Bibliographies on the Internet 380 Chapter 8: Process Management 381 8.1 Introduction 381 8.2 Process Migration 382 8.3 Threads 398 8.4 Summary 414 Exercises 415 Bibliography 418 Pointers to Bibliographies on the Internet 420 Chapter 9: Distributed File Systems 421 9.1 Introduction 421 9.2 Desirable Features of a Good Distributed File System 423 9.3 File Models 426 9.4 File-Accessing Models 427 9.5 File-Sharing Semantics 430 9.6 File-Caching Schemes 433 9.7 File Replication 440 9.8 Fault Tolerance 447 9.9 Atomic Transactions 453 9.10 Design Principles 474 9.11 Case Study: DeE Distributed File Service 475 9.12 Summary 484 Exercises 486 Bibliography 489 Pointers to Bibliographies on the Internet 495

– 9 of 763 –

Contents Chapter 10: Naming 496 ix 10.1 Introduction 496 10.2 Desirable Features of a Good Naming System 10.3 Fundamental Terminologies and Concepts 10.4 System-Oriented Names 509 10.5 Object-Locating Mechanisms 512 10.6 Human-Oriented Names 515 10.7 Name Caches 541 10.8 Naming and Security 544 10.9 Case Study: DCE Directory Service 546 10.10 Summary 556 Exercises 558 Bibliography 560 Pointers to Bibliographies on the Internet 564 Chapter 11: Security 565 497 499 11.1 Introduction 565 11.2 Potential Attacks to Computer Systems 567 11.3 Cryptography 575 11.4 Authentication 586 11.5 Access Control 607 11.6 Digital Signatures 623 11.7 Design Principles 626 11.8 Case Study: DeE Security Service 627 11.9 Summary 630 Exercises 63 1 Bibliography 634 Pointers to Bibliographies on the Internet 640 Chapter 12: Case Studies 642 12.1 Introduction 642 12.2 Amoeba 643 12.3 V-System 659 12.4 Mach 674 12.5 Chorus 696 12.6 A Comparison of Amoeba, V-System, Mach, and Chorus 714 12.7 Summary 718 Exercises 722 Bibliography 725 Pointers to Bibliographies on the Internet 730 Index 731

– 10 of 763 –

– 11 of 763 –

Preface Motivation The excellent price/performance ratio offered by microprocessor-based workstations over traditional mainframe systems and the steady improvements in networking technologies have made distributed computing systems very attractive. While the hardware issues of building such systems have been fairly well understood for quite some time, the major stumbling block until now has been the availability of good distributed operating systems. Fortunately, recent research and development work in academic institutions and industries have helped us better understand the basic concepts and design issues in developing distributed operating systems. Distributed operating systems are no more only in research laboratories but are now commercially available. With the proliferation of distributed computing systems, it has become increasingly important for computer science and computer engineering students to learn about distributed operating systems. As a result, a number of universities have instituted regular courses on distributed operating systems at the graduate level. Even in various undergraduate-level operating systems courses, the fundamental concepts and design principles of distributed operating systems have been incorporated. However, there is still a lack of good textbooks that can provide a comprehensive and solid introduction to distributed operating systems in an orderly manner. Except for a few xi

– 12 of 763 –

xii Preface recently published books, almost all books in this area are research monographs. Therefore, for both an educator and a student, the creation of an overall image of distributed operating systems is currently a complicated and time-consuming task. Furthermore, computer professionals and starting researchers who want to get an overall picture of distributed operating systems so as to identify the various research and design issues have difficulty in finding a good text for their purpose. Motivated by these factors, I decided to do research toward the preparation of a textbook on distributed operating systems. My primary objective was to concisely present a clear explanation of the current state of the art in distributed operating systems so that readers can gain sufficient background to appreciate more advanced materials of this field. The book is designed to provide a clear description of the fundamental concepts and design principles that underlie distributed operating systems. It does not concentrate on any particular distributed operating system or hardware. Instead, it discusses, in a general setting, the fundamental concepts and design principles that are applicable to a variety of distributed operating systems. However, case studies are included in the text to relate the discussed concepts with real distributed operating systems. The material in the book has been drawn largely from the research literature in the field. Of the vast amount of research literature available in this field, effort was made to select and give more emphasis to those concepts that are of practical value in real systems, rather than those that are only of theoretical interest. Each chapter contains carefully designed exercises that are meant to test the understanding of the materials in the text and to stimulate investigation. An extensive set of references and a list of selected pointers to on-line bibliographies on the Internet have been provided at the end of each chapter to allow interested readers to explore more advanced materials dealing with finer details about each chapter’s topics. Throughout the book, the style of presentation used is motivational and explanatory in nature. Chapter 1 provides an introduction to distributed computing systems, distributed operating systems, and the issues involved in designing distributed operating systems. It also provides a brief introduction to Distributed Computing Environment (DCE), whose components are described as case studies of key technologies in several chapters of the book. Chapter 2 presents a brief introduction to computer networks and describes the current state of the art in networking technology.

– 13 of 763 –

Preface xiii Chapters 3, 4, and 5 describe the various communication techniques used for exchange of information among the processes of a distributed computing system. In particular, these three chapters deal with the issues involved in the design of interprocess communication mechanisms and the commonly used practical approaches to handle these issues. Chapter 3 deals with the message-passing mechanism. Chapter 4 deals with the remote procedure call mechanism, and Chapter 5 deals with the distributed shared- memory mechanism for interprocess communication. Synchronization issues to be dealt with in a distributed system, such as clock synchronization, mutual exclusion, deadlock, and election algorithms, are discussed in Chapter 6. Chapter 7 presents a discussion of the commonly used approaches for resource management in distributed systems. Chapter 8 deals with the process management issues. In particular, it presents a discussion of process migration mechanisms and mechanisms to support threads facility. A discussion of the issues and the approaches for designing a file system for a distributed system is given in Chapter 9. Chapter 10 deals with the issues and mechanisms for naming and locating objects in distributed systems. The security issues and security mechanisms for distributed systems are discussed in Chapter 11. Finally, Chapter 12 contains case studies of four existing distributed operating systems to relate the concepts discussed in the preceding chapters with real distributed operating systems. Audience The book is suitable for anyone who needs a concise and informal introduction to distributed operating systems. It can serve as an ideal textbook for a course on distributed operating systems. It can also be used for advanced undergraduate and postgraduate courses on operating systems, which often need to cover the fundamental concepts and design issues of distributed operating systems in addition to those of centralized operating systems. The book can also be used as a self-study text by system managers, professional software engineers, computer scientists, and researchers, who either need to learn about distributed operating systems or are involved in the design and development of distributed operating systems or distributed application systems. Advanced researchers will also find the rich set of references and the pointers to on- line bibliographies on the Internet provided at the end of each chapter very helpful in probing further on any particular topic. Although full care has been taken to make the subject matter simple and easy to understand by a wide range of readers, I have assumed that the reader has a knowledge of elementary computer architecture and is familar with basic centralized operating systems concepts discussed in standard operating systems textbooks.

– 14 of 763 –

xiv About Pointers to Bibliographies on the Internet Preface In addition to a good number of references provided in the end-of-chapter bibliographies, I have also provided lists of selected pointers to the on-line bibliographies of interest on the Internet. The purpose of these pointers is twofold:

  1. The end-of-chapter bibliographies contain only selected references. A large number of references on the topics covered in a chapter are not included in the chapter’s bibliography due to space limitations. The pointers may be used by interested readers to locate such references.
  2. The end-of-chapter bibliographies contain references to only already published documents. Distributed operating systems is currently an active area of research, and a large volume of new documents are published almost every month. Since the on-line bibliographies on the Internet are updated from time to time, interested readers may use the pointers to locate those documents that are published after the publication of this book. Thus, in addition to the information contained in it, the book also provides a way for its readers to keep track of on-going research activities on the topics covered and related topics. Note that the end-of-chapter lists of pointers to on-line bibliographies are by no means exhaustive. I have provided pointers for only those on-line bibliographies that I knew about and I felt would be useful in easily locating references of interest. Moreover, it is often the case that there are many mirrors for an on-line bibliography (the same bilbiography exists on multiple sites). For such cases, I have provided only one pointer for a bibliography. Also note that most of the on-line bibliographies are not about on-line documents, but about on-line references to documents. A vast majority of documents referenced in the on- line bibliographies only exist in hard-copy form. However, a few of the referenced documents do have an on-line version on the Internet. For such documents, the bibliographies normally contain URLs (Uniform Resource Locators) pointing to the on- line version of the document. If you find a reference containing such a URL, just follow the URL to access the on-line version of the corresponding document.

– 15 of 763 –

Acknowledgments Many people have contributed to this book, either directly or indirectly. To start with, I must thank all the researchers who have contributed to the fields of distributed computing systems and distributed operating systems because the book is based on their research results. Mamoru Maekawa, my Ph.D. supervisor, provided me with the opportunity to do research in the area of distributed operating systems. Without this opportunity, this book would not have been possible. Lively discussions with the members of the Galaxy distributed operating system project, including Kentaro Shimizu, Xiaohua Jia, Hyo Ashishara, Naoki Utsunomiya, Hirohiko Nakano, Kyu Sung Park, and Jun Hamano, helped a lot in broadening my knowledge of distributed operating systems. Without the efforts of all the people who collected references and made them available on the Internet, it would not have been possible for me to provide the end-of- chapter pointers to the bibliographies on the Internet. Several anonymous reviewers of my draft manuscript provided invaluable feedback concerning organization, topic coverage, t.ypographical errors, and parts of the text that were not as clear as they are now. My production editor at IEEE Press, Denise Phillip, did an excellent job in numerous ways to present the book in its current form. IEEE Press Director Dudley Kay, Senior xv

– 16 of 763 –

xvi Acknowledgements Acquisitions Editor John Griffin, and review coordinators Lisa Mizrahi and Lisa Dayne were of great help in improving the overall quality of the book and in bringing it out in a timely manner. Finally, I thank my wife, Priti, for preparing the electronic version of the entire hand- written draft manuscript. I also thank her for her continuous patience and sacrifices during the entire period of this long project. Without her loving support and understanding, I would never have succeeded in completing this project. Pradeep K. Sinha

– 17 of 763 –

Abbreviations Qnd Acronyms AAL ATM Adaptation Layer CDS Cell Directory Service/Server ACL Access Control List CERN European Centre for Nuclear AFS Andrew File System Research ANSI American National Standards CFS Cedar File System Institute CICS Customer Information Control API Application Programming System Interface CLP Cell Loss Priority APPN Advanced Peer-to-Peer eMH Chandy-Misra-Hass Networking CMIP Common Management ARP Address Resolution Protocol Information Protocol ARPANET Advanced Research Projects COOL Chorus Object-Oriented Layer Agency NETwork CSMAlCD Carrier Sense Multiple Access ASN.I Abstract Syntax Notation with Collision Detection ATM Asynchronous Transfer Mode CSRG Computer Systems Research BIOS Basic Input Output System Group B-ISDN Broadband Integrated Services DCE Distributed Computing Digital Network Environment CBR Constant Bit Rate DDLeN Distributed Double-Loop CCITT International Telegraph and Computer Network Telephone Consultative DEC Digital Equipment Corporation Committee DES Data Encryption Standard xvii

– 18 of 763 –

xviii Abbreviations and Acronyms DFS Distributed File Service IP Internet Protocol DI Directory Identifier IPC Inter-Process Communication DIB Directory Information Base ISDN Integrated Services Digital OIT Directory Information Tree Network DME Distributed Management ISO International Standards Environment Organization ON Distinguished Name lTV International ONS Domain NamelNaming Telecommunications Union Service/System KDBMS Kerberos Database Management DoD Department of Defense Server DSM Distributed Shared Memory KDC Key Distribution Center DSVM Distributed Shared Virtual LAN Local Area Network Memory LEC LAN Emulation Client DTS Distributed Time Service LES LAN Emulation Server Email Electronic Mail LRPC Lightweight Remote Procedure ERB Expanding Ring Broadcast Call FOOl FiberDistributed Data MAN Metropolitan Area Network Interface MBone Multicast Backbone FIFO First-In First-Out Mbps Megabits per second FLIP Fast Local Internet Protocol MIG Mach Interface Generator FTP File Transfer Protocol MMU Memory Management Unit Gbps Gigabits per second MTBF Mean Time Between Failures GDA Global Directory Agent MTU Maximum Transfer Unit GDS Global Directory Service/Server NCA Network Computing GEOS Geostationary Operational Architecture Environmental Satellites NCS Network Computing System GFC Generic Flow Control NFS Network File System GNS Global Name Service NIC Network Information Center GNU Gnu’s Not Unix NIST National Institute for Standards GPS Global Positioning System and Technology HEe Header Error Control NRMB Non-Replicated Migrating HRPC Heterogeneous Remote Block Procedure Call NRNMB Non-Replicated Non-Migrating IBM International Business Machines Block ICMP Internet Control Message NSAP Network Service Access Point Protocol NTP Network Time Protocol IOL Interface Definition Language NVMA Non-Uniform Memory Access IEEE Institute of Electrical and OC-n Optical Carrier level n Electronics Engineers OLTP On Line Transaction IETF Internet Engineering Task Force Processing IMS Information Management OPC Output Port Controller System OSF Open Software Foundation INRIA Institute National de Recherche OSI Open System International en Informatique et PCB Process Control Block Automatique PEM Privacy Enhanced Mail

– 19 of 763 –

Abbreviations and Acronyms xix PKM Public Key Manager STS-n Synchronous Transport Signal PMD Physical Medium Dependent level n POSIX Portable Operating System TC Transmission Convergence Interface for Computer TCF Transparent Computing Facility Environments TCP Transport Control Protocol PRAM Pipelined Random Access TFTP Trivial File Transfer Protocol Memory TI-RPC Transport Independent-Remote PSE Packet Switching Exchange Procedure Call PTI Payload Type Identifier TP Transport Protocol RARP Reverse Address Resolution TWFG Transaction Wait-For-Graph Protocol VCP Unilateral Commit Protocol RON Relative Distinguished Name UDP User Datagram Protocol RFS Remote File Server UDS Universal Directory Service RFT Request For Technology UNI User Network Interface RMB Replicated Migrating Block UTC Coordinated Universal Time RNMB Replicated Non-Migrating VUID Universally Unique Identifier Block VBR Variable Bit Rate RPC Remote Procedure Call vel Virtual Channel Identifier RPCL Remote Procedure Call VM Virtual Memory Language VMTP Versatile Message Transfer RR Round-Robin Protocol RSA Rivest-Shamir-Adleman VPI Virtual Path Identifier RSS Research Storage System WAIS Wide Area Information Servers SDH Synchronous Digital Hierarchy WAN Wide Area Network SEAL Simple and Efficient Adaptation WFG Wait For Graph Layer WWW \lorld Wide Web SLIP Serial Line Internet Protocol X-IPe eXtcnted Inter-Process SMTP Simple Mail Transfer Protocol Communication SNA System Network Architecture XDR eXternal Data Representation SNMP Simple Network Management XDS X/Open Directory Server Protocol XNS Xerox Networking System SONET Synchronous Optical NETwork XOM X/Open Object Management

– 20 of 763 –

CHAPTER 1 Fundamentals 1.1 WHAT IS A DISTRIBUTED COMPUTING SYSTEM? Over the past two decades, advancements in microelectronic technology have resulted in the availability of fast, inexpensive processors , and advancements in communication technology have resulted in the availability of cost-effective and highly efficient computer networks. The net result of the advancements in these two technologies is that the price- performance ratio has now changed to favor the use of interconnected, multiple processors in place of a single, high-speed processor. Computer architectures consisting of interconnected, multiple processors are basically of two types: I. Tightly coupled systems. In these systems, there is a single systemwide primary memory (address space) that is shared by all the processors [Fig. l.1(a)]. If any processor writes, for example, the value 100 to the memory location x, any other processor subsequently reading from location x will get the value 100. Therefore, in these systems, any communication between the processors usually takes place through the shared memory. 2. Loosely coupled systems. In these systems, the processors do not share memory, and each processor has its own local memory [Fig. l.1(b)] . If a processor writes the value 1

– 21 of 763 –

2 Chap. 1 • Fundamentals CPU CPU Systemwide CPU CPU shared memory Interconnection hardware I(a) Local memory Local memory Local memory Local memory CPU CPU CPU CPU Communication network (b) Fig_ 1.1 Difference between tightly coupled and loosely coupled multiprocessor systems: (a) a tightly coupled multiprocessor system; (b) a loosely coupled multiprocessor system. 100 to the memory location x, this write operation will only change the contents of its local memory and will not affect the contents of the memory of any other processor. Hence, if another processor reads the memory location x, it will get whatever value was there before in that location of its own local memory. In these systems, all physical communication between the processors is done by passing messages across the network that interconnects the processors. Usually, tightly coupled systems are referred to as parallel processing systems, and loosely coupled systems are referred to as distributed computing systems, or simply distributed systems. In this book, however, the term “distributed system” will be used only for true distributed systems-distributed computing systems that use distributed operating systems (see Section 1.5). Therefore, before the term “true distributed system” is defined in Section 1.5, the term “distributed computing system” will be used to refer to loosely coupled systems. In contrast to the tightly coupled systems, the processors of distributed computing systems can be located far from each other to cover a wider geographical area. Furthermore, in tightly coupled systems, the number of processors that can be usefully deployed is usually small and limited by the bandwidth of the shared memory. This is not the case with distributed computing systems that are more freely expandable and can have an almost unlimited number of processors.

– 22 of 763 –

Sec. 1.2 • Evolution of Distributed Computing Systems 3 In short, a distributed computing system is basically a collection of processors interconnected by a communication network in which each processor has its own local memory and other peripherals, and the communication between any two processors of the system takes place by message passing over the communication network. For a particular processor, its own resources are local, whereas the other processors and their resources are remote. Together, a processor and its resources are usually referred to as a node or site or machine of the distributed computing system. 1.2 EVOLUTION OF DISTRIBUTED COMPUTING SYSTEMS Early computers were very expensive (they cost millions of dollars) and very large in size (they occupied a big room). There were very few computers and were available only in research laboratories of universities and industries. These computers were run from a console by an operator and were not accessible to ordinary users. The programmers would write their programs and submit them to the computer center on some media, such as punched cards, for processing. Before processing a job, the operator would set up the necessary environment (mounting tapes, loading punched cards in a card reader, etc.) for processing the job. The job was then executed and the result, in the form of printed output, was later returned to the programmer. The job setup time was a real problem in early computers and wasted most of the valuable central processing unit (CPU) time. Several new concepts were introduced in the 1950s and 1960s to increase CPU utilization of these computers. Notable among these are batching together of jobs with similar needs before processing them, automatic sequencing of jobs, off-line processing by using the concepts of buffering and spooling, and“ multiprogramming. Batching similar jobs improved CPU utilization quite a bit because now the operator had to change the execution environment only when a new batch of jobs had to be executed and not before starting the execution of every job. Automatic job sequencing with the use of control cards to define the beginning and end of a job improved CPU utilization by eliminating the need for human job sequencing. Off-line processing improved CPU utilization by allowing overlap of CPU and input/output (I/O) operations by executing those two actions on two independent machines (110 devices are normally several orders of magnitude slower than the CPU). Finally, multiprogramming improved CPU utilization by organizing jobs so that the CPU always had something to execute. However, none of these ideas allowed multiple users to directly interact with a computer system and to share its resources simultaneously. Therefore, execution of interactive jobs that are composed of many short actions in which the next action depends on the result of a previous action was a tedious and time-consuming activity. Development and debugging of programs are examples of interactive jobs. It was not until the early 1970s that computers started to use the concept of time sharing to overcome this hurdle. Early time-sharing systems had several dumb terminals attached to the main computer. These terminals were placed in a room different from the main computer room. Using these terminals, multiple users could now simultaneously execute interactive jobs and share the resources of the computer system. In a time-sharing system, each user is given

– 23 of 763 –

4 Chap. 1 • Fundamentals the impression that he or she has his or her own computer because the system switches rapidly from one user’s job to the next user’s job, executing only a very small part of each job at a time. Although the idea of time sharing was demonstrated as early as 1960, time- sharing computer systems were not common until the early 1970s because they were difficult and expensive to build. Parallel advancements in hardware technology allowed reduction in the size and increase in the processing speed of computers, causing large-sized computers to be gradually replaced by smaller and cheaper ones that had more processing capability than their predecessors. These systems were called minicomputers. The advent of time-sharing systems was the first step toward distributed computing systems because it provided us with two important concepts used in distributed computing systems-the sharing of computer resources simultaneously by many users and the accessing of computers from a place different from the main computer room. Initially, the terminals of a time-sharing system were dumb terminals, and all processing was done by the main computer system. Advancements in microprocessor technology in the 1970s allowed the dumb terminals to be replaced by intelligent terminals so that the concepts of off-line processing and time sharing could be combined to have the advantages of both concepts in a single system. Microprocessor technology continued to advance rapidly, making available in the early 1980s single-user computers called workstations that had computing power almost equal to that of minicomputers but were available for only a small fraction of the price of a minicomputer. For example, the first workstation developed at Xerox PARC (called Alto) had a high-resolution monochrome display, a mouse, 128 kilobytes of main memory, a 2.5-megabyte hard disk, and a microprogrammed CPU that executed machine-level instructions at speeds of 2-6 f.Ls. These workstations were then used as terminals in the time-sharing systems. In these time-sharing systems, most of the processing of a user’s job could be done at the user’s own computer, allowing the main computer to be simultaneously shared by a larger number of users. Shared resources such as files, databases, and software libraries were placed on the main computer. Centralized time-sharing systems described above had a limitation in that the terminals could not be placed very far from the main computer room since ordinary cables were used to connect the terminals to the main computer. However, in parallel, there were advancements in computer networking technology in the late 1960s and early 1970s that emerged as two key networking technologies-LAN (local area network) and WAN (wide- area network). The LAN technology allowed several computers located within a building or a campus to be interconnected in such a way that these machines could exchange information with each other at data rates of about 10 megabits per second (Mbps). On the other hand, WAN technology allowed computers located far from each other (may be in different cities or countries or continents) to be interconnected in such a way that these machines could exchange information with each other at data rates of about 56 kilobits per second (Kbps). The first high-speed LAN was the Ethernet developed at Xerox PARe in 1973, and the first WAN was the ARPAnet (Advanced Research Projects Agency Network) developed by the U.S. Department of Defense in 1969. The data rates of networks continued to improve gradually in the 1980s, providing data rates of up to 100 Mbps for LANs and data rates of up to 64 Kbps for WANs. Recently (early 1990s) there has been another major advancement in networking technology-the ATM (asynchronous

– 24 of 763 –

Sec. 1.3 • Distributed Computing System Models 5 transfer mode) technology. The Al’M technology is an emerging technology that is still not very well established. It will make very high speed networking possible, providing data transmission rates up to 1.2 gigabits per second (Gbps) in both LAN and WAN environments. The availability of such high-bandwidth networks will allow future distributed computing systems to support a completely new class of distributed applications, called multimedia applications, that deal with the handling of a mixture of information, including voice, video, and ordinary data. These applications were previously unthinkable with conventional LANs and WANs. The merging of computer and networking technologies gave birth to distributed computing systems in the late 1970s. Although the hardware issues of building such systems were fairly well understood, the major stumbling block at that time was the availability of adequate software for making these systems easy to use and for fully exploiting their power. Therefore, starting from the late 1970s, a significant amount of research work was carried out in both universities and industries in the area of distributed operating systems. These research activities have provided us with the basic ideas of designing distributed operating systems. Although the field is still immature, with ongoing active research activities, commercial distributed operating systems have already started to emerge. These systems are based on already established basic concepts. This book deals with these basic concepts and their use in the design and implementation of distributed operating systems. Several of these concepts are equally applicable to the design of applications for distributed computing systems, making this book also suitable for use by the designers of distributed applications. 1.3 DISTRI8UTED COMPUTING SYSTEM MODELS Various models are used for building distributed computing systems. These models can be broadly classified into five categories-minicomputer, workstation, workstation-server, processor-pool, and hybrid. They are briefly described below. 1.3.1 Minicomputer Model The minicomputer model is a simple extension of the centralized time-sharing system. As shown in Figure 1.2, a distributed computing system based on this model consists of a few minicomputers (they may be large supercomputers as well) interconnected by a communication network. Each minicomputer usually has multiple users simultaneously logged on to it. For this, several interactive terminals are connected to each minicomputer. Each user is logged on to one specific minicomputer, with remote access to other minicomputers. The network allows a user to access remote resources that are available on some machine other than the one on to which the user is currently logged. The minicomputer model may be used when resource sharing (such as sharing of information databases of different types, with each type of database located on a different machine) with remote users is desired. The early ARPAnet is an example of a distributed computing system based on the minicomputer model.

– 25 of 763 –

6 Mini- compute Chap. 1 • Fundamentals /TerminalS Mini· compute Mini- computer Fig_ 1.2 A distributed computing system based on the minicomputer model. 1.3.1 Workstation Mod.1 As shown in Figure 1.3, a distributed computing system based on the workstation model consists of several workstations interconnected by a communication network. A company’s office or a university department may have several workstations scattered throughout a building or campus, each workstation equipped with its own disk and serving as a single-user computer. It has been often found that in such an environment, at anyone time (especially at night), a significant proportion of the workstations are idle (not being used), resulting in the waste of large amounts of CPU time. Therefore, the idea of the workstation model is to interconnect all these workstations by a high-speed LAN so that idle workstations may be used to process jobs of users who are logged onto other workstations and do not have sufficient processing power at their own workstations to get their jobs processed efficiently. In this model, a user logs onto one of the workstations called his or her “home” workstation and submits jobs for execution. When the system finds that the user’s workstation does not have sufficient processing power for executing the processes of the submitted jobs efficiently, it transfers one or more of the processes from the user’s workstation to some other workstation that is currently idle and gets the process executed there, and finally the result of execution is returned to the user’s workstation. This model is not so simple to implement as it might appear at first sight because several issues must be resolved. These issues are [Tanenbaum 1995] as follows:

– 26 of 763 –

Sec. 1.3 • Distributed Computing System Models li’ig. 1.3 A distributed computing system based on the workstation model. 7

  1. How does the system find an idle workstation?
  2. How is a process transferred from one workstation to get it executed on another workstation?
  3. What happens to a remote process if a user logs onto a workstation that was idle until now and was being used to execute a process of another workstation? Ways to handle the first two issues are described in Chapters 7 and 8, respectively. Three commonly used approaches for handling the third issue are as follows:
  4. The first approach is to allow the remote process share the resources of the workstation along with its own logged-on user’s processes. This method is easy to implement, but it defeats the main idea of workstations serving as personal computers, because if remote processes are allowed to execute simultaneously with the logged-on user’s own processes, the logged-on user does not get his or her guaranteed response.
  5. The second approach is to kill the remote process. The main drawbacks of this method are that all processing done for the remote process gets lost and the file system may be left in an inconsistent state, making this method unattractive.
  6. The third approach is to migrate the remote process back to its home workstation, so that its execution can be continued there. This method is difficult to implement because it requires the system to support preemptive process migration facility. The definition of preemptive process migration and the issues involved in preemptive process migration are given in Chapter 8.

– 27 of 763 –

8 Chap. I • Fundamentals The Sprite system [Ousterhout et al. 1988] and an experimental system developed at Xerox PARe [Shoch and Hupp 1982] are two examples of distributed computing systems basedon the workstation model. 1.3.3 Workstatlon-S.rver Model The workstation model is a network of personal workstations, each with its own disk and a local file system. A workstation with its own local disk is usually called a diskful workstation and a workstation without a local disk is called a diskless workstation. With the proliferation of high-speed networks, diskless workstations have become more popular in network environments than diskful workstations, making the workstation-server model more popular than the workstation model for building distributed computing systems. As shown in Figure 1.4, a distributed computing system based on the workstation- servermodelconsists of a few minicomputers and several workstations (most of which are diskless, but a few of which may be diskful) interconnected by a communication network. Mini- com. puter usedas file server Mini- compute usedas database server Mini- computer usedas print server Fig. 1.4 A distributed computing system based on the workstation-server model. Note that when diskless workstations are used on a network, the file system to be used by these workstations must be implemented either by a diskful workstation or by a minicomputer equipped with a disk for file storage. The minicomputers are used for this purpose. One or more of the minicomputers are used for implementing the file system. Other minicomputers may be used for providing other types of services, such as database service and print service. Therefore, each minicomputer is used as a server machine to provide one or more types of services. Hence in the workstation-server model, in addition to the workstations, there are specialized machines (may be specialized workstations) for running server processes (called servers) for managing and providing access to shared resources.

– 28 of 763 –

Sec. 1.3 • Distributed Computing System Models 9 For a number of reasons, such as higher reliability and better scalability, multiple servers are often used for managing the resources of a particular type in a distributed computing system. For example, there may be multiple file servers, each running on a separate minicomputer and cooperating via the network, for managing the files of all the users in the system. Due to this reason, a distinction is often made between the services that are provided to clients and the servers that provide them. That is, a service is an abstract entity that is provided by one or more servers. For example, one or more file servers may be used in a distributed computing system to provide file service to the users. In this model, a user logs onto a workstation called his or her home workstation. Normal computation activities required by the user’s processes are performed at the user’s home workstation, but requests for services provided by special servers (such as a file server or a database server) are sent to a server providing that type of service that performs the user’s requested activity and returns the result of request processing to the user’s workstation. Therefore, in this model, the user’s processes need not be migrated to the server machines for getting the work done by those machines. For better overall system performance, the local disk of a diskful workstation is normally used for such purposes as storage of temporary files, storage of unshared files, storage of shared files that are rarely changed, paging activity in virtual-memory management, and caching of remotely accessed data. As compared to the workstation model, the workstation-server model has several advantages:

  1. In general, it is much cheaper to use a few minicomputers equipped with large, fast disks that are accessed over the network than a large number of diskful workstations, with each workstation having a small, slow disk.
  2. Diskless workstations are also preferred to diskful workstations from a system maintenance point of view. Backup and hardware maintenance are easier to perform with a few large disks than with many small disks scattered all over a building or campus. Furthermore, installing new releases of software (such as a file server with new functionalities) is easier when the software is to be installed on a few file server machines than on every workstation.
  3. In the workstation-server model, since all files are managed by the file servers, users have the flexibility to use any workstation and access the files in the same manner irrespective of which workstation the user is currently logged on. Note that this is not true with the workstation model, in which each workstation has its local file system, because different mechanisms are needed to access local and remote files.
  4. In the workstation-server model, the request-response protocol described above is mainly used to access the services of the server machines. Therefore, unlike the workstation model, this model does not need a process migration facility, which is difficult to implement. The request-response protocol is known as the client-server model of communica- tion. In this model, a client process (which in this case resides on a workstation) sends a

– 29 of 763 –

10 Chap. 1 • Fundamentals request to a server process (which in this case resides on a minicomputer) for getting some service such as reading a block of a file. The server executes the request and sends back a reply to the client that contains the result of request processing. The client-server model provides an effective general-purpose approach to the sharing of information and resources in distributed computing systems. It is not only meant for use with the workstation-server model but also can be implemented in a variety of hardware and software environments. The computers used to run the client and server processes need not necessarily be workstations and minicomputers. They can be of many types and there is no need to distinguish between them. It is even possible for both the client and server processes to be run on the same computer. Moreover, some processes are both client and server processes. That is, a server process may use the services of another server, appearing as a client to the latter. 5. A user has guaranteed response time because workstations are not used for executing remote processes. However, the model does not utilize the processing capability of idle workstations. The V-System [Cheriton 1988] is an example of a distributed computing system that is based on the workstation-server model. 1.3.4 Proc.ssor-Pool Mod.1 The processor-pool model is based on the observation that most of the time a user does not need any computing power but once in a while he or she may need a very large amount of computing power for a short time (e.g., when recompiling a program consisting of a large number of files after changing a basic shared declaration). Therefore, unlike the workstation-server model in which a processor is allocated to each user, in the processor- pool model the processors are pooled together to be shared by the users as needed. The pool of processors consists of a large number of microcomputers and minicomputers attached to the network. Each processor in the pool has its own memory to load and run a system program or an application program of the distributed computing system. As shown in Figure 1.5, in the pure processor-pool model, the processors in the pool have no terminals attached directly to them, and users access the system from terminals that are attached to the network via special devices. These terminals are either small diskless workstations or graphic terminals, such as X terminals. A special server (called a run server) manages and allocates the processors in the pool to different users on a demand basis. When a user submits a job for computation, an appropriate number of processors are temporarily assigned to his or her job by the run server. For example, if the user’s computation job is the compilation of a program having n segments, in which each of the segments can be compiled independently to produce separate relocatable object files, n processors from the pool can be allocated to this job to compile all the n segments in parallel. When the computation is completed, the processors are returned to the pool for use by other users. In the processor-pool model there is no concept of a home machine. That is, a user does not log onto a particular machine but to the system as a whole. This is in contrast

– 30 of 763 –

Sec. 1.3 • Distributed Computing System Models Fig. 1.5 A distributed computing system based on the processor-pool model. Terminals ~Pool of processors File serve 11 to other models in which each user has a home machine (e.g., a workstation or minicomputer) onto which he or she logs and runs most of his or her programs there by default. As compared to the workstation-server model, the processor-pool model allows better utilization of the available processing power of a distributed computing system. This is because in the processor-pool model, the entire processing power of the system is available for use by the currently logged-on users, whereas this is not true for the workstation-server model in which several workstations may be idle at a particular time but they cannot be used for processing the jobs of other users. Furthermore, the processor- pool model provides greater flexibility than the workstation-server model in the sense that the system’s services can be easily expanded without the need to install any more computers; the processors in the pool can be allocated to act as extra servers to carry any additional load arising from an increased user population or to provide new services. However, the processor-pool model is usually considered to be unsuitable for high- performance interactive applications, especially those using graphics or window systems. This is mainly because of the slow speed of communication between the computer on which the application program of a user is being executed and the terminal via which the user is interacting with the system. The workstation-server model is generally considered to be more suitable for such applications. Amoeba [Mullender et a1. 1990], Plan 9 [Pike et at 1990], and the Cambridge Distributed Computing System [Needham and l-lerbert 1982] are examples of distributed computing systems based on the processor-pool model.

– 31 of 763 –

12 Chap. 1 • Fundamentals 1.3.5 Hybrid Mod.’ Out of the four models described above, the workstation-server model, is the most widely used model for building distributed computing systems. This is because a large number of computer users only perform simple interactive tasks such as editing jobs, sending electronic mails, and executing small programs. The workstation-server model is ideal for such simple usage. However, in a working environment that has groups of users who often perform jobs needing massive computation, the processor-pool model is more attractive and suitable. To combine the advantages of both the workstation-server and processor-pool models, a hybrid model may be used to build a distributed computing system. The hybrid model is based on the workstation-server model but with the addition of a pool of processors. The processors in the pool can be allocated dynamically for computations that are too large for workstations or that require several computers concurrently for efficient execution. In addition to efficient execution of computation-intensive jobs, the hybrid model gives guaranteed response to interactive jobs by allowing them to be processed on local workstations of the users. However, the hybrid model is more expensive to implement than the workstation-server model or the processor-pool model. 1.4 WHY ARE DISTRIBUTED COMPUTING SYSTEMS GAINING POPULARnv? From the models of distributed computing systems presented above, it is obvious that distributed computing systems are much more complex and difficult to build than traditional centralized systems (those consisting of a single CPU, its memory, peripherals, and one or more terminals). The increased complexity is mainly due to the fact that in addition to being capable of effectively using and managing a very large number of distributed resources, the system software of a distributed computing system should also be capable of handling the communication and security problems that are very different from those of centralized systems. For example, the performance and reliability of a distributed computing system depends to a great extent on the performance and reliability of the underlying communication network. Special software is usually needed to handle loss of messages during transmission across the network or to prevent overloading of the network, which degrades the performance and responsiveness to the users. Similarly, special software security measures are needed to protect the widely distributed shared resources and services against intentional or accidental violation of access control and privacy constraints. Despite the increased complexity and the difficulty of building distributed computing systems, the installation and use of distributed computing systems are rapidly increasing. This is mainly because the advantages of distributed computing systems outweigh their disadvantages. The technical needs, the economic pressures, and the major advantages that have led to the emergence and popularity of distributed computing systems are described next.

– 32 of 763 –

Sec. 1.4 • Why Are Distributed Computing Systems Gaining Popularity? 1.4.1 Inherently Distributed Applications 13 Distributed computing systems come into existence in some very natural ways. For example, several applications are inherently distributed in nature and require a distributed computing system for their realization. For instance, in an employee database of a nationwide organization, the data pertaining to a particular employee are generated at the employee’s branch office, and in addition to the global need to view the entire database, there is a local need for frequent and immediate access to locally generated data at each branch office. Applications such as these require that some processing power be available at the many distributed locations for collecting, preprocessing, and accessing data, resulting in the need for distributed computing systems. Some other examples of inherently distributed applications are a computerized worldwide airline reservation system, a computerized banking system in which a customer can deposit/withdraw money from his or her account from any branch of the bank, and a factory automation system controlling robots and machines all along an assembly line. 1.4.2 Information Sharing among Distributed Users Another reason for the emergence of distributed computing systems was a desire for efficient person-to-person communication facility by sharing information over great distances. In a distributed computing system, information generated by one of the users can be easily and efficiently shared by the users working at other nodes of the system. This facility may be useful in many ways. For example, a project can be performed by two or more users who are geographically far off from each other but whose computers are a part of the same distributed computing system. In this case, although the users are geographically separated from each other, they can work in cooperation, for example, by transferring the files of the project, logging onto each other’s remote computers to run programs, and exchanging messages by electronic mail to coordinate the work. The use of distributed computing systems by a group of users to work cooperatively is known as computer-supported cooperative working (CSCW), or groupware. Groupware applications depend heavily on the sharing of data objects between programs running on different nodes of a distributed computing system. Groupware is an emerging technology that holds major promise for software developers. 1.4.3 Resource Sharing Information is not the only thing that can be shared in a distributed computing system. Sharing of software resources such as software libraries and databases as well as hardware resources such as printers, hard disks, and plotters can also be done in a very effective way among all the computers and the users of a single distributed computing system. For example, we saw that in a distributed computing system based on the workstation-server model the workstations may have no disk or only a small disk (10-20 megabytes) for temporary storage, and access to permanent files on a large disk can be provided to all the workstations by a single file server.

– 33 of 763 –

14 Chap. 1 • Fundamentals This is one of the most important reasons for the growing popularity of distributed computing systems. With the rapidly increasing power and reduction in the price of microprocessors, combined with the increasing speed of communication networks, distributed computing systems potentially have a much better price-performance ratio than a single large centralized system. For example, we saw how a small number of CPUs in a distributed computing system based on the processor-pool model can be effectively used by a large number of users from inexpensive terminals, giving a fairly high price-performance ratio as compared to either a centralized time-sharing system or a personal computer. Another reason for distributed computing systems to be more cost-effective than centralized systems is that they facilitate resource sharing among multiple computers. For example, a single unit of expensive peripheral devices such as color laser printers, high-speed storage devices, and plotters can be shared among all the computers of the same distributed computing system. If these computers are not linked together with a communication network, each computer must have its own peripherals, resulting in higher cost. 1.4.5 Shorter Response nmes and Higher Throughput Due to multiplicity of processors, distributed computing systems are expected to have better performance than single-processor centralized systems. The two most commonly used performance metrics are response time and throughput of user processes. That is, the multiple processors of a distributed computing system can be utilized properly for providing shorter response times and higher throughput than a single-processor centralized system. For example, if there are two different programs to be run, two processors are evidently more powerful than one because the programs can be simultaneously run on different processors. Furthermore, if a particular computation can be partitioned into a number of subcomputations that can run concurrently, in a distributed computing system all the subcomputations can be simultaneously run with each one on a different processor. Distributed computing systems with very fast communication networks are increasingly being used as parallel computers to solve single complex problems rapidly. Another method often used in distributed computing systems for achieving better overall performance is to distribute the load more evenly among the multiple processors by moving jobs from currently overloaded processors to lightly loaded ones. For example, in a distributed computing system based on the workstation model, if a user currently has two processes to run, out of which one is an interactive process and the other is a process that can be run in the background, it may be advantageous to run the interactive process on the home node of the user and the other one on a remote idle node (if any node is idle). 1.4.6 Higher Reliability Reliability refers to the degree of tolerance against errors and component failures in a system [Stankovic 1984]. A reliable system prevents loss of information even in the event of component failures. The multiplicity of storage devices and processors in a distributed computing system allows the maintenance of multiple copies of critical information within

– 34 of 763 –

Sec. 1.4 • Why Are Distributed Computing Systems Gaining Popularity? 15 the system and the execution of important computations redundantly to protect them against catastrophic failures. With this approach, if one of the processors fails, the computation can be successfully completed at the other processor, and if one of the storage devices fails, the information can still be used from the other storage device. Furthermore, the geographical distribution of the processors and other resources in a distributed computing system limits the scope of failures caused by natural disasters. An important aspect of reliability is availability, which refers to the fraction of time for which a system is available for usc. In comparison to a centralized system, a distributed computing system also enjoys the advantage of increased availability. For example, if the processor of a centralized system fails (assuming that it is a single-processor centralized system), the entire system breaks down and no useful work can be performed. However, in the case of a distributed computing system, a few parts of the system can be down without interrupting the jobs of the users who are using the other parts of the system, For example, if a workstation of a distributed computing system that is based on the workstation-server model fails, only the user of that workstation is affected. Other users of the system are not affected by this failure. Similarly, in a distributed computing system based on the processor- pool mode), if some of the processors in the pool are down at any moment, the system can continue to function normally, simply with some loss in performance that is proportional to the number of processors that are down. In this case, none of the users is affected and the users cannot even know that some of the processors are down. The advantage of higher reliability is an important reason for the use of distributed computing systems for critical applications whose failure may be disastrous. However, often reliability comes at the cost of performance. Therefore, it is necessary to maintain a balance between the two. 1.4.7 Extensibility and Incremental Growth Another major advantage of distributed computing systems is that they are capable of incremental growth. That is, it is possible to gradually extend the power and functionality of a distributed computing system by simply adding additional resources (both hardware and software) to the system as and when the need arises. For example, additional processors can be easily added to the system to ha~dle the increased workload of an organization that might have resulted from its expansion. Incremental growth is a very attractive feature because for most existing and proposed applications it is practically impossible to predict future demands of the system. Extensibility is also easier in a distributed computing system because addition of new resources to an existing system can be performed without significant disruption of the normal functioning of the system. Properly designed distributed computing systems that have the property of extensibility and incremental growth are called open distributed systems. 1.4.8 Setter Flexibility in M••tlng Users’ Needs Different types of computers are usually more suitable for performing different types of computations. For example, computers with ordinary power are suitable for ordinary data processing jobs, whereas high-performance computers are more suitable for complex

– 35 of 763 –

16 Chap. 1 • Fundamentals mathematical computations. In a centralized system, the users have to perform all types of computations on the only available computer. However, a distributed computing system may have a pool of different types of computers, in which case the most appropriate one can be selected for processing a user’s job depending on the nature of the job. For instance, we saw that in a distributedcomputing system that is based on the hybrid model, interactive jobs can be processed at a user’s. own workstation and the processors in the pool may be used to process noninteractive, computation-intensivejobs. Note that the advantages of distributed computing systems mentioned above are not achieved automatically but depend on the careful design of a distributed computing system. This book deals with the various design methodologies that may be used to achieve these advantages. 1.5 WHAT IS A DISTRI8UTED OPERATING SYSTEM? Tanenbaumand VanRenesse [1985]define an operating system as a program that controls the resources of a computer system and provides its users with an interface or virtual machine that is more convenient to use than the bare machine. According to this definition, the two primary tasks of an operating system are as follows:

  1. To present users with a virtual machine that is easier to program than the underlying hardware.
  2. To manage the various resources of the system. This involves performing such tasks as keeping track of who is using which resource, granting resource requests, accounting for resource usage, and mediating conflicting requests from different programs and users. Therefore, the users’ view of a computer system, the manner in which the users access the various resources of the computer system, and the ways in which the resource requests are granted depend to a great extent on the operating system of the computer system. The operating systems commonly used for distributed computing systems can be broadly classified into two types-network operating systems and distributed operating systems. The three most important features commonly used to differentiate between these two types of operating systems are system image, autonomy, and fault tolerance capability. These features are explained below.
  3. System image. The most important feature used to differentiate between the two types of operating systems is the image of the distributed computing system from the point of view of its users. In case of a network operating system, the users view the distributed computing system as a collection of distinct machines connected by a communication subsystem. That is, the users are aware of the fact that multiple computers are being used. On the other hand, a distributed operating system hides the existence of multiple computers and provides a single-system image to its users. That is, it makes a collection

– 36 of 763 –

Sec. 1.5 • What Is a Distributed Operating System? 17 of networked machines act as a virtual uniprocessor. The difference between the two types of operating systems based on this feature can be best illustrated with the help of examples. Two such examples are presented below. In the case of a network operating system, although a user can run a job on any machine of the distributed computing system, he or she is fully aware of the machine on which his or her job is executed. This is because, by default, a user’s job is executed on the machine on which the user is currently logged. If the user wants to execute a job on a different machine, he or she should either log on to that machine by using some kind of “remote login” command or use a special command for remote execution to specify the machine on which the job is to be executed. In either case, the user knows the machine on which the job is executed. On the other hand, a distributed operating system dynamically and automatically allocates jobs to the various machines of the system for processing. Therefore, a user of a distributed operating system generally has no knowledge of the machine on which a job is executed. That is, the selection of a machine for executing a job is entirely manual in the case of network operating systems but is automatic in the case of distributed operating systems. With a network operating system, a user is generally required to know the location of a resource to access it, and different sets of system calls have to be used for accessing local and remote resources. On the other hand, users of a distributed operating system need not keep track of the locations of various resources for accessing them, and the same set of system calls is used for accessing both local and remote resources. For instance, users of a network operating system are usually aware of where each of their files is stored and must use explicit file transfer commands for moving a file from one machine to another, but the users of a distributed operating system have no knowledge of the location of their files within the system and use the same command to access a file irrespective of whether it is on the local machine or on a remote machine. That is, control over file placement is done manually by the users in a network operating system but automatically by the system in a distributed operating system. Notice that the key concept behind this feature is “transparency.” We will see later in this chapter that a distributed operating system has to support several fOnDS of transparency to achieve the goal of providing a single-system image to its users. Moreover, it is important to note here that with the current state of the art in distributed operating systems, this goal is not fully achievable. Researchers are still working hard to achieve this goal. 2. Autonomy. A network operating system is built on a set of existing centralized operating systems and handles the interfacing and coordination of remote operations and communications between these operating systems. That is, in the case of a network operating system, each computer of the distributed computing system has its own local operating system (the operating systems of different computers may be the same or different), and there is essentially no coordination at aJI among the computers except for the rule that when two processes of different computers communicate with each other, they must use a mutually agreed on communication protocol. Each computer functions independently of other computers in the sense that each one makes independent decisions about the creation and termination of their own processes and management of local

– 37 of 763 –

18 Chap. 1 • Fundamentals resources. Notice that due to the possibility of difference in local operating systems, the system calls for different computers of the same distributed computing system may be different in this case. On the other hand, with a distributed operating system, there is a single systemwide operating system and each computer of the distributed computing system runs a part of this global operating system. The distributed operating system tightly interweaves all the computers of the distributed computing system in the sense that they work in close cooperation with each other for the efficient and effective utilization of the various resources of the system. That is, processes and several resources are managed globally (some resources are managed locally). Moreover, there is a single set of globally valid system calls available on all computers of the distributed computing system. The set of system calls that an operating system supports are implemented by a set of programs called the kernel of the operating system. The kernel manages and controls the hardware of the computer system to provide the facilities and resources that are accessed by other programs through system calls, To make the same set of system calls globally valid, with a distributed operating system identical kernels are run on all the computers of a distributed computing system. The kernels of different computers often cooperate with each other in making global decisions, such as finding the most suitable machine for executing a newly created process in the system. In short, it can be said that the degree of autonomy of each machine of a distributed computing system that uses a network operating system is considerably high as compared to that of machines of a distributed computing system that uses a distributed operating system. 3. Fault tolerance capability. A network operating system provides little or no fault tolerance capability in the sense that if 10% of the machines of the entire distributed computing system are down at any moment, at least 10% of the users are unable to continue with their work. On the other hand, with a distributed operating system, most of the users are normally unaffected by the failed machines and can continue to perform their work normally, with only a 10% loss in performance of the entire’ distributed computing system. Therefore, the fault tolerance capability of a distributed operating system is usually very high as compared to that of a network operating system. The following definition of a distributed operating system given by Tanenbaum and Van Renesse [1985] covers most of its features mentioned above: A distributed operating system is one that looks to its users like an ordinary centralized operating system but runs on multiple, independent central processing units (CPUs). The key concept here is transparency. In other words, the use of multiple processors should be invisible (transparent) to the user. Another way of expressing the same idea is to say that the user views the system as a “virtual uniprocessor,” not as a collection of distinct machines. [P.419]. A distributed computing system that uses a network operating system is usually referred to as a network system, whereas one that uses a distributed operating system is

– 38 of 763 –

Sec. 1.6 • Issues in Designing a Distributed Operating System 19 usually referred to as a true distributed system (or simply a distributed system). In this book, the term distributed system will be used to mean a true distributed system. Note that with the current state of the art in distributed operating systems, it is not possible to design a completely true distributed system. Completely true distributed systems are the ultimate goal of researchers working in the area of distributed operating systems. 1.6 ISSUES IN DESIGNING A DISTRIBUTED OPERATING SYSTEM In general, designing a distributed operating system is more difficult than designing a centralized operating system for several reasons. In the design of a centralized operating system, it is assumed that the operating system has access to complete and accurate information about the environment in which it is functioning. For example, a centralized operating system can request status information, being assured that the interrogated component will not change state while awaiting a decision based on that status information, since only the single operating system asking the question may give commands. However, a distributed operating system must be designed with the assumption that complete information about the system environment will never be available. In a distributed system, the resources are physically separated, there is no common clock among the multiple processors, delivery of messages is delayed, and messages could even be lost. Due to all these reasons, a distributed operating system does not have up-to-date, consistent knowledge about the state of the various components of the underlying distributed system. Obviously, lack of up-to-date and consistent information makes many things (such as management of resources and synchronization of cooperating activities) much harder in the design of a distributed ’operating system. For example, it is hard to schedule the processors optimally if the operating system is not sure how many of them are up at the moment. Despite these complexities and difficulties, a distributed operating system must be designed to provide an the advantages of a distributed system to its users. That is, the users should be able to view a distributed system as a virtual centralized system that is flexible, efficient, reliable, secure, and easy to use. To meet this challenge, the designers of a distributed operating system must deal with several design issues. Some of the key design issues are described below. The rest of the chapters of this book basically contain detailed descriptions of these design issues and the commonly used techniques to deal with them. 1.6.1 Transparency We saw that one of the main goals of a distributed operating system is to make the existence of multiple computers invisible (transparent) and provide a single system image to its users. That is, a distributed operating system must be designed in such a way that a collection of distinct machines connected by a communication subsystem

– 39 of 763 –

20 Chap. 1 • Fundamentals appears to its users as a virtual uniprocessor. Achieving complete transparency is a difficult task and requires that several different aspects of transparency be supported by the distributed operating system. The eight forms of transparency identified by the International Standards Organization’s Reference Model for Open Distributed Process- ing [ISO 1992] are access transparency, location transparency, replication transparency, failure transparency, migration transparency, concurrency transparency, performance transparency, and scaling transparency. These transparency aspects are described below. Access Transparency Access transparency means that users should not need or be able to recognize whether a resource (hardware or software) is remote or local. This implies that the distributed operating system should allow users to access remote resources in the same way as local resources. That is, the user interface, which takes the form of a set of system calls, should not distinguish between local and remote resources, and it should be the responsibility of the distributed operating system to locate the resources and to arrange for servicing user requests in a user-transparent manner. This requirement calls for a well-designed

[…content truncated for processing]