Operating System Concepts / Edition 10

by Abraham Silberschatz, Peter B. Galvin, Greg Gagne

Overview

The tenth edition of Operating System Concepts has been revised to keep it fresh and up-to-date with contemporary examples of how operating systems function, as well as enhanced interactive elements to improve learning and the student’s experience with the material. It combines instruction on concepts with real-world applications so that students can understand the practical usage of the content. End-of-chapter problems, exercises, review questions, and programming exercises help to further reinforce important concepts. New interactive self-assessment problems are provided throughout the text to help students monitor their level of understanding and progress. A Linux virtual machine (including C and Java source code and development tools) allows students to complete programming exercises that help them engage further with the material.

The Print Companion includes all of the content found in a traditional text book, organized the way you would expect it, but without the problems.

Product Details

ISBN-13:	9781119439257
Publisher:	Wiley
Publication date:	01/18/2018
Edition description:	New Edition
Pages:	976
Product dimensions:	7.00(w) x 9.90(h) x 1.50(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 ONE OVERVIEW

Chapter 1 Introduction

1.1 What Operating Systems Do 4

1.2 Computer-System Organization 7

1.3 Computer-System Architecture 15

1.4 Operating-System Operations 21

1.5 Resource Management 27

1.6 Security and Protection 33

1.7 Virtualization 34

1.8 Distributed Systems 35

1.9 Kernel Data Structures 36

1.10 Computing Environments 40

1.11 Free and Open-Source Operating Systems 46

Practice Exercises 53

Further Reading 54

Chapter 2 Operating-System Structures

2.1 Operating-System Services 55

2.2 User and Operating-System Interface 58

2.3 System Calls 62

2.4 System Services 74

2.5 Linkers and Loaders 75

2.6 Why Applications Are Operating-System Specific 77

2.7 Operating-System Design and Implementation 79

2.8 Operating-System Structure 81

2.9 Building and Booting an Operating System 92

2.10 Operating-System Debugging 95

2.11 Summary 100

Practice Exercises 101

Further Reading 101

PART TWO PROCESS MANAGEMENT

Chapter 3 Processes

3.1 Process Concept 106

3.2 Process Scheduling 110

3.3 Operations on Processes 116

3.4 Interprocess Communication 123

3.5 IPC in Shared-Memory Systems 125

3.6 IPC in Message-Passing Systems 127

3.7 Examples of IPC Systems 132

3.8 Communication in Client–Server Systems 145

3.9 Summary 153

Practice Exercises 154

Further Reading 156

Chapter 4 Threads & Concurrency

4.1 Overview 160

4.2 Multicore Programming 162

4.3 Multithreading Models 166

4.4 Thread Libraries 168

4.5 Implicit Threading 176

4.6 Threading Issues 188

4.7 Operating-System Examples 194

4.8 Summary 196

Practice Exercises 197

Further Reading 198

Chapter 5 CPU Scheduling

5.1 Basic Concepts 200

5.2 Scheduling Criteria 204

5.3 Scheduling Algorithms 205

5.4 Thread Scheduling 217

5.5 Multi-Processor Scheduling 220

5.6 Real-Time CPU Scheduling 227

5.7 Operating-System Examples 234

5.8 Algorithm Evaluation 244

5.9 Summary 250

Practice Exercises 251

Further Reading 254

PART THREE PROCESS SYNCHRONIZATION

Chapter 6 Synchronization Tools

6.1 Background 257

6.2 The Critical-Section Problem 260

6.3 Peterson’s Solution 262

6.4 Hardware Support for Synchronization 265

6.5 Mutex Locks 270

6.6 Semaphores 272

6.7 Monitors 276

6.8 Liveness 283

6.9 Evaluation 284

6.10 Summary 286

Practice Exercises 287

Further Reading 288

Chapter 7 Synchronization Examples

7.1 Classic Problems of Synchronization 289

7.2 Synchronization within the Kernel 295

7.3 POSIX Synchronization 299

7.4 Synchronization in Java 303

7.5 Alternative Approaches 311

7.6 Summary 314

Practice Exercises 314

Further Reading 315

Chapter 8 Deadlocks

8.1 System Model 318

8.2 Deadlock in Multithreaded Applications 319

8.3 Deadlock Characterization 321

8.4 Methods for Handling Deadlocks 326

8.5 Deadlock Prevention 327

8.6 Deadlock Avoidance 330

8.7 Deadlock Detection 337

8.8 Recovery from Deadlock 341

8.9 Summary 343

Practice Exercises 344

Further Reading 346

PART FOUR MEMORY MANAGEMENT

Chapter 9 Main Memory

9.1 Background 349

9.2 Contiguous Memory Allocation 356

9.3 Paging 360

9.4 Structure of the Page Table 371

9.5 Swapping 376

9.6 Example: Intel 32- and 64-bit Architectures 379

9.7 Example: ARMv8 Architecture 383

9.8 Summary 384

Practice Exercises 385

Further Reading 387

Chapter 10 Virtual Memory

10.1 Background 389

10.2 Demand Paging 392

10.3 Copy-on-Write 399

10.4 Page Replacement 401

10.5 Allocation of Frames 413

10.6 Thrashing 419

10.7 Memory Compression 425

10.8 Allocating Kernel Memory 426

10.9 Other Considerations 430

10.10 Operating-System Examples 436

10.11 Summary 440

Practice Exercises 441

Further Reading 444

PART FIVE STORAGE MANAGEMENT

Chapter 11 Mass-Storage Structure

11.1 Overview of Mass-Storage Structure 449

11.2 HDD Scheduling 457

11.3 NVM Scheduling 461

11.4 Error Detection and Correction 462

11.5 Storage Device Management 463

11.6 Swap-Space Management 467

11.7 Storage Attachment 469

11.8 RAID Structure 473

11.9 Summary 485

Practice Exercises 486

Further Reading 487

Chapter 12 I/O Systems

12.1 Overview 489

12.2 I/O Hardware 490

12.3 Application I/O Interface 500

12.4 Kernel I/O Subsystem 508

12.5 Transforming I/O Requests to Hardware Operations 516

12.6 STREAMS 519

12.7 Performance 521

12.8 Summary 524

Practice Exercises 525

Further Reading 526

PART SIX FILE SYSTEM

Chapter 13 File-System Interface

13.1 File Concept 529

13.2 Access Methods 539

13.3 Directory Structure 541

13.4 Protection 550

13.5 Memory-Mapped Files 555

13.6 Summary 560

Practice Exercises 560

Further Reading 561

Chapter 14 File-System Implementation

14.1 File-System Structure 564

14.2 File-System Operations 566

14.3 Directory Implementation 568

14.4 Allocation Methods 570

14.5 Free-Space Management 578

14.6 Efficiency and Performance 582

14.7 Recovery 586

14.8 Example: TheWAFL File System 589

14.9 Summary 593

Practice Exercises 594

Further Reading 594

Chapter 15 File-System Internals

15.1 File Systems 597

15.2 File-System Mounting 598

15.3 Partitions and Mounting 601

15.4 File Sharing 602

15.5 Virtual File Systems 603

15.6 Remote File Systems 605

15.7 Consistency Semantics 608

15.8 NFS 610

15.9 Summary 615

Practice Exercises 616

Further Reading 617

PART SEVEN SECURITY AND PROTECTION

Chapter 16 Security

16.1 The Security Problem 621

16.2 Program Threats 625

16.3 System and Network Threats 634

16.4 Cryptography as a Security Tool 637

16.5 User Authentication 648

16.6 Implementing Security Defenses 653

16.7 An Example:Windows 10 662

16.8 Summary 664

Further Reading 665

Chapter 17 Protection

17.1 Goals of Protection 667

17.2 Principles of Protection 668

17.3 Protection Rings 669

17.4 Domain of Protection 671

17.5 Access Matrix 675

17.6 Implementation of the Access Matrix 679

17.7 Revocation of Access Rights 682

17.8 Role-Based Access Control 683

17.9 Mandatory Access Control (MAC) 684

17.10 Capability-Based Systems 685

17.11 Other Protection Improvement Methods 687

17.12 Language-Based Protection 690

17.13 Summary 696

Further Reading 697

PART EIGHT ADVANCED TOPICS

Chapter 18 Virtual Machines

18.1 Overview 701

18.2 History 703

18.3 Benefits and Features 704

18.4 Building Blocks 707

18.5 Types of VMs and Their Implementations 713

18.6 Virtualization and Operating-System Components 719

18.7 Examples 726

18.8 Virtualization Research 728

18.9 Summary 729

Further Reading 730

Chapter 19 Networks and Distributed Systems

19.1 Advantages of Distributed Systems 733

19.2 Network Structure 735

19.3 Communication Structure 738

19.4 Network and Distributed Operating Systems 749

19.5 Design Issues in Distributed Systems 753

19.6 Distributed File Systems 757

19.7 DFS Naming and Transparency 761

19.8 Remote File Access 764

19.9 Final Thoughts on Distributed File Systems 767

19.10 Summary 768

Practice Exercises 769

Further Reading 770

PART NINE CASE STUDIES

Chapter 20 The Linux System

20.1 Linux History 775

20.2 Design Principles 780

20.3 Kernel Modules 783

20.4 Process Management 786

20.5 Scheduling 790

20.6 Memory Management 795

20.7 File Systems 803

20.8 Input and Output 810

20.9 Interprocess Communication 812

20.10 Network Structure 813

20.11 Security 816

20.12 Summary 818

Practice Exercises 819

Further Reading 819

Chapter 21 Windows 10

21.1 History 821

21.2 Design Principles 826

21.3 System Components 838

21.4 Terminal Services and Fast User Switching 874

21.5 File System 875

21.6 Networking 880

21.7 Programmer Interface 884

21.8 Summary 895

Practice Exercises 896

Further Reading 897

PART TEN APPENDICES

Chapter A Influential Operating Systems

A.1 Feature Migration 1

A.2 Early Systems 2

A.3 Atlas 9

A.4 XDS-940 10

A.5 THE 11

A.6 RC 4000 11

A.7 CTSS 12

A.8 MULTICS 13

A.9 IBM OS/360 13

A.10 TOPS-20 15

A.11 CP/M and MS/DOS 15

A.12 Macintosh Operating System and Windows 16

A.13 Mach 16

A.14 Capability-based Systems—Hydra and CAP 18

A.15 Other Systems 20

Further Reading 21

Chapter B Windows 7

B.1 History 1

B.2 Design Principles 3

B.3 System Components 10

B.4 Terminal Services and Fast User Switching 34

B.5 File System 35

B.6 Networking 41

B.7 Programmer Interface 46

B.8 Summary 55

Practice Exercises 55

Further Reading 56

Chapter C BSD UNIX

C.1 UNIX History 1

C.2 Design Principles 6

C.3 Programmer Interface 8

C.4 User Interface 15

C.5 Process Management 18

C.6 Memory Management 22

C.7 File System 25

C.8 I/O System 33

C.9 Interprocess Communication 36

C.10 Summary 41

Further Reading 42

Chapter D TheMach System

D.1 History of the Mach System 1

D.2 Design Principles 3

D.3 System Components 4

D.4 Process Management 7

D.5 Interprocess Communication 13

D.6 Memory Management 18

D.7 Programmer Interface 23

D.8 Summary 24

Further Reading 25

Credits 899

Index 901