现代操作系统（英文版·第4版）

　　作 者 简 介Andrew S. Tanenbaum拥有麻省理工学院的理学学士学位和加州大学伯克利分校的博士学位，如今他是阿姆斯特丹自由大学计算机科学学院的教授。他曾经是计算与图像高级学院的院长，这是一个跨大学的研究生院，主要研究高级并行、分布式以及图像系统。他同时也是荷兰皇家艺术与科学院的教授，这使得他没有变成一个刻板的人。他还赢得过享有盛名的欧洲研究理事会卓越贡献奖。
　　过去一段时间，他的主要研究方向是编译器、操作系统、网络以及分布式系统。现在他的主要研究方向是安全可靠的操作系统。他在这个研究方向已经发表了超过175篇经常被引用的期刊和会议论文。Tanenbaum教授还撰写或参与撰写了5本教材，并被翻译成20种语言，其中包括巴斯克语和泰语。这些教材被全球的大学使用，总计有163个版本（语言和版本加起来）。
　　Tanenbaum教授还编写了大量的软件，特别是MINIX，这是一个小型的UNIX。其灵感直接源于Linux以及Linux初开发的平台。如今的MINIX版本是MINIX 3，专注于成为一个非常可靠和安全的操作系统。只有当任何用户都不会遭遇操作系统崩溃的情况时，Tanenbaum教授才认为他完成了自己的工作。MINIX 3是一个欢迎所有人来完善的开放源代码项目，请访问www.minix3.org下载MINIX 3的免费版本，并试着运行它。x86和ARM版本都可用。
　　Tanenbaum教授的博士生在毕业后都有很好的前途，对于这一点教授本人非常自豪。在这方面，他如同一只爱孩子的母鸡。
　　Tanenbaum教授是ACM会士、IEEE会士，也是荷兰皇家艺术与科学院院士。他荣获了相当多的ACM、IEEE和USENIX奖项。如果你对此感到好奇，可以去他的Wikipedia主页查看。他还有两个荣誉博士学位。

　　Herbert Bos在特温特大学获得硕士学位，在剑桥大学计算机实验室获得博士学位。此后，他为Linux等操作系统的可信I/O架构做了大量工作，同时也基于MINIX 3研究系统。他现在是阿姆斯特丹自由大学计算机科学学院系统与网络安全系的教授，主要研究方向是系统安全。他与学生一起以新颖的方式检测并阻止攻击，分析并对恶意软件进行反向工程，还共同拆卸过僵尸网络（横跨几百万台计算机的恶意网络基础设施）。2011年，他因在反向工程领域的研究获得了ERC奖。他的三个学生因所写的与系统相关的论文被评为欧洲佳博士论文而获得了Roger Needham奖。

