Operating System Concepts / Edition 7

by Abraham Silberschatz, Peter B. Galvin, Greg Gagne

Overview

TAKE THE NEXT STEP IN THE EVOLUTION OF OPERATING SYSTEMS

For the past two decades, dinosaurs have roamed the cover of Silberschatz, Galvin, and Gagne's OPERATING SYSTEMS CONCPETS. The product of a long process of evolutionary adaptations, this best-selling text has continually evolved to address the latest trends in operating system design. With its strong emphasis underlying concepts and rich selection of examples and case studies, no other text provides such a solid theoretical foundation for understanding operating systems.

Now in a fully revised and updated Sixth Edition, OPERATING SYSTEM CONCEPTS offers new chapters on Threads and Windows 2000, as well as new and expanded coverage of the client-server model and NFS, small footprint operating systems for PDAs, real-time operating systems, and more.

Product Details

ISBN-13:	9780471694663
Publisher:	Wiley
Publication date:	12/28/2004
Edition description:	Older Edition
Pages:	944
Product dimensions:	7.32(w) x 10.12(h) x 1.49(d)

About the Author

Abraham Silberichatz is the director of the Information Sciences Research Center at Bell Laboratories in Murray Hill, New Jersey. Prior to joining Bell Labs, he held a chaired professorship in the Department of Computer Sciences at the University of Texas at Austin. Dr. Silberschatz is a Fellow of the ACM. He is recognized as a leading researcher, educator, and author in operating systems, database systems, and distributed systems. His writings have appeared in numerous ACM and IEEE publications, as well as in other journals and proceedings of professional conferences. He is the coauthor of the textbook Database System Concepts (Third Edition, McGraw-Hill, 1997).

Peter Baer Galvin is the Chief Technologist for Corporate Technologies, a systems-integration and consulting company. He is also Adjunct Systems Planner for Brown University's Computer Science Department. Mr. Galvin is on the Board of Directors for the Sun User Group and has presented talks and tutorials worldwide on the topics of system management, security, and performance. He is the security columnist for SunWorld Magazine.

Read an Excerpt

Chapter 3: Operating-System Structures

3.6.1 Implementation

Although the virtual machine concept is useful, it is difficult to implement. Much effort is required to provide an exact duplicate of the underlying machine. Remember that the underlying machine has two modes: user mode and monitor mode. The virtual-machine software can run in monitor mode, since it is the operating system. The virtual machine itself can execute in only user mode. Just as the physical machine has two modes, however, so must the virtual machine. Consequently, we must have a virtual user mode and a virtual monitor mode, both of which run in a physical user mode. Those actions that cause a transfer from user mode to monitor mode on a real machine (such as a system call or an attempt to execute a privileged instruction) must also cause a transfer from virtual user mode to virtual monitor mode on a virtual machine.

This transfer can generally be done fairly easily. When a system call, for example, is made by a program running on a virtual machine, in virtual user mode, it will cause a transfer to the virtual-machine monitor in the real machine. When the virtual-machine monitor gains control, it can change the register contents and program counter for the virtual machine to simulate the effect of the system call. It can then restart the virtual machine, noting that it is now in virtual monitor mode. If the virtual machine then tries, for example, to read from its virtual card reader, it will execute a privileged I/O instruction. Because the virtual machine is running in physical user mode, this instruction will trap to the virtual-machine monitor. The virtual-machine monitor must then simulate the effect of the I/O instruction. First, it finds the spooled file that implements the virtual card reader. Then, it translates the read of the virtual card reader into a read on the spooled disk file, and transfers the next virtual "card image" into the virtual memory of the virtual machine. Finally, it can restart the virtual machine. The state of the virtual machine has been modified exactly as though the I/O instruction had been executed with a real card reader for a real machine executing in a real monitor mode.

The major difference is, of course, time. Whereas the real I/O might have taken 100 milliseconds, the virtual I/O might take less time (because it is spooled) or more (because it is interpreted). In addition, the CPU is being multiprogrammed among many virtual machines, further slowing down the virtual machines in unpredictable ways. In the extreme case, it may be necessary to simulate all instructions to provide a true virtual machine. VM works for IBM machines because normal instructions for the virtual machines can execute directly on the hardware. Only the privileged instructions (needed mainly for I/O) must be simulated and hence execute more slowly.

3.6.2 Benefits

The virtual-machine concept has several advantages. Notice that in this environment there is complete protection of the various system resources. Each virtual machine is completely isolated from all other virtual machines, so there are no security problems. On the other hand, there is no direct sharing of resources. To provide sharing, two approaches have been implemented. First, it is possible to share a minidisk. This scheme is modeled after a physical shared disk, but is implemented by software. With this technique, files can be shared. Second, it is possible to define a network of virtual machines, each of which can send information over the virtual communications network. Again, the network is modeled after physical communication networks, but is implemented in software.

Such a virtual-machine system is a perfect vehicle for operating-systems research and development. Normally, changing an operating system is a difficult task. Because operating systems are large and complex programs, it is difficult to be sure that a change in one point will not cause obscure bugs in some other part. This situation can be particularly dangerous because of the power of the operating system. Because the operating system executes in monitor mode, a wrong change in a pointer could cause an error that would destroy the entire file system. Thus, it is necessary to test all changes to the operating system carefully.

The operating system, however, runs on and controls the entire machine. Therefore, the current system must be stopped and taken out of use while changes are made and tested. This period is commonly called system-development time. Since it makes the system unavailable to users, system-development time is often scheduled late at night or on weekends, when system load is low.

A virtual-machine system can eliminate much of this problem. System programmers are given their own virtual machine, and system development is done on the virtual machine, instead of on a physical machine. Normal system operation seldom needs to be disrupted for system development.

Virtual machines are coming back into fashion as a means of solving system compatibility problems. For instance, there are thousands of programs available for MS-DOS on Intel CPU-based systems. Computer vendors like Sun Microsystems and Digital Equipment Corporation (DEC) use other, faster processors, but would like their customers to be able to run these MS-DOS programs. The solution is to create a virtual Intel machine on top of the native processor. An MS-DOS program is run in this environment, and its Intel instructions are translated into the native instruction set. MS-DOS is also run in this virtual machine, so the program can make its system calls as usual. The net result is a program which appears to be running on an Intel-based system but is really executing on a very different processor. If the processor is sufficiently fast, the MS-DOS program will run quickly even though every instruction is being translated into several native instructions for execution. Similarly, the PowerPC-based Apple Macintosh includes a Motorola 68000 virtual machine to allow execution of binaries that were written for the older 68000-based Macintosh.

3.6.3 Java

Another example of the continued utility of virtual machines involves the Java language. Java is a very popular language designed by Sun Microsystems. Java is implemented by a compiler that generates bytecode output. These bytecodes are the instructions that run on the Java Virtual Machine (JVM). For Java programs to run on a platform, that platform must have a JVM running on it. The JVM runs on many types of computer, including IBM-Compatible PC, Macintosh, Unix workstation and server, and IBM minicomputer and mainframe. The JVM is also implemented within web browsers such as Microsoft Internet Explorer and Netscape Communicator. These browsers, in turn, run on top of varying hardware and operating systems. The JVM is also implemented on the small JavaOS, which implements the JVM directly on hardware to avoid the overhead imposed by running Java on general-purpose operating systems. Finally, single-purpose devices such as cellular phones can be implemented via Java through the use of microprocessors that execute Java bytecodes as native instructions.

The Java Virtual Machine implements a stack-based instruction set that includes the expected arithmetic, logical, data movement, and flow control instructions. Because it is a virtual machine, it can also implement instructions that are too complex to be built in hardware, including object creation, manipulation, and method invocation instructions. Java compilers can simply emit these bytecode instructions, and the JVM must implement the necessary functionality on each platform.

The design of Java takes advantage of the complete environment that a virtual machine implements. For instance, the bytecodes are checked for instructions that could compromise the security or reliability of the underlying machine. The Java program is not allowed to run if it fails this check. Through the implementation of Java as a language that executes on a virtual machine, Sun has created an efficient, dynamic, secure, and portable object-oriented facility. Although Java programs are not as fast as programs that compile to the native hardware instruction set, they nevertheless are more efficient than interpreted programs and have several advantages over native-compilation languages such as C.

3.7.0 System Design and Implementation

In this section, we discuss the problems of designing and implementing a system. There are, of course, no complete solutions to the design problems, but there are approaches that have been successful.

3.7.1 Design Goals

The first Problem in designing a system is to define the goals and specifications of the system. At the highest level, the design of the system will be affected.....

Table of Contents

