四章节存储器管理知识讲解

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

1、第四章 存储器管理,4.1 程序的装入和链接 4.2 连续分配方式 4.3 基本分页存储管理方式 4.4 基本分段存储管理方式 4.5 虚拟存储器的基本概念 4.6 请求分页存储管理方式 4.7 页面置换算法 4.8 请求分段存储管理方式,4.1 程序的装入和链接,图 4-1 对用户程序的处理步骤,4.1.1 程序的装入,1. 绝对装入方式(单道系统中),程序中所使用的绝对地址，既可在编译或汇编时给出， 也可由程序员直接赋予。 通常是在编译或汇编时，再将这些符号地址转换为绝对地址。,2. 可重定位装入方式(Relocation Loading Mode),图 4-2 作业装入内存时的情况,4.

2、1.2 程序的链接,1. 静态链接方式(Static Linking),图 4-3 程序链接示意图,在将这几个目标模块装配成一个装入模块时，须解决以下两个问题： (1) 对相对地址进行修改。 (2) 变换外部调用符号。,2. 装入时动态链接(Loadtime Dynamic Linking),目标模块是边装入内存边链接的。 优点： 便于修改和更新。 （目标模块是分开存放的） (2) 便于实现对目标模块的共享。 （一个目标模块可链接到几个应用模块 ）,3. 运行时动态链接(Run-time Dynamic Linking),在执行过程中，当发现一个被调用模块尚未装入内存时，再装入内存， 把它链接

3、到调用者模块上。 未被用到的目标模块，都不会被调入内存和被链接到装入模块上，（如：错误处理用的目标模块） 优点：加快程序的装入过程，可节省大量的内存空间。,4.2 连续分配方式,4.2.1 单一连续分配 （单用户、单任务）,把内存分为系统区和用户区两部分 系统区仅提供给OS使用，通常是放在内存的低址部分； 用户区是指除系统区以外的全部内存空间， 提供给用户使用。,4.2.2 固定分区分配,1. 划分分区的方法,分区大小相等。 程序太小时浪费内存，程序太大时可能不足以装入。 (2) 分区大小不等。 多个较小的分区，适量的中等分区，少量大分区,2. 内存分配,图 4-4 固定分区使用表,4.2.3

4、 动态分区分配,1. 分区分配中的数据结构,空闲分区表。 表目：序号，始址 大小 (2) 空闲分区链。,图 4-5 空闲链结构,2. 分区分配算法,首次适应算法FF。 以地址递增的次序链接空闲分区 分配内存时，从链首顺序查找，找到为止，若找不到则分配失败 优点：优先利用低址，从而保留高址的大空间 缺点：低址不断利用，留下碎片；增加查找开销 (2) 循环首次适应算法，该算法是由首次适应算法演变而成的。 由首次适应算法演变而来，只是从上次找到的空闲分区的下一个开始查找 采用循环查找的方式 优点：空闲分区的分布得更均匀；缺点：会缺乏大空闲分区； (3) 最佳适应算法。 找到满足要求，又是最小的空闲分

5、区 从小到大形成一空闲分区链 但切割剩余部分是最小的,3. 分区分配操作,1) 分配内存,图 4-6 内存分配流程,2) 回收内存（四种情况）,图 4-7 内存回收时的情况,4.2.4 可重定位分区分配,1. 动态重定位的引入（要求连续空间，移动后的程序须重定位）,图 4-8 紧凑的示意,2. 动态重定位的实现,动态装入方式中，内存中的作业仍是相对地址，在程序执行时，才转换为绝对地址 为加快转换速度，增设重定位寄存器，用于存放起始地址 在小分区“拼凑”时，不需对程序作任何修改,2. 动态重定位的实现,图 4-9 动态重定位示意图,3. 动态重定位分区分配算法,图 4-10 动态分区分配算法流程

