存储管理PPT学习教案

1、会计学1存储管理存储管理操作系统的资源管理 (3) 主存管理 2第1页/共61页3操作系统的资源管理 (3) 主要内容 第2页/共61页4分区存储管理段式存储管理操作系统的资源管理 (3) 主存管理的功能 页式存储管理段页式存储管理一个程序是一个连续、线性的地址结构；确定线性地址空间中的指令地址或操作数地址只需要一个信息。 程序地址空间程序地址空间01 n-1 第3页/共61页5一个程序由若干个分段组成，每个分段是一个连续的地址区；确定任一线性地址空间中的指令地址或操作数地址需要两个信息，一是该信息所在的分段，另一个是该信息在段内的偏移量。code_addr4KB 10代码分代码分段段data

2、_addr3KB 10数据分数据分段段stack_addr2KB 10栈段栈段11 操作系统的资源管理 (3) 主存管理的功能 第4页/共61页6 物理地址是计算机主存单元的真实地址，又称为绝对地址或实地址。 物理地址的集合所对应的空间组成了主存空间。 用户的程序地址(指令地址或操作数地址)均为逻辑地址。 用户程序所有的逻辑地址集合对应的空间。操作系统的资源管理 (3) 主存管理的功能 第5页/共61页7主存空间主存空间01m-1作业作业1地址空地址空间间01n-1作业作业 i 地址空地址空间间01k-1 操作系统的资源管理 (3) 主存管理的功能 第6页/共61页8操作系统的资源管理 (3)

3、 主存管理的功能 第7页/共61页9什么是地址映射 将程序地址空间中使用的逻辑地址变换成主存中的物 理地址的过程，称为地址映射。mov r1,5001230100500599作业地址空间作业地址空间mov r1,50012301000110015001599256k-1存储空间存储空间操作系统的资源管理 (3) 主存管理的功能 第8页/共61页10静态地址映射 在作业装入过程中随即进行的地址变换方式称为静态 地址映射。mov r1,500mov r1,500+m01005005990mm+100256k-1作业地址空间作业地址空间存储空间存储空间m+500重定位重定位装入程序装入程序12312

4、3操作系统的资源管理 (3) 主存管理的功能 第9页/共61页11动态地址映射 在程序执行期间，随着每条指令和数据的访问自动地 连续地进行地址映射，这种地址变换方式称为动态地 址映射。重定位寄存器重定位寄存器 1000 500逻辑地址+0 mov r1 , 500 1000256k-1存储空间110015001600123mov r1,5000100500599作业地址空间123操作系统的资源管理 (3) 主存管理的功能 第10页/共61页12静态地址映射与动态地址映射的区别静态地址映射 动态地址映射 操作系统的资源管理 (3) 主存管理的功能 第11页/共61页13构造分配用的数据结构制定策

5、略分配策略在众多个请求者中选择一个请求者的原则放置策略在可用资源中选择一个空闲区的原则调入策略决定信息装入主存的时机 预调策略：预先将信息调入主存 请调策略：当需要信息时，将信息调入主存淘汰策略在主存中没有可用的空闲区(对某一作业而言)时，决定哪些信息从主存中移走，即确定淘汰已占用的内存区的原则。实施主存分配与回收操作系统的资源管理 (3) 主存管理的功能 第12页/共61页14实现方法程序的全部代码和数据存放在辅存中；将程序当前执行所涉及的那部分程序代码放入主存中；程序执行时，当所需信息不在主存，由操作系统和硬件相配合来完成主存从辅存中调入信息，程序继续执行。什么是虚拟存储器 由操作系统和硬

6、件配合完成主存和辅存之间信息的动态 调度。计算机系统为用户提供一个其存储容量比实际主 存大得多的存储器，这个存储器称为虚拟存储器。局部性特征局部性特征操作系统的资源管理 (3) 主存管理的功能 第13页/共61页15虚拟存储器的核心逻辑地址与物理地址分开存储空间与虚地址空间分开提供地址变换机构实现虚拟存储器的物质基础有相当容量的辅存 足以存放应用程序的虚地址空间有一定容量的主存 存放进入主存的多进程的信息地址变换机构 操作系统的资源管理 (3) 主存管理的功能 第14页/共61页16什么是存储保护 在多用户环境中，主存储器按区分配给各用户程序使 用。为了互不影响，必须由硬件(软件配合)保证各用

