【操作系统】一文搞定操作系统存储管理功能！

写在前面

• 关于文章

  内存管理是操作系统的重要功能之一,对内存管理的好坏直接影响计算机系统工作性能的高低。在这里主要学习操作系统中的存储管理功能，重点学习几种存储管理方案以及空闲分区分配策略和页面置换算法等等。

  • 上一篇文章：【操作系统】信号量机制的应用 - 编程那点事儿 (imyjs.cn)

• 我的站点

  网络云书签-理想 (imyjs.cn)

  理想智能云解析 (imyjs.cn)

  任务墙 (imyjs.cn)

  LiXiang's Blog (gitee.io) 不再更文

  学编程那点事儿 (imyjs.cn)

• 联系我

  🐧：2410685763

  WeChat：Super_Baby_00

  公众号：编程那点事儿

概要

计算机系统中的存储器可以分成两类:内存储器(简称内存)和外存储器(简称外存)。处理器可以直接访问内存,但不能直接访问外存。CPU要通过启动相应的输入/输出设备后才能使外存与内存交换信息。
内存管理是操作系统的重要功能之一,对内存管理的好坏直接影响计算机系统工作性能的高低。

基本概念

在计算机系统中,存储器是处理器处理的信息的来源与归宿,占据着重要地位。

存储体系

在上述存储体系中包含:

• 少量的、非常快速、昂贵、内容易变的高速缓存器(Cache) ,通常是百KB的数量级;
• 若干兆字节、中等速度、中等价格、内容易变的内存(RAM) ,通常是千MB的数量级;
• 低速、价廉、内容不易变的外存(磁盘),通常是百至千GB的数量级;
• 如果配有光盘或者磁带机,外存的容量可以增大至千GB甚至更大。

快速存储设备和大容量存储设备必须构成为统一的整体,由操作系统协调这些存储器的使用。对于内存速度和容量的要求是,内存的直接存取速度尽量快到与CPU取指速度相匹配,其容量大到能装下当前运行的程序与数据,否则CPU执行速度就会受到内存速度和容量的影响而得不到充分发挥。

存储管理任务

任何程序和数据以及各种控制用的数据结构都必须占用一定的存储空间,因此,存储管理直接影响系统性能。

存储器由内存和外存组成。所谓内存空间,是由存储单元(字节或字)组成的一维连续的地址空间,简称内存空间。

内存空间用来存放当前正在运行程序的代码及数据,是程序中指令本身地址所指的亦即程序计数器所指的存储空间。

内存空间一般分为两部分:

• 系统区,用以存放操作系统常驻内存部分,用户不能占用这部分空间;
• 用户区,分配给用户使用,用于装入并存放用户程序和数据,这部分的信息随时都在发生变化。

  存储管理实质上就是管理供用户使用的那部分空间。

为了对内存进行有效的管理,一般把内存分成若干个区域。即使在最简单的单道、单用户系统中,至少也要把它分成两个区域:在一个区域内存放系统软件,如操作系统本身;而另外一个区域则用于安置用户程序。显然,在多道、多用户系统中,为了提高系统的利用率,需要将内存划分成更多的区域,以便支持多道程序。

内存的分配和回收

一个有效的存储分配机制,应对用户提出的需求予以快速响应,为之分配相应的存储空间;在用户程序不再需要它时及时回收,以供其他用户使用。为此,应该具有以下功能:

