连续存储管理 页式管理PPT学习教案

1、会计学1 连续存储管理连续存储管理 页式管理页式管理 第五章 存储管理 研究三方面的问题：研究三方面的问题： 取（取（fetchfetch） 放（放（placementplacement） 替换（替换（replacementreplacement） 请调、预调请调、预调 连续、非连续连续、非连续 第1页/共28页 内存空间安排内存空间安排 5.1 5.1 连续空间分配连续空间分配 5.1.15.1.1单道连续分配单道连续分配 特点：任一时刻内存只有一道作业，该任一时刻内存只有一道作业，该 作业连续存放于内存中。作业连续存放于内存中。 一、管理方法 操作系统操作系统 用户程序用户程序 0 a a

2、 a+1a+1 n n 界地址寄存器界地址寄存器 第2页/共28页 界地址寄存器界地址寄存器 主存主存A a?A a? cpucpu truetrue falsefalse 地址地址A A 终止程序运行终止程序运行 越界检查机构：用户程序每访问一次主用户程序每访问一次主 存，越界检查机构将访问的地址与界地存，越界检查机构将访问的地址与界地 址寄存器中的值比较。若越界，则终止址寄存器中的值比较。若越界，则终止 其执行。其执行。 第3页/共28页 二、覆盖（overlap） 操作系统操作系统 固定区固定区(4k)(4k) 覆盖区覆盖区(6k)(6k) 覆盖区覆盖区(10k)(10k) A(4k)A

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

4、 (等等CPU)CPU)状态的进程从主存换出到辅存，状态的进程从主存换出到辅存， 把将要执行的进程移入主存。把将要执行的进程移入主存。 三、交换 多道程序设计的要求多道程序设计的要求 交换要花费较长的时间。交换要花费较长的时间。 为了支持交换，必须在系统空间设立为了支持交换，必须在系统空间设立I/OI/O缓缓 冲区。冲区。 第5页/共28页 特点：任一时刻内存可有多道作业，每道作业任一时刻内存可有多道作业，每道作业 连续存放于内存连续存放于内存. . 操作系统操作系统 U1U1 . UnUn 5.1.2 5.1.2 多道固定划分法多道固定划分法 一、管理方法 将用户内存空将用户内存空 间分成长

5、度固定间分成长度固定 的若干块的若干块。 用户空用户空 间间 第6页/共28页 1.上下界寄存器和地址检查机构。当作业当作业 被调度运行时，作业在内存中的上下界地被调度运行时，作业在内存中的上下界地 址送上下界寄存器，每次内存访问时，地址送上下界寄存器，每次内存访问时，地 址检查机构作越界检查。作业程序是绝对址检查机构作越界检查。作业程序是绝对 地址或静态可浮动的。地址或静态可浮动的。 CPUCPU主存主存 下界寄存器下界寄存器上界寄存器上界寄存器 TrueTrueTrueTrue地址地址A A F F F F 程序性中断程序性中断 地址访问保护有两种方式地址访问保护有两种方式 ： 第7页/共

6、28页 2.基址寄存器、长度寄存器和动态地址转 换机构。当作业被调度运行时，将作业所当作业被调度运行时，将作业所 占内存基址及长度送基址、长度寄存器，占内存基址及长度送基址、长度寄存器， 每次内存访问时，先看访问地址是否小于每次内存访问时，先看访问地址是否小于 长度，然后长度，然后+ +基址进行访存。用户程序代码基址进行访存。用户程序代码 是可是可动态浮动动态浮动的。的。 CPUCPU主存主存 基地址寄存器基地址寄存器长度寄存器长度寄存器 + + TrueTrue 地址地址A A F F 程序性中断程序性中断 第8页/共28页 二、调度 OS 4k 6k 12k OS 4k 6k 12k .7

7、k3k4k5k .3k4k1k2k .5k6k .7k 10k11k8k 多队列法多队列法 单队列法单队列法 第9页/共28页 三、存储碎片 内部碎片：内部碎片：内存某存储区间大于其存放作内存某存储区间大于其存放作 业空间的部分。业空间的部分。 外部碎片：外部碎片：内存某存储区间容不下要运行内存某存储区间容不下要运行 的作业时。的作业时。 OS 12k 4k 3K 内部碎片内部碎片 OSOS 4k4k 6k6k 12k12k 作业长度：作业长度：5K5K、8K8K、12K12K 外部碎片外部碎片 第10页/共28页 一、管理方法 5.1.3 5.1.3 多道连续可变划分法多道连续可变划分法 特