Part 1	Overview
Chapter 1	Introduction
1.1	What Is an Operating System?	3
1.2	Simple Batch Systems	6
1.3	Multiprogrammed Batched Systems	8
1.4	Time-Sharing Systems	9
1.5	Personal-Computer Systems	12
1.6	Parallel Systems	14
1.7	Distributed Systems	16
1.8	Real-Time Systems	18
1.9	Summary	19
	Exercises	20
	Bibliographical Notes	21
Chapter 2	Computer-System Structures
2.1	Computer-System Operation	23
2.2	I/O Structure	26
2.3	Storage Structure	30
2.4	Storage Hierarchy	35
2.5	Hardware Protection	37
2.6	General System Architecture	43
2.7	Summary	45
	Exercises	45
	Bibliographical Notes	47
Chapter 3	Operating-System Structures
3.1	System Components	49
3.2	Operating-System Services	55
3.3	System Calls	57
3.4	System Programs	66
3.5	System Structure	68
3.6	Virtual Machines	74
3.7	System Design and Implementation	78
3.8	System Generation	81
3.9	Summary	83
	Exercises	83
	Bibliographical Notes	84
Part 2	Process Management
Chapter 4	Processes
4.1	Process Concept	89
4.2	Process Scheduling	93
4.3	Operation on Processes	97
4.4	Cooperating Processes	100
4.5	Threads	102
4.6	Interprocess Communication	108
4.7	Summary	119
	Exercises	120
	Bibliographical Notes	121
Chapter 5	CPU Scheduling
5.1	Basic Concepts	123
5.2	Scheduling Criteria	127
5.3	Scheduling Algorithms	129
5.4	Multiple-Processor Scheduling	141
5.5	Real-Time Scheduling	141
5.6	Algorithm Evaluation	144
5.7	Summary	149
	Exercises	150
	Bibliographical Notes	152
Chapter 6	Process Synchronization
6.1	Background	155
6.2	The Critical-Section Problem	157
6.3	Synchronization Hardware	164
6.4	Semaphores	167
6.5	Classical Problems of Synchronization	172
6.6	Critical Regions	177
6.7	Monitors	181
6.8	Synchronization in Solaris 2	189
6.9	Atomic Transactions	190
6.10	Summary	199
	Exercises	200
	Bibliographical Notes	204
Chapter 7	Deadlocks
7.1	System Model	207
7.2	Deadlock Characterization	209
7.3	Methods for Handling Deadlocks	212
7.4	Deadlock Prevention	214
7.5	Deadlock Avoidance	217
7.6	Deadlock Detection	223
7.7	Recovery from Deadlock	227
7.8	Combined Approach to Deadlock Handling	229
7.9	Summary	230
	Exercises	231
	Bibliographical Notes	235
Part 3	Storage Management
Chapter 8	Memory Management
8.1	Background	239
8.2	Logical versus Physical Address Space	245
8.3	Swapping	246
8.4	Contiguous Allocation	249
8.5	Paging	257
8.6	Segmentation	272
8.7	Segmentation with Paging	278
8.8	Summary	282
	Exercises	284
	Bibliographical Notes	287
Chapter 9	Virtual Memory
9.1	Background	289
9.2	Demand Paging	291
9.3	Performance of Demand Paging	297
9.4	Page Replacement	300
9.5	Page-Replacement Algorithms	303
9.6	Allocation of Frames	313
9.7	Thrashing	317
9.8	Other Considerations	322
9.9	Demand Segmentation	328
9.10	Summary	329
	Exercises	331
	Bibliographical Notes	335
Chapter 10	File-System Interface
10.1	File Concept	337
10.2	Access Methods	346
10.3	Directory Structure	349
10.4	Protection	360
10.5	Consistency Semantics	364
10.6	Summary	365
	Exercises	366
	Bibliographical Notes	368
Chapter 11	File-System Implementation
11.1	File-System Structure	369
11.2	Allocation Methods	373
11.3	Free-Space Management	382
11.4	Directory Implementation	385
11.5	Efficiency and Performance	386
11.6	Recovery	389
11.7	Summary	391
	Exercises	392
	Bibliographical Notes	393
Part 4	I/O Systems
Chapter 12	I/O Systems
12.1	Overview	397
12.2	I/O Hardware	398
12.3	Application I/O Interface	408
12.4	Kernel I/O Subsystem	414
12.5	Transforming I/O Requests to Hardware Operations	420
12.6	Performance	423
12.7	Summary	427
	Exercises	428
	Bibliographical Notes	429
