`
`OPERATING
`SYSTEMS
`
`Internals and Design Principles
`
`
`
`VViiliarn Stallinffi
`
`Patent Owner, Bot M8 LLC - Ex. 2014, p. 1
`
`

`

`This page intentionally left blank
`
`Patent Owner, Bot M8 LLC - Ex. 2014, p. 2
`
`

`

`OPERATING SYSTEMS
`INTERNALS AND DESIGN
`PRINCIPLES
`SEVENTH EDITION
`
`William Stallings
`
` Prentice Hall
` Boston Columbus Indianapolis New York San Francisco Upper Saddle River
` Amsterdam Cape Town Dubai London Madrid Milan Munich Paris Montreal Toronto
` Delhi Mexico City São Paulo Sydney Hong Kong Seoul Singapore Taipei Tokyo
`
`Patent Owner, Bot M8 LLC - Ex. 2014, p. 3
`
`

`

` Editorial Director: Marcia Horton
` Editor in Chief: Michael Hirsch
` Executive Editor: Tracy Dunkelberger
` Assistant Editor: Melinda Haggerty
` Editorial Assistant: Allison Michael
` Director of Marketing: Patrice Jones
` Marketing Manager: Yezan Alayan
` SenioMarketing Coordinator: Kathryn Ferranti
` Production Manager: Pat Brown
`
` Art Director: Jayne Conte
` Cover Designer: Bruce Kenselaar
` Media Director: Daniel Sandin
` Media Project Manager: Wanda Rockwell
` Full-Service Project Management/Composition:
` Shiny Rajesh/Integra Software Service Pvt. Ltd.
` Interior Printer/Bindery: Edwards Brothers
` Cover Printer: Lehigh-Phoenix Color
`
` Credits and acknowledgments borrowed from other sources and reproduced, with permission, in this textbook appear on
`appropriate page within text.
`
` Microsoft® and Windows® are registered trademarks of the Microsoft Corporation in the U.S.A. and other countries. Screen
`shots and icons reprinted with permission from the Microsoft Corporation. This book is not sponsored or endorsed by or
`affi liated with the Microsoft Corporation.
`
` Copyright © 2012, 2009, 2005, 2001, 1998 Pearson Education, Inc., publishing as Prentice Hall, 1 Lake Street,
`Upper Saddle River, New Jersey, 07458. 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, 1 Lake Street, Upper Saddle River, New Jersey, 07458.
`
` Many of the designations by manufacturers and sellers 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
`
`Stallings, William.
`Operating systems : internals and design principles / William Stallings. — 7th ed.
`
` p. cm.
`
`Includes bibliographical references and index.
`
`ISBN-13: 978-0-13-230998-1 (alk. paper)
`
`ISBN-10: 0-13-230998-X (alk. paper)
` 1. Operating systems (Computers)
`I. Title.
`QA76.76.O63S733 2011
`005.4'3 dc22
`
`
`2010048597
`
` 10 9 8 7 6 5 4 3 2 1—EB—15 14 13 12 11
`
` ISBN 10: 0-13-230998-X
` ISBN 13: 978-0-13-230998-1
`
`Patent Owner, Bot M8 LLC - Ex. 2014, p. 4
`
`

`

`To my brilliant and brave wife,
`Antigone Tricia, who has survived
`the worst horrors imaginable.
`
`Patent Owner, Bot M8 LLC - Ex. 2014, p. 5
`
`

`

