Main Memory

基本知识 - 内存中的数据无意义，取决于解释的方式

Physical Memory

Problem: Process 4 requires space larger than the largest empty space hard to move

Solution

• 用逻辑地址而不是实际上的物理地址
• 在 runtime 的时候转换
• 可以很简单地挪进程

硬件实现

每次访存时由 CPU 完成

Partition

• 实现：Base & Limit 寄存器
• 逻辑地址都要加上 Base
• 如果超过 Base + Limit，报错
• 否则 Loaded by OS at each context switch
• 每次更换 process，改变 Base & Limit 寄存器，实现内存隔离

Memory Allocate

Fixed Partition

• 分成相同大小的 Partition，每次分配一个
• Internal Fragmentation - Process 比 Partition 小，剩下的多余内存
• 当进程比 parition 大 - divide & conquer

Variable Partition

• 不同大小的 Partition
• 具体策略（会出选择）
  • first fit
  • best fit
  • worst fit
• External Fragmentation - 在所有 partition 之外的碎片内存，不能使用
• 可以通过碎片整理解决（耗时）

Segmentation(Partition)

ELF binary basic - 最少需要 5 个 partition

• cat * 3
• heap
• stack
• 多个 base 和 limit，放在一页内存中，有相应的 segment-number
• Local address - （offset 是段内的偏移量）

section -映射-> segmentation

MMU - 起到一个把 logical address 转换成 physical address 的作用

CPU -> MMU -> Memory

Paging

Basic Idea:

• 物理内存分成固定大小的块 - frame

• 虚拟内存分成相同大小的块 - page

这样就能灵活地把虚拟地址映射到物理地址

难点 - keep tracking 这个映射（page table）

• 改善 fragmentation - 只有最后的页有 fragmentation

• 小页 - 小 fragmentation，但 keep tracking too many frame

• page table 里只存了帧号，页号是下标

• 优点
  • 每个进程可以有不同的内存映射
  • Memory can be moved
  • Memory can be swapped to disk

TLB - page 的 cache，一般是 MMU 的一部分

Page sharing

运行同一个程序两次，下面的可以 share

• code 段
• 动态链接库的 code 段
• 在两个进程的页表映射中都放

Structure of Page Table

• 需要连续的物理地址（虚拟地址也要连续）
• 需要的空间太大
• 每个进程有自己的页表，因此有不同的内存映射

Hierarchical page table

多层 page tabel

一页 4KB，32 位地址 - 4GB 的物理内存

• 高 10 位 - page directory 的 index（每项叫 PGDE）
• 中 10 位 - page table 的 index
• 低 12 位 - 页内寻址

一页 4KB，64 位地址 - 至少是 3 级页表（39 bit）

• PTE 变为 8 B
• PGD
• 在往上（P4D）
• 高 9 位 - 每一项管 1 GB（PUD）
• 中 9 位 - 每一项管 2 MB（PMD）
• 次低 9 位 - 每一项管 4 KB 的内存（PTE）
• 最低 12 位 - 业内寻址

如何省内存 -

Hashed Page Table

优缺点

• Hash 链表长的时候，速度慢
• 要运算 hash function
• 用内存稀疏时，适用

Inverted table

现实中的例子

Demanding paging

background: code 段大，不能一次全部放进内存，partially-loaded program

虚拟内存并没有存任何数据，都是由物理内存映射的

Demanding paging - 只有当 page 被需要时，才带到内存中

• demand - read/write
• page is valid but not in memory(page fault) => bring it to memory
• malloc - 分配内存，当要用的时候才处理 page fault(lazy 策略)
• User space program 访问新页时，MMU 发出 page fault，OS 处理 page fault
• 好处 - 省资源，有效避免“要的多，用的少”
• 缺点 - 浪费时间（时间换空间）

操作系统如何 handle

• check vm_area to decide fault type(segmentation fault 还是 page fault)
  • vm_area - 账本，记录程序的起始和终止虚拟地址（可能并未实际分配）
• Data 段和 Text 段是 file-backed 的，因此必须从磁盘读 - major page fault（少
• heap 和 stack 可以直接分配空闲 page，不用读盘 - minior page fault（多

Shared Library

Copy-on-write

Page Replacement

OS 可能把内存用光 - out-of-memory

此时需要替换 page

algorithm - FIFO, optimal, LRU, LFU, MFU

• optimal: 替换掉未来最不常用的
• LRU: least recent use, 可以用时间戳实现（性能会差）
  • 另一种算法：additional-Reference-Bits Algorithm
    • 用一串 01 记录访问情况，最开始全零。
    • 每次访问右移，如果使用当前页，把最高位置 1
  • second-chance
    • 一个 reference bit 记录访问情况，初始为 0，访问置 1
    • 当要牺牲它时，为 1 的话再给一次机会

Page-Buffering Al

Reclaiming Page

• 保证系统里内存充足 - 当 free frame 少于限度时，用替换策略回收 free frame

Non-Uniform Memory Access

• NUMA

Thrashing

• 系统内存不足，开启很多进程，需要频繁换页
• CPU 等待换页，利用率低
• 可以 kill 掉 process 解决

Working-Set Model

I/O interlock

Buddy System Allocator

• 二分法
• 可以分开也可以 merge

Slab Allocator

• a slab contains one or more pages, divided into equal-sized objects
• kernel uses one cache for each unique kernel data structure
  • kernel 每次分配一个 slab，divide into 多个 object
• Benefits: no fragmentation and fast memory allocation

只需要虚拟连续

Kernel & User virtual address

一般来说（virtual address）

• 高地址分配给 kernel
• 低地址分配给 user
• 32-bit 0xC0000000 划分
• 64-bit 0xffff000000000000 划分

• physical 地址不划分

进程之间如何 context switch

• switch_mm() - 写入新的 satp
• mm_struct 里存的虚拟地址，user space 的 page table

问题：物理地址空间比虚拟地址空间大时如何寻址

• 低位的 896 MB 直接映射到虚拟地址 - 转换简单（直接减 offset）
• 复用最高位的 128 MB - 用完马上释放，需要用页表寻址
• ARM64 - TTBR0 管 user、TTBR1 管 kernel，切换进程只换 TTBR0
• 内核管理物理内存，但不使用

Slab

复习

现在遇到的几个 table

• Segment table
• Page table
• System-call table