Your Site Title

Compute System Memory

内存管理的作用:

内存管理的方法:

需要与内存MMU相互配合

地址空间

逻辑地址生成:

  1. .c 通过编译 .s 从0开始的逻辑地址
  2. .s 通过汇编 .o 从0开始的逻辑地址
  3. .o 通过link 组合多个库, 成exe
  4. load .o 程序重定位

CPU MMU 逻辑对物理的映射:

  1. AOU带逻辑地址发MMU请求
  2. MMU没有去内存中找
  3. CPU给主存发请求
  4. 主存返回

内存表

操作系统需要维护的表:

内存分配

  1. 程序启动时分配
  2. 程序运行中请求分配

内存碎片

空闲内存不能被利用

连续内存分配算法

分配给一个程序的物理内存是连续的 内存利用率较低 有外碎片, 内碎片的问题

first fit

遇到第一个满足需求的空闲块

需求:

  1. 按地址排序的空闲块列表
  2. 分配需要寻找一个合适的分区
  3. 重分配需要检查, 看是否自由分区能合并于相邻的空间分区

优势:

  1. 简单
  2. 易于产生更大的空间块

劣势:

  1. 易产生外部碎片
  2. 不确定性
best fit

寻找最适合的空间块

需求:

  1. 按尺寸排列的空闲块列表
  2. 分配需要寻找一个合适的分区
  3. 重分配需要搜索及合并于相邻的空闲分区

优势:

  1. 当大部分分配是小尺寸时非常有效
  2. 比较简单

劣势:

  1. 外部碎片
  2. 重分配慢
  3. 易产生很多没用的微小碎片
worst fit

寻找差距最大的空间块

需求:

  1. 按尺寸排列的空闲块列表
  2. 分配很快
  3. 重分配需要合并于相邻的空闲分区, 然后调整空闲列表

优势:

  1. 假如分配是中等尺寸效果最好

劣势:

  1. 重分配慢
  2. 外部碎片
  3. 易于破碎大的空闲块以致大分区无法被分配

非连续分配算法

一个程序的物理地址空间是非连续的 更好的内存利用和管理 允许共享代码与数据 支持动态加载和动态链接

缺点: 如何建立虚拟地址和物理地址之间的转换. 软件转换性能开销大. 硬件转换: 分段和分页

分段(segment)

分散管理

段访问机制: (s, addr) 需要段表, 起始地址, 长度限制

分页(page)

与分段不一样地方, 页的大小固定, 段的大小不固定.

页表 page table MMU/TLB

帧: 号, 偏移 物理地址=2^s* f + o

页: 号, 偏移

逻辑地址由固定大小的页组成, 逻辑地址(p, o), 查page table和他的基地址获取帧号. 由 帧号+页偏移获取物理地址.

逻辑地址 大于 物理地址 因为多个页可以映射到同一个帧中

页表 page table

每个运行的程序都有一个页表, 是一个大数组, 索引是页号, 保存frame num和是否存在内存 中. 属于程序运行状态, 是动态变化的.

分页性能问题
  1. 访问一个内存单元需要2次内存访问
  2. 页表可能非常大
  3. 每个程序都有一份页表

时间上解决

空间上解决

大地址空间问题

有大地址空间(64-bits), 前向映射页表变得繁琐, 比如: 5 级页表 不是让页表与逻辑地址空间的大小相对应, 而是让页表与物理地址空间大小相对应.逻辑(虚拟) 地址空间增长速度快于物理地址空间.

虚拟内存

把cache, memory, disk组合起来, 让内存看起来看起来比较大.

内存替换

覆盖技术

是在较小的可用内存中运行较大的程序. 常用于多道道程序系统.

  1. 常驻区, 用于管理程序的移入和移出.
  2. 分区分时共享内存, 把没有调用关系的程序分为一个区.

缺点:

  1. 由程序员来分区
  2. 导入导出时间的把握
交换技术

多道程序在内存中时, 让正在运行的程序或需要运行的程序获得更多的内存资源.

  1. 可将暂时不能运行的程序送到外存, 从而获得空闲内存空间.
  2. 操作系统把一个进程的整个地址空间的内存保存到外存中或换回来.swap out swap in

什么时候交换: 只当内存不够或有不够的危险时换出 多大的交换区: 必须足够大以存放所有用户进程的所有内存映像的拷贝 程序换入重定位: 动态地址映射的方法

虚拟存储技术

覆盖技术: 程序员编程复杂 交换技术: 进程交换粒度太大

虚存技术: 操作系统管理, 以页为交换单位. 程序只有小部分在内存中, 大部分在硬盘上. 如果CPU需要的数据不在内存, 那么会以缺页异常通知操作系统, 操作系统会自动交换数据, 使 程序继续执行.

