【正文】 分配策略和分配算法 調(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)銷(xiāo)大 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è)面置換的工作上，稱(chēng)該進(jìn)程發(fā)生了抖動(dòng)（或稱(chē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è)面分布情況 頁(yè)面預(yù)先裝入 先進(jìn)先出置換算法舉例說(shuō)明 40 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 頁(yè)面置換算法 抖動(dòng)與缺頁(yè)率 最佳置換算法 先進(jìn)先出置換算法 最近最久未使用置換算法 Clock置換算法 最少使用置換算法 頁(yè)面緩沖算法 41 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 最近最久未使用置換算法 LRU ? Least Recently Used ? 基本思想 ? 以“最近的過(guò)去”作為“最近的將來(lái)”的近似，選擇最近一段時(shí)間最長(zhǎng)時(shí)間未被訪問(wèn)的頁(yè)面淘汰出內(nèi)存 ? 評(píng)價(jià) ? 適用于各種類(lèi)型的程序，性能較好，但需要較多的硬件支持 42 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 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 3 3 3 3 3 3 0 0 0 0 0 1 1 1 3 3 3 2 2 2 2 2 2 2 2 2 7 7 7 ? 某進(jìn)程分配獲得三個(gè)物理塊 ? 缺頁(yè)中斷次數(shù)為 9次，缺頁(yè)率 45% 頁(yè)面訪問(wèn)序列 內(nèi)存頁(yè)面分布情況 頁(yè)面預(yù)先裝入 最近最久未使用置換算法舉例說(shuō)明 43 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 LUR置換算法實(shí)現(xiàn) ? 軟件實(shí)現(xiàn)的問(wèn)題 ? 需要用操作系統(tǒng)軟件來(lái)更新頁(yè)面訪問(wèn)時(shí)間。實(shí)際上，用戶(hù)看到的大容量只是一種感覺(jué)，是虛的，故而得名虛擬存儲(chǔ)器。 56 2022年 8月 21日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 頁(yè)面緩沖算法 PBA ? 實(shí)現(xiàn)方法 ? 根據(jù)進(jìn)程缺頁(yè)率變化，修改一個(gè)進(jìn)程的可分配物理塊數(shù)。 ?每位價(jià)格