存储器管理主题知识讲座

第四章存放器管理（二）中国民航大学计算机科学与技术学院存储器管理主题知识讲座第1页第四章存放器管理4.1存放器存放层次4.2程序装入和链接4.3连续分配方式4.4基本分页存放管理方式4.5基本分段存放管理方式4.6虚拟存放器基本概念4.7请求分页存放管理方式4.8页面置换算法4.9请求分段存放管理方式存储器管理主题知识讲座第2页4.6虚拟存放器基本概念

传统内存管理方式要求将一个作业全部装入内存才能够运行，由此造成了以下两种情况：大作业对内存要求超出物理内存总容量，致使其无法运行内存因为容量限制，只能装入少许作业使其运行，而其它大量作业留在外存上怎么办？方法一：从物理上增加内存容量，成本高！方法二：从逻辑上扩充内存容量！虚拟存放技术！存储器管理主题知识讲座第3页4.6.1虚拟存放器引入传统思绪：进程必须全部进入内存，直至运行结束“一次性”全部装入内存，对空间浪费非常大在进程运行过程中，一直“驻留”在内存。暂时不用数据无法释放1、常规存放器管理方式特征——一次性、驻留性。存储器管理主题知识讲座第4页2.局部性原理早在1968年，Denning.P就曾指出：程序在执行时展现局部性规律。在较短时间内，程序执行局限于某个部分；访问存放空间局限于某个区域。程序执行时，除了少部分转移和过程调用指令外，在大多数情况下仍是次序执行。过程调用将会使程序执行轨迹由一部分区域转至另一部分区域，但经研究看出，过程调用深度在大多数情况下都不超出5。程序中存在许多循环结构，这些即使只由少数指令组成，不过它们将屡次执行。程序中还包含许多对数据结构处理，如对数组进行操作，它们往往都局限于很小范围内。存储器管理主题知识讲座第5页

不足又表现在下述两个方面：时间不足。假如程序中某条指令一旦执行，则很快以后该指令可能再次执行；假如某数据被访问过，则很快以后该数据可能再次被访问。产生时间不足经典原因，是因为在程序中存在着大量循环操作。空间不足。一旦程序访问了某个存放单元，在很快之后，其附近存放单元也将被访问，即程序在一段时间内所访问地址，可能集中在一定范围之内，其经典情况便是程序次序执行。存储器管理主题知识讲座第6页基于局部性原理：在程序装入时，无须将其全部读入到内存，而只需将当前需要执行部分页或段读入到内存，就可让程序开始执行。在程序执行过程中，假如需执行指令或访问数据还未在内存（称为缺页或缺段），利用OS提供请求调页（段）功效，将对应页或段调入到内存，然后继续执行程序。假如此时内存已满，无法装入新页（段），则还必须调用页（段）置换功效。这么，便可是一个大用户程序，在较小内存空间运行；也可在内存中同时装入更多进程并发运行。存储器管理主题知识讲座第7页3.虚拟存放器定义

所谓虚拟存放器，是指含有请求调入功效和置换功效，能从逻辑上对内存容量加以扩充一个存放器系统。其逻辑容量由内存容量和外存容量之和所决定其运行速度靠近于内存速度成本却又靠近于外存虚拟存放技术是一个性能非常优越存放器管理技术，故被广泛地应用于大、中、小型机器和微型机中。

