操作系统

内存管理

内存管理机制

分为连续分配方式和非连续分配方式

连续分配方式:是指为一个用户程序分配一个连续的内存空间.

非连续分配方式:是允许一个程序分散的装入不相邻的内存分区中.

连续内存分配方式

1. 单一连续分配

将内存空间分为系统区和用户区

在用户区中将全部内存分配给一个作业使用,等到该作业完成结束时,才将内存释放

2. 固定分区分配

将内存空间划分为若干个固定大小的分区,这些分区可以大小相等或大小不相等

并且为分区排序,建立分区表,表项包括每个分区的起始地址、大小及状态

当程序需要分配内存时,检索该分区表,找到合适大小的未分配的内存分区,然后分配.如果找不到合适的内存分区,则拒绝为程序分配内存

3. 动态分区分配

在程序装入申请内存时,才根据程序的大小建立合适的内存分区

一般通过空闲分区表和空闲分区链来管理分区

当程序申请内存时,从空闲分区表(链)中找到合适的分区为其分配

动态分区分配算法

1. 基于顺序搜索的算法

  1. 首次适应算法

    将空闲分区按地址递增的顺序排列,在分配内存时,从首部开始查找,直到找到一个满足大小的空闲分区,然后按照程序的需要的内存大小,划分内存空间分配.若从首部到尾部都未找到合适的分区,则表示没有足够的内存分配,内存分配失败

    **特点：**低地址部分不断被划分，留下许多难以利用的很小的空闲分区 ，而每次查找又都是从低地址部分开始，增加了查找可用空闲分区的开销。

  2. 循环首次适应算法

    与首次适应算法相似,不过每次不是从首部开始查找,而是从上一次找到的空闲分区的下一个分区开始查找

    **特点:**使存储空间的利用更加均衡，不致使小的空闲区集中在存储区的一端，但这会导致缺乏大的空闲分区

  3. 最佳适应算法

    该算法要求空闲分区按照分区大小递增排序,然后从首部开始查找,找到第一个满足大小的空闲分区.这样可以找到满足大小的最小的空闲分区

    **特点:**保留了大的空闲分区。但往往使剩下的空闲区非常小，从而在存储器中留下许多难以利用的小空闲区

  4. 最坏适应算法

    与最佳适应算法相反,每次找到最大的空闲分区.

    **特点:**由于最大的空闲分区总是因首先分配而划分，大作业的内存申请往往会得不到满足。

2. 基于索引搜索的算法

  1. 快速适应算法

    将空闲分区按照大小进行分类,对于每一类具有相同容量的空闲分区,建立空闲分区链表,再为这些空闲链表建立管理索引表

    分配时,只要按照大小查找满足条件的最小空闲分区,分配第一块分区

  2. 伙伴系统

    规定,无论是已分配的分区还是未分配的分区,其分区大小都是2的k次幂.$n\leq k\leq m$,$2^n$是分区的最小大小,$2^m$是分区的最大大小,通常是整个内存的大小

    在系统运行过程中，由于不断地划分，将会形成若干个不连续的空闲分区，将这些空闲分区按分区的大小进行分类。对于具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表

    分配过程:

    当程序申请大小为n的内存空间时,首先计算i,满足 $2^{i-1} < n\leq 2^i$

    在空闲分区大小为$2^i$的链表上查找分区,若存在分区,则将该分区分配.

    否则,就向上寻找大小为$2^{i+1}$的分区链表,若存在分区,则将该分区划分成2个大小为$2^i$的分区,一个用于分配,一个保存在链表中.

    若还是不存在,则继续向上寻找$2^{i+2}$,先将其分为2个大小为$2^{i+1}$的分区,其中一个保证在链表,另一个继续划分为2个大小为$2^i$的分区,一个用于分配,一个保存在链表中.

    内存释放:

    将伙伴合成为更大的内存块,一直向上继续

slab机制:

Linux操作系统的一种内存分配机制.

主要针对一些经常分配而且占用内存空间小的对象.减小伙伴系统对于过小的内存的分配的消耗.

对于对象类型的内存分配是从slab缓存中获取的,而不是从伙伴系统中分配内存.

  1. 哈希算法

    构造一张以空闲分区大小为关键字的哈希表，该表的每一个表项记录了一个对应的空闲分区链表表头指针。

    进行空闲分区分配时，根据所需空闲分区大小，通过哈希函数得到在哈希表中的位置，从中得到相应的空闲分区链表的表头指针。

动态重定位分配

当内存分配后会出现被分割的小分区,因此缺乏大分区.因此需要通过内存紧凑来将这些小分区整合为大分区.

**动态重定位:**作业在内存中的位置发生了改变,因此需要改变对物理内存地址的访问.

程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。

非连续内存分配方式

1. 基本分页管理

程序中的页是固定大小的,且物理内存中的页框对应相同的大小.

