2月 15, 2011

記憶體管理(Memory Management)

外部碎裂 (External Fragmentation)
系統中,所有可用空間總和大於某個 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 佳

1 則留言: