OperatingSystems:DesignandImplementation,2ndEdition资源-CSDN文库

4星 · 超过85%的资源需积分: 10 72 浏览量 2008-06-29 22:33:38 上传评论 4 收藏 2.19MB PDF 举报

资源推荐

资源详情

资源评论

Operating Systems: Design and Implementation

June 29, 2008

Contents

1 INTRODUCTION

√

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 . . . . . . . . . . . . . . . . . . . . . . . 4

1.2.1 The First Generation (1945—1955): Vacuum Tubes and Plugboards 5

1.2.2 The Second Generation (1955—1965): Transistors and Batch Sys-

tems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2.3 The Third Generation (1965—1980): ICs and Multiprogramming 6

1.2.4 The Fourth Generation (1980—Present): Personal Computers . . 10

1.2.5 History of MINIX . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.3 Operating System Concepts . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.3.1 Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.3.2 Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.3.3 The Shell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

1.4 System Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

1.4.1 System Calls for Process Management . . . . . . . . . . . . . . . 20

1.4.2 System Calls for Signaling . . . . . . . . . . . . . . . . . . . . . 22

1.4.3 System Calls for File Management . . . . . . . . . . . . . . . . . 24

1.4.4 System Calls for Directory Management . . . . . . . . . . . . . . 28

1.4.5 System Calls for Protection . . . . . . . . . . . . . . . . . . . . 30

1.4.6 System Calls for Time Management . . . . . . . . . . . . . . . . 31

1.5 Operating System Structure . . . . . . . . . . . . . . . . . . . . . . . . . 31

1.5.1 Monolithic Systems . . . . . . . . . . . . . . . . . . . . . . . . 31

1.5.2 Layered Systems . . . . . . . . . . . . . . . . . . . . . . . . . . 32

1.5.3 Virtual Machines . . . . . . . . . . . . . . . . . . . . . . . . . . 34

1.5.4 Client-Server Model . . . . . . . . . . . . . . . . . . . . . . . . 35

1.6 Outline Of The Rest Of This Book . . . . . . . . . . . . . . . . . . . . . 37

1.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

2 PROCESSES

√

2.1 INTRODUCTION TO PROCESSES . . . . . . . . . . . . . . . . . . . . 39

2.1.1 The Process Model . . . . . . . . . . . . . . . . . . . . . . . . . 39

2.1.2 Implementation of Processes . . . . . . . . . . . . . . . . . . . . 43

2.1.3 Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

2.2 INTERPROCESS COMMUNICATION . . . . . . . . . . . . . . . . . . 47

2.2.1 Race Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . 47

2.2.2 Critical Sections . . . . . . . . . . . . . . . . . . . . . . . . . . 48

2.2.3 Mutual Exclusion with Busy Waiting . . . . . . . . . . . . . . . 49

iii

iv CONTENTS

2.2.4 Sleep and Wakeup . . . . . . . . . . . . . . . . . . . . . . . . . 52

2.2.5 Semaphores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

2.2.6 Monitors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

2.2.7 Message Passing . . . . . . . . . . . . . . . . . . . . . . . . . . 60

2.3 CLASSICAL IPC PROBLEMS . . . . . . . . . . . . . . . . . . . . . . 62

2.3.1 The Dining Philosophers Problem . . . . . . . . . . . . . . . . . 63

2.3.2 The Readers and Writers Problem . . . . . . . . . . . . . . . . . 64

2.3.3 The Sleeping Barber Problem . . . . . . . . . . . . . . . . . . . 67

2.4 PROCESS SCHEDULING . . . . . . . . . . . . . . . . . . . . . . . . . 68

2.4.1 Round Robin Scheduling . . . . . . . . . . . . . . . . . . . . . . 70

2.4.2 Priority Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . 71

2.4.3 Multiple Queues . . . . . . . . . . . . . . . . . . . . . . . . . . 72

2.4.4 Shortest Job First . . . . . . . . . . . . . . . . . . . . . . . . . . 73

2.4.5 Guaranteed Scheduling . . . . . . . . . . . . . . . . . . . . . . . 74

2.4.6 Lottery Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . 74

2.4.7 Real-Time Scheduling . . . . . . . . . . . . . . . . . . . . . . . 75

2.4.8 Two-level Scheduling . . . . . . . . . . . . . . . . . . . . . . . . 76

2.4.9 Policy versus Mechanism . . . . . . . . . . . . . . . . . . . . . . 77