　　前　　言
　　本书的第4版与第3版有很大的不同。因为操作系统并非一成不变，所以书中随处可见许多为介绍新内容而做的细小改动。我们删除了有关多媒体操作系统的章节，主要是为了给新内容腾出空间，同时也避免此书的篇幅变得不可控。还删除了有关Windows Vista的章节，这是因为Vista的表现并没有达到微软公司的预期。同样被删除的还有Symbian章节，因为Symbian已不再被广泛使用。我们用Windows 8替换了Vista的内容，用Android替换了Symbian的内容。此外，我们还增加了关于虚拟化和云的章节。以下是有关各章节更改的概要。
　　第1章的很多地方都进行了大量的修改和更新，除增加了移动计算外，没有增加或删减主要章节。
　　第2章在删除一些过时内容的同时也增加了一些新内容。例如，增加了futex同步原语，还增加了一节介绍怎样通过读–复制–更新（Read-Copy-Update）的方式来避免锁定。
　　第3章更关注现代的硬件部件，而减少了对段和MULTICS的介绍。
　　第4章删除了有关CD-ROM的内容，因为它们已不常见。替代它们的是更加现代的解决方案（比如闪存盘）。不仅如此，我们还在讨论RAID时添加了6级RAID的内容。
　　第5章的内容做了很多改动，CRT和CD-ROM等过时设备的介绍被删掉了，同时加入了触摸屏等新技术。
　　第6章的内容基本没有改变，有关死锁的主题基本上是稳定的，并没有新的成果。
　　第7章是全新的，涵盖虚拟化和云等重要内容，并加入了一节有关VMware的内容作为案例。
　　第8章是对之前讨论的多处理机系统的更新。如今我们更加强调多核与众核系统，因为它们在过去的几年中变得愈发重要。高速缓存一致性近年来也已经成为一个重要问题，这里将会有所涉及。
　　第9章进行了大量修改和重新组织，增加了对缺陷代码、恶意软件进行探查和防御的新内容。对于空指针引用和缓冲区溢出等攻击行为提出了更详细的应对方法，并从攻击路径入手，详细论述了包含金丝雀（canary）保护、不执行（NX）位以及地址空间随机化在内的防御机制。
　　第10章有很大改变，除了对UNIX和Linux的内容进行更新外，还新增了有关Android操作系统的详细章节，该系统如今已广泛用于智能手机与平板电脑。
　　第11章在本书第3版中主要针对Windows Vista，然而这些内容已经被Windows 8尤其是Windows 8.1取代，本章介绍了有关Windows的最新内容。
　　第12章是对本书前一版本的第13章的修订。
　　第13章是一份全新的推荐阅读目录。此外，我们也对参考文献进行了更新，收录了本书第3版推出后发表的233篇新论文。
　　此外，每章末的相关研究部分完全重写了，以反映最新的操作系统研究成果。并且，所有章节都增加了新的习题。
　　网站中包含幻灯片、学习操作系统的软件工具、学生实验、模拟程序以及许多有关操作系统课程的材料。
　　有很多人参与了本书第4版的编写工作。我要介绍的第一位同时也是最重要的一位，是来自阿姆斯特丹自由大学的Herbert Bos教授，他是本书的合著者。他是一名全方位的系统专家，尤其是在安全和UNIX方面，有他的帮助真是太好了。他编写了除以下所述内容之外的绝大部分新内容。
　　我们的编辑Tracy Johnson出色地完成了她的工作，像以往一样，她将所有零碎的东西整理在一起，解决了所有的麻烦，使得这项工作能够按时完成。我们同样为拥有一位长期合作的制作编辑而感到幸运，那就是Camille Trentacoste。多亏她在诸多方面的技巧，为我们节省了很多时间。我们很高兴在许多年之后又能有她的加入。Carole Snyder在本书编写过程中出色地完成了协调工作。
　　第7章中有关VMware的内容（7.12节）是由Edouard Bugnion完成的，他来自洛桑联邦理工学院（EPFL）。Edouard是VMware公司的创始人之一，他比其他人更了解VMware，我们感谢他所提供的巨大支持。
　　佐治亚理工学院的Ada Gavrilovska 是Linux内核专家，她帮忙更新了第10章的内容。第10章中有关Android的内容是由来自Google的Android系统核心工程师Dianne Hackborn编写的。Android现在是智能手机的主要操作系统，所以我们非常感谢Dianne所提供的帮助。如今第10章篇幅较长并且十分详细，UNIX、Linux和Android的粉丝们都能从中学到很多。值得一提的是，本书中最长并且最有技术含量的章节是由两位女士所写的，而我们只是完成了其余容易的工作。
　　然而，我们并没有忽略Windows。Microsoft的Dave Probert更新了上版中第11章的内容，这一版将详细讲解Windows 8.1。Dave拥有完备的Windows知识及足够的远见，可以辨别出微软正确的地方和错误的地方。Windows的粉丝们肯定会喜欢这一章。
　　这本书由于所有这些专家所做出的贡献而变得更好，所以再一次感谢他们的宝贵帮助。
　　同样令我们感到幸运的是，我们拥有那么多阅读过原稿并提出建议的评论者，他们是Trudy Levine、Shivakant Mishra、Krishna Sivalingam以及Ken Wong。Steve Armstrong为将本书作为教材的教师制作了PPT。

ONTENTS

