; i <^*.'%-> ?,~<:i
`^iliW
`
`r-#V'
`
`,* ^
`
`•f ,
`
`The scene depicted is set during
`
`the late Cretaceous period in the
`
`western United States. A
`
`Tyrannosaurus rex threatens a
`
`Staurikosaurus while a small
`
`varanid lizard is safe in a jumble
`
`of rocks. A small herd of
`
`Om'rthomimus stays out of the way
`
`in the background while Pterosaurs
`
`circle in flight above. The massive
`
`seems rtinconcerned
`
`by the confrontation.
`
`,
`
`% .
`
`SAMSUNG EX. 1014 - 1/53
`
`

`

`To my parents, Wira and Mietek,
`and my children, Lemor, Sivan, and Aaron.
`
`Aui Silberschatz
`
`To Carla, Gwendolyn, and Owen
`- -»
`
`Peter Galvin
`
`SAMSUNG EX. 1014 - 2/53
`
`

`

`OPERATING
`
`Fifth Edition
`
`Abraham Silberschatz
`Bell Labs
`
`Peter Baer Galvin
`Corporate Technologies, Inc.
`
`ArADDISON-WESLEY
`An imprint of Addison Wesley Longman, Inc.
`
`Reading, Massachusetts • Harlow, England • Menlo Park, California
`Berkeley, California • Don Mills, Ontario • Sydney
`Bonn • Amsterdam • Tokyo • Mexico City
`
`SAMSUNG EX. 1014 - 3/53
`
`

`

`PREFACE
`
`Operating systems are an essential part of any computer system. Similarly,
`a course on operating systems is an essential part of any computer-science
`education. This book is intended as a text for an introductory course in
`operating systems at the junior or senior undergraduate level, or at the first-
`year graduate level. It provides a clear description of the concepts that underlie
`operating systems.
`In this book, we do not concentrate on any particular operating system
`or hardware. Instead, we discuss fundamental concepts that are applicable
`to a variety of systems. We present a large number of examples that pertain
`specifically to UNIX and to other popular operating systems. In particular, we
`use Sun Microsystem's Solaris 2 operating system, a version of UNIX, which
`recently has been transformed into a modern operating system with support
`for threads at the kernel and user levels, symmetric multiprocessing, and real-
`time scheduling. Other examples used include Microsoft MS-DOS, Windows,
`~and Wih^oWsHSTT^TMuxTTBT^^
`and DEC VMS and TOPS-20.
`
`Prerequisites
`
`As prerequisites, we assume that the reader is familiar with general computer
`organization and with a high-level language, such as Pascal. The hardware
`topics required for an understanding of operating systems are included in
`Chapter 2. We use pseudo-Pascal notation for code examples, but the algo-
`
`SAMSUNG EX. 1014 - 4/53
`
`

`

`vi
`
`JrTetace
`
`rithms can be understood by people who do not have a thorough knowledge of
`Pascal.
`
`Content of this Book
`
`The text is organized in seven major parts:
`
`• Overview (Chapters 1 to 3). These chapters explain what operating systems
`are, what they do, and how they are designed and constructed. They explain
`how the concept of an operating system has developed, what the common
`features of an operating system are, what an operating system does for the
`user, and what it does for the computer-system operator. The presentation
`is motivational, historical, and explanatory in nature. We have avoided a
`discussion of how things are done internally in these chapters. Therefore,
`they are suitable for individuals or for students in lower-level classes who
`want to learn what an operating system is, without getting into the details
`of the internal algorithms. Chapter 2 covers the hardware topics that are
`important to an understanding of operating systems. Readers well-versed
`in hardware topics, including I/O, DMA, and hard-disk operation, may
`chose to skim or skip this chapter.
`
`• Process management (Chapters 4 to 7). The process concept and concur-
`rency are at the heart of modern operating systems. A process is the unit
`of work in a system. Such a system consists of a collection of concur^
`rently executing processes, some of which are operating-system processes
`(those that execute system code), and the rest of which are user processes
`(those that execute user code). These chapters cover various methods for
`process scheduling, interprocess communication, process synchronization,
`and deadlock handling. Also included under this topic is a discussion of
`threads.
`
`• Memory and storage management (Chapters 8 to 11). A process must
`be irrm
`both the utilization of CPU and the speed of its response to its users, the
`computer must keep several processes in memory. There are many different
`memory-management schemes. These schemes reflect various approaches
`to memory management, and the effectiveness of the different algorithms
`depends on the particular situation. Since main memory is usually too
`small to accommodate all data and programs, and since it cannot store
`data permanently, the computer system must provide secondary storage
`to back up main memory. Most modern computer systems use disks as
`the primary on-line storage medium for information (both programs and
`data). The file system provides the mechanism for on-line storage of and
`access to both data and programs residing on the disks. These chapters deal
`
`SAMSUNG EX. 1014 - 5/53
`
`

`

