changed 4 years ago  
Published Linked with GitHub

OS筆記-Chapter 8: Main Memory

tags: OS

目錄

背景說明(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
Select a repo