Operating Systems Design And Implementation 2nd Edition

CHAPTER 1 INTRODUCTION 1

1.1 WHAT IS AN OPERATING SYSTEM? 3
1.1.1 The Operating System as an Extended Machine 3
1.1.2 The Operating System as a Resource Manager 4

1.2 HISTORY OF OPERATING SYSTEMS 5
1.2.1 The First Generation (1945-55) Vacuum Tubes and Plugboards 6
1.2.2 The Second Generation (1955-65) Transistors and Batch Systems 6
1.2.3 The Third Generation (1965-1980): ICs and Multiprogramming 8
1.2.4 The Fourth Generation (1980-Present): Personal Computers 12
1.2.5 History of MINIX 13

1.3 OPERATING SYSTEM CONCEPTS 15
1.3.1 Processes 15
1.3.2 Files 17
1.3.3 The Shell 20

1.4 SYSTEM CALLS 21
1.4.1 System Calls for Process Management 22
1.4.2 System Calls for Signaling 26 1.4.3 System Calls for File Management 28
1.4.4 System Calls for Directory Management 33
1.4.5 System Calls for Protection 35
1.4.6 System Calls for Time Management 36

1.5 OPERATING SYSTEM STRUCTURE 37
1.5.1 Monolithic Systems 37
1.5.2 Layered Systems 39
1.5.3 Virtual Machines 40
1.5.4 Client-Server Model 42

1.6 OUTLINE OF THE REST OF THIS BOOK 44

1.7 SUMMARY 44

CHAPTER 2 PROCESSES 47

2.1 INTRODUCTION TO PROCESSES 47
2.1.1 The Process Model 48
2.1.2 Implementation of Processes 52
2.1.3 Threads 53

2.2 INTERPROCESS COMMUNICATION 57
2.2.1 Race Conditions 57
2.2.2 Critical Sections 58
2.2.3 Mutual Exclusion with Busy Waiting 59
2.2.4 Sleep and Wakeup 63
2.2.5 Semaphores 66
2.2.6 Monitors 68
2.2.7 Message Passing 72

2.3 CLASSICAL IPC PROBLEMS 75
2.3.1 The Dining Philosophers Problem 75
2.3.2 The Readers and Writers Problem 77
2.3.3 The Sleeping Barber Problem 80

2.4 PROCESS SCHEDULING 82
2.4.1 Round Robin Scheduling 84
2.4.2 Priority Scheduling 85
2.4.3 Multiple Queues 86
2.4.4 Shortest Job First 87
2.4.5 Guaranteed Scheduling 89
2.4.6 Lottery Scheduling 89
2.4.7 Real-Time Scheduling 90
2.4.8 Two-level Scheduling 92
2.4.9 Policy versus Mechanism 93

2.5 OVERVIEW OF PROCESSES IN MINIX 93
2.5.1 The Internal Structure of MINIX 93
2.5.2 Process Management in MINIX 95
2.5.3 Interprocess Communication in MINIX 97
2.5.4 Process Scheduling in MINIX 98

2.6 IMPLEMENTATION OF PROCESSES IN MINIX 98
2.6.1 Organization of the MINIX Source Code 99
2.6.2 The Common Header Files 102
2.6.3 The MINIX Header Files 107
2.6.4 Process Data Structures and Header Files 112
2.6.5 Bootstrapping MINIX 120
2.6.6 System Initialization 122
2.6.7 Interrupt Handling in MINIX 128
2.6.8 Interprocess Communication in MINIX 137
2.6.9 Scheduling in MINIX 140
2.6.10 Hardware-Dependent Kernel Support 142
2.6.11 Utilities and the Kernel Library 145

2.7 SUMMARY 147




CHAPTER 3 INPUT/OUTPUT 153

3.1 PRINCIPLES OF I/O HARDWARE 154
3.1.1 I/O Devices 154
3.1.2 Device Controllers 155
3.1.3 Direct Memory Access (DMA) 157

3.2 PRINCIPLES OF I/O SOFTWARE 159
3.2.1 Goals of the I/O Software 159
3.2.2 Interrupt Handlers 161
3.2.3 Device Drivers 161
3.2.4 Device-Independent I/O Software 162
3.2.5 User-Space I/O Software 164

3.3 DEADLOCKS 166
3.3.1 Resources 167
3.3.2 Principles of Deadlock 168
3.3.3 The Ostrich Algorithm 170
3.3.4 Detection and Recovery 172
3.3.5 Deadlock Prevention 173
3.3.6 Deadlock Avoidance 175

3.4 OVERVIEW OF I/O IN MINIX 179
3.4.1 Interrupt Handlers in MINIX 180
3.4.2 Device Drivers in MINIX 181
3.4.3 Device-Independent I/O Software in MINIX 185
3.4.4 User-level I/O Software in MINIX 185
3.4.5 Deadlock Handling in MINIX 186

3.5 BLOCK DEVICES IN MINIX 187
3.5.1 Overview of Block Device Drivers in MINIX 187
3.5.2 Common Block Device Driver Software 190
3.5.3 The Driver Library 193

3.6 RAM DISKS 195
3.6.1 RAM Disk Hardware and Software 196
3.6.2 Overview of the RAM Disk Driver in MINIX 197
3.6.3 Implementation of the RAM Disk Driver in MINIX 198

3.7 DISKS 200
3.7.1 Disk Hardware 200
3.7.2 Disk Software 202
3.7.3 Overview of the Hard Disk Driver in MINIX 208
3.7.4 Implementation of the Hard Disk Driver in MINIX 211
3.7.5 Floppy Disk Handling 220

3.8 CLOCKS 222
3.8.1 Clock Hardware 223
3.8.2 Clock Software 224
3.8.3 Overview of the Clock Driver in MINIX 227
3.8.4 Implementation of the Clock Driver in MINIX 230

3.9 TERMINALS 235
3.9.1 Terminal Hardware 235
3.9.2 Terminal Software 240
3.9.3 Overview of the Terminal Driver in MINIX 249
3.9.4 Implementation of the Device-Independent Terminal Driver 264
3.9.5 Implementation of the Keyboard Driver 282
3.9.6 Implementation of the Display Driver 288

3.10 THE SYSTEM TASK IN MINIX 296

3.11 SUMMARY 304




CHAPTER 4 MEMORY MANAGEMENT 309

4.1 BASIC MEMORY MANAGEMENT 310
4.1.1 Monoprogramming without Swapping or Paging 310
4.1.2 Multiprogramming wiith Fixed Partitions 311

4.2 SWAPPING 313
4.2.1 Memory Management with Bit Maps 316
4.2.2 Memory Management with Linked Lists 317

4.3 VIRTUAL MEMORY 319
4.3.1 Paging 319
4.3.2 Page Tables 322
4.3.3 TLBs-Translation Lookaside Buffers 327
4.3.4 Inverted Page Tables 330

4.4 PAGE REPLACEMENT ALGORITHMS 331
4.4.1 The Optimal Page Replacement Algorithm 331
4.4.2 The Not-Recently-Used Page Replacement Algorithm 332
4.4.3 The First-In, First-Out (FIFO) Page Replacement Algorithm 333
4.4.4 The Second Chance Page Replacement Algorithm 333
4.4.5 The Clock Page Replacement Algorithm 334
4.4.6 The Least Recently Used (LRU) Page Replacement Algorithm 334
4.4.7 Simulating LRU in Software 336

