大學(xué)操作系統(tǒng)課本：操作系統(tǒng)知識點(diǎn)

1、第一章（一）1.未配置操作系統(tǒng)的計算機(jī)系統(tǒng)（1）人工操作方式（人機(jī)矛盾）（2）脫機(jī)輸入/輸出方式2.單道批處理系統(tǒng) 內(nèi)存里一道作業(yè)3.多道批處理系統(tǒng) 優(yōu)點(diǎn)：（1）資源利用率高（CPU、內(nèi)存、I/0設(shè)備） （2）系統(tǒng)吞吐量大 缺點(diǎn)：（1）平均周轉(zhuǎn)時間長 （2）無交互能力3.分時系統(tǒng)（解決人機(jī)交互） 及時接收：多個用戶（配置多路卡）、為每個用戶配置一個緩沖區(qū) 及時處理：（1）作業(yè)直接進(jìn)入內(nèi)存 （2）采用輪轉(zhuǎn)運(yùn)行方式（時間片） 響應(yīng)時間=時間片×終端數(shù)4. 實(shí)時系統(tǒng)周期性實(shí)時任務(wù)和非. 硬實(shí)時任務(wù)和軟.（二）操作系統(tǒng)的基本特性1. 并發(fā)（進(jìn)程才能） 實(shí)現(xiàn)并發(fā)執(zhí)行的前提是：多道程序環(huán)境2.

2、共享 互斥共享方式、同時訪問方式3.虛擬（1）時空復(fù)用技術(shù)（虛擬處理機(jī)技術(shù)、虛擬設(shè)備技術(shù)） （2）空分復(fù)用技術(shù)（虛擬磁盤技術(shù)、虛擬儲存器技術(shù)）4. 異步5. 操作系統(tǒng)兩個最基本的特征：并發(fā)和共享第二章（一）1.前趨圖（有向無環(huán)圖）：描述進(jìn)程之間執(zhí)行的先后順序2.順序執(zhí)行：順序性、封閉性、可再現(xiàn)性 并發(fā)執(zhí)行：間斷性、失去封閉性、不可再現(xiàn)性（與時間有關(guān)的錯誤） Bernstein條件（二）1.進(jìn)程實(shí)體：包括程序段、數(shù)據(jù)的和PCB2.進(jìn)程的特征：動態(tài)性、并發(fā)性、獨(dú)立性、異步性（按各自速度推進(jìn)）3.進(jìn)程的三種基本狀態(tài)：就緒、執(zhí)行、阻塞 相互之間的轉(zhuǎn)換 注意：執(zhí)行-（時間片完）->就緒4.進(jìn)程的創(chuàng)

3、建（狀態(tài)）：申請空白PCB->分配資源->掛到就緒隊列 進(jìn)程的終止（狀態(tài)）：保存記錄->PCB返還系統(tǒng)5.進(jìn)程的掛起（不再被調(diào)度不在內(nèi)存了、suspend原語） 活動就緒-（掛起）->靜止就緒 活動阻塞-（掛起）->靜止阻塞 執(zhí)行 -（掛起）->靜止就緒 進(jìn)程的激活（active原語） 靜止就緒-（激活）->活動就緒 靜止阻塞-（激活）->活動阻塞6.PCB中的信息：P41 PCB組織方式：線性方式、鏈接方式、索引方式(三)1.OS內(nèi)核：常駐內(nèi)存 OS狀態(tài):系統(tǒng)態(tài)（管態(tài)、內(nèi)核態(tài)） 用戶態(tài)（目態(tài)）2.父進(jìn)程創(chuàng)建子進(jìn)程：3種返回值 進(jìn)程圖:描述進(jìn)程家