基本特征:

  1. 大的用户空间
  2. 部分交换
  3. 非连续内存

虚拟页式内存管理: 在页式存储管理的基础上, 增加请求调页和页面置换功能 页表需要增加位:

  1. 驻留位resident bit 是否在内存中
  2. 保护位protect bit 只读, 可读写, 可执行等
  3. 修改位dirty bit 是否修改过
  4. 访问位access(used) bit 是否在近期访问过

后备存储 Backing store

  1. 虚拟地址空间 映射到一个文件
  2. 代码段 映射到二进制文件
  3. 共享库: 映射到动态调用的库文件
  4. 其它段: 映射到交换文件

effective memory access time (EAT) EAT=访存时间 * 页表命中几率 + page fault处理时间* page fault几率

置换算法

当缺页中断发生, 需要调入新的页面而内存已满时, 选择内存当中哪个物理页面被转换.
需要尽可能地减少页面的换进换出次数(既缺页中断的次数. 一般使用局部性原理指导下
依据过去的统计来选择.

页面锁定(frame locking): 使某些页不在置换的目标当中.

页的调用轨迹, 需要生成一个程序最近调用页的轨迹, 只用保存页号

最优页面转换算法

当一个缺页中断发生时, 对于保存在内存当中的每一个逻辑页面. 计算在它的下一次访问
之前. 还需等待多长时间. 从中选择等待时间最长的那个. 作为被置换的页面.
这只是一种理想情况. 实际中操作系统是无法知道页等待多长时间以后才会再次被访问

先进先出

First-In First-Out
选择在内存中驻留时间最长的页面并淘汰之. 性能较差. 调出的页面有可能是经常要访问的
页面. 并且有Belady现象. FIFO算法很少单独使用.

最近最久未使用算法

Least Recently Used LRU. 最久未使用的那个页面.

1. 使用链表, 最近放在表头, 抽出表内重复, 最久在表尾 
2. 使用堆栈, 最近压入栈顶, 抽出栈内重复, 最久在栈底

查找重复的页号, 开销比较大

时钟页面置换算法

Clock页面转换算法, LRU的近似, 对FIFO的一种改进:
需要用到页表项当中的访问位, 当一个页面被装入内存时, 把该位初始化为0. 然后如果这
个页面被访问(读/写), 则把该位置为1;
把各个页面组织成环形链表(类似钟表面), 把指针指向最老的页面(最先进来).
当发生一个缺页中断时, 考察指针所指向的最老页面. 若它的访问位为0, 立即淘汰; 若访问
位为1, 则把该位置为0, 然后指针往下移动一格. 如此下去, 直到找到被淘汰的页面, 然后把
指针移动到它的下一格.

二次机会法

在时钟页面置换基础上, 添加了dirty bit, 当access bit和dirty bit 都为1时, 第一次会
把access bit设置为0, 第二次, dirty bit设置为0. 当两个bit都为0时就置换出去.

最不常算法

Least Frequentl Used, LFU: 选择访问次数最少的那个页面, 需要统计页被访问的次数.

问题
  1. Belady现象

使用FIFO算法时, 有时会出现分配的物理页面数增加, 缺页率反而提高. 主要是因为置换出
去的页面并不一定是进程不会访问的.

  1. 局部页替换算法的问题

页面置换算法的效率使用的frame大小有很大关系, 如果一个程序使用固定frame数, 那么
限制了程序产生缺页的特点, 程序运行过程中对frame数是动态的. 所以需要在程序运行阶段
动态分配frame, 由此产生全局页替换算法.

全局页替换算法

工作集(work set): 一个进程当前正在使用的逻辑页面集合. t代表当前时间, Δ代表t到
过去的时间(working set window).

常驻集是指在当前时刻, 进程实际驻留在内存当中的页面集合. 最好常驻集=工作集就不会中断.

工作集置换算法, 当页不在窗口, 就置换出去.

可变分配策略, 工作集和常驻集可以根据缺页率算法(page fault frequency, PFF)来改变
它们的大小. 缺页率: 缺页次数/内存访问次数. 当前中断与上次中断比较, 如果大于一个
阀值, 那么就是工作集较大, 把工作集中没有使用到的页置换, 减少工作集; 如果小于一个阀
值, 那么就是工作集较少, 把页加到工作集中, 使工作集变大.

内存抖动, 当分配给一个进程的物理页面太少, 不能包含整个的工作集. 那么进程将会造成
很多的缺页中断. 操作系统需要选择适合的进程数和进程需要的帧数.

This site is open source. Improve this page.