}P
`
` ao oF
`
`aaRRaeBaeaieataIaAaarNi
`
`
`Ha
`
`ad
`
`PS
`
`aNny
`GALVIN
`
`Docker EX 1009
`
`Page | of 32
`
`OPERATING SYSTEM
`
`ooss
`
`
`
`
`
`pr,
`
`ak
`“7
`
`A
`
`* =
`
`a
`
`eee
`
`ees
`
`Fd
`i
`
`f
`
`‘bVs
`
`<a
`
`_—
`oe “f
`4
`
`Pama
`
`mt AT
`
`Q A
`
`Docker EX1009
`Page 1 of 32
`
`

`

`
`
`Docker EX1009
`Page 2 of 32
`
`

`

`Page 3 of 32
`
`Docker EX1009
`Page 3 of 32
`
`

`

`FOURTH EDITION
`
`OPERATING
`SYSTEM
`CONCEPTS
`
`Abraham. Silberschatz
`University of Texas
`
`Peter B. Galvin
`Brown University
`
`-r"T Addison-Wesley Publishing Company
`Reading, Massachusetts • Menlo Park, California • New York
`Don Mills, Ontario • W okingham, England • Amsterdam • Bonn
`Sydney • Singapore • Tokyo • Madrid • San Juan • Milan • Paris
`
`Docker EX1009
`Page 4 of 32
`
`

`

`Sponsoring Editor: Deborah Lafferty
`Senior Editor: Tom Stone
`Senior Production Supervisor: Helen Wythe
`Marketing Manager: Phyllis Cerys
`Technical Art Coordinator: Susan London-Payne
`Cover and Endpaper Designer: HowardS. Friedman
`Manufacturing Manager: Roy Logan
`
`Many of the designations used by manufacturers and sellers to distinguish
`their products are claimed as trademarks. Where those designations appear in
`this book, and Addison-Wesley was aware of a trademark claim, the designa(cid:173)
`tions have been printed in initial caps or all caps.
`
`The procedures and applications presented in this book have been included
`for their instructional value. They have been tested with care but are not guar(cid:173)
`anteed for any particular purpose. The publisher does not offer any warranties
`or representations, nor does it accept any liabilities with respect to the pro(cid:173)
`grams or applications.
`
`Library of Congress Cataloging-in-Publication Data
`
`Silberschatz, Abraham.
`Operating system concepts I Abraham Silberschatz, Peter B. Galvin.
`p.
`em.
`Includes bibliographical references and index.
`ISBN 0-201-50480-4
`1. Operating systems (Computers)
`QA76.76.063S5583 1994
`005.4'3--dc20
`
`I. Galvin, Peter B.
`
`II. Title.
`
`93-24415
`CIP
`
`Reprinted with corrections January, 1995
`
`Reproduced by Addison-Wesley from camera-ready copy supplied by the
`authors.
`
`Copyright© 1994 by Addison-Wesley Publishing Company, Inc.
`
`All rights reserved. No part of this publication may be reproduced, stored in a
`retrieval system, or transmitted, in any form or by any means, electronic,
`mech~n~cal, photocopying, recording, or otherwise, without the prior written
`permiSSion of the publisher. Printed in the United States of America.
`
`ISBN 0-201-50480-4
`8 9 1 0-MA-99 98 97 96
`
`Docker EX1009
`Page 5 of 32
`
`

`

`To my parents, Wira and Mietek,
`my wife, Haya,
`and my children, Lemor, Sivan and Aaron.
`
`Avi Silberschatz
`
`To Carla and Gwendolyn.
`
`Peter Galvin
`
`Docker EX1009
`Page 6 of 32
`
`

`

`CONTENTS
`
`PARTONE
`
`• OVERVIEW
`
`Introduction
`Chapter 1
`1.1 What Is an Operating System?
`1.2 Early Systems 6
`1.3 Simple Batch Systems 7
`1.4 Multiprogrammed Batched
`Sys}erns 13
`1.5 Time-Sharing Systems 15
`1.6 Personal-Computer Systems
`
`17
`
`3
`
`1.7
`1.8
`1.9
`1.10
`
`Parallel Systems 20
`Distributed Systems
`Real-Time Systems
`Summary 25
`Exercises 26
`Bibliographic Notes
`
`22
`23
`
`27
`
`Chapter 2 Computer-System Structures
`2.6 General-System Architecture
`2.1 Computer-System Operation 29
`2.2 I I 0 Structure 32
`2.7 Summary 52
`2.3 Storage Structure 37
`Exercises 53
`2.4 Storage Hierarchy 42
`Bibliographic Notes 55
`2.5 Hardware Protection 45
`
`51
`
`Chapter 3 Operating-System Structures
`3.1 System Components 57
`3.2 Operating-System Services 63
`3.3 System Calls 65
`
`3.4 System Programs 74
`3.5 System Structure 76
`3.6 Virtual Machines 82
`
`xi
`
`Docker EX1009
`Page 7 of 32
`
`