存储器管理主题知识讲座第8页地址空间存贮空间(编程)(运行)逻辑物理虚空间(虚存)实存、实空间交换o.s程序访问地址称为虚地址而程序可访问虚地址范围叫做程序虚地址空间。可使用实地址范围叫实地址空间(即主存)在多道程序运行环境下，o.s把实际内存扩充成若干个虚存系统为每个用户建立一个虚拟存贮器，各用户可独立在虚存上编程运行。存储器管理主题知识讲座第9页XXXX7X5XXX34061260K-64K56K-60K52K-56K48K-52K44K-48K40K-44K36K-40K32K-36K28K-32K24K-28K20K-24K16K-20K12K-16K8K-12K4K-8K0K-4K28K-32K24K-28K20K-24K16K-20K12K-16K8K-12K4K-8K0K-4K虚地址空间物理地址空间}虚页页框存储器管理主题知识讲座第10页151413121110987654321000000000000000011110000101100000000000011011001000111010111010100010000000000100011000000000100011在/不在内存页表虚地址8196物理地址24580存储器管理主题知识讲座第11页4.6.2虚拟存放器实现方法实现原理进程运行只装入部分程序和数据在外存保留完整副本运行中动态调整进程在内存中布署技术难点怎样确定和统计当前哪些部分在内存？执行中访问不在内存指令和数据时怎样处理？从外存中调入某页时,内存中空间不够怎样处理？优点:利用率高，方便用户，对多道程序运行有较强支持有两种经典虚拟存放器实现方式存储器管理主题知识讲座第12页1.分页请求系统在分页系统基础上，增加了请求调页功效、页面置换功效所形成页式虚拟存放系统基本思想分页管理，装入少许页运行，缺页故障后调整页表结构进行了调整:页号+标志位+块号+外存地址地址转换:正常地址转换缺页时：缺页中止存储器管理主题知识讲座第13页2.请求分段系统在分段系统基础上，增加请求调段及分段置换功效后，所形成段式虚拟存放系统。基本思想装入部分段动态装入或调出段段表结构进行了扩充：段号+主存起址+长度+辅存起址+标志位+扩充位…缺段中止机构地址变换机构存储器管理主题知识讲座第14页4.5.3虚拟存放器特征离散性在内存分配时采取离散分配方式屡次性一个作业被分成屡次地调入内存运行对换性允许作业在运行过程中换进、换出虚拟性从逻辑上扩充内存容量，使用户可使用内存空间大于实际物理内存。存储器管理主题知识讲座第15页第四章存放器管理4.1存放器存放层次4.2程序装入和链接4.3连续分配方式4.4基本分页存放管理方式4.5基本分段存放管理方式4.6虚拟存放器基本概念4.7请求分页存放管理方式4.8页面置换算法4.9请求分段存放管理方式存储器管理主题知识讲座第16页4.7.1请求分页中硬件支持为了实现请求分页，系统要提供一定硬件支持。除了一定容量内存和外存，还需要有：页表机制、缺页中止机构和地址变换机构存储器管理主题知识讲座第17页问题一：怎样发觉页不在内存？扩充表(以前页表结构只包含页号和块号两个信息，这是进行地址变换机构所必须，为了判断页面在不在主存，可在原页表上扩充）！存储器管理主题知识讲座第18页1.页表机制页号物理块号状态位P

访问字段A修改位M外存地址用于将用户逻辑地址空间变换为内存物理地址空间。在页表中增加若干项，方便于标志程序或数据状态。页表项：状态位（存在位）P：表示该页是否调入内存访问字段A：用于统计该页在某段时间内被访问次数修改位M：表示该页在调入内存后是否被修改过外存地址：该页在外存上地址，通常是物理块号存储器管理主题知识讲座第19页缺页中止管理！问题二：怎样处理缺页？存储器管理主题知识讲座第20页2.缺页中止机构在地址映射过程中，在页表中发觉所要访问页不在内存，则产生缺页中止。操作系统接到此中止信号后，就调出缺页中止处理程序，依据页表中给出外存地址，将该页调入内存，使进程继续运行下去。假如内存中有空闲块，则分配一页，将新调入页装入内存，并修改页表中对应页表项目标状态位及对应内存块号。若此时内存中没有空闲块，则要淘汰某页，若该页在内存期间被修改过，则要将其写回外存。存储器管理主题知识讲座第21页

处理过程：保护CPU现场、分析中止原因、转入缺页中止处理程序、恢复CPU环境。特点缺页中止发生在指令执行期间，而通常情况下，CPU是在一条指令执行完后，才检验是否有中止请求抵达；一条指令在执行期间，可能产生屡次缺页中止。存储器管理主题知识讲座第22页图4-23包括6次缺页中止指令硬件机构应能保留屡次中止时状态，并确保最终能返回到中止前产生缺页中止指令处，继续执行。存储器管理主题知识讲座第23页问题三：缺页中止，调入所缺页，假如内存不足，选一页淘汰，选择哪一页呢？存储器管理主题知识讲座第24页页号物理块号状态位P访问位A修改位M外存地址

访问位是来指示某页最近被访问过没有。修改位是来指示某页数据修改过没有。“0”表示没有访问过“1”表示已被访问过访问位修改位1修改位–––写回辅存0未修改过–––无须写回辅存存储器管理主题知识讲座第25页问题四：怎样实现地址变换？存储器管理主题知识讲座第26页3.地址变换机构图4-24请求分页中地址变换过程存储器管理主题知识讲座第27页在地址变换时，首先检索快表，试图从中找到要访问页。如找到，修改其访问位。对于“写”指令，还要设置修改位值。如未找到，则转3。利用页表项中物理块号和页内地址，形成物理地址。查找页表，找到页表项后，判断其状态位P，查看该页是否在内存中。假如在，则将该页写入快表（若快表已满，则应该先调出某个或一些页表项）。假如不在，则产生缺页中止，由OS从外存将该页调入内存。存储器管理主题知识讲座第28页工作区入内存填写页表中各项进程调度该进程执行开启待执行指令计算页号与页内相对地址该页在主存吗？执行下一条指令访内存执行完成该指令地址变换保留当前进程现场有空闲页面吗？调入所需虚页调整页表及空闲页面表恢复被中止进程现场选择一页淘汰该页修改过？把该页写回外存缺页中止是否否否是是硬件完成请求分页处理流程。存储器管理主题知识讲座第29页L1,2120ADD1,341000680201k2k3k01k2k3k-101k2k3k-10062514k-1job1job2job30…051…062…1－0…021…042…1－3…1－0…081…032…1－ososjob2(0页)job3(1页)L1,2120ADD1,3410job1(0页)job1(1页)空job3(0页)空01k2k3k10-k4k5k6k7k8k9k辅存块号主存请求页式映象存贮图：存储器管理主题知识讲座第30页4.7.2内存分配策略和分配算法在为进程分配物理块时，要处理以下三个问题：确保进程可正常运行所需要最少物理块数每个进程物理块数，是固定值还是可变值（分配策略）不一样进程所分配物理块数，是采取平均分配算法还是依据进程大小按照百分比给予分配（分配算法）。存储器管理主题知识讲座第31页4.7.2内存分配策略和分配算法进程应取得最少物理块数与计算机硬件机构相关，取决于指令格式、功效和寻址方式。一、最小物理块数存储器管理主题知识讲座第32页在请求分页中，可采取两种分配策略，即固定和可变分配策略。在进行置换时，也可采取两种策略，即全局置换和局部置换（置换范围不一样）。于是组合出三种适用策略：二、页面分配和置换策略存储器管理主题知识讲座第33页1、固定分配局部置换思绪分配固定数目标内存空间，在整个运行期间都不改变策略假如缺页，则先从该进程在内存页面中选中一页，进行换出操作，然后再调入一页。特点为每个进程分配多少页是适当值难以确定。存储器管理主题知识讲座第34页2、可变分配全局置换思绪：每个进程预先分配一定数目标物理块，同时OS也保持一个空闲物理块队列。策略当缺页时，首先将对OS所占有空闲块进行分配，从而增加了各进程物理块数。当OS空闲块全部用完，将引发换出操作。存储器管理主题知识讲座第35页思绪系统依据缺页率动态调整各进程占有物理块数目，使其保持在一个比较低缺页率状态下。特点使大部分进程能够到达比较近似性能。3、可变分配局部置换存储器管理主题知识讲座第36页在采取固定分配策略时，可使用以下方法来分配：1、平均分配算法：将系统中全部可供分配物理块，平均分配给各个进程。2、按百分比分配算法：按照进程大小百分比分配物理块。3、考虑优先权分配算法：为了对于紧迫作业，能够尽快完成。能够将内存物理块分成两部分，一部分按照百分比分配给各进程，另一部分依据进程优先级，适当增加其对应份额，分配给各进程。三、分配算法存储器管理主题知识讲座第37页

1)平均分配算法