`Fretace
`
`vii
`
`with the classic internal algorithms and structures of storage management.
`They provide a firm practical understanding of the algorithms used—the
`properties, advantages, and disadvantages.
`
`• I/O systems (Chapters 12 to 14). The devices that attach to a computer vary
`in multiple dimensions. In many ways, they are also the slowest major
`components of the computer. Because devices vary so widely, the operat-
`ing system needs to provide a wide range of functionality to applications
`to allow them to control all aspects of the devices. This section discusses
`system I/O in depth, including I/O system design, interfaces, and internal
`system structures and functions. Because devices are a performance bottle-
`neck, performance issues are examined. Matters related to secondary and
`tertiary'storage are explained as well.
`
`• Distributed systems (Chapters 15 to 18). A distributed system is a collection
`of processors that do not share memory or a clock. Such a system provides
`the user with access to the various resources^that the system maintains.
`Access to a shared resource allows computation speedup and improved
`data availability and reliability. Such a system also provides the user with a
`distributed file system, which is a file-service system whose users, servers,
`and storage devices are dispersed among the various sites of a distributed
`system. A distributed system must provide various mechanisms for pro-
`cess synchronization and communication, for dealing with the deadlock
`problem and the variety of failures that are not encountered in a centralized
`, system.
`
`• Protection and security (Chapters 19 and 20). The various processes in an
`operating system must be protected from one another's activities. For that
`purpose, mechanisms exist that we can use to ensure that the files, memory
`segments, CPU, and other resources can be operated on by only those
`processes that have gained proper authorization from the operating system.
`Protection is a mechanism for controlling the access of'programs, processes,
`or users to the resources defined by a computer system. This mechanism
`must provide-a-me^ns far^
`imposed, as^
`well as a means of enforcement. Security protects the information stored
`in the system (both data and code), as well as the physical resources of
`the computer system, from unauthorized access, malicious destruction or
`alteration, and accidental introduction of inconsistency.
`
`• Case studies (Chapters 21 to 24). We integrate the various concepts
`described in this book by describing real operating systems. Three such
`systems are covered in great detail—UNIX Berkeley 4.3BSD, Linux, and
`Microsoft Windows NT. We chose Berkeley 4.3BSD and Linux because UNIX
`at one time was almost small enough to understand, and yet was not a
`"toy" operating system. Most of its internal algorithms were selected for
`simplicity, rather than for speed or sophistication. Both Berkeley 4.3BSD
`
`SAMSUNG EX. 1014 - 6/53
`
`

`

`vm
`
`and Linux are readily available to computer-science departments, so many
`students have access to these systems. We chose Windows NT because it
`provides an opportunity for us to study a modern operating system that
`has a design and implementation drastically different from those of UNIX.
`Chapter 24 briefly describes a few other influential operating systems.
`:
`
`The Fifth Edition
`
`Many comments and suggestions were forwarded to us concerning our previ-
`ous editions. These inputs, with our own observations, have prodded us to
`produce this fifth edition. In particular, we have made drastic changes to our
`coverage of I/O systems, and have added two new chapters covering modern
`operating systems. Specifically, we rewrote the material in several chapters that
`deal with storage devices (Chapters 1,2,3, and 8) by bringing older material up
`to date and removing material that was no longer of interest. We have added
`new chapters on I/O systems, on tertiary storage, on Linux, and on Windows
`NT.
`.
`"
`We made substantive revisions and changes in organization structure in the
`following chapters:
`
`• Chapter 3. We have added a new section discussing the Java Virtual
`Machine.
`. - . .-
`; , 1
`-
`
`• Chapter 4. We have added a new section describing the interprocess-
`communication facility of Windows NT.
`
`• Chapter 12. This new chapter describes operating-system I/O architecture
`and implementation, including kernel structure, transfer methods, notifica-
`tion methods, and performance.
`
`• Chapter 13. This chapter was the old Chapter 12. We have updated the
`material substantially.
`
`• Chapter 14. This new chapter covers tertiary-storage systems.
`
`• Chapter 19. This chapter was the old Chapter 13.
`
`• Chapter 20. This chapter was the old Chapter 14.
`
`• Chapter 21. This chapter was the old Chapter 19. ~
`
`• Chapter 22. This new chapter covers Linux.
`
`• Chapter 23. This new chapter covers Windows NT.
`
`• Chapter 24. This chapter was the old Chapter 21. We have added a section
`describing early-batch systems (previously covered in Chapter 1), and a
`section summarizing the novel features of the Mach operating system.
`
`SAMSUNG EX. 1014 - 7/53
`
`

