Ranfromran.com搜索
菜单

历史归档 · 操作系统

操作系统（二）：内存分配

从系统调用与异常，到连续内存分配和虚拟内存的基础整理。

11 分钟阅读

1.操作系统与设备和程序的交互

  • 系统调用：应用程序主动向操作系统发出请求。发出点是同步，返回点可能是异步
  • 异常：来源于不良的应用程序。非法指令或其他坏的处理状态（如：内存出错）。是同步的。
  • 中断：不同硬件的计时器和网络中断。来源于外设。是异步的

异步：当一个事件产生时，应用程序不知道什么时候发生

对以上三种情况的响应：

  • 系统调用：等待和持续
  • 异常：杀死进程，或重新执行引起异常的程序指令
  • 中断：持续，对应用程序是透明的。由操作系统来完成

2.用户态和内核态

这种切换在发生系统调用时产生。开销：

  • 建立 中断/异常/系统调用 号与对应服务例程映射关系
  • 建立内核堆栈（维护）
  • 验证参数（安全上考虑）
  • 用户态映射到内核态地址空间（更新页面映射权限）
  • 内核独自地址空间（TLB）

3.CPU的组成

运算器（ALU），寄存器，控制器，缓存，MMU

4.物理地址分配/连续内存分配（没有引入逻辑内存）

缺点：内存利用率低；有内外碎片的问题

物理地址空间——硬件支持的地址空间：内存+硬盘

逻辑地址空间——一个运行的程序所拥有的地址范围

连续地址分配——空闲的内存不能被利用：

  • 外部碎片：在分配单元间未分配的内存
  • 内部碎片：在分配单元内未分配的内存

分配策略

I 首次适配/第一匹配分配/First Fit

为了分配n个字节，使用第一个尺寸比n个字节大的空闲快

需求：1. 按照地址排序的空闲快列表。2. 分配需要寻找一个合适的分区。3.重分配需要检查，看是否有相邻的空闲区域能否合并

  • 优：简单；在地址空间的结尾易于产生较大的空闲块
  • 劣：外部碎片；不确定性

II 最佳适配/Best Fit

与请求分配的尺寸差最小，并比请求分配的尺寸大

为了避免分割大的空闲块，为了最小化外部碎片产生的尺寸

需求：1. 按尺寸排列的空闲块列表。2和3相同

  • 优：当大部分分配是小尺寸时；比较简单
  • 劣：外部碎片（拆分得比较细）；重分配慢；易产生很多没有的细小碎片

III 最差适配/Worst Fit

最大可用空闲块；为了面有太多的微小碎片

需求：1.按照尺寸排列的空闲块列表。2.分配很快（获得最大的分区）。3.重分配合并相邻空闲块

  • 优：分配是中等尺寸效果最好
  • 劣：易于破碎大的空闲块已至大的分区无法被分配

对碎片进一步处理

I 压缩式碎片处理/compaction

重置程序已合并孔洞；要求程序是动态可执行的（何时重置？开销？）

II 交换式内存整理

若运行的程序需要更多的内存——>抢占等待的程序并且回收它们的内存（换哪个？开销？）

非连续内存分配

5. 分段

基础：计算机程序由格式各样的段组成——代码：主程序，子程序，共享库；数据：栈，堆，共享数据段

分段：更好的分离和共享

连续的逻辑地址空间——>分段的物理地址空间

分段寻址方案：一个二维的二元数组：段号+偏移

段表：段的起始地址+段长度限制

6.分页

与分段的区别：段的大小是非固定的，而页的大小是固定的

  • frame：帧——物理内存划分单位
  • page：页——逻辑地址单位

帧和页大小相同，为2的幂

I 帧/Frame

一个物理地址是一个二元组（f,O)——（帧号，帧内偏移）

f：F 位——一共有 2^F 帧；O：S 位，每帧有 2^S 个字节

II 页/Page

一个逻辑地址是一个二元组（p,o）——（页号，页内偏移）

III 页寻址机制

  • 页映射到帧
  • 页是连续的虚拟内存；帧是非连续的物理内存
  • 不是所有页都有对应的帧

7.页表

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

标志位/Flags：dirty bit；resident bit； clock/reference bit

性能问题：

  1. 访问一个内存单元需要两次内存方位：一次获取页表项，一次访问数据
  2. 页表可能非常大

解决方案：1. 缓存/caching；2. 间接访问/indirection

TLB

