【正文】 B: A: 18 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 地址變換機(jī)構(gòu) ? 在分頁(yè)系統(tǒng)的地址變換機(jī)構(gòu)的基礎(chǔ)上，增加缺頁(yè)中斷產(chǎn)生和處理并頁(yè)面置換功能而構(gòu)成 ? 地址變換過(guò)程要領(lǐng) ? 從頁(yè)表找到對(duì)應(yīng)分頁(yè)的頁(yè)表項(xiàng)獲悉該頁(yè)尚未調(diào)入內(nèi)存時(shí)，應(yīng)產(chǎn)生缺頁(yè)中斷，請(qǐng)求操作系統(tǒng)從外存把該頁(yè)調(diào)入內(nèi)存 ? 關(guān)于快表和頁(yè)表的檢索及表項(xiàng)修改 Steps in Handling a Page Fault 20 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 請(qǐng)求分頁(yè)系統(tǒng)地址變換過(guò)程 程序請(qǐng)求訪問(wèn)一頁(yè) CPU檢索快表 找到否？ 訪問(wèn)頁(yè)表 是 否 頁(yè)在內(nèi)存？ 否 產(chǎn)生缺頁(yè)中斷請(qǐng)求調(diào)頁(yè) 是 修改頁(yè)表對(duì)應(yīng)頁(yè)表項(xiàng)訪問(wèn)字段和修改位 形成物理地址 地址變換結(jié)束 頁(yè)號(hào)有效？ 是 否 越界 中斷 修改快表 硬件實(shí)現(xiàn)！ 21 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 缺頁(yè)中斷處理算法流程 從外存中找到缺頁(yè) 內(nèi)存滿否？ 從內(nèi)存選擇某頁(yè)換出 是 否 該頁(yè)被修改否？ 是 將該頁(yè)寫(xiě)回外存 否 命令 CPU從外存讀取缺頁(yè) 啟動(dòng) I/O硬件 將缺頁(yè)從外存換入內(nèi)存 修改頁(yè)表相應(yīng)表項(xiàng) 狀態(tài)位及物理塊號(hào) 返回 恢復(fù) CPU現(xiàn)場(chǎng) 阻塞當(dāng)前執(zhí)行程序和響應(yīng)缺頁(yè)中斷處理 保護(hù) CPU現(xiàn)場(chǎng) 22 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 請(qǐng)求分頁(yè)存儲(chǔ)管理方式 ?除了硬件支持外，更多管理任務(wù)需要操作系統(tǒng)軟件的支持。不同的操作系統(tǒng)可以有非常不同的設(shè)計(jì)！ 23 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 請(qǐng)求分頁(yè)存儲(chǔ)管理方式 請(qǐng)求分頁(yè)中的硬件支持 內(nèi)存分配策略和分配算法 調(diào)頁(yè)策略 頁(yè)面置換算法 24 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 最小物理塊數(shù)的確定 ? 保證進(jìn)程正常運(yùn)行所需的最少物理塊數(shù) ? 若系統(tǒng)為某進(jìn)程分配的物理塊數(shù)少于此值，進(jìn)程將無(wú)法正常運(yùn)行 ? 不同于使進(jìn)程有效工作所需的物理塊數(shù) ? 與計(jì)算機(jī)的硬件結(jié)構(gòu)有關(guān)，并取決于指令的格式（操作數(shù)個(gè)數(shù)）、功能和尋址方式（直接 /間接） 25 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 物理塊分配算法 ? 平均分配算法 ? 將系統(tǒng)可供分配的物理塊平均分配 ? 按比例分配算法 ? BlockOfPk = max{minBlocks, Blocks ? PagesOfPk/?PagesOfPi} ? 考慮優(yōu)先權(quán)的分配算法 ? 照顧重要或緊迫的作業(yè)能盡快完成 26 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 物理塊分配與置換策略 ? 固定分配局部置換 ? 為每個(gè)進(jìn)程分配一固定頁(yè)數(shù)的內(nèi)存空間，在整個(gè)運(yùn)行期間都不再改變 ? 可變分配全局置換 ? 系統(tǒng)設(shè)立一個(gè)空閑物理塊隊(duì)列 ? 可變分配局部置換 ? 依據(jù)缺頁(yè)率酌情增加或減少物理塊 27 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 請(qǐng)求分頁(yè)存儲(chǔ)管理方式 請(qǐng)求分頁(yè)中的硬件支持 內(nèi)存分配策略和分配算法 調(diào)頁(yè)策略 頁(yè)面置換算法 28 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 何時(shí)調(diào)入頁(yè)面 ? 預(yù)調(diào)頁(yè)策略 ? 將那些預(yù)計(jì)在不久之后便會(huì)被訪問(wèn)的程序或數(shù)據(jù)所在的頁(yè)面，預(yù)先調(diào)入內(nèi)存 ? 以預(yù)測(cè)為基礎(chǔ)，主要用于進(jìn)程首次調(diào)入 ? 請(qǐng)求調(diào)頁(yè)策略 ? 當(dāng)進(jìn)程在運(yùn)行中需要訪問(wèn)某部分程序和數(shù)據(jù)時(shí)，若發(fā)現(xiàn)其所在的頁(yè)面不在內(nèi)存，應(yīng)立即提出請(qǐng)求，由系統(tǒng)將其所需頁(yè)面調(diào)入內(nèi)存；易于實(shí)現(xiàn)但系統(tǒng)開(kāi)銷大 29 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 何處調(diào)入頁(yè)面 ? 對(duì)換區(qū)空間充分 ? 進(jìn)程運(yùn)行前，便須將與該進(jìn)程有關(guān)的文件，從文件區(qū)拷貝到對(duì)換區(qū) ? 對(duì)換區(qū)空間不足 ? 文件是否修改分別處理 ? UNIX方式 ? 凡未運(yùn)行過(guò)的頁(yè)面都應(yīng)從文件區(qū)調(diào)入，而對(duì)于曾運(yùn)行過(guò)又被換出到對(duì)換區(qū)的頁(yè)面則從對(duì)換區(qū)調(diào)入 30 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 頁(yè)面調(diào)入過(guò)程 ? 缺頁(yè)中斷發(fā)生 ? 程序所訪問(wèn)的頁(yè)面不在內(nèi)存時(shí)產(chǎn)生缺頁(yè)中斷并轉(zhuǎn)入缺頁(yè)中斷處理程序 ? 根據(jù)頁(yè)表外存地址調(diào)入所缺頁(yè)面 ? 頁(yè)表項(xiàng)外存地址（物理盤(pán)塊號(hào)） ? 內(nèi)存不足置換 ? 頁(yè)面淘汰算法 ? 是否重寫(xiě)磁盤(pán) 31 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 請(qǐng)求分頁(yè)存儲(chǔ)管理方式 請(qǐng)求分頁(yè)中的硬件支持 內(nèi)存分配策略和分配算法 調(diào)頁(yè)策略 頁(yè)面置換算法 32 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 頁(yè)面置換算法 抖動(dòng)與缺頁(yè)率 最佳置換算法 先進(jìn)先出置換算法 最近最久未使用置換算法 Clock置換算法 最少使用置換算法 頁(yè)面緩沖算法 33 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 抖動(dòng)與缺頁(yè)率 ? 抖動(dòng)的定義 ? 如果所用置換算法不當(dāng)，便可能導(dǎo)致這樣一種情形：剛被換出的頁(yè)面很快又被訪問(wèn)，需重新調(diào)入，為此，又需再選一頁(yè)換出；而此剛被換出的頁(yè)面，不久也被訪問(wèn)，故又需將它調(diào)入，如此頻繁地更換頁(yè)面，以致一個(gè)進(jìn)程在運(yùn)行中把大部分的時(shí)間耗費(fèi)在頁(yè)面置換的工作上，稱該進(jìn)程發(fā)生了抖動(dòng)（或稱之為顛簸） ? 缺頁(yè)率 ? 缺頁(yè)率 = 缺頁(yè)中斷次數(shù) /頁(yè)面訪問(wèn)次數(shù) 34 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 頁(yè)面置換算法 抖動(dòng)與缺頁(yè)率 最佳置換算法 先進(jìn)先出置換算法 最近最久未使用置換算法 Clock置換算法 最少使用置換算法 頁(yè)面緩沖算法 35 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 最佳置換算法 ? 基本思想 ? 選擇永不使用或是在最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)（即距現(xiàn)在最長(zhǎng)時(shí)間才會(huì)被訪問(wèn)）的頁(yè)面淘汰出內(nèi)存 ? 評(píng)價(jià) ? 理想化算法，具有最好性能（對(duì)于固定分配頁(yè)面方式，本法可保證獲得最低的缺頁(yè)率），但實(shí)際上卻難于實(shí)現(xiàn)，故主要用于算法評(píng)價(jià)參照 36 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 最佳置換算法舉例說(shuō)明 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 7 7 2 2 2 2 2 2 2 2 2 2 2 2 2 2 7 7 7 0 0 0 0 0 0 4 4 4 0 0 0 0 0 0 0 0 0 0 1 1 1 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1 ? 某進(jìn)程分配獲得三個(gè)物理塊 ? 缺頁(yè)中斷次數(shù)為 6次，缺頁(yè)率 30% 頁(yè)面訪問(wèn)序列 內(nèi)存頁(yè)面分布情況 頁(yè)面預(yù)先裝入 37 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 頁(yè)面置換算法 抖動(dòng)與缺頁(yè)率 最佳置換算法 先進(jìn)先出置換算法 最近最久未使用置換算法 Clock置換算法 最少使用置換算法 頁(yè)面緩沖算法 38 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 先進(jìn)先出置換算法 ? 基本思想 ? 選擇最先進(jìn)入內(nèi)存即在內(nèi)存駐留時(shí)間最久的頁(yè)面換出到外存 ? 進(jìn)程已調(diào)入內(nèi)存的頁(yè)面按進(jìn)入先后次序鏈接成一個(gè)隊(duì)列，并設(shè)置替換指針以指向最老頁(yè)面 ? 評(píng)價(jià) ? 簡(jiǎn)單直觀，但不符合進(jìn)程實(shí)際運(yùn)行規(guī)律，性能較差，故實(shí)際應(yīng)用極少 39 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7 7 7 2 2 2 2 4 4 4 0 0 0 0 0 0 0 7 7 7 0 0 0 0 3 3 3 2 2 2 2 2 1 1 1 1 1 0 0 1 1 1 1 0 0 0 3 3 3 3 3 2 2 2 2 2 1 ? 某進(jìn)程分配獲得三個(gè)物理塊 ? 缺頁(yè)中斷次數(shù)為 12次，缺頁(yè)率 60% 頁(yè)面訪問(wèn)序列 內(nèi)存頁(yè)面分布情