`

`Preface
`
`ix
`
`Coverage of the Mach operating system (old Chapter 20), which is a modern
`operating system that provides compatibility with 4.3BSD, is available on-line.
`Coverage of the Nachos System (old Appendix), which provides a good way
`to gain a deeper understanding of modern operating-systems concepts and
`allows students to get their hands dirty—to take apart the code for an operating
`system, to see how it works at a low level, to build significant pieces of .the
`operating system themselves, and to observe the effects of their work—also is
`available on line.
`
`Mailing List and Supplements
`
`»
`We now have a web page for this book that contains information such as
`the set of slides that accompanies the book, the postscript files of the Mach
`and Nachos chapters, and the most recent errata list. We also provide an
`environment where users can communicate among themselves and with us.
`We have created a mailing list consisting of users of our book with the following
`address: os-book@research.bell-labs.com. If you wish to be on the list, please
`send a message to avi@bell-labs.com indicating your name, affiliation, and
`e-mail address.
`For information about teaching supplements and on-line material, which
`complement the book, visit the URL http://www.awl.com/cseng/books/osc5e.
`A list of supplements and detail contact information for the United States and
`international can be obtained via an automatic e-mail reply generated by
`sending mail to osc@aw.com. To obtain restricted supplements, please contact
`your local sales representative.
`
`Errata
`
`We have attempted to clean up every error in this new edition, but — as happens
`with operating systems — a few obscure bugs will remain. We would appreciate
`
`in the book. Also, if you would like to suggest improvements or to contribute
`exercises, we would be glad to hear from you. Any correspondence should be
`sent to Avi Silberschatz, Director, Information Sciences Research Center, MH
`2T-210, Bell Laboratories, 600 Mountain Ave., Murray Hill, NJ 07974 (avi@bell-
`labs.com).
`
`Acknowledgments
`
`This book is derived from the previous editions, the first three of which
`were coauthored by James Peterson. Other people that have helped us with
`
`SAMSUNG EX. 1014 - 8/53
`
`

`

`the previous editions include Randy Bentson, David Black, Joseph Boykin,
`Jeff Brumfield, Gael Buckley, P. C: Capon, John Carpenter, Thomas Casa-
`vant, Ajoy Kumar Datta, Joe Deck, Thomas Doeppner, Caleb Drake, M. Ra§it
`Eskicioglu, Hans Flack, Robert Fowler, G. Scott Graham, Rebecca Hartman,
`Wayne Hathaway, Christopher Haynes, Mark Holliday, Richard Kieburtz, Carol
`Kroll, Thomas LeBlanc, John Leggett, Jerrold Leichter, Ted Leung, Gary Lipp-
`man, Carolyn Miller, Michael Molloy, Yoichi Muraoka, Jim M. Ng, Ed Posnak,
`Boris Putanec, Charles Qualline, John Quarterman, John Stankovic, Adam
`Stauffer, Steven Stepanek, Hal Stern, Louis Stevens, David Umbaugh, Steve
`Vinoski, John Werth, and J. S. Weston.
`Lyn Dupre copyedited the book; Cliff Wilkes provided technical copyedit-
`ing; Sara Strandtman edited our text into Latex format; Marilyn Turnamian
`helped with the generation of figures. Debbie Lafferty, Lynne Doran Cote, and
`Patricia Unubun were helpful with book production.
`Bruce Hillyer reviewed and helped with the rewrite of Chapters 2, 12, 13,
`and 14. Chapter 14 was derived from a paper by Hillyer and Silberschatz [1996].
`Chapter 17 was derived from a paper by Levy and Silberschatz [1990]. Chapter
`19 was derived from a paper by Quarterman et al. [1985]. Chapter 22 was
`derived from an unpublished manuscript by Stephen Tweedie. Chapter 23 was
`derived from an unpublished manuscript by Cliff Martin. Additional editing
`on this chapter was done by Bruce Hillyer. .
`...
`We thank the following people, who reviewed this edition of the book:
`Hamid Arabnia, Sudarshan_K. Dhall, Steven Stepanek, Pete Thomas, L. David
`Umbaugh, Tommy Wagner.
`,
`
`Abraham Silberschatz, 1997, Murray Hill, NJ
`Peter Baer Galvin, 1997, Norton MA
`
`~
`
`SAMSUNG EX. 1014 - 9/53
`
`

`

