[ll’ERATING SYSTEM
`CflNCEP’I‘S
`
`EMC méEEZEi
`
`a»!
`
`SILBEHSCHATZ
`GALVIN
`
`IV 2007
`EMC Corporation v. IV
`IPR2017-00439
`
`

`

`FOURTH EDITION
`
`OPERATING
`SYSTEM
`CONCEPTS
`
`Abraham Silberschatz
`University of Texas
`
`Peter B. Galvin
`Brown University
`
`VV Addison-Wesley Publishing Company
`Reading, Massachusetts . Menlo Park, California . New York
`Don Mills, Ontario . Wokingham, England . Amsterdam . Bonn
`Sydney . Singapore (cid:149) Tokyo . Madrid (cid:149) San Juan . Milan . Paris
`
`

`

`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: Howard S. 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-
`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-
`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-
`grams or applications.
`
`Library of Congress Cataloging-in-Publication Data
`
`Silberschatz, Abraham.
`Operating system concepts / Abraham Silberschatz, Peter B. Galvin.
`cm.
`p. (cid:9)
`Includes bibliographical references and index
`ISBN 0-201-50480-4
`1. Operating systems (Computers) I. Galvin, Peter B. II. Title.
`QA76.76.063S5583 1994
`005.4’3--dc20 (cid:9)
`
`93-24415
`CIP
`
`Reproduced by Addison-Wesley from camera-ready copy supplied by the
`authors.
`
`Reprinted with corrections June, 1994
`
`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,
`mechanical, photocopying, recording, or otherwise, without the prior written
`permission of the publisher. Printed in the United States of America.
`
`ISBN 0-201-50480-4
`345678910-MA-9594
`
`

`

`among
`users
`u wish
`licating
`
`dement
`
`1–(cid:151)as
`some
`)tlfy us
`;uggest
`ir from
`nent of
`
`i were
`ith the
`uckley,
`. Scott
`laynes,
`Vlichael
`nkovic,
`
`chnical
`Debbie
`uction.
`[1990].
`John
`4.3BSD.
`
`e book:
`Caleb
`Gary
`utanec,
`J. (cid:9) S.
`i (cid:9)
`
`A.S.
`P.B.G.
`
`CONTENTS
`
`PART ONE U OVERVIEW
`
`Introduction
`Chapter 1 (cid:9)
`1.1 What Is an Operating System? (cid:9)
`1.2 Early Systems (cid:9)
`6 (cid:9)
`7 (cid:9)
`1.3 Simple Batch Systems (cid:9)
`1.4 Multiprogrammed Batched (cid:9)
`Systems (cid:9)
`13
`15
`1.5 Time-Sharing Systems (cid:9)
`1.6 Personal-Computer Systems (cid:9)
`
`3 (cid:9)
`
`17
`
`20
`1.7 Parallel Systems (cid:9)
`1.8 Distributed Systems (cid:9)
`1.9 Real-Time Systems (cid:9)
`1.10 Summary 25
`Exercises (cid:9)
`26
`Bibliographic Notes (cid:9)
`
`22
`23
`
`27
`
`Chapter 2 (cid:9) Computer-System Structures
`2.6 General-System Architecture (cid:9)
`29 (cid:9)
`2.1 Computer-System Operation (cid:9)
`2.7 Summary 52
`2.2 I/O Structure (cid:9)
`32 (cid:9)
`Exercises (cid:9)
`53
`37
`2.3 Storage Structure (cid:9)
`Bibliographic Notes (cid:9)
`42
`2.4 Storage Hierarchy (cid:9)
`2.5 Hardware Protection (cid:9)
`
`55
`
`45
`
`Chapter 3 (cid:9) Operating-System Structures
`3.4 System Programs (cid:9)
`3.1 System Components (cid:9)
`57 (cid:9)
`3.5 System Structure (cid:9)
`3.2 Operating-System Services (cid:9)
`3.6 Virtual Machines (cid:9)
`3.3 System Calls (cid:9)
`65 (cid:9)
`
`63 (cid:9)
`
`74
`76
`82
`
`51
`
`Xi
`
`