7、户 程序只能在给定的存储区域内活动，这种措施叫做存 储保护。操作系统的资源管理 (3) 主存管理的功能 第15页/共61页17界地址保护上下界防护 例：作业大小为4KB，主存首址为20KB。 mov r1 , 500 123020KB256KB 1存储空存储空间间24KB下界寄存器下界寄存器 20KB上 界 寄 存上 界 寄 存器器 24KB设置上下界寄存器内容 ？判断是否越界 ？ 若 20KBD24KB 允许访问； 否则发生越界中断操作系统的资源管理 (3) 主存管理的功能 第16页/共61页18基地址、限长防护 例：作业大小为4KB，主存首址为20KB。设置基址、限长寄存器内容 ？判断是否

8、越界 ？ 若 逻辑地址 4KB 允许访问； 否则发生越界中断 mov r1 , 500 123020KB256KB 1存储空存储空间间24KB基址寄存器基址寄存器 20KB限 长 寄 存限 长 寄 存器器 4KB操作系统的资源管理 (3) 主存管理的功能 第17页/共61页19 在处理作业的过程中，建立分区，依请求的大小分配分区。操作系统的资源管理 (3) 分区存储管理 第18页/共61页20作业作业1申请申请 32KB 0 256KB 1主存主存2 0 KBos20KB 0 5 2 KB256KB 1主存主存os作业1作业作业2申请申请 14KB20KB 0 5 2 KB66KB256KB

9、1主存主存os作业1作业2作业作业3申请申请 64KB2 0 KB 0 52KB66KB130KB256KB 1主存主存os作业1作业2作业3作业作业4申请申请 100KB2 0 KB 0 52KB66KB130KB230KB256KB 1主存主存os作业1作业2作业3作业4作业作业5申请申请 50KB操作系统的资源管理 (3) 分区存储管理 第19页/共61页21作业作业2 完成完成 作业作业4 完成完成 20KB 0 52KB66KB130KB230KB256KB 1主存主存作 业1作 业2作 业3作 业4os20KB 0 52KB66KB1 3 0 KB230KB256KB 1主存主存作

10、 业1作 业3作 业4os20KB 0 52KB6 6 KB130KB230KB256KB 1主存主存os作 业1作 业3操作系统的资源管理 (3) 分区存储管理 第20页/共61页22 等待队列头指针 空闲区队列头指针 主存分配程序入口地址M_RIBflag： 为 0 空闲区 为 1 已分配区 size： 分区大小 next：空闲区自由主存队列中的勾链字 已分配区此项为零 分配标志 flag 大小 size 勾链字 nextPD操作系统的资源管理 (3) 分区存储管理 第21页/共61页232 0 KB 0 5 2 KB6 6 KB130KB230KB256KB 1主存主存os作业1作业3作

11、业45 2 KBm_rib 空闲区队列空闲区队列230KB01 4 KB02 6 KB 操作系统的资源管理 (3) 分区存储管理 第22页/共61页24 选择空闲区的策略，称为放置策略。 常用的放置策略 首次匹配(首次适应算法) 最佳匹配(最佳适应算法) 操作系统的资源管理 (3) 分区存储管理 第23页/共61页25首次适应算法是将输入的作业放置到主存里第一个足 够装入它的地址最低的空闲区中。 作 业作 业A 18KB首次适应算法的例空闲区队列结构 空闲区地址由低到高排序 尽可能地利用存储器中低 地址的空闲区，而尽量保 存高地址的空闲区。 在使在使用用在使用在使用在使用在使用30KB5KB4

12、6KB0KB20KB100KB20KB160KB210KB256KB- -1主存主存os操作系统的资源管理 (3) 分区存储管理 第24页/共61页26最佳适应算法是将输入的作业放置到主存中与它所需 大小最接近的空闲区中。 作 业作 业A 18KB最佳适应算法的例空闲区队列结构 空闲区大小由小到大排序最佳适应算法的特点 尽可能地利用存储器中小的 空闲区，而尽量保存大的空 闲区。 在使在使用用在使用在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB- -1主存主存os操作系统的资源管理 (3) 分区存储管理 第25页/共61页27作业A要求18