`CONTENTS
`
`Online Resources x
`Preface xi
`About the Author xix
`
`Chapter 0 Reader’s and Instructor’s
`Guide 1
`Outline of this Book 2
`Example Systems 2
`A Roadmap for Readers and
`Instructors 3
`Internet and Web Resources 4
`
`0.1
`0.2
`0.3
`
`0.4
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`2.6
`
`2.7
`2.8
`2.9
`2.10
`2.11
`
`OS Design Considerations for
`Multiprocessor and Multicore 77
`Microsoft Windows Overview 80
`Traditional UNIX Systems 90
`Modern UNIX Systems 92
`Linux 94
`Linux VServer Virtual Machine
`Architecture 100
`2.12 Recommended Reading and Web
`Sites 101
`Key Terms, Review Questions, and
`Problems 103
`
`2.13
`
`PART 1 BACKGROUND 7
`Chapter 1 Computer System
`Overview 7
`Basic Elements 8
`Evolution of the
`Microprocessor 10
`Instruction Execution 11
`Interrupts 14
`The Memory Hierarchy 24
`Cache Memory 27
`Direct Memory Access 31
`Multiprocessor and Multicore
`Organization 33
`Recommended Reading and
`Web Sites 36
`Key Terms, Review Questions,
`and Problems 37
`Performance Characteristics of
`Two-Level Memories 39
`Chapter 2 Operating System
`Overview 46
`Operating System Objectives and
`Functions 48
`The Evolution of Operating
`Systems 52
`Major Achievements 62
`Developments Leading to Modern
`Operating Systems 71
`Virtual Machines 74
`
`1.1
`1.2
`
`1.3
`1.4
`1.5
`1.6
`1.7
`1.8
`
`1.9
`
`1.10
`
`1A
`
`2.1
`
`2.2
`
`2.3
`2.4
`
`2.5
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`iv
`
`PART 2 PROCESSES 106
`Chapter 3 Process Description and
`Control 106
`What Is a Process? 108
`Process States 110
`Process Description 126
`Process Control 134
`Execution of the Operating
`System 140
`Security Issues 143
`UNIX SVR4 Process
`Management 147
`Summary 152
`Recommended Reading 152
`Key Terms, Review Questions, and
`Problems 153
`Chapter 4 Threads 157
`Processes and Threads 158
`
`4.1
`Types of Threads 164
`
`4.2
`Multicore and Multithreading 171
`
`4.3
`Windows 7 Thread and SMP
`
`4.4
`Management 176
`Solaris Thread and SMP
`Management 182
`Linux Process and Thread
`Management 186
`Mac OS X Grand Central
`Dispatch 189
`
`3.1
`3.2
`3.3
`3.4
`3.5
`
`3.6
`3.7
`
`3.8
`3.9
`3.10
`
`4.5
`
`4.6
`
`4.7
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Patent Owner, Bot M8 LLC - Ex. 2014, p. 6
`
`

`

`4.8
`4.9
`4.10
`
`5.1
`5.2
`
`6.1
`6.2
`6.3
`6.4
`6.5
`
`6.6
`6.7
`
`6.8
`
`6.9
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`5.3
`5.4
`5.5
`5.6
`5.7
`5.8
`5.9
`
`Summary 192
`Recommended Reading 192
`Key Terms, Review Questions, and
`Problems 193
`Chapter 5 Concurrency: Mutual Exclu-
`sion and Synchronization 198
`Principles of Concurrency 201
`Mutual Exclusion: Hardware
`Support 209
`Semaphores 213
`Monitors 226
`Message Passing 233
`Readers/Writers Problem 239
`Summary 243
`Recommended Reading 244
`Key Terms, Review Questions,
`and Problems 245
`Chapter 6 Concurrency: Deadlock and
`Starvation 258
`Principles of Deadlock 259
`Deadlock Prevention 268
`Deadlock Avoidance 270
`Deadlock Detection 276
`An Integrated Deadlock
`Strategy 278
`Dining Philosophers Problem 279
`UNIX Concurrency
`Mechanisms 281
`Linux Kernel Concurrency
`Mechanisms 285
`Solaris Thread Synchronization
`Primitives 292
`6.10 Windows 7 Concurrency
`Mechanisms 294
`Summary 298
`6.11
`6.12 Recommended Reading 298
`Key Terms, Review Questions,
`6.13
`and Problems 299
`
`CONTENTS v
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`7.3
`7.4
`7.5
`7.6
`7.7
`7.8
`
`8.2
`8.3
`
`8.4
`8.5
`
`8.6
`8.7
`
`8.8
`
`Paging 321
`Segmentation 325
`Security Issues 326
`Summary 330
`Recommended Reading 330
`Key Terms, Review Questions, and
`Problems 331
`Loading and Linking 334
`7A
`
`Chapter 8 Virtual Memory 340
`Hardware and Control
`
`8.1
`Structures 341
`Operating System Software 360
`UNIX and Solaris Memory
`Management 379
`Linux Memory Management 384
`Windows Memory
`Management 386
`Summary 389
`Recommended Reading and Web
`Sites 390
`Key Terms, Review Questions,
`and Problems 391
`
`PART 4 SCHEDULING 395
`Chapter 9 Uniprocessor Scheduling 395
`Types of Processor Scheduling 396
`
`9.1
`Scheduling Algorithms 400
`
`9.2
`Traditional UNIX
`
`9.3
`Scheduling 422
`Summary 424
`Recommended Reading 425
`Key Terms, Review Questions,
`and Problems 426
`Chapter 10 Multiprocessor and Real-Time
`Scheduling 430
`10.1 Multiprocessor Scheduling 431
`10.2 Real-Time Scheduling 442
`Linux Scheduling 457
`10.3
`10.4 UNIX SVR4 Scheduling 461
`10.5 UNIX FreeBSD Scheduling 463
`10.6 Windows Scheduling 466
`Linux Virtual Machine Process
`10.7
`Scheduling 468
`Summary 469
`
`9.4
`9.5
`9.6
`
`10.8
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`PART 3 MEMORY 305
`Chapter 7 Memory Management 305
`Memory Management
`
`7.1
`Requirements 307
`Memory Partitioning 310
`
`7.2
`
`
`
`Patent Owner, Bot M8 LLC - Ex. 2014, p. 7
`
`

