前言

北大《操作系統(tǒng)原理》課堂筆記，大綱如下：

1. 操作系統(tǒng)概述
2. 操作系統(tǒng)運(yùn)行環(huán)境
3. 進(jìn)程線程模型
4. 處理器調(diào)度
5. 同步機(jī)制
6. 存儲模型
7. 文件系統(tǒng)
8. I/O系統(tǒng)
9. 死鎖

操作系統(tǒng)概述

1. 執(zhí)行程序：通過調(diào)度選中程序開始執(zhí)行，在執(zhí)行過程中，不斷陷入操作系統(tǒng)提供各種服務(wù)支持，再調(diào)度選中程序，直到完成
2. 功能：有效（充分利用CPU、內(nèi)存、磁盤等資源）、合理（公平的資源管理策略）、易用（用戶界面和編程接口）
3. 作用：管理資源（硬件、軟件）、向用戶提供服務(wù)（創(chuàng)建、執(zhí)行、IO、統(tǒng)計）、對硬件機(jī)器擴(kuò)展（屏蔽硬件細(xì)節(jié)、提供虛擬機(jī)器界面）
4. 特征：并發(fā)（處理多個同時性活動）、共享（非同時互斥共享、同時共享有限系統(tǒng)資源）、虛擬（映射為若干邏輯實體）、隨機(jī)（不可預(yù)知運(yùn)行次序）
5. 典型架構(gòu)（用戶態(tài)、內(nèi)核態(tài)）：Windows（硬件抽象、設(shè)備驅(qū)動、內(nèi)核、圖形窗口、執(zhí)行體、內(nèi)核態(tài)可調(diào)用接口、服務(wù)分發(fā)器、DLL）、Unix（硬件控制層、調(diào)度、進(jìn)程間通信、存儲管理、內(nèi)存管理、文件系統(tǒng)、設(shè)備驅(qū)動、系統(tǒng)調(diào)用接口）、Linux（進(jìn)程、調(diào)度、虛擬內(nèi)存、物理內(nèi)存管理、各種設(shè)備驅(qū)動、網(wǎng)絡(luò)模塊、陷入異常模塊、中斷處理模塊、系統(tǒng)調(diào)用接口） 、Android（Linux內(nèi)核、系統(tǒng)庫和Android運(yùn)行時系統(tǒng)、應(yīng)用程序框架、應(yīng)用程序）
6. 分類：批處理（Spooling緩存I/O到磁盤）、分時（時間片、追求響應(yīng)時間、交互式）、實時（嚴(yán)格時間、高可靠）、個人計算機(jī)（使用方便）、網(wǎng)絡(luò)（通信、資源共享）、分布式（多機(jī)協(xié)同完成一項任務(wù)）、嵌入式（特定裝置中的軟硬件系統(tǒng)）

操作系統(tǒng)運(yùn)行環(huán)境

1. CPU：運(yùn)算器、控制器、通用寄存器、控制和狀態(tài)寄存器（PC、IR、PSW）、高速緩存
2. CPU狀態(tài)：內(nèi)核態(tài)（特權(quán)指令R0）、用戶態(tài)（用戶R3）
3. 中斷／異常機(jī)制：CPU暫停當(dāng)前執(zhí)行程序，保留現(xiàn)場，硬件自動轉(zhuǎn)去處理程序，處理完后回到斷點(diǎn)，繼續(xù)被打斷的程序
4. 事件：中斷響應(yīng)外部事件，異步處理，總是返回下一條指令，如I/O、時鐘、硬件故障；異常源于內(nèi)部正在執(zhí)行的程序，同步處理，分為陷入、故障、終止，如系統(tǒng)調(diào)用、頁故障、斷點(diǎn)、權(quán)限保護(hù)、程序
5. 中斷響應(yīng)（硬件）：指令周期末掃描中斷寄存器，CPU切換到內(nèi)核態(tài)，保存現(xiàn)場（PSW+PC），通過中斷碼查中斷向量表（中斷處理程序入口+處理機(jī)狀態(tài)字），推送中斷處理程序入口到寄存器
6. 中斷處理程序（軟件）：保存相關(guān)寄存器信息，分析發(fā)生原因。執(zhí)行處理功能，恢復(fù)現(xiàn)場
7. 系統(tǒng)調(diào)用：用戶在編程時可以調(diào)用的操作系統(tǒng)功能，如進(jìn)程控制、通信、文件使用、目錄操作、設(shè)備管理、信息維護(hù)
8. 程序調(diào)用：應(yīng)用程序可以通過庫函數(shù)和API進(jìn)入系統(tǒng)調(diào)用，也可直接引發(fā)系統(tǒng)調(diào)用，系統(tǒng)調(diào)用再調(diào)用對應(yīng)內(nèi)核函數(shù)
9. 系統(tǒng)調(diào)用設(shè)計：中斷／異常機(jī)制（支持系統(tǒng)調(diào)用服務(wù)的實現(xiàn)），陷入指令（引發(fā)異常，用戶態(tài)切換到內(nèi)核態(tài)），系統(tǒng)調(diào)用號和參數(shù)（不同系統(tǒng)調(diào)用的編號），系統(tǒng)調(diào)用表（服務(wù)程序的入口地址），參數(shù)傳遞（陷入指令自帶、通用寄存器、內(nèi)存中專用堆棧區(qū)）
10. 系統(tǒng)調(diào)用過程：CPU執(zhí)行到特殊的陷入指令；中斷硬件保護(hù)現(xiàn)場，通過門描述符（段選擇符+偏移量）查系統(tǒng)調(diào)用表；轉(zhuǎn)入查到的系統(tǒng)調(diào)用總?cè)肟诔绦颍Ｗo(hù)現(xiàn)場，保存參數(shù)到內(nèi)核堆棧，通過系統(tǒng)調(diào)用號查系統(tǒng)調(diào)用表；執(zhí)行查到的系統(tǒng)調(diào)用例程；恢復(fù)現(xiàn)場，返回用戶程序