4、族關(guān)系的一棵樹3.進(jìn)程的創(chuàng)建（Creat原語） 引起進(jìn)程創(chuàng)建的事件：用戶登錄、作業(yè)調(diào)度、提供服務(wù)（創(chuàng)建打印進(jìn)程）、應(yīng)用請求（用戶創(chuàng)建） 創(chuàng)建過程：申請空白PCB->分配資源（從系統(tǒng)或父進(jìn)程）->初始化進(jìn)程控制塊（初始化內(nèi)容見P45）->插入就緒隊列4.進(jìn)程的終止 引起進(jìn)程終止的事件：正常結(jié)束、異常結(jié)束、外界干預(yù) 終止過程：P465.進(jìn)程的阻塞（block原語） 引起事件：請求共享資源失敗、等待某種操作的完成（I/O操作）、新數(shù)據(jù)未到達(dá)（合作進(jìn)程中）、等待新任務(wù)的到來（發(fā)送進(jìn)程，沒有信息可發(fā)送） 阻塞過程：狀態(tài)：執(zhí)行變?yōu)樽枞?>PCB掛到阻塞隊列->調(diào)度其他進(jìn)程6.

5、進(jìn)程的喚醒（wakeup原語） 喚醒過程：移除阻塞隊列->掛到就緒隊列（四）1.進(jìn)程的同步（1）同步:即某件事要等待另一件事完成才可以開始（2）2種相互制約關(guān)系：間接相互制約關(guān)系（進(jìn)程互斥訪問資源）、直接相互制約關(guān)系（進(jìn)程合作）2.臨界資源、臨界區(qū)（進(jìn)入?yún)^(qū)、退出區(qū)、剩余區(qū)）3.同步機(jī)制遵循的規(guī)則:空閑讓進(jìn)、忙則等待、有限等待、讓權(quán)等待（請求資源失敗應(yīng)釋放CPU）4.3種信號量：互斥信號量（初值為1）、資源信號量（初值可為n）、同步信號量(初值為0) P（wait）原語：減1 V(signal)原語：加1（五）1.進(jìn)程的互斥和同步稱為低級進(jìn)程通信，還有基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式也是2.進(jìn)程

6、通信方式（1）直接通信方式（基于共享存儲區(qū)） 申請一個緩沖區(qū)->將進(jìn)程A發(fā)送區(qū)的內(nèi)容復(fù)制給緩沖區(qū)->將緩沖區(qū)掛到進(jìn)程B的消息隊列->進(jìn)程B將緩沖區(qū)復(fù)制到自己的接收區(qū)（2）管道通信方式（對管道的write和read） 管道是一個pipe文件，作為一個中介（3） 消息傳遞方式（封裝）：直接和間接（有中間實(shí)體：郵箱）（六）進(jìn)程和線程的區(qū)別 重第三章（一）1.三大調(diào)度：高級調(diào)度（作業(yè)調(diào)度）：調(diào)度作業(yè)（外存->內(nèi)存），只用于多道批處理系統(tǒng) 低級調(diào)度（進(jìn)程調(diào)度）：調(diào)度進(jìn)程（就緒->獲得CPU） 中級調(diào)度（內(nèi)存調(diào)度）：掛起（內(nèi)存->外存->重入內(nèi)存）2.CPU利用率

7、：CPU有效工作時間/(CPU有效工作時間+CPU空閑等待時間)（二）1.作業(yè)：包含程序和數(shù)據(jù)，還有作業(yè)說明書。 批處理系統(tǒng)中，是以作業(yè)為基本單位從外存調(diào)入內(nèi)存的。2.作業(yè)控制塊（JCB）:作業(yè)在系統(tǒng)中存在的標(biāo)志。包含：作業(yè)標(biāo)識、.P883.作業(yè)進(jìn)入系統(tǒng)時->“作業(yè)注冊”程序?yàn)槠浣⒆鳂I(yè)控制塊->放到作業(yè)后備隊列（外存）->調(diào)度作業(yè)進(jìn)入內(nèi)存4.作業(yè)的4種狀態(tài)：提交狀態(tài)、后備狀態(tài)、運(yùn)行狀態(tài)（對應(yīng)的進(jìn)程有3種狀態(tài)）、完成狀態(tài)5.作業(yè)調(diào)度的任務(wù)：（1）接納多少個作業(yè)：取決于多道程序度 （2）接納哪些作業(yè)：取決于調(diào)度算法 調(diào)度時機(jī)：內(nèi)存中的進(jìn)程數(shù)小于多道度6.進(jìn)程的響應(yīng)時間（作業(yè)的周

