首页 > 其他分享 >【操作系统】05-虚拟存储器

【操作系统】05-虚拟存储器

时间：2023-02-09 19:55:05浏览次数：49  
标签：操作系统 05 置换 访问 算法 内存 虚拟存储器 进程 页面

计算机操作系统——虚拟存储器

目录

第五章 虚拟存储器

5.1 虚拟存储器概述

第四章所介绍的各种存储器管理方式统称为传统存储器管理方式，其共同特点：都要求将一个作业全部装入内存后方能运行。

出现情况：

  1. 有的作业很大，其所要求的内存空间超过了内存总容量，作业不能全部被装入内存，致使该作业无法运行。
  2. 有大量作业要求运行，但由于内存容量不足以容纳所有这些作业，只能将少数作业装入内存让它们先运行，而将其它大量的作业留在外存上等待。

原因：内存容量不够大。

解决方法：

  1. 从物理上增加内存容量。
  2. 从逻辑上扩充内存容量。

5.1.1 常规存储器管理方式的特征和局部性原理

常规存储器管理方式的特征

  1. 一次性：指作业必须一次性全部装入内存方能开始运行。
  2. 驻留性：指作业被装入内存后，整个作业都一直驻留在内存中。

局部性原理

程序在运行时将呈现局部性的规律：在一较短的时间内，程序的执行仅局限于某个部分，相应地，它所访问的存储空间也局限于某个区域。

局限性又表现在两方面：

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

虚拟存储器的基本工作情况

程序在运行前：

  • 仅将当前要运行的少数页面或段先装入内存，其余部分暂留在盘上。

程序在运行时：

  • 如果所要访问的页(段)已调入内存，便可继续执行。
  • 如果所要访问的页(段)尚未调入内存(称为缺页或缺段)，便发出缺页(段)中断请求，OS将利用请求调页(段)功能将它们调入内存，程序继续执行。
  • 如果此时内存已满，无法再装入新的页(段)，则OS利用页(段)的置换功能，将内存中暂时不用的页(段)调至盘上，腾出足够内存空间后再将要访问的页(段)调入内存，程序继续执行。

5.1.2 虚拟存储器的定义和特征

虚拟存储器的定义

所谓虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。

逻辑容量由内存容量和外存容量之和所决定，
运行速度接近于内存速度，
而每位的成本却又接近于外存。

虚拟存储器的特征

  • 多次性：指一个作业被分成多次调入内存运行。
  • 对换性：指允许在作业的运行过程中进行换进、换出。
  • 虚拟性：指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。

虚拟性是以多次性和对换性为基础的，而多次性和对换性又必须建立在离散分配的基础上。

5.1.3 虚拟存储器的实现方法

  1. 分页请求系统

    是在分页系统的基础上，增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。

    硬件支持：请求分页的页表机制；缺页中断机构；地址变换机构

  2. 请求分段系统

    这是在分段系统的基础上，增加了请求调段及分段置换功能后所形成的段式虚拟存储系统。

    硬件支持：请求分段的段表机制；缺段中断机构；地址变换机构

目前，有不少虚拟存储器是建立在段页式系统基础上的，通过增加请求调页和页面置换功能而形成了段页式虚拟存储器系统，而且把实现虚拟存储器所需支持的硬件集成在处理器芯片上。

5.2 请求分页存储管理方式

5.2.1 请求分页中的硬件支持

1、请求页表机制

在请求分页系统中所需要的主要数据结构是页表。其基本作用：将用户地址空间中的逻辑地址变换为内存空间中的物理地址。

页号 物理块号 状态位P 访问字段A 修改位M 外存地址

各字段说明：

  1. 状态位 P：用于指示该页是否已调入内存，供程序访问时参考。
  2. 访问字段 A：用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，供选择换出页面时参考。
  3. 修改位 M：表示该页在调入内存后是否被修改过。由于内存中的每一页都在外存上保留一份副本，因此，若未被修改，在置换该页时就不需再将该页写回到外存上，以减少系统的开销和启动磁盘的次数；若已被修改，则必须将该页重写到外存上，以保证外存中所保留的始终是最新副本。简言之，M 位供置换页面时参考。
  4. 外存地址：用于指出该页在外存上的地址，通常是物理块号，供调入该页时参考。

