DJ4-7 请求分页存储管理方式

这篇具有很好参考价值的文章主要介绍了DJ4-7 请求分页存储管理方式。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

4.7.1  请求分页中的硬件支持

1、页表机制

2、缺页中断机构

4.7.2  内存分配策略和分配算法

1、最小物理块数的确定

2、物理块的分配策略

3、物理块的分配算法

4.7.3  调页策略

1、系统应当在何时把一个页面装入内存?

2、从何处调入页面?

3、页面调入过程?

4.7.4  页面置换算法

1、最佳置换算法(OPT)

2、先进先出置换算法(FIFO)

3、最近最久未使用置换算法(LRU)

4、最少使用置换算法(LFU)

5、简单的 Clock 置换算法(NRU)最近未用算法

6、改进型 Clock 置换算法


请求分页系统:是指建立在基本分页基础上的,为了能支持虚拟存储器功能,而增加了请求调页功能和页面置换功能。

工作原理:作业运行时,只将当前的一部分装入内存,其余的放在辅存,一旦发现访问的页不在主存中,则发出缺页中断,由 OS 将其从辅存调入主存,如果内存无空块,则根据某种算法选择一个页淘汰以便装入新的页面。

为了实现请求调页、页面置换两大功能,系统必须提供如下的硬件支持:

  1. 请求分页的页表机制
  2. 缺页中断机构
  3. 地址变换机构

4.7.1  请求分页中的硬件支持

1、页表机制

虚拟存储系统中的所有页表,其页描述子需要增加四个信息标识位。

DJ4-7 请求分页存储管理方式

(1) 状态位 D

用于说明该页是否已调入内存,供程序访问时参考。

  • D=0,该页不在内存
  • D=1,该页在内存

(2) 访问位 A

用于记录本页在一段时间内被访问的次数,或最近已有多长时间未被访问,供置换算法选择换出页面时参考。

  • A=0,该页未被访问
  • A=1,该页被访问,大概率后面还会用

(3) 修改位 M

用于表示该页在调入内存后是否被修改过,也是提供给置换算法在换出页面时是否将该页面写回外存作参考。

  • M=0,该页在内存中未被修改,则不用从内存写回外存
  • M=1,该页在内存中已经被修改

(4) 外存地址

用于指出该页在外存上的地址,供调入该页时使用。

2、缺页中断机构

状态位记录了访问页面是否在内存。在地址映射过程中,在页表中发现所要访问的页不在内存,则产生缺页中断,也称为缺页故障。OS 接到此中断信号后,就调出缺页中断处理程序,根据页表中给出的外存地址,将该页调入内存,使作业继续运行下去。

缺页中断是一种特殊的中断,与一般中断相比,主要表现为:

(1) 在指令执行期间产生和处理中断信号。通常,CPU 只能在指令之间接受中断;然而,一个缺页中断要求在指令执行中间得到服务,即发现所要访问的指令或数据不在内存时产生缺页中断并处理。

(2) 再则,一条指令可能引起多次不同的页面故障。下图是一个十分极端的例子,这条指令的执行需要访问六个不同的页面,对它们的访问都可能引起缺页中断。

DJ4-7 请求分页存储管理方式

由于缺页中断的独特性,系统中需要提供硬件寄存器或其它机构,用于保存发生缺页中断时部分完成的指令的状态。此外,还需一条特殊的返回指令,确保恢复原指令的执行。

缺页中断处理过程

  1. 操作系统接收到进程产生的缺页中断信号,启动中断处理例程,保留处理机现场;
  2. 操作系统通知处理机从外存读取指定的页面;
  3. 处理机激活 I/O 设备;
  4. 检查内存有无足够的空闲空间装入该页面?若有,转(6);否则,执行(5);
  5. 利用页面置换算法,选择内存中的某个页面,换出内存;
  6. 将指定页面从外存装入内存;
  7. 更新该进程的页表,即将存在位 D 置为 1;
  8. 更新快表,即写入该页的页表项;
  9. 计算物理地址。

4.7.2  内存分配策略和分配算法

在为进程分配物理块时,又将涉及到这样三个问题:

  • 为保证进程能正常运行所需的最少物理块数的确定;
  • 为每个进程分配的物理块,其数目是固定的还是可变的;
  • 对各进程所分配的物理块数,是采取平均分配算法还是根据进程的大小按比例予以分配等。

