《【教学课件】第六章存储管理.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第六章存储管理.ppt（81页珍藏版）》请在三一办公上搜索。
1、第六章 存储管理,存储管理功能内存资源管理存储管理方式外存空间管理虚拟存储系统,6.1 存储管理功能,存储分配和去配分配去配对象内存、外存(相同方法)分配去配时刻进程创建、撤销、交换、长度变化存储共享目的：节省内存、相互通讯内容：代码、数据存储保护防止地址越界防止操作越权,6.1 存储管理功能(Cont.),存储扩充内存、外存结合，虚拟存储体系速度接近内存，容量相当外存地址映射逻辑地址=物理地址硬件支持基址寄存器(base)、限长寄存器(limit)、快表；使用上述寄存器完成地址映射过程；不能正常完成地址映射时产生中断。,6.2 内存资源管理,6.2.1 内存分区分区时刻静态分区：系统初始化时
2、分；动态分区：申请时分。分区大小等长分区：2i异长分区：依程序、程序单位、对象大小。通常作法静态+等长（页式、段页式）动态+异长（段式、界地址）,6.2.2 内存分配,静态等长分区的分配 字位映象图 空闲页面表 空闲页面链动态异长分区的分配最先适应(First Fit)最佳适应(Best Fit)最坏适应(Worst Fit),字位映象图（bit map）,空闲页面表,特点：可以分配连续页面。,占用,占用,120页,121页,122页,123页,.,.,空闲页面链,占用,占用,占用,Head:,优点：节省空间。（不适合管理外存）,动态异长分区的分配,数据结构：,Criteria:尽量使空闲区域
3、连续。,初始时一个连续空闲区。长度=0为表尾。,最先适应算法（First Fit）,空闲区：首址递增排列；申请：取第一个可满足区域；优点：尽量使用低地址空间，高区保持大空闲区域。缺点：可能分割大空闲区。Eg.申请32将分割第 一个区域。,最佳适应算法（Best Fit）,空闲区：首址递增排列；申请：取最小可满足区域；优点：尽量使用小空闲区，保持大空闲区。缺点：可能形成碎片(fragment)。Eg.申请30将留下长 度为2的空闲区。,最坏适应算法（Worst Fit）,空闲区：首址递增排列；申请：取最大可满足区域；优点：防止形成碎片。缺点：分割大空闲区域。,6.2.3 碎片处理,紧凑：移动占用
4、区域，使所有空闲区域连成一片（开销很大）。,OS,P1(248k),P2(250k),8k,6k,4k,256k:,512k:,768k:,264k:,518k:,256k:,504k:,754k:,18k,6.3 存储管理方式,界地址管理方式（一维地址）页式管理方式（一维地址）段式管理方式（二维地址）段页式管理方式（二维地址）,6.3.1 界地址管理方式,4.3.1.1 基本原理 1.内存空间划分：动态异长；2.进程空间划分：一个进程一个区域，逻辑地址0l-1 3.进程空间与内存空间对应关系（可以浮动）：,0:,l-1:,.,.,b:,l,b+l-1:,进程空间,内存空间,6.3.1 界地址
5、管理方式,4.所需表目：(1)内存分配表-在PCB中；(2)空闲区域表：array of(addr,size)。5.所需寄存器：(1)基址寄存器；(2)限长寄存器。6.地址映射：,6.3.1 界地址管理方式,0:,l-1:,.,.,b:,l,b+l-1:,l,b,逻辑地址,CP,+,a,a+b,步骤：(1)由程序确定逻辑地址a；(2)a与l比较判断是否越界，不满足：0al-1，越界；(3)a与b相加得到物理地址。,进程空间,内存空间,6.3.2 分页式存储管理(paging),6.3.2.1 基本原理 1.内存空间划分：静态等长，2i,称为一个页架。,.,.,第0页,第1页,第k页,第2n-i
6、-1页,2i,02i:,12i:,k2i:,(2n-i-1)2i:,物理地址=页架首址+页内地址=页架号 2i+页内地址=,i位,n-i位,6.3.2 分页式存储管理,2.进程空间划分：静态等长，2i,称为一个页面。,.,.,第0页,第1页,第k页,第l-1页,2i,02i:,12i:,k2i:,(l-1)2i:,逻辑地址=逻辑页首址+页内地址=逻辑页号 2i+页内地址=,i位,3.进程空间与内存空间对应关系,.,第0页,第1页,第2页,第3页,第16页,第22页,第32页,第15页,.,.,.,进程空间,内存空间,4.所需表目：,(1)页表，每个进程一个,物理页号,逻辑页号:,15,22,1
7、6,32,0,1,2,3,5.所需寄存器,(2)总页表：系统一个,(1)页表首址寄存器：,b,l,(2)页表长度寄存器：,系统一个,系统一个,(3)快表：系统一组：,逻辑页号,页架号,.,.,.,.,f,p,逻辑地址(p,d)物理地址(f,d)(1)由程序确定逻辑地址(p,d)；(2)由p查快表得页架号f；如查不到：(a)由p与l比较，判别是否越界：不满足：0pl-1，越界；(b)由p和b查页表得f,(p,f)快表，如满淘汰一个；(c)转(2);(3)f与d合并得物理地址,6.地址映射:(p,d)(f,d),.,逻辑页号,页架号,.,.,.,.,f,p,l,b,b,l,.,.,PCB,页架号,
8、逻辑页号,.,f,.,p,.,f d,+,cp,p f,物理地址,逻辑地址,b:,.,6.3.2.2 多级页表,提出背景进程虚拟空间大幅度增加单级页表需要很大连续内存空间例如32位进程地址空间，页长4k（占12位），页号20位，页表需要220个入口！解决策略二级或多级页表,Two-Level Page-Table Scheme,Address-Translation Scheme,6.3.2.3 反置页表(inverted page table),传统页表面向进程空间每个进程逻辑页面有一表项当进程空间很大时，页表很大反置页表面向内存空间每个内存页架一个表项大小固定,反置页表-工作原理,反置页表
9、,1.内存空间划分：动态异长，每区一段。,段首址+段内地址,物理地址=,b：,l,b+d,6.3.3 分段式存储管理(segmentation),2.进程空间划分：若干段，每段一个程序单位。,调用x段e,f:访问d段a,e:调用y段f,main(段号0),X(段号1),Y(段号2),D(段号3),a:,080k-1,0.40k-1,020k-1,060k-1,逻辑地址=,段号 段内地址,(二维地址),main,x,y,d,3.对应关系,40k,60k,80k,20k,.,.,.,.,进程空间,内存空间,100k:,200k:,300k:,320k:,4.所需表目,(1)段表：每进程一个,段首址
10、,段长度,100k,40k,80k,60k,段号,0:1:2:3:,20k,200k,320k,300k,(2)空闲表：系统一个 array of(addr,size),5.所需寄存器,(1)段表首址寄存器：,b,l,(2)段表长度寄存器：,系统一个,系统一个,(3)快表：系统一组：,段号 段首址 段长度,.,.,.,.,l,s,.,b,.,6.地址映射:(s,d)(b+d)逻辑地址(s,d)物理地址(b+d)(1)由程序确定逻辑地址(s,d);(2)由s查快表得b和l 如查不到：(a)由s与l比较判断是否越界 不满足：0sl-1，越界；(b)由s和b查段表，得b和l(s,b,l)快表,如快表
11、满淘汰一个；(c)转(2)(3)由d与l比较，判断是否越界 不满足：0dl-1，越界；(4)由bd得物理地址。,段号,段长 段首址,.,.,.,.,l b,s,l,b,b,l,.,.,PCB,段长 段首址,段号,.,l b,.,s,.,.,b:,若快表查不到,段号,段长 段首址,.,.,.,.,l b,s,l,b,b,l,.,.,PCB,段长 段首址,段号,.,l b,.,s,.,.,b:,6.3.3.2 段的共享,段长 段首址,.,l b,.,段号 si.,P1段表：,段长 段首址,.,l b,.,段号 sj.,P2段表：,共享段,.,.,b:,l,内存空间,段名 共享记数 段长 段首址 其
12、它,.,vi 3 35k 125k?,.,共享段表：,进程段表(n)共享段表(1)共享段(1),6.3.3.2 段的保护(1)段表的改进：,段长 段首址,.,l b 1 0 1,段号 s.,访问权限R W E,.,段号 段长 段首址,.,s l b 1 0 1,访问权限R W E,(2)快表的改进：,.,6.3.4 段页式存储管理(segmentation with paging),段式优于页式便于共享和保护页式优于段式消除“碎片”问题段页式：结合二者优点每个进程包含若干段每个段包含若干页,6.3.4.1 基本原理 1.内存空间划分：(同页式)静态等长，2i,称为一页。物理地址=(页架号,页内
13、地址)=(f,d)2.进程空间划分：一个进程若干个段 一个段若干个页 逻辑地址=(段号,逻辑页号,页内地址)=(s,p,d),3.对应关系：,0页,1页,2页,0页,1页,第1段：,0页,1页,2页,第0段：,第2段：,25页,26页,27页,28页,29页,30页,31页,32页,33页,.,.,内存空间,进程空间,4.所需表目(1)段表：每个进程一个,页表首址 页表长度,.,b l,.,段号 0.s.l-1,(2)页表：每个段一个,逻辑页号 0 p l-1,页架号,.,f,.,(3)总页表：系统一个,5.所需寄存器(1)段表基址寄存器：保存正运行程度段表首址；(2)段表限长寄存器：保存正运
14、行程序段表长度。(3)快表：一组联想寄存器(快段表+快页表),段号 逻辑页号 页架号,.,s p f,.,b,l,6.地址映射(P.141):(s,p,d)(f,d)逻辑地址(s,p,d)物理地址(f,d)(1)由程序确定逻辑地址；(2)由(s,p)查快表得f；如找不到：(a)由s与l比较判断是否越界：不满足：0sl-1,越界(b)由s和b查段表得页表(b,l)(c)由p与l比较判断是否越界：不满足：0pl-1,越界(d)由b与p查页表得f(s,p,f)快表，若快表已满，淘汰一个(e)转(2)(3)由f与d合并得物理地址(f,d),6.4 外存资源管理,外存空间划分静态等长，2i,称为一块(b
15、lock)，块是外存分配的基本单位，也是IO传输的基本单位。外存空间分配空闲块链(慢)空闲块表(UNIX)字位映像图,Swap空间,File空间,输入井,输出井,进程与外存对应关系,界地址每进程占一组外存连续块；每进程占二组外存连续块（双对界）。页式内存一页，外存一块。段式每段占外存若干连续块。段页式内存一页，外存一块。,6.5 虚拟存储系统,无虚拟问题不能运行比内存大的程序；进程全部装入内存，浪费空间（进程活动具有局部性)。单控制流的进程需要较少部分在内存；多控制流的进程需要较多部分在内存。虚拟存储进程部分装入内存，部分（或全部）装入外存，运行时访问在外存部分动态调入，内存不够淘汰。,6.5
16、.1 虚拟页式存储系统,基本原理进程运行前：全部装入外存，部分装入内存。进程运行时：访问页不在内存，发生缺页中断，中断处理程序：找到访问页在外存的地址；在内存找一空闲页面；如没有，按淘汰算法淘汰一个；如需要，将淘汰页面写回外存，修改页表和总页表；读入所需页面（切换进程）；重新启动中断指令。,对页表的改进：,对快表的改进：,逻辑页号 p.,.,页架号 外存页号 内外标识 访问权限 修改标志,f p(0,1)r,w,e(0,1),.,.,逻辑页号 页架号 访问权限 修改标志,p f r,w,e(0,1),.,6.5.1.2 内存页面分配策略（静态策略）1.平均分配 如内存128页，进程25个，每个
17、进程5个页面 2.按进程长度比例分配 pi共si个页面；S=si；内存共m个页面 ai=(si/S)m 3.按进程优先级比例分配 4.按进程长度和优先级别比例分配 静态策略没有反映：(1)程序结构；(2)程序在不同时刻的行为特性。,6.5.1.3 外存块的分配策略 1.静态分配 外存保持进程的全部页面：优点：速度快-淘汰时不必写回(未修改情况)缺点：外存浪费 2.动态分配 外存仅保持进程不在内存的页面：优点：节省外存 缺点：速度慢-淘汰时必须写回,6.5.1.4 页面调入时机 1.请调(demand paging)upon page fault,发生缺页中断时调入。2.预调(prepaging
18、)before page fault,将要访问时调入(根据程序顺序行为，不一定准）预调必须辅以请调。,6.5.1.5 淘汰算法(replacement algorithm)用于：页淘汰、段淘汰、快表淘汰。Objective:lowest page-fault rate.1.最佳淘汰算法(OPT-optimal)淘汰将来最长时间以后才用到的。效率最高，not feasible。,2.先进先出(FIFO)淘汰最先调入的。实现：队列 依据:先进入的可能已经使用完毕。negative case:有些代码和数据可能整个程序运行中用到。例子：1，2，3，4，1，2，5，1，2，3，4，5 内存3个物理页面
19、：页故障率=9/12 内存4个物理页面：页故障率=10/12 Belady异常。,3.使用过最久的先淘汰（LRU）淘汰最近一次访问距当前时间最长的。实现：stack例子：4,7,0,7,1,0,1,2,1,2,7,1,2,4.最近不用的先淘汰(not used recently)淘汰最近一段时间未用到的。实现：每页增加一个访问标志，访问置1，定时清0，每页增加一个修改位，修改置1，未修改为0，淘汰时：访问标志=0 修改位=0 访问标志=0 修改位=1 访问标志=1 修改位=0 访问标志=1 修改位=1,5.最不经常使用的先淘汰(LFU)淘汰使用次数最少的。缺点:(1)前期使用多，但以后不用，难
20、换出；(2)刚调入的页面，引用少，被换出可能大。实现：记数器，调入清0，访问增1，淘汰选取最小者。6.最经常使用的先淘汰(MFU)淘汰使用次数最多的。缺点:程序有些成分是在整个程序运行中都使用的。,6.5.1.6 颠簸(thrashing)页面在内存与外存之间频繁换入换出。原因：(1)分给进程物理页架过少；(2)淘汰算法不合理。处理：(1)增加分给进程物理页架数；(2)改进淘汰算法。,6.5.1.7 工作集模型(working set model),工作集(working set):进程在一段时间内所访问页面的集合。,WS(t,)=5,7,1,6,2,2 6 1 5 7 7 7 7 5 1 6
21、 2 2 1 2 3(page reference),t,：称为窗口尺寸(window size)。Denning 认为：为使程序有效运行，工作集应能放入内存。,T,工作集与时间有关：,工作集与窗口尺寸有关：,程序大小,WS,窗口尺寸确定：过小：活动页面不能全部装入，页故障率高；过大：内存浪费。Madnick,Donovan建议：1万次访内。实现：页表中增加访问位：,访问位,页表：,开始时，全部清0,访问：置1,结束时(新开始时)访问标志为1的，为该期间工作集，调整(增加或减少)该进程在内存页面数为该工作集大小。,6.5.1.8 页故障率反馈模型,PFFB(Page Fault Feed Ba
22、ck)页故障率高(达到某上界阈值)：内存页面少，增加。页故障率低(达到某下界阈值)：内存页面多，减少。,6.5.2 虚拟段式存储系统,段号 段长 内存首址 访问权限 修改标志,6.5.2.2 段的动态连接(dynamic linking),动态连接 vs.静态连接静态连接：运行前连接，由link完成；动态连接：运行时连接，由OS完成.静态连接的缺点连接时间长；目标代码长；连接段可能并不执行(未用到)。,动态连接的实现(Multics为例)段名-段号对照表：每进程一个,符号名 段内位移,func 150,.,.,符号表：每段一个,段形式：,符号表,目标代码或者数据,(1)编译(汇编)时：遇到访问
23、外段指令，采用间接寻址，指向一个间接字：,L,D,(2)执行时：遇到间接指令，且L=1,发生链接中断，处理程序：(a)由D取出符号地址；(b)由段名查段名-段号对照表，是否分配段号。,已分配段号：取出该段号，找到该段(内存或外存)由入口名查符号表得段内地址；(段号，段内地址)D,0 L 未分配段号：读入内存，读入外存，分配段号，填写段表，填写段名-段号对照表，转(b),例子：汇编前：,.Load 1,X|Load 2,X|.,W段,X段,12345678.,Y:,Z:,汇编后，连接前：,100:,Load*1,2|100;Load*2,2|150;“7X|”.“7X|”,1 2 250,150
24、:,200:,250:,W段（段号=2),X段,300 40012345678,300,400,段表,段首址,.,段号 0 1 2 3.,Main 0,A 1,W 2,段名-段号对照表,第一次连接后：,100:,Load*1,2|100;Load*2,2|150;“7X|”.“7X|”,1 2 250,150:,200:,250:,W段（段号=2),X段,300 40012345678,300,400,段表,段首址,.,段号 0 1 2 3.,Main 0,A 1,W 2,段名-段号对照表,X 3,100:,Load*1,2|100;Load*2,2|150;“7X|”.“7X|”,0 3 4
25、00,150:,200:,250:,W段（段号=2),X段,300 40012345678,300,400,段表,段首址,.,段号 0 1 2 3.,Main 0,A 1,W 2,段名-段号对照表,X 3,第二次连接后：,动态连接问题,动态连接与共享的矛盾动态连接：修改连接字（代码）段的共享：要求纯代码（pure code)解决方法共享代码分为“纯段”和“杂段”纯段共享，杂段私用。,6.5.3 虚拟段页式存储系统,考虑段的动态连接段的共享段长度的动态变化,所需表目：,(1)段表：每进程一个,段号,(2)页表：每段一个,逻辑页号,(3)共享段表：系统一个,段名 页表长度 页表首址 扩充标志 共享
26、计数,(4)段名-段号对照表：每进程一个对应关系：,共享段表,P1段表：,P2段表：,15,16,17,18,19,20,21,22,23,24,25,.,.,页表,页表,存储空间：,si,sj,sk,所需寄存器：(1)段表长度寄存器：保存正运行进程段表长度(2)段表首址寄存器：保存正运行进程段表首址(3)快表,地址映射：,:(s,p,d)(f,d)逻辑地址(s,p,d)物理地址(f,d),由(s,p)查快表得f,查到,访问合法,形成物理地址(f,d),是间址,有障碍位,继续,0sl-1,0pl-1,由(s,b)查段表得b,l,越界中断,越界中断,由b和p查页表得f,该页在内存,缺页中断,(s
27、,p,f)快表,越权中断,T,F,T,F,连接中断,T,F,T,F,T,F,T,F,T,中断处理：1.连接中断(1)所有进程均未连接(共享段表、段名-段号对照表均无)建立页表，由文件读入外存swap，部分页读入内存，分配 段号，填段名-段号对照表，如是共享段填共享段表，填段 表，形成逻辑地址。(2)其它进程连接过，本进程未连接过(共享段表有，段名-段 号对照表无)分配段号，填段名-段号对照表，填段表(指向共享段表)，共享记数加1,形成逻辑地址。(3)本进程连接过(段名-段号对照表有，共享段表有或无)形成逻辑地址。,2.缺页中断 调入所需页面，更新页表和总页表。3.越界中断(1)段号越界：错误处理。(2)页号越界：如可扩展，扩展该段(增加页)，修改页表和段 表(页表长);如不可扩展，错误处理。4.越权中断 错误处理。,
