《计算机操作系统课件第三章课件.ppt》由会员分享，可在线阅读，更多相关《计算机操作系统课件第三章课件.ppt（38页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三章 存储管理 主存中必须同时驻留操作系统和一个或多个执行进程。存储管理负责给各个进程分配内存，同时保护已分配的内存不被其他进程非法访问。存储管理也负责保护分给操作系统的内存，防止未授权的访问。存储管理不仅是软件任务。操作系统需要硬件支持来实现复杂的存储管理方案。所以，操作系统的一些设计问题也是硬件设计问题。通常，用户不能直接访问存储管理硬件，而是由操作系统单独负责对它的控制。3.1 存储管理的基本概念3.1.1 存储管理研究的课题 存储管理主要研究课题归纳为四个方面:存储分配问题:重点是研究存储共享和各种分配算法。地址再定位问题:研究各种地址变换机构，以及静态和动态再定位方法。存储保护问题
2、:研究保护各类程序、数据区的方法。存储扩充问题:主要研究虚拟存储器问题及其各种调度算法。3.1.2 地址再定位 名地址:对程序员来说数据的存放地址是由符号决定的,故称为符号名地址或简称名地址,源程序的地址空间称为符号名空间或简称名空间。相对地址:由于编译程序无法确定目标代码在执行时所驻留的实际内存地址,故一般总是从“0”号单元开始为其编址,并顺序分配所有的符号名所对应的地址单元。它们都不是真实的内存地址故称为相对地址、逻辑地址或虚拟地址。绝对地址(物理地址或实地址)：CPU直接访问的内存地址，称为绝对地址。一个逻辑地址空间的程序装入到物理地址空间时,由于两个空间不一致，需要进行地址变换，或称地
3、址映射，即地址的再(重)定位。地址再定位有两种方式：静态再定位和动态再定位。1.静态地址再定位静态再定位是在程序执行之前进行再定位。这一工作由装配程序完成。优点：实现容易，无需硬件支持。缺点：程序经地址再定位后就不能再移动了，因而不能重新分配内存，不利于内存的有效利用。程序在存储空间中只能连续分配，不能分布在内存的不同区域。若干用户很难共享内存中的同一程序。2.动态地址再定位 动态地址再定位是在程序执行期间，在每次存储访问之间进行的。动态重定位可使装配模块不加任何修改而装入内存，但是它需要硬件定位寄存器的支持。优点：在执行过程中，用户程序在内存中可以移动，这有利于内存的充分利用。程序不必连续存
4、放在内存中，可分布在内存的若干不同区域。若干用户可以共享同一程序。缺点：需硬件支持，实现存储管理的算法比较复杂。3.1.3 虚拟存储器 由操作系统(在一定硬件的支持下)把两级存储器(主存和辅存)实施统一管理,达到“扩充”主存的目的,呈现给用户一个远远大于主存储容量的编程空间,即虚拟空间。这一点是以时间(CPU用于主、辅存之间信息交换所作管理的时间开销)换空间(存储空间的扩大)而达到的。虚存的最大容量由计算机的地址结构确定。虚存容量与主存大小没有直接关系,虚存容量可以比实存大,也可以比实存小,在多道环境下,一个系统可以为每个用户建立一个虚存,每个用户可以在自己的地址空间(最大容量为虚存容量)内编
5、程。逻辑容量=内存+外存运行速度内存速度成本外存 3.2 早期的存储管理3.2.1 单一连续分配优点：易于实现。缺点：仅适用于单道程序。单一连续分配用户作业 主存可用空间时，怎么办？覆盖技术：用户把一个程序划分成不同的程序段并规定好它们的执行和覆盖顺序(覆盖描述文件)，连同目标程序一起提交系统。操作系统根据覆盖结构完成程序段之间的覆盖。采用覆盖技术的程序模块结构和程序运行时的内存结构:系统操作过程：首先把A、B、F装入内存中;当A运行到调用C时,才将C装入到覆盖区0,自动地将B覆盖,同时将D装入覆盖区1,自动地将F覆盖;当C运行到调用E时,再将E装入到覆盖区1,自动地将D覆盖。3.2.2 分区
6、分配1.固定式分区法固定式分区法是在系统生成时就将主存划分为若干个分区,每个分区的大小可以不等,但事先必须固定,以后不能改变。系统操作方法：调度作业时，由内存管理程序根据作业所需内存量，在分区说明表中找到一个足够大的空闲分区分配给它，然后用重定位装入程序将此作业装入。若找不到，则通知作业调度模块，另外选择一个作业。缺点：一个作业的大小不可能刚好等于某个分区的大小，于是在每个分配的分区中总有一部分被浪费。2.可变式分区法可变式分区法是在作业装入和处理过程中建立的分区，并且要使分区的容量能正好适应作业的大小。内存初始分配情况 可变式分区管理举例(假设操作系统所用内存空间20KB)：内存分配变化过程
7、分区号分区容量分区位置状态18KB20KB已分配2-空项350KB44KB已分配4-空项516KB232KB已分配-空项已分配的分区状态表(最终)分区号分区容量分区位置状态116KB28KB可用2138KB94KB可用38KB248KB可用-未分配的分区状态表(最终)可变式分区中请求一个分区的流程可变式分区中释放一个分区的流程可变分区的分配和回收算法 分配算法 空白区组织方式(每次回收要调整空闲表的排列)最佳适应(Best Fit)算法:从全部空闲区中找出能满足作业需求的容量最小的空闲区分配之。优点：选用的空白区容量最接近分配容量。缺点：可能产生大量碎片。空白区按其容量以递增的次序排列。(由小
8、到大)最差适应(Worst Fit)算法:从全部空闲区中找出能满足作业需求的容量最大的空闲区分配之。优点：速度快，剩余空间可供再分配的概率较大。缺点：各空白区比较均匀地减少,工作一段时间后就不能满足对于较大空白区的分配要求。空白区按其容量以递减的次序排列。(由大到小)最先适应(First Fit)算法:把最先找到的满足需求的空闲区分配之。优点：高地址留有较多或较大空白区以备分配。缺点：搜索次数增加，影响工作效率。空白区按地址大小递增顺序排列。例:某基于动态分区存储管理的计算机,其主存容量为55MB(初始为空),采用最佳适配算法,分配和释放的顺序为:分配15MB,分配30MB,释放15MB,分配
9、8MB,分配6MB,此时主存中最大空闲分区的大小?固定式分区和可变式分区分配的优点：有助于多道程序设计;不受过多的硬件限制，只需要界地址寄存器，用于存储保护;所采用的算法大都比较简单，易于实现;固定式分区和可变式分区分配的缺点：会产生一些碎片，这些碎片散布在存储器的各处，不能集中使用，因而降低了存储器的有效利用;分区的大小受到主存容量的限制，这种方法无法扩充主存容量。3.3 分页存储管理3.3.1 分页原理 因为用户作业地址空间的起点与分区的物理位置无关，所以作业的地址空间通常从0开始。分页存储管理就是从逻辑地址空间到物理地址空间的一种变换。页面：逻辑地址空间划分为一些相等的片段，称之为“页面
10、”。块：物理地址空间被划分为同样大小的片段，称之为“块”。页的大小块的大小;(页的大小通常是2的幂)一个作业若有m个页，要为它分配m个块，每页装入一块，但这些块并不一定是相互邻接的。例：作业1、作业2和作业3的地址空间分别被划分为2、3、1个页面，每个页面大小为1KB。10KB的物理地址空间被划分为10块，逻辑地址空间与物理地址空间的对应关系由称为页面变换表的PMT(简称页表)指出。3.3.2 地址变换机构 为了实现从逻辑地址空间到物理地址空间的地址变换，在硬件上必须提供一套地址变换机构。1.动态地址变换机构DAT若有效地址是24位，逻辑地址可达16MB。假设页面大小为4KB，则逻辑地址空间最
11、多可达4096个页面。即：12位为页号，12位为页内地址。动态地址变换机构自动将所有地址划分为页号和页内地址两部分。利用PMT表将页号代之以块号，就得到了要使用的物理存储地址。假定某作业的一条取数指令由处理机产生一个有效地址为：002090h它表示该地址为页2的144号单元。从有效地址到物理地址的变换过程如下：物理地址=块号块长+页内地址=007090h页面变换表每个作业的页面变换表由页面变换寄存器(PMTAR)指出。PMTAR指出了该作业页面变换表的起始地址。当处理机执行一个新作业或恢复一个旧作业时，只要修改PMTAR的内容使之指向要执行作业的PMT起始地址即可。3.3.3 分页存储管理算法
12、 为实现分页管理,在软件方面建立作业表(JT)存储分块表(MBT)页面变换表(PMT),并由操作系统实施管理。当有一个作业进入系统时,就在作业表上登记页表长度及状态信息,并为PMT表分配一个存储区,然后将PMT表的起始地址填入作业表中。然后搜索存储分块表,如有空闲块则将作业号填入存储分块表的相应表项，再把存储块号填入PMT表。3.3.4 分页存储管理方案的评价 分页存储管理方案不必执行费时的靠拢操作，消除了碎片，便于多道程序设计，提高了处理机和主存的利用率。但仍然存在如下严重缺点：采用动态地址变换会增加计算机成本和降低处理机速度。各种表格占用一定容量的主存空间，还要花费一部分处理机时间来建立和
13、管理这些表格。虽然说消除碎片，但每个作业的最后一页仍不能充分利用。存储扩充问题仍没有得到解决。当没有足够的可用空间能装下整个作业地址空间时，该作业还是无法运行。3.4 请求分页存储管理 请求分页存储管理系统又称页式虚拟存储系统。请求分页技术可以实现主存的扩充，它为每个用户提供一个虚拟存储器，其地址空间远比主存的存储空间大，一个作业的地址空间存在于一个虚拟存储器中。把作业地址空间划分的页称为虚页。主存称为实存，在实存中的块称为实页。3.4.1 请求分页原理一、基本思想l 运行一个作业时并不把该作业的全部程序和数据都装入内存,可以只把目前要执行的几页调入内存的空闲块中(程序执行的局部性原理),其余
14、仍保留在外存,以后根据作业的需要再调入内存。l 此时的页表描述子应分别指明在外存、内存的页码，并具有调入、调出的保障机制。l 以透明的方式提供给用户一个比实际内存大得多的作业地址空间。它不是任何实际的物理存储器,而是一个容量非常大的存储器的逻辑模型。l 以处理机提供的逻辑地址访问虚拟存储器,用户可在非常大的地址空间中放心地安排自己的程序和数据,就仿佛他真的拥有这么大的内存空间一样。采用两级存储方式，一级存储器为内存，二级存储器为外存，操作系统在两个存储器之间调度。在虚拟存储系统中，外存可以看作是内存的扩充。二、PMT的扩充 辅存页表又称外页表，用来指出该作业的各虚页在辅存上的位置。当作业被调入
15、主存开始运行时，系统为其建立一张页表PMT，并将辅助页表中的各项复制过来。改变位:=0/1表示该页未修改/已修改,用于决定该页淘汰时是否写入辅存。引用位:=1 表示该页最近被访问过。可用于决定先淘汰谁。状态位:=0/1表示该页在主存/辅存。将某一页从实存移到辅存称为“出页”，从辅存调入实存称为“入页”，入页与出页的操作称为“分页”操作。对某页反复进行入页和出页的现象称为“抖动”，也叫做系统颠簸。缺页中断的发生及其处理3.4.2 页面置换算法1.先进先出算法(First-in First-out,FIFO)选择驻留内存时间最长的一页淘汰。理由：先入者不再使用的可能性较大。2.最近最久未用置换算法
16、(Least Recently Used,LRU)选择离当前时间最近的一段时间内最久没有被使用过的页面先淘汰。理由：若一页刚被访问过，很可能最近还要访问之，反之则反。通过周期性地对“引用位”进行检查，并利用它来记录一页自上次被访问以来所经历的时间t,淘汰时选择t最大的页。实际使用成本过高。3.LRU近似算法该算法需要在存储分块表MBT(或页表PMT)中设“引用位”，当存储分块表中的页被访问时，该位由硬件自动置“1”,而由页面管理软件周期(T)地把所有引用位置“0”。在时间T内，被访问过的页面的引用位为“1”,未被访问过的页面的引用位为“0”。淘汰时选择引用位为“0”的页先淘汰。4.理想型淘汰算
17、法OPT(optimal replacement algorithm)该算法淘汰在访问串中将来再也不出现的或是在离当前最远的位置上出现的页面(在最长的时间以后才需要访问的页面)。OPT算法由于必须预先知道每一个进程的指令访问串，所以是无法实现的。但是可以用来比较其他算法的优劣。3.4.3 性能分析 欲访问的页面不在主存中，称为缺页故障或页面失效。缺页故障次数占全部访问页面数的百分比，即为页面失效率。f=(缺页次数访问页面)100%为分析主存容量与缺页中断次数的关系，引入页面走向这一概念。程序严格地按顺序执行的指令序列称为程序的执行轨迹;每条指令在执行时所访问的单元地址称为地址轨迹;这些地址所在
18、的页面称为页面轨迹或页面走向。例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
19、+341+23512F+缺页中断发生次数:F=10,访问页面数:T=12,缺页率:f=F/T=10/12=83%OPT法性能分析(M=3):(淘汰在最长的时间以后才需要访问的页面)时刻123456789101112P432143543215M44343 24 31431431435435435235215215F+缺页中断发生次数: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):时刻1234567
20、89101112P432143543215M4+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+2344 12334125+341453134512+3451+2345+123F+缺页中断发生次数:F=8,访问页面数:T=12,缺页率:f=F/T=8/12=67%时刻123456789101112P432143543215M4434 3243
21、214 3214321432 543254325432513251325F+OPT法性能分析(M=4):(淘汰在最长的时间以后才需要访问的页面)缺页中断发生次数:F=6,访问页面数:T=12,缺页率:f=F/T=6/12=50%在P=11时,如果预知页面走向则在淘汰时不选5,而选4,则P=12时就不发生缺页中断。由实验和测试发现FIFO算法的内存利用率不高,这是因为该算法是基于CPU按线性顺序访问地址空间的这个假设。其实有些在内存中停留时间长的页往往也是经常被访问的。一般情况下,如果分给一作业或进程的内存页面数越接近它所要求的页面数,则发生缺页的次数会越少。但是，使用FIFO算法时，在未给进程
22、或作业分配足它所要求的页面数时，有时会出现分配的页面数增多，缺页次数反而增加的奇怪现象。这种现象称为Belady现象。3.4.4请求分页存储管理方案的评价 请求分页存储管理保留了分页存储管理的全部优点,特别是它解决了消除碎片的问题。此外,它还有如下优点:它提供了大容量的多个虚拟存储器,作业地址空间不再受实存容量的限制;更有效地利用了主存,一个作业的地址空间不必全部同时都装入主存,只装入其必要部分,其它部分根据请求装入,或根本不装入(如错误处理程序等);更加有利于多道程序的运行,从而提高了系统效率;方便了用户,特别是大作业用户。但请求分页还存在以下缺点：为处理缺页中断,增加了处理机时间的开销,即
23、请求分页系统是用时间的代价换取了空间的扩大;可能因作业地址空间过大或多道程序道数过多以及其它原因而造成系统抖动;为防止系统抖动所采取的各种措施会增加系统的复杂性。3.5.1 分段原理按作业的逻辑单位为一段来分配内存。每段分配一个连续的主存区域。与分页不同的是段的大小可变。用户或编译程序负责把程序划分成段，操作系统并不参与程序分段，硬件设置段大小的上限。程序的分段：主程序段、子程序段、数据段、工作区段。每段必须有一个唯一的段名。作业地址空间的每一个单元都用两维地址表示:3.5 分段存储管理分页管理的欠缺：固定大小的页不是作业的逻辑单位。如：一个子程序跨在两页上、一页之内既有程序也有数据等。mov
24、 ax,ds:6mov ss:50,axcall 0003:0000 在分段存储管理系统中可用类似于分页管理用过的地址变换机构,实现分段管理的地址变换。地址变换是在作业执行过程中由硬件自动完成。3.5.2 段变换表(SMT)段号容量存取权限状态起始地址访问位修改位增补位0160E040000003340E03460000SMT表格式段长(段容量):该段的长度(字节数),在虚存和实存中段长是一样的。起始地址:该段装入主存内的起始地址。状态位:表示该段是否装入主存,”0”表示该段在主存，“1”表示该段不在主存。存取控制权限:为实现段的保护而规定各段的存取权限。执行E：执行一个程序或子程序，不允许读
25、或写。读 R：允许读，不允许写或执行。写 W：允许写，不允许读或执行。当存取要求违反了段的存取权限，则发生保护中断。访问位:该段在主存并被访问过，则置访问位为“1”。置换页面时可作参考。改变位:该段被修改时置“1”。增补位:用于动态扩大段长。地址变换:分页和分段存储管理有许多相似之处,容易被搞混,但概念上完全不同。分页和分段的主要区别：u页是信息的物理单位，段是信息的逻辑单位。u页的大小固定，段的大小不固定。u分页的作业地址空间是一维的线性地址空间,分段的作业地址空间是二维的。u页式管理的逻辑地址连续。段式管理的段间的逻辑地址可不连续，分段由用户划分。3.5.3 分段存储管理方案的评价优点：消
26、除了碎片。提供了大容量的虚存。一个段的大小不能超过实存可用的空间。允许动态增加段的长度。便于动态装入和链接。每个模块分配一个段,因此可在运行过程中当调用到一程序段或数据段时进行动态装入和链接。便于对具有完整逻辑功能的信息进行共享。便于实现存储保护。(在SMT中有存取权限)缺点：进行地址变换和靠拢操作要花费处理机时间，为管理各分段要设立若干表，提供附加的存储空间。在辅存上管理可变长度的段比较困难。段的最大长度受实存容量的限制。会出现系统抖动现象。两个作业共享一个子程序(SORT)的例子：3.6 段页式存储管理用分段方法来分配和管理虚存;用分页方法来分配和管理实存。3.6.1 段页式存储管理的实现
27、一、基本思想段管理的缺点：每段必须占主存的一个连续区域，为消除零头，允许段动态增长，要化CPU大量时间移动分段。取页管理的优点取代段管理缺点。段页管理：在每段内再分页(大小相同)，内存按页的大小分块，以块为单位分配内存，允许段在内存中不连续，也不必一次全部装入。二、逻辑地址 程序的分段可由程序员或编译程序按信息的逻辑结构来划分，而分页与程序员无关，它由操作系统自动完成。地址变换中所用表格的关系段页式系统地址变换过程查找过程：虚地址：段表起址+S页表起址+P实页号+W 实地址 从逻辑地址物理地址的变换中要三次访问主存。使用联想存储器的方法可加快查表速度。若(S,P)在联想存储器中则直接找到实页号，加上页内地址就可确定物理地址;若不在，则通过查段表、页表的方法确定物理地址，并把查得的存储块号和虚地址(S,P)存入快表的空表目，如无空表目，则采用淘汰算法淘汰旧表目，写入新表目。优点方便用户设计，提高内存利用率，适用于大型通用机。缺点增加了硬件成本和系统开销。