存储管理之段页式管理课件

第四章存储管理之段页式管理4.2分区存储管理4.3页式存储管理4.4段式存储管理4.5段页式存储管理4.6交换技术与覆盖技术4.7虚拟存储第四章存储管理之段页式管理

4.3页式存储管理

为什么要引进分页技术?分区式存储管理：程序要求连续存放，会产生碎片问题。大程序进入时需要移动已在主存中的信息。分页式存储管理允许把一个作业存放到若干不相邻接的分区中免去移动信息充分利用主存空间4.3页式存储管理为什么要引进分页技术?21.用户程序划分把用户程序按逻辑页划分成大小相等的部分，称为页。从0开始编制页号，页内地址是相对于0编址1.用户程序划分把用户程序按逻辑页划分成大小相等的部逻辑地址用户程序的划分是由系统自动完成的，对用户是透明的。一般，一页的大小为2的整数次幂，因此，地址的高位部分为页号，低位部分为页内地址页号页内地址逻辑地址用户程序的划分是由系统自动完成的，对用户是透明0111231页号P页内位移量W编号0~1048575相对地址0~4095逻辑地址：一维0111231页号P页内位移量W编号0~1048575相对地内存空间：按页的大小划分为大小相等的区域，称为内存块（物理页面，页框）内存分配：以页为单位进行分配，并按作业的页数多少来分配。逻辑上相邻的页，物理上不一定相邻内存空间：按页的大小划分为大小相等的区域，称为内存块（...01234560123456作业的地址空间页框（物理块）页号页表主存中页框（物理块）..........01234560123456作业的页框页号页表主存中页4.3.3管理1.页表：系统为每个进程建立一个页表，页表给出逻辑页号和具体内存块号相应的关系页表放在内存，属于进程的现场信息2.空块管理——位示图3.内存的分配与回收4.3.3管理1.页表：系统为每个进程建立一个页表，页表给0310/10/10/10/10/1017……空闲块数……空块管理——位示图0310/10/10/10/10/1017……空闲块数……空计算一个作业所需要的总块数N查位示图，看看是否还有N个空闲块如果有足够的空闲块，则页表长度设为N，可填入PCB中；申请页表区，把页表始址填入PCB依次分配N个空闲块，将块号和页号填入页表修改位示图计算一个作业所需要的总块数N4.3.4硬件支持1．系统设置一对寄存器：

页表始址寄存器页表长度寄存器2．相联存储器——快表快表表项：页号；内存块号；标识位；淘汰位4.3.4硬件支持1．系统设置一对寄存器：1.基本的地址变换机构图4-12分页系统的地址变换机构1.基本的地址变换机构图4-12分页系统的地址变换机p’页表地址越界L比较P>=Lpp’...快表

b+页号p页内地址dP’d物理地址页表地址寄存器页表长度寄存器逻辑地址快表地址映射机制页表地址越界L比较P>=Lpp’...快表b+页号p页存在的问题当读/写数据时，必须访问两次主存。第一次按页号读出页表中相应栏内容的块号第二次根据计算出来的绝对地址进行读/写解决方法：利用高速缓存存在的问题当读/写数据时，必须访问两次主存。14假定访问主存时间为100毫微秒，访问相联存储器时间为20毫微秒，相联存储器为32个单元时快表命中率可达90%，按逻辑地址存取的平均时间为：（100＋20）×90%＋(100+100+20)×(1-90%)＝130毫微秒比两次访问主存的时间100毫微秒×2+20＝220毫微秒下降了四成多。假定访问主存时间为100毫微秒，访问相联存储器时间为154.3.5页式管理的优缺点优点：解决了碎片问题便于管理缺点：不易实现共享不便于动态连接思考：页的共享？页的保护？4.3.5页式管理的优缺点优点：解决了碎片问题4.3.3两级和多级页表

逻辑地址空间(232~264)。页表就变得非常大，要占用相当大的连续的内存空间。

eg:32位逻辑地址空间的分页系统，规定页面大小为4KB即212B，则在每个进程页表中的页表项可达1兆个之多。解决办法：1、采用离散分配方式。解决难以找到一块连续的大内存空间的问题；

