操作系统简介：存储管理

1. 基本概念

• 存储器结构
  存储器的功能是保存数据，存储器的发展方向是高速度、大容量和小体积。
  一般存储器的结构有“寄存器-主存-外存”结构和“寄存器-缓存-主存-外存”结构，如图所示。
  

• 地址重定位
  将逻辑地址转换成主存物理地址的过程称为地址重定位。在可执行文件装入时，需要解决可执行文件中地址(指令和数据)与主存地址的对应关系，由操作系统中的装入程序(Loader)和地址重定位机构来完成。地址重定位分为静态地址重定位和动态地址重定位。

2. 存储管理方案

存储管理的主要目的是解决多个用户使用主存的问题。其管理方案主要包括分区存储管理、分页存储管理、分段存储管理、段页式存储管理以及虚拟存储管理。

2.1 分区存储管理

分区存储管理是早期的存储管理方案，其基本思想是把主存的用户区划分成若干个区域,每个区域分配给一个用户作业使用，并限定它们只能在自己的区域中运行，这种主存分配方案就是分区存储管理方式。按分区的划分方式不同，可分为固定分区、可变分区和可重定位分区。

1. 固定分区：静态分区方法，系统生成时固定生成，每个区域可以不等，操作系统通过主存分配情况表管理主存。
2. 可变分区：可变分区分配需要两种管理表格：已分配表和未分配表。请求和释放分区主要有4种算法：最佳适应算法、最差适应算法、首次适应算法和循环首次适应算法。
3. 可重定位分区。基本思想是移动所有已分配好的分区，使之成为连续区域。当请求空间不足时发生。

• 分区保护
  目的是防止未经校核的用户访问分区，常用如下两种方式：上界/下界寄存器保护（上界寄存器≤物理地址≤下界寄存器）、基址/限长寄存器保护（基址寄存器≤物理地址<基址寄存器+限长寄存器）。

2.2 分页存储管理

分页存储管理方案是对分区存储管理方案的优化。

• 纯分页存储管理

3. 页表
   将进程的每一页离散地分配到内存的多个物理块中后，系统应保证能在内存中找到每个页面所对应的物理块。为此，系统为每个进程建立了一张页面映射表，简称页表，如图所示。
   

• 快表
  从地址映射的过程可以发现，页式存储管理至少需要两次访问内存，第一次是访问页表，得到数据的物理地址;第二次是存取数据。若采用间接寻址访问数据，还需要再进行地址变换。为了提高访问内存的速度，可以在地址映射机构中增加一组高速寄存器，用来保存页表，这种方法需要大量的硬件开销。另一种方法是在地址映射机构中增加一个小容量的联想存储器，联想存储器由一组高速存储器组成，称为快表，用来保存当前访问频率高的少数活动页的页号及相关信息。

2.3 分段存储管理

2.4 虚拟存储管理

• 程序局部性原理：程序在执行时将呈现出局部性规律，即在一段时间内，程序的执行仅局限于某个部分。程序的局限性表现在时间局限性和空间局限性两个方面。
• 虚拟存储器的实现
  虚拟存储器具有请求调入功能和置换功能，可以把作业的一部分装入主存使其开始运行，能从逻辑上对主存容量进行扩充。虚拟存储器的逻辑容量由主存和外存容量之和以及 CPU 可寻址的范围来决定，其运行速度接近于主存速度，成本接近于外存。虚拟存储器实现主要有以下3 种方式。
  1. 请求分页系统。以页为单位调入和置换来执行程序。
  2. 请求分段系统。以段为单位
  3. 请求段页式系统。
• 请求分页管理的实现
  请求分页是在纯分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页式虚拟存储系统，是目前常用的一种虚拟存储器的方式。
  在请求分页系统中，每当所要访问的页面不在主存时，便产生一个缺页中断，请求调入所缺的页。缺页中断与一般中断的主要区别在于:缺页中断在指令执行期间产生和处理中断信号,而一般中断在一条指令执行结束后，下一条指令开始执行前检查和处理中断信号;缺页中断返回到被中断指令的开始重新执行该指令，而一般中断返回到下一条指令执行;一条指令在执行期间，可能会产生多次缺页中断。

页面置换算法

在进程运行过程中，如果发生缺页而内存中又无空闲块时，为了保证进程能正常运行，就必须从内存中调出一页程序或数据送入磁盘的对换区。置换算法的好坏将直接影响系统的性能，不适当的算法可能会导致刚被换出的页很快又被访问，需重新调入，使得系统频繁地更换页面，以致一个进程在运行中把大部分时间花费在页面置换工作上，称该进程发生了**“抖动”(Thrashing，也称颠簸)**。请求分页系统的核心问题是选择合适的页面置换算法。常用的页面置换算法如下所述。

1. 最佳置换算法：选择那些永不使用，或者是在最长时间内不再被访问的页面置换出去。但是要确定哪一个页面是未来最长时间内不再被访问的，很难估计。
   

2. 先进先出置换算法：总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。但是可能发生Belady现象，是指如果对一个进程未分配它所要求的全部页面，有事就会出现分配的页面数增加但缺页率反而增加的异常现象。
   

3. 最近最少使用置换算法：选择最近最少使用的页面予以淘汰，系统在每个页面设置一个访问字段，用于记录这个页面自上次被访问以来所经历的时间T，当要淘汰一个页面时，选择T最大的页面。
   

4. 最近未用置换算法
   NRU 算法是将最近一段时间未引用过的页面换出。这是一种 工RU 的近似算法。该算法为每个页面设置一位访问位，将内存中的所有页面通过链接指针连成一个循环队列。当某页被访问时，其访问位置 1。在选择一页淘汰时，就检查其访问位，如果是0，就选择该页换出;若为 1，则重新置为 0，暂不换出该页，在循环队列中检査下一个页面，直到找到访问位为0的页面为止。该算法只有一位访问位，只能用它表示该页是否已经使用过，若未使用过，则可将其置换出去。