Chapter08-虚存汇编.ppt

1,虚拟存储器,Chapter8,前一章节讨论了计算机系统所使用的各种内存管理策略目的：同时将多个进程保存在内存中以实现多道程序设计要求：在进程执行前必须将这个进程整个地放入内存虚拟存储技术允许进程执行时进程所有信息部分地保存在内存中内存中只需保存当前执行必须的信息，其他信息放在辅存储器中，必要时再调入内存优点：程序可以比物理内存大,2,虚拟内存将内存和辅助存储器统一管理，将其抽象成一个巨大、统一的存储结构，从而允许程序员不受内存的限制虚拟存储器的实现并不容易，使用不当会极大地降低性能本章通过请求式分页技术来讨论虚拟内存，并研究其复杂性和开销,4,实存下作业的运行,要求作业在执行前全部装入内存许多情况下程序并不需要整个装入作业的一次运行并不会用到所有程序分支程序通常有处理异常错误条件的代码，错误即使有也很少发生，这些代码几乎执行不到数组、链表和表通常分配比所需更多的空间例如一个100*100个单元的数组，可能实际用到的只是10*10个元素有些程序模块调用一次以后就不再需要了,内存空间浪费严重,5,硬件和控制结构,分页/分段的两个特点所有存储器访问都是逻辑地址，这些逻辑地址在运行时动态地被转换成物理地址进程可被换入/换出主存，因此执行过程的不同时刻可占据不同主存区域进程可被划分成块（页/段），而且在执行期间这些块在主存中不要求连续,进程执行时不要求所有进程块都装入到内存,6,7,程序的执行,装入时，操作系统仅取进程序的几个块常驻集进程中常驻主存的部分遇到不在主存的逻辑地址时产生中断操作系统置进程为阻塞状态把包含逻辑地址的进程块取进主存,8,中断处理,将包含逻辑地址的进程块取进主存操作系统产生一个磁盘I/O读请求执行磁盘I/O操作期间系统可分派另一个进程占据处理机一旦目标块被取进主存，则产生一个I/O中断，控制被交回操作系统，将该进程置为就绪状态,9,进程部分入驻内存的优点,主存中可保留多个进程任何特定进程都仅仅装入它的部分块内存可放置更多的进程，因此可更有效地利用处理器进程可使用比主存大得多的内存空间,一条指令可能涉及多个页的访问，对指令的访问是否会产生多个缺页中断，从而导致令人无法接受的系统性能呢？,抖动：处理器大部分时间用于交换块，而非执行指令1970s系统抖动市一个重要的研究领域,10,局部性（PrincipleofLocality）,进程中的程序和数据引用具有簇聚性在很小的时间段内，执行可能会局限在几个进程块中操作系统可根据块的最近引用历史预测将来可能用到哪些块这种推测可有效地支持虚存工作,11,存储器概念,实存（Realmemory）即主存虚存（Virtualmemory）非物理方式存在的存储器，在一定内外存和物质基础上，用软件方法，将内存外存统一管理而得到的逻辑存储器虚存大小为磁盘上的存储空间允许更有效的多道程序设计，放松了用户程序与主存间的约束部分装入、请求式调入、交换为特征,内外存统一管理，将外存看作内存的后备存储空间，其大小应为磁盘与主存之和,外存作为内存的后备存储空间，可行性？,12,虚存实现的物质基础,相当容量的辅存空间和主存空间支持分页/段的硬件机构操作系统必须有管理页/段在主存和辅存之间移动的软件,13,请求式分页的思想,仅当页被调用到时才换入内存需要较少的I/O需要较少的内存快速响应支持更多用户调用页查阅此页无效访问）abort不在内存）换入内存,14,请求式分页的页表,每个进程都有自己的页表每个页表项包含与该页对应的内存帧的帧号（如果该页已在内存）需要对页表进行修改,增加一个位P，表示对应页当前是否在主存中增加一个修改位M，表示该页自装入主存到现在是否已被修改未被修改，当该页被换出内存时不需要回写,15,16,17,转换后备缓冲区,每个虚存访问可能引起两次物理存储器访问地址转换时存取相应的页表项存取数据引入一个特殊的高速缓冲寄存器，保存最近访问到的页表项称作转换后备缓冲区（TranslationLookasideBuffer，TLB),18,引入TLB的地址转换,给定虚地址，处理器首先检查TLB如果命中，取帧号并形成实地址没有命中，以页号为索引检索进程页表，取页描述子如果存在位为1，则该页已在主存否则产生一次存储器访问故障，称作缺页（pagefault）故障更新TLB，使包含该次访问新页的信息,缺页中断是特殊中断，为什么？,19,20,性能分析,缺页率(PageFaultRate)p,0p1.0ifp=0,没有缺页ifp=1,每次访问都缺页有效存取时间(EffectiveAccessTime,EAT)EAT=(1p)x内存存取时间+p(缺页处理时间+页面换出时间+换入时间+重启开销),21,性能分析例,内存存取时间=1microsecond50%的情况下所置换的页被修改，需要重写页面交换时间=10,000msecEAT=(1p)x1+p(15000)=1+15000Pmsec,22,页的大小,页越小，内部碎片的量越少页越小，每个进程所需要的页的数目越多页表将变大，也可能部分存在于内存，访问页表也可能发生缺页中断页越小，主存中可保留更多的页，随着执行的深入，主存中可能包含最近引用到的所有页，缺页率将降低辅存设备高速旋转的物理特性要求页较大，以实现更有效的数据块传送,23,缺页率除与页大小有关，还与什么有关？,若分配给进程的帧越多，缺页率会怎样？,24,请求式分段,段的大小是不相等、动态的简化不断增长的数据结构的处理程序员事先不知道特定的某数据结构会变得多大允许程序独立地改变或重新编译有助于进程间的共享有助于保护,25,段表,记录进程的段在主存中的对应块的信息每个段表项包含主存相应块的起始地址和长度用一个位来表明相应的段是否在主存中修改位用于表明相应段从上一次装入主存到目前为止其内容是否被改变,26,27,段页式,分页对程序员透明分段对程序员是可见的段页式系统中，用户地址空间根据程序员的判断划分成许多段；物理内存空间以页为单位进行管理,28,段页式的地址结构,29,操作系统存储管理设计取决于三个基本问题的选择是否使用虚存技术使用的是分页还是分段，或者二者结合为各种存储管理采用的算法或策略,30,决定存储管理设计的三个问题,前两者取决于使用的硬件平台早期Unix不提供虚存，因其处理器不支持分页或分段除老式PC机上的操作系统或特殊系统外，所有重要的操作系统都提供了虚存纯粹的分段系统越来越少，当分段/页组合后，大多数存储管理问题都是关于分页方面的,31,第三个问题属于操作系统策略最重要的都是与性能相关的问题：由于页故障带来相当大的系统开销，因此希望页故障发生的频率最小,32,33,用于虚存的操作系统策略,取策略驻留集管理放置策略置换策略清除策略加载控制,取策略确定一个页何时取入主存，常用请求式、预约式页面调度策略驻留集管理驻留集大小：给进程分配多少主存放置策略决定进程块驻留在主存的什么地方,34,35,置换策略确定淘汰页面掌握常用的置换策略清除策略确定何时将一个被修改过的页写回辅存加载控制涉及驻留主存的进程数,36,取策略FetchPolicy,取策略确定一个页何时取入主存请求式页面调度（Demandpaging）仅当访问到某页中的单元时才将该页调入进程开始启动时会出现大量的缺页预约式页面调入（Prepaging）可能取进额外的页面进程页连续存储在磁盘时有效，充分利用了大多数辅存的特性,37,放置策略PlacementPolicy,确定一个进程块驻留在实存中的什么地方在分段系统中不重要，最佳/先/坏适配法都可用分页/段页式系统，如何放置通常没有关系地址转换硬件、主存访问硬件可为任何页帧组合等效执行地址转换功能,38,置换策略ReplacementPolicy,取进新页时，若无空白帧，选择替换主存中的哪一页？目标是移出最近最不可能访问到的页大多数策略基于过去的行为预测将来的行为存在抖动现象,39,抖动（Thrashing）,当主存中无空白块时，为换进一个块必须换出另一个块；如果一块正好在将要被用道前被换出，系统又将随后立即把它取回来处理器的大部分时间都将用于块的交换，而不是执行指令与页面置换算法选择和进程分配到的页面数太少有关,基本置换算法,最佳页面置换策略OPT选择那些将来不用，或很久以后才用的页面，即下次访问距当前时间最长的页需要预先知道进程运行期间页面的走向，因此无法实现,41,先进先出页面置换算法（FIFO）选择在主存中驻留时间最长的页淘汰推理逻辑：一个很久前被取入主存的页，到现在可能已不会再用到,42,将进程的页帧看作一个循环缓冲区，以循环方式移动页，是实现最简单的置换策略页面可能会反复地换进和换出存在Belady现象缺页率可能会随着分配给进程的帧数的增加而增加,43,最近最少使用策略（LRU）推理逻辑：若某页被访问了，可能很快又被访问；若长时间未被访问，则最近时间段内不会被访问到替换上次访问距当前最远的页，根据局部性原理，也就是最近最不可能访问到的页,44,LRU策略经常用作页面置换算法，主要问题是如何实现LRU可能需要大量硬件支持：为页帧确定一个排序序列，按页帧上次使用的时间来定义最近未使用置换算法（NUR）与LRU类似，更易实现，使用一个引用位，定期置0当某页被访问，将该位置为1选择那些引用位是0的淘汰每次置换后设置所有页面的引用位为0,45,常用置换算法的比较,46,两个概念,抖动虚存中页面在内存和外存之间频繁调度，以至调度页面所需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致系统崩溃，这种现象称为抖动产生的原因：页面置换算法不合理；分配给进程的物理页面数太少（本质上，系统试图根据最近的访问猜测不远将来最可能用到的块）Belady缺页率可能随着分配给进程的帧数的增加而增加,47,思考题,虚拟存储器的容量有哪些限制及代价？可重定位分区管理技术支持虚拟内存吗？请简要分析。试分析缺页中断与一般中断相比，其主要的区别是什么?为实现分页式虚拟存贮，页表中至少应含有哪些内容？纯分页存储管理能实现真正意义上的虚拟存储器吗？为什么？在内存管理中，“内零头”和“外零头”各指的是什么？在固定式分区分配、可变式分区分配、页式虚拟存储系统、段式虚拟系统中，各会存在何种零头？,假定一个存储管理程序已经把它的页面淘汰决定缩小到两页之一，其中一页由几个进程共享，另一页仅由一个进程使用，最终应该淘汰哪页？为什么？一台计算机有4个页，装入时间、上次引用时间和它们的R（读）和M（修改）位如下所示，如果需要调入一个新页，根据OPT、FIFO、LRU算法，系统将选择淘汰哪一个页？什么叫抖动？产生都抖动的原因有哪些？针对每个产生原因有何解决策略？,页装入时间上次引用时间RM012627900123026010212027211316028011,页式虚拟存储器的地址变换过程中进程状态有无可能发生变化？如可能则请指出在哪些点上可能发生变化。,习题,某计算机为它的用户提供了232B的虚拟存储空间。计算机有218B的物理内存。虚存采用页面大小为4094B的分页机制实现。一个用户产生虚拟地址11123456，请说明系统怎样建立相应的物理地址。假设有下面的页引用序列：1、2、3、4、2、1、5、6、2、1、2、3、7、6、3、2、1、2、3、6，LRU、FIFO、OPT置换算法下分别会产生多少次缺页中断？假设分配给进程的帧有3个，所有帧初始为空；假定现有一种淘汰算法，该算法淘汰页面的策略为当需要淘汰页面时，就把刚使用过的页面作为淘汰对象，试问就相同的页面走向，其缺页率又为多少？,51,一个程序的段表如下：段号状态位段始址段长存取控制0010040W11201020W201590100E307550R其中状态位“1”表示该段不在内存中，存取控制：W表示可写，R表示可读，E表示可执行。对于下列指令可能发生什么情况？如果正常，请给出指令地址的物理地址。1）STOR