操作系统 第五章虚拟存储器

5.1 虚拟存储器概述

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

  1. 常规存储管理方式的特征

    第四章介绍的各种存储器管理方式统称为传统存储器管理方式具有两个特征:

    • 一次性:作业必须一次全部装入内存才能运行。
    • 驻留性:作业被装入内存后,整个作业一直驻留在内存中,直至结束。
  2. 局部性原理

    一较短时间内,程序的执行局限于某个部分。相应地,它所访问的存储空间也局限于某个区域。表现为:

    • 时间局限性:程序中大量的虚循环操作。指令被再次执行、存储单元被再次访问。
    • 空间局限性:程序在一段时间内所访问的地址,可能集中在一定的范围内,典型原因式顺序执行。
  3. 虚拟存储器的基本工作情况

    仅将当前运行的少数页面或段先装入内存便可运行,其余留在盘上。运行时,若需要访问的页(段)已在内存,便继续执行;若缺页(段),则发出缺页(段)中断请求,OS 利用请求调页(段)入内存,继续执行。若内存已满,利用页(段)置换功能,腾出空间,继续执行。

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

  1. 虚拟存储器的定义

    是指具有请求调入功能和置换功能,从逻辑上对内存容量加以扩充的一种存储器系统。逻辑容量由内存容量和外村容量之和决定,其运行速度接近于内存速度。是一种行嗯非常优越的存储器管理技术。

  2. 虚拟存储器的特征

    • 多次性:一个作业被分成多次调入内存运行。最重要的特征,逻辑上扩大内存。
    • 对换性:一个作业中的数据和程序无须一直常驻,内存外存换入换出。
    • 虚拟性:指逻辑上能扩充内存容量,可以在小内存中运行大的作业,或提高多道程序度。改善内存利用率,提高程序执行的并发程度,从而增加系统的吞吐量。

    虚拟性以多次性和对换性为基础。多次性和对换性建立在离散分配的基础上。

5.1.3 虚拟存储器的实现方法

  1. 分页请求系统

    在分页系统的基础上,增加了调页功能和页面置换功能。系统必须提供必要的硬件支持和实现请求分页的软件。

    • 硬件支持:请求分页的页表机制、缺页中断机制、地址变换机构。
    • 实现请求分页的软件
  2. 请求分段系统

    在分段系统的基础上,增加了调段功能和分段置换功能。系统必须提供必要的硬件支持和软件支持。

    • 硬件支持:请求分段的段表机制、缺段中断机制、地址变换机构。
    • 实现请求分段的软件

5.2 请求分页存储管理方式

5.2.1 请求分页中的硬件支持

  1. 请求页表机制

    请求分页系统中每个页表包含:

  2. 缺页中断机构

    当 OS 要访问的页面不存在时,便产生缺页中断。与一般中断的主要区别在于:

    • 缺页中断在指令执行期间产生和处理中断信号,而一般中断在一条指令执行完后检查和处理中断信号。
    • 缺页中断返回到该指令的开始重新执行该指令,而一般中断返回到该指令的下一条指令执行。
    • 一条指令在执行期间,可能产生多次缺页中断。
  3. 地址变换机构

5.2.2 请求分页中的内存分配

  1. 最小物理块数的确定

    最小物理块数能保证进程能正常运行所需的最少物理块数。若系统为某进程所分配的物理块数少于此值时,进程将无法运行,这取决于指令的格式、功能和寻址方式。

  2. 内存分配策略

    两种内存分配策略:固定和而可变分配策略;两种置换策略:全局置换和局部置换。

    固定分配:为每个进程分配一固定数目的物理块,在整个运行期间都不再改变。

    可变分配:为每个进程分配一固定数目的物理块,在运行期间,可适当增加或减少。

    局部置换:如果进程在运行中发现缺页,则只能从固定物理块中选出一页换出,然后再调入另一页,保证分配给该进程的内存空间不变。

    全局置换:当某进程发现缺页时,由系统从空闲物理块队列中,取出一物理块分配给该进程,并将欲调入的缺页装入其中。

    • 固定分配局部置换
    • 可变分配全局置换:最易于实现,但缺页率增加。
    • 可变分配局部置换
  3. 物理块分配算法

    平均分配算法、按比例分配算法、考虑优先权的分配算法

5.2.3 页面调入策略

  1. 何时调入页面
    • 预调度策略:预计不久之后会访问的页面预先调入内存。
    • 请求调页策略:是指当进程在运行中发生缺页时,就立即提出请求,由系统将缺页调入内存。需频繁启动磁盘 I/O。
  2. 从何处调入页面
    • 系统拥有足够的对换区空间,全部从对换区调入所需页面。
    • 系统缺少足够的对换区空间,不会被修改的页面,从文件区调入,可能被修改的页面,从对换区调入、换出。
    • 在 UNIX 系统中,对于从未运行过的页面,都应从硬盘文件区调入;对于曾经运行过而又被换出的页面,可以从对换区调入;
  3. 页面调入过程
  4. 缺页率

5.3 页面置换算法

不适当的算法可能导致进程发生“抖动”,即频繁地更换页面。

