《操作系统原理》第四章 存储管理.ppt

1、第四章 存储管理,存储管理内容,概述 各种存储管理方案 单一用户（连续区）存储管理 分区式存储管理 分页式存储管理 分段式存储管理 段页式存储管理,一、概 述,存储器管理：对内存的管理 单道程序系统，主存被划分成两部分： 一部分供操作系统使用， 一部分供当前正在执行的程序使用。 多道程序系统，存储器的”用户”部分必须进一步地细分，以适应多个进程的要求。细分的任务由操作系统动态实现，称作存储器管理。,内存管理的目的,操作系统的“方便”性 便于用户装入程序，无须了解底层细节 可实现动态的存储空间伸缩，适应不同程序的需要 操作系统的“合理”性 合理分配内存空间，保证多道程序的顺利运行 合理保护内存空

2、间，防止各种可能的破坏泄漏 操作系统的“有效性” 有效保持内存空间的可用性，防止对资源的浪费 有效实现“小空间大容量”，提高计算机的适应性 有效配合CPU的调度过程，实现系统运行的稳定,存储器管理功能,1、内存分配和回收：系统应能记住每个存储区的状态；实施存储器的分配；回收系统或用户释放的存储区。 2、地址转换或重定位：使多道程序能动态地共享内存，最好能共享内存中的信息 3、内存保护和共享： 内存保护：如何防止地址越界或操作越权？ 内存共享：代码和数据共享 4、内存扩充：借助于虚拟存储技术或其他覆盖和交换技术，为用户提供比内存空间大的地址空间。,存储器管理中使用的几个概念,1、名字空间： 在用

3、汇编语言或高级语言编写的程序中，是通过符号名来访问子程序和数据的。我们把程序中符号名的集合叫做名字空间 2、地址空间： 一个应用程序经编译后，通常会形成若干个目标程序，这些目标程序再经过链接而形成可装入程序。这些程序的地址都是从“0”开始的，程序中的其他地址都是相对于起始地址计算的，由这些地址所形成的地址范围称为地址空间，其中的地址叫做相对地址，或逻辑地址，又叫虚地址。 地址空间的大小：由被编译的源程序决定。,3、存储空间 是指物理存储器中全部物理存储单元的集合所限定的空间。每个存储单元都有它自己的编号地址。该地址被称为绝对地址，或物理地址，或实地址。 存储空间的大小：由系统的硬件配置决定的。

4、 一个程序只有从地址空间装入到存储空间后才能运行。,4、地址重定位(Relocation) 把程序地址空间的逻辑地址转换为存储空间的物理地址的工作叫地址重定位。又叫地址映射，或地址变换。 地址重定位的原因： 地址空间的逻辑地址往往与分配到的存储空间的物理地址不一致， 而处理机执行用户程序时，所要访问的指令和数据地址必须是实际的物理地址。 装入程序：负责把用户程序由地址空间装入到存储空间。 地址重定位分：静态重定位、动态重定位。,地址转换工作是在程序执行前，由装入程序集中一次完成。 特点：无硬件变换机构；为每个程序分配一个连续的存储区；在程序执行期间不能移动，主存利用率低；难以做到程序和数据的共

5、享。,静态重定位,静态地址重定位过程,LOAD 1,300,5678,0,100,300,400,0,1000,1100,1300,1400,5678,某程序的地址空间,存储空间,装入程序,把程序装入起始地址为1000的内存区,LOAD 1,1300,动态重定位,动态重定位：装入程序把程序和数据原样装入到已分配的存储区中，然后把这个存储区的起始地址送入重定位寄存器中。在程序执行时，再将相对地址转换成绝对地址。,把程序装入起始地址为1000的内存区,0,1000,1100,1300,1400,5678,存储空间,1000,+,重定位寄存器,逻辑地址,物理地址,动态地址重定位过程,Load 1,3

6、00,动态重定位,优点： 主存利用率高。在存储区域可移动用户程序。移动后，只要修改重定位寄存器即可。 程序不必占有连续的存储空间。 便于多用户共享同一程序。,存储管理方案,单一用户（连续区）存储管理 分区式存储管理 分页式存储管理 分段式存储管理 段页式存储管理,单一用户（连续区）存储管理,单用户系统在一段时间内，只有一个进程在内存，故内存分配管理十分简单，内存利用率低。内存分为两个区域，一个供操作系统使用，一个供用户使用,早期大型机使用的内存管理方式,少数掌上电脑和嵌入式系统使用的内存管理方式,早期PC使用的内存管理方式（MS-DOS),分区存储管理,系统把内存划分成若干个分区，除了操作系统

