内存管理

虚拟内存

虚拟内存的目的是为了让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。

为了更好的管理内存，操作系统将内存抽象成地址空间。每个程序拥有自己的地址空间，这个地址空间被分割成多个快，每一块称为一页。这些页被映射到物理内存，但不需要映射到连续的物理内存，也不需要将所有页都必须装在物理内存中。当程序引用到不在物理内存中的页时，由硬件执行必要的映射，将缺失的部分装入物理内存并重新执行失败指令。

从上面的描述中可以看出，虚拟内存允许程序不用将地址空间的每一页都映射到物理内存，也就是说一个程序不需要全部调入内存就可以运行。

分页系统地址映射

内存管理单元管理着地址空间和物理内存的转换，其中的页表存储着页（程序地址空间）和页框（物理内存空间）的映射表。

一个虚拟地址分成两个部分，一部分存储页面号，一部分存储偏移量。

页面置换算法

在程序运行过程中，如果要访问的页面不在内存中，就发生缺页中断从而将该页调入内存中。此时如果内存已无空闲空间，系统必须从内存中调出一个页面到磁盘对换区中来腾出空间。

页面置换算法的主要目标是使页面置换频率最低（也可以说缺页率最低）。

1.最佳置换算法

所选择的被换出的页面将是最长时间内不再被访问，通常可以保证获得最低的缺页率。

2.最近最久未使用算法(LRU算法)

虽然无法知道将来要使用的页面情况，但是可以知道过去使用页面的情况。LRU 将最近最久未使用的页面换出。

为了实现 LRU，需要在内存中维护一个所有页面的链表。当一个页面被访问时，将这个页面移到链表表头。这样就能保证链表表尾的页面是最近最久未访问的。

因为每次访问都需要更新链表，因此这种方式实现的 LRU 代价很高。

image-20200628175847422

3.最近未使用（NRU算法）

每个页面都会有两个状态位：R与M，当页面被访问时设置页面的 R=1,当页面被修改时设置M=1。其中R位会定时被清零。可以将页面分成以下四类：

  • R=0，M=0
  • R=0，M=1
  • R=1，M= 0
  • R=1，M=1

当发生缺页中断时，NRU算法随机地从类编号最小的非空类中挑选一个页面将它们换出。

NRU优先换出已经被修改的脏页面（R=0,M=1），而不是被频繁使用的干净页面（R=1,M=0）

4.先进先出（FIFO）

选择换出的页面是最先进入的页面。

但是最先进入的页面也有可能经常被访问到，可能导致缺页率升高。

5.第二次机会算法

FIFO 算法可能会把经常使用的页面置换出去，为了避免这一问题，对该算法做一个简单的修改：

当页面被访问 (读或写) 时设置该页面的 R 位为 1。需要替换的时候，检查最老页面的 R 位。如果 R 位是 0，那么这个页面既老又没有被使用，可以立刻置换掉；如果是 1，就将 R 位清 0，并把该页面放到链表的尾端，修改它的装入时间使它就像刚装入的一样，然后继续从链表的头部开始搜索。

6.时钟算法

第二次机会算法需要在链表中移动页面，降低了效率。时钟算法使用环形链表将页面连接起来，再使用一个指针指向最老的页面。

image-20200628181100863

分段

用户把自己的作业按照逻辑关系划分为若干个段，每个段都从0开始编址，并有自己的名字和长度(如汇编语言中的数据段、代码段、堆栈段等)。

因此，程序员们都迫切地需要访问的逻辑地址是由段名(段号)和段内偏移量(段内地址)决定的，这不仅可以方便程序员编程，也可使程序非常直观，更具可读性。

分页系统中的“页”只是存放信息的物理单位(块)，并无完整的逻辑意义

段页式

程序的地址空间划分成多个拥有独立地址空间的段，每个段上的地址空间划分成大小相同的页。这样既拥有分段系统的共享和保护，又拥有分页系统的虚拟内存功能。

分页与分段的比较

  • 对程序员的透明性：分页透明，但是分段需要程序员显式划分每个段。
  • 地址空间的维度：分页是一维地址空间，分段是二维的。
  • 大小是否可以改变：页的大小不可变，段的大小可以动态改变。
  • 出现的原因：分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护。