4.5 DESIGN ISSUES FOR PAGING SYSTEMS 338
4.5.1 The Working Set Model 338
4.5.2 Local versus Global Allocation Policies 339
4.5.3 Page Size 341
4.5.4 Virtual Memory Interface 343

4.6 SEGMENTATION 343
4.6.1 Implementation of Pure Segmentation 347
4.6.2 Segmentation with Paging: MULTICS 348
4.6.3 Segmentation with Paging: The Intel Pentium 352

4.7 OVERVIEW OF MEMORY MANAGEMENT IN MINIX 356
4.7.1 Memory Layout 358
4.7.2 Message Handling 361
4.7.3 Memory Manager Data Structures and Algorithms 363
4.7.4 The FORK, EXIT, and WAIT System Calls 367
4.7.5 The EXEC System Call 368
4.7.6 The BRK System Call 371
4.7.7 Signal Handling 372
4.7.8 Other System Calls 378

4.8 IMPLEMENTATION OF MEMORY MANAGEMENT IN MINIX 379
4.8.1 The Header Files and Data Structures 379
4.8.2 The Main Program 382
4.8.3 Implementation of FORK, EXIT, and WAIT 382
4.8.4 Implementation of EXEC 385
4.8.5 Implementation of BRK 386
4.8.6 Implementation of Signal Handling 387
4.8.7 Implementation of the Other System Calls 393
4.8.8 Memory Manager Utilities 394

4.9 SUMMARY 396




CHAPTER 5 FILE SYSTEMS 401

5.1 FILES 402
5.1.1 File Naming 402
5.1.2 File Structure 404
5.1.3 File Types 405
5.1.4 File Access 407
5.1.5 File Attributes 408
5.1.6 File Operations 409

5.2 DIRECTORIES 410
5.2.1 Hierarchical Directory Systems 411
5.2.2 Path Names 412
5.2.3 Directory Operations 414

5.3 FILE SYSTEM IMPLEMENTATION 415
5.3.1 Implementing Files 415
5.3.2 Implementing Directories 419
5.3.3 Disk Space Management 422
5.3.4 File System Reliability 424
5.3.5 File System Performance 429
5.3.6 Log-Structured File Systems 432

5.4 SECURITY 434
5.4.1 The Security Environment 434
5.4.2 Famous Security Flaws 436
5.4.3 Generic Security Attacks 439
5.4.4 Design Principles for Security 441
5.4.5 User Authentication 442

5.5 PROTECTION MECHANISMS 446
5.5.1 Protection Domains 446
5.5.2 Access Control Lists 448
5.5.3 Capabilities 450
5.5.4 Covert Channels 451

5.6 OVERVIEW OF THE MINIX FILE SYSTEM 453
5.6.1 Messages 454
5.6.2 File System Layout 454
5.6.3 Bit Maps 458
5.6.4 I-nodes 460
5.6.5 The Block Cache 461
5.6.6 Directories and Paths 463
5.6.7 File Descriptors 465
5.6.8 File Locking 467
5.6.9 Pipes and Special Files 467
5.6.10 An Example: The READ System Call 469

5.7 IMPLEMENTATION OF THE MINIX FILE SYSTEM 470
5.7.1 Header Files and Global Data Structures 470
5.7.2 Table Management 474
5.7.3 The Main Program 482
5.7.4 Operations on Individual Files 485
5.7.5 Directories and Paths 493
5.7.6 Other System Calls 498
5.7.7 The I/O Device Interface 501
5.7.8 General Utilities 503

5.8 SUMMARY 503




CHAPTER 6 READING LIST AND BIBLIOGRAPHY 507

6.1 SUGGESTIONS FOR FURTHER READING 507
6.1.1 Introduction and General Works 507
6.1.2 Processes 509
6.1.3 Input/Output 510
6.1.4 Memory Management 511
6.1.5 File Systems 511

6.2 ALPHABETICAL BIBLIOGRAPHY 512

APPENDIX A MINIX SOURCE CODE LISTING 521

APPENDIX B INDEX TO FILES 905

APPENDIX C INDEX TO SYMBOLS 909

INDEX 925

Click here to Download

Read More

Operating Systems Design And Implementation 2nd Edition

CHAPTER 1 INTRODUCTION 1

1.1 WHAT IS AN OPERATING SYSTEM? 3
1.1.1 The Operating System as an Extended Machine 3
1.1.2 The Operating System as a Resource Manager 4

1.2 HISTORY OF OPERATING SYSTEMS 5
1.2.1 The First Generation (1945-55) Vacuum Tubes and Plugboards 6
1.2.2 The Second Generation (1955-65) Transistors and Batch Systems 6
1.2.3 The Third Generation (1965-1980): ICs and Multiprogramming 8
1.2.4 The Fourth Generation (1980-Present): Personal Computers 12
1.2.5 History of MINIX 13

1.3 OPERATING SYSTEM CONCEPTS 15
1.3.1 Processes 15
1.3.2 Files 17
1.3.3 The Shell 20

1.4 SYSTEM CALLS 21
1.4.1 System Calls for Process Management 22
1.4.2 System Calls for Signaling 26

Read More

Handbook of Data Structures and Applications

