《操作系统》第4章存储管理

《操作系统》第4章存储管理4.1存储管理概述存储管理是指存储器资源（主要指内存并涉及外存）的管理。存储器资源的组织（如内存的组织方式）地址变换（逻辑地址与物理地址的对应关系维护）虚拟存储的调度算法2023/3/202存储组织存储器的功能是保存数据，存储器的发展方向是高速、大容量和小体积。内存在访问速度方面的发展：DRAM、SDRAM、SRAM等；硬盘技术在大容量方面的发展：接口标准、存储密度等；存储组织是指在存储技术和CPU寻址技术许可的范围内组织合理的存储结构。微机中的存储层次组织：访问速度越慢，容量越大，价格越便宜；最佳状态应是各层次的存储器都处于均衡的繁忙状态（如：缓存命中率正好使主存读写保持繁忙）；2023/3/203存储层次结构高速缓存：DataCacheTLB(TranslationLookasideBuffer)内存：DRAM,SDRAM等；外存：软盘、硬盘、光盘、磁带等；高速缓存主存外存cpu可访n+k~几百knM~几百Mn+M~nG(G=1kn)2023/3/204存储管理目的方便用户，使用户减少甚至摆脱对存储器使用的管理。提高内存资源的利用率，关键是实现内存共享。现代操作系统可区分两类主存：物理主存共享的基础；由0～（m－1）个物理地址组成。逻辑主存主存以分片方式实现共享：按区分配：根据实际需要划分为大小不等的区域。按页分配：划分为大小相等的块。2023/3/205存储管理的功能主存储空间的分配和回收（静态、动态）地址转换主存储空间的保护保护操作系统占有的主存区保护各程序的私有主存区保护可供多个程序访问的主存共享区主存储空间的共享主存储器资源的共享某一主存区域的共享主存储空间的扩充2023/3/206重定位（地址映射）逻辑地址（相对地址，虚地址）：用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式。其首地址为0，其余指令中的地址都相对于首地址来编址。不能用逻辑地址在内存中读取信息。物理地址（绝对地址，实地址）：内存中存储单元的地址。物理地址可直接寻址。2023/3/207作业的名字空间、逻辑地址空间和装入后的物理空间符号源程序目标代码可执行代码汇编编译连接地址重定位名字空间地址空间存储空间:x=x+1::R=XR=R+1X=R:0:K100:100+K:R=XR=R+1X=R:2023/3/208地址重定位地址重定位：将虚拟空间中已链接和划分好的内容装入内存，并将虚拟地址映射为内存地址的问题。称之为地址重定位或地址映射。实现地址映射的方式（对可执行程序）：

直接定位：早期单道系统中静态重定位动态重定位2023/3/209静态重定位在可执行文件中，列出各个需要重定位的地址单元和相对地址值。当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后不再转换（一般在装入内存时由软件完成）。即：装入时根据所定位的内存地址去修改每个重定位地址项，添加相应偏移量。

