第十一讲 连续存储分配、页式存储管理目的与要求了解连续存储

1、第十一讲第十一讲 连续存储分配、页式存储管理连续存储分配、页式存储管理目的与要求：目的与要求：了解连续存储分配，掌握页了解连续存储分配，掌握页式存储管理。式存储管理。重点与难点：重点与难点：连续可变存储管理，页式存连续可变存储管理，页式存储管理。储管理。作业：作业：5，6，7，10。第5章 存储管理研究三方面的问题：研究三方面的问题： 取（取（fetchfetch） 放（放（placementplacement） 替换（替换（replacementreplacement）请调、预调请调、预调连续、非连续连续、非连续内存空间安排内存空间安排5.1 连续空间分配5.1.1 单道连续分配特点：任一时

2、刻内存只有一道作业，该任一时刻内存只有一道作业，该作业连续存放于内存中。作业连续存放于内存中。一、管理方法操作系统操作系统用户程序用户程序0a aa+1a+1n n界地址寄存器界地址寄存器界地址寄存器界地址寄存器主存主存A Aa acpucputruetruefalsefalse地址地址A A终止程序运行终止程序运行越界检查机构：用户程序每访问一次主存，用户程序每访问一次主存，越界检查机构将访问的地址与界地址寄存越界检查机构将访问的地址与界地址寄存器中的值比较。若越界，则终止其执行。器中的值比较。若越界，则终止其执行。二、覆盖（overlap） 操作系统操作系统固定区固定区(4k)(4k)覆盖

3、区覆盖区(6k)(6k)覆盖区覆盖区(10k)(10k)A(4k)A(4k)E(10k)E(10k)D(6k)D(6k)C(4k)C(4k)B(6k)B(6k)F(8k)F(8k) 因内存小于作业的程序空间而引入覆盖，因内存小于作业的程序空间而引入覆盖，将用户空间划分成一个固定区和多个覆盖区。将用户空间划分成一个固定区和多个覆盖区。主程序放固定区，依次调用的子程序则放在主程序放固定区，依次调用的子程序则放在同一个覆盖区。操作系统提供覆盖系统调用同一个覆盖区。操作系统提供覆盖系统调用函数，函数，由用户编程序时考虑调用。由用户编程序时考虑调用。基本思想：将处于等待状态将处于等待状态( (等等I/O

4、)I/O)或就或就绪绪( (等等CPU)CPU)状态的进程从主存换出到辅存，状态的进程从主存换出到辅存，把将要执行的进程移入主存。把将要执行的进程移入主存。三、交换交换要花费较长的时间。交换要花费较长的时间。申请空间申请空间的系统调用，用于动态申请空间。的系统调用，用于动态申请空间。I/OI/O缓冲区对于交换的影响。缓冲区对于交换的影响。特点：任一时刻内存可有多道作业，每道任一时刻内存可有多道作业，每道作业连续存放于内存作业连续存放于内存. .操作系统操作系统U1U1.U Un n5.1.2 多道固定划分法一、管理方法 将用户内存将用户内存空间分成长度空间分成长度固定的若干块固定的若干块。用户

5、空间用户空间 1.上下界寄存器和地址检查机构。当当作业被调度运行时，作业在内存中的上下作业被调度运行时，作业在内存中的上下界地址送上下界寄存器，每次内存访问时，界地址送上下界寄存器，每次内存访问时，地址检查机构作越界检查。作业程序须是地址检查机构作越界检查。作业程序须是绝对地址或静态可浮动的。绝对地址或静态可浮动的。CPUCPU主存主存下界寄存器下界寄存器上界寄存器上界寄存器 TrueTrueTrueTrue地址地址A Afalse false false false程序性中断程序性中断地址访问保护有两种方式： 2.基址寄存器、长度寄存器和动态地址转换机构。当作业被调度运行时，将作当作业被调度

6、运行时，将作业所占内存基址及长度送基址、长度寄存业所占内存基址及长度送基址、长度寄存器，每次内存访问时，先看访问地址是否器，每次内存访问时，先看访问地址是否小于长度，然后小于长度，然后+ +基址进行访存。用户程基址进行访存。用户程序代码是动态浮动的。序代码是动态浮动的。CPUCPU主存主存基地址寄存器基地址寄存器长度寄存器长度寄存器 + +TrueTrue地址地址A Afalse false 程序性中断程序性中断二、作业调度OS4k6k12kOS4k6k12k.7k3k4k5k.3k4k1k2k.5k6k.7k10k11k8k多队列法多队列法单队列法单队列法三、存储碎片 内部碎片：内部碎片：内

