text:
Principal Operating Systems: Internals and Design Principles
Operating Systems: Internals and Design PrinciplesWilliam Stallings
You may be interested in
You can write a book review and share your experiences. Other readers will always be interested in your opinion of the books you've read. Whether you've loved the book or not, if you give your honest and detailed thoughts then people will find new books that are right for them.
[image: ] Senior Vice President Courseware Portfolio Management: Marcia J. Horton Director, Portfolio Management: Engineering, Computer Science & Global Editions: Julian Partridge Higher Ed Portfolio Management: Tracy Johnson (Dunkelberger) Portfolio Management Assistant: Kristy Alaura Managing Content Producer: Scott Disanno Content Producer: Robert Engelhardt Web Developer: Steve Wright Rights and Permissions Manager: Ben Ferrini Manufacturing Buyer, Higher Ed, Lake Side Communications Inc (LSC): Maura Zaldivar-Garcia Inventory Manager: Ann Lam Marketing Manager: Demetrius Hall Product Marketing Manager: Yvonne Vannatta Marketing Assistant: Jon Bryant Cover Designer: Marta Samsel Cover Art: Colin Anderson/Getty Images Full-Service Project Management: Bhanuprakash Sherla, SPi Global Credits and acknowledgments borrowed from other sources and reproduced, with permission, in this textbook appear on page CL-1. © 2018, 2015, 2012, 2009 by Pearson Education, Inc., Hoboken, New Jersey 07030. All rights reserved. Manufactured in the United States of America. This publication is protected by Copyright, and permission should be obtained from the publisher prior to any prohibited reproduction, storage in a retrieval system, or transmission in any form or by any means, electronic, mechanical, photocopying, recording, or likewise. To obtain permission(s) to use material from this work, please submit a written request to Pearson Education, Inc., Permissions Department, Pearson Education, Inc., Hoboken, New Jersey 07030. Many of the designations by manufacturers and seller to distinguish their products are claimed as trademarks. Where those designations appear in this book, and the publisher was aware of a trademark claim, the designations have been printed in initial caps or all caps. Library of Congress Cataloging-in-Publication Data Names: Stallings, William, author. Title: Operating systems : internals and design principles / William Stallings. Description: Ninth edition. | Upper Saddle River, New Jersey : Pearson Education, Inc., [2017] | Includes bibliographical references and index. Identifiers: LCCN 2017000148| ISBN 9780134670959 | ISBN 0134670957 Subjects: LCSH: Operating systems (Computers) Classification: LCC QA76.77 .S73 2017 | DDC 005.4/3—dc23 LC record available at https://lccn.loc.gov/2017000148 1 17 ISBN 10: 0-13-467095-7 ISBN 13: 978-0-13-467095-9 Contents Online Chapters and Appendices xiii VideoNotes xv Preface xvii About the Author xxvii Part 1 Background 1 Chapter 1 Computer System Overview 1 1.1 Basic Elements 2 1.2 Evolution of the Microprocessor 4 1.3 Instruction Execution 4 1.4 Interrupts 7 1.5 The Memory Hierarchy 18 1.6 Cache Memory 21 1.7 Direct Memory Access 25 1.8 Multiprocessor and Multicore Organization 26 1.9 Key Terms, Review Questions, and Problems 30 1 A Performance Characteristics of Two-Level Memories 33 Chapter 2 Operating System Overview 40 2.1 Operating System Objectives and Functions 41 2.2 The Evolution of Operating Systems 45 2.3 Major Achievements 55 2.4 Developments Leading to Modern Operating Systems 64 2.5 Fault Tolerance 67 2.6 Os Design Considerations for Multiprocessor and Multicore 70 2.7 Microsoft Windows Overview 73 2.8 Traditional Unix Systems 80 2.9 Modern Unix Systems 82 2.10 Linux 85 2.11 Android 90 2.12 Key Terms, Review Questions, and Problems 99 Part 2 Processes 101 Chapter 3 Process Description and Control 101 3.1 What is a Process? 103 3.2 Process States 105 3.3 Process Description 120 3.4 Process Control 129 3.5 Execution of the Operating System 135 3.6 Unix Svr4 Process Management 138 3.7 Summary 143 3.8 Key Terms, Review Questions, and Problems 143 Chapter 4 Threads 148 4.1 Processes and Threads 149 4.2 Types of Threads 155 4.3 Multicore and Multithreading 162 4.4 Windows Process and Thread Management 167 4.5 Solaris Thread and Smp Management 174 4.6 Linux Process and Thread Management 178 4.7 Android Process and Thread Management 183 4.8 Mac OS X Grand Central Dispatch 187 4.9 Summary 189 4.10 Key Terms, Review Questions, and Problems 190 Chapter 5 Concurrency: Mutual Exclusion and Synchronization 195 5.1 Mutual Exclusion: Software Approaches 198 5.2 Principles of Concurrency 204 5.3 Mutual Exclusion: Hardware Support 213 5.4 Semaphores 216 5.5 Monitors 229 5.6 Message Passing 235 5.7 Readers/Writers Problem 242 5.8 Summary 246 5.9 Key Terms, Review Questions, and Problems 247 Chapter 6 Concurrency: Deadlock and Starvation 261 6.1 Principles of Deadlock 262 6.2 Deadlock Prevention 271 6.3 Deadlock Avoidance 272 6.4 Deadlock Detection 278 6.5 An Integrated Deadlock Strategy 280 6.6 Dining Philosophers Problem 281 6.7 Unix Concurrency Mechanisms 285 6.8 Linux Kernel Concurrency Mechanisms 287 6.9 Solaris Thread Synchronization Primitives 296 6.10 Windows Concurrency Mechanisms 298 6.11 Android Interprocess Communication 302 6.12 Summary 303 6.13 Key Terms, Review Questions, and Problems 304 Part 3 Memory 311 Chapter 7 Memory Management 311 7.1 Memory Management Requirements 312 7.2 Memory Partitioning 316 7.3 Paging 327 7.4 Segmentation 330 7.5 Summary 332 7.6 Key Terms, Review Questions, and Problems 332 7 A Loading and Linking 335 Chapter 8 Virtual Memory 342 8.1 Hardware and Control Structures 343 8.2 Operating System Software 360 8.3 Unix and Solaris Memory Management 379 8.4 Linux Memory Management 385 8.5 Windows Memory Management 389 8.6 Android Memory Management 391 8.7 Summary 392 8.8 Key Terms, Review Questions, and Problems 393 Part 4 Scheduling 397 Chapter 9 Uniprocessor Scheduling 397 9.1 Types of Processor Scheduling 398 9.2 Scheduling Algorithms 402 9.3 Traditional Unix Scheduling 424 9.4 Summary 426 9.5 Key Terms, Review Questions, and Problems 427 Chapter 10 Multiprocessor, Multicore, and Real-Time Scheduling 432 10.1 Multiprocessor and Multicore Scheduling 433 10.2 Real-Time Scheduling 446 10.3 Linux Scheduling 461 10.4 Unix Svr4 Scheduling 464 10.5 Unix Freebsd Scheduling 466 10.6 Windows Scheduling 470 10.7 Summary 472 10.8 Key Terms, Review Questions, and Problems 472 Part 5 Input/Output And Files 477 Chapter 11 I/O Management and Disk Scheduling 477 11.1 I/O Devices 478 11.2 Organization of the I/O Function 480 11.3 Operating System Design Issues 483 11.4 I/O Buffering 486 11.5 Disk Scheduling 489 11.6 Raid 496 11.7 Disk Cache 505 11.8 Unix Svr4 I/O 509 11.9 Linux I/O 512 11.10 Windows I/O 516 11.11 Summary 518 11.12 Key Terms, Review Questions, and Problems 519 Chapter 12 File Management 522 12.1 Overview 523 12.2 File Organization and Access 529 12.3 B-Trees 533 12.4 File Directories 536 12.5 File Sharing 541 12.6 Record Blocking 542 12.7 Secondary Storage Management 544 12.8 Unix File Management 552 12.9 Linux Virtual File System 557 12.10 Windows File System 561 12.11 Android File Management 566 12.12 Summary 567 12.13 Key Terms, Review Questions, and Problems 568 Part 6 Embedded Systems 571 Chapter 13 Embedded Operating Systems 571 13.1 Embedded Systems 572 13.2 Characteristics of Embedded Operating Systems 577 13.3 Embedded Linux 581 13.4 Tinyos 587 13.5 Key Terms, Review Questions, and Problems 597 Chapter 14 Virtual Machines 599 14.1 Virtual Machine Concepts 600 14.2 Hypervisors 603 14.3 Container Virtualization 607 14.4 Processor Issues 614 14.5 Memory Management 616 14.6 I/O Management 617 14.7 Vmware Esxi 619 14.8 Microsoft Hyper-V and Xen Variants 622 14.9 Java Vm 623 14.10 Linux Vserver Virtual Machine Architecture 624 14.11 Summary 627 14.12 Key Terms, Review Questions, and Problems 627 Chapter 15 Operating System Security 629 15.1 Intruders and Malicious Software 630 15.2 Buffer Overflow 634 15.3 Access Control 642 15.4 Unix Access Control 650 15.5 Operating Systems Hardening 653 15.6 Security Maintenance 657 15.7 Windows Security 658 15.8 Summary 663 15.9 Key Terms, Review Questions, and Problems 664 Chapter 16 Cloud and IoT Operating Systems 667 16.1 Cloud Computing 668 16.2 Cloud Operating Systems 676 16.3 The Internet of Things 692 16.4 IoT Operating Systems 696 16.5 Key Terms and Review Questions 703 Appendices Appendix A Topics in Concurrency A-1 A.1 Race Conditions and Semaphores A-2 A.2 A Barbershop Problem A-9 A.3 Problems A-14 Appendix B Programming and Operating System Projects B-1 B.1 Semaphore Projects B-2 B.2 File Systems Project B-3 B.3 OS/161 B-3 B.4 Simulations B-4 B.5 Programming Projects B-4 B.6 Research Projects B-6 B.7 Reading/Report Assignments B-7 B.8 Writing Assignments B-7 B.9 Discussion Topics B-7 B.10 BACI B-7 References R-1 Credits CL-1 Index I-1 Online Chapters and Appendices 1 1 Below chapters, appendices, and other documents are regarded as Premium Content Chapter 17 Network Protocols 17.1 The Need for a Protocol Architecture 17-3 17.2 The TCP/IP Protocol Architecture 17-5 17.3 Sockets 17-12 17.4 Linux Networking 17-16 17.5 Summary 17-18 17.6 Key Terms, Review Questions, and Problems 17-18 17A The Trivial File Transfer Protocol 17-21 Chapter 18 Distributed Processing, Client/Server, and Clusters 18.1 Client/Server Computing 18-2 18.2 Distributed Message Passing 18-12 18.3 Remote Procedure Calls 18-16 18.4 Clusters 18-19 18.5 Windows Cluster Server 18-25 18.6 Beowulf and Linux Clusters 18-27 18.7 Summary 18-29 18.8 References 18-29 18.9 Key Terms, Review Questions, and Problems 18-30 Chapter 19 Distributed Process Management 19.1 Process Migration 19-2 19.2 Distributed Global States 19-9 19.3 Distributed Mutual Exclusion 19-14 19.4 Distributed Deadlock 19-23 19.5 Summary 19-35 19.6 References 19-35 19.7 Key Terms, Review Questions, and Problems 19-37 Chapter 20 Overview of Probability and Stochastic Processes 20.1 Probability 20-2 20.2 Random Variables 20-7 20.3 Elementary Concepts of Stochastic Processes 20-12 20.4 Problems 20-20 Chapter 21 Queueing Analysis 21.1 How Queues Behave—A Simple Example 21-3 21.2 Why Queueing Analysis? 21-8 21.3 Queueing Models 21-10 21.4 Single-Server Queues 21-17 21.5 Multiserver Queues 21-20 21.6 Examples 21-20 21.7 Queues With Priorities 21-26 21.8 Networks of Queues 21-27 21.9 Other Queueing Models 21-31 21.10 Estimating Model Parameters 21-32 21.11 References 21-35 21.12 Problems 21-35 Programming Project One Developing a Shell Programming Project Two The HOST Dispatcher Shell Appendix C Topics in Concurrency C-1 Appendix D Object-Oriented Design D-1 Appendix E Amdahl's Law E-1 Appendix F Hash Tables F-1 Appendix G Response Time G-1 Appendix H Queueing System Concepts H-1 Appendix I The Complexity of Algorithms I-1 Appendix J Disk Storage Devices J-1 Appendix K Cryptographic Algorithms K-1 Appendix L Standards Organizations L-1 Appendix M Sockets: A Programmer's Introduction M-1 Appendix N The International Reference Alphabet N-1 Appendix O BACI: The Ben-Ari Concurrent Programming System O-1 Appendix P Procedure Control P-1 Appendix Q ECOS Q-1 Glossary VideoNotes Locations of VideoNotes http://www.pearsonhighered.com/stallings Chapter 5 Concurrency: Mutual Exclusion and Synchronization 195 5.1 Mutual Exclusion Attempts 199 5.2 Dekker's Algorithm 202 5.3 Peterson's Algorithm for Two Processes 203 5.4 Illustration of Mutual Exclusion 210 5.5 Hardware Support for Mutual Exclusion 214 5.6 A Definition of Semaphore Primitives 218 5.7 A Definition of Binary Semaphore Primitives 219 5.9 Mutual Exclusion Using Semaphores 221 5.12 An Incorrect Solution to the Infinite-Buffer Producer/Consumer Problem Using Binary Semaphores 224 5.13 A Correct Solution to the Infinite-Buffer Producer/Consumer Problem Using Binary Semaphores 226 5.14 A Solution to the Infinite-Buffer Producer/Consumer Problem Using Semaphores 227 5.16 A Solution to the Bounded-Buffer Producer/Consumer Problem Using Semaphores 228 5.17 Two Possible Implementations of Semaphores 229 5.19 A Solution to the Bounded-Buffer Producer/Consumer Problem Using a Monitor 232 5.20 Bounded-Buffer Monitor Code for Mesa Monitor 234 5.23 Mutual Exclusion Using Messages 240 5.24 A Solution to the Bounded-Buffer Producer/Consumer Problem Using Messages 241 5.25 A Solution to the Readers/Writers Problem Using Semaphore: Readers Have Priority 243 5.26 A Solution to the Readers/Writers Problem Using Semaphore: Writers Have Priority 245 5.27 A Solution to the Readers/Writers Problem Using Message Passing 246 5.28 An Application of Coroutines 249 Chapter 6 Concurrency: Deadlock and Starvation 261 6.9 Deadlock Avoidance Logic 277 6.12 A First Solution to the Dining Philosophers Problem 283 6.13 A Second Solution to the Dining Philosophers Problem 283 6.14 A Solution to the Dining Philosophers Problem Using a Monitor 284 6.18 Another Solution to the Dining Philosophers Problem Using a Monitor 309 Chapter 13 Embedded Operating Systems 571 13.12 Condition Variable Example Code 598 Preface WHAT'S NEW IN THE NINTH EDITION Since the eighth edition of this book was published, the field of operating systems has seen continuous innovations and improvements. In this new edition, I have tried to capture these changes while maintaining a comprehensive coverage of the entire field. To begin the process of revision, the eighth edition of this book was extensively reviewed by a number of professors who teach the subject and by professionals working in the field. The result is that, in many places, the narrative has been clarified and tightened, and illustrations have been improved. Beyond these refinements to improve pedagogy and user friendliness, the technical content of the book has been updated throughout to reflect the ongoing changes in this exciting field, and the instructor and student support has been expanded. The most noteworthy changes are as follows: Updated Linux coverage: The Linux material has been updated and expanded to reflect changes in the Linux kernel since the eighth edition. Updated Android coverage: The Android material has been updated and expanded to reflect changes in the Android kernel since the eighth edition. New Virtualization coverage: The chapter on virtual machines has been completely rewritten to provide better organization and an expanded and more up-to-date treatment. In addition, a new section has been added on the use of containers. New Cloud operating systems: New to this edition is the coverage of cloud operating systems, including an overview of cloud computing, a discussion of the principles and requirements for a cloud operating system, and a discussion of a OpenStack, a popular open-source Cloud OS. New IoT operating systems: New to this edition is the coverage of operating systems for the Internet of Things. The coverage includes an overview of the IoT, a discussion of the principles and requirements for an IoT operating system, and a discussion of a RIOT, a popular open-source IoT OS. Updated and Expanded Embedded operating systems: This chapter has been substantially revised and expanded including: The section on embedded systems has been expanded and now includes discussions of microcontrollers and deeply embedded systems. The overview section on embedded OSs has been expanded and updated. The treatment of embedded Linux has been expanded, and a new discussion of a popular embedded Linux system, μClinux, has been added. Concurrency: New projects have been added to the Projects Manual to better help the student understand the principles of concurrency. OBJECTIVES This book is about the concepts, structure, and mechanisms of operating systems. Its purpose is to present, as clearly and completely as possible, the nature and characteristics of modern-day operating systems. This task is challenging for several reasons. First, there is a tremendous range and variety of computer systems for which operating systems are designed. These include embedded systems, smart phones, single-user workstations and personal computers, medium-sized shared systems, large mainframe and supercomputers, and specialized machines such as real-time systems. The variety is not just confined to the capacity and speed of machines, but in applications and system support requirements. Second, the rapid pace of change that has always characterized computer systems continues without respite. A number of key areas in operating system design are of recent origin, and research into these and other new areas continues. In spite of this variety and pace of change, certain fundamental concepts apply consistently throughout. To be sure, the application of these concepts depends on the current state of technology and the particular application requirements. The intent of this book is to provide a thorough discussion of the fundamentals of operating system design, and to relate these to contemporary design issues and to current directions in the development of operating systems. EXAMPLE SYSTEMS This text is intended to acquaint the reader with the design principles and implementation issues of contemporary operating systems. Accordingly, a purely conceptual or theoretical treatment would be inadequate. To illustrate the concepts and to tie them to real-world design choices that must be made, four operating systems have been chosen as running examples: Windows: A multitasking operating system for personal computers, workstations, servers, and mobile devices. This operating system incorporates many of the latest developments in operating system technology. In addition, Windows is one of the first important commercial operating systems to rely heavily on object-oriented design principles. This book covers the technology used in the most recent version of Windows, known as Windows 10. Android: Android is tailored for embedded devices, especially mobile phones. Focusing on the unique requirements of the embedded environment, the book provides details of Android internals. UNIX: A multiuser operating system, originally intended for minicomputers, but implemented on a wide range of machines from powerful microcomputers to supercomputers. Several flavors of UNIX are included as examples. FreeBSD is a widely used system that incorporates many state-of-the-art features. Solaris is a widely used commercial version of UNIX. Linux: An open-source version of UNIX that is widely used. These systems were chosen because of their relevance and representativeness. The discussion of the example systems is distributed throughout the text rather than assembled as a single chapter or appendix. Thus, during the discussion of concurrency, the concurrency mechanisms of each example system are described, and the motivation for the individual design choices is discussed. With this approach, the design concepts discussed in a given chapter are immediately reinforced with real-world examples. For convenience, all of the material for each of the example systems is also available as an online document. SUPPORT OF ACM/IEEE COMPUTER SCIENCE CURRICULA 2013 The book is intended for both an academic and a professional audience. As a textbook, it is intended as a one-semester or two-semester undergraduate course in operating systems for computer science, computer engineering, and electrical engineering majors. This edition is designed to support the recommendations of the current (December 2013) version of the ACM/IEEE Computer Science Curricula 2013 (CS2013). The CS2013 curriculum recommendation includes Operating Systems (OS) as one of the Knowledge Areas in the Computer Science Body of Knowledge. CS2013 divides all course work into three categories: Core-Tier 1 (all topics should be included in the curriculum), Core-Tier 2 (all or almost all topics should be included), and Elective (desirable to provide breadth and depth). In the OS area, CS2013 includes two Tier 1 topics, four Tier 2 topics, and six Elective topics, each of which has a number of subtopics. This text covers all of the topics and subtopics listed by CS2013 in these three categories. Table P.1 shows the support for the OS Knowledge Areas provided in this textbook. A detailed list of subtopics for each topic is available as the file CS2013-OS .pdf at box.com/OS9e. Table P.1 Coverage of CS2013 Operating Systems (OSs) Knowledge Area Topic Coverage in Book Overview of Operating Systems (Tier 1) Chapter 2: Operating System Overview Operating System Principles (Tier 1) Chapter 1: Computer System Overview Chapter 2: Operating System Overview Concurrency (Tier 2) Chapter 5: Mutual Exclusion and Synchronization Chapter 6: Deadlock and Starvation Appendix A: Topics in Concurrency Chapter 18: Distributed Process Management Scheduling and Dispatch (Tier 2) Chapter 9: Uniprocessor Scheduling Chapter 10: Multiprocessor and Real-Time Scheduling Memory Management (Tier 2) Chapter 7: Memory Management Chapter 8: Virtual Memory Security and Protection (Tier 2) Chapter 15: Operating System Security Virtual Machines (Elective) Chapter 14: Virtual Machines Device Management (Elective) Chapter 11: I/O Management and Disk Scheduling File System (Elective) Chapter 12: File Management Real Time and Embedded Systems (Elective) Chapter 10: Multiprocessor and Real-Time Scheduling Chapter 13: Embedded Operating Systems Material on Android throughout the text Fault Tolerance (Elective) Section 2.5: Fault Tolerance System Performance Evaluation (Elective) Performance issues related to memory management, scheduling, and other areas addressed throughout the text PLAN OF THE TEXT The book is divided into six parts: Background Processes Memory Scheduling Input/Output and files Advanced topics (embedded OSs, virtual machines, OS security, and cloud and IoT operating systems) The book includes a number of pedagogic features, including the use of animations and videonotes and numerous figures and tables to clarify the discussion. Each chapter includes a list of key words, review questions, and homework problems. The book also includes an extensive glossary, a list of frequently used acronyms, and a bibliography. In addition, a test bank is available to instructors. INSTRUCTOR SUPPORT MATERIALS The major goal of this text is to make it as effective a teaching tool as possible for this fundamental yet evolving subject. This goal is reflected both in the structure of the book and in the supporting material. The text is accompanied by the following supplementary material to aid the instructor: Solutions manual: Solutions to end-of-chapter Review Questions and Problems. Projects manual: Suggested project assignments for all of the project categories listed in this Preface. PowerPoint slides: A set of slides covering all chapters, suitable for use in lecturing. PDF files: Reproductions of all figures and tables from the book. Test bank: A chapter-by-chapter set of questions with a separate file of answers. VideoNotes on concurrency: Professors perennially cite concurrency as perhaps the most difficult concept in the field of operating systems for students to grasp. The edition is accompanied by a number of VideoNotes lectures discussing the various concurrency algorithms defined in the book. This icon appears next to each algorithm definition in the book to indicate that a VideoNote is available: Sample syllabuses: The text contains more material that can be conveniently covered in one semester. Accordingly, instructors are provided with several sample syllabuses that guide the use of the text within limited time. These samples are based on real-world experience by professors with the seventh edition. All of these support materials are available at the Instructor Resource Center (IRC) for this textbook, which can be reached through the publisher's website www.pearsonhighered.com/stallings or by clicking on the link labeled Pearson Resources for Instructors at this book's Author Web site at WilliamStallings.com /OperatingSystems. To gain access to the IRC, please contact your local Pearson sales representative via pearsonhighered.com/educator/replocator/requestSalesRep .page or call Pearson Faculty Services at 1-800-526-0485. The Author website, at WilliamStallings.com/OperatingSystems (click on Instructor Resources link), includes the following: Links to websites for other courses being taught using this book. Sign-up information for an Internet mailing list for instructors using this book to exchange information, suggestions, and questions with each other and with the author. PROJECTS AND OTHER STUDENT EXERCISES For many instructors, an important component of an OS course is a project or set of projects by which the student gets hands-on experience to reinforce concepts from the text. This book has incorporated a projects component in the course as a result of an overwhelming support it received. In the online portion of the text, two major programming projects are defined. In addition, the instructor's support materials available through Pearson not only includes guidance on how to assign and structure the various projects, but also includes a set of user's manuals for various project types plus specific assignments, all written especially for this book. Instructors can assign work in the following areas: OS/161 projects: Described later. Simulation projects: Described later. Semaphore projects: Designed to help students understand concurrency concepts, including race conditions, starvation, and deadlock. Kernel projects: The IRC includes complete instructor support for two different sets of Linux kernel programming projects, as well as a set of kernel programming projects for Android. Programming projects: Described below. Research projects: A series of research assignments that instruct the student to research a particular topic on the Internet and write a report. Reading/report assignments: A list of papers that can be assigned for reading and writing a report, plus suggested assignment wording. Writing assignments: A list of writing assignments to facilitate learning the material. Discussion topics: These topics can be used in a classroom, chat room, or message board environment to explore certain areas in greater depth and to foster student collaboration. In addition, information is provided on a software package known as BACI that serves as a framework for studying concurrency mechanisms. This diverse set of projects and other student exercises enables the instructor to use the book as one component in a rich and varied learning experience and to tailor a course plan to meet the specific needs of the instructor and students. See Appendix B in this book for details. OS/161 This edition provides support for an active learning component based on OS/161. OS/161 is an educational operating system that is becoming increasingly recognized as the preferred teaching platform for OS internals. It aims to strike a balance between giving students experience in working on a real operating system, and potentially overwhelming students with the complexity that exists in a full-fledged operating system, such as Linux. Compared to most deployed operating systems, OS/161 is quite small (approximately 20,000 lines of code and comments), and therefore it is much easier to develop an understanding of the entire code base. The IRC includes: A packaged set of html files that the instructor can upload to a course server for student access. A getting-started manual to be distributed to students to help them begin using OS/161. A set of exercises using OS/161, to be distributed to students. Model solutions to each exercise for the instructor's use. All of this will be cross-referenced with appropriate sections in the book, so the student can read the textbook material then do the corresponding OS/161 project. SIMULATIONS The IRC provides support for assigning projects based on a set of seven simulations that cover key areas of OS design. The student can use a set of simulation packages to analyze OS design features. The simulators are written in Java and can be run either locally as a Java application or online through a browser. The IRC includes specific assignments to give to students, telling them specifically what they are to do and what results are expected. ANIMATIONS This edition also incorporates animations. Animations provide a powerful tool for understanding the complex mechanisms of a modern OS. A total of 53 animations are used to illustrate key functions and algorithms in OS design. The animations are used for Chapters 3, 5, 6, 7, 8, 9, and 11. PROGRAMMING PROJECTS This edition provides support for programming projects. Two major programming projects, one to build a shell, or command line interpreter, and one to build a process dispatcher are described in the online portion of this textbook. The IRC provides further information and step-by-step exercises for developing the programs. As an alternative, the instructor can assign a more extensive series of projects that cover many of the principles in the book. The student is provided with detailed instructions for doing each of the projects. In addition, there is a set of homework problems, which involve questions related to each project for the student to answer. Finally, the project manual provided at the IRC includes a series of programming projects that cover a broad range of topics and that can be implemented in any suitable language on any platform. ONLINE DOCUMENTS AND VIDEONOTES FOR STUDENTS For this new edition, a substantial amount of original supporting material for students has been made available online, at two online locations. The Author website, at WilliamStallings.com/OperatingSystems (click on Student Resources link), includes a list of relevant links organized by chapter and an errata sheet for the book. Purchasing this textbook new also grants the reader twelve months of access to the Companion Website, which includes the following materials: Online chapters: To limit the size and cost of the book, 5 chapters of the book, covering security, are provided in PDF format. The chapters are listed in this book's table of contents. Online appendices: There are numerous interesting topics that support material found in the text, but whose inclusion is not warranted in the printed text. A total of 15 online appendices cover these topics for the interested student. The appendices are listed in this book's table of contents. Homework problems and solutions: To aid the student in understanding the material, a separate set of homework problems with solutions is available. Animations: Animations provide a powerful tool for understanding the complex mechanisms of a modern OS. A total of 53 animations are used to illustrate key functions and algorithms in OS design. The animations are used for Chapters 3, 5, 6, 7, 8, 9, and 11. VideoNotes: VideoNotes are step-by-step video tutorials specifically designed to enhance the programming concepts presented in this textbook. The book is accompanied by a number of VideoNotes lectures discussing the various concurrency algorithms defined in the book. To access the Premium Content site, click on the Premium Content link at the Companion website or at pearsonhighered.com/stallings and enter the student access code found on the card in the front of the book. ACKNOWLEDGMENTS I would like to thank the following for their contributions. Rami Rosen contributed most of the new material on Linux. Vineet Chadha made a major contribution to the new chapter on virtual machines. Durgadoss Ramanathan provided the new material on Android ART. Through its multiple editions this book has benefited from review by hundreds of instructors and professionals, who generously spared their precious time and shared their expertise. Here I acknowledge those whose help contributed to this latest edition. The following instructors reviewed all or a large part of the manuscript for this edition: Jiang Guo (California State University, Los Angeles), Euripides Montagne (University of Central Florida), Kihong Park (Purdue University), Mohammad Abdus Salam (Southern University and A&M College), Robert Marmorstein (Longwood University), Christopher Diaz (Seton Hill University), and Barbara Bracken (Wilkes University). Thanks also to all those who provided detailed technical reviews of one or more chapters: Nischay Anikar, Adri Jovin, Ron Munitz, Fatih Eyup Nar, Atte Peltomaki, Durgadoss Ramanathan, Carlos Villavieja, Wei Wang, Serban Constantinescu and Chen Yang. Thanks also to those who provided detailed reviews of the example systems. Reviews of the Android material were provided by Kristopher Micinski, Ron Munitz, Atte Peltomaki, Durgadoss Ramanathan, Manish Shakya, Samuel Simon, Wei Wang, and Chen Yang. The Linux reviewers were Tigran Aivazian, Kaiwan Billimoria, Peter Huewe, Manmohan Manoharan, Rami Rosen, Neha Naik, and Hualing Yu. The Windows material was reviewed by Francisco Cotrina, Sam Haidar, Christopher Kuleci, Benny Olsson, and Dave Probert. The RIOT material was reviewed by Emmanuel Baccelli and Kaspar Schleiser, and OpenStack was reviewed by Bob Callaway. Nick Garnett of eCosCentric reviewed the material on eCos; and Philip Levis, one of the developers of TinyOS reviewed the material on TinyOS. Sid Young reviewed the material on container virtualization. Andrew Peterson of the University of Toronto prepared the OS/161 supplements for the IRC. James Craig Burley authored and recorded the VideoNotes. Adam Critchley (University of Texas at San Antonio) developed the simulation exercises. Matt Sparks (University of Illinois at Urbana-Champaign) adapted a set of programming problems for use with this textbook. Lawrie Brown of the Australian Defence Force Academy produced the material on buffer overflow attacks. Ching-Kuang Shene (Michigan Tech University) provided the examples used in the section on race conditions and reviewed the section. Tracy Camp and Keith Hellman, both at the Colorado School of Mines, developed a new set of homework problems. In addition, Fernando Ariel Gont contributed a number of homework problems; he also provided detailed reviews of all of the chapters. I would also like to thank Bill Bynum (College of William and Mary) and Tracy Camp (Colorado School of Mines) for contributing Appendix O; Steve Taylor (Worcester Polytechnic Institute) for contributing the programming projects and reading/report assignments in the instructor's manual; and Professor Tan N. Nguyen (George Mason University) for contributing the research projects in the instruction manual. Ian G. Graham (Griffith University) contributed the two programming projects in the textbook. Oskars Rieksts (Kutztown University) generously allowed me to make use of his lecture notes, quizzes, and projects. Finally, I thank the many people responsible for the publication of this book, all of whom did their usual excellent job. This includes the staff at Pearson, particularly my editor Tracy Johnson, her assistant Kristy Alaura, program manager Carole Snyder, and project manager Bob Engelhardt. Thanks also to the marketing and sales staffs at Pearson, without whose efforts this book would not be in front of you. About the Author Dr. William Stallings has authored 18 titles, and including the revised editions, over 40 books on computer security, computer networking, and computer architecture. His writings have appeared in numerous publications, including the Proceedings of the IEEE, ACM Computing Reviews and Cryptologia. He has received the Best Computer Science textbook of the Year award 13 times from the Text and Academic Authors Association. In over 30 years in the field, he has been a technical contributor, technical manager, and an executive with several high-technology firms. He has designed and implemented both TCP/IP-based and OSI-based protocol suites on a variety of computers and operating systems, ranging from microcomputers to mainframes. As a consultant, he has advised government agencies, computer and software vendors, and major users on the design, selection, and use of networking software and products. He created and maintains the Computer Science Student Resource Site at ComputerScienceStudent.com. This site provides documents and links on a variety of subjects of general interest to computer science students (and professionals). He is a member of the editorial board of Cryptologia, a scholarly journal devoted to all aspects of cryptology. Dr. Stallings holds a Ph.D. from M.I.T. in Computer Science and a B.S. from Notre Dame in electrical engineering. The William Stallings Books on Computer and Data Communications Technology Data and Computer Communications, Tenth Edition A comprehensive survey that has become the standard in the field, covering: (1) data communications, including transmission, media, signal encoding, link control, and multiplexing; (2) communication networks, including wired and wireless WANs and LANs; (3) the TCP/IP protocol suite, including IPv6, TCP, MIME, and HTTP, as well as a detailed treatment of network security. Received the 2007 Text and Academic Authors Association (TAA) award for the best Computer Science and Engineering Textbook of the year. Computer Organization and Architecture, Tenth Edition A unified view of this broad field. Covers fundamentals such as CPU, control unit, microprogramming, instruction set, I/O, and memory. Also covers advanced topics such as multicore, superscalar, and parallel organization. Five-time winner of the TAA award for the best Computer Science and Engineering Textbook of the year. Wireless Communication Networks and Systems, first edition (with Cory Beard) A comprehensive, state-of-the-art survey. Covers fundamental wireless communications topics, including antennas and propagation, signal encoding techniques, spread spectrum, and error correction techniques. Examines satellite, cellular, wireless local loop networks and wireless LANs, including Bluetooth and 802.11. Covers wireless mobile networks and applications. Computer Security, Third Edition (with Lawrie Brown) A comprehensive treatment of computer security technology, including algorithms, protocols, and applications. Covers cryptography, authentication, access control, database security, cloud security, intrusion detection and prevention, malicious software, denial of service, firewalls, software security, physical security, human factors, auditing, legal and ethical aspects, and trusted systems. Received the 2008 TAA award for the best Computer Science and Engineering Textbook of the year. Foundations of Modern Networking: SDN, NFV, QoE, IoT, and Cloud, first edition An in-depth up-to-date survey and tutorial on Software Defined Networking, Network Functions Virtualization, Quality of Experience, Internet of Things, and Cloud Computing and Networking. Examines standards, technologies, and deployment issues. Also treats security and career topics. Cryptography and Network Security, Seventh Edition A tutorial and survey on network security technology. Each of the basic building blocks of network security, including conventional and public-key cryptography, authentication, and digital signatures, are covered. Provides a thorough mathematical background for such algorithms as AES and RSA. The book covers important network security tools and applications, including email security, IP Security, Kerberos, SSL/TLS, network access control, cloud security, and Wi-Fi security. In addition, methods for countering hackers and viruses are explored. Second edition received the TAA award for the best Computer Science and Engineering Textbook of 1999. Network Security Essentials, Sixth Edition A tutorial and survey on network security technology. The book covers important network security tools and applications, including email security, IP Security, Kerberos, SSL/TLS, network access control, cloud security, and Wi-Fi security. In addition, methods for countering hackers and viruses are explored. Business Data Communications, Seventh Edition (with Tom Case) A comprehensive presentation of data communications and telecommunications from a business perspective. Covers voice, data, image, and video communications and applications technology, and includes a number of case studies. Topics covered include data communications, TCP/IP, cloud computing, Internet protocols and applications, LANs and WANs, network security, and network management. Part 1 Background Chapter 1 Computer System Overview 1.1 Basic Elements 1.2 Evolution of the Microprocessor 1.3 Instruction Execution 1.4 Interrupts Interrupts and the Instruction Cycle Interrupt Processing Multiple Interrupts 1.5 The Memory Hierarchy 1.6 Cache Memory Motivation Cache Principles Cache Design 1.7 Direct Memory Access 1.8 Multiprocessor and Multicore Organization Symmetric Multiprocessors Multicore Computers 1.9 Key Terms, Review Questions, and Problems APPENDIX 1A Performance Characteristics of Two-Level Memories Locality Operation of Two-Level Memory Performance Learning Objectives After studying this chapter, you should be able to: Describe the basic elements of a computer system and their interrelationship. Explain the steps taken by a processor to execute an instruction. Understand the concept of interrupts, and how and why a processor uses interrupts. List and describe the levels of a typical computer memory hierarchy. Explain the basic characteristics of multiprocessor systems and multicore computers. Discuss the concept of locality and analyze the performance of a multilevel memory hierarchy. Understand the operation of a stack and its use to support procedure call and return. An operating system (OS) exploits the hardware resources of one or more processors to provide a set of services to system users. The OS also manages secondary memory and I/O (input/output) devices on behalf of its users. Accordingly, it is important to have some understanding of the underlying computer system hardware before we begin our examination of operating systems. This chapter provides an overview of computer system hardware. In most areas, the survey is brief, as it is assumed that the reader is familiar with this subject. However, several areas are covered in some detail because of their importance to topics covered later in the book. Additional topics are covered in Appendix C. For a more detailed treatment, see [STAL16a]. 1.1 BASIC ELEMENTS At a top level, a computer consists of processor, memory, and I/O components, with one or more modules of each type. These components are interconnected in some fashion to achieve the main function of the computer, which is to execute programs. Thus, there are four main structural elements: Processor: Controls the operation of the computer and performs its data processing functions. When there is only one processor, it is often referred to as the central processing unit (CPU). Main memory: Stores data and programs. This memory is typically volatile; that is, when the computer is shut down, the contents of the memory are lost. In contrast, the contents of disk memory are retained even when the computer system is shut down. Main memory is also referred to as real memory or primary memory. I/O modules: Move data between the computer and its external environment. The external environment consists of a variety of devices, including secondary memory devices (e.g., disks), communications equipment, and terminals. System bus: Provides for communication among processors, main memory, and I/O modules. Figure 1.1 depicts these top-level components. One of the processor's functions is to exchange data with memory. For this purpose, it typically makes use of two internal (to the processor) registers: a memory address register (MAR), which specifies the address in memory for the next read or write; and a memory buffer register (MBR), which contains the data to be written into memory, or receives the data read from memory. Similarly, an I/O address register (I/OAR) specifies a particular I/O device. An I/O buffer register (I/OBR) is used for the exchange of data between an I/O module and the processor. [image: A diagram provides a top-level view of computer components.] Figure 1.1 Computer Components: Top-Level View Description The computer components are as follows: The C P U consists of the P C, I R, execution unit, M Ay R, M B R, I/O Ay R, and I/O B R. The I/O Module consists of buffers. The main memory consists of instruction layers on top of data layers from 0 to n minus 1. The system bus leads from the C P U and I/O module to the main memory A memory module consists of a set of locations, defined by sequentially numbered addresses. Each location contains a bit pattern that can be interpreted as either an instruction or data. An I/O module transfers data from external devices to processor and memory, and vice versa. It contains internal buffers for temporarily storing data until they can be sent on. 1.2 EVOLUTION OF THE MICROPROCESSOR The hardware revolution that brought about desktop and handheld computing was the invention of the microprocessor, which contained a processor on a single chip. Though originally much slower than multichip processors, microprocessors have continually evolved to the point that they are now much faster for most computations due to the physics involved in moving information around in sub-nanosecond timeframes. Not only have microprocessors become the fastest general-purpose processors available, they are now multiprocessors; each chip (called a socket) contains multiple processors (called cores), each with multiple levels of large memory caches, and multiple logical processors sharing the execution units of each core. As of 2010, it is not unusual for even a laptop to have 2 or 4 cores, each with 2 hardware threads, for a total of 4 or 8 logical processors. Although processors provide very good performance for most forms of computing, there is increasing demand for numerical computation. Graphical Processing Units (GPUs) provide efficient computation on arrays of data using Single-Instruction Multiple Data (SIMD) techniques pioneered in supercomputers. GPUs are no longer used just for rendering advanced graphics, but they are also used for general numerical processing, such as physics simulations for games or computations on large spreadsheets. Simultaneously, the CPUs themselves are gaining the capability of operating on arrays of data–with increasingly powerful vector units integrated into the processor architecture of the x86 and AMD64 families. Processors and GPUs are not the end of the computational story for the modern PC. Digital Signal Processors (DSPs) are also present for dealing with streaming signals such as audio or video. DSPs used to be embedded in I/O devices, like modems, but they are now becoming first-class computational devices, especially in handhelds. Other specialized computational devices (fixed function units) co-exist with the CPU to support other standard computations, such as encoding/decoding speech and video (codecs), or providing support for encryption and security. To satisfy the requirements of handheld devices, the classic microprocessor is giving way to the System on a Chip (SoC), where not just the CPUs and caches are on the same chip, but also many of the other components of the system, such as DSPs, GPUs, I/O devices (such as radios and codecs), and main memory. 1.3 INSTRUCTION EXECUTION A program to be executed by a processor consists of a set of instructions stored in memory. In its simplest form, instruction processing consists of two steps: The processor reads (fetches) instructions from memory one at a time and executes each instruction. Program execution consists of repeating the process of instruction fetch and instruction execution. Instruction execution may involve several operations and depends on the nature of the instruction. The processing required for a single instruction is called an instruction cycle. Using a simplified two-step description, the instruction cycle is depicted in Figure 1.2. The two steps are referred to as the fetch stage and the execute stage. Program execution halts only if the processor is turned off, some sort of unrecoverable error occurs, or a program instruction that halts the processor is encountered. [image: A flowchart diagram.] Figure 1.2 Basic Instruction Cycle Description The basic instruction cycle is as follows: start, fetch next instruction, execute next instructions, halt, with a feedback loop from the execute stage to the fetch stage. At the beginning of each instruction cycle, the processor fetches an instruction from memory. Typically, the program counter (PC) holds the address of the next instruction to be fetched. Unless instructed otherwise, the processor always increments the PC after each instruction fetch so it will fetch the next instruction in sequence (i.e., the instruction located at the next higher memory address). For example, consider a simplified computer in which each instruction occupies one 16-bit word of memory. Assume that the program counter is set to location 300. The processor will next fetch the instruction at location 300. On succeeding instruction cycles, it will fetch instructions from locations 301, 302, 303, and so on. This sequence may be altered, as explained subsequently. The fetched instruction is loaded into the instruction register (IR). The instruction contains bits that specify the action the processor is to take. The processor interprets the instruction and performs the required action. In general, these actions fall into four categories: Processor-memory: Data may be transferred from processor to memory, or from memory to processor. Processor-I/O: Data may be transferred to or from a peripheral device by transferring between the processor and an I/O module. Data processing: The processor may perform some arithmetic or logic operation on data. Control: An instruction may specify that the sequence of execution be altered. For example, the processor may fetch an instruction from location 149, which specifies that the next instruction be from location 182. The processor sets the program counter to 182. Thus, on the next fetch stage, the instruction will be fetched from location 182 rather than 150. An instruction's execution may involve a combination of these actions. Consider a simple example using a hypothetical processor that includes the characteristics listed in Figure 1.3. The processor contains a single data register, called the accumulator (AC). Both instructions and data are 16 bits long, and memory is organized as a sequence of 16-bit words. The instruction format provides 4 bits for the opcode, allowing as many as 24=16 different opcodes (represented by a single hexadecimal1 digit). The opcode defines the operation the processor is to perform. With the remaining 12 bits of the instruction format, up to 212=4,096 (4K) words of memory (denoted by three hexadecimal digits) can be directly addressed. 1 A basic refresher on number systems (decimal, binary, hexadecimal) can be found at the Computer Science Student Resource Site at ComputerScienceStudent.com. [image: A diagram shows two 16-bit words, along with internal C P U registers and a partial list of op codes.] Figure 1.3 Characteristics of a Hypothetical Machine Description Part ay: instruction format. The word has two parts, listed with their bit locations: op code, bits 0 to 3; address, bits 4 to 15. Part b: integer format. The word has two parts, listed with their bit locations: S, bit 0; magnitude, bits 1 to 15. Part c: internal C P U registers. Program counter, P C, = address of instruction. Instruction register, I R, = instruction being executed. Accumulator, Ay C, = temporary storage. Part d: partial list of op codes. 0 0 0 1 = load Ay C from memory. 0 0 1 0 = store Ay C to memory. 0 1 0 1 = add to Ay C from memory. Figure 1.4 illustrates a partial program execution, showing the relevant portions of memory and processor registers. The program fragment shown adds the contents of the memory word at address 940 to the contents of the memory word at address 941 and stores the result in the latter location. Three instructions, which can be described as three fetch and three execute stages, are required: [image: A diagram represents program execution.] Figure 1.4 Example of Program Execution (contents of memory and registers in hexadecimal) Description Program execution involves six steps, alternating between the fetch and execute stages. Step 1, fetch: Data from the memory is loaded into the C P U registers. The following list provides the addresses and hexadecimal values for different locations in the memory: 300, 1 9 4 0; 301, 5 9 4 1; 302, 2 9 4 1; 940, 0 0 0 3; 941, 0 0 0 2. The C P U registers has three locations with the following addresses and values: P C, 3 0 0; Ay C, blank; I R, blank. The value, 1 9 4 0, is transferred from address 300 in memory to address I R in C P U registers. Step 2, execute: Data from the memory is loaded into the C P U registers. The following list provides the addresses and hexadecimal values for different locations in the memory: 300, 1 9 4 0; 301, 5 9 4 1; 302, 2 9 4 1; 940, 0 0 0 3; 941, 0 0 0 2. The C P U registers has three locations with the following addresses and values: P C, 3 0 0; Ay C, blank; I R, blank. The value, 1 9 4 0, is transferred from address 300 in memory to address I R in C P U registers. Step 3, fetch: Data from the memory is loaded into the C P U registers. The following list provides the addresses and hexadecimal values for different locations in the memory: 300, 1 9 4 0; 301, 5 9 4 1; 302, 2 9 4 1; 940, 0 0 0 3; 941, 0 0 0 2. The C P U registers has three locations with the following addresses and values: P C, 3 0 1; Ay C, 0 0 0 3; I R, 5 9 4 1. The value, 5 9 4 1, is transferred from address 300 in memory to address I R in C P U registers. Step 4,execute: Data from the memory is loaded into the C P U registers. The following list provides the addresses and hexadecimal values for different locations in the memory: 300, 1 9 4 0; 301, 5 9 4 1; 302, 2 9 4 1; 940, 0 0 0 3; 941, 0 0 0 2. The C P U registers has three locations with the following addresses and values: P C, 3 0 2; Ay C, 0 0 0 5; I R, 5 9 4 1. The values, 0 0 0 2, from the address 941 and 0 0 0 3 from address 940 are transferred in memory to address A C in C P U registers. Step 5, fetch: Data from the memory is loaded into the C P U registers. The following list provides the addresses and hexadecimal values for different locations in the memory: 300, 1 9 4 0; 301, 5 9 4 1; 302, 2 9 4 1; 940, 0 0 0 3; 941, 0 0 0 2. The C P U registers has three locations with the following addresses and values: P C, 3 0 2; Ay C, 0 0 0 5; I R, 2 9 4 1. The value, 1 9 4 1, is transferred from address 302 in memory to address I R in C P U registers. Step 6, execute: Data from the memory is loaded into the C P U registers. The following list provides the addresses and hexadecimal values for different locations in the memory: 300, 1 9 4 0; 301, 5 9 4 1; 302, 2 9 4 1; 940, 0 0 0 3; 941, 0 0 0 5. The C P U registers has three locations with the following addresses and values: P C, 3 0 3; Ay C, 0 0 0 5; I R, 2 9 4 1. The value, 2 9 4 1, is transferred from C P U register AC is transferred to address 941 in memory. The PC contains 300, the address of the first instruction. This instruction (the value 1940 in hexadecimal) is loaded into the IR and the PC is incremented. Note that this process involves the use of a memory address register (MAR) and a memory buffer register (MBR). For simplicity, these intermediate registers are not shown. The first 4 bits (first hexadecimal digit) in the IR indicate that the AC is to be loaded from memory. The remaining 12 bits (three hexadecimal digits) specify the address, which is 940. The next instruction (5941) is fetched from location 301 and the PC is incremented. The old contents of the AC and the contents of location 941 are added, and the result is stored in the AC. The next instruction (2941) is fetched from location 302, and the PC is incremented. The contents of the AC are stored in location 941. In this example, three instruction cycles, each consisting of a fetch stage and an execute stage, are needed to add the contents of location 940 to the contents of 941. With a more complex set of instructions, fewer instruction cycles would be needed. Most modern processors include instructions that contain more than one address. Thus, the execution stage for a particular instruction may involve more than one reference to memory. Also, instead of memory references, an instruction may specify an I/O operation. 1.4 INTERRUPTS Virtually all computers provide a mechanism by which other modules (I/O, memory) may interrupt the normal sequencing of the processor. Table 1.1 lists the most common classes of interrupts. Table 1.1 Classes of Interrupts Program Generated by some condition that occurs as a result of an instruction execution, such as arithmetic overflow, division by zero, attempt to execute an illegal machine instruction, or reference outside a user's allowed memory space. Timer Generated by a timer within the processor. This allows the operating system to perform certain functions on a regular basis. I/O Generated by an I/O controller, to signal normal completion of an operation or to signal a variety of error conditions. Hardware failure Generated by a failure, such as power failure or memory parity error. Interrupts are provided primarily as a way to improve processor utilization. For example, most I/O devices are much slower than the processor. Suppose that the processor is transferring data to a printer using the instruction cycle scheme of Figure 1.2. After each write operation, the processor must pause and remain idle until the printer catches up. The length of this pause may be on the order of many thousands or even millions of instruction cycles. Clearly, this is a very wasteful use of the processor. To give a specific example, consider a PC that operates at 1 GHz, which would allow roughly 109 instructions per second.2 A typical hard disk has a rotational speed of 7200 revolutions per minute for a half-track rotation time of 4 ms, which is 4 million times slower than the processor. 2 A discussion of the uses of numerical prefixes, such as giga and tera, is contained in a supporting document at the Computer Science Student Resource Site at ComputerScienceStudent.com. Figure 1.5a illustrates this state of affairs. The user program performs a series of WRITE calls interleaved with processing. The solid vertical lines represent segments of code in a program. Code segments 1, 2, and 3 refer to sequences of instructions that do not involve I/O. The WRITE calls are to an I/O routine that is a system utility and will perform the actual I/O operation. The I/O program consists of three sections: [image: A diagram represents program flow with and without interrupts.] Figure 1.5 Program Flow of Control Without and With Interrupts Description Part ay: no interrupts. The user program begins with code segment 1, followed by a write call. The write call initiates the I O program, which consists of the following sequence: code segment 4, I O command, code segment 5, end, with the end command fed back to the write call. After the first write call, the user program proceeds to code segment 2, followed by a second write call, which initiates the same sequence in the I O program. The user program concludes with code segment 3 and a third write call. Part b: interrupts; short I/O wait. The user program begins with code segment 1, followed by a write call. The write call initiates the I O program, which consists of the following sequence: code segment 4, I O command. After the first write call, the user program proceeds to code segment 2 a wait 2b, followed by a second write call, which initiates an interrupt handler, which consists of a code segment 5, end. The user program concludes with code segment 3a wait 3b and a third write call. Part c: interrupts; long I/O wait. The user program begins with code segment 1, followed by a write call. The write call initiates the I O program, which consists of the following sequence: code segment 4, I O command fed back to the write call. After the first write call, the user program proceeds to code segment 2, followed by a second write call, which initiates the same sequence in the interrupt handler, which consists of a code segment 5, end. The user program concludes with code segment 3 and a third write call. A sequence of instructions, labeled 4 in the figure, to prepare for the actual I/O operation. This may include copying the data to be output into a special buffer and preparing the parameters for a device command. The actual I/O command. Without the use of interrupts, once this command is issued, the program must wait for the I/O device to perform the requested function (or periodically check the status of, or poll, the I/O device). The program might wait by simply repeatedly performing a test operation to determine if the I/O operation is done. A sequence of instructions, labeled 5 in the figure, to complete the operation. This may include setting a flag indicating the success or failure of the operation. The dashed line represents the path of execution followed by the processor; that is, this line shows the sequence in which instructions are executed. Thus, after the first WRITE instruction is encountered, the user program is interrupted and execution continues with the I/O program. After the I/O program execution is complete, execution resumes in the user program immediately following the WRITE instruction. Because the I/O operation may take a relatively long time to complete, the I/O program is hung up waiting for the operation to complete; hence, the user program is stopped at the point of the WRITE call for some considerable period of time. Interrupts and the Instruction Cycle With interrupts, the processor can be engaged in executing other instructions while anI/O operation is in progress. Consider the flow of control in Figure 1.5b. As before, the user program reaches a point at which it makes a system call in the form of a WRITE call. The I/O program that is invoked in this case consists only of the preparation code and the actual I/O command. After these few instructions have been executed, control returns to the user program. Meanwhile, the external device is busy accepting data from computer memory and printing it. This I/O operation is conducted concurrently with the execution of instructions in the user program. When the external device becomes ready to be serviced (that is, when it is ready to accept more data from the processor) the I/O module for that external device sends an interrupt request signal to the processor. The processor responds by suspending operation of the current program; branching off to a routine to service that particular I/O device (known as an interrupt handler); and resuming the original execution after the device is serviced. The points at which such interrupts occur are indicated by in Figure 1.5b. Note that an interrupt can occur at any point in the main program, not just at one specific instruction. For the user program, an interrupt suspends the normal sequence of execution. When the interrupt processing is completed, execution resumes (see Figure 1.6). Thus, the user program does not have to contain any special code to accommodate interrupts; the processor and the OS are responsible for suspending the user program, then resuming it at the same point. [image: The user program is partitioned from address 1 to address M. The interrupt occurs between addresses i and i + 1, where the program is accessed by the interrupt handler.] Figure 1.6 Transfer of Control via Interrupts To accommodate interrupts, an interrupt stage is added to the instruction cycle, as shown in Figure 1.7 (compare with Figure 1.2). In the interrupt stage, the processor checks to see if any interrupts have occurred, indicated by the presence of an interrupt signal. If no interrupts are pending, the processor proceeds to the fetch stage and fetches the next instruction of the current program. If an interrupt is pending, the processor suspends execution of the current program and executes an interrupt-handler routine. The interrupt-handler routine is generally part of the OS. Typically, this routine determines the nature of the interrupt and performs whatever actions are needed. In the example we have been using, the handler determines which I/O module generated the interrupt, and may branch to a program that will write more data out to that I/O module. When the interrupt-handler routine is completed, the processor can resume execution of the user program at the point of interruption. [image: A flow chart represents the instruction cycle.] Figure 1.7 Instruction Cycle with Interrupts Description The instructional cycle has the following main sequence: start, fetch next instruction, execute instruction, check for interrupt; initiate interrupt handler. The execute instruction also leads to halt. Interrupts can be enabled between executive instruction and check for interrupt. Interrupts can be disabled at execution of the instruction. From check for interrupt, loop extends back to start through interrupt, execute and fetch stages. It is clear that there is some overhead involved in this process. Extra instructions must be executed (in the interrupt handler) to determine the nature of the interrupt and to decide on the appropriate action. Nevertheless, because of the relatively large amount of time that would be wasted by simply waiting on an I/O operation, the processor can be employed much more efficiently with the use of interrupts. To appreciate the gain in efficiency, consider Figure 1.8, which is a timing diagram based on the flow of control in Figures 1.5a and 1.5b. Figures 1.5b and 1.8 assume that the time required for the I/O operation is relatively short: less than the time to complete the execution of instructions between write operations in the user program. The more typical case, especially for a slow device such as a printer, is that the I/O operation will take much more time than executing a sequence of user instructions. Figure 1.5c indicates this state of affairs. In this case, the user program reaches the second WRITE call before the I/O operation spawned by the first call is complete. The result is that the user program is hung up at that point. When the preceding I/O operation is completed, this new WRITE call may be processed, and a new I/O operation may be started. Figure 1.9 shows the timing for this situation with and without the use of interrupts. We can see there is still a gain in efficiency, because part of the time during which the I/O operation is underway overlaps with the execution of user instructions. [image: A diagram represents program timing with and without interrupts.] Figure 1.8 Program Timing: Short I/O Wait Description Part ay: without interrupts. Time flows from 1, 4, 5, 2, 4, 5, 3 with I/O operation and processor waiting between 4 and 5. Part b: with interrupts. Time flows from 1, 4, 2 a, 5, 2 b, 4, 3 a, 5, 3 b with I/O operation concurrent with processor executing at 2 ay and 5. [image: A diagram represents program timing with and without interrupts.] Figure 1.9 Program Timing: Long I/O Wait Description Part ay: without interrupts. Time flows from 1, 4, 5, 2, 4, 5, 3 with I/O operation and processor waiting between 4 and 5. Part b: with interrupts. Time flows from 1, 4, 2, 5, 4, 3, 5 with I/O operation concurrent with processor executing followed by the processor waiting from 2 to 5 and from 3 to 5. Interrupt Processing An interrupt triggers a number of events, both in the processor hardware and in software. Figure 1.10 shows a typical sequence. When an I/O device completes an I/O operation, the following sequence of hardware events occurs: [image: A diagram demonstrates interrupt processing.] Figure 1.10 Simple Interrupt Processing Description During processing, the hardware sequence is a followed by the software sequence. The hardware sequence is as follows: Device controller or other system hardware issues an interrupt. Processor finishes execution of current instruction. Processor signals acknowledgment of interrupt. Processor pushes PSW and PC onto control stack. Processor loads new PC value based on interrupt. The software sequence is as follows: Save remainder of process state information. Process interrupt. Restore process state information. Restore old P S W and P C. The device issues an interrupt signal to the processor. The processor finishes execution of the current instruction before responding to the interrupt, as indicated in Figure 1.7. The processor tests for a pending interrupt request, determines there is one, and sends an acknowledgment signal to the device that issued the interrupt. The acknowledgment allows the device to remove its interrupt signal. The processor next needs to prepare to transfer control to the interrupt routine. To begin, it saves information needed to resume the current program at the point of interrupt. The minimum information required is the program status word3 (PSW) and the location of the next instruction to be executed, which is contained in the program counter (PC). These can be pushed onto a control stack (see Appendix P). 3 The PSW contains status information about the currently running process, including memory usage information, condition codes, and other status information such as an interrupt enable/disable bit and a kernel/user-mode bit. See Appendix C for further discussion. The processor then loads the program counter with the entry location of the interrupt-handling routine that will respond to this interrupt. Depending on the computer architecture and OS design, there may be a single program, one for each type of interrupt, or one for each device and each type of interrupt. If there is more than one interrupt-handling routine, the processor must determine which one to invoke. This information may have been included in the original interrupt signal, or the processor may have to issue a request to the device that issued the interrupt to get a response that contains the needed information. Once the program counter has been loaded, the processor proceeds to the next instruction cycle, which begins with an instruction fetch. Because the instruction fetch is determined by the contents of the program counter, control is transferred to the interrupt-handler program. The execution of this program results in the following operations: At this point, the program counter and PSW relating to the interrupted program have been saved on the control stack. However, there is other information that is considered part of the state of the executing program. In particular, the contents of the processor registers need to be saved, because these registers may be used by the interrupt handler. So all of these values, plus any other state information, need to be saved. Typically, the interrupt handler will begin by saving the contents of all registers on the stack. Other state information that must be saved will be discussed in Chapter 3. Figure 1.11a shows a simple example. In this case, a user program is interrupted after the instruction at location N. The contents of all of the registers plus the address of the next instruction (N+1), a total of M words, are pushed onto the control stack. The stack pointer is updated to point to the new top of stack, and the program counter is updated to point to the beginning of the interrupt service routine. [image: A diagram represents change in memory and registers for an interrupt.] Figure 1.11 Changes in Memory and Registers for an Interrupt Description Part ay: Interrupt occurs after instruction at location N. The components of the main memory are as follows: control stack from T minus M to T with general registers in the middle; interrupt service routine from Start (Y) to Return (Y plus L); user's program including N and N plus 1. Input Y enters the program counter of the processor. The program counter then produces N + 1, which is entered into the control stack of the main memory. The general registers from the processor populate the control stack addresses after N + 1, and input T minus M produces T in the processor's stack pointer. Part b: return from interrupt. N + 1 in the control stack of the main memory yields Y + L + 1 in the program counter, and the general registers are transferred back from the main memory to the processor. In addition, input T yields T minus M in the stack pointer. The interrupt handler may now proceed to process the interrupt. This includes an examination of status information relating to the I/O operation or other event that caused an interrupt. It may also involve sending additional commands or acknowledgments to the I/O device. When interrupt processing is complete, the saved register values are retrieved from the stack and restored to the registers (see Figure 1.11b). The final act is to restore the PSW and program counter values from the stack. As a result, the next instruction to be executed will be from the previously interrupted program. It is important to save all of the state information about the interrupted program for later resumption. This is because the interrupt is not a routine called from the program. Rather, the interrupt can occur at any time, and therefore at any point in the execution of a user program. Its occurrence is unpredictable. Multiple Interrupts So far, we have discussed the occurrence of a single interrupt. Suppose, however, that one or more interrupts can occur while an interrupt is being processed. For example, a program may be receiving data from a communications line, and printing results at the same time. The printer will generate an interrupt every time it completes a print operation. The communication line controller will generate an interrupt every time a unit of data arrives. The unit could either be a single character or a block, depending on the nature of the communications discipline. In any case, it is possible for a communications interrupt to occur while a printer interrupt is being processed. Two approaches can be taken to dealing with multiple interrupts. The first is to disable interrupts while an interrupt is being processed. A disabled interrupt simply means the processor ignores any new interrupt request signal. If an interrupt occurs during this time, it generally remains pending and will be checked by the processor after the processor has reenabled interrupts. Thus, if an interrupt occurs when a user program is executing, then interrupts are disabled immediately. After the interrupt-handler routine completes, interrupts are reenabled before resuming the user program, and the processor checks to see if additional interrupts have occurred. This approach is simple, as interrupts are handled in strict sequential order (see Figure 1.12a). [image: A diagram represents transfer of control.] Figure 1.12 Transfer of Control with Multiple Interrupts Description Part ay: Sequential interrupt processing. The user program transfers control to interrupt handler X and Y, which then pass control back to the user program. Part B: Nested interrupt processing. The user program passes control to interrupt handler X that passes control back to user program. Interrupt handler X passes control to interrupt handler Y that passes control back to user program. The drawback to the preceding approach is that it does not take into account relative priority or time-critical needs. For example, when input arrives from the communications line, it may need to be absorbed rapidly to make room for more input. If the first batch of input has not been processed before the second batch arrives, data may be lost because the buffer on the I/O device may fill and overflow. A second approach is to define priorities for interrupts and to allow an interrupt of higher priority to cause a lower-priority interrupt handler to be interrupted (see Figure 1.12b). As an example of this second approach, consider a system with three I/O devices: a printer, a disk, and a communications line, with increasing priorities of 2, 4, and 5, respectively. Figure 1.13 illustrates a possible sequence. A user program begins at t=0. At t=10, a printer interrupt occurs; user information is placed on the control stack and execution continues at the printer interrupt service routine (ISR). While this routine is still executing, at t=15 a communications interrupt occurs. Because the communications line has higher priority than the printer, the interrupt request is honored. The printer ISR is interrupted, its state is pushed onto the stack, and execution continues at the communications ISR. While this routine is executing, a disk interrupt occurs (t=20). Because this interrupt is of lower priority, it is simply held, and the communications ISR runs to completion. [image: A diagram shows an example time sequence.] Figure 1.13 Example Time Sequence of Multiple Interrupts Description A diagram of a user program at t = 0 passes control at t = 10 to printer interrupt service routine which passes control back to the user program at t = 40. It then passes control to the communication interrupt service routine with t = 15 which then passes back to the printer interrupt service at t = 25. It passes control to the disk interrupt service routine at t = 25 which in turn passes control back to the printer interrupt service routine at t = 35. When the communications ISR is complete (t=25), the previous processor state is restored, which is the execution of the printer ISR. However, before even a single instruction in that routine can be executed, the processor honors the higher-priority disk interrupt and transfers control to the disk ISR. Only when that routine is complete (t=35) is the printer ISR resumed. When that routine completes (t=40), control finally returns to the user program. 1.5 THE MEMORY HIERARCHY The design constraints on a computer's memory can be summed up by three questions: How much? How fast? How expensive? The question of how much is somewhat open-ended. If the capacity is there, applications will likely be developed to use it. The question of how fast is, in a sense, easier to answer. To achieve greatest performance, the memory must be able to keep up with the processor. That is, as the processor is executing instructions, we would not want it to have to pause waiting for instructions or operands. The final question must also be considered. For a practical system, the cost of memory must be reasonable in relationship to other components. As might be expected, there is a trade-off among the three key characteristics of memory: capacity, access time, and cost. A variety of technologies are used to implement memory systems, and across this spectrum of technologies, the following relationships hold: Faster access time, greater cost per bit Greater capacity, smaller cost per bit Greater capacity, slower access speed The dilemma facing the designer is clear. The designer would like to use memory technologies that provide for large-capacity memory, both because the capacity is needed and because the cost per bit is low. However, to meet performance requirements, the designer needs to use expensive, relatively lower-capacity memories with fast access times. The way out of this dilemma is to not rely on a single memory component or technology, but to employ a memory hierarchy. A typical hierarchy is illustrated in Figure 1.14. As one goes down the hierarchy, the following occur: [image: A pyramid represents the memory hierarchy.] Figure 1.14 The Memory Hierarchy Description The pyramid is divided into three levels described from bottom to top. Level 1: off-line storage in the form of magnetic tape. Level 2: outboard storage in the form of magnetic disk, C D ROM, C D R W, D V D R W, D V D RAM, and blue ray. Level 3: inboard memory in the form of main memory, cache, and registers from bottom to top. Decreasing cost per bit Increasing capacity Increasing access time Decreasing frequency of access to the memory by the processor Thus, smaller, more expensive, faster memories are supplemented by larger, cheaper, slower memories. The key to the success of this organization is the decreasing frequency of access at lower levels. We will examine this concept in greater detail later in this chapter when we discuss the cache, and when we discuss virtual memory later in this book. A brief explanation is provided at this point. Suppose the processor has access to two levels of memory. Level 1 contains 1000 bytes and has an access time of 0.1 μs; level 2 contains 100,000 bytes and has an access time of 1 μs. Assume that if a byte to be accessed is in level 1, then the processor accesses it directly. If it is in level 2, the byte is first transferred to level 1, then accessed by the processor. For simplicity, we ignore the time required for the processor to determine whether the byte is in level 1 or level 2. Figure 1.15 shows the general shape of the curve that models this situation. The figure shows the average access time to a two-level memory as a function of the hit ratio H, where H is defined as the fraction of all memory accesses that are found in the faster memory (e.g., the cache), T1 is the access time to level 1, and T2 is the access time to level 2.4 As can be seen, for high percentages of level 1 access, the average total access time is much closer to that of level 1 than that of level 2. 4 If the accessed word is found in the faster memory, that is defined as a hit. A miss occurs if the accessed word is not found in the faster memory. Figure 1.15 Performance of a Simple Two-Level Memory [image: The graph plots average access time versus fraction of accesses involving only level 1, or the hit ration. The plot falls diagonally from (0, T sub 1 + T sub 2) to (1, T sub 1).] In our example, suppose 95% of the memory accesses are found in the cache (H=0.95). Then, the average time to access a byte can be expressed as (0.95)(0.1 μs)+(0.05)(0.1 μs+1 μs)=0.095+0.055=0.15 μs The result is close to the access time of the faster memory. So the strategy of using two memory levels works in principle, but only if conditions (a) through (d) in the preceding list apply. By employing a variety of technologies, a spectrum of memory systems exists that satisfies conditions (a) through (c). Fortunately, condition (d) is also generally valid. The basis for the validity of condition (d) is a principle known as locality of reference [DENN68]. During the course of execution of a program, memory references by the processor, for both instructions and data, tend to cluster. Programs typically contain a number of iterative loops and subroutines. Once a loop or subroutine is entered, there are repeated references to a small set of instructions. Similarly, operations on tables and arrays involve access to a clustered set of data bytes. Over a long period of time, the clusters in use change, but over a short period of time, the processor is primarily working with fixed clusters of memory references. Accordingly, it is possible to organize data across the hierarchy such that the percentage of accesses to each successively lower level is substantially less than that of the level above. Consider the two-level example already presented. Let level 2 memory contain all program instructions and data. The current clusters can be temporarily placed in level 1. From time to time, one of the clusters in level 1 will have to be swapped back to level 2 to make room for a new cluster coming in to level 1. On average, however, most references will be to instructions and data contained in level 1. This principle can be applied across more than two levels of memory. The fastest, smallest, and most expensive type of memory consists of the registers internal to the processor. Typically, a processor will contain a few dozen such registers, although some processors contain hundreds of registers. Skipping down two levels, main memory is the principal internal memory system of the computer. Each location in main memory has a unique address, and most machine instructions refer to one or more main memory addresses. Main memory is usually extended with a higher-speed, smaller cache. The cache is not usually visible to the programmer or, indeed, to the processor. It is a device for staging the movement of data between main memory and processor registers to improve performance. The three forms of memory just described are typically volatile and employ semiconductor technology. The use of three levels exploits the fact that semiconductor memory comes in a variety of types, which differ in speed and cost. Data are stored more permanently on external mass storage devices, of which the most common are hard disk and removable media, such as removable disk, tape, and optical storage. External, nonvolatile memory is also referred to as secondary memory or auxiliary memory. These are used to store program and data files, and are usually visible to the programmer only in terms of files and records, as opposed to individual bytes or words. A hard disk is also used to provide an extension to main memory known as virtual memory, which will be discussed in Chapter 8. Additional levels can be effectively added to the hierarchy in software. For example, a portion of main memory can be used as a buffer to temporarily hold data that are to be read out to disk. Such a technique, sometimes referred to as a disk cache (to be examined in detail in Chapter 11), improves performance in two ways: Disk writes are clustered. Instead of many small transfers of data, we have a few large transfers of data. This improves disk performance and minimizes processor involvement. Some data destined for write-out may be referenced by a program before the next dump to disk. In that case, the data are retrieved rapidly from the software cache rather than slowly from the disk. Appendix 1A examines the performance implications of multilevel memory structures. 1.6 CACHE MEMORY Although cache memory is invisible to the OS, it interacts with other memory management hardware. Furthermore, many of the principles used in virtual memory schemes (to be discussed in Chapter 8) are also applied in cache memory. Motivation On all instruction cycles, the processor accesses memory at least once, to fetch the instruction, and often one or more additional times, to fetch operands and/or store results. The rate at which the processor can execute instructions is clearly limited by the memory cycle time (the time it takes to read one word from or write one word to memory). This limitation has been a significant problem because of the persistent mismatch between processor and main memory speeds. Over the years, processor speed has consistently increased more rapidly than memory access speed. We are faced with a trade-off among speed, cost, and size. Ideally, main memory should be built with the same technology as that of the processor registers, giving memory cycle times comparable to processor cycle times. This has always been too expensive a strategy. The solution is to exploit the principle of locality by providing a small, fast memory between the processor and main memory, namely the cache. Cache Principles Cache memory is intended to provide memory access time approaching that of the fastest memories available, and at the same time support a large memory size that has the price of less expensive types of semiconductor memories. The concept is illustrated in Figure 1.16a. There is a relatively large and slow main memory together with a smaller, faster cache memory. The cache contains a copy of a portion of main memory. When the processor attempts to read a byte or word of memory, a check is made to determine if the byte or word is in the cache. If so, the byte or word is delivered to the processor. If not, a block of main memory, consisting of some fixed number of bytes, is read into the cache then the byte or word is delivered to the processor. Because of the phenomenon of locality of reference, when a block of data is fetched into the cache to satisfy a single memory reference, it is likely that many of the near-future memory references will be to other bytes in the block. [image: A diagram represents time-level cache organization.] Figure 1.16 Cache and Main Memory Description Part ay: Single cache consists of Word transfer, which is the fast connection between the C P U and Cache and back again. Block transfer is the slow connection between the main memory and cache. Part B: Three-level cache organization consists of the fastest connection between a C P U and Level 1, or L 1, cache and back again; the fast connection between level 1, or L 1 and level 2, or L 2, caches; the less fast connection between L 2 and L 3caches; and the slow connection between L 3 and main memory. Figure 1.16b depicts the use of multiple levels of cache. The L2 cache is slower and typically larger than the L1 cache, and the L3 cache is slower and typically larger than the L2 cache. Figure 1.17 depicts the structure of a cache/main memory system. Main memory consists of up to 2n addressable words, with each word having a unique n-bit address. For mapping purposes, this memory is considered to consist of a number of fixed-length blocks of K words each. That is, there are M=2n/K blocks. Cache consists of C slots (also referred to as lines) of K words each, and the number of slots is considerably less than the number of main memory blocks (C <> M).5 Some subset of the blocks of main memory resides in the slots of the cache. If a word in a block of memory that is not in the cache is read, that block is transferred to one of the slots of the cache. Because there are more blocks than slots, an individual slot cannot be uniquely and permanently dedicated to a particular block. Therefore, each slot includes a tag that identifies which particular block is currently being stored. The tag is usually some number of higher-order bits of the address, and refers to all addresses that begin with that sequence of bits. 5 The symbol << means much less than. Similarly, the symbol >> means much greater than. [image: A diagram shows the cache and main memory structure.] Figure 1.17 Cache/Main Memory Structure Description Part ay: Cache. The block from top to bottom has line numbers from 0 to C minus 1, and block length k words. Part b: Main memory. The memory stack from top to bottom has memory addresses 0 to 2 sup n minus 1. Top block 0 is k words. Bottom block is M minus 1. As a simple example, suppose we have a 6-bit address and a 2-bit tag. The tag 01 refers to the block of locations with the following addresses: 010000, 010001, 010010, 010011, 010100, 010101, 010110, 010111, 011000, 011001, 011010, 011011, 011100, 011101, 011110, 011111. Figure 1.18 illustrates the read operation. The processor generates the address, RA, of a word to be read. If the word is contained in the cache, it is delivered to the processor. Otherwise, the block containing that word is loaded into the cache, and the word is delivered to the processor. [image: A flow chart demonstrates the cache read operation.] Figure 1.18 Cache Read Operation Description The process begins with receipt of the read address, or R Ay, from the C P U. The system then asks, if the block containing the R Ay in the cache? If no, then the system accesses the main memory for the block containing the R Ay, then allocates a cache slot for the main memory block. The main memory block is then loaded into the cache slot, and the system delivers the R Ay word to the C P U before finishing. On the other hand, if the block containing the R Ay is in the cache, then the system fetches the R Ay word and delivers it to the C P U before finishing. Cache Design A detailed discussion of cache design is beyond the scope of this book. Key elements are briefly summarized here. We will see that similar design issues must be addressed in dealing with virtual memory and disk cache design. They fall into the following categories: Cache size Block size Mapping function Replacement algorithm Write policy Number of cache levels We have already dealt with the issue of cache size. It turns out that reasonably small caches can have a significant impact on performance. Another size issue is that of block size: the unit of data exchanged between cache and main memory. Consider beginning with a relatively small block size, then increasing the size. As the block size increases, more useful data are brought into the cache with each block transfer. The result will be that the hit ratio increases because of the principle of locality: the high probability that data in the vicinity of a referenced word are likely to be referenced in the near future. The hit ratio will begin to decrease, however, as the block becomes even bigger, and the probability of using the newly fetched data becomes less than the probability of reusing the data that have to be moved out of the cache to make room for the new block. When a new block of data is read into the cache, the mapping function determines which cache location the block will occupy. Two constraints affect the design of the mapping function. First, when one block is read in, another may have to be replaced. We would like to do this in such a way as to minimize the probability that we will replace a block that will be needed in the near future. The more flexible the mapping function, the more scope we have to design a replacement algorithm to maximize the hit ratio. Second, the more flexible the mapping function, the more complex is the circuitry required to search the cache to determine if a given block is in the cache. The replacement algorithm chooses (within the constraints of the mapping function) which block to replace when a new block is to be loaded into the cache and the cache already has all slots filled with other blocks. We would like to replace the block that is least likely to be needed again in the near future. Although it is impossible to identify such a block, a reasonably effective strategy is to replace the block that has been in the cache longest with no reference to it. This policy is referred to as the least-recently-used (LRU) algorithm. Hardware mechanisms are needed to identify the least-recently-used block. If the contents of a block in the cache are altered, then it is necessary to write it back to main memory before replacing it. The write policy dictates when the memory write operation takes place. At one extreme, the writing can occur every time that the block is updated. At the other extreme, the writing occurs only when the block is replaced. The latter policy minimizes memory write operations, but leaves main memory in an obsolete state. This can interfere with multiple-processor operation, and with direct memory access by I/O hardware modules. Finally, it is now commonplace to have multiple levels of cache, labeled L1 (cache closest to the processor), L2, and in many cases L3. A discussion of the performance benefits of multiple cache levels is beyond our current scope (see [STAL16a] for a discussion). 1.7 DIRECT MEMORY ACCESS Three techniques are possible for I/O operations: programmed I/O, interrupt-driven I/O, and direct memory access (DMA). Before discussing DMA, we will briefly define the other two techniques; see Appendix C for more detail. When the processor is executing a program and encounters an instruction relating to I/O, it executes that instruction by issuing a command to the appropriate I/O module. In the case of programmed I/O, the I/O module performs the requested action, then sets the appropriate bits in the I/O status register but takes no further action to alert the processor. In particular, it does not interrupt the processor. Thus, after the I/O instruction is invoked, the processor must take some active role in determining when the I/O instruction is completed. For this purpose, the processor periodically checks the status of the I/O module until it finds that the operation is complete. With programmed I/O, the processor has to wait a long time for the I/O module of concern to be ready for either reception or transmission of more data. The processor, while waiting, must repeatedly interrogate the status of the I/O module. As a result, the performance level of the entire system is severely degraded. An alternative, known as interrupt-driven I/O, is for the processor to issue an I/O command to a module then go on to do some other useful work. The I/O module will then interrupt the processor to request service when it is ready to exchange data with the processor. The processor then executes the data transfer, as before, and resumes its former processing. Interrupt-driven I/O, though more efficient than simple programmed I/O, still requires the active intervention of the processor to transfer data between memory and an I/O module, and any data transfer must traverse a path through the processor. Thus, both of these forms of I/O suffer from two inherent drawbacks: The I/O transfer rate is limited by the speed with which the processor can test and service a device. The processor is tied up in managing an I/O transfer; a number of instructions must be executed for each I/O transfer. When large volumes of data are to be moved, a more efficient technique is required: direct memory access (DMA). The DMA function can be performed by a separate module on the system bus, or it can be incorporated into an I/O module. In either case, the technique works as follows. When the processor wishes to read or write a block of data, it issues a command to the DMA module by sending the following information: Whether a read or write is requested The address of the I/O device involved The starting location in memory to read data from or write data to The number of words to be read or written The processor then continues with other work. It has delegated this I/O operation to the DMA module, and that module will take care of it. The DMA module transfers the entire block of data, one word at a time, directly to or from memory without going through the processor. When the transfer is complete, the DMA module sends an interrupt signal to the processor. Thus, the processor is involved only at the beginning and end of the transfer. The DMA module needs to take control of the bus to transfer data to and from memory. Because of this competition for bus usage, there may be times when the processor needs the bus and must wait for the DMA module. Note this is not an interrupt; the processor does not save a context and do something else. Rather, the processor pauses for one bus cycle (the time it takes to transfer one word across the bus). The overall effect is to cause the processor to execute more slowly during a DMA transfer when processor access to the bus is required. Nevertheless, for a multiple-word I/O transfer, DMA is far more efficient than interrupt-driven or programmed I/O. 1.8 MULTIPROCESSOR AND MULTICORE ORGANIZATION Traditionally, the computer has been viewed as a sequential machine. Most computer programming languages require the programmer to specify algorithms as sequences of instructions. A processor executes programs by executing machine instructions in sequence and one at a time. Each instruction is executed in a sequence of operations (fetch instruction, fetch operands, perform operation, store results). This view of the computer has never been entirely true. At the micro-operation level, multiple control signals are generated at the same time. Instruction pipelining, at least to the extent of overlapping fetch and execute operations, has been around for a long time. Both of these are examples of performing functions in parallel. As computer technology has evolved