`

`xii Contents
`
`3.7 System Design and
`Implementation 86
`3.8 System Generation 89
`
`3.9 Summary 90
`Exercises 91
`Bibliographic Notes 92
`
`PART TWO
`
`•
`
`PROCESS MANAGEMENT
`
`Chapter 4 Processes
`
`4.1 Process Concept 97
`4.2 Process Scheduling 100
`4.3 Operation on Processes 105
`4.4 Cooperating Processes 108
`4.5 Threads 111
`
`4.6 Interprocess Communication
`4.7 Summary 126
`Exercises 127
`Bibliographic Notes 129
`
`116
`
`Chapter 5 CPU Scheduling
`
`5.1 Basic Concepts 131
`5.2 Scheduling Criteria 135
`5.3 Scheduling Algorithms 137
`5.4 Multiple-Processor Scheduling 149
`5.5 Real-Time Scheduling 150
`
`5.6 Algorithm Evaluation 152
`5.7 Summary 158
`Exercises 159
`Bibliographic Notes 161
`
`Chapter 6 Process Synchronization
`6.1 Background 163
`6.2 The Critical-Section Problem
`6.3 Synchronization Hardware
`6.4 Semaphores 175
`6.5 Classical Problems of
`Synchronization 181
`6.6 Critical Regions 186
`
`6.7
`6:8
`6.9
`6.10
`
`165
`172
`
`Monitors 190
`Synchronization in Solaris 2 198
`Atomic Transactions 199
`Summary 208
`Exercises 210
`Bibliographic Notes 214
`
`Chapter 7 Deadlocks
`
`7.1 System Mode] 217
`7.2 Deadlock Characterization 219
`7.3 Methods for Handling
`Deadlocks 223
`
`7.4 Deadlock Prevention 224
`7.5 Deadlock A voidance 227
`7.6 Deadlock Detection 234
`7.7 Recovery from Deadlock 238
`\
`
`Docker EX1009
`Page 8 of 32
`
`

`

`7.8 Combined Approach to
`Deadlock Handling 240
`7.9 Summary 241
`
`Contents
`
`xiii
`
`Bibliographic Notes 245
`Exercises 242
`
`PART THREE
`
`•
`
`STORAGE MANAGEMENT
`
`Chapter 8 Memory Management
`
`8.1 Background 249
`8.2 Logical versus Physical
`Address Space 255
`8.3 Swapping 256
`8.4 Contiguous Allocation 259
`8.5 Paging 267
`
`8.6 Segmentation 283
`8.7 Segmentation with Paging 290
`8.8 Summary 294
`Exercises 296
`Bibliographic Notes 299
`
`Chapter 9 Virtual Memory
`
`9.1 Background 301
`9.2 Demand Paging 303
`9.3 Performance of Demand Paging 309
`9.4 Page Replacement 312
`9.5 Page-Replacement Algorithms 315
`9.6 Allocation of Frames 326
`
`9.7 Thrashing 329
`9.8 Other Considerations 334
`9.9 Demand Segmentation 341
`9.10 Summary 342
`Exercises 343
`Bibliographic Notes 348
`
`Chapter 10 File-System Interface
`
`10.1 File Concept 349
`10.2 Access Methods 358
`10.3 Directory Structure 361
`10.4 Protection 373
`
`10.5 Consistency Semantics 378
`10.6 Summary 379
`Exercises 380
`Bibliographic Notes 381
`
`Chapter 11 File-System Implementation
`
`11.1 File-System Structure 383
`11.2 Allocation Methods 387
`11.3 Free-Space Management 397
`11.4 Directory Implementation 399
`11.5 Efficiency and Performance 401
`
`11.6 Recovery 403
`11.7 Summary 405
`Exercises 406
`Bibliographic Notes 408
`
`Docker EX1009
`Page 9 of 32
`
`

