离散分配.ppt
《离散分配.ppt》由会员分享,可在线阅读,更多相关《离散分配.ppt(83页珍藏版)》请在三一文库上搜索。
1、4.4 基本分页存储管理方式,连续分配存储管理方式产生的问题 在分区存储管理中,要求把进程放在一个连续的存储区中,因而会产生许多碎片。 碎片问题的解决方法 (1)拼接/紧凑技术-代价较高。 (2)离散分配方式-允许将作业/进程离散放到多个不相邻接的分区中,就可以避免拼接。基于这一思想产生了以下的离散分配方式: 分页式存储管理:离散分配的基本单位是页 分段式存储管理:离散分配的基本单位是段 段页式存储管理:离散分配的基本单位是段、页,4.4 基本分页存储管理方式,在分页存储管理方式中,如不具备页面对换功能,不支持虚拟存储器功能,在调度作业运行时,必须将它的所有页面一次调入内存,若内存没有足够的块
2、,则作业等待,这种存储管理方式称为纯分页或基本分页存储管理方式 。 基本思想 页表 地址结构 地址变换机构 多级页表 页的共享与保护,一、基本思想,空间划分 (1)将一个用户进程的地址空间(逻辑)划分成若干个大小相等的区域,称为页或页面,并为各页从0开始编号。 (2)内存空间也分成若干个与页大小相等的区域,称为(存储、物理)块或页框(frame),同样从0开始编号。 内存分配 在为进程分配内存时,以块为单位,将进程中若干页装入到多个不相邻的块中,最后一页常装不满一块而出现页内碎片。,注:需要CPU的硬件支持(地址变换机构)。,一、基本思想,一、基本思想,页面大小 若页面较小: 减少页内碎片和内
3、存碎片的总空间,有利于提高内存利用率。每个进程页面数增多,从而使页表长增加,占用内存就较大。页面换进换出速度将降低。 若页面较大: 每个进程页面数减少,页表长度减少,占用内存就较小。页面换进换出速度将提高。但会增加页内碎片不利于提高内存利用率。 页面大小-选择适中,通常为2的幂,一般在512B-8KB之间。,二、页表,为了便于在内存找到进程的每个页面所对应块,系统为每个进程建立一张页面映象,简称页表,如图。 记录了页面在内存中对应的块号 页表一般存放在内存中 页表的基址及长度在页表寄存器中 访问一个字节的数据/指令需访问内存2次(页表一次,内存一次),所以出现内存访问速度降低的问题。,三、地址
4、结构,分页存储管理系统中的地址结构(逻辑): 地址长为32位,其中0-11位为页内地址,即每页的大小为212=4KB 12-31位为页号,地址空间最多允许有220 =1M页。 物理地址: 地址长为22位,其中0-11位为块内地址,即每块的大小为212=4KB,与页相等 12-21位为块号,内存地址空间最多允许有210 =1K块。,三、地址结构 例题,设有一页式存储管理系统,向用户提供的逻辑地址空间最大为16页,每页2048B,内存总共有8个存储块,试问逻辑地址至少应为多少位?内存空间有多大? 解: (1)页式存储管理系统的逻辑地址为: 其中页内地址表示每页的大小即 2048B=2*1024B=
5、211B,所以页内地址为11位。 其中页号表最多允许的页数即 16页=24页,所以页号为4位。 故逻辑地址至少应为15位。,三、地址结构 例题,设有一页式存储管理系统,向用户提供的逻辑地址空间最大为16页,每页2048B,内存总共有8个存储块,试问逻辑地址至少应为多少位?内存空间有多大? 解: (2)物理地址为: 其中块内地址表每块的大小与页大小相等,所以块内地址也为11位。 其中块号表内存空间最多允许的块数即 8块=23块,所以块号为3位。 故内存空间至少应为14位,即214 =16KB,三、地址结构 例题,设一个逻辑地址空间中的地址A,页面大小为L。A对应的页号p和页内地址w是多少? 解:
6、 (1) 先看A应该在哪一页中:p=int(A/L) (2) 在看A在页内的位置:w=A mod L 假设A=2170,页面大小为1KB,则A所属页号为2,页内地址为122。,四、地址变换机构,为了能将用户地址空间中的逻辑地址变换为内存空间中的物理地址,在系统中必须设置地址变换机构。分基本的地址变换机构和具有快表的地址变换机构。 地址变换机构的基本任务 -实现逻辑地址向物理地址的转换(页号-块号)。 地址变换借助页表来完成。,四、地址变换机构,分页系统的基本地址变换机构如图所示:,四、地址变换 例题,例1: 若在一分页存储管理系统中,某作业的页表如表所示,已知页面大小为1024B,试将逻辑地址
7、1011,2148,5012转化为相应的物理地址?画出其地址转换图。 解:由题知逻辑地址为: 物理地址为: (1)逻辑地址1011(十进制)的二进制表示为 00 1111110011 由此可知逻辑地址1011的页号0,查页表知该页放在第2物理块中,其物理地址的二进制表示为 010 1111110011 所以逻辑地址1011对应的物理地址为0BF3H.其地址转换图如后所示。,地址变换过程,+,页表长度,页表始址,3F3,0,页表寄存器,逻辑地址1011(03F3H),物理地址0BF3H,越界中断,页合法,三、地址变换例题,三、地址变换例题,例1: 若在一分页存储管理系统中,某作业的页表如表所示,
8、已知页面大小为1024B,试将逻辑地址1011,2148,5012转化为相应的物理地址?画出其地址转换图。 解:由题知逻辑地址为: 物理地址为: (2)逻辑地址2148时,2148/1024=2 2148 % 1024=100 由此可知逻辑地址2148的页号为2,查页表知该页放在第1物理块中,其物理地址为 1*1024+100=1124 001 0001100100 所以逻辑地址2148对应的物理地址为08C4H。其地址转换图略。,三、地址变换例题,例1: 若在一分页存储管理系统中,某作业的页表如表所示,已知页面大小为1024B,试将逻辑地址1011,2148,5012转化为相应的物理地址?画
9、出其地址转换图。 解:由题知逻辑地址为: 物理地址为: (3)逻辑地址5012时,5012/1024=4 查页表知该页为不合法页,则产生越界中断。,例2 在一个页式存储管理系统中,页表内容如下所示,若页的大小为4K,则地址转换机构将逻辑地址0转换成的物理地址为多少? 页号 块号 0 2 1 1 2 6 3 3 4 7,三、地址变换例题,解:页的大小为4k=212,则页内地址和块内地址都是12位。由题目得内存中最多允许的块数是23,所以块号为3位。 逻辑地址0在第0页,它对应的块号是2,则它的物理地址为: 010 000000000000,四、地址变换机构 -具有快表的地址变换机构,基本的地址变
10、换机构存在的问题 地址变换速度降低(CPU访问一个字节的数据需两次访问内存) 目的:为提高地址变换速度 快表 为一种特殊高速缓冲存储器。 内容-为页表中的一部分或全部 CPU产生的逻辑地址的页首先在快表中寻找,若找到(命中),就找出其对应的物理块;若未找到(未命中),再到页表中找其对应的物理块,并将之复制到快表。 若快表中内容满,则按某种算法淘汰某些页。,有效访问内存的时间 T=PTLB*(TTLB+TM)+ (1-PTLB )*( TTLB + 2TM ) 其中,PTLB为快表的命中率,TTLB为快表的访问时间, TM为内存的访问时间,具有快表的地址变换机构,例: 有一页式系统,其页表存放在
11、主存中。 (1)如果对主存的一次存取需要100ns,试问实现一次页面访问的存取时间是多少? (2)如果系统加有快表,对快表的一次存取需要20ns,若平均命中率为85%,试问此时的存取时间为多少? 解: (1)页表放主存中,则实现一次页面访问需2次访问主存,一次是访问页表,确定所存取页面的物理块,从而得到其物理地址,一次根据物理地址存取页面数据。所以实现一次页面访问的存取时间为: 100ns*2=200ns (2)系统加有快表,则实现一次页面访问的存取时间为: 0.85*(20ns+100ns)+(1-0.85)*(20ns+2*100ns)=135ns,有效内存访问时间T例题,问题 若逻辑地址
12、空间很大,则划分的页就很多,页表就很大,其占用的存储空间(要求连续)就大,实现较难。 解决问题的方法 1、只将当前需用的部分页表项调入内存,其余的需用时再调入。 2、多级页表,五、多级页表,1.两级页表 (1)基本思想 将页表再进行分页,并离散地将各个页表页面存放在不同的物理块中,同时也再建立一张页表(外层页表)用以记录页表页面对应的物理块号。,说明: 页表中每个页表项中存放的是进程分页后某页在内存中的物理块号。 外层页表中每个页表项中存放的是某页表分页后每页在内存中的首地址。 两级页表中个,CPU要存取数据是需3次访问内存。,(2)逻辑地址 (3)地址转换,1.两级页表,将外层页表再进行分页
13、,也将各外层页表页面离散地存放在不同的物理块中,再利用第2级的外层页表来记录它们之间的对应的关系。 逻辑地址:,2.多级页表,4.5 基本分段存储管理方式,分页存储管理方式提高内存利用率,系统的需要 分段存储管理方式方便用户操作,用户的需要 引入: 1) 方便编程 2) 信息共享 3) 信息保护 4) 动态增长 5) 动态链接,4.5 基本分段存储管理方式,基本原理 段表 地址变换机构 分页和分段的主要区别 信息共享 段页式存储管理方式,一、基本原理,在分段存储管理方式中,将逻辑空间划分为若干个段,每个段定义了一组逻辑信息。 (1)段号:每段的名字 (2)段内地址:从0开始,一段连续的地址空间
14、 (3)段长度:由各自的逻辑信息组的长度决定,各段 长度不等 (4)分段地址的结构:整个作业的地址空间由于是分成多个段,因而是二维的,亦即,其逻辑地址由段号(段名)和段内地址所组成。,二、段表,分段式存储管理系统中,则是为每个分段分配一个连续的分区,而进程中的各个段可以离散地移入内存中不同的分区中。 从物理内存中找出每个逻辑段所对应的位置,在系统中为每个进程建立一张段映射表,简称“段表”。 (1)每个段在表中占有一个表项,其中记录了该段在内存中的起始地址(又称为“基址”)和段的长度; (2)段表常驻内存,三、地址变换机构,分段式存储管理系统中,为了实现从进程的逻辑地址到物理地址的变换功能,设置
15、了段表寄存器,用于存放段表始址和段表长度TL。,三、地址变换机构,练习:有下列段表,请将逻辑地址(0,137), (1,4000), (2,3600), (5,230)转换成物理地址。,四、分页和分段的主要区别,两者都采用离散分配方式,且都要通过地址映射机构来实现地址变换。但在概念上两者完全不同,主要表现在下述三个方面。 (1) 页是信息的物理单位 段则是信息的逻辑单位 (2) 页的大小固定且由系统决定 段的长度却不固定,根据信息的性质来划分。 (3) 分页的作业地址空间是一维的,即单一的线性地址空间,程序员只需利用一个记忆符,即可表示一个地址; 分段的作业地址空间则是二维的,程序员在标识一个
16、地址时,既需给出段名,又需给出段内地址。,五、信息共享,分段系统的一个突出优点,是易于实现段的共享,即允许若干个进程共享一个或多个分段,且对段的保护也十分简单易行。 例如,有一个多用户系统,可同时接纳40个用户,他们都执行一个文本编辑程序(Text Editor)。已知文本编辑程序有160 KB的代码和另外各用户所需40 KB的数据区。 无论是在分页系统还是在分段系统中,该代码都能被共享,在内存中只需保留一份文本编辑程序的副本,此时所需的内存空间仅为1760 KB(4040+160),而不是8000 KB。,假设每页的大小为4k,则分页系统的共享如图:,内存空间,进程1,段表,段长 基址,段表
17、,段长 基址,进程2,80 240 380,分段系统的共享如图:,六、段页式存储管理方式,1、基本原理 段页式系统的基本原理,是分段和分页原理的结合,即先将用户程序分成若干个段,再把每个段分成若干个页,并为每一个段赋予一个段名。,六、段页式存储管理方式,2、地址转换结构,4.6 虚拟存储器的基本概念,常规存储管理方式的共同点 要求一个作业全部装入内存后方能运行。 问题: (1)有的作业很大,所需内存空间大于内存总容量,使作业无法运行。 (2)有大量作业要求运行,但内存容量不足以容纳下所有作业,只能让一部分先运行,其它在外存等待。 解决方法 (1)*增加内存容量。 (2)从逻辑上扩充内存容量 -
18、对换 -虚拟存储器,一、虚拟存储器的引入,1.常规存储器管理方式的特征 (1)一次性:作业在运行前需一次性地全部装入内存。 (2)驻留性:作业装入内存后,便一直驻留内存,直至作业运行结束。 2.局部性原理 指程序在执行时呈现出局部性规律,即在一较短时间内,程序的执行仅限于某个部分,相应地,它所访问的存储空间也局限于某个区域。 局部性又表现为时间局部性(由于大量的循环操作,某指令或数据被访问后,则不久可能会被再次访问)和空间局部性(如顺序执行,指程序在一段时间内访问的地址,可能集中在一定的范围之内)。,3.虚拟存储器的概念,基于局部性原理,程序在运行之前,没有必要全部装入内存,仅须将当前要运行的
19、页(段)装入内存即可。 运行时,如访问的页(段)在内存中,则继续执行,如访问的页未在内存中(缺页或缺段),则利用OS的请求调页(段)功能,将该页(段)调入内存。 如内存已满,则利用OS的页(段)置换功能,按某种置换算法将内存中的某页(段)调至外存,从而调入需访问的页。,一、虚拟存储器的引入,3.虚拟存储器的概念,虚拟存储器是指仅把作业的一部分装入内存便可运行作业的存储管理系统,它具有请求调入功能和置换功能,能从逻辑上对内存容量进行扩充的一种存储器系统。 其逻辑容量由外存容量和内存容量之和决定,其运行速度接近于内存,成本接近于外存。,一、虚拟存储器的引入,二、虚拟存储器的实现方法 建立在离散分配
20、的存储管理方式的基础上,1、分页请求系统 在分页系统的基础上,增加了请求调页功能、页面置换功能所形成的页式虚拟存储器系统。 它允许只装入若干页的用户程序和数据,便可启动运行,以后在硬件支持下通过调页功能和置换页功能,陆续将要运行的页面调入内存,同时把暂不运行的页面换到外存上,置换时以页面为单位。 系统须设置相应的硬件支持和软件: (1)硬件支持:请求分页的页表机制、缺页中断机构和地址变换机构。 (2)软件:请求调页功能和页置换功能的软件。,二、虚拟存储器的实现方法,2、分段请求系统 在分段系统的基础上,增加了请求调段功能及分段置换功能,所形成的段式虚拟存储器系统。 它允许只装入若干段的用户程序
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散 分配
链接地址:https://www.31doc.com/p-2599819.html