c第四章存储器管理

《c第四章存储器管理》由会员分享，可在线阅读，更多相关《c第四章存储器管理（108页珍藏版）》请在金锄头文库上搜索。

1、第四章 存储器管理,4.0 存储器的层次结构4.1 程序的装入和链接 4.2 连续分配方式 4.3 基本分页存储管理方式 4.4 基本分段存储管理方式 4.5 虚拟存储器的基本概念 4.6 请求分页存储管理方式 4.8 页面置换算法 4.9 请求分段存储管理方式,内存(Main Memory或Primary Memory或Real Memory)也称主存,是指CPU能直接存取指令和数据的存储器。,图 内存在计算机系统中的地位,4.0 存储器的层次结构,4.0 存储器的层次结构,功能：储存以二进位形式表示的程序和数据分类：内存储器/外存储器,在多道程序环境下，程序要运行必须为之创建进程，而创建进

2、程的第一件事，就是要将程序和数据装入内存。如何将一个用户源程序变为一个可在内存中执行的程序，通常要经过以下几步 :（1）编译：由编译程序（Compiler）将用户源代码编译成若干个目标模块（Object Module）；（2）链接：由链接程序（Linker）将编译后形成的目标模块以及它们所需要的库函数，链接在一起，形成一个装入模块（Load Module）；（3）装入：由装入程序（Loader）将装入模块装入内存。,4.1 程序的装入和链接,4.1 程序的装入和链接,图 4-1 对用户程序的处理步骤,1)静态链接： 在装入内存前链接成一个大的装入模块module。但需要解决两个问题，即： (1

3、) 修改相对地址。 (2) 变换外部调用符号。2)装入时动态链接： 边装入边链接，即装入一个模块时，便去找它的调用模块，如有便再装入，同时修改目标模块中的相对地址。由于分开装入：便于模块更新修改；便于模块的共享。3)运行时动态链接: 将对某些目标模块的链接推迟到执行时才进行。 凡在执行过程中未被用到的目标模块，都不会被调入内存或被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。,4.1.2 程序的链接,图 4-3 程序链接示意图,4.1.1 程序的装入,绝对装入方式可重定位装入方式（静态重定位）动态运行时装入方式（动态重定位）,重要的术语： 逻辑地址，是目标程序中的地

4、址。这种地址一般以0为基地址，顺序编址。一个作业或进程的目标程序（准确地说应是装入模块）的逻辑地址的集合称为该作业或进程的逻辑地址空间，或称地址空间或虚拟空间。逻辑地址也称相对地址或虚拟地址。 物理地址，是物理存贮器的单元地址。物理地址的集合称为物理地址空间，或称存储空间或实地址空间。物理地址也称绝对地址或实地址。 重定位：把装入模块中指令的逻辑地址以及数据的逻辑地址变换成内存中物理地址的过程称为重定位。,1.绝对装入：只能将目标模块装入指定的内存位置 缺点：（1）在程序中必须由程序员给出绝对地址。或者说此时的相对地址和绝对地址一样；（2）要求程序员对内存使用情况非常熟悉。事先知道自己的程序将

5、要装在什么地方；（3）只适合于单道程序环境。例如：某个程序员想在内存200处编一个程序：,Mov ax,20435h,程序逻辑地址相对地址,内存中进程绝对地址物理地址,2.可重定位的装入：装入时将逻辑地址转换为物理地址(重定位)，逻辑地址从0开始。适合于多道程序环境。地址变换在装入时一次性完成，以后不变，可看作是静态重定位。,例如:准备将程序装入内存10000处,11000,12500,注意：这种装入后程序不便在内存中移动。Why?,3.动态运行时装入：模块装入内存后没有立即重定位，仍然是相对地址；只有当CPU执行到具有相对地址的代码时才去重定位，因此是动态重定位。,这种装入后程序可以内存中移