`CONTENTS
`
`PART ONE
`
`OVERVIEW
`
`Chapter 1 Introduction
`1.1 What Is an Operating System? 3
`1.2 Simple Batch Systems 6
`1.3 Multiprogrammed Batched
`Systems 8
`1.4 Time-Sharing Systems 9
`1.5 Personal-Computer Systems 12
`
`1.6 Parallel Systems 14
`1.7 Distributed Systems 16
`1.8 Real-Time Systems 18
`1.9 Summary 19
`Exercises 20
`Bibliographical Notes 21
`
`Chapter 2 Computer-System Structures
`2.1 Computer-System Operation 23
`2.6 General System Architecture 43
`2.2 I/O Structure 26
`2.7 Summary 45
`2.3 Storage Structure 30
`Exercises 45
`2.4 Storage Hierarchy 35
`Bibliographical Notes 47
`2.5 Hardware Protection 37
`
`XI
`
`SAMSUNG EX. 1014 - 10/53
`
`

`

`Chapter 3 Operating-System Structures
`3.1 System Components 49
`3.7 System Design and
`3.2 Operating-System Services 55
`Implementation 78
`3.3 System Calls 57
`3.8 System Generation 81
`3.4 System Programs 66
`3.9 Summary 83
`3.5 System Structure 68
`Exercises 83
`3.6 Virtual Machines 74
`Bibliographical Notes 84
`
`PART TWO
`
`PROCESS MANAGEMENT
`
`Chapter 4 Processes
`4.1 Process Concept 89
`4.2 Process Scheduling 93
`4.3 Operation on Processes 97
`4.4 Cooperating Processes 100
`4.5 Threads 102
`
`4.6 Interprocess Communication 108
`4.7 Summary 119
`Exercises 120
`Bibliographical Notes 121
`
`Chapter 5 CPU Scheduling
`5.1 Basic Concepts 123. -
`5.2 Scheduling Criteria 127
`5.3 Scheduling Algorithms 129
`5.4 Multiple-Processor Scheduling 141
`5.5 Real-Time Scheduling 141
`
`5.6 Algorithm Evaluation 144
`5.7 Summary 149
`Exercises 150
`Bibliographical Notes 152
`
`Chapter 6 Process Synchronization
`6.1 Background 155
`6.7 Monitors 181
`6.8 Synchronization in Solaris 2- 189
`6.2 The Critical-Section Problem 157
`6.9 Atomic Transactions 190
`6.3 Synchronization Hardware 164.
`6.10-Summary 199
`6.4 Semaphores 167
`Exercises 200
`6.5 Classical Problems of
`: Bibliographical Notes 204
`Synchronization 172
`6.6 Critical Regions 177
`
`. - . - -.
`
`SAMSUNG EX. 1014 - 11/53
`
`