進(jìn)程線程模型

1. 并發(fā)程序：一段時間內(nèi)，單處理器上多個程序同時處于開始運(yùn)行但未結(jié)束狀態(tài)，且次序不是事先確定的
2. 進(jìn)程：程序的一次執(zhí)行，正在運(yùn)行程序的抽象、將CPU虛擬為多個，系統(tǒng)資源分配單位，每個具有獨(dú)立地址空間，操作系統(tǒng)將CPU調(diào)度給進(jìn)程
3. 進(jìn)程控制塊PCB：進(jìn)程描述（PID、用戶標(biāo)識、進(jìn)程組關(guān)系）、進(jìn)程控制（狀態(tài)、優(yōu)先級、入口地址、隊列指針）、資源和使用狀況（存儲空間、文件）、CPU現(xiàn)場（進(jìn)程不執(zhí)行時保存寄存器值、指向頁表的指針）
4. 進(jìn)程狀態(tài)：運(yùn)行（占用CPU）、就緒（CPU不空閑）、等待／阻塞（等待某事）；創(chuàng)建（信息設(shè)置完但資源有限）、終止（統(tǒng)計信息、回收資源）；掛起（分就緒掛起和阻塞掛起，回收內(nèi)存存磁盤，條件允許后可激活）
5. 進(jìn)程隊列：每類進(jìn)程狀態(tài)有一個或多個隊列，元素為PCB，進(jìn)程狀態(tài)改變就是換隊
6. 進(jìn)程控制：利用完成某種功能的不允許中斷的控制原語，轉(zhuǎn)換進(jìn)程狀態(tài)
7. Unix進(jìn)程控制操作：fork（復(fù)制調(diào)用進(jìn)程創(chuàng)建）、exec（新代碼覆蓋原地址空間創(chuàng)建）、wait（主動阻塞）、exit（撤銷，回收資源和PCB）
8. 進(jìn)程層次結(jié)構(gòu)：進(jìn)程由其他進(jìn)程創(chuàng)建，Unix進(jìn)程家族樹以init為根，Windows中各進(jìn)程的地位相同
9. 進(jìn)程地址空間：內(nèi)核地址空間、用戶地址空間（代碼段、數(shù)據(jù)段、堆、共享庫、棧）
10. 進(jìn)程映像：進(jìn)程地址空間、硬件寄存器、PCB及各種數(shù)據(jù)結(jié)構(gòu)、進(jìn)入進(jìn)程時所需的內(nèi)核棧
11. 上下文context切換：CPU硬件狀態(tài)從一個進(jìn)程換到另一個，運(yùn)行的進(jìn)程硬件狀態(tài)保存在CPU寄存器上，不運(yùn)行時保存在PCB中，之后可推送至CPU寄存器
12. 引入線程：應(yīng)用需要（如Web服務(wù)器）、減少開銷（創(chuàng)建和切換花費(fèi)時間少，通信無需內(nèi)核）、提升性能（多處理器）
13. 線程與進(jìn)程：線程是進(jìn)程中的運(yùn)行實體，CPU的調(diào)度單位，增加了多個執(zhí)行序列
14. 線程屬性：ID、狀態(tài)、上下文、棧指針；共享進(jìn)程的地址空間和其他資源；程序以單線程進(jìn)程開始，線程由線程創(chuàng)建和撤銷
15. 線程的實現(xiàn)：Unix是用戶級線程，內(nèi)核無法感知線程存在，切換較快，但同進(jìn)程的線程不能分到多CPU上，阻塞會阻塞整個進(jìn)程；Windows是內(nèi)核級線程，內(nèi)核中包含線程表，調(diào)度以線程為單位；Solaris為混合模型，線程創(chuàng)建在用戶空間，調(diào)度在內(nèi)核
16. Pthread：POSIX多線程編程接口，線程協(xié)商誰上CPU；如yield函數(shù)主動讓出CPU
17. 進(jìn)程特性：并發(fā)（任何進(jìn)程都可和其他同時推進(jìn)）、動態(tài)（生命周期中切換狀態(tài)）、獨(dú)立（資源）、交互（進(jìn)程間產(chǎn)生關(guān)系）、異步（進(jìn)程獨(dú)立不可預(yù)知的推進(jìn)）、進(jìn)程映像（程序+數(shù)據(jù)+棧+PCB）
18. 可重入程序：純代碼，執(zhí)行不改變，調(diào)用它的進(jìn)程提供數(shù)據(jù)區(qū)；大部分進(jìn)程和線程只有可重入程序才可以運(yùn)行

處理器調(diào)度

