Modern operating systems

Cover......Page 1
Title......Page 5
Content......Page 9
PREFACE......Page 25
1 INTRODUCTION......Page 33
 1.1 WHAT IS AN OPERATING SYSTEM?......Page 35
  1.1.1 The Operating System as an Extended Machine......Page 36
  1.1.2 The Operating System as a Resource Manager......Page 37
 1.2 HISTORY OF OPERATING SYSTEMS......Page 38
  1.2.1 The First Generation (1945–55): Vacuum Tubes......Page 39
  1.2.2 The Second Generation (1955–65): Transistors and Batch Systems......Page 40
  1.2.3 The Third Generation (1965–1980): ICs and Multiprogramming......Page 41
  1.2.4 The Fourth Generation (1980–Present): Personal Computers......Page 47
  1.2.5 The Fifth Generation (1990–Present): Mobile Computers......Page 51
 1.3 COMPUTER HARDWARE REVIEW......Page 52
  1.3.1 Processors......Page 53
  1.3.2 Memory......Page 56
  1.3.3 Disks......Page 59
  1.3.4 I/O Devices......Page 60
  1.3.5 Buses......Page 64
  1.3.6 Booting the Computer......Page 66
  1.4.2 Server Operating Systems......Page 67
  1.4.5 Handheld Computer Operating Systems......Page 68
  1.4.8 Real-Time Operating Systems......Page 69
 1.5 OPERATING SYSTEM CONCEPTS......Page 70
  1.5.1 Processes......Page 71
  1.5.3 Files......Page 73
  1.5.6 The Shell......Page 77
  1.5.7 Ontogeny Recapitulates Phylogeny......Page 79
 1.6 SYSTEM CALLS......Page 82
  1.6.1 System Calls for Process Management......Page 85
  1.6.2 System Calls for File Management......Page 88
  1.6.3 System Calls for Directory Management......Page 89
  1.6.4 Miscellaneous System Calls......Page 91
  1.6.5 The Windows Win32 API......Page 92
 1.7 OPERATING SYSTEM STRUCTURE......Page 94
  1.7.1 Monolithic Systems......Page 95
  1.7.2 Layered Systems......Page 96
  1.7.3 Microkernels......Page 97
  1.7.4 Client-Server Model......Page 100
  1.7.5 Virtual Machines......Page 101
  1.8.1 The C Language......Page 105
  1.8.2 Header Files......Page 106
  1.8.3 Large Programming Projects......Page 107
  1.8.4 The Model of Run Time......Page 108
 1.9 RESEARCH ON OPERATING SYSTEMS......Page 109
 1.10 OUTLINE OF THE REST OF THIS BOOK......Page 110
 1.11 METRIC UNITS......Page 111
 1.12 SUMMARY......Page 112
 2.1 PROCESSES......Page 117
  2.1.1 The Process Model......Page 118
  2.1.2 Process Creation......Page 120
  2.1.3 Process Termination......Page 122
  2.1.4 Process Hierarchies......Page 123
  2.1.5 Process States......Page 124
  2.1.6 Implementation of Processes......Page 126
  2.1.7 Modeling Multiprogramming......Page 127
  2.2.1 Thread Usage......Page 129
  2.2.2 The Classical Thread Model......Page 134
  2.2.3 POSIX Threads......Page 138
  2.2.4 Implementing Threads in User Space......Page 140
  2.2.5 Implementing Threads in the Kernel......Page 143
  2.2.6 Hybrid Implementations......Page 144
  2.2.7 Scheduler Activations......Page 145
  2.2.8 Pop-Up Threads......Page 146
  2.2.9 Making Single-Threaded Code Multithreaded......Page 148
  2.3.1 Race Conditions......Page 151
  2.3.2 Critical Regions......Page 153
  2.3.3 Mutual Exclusion with Busy Waiting......Page 154
  2.3.4 Sleep and Wakeup......Page 159
  2.3.5 Semaphores......Page 162
  2.3.6 Mutexes......Page 164
  2.3.7 Monitors......Page 169
  2.3.8 Message Passing......Page 176
  2.3.9 Barriers......Page 178
  2.3.10 Avoiding Locks: Read-Copy-Update......Page 180
 2.4 SCHEDULING......Page 181
  2.4.1 Introduction to Scheduling......Page 182
  2.4.2 Scheduling in Batch Systems......Page 188
  2.4.3 Scheduling in Interactive Systems......Page 190
  2.4.4 Scheduling in Real-Time Systems......Page 196
  2.4.5 Policy Versus Mechanism......Page 197
  2.4.6 Thread Scheduling......Page 198
  2.5.1 The Dining Philosophers Problem......Page 199
  2.5.2 The Readers and Writers Problem......Page 203
 2.6 RESEARCH ON PROCESSES AND THREADS......Page 204
 2.7 SUMMARY......Page 205
