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

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

2、J,/、互斥共享方式、同時訪問方式3.虛擬（ 1）時空復(fù)用技術(shù)（虛擬處理機技術(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ù)據(jù)的和 PCB2.進(jìn)程的特征：動態(tài)性、并發(fā)性、獨立性、異步性（按各自速度推進(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 中的信息： P41PCB 組織方式：線性方式、鏈接方式、索引方式（三）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)程家族關(guān)系的一棵

4、樹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.進(jìn)程的喚醒（ wa

5、keup 原語）喚醒過程：移除阻塞隊列 - 掛到就緒隊列四）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.同步機制遵循的規(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)的

6、通信方式也是2. 進(jìn)程通信方式（ 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）消息傳遞方式（封裝）：直接和間接（有中間實體：郵箱）（六）進(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)

7、存）2.CPU 利用率： 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è)控制塊 - 放到作業(yè)后備隊列（外存） - 調(diào)度作業(yè)進(jìn)入內(nèi)存4.作業(yè)的 4 種狀態(tài)：提交狀態(tài)、后備狀態(tài)、運行狀態(tài)（對應(yīng)的進(jìn)程有 3 種狀態(tài)）、完成狀態(tài)5.作業(yè)調(diào)度的任務(wù)：（ 1）接納多少個作業(yè)：取決于 多道程序度（2）接納哪些作業(yè)：取決于 調(diào)度算法 調(diào)度時機：內(nèi)存中

8、的進(jìn)程數(shù)小于多道度6.進(jìn)程的響應(yīng)時間 （作業(yè)的周轉(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+等待時間/

9、服務(wù)時間 必須等某個進(jìn)程完成時，才重新計算優(yōu)先權(quán)，即運行某進(jìn)程過程中有新進(jìn) 程到達(dá)也不會重新調(diào)度后面 3 個對于作業(yè)只能非搶占式；對于進(jìn)程，可搶占式或非搶占式8.題目未說明時，默認(rèn)是非搶占式。（三）1.非搶占式：調(diào)度時機為 （1 ）進(jì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)先算法：松

10、弛度 =必須完成時間 -需要服務(wù)時間（四）1.可重用性資源（打印機）：請求資源 - 獲得資源 - 釋放資源 可消耗性資源（通信中的消息）：進(jìn)程運行期間動態(tài)創(chuàng)建和消耗的，不再返回 可搶占性資源（CPU、內(nèi)存）不可搶占性資源（打印機）：可能引起死鎖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

11、）互斥條件不能破壞還應(yīng)保持（2）破壞請求和保持條件：A. 一次性申請所需全部資源B.申請部分資源，用完釋放，然后繼續(xù)申請 （資源靜態(tài)分配 ）（ 3）破壞不可搶占條件：提出新的資源請求時，必須釋放自己已保持的所有資 源（好像被搶占了）（ 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ù) avai

12、lableB. 表示每個資源當(dāng)前可分配數(shù)（即加上某個進(jìn)程運 行完，釋放后的資源數(shù)） workC. 表示每個進(jìn)程能否獲得足夠資源而運行finish算法思路： P112-1147. 檢測死鎖：（ 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 個特點：一次性和駐留性 P153（一）1. 存儲系統(tǒng)至少 3 級：最高層為 CPU 寄存器，內(nèi)存，最底層為輔存。2

13、. 可執(zhí)行存儲器：寄存器和內(nèi)存 。3. 進(jìn)程訪問可執(zhí)行存儲器：使用一條 load 或 store 指令即可訪問輔存：需通過 I/O 設(shè)備4. 程序的裝入方式（ 1 ）絕對裝入方式 ：單道環(huán)境 程序的相對地址（邏輯地址）與內(nèi)存地址完全 相同（ 2） 靜態(tài)可重定位裝入方式 ：多道環(huán)境 在裝入時對目標(biāo)程序中指令和數(shù)據(jù)地 址進(jìn)行修改，以后不再改變。（3）動態(tài)運行時的裝入方式 ：程序運行過程在內(nèi)存的位置經(jīng)常會改變 裝入內(nèi) 存，地址轉(zhuǎn)換推遲到程序運行時才進(jìn)行。A. 工作原理：增設(shè)一個 重定位寄存器，存放程序在內(nèi)存中的起始地址- 真正訪問內(nèi)存地址 =相對地址 +寄存器中的地址- 程序移動時，只需修改寄存器中

14、的起始地址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ū)大小不等( 2 )地址映射：采用靜態(tài)重定位( 3)缺點：造成大量的內(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 下面回

15、收： P1 29 注意不同合并方式會對空閑分區(qū)表的修改不同( 4)基于順序搜索的動態(tài)分區(qū)分配算法A. 首次適應(yīng)算法：每次分配從頭順序查找，找到大小可以滿足為止特點：優(yōu)先利用內(nèi)存地址空閑區(qū)，保留了高址的大空閑區(qū)缺點：低址不斷被劃分，產(chǎn)生許多碎片；查找效率低對固定分區(qū)：整體分配，易形成內(nèi)碎片對可變分區(qū)：按需劃分，易形成外碎片B. 循環(huán)首次適應(yīng)算法：循環(huán)的，從上次找到的位置往下查找特點：使內(nèi)存的空閑分區(qū)分布得更均勻缺點：缺乏大的空閑分區(qū)C.最佳適應(yīng)算法：所有空閑分區(qū)從小到大形成空閑分區(qū)鏈缺點：留下許多碎片對固定分區(qū)：內(nèi)碎片小對可變分區(qū)：易形成外碎片D. 最壞適應(yīng)算法：所有空閑分區(qū)從大到小形成空閑分區(qū)

16、鏈優(yōu)點： 產(chǎn)生碎片的可能性最小 ；查找效率高對固定分區(qū)：內(nèi)碎片大對可變分區(qū)：剩余分區(qū)可再次利用（5）基于索引搜索的動態(tài)分區(qū)分配算法A. 快速適應(yīng)算法：相同容量的空閑分區(qū)形成一個空閑分區(qū)鏈設(shè)置索引表查找特點：不會對任何分區(qū)產(chǎn)生分割， 不會產(chǎn)生內(nèi)存碎片優(yōu)點：查找效率高在分配分區(qū)時，以進(jìn)程為單位，一個分區(qū)只屬于一個進(jìn)程，或多或少存在浪 費B. 伙伴系統(tǒng)：原理、分配、回收、計算伙伴地址P132C. 哈希算法：建立哈希函數(shù)，構(gòu)造哈希表4.動態(tài)重定位分區(qū)分配算法：與 3（3）基本相同，差別僅在于增加了緊湊的功 能（三）對換1. 對換：進(jìn)程或程序和數(shù)據(jù)：內(nèi)存 外存2. 對換的類型 ：（ 1 ）整體對換（進(jìn)程

17、對換）：整個進(jìn)程為單位對換（2）頁面 /分段對換（部分對換）：以進(jìn)程的一個頁面或分段為單位對換目的：支持虛擬存儲系統(tǒng)3.磁盤空間分為文件區(qū)和對換區(qū)（對換空間）文件區(qū)：離散分配對換區(qū)：按需分配（分配算法上面 4 種都可以）、合并回收4.進(jìn)程的換進(jìn)換出的選擇標(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,

18、則邏輯地址 LA=P*L+W4. 每個進(jìn)程一張 頁面映像表（頁表） ：存放在內(nèi)存里，實現(xiàn)從頁號到物理塊號的地址映射頁表大小 = 表項數(shù) *表項大小 P1395. 地址變換機構(gòu)：實現(xiàn)從邏輯地址到物理地址的轉(zhuǎn)換6. 頁表寄存器：存放頁表始址 + 頁表長度進(jìn)程未執(zhí)行時，頁表始址 + 頁表長度放在 本進(jìn)程 PCB 中- 執(zhí)行時，裝入頁表 寄存器7. 查找過程（ 2 次訪問內(nèi)存）：頁表寄存器 - 頁表（內(nèi)存里） - 得到內(nèi)存物理 地址，到內(nèi)存取指令8. 具有快表（聯(lián)想寄存器）：先查快表看能否命中，未能命中則查完頁表后還要修改快表9. 查快表 t1, 查頁表和取指令 t2:若同時查塊表和頁表：命中： t1

19、+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)地址（二維的）段號太大，段表中找不到則表示 越界 ；段內(nèi)地址太大，超過段表中目的段的大 小，則表示 段內(nèi)越界 。4.每個進(jìn)程一張段映射表（段表）：存放在內(nèi)存里，每個表項包含一個 段的起始 地址（基址） + 該段的長度5.地址變換機構(gòu)：段表寄存器，存放段表始址 + 段表長度6.查找過程（ 2 次訪問內(nèi)存

20、）：段表寄存器 - 段表（內(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.查找過程（ 3 次訪問內(nèi)存）：段表寄存器 - 找段表（內(nèi)存里），得到該段對 應(yīng)的頁表起始地址 - 找頁表（內(nèi)存里），得到該頁的物里塊號 - 形成物理地 址，到內(nèi)存取指令5.具有聯(lián)想寄存器的：與分頁式相同第五章 虛擬儲存器 原理：局部性原理（時間局部性、空

21、間局部性）（一）概述1.虛擬儲存器：具有 請求調(diào)入 功能和置換功能，從邏輯上對內(nèi)存容量擴充2.特征：多次性、對換性、虛擬性3.實現(xiàn)虛擬儲存器的基礎(chǔ)：離散存放、多次裝入（二）請求分頁存儲管理方式1.頁表增加 4 個字段：狀態(tài)位（該頁是否已調(diào)入內(nèi)存）、訪問位（訪問次數(shù)或多 久未訪問）、修改位（有被修改的置換時要寫回外存）、 外存地址2.缺頁中斷機構(gòu) ：指令執(zhí)行期間，發(fā)現(xiàn)要訪問的指令或數(shù)據(jù)不在內(nèi)存，馬上發(fā)出 中斷這種屬于陷進(jìn)（軟中斷），之前打印機那些是硬中斷3.地址變換過程 P158（ 重） 注意最后必有“修改訪問位和修改位”這一步驟4.最小物理塊數(shù)：進(jìn)程能正常運行的最小物理塊數(shù)5.內(nèi)存分配策略 ：

22、（1）固定分配局部置換 固定分配：為每個進(jìn)程分配固定數(shù)目的物理塊，不再改變 局部置換：只能從分配給該進(jìn)程的頁面中選一頁換出（ 2）可變分配全局置換（3）可變分配局部置換 一進(jìn)程運行時缺頁率很低，可以減少分配給該進(jìn)程的物理塊數(shù)6.物理塊分配算法（1）平均分配算法：平均分配給各個進(jìn)程（2）按比例分配算法：按進(jìn)程大小3）考慮優(yōu)先級的分配算法7.頁面調(diào)入策略（1）何時調(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 方式：從未運行過的，從文件區(qū)調(diào)入置換在對換區(qū)的，從對換區(qū)調(diào)入8缺頁率：訪問頁面失敗

23、的次數(shù) F/訪問頁面總次數(shù) A（三）頁面置換算法1. 最佳置換算法（無法實現(xiàn)的）：換出未來最遲被訪問的頁面2. 先進(jìn)先出置換算法： 可能產(chǎn)生 Belady 異常，即分配的頁面數(shù)越多，缺頁率反 而越多原因：先進(jìn)的一般都是經(jīng)常被訪問的3最近最久未使用置換算法（LRU）:需要移位寄存器或棧兩個硬件之一的支持移位寄存器：每個在內(nèi)存的頁面配置一個R=Rn-1Rn-2.R1R0進(jìn)程訪問某物理塊時，將相應(yīng)的寄存器的 Rn-1 位置 1。每隔一 段時間寄存器右移一位。最小數(shù)值那個就是最近最久未使用的頁面。棧：棧頂總是最近訪問的頁面號（命中時調(diào)到棧頂），棧低總是最久的（置換 時從棧底淘汰）4.最少使用置換算法（

24、 LFU） :即看訪問次數(shù)最少的采用移位寄存器方式：每次訪問某頁，將該寄存器最高位置 1，每隔一段 時間右移一位。最小數(shù)值那個就是最少使用的頁面。5.簡單的 Clock 置換算法（最近未用算法 NRL ）：每頁設(shè)置訪問位 （A） ，將內(nèi)存中所有頁面構(gòu)成循環(huán)隊列。 某頁被訪問時， 訪問位置 1置換時，若訪問位為 0 則換出，為 1 則改為 0改進(jìn)的 Clock 置換算法 ：多了修改位 （W） ，修改為為 1 表示修改過 第一步：優(yōu)先置換“ A=0 ，W=0 ”的頁面，不改變訪問位 A 第二步：找“ A=0 ，W=1 ”的頁面，同時將 A=1 的改為 A=0 第三步：重復(fù)第一步6.頁面緩沖算法（

25、PBA）：（1）影響頁面換進(jìn)換出效率的因素A. 頁面置換算法 B.寫回磁盤的頻率 C.讀入內(nèi)存的頻率（ 2）算法原理 :A. 空閑頁面鏈表：用于分配給頻繁缺頁的進(jìn)程、一個 未被修改的頁面（有 數(shù)據(jù)）要換出時，不換出，接到該鏈末尾B. 修改頁面鏈表：一個 已修改的頁面要換出時，不換出，接到該鏈末尾， 方便集中寫回磁盤（四）抖動與工作集1. 工作集：某段時間內(nèi)，進(jìn)程實際所要訪問頁面的集合不同時間的工作集大小不同，所含的頁面數(shù)也不同 P1712. 抖動（ 1）產(chǎn)生原因：進(jìn)程太多，缺頁頻繁， CPU 效率急劇下降（進(jìn)程處于“抖動” 狀態(tài)）2）產(chǎn)生前提：采取可變分配 + 全局置換（3）預(yù)防方法：A.采取

26、局部置換策略B. 把工作集算法融入到處理機調(diào)度中調(diào)入作業(yè)之前，檢查每個進(jìn)程在內(nèi)存的駐留頁面是否足夠多。C. 利用“ L=S ”準(zhǔn)則調(diào)節(jié)缺頁率 P172D. 選擇暫停的進(jìn)程：掛起若干進(jìn)程第六章（一） I/O 系統(tǒng)1.I/O 系統(tǒng)的層次結(jié)構(gòu)：從下往上：硬件 - 中斷處理程序 - 設(shè)備驅(qū)動程序 - 設(shè)備獨立性軟件 - 用戶層軟件2.I/O 系統(tǒng)的上、下接口： I/O 系統(tǒng)接口、軟件/硬件接口（下面就是硬件部分了）3.I/O 系統(tǒng)的分層：從下往上：中斷處理程序 - 設(shè)備驅(qū)動程序 - 設(shè)備獨立性軟 件4.I/O 系統(tǒng)接口：有 3 種（ 1 ）塊設(shè)備接口A. 塊設(shè)備：以數(shù)據(jù)塊為單位（磁盤）特點：傳輸速率高

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

28、A. 設(shè)備控制器與 CPU 的接口（并行）：數(shù)據(jù)總線 -DR: 內(nèi)存 設(shè)備-C/S: 狀態(tài)：設(shè)備 -CPU啟動： CPU- 設(shè)備地址總線：設(shè)備名 - 譯碼電路（ I/O 邏輯） - 接口控制總線：操作碼 - 譯碼電路 -CRB. 設(shè)備控制器與設(shè)備的接口（串行）：數(shù)據(jù)線：設(shè)備 DR狀態(tài)線：設(shè)備 -C/S控制線： C/S- 設(shè)備C. 譯碼電路（I/O 邏輯）：實現(xiàn)對設(shè)備的控制上面 2 個譯碼功能 +并行-（分解） - 設(shè)備控制器地址（即要選哪個設(shè)備） -地址線-設(shè)備控制器-I/O 邏輯進(jìn)行譯碼- 選中設(shè)備（ 3）設(shè)備 -DR: 數(shù)據(jù)準(zhǔn)備； DR- 內(nèi)存：數(shù)據(jù)傳送（ 4）設(shè)備控制器的功能：A. 接收

29、和識別命令B. 數(shù)據(jù)交換C. 標(biāo)識和報告設(shè)備的狀態(tài)D. 地址識別（設(shè)備控制器可連接多個設(shè)備、其里面也有很大寄存器，都需 要地址）E. 數(shù)據(jù)緩沖區(qū)F 差錯控制3.I/O 通道（特殊處理機）（ 1）在 CPU 與設(shè)備控制器之間 目的：建立獨立的 I/O 操作（ 2）過程： CPU 發(fā) I/O 指令- 通道- 內(nèi)存中取對應(yīng)的通道程序并執(zhí)行 - 完 成后，向 CPU 發(fā)中斷信號（ 3）通道與 CPU 共享內(nèi)存（其通道程序放在內(nèi)存）（ 4 ）通道的類型：A. 字節(jié)多路通道：每個字通道連接一個設(shè)備，按時間片輪轉(zhuǎn)共享主通道 適合低速設(shè)備B. 數(shù)組選擇通道：每次只允許一個設(shè)備傳輸數(shù)據(jù)C. 數(shù)組多路通道（三）設(shè)

30、備驅(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ū)動程序的特點：A. 用匯編語言編寫B(tài).允許可重入3.設(shè)備處理方式：A. 每類設(shè)備一個進(jìn)程來控制B. 整個系統(tǒng)一個進(jìn)程或一個輸入一個輸出共 2 個進(jìn)程C. 不設(shè)置進(jìn)程（常用）4. 設(shè)備驅(qū)動程序的處理過程： 將抽象要求轉(zhuǎn)換為具體要求 - 對服務(wù)請求進(jìn)行校 驗 -檢查設(shè)備的狀態(tài) - 傳送必要的參數(shù)- 啟動 I/O 設(shè)備啟動后，驅(qū)動程序把控制返回給 I/O 系統(tǒng)，自己阻

31、塞起來， 直到中斷到來被喚 醒I/O 操作是在設(shè)備控制器的控制下進(jìn)行 ，實現(xiàn)處理機與 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)過 CPUB. DMA 控制器：三部分組成：DMA 控制器與主機的接口、與設(shè)備的接口、I/O 控制邏輯含有 4 個寄存器：數(shù)據(jù)寄存器 DR、控制/狀態(tài)寄存器 CR、數(shù)據(jù)計數(shù)