《连续存储分配、页式存储管理》由会员分享，可在线阅读，更多相关《连续存储分配、页式存储管理（28页珍藏版）》请在金锄头文库上搜索。
1、第十一讲 连续存储分配、页式存储管理目的与要求：了解连续存储分配，掌握页式存储管理。 重点与难点：连续可变存储管理；页式存储管理。 作业：5，6，7，11,第五章 存储管理,研究作业或进程在主存的存放问题(以放的方法为线索）：放（placement）取（fetch）替换（replacement）,内存空间安排,5.1 连续空间分配 5.1.1单道连续分配,特点：任一时刻内存只有一道作业，该作业连续存放于内存中。,一、空间划分与保护,操作系统,用户程序,0,a,a+1,n,界地址寄存器,主存,A a?,cpu,true,false,地址A,终止程序运行,越界检查机构：用户程序每次执行访存指令，硬
2、件越界检查机构将访问的地址与界地址寄存器中的值比较。若越界，则终止其执行。,二、覆盖（overlap）,操作系统,固定区(4k),覆盖区(6k),覆盖区(10k),A(4k),E(10k),D(6k),C(4k),B(6k),F(8k),因内存小于作业的程序空间而引入覆盖。将用户空间划分成一个固定区和多个覆盖区。主程序放固定区，依次调用的子程序则放在同一个覆盖区。操作系统提供覆盖系统调用函数，由用户编程序时考虑调用。,基本思想：将处于等待状态(等I/O)或就绪(等CPU)状态的进程从主存换出到辅存，把将要执行的进程移入主存。,三、交换,交换要花费较长的时间。,I/O对于交换的要求:必须在系统空
3、间设立I/O缓冲区。,特点：任一时刻内存可有多道作业，每道作业连续存放于内存.,操作系统,U1,.,Un,5.1.2 多道固定划分法,一、空间划分及保护,将用户内存空间分成长度固定的若干块。,用户空间,1.上下界寄存器和地址检查机构。当作业被调度运行时，作业在内存中的上下界地址送上下界寄存器，每次执行访存指令时，地址检查机构作越界检查。作业程序要是绝对地址或静态可浮动的。,CPU,主存,下界寄存器,上界寄存器,True,True,地址A,F F,程序性异常,地址访问保护有两种方式：,2.基址寄存器、长度寄存器和动态地址转换机构。当作业被调度运行时，将作业所占内存基址及长度送基址、长度寄存器，每
4、次执行访存指令时，先看访问地址是否小于长度，然后+基址进行访存。用户程序代码是动态浮动的。,CPU,主存,基地址寄存器,长度寄存器,+,True,地址A,F,程序性异常,二、作业存储调度,OS,4k,6k,12k,OS,4k,6k,12k,.,7k,3k,4k,5k,.,3k,4k,1k,2k,.,5k,6k,.,7k,10k,11k,8k,多队列法,单队列法,三、存储碎片内部碎片：内存某存储区间大于其存放作业空间的部分。外部碎片：内存某存储区间容不下要运行的作业时。,一、管理方法,5.1.3 多道连续可变划分法,特点：多道、连续、但不固定划分内存。,系统设置一个空闲块队列，初始状态时队列中只
5、有一个连续的空闲块。作业到达后，以某种策略分配空间。作业撤离时，将释放的空间加入空闲队列。,举例：假设任一时间段内，内存中每一作业的运行时间片相等。,作业到来次序 所需存储量 运行时间,1 60 10,2 100 5,3 30 20,4 70 8,5 50 15,OS,0 40 256,J1,J2,J3,J4,J5,分配：分配策略包括首次满足法/最佳满足法/最大满足法，在找到合适的空闲块后，从其中将作业大小的空间分给作业，而剩余部分挂入空闲队列。 下面F是空闲块集合; size(k)为块k的大小; size(v)为用户所需空间。if 所有属于F的k，均有size(k)size(v),则失败。
6、否则按某一策略选出k，使得size(k)size(v). F = F k;,回收：当作业结束时，收回作业所占空间，将此块链入空闲队列。若空闲队列中原来有与此块的相邻块，则把这些块合并成一个大连续块。,（续分配） 4. if size(k)-size(v)基本单位，则将k分给用户。 5. 否则将k分成k1、k2，其中k1分给用户 size(k1)=size(v)， F = F + k2,紧致：通过移动作业位置可以将零散的空闲块连接成大块。要求作业动态可浮动。,Bitmap数组1,1,1,0,0,1,0,0,0,0,1,0,0,3,2,1,4,1 2,空闲队列头,二、可用空间管理除用队列表示可用空
7、闲块外,也可以用数组登记可用空闲块，数组项=用户空间总量/基本分配单位。,一、空间安排用户进程空间(地址)叫逻辑空间(地址)内存空间(地址)叫物理空间(地址)，用相同长度为单位对逻辑空间等分出的每个区域叫页，对物理空间等分出的区域叫页帧。,5.2 不连续空间分配 5.2.1页式管理,特点：作业(进程)分成页面，内存也划分成页面，将作业(进程)页面不连续地分布到内存页面。,回收：当进程结束时，系统回收它的所有物理页帧入空闲队列。二、动态地址转换机构因页式方法中逻辑地址与物理地址之间失去自然联系，故要通过页表，并由硬件动态地址转换机构将逻辑地址映射成物理地址才能正确访存。,分配：系统初始时，所有页
8、帧都在空闲队列中，当用户进程被创建时，系统按需要量从空闲队列获得相应量的页帧。,1,8,5,3,0,4,9,8,7,6,5,4,3,2,1,0,3,2,1,0,逻辑空间,物理空间,页表,(一)页表 页表放在系统空间的页表区，存放逻辑页与物理页帧的对应关系。PCB表中有指针指向页表。,页号,(二)地址结构分页逻辑地址 = P(页号).d(页内位移)分页物理地址 = f(页帧号).d(同上)P = 线性逻辑地址 / 页面大小；d = 线性逻辑地址 - p*页面大小。,4,3,2,1,0,页号,(三)页面大小的考虑 将页面大小取成2的k次幂(k是正整数),获取p和d的除、乘法只要通过位移实现. 页面
9、大小为2的k次幂的地址转换原理如下：,P d,页表始地,f,n k-1 0,f d,n k-1 0,+,页表,CPU有一个用于页号页帧号转换的联想存储器。将页表存入联想存储器的地址转换原理如下：,P d,n k-1 0,f d,n k-1 0,P2,f2,P1,f1,.,.,P,f,.,.,Pm,fm,(四)联想存储器,关键字 值,地址转换的一般过程 (联想存储器可以看成是页表的cache),P d,n k-1 0,f d,n k-1 0,P2,f2,P1,f1,.,.,P,f,.,.,Pm,fm,f,页表始地,+,页表,联想存储器,在进程被调度占用cpu时，将进程页表始址装入页表始地址寄存器
10、，同时作废掉联想存储器中的原内容，用新的页表项替换。,命中率：选用8-12项组成的联想存储器，并采用适当的替换策略，在联想存储器中匹配成功的可能性可达80-90%。,等效访问时间：设访存时间为750ns，搜索联想存储器的时间为50ns，命中率为80%，则（这里假设先查联想存储器再查页表）：80% *（50750）+ 20% *（50750+750）= 950ns,三、可用空间管理可用bitmap数组或空闲页帧链来管理可用页帧。四、共享与保护通过页表可以使几个逻辑空间指向同一个物理空间，实现程序共享。,举例：,EDIT1,EDIT2,EDIT3,DATA1,EDIT1,EDIT2,EDIT3,D
11、ATA2,EDIT1,EDIT2,EDIT3,DATA3,3,4,6,1,3,4,6,7,3,4,6,10,OS,DATA1,EDIT1,0 1 2 3 4 5 6 7 8 9 10 11,EDIT2,EDIT3,DATA2,DATA3,P1 P2 P3,页表,存储保护：越界保护：设置页表长度寄存器，查页表前，先检查页号是否越界。操作访问保护：在每个页表项中增设一存储保护域，用于说明对该页的访问权限，每一个对该页存储的访问都首先要比照是否满足该页访问权限的说明，满足则访问，否则报错。,举例：设为每一页表项增加三位，R位表示读权限，W位表示写权限，E位表示执行权限。R W E0 0 0 不可进行任何操作0 0 1 可以执行,不可以读写0 1 0 只可以写0 1 11 0 01 0 11 1 01 1 1,