3 MEMORY MANAGEMENT......Page 213
 3.1 NO MEMORY ABSTRACTION......Page 214
 3.2 A MEMORY ABSTRACTION: ADDRESS SPACES......Page 217
  3.2.1 The Notion of an Address Space......Page 218
  3.2.2 Swapping......Page 219
  3.2.3 Managing Free Memory......Page 222
 3.3 VIRTUAL MEMORY......Page 226
  3.3.1 Paging......Page 227
  3.3.2 Page Tables......Page 230
  3.3.3 Speeding Up Paging......Page 233
  3.3.4 Page Tables for Large Memories......Page 237
  3.4.1 The Optimal Page Replacement Algorithm......Page 241
  3.4.2 The Not Recently Used Page Replacement Algorithm......Page 242
  3.4.3 The First-In, First-Out (FIFO) Page Replacement Algorithm......Page 243
  3.4.5 The Clock Page Replacement Algorithm......Page 244
  3.4.6 The Least Recently Used (LRU) Page Replacement Algorithm......Page 245
  3.4.7 Simulating LRU in Software......Page 246
  3.4.8 The Working Set Page Replacement Algorithm......Page 247
  3.4.9 The WSClock Page Replacement Algorithm......Page 251
  3.4.10 Summary of Page Replacement Algorithms......Page 253
  3.5.1 Local versus Global Allocation Policies......Page 254
  3.5.3 Page Size......Page 257
  3.5.4 Separate Instruction and Data Spaces......Page 259
  3.5.5 Shared Pages......Page 260
  3.5.6 Shared Libraries......Page 261
  3.5.7 Mapped Files......Page 263
  3.5.9 Virtual Memory Interface......Page 264
  3.6.1 Operating System Involvement with Paging......Page 265
  3.6.2 Page Fault Handling......Page 266
  3.6.3 Instruction Backup......Page 267
  3.6.5 Backing Store......Page 269
  3.6.6 Separation of Policy and Mechanism......Page 271
 3.7 SEGMENTATION......Page 272
  3.7.2 Segmentation with Paging: MULTICS......Page 275
  3.7.3 Segmentation with Paging: The Intel x86......Page 279
 3.8 RESEARCH ON MEMORY MANAGEMENT......Page 284
 3.9 SUMMARY......Page 285
