Skip to content

Latest commit

 

History

History
260 lines (150 loc) · 8.11 KB

Charpter 4.md

File metadata and controls

260 lines (150 loc) · 8.11 KB

Website

深入理解操作系统 第四章

第四章的主要内容是：操作系统的非连续内存分配

第三章介绍的是连续内存管理, 即 : 操作系统加载到内存以及程序加载到内存中时, 分配一块连续的空闲(内存)块. 但是容易出现碎片问题, 这一章介绍的非连续内存分配可以有效的减少碎片的出现.

非连续内存分配的必要性

连续内存分配的缺点

  1. 分配给一个程序的物理内存是连续的
  2. 内存利用率低
  3. 有外碎片 / 内碎片的问题

非连续内存分配的优点

  1. 一个程序的物理地址空间是非连续的

  2. 更好的内存利用和管理

  3. 允许共享代码与数据(共享库等...)

  4. 支持动态加载和动态链接

非连续内存分配的缺点

  1. 建立虚拟地址和物理地址的转换难度大

    • 软件方案

    • 硬件方案(采用硬件方案) : 分段 / 分页

非连续内存分配

分段(Segmentation)

段 : 在程序中会有来自不同文件的函数 ; 在程序执行时, 不同的数据也有不同的字段, 比如 : 堆 / 栈 / .bss / .data 等

**分段 : **更好的分离和共享

程序的分段地址空间如下图所示 :

分段寻址方案

逻辑地址空间连续，但是物理地址空间不连续，使用映射机制进行关联.

一个段 : 一个内存"块"

程序访问内存地址需要 : 一个二维的二元组(s, addr) → (段号, 地址)

操作系统维护一张段表, 存储(段号, 物理地址中的起始地址, 长度限制)

物理地址 : 段表中的起始地址 + 二元组中的偏移地址

分页(Paging)

分页地址空间

划分物理内存至固定大小的帧(Frame)

  • 大小是2的幂, 512 / 4096 / 8192

划分逻辑地址空间至相同大小的页(Page)

  • 大小是2的幂, 512 / 4096 / 8192

建立方案 → 转换逻辑地址为物理地址(pages to frames)

  • 页表
  • MMU / TLB

帧(Frame)

物理内存被分割为大小相等的帧. 一个内存物理地址是一个二元组(f, o) → (帧号, 帧内偏移)

帧号 : F位, 共有2^F个帧

帧内偏移 : S位, 每帧有2^S个字节

物理地址 = 2^S * f + o

(例子 : 16-bit地址空间, 9-bit(512 byte) 大小的页帧 物理地址 = (3,6) 物理地址 = 2^9 * 3 + 6 = 1542)

分页和分段的最大区别 : 这里的 S 是一个固定的数, 而分段中的长度限制不定

页(Page)

一个程序的逻辑地址空间被划分为大小相等的页. 页内偏移的大小 = 帧内偏移的大小 页号大小 <> 帧号大小

一个逻辑地址是一个二元组(p, o) → (页号, 页内偏移)

页号 : P位, 共有2^P个页

页内偏移 : S位, 每页有2^S个字节

虚拟地址 = 2^S * p + o

页寻址方案

操作系统维护一张页表, 页表保存了逻辑地址——物理地址之间的映射关系

存储 : (页号, 帧号)

  • 逻辑地址空间应当大于物理内存空间
  • 页映射到帧
  • 页是连续的虚拟内存
  • 帧是非连续的物理内存(有助于减少碎片的产生)
  • 不是所有的页都有对应的帧

页表(Page Table)

页表概述

每一个运行的程序都有一个页表

  • 属于程序运行状态, 会动态变化
  • PTBR : 页表基址寄存器

转换流程

CPU根据程序的page的页号的若干位, 计算出索引值index, 在页表中搜索这个index, 得到的是帧号, 帧号和原本的offset组成物理地址.

页表中还有一些特殊标志位

  • dirty bit,
  • resident bit, (0 : 对应的物理页帧在内存中不存在 ; 1 : 存在)
  • clock / reference bit

转换实例

16位地址的系统

  • 32KB的物理内存
  • 每页的 1024 byte

逻辑地址空间 : (4, 0) ... (3, 1023)

页表 :

