内存管理

Posted on | In , | Views:

存储管理

存储器抽象

操作系统需要为底层的硬件资源提供一种抽象，从而向上层隐藏底层实现细节，并便于上层软件的开发。

不抽象

而对存储器的最简单的抽象就是不进行抽象，每个程序可以直接访问内存，不同进程由于使用的是同一个地址空间，因此可以访问和修改其他进程甚至操作系统的数据。在这种抽象的情况下，如果需要运行多个进程可以利用交换技术，每次需要运行其他进程时会先将当前进程的数据保存到磁盘，然后调入其他进程；或者可以将地址空间进行划分，每个进程使用不同的地址空间来支持多个进程的运行。

地址空间

由于直接使用物理内存空间作为存储器抽象没有为上层软件开发提供一个足够好的环境，因此人们开始将物理内存抽象为地址空间。由于地址空间是每个内存可用于寻址的一系列地址的集合，因此需要将为每个进程划分一个自己的地址空间，一个方法是使用基址寄存器和界限寄存器，其中基址寄存器用于保存该进程地址空间的0地址在物理地址空间的位置，而界限寄存器用于保留程序的长度。因此程序需要装载到内存中连续的地址中，而每次进程访问内存、取指或者读写数据时CPU会在将地址发送到内存的总线前加上基址，同时监测偏移是否超过了界限寄存器。使用基址寄存器和界限寄存器可以非常方便的为每个进程提供私有的地址空间，但是由于每次访问内存都需要进行加法和比较运算因此会带来一定的额外负担，而且要求每次将程序装载到连续的内存空间中。

交换和虚拟内存

交换技术

内存空间如果不够了可以使用交换技术或者虚拟内存技术来解决该问题。交换技术通过将一个进程完整的调入内存，在运行一段时间后再存回磁盘。

虚拟内存

虽然存储器的容量在快速的增长，但仍然赶不上软件的需求，软件可能需要访问超过物理内存大小的地址空间，因此人们提出了虚拟内存，该技术的思想是每个程序拥有自己的地址空间，该空间被分割为多个块，每个块有连续的地址空间，这些块会被动态的映射到物理内存，程序在执行时不需要整个地址空间的内容都被调入物理内存中。在使用虚拟内存后程序访问内存的流程如下：

  • 程序给定需要访问的地址(虚拟地址)
  • 虚拟地址发送给内存管理单元(MMU)
  • 内存管理单元将虚拟地址映射为物理地址
  • 利用物理地址访问内存

而在上述过程中根据如何划分进程的虚拟地址空间又可细分为三类：页式、段式、段页式。

分页存储管理

使用分页存储管理时会将用户程序的地址空间划分为若干个大小相同的块，称为页，同时物理内存也被划分为多个大小相同的物理块，称为页框，其中页的大小与页框的大小相同。程序所使用的虚拟地址会被划分为两部分，前半部分为页号，后半部分为业内偏移，而MMU会将页号转换为存储相应页的物理内存的块号，其具体流程如下：

  • 根据虚拟地址(逻辑地址)计算页号和页内偏移
  • 比较页号与页表长度，查看是否应当产生越界中断
  • 检索快表(TLB)，如果命中则组合处物理地址
  • 利用页表寄存器中的内容计算对应页号所对应页表项的地址，并将对应条目存入TLB中，如果该页面尚未调入内存则还会产生缺页中断
  • 利用对应的页表项获取块号，并将块号与业内偏移组合为物理地址

虚拟地址翻译流程

分段存储管理

页面是主存物理空间中划分出来的等长的固定区域。分页方式的优点是页长固定，因而便于管理。但分页方式的缺点是页长与程序的逻辑大小无关。因此可以将虚拟内存空间划分为多个段，每个段是按照程序用途划分的可以动态改变长度的区域。在访问内存时与分页式管理相似，首先查找段表获得对应段在内存中的起始地址，然后与偏移一起组合为物理内存的地址。

段页式存储管理

由于页式内存管理能够提高内存利用率，段式内存管理能够反映程序的逻辑结构并利于段的共享，因此二者可以相结合为段页式内存管理。在段页式内存管理中，虚拟内存空间首先被划分为多个段，每个段再划分为多个固定大小的页，因此在使用段页式内存管理时每个段都会有一张页表，需要访问内存时会先将地址分为段号、页号和页内偏移，首先利用段号找到对应页表，再用页号查找对应的物理块的地址，最后和页内偏移组合为物理地址。

页面置换算法

在程序运行时，如果其需要访问的页面不在内存中则需要将其调入内存，如果内存已满则需要选择一个页面调换至磁盘，选择调出页面的算法即为页面置换算法。

最佳置换算法

最佳置换算法选择的是之后最长时间内不会被使用的页面，因此可以保证缺页率最低，但是由于人们目前无法预知未来，因此该算法无法实现。

FIFO算法

该算法选择最早进入内存的页面，但是可能由于某些页面经常被访问，因此可能带来缺页率的上升。

第二次机会算法

该算法是对FIFO的一个改进算法，由于FIFO可能将经常使用的页面置换出去，因此可以为每个页面加上一个访问标记，如果FIFO算法发现下一次要置换的页面最近被访问过则将该访问标记清楚然后置于FIFO队列的尾端。

时钟页面置换算法

由于第二次机会算法需要将页面在链表中不断一定，因此降低了效率，因此可以进一步改进，将所有页面连接成一个链表，有一个指针指向最老的页面，每次发生缺页中断时会将指针移动一位，如果该页面未被访问则将该页换出，如果该页已经被访问则清空访问位，然后移动至下一个页面。

最近未使用(NRU)算法

为每个页面加上两个状态位，一个用于标识该页面最近被访问过，另一个用于标识该页面已经被修改了。在刚开始时所有页面都标记为未被访问，未被修改，访问位会定期被清除。当发生缺页中断时所有页面可分为四类：1)未被访问、未被修改2)未被访问、被修改3)被访问、未被修改4)被访问、被修改，每次NRU都会从类号最小的的类中挑选一个淘汰。

最近最少使用(LRU)算法

该算法选择最长时间没有使用的页面调出内存，因为某一页面如果在过去很久都没有被访问，那么之后可能页不会被访问。但该方法实现较为复杂，因为需要每次维护一个所有页面的链表，最近最多使用的在表头，最近最少使用的在表尾，每次访问时需要在链表中找到一个页面，然后将其移动到表头。

最不常用(NFU)算法

每个页面关联到一个计数器，每次隔一段时间将计数器右移一位，然后将当前的访问位(0/1)加到计数器上。每次置换时选择计数器最小的页面。

参考

https://blog.csdn.net/yongchaocsdn/article/details/78533097
https://blog.csdn.net/zhongyangtony/article/details/80879425