1. CPU調(diào)度：在合適的調(diào)度時機(jī)，按調(diào)度算法，調(diào)度就緒隊列中的進(jìn)程進(jìn)CPU
2. 調(diào)度時機(jī)：內(nèi)核對中斷／異常／系統(tǒng)調(diào)用處理后，就緒隊列改變引發(fā)重新調(diào)度，如進(jìn)程終止、創(chuàng)建、運(yùn)行轉(zhuǎn)入阻塞、運(yùn)行轉(zhuǎn)入就緒
3. 進(jìn)程切換：切換全局頁目錄加載新的地址空間，切換內(nèi)核棧和硬件上下文；進(jìn)程A切換到B，保存A上下文環(huán)境，更新A的PCB，A移至合適隊列，B設(shè)為運(yùn)行態(tài)，從B的PCB恢復(fù)上下文
4. 調(diào)度算法考慮：優(yōu)先級與優(yōu)先數(shù)？多級就緒隊列如何組織？是否搶占？I/O密集或CPU密集友好？時間片長度？
5. 不同系統(tǒng)的調(diào)度算法：批處理處理看重吞吐量、周轉(zhuǎn)時間、CPU利用率、平衡（先來先服務(wù)FCFS、最短作業(yè)優(yōu)先SJF、最短剩余時間優(yōu)先SRTN、最高響應(yīng)比優(yōu)先HRRN）；交互式系統(tǒng)看重響應(yīng)時間、平衡（輪轉(zhuǎn)Round-Robin、最高優(yōu)先級HPF、多級反饋隊列Feedback、類似SJF的最短進(jìn)程優(yōu)先SPN）
6. 優(yōu)先級反轉(zhuǎn)：搶占式最高優(yōu)先級調(diào)度時，高優(yōu)先級受制于低優(yōu)先級（如臨界區(qū)等待），而低優(yōu)先級被運(yùn)行時間較長的中優(yōu)先級進(jìn)程搶占，導(dǎo)致高優(yōu)先級無法上CPU
7. 多級反饋隊列：多個就緒隊列，順次優(yōu)先級遞減，時間片遞增，每個隊列內(nèi)部按時間片輪轉(zhuǎn)；新建進(jìn)程進(jìn)一級隊列，用完時間片進(jìn)下一級就緒隊列；因阻塞進(jìn)入等待隊列的進(jìn)程在等待完畢后，回到原級別的就緒隊列，但可設(shè)置時間片是否重新分配，加入隊首或隊尾
8. 系統(tǒng)調(diào)度算法：Unix動態(tài)優(yōu)先數(shù)，5.3BSD多級反饋隊列，Linux搶占式調(diào)度，Windows基于優(yōu)先級的搶占式多任務(wù)調(diào)度
9. Windows線程調(diào)度：調(diào)度單位是線程，基于動態(tài)優(yōu)先級的搶占式調(diào)度，結(jié)合時間配額的調(diào)整；引發(fā)調(diào)度的條件除線程終止、創(chuàng)建、運(yùn)行轉(zhuǎn)入阻塞、運(yùn)行轉(zhuǎn)入就緒外，還有線程優(yōu)先級改變和親和處理機(jī)集合改變
10. 線程優(yōu)先級提升：I/O完成、信號量或事件等待結(jié)束、前臺進(jìn)程的線程完成等待、窗口被喚醒、饑餓超時
11. 調(diào)度算法對比：

同步機(jī)制