8、点：多道、连续、但不固定划分内存。多道、连续、但不固定划分内存。 系统设置一个空闲块队列，初始状态时队列系统设置一个空闲块队列，初始状态时队列 中只有一个连续的空闲块。作业到达后，以某中只有一个连续的空闲块。作业到达后，以某 种策略分配空间。作业撤离时，将释放的空间种策略分配空间。作业撤离时，将释放的空间 加入空闲队列。加入空闲队列。 第11页/共28页 举例：假设任一时间段内，内存中每一作业举例：假设任一时间段内，内存中每一作业 的运行时间相等。的运行时间相等。 作业到来次序作业到来次序 所需存储量所需存储量 运行时间运行时间 1 60 10 2 100 5 3 30 20 4 70 8 5

9、 50 15 OS 0 40 256 J1J2J3J4J5 第12页/共28页 分配：分配策略包括分配策略包括首次满足法首次满足法/ /最佳满足最佳满足 法法/ /最大满足法最大满足法，在找到合适的空闲块后，在找到合适的空闲块后， 从其中将作业大小的空间分给作业，而剩余从其中将作业大小的空间分给作业，而剩余 部分挂入空闲队列。部分挂入空闲队列。 下面下面F F是空闲块集合是空闲块集合; size(k); size(k)为块为块k k的大小的大小; ; size(v)size(v)为用户所需空间。为用户所需空间。 1.1.if if 所有属于所有属于F F的的k k，均有，均有size(k)si

10、ze(v),size(k)size(v),则则 失败。失败。 2.2.否则按某一策略选出否则按某一策略选出k k，使得，使得 size(k)size(v).size(k)size(v). 3.3.F = F F = F k; k; 第13页/共28页 回收： 当作业结束时，收回作业所占空间，当作业结束时，收回作业所占空间， 将此块链入空闲队列。将此块链入空闲队列。 若空闲队列中原来有与此块的相邻块若空闲队列中原来有与此块的相邻块 ，则把这些块合并成一个大连续块。，则把这些块合并成一个大连续块。 （续分配）（续分配） 4. if size(k)-size(v)4. if size(k)-size

11、(v)基本单位，则将基本单位，则将k k分分 给用户。给用户。 5. 5. 否则将否则将k k分成分成k1k1、k2k2，其中，其中k1k1分给用户分给用户 size(k1)=size(v)size(k1)=size(v)， F = F + k2F = F + k2 第14页/共28页 紧致：通过移动作业位置可以将零散的空闲块连通过移动作业位置可以将零散的空闲块连 接成大块。要求作业动态可浮动。接成大块。要求作业动态可浮动。 Bitmap数组 1,1,1,0,0,1,0,0,0,0,1,0,0 3 2 1 4 1 2 空闲队列头 二、可用空间管理 除用队列表示可用空闲块外除用队列表示可用空闲块

12、外, ,也可以用数组也可以用数组 登记可用空闲块，数组项登记可用空闲块，数组项= =用户空间总量用户空间总量/ /基本基本 分配单位。分配单位。 第15页/共28页 一、空间安排 用户进程空间用户进程空间( (地址地址) )叫叫逻辑空间逻辑空间( (地址地址) ) 内存空间内存空间( (地址地址) )叫叫物理空间物理空间( (地址地址) )， 用相同长度为单位对逻辑空间等分出的用相同长度为单位对逻辑空间等分出的 每个区域叫每个区域叫页页，对物理空间等分出的区域，对物理空间等分出的区域 叫叫页帧页帧. . 5.2 5.2 不连续空间分配不连续空间分配 5.2.15.2.1页式管理页式管理 特点：

