【正文】 1 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 第四章 存儲(chǔ)器管理 內(nèi)存管理概述 連續(xù)分配存儲(chǔ)管理方式 基本分頁存儲(chǔ)管理方式 基本分段存儲(chǔ)管理方式 虛擬存儲(chǔ)器概念及關(guān)鍵技術(shù) 請(qǐng)求分頁存儲(chǔ)管理方式 請(qǐng)求分段存儲(chǔ)管理方式 2 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 用戶 程序 處理過程 內(nèi)存 裝入程序 源程序 裝入模塊 鏈接程序 庫 編譯程序 … … 目標(biāo)模塊 符號(hào)名空間 目標(biāo)地址 空間 統(tǒng)一的 目標(biāo)地址空間 物理地址 空間 數(shù)據(jù)和指令構(gòu)成：存取訪問問題 布局？ 3 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 程序處理與內(nèi)存管理 ? 程序地址空間及形成 ? 目標(biāo)模塊（由編譯 /匯編得到）：相對(duì)地址 ? 鏈接過程實(shí)現(xiàn)各目標(biāo)模塊相對(duì)地址的統(tǒng)一 ? 內(nèi)存管理物理部件 ? MMU負(fù)責(zé)將邏輯地址轉(zhuǎn)換為物理地址 ? X86體系結(jié)構(gòu) MMU支持分頁和分段機(jī)制 ? 內(nèi)存管理方式 ? 實(shí)模式和保護(hù)模式 4 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 程序的鏈接 ? 鏈接過程 ? 根據(jù) 外部訪問符號(hào)名表 ，將經(jīng)過編譯或匯編得到的一組目標(biāo)模塊以及它們所需要的庫函數(shù)，裝配成一個(gè)完整的裝入模塊 ? 關(guān)鍵問題 ? 修改相對(duì)地址 ? 變換外部調(diào)用符號(hào) ? 鏈接方式 ? 靜態(tài)鏈接方式、裝入 /運(yùn)行時(shí)動(dòng)態(tài)鏈接方式 5 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 程序的鏈接過程 目標(biāo)模塊 模塊 A CALL B。 Return。 L1 相對(duì)地址 0 模塊 B CALL C。 Return。 M1 0 模塊 C Code Return。 N1 0 相對(duì)裝入模塊 模塊 A JSR “L”。 Return。 L1 相對(duì)地址 0 模塊 B JSR “L+M”。 Return。 L+M1 L 模塊 C Code Return。 L+M+N1 L+M 6 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 鏈接方式比較 ? 靜態(tài)鏈接方式 ? 可執(zhí)行文件、難以實(shí)現(xiàn) “ 內(nèi)存 ” 模塊共享 ? 裝入時(shí)動(dòng)態(tài)鏈接 ? 便于軟件版本的修改和更新 ? 便于實(shí)現(xiàn)目標(biāo)模塊為多個(gè)應(yīng)用程序共享 ? 運(yùn)行時(shí)動(dòng)態(tài)鏈接 ? 將某些目標(biāo)模塊的鏈接推遲到執(zhí)行時(shí)根據(jù)是否需要再完成 7 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 程序的裝入 ? 基本目標(biāo)及相關(guān)問題 ? 由裝入程序?qū)⒀b入模塊載入到內(nèi)存 ? 裝入位置、地址變換（重定位）及時(shí)機(jī) ? 關(guān)鍵概念 ? 相對(duì)地址、絕對(duì)地址、重定位及其寄存器 ? 裝入方式 ? 絕對(duì)裝入方式（單道程序環(huán)境） ? 靜態(tài)可重定位裝入方式（多道程序環(huán)境） ? 動(dòng)態(tài)運(yùn)行時(shí)裝入方式（運(yùn)行中移動(dòng)位置） 8 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 絕對(duì)裝入模塊和可重定位裝入模塊 JMP 1424 Code LOAD 1, 2224 Data 1424 2224 絕對(duì)地址 1024 絕對(duì)裝入模塊 PROGRAM JMP Addri Code LOAD 1,Addrj DATA Data Addri Addrj 符號(hào)地址 目標(biāo)模塊 JMP 400 Code LOAD 1, 1200 Data 400 1200 相對(duì)地址 0 可重定位裝入模塊 9 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 （靜態(tài) /動(dòng)態(tài)） 可重定位 ? 重定位 ? 程序裝入或執(zhí)行時(shí)對(duì)裝入模塊或目標(biāo)程序中的指令及數(shù)據(jù)地址的修改過程 ? 靜態(tài)重定位 ? 由重定位裝入程序在將裝入模塊裝入內(nèi)存時(shí)一次性完成重定位 ? 需要連續(xù)存儲(chǔ)空間，裝入后不能移動(dòng) ? 動(dòng)態(tài)重定位 ? 需要特殊硬件（地址變換機(jī)構(gòu)）支持，以保證地址轉(zhuǎn)換不會(huì)影響指令的執(zhí)行速度 ? 便于動(dòng)態(tài)鏈接和代碼共享 10 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 動(dòng)態(tài)重定位示意圖 C P U 10000 相對(duì)地址 2500 + 重定位寄存器 內(nèi)存 物理地址 12500 LOAD 1, 2500 365 10000 10100 12500 15000 LOAD 1, 2500 365 0 100 2500 5000 作業(yè) J 11 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 操作系統(tǒng)內(nèi)存管理功能要求 ? 內(nèi)存分配 ? 使各得其所、提高利用率及適應(yīng)動(dòng)態(tài)增長(zhǎng)要求 ? 連續(xù)分配 /離散分配方式 ? 地址映射 ? 邏輯地址轉(zhuǎn)換為物理地址，與分配方式相關(guān) ? 內(nèi)存保護(hù) ? 基于地 址的保護(hù)、存取訪問控制保護(hù) ? 內(nèi)存擴(kuò)充 ? 對(duì)換技術(shù)、虛擬存儲(chǔ)技術(shù) 12 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 作業(yè)題 ? 談?wù)勀銓?duì)程序處理過程及內(nèi)存管理相關(guān)概念與關(guān)鍵問題的認(rèn)識(shí)與理解。同時(shí)并就各種可能的程序鏈接方式和程序裝入方式進(jìn)行比較和展開討論。 13 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 第四章 存儲(chǔ)器管理 內(nèi)存管理概述 連續(xù)分配存儲(chǔ)管理方式 基本分頁存儲(chǔ)管理方式 基本分段存儲(chǔ)管理方式 虛擬存儲(chǔ)器概念及關(guān)鍵技術(shù) 請(qǐng)求分頁存儲(chǔ)管理方式 請(qǐng)求分段存儲(chǔ)管理方式 14 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 連續(xù)分配存儲(chǔ)管理方式 單一連續(xù)分配存儲(chǔ)管理 固定分區(qū)分配存儲(chǔ)管理 動(dòng)態(tài)分區(qū)分配存儲(chǔ)管理 動(dòng)態(tài)可重定位分區(qū)分配 對(duì)換技術(shù) 15 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 單一連續(xù)分配方式 ? 內(nèi)存劃分為系統(tǒng)區(qū)和用戶區(qū) ? 整個(gè)用戶區(qū)為一個(gè)用戶獨(dú)占，僅駐留一道程序 ? 靜態(tài)鏈接和動(dòng)態(tài)重定位技術(shù)、存儲(chǔ)器保護(hù)措施 ? 僅適用于單用戶、單任務(wù)操作系統(tǒng)中 C P U 界限 寄存器 基址 寄存器 邏輯地址 + 是 物理地址 內(nèi)存 否 地址錯(cuò) 16 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 連續(xù)分配存儲(chǔ)管理方式 單一連續(xù)分配存儲(chǔ)管理 固定分區(qū)分配存儲(chǔ)管理 動(dòng)態(tài)分區(qū)分配存儲(chǔ)管理 動(dòng)態(tài)可重定位分區(qū)分配 對(duì)換技術(shù) 17 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 固定分區(qū)分配方式 ? 用戶區(qū)分為若干固定區(qū)域 ? 每個(gè)分區(qū)可裝入一道作業(yè) ? 分區(qū)劃分方法 (等分 /不等分 ) ? 分區(qū)說明表與內(nèi)存分配算法 ? 可用于多道程序存儲(chǔ)管理 A:B:C = 15:30:50 操作系統(tǒng) 作業(yè) A 作業(yè) B 作業(yè) C 存儲(chǔ)空間分配情況 0 30K 45K 75K 125K 225K 分區(qū)號(hào) 大小 KB 始址 K 狀態(tài) 1 15 30 已分配 2 30 45 空閑 3 50 75 已分配 4 100 125 空閑 ? ? ? ? 18 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 連續(xù)分配存儲(chǔ)管理方式 單一連續(xù)分配存儲(chǔ)管理 固定分區(qū)分配存儲(chǔ)管理 動(dòng)態(tài)分區(qū)分配存儲(chǔ)管理 動(dòng)態(tài)可重定位分區(qū)分配 對(duì)換技術(shù) 19 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 動(dòng)態(tài)分區(qū)分配方式 ? 基本思想 ? 根據(jù)進(jìn)程的實(shí)際需求，動(dòng)態(tài)地對(duì)內(nèi)存空間進(jìn)行分配、回收及劃分 ? 關(guān)鍵問題 ? 分區(qū)分配用數(shù)據(jù)結(jié)構(gòu) ? 分區(qū)分配算法 ? 分區(qū)分配與回收操作 ? 碎片（零頭）處理 ？ 黑板教學(xué) 20 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 分區(qū)分配用數(shù)據(jù)結(jié)構(gòu) 空閑分區(qū)表 空閑分區(qū)鏈 前向指針 后向指針 N+4 N+4 N個(gè)字節(jié)可用 分區(qū)大小 分區(qū)號(hào) 大小 KB 始址 K 1 64 44 2 24 132 3 40 210 4 30 270 … … … 21 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 分區(qū)分配算法 ? 首次適應(yīng)算法 FF ? 要求空閑分區(qū)鏈以地址遞增次序鏈接 ? 查找開銷大，但有利于大作業(yè)分配 ? 循環(huán)首次適應(yīng)算法 ? 首次適應(yīng) + 起始查尋指針 + 循環(huán)查找 ? 減少查找開銷，但不利于大作業(yè)分配 ? 最佳適應(yīng)算法 ? 追求既能滿足要求且又最小的空閑分區(qū) ? 要求空閑分區(qū)按大小遞增次序鏈接 ? 微觀意義上的最佳與宏觀上的零頭問題 最壞適應(yīng)算法 ？ 22 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 動(dòng)態(tài)分區(qū)內(nèi)存分配流程 從頭開始查找可變分區(qū)分配用數(shù)據(jù)結(jié)構(gòu) 開始 ≧ ? 檢索完否 ? ≦ size? 從當(dāng)前分區(qū)劃出 是 否 否 否 修改分配用數(shù)據(jù)結(jié)構(gòu)并執(zhí)行分配 是 返回 是 檢索下一分區(qū)信息 移出 當(dāng)前分區(qū) 分配單位 ？ 23 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 動(dòng)態(tài)分區(qū)內(nèi)存回收情況 F1 回收區(qū) 回收區(qū) F2 F1 回收區(qū) F2 回收區(qū) 24 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 動(dòng)態(tài)分區(qū)內(nèi)存回收流程 順序查找分配用數(shù)據(jù)結(jié)構(gòu)直至找到某分區(qū)之 =0 開始 是 返回 回收區(qū)與前一空閑區(qū)合并同時(shí)修正分配用數(shù)據(jù)結(jié)構(gòu) 非第一分區(qū)且與前一空閑區(qū)相鄰 ? 否 非最末分區(qū)且與后一空閑區(qū)相鄰 ? 回收區(qū)與后一空閑區(qū)合并同時(shí)修正分配用數(shù)據(jù)結(jié)構(gòu) 與后一空閑區(qū)相鄰 ? 與后一空閑區(qū)合并同時(shí)修正分配用數(shù)據(jù)結(jié)構(gòu) 是 是 回收區(qū)=0? 否 插入回收區(qū)并調(diào)整分配用數(shù)據(jù)結(jié)構(gòu) 否 是 25 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 連續(xù)分配存儲(chǔ)管理方式 單一連續(xù)分配存儲(chǔ)管理 固定分區(qū)分配存儲(chǔ)管理 動(dòng)態(tài)分區(qū)分配存儲(chǔ)管理 動(dòng)態(tài)可重定位分區(qū)分配 對(duì)換技術(shù) 26 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 動(dòng)態(tài)重定位分區(qū)分配方式 ? 緊湊 ? 連續(xù)分配要求程序裝入內(nèi)存空間的連續(xù)性 ? 分區(qū)分配產(chǎn)生的零頭 /碎片問題 ? 通過移動(dòng)把多個(gè)分散拼接成大分區(qū) ? 用戶程序內(nèi)存地址變化及地址修正問題 ? 動(dòng)態(tài)重定位 ? 動(dòng)態(tài)運(yùn)行時(shí)裝入方式及重定位寄存器 ? 動(dòng)態(tài)重定位分區(qū)分配算法 ? 動(dòng)態(tài)分配分區(qū)算法 + 緊湊功能 27 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 緊湊（拼接）技術(shù) 操作系統(tǒng) 用戶程序 1 10KB 用戶程序 3 30KB 用戶程序 6 14KB 用戶程序 9 26KB 操作系統(tǒng) 用戶程序 1 用戶程序 3 用戶程序 6 用戶程序 9 80KB 緊湊前 緊湊后 28 2022年 10月 23日星期日 北京交通大學(xué)計(jì)算機(jī)學(xué)院 翟高壽 動(dòng)態(tài)重定位分區(qū)分配流程 從頭開始查找可變分區(qū)分配用數(shù)據(jù)結(jié)構(gòu) 開始 找到不小于閑分區(qū)否 ? 空閑分區(qū)總和不小于 ? 進(jìn)行拼湊形成連續(xù)空閑區(qū)修改分配用數(shù)據(jù)結(jié)構(gòu) 是 否 否 按動(dòng)態(tài)分區(qū)方式進(jìn)行分配，修改分配用數(shù)據(jù)結(jié)構(gòu) 返回 是 29 2022年 10月 23日星期日