1. 并發(fā)：進(jìn)程的執(zhí)行是間斷的，相對運(yùn)行速度不可預(yù)測，共享資源帶來制約性
2. 競爭條件：多個進(jìn)程讀寫共享數(shù)據(jù)時，結(jié)果取決于進(jìn)程的精確時序
3. 進(jìn)程互斥：多個進(jìn)程的臨界區(qū)代碼對臨界資源的使用需要排他性，各進(jìn)程間競爭使用這些共享資源
4. 臨界區(qū)：臨界區(qū)空則可進(jìn)入，但臨界區(qū)中至多一個進(jìn)程，臨界區(qū)外的進(jìn)程不能阻塞其他進(jìn)程進(jìn)臨界區(qū)，不能讓想進(jìn)臨界區(qū)的進(jìn)程無限等待
5. 軟件解決互斥：臨界區(qū)空閑標(biāo)志（free）、進(jìn)區(qū)的用戶（turn）、各自進(jìn)區(qū)標(biāo)志（pturn+qturn）、dekker算法（turn+pturn+qturn）、peterson（enter_region+leave_region/turn+interest[]）、
6. 硬件解決互斥：開關(guān)中斷指令（特權(quán)指令、中斷屏蔽限制CPU并發(fā)、不適合多CPU）、測試并加鎖指令（對總線加鎖）、交換指令（交換寄存器與鎖變量）
7. 忙等待：進(jìn)程在得到臨界區(qū)訪問權(quán)前，在CPU持續(xù)測試而不做別的事；多處理器中使用自旋鎖測試，讓其他CPU改鎖狀態(tài)，切換代價反而比持續(xù)測試大
8. 進(jìn)程同步：多進(jìn)程中發(fā)生的事件存在時序關(guān)系，需要協(xié)作完成任務(wù)
9. 生產(chǎn)者/消費(fèi)者問題：生產(chǎn)者寫入緩沖區(qū)，消費(fèi)者從緩沖區(qū)取數(shù)據(jù)，不能同時消費(fèi)和生產(chǎn)，緩沖區(qū)空不能消費(fèi)，緩沖區(qū)滿不能生產(chǎn)
10. 信號量：用于進(jìn)程間傳遞信息的整數(shù)值，包含隊列；操作包括初始化（非負(fù)數(shù)），原語操作P（減）V（增）；二元信號量解決互斥，多值信號量解決同步
11. PV解決互斥：劃定臨界區(qū)，初始化mutex為1，進(jìn)臨界區(qū)前執(zhí)行P申請資源，出臨界區(qū)后執(zhí)行V喚醒等待
12. PV解決生產(chǎn)者/消費(fèi)者：初始化mutex為1，empty為空位，full為0；用mutex對緩沖區(qū)進(jìn)行PV解決互斥，用empty和full進(jìn)行PV解決同步
13. PV解決讀者/寫者問題：允許多個讀者同時讀，不允許同時讀寫；針對w信號，第一個讀前P，最后一個讀完V，寫前后PV；針對讀者序列rc，也需要在修改或判斷前后用PV保護(hù)
14. Linux讀寫鎖：每個執(zhí)行實體對臨界區(qū)的訪問或讀或?qū)?，不會同時讀寫，此時可應(yīng)用讀者/寫者模型；如路由表中的讀寫鎖
15. 管程：有自己名字的特殊模塊，由關(guān)于共享資源的數(shù)據(jù)結(jié)構(gòu)和在其上的操作過程組成，進(jìn)程可調(diào)用管程的過程以操作管程中的數(shù)據(jù)結(jié)構(gòu)；編譯器復(fù)雜管程的互斥，設(shè)置條件變量及等待喚醒操作解決同步問題
16. 管程內(nèi)多進(jìn)程：若P喚醒Q，則管程中同時存在活躍狀態(tài)的P和Q兩個進(jìn)程；處理方法有Hoare（P等待Q）、Mesa（Q等待P），Hansen并發(fā)pascal（讓喚醒是管程中最后可執(zhí)行操作）
17. 管程應(yīng)用：直接構(gòu)造條件變量恰當(dāng)?shù)墓艹?，用已有的同步機(jī)制間接構(gòu)造；C++不支持管程，Java支持類似管程
18. Hoare管程：管程入口設(shè)置入口等待隊列，內(nèi)部設(shè)置緊急等待隊列放置喚醒進(jìn)程，P喚醒Q則P等待Q；wait(c)優(yōu)先喚醒緊急隊列隊首，再將進(jìn)程加入c鏈尾，signal(c)優(yōu)先喚醒c鏈?zhǔn)走M(jìn)入緊急等待隊列
19. Mesa管程：P喚醒Q則Q等待P，避免額外進(jìn)程切換開銷；signal衍化到notify，進(jìn)程調(diào)度執(zhí)行前再次檢查條件，每個條件原語關(guān)聯(lián)監(jiān)視計時器超時即就緒，再衍化到broadcast使所有該條件隊列上等待的進(jìn)程進(jìn)入就緒隊列；Mesa優(yōu)于Hoare
20. Pthread中的同步機(jī)制：互斥變量保護(hù)臨界區(qū)Pthread_mutex_[init/destroy/lock/unlock/trylock]；條件變量解決同步Pthread_cond_[init/destroy/wait/signal/broadcast]
21. 進(jìn)程間通信：消息傳遞、共享內(nèi)存、管道、用于網(wǎng)絡(luò)分布式系統(tǒng)的套接字和遠(yuǎn)程過程調(diào)用
22. 消息傳遞：send原語，陷入內(nèi)核，操作系統(tǒng)復(fù)制到消息緩沖區(qū)，并掛接消息到接受進(jìn)程的消息隊列指針；receive原語，操作系統(tǒng)將消息復(fù)制到接收進(jìn)程的地址空間
23. 共享內(nèi)存：物理內(nèi)存中建立一塊能夠共享的內(nèi)存空間，將物理內(nèi)存空間映射到兩個進(jìn)程的地址空間；利用讀者/寫者問題解決互斥
24. 管道：利用緩沖傳輸介質(zhì)內(nèi)存或文件連接兩個進(jìn)程；按字符流讀寫，先進(jìn)先出，解決互斥同步
25. Linux內(nèi)核同步機(jī)制：原子操作（不可分割）、屏障（一組線程都到達(dá)匯合點(diǎn)后再一起推進(jìn)）、自旋鎖、信號量、完成變量、互斥體等

存儲模型