8、轉(zhuǎn)時間）：完成時間-到達(dá)時間 或 服務(wù)時間+等待時間 平均周轉(zhuǎn)時間：N個的和除以N 帶權(quán)周轉(zhuǎn)時間：（服務(wù)時間+等待時間）/服務(wù)時間 或 1+等待時間/服務(wù)時間 平均帶權(quán)周轉(zhuǎn)時間：N個的和除以N7.調(diào)度算法(4種都可用于作業(yè)調(diào)度或進(jìn)程調(diào)度)（1）先來先服務(wù)（FCFS） 只能非搶占式（2）短進(jìn)程優(yōu)先（SJF）：有效降低作業(yè)的平均周轉(zhuǎn)時間；對長作業(yè)不利（3）優(yōu)先級調(diào)度算法(PSA)（4）高響應(yīng)比優(yōu)先調(diào)度算法（HRRN）:優(yōu)先級隨等待時間延長而增加 優(yōu)先權(quán)=（服務(wù)時間+等待時間）/服務(wù)時間 或 1+等待時間/服務(wù)時間 必須等某個進(jìn)程完成時，才重新計算優(yōu)先權(quán)，即運(yùn)行某進(jìn)程過程中有新進(jìn)程到達(dá)也不會重新調(diào)度

9、后面3個對于作業(yè)只能非搶占式；對于進(jìn)程，可搶占式或非搶占式8.題目未說明時，默認(rèn)是非搶占式。（三）1.非搶占式：調(diào)度時機(jī)為（1）進(jìn)程運(yùn)行完畢（2）進(jìn)程I/O請求（3）執(zhí)行Block原語 搶占式：搶占原則（1）優(yōu)先權(quán)（2）短進(jìn)程優(yōu)先（3）時間片2.調(diào)度算法（1）輪轉(zhuǎn)調(diào)度算法：基于時間片（2）優(yōu)先級調(diào)度算法（3）多隊列調(diào)度算法：多個就緒隊列，不同隊列采用不同的調(diào)度算法（4）多級反饋隊列調(diào)度算法：對于長作業(yè)，往后時間片越長，得到的處理時間越長（5）最低松弛度優(yōu)先算法：松弛度=必須完成時間-需要服務(wù)時間（四）1.可重用性資源（打印機(jī)）：請求資源->獲得資源->釋放資源 可消耗性資源（通信中

10、的消息）：進(jìn)程運(yùn)行期間動態(tài)創(chuàng)建和消耗的，不再返回 可搶占性資源（CPU、內(nèi)存） 不可搶占性資源（打印機(jī)）：可能引起死鎖2.引起死鎖的3個原因：（1）競爭不可搶占性資源（2）競爭可消耗性資源（3）進(jìn)程推進(jìn)順序不當(dāng)（不安全區(qū)D）3.產(chǎn)生死鎖的必要條件：（1）互斥條件（2）請求和保持條件（3）不可搶占條件（4）循環(huán)等待條件（產(chǎn)生回路）4.處理死鎖的方法：（1）預(yù)防死鎖（2）避免死鎖（3）檢測死鎖（4）解除死鎖5.預(yù)防死鎖：破壞其中一個條件（1）互斥條件不能破壞還應(yīng)保持（2）破壞請求和保持條件：A.一次性申請所需全部資源 B.申請部分資源，用完釋放，然后繼續(xù)申請(資源靜態(tài)分配)（3）破壞不可搶占條件：

11、提出新的資源請求時，必須釋放自己已保持的所有資源（好像被搶占了）（4）破壞循環(huán)等待條件：每個進(jìn)程按序號遞增的順序請求資源（資源有序分配）6.避免死鎖：防止系統(tǒng)進(jìn)入不安全狀態(tài)（1）系統(tǒng)安全狀態(tài)：分配資源后，系統(tǒng)能按一安全序列推進(jìn)（2）銀行家算法：二維數(shù)組 A.表示每個進(jìn)程對每個資源的最大需求量 B.表示每個進(jìn)程對每個資源已分配到的 C.表示每個進(jìn)程對每個資源還需要的 一維數(shù)組 A.表示每類資源的可分配數(shù) available B.表示每個資源當(dāng)前可分配數(shù)（即加上某個進(jìn)程運(yùn)行完，釋放后的資源數(shù)）work C.表示每個進(jìn)程能否獲得足夠資源而運(yùn)行 finish 算法思路：P112-1147.檢測死鎖：（

