操作系统原理(ch5)

2009-4-7,1,操作系统原理,张德海E-mail:dhzhang2009年4月7日,云南大学软件学院,2009-4-7,2,第五章存储管理(MemoryManagement),5.1存储管理的功能5.2分区存储管理5.3覆盖与交换技术5.4页式管理5.5段式与段页式管理5.6局部性原理和抖动问题,2009-4-7,3,基本概念-存储器的分类,内存储器（简称内存、主存、物理存储器）处理机能直接访问的存储器。用来存放系统和用户的程序和数据，其特点是存取速度快，存储方式是以新换旧，断电信息丢失。价格昂贵,外存储器（简称外存、辅助存储器）处理机不能直接访问的存储器。用来存放用户的各种信息，存取速度相对内存而言要慢得多，但它可用来长期保存用户信息。在文件系统中介绍。价格便宜,2009-4-7,4,基本概念-内存的物理组织,物理地址：把内存分成若干个大小相等的存储单元，每个单元给一个编号，这个编号称为内存地址（物理地址、绝对地址、实地址），存储单元占8位，称作字节（byte）。物理地址空间：物理地址的集合称为物理地址空间（主存地址空间），它是一个一维的线性空间。,2009-4-7,5,程序地址：用户编程序时所用的地址（或称逻辑地址、虚地址），基本单位可与内存的基本单位相同，也可以不相同。程序地址空间（逻辑地址空间、虚地址空间）:用户的程序地址的集合称为逻辑地址空间，它的编址总是从0开始的，可以是一维线性空间，也可以是多维空间。,基本概念-程序的逻辑结构,2009-4-7,6,5.1存储管理的功能,1.虚拟存储器2.地址变换3.内外存数据传输的控制4.内存的分配与回收5.内存信息的共享与保护,2009-4-7,7,5.1.1虚拟存储器,1、问题的提出物理存储器的结构是个一维的线性空间，容量是有限的。用户程序结构：一维空间一个用户程序就是一个程序，并且程序和数据是不分离的；二维空间程序由主程序和若干个子程序（或函数）组成，并且程序与数据是分离的；n维空间即一个大型程序，由一个主模块和多个子模块组成，其中，各子模块又由主程序和子程序（或函数）组成。用户程序的大小，可能比内存容量小，也可能比内存容量大，有时候要大得多。,2009-4-7,8,5.1.1虚拟存储器,如何将与物理内存结构不同，且大于物理内存容量的用户程序装入运行？这就是提出研究虚拟存储器的原因，或称为虚拟存储技术发展的原动力。,2009-4-7,9,5.1.1虚拟存储器,虚拟存储器的实现基础：实验证明，在一个进程的执行过程中，其大部分程序和数据并不经常被访问。实现原理：把进程中那些不经常被访问的程序段和数据放入外存中，待需要访问它们时再将它们调入内存。,2009-4-7,10,引入虚拟存储技术的好处,大程序：可在较小的可用内存中执行较大的用户程序；大的用户空间：提供给用户可用的虚拟内存空间通常大于物理内存(realmemory)并发：可在内存中容纳更多程序并发执行；易于开发：不会影响编程时的程序结构,2009-4-7,11,5.1.1虚拟存储器概念,将进程中的目标代码、数据等的虚拟地址（又称逻辑地址，相对地址）组成的虚拟空间称为虚拟存储器（Virtualmemory）。虚拟存储器不考虑物理存储器的大小和信息存放的实际位置，只规定每个进程中互相关联的信息的相对位置。每个进程都有自己的虚拟存储器，通常是一个以0地址为始地址的一维（或多维）虚拟地址空间。从虚拟地址空间到物理地址空间需要进行地址变换。,思考：虚拟存储器是一个静态概念还是一个动态概念？,2009-4-7,12,5.1.2地址变换,源程序,编译链接,虚拟空间,地址转换,物理存储器,物理地址空间是一维的，而虚拟地址空间可以是一维的，也可以是多维的。当程序装入内存时,操作系统要为该程序分配一个合适的内存空间，由于程序的逻辑地址与分配到内存物理地址不一致,而CPU执行指令时，是按物理地址进行的，所以要进行地址转换。,2009-4-7,13,5.1.2地址变换,地址映射：将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址。地址变换涉及两个问题：虚拟空间的划分地址重定位（地址映射）地址重定位的方法：静态地址重定位动态地址重定位,2009-4-7,14,1.静态地址重定位(staticaddressrelocation),静态地址重定位是在程序装入内存时，完成从逻辑地址到物理地址的转换的。在一些早期的系统中都有一个装入程序（加载程序），它负责将用户程序装入系统，并将用户程序中使用的访问内存的逻辑地址转换成物理地址。如下图所示。,2009-4-7,15,1.静态地址重定位(staticaddressrelocation),评价:优点：实现简单，不要硬件的支持。缺点:(1)程序一旦装入内存，移动就比较困难。(2)有时间上的浪费。(3)在程序装入内存时要将所有访问内存的地址转换成物理地址。(4)无法实现虚拟存储器。,2009-4-7,16,动态地址重定位是在程序执行过程中，在CPU访问内存之前，将要访问的程序或数据地址转换成内存地址。动态地址重定位依靠硬件地址变换机构完成：地址重定位机构需要一个（或多个）基地址寄存器BR和一个（或多个）程序虚拟地址寄存器VR。内存地址MR与虚拟地址的关系为：MR=BR+VR。,2.动态地址重定位(dynamicaddressrelocation),2009-4-7,17,2.动态地址重定位,1200,3456,LOADA200,2009-4-7,18,2.动态地址重定位的特点,动态地址映射是由硬件在执行时完成的，程序中不执行的程序就不做地址映射的工作，这样节省了CPU的时间；重定位寄存器的内容由操作系统用特权指令来设置，比较灵活；实现动态地址映射必须有硬件的支持，并有一定的执行时间延迟。现代计算机系统中都采用动态地址映射技术；,2009-4-7,19,2.动态地址重定位的特点（续）,可以对内存进行非连续分配；可以实现虚拟存储器；有利于程序段共享。,2009-4-7,20,5.1.3内外存数据传输的控制,控制内存和外存之间的数据流动的办法：用户程序控制主要由用户程序以覆盖技术进行内外存的数据交换。操作系统控制交换方式、请求调入方式（ondemand）和预调入方式（onprefetch）,2009-4-7,21,5.1.3内外存数据传输的控制,交换方式：由操作系统把那些在内存中处于等待状态的进程换出内存，而把那些等待事件已发生，处于就绪状态的进程换入内存。请求调入方式：在程序执行时，如果所要访问的程序或数据段不在内存中，则操作系统自动地从外存将有关的程序段和数据段调入内存。预调入方式：由操作系统预测在不远的将来会访问到的那些程序段和数据段部分，并在它们被访问之前系统选择适当的时机把它们调入内存。,2009-4-7,22,5.1.4内存的分配与回收,存储管理模块要为每一个并发执行的进程分配内存空间，当进程执行结束时，要及时地回收该进程所占用的内存资源，以便给其他进程分配空间。,2009-4-7,23,5.1.4内存的分配与回收,内存分配与回收的策略：分配结构：登记使用情况，供分配程序使用的表格与链表。放置策略：确定调入内存的程序和数据在内存中的位置。交换策略：在需要将某个程序段和数据调入内存时，确定把内存中哪些程序段和数据调出内存。调入策略：外存中的程序段和数据按什么控制方式进入内存。回收策略：确定回收时机和对所回收的内存区和已存在的内存空闲区进行调整。,2009-4-7,24,5.1.5内存信息的共享与保护,在多道程序设计的环境下，系统中有系统程序和多个用户程序同时存在，并且可能共享程序和数据，如何保证用户程序不破坏系统程序，用户程序之间不相互干扰？这就是存储保护所要解决的问题。常用的存储保护有三种：硬件法：上下界保护法。软件法：保护键法。软件与硬件结合：界限寄存器与与CPU用户态或核心态工作方式结合。,2009-4-7,25,1.上下界寄存器保护法,上下界寄存器保护法是一种硬件保护法：为每一个进程设置一对装有程序起始地址和结束地址的上下界寄存器，在程序执行中，对内存的访问始终对所访问的地址进行检查。,2009-4-7,26,1.上下界寄存器保护法,例：有一程序装入内存的首地址是500，末地址是1500，访问内存的逻辑地址是500、345、1000。下界寄存器：500上界寄存器：1500逻辑地址装入内存的首地址物理地址1、5005001000500100015002、34550084550084515003、1000500150050015001500,2009-4-7,27,2.保护键法,保护键法是一种软件保护法：为每一个被保护的存储块分配一个单独的保护键，在程序状态字中则设置相应的保护键开关字段，对不同的进程赋予不同的开关代码和与被保护的存储块中的保护键进行匹配。,2009-4-7,28,2.保护键法举例,2K,4K,6K,内存,正确访问：LOAD15000非读保护STORE25200开关字-键匹配非正确访问LOAD12500出错，开关字-键不匹配,开关字节,当前程序状态字,2009-4-7,29,3.界限寄存器与CPU工作方式结合,在这种方式下，用户态进程只能访问那些在界限寄存器所规定的的内存区域，而核心态进程则可以访问整个内存地址空间。UNIX系统就是采用这种保护方式。,2009-4-7,30,5.2分区存储管理,5.2.1分区管理的基本原理：分区管理是把内存划分成若干个大小不等的区域，以连续存储各进程的程序和数据，除操作系统占用一个区域之外，其余由多道环境下的各并发进程共享。分区管理是多道程序设计下的一种最简单的存储管理方法。分区管理的方法：固定分区法动态分区法,2009-4-7,31,1.固定分区法,固定分区方法：把内存空间分成若干个大小不等的区域，称为分区。每个用户程序（作业、进程）调入内存后，占用其中一个分区，程序运行完成后释放该分区。操作系统占用其中一个分区。特点：适用于多道程序系统和分时系统支持多个程序并发执行难以进行内存分区的共享。问题：可能存在内碎片和外碎片。内碎片：占用分区之内未被利用的空间外碎片：占用分区之间难以利用的空闲分区（通常是小空闲分区）。,1.固定分区法,0K,20K,28K,60K,124K,256K,第1分区,第2分区,第3分区,第4分区,(a)分区说明表,(b)内存状态,2009-4-7,33,2.动态分区法,动态创建分区：在装入程序时按其初始要求分配，或在其执行过程中通过系统调用进行分配或改变分区大小。优点：没有内碎片。缺点：有外碎片；如果大小不是任意的，也可能出现内碎片。,2009-4-7,34,2.动态分区法内存的初始分配,进程A8K,进程B16K,进程C64K,进程D124K,OS,进程A,OS,进程A,进程B,OS,进程A,进程B,进程C,OS,进程A,进程B,进程C,进程D,2009-4-7,35,举例：动态分区法的内存分配变化,进程E(50K)F(16K)进入内存,进程B(16K)D(124K)完成,2009-4-7,36,2.动态分区法数据结构,动态分区法也使用分区说明表、可用表、自由链、请求表等数据结构。可用表的每个表目记录一个空闲区自由链是利用每个内存空闲区的头几个单元存放本空闲区的大小及下一个空闲区的起始地址，从而把所有空闲区链接起来，便于分配。请求表的每个表目描述请求内存资源的作业或进程号以及所请求的内存大小。,2009-4-7,37,可用表、自由链及请求表,(a)可用表,(b)自由链,(c)请求表,2009-4-7,38,5.2.2分区的分配与回收,固定分区的分配与回收动态分区的分配与回收,2009-4-7,39,1.固定分区的分配与回收,分配：存储管理程序根据请求表查询分区说明表，从中找出一个满足要求的空闲分区，并将其分配给申请者。回收：当进程执行完毕，不再需要内存资源时，管理程序将对应的分区状态置为未使用。,2009-4-7,40,固定分区分配算法,2009-4-7,41,2.动态分区的分配与回收,主要解决三个问题：(1)对于请求表中的要求内存长度，从可用表或自由链中寻找出合适的空闲区分配程序；(2)分配空闲区之后，更新可用表或自由链；(3)进程或作业释放内存资源时，和相邻的空闲区进行链接合并，更新可用表或自由链。,2009-4-7,42,动态分区的分配算法,最先适应法（firstfitalgorithm）最佳适应法（bestfitalgorithm）最坏适应法（worstfitalgorithm）以上三种方法要求可用表或自由链按不同的方式排列。,2009-4-7,43,(1)最先适应法,将可用表或自由链按起始地址递增次序排列；一旦找到大于或等于所要求内存长度的分区，则结束探索。从所找到的分区中划出所要求的内存长度给用户；把余下的部分进行合并（如果有相邻空闲区存在）后留在可用表中。,2009-4-7,44,最先适应法算法流程,请求SIZE大小的分区,从空闲区表第一项顺序查找,表结束吗,该空闲区长度SIZE,该空闲区长度SIZE,从可用表中移去该表项，调整可用表,返回分配起始地址,无法分配,取下一表项,是,是,是,否,否,否,从该空闲区中截取所需大小，修改可用表,2009-4-7,45,(2)最佳适应法,将可用表或自由链按从小到大的递增次序排列；找到第一个大于或等于所要求内存长度的分区，则停止查找。从所找到的分区中划出所要求的内存长度给用户；把余下的部分进行合并（如果有相邻空闲区存在）后留在可用表中。,2009-4-7,46,(2)最坏适应法,将可用表或自由链按从大到小的递减次序排列；找到第一个大于或等于所要求内存长度的分区，则停止查找。若可用表或自由链的第一项长度小于所要求的，则分配失败。从所找到的分区中划出所要求的内存长度给用户；把余下的部分进行合并（如果有相邻空闲区存在）后留在可用表中。,2009-4-7,47,几种分配算法的比较,2009-4-7,48,2.动态分区分区回收与拼接,当进程执行结束时，存储管理程序要收回已使用完毕的分区，并将这个空闲区插入可用表或自由链。为提高内存利用率，要对相邻的空闲区进程拼接，从而得到更大的空闲区。,2009-4-7,49,空闲区的合并,四种可能的空闲区相邻情形：,(a)上下相邻区都是空闲区,(b)上相邻区是空闲区,(c)下相邻区是空闲区,(d)上下相邻区都不是空闲区,2009-4-7,50,5.2.3有关分区管理其他问题的讨论,1.关于虚拟存储器的实现分区管理实现了每个用户可以自由编程的虚拟空间；无法实现容量只受内存和外存容量之和的限制的虚拟存储器；每个用户进程所需内存容量受到分区大小的限制。,2009-4-7,51,5.2.3有关分区管理其他问题的讨论,2.关于内存扩充可以使用覆盖和交换的内存扩充技术进行内存扩充。,2009-4-7,52,5.2.3有关分区管理其他问题的讨论,3.关于地址变换和内存保护可利用动态地址重定位的方法实现虚拟地址到物理地址的转换；可利用上下界寄存器对分区地址进行保护，也可利用保护键法进行内存保护。,2009-4-7,53,5.2.3有关分区管理其他问题的讨论,4.分区存储管理的主要优缺点：优点：实现了内存共享，有利于多道程序设计，提高了内存利用率；硬件支持少，管理算法简单，容易实现。缺点：内存利用率仍不高，小碎片难以利用；进程大小受分区大小限制；难以实现分区间的信息共享。,2009-4-7,54,5.3覆盖和交换技术,覆盖技术主要用于早期的操作系统中；交换技术仍用于今天的操作系统。,2009-4-7,55,5.3.1覆盖技术,引入：其目标是在较小的可用内存中运行较大的程序。常用于多道程序系统，与分区存储管理配合使用。原理：一个程序的几个代码段或数据段，按照时间先后来占用公共的内存空间。将程序的必要部分（常用功能）的代码和数据常驻内存；可选部分（不常用功能）在其他程序模块中实现，平时存放在外存中（覆盖文件），在需要用到时才装入到内存；不存在调用关系的模块不必同时装入到内存，从而可以相互覆盖。(即不同时用的模块可共用一个分区),2009-4-7,56,注：另一种覆盖方法：(100K)A(20K)占一个分区：20K；B(50K)、D(20K)和E(40K)共用一个分区：50K；F(30K)和C(30K)共用一个分区：30K；,覆盖技术,2009-4-7,57,5.3.1覆盖技术,缺点：编程时必须划分程序模块和确定程序模块之间的覆盖关系，增加编程复杂度。从外存装入覆盖文件，以时间延长来换取空间节省。,2009-4-7,58,5.3.2交换技术,引入：多个程序并发执行，可以将暂时不能执行的程序送到外存中，从而获得空闲内存空间来装入新程序，或读入保存在外存中而目前到达就绪状态的进程。交换单位为整个进程的地址空间。常用于多道程序系统或小型分时系统中，与分区存储管理配合使用。又称作对换或滚进/滚出(roll-in/roll-out)；程序暂时不能执行的可能原因：处于阻塞状态，低优先级（确保高优先级程序执行）；,2009-4-7,59,5.3.2交换技术,原理：暂停内存中执行的进程，将整个进程的地址空间保存到外存的交换区中（换出swapout），而将外存中由阻塞变为就绪的进程的地址空间读入到内存中，并将该进程送到就绪队列（换入swapin）。,2009-4-7,60,换出过程SWAPOUT的描述,Swapout(i):Beginlocalmm.basebasei;m.ceillingbasei+sizei;m.direction“out”;m.destinationbaseoffreeareaonswapareabackupstorebaseim.destination;send(m,i),devicequeue);end,2009-4-7,61,换入过程SWAPIN的描述,Swapin(i):Beginlocalmm.basebasei;m.ceillingbasei+sizei;m.direction“in”;m.sourcebackupstorebaseisend(m,i),devicequeue);end,2009-4-7,62,5.3.2交换技术,优点：增加并发运行的程序数目，并且给用户提供适当的响应时间；编写程序时不影响程序结构缺点：对换入和换出的控制增加处理机开销；程序整个地址空间都进行传送，没有考虑执行过程中地址访问的统计特性。考虑的问题：程序换入时的重定位；减少交换中传送的信息量，特别是对大程序；对外存交换区空间的管理：如动态分区方法；,2009-4-7,63,5.4页式管理,提出页式管理的原因：（1）分区管理方式存在着严重的碎片问题使得内存的利用率不高。（2）进程的大小仍受分区大小或内存可用空间的限制。（3）分区管理不利于程序段和数据的共享。,2009-4-7,64,5.4.1页式管理的基本原理,各进程的虚拟地址空间被划分成若干个长度相等的页（page）。页长的划分和内存外存之间数据传输速度以及内存大小等有关，一般为1-4K。物理内存空间也按页的大小划分为页面（pageframe）。这些页面为系统中的任一进程所共享。页式管理把页式虚拟地址与内存物理地址建立一一对应的页表，并用相应的硬件地址变换机构，来解决离散地址变换。页式管理采用请求调页或预调页技术实现了内外存存储器的统一管理。,2009-4-7,65,5.4.1页式管理的基本原理,经过页划分后，进程的虚地址变为页号P与页内地址w所组成。,2009-4-7,66,5.4.1页式管理的基本原理,分页管理时，用户进程在内存空间中除了在每个页面内地址连续之外，每个页面之间不再连续。第一是实现了内存中碎片的减少，因为作一碎片都会小于一个页面。第二是实现了由连续存储到非连续存储的飞跃，为在内存中局部地，动态地存储那些反复执行或即将执行的程序和数据打下了基础。,2009-4-7,67,5.4.1页式管理的基本原理,页式存储管理要解决如下问题：1、页式存储管理系统的地址映射；2、调入策略；3、淘汰策略；4、放置策略。,2009-4-7,68,5.4.2静态页面管理,静态页面管理方法：在进程开始执行之前，把该作业或进程的程序段和数据全部装入内存的各个页面中，并通过页表（pagemappingtable）和硬件地址变换机构实现虚地址到内存物理地址的地址映射。,2009-4-7,69,5.4.2静态页面管理,1.内存页面分配与回收：管理程序依靠存储页面表，请求表以及页表来完成内存的分配工作。页表：页表的大小由进程或作业的长度决定，每个进程至少拥有一个页表。,基本页表示例,5.4.2静态页面管理,请求表请求表用来确定作业或进程的虚拟空间的各页在内存中的实际对应位置。页表中记录了每个进程的页表起始地址和长度及进程所要求的页面数，以进行内存分配和地址变换。,2009-4-7,71,5.4.2静态页面管理,存储页面表整个系统使用一张存储页面表，它标出了内存中各页面是否已被分配出去，每个单元的一个比特表示一个页面，已分配的页面置1，未分配的置0。此外还记录了未分配页面的总数。存储页面表可以是内存中的一个固定区域。也可以用空闲页面链来表示。,2009-4-7,72,存储页面表位示图,2009-4-7,73,分配算法,请求n个页面,空闲页面表中有n个页面吗？,无法分配,设置页表，将页表始址，页表长度置入请求表中，置状态=已分配,搜索空闲页面表，分配n个页面，并将页面号填入页表中,返回,2009-4-7,74,5.4.2静态页面管理,页面回收：当进程执行完毕时，拆除对应的页表，并把页表中的各页面插入存储页面表即可。,5.4.2静态页面管理地址变换,例：指令Load1,2500的虚地址为100，页表如图，求该指令的物理地址及2500单元的物理地址？(设页的长度为1K),解：指令Load1,2500的虚地址为100，在第0页，其对应的物理页面为2，则其物理地址为：2*1024+100=2148因2500是虚地址，对应的页及页内地址为第2页452单元，其对应的物理页面为第8页452单元，则其物理地址为：8*1024+452=8644如下图所示：,静态页面管理的地址变换,控制寄存器,有效地址,2,452,物理地址,8,452,2148,8644,内存,2009-4-7,77,静态页式管理的特点,优点：解决了分区管理时的碎片问题。缺点：由于静态页式管理要求进程或作业在执行前全部装入内存，如果可用页面数小于用户要求时，该作业或进程只好等待。作业或进程的大小仍受内存可用页面数的限制。,2009-4-7,78,5.4.3动态页式管理,动态页式管理：请求页式管理：当需要执行某条指令而又发现它不在内存时或当执行某条指令需要访问其他的数据或指令时，这些指令或数据不在内存中，从而发生缺页中断，系统将外存中相应的页面调入内存。预调入页式管理：系统对那些在外存中的页进行调入顺序计算，估计出这些页中指令和数据的执行和被访问的顺序，并按此顺序将它们顺次调入和调出内存。,2009-4-7,79,请求页式管理,地址变换过程与静态页式管理时的相同，也是通过页表查出页面号之后，由页面号与页内相对地址相加而得到实际物理地址。请求页式管理需要解决缺页中断问题。为避免重复保存页，需要记录页内的数据是否被修改。,2009-4-7,80,请求页式管理的页表,2009-4-7,81,抖动问题,由于页面置换算法选择不当，导致整个系统的页面调度非常频繁，大部分时间都花在内存和外存之间的来回调入调出上，这个现象称为抖动。,2009-4-7,82,动态页式管理流程图,略,2009-4-7,83,5.4.4请求页式管理中的置换算法,随机淘汰算法(randomglongram)：在系统设计人员无法确定哪些页被访问的概率较低时，随机地选择某个用户的页面并将其换出将是一种明智的作法。轮转法(roundrobin)：轮转法循回地换出内存可用区内一个可被换出的页，无论该页是刚被换进还是已换进内存很长间。先进先出(FIFO)：选择驻留内存时间最长的页淘汰,2009-4-7,84,5.4.4请求页式管理中的置换算法,先进先出(FIFO)：选择驻留内存时间最长的页淘汰。FIFO算法认为先调入的页不再被访问的可能性要比其他页大，因而选择最先调入内存的页换出。实现FIFO算法需要把各个已分配的页面按分配时间顺序链接起来，组成FIFO队列，并设置一个置换指针指向FIFO的队首页面。,2009-4-7,85,FIFO页置换算法,FIFO和RR算法的内存利用率不高，因为这两种算法都基于CPU按线性顺序访问地址空间的假设。事实上，CPU很多时候不按线性方式顺序访问内存，如执行循环语句。FIFO算法可能会产生Belady现象。原因在于没有考虑到程序执行的动态特征。,2009-4-7,86,FIFO算法的Belady现象,在使用FIFO算法时，在未给进程分配它所要求的足够页面数时，有时会出现分配的页面数增多，缺页次数反而增加的奇怪现象，这种现象称为Belady现象。,M(页面分配数),0,缺页次数,M(页面分配数),0,缺页次数,2009-4-7,87,Belady现象举例,正常情况,缺页率：12/17=70.5%,2009-4-7,88,Belady现象举例,正常情况,缺页率：9/17=52.9%,2009-4-7,89,Belady现象举例,Belady现象,缺页率：9/12=75%,2009-4-7,90,Belady现象举例,Belady现象,缺页率：10/12=83.3%,5.4.4请求页式管理中的置换算法,最近最久未使用页面置换算法(leastrecentlyused)：当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。算法主要出发点：如果某页很长时间未被访问，则它在最近一段时间内也不会被访问。算法实现较困难，因为必须为每个页面设置有关的访问记录项，且每次访问都必须更新记录。近似算法：最不经常使用LFU(leastfrequentlyused)：为每个设置访问次数，淘汰访问次数最少的页。最近没有使用NUR：选择最近一个时期内未被访问的页淘汰，只要在页表中设置一个访问位就可以实现。,2009-4-7,92,5.4.4请求页式管理中的置换算法,理想型淘汰算法OPT(Optimalreplacementalgorithm)：该算法淘汰在访问串中将来再也不出现或是在离当前最远的位置上出现的页。特点：无法预测进程的访问串，因而无法实现。,2009-4-7,93,5.4.5存储保护,地址越界保护：硬件寄存器设置受保护的地址范围。存取控制保护：在页表中设置相应的保护位。,2009-4-7,94,5.4.6页式管理的优缺点,优点：有效地解决了碎片问题；提供了内存和外存统一管理的虚拟存储器实现方式，使用户可以利用的存储空间大大增加。缺点：要求有相应的硬件支持；增加了系统开销（如缺页中断处理）；如置换算法选择不当，可能会产生抖动现象；每个进程的最后总有一部分空间得不到利用。,2009-4-7,95,5.5段式与段页式管理,分区管理和页式管理存在的问题：因进程地址空间都是线性的，而共享程序或数据往往按照程序名或数据块调用，所以不同进程之间共享公用子程序和数据变得非常困难。页式管理中，一个页面可能装有两个不同子程序段的指令代码，很难通过共享页面来共享程序段和数据块。链接时，分区管理和页式管理只能采用静态链接，造成CPU开销的浪费。,2009-4-7,96,5.5.1段式管理的基本思想,把程序按内容或过程（函数）关系分成段，每段有自己的名字。一个用户作业或进程所包含的段对应于一个二维的线性虚拟空间，也就是一个二维虚拟存储器。段式管理程序以段为单位分配内存，然后通过地址映射机构把段式虚拟地址转换成实际的内存物理地址。段式管理也采用交换技术扩充内存。,2009-4-7,97,5.5.2段式管理的实现原理,1.段式虚存空间段式管理把一虚地址空间设计成二维结构，即段号S与段内相对地址w。段式管理中的段号与段号之间无顺序关系；段的长度不固定，每个段定义一组逻辑上完整的程序或数据。每个段是一个首地址为零的、连续的一维线性空间。根据需要，段的长度可动态增长。,2009-4-7,98,5.5.2段式管理的实现原理,1.段式虚存空间例：CALLX|转向段名为X的子程序的入口点Y。LOAD1，A|6将段名为A的数组中第6个元素的值读到寄存器1中。STORE1，B|将寄存器1的内容存入段名为B，段内地址为C的单元中,2009-4-7,99,2.段式管理的内存分配与回收,段式管理中以段为单位分配内存，每段分配一个连续的内存区。同一进程包含的各段之间不要求连续。段式管理的内存分配与释放在进程的执行过程中动态进行。,2009-4-7,100,2.段式管理的内存分配与回收,分配步骤：段式管理程序为一个进入内存准备执行的进程分配部分内存；进程根据需要随时申请调入新段和释放老段；管理程序根据情况作出相应处理：如果有空闲区，则按最先适应法、最佳适应法或最坏适应法分配内存，如果没有空闲区，则根据给定的置换算法淘汰访问概率最低的段。,2009-4-7,101,段式管理的段淘汰算法,FIFOLRU及其近似算法需要调入内存的段的长度可能会大于被淘汰的段的长度，这时，应再淘汰另外的段直到满足需要调入段的内存要求时为止。段式管理时，任何一个段的段长都不允许超过内存可用区长度，否则将会造成内存分配出错。段的淘汰或置换算法实际上是缺段中断处理过程的一部分。,缺段中断处理过程,存在不小于X段长的空闲区吗？,合并空闲区以形成长度不小于X段长度的空闲区,按FIFO或LRU或LFU算法反复淘汰老段，以形成一个长度不小于X段长的空闲区,返回,需调入新段X,所有空闲区总和小于X段长吗？,为X段分配内存空闲区,将X段调入内存并改写段表,否,否,是,是,2009-4-7,103,3.段式管理的地址变换,段式地址变换机构完成二维虚拟地址空间向一维物理地址空间的映射。主要数据结构：段表。,2009-4-7,104,动态地址变换,在内存中给定一块固定的区域放置段表。当某进程开始执行时，管理程序首先把该进程的段表始址放入段表地址寄存器。通过访问段表寄存器，管理程序得到该进程的段表始址从而可开始访问段表。由虚地址中的段号s为索引，查段表。若该段在内存，则判断其控制方式是否有错，若正确，则从段表相应表目中查出该段在内存的起始地址，并将其和段内相对地址w相加，从而得到实际物理地址。,段式地址变换过程,段表始址,段表地址寄存器,虚拟地址,段号段内地址,+,内存,3400,3520,段表,0,1,2009-4-7,106,4.段的共享和保护,段式存储管理可以方便地实现内存信息共享和进行有效地内存保护。这是因为段是按逻辑意义来划分的，可以按段名进行访问。,2009-4-7,107,(1)段的共享,在多道环境下，被多个应用程序共享的程序段和数据在内存中只保留一个副本。多个用户进程通过使用相同的段名，在新的段表中填入共享段的起始地址，并置以适当的读写控制权，就可以共享一段逻辑上完整的程序和数据。当多个进程并发执行共享段时，共享段不能被修改，并且不能将正在或将要执行的共享段换出内存，这个机制可以通过在段表中设置共享位来实现。,段式系统中的共享内存副本,段1,段2,段n,进程1的段表,段1,段2,段n,进程2的段表,2009-4-7,109,(2)段的保护,地址越界保护法：利用段表中的段长项与虚拟地址中的段内相对地址比较，确定是否越界。若段内地址大于段长，则系统会产生保护中断。但在允许段长动态增长的系统中，段内相对地址可以大于段长。存取方式控制保护法,2009-4-7,110,5.5.3段式管理的优缺点,优点：提供了内外存统一管理的虚拟存储器的实现；在段式管理中，段长可根据需要动态增长；便于对具有完整逻辑功能的信息段进行共享；便于实现动态链接。,2009-4-7,111,5.5.3段式管理的优缺点,缺点：需要更多的硬件支持，提高了机器成本；仍存在碎片问题；允许段的动态增长会给系统管理带来一定的难度和开销。每个段的长度受内存可用区大小的限制。如果淘汰算法选择不当，也会产生抖动现象。,2009-4-7,112,5.5.4段页式管理的基本思想,段式管理为用户提供了一个二维的虚地址空间，反映了程序的逻辑结构，有利于段的动态增长及共享和内存保护。页式管理有效地克服了碎片，提高了内存的利用率。段页式管理将段式管理和页式管理结合起来，取长补短。,2009-4-7,113,5.5.5段页式管理的实现原理,段页式管理时，将一个进程中所包含的具有独立逻辑功能的程序或数据划分成段，并有各自的段号。对于段中的程序或数据，按照一定大小划分成不同的页。和页式管理一样，最后不足一页的部分仍占一页。,1.段页式管理的虚地址的构成,段页式管理时的进程的虚拟地址由三部分组成：段号s，页号p和页内相对地址d：,s,p,d,w,对程序员而言，虚拟地址仍可视为由段号s和段内相对地址w组成，地址变换机构会把w的高几位解释为页号p，把剩下的部分解释为页内地址d。,2009-4-7,115,1.段页式管理的虚地址的构成,段页式管理中，虚拟空间的最小单位是页而不是段，因此，物理内存就可划分为和页大小相等的页面，且每段所拥有的程序和数据在内存中可以非连续地存放。这样，分段的大小不再受内存可用区的限制。,2009-4-7,116,2.段表和页表,为实现段页式管理，系统必须为每个进程建立一张段表，用于管理内存的分配、释放、缺段处理、存储保护和地址变换等。为每个段建立一张页表，把段中的虚页变换成内存中的实际页面，同时用于缺页中断处理和页面保护等功能。段页式管理中，页表属于段而不属于进程。段表中应有专项指出该段所对应页表始址和页表长度。,段页式管理中段表、页表与内存的关系,段表地址寄存器,第0段页表,第2段页表,段表,内存,2009-4-7,118,3.动态地址变换过程,段页式管理系统中，在内存中辟出一块固定的内存区域存放段表和页表。如果要对内存中的指令或数据进行一次存取，至少需要访问三次以上的内存：第一次：由段表地址寄存器得到段表始址去访问段表，由此取出对应段的页表地址；第二次：访问页表得到所要访问的物理地址；第三次：访问真正的内存物理单元。,2009-4-7,119,3.动态地址变换过程