1. 地址重定位：將邏輯／相對／虛擬地址，映射到物理／絕對／實地址；程序加載時用軟件靜態(tài)重定位，執(zhí)行每條指令時用內(nèi)存管理單元MMU動態(tài)重定位
2. 物理內(nèi)存管理：數(shù)據(jù)結(jié)構(gòu)（位圖、空閑+已分配區(qū)表、空閑塊鏈表）；分配算法（首次適配、下次適配、最佳適配、最差適配）
3. 伙伴系統(tǒng)：Linux底層內(nèi)存分配算法，內(nèi)存按2的整數(shù)次冪劃分，組成空閑塊鏈表，在鏈表中查找長度大于等于申請空間且不大于其一半的空閑塊，內(nèi)存回收時遞歸合并空閑伙伴
4. 基本內(nèi)存管理方案：占據(jù)內(nèi)存連續(xù)空間（單一連續(xù)區(qū)、固定分區(qū)、可變分區(qū)），分布在內(nèi)存中不連續(xù)區(qū)域（頁式、段式、段頁式）
5. 單一連續(xù)區(qū)：單一程序獨(dú)占內(nèi)存，總是被加載到同一內(nèi)存地址
6. 固定分區(qū)：將內(nèi)存分割為若干連續(xù)分區(qū)，大小可不同但必須固定不變，每個分區(qū)裝載一個進(jìn)程
7. 可變分區(qū)：根據(jù)進(jìn)程需要，動態(tài)分割出分區(qū)分配給進(jìn)程
8. 頁式：用戶地址空間劃分為大小相等的頁，內(nèi)存空間按頁大小劃分為多個頁框，分配單位是頁
9. 段式：用戶地址空間按自身邏輯劃分為若干段，內(nèi)存空間劃分為若干個長度不同的區(qū)域（可變分區(qū)），分配單位是段
10. 段頁式：用戶程序地址空間是段式，每段內(nèi)含有多頁，內(nèi)存空間是頁式，分配單位是頁
11. 緊縮技術(shù)：在內(nèi)存中移動程序，將所有小的碎片合并為較大的空閑區(qū)，不能解決頁式管理造成的內(nèi)碎片
12. 覆蓋技術(shù)：將不會同時執(zhí)行的程序段共享同一塊內(nèi)存，需要程序員顯式編程，現(xiàn)在很少用
13. 交換技術(shù)：將程序內(nèi)存中的堆棧（靜態(tài)數(shù)據(jù)一直在磁盤），在很少使用或內(nèi)存不夠時，暫時移動到磁盤上的交換區(qū)（swap／pagefile），讓外存中的程序占據(jù)其原有內(nèi)存
14. 空間增長：進(jìn)程的數(shù)據(jù)段和棧段會持續(xù)增長（堆向上，棧向下），可預(yù)留一些空間供給它們同向或反向增長
15. 虛擬存儲：進(jìn)程運(yùn)行時先將部分裝入內(nèi)存，另一部分暫留在磁盤，執(zhí)行指令或訪問數(shù)據(jù)時按需從磁盤調(diào)入內(nèi)存；虛存構(gòu)建在存儲體系上，由操作系統(tǒng)調(diào)度各存儲器的使用；虛存大小與機(jī)器位數(shù)和磁盤大小有關(guān)
16. 存儲保護(hù)：每個進(jìn)程有獨(dú)立地址空間，訪問合法地址范圍，權(quán)限合法
17. 虛擬頁式：虛擬存儲技術(shù)結(jié)合頁式存儲管理；方式有請求調(diào)頁和預(yù)先調(diào)頁
18. 頁式映射：遞歸查找多級頁表起始地址，與頁內(nèi)偏移拼接為物理地址；頁表項中有效位代表是否已存入內(nèi)存
19. 反轉(zhuǎn)頁表：以物理內(nèi)存大小建立頁表，將虛擬地址的頁號部分哈希，指向反轉(zhuǎn)頁表的某個位置，借助鏈表解決沖突
20. 內(nèi)存管理單元MMU：查頁表和頁表項的功能位，將虛擬地址轉(zhuǎn)換為物理地址
21. 塊表TLB：由cache組成，是按內(nèi)容并行查找的相聯(lián)存儲器，保存部分頁表項；MMU先查快表，沒命中再查頁表
22. 頁錯誤：地址轉(zhuǎn)換過程中硬件產(chǎn)生異常，包括缺頁、違反權(quán)限、地址指向未定義
23. 駐留集：給每個進(jìn)程分配的頁框數(shù)；可根據(jù)進(jìn)程類型和需要的固定分配，或依據(jù)缺頁率評估的動態(tài)分配
24. 置換策略：置換范圍為當(dāng)前進(jìn)程的駐留集叫局部置換，內(nèi)存中所有未鎖定頁面都為候選叫全局置換；局部、全局置換結(jié)合固定、動態(tài)分配策略，共產(chǎn)生三種方案，局部固定、全局固定、全局動態(tài)
25. 清除策略：從進(jìn)程駐留集中收回頁框；分頁守護(hù)程序，保證系統(tǒng)中總有一定數(shù)量的空頁框；頁緩沖技術(shù)，不丟棄置換頁而是加入修改頁鏈表中，定期批量寫回磁盤
26. 頁面置換算法：OPT（未來最遠(yuǎn)使用）、NRU（LRU的粗略近似）、FIFO（先進(jìn)先出）、第二次機(jī)會（第一次先放隊尾）、時鐘（在環(huán)上移動指針）、LRU（優(yōu)秀開銷大）、老化（左置右移）、工作集（保持活躍頁面的集合）
27. 影響缺頁次數(shù)：置換（磁盤調(diào)度頁面比運(yùn)行時間多產(chǎn)生顛簸），頁面大?。ㄗ顑?yōu)值為2倍的程序規(guī)模乘頁表項再開根），程序編制方法（多維數(shù)組），駐留集（平衡點(diǎn)）
28. Belady現(xiàn)象：FIFO算法，駐留集增大，缺頁率可能反而增加
29. 內(nèi)存映射文件：用系統(tǒng)調(diào)用將文件映射到虛擬地址空間，訪問文件就像訪問大數(shù)組
30. 寫時復(fù)制：父進(jìn)程創(chuàng)建子進(jìn)程后共享一塊標(biāo)記為寫時復(fù)制的虛擬空間，當(dāng)子進(jìn)程執(zhí)行自己代碼數(shù)據(jù)時，操作系統(tǒng)為其分配新的空間