12、1）資源分配圖（2）死鎖定理：S為死鎖的充分條件:當(dāng)且僅當(dāng)S狀態(tài)的資源分配圖是不可完全簡化的8.解除死鎖：（1）搶占資源（2）終止（撤銷）進(jìn)程 方法：A.終止所有進(jìn)程 B.逐個終止進(jìn)程：付出代價最小的死鎖解除算法P117-118第四章 存儲器管理均稱為傳統(tǒng)存儲器管理方式，具有2個特點(diǎn)：一次性和駐留性 P153（一）1.存儲系統(tǒng)至少3級：最高層為CPU寄存器，內(nèi)存，最底層為輔存。2.可執(zhí)行存儲器：寄存器和內(nèi)存。3.進(jìn)程訪問可執(zhí)行存儲器：使用一條load或store指令即可 訪問輔存：需通過I/O設(shè)備4.程序的裝入方式（1）絕對裝入方式：單道環(huán)境 程序的相對地址（邏輯地址）與內(nèi)存地址完全相同（2）

13、靜態(tài)可重定位裝入方式：多道環(huán)境 在裝入時對目標(biāo)程序中指令和數(shù)據(jù)地址進(jìn)行修改，以后不再改變。（3）動態(tài)運(yùn)行時的裝入方式：程序運(yùn)行過程在內(nèi)存的位置經(jīng)常會改變 裝入內(nèi)存，地址轉(zhuǎn)換推遲到程序運(yùn)行時才進(jìn)行。 A.工作原理：增設(shè)一個重定位寄存器，存放程序在內(nèi)存中的起始地址->真正訪問內(nèi)存地址=相對地址+寄存器中的地址 ->程序移動時，只需修改寄存器中的起始地址 B.在“緊湊（拼接）”時，要用到。（二）連續(xù)分配存儲管理方式1.單一連續(xù)分配：單道環(huán)境 內(nèi)存分為系統(tǒng)區(qū)（多放在低址）和用戶區(qū)2.固定分區(qū)分配：多道環(huán)境 內(nèi)存劃分為若干個固定大小的區(qū)域，一個區(qū)域裝入一道作業(yè)（1）a.分區(qū)大小相等 b.分區(qū)

14、大小不等（2）地址映射：采用靜態(tài)重定位（3）缺點(diǎn)：造成大量的內(nèi)部碎片（4）數(shù)據(jù)結(jié)構(gòu)：分區(qū)使用表 包括分區(qū)號、大小、起址、狀態(tài)。3.動態(tài)分區(qū)分配（可變分區(qū)分配）：（1）分區(qū)分配：按需劃分 分區(qū)回收：合并回收（2）數(shù)據(jù)結(jié)構(gòu)：空閑分區(qū)表 包括分區(qū)號、大小、起址、狀態(tài)（全都是未分配） 空閑分區(qū)鏈 雙向的（3）分配：P128 下面 回收：P129 注意不同合并方式會對空閑分區(qū)表的修改不同（4）基于順序搜索的動態(tài)分區(qū)分配算法 A.首次適應(yīng)算法：每次分配從頭順序查找，找到大小可以滿足為止 特點(diǎn)：優(yōu)先利用內(nèi)存地址空閑區(qū)，保留了高址的大空閑區(qū) 缺點(diǎn)：低址不斷被劃分，產(chǎn)生許多碎片；查找效率低 對固定分區(qū)：整體分配

15、，易形成內(nèi)碎片 對可變分區(qū)：按需劃分，易形成外碎片 B.循環(huán)首次適應(yīng)算法：循環(huán)的，從上次找到的位置往下查找 特點(diǎn)：使內(nèi)存的空閑分區(qū)分布得更均勻 缺點(diǎn)：缺乏大的空閑分區(qū) C.最佳適應(yīng)算法：所有空閑分區(qū)從小到大形成空閑分區(qū)鏈 缺點(diǎn)：留下許多碎片 對固定分區(qū)：內(nèi)碎片小 對可變分區(qū)：易形成外碎片 D.最壞適應(yīng)算法：所有空閑分區(qū)從大到小形成空閑分區(qū)鏈 優(yōu)點(diǎn)：產(chǎn)生碎片的可能性最??；查找效率高 對固定分區(qū)：內(nèi)碎片大 對可變分區(qū)：剩余分區(qū)可再次利用（5）基于索引搜索的動態(tài)分區(qū)分配算法 A.快速適應(yīng)算法：相同容量的空閑分區(qū)形成一個空閑分區(qū)鏈 設(shè)置索引表查找 特點(diǎn)：不會對任何分區(qū)產(chǎn)生分割，不會產(chǎn)生內(nèi)存碎片 優(yōu)點(diǎn)：