在分页管理中,允许进程将各个页存在在物理内存的不同位置,因此需要通过页表来做一个页面的映射.

程序的页面由:页号+页内地址组成.

通过内存管理单元(MMU),用逻辑页号在页表中查询对应的物理页框号.再通过物理页框号的地址+页内地址偏移组成真正的物理内存地址.

快表和多级页表

基本的分页管理中存在显著问题:

  1. 虚拟地址到物理地址的映射需要很快,否则映射消耗会成为性能瓶颈
  2. 如果虚拟地址很大,出现页表过大的问题

快表

传统的映射需要访问内存2次,一次访问页表,一次访问实际物理内存

因此引入转换检测缓冲区(TLB),又称快表

通常在MMU中通过快表保留了少量的最近访问的页表,当下次访问时,首先通过访问快表,如果快表中有映射关系,则可直接通过快表访问物理地址.如果快表中不存在,则需要访问内存中的页表,然后将访问过的这次映射关系添加到快表中.

因此,该种访问方式,如果快表中存在则只需要访问一次内存即可.

多级页表

在针对过大页表时,采取将页表分多级的方式来降低页表的占用.

通过一级页表来映射二级页表,再通过二级页表来映射页框.

为何节约内存?

  1. 二级页表可以直接不存在.

    程序在运行时,并不一定会用到全部的内存空间.因此只需要做一个一级页表,再将用到的二级页表通过一级页表映射出来即可,其他没用到的不需要占用内存空间.

  2. 二级页表不在主存

    类似于虚拟内存的管理方式.直接将二级页表放入磁盘中,当访问了需要的二级页表,产生缺页请求,通过将所需要的二级页表调度进入内存即可.

倒排页表

通过物理内存的页框来映射页表.表项中记录了哪些页面映射到该页框上.

严重的缺点在于从虚拟地址映射到物理地址的过程将变得相当困难.

2. 基本分段管理

因为分页管理中的页是固定大小的,为了满足动态扩张和收缩的要求,引出了分段管理的实现方式.

每个段由一个从0到最大线性地址序列构成.各个段的长度可以是0到某个允许的最大值之间的任何一个值.不同段的长度可以不同.

通过建立段表来映射虚拟地址到物理地址的映射.每个段表项对应进程中的一个段.通过段号和段内地址偏移来查找物理内存地址.与分页管理类似.

分页管理与分段管理的异同

  1. 两者都是为了提高内存利用率
  2. 两者映射的实际物理地址是离散的,但在页内或段内地址是连续的.
  3. 页的大小是有os决定的固定大小的,段的大小是不固定的
  4. 分页管理是为了满足操作系统内存管理的需求,而分段管理能反应程序的逻辑结构并有利于段的共享

3. 段页式管理

将分页与分段结合.

程序的地址空间被分为若干个逻辑段,每个段有自己段号,每个段又分为若干个大小固定的页

对内存空间的管理仍然和分页存储管理一样，将其分成若干个和页面大小相同的存储块，对内存的分配以存储块为单位。

因此段页式的逻辑地址组成为:段号+页号+页内偏移

因此需要为每个进程建立一个段表,段表项中包含段号+页表长度+页表起始地址,再为每个段建立一个页表.

寻址过程:先通过段号寻找到页表的起始地址,再通过页表以及页号查找到页框号,最后加上页内偏移构成物理内存地址.

局部性原理

  1. 时间局部性:如果程序中的某条指令一旦执行，则不久以后该指令可能再次执行；如果某数据被访问过，则不久以后该数据可能再次被访问。产生时间局部性的典型原因，是由于在程序中存在着大量的循环操作。
  2. 空间局部性:一旦程序访问量某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，其典型情况便是程序的顺序执行。

时间局部性是通过将进来使用的指令和数据保存到高速缓存存储器中，并使用高速缓存的层次结构实现。空间局部性通常是使用较大的高速缓存，并将预取机制集成到高速缓存控制逻辑中实现。虚拟内存技术实际上就是建立了“内存-外存”的两级存储器的结构，利用局部性原理实现高速缓存。

虚拟内存实现

1. 请求分页存储管理

在基本分页管理中,程序运行需要将全部的页装入内存才可启动,而在请求分页中,只要求将当前需要的一部分页面装入内存，便可以启动作业运行.在程序执行过程中,若出现访问的页面不存在,产生缺页中断,再通过页面置换将页面换入内存,同时将暂时不用的页面换出到外存.

在基本的页表项中增加了四个字段：状态位P、访问字段A、修改位M、外存地址

  • 状态位P：用于指示该页是否已调入内存，共程序访问时参考。
  • 访问字段A：用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，供置换算法换出页面时参考。
  • 修改位M：表示该页在调入内存后是否被修改过。
  • 外存地址：用于指出该也在外存上的地址，通常是物理块号，供调入该页时参考。

2. 请求分段存储管理