13、KB；作业B要求25KB；作业C要求30KB。 用首次适应算法、最佳适应算法、最坏适应算法来处理 该作业序列，看哪种算法合适。 操作系统的资源管理 (3) 分区存储管理 第26页/共61页28首次适应算法、最佳适应算法队列结构 在使在使用用在使用在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB- -1主存主存os(a) 首次适应算法的空闲区队首次适应算法的空闲区队列列 20KB 0 30KB 100KB 0 20KB 160KB 0 5KB 210KB 0 46KB (a) 最佳适应算法的空闲区队最佳适应算法的空闲区队列列160KB 0 5

14、KB 100KB 0 20KB 20KB 0 30KB 210KB 0 46KB 操作系统的资源管理 (3) 分区存储管理 第27页/共61页29首次适应算法 作业A要求18KB，作业B要求25KB，作业C要求30KB 首次适应算法对该作业序列是不合适的 在使在使用用在使用在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB- -1主存主存os(a) 首次适应算法的空闲区队首次适应算法的空闲区队列列 20KB 0 30KB 100KB 0 20KB 160KB 0 5KB 210KB 0 46KB 操作系统的资源管理 (3) 分区存储管理 第2

15、8页/共61页30最佳适应算法 在使在使用用在使用在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB- -1主存主存os(a) 最佳适应算法的空闲区队最佳适应算法的空闲区队列列160KB 0 5KB 100KB 0 20KB 20KB 0 30KB 210KB 0 46KB 操作系统的资源管理 (3) 分区存储管理 作业A要求18KB，作业B要求25KB，作业C要求30KB 最佳适应算法对该作业序列是合适的 第29页/共61页31在已分配区之间存在着的一些没有被充分利用的空闲区 如何解决碎片问题？如何解决碎片问题？ 所谓拼接技术是指移动存储器

16、中某些已分配区中的信息，使本来分散的空闲区连成一个大的空闲区。 20KB 54KB58KB135 KB254KB256KB 1主主存存138KB作业2 0os作业3作 业拼接前20KB 0 5 4 KB1 3 1 KB2 4 7 KB256KB 1主主存存os作 业作业2作业3拼接后操作系统的资源管理 (3) 分区存储管理 第30页/共61页32 程序的地址空间被等分成 大小相等的片，称为页面， 又称为虚页。主存被等分成大小相等的片，称为主存块，又称为实页。02 KB4KB254KB256KB 102KB4KB6KB0页1页2页3页主存主存作业地址空间作业地址空间操作系统的资源管理 (3) 页

17、式地址变换 第31页/共61页33 为了实现从地址空间到物理主存的映象，系统建立的 记录页与内存块之间对应关系的地址变换的机构称为 页面映像表，简称页表。高速缓冲存储器 地址变换速度快，但成本较高主存区域 地址变换速度比硬件慢，成本较低操作系统的资源管理 (3) 页式地址变换 第32页/共61页3401KB01KB2KB3KB 1主存主存作业作业2地址空间地址空间2KB3KB4KB5KB6 KB7 KB8 KB9 KB10KB 101KB2KB 1作业作业1地址空地址空间间01KB 1作业作业3地址空间地址空间0516页页号号块块号号02140827作业作业1页表页表作业作业2页表页表作业作业

18、3页表页表osos操作系统的资源管理 (3) 页式地址变换 第33页/共61页35 记录页与块之间对应关系的。 当CPU给出的虚地址长度为16位，页面大小为1KB时，在分页系统中地址结构的格式如下： p w15 10 9 0页号页号P页内位移页内位移Wmov r1 ,250012301KB2KB3KB 1作业作业2地址空间地址空间操作系统的资源管理 (3) 页式地址变换 第34页/共61页361页式地址变换的例 作业2地址空间中，设100号单元处有如下指令： mov r1,2500。当这条指令执行时，如何进行正确的 地址变换。2500 21024 + 452 p=2 w=45200001001