`

`contents
`
`xiu
`
`Chapter 7 Deadlocks
`7.1 System Model 207
`7.2 Deadlock Characterization
`7.3 Methods for Handling
`Deadlocks 212
`7.4 Deadlock Prevention 214
`7.5 Deadlock Avoidance 217
`7.6 Deadlock Detection 223
`
`209
`
`7.7 Recovery from Deadlock 227
`7.8 Combined Approach to Deadlock
`. Handling 229 .
`7.9 Summary 230
`Exercises 231
`Bibliographical Notes 235
`
`PART THREE
`
`STORAGE MANAGEMENT
`
`Chapter 8 Memory Management
`8.6 Segmentation 272
`8.1 Background 239
`8.7 Segmentation with Paging
`8.2 Logical versus Physical Address
`8.8 Summary 282
`Space 245
`Exercises 284
`8.3 Swapping 246
`Bibliographical Notes 287
`8.4 Contiguous Allocation 249
`8.5 Paging 257
`
`278
`
`Chapter 9 Virtual Memory
`9.1 Background 289
`9.2 Demand Paging 291
`9.3 Performance of Demand Paging 297
`.9.4J^ageRepJacement_ 300
`9.5 Page-Replacement Algorithms 303
`9.6 Allocation of Frames 313
`
`9.7 Thrashing 317
`9.8 Other Considerations 322
`9.9 Demand Segmentation 328
`9.10 Summary 329
`Exercises 331
`Bibliographical Notes 335
`
`Chapter 10 File-System Interface
`10.5 Consistency Semantics 364
`10.1 File Concept 337
`10.6 Summary 365
`10.2 Access Methods 346
`10.3 Directory Structure, 349
`Exercises 366
`Bibliographical Notes 368
`10.4 Protection 360
`
`SAMSUNG EX. 1014 - 12/53
`
`

`

`xiv
`
`Contents
`
`Chapter 11 File-System Implementation
`11.1 File-System Structure 369
`11.6 Recovery 389
`11.2 Allocation Methods 373
`11.7 Summary 391
`11.3 Free-Space Management 382
`Exercises 392
`11.4 Directory Implementation 385
`Bibliographical Notes 393
`11.5 Efficiency and Performance 386
`
`PART FOUR m I/O SYSTEMS
`
`Chapter 12 I/O Systems
`12.1 Overview 397
`12.2 I/O Hardware 398
`12.3 Application I/O Interface 408
`12.4 Kernel I/O Subsystem 414
`12.5 Transforming I/O Requests.to
`Hardware Operations 420
`
`12.6 Performance 423
`12.7 Summary 427
`Exercises 428
`Bibliographical Notes 429
`v
`.
`-
`• _ •
`-
`•:
`
`.
`,
`
`„
`
`Chapter 13 Secondary-Storage Structure
`13.1 Disk Structure 431
`13.6 Stable-Storage Implementation 446
`13.2 Disk Scheduling 432
`13.7 Summary 447
`13.3JDisk Management 438
`Exercises 447
`13.4 Swap-Space Management""442
`^ibTmgr¥phKarNotes 452
`13.5 Disk Reliability 444
`
`Chapter 14 Tertiary-Storage Structure
`14.1 Tertiary-Storage Devices 455
`.- 14.4 Summary 466
`14.2 Operating-System Jobs 458
`Exercises 466
`14.3 Performance Issues 461
`Bibliographical Notes 469
`
`SAMSUNG EX. 1014 - 13/53
`
`

`

`Contents
`
`xv
`
`PART FIVE
`
`• DISTRIBUTED SYSTEMS
`
`Chapter 15 Network Structures
`15.1 Background 473
`15.2 Motivation 475
`15.3 Topology 476
`15.4 Network Types 481
`15.5 Communication 484
`
`15.6 Design Strategies 491
`15.7 Networking Example 495
`15.8 Summary 497
`Exercises 498
`Bibliographical Notes 499
`
`Chapter 16 Distributed System Structures
`16.1 Network Operating Systems 501
`16.5 Design Issues 512
`16.2 Distributed Operating Systems 503
`16.6 Summary 515
`16.3 Remote Services 506
`Exercises 516
`16.4 Robustness 511
`Bibliographical Notes 516
`
`Chapter 17 Distributed File Systems
`17.1 Background 519
`.
`17.6 Example Systems 532
`17.2 Naming and Transparency 521
`17.7 Summary 559
`17.3 Remote File Access 525
`Exercises 560
`17.4 Stateful versus Stateless Service 530
`Bibliographical Notes 561
`17.5 File Replication 531
`
`Chapter 18 Distributed Coordination
`18.1 Event Ordering 563
`18.6 Election Algorithms 586
`18.2 Mutual Exclusion 566
`18.7 Reaching Agreement 588
`18.3 Atomicity 569
`18.8 Summary 591
`18.4 Concurrency Control 573
`Exercises 592
`18.5 Deadlock Handling 578
`Bibliographical Notes 593
`
`SAMSUNG EX. 1014 - 14/53
`
`

`

