chapter5-2

nullnull第五章    存储器管理5.4 静态页式存储管理 5.5 静态段式存储管理 5.6 段页式存储管理 5.7 虚拟存储器 5.8 请求页式存储管理方式 null第五章    存储器管理 离散（非连续）分配方式之 5.4 静态页式存储管理 5.4.1 页式存储管理的引入 5.4.1 页式存储管理的引入 在动态分区的存储空间中，存在“零头碎片”问题。尽管采用“紧凑”技术可以解决这个问题，但要为移动大量内存空间花费不少的处理机时间，代价较高。 进程的大小受分区大小或内存可用空间的限制。 分区管理不利于程序段和数据的共享。 null5.4.2 页面与页 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 1.页面和物理块 分页存储管理，是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号。 相应地，也把内存空间分成与页面相同大小的若干个存储块，称为(物理)块或页框(frame)，在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。 * 页面大小：页面的大小应选择得适中，且页面大小 应是2的幂，通常为512 B~8 KB 2.页表 2.页表 页表是存储在内存的一种专用数据结构，它列出了作业程序的逻辑地址与其在主存中的物理地址间的映射关系。 一个页表中包含若干个表目，每个表目包含两项数据：用户程序中的逻辑页号，及该页在内存存储的物理块号。 分页管理中页面与物理块的对应关系 分页管理中页面与物理块的对应关系 块号离散地存储null3.地址结构 页式管理中的逻辑地址结构： 3112110 对某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按下式求得： P＝A整除L的商 d＝A整除L的余数 null5.4.3 地址变换机构 基本的地址变换机构 (将用户地址空间的逻辑地址变换为内存空间的物理地址) 图 4-4-2分页系统的地址变换机构 进程执行前，将页表始址和页表长度从进程PCB中读入页表寄存器 2. 地址变换过程 2. 地址变换过程 例如程序编译后的指令 LOAD A,2500 的地址变换过程如下：逻辑地址页表项 地址变换的详细过程 地址变换的详细过程 1.把虚拟地址2500转换成页号P=2，位移量W=452； 2.如果页号2大于页表大小，则中断；否则继续； 3.页号2与页表起址1000运算（1000+2*20，设每个页表项长度为20）得到该表项在页表的地址为1040； 4.访问目标页表项，得到页号2对应的物理块号是8； 5.根据页表项的“存取控制”判断该指令是否被允许访问内存，如果不允许，则中断；否则继续； 6.块号8与位移量452运算（8*1024+452=9644，1024为页面大小）得到物理地址9644； 7.把内存地址9644单元中一个字节的数据写入寄存器A。3. 页式管理所用的数据结构3. 页式管理所用的数据结构1)页表：系统为每个进程建立一个页表，页表常驻内存，属于进程的现场信息，在进程未执行时，页表始址和页表长度存放在该进程的PCB中。 2)页表寄存器：存放页表始址和长度 3)位示图——内存空块管理（对比分区管理中用到的空闲区表，空闲区链等结构）null0310/10/10/10/10/1017……空闲块数……空块管理——位示图 内存的分配 内存的分配 计算一个作业所需要的总块数N 查位示图，看看是否还有N个空闲块 如果有足够的空闲块，则页表长度设为N，填入PCB中；在内存中申请页表区，并把页表始址填入PCB 依次分配N个空闲块，将块号和页号填入页表 修改位示图 4.快表 4.快表 思考：在基本页式管理中，CPU每访问一个数据时，需要几次访问内存？ 为了解决查页表导致效率降低的问题，在地址变换机构中增加一组硬件寄存器，存放当前访问过的页的页表项。 　　 每次访问主存时，首先查找快表，若找到所需的页表项，则快速形成物理地址。否则还需访问内存中的页表后才能得到物理地址，同时修改快表（把本次方位的页表项写入快表）。如果 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 得当，快表的命中率可以很高。 具有快表的地址变换机构具有快表的地址变换机构图 4-4-3 具有快表的地址变换机构练习练习 1.假设某系统内存中地址由低到高排列有两个空闲区：F1=110K，F2=60K； 现有三个作业A，B，C，其中A＝20K，B＝80K，C＝50K； 试问： a.对于作业序列A－B－C，采用哪种分区分配算法（最佳适应、最坏适应、首次适应）的内存利用率最高？ b.若作业序列是C－A－B，结果又如何？ 课后作业课后作业 2.地址重定位的方法有哪几类？简要对它们进行说明。 3.一个由8个页面，每页1024个字节组成的逻辑空间，把它装入有32个物理块的存储器中，问： a.逻辑地址需要多少位二进制表示？ b.物理地址需要多少位二进制表示？ 4.某虚拟存储器的用户空间共有32个页面，每页1K，主存16K。假定某时刻系统为用户的第0、1、2、3页分配的物理块号为5、10、4、7。而该用户作业的长度为6页，试将十六进制的虚拟地址0A5C、093C 、103C、1A5C转换成物理地址。 null第四章    存储器管理 5.5 段式存储管理 5.5.1 分段式存储管理的引入 5.5.1 分段式存储管理的引入 在分区式和分页式存储系统中，作业的地址空间结构都是线性的，即把源程序中的主程序、子程序和数据区等按线性空间的一维地址顺序排列。这破坏了程序内部天然的逻辑结构（逻辑页没有完整的物理意义，不能与用户给定的程序名和数据块名对应起来），造成共享、保护的困难。 引入分段存储管理方式， 主要是为了： 1) 方便编程 2) 信息共享 3) 信息保护 4) 动态增长 5) 动态链接 null0116Nnull5.5.2 分段系统的基本原理 1. 基本思想 把用户作业/程序按内容或过程（函数）划分成若干个段，每段有段名（通常用段号代替），并包含了一组有逻辑意义的信息。 每个段都从0开始编址，并拥有一段连续的地址 空间，段长由相对应的逻辑信息组的长度决定。因此，整个作业的地址空间构成了一个二维线性虚拟空间。 段式存储管理程序以段为单位分配内存，然后通过地址变换机构把由段号和段内地址组成的虚拟地址转换成实际的内存物理地址。null2. 地址结构 31 16 15 0如一个32位的逻辑地址具有以下结构：3. 段表3. 段表 系统为每个分段分配一个连续的内存空间，进程中的各个段可以离散地分布在内存不同区域。 为每个进程建立一张段映射表，存储在内存，其中每个表项 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 了该段在内存中的起始地址和段长。null 分段管理中作业与段表、内存空间的关系4. 地址变换机构 系统设置一对寄存器： 段表始址寄存器 用于保存正在运行的进程的段表始址 段表长度寄存器 用于保存正在运行进程的段表的长度（例如上图的段表长度为5）4. 地址变换机构 null图 4-5-2 段式存储管理中的地址变换过程思考：段式存储管理中，CPU存取一次数据，需要几次访问内存？图 4-5-3 基于快表的地址变换及存储保护机制 Cl Cb+段号S 段内地址d比较比较b + d 段表S>= Cl快表物理地址段表始址寄存器段表长度寄存器逻辑地址lb...Slb地址越界d>=ld>=l图 4-5-3 基于快表的地址变换及存储保护机制地址越界地址越界比较null5. 分页和分段的主要区别 页是信息的物理单位，分页仅仅是为系统消除碎片等管理问题的需要，而不是用户的需要； 段则是信息的逻辑单位，能更好地满足用户需要。 (2) 页的大小固定且由系统决定， 而段的长度却不固定，由用户程序本身的逻辑决定。 (3) 分页的作业地址空间是一维的，即单一的线性地址空间； 而分段的作业地址空间则是二维的。null第四章    存储器管理 5.6 段页式存储管理 1.基本原理 1.基本原理 将分页和分段原理结合： 将用户程序分成若干个段，每段赋予一个段名； 再把每个段分成若干个页（页面大小固定）； 逻辑地址结构由： 段号、段内页号和页内地址组成（P123图4-20） 2.地址变换机构 2.地址变换机构（P124图4-21） 段表寄存器：存放段表始址和段长； 段表（记录每一段的页表始址和页表长度）： 段号，控制态，页表大小，页表始址 页表（记录每个段内的各逻辑页号与内存块号的对应关系）： 页号，控制态，物理块号。 null作业的地址空间和地址结构图（a）显示： 系统中的一个作业的地址空间结构页面尺寸为４Ｋ字节， 该作业有三个分段，第一段为15K字节，占4页，最后一 页只有1K未用；其它段同理。未足一页大小的补为一页。地址结构如图（b）所示3.地址映射过程3.地址映射过程 地址映射过程（续） 地址映射过程（续）从控制寄存器读取段表始址，找到段表； 段号＋段表始址 得到要访问的段表项的地址； 从段表项中读取页表始址，找到页表； 页号＋页表始址 得到页表项地址； 从页表项中读取物理块号； 物理块号＋页内位移量 得到物理地址。 上述的地址变换至少要访问主存三次，这将使执行程序的速度大大降低。为了解决上述问题，可以采取前边讲过的“快表”技术。null第四章    存储器管理 5.7 虚拟存储器1.问题的提出1.问题的提出 前述讨论的几种存储管理方式，都要求将一个作业的 全部内容装入内存后才能运行，这可能导致出现两种 情况： 1）有的作业很大，其要求的内存空间超过了内存总容量，作业将不能被装入执行； 2）有大量作业要求运行，但由于内存容量不足以容纳所有作业，只能将少数作业装入先运行，其余作业留在外存等待。 于是提出了从逻辑上扩充内存的方法——虚拟存储器 技术。 null 在一个短的时间内，程序的执行往往局限于某个部分，相应地，它所访问的存储空间也局限于某个区域。 具体表现在两个方面： 时间局部性：一条指令被执行了，则在不久的将来它可能再被执行；如果某数据被访问过，则不久后该数据可能再次被访问。 空间局部性：若某一存储单元被访问了，则不久以后，与该存储单元相邻的单元可能被访问，即程序在一段时间内访问的地址可能集中在一定的范围区间内。2.局部性原理3.虚拟存储技术3.虚拟存储技术基本思想：在逻辑上扩充内存容量，使得作业所 包含的程序、数据、堆栈的大小可以超过内存物 理容量。 实现：操作系统在离散分配的存储管理的基础 上，根据局部性原理，仅把程序当前要访问的 部分页面或段装入内存，而其余部分则暂留在磁 盘上。当程序访问发现需要的页（段）尚未装入 内存时，才通过请求调入操作，将它们从外存调 入内存。 虚拟存储器 虚拟存储器 指的是: 具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。 虚拟存储器就是将内外存统一管理的一个虚拟地址空间。 4.虚存的容量 4.虚存的容量 一个虚拟存储器的最大容量是由计算机的地址结构确定的。如：若CPU的有效地址长度为32位，则程序可以寻址范围是0～(232)-1 ，即虚存容量为 4GB。 虚拟存储器的容量与主存的实际大小没有直接的关系，而是由主存与辅存的容量之和所确定。null第四章    存储器管理 5.8 请求页式存储管理 一. 请求式分页存储管理 一. 请求式分页存储管理 也称虚拟页式存储管理，即在基本分页存储管理基础上，增加了请求调页功能和页面置换功能。 原理：请求式分页管理系统在进程开始运行之前，不是装入全部页面，而是装入少量即将访问的页面，之后随着进程的执行，发生了缺页时再动态装入其余页面；当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰当前内存中的某个页面，以便腾出空间装入需要的新页面。1.需要解决的问题1.需要解决的问题系统需要解决下面三个问题： 系统如何获知进程当前所需页面不在主存。 当发现缺页时，如何把所缺页面调入主存。 当需要发生页面置换时，根据什么策略选择欲淘汰的页面。2.页表的扩充2.页表的扩充 状态位：表示该页是否在内存 访问位：表示该页最近被访问的次数（可以根据访问位来决定淘汰哪页） 修改位：表示此页在调入内存后是否被修改过 外存地址：指出该页在外存的地址，供调入和数据写回时使用 3.缺页中断（Page Fault） 3.缺页中断（Page Fault）在地址映射过程中，在页表中发现所要访问的页不在内存，则产生缺页中断。操作系统接到此中断信号后，就调出缺页中断处理程序，根据页表中给出的外存地址，将该页调入内存，使作业继续运行下去。 如果内存中有空闲块，则分配一页，将新调入页装入内存，并修改页表中相应页表项目的驻留位及相应的内存块号。 若此时内存中没有空闲块，则要淘汰某页，若该页在内存期间被修改过，则要将其写回外存。 4.地址变换过程 4.地址变换过程 二.页面置换算法 二.页面置换算法 一个好的页面置换算法，应具有较低的页面 更换频率。 最佳置换算法 先进先出置换算法 最近最久未用置换算法 1.最佳置换算法 1.最佳置换算法 由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。null 假定系统为某进程分配了三个物理块， 并考虑有以下的页面号访问序列： 7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1 解：进程运行时，先将7、0、1三个页面装入内存。以后，当进程要访问页面2时，将会产生缺页中断。此时OS根据最佳置换算法，将选择页面7予以淘汰。 2.先进先出(FIFO)页面置换算法 2.先进先出(FIFO)页面置换算法 利用FIFO置换算法时的置换图置换时，选择最先进入内存的页，即在内存中驻留时间最长的页并淘汰之。null 3.最近最久未使用(LRU)置换算法 LRU页面置换算法的置换图 根据页面调入内存后的使用情况进行决策，选择最后一次访问时间距离当前时间最长的页并淘汰之。即淘汰未使用的时间最长的页。 实现代价很高（时间戳或硬件方法）影响缺页次数的因素:影响缺页次数的因素:(1) 分配给进程的物理页面数 (2) 页面本身的大小 (3) 程序的编制方法 (4) 页面淘汰算法三.性能问题抖动现象抖动（颠簸）: 一个进程在执行过程中缺页率过高，造成页面在内存与外存之间频繁调度，以至于调度页面所需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致系统崩溃。这种现象称为抖动或颠簸。 原因： 页面淘汰算法不合理 分配给进程的物理页面数太少抖动现象 工作集（Working Set）模型 工作集（Working Set）模型 试验表明，任何程序在局部性装入时，都有一个临界值的要求（如下图）。 该临界值被称为工作集。当内存分配小于工作集时，内外存 之间页面交换的频率将会急剧增加；而内存分配大于工作集 时，即使再增加内存分配也不能显著减少交换次数。null