操作系統(tǒng)總復(fù)習(xí)

1、 總復(fù)習(xí) 2015-11 2013級(jí)軟件3-4 考試時(shí)間與題型 考試時(shí)間：12.3，第14周周四上午10：10-12：00 考試題型： 選擇題（20分），20個(gè)選擇，每個(gè)選擇1分 填空題（20分），20個(gè)空，每空1分 簡(jiǎn)答題（30分），6道題，每題5分，每章1題 綜合題（30分），3道題， 第二章：用信號(hào)量解決進(jìn)程同步、互斥問(wèn)題 第三章：處理機(jī)調(diào)度/銀行家算法 第四章/第五章：地址 變換/頁(yè)面置換算法 總分：100分（閉卷，考試允許帶計(jì)算器，所有計(jì)算結(jié)果精確至小數(shù)點(diǎn)后2位） 考試范圍 第一章 操作系統(tǒng)引論 第二章 進(jìn)程的描述與控制 第三章 處理機(jī)調(diào)度與死鎖 第四章 存儲(chǔ)器管理 第五章 虛擬存儲(chǔ)

2、器 第六章 輸入輸出系統(tǒng) 第七章 文件管理 第八章 磁盤(pán)存儲(chǔ)器的管理 第1章 操作系統(tǒng)引論 操作系統(tǒng)的目標(biāo) 有效性、方便性、可擴(kuò)展性、開(kāi)放性 操作系統(tǒng)的作用 用戶(hù)觀點(diǎn)、資源管理者、虛擬機(jī) 操作系統(tǒng)的發(fā)展過(guò)程 脫機(jī)/聯(lián)機(jī)輸入輸出技術(shù) 多道程序設(shè)計(jì)技術(shù)，解決了哪 二對(duì)矛盾 為什么引入分時(shí)系統(tǒng) 為什么引入實(shí)時(shí)系統(tǒng) 操作系統(tǒng)四大特征 并發(fā)、共享、虛擬、異步 并發(fā)與并行概念 五大功能 處理機(jī)管理、存儲(chǔ)器管理、設(shè)備管理、文件管理、提供接口 接口類(lèi)型：用戶(hù)接口（CLI、GUI）、程序員接口（API/系統(tǒng)調(diào)用） OS結(jié)構(gòu) 微內(nèi)核結(jié)構(gòu)：所采用的技術(shù)，微內(nèi)核中包括什么內(nèi)容 第2章 進(jìn)程的描述與控制 程序并發(fā)執(zhí)行時(shí)

3、的特征（間斷、失去封閉、不可再現(xiàn)） 并發(fā)與并行的概念 進(jìn)程相關(guān)的概念 為什么要引入進(jìn)程 進(jìn)程由什么組成的（程序段+數(shù)據(jù)段+PCB） 為什么說(shuō)PCB是進(jìn)程存在的唯一標(biāo)志 進(jìn)程的三種基本狀態(tài)，它們之間如何進(jìn)行轉(zhuǎn)換 進(jìn)程的同步與互斥 臨界資源、臨界區(qū)的概念 忙等的概念 信號(hào)量：記錄型信號(hào)量的含義、信號(hào)量集 應(yīng)用信號(hào)量機(jī)制解決進(jìn)程的同步與互斥問(wèn)題（前趨圖、生產(chǎn)者與消費(fèi)者、哲學(xué)家進(jìn)餐、讀者-寫(xiě)者） 進(jìn)程通信（4種高級(jí)通信） 管程 管程的組成（4部分） 線程 線程的特點(diǎn) 第3章 處理機(jī)調(diào)度與死鎖 調(diào)度層次 低級(jí)調(diào)度：進(jìn)程調(diào)度 高級(jí)調(diào)度：作業(yè)調(diào)度 中級(jí)高度：內(nèi)存調(diào)度 處理機(jī)調(diào)度算法 FCFS、SJF、高響應(yīng)

