孙钟秀操作系统第四章存储管理2

《孙钟秀操作系统第四章存储管理2》由会员分享，可在线阅读，更多相关《孙钟秀操作系统第四章存储管理2（100页珍藏版）》请在金锄头文库上搜索。

1、1,在早期的操作系统中，主存分配广泛采用连续分配方式。 连续分配方式为一个用户程序分配一个连续的主存空间。,4.2 连续存储空间管理,2,一、单一连续分配（单个分区）,最简单的存储管理方式，用于多道程序设计技术之前。 内存分为系统区和用户区，系统区由操作系统使用。用户区作为一个连续的分区分配给一个作业。 评价 优点：方法简单，易于实现 缺点： 1.仅适用于单道程序，只能用于单用户单任务的操作系统 2.系统资源利用率低,3,分区存储管理是满足多道程序设计的最简单的一种存储管理方法，它允许多个用户程序同时存在系统内存中，即共享内存空间。 按分区划分方式可分为固定分区和可变分区。,4,二、 固定分区

2、存储管理,1.基本思想 把内存的用户区预先划分成多个分区，每个分区大小可以相同，也可以不同。（分区的划分由计算机的操作员或者由操作系统给出，并给出主存分配表） 分区个数固定，分区的大小固定。 一个分区中可装入一个作业，作业执行过程中不会改变存放区域。,早期的IBM的OS/MFT（具有固定任务数的多道程序系统）采用了这种固定分区的方法。,5,2.主存分配表 为了说明各分区的分配和使用情况，需设置“主存分配表”，记录各分区及其使用情况。 主存分配表内容：分区号，分区的起始地址，长度，占用标志。 3.主存空间分配 主存存分配程序检索主存分配表，从中找到还未分配且大小满足要求的分区，则将此分区分配给该

3、作业。若没找到满足条件的分区，则拒绝为该作业分配主存。,6,例：某系统的内存容量为256K，操作系统占用低地址的20K，其余空间划分成4个固定大小的分区。如下图,主存分配表,7,.固定分区性能分析,在作业大小和出现频率均已知的情况下，固定分区是合适的。在这种情况下分区的大小选择与作业大小相当，这样内存的使用效率较高。 但是若作业的大小和出现的频率不知道时，势必造成分区的大小和作业的大小相差甚远，这样就会造成存储空间的浪费，从而影响整个系统的效率。 缺点：碎片问题，主存利用率很低。,8,三、 可变分区存储管理（动态分区）,1.基本思想 内存不是预先划分好的，而是在系统运行的过程中建立分区.当作业

4、装入主存时，根据作业所需要的主存容量查看是否有足够的主存空间，若有则按需要分割一个分区给该作业；否则令该作业等待. 分区长度不固定,分区个数不固定. 这种存储管理的方法克服了固定分区严重浪费主存的问题，提高了主存资源的利用率。 操作系统采用可变分区存储管理。,9,当有作业完成后释放所占用的存储区。 在系统运行的过程中，系统中形成多个空闲的不连续的存储区，称空闲区。,10,2.实现动态分区需要的数据结构,在动态分区存储管理中，要有相应的数据结构来登记空闲区信息，它包括空闲区的大小和位置。 不同系统根据设计要求采用不同的结构。常用的有表结构和链结构。 系统还要设置了等待分区队列，当系统中无空闲区或

5、无满足要求的空闲区时，则把申请者送入等待队列中，等待别的进程释放内存之后再唤醒队列中的进程。,11,例:,12,3.分区分配算法,空闲区表（链）中的空闲区可按一定规则排列，例如按空闲区大小的升序（降序）排列；按空闲区地址升序（降序）组织。 根据空闲区表（链）排列方法不同，对应不同的分配算法，常用的可变分区分配算法有最先适应算法，下次适应分配算法，最优适应算法、最坏适应算法等。,13,(1)最先适应算法,空闲区按地址从小到大的次序排列。,分配：当进程申请大小为SIZE的内存时，系统顺序查找空闲区表（链），直到找到容量满足要求（SIZE）的空闲区为止。从该空闲区中划出大小为SIZE的分区分配给进程