2、只将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入。4.3.3两级和多级页表逻辑地址空间(21.两级页表(Two-LevelPageTable)逻辑地址结构可描述如下：

为了解决页表需要连续存储空间的问题，将页表离散的放入内存，然后建立一个页表的页表（连续存储在外存中），用以标识页表放在内存中的位置。同时逻辑地址也变成了如上的表示（一维）1.两级页表(Two-LevelPageTable)图4-14两级页表结构图4-14两级页表结构图4-15具有两级页表的地址变换机构图4-15具有两级页表的地址变换机构页目录地址目录位移页表位移页位移虚拟地址页表地址...页目录（每进程一个）块号...页表代码或数据...内存块二级页表结构及地址映射++页目录地址目录位移页表位移页位移虚拟地址页表地址.页目录（每段号单元号4.4.1基本思想一个程序的各个段离散存放段式存储管理单个段的存储基于可变分区存储管理实现，占据连续的内存存储空间段页式存储管理单个段的存储基于页式存储管理实现4.4分段式存储管理段号单元号4.4.1基本思想4.4分段式存储管理...0S工作区段[B]主程序段[M]......0EP子程序段[X]0K...CALL[X][E].........CALL[Y][F]CALL[A]116......0FL子程序段[Y]0116N数组[A]12345......0S工作区段[B]主程序段[M]0EP子程操作系统.....B0SA0NY0LX0PM0K逻辑段号01234作业1的地址空间10003200500060008000PKSLN主存K3200P1500L6000N8000S5000长度段地址01234操作系统操作系统B0SA0NY0LX0PM0K逻辑段号01用户程序划分按程序自身的逻辑关系划分为若干个程序段，每个程序段都有一个段名，且有一个段号。段号从0开始，每一段也从0开始编址，段内地址是连续的用户程序划分按程序自身的逻辑关系划分为若干个程序段，每个逻辑地址内存划分内存空间被动态的划分为若干个长度不相同的区域，这些区域被称为物理段，每个物理段由起始地址和长度确定段号段内地址逻辑地址内存划分段号段内地址内存分配以段为单位分配内存，每一个段在内存中占据连续空间（内存随机分割，需要多少分配多少），但各段之间可以不连续存放内存分配以段为单位分配内存，每一个段在内存中占据连续空间4.4.2管理段表：它记录了段号，段的首（地）址和长度之间的关系每一个程序设置一个段表，放在内存属于进程的现场信息段号012段首址段长度58K20K100K110K260K140K4.4.2管理段表：段号012段首址段长度58K20K10空闲块管理：记录了空闲区起始地址和长度内存的分配算法：首先适配；最佳适配；最坏适配空闲块管理：记录了空闲区起始地址和长度4.4.3硬件支持系统设置一对寄存器段表始址寄存器：用于保存正在运行进程的段表的始址段表长度寄存器：用于保存正在运行进程的段表的长度（例如上图的段表长度为3）4.4.3硬件支持系统设置一对寄存器

Cl

Cb+段号S段内地址d比较比较b+d段表S>=Cl快表物理地址段表始址寄存器段表长度寄存器逻辑地址lb...Slb地址越界d>=1d>=1地址映射及存储保护机制地址越界地址越界比较L:为段长，注意与分页的区别ClCb+段号S段内地址d比较比较b+d段介于内存与寄存器之间的存储机制，它又叫快表用途：保存正在运行进程的段表的子集（部分表项）特点：按内容并行查找相联（联想）存储器（associativememory）

TLB（Translationlookasidebuffers）介于内存与寄存器之间的存储机制，它又叫快表相联（联想）引入快表的作用：

为了提高地址映射速度快表项目：段号；段始址；段长度；标识（状态）位；访问位（淘汰位）快表淘汰问题？（淘汰机制）引入快表的作用：

为了提高地址映射速度4.4.3信息共享图4-18分页系统中共享editor的示意图4.4.3信息共享图4-18分页系统中共享edit图4-19分段系统中共享editor的示意图图4-19分段系统中共享editor的示意图优点：便于动态申请内存管理和使用统一化便于共享便于动态链接缺点：产生碎片思考：与可变分区存储管理方案的相同点与不同点？优点：4.4.4段页式存储管理1。产生背景及基本思想背景：结合了二者优点克服了二者的缺点4.4.4段页式存储管理1。产生背景及基本思想基本思想：用户程序划分：按段式划分（对用户来讲，按段的逻辑关系进行划分；对系统讲，按页划分每一段）逻辑地址：内存划分：按页式存储管理方案内存分配：以页为单位进行分配段号段内地址页号页内地址基本思想：用户程序划分：按段式划分（对用户来讲，按段的段页式存储方式的管理1.段表：记录了每一段的页表始址和页表长度2.页表：记录了逻辑页号与内存块号的对应关系（每一段有一个，一个程序可能有多个页表）3.空块管理：同页式管理4.分配：同页式管理段页式存储方式的管理1.段表：记录了每一段的页表始址和页表图4-21利用段表和页表实现地址映射图4-21利用段表和页表实现地址映射2.地址变换过程图4-22段页式系统中的地址变换机构2.地址变换过程图4-22段页式系统中的地址变换机构4.5虚拟存储技术计算机系统资源管理策略：内存比较昂贵，同时资源有限；外存较大，价格便宜；以CPU时间和外存空间换取昂贵内存空间，这是操作系统中的资源转换技术4.5虚拟存储技术计算机系统资源管理策略：1.常规存储器管理方式的特征一次性。作业在运行时全部一次装入。

(2)驻留性。作业装入内存后，直至作业结束才完全撤出。1.常规存储器管理方式的特征一次性。作业在运行时全部一4.5.1概述1、问题的提出程序大于内存程序暂时不执行或运行完是否还要占用内存

虚拟存储器的基本思想是：程序、数据、堆栈的大小可以超过内存的大小，操作系统把程序当前使用的部分保留在内存，而把其它部分保存在磁盘上，并在需要时在内存和磁盘之间动态交换。虚拟存储器支持多道程序设计技术4.5.1概述1、问题的提出2、程序局部性原理

在一段时间内一个程序的执行往往呈现出高度的局部性，表现在时间与空间两方面时间局部性：一条指令被执行了，则在不久的将来它可能再被执行空间局部性：若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被使用2、程序局部性原理3、虚拟存储技术虚存：把内存与外存有机的结合起来使用，从而得到一个容量很大的“内存”，这就是虚存实现思想：当进程运行时，先将一部分程序装入内存，另一部分暂时留在外存，当要执行的指令不在内存时，由系统自动完成将它们从外存调入内存工作目的：提高内存利用率。3、虚拟存储技术虚存：把内存与外存有机4.5.3虚拟存储器的特征多次性一个作业分多次调入内存执行对换性进程运行期间允许程序和数据换进、换出。3.虚拟性从逻辑上对内存进行扩充，允许运行比内存大的程序4.5.3虚拟存储器的特征多次性4.6虚拟页式存储管理(请求分页式)1、基本工作原理

在进程开始运行之前，不是装入全部页面，而是装入一个或零个页面，之后根据进程运行的需要，动态装入其它页面；当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面4.6虚拟页式存储管理(请求分页式)1、基本工作原理2、页表表项（有可能在外存上，故如下）页号、驻留位、内存块号、外存地址、访问位、修改位 驻留位（中断位）：表示该页是在内存还是在外存访问位：根据访问位来决定淘汰哪页（由不同的算法决定）修改位：查看此页是否在内存中被修改过页号中断位内存块号外存地址访问位修改位2、页表表项（有可能在外存上，故如下）页号、驻留位、内存块号3、缺页中断（PageFault）在地址映射过程中，在页表中发现所要访问的页不在内存，则产生缺页中断。操作系统接到此中断信号后，就调出缺页中断处理程序，根据页表中给出的外存地址，将该页调入内存，使作业继续运行下去如果内存中有空闲块，则分配一页，将新调入页装入内存，并修改页表中相应页表项目的驻留位及相应的内存块号若此时内存中没有空闲块，则要淘汰某页，若该页在内存期间被修改过，则要将其写回外存3、缺页中断（PageFault）在地址映射过程中，在页表与一般中断机制的区别;(1)指令执行期间产生和处理中断信号。因为在执行期间发现缺少某页。（2）一条指令期间可能需要多次中断才能完成任务。因为一条指令需要的数据或指令可能跨越多个页面。与一般中断机制的区别;3.地址变换机构图4-24请求分页中的地址变换过程3.地址变换机构图4-24请求分页中的地址变换过程4.6.2内存分配策略和分配算法1.最小物理块数的确定保证进程正常运行所需的最小物理块数。当系统为进程分配的物理块数少于此值时，进程将无法运行。（1）若是单地址指令且采用直接寻址方式，则所需的最少物理块数为2。一块是用于存放指令的页面，另一块则是用于存放数据的页面。（2）如果该机器允许间接寻址时，则至少要求有三个物理块。（3）对于某些功能较强的机器，其指令长度可能是两个或多于两个字节，因而其指令本身有可能跨两个页面，且源地址和目标地址所涉及的区域也都可能跨两个页面。4.6.2内存分配策略和分配算法1.最小物理块数的确2.物理块的分配策略1)固定分配局部置换(FixedAllocation,LocalReplacement)为某个进程分配固定页面数，其间不能改变。需要置换时候只能置换自己的。2)可变分配全局置换(VariableAllocation,lobalReplacement)先为进程一定的内存页面，如果在需要责从空闲块中选择相应的页面分配给它。3)可变分配局部置换(VariableAllocation,LocalReplacemen初始分配同上，但是如果发生缺页，必须置换自己的页面。如果缺页率过高，os再为其分配一定的页面数目。2.物理块的分配策略1)固定分配局部置换(Fixe3.物理块分配算法1)平均分配算法这是将系统中所有可供分配的物理块，平均分配给各个进程。例如，当系统中有100个物理块，有5个进程在运行时，每个进程可分得20个物理块。这种方式貌似公平，但实际上是不公平的，因为它未考虑到各进程本身的大小。如有一个进程其大小为200页，只分配给它20个块，这样，它必然会有很高的缺页率；而另一个进程只有10页，却有10个物理块闲置未用。3.物理块分配算法1)平均分配算法2)按比例分配算法这是根据进程的大小按比例分配物理块的算法。如果系统中共有n个进程，每个进程的页面数为Si，则系统中各进程页面数的总和为：又假定系统中可用的物理块总数为m，则每个进程所能分到的物理块数为bi，将有：b应该取整，它必须大于最小物理块数。2)按比例分配算法3)考虑优先权的分配算法在实际应用中，为了照顾到重要的、紧迫的作业能尽快地完成，应为它分配较多的内存空间。通常采取的方法是把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程。在有的系统中，如重要的实时控制系统，则可能是完全按优先权来为各进程分配其物理块的。3)考虑优先权的分配算法4.6.3调页策略1.何时调入页面预调页策略一次调入进程的多个相邻的多个页面，这样可以降低每次缺页都要进行调入的开销。可以采用预测机制进行处理。2)请求调页策略发生缺页时才将缺页调入内存中。在目前的虚拟存储中基本采用此种方法进行。4.6.3调页策略1.何时调入页面预调页策略2.从何处调入页面外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。对换区是采用连续分配方式，故对换区的磁盘I/O速度比文件区的高。这样，每当发生缺页请求时，系统应从何处将缺页调入内存，可分成如下三种情况：(1)系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以提高调页速度。为此，在进程运行前，便须将与该进程有关的文件，从文件区拷贝到对换区。2.从何处调入页面外存分为两部分：用于存放文件(2)系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；而当换出这些页面时，由于它们未被修改而不必再将它们换出，以后再调入时，仍从文件区直接调入。但对于那些可能被修改的部分，在将它们换出时，便须调到对换区，以后需要时，再从对换区调入。(3)UNIX方式。由于与进程有关的文件都放在文件区，故凡是未运行过的页面，都应从文件区调入。而对于曾经运行过但又被换出的页面，由于是被放在对换区，因此在下次调入时，应从对换区调入。由于UNIX系统允许页面共享，因此，某进程所请求的页面有可能已被其它进程调入内存，此时也就无须再从对换区调入。(2)系统缺少足够的对换区空间，这时凡是不会3.页面调入过程

