操作系统-课件xuos

第三章存储管理

主存中必须同时驻留操作系统和一个或多个执行进程。存储管理负责给各个进程分配内存，同时保护已分配的内存不被其他进程非法访问。存储管理也负责保护分给操作系统的内存，防止未授权的访问。 存储管理不仅是软件任务。操作系统需要硬件支持来实现复杂的存储管理方案。所以，操作系统的一些设计问题也是硬件设计问题。通常，用户不能直接访问存储管理硬件，而是由操作系统单独负责对它的控制。3.1存储管理的基本概念3.1.1存储管理研究的课题存储管理主要研究课题归纳为四个方面:⑴存储分配问题:重点是研究存储共享和各种分配算法。⑵地址再定位问题:研究各种地址变换机构，以及静态和动态再定位方法。⑶存储保护问题:研究保护各类程序、数据区的方法。⑷存储扩充问题:主要研究虚拟存储器问题及其各种调度算法。3.1.2地址再定位地址空间

一个程序可以访问的地址范围称为地址空间，即程序访问信息所用的地址单元的集合。这些单元的编号称为逻辑地址。

程序的地址空间大小是由计算机体系结构决定的。例如：地址长度为16位的计算机只能访问64KB的内存。地址长度为32的计算机允许直接寻址4GB，这样的体系结构有4GB的虚拟地址空间。特定计算机上配置的实际物理内存的大小可能比地址空间小得多。由于编译程序无法确定目标代码在执行时所驻留的实际内存地址,故一般总是从“0”号单元开始为其编址,并顺序分配所有的符号名所对应的地址单元，所以地址空间中的所有地址都是相对于起始地址的，故称为相对地址，或称为逻辑地址或虚拟地址。对程序员来说数据的存放地址是由符号决定的,故称为符号名地址或简称名地址,源程序的地址空间称为符号名空间或简称名空间。地址转换一个作业装入内存时分配到的存储空间和它的地址空间是不一致的，因此作业在CPU上运行时其所要访问的指令和数据的物理地址与地址空间中的逻辑地址是不同的，如果在作业装入内存或者在它执行时不对其相对地址加以修改就会导致错误的结果。2.存储空间

存储空间是指能够访问的主存范围。一个数据在主存中的位置称为物理地址或绝对地址。存储空间的大小取决于主存的实际容量。

地址空间是逻辑地址的集合，存储空间是物理地址的集合;一个是“虚”的概念，一个是“实”的物质。

一个逻辑地址空间的程序装入到物理地址空间时,由于两个空间不一致，需要进行地址变换，或称地址映射，即地址的再(重)定位。地址再定位有两种方式：静态再定位和动态再定位。静态地址再定位 静态再定位是在程序执行之前进行再定位。这一工作由装配程序完成。优点：实现容易，无需硬件支持。缺点：⑴程序经地址再定位后就不能再移动了，因而不能重新分配内存，不利于内存的有效利用。⑵程序在存储空间中只能连续分配，不能分布在内存的不同区域。⑶若干用户很难共享内存中的同一程序。2.

动态地址再定位动态地址再定位是在程序执行期间，在每次存储访问之间进行的。动态重定位可使装配模块不加任何修改而装入内存，但是它需要硬件——定位寄存器(基址寄存器和界限寄存器)的支持。基址寄存器存放程序在内存中的起始地址,界限寄存器存放程序的终止位置。优点：⑴在执行过程中，用户程序在内存中可以移动，这有利于内存的充分利用。⑵程序不必连续存放在内存中，可分布在内存的若干不同区域。⑶若干用户可以共享同一程序。缺点：需硬件支持，实现存储管理的算法比较复杂。3.1.3虚拟存储器