`

`xii Contents
`
`3.7 System Design and (cid:9)
`Implementation 86 (cid:9)
`3.8 System Generation 89 (cid:9)
`
`3.9 Summary 90
`Exercises 91
`Bibliographic Notes 92
`
`PART TWO U PROCESS MANAGEMENT
`
`Chapter 4 Processes
`97
`4.1 Process Concept (cid:9)
`100
`4.2 Process Scheduling (cid:9)
`4.3 Operation on Processes
`4.4 Cooperating Processes
`111
`4.5 Threads (cid:9)
`
`105 (cid:9)
`108 (cid:9)
`
`4.6 Interprocess Communication 116
`4.7 Summary 126
`Exercises 127
`Bibliographic Notes 129
`
`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
`190
`6.1 Background 163
`6.7 Monitors (cid:9)
`6.2 The Critical-Section Problem
`68 Synchronization in Solaris 2 (cid:9)
`6.3 Synchronization Hardware
`6.9 Atomic Transactions (cid:9)
`199
`6.4 Semaphores 175
`6.10 Summary 208
`6.5 Classical Problems of
`Exercises (cid:9)
`210
`Synchronization 181
`Bibliographic Notes (cid:9)
`6.6 Critical Regions 186
`
`165 (cid:9)
`172 (cid:9)
`
`214
`
`198
`
`Chapter 7 Deadlocks
`7.1 System Model 217
`7.2 Deadlock Characterization 219
`7.3 Methods for Handling
`Deadlocks 223
`
`7.4 Deadlock Prevention 224
`7.5 Deadlock Avoidance 227
`7.6 Deadlock Detection 234
`7.7 Recovery from Deadlock 238
`
`

`

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

`

`xiv Contents
`
`Chapter 12 Secondary-Storage Structure
`12.6 Stable-Storage
`12.1 Disk Structure 409
`Implementation 424
`12.2 Disk Scheduling 410
`12.7 Summary 425
`12.3 Disk Management 417
`Exercises 426
`12.4 Swap-Space Management 419
`Bibliographic Notes 427
`12.5 Disk Reliability 422
`
`PART FOUR (cid:149) 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 U DISTRIBUTED SYSTEMS
`
`Chapter 15 Network Structures
`15.1 Background (cid:9)
`479
`15.2 Motivation (cid:9)
`481
`15.3 Topology (cid:9)
`482
`15.4 Network Types 488
`15.5 Communication (cid:9)
`491
`
`15.6 Design Strategies 498
`15.7 Networking Example 501
`15.8 Summary 504
`Exercises 504
`Bibliographic Notes 505
`
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`

`

`TY
`
`448
`451
`
`Contents xv
`
`Chapter 16 Distributed-System Structures
`16.5 Design Issues 519
`16.1 Network-Operating Systems 507 (cid:9)
`16.6 Summary 521
`16.2 Distributed-Operating Systems 509 (cid:9)
`16.3 Remote Services 512 (cid:9)
`Exercises 522
`Bibliographic Notes 523
`16.4 Robustness 517 (cid:9)
`
`Chapter 17 Distributed-File Systems
`17.6 Example Systems 539
`17.1 Background 525
`17.7 Summary 567
`17.2 Naming and Transparency 527
`Exercises 568
`17.3 Remote File Access 531
`17.4 Stateful versus Stateless Service 536 (cid:9)
`Bibliographic Notes 569
`17.5 File Replication 538
`
`Chapter 18 Distributed Coordination
`18.1 Event Ordering 571
`18.6 Election Algorithms 595
`18.7 Reaching Agreement 598
`18.2 Mutual Exclusion 574
`18.8 Summary 600
`18.3 Atomicity 577
`Exercises 601
`18.4 Concurrency Control 581
`Bibliographic Notes 602
`18.5 Deadlock Handling 586
`
`PART SIX (cid:149) 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/O 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 (cid:9)
`
`20.6 Memory Management 679
`20.7 Programmer Interface 685
`20.8 Summary 686
`Exercises 687
`Bibliographic Notes 688
`
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`

`

`xvi Contents
`
`Chapter 21 Historical Perspective
`21.1 Atlas 691
`21.5 CTSS 695
`21.2 XDS-940 692
`21.6 M1JLTICS 696
`21.3 THE 693
`21.7 OS/360 696
`21.8 Other Systems 698
`21.4 RC4000 694
`
`A.5 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
`
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`

`

`9.5 Page-Replacement Algorithms (cid:149) 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.
`Page replacement is basic to demand paging. It completes the
`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
`I/O is
`so expensive. Even slight improvements in demand-paging methods yield
`large gains in system performance.
`
`9.5 (cid:149) 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
`
`

`

`316 (cid:149) 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.
`
`16
`
`14
`
`Cl)
`
`12
`
`a)
`a 10
`ci
`
`a)
`E 6
`
`4
`
`2
`
`1 (cid:9)
`
`2 (cid:9)
`
`3 (cid:9)
`
`4 (cid:9)
`
`5 (cid:9)
`
`6
`
`number of frames
`
`Figure 9.7 Graph of page faults versus the number of frames.
`
`

`

`ault.
`tely
`
`the
`
`tring
`r of
`lable
`tring
`we
`)age.
`ye a
`we
`ames
`Of
`
`- (cid:9)
`
`9.5 (cid:9) Page-Replacement Algorithms (cid:149) 317
`
`illustrate (cid:9)
`To (cid:9)
`reference string
`
`the (cid:9) page-replacement algorithms, (cid:9) we (cid:9) shall use (cid:9)
`
`the
`
`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. (cid:9) 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
`
`701 (cid:9) 20304230321 (cid:9) 201701
`
`7772 (cid:9) 224440 (cid:9)
`
`000333222 (cid:9)
`
`0 0 (cid:9)
`
`ii (cid:9)
`
`777
`
`100
`
`page frames
`
`Figure 9.8 FIFO page-replacement algorithm.
`
`(cid:9)
`

`

`NA
`
`318 U 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.
`To illustrate the problems that are possible with a FIFO page-
`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
`is greater
`frames. We notice that the number of faults for four frames (10)
`than the number of faults for three frames (nine)! This result is most
`unexpected and is known as Belady’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
`
`16
`
`14
`
`12
`
`10
`
`U)
`
`a)
`C) ca (cid:9)
`C.
`
`a)
`E 6
`
`4
`
`2
`
`1 (cid:9)
`
`2 (cid:9)
`
`3 (cid:9)
`
`4 (cid:9)
`
`5 (cid:9)
`
`6 (cid:9)
`
`7
`
`number of frames
`
`Figure 9.9 Page-fault curve for FIFO replacement on a reference string.
`
`

`

`9.5 Page-Replacement Algorithms U 319
`
`algorithm will never suffer from Belady’s anomaly. An optimal page-
`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, (cid:9) on our sample reference string, (cid:9)
`the optimal page-
`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.) (cid:9)
`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.2.) As a result, the optimal algorithm is used mainly for
`comparison studies. (cid:9) For instance, it may be quite ueful 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
`
`reference string
`
`701 (cid:9) 20304230321 (cid:9) 201 (cid:9) 701
`
`1H1
`
`page frames
`
`Figure 9.10 Optimal page-replacement algorithm.
`
`ctive
`e:to.
`ctive
`page
`-fault
`
`)age-
`
`lable
`reater
`most
`s the
`may
`that
`;ome
`ways
`
`’r an (cid:9)
`rnent
`timal
`
`ig. (cid:9)
`
`I
`
`I (cid:9)
`
`

`

`320 (cid:149) Chapter 9: Virtual Memory
`
`reference string
`
`701 (cid:9) 20304230321 (cid:9) 201 (cid:9) 701
`
`7 772 (cid:9)
`
`000 (cid:9)
`1 (cid:9)
`1 (cid:9)
`
`page frames
`
`2 (cid:9)
`0 (cid:9)
`3 (cid:9)
`
`4440 (cid:9)
`
`0033 (cid:9)
`3222 (cid:9)
`
`1 (cid:9)
`
`3 (cid:9)
`2 (cid:9)
`
`1 (cid:9)
`
`0 (cid:9)
`2 (cid:9)
`
`1
`
`0
`7
`
`Figure 9.11 LRU page-replacement algorithm.
`
`FIFO algorithm uses the time when a page was brought into memory; the
`ovr 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 algorithm looking backward in time, rather than
`forward. (Strangely, if we let S R be the reverse of a reference string S.
`then the page-fault rate for the OPT algorithm on S 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 S is the same as the page-fault rate fcr the
`LRU
`algorithm on S 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 three pages in memory 10, 3, 41, 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:
`
`(cid:149) 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
`
`a
`a
`a
`
`(cid:9)
`(cid:9)
`

`

`9.5 Page-Replacement Algorithms U 321
`
`clock is incremented for every memory reference. Whenever a
`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 access. The
`times must also be maintained when page tables are changed (due to
`CPU scheduling). Overflow of the clock must be considered.
`(cid:149) 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 stick algorithm is an
`n
`algorithm for which it can be shown that the set of pages in memory for
`
`reference string
`
`47071 (cid:9) 01 (cid:9) 21 (cid:9) 27 t –1 (cid:9)
`
`2
`
`stack
`before
`a
`
`stack
`after
`b
`
`Figure 9.12 Use of a stack to record the most recent page references.
`
`

`