Translation Look-aside Buffer：CPU中的快表

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

  • 使用 关联内存/associative memory 实现
  • 若 TLB 被命中，则物理帧号可以很快的被获取
  • 若未命中，则对应的页表项被更新到TLB中

二级页表/多级页表

一级页表中存的是二级页表的起始地址。逻辑地址——p1 + p2 + offset

以时间换空间

反向页表

为什么用：

  1. 有大的地址空间（64-bit)，向前映射页表变得繁琐
  2. 不是让页表与逻辑地址空间的大小相对应，而是与物理地址空间的大小相对应——逻辑地址空间的增长速度快于物理地址空间

实现方案

  • 基于 页寄存器/page register ：帧号为索引，内容是页号（怎么去找page number 所在的位置？）
  • 基于关联内存：key：页号，value：帧号——设计成本太大
  • 基于hash查找：h（pid，p）——加进程id是为了缓解哈希冲突

8.虚拟页式内存管理

在页式内存管理的基础上，增加请求调页和页面置换功能

页表表项：逻辑页号 + Flags（访问位，修改位，保护位，驻留位）+物理页帧号

虚拟内存性能

有效寄存器访问时间/EAT：effective memory access time

EAT = 访问时间 * 页表命中率 + page fault 处理时间 * page fault 处理时间

= t_{访问} \times （1 - p) + t_{处理} \times p \times （1 + q）

p: page fault 几率； q：dirty page 几率

页面置换算法

目标：尽可能减少页面换进换出的次数；通常只能在局部性的指导下依据过去的统计数据来进行预测

页面锁定/Frame Locking：在页表中添加锁定标志位/Lock Bit。用来描述：1.必须常驻内存的操作系统的关键部分； 2. 时间关键的应用程序

1**.最优页面置换算法**

计算内存中每一个逻辑页面在下一次访问之前的等待时间，选取最长的那个。

理想情况，可作为其他算法评估的依据

2. 先进先出算法/FIFO

系统维护这一个链表，记录了所有位于内存的逻辑页面。链首页面驻留时间最长，当发生缺页中断时，把链首页面淘汰掉，把新的页面加入到链尾。

性能较差；调出的页面可能是经常要访问的页面

Belady现象：给出的物理页帧越多，更频繁的发生缺页中断

3.LRU/Least Recently Used/最近最久未使用算法

当缺页中断发生时，淘汰最久未曾使用的页面

依据的是程序的局部性

class LRUcache
{
public:
LRUcache(int capacity)
{
this->capacity = capacity;
}

int get(int key)
{
auto iter = dic.find(key);

if (iter != dic.end())
{
pair<int, int> temp = *dic[key];
cache.erase(dic[key]);
cache.push_front(temp);
dic[key] = cache.begin();
return(temp.second);
}

return(-1);
}

void put(int key, int value)
{
auto iter = dic.find(key);

if (iter != dic.end())
{
cache.erase(dic[key]);
cache.push_front(make_pair(key,value));
dic[key] = cache.begin();
}
else
{
if (cache.size() == this->capacity)
{
auto temp = cache.back();
dic.erase(temp.first);
cache.pop_back();
}
cache.push_front(make_pair(key, value));
dic[key] = cache.begin();
}

}

private:
list<pair<int, int>> cache;
unordered_map<int, list<pair<int, int>>::iterator> dic;
int capacity;
};

4. 页面时钟置换算法

基本思路：

  • 需要用到页表项中的访问位。当一个页面被装入内存时，访问位初始化为0。然后如果这个页面被访问过，置为1.
  • 把各个页面组织成环形链表，把指针指向最老的页面（最先进来）
  • 缺页中断发生时，考察指针所指的最老页面，若其访问位为0，则立即淘汰；若为1则置为0，并把指针指向下一位。指导找到淘汰的页面，并把指针指向下一位。

加入dirty bit——二次进位法

优先换只读页，减小对写操作页的置换，以减少对磁盘的访问

5.LFU/Least Frequently Used/最不常用页面算法

当缺页中断发生时，淘汰访问次数最少的页面

LRU与LFU的区别

  • LRU的标准是多久没有访问，时间越短越好
  • LFU考察的是访问次数，频率越高越好
struct Node
{
int key, value, frequency;
Node(int INvale, int INvalue, int INfrequency) :
key(INvale), value(INvalue), frequency(INfrequency) {};
};