Edited by
Dinesh P. Mehta
Colorado School of Mines
Golden
and
Sartaj Sahni
University of Florida
Gainesville
Contents
Part I: Fundamentals
1 Analysis of Algorithms Sartaj Sahni . . . . . . . . . . . . . . . . . . . . 1-1
2 Basic Structures Dinesh P. Mehta . . . . . . . . . . . . . . . . . . . . . 2-1
3 Trees Dinesh P. Mehta . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-1
4 Graphs Narsingh Deo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4-1
Part II: Priority Queues
5 Leftist Trees Sartaj Sahni . . . . . . . . . . . . . . . . . . . . . . . . . . 5-1
6 Skew Heaps C. Pandu Rangan . . . . . . . . . . . . . . . . . . . . . . . 6-1
7 Binomial, Fibonacci, and Pairing Heaps Michael L. Fredman . . . . . 7-1
8 Double-Ended Priority Queues Sartaj Sahni . . . . . . . . . . . . . . . 8-1
Part III: Dictionary Structures
9 Hash Tables Pat Morin . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9-1
10 Balanced Binary Search Trees Arne Andersson, Rolf Fagerberg, and Kim
S. Larsen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10-1
11 Finger Search Trees Gerth Stølting Brodal . . . . . . . . . . . . . . . . 11-112 Splay Trees Sanjeev Saxena . . . . . . . . . . . . . . . . . . . . . . . . . 12-1
13 Randomized Dictionary Structures C. Pandu Rangan . . . . . . . . . 13-1
14 Trees with Minimum Weighted Path Length Wojciech Rytter . . . . 14-1
15 B Trees Donghui Zhang . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15-1
Part IV: Multidimensional and Spatial Structures
16 Multidimensional Spatial Data Structures Hanan Samet . . . . . . . 16-1
17 Planar Straight Line Graphs Siu-Wing Cheng . . . . . . . . . . . . . . 17-1
18 Interval, Segment, Range, and Priority Search Trees D. T. Lee . . . . 18-1
19 Quadtrees and Octrees Srinivas Aluru . . . . . . . . . . . . . . . . . . . 19-1
20 Binary Space Partitioning Trees . . . . . . . . . . . . 20-1
21 R-trees Scott Leutenegger and Mario A. Lopez . . . . . . . . . . . . . 21-1
22 Managing Spatio-Temporal Data Sumeet Dua and S. S. Iyengar . . 22-1
23 Kinetic Data Structures Leonidas Guibas . . . . . . . . . . . . . . . . . 23-1
24 Online Dictionary Structures Teofilo F. Gonzalez . . . . . . . . . . . . 24-1
25 Cuttings . . . . . . . . . . . . . . . . . . . . . . . . . . 25-1
26 Approximate Geometric Query Structures Christian A. Duncan and Michael
T. Goodrich . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26-1
27 Geometric and Spatial Data Structures in External Memory Jeffrey Scott
Vitter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27-1
Part V: Miscellaneous Data Structures
28 Tries Sartaj Sahni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28-1
29 Suffix Trees and Suffix Arrays Srinivas Aluru . . . . . . . . . . . . . . 29-1
30 String Searching Andrzej Ehrenfeucht and Ross M. McConnell . . . . 30-1
31 Persistent Data Structures Haim Kaplan . . . . . . . . . . . . . . . . . 31-1
32 PQ Trees, PC Trees, and Planar Graphs Wen-Lian Hsu and Ross M.
McConnell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32-1
33 Data Structures for Sets Rajeev Raman . . . . . . . . . . . . . . . . . . 33-1
34 Cache-Oblivious Data Structures Lars Arge, Gerth Stølting Brodal, and
Rolf Fagerberg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34-1
35 Dynamic Trees Camil Demetrescu, Irene Finocchi, and Giuseppe F. Ital-
iano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35-1
36 Dynamic Graphs Camil Demetrescu, Irene Finocchi, and Giuseppe F.
Italiano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36-1
37 Succinct Representation of Data Structures J. Ian Munro and S. Srini-
vasa Rao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37-1
38 Randomized Graph Data-Structures for Approximate Shortest Paths Suren-
der Baswana and Sandeep Sen . . . . . . . . . . . . . . . . . . . . . . . . . 38-1
39 Searching and Priority Queues in o(log n) Time Arne Andersson . . 39-1
Part VI: Data Structures in Languages and Libraries
40 Functional Data Structures Chris Okasaki . . . . . . . . . . . . . . . . 40-1
41 LEDA, a Platform for Combinatorial and Geometric Computing Stefan
Naeher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41-1
42 Data Structures in C++ Mark Allen Weiss . . . . . . . . . . . . . . . . 42-1
43 Data Structures in JDSL Michael T. Goodrich, Roberto Tamassia, and
Luca Vismara . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43-1
44 Data Structure Visualization John Stasko . . . . . . . . . . . . . . . . . 44-1
45 Drawing Trees Sebastian Leipert . . . . . . . . . . . . . . . . . . . . . . 45-1
46 Drawing Graphs Peter Eades and Seok-Hee Hong . . . . . . . . . . . . 46-1
47 Concurrent Data Structures Mark Moir and Nir Shavit . . . . . . . . 47-1
Part VII: Applications
48 IP Router Tables Sartaj Sahni, Kun Suk Kim, and Haibin Lu . . . 48-1
49 Multi-Dimensional Packet Classification Pankaj Gupta . . . . . . . . 49-1
50 Data Structures in Web Information Retrieval Monika Henzinger . . 50-1
51 The Web as a Dynamic Graph S. N. Maheshwari . . . . . . . . . . . . 51-1
52 Layout Data Structures Dinesh P. Mehta . . . . . . . . . . . . . . . . . 52-1
53 Floorplan Representation in VLSI Zhou Feng, Bo Yao, and Chung-
Kuan Cheng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53-1
54 Computer Graphics Dale McMullin and Alyn Rockwood . . . . . . . 54-1
55 Geographic Information Systems Bernhard Seeger and Peter Widmayer 55-1
56 Collision Detection Ming C. Lin and Dinesh Manocha . . . . . . . . . 56-1
57 Image Data Structures S. S. Iyengar, V. K. Vaishnavi, and S. Gu-
nasekaran . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57-1
58 Computational Biology Stefan Kurtz and Stefano Lonardi . . . . . . 58-1
59 Elimination Structures in Scientific Computing Alex Pothen and Sivan
Toledo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59-1
60 Data Structures for Databases Joachim Hammer and Markus Schneider 60-1
61 Data Mining Vipin Kumar, Pang-Ning Tan, and Michael Steinbach 61-1
62 Computational Geometry: Fundamental Structures Mark de Berg and
Bettina Speckmann . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62-1
63 Computational Geometry: Proximity and Location Sunil Arya and David
M. Mount . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63-1
64 Computational Geometry: Generalized Intersection Searching Prosenjit
Gupta, Ravi Janardan, and Michiel Smid . . . . . . . . . . . . . . . . . . 64-1

Download

Read More

Handbook of Data Structures and Applications

Edited by
Dinesh P. Mehta
Colorado School of Mines
Golden
and
Sartaj Sahni
University of Florida
Gainesville
Contents
Part I: Fundamentals
1 Analysis of Algorithms Sartaj Sahni . . . . . . . . . . . . . . . . . . . . 1-1
2 Basic Structures Dinesh P. Mehta . . . . . . . . . . . . . . . . . . . . . 2-1
3 Trees Dinesh P. Mehta . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-1
4 Graphs Narsingh Deo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4-1
Part II: Priority Queues
5 Leftist Trees Sartaj Sahni . . . . . . . . . . . . . . . . . . . . . . . . . . 5-1
6 Skew Heaps C. Pandu Rangan . . . . . . . . . . . . . . . . . . . . . . . 6-1
7 Binomial, Fibonacci, and Pairing Heaps Michael L. Fredman . . . . . 7-1
8 Double-Ended Priority Queues Sartaj Sahni . . . . . . . . . . . . . . . 8-1
Part III: Dictionary Structures
9 Hash Tables Pat Morin . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9-1
10 Balanced Binary Search Trees Arne Andersson, Rolf Fagerberg, and Kim
S. Larsen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10-1
11 Finger Search Trees Gerth Stølting Brodal . . . . . . . . . . . . . . . . 11-1

Read More

Operating Systems Design And Implementation 2nd Edition

CHAPTER 1 INTRODUCTION 1

1.1 WHAT IS AN OPERATING SYSTEM? 3
1.1.1 The Operating System as an Extended Machine 3
1.1.2 The Operating System as a Resource Manager 4

1.2 HISTORY OF OPERATING SYSTEMS 5
1.2.1 The First Generation (1945-55) Vacuum Tubes and Plugboards 6
1.2.2 The Second Generation (1955-65) Transistors and Batch Systems 6
1.2.3 The Third Generation (1965-1980): ICs and Multiprogramming 8
1.2.4 The Fourth Generation (1980-Present): Personal Computers 12
1.2.5 History of MINIX 13

1.3 OPERATING SYSTEM CONCEPTS 15
1.3.1 Processes 15
1.3.2 Files 17
1.3.3 The Shell 20

1.4 SYSTEM CALLS 21
1.4.1 System Calls for Process Management 22
1.4.2 System Calls for Signaling 26
1.4.3 System Calls for File Management 28
1.4.4 System Calls for Directory Management 33
1.4.5 System Calls for Protection 35
1.4.6 System Calls for Time Management 36

