【文章內(nèi)容簡(jiǎn)介】 配到的分區(qū)的首地址返回 可以看出，動(dòng)態(tài)分區(qū)分配方式中內(nèi)部碎片最大不超過(guò)min_size ? 回收，要考慮合并 – 向前合并 ? 只需修改前一個(gè)空閑分區(qū)表項(xiàng)中的大小 – 向后合并（圖） ? 只需修改后一個(gè)空閑分區(qū)表項(xiàng)中的起始地址和大小 – 與前后同時(shí)合并 ? 修改前一個(gè)空閑分區(qū)表項(xiàng)中的大小，并取消后一個(gè)分區(qū)表項(xiàng) – 無(wú)相鄰空閑分區(qū)，無(wú)需合并 ? 建立一個(gè)新的表項(xiàng)，填寫相關(guān)信息，插入 – 上述過(guò)程中，根據(jù)鏈表的維護(hù)規(guī)則，可能需要調(diào)整相應(yīng)表項(xiàng)在空閑鏈表中的位置 動(dòng)態(tài)分區(qū)分配分析 ? 隨著分配的進(jìn)行，空閑分區(qū)可能分散在內(nèi)存的各處 – 盡管有回收，但內(nèi)存仍然被劃分的越來(lái)越碎，形成大量的外部碎片 OS process 5 process 8 process 2 OS process 5 process 2 OS process 5 process 2 OS process 5 process 9 process 2 process 9 process 10 解決方案之一：緊湊 Compaction ? 針對(duì)外部碎片：采用緊湊的方法 ? 緊湊：通過(guò)移動(dòng)進(jìn)程在內(nèi)存中的位置，把多個(gè)分散的小分區(qū)拼成大分區(qū) ? 需要?jiǎng)討B(tài)重定位技術(shù)支持 ? 動(dòng)態(tài)重定位分區(qū)分配算法： 引入緊湊和動(dòng)態(tài)重定位技術(shù)的動(dòng)態(tài)分區(qū)分配算法 ? 基本與動(dòng)態(tài)分區(qū)分配算法相同 思考 ? 緊湊的時(shí)間開(kāi)銷：若計(jì)算機(jī)讀一個(gè) 32位的時(shí)間是 10ns，那么緊湊 128MB的空間需要多長(zhǎng)時(shí)間？ Swapping 對(duì)換 ? 最早用于 MIT的 CTSS中 – 單用戶＋時(shí)間片＋對(duì)換 ? 對(duì)換是指 把內(nèi)存中暫時(shí)不能運(yùn)行的進(jìn)程，或暫時(shí)不用的程序和數(shù)據(jù)，換出到外存上，以騰出足夠的內(nèi)存空間，把已具備運(yùn)行條件的進(jìn)程，或進(jìn)程所需要的程序和數(shù)據(jù)，換入內(nèi)存 ? 能提高內(nèi)存利用率 ? 對(duì)換的單位： – 進(jìn)程：整體對(duì)換；進(jìn)程對(duì)換 – 頁(yè)、段：部分對(duì)換 ? 對(duì)換技術(shù)需要實(shí)現(xiàn)三個(gè)方面的功能 – 對(duì)換空間的管理 – 進(jìn)程的換出 – 進(jìn)程的換入 Backing store，對(duì)換空間 ? Fast disk, large enough to acmodate copies of all memory images for all users。 must provide direct access to these memory images. – 為提高速度，考慮連續(xù)分配方式，忽略碎片問(wèn)題 – 需提供數(shù)據(jù)結(jié)構(gòu)對(duì)空閑盤塊進(jìn)行管理 ? 方法類似動(dòng)態(tài)分區(qū)分配方法 進(jìn)程的換出 ? 第一步：選擇被換出的進(jìn)程 – Some approaches ? RR scheduling: swapped out when a quantum expires ? Prioritybased scheduling: Roll out, roll in ? Lowerpriority process is swapped out so higherpriority process can be loaded and executed. ? 第二步：換出 – 確定要換出的內(nèi)容 ? 非共享的程序和數(shù)據(jù)段的換出 ? 共享的程序和數(shù)據(jù)段的換出：計(jì)數(shù)器 – 申請(qǐng)對(duì)換空間，換出，并修改相關(guān)數(shù)據(jù)結(jié)構(gòu) 進(jìn)程的換入 ? 第一步：選擇被換入的進(jìn)程 – 考慮“靜止就緒狀態(tài)”的進(jìn)程 – ＋其他原則 ? 第二部：申請(qǐng)內(nèi)存并換入 – 申請(qǐng)成功 – 申請(qǐng)失?。豪脤?duì)換技術(shù)騰出內(nèi)存 Schematic View of Swapping Swapping (cont.) ? Context switch – Swapped in amp。 out cost too much – Assume: process size 1MB, disk transfer rate 5MB/sec, average latency 8ms ? Transfer time =1MB / (5MB/sec) = 1/5 sec = 200 ms ? Swap time = 208 ms ? Swap out amp。 in = 416 – Major part of swap time is transfer time ? For RR scheduling, time quantum should 416ms ? Problems exist for pending I/O processes swapping 內(nèi)容提要 ? 存儲(chǔ)器的層次結(jié)構(gòu) ? 程序執(zhí)行的基礎(chǔ)知識(shí)、程序的裝入和鏈接 ? 連續(xù)分配存儲(chǔ)管理方式 ? 離散分配方式（ Discrete Memory Allocation） – 分頁(yè)存儲(chǔ)管理方式 ? 碎片 頁(yè) – 分段存儲(chǔ)管理 ? 從邏輯上進(jìn)行分段 – 段頁(yè)式存儲(chǔ)管理 內(nèi)容提要 ? 存儲(chǔ)器的層次結(jié)構(gòu) ? 程序執(zhí)行的基礎(chǔ)知識(shí)、程序的裝入和鏈接 ? 連續(xù)分配存儲(chǔ)管理方式 ? 離散分配方式（ Discrete Memory Allocation） – 分頁(yè)存儲(chǔ)管理方式 ? 碎片 頁(yè) – 分段存儲(chǔ)管理 ? 從邏輯上進(jìn)行分段 – 段頁(yè)式存儲(chǔ)管理 分頁(yè)存儲(chǔ)管理方式 1）將一個(gè)進(jìn)程的地址空間分成若干個(gè)大小相等的片，稱為 頁(yè)面或頁(yè)（ pages） 2）內(nèi)存空間也分成與頁(yè)大小相同的若干個(gè)存儲(chǔ)塊，稱為 物理頁(yè)或頁(yè)框（ page frames） 序號(hào)： 0， 1， ……， n 大小：取 2的冪， 512~8192B ? 地址結(jié)構(gòu) – 頁(yè)內(nèi)偏移：相對(duì)于頁(yè)（頁(yè)框）的起始地址的相對(duì)地址 – 頁(yè)（頁(yè)框）號(hào) S ? 對(duì)于 32位地址長(zhǎng)度 – 若頁(yè)（頁(yè)框）的大小為 4KB，則需要使用低端 12位表示頁(yè)內(nèi)偏移 – 剩余的高端 20位可以表示 220個(gè)頁(yè)（頁(yè)框）， 1M個(gè) 頁(yè)（頁(yè)框）號(hào) p 頁(yè)（頁(yè)框）內(nèi)偏移 d 0 11 12 31 ? 計(jì)算頁(yè)（頁(yè)框）號(hào)和頁(yè)（頁(yè)框）內(nèi)偏移的方法： – 地址： A – 頁(yè)（頁(yè)框）大小： L 頁(yè)（頁(yè)框）號(hào) p＝ A 整除 L 頁(yè)（頁(yè)框）內(nèi)偏移 d＝ A mod L ? 考慮 L是 2的冪，不妨設(shè)為 2N，則 – p ＝ A 右移 N位，即取 A的高（ 32－ N)位 – d＝ A的低端 N位 ? 必須在進(jìn)程的邏輯地址空間和內(nèi)存的物理地址空間之間建立一個(gè)映射關(guān)系 ? 使用頁(yè)表 ? 每個(gè)進(jìn)程都擁有各自的頁(yè)面映射表，即頁(yè)表 – 按序號(hào)，進(jìn)程地址空間中的每個(gè)頁(yè)在頁(yè)表中都有一個(gè)頁(yè)表項(xiàng)表示 – 頁(yè)表項(xiàng)中記錄的對(duì)應(yīng)的物理頁(yè)框的序號(hào) – 可以實(shí)現(xiàn)從頁(yè)號(hào)到頁(yè)框號(hào)的映射 頁(yè)表示意圖 頁(yè)表的例子 ? Page size = 4B ? Physical memory = 32B – 8 frames ? Logical memory = 16B – 4 pages ? Logical address 9 = 2*4+1 – p=2, d=1 – Page 2 is stored in frame 1 – Physical address = 1*4+1 = 5 思考 ? 下列 10進(jìn)制虛擬地址，分別計(jì)算頁(yè)面大小為 4KB和 8KB時(shí)的頁(yè)號(hào)和頁(yè)內(nèi)偏移 – 20220 – 32768 – 60000 思考 根據(jù)左圖，計(jì)算出以下虛擬地址對(duì)應(yīng)的物理地址 1. 20 2. 4100 3. 8300 地址變換機(jī)構(gòu) ? 使用專門的（軟）硬件 將用戶地址空間中的邏輯地址轉(zhuǎn)換為內(nèi)存空間中的物理地址 ? 基本的地址變換機(jī)構(gòu) ? 具有快表的地址變換機(jī)構(gòu) 基本的地址變換機(jī)構(gòu) Page table is kept in main memory, amp。 ? PageTable Base Register (PTBR) – Points to the page table currently used ? Pagetable leng