class LFUCache
{
public:
LFUCache(int capacity)
{
this->capacity = capacity;
miniFreq = 0;
freqTable.clear();
keyTable.clear();
}

int get(int key)
{
if (capacity == 0)
return(-1);

auto iter = keyTable.find(key);

if (iter == keyTable.end())
return(-1);

Node temp = *(iter->second);

int value = temp.value;
int freq = temp.frequency;
freqTable[freq].erase(iter->second);

if (freqTable[freq].size() == 0)
{
freqTable.erase(freq);
if (miniFreq == freq)
miniFreq++;
}

freqTable[freq + 1].push_front(Node(key, value, freq + 1));
keyTable[key] = freqTable[freq + 1].begin();
return(value);
}

void put(int key, int value)
{
if (capacity == 0)
return;

auto iter = keyTable.find(key);

if (iter == keyTable.end())
{
if (capacity == keyTable.size())
{
Node temp = freqTable[miniFreq].back();
keyTable.erase(temp.key);
freqTable[miniFreq].pop_back();

if (freqTable[miniFreq].size() == 0)
freqTable.erase(miniFreq);
}
freqTable[1].push_front(Node(key, value, 1));
keyTable[key] = freqTable[1].begin();
miniFreq = 1;
}
else
{
Node temp = *(iter->second);

int freq = temp.frequency;
freqTable[freq].erase(iter->second);

if (freqTable[freq].size() == 0)
{
freqTable.erase(freq);
if (miniFreq == freq)
miniFreq++;
}

freqTable[freq + 1].push_front(Node(key, value, freq + 1));
keyTable[key] = freqTable[freq + 1].begin();
}
}

private:
int capacity;
int miniFreq;
unordered_map<int, list<Node>> freqTable;
unordered_map<int, list<Node>::iterator> keyTable;
};

7. Belady现象

在采用FIFO算法时，会出现分配的物理帧数增加，缺页率反而提高的现象

原因：FIFO算法的置换特征与进程访问内存的动态特征是相矛盾的，与置换算法的目标（替换较少使用的页面）是不一致的。所以，它置换出去的页面不一定是进程不会访问的。

LRU为何没有Belady现象：符合栈算法的特点？

8. LRU，FIFO和Clock算法比较

如果页面进入内存后没有被访问过，那么LRU退化为FIFO

LRU性能好，但开销大；FIFO开销小，但性能差；折中的算法是clock算法。

全局页面置换算法

1.工作集模型

工作集/Working Set：一个进程当前正在使用的页面的集合。可用二元函数w(t,🔺）表示。

t——当前执行石刻；🔺——一个定长的页面访问的时间窗口

|w(t,🔺）|——工作集大小

2.常驻集

当前时刻，进程实际驻留在内存中的页面集合。

  • 工作集是进程在运行过程中的固有性质；常驻集取决于系统分配给进程的物理页数以及所采用的页面置换算法
  • 若一个进程的工作集都在内存中，即 常驻集 包含 工作集。那么不会有太多的缺页中断。指导工作集发生剧烈变动，进入下一个阶段
  • 当进程的常驻集的大小达到某一数目后，再给他分配更多的页面，缺页率也不会明显下降

3.工作集页面置换算法（全局算法）

某个页面不在工作集的窗口内 –> 置换出去 （并不是没有空闲物理页面时置换）

在运行多个程序的系统中，整体缺页率下降

4. 缺页率置换算法（全局）

基于上面一种算法的改进

缺页率 = \frac{缺页次数}{内存访问次数} = 缺页的平均时间间隔的倒数

影响缺页率的因数：

  • 页面置换算法
  • 分配给进程的物理页面数目
  • 页面本身大小
  • 程序编写方法

算法——力图使每一个进程的缺页率保持在一个合理的范围内

  1. 若运行程序的缺页率过高，则通过增加工作集来分配更多的物理页面
  2. 若进程缺页率过低，这减小工作集以减小它的物理页面

具体算法：

  1. t_{current} - t_{last} > T_{threshold}：从内存中移除所有在 [t_{current}, t_{last}] 时间内没有被访问的页面
  2. t_{current} - t_{last} \leq T_{threshold}：增加缺失页到工作集中

5.抖动问题/Thrashing

  • 分配给一个程序的物理页面太少，不能包含整个工作集（常驻集 \subset 工作集），那么进程就会造成很多的缺页中断，从而使得进程的运行速度很慢
  • 随着驻留内存的进程数增加，每个进程的物理页面不断减少，缺页率不断上升。故OS要选择一个合适的进程数和进程所需要的物理帧数，以在并发水平和缺页率之间达到平衡

Better criteria for load control:

平均页缺失时间 = 页缺失服务时间

MTPF = PFSF

mean time between page fault = page fault service time