文件系統(tǒng)

1. 文件：標(biāo)識為文件名，對用戶而言有完整的邏輯含義，對操作系統(tǒng)而言是信息項的序列
2. 文件系統(tǒng)：管理磁盤空間，實現(xiàn)按名存?。挚臻g到磁盤空間的轉(zhuǎn)換），共享及保護(hù)，向用戶和I/O提供接口
3. 文件分類：普通文件（包含用戶信息的ASCII或二進(jìn)制文件）、目錄文件（管理文件系統(tǒng)的系統(tǒng)文件）、特殊文件（字符／塊設(shè)備）、管道文件、套接字
4. 邏輯結(jié)構(gòu)：流式文件（字符）、記錄式文件（記錄）
5. 蔟：信息存儲、分配、傳輸?shù)莫?dú)立物理塊單元
6. 磁盤結(jié)構(gòu)：物理地址由磁頭／盤面號、磁道／柱面號、扇區(qū)號構(gòu)成；扇區(qū)包括10B標(biāo)題、512B數(shù)據(jù)、12~16B的ECC糾錯信息
7. 磁盤中文件相關(guān)數(shù)據(jù)結(jié)構(gòu)：位圖（設(shè)置0/1）、空閑塊表（起始塊號和空閑長度）、空閑塊鏈表（每個節(jié)點(diǎn)含下一個指針）、成組鏈接法（從專用塊出發(fā)，每組首個空閑塊記錄下組的空閑塊號和塊數(shù)）
8. 文件控制塊FCB：包含管理文件所需的文件屬性或元數(shù)據(jù)，包括名字、時間、地址、標(biāo)志等
9. 文件目錄：統(tǒng)一管理每個文件的元數(shù)據(jù)，完成名字到地址轉(zhuǎn)換；文件目錄以目錄文件的形式存儲在磁盤；目錄項是FCB
10. 物理結(jié)構(gòu)：順序結(jié)構(gòu)、鏈接結(jié)構(gòu)、索引結(jié)構(gòu)（存放索引表的索引塊地址放在FBC中）
11. 索引表的組織：索引表很大，需要多個物理快存儲時，可采用鏈接方式鏈接多個塊、上級索引表每個表項放置下級索引表地址的多級索引、或兩者結(jié)合的綜合模式
12. 文件卷：磁盤邏輯分區(qū)，由一個或多個蔟組成，包含2的整數(shù)次冪個扇區(qū)；格式化就是在文件卷上初始化元數(shù)據(jù)，建立文件系統(tǒng)
13. 分區(qū)內(nèi)容：引導(dǎo)區(qū)（引導(dǎo)操作系統(tǒng)所需信息，第一扇區(qū)）、卷信息（總蔟數(shù)、空閑蔟數(shù)和指針、空閑FCP數(shù)量和指針等）、目錄文件（根目錄及其他目錄文件）、用戶文件
14. Unix文件系統(tǒng)布局：引導(dǎo)區(qū)、超級數(shù)據(jù)塊（文件系統(tǒng)結(jié)構(gòu)信息）、空閑區(qū)管理（空閑表或相關(guān)結(jié)構(gòu)）、i節(jié)點(diǎn)區(qū)、根目錄區(qū)
15. Windows中FAT系統(tǒng)布局：引導(dǎo)區(qū)（文件系統(tǒng)數(shù)據(jù)記錄）、文件分配表1（蔟的分配狀態(tài)、標(biāo)注下一簇）、文件分配表2（1的鏡像）、根目錄、其他目錄和文件
16. 內(nèi)存中文件相關(guān)數(shù)據(jù)結(jié)構(gòu)：系統(tǒng)打開文件表，整個系統(tǒng)一張，包括FCB（i節(jié)點(diǎn)）信息、引用計數(shù)、修改標(biāo)記；用戶打開文件表，保存在每個進(jìn)程的PCB中，包括文件描述符、打開方式、讀寫指針、系統(tǒng)打開文件表索引
17. 目錄項分解：把FCB分為2部分，符號目錄項（文件名、文件號）和基本目錄項（除文件名外所有字段，描述文件相關(guān)信息）；Unix中FCB=目錄項+i節(jié)點(diǎn)，每個文件由目錄項、i節(jié)點(diǎn)、若干磁盤塊構(gòu)成
18. Unix文件查找/a/b/c：超級數(shù)據(jù)塊中得到根目錄文件地址，根目錄文件中得到a的i節(jié)點(diǎn)地址，a的i節(jié)點(diǎn)中得到a目錄文件地址，a目錄文件中得到b的i節(jié)點(diǎn)地址，b的i節(jié)點(diǎn)中得到b目錄文件地址，b目錄文件中得到c的i節(jié)點(diǎn)地址，c的i節(jié)點(diǎn)中得到文件物理地址
19. FAT文件系統(tǒng)：按FAT表項字節(jié)數(shù)分為FAT12、FAT16、FAT32；FAT16根目錄大小固定，不支持Unicode；目錄項都為32B，包含文件屬性和起始蔟號
20. 文件分配表FAT：可看作整數(shù)數(shù)組，每個整數(shù)代表磁盤分區(qū)的一個蔟號，記錄狀態(tài)和下一組蔟號
21. 解決長文件名：使用不固定長度的目錄項，添加長度和結(jié)束標(biāo)志；名字統(tǒng)一在堆存放，目錄項中包含指向堆內(nèi)的指針；FAT32的每個長目錄項可保存13字符，長目錄項前必須有一個普通的短目錄項
22. 文件操作：創(chuàng)建（建FCB，分配存儲空間）；打開（找目錄項，更新共享計數(shù)，獲取文件描述符）；指針定位（fd查用戶打開文件表找表項，設(shè)置讀寫指針）；讀文件（由文件描述符找FCB，轉(zhuǎn)換為物理塊，申請緩沖區(qū)，進(jìn)行I/O）；重命名（修改FCB中的名字）
23. 一致性：磁盤塊寫回內(nèi)存前出現(xiàn)故障，元數(shù)據(jù)一致性被破壞；Unix中用兩個表記錄使用中的塊和空閑塊，對比修復(fù)一致性
24. 寫入策略：同時考慮速度和一致性；通寫、延遲寫、可恢復(fù)寫（日志，如NTFS、ext3）
25. 訪問控制：訪問控制表（每個文件能被哪些用戶操作），能力表（每個用戶能操作哪些文件）；用戶（owner、group、other），操作（r、w、x、-）
26. 提高性能：目錄項分解、當(dāng)前目錄、磁盤碎片整理、塊高速緩存（一式三份存在于磁盤、內(nèi)存、緩存）、提前讀取、合理分配磁盤空間（FCB與蔟同組）、磁盤調(diào)度、信息的優(yōu)化分布（磁道排列方式）、記錄的成組與分解（若干邏輯記錄組成一塊）、RAID等
27. 磁盤調(diào)度算法：FCFS、最短尋道時間優(yōu)先、SCAN（電梯）、C-SCAN（總是從0號向內(nèi)）、N-step-SCAN（每次服務(wù)n長子隊列）、FSCAN（兩個隊列，新請求入另一個隊列）、旋轉(zhuǎn)調(diào)度（旋轉(zhuǎn)延遲）
28. RAID：獨(dú)立磁盤冗余矩陣，文件卷跨盤，用數(shù)據(jù)分條（如RAID0）并行I/O提高性能、用鏡像（如RAID1）和校驗（如RAID4）提供容錯

