【正文】 表中可以省去頁號這個(gè)表目 。假定 m減少x%。 因此 ， 頁面的大小應(yīng)選擇得適中 ， 且頁面大小應(yīng)是 2的冪 ， 通常為 512 B~8 KB。 由于進(jìn)程的最后一頁經(jīng)常裝不滿一塊而形成了不可利用的碎片 ， 稱之為“ 頁內(nèi)碎片 ” 。 ? 造成這樣問題的主要原因是用戶程序裝入內(nèi)存時(shí)是整體裝入的，為解決這個(gè)問題，提出了分頁存儲(chǔ)管理技術(shù)。 內(nèi)存分配 例：利用最佳適應(yīng)算法，在上圖所示系統(tǒng)中確定內(nèi)存分配次序和內(nèi)存變化情況：申請內(nèi)存分別是25K， 20K， 10K， 5K。 內(nèi)存分配 ? 最壞適應(yīng)算法 ? 為了克服最佳適應(yīng) 算法把空閑區(qū)切割得大小的缺點(diǎn) ， 人們提出了一種最壞適應(yīng)算法 ， 即每次分配時(shí) ， 總是將最大的空閑區(qū)切去一部分分配給請求者 ， 其依據(jù)是當(dāng)一個(gè)很大的空閑區(qū)被切割了一部分后可能仍是一個(gè)較大的空閑區(qū) 。 內(nèi)存分配 ? 最佳適應(yīng)算法的 空閑區(qū)表按空閑區(qū)大小升序方法 組織 。 內(nèi)存分配 ? 例：利用首次適應(yīng)算法 ， 在上圖所示系統(tǒng)中確定內(nèi)存分配次序和內(nèi)存變化情況：申請內(nèi)存分別是 25K， 20K， 10K， 5K。 內(nèi)存分配 ? 首次適應(yīng)算法 ? 首次適應(yīng)算法 的表是 按空閑區(qū)首址升序的 （ 即空閑區(qū)表是按空閑區(qū)首址從小到大 ） 方法組織的 。+= ? C、 f r、 f2 合并到 f1, 。 內(nèi)存分配 ? 回收算法 ? 當(dāng)一個(gè)進(jìn)程（或程序）釋放某內(nèi)存區(qū)時(shí)，要調(diào)用存儲(chǔ)區(qū)釋放算法 release,它將首先檢查釋放區(qū)是否與空閑區(qū)表（隊(duì)列）中的其它空閑區(qū)相鄰，若相鄰則合并成一個(gè)空閑區(qū)，否則，將釋放為一個(gè)空閑區(qū)插入空閑區(qū)表（或隊(duì)列）中的適當(dāng)位置。 ? 門限值是切割空閑區(qū)后剩下的區(qū)域若小于門限值 ， 就不切割該空閑區(qū) ， 統(tǒng)統(tǒng)分給申請者 。 內(nèi)存分配 ? 分區(qū)存儲(chǔ)管理使用的數(shù)據(jù)結(jié)構(gòu)主要是空閑區(qū)表 、 空閑區(qū)隊(duì)列兩種 。 內(nèi)存分配 動(dòng)態(tài)分區(qū)存儲(chǔ)管理技術(shù) ? 系統(tǒng)生成后 ， 操作系統(tǒng)占用內(nèi)存的一部分 ， 一般在物理內(nèi)存的開始處 ， 比如 ， 一個(gè)操作系統(tǒng)占20KB， 裝入系統(tǒng)后占用 0～ 20KB的內(nèi)存空間 ， 剩下的部分作為一個(gè)空閑區(qū) ， 當(dāng)一個(gè)用戶程序 （ 作業(yè) 、進(jìn)程 ） 調(diào)入內(nèi)存時(shí) ， 把這個(gè)空閑區(qū)的 低地址部分 的區(qū)域分配給它 ， 如圖所示 。 內(nèi)存分配 ? 分區(qū)存儲(chǔ)管理 ? 分區(qū)存儲(chǔ)管理是滿足多道程序設(shè)計(jì)的最簡單的一種存儲(chǔ)管理方法，它允許 多個(gè) 用戶程序同時(shí)存在系統(tǒng)內(nèi)存中，即 共享內(nèi)存 空間。 這種鏈接方式是將對某些模塊的鏈接推遲到執(zhí)行時(shí)才執(zhí)行 ， 亦即 ， 在執(zhí)行過程中 ， 當(dāng)發(fā)現(xiàn)一個(gè)被調(diào)用模塊尚未裝入內(nèi)存時(shí) ， 立即由 OS去找到該模塊并將之裝入內(nèi)存 ， 把它鏈接到調(diào)用者模塊上 。 (2) 變換外部調(diào)用符號。 因此 ，通常是寧可在程序中采用符號地址 ， 然后在編譯或匯編時(shí) ，再將這些符號地址轉(zhuǎn)換為絕對地址 。 ? 實(shí)現(xiàn)動(dòng)態(tài)地址映射必須有硬件的支持，并有一定的執(zhí)行時(shí)間延遲。 ? ? 動(dòng)態(tài)地址映射是在程序執(zhí)行時(shí)由系統(tǒng)硬件完成從邏輯地址到物理地址的轉(zhuǎn)換的 。 ? 評價(jià) : ? 優(yōu)點(diǎn)是實(shí)現(xiàn)簡單 ， 不要硬件的支持 。 有時(shí)也稱為地址重定位 。 ? 程序邏輯地址空間 （ 邏輯地址空間 、 虛地址空間 ） :用戶的程序地址的集合稱為邏輯地址空間 ， 它的編址總是從 0開始的 ， 可以是一維線性空間 ， 也可以是多維空間 。在文件系統(tǒng)中介紹 。第四章 存儲(chǔ)器管理 存儲(chǔ)器分成兩類： ? 內(nèi)存儲(chǔ)器 （ 簡稱內(nèi)存 、 主存 、 物理存儲(chǔ)器 ） ? 處理機(jī)能直接訪問的存儲(chǔ)器 。 用來存放用戶的各種信息 ， 存取速度相對內(nèi)存而言要慢得多 ， 但它可用來長期保存用戶信息 。 ? ? 程序邏輯地址 ： 用戶編程序時(shí)所用的地址（ 或稱邏輯地址 、 虛地址 ） ， 基本單位可與內(nèi)存的基本單位相同 ， 也可以不相同 。 ? (4) 提供虛擬存儲(chǔ)技術(shù) ? 使用戶程序的大小 和結(jié)構(gòu) 不受主存容量和結(jié)構(gòu) 的限制，即使在用戶程序比實(shí)際主存容量還要大的情況下，程序也能正確運(yùn)行． ? 地址映射 ? 一 、 什么是地址映射 ? 地址映射 ? 將程序地址空間中使用的邏輯地址變換成主存中的物理地址的過程稱為地址映射 。 ? 在一些早期的系統(tǒng)中都有一個(gè)裝入程序 （ 加載程序 ） ， 它負(fù)責(zé)將用戶程序裝入系統(tǒng) ， 并將用戶程序中使用的訪問內(nèi)存的邏輯地址轉(zhuǎn)換成物理地址 。 在程序裝入內(nèi)存時(shí)要將所有訪問內(nèi)存的地址轉(zhuǎn)換成物理地址 。 ? 重定位寄存器的內(nèi)容（ 程序裝入內(nèi)存的基址 ）由操作系統(tǒng)用特權(quán)指令來設(shè)置，比較靈活 。 但在由程序員直接給出絕對地址時(shí) ， 不僅要求程序員熟悉內(nèi)存的使用情況 ， 而且一旦程序或數(shù)據(jù)被修改后 ， 可能要改變程序中的所有地址 。 程序的鏈接 1. 靜態(tài)鏈接方式 (Static Linking) 圖 43 程序鏈接示意圖 模塊 AC A L L B ；R e t u r n ；0L － 1模塊 BC A L L C ；R e t u r n ；0M － 1模塊 CR e t u r n ；0N － 10模塊 AJ S R “ L ”R e t u r n ；L － 1模塊 BJ S R “ L ＋ M”R e t u r n ；LL ＋ M － 1L ＋ ML ＋ M ＋ N － 1模塊 CR e t u r n ；( a ) 目標(biāo)模塊 ( b ) 裝入模塊 在將這幾個(gè)目標(biāo)模塊裝配成一個(gè)裝入模塊時(shí) ， 須解決以下兩個(gè)問題： (1) 對相對地址進(jìn)行修改 。 3. 運(yùn)行時(shí)動(dòng)態(tài)鏈接 (Runtime Dynamic Linking) 近幾年流行起來的運(yùn)行時(shí)動(dòng)態(tài)鏈接方式 ， 是對上述在裝入時(shí)鏈接方式的一種改進(jìn) 。內(nèi)存管理策略有三種： ? 放置策略 ? 決定內(nèi)存中放置信息的區(qū)域 （ 或位置 ） ，即如何在若干個(gè)空閑區(qū)中選擇一個(gè)或幾個(gè)空閑區(qū)的原則； 內(nèi)存分配 ? 調(diào)入策略 ? 決定信息裝入內(nèi)存的時(shí)機(jī) ， 有兩種 （ 1）在用戶請求時(shí)調(diào)入 ， 稱為 請調(diào) ； （ 2） 根據(jù)某種算法 ， 確定系統(tǒng)將要使用的信息 ， 并在執(zhí)行前預(yù)先調(diào)入內(nèi)存 ， 稱為 預(yù)調(diào) ； ? 淘汰策略 ? 當(dāng)內(nèi)存不足時(shí) ， 決定將某些信息調(diào)出內(nèi)存的策略 (交換與覆蓋 ) 。 ? 這種存儲(chǔ)管理的方法的主要問題是內(nèi)存使用效率極低 ，很快就被淘汰 。 內(nèi)存分配 ? 動(dòng)態(tài)分區(qū)存儲(chǔ)管理技術(shù)的實(shí)現(xiàn) ： ? (1)地址映射 ? (2)動(dòng)態(tài)存儲(chǔ)管理的機(jī)構(gòu) （ 數(shù)據(jù)結(jié)構(gòu) ） ? (3)分區(qū)的分配和回收 ? (4)三種基本的放置策略 內(nèi)存分配 ? 用基地址寄存器實(shí)現(xiàn)動(dòng)態(tài)地址映射 ? 在這種存儲(chǔ)管理技術(shù)中 ， 系現(xiàn)設(shè)置一個(gè)專用寄存器 ， 稱為基地址寄存器 ，當(dāng)一個(gè)進(jìn)程 （ 或程序 、 作業(yè) ） 被調(diào)度運(yùn)行時(shí) ， 系統(tǒng)首先從 PCB中取出該進(jìn)程的首地址裝入基地址寄存器中 ， 在該進(jìn)程運(yùn)行的過程中實(shí)現(xiàn)動(dòng)態(tài)地址映射 。 內(nèi)存分配 ? 分配算法 ? 分配算法中切割空閑區(qū)是從低地址開始的 ， 例如 ， 一個(gè)空閑區(qū)大小是 100KB， 首址是 230KB， 一申請者要求 80KB， 分配時(shí)將從 230KB開始的 80KB分配給申請者 ， 剩下的部分仍作為一個(gè)空閑區(qū) ， 其首址是310KB， 大小是 20KB。 從空閑區(qū)尾開始 ? 空閑區(qū)大小 50KB，首址 156KB，申請 34KB。+= ? B、 將 r合并到 f2, 。 ? 根據(jù)空閑區(qū)表組織的方法的不同 ， 有不同的放置策略 ， 它們是最佳適應(yīng)算法 、 首次適應(yīng)算法和最壞適應(yīng)算法三種 。 ? 回收時(shí) ， 首先考察釋放區(qū)是否與系統(tǒng)中的某個(gè)空閑區(qū)相鄰 ， 若相鄰則合并成一個(gè)空閑區(qū) ， 否則 ， 將釋放區(qū)作為一個(gè)空閑區(qū)按首址升序的規(guī)則插入到空閑區(qū)表適當(dāng)?shù)奈恢?。 （ 首次適應(yīng)法則不一定 ） 。 內(nèi)存分配 例：利用最佳適應(yīng)算法，在上圖所示系統(tǒng)中確定內(nèi)存分配次序和內(nèi)存變化情況：申請內(nèi)存分別是 25K， 20K， 10K， 5K。 ? 分配時(shí)總是 取表中的第一個(gè)表目 ，若不能滿足申請者的要求，則表示系統(tǒng)