操作系统 原理与设计 英文PDF电子书下载

1 INTRODUCTION TO THE OPERATING SYSTEM 1

1.1 OS Functions 1

1.1.1 OS Acts as a User/Computer Interface 1

1.1.2 Interaction with OS 3

1.1.3 Operating System Commands 5

1.1.4 Operating System as Efficient Resource Manager 19

1.1.5 OS Upgrading 21

1.1.6 Operating System Security and Protection 22

1.2 Evolution of Operating System 31

1.2.1 Serial Processing 31

1.2.2 Batch Processing 32

1.2.3 Multiprogramming or Simple Concurrent Processing 34

1.2.4 Resource Management 35

1.2.5 Operating System Structure 43

1.2.6 Future Operating System Trends 48

Summary 49

Exercises 49

2 OS PREREQUISITES 50

2.1 Important Software Resources to be Managed by OS 50

2.2 Interaction with OS in Mainframe Systems(Interrupts in General) 55

2.2.1 The Program Status Word 55

2.2.2 Different Fields of PSW 55

2.2.3 Controlling I/O 57

2.2.4 The Interrupt Concept 60

2.2.5 Interrupt Priority 65

2.2.6 What Other Manufacturers(Other than IBM)Do? 66

2.2.7 Interrupt Cycle 67

2.2.8 Differences between Subroutine Call and Interrupt Scheme 68

2.3 Example from PC Environment and Related Discussion 69

2.3.1 Different Ways to Control PC Hardware 69

2.3.2 Accessing the BIOS and DOS 71

2.4 Current'State-of-the-Art'Scenario in OS Design 75

2.5 Fundamental Concepts Related to IPC 100

2.5.1 Message Queues 102

2.5.2 Semaphores 111

2.5.3 Shared Memory 120

Summary 124

Exercises 124

3 CONCURRENT PROCESSING 126

3.1 Introduction to Concurrent Processing 126

3.2 Process Concept 127

3.3 Introduction to Process Control Block 128

3.4 Interaction of User's Process with the System 139

3.4.1 Exec sys 140

3.5 Introduction to Concurrent Program 144

3.6 Distinction between a Procedure Call and a Process Creation 145

3.7 Introduction to Process Environment 148

3.7.1 Introduction to Process id 148

3.7.2 Shells or Command Interpreter 154

3.8 Process State Transitions 155

3.9 Difference between User,Daemon and Kernel Processes 160

3.10 Interprocess Communication 161

3.10.1 File and Record Locking 161

3.10.2 Simple Pipes and Named Pipes 188

3.10.3 Pipes and Sockets 188

3.11 Hierarchy of Processes 190

3.11.1 Process Creation 191

3.11.2 Processes and Threads 191

Summary 193

Exercises 194

4 SCHEDULING 195

4.1 CPU Scheduling Algorithms 195

4.1.1 Allocation of Different Resources 195

4.1.2 Scheduling Queues 196

4.1.3 Different Scheduling Algorithms 207

4.1.4 Algorithm Evaluation 226

Summary 227

Exercises 228

5 DISCUSSION ON CONCURRENCY CONTROL 229

5.1 Bernstein's Concurrency Conditions 229

5.1.1 Fork and Join Construct 230

5.1.2 Alternative to Fork-Join 235

5.2 Process States and Precedence Graphs 238

5.3 Dijkstra's Concurrent Statement in the Form of Fork and Join Constructs 238

5.4 The Critical Section Problem 239

5.4.1 Bounded Buffer Producer-Consumer Problem 239

5.4.2 Critical Section Problem Description and Their Solution 245

5.5 Hardware Solution to the Critical Section Problem 264

5.6 New Synchronization Tool—Semaphore 266

5.6.1 Usage of Semaphores 266

5.7 Classical Process Coordination Problems 269

5.7.1 Bounded Buffer Problem 269

5.7.2 The Reader's and Writer's Problem 272

5.7.3 Dining Philosophers' Problem 294

5.7.4 Sleeping Barber Problem 299

5.7.5 Cigarette Smoker's Problem 307

5.8 Language Constructs for Synchronization and Modularization 310

5.8.1 Critical Regions 311

5.8.2 Conditional Critical Region 313

5.8.3 Monitor Construct 315

Summary 334

Exercises 334

6 DEADLOCK 336

6.1 Introduction 336

6.2 Definition of Deadlock 337

6.3 Deadlock and Starvation 338

6.4 Resource Allocation Graph 339

6.5 Ways to Solve Deadlock Problem 341

6.5.1 Tackling Deadlock Using Deadlock Prevention 341

6.5.2 Deadlock Avoidance 342

6.5.3 Deadlock Detection 351

6.5.4 Difference between Deadlock Detection Algorithm (Multiple Instances of each Resource Type)and Safety Algorithm 356

6.5.5 Solution of Deadlock under Difierent Scenarios 357

Summary 360

Exercises 360

7 MAIN MEMORY MANAGEMENT 362

7.1 Introduction 362

7.2 Memory Management Schemes 363

7.3 Partitioned Allocation 364

7.4 Logical vs Physical Address Space 366

7.4.1 Address Binding 366

7.4.2 Address Translation 367

7.5 Simple Paging 367

7.6 The Role of the Long-term Scheduler 369