`

`xiv Contents
`
`Chapter 12 Secondary-Storage Structure
`
`12.1 Disk Structure 409
`12.2 Disk Scheduling 410
`12.3 Disk Management 417
`12.4 Swap-Space Management 419
`12.5 Disk Reliability 422
`
`12.6 Stable-Storage
`Implementation 424
`12.7 Summary 425
`Exercises 426
`Bibliographic Notes 427
`
`PART FOUR
`
`•
`
`PROTECTION AND SECURITY
`
`Chapter 13 Protection
`
`13.1 Goals of Protection 431
`13.2 Domain of Protection 432
`13.3 Access Matrix 438
`13.4 Implementation of Access
`Matrix 443
`13.5 Revocation of Access Rights 446
`
`13.6 Capability-Based Systems 448
`13.7 Language-Based Protection 451
`13.8 Summary 455
`Exercises 455
`Bibliographic Notes 457
`
`Chapter 14 Security
`
`14.1 The Security Problem 459
`14.2 Authentication 461
`14.3 Program Threats 464
`14.4 System Threats 465
`14.5 Threat Monitoring 469
`
`14.6 Encryption 471
`14.7 Summary 473
`Exercises 473
`Bibliographic Notes 474
`
`PART FIVE
`
`• DISTRIBUTED SYSTEMS
`
`Chapter 15 Network Structures
`
`15.1 Background 479
`15.2 Motivation 481
`15.3 Topology 482
`15.4 Network Types 488
`15.5 Communication 491
`
`15.6 Design Strategies 498
`15.7 Networking Example 501
`15.8 Summary 504
`Exercises 504
`Bibliographic Notes 505
`
`Docker EX1009
`Page 10 of 32
`
`

`

`Contents
`
`xv
`
`Chapter 16· Distributed-System Structures
`
`16.1 Network-Operating Systems 507
`16.2 Distributed-Operating Systems 509
`16.3 Remote Services 512
`16.4 Robustness 517
`
`16.5 Design Issues 519
`16.6 Summary 521
`Exercises 522
`Bibliographic Notes 523
`
`Chapter 17 Distributed-File Systems
`
`17.1 Background 525
`17.2 Naming and Transparency 527
`17.3 Remote File Access 531
`17.4 Stateful versus Stateless Service 536
`17.5 File Replication 538
`
`17.6 Example Systems 539
`17.7 Summary 567
`Exercises 568
`Bibliographic Notes 569
`
`Chapter 18 Distributed Coordination
`
`18.1 Event Ordering 571
`18.2 Mutual Exclusion 574
`18.3 Atomicity 577
`18.4 Concurrency Control 581
`18.5 Deadlock Handling 586
`
`18.6 Election Algorithms 595
`18.7 Reaching Agreement 598
`18.8 Summary 600
`Exercises 601
`Bibliographic Notes 602
`
`PART SIX
`
`• CASE STUDIES
`
`Chapter 19 The UNIX System
`19.1 History 607
`19.2 Design Principles 613
`19.3 Programmer Interface 615
`19.4 User Interface 623
`19.5 Process Management 627
`19.6 Memory Management 632
`
`19.7 File System 636
`19.8 I/0 System 645
`19.9 Interprocess Communication 649
`19.10 Summary 655
`Exercises 655
`Bibliographic Notes 657
`
`Chapter 20 The Mach System
`20.1 History 659
`20.2 Design Principles 661
`20.3 System Components 662
`20.4 Process Management 666
`20.5 Interprocess Communication 673
`
`20.6 Memory Management 679
`20.7 Programmer Interface 685
`20.8 Summary 686
`Exercises 687
`Bibliographic Notes 688
`
`Docker EX1009
`Page 11 of 32
`
`

`

`xvi Contents
`
`Chapter 21 Historical Perspective
`
`21.1 Atlas 691
`21.2 XDS-940 692
`21.3 THE 693
`21.4 RC 4000 694
`
`21.5 CTSS 695
`21.6 MULTICS 696
`21.7 OS I 360 696
`21.8 Other Systems 698
`
`A.S Conclusions 713
`Bibliographic Notes 713
`
`Appendix The Nachos System
`
`A.1 Overview 700
`A.2 Nachos Software Structure 702
`A.3 Sample Assignments 705
`A.4 Information on Obtaining a
`Copy of Nachos 711
`
`Bibliography 715
`
`Credits 745
`
`Index 747
`
`Docker EX1009
`Page 12 of 32
`
`

`

