Modern Operating Systems (5th Edition) PDF

GLOBAL EDITION Processor Management Error Memory Detection Management Functions of an Operating System File Sec...

GLOBAL EDITION Processor Management Error Memory Detection Management Functions of an Operating System File Security Management Modern Operating Systems FIFTH EDITION Tanenbaum Bos  MODERN OPERATING SYSTEMS FIFTH EDITION GLOBAL EDITION This page is intentionally left blank  MODERN OPERATING SYSTEMS FIFTH EDITION GLOBAL EDITION ANDREW S. TANENBAUM HERBERT BOS Vrije Universiteit Amsterdam, The Netherlands PEARSON HOBOKEN, NEW JERSEY 07458 Product Management: K. K. Neelakantan Production and Digital Studio: Vikram Medepalli, Supplements: Nitin Shankar Naina Singh, and Niharika Thapa Rights and Permissions: Anjali Singh and Ashish Vyas Cover image: tk Please contact https://support.pearson.com/getsupport/s/ with any queries on this content. Pearson Education Limited KAO Two KAO Park Hockham Way Harlow CM17 9SR United Kingdom and Associated Companies throughout the world Visit us on the World Wide Web at: www.pearsonglobaleditions.com © Pearson Education Limited 2024 The rights of Andrew S. Tanenbaum and Herbert Bos to be identified as the authors of this work have been asserted by them in accordance with the Copyright, Designs and Patents Act 1988. Authorized adaptation from the United States edition, entitled Modern Operating Systems, 5th Edition, ISBN 978-0-13- 761887-3 by Andrew S. Tanenbaum and Herbert Bos published by Pearson Education © 2023. All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, without either the prior written permission of the publisher or a license permitting restricted copying in the United Kingdom issued by the Copyright Licensing Agency Ltd, Saffron House, 6–10 Kirby Street, London EC1N 8TS. For information regarding permissions, request forms and the appropriate contacts within the Pearson Education Global Rights & Permissions department, please visit www.pearsoned.com/permissions/. Acknowledgments of third-party content appear on the appropriate page within the text. PEARSON and ALWAYS LEARNING are exclusive trademarks owned by Pearson Education, Inc. or its affiliates in the U.S. and/or other countries. Unless otherwise indicated herein, any third-party trademarks that may appear in this work are the property of their respective owners and any references to third-party trademarks, logos or other trade dress are for demonstrative or descriptive purposes only. Such references are not intended to imply any sponsorship, endorsement, authorization, or promotion of Pearson’s products by the owners of such marks, or any relationship between the owner and Pearson Education, Inc. or its affiliates, authors, licensees, or distributors. This eBook is a standalone product and may or may not include all assets that were part of the print version. It also does not provide access to other Pearson digital products like MyLab and Mastering. The publisher reserves the right to remove any material in this eBook at any time. ISBN 10: 1-292-45966-2 ISBN 13: 978-1-292-45966-0 eBook ISBN 13: 978-1-292-72789-9 British Library Cataloguing-in-Publication Data A catalogue record for this book is available from the British Library To Suzanne, Barbara, Aron, Nathan, Marvin, Matilde, Olivia and Mirte. (AST) To Marieke, Duko, Jip, Loeka and Spot. (HB) This page is intentionally left blank  CONTENTS PREFACE xxiii 1 INTRODUCTION 1 1.1 WHAT IS AN OPERATING SYSTEM? 4 1.1.1 The Operating System as an Extended Machine 4 1.1.2 The Operating System as a Resource Manager 6 1.2 HISTORY OF OPERATING SYSTEMS 7 1.2.1 The First Generation (1945–1955): Vacuum Tubes 8 1.2.2 The Second Generation (1955–1965): Transistors and Batch Systems 8 1.2.3 The Third Generation (1965–1980): ICs and Multiprogramming 10 1.2.4 The Fourth Generation (1980–Present): Personal Computers 15 1.2.5 The Fifth Generation (1990–Present): Mobile Computers 19 1.3 COMPUTER HARDWARE REVIEW 20 1.3.1 Processors 20 1.3.2 Memory 24 1.3.3 Nonvolatile Storage 28 1.3.4 I/O Devices 29 1.3.5 Buses 33 1.3.6 Booting the Computer 34 vii viii CONTENTS 1.4 THE OPERATING SYSTEM ZOO 36 1.4.1 Mainframe Operating Systems 36 1.4.2 Server Operating Systems 37 1.4.3 Personal Computer Operating Systems 37 1.4.4 Smartphone and Handheld Computer Operating Systems 37 1.4.5 The Internet of Things and Embedded Operating Systems 37 1.4.6 Real-Time Operating Systems 38 1.4.7 Smart Card Operating Systems 39 1.5 OPERATING SYSTEM CONCEPTS 39 1.5.1 Processes 39 1.5.2 Address Spaces 41 1.5.3 Files 42 1.5.4 Input/Output 45 1.5.5 Protection 46 1.5.6 The Shell 46 1.5.7 Ontogeny Recapitulates Phylogeny 47 1.6 SYSTEM CALLS 50 1.6.1 System Calls for Process Management 53 1.6.2 System Calls for File Management 57 1.6.3 System Calls for Directory Management 58 1.6.4 Miscellaneous System Calls 60 1.6.5 The Windows API 60 1.7 OPERATING SYSTEM STRUCTURE 63 1.7.1 Monolithic Systems 63 1.7.2 Layered Systems 64 1.7.3 Microkernels 66 1.7.4 Client-Server Model 68 1.7.5 Virtual Machines 69 1.7.6 Exokernels and Unikernels 73 1.8 THE WORLD ACCORDING TO C 74 1.8.1 The C Language 74 1.8.2 Header Files 75 1.8.3 Large Programming Projects 76 1.8.4 The Model of Run Time 78 1.9 RESEARCH ON OPERATING SYSTEMS 78 1.10 OUTLINE OF THE REST OF THIS BOOK 79  CONTENTS ix 1.11 METRIC UNITS 80 1.12 SUMMARY 81 2 PROCESSES AND THREADS 85 2.1 PROCESSES 85 2.1.1 The Process Model 86 2.1.2 Process Creation 88 2.1.3 Process Termination 90 2.1.4 Process Hierarchies 91 2.1.5 Process States 92 2.1.6 Implementation of Processes 94 2.1.7 Modeling Multiprogramming 95 2.2 THREADS 97 2.2.1 Thread Usage 97 2.2.2 The Classical Thread Model 102 2.2.3 POSIX Threads 106 2.2.4 Implementing Threads in User Space 107 2.2.5 Implementing Threads in the Kernel 111 2.2.6 Hybrid Implementations 112 2.2.7 Making Single-Threaded Code Multithreaded 113 2.3 EVENT-DRIVEN SERVERS 116 2.4 SYNCHRONIZATION AND INTERPROCESS COMMUNICATION 119 2.4.1 Race Conditions 119 2.4.2 Critical Regions 120 2.4.3 Mutual Exclusion with Busy Waiting 121 2.4.4 Sleep and Wakeup 127 2.4.5 Semaphores 129 2.4.6 Mutexes 134 2.4.7 Monitors 138 2.4.8 Message Passing 145 2.4.9 Barriers 148 2.4.10 Priority Inversion 150 2.4.11 Avoiding Locks: Read-Copy-Update 151 x CONTENTS 2.5 SCHEDULING 152 2.5.1 Introduction to Scheduling 153 2.5.2 Scheduling in Batch Systems 160 2.5.3 Scheduling in Interactive Systems 162 2.5.4 Scheduling in Real-Time Systems 168 2.5.5 Policy Versus Mechanism 169 2.5.6 Thread Scheduling 169 2.6 RESEARCH ON PROCESSES AND THREADS 171 2.7 SUMMARY 172 3 MEMORY MANAGEMENT 179 3.1 NO MEMORY ABSTRACTION 180 3.1.1 Running Multiple Programs Without a Memory Abstraction 181 3.2 A MEMORY ABSTRACTION: ADDRESS SPACES 183 3.2.1 The Notion of an Address Space 184 3.2.2 Swapping 185 3.2.3 Managing Free Memory 188 3.3 VIRTUAL MEMORY 192 3.3.1 Paging 193 3.3.2 Page Tables 196 3.3.3 Speeding Up Paging 200 3.3.4 Page Tables for Large Memories 203 3.4 PAGE REPLACEMENT ALGORITHMS 207 3.4.1 The Optimal Page Replacement Algorithm 208 3.4.2 The Not Recently Used Page Replacement Algorithm 209 3.4.3 The First-In, First-Out (FIFO) Page Replacement Algorithm 210 3.4.4 The Second-Chance Page Replacement Algorithm 210 3.4.5 The Clock Page Replacement Algorithm 211 3.4.6 The Least Recently Used (LRU) Page Replacement Algorithm 212 3.4.7 Simulating LRU in Software 212 3.4.8 The Working Set Page Replacement Algorithm 214 3.4.9 The WSClock Page Replacement Algorithm 218 3.4.10 Summary of Page Replacement Algorithms 220  CONTENTS xi 3.5 DESIGN ISSUES FOR PAGING SYSTEMS 221 3.5.1 Local versus Global Allocation Policies 221 3.5.2 Load Control 224 3.5.3 Cleaning Policy 225 3.5.4 Page Size 226 3.5.5 Separate Instruction and Data Spaces 227 3.5.6 Shared Pages 228 3.5.7 Shared Libraries 230 3.5.8 Mapped Files 232 3.6 IMPLEMENTATION ISSUES 232 3.6.1 Operating System Involvement with Paging 232 3.6.2 Page Fault Handling 233 3.6.3 Instruction Backup 234 3.6.4 Locking Pages in Memory 236 3.6.5 Backing Store 236 3.6.6 Separation of Policy and Mechanism 238 3.7 SEGMENTATION 240 3.7.1 Implementation of Pure Segmentation 242 3.7.2 Segmentation with Paging: MULTICS 243 3.7.3 Segmentation with Paging: The Intel x86 248 3.8 RESEARCH ON MEMORY MANAGEMENT 248 3.9 SUMMARY 250 4 FILE SYSTEMS 259 4.1 FILES 261 4.1.1 File Naming 261 4.1.2 File Structure 263 4.1.3 File Types 264 4.1.4 File Access 266 4.1.5 File Attributes 267 4.1.6 File Operations 269 4.1.7 An Example Program Using File-System Calls 270 xii CONTENTS 4.2 DIRECTORIES 272 4.2.1 Single-Level Directory Systems 272 4.2.2 Hierarchical Directory Systems 273 4.2.3 Path Names 274 4.2.4 Directory Operations 277 4.3 FILE-SYSTEM IMPLEMENTATION 278 4.3.1 File-System Layout 278 4.3.2 Implementing Files 280 4.3.3 Implementing Directories 285 4.3.4 Shared Files 288 4.3.5 Log-Structured File Systems 290 4.3.6 Journaling File Systems 292 4.3.7 Flash-based File Systems 293 4.3.8 Virtual File Systems 298 4.4 FILE-SYSTEM MANAGEMENT AND OPTIMIZATION 301 4.4.1 Disk-Space Management 301 4.4.2 File-System Backups 307 4.4.3 File-System Consistency 312 4.4.4 File-System Performance 315 4.4.5 Defragmenting Disks 320 4.4.6 Compression and Deduplication 321 4.4.7 Secure File Deletion and Disk Encryption 322 4.5 EXAMPLE FILE SYSTEMS 324 4.5.1 The MS-DOS File System 324 4.5.2 The UNIX V7 File System 327 4.6 RESEARCH ON FILE SYSTEMS 330 4.7 SUMMARY 331 5 INPUT/OUTPUT 337 5.1 PRINCIPLES OF I/O HARDWARE 337 5.1.1 I/O Devices 338 5.1.2 Device Controllers 338 5.1.3 Memory-Mapped I/O 340  CONTENTS xiii 5.1.4 Direct Memory Access 344 5.1.5 Interrupts Revisited 347 5.2 PRINCIPLES OF I/O SOFTWARE 352 5.2.1 Goals of the I/O Software 352 5.2.2 Programmed I/O 354 5.2.3 Interrupt-Driven I/O 355 5.2.4 I/O Using DMA 356 5.3 I/O SOFTWARE LAYERS 357 5.3.1 Interrupt Handlers 357 5.3.2 Device Drivers 359 5.3.3 Device-Independent I/O Software 362 5.3.4 User-Space I/O Software 368 5.4 MASS STORAGE: DISK AND SSD 370 5.4.1 Magnetic Disks 370 5.4.2 Solid State Drives (SSDs) 381 5.4.3 RAID 385 5.5 CLOCKS 390 5.5.1 Clock Hardware 390 5.5.2 Clock Software 391 5.5.3 Soft Timers 394 5.6 USER INTERFACES: KEYBOARD, MOUSE, & MONITOR 395 5.6.1 Input Software 396 5.6.2 Output Software 402 5.7 THIN CLIENTS 419 5.8 POWER MANAGEMENT 420 5.8.1 Hardware Issues 421 5.8.2 Operating System Issues 422 5.8.3 Application Program Issues 428 5.9 RESEARCH ON INPUT/OUTPUT 428 5.10 SUMMARY 430 xiv CONTENTS 6 DEADLOCKS 437 6.1 RESOURCES 438 6.1.1 Preemptable and Nonpreemptable Resources 438 6.1.2 Resource Acquisition 439 6.1.3 The Dining Philosophers Problem 440 6.2 INTRODUCTION TO DEADLOCKS 444 6.2.1 Conditions for Resource Deadlocks 445 6.2.2 Deadlock Modeling 445 6.3 THE OSTRICH ALGORITHM 447 6.4 DEADLOCK DETECTION AND RECOVERY 449 6.4.1 Deadlock Detection with One Resource of Each Type 449 6.4.2 Deadlock Detection with Multiple Resources of Each Type 451 6.4.3 Recovery from Deadlock 454 6.5 DEADLOCK AVOIDANCE 455 6.5.1 Resource Trajectories 456 6.5.2 Safe and Unsafe States 457 6.5.3 The Banker’s Algorithm for a Single Resource 458 6.5.4 The Banker’s Algorithm for Multiple Resources 459 6.6 DEADLOCK PREVENTION 461 6.6.1 Attacking the Mutual-Exclusion Condition 461 6.6.2 Attacking the Hold-and-Wait Condition 462 6.6.3 Attacking the No-Preemption Condition 462 6.6.4 Attacking the Circular Wait Condition 463 6.7 OTHER ISSUES 464 6.7.1 Two-Phase Locking 464 6.7.2 Communication Deadlocks 465 6.7.3 Livelock 467 6.7.4 Starvation 468 6.8 RESEARCH ON DEADLOCKS 469 6.9 SUMMARY 470  CONTENTS xv 7 VIRTUALIZATION AND THE CLOUD 477 7.1 HISTORY 480 7.2 REQUIREMENTS FOR VIRTUALIZATION 482 7.3 TYPE 1 AND TYPE 2 HYPERVISORS 484 7.4 TECHNIQUES FOR EFFICIENT VIRTUALIZATION 486 7.4.1 Virtualizing the Unvirtualizable 487 7.4.2 The Cost of Virtualization 489 7.5 ARE HYPERVISORS MICROKERNELS DONE RIGHT? 490 7.6 MEMORY VIRTUALIZATION 493 7.7 I/O VIRTUALIZATION 497 7.8 VIRTUAL MACHINES ON MULTICORE CPUS 501 7.9 CLOUDS 501 7.9.1 Clouds as a Service 502 7.9.2 Virtual Machine Migration 503 7.9.3 Checkpointing 504 7.10 OS-LEVEL VIRTUALIZATION 504 7.11 CASE STUDY: VMWARE 507 7.11.1 The Early History of VMware 507 7.11.2 VMware Workstation 509 7.11.3 Challenges in Bringing Virtualization to the x86 509 7.11.4 VMware Workstation: Solution Overview 511 7.11.5 The Evolution of VMware Workstation 520 7.11.6 ESX Server: VMware’s type 1 Hypervisor 521 7.12 RESEARCH ON VIRTUALIZATION AND THE CLOUD 523 7.13 SUMMARY 524 xvi CONTENTS 8 MULTIPLE PROCESSOR SYSTEMS 527 8.1 MULTIPROCESSORS 530 8.1.1 Multiprocessor Hardware 530 8.1.2 Multiprocessor Operating System Types 541 8.1.3 Multiprocessor Synchronization 545 8.1.4 Multiprocessor Scheduling 550 8.2 MULTICOMPUTERS 557 8.2.1 Multicomputer Hardware 558 8.2.2 Low-Level Communication Software 562 8.2.3 User-Level Communication Software 565 8.2.4 Remote Procedure Call 569 8.2.5 Distributed Shared Memory 571 8.2.6 Multicomputer Scheduling 575 8.2.7 Load Balancing 576 8.3 DISTRIBUTED SYSTEMS 579 8.3.1 Network Hardware 581 8.3.2 Network Services and Protocols 585 8.3.3 Document-Based Middleware 588 8.3.4 File-System-Based Middleware 590 8.3.5 Object-Based Middleware 594 8.3.6 Coordination-Based Middleware 595 8.4 RESEARCH ON MULTIPLE PROCESSOR SYSTEMS 598 8.5 SUMMARY 600 9 SECURITY 605 9.1 FUNDAMENTALS OF OPERATING SYSTEM SECURITY 607 9.1.1 The CIA Security Triad 608 9.1.2 Security Principles 609 9.1.3 Security of the Operating System Structure 611 9.1.4 Trusted Computing Base 612 9.1.5 Attackers 614 9.1.6 Can We Build Secure Systems? 617  CONTENTS xvii 9.2 CONTROLLING ACCESS TO RESOURCES 618 9.2.1 Protection Domains 619 9.2.2 Access Control Lists 621 9.2.3 Capabilities 625 9.3 FORMAL MODELS OF SECURE SYSTEMS 628 9.3.1 Multilevel Security 629 9.3.2 Cryptography 632 9.3.3 Trusted Platform Modules 636 9.4 AUTHENTICATION 637 9.4.1 Passwords 637 9.4.2 Authentication Using a Physical Object 644 9.4.3 Authentication Using Biometrics 645 9.5 EXPLOITING SOFTWARE 647 9.5.1 Buffer Overflow Attacks 648 9.5.2 Format String Attacks 658 9.5.3 Use-After-Free Attacks 661 9.5.4 Type Confusion Vulnerabilities 662 9.5.5 Null Pointer Dereference Attacks 664 9.5.6 Integer Overflow Attacks 665 9.5.7 Command Injection Attacks 666 9.5.8 Time of Check to Time of Use Attacks 667 9.5.9 Double Fetch Vulnerability 668 9.6 EXPLOITING HARDWARE 668 9.6.1 Covert Channels 669 9.6.2 Side Channels 671 9.6.3 Transient Execution Attacks 674 9.7 INSIDER ATTACKS 679 9.7.1 Logic Bombs 679 9.7.2 Back Doors 680 9.7.3 Login Spoofing 681 9.8 OPERATING SYSTEM HARDENING 681 9.8.1 Fine-Grained Randomization 682 9.8.2 Control-Flow Restrictions 683 9.8.3 Access Restrictions 685 9.8.4 Code and Data Integrity Checks 689 9.8.5 Remote Attestation Using a Trusted Platform Module 690 9.8.6 Encapsulating Untrusted Code 691 xviii CONTENTS 9.9 RESEARCH ON SECURITY 694 9.10 SUMMARY 696 10 CASE STUDY 1: UNIX, LINUX, AND ANDROID 703 10.1 HISTORY OF UNIX AND LINUX 704 10.1.1 UNICS 704 10.1.2 PDP-11 UNIX 705 10.1.3 Portable UNIX 706 10.1.4 Berkeley UNIX 707 10.1.5 Standard UNIX 708 10.1.6 MINIX 709 10.1.7 Linux 710 10.2 OVERVIEW OF LINUX 713 10.2.1 Linux Goals 713 10.2.2 Interfaces to Linux 714 10.2.3 The Shell 716 10.2.4 Linux Utility Programs 719 10.2.5 Kernel Structure 720 10.3 PROCESSES IN LINUX 723 10.3.1 Fundamental Concepts 724 10.3.2 Process-Management System Calls in Linux 726 10.3.3 Implementation of Processes and Threads in Linux 730 10.3.4 Scheduling in Linux 736 10.3.5 Synchronization in Linux 740 10.3.6 Booting Linux 741 10.4 MEMORY MANAGEMENT IN LINUX 743 10.4.1 Fundamental Concepts 744 10.4.2 Memory Management System Calls in Linux 746 10.4.3 Implementation of Memory Management in Linux 748 10.4.4 Paging in Linux 754 10.5 INPUT/OUTPUT IN LINUX 757 10.5.1 Fundamental Concepts 758 10.5.2 Networking 759  CONTENTS xix 10.5.3 Input/Output System Calls in Linux 761 10.5.4 Implementation of Input/Output in Linux 762 10.5.5 Modules in Linux 765 10.6 THE LINUX FILE SYSTEM 766 10.6.1 Fundamental Concepts 766 10.6.2 File-System Calls in Linux 770 10.6.3 Implementation of the Linux File System 774 10.6.4 NFS: The Network File System 783 10.7 SECURITY IN LINUX 789 10.7.1 Fundamental Concepts 789 10.7.2 Security System Calls in Linux 791 10.7.3 Implementation of Security in Linux 792 10.8 ANDROID 793 10.8.1 Android and Google 794 10.8.2 History of Android 794 10.8.3 Design Goals 800 10.8.4 Android Architecture 801 10.8.5 Linux Extensions 803 10.8.6 ART 807 10.8.7 Binder IPC 809 10.8.8 Android Applications 818 10.8.9 Intents 830 10.8.10 Process Model 831 10.8.11 Security and Privacy 836 10.8.12 Background Execution and Social Engineering 856 10.9 SUMMARY 863 11 CASE STUDY 2: WINDOWS 11 871 11.1 HISTORY OF WINDOWS THROUGH WINDOWS 11 871 11.1.1 1980s: MS-DOS 872 11.1.2 1990s: MS-DOS-based Windows 873 11.1.3 2000s: NT-based Windows 873 11.1.4 Windows Vista 876 11.1.5 Windows 8 877 xx CONTENTS 11.1.6 Windows 10 878 11.1.7 Windows 11 879 11.2 PROGRAMMING WINDOWS 880 11.2.1 Universal Windows Platform 881 11.2.2 Windows Subsystems 883 11.2.3 The Native NT Application Programming Interface 884 11.2.4 The Win32 Application Programming Interface 887 11.2.5 The Windows Registry 891 11.3 SYSTEM STRUCTURE 894 11.3.1 Operating System Structure 894 11.3.2 Booting Windows 910 11.3.3 Implementation of the Object Manager 914 11.3.4 Subsystems, DLLs, and User-Mode Services 926 11.4 PROCESSES AND THREADS IN WINDOWS 929 11.4.1 Fundamental Concepts 929 11.4.2 Job, Process, Thread, and Fiber Management API Calls 934 11.4.3 Implementation of Processes and Threads 941 11.4.4 WoW64 and Emulation 950 11.5 MEMORY MANAGEMENT 955 11.5.1 Fundamental Concepts 955 11.5.2 Memory-Management System Calls 961 11.5.3 Implementation of Memory Management 962 11.5.4 Memory Compression 973 11.5.5 Memory Partitions 976 11.6 CACHING IN WINDOWS 977 11.7 INPUT/OUTPUT IN WINDOWS 979 11.7.1 Fundamental Concepts 980 11.7.2 Input/Output API Calls 982 11.7.3 Implementation of I/O 984 11.8 THE WINDOWS NT FILE SYSTEM 989 11.8.1 Fundamental Concepts 989 11.8.2 Implementation of the NT File System 990 11.9 WINDOWS POWER MANAGEMENT 1000  CONTENTS xxi 11.10 VIRTUALIZATION IN WINDOWS 1003 11.10.1 Hyper-V 1003 11.10.2 Containers 1011 11.10.3 Virtualization-Based Security 1017 11.11 SECURITY IN WINDOWS 1018 11.11.1 Fundamental Concepts 1020 11.11.2 Security API Calls 1022 11.11.3 Implementation of Security 1023 11.11.4 Security Mitigations 1025 11.12 SUMMARY 1035 12 OPERATING SYSTEM DESIGN 1041 12.1 THE NATURE OF THE DESIGN PROBLEM 1042 12.1.1 Goals 1042 12.1.2 Why Is It Hard to Design an Operating System? 1043 12.2 INTERFACE DESIGN 1045 12.2.1 Guiding Principles 1045 12.2.2 Paradigms 1048 12.2.3 The System-Call Interface 1051 12.3 IMPLEMENTATION 1053 12.3.1 System Structure 1054 12.3.2 Mechanism vs. Policy 1057 12.3.3 Orthogonality 1058 12.3.4 Naming 1059 12.3.5 Binding Time 1061 12.3.6 Static vs. Dynamic Structures 1062 12.3.7 Top-Down vs. Bottom-Up Implementation 1063 12.3.8 Synchronous vs. Asynchronous Communication 1064 12.3.9 Useful Techniques 1065 12.4 PERFORMANCE 1070 12.4.1 Why Are Operating Systems Slow? 1071 12.4.2 What Should Be Optimized? 1071 12.4.3 Space-Time Trade-offs 1072 xxii CONTENTS 12.4.4 Caching 1075 12.4.5 Hints 1076 12.4.6 Exploiting Locality 1077 12.4.7 Optimize the Common Case 1077 12.5 PROJECT MANAGEMENT 1078 12.5.1 The Mythical Man Month 1078 12.5.2 Team Structure 1079 12.5.3 The Role of Experience 1081 12.5.4 No Silver Bullet 1082 13 READING LIST AND BIBLIOGRAPHY 1087 13.1 SUGGESTIONS FOR FURTHER READING 1087 13.1.1 Introduction 1088 13.1.2 Processes and Threads 1088 13.1.3 Memory Management 1089 13.1.4 File Systems 1090 13.1.5 Input/Output 1090 13.1.6 Deadlocks 1091 13.1.7 Virtualization and the Cloud 1092 13.1.8 Multiple Processor Systems 1093 13.1.9 Security 1093 13.1.10 Case Study 1: UNIX, Linux, and Android 1094 13.1.11 Case Study 2: Windows 1095 13.1.12 Operating System Design 1096 13.2 ALPHABETICAL BIBLIOGRAPHY 1097 INDEX 1121  PREFACE The fifth edition of this book differs from the fourth edition in many ways. There are large numbers of small changes everywhere to bring the material up to date as operating systems are not standing still. For example, where the previous edition focused almost exclusively on magnetic hard disks for storage, this time we give the flash-based Solid State Drives (SSDs) the attention that befits their popu- larity. The chapter on Windows 8.1 has been replaced entirely by a chapter on the new Windows 11. We have rewritten much of the security chapter, with more focus on topics that are directly relevant for operating systems (and exciting new attacks and defenses), while reducing the discussion of cryptography and steganog- raphy. Here is a chapter-by-chapter rundown of the changes. Chapter 1 has been heavily modified and updated in many places, but with the exception of dropping the description of CD-ROMs and DVDs in favor of modern storage solutions such as SSDs and persis- tent memory, no major sections have been added or deleted. In Chapter 2, we significantly expanded the discussion of event-driven servers and included an extensive example with pseudo code. We gave priority inversion its own section where we also discussed ways to deal with the problem. We reordered some of the sections to clarify the dis- cussion. For instance, we now discuss the readers-writers problem xxiii xxiv PREFACE immediately after the producer-consumer section and moved the din- ing philosophers to another chapter, that of deadlocks, entirely. Be- sides numerous smaller updates, we also dropped some older material, such as scheduler activations and pop-up threads. Chapter 3 now focuses on modern 64-bit architectures and contains more precise explanations of many aspects of paging and TLBs. For instance, we describe how operating systems use paging also and how some operating systems map the kernel into the address spaces of user processes. Chapter 4 changed significantly. We dropped the lengthy descriptions of CD-ROMs and tapes, and instead added sections about SSD-based file systems, booting in modern UEFI-based computer systems, and secure file deletion and disk encryption. In Chapter 5, we have more information about SSDs and NVMe, and explain input devices using a modern USB keyboard instead of the older PS/2 one of the previous edition. In addition, we clarify the rela- tion between interrupts, traps, exceptions, and faults. As mentioned, we added the dining philosophers example to Chapter 6. Other than that, the chapter is pretty much unchanged. The topic of deadlocks is fairly stable, with few new results. In Chapter 7, we added a section about containers to the existing (and updated) explanation of hypervisor-based virtualization. The material on VMware has also been brought up to date. Chapter 8 is an updated version of the previous material on multiproc- essor systems. We added subsections on simultaneous multithreading and discuss new types of coprocessors, while dropping sections such as the one on the older IXP network processors and the one on the (now dead) CORBA middleware. A new section discusses scheduling for security. Chapter 9 has been heavily revised and reorganized, with much more focus on what is relevant for the operating system and less emphasis on crypto. We now start the chapter with a discussion of principles for secure design and their relevance for the operating system structure. We discuss exciting new hardware developments, such as the Melt- down and Spectre transient execution vulnerabilities, that have come to light since the previous edition. In addition, we describe new software vulnerabilities that are important for the operating system. Finally, we greatly expanded the description of the ways in which the operating system can be hardened, with extensive discussion of control flow integrity, fine-grained ASLR, code signing, access restrictions, and  PREFACE xxv attestation. Since there is much ongoing research in this area, new ref- erences have been added and the research section has been rewritten. Chapter 10 has been updated with new developments in Linux and Android. Android has evolved considerably since the previous edition, and this chapter covers the current version in detail. This section has been substantially rewritten. Chapter 11 has changed significantly. Where the fourth edition was on Windows 8.1, we now discuss Windows 11. It is basically a new chap- ter. Chapter 12 is a slightly revised version of the previous edition. This chapter covers the basic principles of system design, and they have not changed much in the past few years. Chapter 13 is a thoroughly updated list of suggested readings. In addi- tion, the list of references has been updated, with entries to well over 100 new works published after the fourth edition of this book came out. In addition, the sections on research throughout the book have all been redone from scratch to reflect the latest research in operating systems. Furthermore, new problems have been added to all the chapters. Instructor supplements (including the PowerPoint sheets) can be found at http://www.pearsonglobaleditions.com. A number of people have been involved in the fifth edition. The material in Chap. 7 on VMware (in Sec. 7.12) was written by Edouard Bugnion of EPFL in Lausanne, Switzerland. Ed was one of the founders of the VMware company and knows this material as well as anyone in the world. We thank him greatly for sup- plying it to us. Ada Gavrilovska of Georgia Tech, who is an expert on Linux internals, up- dated Chap. 10 from the Fourth Edition, which she also wrote. The Android ma- terial in Chap. 10 was written by Dianne Hackborn of Google, one of the key developers of the Android system. Android is the most popular operating system on smartphones, so we are very grateful to have Dianne help us. Chapter 10 is now quite long and detailed, but UNIX, Linux, and Android fans can learn a lot from it. We haven’t neglected Windows, however. Mehmet Iyigun of Microsoft up- dated Chap. 11 from the previous edition of the book. This time the chapter covers Windows 11 in detail. Mehmet has a great deal of knowledge of Windows and enough vision to tell the difference between places where Microsoft got it right and where it got it wrong. He was ably assisted by Andrea Allievi, Pedro Justo, Chris Kleynhans, and Erick Smith. Windows fans are certain to enjoy this chapter. The book is much better as a result of the work of all these expert contributors. Again, we would like to thank them for their invaluable help. xxvi PREFACE We were also fortunate to have several reviewers who read the manuscript and also suggested new end-of-chapter problems. They were Jeremiah Blanchard (University of Florida), Kate Holdener (St. Louis University), Liting Hu (Virginia Tech), Jiang-Bo Liu (Bradley University), and Mai Zheng (Iowa State University). We remain responsible for any remaining errors, of course. Several people at the VUSec group at Vrije Universiteit Amsterdam also played an important role in this edition. We are grateful to Cristiano Giuffrida for his many excellent suggestions of things to add to or remove from the previous text. Meanwhile, Erik van der Kouwe, Sebastian Osterlund, Johannes Blaser were amazing in how fast they provided fantastic feedback on all the new bits in the security chapter. We would also like to thank our editor, Tracy Johnson, for keeping the project on track and herding all the cats, albeit virtually this time. Erin Sullivan managed the review process and Carole Snyder handled production. Finally, last but not least, Barbara, Marvin, and Matilde are still wonderful, as usual, each in a unique and special way. Aron and Nathan are great kids and Olivia and Mirte are treasures. And of course, I would like to thank Suzanne for her love and patience, not to mention all the druiven, kersen, and sinaasappelsap, as well as other agricultural products. (AST) As always, I owe a massive thank you to Marieke, Duko, and Jip. Marieke for just being there and for bearing with me in the countless hours that I was working on this book, and Duko and Jip for tearing me away from it to play hoops, day and night! I am also grateful to the neighbors for putting up with our midnight basket- ball games. (HB) Andrew S. Tanenbaum Herbert Bos  PREFACE xxvii ABOUT THE AUTHORS Andrew S. Tanenbaum has an S.B. degree from M.I.T. and a Ph.D. from the University of California at Berkeley. He is currently a Professor Emeritus of Com- puter Science at the Vrije Universiteit in Amsterdam, the Netherlands. He was formerly Dean of the Advanced School for Computing and Imaging, an interuni- versity graduate school doing research on advanced parallel, distributed, and imag- ing systems. He was also an Academy Professor of the Royal Netherlands Acade- my of Arts and Sciences, which has saved him from turning into a bureaucrat. He also won a prestigious European Research Council Advanced Grant. In the past, he has done research on compilers, reliable operating systems, net- working, and distributed systems. This research has led to over 200 refereed pub- lications in journals and conferences. Prof. Tanenbaum has also authored or co- authored five books, which have been translated into over 20 languages, ranging from Basque to Thai. They are used at universities all over the world. There are 163 versions of his books. Prof. Tanenbaum has also produced a considerable volume of software, no- tably MINIX, a small UNIX clone. It was the direct inspiration for Linux and the platform on which Linux was initially developed. The current version of MINIX, called MINIX 3, is now focused on being an extremely reliable and secure operat- ing system. Prof. Tanenbaum will consider his work done when no user has any idea what an operating system crash is. MINIX 3 is an ongoing open-source pro- ject to which you are invited to contribute. Go to www.minix3.org to download a free copy of MINIX 3 and give it a try. Both x86 and ARM versions are available. Prof. Tanenbaum’s Ph.D. students have gone on to greater glory after graduat- ing. Some have become professors; others have fulfilled leading roles in govern- ment organizations and industry. He is very proud of them. In this respect, he resembles a mother hen. Prof. Tanenbaum is a Fellow of the ACM, a Fellow of the IEEE, and a member of the Royal Netherlands Academy of Arts and Sciences. He has also won numer- ous scientific prizes from ACM, IEEE, and USENIX. If you are unbearably curi- ous about them, see his page on Wikipedia. He also has two honorary doctorates. Herbert Bos obtained his Master’s degree from Twente University and his Ph.D. from Cambridge University in the United Kingdom. Since then, he has worked extensively on dependable and efficient I/O architectures for operating sys- tems like Linux, but also research systems based on MINIX 3. He is currently a professor at the VUSec Systems Security Research Group in the Department of Computer Science at the Vrije Universiteit in Amsterdam, the Netherlands. His main research field is systems security. With his group, he discovered and analyzed many vulnerabilities in both hard- ware and software. From buggy memory chips to vulnerable CPUs, and from flaws in operating systems to novel exploitation techniques, the research has led to fixes xxviii PREFACE in most major operating systems, most popular browsers, and all modern Intel processors. He believes that offensive research is valuable because the main reason for today’s security problems is that systems have become so complex that we no longer understand them. By investigating how we can make systems behave in unintended ways, we learn more about their (real) nature. Armed with this know- ledge, developers can then improve their designs in the future. Indeed, while sophisticated new attacks tend to feature prominently in the media, Herbert spends most of his time on developing defensive techniques to improve the security. His (former) students are all awesome and much cleverer than he is. With them, he has won five Pwnie Awards at the Black Hat conference in Las Vegas. Moreover, five of his students have won the ACM SIGOPS EuroSys Roger Need- ham Award for best European Ph.D. thesis in systems, two of them have won the ACM SIGSAC Doctoral Dissertation Award for best Ph.D. thesis in security, and two more won the William C. Carter Ph.D. Dissertation Award for their work on dependability. Herbert worries about climate change and loves the Beatles.  1 INTRODUCTION A modern computer consists of one or more processors, some amount of main memory, hard disks or Flash drives, printers, a keyboard, a mouse, a display, net- work interfaces, and various other input/output devices. All in all, a complex sys- tem. If every application programmer had to understand how all these things work in detail, no code would ever get written. Furthermore, managing all these compo- nents and using them optimally is an exceedingly challenging job. For this reason, computers are equipped with a layer of software called the operating system, whose job is to provide user programs with a better, simpler, cleaner, model of the computer and to handle managing all the resources just mentioned. Operating sys- tems are the subject of this book. It is important to realize that smart phones and tablets (like the Apple iPad) are just computers in a smaller package with a touch screen. They all have operating systems. In fact, Apple’s iOS is fairly similar to macOS, which runs on Apple’s desktop and MacBook systems. The smaller form factor and touch screen really doesn’t change that much about what the operating system does. Android smart- phones and tablets all run Linux as the true operating system on the bare hardware. What users perceive as ‘‘Android’’ is simply a layer of software running on top of Linux. Since macOS (and thus iOS) is derived from Berkeley UNIX and Linux is a clone of UNIX, by far the most popular operating system in the world is UNIX and its variants. For this reason, we will pay a lot of attention in this book to UNIX. Most readers probably have had some experience with an operating system such as Windows, Linux, FreeBSD, or macOS, but appearances can be deceiving. 1 2 INTRODUCTION CHAP. 1 The program that users interact with, usually called the shell when it is text based and the GUI (Graphical User Interface) (which is pronounced ‘‘gooey’’) when it uses icons, is actually not part of the operating system, although it uses the operat- ing system to get its work done. A simple overview of the main components under discussion here is given in Fig. 1-1. Here we see the hardware at the bottom. The hardware consists of chips, boards, Flash drives, disks, a keyboard, a monitor, and similar physical objects. On top of the hardware is the software. Most computers have two modes of operation: kernel mode and user mode. The operating system, the most fundamental piece of software, runs in kernel mode (also called supervisor mode) for at least some of its functionality. In this mode, it has complete access to all the hardware and can execute any instruction the machine is capable of executing. The rest of the soft- ware runs in user mode, in which only a subset of the machine instructions is available. In particular, those instructions that affect control of the machine, deter- mine the security boundaries, or do I/O (Input/Output) are forbidden to user- mode programs. We will come back to the difference between kernel mode and user mode repeatedly throughout this book. It plays a crucial role in how operating systems work. E-mail Music Web reader player browser User mode User interface program Software Kernel mode Operating system Hardware Figure 1-1. Where the operating system fits in. The user interface program, shell or GUI, is the lowest level of user-mode soft- ware, and allows the user to start other programs, such as a Web browser, email reader, or music player. These programs, too, make heavy use of the operating sys- tem. The placement of the operating system is shown in Fig. 1-1. It runs on the bare hardware and provides the base for all the other software. An important distinction between the operating system and normal (user- mode) software is that if a user does not like a particular email reader, she is free to get a different one or write her own if she so chooses; she is typically not free to write her own clock interrupt handler, which is part of the operating system and is  INTRODUCTION 3 protected by hardware against attempts by users to modify it. This distinction, however, is sometimes blurred, for instance in embedded systems (which may not have kernel mode) or interpreted systems (such as Java-based systems that use interpretation, not hardware, to separate the components). Also, in many systems there are programs that run in user mode but help the operating system or perform privileged functions. For example, there is often a program that allows users to change their passwords. It is not part of the operating system and does not run in kernel mode, but it clearly carries out a sensitive func- tion and has to be protected in a special way. In some systems, this idea is carried to an extreme, and pieces of what is traditionally considered to be the operating system (such as the file system) run in user mode. In such systems, it is difficult to draw a clear boundary. Everything running in kernel mode is clearly part of the operating system, but some programs running outside it are arguably also part of it, or at least closely associated with it. Operating systems differ from user (i.e., application) programs in ways other than where they reside. In particular, they are huge, complex, and very long-lived. The source code for Windows is over 50 million lines of code. The source code for Linux is over 20 million lines of code. Both are still growing. To conceive of what this means, think of printing out 50 million lines in book form, with 50 lines per page and 1000 pages per volume (about the size of this book). Each book would contain 50,000 lines of code. It would take 1000 volumes to list an operating sys- tem of this size. Now imagine a bookcase with 20 books per shelf and seven shelves or 140 books in all. It would take a bit over seven bookcases to hold the full code of Windows 10. Can you imagine getting a job maintaining an operating system and on the first day having your boss bring you to a room with these seven bookcases of code and say: ‘‘Go learn that.’’ And this is only for the part that runs in the kernel. No one at Microsoft understands all of Windows and probably most programmers there, even kernel programmers, understand only a small part of it. When essential shared libraries are included, the source code base gets much big- ger. And this excludes basic application software (things like the browser, the media player, and so on). It should be clear now why operating systems live a long time—they are very hard to write, and having written one, the owner is loath to throw it out and start again. Instead, such systems evolve over long periods of time. Windows 95/98/Me was basically one operating system and Windows NT/2000/XP/Vista/Windows 7/8/10 is a different one. They look similar to the users because Microsoft made very sure that the user interface of Windows 2000/XP/Vista/Windows 7 was quite similar to that of the system it was replacing, mostly Windows 98. This was not necessarily the case for Windows 8 and 8.1 which introduced a variety of changes in the GUI and promptly drew criticism from users who liked to keep things the same. Windows 10 reverted some of these changes and introduced a number of improvements. Windows 11 is built upon the framework of Windows 10. We will study Windows in detail in Chap. 11. 4 INTRODUCTION CHAP. 1 Besides Windows, the other main example we will use throughout this book is UNIX and its variants and clones. It, too, has evolved over the years, with versions like FreeBSD (and essentially, macOS) being derived from the original system, whereas Linux is a fresh code base, although very closely modeled on UNIX and highly compatible with it. The huge investment needed to develop a mature and reliable operating system from scratch led Google to adopt an existing one, Linux, as the basis of its Android operating system. We will use examples from UNIX throughout this book and look at Linux in detail in Chap. 10. In this chapter, we will briefly touch on a number of key aspects of operating systems, including what they are, their history, what kinds are around, some of the basic concepts, and their structure. We will come back to many of these important topics in later chapters in more detail. 1.1 WHAT IS AN OPERATING SYSTEM? It is hard to pin down what an operating system is other than saying it is the software that runs in kernel mode—and even that is not always true. Part of the problem is that operating systems perform two essentially unrelated functions: pro- viding application programmers (and application programs, naturally) a clean ab- stract set of resources instead of the messy hardware ones and managing these hardware resources. Depending on who is doing the talking, you might hear mostly about one function or the other. Let us now look at both. 1.1.1 The Operating System as an Extended Machine The architecture (instruction set, memory organization, I/O, and bus struc- ture) of most computers at the machine-language level is primitive and awkward to program, especially for input/output. To make this point more concrete, consider modern SATA (Serial ATA) hard disks used on most computers. A book (Dem- ing, 2014) describing an early version of the interface to the disk—what a pro- grammer would have to know to use the disk—ran over 450 pages. Since then, the interface has been revised multiple times and is even more complicated than it was in 2014. Clearly, no sane programmer would want to deal with this disk at the hardware level. Instead, a piece of software, called a disk driver, deals with the hardware and provides an interface to read and write disk blocks, without getting into the details. Operating systems contain many drivers for controlling I/O devices. But even this level is much too low for most applications. For this reason, all operating systems provide yet another layer of abstraction for using disks: files. Using this abstraction, programs can create, write, and read files, without having to deal with the messy details of how the hardware actually works. SEC. 1.1 WHAT IS AN OPERATING SYSTEM? 5 This abstraction is the key to managing all this complexity. Good abstractions turn a nearly impossible task into two manageable ones. The first is defining and implementing the abstractions. The second is using these abstractions to solve the problem at hand. One abstraction that almost every computer user understands is the file, as mentioned above. It is a useful piece of information, such as a digital photo, saved email message, song, or Web page. It is much easier to deal with pho- tos, emails, songs, and Web pages than with the details of SATA (or other) disks. The job of the operating system is to create good abstractions and then implement and manage the abstract objects thus created. In this book, we will talk a lot about abstractions. They are one of the keys to understanding operating systems. This point is so important that it is worth repeating but in different words. With all due respect to the industrial engineers who so very carefully designed the Apple Macintosh computers (now known simply as ‘‘Macs’’), hardware is grotesque. Real processors, memories, Flash drives, disks, and other devices are very compli- cated and present difficult, awkward, idiosyncratic, and inconsistent interfaces to the people who have to write software to use them. Sometimes this is due to the need for backward compatibility with older hardware. Other times it is an attempt to save money. Often, however, the hardware designers do not realize (or care) how much trouble they are causing for the software. One of the major tasks of the oper- ating system is to hide the hardware and present programs (and their programmers) with nice, clean, elegant, consistent, abstractions to work with instead. Operating systems turn the awful into the beautiful, as shown in Fig. 1-2. Application programs Beautiful interface Operating system Awful interface Hardware Figure 1-2. Operating systems turn awful hardware into beautiful abstractions. It should be noted that the operating system’s real customers are the applica- tion programs (via the application programmers, of course). They are the ones who deal directly with the operating system and its abstractions. In contrast, end users deal with the abstractions provided by the user interface, either a com- mand-line shell or a graphical interface. While the abstractions at the user interface may be similar to the ones provided by the operating system, this is not always the case. To make this point clearer, consider the normal Windows desktop and the 6 INTRODUCTION CHAP. 1 line-oriented command prompt. Both are programs running on the Windows oper- ating system and use the abstractions Windows provides, but they offer very dif- ferent user interfaces. Similarly, a Linux user running Gnome or KDE sees a very different interface than a Linux user working directly on top of the underlying X Window System, but the underlying operating system abstractions are the same in both cases. In this book, we will study the abstractions provided to application programs in great detail, but say rather little about user interfaces. That is a large and important subject, but one only peripherally related to operating systems. 1.1.2 The Operating System as a Resource Manager The concept of an operating system as primarily providing abstractions to application programs is a top-down view. An alternative, bottom-up, view holds that the operating system is there to manage all the pieces of a complex system. Modern computers consist of processors, memories, timers, disks, mice, network interfaces, printers, touch screens, touch pad, and a wide variety of other devices. In the bottom-up view, the job of the operating system is to provide for an orderly and controlled allocation of the processors, memories, and I/O devices among the various programs wanting them. Modern operating systems allow multiple programs to be in memory and run at the same time. Imagine what would happen if three programs running on some computer all tried to print their output simultaneously on the same printer. The first few lines of printout might be from program 1, the next few from program 2, then some from program 3, and so forth. The result would be utter chaos. The operating system can bring order to the potential chaos by buffering all the output destined for the printer on the disk or Flash drive. When one program is finished, the operat- ing system can then copy its output from the disk file where it has been stored for the printer, while at the same time the other program can continue generating more output, oblivious to the fact that the output is not really going to the printer (yet). When a computer (or network) has more than one user, managing and protect- ing the memory, I/O devices, and other resources is even more important since the users might otherwise interfere with one another. In addition, users often need to share not only hardware, but information (files, databases, etc.) as well. In short, this view of the operating system holds that its primary task is to keep track of which programs are using which resource, to grant resource requests, to account for usage, and to mediate conflicting requests from different programs and users. Resource management includes multiplexing (sharing) resources in two dif- ferent ways: in time and in space. When a resource is time multiplexed, different programs or users take turns using it. First one of them gets to use the resource, then another, and so on. For example, with only one CPU and multiple programs that want to run on it, the operating system first allocates the CPU to one program, then, after it has run long enough, another program gets to use the CPU, then SEC. 1.1 WHAT IS AN OPERATING SYSTEM? 7 another, and then eventually the first one again. Determining how the resource is time multiplexed—who goes next and for how long—is the task of the operating system. Another example of time multiplexing is sharing the printer. When multi- ple print jobs are queued up for printing on a single printer, a decision has to be made about which one is to be printed next. The other kind of multiplexing is space multiplexing. Instead of the customers taking turns, each one gets part of the resource. For example, main memory is nor- mally divided up among several running programs, so each one can be resident at the same time (for example, in order to take turns using the CPU). Assuming there is enough memory to hold multiple programs, it is more efficient to hold several programs in memory at once rather than give one of them the entire mem, especial- ly if it only needs a small fraction of the total. Of course, this raises issues of fair- ness, protection, and so forth, and it is up to the operating system to solve them. Other resource that are space multiplexed are disks and Flash drives. In many sys- tems, a single disk can hold files from many users at the same time. Allocating disk space and keeping track of who is using which disk blocks is a typical operating system task. By the way, people commonly refer to all nonvolatile memory as ‘‘disks,’’ but in this book we try to explicitly distinguish between disks, which have spinning magnetic platters, and SSDs (Solid State Drives), which are based on Flash memory and electronic rather than mechanical. Still, from a software point of view, SSDs are similar to disks in many (but not all) ways. 1.2 HISTORY OF OPERATING SYSTEMS Operating systems have been evolving through the years. In the following sec- tions, we will briefly look at a few of the highlights. Since operating systems have historically been closely tied to the architecture of the computers on which they run, we will look at successive generations of computers to see what their operat- ing systems were like. This mapping of operating system generations to computer generations is crude, but it does provide some structure where there would other- wise be none. The progression given below is largely chronological, but it has been a bumpy ride. Each development did not wait until the previous one nicely finished before getting started. There was a lot of overlap, not to mention many false starts and dead ends. Take this as a guide, not as the last word. The first true digital computer was designed by the English mathematician Charles Babbage (1792–1871). Although Babbage spent most of his life and for- tune trying to build his ‘‘analytical engine,’’ he never got it working properly because it was purely mechanical, and the technology of his day could not produce the required wheels, gears, and cogs to the high precision that he needed. Needless to say, the analytical engine did not have an operating system. As an interesting historical aside, Babbage realized that he would need soft- ware for his analytical engine, so he hired a young woman named Ada Lovelace, 8 INTRODUCTION CHAP. 1 who was the daughter of the famed British poet Lord Byron, as the world’s first programmer. The programming language Ada® is named after her. 1.2.1 The First Generation (1945–1955): Vacuum Tubes After Babbage’s unsuccessful efforts, little progress was made in constructing digital computers until the World War II period, which stimulated an explosion of activity. Professor John Atanasoff and his graduate student Clifford Berry built what is now regarded as the first functioning digital computer at Iowa State Univer- sity. It used 300 vacuum tubes. At roughly the same time, Konrad Zuse in Berlin built the Z3 computer out of electromechanical relays. In 1944, the Colossus was built and programmed by a group of scientists (including Alan Turing) at Bletchley Park, England, the Mark I was built by Howard Aiken at Harvard, and the ENIAC was built by William Mauchley and his graduate student J. Presper Eckert at the University of Pennsylvania. Some were binary, some used vacuum tubes, some were programmable, but all were very primitive and took seconds to perform even the simplest calculation. In these early days, a single group of people (usually engineers) designed, built, programmed, operated, and maintained each machine. All programming was done in absolute machine language, or even worse yet, by wiring up electrical cir- cuits by connecting thousands of cables to plugboards to control the machine’s basic functions. Programming languages were unknown (even assembly language was unknown). Operating systems were unheard of. The usual mode of operation was for the programmer to sign up for a block of time using the signup sheet on the wall, then come down to the machine room, insert his or her plugboard into the computer, and spend the next few hours hoping that none of the 20,000 or so vac- uum tubes would burn out during the run. Virtually all the problems were simple straightforward mathematical and numerical calculations, such as grinding out tables of sines, cosines, and logarithms, or computing artillery trajectories. By the early 1950s, the routine had improved somewhat with the introduction of punched cards. It was now possible to write programs on cards and read them in instead of using plugboards; otherwise, the procedure was the same. 1.2.2 The Second Generation (1955–1965): Transistors and Batch Systems The introduction of the transistor in the mid-1950s changed the picture radi- cally. Computers became reliable enough that they could be manufactured and sold to paying customers with the expectation that they would continue to function long enough to get useful work done. For the first time, there was a clear separation between designers, builders, operators, programmers, and maintenance personnel. These machines, which are now called mainframes, were locked away in large, specially air-conditioned computer rooms, with staffs of professional opera- tors to run them. Only large corporations or government agencies or universities SEC. 1.2 HISTORY OF OPERATING SYSTEMS 9 could afford the multimillion-dollar price tag. To run a job (i.e., a program or set of programs), a programmer would first write the program on paper (in FORTRAN or assembler), then punch it on cards. The programmer would then bring the card deck down to the input room, hand it to one of the operators, and go drink coffee until the output was ready. When the computer finished whatever job it was currently running, an operator would go over to the printer and tear off the output and carry it over to the output room, so that the programmer could collect it later. Then the operator would take one of the card decks that had been brought from the input room and read it in. If the FORTRAN compiler was needed, the operator would have to get it from a file cabinet and read it in. Much computer time was wasted while operators were walk- ing around the machine room. Given the high cost of the equipment, it is not surprising that people quickly looked for ways to reduce the wasted time. The solution generally adopted was the batch system. The idea behind it was to collect a tray full of jobs in the input room and then read them onto a magnetic tape using a small (relatively) inexpen- sive computer, such as the IBM 1401, which was quite good at reading cards, copying tapes, and printing output, but not at all good at numerical calculations. Other, much more expensive machines, such as the IBM 7094, were used for the real computing. This situation is shown in Fig. 1-3. Tape System drive Input tape Output Card tape tape reader Printer 1401 7094 1401 (a) (b) (c) (d) (e) (f) Figure 1-3. An early batch system. (a) Programmers bring cards to 1401. (b) 1401 reads batch of jobs onto tape. (c) Operator carries input tape to 7094. (d) 7094 does computing. (e) Operator carries output tape to 1401. (f) 1401 prints output. After about an hour of collecting a batch of jobs, the cards were read onto a magnetic tape, which was carried into the machine room, where it was mounted on a tape drive. The operator then loaded a special program (the ancestor of today’s operating system), which read the first job from tape and ran it. The output was written onto a second tape, instead of being printed. After each job finished, the operating system automatically read the next job from the tape and began running it. When the whole batch was done, the operator removed the input and output 10 INTRODUCTION CHAP. 1 tapes, replaced the input tape with the next batch, and brought the output tape to a 1401 for printing off line (i.e., not connected to the main computer). The structure of a typical input job is shown in Fig. 1-4. It started out with a $JOB card, specifying the maximum run time in minutes, the account number to be charged, and the programmer’s name. Then came a $FORTRAN card, telling the operating system to load the FORTRAN compiler from the system tape. It was directly followed by the program to be compiled, and then a $LOAD card, direct- ing the operating system to load the object program just compiled. (Compiled pro- grams were often written on scratch tapes and had to be loaded explicitly.) Next came the $RUN card, telling the operating system to run the program with the data following it. Finally, the $END card marked the end of the job. These control cards were the forerunners of modern shells and command-line interpreters. $END Data for program $RUN $LOAD FORTRAN program $FORTRAN $JOB, 10,7710802, ADA LOVELACE Figure 1-4. Structure of a typical FMS job. Large, second-generation computers were used mostly for scientific and engin- eering calculations, such as solving the partial differential equations that often occur in physics and engineering. They were largely programmed in FORTRAN and assembly language. Typical operating systems were FMS (the Fortran Moni- tor System) and IBSYS, IBM’s operating system for the 7094. 1.2.3 The Third Generation (1965–1980): ICs and Multiprogramming By the early 1960s, most computer manufacturers had two distinct and incom- patible, product lines. On the one hand, there were the word-oriented, large-scale scientific computers, such as the 7094, which were used for industrial-strength SEC. 1.2 HISTORY OF OPERATING SYSTEMS 11 numerical calculations in science and engineering. On the other hand, there were the character-oriented, commercial computers, such as the 1401, which were wide- ly used for tape sorting and printing by banks and insurance companies. Developing and maintaining two completely different product lines was an expensive proposition for the manufacturers. In addition, many new computer cus- tomers initially needed a small machine but later outgrew it and wanted a bigger machine that would run all their old programs, but faster. IBM attempted to solve both of these problems at a single stroke by introduc- ing the System/360. The 360 was a series of software-compatible machines rang- ing from 1401-sized models to much larger ones, more powerful than the mighty 7094. The machines differed only in price and performance (maximum memory, processor speed, number of I/O devices permitted, and so forth). Since they all had the same architecture and instruction set, programs written for one machine could run on all the others—at least in theory. (But as Yogi Berra reputedly said: ‘‘In theory, theory and practice are the same; in practice, they are not.’’) Since the 360 was designed to handle both scientific (i.e., numerical) and commercial computing, a single family of machines could satisfy the needs of all customers. In subsequent years, IBM came out with backward compatible successors to the 360 line, using more modern technology, known as the 370, 4300, 3080, and 3090. The zSeries is the most recent descendant of this line, although it has diverged considerably from the original. The IBM 360 was the first major computer line to use (small-scale) ICs (Inte- grated Circuits), thus providing a major price/performance advantage over the second-generation machines, which were built up from individual transistors. It was an immediate and massive success, and the idea of a family of compatible computers was soon adopted by all the other major manufacturers. The descen- dants of these machines are still in use at computer centers today. Nowadays they are often used for managing huge databases (e.g., for airline reservation systems) or as servers for World Wide Web sites that must process thousands of requests per second. The greatest strength of the ‘‘single-family’’ idea was simultaneously its great- est weakness. The original intention was that all software, including the operating system, OS/360, had to work on all models. It had to run on small systems, which often just replaced 1401s for copying cards to tape, and on very large systems, which often replaced 7094s for doing weather forecasting and other heavy comput- ing. It had to be good on systems with few peripherals and on systems with many peripherals. It had to work in commercial environments and in scientific environ- ments. Above all, it had to be efficient for all of these different uses. There was no way that IBM (or anybody else for that matter) could write a piece of software to meet all those conflicting requirements. The result was an enormous and extraordinarily complex operating system, probably two to three orders of magnitude larger than FMS. It consisted of millions of lines of assembly language written by thousands of programmers, and contained thousands upon 12 INTRODUCTION CHAP. 1 thousands of bugs, which necessitated a continuous stream of new releases in an attempt to correct them. Each new release fixed some bugs and introduced new ones, so the number of bugs probably remained constant over time. One of the designers of OS/360, Fred Brooks, subsequently wrote a now-clas- sic, witty, and incisive book (Brooks, 1995) describing his experiences with OS/360. While it would be impossible to summarize the book here, suffice it to say that the cover shows a herd of prehistoric beasts stuck in a tar pit. The cover of Silberschatz et al. (2012) makes a similar point about operating systems being dinosaurs. He also made the comment that adding programmers to a late software project makes it even later as well saying that it takes 9 months to produce a child, no matter how many women you assign to the project. Despite its enormous size and problems, OS/360 and the similar third-genera- tion operating systems produced by other computer manufacturers actually satis- fied most of their customers reasonably well. They also popularized several key techniques absent in second-generation operating systems. Probably the most important of these was multiprogramming. On the 7094, when the current job paused to wait for a tape or other I/O operation to complete, the CPU simply sat idle until the I/O finished. With heavily CPU-bound scientific calculations, I/O is infrequent, so this wasted time is not significant. With commercial data processing, the I/O wait time can often be 80% or 90% of the total time, so something had to be done to avoid having the (expensive) CPU be idle so much. The solution that evolved was to partition memory into several pieces, with a different job in each partition, as shown in Fig. 1-5. While one job was waiting for I/O to complete, another job could be using the CPU. If enough jobs could be held in main memory at once, the CPU could be kept busy nearly 100% of the time. Having multiple jobs safely in memory at once requires special hardware to protect each job against snooping and mischief by the other ones, but the 360 and other third-generation systems were equipped with this hardware. Job 3 Job 2 Memory Job 1 partitions Operating system Figure 1-5. A multiprogramming system with three jobs in memory. Another major feature present in third-generation operating systems was the ability to read jobs from cards onto the disk as soon as they were brought to the computer room. Then, whenever a running job finished, the operating system could load a new job from the disk into the now-empty partition and run it. This ability is SEC. 1.2 HISTORY OF OPERATING SYSTEMS 13 called spooling (from Simultaneous Peripheral Operation On Line) and was also used for output. With spooling, the 1401s were no longer needed, and much carrying of tapes disappeared. Although third-generation operating systems were well suited for big scientific calculations and massive commercial data-processing runs, they were still basically batch systems. Many programmers pined for the first-generation days when they had the machine all to themselves for a few hours, so they could debug their pro- grams quickly. With third-generation systems, the time between submitting a job and getting back the output was often several hours, so a single misplaced comma could cause a compilation to fail, and the programmer to waste half a day. Pro- grammers did not like that very much. This desire for quick response time paved the way for timesharing, a variant of multiprogramming, in which each user has an online terminal. In a timesharing system, if 20 users are logged in and 17 of them are thinking or talking or drinking coffee, the CPU can be allocated in turn to the three jobs that want service. Since people debugging programs usually issue short commands (e.g., compile a five- page procedure†) rather than long ones (e.g., sort a million-record file), the com- puter can provide fast, interactive service to a number of users and perhaps also work on big batch jobs in the background when the CPU is otherwise idle. The first general-purpose timesharing system, CTSS (Compatible Time Sharing Sys- tem), was developed at M.I.T. on a specially modified 7094 (Corbató et al., 1962). However, timesharing did not really become popular until the necessary protection hardware became widespread during the third generation. After the success of the CTSS system, M.I.T., Bell Labs, and General Electric (at that time a major computer manufacturer) decided to embark on the develop- ment of a ‘‘computer utility,’’ that is, a machine that would support some hundreds of simultaneous timesharing users. Their model was the electricity system—when you need electric power, you just stick a plug in the wall, and within reason, as much power as you need will be there. The designers of this system, known as MULTICS (MULTiplexed Information and Computing Service), envisioned one huge machine providing computing power for everyone in the Boston area. The idea that machines 10,000 times faster than their GE-645 mainframe would be sold (for well under $1000) by the millions only 40 years later was pure science fiction. Sort of like the idea of supersonic trans-Atlantic undersea trains now. MULTICS was a mixed success. It was designed to support hundreds of users on a machine 1000× slower than a modern smartphone and with a million times less memory. This is not quite as crazy as it sounds, since in those days people knew how to write small, efficient programs, a skill that has subsequently been completely lost. There were many reasons that MULTICS did not take over the world, not the least of which is that it was written in the PL/I programming lan- guage, and the PL/I compiler was years late and barely worked at all when it final- ly arrived. In addition, MULTICS was enormously ambitious for its time, much like Charles Babbage’s analytical engine in the nineteenth century. 14 INTRODUCTION CHAP. 1 To make a long story short, MULTICS introduced many seminal ideas into the computer literature, but turning it into a serious product and a major commercial success was a lot harder than anyone had expected. Bell Labs dropped out of the project, and General Electric quit the computer business altogether. However, M.I.T. persisted and eventually got MULTICS working. It was ultimately sold as a commercial product by the company (Honeywell) that bought GE’s computer busi- ness when GE got tired of it and was installed by about 80 major companies and universities worldwide. While their numbers were small, MULTICS users were fiercely loyal. General Motors, Ford, and the U.S. National Security Agency, for example, shut down their MULTICS systems only in the late 1990s, 30 years after MULTICS was released, after years of begging Honeywell to update the hardware. The last MULTICS system was shut down amid a lot of tears in October 2000. Can you imagine hanging onto your PC for 30 years because you think it is so much better than everything else out there? That’s the kind of loyalty MULTICS inspired—and for good reason. It was hugely important. By the end of the 20th century, the concept of a computer utility had fizzled out, but it came back in the form of cloud computing, in which relatively small computers (including smartphones, tablets, and the like) are connected to servers in vast and distant data centers where all the computing is done, with the local com- puter mostly handling the user interface. The motivation here is that most people do not want to administrate an increasingly complex and evolving computer sys- tem and would prefer to have that work done by a team of professionals, for exam- ple, people working for the company running the data center. Despite its lack of commercial success, MULTICS had a huge influence on subsequent operating systems (especially UNIX and its derivatives, Linux, macOS, iOS, and FreeBSD). It is described in several papers and a book (Corbató and Vyssotsky, 1965; Daley and Dennis, 1968; Organick, 1972; Corbató et al., 1972; and Saltzer, 1974). It also has an active Website, located at www.multicians.org, with much information about the system, its designers, and its users. Another major development during the third generation was the phenomenal growth of minicomputers, starting with the DEC PDP-1 in 1961. The PDP-1 had only 4K of 18-bit words, but at $120,000 per machine (less than 5% of the price of a 7094), it sold like hotcakes. For certain kinds of nonnumerical work, it was almost as fast as the 7094 and gave birth to a whole new industry. It was quickly followed by a series of other PDPs (unlike IBM’s family, all incompatible) culmi- nating in the PDP-11. One of the computer scientists at Bell Labs who had worked on the MULTICS project, Ken Thompson, subsequently found a small PDP-7 minicomputer that no one was using and set out to write a stripped-down, one-user version of MULTICS. This work later developed into the UNIX operating system, which became popular in the academic world, with government agencies, and with many companies. The history of UNIX has been told elsewhere (e.g., Salus, 1994). Part of that story will be given in Chap. 10. For now, suffice it to say that because the source SEC. 1.2 HISTORY OF OPERATING SYSTEMS 15 code was widely available, various organizations developed their own (incompati- ble) versions, which led to chaos. Two major versions developed, System V, from AT&T, and BSD (Berkeley Software Distribution) from the University of Cali- fornia at Berkeley. These had minor variants as well. To make it possible to write programs that could run on any UNIX system, IEEE developed a standard for UNIX, called POSIX, that most versions of UNIX now support. POSIX defines a minimal system-call interface that conformant UNIX systems must support. In fact, some other operating systems now also support the POSIX interface. As an aside, it is worth mentioning that in 1987, one of the authors (Tanen- baum) released a small clone of UNIX, called MINIX, primarily for educational purposes. Functionally, MINIX is very similar to UNIX, including POSIX support. Since that time, the original version of MINIX has evolved into MINIX 3, which is highly modular and focused on very high reliability and available for free from the Website www.minix3.org. MINIX 3 has the ability to detect and replace faulty or even crashed modules (such as I/O device drivers) on the fly without a reboot and without disturbing running programs. A book describing its internal operation and listing the source code in an appendix is also available (Tanenbaum and Woodhull, 2006). The desire for a free production (as opposed to educational) version of MINIX led a Finnish student, Linus Torvalds, to write Linux. This system was directly inspired by and developed on MINIX and originally supported various MINIX fea- tures (e.g., the MINIX file system). It has since been extended in many ways by many people but still retains some underlying structure common to MINIX and to UNIX. Readers interested in a detailed history of Linux and the open source movement might want to read Glyn Moody’s (2001) book. Most of what will be said about UNIX in this book thus applies to System V, MINIX, Linux, and other versions and clones of UNIX as well. Interestingly, both Linux and MINIX have become widely used. Linux powers a huge share of the servers in data centers and forms the basis of Android which dominates the smartphone market. MINIX was adapted by Intel for a separate and somewhat secret ‘‘management’’ processor embedded in virtually all its chipsets since 2008. In other words, if you have an Intel CPU, you also run MINIX deep in your processor, even if your main operating system is, say, Windows or Linux. 1.2.4 The Fourth Generation (1980–Present): Personal Computers With the development of LSI (Large Scale Integration) circuits—chips con- taining thousands of transistors on a square centimeter of silicon—the age of the personal computer dawned. In terms of architecture, personal computers (initially called microcomputers) were not all that different from minicomputers of the PDP-11 class, but in terms of price they certainly were different. Where the mini- computer made it possible for a department in a company or university to have its 16 INTRODUCTION CHAP. 1 own computer, the microprocessor chip made it possible for a single individual to have his or her own personal computer. In 1974, when Intel came out with the 8080, the first general-purpose 8-bit CPU, it wanted an operating system for it, in part to be able to test it. Intel asked one of its consultants, Gary Kildall, to write one. Kildall and a friend first built a controller for the newly released Shugart Associates 8-inch floppy disk and hooked the floppy disk up to the 8080, thus producing the first microcomputer with a disk. Kildall then wrote a disk-based operating system called CP/M (Control Program for Microcomputers) for it. Since Intel did not think that disk-based microcom- puters had much of a future, when Kildall asked for the rights to CP/M, Intel grant- ed his request. Kildall then formed a company, Digital Research, to further develop and sell CP/M. In 1977, Digital Research rewrote CP/M to make it suitable for running on the many microcomputers using the 8080, Zilog Z80, and other CPU chips. Many application programs were written to run on CP/M, allowing it to completely dom- inate the world of microcomputing for about 5 years. In the early 1980s, IBM designed the IBM PC and looked around for software to run on it. People from IBM contacted Bill Gates to license his BASIC inter- preter. They also asked him if he knew of an operating system to run on the PC. Gates suggested that IBM contact Digital Research, then the world’s dominant operating systems company. Making what was without a doubt the worst business decision in recorded history, Kildall refused to meet with IBM, sending a subordi- nate instead. To make matters even worse, his lawyer even refused to sign IBM’s nondisclosure agreement covering the not-yet-announced PC. Consequently, IBM went back to Gates asking if he could provide them with an operating system. When IBM came back to him, Gates quickly realized that a local computer manufacturer, Seattle Computer Products, had a suitable operating system, DOS (Disk Operating System). He approached them and asked to buy it (allegedly for $75,000), which they readily accepted. Gates then offered IBM a DOS/BASIC package, which IBM accepted. IBM wanted certain modifications, so Gates hired the person who wrote DOS, Tim Paterson, as an employee of Gates’ fledgling company, Microsoft, to make them. The revised system was renamed MS-DOS (MicroSoft Disk Operating System) and quickly came to dominate the IBM PC market. A key factor here was Gates’ (in retrospect, extremely wise) decision to sell MS-DOS to computer companies for bundling with their hardware, compared to Kildall’s attempt to sell CP/M to end users one at a time (at least initially). After all this transpired, Kildall died suddenly and unexpectedly from causes that have not been fully disclosed. By the time the successor to the IBM PC, the IBM PC/AT, came out in 1983 with the Intel 80286 CPU, MS-DOS was firmly entrenched and CP/M was on its last legs. MS-DOS was later widely used on the 80386 and 80486. Although the initial version of MS-DOS was fairly primitive, subsequent versions included more advanced features, including many taken from UNIX. (Microsoft was well aware SEC. 1.2 HISTORY OF OPERATING SYSTEMS 17 of UNIX, even selling a microcomputer version of it called XENIX during the company’s early years.) CP/M, MS-DOS, and other operating systems for early microcomputers were all based on users typing in commands from the keyboard. That eventually chang- ed due to research done by Doug Engelbart at Stanford Research Institute in the 1960s. Engelbart invented the Graphical User Interface, complete with windows, icons, menus, and mouse. These ideas were adopted by researchers at Xerox PARC and incorporated into machines they built. One fine day, Steve Jobs, who co-invented the Apple computer in his garage, visited PARC, saw a GUI, and instantly realized its potential value, something Xerox management famously did not. This strategic blunder of incredibly gargan- tuan proportions led to a book entitled Fumbling the Future (Smith and Alexander, 1988). Jobs then embarked on building an Apple with a GUI. This project led to the Lisa, which was too expensive and failed commercially. Jobs’ second attempt, the Apple Macintosh, was an huge success, not only because it was much cheaper than the Lisa, but also because it was user friendly, meaning that it was intended for users who not only knew nothing about computers but furthermore had abso- lutely no intention whatsoever of learning. In the creative world of graphic design, professional digital photography, and professional digital video production, Macin- toshes became widely used and their users loved them. In 1999, Apple adopted a kernel derived from Carnegie Mellon University’s Mach microkernel which was originally developed to replace the kernel of BSD UNIX. Thus, Apple’s macOS is a UNIX-based operating system, albeit with a distinctive interface. When Microsoft decided to build a successor to MS-DOS, it was strongly influenced by the success of the Macintosh. It produced a GUI-based system call- ed Windows, which originally ran on top of MS-DOS (i.e., it was more like a shell than a true operating system). For about 10 years, from 1985 to 1995, Windows was just a graphical environment on top of MS-DOS. However, starting in 1995 a freestanding version, Windows 95, was released that incorporated many operating system features into it, using the underlying MS-DOS system only for booting and running old MS-DOS programs. Microsoft rewrote much of the operating system from scratch for Windows NT, a full 32-bit system. The lead designer for Win- dows NT was David Cutler, who was also one of the designers of the VAX VMS operating system, so some ideas from VMS are present in NT. In fact, so many ideas from VMS were present in it that the owner of VMS, DEC, sued Microsoft. The case was settled out of court for an amount of money requiring many digits to express. Version 5 of Windows NT was renamed Windows 2000 in early 1999, and two years later Microsoft released a slightly upgraded version called Windows XP which had a longer run than other versions (6 years). After Windows 2000, Microsoft broke up the Windows family into a client and a server line. The client line was based on XP and its successors, while the server line produced Windows Server 2003–2019 and now Windows Server vNext. Microsoft later also introduced a third line, for the embedded world. All of these 18 INTRODUCTION CHAP. 1 families of Windows forked off their own variations in the form of service packs in a dizzying proliferation of versions. It was enough to drive some administrators (and writers of operating systems textbooks) balmy. When in January 2007 Microsoft finally released the successor to Windows XP, which it called Vista, it came with a new graphical interface, improved securi- ty, and many new or upgraded user programs. It bombed. Users complained about high system requirements and restrictive licensing terms. Its successor, Windows 7, a much less resource hungry version of the operating system, quickly overtook it. In 2012, Windows 8 came out. It had a completely new look and feel, geared largely for touch screens. The company hoped that the new design would become the dominant operating system on a wide variety of devices: desktops, notebooks, tablets, phones, and home theater PCs. It did not. While Windows 8 (and especial- ly Windows 8.1) were successful, their popularity was mostly limited to PCs. In fact, many people did not like the new design much and Microsoft reverted it in 2015 in Windows 10. A few years later, Windows 10 overtook Windows 7 as the most popular Windows version. Windows 11 was released in 2021. The other major contender in the personal computer world comprises the UNIX family. UNIX, and especially Linux, is strongest on network and enterprise servers but also popular on desktop computers, notebooks, tablets, embedded sys- tems, and smartphones. FreeBSD is also a popular UNIX derivative, originating from the BSD project at Berkeley. Every modern Mac runs a modified version of FreeBSD (macOS). UNIX derivatives are widely used on mobile devices, such as those running iOS 7 or Android. Many UNIX users, especially experienced programmers, prefer a com- mand-based interface to a GUI, so nearly all UNIX systems support a windowing system called the X Window System (also known as X11) produced at M.I.T. This system handles the basic window management, allowing users to create, delete, move, and resize windows using a mouse. Often a complete GUI-based desktop environment, such as Gnome or KDE, is available to run on top of X11, giving UNIX a look and feel something like the Macintosh or Microsoft Windows, for those UNIX users who want such a thing. An interesting development that began during the mid-1980s was the develop- ment of network operating systems and distributed operating systems to man- age a collection of computers (Van Steen and Tanenbaum, 2017). In a network operating system, the users are aware of the existence of multiple computers and can log in to remote machines and copy files from one machine to another. Each machine runs its own local operating system and has its own local user (or users). Such systems are not fundamentally different from single-processor operating sys- tems. They obviously need a network interface and some low-level software to drive it, as well as programs to achieve remote login and remote file access, but these additions do not change the essential structure of the operating system. A distributed operating system, in contrast, is one that appears to its users as a traditional uniprocessor system, even though it is actually composed of multiple SEC. 1.2 HISTORY OF OPERATING SYSTEMS 19 processors. The users should not be aware of where their programs are being run or where their files are located; that should all be handled automatically and ef- ficiently by the operating system. True distributed operating systems require more than just adding a little code to a uniprocessor operating system, because distributed and centralized systems differ in certain critical ways. Distributed systems, for example, often allow appli- cations to run on several processors at the same time, thus requiring more complex processor scheduling algorithms in order to optimize the amount of parallelism. Moreover, communication delays within the network often mean that these (and other) algorithms must run with incomplete, outdated, or even incorrect infor- mation. This situation differs radically from that in a single-processor system in which the operating system has complete information about the system state. 1.2.5 The Fifth Generation (1990–Present): Mobile Computers Ever since detective Dick Tracy started talking to his ‘‘two-way radio wrist watch’’ in the 1940s comic strip, people have craved a communication device they could carry around wherever they went. The first real mobile phone appeared in 1946 and weighed some 40 kilos. You could take it wherever you went as long as you had a car in which to carry it. The first true handheld phone appeared in the 1970s and, at roughly one kilo- gram, was positively featherweight. It was affectionately known as ‘‘the brick.’’ Pretty soon everybody wanted one. Today, mobile phone penetration in developed countries is close to 90% of the global population. We can make calls not just with our portable phones and wrist watches, but even with eyeglasses and other wear- able items. Moreover, the phone part is no longer central. We receive email, surf the Web, text our friends, play games, navigate around heavy traffic—and do not even think twice about it. While the idea of combining telephony and computing in a phone-like device has been around since the 1970s also, the first real smartphone did not appear until the mid-1990s when Nokia released the N9000, which literally combined two, mostly separate devices: a phone and a Personal Digital Assistant. In 1997, Erics- son coined the term smartphone for its GS88 ‘‘Penelope.’’ Now that smartphones have become ubiquitous, the competition between the operating systems is as fierce as in the PC world. At the time of writing, Google’s Android is the dominant operating system with Apple’s iOS a clear second, but this was not always the case and all may be different again in just a few years. If any- thing is clear in the world of smartphones, it is that it is not easy to stay king of the mountain for long. After all, most smartphones in the first decade after their inception were run- ning Symbian OS. It was the operating system of choice for popular brands like Samsung, Sony Ericsson, Motorola, and especially Nokia. However, other operat- ing systems like RIM’s Blackberry OS (introduced for smartphones in 2002) and 20 INTRODUCTION CHAP. 1 Apple’s iOS (released for the first iPhone in 2007) started eating into Symbian’s market share. Many expected that RIM would dominate the business market, while iOS would dominate on consumer devices. Symbian’s market share plummeted. In 2011, Nokia ditched Symbian and announced it would focus on Windows Phone as its primary platform. For some time, Apple and RIM were the toast of the town (although not nearly as dominant as Symbian had been), but it did not take very long for Android, a Linux-based operating system released by Google in 2008, to overtake all its rivals. For phone manufacturers, Android had the advantage that it was open source and available under a permissive license. As a result, they could tinker with it and adapt it to their own hardware with ease. Also, it has a huge community of devel- opers writing apps, mostly in the familiar Java programming language. Even so, the past years have shown that the dominance may not last, and Android’s competi- tors are eager to claw back some of its market share. We will look at Android in detail in Sec. 10.8. 1.3 COMPUTER HARDWARE REVIEW An operating system is intimately tied to the hardware of the computer it runs on. It extends the computer’s instruction set and manages its resources. To work, it must know a great deal about the hardware, at least about how the hardware appears to the programmer. For this reason, let us briefly review computer hard- ware as found in modern personal computers. After that, we can start getting into the details of what operating systems do and how they work. Conceptually, a simple personal computer can be abstracted to a model resem- bling that of Fig. 1-6. The CPU, memory, and I/O devices are all connected by a system bus and communicate with one another over it. Modern personal computers have a more complicated structure, involving multiple buses, which we will look at later. F