Paging

• Process的physical address space可以是不連續的狀態，且只要後者可用，process就會被分配到記憶體。

1. 避免外部碎片的產生。
2. 避免memory chunks有不同尺吋的問題。

• 劃分physical memory到固定大小區塊的稱作為「frames」。

1. 尺寸大小是2的冪數。

• 劃分logical memory到相同大小區塊的稱作為「pages」。
• 追蹤所有的free frames。
• 執行依大小為N pages的程式，需要去找到N個free frames和下載程式。
• 設置一個page table去轉換從logical address到physical address
• Backing store同樣被分為pages。
• 依然會有內部碎片的存在。

Address Translation Scheme

• 由CPU產生的address被分成兩部分：

1. Page number(p)：用類似於page table的索引表，起該表包含physical memory中每個page的base address。
2. Page offset(d)：和base address連結、定義並發送到memory unit的physical memory address。

Implementation of Page Table

• Page table是留在主記憶體中。
• Page-table base register(PTBR)：指向page table。
• Page-table length register(PTLR)：指示page table的大小。
• 在這個scheme中，每個data、指令存取都需要兩個記憶體：

1. 一個給page table使用，另外一個給data根指令。

• 兩個記憶體存取問題可以使用稱為Associate Memory或是Translation Look-aside Buffers(TLBs)的特別快速尋找硬體快取來解決。
• 一些TLBs在每個TLB entry中，儲存address-space identifies(ASIDs)，且每個process都有獨特的識別碼去提供address-space保護process。

1. 此外需要在環境轉換時進行flush。

• TLBs通常大小很小。
• 將錯過的TLB值加載入TLB中，讓下一次可以更快速的存取。

1. 更換策略方法是需要慎重考慮的。
2. 一些entry可以被使用於永久快速的存取中。

Associative Memory

• 是平行搜尋的模式。
• Address translation(p,d)：

1. 如果p在相關寄存器中，便會得到frame #out的指令。
2. 否則就是在記憶體中得到frame #from 的page table。

Effective Access Time

• 相關查找 = ε個時間單位。

1. 可少於記憶體存取時間的10%。

• Hit ratio(命中率) = α ：

1. 在相關暫存器中找到page數量的時間百分比。
2. Effective Access Time(EAT) = (1+ε)α+(2+ε)(1-α) = 2+ε-α。

Memory Protection

• 執行記憶體保護是由保護bit和每個frame的相關聯並指示是否允許read-only或read-write的存取操作。
• 在page table中附加valid-invalid到每個entry中：

1. Valid：指示相關page是在process的logical address空間中，因此是個合法的page。
2. Invalid：指出相關page並不在process的logical address空間中。
3. 可以使用Page-table length register(PTLR)。

Shared Pages

• Shared code：

1. 在process之間共享read-only code的一個複製。
2. 類似於和多重執行緒共享相同的process空間。
3. 如果read-write page的共享是允許的話，對於process間的溝通是很有幫助的。

• Private code and data：

1. 每個process會保留code跟data的單獨複製。
2. private code跟data可以在logical address空間中的任何地方出現。

Structure of the Page Table

• 使用簡單的方法就可以取得page的記憶體架構：

1. Page的尺寸大小為4 KB。
2. 一個Page table擁有1百萬個entries。
3. 如果每個entry是4 bytes，則4 MB的physical address空間或記憶體就僅限用在page table。

Hierarchical Page Tables

• 分割logical address空間到multiple page tables。
• Two-level page table是一個簡單的技術。
• 接著使用者會翻閱這些table。

Two-Level Paging Example

• 一個logical address被分成：

1. 由22 bits組成的page number。
2. 由10 bits所組成的page offset。

• 既然page table已經被分頁了，則page number會更進一步被分成：

1. 一個12 bit的page number。
2. 一個10 bit的page offset。

64-bit Logical Address Space

• 甚至是two-level paging scheme都不足夠使用。
• 如果page的大小是4 KB的話：

1. 則page table擁有2^52個entries。
2. 如果是two level scheme的話，page table內部可能就會有2^10個4 byte entries。
3. 而page table外部會有2^42或2^44個entries。
4. 有一個解決方法就是再加入2^nd的外部page table。
5. 但有可能造成4個記憶體存取權限會到達一個physical memory的位置上。

Hashed(散列) Page Tables

• 適合使用的地址空間要大於32b its。
• 虛擬地址(virtual page)的數量會散列在page table中。

1. 此page table則包含散列到同一位置的同一元素。

• 每個執行都包含：

1. 虛擬地址的數量。
2. 對應到page frame的值。
3. 指向下一個元素。

• 虛擬pag數量是在這個chain中比較搜尋匹配的。

1. 如果找到相符的，則提取相對應的physical frame。

• 64-bit地址的變化是個clustered page tables。

1. 和散列相似，但每個entry會參考好幾個pages(例如16個)而不是只有一個。
2. 對於疏散地址空間是特別有用。

Inverted Page Table

• 並不是每個process都有一個page，並追蹤所有可能的logical page跟所有的physical address。
• 是每個實際記憶體page中的一個entry。
• Page的entry由virtual address所組成，儲存在實際的記憶體位置。
• 降低儲存每個page table的記憶體需要，但增加發生page引用時搜尋table的所需時間
• 使用hash table會將搜尋限制為一個或多個的page-table entries。

1. TLB可以加速存取。

Oracle SPARC Solaris

• 目標是要有效率且低負荷。
• 以散列為基礎，可是卻更加複雜。
• 有兩個hash table：

1. 一個給kernel使用，另一個給所有的user process使用。
2. 每個映照的記憶體位置是從virual到physical memory。
   ==>所以比每個page擁有分離的hash-table entry要更有效率。
3. 每個entry有擁有base跟span(也就是表示pages的entry數量)。

• TLLB會處理translation table entries(TTE)給硬體尋找。

1. TTE的快去會駐留在translation storage buffer(TSB)。

• 引用了虛擬地址的話，就會造成TLB的搜尋動作：

1. 如果錯過，硬體便會進入記憶體中，尋找對應該地址的TTE。
   1- 如果找到相符合的，CPU會複製TSB的entries到TLB中並完成轉換。
   2- 如果沒有找到相符合的，就會中斷kernel而去搜尋hash table。然後kernel會從合適的hash table中新增一個TTE，並儲存在TSB中，倘若有哪個已經完成轉換了，就會打斷它的處理並控制返回到MMU中。

==>此章節的介紹就到這裡一段落，對我來說這個章節比前幾章要來的複雜點，所以有需多不足的地方，如果想了解更多關於記憶體管理的話，可以再繼續去搜尋資料，補充知識喔!