4 FILE SYSTEMS......Page 295
  4.1.1 File Naming......Page 297
  4.1.2 File Structure......Page 299
  4.1.3 File Types......Page 300
  4.1.4 File Access......Page 302
  4.1.5 File Attributes......Page 303
  4.1.6 File Operations......Page 304
  4.1.7 An Example Program Using File-System Calls......Page 305
  4.2.2 Hierarchical Directory Systems......Page 308
  4.2.3 Path Names......Page 309
  4.2.4 Directory Operations......Page 312
  4.3.1 File-System Layout......Page 313
  4.3.2 Implementing Files......Page 314
  4.3.3 Implementing Directories......Page 320
  4.3.4 Shared Files......Page 322
  4.3.5 Log-Structured File Systems......Page 325
  4.3.6 Journaling File Systems......Page 327
  4.3.7 Virtual File Systems......Page 328
 4.4 FILE-SYSTEM MANAGEMENT AND OPTIMIZATION......Page 331
  4.4.1 Disk-Space Management......Page 332
  4.4.2 File-System Backups......Page 338
  4.4.3 File-System Consistency......Page 344
  4.4.4 File-System Performance......Page 346
  4.4.5 Defragmenting Disks......Page 351
  4.5.1 The MS-DOS File System......Page 352
  4.5.2 The UNIX V7 File System......Page 355
  4.5.3 CD-ROM File Systems......Page 357
 4.6 RESEARCH ON FILE SYSTEMS......Page 363
 4.7 SUMMARY......Page 364
 5.1 PRINCIPLES OF I/O HARDWARE......Page 369
  5.1.1 I/O Devices......Page 370
  5.1.2 Device Controllers......Page 371
  5.1.3 Memory-Mapped I/O......Page 372
  5.1.4 Direct Memory Access......Page 376
  5.1.5 Interrupts Revisited......Page 379
  5.2.1 Goals of the I/O Software......Page 383
  5.2.2 Programmed I/O......Page 384
  5.2.3 Interrupt-Driven I/O......Page 386
  5.2.4 I/O Using DMA......Page 387
  5.3.1 Interrupt Handlers......Page 388
  5.3.2 Device Drivers......Page 389
  5.3.3 Device-Independent I/O Software......Page 393
  5.3.4 User-Space I/O Software......Page 399
  5.4.1 Disk Hardware......Page 401
  5.4.2 Disk Formatting......Page 407
  5.4.3 Disk Arm Scheduling Algorithms......Page 411
  5.4.4 Error Handling......Page 414
  5.4.5 Stable Storage......Page 417
  5.5.1 Clock Hardware......Page 420
  5.5.2 Clock Software......Page 422
  5.5.3 Soft Timers......Page 424
  5.6.1 Input Software......Page 426
  5.6.2 Output Software......Page 431
 5.7 THIN CLIENTS......Page 448
 5.8 POWER MANAGEMENT......Page 449
  5.8.1 Hardware Issues......Page 450
  5.8.2 Operating System Issues......Page 451
  5.8.3 Application Program Issues......Page 457
 5.9 RESEARCH ON INPUT/OUTPUT......Page 458
 5.10 SUMMARY......Page 460
6 DEADLOCKS......Page 467
  6.1.1 Preemptable and Nonpreemptable Resources......Page 468
  6.1.2 Resource Acquisition......Page 469
 6.2 INTRODUCTION TO DEADLOCKS......Page 471
  6.2.2 Deadlock Modeling......Page 472
 6.4 DEADLOCK DETECTION AND RECOVERY......Page 475
  6.4.1 Deadlock Detection with One Resource of Each Type......Page 476
  6.4.2 Deadlock Detection with Multiple Resources of Each Type......Page 478
  6.4.3 Recovery from Deadlock......Page 481
  6.5.1 Resource Trajectories......Page 482
  6.5.2 Safe and Unsafe States......Page 484
  6.5.3 The Banker’s Algorithm for a Single Resource......Page 485
  6.5.4 The Banker’s Algorithm for Multiple Resources......Page 486
  6.6.2 Attacking the Hold-and-Wait Condition......Page 488
  6.6.4 Attacking the Circular Wait Condition......Page 489
 6.7 OTHER ISSUES......Page 490
  6.7.2 Communication Deadlocks......Page 491
  6.7.3 Livelock......Page 493
  6.7.4 Starvation......Page 495
 6.9 SUMMARY......Page 496