1.5 OPERATING SYSTEM STRUCTURE 37
1.5.1 Monolithic Systems 37
1.5.2 Layered Systems 39
1.5.3 Virtual Machines 40
1.5.4 Client-Server Model 42

1.6 OUTLINE OF THE REST OF THIS BOOK 44

1.7 SUMMARY 44




CHAPTER 2 PROCESSES 47

2.1 INTRODUCTION TO PROCESSES 47
2.1.1 The Process Model 48
2.1.2 Implementation of Processes 52
2.1.3 Threads 53

2.2 INTERPROCESS COMMUNICATION 57
2.2.1 Race Conditions 57
2.2.2 Critical Sections 58
2.2.3 Mutual Exclusion with Busy Waiting 59
2.2.4 Sleep and Wakeup 63
2.2.5 Semaphores 66
2.2.6 Monitors 68
2.2.7 Message Passing 72

2.3 CLASSICAL IPC PROBLEMS 75
2.3.1 The Dining Philosophers Problem 75
2.3.2 The Readers and Writers Problem 77
2.3.3 The Sleeping Barber Problem 80

2.4 PROCESS SCHEDULING 82
2.4.1 Round Robin Scheduling 84
2.4.2 Priority Scheduling 85
2.4.3 Multiple Queues 86
2.4.4 Shortest Job First 87
2.4.5 Guaranteed Scheduling 89
2.4.6 Lottery Scheduling 89
2.4.7 Real-Time Scheduling 90
2.4.8 Two-level Scheduling 92
2.4.9 Policy versus Mechanism 93

2.5 OVERVIEW OF PROCESSES IN MINIX 93
2.5.1 The Internal Structure of MINIX 93
2.5.2 Process Management in MINIX 95
2.5.3 Interprocess Communication in MINIX 97
2.5.4 Process Scheduling in MINIX 98

2.6 IMPLEMENTATION OF PROCESSES IN MINIX 98
2.6.1 Organization of the MINIX Source Code 99
2.6.2 The Common Header Files 102
2.6.3 The MINIX Header Files 107
2.6.4 Process Data Structures and Header Files 112
2.6.5 Bootstrapping MINIX 120
2.6.6 System Initialization 122
2.6.7 Interrupt Handling in MINIX 128
2.6.8 Interprocess Communication in MINIX 137
2.6.9 Scheduling in MINIX 140
2.6.10 Hardware-Dependent Kernel Support 142
2.6.11 Utilities and the Kernel Library 145

2.7 SUMMARY 147




CHAPTER 3 INPUT/OUTPUT 153

3.1 PRINCIPLES OF I/O HARDWARE 154
3.1.1 I/O Devices 154
3.1.2 Device Controllers 155
3.1.3 Direct Memory Access (DMA) 157

3.2 PRINCIPLES OF I/O SOFTWARE 159
3.2.1 Goals of the I/O Software 159
3.2.2 Interrupt Handlers 161
3.2.3 Device Drivers 161
3.2.4 Device-Independent I/O Software 162
3.2.5 User-Space I/O Software 164

3.3 DEADLOCKS 166
3.3.1 Resources 167
3.3.2 Principles of Deadlock 168
3.3.3 The Ostrich Algorithm 170
3.3.4 Detection and Recovery 172
3.3.5 Deadlock Prevention 173
3.3.6 Deadlock Avoidance 175

3.4 OVERVIEW OF I/O IN MINIX 179
3.4.1 Interrupt Handlers in MINIX 180
3.4.2 Device Drivers in MINIX 181
3.4.3 Device-Independent I/O Software in MINIX 185
3.4.4 User-level I/O Software in MINIX 185
3.4.5 Deadlock Handling in MINIX 186

3.5 BLOCK DEVICES IN MINIX 187
3.5.1 Overview of Block Device Drivers in MINIX 187
3.5.2 Common Block Device Driver Software 190
3.5.3 The Driver Library 193

3.6 RAM DISKS 195
3.6.1 RAM Disk Hardware and Software 196
3.6.2 Overview of the RAM Disk Driver in MINIX 197
3.6.3 Implementation of the RAM Disk Driver in MINIX 198

3.7 DISKS 200
3.7.1 Disk Hardware 200
3.7.2 Disk Software 202
3.7.3 Overview of the Hard Disk Driver in MINIX 208
3.7.4 Implementation of the Hard Disk Driver in MINIX 211
3.7.5 Floppy Disk Handling 220

3.8 CLOCKS 222
3.8.1 Clock Hardware 223
3.8.2 Clock Software 224
3.8.3 Overview of the Clock Driver in MINIX 227
3.8.4 Implementation of the Clock Driver in MINIX 230

3.9 TERMINALS 235
3.9.1 Terminal Hardware 235
3.9.2 Terminal Software 240
3.9.3 Overview of the Terminal Driver in MINIX 249
3.9.4 Implementation of the Device-Independent Terminal Driver 264
3.9.5 Implementation of the Keyboard Driver 282
3.9.6 Implementation of the Display Driver 288

3.10 THE SYSTEM TASK IN MINIX 296

3.11 SUMMARY 304




CHAPTER 4 MEMORY MANAGEMENT 309

4.1 BASIC MEMORY MANAGEMENT 310
4.1.1 Monoprogramming without Swapping or Paging 310
4.1.2 Multiprogramming wiith Fixed Partitions 311

4.2 SWAPPING 313
4.2.1 Memory Management with Bit Maps 316
4.2.2 Memory Management with Linked Lists 317

4.3 VIRTUAL MEMORY 319
4.3.1 Paging 319
4.3.2 Page Tables 322
4.3.3 TLBs-Translation Lookaside Buffers 327
4.3.4 Inverted Page Tables 330

4.4 PAGE REPLACEMENT ALGORITHMS 331
4.4.1 The Optimal Page Replacement Algorithm 331
4.4.2 The Not-Recently-Used Page Replacement Algorithm 332
4.4.3 The First-In, First-Out (FIFO) Page Replacement Algorithm 333
4.4.4 The Second Chance Page Replacement Algorithm 333
4.4.5 The Clock Page Replacement Algorithm 334
4.4.6 The Least Recently Used (LRU) Page Replacement Algorithm 334
4.4.7 Simulating LRU in Software 336

4.5 DESIGN ISSUES FOR PAGING SYSTEMS 338
4.5.1 The Working Set Model 338
4.5.2 Local versus Global Allocation Policies 339
4.5.3 Page Size 341
4.5.4 Virtual Memory Interface 343

4.6 SEGMENTATION 343
4.6.1 Implementation of Pure Segmentation 347
4.6.2 Segmentation with Paging: MULTICS 348
4.6.3 Segmentation with Paging: The Intel Pentium 352

4.7 OVERVIEW OF MEMORY MANAGEMENT IN MINIX 356
4.7.1 Memory Layout 358
4.7.2 Message Handling 361
4.7.3 Memory Manager Data Structures and Algorithms 363
4.7.4 The FORK, EXIT, and WAIT System Calls 367
4.7.5 The EXEC System Call 368
4.7.6 The BRK System Call 371
4.7.7 Signal Handling 372
4.7.8 Other System Calls 378

