[Operating System Cheat sheat] — Memory Management

1. Binding Time
2. Contiguous Memory Allocation
3. External fragementation/Internal fragementation
4. Page Memory Management
5. Page Table implementation method
6. Segment Memory Management
7. Paged Segment Memory Management
8. Virtual Memory
9. Demand paging
10. Page fault
11. Page replacement
12. Thrashing
13. Working-set Model

Binding

決定程式(process)執行的起始位址，以及分配變數(variable)真正的記憶體位置，此一動作稱之。

共有三個時機點 :

1. Compiling Time
   — 由 Compipler 作 Binding
2. Loading Time / Linking Loading Time
   — Linking Loader 或 Linking Editor
3. Execution Time
   — 由 OS動態決定，也叫作Dynamic Binding

我們逐一說明 :

Compiling Time

Compiling Time 由 Compiler 作 Binding: 產生之 object code 叫作
”Absolute” object code。後面的loader 叫作”Absolute”loader,主要是作 Allocation 與 Loading only。

其程式碼起始位址亦為Memory實際位置

<缺點>
Process若要改變起始位址，則必須Re-Compile ，非常不便。

Loading Time

Loading Time 由 Linking Loader 作 Binding : Compiler 所產生的 object code

叫作”Relocatable” object code(可重新定位之目的碼)

Note . Relocatable object code 在 compile time時產生(未知 value)，是在load time時才分配給值(確定 value)。

Linking Loader 主要4個工作

1. Allocation:向OS要求起始位址
2. Loading : object code載入到 Memory
3. Linking: 依 Compiler所交辦之Linking修正資訊,執行Linking 修正
   (???改成 8000)
4. Relocation:作重定位修正

<優點>
程式的起始位址若要改變,則無需重新Recompling,直接Linking即可

<缺點>

1.程式重新執行,若modules數多,則Re-linking很花時間

2.Process執行期間,不可更改起始位址

Note:凡是”Static”Binding,皆無法更改

Dynamic Binding(Execution Time 由 “MMU” 作 Binding)

決定Process起始位址之工作,延到執行時期(Execution Time)才動態執行,即Process在執行期間,可任意變更起始位址,且Process仍能正確執行。

需要硬體支援 (MMU)

1. Logical Address : generated by CPU

2. Physcial Address: 實際去 Physical Memory(RAM)存取之位址

Logical Address = Physical Address,稱為 Static Binding
Logical Address !=Physical Address,稱為 Dynamic Binding
(Page, Segment,Paged Segment)

若有 Logical Address 轉成 Physical Address之運作,皆由硬體負責,而

該單元叫 MMU(Memory Management Unit)

<優點>

Process之起始位址可於執行時間任意更動,且能正常執行,有助於OS記憶體管理之彈性度
(ex: Compaction 實施,Process swap out 後再swap in,不一定要相同起始位址)

<缺點>

1.需要硬體支援(MMU)

2.Process執行時間較久,效益較差

Dynamic Loading

也稱作 "Load-on-call"，在執行期間，若此Module真正被呼叫而且不在memory中時，此時loader 才將其載入到memory 中

Dynamic Linking

在Execution Time中，若Module被呼叫時，才將之載入並且並且與其他Modules做Linking修正(外部符號之解決)，通常用於Library Linking(ex:Dynamic Linking Libray,dll)

Note.
只有Dynamic Binding需要 HW (MMU)支援

Contiguous Memory Allocation

也叫作Dynamic Varible Partition Memory Mangement
(動態變動分區記憶體管理)

OS必須配置 process — 個連續的Free Memory Space

Partition :

l. Process 所估用的Memory Space

2. Partition數目 =process數目 = multiprogramming degree，由於不同時

期，系統內process數目不固定，所以Partition 數目不固定(Dynamic)