这是将系统中全部可供分配物理块，平均分配给各个进程。比如，当系统中有100个物理块，有5个进程在运行时，每个进程可分得20个物理块。这种方式貌似公平，但实际上是不公平，因为它未考虑到各进程本身大小。如有一个进程其大小为200页，只分配给它20个块，这么，它必定会有很高缺页率；而另一个进程只有10页，却有10个物理块闲置未用。存储器管理主题知识讲座第38页

2)按百分比分配算法这是依据进程大小按百分比分配物理块算法。假如系统中共有n个进程，每个进程页面数为Si，则系统中各进程页面数总和为：又假定系统中可用物理块总数为m，则每个进程所能分到物理块数为bi，将有：b应该取整，它必须大于最小物理块数。存储器管理主题知识讲座第39页

3)考虑优先权分配算法

在实际应用中，为了照料到主要、紧迫作业能尽快地完成，应为它分配较多内存空间。通常采取方法是把内存中可供分配全部物理块分成两部分：一部分按百分比地分配给各进程；另一部分则依据各进程优先权，适当地增加其对应份额后，分配给各进程。在有系统中，如主要实时控制系统，则可能是完全按优先权来为各进程分配其物理块。存储器管理主题知识讲座第40页4.7.3调页策略1.何时调入页面预调页策略预先装入主存一页或几页（提前页）主要用于进程首次调入请求调页策略当用到某页而不在主存时即缺页时取页用得较多一次调入一页，增加了磁盘I/O开启频率存储器管理主题知识讲座第41页2.从何处调入页面外存有两个部分：文件区和对换区。对换区I/O操作速度比文件区相对快一些，所以普通应该尽可能使用对换区来调入页面。对于不一样情况，采取不一样策略：1、系统有足够对换空间2、系统对换空间不足3、UNIX调入方式存储器管理主题知识讲座第42页3.页面调入过程进程需要页面不在内存，引发缺页中止中止处理程序保留现场环境，转入缺页中止处理程序中止处理程序查找页表，得到对应外存物理块号。假如内存有空闲，则开启磁盘操作，将所缺页面读入，并修改页表。不然，到4。执行置换算法，选出要换出页面，假如该页修改过，应将其写入磁盘，然后将所缺页调入内存，修改对应表项，将其存在位置为‘1’，并放入快表。利用修改后页表，形成物理地址，访问内存数据。存储器管理主题知识讲座第43页优点：

可提供多个大容量虚拟存放器：作业地址空间不再受主存大小限制主存利用率大大提升：作业中不惯用页不会长久驻留在主存，当前运行用不到信息也无须调入主存能实现多道作业同时运行方便用户：大作业也无须考虑覆盖问题缺点：

缺页中止处理增加系统开销页面调入调出增加I/O系统负担另外页表等占用空间且需要管理，存在页内零头请求分页存放管理方式存储器管理主题知识讲座第44页第四章存放器管理4.1存放器存放层次4.2程序装入和链接4.3连续分配方式4.4基本分页存放管理方式4.5基本分段存放管理方式4.6虚拟存放器基本概念4.7请求分页存放管理方式4.8页面置换算法4.9请求分段存放管理方式存储器管理主题知识讲座第45页4.8页面置换算法功效：需要调入页面时，选择内存中哪个物理页面被置换。目标：把未来不再使用或短期内较少使用页面调出，通常只能在局部性原理指导下依据过去统计数据进行预测。页面锁定(framelocking)：用于描述必须常驻内存操作系统关键部分或时间关键(time-critical)应用进程。实现方法为在页表中加上锁定标志位(lockbit)。存储器管理主题知识讲座第46页系统抖动：内外存交换频繁使效率下降(造成系统效率急剧下降主、辅存之间频繁转换现象)驻留集：驻留在内存中页面集合。存储器管理主题知识讲座第47页几个页面置换算法:

最正确置换算法(OPT,optimal)*先进先出算法(FIFO)*最近最久未使用算法(LRU,LeastRecentlyUsed)*轮转算法(clock)最不惯用置换算法(LFU,LeastFrequentlyUsed)*页面缓冲算法(pagebuffering)存储器管理主题知识讲座第48页1.最正确置换算法最正确置换算法是由Belady于1966年提出一个理论上算法。其所选择被淘汰页面，将是以后永不使用，或许是在最长(未来)时间内不再被访问页面。采取最正确置换算法，通常可确保取得最低缺页率。这是一个理想情况，是实际执行中无法预知，因而不能实现。可用作性能评价依据。存储器管理主题知识讲座第49页

例、假定系统为某进程分配了三个物理块，并考虑有以下页面号引用串：

