《存储器管理》PPT课件.ppt

第三章 存储管理,存储器管理是操作系统的重要的一个部分，它负责管理计算机系统的存储器,3.1 计算机系统中的存储器,内 存,外 存,高速缓存器（Cache）,存取速度越来越快,存取容量越来越小,成本越来越大,寄存器,寄 存 器,寄存器（Register)是中央处理器内的组成部份，它们可用来暂存指令、数据和地址，常用的有：指令寄存器，通用寄存器，控制寄存器等,高 速 缓 存 cache,高速缓冲存储器Cache是位于CPU与内存之间的临时存储器，它的容量比内存小但交换速度快,内 存,存储容量较大，存取速度较快。存储单元以字节为单位进行编址。用于存放用户当前需执行的程序和数据，以及操作系统进行控制和管理的信息,内存,用户区,0,n-1,操作系统,存储器管理主要指的是对内存储器的管理,逻辑地址:用户程序中使用的地址。 逻辑地址空间：由程序中逻辑地址组成的地址范围叫做逻辑地址空间（相对地址空间）。,3.2 重定位,程序A,程序B,程序C,假设程序A、B、C分别有100、50、120条指令，问各自的逻辑地址空间范围？,0,1,99,0,1,49,0,1,119,系统为了方便管理内存，对内存中每个字节单元，从0开始编号，该编号称为主存储器的绝对地址 绝对地址对应的内存空间， 称为“物理地址空间”,内存地址空间,物理地址,从地址处取数到寄存器1,程序A有701条指令，其逻辑地址空间为？,装入内存,思考：指令LOAD的逻辑地址和物理地址是多少？ 数据12345的逻辑地址和物理地址是多少？,需要把指令LOAD 1, 500中涉及到地址的量进行修改,12345,重定位：我们把对目标程序中的指令和数据的地址的修改过程，称之为重定位 对程序进行重定位的技术按重定位的时机可分为两种：静态重定位和动态重定位。,地址转换,1.静态重定位 是指在目标程序装入内存时，由装入程序对目标程序中的指令和数据的地址进行修改的重定位。 对每个程序来说，这种地址变换只是在装入时一次性完成，在程序运行期间不再进行重定位。,优点： 无需增加硬件地址转换机构，便于实现程序的静态连接 缺点是： 程序重定位之后就不能再移动，这不利于内存空间的有效使用； 各个用户进程很难共享内存中的同一程序的副本。,2. 动态重定位 是在程序执行期间每次访问内存之前进行重定位。 这种变换是靠硬件地址变换机构实现的，通常采用一个重定位寄存器，其中放有当前正在执行的程序在内存空间中的起始地址,重定位寄存器,又称“基址寄存器”,动态重定位的主要优点是： 程序占用的内存空间动态可变，不必连续存放在一处； 比较容易实现几个进程对同一程序副本的共享使用。 它的主要缺点是需要附加硬件支持，增加了成本。,?,经过 （ ）重定位，程序无需改动直接装入内存，既可执行。 A 静态重定位 B 动态重定位,B,3.3-3.6 存储管理机制,存储管理方案很多，大致把存储管理方案概括成4种：分区管理、分页管理、分段管理和段页式管理。对于每一种方案管理要掌握其基本思想、工作原理和特点。,分 区 管 理,单用户连续存储管理,固定分区管理,可变分区管理,主要适用于单道批处理系统。 分配策略的基本思想是总体上把内存储器分为两个分区。一个分区固定分配给操作系统使用称之为“系统区”；另一个分配给用户使用，称为“用户区”。,3.3 单用户连续存储管理,单道批处理系统,缺 点： 系统的工作效率不高，资源利用率低下。 若用户作业的相对地址空间比用户区大，那么该作业就无法运行。即大作业无法在小内存上运行。,如何实现内存保护？,小贴士: 执行用户程序时，CPU去某地址取指令或数据前先把该地址与界限寄存器中值进行比较，大于等于该值，可继续执行否则产生地址越界中断,采用这种存储分配策略时，将对用户程序 实行静态重定位,1、处理器不能直接访问的存储器是（ ） A、寄存器 B、高速缓冲存储器 C、主存储器 D、光盘 2计算机主存储器中，存储单元的编址单位是（ ） A二进制位 B字节 C字 D块,D,B,3、存储管理中的地址转换(重定位)指的是( ) A、将绝对地址转换成逻辑地址 B、将物理地址转换成逻辑地址 C、将逻辑地址转换成绝对地址 D、将物理地址转换成相对地址,C,4.价格昂贵、存取速度最快，但容量较小的存储器是（ ） A.寄存器 B.高速缓冲存储器 C.主存储器 D.辅助存储器 5.程序状态字寄存器是属于（ ） A.指令寄存器 B.通用寄存器 C.控制寄存器 D.时钟寄存器 6.处理器中仅设置一个界限寄存器的存储管理方式是（ ） A.页式存储管理 B.可变分区存储管理 C.固定分区存储管理D.单用户连续存储管理,A,C,D,7.地址转换是在作业执行前集中完成，执行中无需再进行地址转换的定位方式称为_。 8.现在常用的辅助存储器中速度最快的是_。 9、必须有硬件地址转换机构的地址转换方式称为_ _,静态重定位,硬盘,动态重定位,指预先把内存储器中可供分配的用户区划分成若干个连续的分区，每个分区的尺寸可以相同，也可以不同。划分后，内存储器中分区的个数以及每个分区的尺寸保持不变。 每个分区中只允许装入一个作业运行。,3.4 固定分区存储管理,38,系统区,0,20K,第一分区（8KB),第二分区（32KB),第三分区（64KB),第四分区（132KB),256KB内存,该内存中允许并发执行的作业最多有几个？,有两个作业A、B依次进入内存，大小分别是80K、6K分别装入内存中合适的分区，如何分配内存。,40,系统区,0,20K,第一分区（8KB),第二分区（32KB),第三分区（64KB),第四分区（132KB),256KB内存,作业A,作业B,内部碎片,内部碎片,分配给用户 而用户未使用到的内存空间,操作系统设置一张名为“分区分配表”的表格，用它记录各分区的信息以及当前的使用情况。,使用标志为“0”时，表示该分区当前是空闲的，作业名，表示该分区已经分配给该作业使用,固定分区存储管理的特点 提高了内存资源的利用率。 对进入分区的作业程序，实行的是静态重定位。,在固定分区存储管理中，不仅要防止用户程序对操作系统形成的侵扰，也要防止用户程序与用户程序之间形成的侵扰。因此必须在CPU中设置一对专用的寄存器,下限寄存器,上限寄存器,CPU欲执行那个作业就把该作业的上限和下限地址装入寄存器，执行指令时，若 下限地址绝对地址上限地址， 则表示访问合法，否则产生“地址越界”中断,如何提高内存空间利用率,根据经常出现的作业的大小和数量来划分分区，尽可能使各个分区被充分利用,划分分区时按分区大小顺序排列，方便找出一个能满足作业要求的最小空闲区分配给它，使闲置的空间尽可能的小,按作业对主存的需求量排成多个作业队列,47,系统区,0,20K,第一分区（8KB),第二分区（32KB),第三分区（64KB),第四分区（132KB),256KB内存,有一批作业需要系统处理， 分别需内存:,如何执行内存利用率高？,48,操作系统,0,d,c,b,a,分区1,分区3,分区2,缺点： 如果到达作业的尺寸比任何一个分区的长度都大，那么它就无法运行。 进入分区的作业尺寸，不见得与分区的大小相吻合，势必产生内部碎片，引起内存资源的浪费。,又称动态分区, 对存储空间的划分是在装入作业时进行的，且分区大小正好适应作业的需要。,3.5 可变分区存储管理,主存空间的分配与回收 系统初启时，内存中除常驻的操作系统外，其余的是一个完整的大空闲区。随后，对调入若干个作业接连划分成几个大小不等的分区分配给它们。但是系统运行一段时间后，随着作业的撤除且相应分区的释放，原来一整块的存储区会形成空闲分区和已分配区相间的局面。,作业A(16KB) 、作业B(100KB)、作业C(70KB)依次进入内存,此时，作业D（75KB）欲进入内存，分配否？,作业要求装入内存储器时，如果当时内存储器中有足够的存储空间，那么就划分出一个与作业相对地址空间同样大小的分区分配给它。如果没有足够大的区域，就拒绝进行分配。,一段时间后，作业B执行完毕,思 考,在内存使用情况为f图情况下，若又有作业（大小为），作业（大小为）和作业（）先后提出内存使用申请，分析内存分配情况,剩余空间为 ,外部碎片,外部碎片,在存储管理中，把那些无法满足作业存储请求的空闲区称为“外部碎片”,又称”零头”。 内部碎片是分配给了用户而用户未用的存储区；外部碎片是无法分配给用户使用的存储区。,可变分区的管理方式： 为了记录内存中现有的分区以及各分区的类型，操作系统设置了张表格，为“空闲区表”，用来记录空闲区的起始地址和长度,可变式分区说明表,未分配,未分配,空,空,空,空闲区的分配算法： 在可变分区存储管理中，常用的分区分配算法有：最先适应算法、最佳适应算法以及最坏适应算法。,最先适应算法 实行这种分配算法时，总是把最先找到的、满足存储需求的那个空闲分区作为分配的对象。,最优适应算法 实行这种分配算法时，总是从当前所有空闲区中找出一个能够满足存储需求的、最小的空闲分区作为分配的对象。,最坏适应算法 实行这种分配算法时，总是从当前所有空闲区中找出一个能够满足存储需求的、最大的空闲分区作为分配的对象。,若作业D到达，提出存储需求20KB。试问：如果系统实行最先适应算法，应该把哪一个空闲分区分配给它？分配后的内存情形用图示出。如果系统实行最佳适应算法和最坏适应算法，应该把哪一个空闲分区分配给作业D？,思 考,最先适应算法,最佳适应算法,思考：各算法下Job1的内存分配情况,始址,长度,标志,a,d,c,b,16K,30K,10K,14K,Job1：13K,Job2,Job3,作业队列,不同算法下，空闲区表各项内容的排序不同： 最先适应算法：按空闲区的地址顺序从小到大登记在空闲区表中 最优适应算法：按空闲区的长度从小到大登记在空闲区表中 最坏适应算法：按空闲区的长度从大到小登记在空闲区表中,1（多选）可变分区管理的主存分配算法中，需要在空闲区表中将空闲区项按长度以递增或递减次序排列的分配算法是（ ） A、最先适应 B、循环最先适应 C、最优适应 D、最坏适应 E、随机适应,CD,回收撤消作业所占分区时，要检查回收的分区是否与空闲区邻接，若是则加以合并，使之成为连续的大分区，并登记到空闲区表中，再次等待后来作业申请而进行分配。,思考：当一个作业完成退出内存时， 内存中空闲区的数目一定增加吗？,当作业A执行完毕，推出内存时，各图中，空闲区个数的变化？,增加,不变,不变,减少,3.5.2 地址转换和存储保护,采用可变分区方式管理时，一般采用动态重定位方式装入作业。硬件设置两个专用的控制寄存器：基址寄存器和限长寄存器,作业在内存的始址,作业在内存的末址,73,基址寄存器,限长寄存器,+,绝对地址a+k？,内存,操作系统,0,a,a+b,a+c,a+k,+,c,作业地址空间,a,a+k,c,a+c,是,否,地址越界中断,图3-13 地址转换示例,优 点： 缺 点：,实现了内存共享 算法简单，容易实现,存在外部碎片（零头），浪费内存 不能实现内存扩充,3.5.3 移动技术,移 动,把作业从一个存储区域移动到另一个存储区的工作,移动的目的,集中分散的空闲区,便于作业动态扩充内存,77,操作系统,作业1,空闲区,作业2,空闲区,作业3,空闲区,操作系统,作业1,空闲区,作业2,空闲区,作业3,空闲区,作业2,空闲区,操作系统,作业1,空闲区,作业2,空闲区,作业3,空闲区,作业2,空闲区,作业3,空闲区,空闲区,a. 分散的空闲区,c. 移动作业3后,b. 移动作业2后,采用移动技术，需注意： 移动会增加系统开销 移动是有条件地,操作系统所占用的系统资源和所需的处理器时间，称为“系统开销”,移动一道作业时，应先判定是否在与外围设备交换信息，是，不可移动；否，可移动,优 点： 缺 点：,实现了内存共享 算法简单，容易实现,存在外部碎片（零头），浪费内存 不能实现内存扩充,1、可以采用静态重定位方式转换地址的管理内存方案是( ) A、页式管理 B、页式虚拟管理 C、可变分区管理 D、固定分区管理,D,2减少可变分区存储管理中碎片的措施是（ ） A增大分区长度 B增加分区数目 C采用移动技术 D减少分区长度 3可变分区存储管理中，通常分配最快的算法是（ ） A最先适应分配 B最优适应分配 C最坏适应分配 D随机分配,C,A,4CPU中与地址转换有关的寄存器是（ ） A指令寄存器 B基址寄存器 C程序状态字寄存器 D界限寄存器 E上界、下界寄存器,BD,5辅助存储器通常指的是_。 6单用户连续存储管理是采用_方式进行地址转换的。 7可变分区存储管理中，可用一张空闲区表来管理各分区的分配和回收，当某作业完成，回收该分区时发现空闲区表项不仅不增加，还减少了一项，说明该作业_。 8、采用可变分区管理主存时，移动技术可以集中分散的空闲区，还可便于作业_。,硬盘,静态重定位,有上邻空闲区和下邻空闲区,动态扩充内存,前言：分区管理方案要求作业放入一个连续的存储区，导致内存利用率低,举例说明,剩余空间为 ,思考：当前内存空闲容量为10K，但在分区 管理方案下，能否装入大小为8KB的程序？,7KB,3KB,3.6 页式虚拟存储管理,在分区管理中，一个作业总要求占用一个连续的内存区，因而产生了碎片（零头）问题。 分页存储管理有两种：简单分页存储管理和请求分页存储管理。,3.6.1 页式存储管理的基本原理 内存空间分块：首先把整个内存储器划分成大小相等的许多分区，每个分区称为“块”或“内存块”或“页块”。对每块进行编号，从0开始，分别为0,1,2,n-1。,块 号,内存空间分块, 逻辑地址空间分页：然后按照内存块的尺寸对该空间进行划分，称之为“页”。这种划分是在系统内部进行的，用户感觉不到这种划分，也对其进行编号。编号从0开始，第0页、第1页、第2页、,页 号,页面（或块）的大小由硬件决定，一般为2的若干次幂。 例如：IBM AS/400规定的页面大小为512B Intel 80386的页面大小为4KB,内存分配原则：在分页的情况下，系统以块为单位，把内存分配给作业或进程，并且一个进程的若干页一次性的全部原封不动地分别装入物理上不相邻的内存块中。,例 题,某作业大小为4096个字节，某计算机系统划定的页面大小为1024个字节，假定系统分配给该作用的内存块号分别为40号、45、46、100。装入内存后如图所示,3.6.3 页表和地址转换,页表：系统又为每个进程设立一张页面映像表，简称页表，作用实现从页号到物理块号的地址映射。,页表包含两项信息：页号及其对应的块号，以此来实现页号到内存块号的地址映射,逻辑地址表示 用户逻辑地址空间中的每一个逻辑地址，都可以用“页号，页内位移”来表示。即数对（p , d）其地址结构如下图所示,思考：上述地址结构中，最多允许有多少页，页长为多大？,8、若页式存储管理中的地址格式为 则它的最大页号和最大页内地址是（ ） A、256和65536 B、255和65535 C、256和65535 D、255和65536,页号,页内地址,B,35.设某页式存储管理主存的地址是20位，其中12位是页内地址，则该系统的页面长度为_字节，最大可存放256页。,4096,例如：某作业大小为4096B，若系统页面大小为1024个字节，则该作业被分为4个页面。,作业逻辑地址空间,0,1023,2047,3071,4095,0 页,1 页,2 页,3 页,思考：逻辑地址为2000和4000的指令对应的页号和偏移量是多少,2000（1，976）,4000（3，928）,如果给的逻辑地址是A，页面大小为L,则页号p和页内地址d的计算公式是： 页号p = A/L； 页内位移d = A % L 其中，/用于整数表示整除，% 是求余操作,例如：设某系统的页面大小为1KB，A=3456, 则p = , d= . 用一个数对（p,d)来表示，就是（ ， ）,3,384,3,384,将用户的逻辑地址转换成数对（页号、页内位移）；按照页号p去查页表找到该页对应的物理块号b；由块起始地址和页内位移相加形成绝对地址。即物理地址w=bL + d,地址变换,某系统页长为2KB，某作业被分为3个页面，页表内容如下，求作业逻辑地址为1500，6000的指令对应的物理地址,逻辑地址 1500,（0，1500）,W=f*L+d W=5*2048+1500 =11740,查页表，得块号,在采用页式存储管理的系统中，某一作业J的逻辑地址空间为4页（每页2048个字节），且已知该作业的页面映象表（即页表）如下： 则有效逻辑地址4865所对应的物理地址是_。,12K+769,直接映像的页地址转换 页表在内存中存放 当进程被调度到处理器上运行时，操作系统自动的将该进程的页表起始地址装入页表地址寄存器中,内存用户区,A,地址映像机构,查页表,得 块 号,得 物 理 地 址,CPU取得所需指令（数据）需要访问内存几次？,CPU要两次访问内存才得到所要的数据；一次访问内存查页表；一次访问内存取所需数据,举例：假定块的尺寸为1KB，作业A的相对地址空间为3KB大小，作业A进入系统后被划分成3页，调用逻辑地址为3000处的一条指令。页表内容如下，试分析地址变换过程,逻辑地址 A=3000,(2, 952),查页表，得块号7,块号与页内地址拼接得物理地址 71024952,8120,快表加速地址转换 为了提高地址的转换速度，可用高速缓冲存储器存放页表的一部分，简称“快表”。,在地址转换过程中，根据页号同时查“快表”和“页表”，若该页已登记在快表中，就自动停止在内存中查“页表”的工作。,查 页 表,查快表,得到块号,利用快表的地址转换过程,通过查快表就能实现内存访问的成功率为“命中率”，命中率越高，性能就越好。快表命中率统计,原理依据：由于程序运行中有局部性的特点，即刚被访问过的单元在很短的时间内还将被访问（时间的局部性）和刚被访问过的单元的邻近单元也将被访问（空间的局部性）。,存在循环,指令执行的顺序性,3.6.4 页的共享和保护 页式存储管理有利于实现多个作业共享程序和数据。需共享的信息只需在内存中保留一个副本，各作业共享这些信息时可使他们各自的页表中有关表目指向共享信息所在的主存块号,页号,标志,块号,0,1,2,3,218,542,103,58,只执行,只读,读/写,读/写,页号,标志,块号,0,1,2,3,218,200,72,542,只执行,读/写,只读,读/写,作业1页表,作业2页表,共享程序,共享数据,218块,542块,内 存,页面共享,注意： 对于共享的页面，若是程序，则只可执行；若是数据，则只可读。,33.页式存储管理中，对于多个作业共享的块， 限制各作业_。,写入信息,3.6.2 页式主存空间的分配与回收 分页式存储管理是以“块”为单位进行存储分配的，在有存储请求时，只要系统中有足够的空闲块存在，就可以进行存储分配，系统采用存储分块表来记录每个存储块的状态。,内存分配：当有存储请求时，就查存储分块表。只要表中“空闲块总数”记录的数目大于请求的存储量，就可以进行分配，同时把表中分配出去的块的状态改为“已分配”。 内存回收：当作业完成归还存储块时，就把表中相应块的状态改为“空闲”。,具体实现时可用一张“位示图”来构成主存分配表。 例如：某内存有64块，则可用8个字（字长为8）的位示图来表示。,位示图,07号块,815号块,1623号块,2431号块,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,0,1,0,1,0,1,思考：1号字5号位表示内存块号是多少，该块状态为。？ 18号块的状态为？,块号=字号字长+位号 字号=块号/字长 位号=块号 mod 字长,块号除以字长，商为字号，余数为位号,49页式管理中，用一张16个字长为32位的字构成的位示图分配512个主存页面，编号习惯都从0开始。 试问：（1）399号页面对应的字号和位号； （2）9号字的18号位对应的页面号。,（1）字号=399/32=12 位号=399%32=15,（2）页面号=字号字长+位号=9 32+18=306,简单分页式存储管理的特点,平均每一个作业要浪费半页大小的存储块。 47.页式存储管理中是否存在碎片？请说明理由。,思考： 作业大小为5500B，系统设定页长为1KB 则该作业被分为6页，需6个内存块，存在内存浪费,内零头,作业虽然可以不占据连续的存储区，但是每次仍然要求一次全部进入内存。因此，如果作业很大，其存储需求大于内存，仍然存在小内存不能运行大作业的问题。,作 业,假定某页式管理系统主存容量为64KB，分成16块，块号分别为0，1，2，,15.某作业有4页，其页号为0，1，2，3，被分别装入主存的2，4，1，6号块。问： （1）该作业的总长度是多少字节 （2）求逻辑地址为3100的指令所在的内存块号及其偏移量 （3）给出逻辑地址（0，100），（1，50），（2，0），（3，60），请计算出相应的内存地址,覆盖和交换技术,覆盖和交换技术都是实现存储管理技术。主要用来解决在较小的存储空间中运行大作业时遇到的矛盾问题。,3.6.5 什么是虚拟存储器,（1）覆盖技术 覆盖：是指同一主存区可以被不同的程序段重复使用。 通常一个作业由若干个功能上相互独立的程序段组成，让那些不会同时执行的程序段共用同一个主存区。因此，我们把可以相互覆盖的程序段叫做覆盖。而把可共享的主存区叫做覆盖区。,子程序D(200k),子程序F(300k),主程序A (200k),覆盖区1 (400k),覆盖 区0 (500k),内 存 区,用 户 的 结 构 化 程 序 区,子程序B(500k),子程序 C(300k),子程序E(400k),主程序A(200k),节 省 多 少 空 间 ？,覆盖技术要求用户指明作业各模块间的调用结构，增加用户的负担。目前主要用于小型系统的系统程序的内存管理上，MS-DOS系统中，也采用了覆盖技术。,交换技术 交 换：就是系统根据需要把主存中暂时不运行的某个(或某些)作业部分或全部移到外存，而把外存中的某个(或某些)作业移到相应的主存区，并使其投入运行。所以，交换技术也叫对换或滚进滚出（roll-in,roll-out）。,虚 拟 存 储 器,采用某种技术，使得用户感觉到的内存容量比其实际容量大的多的逻辑模型,基本思想：是用软件技术（动态地址映像机构）和硬件（辅存）技术把内存与外存这两级存储器当成一级存储器来用，从而给用户提供了一个比内存也比任何应用程序大得多的虚拟存储器,磁盘,内 存,CPU,程序部分装入,虚拟内存的最大容量，受两个条件的制约： 指令中地址长度 辅助存储器容量,32位的地址结构所能提供的最大 虚拟内存容量为,思考,虚拟存储器的最大容量是由（ ）决定的？ A 内、外存容量之和 B 计算机系统的地址结构 C 作业的相对地址空间 D 作业的绝对地址空间 32位地址结构最大可表示（ ）虚拟内存容量,B,2,32,4G,是基于分页式存储管理的一种虚拟存储器。请求分页存储器技术是在简单分页技术基础上发展起来的，二者根本区别在于请求分页提供虚拟存储器。,3.6.6 页式虚拟存储管理的实现,实现原理： 它与分页式存储管理相同的是：,内存空间划分“块” 逻辑地址空间划分成“页” 以“块”为单位进行分配,它与分页式存储管理不同的是：运行时，并不把整个作业程序一起都装入到内存，而只装入目前要用的若干页，其他页仍然保存在辅助存储器里。,不完全装入,运行过程中，逻辑地址被转换成数对：（页号，页内位移）。根据页号查页表时，如果该页已经在内存，则访问内存，继续运行；如果该页不在内存，运行就无法继续下去。产生“缺页中断”，此时，就要根据该页号把它从辅助存储器里调入内存，以保证程序的运行。,逻辑地址A,（p, d),查页表,查页表，在内存否？,否,缺页中断,得块号，然后与偏移量拼接的物理地址,是,页表机制,1：在内存 0：不在内存,页 号,标 志,主存块号,磁盘上的位置,地址变换和缺页中断的处理,缺页中断,页面淘汰,2. 页面调度 “页面调度” ：也称为“页面淘汰”，指发生缺页时，如果内存中已经没有空闲块，那么就必须在内存中选择一页，然后把它调出内存，以便为即将调入的页面让出块空间，这一过程称为页面调度。,页面调度是由 “缺页中断”引起的！,“缺页中断”一定会引起的页面淘汰？,缺页中断不一定引起页面淘汰。只有当内存中没有空闲块时，缺页中断才会引起页面淘汰。 常见的页面淘汰策略有：“先进先出页面淘汰算法”、“最近最久未使用页面淘汰算法”、“最近最不经常用页面淘汰算法”以及“最优页面淘汰算法”等。,先进先出页面淘汰算法 先进先出（FIFO）页面淘汰算法：是进行页面淘汰时，总是把最早进入内存的页面作为淘汰的对象。 比如，给出一个作业运行时的页面走向为：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，设分配给该作业三个内存块），把开始的三页先装入内存，分析按FIFO算法页面装入情况,页面走向 7 0 1 2 0 3 0 4,K,中断计数,7,0,1,2,7,0,1,2,3,2,3,0,4,3,0,页面走向 4 2 3 0 3 2 1 2,中断计数,4,3,0,4,2,0,4,2,3,0,2,3,0,2,3,0,2,3,0,1,3,0,1,2,缺页率缺页中断次数访问页面总数100,缺页率=9 15 100%=60%,最近最久未用页面淘汰算法 最近最久未用（LRU:Least Recently Used)页面淘汰算法是在进行页面淘汰时，检查这些淘汰对象的被访问时间，总是把最长时间未被访问过的页面淘汰出去。,在实际应用中，用页号队列的方法，队列中存放当前在主存中的页，规定队首总是为最久未被访问的页面，而队尾总是最近刚访问的页。当发生缺页中断时总是选择队首所指示的页面调出即可。,不需要 指针,LRU算法分析情况,页面走向 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2,中断计数,7,0,1,7,0,1,2,7,0,1,2,0,2,3,0,2,3,0,3,4,0,4,2,3,4,2,3,2,0,3,2,0,3,2,0,3,2,1,3,2,1,缺页率=7 15 100%=46.7%,最近最不经常使用页面调度算法 最近最少用（LFU）页面淘汰算法的着眼点是考虑内存块中页面的使用频率，它认为在一段时间里使用得最多的页面，将来用到的可能性就大。因此，当要进行页面淘汰时，总是把当前使用得最少的页面淘汰出去。,练习1,给出一个作业运行时的页面走向为：1、2、3、4、1、2、5、1、2、3、4、5（设分配给该作业三个内存块），假设起始未装入任何页，分析页面装入情况,缺页率:75%,缺页中断次数,抖 动,先进先出FIFO页面调度算法,“抖动”：又称为“颠簸”，指由于使用的淘汰的策略不合理，出现刚被淘汰出去的页面很快又被访问，又把它从外存调入，不久再一次被淘汰，再访问，再调入。如此频繁地反复进行，使整个系统一直陷于页面的调入、调出，以致大部分CPU时间都用于处理缺页中断和页面淘汰，很少能顾及到用户作业的实际计算的现象。 抖动使得整个系统效率低下，甚至趋于崩溃，是应该极力避免和排除的,最优页面淘汰算法（OPT） 如果已知一个作业的页面走向，那么要进行页面淘汰时，应该把以后不再使用的或在最长时间内不会用到的页面淘汰出去。,页面走向 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2,中断计数,缺页率=515 100%=33.3%,7,0,1,看将来,2,0,1,2,0,1,2,0,3,2,0,3,2,4,3,2,4,3,2,4,3,2,0,3,2,0,3,2,0,3,2,1,3,2,1,3,52.某采用页式存储管理的系统接受了一个共7页的作业，该作业执行时依次访问的页面是：1，2，3，4，2，l，2，3，2，4，5，2，7，6，4。假设系统只给该作业3个主存工作块，且先将开始三页依次装入主存。当分别采用先进先出(FIFO)和最近最久未使用(LRU)调度算法时，作业执行过程中会产生多少次缺页中断?并依次写出每次中断后应淘汰的页。, 页式虚拟存储管理的特点 它不仅打破了占据连续存储区的禁锢，而且打破了要求作业全部进入内存的禁锢。由于它能够向用户作业提供虚拟存储器，从而解决了小内存与大作业的矛盾。,某页式管理系统，页长为4KB,思考逻辑地址划分情况？,补充了解 分段存储管理 分段基本思想 把作业按照逻辑关系加以组织、划分成若干段，并按照这些段来分配内存。所以，段是一组逻辑信息的组合。 例如，有主程序段main、子程序段P、数据段D和栈段S等。如图所示。,系统常常为每一段规定一个内部段名。内部段名实际上是一个编号，称为段号。 每个段号从0开始编址，并采用一段连续的地址空间。段的长度由该段所包含的逻辑信息的长度决定，因而各段的长度不等。, 地址结构 由于整个作业的地址空间分成多段，所以，逻辑地址要用两个成分来表示：段号s和段内地址d。分段系统中所用的地址结构如下图所示。,二维地址结构, 内存分配 在分段存储管理中内存以段为单位进行分配，每个段单独占用一块连续的内存分区。各分区的大小由对应段的大小决定，段与段之间可以连续,也可以不连续.,在分段管理中（ ）。 A. 以段为单位分配，每段是一个连续存储区 B. 段与段之间必定不连续 C. 段与段之间必定连续 D. 每段是等长,A, 段表和段表地址寄存器 为了能找出每个逻辑段所对应的物理内存中分区的位置，系统为每个进程建立一个段映射表，简称段表。 每个段在段表中占有一项,段表按段号从小到大顺序排列。,3. 分段的虚拟存储管理 在分段基础上实现的虚拟存储器是以段为单位进行换入、换出的。请求分段在程序运行之前不要调入所有段，只需把当前程序运行所需的几个分段装入内存，就启动程序运行。,不完全 装入,4.5.4 段页式存储管理技术 1 基本原理 （1） 等分内存 把整个内存分成大小相等的内存块，内存块从0开始依次编号。 （2） 作业或进程的地址空间采用分段的方式,块 号,（3） 段内分页： 把每一段划分成若干页。页面的大小与内存块相同，每段的各个页面都分别从0开始依次编号。,段内页号,先分段，然后段内分页,设系统块大小为4KB，分析段内分页情况,0 页,1 页,0 页,0 页,0 页,1 页,1 页,1 页,1 页,（4） 逻辑地址结构 一个逻辑地址示由三部分组成：段号 s 、页号 p 和页内地址 d ，记作v=(s， p， d )。如图所示。,（5） 内存分配 内存的分配单位是内存块。 （6） 段表、页表和段表地址寄存器 为了实现从逻辑地址到物理地址的转换，系统要为每个作业或进程建立一个段表，并且还要为该作业段表中的每一段建立一个页表。,已知： 页表在内存中存放 Windows 2000