`42 • Chapter 2: Computer-System Structures
`
`their performance is increasing. Because they are more rugged, they, like
`floppy disks, have the added advantage of removability.
`
`2.3.4 Magnetic Tapes
`Magnetic tape was used as an early secondary-storage media. Although it
`is relatively permanent, and can hold large numbers of data, magnetic tape
`is quite slow in comparison to the access time of main memory. Even
`more important, magnetic tape is limited to sequential access. Thus, it is
`unsuitable for providing the random access needed for most secondary(cid:173)
`storage requirements. Tapes are used mainly for backup, for storage of
`transferring
`information, and as a medium for
`infrequently used
`information from one system to another.
`A tape is kept in a spool, and is wound or rewound past a read-write
`head. Moving to the correct spot on a tape can take minutes rather than
`milliseconds; once positioned, however, tape drives can write data at
`densities and speeds approaching those of disk drives. Capacities vary
`depending on -r-the length and width of the tape, and on the density at
`which the head can read and write. A tape drive is usually named by its
`width. Thus, there are 8-millimeter, 114-inch, and 1/2-inch. (also known as
`9-track) tape drives. The 8-millimeter tape drives have the highest density,
`due to the technology they use; they currently store 5 gigabytes of data (a
`gigabyte is one billion bytes) on a 350-foot tape.
`
`2.4 • Storage Hierarchy
`
`The wide variety of storage systems in a computer system can be
`organized in a hierarchy (Figure 2.6) according to their speed and their
`cost. The higher levels are expensive, but are fast. As we move down the
`hierarchy, the cost per bit decreases, whereas the access time increases.
`This tradeoff is reasonable; if a given storage system were both faster and
`less expensive than another -
`other properties being the same -
`then
`there would be no reason to use the slower, more expensive memory. In
`fact, many early storage devices, including paper tape and core memories,
`are relegated to museums now that magnetic tape and semiconductor
`memory have become faster and cheaper.
`In addition to the speed and cost of the various storage systems, there
`is also the issue of storage volatility. 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 2.6, the storage
`system above disks is volatile, whereas the storage system below main
`memory is nonvolatile. The design of a complete memory system attempts
`to balance all these factors: It uses only as much expensive memory as
`
`Docker EX1009
`Page 13 of 32
`
`

`

`2.4
`
`43
`
`Figure 2.6 Storage-device hierarchy.
`
`necessary, while providing as much inexpensive, nonvolatile,
`possible. Caches can be installed to ameliorate
`where there is a large
`or transfer-rate
`components.
`
`2.4.1 Caching
`Caching
`of computer
`an important
`normally
`in some
`and software. Information
`it
`copied into a faster
`as main memory). As it
`When we need a
`the cache, on a temporary
`information, we first check whether it is in the cache.
`if it is not, we use
`information directly from the
`from the main storage system, putting a copy in
`assumption that there is a high probability that it will be
`Extending this view, internal programmable registers,
`and accumulators, are a high-speed cache for
`
`Docker EX1009
`Page 14 of 32
`
`