(1)向CPU发出缺页中断，保留CPU环境，分析中断原因后，转入缺页中断处理程序。(2)查找页表，得到该页在外存的物理块后，如果此时内存能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。（3）如果内存已满，则须先按照某种置换算法从内存中选出一页准备换出；3.页面调入过程

（4）检查该页是否被修改。a.如果该页未被修改过，可不必将该页写回磁盘；b.如果此页已被修改，则必须将它写回磁盘，然后再把所缺的页调入内存。(5)修改页表中的相应表项，置其存在位为“1”，并将此页表项写入快表中。(6)在缺页调入内存后，利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。（4）检查该页是否被修改。4.7页面淘汰算法1、最佳页面淘汰算法（OPT）

淘汰以后不再需要的或最远的将来才会用到的页面（理论上可行，实际上不可行）2、最近最久未使用（LRU）在最近的一段时间之内一直没有被访问的页面，我们可以认为该页面在将来可能页不会被访问，所以淘汰掉。

即淘汰没有使用的时间最长的页。4.7页面淘汰算法1、最佳页面淘汰算法（OPT）

3、先进先出页面淘汰算法（FIFO）选择在内存中驻留时间最长的页并淘汰之4、第二次机会淘汰算法(NUR)

按照先进先出算法选择某一页面，检查其访问位，如果为0，则淘汰该页，如果为1，则给第二次机会，并将访问位置0。该算法要求在访问某页面时将其访问位置13、先进先出页面淘汰算法（FIFO）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时，将会产生缺页中断。此时OS根据最佳置换算法，将选择页面7予以淘汰。1、OPT页面置换算法时刻PMF12345678910111213141516171819070120304230321201701707107210ffffv210230230v2342342fVVf34230f230v230v210f210v210V210v710f710v710v缺页率σ=9/20=45%时刻PMF1234567891011121314151617662.先进先出(FIFO)页面置换算法图4-26利用FIFO置换算法时的置换图2.先进先出(FIFO)页面置换算法图4-26利用时刻PMF12345678910111213141516171819070120304230321201701707107210ffffv210321032f4032403ffff24032f032v032v103f210f210v210v721f072f107f缺页率σ=15/20=75%2.先进先出(FIFO)页面置换算法时刻PMF123456789101112131415161768时刻PMF12345678910111213141516171819070120304230321201701707107210ffffv210230230v4304204ffff23023f023v023v123f123v120f120v170f170v170v缺页率σ=12/20=60%3.LRU(LeastRecentlyUsed)置换算法的描述时刻PMF123456789101112131415161769例：计算缺页次数

