# OS筆記-Chapter 8: Main Memory

###### tags: `OS`
---
#### 目錄
* 總論
[Chapter 1: Introduction](https://hackmd.io/NoZq3J7IQvOQpcbo_tctjA)
[Chapter 2: Operating-System Structures](https://hackmd.io/OKykRLBESI6v9a13HgS35A)
* 行程管理
[Chapter 3: Processes](https://hackmd.io/HOqN-iQ3RIKIC-NB9QjBIQ)
[Chapter 4: Threads](https://hackmd.io/qzAIHeSASmKuecdkqidmHw)
[Chapter 5: CPU Scheduling](https://hackmd.io/IT5g2wHzTdOtMSDXPVEpOw)
[Chapter 6: Process Synchronization](https://hackmd.io/rv-PNe3ESxi08PElyUTc4Q)
[Chapter 7: Deadlocks](https://hackmd.io/Uu0jDK-rSyKNKq690y146g)
* 記憶體管理
<font color="red">Chapter 8: Main Memory</font>
[Chapter 9: Virtual Memory](https://hackmd.io/yirxZFn8Rz2wT56AAR7Sxw)
* 儲存裝置
[Chapter 10: File-System Interface](https://hackmd.io/aNPWKsFhTlGc-WFgQ__KRg)
[Chapter 11: File System Implementation](https://hackmd.io/bFcrlmefQsGp6hZdbI1MHQ)
[Chapter 12: Mass-Storage Systems](https://hackmd.io/9Y7Qo0OERda6htK7OOI36Q)
[Chapter 13: I/O Systems](https://hackmd.io/VNwXrhJPSo-l_t9tUBhYIg)
* 保護和安全
[Chapter 14: Protection](https://hackmd.io/izkd4JwXRwub_ZmhSMTlNw)
[Chapter 15: Security](https://hackmd.io/ofyvDidvQf-PxLMMZYhtsg)
---

### 背景說明(Background)
* 主記憶體(main memory)和建立在處理器內的暫存器(register)是CPU唯一可以直接存取的記憶體

* 記憶體存取可能需要許多週期才能完成，在這情況下處理器通程需要停待(stall)

* 快取記憶體(cache):用來配合存取速度的差異的記憶體緩衝器，在記憶體與CPU之間

* 必須保護作業系統免於使用者行程存取
* 基底暫存器(base register):最小合法的記憶體位址
* 界限暫存器(limit register):範圍大小
* 只有作業系統能設定基底和界限暫存器

* 位址連結
* 輸入佇列(input queue):磁碟上正等待被載入到記憶體執行的所有行程
* 通常編譯程式將原始程式中的位址連結(bind)重新定位的位址(如離開使處14個位元)，鏈結編輯程式或載入程式再將重新定位的位址連結致絕對位址
* 編譯時間(compile time):若已確知行程在記憶體中的位址，產生絕對碼(absoulte code)，如果一段時間後，起始位置改變，必須重新編譯
* 載入時間(load time):不能確定行程在記憶體中的位址，產生可重定位碼(reloactable code)，如果一段時間後，起始位置改變，只需重新載入
* 執行時間(execution time):如果行程能夠被由原來的記憶體段落移至另一段落，連結的動作將到執行時才發生

* 邏輯位址空間與實體位址空間
* 邏輯位址(logic address):由CPU產生的位址，通常叫做虛擬位址(virtual address)
* 實體位址(physical address):被記憶體單元鎖看到的位址
* 編譯時間和載入時間:邏輯位址與時體位址相同
* 執行時間:邏輯位址與時體位址不同
* 記憶體管理單元(MMU,Memory-Management Unit):將虛擬位址對映到實體位址
* 基底暫存器被稱為重定位暫存器(relocation register)
* 使用者不知道實體位址

* 動態載入
* 行程大小受限於記憶體大小
* 為了得到較佳的記憶體使用率，常式只在被呼叫時才載入
* 不須作業系統提供特殊支援，設計程式時就必須考量

* 動態鏈結
* 動態鏈結程式庫(dynamically linked library):程式執行時，才連結到使用者程式的系統程式庫
* 是連結而非載入，執行時才發生
* 記號(stub):一小段程式來指示如何去尋找程式庫副程式
* 須要從作業系統得到一些幫助

* 共用程式庫
* 動態鏈結的方式
* 可以重新鏈結以獲得新程式庫的存取

### 置換(Swapping)
* 藉由暫時將行程由記憶體置換到備份儲存體(backing store)，增加系統多元程式的程度

* 標準置換
* 分派程式(dispatcher)檢查準備要執行的行程是否在主記憶體中，如果不是，則檢查主記憶體可用空間是否足夠，若不夠，分派程式會換出一個行程，並換入藥執行的行程
* 內容轉換(context-switch)花費大量時間
* 100MB的行程要換入，傳遞速度50MB，則換入加換出要4秒，也就是4000毫秒，跟CPU運算速度比起來，非常耗時
* 必須確定被換出的行程必須完全閒置
* 若等待I/O的行程被置換，可能存取到錯誤的記憶體位置
* 等待I/O的行程不能被置換
* 只有在進入作業系統緩衝器的行程才能執行I/O，且作業系統與行程間的資料交換，只能在行程被換入時才能執行

* 行動裝置的置換
* 通常不支援置換
* 要求應用程式放棄配置的記憶體
* Android會寫入應用程式狀態(application state)到快取記憶體，以便快速重啟

### 連續記憶體配置(Contiguous Allocation)
* 多重分割方法(multiple-partition method)
* 主記憶體分割成一些固定大小的分割(partition)
* 行程挑出可用分割使用

* 可變分割方法(variable-partition method)
* 洞(hole):主記憶體中未劃分的部分

* 動態儲存體配置問題(dynamic storage allocation problem)
* 最先配合(First-fit):配置第一個足夠大的空間
* 最佳配合(Best-fit):配置所有足夠大空間中最小的
* 最差配合(Worst-fit):配置最大的空間

* 斷裂(Fragmentation)
* 外部(external)
* 總記憶體空間足夠，但不連續
* 50-percent rule:因為斷裂導致N個配置區間將移失其他0.5N，那麼1/3的記憶體可能沒有利用到(1.5N=100%,0.5N=33%)
* 解決
* 聚集(compaction):行程採用動態重定位且程式執行完時，將不連續的記憶體聚集
* 允許邏輯位址不連續
* 內部(internal)
* 大小固定的區間，配置的記憶體可能比實際需要多，導致浪費

### 分段(Segmentation)
* 允許一個行程的實體位址不連續

* 程式人員用兩個量來指定每個位址
* 分段名稱
* 偏移量

* 因此邏輯位址由以下二元(two tuple)所組成:<分段號碼,偏移量>

* 雖然程式人員可以用二維的位址，但是記憶體實際上仍為一維
* 分段表(segment table):對照實際記憶體位址
* 偏移量需介於0與該分段界限值之間

### 分頁(Paging)
* 允許一個行程的實體位址不連續，且避免了外部斷裂，但有內部斷裂

* 實體記憶體被分為許多大小相同的欄(frame)
* 邏輯記憶體則被分為大小相同的頁(page)
* 當行程要執行時，頁被載入到可用的欄中

* 邏輯位址
* 頁數(page number):當作指向分頁表(page table)的索引
* 頁偏移量(page offset)
* 若邏輯位址空間為2ᵐ，而頁的大小為2ⁿ
* 每頁4位元組，32位元組記憶體
* 允許邏輯位址空間大於實際位址空間(重複對映)

* 分欄表(frame table):紀錄欄是否可用或已被配置

* 分頁法會增加內容轉換的時間

* 硬體的支援
* 分頁表可儲存於暫存器(register)
* 若分頁表太大，則存主記憶體內
* 耗時，儲存一個內容須兩次記憶體存取
* 分頁表基底暫存器(PTBR,page-table base register):用來指向分頁表
* 轉譯旁觀緩衝區(TLB,translation look-aside buffer)
* 高速記憶體
* TLB miss:頁數不再TLB中
* 硬體繞線固定(wired down):內容不能從TLB移除
* 儲存位址空間識別符號(ASID,address-space identifier):用來唯一識別行程，並提供該行程的位址保護
* 每次選中新的分頁表時，TLB應全部清除(避免使用錯誤位址)
* 有效記憶體存取時間(effective memory-acess time):
* TLB 命中率(hit ratio)= 80%，記憶體存取時間:100ns
* 0.8 * 100ns + 0.2 * (100 + 100) = 120ns

* 保護(Memory Protection)
* 保護位元
* 無效(invalid):不在行程的邏輯位址空間內
* 有效(valid):在行程的邏輯位址空間內，可存取
* 分頁表長度暫存器(PTLR,page-table length register):用來驗證是否在一個行程有效的範圍內

* 共用分頁(Shared Pages)
* 若程式碼是可重進入的程式碼(reentrant code/pure code)，則可以共用
* 可重進入的程式碼是不可自行修改的程式碼(non-self-modifying code)，永遠不會在執行中改變
* 甕用程式碼，但每個行程有自己的資料頁

### 分頁表的結構(Page Table Structure)
* 階層式分頁表(Hierarchical Page Tables)
* 分頁表太大，不希望連續的放在記憶體內
* 也稱向前對映分頁表(forward-mapped page table)
* 分成多層
* 一頁4kb，32位元系統
* 64位元的系統，不適合階層式架構，因為必須分很多層，導致轉換困難

* 雜湊分頁表(Hashed Page Tables)
* 邏輯位址被雜湊到雜湊表中比對
* 位址空間大於32位元可使用
* 碰撞(collision):雜湊到相同位置
* 使用列結串列(linked list)處理碰撞

* 反轉分頁表(Inverted Page Table)
* 通常每個行程都有自己一份的分頁表
* 每一個實替記憶體中的欄在反轉分頁表上有對映的虛擬位址，因此電腦系統中只需一份分頁表
* 減少儲存每一份分頁表所需的記憶體
* 增加搜尋所需要的時間(實體記憶體排序，搜尋虛擬記憶體可能需要遍歷)
* 只用雜湊減輕這個問題
* 雜湊增加了一次記憶體存取(雜湊表+分頁表)
* 共用記憶體
* 原本虛擬位址對映到同一個實體位址以達到共，但反轉分頁表一個實體位址只有一個進入點，不能有兩個共用虛擬位址
* 讓個別分頁表只包含虛擬位址到共用實體位址的對映

* SPARC CPU上執行的Solaris是一個64位元的作業系統
* 使用雜湊分頁
* CPU製作存放轉換表格項次(TTEs,translation table entries)以做快速硬體查詢的TLB
* TTEs存放於轉換儲存緩衝區(TSB,translation storage buffer)
* 會先搜尋TLB，若找不到則會走遍TSB