蒲晓蓉_操作系统原理第3_3章_存储管理

3.5虚拟存储管理技术•简单存储：要求将一个进程所需的程序和数据全部装入内存方可执行。•这样的系统存在两个很严重的问题。—其一，对于大进程，如果其所需内存空间超过了内存的最大容量，则无法运行。—其二，对于多道程序系统，由于每一个进程需要全部装入内存，使同时驻留内存的进程数量受到限制。虽然也可以通过提高内存容量来解决，但是代价太高。•如果能将一部分价格较低的外存空间当作内存使用，从逻辑上扩充内存容量。那么，将获得更高的性价比。虚拟存储技术的理论依据•程序执行的局部性原理：程序的执行总是呈现局部性。即，在一个较短的时间段内，程序的执行仅限于某个部分；相应的，它所访问的存储空间也局限于某个区域。•因此，只要保证进程执行所需的部分程序和数据驻留在内存，一段时间内进程都能顺利执行。实现虚拟存储的一般过程•进程运行之前，仅需要将一部分页面或段装入内存，便可启动运行，其余部分暂时保留在磁盘上。•进程运行时，如果它所需要访问的页面（段）已经装入内存，则可以继续执行下去；•如果其所需要访问的页面（段）尚未装入内存，则发生缺页（段）中断，进程阻塞。•此时，系统将启动请求调页（段）功能，将进程所需的页（段）装入内存。实现虚拟存储的一般过程•如果当前内存已满，无法装入新的页（段），则还需要利用页（段）置换功能，将内存中暂时不用的页（段）交换到磁盘上，以腾出足够的内存空间。•再将进程所需的页（段）装入内存，唤醒阻塞的进程，使之重新参与调度执行。从外存装入页/段更新页/段表交换页/段内存满？是否缺页/段中断页/段在内存是否进程执行图3.28实现虚拟存储的典型过程？什么是虚拟存储•通过系统提供的缺页/段中断功能和交换技术，动态装入进程的程序代码和数据，使得一个大的用户程序能在一个相对较小的内存空间中运行，也使得有限的内存能同时容纳更多的进程。•习惯上，人们把这种用户感觉上的、由实际内存和部分外存共同构成的存储空间称为虚拟存储器虚拟存储技术的技术支持•首先，必须有相应的硬件支持，用以实现虚拟分页或虚拟分段存储管理。•其次，操作系统必须提供相应的软件支持，管理页或段在内存和外存之间的移动。虚拟存储的基本数据结构•由于虚拟存储系统中，进程的程序代码和数据只有一部分在内存，另一部分保存在外存。•在页/段表项中增加一个“存在”字段，其值为0或1。•增加一个“修改”字段，表明对应页/段自进入内存以来是否被修改过。只有被修改过的页/段才需要保存到外存，若需要将未修改过的页/段换出内存，只需要将新装入的页/段直接覆盖其存储区域，而不必将其内容保存到外存。图3.29虚拟分页、分段及段页式存储系统的数据结构页号页框号存在修改其他控制(a)虚拟存储页表项段号段长存在修改其他控制(b)虚拟存储段表项段基址长(c)虚拟存储段页式系统的段表项和页表项段号其他控制页表长度页表基址段表项页号页框号存在修改其他控制页表项虚拟存储的好处•第一，可以运行大程序，包括超过内存实际容量的大程序。•第二，可以在有限的物理内存中运行更多的程序。多道程序系统的度不再受到物理内存空间的限制。虚拟存储的典型问题抖动（thrashing）•当进程要求装入新的页面或程序段时，如果当前没有足够的空闲空间，需要交换一些页面或段到外存。如果被交换出去的页面或段很快将被进程使用，则又需要将其换入内存。•如果系统花费大量的时间把程序和数据频繁地装入和移出内存而不是执行用户指令，那么，称系统出现了抖动。出现抖动现象时，系统显得非常繁忙，但是吞吐量很低，甚至产出为零。•根本原因：选择的页面或段不恰当。虚拟存储分页技术•建立在简单分页存储管理系统之上，是目前常用的一种虚拟存储管理技术。地址变换•基于简单存储分页系统增加了某些功能，如产生和处理缺页中断，以及从内存中换出页面等。•进程执行时，首先通过根据逻辑地址中的页号，查找快表中是否存在对应的页表项。若快表中不存在该页表项，则再查找页表。检查对应的页面是否在内存中存在。若该页面不在内存，启动缺页中断处理例程，装入需要的页面，并更新页表和快表。若该页面已经在内存中，将对应的页表项插入快表中，更新快表。若快表中存在该表项，则直接取出其中的页框号，加上页内偏移量，计算出物理地址。访问页表图3.30虚拟存储分页系统地址变换过程物理地址页框号偏移量更新快表页号偏移量逻辑地址检索快表是否是否换出页面处理机处理中断是否处理机从外存取该页将该页装入内存更新页表缺页中断处理？命中？内存满？页在内存缺页中断处理过程（1）操作系统接收到进程产生的缺页中断信号，启动中断处理例程，保留处理机现场；（2）操作系统通知处理机从外存读取指定的页面；（3）处理机激活I/O设备；（4）检查内存有无足够的空闲空间装入该页面？若有，转（6），否则，执行（5）；（5）利用页面置换算法，选择内存中的某个页面，换出内存；（6）将指定页面从外存装入内存；（7）更新该进程的页表；（8）更新快表；（9）计算物理地址。虚拟存储分段技术•建立在简单存储分段系统基础上，利用动态分区技术分配存储空间，并以段作为交换的单位。•进程执行之前，系统为之分配几个必要的内存分区，每一个分区中装入一段。•当进程执行过程中，出现缺段中断时，操作系统将为进程装入需要的程序段。虚拟存储分段：数据结构•因此，需要修改段表，增加“存在”字段和“修改”字段，分别标明对应段是否存在于内存，以及内存中的段自装入以来是否被修改过。地址变换与存储保护•在简单分段系统的地址变换机构基础上形成的。•越界检查：可能产生一个地址越界中断，进入相应的中断处理例程执行。一般地，当地址越界中断处理完毕，该进程将异常结束。•操作合法性检查：如果属于非法操作，产生非法访问中断，这时也会让进程异常终止。•缺段处理：执行进程被阻塞。并产生一个中断信号，处理机执行缺段中断处理例程。图3.31虚拟存储分段系统地址变换过程物理地址段基址偏移量更新快表否非法访问中断是是否是越界中断处理访问段表段号偏移量逻辑地址检索快表否是缺段中断处理否更新段表？命中？段在内存？地址越界？合法访问图3.31虚拟存储分段系统中的缺段中断的处理过程换出一个或几个段形成一个合适空闲区返回修改段表、空闲分区表从外存读入段s唤醒进程是拼接外零头，形成一个合适的空闲区是段s不在内存阻塞执行进程内存中有合适的空闲区吗？否空闲区容量总和能否满足？否虚拟存储段页式技术•虚拟存储段页式系统中，程序和数据通常以页面为单位被系统装入和移出内存。•因此，一般不需要在段表项中增加“存在”字段和“修改”字段，而将它们放在页表中。•段表中需要保留基于段的保护与存储共享等目的的存取控制信息，页表中设置基于页的控制信息。地址变换•首先，通过根据段号和页号，查找快表中是否存在对应的页表项。•若快表中不存在该页表项，则再查找段表。然后，检索段号对应的段表项，找到对应段的页表起始地址。•再根据页号检索该页表，检查对应页面是否在内存。若该页面不在内存，启动缺页中断处理例程，装入需要的页面，并更新页表和快表。若该页面已经在内存中，将对应的页表项插入快表中，更新快表。•若快表中存在该表项，则直接取出其中的页框号，加上页内偏移量，计算出物理地址。图3.32虚拟存储分页系统地址变换过程更新页表缺页中断处理物理地址页框号偏移量更新快表是否访问段表访问页表检索快表段号页内偏移量逻辑地址段内页号否是？命中？页在内存虚拟存储系统的软件策略•现代操作系统几乎都采用虚拟存储管理系统•一些特殊的操作系统和一些较老的操作系统没有采用虚拟存储技术。例如，MSDOS和早期的UNIX操作系统等。•大多采用分段与分页相结合的段页式管理系统。•下面以分页存储管理为例，介绍虚拟存储系统采用的软件策略。虚拟存储系统的软件策略•驻留集管理(ResidentSetManagement)•放置策略(PlacementPolicy)•获取策略(FetchPolicy)•置换策略(ReplacementPolicy)•清除策略(CleaningPolicy)•负载控制(LoadControl)驻留集管理•进程的驻留集指，虚拟存储系统中，每个进程驻留在内存的页面集合，或进程分到的物理页框集合。•驻留集管理主要解决的问题是，系统应当为每个活跃进程分配多少个页框。影响页框分配的主要因素•分配给每个活跃进程的页框数越少，同时驻留内存的活跃进程数就越多，进程调度程序能调度就绪进程的概率就越大。然而，这将导致进程发生缺页中断的概率较大；•为进程分配过多的页框，并不能显著地降低其缺页中断率。基本的驻留集管理策略•固定分配策略(Fixed-AllocationPolicy)•可变分配策略(Variable-AllocationPolicy)固定分配策略•为每个进程分配固定数量的页框。即，每个活跃进程的驻留集尺寸在运行期间固定不变。•为进程分配多少个页框是合理的呢？—可以由系统根据进程的类型确定，也可以由编程人员或系统管理员指定。可变分配策略•为每个活跃进程分配的页框数在进程的生命周期内是可变的。即，系统可以首先给进程分配一定数量的页框。进程运行期间，可以增加或减少页框。•系统可以根据进程的缺页率调整进程的驻留集。—当进程的缺页率很高时，驻留集太小，需要增加页框；—当缺页率一段时间内都保持很低时，可以在不会明显增加进程缺页率的前提下，回收其一部分页框，减小进程的驻留集。可变分配vs.固定分配•可变分配策略比固定分配策略更灵活，既可以提高系统的吞吐量，又能保证内存的有效利用。•可变分配要求统计进程的缺页率，增加系统额外开销。而准确判断进程缺页率的高低，确定缺页率的阈值是非常困难的。•可变分配策略不仅需要操作系统软件专门的支持，而且，还需要处理机平台提供的硬件支持页面放置策略•解决的问题：系统应当在内存的什么位置为活跃进程分配页框？•一般地，对于一个分页系统或段页式系统，将进程的一个页面装入哪一个页框无关紧要。•对于分段系统，需要考虑将一个程序段装入哪一个合适的分区中，可采用的分配算法包括首次适应法、下次适应法、最佳适应法或最差适应法等。页面获取策略•解决的问题：系统应当在何时把一个页面装入内存？•请求调页(DemandPaging)•预调页(Prepaging)请求调页•仅当进程执行过程中，通过检查页表发现相应页面不在内存时，才装入该页面。•当进程刚开始执行时，由于预先未装入进程的页面，故需要频繁地申请装入页面。执行一段时间以后，进程的缺页率将下降。•采用请求调页方式，一次装入请求的一个页面，磁盘I/O的启动频率较高，系统的开销较大。预调页方式•当进程创建时，预先为进程装入多个页面。•缺页中断时，系统为进程装入指定的页面以及与之相临的多个页面。•若局部性很差，预先装入的很多页面不会很快被引用，并会占用大量的内存空间，反而降低系统的效率页面置换策略•当发生缺页中断且无足够的内存空间时，需要置换已有的某些（个）页面。•应该解决的基本问题：—当系统欲把一个页面装入内存时，应当在什么范围内判断已经没有空闲页框供分配？—当指定的范围内没有空闲页框时，应当从指定的范围内选择哪个页面移出内存？局部置换策略•可以采用局部置换或全局置换策略。•局部置换：系统在进程自身的驻留集中判断当前是否存在空闲页框，并在其中进行置换。全局置换策略•在整个内存空间内判断有无空闲页框，并允许从其它进程的驻留集中选择一个页面换出内存。分配模式vs.置换模式•固定分配策略局部置换策略•全局置换策略可变分配策略•可变分配策略+局部置换策略—即可增加或减少分配给每个活跃进程的页框数；当进程的页框全部用完，而需要装入一个新的页面时，系统将在该进程的当前驻留集中选择一个页面换出内存。页面置换策略•页面置换算法：在指定的置换范围内，决定将哪一个页面换出内存。•置换算法的好坏将直接影响系统的性能，不适当的置换算法可能导致系统出现“抖动”现象。•常用的页面置换算法：最佳置换算法、最近最少使用算法、先进先出算法和时钟算法等最佳置换算法(OptimalAlgorithm，OPT)•基本思想：被置换的页面是将来不再访问，或在最远的将来才被访问的页面。•若采用固定分配