16、查找效率高 在分配分區(qū)時，以進(jìn)程為單位，一個分區(qū)只屬于一個進(jìn)程，或多或少存在浪費(fèi) B.伙伴系統(tǒng)：原理、分配、回收、計算伙伴地址 P132 C.哈希算法：建立哈希函數(shù)，構(gòu)造哈希表4.動態(tài)重定位分區(qū)分配算法：與3（3）基本相同，差別僅在于增加了緊湊的功能（三）對換1.對換：進(jìn)程或程序和數(shù)據(jù)：內(nèi)存<->外存2.對換的類型：（1）整體對換（進(jìn)程對換）：整個進(jìn)程為單位對換（2）頁面/分段對換（部分對換）：以進(jìn)程的一個頁面或分段為單位對換 目的：支持虛擬存儲系統(tǒng)3.磁盤空間分為文件區(qū)和對換區(qū)（對換空間） 文件區(qū)：離散分配 對換區(qū)：按需分配（分配算法上面4種都可以）、合并回收4. 進(jìn)程的換進(jìn)換出

17、的選擇標(biāo)準(zhǔn) P137 換出：換到無阻塞進(jìn)程為止 換入：第一個換“就緒”且換出時間最久的進(jìn)程，繼續(xù)換到無處于“就緒且換出”狀態(tài)的進(jìn)程為止（四）分頁存儲管理方式：提高內(nèi)存利用率1.程序分為若干固定大小的頁面，內(nèi)存同樣稱為物理塊（頁框）2.頁面大小應(yīng)為2的冪，通常為1KB-8KB3.地址結(jié)構(gòu)：頁號P+頁內(nèi)地址W（一維的） 若頁面的大小為L,則邏輯地址LA=P*L+W4.每個進(jìn)程一張頁面映像表（頁表）：存放在內(nèi)存里，實(shí)現(xiàn)從頁號到物理塊號的地址映射 頁表大小=表項數(shù)*表項大小 P1395.地址變換機(jī)構(gòu)：實(shí)現(xiàn)從邏輯地址到物理地址的轉(zhuǎn)換6.頁表寄存器：存放頁表始址+頁表長度 進(jìn)程未執(zhí)行時，頁表始址+頁表長度

18、放在本進(jìn)程PCB中->執(zhí)行時，裝入頁表寄存器7.查找過程（2次訪問內(nèi)存）：頁表寄存器->頁表（內(nèi)存里）->得到內(nèi)存物理地址，到內(nèi)存取指令8.具有快表（聯(lián)想寄存器）：先查快表看能否命中，未能命中則查完頁表后還要修改快表9.查快表t1,查頁表和取指令t2: 若同時查塊表和頁表：命中：t1+t2 未命中：t2+t1(修改快表)+t2 若命中率為h,可得有效訪問內(nèi)存的時間:h*t1+(1-h)*(t2+t1)+t2（五）分段存儲管理方式：滿足用戶編程和使用的要求1.作業(yè)分為若干個大小不同的段2.一個作業(yè)最多64K個段，每個段最大長度為64KB3.地址結(jié)構(gòu)：段號+段內(nèi)地址（二維的） 段

19、號太大，段表中找不到則表示越界；段內(nèi)地址太大，超過段表中目的段的大小，則表示段內(nèi)越界。4.每個進(jìn)程一張段映射表（段表）：存放在內(nèi)存里，每個表項包含一個段的起始地址（基址）+該段的長度5.地址變換機(jī)構(gòu)：段表寄存器，存放段表始址+段表長度6.查找過程（2次訪問內(nèi)存）：段表寄存器->段表（內(nèi)存里）->得到內(nèi)存物理地址，到內(nèi)存取指令7.具有聯(lián)想寄存器的：與分頁式相同8.分頁與分段的區(qū)別：P148(重)（六）段頁式存儲管理方式1.程序分成若干段，每個段再分成若干頁2.地址結(jié)構(gòu)：段號+段內(nèi)頁號+頁內(nèi)地址（二維的）3.需要段表寄存器、段表、頁表： 每個進(jìn)程一張段表，段表包含頁表始址+頁表大小4.