`

`vi CONTENTS
`
`
`
`
`10.9 Recommended Reading 470
`10.10 Key Terms, Review Questions, and
`Problems 471
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`PART 5 INPUT/OUTPUT AND
`FILES 474
`Chapter 11 I/O Management and Disk
`Scheduling 474
`I/O Devices 475
`11.1
`11.2 Organization of the I/O
`Function 477
`11.3 Operating System Design Issues 480
`I/O Buffering 483
`11.4
`11.5 Disk Scheduling 487
`11.6 RAID 494
`11.7 Disk Cache 502
`11.8 UNIX SVR4 I/O 506
`Linux I/O 509
`11.9
`11.10 Windows I/O 512
`Summary 515
`11.11
`11.12 Recommended Reading 516
`11.13 Key Terms, Review Questions, and
`Problems 517
`Chapter 12 File Management 520
`12.1 Overview 522
`
`File Organization and Access 527
`
`12.2
`B-Trees 532
`
`12.3
`File Directories 535
`
`12.4
`File Sharing 540
`
`12.5
`12.6 Record Blocking 541
`
`Secondary Storage
`
`12.7
`Management 543
`File System Security 551
`12.8
`12.9 UNIX File Management 553
`12.10 Linux Virtual File System 560
`12.11 Windows File System 564
`Summary 569
`12.12
`12.13 Recommended Reading 570
`12.14 Key Terms, Review Questions, and
`Problems 571
`
`
`
`
`
`
`
`
`
`PART 6 EMBEDDED SYSTEMS 573
`Chapter 13 Embedded Operating
`Systems 573
`Embedded Systems 574
`Characteristics of Embedded
`
`13.1
`13.2
`
`
`
`
`
`
`
`
`
`
`Operating Systems 576
`eCos 579
`13.3
`TinyOS 594
`13.4
`13.5 Recommended Reading and
`Web Sites 603
`Key Terms, Review Questions,
`and Problems 604
`
`13.6
`
`PART 7 COMPUTER SECURITY 607
`Chapter 14 Computer Security
`Threats 607
`Computer Security
`Concepts 608
`Threats, Attacks, and Assets 610
`14.2
`Intruders 616
`14.3
`14.4 Malicious Software
`Overview 619
`Viruses, Worms, and Bots 623
`14.5
`14.6 Rootkits 633
`14.7 Recommended Reading and
`Web Sites 635
`Key Terms, Review Questions,
`and Problems 636
`Chapter 15 Computer Security
`Techniques 639
`Authentication 640
`15.1
`Access Control 646
`15.2
`Intrusion Detection 653
`15.3
`15.4 Malware Defense 657
`15.5 Dealing with Buffer Overfl ow
`Attacks 663
`15.6 Windows 7 Security 667
`15.7 Recommended Reading and
`Web Sites 672
`Key Terms, Review Questions,
`and Problems 674
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`14.1
`
`14.8
`
`15.8
`
`16.1
`16.2
`
`PART 8 DISTRIBUTED SYSTEMS 677
`Chapter 16 Distributed Processing, Client/
`Server, and Clusters 677
`Client/Server Computing 678
`Service-Oriented
`Architecture 689
`16.3 Distributed Message Passing 691
`16.4 Remote Procedure Calls 695
`Clusters 699
`16.5
`
`
`
`
`
`
`
`
`Patent Owner, Bot M8 LLC - Ex. 2014, p. 8
`
`