某程序在内存中分配三个页面，初始为空，页面走向为4，3，2，1，4，3，5，4，3，2，1，5例：计算缺页次数某程序在内存中分配三个页面，初始为空FIFO432143543215页1432143555211页243214333522页34321444355

xxxxxxx

xx共缺页中断9次FIFO43214354

LRU432143543215页1432143543215页243214354321页34321435432

xxxxxxx

xxx共缺页中断10次LRU4321435

OPT432143543215页1

432111555211页243333333555页34444444444

xxxx

x

xx

共缺页中断7次最佳页面算法（OPT）OPT4321435LRU置换算法的硬件支持1)寄存器为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为R=Rn-1Rn-2Rn-3…R2R1R0

进程访问某物理块时，要将相应的寄存器r位置为1。定时信号将每隔一段时间将寄存器右移1位，将n位寄存器看作一个整数，那么，具有最小数值的寄存器所对应的页面，就是最近最久未使用页面。如下图所示：LRU置换算法的硬件支持1)寄存器图4-28某进程具有8个页面时的LRU访问情况图4-28某进程具有8个页面时的LRU访问情况2)栈图4-29用栈保存当前使用页面时栈的变化情况

保存当前使用的各个页面的页面号，当进程访问某个页面时，便将该页面的页面号从栈中取出，将其压入栈顶。因此栈顶永远是最近使用的页面，而栈底则是最近最久没有被访问的页面。2)栈图4-29用栈保存当前使用页面时栈的变化情况4

、Clock置换算法（NUR）1.简单的Clock置换算法图4-30简单Clock置换算法的流程和示例注：页面被访问时，其访问位被置为14、Clock置换算法（NUR）1.简单的Clock2.改进型Clock置换算法

由访问位A和修改位M可以组合成下面四种类型的页面：1类(A=0,M=0):表示该页最近既未被访问，又未被修改，是最佳淘汰页。2类(A=0,M=1)：表示该页最近未被访问，但已被修改，并不是很好的淘汰页。3类(A=1,M=0)：最近已被访问，但未被修改，该页有可能再被访问。4类(A=1,M=1):最近已被访问且被修改，该页可能再被访问。2.改进型Clock置换算法由访问位A和修(1)从指针所指示的当前位置开始，扫描循环队列，寻找A=0且M=0的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位A。(2)如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找A=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置0。(1)从指针所指示的当前位置开始，扫描循环

(3)如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复0。然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。(3)如果第二步也失败，亦即未找到第二4.7.4其它置换算法