6、图,4.2.5 对换(Swapping),1. 对换的引入,所谓“对换”， 是指把内存中暂时不能运行的进程或数据，调出到外存上，再把已具备运行条件的进程或数据，调入内存。 对换是提高内存利用率的有效措施。,2. 对换空间的管理,在外存中设一对换区，用于存放换出的进程 进程在对换区中驻留是短暂的，对换是频繁的，故采用连续分配方式，以提高速度 对换区的分配同样可以用空闲分区表或空闲分区链。在空闲分区表中的每个表目中应包含两项， 即对换区的首址及其大小，它们的单位是盘块号和盘块数。,3. 进程的换出与换入,(1) 进程的换出。 1、系统首先选择处于阻塞状态且优先级最低的进程作为换出进程， 2、将该进

7、程的程序和数据传送到磁盘的对换区上。 3、若传送过程未出现错误，便可回收该进程所占用的内存空间，并对该进程的PCB做相应的修改。,(2) 进程的换入。 将换出时间(换出到磁盘上)最久的进程作为换入进程，将之换入，直至已无可换入的进程或无可换出的进程为止。,4.3 基本分页存储管理方式,4.3.1 页面与页表,1. 页面 1) 页面和物理块 页面或页：将进程的逻辑地址空间分成若干个大小相等的片，并为各页从0开始加以编号。 (物理)块或页框(frame)：把内存空间分成与页面相同大小的若干个存储块，加以编号。 在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。

8、“页内碎片”：由于进程的最后一页经常装不满一块而形成了不可利用的碎片。,2) 页面大小 页面若太小： 内存碎片减小 但会导致进程的页表过长，占用更多的内存； 还会降低页面换进换出的效率。 若页面较大： 虽然可以减少页表的长度，提高页面换进换出的速度， 但却又会使页内碎片增大。 合适的页面大小： 应是2的幂，通常为512 B8 KB。,2. 地址结构,分页地址中的地址结构如下：,31,12,11,0,对某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为A(2170)，页面的大小为L(1024)，则页号P(2)和页内地址d(122)可按下式求得：,3. 页表（每个进程一个页表，将页号

9、转换为块号）,图 4-11 页表的作用,4.3.2 地址变换机构,1. 基本的地址变换机构（始址和长度是平时放在PCB中，运行时调入寄存器）,图 4-12 分页系统的地址变换机构,2. 具有快表的地址变换机构(一次访存),图 4-13 具有快表的地址变换机构,快表也叫“联想寄存器”，IBM系统中也称“TLB” CPU给出有效地址，先查快表，若找到则直接读物理块，若没找到则找内存中的页表，并把表项送到快表中，若快表满则找不再需要的页表项换出。,4.3.3 两级和多级页表,一般计算机系统逻辑地址空间(232264)，页表就变得非常大，要占很大内存空间。 如，一个32位逻辑地址空间的分页系统，页面大

10、小为4 KB即212 B，则每个进程页表中的页表项可达1兆个。每个页表项占一个字节， 其页表就要占用1MB的内存空间，而且还要求是连续的。 可以采用这样两个方法来解决这一问题： 采用离散分配方式来解决难以找到一块连续的大内存空间的问题： 只将当前需要的部分页表项调入内存， 其余的页表项仍驻留在磁盘上，需要时再调入。,1. 两级页表(Two-Level Page Table),逻辑地址结构可描述如下：,图 4-14 两级页表结构,图 4-15 具有两级页表的地址变换机构,两级页表采用离散分配空间的方法，但并没有减少页表所占空间。 故采用只将当前需要的页表调入内存，以后再根据需要陆续调入。 在外层

11、页表中增设一个状态位S，若为0表示页表不在内存，若为1表示在内存。,2. 多级页表 对于64位的机器，如果页面大小仍采用4 KB，此时在外层页表中可能有4096 G个页表项， 要占用16384 GB的连续内存空间。 必须采用多级页表，将外层页表再进行分页。 对于64位的计算机，如果要求它能支持2(=1844744 TB)规模的物理存储空间，则即使是采用三级页表结构也是难以办到的；而在当前的实际应用中也无此必要。,4.4 基本分段存储管理方式,4.4.1 分段存储管理方式的引入,引入分段存储管理方式， 主要是为了满足用户和程序员的下述一系列需要： 1) 方便编程 （按逻辑关系分段） 2) 信息共

