دانلود کتاب Operating Systems Design and Implementation

فهرست مطالب :

Cover......Page 1
CONTENTS......Page 8
PREFACE......Page 16
1 INTRODUCTION......Page 20
1.1.1 The Operating System as an Extended Machine......Page 23
1.1.2 The Operating System as a Resource Manager......Page 24
1.2 HISTORY OF OPERATING SYSTEMS......Page 25
1.2.2 The Second Generation (1955–65) Transistors and Batch Systems......Page 26
1.2.3 The Third Generation (1965–1980) ICs and Multiprogramming......Page 28
1.2.4 The Fourth Generation (1980–Present) Personal Computers......Page 33
1.2.5 History of MINIX 3......Page 35
1.3 OPERATING SYSTEM CONCEPTS......Page 38
1.3.1 Processes......Page 39
1.3.2 Files......Page 41
1.3.3 The Shell......Page 44
1.4 SYSTEM CALLS......Page 45
1.4.1 System Calls for Process Management......Page 46
1.4.2 System Calls for Signaling......Page 50
1.4.3 System Calls for File Management......Page 52
1.4.4 System Calls for Directory Management......Page 57
1.4.5 System Calls for Protection......Page 59
1.5.1 Monolithic Systems......Page 61
1.5.2 Layered Systems......Page 64
1.5.3 Virtual Machines......Page 65
1.5.5 Client-Server Model......Page 68
1.7 SUMMARY......Page 70
2.1 INTRODUCTION TO PROCESSES......Page 74
2.1.1 The Process Model......Page 75
2.1.2 Process Creation......Page 76
2.1.3 Process Termination......Page 78
2.1.5 Process States......Page 79
2.1.6 Implementation of Processes......Page 81
2.1.7 Threads......Page 83
2.2 INTERPROCESS COMMUNICATION......Page 87
2.2.1 Race Conditions......Page 88
2.2.2 Critical Sections......Page 89
2.2.3 Mutual Exclusion with Busy Waiting......Page 90
2.2.4 Sleep and Wakeup......Page 95
2.2.5 Semaphores......Page 97
2.2.7 Monitors......Page 100
2.2.8 Message Passing......Page 104
2.3 CLASSICAL IPC PROBLEMS......Page 107
2.3.1 The Dining Philosophers Problem......Page 108
2.3.2 The Readers and Writers Problem......Page 111
2.4 SCHEDULING......Page 112
2.4.1 Introduction to Scheduling......Page 113
2.4.2 Scheduling in Batch Systems......Page 118
2.4.3 Scheduling in Interactive Systems......Page 121
2.4.4 Scheduling in Real-Time Systems......Page 128
2.4.6 Thread Scheduling......Page 129
2.5.1 The Internal Structure of MINIX 3......Page 131
2.5.2 Process Management in MINIX 3......Page 135
2.5.3 Interprocess Communication in MINIX 3......Page 139
2.5.4 Process Scheduling in MINIX 3......Page 141
2.6.1 Organization of the MINIX 3 Source Code......Page 144
2.6.2 Compiling and Runniing MINIX 3......Page 147
2.6.3 The Common Header Files......Page 149
2.6.4 The MINIX 3 Header Files......Page 157
2.6.5 Process Data Structures and Header Files......Page 165
2.6.6 Bootstrapping MINIX 3......Page 175
2.6.7 System Initialization......Page 179
2.6.8 Interrupt Handling in MINIX 3......Page 186
2.6.9 Interprocess Communication in MINIX 3......Page 197
2.6.10 Scheduling in MINIX 3......Page 201
2.6.11 Hardware-Dependent Kernel Support......Page 204
2.6.12 Utilities and the Kernel Library......Page 209
2.7 THE SYSTEM TASK IN MINIX 3......Page 211
2.7.1 Overview of the System Task......Page 213
2.7.2 Implementation of the System Task......Page 216
2.7.3 Implementation of the System Libarary......Page 219
2.8.1 Clock Hardware......Page 223
2.8.2 Clock Software......Page 225
2.8.3 Overview of the Clock Driver in MINIX 3......Page 227
2.8.4 Implementation of the Clock Driver in MINIX 3......Page 231
2.9 SUMMARY......Page 233
3 INPUT/OUTPUT......Page 240
3.1.1 I/O Devices......Page 241
3.1.2 Device Controllers......Page 242
3.1.3 Memory-Mapped I/O......Page 244
3.1.4 Interrupts......Page 245
3.1.5 Direct Memory Access......Page 246
3.2.1 Goals of the I/O Software......Page 248
3.2.3 Device Drivers......Page 250
3.2.4 Device-Independent I/O Software......Page 252
3.2.5 User-Space I/O Software......Page 255
3.3 DEADLOCKS......Page 256
3.3.1 Resources......Page 257
3.3.2 Principles of Deadlock......Page 258
3.3.3 The Ostrich Algorithm......Page 261
3.3.4 Detection and Recovery......Page 263
3.3.5 Deadlock Prevention......Page 264
3.3.6 Deadlock Avoidance......Page 266
3.4.1 Interrupt Handlers in MINIX 3......Page 271
3.4.2 Device Drivers in MINIX 3......Page 275
3.4.3 Device-Independent I/O Software in MINIX 3......Page 278
3.4.5 Deadlock Handling in MINIX 3......Page 279
3.5 BLOCK DEVICES IN MINIX3......Page 280
3.5.1 Overview of Block Device Drivers in MINIX 3......Page 281
3.5.2 Common Block Device Driver Software......Page 284
3.5.3 The Driver Library......Page 288
3.6.1 RAM Disk Hardware and Software......Page 290
3.6.2 Overview of the RAM Disk Driver in MINIX 3......Page 292
3.6.3 Implementation of the RAM Disk Driver in MINIX 3......Page 293
3.7.1 Disk Hardware......Page 297
3.7.2 RAID......Page 299
3.7.3 Disk Software......Page 300
3.7.4 Overview of the Hard Disk Driver in MINIX 3......Page 306
3.7.5 Implementation of the Hard Disk Driver in MINIX 3......Page 309
3.7.6 Floppy Disk Handling......Page 319
3.8 TERMINALS......Page 321
3.8.1 Terminal Hardware......Page 322
3.8.2 Terminal Software......Page 326
3.8.3 Overview of the Terminal Driver in MINIX 3......Page 335
3.8.4 Implementation of the Device-Independent Terminal Driver......Page 350
3.8.5 Implementation of the Keyboard Driver......Page 369
3.8.6 Implementation of the Display Driver......Page 376
3.9 SUMMARY......Page 385
4 MEMORY MANAGEMENT......Page 392
4.1.1 Monoprogramming without Swapping or Paging......Page 393
4.1.2 Multiprogramming with Fixed Partitions......Page 394
4.1.3 Relocation and Protection......Page 396
4.2 SWAPPING......Page 397
4.2.1 Memory Management with Bitmaps......Page 399
4.2.2 Memory Management with Linked Lists......Page 400
4.3 VIRTUAL MEMORY......Page 402
4.3.1 Paging......Page 403
4.3.2 Page Tables......Page 407
4.3.3 TLBs—Translation Lookaside Buffers......Page 411
4.3.4 Inverted Page Tables......Page 414
4.4 PAGE REPLACEMENT ALGORITHMS......Page 415
4.4.1 The Optimal Page Replacement Algorithm......Page 416
4.4.2 The Not Recently Used Page Replacement Algorithm......Page 417
4.4.4 The Second Chance Page Replacement Algorithm......Page 418
4.4.5 The Clock Page Replacement Algorithm......Page 419
4.4.7 Simulating LRU in Software......Page 420
4.5.1 The Working Set Model......Page 423
4.5.2 Local versus Global Allocation Policies......Page 425
4.5.3 Page Size......Page 427
4.6 SEGMENTATION......Page 429
4.6.1 Implementation of Pure Segmentation......Page 433
4.6.2 Segmentation with Paging: The Intel Pentium......Page 434
4.7 OVERVIEW OF THE MINIX 3 PROCESS MANAGER......Page 439
4.7.1 Memory Layout......Page 441
4.7.2 Message Handling......Page 444
4.7.3 Process Manager Data Structures and Algorithms......Page 445
4.7.4 The FORK, EXIT, and WAIT System Calls......Page 451
4.7.5 The EXEC System Call......Page 452
4.7.6 The BRK System Call......Page 456
4.7.7 Signal Handling......Page 457
4.7.8 Other System Calls......Page 465
4.8.1 The Header Files and Data Structures......Page 466
4.8.2 The Main Program......Page 469
4.8.3 Implementation of FORK, EXIT, and WAIT......Page 474
4.8.4 Implementation of EXEC......Page 477
4.8.5 Implementation of BRK......Page 480
4.8.6 Implementation of Signal Handling......Page 481
4.8.7 Implementation of Other System Calls......Page 490
4.8.8 Memory Management Utilities......Page 492
4.9 SUMMARY......Page 494
5 FILE SYSTEMS......Page 500
5.1.1 File Naming......Page 501
5.1.2 File Structure......Page 503
5.1.3 File Types......Page 504
5.1.5 File Attributes......Page 507
5.1.6 File Operations......Page 509
5.2.1 Simple Directories......Page 510
5.2.2 Hierarchical Directory Systems......Page 511
5.2.3 Path Names......Page 512
5.2.4 Directory Operations......Page 515
5.3.1 File System Layout......Page 516
5.3.2 Implementing Files......Page 518
5.3.3 Implementing Directories......Page 521
5.3.4 Disk Space Management......Page 528
5.3.5 File System Reliability......Page 531
5.3.6 File System Performance......Page 538
5.3.7 Log-Structured File Systems......Page 543
5.4.1 The Security Environment......Page 545
5.4.2 Generic Security Attacks......Page 550
5.4.3 Design Principles for Security......Page 551
5.4.4 User Authentication......Page 552
5.5.1 Protection Domains......Page 556
5.5.2 Access Control Lists......Page 558
5.5.3 Capabilities......Page 561
5.5.4 Covert Channels......Page 564
5.6 OVERVIEW OF THE MINIX 3 FILE SYSTEM......Page 567
5.6.2 File System Layout......Page 569
5.6.3 Bitmaps......Page 572
5.6.4 I-Nodes......Page 574
5.6.5 The Block Cache......Page 576
5.6.6 Directories and Paths......Page 578
5.6.7 File Descriptors......Page 580
5.6.9 Pipes and Special Files......Page 582
5.6.10 An Example: The READ System Call......Page 584
5.7.1 Header Files and Global Data Structures......Page 585
5.7.2 Table Management......Page 589
5.7.3 The Main Program......Page 598
5.7.4 Operations on Individual Files......Page 602
5.7.5 Directories and Paths......Page 610
5.7.6 Other System Calls......Page 615
5.7.7 The I/O Device Interface......Page 616
5.7.8 Additional System Call Support......Page 622
5.7.9 File System Utilities......Page 624
SUMMARY......Page 625
6.1.1 Introduction and General Works......Page 630
6.1.3 Input/Output......Page 633
6.1.4 Memory Management......Page 634
6.1.5 File Systems......Page 635
6.2 ALPHABETICAL BIBLIOGRAPHY......Page 637
APPENDICES......Page 646
A: INSTALLING MINIX 3......Page 648
B: MINIX 3 SOURCE CODE LISTING......Page 656
C: INDEX TO FILES......Page 1052
A......Page 1054
C......Page 1055
D......Page 1056
G......Page 1057
I......Page 1058
L......Page 1059
M......Page 1060
O......Page 1065
P......Page 1066
S......Page 1067
U......Page 1069
Z......Page 1070