最少使用(LFU：LeastFrequentlyUsed)置换算法2.页面缓冲算法(PBA：PageBufferingAlgorithm)4.7.4其它置换算法最少使用(LFU：Least4.8虚拟段式存储管理（请求分段式）1、段表机制增加：存在位（在/不在内存，是否可共享），存取方式位（读，写，执行），修改位（是否修改过，能否移动），增补位（固定长/可扩充），访问字段a:纪录该段被访问的频繁度；

外存始址：本段在外存中的起始地址，即起始盘块号。4.8虚拟段式存储管理（请求分段式）1、段表机制2、越界中断处理

进程在执行过程中，有时需要扩大分段，如数据段。由于要访问的地址超出原有的段长，所以发越界中断。操作系统处理中断时，首先判断该段的“扩充位”，如可扩充，则增加段的长度；否则按出错处理2、越界中断处理3、缺段中断处理检查内存中是否有足够的空闲空间

①若有，则装入该段，修改有关数据结构，中断返回

②若没有，检查内存中空闲区的总和是否满足要求，是则应采用紧缩技术，转①；否则，淘汰一（些）段，转①3、缺段中断处理2.缺段中断机构图4-31请求分段系统中的中断处理过程2.缺段中断机构图4-31请求分段系统中的中断处理过分段式虚拟存储管理S段在内存否是B<S段长度发越界中断是否形成绝对地址继续执行指令移动或调出分段与S段末端相邻的空闲区长度满足要求地址错S段可扩充是装入S段重新启动指令调整S段段表及主存分配表操作系统硬件访问S段B单元否符合存取权限发保护中断是否发缺段中断非法存取否主存中有满足S段长度的连续空闲区是否是移动或调出分段分段式虚拟存储管理S段在内存否是B<S段长度发越界中断是否形3.地址变换机构

图4-32请求分段系统的地址变换过程3.地址变换机构图4-32请求分段系统的地址变换过程4.8.2分段的共享与保护1.共享段表图4-33共享段表项另外单独设置一个共享段表，所有共享段都在里面有一个表项。记录项目如下：4.8.2分段的共享与保护1.共享段表图4-33共享进程计数：记录有多少个进程在使用该段。控制存取字段：设置使用该段的权限，“写”、“读”等段号：允许不同的进程使用不同的段号来访问相同的段。共享进程计数：记录有多少个进程在使用该段。2.共享段的分配与回收1)共享段的分配在为共享段分配内存时，对第一个请求使用该共享段的进程，由系统为该共享段分配一物理区，再把共享段调入该区，同时将该区的始址填入请求进程的段表的相应项中，还须在共享段表中增加一表项，填写有关数据，把count置为1；之后，当又有其它进程需要调用该共享段时，由于该共享段已被调入内存，故此时无须再为该段分配内存，而只需在调用进程的段表中，增加一表项，填写该共享段的物理地址；在共享段的段表中，填上调用进程的进程名、存取控制等，再执行count∶=count+1操作，以表明有两个进程共享该段。2.共享段的分配与回收1)共享段的分配2)共享段的回收当共享此段的某进程不再需要该段时，应将该段释放，包括撤在该进程段表中共享段所对应的表项，以及执行count∶=count-1操作。若结果为0，则须由系统回收该共享段的物理内存，以及取消在共享段表中该段所对应的表项，表明此时已没有进程使用该段；否则(减1结果不为0)，则只是取消调用者进程在共享段表中的有关记录。2)共享段的回收3.分段保护越界检查：检查段号与段表长度，段内地址与段长的比较。2)存取控制检查：设定存取权限只读(2)只执行(3)读/写3)环保护机构划分程序优先级，内环优先级高，外环优先级第，编号由内向外编号。调用和访问方式如下图所示:3.分段保护越界检查：检查段号与段表长度，段内地址与段图4-34环保护机构图4-34环保护机构

2、分区式存储管理a.固定式分区管理；b.可变式分区管理。

3、页式存储管理a.页式管理（作业表，页表）b.请求页式管理（作业表，扩充页表。缺页率）

4、段式与段页式存储管理a.段式管理（段表）；b.段页式管理（段表、页表）。小结

1、单一连续存储2、分区式存储管理3、页式存储管理4、段式与段页式存储94

谢谢大家

95第四章存储管理之段页式管理4.2分区存储管理4.3页式存储管理4.4段式存储管理4.5段页式存储管理4.6交换技术与覆盖技术4.7虚拟存储第四章存储管理之段页式管理

4.3页式存储管理

为什么要引进分页技术?分区式存储管理：程序要求连续存放，会产生碎片问题。大程序进入时需要移动已在主存中的信息。分页式存储管理允许把一个作业存放到若干不相邻接的分区中免去移动信息充分利用主存空间4.3页式存储管理为什么要引进分页技术?971.用户程序划分把用户程序按逻辑页划分成大小相等的部分，称为页。从0开始编制页号，页内地址是相对于0编址1.用户程序划分把用户程序按逻辑页划分成大小相等的部逻辑地址用户程序的划分是由系统自动完成的，对用户是透明的。一般，一页的大小为2的整数次幂，因此，地址的高位部分为页号，低位部分为页内地址页号页内地址逻辑地址用户程序的划分是由系统自动完成的，对用户是透明0111231页号P页内位移量W编号0~1048575相对地址0~4095逻辑地址：一维0111231页号P页内位移量W编号0~1048575相对地内存空间：按页的大小划分为大小相等的区域，称为内存块（物理页面，页框）内存分配：以页为单位进行分配，并按作业的页数多少来分配。逻辑上相邻的页，物理上不一定相邻内存空间：按页的大小划分为大小相等的区域，称为内存块（...01234560123456作业的地址空间页框（物理块）页号页表主存中页框（物理块）..........01234560123456作业的页框页号页表主存中页4.3.3管理1.页表：系统为每个进程建立一个页表，页表给出逻辑页号和具体内存块号相应的关系页表放在内存，属于进程的现场信息2.空块管理——位示图3.内存的分配与回收4.3.3管理1.页表：系统为每个进程建立一个页表，页表给0310/10/10/10/10/1017……空闲块数……空块管理——位示图0310/10/10/10/10/1017……空闲块数……空计算一个作业所需要的总块数N查位示图，看看是否还有N个空闲块如果有足够的空闲块，则页表长度设为N，可填入PCB中；申请页表区，把页表始址填入PCB依次分配N个空闲块，将块号和页号填入页表修改位示图计算一个作业所需要的总块数N4.3.4硬件支持1．系统设置一对寄存器：

页表始址寄存器页表长度寄存器2．相联存储器——快表快表表项：页号；内存块号；标识位；淘汰位4.3.4硬件支持1．系统设置一对寄存器：1.基本的地址变换机构图4-12分页系统的地址变换机构1.基本的地址变换机构图4-12分页系统的地址变换机p’页表地址越界L比较P>=Lpp’...快表