7、存某存储区间大于其存放作内存某存储区间大于其存放作 业空间的部分。业空间的部分。 外部碎片：外部碎片：内存某存储区间容不下要运行内存某存储区间容不下要运行 的作业时。的作业时。OS12KB4KB3KB内部碎片内部碎片OSOS4KB4KB6KB6KB12KB12KB作业长度：作业长度：5KB5KB，8KB8KB，12KB12KB外部碎片外部碎片 一、管理方法5.1.3 多道连续可变划分法特点：多道、连续、但不固定划分内存。多道、连续、但不固定划分内存。 系统设置一个空闲块队列，初始状态系统设置一个空闲块队列，初始状态时队列中只有一个连续的空闲块。作业时队列中只有一个连续的空闲块。作业到达后，以某

8、种策略分配空间。作业撤到达后，以某种策略分配空间。作业撤离时，将释放的空间加入空闲队列。离时，将释放的空间加入空闲队列。举例：假设任一时间段内，内存中每一作举例：假设任一时间段内，内存中每一作业的运行时间相等。业的运行时间相等。作业到来次序作业到来次序 所需存储量所需存储量 运行时间运行时间 1 60KB 10s 2 100KB 5s 3 30KB 20s 4 70KB 8s 5 50KB 15sOS0 40 256J1J2J3J4J5分配：分配策略包括分配策略包括首次满足法首次满足法/ /最佳满足最佳满足法法/ /最大满足法，最大满足法，在找到合适的空闲块后，在找到合适的空闲块后，从其中将作

9、业大小的空间分给作业，而剩从其中将作业大小的空间分给作业，而剩余部分挂入空闲队列。余部分挂入空闲队列。 下面下面F F 是空闲块集合是空闲块集合; size(; size(k k) )为块为块k k的大小的大小; ; size(size(v v) )为用户所需空间。为用户所需空间。 1.1.如果所有属于如果所有属于F F 的的k k，均有，均有size(size(k k)size()size()size(v v) ) 3. 3.F F = = F F k k;回收： 当作业结束时，收回作业所占空间，当作业结束时，收回作业所占空间，将此块链入空闲队列。将此块链入空闲队列。 若空闲队列中原来有与此

10、块的相邻块，若空闲队列中原来有与此块的相邻块，则把这些块合并成一个大连续块。则把这些块合并成一个大连续块。（续分配）（续分配） 4. 4. 如果如果size(size(k k)-size()-size(v v) )基本单位，则基本单位，则将将k k分给用户。分给用户。 5. 5. 否则将否则将k k分成分成k k1,1,k k2 2，其中，其中 size(size(k k1)=size(1)=size(v v) )，F F = = F F + + k k22紧致：通过移动作业位置可以将零散的空通过移动作业位置可以将零散的空闲块连接成大块。要求作业动态可浮动。闲块连接成大块。要求作业动态可浮动。

11、Bitmap数组1,1,1,0,0,1,0,0,0,0,1,0,03 21412空闲队列头 二、可用空间管理 除用队列表示可用空闲块外除用队列表示可用空闲块外, ,也可以也可以用数组登记可用空闲块，数组项用数组登记可用空闲块，数组项= =用户空用户空间总量间总量/ /基本分配单位。基本分配单位。一、空间安排 用户进程空间用户进程空间( (地址地址) )叫叫逻辑空间逻辑空间( (地址地址);); 内存空间内存空间( (地址地址) )叫叫物理空间物理空间( (地址地址);); 用相同长度为单位对逻辑空间等分出的每用相同长度为单位对逻辑空间等分出的每 个区域叫个区域叫页，页，对物理空间等分出的区域叫

12、对物理空间等分出的区域叫 页帧，页帧，对外存交换区等分出的每个区域叫对外存交换区等分出的每个区域叫 块。块。5.2 不连续空间分配5.2.1 页式管理特点：作业作业( (进程进程) )分成页面，内存也划分分成页面，内存也划分成页面，将作业成页面，将作业( (进程进程) )页面不连续地分布页面不连续地分布到内存页面。到内存页面。回收：当进程结束时，系统回收它的所有当进程结束时，系统回收它的所有物理页帧入空闲队列。物理页帧入空闲队列。 二、动态地址转换机构 因页式方法中逻辑地址与物理地址之因页式方法中逻辑地址与物理地址之间失去自然联系，故要通过间失去自然联系，故要通过页表，页表，并由硬并由硬件件动

