存储器管理

null第四章    存储器管理第四章    存储器管理第一节    程序的装入和链接 （了解） 第二节    连续分配方式（基础） 第三节    基本分页存储管理方式（重点） 第四节    基本分段存储管理方式（重点） 第五节    虚拟存储器的基本概念（基础） 第六节    请求分页存储管理方式（重点） 第七节    页面置换算法（重点） 第八节    请求分段存储管理方式（重点）存储器的层次结构存储器的层次结构1. 存储器的层次结构 在现代计算机系统中，存储器是信息处理的来源与归宿，占据重要位置。但是，在现有技术条件下，任何一种存储装置，都无法同时从速度与容量两方面，满足用户的需求。实际上它们组成了一个速度由快到慢，容量由小到大的存储装置层次。 存储器的层次结构各种存储器各种存储器内存RAM： 若干兆字节、中等速度、中等价格、易变的 高速缓存Cache： 少量的、非常快速、昂贵、易变的 磁盘： 数百兆或数千兆字节、低速、价廉、不易变的 由操作系统协调这些存储器的使用存储管理的目的存储管理的目的存储器管理的主要对象是内存（主存），而外存主要存放文件，对外存的管理主要是文件管理。 （1）主存的分配和管理 （2）提高主存储器的利用率 （3）“扩充”主存容量 （4）存储保护4.1  程序的装入和链接4.1  程序的装入和链接从源程序到程序执行 地址空间的概念 重定位的概念 程序的装入 程序的链接 编译、链接、装入 编译、链接、装入编译：编译程序 由编译程序（Compiler）将用户源代码编译成若干个目标模块。 链接：链接程序 由链接程序（Linker）将编译后形成的一组目标模块，以及它们所需要的库函数链接在一起，形成装入模块。 装入：装入程序 由装入程序（Loader）将装入模块复制到内存中。 从源程序到程序执行 从源程序到程序执行 库装入模块库主子1子2库主子1子24.1.1 程序的装入4.1.1 程序的装入就是把链接好的装入模块装入“内存”。 装入方式 绝对装入：单道（任务）；装入位置是固定的。程序员直接编址或由汇编、编译程序完成地址重定位。 可重定位装入（静态重定位） 动态运行时装入（动态重定位） 提示：通常链接、装入程序是一体的。 地址空间的概念 地址空间的概念物理（绝对）地址——程序执行 每个内存单元的固定顺序地址（编号）。 逻辑（相对）地址——装入（汇编编译） 被链接装配（或汇编、编译）后的目标模块所限定的地址的集合； 相对于某个基准量（通常为：0）的编址。null 1. 绝对装入方式 程序中所使用绝对地址（在编译或汇编时给出， 也可由程序员直接赋予），要求程序员熟悉内存的使用情况，而且一旦程序或数据被修改后，可能要改变程序中的所有地址。 因此，通常是宁可在程序中采用符号地址，然后在编译或汇编时，再将这些符号地址转换为绝对地址。 此时程序中的逻辑地址与实际内存地址完全相同。 1. 绝对装入方式 2.可重定位装入方式 2.可重定位装入方式绝对定位方式只能将目标模块装入到内存中事先指定的位置（必须预知），只适合单道程序。 在多道程序中，所得到的目标模块的起始地址通常以“0”开始的，程序中的其它地址也都是相对于起始地址计算的（不必预知），这时采用可重定位装入方式。 注意：在采用可重定位装入内存后，装入的模块的所有逻辑地址与实际装入内存的物理地址不同。 null重定位的概念： 把在装入时对目标程序中指令和数据的修改过程称为重定位。它是将逻辑地址变换为物理地址的过程。 重定位的类型： 静态重定位：程序执行前，一次性链接装入程序，以后不在改变。 动态重定位：处理机每次访问主存时，有动态地址变换机构（硬件）自动执行。重定位概念null 作业地址空间 内存空间可重定位装入图 4-2 作业装入内存时的情况静态重定位装入内存的情况 问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 问题 问题的提出：可重定位装入方式，虽然可以将装入模块装入到内存中的任何允许的位置上，但不允许程序运行时在内存中移动位置（即不允许程序在内存中的物理位置发生变化）。 问题的解决：把装入模块装入内存后，并不立即把装入模块中的相对地址装换为绝对地址，而是在程序真正要执行时才做地址转换，即采用动态运行时装入方式（装入内存后的所有地址都是相对地址）。 3. 动态运行时装入方式 问题的提出：可重定位装入方式，虽然可以将装入模块装入到内存中的任何允许的位置上，但不允许程序运行时在内存中移动位置（即不允许程序在内存中的物理位置发生变化）。 问题的解决：把装入模块装入内存后，并不立即把装入模块中的相对地址装换为绝对地址，而是在程序真正要执行时才做地址转换，即采用动态运行时装入方式（装入内存后的所有地址都仍然是相对地址）。 3. 动态运行时装入方式4.1.2 程序的链接4.1.2 程序的链接链接概念： 把一个程序相关的一组目标模块和系统调用模块（库函数）链接形成一个整体，装入模块的过程。 具体工作： 对相对地址的修改； 变换外部调用符号。null链接方式 （1）静态链接： 程序在运行之前，事先将各个目标模块及程序所需的各个库函数，链接成一个完整的装配模块（可执行文件），以后不在拆开。 （2）装入时动态链接： 将用户原程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的方式； （3）运行时动态链接： 对于某些目标模块程序的链接是在程序执行中需要该模块时，才对它进行链接； 1.静态链接方式 1.静态链接方式 2.装入时动态链接（1）将用户原程序编译后所得到的一组目标模块，都是分开存放的； （2）若发生一个外部调用事件，将引起装入程序去找出相应的外部目标模块，在将它装入内存时，采用边装入边链接的方式，同时修改目标模块中的相对地址。 优点： （1）便于修改和更新。 （2）便于实现对目标模块的共享。 2.装入时动态链接 3.运行时动态链接 将对某些模块的链接推迟到执行时才执行。 即：在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存， 把它链接到调用者模块上。 凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上。 优点： 最小化快速装入，节省内存。 3.运行时动态链接4.2  连续分配方式4.2  连续分配方式 为用户程序分配一个连续的内存空间。曾被广泛应用，且现在仍被采用。 1.单一连续分配 2.固定分区分配 3.动态分区分配 4.可重定位分区分配 5.实存扩充技术4.2.1 单一连续分配4.2.1 单一连续分配单一连续分配的基本思想 把内存分为系统区和用户区。 系统区仅供OS使用，通常放在低址部分，系统区以外的全部内存空间是用户区。 单一连续分配的特点 只能用于单用户、单任务的OS中。 软件简单，硬件要求低（无需存储保护） 实例 MS-DOS， CP/M，RT-11null4.2.2 固定分区分配4.2.2 固定分区分配划分分区的方法 分区大小相等 分区大小不相等 内存分配管理 分区按大小排队； 分区使用 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf （MBT）：起始地址、大小、状态； 由内存分配程序检索分区使用表，找到符合要求的分区。 实例： 60年代的控制相同对象的控制系统:IBM360的MFT， (每个对象的控制程序大小相同,所需要的数据也一致) 缺点：造成存储空间的浪费null4.2.3 动态分区分配4.2.3 动态分区分配思想 应作业、进程的实际需要，动态地分配内存空间，位置和大小都不固定。 1.分区分配中的数据结构 1.分区分配中的数据结构数据结构的两种形式: 空闲分区表：一个空闲分区占一个表目，包括： 分区序号、分区始址、分区大小 空闲分区链： （1）分区起始部分组成： 控制分区分配信息+链接各分区前向指针+后向指针 （2）分区尾部部分组成： 状态位（“0”分区未分配，“1”已分配）+分区大小 2.存储分配算法 2.存储分配算法（1）首次（最先）适应算法： 思想:从链首开始循序查找，直至找到一个大小合适的空闲分区为止； 优点：优先利用内存低地址部分空闲空间，保留大量高地址空间，以便为后到达的大作业分配大的内存空间。 缺点： a.低地址空间因被划成很小的空间，很难再利用。 b.每次查找都从低地址部分开始，增加系统查找可用空闲分区的开销；null（2）循环首次适应算法： 思想: 每次查找空闲分区不是从链首开始，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个满足条件的空闲分区； 利用查寻指针，指示下一次起始查寻的空闲分区，并循环查找，如果最后一个（链尾）空闲分区的大小仍不合适，则返回到第一个空闲分区去比较大小是否合适。 优点： 内存中的空闲分区分布均匀；减少查找空闲内存开销； 缺点： 系统缺乏大的空闲分区； null（3）最佳适应算法： 思想: 每次分配内存时，将所有的空闲分区按其容量大小从小到大的顺序排成一个空闲分区链，依次查找大小最接近的空闲分区予以分配，保证较小的碎片。 优点： 大多数作业能够以较快的速度分配到合适的空闲分区。 缺点： 宏观上，系统会残留许多难以利用的小的空闲区。null（4）最差适应算法： 思想: 每次分配内存时，将所有的空闲分区按其容量大小从大到小的顺序排成一个空闲分区链，依次查找大小最接近的空闲分区予以分配，保证较小的碎片。 优点： 大多数作业能够以较快的速度分配到合适的空闲分区。 缺点： 系统会残留许多难以利用的小的空闲区。例题1：存储分配算法例题1：存储分配算法 在一个使用交换技术的系统中，按地址从低到高排列的内存空间长度是：10KB、4KB、20KB、18KB、7KB、9KB、12KB、15KB。对于下列顺序的作业请求：⑴12KB ⑵ 10KB ⑶ 15KB ⑷ 18KB ⑸ 12KB 问题: (1)分别使用首次(最先)适应算法、循环首次适应算法、最佳适应算法、最差适应说明空间的使用情况; (2)说明暂不能分配情况的处理方法。nullnull 3.分区分配操作 3.分区分配操作 为了减小大量难以利用的小空闲分区造成的查找开销，在进行内存分配时，可以事先设定一个限定值，当找到的分区中剩余空间小于该值时，将不再进行分区的分割，而是把整个分区分配给请求者。（1）分配内存（1）分配内存 空闲分区大小（ M.Size ）与所需空间大小(U.Size )“匹配”条件： M.Size – U.Size ≦ Size （Size为系统规定不再分割的剩余分区的尺寸） 满足：将整个空闲分区分配给所需者； 不满足：剩余部分挂接到空闲分区链（表）上。nullnull 进程运行完毕后释放内存时，系统先检查是否有空闲分区与回收区相临： 若有则必须修改空闲分区表或空闲分区链将它们进行合并，回收区或合并后得到的新空闲分区将根据分配算法按它的起始地址或分区大小插入空闲分区表或空闲分区链。 （2）回收内存null 系统根据回收区的首地址，从空闲区链（表）中找到相应的插入点，但可能会出现以下四种情况： 回收区与插入点的前一个空闲分区F1相邻接； 回收区与插入点的后一个空闲分区F2相邻接； 回收区与插入点的前、后两个空闲分区相邻接； 回收区不与任何一个空闲分区相邻接； 缺点 管理复杂，总会有闲置的小分区——“碎片”。 null(a) (b) (c) 图 4-7 内存回收时的情况(a) ：合并（F1和回收区），F1的首址为新的首地址； (b)：合并（回收区和F2）， 回收区的首址为新的首地址； (c)：合并（F1、回收区和F2），F1的首址为新的首地址；4.2.4 可重定位分区分配 1.动态重定位的引入4.2.4 可重定位分区分配 1.动态重定位的引入 随着系统接收的作业的增加，内存中连续的大块分区将不存在，产生了大量的“碎片”。 前提:新的作业无法装入到每个“碎片”小分区上运行，但所有碎片的空间总和可能大于需求。 解决 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 :通过移动内存中作业的位置，把原来多个分散的小分区“拼接”成一个大分区的方法，称为“拼接”或“紧凑” /“紧缩”/“”澄清“ 。null 2.动态重定位的实现 2.动态重定位的实现动态重定位概念: 作业被装入到内存中的相对地址要转换为物理地址，被推迟到程序指令真正要执行的时候进行。null实现： （1）必须由硬件地址变换机构重定位寄存器支持：存放程序的起始地址; （2）当系统对内存进行了“紧凑”，使得 真正访问的内存物理地址= 相对地址+重定位寄存器中地址null动态重定位装入方式动态运行时装入null优点： 消除“碎片”，提高了内存利用率，同时提高了系统效率。 缺点： （1）需要动态重定位“硬件”机构支持，增加了系统成本； （2）轻度降低了程序执行速度； （3）“紧凑”处理增加了系统开销。null3.可重定位分区分配算法4.2.5 对换技术（Swapping） 1.对换的引入4.2.5 对换技术（Swapping） 1.对换的引入是实存扩充技术中的一种。 用于解决内存不足的问题； 通过外存缓冲，以进程为单位“滚进滚出” 。一个作业的所有进程不必同时位于内存中； 对换的时机：创建新进程而内存不足时。 对换概念 对换概念 指把内存中暂时不能运行的进程或暂时不能用的程序和数据，调出到外存上，以便腾出足够的内存空间。 同时当内存中又稍有空闲时，把已具备运行条件的进程或进程所需要的程序和数据，调入内存。 对换类型 对换类型整体对换（进程对换） 广泛应用于分时系统中； 部分对换（分页、分段对换） 为了支持虚拟存储系统： 分页对换：以“页”为对换单位进行对换； 分段对换：以“段”为对换单位进行对换。 2.进程对换系统要实现的功能 2.进程对换系统要实现的功能（1）对换空间的管理 把外存分为： a.文件区（存放文件）— 提高文件存储空间的利用率; b.对换区（存放内存换出的进程）— 提高进程换入/出的速度； 对换空间管理的主要目标是提高进程换入、换出的速度，因此常将对换空间设置在高速的磁盘中，采用连续分配方式。null（2）进程的换入和换出 a.进程的换出： 条件:创建进程需更多的内存空间时, 或内存空间不够用时; 过程:选择阻塞、优先级最低的进程作为换出进程——启动盘块—将进程的程序和数据传送到磁盘的对换区上。 b.进程的换入： 条件:当内存空间稍有空闲时; 过程:找出就绪、但已经换出（到磁盘上）的进程——将其中换出时间最久的进程——将其换出,直至已经无可以换入的进程或无可以换出的进程为止。4.3 基本分页存储管理方式4.3 基本分页存储管理方式 连续分配方式 “碎片”过多，“紧凑”方法开销很大，将一个进程直接分散地装入到许多不相邻接的分区中，无须“紧凑”，促使人们产生了离散分配的管理思想, 从而引入了“分页”分配管理的管理方式。 分为： （1）基本分页（纯分页）管理： 不具备页面置换功能； 不具备支持实现虚拟存储器的功能； 要求把每个作业全部装入内存后才能运行。 （2）支持虚存管理的请求分页管理。4.3.1 页面与页表4.3.1 页面与页表01234567891110内存用户作业0 2K-1第2页 （页长2K）0 2K-14号页架 （页长2K） 1.页面 1.页面页面（页）： 将一个进程的逻辑地址空间分成若干个大小相等的片；顺序编号（从0开始）。 物理块（页框/架）： 把内存空间分成与页面相同大小的若干个存储块；顺序编号（也从0开始）。 null页内碎片：是指在为进程分配内存时，以块为单位将进程中的若干个页也分别装入到多个可以不相邻接的物理块中，进程的最后一页经常装不满一块，而又不可以利用的碎片，称为“页内碎片”。 页面大小： （1）页面过小： 内存碎片小—页面多—页表过长—占用内存大 （2）页面过大： 页面少—页表长度短—占用内存大—页内碎片大 （3）页面大小适中： 2n Bytes， 一般在：512B ~ 8/32K 2.分页地址结构 2.分页地址结构 逻辑地址 n-1 k k-1 0线性的逻辑地址长度为n位, 包括两部分： 页号P：n-k位,即:地址空间最多允许有2n-kB页； 位移量W（页内位移量，即页内地址）：k位,页内地址大小=2kB 若给定一个逻辑地址空间中的地址为A，页面大小为L，则可以由 公式 小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载 求出： 页号P=INT[A/L]，页内地址d=[A] mod L 例如：系统的页面大小L为1KB，A=2170B， 求出P=2,d=122 null逻辑地址 31 12 11 0页号P：12~31共20位 地址空间最多允许有220B=1M页，即每个进程占用1M个页。 位移量W：0~11共12位 页内地址大小（即每页的大小）为212B=4KB。 例：现代的大多数计算机系统的逻辑地址空间都支持很大的逻辑地址空间（232——264）B，如下逻辑地址长度为32位，包括两部分： 3.页表 3.页表页表： 系统为每一个进程建立的，在内存中找到每个页面所对应的物理块号的一张页面映像表。 一个进程占用多少页，就在页表中有多少页表项。 页表的作用：实现从页号到物理块号的地址映射。 数据结构： 页号、块号、存取控制字段（控制存储块中的内容是允许读/写、只读、只执行）。null内存图4-11 页表的作用4.3.2 地址变换机构4.3.2 地址变换机构地址映射——从逻辑地址到物理地址的变换过程。 将用户地址空间中的逻辑地址变换为内存空间中的物理地址，系统设置了地址变换机构。 由于页面地址和物理地址一一对应，所以地址变换机构只是将逻辑地址中的页号，转换为内存中的物理地址的物理块号。借助页表完成。逻辑地址 物理地址 1.基本的地址变换机构 1.基本的地址变换机构页表存放在内存系统区的一个连续空间中； 分页地址变换机构变换过程： （1）进程执行之前：PCB （内存中的页表始址+页表长度） （2）进程调度后：页表寄存器PTR （内存中的页表始址+页表长度） （3）检索页表 条件：页表长度>逻辑地址中的页号 不成立：所访问的地址越界，产生一地址越界中断； 成立：未地址越界，则： 由“页表始址+页号x页表长度”找到该页号在页表中的位置。null 2.具有快表的地址变换机构 2.具有快表的地址变换机构提出改进的原因： 计算机CPU存取数据需要访问内存两次，处理速度降低为1/2。 改进方法： 利用联想寄存器（快表）——并行查询； 空间大小： 几K到几百K ，存放16~512个页表项；null实现原理： 快表与页表同时访问： （1）在快表中找到相匹配的页号—— 直接从快表中读出对应物理块号； （2）在快表中没有找到相匹配的页号—— 还须找页表，再从页表中对出物理块号； 再将此页表项存入快表中，重新更新快表。 优点：加快了地址变换的速度。null4.3.3 两级和多级页表4.3.3 两级和多级页表问题提出： 现代大多计算机的逻辑地址空间很大（232~264），若规定页面大小为212B=4KB,则页号P=int(232/212)=220=1M，即相应的页表项有1M个，且要求是连续的，采用离散分配方式难以解决大页表占用大的连续存储空间问题。 问题解决： 采用两级页表和多级页表，只将当前需要的部分页表项调入内存，其余的页表项仍然留在磁盘上，需要时时在调入。 1.两级页表 1.两级页表解决大页表占用大的连续存储空间的问题； 外层页表：记录每个页表分页的始址； 逻辑地址： 外层页号+外层页内地址+页内地址 逻辑地址32位的线性地址系统，当页面大小为4KB时，页若采用一级页表，页表项有1M个，若采用两级页表分页，每个页表有210个页表项。null（包含该页中的物理块号b） 2.多级页表 2.多级页表 将外层页表再做分页，将各个分页离散地装入到不相邻接的物理块中，在利用第2级的外层来映射它们之间的关系。 逻辑地址映射到物理地址的方法和二级页表相同。基本分页的特点基本分页的特点优点： 存在页内碎片，但碎片相对较小，内存利用率较高； 实现了离散分配，消除了程序浮动。 缺点： 需要专门的硬件支持，尤其“快表”； 内存访问的效率下降; 不能实现真正的共享，不支持动态链接。4.4  基本分段存储管理方式4.4  基本分段存储管理方式基本分段管理思想的引入 基本原理 地址变换 分段与分页的主要区别 段页式存储管理方式4.4.1 分段管理思想的引入4.4.1 分段管理思想的引入 引入分段存储管理方式，主要是为了满足用户和程序员的下列需要： 方便编程：把用户作业按逻辑关系划分为若干个段，通过逻辑地址的段名（段号）和段内偏 移量（段内地址）来访问数据。如： LOAD 1，[A]| 信息共享:分段便于共享信息的逻辑单位 信息保护 动态增长 动态链接：先将程序对应的目标程序装入内存并不启动运行，需要调用某段时，才将该段调入内存并且进行链接后运行。