评价:优点：不需硬件支持，可以装入有限多道程序缺点：一个程序通常需要占用连续的内存空间，程序装入内存后不能移动。不易实现共享。2023/3/2010说明：重定位表中列出所有修改的位置。如：重定位表的150表示相对地址150处的内容为相对地址(即100为从0起头的相对位置)。在装入时，要依据重定位后的起头位置(2000)修改相对地址。重定位修改：重定位表中的150->绝对地址2150(=2000+150)内容修改：内容100变成2100(=100+2000))。2023/3/2011动态重定位动态地址映射是在程序执行时由系统硬件完成从逻辑地址到物理地址的转换的。动态地址映射是由硬件地执行时完成的，程序中不执行的程序就不做地址映射的工作，这样节省了CPU的时间。重定位寄存器的内容由操作系统用特权指令来设置，比较灵活。实现动态地址映射必须有硬件的支持，并有一定的执行时间延迟。现代计算机系统中都采用动态地址映射技术。2023/3/2012优点：OS可以将一个程序分散存放于不连续的内存空间，可以移动程序，有利用实现共享。能够支持程序执行中产生的地址引用，如指针变量（而不仅是生成可执行文件时的地址引用）。缺点需要硬件支持（通常是CPU），OS实现较复杂。它是虚拟存储的基础。2023/3/2013存储保护在多道程序设计的环境下，系统中有系统程序和多个用户程序同时存在，如何保证用户程序不破坏系统程序，用户程序之间不相互干扰？这就是存储保护所要解决的问题。常用的存储保护有两种：越界保护－范围上下界保护；基址、限长寄存器保护。存贮键保护－存贮权限2023/3/2014虚拟存储器局部性原理(principleoflocality)：指程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域。还可以表现为：时间局部性：一条指令的一次执行和下次执行，一个数据的一次访问和下次访问都集中在一个较短时期内；空间局部性：当前指令和邻近的几条指令，当前访问的数据和邻近的数据都集中在一个较小区域内。2023/3/2015局部性原理的具体体现程序在执行时，大部分是顺序执行的指令，少部分是转移和过程调用指令。过程调用的嵌套深度一般不超过5，因此执行的范围不超过这组嵌套的过程。程序中存在相当多的循环结构，它们由少量指令组成，而被多次执行。程序中存在相当多对一定数据结构的操作，如数组操作，往往局限在较小范围内。2023/3/2016虚拟存储的基本原理在程序装入时，不必将其全部读入到内存，而只需将当前需要执行的部分页或段读入到内存，就可让程序开始执行。在程序执行过程中，如果需执行的指令或访问的数据尚未在内存（称为缺页或缺段），则由处理器通知操作系统将相应的页或段调入到内存，然后继续执行程序。另一方面，操作系统将内存中暂时不使用的页或段调出保存在外存上，从而腾出空间存放将要装入的程序以及将要调入的页或段。只需程序的一部分在内存就可执行。2023/3/2017为用户提供一种不受物理存储器结构和容量限制的存储器的技术称为虚拟存储器，或称虚拟存储技术。虚拟存储器的核心：让程序的访问地址（虚地址）和主存的可用地址（实地址）相脱离。在多道运行环境下，操作系统把实际主存扩充成若干个虚存，系统为每个用户建立一个虚存。实现虚拟存储技术需要的物质基础：需要有相当容量的辅存；要有一定容量的主存；地址变换机构。 引进虚存后必须在地址变换上花费开销，所以，在设计虚拟存储器时，应力求地址变换能快速进行。2023/3/2018虚拟存储技术的特征虚存容量不是无限的，极端情况受内存和外存可利用的总容量限制虚存容量还受计算机总线地址结构限制速度和容量的“时空”矛盾，虛存量的“扩大”是以牺牲CPU工作时间以及内外存交換时间为代价的2023/3/20194.2简单的存储管理单一连续区存储管理基本原理：这是最早出现的一种存储管理方式。在主存中仅驻留一道程序，整个用户区为一用户独占。当用户作业空间大于用户区时，该作业不能装入。这种分配方式仅能用于单用户、单任务的操作系统中，不能用于多用户系统和单用户多任务系统中。2023/3/2020单一连续区存储管理主存空间的分配与回收地址转换与存储保护2023/3/2021单一连续区存储管理管理特点（1）管理简单。它把主存分为两个区，用户区一次只能装入一个完整的作业，且占用一个连续的存储空间。它需要很少的软硬件支持，且便于用户了解和使用。（2）在主存中的作业不必考虑移动的问题，并且主存的回收不需要任何操作。（3）资源利用率低。不管用户区有多大，它一次只能装入一个作业，这样造成了存储空间的浪费，使系统整体资源利用率不高。（4）这种分配方式不支持虚拟存储器的实现。2023/3/2022分区存储管理系统把内存用户区划分为若干分区，分区大小可以相等，也可以不等。一个进程占据一个分区。固定分区可变分区2023/3/2023固定式分区把内存划分为若干个固定大小的连续分区分区大小相等分区大小不等固定分区存储管理方式是最早使用的一种可运行多道程序的存储管理方式。它仍然要求把作业全部装入主存，且装入一个连续的存储空间。

2023/3/2024区号大小 起址 标志 116KB 20K 已分配232KB 36K 已分配364KB 68K 已分配4124KB132K 未分配(a)分区说明表0k：

20k：

第1分区（16kb）36k：

第2分区（32kb）

（已分配）68k：