`-VJJLI.Vtmi.lC3
`
`PART SIX
`
`PROTECTION AND SECURITY
`
`Chapter 19 Protection
`19.1 Goals of Protection 597
`19.2 Domain of Protection 598
`19.3 Access Matrix 604
`19.4 Implementation of Access
`Matrix 608
`19.5 Revocation of Access Rights
`
`611
`
`Chapter 20 Security
`20.1 The Security Problem 623
`20.2 Authentication 625
`20.3 One-Time Passwords 628
`20.4 Program Threats 629
`20.5 System Threats 630
`20.6 Threat Monitoring 634
`20.7 Encryption 637
`
`19.6 Capability-Based Systems 613 "
`19.7 Language-Based Protection 616
`19.8 Summary 620
`Exercises 620
`Bibliographical Notes 621
`
`20.8 Computer-Security
`Classifications 639
`20.9 An Example Security Model:"
`Windows NT 640
`20.10 Summary 642
`Exercises 643
`Bibliographical Notes 644
`
`PART SEVEN
`
`CASE STUDIES
`
`Chapter 21 The UNIX System
`21.1 History 647
`21.2 Design Principles 653
`21.3 Programmer Interface 654
`21.4 User Interface 663
`21.5 Process Management 666
`21.6..Memory Management 671
`
`21.7 File System 675
`21.8 I/O System 683
`21.9 Interprocess Communication
`21.10 Summary 692
`Exercises 693
`Bibliographical Notes 694
`
`Chapter 22 The Linux System
`22.1 History 697
`22.2 Design Principles 702
`22.3 Kernel Modules 705
`22.4 Process Management 709
`22.5 Scheduling 713
`22.6 Memory Management 717
`22.7 File Systems 725
`
`.
`
`22.8 Input and Output 730
`22.9 Interprocess Communication
`22.10 Network Structure 736
`22.11 Security 738
`22.12 Summary 741
`Exercises 742
`Bibliographical Notes 743
`
`687
`
`734
`
`SAMSUNG EX. 1014 - 15/53
`
`

`

`Contents
`
`xvii
`
`Chapter 23 Windows NT
`23.1 History 745
`23.2 Design Principles 746
`23.3 System Components 747
`23.4 Environmental Subsystems 763
`23.5 File System 766
`
`23.6 Networking 773
`23.7 Programmer Interface 779
`23.8 Summary 786
`Exercises 786
`Bibliographical Notes 787
`
`Chapter 24 Historical Perspective
`24.1 Early Systems 789
`24.6 CTSS 799
`24.2 Atlas 795
`24.7 MULTICS 799
`24.3 XDS-940 796
`24.8 OS/360 800
`24.4 THE 797
`24.9 Mach 802
`24.5 RC4000 798
`24.10 Other Systems 803
`
`Bibliography 805
`
`Credits 839
`
`Index 841
`
`SAMSUNG EX. 1014 - 16/53
`
`

`

`SAMSUNG Ex. 1014 - 17/53
`
`SAMSUNG EX. 1014 - 17/53
`
`

`

`Part One
`
`OVERVIEW
`
`An operating system is a program that acts as an intermediary between a user of
`a computer and the computer hardware. The purpose of an operating system is
`to provide an environment in which a user can execute programs in a convenient
`and efficient manner.
`We trace the development of operating systems from the first hands-on
`systems to current multiprogrammed and time-shared systems. Understanding
`the reasons behind the development of operating systems gives us an appreci-
`ation for what an operating system does and how it does it.
`The operating system must ensure the correct operation of the computer
`system. To prevent user programs from interfering with the proper operation
`of the system, the hardware must provide appropriate mechanisms to ensure
`such proper behavior. We describe the basic computer architecture that makes
`it possible to write a correct operating^ystem.
`The operating system provides certain services to programs and to the users
`of those programs in order to make the programming task easier. The specific
`services provided will, of course, differ from one operating system to another,
`but there are some common classes of services that we identify and explore.
`
`SAMSUNG EX. 1014 - 18/53
`
`

`

