精华内容
下载资源
问答
  • 虚拟存储器管理

    2020-07-11 20:37:40
    虚拟存储器管理 一、实验目的 加深对虚拟存储器中的页面置换算法的理解,特别是要掌握先入先出页面置换算法和最近最久未使用置换算法的用法。 二、实验原理 设计一个请求页式存储管理方案,编写模拟程序实现具体过程...

    虚拟存储器管理

    一、实验目的

    加深对虚拟存储器中的页面置换算法的理解,特别是要掌握先入先出页面置换算法和最近最久未使用置换算法的用法。

    二、实验原理

    设计一个请求页式存储管理方案,编写模拟程序实现具体过程,并计算缺页率(所有内存开始都是空的,凡第一次用到的页面都产生一次缺页中断)。
    要求实现下列页面置换算法:
    (1)先进先出算法(FIFO) (2)最近最久未使用算法(LRU)
    基本知识:
    虚拟存储器是只具有请求调入功能和置换功能,能从逻辑上对内存容量进行扩充的一种存储器系统。分页请求系统是指在分页系统的基础上,增加了请求调页功能、页面置换功能所形成的页面形式虚拟存储系统。
    先进先出算法(FIFO)是指淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。
    最近最久未使用算法(LRU)是指淘汰最近最久未被使用的页面。
    选择置换算法,先输入所有页面号,为系统分配物理块,依次按照FIFO或LRU算法进行置换。
    例:假定系统为某进程分配了三个物理块, 并考虑有以下的页面号引用串:7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1进程运行时, 先将7,0,1三个页面装入内存(凡第一次用到的页面都产生一次缺页中断)。 以后,当进程要访问页面2时将会产生缺页中断。此时OS根据置换算法,将选择页面予以淘汰。

    采用FIFO算法进行页面置换过程:
    在这里插入图片描述
    产生15次缺页中断,缺页率为15/20。

    采用LRU算法进行页面置换过程:
    在这里插入图片描述
    产生12次缺页中断, 缺页率为12/20。

    三、实验操作方法和步骤

    本实验要求通过编写和调试一个程序,可以通过逻辑地址计算出物理地址。具体步骤如下:
    (1)编写代码,实现先进先出算法;
    (2)以数组的形式给出一个一号序列,显示出基于先进先出算法的页面置换过程;
    (3)编写代码,实现最近最久未使用算法;
    (4)以数组的形式给出一个一号序列,显示出基于最近最久未使用算法的页面置换过程。

    四、实验结果与分析
    1、对重要部分代码进行截图,并进行简要说明
    1)FIFO算法是最先出现的置换算法。该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单,只需把一个进程已经调入内存的页面按先后次序连接成一个队列,并设置一个指针,称为替换指针,使它总是指向最老的页面,但该算法与进程实际运行的规律不相适应,因为在该进程中,有些页面经常被访问,比如含有全局变量、常用函数、例程的页面,FIFO算法并不能保证页面不被淘汰。
    在这里插入图片描述

    2)FFO置换算法的性能之所以较差,是因为它所依据的条件是各个页面调入内存的时间,而页面调入的先后并不能反映页面的使用情况。最近最久未使用(LRU的页面置换算法是根据页面调入内存后的使用情况做出决策的。由于无法预测各页面将来的使用情况,只能利用“最近的过去”作为“最近的将来”的近似,因此,LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间t。当需淘汰一个页面时,选择现有页面中其t值最大的,即最近最久未使用的页面予以淘汰。

    在这里插入图片描述
    在这里插入图片描述

    2、对运行结果进行截图,并进行简要说明
    1)如下列结果:当进程第一次访问页面2时,将把第二页患处,因为它是最先被调入内存的;在第一次访问也买呢3时,有将把第0页换出,因为它在现有的2、0、1三个页面中最老的页。利用FIFO算法时,进行了12次页面置换,比最佳置换算法正好多一倍。
    在这里插入图片描述

    2)当进程第一次对页面2进行访问时,由于页面7是最近最久未被访问的,故将它置换出去。当进程第一次对页面3进行访问时,第1页成为最近最久未使用的页,将它换出。由图可以看出,前5个时间的图像与最佳置换算法时的相同,但这并非是必然的结果。因为最佳置换算法是从“向后看”的观点出发的,即它是依据以后各页的使用情况进行判断;而LRU算法则是“向前看”的,即根据页以前的使用情况来判断,而页面过去和未来的走向之间并无必然的联系。

    在这里插入图片描述

    展开全文
  • Windows虚拟存储器管理

    2012-11-29 09:42:33
    Windows虚拟存储器管理,wendangneichunxu
  • 模拟虚拟存储器管理

    2013-07-08 12:42:23
    一个简单的模拟虚拟存储器管理工具,可以用来检查fifo opt 和lru算法
  • 包括 模拟虚拟存储器管理 的各种实现算法,可以学下。
  • 文章目录第五章:虚拟存储器管理5.1、虚拟存储器概述5.1.1、常规存储管理方式的特征和局部性原理5.1.2、虚拟存储器的定义和特征5.1.3、虚拟存储器的实现方法5.2、请求分页管理方式5.2.1、请求分页的硬件支持5.2.2、...

    第五章:虚拟存储器管理

    5.1、虚拟存储器概述

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

    常规存储管理方式的特征

    存在的问题 特点 缺点
    一次性 程序必须全部装入内存才能运行 ①大作业无法在小内存中运行;
    ②限制了在内存中并发进程的数量
    驻留性 作业一直驻留内存直到完成 一些不用或者暂时不用的程序(数据)占据了大量的内存空间,浪费空间

    局部性原理

    程序运行的局部性:程序在一个有限的时间内,访问过的代码和数据集中在有限的地址范围内。

    局限性又表现在下述的两个方面:

    1)、时间局部性:即刚被访问过的单元在很短的时间内还将被访问。

    2)、空间局部性:即被访问过的单元的邻近单元也将被访问。

    产生时间局限性的典型原因是:在程序中存在大量的循环结构

    产生空间局部性的典型原因是:程序的顺序执行

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

    虚拟存储器的定义

    虚拟存储器:是指仅把作业的一部分装入内存便可运行作业的存储器系统,具有请求调入功能置换功能,能从逻辑上对内存容量进行扩充的一种存储器系统。

    虚拟存储器的特征

    1)、多次性

    ​ 多次性是相对于传统存储器管理方式的一次性而言的,是指一个作业中的程序和数据无需在作业运行时一次性地全部装入内存,而是被分成多次调入内存运行。

    2)、对换性

    ​ 在进程运行期间,允许将那些暂不使用的代码和数据从内存调至外存的对换区(换出),待以后需要时再将它们从外存调至内存(换进)。

    ​ 甚至还允许将暂时不运行的进程调至外存,待它们重又具备运行条件时再调入内存。

    3)、虚拟性

    ​ 虚拟性是指能够从逻辑上扩充内存容量,使用户所看到的内存容量远大于实际内存容量。

    虚拟性是以多次性和对换性为基础的,而多次性和对换性又是以离散分配为基础的。

    5.1.3、虚拟存储器的实现方法

    虚拟存储的实现思路

    基于局部性原理,应用程序在运行之前没有必要将之全部装入内存,而仅须将那些当前要运行的少数页面(段)先装入内存便可运行,其余部分暂留在盘上。

    程序在运行时,如果它所要访问的页(段)已调入内存,便可继续执行下去;

    但如果程序所要访问的页(段)尚未调入内存(称为缺页或缺段),便发出缺页(段)中断请求,此时OS将利用请求调页(段)功能将它们调入内存,以使进程能继续执行下去。

    如果此时内存已满,无法再装入新的页(段),OS还须再利用页(段)的置换功能,将内存中暂时不用的页(段)调至盘上,腾出足够的内存空间后,在将要访问的页(段)调入内存,使程序继续执行下去,这样,便可是一个大的用户程序在较小的内存空间中运行,也可在内存中同时装入更多的进程,使它们并发执行。

    综上所述,简而言之,就是:

    在程序运行时,只把当前必须运行的很小的一部分代码和数据装入内存,其余代码和数据需要时再装入,不再运行的代码和数据及时从内存中删除。

    虚拟存储器管理的目标

    • 使得大的程序能在较小的内存中运行;
    • 使得多个程序能在较小的内存中运行;
    • 使得多个程序并发运行时地址不冲突;
    • 使得内存利用效率高;

    虚拟存储器的工作原理:

    置换

    • 基于置换算法

    请求调入

    • 基于中断机制

    部分装入

    • 基于局部性原理

    基于离散的存储管理

    • 页式虚拟存储管理方式 —— 请求分页系统

    在这里插入图片描述

    • 段氏虚拟存储管理方式 —— 请求分段系统

    在这里插入图片描述

    5.2、请求分页管理方式

    5.2.1、请求分页的硬件支持

    ​ 为了实现请求分页,系统必须提供一定的硬件支持,计算机系统除了要求一定容量的内存和外存外,还需要请求页表机制缺页中断机构以及地址变换机构

    1、请求页表机制

    作用:仍然是将用户地址空间中的逻辑地址映射为内存空间中的物理地址。

    为了满足页面换仅换出的需要,在请求页表中又增加了四个字段:
    在这里插入图片描述

    1)状态位(存在位)P:指示该页是否已调入内存,供程序访问时参考。

    2)访问字段A:用于记录本页在一段时间内被访问过的次数,或记录本页最近已有多长时间未被访问,提供给置换算法(程序)在选择换出页面时参考。

    3)修改位M:标识该页在调入内存后是否被修改过。

    由于内存中的每一页都在外存上保留一份副本,因此在置换该页时,有两种情形:

    • 若未被修改过,就不需要再将该页写回到外存上
    • 若被修改过,则必须将该页重写到外存上,以保证外存中所保留的副本始终是最新的。

    4)外存地址:指出该页在外村上的地址,通常是物理块号,供调入该页时参考

    2、缺页中断机构

    当要访问的页面不在内存时,便产生一缺页中断,请求OS将所缺页调入内存。

    缺页中断作为一种特殊的中断,它与一般的中断相比有着明显的区别,主要表现在下面两个方面:

    1)在指令执行期间产生和处理中断信号。

    • 缺页中断返回后,该指令要重新执行(指令复执)

    2)一条指令在执行期间可能产生多次缺页中断。
    在这里插入图片描述
    3、地址变换机构

    简要地址变换过程:
    在这里插入图片描述

    请求分页系统中的详细的地址的地址变换过程:
    在这里插入图片描述

    主要的动作:

    • 处理缺页中断
    • 从外存磁盘读入所需的页面
    • 重新开始执行被中断的进程

    主要的时间开销:

    • 从磁盘读入所需的页面(I\O操作)

    5.2.2、请求分页中的内存分配

    在为进程分配内存时,将涉及到三个问题:

    (对于单个进程而言)

    第一:为保证进程能正常运行,所需要的最小物理块数的确定

    第二:在为每个进程分配物理块时,应采取什么样的分配策略,即所分配的物理块是固定的还是可变的;

    (对于全部进程而言)

    第三:为不同进程所分配的物理块数,采取什么样的策略,是采取平均分配算法,还是根据进程的大小按比例分配;

    1、最小物理块数的确定

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

    1)分配给一个进程的物理块数越少,内存中的进程数越多;

    2)若一个进程分配的物理块数太少,缺页率较高;

    3)最少物理块数与指令的格式、功能和寻址方式有关

    2、内存分配策略

    • 在请求分页系统中,可采取两种内存分配策略,即固定和可变分配策略

    • 在进行置换时,也可采取两种策略,即全局置换和局部置换

    • 从空闲物理块中选择

    • 若没有空闲物理块 —— 置换

    • 全局置换:可以选择内存中任意进程的页进行替换。可以从另一个进程中获得物理块。

    • 局部置换:只能从进程自身在内存中的页面进行替换。

    于是可组合出一下三种适用的策略

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

    • 固定分配:指为每个进程分配固定的物理块数,进程在整个运行期间不变

    • 局部置换:指进程运行过程中若发生缺页,只能从进程本身所拥有的的物理块中选择一页换出,再调入所需页。

    • 特点:

      • 分配简单,不会影响其他进程。
      • 但进程所需的内存大小难确定;太少,频繁缺页中断;太多,内存中进程数目减少

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

    • 可变分配:开始时系统为每个进程分配一定数目的物理块,OS自身保留一空闲物理块队列。当某进程发生缺页中断时,从空闲队列中取出一空闲物理块分配给该进程,让其装入页

    • 全局置换:指若空闲队列已空,而又发生缺页中断时,从内存空间中的任一进程所拥有的物理块中选择一页换出。

    • 特点:

      • 实现简单,在很多操作系统中使用。
      • 但会导致其他进程缺页率增加。

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

    • 可变分配:开始为各进程分配一定数目的物理块,并且在进程运行期间可根据情况(缺页率)适当调整物理块数。

    • 局部置换:当发生缺页中断时,只能从本进程的页面中选择一页换出。

    • 特点:

      • 性能较好,但较复杂。

    3、物理块分配算法

    1)平均分配算法:即将系统中所有可供分配的物理块平均分配给各个进程。

    2)按比例分配:即根据进程的大小按比例分配物理块

    • 各进程页面总数为:S=i=1NSiS = \sum_{i=1}^N Si
      • Si 为每个进程的页面数
    • 物理块总数为:m
    • 则每个进程所得物理块数为:Bi=SiSmBi = \frac{Si}{S} * m
      • 其中BiBi应该取整,它必须小于最小物理块数

    3)考虑优先权的分配算法:依据进程优先级分配物理块。

    5.2.3、页面调入策略

    为了使进程能够正常运行,必须事先将要执行的那部分程序和数据所在的页面调入内存。

    现在的问题是:

    • 系统应在何时调入所需页面
    • 系统应从何处调入这些页面
    • 是如何进行调入的

    1、何时调入所需页面

    为了确定系统在进程运行时将所缺的页面调入内存的时机,可以采取预调入页策略请求调页策略。先分述如下:

    1)预调入策略

    如果进程的许多页是存放在外存的一个连续区域中,一次调入若干个相邻的页会比一次调入一页更高效些。

    以预测为基础的预调页策略,将那些预计在不久后之后便会被访问的页面预先调入内存,目前预调页的成功率仅约 50%。

    2)请求调页策略

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

    • 优点:

      • 易于实现,目前虚拟存储器,大多采用此策略
    • 缺点:

      • 花费较大的系统开销,增加了磁盘I/O的启动频率

    2、从何处调入这些页面

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

    • 用于存放文件的文件区(采用离散分配方式)
    • 用于存放对换页面的对换区(通常是采用连续存储分配的)

    每当发生缺页请求时,系统应从何处将缺页调入内存,可分成如下三种情况进行:

    1**)、系统拥有足够的对换区空间。**

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

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

    ​ 这时,凡是不会被修改的文件,都直接从文件区调入;当换出这些页面时,由于它们未被修改,则不必再将它们重写到磁盘(换出),以后再调入时,仍从文件区调入。

    ​ 对于已被修改的页面,在将它们换出时便须调到对换区,以便需要时在从对换区调入。

    3)、UNIX方式

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

    ​ 由于UNIX系统允许页面共享,因此,某进程所请求的页面有可能被其他进程调入内存,此时也就无需再从对换区调入。

    3、页面调入过程

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

    2)、通过查找页表找到该页在外存的物理地址后

    3)、查看此时内存是否已满,如果未满,就能容纳新页,则启动磁盘I/O,将所缺之页调入内存,然后修改页表

    4)、如果已满,则须先按照某种置换算法,从内存中选出一页准备换出;若要换出的一页未被修改过(修改位为”0“),可不必将该页写会磁盘;

    5)、但如果此页已被修改过(修改位为“1“),则必须将它写会磁盘,然后再把所缺的页调入内存,并修改页表中的相应表项(将存在位置为“1”),并将此页表项写入快表中;

    6)、缺页调入内存后,利用修改后的页表形成所要访问的物理地址,再去访问内存数据。

    4、缺页率

    假设在进程 J中:

    • 逻辑页面:n 页
    • 物理块:m 块 (m <= n)
    • 访问页面成功的次数为:S
    • 访问页面失败(产生缺页)的次数为:F
    • 进程执行过程中总的页面访问次数为:A
      • A=S+FA = S + F

    则,进程运行中的缺页率为:P=FAP = \frac{F}{A}

    和存取时间的关系:

    • 存取内存的时间:1ms
    • 页面交换的时间:10ms

    EAT=(1p)1+p10=1+9pEAT = (1-p)*1 + p*10 = 1+9p

    影响缺页率的因素:

    • 页面的大小
    • 进程分配的物理块数
    • 页面置换算法
    • 程序固有特性

    5.3、页面置换算法

    ​ 在进程的运行过程中,若其要访问的页面不在内存中,而需要把它们调入内存,但内存已无空闲空间时,为了保证进程能够正常运行,系统必须从内存中调出一页程序(数据)送到磁盘的对换区中。

    把选择换出页面的算法称为:页面置换算法(Page-Replacement Algorithm)

    在介绍页面置换算法之前,先了解一下什么是 “抖动”?

    “抖动”(Thrashing):即刚被换出的页很快又要被访问,需要将它重新调入,此时有需要再选一页调出;而此刚被调出的页很快又被访问,又需将它调入,如此频繁地更换页面,以致一个进程在运行中把大部分的时间花费在页面置换工作中,我们称该进程发生了“抖动”。

    简而言之:“抖动”是页面在内存和外存之间频繁交换的现象。

    页面置换策略的目标是:

    1. 具有较低的缺页率(高命中率)
    2. 避免程序发送“抖动”

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

    1、最佳置换算法(OPT,optimal)

    只能作为一个“标准”,去评价其他算法

    • 思想:置换永不再用或者**最长时间内(未来)**不再被访问的页面

    • 举例:

    在这里插入图片描述

    • 优点:

      • 缺页率最低,性能最好
    • 缺点:

      • 实际上无法实现,无法预知哪一个页面是未来最长时间内不再被访问过的;

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

    • 思想:置换在内存中驻留时间最久的页面

    • 举例:
      在这里插入图片描述

    • 优点:

      • 实现简单
    • 缺点:

      • 与进程实际运行的规律不相适应,进程只有按顺序访问地址空间时,页面命中率最理想。
    • 异常现象:Belady现象(随着物理块数的增加,缺页率不减少反而增加)

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

    3、最近最久未使用(LRU,Least Recently Used)

    • 思想:置换最长时间未被使用的页面

    • 实现方式:

      • 赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来经历的时间 t。当需要淘汰一个页面时,选择现有页面中 t 值最大的页面进行置换。
    • 举例:
      在这里插入图片描述

    • 优点:性能接近最佳算法

    • 缺点:需要记录页面使用时间的先后关系,硬件开销太大。

    4、最少使用置换算法(LFU,Least Frequently Used)

    • 思想:选择在最近时期使用最少的页面作为淘汰页

    • 举例:LFU置换算法的页面访问图,与LRU置换算法的访问图完全相同。

    在这里插入图片描述

    • 特点:
      • 要求较多的硬件支持,使得其实现所需要的成本较高。
      • 故在实际应用中,大多采用LRU的近似算法。Clock算法就是用得较多的一种LRU近似算法。

    5.2.3、Clock置换算法

    是LRU的一种近似算法

    1、简单的Clock算法

    由于该算法是循环检查个页面的使用情况,故称为:Clock算法。

    执行过程:

    1)、利用简单Clock算法时,只需为每页设置一位访问位,再将内存中的所有页面都通过链接指针连接成一个循环队列

    2)、当某页被访问过时,其访问位置被置为 1。置换算法在选择一页淘汰时,只需检查页的访问位。如果是 0,就选择该页换出;

    3)、若为 1,则重新将它置为 0,暂不换出,给予该页第二次驻留内存的机会,再按照 FIFO 算法检查下一个页面。

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

    在这里插入图片描述

    但因该算法只有一位访问位,只能用它表示该页是否已经使用过,而置换时是将未使用的页面换出去,故又把该算法称为 最近未用算法(NRU,Not Recently Used)

    2、改进型的Clock置换算法

    ​ 在将一个页面换出时,如果该页已被修改过,便须将该页重新写会到磁盘上;但如果该页未被修改过,则不必将它拷回磁盘。

    ​ 换而言之,对于修改过的页面,在换出时所付出的开销比未修改过的页面大,或者说,置换代价大。

    ​ 这样,在选择页面换出时,既要考虑未使用过的页面又要是未被修改过的页面。
    在这里插入图片描述

    执行过程:

    1)、从指针所指示的当前位置开始,扫描循环队列,寻找 A = 0,M = 0的第一类页面,将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位 A。

    2)、如果第一步失败,即查找一轮后未遇到第一类页面,则开始第二轮扫描,寻找 A = 0,M = 1的第二类页面,将所遇到的第一个这类页面作为淘汰页。在第二次扫描期间,将所有扫描过的访问位 A 都置为 0。

    3)、如果第二步也失败,即未找到第二类页面,则将指针返回到最开始的位置,并将所有与的访问位A复 0,然后重复第一步,如果仍失败,则重复第二步。

    ​ 该算法与简单Clock算法比较,可减少磁盘的I/O操作次数。但为了找到一个可置换的页,可能须经过几轮扫描。

    ​ 换言之,实现该算法本身的开销将有所增加。

    5.3.4、页面缓冲算法

    在请求分页系统中,页面换进换出所要付出的开销将对系统性能产生重大影响。为此,我们需要对影响页面环进环出的因素进行分析。

    1、影响页面环进环出效率的若干因素

    1)、页面置换算法

    2)、写回磁盘的频率

    ​ 对于已修改的页面,在将其换出时,应当会写回磁盘。

    ​ 但是如果在系统中建立一个已修改换出页面的链表,则对每一个要被换出的页面(已修改),系统可暂时不把它们写会磁盘,而是将它们挂在已修改换出页面的链表上,仅当被换出页面达到一定值时,再一起写回磁盘。减少了操作磁盘I/O的操作次数。

    3)、读入内存的频率

    ​ 在设置了已修改换出页面链表后,在该链表上就暂时有一批装有数据的页面,如果该进程在这批数据还未写会磁盘时,就需要再次访问,则可以直接从已修改换出页面的链表上获取。减少将页面从磁盘读入内存的频率。

    2、页面缓冲算法 PBA

    在 VAX/VMS操作系统中

    在内存中需要设置两个链表

    • 空闲页面链表

    • 修改页面链表

    • 特点:

      • 显著降低了页面换进、换出的频率,使磁盘I/O操作次数大为减少,因而减少了页面换进换出的开销。
      • 实现简单,不需要特殊的硬件支持

    5.3.5、访问内存的有效时间

    EAT访EAT:内存的有效访问时间

    λ\lambda:查找快表的时间

    t访()t:访问实际物理地址所需的时间(或查找页表项的时间)

    α\alpha:处理缺页中断的时间

    1)被访问的页在内存中,且对应的页表项在快表中

    EAT = 查找快表的时间 + 访问实际物理地址所需的时间

    EAT=λ+tEAT = \lambda + t

    2)被访问的页在内存中,且对应的页表项不在快表中

    EAT = 查找快表的时间 + 查找页表项的时间 + 更新快表的时间 + 访问实际物理地址所需的时间

    EAT=λ+t+λ+tEAT = \lambda + t + \lambda + t

    3)被访问的页不在内存中

    EAT = 查找快表的时间 + 查找页表项的时间 + 处理缺页中断的时间+ 更新快表的时间 + 访问实际物理地址所需的时间

    EAT=λ+t+α+λ+tEAT = \lambda + t + \alpha + \lambda + t

    5.4、“抖动”与工作集

    5.4.1、多道程序度与“抖动”

    1、多道程序度与处理机利用率
    在这里插入图片描述

    横轴:多道程序度

    纵轴:CPU的利用率

    2、产生“抖动“的原因

    ​ 发生“抖动”的根本原因是,同时在系统中运行的进程太多,由此分配给每一个进程的物理块太少,不能满足进程正常运行的基本要求,致使每个进程在运行时,频繁地出现缺页,必须请求系统将所缺之页调入内存,这会使得在系统中排队等待页面调进/调出的进程数目增加。

    ​ 显然,对磁盘的有效访问时间也随之增加,造成每个进程的大部分时间都用于页面的换进/换出,而几乎不能再去做任何有效的工作,从而导致发生处理机的利用率急剧下降并趋于 0 的情况。我们称此时的进程是处于 “抖动” 状态。

    5.4.2、工作集

    1、引入的原因:

    由于“抖动”的发生与系统为进程分配的物理块的多少有关,1968年,Denning认为,依据程序访问的局部性原理,通过进程在过去一段时间内访问的页面来动态调整分配给进程的物理块数

    2、工作集的定义

    工作集:一个进程在某段时间间隔 Δ\Delta 内,进程要访问的页面集合。

    • Δ\Delta:工作集窗口,是给定访问序列选取的定长区间。

    • 落在工作集窗口中的页面集合称为工作集

    • W(ti,Δ)W(t_i, \Delta)表示在 tiΔt_i - \Deltatit_i 之间所访问的页面集合,则它就是进程在时间 tit_i的工作集

    • W(ti,Δ)|W(t_i, \Delta)| 表示工作集中页面数目,称为 工作集尺寸

    • 举例:
      在这里插入图片描述

    如果系统能随 W(ti,Δ)|W(t_i, \Delta)| 的大小来分配物理块,就既能有效利用主存,又可使缺页中断尽量少地发生。

    3、实现过程

    • 操作系统跟踪每个进程的工作集,并为其分配大于其工作集的物理块
    • 如果还有空闲物理块,则可启动其他进程
    • 如果所有工作集之和超过了可用物理块的总数,那么操作系统会暂停一个进程,将其该进程换出,所释放的物理块分配给其他进程。

    5.4.3、“抖动”的预防方法

    1、采取局部置换策略(内存如果是可变分配方式)

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

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

    • L:缺页之间的平均时间

    • S:平均缺页时间,即用于置换一个页面所需的时间

    4、选择暂停的进程

    在内存管理中,“内零头”和“外零头”个指的是什么?在固定式分区分配、可变式分区分配、页式虚拟存储系统、段式虚拟存储系统中,各会存在何种零头?为什么?

    解答:

    1)、在存储管理中,内零头是指分配给作业的存储空间中未被利用的部分,外零头是指系统中无法利用的小存储块。
    在固定式分区分配中,为将一个用户作业装入内存,内存分配程序从系统分区表中找出一个能满足作业要求的空闲分区分配给作业,由于一个作业的大小并不一定与分区大小相等,因此,分区中有一部分存储空间浪费掉了。由此可知,固定式分区分配中存在内零头。

    2)、在可变式分区分配中,为把一个作业装入内存,应按照一定的分配算法从系统中找出一个能满足作业需求的空闲分区分配给作业,如果这个空闲分区的容量比作业申请的空间容量要大,则将该分区一分为二,一部分分配给作业,剩下的部分仍然留作系统的空闲分区。由此可知,可变式分区分配中存在外零头。

    3)、在页式虚拟存储系统中,用户作业的地址空间被划分成若干大小相等的页面,存储空间也分成也页大小相等的物理块,但一般情况下,作业的大小不可能都是物理块大小的整数倍,因此作业的最后一页中仍有部分空间被浪费掉了。由此可知,页式虚拟存储系统中存在内零头。

    4)、在段式虚拟存储系统中,作业的地址空间由若干个逻辑分段组成,每段分配一个连续的内存区,但各段之间不要求连续,其内存的分配方式类似于动态分区分配。由此可知,段式虚拟存储系统中存在外零头。

    展开全文
  • 虚拟存储器管理 vc++程序,有结果截图。
  • 所谓“虚拟存储器”,是指具有请求调入功能和置换功能,能从逻辑上对内存容量加以扩充的一种存储器系统。 虚拟的实现建立在离散分配存储管理基础上 ,若采用连续分配方式,需申请足够空间,再分多次装入,造成...

    具体寻找物理快号的流程如下:

    虚拟处理部分如下:

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

    虚拟的实现建立在离散分配存储管理基础上 ,若采用连续分配方式,需申请足够空间,再分多次装入,造成内存资源浪费,并不能从逻辑上扩大内存容量。

    缺页率: 页面调入次数(缺页次数/总的页面使用次数 

    页面置换算法(page replacement algorithms):选择换出哪些页面的算法,其好坏直接影响系统的性能。

    1)最佳Optimal置换算法

    2)先进先出FIFO置换算法

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

    4)CLOCK置换算法

    Belady现象:

    出现分配的页面数增多,缺页率反而提高的异常现象

     影响缺页率的主要因素:

    (1)分配给作业的主存块数: 多则缺页率低,反之则高。

    (2)页面大小:大则缺页率低;反之则高。

    (3)页面调度算法:对缺页中断率影响很大,但不可能找到一种最佳算法。

    (4)程序编制方法:以数组运算为例,如果每一行元素存放在一页中,则按行处理各元素缺页中断率低;反之,按列处理各元素,则缺页中断率高。 

    抖动:

     

    在请求分页存储管理中,从主存中刚刚换出某一页面后,根据请求马上又换入该页,这种反复换出换入的现象称为抖动。

    抖动原因:页面淘汰算法不合理;分配给进程的物理页面数(驻留集)太少。

    请求分段存储管理方式:

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

    展开全文
  • 虚拟存储器管理_操作系统一、实验内容二、实验思路三、实验截图四、实验代码 一、实验内容 1.模拟分页式存储管理中硬件的地址转换和产生缺页中断 分页式虚拟存储系统是把作业信息的副本存放在磁盘上, 当作业被选中时...

    一、实验内容

    1.模拟分页式存储管理中硬件的地址转换和产生缺页中断

    分页式虚拟存储系统是把作业信息的副本存放在磁盘上, 当作业被选中时, 可把作业的开始几页先装入主存且启动执行。 为此, 在为作业建立页表时, 应说明哪些页已在主存, 哪些页尚未装入主存。

    作业执行时, 指令中的逻辑地址指出了参加运算的操作存放的页号和单元号, 硬件的地址转换机构按页号查页表, 若该页对应标志为 “1”, 则表示该页已在主存, 这时根据关系式 “绝对地址=块号 X块长十单元号” 计算出欲访问的主存单元地址 。 如果块长为2 的幕次, 则可把块号作为高地址部分, 把单元号作为低地址部分, 两者拼接而成绝对地址。若访问的页对应标志为“0”,则表示该页不在主存,这时硬件发“缺页中断”信号, 由操作系统按该页在磁盘上的位置, 把该页信息从磁盘读出装入主存后再重新执行这条指令。

    2.用先进先出(FIFO)页面调度算法处理缺页中断

    在分页式虚拟存储系统中,当硬件发出“缺页中断”后,引出操作系统来处理这个中断事件 。 如果主存中已经没有空闲块, 则可用 FIF0页面调度算法把 该作业中最先进入主存的一页调出, 存放到磁盘上, 然后再把当前要访问的页装入该块。 调出和装入后都要修改页表中对应页的标志。

    FIF0页面调度算法总是淘汰该作业中最先进入主存的那一页, 因此可以用一个数组来表示该作业已在主存的页面 。 假定作业被选中时, 把开始的 m个页面装入主存, 则数组的元素可定为m个。

    二、实验思路

    1. 地址转换
      为更快进行实验,指令的逻辑地址定为10个,已经固定值。
      通过一个for循环按顺序读入指令的逻辑地址,然后在页表中查找该逻辑地址的页号是否在内存中,如果在,则使用从页表中查到的页号的块号形成绝对地址的高位,逻辑地址的页内地址形成绝对地址的低位。

    2. FIFO页面调度
      初始内存为空,当有页面进入时,将3个内存单元的内容前移,起到页面的移除作用,最前面的为最早进入的,空出的第三个进入新的页面,以此循环实现FIFO算法。

    三、实验截图

    在这里插入图片描述

    四、实验代码

    #include<iostream>
    using namespace std;
    
    //存储器管理 块大小16 内存3
    	/*	----------FIFO-----------
    页面引用号:3 4 2 3 5 7 8 1 5 3
     3 3 3 3 5 5 5 1 1 1
     0 4 4 4 4 7 7 7 5 5
     0 0 2 2 2 2 8 8 8 3
    是否发生置换:
     1 1 1 0 1 1 1 1 1 1
    缺页率为:0.9
    */
    
    class page{
    public:
        int pageNum;//页号
        int state;//在内存标志
        int address;//磁盘地址
    };
    
    page pTable[]={
    {0,0,4},{1,0,5},
    {2,0,6},{3,0,7},
    {4,0,9},{5,0,10},
    {6,0,11},{7,0,13},
    {8,0,14},{9,0,15}
    };//作业信息副本
    
    page ram[3];//内存大小
    
    //指令的逻辑地址分为页号0-9和业内地址0-15
    //页号可以在页表找到物理块号0-15
    //该物理块号与页内地址拼接成物理地址
    
    //绝对地址=块号0-15×块长15+页内地址0-15
    //绝对地址=块号 X块长十单元号
    
    //如果块长为2的幕次,
    //则可把块号作为高地址部分, 把单元号作为低地址部分,
    //两者拼接而成绝对地址
    
    class Order{
    public:
        int idpage;//0-9
        int idinpage;//0-15
    };
    
    Order ord[]={
    {3,4},{4,2},{2,8},{3,6},{5,9},{7,4},{8,3},{1,8},{5,4},{3,8}
    };//逻辑地址 指令集合
    
    class Ram_address{
    public:
        int abshigh;
        int abslow;
    };//绝对地址
    
    void FIFO(int a);
    Ram_address fun(int a,int b);
    void Address_translation();
    
    Ram_address fun(int a,int b){
        Ram_address A;
        for(int j=0;j<10;j++){//查表
            if(pTable[j].pageNum==a){
                if(pTable[j].state==1){//在内存
                    A.abshigh=pTable[j].address;//高位 块号
                    A.abslow=b;//底位 页内地址
                    return A;
                }else if(pTable[j].state==0){//不在内存
                    cout<<"缺"<<a<<"页中断"<<endl;
                    FIFO(a);
                    return fun(a,b);
                }
            }
        }
    }
    
    
    void FIFO(int a){
        int c;
        int del=ram[0].pageNum;
        for(int i=0;i<2;i++){
            ram[i]=ram[i+1];
        }
    
        for(int j=0;j<10;j++){//页表信息更改
            if(pTable[j].pageNum==del){
                pTable[j].state=0;
            }
            if(pTable[j].pageNum==a){
                pTable[j].state=1;
                c=pTable[j].address;
            }
        }
    
        ram[2].address=c;
        ram[2].pageNum=a;
        ram[2].state=1;
    }
    
    
    void Address_translation(){
        //10个逻辑地址输入
        for(int i=0;i<10;i++){//10次作业地址转换
            int a=ord[i].idpage;//逻辑地址拆分
            int b=ord[i].idinpage;
            cout<<"指令的逻辑地址"<<a<<b<<endl;
            Ram_address out;
            out=fun(a,b);
            cout<<"内存的绝对地址";//16进制输出便于观察
            if(out.abshigh>=10){
                for(int j=0;j<6;j++){
                    if(out.abshigh-10==j){
                        cout<<(char)('A'+j);
                    }
                }
            }else{cout<<out.abshigh;}
    
            if(out.abslow>=10){
                for(int j=0;j<6;j++){
                    if(out.abslow-10==j){
                        cout<<(char)('A'+j)<<endl;
                    }
                }
            }else{cout<<out.abslow<<endl<<endl;}
        }
    }
    
    
    int main(){
        Address_translation();
        return 0;
    }
    
    
    展开全文
  • 第五章 虚拟存储器管理作业 什么是程序运行时的时间局限性和空间局限性? 时间局限性: 程序中的某条指令一旦执行, 则补救的将来该指令可能再次被执行; 对于储存单元同样使用 时间局限性主要原因是程序中大量的循环...
  • 课程设计贡献上来给大家分享下~! 操作系统课程设计 虚拟存储器管理系统设计
  • A:(1)对换(2)内存保护(3)地址映射(4)虚拟存储器。分析:对换是提高处理机利用率和系统吞吐量。2、从下列关于非虚拟存储器的论述中,选出一条正确的论述。要求作业在运行前,必须全部装入内存,且在运行过程...
  • 操作系统实验五 虚拟存储器管理

    万次阅读 多人点赞 2015-12-07 21:56:12
    实验五 虚拟存储器管理一、实验目的1、 理解虚拟存储器概念。2、 掌握分页式存储管理地址转换和缺页中断。二、实验内容与基本要求1、 模拟分页式存储管理中硬件的地址转换和产生缺页中断。2、 用先进先出页面调度...
  • 虚拟存储器管理之:页面置换算法 存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。 这次的目的是通过请求页式管理中页面置换算法模拟设计,了解虚拟存储技术...
  • 它是一篇《操作系统》课程设计的报告,关于windows虚拟存储器管理的完整性报告。
  • 实验二 Windows虚拟存储器管理 2.1实验目的 了解Windows 2000/XP的内存管理机制,掌握页式虚拟存储技术 理解内存分配原理,特别是以页面为单位的虚拟内存分配方法 掌握Windows 2000/XP下内存管理的基本API ......
  • 对于虚拟存储器的原理,以及分页虚拟存储管理方式,分段虚拟存储管理进行了详细的介绍!
  • 存储器管理中,连续分配方式会形成许多“碎片”,虽然可通过“紧凑”方法将许多碎片拼接成可用的大块空间,但须为之付出很大开销。 如果允许将一个进程直接分散地装入到许多不相邻的分区中,则无须再进行“紧凑”...
  • 操作系统(五)虚拟存储器管理

    千次阅读 2020-06-14 09:23:21
    文章目录概述局部性原理时间局部性空间局部性虚拟存储器的特征虚拟存储器定义分页虚拟存储管理方式分页虚拟存储管理基本原理缺页中断缺页中断与与一般的中断的区别地址变换页面置换算法下面都看这张图,==并思考如何...
  • 二、准备知识2.1 分页式存储管理原理在存储器管理中,连续分配方式会形成许多“碎片”,虽然可通过“紧凑”方法将许多碎片拼接成可用的大块空间,但须为之付出很大开销。如果允许将一个进程直接分散地装入到许多不...
  • 1 voidinitpgc()2 {3 for(int i=0; i4 {5 pgclub[i]=0;6 }7 num=pgcnum/bknum;8 cout<12 {13 surplus=0;14 for(int i=0; i28 }29 cout<42 cout<45 cout<50...
  • //页式存储管理方案,LRU算法 #include<iostream> using namespace std; int const Stack_Size=4; int Count_Page=0; int lackofpage=0; struct stack{ int Page[Stack_Size]; int Head; }; struct stack Stack; int ...
  • 内存管理内存管理操作系统的内存管理主要是做什么?操作系统的内存管理主要负责内存的分配与回收(malloc 函数:申请内存,free 函数:释放内存),另外地址转换也就是将逻辑地址转换成相应的物理地址等功能也是操作...
  • 虚拟存储器管理-模拟分页请求和缺页调度 请求分页系统虚拟存储技术是把作业地址空间的全部信息放在磁盘上,当作业被选中运行时,先把作业的开始几页装入主存并启动运行。为此在为作业建立页表时,应说明哪些页已经...
  • 虚拟存储器管理(C++实现)

    千次阅读 2019-06-05 20:50:04
    请求分页虚拟存储管理技术,是把作业地址空间的全部信息存放在磁盘上。当作业被选中运行时,先把作业的开始几页装入主存,并启动运行。为此,在为作业建立页表时,应说明哪些页已在主存,哪些页不在主存。其中标志...
  • 外存及虚拟存储器管理

    千次阅读 2018-06-29 16:49:52
    外存资源管理外存空间划分静态等长,2i, 称为一块(block),块是外存分配的基本单位,也是IO传输的基本单位。如果需求不足一个完整块,会形成块内“零头”。由于外存空间很大,块内零头忽略。外存空间分配空闲块链(慢...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,058
精华内容 823
关键字:

虚拟存储器管理