《第四章存储器管理S知识分享》由会员分享，可在线阅读，更多相关《第四章存储器管理S知识分享（88页珍藏版）》请在金锄头文库上搜索。
1、第四章 存储器管理,4.1 概述,存储体系,存储层次结构,依据访问速度的匹配关系、容量要求和价格，在存储技术和CPU寻址技术许可的范围内组织合理的存储结构。,存储管理的任务 存储分配和回收 地址变换(地址重定位) 存储共享和保护 存储器扩充, 重定位的方式 静态重定位：目标代码装入内存时，一次性进行 地址转换。 动态重定位：目标代码装入内存时，先不进行地 址转换（即原代码装入），在执行 时，再实施地址转换。, 地址重定位过程 例：,0,0,4.2 程序的装入和链接,1）源程序转换成可执行程序过程 编译 链接 装入,2）程序的链接与装入 程序的链接（模块拼接） 静态链接：装入前先链接 动态链接：
2、装入时（或执行时）才进行链接 程序的装入 绝对装入：目标代码与装入位置地址相一致 静态重定位装入：装入时实现地址转换 动态重定位装入：待执行时再进行地址转换 分配方式：连续分配或者离散分配,4.3 连续分配方式 单一连续区分配 固定分区分配 可变（动态）分区分配 可重定位分区分配 伙伴系统,1）单一连续分配 只能用于单用户、单任务的操作系统中。 系统区：仅提供给操作系统使用，OS通常驻留在 内存的低址部分； 用户区：指除系统区以外的全部内存空间提供给某 一用户使用。,2）固定分区分配 算法思想内存可用区划分成若干个大小固定的分区，这些分区大小可以相同也可不同，每个分区分别装入一道作业的代码（数
3、据）。 算法实现建立一个分区说明表来登记和管理整个内存。在这个表中登记了每一个分区的大小，起始地址和分配状态。,分区说明表,已分配,260K,200KB,4,已分配,120K,40KB,2,未分配,160K,100KB,3,已分配,100K,20KB,1,分配状态,起始地址,大小,分区号,例：,分配：查分区说明表，找到一个 足够大的空闲分区分配之,回收：将回收分区对应的分区说明 表状态改为“空闲”。,特点,与单一连续分配相比，内存利用率提高，内存可同时装入多道作业代码，算法实现简单； 分区一次性全部分配出去存在浪费，产生内碎片（分区内不能被利用的小空间）。,3）可变分区分配 算法思想按需分配：
4、每次从空闲分区中按作业大小分配一块给该作业，然后将剩下的部分再作为空表块留在空闲分区中。(分区的大小和个数不固定) 算法实现建立相关空闲分区表，用来记录每个空闲分区的大小、起始地址。空闲分区的管理常采用链表形式。,分区分配算法： 寻找某个空闲分区，其大小需大于或等于程序的要求。若是大于要求，则将该分区分割成两个分区，其中一个分区分配给用户，而另一个分区仍留在空闲分区链表中。 首次适应算法 循环首次适应算法 最佳适应算法 最差适应算法 快速适应算法,首次适应算法,算法思想：将所有的空闲分区按照地址递增的顺序排列,分配过程：每次分配时，从空闲分区链的链首开始查找， 找到符合要求的第一个分区，一分为
5、二分配,特点：较大的空闲分区可以被保留在内存高地址空间； 但随着低端分区不断划分而产生较多小分区，每次 分配时从头开始查找，时间开销大。,循环首次适应算法,算法思想：将所有的空闲分区按照地址递增的顺序排列，从上次分配的分区的下一个空闲分区起查找，找到符合要求的第一个分区,分配过程：设置一个起始查找指针，指向上次分配的分区的下一个空闲分区，分配时总是从起始查找指针所指向的表项开始查找，找到第一个满足要求的空闲区时，一分为二分配,特点：该算法的分配和释放的时间性能较好； 但较大的空闲分区不易保留。,最佳适应算法,算法思想：将空闲分区按容量递增顺序排序，,分配过程：每次分配时，从空闲分区链的链首开始
6、查找， 找到符合要求的第一个分区，一分为二分配,特点：较大的空闲分区可以被保留； 但容易形成很多外碎片（分区之间不能被利用的空间）,最坏适应算法,算法思想：将空闲分区按容量递减顺序排序,分配过程：只需查找空闲区链最前面的空闲块即可,特点：分配的时候，只需查找一次，分配的算法很快； 但较大的空闲分区不被保留。,分区回收算法 如果释放区与临近的空闲区相连接，要将它们合并成较大的空闲区，否则空闲区将被分割得越来越小，最终导致不能利用。 上邻接合并 下邻接合并 上、下邻接合并 不邻接处理,例：某系统内存使用情况如下图，若采用首次适应算法分配内存，分别给出为某作业分配50k空间和回收作业4后的空闲分区链
7、,分配50k后,回收作业4后,初始时,4）可重定位分区分配 算法思想 在可变分区分配算法的基础上，采用动态重定位方式装入程序（数据）。当无足够大的分区供分配时，若总空闲存储容量够用，则将各分区中的内容向内存一端移动（紧凑），使另一端形成一个大的空闲分区，然后再分配。 算法流程（如下页图示）,与动态分区分配算法基本相同，差别仅在于增加了紧凑功能。,请求分配 u.size分区,检索空闲分区链(表),找到大于u.size 的可用区？,按动态分区方式 进行分配,修改有关的 数据结构,返回分区号 及首址,空闲分区总和 u.size?,进行紧凑形成连续 空闲区,修改有关数据结构,无法分配 返回,否,是,是
8、,否,(图4-10 动态重定位分区分配算法流程图),例：前例若要为作业10分配120k的存储空间，因无足够大分区（总空闲容量290k），则先进行合并处理。,合并后空闲分区链为：,此时，就可以为作业10分配空间,算法实现 为每个作业（分区）分配一个重定位寄存器，用以存放对 应分区首地址，以便实现动态地址转换；移动后，只需修 改重定位寄存器的值为新地址即可 优、缺点,可实现动态（可变）分区分配，又适时解决碎片问题 但移动内存需增加系统开销，增加辅助空间,5）伙伴系统,算法思想：将所有的空闲分区按照容量大小进行分类，而且分区大小均为2的K次幂，对每一类具有相同大小的所有空闲分区均设立一个空闲分区双向
9、链表。,分配过程：根据进程长度n找到能容纳它的最小空闲区链表，取下第一个分区进行分配。如果该分区容量比所需的要大，就将其进行平均分割，其中一个分区用于分配，另一个分区加入对应大小的空闲分区链中。如果分割后的分区仍比所需分区大的话，按前叙方法继续分割，直到满足要求为止。,特点：其分配和回收的时间性能取决于查找空闲分区的位置和 分割、合并空闲分区所花费的时间。,4.4 基本分页存储管理方式 1）算法思想和算法实现 算法思想 作业地址空间被分成大小相同的若干页（页面） 内存存储空间被分成大小与页相同的若干块（物理块） 将连续的页分配并存放到不连续的若干内存块中 建立页表，记录每一页对应的存储块的块号
10、,算法实现 确定分页的页面大小 建立辅助数据结构 作业代码装入方式,页表：每个作业（进程）一张表空闲块链表：记录所有未分配空闲块情况（供分配用）存储分块表：记录内存每一块的使用情况,太大：存在页内碎片太小：页表占用空间太多,采用动态重定位在执行时实现地址转换,2）地址变换过程和地址变换机构,地址的机构由两部分组成:P(页号)和D(页内偏移量)。,分页系统利用页表进行地址变换，由CPU中的内存管理单元 (MMU,Memory Management Unit)完成地址变换过程如下图所示:,分页存储管理逻辑地址转换成物理地址方法： 逻辑地址/页大小 取整页号 块号 逻辑地址/页大小 取余页内位移量
11、块号*页大小+页内位移量物理地址,查页表,地址变换实例：设一个3页长的进程具有页号0，1，2，其对应的物理块号则为2，3，8，如果每个页面的长度为1KB，则逻辑地址2500所对应的物理地址为多少？,解答： 2500/1024=2页号 2页对应物理块号8 2500%1024=452页内偏移 物理地址为：81024+452=8644,为了缩短页表查找时间，可将当前访问的页表项装入到地址变换机构中的特殊高速缓冲寄存器，称为联想存储器或称快表,3）改进的地址变换机构,4）内存的分配与回收 计算作业（进程）所需的页面数查是否有足够空闲块数的内存供分配 查空闲块链表，分配内存块分配页表空间，建立页表修改空
12、闲链表及空闲总块数等数据 根据页表，回收（释放）各内存块回收页表修改相关数据项,若 够,分配过程,回收过程,5）分页分配不足之处 碎片问题，虽然大部分的问题都解决了，但是每一个作业或者进程的最后一页基本都不能充分利用 分割分配并存放，使逻辑完整的模块物理上不完整，不利于内存信息（数据）共享,4.5 基本分段存储管理方式,1）算法思想 是根据程序的模块结构，把作业划分为大小不同段。每段有一个段名（通常用段号代替），段号(S)从0开始，每一段内也从0连续编址(偏移W) 采用可变分区分配算法为每一段分配分区空间，段与段之间不一定连续但段内地址是连续的 建立段表，记录每一段的段长及段在内存的起始地址,
13、将程序的地址空间划分为若干个段，物理内存的管理 采用动态分区，这些段不必连续,0,1,2,2）地址结构和地址变换过程 地址结构 地址变换机构,二维地址,例：以下是基本分段存储管理中的地址变换机构， 1）说明分段存储管理方式的地址变换过程； 2）若逻辑地址中的段号S=0，段内相对地址为500，给出地址变换后对应的物理地址值。,解答： 1）地址变换过程：取逻辑 地址中的段号查段表，从 而得到对应段在内存的起始地址，再用此起始地址与逻辑地址中的段内相对地址相加，从而获得对应的物理地址； 2）指定的逻辑地址经地址 变换结构变换后的物理地 址是：4596,3）段式管理的数据结构,4）改进的地址变换机构
14、增设一个关联寄存器，用于保存最近常用的段表项。一般情 况下段比页大，因而段表项的数目比页表数目少，其所需的 关联寄存器也相对较小，可以显著地减少存取数据的时间。,进程段表：描述组成进程地址空间的各段，可以是指向系统段表中表项的索引。每段有段基址(base address) 系统段表：系统内所有占用段 空闲段表：内存中所有空闲段，可以结合到系统段表中。内存分配算法可以采用最先适应算法、最佳适应算法和最坏适应算法。,5）分段分配特点,分段共享：可以按段为单位来进行共享 分段保护：可以针对不同类型的段采取不同的保护 动态链接：通过动态链接进行代码共享 动态增长 没有内碎片，外碎片要通过内存紧缩来消除
15、,采用离散分配，采用动态重定位实现地址转换 不同之处 分页分段 地址空间划分物理（大小固定） 逻辑（大小可变） 分配空间不连续的块不连续的分区 地址结构一维二维 地址变换块号与页内位段始地址与段内 移量拼接相对地址相加 共享性不利于共享利于共享,6）分页与分段存储管理的比较,可重入代码：不允许任何进程对其修改的共享代码 分页共享 每个共享进程的页表项中记录共享代码的所有物理块号 分段共享 每个进程的段表中记录共享段的物理地址,7）信息的共享,4.6 段页式存储管理方式,引入： 分页存储管理能有效地提高内存的利用率，而分段存储管理则能很好地满足用户需要。将两种存储管理方式“各取所长”后，则可以将
16、两者结合成一种新的存储管理方式 “段页式存储管理” 。 段页式存储管理既具有分段系统便于实现、分段可共享、易于保护、可动态链接等优点；又能像分页系统那样很好地解决内存的外碎片问题，以及为各个分段可不连续地分配内存等问题。,算法思想 作业地址空间先分段，每段再分页 内存存储空间按页的大小分块 为每段的若干页分配存储块空间，并分块存放 建立段表、页表记录作业段、页与内存块的对应信息 地址结构 地址结构由段号、段内页号和页内地址三部分组成,段页式存储管理的数据结构 段表：记录了每一段的页表起始地址和页表长度 页表：记录了每一个段所对应的逻辑页号与内存块号的对应关系，每一段有一个页表，而一个程序可能有多个页表 空闲内存页表：由于物理内存采用分页式的存储管理，所以它的结构同分页式存储管理 物理内存分配：同分页式存储管理,段表及其页表：,地址变换过程 在段页式存储管理中，
