DISTRIBUTED OPERATING SYSTEMS CONCEPTS & PRACTICE DOREEN L. GALLI Distributed Operating Systems Concepts and Practice Doreen L. Galli, Ph.D. Prentice Hall Upper Saddle River, NJ 07458 Publisher: Alan Apt Editorial supervision/page composition: Scott Disanno Editor-in Chief: Marcia Horton Executive Managing Editor: Vince O’Brien Managing Editor: Eileen Clark Director of production and manufacturing: David W. Riccardi Cover design director: Jerry Votta Cover design: Heather Scott Manufacturing buyer: Pat Brown Cover art: Blanchard, Andy, (www.andyblanchard.com) Detail of Astral Forest, 1998. Acrylic on Wood, 4CTx24’\ Private Collection. © 1998 Galli Enterprises, Atlanta Georgia. © 2000 by Prentice Hall Prentice-Hall, Inc. Upper Saddle River, New Jersey 07458 Prentice Hall books are widely used by corporations and government agencies for training, market­ ing, and resale. The publisher offers discounts on this book when ordered in bulk quantities. For more information, contact Corporate Sales Department, Phone: 800-382-3419; FAX: 201-236-7141 E-mail: [email protected] or write Prentice Hall, One Lake Street, Upper Saddle River, NJ 07458. All rights reserved. No part of this book may be reproduced, in any form or by any means, without permission in writing from the publisher. Printed in the United States of America IO 9 8 7 6 5 4 3 2 1 ISBN 0-13-079843-6 Prcnticc-Hall International (UK) Limited, London Prentice-Hall of Australia Pty. Limited, Sydney Prentice-Hall Canada Inc., Toronto Prentice-Hall Hispanoamericana, S.A., Mexico Prcnticc-Hall of India Private Limited, New Delhi Prentice-Hall of Japan, Inc., Tokyo Prcnticc-Hall (Singapore) Ptc. Ltd., Singapore Editora Prentice-Hall do Brasil, Ltda., Rio de Janeiro To my loving husband, Marc and my little ones, Marc Jr. and Steven Preface 1 his book examines concepts and practice in distributed computing. It is designed to be useful not only for students but for practitioners and corporate training as well. Over the past decade, computer systems have become in­ creasingly more advanced. Most computers are connected to some type of network on a regular basis. The installation of LANs at smaller businesses is even becoming common­ place. LANs are also being installed in custom homes at an ever-increasing rate. Software technology must keep up and so must our future and current practitioners! At the current pace, it is only a matter time before a working knowledge of distributed systems is manda­ tory for all computer scientists, because this technology pertains to a majority of all comput­ ers and their applications. Intended Audience While the study of standard operating system concepts is extremely important lor computer science undergraduates, there is a significant and ever-increasing demand to extend this knowledge in the graduate and fourth-year undergraduate curriculum as well as for the practitioner out in industry. Therefore, there is a great need to study distributed operating v VI Preface systems concepts as well as practical solutions and approaches. This hook is intended to meet this need for both students and practitioners. Objective The objective of this book is to describe in detail each major aspect of distributed operating systems from a conceptual and practical viewpoint. Thus, it includes relevant examples of real operating systems to reinforce the concepts and to illustrate the decisions that must be made by distributed system designers. Operating systems such as Amoeba, Clouds and Cho­ rus (the base technology for JavaOS) are utilized as examples throughout the book. In addi­ tion, the case study on Windows 2000,M provides an example of a real commercial solution. Technologies such as CORBA, DCOM, NFS, LDAP, X.500, Kerberos, RSA, DES, SSH, and NTP are also included to demonstrate real-life solutions to various aspects of distributed computing. In addition, a simple client/server application is included in the appendix that demonstrate key distributed computing programming concepts such as the use of 1NET sockets, pthreads, and synchronization via mutex operations. In summary, this book focuses on the concepts, theory and practice in distributed sys­ tems. It is designed to be useful for practitioners, fourth year undergraduate as well as graduate level students and assumes that the reader has taken a basic operating system course. It is hoped that this book will prove to be invaluable not only for those already ac­ tive in industry who wish to update and enhance one’s knowledge base but also for future reference for those who have used it as a course text. Organization and Pedagogical Features This book is divided into two parts. The first part, Chapter 1-6, presents the base foundation for distributed computing. The second part, Chapter 7-11, expands on these topics and delves more heavily into advanced distributed operating system topics. The pedagogical features included in this book are the following. 1 2 3 4 5 1. Detail Boxes to further enhance understanding. These boxes contain in­ forma tion such as complex algorithms and more in depth examples. 2. More than 150 figures and tables to help illustrate concepts. 3. A case study of Windows 2000lM to demonstrate a real life commercial solutions. 4. Project oriented exercises (those with italicized numbers) to provide "hands on" experience. 5. Exercises that build upon concepts covered in earlier chapters. Preface VII 6. Reference pointers to relevant sources including: A. overview sources for further in-depth study, B. research papers, and C. 'core1 web & ftp sites. 7. A simplified distributed application program to demonstrate key distribut­ ing programming concepts. 8. Comprehensive glossary of terms (boldfaced words appear in the glos­ sary) to provide a centralized location for key definitions. 9. Complete list of acronyms to aid readability and provide a centralized lo­ cation for easy reference. 10. Chapter summaries. 11. Comprehensive index, primary references in bold. 12. Book website located at www.prenhall.com/galli. Suggestions for Instructors This book is designed to provide maximum flexibility to instructors and has pedagogical features inherent within the text to allow you to customize the coverage to best meet the needs of your class and your institution’s mission statement. In preparing this book, the only assumption made is that a basic introductory to operating systems course has been taken by the reader. Select topics that may be included in an introductory operating system course but are sometimes omitted, covered lightly, often not grasped or may have been forgotten but nonetheless are key to distributed operating systems, are included where appropriate. This material need not be presented in the classroom but is included in the book so that you can be assured that the students have the basis necessary for the more advanced distributed top­ ics. Below are suggestions on how this book may be used for those requiring additional practical emphasis as well as for those desiring additional research emphasis. A graduate course desiring to add both types of emphasis may wish to use suggestions from both cate­ gories. Additional information may be available at the author’s Prentice Hall website, www.prenhall.com/galli. Adding Practical Emphasis The following are a few suggestions for adding practical emphasis to a course utilizing this text. viii Preface 1. Have the students, either individually or as a group complete one or more of the ‘Project Exercises', those indicated by an italicized exercise number at the end of relevant chapters. Additional practical experience may be achieved if their design and implementation is orally presented to the class. 2. Cover all Detail Boxes related to real-life implementations. 3. Spend class time covering the Windows 20001M Case study. 4. Create an individual or group project working with the distributed features of Windows 2000™. 5. Have the students expand or change the Surgical Scheduling Program. This may be as simple as changing the type of interprocess communication em­ ployed or as complex as creating another program utilizing the same dis­ tributed concepts. Adding Research Emphasis The following are a few suggestions for adding a research emphasis to a course utilizing this book. 1 2 3 4 1. Have the students, either individually or as a group, prepare a paper on a topic relevant to distributed operating systems. Reference papers cited at the end of each chapter should serve as good starting points. These projects may include an oral presentation. 2. Present lecture material from the relevant RFCs or research papers cited at the end of each chapter that arc available on the web and include it the list of required reading for the students. 3. Have the students seek the relevant RFCs or research papers cited at the end of each chapter that are available on the web and prepare a summary. 4. Select a subset of the reference papers cited at the end of each chapter and create a spiral bound accompaniment to be used in conjunction throughout the course with the book. A large number of bookstores at research institu­ tions have the ability to perform the copyright clearing necessary for this purpose. Contents 1. Introduction to Distributed Systems 1 1.1 What is an Operating System? 1 1.2 What is a Distributed System? 2 1.2.1 Popular Network Topologies and Features 4 1.2.2 1SO/OSÍ Reference Model 8 1.2.3 Distributed Computing Models 12 1.2.4 Distributed versus Centralized Solutions 14 1.2.5 Network vs. Distributed Operating Systems 15 1.3 What is a Real-Time System? 16 1.3.1 Real-time Event Characteristics 17 1.3.2 Network Characteristics Affecting Distributed Real-Time Applications 17 1.4 What is a Parallel System? 19 1.4.1 Parallel Architectures 19 1.4.2 Parallel Software Paradigms 23 1.5 Sample Distributed Application 25 1.6 Summary 27 1.7 References for Further Study 27 Exercises 28 2. The Kernel 31 2./ Kernel Types 31 2.2 Processes and Threads 33 2.2.1 Introduction to Multi-threaded Processes 33 2.2.2 Multi-threaded Process Paradigms 34 2.2.3 Multi-threaded support 37 2.3 Process Management 38 2.3.1 Types of Processes 40 2.3.2 Load Distribution & Process Migration 41 2.4 Process Scheduling 45 2.4.1 Identifying Processes for Scheduling 45 2.4.2 Scheduler Organization 45 2.5 Summary 46 ix