作业的若干分段别放入内存，就可以开始作业运行. 在作业运行过程中，如果要访问的分段不在内存中，则通过调段功能将其调入，同时还可以通过置换功能将暂时不用的分段换出到外存，以便腾出内存空间。

在基本的段表项中增加了:

  • 存取方式：存取属性（执行、只读、允许读/写）
  • 访问字段A：记录该段被访问的频繁程度
  • 修改位M：表示该段在进入内存后，是否被修改过。
  • 存在位P：表示该段是否在内存中。
  • 增补位：表示在运行过程中，该段是否做过动态增长。
  • 外存地址：表示该段在外存中的起始地址。

与请求分页不同的是,因为分页的页大小是固定的,因此直接置换页即可,但在分段管理中,段的大小是不固定的,因此只置换一个段,可能内存空间还是无法满足所需的段空间的内存大小,因此可能需要置换出多个段空间.

3. 请求段页式存储管理

与以上类似

页面置换算法

页面置换算法

1. 最优页面置换算法(OPT)

该算法的基本思想是在产生缺页时,替换在以后的最长时间不会再访问的页面.

唯一缺点在于无法实现,因为os永远不知道接下来要访问的页面.

2. 最近未使用置换算法(NRU)

该算法为每个页面设置两个状态位,访问位R,写入位M

因此将页面分为4类

  • 没有被访问,没有被修改
  • 没有被访问,被修改
  • 被访问,没有被修改
  • 被访问,被修改

其中访问位R会被定期重置为0

该算法优先考虑换出第一类页面,也就是未被访问的已修改页面

3. 先进先出页面置换算法(FIFO)

该算法维护一个页面的链表,最新进入的页面在链表尾部,因此最早进入的页面会出现在链头

每次缺页中断时,将链头的页面换出,将新换入的页面加入到链尾

4. 第二次机会页面置换算法(SC)

该算法在FIFO的基础上为页表设置一个访问位R.

每次缺页中断时,检查链头的页表,如果R位为0,则直接换出,否则将R位置0,并放入链尾.

5. 时钟页面置换算法(Clock)

在SC的基础上进行改进,将页面保存为一个环形链表,将表针指向最老的页面.

每次缺页中断时,检查指针指向的页面,如果R位为0,则直接换出,否则将R位置0,并且指针前移一位,而不是移动页面.

6. 最近最少使用页面置换算法(LRU)

该算法维护一个页面链表,将最近访问的页表从链表中的原位置删除,并添加到链头,这样就能保证链尾总是最近最少被访问的页面.

每次缺页中断时,直接将链尾的页面换出,然后换入新页面放入链头即可.

7. 最不常用算法(NFU)

该算法为每个页面维护一个计数器,每次时钟中断时,将访问位R(值为0或1)加到计数器上.

当缺页中断时,置换出计数器最小的页面.

该算法的缺点在于计数器一直累加下去,可能存在某些页面的计数器值变得很大,即使他们在后面的很长时间都不被访问,也因为计数器而不被换出.

8. 老化算法

在NFU的基础上,每次时钟中断时,不再是直接将R加到计数器上,而是先将计数器右移一位,然后将R加到最左端的位置上.

每次缺页中断时,将计数器最小的页面换出即可.

老化算法

9. 工作集页面置换算法

一个进程当前正在使用的页面的集合成为它的工作集.如果该进程的工作集中的页面无法得到满足,就会出现频繁的页面置换调度,称为颠簸或抖动.

因此该算法的主要思想就是确定一个进程的工作集,将工作集需要用到的页面置入内存,当发生缺页中断时,置换掉不在工作集中的页面即可.

一种实现方式,为每个页面添加上次使用时间和访问位R.

当发生缺页中断时,检查每个页,如果R为1,则表明被访问,将当前实际时间替换上次使用时间

如果R为0,则计算生存时间(当前实际时间-上次使用时间),然后与一个阈值比较,如果大于阈值,则说明这个页面不在工作集中,替换即可.

如果R为0,但生存时间小于等于阈值,则需要记录生存时间最长的页面,因为可能无法找到合适的页面,这时就需要替换生存时间最长的页面.

如果全部页面的R都为1,那么随机替换一个页面,最好是未被修改过的页面.

10. 工作集时钟页面置换算法

该算法将工作集页表构造为一个循环链表.

当发生缺页中断时,如果R位为1,则将该页的R位置为0,然后指针前移

如果R位为0,则检查生存时间和是否修改,然后生存时间大于阈值并且是干净未修改的,则可以直接置出.

若该页被修改过,则需要指针继续前移.

如果有写操作,则最终会有干净的页面,因此置换遇到的第一个干净的页面即可.

如果所有页面都在工作集中,则随便置换一个干净的页面.如果不存在干净的页面,则将指针处的页面写回磁盘,并置换.

页面置换算法总结

置换算法总结