7 VIRTUALIZATION AND THE CLOUD......Page 503
 7.1 HISTORY......Page 505
 7.2 REQUIREMENTS FOR VIRTUALIZATION......Page 506
 7.3 TYPE 1 AND TYPE 2 HYPERVISORS......Page 509
 7.4 TECHNIQUES FOR EFFICIENT VIRTUALIZATION......Page 510
  7.4.1 Virtualizing the Unvirtualizable......Page 511
  7.4.2 The Cost of Virtualization......Page 514
 7.5 ARE HYPERVISORS MICROKERNELS DONE RIGHT?......Page 515
 7.6 MEMORY VIRTUALIZATION......Page 518
 7.7 I/O VIRTUALIZATION......Page 522
 7.8 VIRTUAL APPLIANCES......Page 525
 7.10 LICENSING ISSUES......Page 526
 7.11 CLOUDS......Page 527
  7.11.2 Virtual Machine Migration......Page 528
  7.11.3 Checkpointing......Page 529
  7.12.1 The Early History of VMware......Page 530
  7.12.2 VMware Workstation......Page 531
  7.12.3 Challenges in Bringing Virtualization to the x86......Page 532
  7.12.4 VMware Workstation: Solution Overview......Page 534
  7.12.5 The Evolution of VMware Workstation......Page 543
  7.12.6 ESX Server: VMware’s type 1 Hypervisor......Page 544
 7.13 RESEARCH ON VIRTUALIZATION AND THE CLOUD......Page 546
8 MULTIPLE PROCESSOR SYSTEMS......Page 549
  8.1.1 Multiprocessor Hardware......Page 552
  8.1.2 Multiprocessor Operating System Types......Page 563
  8.1.3 Multiprocessor Synchronization......Page 566
  8.1.4 Multiprocessor Scheduling......Page 571
 8.2 MULTICOMPUTERS......Page 577
  8.2.1 Multicomputer Hardware......Page 578
  8.2.2 Low-Level Communication Software......Page 582
  8.2.3 User-Level Communication Software......Page 585
  8.2.4 Remote Procedure Call......Page 588
  8.2.5 Distributed Shared Memory......Page 590
  8.2.6 Multicomputer Scheduling......Page 595
 8.3 DISTRIBUTED SYSTEMS......Page 598
  8.3.1 Network Hardware......Page 600
  8.3.2 Network Services and Protocols......Page 604
  8.3.3 Document-Based Middleware......Page 608
  8.3.4 File-System-Based Middleware......Page 609
  8.3.5 Object-Based Middleware......Page 614
  8.3.6 Coordination-Based Middleware......Page 616
 8.4 RESEARCH ON MULTIPLE PROCESSOR SYSTEMS......Page 619
 8.5 SUMMARY......Page 620
9 SECURITY......Page 625
 9.1 THE SECURITY ENVIRONMENT......Page 627
  9.1.1 Threats......Page 628
 9.2 OPERATING SYSTEMS SECURITY......Page 631
  9.2.1 Can We Build Secure Systems?......Page 632
  9.2.2 Trusted Computing Base......Page 633
 9.3 CONTROLLING ACCESS TO RESOURCES......Page 634
  9.3.1 Protection Domains......Page 635
  9.3.2 Access Control Lists......Page 637
  9.3.3 Capabilities......Page 640
 9.4 FORMAL MODELS OF SECURE SYSTEMS......Page 643
  9.4.1 Multilevel Security......Page 644
  9.4.2 Covert Channels......Page 647
 9.5 BASICS OF CRYPTOGRAPHY......Page 651
  9.5.1 Secret-Key Cryptography......Page 652
  9.5.2 Public-Key Cryptography......Page 653
  9.5.3 One-Way Functions......Page 654
  9.5.4 Digital Signatures......Page 655
  9.5.5 Trusted Platform Modules......Page 656
 9.6 AUTHENTICATION......Page 658
  9.6.1 Authentication Using a Physical Object......Page 665
  9.6.2 Authentication Using Biometrics......Page 668
 9.7 EXPLOITING SOFTWARE......Page 671
  9.7.1 Buffer Overflow Attacks......Page 672
  9.7.2 Format String Attacks......Page 681
  9.7.3 Dangling Pointers......Page 684
  9.7.4 Null Pointer Dereference Attacks......Page 685
  9.7.5 Integer Overflow Attacks......Page 686
  9.7.6 Command Injection Attacks......Page 687
  9.7.7 Time of Check to Time of Use Attacks......Page 688
  9.8.1 Logic Bombs......Page 689
  9.8.2 Back Doors......Page 690
  9.8.3 Login Spoofing......Page 691
 9.9 MALWARE......Page 692
  9.9.1 Trojan Horses......Page 695
  9.9.2 Viruses......Page 696
  9.9.3 Worms......Page 706
  9.9.4 Spyware......Page 708
  9.9.5 Rootkits......Page 712
 9.10 DEFENSES......Page 716
  9.10.1 Firewalls......Page 717
  9.10.2 Antivirus and Anti-Antivirus Techniques......Page 719
  9.10.3 Code Signing......Page 725
  9.10.4 Jailing......Page 726
  9.10.5 Model-Based Intrusion Detection......Page 727
  9.10.6 Encapsulating Mobile Code......Page 729
  9.10.7 Java Security......Page 733
 9.11 RESEARCH ON SECURITY......Page 735
 9.12 SUMMARY......Page 736