第3分区（64kb）（已分配）132k：

第4分区（124kb）（未分配）

256k：（b）内存分配图操作系统作业A（16k）作业B（26k）作业C（56k）在处理作业前，固定划分区域。每个作业占一个分区，作业连续存放。2023/3/2025固定式分区优点：易于实现，开销小。缺点：内碎片造成浪费分区总数固定，限制了并发执行的程序数目。2023/3/2026固定式分区地址转换与存储保护一对上限/下限寄存器B下限寄存器逻辑地址CPU绝对地址操作系统区用户分区1用户分区2用户分区3B+L2上限寄存器<B+L2越界中断2023/3/2027可变式分区动态创建分区：在装入程序时按其初始要求分配，或在其执行过程中通过系统调用进行分配或改变分区大小。2023/3/2028当有作业完成后释放所占用的存储区。在系统运行的过程中，系统中形成多个空闲的不连续的存储区，称为空闲区。这些空闲区可以被其他作业使用，但由于空闲区和容纳的作业的大小不一定正好相等，因而这样剩余的空闲区域变得很小。当系统运行相当长一段时间后，主存中会出现一些更小的空闲区。2023/3/2029分区存储管理技术的实现：地址映射动态存储管理的机构（数据结构）空闲区表、空闲区链分区的分配和回收三种基本的放置策略2023/3/2030可变分区存储管理地址转换与存储保护一对基址/限长寄存器B基址寄存器逻辑地址CPU绝对地址操作系统区空闲分区1用户作业1空闲分区2L2限长寄存器<L2越界中断2023/3/2031分区分配算法分区分配算法：寻找某个空闲分区，其大小需大于或等于程序的要求。若是大于要求，则将该分区分割成两个分区，其中一个分区为要求的大小并标记为“占用”，而另一个分区为余下部分并标记为“空闲”。分区的先后次序通常是从内存低端到高端。分区释放算法：需要将相邻的空闲分区合并成一个空闲分区。(这时要解决的问题是：合并条件的判断和合并时机的选择)2023/3/2032最先匹配法(first-fit)：按分区的先后次序，从头查找，找到符合要求的第一个分区该算法的分配和释放的时间性能较好，较大的空闲分区可以被保留在内存高端。但随着低端分区不断划分而产生较多小分区，每次分配时查找时间开销会增大。最佳匹配法(best-fit)：找到其大小与要求相差最小的空闲分区从个别来看，外碎片较小，但从整体来看，会形成较多外碎片。较大的空闲分区可以被保留。最坏匹配法(worst-fit)：找到最大的空闲分区基本不留下小空闲分区，但较大的空闲分区不被保留。2023/3/2033这三种放置算法的优劣很难区分，要具体情况具体分析。例如：某时刻系统中有三个空闲区其大小和首址为：(35KB，100KB)、(12KB，156KB)、(28KB，200KB)有一作业系列：(JOB1，12KB)、(JOB2，30KB)、(JOB3，28KB)2023/3/20342023/3/2035回收算法当一个进程（或程序）释放某内存区时，要调用存储区释放算法release,它将首先检查释放区是否与空闲区表（队列）中的其它空闲区相邻，若相邻则合并成一个空闲区，否则，将释放为一个空闲区插入空闲区表（或队列）中的适当位置。

