編輯推薦
在本書中作者深入討論瞭許多主題,包括:進程、綫程、存儲管理、文件係統、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): 持續強調分析算法的時間復雜度,並著重於設計和理解多項式時間內的解決方案。 本書的特點與價值 《算法導論》(第三版)的獨特價值在於其嚴謹的數學分析、清晰的僞代碼描述、豐富的圖解以及海量的練習題。 嚴謹的數學分析: 每一種算法都經過詳細的數學分析,包括時間復雜度和空間復雜度分析,以及必要時的正確性證明。這使得讀者不僅能理解“怎麼做”,更能理解“為什麼這麼做”以及“為什麼有效”。 清晰的僞代碼: 本書提供的僞代碼清晰易懂,獨立於任何具體的編程語言,便於讀者將其轉化為自己熟悉的語言實現。 豐富的圖解: 大量精心設計的圖例和錶格,直觀地展示瞭算法的執行過程和數據結構的演變,極大地幫助瞭讀者的理解。 海量練習題: 書末附帶的練習題涵蓋瞭從簡單概念檢驗到復雜問題設計的各個層次,是鞏固知識、提升能力的絕佳途徑。 廣泛的適用性: 無論是計算機科學專業的本科生、研究生,還是從事軟件開發、數據科學、人工智能等領域的專業人士,都能從本書中獲益匪淺。它為解決各種計算難題提供瞭堅實的理論基礎和實用的技術。 總而言之,《算法導論》(第三版)是一部包羅萬象的算法百科全書,它以其深度、廣度和權威性,深刻地影響著一代又一代的計算機科學工作者,是構建紮實算法功底的必讀之作。