6、，余下的部分仍作为一个空闲区，但要修改其首址和大小。,优点：这种算法是尽可能地利用低地址部分的空闲区，而尽量地保证高地址部分的大空闲区，有利于大作业的装入。 缺点:主存低地址和高地址分区利用不均衡。在低地址部分,集中了许多非常小的空闲区(碎片),降低了主存的利用率。,14,（）下次适应分配算法,最先适应算法的变种。 总是从空闲区上次扫描结束处顺序查找空闲区表（链），直到找到第一个满足容量要求的空闲区为止，分割一部分给作业，剩余部分仍作为空闲区。,15,()最优适应算法,空闲区按容量递增的次序排列。,分配：当进程申请存储空间，系统顺序查找空闲区表（链），直到找到第一个满足容量要求的空闲区为止。

7、采用最优适应算法选中的空闲区是满足容量要求的最小空闲区。,16,优点： 选中的空闲区是满足容量要求的最小空闲区，而不致于毁掉较大的空闲区。 缺点： 空闲区的大小一般与申请分区大小不相等，因此将其一分为二，留下来的空闲区一般情况下是很小的，以致无法使用。随着时间的推移，系统中的小空闲区会越来越多，从而造成存储空间的浪费。,17,()最坏适应算法,要求空闲区按容量递减的顺序排列。,分配：进程申请存储区时，检查空闲区表（链）的第一个空闲区的大小是否满足要求，若不满足则令进程等待；若满足则从该空闲区中分配一部分存储区给用户，剩下的部分仍作为空闲区。,为了克服最佳适应算法把空闲区切割得太小的缺点，人们提

8、出了一种最坏适应算法，即每次分配时，总是将最大的空闲区切去一部分分配给请求者，剩余的部分仍是一个较大的空闲区。避免了空闲区越分越小的问题。,18,分析:,当程序装入内存中最大的空闲区后，剩下的空闲区还可能相当大，还能装下较大的程序。 另一方面每次仅作一次查询工作，查找效率高。,19,例：某时刻系统中有三个空闲区,有一作业大小25k。,首次适应算法： 最优适应算法： 最坏适应算法：,20,4.可变分区的回收,当某个进程释放某存储区时，系统首先检查释放区是否与系统中的空闲区相邻，若相邻则把释放区合并到相邻的空闲区中去，否则把释放区作为一个空闲区插入到空闲区表的适当位置。,释放区与空闲区相邻的四种情

9、况,21,(a)释放区与前空闲区相邻：将释放区与前空闲区合并为一个空闲区。其首址仍为前空闲区首址，大小为释放区大小与空闲区大小之和。 (b)释放区与后空闲区相邻：则把释放区合并到后空闲，首地址为释放区首地址，大小为二者大小之和。 (c)释放区与前后两个空闲区相邻：将这三个区合为一个空闲区，其首址为前空闲区首址，大小为这三个区大小之和，并取消原后空闲区表目。 (c)释放区不与任何空闲区相邻：将释放区作为一个空闲区，将其大小和首址插入到空闲区表的适当位置。,22,可变分区存储管理分析,优点: 1.有助于多道程序设计 2.不需过多硬件,仅需界地址寄存器用于存储保护 3.所采用的算法都比较简单,易于实

10、现,缺点: 1.碎片问题 由于空闲区的大小与申请内存的大小相等的情况是很少的，绝大多数情况是从一个空闲区中切去一块，剩下的部分作为一个空闲区仍留在空闲区表中，随着时间的推移，空闲区的发展趋势是越来越小，直至不能满足任何用户要求。 这种不能被任何用户使用的极小的空闲区称为碎片。碎片的出现造成了存储空间的浪费。 2.分区大小受主存容量限制,无法扩充主存容量,23,四、可重定位分区存储管理,解决碎片问题的一种简单方法是采用可重定位分区分配. 1.基本思想 例:内存中现有3个空闲区，如图所示，现有一作业到达，要求获得30k内存空间，没有分区满足容量要求，若想把作业装入，可将内存中所有作业进行移动，这样

11、把原来分散的空闲区汇集成一个大的空闲区。,24,将内存中的作业进行移动,使它们连接在一起,把原来分散的多个小分区拼接成一个大的空闲区.这个过程称为”紧凑”或”移动”. 需解决的问题:每次”紧凑”后,程序或数据装入的物理地址变化,采用动态重定位.,25,2.动态重定位分区分配算法 与动态分区分配算法基本相同,差别在找不到足够大的空闲分区时进行”紧凑”.,26,分区分配方案评价,优点: 1.实现了主存共享,有助于多道程序设计,提高了系统资源的利用率; 主存利用率:可重定位分区分配动态分区分配固定分区分配 2.与后面所介绍的存储管理方式相比,实现分区分配所使用的表格,占用的存储空间较少,算法也相对简