由操作系统(在一定硬件的支持下)把两级存储器(主存和辅存)实施统一管理,达到“扩充”主存的目的,呈现给用户一个远远大于主存储容量的编程空间,即虚拟空间。这一点是以时间(CPU用于主、辅存之间信息交换所作管理的时间开销)换空间(存储空间的扩大)而达到的。虚存的最大容量由计算机的地址结构确定。虚存容量与主存大小没有直接关系,虚存容量可以比实存大,也可以比实存小,在多道环境下,一个系统可以为每个用户建立一个虚存,每个用户可以在自己的地址空间(最大容量为虚存容量)内编程。逻辑容量=内存+外存运行速度≈内存速度成本≈外存3.2早期的存储管理3.2.1单一连续分配优点：易于实现。缺点：仅适用于单道程序。单一连续分配用户作业>主存可用空间时，怎么办？覆盖技术：用户把一个程序划分成不同的程序段并规定好它们的执行和覆盖顺序(覆盖描述文件)，连同目标程序一起提交系统。操作系统根据覆盖结构完成程序段之间的覆盖。采用覆盖技术的程序模块结构和程序运行时的内存结构:系统操作过程：首先把A、B、F装入内存中;当A运行到调用C时,才将C装入到覆盖区0,自动地将B覆盖,同时将D装入覆盖区1,自动地将F覆盖;当C运行到调用E时,再将E装入到覆盖区1,自动地将D覆盖。3.2.2分区分配固定式分区法 固定式分区法是在系统生成时就将主存划分为若干个分区,每个分区的大小可以不等,但事先必须固定,以后不能改变。系统操作方法：调度作业时，由内存管理程序根据作业所需内存量，在分区说明表中找到一个足够大的空闲分区分配给它，然后用重定位装入程序将此作业装入。若找不到，则通知作业调度模块，另外选择一个作业。缺点：一个作业的大小不可能刚好等于某个分区的大小，于是在每个分配的分区中总有一部分被浪费。可变式分区法 可变式分区法是在作业装入和处理过程中建立的分区，并且要使分区的容量能正好适应作业的大小。内存初始分配情况

可变式分区管理举例(假设操作系统所用内存空间20KB)：内存分配变化过程

分区号分区容量分区位置状态18KB20KB已分配2------空项350KB44KB已分配4------空项516KB232KB已分配---------空项已分配的分区状态表(最终)分区号分区容量分区位置状态116KB28KB可用2138KB94KB可用38KB248KB可用------------未分配的分区状态表(最终)可变式分区中请求一个分区的流程可变式分区中释放一个分区的流程可变分区的分配和回收算法

分配算法

空白区组织方式

(每次回收要调整空闲表的排列)

最佳适应(BestFit)算法:

从全部空闲区中找出能满足作业需求的容量最小的空闲区分配之。优点：选用的空白区容量最接近分配容量。缺点：可能产生大量碎片。空白区按其容量以递增的次序排列。(由小到大)最差适应(WorstFit)算法:

从全部空闲区中找出能满足作业需求的容量最大的空闲区分配之。

优点：速度快，剩余空间可供再分配的概率较大。缺点：各空白区比较均匀地减少,工作一段时间后就不能满足对于较大空白区的分配要求。空白区按其容量以递减的次序排列。(由大到小)最先适应(FirstFit)算法:

把最先找到的满足需求的空闲区分配之。优点：高地址留有较多或较大空白区以备分配。缺点：搜索次数增加，影响工作效率。空白区按地址大小递增顺序排列。例:某基于动态分区存储管理的计算机,其主存容量为55MB(初始为空),采用最佳适配算法,分配和释放的顺序为:分配15MB,分配30MB,释放15MB,分配8MB,分配6MB,此时主存中最大空闲分区的大小?固定式分区和可变式分区分配的优点：①有助于多道程序设计;②不受过多的硬件限制，只需要界地址寄存器，用于存储保护;③所采用的算法大都比较简单，易于实现;固定式分区和可变式分区分配的缺点：①会产生一些碎片，这些碎片散布在存储器的各处，不能集中使用，因而降低了存储器的有效利用;②分区的大小受到主存容量的限制，这种方法无法扩充主存容量。3.3分页存储管理3.3.1分页原理因为用户作业地址空间的起点与分区的物理位置无关，所以作业的地址空间通常从0开始。分页存储管理就是从逻辑地址空间到物理地址空间的一种变换。页面：逻辑地址空间划分为一些相等的片段，称之为“页面”。块：物理地址空间被划分为同样大小的片段，称之为“块”。页的大小＝块的大小;(页的大小通常是2的幂)