I/O系統(tǒng)

1. I/O管理：建立設(shè)備和內(nèi)存間的數(shù)據(jù)通道，從應(yīng)用程序或文件系統(tǒng)獲得請求，交由設(shè)備硬件響應(yīng)，過程由CPU控制
2. 設(shè)備分類：塊設(shè)備（以塊尋址）、字符設(shè)備（速率低）；獨(dú)享設(shè)備（單進(jìn)程使用，可靜態(tài)或動態(tài)分配）、共享設(shè)備（多進(jìn)程排隊分時共享）、虛設(shè)備（共享設(shè)備模擬的獨(dú)占設(shè)備，如Spooling技術(shù)）
3. 管理目標(biāo)：按照用戶請求，控制設(shè)備完成與內(nèi)存間的數(shù)據(jù)交換；建立方便、統(tǒng)一的獨(dú)立于設(shè)備的接口；提高CPU與設(shè)備、設(shè)備與設(shè)備的并行工作能力；保護(hù)數(shù)據(jù)的安全性、完整性、保密性
4. 硬件組成：機(jī)械部分是設(shè)備本身，物理裝置；電子部分是設(shè)備控制器，完成端口編址、信號處理、緩沖
5. I/O地址：獨(dú)立編址，端口與內(nèi)存地址空間完全獨(dú)立，分配給I/O地址空間很少，操作不靈活；內(nèi)存映像編址，將I/O端口看作存儲單元，與內(nèi)存空間統(tǒng)一編址，不能對控制寄存器高速緩存
6. 控制方式：可編程（輪詢，CPU忙等待）、中斷驅(qū)動（操作結(jié)束后用中斷主動通知驅(qū)動）、DMA（直接存儲器訪問，不通過CPU）
7. I/O演化：CPU控制->輪詢->中斷->DMA->單獨(dú)的處理器->擁有局部存儲器（本身已是計算機(jī)）
8. 軟件層次：用戶進(jìn)程I/O（用戶層執(zhí)行輸入輸出系統(tǒng)調(diào)用，準(zhǔn)備假脫機(jī)）、邏輯I/O（驅(qū)動程序的統(tǒng)一接口，錯誤報告，緩沖，分配和釋放設(shè)備）、設(shè)備驅(qū)動程序（設(shè)置寄存器，檢查執(zhí)行狀態(tài)）、中斷處理程序（完成后喚醒設(shè)備驅(qū)動）
9. 設(shè)備獨(dú)立性：用戶編寫程序時使用邏輯設(shè)備名，由系統(tǒng)實現(xiàn)邏輯設(shè)備到物理設(shè)備的映射；操作系統(tǒng)設(shè)計I/O軟件時，除直接與設(shè)備打交道的底層軟件外不依賴于硬件；設(shè)備分配靈活，易于實現(xiàn)I/O重定向
10. 緩沖技術(shù)：解決到達(dá)與離開速度不匹配的問題，提高CPU與I/O設(shè)備的并行性；按緩沖區(qū)位置有硬緩沖、軟緩沖，按緩沖池個數(shù)有單緩沖、雙緩沖、緩沖池
11. 緩沖區(qū)：由緩沖控制塊和緩沖數(shù)據(jù)區(qū)組成，相關(guān)數(shù)據(jù)結(jié)構(gòu)有空閑緩沖區(qū)隊列av鏈和設(shè)備緩沖隊列b鏈；開始時在av鏈，開始I/O請求時在I/O請求隊列和b鏈，完成I/O后在av鏈和b鏈
12. 設(shè)備管理數(shù)據(jù)結(jié)構(gòu)：描述設(shè)備的表格、建立同類資源的隊列、面向I/O進(jìn)程的動態(tài)數(shù)據(jù)結(jié)構(gòu)、建立I/O的隊列
13. 驅(qū)動程序：每個設(shè)備驅(qū)動程序管理一類設(shè)備，從上層接受并釋放命令，監(jiān)督執(zhí)行時可讓進(jìn)程等待也可以不等待；與操作系統(tǒng)、用于初始化的系統(tǒng)引導(dǎo)、設(shè)備都有接口
14. I/O進(jìn)程：系統(tǒng)級進(jìn)程，優(yōu)先級高；對于I/O請求，用戶通過send發(fā)送給I/O進(jìn)程，阻塞自己直到I/O完成并被喚醒，操作系統(tǒng)通過wakeup喚醒I/O進(jìn)程，完成時用戶要求的任務(wù)；對于I/O中斷，操作系統(tǒng)判斷為正常中斷則交給I/O進(jìn)程，異常則交給錯誤處理程序
15. 提高性能：緩沖（減少CPU和I/O的速度差距）、異步I/O（等待I/O期間CPU可進(jìn)行其他操作）、DMA（CPU擺脫I/O）