b+页号p页内地址dP’d物理地址页表地址寄存器页表长度寄存器逻辑地址快表地址映射机制页表地址越界L比较P>=Lpp’...快表b+页号p页存在的问题当读/写数据时，必须访问两次主存。第一次按页号读出页表中相应栏内容的块号第二次根据计算出来的绝对地址进行读/写解决方法：利用高速缓存存在的问题当读/写数据时，必须访问两次主存。109假定访问主存时间为100毫微秒，访问相联存储器时间为20毫微秒，相联存储器为32个单元时快表命中率可达90%，按逻辑地址存取的平均时间为：（100＋20）×90%＋(100+100+20)×(1-90%)＝130毫微秒比两次访问主存的时间100毫微秒×2+20＝220毫微秒下降了四成多。假定访问主存时间为100毫微秒，访问相联存储器时间为1104.3.5页式管理的优缺点优点：解决了碎片问题便于管理缺点：不易实现共享不便于动态连接思考：页的共享？页的保护？4.3.5页式管理的优缺点优点：解决了碎片问题4.3.3两级和多级页表

逻辑地址空间(232~264)。页表就变得非常大，要占用相当大的连续的内存空间。

eg:32位逻辑地址空间的分页系统，规定页面大小为4KB即212B，则在每个进程页表中的页表项可达1兆个之多。解决办法：1、采用离散分配方式。解决难以找到一块连续的大内存空间的问题；