一个作业若有m个页，要为它分配m个块，每页装入一块，但这些块并不一定是相互邻接的。这就需要操作系统为每个作业维护一个页表，页表给出该作业每一页对应的块号。例：作业1、作业2和作业3的地址空间分别被划分为2、3、1个页面，每个页面大小为1KB。10KB的物理地址空间被划分为10块，逻辑地址空间与物理地址空间的对应关系由称为页面变换表的PMT(简称页表)指出。3.3.2地址变换机构为了实现从逻辑地址空间到物理地址空间的地址变换，在硬件上必须提供一套地址变换机构。动态地址变换机构DAT若有效地址是24位，逻辑地址可达16MB。假设页面大小为4KB，则逻辑地址空间最多可达4096个页面。即：12位为页号，12位为页内地址。动态地址变换机构自动将所有地址划分为页号和页内地址两部分。利用PMT表将页号代之以块号，就得到了要使用的物理存储地址。假定某作业的一条取数指令由处理机产生一个有效地址为：002090h它表示该地址为页2的144号单元。从有效地址到物理地址的变换过程如下：物理地址=块号×块长+页内地址=007090h页面变换表每个作业的页面变换表由页面变换寄存器(PMTAR)指出。PMTAR指出了该作业页面变换表的起始地址。当处理机执行一个新作业或恢复一个旧作业时，只要修改PMTAR的内容使之指向要执行作业的PMT起始地址即可。2.二级分页系统的地址转换3.倒排页表页表设计的一个重要缺陷是页表的大小与虚拟地址空间的大小成正比。使用一级或多级页表的一种替代方法是使用一个倒排页表结构。在这种方法中，虚拟地址的页号部分使用一个简单的散列函数映射到散列表中。散列表包含一个指向倒排表的指针，而倒排表中含有页表项。通过这个结构散列表和倒排表中各有一项对应于一个实存页，而不是虚拟页。因此不论有多少进程、支持多少虚拟页，页表都只需要实存中的一个固定部分。由于多个虚拟地址可能映射到同一个散列表中，因此需要使用一种链接技术管理这种溢出。页表结构说明：页号：虚拟地址的页号部分。进程标志符：使用该页的进程。页号和进程标志符结合起来标志一个特定进程的虚拟地址空间的一页。控制位：该域包含一些标记，如有效、访问、修改以及保护和锁定信息。链指针：如果某个项没有链项，则该域为空，否则该域包含链中下一项的索引值(0–2m-1)。{对于大小为2m个页框的物理内存}倒排页表结构转换检测缓冲区每个虚存的访问可能引起两次物理内存访问：一次取相应的页表项，一次取需要的数据。因此简单的虚拟内存方案会导致存储器访问时间的加倍。为克服这个问题，大多数虚拟内存方案为页表项使用一个特殊的高速缓存，通常称做转换检测缓冲区(TranslationLookasideBuffer,TBL)。在其内存放最近用过的页表项，由此可得到分页硬件组织。给定一个虚拟地址，处理器首先检查TLB，如果需要的页表项在其中(TLB命中)，则检索页框号并形成实地址。如果没有找到需要的页表项，则处理器用页号检索进程页表，并检查相应的页表项。如果“存在位”已置位，则该页在内存中，处理器从页表项中检索页框号以形成实地址，处理器同时更新TLB使其包含这个新的页表项。如果“存在位”没有置位，则表示需要的页不在内存中，这时将产生一次存储器访问故障，称为缺页中断。这时离开硬件作用范围，调用操作系统，由操作系统负责装入所需的页，并更新页表。转换检测缓冲区的用法3.3.3分页存储管理算法为实现分页管理,在软件方面建立①作业表(JT)②存储分块表(MBT)③页面变换表(PMT),并由操作系统实施管理。当有一个作业进入系统时,就在作业表上登记页表长度及状态信息,并为PMT表分配一个存储区,然后将PMT表的起始地址填入作业表中。然后搜索存储分块表,如有空闲块则将作业号填入存储分块表的相应表项，再把存储块号填入PMT表。3.3.4分页存储管理方案的评价分页存储管理方案不必执行费时的靠拢操作，消除了碎片，便于多道程序设计，提高了处理机和主存的利用率。但仍然存在如下严重缺点：⑴采用动态地址变换会增加计算机成本和降低处理机速度。⑵各种表格占用一定容量的主存空间，还要花费一部分处理机时间来建立和管理这些表格。⑶虽然说消除碎片，但每个作业的最后一页仍不能充分利用。⑷存储扩充问题仍没有得到解决。当没有足够的可用空间能装下整个作业地址空间时，该作业还是无法运行。3.4