空闲释放区与空闲区相邻有四种情况。2023/3/2036A、将r合并到f1，f1.addr;f1.size+r.size=>f.sizeB、将r合并到f2,r.addr;r.size+r.size=>f2.sizeC、f1、r、f2合并到f1,f1.addr;f1.size+r.size+f2.size=>f1.size撤消f2空闲区D、r作为一个空闲区，并插入到空闲区表的适当位置2023/3/2037碎片问题及拼接技术碎片：在已分配区之间存在着的一些没有被充分利用的空闲区。拼接技术：移动存储器中某些已分配区中的信息，使本来分散的空闲区连成一个大的空闲区。拼接时机的选择：某个分区回收时立即进行；当找不到足够大的空白区，而空白区的存储容量总和却可以满足作业需要时进行。2023/3/2038拼接技术的缺点：消耗系统资源；拼接时必须停止所有其他的工作；拼接需要重新定义已存入主存的作业。2023/3/2039分区管理的优缺点优点：实现了主存共享设计实现简单，系统开销小缺点：利用不充分，有碎片要求作业连续存放2023/3/2040覆盖和交换覆盖（overlay）引入：其目标是在较小的可用内存中运行较大的程序。常用于多道程序系统，与分区存储管理配合使用。原理：一个程序的几个代码段或数据段，按照时间先后来占用公共的内存空间。2023/3/2041将程序的必要部分（常用功能）的代码和数据常驻内存；可选部分（不常用功能）在其他程序模块中实现，平时存放在外存中（覆盖文件），在需要用到时才装入到内存；不存在调用关系的模块不必同时装入到内存，从而可以相互覆盖。(即不同时用的模块可共用一个分区)2023/3/2042注：另一种覆盖方法：(100K)A(20K)占一个分区：20K；B(50K)、D(20K)和E(40K)共用一个分区：50K；F(30K)和C(30K)共用一个分区：30K；2023/3/2043覆盖（overlay）缺点：编程时必须划分程序模块和确定程序模块之间的覆盖关系，增加编程复杂度。从外存装入覆盖文件，以时间延长来换取空间节省。实现：函数库（操作系统对覆盖不得知），或操作系统支持2023/3/2044交换(swapping)引入：多个程序并发执行，可以将暂时不能执行的程序送到外存中，从而获得空闲内存空间来装入新程序，或读入保存在外存中而目前到达就绪状态的进程。交换单位为整个进程的地址空间。常用于多道程序系统或小型分时系统中，与分区存储管理配合使用。又称作"对换"或"滚进/滚出(roll-in/roll-out)"；程序暂时不能执行的可能原因：处于阻塞状态，低优先级（确保高优先级程序执行）；2023/3/2045交换(swapping)原理：暂停执行内存中的进程，将整个进程的地址空间保存到外存的交换区中（换出swapout），而将外存中由阻塞变为就绪的进程的地址空间读入到内存中，并将该进程送到就绪队列（换入swapin）。优点：增加并发运行的程序数目，并且给用户提供适当的响应时间；编写程序时不影响程序结构缺点：对换入和换出的控制增加处理机开销；程序整个地址空间都进行传送，没有考虑执行过程中地址访问的统计特性。考虑的问题：程序换入时的重定位；减少交换中传送的信息量，特别是对大程序；对外存交换区空间的管理：如动态分区方法；2023/3/2046覆盖与交换的区别覆盖由用户解决空间不足交换由系统解决空间不足覆盖中被覆盖的那部分，既使未被破坏也不能使用，要重新调用。而交换中在界地址寄存器的保护下次可使用。2023/3/20474.3分页式存储管理分区存储管理的主要问题是碎片问题。在采用分区存储管理的系统中，会形成一些非常小的分区，最终这些非常小的分区不能被系统中的任何用户（程序）利用而浪费。造成这样问题的主要原因是用户程序装入内存时是整体装入的，为解决这个问题，提出了分页存储管理技术。2023/3/2048基本思想将程序的逻辑地址空间和物理内存划分为固定大小的页或页面(pageorpageframe)，程序加载时，分配其所需的所有页，这些页不必连续。需要CPU的硬件支持。2023/3/2049页表2023/3/2050地址变换机构虚地址结构：虚地址是用户程序中的逻辑地址，它包括页号和页内地址（页内位移）。

区分页号和页内地址的依椐是页的大小，页内地址占虚地址的低位部分，页号占虚地址的高位部分。假定页面大小1024字节，虚地址共占用2个字节(16位)页号页内地址（位移量）

