编辑推荐
在本书中作者深入讨论了许多主题,包括:进程、线程、存储管理、文件系统、I/O、死锁、接口设计、多媒体、性能权衡,以及有关操作系统设计的新趋势。书中不仅涵盖了现代操作系统的原理和实践,而且特别关注了Linux操作系统、Windows Vista操作系统、嵌入式操作系统、实时操作系统以及多媒体操作系统。 本书适合从事相关研究工作的人员参考阅读。
内容简介
Tanenbaum教授作为三个操作系统的设计师或联合设计师,具有长期设计开发操作系统的经验,从而把其对理论的深入理解和具体实践融入书中,使本书成为操作系统领域的经典之作。
在本书第3版中,作者深入讨论了许多主题,包括:进程、线程、存储管理、文件系统、I/O、死锁、接口设计、多媒体、性能权衡,以及有关操作系统设计的最新趋势。书中不仅涵盖了现代操作系统的原理和实践,而且特别关注了Linux操作系统、Windows Vista操作系统、嵌入式操作系统、实时操作系统以及多媒体操作系统。
作者简介
Andrew S.Tenenbeum,拥有美国麻省理工学院的理学学士学位和加州大学伯克利分校的哲学博士学位,目前是荷兰阿姆斯特丹Vrije大学的计算机科学系教授。多年来,他在编译技术,操作系统,网络及局域分布式系统方面进行了大量的研究工作。目前,他专注于系统和安全方面的高级研究。他已经发表了近150篇论文。并在十几个国家做了有关操作系统的学术报告。Tanenbaum是ACM会员,IEEE资深会员,荷兰皇家艺术和科学学院院士,并由于。对计算领域,特别是计算机组织,网络和操作系统方面的教育所做的贡献。而获得2007年度IEEE Jarnes H Mulligan,JL教育奖。他还入选了《世界名人录》。
内页插图
目录
PREFACE
1 INTRODUCTION1
1.1 WHAT IS AN OPERATING SYSTeM?3
1.1.1 The Operating System as all Extended Machine 4
1.1.2 The Operating System as a Resource Manager 6
1.2 HISTORY OF OPERATING SYSTEMS 7
1.2.1 The First Generation(1945-55)Vacuum Tubes 7
1.2.2 The Second Generation(1955-65)Transistors and Bacch Systerms 8
1.2.3 The Third Generation(1965—1980)ICs and Multiprogramming 10
1.2 4 The Fourth Generation(1980-Present)Person Computers 15
1.3 COMPUTER HARDWARE REVIEW 19
l.3.1 Processors 19
1.3.2 Memory 23
1.3.3 Disks 26
1.3.4 Tapes 27
1.3.5 I/ODevices 27
1.3.6 Buses 30
1 3.7 Booting the Computer 33
1.4 THE OPERATING SYSTEM ZOO 33
1.4.1 Mainframe Operating Systems 34
1.4.2 Server Operating Systems 34
1.4.3 Multiprocessor Operating Systems 34
1.4.4 Personal Computer Operating Systems 35
1.4.5 Handheld Computer Operating Systems 35
1.4.6 Embedded Operating Systems. 35
1.4.7 Sensor Node Operating Systems 36
1.4.8 Real-Time Operating Systems 36
1.4.9 Smart Card Operating Systems 37
1.5 OPERATING SYSTEM CONCEPTS 37
1.5.1 Processes 38
1.5.2 Address Spaces 40
1.5.3 Files 40
1.5.4 Input/Output 43
1.5.5 Protection 44
1.5.6 The Shell 44
1.5.7 0ntogeny Recapitulates Phylogeny 46
1.6 SYSTEM CALLS 49
1.6.1 System Calls for Process Management 52
1.6.2 System Calls for File Management 56
1.6.3 System Calls for Directory Management 57
1.6.4 Miscellaneous System Calls 58
1.6.5 The Windows Win32 API 59
1.7 OPERATING SYSTEM STRUCTURE 62
1.7.1 Monolithic Systems 62
1.7.2 Layered Systems 63
1.7.3 Microkernels 64
1.7.4 Client-Server Model 67
1.7.5 Virtual Machines 67
1.7.6 Exokemels 71
1.8 THE WORLD ACCORDING TO C 72
1.8.1 The C Language 72
1.8.2 Header Files 73
1.8.3 Large Programming Projects 74
1.8.4 The Model of Run Time 75
1.9 RESEARCH ON OPERATING SYSTEMS 76
1.10 OUTLINE OF THE REST OF THIS BOOK 77
1.11 METRICIfNITS 78
1.12 SUMMARY 79
2 PROCESSES AND THREADS
2.1 PROCESSES 83
2.1.1 The Process Model 84
2.1.2 Process Creation 86
2.1.3 Process Termination 88
2.1.4 Process Hierarchies 89
2.1.5 Process States 90
2.1.6Implementation of Processes 91
2.1.7 Modeling Multiprogramming 93
2.2 THREADS 95
2.2.1 Thread Usage 95
2.2.2 The Classical Thread Model 100
2.2.3 POSIX Threads 104
2.2.4 Implementing Threads in User Space 106
2.2.5 Implementing Threads in the Kernel 109
2.2.6 Hybrid Implementations 110
2.2.7 Scheduler Activations 111
2.2.8 Pop-Up Threads 112
2.2.9 Making Single-Threaded Code Multithreaded 114
2.3 INTERPROCESS COMMUNICATION 117
2.3.1 Race Conditions 117
2.3.2 Critical Regions 119
2.3.3 Mutual Exclusion with Busy Waiting 120
2.3.4 Sleep and Wakeup 125
2.3.5 Semaphores 128
2.3.6 Mutexes 130
2.3.7 Monitors 134
2.3.8 Message Passing 140
2.3.9 Barriers 144
2.4 SCHEDULING 145
2.4.1 Introduction to Scheduling 145
2.4.2 Scheduling in Batch Systems 152
2.4.3 Scheduling in Interactive Systems 154
2.4.4 Scheduling in Real-Time Systems 160
2.4.5 Policy versus Mechanism 161
2.4.6 Thread Scheduling 162
2.5 CLASSICAL IPC PROBLEMS 163
2.5.1 The Dining Philosophers Problem 164
2.5.2 The Readers and Writers Problem 167
2.6 RESEARCH ON PROCESSES AND THREADS 168
2.7 SUMMARY 169
3 MEMORY MANAGEMETNT
4 FILE SYSTEMS
5 INPUT/OUTPUT
6 DEADLOCKS
7 MULTIMEDIA OPERATING SYSTEMS
8 MULTIPLE PROCESSOR SYSTEMS
9 SECURITY
10 CASE STUDY 1:LINUX
11 CASE STUDY 2:WINDOWS VISTA
12 CASE STUDY 3:SYMBIAN OS
13 OPERATING SYSYTEM DESIGN
14 READING LIST AND BIBLIOGRAPHY
INDEX
精彩书摘
The library procedure, possibly written in assembly language, typically putsthe system call number in a place where the operating system expects it, such as aregister (step 5). Then it executes a TRAP instruction to switch from user mode tokemel mode and start execution at a fixed address within the kernel (step 6). TheTRAP instruction is actually fairly similar to the procedure call instruction in thesense that the instruction following it is taken from a distant location and the return address is saved on the stack for use later.
Nevertheless, the TRAP instruction also differs from the procedure call instruction in two fundamental ways. First, as a side effect, it switches into kernelmode. The procedure call instruction does not change the mode. Second, ratherthan giving a relative or absolute address where the procedure is located, the TRAPinstmction cannot jump to an arbitrary address. Depending on the architecture, iteither jumps to a single fixed location or there is an 8 bit field in the instruction giving the index into a table in memory containing jump addresses, or equivalent.
前言/序言
文艺复兴以降,源远流长的科学精神和逐步形成的学术规范,使西方国家在自然科学的各个领域取得了垄断性的优势-也正是这样的传统,使美国在信息技术发展的六十多年间名家辈出、独领风骚。在商业化的进程中,美国的产业界与教育界越来越紧密地结合,计算机学科中的许多泰山北斗同时身处科研和教学的最前线,由此而产生的经典科学著作,不仅擘划了研究的范畴,还揭示了学术的源变,既遵循学术规范,又自有学者个性,其价值并不会因年月的流逝而减退。近年,在全球信息化大潮的推动下,我国的计算机产业发展迅猛,对专业人才的需求日益迫切。这对计算机教育界和出版界都既是机遇,也是挑战;而专业教材的建设在教育战略上显得举足轻重。在我国信息技术发展时间较短的现状下,美国等发达国家在其计算机科学发展的几十年间积淀和发展的经典教材仍有许多值得借鉴之处。因此,引进一批国外优秀计算机教材将对我国计算机教育事业的发展起到积极的推动作用,也是与世界接轨、建设真正的世界一流大学的必由之路。
《算法导论》(第三版) 内容简介 《算法导论》(第三版)是一部权威的、内容翔实的计算机算法经典著作,旨在为读者提供一个全面且深入的算法世界之旅。本书由麻省理工学院计算机科学与人工智能实验室的三位杰出教授——Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest 以及 Clifford Stein 联合撰写,历经多次修订,已成为全球计算机科学教育领域不可或缺的教材,同时也是算法研究者和实践者的必备参考书。 本书的结构设计严谨,从基础概念入手,循序渐进地涵盖了广泛的算法主题,涵盖了从经典算法设计技术到现代高级算法研究的最新进展。其核心目标是帮助读者掌握设计、分析和实现高效算法所需的工具和思维方式,理解算法的计算复杂度,并能在实际问题中选择和应用最适合的算法。 核心算法思想与设计技术 全书的基石在于对算法分析方法的深入阐述。本书详细介绍了渐进符号(大O、大Omega、大Theta)的运用,以及如何通过主定理(Master Theorem)等工具来分析递归算法的时间复杂度。这为理解算法的效率提供了坚实的基础。 在算法设计技术方面,本书系统地介绍了以下几种核心方法: 分治法(Divide and Conquer): 从经典的归并排序(Merge Sort)和快速排序(Quick Sort)出发,深入剖析了如何将一个大问题分解为若干个规模更小的子问题,然后递归地解决这些子问题,最后将子问题的解合并起来得到原问题的解。本书还探讨了 Strassen 矩阵乘法等更复杂的应用。 动态规划(Dynamic Programming): 这是一个解决重叠子问题和最优子结构问题的强大技术。本书通过诸如背包问题(Knapsack Problem)、最长公共子序列(Longest Common Subsequence)和矩阵链乘法(Matrix-Chain Multiplication)等经典案例,清晰地展示了如何通过构建递推关系,并利用备忘录(memoization)或自底向上(bottom-up)的表格填充方式来避免重复计算,从而获得最优解。 贪心算法(Greedy Algorithms): 贪心算法在每一步都做出局部最优的选择,以期达到全局最优。本书通过活动选择问题(Activity Selection Problem)、霍夫曼编码(Huffman Coding)以及最小生成树(Minimum Spanning Tree)问题(如 Kruskal 算法和 Prim 算法)来阐释贪心策略的原理和适用范围,并讨论了证明贪心算法正确性的方法。 网络流(Network Flow): 本书对网络流算法进行了深入的探讨,包括最大流(Maximum Flow)和最小割(Minimum Cut)等概念。通过 Ford-Fulkerson 方法及其改进算法(如 Edmonds-Karp 算法),以及 Dinic 算法,读者可以理解如何利用网络流解决诸如二分图匹配、多源汇流等一系列组合优化问题。 计算几何(Computational Geometry): 针对处理几何对象的问题,本书介绍了一些基本的计算几何算法,例如凸包(Convex Hull)的计算(如 Graham 扫描法和分治法)以及点定位(Point Location)等。 重要数据结构与算法 除了算法设计技术,本书还详细介绍了构建高效算法所必需的关键数据结构和相应算法: 链表、栈、队列: 这些基本的数据结构是构建更复杂算法的基础,本书对其操作和应用进行了清晰的说明。 堆(Heaps): 包括最大堆和最小堆,以及二叉堆和二项堆。堆在排序、优先队列以及图算法中扮演着至关重要的角色。 散列表(Hash Tables): 探讨了散列表的原理、冲突解决方法(如链地址法和开放地址法)以及分析其平均和最坏情况下的性能。 树(Trees): 二叉查找树(Binary Search Trees): 涵盖了平衡二叉查找树的概念,如AVL树和红黑树(Red-Black Trees),并详细介绍了它们的插入、删除和搜索操作,以及旋转等平衡机制,确保了对数时间复杂度的查找。 B 树(B-Trees): 特别适用于磁盘存储,能够高效地处理大量数据。 堆(Heaps): 已经作为设计技术中的一部分提及,但在数据结构部分也会再次强调其结构和操作。 图算法(Graph Algorithms): 图是描述实体间关系的重要模型,本书对其算法进行了全面的覆盖: 图的表示: 邻接矩阵和邻接表。 图的遍历: 广度优先搜索(Breadth-First Search, BFS)和深度优先搜索(Depth-First Search, DFS),以及它们在查找连通分量、拓扑排序等问题中的应用。 最短路径算法: Dijkstra 算法(用于单源非负权最短路径)、Bellman-Ford 算法(用于单源可含负权最短路径,并能检测负权环)以及 Floyd-Warshall 算法(用于所有顶点对最短路径)。 最小生成树(Minimum Spanning Tree, MST): Kruskal 算法和 Prim 算法。 传递闭包(Transitive Closure): 强连通分量(Strongly Connected Components): 字符串匹配(String Matching): 介绍了朴素字符串匹配算法,以及更高效的 Knuth-Morris-Pratt (KMP) 算法和 Rabin-Karp 算法。 线性规划(Linear Programming): 提供了线性规划的初步介绍,包括单纯形法(Simplex Method)的基本思想。 计算理论与高级主题 除了基础算法,本书也触及了计算理论的核心概念,为理解算法的计算边界提供了视角: 计算模型: 简单介绍图灵机等计算模型。 可计算性(Computability): 讨论了不可解问题(Unsolvable Problems)的存在。 计算复杂度类(Complexity Classes): 引入了 P 类、NP 类(Non-deterministic Polynomial time)等概念,并深入探讨了 NP-完全性(NP-Completeness)问题,包括识别 NP-完全问题的方法以及多项式时间规约(Polynomial-time Reduction)的概念。本书通过 SAT 问题、旅行商问题(Traveling Salesperson Problem, TSP)等经典 NP-完全问题,展示了 NP-完全性的概念及其深远影响。 近似算法(Approximation Algorithms): 针对 NP-难问题,本书也介绍了一些近似算法的设计思想,旨在找到接近最优解的可行解。 随机算法(Randomized Algorithms): 探讨了利用随机性来设计和分析算法的优势,如 Monte Carlo 算法和 Las Vegas 算法。 多项式时间算法(Polynomial-Time Algorithms): 持续强调分析算法的时间复杂度,并着重于设计和理解多项式时间内的解决方案。 本书的特点与价值 《算法导论》(第三版)的独特价值在于其严谨的数学分析、清晰的伪代码描述、丰富的图解以及海量的练习题。 严谨的数学分析: 每一种算法都经过详细的数学分析,包括时间复杂度和空间复杂度分析,以及必要时的正确性证明。这使得读者不仅能理解“怎么做”,更能理解“为什么这么做”以及“为什么有效”。 清晰的伪代码: 本书提供的伪代码清晰易懂,独立于任何具体的编程语言,便于读者将其转化为自己熟悉的语言实现。 丰富的图解: 大量精心设计的图例和表格,直观地展示了算法的执行过程和数据结构的演变,极大地帮助了读者的理解。 海量练习题: 书末附带的练习题涵盖了从简单概念检验到复杂问题设计的各个层次,是巩固知识、提升能力的绝佳途径。 广泛的适用性: 无论是计算机科学专业的本科生、研究生,还是从事软件开发、数据科学、人工智能等领域的专业人士,都能从本书中获益匪浅。它为解决各种计算难题提供了坚实的理论基础和实用的技术。 总而言之,《算法导论》(第三版)是一部包罗万象的算法百科全书,它以其深度、广度和权威性,深刻地影响着一代又一代的计算机科学工作者,是构建扎实算法功底的必读之作。