请求分页存储管理

请求分页存储管理系统又称页式虚拟存储系统。请求分页技术可以实现主存的扩充，它为每个用户提供一个虚拟存储器，其地址空间远比主存的存储空间大，一个作业的地址空间存在于一个虚拟存储器中。把作业地址空间划分的页称为虚页。主存称为实存，在实存中的块称为实页。3.4.1请求分页原理一、基本思想运行一个作业时并不把该作业的全部程序和数据都装入内存,可以只把目前要执行的几页调入内存的空闲块中(程序执行的局部性原理),其余仍保留在外存,以后根据作业的需要再调入内存。此时的页表描述子应分别指明在外存、内存的页码，并具有调入、调出的保障机制。以透明的方式提供给用户一个比实际内存大得多的作业地址空间。它不是任何实际的物理存储器,而是一个容量非常大的存储器的逻辑模型。以处理机提供的逻辑地址访问虚拟存储器,用户可在非常大的地址空间中放心地安排自己的程序和数据,就仿佛他真的拥有这么大的内存空间一样。采用两级存储方式，一级存储器为内存，二级存储器为外存，操作系统在两个存储器之间调度。在虚拟存储系统中，外存可以看作是内存的扩充。二、PMT的扩充辅存页表又称外页表，用来指出该作业的各虚页在辅存上的位置。当作业被调入主存开始运行时，系统为其建立一张页表PMT，并将辅助页表中的各项复制过来。改变位:=0/1表示该页未修改/已修改,用于决定该页淘汰时是否写入辅存。引用位:=1表示该页最近被访问过。可用于决定先淘汰谁。状态位:=0/1表示该页在主存/辅存。将某一页从实存移到辅存称为“出页”，从辅存调入实存称为“入页”，入页与出页的操作称为“分页”操作。对某页反复进行入页和出页的现象称为“抖动”，也叫做系统颠簸。缺页中断的发生及其处理3.4.2页面置换算法先进先出算法(First-inFirst-out,FIFO)

选择驻留内存时间最长的一页淘汰。理由：先入者不再使用的可能性较大。最近最久未用置换算法(LeastRecentlyUsed,LRU)

选择离当前时间最近的一段时间内最久没有被使用过的页面先淘汰。 理由：若一页刚被访问过，很可能最近还要访问之，反之则反。 通过周期性地对“引用位”进行检查，并利用它来记录一页自上次被访问以来所经历的时间t,淘汰时选择t最大的页。实际使用成本过高。LRU近似算法 该算法需要在存储分块表MBT(或页表PMT)中设“引用位”，当存储分块表中的页被访问时，该位由硬件自动置“1”,而由页面管理软件周期(T)地把所有引用位置“0”。在时间T内，被访问过的页面的引用位为“1”,未被访问过的页面的引用位为“0”。淘汰时选择引用位为“0”的页先淘汰。理想型淘汰算法OPT(optimalreplacementalgorithm)

该算法淘汰在访问串中将来再也不出现的或是在离当前最远的位置上出现的页面(在最长的时间以后才需要访问的页面)。OPT算法由于必须预先知道每一个进程的指令访问串，所以是无法实现的。但是可以用来比较其他算法的优劣。3.4.3性能分析欲访问的页面不在主存中，称为缺页故障或页面失效。缺页故障次数占全部访问页面数的百分比，即为页面失效率。

f=(缺页次数÷访问页面)×100%为分析主存容量与缺页中断次数的关系，引入页面走向这一概念。程序严格地按顺序执行的指令序列称为程序的执行轨迹;每条指令在执行时所访问的单元地址称为地址轨迹;这些地址所在的页面称为页面轨迹或页面走向。例1:设页面走向为P=4,3,2,1,4,3,5,4,3,2,1,5,实页面数M=3。置换算法采用FIFO、LRU和OPT时，试计算各方法的页面失效率。FIFO法性能分析(M=3):时刻123456789101112P432143543215M4+3+42+341+234+123+415+345345342+531+25125F+++++++++缺页中断发生次数:F=9,访问页面数:T=12,缺页率:f=F/T=9/12=75%LRU法性能分析(M=3):时刻123456789101112P432143543215M4+3+42+341+234+123+415+344533452+341+23512F++++++++++缺页中断发生次数:F=10,访问页面数:T=12,缺页率:f=F/T=10/12=83%OPT法性能分析(M=3):(淘汰在最长的时间以后才需要访问的页面)时刻123456789101112P432143543215M443432431431431435435435235215215F++++

