主存（Main memory）
1.背景
程序保存在存储设备（backing store）里，而CPU能直接访问的存储介质只有主存（Main Memory）和CPU寄存器，可以说主存是是程序执行的中心：在指令执行过程（取指-指令解码-执行指令-取数-存结果），执行的指令需要去主存取来，指令执行的操作数可能需要去主存取来，执行结果可能存回主存；这样一个程序在运行前必须要从存储设备加载到主存中。为了支持多任务，多个进程通过CPU调度共享CPU资源（CPU共享）。为了提高CPU利用率和计算机对用户的响应速度，系统会让尽可能多的进程同时存放在内存中，即（内存共享）。
主存
主存其实就是一块大数组。通过内存地址，访问里面的内容，只关心访问内存的地址；不关心里面内存里面的内容是怎么产生的，以及里面的内容是数据还是指令。
基本硬件
CPU寄存器位于CPU 内部，CPU访问寄存器只需要一个CPU cycle；CPU 访问主存需要很多CPU cycle，会引起降速；因此会在CPU寄存器和主存之间放cache
内存保护
为了确保程序的正确执行，既需要保护OS防止用户程序访问，又要保护一个用户程序防止另一个程序访问。
处于性能考虑，OS 通常不介入CPU 和内存之间的访问，通过硬件实现。
实现
-
每个进程拥有独立的地址空间；
-
base和limit 寄存器，一个指定进程的物理内存空间的基地址，一个指定内存空间的大小；
image.png
- 内存空间的保护的实现是是CPU 硬件将每一个用户产生的地址与寄存器比较
image.png
-
结果：要么trap 到OS，or 访问内存
-
OS 有特权，负责加载base和limit 寄存器
地址绑定
一般程序作为二进制可执行文件，位于存储设备中。要运行程序，需要加载到主存中并放到进程上下文中。
用户程序经过几个处理阶段：编译（src->obj）-加载（obj->exe)-执行（runtime）
image.png
指令和数据的内存地址绑定可发生任何一个阶段：
-
编译阶段：若编译阶段确定进程内存地址，就产生绝对地址的代码；这样每次需要改变进程起始地址，必须重新编译。
-
加载阶段：若编译阶段，进程地址空间不可知，，则编译器产生可重定向的代码，最终的地址绑定延迟到加载阶段；
-
执行阶段：若进程在执行阶段能从一个段移动到另一段，则地址绑定延迟到运行阶段。大多数OS 采用这种方法。
逻辑 VS 物理地址空间
逻辑地址：CPU 产生的地址
物理地址：加载到内存单元的的地址寄存器的地址
编译阶段和加载阶段的地址绑定方案，逻辑和物理地址是一样的；而执行阶段，逻辑地址（虚拟地址）和物理地址不一样；
运行时，虚拟地址到物理地址的映射是通过MMU 完成的
image.png
动态加载
程序有主程序和一系列的函数；整个程序确实需要在内存中执行；可以调用到这个函数时加载它；这样的好处是：更好的内存空间利用率；不实用的函数绝不加载；任何保存的函数以可重定向的加载格式；在大量的代码用于处理很少发生的case时，很有用；
2. 内存分配
主存必须要能容得下OS和各种各样的用户程序。由于内存空间有限，需要高效分配内存
2.1 连续内存分配策略（早期）
-
将整个内存空间分为两部分：OS ，用户进程
-
多个进程同时位于内存中；
-
每个进程容纳于单个的连续的一个区域
-
内存保护
-
（relocated，limit）register
-
MMU 动态的映射逻辑地址到物理地址
image.png
-
内存分配
-
可变大小的分区内存分配
-
每个分区可能只放一个进程；
-
新进程开始前，从一个足够大的空洞中分配一个足够大的partition给进程
-
退出的进程释放分区，相邻的空闲的分区会合并
-
OS 维护信息：已分配的分区；空闲的空洞
-
-
分配策略-动态内配
-
first-fit：分配第一个的足够大的空洞
-
best- fit：分配最小的足够大的空洞
-
worst-fit：分配最大的空洞
-
-
碎片化
-
外部碎片化
-
进程不断的加载到内存和从内存中移除，空闲空间被拆分成许多小分
-
总可用的内存空间足以满足请求的大小，但是空间不连续
-
可以采用compaction
-
将所有空闲空间放到一块组成一个更大的；
-
需要重定向是动态的，执行时完成重定向；
-
若重定向是静态的，并且在汇编和加载是完成重定向，不能做compaction
-
compaction 开销很大
-
-
-
内部碎片化
分配的空间可能略微大于实际请求的:多分配的内存没有使用
解决外部碎片化-运行进程的逻辑地址空间可以不连续
2.2.非连续内存分配（分段/分页/分页分段）
分段
-
用户视角的内存管理方案
image.png
-
一个程序是一个集合的分段segment；
image.png
-
一个进程的物理地址空间可以不连续；
-
每个分段可以是大小不同的内存块;
-
外部碎片化
-
分段架构
1）逻辑地址是一个（segment number，offset ）二元组
2）分段表（segment table）-映射二维物理地址，每个table entry指定一段特定的连续的物理内存，base 和limit
3）分段表基地址寄存器(STBR)：指定分段表（segment table）的位置
4）分段表长度寄存器(STLR)：程序使用了segment 数量（legal segment number s < STLR)
分页
进程的物理地址空间可以不连续；只要有物理内存可用，就能分配给进程，可以避免外部碎片化和compaction，可以避免变长内存块的问题；
-
分页实现
-
将整个物理内存空间分成固定大小的块，即frames;
-
将整个逻辑地址划分成同样大小的page；
-
存储设备（backing store）划分成固定大小的与frames 或多个frames 大小；
-
记录所有的空闲的frames；
-
为了运行一个大小N个pages的程序，需要找到N个空闲的frames 并加载这个程序；
-
逻辑地址空间与物理地址空间完全隔离；
-
每个CPU产生的逻辑地址划分成两部分：page number + page offset；
-
image.png
-
每个进程创建一张页表(page table)，用于逻辑地址到物理地址的转化;
-
Page table ：逻辑地址的page 号作为这个page table的索引，page offset作为frame 内地址偏移；MMU 完成逻辑地址到物理地址的转化；
image.png
image.png
-
分配空闲内存
-
OS 维护一个free frames的链表
image.png
页表（page table）基本原理实现
-
页表保存在主存中
-
页表通过一套专用的高速硬件寄存器以高效实现
-
page table base 寄存器 （PTBR）指向page table
-
page table length 寄存器指明page大小
-
每个数据或指令的访问需要两次memory 访问：一次访问页表，一次数据或指令
-
两次memory访问解决的方案可通过使用一块很小的专门用于快速查询的的硬件擦车实现，页表缓存（TLB）
TLB
- TLB 每个entry 包含两部分：一个key即page号,一个value（frame 号）
image.png
-
是通常很小，只包含很少的页表entry；
-
TLB 查询很快，是指令流水线的一部分；
-
地址转化（p,d)；
-
每个通过会TLB 所有的key即page 号，
-
若TLB 命中即p 在TLB 中，直接得到frame 号；
-
若TLB Miss 则从主存的页表得到frame号，将这个的page号和Frame 号加到TLB 中
-
-
TLB 满处理-替换策略
-
一些TLB entry 可以hard code；
TLB + page table 实现
-
TLB 作为page table的cache；
-
访问memory 过程：
-
CPU 产生逻辑地址，MMU 首先检查page 号是否在TLB；
-
若TLB hit，frame 直接可用与访问内存，此过程是CPU 内部流水线的一部分，没有性能损失；
-
若TLB Miss，通过访问内存中的页表获取frame 号，同时是将这个的page号和Frame 号加到TLB 中
-
image.png
- 有效访问时间(EAT)计算
EAT = hit ratio * 主存访问时间 + (1- hit ratio) * TLB 访问时间
- 内存保护
增加相应frame的保护位，valid- invalid bit
image.png
page table 的实现
采用直接映射的方法，页表会很大；页表会有1M 个entry（2^ 32 /2^12), 一个entry 4B，一个页表4MB；
方案-划分成更小的单元
- 层级页表
将逻辑地址空间拆分成多级页表
两级分页页表
页表本身也使用页表寻址
image.png
页表分页
-
正常一个逻辑划分成部分：一个22bit page 号，一个10bit page 偏移；
-
page号再进一步划分成：12bit page 号，page oofset;
image.png
-
p1 是最外面的page table的索引，p2是最里面的page table 的索引
-
最外面和最里面的 page table都包含2^10 个entry，最里面的page table包含2^10
image.png
image.png
- 对于64bit 逻辑地址空间，两级分页不合适，需要对外面的page table 再分页，这样就成了三级page 分页table
image.png
- 三级分页页表仍然很大，下一步就是四级分页页表，由此可看出地址空间大于32位时，层级页表不合适
-
hash 页表 -用于地址空间大于32位
-
virtual page 号通过hash函数找到对应的hash table 中的entry
-
hash 页表的每个元素包含三部分：virtual page号+映射的page frame 号+指向下一个hash 到同一个位置的元素；
-
多个hash 值冲突，则比较链表中的每个元素的virtual page 号；
-
image.png
- 反向页表
-
反向页表不是通过page 号索引，而是通过物理frame 号索引；
-
不是让每个进程维护一个page table并跟踪每个逻辑page 的映射情况，而是跟踪所有物理frame的使用情况；
-
每个真正的物理内存page 是一个entry；
-
每个entry 包含对应实际的物理Frame号的虚拟page号，并包含拥有这个page 的进程信息
image.png
-
时间换空间：减少保存每一份page table的必要的内存，增加了搜索整个table的时间
- 可以使用hash table 来限制搜索一个或多个page table entry
-
共享内存问题：反向页表，每个物理frame 对应只有一个虚拟 page
交换技术
进程指令和数据必须在内存中执行；
进程或其一部分可以临时swapout 到辅存中，后续执行的时候再swapin到主存中
image.png
标准的交换技术
- 整个进程在主存和辅存之间移动技术；
- 辅存通常足够大以容纳进程任何一部分；必须提供直接访问这些内存image 的方法；
- 进程swap 到辅存是，与进程相关的数据结构也必须swap到辅存中；
- 优势：比实际的物理内存能容纳更多的进程；
- 缺点：将整个进程在主存和辅存之间移动的时间开销很高；
- 用于传统的UNIX 系统中，不再用于现在的OS；
分页+交换
进程的一部分在主存与辅存之间移动;
不会引起swap 整个进程的开销，只有少量的page 涉及交换；
page out, page in:一个page在主存与辅存直接移动；
image.png
移动端的交换技术
-
为PC和服务器设计的现代OS 支持交换page。与之相反，移动系统通常不支持任何形式的swap。
-
移动设备使用flash有限的PE 值，主存与flash 直接交换很差的吞吐量，并且移动端空间有限，从而导致移动OS 避免使用swapping。
-
不使用swap 技术，但是Apple IOS 让应用主动让出分配的内存，read-only的数据会从主存中移除
-
Android 是在空闲内存不够，则杀手进程以释放回收内存。
Intel IA-32 架构
-
内存管理分成两部分：segmentation和paging
-
CPU 产生逻辑地址给到分段单元，分段单元将逻辑地址转换成线性地址给到分页单元，分页单元将线性地址转换成物理地址。分段单元和分页单元共同组成MMU
image.png
分段（segmentation）
- 逻辑地址空间分段；
- 整个逻辑地址空间分为两部分：一部分对该进程私有，一部分是所有进程公共的。
- 两部分都可以分成多大8K 个segment
- 第一部分信息放在LDT，第二部分GDT
- 两个表的每个entry 有对应segment 的8B 描述符（base + limit）
- 逻辑地址：（selector，offset）
- selector: s-13bit 段号（segment number）；
- 1bit g 指定区分LDT 和GDT；
- 2bit p 用于保护；
image.png
-
硬件有6个segment 寄存器，这样能存放来自LDT或者GDT的对应段描述符，避免每次内存访问必须访问内存中的描述符。
-
线性地址产生过程：
- 段寄存器指向LDT或GDT 中对应的entry；
- 段寄存器base和limit 分别用于产生线性地址，
- 先用limit检查地址有效性，
- 若无效，产生memory fault；
-
否则将offset 与limit 相加，产生对于的32bit 线性地址
image.png
分页（paging）
-
IA-32 运行page size是4KB 或 4MB；
-
对于4KB page 大小，两级方案；
+地址转换类似于
image.png
image.png
网友评论