• (1）记住每个存储区域的状态。内存空间哪些是分配了的,哪些是空闲的?这就需要设置相应的分配表格,记录内存空间使用状态。
• (2）实施分配。当用户提出申请时,按需要进行分配,并修改相应的分配表格。分配方式有静态分配和动态分配两种。
• ( 3）回收。接受用户释放的区域,并修改相应的分配表格。

为实现上述功能,必须引入分配表格,通称为内存分配表,其组织方式包括:

内存分配有两种方式:

• (1）静态分配。程序要求的内存空间是在目标模块连接装入内存时确定并分配的,并且在程序运行过程中不允许再申请或在内存中“搬家”,即分配工作是在程序运行前一次性完成。
• (2）动态分配。程序要求的基本内存空间是在目标模块装入时确定并分配的。但是在程序运行过程中,允许申请附加的内存空间或在内存中“搬家”,即分配工作可以在程序运行前及运行过程中逐步完成。

存储共享

存储共享是指两个或多个进程共用内存中的相同区域,这样不仅能使多道程序动态地共享内存,提高内存利用率,而且还能共享内存中某个区域的信息。共享的内容包括:代码共享和数据共享,特别是代码共享要求代码必须是纯代码。

存储保护

存储保护的目的在于为多个程序共享内存提供保障,使在内存中的各程序只能访问其自己的区域,避免各程序间相互干扰。

存储保护通常需要有硬件支持,并由软件配合实现。

存储保护的内容包括:保护系统程序区不被用户有意或无意的侵犯;不允许用户程序读写不属于自己地址空间的数据,如系统区地址空间、其他用户程序的地址空间。

• 地址越界保护

  每个进程都具有其相对独立的进程空间,如果进程在运行时所产生的地址超出其地址空间,则发生地址越界。地址越界可能侵犯其他进程的空间,影响其他进程的正常运行;也可能侵犯操作系统空间,导致系统混乱。因此,对进程所产生的地址必须加以检查,发生越界时产生中断,由操作系统进行相应处理。

• 权限保护

  对于允许多个进程共享的公共区域,每个进程都有自己的访问权限。例如,有些进程可以执行写操作,而其他进程只能执行读操作等。因此,必须对公共区域的访问加以限制和检查。

  • 对属于自己区域的信息,可读可写。
  • 对公共区域中允许共享的信息或获得授权可使用的信息,可读而不可修改。
  • 对未获授权使用的信息,不可读、不可写。

“扩充”内存容量

具体实现是在硬件支持下,软件、硬件相互协作,将内存和外存结合起来统一使用。通过这种方法扩充内存,使用户在编制程序时不受内存限制。借助虚拟存储技术或其他交换技术,达到在逻辑上扩充内存容量,亦即为用户提供比内存物理空间大得多的地址空间,使得用户感觉他的程序是在这样一个大的存储器中运行。

地址转换

一般而言,存储器以字节(每个字节为8个二进制位)为编址单位,每个字节都有一个地址与其对应。假定存储器的容量为n字节,其地址编号顺序为0,1 ,2,… ,n-1。这些地址称为内存的“绝对地址”,与绝对地址对应的内存空间称为“物理地址空间”。

在多道程序设计的系统中,内存中同时存放了多个用户程序。操作系统根据内存的使用情况为用户分配内存空间。因此,每个用户不能预先知道他的程序将被存放到内存的什么位置。这样,用户程序中就不能使用内存的绝对地址。为了方便用户,每个用户都可认为自己的程序和数据存放在一组从“0”地址开始的连续空间中。用户程序中使用的地址称为“逻辑地址”,与逻辑地址对应的存储空间称为“逻辑地址空间”。

地址重定位

当用户程序进入计算机系统请求执行时,存储管理要为它分配合适的内存空间,这个分配到的内存空间可能是从某单元开始的一组连续的地址空间。该地址空间的起始地址是不固定的,而且逻辑地址与分到的内存空间的绝对地址经常不一致。程序执行时不能按照其逻辑地址到内存中存取信息,处理器必须按照实际地址去访问内存才能保证程序的正确执行。

为了保证程序的正确执行,必须根据分配给程序的内存区域对程序中指令和数据的存放地址进行重定位,即要把逻辑地址转换成绝对地址。
把逻辑地址转换成绝对地址的工作称为“地址重定位"或“地址转换”,又称“地址映射”。

静态重定位

在装入一个程序时,把程序中的指令地址和数据地址全部转换成绝对地址。由于地址转换工作是在程序开始执行前集中完成的,所以在程序执行过程中就无须再进行地址转换工作,这种地址转换方式称为“静态重定位”。

动态重定位

在装入程序时,不进行地址转换,而是直接把程序装入到分配的内存区域中。在程序执行过程中,每当执行一条指令时都由硬件的地址转换机构将指令中的逻辑地址转换成绝对地址。这种方式的地址转换是在程序执行时动态完成的,故称为“动态重定位”。

动态重定位由软件和硬件相互配合来实现。硬件要有一个地址转换机构,该机构可由一个基址寄存器和一个地址转换线路组成。

存储管理为程序分配内存区域后,装入程序把程序直接装到所分配的区域中,并把该内存区域的起始地址存入相应程序进程的进程控制块中。当程序进程被调度占用处理器时,随同现场信息的恢复,程序所占的内存区域的起始地址也被存放到“基址寄存器”中。程序执行时,处理器每执行一条指令都会把指令中的逻辑地址与基址寄存器中的值相加得到绝对地址,然后按绝对地址访问内存。

分区存储管理方案

分区存储管理是能满足多道程序运行的最简单的存储管理方案。

其基本思想是把内存划分成若干个连续区域,称为分区,每个分区装入一个运行程序。

分区的方式可以归纳成固定分区和可变分区两类。

固定分区

系统先把内存划分成若干个大小固定的分区，一旦划分好,在系统运行期间便不再重新划分。为了满足不同程序的存储要求,各分区的大小可以不同。

由于每一分区的大小是固定的,就对可容纳程序的大小有所限制了。因此,程序运行时必须提供对内存资源的最大申请量。

用于固定分区管理的内存分配表是一张分区说明表,按顺序每个分区在分区说明表中对应一个表目。表目内容包括分区序号、分区大小、分区起始地址以及使用状态(空闲或占用)。

当一个程序在运行时,先要根据其对内存的需求量,按一定的分配策略在分区说明表中查找空闲分区。若找到合乎需要的分区,就将该分区分配给程序,并将该分区置为占用状态。当程序完成时释放这块分区内存,由系统回收,并在分区说明表中将回收的分区重新置为空闲状态。

可变分区

基本思想

系统不预先划分固定分区,而是在装入程序时划分内存分区,使为程序分配的分区的大小正好等于该程序的需求量,且分区的个数是可变的。

系统初启后,在内存中除操作系统区之外,其余空间为一个完整的大空闲区。当有程序要求装入内存运行时,系统从该空闲区中划分出一块与程序大小相同的区域进行分配。当系统运行一段时间后,随着一系列的内存分配和回收,原来的一整块大空闲区形成了若干占用区和空闲区相间的布局。若有上下相邻的两块空闲区,系统应将它们合并成为一块连续的大空闲区。

移动技术

内存经过一段时间的分配回收后,会存在很多很小的空闲块。每一块空闲块都不足以满足程序进一步分配内存的要求,但其总和却可以满足程序的分配要求,这些空闲块被称为碎片。在可变分区管理方案中,随着分配和回收次数的增加,必然导致碎片的出现。

解决碎片问题的办法是在适当时刻进行碎片整理,通过移动内存中的程序,把所有空闲碎片合并成一个连续的大空闲区且放在内存的一端,而把所有程序占用区放在内存的另一端。这一技术称为“移动技术”或“紧凑技术”或“紧缩技术”。

移动技术可以集中分散的空闲区,提高内存的利用率,便于作业动态扩充内存。采用移动技术要注意以下问题:

• (1)移动技术会增加系统的开销。采用移动技术,需要大量地在内存中进行数据块移动的操作,还要修改内存分配表和进程控制块,这些工作既增加了系统程序的规模,也增大了系统运行时间。
  (2）移动是有条件的。不是任何在内存中的作业都能随时移动。比如,若某个进程正在与外部设备交换信息,与该进程有关的数据块就不能移动,只能在与外部设备的信息交换结束之后,再考虑移动。
  所以,在采用移动技术时应该尽可能减少需要移动的作业数和信息量。

可变分区实现

采用可变分区方式管理时,要有硬件的地址转换机构作支持。硬件设置两个专用的控制寄存器:基址寄存器和限长寄存器。

• 基址寄存器用来存放程序所占分区的起始地址
• 限长寄存器用来存放程序所占分区的长度。

实现步骤：当程序被装到所分配的分区后,

• ①把分区的起始地址和长度作为现场信息存入该作业进程的进程控制块中。
• ②进程调度选中某程序进程占用处理器时,作为现场信息的分区起始地址和长度被送入基址寄存器和限长寄存器中。
• ③程序执行过程中,处理器每执行一条指令都要取出该指令中的逻辑地址。

  当逻辑地址小于限长寄存器中的限长值时,逻辑地址加基址寄存器值就可得到绝对地址。当逻辑地址大于限长寄存器中的限长值时,表示欲访问的内存地址超出了所分配的分区范围。这时就不允许访问,而形成一个“地址越界”的程序性中断事件。

为了实现可变分区的管理,必须设置某种数据结构用以记录内存分配的情况,确定某种分配策略并且实施内存的分配与回收。内存分配表由两张表格组成。

• 已分配区表：记录已装入的程序在内存中占用分区的起始地址和长度,用标志位指出占用分区的程序名。
• 空闲区表：记录内存中可供分配的空闲区的起始地址和长度,用标志位指出该分区是未分配的空闲区。

★空闲分区的分配策略★

最先适应算法

最先（首次）适应算法（First Fit):从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业，这种方法目的在于减少查找时间。为适应这种算法，空闲分区表（空闲区链〉中的空闲分区要按地址由低到高进行排序。该算法优先使用低址部分空闲区,在低址空间造成许多小的空闲区，在高地址空间保留大的空闲区。

优先使用低地址。在可变分区内存管理中，倾向于优先使用低地址空闲区的算法是首次适应算法。

最优适应算法

最优（佳）适应算法（Best Fit）:从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小。为适应此算法，空闲分区表（空闲区链）中的空闲分区要按从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。该算法保留大的空闲区，但造成许多小的空闲区。

在可变分区存储管理方案中，为加快内存分配，当采用最佳适应算法时空闲区的组织应该是按空闲区大小递增顺序排列。

最坏适应算法

最差适配算法，从全部空闲区中找出能满足作业要求的、且大小最大的空闲分区，从而使链表中的结点大小趋于均匀，适用于请求分配的内存大小范围较窄的系统。为适应此算法，空闲分区表（空闲区链)中的空闲分区要按大小从大到小进行排序，自表头开始查找到第一个满足要求的自由分区分配。该算法保留小的空闲区，尽量减少小的碎片产生。

下次适应算法

当接到内存申请时，查找分区说明表，从上一次分配的位置开始扫描内存，选择下一个大小足够的可用块。

分区的回收

当用户程序执行结束后,系统要回收已使用完毕的分区,将其记录在空闲区表中。在收回空间时,应首先检查是否有与回收区相邻的空闲区，若有,则应合并成一个空闲区登记。

一个归还区可以有上邻空闲区,也可以有下邻空闲区,或既有上邻空闲区又有下邻空闲区,或既无上邻空闲区又无下邻空闲区。一般情况下应考虑如下四种可能性。

• （1）回收分区的上邻分区是空闲的,需要将两个空闲区合并成一个更大的空闲区,然后修改空闲区表。
• （2）回收分区的下邻分区是空闲的,需要将两个空闲区合并成一个更大的空闲区,然后修改空闲区表。
• （3）回收分区的上邻分区和下邻分区都是空闲的,需要将三个空闲区合并成一个更大的空闲区,然后修改空闲区表。
• （4）回收分区的上邻分区和下邻分区都不是空闲的,则直接将空闲分区记录在空闲区表中。

分区的保护

• 系统设置界限寄存器
  通常,系统设置一对界限寄存器,用来存放现行进程的存储界限。在进程的PCB中保存界限值,当轮到该进程执行时,将界限值作为进程现场的一部分恢复。在进程执行过程产生的每一个访问内存的地址,硬件都自动将其与界限寄存器中的值进行比较,若发生地址越界,便产生保护性地址越界中断。
• 保护键

  即为每个分区分配一个保护键,相当于一把锁。同时为每个进程分配一个相应的保护键,相当于一把钥匙,存放在程序状态字中。每当访问内存时,都要检查钥匙和锁是否匹配,若不匹配,将发出保护性中断。

分区存储小结

分区管理是实现多道程序设计的一种简单易行的存储管理技术。

通过分区管理,内存真正成了共享资源,有效地利用了处理机和I/O设备,从而提高了系统的吞吐量和缩短了周转时间。

分区存储管理算法比较简单,所采用的表格不多,实现起来比较容易,内存额外开销较少,存储保护措施也很简单。

在内存利用率方面,可变分区的内存利用率比固定分区高。

分区管理的主要缺点是,内存使用仍不充分,并且存在着较为严重的碎片问题。虽然可以解决碎片问题,但需要移动大量信息,浪费了处理机时间。此外,分区管理不能为用户提供“虚存”,即不能实现对内存的“扩充”,每一个用户程序的存储要求仍然受到物理存储器实际存储容量的限制。分区管理要求运行程序一次全部装入内存之后,才能开始运行。这样,内存中可能包含有一些实际不使用的信息。

覆盖技术与交换技术

覆盖技术

覆盖技术是指一个程序的若干程序段或几个程序的某些部分共享某一个存储空间。

覆盖技术的实现是把程序划分为若干个功能上相对独立的程序段,按照其自身的逻辑结构使那些不会同时执行的程序段共享同一块内存区域。未执行的程序段先保存在磁盘上,当有关程序段的前一部分执行结束后,把后续程序段调入内存,覆盖前面的程序段。

覆盖技术不需要任何来自操作系统的特殊支持,可以完全由用户实现,即覆盖技术是用户程序自己附加的控制。覆盖技术要求程序员提供一个清楚的覆盖结构,即程序员要把一个程序划分成不同的程序段,并规定好它们的执行和覆盖的顺序。操作系统则根据程序员提供的覆盖结构,完成程序段之间的覆盖。

覆盖技术可以由编译程序提供支持。此时被覆盖的块是由程序员或编译程序预先(在执行前)确定的。总之,覆盖可以从用户级彻底解决内存小装不下程序的问题。

覆盖技术打破了需要将一个程序的全部信息装入内存后程序才能运行的限制。

它利用相互独立的程序段之间在内存空间的相互覆盖,逻辑上扩充了内存空间,从而在某种程度上实现了在小容量内存上运行较大程序的目的。

交换技术

交换技术又称对换技术。在分时系统中,用户的进程比内存能容纳的数量要多,这就需要在磁盘上保存那些内存放不下的进程。在需要运行这些进程时,再将它们装入内存。

进程从内存移到磁盘并再移回内存称为交换。交换技术是进程在内存与外存之间的动态调度,是由操作系统控制的。

系统可以将那些不在运行中的进程或其一部分调出内存,暂时存放在外存上的一个后备存储区(称为盘交换区Swapping Area)中 ,以腾出内存空间给现在需要内存空间的进程,后者可能需要从外存换入内存,以后再将换出的进程调入内存继续执行。

交换技术的目的是尽可能达到“足够快地交换进程,以使当CPU调度程序想重新调度CPU时,总有进程在内存中处于就绪(准备执行)状态”的理想状态,从而提高内存利用率。

交换技术的缺点是,由于交换时需要花费大量的CPU时间,这将影响对用户的响应时间。

减少交换的信息量是交换技术的关键问题。合理的做法是,在外存中保留每个程序的交换副本,换出时仅将执行时修改过的部分复制到外存。

同覆盖技术一样,交换技术也是利用外存来逻辑地扩充内存,它的主要特点是,打破了一个程序一旦进入内存便一直运行到结束的限制。

覆盖技术与交换技术的发展导致了虚拟存储技术的出现。

页式存储管理方案

当用分区方式管理内存时,每道程序都占用内存的一块或几块连续的存储空间。因此,当内存中无足够大的连续空间时,程序就无法装入,必须移动已在内存中的某些程序后才能再装入新的程序,这不仅不方便,而且系统开销也增大。

如果可以把一个逻辑地址连续的程序分散存放到几个不连续的内存区域中,并且保证程序的正确执行,则既可充分利用内存空间,又可减少移动所花费的开销。

基本思想

支持页式存储管理的硬件部件通常称为“存储管理部件”( Memory Man-agement Unit , MMU)。
存储管理部件首先把内存分成大小相等的许多区,把每个区称为“块”,块是进行主存空间分配的物理单位。同时,要求程序中的逻辑地址也进行分页,页的大小与块的大小一致。这样，就可把程序信息按页存放到块中。于是,页式存储器提供编程使用的逻辑地址由两部分组成:页号和页内地址。

页式存储的地址结构确定了内存分块的大小,也就决定了页面的大小。

存储空间的分配与回收

页式存储管理分配内存空间以物理页面为单位,由于物理页面的大小是固定的,所以只要在内存分配表中具有可以指出已经分配块、尚未分配块以及当前剩余的空闲块数等三种不同的标识即可。
简单的内存分配表可以用一张“位示图"构成。假设内存的可分配区域被分成256块,则可用字长为32位的8个字作为“位示图”。位示图中的每一位与一个内存块对应,每一位的值可以是0或1,0表示对应的内存块为空闲,1表示已占用。在位示图中再增加一个字节记录当前剩余的总空闲块数。初始化时系统在位示图中把操作系统占用块所对应的位置成1 ,其余位均置0,剩余空闲块数为可分配的空闲内存块总数。

在进行内存分配时,

• 先查看空闲块数是否能满足程序要求。

  若不能满足,则不进行分配,程序就不能装入内存;若能满足,则根据需求从位示图中找出一些为0的位,把这些位置成1,并从空闲块数中减去本次分配的块数,然后按照找到的位计算出对应的块号。

• 当找到一个为0的位后,根据它所在的字号、位号,按如下公式就可计算出对应的块号:

  块号=字号×字长＋位号

• 把程序装入到这些内存块中,并为该程序建立页表。

当程序执行结束时,则应收回它所占用的内存块。根据归还的块号计算出该块在位示图中对应的位置,将占用标志修改成0,再把回收的块数加人到空闲块数中。
假定归还块的块号为i,则在位示图中对应的位置为:

地址转换与快表

页式存储管理要有硬件的地址转换机构作支持。同时,要为每个被装入内存的进程提供一张页表,该页表所在内存的起始地址和长度作为现场信息存放在该进程的进程控制块中。一旦进程被调度进入处理器执行,这些信息将被作为恢复现场信息送入系统的地址映射机制中的寄存器里。

地址转换

为了实现页式存储管理,系统要提供一对硬件的页表控制寄存器,即页表起始地址寄存器和页表长度寄存器,另外还需要高速缓冲存储器的支持。

• 页表起始地址寄存器用于保存正在运行进程的页表在内存的首地址,当进程被调度程序选中投人运行时,系统将其页表首地址从进程控制块中取出送入该寄存器。
• 页表长度寄存器用于保存正在运行进程的页表的长度,当进程被选中运行时,系统将它从进程控制块中取出送入该寄存器。

页表指出该程序逻辑地址中的页号与所占用的内存块号之间的对应关系。页表的长度由程序拥有的页面数而定,故每个程序的页表长度可能是不同的。

页表又是硬件进行地址转换的依据,每执行一条指令时按逻辑地址中的页号查页表。若页表中无此页号,则产生一个“地址错”的程序性中断事件。若页表中有此页号,则可得到对应的内存块号,按计算公式可转换成访问的内存的物理地址。

物理地址的计算公式为:

页表

• 多级页表

  称存放页表的页面为页表页。一般来说,页表页可以不连续存放,因此需要对页表页的地址进行索引。一个简单的解决办法就是分级,例如采用两级页表,即页面大小为4KB的32位机器,逻辑地址可被划分为10位页目录、10位页表和12位的页内偏移。
  在大多数操作系统中采用二级页表,即由页表页和页目录一起构成进程页表。

  

  其中,第一级表示页目录,保存页表页的地址;第二级表示页表页,保存物理页面号(即内存块号)。

• 散列页表

  当地址空间大于32位时,一种常见的方法是使用以页号为散列值的散列页表。其中每个表项都包含一个链表,该链表中元素的散列值都指向同一个位置。这样,散列页表中的每个表项都包含三个字段:( a)虚拟页号,(b)所映射的页框号,( c)指向链表中下一个元素的指针。
  使用的算法如下:

  由虚拟页号得到散列值来查找散列页表,并将此页号与链表中的第一个元素的字段( a)进行比较。如果匹配,则相应的页框号[字段(b)]就可用于形成物理地址。如果不匹配,则沿链表依次寻找相匹配的表项。
  

• 反置页表

  在反置页表中,每个物理页框对应一个表项,每个表项包含与该页框相对应的虚拟页面地址以及拥有该页面进程的信息。因此,整个系统中只存在一个页表,并且每个页框对应其中一个表项。由于一方面系统中只有一个页表,而另一方面系统中又存在着多个映射着物理内存的地址空间,因此需要在反置页表中存放地址空间标志符这样就保证了一个特定进程的逻辑页面可以映射到相应的物理页框上。

  尽管这种方法减少了为存放每个页表所使用的内存数量,但却增加了内存访问时的查表时间。由于反置页表是按照物理地址排序的,而在使用时却是按照虚拟地址查找,因此有可能为了寻找相匹配的表项而遍历全表。

快表

一般而言,页式存储管理中的页表是存放在内存中的。于是,当要按给定的逻辑地址进行读写时,必须访问两次内存。两次访问内存显然延长了指令的执行周期,降低了执行速度。

• 第一次按页号读出页表中对应的块号
• 第二次按计算出来的绝对地址进行读写。

为了提高存取速度,有两种方法。

• 在地址映射机制中增加一组高速寄存器保存页表，这需要大量的硬件开销,在经济上不可行。
• 在地址映射机制中增加一个小容量的联想寄存器(相联存储器),它由高速缓冲存储器组成。

利用高速缓冲存储器存放当前访问最频繁的少数活动页面的页号,这个高速缓冲器被称为“快表”,也称为转换检测缓冲器(Translation Lookaside Buffer , TLB)。
快表中登记了页表中的一部分页号与内存块号的对应关系。根据程序的存储访问局部性原理,在一段时间内总是经常访问少数几页,若这些页登记在快表中,显然可快速查找并提高指令执行速度。

快表只存放当前进程最活跃的少数几页,随着进程的推进,快表的内容动态进行更新。
快表内容的更新原理如下:

当某一用户程序需要存取数据时,根据该数据所在的逻辑页号在快表中找出对应的内存块号,然后拼接页内地址,以形成物理地址;如果在快表中没有相应的逻辑页号,则地址映射仍然通过内存中的页表进行;在得到内存块号后需将该块号填到快表的空闲单元中;若快表中没有空闲单元,则根据置换算法置换某一行,再填入新得到的页号和块号。

★虚拟页式存储管理★

如何解决程序规模大于内存的问题?早期的解决方案如覆盖技术是由程序员指定,系统辅助完成的,对程序员的要求甚高，而且容易出错。所以根本的解决方法是将这类工作全部交给操作系统完成。这就产生了虚拟存储技术。

虚拟存储技术

虚拟存储技术的基本思想是利用大容量的外存来扩充内存,产生一个比有限的实际内存空间大得多的,逻辑的虚拟内存空间,简称虚存,以便能够有效地支持多道程序系统的实现和大型程序运行的需要,从而增强系统的处理能力。

虚拟存储管理是由操作系统在硬件支持下把两级存储器(内存和外存)统一实施管理,达到“扩充”内存的目的,呈现给用户的是一个远远大于内存容量的编程空间,即虚存。

程序、数据、堆栈的大小可以超过内存的大小,操作系统把程序当前使用的部分保留在内存,而把其他部分保存在磁盘上,并在需要时在内存和磁盘之间动态交换。

虚拟存储管理支持多道程序设计技术。

实现虚拟存储器需要以下的硬件支持:

• (1)系统有容量足够大的外存。
• (2）系统有一定容量的内存。
• (3)最主要的是,硬件提供实现虚–实地址映射的机制。

虚拟存储器的工作原理如下:

虚拟存储技术同交换技术在原理上是类似的,其区别在于在传统的交换技术中,交换到外存上的对象一般都是进程,也就是说交换技术是以进程为单位进行的,如果一个进程所需内存大于当前系统内存,那么该进程就不能在系统中运行。而虚拟存储一般是以页或段为单位,所以如果一个进程所需内存大于当前系统内存,那么该进程仍然可以在系统中正常运行,因为该进程的一部分可以被换出到外存上。

虚拟页式存储管理

基本思想

在进程开始运行之前,不是装入全部页面,而是装入一个或零个页面,之后根据进程运行的需要,动态装入其他页面;当内存空间已满,而又需要装入新的页面时,则根据某种算法置换出某个页面,以便装入新的页面。
在使用虚拟页式存储管理时需要在页表中增加以下的表项:

缺页中断

若在页表中发现所要访问的页面不在内存,则产生缺页中断。当发生缺页中断时,操作系统必须在内存中选择一个页面将其移出内存,以便为即将调入的页面让出空间。如果要移走的页面在内存期间已经被修改过,就必须把它写回磁盘以更新该页在磁盘上的副本。如果该页没有被修改过,那么它在磁盘上的副本仍然是最新的,则不需要写回,调入的页直接覆盖被置换的页。

整个缺页处理过程简单阐述如下:

• (1）根据当前执行指令中的逻辑地址查页表的驻留位,判断该页是否在内存。
• (2）该页标志为“0”,形成缺页中断。保留现场。中断装置通过交换PSW让操作系统的中断处理程序占用处理器。
• (3）操作系统处理缺页中断,寻找一个空闲的页面。
• (4）若有空闲页,则把磁盘上读出的信息装入该页面中。
• (5）修改页表及内存分配表,表示该页已在内存。
• (6）如果内存中无空闲页,则按某种算法选择一个已在内存的页面,把它暂时调出内存。若在执行中该页面已被修改过,则要把该页信息重新写回到磁盘上,否则不必重新写回磁盘。当一页被暂时调出内存后,让出的内存空间用来存放当前需要使用的页面。页面被调出或装入之后都要对页表及内存分配表作修改。
• (7）恢复现场,重新执行被中断的指令。当重新执行该指令时,由于要访问的页面已被装入内存,所以可正常执行下去。

页面调度策略

调入策略

虚拟存储器的调入策略决定了什么时候将一个页由外存调入内存之中。在虚拟页式管理中有两种常用调入策略:

• 请求调页(Demand Paging):只调入发生缺页时所需的页面。这种调入策略实现简单,但容易产生较多的缺页中断,造成对外存IО次数多,时间开销过大,容易产生抖动现象。
• 预调页(Prepaging):在发生缺页需要调入某页时,一次调入该页以及相邻的几个页。这种策略提高了调页的I/O效率,减少了IO次数。但由于这是一种基于局部性原理的预测,若调入的页在以后很少被访问,则造成浪费。这种方式常在程序装入时使用。

通常对外存交换区的I/O效率比文件区的高。关于调入页面来源,通常有两种做法:

• 进程装入时,将其全部页面复制到交换区,以后总是从交换区调入。执行时调入速度快,要求交换区空间较大。
• 凡是未被修改的页面,都直接从文件区读入,而被置换时不需调出;已被修改的页面,被置换时需调出到交换区,以后从交换区调入。

置页策略

当线程产生缺页中断时,内存管理器还必须确定将调入的虚拟页放在物理内存的何处。用于确定最佳位置的一组规则称为“置页策略”。选择页框应使CPU内存高速缓存不必要的震荡最小。

置换策略

如果缺页中断发生时物理内存已满,“置换策略”被用于确定哪个虚页面必须从内存中移出,为新的页面腾出空位。在虚拟页式存储管理方案中,可采用两种分配策略,即固定分配策略和可变分配策略。在进行置换时,也可以采用两种策略,即全局置换和局部置换。将它们组合起来,有如下三种策略:

• 固定分配局部置换(Fixed Allocation , Local Replacement)。

  可基于进程的类型,为每一进程分配固定的页数的内存空间,在整个运行期间都不再改变。采用该策略时,如果进程在运行中出现缺页,则只能从该进程的N个页面中选出一个换出,然后再调入一页,以保证分配给该进程的内存空间不变。

• 可变分配全局置换(Variable Allocation, Global Replacement)。

  采用这种策略时,先为系统中的每一进程分配一定数量的物理块,操作系统本身也保持一个空闲物理块队列。当某进程发生缺页时,由系统的空闲物理块队列中取出一物理块分配给该进程。但当空闲物理块队列中的物理块用完时,操作系统才从内存中选择一块调出。该块可能是系统中任意一个进程的页。

• 可变分配局部置换(Variable Allocation，Local Replacement)。

  同样基于进程的类型,为每一进程分配一定数目的内存空间。但当某进程发生缺页时,只允许从该进程的页面中选出一页换出,这样就不影响其他进程的运行。如果进程在运行的过程中频繁地发生缺页中断,则系统再为该进程分配若干物理块,直到进程的缺页率降低到适当程度为止。

页面置换算法

如果刚被调出的页面又立即要用,因而又要把它装入,而装入不久又被选中调出,调出不久又被装入,如此反复,使调度非常频繁。这种现象称为“抖动”或称“颠簸”。

先进先出置换算法(FIFO)

先进先出页面置换算法总是选择最先装入内存的一页调出,或者说是把驻留在内存中时间最长的一页调出。即淘汰最早进入主存的页面;最早进入的页面，不再使用的可能性比最近调入的页面要大，先被置换。

FIFO页面置换算法有可能产生Belady异常现象。

FIFO算法简单,容易实现。

把装入内存的那些页面的页号**按进入的先后次序**排好队列,每次总是调出队首的页,当装入一个新页后,把新页的页号排入队尾。由操作系统维护一个所有当前在内存中的页面的链表,最老的页面在表头,最新的页面在表尾。当发生缺页时,置换表头的页面并把新调入的页面加到表尾。

最近最少使用算法(LRU)

该算法首选置换距离现在最长时间未被使用过的页面。LRU是Least Recently Used的缩写，即最近最少使用页面置换算法，首先置换近期最长时间以来没被访问的页面，是为虚拟页式存储管理服务的。

在页表中为每一页增加一个“计时”标志,记录该页面自上次被访问以来所经历的时间,每被访问一次都应从“0”开始重新计时。当要装入新页时,检查页表中各页的计时标志,从中选出计时值最大的那一页调出(即最近一段时间里最长时间没有被使用过的页) ,并且把各页的计时标志全置成“0”,重新计时。当再一次产生缺页中断时,又可找到最近最久未使用过的页,将其调出。

这种实现方法必须对每一页的访问情况时时刻刻地加以记录和更新,实现起来比较麻烦且开销比较大。

最近最不常使用算法（LFU)

最近最不常用页面置换算法，在虚拟页式系统中进行页面置换时，根据在一段时间里页面被使用的次数多少选择可以调出的页。该算法选择当前时间为止被访问次数最少的页置换。

为每一页设置一个计数器,每当访问一页时,就把该页对应的计数器加1。另外,操作系统还要确定一个周期T,在周期T的一段时间内，若没有发生缺页中断,则把所有的计数器清“0”,开始一个新的周期重新计数。若在周期T的时间内发生了缺页中断,则选择计数值最小的那页调出(它是最近一段时间内最不常用的页),同时把所有的计数器清“O”。

这个算法的实现要花很大的开销,并且要确定一个合适的周期T也有一定的难度。

理想页面置换算法(OPT)

理想页面置换算法(OPT)也叫最佳页面置换算法，从主存中移出永远不再需要的页面;如无这样的页面存在，则选择最长时间不需要访问的页面。所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率。

最近未使用页面置换算法（NRU)

为使操作系统能够收集有用的统计信息,在大部分支持虚存的计算机中,硬件为每一页面设置了两个状态位。当访问页面(读或写)时设置R位;当写入页面(即修改页面)时设置M位。这些位包含在页表项中。如果硬件没有这些位,则对其进行软件模拟。

用R位和M位可以构造一个简单的页面置换算法:当启动一个进程时,它的所有页面的两个位都由操作系统设置成0,定期将R位(比如在每次时钟中断时)清零,以区别最近没有被访问的页面和被访问的页面。

有四种页面置换:

• 第1类:没有被访问，没有被修改;
• 第2类:没有被访问，已被修改;
• 第3类:已被访问，没有被修改;
• 第4类:己被访问，已被修改。

NRU( Not Recently Used ,最近未使用)算法随机地从类编号最小的非空类中挑选一个页面淘汰之。这个算法隐含的意思是,在最近一个时钟滴答中(典型的时间是大约20 ms)置换一个没有被访问的已修改页面要比置换一个被频繁使用的“干净”页面好。

NRU的主要优点是易于理解和能够有效地被实现,虽然它的性能不是最好的,但是已经够用了。

第二次机会页面置换算法

在虚拟页式系统中进行页面置换时，检查进入内存时间最久页面的R位，如果是0，则置换该页;如果是1，就将R位清0，并把该页面放到链表的尾端，修改其进入时间，然后继续搜索，这一策略称为第二次机会页面置换算法。

基本思想是寻找一个最近的时钟间隔以来没有被访问过的页面。如果所有的页面都被访问过了,该算法就退化为FIFO算法。

小结

缺页中断率

假定一个程序共有n页,系统分配给它的内存块是m块( m,n均为正整数,且1≤m ≤n)。因此,该程序最多有m页可同时被装入内存。如果程序执行中访问页面的总次数为A,其中有F次访问的页面尚未装入内存,故产生了F次缺页中断。现定义:

显然,缺页中断率与缺页中断的次数有关。因此,影响缺页中断率的因素如下:

• 1)分配给程序的内存块数
  分配给程序的内存块数多,则同时装入内存的页面数就多,故减少了缺页中断的次数,也就降低了缺页中断率。反之,缺页中断率就高。
• 2)页面的大小
  页面的大小取决于内存分块的大小,块大则页面也大,每个页面大了则程序的页面数就少。装入程序时是按页存放在内存中的,因此,装入一页的信息量就大,就减少了缺页中断的次数,降低了缺页中断率。反之,若页面小则缺页中断率就高。
• 3)程序编制方法

  缺页中断率与程序的局部化程度密切相关。一般说来,希望编制的程序能经常集中在几个页面上进行访问,以减少缺页中断率。

• 4)页面置换算法
  页面置换算法对缺页中断率的影响也很大,调度不好就会出现“抖动”。理想的调度算法(OPT)能使缺页中断率最低。

虚拟存储管理的性能问题

引入虚拟存储管理,把内存和外存统一管理,其真正目的,是把那些访问概率非常高的页放入内存,减少内外存交换的次数。

任何程序对内存都有一个临界值要求,当分配给进程的物理页面数小于这个临界值时,缺页率上升;当分配给进程的物理页面数大于该临界值时,再增加物理页面数也不能显著减少缺页次数。因此,希望分配给进程的物理页面数与当前工作集大小一致。

在实现时,操作系统为每一个进程保持一个工作集,并为该进程提供与工作集大小相等的物理页面数,这一过程可动态调整。统计工作集大小一般由硬件完成,系统开销较大。

段式与段页式存储管理方案

段式存储管理方案

系统将内存空间动态划分为若干个长度不同的区域,每个区域称作一个物理段。每个物理段在内存中有一个起始地址,称作段首址。将物理段中的所有单元从0开始依次编址,称为段内地址。

用户程序则按逻辑上有完整意义的段来划分,称为逻辑段(简称段),例如主程序、子程序、数据等都可各成一段,每段对应于一个过程、一个程序模块或一个数据集合。将一个用户程序的所有逻辑段从0开始编号,称为段号。将一个逻辑段中的所有单元从0开始编址,称为段内地址。用户程序的逻辑地址由段号和段内地址两部分组成。

内存分配时,系统以段为单位进行内存分配,为每一个逻辑段分配一个连续的内存区(物理段)。逻辑上连续的段在内存中不一定连续存放。

操作系统为了实现段式管理,需要建立段表。当把程序装入内存后,系统为每个用户程序建立一张段表,用于记录用户程序的逻辑段与内存物理段之间的对应关系。段表包括逻辑段号,物理段起始地址(段首址)和物理段长度三项内容。用户程序有多少逻辑段,该段表里就登记多少行,且按逻辑段的顺序排列。段表存放在内存系统区里。

段式存储管理分配内存空间的方法与可变分区管理方案的分配方法相同,有相同结构的内存分配表,包括已分配区表和空闲区表。

段页式存储管理方案

段式存储管理为用户提供了一个二维地址空间,满足程序和信息的逻辑分段的要求。段式管理反映了程序的逻辑结构,有利于段的动态增长以及共享和内存保护等,这大大地方便了用户。

而页式存储管理的特征是等分内存,有效地克服了碎片,提高了存储器的利用率。从存储管理的目的来讲,主要是方便用户的程序设计和提高内存的利用率。为了保持页式在存储管理上的优点和段式在逻辑上的优点,结合页式和段式两种存储管理方案,形成了段页式存储管理。

段页式存储管理的基本思想是:用页式方法来分配和管理内存空间,即把内存划分为若干大小相等的页面;用段式方法对用户程序按照其内在的逻辑关系划分成若干段;再按照划分内存页面的大小,把每一段划分成若干大小相等的页面。内存是以页为基本单位分配给每个用户程序的,逻辑上相邻的页面在物理内存中不一定相邻。

由于内存空间的最小单位是页而不是段,从而内存可用区也就被划分成为若干个大小相等的页面,且每段所拥有的程序和数据在内存中可以分开存放。分段的大小不再受内存可用区的限制。

为了实现段页式管理,需要增加段式管理和页式管理的成分:系统必须为每个程序建立一张段表;由于一个段又被划分成了若干页,系统又为每个段建立一张页表。段表中记录了该段对应页表的起始地址和长度;而页表则给出该段的各个逻辑页面与内存块号之间的对应关系。

当然,也需要采用位示图法建立内存分配表,用于记录并管理内存空闲块。

在进行动态地址转换时,硬件提供段表起始地址寄存器,段表长度寄存器等支持。

微信关注

WeChat