+++缺页中断发生次数:F=7,访问页面数:T=12,缺页率:f=F/T=7/12=58%例2:设页面走向为P=4,3,2,1,4,3,5,4,3,2,1,5,实页面数M=4。置换算法采用FIFO、LRU和OPT时，试计算各方法的页面失效率。FIFO法性能分析(M=4):时刻123456789101112P432143543215M4+3+42+341+234123412345+1234+5123+4512+3451+2345+123F++++

++++++缺页中断发生次数:F=10,访问页面数:T=12,缺页率:f=F/T=10/12=83%LRU法性能分析(M=4):时刻123456789101112P432143543215M4+3+42+341+234412334125+341453134512+3451+2345+123F++++

++++缺页中断发生次数:F=8,访问页面数:T=12,缺页率:f=F/T=8/12=67%时刻123456789101112P432143543215M4434

32432143214321432543254325432513251325F++++

+

+

OPT法性能分析(M=4):(淘汰在最长的时间以后才需要访问的页面)缺页中断发生次数:F=6,访问页面数:T=12,缺页率:f=F/T=6/12=50%在P=11时,如果预知页面走向则在淘汰时不选5,而选4,则P=12时就不发生缺页中断。

由实验和测试发现FIFO算法的内存利用率不高,这是因为该算法是基于CPU按线性顺序访问地址空间的这个假设。其实有些在内存中停留时间长的页往往也是经常被访问的。一般情况下,如果分给一作业或进程的内存页面数越接近它所要求的页面数,则发生缺页的次数会越少。但是，使用FIFO算法时，在未给进程或作业分配足它所要求的页面数时，有时会出现分配的页面数增多，缺页次数反而增加的奇怪现象。这种现象称为Belady现象。3.4.4 请求分页存储管理方案的评价请求分页存储管理保留了分页存储管理的全部优点,特别是它解决了消除碎片的问题。此外,它还有如下优点:⑴它提供了大容量的多个虚拟存储器,作业地址空间不再受实存容量的限制;⑵更有效地利用了主存,一个作业的地址空间不必全部同时都装入主存,只装入其必要部分,其它部分根据请求装入,或根本不装入(如错误处理程序等);⑶更加有利于多道程序的运行,从而提高了系统效率;⑷方便了用户,特别是大作业用户。但请求分页还存在以下缺点：⑴为处理缺页中断,增加了处理机时间的开销,即请求分页系统是用时间的代价换取了空间的扩大;⑵可能因作业地址空间过大或多道程序道数过多以及其它原因而造成系统抖动;⑶为防止系统抖动所采取的各种措施会增加系统的复杂性。3.5.1分段原理按作业的逻辑单位为一段来分配内存。每段分配一个连续的主存区域。与分页不同的是段的大小可变。用户或编译程序负责把程序划分成段，操作系统并不参与程序分段，硬件设置段大小的上限。程序的分段：主程序段、子程序段、数据段、工作区段。每段必须有一个唯一的段名。作业地址空间的每一个单元都用两维地址表示:3.5

分段存储管理分页管理的欠缺：固定大小的页不是作业的逻辑单位。如：一个子程序跨在两页上、一页之内既有程序也有数据等。 movax,ds:[6] movss:[50],ax call0003:0000

在分段存储管理系统中可用类似于分页管理用过的地址变换机构,实现分段管理的地址变换。地址变换是在作业执行过程中由硬件自动完成。3.5.2段变换表(SMT)段号容量存取权限状态起始地址访问位修改位增补位0160E04000000……………………3340E03460000SMT表格式段长(段容量):该段的长度(字节数),在虚存和实存中段长是一样的。起始地址:该段装入主存内的起始地址。状态位:表示该段是否装入主存,”0”表示该段在主存，“1”表示该段不在主存。存取控制权限:为实现段的保护而规定各段的存取权限。 执行E：执行一个程序或子程序，不允许读或写。 读R：允许读，不允许写或执行。 写