PREFACE xxiii
1 INTRODUCTION 1
1.1 WHAT IS AN OPERATING SYSTEM? 3
1.1.1 The Operating System as an Extended Machine 4
1.1.2 The Operating System as a Resource Manager 5
1.2 HISTORY OF OPERATING SYSTEMS 6
1.2.1 The First Generation (1945–55): Vacuum Tubes 7
1.2.2 The Second Generation (1955–65): Transistors and Batch Systems 8
1.2.3 The Third Generation (1965–1980): ICs and Multiprogramming 9
1.2.4 The Fourth Generation (1980–Present): Personal Computers 14
1.2.5 The Fifth Generation (1990–Present): Mobile Computers 19
1.3 COMPUTER HARDWARE REVIEW 20
1.3.1 Processors 21
1.3.2 Memory 24
1.3.3 Disks 27
1.3.4 I/O Devices 28
1.3.5 Buses 31
1.3.6 Booting the Computer 34
1.4 THE OPERATING SYSTEM ZOO 35
1.4.1 Mainframe Operating Systems 35
1.4.2 Server Operating Systems 35
1.4.3 Multiprocessor Operating Systems 36
1.4.4 Personal Computer Operating Systems 36
1.4.5 Handheld Computer Operating Systems 36
1.4.6 Embedded Operating Systems 36
1.4.7 Sensor-Node Operating Systems 37
1.4.8 Real-Time Operating Systems 37
1.4.9 Smart Card Operating Systems 38
1.5 OPERATING SYSTEM CONCEPTS 38
1.5.1 Processes 39
1.5.2 Address Spaces 41
1.5.3 Files 41
1.5.4 Input/Output 45
1.5.5 Protection 45
1.5.6 The Shell 45
1.5.7 Ontogeny Recapitulates Phylogeny 46
1.6 SYSTEM CALLS 50
1.6.1 System Calls for Process Management 53
1.6.2 System Calls for File Management 56
1.6.3 System Calls for Directory Management 57
1.6.4 Miscellaneous System Calls 59
1.6.5 The Windows Win32 API 60
1.7 OPERATING SYSTEM STRUCTURE 62
1.7.1 Monolithic Systems 62
1.7.2 Layered Systems 63
1.7.3 Microkernels 65
1.7.4 Client-Server Model 68
1.7.5 Virtual Machines 68
1.7.6 Exokernels 72
1.8 THE WORLD ACCORDING TO C 73
1.8.1 The C Language 73
1.8.2 Header Files 74
1.8.3 Large Programming Projects 75
1.8.4 The Model of Run Time 76
1.9 RESEARCH ON OPERATING SYSTEMS 77
1.10 OUTLINE OF THE REST OF THIS BOOK 78
1.11 METRIC UNITS 79
1.12 SUMMARY 80
2 PROCESSES AND THREADS 85
2.1 PROCESSES 85
2.1.1 The Process Model 86
2.1.2 Process Creation 88
2.1.3 Process Termination 90
2.1.4 Process Hierarchies 91
2.1.5 Process States 92
2.1.6 Implementation of Processes 94
2.1.7 Modeling Multiprogramming 95
2.2 THREADS 97
2.2.1 Thread Usage 97
2.2.2 The Classical Thread Model 102
2.2.3 POSIX Threads 106
2.2.4 Implementing Threads in User Space 108
2.2.5 Implementing Threads in the Kernel 111
2.2.6 Hybrid Implementations 112
2.2.7 Scheduler Activations 113
2.2.8 Pop-Up Threads 114
2.2.9 Making Single-Threaded Code Multithreaded 115
2.3 INTERPROCESS COMMUNICATION 119
2.3.1 Race Conditions 119
2.3.2 Critical Regions 121
2.3.3 Mutual Exclusion with Busy Waiting 121
2.3.4 Sleep and Wakeup 127
2.3.5 Semaphores 130
2.3.6 Mutexes 132
2.3.7 Monitors 137
2.3.8 Message Passing 144
2.3.9 Barriers 146
2.3.10 Avoiding Locks: Read-Copy-Update 148
2.4 SCHEDULING 148
2.4.1 Introduction to Scheduling 149
2.4.2 Scheduling in Batch Systems 156
2.4.3 Scheduling in Interactive Systems 158
2.4.4 Scheduling in Real-Time Systems 164
2.4.5 Policy Versus Mechanism 165
2.4.6 Thread Scheduling 165
2.5 CLASSICAL IPC PROBLEMS 167
2.5.1 The Dining Philosophers Problem 167
2.5.2 The Readers and Writers Problem 169
2.6 RESEARCH ON PROCESSES AND THREADS 172
2.7 SUMMARY 173
3 MEMORY MANAGEMENT 181
3.1 NO MEMORY ABSTRACTION 182
3.2 A MEMORY ABSTRACTION: ADDRESS SPACES 185
3.2.1 The Notion of an Address Space 185
3.2.2 Swapping 187
3.2.3 Managing Free Memory 190
3.3 VIRTUAL MEMORY 194
3.3.1 Paging 195
3.3.2 Page Tables 198
3.3.3 Speeding Up Paging 201
3.3.4 Page Tables for Large Memories 205
3.4 PAGE REPLACEMENT ALGORITHMS 209
3.4.1 The Optimal Page Replacement Algorithm 209
3.4.2 The Not Recently Used Page Replacement Algorithm 210
3.4.3 The First-In, First-Out (FIFO) Page Replacement Algorithm 211
3.4.4 The Second-Chance Page Replacement Algorithm 211
3.4.5 The Clock Page Replacement Algor