`

`
`
`
`
`
`
`
`16.6 Windows Cluster Server 704
`Beowulf and Linux Clusters 706
`16.7
`Summary 708
`16.8
`16.9 Recommended Reading and Web
`Sites 709
`16.10 Key Terms, Review Questions, and
`Problems 710
`
`APPENDICES
`Appendix A Topics in Concurrency A-1
` A.1 Mutual Exclusion: Software
`Approaches A-2
`Race Conditions and
`Semaphores A-8
`A Barbershop Problem A-15
`Problems A-21
`
` A.3
` A.4
`
` A.2
`
`CONTENTS vii
`
`
`
`
`
`
`
`B.1
`B.2
`B.3
`B.4
`B.5
`
`Appendix B Programming and Operating
`System Projects B-1
`OS/161 B-2
`Simulations B-3
`Programming Projects B-4
`Research Projects B-6
`Reading/Report
`Assignments B-6
`B.6 Writing Assignments B-6
`
`Discussion Topics B-7
`B.7
`
`BACI B-7
`B.8
`
`Glossary 713
`
`References 723
`
`Index 743
`
`Patent Owner, Bot M8 LLC - Ex. 2014, p. 9
`
`

`

`ONLINE CHAPTERS AND APPENDICES1
`
`17.2
`
`17.7
`
`17A
`
`19.5
`
`Chapter 17 Network Protocols 17-1
`The Need for a Protocol
`
`17.1
`Architecture 17-3
`The TCP/IP Protocol
`Architecture 17-6
`Sockets 17-15
`17.3
`Linux Networking 17-21
`17.4
`Summary 17-22
`17.5
`17.6 Recommended Reading and Web
`Sites 17-23
`Key Terms, Review Questions, and
`Problems 17-24
`The Trivial File Transfer
`Protocol 17-28
`Chapter 18 Distributed Process
`Management 18-1
`Process Migration 18-2
`18.1
`18.2 Distributed Global States 18-10
`18.3 Distributed Mutual
`Exclusion 18-16
`18.4 Distributed Deadlock 18-30
`Summary 18-44
`18.5
`18.6 Recommended Reading 18-45
`Key Terms, Review Questions, and
`18.7
`Problems 18-46
`Chapter 19 Overview of Probability
`and Stochastic Processes 19-1
`Probability 19-2
`19.1
`19.2 Random Variables 19-8
`Elementary Concepts of Stochas-
`19.3
`tic Processes 19-14
`19.4 Recommended Reading and Web
`Sites 19-26
`Key Terms, Review Questions, and
`Problems 19-27
`Chapter 20 Queueing Analysis 20-1
`20.1 How Queues Behave—A Simple
`
`Example 20-3
`20.2 Why Queueing Analysis? 20-8
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`20.3 Queueing Models 20-10
`Single-Server Queues 20-20
`20.4
`20.5 Multiserver Queues 20-22
`Examples 20-24
`20.6
`20.7 Queues with Priorities 20-30
`20.8 Networks of Queues 20-32
`20.9 Other Queueing Models 20-37
`20.10 Estimating Model
`Parameters 20-38
`20.11 Recommended Reading and Web
`Sites 20-42
`20.12 Key Terms, Review Questions, and
`Problems 20-43
`Programming Project One
`a Shell
`
` Developing
`
`Programming Project Two The HOST
`Dispatcher Shell
`
` C.1
` C.2
`
` C.3
`
` C.4
`
`Appendix C Topics in Computer
`Organization C-1
`Processor Registers C-2
`Instruction Execution for I/O
`Instructions C-6
`I/O Communication
`Techniques C-7
`Hardware Performance
`Issues for Multicore
`Organization C-12
`Appendix D
` Object-Oriented
`Design D-1
` D.1 Motivation D-2
`Object-Oriented Concepts D-4
` D.2
`Benefi ts of Object-Oriented
` D.3
`Design D-9
`CORBA D-11
`Recommended Reading and
`Web Site D-17
`Appendix E Amdahl’s Law E-1
`
` D.4
` D.5
`
`Appendix F
`
` Hash Tables F-1
`
`1 Online chapters, appendices, and other documents are Premium Content, available via the access card
`at the front of this book.
`
`viii
`
`Patent Owner, Bot M8 LLC - Ex. 2014, p. 10
`
`

`