4、比優(yōu)先調(diào)度、RR，要求知道每種算法的調(diào)度規(guī)則、調(diào)度方式與偏好性，會(huì)計(jì)算周轉(zhuǎn)時(shí)間與帶權(quán)周轉(zhuǎn)時(shí)間 實(shí)時(shí)調(diào)度算法 實(shí)時(shí)系統(tǒng)調(diào)度能力 最低松弛度優(yōu)先算法（調(diào)度規(guī)則、松弛度） 死鎖的相關(guān)概念 死鎖的定義與產(chǎn)生死鎖的原因 產(chǎn)生死鎖的4個(gè)必要條件 預(yù)防死鎖的方法 靜態(tài)資源分配法、資源剝奪法、有序資源分配法 避免死鎖 銀行家算法 并非所有不安全狀態(tài)都是死鎖狀態(tài)，但只要系統(tǒng)處于安全狀態(tài)便可避免死鎖狀態(tài)。 檢測(cè)并解除死鎖 檢測(cè)死鎖：資源分配圖完全簡(jiǎn)化法 解除死鎖：剝奪資源與撤消進(jìn)程 第45章（虛擬）存儲(chǔ)器管理 程序的裝入與鏈接 裝入：絕對(duì)、可重定位、動(dòng)態(tài)運(yùn)行 鏈接：靜態(tài)、裝入時(shí)動(dòng)態(tài)、運(yùn)行時(shí)動(dòng)態(tài) 重定位：重定位、靜

5、態(tài)重定位、動(dòng)態(tài)重定位 地址空間：作業(yè)地址空間與物理地址空間 動(dòng)態(tài)分區(qū)分配算法 首次適應(yīng) 循環(huán)首次 最佳 最壞 空閑分區(qū)的分配與回收算法 基本分頁(yè)存儲(chǔ)管理 頁(yè)面、頁(yè)框、頁(yè)表的概念 邏輯地址結(jié)構(gòu) 地址變換機(jī)構(gòu) 快表 基本分段存儲(chǔ)管理 為什么要引入分段存儲(chǔ)管理方式 邏輯地址結(jié)構(gòu) 地址變換機(jī)構(gòu) 虛擬存儲(chǔ)器基本概念 引入虛擬存儲(chǔ)器的目的 虛擬存儲(chǔ)器的特征 整體對(duì)換VS虛擬存儲(chǔ)器 請(qǐng)求分頁(yè)存儲(chǔ)管理 系統(tǒng)需要的硬件支持 系統(tǒng)需要的軟件支持 物理塊分配與置換的策略 缺頁(yè)中斷與一般中斷的不同 抖動(dòng) 頁(yè)面置換算法（OPT、FIFO、LRU、CLOCK） 第6章 輸入輸出系統(tǒng) I/O系統(tǒng) 設(shè)備控制器 設(shè)備控制器是C

6、PU與I/O設(shè)備之間的接口 功能：完成設(shè)備與主機(jī)間的連接和通信 分類(lèi)：字符設(shè)備與塊設(shè)備，典型的設(shè)備是什么 通道 概念，作用：實(shí)現(xiàn)內(nèi)存與外設(shè)之間的信息傳輸 I/O控制方式：程序、中斷、DMA、通道 中斷、DMA控制方式適用于何種類(lèi)型的設(shè)備 緩沖管理 引入緩沖區(qū)的目的 設(shè)備獨(dú)立性的概念 什么是設(shè)備獨(dú)立性，如何實(shí)現(xiàn) 設(shè)備驅(qū)動(dòng) 設(shè)備的分配 數(shù)據(jù)結(jié)構(gòu) 獨(dú)占設(shè)備的分配 SPOOLing技術(shù)及組成 磁盤(pán)存儲(chǔ)器的調(diào)度 磁盤(pán)調(diào)度算法（FCFS；SSTF；SCAN；CSCAN） 第7章 文件管理 文件系統(tǒng)的目標(biāo) 文件的邏輯結(jié)構(gòu) 邏輯結(jié)構(gòu)：概念及分類(lèi)（順序文件、索引文件、索引順序文件） 目錄管理 對(duì)目錄管理的要求