10 CASE STUDY 1: UNIX, LINUX, AND ANDROID......Page 745
  10.1.1 UNICS......Page 746
  10.1.2 PDP-11 UNIX......Page 747
  10.1.3 Portable UNIX......Page 748
  10.1.4 Berkeley UNIX......Page 749
  10.1.5 Standard UNIX......Page 750
  10.1.6 MINIX......Page 751
  10.1.7 Linux......Page 752
  10.2.1 Linux Goals......Page 755
  10.2.2 Interfaces to Linux......Page 756
  10.2.3 The Shell......Page 758
  10.2.4 Linux Utility Programs......Page 761
  10.2.5 Kernel Structure......Page 763
  10.3.1 Fundamental Concepts......Page 765
  10.3.2 Process-Management System Calls in Linux......Page 768
  10.3.3 Implementation of Processes and Threads in Linux......Page 772
  10.3.4 Scheduling in Linux......Page 778
  10.3.5 Booting Linux......Page 783
 10.4 MEMORY MANAGEMENT IN LINUX......Page 785
  10.4.1 Fundamental Concepts......Page 786
  10.4.2 Memory Management System Calls in Linux......Page 788
  10.4.3 Implementation of Memory Management in Linux......Page 790
  10.4.4 Paging in Linux......Page 796
  10.5.1 Fundamental Concepts......Page 799
  10.5.2 Networking......Page 801
  10.5.3 Input/Output System Calls in Linux......Page 802
  10.5.4 Implementation of Input/Output in Linux......Page 803
  10.5.5 Modules in Linux......Page 806
  10.6.1 Fundamental Concepts......Page 807
  10.6.2 File-System Calls in Linux......Page 812
  10.6.3 Implementation of the Linux File System......Page 816
  10.6.4 NFS: The Network File System......Page 824
  10.7.1 Fundamental Concepts......Page 830
  10.7.3 Implementation of Security in Linux......Page 833
 10.8 ANDROID......Page 834
  10.8.1 Android and Google......Page 835
  10.8.2 History of Android......Page 836
  10.8.3 Design Goals......Page 839
  10.8.4 Android Architecture......Page 841
  10.8.5 Linux Extensions......Page 842
  10.8.6 Dalvik......Page 846
  10.8.7 Binder IPC......Page 847
  10.8.8 Android Applications......Page 856
  10.8.9 Intents......Page 868
  10.8.11 Security......Page 870
  10.8.12 Process Model......Page 876
 10.9 SUMMARY......Page 881
 11.1 HISTORY OF WINDOWS THROUGH WINDOWS 8.1......Page 889
  11.1.1 1980s: MS-DOS......Page 890
  11.1.3 2000s: NT-based Windows......Page 891
  11.1.4 Windows Vista......Page 894
  11.1.5 2010s: Modern Windows......Page 895
 11.2 PROGRAMMING WINDOWS......Page 896
  11.2.1 The Native NT Application Programming Interface......Page 900
  11.2.2 The Win32 Application Programming Interface......Page 903
  11.2.3 The Windows Registry......Page 907
  11.3.1 Operating System Structure......Page 909
  11.3.2 Booting Windows......Page 925
  11.3.3 Implementation of the Object Manager......Page 926
  11.3.4 Subsystems, DLLs, and User-Mode Services......Page 937
  11.4.1 Fundamental Concepts......Page 940
  11.4.2 Job, Process, Thread, and Fiber Management API Calls......Page 946
  11.4.3 Implementation of Processes and Threads......Page 951
 11.5 MEMORY MANAGEMENT......Page 959
  11.5.1 Fundamental Concepts......Page 960
  11.5.2 Memory-Management System Calls......Page 963
  11.5.3 Implementation of Memory Management......Page 965
 11.6 CACHING IN WINDOWS......Page 974
 11.7 INPUT/OUTPUT IN WINDOWS......Page 975
  11.7.1 Fundamental Concepts......Page 976
  11.7.2 Input/Output API Calls......Page 977
  11.7.3 Implementation of I/O......Page 980
 11.8 THE WINDOWS NT FILE SYSTEM......Page 984
  11.8.1 Fundamental Concepts......Page 985
  11.8.2 Implementation of the NT File System......Page 986
 11.9 WINDOWS POWER MANAGEMENT......Page 996
 11.10 SECURITY IN WINDOWS 8......Page 998
  11.10.1 Fundamental Concepts......Page 999
  11.10.2 Security API Calls......Page 1001
  11.10.3 Implementation of Security......Page 1002
  11.10.4 Security Mitigations......Page 1005
 11.11 SUMMARY......Page 1007