`SAMSUNG Ex. 1014 - 19/53
`
`SAMSUNG EX. 1014 - 19/53
`
`

`

`Chapter 1
`
`INTRODUCTION
`
`An operating system is a program that acts as an intermediary between a user of
`a computer and the computer hardware. The purpose of an operating system is
`to provide an environment in which a user can execute programs. The primary
`goal of an operating system is thus to make the computer system convenient to
`use. A secondary goal is to use the computer hardware in an efficient manner.
`To understand what operating systems are, we must first understand how
`they have developed. In this chapter, as well as in Chapter 24, we trace the
`development of operating systems from the first hands-on systems to current
`multiprogrammed and time-shared systems. As we move through the various
`stages, we see how the components of operating systems evolved as natural
`solutions to problems in early computer systems. Understanding the reasons
`behind the development of operating systems gives us an appreciation for what
`-tasks an operating^system does^and howH^does them-
`
`1.1 • What Is an Operating System?
`
`An operating system is an important part of almost every computer system. A
`computer system can be divided roughly into four components: the hardware,
`the operating system, the application programs, arid the users (Figure 1.1).
`The hardware—the central processing unit (CPU), the memory, and the
`input/output (I/O) devices—provides the basic computing resources. The
`application programs—such as compilers, database systems, games, and busi-
`ness programs—define the ways in which these resources are used to solve the
`
`SAMSUNG EX. 1014 - 20/53
`
`

`

`Chapter 1
`
`Introduction
`
`user
`1
`
`user
`2
`
`-user
`3
`
`user
`
`compiler
`
`assembler
`
`text editor
`
`database
`system
`
`system and application programs
`
`operating system
`
`computer hardware
`
`Figure 1.1 Abstract view of the components of a computer system.
`
`computing problems of the users. There may be many different users (people,
`machines, other computers) trying to solve different problems. Accordingly,
`there may be many different application programs. The operating system con:
`trols and coordinates the use of the hardware among the various application
`programs for the various users.
`An operating system is similar to a government. The components of a
`computer system are its hardware, software, and data. The operating system
`provides the means for the proper use of these resources in the operation of
`the computer system. Like a government, the operating system performs no
`useful function by itself. It simply provides an environment within which other
`programs^an^lo useful
`We can view an operating system as a resource allocator. A computer system
`has many resources (hardware and software) that may be required to solve
`a problem: CPU time, memory space, file storage space, I/O devices, and so
`on. The operating system acts as the manager of these resources and allocates
`them to specific programs and users as necessary for tasks. Since there may
`be many— possibly conflicting — requests for resources, the operating system
`must decide which requests are allocated resources to operate the computer
`system efficiently and fairly.
`A slightly different view of an operating system focuses on the need to
`control the various I/O devices and user programs. An operating system is
`a control program. A control program controls the execution of user programs
`
`SAMSUNG EX. 1014 - 21/53
`
`