`

`44 • Chapter 2: Computer-System Structures
`
`programmer (or compiler) implements the register-allocation and register(cid:173)
`replacement algorithms to decide which information to keep in registers
`and which to keep in main memory. There are also caches that are
`implemented totally in hardware. For instance, most systems have an
`instruction cache to hold the next instructions expected to be executed.
`Without this cache, the CPU would have to wait several cycles while an
`instruction was fetched from main memory. We are not concerned with
`these hardware-only caches in this text, since they are outside of the
`control of the operating system.
`Since caches have limited size, cache management is an important design
`problem. Careful selection of the cache size and of a replacement policy
`can result in 80 to 99 percent of all accesses being in the cache, resulting in
`extremely high performance. Various
`replacement algorithms
`for
`software-controlled caches are discussed in Chapter 9.
`Main memory can be viewed as a fast cache for secondary memory,
`since data on secondary storage must be copied into main memory for use,
`and data must be in main memory before being moved to secondary
`storage for safekeeping. The file system itself, which must reside on
`nonvolatile storage, may have several levels of storage. At the highest
`level, ·we have the electronic (or RAM) disk storage, which is backed up by
`the larger, but slower, magnetic-disk storage. The magnetic-disk storage,
`in turn, is backed up by the larger, but slower, tape storage. Optical disks
`are also efficient high-capacity but low-cost storage media. When
`compared to magnetic tape, they have the drawback of higher cost, but
`offer much greater speed and convenience. Transfers between these two
`storage levels are generally requested explicitly, but some systems now
`automatically archive a file that has not been used for a long time (for
`example, 1 month), and then automatically fetch back the file to disk when
`it is next referenced.
`The movement of information between levels of a storage hierarchy
`may be either explicit or implicit, depending on the hardware design and
`the controlling operating-system software. For instance, data transfer from
`cache to CPU and registers is usually a hardware function, with no
`operating-system intervention. On the other hand, transfer of data from
`disk to memory is usually controlled by the operating system.
`
`2.4.2 Coherency and Consistency
`In a hierarchical storage structure, the same datum may appear in different
`storage systems. For example, consider an integer A located in file B that
`is to be incremented by 1. Suppose that file B resides on magnetic disk.
`The increment operation proceeds by first issuing an 110 operation to copy
`the disk block on which A resides to main memory. This operation is
`followed by a possible copying of A to the cache, and by copying A to an
`internal register. Thus, the copy of A appears in several places. Once the
`
`Docker EX1009
`Page 15 of 32
`
`

`

`9.5 Page-Replacement Algorithms • 315
`
`pages cannot be modified; thus, they may be discarded when desired.
`This scheme can reduce significantly the time to service a page fault, since
`it reduces 110 time by one-half if the page is not modified.
`the
`Page replacement is basic
`to demand paging. It completes
`separation between logical memory and physical memory. With this
`mechanism, a very large virtual memory can be provided for programmers
`on a smaller physical memory. With non-demand paging, user addresses
`were mapped into physical addresses, allowing the two sets of addresses
`to be quite different. All of the pages of a process still must be in physical
`memory, however. With demand paging, the size of the logical address
`space is no longer constrained by physical memory. If we have a user
`process of 20 pages, we can execute it in 10 frames simply by using
`demand paging, and using a replacement algorithm to find a free frame
`whenever necessary. If a page that has been modified is to be replaced, its
`contents are copied to the disk. A later reference to that page will cause a
`page fault. At that time, the page will be brought back into memory,
`perhaps replacing some other page in the process.
`We must solve two major problems to implement demand paging: We
`must develop a frame-allocation algorithm and a page-replacement algorithm. If
`we have multiple processes in memory, we must decide how many frames
`to allocate to each process. Further, when page replacement is required,
`we must select the frames that are to be replaced. Designing appropriate
`algorithms to solve these problems is an important task, because disk 110 is
`so expensive. Even slight improvements in demand-paging methods yield
`large gains in system performance.
`
`9.5 • Page-Replacement Algorithms
`
`There are many different page-replacement algorithms. Probably every
`operating system has its own unique replacement scheme. How do we
`select a particular replacement algorithm? In general, we want the one
`with the lowest page-fault rate.
`We evaluate an algorithm by running it on a particular string of
`memory references and computing the number of page faults. The string of
`memory references is called a reference string. We can generate reference
`strings artificially (by a random-number generator, for example) or by
`tracing a given system and recording the address of each memory
`reference. The latter choice produces a large number of data (on the order
`of 1 million addresses per second). To reduce the number of data, we note
`two things.
`First, for a given page size (and the page size is generally fixed by the
`hardware or system), we need to consider only the page number, not the
`entire address. Second, if we have a reference to a page p, then any
`
`Docker EX1009
`Page 16 of 32
`
`

`

`316 • Chapter 9: Virtual Memory
`
`immediately following references to page p will never cause a page fault.
`Page p will be in memory after the first reference; the immediately
`following references will not fault.
`.
`For example, if we trace a particular process, we might record the
`following address sequence:
`
`0100, 0432, 0101, 0612, 0102, 0103, 0104, 0101, 0611, 0102, 0103,
`0104, 0101, 0610, 0102, 0103, 0104, 0101, 0609, 0102, 0105,
`
`which, at 100 bytes per page, is reduced to the following reference string
`
`1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1.
`
`To determine the number of page faults for a particular reference string
`and page-replacement algorithm, we also need to know the number of
`page frames available. Obviously, as the number of frames available
`increases, the number of page faults will decrease. For the reference string
`considered previously, for example, if we had three or more frames, we
`would have only three faults, one fault for the first reference to each page.
`On the other hand, with only one frame available, we would have- a
`replacement with every reference, resulting in 11 faults. In general, we
`expect a curve such as that in Figure 9. 7. As the number of frames
`increases, the number of page faults drops to some minimal level. Of
`course, adding physical memory increases the number of frames.
`
`$
`'"5
`
`Ol
`
`ctl -Q)
`ctl a. -0
`
`....
`Q)
`.0
`E
`:::1 c
`
`16
`
`14
`
`12
`
`10
`
`8
`
`6
`
`4
`
`2
`
`\
`'
`\
`
`'
`
`~
`~
`
`-i'---.
`
`, .
`
`1
`
`2
`
`3
`
`4
`number of frames
`
`5
`
`6
`
`Figure 9.7 Graph of page faults versus the number of frames.
`
`Docker EX1009
`Page 17 of 32
`
`

