OPERATING SYSTEM PRINCIPLES CTA eee y wi \ a STUDENT _ } \ EDITION 7 ei RESTRICTED! FOR SALE ONLY IN INDIA, BANGLADESH, NEPAL, PN VUES asia ea PAKISTAN, SRI LANKA dey & BHUTAN GREG GAGNEOPERATING SYSTEM PRINCIPLES Seventh Edition Copyright © 2006 by John Wiley & Sons (Asia) Pte. Ltd. All rights reserved. Authorized reprint by Wiley India (P.) Ltd., 4435/7, Ansari Road, Daryagenj, New Delhi 110 002. All rights reserved. AUTHORIZED REPRINT OF THE EDITION PUBLISHED BY JOHN WILEY & SONS (ASIA) PTE. LTD., SINGAPORE. No part of this book may be reproduced in any form without the written permission of the publisher. Bicentennial logo designer: Richard J. Pacifico Limits of Liability/Disclaimer of Warranty: The publisher and the author make no representation or warranties with respect to the accuracy or completeness of the contents of this work and specifically disclaim all warranties, including without limitation warranties of fitness for a particular purpose. No warranty may be created or extended by sales or promotional materials. The advice and strategies contained herein may not be suitable for every situation. This work is sold with the understanding that the publisher is not engaged in rendering legal, accounting, or other professional services. If professional assictance is required, the services of a competent professional person should be sought. Neither the publisher nor the author shail be liable for damages arising Nerefrom. The fact that an organization or Website if referred to in this work as a citation and/or a potential source of further infomation does not mean that ‘he author or the publisher endorses the information the organization or Website may provide or recommendations it may make. Further, readers should be aware that Intemet Websites listed in this work may have changed or disappeared between when this work was written and when it is read. Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be avaitable in electronic books. For more information about Wiley products, visit our website at www.wiley.com. Reprint : 2009 Printed at : $.B. Printers, Noida ISBN : 978-81-265-0962-1PARTONE &@ OVERVIEW Chapter1 Introduction 1.1 What Operating Systems Do 3 1.2 Computer-System Organization _6 13 Computer-System Architecture 11 14 Operating-System Structure 15 1.5 Operating-System Operations 17 1.6 Process Management 20 1.7 Memory Management 21 1.8 Storage Management 22 Chapter2 System Structures 2.1 Operating-System Services 39 22 User Operating-System Interface 41 23 System Calls 43 24 Types of System Calls 46 25 System Programs 52 2.6 Operating-System Design and Implementation 53 1.9 Protection and Security 26 1.10 Distributed Systems 28 1.11 Special-Purpose Systems 29 1.12 Computing Environments 31 1.13 Summary 34 Exercises 36 Bibliographical Notes 37 27 Operating-System Structure 56 28 Virtual Machines 62 29 Operating System Generation 66 2.10 System Boot 67 2.11 Summary 68 Exercises 69 Bibliographical Notes 74 PARTTWO @@ PROCESS MANAGEMENT Chapter3 Process-Concept 31 Overview 79 3.2 ProcessScheduling 83 3.3 Operations on Processes 87 3.4 Interprocess Communication 93 3.5 Examples of IPC Systems 100 36 Communication in Client- Server Systems 105 37 Summary 113 Exercises 114 Bibliographical Notes 122 xvxvi Chapter9 Virtual-Memory Management 9.1 Background 303 9.8 Allocating KemelMemory 340 9.2 Demand Paging 306 9.9 Other Considerations 44 9.3 Copy-on-Write 313 9.10 Operating-System Examples 350 9A Page Replacemen: 315 9.11 Summary 352 95 Allocation of Frames 327 Exercises 353 9.6 Thrashing 330 Bibliographical Notes _356 9.7 Memory-Mapped Files’ 335 PART FIVE HM STORAGE MANAGEMENT Chapter 10 File System 10.1 File Concept 359 10.6 Protection 386 10.2 Access Methods 367 10.7 Summary 391 10.3 Directory Structure 369 Exercises 392 10.4 File-System Mounting 379 Bibliographical Notes 392 10.5 File Sharing 381 Chapter 11 Implementing File Systems 11.1 File-System Structure 395 11.8 Log-Structured File Systems 421 11.2 File-System Implementation 397 11.9 NFS 422 11.3 Directory Implementation 403 11.10 Example: The WAFL File System 428. 11.4 Allocation Methods 404 1111 Summary 429 11.5 Free-Space Management 413 Exercises 431 11.6 Efficiency and Performance 415 Bibliographical Notes 432 1L7 Recovery 419 Chapter 12° Secondary-Storage Structure 12.1 Overview of Mass-Storage 12.7 RAIDStructure 451 Structure 435 12.8 Stable-Storage Implementation 459 12.2 Disk Structure 437 12.9 Tertiary-Storage Structure 460 12.3 Disk Attachment 438 12.10 Summary 470 124 Disk Scheduling 440 Exercises 471 12.5 Disk Management 445 Bibliographical Notes 475 12.6 Swap-Space Management 449 Chapter 13 I/O Systems 13.1 Overview 477, 13.6 STREAMS 502 13.2 1/O Hardware 478 137 Performance 504 13.3 Application I/O Interface 487 13.8 Summary 507 13.4 Kernel 1/O Subsystem 492 Exercises 508 13.5 Transforming I/O Requests to Bibliographical Notes 508 Hardware Operations 499Part One An operating system acts as an intermediary between the user of a computer and the computer hardware. The purpose of an operating system is to provide an environment in which a user can execute Programs in a convenient and efficient manner. ‘An operating system is software that manages the computer hard- ware. The hardware must provide appropriate mechanisms to ensure the correct operation of the computer system and to prevent user programs from interfering with the proper operation of the system. Internally, operating systems vary greatly in their makeup, since they are organized along many different lines. The design of a new operating system is a major task. It is important that the goals of the system be well defined before the design begins. These goals form the basis for choices among various algorithms and strategies. Because an operating system islarge and complex, it must be created piece by piece. Each of these pieces should be a well delineated portion of the system, with carefully defined inputs, outputs, and functions.1.2 Chapter1 {introduc space and lack even a full-screen editor, whereas others require gigabytes of space and are entirely based on graphical windowing systems. (A kilobyte, or KB, is 1,024 bytes; a megabyte, or MB, is 1,024” bytes; and a gigabyte, or GB, is 1,024? bytes. Computer manufacturers often round off these numbers and say that a megabyte is 1 million bytes and a gigabyte is 1 billion bytes.) A more common definition is that the operating system is the one program running at all times on the computer (usually called the kernel), with all else being systems programs and application programs. This last definition is the one that we generally follow. The matter of what constitutes an operating system has become increas- * ingly important. In 1998, the United States Department of Justice filed suit against Microsoft, in essence claiming that Microsoft included too much func- tionality in its operating systems and thus prevented application vendors from competing. For example, a web browser was an integral part of the operating, system. As a result, Microsoft was found guilty of using its operating system monopoly to limit competition. 2m Organization Before we can explore the details of how computer systems operate, we need a general knowledge of the structure of a computer system. In this section, we look at several parts of this structure to round out our background knowledge. The section is mostly concerned’ with computer-system organization, so you can skim or skip it if you already understand the concepts. 1.2.1. Computer-System Operation A modern general-purpose computer system consists of one or more CPUS and a number of device controllers connected through a common bus that provides access to shared memory (Figure 1.2). Each device controller is in charge of a specific type of device (for example, disk drives, audio devices, and video displays). The CPU and the device controllers can execute concurrently, mouse keyboard Se 5 cpu | se USB controller me,nory | Figure 1.2. A modem computer system.10 Chapter 1 iniroductic cheaper. The top four levels of memory in Figure 1.4 may be constructed using semiconductor memory. In addition to differing in speed and cost, the various storage systems are either volatile or nonvolatile. As mentioned earlier, volatile storage loses its contents when the power to the device is removed. In the absence of expensive battery and generator backup systems, data must be written to nonvolatile storage for safekeeping. In the hierarchy shown in Figure 14, the storage systems above the electronic disk are volatile, whereas those below are nonvolatile. An electronic disk can be designed to be either volatile or nonvolatile. During normal operation, the electronic disk stores data in a large DRAM array, which is volatile. But many electronic-disk devices contain a hidden magnetic hard disk and a battery for backup power. If external power is interrupted, the electronic-disk controller copies the data from RAM to the magnetic disk. When external power is restored, the controller copies the data back into the RAM. Another form of electronic disk is flash memory, which is popular in cameras and personal digital assistants (PDAs), in robots, and incteasingly as removable storage on general-purpose computers. Flash memory is slower than DRAM but needs no power to retain its contents. Another form of nonvolatile storage is NVRAM, which is DRAM with battery backup power. This memory can be as fast as DRAM but has a’ limited duration in which it is nonvolatile. The cesign of a complete memory system must balance all the factors just discussed: It must use only as much expensive memory as necessary while providing as much inexpensive, nonvolatile memory as possible. Caches can be installed to improve performance where a large access-time or transfer-rate disparity exists between two components. 1.2.3 I/O Structure Storage is only one of many types of 1/0 devices within a computer. A large portion of operating system code is dedicated to managing 1/0, both because of its importance to the reliability and performance of a system and because of the varying nature of the devices. Therefore, we now provide an overview of y/o. A general-purpose computer system consists of CPUs and multiple device controllers that are connected through a common bus. Each device controller is in charge of a specific type of device. Depending on the controller, there may be more than one attached device. For instance, seven or more devices can be attached to the small computer-systems interface (SCSI) controller. A device controller maintains some local buffer storage and a set of special-purpose registers. The device controller is responsible for moving the data between the peripheral devices that it controls and its local buffer storage. Typically, operating systems have a device driver for each device controller. This device driver understands the device controller and presents a uniform interface to the device to the rest of the operating system. To start an 1/0 operation, the device driver loads the appropriate registers within the device controller. The device controller, in turn, examines the contents of these registers to determine what action to take (such as “read a character from the keyboard”). The controller starts the transfer of data from the device to its local buffer. Once the transfer of data is complete, the device4 Chapter 1 resulting in inefficiencies. These inefficiencies can be avoided if the processors share certain data structures. A multiprocessor system of this form will allow processes and resources—such as memory—to be shared dynamically among the various processors and can lower the variance among the processors. Such a system must be written carefully, as we shall see in Chapter 6. Virtually all modern operating systems— including Windows, Windows XP, Mac OS x, and Linux—now provide support for SMP. The difference between symmetric and asymmetric multiprocessing may result from either hardware or software, Special hardware can differentiate the multiple processors, or the software can be written toallow only one master and multiple slaves. For instance, Sun's operating system SunOS Version 4 provided asymmetric multiprocessing, whereas Version 5 (Solaris) is symmetric on the same hardware. A recent trend in CPU design is to include multiple compute cores on a single chip. In essence, these are multiprocessor chips. Two-way chips are becoming mainstream, while N-way chips are going to be common in high-end systems. Aside from architectural considerations such as cache, memory, and bus contention, these multi-core CPUs look to the operating system just as N standard processors. Lastly, blade servers are a recent development in which multiple processor boards, [/O boards, and networking boards are placed in the same chassis. The difference between these and traditional multiprocessor systems is that each blade-processor board boots independently and runs its own operating system. Some blade-server boards are multiprocessor as well, which blurs the lines between types of computers. In essence, those servers consist of multiple independent multiprocessor systems. 1.3.2 Clustered Systems Another type of multiple-CPU system is the clustered system. Like multipro- cessor systems, clustered systems gather together multiple CPUs to accomplish computational work. Clustered systems differ from multiprocessor systems, however, in that they are composed of two or more individual systems coupied together. The definition of the term clustered is not concrete; many commercial packages wrestle with what a clustered system is and why one form is better than another. The generally accepted definition is that clustered computers share storage and are closely linked via a local-area network (LAN) {as described in Section 1.10) or a faster interconnect such as InfiniBand. Clustering is usually used to provide high-availability service; that is, service will continue even if one or more systems in the cluster fail. High availability is generally obtained by adding a level of redundancy in the system. A layer of cluster software runs on the cluster nodes. Each node can monitor one or more of the others (over the LAN). If the monitored machine fails, the monitoring machine can take ownership of its storage and restart the applications that were running on the failed machine. The users and clients of the applications see only a brief interruption of service. Clustering can be structured asymmetrically or symmetrically. In asym- metric clustering, one machine is in hot-standby mode while the other is running the applications. The hot-standby host machine does nothing but monitor the active server. If that server fails, the hot-standby host becomes the18 Chapter 1 be performed. The interrupt-driven nature of an operating system defines that system’s general structure. For each type of interrupt, separate segments of code in the operating system determine what action should be taken. An interrupt service routine is provided that is responsible for dealing with the interrupt. Since the operating system and the users share the hardware and software resources of the computer system, we need to make sure that an error ina user program could cause probiems only for the one program that was running. With sharing, many processes could be adversely affected by a bug in one program. For example, if a process gets stuck in an infinite loop, this loop could prevent the correct operation of many other processes. More subtle errors can occur in a multiprogramming system, where one erroneous program might modify another program, the data of another program, or even the operating system itself. Without protection against these sorts of errors, either the computer must execute only one process at a time or all output must be suspect. A properly designed operating system must ensure that an incorrect (or malicious) program cannot cause other programs to execute incorrectly. 1.5.1 Dual-Mode Operation In order to ensure the proper execution of the operating system, we must be able to distinguish between the execution of operating-system code and user- defined code. The approach taken by most computer systems is to provide hardware support that allows us to differentiate among various modes of execution. At the very least, we need two separate modes of operation: user mode and kernel mode (also called supervisor mode, system mode, or privileged mode). A bit, called the mode bit, is added to the hardware of the computer to indicate the current mode: kernel (0) or user (1). With the mode bit, we are able to distinguish between a task that is executed on behalf of the operating system and one that is executed on behalf of the user. When the computer system is executing on behalf of a user application, the system is in user mode. However, when a user application requests a service from the operating system (via a system call), it must transition from user to kernel mode to fulfill the request. This is shown in Figure 1.8. As we shall see, this architectural enhancement is useful for many other aspects of system operation as well. ser process el user mode ing LI calls system retum from system call || (ede = 1) a ea eo att - ¥ ; trap return ] kernel mode bit =0 mode bit = 1 | | kernel mode (made bit = 0) stem call Figure 1.8 Transition from user to kernel mode.