4.8 IMPLEMENTATION OF MEMORY MANAGEMENT IN MINIX 379
4.8.1 The Header Files and Data Structures 379
4.8.2 The Main Program 382
4.8.3 Implementation of FORK, EXIT, and WAIT 382
4.8.4 Implementation of EXEC 385
4.8.5 Implementation of BRK 386
4.8.6 Implementation of Signal Handling 387
4.8.7 Implementation of the Other System Calls 393
4.8.8 Memory Manager Utilities 394

4.9 SUMMARY 396




CHAPTER 5 FILE SYSTEMS 401

5.1 FILES 402
5.1.1 File Naming 402
5.1.2 File Structure 404
5.1.3 File Types 405
5.1.4 File Access 407
5.1.5 File Attributes 408
5.1.6 File Operations 409

5.2 DIRECTORIES 410
5.2.1 Hierarchical Directory Systems 411
5.2.2 Path Names 412
5.2.3 Directory Operations 414

5.3 FILE SYSTEM IMPLEMENTATION 415
5.3.1 Implementing Files 415
5.3.2 Implementing Directories 419
5.3.3 Disk Space Management 422
5.3.4 File System Reliability 424
5.3.5 File System Performance 429
5.3.6 Log-Structured File Systems 432

5.4 SECURITY 434
5.4.1 The Security Environment 434
5.4.2 Famous Security Flaws 436
5.4.3 Generic Security Attacks 439
5.4.4 Design Principles for Security 441
5.4.5 User Authentication 442

5.5 PROTECTION MECHANISMS 446
5.5.1 Protection Domains 446
5.5.2 Access Control Lists 448
5.5.3 Capabilities 450
5.5.4 Covert Channels 451

5.6 OVERVIEW OF THE MINIX FILE SYSTEM 453
5.6.1 Messages 454
5.6.2 File System Layout 454
5.6.3 Bit Maps 458
5.6.4 I-nodes 460
5.6.5 The Block Cache 461
5.6.6 Directories and Paths 463
5.6.7 File Descriptors 465
5.6.8 File Locking 467
5.6.9 Pipes and Special Files 467
5.6.10 An Example: The READ System Call 469

5.7 IMPLEMENTATION OF THE MINIX FILE SYSTEM 470
5.7.1 Header Files and Global Data Structures 470
5.7.2 Table Management 474
5.7.3 The Main Program 482
5.7.4 Operations on Individual Files 485
5.7.5 Directories and Paths 493
5.7.6 Other System Calls 498
5.7.7 The I/O Device Interface 501
5.7.8 General Utilities 503

5.8 SUMMARY 503




CHAPTER 6 READING LIST AND BIBLIOGRAPHY 507

6.1 SUGGESTIONS FOR FURTHER READING 507
6.1.1 Introduction and General Works 507
6.1.2 Processes 509
6.1.3 Input/Output 510
6.1.4 Memory Management 511
6.1.5 File Systems 511

6.2 ALPHABETICAL BIBLIOGRAPHY 512

APPENDIX A MINIX SOURCE CODE LISTING 521

APPENDIX B INDEX TO FILES 905

APPENDIX C INDEX TO SYMBOLS 909

INDEX 925 

Download this book click here

Read More

Operating Systems Design And Implementation 2nd Edition

CHAPTER 1 INTRODUCTION 1

1.1 WHAT IS AN OPERATING SYSTEM? 3
1.1.1 The Operating System as an Extended Machine 3
1.1.2 The Operating System as a Resource Manager 4

1.2 HISTORY OF OPERATING SYSTEMS 5
1.2.1 The First Generation (1945-55) Vacuum Tubes and Plugboards 6
1.2.2 The Second Generation (1955-65) Transistors and Batch Systems 6
1.2.3 The Third Generation (1965-1980): ICs and Multiprogramming 8
1.2.4 The Fourth Generation (1980-Present): Personal Computers 12
1.2.5 History of MINIX 13

1.3 OPERATING SYSTEM CONCEPTS 15
1.3.1 Processes 15
1.3.2 Files 17
1.3.3 The Shell 20

1.4 SYSTEM CALLS 21
1.4.1 System Calls for Process Management 22
1.4.2 System Calls for Signaling 26
1.4.3 System Calls for File Management 28
1.4.4 System Calls for Directory Management 33
1.4.5 System Calls for Protection 35

Read More

Computer Systems Architecture - A Networking Approach

Preface  xiii