6、动，但需要重定位寄存器的硬件支持。,内存的分配 提纲,内存分配的总的介绍：连续分配方式-离散分配方式,连续,离散,对换技术,虚拟存储器,4.2 连续分配方式,4.2.1 单一连续分配,最简单的一种存储管理方式 将内存分为系统区和用户区两部分，系统区仅提供给OS使用，通常是放在内存的低址部分；用户区是指除系统区以外的全部内存空间， 提供给用户使用 只能用于单用户、单任务的操作系统,4.2.2 固定分区分配,最简单的多道程序的存储管理方式主要思想：在单一连续分配的基础上，将用户区划分成若干个固定大小的区，每个区可以放一个作业进程，多个进程并发。系统一启动后就已经分好了分区；,4.2.2 固定分区分

7、配,分区大小划分方法：（a）分区大小相等：缺乏灵活性，当程序太小时，内存空间浪费；当程序太大时，一个分区又不足以装入该程序。通常适合于控制多个相同对象的场合。（b）分区大小不等：将内存划分成含多个较小的分区、适量的中等分区及少量的大分区。,分区1,分区2,分区3,4.2.2 固定分区分配,如何分配 （a）分区使用表：表中包含每个分区的起始地址、大小、状态。 （b）分配方法：在分区使用表中找出一个能满足要求的、尚未分配的分区。将该分区分给程序、并修改分区使用表,点击鼠标：对1k、9k、33k、121k作业分配内存，并修改分区状态,浪费（阴影部分）：7k,23k,87k,211k,总浪费：328k

8、,操作系统,0K,20K,28K,60K,180K,512k-1,分区1,分区2,分区3,分区4,内存分区情况,180k,20k,8k,例题：某系统采用固定分区管理方式，内存分区如图。现有大小为1k、9k、33k、121k要求进入内存，画出他们进入内存的空间分配情况，说明主存浪费多大。,28k,60k,32k,120k,332k,分区使用表,已分配,已分配,已分配,已分配,4.2.3 动态分区分配,含义：根据作业进程的需要，动态的分配内存。系统刚启动时并不分区。数据结构：用来描述空闲分区和已分配分区的情况。常用的数据结构有以下两种形式：空闲分区链：以链表形式记录每个空闲分区的情况。空闲分区表：

9、以表结构形式记录每个空闲分区的情况。例如：,操作系统,0K,20K,28K,60K,180K,空闲分区表,301k,21k,7k,211k,4.2.3 动态分区分配,分配算法：（1）首次适应算法： 从空闲分区表或分区链（按照地址递增次序排列）头上开始查找，找到第一个满足要求的分区为止，分配内存，余下的部分然仍留在空闲分区表中。 优点：倾向于优先利用内存低地址部分的空闲分区；保留了高地址部分的空闲分区。 缺点：低地址部分不断被划分，留下很多碎片. 例题：,例题：已知主存有256k容量，其中os占地端内存20k，有下列作业序列：分析内存分配情况和空闲分区表情况 作业1 要求 80k；作业2 要求

10、16k；作业3 要求 140k 作业1完成；作业3完成； 作业4 要求60k；作业5 要求 120k,空闲分区表,作业1来到,空闲分区表,作业1,100k,刚开始时,作业2 16k作业3 140k分别来到后,空闲分区表,作业2,作业3,116k,作业1 完成作业3 完成,空闲分区表,作业4 60k作业5 120k（12k?)分别来到,作业4,作业5,back,4.2.3 动态分区分配,分配算法：（2）最佳适应算法： 每次为作业分配内存时，总是找一个既能满足要求、又是最小的空闲分区分配给作业。 特点：为提高程序中查找速度，常常将分配表按照分区容量按照从小到大排列，查找时只需要从表首按顺序查找最合