1、最小物理块数的确定

显然,给每个进程分配的物理块数越少,则进程执行中的缺页率越高,进程的执行速度也将减慢。为使进程能有效地工作,应为它分配一定数目的物理块。

最小物理块数:是指能保证进程正常运行所需的最少物理块数。若系统为某进程所分配的物理块数少于此值时,进程将无法运行。

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

  • 对于某些简单的机器,若是单地址指令且采用直接寻址方式,则所需的最少物理块数为 2 。
  • 如果该机器允许间接寻址时,则至少要求有物理块数为 3 。

对于前面所介绍的在缺页中断机构中要发生6次中断的情况,至少要为每个进程分配6个物理块,以装入6个页面。

2、物理块的分配策略

DJ4-7 请求分页存储管理方式

  1. 固定分配局部置换(Fixed Allocation,Local Replacement)
  2. 可变分配全局置换(Variable Allocation,Global Replacement)
  3. 可变分配局部置换(Variable Allocation,Local Replacement)

因为分配固定了,所以不能进行全局置换。

(1) 固定分配局部置换

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

困难在于难以确定应为每个进程分配多少个物理块。若太少,则会频繁地出现缺页中断,从而降低系统的吞吐量;若太多,则又必然使内存中驻留的进程数目减少,进而可能造成 CPU 空闲或其它资源空闲的情况,而且在实现进程对换时,会花费更多的时间。

(2) 可变分配全局置换(常用方式)

为系统中的每个进程分配一定数目的物理块,而系统自身也保持一个空闲物理块队列。当某进程发现缺页时,由系统从空闲物理块队列中,取出一个物理块分配给该进程,并将所缺页装入其中。

这样,凡是产生缺页中断的进程,都将获得新的物理块;仅当空闲物理块队列中的物理块用完时,OS 才会从内存中选择一页调出,该页可能是系统中任一进程的页。这样,自然又会使那个进程的物理块减少,进而使其缺页率增加。

(3) 可变分配局部置换

为每个进程分配一定数目的物理块,但当某进程发现缺页时,只允许从该进程在内存的页面中选出一页换出,这样就不会影响其它进程的运行。

在进程运行过程中统计进程的缺页率,如果缺页率高,则为其增加一定的内存页,否则适当减少其内存的页面数。

当需要置换时只从本进程的内存页中选择,但此方式实现复杂,对进程的缺页情况的统计需要额外的开销。

3、物理块的分配算法

在采用固定分配局部置换策略时,如何将系统中可供分配的所有物理块分配给各个进程,可采取下述几种方法。

(1) 平均分配算法

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

例:当系统中有 100 个物理块,有 5 个进程在运行时,每个进程可分得 20 个物理块。若一个进程有 200 页,却只分配给它 20 个块,那么它必然会有很高的缺页率;而另一个进程只有 10 页,则还有 10 个物理块闲置未用。

这种方式貌似公平,但实际上并不公平。因为,它并未考虑到各个进程的大小。        

(2) 按比例分配算发

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

例:系统中共有 n 个进程,每个进程的页面数为 Si,则系统中各进程页面数的总和为:

又假定系统中可用的物理块总数为 m,则每个进程所能分到的物理块数为 bi,将有:

 

b 应该取整,它必须大于最小物理块数。

最小物理块数是算出来的。

(3) 考虑优先权的分配算法

通常采取的方法是把内存中可供分配的所有物理块分成两部分:

  • 一部分按比例地分配给各进程;
  • 另一部分则根据各进程的优先权,适当地增加其相应份额后,分配给各进程。

在有的系统中,如重要的实时控制系统,则可能是完全按优先权来为各进程分配物理块。

4.7.3  调页策略

1、系统应当在何时把一个页面装入内存?

(1) 预调页方式

预调页:将那些预计在不久之后便会被访问的页面预先调入内存。

处理过程:

  1. 进程创建时,预先为进程装入多个页面。
  2. 缺页中断时,系统为进程装入指定的页面以及与之相临的多个页面。

若局部性很差,那么预先装入的很多页面不会被很快引用,并会占用大量的内存空间,反而降低系统的效率。预调页的成功率仅约 50%。