7、占用一个分区之外，其余的每一个分区容纳一个程序。 固定式分区 可变式分区,固定式分区,预先把可分配的内存空间分割成若干个连续区域，每一区域称为分区 每个分区的大小可以相同也可以不同，分区大小固定不变，每个分区装一个且只能装一个作业 存储分配：当作业到达时，选择一个适合作业要求的空闲区分给作业，或当没有可用的空闲分区时，让其在该分区队列中等待。,让作业按大小分别排入各分区队列中等待,作业,作业,得到一个空闲分区， 就装入一个作业,分区说明表: 实现固定式分区管理，描述各分区的分配情况。 例如： 分区起始地址 分区大小 占用标志 50k 30k J1 80k 100k 0 180k 200k J2

8、 380k 132k 0 固定式分区内存使用情况表,优点：简单 缺点：主存利用不充分 因为作业的大小不可能刚好等于某个分区的大小，绝大多数已分配的分区中，都有一部分存储空间被浪费掉了，这个被浪费的空间叫做内碎片。,可变式分区,基本思想： 内存不是预先划分好的 作业装入时，根据作业的需求和内存空间的使用情况来决定是否分配 若有足够的空间，则按需要分割一部分分区给该进程；否则令其等待内存空间 各分区的大小是不定的； 内存中分区的数目也是不定的。,可变式分区(2),优点：改变了固定分区法中那种即使是小作业也要占据大分区的浪费现象，从而提高了内存的利用率。,可变式分区(3),常用的数据结构：分区说明表

9、、空闲区链表 1、分区说明表：已分配分区说明表，空闲分区说明表。 当为作业分配内存时： a.首先从空闲分区说明表中找一个足以容纳该作业的空闲区，若这个分区比较大，则一分为二，一部分分配给作业，另一部分仍作为空闲区留在表中。 b.再在已分配分区说明表中找一个空表目，填入新分配作业的信息。,始址,长度,标志,100K,10K,270K,730K,未分配,未分配,空,空,Pc 100k,10k,Pe(60k),始址,长度,标志,20K,80K,110K,60K,170K,100K,空,Pd,Pe,Pc,1M,100k,20k,110k,170k,270k,已分配分区说明表,空闲分区说明表,当作业运行

10、完成撤离系统时： 将回收的分区登记在空闲分区说明表中。 将该作业占用的已分配分区说明表置为空。 优点：比较直观、简单。 缺点：由于内存分区个数不定，所以表格长度的设置，或者表格不够用或者造成表格浪费。,2、空闲区链 为了实现对空闲分区的分配和链接，在每个空闲分区的两端设置附加信息。 (1) 状态信息： 0表示该区空闲，1表示已分配。 (2) 该区的大小(以字或块为单位)。 (3) 指针：分别指向其上或其下分区的位置。通常首字指针(又叫前向指针)指向下一分区，尾字指针(又叫后向指针)指向其上一分区位置。,字,字,可变分区分配和释放算法,最佳适应（Best Fit）算法 首次（最先）适应（Firs

11、t Fit）算法 最坏适应（Worst Fit）算法 下次适应（Next Fit）算法,最佳适应（Best Fit）算法,它从全部空闲区中找出能满足作业需求的容量最小的空闲区分配之，此法的着眼点是使碎片尽量小。 可从小到大对空闲区排序，方便查找。,首次适应（First Fit）算法,该算法要求空闲分区按地址递增的次序排列。 当进行内存分配时，把首先找到的满足需求的空闲区分配之，此法的目的在于尽量减少查找时间。 优点：当需要一个较大的分区时，有较大希望找到足够大的空闲区以满足要求。 缺点：低地址端可能留下许多很少的空闲分区，而每次查找是从低地址部分开始，会增加查找开销。,最坏适应（Worst F

12、it）算法,分配内存时，要扫描整个空闲区，找到空闲区中最大的空闲区。然后，一分为二，一部分给进程，另一部分仍作为空闲区。 想法：使剩下的空闲区仍能分配给其它进程，减少空区碎片的机会 改进：从大到小对空闲区排序，以提高查找速度。,下次适应（Next Fit）算法,将空闲区链成环形链 每次分配从上次分配的位置开始查找合适空闲区,内存回收,当作业或进程释放内存资源时，和相邻的空闲区进行链接合并，并修改可用表和自由链。 考虑：上邻、下邻、上下相邻、上下不相邻。,“碎片”问题,经过一段时间的分配回收后，内存中存在很多很小的空闲块。它们每一个都很小，不足以满足分配要求，但其总和满足分配要求。这些空闲块被成