`Appendix G
`
` Response Time G-1
`
` Queueing System
`Appendix H
`Concepts H-1
`The Single-Server Queue H-2
`The Multiserver Queue H-4
`Poisson Arrival Rate H-7
`
` H.1
` H.2
` H.3
`
`Appendix I The Complexity of
`Algorithms I-1
`
` Disk Storage Devices J-1
`Appendix J
`Magnetic Disk J-2
`
`J.1
`Optical Memory J-8
`
`J.2
`Appendix K
` Cryptographic
`Algorithms K-1
`Symmetric Encryption K-2
` K.1
`Public-Key Cryptography K-6
` K.2
`Secure Hash Functions K-10
` K.3
`Appendix L
` Standards Organizations L-1
`The Importance of Standards L-2
`
`L.1
`Standards and Regulation L-3
`
`L.2
`Standards-Setting Organizations L-4
`
`L.3
`Appendix M
` Sockets: A Programmer’s
`Introduction M-1
`Sockets, Socket Descriptors, Ports,
`and Connections M-4
`
` M.1
`
`ONLINE CHAPTERS AND APPENDICES ix
`
` M.2
`
` M.3
` M.4
`
`The Client/Server Model of
`Communication M-6
`Sockets Elements M-8
`Stream and Datagram
`Sockets M-28
` M.5 Run-Time Program
`Control M-33
` M.6 Remote Execution of a Windows
`Console Application M-38
`
`Appendix N The International Reference
`Alphabet N-1
`
` BACI: The Ben-Ari
`Appendix O
`Concurrent Programming
`System O-1
`Introduction O-2
`BACI O-3
`Examples of BACI Programs O-7
`BACI Projects O-11
`Enhancements to the BACI
`System O-16
`
` O.1
` O.2
` O.3
` O.4
` O.5
`
`Appendix P Procedure Control P-1
`P.1
`Stack Implementation P-2
`P.2
`Procedure Calls and Returns P-3
`P.3
`Reentrant Procedures P-4
`
`Patent Owner, Bot M8 LLC - Ex. 2014, p. 11
`
`

`

`ONLINE RESOURCES
`
` Site
`
`Companion Web Site
`
`Premium Web Content
`
`Instructor Resource Center
`(IRC)
`
`Computer Science Student
`Resource Site
`
` Location
`
` Description
`
` williamstallings.com/OS/
`OS7e.html
`www.pearsonhighered.com/
`stallings/
`
` www.pearsonhighered.com/
`stallings/, click on Premium
`Web Content button and
`enter the student access code
`found on the card in the front
`of the book.
` Pearsonhighered.com/
`Stallings/, click on Instructor
`Resource button.
` computersciencestudent.com
`
`Student Resources button:
`Useful links and documents
`for students
`Instructor Resources button:
`Useful links and documents
`for instructors
` Online chapters, appendices,
`and other documents that
` supplement the book
`
` Solutions manual, projects
`manual, slides, and other
` useful documents
` Useful links and documents
`for computer science students
`
`x
`
`Patent Owner, Bot M8 LLC - Ex. 2014, p. 12
`
`

`

`PREFACE
`
` This book does not pretend to be a comprehensive record; but it aims
`at helping to disentangle from an immense mass of material the crucial
`issues and cardinal decisions. Throughout I have set myself to explain
`faithfully and to the best of my ability.
` — THE WORLD CRISIS , Winston Churchill
`
`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 char-
`acteristics 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 in the
`capacity and speed of machines, but in applications and system support require-
`ments as well. Second, the rapid pace of change that has always characterized com-
`puter systems continues with no letup. 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 oper-
`ating 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 implemen-
`tation 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, three operating systems have
`been chosen as running examples:
`
`• Windows 7: A multitasking operating system for personal computers, work-
`stations, and servers. 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
`xi
`
`Patent Owner, Bot M8 LLC - Ex. 2014, p. 13
`
`

`

