|
|
知识路径： > 嵌入式系统软件基础知识 > 嵌入式操作系统基础知识 > 存储管理 > 虚拟存储技术（程序局部性原理、虚拟页式存储管理、页面置换算法等） >
|
被考次数：1次
被考频率：低频率
总体答错率：49%
知识难度系数： 
|
由 软考在线 用户真实做题大数据统计生成
|
|
考试要求：掌握
相关知识点：21个
|
|
|
|
|
在操作系统的支持下，MMU还提供虚拟存储功能。即使一个任务所需要的内存空间超过了系统所能提供的内存空间，也能够正常运行。
|
|
|
|
|
|
程序的局部性原理，指的是程序在执行过程中的一个较短时期内，它所执行的指令和访问的存储空间，分别局限在一定的区域内。这可以表现在时间和空间两个方面。
|
|
|
|
.时间局限性：一条指令的一次执行和下一次执行，一个数据的一次访问和下一次访问，都集中在一个较短的时期内；
|
|
|
|
.空间局限性：如果程序执行了某条指令，则它相邻的几条指令也可能马上被执行；如果程序访问了某个数据，则它相邻的几个数据也可能马上被访问。
|
|
|
|
|
|
.程序在执行时，大部分都是顺序执行的指令，只有少部分是跳转和函数调用指令。而顺序执行就意味着在一小段时间内，CPU所执行的若干条指令在地址空间当中是连续的，集中在一个很小的区域内；
|
|
|
|
.程序中存在着相当多的循环结构，在这些循环结构的循环体当中，只有少量的指令，它们会被多次地执行；
|
|
|
|
.程序中存在着相当多对一定数据结构的操作，这些操作往往局限在比较小的范围内。例如数组操作，数组是连续分配的，各个数组元素之间是相邻的。
|
|
|
|
程序的局部性原理说明，在一个程序的运行过程中，在某一段时间内，这个程序只有一小部分的内容是处于活跃状态，正在被使用，而其他的大部分内容可能都处于一种休眠状态，没有在使用，而这就意味着，从理论上来说，虚拟存储技术能够实现且能产生较好的效果。实际上，在很多地方都已经用到了程序的局部性原理。例如，页式地址映射当中的TLB、CPU里面的Cache等，都是基于局部性原理。
|
|
|
|
|
|
虚拟页式存储管理就是在页式存储管理的基础上，增加了请求调页和页面置换的功能。它的基本思路是：当一个用户程序需要调入内存去运行时，不是将这个程序的所有页面都装入内存，而是只装入部分的页面，就可以启动这个程序去运行。在运行过程中，如果发现要执行的指令或者要访问的数据不在内存当中，就向系统发出缺页中断请求，然后系统在处理这个中断请求时，就会将保存在外存中的相应页面调入内存，从而使该程序能够继续运行。
|
|
|
|
在单纯的页式存储管理当中，页表的功能就是把逻辑页面号映射为相应的物理页面号。因此，对于每一个页表项来说，它只需要两个信息，一个是逻辑页面号，另一个是与之相对应的物理页面号。但是在虚拟页式存储管理当中，除了这两个信息之外，还要增加其他的一些信息，包括驻留位、保护位、修改位和访问位。
|
|
|
|
.驻留位：表示这个页面现在是在内存还是在外存。如果这一位等于1，表示页面位于内存中，即页表项是有效的；如果这一位等于0，表示页面还在外存中，即页表项是无效的。如果此时去访问，将会导致缺页中断；
|
|
|
|
.保护位：表示允许对这个页面做何种类型的访问，如只读、可读写、可执行等；
|
|
|
|
.修改位：表示这个页面是否曾经被修改过。如果该页面的内容被修改过，CPU会自动地把这一位的值设置为1；
|
|
|
|
.访问位：如果这个页面曾经被访问过，包括读操作、写操作等，那么这一位就会被硬件设置为1。这个信息主要是用在页面置换算法当中。
|
|
|
|
当一个缺页中断发生时，操作系统是如何来处理的呢？当发生一个缺页中断时，首先判断在内存中是否还有空闲的物理页面。如果有，就分配一个空闲页面出来；如果没有，就要采用某种页面置换算法，从内存当中，选择一个即将被替换出去的页面。对这个页面的处理也要分两种情形。如果这个页面在内存期间曾经被修改过，也就是说，在它的页表项里面，修改位的值等于1，那么就把它的内容写回到外存当中。如果这个页面在内存期间没有被修改过，那么就什么都不用做，到时候它自然而然会被新的页面所覆盖。现在我们已经有了一个可供使用的物理页面，不管这个页面是直接分配的空闲页面，还是将某个页面置换出去后腾出来的。接下来，就可以把需要访问的新的逻辑页面装入到这个物理页面当中，并修改相应的页表项的内容，包括驻留位、物理页面号等等。最后退出中断，重新运行中断前的指令。当这条指令重新运行的时候，由于它需要访问的逻辑页面已经在内存当中，所以就能够顺利地运行下去，不会再产生缺页中断。缺页中断的处理流程如下图所示。
|
|
|
|
|
|
|
|
|
|
如前所述，系统在处理缺页中断时，需要调入新的页面。如果此时内存已满，就要采用某种页面置换算法，从内存中选择某一个页面，把它置换出去。最简单的做法是随机地进行选择，但这显然不是一个令人满意的方法。例如，假设随机选中的是一个经常要访问的页面，当它被置换出去后，可能马上又得把它换进来，而这种换进换出是需要开销的。所以，对于一个好的页面置换算法来说，它应该尽可能地减少页面的换进换出次数，或者说，尽可能地减少缺页中断的次数，从而减少系统在这方面的开销。具体来说，它应该把那些将来不再使用的，或者短期内较少使用的页面换出去，而把那些经常要访问的页面保留下来。不过，在通常的情形下，我们不可能完全做到这一点。因此，通常的做法，就是在程序局部性原理的指导下，依据过去的统计数据来对将来进行预测。
|
|
|
|
常用的页面置换算法包括：最优页面置换算法、最近最久未使用算法、最不常用算法、先进先出算法和时钟页面置换算法。
|
|
|
|
最优页面置换算法（optimal page replacement algorithm，OPT）
|
|
|
|
最优页面置换算法的基本思路是：当一个缺页中断发生时，对于内存中的每一个逻辑页面，计算在它的下一次访问之前，还要等待多长的时间，然后从中选择等待时间最长的那个，来作为被置换的页面。从算法本身来看，这的确是一个最优算法，它能保证缺页中断的发生次数是最少的。但是，这个算法只是一种理想化的算法，在实际的系统中是无法实现的，因为操作系统无从知道，每一个页面还要等待多长的时间，才会被再次地访问。因此，该算法通常是用作其他算法的性能评价依据。
|
|
|
|
最近最久未使用算法（Least Recently Used，LRU）
|
|
|
|
最近最久未使用算法的基本思路是：当一个缺页中断发生时，从内存中选择最近最久没有被使用的那个页面，把它淘汰出局。LRU算法实质上是对最优页面置换算法的一个近似，它的理论依据就是程序的局部性原理。也就是说，如果在最近一小段时间内，某些页面被频繁地访问，那么在将来的一小段时间内，这些页面可能会再次被频繁地访问。反之，如果在过去一段时间内，某些页面长时间没有被访问，那么在将来，它们还可能会长时间得不到访问。OPT算法寻找的是将来长时间内得不到访问的那个页面，而LRU算法寻找的是过去长时间内没有被访问的那个页面。
|
|
|
|
LRU算法需要记录各个页面在使用时间上的先后顺序，因此系统的开销比较大。在具体实现上，主要有两种方法。
|
|
|
|
.链表法：由系统来维护一个页面链表，把最近刚刚使用过的页面作为首结点，把最久没有使用的页面作为尾结点。在每一次访问内存的时候，找到相应的逻辑页面，把它从链表中摘下来，移动到链表的开头，成为新的首结点。然后，当发生缺页中断的时候，总是淘汰链表末尾的那个页面，因为它就是最久未使用的。
|
|
|
|
.栈方法：由系统来设置一个页面栈，每当访问一个逻辑页面时，就把相应的页面号压入到栈顶，然后考察栈内是否有与之相同的页面号，如果有就把它抽出来。当需要淘汰一个页面时，总是选择栈底的页面，因为它就是最久未使用的。
|
|
|
|
最不常用算法（Least Frequently Used，LFU）
|
|
|
|
最不常用算法的基本思路是：当一个缺页中断发生时，选择访问次数最少的那个页面，把它淘汰出局。在具体实现上，需要对每一个页面都设置一个访问计数器。每当一个页面被访问时，就把它的计数器的值加1。然后在发生缺页中断的时候，选择计数值最小的那个页面，把它置换出去。LFU算法和LRU算法类似，都是基于程序的局部性原理，通过分析过去的访问情况来预测将来的访问情况。两者的区别在于：LRU考察的是访问的时间间隔，即对于每一个页面，从它的上一次访问到现在，经历了多长的时间。而LFU考察的是访问的频度，即对于每一个页面，在最近一段时间内，它总共被访问了多少次。
|
|
|
|
先进先出算法（First In First Out，FIFO）
|
|
|
|
先进先出算法的基本思路是：选择在内存中驻留时间最长的页面，把它淘汰出局。在具体实现上，系统会维护一个链表，里面记录了内存当中的所有页面。从链表的排列顺序来看，链首页面的驻留时间最长，链尾页面的驻留时间最短。当发生一个缺页中断时，把链首的页面淘汰出局，然后把新来的页面添加到链表的末尾。FIFO算法的性能比较差，因为它每次淘汰的都是驻留时间最长的页面，而这样的页面并不一定就是不受欢迎的页面，相反，可能是一些经常要访问的页面。如果现在把它们置换出去，将来可能还要把它们再换回来。
|
|
|
|
|
|
FIFO算法的缺点在于：它是根据页面的驻留时间来做出选择，而没有去考虑页面的访问情况。时钟页面置换算法对此进行了改进，把页面的访问情况也作为淘汰页面的一个依据。Clock算法需要用到页表项当中的访问位。当一个页面在内存当中的时候，如果它被访问了（不管是读操作还是写操作），那么它的访问位就会被CPU设置为1。算法的基本思路是：把各个页面组织成环形链表的形式，类似于一个时钟的表面，然后把指针指向最古老的那个页面，即最先进来的那个页面。当发生一个缺页中断的时候，考察指针所指向的那个页面。如果它的访问位的值等于0，说明这个页面的驻留时间最长，而且没有被访问过，因此理所当然地把它淘汰出局。如果访问位的值等于1，这说明这个页面的驻留时间虽然是最长的，但是在这一段时间内，它曾经被访问过了。因此，在这种情形下，就暂不淘汰这个页面，但要把它的访问位的值设置为0。然后把指针往下移动一格，去考察下一个页面。就这样一直进展下去，直到发现某一个页面，它的访问位的值等于0，因此就把它淘汰掉。
|
|
|
|
|
|
工作集模型是计算机科学家Denning在20世纪60年代提出来的，它描述的是一个程序在运行过程中的行为规律。所谓的工作集，就是指任务当前正在使用的逻辑页面的集合。它可以用一个二元函数W（t，△）来表示，其中t指的是当前的执行时刻，△称为工作集窗口，也就是一个定长的页面访问窗口。W（t，△）就等于在t时刻之前的△窗口当中，所有页面所组成的集合。显然，随着当前时刻t的不断变化，任务的工作集也在不断地变化。
|
|
|
|
在一个任务的运行过程中，它的工作集是在不断变化的。一般来说，当一个任务刚刚启动时，它会不断地去访问一些新的页面，然后逐步地建立一个比较稳定的工作集。当内存访问的局部性区域的位置大致稳定时，工作集的大小也就大致地稳定下来。然后，当内存访问的局部性区域的位置发生改变时，工作集就会快速地扩张和收缩，并且过渡到下一个稳定值。在这些稳定阶段，任务在运行的时候，只会去访问一些固定的页面，而其他的页面一般是不会去访问的，这就是程序的局部性原理的具体表现。所以当一个任务在运行的时候，并不需要把它的整个程序都装入到内存，只要把它的工作集装入到内存就可以了。
|
|
|
|
与工作集相关的另一个概念是驻留集。所谓的驻留集，就是在当前时刻，任务实际驻留在内存当中的页面集合。驻留集与工作集既有区别，也有联系。工作集是任务在运行过程中所固有的性质，而驻留集则取决于系统分配给任务的物理页面个数，以及所采用的页面置换算法。当一个任务在运行时，如果它的整个工作集都在内存当中，也就是说，它的工作集是驻留集的一个子集，那么这个任务将会很顺利地运行，不会造成太多的缺页中断。反之，如果分配给一个任务的物理页面数太少，不能包含整个的工作集，也就是说，驻留集是工作集的一个真子集。在这种情形下，任务将会造成很多的缺页中断，需要频繁地进行页面置换，从而使任务的运行速度变得非常慢，这种现象称为“抖动”（thrashing）。
|
|
|
