In Chapter 5, we showed how the CPU can be shared by a set of processes. As a result of CPU scheduling, we can improve both the utilization of the CPU and the speed of the computer’s response to its users. To realize this increase in performance, however, we must keep many processes in memory — that is, we must share memory.

In this chapter, we discuss various ways to manage memory. The memory- management algorithms vary from a primitive bare-machine approach to a strategy that uses paging. Each approach has its own advantages and disad- vantages. Selection of a memory-management method for a specific system depends on many factors, especially on the hardware design of the system. As we shall see, most algorithms require hardware support, leading many systems to have closely integrated hardware and operating-system memory management.

1. Background

Address Protection

  • base register 存取該 process 的最低 physical memory address
  • limit register 存取該 process 佔據的 range
  • 若存取 illegal address，則 trap to OS

Address Binding

決定 absolute address 的時機：

  • Compile/Load time: If starting location cahange, 就需要 re-compile
  • Execution time: 大部分 OS 用這個方法

Logical / Physical Address

  • Logical Address: 由 CPU 產生的 address
  • Physical Address: 真正在 memory unit 的 address
  • 在 compile / load time 時，logical == physical（因為還不知道真正的 address 會在哪），但當 execution time 時就會不同
  • Logical address is sometime refer as virtual address

Momery-Management Unit (MMU)

  • 快速轉換 logical/pysical memory，因為要快，所以是 hardware implement
  • 在 MMU 中，base register 又稱作 relocation register

Dynamic Loading

  • 在需要用到的時候，再把一個 routine load 進 main memory
  • 好處：如果有大量的很少使用的 code，Dymatic loading 就可以節省不必要的 memory 浪費並提升效率
  • Dynamic Loading 是 programmer 的責任，programmer 要自己 design how to dynamic loading

Dynamic Linking and Shared Libraries

  • 只有當 execution time 呼叫到相關函式時，才把相應的 source code load 進 memory
  • 好處：比較小的 execution file（library 還沒進來）
  • 好處：library 更新時不需要 recompile

2. Contiguous Memory Allocation and its Problem

Memory Protection

  • 因為是連續的，所以 memory translation 很容易

Memory Allocation

How to fit memory ?

  • First fit - 最有效率
  • Best fit - 剩下最小的洞
  • Worst fit - 剩下最大的洞

Fragmentation

  • Internel Fragmentation
    • 會多給 process 多一點 memory（給滿 block 的整數倍）
    • 問題：最多可能會浪費一整個 block 的 memory

  • Externel Fragmentation
    • 因為不夠好的 memory allocation algorithm，導致儘管 memory 足夠，但都被切成小塊以致無法使用
    • 解決方法：
      • Compation: 把 fragment 集中在一起
      • Paging: Non-contiguous Memory Allocation

3. Paging

Paging MMU and Process Allocation

  • p: page number 透過 page table 轉換成 f, frame number
  • d: page offset, 在兩邊會是一樣的

  • 利用 free-frame list 追蹤哪些 frame 可以被 map
  • 在一個 process 開始時，根據他的要求把 process’s page map 到 frames

Paging Internal Fragmentation

  • 為了方便，OS 還是會給整數倍 page size 的 memory，造成一小部分的 memory 被浪費掉
  • 若將 page size 調小，的確可以解決 internal fragmentation 的問題，但是小 page 也會有以下問題：
    • page table size increase
    • Disk I/O 一次讀寫大量 Data 比較有效率
  • 目前大部分的 page size 是 4KB or 8KB

Amount of Addressed Memory

More on Page Table

  • 是一個 per-process 的 data structure
  • 兩種 implementation 方式：
    • 放在 CPU 的高速 register 裡
      • address translation 很快
      • context switch 時造成 overhead
    • 利用存在 PCB 的 page-table base register (PTRB) 並將他指向 page table 存在 Main Memory 裡
      • 每次需要 page table 時都需要 access memory
      • context switch 比較快

Translation Look-Aside Buffer (TLB)

若我們使用 PTRB implement page table（如同多數 OS），則可以使用 TLB 加速

  • 將一些 map 過的 address 存在 cache 中（比 Main Memory 快速）
  • 當 TLB 滿的時候，就需要 replacement
    • Algorithm used: Least recently used, round-robin, random…
    • 有些 TLB 會保留一些 entry 不能被 replace
  • Address-Space Identifier(ASIDs), 可以記錄 TLB 中的哪些區域是屬於哪個 process 的
    • TLB 中可以有多個 process 的 mapping entry
    • 如果沒有 AIDs，每次 context switch 時 TLB 都必須要被 flush/erased

Effective Memory-Access Time

Protection

  • 某些 page table entry 裡的 bit 會拿來存額外的訊息
  • Valid-invalid bit: 該 page 是否被 map 到 physical memory
  • Page-table length register (PTLR): 存取 page-table 的大小，防止戳到 invalid address

Shared Pages

  • 當不同 process 要呼叫相同的函式(library)或使用相同的 data 時，可以透過 share page 的方式實作
  • 必須注意的是，這些被 map 到的 frame 必須是 reentrant code，也就是不會因為自己而改變的 code

4. Structure of Page Table

Heirarchical Paging (Two/Multi-Level Paging)

Page Tabel 可以到 4MB 的大小（$2^{20}$個 entry $\times$ 4B），但我們不想要 page tabel 在 physical memory 裡是連續的一塊，因此需要用某種方法將 page table 切成小塊

Hashed Page Table

  • 透過 hash function 將 logical address 轉成 physical address

Inverted Page Table

  • 減少需要的 memory（不用再每個 process 存一個 page table 了）
  • 增加 search table 所需的時間（需要找到對應的 pid）可以透過 hash table 或與正向 page table 混和使用來加速
  • 因為 page 跟 frame 是一對一關係，所以無法實作 share memory

5. Swapping

  • 將一部分/全部的 process 移進 backing store
  • Swapping 讓所有 process 可使用的 address space 總和大於 Main memory

Type of Swapping

  • Standard Swapping: 直接把整個 process 搬去 backing store
  • Swapping with Paging: 只 swap process 中部分的 pages