`xii PREFACE
`
` object-oriented design principles. This book covers the technology used in
`the most recent version of Windows, known as Windows 7.
`• UNIX: A multiuser operating system, originally intended for minicomput-
`ers, but implemented on a wide range of machines from powerful microcom-
`puters to supercomputers. Several flavors of UNIX are included as examples.
`FreeBSD is a widely used system that incorporates many state-of-the-art fea-
`tures. Solaris is a widely used commercial version of UNIX.
`• Linux: An open-source version of UNIX that is now 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 concur-
`rency, 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.
`
`INTENDED AUDIENCE
`
` The book is intended for both an academic and a professional audience. As a text-
`book, it is intended as a one-semester undergraduate course in operating systems
`for computer science, computer engineering, and electrical engineering majors.
`It covers all of the core topics and most of the elective topics recommended in
`Computer Science Curriculum 2008 , from the Joint Task Force on Computing
`Curricula of the IEEE Computer Society and the ACM, for the Undergraduate
`Program in Computer Science. The book also covers the operating systems top-
`ics recommended in the Guidelines for Associate-Degree Curricula in Computer
`Science 2002 , also from the Joint Task Force on Computing Curricula of the IEEE
`Computer Society and the ACM. The book also serves as a basic reference volume
`and is suitable for self-study.
`
`PLAN OF THE TEXT
`
` The book is divided into eight parts (see Chapter 0 for an overview):
`
`• Background
`• Processes
`• Memory
`• Scheduling
`• Input/output and files
`• Embedded systems
`• Security
`• Distributed systems
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Patent Owner, Bot M8 LLC - Ex. 2014, p. 14
`
`

`

`PREFACE xiii
`
` The book includes a number of pedagogic features, including the use of ani-
`mations and numerous figures and tables to clarify the discussion. Each chapter
`includes a list of key words, review questions, homework problems, suggestions for
`further reading, and recommended Web sites. 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.
`
`WHAT’S NEW IN THE SEVENTH EDITION
`
` In the 3 years since the sixth edition of this book was published, the field has seen
`continued innovations and improvements. In this new edition, I try to capture these
`changes while maintaining a broad and comprehensive coverage of the entire field.
`To begin the process of revision, the sixth 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 clari-
`fied and tightened, and illustrations have been improved. Also, a number of new
`“field-tested” homework problems have been added.
` Beyond these refinements to improve pedagogy and user friendliness, the
`technical content of the book has been updated throughout, to reflect the ongo-
`ing changes in this exciting field, and the instructor and student support has been
`expanded. The most noteworthy changes are as follows:
`
`• Windows 7: Windows 7 is Microsoft’s latest OS offering for PCs, worksta-
`tions, and servers. The seventh edition provides details on Windows 7
` internals in all of the key technology areas covered in this book, including
`process/thread management, scheduling, memory management, security,
`file systems, and I/O.
`• Multicore operating system issues: The seventh edition now includes cover-
`age of what has become the most prevalent new development in computer
`systems: the use of multiple processors on a single chip. At appropriate points
`in the book, operating system issues related to the use of a multicore organiza-
`tion are explored.
`• Virtual machines: Chapter 2 now includes a section on virtual machines, which
`outlines the various approaches that have been implemented commercially.
`• New scheduling examples: Chapter 10 now includes a discussion of the
`FreeBSD scheduling algorithm, designed for use with multiprocessor and
`multicore systems, and Linux VServer scheduling for a virtual machine
`environment.
`• Service-oriented architecture (SOA): SOA is a form of client/server archi-
`tecture that now enjoys widespread use in enterprise systems. SOA is now
`covered in Chapter 16 .
`• Probability, statistics, and queueing analysis: Two new chapters review key
`topics in these areas to provide background for OS performance analysis.
`• B-trees: This is a technique for organizing indexes into files and databases
`that is commonly used in OS file systems, including those supported by
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Patent Owner, Bot M8 LLC - Ex. 2014, p. 15
`
`

