Modern operating systems

✍ Scribed by Tanenbaum, Andrew S;Bos, Herbert

• Publisher: Pearson Education (Us); Langara College
• Year: 2016
• Tongue: English
• Leaves: 1137
• Edition: Fourth edition
• Category: Library

✦ Synopsis

"Modern Operating Systems, Fourth Edition, "" is intended for introductory courses in Operating Systems in Computer Science, Computer Engineering, and Electrical Engineering programs. It also serves as a useful reference for OS professionals" The widely anticipated revision of this worldwide best-seller incorporates the latest developments in operating systems (OS) technologies. The Fourth Edition includes up-to-date materials on relevant OS. Tanenbaum also provides information on current research based on his experience as an operating systems researcher. "Modern Operating Systems, "Third Editionwas the recipient of the 2010 McGuffey Longevity Award. The McGuffey Longevity Award recognizes textbooks whose excellence has been demonstrated over time. http: //taaonline.net/index.htmlTeaching and Learning ExperienceThis program will provide a better teaching and learning experience-for you and your students. It will help: Provide Practical Detail on the Big Picture Concepts: A clear and entertaining writing style outlines the concepts every OS designer needs to master.Keep Your Course Current: This edition includes information on the latest OS technologies and developmentsEnhance Learning with Student and Instructor Resources: Students will gain hands-on experience using the simulation exercises and lab experiments.

✦ Table of Contents