7、第8章 磁盤(pán)存儲(chǔ)器的管理 文件的物理結(jié)構(gòu) 物理結(jié)構(gòu)：概念及分類(lèi)（連續(xù)分配方式、鏈接分配、索引分配） 文件存儲(chǔ)空間的管理 位示圖法 磁盤(pán)容錯(cuò)技術(shù) 第一、二級(jí)容錯(cuò)技術(shù)第1章 作業(yè)一、選擇題1. 操作系統(tǒng)中采用多道程序設(shè)計(jì)技術(shù)提高了CPU和外部設(shè)備的 A. 利用率B. 可靠性C. 穩(wěn)定性D. 兼容性2. 在操作系統(tǒng)中，并發(fā)性是指若干事件 發(fā)生。A. 在同一時(shí)刻B. 一定在不同時(shí)刻C. 在某一時(shí)間間隔內(nèi)D. 依次在不同時(shí)間間隔內(nèi)3. 訂購(gòu)機(jī)票系統(tǒng)處理各個(gè)終端的服務(wù)請(qǐng)求，處理后通過(guò)終端回答用戶(hù)，所以它是一個(gè) 。A. 分時(shí)系統(tǒng)B. 多道批處理系統(tǒng)C. 計(jì)算機(jī)網(wǎng)絡(luò)D. 實(shí)時(shí)信息處理系統(tǒng)4. 下列選擇中， 不

8、是操作系統(tǒng)關(guān)心的主要問(wèn)題。A. 管理計(jì)算機(jī)裸機(jī)B. 設(shè)計(jì)、提供用戶(hù)程序與計(jì)算機(jī)硬件系統(tǒng)的界面C. 管理計(jì)算機(jī)系統(tǒng)資源D. 高級(jí)程序設(shè)計(jì)語(yǔ)言的編譯器5. 在操作系統(tǒng)中，處理機(jī)負(fù)責(zé)對(duì)進(jìn)程進(jìn)行管理和調(diào)度，對(duì)系統(tǒng)中的信息進(jìn)行管理的部分通常稱(chēng)為 。A. 數(shù)據(jù)庫(kù)系統(tǒng)B. 軟件系統(tǒng)C. 文件系統(tǒng)D. 檢索系統(tǒng)二、簡(jiǎn)答題1、設(shè)計(jì)現(xiàn)代OS的主要目標(biāo)是什么？2、何謂脫機(jī)I/O和聯(lián)機(jī)I/O？3、實(shí)現(xiàn)分時(shí)系統(tǒng)的關(guān)鍵問(wèn)題是什么？應(yīng)如何解決？4、OS有哪幾大特征？其最基本的特征是什么？5、是什么原因使操作系統(tǒng)具有異步性特征？6、何謂微內(nèi)核技術(shù)？在微內(nèi)核中通常提供了哪些功能？三、綜合題1、設(shè)內(nèi)存中有三道程序A、B、C，它們

9、按A、B、C的優(yōu)先次序執(zhí)行。它們的計(jì)算和I/O操作時(shí)間如表所示（單位：ms）。三道程序的操作時(shí)間 程序操作ABC計(jì)算306020I/O403040計(jì)算101020假設(shè)三道程序使用相同設(shè)備I/O操作，即程序是以串行方式使用設(shè)備，調(diào)度程序的執(zhí)行時(shí)間忽略不計(jì)，試計(jì)算出在單道和多道兩種情況下，完成這三道程序各要花多少時(shí)間？要求畫(huà)出多道運(yùn)行的時(shí)序圖。（假定在多道方式下采用的是基于優(yōu)先級(jí)的非搶占調(diào)度程序）第2章作業(yè)1、進(jìn)程之間存在著哪幾種制約關(guān)系？各是什么原因引起的？下列活動(dòng)分別屬于哪種制約關(guān)系？（1）若干同學(xué)去圖書(shū)館借書(shū)；（2）兩隊(duì)舉行籃球比賽；（3）流水線生產(chǎn)的各道工序；（4）商品生產(chǎn)和社會(huì)消費(fèi)。2、