`

`1.1 What Is an Operating System?
`
`to prevent errors and improper use of the computer. It is especially concerned
`with the operation and control of I/O devices.
`In general, however, there is no completely adequate definition of an
`operating system. Operating systems exist because they are a reasonable way:
`to solve the problem of creating a usable computing system. The fundamental
`goal of computer systems is to execute user programs and to make solving user
`problems easier. Toward this goal, computer hardware is constructed. Since
`bare hardware alone is not particularly easy to use, application programs are
`developed. These various programs require certain common operations, such
`as those controlling the I/O devices. The common functions of controlling and
`allocating resources are then brought together into one piece of software: the
`operating system.
`There is also no universally accepted definition of what is part of the
`operating system and what is not. A simple viewpoint is that everything a
`vendor ships when you order "the operating system" should be considered.
`The memory requirements and features included, however, vary greatly across
`systems. Some take up less than 1 megabyte of space (1 megabyte is 1 million
`bytes) and lack even a full-screen editor, whereas others require hundreds of
`megabytes of space and include spell checkers and entire "window systems."
`A more common definition is that the operating system is the one program
`running at all times on the computer (usually called the kernel), with all else
`being application programs. This last definition is more common and is the one
`we generally follow.
`It is easier to define operating systems by what they do than by what
`they are. The primary goal of an operating system is convenience for the user.
`Operating systems exist because they are supposed to make it easier to compute
`with them than without them. This view is particularly clear when you look at
`operating systems for small personal computers.
`A secondary goal is efficient operation of the computer system. This goal
`is particularly important for large, shared multiuser systems. These systems
`are typically expensive, so it is desirable to make them as efficient as possible.
`These two goals—convenience and efficiency—are sometimes contradictory.
`In the past>- efficiency-considerations-were^often-more important^ than conve-
`nience. Thus, much of operating-system theory concentrates on optimal use of
`computing resources.
`To see what operating systems are and what operating systems do, let us
`consider how they have developed over the past 35 years. By tracing that
`evolution, we can identify the common elements of operating systems, and see
`how and why these systems have developed as they have. A more detailed
`discussion on historical-perspective is given in Chapter 24.
`Operating systems and computer architecture have had a great deal of
`influence on each other. To facilitate the use of the hardware, operating systems
`were developed. As operating systems were designed and used, it became
`obvious that changes in the design of the hardware could simplify them. In
`
`SAMSUNG EX. 1014 - 22/53
`
`

`

`\_napter i
`
`inirouucuun
`
`this short historical review, notice how operating-system problems led to the
`introduction of new hardware features.
`
`1.2 • Simple Batch Systems
`
`Early computers were (physically) enormously large machines run from a
`console. The common input devices were card readers and tape drives. The
`common output devices were line printers, tape drives, and card punches. The
`users of such systems did not interact directly with the computer systems.
`Rather, the user prepared a job—which consisted of the program, the data,
`and some-control information about the nature of the job (control cards)—and
`submited it to the computer operator. The job would usually be in the form of
`punch cards. At some later time (perhaps minutes, hours, or days), the output
`appeared. The output consisted of the result of the program, as well as a-dump
`of memory and registers in case of program error.
`Its
`The operating system in these early computers was fairly simple.
`major task was to transfer control automatically from one job to the next. The
`operating system was always (resident) in memory (Figure 1.2).
`To speed up processing, jobs with similar needs were batched together and
`were run through the computer as a group. Thus, the programmers would
`leave their programs with the operator. The operator would sort programs
`into batches with similar requirements and, as the computer, became available,
`would run each batch. The output from each job would be sent back to the
`appropriate programmer.
`-
`-
`_ . ~
`A batch operating system, thus, normally reads a stream of separate jobs
`(from a card reader, for example), each with its own control cards that predefine
`
`operating
`^system' „
`
`user program
`area
`
`Figure 1.2 Memory layout for a simple batch system.
`
`SAMSUNG EX. 1014 - 23/53
`
`

`

`1.2 Simple Batch Systems
`
`what the job does. When the job is complete, its output is usually printed (on a
`line printer, for example). The definitive feature of a batch system is the lack of
`interaction between the user and the job while that job is executing. The job is
`prepared and submitted, and at some later time, the output appears. The delay.
`between job submission and job completion (called turnaround time) may result
`from the amount of computing needed, or from delays before the operating
`system starts to process the job.
`In this execution environment, the CPU is often idle. This idleness occurs
`because the speeds of the mechanical I/O devices are intrinsically slower than
`those of electronic devices. Even a slow CPU works in the microsecond range,
`with thousands of instructions executed per second. A fast card reader, on the
`other hand, might read 1200 cards per minute (20 cards per second). Thus, the
`difference in speed between the CPU and its I/O devices may be three orders of
`magnitude or more. Over time, of course, improvements in technology resulted
`in faster I/O devices. Unfortunately, CPU speeds increased even faster, so that
`the problem was not only unresolved, but also exacerbated.
`The introduction of disk technology has helped in this regard. Rather than
`the cards being read from the card reader directly into memory, and then the job
`being processed, cards are read directly from the card reader onto the disk. The
`location of card images is recorded in a table kept by the operating system.
`When a job is executed, the operating system satisfies its requests for card-
`reader input by reading fr