2、只将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入。4.3.3两级和多级页表逻辑地址空间(21.两级页表(Two-LevelPageTable)逻辑地址结构可描述如下：

为了解决页表需要连续存储空间的问题，将页表离散的放入内存，然后建立一个页表的页表（连续存储在外存中），用以标识页表放在内存中的位置。同时逻辑地址也变成了如上的表示（一维）1.两级页表(Two-LevelPageTable)图4-14两级页表结构图4-14两级页表结构图4-15具有两级页表的地址变换机构图4-15具有两级页表的地址变换机构页目录地址目录位移页表位移页位移虚拟地址页表地址...页目录（每进程一个）块号...页表代码或数据...内存块二级页表结构及地址映射++页目录地址目录位移页表位移页位移虚拟地址页表地址.页目录（每段号单元号4.4.1基本思想一个程序的各个段离散存放段式存储管理单个段的存储基于可变分区存储管理实现，占据连续的内存存储空间段页式存储管理单个段的存储基于页式存储管理实现4.4分段式存储管理段号单元号4.4.1基本思想4.4分段式存储管理...0S工作区段[B]主程序段[M]......0EP子程序段[X]0K...CALL[X][E].........CALL[Y][F]CALL[A]116......0FL子程序段[Y]0116N数组[A]12345......0S工作区段[B]主程序段[M]0EP子程操作系统.....B0SA0NY0LX0PM0K逻辑段号01234作业1的地址空间10003200500060008000PKSLN主存K3200P1500L6000N8000S5000长度段地址01234操作系统操作系统B0SA0NY0LX0PM0K逻辑段号01用户程序划分按程序自身的逻辑关系划分为若干个程序段，每个程序段都有一个段名，且有一个段号。段号从0开始，每一段也从0开始编址，段内地址是连续的用户程序划分按程序自身的逻辑关系划分为若干个程序段，每个逻辑地址内存划分内存空间被动态的划分为若干个长度不相同的区域，这些区域被称为物理段，每个物理段由起始地址和长度确定段号段内地址逻辑地址内存划分段号段内地址内存分配以段为单位分配内存，每一个段在内存中占据连续空间（内存随机分割，需要多少分配多少），但各段之间可以不连续存放内存分配以段为单位分配内存，每一个段在内存中占据连续空间4.4.2管理段表：它记录了段号，段的首（地）址和长度之间的关系每一个程序设置一个段表，放在内存属于进程的现场信息段号012段首址段长度58K20K100K110K260K140K4.4.2管理段表：段号012段首址段长度58K20K10空闲块管理：记录了空闲区起始地址和长度内存的分配算法：首先适配；最佳适配；最坏适配空闲块管理：记录了空闲区起始地址和长度4.4.3硬件支持系统设置一对寄存器段表始址寄存器：用于保存正在运行进程的段表的始址段表长度寄存器：用于保存正在运行进程的段表的长度（例如上图的段表长度为3）4.4.3硬件支持系统设置一对寄存器

Cl

Cb+段号S段内地址d比较比较b+d段表S>=Cl快表物理地址段表始址寄存器段表长度寄存器逻辑地址lb...Slb地址越界d>=1d>=1地址映射及存储保护机制地址越界地址越界比较L:为段长，注意与分页的区别ClCb+段号S段内地址d比较比较b+d段介于内存与寄存器之间的存储机制，它又叫快表用途：保存正在运行进程的段表的子集（部分表项）特点：按内容并行查找相联（联想）存储器（associativememory）

TLB（Translationlookasidebuffers）介于内存与寄存器之间的存储机制，它又叫快表相联（联想）引入快表的作用：

为了提高地址映射速度快表项目：段号；段始址；段长度；标识（状态）位；访问位（淘汰位）快表淘汰问题？（淘汰机制）引入快表的作用：

为了提高地址映射速度4.4.3信息共享图4-18分页系统中共享editor的示意图4.4.3信息共享图4-18分页系统中共享edit图4-19分段系统中共享editor的示意图图4-19分段系统中共享editor的示意图优点：便于动态申请内存管理和使用统一化便于共享便于动态链接缺点：产生碎片思考：与可变分区存储管理方案的相同点与不同点？优点：4.4.4段页式存储管理1。产生背景及基本思想背景：结合了二者优点克服了二者的缺点4.4.4段页式存储管理1。产生背景及基本思想基本思想：用户程序划分：按段式划分（对用户来讲，按段的逻辑关系进行划分；对系统讲，按页划分每一段）逻辑地址：内存划分：按页式存储管理方案内存分配：以页为单位进行分配段号段内地址页号页内地址基本思想：用户程序划分：按段式划分（对用户来讲，按段的段页式存储方式的管理1.段表：记录了每一段的页表始址和页表长度2.页表：记录了逻辑页号与内存块号的对应关系（每一段有一个，一个程序可能有多个页表）3.空块管理：同页式管理4.分配：同页式管理段页式存储方式的管理1.段表：记录了每一段的页表始址和页表图4-21利用段表和页表实现地址映射图4-21利用段表和页表实现地址映射2.地址变换过程图4-22段页式系统中的地址变换机构2.地址变换过程图4-22段页式系统中的地址变换机构4.5虚拟存储技术计算机系统资源管理策略：内存比较昂贵，同时资源有限；外存较大，价格便宜；以CPU时间和外存空间换取昂贵内存空间，这是操作系统中的资源转换技术4.5虚拟存储技术计算机系统资源管理策略：1.常规存储器管理方式的特征一次性。作业在运行时全部一次装入。

(2)驻留性。作业装入内存后，直至作业结束才完全撤出。1.常规存储器管理方式的特征一次性。作业在运行时全部一4.5.1概述1、问题的提出程序大于内存程序暂时不执行或运行完是否还要占用内存

虚拟存储器的基本思想是：程序、数据、堆栈的大小可以超过内存的大小，操作系统把程序当前使用的部分保留在内存，而把其它部分保存在磁盘上，并在需要时在内存和磁盘之间动态交换。虚拟存储器支持多道程序设计技术4.5.1概述1、问题的提出2、程序局部性原理

在一段时间内一个程序的执行往往呈现出高度的局部性，表现在时间与空间两方面时间局部性：一条指令被执行了，则在不久的将来它可能再被执行空间局部性：若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被使用2、程序局部性原理3、虚拟存储技术虚存：把内存与外存有机的结合起来使用，从而得到一个容量很大的“内存”，这就是虚存实现思想：当进程运行时，先将一部分程序装入内存，另一部分暂时留在外存，当要执行的指令不在内存时，由系统自动完成将它们从外存调入内存工作目的：提高内存利用率。3、虚拟存储技术虚存：把内存与外存有机4.5.3虚拟存储器的特征多次性一个作业分多次调入内存执行对换性进程运行期间允许程序和数据换进、换出。3.虚拟性从逻辑上对内存进行扩充，允许运行比内存大的程序4.5.3虚拟存储器的特征多次性4.6虚拟页式存储管理(请求分页式)1、基本工作原理

在进程开始运行之前，不是装入全部页面，而是装入一个或零个页面，之后根据进程运行的需要，动态装入其它页面；当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面4.6虚拟页式存储管理(请求分页式)1、基本工作原理2、页表表项（有可能在外存上，故如下）页号、驻留位、内存块号、外存地址、访问位、修改位 驻留位（中断位）：表示该页是在内存还是在外存访问位：根据访问位来决定淘汰哪页（由不同的算法决定）修改位：查看此页是否在内存中被修改过页号中断位内存块号外存地址访问位修改位2、页表表项（有可能在外存上，故如下）页号、驻留位、内存块号3、缺页中断（PageFault）在地址映射过程中，在页表中发现所要访问的页不在内存，则产生缺页中断。操作系统接到此中断信号后，就调出缺页中断处理程序，根据页表中给出的外存地址，将该页调入内存，使作业继续运行下去如果内存中有空闲块，则分配一页，将新调入页装入内存，并修改页表中相应页表项目的驻留位及相应的内存块号若此时内存中没有空闲块，则要淘汰某页，若该页在内存期间被修改过，则要将其写回外存3、缺页中断（PageFault）在地址映射过程中，在页表与一般中断机制的区别;(1)指令执行期间产生和处理中断信号。因为在执行期间发现缺少某页。（2）一条指令期间可能需要多次中断才能完成任务。因为一条指令需要的数据或指令可能跨越多个页面。与一般中断机制的区别;3.地址变换机构图4-24请求分页中的地址变换过程3.地址变换机构图4-24请求分页中的地址变换过程4.6.2内存分配策略和分配算法1.最小物理块数的确定保证进程正常运行所需的最小物理块数。当系统为进程分配的物理块数少于此值时，进程将无法运行。（1）若是单地址指令且采用直接寻址方式，则所需的最少物理块数为2。一块是用于存放指令的页面，另一块则是用于存放数据的页面。（2）如果该机器允许间接寻址时，则至少要求有三个物理块。（3）对于某些功能较强的机器，其指令长度可能是两个或多于两个字节，因而其指令本身有可能跨两个页面，且源地址和目标地址所涉及的区域也都可能跨两个页面。4.6.2内存分配策略和分配算法1.最小物理块数的确2.物理块的分配策略1)固定分配局部置换(FixedAllocation,LocalReplacement)为某个进程分配固定页面数，其间不能改变。需要置换时候只能置换自己的。2)可变分配全局置换(VariableAllocation,lobalReplacement)先为进程一定的内存页面，如果在需要责从空闲块中选择相应的页面分配给它。3)可变分配局部置换(VariableAllocation,LocalReplacemen初始分配同上，但是如果发生缺页，必须置换自己的页面。如果缺页率过高，os再为其分配一定的页面数目。2.物理块的分配策略1)固定分配局部置换(Fixe3.物理块分配算法1)平均分配算法这是将系统中所有可供分配的物理块，平均分配给各个进程。例如，当系统中有100个物理块，有5个进程在运行时，每个进程可分得20个物理块。这种方式貌似公平，但实际上是不公平的，因为它未考虑到各进程本身的大小。如有一个进程其大小为200页，只分配给它20个块，这样，它必然会有很高的缺页率；而另一个进程只有10页，却有10个物理块闲置未用。3.物理块分配算法1)平均分配算法2)按比例分配算法这是根据进程的大小按比例分配物理块的算法。如果系统中共有n个进程，每个进程的页面数为Si，则系统中各进程页面数的总和为：又假定系统中可用的物理块总数为m，则每个进程所能分到的物理块数为bi，将有：b应该取整，它必须大于最小物理块数。2)按比例分配算法3)考虑优先权的分配算法在实际应用中，为了照顾到重要的、紧迫的作业能尽快地完成，应为它分配较多的内存空间。通常采取的方法是把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程。在有的系统中，如重要的实时控制系统，则可能是完全按优先权来为各进程分配其物理块的。3)考虑优先权的分配算法4.6.3调页策略1.何时调入页面预调页策略一次调入进程的多个相邻的多个页面，这样可以降低每次缺页都要进行调入的开销。可以采用预测机制进行处理。2)请求调页策略发生缺页时才将缺页调入内存中。在目前的虚拟存储中基本采用此种方法进行。4.6.3调页策略1.何时调入页面预调页策略2.从何处调入页面外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。对换区是采用连续分配方式，故对换区的磁盘I/O速度比文件区的高。这样，每当发生缺页请求时，系统应从何处将缺页调入内存，可分成如下三种情况：(1)系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以提高调页速度。为此，在进程运行前，便须将与该进程有关的文件，从文件区拷贝到对换区。2.从何处调入页面外存分为两部分：用于存放文件(2)系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；而当换出这些页面时，由于它们未被修改而不必再将它们换出，以后再调入时，仍从文件区直接调入。但对于那些可能被修改的部分，在将它们换出时，便须调到对换区，以后需要时，再从对换区调入。(3)UNIX方式。由于与进程有关的文件都放在文件区，故凡是未运行过的页面，都应从文件区调入。而对于曾经运行过但又被换出的页面，由于是被放在对换区，因此在下次调入时，应从对换区调入。由于UNIX系统允许页面共享，因此，某进程所请求的页面有可能已被其它进程调入内存，此时也就无须再从对换区调入。(2)系统缺少足够的对换区空间，这时凡是不会3.页面调入过程