死鎖

1. 死鎖：每個進(jìn)程無限等待被該組進(jìn)程中另一進(jìn)程占有的資源；與之對比，活鎖為先加鎖再輪詢不阻塞不推進(jìn)，饑餓是由于資源分配策略如優(yōu)先級導(dǎo)致得不到資源
2. 死鎖條件：互斥使用（資源獨(dú)占），占有且等待（部分分配），不可搶占（不可剝奪），循環(huán)等待（進(jìn)程等待環(huán)路）
3. 資源分配圖：進(jìn)程是圓，資源類是方，資源實例是方框中黑點(diǎn)；申請邊（進(jìn)程，資源類）表示進(jìn)程請求某類資源，分配邊（資源實例，進(jìn)程）表示資源分配給某進(jìn)程
4. 死鎖定理：在資源分配圖中，無環(huán)路必?zé)o死鎖，有環(huán)路可能有死鎖，有環(huán)且資源類只包含一個實例必有死鎖
5. 資源分配圖簡化：找只有分配邊的資源，去掉邊分配給需要的進(jìn)程，自己變成孤點(diǎn)；重復(fù)上述步驟，若最后所有都是孤點(diǎn)則無死鎖，否則有死鎖
6. 解決死鎖：鴕鳥算法（不考慮死鎖）、死鎖預(yù)防（靜態(tài)分配）、死鎖避免（動態(tài)評估）、死鎖檢測和解除
7. 死鎖預(yù)防：破壞死鎖必要條件；獨(dú)占轉(zhuǎn)為共享資源，一次性申請和分配、主動釋放部分分配，操作系統(tǒng)幫助搶占，資源有序分配法（資源按熱度編號，進(jìn)程按資源號增序請求）
8. 死鎖避免：對進(jìn)程發(fā)出的每一個能滿足的資源申請進(jìn)行動態(tài)檢查，根據(jù)分配后系統(tǒng)是否為不安全狀態(tài)（死鎖）決定是否分配
9. 安全序列：進(jìn)程序列中任意進(jìn)程，它還需要的資源不超過當(dāng)前系統(tǒng)剩余資源與它之前的所有進(jìn)程占有資源的和；此時系統(tǒng)為安全狀態(tài)，一定無死鎖，若不存在任何安全序列則為不安全狀態(tài)，一定導(dǎo)致死鎖
10. 銀行家算法：五類數(shù)組available, max[i], allocation[i], need[i], request[i]；當(dāng)進(jìn)程i提出request[i]時，若不大于available則將allocation[i]加request[i]、available和need[i]減request[i]，此時判斷新狀態(tài)是否安全，安全則分配否則等待
11. 死鎖檢測：允許死鎖發(fā)生，在資源不足、利用率下降時或周期性檢測系統(tǒng)進(jìn)展判斷是否真的有死鎖發(fā)生；死鎖后解除死鎖并以最小的代價恢復(fù)系統(tǒng)運(yùn)行，可通過撤銷死鎖進(jìn)程組、回退再啟動、按某種原則逐一撤銷進(jìn)程或剝奪資源
12. 哲學(xué)家就餐：同步互斥問題，五個哲學(xué)家日常行為是思考，兩兩間放一只筷子，饑餓時要從左右取兩只筷子才可吃飯，都先拿右邊筷子時出現(xiàn)死鎖；解決方法包括最多允許四個哲學(xué)家、利用管程一次性拿兩只筷子、設(shè)置哲學(xué)家的三種狀態(tài)結(jié)合檢測和PV操作、每個哲學(xué)家按筷子增序拿、由銀行家算法將最后的筷子分配給已拿到一只的人