11、适的。 缺点：都在找最合适的分割，常会剩下一些小碎片 例题：,例题：已知内存分配情况如下图。要求填写空闲分区表，并分配如下作业序列 作业4 大小2k，作业5 大小6k， 作业6 大小2k,空闲分区表,作业4,作业5,作业6,改进：空闲分区表（按大小排列，便于程序）,4.2.3 动态分区分配,分配算法：（3）最坏适应算法 每次分配总是挑选出分配表（链）中最大的分区进行分配（4）循环首次适应算法 由首次适应算法演变而来（5）快速适应算法 又称为分类搜索算法，将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表。,看书自行理解,4.2.3 动态分区分配,分

12、配内存： 在系统利用上述的某种分配算法，从空闲分区表（链）中找到所需大小的空闲分区之后，应进行内存的分配操作，即： 1. 计算当前空闲分区的大小m.size和实际请求的分区大小u.size之差 2. 若m.size-u.sizesize，则从该空闲分区中按请求的大小划分出一块内存空间分配给请求者，并将剩余的部分仍留在空闲分区表（链）中。 4. 将分配区的首地址返回给调用者。 实际地，内存分配的操作流程亦可描述为：,4.2.3 动态分区分配,回收内存： 当进程运行完毕释放内存时，系统根据回收区的首地址，从空闲分区表（链）中找到相应的插入点，将回收区插入到空闲分区表（链）中的适当位置。 此时，可能

13、出现以下四种情况之一： 1. 回收区前连空闲区 2. 回收区后连空闲区 3. 回收区前、后连空闲区 4. 回收区前、后都不连空闲区 例题：,操作系统,作业1,0k,20k,256k-1,10k,25k,作业2,3k,35k,45k,作业3,156k,48k,100k,作业5,作业6,作业4,58k,68k,70k,空闲分区表,作业3完成、作业1完成、作业2完成、作业5完成,作业3完成,10k,作业1完成,5k,作业2完成,10k,作业5完成,2k,4.2.4 动态重定位分区分配,1. 动态重定位的引入,思想：在动态分区分配的基础上引入“紧凑”技术（整理功能）,2. 动态重定位的实现 动态重定位

14、分区分配算法需与在装入时，采用“动态运行时装入”方式，才能保证程序中相对地址的正确性,4.2.4 动态重定位分区分配,3. 动态重定位分区分配算法,4.2.4 动态重定位分区分配,动态重定位分区分配算法与动态分区分配算法基本相同，差别仅在于：在找不到足够大的空闲分区来满足用户需求时应进行“紧凑”。其流程可描述为：,优点:可以消除碎片,能够分配更多的分区,有助于多道程序设计,提高内存的利用率。缺点:紧凑花费了大量CPU时间;,4.2.5 对换(Swapping),1. 对换的引入（新教材P129）,所谓“对换”，是指把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到外存上，以便腾出足够的

15、内存空间，再把已具备运行条件的进程或进程所需要的程序和数据，调入内存。对换是提高内存利用率的有效措施。 对换又分为： （1）整体对换 即对换是以整个进程为单位的，又称进程对换。 （2）部分对换 页面对换：对换是以“页”为单位进行的。 分段对换：对换是以“段”为单位进行的。,图 对换两个进程,4.2.5 对换(Swapping),2. 对换空间的管理,为了能对对换区中的空闲盘块进行管理，在系统中应配置相应的数据结构，以记录外存的使用情况。其形式与内存在动态分区分配方式中所用数据结构相似，即同样可以用空闲分区表或空闲分区链。在空闲分区表中的每个表目中应包含两项， 即对换区的首址及其大小，它们的单位是盘块号和盘块数。,3. 进程的换出与换入,(1) 进程的换出。 每当一进程由于创建子进程而需要更多的内存空间，但又无足够的内存空间等情况发生时，系统应将某进程换出。 其过程是：系统首先选择处于阻塞状态且优先级最低的进程作为换出进程，然后启动磁盘，将该进程的程序和数据传送到磁盘的对换区上。若传送过程未出现错误，便可回收该进程所占用的内存空间，并对该进程的进程控制块做相应的修改。,