【正文】 態(tài)連接與共享的矛盾 ? 動態(tài)連接：修改連接字（代碼） ? 段的共享：要求純代碼（ pure code) ? 解決方法 ? 共享代碼分為“純段”和“雜段” ? 純段共享， ? 雜段私用。 ? 已分配段號：取出該段號，找到該段，查符號表得段內(nèi)地址； (段號，段內(nèi)地址 )?D, 0 ?L ? 未分配段號：將該段讀入內(nèi)存，分配段號， 填寫段表，填寫段名 段號對照表，轉(zhuǎn) (b) 匯編前： ... Load 1, [X]|Y … … ... [W]段 [X]段 … 1234 … … ... Y 示例 匯編后，連接前： 100: Load *1, 2|100。 ? 進程的某些程序段在進程運行期間可能根本不用，如某些錯誤處理分支； ? 互斥執(zhí)行的程序段沒有必要同時駐留內(nèi)存； ? 有些程序段執(zhí)行一次后不再用到。 分段與分頁的區(qū)別 ? 頁是信息的物理單位，頁的內(nèi)容通常 無完整意義 ；段是信息的邏輯單位，段的內(nèi)容具有 完整邏輯意義； ? 分頁是 靜態(tài) 的，分段是 動態(tài) 的； ? 頁的大小固定，段的大小取決于用戶所寫的程序； ? 分頁主要是為了節(jié)省內(nèi)存，分段主要為了滿足用戶需求； ? 分頁進程地址空間是 一維線性連續(xù)的 ，分段進程地址空間是二維 的； ? 分頁是對用戶 透明 的，而分段是用戶 可見 的。 則該進程在兩種編程方法下的缺頁次數(shù)分別為： 128*128+1和128+1。 設(shè)某請求分頁系統(tǒng)采用固定分配局部置換策略，一進程的頁面走向為 5，該進程分得 3個頁架，初始為空，試計算分別采用 FIFO、 LRU、 OPT置換算法時該進程訪問過程中所發(fā)生的缺頁次數(shù)和依次被換出的頁面。 這種改進的 SC法就是 Clock法。 Belady異常 近期最少使用（ LRU）算法 選擇最后一次訪問時間距離當(dāng)前時間最長的一頁并淘汰之。 3. 內(nèi)存分配策略和分配算法（續(xù)） ?物理塊的分配算法：采用 固定分配策略 時，可采用以下算法確定進程所能分配的物理塊。 缺頁中斷與常規(guī)中斷的不同之處： ? 常規(guī)中斷是在一條指令執(zhí)行完之后響應(yīng)與處理； ? 缺頁中斷是在指令執(zhí)行期間產(chǎn)生和處理中斷信號；且在一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁中斷。 ? 程序僅需將當(dāng)前要運行的 頁或段 裝入內(nèi)存即可運行； ? 運行時，如果需要訪問的 頁或段 不在內(nèi)存中（稱為 缺頁或缺段 ），由 OS提供的請求 調(diào)頁（段） 功能，將其調(diào)入內(nèi)存； ? 如果內(nèi)存已滿，則需按照預(yù)定的 置換策略 ，將暫時不用的 頁或段 調(diào)出外存，騰出足夠的存儲空間，在裝入所缺的 頁或段 。 6. 實分頁存儲管理方式小結(jié) ? 優(yōu)點： 內(nèi)存利用率高 ，解決了碎片問題； 便于管理。 d 頁表地址寄存器 頁表長度寄存器 邏輯地址 物理地址 主要問題：兩次內(nèi)存訪問 引入快表 – 加快地址轉(zhuǎn)換 快表使用聯(lián)想存儲器 （ associative memory，也稱為相聯(lián)存儲器） ，在 IBM系統(tǒng)中稱 TLB（ Translation lookaside buffers） ? 用途：保存正在運行進程的部分頁表項，以快速重定位 ? 快表表目內(nèi)容：頁號、內(nèi)存塊號、標(biāo)識位、淘汰位 ? 快表的特點：可按內(nèi)容并行查找 ? 快表命中率：已經(jīng)證明， 16個表目可達 90%以上。 2） 在實分頁存儲管理中 ， 進程運行時，全部頁面必須裝入內(nèi)存，但 邏輯上連續(xù)的各個頁所對應(yīng)的內(nèi)存塊可以不連續(xù) 。 ? Linux維護 6個鏈表 ，對應(yīng)長為 1 32個頁幀的內(nèi)存塊。此時，原先的 5個空閑區(qū)依次裝入了 5個作業(yè)，它們是：Jb(15k)， Jd(26k)， Ja(10k)， Je(180k)和 Jc(102k)。 （ 1） 最先 適應(yīng)分配算法 ?空閑分區(qū)表按 分區(qū)地址大小 以遞增順序排列 ?順序查找 空閑分區(qū)表，找到 第一個 滿足作業(yè)要求的空閑分區(qū) ?優(yōu)點 ：易于合并相鄰的空閑分區(qū)，盡可能 保留高地址端 的空閑分區(qū) ?缺點 ：搜索次數(shù)多，影響工作效率 三種主存分配算法 （ 2） 最佳 適應(yīng)分配算法 ?空閑分區(qū)表按 分區(qū)的大小 以遞增順序排列 ?找到 第一個 滿足作業(yè)要求的空閑分區(qū)，一定是 最小、且長度接近或合適作業(yè)要求 的空閑分區(qū) ?優(yōu)點 ：盡可能 保留較大 的空閑分區(qū) ?缺點 ：產(chǎn)生非常小的空閑分區(qū)（外碎片） 三種主存分配算法（續(xù)） （ 3） 最壞 適應(yīng)分配算法 ?空閑分區(qū)表按 分區(qū)的大小 以 遞減 順序排列 ?找到 第一個 滿足作業(yè)要求的空閑分區(qū)，一定是 最大 、且長度與作業(yè)要求 差別最大 的空閑分區(qū) ?優(yōu)點 ：分割后產(chǎn)生的空閑分區(qū)一般仍可供以后分配使用 ?缺點 ：工作一段時間后， 不能滿足大作業(yè) 對空閑分區(qū)的請求 主存空間的釋放 增加了合并相鄰空閑區(qū)的操作，主要是為了盡量及時簡單地減少“外碎片”。 2. 固定分區(qū)存儲管理 ——單一連續(xù)區(qū)在多道程序系統(tǒng)中的直接應(yīng)用 OS 0 a b c d job2 空 內(nèi)存 當(dāng)前運行作 業(yè)所在分區(qū) 下限寄存器 上限寄存器 2 b c CPU job3 設(shè)置“主存分配表”，來管理主存空間的使用 1）主存空間分配與釋放 區(qū)號 起始地址 長度 (KB) 占用標(biāo)志 1 a S1 0 2 b S2 Job2 3 c S3 Job3 三個分區(qū)的主存分配表 主存分配： 尋找沒被占用且長度滿足進程要求的分區(qū)。 ? 分頁式存儲管理 ：內(nèi)存空間和虛存空間都分成大小相等的頁（如 4k），虛存空間每一頁可以按照某種策略裝入內(nèi)存空間的某一頁。 本章需掌握的知識要點 ? 內(nèi)存管理任務(wù) ? 三種內(nèi)存管理方式 ? 兩類算法（內(nèi)存分配、頁面置換） ? 三組區(qū)別 可 重定位動態(tài)分區(qū) 基本分頁 請求分頁 實存 與 虛存 分頁 與 分段 連續(xù) 與 離散 存儲管理的概念 存儲管理策略的分類 OS本身的程序和數(shù)據(jù)與其他程序一起共享主存，為安全起見，多道程序系統(tǒng)常由 OS把內(nèi)存初始化為系統(tǒng)區(qū)和用戶區(qū)兩大部分： 內(nèi)存 系統(tǒng)區(qū)（存放 OS程序和數(shù)據(jù)） 用戶區(qū) （ 存放用戶程序 、 數(shù)據(jù) ） 對 用戶區(qū)內(nèi)存 的管理可采取不同的 策略 ，這些策略可以 按照不同的方法進行分類 。 便于編程及程序共享 ? 段頁式存儲管理 ：結(jié)合段式和頁式優(yōu)點，先對進程空間分段，再對每個段進行分頁。 2）地址轉(zhuǎn)換與存儲保護 ?地址轉(zhuǎn)換 ?常采用“ 靜態(tài)重定位 ”方法 ?作業(yè)在裝入時： 物理地址 =邏輯地址 +分區(qū)下限地址 ?存儲 保護 ?采用“ 界限寄存器對 ”法 ?程序執(zhí)行時判斷：下限地址 = 物理地址 = 上限地址 ?參看 P81頁，圖 31 3）主存空間的利用率 ?“內(nèi)碎片”問題嚴(yán)重，嚴(yán)重影響主存空間利用率 ?分區(qū)大小固定 ?作業(yè)往往比分區(qū)小很多，導(dǎo)致 分區(qū)內(nèi)部 一部分空間閑置不用 ?幾種解決方法（了解） ?方法一： 劃分從小到大的多個分區(qū)，按順序分配法分配，作業(yè)分配到的空間總是滿足其要求的最小分區(qū)（ 常用方法 ） ?方法二： 根據(jù)經(jīng)常出現(xiàn)的作業(yè)的大小和頻率進行靜態(tài)分區(qū) ?方法三： 作業(yè)按對主存空間的需求排成多個隊列，規(guī)定每個隊列中的作業(yè)只能進入到一個指定分區(qū) 3. 可變分區(qū)存儲管理 根據(jù)進程的需要， 動態(tài) 劃分內(nèi)存空間。 例 分區(qū)存儲管理算法題 采用可變分區(qū)方式管理內(nèi)存時，若內(nèi)存中 按地址順序 依次有五個大小依次為 15k、 28k、 10k、 226k和 110k的 空閑區(qū)。例如，某進程提出的 50KB的內(nèi)存請求，將首先被系統(tǒng)向上取整，轉(zhuǎn)化為對 1個 64KB的空閑塊的請求。例如， 1個 257KB 的進程需要占用 1個 512KB 的分配單位，其中將產(chǎn)生 255KB的內(nèi)碎片。 ? 頁內(nèi)碎片 ：進程空間的最后一頁可能不能裝滿整個物理內(nèi)存塊，物理內(nèi)存塊空閑部分稱為“ 頁內(nèi)碎片 ” 1. 相關(guān)原理及概念（續(xù)二） ? 頁表 系統(tǒng)為每個進程建立一個頁表，頁表給出邏輯頁號和具體內(nèi)存塊號相應(yīng)的關(guān)系。 . 快表 b + 頁號 p 頁內(nèi)地址 d P180。 ? 解決方法 ? 擴充物理內(nèi)存：增加成本； ? 虛擬存儲技術(shù) ：允許作業(yè)僅 部分裝入內(nèi)存 即可運行，其理論依據(jù)是 程序局部性原理 。 ? 按照 實分頁 方式進行分頁和分塊； ? 進程運行時，只需 部分頁面 在內(nèi)存； ? 當(dāng)進程訪問的頁不在內(nèi)存時將產(chǎn)生 缺頁中斷 ， 由中斷服務(wù)程序把所缺頁裝入內(nèi)存 ? 若內(nèi)存空間已滿，需要根據(jù) 頁面置換策略（頁面調(diào)度算法） 淘