####5.3.1 最佳置换算法和先进先出置换算法

  1. 最佳(Optimal)置换算法

    选择那些永不使用的,或者是在最长时间内不再被访问的页面置换出去。但是要确定哪一个页面是未来最长时间内不再被访问的,目前来说是很难估计的,所以该算法通常用来评价其它算法。

    设作业执行中访问页面的总次数为 A,其中有 F 次访问的页面尚未装入主存,故产生了 F 次缺页中断。现定义缺页中断率为:\(f=F/A\)

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

    该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。它是一种最直观,性能最差的算法。

5.3.2 最近最久未使用和最少使用置换算法

  1. LRU(Last Recently Used)算法的描述

    选择内存中最近最久未使用的页面被置换。这是局部性原理的合理近似,性能接近最佳算法。但由于需要记录页面使用时间的先后关系,硬件开销太大。

  2. LRU 置换算法的硬件支持

    • 寄存器:每个内存页面设置一个移位寄存器:被访问时左边最高位置 1,定期右移并且最高位补 0,于是寄存器数值最小的是最久未使用页面。
    • 栈:把被访问的页面移到栈顶,于是栈底的是最久未使用页面。
  3. 最少使用(Least Frequently Used, LFU)置换算法

    选择到当前时间为止被访问次数最少的页面被置换。每页设置访问计数器,每当页面被访问时,该页面的访问计数器加1;发生缺页中断时,淘汰计数值最小的页面,并将所有计数清零。

5.3.3 Clock 置换算法(*)

  1. 简单的 Clock 置换算法

    只有一位访问位,只表示该页是否已经使用过。内存中所有页面通过指针链接成一个循环队列。该算法是将未使用过的页面换出去,又称为最近未用算法(Not Recently Used, NRU)。

  2. 改进型 Clock 置换算法

5.3.4 页面缓冲算法(Page Buffering Algorithm, PBA)

对 FIFO 算法的发展,通过被置换页面的缓冲,有机会找回刚被置换的页面。采用可变分配和局部置换的方式。

用 FIFO 算法选择被置换页,把被置换的页面放入两个链表之一。

  • 如果页面未被修改,就将其归入到空闲页面链表的末尾
  • 否则将其归入到已修改页面链表。

5.3.5 访问内存的有效时间

在请求分页系统中,假设存储器的访问时间 ma 为 100ns(一般为 10ns~几百 ns),缺页率为 p,缺页中断时间为 25ms,则有效访问时间就可以表示为:有效访问时间 =(1一p)×ma十p×缺页中断时间 =(1一p)×0.1十p×25000 = 0.1十24999.9 p。

提高磁盘I/O的速度,对改善请求分页系统的性能至关重要。为此,应选用高速磁盘和高速磁盘接口。

5.4 “抖动”与工作集

5.4.1 多道程序度与“抖动”

产生“抖动”的根本原因是,同时在系统中运行的进程太多,由此分配给每一个进程的物理块太少,不能满足进程正常运行的基本要求,使得进程运行时频繁缺页。每个进程大部分时间都用于页面的换进/换出,导致发生处理机的利用率急剧下降并趋于 0。

5.4.2 工作集

工作集:在某段时间间隔(Δ)里,进程实际要访问的页面的集合。把某进程在时间 t 的工作集记为 \(w(t, Δ)\),把变量 Δ 称为工作集“窗口尺寸”(Windows Size)。正确选择工作集窗口(Δ)的大 小,对存储器的有效利用和系统吞吐量的提高,都将产生重要的影响。

5.4.3 “抖动”的预防方法

  1. 采取局部置换策略

    若采用可变分配方法,则可以采取局部置换方法,当进程缺页只能分配给自己的内存空间内进行置换,不允许从其他进程获得新的物理块。

  2. 把工作集算法融入到处理机调度中

    在调度程序之前,先检查每个进程在内存的驻留页面是否足够多。如果足够,便从外存调入新的作业,反之为缺页率高的作业增加新的物理块,不再调入新的作业。

  3. 利用“L=S”准则调节缺页率

    L 是缺页之间的平均时间,S 是平均缺页服务时间,即置换一个页面所需的时间。若 L > S,很少发生缺页,反之频繁发生缺页。当 L 与 S 接近时,磁盘和处理机都可达到它们的最大利用率。

  4. 选择暂停的进程

    采取与调度程序一致的策略,暂停某些进程,比如优先级较低的进程。

5.5 请求分段存储管理方式

5.5.1 请求分段中的硬件支持

  1. 请求段表机制

  2. 缺段中断机制

  3. 地址变换机构

5.5.2 分段的共享与保护

  1. 共享段表

    在系统中,用共享段表来记录了每一个共享段的段号和段长、内存始址、存在位等信息,并记录共享此分段的每个进程的情况。共享段表如下图所示:

    • 共享进程计数器 COUNT:记录有多少个进程需要共享该分段。
    • 存取控制字段:说明不同的进程对该分段不同的存取权限。
    • 段号:对于同一个共享段,不同的进程可以使用不同的段号去共享该段。
  2. 共享段的分配与回收

    • 共享段的分配:

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

      其它进程请求共享段,已调入内存,无需分配,进程段表中加一表项,填入共享段的物理地址。在共享段的段表中,填入调用进程名、存取控制等,count = count + 1。

    • 共享段的回收:

      取消进程段表中该共享段所对应的表项,count = count - 1;若 count = 0,则回收物理内存,取消共享段表中该段的表项。

  3. 分段保护

    • 越界检查
    • 存取控制检查
    • 环保护机构

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×