2、缺页中断机制

在请求分页系统中，每当所要访问的页面不在内存时，便产生一缺页中断，请求 OS 将所缺之页调入内存。

缺页中断是一种特殊的中断，它与一般的中断相比，有着明显的区别，主要表现在：

  1. 在指令执行期间产生和处理中断信号。
  2. 一条指令在执行期间，可能产生多次缺页中断。

3、地址变换机构

请求分页系统中的地址变换机构，是在分页系统地址变换机构的基础上，再为实现虚拟存储器而增加了某些功能而形成的，如产生和处理缺页中断，以及从内存中换出一页的功能等等。

地址变换过程：

首先去检索快表，试图从中找出所要访问的页。若找到，便修改页表项中的访问位。对于写指令，还须将修改位置成“1”，然后利用页表项中给出的物理块号和页内地址形成物理地址。地址变换过程结束。

如果在快表中未找到该页的页表项时，应到内存中去查找页表，再从找到的页表项中的状态位 P，来了解该页是否已调入内存：

  • 若该页已调入内存，这时应将此页的页表项写入快表，当快表已满时，应先调出按某种算法所确定的页的页表项，然后再写入该页的页表项；
  • 若该页尚未调入内存，这时应产生缺页中断，请求 OS 从外存把该页调入内存。

5.2.2 请求分页中的内存分配

1、最小物理块数的确定

最小物理块数是指能保证进程正常运行所需的最小物理块数。

进程应获得的最少物理块数与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。

2、内存分配策略

在请求分页系统中，可采取两种内存分配策略，即固定和可变分配策略。
在进行置换时，也可采取两种策略，即全局置换和局部置换。

  1. 固定分配局部置换(Fixed Allocation，Local Replacement)

    所谓固定分配，是指为每个进程分配一组固定数目的物理块，在进程运行期间不再改变。

    所谓局部置换，是指如果进程在运行中发现缺页，则只能从分配给该进程的 n 个页面中选出一页换出，然后再调入一页，以保证分配给该进程的内存空间不变。

  2. 可变分配全局置换(Variable Allocation，Global Replacement)

    这可能是最易于实现的一种物理块分配和置换策略。

    所谓可变分配，是指先为每个进程分配一定数目的物理块，在进程运行期间可根据情况做适当的增加或减少。

    所谓全局置换，是指如果进程在运行中发现缺页，则将OS所保留的空闲物理块(一般组织为一个空闲物理块队列)中取出一块分配给该进程，或者以所有进程的全部物理块为标的，选择一块换出，然后将所缺页调入。

  3. 可变分配局部置换(Variable Allocation，Local Replacement)

3、物理块分配算法

采用固定分配策略：

  1. 平均分配算法

    将系统中所有可供分配的物理块平均分配给各个进程。

  2. 按比例分配算法

    根据进程的大小按比例分配物理块。

    如果系统中共有 n 个进程，每个进程的页面数为 \(S_i\)，则系统中各进程页面数的总和为： \(S=\sum_{i=1}^nS_i\)

    又假定系统中可用的物理块总数为 m，则每个进程所能分到的物理块数为 \(b_i\)，将有： \(b_i = \dfrac{S_i}{S} \times m\)（b 应该取整，它必须大于最小物理块数）

  3. 考虑优先权的分配算法

    为重要的、紧迫的作业分配较多的内存空间，使其尽快地完成。

    把内存中可供分配的所有物理块分成两部分：

    • 一部分按比例地分配给各进程；
    • 另一部分则根据各进程的优先权进行分配，为高优先进程适当地增加其相应份额。

5.2.3 页面调入策略

1、何时调入

为了确定系统将进程运行时所缺的页面调入内存的时机，可采取预调页策略或请求调页策略。

  1. 预调页策略

    以预测为基础，将那些预计在不久之后便会被访问的页面预先调入内存。

    目前预调页的成功率仅约 50%。

  2. 请求调页策略

    当进程在运行中需要访问某部分程序和数据时，若发现其所在的页面不在内存，便立即提出请求，由 OS 将其所需页面调入内存。

    这种策略每次仅调入一页，花费较大的系统开销，增加了磁盘 I/O 的启动频率。

2、何处调入

