易小林操作系统第4章

《易小林操作系统第4章》由会员分享，可在线阅读，更多相关《易小林操作系统第4章（114页珍藏版）》请在金锄头文库上搜索。

1、第四章 存储器管理 4.1 存储器的层次结构4.2 程序的装入和链接4.3 连续分配存储管理方式4.4 对换4.5 分页存储管理方式4.6 分段存储管理方式虚拟存储器第四章 存储器管理 4.1 存储器的层次结构4.1 存储器的层次结构 1. 存储器的多层结构 在计算机执行时，几乎每一条指令都涉及到对存储器的访问，因此存储器的速度必须非常快，能与处理机的速度相匹配，否则会明显地影响到处理机的运行。此外还要求存储器具有非常大的容量，而且存储器的价格还应很便宜。对于这样十分严格的三个条件，目前是无法同时满足的。于是在现代计算机系统中，都无一例外地采用了多层结构的存储器系统。4.1 存储器的层次结构

2、对于通用计算机而言，存储层次至少应具有三级：最高层为CPU寄存器，中间为主存，最底层是辅存。在较高档的计算机中，还可以根据具体的功能分工，细划为寄存器、高速缓存、主存储器、磁盘缓存、固定磁盘、可移动存储介质等6层。2.各种存储器寄存器、高速缓存：少量的、非常快速、昂贵、易变；高速缓存是介于寄存器和存储器之间的存储器； 主存储器：简称内存或主存、数十MB到数GB、中等速度、中等价格、易变；寄存器和主存储器又被称为可执行存储器； 磁盘缓存：依托于固定磁盘，提供对主存储器存储空间的扩充； 磁盘：数百兆或数千兆字节、低速、价廉、不易变； 4.1 存储器的层次结构返回第四章 存储器管理 4.2 程序的装

3、入和链接4.2 程序的装入和链接1.对用户程序的处理步骤2.程序的装入 (1) 绝对装入方式计算机系统很小仅能运行单道程序完全有可能知道程序将驻留在内存的什么位置。编译后，将产生绝对地址的目标代码缺点：要求程序员熟悉内存的使用情况一旦程序或数据被修改后，可能要改变程序中的所有地址4.2 程序的装入和链接 (2)可重定位装入方式多道程序环境。不可能预知经编译后所得到的目标模块在内存的地址。编译所形成的若干个目标模块，它们的起始地址通常都是从0开始的，程序中的其它地址也都是相对于起始地址计算的。缺点：不允许程序运行时在内存中移动位置 2.程序的装入 (3)动态运行时装入方式在具有对换功能的系统中装

4、入模块中的相对地址在装入时并不转换为绝对地址 地址转换，推迟到程序真正要执行时才进行。 需要一个重定位寄存器的支持2.程序的装入3.程序的链接 (1)静态链接方式 在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装配模块，以后不再拆开。4.2 程序的装入和链接 (1)静态链接方式 须解决以下两个问题： 对相对地址进行修改 由编译程序所产生的所有目标模块中，使用的都是相对地址，其起始地址都为0，每个模块中的地址都是相对于起始地址计算的，需要进行修改。 变换外部调用符号 将每个模块中所用的外部调用符号也都变换为相对地址。 3.程序的链接 (2)装入时动态链接 用户源程序编译后所得

5、到的一组目标模块，在装入内存时，采用边装入边链接的链接方式。优点： 便于修改和更新 因为各目标模块是分开存放的。 便于实现对目标模块的共享 OS很容易将一个目标模块，链接到几个应用模块上，实现多个应用程序对该模块的共享。 3.程序的链接 (3)运行时动态链接 将对某些模块的链接，推迟到程序执行时才进行。优点： 加快程序的装入过程 凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上。 可节省大量的内存空间 仅装入了运行所需要的模块。 3.程序的链接第四章 存储器管理 4.3 连续分配存储管理方式4.3 连续分配存储管理方式1.单一连续分配单道程序环境下内存分为系统区和用户区系