`322 (cid:149) 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. Some systems provide no hardware support, and other
`page-replacement algorithms (such as a FIFO algorithm) must be used.
`reference bit.
`Many systems provide some help, however, in the form of a
`The reference bit for a page is set, by the hardware, whenever that page is
`referenced (either a read or a write to any byte 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 executes, 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 used
`and which were not used. This partial ordering information leads to many
`page-replacement algorithms that approximate LRU replacement.
`
`9.5.4.1 Additional-Reference-Bits Algorithm
`We can gain additional ordering information by recording the reference
`bits at regular intervals. We can keep an 8-bit byte for each page in a table
`in memory. At regular intervals (say every 100 milliseconds), a timer
`interrupt transfers control to the operating system. The operating system
`shifts the reference bit for each page into the high-order bit of its 8-bit
`byte, shifting the other bits right 1 bit, discarding the low-order bit. These
`8-bit shift registers contain the history of page use for the last eight time
`periods. If the shift register contains 00000000, then the page has not been
`used for eight time periods; a page that is used at least once each period
`would have a shift register value of 11111111.
`A page with a history register value of 11000100 has been used more
`recently than has one with 01110111. If we interpret these 8-bit bytes as
`unsigned integers, the page with the lowest number is the LRU page, and it
`
`

`

`9.5 Page-Replacement Algorithms M 323
`
`can be replaced. Notice that the numbers are not guaranteed to be unique,
`however. We can either replace (swap out) all pages with the smallest
`value, or use a FIFO selection among them.
`The number of bits of history can be varied, of course, and would be
`selected (depending on the hardware available) to make the updating as
`fast as possible. In the extreme case, the number can be reduced to zero,
`leaving only the reference bit itself. This algorithm is called the second-
`chance page-replacement algorithm.
`
`9.5.4.2 Second-Chance Algorithm
`The basic algorithm of second-chance replacement is a
`FIFO replacement
`algorithm. When a page has been selected, however, we inspect its
`reference bit. If the value is 0, we proceed to replace this page. If the
`reference bit is 1, however, we give that page a second chance and move
`on to select the next FIFO page. When a page gets a second chance, its
`reference bit is cleared and its arrival time is reset to the current time.
`Thus, a page that is given a second chance will not be replaced until all
`other pages are replaced (or given second chances). In addition, if a page
`is used often enough to keep its reference bit set, it will never be replaced.
`One way to implement the second-chance (sometimes referred to as
`the clock) algorithm is as a circular queue. A pointer indicates which page
`is to be replaced next. When a frame is needed, the pointer advances until
`it finds a page with a 0 reference bit. As it advances, it clears the reference
`bits (Figure 9.13). Once a victim page is found, the page is replaced and
`the new page is inserted in the circular queue in that position. Notice
`that, in the worst case, when all bits are set, the pointer cycles through the
`whole queue, giving each page a second chance. It clears all the reference
`bits before selecting the next page for replacement. Second-chance
`replacement degenerates to FIFO replacement if all bits are set.
`
`9.5.4.3 Enhanced Second-Chance Algorithm
`The second-chance algorithm described above can be enhanced by
`considering both the reference bit and the modify bit (Section 9.4) as an
`ordered pair. With these 2 bits, we have the following four possible
`classes:
`
`1. (0,0) neither recently used nor modified - best page to replace
`
`2, (0,1) not recently used but modified - not quite as good, because the
`page will need to be written out before replacement
`
`3. (1,0) recently used but clean - probably will be used again soon
`
`4. (1,1) recently used and modified - probably will be used again, and
`write out will be needed before replacing it
`
`

`

`
`324 0 Chapter 9: Virtual Memory
`
`reference
`bits
`
`pages
`
`reference
`bits
`
`pages
`
`next
`victim (cid:9)
`
`H
`H
`LiI1
`H
`H
`H
`H
`
`H
`H
`H
`H
`
`H
`H
`
`circular queue of pages
`
`circular queue of pages
`
`(a)
`
`(b)
`
`Figure 9.13 Second-chance (clock) page-replacement algorithm.
`
`When page replacement is called for, each page is in one of these four
`classes. We use the same scheme as the clock algorithm, but instead of
`examining whether the page to which we are pointing has the reference bit
`set to 1, we examine the class to which that page belongs. We replace the
`first page encountered in the lowest nonempty class. Notice that we may
`have to scan the circular queue several times before we find a page to be
`replaced.
`This algorithm is used in the Macintosh virtual-memory-management
`scheme. The major difference between this algorithm and the simpler
`clock algorithm is that here we give preference to those pages that have
`been modified to reduce the number of I/os required.
`
`9.5.5 Counting Algorithms
`There are many other algorithms that can be used for page replacement.
`For example, we could keep a counter of the number of references that
`have been made to each page, and develop the following two schemes.
`
`

`

`9.5 Page-Replacement Algorithms U 325
`
`(cid:149) LFU Algorithm: The
`least frequently used
`(LFU) page-replacement
`algorithm requires that the page with the smallest count be replaced.
`The reason for this selection is that an actively used page should have
`a large reference count. This algorithm suffers from the situation in
`which a page is used heavily during the initial phase of a process, but
`then is never used again. Since it was used heavily, it has a large count
`and remains in memory even though it is no longer needed. One
`solution is to shift the counts right by 1 bit at regular intervals, forming
`an exponentially decaying average usage cou