20、查找過程（3次訪問內(nèi)存）：段表寄存器->找段表（內(nèi)存里），得到該段對應(yīng)的頁表起始地址->找頁表（內(nèi)存里），得到該頁的物里塊號->形成物理地址，到內(nèi)存取指令5.具有聯(lián)想寄存器的：與分頁式相同第五章 虛擬儲存器原理：局部性原理（時間局部性、空間局部性）（一）概述1.虛擬儲存器：具有請求調(diào)入功能和置換功能，從邏輯上對內(nèi)存容量擴(kuò)充2.特征：多次性、對換性、虛擬性3.實(shí)現(xiàn)虛擬儲存器的基礎(chǔ)：離散存放、多次裝入（二）請求分頁存儲管理方式1.頁表增加4個字段：狀態(tài)位（該頁是否已調(diào)入內(nèi)存）、訪問位（訪問次數(shù)或多久未訪問）、 修改位（有被修改的置換時要寫回外存）、外存地址2.缺頁中斷機(jī)構(gòu)：指令執(zhí)

21、行期間，發(fā)現(xiàn)要訪問的指令或數(shù)據(jù)不在內(nèi)存，馬上發(fā)出中斷 這種屬于陷進(jìn)（軟中斷），之前打印機(jī)那些是硬中斷3.地址變換過程 P158(重) 注意最后必有“修改訪問位和修改位”這一步驟4.最小物理塊數(shù)：進(jìn)程能正常運(yùn)行的最小物理塊數(shù)5.內(nèi)存分配策略：（1）固定分配局部置換 固定分配：為每個進(jìn)程分配固定數(shù)目的物理塊，不再改變 局部置換：只能從分配給該進(jìn)程的頁面中選一頁換出（2）可變分配全局置換（3）可變分配局部置換 一進(jìn)程運(yùn)行時缺頁率很低，可以減少分配給該進(jìn)程的物理塊數(shù)6.物理塊分配算法（1）平均分配算法：平均分配給各個進(jìn)程（2）按比例分配算法：按進(jìn)程大?。?）考慮優(yōu)先級的分配算法7.頁面調(diào)入策略（1）何

22、時調(diào)入 A.預(yù)調(diào)頁策略：將預(yù)計不久后會被訪問的頁面預(yù)先調(diào)入內(nèi)存，可用于首次調(diào)入時 B.請求調(diào)頁策略：缺頁請求時再調(diào)入，一次只調(diào)入一頁（2）何處調(diào)入 UNIX方式：從未運(yùn)行過的，從文件區(qū)調(diào)入 置換在對換區(qū)的，從對換區(qū)調(diào)入8.缺頁率：訪問頁面失敗的次數(shù)F/訪問頁面總次數(shù)A（三）頁面置換算法1.最佳置換算法（無法實(shí)現(xiàn)的）：換出未來最遲被訪問的頁面2.先進(jìn)先出置換算法：可能產(chǎn)生Belady異常，即分配的頁面數(shù)越多，缺頁率反而越多 原因：先進(jìn)的一般都是經(jīng)常被訪問的3.最近最久未使用置換算法（LRU）:需要移位寄存器或棧兩個硬件之一的支持 移位寄存器：每個在內(nèi)存的頁面配置一個 R=Rn-1Rn-2.R1R

23、0 進(jìn)程訪問某物理塊時，將相應(yīng)的寄存器的Rn-1位置1。每隔一段時間寄存器右移一位。 最小數(shù)值那個就是最近最久未使用的頁面。 棧：棧頂總是最近訪問的頁面號（命中時調(diào)到棧頂），棧低總是最久的（置換時從棧底淘汰）4.最少使用置換算法（LFU）:即看訪問次數(shù)最少的 采用移位寄存器方式：每次訪問某頁，將該寄存器最高位置1，每隔一段時間右移一位。 最小數(shù)值那個就是最少使用的頁面。5.簡單的Clock置換算法（最近未用算法NRL）： 每頁設(shè)置訪問位(A)，將內(nèi)存中所有頁面構(gòu)成循環(huán)隊列。 某頁被訪問時，訪問位置1 置換時，若訪問位為0則換出，為1則改為0 改進(jìn)的Clock置換算法：多了修改位(W)，修改為為