19、11000100 000010 0111000100mov r1 ,250012301KB2KB3KB 1作业作业2地址空间地址空间操作系统的资源管理 (3) 页式地址变换 第35页/共61页37页式地址变换过程页表始址寄存页表始址寄存器器mov r1 ,250012301KB2KB3KB 1作业作业2地址空间地址空间+021427页页表表 0 0 0 0 1 0 0 1 1 1 0 0 0 1 0 015 10 9 0页号页号P页内位移页内位移W250001 KB主存主存2KB3KB4KB5 KB6 KB7 KB8 KB9KB10KB 1ososmov r1 , 2500123第第1页页页号

20、页号P页内位移页内位移W 15 10 9 00 0 0 1 1 10 1 1 1 0 0 0 1 0 071024+452=7620操作系统的资源管理 (3) 页式地址变换 第36页/共61页38页式地址变换步骤CPU给出操作数地址(为2500) ；由分页机构自动地把逻辑地址分为两部分，得到页 号p和页内相对位移w (p =2， w =452)；根据页表始址寄存器指示的页表始地址，以页号为 索引，找到第2页所对应的块号(为7) ；将块号b和页内位移量w拼接在一起，就形成了访问 主存的物理地址 (71024+452=7620)操作系统的资源管理 (3) 页式地址变换 第37页/共61页39什么是

21、联想存储器 高速、小容量半导体存储部件，又称缓冲存储器快表 在缓冲存储器中存放正在运行的进程当前用到的页号 和对应的块号，又称为快表。操作系统的资源管理 (3) 页式地址变换 第38页/共61页40利用快表进行地址映射 a + P w 仅在联想映像不匹配时进行仅在联想映像不匹配时进行页号页号 b w首首先先选选择择联想存储器联想存储器所有页表在主存中所有页表在主存中物理地址物理地址pbba+pa操作系统的资源管理 (3) 页式地址变换 第39页/共61页41 页号页号 主存块号主存块号 中断位中断位 辅存地址辅存地址中断位I 标识该页是否在主存 若i=1，表示此页不在主存；若i=0，表示该页在

22、主存辅存地址 该页面在辅存的位置操作系统的资源管理 (3) 请求页面的机制 装入一个作业的全部页面才能投入运行装入一个作业的部分页面即可投入运行 第40页/共61页42作业2在请求分页系统中的存储映像01 KB2 KB4KB 1作业作业2地址空地址空间间mov r1,2120add r1,3410006251 006802 3 KB01KB主存主存2KB3KB4KB5KB6KB7KB8KB9KB10KB 102142作业作业2页页表表osos作业2 第 1页作业2 第 0页3页号页号 辅存地址辅存地址 中断位中断位 块号块号 0011地址地址地址地址操作系统的资源管理 (3) 请求页面的机制

23、第41页/共61页43缺页处理的例 作业2的主存块数为 m2=3，讨论程序执行 “mov r1，2120”指令时的情况。CPU产生的虚地址为2120分页机构得 p=2，w=72查页表。该页中断位i=1发生缺页中断 ！ 如主存中有空白块，且nm 则直接调入如主存中无空白块，或n m ，则需淘汰该作业在主存中的一页01 KB2 KB4KB 1作业作业2地址空地址空间间mov r1,2120add r1,3410006251 006802 3 KB操作系统的资源管理 (3) 请求页面的机制 第42页/共61页44缺页处理 启动要处理的指令启动要处理的指令给出虚地址给出虚地址 得到页号得到页号该页在主

24、存该页在主存?有空闲块有空闲块? 缺页中断缺页中断执 行 完 该 指执 行 完 该 指令令 准备执行下条指令准备执行下条指令选一页淘汰选一页淘汰 从外存读入所需的页从外存读入所需的页 调整存储分配表和页表调整存储分配表和页表 重新启动被中断的指令重新启动被中断的指令 调整存储分配表和页调整存储分配表和页表表要重写入要重写入?该页写入外存该页写入外存YNNY硬件硬件软件软件YN操作系统的资源管理 (3) 请求页面的机制 第43页/共61页45 用来选择淘汰哪一页的规则叫做置换策略，或称淘汰算法。引用位 标识该页最近是否被访问 为“0” 该页没有被访问；为“1” 该页已被访问改变位 表示该页是否被

