5、内存内存存储器的层次结构程序的装入和链接连续分配存储管理方式对换分页存储管理方式分段存储管理方式虚拟存储器概述请求分页存储管理方式页面置换算法“抖动”与工作集请求分段存储管理方式存储器的多层结构多层结构存储器系统产生的原因：无法同 时满足三个条件：³存储器的速度与处理机的速度相匹配（因为许 多指令涉及存储器访问）³存储器具有非常大的容量³存储器的价格很便宜存储器的层次结构存储器的层次结构寄存器、高速缓存：少量的、非常快速、昂贵 、易变；高速缓存是介于寄存器和存储器之间 的存储器主存储器：GB级、中等速度、中等价格、易 变磁盘缓存：依托于固定磁盘，提供对主存储器 存储空间的扩充寄存器和主存（包括高速缓存、主存储器、磁 盘缓存）又被称为可执行存储器磁盘、可移动存储介质：GB级到PB级、低速 、价廉、不易变内存存储器的层次结构程序的装入和链接连续分配存储管理方式对换分页存储管理方式分段存储管理方式虚拟存储器概述请求分页存储管理方式页面置换算法“抖动”与工作集请求分段存储管理方式对用户程序的处理步骤绝对装入方式程序中的逻辑地址和实际内存地址一致适用于仅能运行单道程序的小系统程序中的绝对地址可由程序员直接给出³要求熟悉内存使用³数据结构或程序修改后可能要改程序中的很多 处地址绝对地址也可由程序编译器转换得出静态重定位装入方式程序中的逻辑地址从0 地址开始适用于多道程序环境地址转换在程序装入 时一次完成，不再改 变动态重定位装入方式静态装入不适用于进程切换，每次换入的 内存位置可能不同程序装入时保留相对地址，程序执行时进 行地址转换需要重定位寄存器加速地址转换程序的静态链接方式在程序运行之前，先将各目标模块及它们 所需的库函数，链接成一个完整的装配模 块，以后不再拆开。
程序的静态链接方式1.修改各模块的起始地址2.修改模块中所有涉及相对地址的指令程序装入时的动态链接方式程序编译后所得到的一组目标模块，装入 目标模块时，若发生外部模块调用，装入 程序将外部模块调入内存，同时修改目标 模块中的相对地址优点： 1.便于修改和更新：因为各目标模块是分开存 放的 2.便于实现对目标模块的共享：OS很容易将一 个目标模块，链接到几个应用模块上，实现 多个应用程序对该模块的共享 程序运行时的动态链接方式某些模块有时不需要运行，如异常处理模 块需要用到的模块才进行链接优点： 1.加快程序的装入过程：凡在执行过程中未被 用到的目标模块，都不会被调入内存和被链 接到装入模块上2.节省内存空间：仅装入运行所需要的模块 内存存储器的层次结构程序的装入和链接连续分配存储管理方式对换分页存储管理方式分段存储管理方式虚拟存储器概述请求分页存储管理方式页面置换算法“抖动”与工作集请求分段存储管理方式连续分配存储管理方式连续分配指为一个程序分配一个连续的内 存空间连续分配方式分为四类：³单一连续分配³固定分区分配³动态分区分配³动态重定位分区分配单一连续分配单道程序环境下内存分为系统区和用户区系统区仅提供给OS使用，在内存的低址部分用户区仅装有一道用户程序，即整个内存的用 户空间由该程序独占缺点：³不支持多道 ³主存利用率不高 ³程序的运行受主存容量限制 固定分区分配多道程序环境下整个用户空间划分为若干个固定大小的区 域每个分区中只装入一道作业固定分区分配1.划分分区的方法³分区大小相等：所有的内存分区大小相等，缺 点是缺乏灵活性. ³分区大小不等：存储器分区划分为若干个大小 不等的分区. 固定分区分配2.内存分配³建立分区使用表，记录每个分区的起始地址、大小 及状态（是否已分配）。
³当用户程序装入时，由内存分配程序依据程序大小 检索该表，从中找出一个能满足要求的、尚未分配 的分区，将之分配给该程序，然后将该表项中的状 态置为“已分配” ³若未找到大小足够的分区，则拒绝为该用户程序分 配内存 ³若每个分区的大小固定，会造成存储空间浪费 固定分区分配动态分区分配根据进程的实际需要动态分配内存空间1.动态分区分配中的数据结构 2.动态分区分配算法 3.分区分配操作动态分区分配1.动态分区分配 中的数据结构 ³空闲分区表或 空闲分区链动态分区分配2.动态分区分配算法³传统的顺序式搜索算法³索引式搜索算法动态分区分配3.分区分配操作³分配内存：根据分配算法，从空闲分区表中找 到合适的分区若分区大小比请求空间大（超 过分区最小极限值），则对分区进行分割³回收内存：当进程运行完毕释放内存时，系统 根据回收区的首地址，合并回收进空闲分区表①回收区与插入点的前一个空闲分区F1相邻接②回收分区与插入点的后一空闲分区F2相邻接③回收区同时与插入点的前、后两个分区邻接④回收区既不与F1邻接，又不与F2邻接基于顺序搜索的分区分配算法为了实现动态分区分配，通常是将系统中的空 闲分区链接成一个链。
顺序搜索，是指依次搜 索空闲分区链上的空闲分区，寻找一个大小能 满足要求的分区 ³首次适应算法：选择分区时总是按地址从高到低搜 索³循环首次适应算法：类似首次适应法每次分区时， 总是从上次查找结束的地方开始³最佳适应算法：在空闲块表中找到一个不小于请求 的最小空块进行分配 ³最坏适应算法：在空闲块表中找到一个不小于请求 的最大空块进行分配基于索引搜索的分区分配算法当系统很大时，系统中的内存分区可能会很多 ，相应的空闲分区链就可能很长，这时采用顺 序搜索分区方法可能会很慢 1.快速适应算法：相同容量的分区使用一个空闲 分区链表，所有链表的头指针通过一张管理索 引表访问³根据进程长度从索引表中找到合适的空闲分区链 表³从链表中取第一块分区进行分配，不对分区进行 分割³时间性能比顺序搜索高，空间利用存在浪费基于索引搜索的分区分配算法2.伙伴系统：初始内存是一个大小为2m的空闲 分区，分区可以对半分割，分区大小均为2 的k次幂³若申请长度为n的内存空间（2i-1i，则把空闲块分 为2j-1、2j-2、…、2i、2i的块，并把其中2i的块分配 给进程³若回收大小为2i的空闲块，要查询是否存在另一 个大小为2i的空闲块，若有则需合并成2i+1的空闲 块。
³时间性能高于顺序搜索，低于快速适应算法空 间利用率优于快速适应算法，低于顺序搜索³多处理机系统中广泛应用基于索引搜索的分区分配算法3.哈希算法：改良上述两种索引搜索方法³原因：“根据申请空间查找对应的空闲分区链 表表头指针”这个操作当表项多时速度慢³算法先构造一张以空闲分区大小为关键字的哈 希表，再根据所需空闲分区大小，通过哈希函 数计算，得到在哈希表中的位置，从而得到响 应的空闲分区链表可重定位分区分配连续分配方式的特点：一个程序必须装入一片 连续的内存空间当计算机运行一段时间后， 内存空间将会分割成许多小分区，缺乏大的空 闲空间装入大作业的方法：移动内存中的所有作业使 之相邻这样把原来分散的多个小分区拼接成 一个大分区，就可把大作业装入 技术需求：紧凑、动态重定位、动态重定位分 区分配算法 可重定位分区分配紧凑可重定位分区分配动态重定位可重定位分区分配返回分区号和首地址动态重定位分区分配算法 内存存储器的层次结构程序的装入和链接连续分配存储管理方式对换分页存储管理方式分段存储管理方式虚拟存储器概述请求分页存储管理方式页面置换算法“抖动”与工作集请求分段存储管理方式对换又称为交换技术，在内存和外存间交换数 据，用于解决内存太小的问题。
早期的分时系统中的对换技术：所有的用 户作业放在磁盘上，每次调一个作业进内 存，当时间片用完后再调至外存的后备队 列，再从后备队列中调另一个作业进内存 多道程序环境多道程序环境：³内存中的某些进程由于某事件尚未发生而被阻 塞运行，但占用大量内存空间，甚至可能出现 内存中所有进程都被阻塞³某些进程因内存空间不足，一直不能运行把内存中暂时不能运行的进程或者暂时不 用的程序和数据换出到外存上；再把已具 备运行条件的进程或进程所需要的程序和 数据换入内存 对换的类型 1.整体对换：即处理机中级调度以进程为 对换单位2.页面（分段）对换 ：以进程的 “页面”或“ 分段”为单位进行对换为实现进程对换，系统必须实现的功能: 1.对换空间管理2.进程的换出3.进程的换入对换空间管理在具有对换功能的OS中，通常把硬盘空间分 为文件区和对换区两部分文件区占大部分， 访问频率低交换区占小部分，用于存放内存 中换出的进程对换空间管理的主要目标：³文件区管理的主要目标：首先是提高文件存储空间 的利用率，然后才是提高对文件的访问速度³对换空间管理的主要目标：是提高进程换入和换出 的速度，然后才是提高文件存储空间的利用率.对换空间管理对换区空闲盘块管理中的数据结构³与内存在动态分区分配方式中所用数据结构相 似，即同样可以用空闲分区表或空闲分区链。
在空闲分区表的每个表目中，应包含两项：对 换区的首址及其大小，分别用盘块号和盘块数 表示对换空间管理对换空间的分配与回收³由于对换分区的分配采用的是连续分配方式， 因而对换空间的分配与回收，与动态分区方式 时的内存分配与回收方法雷同³分配算法可以是首次适应算法、循环首次适应 算法或最佳适应算法等.进程的换出1.选择被换出的进程 ³首先选择处于阻塞状态或睡眠状态的进程³其次选择优先级最低的进程 2.进程换出过程 ³申请对换空间若申请成功就启动磁盘，将该进程 的程序和数据传送到磁盘的对换区上³若传送过程未出现错误，则回收进程所占用的内存 空间，并对进程控制块和内存分配表等数据结构做 相应的修改³若内存中还有阻塞进程，则继续执行换出过程进程的换入 对换进程将定时执行换入操作³查看PCB集合中所有进程的状态，为“就绪”已换 出且换出时间最久的进程申请内存；³如果申请成功，则将进程调入内存；如果失败 ，则需先将内存中的某些进程换出，腾出足够 的内存空间后，再将进程调入³若还有可换入的进程，则继续执行换入过程， 直到再无“就绪且换出”状态的进程，或已无足 够的内存来换入进程内存存储器的层次结构程序的装入和链接连续分配存储管理方式对换分页存储管理方式分段存储管理方式虚拟存储器概述请求分页存储管理方式页面置换算法“抖动”与工作集请求分段存储管理方式离散存储管理方式连续分配的存储管理方式 存在碎片问题。
使用“紧凑”技术可以解决这个问题，但时间 代价较高离散分配：给一个进程分配许多不相邻的 分区离散分配的类型分页：内存空间分成固定大小的物理块（ frame，如1KB ）用户程序的地址空间分 为同样大小的区域，称为页从0开始编制 页号，页内地址是相对于0编址分段：用户程序分成大小不同的段，每段 定义一组相对完整的信息存储器分配以 段为单位段页式：目前的主流方式，具有两者的优 点分页存储管理的基本方法页：用户程序的地址空间，分为若干个固 定大小的区域，称为“页”物理块：内存空间分为若干个物理块或页 框，页和块的大小相同页面大小 ：小的页面可以减少内存碎片， 增加进程的页表长度，占用大量内存，降 低页面换进换出的效率大的页面可以减 少页表长度，提高页面换进换出的效率， 增加页内碎片 建议的大小：4KB或8KB分页存储管理的基本方法地址结构 31 12 11 0对某特定机器，其地址结构是一定的若 给定一个逻辑地址空间中的地址为A，页面 的大小为L，则页号P和页内地址d可按下式 求得：页号P位移量W操作系统的内存寻址能力操作系统内存寻址 普通32位Windows3GB 使用PAE技术的32位 Windows2003Standard：32GB Enterprise：64GB 64位WindowsXPEdition：128GB。