24、1表示修改過 第一步：優(yōu)先置換“A=0，W=0”的頁面，不改變訪問位A 第二步：找“A=0，W=1”的頁面，同時將A=1的改為A=0 第三步：重復(fù)第一步6.頁面緩沖算法（PBA）：（1）影響頁面換進(jìn)換出效率的因素 A.頁面置換算法 B.寫回磁盤的頻率 C.讀入內(nèi)存的頻率（2）算法原理: A.空閑頁面鏈表：用于分配給頻繁缺頁的進(jìn)程、一個未被修改的頁面（有數(shù)據(jù)）要換出時，不換出，接到該鏈末尾 B.修改頁面鏈表：一個已修改的頁面要換出時，不換出，接到該鏈末尾，方便集中寫回磁盤（四）抖動與工作集1.工作集：某段時間內(nèi)，進(jìn)程實(shí)際所要訪問頁面的集合 不同時間的工作集大小不同，所含的頁面數(shù)也不同 P1712

25、.抖動（1）產(chǎn)生原因：進(jìn)程太多，缺頁頻繁，CPU效率急劇下降（進(jìn)程處于“抖動”狀態(tài)）（2）產(chǎn)生前提：采取可變分配+全局置換（3）預(yù)防方法：A.采取局部置換策略 B.把工作集算法融入到處理機(jī)調(diào)度中 調(diào)入作業(yè)之前，檢查每個進(jìn)程在內(nèi)存的駐留頁面是否足夠多。 C.利用“L=S”準(zhǔn)則調(diào)節(jié)缺頁率 P172 D.選擇暫停的進(jìn)程：掛起若干進(jìn)程第六章（一）I/O系統(tǒng)1.I/O系統(tǒng)的層次結(jié)構(gòu)：從下往上：硬件->中斷處理程序->設(shè)備驅(qū)動程序->設(shè)備獨(dú)立性軟件->用戶層軟件2.I/O系統(tǒng)的上、下接口：I/O系統(tǒng)接口、軟件/硬件接口（下面就是硬件部分了）3.I/O系統(tǒng)的分層：從下往上：中斷處理程

26、序->設(shè)備驅(qū)動程序->設(shè)備獨(dú)立性軟件4.I/O系統(tǒng)接口：有3種（1）塊設(shè)備接口 A.塊設(shè)備：以數(shù)據(jù)塊為單位（磁盤）特點(diǎn)：傳輸速率高；可尋址；磁盤設(shè)備的I/O常采用DMA方式 B.塊設(shè)備接口特征：隱藏了磁盤的二維結(jié)構(gòu)（磁道號+扇區(qū)）；將抽象的命令映射為底層操作（2）流設(shè)備接口 A.流設(shè)備：以字符為單位（鍵盤、打印機(jī)） 特點(diǎn)：傳輸速率低；不可尋址；流設(shè)備的I/O常采用中斷驅(qū)動方式 B.程序用get和put操作，只能順序存取 C.大多數(shù)流設(shè)備屬于獨(dú)占設(shè)備（互斥方式），要提供打開/關(guān)閉操作。（3）網(wǎng)絡(luò)通信接口（二）硬件部分1.I/O設(shè)備的類型：存儲設(shè)備和I/O設(shè)備、低速設(shè)備（鍵盤、鼠標(biāo)）和

27、中速設(shè)備（打印機(jī)）和高速設(shè)備（磁盤、光盤）2.設(shè)備控制器（控制一個或多個I/O設(shè)備）（1）三部分組成： A.設(shè)備控制器與CPU的接口（并行）： 數(shù)據(jù)總線->DR:內(nèi)存<->設(shè)備 ->C/S:狀態(tài)：設(shè)備->CPU 啟動：CPU->設(shè)備 地址總線：設(shè)備名->譯碼電路（I/O邏輯）->接口 控制總線：操作碼->譯碼電路->CR B.設(shè)備控制器與設(shè)備的接口（串行）： 數(shù)據(jù)線：設(shè)備<->DR 狀態(tài)線：設(shè)備->C/S 控制線：C/S->設(shè)備 C.譯碼電路（I/O邏輯）：實(shí)現(xiàn)對設(shè)備的控制 上面2個譯碼功能+并行-（分解）-&