6、统区仅提供给OS使用，在内存的低址部分用户区仅装有一道用户程序，即整个内存的用户空间由该程序独占缺点：不支持多道 主存利用率不高 程序的运行受主存容量限制 4.3 连续分配存储管理方式2. 固定分区分配多道程序环境下整个用户空间划分为若干个固定大小的区域 每个分区中只装入一道作业2. 固定分区分配（1）划分分区的方法分区大小相等 所有的内存分区大小相等，缺点是缺乏灵活性. 分区大小不等 存储器分区划分为若干个大小不等的分区. 2. 固定分区分配（2）内存分配 将分区按其大小进行排队，并为之建立一张分区使用表，其中各表项包括每个分区的起始地址、大小及状态（是否已分配）。 当有一用户程序要装入时，

7、由内存分配程序依据用户程序的大小检索该表，从中找出一个能满足要求的、尚未分配的分区，将之分配给该程序，然后将该表项中的状态置为“已分配”。 若未找到大小足够的分区，则拒绝为该用户程序分配内存。 由于每个分区的大小固定，必然会造成存储空间的浪费。 2. 固定分区分配（2）内存分配 20K4.3 连续分配存储管理方式3.动态分区分配根据进程的实际需要，动态地为之分配内存空间。 动态分区分配中的数据结构 动态分区分配算法 分区分配操作 3.动态分区分配（1）动态分区分配中的数据结构 系统中必须配置相应的数据结构，用以描述空闲分区和已分配分区的情况，为分配提供依据。 空闲分区表空闲分区链 256405

8、 1281284 32322 起址（K）大小（K）分区号3.动态分区分配（2）动态分区分配算法 为把一个新作业装入内存，须按照一定的分配算法，从空闲分区表或空闲分区链中，选出一分区分配给该作业。由于内存分配算法，对系统性能有很大的影响，故人们对它进行了较广泛而深入地研究，于是产生了许多动态分区分配算法。 将在下面两小节中分别介绍传统的顺序式搜索算法和三种较新的索引式搜索算法。3.动态分区分配（3）分区分配操作 在动态分区存储管理方式中，主要的操作是： 分配内存 系统应利用某种分配算法，从空闲分区链（表）中，找到所需大小的分区。 回收内存 当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区

9、链（表）中找到相应的插入点， 进行合并回收3.动态分区分配（3）分区分配操作分配内存 3.动态分区分配（3）分区分配操作回收内存回收区与插入点的前一个空闲分区F1相邻接回收分区与插入点的后一空闲分区F2相邻接回收区同时与插入点的前、后两个分区邻接回收区既不与F1邻接，又不与F2邻接（3）分区分配操作回收内存流程4.3 连续分配存储管理方式4.基于顺序搜索的分区分配算法 为了实现动态分区分配，通常是将系统中的空闲分区链接成一个链。所谓顺序搜索，是指依次搜索空闲分区链上的空闲分区，去寻找一个其大小能满足要求的分区。 首次适应算法：选择分区时总是按地址从高到低搜索。循环首次适应算法：类似首次适应法每

10、次分区时，总是从上次查找结束的地方开始。最佳适应算法：在空闲块表中找到一个不小于请求的最小空块进行分配 最坏适应算法：在空闲块表中找到一个不小于请求的最大空块进行分配思考练习 1、如果内存划分为100KB、500KB、200KB、300KB和600KB（按顺序），那么，首次适应、最佳适应和最差适应算法各自将如何放置大小分别为212KB、417KB、112KB和426KB(按顺序)的进程，哪一种算法的内存利用率高？ 2、某操作系统采用分区存储管理技术。操作系统占用了低地址端的100KB空间，用户区从100KB处开始共占用512KB。初始时，用户区全部空闲，分配时截取空闲区的低地址部分作为一个新分