`

`9.5 Page-Replacement Algorithms • 317
`
`illustrate the page-replacement algorithms, we shall use the
`To
`reference string
`
`7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
`
`for a memory with three frames.
`
`9.5.1 FIFO Algorithm
`The simplest page-replacement algorithm is a FIFO algorithm.· A FIFO
`replacement algorithm associates with each page the time when that page
`was brought into memory. When a page must be replaced, the oldest page
`is chosen. Notice that it is not strictly necessary to record the time when a
`page is brought in. We can create a FIFO queue to hold all pages in
`memory. We replace the page at the head of the queue. When a page is
`brought into memory, we insert it at the tail of the queue.
`For our example reference string, our three frames are initially empty.
`The first three references (7, 0, 1) cause page faults, and are brought into
`these empty frames. The next reference (2) replaces page 7, because page 7
`was brought in first. Since 0 is the next reference and 0 is already in
`memory, we have no fault for this reference. The first reference to 3 results
`in page 0 being replaced, since it was the first of the three pages in
`memory (0, 1, and 2) to be brought in. This replacement means that the
`next reference, to 0, will fault. Page 1 is then replaced by page 0. This
`process continues as shown in Figure 9.8. Every time a fault occurs, we
`show which pages are in our three frames. There are 15 faults altogether.
`The FIFO page-replacement algorithm is easy to understand and
`program. However, its performance is not always good. The page replaced
`may be an initialization module that was used a long time ago and is no
`longer needed. On the other hand, it could contain a heavily used variable
`that was initialized early and is in constant use.
`
`reference string
`
`7
`
`0
`
`1
`
`2
`
`0
`
`3
`
`0
`
`4
`
`2
`
`3
`
`0
`
`3
`
`2
`
`2
`
`0
`
`1
`
`7
`
`0
`
`page frames
`
`Figure 9.8 FIFO page-replacement algorithm.
`
`Docker EX1009
`Page 18 of 32
`
`

`

`318 • Chapter 9: Virtual Memory
`
`Notice that, even if we select for replacement a page that is in active
`use, everything still works correctly. After we page out an active page to
`bring in a new one, a fault occurs almost immediately to retrieve the active
`page. Some other page will need to be replaced to bring the active page
`back into memory. Thus, a bad replacement choice increases the page-fault
`rate and slows process execution, but does not cause incorrect execution.
`the problems
`that are possible with a FIFO page(cid:173)
`To
`illustrate
`replacement algorithm, we consider the reference string
`
`1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.
`
`Figure 9. 9 shows the curve of page faults versus the number of available
`frames. We notice that the number of faults for four frames (10) is greater
`than the number of faults for three frames (nine)! This result is most
`unexpected and is known as Be lady's anomaly. Belady' s anomaly reflects the
`fact that, for some page-replacement algorithms, the page-fault rate may
`increase as the number of allocated frames increases. We would expect that
`giving more memory to a process would improve its performance. In some
`early research, investigators noticed that this assumption was not always
`true. Belady's anomaly was discovered as a result.
`
`9 .5.2 Optimal Algorithm
`One result of the discovery of Belady' s anomaly was the search for an
`optimal page-replacement algorithm. An optimal page-replacement
`algorithm has the lowest page-fault rate of all algorithms. An optimal
`
`O'l
`
`2
`"5
`
`a:s -Q)
`a:s a.
`... Q)
`0
`.c
`E
`:::1
`c::
`
`16
`
`14
`
`12
`
`10
`
`8
`
`6
`
`4
`
`2
`
`"' ~ ~ ~ "
`
`1
`
`2
`
`3
`number of frames
`
`4
`
`5
`
`6
`
`7
`
`Figure 9.9 Page-fault curve for FIFO r~placement on a reference string.
`
`Docker EX1009
`Page 19 of 32
`
`