3. 由於各個process size不盡相同，所以各Partition 就不一定相同
(Variable Memory中會有一些 Free Memory Space (or Block)叫 Hole，通常OS會用Linked-List 觀念管理這些 Holes，叫作AV-List
(Available List,可用空間串列)

配置方式有 3 種 :

1. First fit
   — 從 AV-List頭開始找起，直到找到第一個hole，其hole size≥ process size為止，即可配置、或找完整條串列，無一夠大為止(linear search)
2. Best fit
   — 必須檢査 AV-List 所有holes，找出一個hole，其hole size ≥ process
   size，且 hole size 減去 process size後，差值”最小”的hole，予以配置。
3. Worst fit
   — 必須檢查 AV-List 所有 holes，找出一個hole，其 hole size ≥
   process size且hole size減去 process size 後，差值”最大”的hole，予以配置

Internal fragmentation

配置給Porcess之空間，超過Process實際size ，兩者之差值空間，造成此Process使用不到，其他Process亦無法使用，是記憶體空間的浪費。

External fragmentation

上述 Contiguous Memory Allocation方法，均會遭遇"外部碎裂"。

在 Contiguous Allocation 要求下，目前 AV-List中任何一個hole size均小於
Process size， 但這些 Holes size 加總卻 ≥ Process size。然而，因為這些Holes並不連續，因此仍無法配置給Processs，造成空間閒置不用，Memory利用度低之問題。

<解決方法>

1. Compaction …真正解決
2. Multple Base/Limit Register … 降低造成的機會
3. Page Memory Management … 真正解決

1. Compaction
   移動執行中的Process ，使得原本非連續的 ，得以聚集形成一 個夠大的連續Free Memory Space。

Compaction

困難點 :
a. 不容易制定最佳的Compaction策略
b. Process 必須是Dynamic Binding才能夠在執行期間移動。

2. Mulitple Base/Limit Register

拆分Process成Code Section以及Data Section分開配置給hole ，以降低外部碎裂發生的機率。因此每個Process需至少2套Base/Limit Register，分別記錄 Code Section與Data Section的起始位址與大小。

3. Page Memory Management(分頁法)

OS 會將 disk 中的資料分割成固定大小的區塊，稱為頁（pages）。當不需要時，將分頁由 memory 移到 disk ；當需要時再將資料取回載入 memory 中。分頁是磁碟和記憶體間傳輸資料塊的最小單位。

a. Physical Memory(RAM)
視為一組Frame(頁框)之集合，且各Frame size 相同。

Note : Frame是硬體決定，OS只是配合，分頁是採 Physical Viewpoint

b. Logical Memory(即 user process大小)
又稱Virtual address，視為一組Page(頁面)之集合,且Page size = Frame size

c. 配置方式
OS採”非連續性”配置原則，即若Process大小=n個Pages，則OS只需依 Physical Memory，挑出n個Free Frames(不一定要連續)，就可以配置給此 Process

d. Page Table
OS會替每個process建立一個Page Table(分頁表)，記錄各個process 配置於
哪個 Frame 之 Frame Number，若 Process大小=n個 Pages，則它的Page
Table就會有n個entry。

優點：

• 解決 external fragmentation問題
• 可以支援記憶體的共享(Sharing)：不同 page 對應相同的 frame。
• 可以支援記憶體的保護(Protection)：在分頁表上多加一個 protection bit 欄位 — R : 表示Read only、RW : 表示Read/Write皆可
• 支援 Dynamic Loading 及 Virtual Memory 的製作

缺點：

• 會有 internal fragmentation 問題 (page size 愈大愈嚴重)
• memory 有效存取時間較長 (logical address 轉 physical address)
• 需要額外的硬體支援(logical 轉physical address by M.M.U、Page table)
• page table implementation (每個 Process 皆有 1 個 page table)
• logic address -> physical address (用到搜尋器、加法器)

Logical address to Physical address by MMU

(假設 Page size = 10)
1. Logical Address初始是單一量,自動拆解成(p,d),其中p代表Page
Number、d 代表 Page offset(頁偏移)
2.依p査詢Page Table,取得該 Page 的 Frame Number,令為 f
3. f與d合成(f,d)、或 fPage size+d,即為 Physical Address
ex : (p,d)=(3,2),依p=3查表,其Frame Number=f7=> (7,2)=
Physical Address = 7*10+2 = 72

Page Table Implementation method

[Method 1]
使用”Register” 保存 Page Table中每個 entry 內容。

優點:
査詢 Page Table 無需Memory Access，速度最快

缺點:
不適合用於大型的Page Table(或大型的Process)，因為reg數量有限

Memory Access次數 : 1次

[Method 2]

使用Memory保存分頁表，且用一個Register :
PTBR(Page Table Base Register)記錄在Memory中之位址; 或者也有 PTLR(Page Table Length(size) Register來記錄 Page Table 大小。

優點:
適用於大型分頁表

缺點:
速度慢，因為需要額外一次 Memory Access 來存取 Page Table

Memory Access次數 : 2次

[Method 3]

用來改善Method 2每次都要存取兩次Memory所造成的時間花費，因此
使用 TLB (Translation Lookaside Buffer)

(或叫關聯式暫存器Associative Register)

Note . TLB 是 full associate cache。

保存 Page Table中經常被存取之Page Number 及 Frame Number，且完整的Page Table 存於 Memory 中。

使用 TLB 之Effective Memory Access Time =

p*( TLB Time + Memory Access Time)+ (1-p)*(TLB Time + 2*Memory Access Time) , where p is TLB hit ratio

Example

Page Table 太大之解決方案

1. Multi-level paging
2. Hash Page table
3. Inverted Page Table
4. Limit reg

Multi-level paging

藉由此法,不需將整個Page Table全部載入Memory中,而是載入部分所需要的內容,因此提出多層次的分頁作法。

• Level 1 Page Tabe: 有2^x個 entry,每個 entry 記錄某個 Level 2 Page Table 之pointer (address)
• Level 2 Page Table: 有2^y個 entry,每個 entry記錄Frame Number。

Process在執行時,只需1個Level 1 Page Table 與一個 Level 2 Page Table 在
Memory中即可。因此可以大幅減少 Page Table 估用 Memory Space

缺點 :
Effective Memory Access Time更久,因為需要多次Memory Access。

Note

With multilevel page tables, the more levels a page table has, the higher the TLB miss penalty will be.

Example.

Hashing Page Table(雜湊分頁表)

利用 Hashing技巧，將 Page Table 視為 Hash Table。

有相同的Hashing Address 的 Page Number,及它的 Frame Number資訊,會置入於同一個entry(Bucket)中，且以 Linked-List(chain)
串接欄位<Page No,Frame No>。

Note.即其解決Collision的方法是使用 Chain

缺點
使用Linear Search 在 Linked-List中找符合的 Page No,較為耗時。

Inverted Page Table

是以Physical Memory(RAM)為記錄對象,並非以Process為對象。

若有n個Frames,則此表就有n個entry,每個entry 記錄
<Process ID, PageNumber>,配對資訊,代表此Frame存放的是哪個Process的哪個Page,整個系統只有一份表格。

缺點:
1.必須使用<Process ID, Page Number>資訊一一比對查詢,此舉甚為耗時
2.喪失了”Memory Sharing”之好處,即無法支援其實現

Segment Memory Management

Virtual Memory

主要目的 :
允許Process 在超過Physical Memory可用空間大小情況下,Process仍能執行。
(是OS的責任(負擔)Programmer無啥負擔)

Logical memory can be much more than physical memory

優點
l. Memory利用度較高
2.盡可能地提高Multiprogramming Degree、增加 CPU利用度
(Note :Thrashing 除外)
3. IO Transfer Time 較小
(Note : IO次數 Total Time 增加)
4.Programmer只需專心寫好程式即可,無需煩惱程式過大、無法執行的
問題,這是OS的責任。所以Programmer也不需要過時的Overlay技術

為了要實現Virtual Memory 我們需要Demand Paging技術的實現

Demand Paging

是架構在 Page Memory Management 基礎上。

差別:
在於採用”LazySwapper”的觀念,即Process執行之初,無需事先載入全部的Pages,而是只載入部分的Pages(甚至不載入任何Page、Pure Demand Paging),Process即可執行。若Process執行時,它所需要的Pages 皆在Memory中,則Process本身一切正常地執行。
若Process執行時,企圖存取不在Memory中的Pages,則稱為發生Page Fault,OS 必須處理。將Process 所需的”Lost” Page從 Disk載入到Memory中,Process才可執行。

在分頁表中,需引進一個欄位: Valid/Invalid Bit,用以區分此Page是否在
Memory 中 .
1.Valid表示有在Memory中

2. Invalid 則表示沒有在Memory中

Note:此Bit是由 OS設定更改、MMU只負責 Reference/讀取

Page fault Steps

Page fault is considered as trap (exception) not interrupt .

1. MMU 會發出一個”Address Error” Interrupt 通知OS … [算是trap]

2.OS收到中斷後,必須暫停,目前Process之執行且保存其Status Info

3.OS檢查Process之存取位址是否合法。
若非法,則終止Process;
若合法,則OS判定是由Page Fault 所引起

4.OS先到Memory中檢查有無Free Frame
若沒有,則必須執行”Page Replacement”工作以空出一個 Free Frame

5. OS再到Disk 中找出Lost Page所在位置,啟動1O運作,將Lost Page載入到Free Frame 中

6. OS 修改 Page Table 記錄此 Page 的 Frame Number、以及將 Invalid 值改為Valid 值

7. OS恢復中斷之前Process 的執行。

影響Page fault的因素

l. Page Replacement 法則之選擇

2. Frame數分配多寡之影響

3. Page size 之影響

4. Program Structure 之影響

Page Replacement

當 Page Fault發生,且Memory中無 Free Frame時,OS必須執行此工作,即選擇一個 Victim Page (or the Replaced Page),將它 Swap out 到 Disk保存,以空出一個

Note . 會額外多出一個 DiskIO 運作,因此Page Fault Process Time 更久

如何降低Swapout此一額外IO次數

作法:

在Page Table再多引進一欄位:Modification Bit(或 Dirty Bit),用以
表示此Page上次載入後到現在,內容是否被修改過:0表無修改、1表有
修改。

OS可檢査Victim Page 的 Modification Bit值 :
若為0,則無需Swapout,因此可降低IO次數
反之,則需要Swapout

Note:
此 Bit由MMU設定修改,OS作Reference(反之是 Valid Bit由OS設定,MMU Reference)

Page Replacment 法則

1. FIFO
2. OPT
3. LRU
4. LRU 近似
   (1) Additional Reference Bits Usage
   (2) Second Chance
   (3) Enhanced Second Chance
5. LFU 與 MFU
6. Page Buffering Algorithm(機制)

FIFO 法則

最早載入(Loading Time最小)的 Page,選為 Victim Page

Example
給予3個Frames. Initially, they are all empty(或 Pure Demand Paging) ,有下列的 Page Reference String,求 Page Fault次數:
7,0,1,2,0,3,0, 4,2,3,0,3,2, 1,2,0, 1,7,0,1

Thrashing

<解決之道>
1. Decrease the degree of multiprogramming
2. Install more main memory

Working-set