10、已知一個(gè)求值公式(A23B)/(B+5A)，若A、B已賦值，試畫(huà)出該公式求值過(guò)程的前趨圖，并使用信號(hào)量描述這些前趨關(guān)系。3、試用信號(hào)量實(shí)現(xiàn)課件中司機(jī)與售票員進(jìn)程的同步關(guān)系課后作業(yè)一、簡(jiǎn)答題：1、什么是前趨圖？為什么要引入前趨圖？2、程序并發(fā)執(zhí)行時(shí)為什么會(huì)失去封閉性和可再現(xiàn)性？3、試說(shuō)明PCB的作用，為什么說(shuō)PCB是進(jìn)程存在的唯一標(biāo)志？4、同步機(jī)構(gòu)應(yīng)遵循哪些基本準(zhǔn)則？5、何謂“忙等”？它有什么缺點(diǎn)？6、試從物理概念上說(shuō)明記錄型信號(hào)量wait和signal。7、在生產(chǎn)者消費(fèi)者問(wèn)題中，分別分析如果缺少了signal(full)或signal(empty)，對(duì)執(zhí)行結(jié)果將會(huì)有何影響？8、我們?yōu)槟撑R界資源

11、設(shè)置一把鎖W，當(dāng)W=1時(shí)表示關(guān)鎖；當(dāng)W=0時(shí)表示鎖已經(jīng)打開(kāi)，試寫(xiě)出開(kāi)鎖和關(guān)鎖原語(yǔ)，并利用它們?nèi)?shí)現(xiàn)互斥。9、試說(shuō)明管程由哪幾部分組成，為什么要引入條件變量？10、為什么要引入信號(hào)量集? 信號(hào)量集中有哪兩種操作？11、當(dāng)前有哪幾種高級(jí)通信機(jī)制？12、為什么引入進(jìn)程？為什么引入線程？ 13、試說(shuō)明線程具有哪些屬性？14、何謂用戶(hù)級(jí)線程和內(nèi)核支持線程？打印進(jìn)程單緩沖區(qū)計(jì)算進(jìn)程綜合題：1、如圖所示，有一計(jì)算進(jìn)程和一打印進(jìn)程，它們共享一個(gè)單緩沖區(qū)，計(jì)算進(jìn)程不斷地計(jì)算出結(jié)果并將它放入單緩沖區(qū)中，打印進(jìn)程則負(fù)責(zé)從單緩沖區(qū)中取出每一個(gè)結(jié)果進(jìn)行打印。請(qǐng)用信號(hào)量來(lái)實(shí)現(xiàn)它們的同步關(guān)系。2、試用信號(hào)量解決讀者寫(xiě)者問(wèn)題

12、，使得寫(xiě)者與讀者優(yōu)先級(jí)根據(jù)到達(dá)順序確定（讀寫(xiě)平等）。在該解決方案中，請(qǐng)加入閱覽室最多只許多N位讀者的限制條件。然后用到達(dá)序列：R1, R2, W1, R3, R4, W2進(jìn)行測(cè)試列出類(lèi)似如下測(cè)試結(jié)果進(jìn)程行為rmutex=1wmutex=1Readcount=0狀態(tài)備注R1到達(dá)rmutex=0rmutex=1wmutex=0Readcount=1執(zhí)行/就緒第1位讀者3、請(qǐng)給出一個(gè)寫(xiě)者優(yōu)先的“讀者寫(xiě)者”問(wèn)題的算法描述，實(shí)現(xiàn)比較溫和的寫(xiě)者優(yōu)先策略。然后用到達(dá)序列：R1, R2, W1, R3, R4, W2進(jìn)行測(cè)試列出類(lèi)似如下測(cè)試結(jié)果進(jìn)程行為rmutex=1wmutex=1Readcount=0狀態(tài)

