精华内容
下载资源
问答
  • 每当我们安心使用LINUX系统或者在编写C语言时候,安心使用malloc或者free时候,我们很少关注过其底层内存是怎么工作,CPU是如何...那么,这篇博客就要讲述一下虚拟存储器是一个什么东西。 第一篇会从硬

    每当我们安心的使用LINUX系统或者在编写C语言的时候,安心的使用malloc或者free的时候,我们很少关注过其底层的内存是怎么工作的,CPU是如何获取从主存中获取数据的,我们的寻址是不是可以直接寻找到对应的数据,还是通过某种转化机制。实际上,对于每一个进程,它所能接触到的地址都不是实际的物理地址,而是通过虚拟地址进行映射而来的。那么,这篇博客就要讲述一下虚拟存储器是一个什么东西。
    第一篇会从硬件和操作系统的角度来说明虚拟存储器是个什么东西。
    第二篇会从动态存储器,从程序应用的角度重点讲述(malloc和free的相关机制)。
    闲话少说,你将在这篇博客里面看到如下内容:
    这里写图片描述
    1.1 什么是虚拟地址和物理地址:
    首先,要说虚拟地址就要先说一下物理地址。可以理解我们的主存被组织成一个由M个连续的字节大小的单元组成的数组。而每一个字节都有一个对应的地址,这样的地址就被称作是物理地址。那么,我们的程序是不是可以直接可以接触到物理地址,就是是不是可以直接从物理地址当中获取数据。答案明显是不是的,我们先来分析一下如果所有的进程直接访问同一块连续的物理地址有什么弊端呢?
    1. 主存的容量有限。虽然我们现在的主存容量在不断上升,4G,8G,16G的主存都出现在市面上。但是我们的进程是无限,如果计算机上的每一个进程都独占一块物理存储器(即物理地址空间)。那么,主存就会很快被用完。但是,实际上,每个进程在不同的时刻都是只会用同一块主存的数据,这就说明了其实只要在进程想要主存数据的时候我们把需要的主存加载上就好,换进换出。针对这样的需求,直接提供一整块主存的物理地址就明显不符合。
    2. 进程间通信的需求。如果每个进程都 独占一块物理地址,这样就只能通过socket这样的手段进行进程通信,但如果进程间能使用同一块物理地址就可以解决这个问题。
    3. 主存的保护问题。对于主存来说,需要说明这段内存是可读的,可写的,还是可执行的。针对这点,光用物理地址也是很难做到的。
    针对物理地址的直接映射的许多弊端,计算机的设计中就采取了一个虚拟化设计,就是虚拟内存。CPU通过发出虚拟地址,虚拟地址再通过MMU翻译成物理地址,最后获得数据,具体的操作如下所示:
    VA转化为PA
    利用了虚拟内存就可以比较有效的解决以上三个问题,在每一个进程开始创建的时候,都会分配一个虚拟存储器(就是一段虚拟地址)然后通过虚拟地址和物理地址的映射来获取真实数据,这样进程就不会直接接触到物理地址,甚至不知道自己调用的那块物理地址的数据。
    1.2 地址空间的概念
    为了能更好的理解下面的所说的地址翻译等知识点,这里说一下地址空间的概念。首先,对于32位的计算机,每一个地址所对应的数据空间是32位,也就是四个字节。那么如果一个地址可以用32位表示,那么对于这32位地址的所有可能就是:232种可能,那么32位地址的地址空间就为232。下面所说的,虚拟地址的地址空间和物理地址的地址空间也就是取决于虚拟地址和物理地址的位数,如果位数分别为M,N,那么地址空间也为:2M和2N.
    下面补充一下几个常见的单位:
    这里写图片描述.

    1.3 地址分页的概念
    对于一整块连续的内存,直接连续使用也是不太符合实际的。于是,就有分页的概念。将1024个地址分成一页,通过访问页来访问数据。那么有了页就要有如何寻找页的概念了。我们通过每一页的首地址作为页入口,即(PTE)来检索页。那么,对于这些PTE,我们也需要一个专门的数据结构来进行管理,这样的数据结构就是页表(page table)。

    1.4 虚拟存储器的缓存作用
    这里先说明一下DRAM,SRAM和磁盘的速度区别,对于速度:
    SRAM>DRAM>>磁盘
    SRAM的速度是DRAM的10倍,DRAM是磁盘速度的百来倍,所以SRAM常作为CPU上L1,L2,L3缓存的材料,DRAM作为主存,针对于SRAM和DRAM,cache MISS的惩罚而言,DRAM的惩罚更大,因为DRAM的读写速度是磁盘的几百倍,所以利用在DRAM的缓存的作用就更大了,针对于虚拟存储器的缓存作用可以用下图所示:
    这里写图片描述
    虚拟存储器中的块分为:未分配的,缓存的,未缓存的。
    未分配的:顾名思义,这一块的虚拟存储器不映射于任何块。
    缓存的:这一块的虚拟存储器映射于已经存在于DRAM中的物理页。
    未缓存的:这一块的虚拟存储器映射于存在于磁盘中的虚拟页。(也就是要使用就要把磁盘中的虚拟页替换到DRAM中的物理页,会发生Page Fault )
    有效和无效通过一个valid bit(有效位)来进行判断
    这里写图片描述

    这里就要再重复说明一下了:页表,PTE,物理存储器,虚拟存储器分别放在什么地方。
    DRAM里面有:页表,PTE,物理存储器
    磁盘里面:虚拟页表

    那么对于缓存来说:就有页命中,和页不命中两种情况
    页命中:在图中就类似于VP1,VP2,这类的页表,直接缓存在DRAM中的物理存储器中,可以直接从DRAM中获取速度就快了。
    页不命中:就是访问页表中未缓存的PTE,如VP3,VP6之类,如下图所说明的情况
    这里写图片描述
    这里写图片描述

    虚拟地址想访问VP3的时候,发现VP3未在缓存中,发生page fault.利用替换算法(替换算法可能是FIFO,或者LRU)将物理存储器中的一个VP3从物理存储器中导出,VP4从磁盘导入DRAM中。此时,PTE3就变成了已缓存,PTE4变成了未缓存。这时候在进行地址翻译,就变成页命中了。
    可见,page fault从磁盘导入的效率是非常低的,但是由于局部性原理,进程往往更多的在较小的活动页面上工作,很少有大跨度的访问内存,使得page fault产生的可能性降低。页命中的可能性提高。
    获取数据的效率就快了很多。

    1.5虚拟存储器的其它作用:
    正如上面所说的只使用物理地址的弊端,虚拟存储器可以解决部分的问题。
    1.简化共享:利用虚拟地址来映射物理地址,使得可以让多个进程的不同虚拟地址映射同一块物理地址,比如类似于printf,这一类常用的库,不会把printf的代码拷贝到每一个进程,而是让不同进程都使用同一块printf.
    2. 虚拟存储器作为存储器保护的工具,在虚拟存储器里面可以设计该PTE是可读,可写,还是可执行的。如果一旦出现只读的PTE被写入了,CPU就会发送出现segmentation fault(段错误)但并不会影响到实际存放数据的物理内存,
    这里写图片描述

    地址翻译

    地址翻译作为虚拟存储器中最难的一块也不为过,本人也是花了好大的功夫才这块东西吃透。
    1.首先先来了解地址翻译的目的是什么,地址翻译的目的是通过MMU将虚拟地址翻译成物理地址。
    那么虚拟地址的那么多个地址位又分成那些部分呢?,我先放上一张符号说明图来为后面的地址翻译提供便利:
    这里写图片描述

    下面以只有一级页表为例:
    下面的转化图将说明虚拟地址到物理地址的一个过程
    这里写图片描述

    无论是虚拟地址还是物理地址都被分成两个部分,一个页号(PN),用来寻找对应的存储页,还有一个偏移量(PO)用来寻找在对应页中的偏移量。对于偏移量来说,虚拟页的偏移量和物理页的偏移量是相同的。那么,说明我们所需要的转化就是从虚拟页号转化到物理页号。
    这也就意味着我们可以使用一个小trick加速翻译的速度,分别将VPN,VPO分开传输,VPN传输到MMU进行翻译,VPO直接传输到L1 cache进行偏移检索,而不是等到VPN翻译成PPN再进行翻译,这个称作是优化地址翻译
    什么下就是翻译页号了,翻译页号的步骤就是通过VPN在页表中进行寻找找到对应的PTE,如果发现PTE的有效位为0,说明页面不存在,就出现缺页错误,重新加载页面到物理存储器中,然后设有效位为1(上面的缺页错误说的就是这个问题)。反之,有效位为1,说明页命中,取出PPN和VPO一合,得到物理地址,下图分别说明了,缺页错误和页命中两种情况的翻译情况:
    这里写图片描述
    这里写图片描述

    1. 但是通过DRAM中的页表来进行地址翻译的速度有可能太慢了,无法满足速度的需求。这个时候就要TLB中派上用场了,TLB作为SRAM的一部分,速度是快于页表查询的。TLB的实际作用,做一个映射,将VPN在TLB中寻找,找到对应的PPN。那么问题来了,TLB是怎么做的映射的呢?这时候就要说明一下VPN对于TLB来说可以分成那几块,请看下图:
      这里写图片描述

    可以看见VPN被分为(TLBT:TLB标记,TLBI:TLB索引)
    这时候再来看看TLB构成是什么样的呢?
    这里展示的是一个四路组相连的一个TLB
    这里写图片描述
    TLBI的两位就说明该选TLB的那一组,前面的6位TLBT说明标记位。

    3.二级或者多级页表怎么处理

    二级页表或者多级页表都是为了更快的检索和更节约空间,请先看下面一个二级页表的例子:
    这里写图片描述
    首先二级页表并不复杂,就相当于多了一次映射,我们做一个简单的计算来说明二级页表容量关系,在二级页表中,一个PTE指向的是二级页表中,1024个PTE的一页,那么二级页表中的一个PTE也就指向虚拟存储器中的一页,也就是1KB的地址空间,一个地址中有32位,也就是4个字节,那么在二级页表中的一个PTE所包含的容量就为4KB字节。对于一级页表而言,一个PTE就代表着4MB字节的空间,1K的一级页表就代表了4GB字节的空间,4GB已经是现在很多内存条的容量了。
    那么对于多级页表,一个VPN又是怎么分配和映射的呢。相信下面的一张图就可以说明清楚。
    这里写图片描述

    1. 物理地址怎么处理
      那么,现在我们得到了物理地址,那么通过物理地址又怎么在物理存储器中寻找到我们想要的数据呢?
      先来看一下我们的物理地址分成那几个部分
      这里写图片描述

    可以看到物理地址被分成了三个部分:CO(块偏移),CI(索引),CT(标签)三个部分
    那么物理存储器又长什么样子呢?请看下图:
    这里写图片描述

    物理地址先找到CI索引,找到对应的set集合,然后判断这个集合的valid bit是否等于一并且tag是否与CT一致。如果这些条件都符合,在通过CO偏移找到想要的数据。

    最后:
    翻译实例:
    首先,我们的翻译实例是基于一级页表之间的转换,关于虚拟地址以及物理地址的长度及位置如下图所示:
    这里写图片描述

    这里写图片描述

    好了,信息完全。
    接下来,我们就来实际翻译的虚拟地址。
    我们翻译的地址为:0x03d4
    这里写图片描述

    我们得到了VPO,只需要翻译出PPN就好。
    接下来我们通过TLBI,TLBT来寻找对应的PPN。首先,可以知道TLBI为0x3,在TLB可以找到3为这个位,对应的标签TLBT也为0x3,很高兴我们找到TLBT为0x3的位,并且里面的PPN有值,值为0D,这个0D就是我们先要的PPN了,

    这时候我们就可以得到物理地址为PPN=0x0d,PPO=0x14,物理地址为:0x354
    如下图:
    这里写图片描述

    我们得到了CO=0x0,CI=0x5,CT=0x0d
    我们先通过CI找索引,然后再通过CT对照,很高兴,我们发现标记位相同,都为0x0D,且有效位为1,于是乎我们再通过CO=0的偏移,取出了数据0x36。嘻嘻嘻。
    这个就是翻译的全过程。
    当然针对于,不同的操作系统中,在通过虚拟地址进行页面通信的时候还有特性使用:例如写时拷贝这个特性,在这里就不赘述了,需要了解的人可以查找资料来了解。
    虚拟存储器的概念与工作原理就到这了。
    下一篇我们将讲述动态存储器的特点(即malloc和free的实际原理)。
    Reference:《深入理解计算机系统》

    展开全文
  • 虚拟存储器

    千次阅读 2014-06-09 15:03:34
    一、虚拟存储器工作原理 页式虚拟存储器虚拟存储器中用得比较广泛一种,另外段式虚拟存储器和段页式虚拟存储器主要是因为地址变换方法不同产生。  页式虚拟存储器:把主存储器、磁盘存储器和虚拟存储器都...

    一、虚拟存储器工作原理
    页式虚拟存储器是虚拟存储器中用得比较广泛的一种,另外的段式虚拟存储器和段页式虚拟存储器主要是因为地址变换方法不同产生的。 
    页式虚拟存储器:把主存储器、磁盘存储器和虚拟存储器都划分成固定大小的块--页(Page).
       主存储器的页称为实页,虚拟存储器中的页称为虚页。
     

    内部地址变换:多用户虚拟地址Av变换成贮存实地址A
      多用户虚拟地址中的页内偏移量D直接作为主存实地址中的页内偏移d
      主存实页号p与它的页内偏移d直接拼接就得到主存是地址A

    一个用户程序要访问虚拟存储器时,必须给出多用户虚拟地址Av。在操作系统和有关硬件的共同管理下,首先进行内部地址变换。

     如果变换成功(命中),得到主存实页号p。把主存实页号p与它的页内偏移d直接拼接起来就得到主存实地址A,访问主存储器。
     如果内部地址变换失败(未命中),表示要访问数据不在主存储器中,必须访问磁盘存储器。这时,进行外部地址变换。

     外部地址变换主要用软件实现,首先查外页表得到与虚页号P相对应的磁盘存储器的实地址,然后再查内页表(主存实页表),看主存储器中是否有空页。如果主存储器中还有空页,只要找到空页号。把磁盘存储器的实地址和主存储器的实页号送入输入输出处理机(输入输出通道)等,在输入输出处理机的控制下,把要访问数据所在的一整页都从磁盘存储器调入到主存储器。

     如果主存储器中已经没有空页,则要采用某种页面替换算法,先把主存中暂时不用的一页写回到磁盘存储器中原来的位置上,以便腾出空位置来存放新的页。

     在进行外部地址变换时,如果没有命中,则表示所需要的页还不在磁盘存储器中。这时,要在操作系统控制下,启动磁带机、光盘存储器等海量存储器,先把与所需要数据相关的文件从海量存储器中调入磁盘存储器。

    二、地址映像与变换

     虚拟存储器中有三种地址空间,对应三种地址。

       虚拟地址空间:虚存空间或虚拟存储器空间,是应用程序员用来编写程序的地址空间,这个地址空间非常大。
        主存储器的地址空间:主存地址空间、主存物理空间或实存地址空间
        辅存地址空间:磁盘存储器的地址空间
        虚拟地址:虚存空间上的地址,又称为虚存地址或者虚地址
        主存地址:又称为主存实地址、主存物理地址、主存储器地址
        磁盘存储器地址:又称为磁盘地址、辅存地址

    l地址映像:把虚拟地址空间映象到主存地址空间,具体地说,就是把用户用虚拟地址编写的程序按照某种规则装入到主存储器中,并建立多用户虚地址与主存实地址之间的对应关系。
    l地址变换:在程序被装入主存储器之后,实际运行时把多用户虚地址变换成主存实地址(内部地址变换)或磁盘存储器地址(外部地址变换)。

    三、虚拟存储方法

    l根据所采用的地址映象和地址变换方法不同,目前主要有页式虚拟存储器、段式虚拟存储器和段页式虚拟存储器等三种。

    1、段式虚拟存储器

    l 程序按模块划分,主存按段分配
    l 地址映像方法:每个程序从0地址开始编址,长度可长可短,可以在程序执行过程中动态调整程序段的长度。
    l每一道程序(或一个用户、一个进程等)由一张段表控制,每个程序段在段表中占一行。 



    l 段式虚拟存储器的主要优点如下:
      1、程序的模块化性能好。
      2、便于程序和数据的共享。
      3、程序的动态链接和调度比较容易。
      4、便于实现信息保护。在一般情况下,一段程序是否需要保护是根据这个段程序的功能来决定的。
    l 段式虚拟存储器的主要缺点是:
      1、地址变换所花费的时间比较长。从多用户虚地址变换到主存实地址需要查两次表,做两次加法运算。
      2、主存储器的利用率往往比较低。
      3、对辅存(磁盘存储器)的管理比较困难。磁盘存储器通常是按固定大小的块来访问的,如何把不定长度的程序段映象到固定长度的磁盘存储器中,需要做一次地址变换。 

    2、页式虚拟存储器

    l 程序按页(虚页)划分,贮存按页(实页)分配
    l 页面大小固定,一般指定为0.5KB的整倍数,通常为1KB至16KB。
    l与段式虚拟存储器相比,由于页长度固定,因此,不需要象段式虚拟存储器中的段长度这一字段,另外,主存地址这一字段只需要指出主存储器的页号,与段式虚拟存储器中的主存地址必须指出整个主存地址长度相比要节省很多。
    l 地址映像方法:




    4、外部地址变换

      前面介绍了内部地址映象和变换方法,即把虚拟地址空间映象到主存物理地址空间,以及把虚拟地址变换成主存实地址。当页表或段表中的有效位指示发生页面失效时,表示需要访问的那一页或那一个程序段还没有装入到主存储器中,这时必须进行外部地址变换。

    l  外部地址变换的目的是要找到辅存(磁盘存储器)的实地址,并且把需要访问的那一页或那一个程序段调入到主存储器中。
    l 外页表:因为它是在外部地址变换中使用的,与在内部地址变换中使用的页表被称为内页表相对应。
    l 磁盘存储器每一个物理块的大小是512字节。在页式和段页式虚拟存储器中,页面大小固定,通常是磁盘物理块的整数倍,段式虚拟存储器,在段表中有段长度,根据段长度和磁盘物理块大小就能计算出本次页面失效需要调入的磁盘存储器的物理块数。因此,在进行外部地址变换时只要给出磁盘存储器的起始地址,就能把一整页或一整个程序段调入主存中
    l    虚拟地址空间中的每一个页面或每一个程序段,在外页表中都有对应的一个存储字。在每一个存储字中除了必须有磁盘存储器的地址之外,至少还应该包括一个装入位。 

    四、页面替换算法

    l页面替换发生时间:当发生页面失效时,要从磁盘中调入一个页面到主存,如果主存中所有页面都已经被占用,必须从主存中淘汰掉一个已有页面,以便存放新调入页面。
    l 评价页面替换算法好坏的标准:命中率要高,算法要容易实现。
    l 目前。在虚拟存储器常用的页面替换算法有如下几种:

     1、随机算法,即RAND算法(Random algorithm)。
        利用软件或硬件的随机数发生器来确定主存储器中被替换的页面。这种算法最简单,而且容易实现。但这种算法完全没有利用主存储器中页面调度情况的历史信息,也没有反映程序的局部性,所以命中率比较低。
      2、先进先出算法,即FIFO算法(First-In First-Out algorithm)。
     这种算法选择最先调入主存储器的页面作为被替换的页面。它的优点是比较容易实现,能够利用主存储器中页面调度情况的历史信息,但是,没有反映程序的局部性。因为最先调入主存的页面,很可能也是经常要使用的页面。

      3、近期最少使用算法,LFU算法(LeastFrequently Used algorithm)。
        这种算法选择近期最少访问的页面作为被替换的页面。显然,这是一种非常合理的算法,因为到目前为止最少使用的页面,很可能也是将来最少访问的页面。该算法既充分利用了主存中页面调度情况的历史信息,又正确反映了程序的局部性。但是,这种算法实现起来非常困难。它要为每个页面设置一个很长的计数器,并且要选择一个固定的时钟为每个计数器定时计数。在选择被替换页面时,要从所有计数器中找出一个计数值最大的计数器。因此,通常采用另外一种变通的办法,就是下面的LRU算法。
      4、最久没有使用算法,LRU算法(LeastRecently Used algorithm)。
        这种算法把近期最久没有被访问过的页面作为被替换的页面。它把LRU算法中要记录数量上的""""简化成判断"""",因此,实现起来比较容易。

      5、最优替换算法,OPT算法(OPTimal replacemant algorithm)。
        上面介绍的几种页面替换算法主要是以主存储器中页面调度情况的历史信息为依据的,它假设将来主存储器中的页面调度情况与过去一段时间内主存储器中的页面调度情况是相同的。显然,这种假设不总是正确的。最好的算法应该是选择将来最久不被访问的页面作为被替换的页面。这种替换算法的命中率一定是最高的。这就是最优替换算法,简称OPT算法。
       要实现OPT算法,唯一的办法是让程序先执行一遍,记录下实际的页地址流情况。根据这个页地址流才能找出当前要被替换的页面。显然,这样做是不现实的。因此,OPT算法只是一种理想化的算法,实际上,经常把这种算法用来作为评价其它页面替换算法好坏的标准。在其它条件相同的情况下,哪一种页面替换算法的命中率与OPT算法最接近,那么,它就是一种比较好的页面替换算法。

    l 虚拟存储器中,实际上可能采用的只有FIFOLRU两种算法。

    例1:一个程序共有5个页面组成,分别为P1~P5。程序执行过程中的页地址流(即程序执行中依次用到的页面)如下:P1,P2,P1,P5,P4,P1,P3,P4,P2,P4,假

    设分配给这个程序的主存储器共有3个页面。图中,用"*"号标记下次将要被替换掉的页面。


    就本例而言,FIFO命中次数2次,命中率Hp=2/10=0.2

                LRU命中次数4次,命中率Hp=4/10=0.4

                OPT命中次数5次,命中率Hp=5/10=0.5

      假设每个数据平均被访问30次,为了使LRU算法的失效率小于10-5,页面应该至少多大?

       (1-Hp)/n =(1-0.4)/30P <10-5  

        解得P>2000字,页面大小应该为2K字

    l FIFO算法的命中率最低,LRU算法的命中率与OPT算法很接近。这一结论具有普遍意义。因此,在实际使用中,LRU算法是一种比较好的算法。目前,许多机器的虚拟存储器都采用LRU算法。

    五、影响主存命中率的因素

    l 影响主存命中率的主要因素有如下几个:
        1、程序在执行过程中的页地址流分布情况。
        2、所采用的页面替换算法。
        3、页面大小。
        4、主存储器的容量
        5、所采用的页面调度方法
    l 页地址流的分布情况是由程序本身决定的,系统设计人员一般无能为力。
    l 页面替换算法,目前多数机器都采用LRU算法。它是一种堆栈型算法。在当前看来,已经是一种比较好的算法了。
    l 存储区域保护:对于非虚拟存储器,采用界限寄存器方式;对于虚拟存储器,采用页表保护、键式保护等。
    l页表保护:虚拟存贮器系统本身固有的保护机能为了更便于实现这种保护,还可在段表中的每行内,不仅设置页表起点,还设置段长(页数)项。若出现该段内的虚页号大于段长,则可发越界中断。
    l键方式由操作系统按当时主存的使用分配状况给主存的每页配一个键, 称为存贮键,所有页的存贮键存在主存相应的快速寄存器内,每个用户(任务)的各实页的存贮键都相同。为了打开这把锁,需要有把“钥匙”,称为访问键。 每个用户的访问键由操作系统给定,存在处理机的程序状态字(PSW)或控制寄存器中。程序每次访问主存前,要核对主存地址所在页的存贮键是否与该程序的访问键相符,只有相符,才准访问。
    l  对正在执行的程序本身保护:环状保护
    l 访问方式的限制(保护):对主存信息的使用可以有读(R)、写(W)和执行(E)3种方式。 “执行”指的是作为指令来用。相应的就有R、W和E访问方式保护。 


    展开全文
  • 试比较虚拟存储器和Cache

    相同点

    • 最终目标都是为了提高系统性能,二者都有容量、速度、价格的梯度。
    • 都把数据划分为小信息块,并作为基本的传递单位,虚存系统的信息块更大。
    • 都有地址的映射、替换算法、更新策略等问题。
    • 依据程序的局部性原理应用“快速缓存的思想”,将活跃的数据放在相对高速的部件中。

    不同点

    • Cache主要解决系统速度问题,虚拟存储器却是为了解决主存容量问题。
    • Cache全由硬件实现,是硬件存储器,对程序员透明;虚拟存储器由OS和硬件共同实现,是逻辑上的存储器,对系统程序员不透明,对应用程序员透明。
    • 对于不命中性能的影响,由于CPU速度大约是Cache的10倍,主存速度大约是硬盘的100倍,因此虚拟存储器系统不命中时对系统性能影响更大。
    • CPU与Cache和主存都建立起了直接访问的通路,而辅存与CPU没有直接通路。Cache不命中时主存能与CPU直接通信,从而将数据调入Cache;虚拟存储器系统不命中时,只能先由硬盘调入主存,而不能直接和CPU进行通信。
    展开全文
  • 对于虚拟存储器的原理,以及分页虚拟存储管理方式,分段虚拟存储管理进行了详细的介绍!

    目录:

    一、概述:

    局部性原理:

    虚拟存储器:

    二、分页虚拟存储管理方式 :

    基本原理:

    缺页中断机构:

    地址变换机构:

    页面置换算法:   

    内存分配策略与分配算法:

    调页策略:

    抖动问题:

    三、分段虚拟存储管理:

    基本原理:

    缺段中断机构:

    段的动态链接:

    段的共享:


    一、概述:

    什么是虚拟存储器?

    虚拟存储器就是使用虚拟技术逻辑上对存储器进行扩充

     

    那么为什么要引入虚拟存储器?

     

    在回答这个问题之前,我们先介绍一个定理——局部性原理!

     

    局部性原理:

    一次性驻留性严重地降低内存的利用率,显著地减少了系统吞吐量 !

    ——一次性:程序在运行时一次性装入内存中。

    ——驻留性:程序一旦装入内存之后便一直驻留到程序运行结束;或者是因I/O而长期等待,又或者是运行一次之后,就不再需要运行了;但是它们将占据着宝贵的内存资源。

     

    研究表明,程序在执行过程中呈现局部性原理(体现在时间和空间两方面)。

     

    ——时间局部性:一条指令被执行后,那么它可能很快会再次被执行(循环结构)  。

    ——空间局部性:若某一存储单元被访问,那么与该存储单元相邻的单元可能也会很快被访问(顺序结构)。

     

    局部性原理使得虚拟存储技术的实现成为可能;一个程序特别是一个大型程序的一部分装入内存是可以运行的

     


    虚拟存储器:

    虚拟存储器定义:

    ——所谓虚拟存储器,是指仅把作业的一部分装入内存便可运行作业的存储器系统

    ——具体地说,所谓虚拟存储器是指具有请求调入功能置换功能,能从逻辑上对内存容量进行扩充的一种存储器系统。

    ——虚拟存储器并非可以无限大,其容量受外存大小和指令中地址长度两方面的限制。

     

    虚拟存储器的特征:

    ——可以把一个程序分多次装入内存,每次仅装入当前运行需要使用的部分——多次性

    ——在程序执行过程中,可以把当前暂不使用的部分换出内存,若以后需要时再换进内存——交换性/非驻留性

    ——程序在内存中不必连续存放——离散性

    ——虚拟存储器还有一个最重要的特征——虚拟性,从逻辑上扩充内存容量,使用户所看到的内存容量远大于实际内存容量。

     

    二、分页虚拟存储管理方式 :

    基本原理:

    ——分页虚拟存储管理方式是在分页系统的基础上,增加了请求调页功能页面置换功能所形成的虚拟存储器系统。

    ——在分页虚拟存储管理时使用的页表,是在原来页表的基础上发展起来的,包括以下内容:物理块号、状态位、访问位、修改位、外存地址

    • 状态位:表示该页是否已经调入内存。
    • 访问位:表示该页在内存期间是否被访问过。
    • 修改位:表示该页在内存中是否被修改过。若未被修改,则在置换该页时就不用将该页写回到外存中,减少系统的开销和启动磁盘的次数;若被修改,则在置换该页时就必须将该页写回到外存中,以保证外存中所保留的数据始终是最新的副本。
    • 外存地址:用于指出该页在外存上的地址,通常是物理块号,供调入该页时使用。

    缺页中断机构:

    每当要访问的页面不在内存时,便产生一缺页中断,请求操作系统把所缺页面调入内存。缺页中断作为中断,它同样需要经历诸如保护CPU现场环境、分析中断原因、转入缺页中断处理程序进行处理、恢复CPU环境等几个步骤。

    缺页中断与与一般的中断的区别:

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

    ——一条指令在执行期间,可能产生多次缺页中断

    个人理解:因为虚拟存储技术,使得程序不再是一次性全部调入内存中,所以在执行的时候才知道所用的页面是否已在内存中,若不在则需要操作系统把它调进内存,可能恰逢多个页面不在内存中,所以可能会缺页中断多次。)

    缺页中断处理

    地址变换机构:

    从总体来说:分页存储管理方式中的地址变换机构的基础上增加了产生和处理缺页中断,以及从内存中换入换出一页等功能

    具体过程:

    ——当用户进程要求访问某一页时,如果该页已经调入内存中,那么按照分页存储管理方式中的地址变换过程转换地址;如果该页还没有调入内存,则产生一个缺页中断,系统进入相应的缺页中断处理过程。

     

    具体的换入过程如下(即中断处理过程):

    ——保存当前进程的CPU现场,从辅存中找到该页。

    ——查看当前内存是否有空闲块调入该页,如果有则启动I/O,将该页由辅存调入内存,同时修改页表,再按分页存储管理方式的地址变换过程转换地址;如果内存已满,则按照某种算法选择一页作为淘汰页调出,腾出空间后再调入。当然如果被淘汰的页在内存中已经被修改过,则需将该页写回辅存。

    ——恢复当前进程的CPU现场。

     


    页面置换算法:   

    如果内存空间己被装满而又要装入新页时,必须按某种算法将内存中的一些页淘汰出去,以便调入新页,这个工作称为“页面置换”。选择被淘汰页的方法称为页面置换算法。

    最佳置换算法(OPT:optimal):(个人理解:条件过于理想化,仅仅作为作为一种标准!)

    ——算法:淘汰那些以后永不使用,或者是在最长时间内不再被访问的页。

    ——无法实现的,只能作为其它置换算法的衡量标准

    先进先出算法(FIFO:first in first out) :(个人理解:实现简单,但是进出的时机和使用的时机不一定匹配!)

    ——算法:每次淘汰最先进入内存的页。

    ——优点:简单,易于实现。

    ——缺点:效率不高,可能产生“抖动”现象。

    “抖动”现象:进程的运行将很频繁地产生缺页中断,这种频率非常高的页面置换现象称为抖动。对刚被替换出去的页,立即又要被访问。需要将它调入,因无空闲内存又要替换另一页,而后者又是即将被访问的页,于是造成了系统需花费大量的时间忙于进行这种频繁的页面交换,致使系统的实际效率很低,严重导致系统瘫痪,这种现象称为抖动现象。(来源自百度百科)

    最近最久未使用(LRU:least recently used)算法:

    ——算法:淘汰那些在最近一段时间里最久未被使用的一页。

    ——LRU算法是较好的一个算法,但是开销太大,要求系统有较多的支持硬件(移位寄存器或栈)。

    (个人理解:片面的讲,这个算法就像打着先进先出算法的底子,但是通过使用频率来调整其淘汰顺序。)

    实现方案:

    ——栈式算法:在内存维护一张进程所有页的链表,表中各项按访问时间先后排序最近访问的页排在表头,最久末用的页排在表尾。每当要置换一页时,必须对链表中的各项进行修改。

    改进使用链表时费时方法,可使用一个特殊硬件实现LRU:

    (1)系统为每个在内存中的页面配置一个移位寄存器,可表示为:R=Rn-1Rn-2…R3R2R1 ;当进程访问某页时,便将相应的寄存器的最高位(Rn-1)置1;定时信号将每隔一定时间将寄存器右移一位。        具有最小数的寄存器所对应的页面,就是最近最久未使用的页。

    (2)利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时,便将该页面的页面号从栈中移出,将它压入栈顶。  栈底就是最近最久未使用页面的页面号。

     

    简单Clock置换算法(最近未使用算法NRC):

    ——算法:每页设置一个访问位,置换算法在选择一页淘汰时,只须检查其访问位,如果是0,就选择该页换出;若为1,则重新将它复0 ,检查下一个页面。当检查到队列中的最后—个页面时,若其访问值仍为1、则再返回到队首再去检查第一个页面。

    ——该算法只能考虑该页面是否被访问过

    置换流程

    改进型Clock置换算法:

    ——算法:除了考虑到页面的使用情况外,还增加了置换代价,选择换出页面时,既要是未使用过的页面,又要是未被修改过的页面把同时满足两条件的页面作为首选被淘汰的页。(如果被淘汰的页在内存中已经被修改过,则需将该页写回辅存,增加了系统的开销。)

    ——该算法与简单Clock算法比较,可减少磁盘的I/O操作次数 ,但实现该算法本身的开销将有所增加。

    具体算法:访问位A和修改位M可以组合成4种类型的页面

    • 1类(A=0,M=0),表示该页最近既没有被访问、又没有被修改,是最佳淘汰页
    • 2类(A=0,M=1),表示该页最近末被访问,但已被修改。并不是很好的淘汰页。
    • 3类(A=l,M=0),最近已被访问,但未被修改,该页有可能再被访问。(因为局部性原理所以可能再被访问!)
    • 4类(A=1,M=1),最近已被访问且被修改,该页可能再被访问。(因为局部性原理所以可能再被访问!)

    执行过程:

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

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

    • (页面的访问位置0——为的是将3类和4类转变成我们想要淘汰的1类、2类;要不然当循环队列里面找不到1类和2类页面时,就会陷入无页面可淘汰的局面;所以这步操作是为了打破僵局,不得不淘汰一个3类或者4类页面了!)

    ③如果第二步也失败,即未找到第二类页面,则将指针返回到开始的位置,并将所有访问位置0。然后,重复第一步,如果仍失败,必要时再重复第二步。


    内存分配策略与分配算法:

    最小物理块数:

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

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

     

    物理块的分配策略:

    固定分配局部置换:(个人理解:大小分配固定,需要交换时内部自调整,对于大小卡的过于死板,大小分配不可能让所有进程满意。)

    ——基于进程的类型或根据程序员的建议,为每个进程分配一定数量的物理块,在整个运行期间都不再改变

    ——如果进程在运行期间发现缺页,则只能在该进程在内存的n个页面中选出一页换出,然后再调入一页,保证分配给该进程的物理块数保持不变

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

    可变分配全局置换:(个人理解:先对每一个进程固定分配,但是保留一个空闲空间,谁缺给谁,当用完还缺时,再从整体层面上抽取一页进行调出。但是给的过于土豪,抽调的过于随机,对于当前缺页的进程对于空闲空间的索取没有加以限制,不是很好!一个“人”的放纵却要集体承担。)

    ——先为系统中的每个进程分配一定数量的物理块,而操作系统本身也保留一个空闲物理块队列

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

    ——凡产生缺页的进程,都将获得新的物理块

    ——仅当空闲物理块队列中的物理块用完时,操作系统才从内存中选择一页调出,该页可能是系统中任一进程的页会使被淘汰页的那个进程的物理块数减少,进而使其缺页率增加

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

    可变分配局部置换:(个人理解:当缺页了,先自己内部解决,自己解决及其吃力,再系统插手救济一下,系统怎么知道你吃力,通过看你的缺页率!当然要是你内部压力很小,自己过得很富足,就给你放放血。整体来讲就是——“劫富济贫”)

    ——进程的类型或根据程序员的要求,为每个进程分配一定数目的物理块;但当某进程发生缺页时,只允许从该进程在内存的页面中选出一页换出

    ——如果进程在运行中频繁地发生缺页中断,则系统须再为该进程分配若干附加的物理块,直至进程的缺页率减低到适当程度为止;反之,若一个进程在运行过程中的缺页率特别低,则此时可适当减少分配给该进程的物理块,但不应引起其缺页率的明显增加。

     

    物理块分配算法:(以固定分配策略举例,在内存容量和进程数量确定的条件下)

    平均分配算法:

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

    ——这个算法看似公平,但是没有考虑到进程之间大小的差异;对于较大的进程,可能会经常发生缺页中断。

    按比例分配算法:

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

    ——如果系统各进程页面数总和为S,又假设m为内存空间可用物理块数,则分配给进程Pi的物理块数ai为:ai = si/S x m(ai应取整,而且必须大于最小物理块数。)

    考虑优先权的分配算法:

    ——即根据进程的优先级别比例分配内存物理块。


    调页策略:

    请求调页策略:(个人理解:有就用,没有就调进来)

    ——当缺页中断发生时进行调度,即当访问某一页面而该页面不在内存时由操作系统将其调入内存

    预调页策略:(个人理解:从本质上就是我预判了你的下一步动作,准不准就不能完全保证了;实际上是对于局部性原理的实际运用。)

    ——也称先行调度,是当缺页中断发生前进行调度,即当一个页面即将被访问之前就将其调入内存

    ——预调页可以节省进程因缺页中断而等待页面调入的时间。

    ——注意:

    • 预调页不一定是百分之百准确的。也就是说,预先调入的页面可能未被用到,仍然会发生缺页中断。
    • 该策略的开销较大,一般用于进程的首次调入时。

    抖动问题:

    什么是抖动?

    进程的大部分时间,都用于页面的换进换出,而几乎不能再去做任何有效的工作,从而导致发生处理机利用率急剧下降,而趋于零的现象,我们称此时系统处于抖动状态。

    产生抖动的原因:

    产生抖动的根本原因是——系统中进程的数量太多,因此分配给每个进程的物理块数量太少,使得每个进程在运行时频繁的发生缺页中断

     

    根据局部性原理,在一定的时间内,进程对于页面的访问是局限在一部分页面的。根据此特征,研究人员进一步提出了工作集的理念。

     

    工作集:

    所谓工作集就是指在某段时间间隔∆内进程访问页面的集合。为了使进程有较低的缺页率,应在该段时间内把进程的全部工作集装入内存中

     

    预防抖动的方法:

    ——采用局部置换策略:(个人理解:起到一种“隔离”的效果。)

    • 当某个进程发生缺页时,只能在自己的自己的内存空间发生置换,不允许从其他进程获得新的物理块,这样该进程发生了抖动也不会影响其他进程的运行,不会引起其他进程的抖动,使得抖动限制在一个较小的范围内
    • 优点:简单易行。
    • 缺点:并未消除抖动,在一些进程发生抖动的时候会长时间处于磁盘I/O的等待队列中,使得队列长度增加,延长了其他进程的缺页处理时间,进而使得平均缺页处理时间延长,延长了有效访问时间。(个人理解:对其置之不理,它就会拖慢整个进度。)

    ——利用工作集算法防止抖动:

    • 当调度程序发现处理机的利用率较低时,便从外存中调入一个新的程序进入内存,以提高处理机的利用率。
    • 引入工作集算法的目的在于——在新的程序调入内存之前,必须先检查此时内存中各个进程在内存中驻留页面是否足够多。如果足够多,则新进程的调入就不会导致缺页率的增加,此时便可以调新的程序进入内存中;如果此时有些进程的内存页面不足,则首先为那些进程分配新的物理块以降低其缺页率,而不是调入新的程序。

    (个人理解:这一段冗长的话的意思就是,先满足已经在内存中进程的可能调用需求,再尝试调入新的进程,不然的你这不是添堵嘛!

    ——利用“L=S”准则调节缺页率:

    “L=S”准则:

    • L:缺页之间的平均时间(换句话说就是平均的缺页中断时间);S:平均缺页服务时间(换句话说就是从磁盘中载入页面的平均时间)。
    • 当L>S时:很少缺页,磁盘能力没有被充分利用。
    • 当L<S时:频繁缺页,超过磁盘的处理能力。
    • 调整并发程序度,使得 L ≈ S ;这种情况下,磁盘和处理机到可以达到最佳利用率。

    (个人理解:类似于两者之间同步了,你中断的时间,我差不多刚好可以将你缺页调进来!)

    ——挂起某些进程:

    • 挂起一个或者几个进程,腾出内存空间供缺页率较高的进程使用,从而达到预防或者消除抖动的目的。

    习题举例:

    设某计算机的逻辑地址空间和物理地址空间均为64KB,按字节编址。若某进程最多需要6页数据存储空间,页的大小为1KB。操作系统采用固定分配局部置换策略为此进程分配4个物理块,如表1所示。当该进程执行到时刻260时,要访问逻辑地址为17CAH的数据,请问答下列问题。

    1) 该逻辑地址对应的页号是多少?

    (2) 若采用先进先出(FIFO)置换算法,该逻辑地址对应的物理地址是多少?(要求给出计算过程)

    (3) 若采用简单CLOCK置换算法,该逻辑地址对应的物理地址是多少?要求给出计算过程。(设搜索下一页的指针沿顺时针方向移动,且当前指向2号物理块,如下图所示。)

    解:17CAH转换为二进制数为0001 0111 1100 1010

    (1)页大小为1K,所以页内偏移地址为10位,于是前6位是页号,故页号为5。

    (2)FIFO,被转换的页面所在的物理块为7,所以对应的物理地址为(0001 1111 1100 1010)2=1FCAH       

    (3)Clock,被转换的页面所在的物理块为2,所以对应的物理地址为(0000 1011 1100 1010) 2=OBCAH 

     

    三、分段虚拟存储管理:

    基本原理:

    ——分段虚拟存储管理原理同分页虚拟存储管理原理一样,在程序运行前,不必调入所有分段,只需先调入若干个分段便可启动运行。当所访问的段不在内存中时,可请求操作系统将所缺的段调入内存

    ——分段虚拟存储管理中的段表包括:段名、段长、段的基址、存取方式、访问位、修改位、存在位、增补位和外存地址。

     

    缺段中断机构:

    ——在分段虚拟存储管理系统中,如果访问的段不在内存中,系统将产生一个缺段中断,请求操作系统将该段调入到内存

    ——缺段中断和缺页中断一样 ,但段是信息的逻辑单位,所以不可能出现一条指令和一组信息被分割在两个段里的情况

    缺段中断处理过程

     

    段的动态链接:

    ——在程序运行之前,所有的程序模块必须由系统的连接装配程序进行链接和重定向,进行静态链接。但是它既费时又费力,有时链接好的模块在程序运行中根本不用。造成了时间和空间上的浪费。

    ——最好的方法就是不事先做链接工作,把它推迟到程序运行过程中运行,需要哪一段,才把那一段链接到程序地址空间中,实现运行时的动态链接方法

    ——在分段虚拟存储管理中,每个程序模块构成独立的分段,且地址空间是二维的,因而为实现动态链接创造了条件

     

    段的共享:

    ——利用段的动态链接很容易实现段的共享一个共享段在不同作业中可具有不同的段号

    ——设立一张共享段表对段的共享进行集中管理

    共享段表项

    ——可重入代码又称为“纯代码” 是一种允许多个进程同时访问的代码。为了使各个进程执行的代码完全一样,绝对不允许可重入代码在执行中有任何改变。为每个使用改代码的进程配一个局部数据区,把在执行中可能改变的部分复制到该数据区。这样程序在执行时,只对该数据区中属于该进程私有的内容进行修改,并不修改共享代码的内容,这时共享代码就变成了可重入代码。

    共享段示意图

     

    Ending... ...

    展开全文
  • 本文研究了虚拟存储器的功能、管理方式、基本工作原理、虚拟存储器地址映象和地址变换、替换算法和虚拟 存储器实现中的问题。
  • 文章目录5.1 虚拟存储器概述5.1.1 常规存储管理方式的特征和局部性原理5.1.2 虚拟存储器的定义和特征5.1.3 虚拟存储器的实现方法5.2 请求分页存储管理方式5.2.1 请求分页中的硬件支持5.2.2 请求分页中的内存分配...
  • 3.7.1虚拟存储器概念 3.7.2页式存储器 主存和Cache之间是分块映射存储,同样,利用局部性原理,也可以将主存和辅存之间进行分块映射存储。 举个粒子,假如现在使用微信文字聊天,该部分程序占用大小了4KB空间,...
  • 虚拟存储器的基本概念 虚拟存储器将主存或辅存的地址空间统一编址,形成一个庞大的地址空间,用户可以在里面进行自由编址,而不需要在乎实际的主存容量和程序存放的位置 虚拟地址比实际地址大 过程 CPU使用虚地址...
  • 虚拟存储器 || 分页 把 地址空间 和 主存容量 概念区分开来。程序员在地址空间里编写程序,而程序则在真正内存中运行。由一个专门机制实现地址空间和实际主存之间映射。 || 虚拟存储系统基本概念 虚拟存储...
  • 虚拟存储器的引入 1.常规存储器管理方式的特征: ●一次性、驻留性 ●情况一:内存空间装不下的大作业无法运行 ●情况二:作业量大时,无法允许更多的作业并发 ●扩充内存容量的方法:物理上、逻辑上 2.局部性原理: ●...
  • 3.7.1 虚拟存储器的基本概念 虚拟存储器的使用 物理内存容量有限,难以满足实际使用的需要; 利用辅存空间,将数据在辅存与主存之间调度; 用户实际访问的仍然是主存,利用辅存的部分空间保存暂时不用的主存内的数据...
  • 建议将思维导图保存下来观看,或点击这里在线观看
  • 也可以运行,采用虚拟技术。...根据局部性原理,就可实现虚拟技术。就可以解决即使装不下也可以运行程序。将虚拟技术和分页存储管理结合起来。只有部分页在内存当中。那么cpu取某页数据时就出现了下图步骤。 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 659
精华内容 263
关键字:

虚拟存储器的原理