系統中，所有可用空間總和大於某個 process 所需要，但因為這些空間不連續
所以無法配給該 process 使用，造成 memory 空間閒置。
內部碎裂 (Internal Fragmentation)
作業系統配置給 process 的 memory 空間大於 process 真正所需的空間，
這些多出來的空間該 process 用不到，而且也沒辦法供其他 process 使用，形成浪費。
記憶體的配置方式 (連續性配置，會有外部碎裂)
1. First fit
2. Best fit
3. Worst fit
4. Next fit
分頁管理記憶體
將 physical memory 視為一組 frame 的集合，而 logical memory 則視為一組 page 的
集合。page 與 frame 的大小是相同的。當 program 需要 n 個 pages 時，作業系統
就會去 physical memory 中找出 n 個 free frame 來放置即可，frame 間不需要連續。
CPU ---logical address---> [Page][Offset] --->查詢分頁表---> [Frame][Offset]
Page Table 的實作方式
1. 全部存在 Memory 中
使用 PTBR(Page table base register) 來記錄 table 的起始位置。所以每次存取
需要 2 次 memory access ，因為第一次查表、第二次是去撈 frame
2. 使用 TLB (Translation Lookupaside Buffer)
這就是 page table 的快取，把最近用到的 page <--> frame 的 mapping 情況記下來。
所花費時間會是：
p * (TLB access + Mem access) + (1-p) * ( TLB access + 2*Mem access)
p = 在 TLB 中找到資料的機率，如果未在 TLB 中找到，
就要去 memory 撈 page table 了。所以當查詢未 hit
會多付出一次 memory 存取的時間。
[ page table 太大的問題 ]
因為 logical memory size 變得相當大，所以 page table 也變得很大，
極佔記憶體空間。
邏輯位址有 32 bits 、page size 4kB、每一個 table entry 佔 4 bytes
求 page table size
[Page][Offset] = 32 bits
Offset 的長度，要能定址一個 page 大小( 4KB = 2^12 byte) ，
所以 Offset 長度為 12 bits 邏輯位址有 32bits 扣去 Offset 的 12 bits，
還剩 20bits，這表示一個 process 最多用 2^20 pages ，
所以系統中 page table 最多有 2^20 個 entry
page table size 最大會是： 2^20 * 4bytes(每個 entry 大小) = 4MB
[解決 page table 太肥的問題]
因為 logical memory size 變得相當大，所以 page table 也變得很大，
極佔記憶體空間。
邏輯位址有 32 bits 、page size 4kB、每一個 table entry 佔 4 bytes
求 page table size?
[Page][Offset] = 32 bits
Offset 的長度，要能定址一個 page 大小( 4KB = 2^12 byte) ，
所以 Offset 長度為 12 bits 邏輯位址有 32bits 扣去 Offset 的 12 bits ，
還剩 20bits，這表示一個 process 最多用 2^20 pages ，
所以系統中 page table 最多有 2^20 個 entry
page table size 最大會是： 2^20 * 4bytes(每個 entry 大小) = 4MB
[解決 page table 太肥的問題]
1. 使用 multilevel Paging
2. 使用 Invert Page table
直接從 physical memory 的觀點去看，若實體記憶體有 n 個 frame，
則反轉分頁表會有 n 個 entry。記錄 frame 存放的東西
是哪個 process 所有 ：
[ Segment Memory ]
1. 將 physical memory 視為一個夠大的連續可用空間
2. 將 logical memory 視為一組 segment(段) 的集合，像是 code, data segment.
3. 段與段之間可以用非連續配置，但就單一段而言，必須是連續性配置。
4. 準備一個 segment table ，記錄每個 segment 的起始位址(base) 與大小(limit)
5. logical address 會是兩個量，因為每個 segment大小都不同。 [segment][offset]
6. 會有外部碎裂的問題 (要找連續空間，來放置一個 segment)
7. 易於進行 memory sharing 與 protection (因為分段觀點與設計者相同)
[ Virtual Memory ]
允許 program size 大於 phsical memory size 之下，program 仍可執行。
使用的是 demand paging 技術，程式在執行之初，並不會將全部 process 載入
到記憶體中，而是僅載入執行所需的 pages 到 memory 中，其餘的 page是存在
backing storage 中。
如果 process 所需的 page 都在 memory 中的話，那麼執行的效果會如同一般
狀況。但如果 process 企圖存取一個不在 memory 中的頁面，那麼就會有
page fault 發生。
[Page Fault]
在 demand paging 的系統下，若執行中的 process 試圖存取不在 memory 中的
page 時，則會發生 page fault。
處理方式：
1. OS收到來自 MMU 發出的錯誤通知，該分頁不在memory中，
2. OS 暫停目前正在執行的 process，並檢查該位址是否合法
3. 如果位址合法，表示此為一個 page fault，
要到 memory 中找 free frame，用來存放 lost page
若無 free frame 可用，就要使用 頁面替代演算法(FIFO, LRU...)
4. OS 將 lost page 載入到可用 frame 並在 table 中標示 valid
5. 繼續剛才執行的 process
[Virtual Memory 效益]
p: page fault 的機率 ，則 effective memory access time 則為：
(1-p) * memory_access + p * page_fault_process_time
[Page Replacement Algo]
1. FIFO
2. LRU - 用 counter 或者 stack 實作
3. OPT
Belady異常
Process 分配到的 frame 數目增加，但 page fault 的發生次數反而逆勢變多。
使用 FIFO 的取代法則會有此問題。
[LRU 近似法則]
1. reference bit：固定週期會向右 shift 一格(捨棄)，值較小的表示近期未存取。
2. second chance：先以 FIFO 挑選 page 並檢查 ref bit，若為 1 則給予機會。
3. enhanced second chance：(Ref Bit, 修改 bit) 順序：(0,0) (0,1) (1,0) (1,1)
[ Thrashing ]
通常造成 Thrashing 現象之原因有三:
(1) Multiprogramming
(2) Global Page Replacement
(3) 頁框分配不足
當 process 所分配到的 frame 數目不足，很容易發生 page fault 而需要進行
分頁置換(page replacement) 的動作，所以 process 會去置換掉其他 process
的 page 結果造成其他 process 也發生了 page fault 無法繼續運作。
此一現象循環發生，造成所有 process 皆在處理 page fault，
Disk I/O 極為忙碌，但 CPU 卻是 idle 的狀況。此時 multi-programming 會試圖
引進更多 process 來充份使用 CPU，反而加速惡化整個狀況。
可以用 working set model 來處理
預估各 process 在不同執行時期，所需要的頁框數，依此為基準配置 frame，
防止 thrashing 發生
[working set model 架構基礎]
program 在執行時，會有 locality 特性。分別是：
- temporal(時間): loop , sub routine , stack(頂端常在變動)
- spatial(空間) : array , 循序執行的程式
WSSi 表示 Pi 在某個時間所需要的 frame 總量
所以 D = ΣWSSi = 頁框總需求量
令 M = physical memory size
當 D > M 時，則 OS 會將某些 process swap out 直到 D <= M 為止
當 D <=M 時，則 OS 會依 WSSi 分配給 Pi 足夠的頁框數
[page size 愈小] (設計趨勢是朝 大size 設計)
1. page fault 機率愈高 (因為跨不同 page 的機率上升)
2. page table size 變大
3. I/O 讀寫次數變多，因為要做 swap out/in
4. 內部碎裂較不嚴重
5. locality 佳
very helpful,thank you!!
回覆刪除