13、态地址转换机构动态地址转换机构将逻辑地址映射成物将逻辑地址映射成物理地址才能正确访存。理地址才能正确访存。分配：初始时，所有页帧都在空闲队列初始时，所有页帧都在空闲队列中，当用户进程被创建时，系统按需要中，当用户进程被创建时，系统按需要量从空闲队列获得相应量的页帧。量从空闲队列获得相应量的页帧。18530498765432103210逻辑空间物理空间页表页表 (一)页表 页表放在系统空间的页表区，存放逻辑页表放在系统空间的页表区，存放逻辑页与物理页帧的对应关系。页与物理页帧的对应关系。PCBPCB表中有指针表中有指针指向页表。指向页表。页号页号 (二)地址结构 逻辑地址逻辑地址 = p(= p

14、(页号页号) ) d(d(页内位移页内位移) ) 物理地址物理地址 = f(= f(页帧号页帧号) ) d(d(页内位移页内位移) ) p p = = 线性逻辑地址线性逻辑地址 / / 页面大小；页面大小； d d = = 线性逻辑地址线性逻辑地址 p p页面大小。页面大小。43210页号页号 (三)页面大小的考虑 将页面大小取成将页面大小取成2 2的的k k次幂次幂( (k k是正整数是正整数),),获取获取p p和和d d的除法或乘法只要通过位移实现。的除法或乘法只要通过位移实现。 页面大小为页面大小为2 2的的k k次幂的地址转换原理次幂的地址转换原理如下：如下：P d页表始地fn k-

15、10f dn k-10+页表 CPU CPU有一个用于有一个用于页号页号页帧号页帧号转换的联转换的联想存储器。将页表存入联想存储器的地址，想存储器。将页表存入联想存储器的地址，其转换原理如下：其转换原理如下：P dn k-10f dn k-10P2f2P1f1.Pf.Pmfm (四)联想存储器关键字关键字 值值地址转换的一般过程：地址转换的一般过程：( (联想存储器可以看成是页表的联想存储器可以看成是页表的cache)cache)P dn k-10f dn k-10P2f2P1f1.Pf.Pmfmf页表始地+页表联想存储器 在进程被调度占用在进程被调度占用CPUCPU时，将进程页表时，将进程页

16、表始址装入页表始地址寄存器，同时用新的始址装入页表始地址寄存器，同时用新的页表内容替换联想存储器中的原内容。页表内容替换联想存储器中的原内容。命中率：命中率：选用选用8 81212项组成的联想存储器，项组成的联想存储器，并采用适当的替换策略，在联想存储器中并采用适当的替换策略，在联想存储器中匹配成功的可能性可达匹配成功的可能性可达80%80%90%90%。等效访问时间：等效访问时间：设访存时间为设访存时间为750ns750ns，搜索，搜索联想存储器的时间为联想存储器的时间为50ns50ns，命中率为，命中率为80%80%，则：则： 80%80%(750+50)+20%(750+50)+20%(

17、750+50+750(750+50+750）950ns950ns 三、可用空间管理 可用可用bitmapbitmap数组或空闲页帧链来管理数组或空闲页帧链来管理可用页帧可用页帧。 四、共享与保护 通过页表可以使几个逻辑空间指向同通过页表可以使几个逻辑空间指向同一个物理空间，实现程序共享。一个物理空间，实现程序共享。 举例举例：EDIT1EDIT2EDIT3DATA1EDIT1EDIT2EDIT3DATA2EDIT1EDIT2EDIT3DATA33461346734610OSDATA1EDIT10 1 2 3 4 5 6 7 8 9 10 11EDIT2EDIT3 DATA2DATA3P1 P2P3页表存储保护： 越界保护：越界保护：设置页表长度寄存器，查页设置页表长度寄存器，查页表前，先检查页号是否越界。表前，先检查页号是否越界。 操作访问保护：操作访问保护：在每个页表项中增设一在每个页表项中增设一存储保护域，用于说明对该页的访问权存储保护域，用于说明对该页的访问权限，每一个对该页存储的访问都首先比限，