Preface to the first edition xv
Recommended lab sessions xxi
Part 1    Basic functions and facilities of a computer
Introduction: the hardware–software interface 3
1.1      Computer systems – the importance of networking 4
1.2      Hardware and software – mutual dependence 5
1.3      Programming your way into hardware – VHDL, a language for
electronic engineers 6
1.4      Systems administration – we all need to know 9
1.5      Voice, image and data – technological convergence 9
1.6      Windowing interfaces – WIMPs 11
1.7      The global Internet – connecting all the networks 13
1.8      Using the PC – a case study; more reasons to study CSA 16
The von Neumann Inheritance 23
2.1      Base 2 – the convenience of binary – 10110011100011110000 24
2.2      Stored program control – general-purpose machines 24
2.3      Instruction codes – machine action repertoire 262.4      Translation – compilers and assemblers 28
2.5      Linking – bringing it all together 28
2.6      Interpreters – executing high-level commands 30
2.7      Code sharing and reuse – let’s not write it all again! 31
2.8      Data codes – numeric and character 32
2.9      The operating system – Unix and Windows 36
2.10    Client–server computing – the way of the Net 40
2.11    Reconfigurable hardware – an alternative to fetch–execute 42
Functional units and the fetch–execute cycle 47
3.1      The naming of parts – CPU, memory, IO units 48
3.2      The CPU fetch–execute cycle – high-speed tedium 52
3.3      System bus – synchronous or asynchronous? 56
3.4      System clock – instruction cycle timing 59
3.5      Pre-fetching – early efforts to speed things up 61
3.6      Memory length – address width 63
3.7      Endian-ness – Microsoft vs. Unix, or Intel vs. Motorola? 65
3.8      Simple input–output – parallel ports 67
Building computers from logic: the control unit 73
4.1      Electronic Lego and logic – the advantage of modular units 74
4.2      Basic logic gates – truth tables for AND, OR, XOR and NOT 75
4.3      Truth tables and multiplexers – a simple but effective design tool 77
4.4      Programmable logic – reconfigurable logic chips 79
4.5      Traffic light controllers – impossible to avoid! 82
4.6      Circuit implementation from truth tables – some practical tips 83
4.7      Decoder logic – essential for control units and memories 85
4.8      CPU control unit – the ‘brain’ 87
4.9      Washing machine controllers – a simple CU 88
4.10    RISC vs. CISC decoding – in search of faster computers 91
Building computers from logic: the ALU 97
5.1      De Morgan’s equivalences – logical interchangeability 98
5.2      Binary addition – half adders, full adders, parallel adders 98
5.3      Binary subtraction – using two’s complement integer format 101
5.4      Binary shifting – barrel shifter 103
5.5      Integer multiplication – shifting and adding 105
5.6      Floating-point numbers – from very, very large to very, very small 108
Building computers from logic: the memory 117
6.1      Data storage – one bit at a time 118
6.2      Memory devices – memory modules for computers 120
6.3      Static memory – a lot of fast flip-flops 121
6.4      Dynamic memory – a touch of analogue amid the digital 122
6.5      DRAM refreshing – something else to do 124
6.6      Page access memories – EDO and SDRAM 124
6.7      Memory mapping – addressing and decoding 127
6.8      IO port mapping – integration vs. differentiation 131
The Intel Pentium CPU 137
7.1      The Pentium – a high-performance microprocessor 138
7.2      CPU registers – temporary store for data and address variables 143
7.3      Instruction set – introduction to the basic Pentium set 148
7.4      Structure of instructions – how the CU sees it 149
7.5      CPU status flags – very short-term memory 151
7.6      Addressing modes – building effective addresses 153
7.7      Execution pipelines – the RISC speedup technique 155
7.8      Pentium 4 – extensions 157
7.9      Microsoft Developer Studio – using the debugger 158
Subroutines 167
8.1      The purpose of subroutines – saving space and effort 168
8.2      Return address – introducing the stack 169
8.3      Using subroutines – HLL programming 170
8.4      The stack – essential to most operations 172
8.5      Passing parameters – localizing a subroutine 173
8.6      Stack frame – all the local variables 176
8.7      Supporting HLLs – special CPU facilities for dealing with subroutines   179
8.8      Interrupt service routines – hardware-invoked subroutines 179
8.9      Accessing operating system routines – late binding 180
Simple input and output 185
9.1      Basic IO methods – polling, interrupt and DMA 186
9.2      Peripheral interface registers – the programmer’s viewpoint 187
9.3      Polling – single-character IO 191
9.4      Interrupt processing – service on demand 197
9.5      Critical data protection – how to communicate with interrupts 205
9.6      Buffered IO – interrupt device drivers 209
9.7      Direct memory access (DMA) – autonomous hardware 210
9.8      Single-character IO – screen and keyboard routines 212
Serial Connections 219
10.1    Serial transmission – data, signals and timing 220
10.2    Data format – encoding techniques 221
10.3    Timing synchronization – frequency and phase 224
10.4    Data codes and error control – parity, checksums, Hamming codes
and CRCs 227
10.5    Flow control – hardware and software methods 235
10.6    The 16550 UART – RS232 237
10.7    Serial mice – mechanical or optical 244
10.8    Serial ports – practical tips, avoiding the frustration 246
10.9    USB – Universal Serial Bus 246
10.10  Modems – modulating carrier waves 252
Parallel connections 263
11.1    Parallel interfaces – better performance 264
11.2    Centronics – more than a printer port but less than a bus 264
11.3    SCSI – the Small Computer Systems Interface 267
11.4    IDE – Intelligent Drive Electronics 271
11.5    AT/ISA – a computer standards success story 272
11.6    PCI – Peripheral Component Interconnection 275
11.7    Plug-and-Play – automatic configuration 278
11.8    PCMCIA – Personal Computer Memory Card
International Association 280
The memory hierarchy 285
12.1    Levels of performance – you get what you pay for 286
12.2    Localization of access – exploiting repetition 288
12.3    Instruction and data caches – matching memory to CPU speed 293
12.4    Cache mapping – direct or associative 295
12.5    Virtual memory – segmentation and demand paging 299
12.6    Address formulation – when, where and how much 304
12.7    Hard disk usage – parameters, access scheduling and
data arrangement 306
12.8    Performance improvement – blocking, caching, defragmentation,
scheduling, RAM disk 310
12.9    Optical discs – CD-DA, CD-ROM, CD-RW and DVDs 312
12.10  DVD – Digital Versatile Disc 316
12.11  MPEG – video and audio compression 316
12.12  Flash sticks – the new floppy disk 323
Part 2    Networking and increased complexity
The programmer’s viewpoint 329
13.1    Different viewpoints – different needs 330
13.2    Application user – office packages 331
13.3    Systems administration – software installation and maintenance         333
13.4    HLL programmer – working with Java, C++, BASIC or C# 337
13.5    Systems programming – assembler and C 340
13.6    Hardware engineer – design and hardware maintenance 344
13.7    Layered virtual machines – hierarchical description 345
13.8    Assemblers – simple translators 346
13.9    Compilers – translation and more 347
Local area networks 353
14.1    Reconnecting the users – email, printers and database 354
14.2    PC network interface – cabling and interface card 359
14.3    Ethernet – Carrier Sense, Multiple Access/Collision Detect 363
14.4    LAN addressing – logical and physical schemes 367
14.5    Host names – another layer of translation 370
14.6    Layering and encapsulation – TCP/IP software stack 371
14.7    Networked file systems – sharing files across a network 372
14.8    Interconnecting networks – gateways 374
14.9    Socket programming – an introduction to WinSock 374
Wide area networks 383
15.1    The Internet – origins 384
15.2    TCP/IP – the essential protocols 386
15.3    TCP – handling errors and flow control 390
15.4    IP routing – how packets find their way 392
15.5    DNS – Distributed Name Database 398
15.6    World Wide Web – the start 401
15.7    Browsing the Web – Netscape Navigator 403
15.8    HTTP – another protocol 407
15.9    Search engines – Google 409
15.10  Open Systems Interconnect – an idealized scheme 412
Other networks 419
16.1    The PSTN – telephones 420
16.2    Cellnets – providers of mobile communications 426
16.3    ATM – Asynchronous Transfer Mode 435
16.4    Messaging – radio paging and packet radio networks 440
16.5    ISDN – totally digital 442
16.6    DSL – Digital Subscriber Line 446
16.7    Cable television – facilities for data transmission 447
Introduction to operating systems 455
17.1    Historic origins – development of basic functions 456
17.2    Unix – a landmark operating system 459
17.3    Outline structure – modularization 462
17.4    Process management – initialization and dispatching 463
17.5    Scheduling decisions – time-slicing, demand preemption
or cooperative 469
17.6    Task communication – pipes and redirection 471
17.7    Exclusion and synchronization – semaphores and signals 473
17.8    Memory allocation – malloc( ) and free( ) 479
17.9    User interface – GUIs and shells 481
17.10  Input–output management – device handlers 482
Windows XP 491
18.1    Windows GUIs – responding to a need 492
18.2    Win32 – the preferred user API 494
18.3    Processes and threads – multitasking 495
18.4    Memory management – virtual memory implementation 496
18.5    Windows Registry – centralized administrative database 496
18.6    NTFS – Windows NT File System 498
18.7    File access – ACLs, permissions and security 499
18.8    Sharing software components – OLE, DDE and COM 502
18.9    Windows NT as a mainframe – Winframe terminal server 502
Filing systems 507
19.1    Data storage – file systems and databases 508
19.2    The PC file allocation table – FAT 515
19.3    Unix inodes – they do it differently 518
19.4    Microsoft NTFS – complexity and security 523
19.5    RAID configuration – more security for the disk subsystem 525
19.6    File security – access controls 526
19.7    CD portable file system – multi-session contents lists 528
Visual output 533
20.1    Computers and graphics – capture, storage, processing
and redisplay 534
20.2    PC graphics adapter cards – graphics coprocessors 541
20.3    Laser printers – this is mechatronics! 547
20.4    Adobe PostScript – a page description language 549
20.5    WIMPs – remodelling the computer 554
20.6    Win32 – graphical API and more 555
20.7    The X Window system – enabling distributed processing 557
20.8    MMX technology – assisting graphical calculations 558
RISC processors: ARM and SPARC 563
21.1    Justifying RISC – increased instruction throughput 564
21.2    Pipeline techniques – more parallel operations 569
21.3    Superscalar methods – parallel parallelism 571
21.4    Register files – many more CPU registers 572
21.5    Branch prediction methods – maintaining the pipelines 574
21.6    Compiler support – an essential part of RISC 576
21.7    The ARM 32 bit CPU – origins 576
21.8    StrongARM processor – a 32 bit microcontroller 585
21.9    The HP iPAQ – a StrongARM PDA 588
21.10  Puppeteer – a StrongARM SBC 590
21.11  Sun SPARC – scalar processor architecture as RISC 592
21.12  Embedded systems – cross-development techniques 594
VLIW processors: the EPIC Itanium 601
22.1    Itanium 64 bit processor – introduction 602
22.2    Itanium assembler – increasing the control of the CPU 609
22.3    Run-time debugging – gvd/gdb 613
22.4    Future processor design – debate 615
Parallel processing 619
23.1    Parallel processing – the basis 620
23.2    Instruction-level parallelism (ILP) – pipelining 623
23.3    Superscalar – multiple execution units 623
23.4    Symmetric, shared memory multiprocessing (SMP) – the future?         623
23.5    Single-chip multiprocessors – the IBM Cell 626
23.6    Clusters and grids – application-level parallelism 629
Appendix: MS Visual Studio 8, Express Edition 635
Glossary 647
Answers to end-of-chapter questions 661
References 713
Index 717