13、備注R1到達(dá)rmutex=0rmutex=1wmutex=0Readcount=1執(zhí)行/就緒第1位讀者4、桌上有一只能容納一個(gè)水果的盤(pán)子；爸爸專(zhuān)向盤(pán)子中放蘋(píng)果(apple)，媽媽專(zhuān)向盤(pán)子中放桔子(orange)，一個(gè)兒子專(zhuān)等吃盤(pán)子中的桔子，一個(gè)女兒專(zhuān)等吃盤(pán)子里的蘋(píng)果，1）試用信號(hào)量實(shí)現(xiàn)他們的同步關(guān)系；2）如果有兩個(gè)家庭的爸爸、媽媽、兒子、女兒和二只盤(pán)子呢？會(huì)需要專(zhuān)門(mén)的實(shí)現(xiàn)嗎？ 5、請(qǐng)用counter作為臨界資源的方案解決生產(chǎn)者消費(fèi)者問(wèn)題？這種解決方案與書(shū)本上的解決方案相比，有何缺點(diǎn)第三章1、某進(jìn)程被喚醒后立即投入運(yùn)行，我們就說(shuō)這個(gè)系統(tǒng)采用的是剝奪調(diào)度方法，對(duì)嗎？為什么？10”2、什么是高響應(yīng)比

14、優(yōu)先調(diào)度算法，它采用何種調(diào)度方式？10”3、假設(shè)一個(gè)系統(tǒng)中有4個(gè)進(jìn)程，它們的到達(dá)時(shí)間和服務(wù)時(shí)間如表所示，忽略I/O以及其他開(kāi)銷(xiāo)時(shí)間，若分別按先來(lái)先服務(wù)（FCFS）、非搶占及搶占的短進(jìn)程優(yōu)先（SPF）、高響應(yīng)比優(yōu)先（HRRN）、時(shí)間片輪轉(zhuǎn)（RR，時(shí)間片=1）、多級(jí)反饋隊(duì)列調(diào)度算法（MFQ，第i級(jí)隊(duì)列的時(shí)間片=2i-1）進(jìn)行CPU調(diào)度，請(qǐng)給出各進(jìn)程的完成時(shí)間、周轉(zhuǎn)時(shí)間、帶權(quán)周轉(zhuǎn)時(shí)間、平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間，填入下表中（搶占式算法要求畫(huà)出調(diào)度時(shí)序圖，HRRN算法要求列出調(diào)度時(shí)的響應(yīng)比）。30”進(jìn)程到達(dá)時(shí)間服務(wù)時(shí)間A05B12C39D67算法時(shí)間進(jìn)程平均時(shí)間ABCDFCFS完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)

15、周轉(zhuǎn)時(shí)間SPF（非搶占）完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間SPF（搶占）完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間RR（q=1）完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間MFQ（q=2i-1）完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間作業(yè)號(hào)到達(dá)時(shí)間運(yùn)行時(shí)間開(kāi)始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間調(diào)度依據(jù)平均周轉(zhuǎn)時(shí)間為：平均帶權(quán)周轉(zhuǎn)時(shí)間為：4、在一個(gè)軟實(shí)時(shí)系統(tǒng)中有四個(gè)周期性任務(wù)，任務(wù)A、B、C、D分別要求每50ms、100ms、200ms、250ms執(zhí)行一次，假定A、B、C、D的執(zhí)行時(shí)間分別為35ms、20ms、10ms與x ms，那么要使得這個(gè)實(shí)時(shí)系統(tǒng)為可調(diào)度的，x的最大值為多少？（要求列出計(jì)算公式）10”5、什么是最低松弛度優(yōu)先調(diào)度算法？它采