在请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。

由于对换区采用连续分配方式而文件区采用离散分配方式，对换区的磁盘 I/O 速度比文件区的高。

三种情况：

  1. 系统拥有足够的对换空间

    全部从对换区调入所需页面，以提高调页速度。

  2. 系统缺少足够的对换区空间

    凡是不会被修改的文件都直接从文件区调入；可能被修改的部分，在将它们换出时，便须调到对换区，以后需要时，再从对换区调入

  3. UNIX 方式

    凡是未运行过的页面，都应从文件区调入；

3、页面调入过程

  1. 每当程序所要访问的页面未在内存时(存在位为0)，便向 CPU 发出一缺页中断，中断处理程序首先保留 CPU 环境，分析中断原因后转入缺页中断处理程序。

  2. 该程序通过查找页表，得到该页在外存的物理块后：

    1. 如果此时内存能容纳新页，则启动磁盘 I/O 将所缺之页调入内存，然后修改页表。

    2. 如果内存已满，则须先按照某种置换算法从内存中选出一页准备换出：

      • 如果该页未被修改过(修改位为0)，可不必将该页写回磁盘
      • 如果此页已被修改(修改位为1)，则必须将它写回磁盘

    3. 然后再把所缺的页调入内存，并修改页表中的相应表项，置其存在位为“1”，并将此页表项写入快表中。

  3. 在缺页调入内存后，利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。

4、缺页率

假设一个进程的逻辑空间为n页，系统为其分配的内存物理块数为m(m≤n)。如果在进程的运行过程中，访问页面成功(即所访问页面在内存中)的次数为S，访问页面失败(即所访问页面不在内存中，需要从外存调入)的次数为F，则该进程总的页面访问次数为A = S + F，那么该进程在其运行过程中的缺页率即为：\(f = \dfrac{F}{A}\)

影响因素：

  1. 页面大小。页面划分较大，则缺页率较低。
  2. 进程所分配物理块的数目。分配物理块数目越多，缺页率越低。
  3. 页面置换算法。算法的优劣决定了进程执行过程中缺页中断的次数。
  4. 程序固有特性。程序编制的局部化程度越高，相应执行时的缺页率越低。

5.3 页面置换算法

5.3.1 最佳(Optimal)页面置换算法

其所选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。

采用最佳置换算法，通常可保证获得最低的缺页率。该算法是无法实现的，但可以利用该算法去评价其它算法。

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

该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。

算法实现：只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。

这是最早出现的置换算法，算法实现简单，但不能保证经常被访问的页面不被淘汰。

5.3.3 最近最久未使用(Least Recently Used，LRU)置换算法

LRU 置换算法是选择最近最久未使用的页面予以淘汰。

算法实现：赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最久未使用的页面予以淘汰。

LRU 置换算法虽然是一种比较好的算法，但要求系统有较多的支持硬件。

为了了解一个进程在内存中的各个页面各有多少时间未被进程访问，以及如何快速地知道哪一页是最近最久未使用的页面，须有两类硬件之一的支持：寄存器或栈。

  • 寄存器

    配置一个移位寄存器，可表示为\(R = R_{n-1}R_{n-2}R_{n-3} … R_2R_1R_0\)

    当进程访问某物理块时，要将相应寄存器的 \(R_{n－1}\)位置成 1。此时，定时信号将每隔一定时间(例如 100 ms)将寄存器右移一位。如果我们把 n 位寄存器的数看做是一个整数，那么，具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。

    例：
    第 3 个内存页面的 R 值最小，当发生缺页时，首先将它置换出去。

  • 栈

    利用一个特殊的栈来保存当前使用的各个页面的页面号。

    每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号，而栈底则是最近最久未使用页面的页面号。

    例：
    在访问页面 6 时发生了缺页，此时页面 4 是最近最久未被访问的页，将它置换出去。

5.3.4 最少使用(Least Frequently Used，LFU)置换算法

该置换算法选择在最近时期使用最少的页面作为淘汰页。

算法实现：在内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率。每次访问某页时，便将该移位寄存器的最高位置 1，再每隔一定时间(例如 100 ms)右移一次。这样，在最近一段时间使用最少的页面将是∑Ri 最小的页。

