1、2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器1操作系统 2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器2 5.1 虚拟存储器的基本概念2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器3简单存储器的特征一次性：作业在运行前一次性地装入内存驻留性：作业装入内存后，便一直驻留在内存直至作业运行结束2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器4 简单存储器管理方式，都要求将一个作业全部装入内存方能运行。于是出现以下两种情况：有的作业很大，所要求的内存空间超过了内存的总容量；有大量的作业要求
2、运行，但由于内存容量不足，难以容纳所有的作业。2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器5虚拟存储器的引入可以从两个方面解决上述问题：1）从物理上增加内存容量；2）从逻辑上扩充内存的容量。2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器6一次性及驻留性带来的问题:会使许多在进程运行时不用的或暂时不用的程序（数据）占据大量的内存空间;使一些需要运行的作业无法装入运行。我们现在要研究的问题是：一次性及驻留性是否是程序运行时所必需的？2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器7局部性原理问题的提出(P.Denn
3、ing)程序在执行时将呈现出局部性规律，即在一较短时间内，程序的执行仅限于某个部分；相应地，它所访问的存储空间也局限于某个区域。2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器8局部性的表现方式时间局部性：一个数据结构被访问，不久可能再次被访问。典型原因：程序中存在大量的循环操作空间局部性：一段时间访问的地址可能集中在一定范围。典型原因：程序顺序执行2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器9虚拟存储器定义什么是虚拟存储？定义：具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。它把内存与外存有机结合起来使用，构成
4、容量很大的“内存”。2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器10虚拟存储器定义 实现思想：当进程运行时，先将一部分程序装入内存，另一部分暂时留在外存，当要执行的指令不在内存时，由系统自动将它们从外存调入内存。2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器11实现虚拟存储的一般过程进程运行之前，将部分页面（段）调入内存，其他部分放在外存。进程运行时，如果它所访问的页面（段）在内存中，则继续运行。2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器12实现虚拟存储的一般过程如果所访问的页面（段）不在内存，则发生缺页
5、（段）中断，进程阻塞。系统启动请求调页（段）功能，将所需页面（段）调入内存。如果内存已满，需要运用交换技术，腾出空间之后将所需页（段）调入，继续运行。2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器13实现虚拟存储的典型过程2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器14虚拟存储器的技术支持虚拟存储器管理的技术支持必须有相应的硬件支持，用以实现虚拟分页和虚拟分段存储管理；操作系统必须提供相应的软件支持，管理页或段在内存和外存之间的移动。2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器15虚拟存储器实现请求分页系统
6、在简单分页基础上，增加了请求调页功能、页面置换功能。置换时以页面为单位进行系统提供的硬件支持：l请求分页的页表机制；l缺页中断机构；l地址变换机构。2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器16虚拟存储器实现请求分段系统在分段的基础上，增加了请求调段功能、分段置换功能置换时以段为单位进行系统提供的硬件支持：l请求分段的段表机制；l缺段中断机构；l地址变换机构。2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器17虚拟存储器实现段页式系统在段页式的基础上，增加了请求调页功能、页面置换功能Intel 80386支持段页式虚拟存储2022年年1
7、2月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器18虚拟存储器特征离散性：指在内存分配时采用离散分配方式，离散性是其它特征的基础。多次性：指一个作业被分成多次调入内存运行。2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器19虚拟存储器特征对换性：指允许在作业的运行过程中换入、换出。虚拟性：指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。这是虚拟存储器表现出的最重要特征。2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器20虚拟存储器特征虚拟存储器带来的好处 更大，可以运行大程序，包括超过内存实际容量大小的程序
8、更多，可以在有限的物理内存中运行更多的程序。2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器215.2 请求分页存储管理 2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器22 建立在简单分页存储管理之上，是目前比较常用的一种虚拟存储管理技术.2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器23硬件支持页表机制在请求分页系统中所需要的主要数据结构，仍是页表。基本作用：将用户地址空间中的逻辑地址变换为内存空间的物理地址。请求分页系统中的每个页表项如下图所示：物理物理块号块号状态状态位位 P访问字访问字段段 A修改修改位位
9、 M外存外存地址地址2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器24硬件支持缺页中断机构与一般中断相同的处理步骤：保护CPU环境、分析中断原因、转入中断处理程序进行处理、恢复CPU环境等步骤。缺页中断和一般的中断相比有如下区别：在指令的执行期间产生和处理中断信号；一条指令在执行期间，可能产生多次缺页中断2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器25缺页中断机构页面B：A：654321指令copy ATO B2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器26硬件支持对硬件的要求 系统中的硬件机构应能够保存多
10、次中断时的状态，并保证最后能返回到中断前产生缺页中断的指令处，继续执行。2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器27硬件支持地址变换机构请求分页系统中的地址变换机构，是以简单分页系统的地址变换机构为基础，再为实现虚拟存储器而增加了某些功能所形成的。如产生和处理缺页中断，以及从内存中换出一页的功能等2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器28硬件支持地址变换过程首先去检索快表，试图从中找到访问的页；如果从快表中找到所要访问的页，则修改页表项中的访问字段；如果是写操作，则应将修改位置“1”。然后利用页表项中给出的物理块号和页内地址
11、，形成物理地址。地址变换到此结束。2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器29如果在快表中未找到该页的页表项，则应再到内存中去查找页表，再从找到的页表项中的状态位P，来了解该页是否已调入内存。其结果可能是：l 该页已调入内存：将页表项写入快表。l 该页尚未调入内存:产生缺页中断，请求OS调页。2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器30越界中断越界中断2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器31页面分配为进程分配物理块时要考虑的问题：最少物理块数的确定；物理块分配策略；物理块分配算法。2022
12、年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器32页面分配最小物理块数是指能保证进程正常运行所需最小物理块数。与计算机的硬件结构有关。2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器33页面分配页面分配和置换策略采取两种分配策略，即固定和可变分配策略。采取两种置换策略，即全局置换和局部置换。2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器34页面分配固定分配局部置换为每个进程分配固定页数的内存空间，整个运行期间不再改变。如果在运行中发现缺页，则只能从该进程在内存的固定页面中选出一页换出，然后再调入一页。2022年年12月月
13、16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器35页面分配难点为每个进程分配多少个页面难以确定。太少，频繁缺页中断，降低系统吞吐量。太多，内存驻留进程减少，可能造成资源空闲。2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器36页面分配可变分配全局置换先为系统中的每个进程分配一定数目的物理块，而OS自身也保持一个空闲物理块队列。当某进程发现缺页，由系统从空闲的物理块队列中，取出一物理块分配该进程，并将欲调入的缺页装入其中。当空闲物理块用完时，OS从内存中任选一页调出（任意进程）。2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器37页面分
14、配可变分配局部置换根据进程的类型或程序员的要求，为每个进程分配一定数目的内存空间。当某进程发生缺页时，只允许从该进程在内存的页面中选出一页换出，这样就不会影响其它进程的运行。如果进程在运行中频繁地发生缺页中断，则系统再为该进程分配附加的物理块；反之，若一个进程在运行中缺页率低，则此时适当减少分配给该进程的物理块。2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器38页面分配物理块分配算法平均分配算法：物理块平均分配给各进程；按比例分配算法：按进程大小的比例分配物理块；（系统中共n个进程，每个进程页面数Si，系统中可用物理块数m）niiss1mssbii2022年年12月
15、月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器39考虑优先权的分配算法：按照作业的重要性、紧迫性进行分配。一般将可供分配的物理块分为两部分：一部分按比例分配；另一部分按优先权适当增加份额。页面分配页面分配2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器40页面调入策略解决应从何时调入页面和从何处调入页面的问题！应从何时调入页面l预调页策略：一次调入若干相邻的页特点：若局部性很差，预先调入的页面并不会很快被使用，反而占据了内存空间，降低了系统效率。目前预调页的成功率仅有50%。主要用于进程的首次调入。2022年年12月月16日星期五日星期五第五章第五章 虚拟存
16、储器虚拟存储器41页面调入策略l请求调页策略：进程在运行时，发现其所访问的程序页面不在内存，请求系统将所需页面调入内存。特点：每次仅调入一页，增加磁盘I/O启动频率，系统开销大；易实现。虚拟存储器大多采用此策略。2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器42页面调入策略应从何处调入页面 系统有足够的存储空间，这时可以全部从对换区调入所需页面，以提高调页的速度。系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；但对于那些可能被修改的部分，在将它们换出时，便须调到对换区，以后需要时再从对换区调入。2022年年12月月16日星期五日星期五第五章第
17、五章 虚拟存储器虚拟存储器43UNIX方式，凡是未运行过的页，都应从文件区调入。对于曾经运行过而又被换出的页面，从对换区调入。2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器44页面调入过程缺页中断处理程序通过查找页表，得到该页所在外存地址。如果此时内存空闲，能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器45如果内存已满，则须先按照某种置换算法，从内存中选出一页准备换出；如果该页未被修改过，可不必将页写入磁盘；但如果该页已被修改，则必须将它重新写入磁盘，然后再将缺页调入内存，并修
18、改页表中的相应表项，再将此页表项写入快表中。据修改后的页表形成去访问数据的物理地址。2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器46页面调入策略缺页率假设进程在运行过程中，访问成功的次数为S，访问页面失败的次数为F,则缺页率为：f=F/(S+F)页面大小进程所分配物理块数页面置换算法程序固有特性2022年年12月月16日星期五日星期五第五章第五章 虚拟存储器虚拟存储器47有一矩阵“int A100100”以行优先进行存储。采用虚拟存储系统，物理内存共有3页，其中一页存放程序，其余2页存放数据。假设程序已在内存中占一页，其余2页空闲。for(int i=0;i99;i+)for(int j=0;j99;j+)Aij=0;若每页可存放200个整数，程序在执行过程各会发生多少次缺页？如果矩阵以列优先进行存储呢？