13、为碎片（零头）。 造成存储资源的浪费,“碎片”问题解决,拼接技术：是指通过在内存移动程序，将所有小的空闲区域合并为大的空闲区域。 问题：系统开销较大,20K,0,OS,在使用,在使用,256KB-1,50K,在使用,120K,70K,拼接,存储保护,存储保护：是为了防止一个作业有意或无意地破坏操作系统或其他作业。 通常采用方法： 界限寄存器 上、下界寄存器 基址和限长寄存器 存储保护键,界限寄存器,上、下界寄存器(硬件保护法)：分别存放作业的结束地址和开始地址。在作业运行过程中，将每个访问内存的地址都同这两个寄存器的内容进行比较。正常情况下，上界寄存器内容访问地址下界寄存器内容。若超出这个范围

14、便产生保护性中断。 基址和限长寄存器：分别存放作业的起始地址及作业的地址空间长度。当作业执行时，将每个访问内存的相对地址和这个限长寄存器比较，如果超过了限长，则发出越界中断信号，并停止作业的运行。,存储保护键,方法：是给每个存储块分配一个单独的保护码，它相当于一把锁（存储块不同于分区，一个分区由若干存储块组成，每个存储块大小相同，一个分区的大小必须是存储块的整数倍）。 此外，进入系统的每个作业也被赋予一个保护键，它相当于一把钥匙。当作业运行时，检查钥匙和锁是否一致，如果二者不匹配，则系统发出保护性中断信号，停止作业运行。,内存扩充技术,在多道环境下，为了解决在较小的存储空间中运行较大程序时遇到

15、的矛盾。因此引入内存扩充技术 覆盖技术：主要用在早期的操作系统中 交换技术：被广泛用于小型分时系统中，交换技术的发展导致了虚存技术的出现,覆盖技术,把程序划分为若干个功能上相对独立的程序段，按照其自身的逻辑结构将那些不会同时执行的程序段共享同一块内存区域。 程序段先保存在磁盘上，当有关程序段的前一部分执行结束，把后续程序段调入内存，覆盖前面的程序段（内存“扩大”大） 覆盖：一个程序的若干子程序段，或几个程序的某些部分共享某一个存储空间 一般要求程序各模块之间有明确的调用结构，程序员要向系统指明覆盖结构，然后由操作系统完成自动覆盖,缺点：对用户不透明，增加了用户负担,交换技术,当内存空间紧张时，

16、系统将内存中某些进程暂时移到外存，把外存中某些进程换进内存，占据前者所占用的区域，这种技术是进程在内存与外存之间的动态调度 多用于分时系统中（roll in roll out） 对用户透明，但需要较多的软件支持,分区管理的优缺点,优点： 实现了多道程序共享主存。 实现分区管理的系统设计相对简单，不需要更多的系统软硬件开销。 实现存储保护的手段也比较简单。 缺点： 主存利用不够充分。系统中总有一部分存储空间得不到利用，这部分被浪费的空间叫碎片。 没有实现主存的扩充问题。 当作业的地址空间大于存储空间时，作业无法运行。也即作业的地址空间受实际存储空间限制。,分页式存储管理,基本思想（工作原理） 用

17、户程序划分 把用户程序按逻辑页划分成大小相等的部分，称为页。从0开始编制页号，页内地址是相对于0编址 逻辑地址 用户程序的划分是由系统自动完成的，对用户是透明的。一般，一页的大小为2的整数次幂，因此，地址的高位部分为页号，低位部分为页内地址,页号P,页内位移W,逻辑地址结构,基本思想（工作原理）,内存空间 按页的大小划分为大小相等的区域，称为内存块（物理页面，页框） 内存分配 以页为单位进行分配，并按进程的页数多少来分配。逻辑上相邻的页，物理上不一定相邻,.,.,.,.,.,.,页表：系统为了能在内存中找到每个页面对应的物理块而为进程建立一张页面映像表，简称页表。一般放在内存。 页表作用：实现

18、从页号到物理块号的地址映射。,LOAD 1,2500,0 100 1k 2k,2500 3k,8,1,2,3,1,1,2,1,0,物理块号,特征,页号,逻辑地址空间,页表,2K 2148 3K 8K,8644 9K,内存空间,8K+452=8644,2块,LOAD 1,2500,12345,12345,8块,动态地址转换,进程或作业的控制块：页表在内存的始址和页表长度还要保存在进程或作业的控制块中。 页表始址寄存器：在页式管理中，系统为每个处理机设立一个页表始址寄存器，用以记录现运行作业的页表始址和页表长度。 在作业被选中将要运行前，操作系统中负责恢复现场程序把该作业的页表始址和页表长度送入该