LFU 置换算法的页面访问图与 LRU 置换算法的访问图完全相同，或者说，利用这样一 套硬件既可实现 LRU 算法，又可实现 LFU 算法。但LFU 算法并不能真正反映出页面的使用情况。

5.3.5 Clock 置换算法

LRU 算法是较好的一种算法，但由于它要求有较多的硬件支持，故在实际应用中多采用 LRU 的近似算法，如Clock 算法。

1、简单的 Clock 置换算法

实现：只需为每页设置一位访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位被置 1。置换算法在选择一页淘汰时，只需检查页的访问位。如果是 0，就选择该页换出；若为 1，则重新将它置 0，暂不换出，而给该页第二次驻留内存的机会，再按照 FIFO 算法检查下一个页面。当检查到队列中的最后一个页面时，若其访问位仍为 1，则再返回到队首去检查第一个页面。

由于该算法是循环地检查各页面的使用情况，故称为 Clock 算法。
因该算法只有一位访问位，只能用它表示该页是否已经使用过，而置换时是将未使用过的页面换出去，故又把该算法称为最近未用算法 NRU(Not Recently Used)。

2、改进型 Clock 置换算法

在将一个页面换出时，如果该页已被修改过，便须将该页重新写回到磁盘上；但如果该页未被修改过，则不必将它拷回磁盘。
在改进型 Clock 算法中增加一个因素——置换代价，在选择页面换出时，既要是未使用过的页面，又要是未被修改过的页面。把同时满足这两个条件的页面作为首选淘汰的页面。

由访问位 A 和修改位 M 组合的四种类型页面：

  • 1 类(A=0，M=0)：表示该页最近既未被访问，又未被修改，是最佳淘汰页。
  • 2 类(A=0，M=1)：表示该页最近未被访问，但已被修改，并不是很好的淘汰页。
  • 3 类(A=1，M=0)：表示该页最近已被访问，但未被修改，该页有可能再被访问。
  • 4 类(A=1，M=1)：表示该页最近已被访问且被修改，该页可能再被访问。

执行过程：

  1. 从指针所指示的当前位置开始，扫描循环队列，寻找 A=0 且 M=0 的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位 A。
  2. 如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找 A=0且 M=1 的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置 0。
  3. 如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复 0。然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。

该算法与简单 Clock 算法比较，可减少磁盘的 I/O 操作次数，但可能要经过几轮扫描，开销有所增加。

5.3.6 页面缓冲算法(Page Buffering Algorithm，PBA)

影响页面换进换出效率的因素

  1. 页面置换算法：最重要的因素，较低缺页率可减少页面换进换出的开销。
  2. 写回磁盘的频率：建立已修改换出页面的链表，当被换出页面数目达到一定值时再一起写回磁盘，可减少磁盘I/O次数。
  3. 读入内存的频率：减少页面从磁盘读入内存的频率，可减少页面换进的开销。

页面缓冲算法(PBA)

特点：显著降低了页面换进换出的频率，减少了开销；采用较简单置换策略，不需要特殊硬件支持。

VAX/VMS 操作系统使用页面缓冲算法，内存分配策略采用了可变分配和局部置换方式，置换算法采用的是FIFO。

系统为每个进程分配一定数目的物理块，自己保留一部分空闲物理块。内存设置如下链表：

  1. 空闲页面链表：减少了页面换进的开销
  2. 修改页面链表：减少已修改页面换出的次数

5.4 “抖动”与工作集

5.4.1 抖动

产生“抖动”的根本原因：系统中运行的进程太多，分配给每个进程的物理块太少，不能满足进程运行的基本要求，致使进程在运行时频繁出现缺页，必须请求系统将所缺页调入内存。使得系统中排队等待的数目增加，造成进程的大部分时间都在等待而不能做有效工作。

5.4.2 工作集

所谓工作集，是指在某段时间间隔△里，进程实际所要访问页面的集合。

5.4.3 "抖动"的预防方法

都是采用调节多道程序度控制“抖动”发生的。

  1. 采取局部置换策略
  2. 把工作集算法融入到处理机调度中
  3. 利用“L=S”准则调节缺页率
  4. 选择暂停的进程

5.5 请求分段存储管理方式

5.5.1 请求分段中的硬件支持

1、请求分段机制