2.5 OVERVIEW OF PROCESSES IN MINIX . . . . . . . . . . . . . . . . . 78

2.5.1 The Internal Structure of MINIX . . . . . . . . . . . . . . . . . . 78

2.5.2 Process Management in MINIX . . . . . . . . . . . . . . . . . . 80

2.5.3 Interprocess Communication in MINIX . . . . . . . . . . . . . . 81

2.5.4 Process Scheduling in MINIX . . . . . . . . . . . . . . . . . . . 81

2.6 IMPLEMENTATION OF PROCESSES IN MINIX . . . . . . . . . . . . 82

2.6.1 Organization of the MINIX Source Code . . . . . . . . . . . . . 82

2.6.2 The Common Header Files . . . . . . . . . . . . . . . . . . . . . 85

2.6.3 The MINIX Header Files . . . . . . . . . . . . . . . . . . . . . . 89

2.6.4 Process Data Structures and Header Files . . . . . . . . . . . . . 94

2.6.5 Bootstrapping MINIX . . . . . . . . . . . . . . . . . . . . . . . 100

2.6.6 System Initialization . . . . . . . . . . . . . . . . . . . . . . . . 102

2.6.7 Interrupt Handling in MINIX . . . . . . . . . . . . . . . . . . . . 106

2.6.8 Interprocess Communication in MINIX . . . . . . . . . . . . . . 114

2.6.9 Scheduling in MINIX . . . . . . . . . . . . . . . . . . . . . . . 116

2.6.10 Hardware-Dependent Kernel Support . . . . . . . . . . . . . . . 118

2.6.11 Utilities and the Kernel Library . . . . . . . . . . . . . . . . . . 120

2.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

3 INPUT/OUTPUT 125

3.1 Principles of I/O Hardware

√

. . . . . . . . . . . . . . . . . . . . . . . . 125

3.1.1 I/O Devices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

3.1.2 Device Controllers . . . . . . . . . . . . . . . . . . . . . . . . . 126

3.1.3 Direct Memory Access (DMA) . . . . . . . . . . . . . . . . . . 128

3.2 Principles of I/O Software

√

. . . . . . . . . . . . . . . . . . . . . . . . 130

3.2.1 Goals of the I/O Software . . . . . . . . . . . . . . . . . . . . . 130

3.2.2 Interrupt Handlers . . . . . . . . . . . . . . . . . . . . . . . . . 131

3.2.3 Device Drivers . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

3.2.4 Device-Independent I/O Software . . . . . . . . . . . . . . . . . 132

3.2.5 User-Space I/O Software . . . . . . . . . . . . . . . . . . . . . . 134

3.3 Deadlocks

√

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

CONTENTS v

3.3.1 Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136

3.3.2 Principles of Deadlock . . . . . . . . . . . . . . . . . . . . . . . 136

3.3.3 The Ostrich Algorithm . . . . . . . . . . . . . . . . . . . . . . . 140

3.3.4 Detection and Recovery . . . . . . . . . . . . . . . . . . . . . . 140

3.3.5 Deadlock Prevention . . . . . . . . . . . . . . . . . . . . . . . . 141

3.3.6 Deadlock Avoidance . . . . . . . . . . . . . . . . . . . . . . . . 142

3.4 Overview of I/O in MINIX . . . . . . . . . . . . . . . . . . . . . . . . . 146

3.4.1 Interrupt Handlers in MINIX . . . . . . . . . . . . . . . . . . . . 146

3.4.2 Device Drivers in MINIX . . . . . . . . . . . . . . . . . . . . . 146

3.4.3 Device-Independent I/O Software in MINIX . . . . . . . . . . . 146

3.4.4 User-level I/O Software in MINIX . . . . . . . . . . . . . . . . . 146

3.4.5 Deadlock Handling in MINIX . . . . . . . . . . . . . . . . . . . 146

3.5 Block Devices in MINIX . . . . . . . . . . . . . . . . . . . . . . . . . . 146

3.5.1 Overview of Block Device Drivers in MINIX . . . . . . . . . . . 147

3.5.2 Common Block Device Driver Software

√

. . . . . . . . . . . . 149

3.5.3 The Driver Library . . . . . . . . . . . . . . . . . . . . . . . . . 152

3.6 Ram Disks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153

3.6.1 RAM Disk Hardware and Software

√

. . . . . . . . . . . . . . . 154