11、配区。在执行了如下的申请、释放序列后： 作业1申请300KB、作业2申请100KB、作业1释放300KB、作业3申请150KB、作业4申请50KB、作业5申请90KB。 分别画出采用首次适应算法、最佳适应算法进行内存分配后的内存分配图和空闲区队列； 若随后又申请80KB，针对上述两种情况会产生什么后果？4.3 连续分配存储管理方式5. 基于索引搜索的分区分配算法 当系统很大时，系统中的内存分区可能会很多，相应的空闲分区链就可能很长，这时采用顺序搜索分区方法可能会很慢。 快速适应算法：将空闲分区，按其容量大小，进行分类，对于每一类的所有空闲分区，单独设立一个空闲分区链表伙伴系统：分区大小均为2

12、的k次幂，将空闲分区按分区的大小进行分类，并单独设立一个空闲分区双向链表。哈希算法：构造一张以以空闲分区大小为关键字的哈希表，该表的每一个表项记录了一个对应的空闲分区链表表头指针。4.3 连续分配存储管理方式6.可重定位分区分配 连续分配方式的一个重要特点是，一个系统或用户程序必须被装入一片连续的内存空间中。当一台计算机运行了一段时间后，它的内存空间将会被分割成许多小的分区，而缺乏大的空闲空间。 若想把大作业装入，可采用的一种方法是: 将内存中的所有作业进行移动，使它们全都相邻接。这样，即可把原来分散的多个小分区拼接成一个大分区，这时就可把一个作业装入该区。 技术需求：紧凑；动态重定；动态重定

13、位分区分配算法 6.可重定位分区分配紧凑6.可重定位分区分配动态重定位的实现6.可重定位分区分配动态重定位分区分配算法 返回第四章 存储器管理 4.4 对换4.4 对换1.多道程序环境下的对换技术(1)对换的引入多道程序环境在内存中的某些进程，由于某事件尚未发生而被阻塞运行，但它却占用了大量的内存空间，甚至有时可能出现在内存中所有进程都被阻塞，而无可运行之进程，迫使CPU停止下来等待的情况；另外，却又有着许多作业，因内存空间不足，一直驻留在外存上，而不能进入内存运行；把内存中暂时不能运行的进程或者暂时不用的程序和数据，换出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的

14、程序和数据，换入内存。 1.多道程序环境下的对换技术(2) 对换的类型整体对换以整个进程为单位；作为处理机中级调度； 页面（分段）对换 以进程的一个“页面”或“分段”为单位进行的 ； 为了实现进程对换，系统必须能实现三方面的功能: 对对换空间的管理 进程的换出 进程的换入对对换空间的管理对换空间管理的主要目标 在具有对换功能的OS中，通常把磁盘空间分为文件区和对换区两部分： 对文件区管理的主要目标：首先是提高文件存储空间的利用率，然后才是提高对文件的访问速度对对换空间管理的主要目标：是提高进程换入和换出的速度，然后才是提高文件存储空间的利用率.对对换空间的管理对换区空闲盘块管理中的数据结构 为

15、了实现对对换区中的空闲盘块的管理，在系统中应配置相应的数据结构，用于记录外存对换区中的空闲盘块使用情况。 其数据结构的形式，与内存在动态分区分配方式中所用数据结构相似，即同样可以用空闲分区表或空闲分区链。在空闲分区表的每个表目中，应包含两项：对换区的首址及其大小，分别用盘块号和盘块数表示。对对换空间的管理对换空间的分配与回收 由于对换分区的分配采用的是连续分配方式，因而对换空间的分配与回收，与动态分区方式时的内存分配与回收方法雷同。 其分配算法可以是首次适应算法、循环首次适应算法或最佳适应算法等。具体的分配操作也与图5-8中内存的分配过程相同。 对换区的回收操作可分为四种情况： 回收区与插入点的前一个空闲分区F1相邻接； 回收分区与插入点的后一空闲分区