28、gt;<-(組裝)-串行（2）CPU啟動一個設(shè)備的過程： 啟動命令->設(shè)備控制器 地址（即要選哪個設(shè)備）-地址線->設(shè)備控制器->I/O邏輯進(jìn)行譯碼->選中設(shè)備（3）設(shè)備->DR:數(shù)據(jù)準(zhǔn)備；DR->內(nèi)存：數(shù)據(jù)傳送（4）設(shè)備控制器的功能： A.接收和識別命令 B.數(shù)據(jù)交換 C.標(biāo)識和報告設(shè)備的狀態(tài) D.地址識別（設(shè)備控制器可連接多個設(shè)備、其里面也有很大寄存器，都需要地址） E.數(shù)據(jù)緩沖區(qū) F.差錯控制3.I/O通道（特殊處理機(jī)）（1）在CPU與設(shè)備控制器之間 目的：建立獨(dú)立的I/O操作（2）過程：CPU發(fā)I/O指令->通道->內(nèi)存中取對應(yīng)的通

29、道程序并執(zhí)行->完成后，向CPU發(fā)中斷信號（3）通道與CPU共享內(nèi)存（其通道程序放在內(nèi)存）（4）通道的類型： A.字節(jié)多路通道：每個字通道連接一個設(shè)備，按時間片輪轉(zhuǎn)共享主通道 適合低速設(shè)備 B.數(shù)組選擇通道：每次只允許一個設(shè)備傳輸數(shù)據(jù) C.數(shù)組多路通道（三）設(shè)備驅(qū)動程序1.設(shè)備驅(qū)動程序的功能： A.將命令中的抽象要求轉(zhuǎn)換為與設(shè)備相關(guān)的底層操作 B.檢查I/O請求的合法性，設(shè)置設(shè)備的工作方式 C.啟動I/O設(shè)備 D.及時響應(yīng)設(shè)備控制器發(fā)來的中斷請求，調(diào)用相應(yīng)的中斷處理程序2.設(shè)備驅(qū)動程序的特點(diǎn)： A.用匯編語言編寫 B.允許可重入3.設(shè)備處理方式： A.每類設(shè)備一個進(jìn)程來控制 B.整個系統(tǒng)

30、一個進(jìn)程或一個輸入一個輸出共2個進(jìn)程 C.不設(shè)置進(jìn)程（常用）4.設(shè)備驅(qū)動程序的處理過程：將抽象要求轉(zhuǎn)換為具體要求->對服務(wù)請求進(jìn)行校驗(yàn)->檢查設(shè)備的狀態(tài)->傳送必要的參數(shù) ->啟動I/O設(shè)備 啟動后，驅(qū)動程序把控制返回給I/O系統(tǒng)，自己阻塞起來，直到中斷到來被喚醒 I/O操作是在設(shè)備控制器的控制下進(jìn)行，實(shí)現(xiàn)處理機(jī)與I/O設(shè)備的并行操作5.對I/O設(shè)備的控制方式（1）輪詢的可編程I/O方式：數(shù)據(jù)傳送過程中，CPU一直查詢 CPU與設(shè)備、設(shè)備之間只能串行工作（2）中斷的可編程I/O方式（以字節(jié)為單位傳送數(shù)據(jù)）： 數(shù)據(jù)傳送過程中，CPU干別的事，傳送好控制器通過控制線發(fā)中斷給CPU，CPU取走數(shù)據(jù)寫入內(nèi)存 能并行工作（3）直接儲存器訪問方式（DMA方式）： A.以數(shù)據(jù)塊為單位、直接從設(shè)備到內(nèi)存、在控制器的控制下不用經(jīng)過CPU B.DMA控制器：三部分組成：DMA控制器與主機(jī)的接口、與設(shè)備的接口、I/O控制邏輯 含有4個寄存器：數(shù)據(jù)寄存器DR、控制/狀態(tài)寄存器C