作業系統 4. 記憶體管理 - Ian-Liu-1990/Computer-Arch-OS GitHub Wiki
-
靜態配置 :
-
動態配置 :
-
分頁 : 允許同一支程式,為了載入不連續空間的主記憶體,將程式切成相同大小的分頁Page,對應實體主記憶體相同大小的頁框Frame
- Page size = Frame size
- 邏輯位置bits = Page數量bits + Page Size(offset);
- 實體位置bits = frame數量bits + frame Size;frame數量 = 實體記憶體大小/frame size
- Page Table size = Pages + 紀錄每一個Page的entry
-
分段
- 主記憶體 : 實體(physical memory)記憶體,
- 快取記憶體 : 轉譯旁觀(Translation Look-aside Buffer, TLB)緩衝區,快取時間,快取存取時間
2. 常見3種失誤
失 誤 類 型 | 說 明 | 改 善 |
---|---|---|
強迫性 - 失誤 | 第一次存取時,失誤 | 預先擷取 |
容量性 - 失誤 | 因已無可用快取記憶體空間,而失誤 | 加大快取記憶體空間 |
衝突性 - 失誤 | 快取記憶體位置已被佔據,而失誤 | 發生大到小Direct mapped、set associative、fully associative,完全關聯快取映射 |
3. 快取映射機制
直接映射 | 主記憶體區塊映射到快取記憶體內的固定位置 | 快取記憶體資料置換頻繁的缺點 |
---|---|---|
完全關聯 | 主記憶體區塊映射到快取記憶體內的任一位置 | 成本最高,電路複雜,硬體實作困難 |
集合關聯 | 主記憶體區塊映射到快取記憶體內所屬集合任意位置, 當集合指有一個區塊使用直接映射;當所有區塊為同一集合使用完全關聯 |
加大快取記憶體空間 |
I. "快取"記憶體平均(期望)存取時間[快取算法]
- 概念: 快取記憶體(SRAM)會先讀取,當快取記憶體讀不到(1 - Cache Hit%)才會去讀主記憶體(DRAM)
- 記憶體平均存取時間公式
= Cache hit% * AvgCacheAccessTime + (1-Cache hit%) * [Avg快取存取時間 + Avg主記憶體存取時間]
= AvgCacheAccessTime + (1-h) * AvgMainMemAccTime
快取記憶體平均存取時間-反推(題目直接敘述存取時間,表達有問題)
II. "TLB" 記憶體有效平均存取時間[TLB 分頁的算法]
- TLB記憶體有效存取時間 =
Cache 命中機率 × (Cache 存取時間 + 映射到主記憶體存取時間)+Cache 沒命中機率 ×( Cache 存取時間+2 * 主記憶體存取時間(主記憶體抓再取回) )
分頁替換演算法[計算 - 分頁錯失(page faults):欲存取的Page尚未載入記憶體內的次數]
- 分頁替換(page replacement):Page fault 發生時,當 memory 已滿,選擇記憶體中的一頁來取代。
- 分頁錯失(page faults):欲存取的Page尚未載入記憶體內
-
FIFO :
- 畢雷地現象: 當被配置的欄數增加之後,分頁錯誤的比率可能會增加,譬如四個欄的分頁錯誤比三個欄的分頁錯誤大
- 輾轉現象(Thrashing) : 當各行程的總需求欄位空間(total demand frames)超過實體記憶體的欄位空間時,便會發生輾轉現象,指行程分頁替換的頻率相當高,於是系統的時間相耗費在輸入輸出(I/O)的動作,CPU的使用率低落,作業系統會認為需要增加多工的程度,而又將更多行程加入系統中,每個行程所分配到的實體記憶體又更少,因而惡性循環。
III. 虛擬記憶體有效存取時間
- VM記憶體有效存取時間
= P命中率 * (存取Page時間 + 主記憶體存取時間) + (1-P) * (主記憶體存取時間)
-
邏輯位置 : 分成兩部分
- P分頁數/分頁表項目數Pages : 一個程式總共被分成幾頁
- d分頁大小Page(Offset) : 一個程式進行分頁,每一頁大小
-
實體位址 : 分頁被載入主記憶體的頁框內
- F頁框/分頁框項目數Page Frames :
- d分頁大小Page(Offset) : 一個程式進行分頁,每一頁大小
- 問 - 分頁表大小Page table Size = Pages * 記下每一個紀錄需要多少
- 邏輯位址Bits數 = 分頁大小Page_Size bits + 分頁數Pages bits
- 實體位址Bits數 = 分頁大小Page_Size bits + 頁框數Page frame bits
分頁數 + Page Frame分頁大小(offset) - 詳
假設某一邏輯位址空間(logical address space)只有 8 個分頁(pages),每個分頁大小(page size)是 1024 位元組(bytes)。對應的實際記憶體(physical memory)上有 32 個頁框(page frames)。請問邏輯位址 (logical address)至少共需幾個位元(bits)來表示?
解: 8 = 2^3 => 需要3個bits, 1024 bytes = 2^10 => 需要10個bits 邏輯位址 = 分頁大小bits + 分頁數(offset, page frame) => 3 + 10 = 13
某作業系統之實體記憶體有256 K bytes,而其虛擬位址(virtual address)有20 bit,其中13 bit要設為page frame裡的Offset,假設每一地址的資料為1 byte,則實體記憶體可以放進多少page?[中華電信]
解: Page frame = 13,每一個Pages大小2^13 ,需要1Byte來記錄位址 => 2^13 * 1 = 2^13 256 KBytes / 2^13 = 2^(18-13) = 2^5 = 32 個Page
一個系統是用反分頁表,一個系統是用單一層次分頁表!!
32 bits - offset 12 bits = 20 bits
故全部page table size = page entry(用來記錄一個位置需要4Byte題目給的)2^20 = 4M bytes
single level 因為3個process獨立 故4M3 = 12M
若使用 inverted page table 256M/4K = 2^16 K bytes : 可放那麼多的分頁
inverted page table entry 數 = memory frame 數
每個分頁項目需要 4 byte紀錄 故table size = 2^16分頁數 * 4需要記錄數 = 256 KB