Computer architecture - Wikipedia, the free encyclopedia
Computer Architecture Tutorial
Download

Read More

Computer Systems Architecture - A Networking Approach

Preface  xiii

Preface to the first edition xv
Recommended lab sessions xxi
Part 1    Basic functions and facilities of a computer
Introduction: the hardware–software interface 3
1.1      Computer systems – the importance of networking 4
1.2      Hardware and software – mutual dependence 5
1.3      Programming your way into hardware – VHDL, a language for
electronic engineers 6
1.4      Systems administration – we all need to know 9
1.5      Voice, image and data – technological convergence 9
1.6      Windowing interfaces – WIMPs 11
1.7      The global Internet – connecting all the networks 13
1.8      Using the PC – a case study; more reasons to study CSA 16
The von Neumann Inheritance 23
2.1      Base 2 – the convenience of binary – 10110011100011110000 24
2.2      Stored program control – general-purpose machines 24
2.3      Instruction codes – machine action repertoire 26

Read More

Operating Systems Design And Implementation 2nd Edition

Download this book click






CHAPTER 1 INTRODUCTION 1

1.1 WHAT IS AN OPERATING SYSTEM? 3
1.1.1 The Operating System as an Extended Machine 3
1.1.2 The Operating System as a Resource Manager 4

1.2 HISTORY OF OPERATING SYSTEMS 5
1.2.1 The First Generation (1945-55) Vacuum Tubes and Plugboards 6
1.2.2 The Second Generation (1955-65) Transistors and Batch Systems 6

1.2.3 The Third Generation (1965-1980): ICs and Multiprogramming 8
1.2.4 The Fourth Generation (1980-Present): Personal Computers 12
1.2.5 History of MINIX 13

1.3 OPERATING SYSTEM CONCEPTS 15
1.3.1 Processes 15
1.3.2 Files 17
1.3.3 The Shell 20

1.4 SYSTEM CALLS 21
1.4.1 System Calls for Process Management 22
1.4.2 System Calls for Signaling 26
1.4.3 System Calls for File Management 28
1.4.4 System Calls for Directory Management 33
1.4.5 System Calls for Protection 35
1.4.6 System Calls for Time Management 36

1.5 OPERATING SYSTEM STRUCTURE 37
1.5.1 Monolithic Systems 37
1.5.2 Layered Systems 39
1.5.3 Virtual Machines 40
1.5.4 Client-Server Model 42

1.6 OUTLINE OF THE REST OF THIS BOOK 44

1.7 SUMMARY 44




CHAPTER 2 PROCESSES 47

2.1 INTRODUCTION TO PROCESSES 47
2.1.1 The Process Model 48
2.1.2 Implementation of Processes 52
2.1.3 Threads 53

2.2 INTERPROCESS COMMUNICATION 57
2.2.1 Race Conditions 57
2.2.2 Critical Sections 58
2.2.3 Mutual Exclusion with Busy Waiting 59
2.2.4 Sleep and Wakeup 63
2.2.5 Semaphores 66
2.2.6 Monitors 68
2.2.7 Message Passing 72

2.3 CLASSICAL IPC PROBLEMS 75
2.3.1 The Dining Philosophers Problem 75
2.3.2 The Readers and Writers Problem 77
2.3.3 The Sleeping Barber Problem 80

2.4 PROCESS SCHEDULING 82
2.4.1 Round Robin Scheduling 84
2.4.2 Priority Scheduling 85
2.4.3 Multiple Queues 86
2.4.4 Shortest Job First 87
2.4.5 Guaranteed Scheduling 89
2.4.6 Lottery Scheduling 89
2.4.7 Real-Time Scheduling 90
2.4.8 Two-level Scheduling 92
2.4.9 Policy versus Mechanism 93

2.5 OVERVIEW OF PROCESSES IN MINIX 93
2.5.1 The Internal Structure of MINIX 93
2.5.2 Process Management in MINIX 95
2.5.3 Interprocess Communication in MINIX 97
2.5.4 Process Scheduling in MINIX 98

2.6 IMPLEMENTATION OF PROCESSES IN MINIX 98
2.6.1 Organization of the MINIX Source Code 99
2.6.2 The Common Header Files 102
2.6.3 The MINIX Header Files 107
2.6.4 Process Data Structures and Header Files 112
2.6.5 Bootstrapping MINIX 120
2.6.6 System Initialization 122
2.6.7 Interrupt Handling in MINIX 128
2.6.8 Interprocess Communication in MINIX 137
2.6.9 Scheduling in MINIX 140
2.6.10 Hardware-Dependent Kernel Support 142
2.6.11 Utilities and the Kernel Library 145

2.7 SUMMARY 147




CHAPTER 3 INPUT/OUTPUT 153

3.1 PRINCIPLES OF I/O HARDWARE 154
3.1.1 I/O Devices 154
3.1.2 Device Controllers 155
3.1.3 Direct Memory Access (DMA) 157

3.2 PRINCIPLES OF I/O SOFTWARE 159
3.2.1 Goals of the I/O Software 159
3.2.2 Interrupt Handlers 161
3.2.3 Device Drivers 161
3.2.4 Device-Independent I/O Software 162
3.2.5 User-Space I/O Software 164

3.3 DEADLOCKS 166
3.3.1 Resources 167
3.3.2 Principles of Deadlock 168
3.3.3 The Ostrich Algorithm 170
3.3.4 Detection and Recovery 172
3.3.5 Deadlock Prevention 173
3.3.6 Deadlock Avoidance 175

3.4 OVERVIEW OF I/O IN MINIX 179
3.4.1 Interrupt Handlers in MINIX 180
3.4.2 Device Drivers in MINIX 181
3.4.3 Device-Independent I/O Software in MINIX 185
3.4.4 User-level I/O Software in MINIX 185
3.4.5 Deadlock Handling in MINIX 186

3.5 BLOCK DEVICES IN MINIX 187
3.5.1 Overview of Block Device Drivers in MINIX 187
3.5.2 Common Block Device Driver Software 190
3.5.3 The Driver Library 193

3.6 RAM DISKS 195
3.6.1 RAM Disk Hardware and Software 196
3.6.2 Overview of the RAM Disk Driver in MINIX 197
3.6.3 Implementation of the RAM Disk Driver in MINIX 198

3.7 DISKS 200
3.7.1 Disk Hardware 200
3.7.2 Disk Software 202
3.7.3 Overview of the Hard Disk Driver in MINIX 208
3.7.4 Implementation of the Hard Disk Driver in MINIX 211
3.7.5 Floppy Disk Handling 220

3.8 CLOCKS 222
3.8.1 Clock Hardware 223
3.8.2 Clock Software 224
3.8.3 Overview of the Clock Driver in MINIX 227
3.8.4 Implementation of the Clock Driver in MINIX 230

3.9 TERMINALS 235
3.9.1 Terminal Hardware 235
3.9.2 Terminal Software 240
3.9.3 Overview of the Terminal Driver in MINIX 249
3.9.4 Implementation of the Device-Independent Terminal Driver 264
3.9.5 Implementation of the Keyboard Driver 282
3.9.6 Implementation of the Display Driver 288

3.10 THE SYSTEM TASK IN MINIX 296

3.11 SUMMARY 304




CHAPTER 4 MEMORY MANAGEMENT 309

4.1 BASIC MEMORY MANAGEMENT 310
4.1.1 Monoprogramming without Swapping or Paging 310
4.1.2 Multiprogramming wiith Fixed Partitions 311

4.2 SWAPPING 313
4.2.1 Memory Management with Bit Maps 316
4.2.2 Memory Management with Linked Lists 317

4.3 VIRTUAL MEMORY 319
4.3.1 Paging 319
4.3.2 Page Tables 322
4.3.3 TLBs-Translation Lookaside Buffers 327
4.3.4 Inverted Page Tables 330

4.4 PAGE REPLACEMENT ALGORITHMS 331
4.4.1 The Optimal Page Replacement Algorithm 331
4.4.2 The Not-Recently-Used Page Replacement Algorithm 332
4.4.3 The First-In, First-Out (FIFO) Page Replacement Algorithm 333
4.4.4 The Second Chance Page Replacement Algorithm 333
4.4.5 The Clock Page Replacement Algorithm 334
4.4.6 The Least Recently Used (LRU) Page Replacement Algorithm 334
4.4.7 Simulating LRU in Software 336

4.5 DESIGN ISSUES FOR PAGING SYSTEMS 338
4.5.1 The Working Set Model 338
4.5.2 Local versus Global Allocation Policies 339
4.5.3 Page Size 341
4.5.4 Virtual Memory Interface 343

4.6 SEGMENTATION 343
4.6.1 Implementation of Pure Segmentation 347
4.6.2 Segmentation with Paging: MULTICS 348
4.6.3 Segmentation with Paging: The Intel Pentium 352

4.7 OVERVIEW OF MEMORY MANAGEMENT IN MINIX 356
4.7.1 Memory Layout 358
4.7.2 Message Handling 361
4.7.3 Memory Manager Data Structures and Algorithms 363
4.7.4 The FORK, EXIT, and WAIT System Calls 367
4.7.5 The EXEC System Call 368
4.7.6 The BRK System Call 371
4.7.7 Signal Handling 372
4.7.8 Other System Calls 378

4.8 IMPLEMENTATION OF MEMORY MANAGEMENT IN MINIX 379
4.8.1 The Header Files and Data Structures 379
4.8.2 The Main Program 382
4.8.3 Implementation of FORK, EXIT, and WAIT 382
4.8.4 Implementation of EXEC 385
4.8.5 Implementation of BRK 386
4.8.6 Implementation of Signal Handling 387
4.8.7 Implementation of the Other System Calls 393
4.8.8 Memory Manager Utilities 394

4.9 SUMMARY 396




CHAPTER 5 FILE SYSTEMS 401

5.1 FILES 402
5.1.1 File Naming 402
5.1.2 File Structure 404
5.1.3 File Types 405
5.1.4 File Access 407
5.1.5 File Attributes 408
5.1.6 File Operations 409

5.2 DIRECTORIES 410
5.2.1 Hierarchical Directory Systems 411
5.2.2 Path Names 412
5.2.3 Directory Operations 414

5.3 FILE SYSTEM IMPLEMENTATION 415
5.3.1 Implementing Files 415
5.3.2 Implementing Directories 419
5.3.3 Disk Space Management 422
5.3.4 File System Reliability 424
5.3.5 File System Performance 429
5.3.6 Log-Structured File Systems 432

5.4 SECURITY 434
5.4.1 The Security Environment 434
5.4.2 Famous Security Flaws 436
5.4.3 Generic Security Attacks 439
5.4.4 Design Principles for Security 441
5.4.5 User Authentication 442

5.5 PROTECTION MECHANISMS 446
5.5.1 Protection Domains 446
5.5.2 Access Control Lists 448
5.5.3 Capabilities 450
5.5.4 Covert Channels 451

5.6 OVERVIEW OF THE MINIX FILE SYSTEM 453
5.6.1 Messages 454
5.6.2 File System Layout 454
5.6.3 Bit Maps 458
5.6.4 I-nodes 460
5.6.5 The Block Cache 461
5.6.6 Directories and Paths 463
5.6.7 File Descriptors 465
5.6.8 File Locking 467
5.6.9 Pipes and Special Files 467
5.6.10 An Example: The READ System Call 469

5.7 IMPLEMENTATION OF THE MINIX FILE SYSTEM 470
5.7.1 Header Files and Global Data Structures 470
5.7.2 Table Management 474
5.7.3 The Main Program 482
5.7.4 Operations on Individual Files 485
5.7.5 Directories and Paths 493
5.7.6 Other System Calls 498
5.7.7 The I/O Device Interface 501
5.7.8 General Utilities 503

5.8 SUMMARY 503




CHAPTER 6 READING LIST AND BIBLIOGRAPHY 507

6.1 SUGGESTIONS FOR FURTHER READING 507
6.1.1 Introduction and General Works 507
6.1.2 Processes 509
6.1.3 Input/Output 510
6.1.4 Memory Management 511
6.1.5 File Systems 511

6.2 ALPHABETICAL BIBLIOGRAPHY 512

APPENDIX A MINIX SOURCE CODE LISTING 521

APPENDIX B INDEX TO FILES 905

APPENDIX C INDEX TO SYMBOLS 909

INDEX 925

Read More

Operating Systems Design And Implementation 2nd Edition

Download this book click






CHAPTER 1 INTRODUCTION 1

1.1 WHAT IS AN OPERATING SYSTEM? 3
1.1.1 The Operating System as an Extended Machine 3
1.1.2 The Operating System as a Resource Manager 4

1.2 HISTORY OF OPERATING SYSTEMS 5
1.2.1 The First Generation (1945-55) Vacuum Tubes and Plugboards 6
1.2.2 The Second Generation (1955-65) Transistors and Batch Systems 6

Read More