(1)向CPU发出缺页中断，保留CPU环境，分析中断原因后，转入缺页中断处理程序。(2)查找页表，得到该页在外存的物理块后，如果此时内存能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。（3）如果内存已满，则须先按照某种置换算法从内存中选出一页准备换出；3.页面调入过程

（4）检查该页是否被修改。a.如果该页未被修改过，可不必将该页写回磁盘；b.如果此页已被修改，则必须将它写回磁盘，然后再把所缺的页调入内存。(5)修改页表中的相应表项，置其存在位为“1”，并将此页表项写入快表中。(6)在缺页调入内存后，利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。（4）检查该页是否被修改。4.7页面淘汰算法1、最佳页面淘汰算法（OPT）

淘汰以后不再需要的或最远的将来才会用到的页面（理论上可行，实际上不可行）2、最近最久未使用（LRU）在最近的一段时间之内一直没有被访问的页面，我们可以认为该页面在将来可能页不会被访问，所以淘汰掉。

即淘汰没有使用的时间最长的页。4.7页面淘汰算法1、最佳页面淘汰算法（OPT）

3、先进先出页面淘汰算法（FIFO）选择在内存中驻留时间最长的页并淘汰之4、第二次机会淘汰算法(NUR)

按照先进先出算法选择某一页面，检查其访问位，如果为0，则淘汰该页，如果为1，则给第二次机会，并将访问位置0。该算法要求在访问某页面时将其访问位置13、先进先出页面淘汰算法（FIFO）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时，将会产生缺页中断。此时OS根据最佳置换算法，将选择页面7予以淘汰。1、OPT页面置换算法时刻PMF12345678910111213141516171819070120304230321201701707107210ffffv210230230v2342342fVVf34230f230v230v210f210v210V210v710f710v710v缺页率σ=9/20=45%时刻PMF12345678910111213141516171612.先进先出(FIFO)页面置换算法图4-26利用FIFO置换算法时的置换图2.先进先出(FIFO)页面置换算法图4-26利用时刻PMF12345678910111213141516171819070120304230321201701707107210ffffv210321032f4032403ffff24032f032v032v103f210f210v210v721f072f107f缺页率σ=15/20=75%2.先进先出(FIFO)页面置换算法时刻PMF1234567891011121314151617163时刻PMF12345678910111213141516171819070120304230321201701707107210ffffv210230230v4304204ffff23023f023v023v123f123v120f120v170f170v170v缺页率σ=12/20=60%3.LRU(LeastRecentlyUsed)置换算法的描述时刻PMF1234567891011121314151617164例：计算缺页次数

某程序在内存中分配三个页面，初始为空，页面走向为4，3，2，1，4，3，5，4，3，2，1，5例：计算缺页次数某程序在内存中分配三个页面，初始为空FIFO432143543215页1432143555211页243214333522页34321444355

xxxxxxx

xx共缺页中断9次FIFO43214354

LRU432143543215页1432143543215页243214354321页34321435432

xxxxxxx

xxx共缺页中断10次LRU4321435

OPT432143543215页1

432111555211页243333333555页34444444444

xxxx

x

xx

共缺页中断7次最佳页面算法（OPT）OPT4321435LRU置换算法的硬件支持1)寄存器为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为R=Rn-1Rn-2Rn-3…R2R1R0

进程访问某物理块时，要将相应的寄存器r位置为1。定时信号将每隔一段时间将寄存器右移1位，将n位寄存器看作一个整数，那么，具有最小数值的寄存器所对应的页面，就是最近最久未使用页面。如下图所示：LRU置换算法的硬件支持1)寄存器图4-28某进程具有8个页面时的LRU访问情况图4-28某进程具有8个页面时的LRU访问情况2)栈图4-29用栈保存当前使用页面时栈的变化情况

保存当前使用的各个页面的页面号，当进程访问某个页面时，便将该页面的页面