第 1章 關(guān)于本書的對(duì)話 1 第　2章 操作系統(tǒng)介紹　3 2.1　虛擬化CPU　4 2.2　虛擬化內(nèi)存　6 2.3　并發(fā)　7 2.4　持久性　9 2.5　設(shè)計(jì)目標(biāo)　11 2.6　簡(jiǎn)單歷史　12 2.7　小結(jié)　15 參考資料　15 第　1部分 虛擬化 第3章　關(guān)于虛擬化的對(duì)話　18 第4章　抽象：進(jìn)程　19 4.1　抽象：進(jìn)程　20 4.2　進(jìn)程API　20 4.3　進(jìn)程創(chuàng)建：更多細(xì)節(jié)　21 4.4　進(jìn)程狀態(tài)　22 4.5　數(shù)據(jù)結(jié)構(gòu)　24 4.6　小結(jié)　25 參考資料　25 作業(yè)　26 問(wèn)題　26 第5章　插敘：進(jìn)程API　28 5.1　fork()系統(tǒng)調(diào)用　28 5.2　wait()系統(tǒng)調(diào)用　29 5.3　最后是exec()系統(tǒng)調(diào)用　30 5.4　為什么這樣設(shè)計(jì)API　32 5.5　其他API　34 5.6　小結(jié)　34 參考資料　34 作業(yè)（編碼）　35 問(wèn)題　35 第6章　機(jī)制：受限直接執(zhí)行　37 6.1　基本技巧：受限直接執(zhí)行　37 6.2　問(wèn)題1：受限制的操作　38 6.3　問(wèn)題2：在進(jìn)程之間切換　40 6.4　擔(dān)心并發(fā)嗎　44 6.5　小結(jié)　45 參考資料　45 作業(yè)（測(cè)量）　47 第7章　進(jìn)程調(diào)度：介紹　48 7.1　工作負(fù)載假設(shè)　48 7.2　調(diào)度指標(biāo)　49 7.3　先進(jìn)先出（FIFO）　49 7.4　最短任務(wù)優(yōu)先（SJF）　50 7.5　最短完成時(shí)間優(yōu)先（STCF）　51 7.6　新度量指標(biāo)：響應(yīng)時(shí)間　52 7.7　輪轉(zhuǎn)　52 7.8　結(jié)合I/O　54 7.9　無(wú)法預(yù)知　54 7.10　小結(jié)　55 參考資料　55 作業(yè)　56 問(wèn)題　56 第8章　調(diào)度：多級(jí)反饋隊(duì)列　57 8.1　MLFQ：基本規(guī)則　57 8.2　嘗試 #1：如何改變優(yōu)先級(jí)　58 8.3　嘗試 #2：提升優(yōu)先級(jí)　60 8.4　嘗試 #3：更好的計(jì)時(shí)方式　61 8.5　MLFQ調(diào)優(yōu)及其他問(wèn)題　61 8.6　MLFQ：小結(jié)　62 參考資料　63 作業(yè)　64 問(wèn)題　64 第9章　調(diào)度：比例份額　65 9.1　基本概念：彩票數(shù)表示份額　65 9.2　彩票機(jī)制　66 9.3　實(shí)現(xiàn)　67 9.4　一個(gè)例子　68 9.5　如何分配彩票　68 9.6　為什么不是確定的　69 9.7　小結(jié)　70 參考資料　70 作業(yè)　71 問(wèn)題　71 第　10章 多處理器調(diào)度（高級(jí)）　73 10.1　背景：多處理器架構(gòu)　73 10.2　別忘了同步　75 10.3　最后一個(gè)問(wèn)題：緩存親和度　76 10.4　單隊(duì)列調(diào)度　76 10.5　多隊(duì)列調(diào)度　77 10.6　Linux 多處理器調(diào)度　79 10.7　小結(jié)　79 參考資料　79 第　11章 關(guān)于CPU虛擬化的總結(jié)對(duì)話　81 第　12章 關(guān)于內(nèi)存虛擬化的對(duì)話　83 第　13章 抽象：地址空間　85 13.1　早期系統(tǒng)　85 13.2　多道程序和時(shí)分共享　85 13.3　地址空間　86 13.4　目標(biāo)　87 13.5　小結(jié)　89 參考資料　89 第　14章 插敘：內(nèi)存操作API　91 14.1　內(nèi)存類型　91 14.2　malloc()調(diào)用　92 14.3　free()調(diào)用　93 14.4　常見錯(cuò)誤　93 14.5　底層操作系統(tǒng)支持　96 14.6　其他調(diào)用　97 14.7　小結(jié)　97 參考資料　97 作業(yè)（編碼）　98 問(wèn)題　98 第　15章 機(jī)制：地址轉(zhuǎn)換　100 15.1　假設(shè)　101 15.2　一個(gè)例子　101 15.3　動(dòng)態(tài)（基于硬件）重定位　103 15.4　硬件支持：總結(jié)　105 15.5　操作系統(tǒng)的問(wèn)題　105 15.6　小結(jié)　108 參考資料　109 作業(yè)　110 問(wèn)題　110 第　16章 分段　111 16.1　分段：泛化的基址/界限　111 16.2　我們引用哪個(gè)段　113 16.3　棧怎么辦　114 16.4　支持共享　114 16.5　細(xì)粒度與粗粒度的分段　115 16.6　操作系統(tǒng)支持　115 16.7　小結(jié)　117 參考資料　117 作業(yè)　118 問(wèn)題　119 第　17章 空閑空間管理　120 17.1　假設(shè)　120 17.2　底層機(jī)制　121 17.3　基本策略　126 17.4　其他方式　128 17.5　小結(jié)　130 參考資料　130 作業(yè)　131 問(wèn)題　131 第　18章 分頁(yè)：介紹　132 18.1　一個(gè)簡(jiǎn)單例子　132 18.2　頁(yè)表存在哪里　134 18.3　列表中究竟有什么　135 18.4　分頁(yè)：也很慢　136 18.5　內(nèi)存追蹤　137 18.6　小結(jié)　139 參考資料　139 作業(yè)　140 問(wèn)題　140 第　19章 分頁(yè)：快速地址轉(zhuǎn)換（TLB）　142 19.1　TLB的基本算法　142 19.2　示例：訪問(wèn)數(shù)組　143 19.3　誰(shuí)來(lái)處理TLB未命中　145 19.4　TLB的內(nèi)容　146 19.5　上下文切換時(shí)對(duì)TLB的處理　147 19.6　TLB替換策略　149 19.7　實(shí)際系統(tǒng)的TLB表項(xiàng)　149 19.8　小結(jié)　150 參考資料　151 作業(yè)（測(cè)量）　152 問(wèn)題　153 第　20章 分頁(yè)：較小的表　154 20.1　簡(jiǎn)單的解決方案：更大的頁(yè)　154 20.2　混合方法：分頁(yè)和分段　155 20.3　多級(jí)頁(yè)表　157 20.4　反向頁(yè)表　162 20.5　將頁(yè)表交換到磁盤　163 20.6　小結(jié)　163 參考資料　163 作業(yè)　164 問(wèn)題　164 第　21章 超越物理內(nèi)存：機(jī)制　165 21.1　交換空間　165 21.2　存在位　166 21.3　頁(yè)錯(cuò)誤　167 21.4　內(nèi)存滿了怎么辦　168 21.5　頁(yè)錯(cuò)誤處理流程　168 21.6　交換何時(shí)真正發(fā)生　169 21.7　小結(jié)　170 參考資料　171 第　22章 超越物理內(nèi)存：策略　172 22.1　緩存管理　172 22.2　最優(yōu)替換策略　173 22.3　簡(jiǎn)單策略：FIFO　175 22.4　另一簡(jiǎn)單策略：隨機(jī)　176 22.5　利用歷史數(shù)據(jù)：LRU　177 22.6　工作負(fù)載示例　178 22.7　實(shí)現(xiàn)基于歷史信息的算法　180 22.8　近似LRU　181 22.9　考慮臟頁(yè)　182 22.10　其他虛擬內(nèi)存策略　182 22.11　抖動(dòng)　183 22.12　小結(jié)　183 參考資料　183 作業(yè)　185 問(wèn)題　185 第　23章 VAX/VMS虛擬內(nèi)存系統(tǒng)　186 23.1　背景　186 23.2　內(nèi)存管理硬件　186 23.3　一個(gè)真實(shí)的地址空間　187 23.4　頁(yè)替換　189 23.5　其他漂亮的虛擬內(nèi)存技巧　190 23.6　小結(jié)　191 參考資料　191 第　24章 內(nèi)存虛擬化總結(jié)對(duì)話　193 第　2部分 并發(fā) 第　25章 關(guān)于并發(fā)的對(duì)話　196 第　26章 并發(fā)：介紹　198 26.1　實(shí)例：線程創(chuàng)建　199 26.2　為什么更糟糕：共享數(shù)據(jù)　201 26.3　核心問(wèn)題：不可控的調(diào)度　203 26.4　原子性愿望　205 26.5　還有一個(gè)問(wèn)題：等待另一個(gè)
線程　206 26.6　小結(jié)：為什么操作系統(tǒng)課要研究
并發(fā)　207 參考資料　207 作業(yè)　208 問(wèn)題　208 第　27章 插敘：線程API　210 27.1　線程創(chuàng)建　210 27.2　線程完成　211 27.3　鎖　214 27.4　條件變量　215 27.5　編譯和運(yùn)行　217 27.6　小結(jié)　217 參考資料　218 第　28章 鎖　219 28.1　鎖的基本思想　219 28.2　Pthread鎖　220 28.3　實(shí)現(xiàn)一個(gè)鎖　220 28.4　評(píng)價(jià)鎖　220 28.5　控制中斷　221 28.6　測(cè)試并設(shè)置指令（原子交換）　222 28.7　實(shí)現(xiàn)可用的自旋鎖　223 28.8　評(píng)價(jià)自旋鎖　225 28.9　比較并交換　225 28.10　鏈接的加載和條件式存儲(chǔ)指令　226 28.11　獲取并增加　228 28.12　自旋過(guò)多：怎么辦　229 28.13　簡(jiǎn)單方法：讓出來(lái)吧，寶貝　229 28.14　使用隊(duì)列：休眠替代自旋　230 28.15　不同操作系統(tǒng)，不同實(shí)現(xiàn)　232 28.16　兩階段鎖　233 28.17　小結(jié)　233 參考資料　233 作業(yè)　235 問(wèn)題　235 第　29章 基于鎖的并發(fā)數(shù)據(jù)結(jié)構(gòu)　237 29.1　并發(fā)計(jì)數(shù)器　237 29.2　并發(fā)鏈表　241 29.3　并發(fā)隊(duì)列　244 29.4　并發(fā)散列表　245 29.5　小結(jié)　246 參考資料　247 第30章　條件變量　249 30.1　定義和程序　250 30.2　生產(chǎn)者/消費(fèi)者（有界緩沖區(qū)）
問(wèn)題　252 30.3　覆蓋條件　260 30.4　小結(jié)　261 參考資料　261 第31章　信號(hào)量　263 31.1　信號(hào)量的定義　263 31.2　二值信號(hào)量（鎖）　264 31.3　信號(hào)量用作條件變量　266 31.4　生產(chǎn)者/消費(fèi)者（有界緩沖區(qū)）
問(wèn)題　268 31.5　讀者—寫者鎖　271 31.6　哲學(xué)家就餐問(wèn)題　273 31.7　如何實(shí)現(xiàn)信號(hào)量　275 31.8　小結(jié)　276 參考資料　276 第32章　常見并發(fā)問(wèn)題　279 32.1　有哪些類型的缺陷　279 32.2　非死鎖缺陷　280 32.3　死鎖缺陷　282 32.4　小結(jié)　288 參考資料　289 第33章　基于事件的并發(fā)（進(jìn)階）　291 33.1　基本想法：事件循環(huán)　291 33.2　重要API：select()（或poll()）　292 33.3　使用select()　293 33.4　為何更簡(jiǎn)單？無(wú)須鎖　294 33.5　一個(gè)問(wèn)題：阻塞系統(tǒng)調(diào)用　294 33.6　解決方案：異步I/O　294 33.7　另一個(gè)問(wèn)題：狀態(tài)管理　296 33.8　什么事情仍然很難　297 33.9　小結(jié)　298 參考資料　298 第34章　并發(fā)的總結(jié)對(duì)話　300 第3部分　持久性 第35章　關(guān)于持久性的對(duì)話　302 第36章　I/O設(shè)備　303 36.1　系統(tǒng)架構(gòu)　303 36.2　標(biāo)準(zhǔn)設(shè)備　304 36.3　標(biāo)準(zhǔn)協(xié)議　304 36.4　利用中斷減少CPU開銷　305 36.5　利用DMA進(jìn)行更高效的數(shù)據(jù)
傳送　306 36.6　設(shè)備交互的方法　307 36.7　納入操作系統(tǒng)：設(shè)備驅(qū)動(dòng)程序　307 36.8　案例研究：簡(jiǎn)單的IDE磁盤驅(qū)動(dòng)
程序　309 36.9　歷史記錄　311 36.10　小結(jié)　311 參考資料　312 第37章　磁盤驅(qū)動(dòng)器　314 37.1　接口　314 37.2　基本幾何形狀　314 37.3　簡(jiǎn)單的磁盤驅(qū)動(dòng)器　315 37.4　I/O時(shí)間：用數(shù)學(xué)　318 37.5　磁盤調(diào)度　320 37.6　小結(jié)　323 參考資料　323 作業(yè)　324 問(wèn)題　324 第38章　廉價(jià)冗余磁盤陣列（RAID）　326 38.1　接口和RAID內(nèi)部　327 38.2　故障模型　327 38.3　如何評(píng)估RAID　328 38.4　RAID 0級(jí)：條帶化　328 38.5　RAID 1級(jí)：鏡像　331 38.6　RAID 4級(jí)：通過(guò)奇偶校驗(yàn)節(jié)省
空間　333 38.7　RAID 5級(jí)：旋轉(zhuǎn)奇偶校驗(yàn)　336 38.8　RAID比較：總結(jié)　337 38.9　其他有趣的RAID問(wèn)題　338 38.10　小結(jié)　338 參考資料　339 作業(yè)　340 問(wèn)題　340 第39章　插敘：文件和目錄　342 39.1　文件和目錄　342 39.2　文件系統(tǒng)接口　343 39.3　創(chuàng)建文件　343 39.4　讀寫文件　344 39.5　讀取和寫入，但不按順序　346 39.6　用fsync()立即寫入　346 39.7　文件重命名　347 39.8　獲取文件信息　348 39.9　刪除文件　349 39.10　創(chuàng)建目錄　349 39.11　讀取目錄　350 39.12　刪除目錄　351 39.13　硬鏈接　351 39.14　符號(hào)鏈接　353 39.15　創(chuàng)建并掛載文件系統(tǒng)　354 39.16　總結(jié)　355 參考資料　355 作業(yè)　356 問(wèn)題　356 第40章　文件系統(tǒng)實(shí)現(xiàn)　357 40.1　思考方式　357 40.2　整體組織　358 40.3　文件組織：inode　359 40.4　目錄組織　363 40.5　空閑空間管理　364 40.6　訪問(wèn)路徑：讀取和寫入　364 40.7　緩存和緩沖　367 40.8　小結(jié)　369 參考資料　369 作業(yè)　370 問(wèn)題　371 第41章　局部性和快速文件系統(tǒng)　372 41.1　問(wèn)題：性能不佳　372 41.2　FFS：磁盤意識(shí)是解決方案　373 41.3　組織結(jié)構(gòu)：柱面組　373 41.4　策略：如何分配文件和目錄　374 41.5　測(cè)量文件的局部性　375 41.6　大文件例外　376 41.7　關(guān)于FFS的其他幾件事　377 41.8　小結(jié)　378 參考資料　378 第42章　崩潰一致性：FSCK和日志　380 42.1　一個(gè)詳細(xì)的例子　380 42.2　解決方案＃1：文件系統(tǒng)檢查
程序　383 42.3　解決方案＃2：日志 （或預(yù)寫日志）　384 42.4　解決方案＃3：其他方法　392 42.5　小結(jié)　393 參考資料　393 第43章　日志結(jié)構(gòu)文件系統(tǒng)　395 43.1　按順序?qū)懭氪疟P　396 43.2　順序而高效地寫入　396 43.3　要緩沖多少　397 43.4　問(wèn)題：查找inode　398 43.5　通過(guò)間接解決方案：inode映射　398 43.6　檢查點(diǎn)區(qū)域　399 43.7　從磁盤讀取文件：回顧　400 43.8　目錄如何　400 43.9　一個(gè)新問(wèn)題：垃圾收集　401 43.10　確定塊的死活　402 43.11　策略問(wèn)題：要清理哪些塊，
何時(shí)清理　403 43.12　崩潰恢復(fù)和日志　403 43.13　小結(jié)　404 參考資料　404 第44章　數(shù)據(jù)完整性和保護(hù)　407 44.1　磁盤故障模式　407 44.2　處理潛在的扇區(qū)錯(cuò)誤　409 44.3　檢測(cè)訛誤：校驗(yàn)和　409 44.4　使用校驗(yàn)和　412 44.5　一個(gè)新問(wèn)題：錯(cuò)誤的寫入　412 44.6　最后一個(gè)問(wèn)題：丟失的寫入　413 44.7　擦凈　413 44.8　校驗(yàn)和的開銷　414 44.9　小結(jié)　414 參考資料　414 第45章　關(guān)于持久的總結(jié)對(duì)話　417 第46章　關(guān)于分布式的對(duì)話　418 第47章　分布式系統(tǒng)　419 47.1　通信基礎(chǔ)　420 47.2　不可靠的通信層　420 47.3　可靠的通信層　422 47.4　通信抽象　424 47.5　遠(yuǎn)程過(guò)程調(diào)用（RPC）　425 47.6　小結(jié)　428 參考資料　429 第48章　Sun的網(wǎng)絡(luò)文件系統(tǒng)（NFS）　430 48.1　基本分布式文件系統(tǒng)　430 48.2　交出NFS　431 48.3　關(guān)注點(diǎn)：簡(jiǎn)單快速的服務(wù)器崩潰
恢復(fù)　431 48.4　快速崩潰恢復(fù)的關(guān)鍵：無(wú)狀態(tài)　432 48.5　NFSv2協(xié)議　433 48.6　從協(xié)議到分布式文件系統(tǒng)　434 48.7　利用冪等操作處理服務(wù)器故障　435 48.8　提高性能：客戶端緩存　437 48.9　緩存一致性問(wèn)題　437 48.10　評(píng)估NFS的緩存一致性　439 48.11　服務(wù)器端寫緩沖的隱含意義　439 48.12　小結(jié)　440 參考資料　440 第49章　Andrew文件系統(tǒng)（AFS）　442 49.1　AFS版本1　442 49.2　版本1的問(wèn)題　443 49.3　改進(jìn)協(xié)議　444 49.4　AFS版本2　444 49.5　緩存一致性　446 49.6　崩潰恢復(fù)　447 49.7　AFSv2的擴(kuò)展性和性能　448 49.8　AFS：其他改進(jìn)　450 49.9　小結(jié)　450 參考資料　451 作業(yè)　452 問(wèn)題　452 第50章　關(guān)于分布式的總結(jié)對(duì)話　453 附錄A　關(guān)于虛擬機(jī)監(jiān)視器的對(duì)話　454 附錄B　虛擬機(jī)監(jiān)視器　455 附錄C　關(guān)于監(jiān)視器的對(duì)話　466 附錄D　關(guān)于實(shí)驗(yàn)室的對(duì)話　467 附錄E　實(shí)驗(yàn)室：指南　468 附錄F　實(shí)驗(yàn)室：系統(tǒng)項(xiàng)目　478 附錄G　實(shí)驗(yàn)室：xv6項(xiàng)目　480