NCTUCS 2013-Fall Introduction to Operating System by Hank Wu

Ch8 - Memory Management

• To provide a detailed description of various ways of organizing memory hardware
• To discuss various memory-management techniques, including paging and segmentation
• To provide a detailed description of the Intel Pentium, which supports both pure segmentation and segmentation with paging

Background

• Program must be brought (from disk) into memory and placed within a process for it to be run
• Main memory and registers are only storage CPU can access directly
• Register access in one CPU clock (or less)
• Main memory can take many cycles
• Cache sits between main memory and CPU registers
• Protection of memory required to ensure correct operation

Base and Limit Registers

A pair of base and limit registers define the logical address space

Binding of Instructions and Data to Memory

Address binding of instructions and data to memory addresses can happen at three different stages
+ Compile time
+ If memory location known a priori, absolute code can be generated
+ must recompile code if starting location changes
+ Load time
+ Must generate relocatable code if memory location is not known at compile time
+ Execution time
+ Binding delayed until run time if the process can be moved during its execution from one memory segment to another.
+ Need hardware support for address maps (e.g., base and limit registers)

Multistep Processing of a User Program

在這中間的每個步驟都可以作 Address binding
windows 底下的 .dll 檔, IE Explorer 的 ActiveX 都是動態連結的例子

Logical vs. Physical Address Space

• Logical address – generated by the CPU; also referred to as virtual address

• Physical address – address seen by the memory unit

• The concept of a logical address space that is bound to a separate physical address space is central to proper memory management

• Logical and physical addresses are the same in compile-time and load-time address-binding schemes
• Logical (virtual) and physical addresses differ in execution-time address-binding scheme

Memory-Management Unit (MMU)

• Hardware device that maps virtual to physical address
• In MMU scheme, the value in the relocation register is added to every address generated by a user process at the time it is sent to memory
• The user program deals with logical addresses; it never sees the real physical addresses

Dynamic relocation using a relocation register

Swapping

Contiguous Memory Allocation

Fragmentation

• External Fragmentation
  • total memory space exists to satisfy a request, but it is not contiguous
• Internal Fragmentation
  • allocated memory may be slightly larger than requested memory
  • this size difference is memory internal to a partition, but not being used
• Reduce external fragmentation by compaction
  • Shuffle memory contents to place all free memory together in one large block
  • Compaction is possible only if relocation is dynamic, and is done at execution time
  • I/O problem
    • Latch job in memory while it is involved in I/O
    • Do I/O only into OS buffers

Paging

目前最常見的是以 4k 為單位的 page
表格的內容是由 software 在維護的，硬體藉由查詢表格的內容得知記憶體的位置。

• Logical address space of a process can be noncontiguous; process is allocated physical memory whenever the latter is available
• Divide physical memory into fixed-sized blocks called frames (size is power of 2, between 512 bytes and 8,192 bytes)
• Divide logical memory into blocks of same size called pages
• Keep track of all free frames
• To run a program of size n pages, need to find n free frames and load program
• Set up a page table to translate logical to physical addresses
• Internal fragmentation

Paging Model of Logical and Physical Memory

Physical Memory 可以不用是連續的
可透過 page table 對應到連續的 Logical Memeory
達到彈性化的 Memory Management

Free Frames

• Page Table 是由 OS 在 Maintain 的
• Free Frame 也是由 OS 在 Maintain 的，要 Allocate 新的記憶體空間必須透過 Free Frame 尋找 Available 的記憶體空間

Implementation of Page Table

Page-table base register (PTBR) points to the page table
Page-table length register (PRLR) indicates size of the page table

X86 內的 CR3 就是 X86 的 PTBR
X86 的 Page Table 長度是固定的，所以不需要 PRLR

Q:剛才提到 Page Table 是由 OS 在 Maintain，但這裡卻說 X86 的 Page Table 長度是固定的。那 Page Table 到底是由 OS 還是 CPU 架構決定？
A: OS 的設計還是必須被侷限在 CPU 的架構底下。

Page Table 把資料存在 Physical Memory 裡面。

從這樣的機制看來，每次的記憶體讀寫都要花兩倍的時間
1. Logical Memory 和 Page Table 之間
2. Page Table 和 Physical Memory 之間
這樣看來 Performance 會非常差
但實際上有 Cache 的存在，所以會解決這個問題

• a special fast-lookup hardware cache called associative memory or translation look-aside buffers (TLBs)
• Some TLBs store address-space identifiers (ASIDs) in each TLB entry – uniquely identifies each process to provide address-space protection for that process

Effective Access Time

EAT = 2 + \varepsilon + \alpha  

Memory Protection

Valid-invalid bit attached to each entry in the page table
+ Valid
+ in the process’ logical address space
+ legal page
+ Invalid
+ not in the process’ logical address space
+ illegal page

Shared Pages

• Shared code
• Private code and data

Structure of the Page Table

• Hierarchical Paging
• Hashed Page Tables
• Inverted Page Tables

Hierarchical Page Tables

• Break up the logical address space into multiple page tables
• A simple technique is a two-level page table

Two-Level Page-Table Scheme

見 p.39 的圖

Address-Translation Scheme

見 p.41 的圖

Three-level Paging Scheme

見 p.42 的圖

outer page, inner page, offset

Hashed Page Table

見 p.44 的圖

• 有 Collision 的問題得解決:利用資料結構學到的方法解決
• 時間複雜度不見得會是 O(1), depend on chain 的長度

Inverted Page Table

• 優點
  • 針對 External Fragmentation 做解決（也是為什麼要有 Page Table 的主要原因）
  • 以 Memory Frame 為本位設計
  • 每個 Frame 都有一個對應的 Page Table
  • 不需要實作 Hash Function
  • 直接到一維陣列裡面做線性的搜尋，比較簡單
• 缺點
  • 搜尋很花時間
  • 不能作多對一的 Mapping
  • 無法實作 Shared Memory Page

Segmentation

透過前面的 Paging 可以得到一個很大的記憶體空間
Segmentation 就是在規劃這些 Address Space 分成不同的 Segment
每個 Segment 負責不同性質的工作
以提升記憶體管理的效率。

• 程式碼區段是唯讀的，可以確保不會被更改，以及比較不容易被惡意攻擊者利用
• 讓 Stack 有專屬的暫存器

Logical View of Segmentation

• 和 Page Table 類似，但還是有不同處
  • 相同處：Mapping 的方法相同
  • 不同處：每個 Segment 的長度是可以變的

在 X86 上面，是先有 Segment 後才有 Page Table 的。

Segmentation Architecture

• Segment table: maps two-dimensional physical addresses
  • base: contains the starting physical address where the segments reside in memory
  • limit: specifies the length of the segment
• Segment-table base register (STBR): points to the segment table’s location in memory
• Segment-table length register (STLR): indicates number of segments used by a program;

if Validation bit = zero, then this segment is illegal.
超過非法的 Segment 取用範圍 => Segmentatioin Fault (segment number >= STLR)

Segmentation Hardware

見 p.52 的圖

Example of Segmentation

見 p.53 的圖

Example: The Intel Pentium

• Supports both segmentation and segmentation with paging
• CPU generates logical address
  • Given to segmentation unit
  • Linear address given to paging unit

Pentium Paging Architecture

見 p.57 的圖

• 越接近 Outer Table，則尺度是越大的
• 4KB page => 2 layer
• 4MB page => 直接由 page directory 產生，不需要是 2 layer

Linear Address in Linux

global directory, middle directory, page table, offset

使用到 kernel code 才能用的 segment 的話，也會出現 Segmentation Fault

Three-level Paging in Linux

見 p.59 的圖