计算机操作系统 存储管理
计算机操作系统第6章 存储管理 Cpu寄存器主存辅存速度容量价格第6章 存储管理 利用率速度安全性第6章 存储管理 ¢6.1 地址重定位¢6.2 连续存储管理¢6.3 基本分页存储管理 ¢6.4 基本分段存储管理¢6.5 段页式存储管理方式¢6.6 虚拟存储器的基本概念¢6.7 请求分页存储管理方式库编译产 生的目 标模块链接 程序装入模块装入 程序内存绝对装入静态重定位装入动态重定位装入静态链接方式装入时动态链接运行时动态链接6.1 地址重定位内存地址逻辑逻辑 地址地址重定位6.1 地址重定位6.1 地址重定位¢(1)静态地址重定位静态地址重定位是在程序 执行之前由操作系统的重 定位装入程序完成的。 ¢(2)动态地址重定位 动态地址重定位是在程序执行期间进行的。 6.1 地址重定位(b)采用动态重定位时内存空间 及地址重定位示意图(a)采用静态重定位后的内存空间 返回本节6.1 地址重定位思考¢比较两种重定位 技术的优缺点?6.2 连续存储管理 ¢广泛应用于20世纪6070年代的os中。至 今,仍有使用。单一连续分配固定分区分配动态分区分配可重定位分区分配最早的多道 程序存储 管理方式内存的分配和回收方法6.2 连续存储管理 固定分区分配碎片OS0K20K256K进入C(64K)A(8K)B(16K)D(124K)OS0K20K256KC完成28K44K234K108K24KADCBOS0K20K256K进入28K44K234K108K24KAD64KBE(50K)F(16K)20K256K28K44K234K108K94KOS0KB、D完成8KAD14KBF250K14KOS0K20K256K28K44K234K108K8KA124K14K16K94KF250K14K6.2 连续存储管理 动态分区分配6.2 连续存储管理 “拼接”技术动态重定位可重定位分区分配Do you have any questions ?内存的分配和回收¢数据结构¢分配流程¢分配算法¢回收方法6.2 连续存储管理 空闲分区表空闲分区连6.2 连续存储管理 从头开始查表检查完否?m.size>u.size?m.size-u.sizesize?从该分区中划出 u.size大小的分区将该分区分配给请求 者修改有关数据结构返回返回继续检索下一个表项将该分区从链中移出YYYN NN动态分区存储管理 方式的分配流程6.2 连续存储管理 可重定位分区存储管 理方式的分配流程请求分配 u.size分区检查空闲分区链(表)找到u.size的 可用分区否?空闲分区 总和u.size?进行紧凑 形成连续空闲区修改有关的 数据结构按动态分区方式 进行分配修改有关的 数据结构返回分区号及首址无法分配返回YYNN6.2 连续存储管理 常用的分配算法¢(1)首次适应算法 ¢(2)最佳适应算法 ¢(3)最差适应算法 下一页首次适应算法下一页6.2 连续存储管理 最佳适应算法下一页6.2 连续存储管理 最差适应算法下一页6.2 连续存储管理 内存使用情况 6.2 连续存储管理 用三种适应算法处理同一作业序列40K100K150K首次最佳最坏思考¢比较三种算法的 优缺点内存回收6.2 连续存储管理 40K回收区F1F2(首址60,大小5)回收区F1F2(首址56,大小5)回收区F1F2(首址65,大小5)回收区F1F2(首址56,大小14)40K40K40K40K首次适应算法思考¢如果采用其他算法如何 回收 ?¢存储保护方式?Do you have any questions ?6.3 基本分页存储管理方式利用率? 碎片? 紧紧凑?离散管理6.3 基本分页存储管理方式0页页1页页2页页3页页4页页n页页页页号块块号02 132638495 01234567 8910用户程序内存页表逻 辑 地 址 空 间物 理 地 址 空 间页面 大小 如何 确定页表的 作用是 什么?是否还 存在 碎片?页表放在哪里? 如何访问?思考¢如何实现地址映 射?6.3 基本分页存储管理方式0页页1页页2页页3页页4页页n页页页页号块块号02 132638495 01234567 8910用户程序内存页表0102420482500L=10242500 / 1024 = 2,4522,4526,4526,4526*1024=61446596它的物理地址?6.3 基本分页存储管理方式4 904 15 10 9 0举例:逻辑地址5000可转换为页面地址结构 4*1024+904页号p 页内地址 d 15 10 9 0P = int A / L d = A mod L 6.3 基本分页存储管理方式4 90415 10 9 0举例:读取某进程其逻辑地址为5000的数据页页号块块号02 132638495 页表页表始址页表长度pcb该进程为运行态, 因此将频繁访问 这两个信息页表始址 页表长度页表寄存器减少内存 访问次数<越界中断+990410120基于页表的地址变换结构 思考¢上述地址映射过 程共访问多少次 内存?6.3 基本分页存储管理方式4 90415 10 9 0举例:读取某进程其逻辑地址为5000的数据基于快表的地址变换结构 页页号块块号02 132638495 页表页表始址 页表长度页表寄存器 <越界中断+990410120页页号块块号0294快表思考¢基于快表的地址映射 能否完全实现1次内存 访问?Do you have any questions ?6.4 基本分段存储管理方式分页页目的分段目的6.4 基本分段存储管理方式01K分段MAIN (主程序)0600分段X(子程序)0540 分段A(数组)0300分段X(工作区)段号s 段内位移w23 16 15 06.4 基本分段存储管理方式030K作业空间 (Main)=0020K(X)=1015K(D)=2010K(S)=3段号段长长基址030K40K120K80K215K120K310K150K(Main)=030K(D)=2 15K(S)=3 10K内存空间 0K40K(X)=1 20K80K120K150K段表段表始址段表寄存器段表 段号段长 内存始址 01k6k 16404k 250010k 330012k103402 100物理地址逻辑地址段号s位移量w1234510k10340内存段表长度<越界<越界6.4 基本分段存储管理方式基于段表的地址变换结构 思考¢1、分段管理和分 业管理的区别是什 么?¢2、基于快表的地 址映射过程?¢3、分析内存共享016K分段MAIN (主程序)010K分段X(子程序)08K分段A(数组)0300分段X(工作区)4K8K4K4K8K 12K段号 页号 页内位移6.5 段页存储管理方式段表大小 段表始址段号页页表大小页页表始址页页号块块号页页号块块号01234567 8910内存6.5 段页存储管理方式段号 页号 页内位移段表始址 段表长度段表地址寄存器段号 段内页号 页内位移逻辑地址+越界中断<段号页页表大小页页表始址越界中断<+页页号块块号页表段表块号 偏移地址物理地址访问一个内存信息, 需要读几次内存?6.5 段页存储管理方式思考¢1、分页存储采用什么 样的内存分配方法?¢2、分段呢?¢3、内存利用率分析?6.6虚拟存储器的基本概念传统存储管理存在两个问题:单个作业大小内存容量大量作业要求运行扩充内存 !6.6虚拟存储器的基本概念扩充内存的技术¢对换技术6.6虚拟存储器的基本概念¢局部性原理:1968年 ,Denning.P提出:程序在执行时将呈现出局部性规律,即在一较短时间内,程序的执行仅局限于某个部分;相应地,它所访问的存储空间也局限于某个区域。常规存储管理的特点:1、 一次性;2、 驻留性¢2 、 对换技术6.6虚拟存储器的基本概念就绪R执行E阻塞B后备备 队队列 DA就绪绪 队队列 BCG阻塞 队队列I外存对换区JEE很紧急!但此 时内存已不足换出H换入J换出后,腾出 足够的内存空间当内存中进程运行结束, 腾出足够的内存空间此,即中级调度 也称“对换”¢2 、 对换技术分类:l整体对换(进程);l部分对换(页、段);6.6虚拟存储器的基本概念重点学习内容!6.6虚拟存储器的基本概念虚拟存储器概念:具有请求调入功能和置换功能 ,能从逻辑上对内存加以扩充的存储其系统。 特点:多次性、对换性、虚拟性、离散性Do you have any questions ?6.7请求分页存储管理方式1、页表页页号物理块块号状态态位P访问访问 字段A修改位M外存地址0231A0010001null0A111001当执行到该页中的指令时, 将发出请求调入页面的中断信号6.7请求分页存储管理方式2、缺页中断机构保留CPU现场从外存中找到缺页内存满否?选择一页换出内存被修改否?将该页写回外存Os命令CPU从外存读缺页启动I/O硬件将一页从外存换入内存修改页表否是否是返回页页 号物 理 块块 号状 态态 位 P访访 问问 字 段 A修 改 位 M外 存 地 址思考¢1、缺页中断与一般 中断的区别¢2、地址变换机构与 基本分页管理系统的 区别6.7请求分页存储管理方式¢3、页面置换算法l1)最佳置换算法(OPT)l2)先进先出页面置换算法(FIFO)l3)最近最久未使用置换算法(LRU)有以下页面号引用流:7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 系统分配给该进程3个物理块。6.7请求分页存储管理方式1)OPT算法该算法由Belady于1966年提出的一种理论上的算法。7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,16.7请求分页存储管理方式发生6次置换发生9次缺页缺页率 = 9 / 206.7请求分页存储管理方式3)FIFO算法这是最早出现的置换算法。7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1发生12次置换发生15次缺页缺页率 = 15 / 206.7请求分页存储管理方式3)LRU算法根据页面调入内存后的使用情况进行决策。7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1发生9次置换发生12次缺页缺页率 = 12 / 20页页号物理块块号状态态位P访问访问字段At:时间时间段修改位M外存地址01234567Do you have any questions ?m(分配页面数)缺页次数0m(分配页面数)缺页次数06.7请求分页存储管理方式分配的物理块数影响缺页率Belady现象LRU算法性能分析(m=3)分配的物理块数影响缺页率LRU算法性能分析(m=4)7/12=58%10/12=83%6.7请求分页存储管理方式6.7请求分页存储管理方式分配的物理块数影响缺页率FIFO算法性能分析(m=3)FIFO算法性能分析(m=4)9/12=75%10/12=83%¢2、抖动现象 ¢在虚存中,页面在内存 与外存之间频繁调度, 以至于调度页面所需时 间比进程实际运行的时 间还多,此时系统效率 急剧下降,甚至导致系 统崩溃。这种现象为抖 动(或颠簸)6.7请求分页存储管理方式缺页页率?抖动动Do you ha