(2) 请求调页

请求调页:仅在进程执行过程中,通过检查页表发现相应页面不在内存时,才装入该页面。

  1. 进程开始执行时,由于预先未装入页面,因此需要频繁申请装入页面。
  2. 执行一段时间后,进程的缺页率将下降。

由于一次只会装入请求那一个页面,因此磁盘 I/O 的启动频率较高,系统的开销较大。

2、从何处调入页面?

DJ4-7 请求分页存储管理方式

在请求分页系统中外存分为两部分:

  • 用于存放文件的文件区
  • 用于存放对换页面的对换区

由于对换区采用的是连续分配方式,而文件区采用的是离散分配方式,因此对换区的磁盘 I/O 速度比文件区的高。初始时,文件都存放在文件区。

由于请求分页系统中的外存分为两部分,因此每当发生缺页请求时,系统应从何处将缺页调入内存,可分成如下三种情况进行:

(1) 系统拥有足够的对换区空间

这时可以全部从对换区调入所需页面,以提高调页速度。为此,在进程运行前,便须将与该进程有关的文件从文件区拷贝到对换区。

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

这时凡是不会被修改的文件,都直接从文件区调入;而当换出这些页面时,由于它们未被修改而不必再将它们换出,以后再调入时,仍从文件区直接调入。但对于那些可能被修改的部分,在将它们换出时,便须调到对换区,以后需要时,再从对换区调入。

(3) UNIX 方式

由于与进程有关的文件都放在文件区,应从文件区调入。故凡是未运行过的页面,都应从文件区调入。而对于曾经运行过但又被换出的页面,由于是被放在对换区,因此在下次调入时,应从对换区调入。

3、页面调入过程?

  1. 每当程序所要访问的页面未在内存时,便向 CPU 发出一缺页中断。
  2. 中断处理程序首先保留 CPU 环境,分析中断原因后,转入缺页中断处理程序。
  3. 如果内存已满,则须先按照某种置换算法从内存中选出一页准备换出;如果此页已被修改,则必须将它写回磁盘。
  4. 然后再把所缺的页调入内存,并修改页表中的相应表项,置其存在位为 “1”,并将此页表项写入快表中。
  5. 形成所要访问数据的物理地址,再去访问内存数据。

整个页面的调入过程对用户是透明的。

4.7.4  页面置换算法

页面置换算法的选择,是虚拟存储器管理系统的核心问题。它的实质是,为系统提供一种方法,当从主存中需要换出页面时,应避免选择那些不久再次要求访问的页面。

置换算法的选择在一定程度上取决于可用的硬件设施。      

  1. 最佳置换算法
  2. 先进先出(FIFO)页面置换算法
  3. 最近最久未使用(LRU)置换算法
  4. Clock 置换算法(NRU)
  5. 改进型 Clock 置换算法

1、最佳置换算法(OPT)

最佳置换算法:从主存中移出永远不再需要的页面;如无这样的页面存在,则应选择最长时间不需要访问的页面。

最佳置换策略本身不是一种实际的方法,因为页面访问的未来顺序是不知道的,但是,可将其它的实用方法与之比较来评价这些方法的优劣。所以,这种最佳策略具有理论上的意义。

例:设页面请求次序 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1,存储块/驻留集为 3,假定最初存储块为空,采用 OPT 算法。

DJ4-7 请求分页存储管理方式

问:发生了几次缺页中断?缺页率多少?

  • 发生了 9 次缺页中断
  • 发生了 6 次页面置换
  • 缺页率 = 缺页次数/访问次数 = 9/20 = 0.45

2、先进先出置换算法(FIFO)

先进先出置换算法:总是选择作业中驻留时间最长的页淘汰,即先进入主存的页面先退出主存。

例:设页面请求次序 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1,存储块/驻留集为 3,假定最初存储块为空,采用 FIFO 算法。

DJ4-7 请求分页存储管理方式

问:发生了几次缺页中断?缺页率多少?

  • 发生了 15 次缺页中断
  • 发生了 12 次页面置换
  • 缺页率 = 缺页次数/访问次数 = 15/20 = 0.75

3、最近最久未使用置换算法(LRU)