25、修改 为“0” 该页未被修改；为“1” 该页已被修改 页页 号号 主存块号主存块号 中断位中断位 辅存地址辅存地址 引用位引用位 改变位改变位操作系统的资源管理 (3) 淘汰机制与策略 第44页/共61页46颠簸 颠簸(thrashing)，又称为“抖动”。 简单地说，导致系统效率急剧下降的主存和辅存之间的 频繁页面置换现像称为“抖动”。缺页中断率假定程序p共有n页，系统分配m块，有 1mn； 若程序p在运行中：成功的访问次数为s，不成功的访 问次数为f；缺页中断率： f=f/ (s+ f) f= f (r，m，p)； r：置换算法； p：程序特征； m：系统分配的块数操作系统的资源管理 (3

26、) 淘汰机制与策略 第45页/共61页47最佳算法(OPT算法) 当要调入一新页而必须先淘汰一旧页时，所淘汰的那一页应是以 后不再要用的，或者是在最长的时间以后才会用到的那页。 先进先出淘汰算法(FIFO算法) 什么是先进先出淘汰算法 总是选择在主存中居留时间最长(即最早进入主存)的一页淘汰。先进先出淘汰算法的实现建立一个页面进入主存的先后次序表；建立一个替换指针，指向最早进入主存的页面；当需要置换一页时，选择替换指向的那一页，然后调整替换指 针的内容。操作系统的资源管理 (3) 淘汰机制与策略 第46页/共61页48页号表 页面进入主存的先后次序： 2451 替换指针 指向最老的一页页号 2

27、 4 5 16 当要调入第6页时：置换第2页将第2页改为6替换指针指向第4页 操作系统的资源管理 (3) 淘汰机制与策略 第47页/共61页49在存储分块表中建立次序表 页面进入主存的先后次序： 4512 当要调入第6页时： 如何处理 ? 512 67102345642516 74 2替换指针替换指针块号块号 页号页号 指针指针710234566251 274 6替换指针替换指针 块号块号 页号页号 指针指针操作系统的资源管理 (3) 淘汰机制与策略 第48页/共61页50最久未使用淘汰算法(LRU算法)什么是最久未使用淘汰算法 总是选择最长时间未被使用的那一页淘汰。最久未使用淘汰算法的实现用

28、引用位考察页面的使用情况；当访问页面时，将引用位置1，并记时；当要淘汰一页时，选择时间最长的一页淘汰。 要精确实现很困难硬件方法：采用计数器软件方法：采用页号栈操作系统的资源管理 (3) 淘汰机制与策略 第49页/共61页51用页号栈实现LRU算法 页面访问轨迹：451 2 5 64512访问第访问第5页页 访问第访问第6页页 淘汰第淘汰第4页页 41251256访问4、5、1、2页后栈的内容 访问第5页后，调整栈的内容 访问第6页后，栈的内容 操作系统的资源管理 (3) 淘汰机制与策略 第50页/共61页52LRU近似算法 (使用引用位)框图 入口入口读出替换指针指向的块号读出替换指针指向的

29、块号移动指针指向下一个存储块移动指针指向下一个存储块 引用位为引用位为0 ?选择该页淘汰，记录该页的页号选择该页淘汰，记录该页的页号、块号、块号将该页所在的将该页所在的块号送到块号送到替换指针替换指针返回返回置引用位为置引用位为0YN操作系统的资源管理 (3) 淘汰机制与策略 第51页/共61页53LRU近似算法举例7102345642514172 4替换指针替换指针 块号块号 页号页号 引用位引用位 指针指针60017102345642564072 7替换指针替换指针 块号块号 页号页号 引用位引用位 指针指针6011当要调入第当要调入第6页时，如何处理页时，如何处理 ?操作系统的资源管理 (3) 淘汰机制与策略 第52页/共61页54 分段是程序中自然划分的一组逻辑意义完整的信息集合。 分段的例：代码分段、数据分段、栈段页。 由若干个逻辑分段组成，每个分段有自己的名字，对于一个分段而 言，它是一个连续的地址区。c