19、寄存器，以便地址转换时使用。,逻辑-物理地址转换,相对页号P,页内偏移地址D,15 10 9 0,页表,页表始址寄存器,页表长度,页表始址,8,452,2,452,有效（虚）地址（2500）,物 理 地 址,2148,8644,内存空间,LOAD 1,2500,12345,1、把页表始址和页表长度送入页表始址寄存器 2、若页表长度大于有效地址的页号部分时，将该地址由地址变换机构自动分成两部分；否则产生地址越界，终止程序运行。 例如：2500=2*1024+452 3、根据页表始址寄存器中的页表始址，找到作业的页表。 4、根据有效地址去访页表，获得该页所对应的物理块号。 5、将物理块号和有效地址

20、中的页内直接地址连在一起，形成访问内存的物理地址。 例：1024*8+452=8644,缺页处理,用户作业当前页面放在内存 其它页面在磁盘上 若页表中此页面不在内存（有效位=0），则发生缺页中断（陷入） 缺页中断处理程序负责把所需页面从磁盘调入内存，修改页表：特征位和物理块号,快 表,用页表地址转换过程中，要存取一个数据或一条指令至少要访问主存两次。把程序的执行速度降低一倍。 1、一次访页表，确定所存取的数据或指令的物理地址， 2、一次根据该地址存取数据或指令。 联想寄存器快表：为了提高存取速度，可在地址变换机构中增设一个具有并行查找能力的高速缓冲寄存器组，又叫联想寄存器。用来存放页表的一部分

21、。,快 表（2）,联想寄存器的存取速度比内存高，但造价也高，只能采用少量。整个系统通常只要用816个寄存器即可使程序执行速度大大提高。 快表表项 相对页号、物理块号、访问位、特征位,页表始址寄存器,逻辑地址,500 7,0 (页号） 100（页内地址）,+,页表,5（内存块号） 100（页内地址）,1,2,3,4,5,使用快表后的地址变换过程,0,1,2,3,4,5,6,5,7,9,15,13,10,16,500,每页的大小 为1024,内存地址：51024+100=5220,500+0=500,0,5,快表,越界中断,引入快表以后的地址变换过程： 同时开始两个变换过程：一个是利用内存页表进行

22、的正常变换过程；一个是利用快表进行的快速变换过程。 快表中有待查找的页号。立即停止正常的访内存页表过程，并将快表中的块号与CPU给出的页内位移相拼接，得到访问内存的绝对地址。 快表中没有要查询的页。则继续正常的转换过程，直到形成访问内存的绝对地址，还要把从内存页表中取出的块号和CPU给出的页号一起写入快表中状态位为0的一行中。若没有这样行存在，则写入访问位为0的某一行中，并同时置状态位和访问位为1。,页面交换调页方式,请求而调入请调：当需要执行某条指令而又发现它不在内存时，或当执行某条指令需要访问其他的数据或指令时，这些指令和数据不在内存中，从而发生缺页中断，系统将外存中相应的页面调入内存。

23、预测调入预调：系统对那些在外存中的页进行调入顺序计算，估计出这些页中指令和数据的执行和被访问的数据，并按此顺序将它们依次调入和调出内存。,页面交换淘汰时机,当内存中没有空闲页而作业运行又需要将新页调入内存时，就要进行页面淘汰 为了保证作业不因等待新页而中断运行，平时保证有一定数量的空闲页面，当需要的时候能够马上提供 free list,页面交换淘汰算法,抖动(thrashing)现象：也称为“颠簸”。刚被淘汰的页面马上又要用，因而又要把它调入。调入不久再被淘汰，淘汰不久再次装入。如此频繁地调入调出，降低系统的处理效率。 可能的原因： 淘汰算法问题 资源紧张问题,淘汰算法,先进先出（FIFO:

24、first in first out) 最近最久未使用淘汰算法(LRU: least recently used) 最佳（优）算法(OPT: optimum） 时钟页面置换算法（Second-Chance Algorithm） 最不频繁使用淘汰算法(LFU: least frequently used),先进先出（FIFO: first in first out),选择在内存中驻留时间最长的页并淘汰之 易实现，但效率不高。 只有在线性访问空间的时候才适用 有可能出现抖动：因为在主存时间最长的页未必是最长时间以后才被访问的页。频繁地调入调出。,最近最久未使用淘汰算法(LRU: least rec

25、ently used),因无法预测将来，所以用“最近的过去”作为“最近的将来”的近似。 根据局部性原理，淘汰那些在最近一段时间里最少使用的一页。 主要出发点是：如果某页被访问了，则它可能马上还要被访问。或者反过来说，如果某页很长时间未被访问，则它在最近一段时间也不会被访问。,最近最久未使用淘汰算法(LRU: least recently used)(2),实现方法：每页设置标志位，访问一页，则将标志位从0改到1，周期性检查，记录被访问的页面，然后把标志位全部清零。要淘汰时，选择最久未使用的页面。 缺点：所有存储块标志位重置0的周期长短不容易确定,时钟页面置换算法（Second-Chance A