Chapter 13	Secondary-Storage Structure
13.1	Disk Structure	431
13.2	Disk Scheduling	432
13.3	Disk Management	438
13.4	Swap-Space Management	442
13.5	Disk Reliability	444
13.6	Stable-Storage Implementation	446
13.7	Summary	447
	Exercises	447
	Bibliographical Notes	452
Chapter 14	Tertiary-Storage Structure
14.1	Tertiary-Storage Devices	455
14.2	Operating-System Jobs	458
14.3	Performance Issues	461
14.4	Summary	466
	Exercises	466
	Bibliographical Notes	469
Part 5	Distributed Systems
Chapter 15	Network Structures
15.1	Background	473
15.2	Motivation	475
15.3	Topology	476
15.4	Network Types	481
15.5	Communication	484
15.6	Design Strategies	491
15.7	Networking Example	495
15.8	Summary	497
	Exercises	498
	Bibliographical Notes	499
Chapter 16	Distributed System Structures
16.1	Network Operating Systems	501
16.2	Distributed Operating Systems	503
16.3	Remote Services	506
16.4	Robustness	511
16.5	Design Issues	512
16.6	Summary	515
	Exercises	516
	Bibliographical Notes	516
Chapter 17	Distributed File Systems
17.1	Background	519
17.2	Naming and Transparency	521
17.3	Remote File Access	525
17.4	Stateful versus Stateless Service	530
17.5	File Replication	531
17.6	Example Systems	532
17.7	Summary	559
	Exercises	560
	Bibliographical Notes	561
Chapter 18	Distributed Coordination
18.1	Event Ordering	563
18.2	Mutual Exclusion	566
18.3	Atomicity	569
18.4	Concurrency Control	573
18.5	Deadlock Handling	578
18.6	Election Algorithms	586
18.7	Reaching Agreement	588
18.8	Summary	591
	Exercises	592
	Bibliographical Notes	593
Part 6	Protection and Security
Chapter 19	Protection
19.1	Goals of Protection	597
19.2	Domain of Protection	598
19.3	Access Matrix	604
19.4	Implementation of Access Matrix	608
19.5	Revocation of Access Rights	611
19.6	Capability-Based Systems	613
19.7	Language-Based Protection	616
19.8	Summary	620
	Exercises	620
	Bibliographical Notes	621
Chapter 20	Security
20.1	The Security Problem	623
20.2	Authentication	625
20.3	One-Time Passwords	628
20.4	Program Threats	629
20.5	System Threats	630
20.6	Threat Monitoring	634
20.7	Encryption	637
20.8	Computer-Security Classifications	639
20.9	An Example Security Model: Windows NT	640
20.10	Summary	642
	Exercises	643
	Bibliographical Notes	644
Part 7	Case Studies
Chapter 21	The UNIX System
21.1	History	647
21.2	Design Principles	653
21.3	Programmer Interface	654
21.4	User Interface	663
21.5	Process Management	666
21.6	Memory Management	671
21.7	File System	675
21.8	I/O System	683
21.9	Interprocess Communication	687
21.10	Summary	692
	Exercises	693
	Bibliographical Notes	694
Chapter 22	The Linux System
22.1	History	697
22.2	Design Principles	702
22.3	Kernel Modules	705
22.4	Process Management	709
22.5	Scheduling	713
22.6	Memory Management	717
22.7	File Systems	725
22.8	Input and Output	730
22.9	Interprocess Communication	734
22.10	Network Structure	736
22.11	Security	738
22.12	Summary	741
	Exercises	742
	Bibliographical Notes	743
Chapter 23	Windows NT
23.1	History	745
23.2	Design Principles	746
23.3	System Components	747
23.4	Environmental Subsystems	763
23.5	File System	766
23.6	Networking	773
23.7	Programmer Interface	779
23.8	Summary	786
	Exercises	786
	Bibliographical Notes	787
Chapter 24	Historical Perspective
24.1	Early Systems	789
24.2	Atlas	795
24.3	XDS-940	796
24.4	THE	797
24.5	RC 4000	798
24.6	CTSS	799
24.7	MULTICS	799
24.8	OS/360	800
24.9	Mach	802
24.10	Other Systems	803
	Bibliography	805
	Credits	839
	Index	841