`

`xiv PREFACE
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Mac OS X, Windows, and several Linux file systems. B-trees are now cov-
`ered in Chapter 12 .
`• Student study aids: Each chapter now begins with a list of learning objec-
`tives. In addition, a chapter-by-chapter set of review outlines highlights key
`concepts that the student should concentrate on in each chapter.
`• OS/161: OS/161 is an educational operating system that is becoming increas-
`ingly recognized as the teaching platform of choice. This new edition provides
`support for using OS/161 as an active learning component. See later in this
`Preface for details.
`• Sample syllabus: The text contains more material than can be conveniently covered
`in one semester. Accordingly, instructors are provided with several sample syllabi
`that guide the use of the text within limited time (e.g., 16 weeks or 12 weeks). These
`samples are based on real-world experience by professors with the sixth edition.
`
` With each new edition, it is a struggle to maintain a reasonable page count while
`adding new material. In part, this objective is realized by eliminating obsolete material
`and tightening the narrative. For this edition, chapters and appendices that are of less
`general interest have been moved online, as individual PDF files. This has allowed an
`expansion of material without the corresponding increase in size and price.
`
`STUDENT RESOURCES
`
` For this new edition, a tremendous amount of original supporting material has been
`made available online, in the following categories
`The Companion Web site and student resource material can be reached through
`the Publisher’s Web site www.pearsonhighered.com/stallings or by clicking on
`the button labeled “Book Info and More Instructor Resources” at the book’s
`Companion Web site WilliamStallings.com/OS/OS7e.html. For this new edition, a
`tremendous amount of original supporting material has been made available online,
`in the following categories:
`
`• Homework problems and solutions: To aid the student in understanding the
`material, a separate set of homework problems with solutions are available.
`These enable the students to test their understanding of the text.
`• Programming projects: Two major programming projects, one to build a
`shell (or command line interpreter) and one to build a process dispatcher, are
`described.
`• Key papers: Several dozen papers from the professional literature, many hard
`to find, are provided for further reading.
`• Supporting documents: A variety of other useful documents are referenced in
`the text and provided online.
`
`Premium Web Content
` Purchasing this textbook new grants the reader 6 months of access to this online
`material. See the access card in the front of this book for details.
`
`Patent Owner, Bot M8 LLC - Ex. 2014, p. 16
`
`

`

`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`PREFACE xv
`
`• Online chapters: To limit the size and cost of the book, four chapters of the
`book 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 mate-
`rial found in the text but whose inclusion is not warranted in the printed text.
`A total of 13 appendices cover these topics for the interested student. The
` appendices are listed in this book’s table of contents.
`
`INSTRUCTOR SUPPORT MATERIALS
`
` Support materials are available at the Instructor Resource Center (IRC)
`for this textbook, which can be reached through the Publisher’s Web site
`www.pearsonhighered.com/stallings or by clicking on the button labeled “Book
`Info and More Instructor Resources” at this book’s Companion Web site
`WilliamStallings.com/OS/OS7e.html. To gain access to the IRC, please contact
`your local Pearson sales representative via pearsonhighered.com/educator/replo-
`cator/requestSalesRep.page or call Pearson Faculty Services at 1-800-526-0485.
`To support instructors, the following materials are provided:
`
`• Solutions manual: Solutions to end-of-chapter Review Questions and
`Problems.
`• Projects manual: Suggested project assignments for all of the project categories
`listed in the next section.
`• 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.
`• Links to Web sites for other courses being taught using this book.
`• An Internet mailing list has been set up so that instructors using this book can
`exchange information, suggestions, and questions with each other and with
`the author. As soon as typos or other errors are discovered, an errata list for
`this book will be available at WilliamStallings.com. Sign-up information for
`this Internet mailing list.
`• Computer science student resource list: A list of helpful links for computer
` science students and professionals is provided at ComputerScienceStudent.com,
`which provides documents, information, and useful links for computer science
`students and professionals.
`• 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 fur-
`ther 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
`
`Patent Owner, Bot M8 LLC - Ex. 2014, p. 17
`
`

`

`xvi PREFACE
`
`
`
`
`
`
`
`
`
`
`
`
`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.
`
`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 provides an unparalleled degree of support for including
`a projects component in the course. In the online portion of the text, two major
` programming projects are defined. In addition, the instructor support materials
`available through Pearson not only include 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 below.
`• Simulation projects: Described below.
`• 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 mes-
`sage 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
` New to this edition is support for an active learning component based on OS/161.
`OS/161 is an educational operating system that is becoming increasingly recog-
`nized as the preferred teaching platform for OS internals. It aims to strike a bal-
`ance between giving students experience in working on a real operating system and
` potentially overwhelming students with the complexity that exists in a fully 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 there-
`fore it is much easier to develop an understanding of the entire code base.
`
`Patent Owner, Bot M8 LLC - Ex. 2014, p. 18
`
`

`

`PREFACE xvii
`
` The IRC includes:
`
`
`
`
`
`
`
`
`
`1. A packaged set of html files that the instructor can upload to a course server
`for student access.
`2. A getting-started manual to be handed out to students to help them begin
`using OS/161.
`3. A set of exercises using OS/161, to be handed out to students.
`4. Model solutions to each exercise for the instructor’s use.
`5. All of this will be cross-referenced with appropriate sections in the book, so
`that the student can read the textbook material and then do the corresponding
`OS/161 project.
`
`Simulations for Students and Instructors
` The IRC provides support for assigning projects base