26、lgorithm）,又叫第二次机会算法 实现方法：近似的LRU算法。要求在页表中增加一个引用位，以指示该页最近是否被引用。0表示最近未被引用，1表示最近正被引用。再将进城所访问的页像时钟一样放在一个循环链中，链中的节点数就是为该进程分配的主存块数。,最优算法(OPT: optimum）,淘汰以后不再需要的或最远的将来才会用到的页面 但这样的算法是不现实的，因为产生缺页时，操作系统不知道每个页的下次访问时间。通常使用这种算法去衡量所采用算法的性能好坏。,最不频繁使用淘汰算法(LFU: least frequently used),实现方法：每页设置计数器，每访问一次则计数器加1，淘汰计数值最小的

27、页。 缺点：需要计数器,减少页面交换延迟的优化方法,作业进入执行状态之前，输入并保存作业的全部信息，根据作业的执行情况，作业“分批分期”进入内存。 为了避免发生缺页中断而临时进行页面交换，可采用预淘汰算法，维护一个free list。 优化访问磁盘的次数，由于磁盘的动臂是一种机械运动，其速度是页交换延迟的主要原因。,页式存储管理的保护措施,1、程序隔离页表的作用 2、对页面的存取控制 在页表中对每个页面设置保护位，在页表结构中增加存取控制位，r、w、etc。操作中违反则触发保护性中断。,工作集,基本思想：根据程序的局部性原理，一般情况下，进程在一段时间内总是集中访问一些页面，这些页面称为活跃页

28、面，如果分配给一个进程的物理页面数太少了，使该进程所需的活跃页面不能全部装入内存，则进程在运行过程中将频繁发生中断 如果能为进程提供与活跃页面数相等的物理页面数，则可减少缺页中断次数,工作集,对于给定的访问序列取定长的区间，称为工作集窗口，落在工作集窗口中的页面集合称为工作集,工作集模型局部性,程序的局部性是虚拟存储器实现的基础，只要装入部分程序就可以运行 局部性的两方面,时间局部性,循环 子程序 栈 计数和总计的变量,空间局部性,数组遍历 代码程序的执行 靠近存放的变量定义,工作集,工作集就是根据对存储访问局部现象的观察，找出当前频繁使用的页面集合,页面故障率,进程在主存中页面的比率,随机访

29、问它的各个页的进程,做局部访问 的进程,0 0.5 1,1 0.5 0,页面故障率和页面数的关系,工作集,工作集是进程活跃地访问的页面的集合 工作集策略力求把活跃程序的工作集保存在内存里,h 时间内的工作集w,时间 h,0 h0,工作集的期望尺寸,分段式存储管理,基本思想： 用户程序划分 按程序自身的逻辑关系划分为若干个程序段，每个程序段都有一个段名，且有一个段号。段号从0开始，每一段也从0开始编址，段内地址是连续的 逻辑地址,段号,段内地址,逻辑化程序的分段形式,子程序段 X,0,E,P,数据段 A,0,116,N,1343,子程序段 Y,0,F,L,工作区B,0,P,S,B,0,S,A,0,N,Y,0,L,X,0,P,M,0,K,作业1的地址空间,1000,3200,5000,6000,8000,P,K,S,L,N,主存,操作系统,内存划分 内存空间被动态的划分为若干个长度不相同的区域，称为物理段，每个物理段由起始地址和长度确定 内存分配 以段为单位分配内存，每一个在内存中占据连续空间（内存随机分割，需要多少分配多少），但各段之间可以不连续存放,段表：实现从逻辑地址到物理地址的变换。系统为每个进程建立一个段表。 段表项：段号、段长和该段在内存的始址。 段表始址寄存器：记录进程的段表在内存的始址和段表长度。 当访问某段时，其逻辑地址(S，W)中的段号S先与段表始址寄存器的段表