7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

进程运行时，先将7，0，1三个页面装入内存。以后，当进程要访问页面2时，将会产生缺页中止。此时OS依据最正确置换算法，将选择页面7给予淘汰。图4-25利用最正确页面置换算法时置换图存储器管理主题知识讲座第50页2.先进先出(FIFO)页面置换算法选择装入最早页面被置换。能够经过链表来表示各页建立时间先后。性能较差。较早调入页往往是经常被访问页，这些页在FIFO算法下被重复调入和调出。而且有抖动现象。存储器管理主题知识讲座第51页图4-26利用FIFO置换算法时置换图

7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

存储器管理主题知识讲座第52页例：某进程分配页数为3，其运行期间页面访问序列：A,B,C,D,A,B,E,A,B,C,D,E，分析其按照FIFO算法进行页面置换时缺页情况（进程页数分别是3和4）。存储器管理主题知识讲座第53页缺页次数=9；缺页率f=9/12=75%

缺页次数=10；缺页率f=10/12=83%驻留集越大，缺页中止率越小吗？Belady’sanomaly存储器管理主题知识讲座第54页3最近最久未使用(LRU)置换算法选择内存中最久未使用页面被置换这是局部性原理合理近似，性能靠近最正确算法。(“最近过去”对“最近未来”近似)但因为需要统计页面使用时间先后关系，硬件开销太大存储器管理主题知识讲座第55页LRU(LeastRecentlyUsed)置换算法描述图4-27LRU页面置换算法

7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