12 OPERATING SYSTEM DESIGN......Page 1013
  12.1.1 Goals......Page 1014
  12.1.2 Why Is It Hard to Design an Operating System?......Page 1015
  12.2.1 Guiding Principles......Page 1017
  12.2.2 Paradigms......Page 1019
  12.2.3 The System-Call Interface......Page 1023
  12.3.1 System Structure......Page 1025
  12.3.2 Mechanism vs. Policy......Page 1029
  12.3.3 Orthogonality......Page 1030
  12.3.4 Naming......Page 1031
  12.3.5 Binding Time......Page 1033
  12.3.6 Static vs. Dynamic Structures......Page 1034
  12.3.7 Top-Down vs. Bottom-Up Implementation......Page 1035
  12.3.8 Synchronous vs. Asynchronous Communication......Page 1036
  12.3.9 Useful Techniques......Page 1037
 12.4 PERFORMANCE......Page 1042
  12.4.2 What Should Be Optimized?......Page 1043
  12.4.3 Space-Time Trade-offs......Page 1044
  12.4.4 Caching......Page 1047
  12.4.5 Hints......Page 1048
  12.4.7 Optimize the Common Case......Page 1049
  12.5.1 The Mythical Man Month......Page 1050
  12.5.2 Team Structure......Page 1051
  12.5.3 The Role of Experience......Page 1053
 12.6 TRENDS IN OPERATING SYSTEM DESIGN......Page 1054
  12.6.2 Manycore Chips......Page 1055
  12.6.3 Large-Address-Space Operating Systems......Page 1056
  12.6.5 Battery-Powered Computers......Page 1057
  12.6.6 Embedded Systems......Page 1058
 12.7 SUMMARY......Page 1059
 13.1 SUGGESTIONS FOR FURTHER READING......Page 1063
  13.1.2 Processes and Threads......Page 1064
  13.1.4 File Systems......Page 1065
  13.1.5 Input/Output......Page 1066
  13.1.7 Virtualization and the Cloud......Page 1067
  13.1.8 Multiple Processor Systems......Page 1068
  13.1.9 Security......Page 1069
  13.1.10 Case Study 1: UNIX, Linux, and Android......Page 1071
  13.1.12 Operating System Design......Page 1072
 13.2 ALPHABETICAL BIBLIOGRAPHY......Page 1073
 A......Page 1105
 B......Page 1107
 C......Page 1108
 D......Page 1109
 E......Page 1111
 F......Page 1112
 G......Page 1113
 I......Page 1114
 L......Page 1116
 M......Page 1118
 N......Page 1120
 O......Page 1121
 P......Page 1122
 R......Page 1125
 S......Page 1126
 T......Page 1129
 U......Page 1130
 V......Page 1131
 W......Page 1132
 Z......Page 1133