Flags | Frame nums

1 0 1 0 0 0 0 0 → 内存访问异常(可能要杀死程序)

0 1 1 0 0 1 0 0 → 页帧是4 偏移是 1023 → 物理地址 (4, 1023)

分页机制的性能问题

访问一个内存单元需要2次内存访问

  • 一次用于获取页表项
  • 一次用于访问数据

页表可能非常大

  • 64位机器如果每页1024字节, 那么一个页表的大小会是多少？(2^64 / 2^10 = 2^54 存放不下)
  • 每一个运行的程序都需要有一个页表

如何处理？

  • 缓存(Caching)
  • 间接(Indirection)访问

转换后备缓冲区(TLB)

缓解时间问题

Translation Look-aside Buffer(TLB) 是一个缓冲区. CPU中有快表TLB(可以将经常访问的页表存放在这边)

缓存近期访问的页帧转换表项

  • TLB使用关联内存实现, 具备快速访问性能
  • 如果TLB命中, 物理页号可以很快被获取
  • 如果TLB未命中, 对应的表项被更新到TLB中(x86的CPU由硬件实现, 其他的可能是由操作系统实现)

二级/多级页表

时间换空间

二级页表

  • 将页号分为两个部分, 页表分为两个, 一级页号对应一级页表, 二级页号对应二级页表.
  • 一级页号查表获得在二级页表的起始地址, 地址加上二级页号的值, 在二级页表中获得帧号
  • 节约了一定的空间, 在一级页表中如果resident bit = 0, 可以使得在二级页表中不存储相关index,而只有一张页表的话, 这一些index都需要保留

多级页表

  • 通过把页号分为k个部分, 来实现多级间接页表, 建立一棵页表"树"

反向页表

解决大地址空间问题

目的 : 根据帧号获得页号

反向页表只需要存在一张即可

  • 有大地址空间(64-bits), 前向映射页表变得繁琐. 比如 : 使用了5级页表
  • 不是让页表与逻辑地址空间的大小相对应, 而是当页表与物理地址空间的大小相对应. 逻辑地址空间增长速度快于物理地址空间
基于页寄存器(Page Registers)的方案

存储 (帧号, 页号) 使得表大小与物理内存大小相关, 而与逻辑内存关联减小.

每一个帧和一个寄存器关联, 寄存器内容包括 :

  • resident bit : 此帧是否被占用
  • occupier : 对应的页号 p
  • protection bits : 保护位

实例 :

  • 物理内存大小是 : 4096 * 4096 = 4K * 4KB = 16 MB
  • 页面大小是 : 4096 bytes = 4 KB
  • 页帧数 : 4096 = 4 K
  • 页寄存器使用的空间(假设8 bytes / register) : 8 * 4096 = 32 Kbytes
  • 页寄存器带来的额外开销 : 32K / 16M = 0.2%
  • 虚拟内存大小 : 任意

优势 :

  • 转换表的大小相对于物理内存来说很小
  • 转换表的大小跟逻辑地址空间的大小无关

劣势 :

  • 需要的信息对调了, 即根据帧号可以找到页号
  • 如何转换回来? (如何根据页号找到帧号)
  • 在需要在反向页表中搜索想要的页号
基于关联内存(associative memory)的方案

硬件设计复杂, 容量不大, 需要放置在CPU中

  • 如果帧数较少, 页寄存器可以被放置在关联内存中
  • 在关联内存中查找逻辑页号
    • 成功 : 帧号被提取
    • 失败 : 页错误异常 (page fault)
  • 限制因素:
    • 大量的关联内存非常昂贵(难以在单个时钟周期内完成 ; 耗电)
基于哈希(hash)的方案

哈希函数 : h(PID, p) 从 PID 标号获得页号

在反向页表中通过哈希算法来搜索一个页对应的帧号

  • 对页号做哈希计算, 为了在帧表中获取对应的帧号
  • 页 i 被放置在表 f(i) 位置, 其中 f 是设定的哈希函数
  • 为了查找页 i , 执行下列操作 :
    • 计算哈希函数 f(i) 并且使用它作为页寄存器表的索引, 获取对应的页寄存器
    • 检查寄存器标签是否包含 i, 如果包含, 则代表成功, 否则失败