16、用何種調(diào)度方式？搶占時(shí)機(jī)是什么？10”6、若有4個(gè)周期性任務(wù)，任務(wù)A要求每30ms執(zhí)行一次，執(zhí)行時(shí)間為15ms；任務(wù)B要求每50ms執(zhí)行一次，執(zhí)行時(shí)間為5ms；任務(wù)C要求每50ms執(zhí)行一次，執(zhí)行時(shí)間為15ms；任務(wù)D要求每100ms執(zhí)行一次，執(zhí)行時(shí)間為10ms，應(yīng)如何按最低松弛度優(yōu)先算法對(duì)它們進(jìn)行CPU調(diào)試？ （要求畫(huà)出0-150ms時(shí)段的調(diào)度時(shí)序圖，并列出每次切換時(shí)每個(gè)任務(wù)的松弛度）20”7、何謂死鎖？產(chǎn)生死鎖的原因和必要條件是什么？10”8、3個(gè)進(jìn)程共享4個(gè)同類(lèi)型的資源，每個(gè)進(jìn)程最大需要2個(gè)資源，請(qǐng)問(wèn)該系統(tǒng)是否會(huì)因?yàn)楦?jìng)爭(zhēng)該資源而死鎖？10”9、不安全狀態(tài)是否必然導(dǎo)致系統(tǒng)進(jìn)入死鎖狀態(tài)？舉例說(shuō)

17、明。10”10、在銀行家算法中，若出現(xiàn)下面的資源分配情況： 30”P(pán)rocessAllocationNeedAvailableP00 0 3 20 0 1 21 5 2 2P11 0 0 01 6 5 0P21 3 5 42 3 5 6P30 1 3 20 5 5 2P40 0 1 40 6 5 8試問(wèn)：1）該狀態(tài)是否安全（要求列出安全性算法檢查表）？ 2）若進(jìn)程P2提出請(qǐng)求Request(1,2,2,2)后，系統(tǒng)能否將資源分配給它（要求根據(jù)分配算法列出檢查過(guò)程）？ 3）如果系統(tǒng)立即滿(mǎn)足P2的上述請(qǐng)求，請(qǐng)問(wèn)，系統(tǒng)是否立即進(jìn)入死鎖狀態(tài)，請(qǐng)說(shuō)明原因？11、進(jìn)程資源的使用情況和可用情況如表所示，請(qǐng)畫(huà)

18、出資源分配圖，并對(duì)資源圖進(jìn)行簡(jiǎn)化，這種情況下系統(tǒng)會(huì)發(fā)生死鎖嗎？20”進(jìn)程當(dāng)前分配數(shù)待分配的請(qǐng)求可用資源R1R2R3R1R2R3R1R2R3P1P2P3P423100131000110001001001000012、要使下表中描述的狀態(tài)安全，可用資源的最小數(shù)目應(yīng)為多少？（注意，問(wèn)題問(wèn)的是可用資源的數(shù)目，而不是存在的資源數(shù)）。10”進(jìn)程當(dāng)前分配數(shù)最大分配數(shù)R1R1P1P2P3P41132329713、在時(shí)間片輪轉(zhuǎn)法中，應(yīng)如何確定時(shí)間片的大??？10”14、在解決死鎖問(wèn)題的幾個(gè)方法中，哪種方法最易于實(shí)現(xiàn)？哪種方法能使資源利用率最高？10”第4-5章作業(yè)1、“整體對(duì)換從邏輯上也擴(kuò)充了內(nèi)存，因此也實(shí)現(xiàn)了虛