12、单; 3.实现存储保护的措施也较简单。,缺点: 1.主存仍不能充分利用,除了可重定位分区法外,都存在碎片问题. 2.采用”紧凑”方法,虽解决了碎片问题,但系统开销太大. 3.不能实现对主存的扩充.因此作业大小受到主存可用空间限制.,27,五、 覆盖技术与对换技术,1.为什么引入？ 在多道环境下扩充内存的方法，用以解决在较小的存储空间中运行较大程序时遇到的矛盾。 覆盖技术主要用在早期的操作系统中。 对换技术被广泛用于小型分时系统中，交换技术的发展导致了虚存技术的出现。,28,2. 覆盖技术,把程序划分为若干个功能上相对独立的程序段，按照其自身的逻辑结构将那些不会同时执行的程序段共享同一块内存区域

13、 程序段先保存在磁盘上，当有关程序段的前一部分执行结束，把后续程序段调入内存，覆盖前面的程序段（内存“扩大”了） 覆盖：一个作业的若干程序段，或几个作业的某些部分共享某一个存储空间 一般要求作业各模块之间有明确的调用结构，程序员要向系统指明覆盖结构，然后由由操作系统完成自动覆盖,29,图示,30,缺点： 对用户不透明，增加了用户负担。 例子：目前这一技术用于小型系统中的系统程序的内存管理上，MS-DOS的启动过程中，多次使用覆盖技术；启动之后，用户程序区TPA的高端部分与COMMAND.COM暂驻模块也是一种覆盖结构。 现代操作系统极少使用覆盖技术。,分析,31,3.对换技术,为平衡系统负载，

14、通过选择一个进程，把其暂时移出到磁盘，腾出空间给其他进程使用，同时把磁盘中的某个进程再换进主存，让其投入运行，这种互换称对换。 多用于分时系统中,32,选择原则（即：将哪个进程换出内存？） 时间片轮转法或基于优先数的调度算法，通常把时间片耗尽或优先级较低的进程换出，因为短时间内它们不会被投入运行。 对换时机（即：何时需发生对换） 批处理系统中，当有进程要求动态扩充主存且得不到满足时可触发对换； 分时系统中，对换可与调度结合在一起，每个时间片结束或执行I/O操作时实施。,33,分析,与覆盖技术相比，交换技术不要求用户给出程序段之间的逻辑覆盖结构； 交换发生在进程或作业之间，而覆盖发生在同一进程或

15、作业内。 覆盖只能覆盖那些与覆盖段无关的程序段。,34,上节所介绍的连续分配方式，会出现碎片问题，虽然采用“紧凑”的方法将许多碎片拼接成可用的大块空间，但须为之付出很大开销，而无实用价值。如果允许将一个进程直接分散地装入到许多不相邻的分区中，则无须再进行“紧凑”。基于这一思想而产生了离散分配方式。 离散分配方式：给进程分配几个不连续的内存区域，并可保证进程的正确执行。 离散分配方式按分配基本单位不同分为分页存储管理和分段存储管理。,35,4.3 分页存储管理,分页技术是由曼彻斯特大学提出，并于1960年前后在Atlas计算机上实现。这种技术对操作系统的发展产生了深远影响。,36,一、基本原理,

16、1.页面 把一个进程的逻辑地址空间分成若干大小相等的片，每个片称为页面或页 。从0开始编制页号。 页面的大小应选择适中，一般页的大小为2的幂，通常为512 B8 KB。 2.逻辑地址 分页存储管理逻辑地址分为两部分：地址的高位部分为页号，低位部分为页内位移。,例：逻辑地址32位，页大小4k，则页内位移占12位，页号占20位。,37,3.物理块（页框） 把主存的物理地址空间分成和页面大小相等的区，每个区称为物理块或页框。从0开始编制块号。 4.物理地址 5.分页存储管理基本原理 以页为单位进行分配。当一个进程装入内存时，将进程的多个页面分别装入内存的多个物理块中，这些物理块可以是不相邻的。,38,例：页面大小1k,39,6.页表 进程的各个页面分散存放在主存不相邻的物理块中，系统如何知道页面和物理块的对应关系。 这就需要系统为每个进程建立一个页表，用来登记页号和块的对应关系和有关信息。 一个进程有多少个页面，页表就有多少项。 进程的页表大多驻留在内存中 ，页表在主存的首地址和长度存放在该进程的进程控制块。,40,例：页面大小1k,进程1页表,页号 块号,