内存

操作系统

存储管理

内存、CPU

内存存储单位8bit，存在内存地址对齐。
CPU两级缓存-高速缓存->内存-缺页->外存（虚拟存储）

MMU

-|存储管理单元
---|逻辑地址空间
---|物理地址空间
--|独立地址空间
--|访问共享内存
-|内存虚拟化（提供更大的地址空间）

内存管理

• 重定位
• 分段
  数据-->代码-->堆栈
• 分页
  基本单位，按需页式虚拟存储

硬件

• 硬件存储架构耦合
• MMU：处理CPU存储访问

地址空间

• 物理地址空间
  硬件支持的地址空间（0-MAXsys）
• 逻辑地址空间
  CPU进程看到的地址（0-MAXprog）

逻辑地址生成

程序--编译->汇编--编译->机器二进制码--链接->地址函数库--程序加载->重定位到物理地址

地址生成情况

• 编译
  初始地址确定，修改初始地址需重新编译
• 加载
  初始地址未知，编译器重定位，加载时生成绝对地址
• 执行
  代码可移动，地址转换映射到硬件支持

地址检查

进程逻辑地址空间--指令->CPU--逻辑地址->操作系统--段长度和基址->物理地址

主要检测段长度和基址是否与操作系统提供的起始和最大逻辑地址空间相对应。

连续内存

一块不小于指定大小的物理连续内存分配。

内存碎片

空闲内存不能被利用。

• 内部碎片
  单元内部未使用，分配单元大小取整。
• 外部碎片
  单元间未被使用。

动态分区分配

加载执行程序，分配大小可变的连续地址。

• 数据结构
  已分配分区和空闲分区
• 策略
  最先匹配
  按地址顺序排序，分配选取第一个合适分区，释放检测与邻近分区合并。
  优：简单，高地址留给大块区域。
  缺：外碎片，分配大块时较慢。
  最优匹配
  空闲分区表大小排序，分配时查找最小差异合适分区，释放时合并邻近分区。
  优：小尺寸匹配效果好，较少外碎片尺寸，相对简单。
  缺：外部碎片，释放分区较慢，产生无用小碎片。
  最差匹配
  空间分区表大小排序，分配时选取最大合适分区，释放时合并邻近分区，调整顺序表。
  优：中等大小分配效果好，避免太多小碎片。
  缺：释放慢，外部碎片，容易破坏大的分区（无法匹配较大分区请求）

碎片整理

调整位置减少，避免分区碎片。
- 条件
动态重定位，开销
- 分区对换（swapping in/out）
等待（等待状态分区）<-->对换等待（对换区）
主要着眼点在于对换哪个进程分区（涉及优先级等）

伙伴系统

• 可分配空间
  按对半分配，处于两个二分之一区间内即可分配空间，逐渐切片模式。
• 数据结构
  空闲块大小和起始地址构成二维数组，初始有2^n个空闲块
• 分配过程
  由小到大找最合适的可用空间块，过大二等分。
• 释放
  释放分区放入空闲块数组，合并需满足2^n分区条件（地址相邻、大小相同、起始地址为2^(i+1)）。

非连续内存

需求分析

• 目的
  提升利用效率和管理灵活性，实现逻辑地址和物理地址的转换。
• 思路
  使用非连续物理地址空间
  共享代码、数据
  动态加载：动态链接
• 实现
  软件实现：灵活，开销大
  硬件实现：够用，开销大
  硬件辅助机制：段、页

段式存储

更细粒度，灵活分配，相对大块地址空间。

地址空间组成

段概念

访问方式和存储数据一致空间。
对应一个连续的内存块。
若干个段组成逻辑地址空间。

段访问过程

逻辑地址二元数组(s,d)
s:段号，d：段偏移

页式存储

页帧

frame page，2^n个物理页面，用于物理区域的划分

• 物理内存划分
  二元组(f,o)
  f表示帧号，一共有F个位；o表示帧内偏移，一共有S位。
  计算：物理地址=f*2^s+o

页面

page，帧和页相同，逻辑页面的划分，页内偏移和帧内偏移一致。

• 逻辑地址划分
  二元组(p,o)
  p表示页号，一共有P个位；o表示帧内偏移，一共有S位。
  计算：物理地址=p*2^s+o

地址映射过程

页到帧的映射，逻辑地址页号连续，物理地址页号不连续，不是所有的页都有对应的帧。

页表

页表概念

保存逻辑地址到物理地址的映射。
每个进程都有一个页表，每个页面对应一个页表项，随进程运行而动态变化，页表基址寄存器。

• 页表项组成
  帧号
  页表项标志位：存在位、修改位、引用位等。
• 性能问题
  内存访问：访问一个内存单元需要两次内存访问（获取页表项、访问数据）
  页表大小：页表非常大
  处理方法：缓存（Caching）、间接（Indirection）访问

快表

Translation Look-aside Buffer,TLB
缓存近期访问的页表项：使用关联存储实现，具备快速访问性能，如果TLB没有命中，则对应的表项被更新到TLB中。

多级页表

通过间接引用将页号分级，简历页表“树”，减少每级页表的长度。

页寄存器

页表与物理地址空间大小对应。

• 寄存器
  每个帧与一个页寄存器关联，寄存器包括：
  使用位（是否被进程占用）、占用页位（对应页号P）、保护位
  优：页表大小相对物理内存而言，与逻辑地址空间无关。
  缺：页表信息对调后，需依据帧号找页号，页寄存器搜索逻辑地址的页号。
• 地址转换
  CPU逻辑地址Hash映射（解决冲突）、块表缓存页表搜索（逻辑地址Hash-->快表查找对应页表项-->冲突时遍历冲突项链表-->查找失败时产生异常）
  快表限制：快表的容量限制，快表的功耗限制。

反置页表

基于Hash映射值查找对应页表项中的帧号。

• 进程标识与页号的Hash值可能有冲突
• 页表项中包括保护位、修改位、访问位和存在位。

段页式存储

段式存储在内存保护上有优势，页式存储在内存利用和优化转移到后备存储方面有优势。
段页式存储：在段式存储管理的基础上，给每个段加一级页表。通过指向相同的页表基址，实现进程间的段共享。