09 虛擬記憶體 (virtual memory) CHAPTER 9.1 (Virtual memory) 9.1.1 9.1.2 9.2 (segmentation) 9.2.1 9.2.2 9.3 (paging) 9.3.1 (static paging algorithm) 9.3.2 (dynamic paging algorithm) 9.4 (segmented/demand paged memory allocation)
作業系統 10 30 (demand paging) (virtual memory) overlay overlay overlay (paging) (segmentation) (memory manager) (page) (segment) (interrupt) 9-1 9-1 (paging) (segmentation) 分頁 (paging) 容許分頁框內部的碎片 (fragmentation) 存在不容許外部的碎片 (external fragmentation) 存在程式分割成大小一樣的分頁 (pages) 使用 page number 與位移 (displacement) 來計算絕對位址 (absolute address) 需要 PMT(page map table) 分段 (segmentation) 不容許內部的碎片 (internal fragmentation) 存在容許外部的碎片 (external fragmentation) 存在程式分割成大小不同的分段 (segments) 使用 segment number 與位移 (displacement) 來計算絕對位址 (absolute address) 需要 SMT(segment map table) 9-2
虛擬記憶體 (virtual memory) 09 9-1 1. 執行程式的大小可以不受限於主記憶體空間的大小 2. 記憶體的使用會更有效率, 因為程式會用到的部分才會占用記憶體的空間 3. 可以進行更廣泛的多工 (multiprogramming) 4. 避免 external fragmentation 的問題, 降低 internal fragmentation 的程度 5. 容許程式碼與資料的共用 6. 讓程式片段的動態連結 (dynamic linking) 更容易 (page interrupts) (thrashing) 9-1 9.1 虛擬記憶體 (Virtual memory) 簡介 (address space) (address space partition) secondary memory 9-2 process address space 9-3
作業系統 9-2 (code segment) (data segment) (spatial reference locality) spatial locality locality (virtual memory manager) 1. 記憶體管理員必須能接受位址空間的分割 2. 位址空間的分割必須能載入並且動態地連結到程式所用的位址 學習活動 1970 9-4
虛擬記憶體 (virtual memory) 09 9.1.1 實體記憶體的抽象化 secondary memory (virtual address space) memory map table page map table (bind) (reference) 9.1.2 虛擬記憶體技術 (swapping system) (absolute module) (relocation value) (symbolic name) (virtual address) (physical address space) 3 (mappings) 1. 分段法 (segmentation) 2. 分頁法 (paging) (symbolic identifier) (label) (variable) (name space) (absolute image) (executable image) (physical address) 9-3 9-5
作業系統 9-3 (dynamic loading) (bind) (address translation map) segmentation paging 學習活動 virtual address space address translation map 9.2 分段式的虛擬記憶體機制 (segmentation) (segmentation) relocation register limit register (segment) UNIX C compiler text, data stack segment <, (offset)> 9-6
虛擬記憶體 (virtual memory) 09 (external fragmentation) 9.2.1 分段法的原理 (modules) job (segment) (subroutine) page frames job (SMT, segment map table) demand paging Job table jobs job table SMT(segment map table) job SMT MMT(memory map table) MMT 9-4 3 9-4 memory manager 9-5 segment 1 8000 job 1 SMT segment 1 A 100 100 A 8000 9-7
作業系統 9-5 SMT 9.2.2 分段法的實作 9-6 4 (segment register) 1. STR(segment table register) : 儲存指向 segment table 的指標 2. CBR(code base register) : 儲存 code segment 的 base value, 有時候也稱為 PBR(procedure base register) 3. DBR(data base register) : 用來為靜態資料引用進行動態的重定位 4. SBR(stack base register) : 指向含有 process stack 的分段 Multics 9-6 Multics 9-8
虛擬記憶體 (virtual memory) 09 9-6 9.3 分頁的虛擬記憶體機制 (paging) (paged memory allocation) CPU job (page) 1. 磁碟上的區塊 : 稱為 sector 或 block 2. 主記憶體的區塊 : 稱為 page frame 3. job 的區塊 : 稱為 page memory manager page page frames pages page frames pages 1 1 page frames job page frames page frame jobs External fragmentation internal fragmentation page frame 9-7 page 3 main memory job-3/page 3 internal fragmentation job page frames 9-9
作業系統 9-7 (paged memory allocation) (paging) (linear) (page) (external fragmentation) (page frame) (page map) (reference locality) 1. 靜態配置演算法 (static allocation) : 當處理元建立的時候可以分配到固定數目的分頁框 (page frame) 然後由分頁配置的政策來處理後來分頁的載入與卸載 2. 動態配置演算法 (dynamic allocation) : 在程式執行的時候, 依照程式的需求改變記憶體空間的分配 9-10 9.3.1 靜態分頁配置演算法 (static paging algorithm) (load) (unload)
虛擬記憶體 (virtual memory) 09 1. 取用政策 (fetch policy) : 決定分頁何時載入主記憶體 2. 替換政策 (replacement policy) : 決定系統資源不足時那一個分頁應卸載 3. 置放政策 (placement policy) : 決定取用的分頁應放在何處 page frames page page frame page N virtual address space (page reference stream) w = r1, r2, r3,, ri, w 9.3.1.1 取用政策 (fetch policy) (prefetch) prefetch (demand paging) t Pt 1. 假如 P t 在 (t-1) 時已經載入, 則不需要進行任何處理 2. 假如 P t 在 (t-1) 時還未載入, 而且分配給程式的 page frame 還有空的, 則將 [ 引用的分頁載入到空的 page frame 中 3. 假如 P t 在 (t-1) 時還未載入, 而且分配給程式的 page frame 沒有空的, 則必須進行置換 9.3.1.2 需求分頁法 (demand paging) (demand paging) job job page frame fetch policy placement p olicy replacement policy 9-11
作業系統 (random replacement) page faults Belady Belady s optimal algorithm 3 page frame job w=0 1 2 3 0 1 2 3 0 1 2 3 4 5 6 7 Belady 9-2 (*) page fault 10 page faults 9-2 Belady frame 0 1 2 3 0 1 2 3 0 1 2 3 4 5 6 7 0 0* 0 0 0 0 0 0 0 0 1* 1 1 4* 4 4 7* 1 1* 1 1 1 1 2* 2 2 2 2 2 2 5* 5 5 2 2* 3* 3 3 3 3 3 3 3 3 3 3 6* 6 (LRU, least recently used) 9-3 LRU 16 page faults 9-3 LRU frame 0 1 2 3 0 1 2 3 0 1 2 3 4 5 6 7 0 0* 0 0 3* 3 3 2* 2 2 1* 1 1 4* 4 4 7* 1 1* 1 1 0* 0 0 3* 3 3 2* 2 2 5* 5 5 2 2* 2 2 1* 1 1 0* 0 0 3* 3 3 6* 6 (LFU, least frequently used) LFU LFU LFU LFU 9-4 LFU 12 page faults 9-12
虛擬記憶體 (virtual memory) 09 9-4 LFU frame 0 1 2 3 0 1 2 3 0 1 2 3 4 5 6 7 0 0* 0 0 0 0 0 0 0 0 0 0 3* 3 3 3 3 1 1* 1 1 1 1 1 3* 3 1* 1 1 1 1 1 1 2 2* 3* 3 3 2* 2 2 2 2 2 4* 5* 6* 7* (FIFO, first-in, first-out) FIFO 9-5 FIFO 16 page faults 9-5 FIFO frame 0 1 2 3 0 1 2 3 0 1 2 3 4 5 6 7 0 0* 0 0 3* 3 3 2* 2 2 1* 1 1 4* 4 4 7* 1 1* 1 1 0* 0 0 3* 3 3 2* 2 2 5* 5 5 2 2* 2 2 1* 1 1 0* 0 0 3* 3 3 6* 6 9.3.1.3 堆疊演算法 (stack algorithms) w = 0 1 2 3 0 1 4 0 1 2 3 4 FIFO page frames 3 9-6 9 page faults page frames page faults 9-6 3 page frame FIFO frame 0 1 2 3 0 1 4 0 1 2 3 4 0 0* 0 0 3* 3 3 4* 4 4 4 4 4 1 1* 1 1 0* 0 0 0 0 2* 2 2 2 2* 2 2 1* 1 1 1 1 3* 3 9-13
作業系統 page frames 4 FIFO 9-7 10 page faults Belady s anomaly page frames page faults? 9-7 4 page frames FIFO frame 0 1 2 3 0 1 4 0 1 2 3 4 0 0* 0 0 0 0 0 4* 4 4 4 3* 3 1 1* 1 1 1 1 1 0* 0 0 0 4* 2 2* 2 2 2 2 2 1* 1 1 1 3 3* 3 3 3 3 3 2* 2 2 page frames 9-6 page 4 1 page 1 9-7 page 4 1 page 1 page frames page frames page frames (inclusion property) (stack algorithms) Belady s anomaly FIFO page 4 1 9-6 {4,0,1} 9-7 {4,1,2,3} LRU LFU 9.3.2 動態分頁配置演算法 (dynamic paging algorithm) (locality) (working set algorithm) job (working set) job pages pages pages page fault job pages pages job working set page faults working set 9-14
虛擬記憶體 (virtual memory) 09 pages pages (locality of reference) (loop) pages 1. 為什麼不乾脆把 job 的 working set 中所有的 pages 一次全部都載入到記憶體中呢? 首先,working set 會隨 locality 而改變, 所以除非是把所有用道 pages 都載入, 否則無法全部一次都載入 2. 分時系統中會有 job swapping 的現象, 重新載入記憶體的 job 一開始都會產生很多 page faults, 影響系統的效能 paging system job working set job working set job working set Working set window size window size, ws=3 page w = 0 1 2 1 0 1 2 ws=3 working set {0,1} page ( page ) 3 pages 0 1 pages job 2 page frames window size page fault page frames page fault page frames locality window size window size (thrashing) page faults window size page faults window size 9-8 Window size 3 16 page faults 9-8 Window size 3 frame 0 1 2 3 0 1 2 3 0 1 2 3 4 5 6 7 0 0* 0 0 3* 3 3 2* 2 2 1* 1 1 4* 4 4 7* 1 1* 1 1 0* 0 0 3* 3 3 2* 2 2 5* 5 5 2 2* 2 2 1* 1 1 0* 0 0 3* 3 3 6* 6 分配 1 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 9-15
作業系統 9-8 page frames 0 3 window size 4 locality page faults 8 8 8 page faults! 9-9 Window size 4 9-8 page 3 1 window size 3 page 0 window size 4 LRU 9-9 Window size 4 frame 0 1 2 3 0 1 2 3 0 1 2 3 4 5 6 7 0 0* 0 0 0 0 0 0 0 0 0 0 0 4* 4 4 4 1 1* 1 1 1 1 1 1 1 1 1 1 1 5* 5 5 2 2* 2 2 2 2 2 2 2 2 2 2 2 6* 6 3 3* 3 3 3 3 3 3 3 3 3 3 3 7* 分配 1 2 3 4 4 4 4 4 4 4 4 4 4 4 4 4 window size (locality) page frame window size 9-10 window size 9 job 8 page faults 8 9-10 Window size 9 frame 0 1 2 3 0 1 2 3 0 1 2 3 4 5 6 7 0 0* 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1* 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2* 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3* 3 3 3 3 3 3 3 3 3 3 3 3 4 4* 4 4 4 5 5* 5 5 6 6* 6 7 7* 配置 1 2 3 4 4 4 4 4 4 4 4 4 5 6 7 8 9-16
虛擬記憶體 (virtual memory) 09 9-11 job page frames 9-11 w = 0 1 2 3 0 1 0 1 2 3 2 3 4 5 6 7 0101 2323 2 page frames locality 2 LRU 9-11 4 page frames frame 0 1 2 3 0 1 0 1 2 3 2 3 4 5 6 7 0 0* 0 0 0 0 0 0 0 0 0 4* 4 4 4 1 1* 1 1 1 1 1 1 1 1 1 5* 5 5 2 2* 2 2 2 2* 2 2 2 2 2 6* 6 3 3* 3 3 3 3* 3 3 3 3 3 7* 配置 1 2 3 4 4 4 3 2 3 4 3 2 3 4 4 4 9.4 分段分頁的記憶體配置 (segmented/demand paged memory allocation) (segment) pages external fragmentation 4 1. 系統要保存一個記載處理中的 jobs 的 Job Table 2. SMT(segment map table) 要列出每個分段的細節, 每個 job 都有一個 SMT 3. 每個 segment 有一個 PMT(page map table), 用來記載每個 page 的細節 4. 系統保存一個 MMT(memory map table), 用來監控 page frames 在記憶體中配置的狀況 9-17
作業系統 9-8 SMT PMT status modified referenced (address) segment number segment page number page (displacement) 3 9-8 (associative memory) associative memory job (registers) job SMT PMT pages 1. 當某個 page 被引用時, 系統會先搜尋 job 的 SMT, 找到對應的 PMT 2. PMT 接著載入到記憶體中, 決定 page 在記憶體中的位置 9-18
虛擬記憶體 (virtual memory) 09 3. 假如 page 不在記憶體中, 發出 page interrupt, 將 page 載入到記憶體中, 然後更新相關的 tables Associative memory pages page request page associative registers associative registers page 9-19
1. 請說明分段 (segmentation) 與分頁 (page) 的差異 2. 系統發生反覆替換 (thrashing) 的現象時, 分頁會一直在主記憶體與次記憶體之間快速地反覆移動, 對於記憶體的使用來說是很沒有效率的, 請說明反覆替換發生的原因? 作業系統要如何偵測與避免反覆替換的現象? 3. 請說明虛擬記憶體技術的優點以及可能產生的缺失 4. 請說明分段分頁記憶體配置法的原理 5. 假設分頁引用的順序為 w=0 1 3 0 4 6 7 5 0 1 0 1, 請仿照表 9-7 使用 4 個 page frames 的 FIFO 的靜態配置演算法, 將表格中的資料寫出來 9-21