19、擬存儲(chǔ)器的功能”這種說(shuō)法是否正確？請(qǐng)說(shuō)明理由。2、什么叫靜態(tài)重定位，什么叫動(dòng)態(tài)重定位，它們分別與何種裝入方式相對(duì)應(yīng)？3、虛擬存儲(chǔ)器有哪些特征？其中最本質(zhì)的特征是什么？4、某系統(tǒng)采用頁(yè)式存儲(chǔ)管理策略，擁有邏輯空間32頁(yè)，每頁(yè)為2KB，擁有物理空間1MB。1）寫(xiě)出邏輯地址的格式。2）若不考慮訪問(wèn)權(quán)限等，進(jìn)程的頁(yè)表有多少項(xiàng)？每項(xiàng)至少有多少位？3）如果物理空間減少一半，頁(yè)表結(jié)構(gòu)應(yīng)相應(yīng)作怎樣的改變？5、對(duì)于下表所示的段表，請(qǐng)將邏輯地址（0，137）、（1，4000）、（2，3600）、（5，230）轉(zhuǎn)換成物理地址。段 表段號(hào)內(nèi)存地址段長(zhǎng)050K10KB160K3KB270K5KB3120K8KB4150

20、K4KB6、在請(qǐng)求分頁(yè)系統(tǒng)中，頁(yè)表應(yīng)包括哪些數(shù)據(jù)項(xiàng)？每項(xiàng)的作用是什么？7、在一個(gè)請(qǐng)求分頁(yè)系統(tǒng)中，假如一個(gè)作業(yè)的頁(yè)面走向?yàn)?、3、2、1、4、3、5、4、3、2、1、5，目前它還沒(méi)有任何頁(yè)裝入內(nèi)存，當(dāng)分配給該作業(yè)的物理塊數(shù)目M分別為3和4時(shí)，請(qǐng)分別計(jì)算采用OPT、LRU和FIFO頁(yè)面淘汰算法時(shí)，訪問(wèn)過(guò)程中所發(fā)生的缺頁(yè)次數(shù)和缺頁(yè)率，并比較所得結(jié)果。 （選做括號(hào)內(nèi)的內(nèi)容：根據(jù)本題的結(jié)果，請(qǐng)查找資料，說(shuō)明什么是Belady現(xiàn)象，在哪種置換算法中會(huì)產(chǎn)生Belady現(xiàn)象，為什么？）8、現(xiàn)有一請(qǐng)求調(diào)頁(yè)系統(tǒng)，頁(yè)表保存在寄存器中。若一個(gè)被替換的頁(yè)未被修改過(guò)，則處理一個(gè)缺頁(yè)中斷需要8ms；若被替換的頁(yè)已被修改過(guò)，

21、則處理一個(gè)缺頁(yè)中斷需要20ms。內(nèi)存存取時(shí)間為1us，訪問(wèn)頁(yè)表的時(shí)間可忽略不計(jì)。假定70%被替換的頁(yè)被修改過(guò)，為保證有效存取時(shí)間不超過(guò)2us，可接受的最大缺頁(yè)率是什么？ 第6章習(xí)題1、有哪幾種I/O控制方式？哪種I/O控制方式適用于字符設(shè)備？哪種I/O控制方式適用于塊設(shè)備？答：有四種：使用輪詢(xún)的可編程I/O方式；使用中斷的可編程I/O方式；直接存儲(chǔ)器訪問(wèn)（DMA） 方式；I/O通道控制方式。其中使用中斷的可編程I/O方式適用于字符設(shè)備，直接存儲(chǔ)器訪問(wèn)（DMA） 方式適用于塊設(shè)備。2、在設(shè)備管理中，為什么要引入緩沖區(qū)？答：在設(shè)備管理中，引入緩沖區(qū)的主要原因有以下四點(diǎn)：1）緩和CPU與I/O設(shè)備速