PW1510902023/3/20512023/3/2052页式地址映射2023/3/20531.虚地址（逻辑地址、程序地址）以十六进制、八进制、二进制的形式给出将虚地址转换成二进制的数；按页的大小分离出页号和位移量（低位部分是位移量，高位部分是页号）；根据题意产生页表；将位移量直接复制到内存地址寄存器的低位部分；以页号查页表，得到对应页装入内存的块号，并将块号转换成二进制数填入地址寄存器的高位部分，从而形成内存地址。2023/3/20542.虚地址以十进制数给出页号＝虚地址/页大小位移量＝虚地址%页大小根据题意产生页表；以页号查页表，得到对应页装入内存的块号内存地址＝块号×页大小＋位移量2023/3/2055例1：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、A、5块，试将虚地址0AFEH，1ADDH转换成内存地址。虚地址0AFEH0000101011111110P＝1W＝01011111110MR＝0100101011111110＝4AFEH2023/3/2056虚地址1ADDH0001101011011101P＝3W＝01011011101MR＝0010101011011101＝2ADDH2023/3/2057例2：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、10、5块，试将虚地址7145，3412转换成内存地址。2023/3/2058虚地址3412P＝3412/2048＝1W＝3412%2048＝1364MR=9*2048+1364=19796虚地址3412的内存地址是：197962023/3/2059虚地址7145P＝7145/2048＝3W＝7145%2048＝1001MR=5*2048+1001=11241虚地址7145的内存地址是：112412023/3/2060采用相应技术加快页表的查询速度快表:因页面较多，页表在内存，取一次数要访问内存两次。所以采用硬件分析。建立一个快表仅存放当前运行作业的部分页表。2023/3/2061例：设访问主存时间为200ns,访问联想存贮器为40ns，命中率为90％，则平均存取时间为多少？解：查页表两次访存：平均为200＋200＝400ns查快表(200+40)×90％＋(200+200+40)×10％＝256ns方法1：方法2：2023/3/2062多级页表结构对页表本身也采取分页措施。即把页表本身按固定大小分成为一个个页面两级页表系统将32位逻辑地址空间的地址分成三段：其中，页表目录号（外层页号p1）和页号（外层页内地址p2）两项各占10位，偏移量（页内地址d）占12位。每页的大小为4KB。由于物理块号和页表的物理地址都占4个字节，使每页中包含1024个页表项，所以页表目录和页表的大小也都是4KB，即一页。在80386中设置了一个外层页表寄存器（CR3），用于存放页表目录的基址。2023/3/2063存储保护四种保护方式：①禁止做任何操作，②只能执行，③只能读，④能读/写，当要访问某页时，先判断该页的存取控制和存储保护信息是否允许。添加了存取控制信息的页表表目如下图所示：2023/3/20644.4请求分页存储管理目标：实现小内存大作业实现方法：作业运行时，只将当前的一部分装入内存其余的放在辅存，一旦发现访问的页不在主存中，则发出缺页中断，由o.s将其从辅存调入主存，如果内存无空块，则选择一个页淘汰。2023/3/2065请求式分页存储管理的地址重定位时，可能会出现所需页面不在主存的情况，此时，系统必须解决以下两个问题：（1）当程序要访问的某页不在内存时，如何发现这种缺页情况？发现后应如何处理？（2）当需要把外存上的某个页面调入内存时，此时内存中没有空闲块应怎么办？2023/3/2066扩充的页表结构为了实现请求分页技术，页表应增加相应的内容，反映该页是否在内存，在外存的位置，在内存的时间的长短等。如何发现缺页2023/3/2067发现后应如何处理？缺页中断在请求分页系统中，每当所要访问的页面不在内存时，便要产生一缺页中断，请求OS将所缺页调入内存。与一般中断的主要区别在于：缺页中断在指令执行期间产生和进行处理，而不是在一条指令执行完毕之后。所缺的页面调入之后，重新执行被中断的指令。一条指令的执行可能产生多次缺页中断，如：swapA,B而指令本身和两个操作数A,B都跨越相邻外存页的分界处，则产生6次缺页中断。2023/3/2068查快表有登记无登记查页表登记入快表发缺页中断在主存在辅存形成绝对地址继续执行指令重新执行被中断指令恢复现场调整页表和主存分配表装入所需页面主存有空闲块保护现场有选择调出页面该页是否修改未修改已修改把该页写回辅存相应位置操作系统硬件逻辑地址无2023/3/2069没有空闲块应怎么办页面淘汰算法当要索取一页面并送入到全满的内存中时，必须把已在内存中的某一页淘汰掉。用来选择淘汰哪一页的规则叫做淘汰算法。系统抖动–––内外存交换频繁使效率下降(导致系统效率急剧下降的主、辅存之间的频繁转换现象)2023/3/2070页面淘汰算法最优算法（OPT算法）最理想的页面置换算法是：从内存中移出以后不再使用的页面；如无这样的页面，则选择以后最长时间内不需要访问的页。这就是最优算法的思想。这种算法本身不是一种实际的方法，因为页面访问的顺序是很难预知的。但是，可把它作为一种评价标准，比较其他实用方法的优劣，所以，最优算法只具有理论上的意义。2023/3/2071页面淘汰算法先进先出算法（FIFO算法）这种算法的基本思想是：总是先淘汰那些驻留在内存时间最长的页面，即先进入内存的页面先被置换掉。理由是：最先进入内存的页面不再被访问的可能性最大。优点：实现简单。缺点：常用的也会被淘汰。2023/3/2072页面淘汰算法最久未使用算法（LRU算法）这种算法的实质：当需要淘汰一页时，选择最长时间未使用的页。依据的理论是如果某页被访问，它可能马上还要被访问；相反，如果某页长时间未被访问，它可能最近也不可能被访问。该算法实现起来比较困难，因为要为每一页设置一特定单元来记录自上次访问后到现在的时间量t，并选择t值最大的页淘汰。2023/3/2073页面淘汰算法LRU算法的近似实现最近未使用算法（NRU）：是LRU和FIFO的折衷一个引用标志位，定期清零时钟算法2023/3/2074页面淘汰算法最不常用页面调度算法(LFU） 选择到当前时间为止被访问次数最少的页面被置换；近似实现算法：淘汰最近一段时间内最不常用的页面每页设置访问计数器，每当页面被访问时，该页面的访问计数器加1；发生缺页中断时，淘汰计数值最小的页面，并将所有计数清零；2023/3/2075例子1：计算缺页次数某程序在内存中分配三个页面，初始为空，页面走向为4，3，2，1，4，3，5，4，3，2，1，5。FIFO432143543215页1432143555211页243214333522页34321444355

xxxxxxx

xx共缺页中断9次2023/3/2076LRU432143543215页1432143543215页243214354321页34321435432

xxxxxxx

xxx共缺页中断10次2023/3/2077OPT432143543215页1432111555211页243333333555页34444444444

xxxx

x

xx

共缺页中断7次2023/3/2078页面淘汰算法两点讨论页表中修改位的作用?分配个作业的内存块数越多，缺页次数会减少吗？注：FIFO页面淘汰算法会产生异常现象，当分配给作业的内存块数增加时，缺页次数反而增加2023/3/2079影响缺页次数的因素(1)分配给进程的物理页面数(2)页面本身的大小(3)程序的编制方法(4)页面淘汰算法2023/3/2080分页式存储管理的评价

优点(1)由于它不要求作业或进程的程序段和数据在内存中连续存放，从而有效地解决了碎片问题。(2)动态页式管理提供了内存和外存统一管理的虚存实现方式，使用户可以利用的存储空间大大增加。这既提高了主存的利用率，又有利于组织多道程序执行。2023/3/2081缺点(1)要求有相应的硬件支持。例如地址变换机构，缺页中断的产生和选择淘汰页面等都要求有相应的硬件支持。这增加了机器成本。(2)增加了系统开销，例如缺页中断处理等。(3)请求调页的算法如选择不当，有可能产生抖动现象。(4)虽然消除了碎片，但每个作业或进程的最后一页内总有一部分空间得不到利用。如果页面较大，则这一部分的损失仍然较大。2023/3/20824.5分段存储管理程序的分段结构┇调用X段的入口E┇调用Y段的入口F┇调用数组段A[16]┇主程序段┇E：┅┅┅┅┅┅┇子程序段X┇F：┅┅┅┅┅┅┇子程序段Y┇┇┇数组段A┇┇┇工作区段2023/3/2083基本原理作业的地址空间由若干个逻辑分段组成，每个分段都有自己的名字，对于一个分段而言，它是一个连续的地址区。在主存中，每个分段占一个分区。一个用户程序往往由几个程序段（主程序、子程序和函数）所组成，当一个程序装入内存时，按段进行分配，每个段的大小是不相等的。程序地址的组成：(S,W)

段号S段内地址W2023/3/2084地址转换段表始址