主題
重點整理
程式引用記憶體位址的方式可以分為三種: compile-time, load-time, execution-time。execution-time是最有彈性也最廣泛使用的方式，它將memory address分為logical address(virtual memory address)及physical address，但需要硬體(memory management unit - MMU)的支援。
程式被載入至記憶體分為兩種方式: static 及 dynamic loading。static是一次將程式全部載入，dynamic則是在需要時載入
程式若用到lib需要做linking的操作，linking也分為static 及 dynamic linking。static會直接載入用到的lib，dynamic會查詢lib是否已經(jīng)在記憶體中，若有則將指標(biāo)指到已經(jīng)存在的lib，若無則載入lib。windows常見的DLL檔也是使用dynamic linking的技術(shù)。
當(dāng)程式暫時用不到時或記憶體快爆的時候會被放進(jìn)disk裡，需要時再從disk讀回記憶體，這個操作稱為Swap
記憶體分配的方式分為兩種: fixed-partition及variable-size partition。fixed-partition將記憶體切成固定大小，老師舉了停車場的例子，停車場的格子都是畫好的，只要停進(jìn)去就OK了。缺點是程式過多的話會塞不進(jìn)記憶體，而且容易產(chǎn)生Internal fragmentation造成浪費((就像重機停進(jìn)四輪車位)。variable-size partition將程式載入空閒的記憶體中，稱為"洞"，尋找洞有多種實作方式。這個方式會產(chǎn)生External fragmentation(無法被塞進(jìn)任何程式的"洞")。解決方式是在執(zhí)行期間使用Compaction，也就是對記憶體空間做整理，將Fragmentation變唯一塊連續(xù)的記憶體空間。
但是Compaction相當(dāng)耗時，無法頻繁使用，因此需要使用Paging的方式改善這個問題。Paging將記憶體分為多個固定大小的區(qū)塊，physical memory分出的區(qū)塊稱為Frames，logical address space分出的區(qū)塊稱為Pages，F(xiàn)rames跟Pages的數(shù)量是相同的，通常一個Page/Frame size為4KB。
Page跟Frame之間的mapping使用一個Page table來儲存，Page table由OS管理，儲存在OS的記憶體中
而因為有了Page table，MMU需要知道這個table在哪裡，因此在程式載入時OS也會將table的address傳進(jìn)MMU的register裡，這樣MMU才能做logical address至physical address的轉(zhuǎn)換。
但是這麼一來每次address轉(zhuǎn)換時就需要兩次讀取操作，一次是讀取table然後做translate，一次是讀取需要的physical address，相當(dāng)耗時。因此在MMU裡加入了叫做Translation Look-aside Buffers (TLB)的硬體，TLB可以將讀取過的Page快取起來，下次對相同Page查詢時可以省下一次對記憶體讀取的操作。TLB因為電路設(shè)計的方式，可以在O(1)的時間內(nèi)查詢，但價格相當(dāng)昂貴，空間也不大。使用TLB可以使記憶體讀取效率提升98%以上
隨著記憶體發(fā)展越來越大，Page entry也變得越來越多，這會使得page的查找變得相當(dāng)慢，且會使一個程式使用太多零散的記憶體空間，於是有三種解決辦法:
1.Hierarchical Paging : 簡單來說就是Page table的table，效能不好，隨著階層數(shù)量使查找次數(shù)變?yōu)镹倍。
2.Hash Page Tables : 改用hash table，效率最好但記憶體碎片零散，改良版將每個hash對應(yīng)的值改為array而非linked list。
3.Inverted Page Table : 捨棄page table只存frame table，節(jié)省大量空間，搜尋效率低且難以共享frame。
實際上程式是跟Segmentation做互動而非Paging，一支程式會被分為多個Segment，每個Segment可能包含main program,function, object ,local/global variables, stack, symbol table, arrays, etc…。address translation的流程會是logical address → segmentation unit → linear address → paging unit → physical address
在Intel Pentium的Logical-address space的address被分為兩類，一半是private一半是shared，因此當(dāng)一個segment產(chǎn)生時就會決定它是否可以共享
Review Slides (1)
3 types of address binding?
- compile-time : Compiler translates symbolic code into absolute code
- load-time : Compiler translates symbolic code into relocatable code
- execution-time : Compiler translates symbolic code into logical-address
- (i.e. virtual-address) code
- Special hardware (i.e. MMU) is needed for this scheme
- compile-time : Compiler translates symbolic code into absolute code
- load-time : Compiler translates symbolic code into relocatable code
- execution-time : Compiler translates symbolic code into logical-address
- (i.e. virtual-address) code
- Special hardware (i.e. MMU) is needed for this scheme
compile-time：編譯器將符號碼轉(zhuǎn)換為絕對程式碼，編譯後將記憶體位置寫死在program，速度最快但只能使用指定的記憶體，很大程度影響記憶體的彈性
load-time：編譯器將符號代碼轉(zhuǎn)換為可重定位程式碼
execution-time：編譯器將符號代碼轉(zhuǎn)換為邏輯位址
（即虛擬位址）代碼
此方案需要特殊硬體（即MMU）
logical address? physical address?
Logical address – generated by CPU (a.k.a. virtual address)
Physical address – seen by the memory module
邏輯位址 – 由 CPU 產(chǎn)生（又稱虛擬位址）
實體位址——記憶體模組看到的
virtual → physical mapping?
Memory Management Unit (MMU)
Hardware device that maps virtual to physical address
記憶體管理單元 (MMU)
將虛擬位址對應(yīng)到實體位址的硬體設(shè)備
dynamic loading? static loading?
static loading: load entire program into memory
dynamic loading: A routine is loaded into memory when it is called, need to add manually in program to load/unload library
靜態(tài)載入：將整個程式載入到記憶體中
動態(tài)載入：例程在呼叫時載入到記憶體中，需要在程式中手動新增載入/卸載函式庫
dynamic linking? static linking?
Static linking: libraries are combinedby the loader into the program in memory image, faster
Dynamic linking: Linking postponeduntil execution time, only one code copy in memory andshared by everyone
靜態(tài)連結(jié)：庫由載入器組合到記憶體映像中的程式中，速度更快
動態(tài)連結(jié)：連結(jié)推遲到執(zhí)行時間，記憶體中只有一份程式碼副本並由所有人共享
Review Slides ( 2 )
Swapping?
A process can be swapped out of memory to a backing store, and later brought back into memory for continuous execution
進(jìn)程可以從記憶體交換到後備存儲，然後再帶回記憶體以持續(xù)執(zhí)行
Contiguous memory allocation?
- fixed-size memory allocation?
- Each process loads into one partition of fixed-size
- Degree of multi-programming is bounded by thenumber of partitions
- 每個進(jìn)程載入到固定大小的一個分割區(qū)中
- 多程式設(shè)計的程度受分區(qū)數(shù)量限制
- Each process loads into one partition of fixed-size
- Degree of multi-programming is bounded by thenumber of partitions
- 每個進(jìn)程載入到固定大小的一個分割區(qū)中
- 多程式設(shè)計的程度受分區(qū)數(shù)量限制
- variable-size memory allocation?first-fit, best-fit, worst-fit?
- Hole: block of contiguous free memory
- Holes of various size are scattered in memory
- First-fit – allocate the 1st hole that fits
- Best-fit – allocate the smallest hole that fits (Must search through the whole list )
- Worst-fit – allocate the largest hole
- 洞：連續(xù)的空閒記憶體區(qū)塊
- 記憶體中散佈著大小不一的洞
- 首次適配 – 分配第一個適合的孔
- 最佳擬合 - 分配適合的最小孔（必須搜尋整個清單）
- 最差擬合 – 分配最大的孔
- Hole: block of contiguous free memory
- Holes of various size are scattered in memory
- First-fit – allocate the 1st hole that fits
- Best-fit – allocate the smallest hole that fits (Must search through the whole list )
- Worst-fit – allocate the largest hole
- 洞：連續(xù)的空閒記憶體區(qū)塊
- 記憶體中散佈著大小不一的洞
- 首次適配 – 分配第一個適合的孔
- 最佳擬合 - 分配適合的最小孔（必須搜尋整個清單）
- 最差擬合 – 分配最大的孔
External & internal fragmentation?
External fragmentation: total free memory space is big enough to satisfy a request, but is not contiguous, Occur in variable-size allocation
Internal fragmentation: memory that is internal to a partitionbut is not being used, Occur in fixed-partition allocation
外部碎片：總可用記憶體空間足以滿足請求，但不連續(xù)，發(fā)生在可變大小分配中
內(nèi)部碎片：分區(qū)內(nèi)部但未使用的內(nèi)存，發(fā)生在固定分區(qū)分配中
compaction?
Shuffle the memory contents to place allfree memory together in one large blockat execution time
Only if binding is done at execution time
執(zhí)行時打亂記憶體內(nèi)容，將所有空閒記憶體放在一個大塊中
僅當(dāng)綁定在執(zhí)行時完成
Review Slides ( 3 )
Memory frame? page? typical page size?
- Divide physical memory into fixed-sized blocks called frames
- Divide logical address space into blocks of the same size calledpages
- typical page size is 4KB
- 將物理記憶體劃分為固定大小的區(qū)塊（稱為幀）
- 將邏輯位址空間分割成相同大小的區(qū)塊（稱為頁）
- 典型頁面大小為 4KB
Page table? virtual → physical translation?
Each entry maps to the base address of a page inphysical memory
A structure maintained by OS for each process
Page table includes only pages owned by a processA process cannot access memory outside its space
virtual → physical translation through MMU
每個條目映射到物理記憶體中頁面的基底位址
作業(yè)系統(tǒng)為每個行程維護(hù)的結(jié)構(gòu)
頁表僅包含進(jìn)程擁有的頁 進(jìn)程無法存取其空間之外的內(nèi)存
透過MMU進(jìn)行虛擬→實體轉(zhuǎn)換
What is PTBR register? When to update it?
Page-table base register (PTBR)
- The physical memory address of the page table
- The PTBR value is stored in PCB (Process Control Block)
- Changing the value of PTBR during Context-switch
頁表基址暫存器 (PTBR)
- 頁表的實體記憶體位址
- PTBR值儲存在PCB（Process Control Block）中
- 在Context-switch期間更改 PTBR 的值
Memory reads # for each reference?
With PTBR, each memory reference results in 2 memory reads, One for the page table and one for the real address
使用 PTBR，每次記憶體引用都會導(dǎo)致 2 次記憶體讀取，一次用於頁表，一次用於實際位址
HW support for paging speed?
Associative Memory
All memory entries can be accessed at the same time
A cache for page table shared by all processes
TLB must be flushed after a context switch
由關(guān)聯(lián)記憶體 (HW) 實作的翻譯後備緩衝區(qū) (TLB) (HW)
聯(lián)想記憶
所有記憶體條目可以同時存取
所有進(jìn)程共享的頁表緩存
上下文切換後必須刷新 TLB
memory protection by page table?
每個頁都與頁表中的一組保護(hù)位相關(guān)聯(lián)
page table memory structure?
- associative memory
- TLB
Associative Memory
All memory entries can be accessed at the same time
- Each entry corresponds to an associative register
- Typical number of entries: 64 ~ 1024
A cache for page table shared by all processes
TLB must be flushed after a context switch
- Otherwise, TLB entry must has a PID field(address-space identifiers (ASIDs) )
由關(guān)聯(lián)記憶體 (HW) 實作的翻譯後備緩衝區(qū) (TLB) (HW)
聯(lián)想記憶
所有記憶體條目可以同時存取
- 每個條目對應(yīng)一個關(guān)聯(lián)暫存器
- 典型條目數(shù)：64 ~ 1024
所有進(jìn)程共享的頁表緩存
上下文切換後必須刷新 TLB
- 否則，TLB 條目必須具有 PID 欄位（位址空間識別碼 (ASID)）
memory protection by page table?
- valid, invalid bits?
每個頁都與頁表中的一組保護(hù)位相關(guān)聯(lián)
page table memory structure?
- hierarchical → 2-level, 3-level, etc
- Break up the logical address space into multiple pagetables
- 將邏輯位址空間分解為多個頁表
- hash table → linked list
- Commonly-used for address > 32 bits
- Virtual page number is hashed into a hash table
- 常用於 > 32 位元的位址
- 虛擬頁號被散列到哈希表中
- inverted page table
- Maintains NO page table for each process
- Maintains a frame table for the whole memory
- 不為每個行程維護(hù)頁表
- 維護(hù)整個記憶體的幀表
How are pages shared by different processes?
Paging allows processes share common code, which must be reentrant
Shared code must appear in the same location in the logical address space of all processes
分頁允許進(jìn)程共享公共代碼，這些代碼必須是可重入的
共享程式碼必須出現(xiàn)在所有程序的邏輯位址空間中的相同位置
Review Slides ( 5 )
Segmentation vs. Paging?
Paging
segmentation
Length
Fixed
Varied
Fragmentation
Internal
External
Table entry
Page number→frame number
Seg ID → (base addr, limit length)
View
Physical memory
User program
Paged segmentation?
- Apply segmentation in logical address space
Paging allows processes share common code, which must be reentrant
Shared code must appear in the same location in the logical address space of all processes
分頁允許進(jìn)程共享公共代碼，這些代碼必須是可重入的
共享程式碼必須出現(xiàn)在所有程序的邏輯位址空間中的相同位置
Review Slides ( 5 )
Segmentation vs. Paging?
| Paging | segmentation | |
| Length | Fixed | Varied |
| Fragmentation | Internal | External |
| Table entry | Page number→frame number | Seg ID → (base addr, limit length) |
| View | Physical memory | User program |
Paged segmentation?
- Apply segmentation in logical address space
- Apply paging in physical address space
- 在邏輯位址空間中應(yīng)用分段
- 在實體位址空間中應(yīng)用分頁
- 在邏輯位址空間中應(yīng)用分段
- 在實體位址空間中應(yīng)用分頁
達(dá)人