7.6.1 Problem Assignment 369

7.7 Implementation of the Page Table 377

7.8 Multiple Process Using a Text Editor Code 378

7.9 Simple Segmentation 378

7.10 Details of Segmentation 379

7.11 Combined System 381

7.11.1 Combination Used in GE645 Multics System 382

7.12 Inner Details of Segmentation and Paging for Intel Systems 383

Summary 385

Exercises 386

8 VIRTUAL MEMORY TECHNIQUE 387

8.1 Introduction 387

8.2 Overlays Technique 388

8.3 Virtual Memory 389

8.3.1 Virtual Memory Concept 389

8.4 Demand Paging 395

8.4.1 Performance of Demand Paging 396

8.5 Page Replacement Algorithm 397

8.5.1 FIFO(Simplest Page Replacement Algorithm is First In First Out) 398

8.5.2 Optimal Replacement 400

8.5.3 Least Recently Used(LRU)Algorithm 405

8.5.4 Second Chance Replacement(With the Help of Reference Bit) 422

8.5.5 Ad hoc Page Replacement Algorithms 423

8.6 Free Frame Allocation Algorithm 424

8.6.1 Equal Allocation 424

8.6.2 Proportional Allocation(According to their Needs Rather than Equal) 424

8.7 Thrashing 425

8.8 Working Set 426

8.8.1 Prepaging 427

8.8.2 I/O Interlock 427

8.8.3 Page Size Anomaly 427

8.9 Program Structure 428

Summary 429

Exercises 430

9 SPOOLER AND DISK SCHEDULING 432

9.1 Introduction to the Design of a Spooling System 432

9.2 Relationship between Spooling and Job Scheduling 434

9.2.1 A Printer Spooler 435

9.3 Device Management 443

9.4 Physical Characteristics of Disks 443

9.4.1 Disks 443

9.5 FCFS Disk Scheduling 444

9.6 Searching an Item in the Disk with Indexed Sequential File Directory 448

9.6.1 Shortest Seek Time First(SSTF) 452

Summary 454

Exercises 454

10 FILE SYSTEM ARCHITECTURE 456

10.1 Overview 456

10.2 Initial Notions 457

10.2.1 Files 457

10.2.2 Directories 457

10.2.3 Different Types of Directories under the UNIX System 458

10.2.4 The Directory and File Naming Conventions 458

10.2.5 Difference between COM and EXE Program 459

10.2.6 Abbreviations for Path Names 460

10.2.7 Paths are Used 462

10.3 Attributes of UNIX Files(For the Beginners) 462

10.3.1 The File Owner and the Group 462

10.3.2 Access Permissions 463

10.3.3 Creating a File 463

10.3.4 Removing Files 466

10.3.5 Maintaining Files 466

10.4 File System and their Type 467

10.4.1 Evolution of File System Over the Years 468

10.5 Introduction of EXT2 FS 468

10.5.1 The View of Inodes from the Point of View of a Blocks Group 469

10.5.2 The Allocated Blocks 472

10.5.3 User and Group id 473

10.6 Virtual File System (VFS） 481

10.6.1 The Linux Virtual File System Layer 481

10.6.2 Registration Procedures of VFS 481

10.6.3 Registering the File Systems in Kernel 484

10.7 Program Designs 488

Appendix 490

End Notes 509

Summary 512

Exercises 512

11 DEVICE DRIVER FOR OPERATING SYSTEM 513

11.1 Introduction 513

11.2 Initial Notions for the Design 514

11.3 Interfacing Device Drivers with the Kernel 530

11.3.1 Character Devices 530

11.3.2 Block Devices 531

11.3.3 Network Device 533

11.4 Theory to Practice 535

Summary 548

Exercises 548

12 LINUX KERNEL AND SECURITY 550

12.1 Introduction 550

12.2 Basics Notions 550

12.2.1 What are LKMs 550

12.2.2 What are System Calls 552

12.2.3 What is Kernel Symbol Table 557

12.2.4 How to Trarnsform Kernel to User Space Memory 558

12.2.5 Ways to Use User Space Like Functions 560

12.2.6 List of Daily Needed Kernel Space Functions 561

12.2.7 What is Kernel Daemon 563

12.2.8 Creating Your Own Devices 563

12.3 Experiments with Linux System Calls 565

12.3.1 How to Intercept Syscalls 565

12.3.2 Interesting System Calls to Intercept 566

12.3.3 File System-Related Hacks 571

12.3.4 Process-Related Hacks 578

12.3.5 Network(Socket)-Related Hacks 583

12.3.6 Virus Writing with LKMs 587

12.4 Directives to the System Administrators for Secured System 593

12.4.1 Theory and Ideas on LKM Detector 593

12.5 The Last Word on the'LKM Story' 613

Summary 613

Exercises 613

13 ROLE OF OS TOWARDS LOW POWER DESIGN 615

13.1 Low Power Design from Various Angles 616

13.2 Power Management in Embedded Linux Platform 618

13.2.1 Dynamic Power Management 618

13.2.2 Main Generic Points in the Low Power Design 621

13.2.3 d-bus Interface 627

13.2.4 Hotplug Mechanism 627

Summary 628

Exercises 628

BIBLIOGRAPHy 630

INDEX 635