22、度不匹配的矛盾；2）減少對(duì)CPU的中斷頻率，放寬對(duì)CPU中斷響應(yīng)時(shí)間的限制；3）解決數(shù)據(jù)粒度不匹配的問(wèn)題；4）提高CPU和I/O設(shè)備之間的并行性。3、什么是設(shè)備的獨(dú)立性？引入設(shè)備的獨(dú)立性有什么優(yōu)點(diǎn)？如何實(shí)現(xiàn)設(shè)備的獨(dú)立性？答：設(shè)備的獨(dú)立性是指應(yīng)用程序獨(dú)立于具體使用的物理設(shè)備。引入設(shè)備獨(dú)立性可提高設(shè)備分配的靈活性和設(shè)備的利用率，使I/O重定向更易于實(shí)現(xiàn)。為實(shí)現(xiàn)設(shè)備的獨(dú)立性引入了邏輯設(shè)備和物理設(shè)備的概念，在應(yīng)用程序中使用的是邏輯名，而系統(tǒng)中還配備了一張將邏輯設(shè)備名轉(zhuǎn)換為物理設(shè)備名的數(shù)據(jù)結(jié)構(gòu)邏輯設(shè)備表（LUT），從而實(shí)現(xiàn)了應(yīng)用程序所使用的設(shè)備與具體的設(shè)備無(wú)關(guān)的設(shè)備獨(dú)立性。4、什么是SPOOLing技術(shù)

23、，它由哪幾部分組成？答：SPOOLing也稱(chēng)為假脫機(jī)技術(shù)，是指在多道程序的環(huán)境下，利用多道程序中的一道或兩道來(lái)模擬外圍控制機(jī)，從而在聯(lián)機(jī)的條件下實(shí)現(xiàn)同時(shí)外圍操作的技術(shù)。它由輸入/輸出井、輸入/輸出緩沖區(qū)、輸入/輸出進(jìn)程和井管理程序四部分組成。5、什么是SCAN算法，它是為了解決什么問(wèn)題而引入的？答：SCAN算法是一種磁盤(pán)調(diào)度算法，它選擇在磁頭當(dāng)前移動(dòng)方向上，與當(dāng)前磁頭所在磁道距離最近的，要求訪問(wèn)的磁道進(jìn)行訪問(wèn)，直至在當(dāng)前移動(dòng)方向上再無(wú)需要訪問(wèn)的磁道時(shí)，才反轉(zhuǎn)磁臂移動(dòng)方向，并執(zhí)行與前面相同的調(diào)度策略。SCAN算法的引入是為了避免出現(xiàn)進(jìn)程“饑餓”現(xiàn)象。6、為什么引入NStepSCAN算法，它是如何

24、解決上述問(wèn)題的？答：在SSTF、SCAN、CSCAN幾種磁盤(pán)調(diào)度算法中，都可能出現(xiàn)“磁臂粘著”現(xiàn)象，即有一個(gè)進(jìn)程或幾個(gè)進(jìn)程對(duì)某一磁道有較高的訪問(wèn)頻率，從而導(dǎo)致磁臂停留在某處不動(dòng)，壟斷了整個(gè)磁盤(pán)設(shè)備。NStepScan算法將磁盤(pán)請(qǐng)求隊(duì)列分成若干個(gè)長(zhǎng)度為N的子隊(duì)列，磁盤(pán)調(diào)度按FCFS算法依次處理這些子隊(duì)列。而每處理一個(gè)子隊(duì)列時(shí)又是按照SCAN算法。當(dāng)處理某子隊(duì)列時(shí)，又有新的磁盤(pán)I/O請(qǐng)求，便將新請(qǐng)求進(jìn)程放入其他隊(duì)列中，從而避免了粘臂現(xiàn)象。7、假定一磁盤(pán)有200個(gè)柱面，編號(hào)為0-199，在完成了磁道125處的請(qǐng)求后，當(dāng)前正在磁道143處為一個(gè)請(qǐng)求服務(wù)。若請(qǐng)求隊(duì)列的先后順序?yàn)?6，147，91，177，94，150，102，175，130，試分別采用FCFS、SSTF、SCAN算法完成上述請(qǐng)求，寫(xiě)出磁頭移動(dòng)的順序，并計(jì)算存取臂移動(dòng)總量。 （PPT最后一頁(yè)的課堂練習(xí)）FCFS算法SSTF算法SCAN算法CSCAN算法8657147414741474147611503150315039156130201752