(1) LRU(least Recently Used)算法描述

LRU 算法:认为过去一段时间里不曾被访问的页面,在最近的将来可能也不会再被访问。即当需要置换一页面时,选择在最近一段时间内最久不用的页面予以淘汰。

实现:通过周期性地对 页面访问位 进行检查,并利用它来记录一个页面自上次访问以来所经历的时间 t,并选择 t 为最大的页予以淘汰。

例:设页面请求次序 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1,存储块/驻留集为 3,假定最初存储块为空,采用 LRU 算法。

DJ4-7 请求分页存储管理方式

问:发生了几次缺页中断?缺页率多少?

  • 发生了 12 次缺页中断
  • 发生了 9 次页面置换
  • 缺页率 = 缺页次数/访问次数 = 12/20 = 0.60

(2) LRU 算法的硬件支持

LRU 算法需要一个移位寄存器或者一个栈。

DJ4-7 请求分页存储管理方式

例如:某进程在内存中具有 8 个页面,每 100ms 将寄存器右移一位。

DJ4-7 请求分页存储管理方式

6 号页面从左往右数的 0 最多,因此是最久未访问的页面。

DJ4-7 请求分页存储管理方式

4、最少使用置换算法(LFU)

最少使用置换算法:选择到当前时间为止被访问次数最少的页面被置换。

(1) 基本方法:记录每个页面的访问次数,最少访问的页面首先考虑淘汰。

(2) 实际采取方法:为页面设置移位寄存器。

  • R1=10000000,R2=01110100
  • LRU 淘汰 R2,LFU 淘汰 R1

5、简单的 Clock 置换算法(NRU)最近未用算法

NRU, not recently used

DJ4-7 请求分页存储管理方式

  • 只需为每页设置一位访问位
  • 将内存中的所有页面链接成一个循环队列
  • 当某页被访问时,其访问位被置 1

NRU 置换算法:

  1. 检查页的访问位
  2. 若为 0,则选择该页换出
  3. 若为 1,则将其访问位置 0,暂不换出
  4. 按 FIFO 算法检查下一页

当检查到队列中的最后一个页面,若其访问位仍为 1,则再返回到队首去检查第一个页面。

例:设页面请求次序 2,3,2,1,5,2,4,5,3,2,5,2,存储块/驻留集为 3,假定最初存储块为空,采用 NRU 算法。

DJ4-7 请求分页存储管理方式

问:发生了几次缺页中断?缺页率多少?

  • 发生了 8 次缺页中断
  • 发生了 5 次页面置换
  • 缺页率 = 缺页次数/访问次数 = 8/12 = 0.67

6、改进型 Clock 置换算法

当系统把一个页面换出内存时,

  • 如果该页面在驻留期间没有被修改过,则不必把它写回辅存;
  • 如果该页面在驻留期间被修改过,则必须把它写回辅存。

这表明,换出未修改过的页面比换出被修改过的页面开销小。显然,我们可以依据上述结论改进 Clock 算法。

(1) 改进后的 Clock 算法将在置换范围内首选:

  • 在最近没有被使用过的
  • 在驻留期间没有被修改过的

页面作为被置换页面。

(2) 访问位 A 和修改位 M 可以组合成以下四种类型:

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

(3) 执行过程可分成以下三步:

Step1:从指针所指示的当前位置开始,扫描循环队列,寻找 1 类页面:

  • 将所遇到的第一个该类页面作为淘汰页
  • 在第一次扫描期间不改变访问位 A

Step2:若第一次未找到最佳淘汰页,则开始第二次扫描,寻找 2 类页面:

  • 将所遇到的第一个该类页面作为淘汰页
  • 在第二次扫描期间将所有扫描过的页面的访问位 A 都置 0

Step3:若第二次也未找到淘汰页,则将指针返回到开始的位置,并将所有的访问位复 0 。然后重复第一步,如果仍失败,必要时再重复第二步,此时就一定能找到被淘汰的页。

Q:为什么还要 “将所有的访问位复 0 ”?

A:指针回去的时候会访问各个页面,默认把访问位置 1,因此需要复 0?文章来源地址https://www.toymoban.com/news/detail-467053.html

到了这里,关于DJ4-7 请求分页存储管理方式的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包