1、第四章 存储管理之段页式管理,4.2 分区存储管理4.3 页式存储管理4.4 段式存储管理4.5 段页式存储管理4.6 交换技术与覆盖技术4.7 虚拟存储,4.3 页式存储管理,为什么要引进分页技术?分区式存储管理：程序要求连续存放，会产生碎片问题。大程序进入时需要移动已在主存中的信息。分页式存储管理允许把一个作业存放到若干不相邻接的分区中免去移动信息充分利用主存空间,1. 用户程序划分,把用户程序按逻辑页划分成大小相等的部分，称为页。从0开始编制页号，页内地址是相对于0编址,逻辑地址,用户程序的划分是由系统自动完成的，对用户是透明的。一般，一页的大小为2的整数次幂，因此，地址的高位部分为页号
2、，低位部分为页内地址,0,11,12,31,页号P,页内位移量W,编号01048575,相对地址04095,逻辑地址：一维,内存空间：,按页的大小划分为大小相等的区域，称为内存块（物理页面，页框）,内存分配：,以页为单位进行分配，并按作业的页数多少来分配。逻辑上相邻的页，物理上不一定相邻,4.3 .3管理,1.页表：系统为每个进程建立一个页表，页表给出逻辑页号和具体内存块号相应的关系 页表放在内存，属于进程的现场信息2.空块管理位示图3.内存的分配与回收,0,31,0/1,0/1,0/1,0/1,0/1,0,1,7,空闲块数,空块管理位示图,计算一个作业所需要的总块数N查位示图，看看是否还有N
3、个空闲块如果有足够的空闲块，则页表长度设为N，可填入PCB中；申请页表区，把页表始址填入PCB依次分配N个空闲块，将块号和页号填入页表修改位示图,4.3.4 硬件支持,1系统设置一对寄存器： 页表始址寄存器 页表长度寄存器2相联存储器快表 快表表项： 页号；内存块号；标识位；淘汰位,1. 基本的地址变换机构,图 4-12 分页系统的地址变换机构,p,页表,地址越界,L,比较,P=L,p,p,.,.,.,快表,b,+,页号p 页内地址d,P,d,物理地址,页表地址寄存器,页表长度寄存器,逻辑地址,快表地址映射机制,存在的问题,当读/写数据时，必须访问两次主存。第一次按页号读出页表中相应栏内容的块
4、号第二次根据计算出来的绝对地址进行读/写解决方法：利用高速缓存,假定访问主存时间为100毫微秒，访问相联存储器时间为20毫微秒，相联存储器为32个单元时快表命中率可达90%，按逻辑地址存取的平均时间为：（10020）90%(100+100+20)(1-90%)130毫微秒 比两次访问主存的时间100毫微秒2+20220毫微秒下降了四成多。,4.3.5 页式管理的优缺点,优点：解决了碎片问题 便于管理缺点：不易实现共享 不便于动态连接思考：页的共享？页的保护？,4.3.3 两级和多级页表,逻辑地址空间(232264)。页表就变得非常大，要占用相当大的连续的内存空间。 eg: 32位逻辑地址空间的
5、分页系统，规定页面大小为4 KB即212 B，则在每个进程页表中的页表项可达1兆个之多。解决办法： 1、 采用离散分配方式。解决难以找到一块连续的大内存空间的问题； 2、只将当前需要的部分页表项调入内存， 其余的页表项仍驻留在磁盘上，需要时再调入。,1. 两级页表(Two-Level Page Table),逻辑地址结构可描述如下：,为了解决页表需要连续存储空间的问题，将页表离散的放入内存，然后建立一个页表的页表（连续存储在外存中），用以标识页表放在内存中的位置。 同时逻辑地址也变成了如上的表示（一维）,图 4-14 两级页表结构,图 4-15 具有两级页表的地址变换机构,页目录地址,目录位移
6、,页表位移,页位移,虚拟地址,页表地址,.,页目录（每进程一个）,块号,.,页表,代码或数据,.,内存块,二级页表结构及地址映射,+,+,4.4.1基本思想 一个程序的各个段离散存放 段式存储管理 单个段的存储基于可变分区存储管理 实现，占据连续的内存存储空间 段页式存储管理 单个段的存储基于页式存储管理实现,4.4分段式存储管理,0,116,N,操作系统,用户程序划分,按程序自身的逻辑关系划分为若干个程序段，每个程序段都有一个段名，且有一个段号。段号从0开始，每一段也从0开始编址，段内地址是连续的,逻辑地址,内存划分 内存空间被动态的划分为若干个长度不相同的区域，这些区域被称为物理段，每个物
7、理段由起始地址和长度确定,内存分配,以段为单位分配内存，每一个段在内存中占据连续空间（内存随机分割，需要多少分配多少），但各段之间可以不连续存放,4.4.2 管理,段表： 它记录了段号，段的首（地）址和长度之间的关系 每一个程序设置一个段表，放在内存 属于进程的现场信息,空闲块管理：,记录了空闲区起始地址和长度内存的分配算法： 首先适配；最佳适配；最坏适配,4.4.3 硬件支持,系统设置一对寄存器段表始址寄存器：用于保存正在运行进程的段表的始址段表长度寄存器： 用于保存正在运行进程的段表的长度（例如上图的段表长度为3）,Cl,Cb,+,段号S 段内地址d,比较,比较,b + d,段表,S= C
8、l,快表,物理地址,段表始址寄存器,段表长度寄存器,逻辑地址,l,b,.,.,.,S,l,b,地址越界,d=1,d=1,地址映射及存储保护机制,地址越界,地址越界,比较,L:为段长，注意与分页的区别,介于内存与寄存器之间的存储机制，它又叫快表用途：保存正在运行进程的段表的子集（部分表项）特点：按内容并行查找,相联（联想）存储器（associative memory） TLB（Translation lookaside buffers）,引入快表的作用： 为了提高地址映射速度,快表项目：段号；段始址；段长度；标识（状态）位；访问位（淘汰位）快表淘汰问题？（淘汰机制）,4.4.3 信息共享,图 4
9、-18 分页系统中共享editor的示意图,图 4-19 分段系统中共享editor的示意图,优点： 便于动态申请内存 管理和使用统一化 便于共享 便于动态链接缺点：产生碎片思考：与可变分区存储管理方案的相同点与不同点？,4.4.4段页式存储管理,1。产生背景及基本思想 背景：结合了二者优点 克服了二者的缺点,基本思想：,用户程序划分：按段式划分（对用户来讲，按段的逻辑关系进行划分；对系统讲，按页划分每一段）逻辑地址：内存划分：按页式存储管理方案内存分配：以页为单位进行分配,段页式存储方式的 管理,1.段表：记录了每一段的页表始址和页表长度2.页表：记录了逻辑页号与内存块号的对应关系（每一段有
10、一个，一个程序可能有多个页表）3.空块管理：同页式管理4.分配：同页式管理,图 4-21 利用段表和页表实现地址映射,2. 地址变换过程,图 4-22 段页式系统中的地址变换机构,4.5 虚拟存储技术,计算机系统资源管理策略： 内存比较昂贵，同时资源有限； 外存较大，价格便宜； 以CPU时间和外存空间换取昂贵内存空间，这是操作系统中的资源转换技术,1. 常规存储器管理方式的特征,一次性。作业在运行时全部一次装入。 (2) 驻留性。作业装入内存后，直至作业结束才完全撤出。,4.5.1 概述,1、问题的提出 程序大于内存 程序暂时不执行或运行完是否还要占用内存 虚拟存储器的基本思想是：程序、数据、
11、堆栈的大小可以超过内存的大小，操作系统把程序当前使用的部分保留在内存，而把其它部分保存在磁盘上，并在需要时在内存和磁盘之间动态交换。 虚拟存储器支持多道程序设计技术,2、程序局部性原理 在一段时间内一个程序的执行往往呈现出高度的局部性，表现在时间与空间两方面时间局部性： 一条指令被执行了，则在不久的将来它可能再被执行空间局部性： 若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被使用,3、虚拟存储技术,虚存：把内存与外存有机的结合起来使用，从而得到一个容量很大的“内存”，这就是虚存 实现思想：当进程运行时，先将一部分程序装入内存，另一部分暂时留在外存，当要执行的指令不在内存时，
12、由系统自动完成将它们从外存调入内存工作 目的： 提高内存利用率。,4.5.3 虚拟存储器的特征,多次性一个作业分多次调入内存执行 对换性进程运行期间允许程序和数据换进、换出。3. 虚拟性 从逻辑上对内存进行扩充，允许运行比内存大的程序,4.6虚拟页式存储管理(请求分页式),1、基本工作原理 在进程开始运行之前，不是装入全部页面，而是装入一个或零个页面，之后根据进程运行的需要，动态装入其它页面；当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面,2、页表表项（有可能在外存上，故如下）,页号、驻留位、内存块号、外存地址、访问位、修改位驻留位（中断位）：表示该页是在
13、内存还是在外存访问位：根据访问位来决定淘汰哪页（由不同的算法决定）修改位：查看此页是否在内存中被修改过,3、缺页中断（Page Fault）,在地址映射过程中，在页表中发现所要访问的页不在内存，则产生缺页中断。操作系统接到此中断信号后，就调出缺页中断处理程序，根据页表中给出的外存地址，将该页调入内存，使作业继续运行下去如果内存中有空闲块，则分配一页，将新调入页装入内存，并修改页表中相应页表项目的驻留位及相应的内存块号若此时内存中没有空闲块，则要淘汰某页，若该页在内存期间被修改过，则要将其写回外存,与一般中断机制的区别;(1)指令执行期间产生和处理中断信号。 因为在执行期间发现缺少某页。（2）一
14、条指令期间可能需要多次中断才能完成任务。 因为一条指令需要的数据或指令可能跨越多个页面。,3. 地址变换机构,图 4-24 请求分页中的地址变换过程,4.6.2 内存分配策略和分配算法,1. 最小物理块数的确定,保证进程正常运行所需的最小物理块数。当系统为进程分配的物理块数少于此值时，进程将无法运行。 （1）若是单地址指令且采用直接寻址方式，则所需的最少物理块数为2。一块是用于存放指令的页面，另一块则是用于存放数据的页面。 （2）如果该机器允许间接寻址时，则至少要求有三个物理块。 （3） 对于某些功能较强的机器， 其指令长度可能是两个或多于两个字节，因而其指令本身有可能跨两个页面，且源地址和目
15、标地址所涉及的区域也都可能跨两个页面。,2. 物理块的分配策略,1) 固定分配局部置换(Fixed Allocation, Local Replacement) 为某个进程分配固定页面数，其间不能改变。需要置换时候只能置换自己的。 2) 可变分配全局置换(Variable Allocation,lobalReplacement) 先为进程一定的内存页面，如果在需要责从空闲块中选择相应的页面分配给它。 3) 可变分配局部置换(Variable Allocation, Local Replacemen 初始分配同上，但是如果发生缺页，必须置换自己的页面。如果缺页率过高，os再为其分配一定的页面数目
16、。,3. 物理块分配算法,1) 平均分配算法 这是将系统中所有可供分配的物理块，平均分配给各个进程。 例如，当系统中有100个物理块，有5个进程在运行时，每个进程可分得20个物理块。这种方式貌似公平，但实际上是不公平的，因为它未考虑到各进程本身的大小。如有一个进程其大小为200页，只分配给它20个块，这样，它必然会有很高的缺页率；而另一个进程只有10页，却有10个物理块闲置未用。,2) 按比例分配算法 这是根据进程的大小按比例分配物理块的算法。如果系统中共有n个进程，每个进程的页面数为Si，则系统中各进程页面数的总和为：又假定系统中可用的物理块总数为m，则每个进程所能分到的物理块数为bi，将有
17、：b应该取整，它必须大于最小物理块数。,3) 考虑优先权的分配算法 在实际应用中，为了照顾到重要的、紧迫的作业能尽快地完成， 应为它分配较多的内存空间。通常采取的方法是把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程。在有的系统中，如重要的实时控制系统，则可能是完全按优先权来为各进程分配其物理块的。,4.6.3 调页策略,1. 何时调入页面,预调页策略 一次调入进程的多个相邻的多个页面，这样可以降低每次缺页都要进行调入的开销。可以采用预测机制进行处理。 2) 请求调页策略 发生缺页时才将缺页调入内存中。在目前
18、的虚拟存储中基本采用此种方法进行。,2. 从何处调入页面,外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。对换区是采用连续分配方式，故对换区的磁盘I/O速度比文件区的高。这样，每当发生缺页请求时，系统应从何处将缺页调入内存，可分成如下三种情况： (1) 系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以提高调页速度。为此，在进程运行前， 便须将与该进程有关的文件，从文件区拷贝到对换区。,(2) 系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；而当换出这些页面时，由于它们未被修改而不必再将它们换出，以后再调入时，仍从文件区直接调入。但对于那些可
19、能被修改的部分，在将它们换出时，便须调到对换区，以后需要时，再从对换区调入。 (3) UNIX方式。由于与进程有关的文件都放在文件区，故凡是未运行过的页面，都应从文件区调入。而对于曾经运行过但又被换出的页面，由于是被放在对换区，因此在下次调入时，应从对换区调入。由于UNIX系统允许页面共享，因此， 某进程所请求的页面有可能已被其它进程调入内存，此时也就无须再从对换区调入。,3. 页面调入过程 (1)向CPU发出缺页中断，保留CPU环境，分析中断原因后， 转入缺页中断处理程序。 (2)查找页表，得到该页在外存的物理块后， 如果此时内存能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。
20、 （3）如果内存已满，则须先按照某种置换算法从内存中选出一页准备换出；,（4）检查该页是否被修改。 a.如果该页未被修改过，可不必将该页写回磁盘； b.如果此页已被修改， 则必须将它写回磁盘，然后再把所缺的页调入内存。 (5)修改页表中的相应表项，置其存在位为“1”，并将此页表项写入快表中。 (6)在缺页调入内存后，利用修改后的页表， 去形成所要访问数据的物理地址，再去访问内存数据。,4.7页面淘汰算法,1、最佳页面淘汰算法（OPT） 淘汰以后不再需要的或最远的将来才会用到的页面（理论上可行，实际上不可行） 2、最近最久未使用（LRU） 在最近的一段时间之内一直没有被访问的页面，我们可以认为该
21、页面在将来可能页不会被访问，所以淘汰掉。 即淘汰没有使用的时间最长的页。,3、先进先出页面淘汰算法（FIFO） 选择在内存中驻留时间最长的页并淘汰之 4、第二次机会淘汰算法 (NUR) 按照先进先出算法选择某一页面，检查其访问位，如果为0，则淘汰该页，如果为1，则给第二次机会，并将访问位置0。 该算法要求在访问某页面时将其访问位置1,1、OPT页面置换算法 假定系统为某进程分配了三个物理块， 并考虑有以下的页面号引用串： 7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1 进程运行时， 先将7，0，1三个页面装入内存。 以后， 当进程要访问页面2时， 将会产生缺页中
22、断。此时OS根据最佳置换算法， 将选择页面7予以淘汰。,时刻,P,M,F,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,0,7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1,7,0,7,1,0,7,2,1,0,f,f,f,f,v,2,1,0,2,3,0,2,3,0,v,2,3,4,2,3,4,2,f,V,V,f,3,4,2,3,0,f,2,3,0,v,2,3,0,v,2,1,0,f,2,1,0,v,2,1,0,V,2,1,0,v,7,1,0,f,7,1,0,v,7,1,0,v,缺页率 =9/20=45%,2. 先进
23、先出(FIFO)页面置换算法,图 4-26 利用FIFO置换算法时的置换图,时刻,P,M,F,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,0,7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1,7,0,7,1,0,7,2,1,0,f,f,f,f,v,2,1,0,3,2,1,0,3,2,f,4,0,3,2,4,0,3,f,f,f,f,2,4,0,3,2,f,0,3,2,v,0,3,2,v,1,0,3,f,2,1,0,f,2,1,0,v,2,1,0,v,7,2,1,f,0,7,2,f,1,0,7,f,缺页率 =15/2
24、0=75%,2. 先进先出(FIFO)页面置换算法,时刻,P,M,F,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,0,7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1,7,0,7,1,0,7,2,1,0,f,f,f,f,v,2,1,0,2,3,0,2,3,0,v,4,3,0,4,2,0,4,f,f,f,f,2,3,0,2,3,f,0,2,3,v,0,2,3,v,1,2,3,f,1,2,3,v,1,2,0,f,1,2,0,v,1,7,0,f,1,7,0,v,1,7,0,v,缺页率 =12/20=60%,3. LRU
25、(Least Recently Used)置换算法的描述,例：计算缺页次数,某程序在内存中分配三个页面，初始为空，页面走向为4，3，2，1，4，3，5，4，3，2，1，5,FIFO 4 3 2 1 4 3 5 4 3 2 1 5页1 4 3 2 1 4 3 5 5 5 2 1 1页2 4 3 2 1 4 3 3 3 5 2 2页3 4 3 2 1 4 4 4 3 5 5 x x x x x x x x x 共缺页中断9次,LRU 4 3 2 1 4 3 5 4 3 2 1 5页1 4 3 2 1 4 3 5 4 3 2 1 5页2 4 3 2 1 4 3 5 4 3 2 1页3 4 3 2 1
26、 4 3 5 4 3 2 x x x x x x x x x x共缺页中断10次,OPT 4 3 2 1 4 3 5 4 3 2 1 5页1 4 3 2 1 1 1 5 5 5 2 1 1页2 4 3 3 3 3 3 3 3 5 5 5页3 4 4 4 4 4 4 4 4 4 4 x x x x x x x 共缺页中断7次,最佳页面算法（OPT）,LRU置换算法的硬件支持,1) 寄存器 为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为,R=Rn-1Rn-2Rn-3 R2R1R0,进程访问某物理块时，要将相应的寄存器r位置为1。定时信号将每隔一段时间将寄存
27、器右移1位，将n位寄存器看作一个整数，那么，具有最小数值的寄存器所对应的页面，就是最近最久未使用页面。 如下图所示：,图 4-28 某进程具有8个页面时的LRU访问情况,2) 栈,图 4-29 用栈保存当前使用页面时栈的变化情况,保存当前使用的各个页面的页面号，当进程访问某个页面时，便将该页面的页面号从栈中取出，将其压入栈顶。因此栈顶永远是最近使用的页面，而栈底则是最近最久没有被访问的页面。,4 、 Clock置换算法 （NUR）,1. 简单的Clock置换算法,图 4-30 简单Clock置换算法的流程和示例,注：页面被访问时，其访问位被置为1,2. 改进型Clock置换算法,由访问位A和修
28、改位M可以组合成下面四种类型的页面： 1类(A=0, M=0): 表示该页最近既未被访问， 又未被修改， 是最佳淘汰页。 2类(A=0, M=1)： 表示该页最近未被访问， 但已被修改， 并不是很好的淘汰页。 3类(A=1, M=0)： 最近已被访问， 但未被修改， 该页有可能再被访问。 4类(A=1, M=1): 最近已被访问且被修改， 该页可能再被访问。,(1) 从指针所指示的当前位置开始， 扫描循环队列， 寻找A=0且M=0的第一类页面， 将所遇到的第一个页面作为所选中的淘汰页。 在第一次扫描期间不改变访问位A。 (2) 如果第一步失败，即查找一周后未遇到第一类页面， 则开始第二轮扫描，
29、寻找A=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置0。,(3) 如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复0。 然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。,4.7.4 其它置换算法,最少使用(LFU： Least Frequently Used)置换算法2. 页面缓冲算法(PBA： Page Buffering Algorithm) ,4.8 虚拟段式存储管理（请求分段式）,1、段表机制 增加：存在位（在/不在内存，是否可共享），存取方式位（读，写，执行
30、），修改位（是否修改过，能否移动），增补位（固定长/可扩充 ）， 访问字段a:纪录该段被访问的频繁度； 外存始址：本段在外存中的起始地址，即起始盘块号。,2、越界中断处理 进程在执行过程中，有时需要扩大分段，如数据段。由于要访问的地址超出原有的段长，所以发越界中断。操作系统处理中断时 ，首先判断该段的“扩充位”，如可扩充，则增加段的长度；否则按出错处理,3、缺段中断处理 检查内存中是否有足够的空闲空间 若有，则装入该段，修改有关数据结构，中断返回 若没有，检查内存中空闲区的总和是否满足要求，是则应采用紧缩技术，转 ；否则，淘汰一（些）段，转,2. 缺段中断机构,图 4-31 请求分段系统中的中
31、断处理过程,分段式虚拟存储管理,3. 地址变换机构,图 4-32 请求分段系统的地址变换过程,4.8.2 分段的共享与保护,1. 共享段表,图 4-33 共享段表项,另外单独设置一个共享段表，所有共享段都在里面有一个表项。记录项目如下：,共享进程计数：记录有多少个进程在使用该段。控制存取字段：设置使用该段的权限，“写”、“读”等段号：允许不同的进程使用不同的段号来访问相同的段。,2. 共享段的分配与回收,1) 共享段的分配 在为共享段分配内存时，对第一个请求使用该共享段的进程，由系统为该共享段分配一物理区，再把共享段调入该区，同时将该区的始址填入请求进程的段表的相应项中，还须在共享段表中增加一
32、表项，填写有关数据，把count置为1；之后，当又有其它进程需要调用该共享段时，由于该共享段已被调入内存，故此时无须再为该段分配内存，而只需在调用进程的段表中，增加一表项，填写该共享段的物理地址；在共享段的段表中，填上调用进程的进程名、存取控制等，再执行count=count+1操作，以表明有两个进程共享该段。,2) 共享段的回收 当共享此段的某进程不再需要该段时，应将该段释放， 包括撤在该进程段表中共享段所对应的表项，以及执行count=count-1操作。若结果为0，则须由系统回收该共享段的物理内存，以及取消在共享段表中该段所对应的表项， 表明此时已没有进程使用该段；否则(减1结果不为0)
33、， 则只是取消调用者进程在共享段表中的有关记录。,3. 分段保护,越界检查 ：检查段号与段表长度，段内地址与段长的比较。2) 存取控制检查 ：设定存取权限只读 (2) 只执行 (3) 读/写 3) 环保护机构 划分程序优先级，内环优先级高，外环优先级第，编号由内向外编号。调用和访问方式如下图所示:,图 4-34 环保护机构,2、分区式存储管理 a. 固定式分区管理； b. 可变式分区管理。,3、页式存储管理 a. 页式管理（作业表，页表） b. 请求页式管理（作业表，扩充页表。缺页率）,4、段式与段页式存储管理 a. 段式管理（段表）； b. 段页式管理（段表、页表）。,小结,1、单一连续存储,谢 谢 大 家,