3.6.2 Overview of the RAM Disk Driver in MINIX . . . . . . . . . . . 155

3.6.3 Implementation of the RAM Disk Driver in MINIX . . . . . . . . 155

3.7 Disks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155

3.7.1 Disk Hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . 155

3.7.2 Disk Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155

3.7.3 Overview of the Hard Disk Driver in MINIX . . . . . . . . . . . 155

3.7.4 Implementation of the Hard Disk Driver in MINIX . . . . . . . . 158

3.7.5 Floppy Disk Handling . . . . . . . . . . . . . . . . . . . . . . . 160

3.8 Clocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160

3.8.1 Clock Hardware . . . . . . . . . . . . . . . . . . . . . . . . . . 160

3.8.2 Clock Software . . . . . . . . . . . . . . . . . . . . . . . . . . . 160

3.8.3 Overview of the Clock Driver in MINIX . . . . . . . . . . . . . . 160

3.8.4 Implementation of the Clock Driver in MINIX . . . . . . . . . . 160

3.9 Terminals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160

3.9.1 Terminal Hardware . . . . . . . . . . . . . . . . . . . . . . . . . 160

3.9.2 Terminal Software . . . . . . . . . . . . . . . . . . . . . . . . . 164

3.9.3 Overview of the Terminal Driver in MINIX . . . . . . . . . . . . 164

3.9.4 Implementation of the Device-Independent Terminal Driver . . . 164

3.9.5 Implementation of the Keyboard Driver . . . . . . . . . . . . . . 164

3.9.6 Implementation of the Display Driver . . . . . . . . . . . . . . . 164

3.10 The System Task in MINIX . . . . . . . . . . . . . . . . . . . . . . . . . 164

3.11 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164

4 MEMORY MANAGEMENT 165

4.1 Basic Memory Management . . . . . . . . . . . . . . . . . . . . . . . . 165

4.1.1 Monoprogramming without Swapping or Paging . . . . . . . . . 166

4.1.2 Multiprogramming wiith Fixed Partitions . . . . . . . . . . . . . 166

4.2 Swapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168

4.2.1 Memory Management with Bit Maps . . . . . . . . . . . . . . . 170

4.2.2 Memory Management with Linked Lists . . . . . . . . . . . . . . 171

4.3 Virtual Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173

剩余249页未读，继续阅读

评论收藏

内容反馈

riky66

2013-11-03

下载的文档可以打开，内容很棒

jamestownson

粉丝: 1
资源: 8

Operating Systems: Design and Implementation, 2nd Edition

最新资源

Operating Systems: Design and Implementation, 2nd Edition

Operating_Systems_Internals_and_Design_Principles_9th_Edition

Operating Systems Internals and Design Principles.pdf

操作系统原理经典书籍（英文原版）经典中的经典啊！！！

Operating Systems Design and Implementation, 3rd Edition chm

the_minix_book_operating-systems-design-implementation-3rd-edition(书 及 其课后习题答案)

Operating Systems Design and Implement

Operating Systems Design and Implementation Chinese-2Edition

The Design and Implementation of the FreeBSD Operating System (2nd Edition)

Moden Operating Systems 2nd Edition

Prentice.Hall.Operating.Systems.Design.and.Implementation

OPERATING SYSTEMS:DESIGN AND IMPLEMENTATION 操作系统设计与实现第二版

Operating Systems Design and Implementation(3rd Edition).rar

Operating Systems Design and Implementation by Tanenbaum Third Edition

Operating Systems Principles and Practice(2nd)

Operating Systems Design and Implementation, Third Edition

Operating Systems Design and Implementation 3rd Edition

Operating Systems Design and Implementation(3rd Edition)

《Operating Systems:Internals and Design Principles,Fifth Edition》Slides

Operating Systems Design and Implementation 3e

Operation System Design and Implementation,Third Edition（PDF版）

Operating Systems Internals and Design Principles, 9th Edition

Operating Systems：Three Easy Pieces PDF完整版

Operating Systems Design & Implementation 3rd Edition

Operating Systems Design and Implementation, Third Edition.part1

Operating Systems Design and Implementation, Third Edition.Part2

UTF-8_Operating-Systems-Design-and-Implementation,-3e.mobi

Operating Systems Design and Implementation - Andrew S. Tanenbaum

最新资源

the_minix_book_operating-systems-design-implementation-3rd-edition(书及其课后习题答案)