|
|
|
在前面介绍的存储管理方案中，必须为每个作业分配足够的空间，以便装入全部信息。当主存空间不能满足作业要求时，作业无法装入主存执行。
|
|
|
|
如果一个作业只部分装入主存便可开始启动运行，其余部分暂时留在磁盘上，在需要时再装入主存，这样可以有效地利用主存空间。从用户角度看，该系统所具有的主存容量将比实际主存容量大得多，人们把这样的存储器称为虚拟存储器。虚拟存储器是为了扩大主存容量而采用的一种设计方法，其容量是由计算机的地址结构决定的。
|
|
|
|
|
|
早在1968年P.Denning就指出，程序在执行时将呈现出局部性规律，即在一段时间内，程序的执行仅局限于某个部分。相应地，它所访问的存储空间也局限于某个区域内。程序的局限性表现在时间局限性和空间局限性两个方面。
|
|
|
|
（1）时间局限性是指如果程序中的某条指令一旦执行，则不久的将来该指令可能再次被执行；如果某个存储单元被访问，则不久以后该存储单元可能再次被访问。产生时间局限性的典型原因是在程序中存在着大量的循环操作。
|
|
|
|
（2）空间局限性是指一旦程序访问了某个存储单元，则在不久的将来，其附近的存储单元也最有可能被访问。即程序在一段时间内所访问的地址可能集中在一定的范围内，其典型原因是程序是顺序执行的。
|
|
|
|
|
|
虚拟存储器是具有请求调入功能和置换功能，能仅把作业的一部分装入主存便可运行作业的存储器系统，是能从逻辑上对主存容量进行扩充的一种虚拟的存储器系统。其逻辑容量由主存和外存容量之和以及CPU可寻址的范围来决定，其运行速度接近于主存速度，成本也下降。可见，虚拟存储技术是一种性能非常优越的存储器管理技术，故被广泛地应用于大、中、小型机器和微型机中。虚拟存储器的实现主要有如下3种方式：
|
|
|
|
（1）请求分页系统。该系统是在分页系统的基础上增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。它允许只装入若干页的用户程序和数据（而非全部程序）就可以启动运行，以后再通过调页功能和页面置换功能陆续把将要使用的页面调入主存，同时把暂不运行的页面置换到外存上，置换时以页面为单位。
|
|
|
|
（2）请求分段系统。该系统是在分段系统的基础上增加了请求调段和分段置换功能所形成的段式虚拟存储系统。它允许只装入若干段的用户程序和数据就可以启动运行，以后再通过调段功能和置换功能将不运行的段调出，同时调入将要运行的段。注意：置换时以段为单位。
|
|
|
|
（3）请求段页式系统。该系统是在段页式系统的基础上增加了请求调页和页面置换功能所形成的段页式虚拟存储系统。
|
|
|
|
|
|
请求分页是在纯分页系统的基础上增加了请求调页功能、页面置换功能所形成的页式虚拟存储系统，它是目前常用的一种虚拟存储器的方式。
|
|
|
|
请求分页的页表机制是在纯分页的页表机制上形成的，由于只将应用程序的一部分调入主存，还有一部分仍在磁盘上，故需在页表中再增加若干项（如状态位、访问字段和辅存地址等）供程序（数据）在换进、换出时参考。
|
|
|
|
请求分页系统中的地址变换机构是在分页系统的地址变换结构的基础上增加了某些功能，如产生和处理缺页中断、从主存中换出一页实现虚拟存储。
|
|
|
|
在请求分页系统中，每当所要访问的页面不在主存时便要产生一个缺页中断，请求OS将所缺的页调入主存，这是由缺页中断机构完成的。缺页中断与一般中断的主要区别如下：
|
|
|
|
（1）缺页中断在指令执行期间产生和处理中断信号，而一般中断在一条指令执行完，下一条指令开始执行前检查和处理中断信号。
|
|
|
|
（2）发生缺页中断时，返回到被中断指令的开始重新执行该指令，而一般中断返回到下一条指令执行。
|
|
|
|
|
|
|
|
请求分页是在纯分页系统的基础上增加了请求调页功能、页面置换功能所形成的页式虚拟存储系统，它是目前常用的一种虚拟存储器的方式。在进程运行过程中，如果发生缺页，此时主存中又无空闲块时，为了保证进程能正常运行，必须从主存中调出一页程序或数据送磁盘的对换区。但究竟将哪个页面调出，需要根据一定的页面置换算法来确定。置换算法的好坏将直接影响系统的性能，不适当的算法可能会导致系统发生“抖动”（thrashing）。即刚被换出的页很快又被访问，需重新调入，导致系统频繁地更换页面，以至于一个进程在运行中把大部分时间花费在完成页面置换的工作上，这种现象称为系统发生了“抖动”（也称颠簸）。请求分页系统的核心问题是选择合适的页面置换算法，常用的页面置换算法如下所述。
|
|
|
|
|
|
这是一种理想化的算法，即选择那些永不使用的，或者是在最长时间内不再被访问的页面置换出去。这种方法性能最好，但实际上难于实现，并且要确定哪一个页面是未来最长时间内不再被访问的是很难的，所以该算法通常用来评价其他算法。
|
|
|
|
|
|
该算法总是淘汰最先进入主存的页面，即选择在主存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程调入主存的页面，按先后次序链接成一个队列，并设置一个指针即可。它是一种最直观、性能最差的算法，有Belady异常现象。所谓Belady现象，是指如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多但缺页率反而提高的异常现象。例如，对于页面访问序列“1，2，3，4，1，2，5，1，2，3，4，5”，当分配的物理块从3块增加到4块时，有缺页次数增加、缺页率提高的异常现象。
|
|
|
|
最近最少使用（Least Recently Used，LRU）置换算法
|
|
|
|
该算法是选择最近最少使用的页面予以淘汰，系统在每个页面设置一个访问字段，用于记录这个页面自上次被访问以来所经历的时间T，当要淘汰一个页面时，选择T最大的页面，但在实现时需要硬件的支持（寄存器或栈）。
|
|
|
|
最近未用（Not Used Recently，NUR）置换算法
|
|
|
|
NUR算法将最近一段时间未引用过的页面换出，这是一种LRU的近似算法。该算法为每个页面设置一位访问位，将主存中的所有页面都通过链接指针链成一个循环队列。当某页被访问时，其访问位置1。在选择一页淘汰时，检查其访问位，如果是0，则选择该页换出；若为1，则重新置为0，暂不换出该页，在循环队列中检查下一个页面，直到访问位为0的页面为止。由于该算法只有一位访问位，只能用它表示该页是否已经使用过，而置换时是将未使用过的页面换出去，所以把该算法称为最近未用算法。
|
|
|
|
|
|
事实上，程序在运行中所产生的缺页情况会影响程序的运行速度及系统性能，而缺页率的高低又与每个进程所占用的物理块数目有关。那么，究竟应该为每个进程分配多少个物理块才能把缺页率保持在一个合理的水平上，而不会因为进程频繁地从辅存请求页面而出现“颠簸”（也称抖动）现象？为了解决这一问题，引入了工作集理论。
|
|
|
|
工作集的理论是1968年由Denning提出的，他认为，虽然程序只需有少量的几页在主存就可以运行，但为了使程序能够有效地运行，较少地产生缺页，必须使程序的工作集驻留在主存中。把某进程在时间t的工作集记为w（t，Δ），变量Δ称为工作集“窗口尺寸（Windows Size）”。正确地选择工作集窗口（Δ）的大小，对存储器的有效利用和系统吞吐量的提高都将产生重大的影响。可见工作集就是指在某段时间间隔（Δ）里进程实际要访问的页面的集合。
|
|
|
|
程序在运行时对页面的访问是不均匀的，即往往在某段时间内的访问仅局限于较少的若干个页面，如果能够预知程序在某段时间间隔内要访问哪些页面，并能将它们提前调入主存，将会大大地降低缺页率，从而减少置换工作，提高CPU的利用率。当每个工作集都已达到最小值时，虚存管理程序跟踪进程的缺页数量，根据主存中自由页面的数量可以适当增加其工作集的大小。
|
|
|