在请求分段式管理中所需的主要数据结构是段表。

请求分段的段表项：

段名 段长 段内基址 存取方式 访问字段A 修改位M 状态位P 增补位 外存始址

字段说明：

  1. 存取方式：用于标识本分段的存取属性是只执行、只读，还是允许读/写。
  2. 访问字段 A：其含义与请求分页的相应字段相同，用于记录该段被访问的频繁程度。
  3. 修改位 M：用于表示该页在进入内存后是否已被修改过，供置换页面时参考。
  4. 存在位 P：指示本段是否已调入内存，供程序访问时参考。
  5. 增补位：这是请求分段式管理中所特有的字段，用于表示本段在运行过程中是否做过动态增长。
  6. 外存始址：指示本段在外存中的起始地址，即起始盘块号。

2、缺段中断机构

缺段中断机构与缺页中断机构类似，它同样需要在一条指令的执行期间，产生和处理中断，以及在一条指令执行期间，可能产生多次缺段中断。

由于分段是信息的逻辑单位，因而不可能出现一条指令被分割在两个分段中和一组信息被分割在两个分段中的情况。

3、地址变换机构

请求分段系统中的地址变换机构是在分段系统地址变换机构的基础上形成的。

因为被访问的段并非全在内存，所以在地址变换时，若发现所要访问的段不在内存，必须先将所缺的段调入内存，并修改段表，然后才能再利用段表进行地址变换。

5.5.2 分段的共享与保护

1、共享段表

为了实现分段共享，可在系统中配置一张共享段表，所有各共享段都在共享段表中占有一表项。表项中记录了共享段的段号、段长、内存始址、存在位等信息，并记录了共享此分段的每个进程的情况。

  1. 共享进程计数 count：
    非共享段仅为一个进程所需要。当进程不再需要该段时，可立即释放该段，并由系统回收该段所占用的空间。
    而共享段是为多个进程所需要的，当某进程不再需要而释放它时，系统并不回收该段所占内存区，仅当所有共享该段的进程全都不再需要它时，才由系统回收该段所占内存区。
    为了记录有多少个进程需要共享该分段，特设置了一个整型变量 count。
  2. 存取控制字段：
    对于一个共享段，应给不同的进程以不同的存取权限。
  3. 段号：
    对于一个共享段，不同的进程可以各用不同的段号去共享该段。

2、共享段的分配和回收

  1. 共享段的分配

    对第一个请求使用该共享段的进程，由系统为该共享段分配一物理区，再把共享段调入该区，同时将该区的始址填入请求进程的段表的相应项中，在共享段表中增加一表项，填写有关数据，把 count 置为1。

    当又有其它进程需要调用该共享段时，无须再为该段分配内存，而只需在调用进程的段表中增加一表项，填写该共享段的物理地址；在共享段的段表中，填上调用进程的进程名、该共享段在本进程中的段号、存取控制等，再执行 count = count + 1 操作。

  2. 共享段的回收

    当共享此段的某进程不再需要该段时，应将该段释放，包括撤消在该进程段表中共享段所对应的表项，以及执行 count = count - 1 操作。

    若结果为 0，则须由系统回收该共享段的物理内存，以及取消在共享段表中该段所对应的表项；否则(减 1 结果不为 0)，只是取消调用者进程在共享段表中的有关记录。

3、分段保护

在分段系统中，由于每个分段在逻辑上是独立的，因而比较容易实现信息保护。

  1. 越界检查

    利用地址变换机构完成。

  2. 存取控制检查

    以段为基本单位进行。

    通常访问方式：只读、只执行、读/写。

  3. 环保护机构

    是一种功能较完善的保护机制。
    规定：低编号的环具有高优先权。OS 核心处于 0 环内；某些重要的实用程序和操作系统服务占居中间环；而一般的应用程序则被安排在外环上。

    在环系统中，程序的访问和调用应遵循以下规则：

    1. 一个程序可以访问驻留在相同环或较低特权环中的数据。
    2. 一个程序可以调用驻留在相同环或较高特权环中的服务。

标签：操作系统,05,置换,访问,算法,内存,虚拟存储器,进程,页面
From： https://www.cnblogs.com/0dot7/p/17105948.html

相关文章

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99