Cover......Page 1
Title Page......Page 4
Copyright Page......Page 5
ABOUT THE AUTHORS......Page 28
CONTENTS......Page 8
PREFACE......Page 24
1 INTRODUCTION......Page 32
1.1 WHAT IS AN OPERATING SYSTEM?......Page 34
1.1.1 The Operating System as an Extended Machine......Page 35
1.1.2 The Operating System as a Resource Manager......Page 36
1.2 HISTORY OF OPERATING SYSTEMS......Page 37
1.2.1 The First Generation (1945–55): Vacuum Tubes......Page 38
1.2.2 The Second Generation (1955–65): Transistors and Batch Systems......Page 39
1.2.3 The Third Generation (1965–1980): ICs and Multiprogramming......Page 40
1.2.4 The Fourth Generation (1980–Present): Personal Computers......Page 46
1.2.5 The Fifth Generation (1990–Present): Mobile Computers......Page 50
1.3 COMPUTER HARDWARE REVIEW......Page 51
1.3.1 Processors......Page 52
1.3.2 Memory......Page 55
1.3.3 Disks......Page 58
1.3.4 I/O Devices......Page 59
1.3.5 Buses......Page 63
1.3.6 Booting the Computer......Page 65
1.4.2 Server Operating Systems......Page 66
1.4.5 Handheld Computer Operating Systems......Page 67
1.4.8 Real-Time Operating Systems......Page 68
1.5 OPERATING SYSTEM CONCEPTS......Page 69
1.5.1 Processes......Page 70
1.5.3 Files......Page 72
1.5.6 The Shell......Page 76
1.5.7 Ontogeny Recapitulates Phylogeny......Page 78
1.6 SYSTEM CALLS......Page 81
1.6.1 System Calls for Process Management......Page 84
1.6.2 System Calls for File Management......Page 87
1.6.3 System Calls for Directory Management......Page 88
1.6.4 Miscellaneous System Calls......Page 90
1.6.5 The Windows Win32 API......Page 91
1.7 OPERATING SYSTEM STRUCTURE......Page 93
1.7.1 Monolithic Systems......Page 94
1.7.2 Layered Systems......Page 95
1.7.3 Microkernels......Page 96
1.7.4 Client-Server Model......Page 99
1.7.5 Virtual Machines......Page 100
1.8.1 The C Language......Page 104
1.8.2 Header Files......Page 105
1.8.3 Large Programming Projects......Page 106
1.8.4 The Model of Run Time......Page 107
1.9 RESEARCH ON OPERATING SYSTEMS......Page 108
1.10 OUTLINE OF THE REST OF THIS BOOK......Page 109
1.11 METRIC UNITS......Page 110
1.12 SUMMARY......Page 111
2.1 PROCESSES......Page 116
2.1.1 The Process Model......Page 117
2.1.2 Process Creation......Page 119
2.1.3 Process Termination......Page 121
2.1.4 Process Hierarchies......Page 122
2.1.5 Process States......Page 123
2.1.6 Implementation of Processes......Page 125
2.1.7 Modeling Multiprogramming......Page 126
2.2.1 Thread Usage......Page 128
2.2.2 The Classical Thread Model......Page 133
2.2.3 POSIX Threads......Page 137
2.2.4 Implementing Threads in User Space......Page 139
2.2.5 Implementing Threads in the Kernel......Page 142
2.2.6 Hybrid Implementations......Page 143
2.2.7 Scheduler Activations......Page 144
2.2.8 Pop-Up Threads......Page 145
2.2.9 Making Single-Threaded Code Multithreaded......Page 147
2.3.1 Race Conditions......Page 150
2.3.2 Critical Regions......Page 152
2.3.3 Mutual Exclusion with Busy Waiting......Page 153
2.3.4 Sleep and Wakeup......Page 158
2.3.5 Semaphores......Page 161
2.3.6 Mutexes......Page 163
2.3.7 Monitors......Page 168
2.3.8 Message Passing......Page 175
2.3.9 Barriers......Page 177
2.3.10 Avoiding Locks: Read-Copy-Update......Page 179
2.4 SCHEDULING......Page 180
2.4.1 Introduction to Scheduling......Page 181
2.4.2 Scheduling in Batch Systems......Page 187
2.4.3 Scheduling in Interactive Systems......Page 189
2.4.4 Scheduling in Real-Time Systems......Page 195
2.4.5 Policy Versus Mechanism......Page 196
2.4.6 Thread Scheduling......Page 197
2.5.1 The Dining Philosophers Problem......Page 198
2.5.2 The Readers and Writers Problem......Page 202
2.6 RESEARCH ON PROCESSES AND THREADS......Page 203
2.7 SUMMARY......Page 204
3 MEMORY MANAGEMENT......Page 212
3.1 NO MEMORY ABSTRACTION......Page 213
3.2 A MEMORY ABSTRACTION: ADDRESS SPACES......Page 216
3.2.1 The Notion of an Address Space......Page 217
3.2.2 Swapping......Page 218
3.2.3 Managing Free Memory......Page 221
3.3 VIRTUAL MEMORY......Page 225
3.3.1 Paging......Page 226
3.3.2 Page Tables......Page 229
3.3.3 Speeding Up Paging......Page 232
3.3.4 Page Tables for Large Memories......Page 236
3.4.1 The Optimal Page Replacement Algorithm......Page 240
3.4.2 The Not Recently Used Page Replacement Algorithm......Page 241
3.4.3 The First-In, First-Out (FIFO) Page Replacement Algorithm......Page 242
3.4.5 The Clock Page Replacement Algorithm......Page 243
3.4.6 The Least Recently Used (LRU) Page Replacement Algorithm......Page 244
3.4.7 Simulating LRU in Software......Page 245
3.4.8 The Working Set Page Replacement Algorithm......Page 246
3.4.9 The WSClock Page Replacement Algorithm......Page 250
3.4.10 Summary of Page Replacement Algorithms......Page 252
3.5.1 Local versus Global Allocation Policies......Page 253
3.5.3 Page Size......Page 256
3.5.4 Separate Instruction and Data Spaces......Page 258
3.5.5 Shared Pages......Page 259
3.5.6 Shared Libraries......Page 260
3.5.7 Mapped Files......Page 262
3.5.9 Virtual Memory Interface......Page 263
3.6.1 Operating System Involvement with Paging......Page 264
3.6.2 Page Fault Handling......Page 265
3.6.3 Instruction Backup......Page 266
3.6.5 Backing Store......Page 268
3.6.6 Separation of Policy and Mechanism......Page 270
3.7 SEGMENTATION......Page 271
3.7.2 Segmentation with Paging: MULTICS......Page 274
3.7.3 Segmentation with Paging: The Intel x86......Page 278
3.8 RESEARCH ON MEMORY MANAGEMENT......Page 283
3.9 SUMMARY......Page 284
4 FILE SYSTEMS......Page 294
4.1.1 File Naming......Page 296
4.1.2 File Structure......Page 298
4.1.3 File Types......Page 299
4.1.4 File Access......Page 301
4.1.5 File Attributes......Page 302
4.1.6 File Operations......Page 303
4.1.7 An Example Program Using File-System Calls......Page 304
4.2.2 Hierarchical Directory Systems......Page 307
4.2.3 Path Names......Page 308
4.2.4 Directory Operations......Page 311
4.3.1 File-System Layout......Page 312
4.3.2 Implementing Files......Page 313
4.3.3 Implementing Directories......Page 319
4.3.4 Shared Files......Page 321
4.3.5 Log-Structured File Systems......Page 324
4.3.6 Journaling File Systems......Page 326
4.3.7 Virtual File Systems......Page 327
4.4 FILE-SYSTEM MANAGEMENT AND OPTIMIZATION......Page 330
4.4.1 Disk-Space Management......Page 331
4.4.2 File-System Backups......Page 337
4.4.3 File-System Consistency......Page 343
4.4.4 File-System Performance......Page 345
4.4.5 Defragmenting Disks......Page 350
4.5.1 The MS-DOS File System......Page 351
4.5.2 The UNIX V7 File System......Page 354
4.5.3 CD-ROM File Systems......Page 356
4.6 RESEARCH ON FILE SYSTEMS......Page 362
4.7 SUMMARY......Page 363
5.1 PRINCIPLES OF I/O HARDWARE......Page 368
5.1.1 I/O Devices......Page 369
5.1.2 Device Controllers......Page 370
5.1.3 Memory-Mapped I/O......Page 371
5.1.4 Direct Memory Access......Page 375
5.1.5 Interrupts Revisited......Page 378
5.2.1 Goals of the I/O Software......Page 382
5.2.2 Programmed I/O......Page 383
5.2.3 Interrupt-Driven I/O......Page 385
5.2.4 I/O Using DMA......Page 386
5.3.1 Interrupt Handlers......Page 387
5.3.2 Device Drivers......Page 388
5.3.3 Device-Independent I/O Software......Page 392
5.3.4 User-Space I/O Software......Page 398
5.4.1 Disk Hardware......Page 400
5.4.2 Disk Formatting......Page 406
5.4.3 Disk Arm Scheduling Algorithms......Page 410
5.4.4 Error Handling......Page 413
5.4.5 Stable Storage......Page 416
5.5.1 Clock Hardware......Page 419
5.5.2 Clock Software......Page 421
5.5.3 Soft Timers......Page 423
5.6.1 Input Software......Page 425
5.6.2 Output Software......Page 430
5.7 THIN CLIENTS......Page 447
5.8 POWER MANAGEMENT......Page 448
5.8.1 Hardware Issues......Page 449
5.8.2 Operating System Issues......Page 450
5.8.3 Application Program Issues......Page 456
5.9 RESEARCH ON INPUT/OUTPUT......Page 457
5.10 SUMMARY......Page 459
6 DEADLOCKS......Page 466
6.1.1 Preemptable and Nonpreemptable Resources......Page 467
6.1.2 Resource Acquisition......Page 468
6.2 INTRODUCTION TO DEADLOCKS......Page 470
6.2.2 Deadlock Modeling......Page 471
6.4 DEADLOCK DETECTION AND RECOVERY......Page 474
6.4.1 Deadlock Detection with One Resource of Each Type......Page 475
6.4.2 Deadlock Detection with Multiple Resources of Each Type......Page 477
6.4.3 Recovery from Deadlock......Page 480
6.5.1 Resource Trajectories......Page 481
6.5.2 Safe and Unsafe States......Page 483
6.5.3 The Banker’s Algorithm for a Single Resource......Page 484
6.5.4 The Banker’s Algorithm for Multiple Resources......Page 485
6.6.2 Attacking the Hold-and-Wait Condition......Page 487
6.6.4 Attacking the Circular Wait Condition......Page 488
6.7 OTHER ISSUES......Page 489
6.7.2 Communication Deadlocks......Page 490
6.7.3 Livelock......Page 492
6.7.4 Starvation......Page 494
6.9 SUMMARY......Page 495
7 VIRTUALIZATION AND THE CLOUD......Page 502
7.1 HISTORY......Page 504
7.2 REQUIREMENTS FOR VIRTUALIZATION......Page 505
7.3 TYPE 1 AND TYPE 2 HYPERVISORS......Page 508
7.4 TECHNIQUES FOR EFFICIENT VIRTUALIZATION......Page 509
7.4.1 Virtualizing the Unvirtualizable......Page 510
7.4.2 The Cost of Virtualization......Page 513
7.5 ARE HYPERVISORS MICROKERNELS DONE RIGHT?......Page 514
7.6 MEMORY VIRTUALIZATION......Page 517
7.7 I/O VIRTUALIZATION......Page 521
7.8 VIRTUAL APPLIANCES......Page 524
7.10 LICENSING ISSUES......Page 525
7.11 CLOUDS......Page 526
7.11.2 Virtual Machine Migration......Page 527
7.11.3 Checkpointing......Page 528
7.12.1 The Early History of VMware......Page 529
7.12.2 VMware Workstation......Page 530
7.12.3 Challenges in Bringing Virtualization to the x86......Page 531
7.12.4 VMware Workstation: Solution Overview......Page 533
7.12.5 The Evolution of VMware Workstation......Page 542
7.12.6 ESX Server: VMware’s type 1 Hypervisor......Page 543
7.13 RESEARCH ON VIRTUALIZATION AND THE CLOUD......Page 545
8 MULTIPLE PROCESSOR SYSTEMS......Page 548
8.1.1 Multiprocessor Hardware......Page 551
8.1.2 Multiprocessor Operating System Types......Page 562
8.1.3 Multiprocessor Synchronization......Page 565
8.1.4 Multiprocessor Scheduling......Page 570
8.2 MULTICOMPUTERS......Page 576
8.2.1 Multicomputer Hardware......Page 577
8.2.2 Low-Level Communication Software......Page 581
8.2.3 User-Level Communication Software......Page 584
8.2.4 Remote Procedure Call......Page 587
8.2.5 Distributed Shared Memory......Page 589
8.2.7 Load Balancing......Page 594
8.3 DISTRIBUTED SYSTEMS......Page 597
8.3.1 Network Hardware......Page 599
8.3.2 Network Services and Protocols......Page 603
8.3.3 Document-Based Middleware......Page 607
8.3.4 File-System-Based Middleware......Page 608
8.3.5 Object-Based Middleware......Page 613
8.3.6 Coordination-Based Middleware......Page 615
8.4 RESEARCH ON MULTIPLE PROCESSOR SYSTEMS......Page 618
8.5 SUMMARY......Page 619
9 SECURITY......Page 624
9.1 THE SECURITY ENVIRONMENT......Page 626
9.1.1 Threats......Page 627
9.2 OPERATING SYSTEMS SECURITY......Page 630
9.2.1 Can We Build Secure Systems?......Page 631
9.2.2 Trusted Computing Base......Page 632
9.3 CONTROLLING ACCESS TO RESOURCES......Page 633
9.3.1 Protection Domains......Page 634
9.3.2 Access Control Lists......Page 636
9.3.3 Capabilities......Page 639
9.4 FORMAL MODELS OF SECURE SYSTEMS......Page 642
9.4.1 Multilevel Security......Page 643
9.4.2 Covert Channels......Page 646
9.5 BASICS OF CRYPTOGRAPHY......Page 650
9.5.1 Secret-Key Cryptography......Page 651
9.5.2 Public-Key Cryptography......Page 652
9.5.3 One-Way Functions......Page 653
9.5.4 Digital Signatures......Page 654
9.5.5 Trusted Platform Modules......Page 655
9.6 AUTHENTICATION......Page 657
9.6.1 Authentication Using a Physical Object......Page 664
9.6.2 Authentication Using Biometrics......Page 667
9.7 EXPLOITING SOFTWARE......Page 670
9.7.1 Buffer Overflow Attacks......Page 671
9.7.2 Format String Attacks......Page 680
9.7.3 Dangling Pointers......Page 683
9.7.4 Null Pointer Dereference Attacks......Page 684
9.7.5 Integer Overflow Attacks......Page 685
9.7.6 Command Injection Attacks......Page 686
9.7.7 Time of Check to Time of Use Attacks......Page 687
9.8.1 Logic Bombs......Page 688
9.8.2 Back Doors......Page 689
9.8.3 Login Spoofing......Page 690
9.9 MALWARE......Page 691
9.9.1 Trojan Horses......Page 694
9.9.2 Viruses......Page 695
9.9.3 Worms......Page 705
9.9.4 Spyware......Page 707
9.9.5 Rootkits......Page 711
9.10 DEFENSES......Page 715
9.10.1 Firewalls......Page 716
9.10.2 Antivirus and Anti-Antivirus Techniques......Page 718
9.10.3 Code Signing......Page 724
9.10.4 Jailing......Page 725
9.10.5 Model-Based Intrusion Detection......Page 726
9.10.6 Encapsulating Mobile Code......Page 728
9.10.7 Java Security......Page 732
9.11 RESEARCH ON SECURITY......Page 734
9.12 SUMMARY......Page 735
10 CASE STUDY 1: UNIX, LINUX, AND ANDROID......Page 744
10.1.1 UNICS......Page 745
10.1.2 PDP-11 UNIX......Page 746
10.1.3 Portable UNIX......Page 747
10.1.4 Berkeley UNIX......Page 748
10.1.5 Standard UNIX......Page 749
10.1.6 MINIX......Page 750
10.1.7 Linux......Page 751
10.2.1 Linux Goals......Page 754
10.2.2 Interfaces to Linux......Page 755
10.2.3 The Shell......Page 757
10.2.4 Linux Utility Programs......Page 760
10.2.5 Kernel Structure......Page 762
10.3.1 Fundamental Concepts......Page 764
10.3.2 Process-Management System Calls in Linux......Page 767
10.3.3 Implementation of Processes and Threads in Linux......Page 771
10.3.4 Scheduling in Linux......Page 777
10.3.5 Booting Linux......Page 782
10.4 MEMORY MANAGEMENT IN LINUX......Page 784
10.4.1 Fundamental Concepts......Page 785
10.4.2 Memory Management System Calls in Linux......Page 787
10.4.3 Implementation of Memory Management in Linux......Page 789
10.4.4 Paging in Linux......Page 795
10.5.1 Fundamental Concepts......Page 798
10.5.2 Networking......Page 800
10.5.3 Input/Output System Calls in Linux......Page 801
10.5.4 Implementation of Input/Output in Linux......Page 802
10.5.5 Modules in Linux......Page 805
10.6.1 Fundamental Concepts......Page 806
10.6.2 File-System Calls in Linux......Page 811
10.6.3 Implementation of the Linux File System......Page 815
10.6.4 NFS: The Network File System......Page 823
10.7.1 Fundamental Concepts......Page 829
10.7.3 Implementation of Security in Linux......Page 832
10.8 ANDROID......Page 833
10.8.1 Android and Google......Page 834
10.8.2 History of Android......Page 835
10.8.3 Design Goals......Page 838
10.8.4 Android Architecture......Page 840
10.8.5 Linux Extensions......Page 841
10.8.6 Dalvik......Page 845
10.8.7 Binder IPC......Page 846
10.8.8 Android Applications......Page 855
10.8.9 Intents......Page 867
10.8.11 Security......Page 869
10.8.12 Process Model......Page 875
10.9 SUMMARY......Page 880
11.1 HISTORY OF WINDOWS THROUGH WINDOWS 8.1......Page 888
11.1.1 1980s: MS-DOS......Page 889
11.1.3 2000s: NT-based Windows......Page 890
11.1.4 Windows Vista......Page 893
11.1.5 2010s: Modern Windows......Page 894
11.2 PROGRAMMING WINDOWS......Page 895
11.2.1 The Native NT Application Programming Interface......Page 899
11.2.2 The Win32 Application Programming Interface......Page 902
11.2.3 The Windows Registry......Page 906
11.3.1 Operating System Structure......Page 908
11.3.2 Booting Windows......Page 924
11.3.3 Implementation of the Object Manager......Page 925
11.3.4 Subsystems, DLLs, and User-Mode Services......Page 936
11.4.1 Fundamental Concepts......Page 939
11.4.2 Job, Process, Thread, and Fiber Management API Calls......Page 945
11.4.3 Implementation of Processes and Threads......Page 950
11.5 MEMORY MANAGEMENT......Page 958
11.5.1 Fundamental Concepts......Page 959
11.5.2 Memory-Management System Calls......Page 962
11.5.3 Implementation of Memory Management......Page 964
11.6 CACHING IN WINDOWS......Page 973
11.7 INPUT/OUTPUT IN WINDOWS......Page 974
11.7.1 Fundamental Concepts......Page 975
11.7.2 Input/Output API Calls......Page 976
11.7.3 Implementation of I/O......Page 979
11.8 THE WINDOWS NT FILE SYSTEM......Page 983
11.8.1 Fundamental Concepts......Page 984
11.8.2 Implementation of the NT File System......Page 985
11.9 WINDOWS POWER MANAGEMENT......Page 995
11.10 SECURITY IN WINDOWS 8......Page 997
11.10.1 Fundamental Concepts......Page 998
11.10.2 Security API Calls......Page 1000
11.10.3 Implementation of Security......Page 1001
11.10.4 Security Mitigations......Page 1004
11.11 SUMMARY......Page 1006
12 OPERATING SYSTEM DESIGN......Page 1012
12.1.1 Goals......Page 1013
12.1.2 Why Is It Hard to Design an Operating System?......Page 1014
12.2.1 Guiding Principles......Page 1016
12.2.2 Paradigms......Page 1018
12.2.3 The System-Call Interface......Page 1022
12.3.1 System Structure......Page 1024
12.3.2 Mechanism vs. Policy......Page 1028
12.3.3 Orthogonality......Page 1029
12.3.4 Naming......Page 1030
12.3.5 Binding......Page 1032
12.3.6 Static vs. Dynamic Structures......Page 1033
12.3.7 Top-Down vs. Bottom-Up Implementation......Page 1034
12.3.8 Synchronous vs. Asynchronous Communication......Page 1035
12.3.9 Useful Techniques......Page 1036
12.4 PERFORMANCE......Page 1041
12.4.2 What Should Be Optimized?......Page 1042
12.4.3 Space-Time Trade-offs......Page 1043
12.4.4 Caching......Page 1046
12.4.5 Hints......Page 1047
12.4.7 Optimize the Common Case......Page 1048
12.5.1 The Mythical Man Month......Page 1049
12.5.2 Team Structure......Page 1050
12.5.3 The Role of Experience......Page 1052
12.6 TRENDS IN OPERATING SYSTEM DESIGN......Page 1053
12.6.2 Manycore Chips......Page 1054
12.6.3 Large-Address-Space Operating Systems......Page 1055
12.6.5 Battery-Powered Computers......Page 1056
12.6.6 Embedded Systems......Page 1057
12.7 SUMMARY......Page 1058
13.1 SUGGESTIONS FOR FURTHER READING......Page 1062
13.1.2 Processes and Threads......Page 1063
13.1.4 File Systems......Page 1064
13.1.5 Input/Output......Page 1065
13.1.7 Virtualization and the Cloud......Page 1066
13.1.8 Multiple Processor Systems......Page 1067
13.1.9 Security......Page 1068
13.1.10 Case Study 1: UNIX, Linux, and Android......Page 1070
13.1.12 Operating System Design......Page 1071
13.2 ALPHABETICAL BIBLIOGRAPHY......Page 1072
A......Page 1104
B......Page 1106
C......Page 1107
D......Page 1108
E......Page 1110
F......Page 1111
G......Page 1112
I......Page 1113
L......Page 1115
M......Page 1117
N......Page 1119
O......Page 1120
P......Page 1121
R......Page 1124
S......Page 1125
T......Page 1128
U......Page 1129
V......Page 1130
W......Page 1131
Z......Page 1132

✦ Subjects

Science;Computer Science;Programming;Nonfiction;Technical;Technology;Reference;Computers;Software;Textbooks