`

`9.5 Page-Replacement Algorithms • 319
`
`algorithm will· never suffer from Be lady's anomaly. An optimal page(cid:173)
`replacement algorithm exists, and has been called OPT or MIN. It is simply
`
`Replace the page that will not be used
`for the longest period of time.
`
`Use of this page-replacement algorithm guarantees the lowest possible
`page-fault rate for a fixed number of frames.
`For example, on our sample reference string, the optimal page(cid:173)
`replacement algorithm would yield nine page faults, as shown in Figure
`9.10. The first three references cause faults that fill the three empty frames.
`The reference to page 2 replaces page 7,· because 7 will not be used until
`reference 18, whereas page 0 will be used at 5, and page 1 at· 14. The
`reference to page 3 replaces page 1, as page 1 will be the last of the three
`pages in memory to be referenced again. With only nine page faults,
`optimal replacement is' much better than a FIFO algorithm, which had 15
`faults. (If we ignore the first three, which all algorithms must suffer, then
`optimal replacement is twice as good as FIFO replacement.) In fact, no
`replacement algorithm can process this reference string in three frames
`with less than nine faults.
`Unfortunately, the optimal page-replacement algorithm is difficult to
`implement, because it requires future knowledge of the reference string.
`(We encountered a similar situation with the SJF CPU-scheduling algorithm
`in Section 5.3.~.) As a result, the optimal algorithm is used mainly for
`comparison studies. For instance, it may be quite useful to know that,
`although a new algorithm is not optimal, it is within 12.3 percent of
`optimal at worst and within 4.7 percent on average.
`
`9.5.3 LRU Algorithm
`If the optimal algorithm is not feasible, perhaps an approximation to the
`optimal algorithm is possible. The key distinction between the FIFO and OPT
`algorithms (other than looking backward or forward in time) is that the
`
`0
`
`3
`
`0
`
`4
`
`2
`
`3
`
`0
`
`3
`
`2
`
`2
`
`0
`
`1
`
`7
`
`0
`
`1
`
`reference string
`2
`7
`0
`
`page frames
`
`Figure 9.10 Optimal page-replacement algorithm.
`
`Docker EX1009
`Page 20 of 32
`
`

`

`320 • Chapter 9: Virtual Memory
`
`0
`
`3
`
`0
`
`4
`
`2
`
`3
`
`0
`
`3
`
`2
`
`1
`
`2
`
`0
`
`1
`
`7
`
`0
`
`1
`
`reference string
`7
`0
`1
`2
`
`page frames
`
`Figure 9.11 LRU page-replacement algorithm.
`
`FIFO algorithm uses the time when a page was brought into memory; the
`OPT algorithm uses the time when a page is to be used. If we use the recent
`past as an approximation of the near future, then we will replace the page
`that has not been used for the longest period of time (Figure 9.11). This
`approach is the least recently used (LRU) algorithm.
`LRU replacement associates with each page the time of that page's last
`use. When a page must be replaced, LRU chooses that page that has not
`been used for the longest period of time. This strategy is the optimal
`page-replacement algoritJ:tm
`looking backward
`in
`time,
`rathe! . than
`forward. (Strangely, if we let 5 R be the reverse of a reference string 5,
`then the page-fault rate for the OPT algorithm on 5 is the same as the
`page-fault rate for the OPT algorithm on S R . Similarly, the page-fault rate
`for ·the LRU algorithm on 5 is the same as the page-fault rate for the LRU
`algorithm on 5 R . )
`The result of applying LRU replacement to our example reference string
`is shown in Figure 9.11. The LRU algorithm produces 12 faults. Notice that
`the first five faults are the same as the optimal replacement. When the
`reference to page 4 occurs, however, LRU replacement sees that, of the
`three frames in memory, page 2 was used least recently. The most recently
`used page is page 0, and just before that page 3 was used. Thus, the LRU
`algorithm replaces page 2, not knowing that page 2 is about to be used.
`When it then faults for page 2, the LRU algorithm replaces page 3 since, of
`the thr~e pages in memory {0, 3, 4}, page 3 is the least recently used.
`·.Despite these problems, LRU replacement with 12 faults is still much better
`than FIFO replacement with 15.
`The LRU policy is often used as. a page-replacement algorithm and is
`considered to be quite good. The major problem is how to implement LRU
`replacement. An LRU page-replacement algorithm may require substantial
`hardware assistance. The problem is to determine an order for the frames
`defined by the time of last use. Two implementations are feasible:
`
`• Counters: In the simplest case, we associate with each page-table entry
`a time-of-use field, and add to the CPU a logical clock. or counter. The
`
`Docker EX1009
`Page 21 of 32
`
`

`

`9.5 Pa~e-Replacement Algorithms • 321
`
`incremented for every memory reference. Whenever a
`is
`clock
`reference to a page is made, the contents of the clock register are
`copied to the time-of-use field in the page table for that page. In this
`way, we always have the "time" of the last reference to each page. We
`replace the page with the smallest time value. This scheme requires a
`search of the page table to find the LRU page, and a write to memory
`(to the time-of-use field, in the page table) for each memory acce~s. The
`times must also be maintained when page tables are changed (due to
`CPU scheduling). Overflow of the clock must be considered.
`
`I
`
`• Stack: Another approach to implementing LRU replacement is to keep a
`stack of page numbers. Whenever a page is referenced, it is removed
`from the stack and put on the top. In this way, the top of the stack is
`always the most recently used page and the bottom is the LRU page
`(Figure 9.12). Because entries must be removed from the middle of the
`stack, it is best implemented by a doubly linked list, with a head and
`tail pointer. Removing a page and putting it on the top of the stack
`then requires changing six pointers at worst. Each update is a little
`more expensive, but there is no search· for a replacement; the tail
`pointer points to the bottom of the stack, which is the LRU page. This
`approach
`is particularly appropriate
`for software or microcode
`implementations of LRU replacement.
`
`Neither optimal replacement nor LRU replacement suffers from Belady's
`anomaly. There is a class of page-replacement algorithms, called stack
`algorithms, that can never exhibit Belady's anomaly. A stack algorithm is an
`algorithm for which it can be shown that the set of pages in memory for n
`
`reference string
`
`4
`
`7
`
`0
`
`7
`
`1
`
`0
`
`2
`
`1
`
`2
`
`7
`
`2
`
`7
`
`2 t a
`
`1
`
`t b
`
`stack
`before
`a
`
`stack
`after
`b
`
`Figure 9.12 Use of a stack to record the most recent page references.
`
`Docker EX1009
`Page 22 of 32
`
`

`

`322 • Chapter 9: Virtual Memory
`
`frames is always a subset of the set of pages that would be in memory with
`n + 1 frames. For LRU replacement, the set of pages in memory would be
`the n most recently referenced pages. If the number of frames is increased,
`these n pages will still be the most recently referenced and so will still be
`in memory.
`Note that neither implementation of LRU would be conceivable without
`hardware assistance beyond the standard TLB registers. The updating of
`the clock fields or stack must be done for every memory reference. If we
`were to use an interrupt for every reference, to allow software to update
`such data structures, it would slow every memory reference by a factor of
`at least 10, hence slowing every user process by a factor of 10. Few
`systems could tolerate that level of overhead for memory management.
`
`9.5.4 LRU Approximation Algorithms
`Few systems provide sufficient hardware support for true LRU page
`replacement. s·ome systems provide no hardware support, and other
`page-replacement algorithms (such as· a FIFO algorithm) must be used.
`Many systems provide some help, however, in the form of a reference bit.
`The reference bit for a page is set, by the hardware, whenever that page is
`referenced (either a read or a write to any pyte in the page). Reference bits
`are associated with each entry in the page table.
`·
`Initially, all bits are cleared (to 0) by the operating system. As a user
`process exeq.ttes, the bit associated with each page referenced is set (to 1)
`by the hardware. After some time, we can determine which pages have
`been used and which have not been used by examining the reference bits.
`We do not know the order of use, but we know which pages were us