存储器管理主题知识讲座第56页存储器管理主题知识讲座第57页LRU置换算法硬件支持存放器每个页面设置移位存放器：被访问时左边最高位置1，定时右移而且最高位补0，于是存放器数值最小是最久未使用页面。栈一个特殊栈：把被访问页面移到栈顶，于是栈底是最久未使用页面。存储器管理主题知识讲座第58页图4-28某进程含有8个页面时LRU访问情况1)存放器存储器管理主题知识讲座第59页2)栈图4-29用栈保留当前使用页面时栈改变情况存储器管理主题知识讲座第60页4.Clock置换算法（LRU近似算法）简单Clock置换算法（最近未用算法NRU）也称最近未使用算法(NRU,NotRecentlyUsed)，它是LRU(最近最久未使用算法)和FIFO折衷。内存中全部页面经过链接指针形成一个循环队列每页有一个使用访问位(usebit)，若该页被访问则置usebit=1。置换时采取一个指针，从当前指针位置开始按地址先后检验各页，寻找usebit=0页面作为被置换页。指针经过userbit=1页都修改userbit=0，最终指针停留在被置换页下一个页。存储器管理主题知识讲座第61页简单Clock置换算法（最近未用算法NRU）图4-30简单Clock置换算法流程和示例存储器管理主题知识讲座第62页存储器管理主题知识讲座第63页存储器管理主题知识讲座第64页存储器管理主题知识讲座第65页改进型Clock置换算法因为Clock算法不考虑换出页面时，页面是否修改过问题。这么在换出页面假如被修改过话，则必须做拷回磁盘处理，开销比较大。于是，改进型Clock算法为每个页又增加了一个修改位。选择页面时，尽可能选择既未使用又没有修改页面。存储器管理主题知识讲座第66页改进型Clock置换算法页面：（访问位A，修改位M）有四种不一样情形：1类(A=0,M=0）既未访问，又没有修改，最正确淘汰页2类(A=0,M=1）未访问，不过有修改，效率低淘汰页3类(A=1,M=0）被访问，但没有修改4类(A=1,M=1）既被访问，又有修改存储器管理主题知识讲座第67页改进型Clock置换算法算法：指针从当前位置开始，开始第一轮扫描循环队列，寻找未使用且没有修改过页面（第1类页面），找到则可换出。假如找不到，则开始第二轮扫描，寻找未使用但修改过页面（第2类页面），而且每经过一个页面时，将其访问位A设置为0。假如找到一个第2类页面，则可换出。假如依旧未找到适当换出页面，则此时指针回到初始位置，且全部页面其访问位A为0。再转回（1）继续工作。存储器管理主题知识讲座第68页存储器管理主题知识讲座第69页

5.最不惯用算法(LFU,LeastFrequentlyUsed)

目标选择到当前时间为止被访问次数最少页面被置换；实现方法1每个页面设置移位存放器：被访问时左边最高位置1，定时右移而且最高位补0，这么，在最近一段时间内时用最少页面将是ΣRi最小页。实现方法2每页设置访问计数器，每当页面被访问时，该页面访问计数器加1；发生缺页中止时，淘汰计数值最小页面，并将全部计数清零。存储器管理主题知识讲座第70页软件模拟LRU老化算法存储器管理主题知识讲座第71页6.页面缓冲算法(pagebuffering)

采取可变分配和局部置换，置换算法为FIFO。它是对FIFO算法发展，经过被置换页面缓冲，有机会找回刚被置换页面；被置换页面选择和处理：由操作系统中专门页面置换进程，用FIFO算法选择被置换页，把被置换页面放入两个链表（空闲页面链表和已修改页面链表）之一。假如页面未被修改，就将其归入到空闲页面链表末尾不然将其归入到已修改页面链表。存储器管理主题知识讲座第72页页面替换算法总结算法原理算法性能使用标准最优算法替换最久不会被使用页面最正确算法无法实现NRU算法简单利用RM位进行页面分类粗糙设计不会实用FIFO式算法依据进入内存时间选择替换页面常识推断逐步形成现实科研方法LRU算法局部性原理推断靠近最优设计高消耗、高性能NFU&老化算法软件模拟LRU最可能LRU有效实现现实算法工作集算法/时钟算法基于全局分析局部性选择最可信（看起来）设计最优异有效算法存储器管理主题知识讲座第73页

4.7*请求分页系统性能分析

缺页率对有效访问时间影响工作集抖动产生原因和预防方法存储器管理主题知识讲座第74页

缺页率(pagefaultrate)缺页率表示“缺页次数/内存访问次数”(比率)或“缺页平均时间间隔倒数”；缺页率影响原因分配给进程页面数目：数目越多－>缺页率越低。页面数目标下限，应该是一条指令及其操作数可能包括页面数目标上限，以确保每条指令都能被执行。存储器管理主题知识讲座第75页

缺页率对有效访问时间影响

假定缺页概率为P，则有效访问时间能够表示为：有效访问时间=(1-P)*ma+P*缺页中止时间其中，ma代表访问存放器时间(10ns~数百ns)。有效访问时间=（1-p)*0.1+p*25000结论：若使有效访问时间延长不超出10%，缺页中止就要小于0.0000004。降低缺页中止；提升I/O速度。存储器管理主题知识讲座第76页

工作集(workingset)

实践证实,一个进程在一段时间内访问到页数是比较确定，系统只需按这个页数分配对应页面数即可。超出这个页面数，进程缺页次数不会降低多少，低于这个数却会使进程缺页次数急剧增加，称这些页面为工作集(workingset)

。基本思想：依据程序局部性原理，普通情况下，进程在一段时间内总是集中访问一些页面，这些页面称为活跃页面，假如分配给一个进程物理页面数太少了，使该进程所需活跃页面不能全部装入内存，则进程在运行过程中将频繁发生中止。存储器管理主题知识讲座第77页

工作集(workingset)

假如能为进程提供与活跃页面数相等物理页面数，则可降低缺页中止次数。对于给定访问序列选取定长区间，称为工作集窗口，落在工作集窗口中页面集合称为工作集。内容取决于页三个原因访页序列特征时刻Ti窗口长度(△)存储器管理主题知识讲座第78页

工作集(workingset)

存储器管理主题知识讲座第79页

抖动产生原因和预防方法抖动产生原因（抖动现象）内存中引入过多进程，造成多道程序度过高每个进程并发执行时对内存进行访问，经常出现缺页情况开启置换策略将某个（一些）页面换出，调入新页继续访问时发觉，又用到刚才调出页面，又引发缺页中止存储器管理主题知识讲座第80页存储器管理主题知识讲座第81页抖动预防采取局部置换策略：仅允许进程在本身范围内进行置换，不影响其它进程在CPU调度程序中引入工作集算法：调入新作业时，应该检验每个进程在内存中驻留集是否足够大L=S准则：产生缺页平均时间L=系统处理进程缺页平均时间S挂起若干进程：使一些低优先级进程进程挂起，从而腾出内存空间存储器管理主题知识讲座第82页分页系统实现问题分析OS运行过程中何时需要考虑与分页相关操作？进程创建：为进程创建并初始化页表，在磁盘交换区中分配空间进程运行：占用CPU时，需更新MMU、刷新TLB页面失效：经过PC确定引发缺页中止页面，然后进行物理页帧分配进程终止：释放页表、页面、磁盘交换空间，共享页面需要保留指令备份与页面锁定页面失效处理流程：硬件陷入－状态保留－缺页中止－页面替换－恢复运行指令备份作用：缺页中止准确位置难以确定，备份PC内容可确保恢复进程运行时正确性页面锁定用途：I/O设备DMA传输与CPU并行工作，不能被换出后备存放磁盘交换区作用：页面替换时暂时保留物理页面磁盘空间磁盘交换区空间管理：进程创建时分配（固定）、页面替换时分配（动态）磁盘交换区实现：OS提供暂时磁盘文件、需要考虑内存增加、信息统计存储器管理主题知识讲座第83页“策略”与“机制”分离思索页面调度策略用户空间程序负责独立于OS内核实例1：Mach实例2：Minix分页管理机制MMU内部细节OS缺页中止处理分离优缺点分析模块化、灵活性增加系统运行开销存储器管理主题知识讲座第84页第四章存放器管理4.1存放器存放层次4.2程序装入和链接4.3连续分配方式4.4基本分页存放管理方式4.5基本分段存放管理方式4.6虚拟存放器基本概念4.7请求分页存放管理方式4.8页面置换算法4.9请求分段存放管理方式存储器管理主题知识讲座第85页4.9请求分段存放管理方式请求分页系统建立虚拟存放器，是以页面为单位进行换入、换出操作。在请求分段系统中实现虚拟存放器，以分段为单位进行换入和换出。程序在运行之前，只需要装入必要若干个分段即可运行。当访问分段不在内存时，可由OS将所缺乏段调入内存。存储器管理主题知识讲座第86页4.9.1请求分段中硬件支持1.段表机制段名段长段基址存取方式访问字段A修改位M存在位P增补位外存始址需要在进程段表中添加若干项：–存取方式：标识本段存取属性。如读R，写W，执行X–访问字段A：统计本段使用频繁程度–修改位：是否在调入内存后做过修改–存在位：本段是否装入内存–增补位：该段是否动态增加过，在请求页式中没有该位–外存地址存储器管理主题知识讲座第87页2.缺段中止机构要有专门缺段中止处理程序。特点：–指令和操作数必定不会跨越在段边界上。–因为段长度是不固定，处理比缺页系统复杂。–调入一个段可能要淘汰几个内存中段。存储器管理主题知识讲座第88页图4-31请求分段系统中中止处理过程存储器管理主题知识讲座第89页3.地址变换机构

请求分段系统地址变换机构，是在分段系统地址变换机构基础上形成。因为分段可能不在内存，所以会引发缺段中止。先将需要段调入内存，修改段表，然后再利用段表进行地址变换。存储器管理主题知识讲座第90页图4-32请求分段系统地址变换过程存储器管理主题知识讲座第91页4.9.2分段共享与保护

在多道程序系统中，尤其在分时系统中，数据共享是很主要在分段系统中，各共享进程应能访问被共享段在共享中必须小心处理一个问题是共享段保护问题存储器管理主题知识讲座第92页1.共享段表图4-33共享段表项为了实现共享，可在系统中配置一张段表，全部共享段都在共享段表中占有一表项。表项中统计了共享段段号、段长、内存始址、存在位等信息，并统计有共享此分段每个进程情况。存储器管理主题知识讲座第93页存储器管理主题知识讲座第94页段动态链接与共享存储器管理主题知识讲座第95页2.共享段分配与回收分配第一个请求进程，由系统分配一物理块，调入共享段，设置相关表项信息，并置count=1以后进程，在自己段表中增加一项，添入共享段信息；在共享段表项中做count=count+1，填写进程相关信息回收做count=count–1假如count=0，则将该共享段回收存储器管理主题知识讲座第96页3.分段保护越界检验在进行存放访问时，要将逻辑地址段号与段表长度进行比较，假如超出则发生越界中止信号；其次，将段内地址与段表中该段长度进行比较，假如有效才进行转换，不然产生越界中止信号。存储器管理主题知识讲座第97页3.分段保护存取控制检验：用于要求对该段访问权限。通常访问方式有：读：允许用户对该段/页内任何信息或其副本进行读操作。写：允许用户修改该段/页内任何信息直至撤消整个段/页。执行：用户能够执行该段/页程序，数据段/页除外。增加：用户可在段/页末尾添加信息，但不允许修改已存在于段/页中信息。存储器管理主题知识讲座第98页3.分段保护环境保护护检验是一个功效较完善保护机制。思想：将全部程序分成不一样级别，分别放置在不一样环上。内环（编号小，在内侧）程序含有高优先权，外环程序优先权低。操作系统关键安排在0环内；主要程序和操作系统服务安排在中间环；普通应用程序安排在外环。一个程序能够直接访问在相同环或低优先级环（比本身相对靠外环）上数据一个程序访问高优先级（比自己靠内环）时，经过系统调用方式实现存储器管理主题知识讲座第99页

调用返回调用返回环0环1环2

环2环1环0数据访问数据访问(a)程序间控制传输(b)数据访问图4-34环境保护护机构存储器管理主题知识讲座第100页本章重点

程序装入和链接程序装入内存三个步骤：编译、链接、装入装入三种方式：绝对装入方式可重定位装入方式动态运行时装入方式链接三种方式：静态链接方式装入时动态链接运行时动态链接

单道、编译时完成多道、装入时完成多道、运行时完成存储器管理主题知识讲座第101页

连续分配方式单一连续分配固定分区分配动态分区分配可重定位分区分配对换（SWAPPING）基本分页、分段存放管理方式页、物理块与段地址变换机构（快表）两种管理方式区分段页式存放方式单用户、单任务多道、划分用户空间多道、分区分配算法多道、支持内存紧凑与动态分区分配类似存储器管理主题知识讲座第102页

虚拟存放器局部性原理特征：屡次性、对换性、虚拟性、离散性页面置换算法最正确置换算法（Optimal）先进先出页面置换算法（FIFO）最近最久未使用置换算法（LRU）

CLOCK置换算法最少使用置换算法（LFU）页面缓冲算法（PBA）请求分页、分段存放管理方式存储器管理主题知识讲座第103页第四章测验最正确适应算法空白区是——。

A.按大小递减次序排列

B.按大小递增次序排列

C.按地址由大到小排列

D.按地址由小到大排列程序经编译或汇编以后形成目标程序，其中指令次序是以0作为参考地址进行编址这些地址称为——。存储器管理主题知识讲座第104页在可变式分配方案中，某一作业完成后，系统收回其主存空间，并与相邻空闲区合并，为此需修改空闲区表，造成空闲区数减1情况是——。

A.无上邻空闲区，也无下邻空闲区

B.有上邻空闲区，但无下邻空闲区

C.有下邻空闲区，但无上邻空闲区

D.有上邻空闲区，也有下邻空闲区在存放器可重定位分区存放管理中，作业装入内存时，采取是——重定位方式。存储器管理主题知识讲座第105页作业在执行中发生了缺页中止，经操作系统处理后，应让其执行——指令。

A.被中止前一条B.被中止那一条

C.被中止后一条D.开启时第一条某虚拟存放器系统采取页式内存管理，使用LRU页面替换算法，考虑下面页面访问地址流：1、8、1、7、8、2、7、2、1、8、3、8、2、1、3、1、7、1、3、7假定内存容量为4个页面，开始时是空，则页面调用次数是——。

A.4B.5C.6D.7存储器管理主题知识讲座第106页在固定分区分配中，每个分区大小是——。

A.相同

B.随作业长度改变

C.能够不一样但预先固定

D.能够不一样但依据作业长度固定分页系统中页面是为——。

A.用户所感知B.操作系统所感知

C.编译系统所感知D.连续装配程序所感知存储器管理主题知识讲座第107页采取分段存放管理系统中，若地址用24位表示，其中8位表示段号，则允许每段最大长度是——。

A.B.C.

D.请求分页系统中一个进程访问页面次序为0，2，1，3，0，2，4，0，2，1，3，4。利用FIFO算法，当进程使用3个页框时缺页——次，使用4个页框时缺页——次。（中科院）存储器管理主题知识讲座第108页本题说明：分配页框数量多，缺页中止不一定少。存储器管理主题知识讲座第109页虚拟存放管理系统基础是程序——理论。

A.局部性B.全局性

C.动态性D.虚拟性支持程序存放在不连续内存中存放管理方法有——。（西安电子科技大）

A.可变式分区分配B.多重分区分配

C.分页式分配D.分段式分配

E.段页式分配存储器管理主题知识讲座第110页考虑下面段表：

那么逻辑地址（2，88）对应物理地址是——；逻辑地址（4，100）对应物理地址是————。（西北工业大）某虚拟存放器中用户空间共有32个页面，每页1KB，主存16KB。假定某时刻系统为用户第0、1、2、3页分别分配物理块号为5、10、4、7，虚地址0A6F对应物理地址为——————。（中科院）存储器管理主题知识讲座第111页某操作系统采取分区存放管理技术。操作系统在低址占用了100KB空间，用户区主存从100KB处开始占用512KB。初始时，用户区全部为空闲，分配时截取空闲区低址部分作为已分配区。在执行了以下申请、释放操作序列后：

reg（300KB）reg（100KB）release（300KB）

reg（150KB）reg（50KB）reg（90KB）采取首次适用算法，主存中有哪些空闲区？采取最正确适应算法，内存中有哪些空闲区？若随即又要申请80KB，针对上述两种情况会产生什么后果？说明了什么问题？存储器管理主题知识讲座第112页采取首次适用算法，主存中空闲区以下：空闲区1首地址390KB，大小10KB；空闲区2首地址500KB，大小112KB；采取最正确适用算法，主存中空闲区以下：空闲区1首地址340KB，大小60KB；空闲区2首地址550KB，大小62KB；首次适用最正确适用存储器管理主题知识讲座第113页若随即又申请80KB，则对于采取首次适用算法能够分配成功，而对于采取最正确适用算法则不能成功。这个结果说明采取首次适用算法，是尽可能利用存放器低地址部分空闲区，这么可尽可能保留在高地址部分有大空闲区。一旦有较大作业要装入时，便有希望找到可供使用空闲区。存储器管理主题知识讲座第114页16、有一矩阵VarA：array[1..100,1..100]ofinteger以行为先序进行存放。有一个虚存系统，物理内存共4页，其中两页用来存放程序（常驻内存），其余两页用于存放数据。每页大小为200个字节。假设程序已在内存中占两页，其余两页空闲，对于程序A或程序B：程序A程序Bfori:=1to100doforj:=1to100doforj:=1to100dofori:=1to100doA[i,j]:=0;A[i,j]:=0;若每个整数占2个字节，程序A和程序B执行过程各会发生多少次缺页？若每个整数占4个字节，程序A和程序B执行过程各会发生多少次缺页？以上说明了什么问题？存储器管理主题知识讲座第115页每个整数占两个字节，主存有两页，可存放两行内容。对于程序A，每访问一行产生一次缺页中止，中止次数为100。对于程序B，每访问一个单元产生一次缺页中止，中止次数为100×100=10000；每个整数占4个字节，则矩阵一行需要占两个页面。对于程序A，每访问一行产生两次缺页中止，中止次数为2×100=200，对于程序B，依然是每访问一个单元产生一个缺页中止，中止次数为100×100=10000；本题说明：程序编制方法和程序执行次序对缺页中止次数有很大影响，而且减小页面大小不一定能降低缺页中止次数。存储器管理主题知识讲座第116页17.有个一虚拟存放系统,某个进程在内存占有3个物理块,刚开始时均为空.有以下访页序列:2、3、4、5、3、4、1、2、3、5、1、4、2、4、5、1、3、2、1、3试给出以下情形下缺页次数:(1)系统采取先进先出(FIFO)淘汰算法.(2)系统采取最近最少使用(LRU)淘汰算法.(3)系统采取优化(OPT)淘汰算法.存储器管理主题知识讲座第117页18.有一个虚拟存放系统采取最近最少使用（LRU）页面淘汰算法，每个作业占3页主存，其中一页用来存放程序和变量i,j（不作它用）.每一页可存放150个整数变量.某作业程序以下：(Pascal语言描述）

VARA:ARRAY[1..150,1..100]OFinteger;i,j:integer;FORi:=1to150DOFORj:=1to100DOA[i,j]:=0;

设变量i,j放在程序页中，初始时，程序及变量i,j已在内存，其余两页为空.矩阵A按行序存放.

（1）试问当程序执行完后，共缺页多少次？（2）最终留在内存中是矩阵A哪一部分？存储器管理主题知识讲座第118页19.请比较分页、分段虚拟存放管理方案基本工作原理:相关使用数据结构；缺页（段）中止处理机制过程；及可能碰到性能问题和处理方法.存储器管理主题知识讲座第119页20.在叙述一个页面置换算法时，一位作者用一个在循环轨道上往返移动雪犁机来模拟说明雪均匀地落在轨道上，雪犁机以恒定速度在轨道上不停循环，轨道上被扫落雪消失。（1）我们讨论哪种算法可用此例模拟？（2）这个模拟说明了该替换算法哪些行为？存储器管理主题知识讲座第120页21.一个32位地址计算机使用两级页表，虚地址被分为9位顶级页表域；11位二级页表域和偏移，请问，页面长度是多少？在地址空间中，共存在多少页？存储器管理主题知识讲座第121页22.一个计算机有4个页帧，装入时间、上次访问时间和每个页面R位、M位以下所表示（时间以时钟滴答为单位）：页面装入时间上次访问时间RM012628010123026501214027000311028511

请问：

1）NRU算法将置换哪个页面？2）FIFO算法将置换哪个页面？

3）LRU算法将置换哪个页面？4）第二次机会算法将置换哪个页面？存储器管理主题知识讲座第122页存储器管理主题知识讲座第123页存储器管理主题知识讲座第124页存放管理实例存储器管理主题知识讲座第125页段页式结合：Multics系统段页式结合实现思想一个逻辑段可能很大，难以全部放在内存中，假如在段中深入分页，则能够处理这一问题寻址采取“段表＋页表＋页面”方式TLB（16项）中保留是页表项信息，支持硬件高速缓存地址结构“段地址（18位）＋页地址（18位）＋页内偏移（10位）”，地址总线宽度为24位段页式结合实现过程操作系统查询段表，确定是否需要进行缺段处理假如段存在于内存中，则深入查询页表，进行缺页处理最终将页面置换到内存中，供进程使用存储器管理主题知识讲座第126页段页式结合：IntelPentiumIntelPentium段页式特色使用32位地址空间实现纯段式、纯页式、段页式三种管理方式关键管理数据结构：LDT（每个用户程序有一个）和GDT（全局共享一个）寻址方式：“段选择符——段存放器——段描述符——经映射取得物理地址”存储器管理主题知识讲座第127页IntelPentium寻址方式IntelPentium存放管理方式纯分段式：“段描述符”中“G”位为0，则用20位描述段长度，最大1MB纯分页式：“段描述符”中“Base”域为0，“Limit”域为“1111”二级页表目录：“页表目录（10Bit）＋页表（10Bit）＋页表项（12Bit）”存储器管理主题知识讲座第128页VxWorks系统内存管理存储器管理主题知识讲座第129页VxWorks系统内存管理嵌入式实时系统经典内存布局硬件相关内存区：起始地址用来保留硬件相关信息、初始堆栈等信息操作系统内存区：用来保留操作系统映象、Tornado工具（加载运行目标程序）用户程序内存区：用来保留用户程序映象，实现特定应用目标VxWorks内存管理机制介绍内存管理单位：内存块——内存池——内存分区系统开启时，创建一个包含系统内存池系统内存分区用户程序与操作系统处于同一地址空间内，程序设计实现时必须确保内存不越界内存分配与管理机制类似于Minix，采取动态、自由链表管理方法VxWork中内存分配、回收默认情况下，用户程序申请内存分配都来自于“SystemMemPool”用户程序也能够创建属于自己内存分区，这个内存分区能够在SystemMemPool中，也能够在扩充内存条中，也能够在CPURAM板中系统以“块”为单位管理内存，内存分配采取“动态链表”＋“最先适配”内存回收时将相邻空闲内存块合并为可用内存分区这类管理方式不能消除内存外零头，即使存在影响效率原因，不过应用环境单一存储器管理主题知识讲座第130页Windows系统内存管理Windows中内存管理基本概念采取“进程－线程”两层机制，其中“进程”只是空壳，而“线程”则是调度和管理单位存放体系物理层次为“磁盘文件——磁盘页面文件——物理内存——TLB”存放体系逻辑层次为“线程——进程——内存管理器——分页/非分页管理机制”Professional内存划分（用户2GB，系统2GB），Server则为（用户3GB，系统1GB）Windows中内存管理机制内存管理器：包含六个运行在关键态管理组件进程VAD自平衡二叉树：每个进程都有一个VAD树，用于描述已经分配给线程虚拟空间系统内存管理机制：一个非分页缓冲池和多个分页缓冲池，供OS设备驱动程序使用用户内存管理机制：公共堆分配、默认私有堆分配、私有堆分配、页面文件分配物理内存管理机制：PFN（页框号数据库）负责统计并维护物理内存页帧信息Windows内存管理机制认识与了解非常复杂内存管理体系，复杂到设计者本身都不敢随意更改集成了分页/非分页、工作集、后备存放、TLB、进程/线程模型等全部当代OS概念存储器管理主题知识讲座第131页Windows内存管理器组件工作集管理器（MmWorkingSetManager）当空闲区低于某一界限时，便开启全部内存管理策略，比如工作集修整、老化、已修改页面写回等，最大程度确保系统运行高效进程/堆栈交换器（KeSwapProcessOrStack）完成进程和内核线程堆栈换入和换出操作已修改页面写回器（MiModifiedPageWriter）将修改链表上“脏”页写回到映射文件（后备存放）中映射页面写回器（MiMappedPageWritter）将映射文件中脏页写回磁盘废弃段线程（MiDereferenceSegmentThread）负责系统高速缓存和页面文件扩大和缩小零页线程（MmZeroPageThread）将空闲链表中页面清零存储器管理主题知识讲座第132页Windows中内存布局应用程序代码全程变量每个线程堆栈DLL代码

7FFFFFFF80000000内核和执行体HAL

引导驱动程序

C0000000进程页表

超空间

C0800000系统高速缓存分页缓冲池未分页缓冲池00000000FFFFFFFF3GB用户空间1GB系统空间BFFFFFFF00000000FFFFFFFF在boot.ini中加入／3GB标志存储器管理主题知识讲座第133页Windows中系统地址空间布局系统代码包含操作系统映像、HAL和用于引导系统设备驱动程序系统映射视图用来映射Win32子系统可加载关键态Win32k.sys，以及它使用关键态图形驱动程序会话空间用来映射一个用户会话信息进程页表和页目录描述虚拟地址映射结构超空间一个特殊区域用来映射进程