13、作业作业( (进程进程) )分成页面，内存也划分分成页面，内存也划分 成页面，将作业成页面，将作业( (进程进程) )页面不连续地分布页面不连续地分布 到内存页面。到内存页面。 第16页/共28页 回收：当进程结束时，系统回收它的所有当进程结束时，系统回收它的所有 物理页帧入空闲队列。物理页帧入空闲队列。 二、动态地址转换机构 因页式方法中逻辑地址与物理地址之因页式方法中逻辑地址与物理地址之 间失去自然联系，故要通过间失去自然联系，故要通过页表页表，并由硬，并由硬 件件动态地址转换机构动态地址转换机构将逻辑地址映射成物将逻辑地址映射成物 理地址才能正确访存。理地址才能正确访存。 分配：初始时，

14、所有页帧都在空闲队列初始时，所有页帧都在空闲队列 中，当用户进程被创建时，系统按需要中，当用户进程被创建时，系统按需要 量从空闲队列获得相应量的页帧。量从空闲队列获得相应量的页帧。 第17页/共28页 1 8 5 3 0 4 9 8 7 6 5 4 3 2 1 0 3 2 1 0 逻辑空间 物理空间 页表页表 (一)页表 页表放在系统空间的页表区，存放逻辑页与物页表放在系统空间的页表区，存放逻辑页与物 理页帧的对应关系。理页帧的对应关系。PCBPCB表中有指针指向页表。表中有指针指向页表。 页号页号 第18页/共28页 (二)地址结构 逻辑地址逻辑地址 = p(= p(页号页号).d().d(

15、页内位移页内位移) ) 物理地址物理地址 = f(= f(页帧号页帧号).d().d(同上同上) ) p = p = 线性逻辑地址线性逻辑地址 / / 页面大小；页面大小； d = d = 线性逻辑地址线性逻辑地址 - p- p* *页面大小。页面大小。 4 3 2 1 0 页号页号 第19页/共28页 (三)页面大小的考虑 将页面大小取成将页面大小取成2 2的的k k次幂次幂(k(k是正整数是正整数),),获取获取p p和和 d d的除、乘法只要通过位移实现的除、乘法只要通过位移实现. . 页面大小为页面大小为2 2的的k k次幂的地址转换原理如下：次幂的地址转换原理如下： P d 页表始地

16、 f n k-10 f d n k-10 + 页表 第20页/共28页 CPUCPU有一个用于有一个用于页号页号页帧号页帧号转换的联想转换的联想 存储器。将页表存入联想存储器的地址存储器。将页表存入联想存储器的地址 转换原理如下：转换原理如下： P d n k-10 f d n k-10 P2f2 P1f1 . Pf . Pmfm (四)联想存储器 关键字关键字 值值 第21页/共28页 地址转换的一般过程地址转换的一般过程 ( (联想存储器可以看成是页表的联想存储器可以看成是页表的cache)cache) P d n k-10 f d n k-10 P2f2 P1f1 . Pf . Pmfm

17、 f 页表始地 + 页表 联想存储器 第22页/共28页 在进程被调度占用在进程被调度占用cpucpu时，将进程页表始址装入时，将进程页表始址装入 页表始地址寄存器，同时作废掉联想存储器中的页表始地址寄存器，同时作废掉联想存储器中的 原内容。原内容。 命中率：命中率：选用选用8-128-12项组成的联想存储器，并采项组成的联想存储器，并采 用适当的替换策略，在联想存储器中匹配成功用适当的替换策略，在联想存储器中匹配成功 的可能性可达的可能性可达80-90%80-90%。 等效访问时间：等效访问时间：设访存时间为设访存时间为750ns750ns，搜索联想存，搜索联想存 储器的时间为储器的时间为5

18、0ns50ns，命中率为，命中率为80%80%，则（这里假设，则（这里假设 先查联想存储器再查页表）：先查联想存储器再查页表）： 80% 80% * *（750+50750+50）+ 20% + 20% * *（750+50+750750+50+750） = 950ns= 950ns 第23页/共28页 三、可用空间管理 可用可用bitmapbitmap数组或空闲页帧链来管理数组或空闲页帧链来管理 可用页帧可用页帧。 四、共享与保护 通过页表可以使几个逻辑空间指向同通过页表可以使几个逻辑空间指向同 一个物理空间，实现程序共享。一个物理空间，实现程序共享。 第24页/共28页 举例举例： EDIT1 EDIT2 EDIT3 DATA1 EDIT1 EDIT2 EDIT3 DATA