【正文】 時存在系統(tǒng)內(nèi)存中，即 共享內(nèi)存 空間。 ? 最早期的分區(qū)存儲管理采用 固定分區(qū) 的方法 ， 把內(nèi)存空間分成若干個大小不等的區(qū)域 ， 稱為分區(qū) 。 每個用戶程序 （ 作業(yè) 、 進(jìn)程 ） 調(diào)入內(nèi)存后 ， 占用其中一個分區(qū) ， 程序運行完成后釋放該分區(qū) 。 ? 這種存儲管理的方法的主要問題是內(nèi)存使用效率極低 ，很快就被淘汰 。 內(nèi)存分配 動態(tài)分區(qū)存儲管理技術(shù) ? 系統(tǒng)生成后 ， 操作系統(tǒng)占用內(nèi)存的一部分 ， 一般在物理內(nèi)存的開始處 ， 比如 ， 一個操作系統(tǒng)占20KB， 裝入系統(tǒng)后占用 0～ 20KB的內(nèi)存空間 ， 剩下的部分作為一個空閑區(qū) ， 當(dāng)一個用戶程序 （ 作業(yè) 、進(jìn)程 ） 調(diào)入內(nèi)存時 ， 把這個空閑區(qū)的 低地址部分 的區(qū)域分配給它 ， 如圖所示 。 內(nèi)存分配 內(nèi)存分配 ? 當(dāng)有作業(yè)完成后釋放所占用的存儲區(qū)。 在系統(tǒng)運行的過程中，系統(tǒng)中形成多個空閑的不連續(xù)的存儲區(qū)。 內(nèi)存分配 ? 動態(tài)分區(qū)存儲管理技術(shù)的實現(xiàn) ： ? (1)地址映射 ? (2)動態(tài)存儲管理的機構(gòu) （ 數(shù)據(jù)結(jié)構(gòu) ） ? (3)分區(qū)的分配和回收 ? (4)三種基本的放置策略 內(nèi)存分配 ? 用基地址寄存器實現(xiàn)動態(tài)地址映射 ? 在這種存儲管理技術(shù)中 ， 系現(xiàn)設(shè)置一個專用寄存器 ， 稱為基地址寄存器 ，當(dāng)一個進(jìn)程 （ 或程序 、 作業(yè) ） 被調(diào)度運行時 ， 系統(tǒng)首先從 PCB中取出該進(jìn)程的首地址裝入基地址寄存器中 ， 在該進(jìn)程運行的過程中實現(xiàn)動態(tài)地址映射 。 內(nèi)存分配 ? 分區(qū)存儲管理使用的數(shù)據(jù)結(jié)構(gòu)主要是空閑區(qū)表 、 空閑區(qū)隊列兩種 。 其形式如圖所示 。 內(nèi)存分配 ? 內(nèi)存分配 程序包括分配一個內(nèi)存塊（ 分區(qū) ） 和釋放一個內(nèi)存塊 （ 分區(qū) ）兩個函數(shù) ， 當(dāng)進(jìn)程需要一個大小為size的內(nèi)存時 ， 可以通過系統(tǒng)調(diào)用向系統(tǒng)申請 。 內(nèi)存分配 ? 分配算法 ? 分配算法中切割空閑區(qū)是從低地址開始的 ， 例如 ， 一個空閑區(qū)大小是 100KB， 首址是 230KB， 一申請者要求 80KB， 分配時將從 230KB開始的 80KB分配給申請者 ， 剩下的部分仍作為一個空閑區(qū) ， 其首址是310KB， 大小是 20KB。 ? 門限值是切割空閑區(qū)后剩下的區(qū)域若小于門限值 ， 就不切割該空閑區(qū) ， 統(tǒng)統(tǒng)分給申請者 。 內(nèi)存分配 ? 切割空閑區(qū)有兩種方法： ? 從空閑區(qū)頭開始 ? 從空閑區(qū)尾開始 ? 空閑區(qū)大小 50KB，首址 156KB，申請 34KB。 內(nèi)存分配 ? 回收算法 ? 當(dāng)一個進(jìn)程（或程序）釋放某內(nèi)存區(qū)時，要調(diào)用存儲區(qū)釋放算法 release,它將首先檢查釋放區(qū)是否與空閑區(qū)表（隊列）中的其它空閑區(qū)相鄰，若相鄰則合并成一個空閑區(qū)，否則，將釋放為一個空閑區(qū)插入空閑區(qū)表（或隊列）中的適當(dāng)位置。 ? ? 空閑釋放區(qū)與空閑區(qū)相鄰有四種情況 。 內(nèi)存分配 ? A、 將 r合并到 f1， 。+= ? B、 將 r合并到 f2, 。+= ? C、 f r、 f2 合并到 f1, 。 ? ++= 撤消 f2空閑區(qū) ? D、 r作為一個空閑區(qū) ， 并插入到空閑區(qū)表的適當(dāng)位置 。 內(nèi)存分配 ? 幾種放置策略 （ 分配算法 ） ? 分區(qū)分配和回收是對空閑區(qū)表 （ 或空閑區(qū)隊列 ） 數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作 ， 空閑區(qū)表的組織有兩種方法： ? 按空閑區(qū)大小的升序 （ 降序 ） 組織； ? 按空閑區(qū)首址升序 （ 降序 ） 組織 。 ? 根據(jù)空閑區(qū)表組織的方法的不同 ， 有不同的放置策略 ， 它們是最佳適應(yīng)算法 、 首次適應(yīng)算法和最壞適應(yīng)算法三種 。 內(nèi)存分配 ? 首次適應(yīng)算法 ? 首次適應(yīng)算法 的表是 按空閑區(qū)首址升序的 （ 即空閑區(qū)表是按空閑區(qū)首址從小到大 ） 方法組織的 。 內(nèi)存分配 內(nèi)存分配 ? 分配時 從表首開始 ，以請求內(nèi)存區(qū)的大小逐個與空閑區(qū)進(jìn)行比較，找到第一個滿足要求的空閑后，若空閑區(qū)大小與請求區(qū)的大小相等，則將該空閑區(qū)分配給請求者，并撤消該空閑區(qū)所在表目；若大于請求區(qū)，就將該空閑區(qū)的一部分分配給請求者，然后，修改空閑區(qū)的大小和首址。 內(nèi)存分配 ? 這種算法的實質(zhì)是盡可能地利用低地址部分的空閑區(qū) ， 而盡量地保證高地址部分的大空閑區(qū) ， 使其不被切削成小的區(qū) ， 其目的是保證在以有有大的作業(yè)的到來有足夠大的空閑區(qū)來滿足請求者 。 ? 回收時 ， 首先考察釋放區(qū)是否與系統(tǒng)中的某個空閑區(qū)相鄰 ， 若相鄰則合并成一個空閑區(qū) ， 否則 ， 將釋放區(qū)作為一個空閑區(qū)按首址升序的規(guī)則插入到空閑區(qū)表適當(dāng)?shù)奈恢?。 內(nèi)存分配 ? 例：利用首次適應(yīng)算法 ， 在上圖所示系統(tǒng)中確定內(nèi)存分配次序和內(nèi)存變化情況：申請內(nèi)存分別是 25K， 20K， 10K， 5K。 內(nèi)存分配 ? 最佳適應(yīng)算法 ? 最佳適應(yīng)算法是將申請者放入與其大小最接近的空閑區(qū)中 。 切割后的空閑區(qū)最小 ， 若系統(tǒng)中有與申請區(qū)大小相等的空閑區(qū) ， 這種算法肯定能將這種空閑區(qū)分配給申請者 。 （ 首次適應(yīng)法則不一定 ） 。 內(nèi)存分配 ? 最佳適應(yīng)算法的 空閑區(qū)表按空閑區(qū)大小升序方法 組織 。 ? 分配時 ， 按申請的大小逐個與空閑區(qū)大小進(jìn)行比較 ， 找到一個滿足要求的空閑區(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ū)切割得大小的缺點 ， 人們提出了一種最壞適應(yīng)算法 ， 即每次分配時 ， 總是將最大的空閑區(qū)切去一部分分配給請求者 ， 其依據(jù)是當(dāng)一個很大的空閑區(qū)被切割了一部分后可能仍是一個較大的空閑區(qū) 。 避免了空閑區(qū)越分越小的問題 。 內(nèi)存分配 ? 最壞適應(yīng)算法的 空閑區(qū)表是按空閑區(qū)大小降序的方法 組織的（從大到小的順序）。 ? 分配時總是 取表中的第一個表目 ，若不能滿足申請者的要求，則表示系統(tǒng)中無滿足要求的空閑區(qū)，分配失敗；否則，將從該空閑區(qū)中分配給申請者，然后修改空閑區(qū)的大小，并將它插入到空閑區(qū)表的適當(dāng)位置。 內(nèi)存分配 例：利用最佳適應(yīng)算法，在上圖所示系統(tǒng)中確定內(nèi)存分配次序和內(nèi)存變化情況：申請內(nèi)存分別是25K， 20K， 10K， 5K。 內(nèi)存分配 ? 三種放置算法的優(yōu)劣很難區(qū)分 ， 要具體情況具體分析 。 ? 例如：某時刻系統(tǒng)中有三個空閑區(qū) ? 其大小和首址為： ? (35KB ， 100KB) 、 (12KB ， 156KB) 、(28KB， 200KB) ? 有一作業(yè)系列： ? (JOB1， 12KB)、 (JOB2， 30KB)、 (JOB3，28KB) 內(nèi)存分配 ? 課堂練習(xí) OS 2140k 4180k 81160k 161320k 321640k ……… ? 如圖所示，內(nèi)存的紅色部分為空閑區(qū)，有如下內(nèi)存申請序列：25k,40k,32k,46k，分別按首次適應(yīng)算法，最佳適應(yīng)算法，最壞適應(yīng)算法確定內(nèi)存分配次序和內(nèi)存變化情況 基本分頁存儲管理方式 ? 問題的提出 ? 分區(qū)存儲管理的主要問題是碎片問題。 ? 在采用分區(qū)存儲管理的系統(tǒng)中，會形成一些非常小的分區(qū)，最終這些非常小的分區(qū)不能被系統(tǒng)中的任何用戶（程序）利用而浪費。 ? 造成這樣問題的主要原因是用戶程序裝入內(nèi)存時是整體裝入的，為解決這個問題，提出了分頁存儲管理技術(shù)。 基本分頁存儲管理方式 頁面與頁表 1. 頁面 1) 分頁存儲管理 ， 是將一個進(jìn)程的邏輯地址空間分成若干個大小相等的片 ， 稱為頁面或頁 ， 并為各頁加以編號 ， 從 0開始 ， 如第 0頁 、 第 1頁等 。 相應(yīng)地 ， 也把內(nèi)存空間分成與頁面相同大小的若干個存儲塊 ， 稱為 (物理 )塊或頁框 (frame)， 也同樣為它們加以編號 ， 如 0＃ 塊 、 1＃ 塊等等 。 基本分頁存儲管理方式 在為進(jìn)程分配內(nèi)存