12、享 （以段为逻辑单位，便于共享，如函数） 3) 信息保护 4) 动态增长 （便于段（数据段）的增长） 5) 动态链接 （目标程序）段动态链接,4.4.2 分段系统的基本原理,1. 分段,分段地址中的地址具有如下结构：,31 16 15 0,按主程序，子程序，数据，栈等分段 每段从0开始编号，段长不定,为每一个段分配一个连续分区 各个段离散地放在内存中不同的分区中 建立一段表，用于从逻辑段到物理内存区的映射 段表中的表项存放段的基址和段的长度 段表通常放在内存中,2. 段表,图 4-16 利用段表实现地址映射,图 4-17 分段系统的地址变换过程,3. 地址变换机构,4. 分页和分段的主要区别,

13、(1) 页是信息的物理单位，分页是为实现离散分配方式，分页仅仅是由于系统管理的需要而不是用户的需要。 段则是信息的逻辑单位，它含有一组其意义相对完整的信息。 分段的目的是为了能更好地满足用户的需要。,(2) 页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的； 而段的长度却不固定，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。 (3) 分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需利用一个记忆符，即可表示一个地址； 而分段的作业地址空间则是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。,4.4.3 信息共享,图

14、4-18 分页系统中共享editor的示意图,图 4-19 分段系统中共享editor的示意图,4.4.4 段页式存储管理方式,1. 基本原理,图 4-20 作业地址空间和地址结构,图 4-21 利用段表和页表实现地址映射,2. 地址变换过程,图 4-22 段页式系统中的地址变换机构,4.5 虚拟存储器的基本概念,4.5.1 虚拟存储器的引入,1. 常规存储器管理方式的特征,一次性。(全部装入，但浪费空间) (2) 驻留性。 （长期驻留，直到结束）,2. 局部性原理,早在1968年， Denning.P就曾指出： (1) 程序执行时，除了少部分的转移和过程调用指令外， 在大多数情况下仍是顺序执

15、行的。 (2) 过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域， 但经研究看出，过程调用的深度在大多数情况下都不超过5。 (3) 程序中存在许多循环结构，这些虽然只由少数指令构成， 但是它们将多次执行。 (4) 程序中还包括许多对数据结构的处理， 如对数组进行操作， 它们往往都局限于很小的范围内。,局限性又表现在下述两个方面： (1) 时间局限性。某条指令或数据一旦执行或访问，则不久以后该指令可能再次执行或访问。 典型原因：是由于在程序中存在着大量的循环操作。 (2) 空间局限性。一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即访问可能集中在一定范围内 典型情况

16、：程序的顺序执行。,3. 虚拟存储器定义,所谓虚拟存储器， 是指具有请求调入功能和置换功能， 能从逻辑上对内存容量加以扩充的一种存储器系统。 其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本接近于外存。 虚拟存储技术是一种性能非常优越的存储器管理技术，故被广泛地应用于大、 中、 小型机器和微型机中。,4.5.2 虚拟存储器的实现方法,1. 分页请求系统,（1）硬件支持。 请求分页的页表机制，它是在纯分页的页表机制上增加若干项而形成的，作为请求分页的数据结构； 缺页中断机构，即要访问的页面尚未调入内存时 便产生一缺页中断，以请求OS将所缺的页调入内存； 地址变换机构。(增加了产生和处理缺页中断和换出功能),4.5.3 虚拟存储器的特征,多次性（作业分多次调入内存） 对换性（允许换入换出） 虚拟性 （从逻辑上扩充内存容量）,4.6 请求分页存储管理方式,4.6.1 请求分页中的硬件支持,1. 页表机制,访问字段A：被访问的次数或多长时间没被访问。,2. 缺页中断