第5章 存储管理2

操作系统原理PrinciplesofOperatingSystem,主讲：孔宪君,5.4分段存储管理方式,5.4.1分段存储管理方式的引入一个程序由多个程序段和数据段组成，程序通过分段划分为多个模块，如代码段、数据段、共享段。分段(segment)就是支持这种用户观点的内存管理方案。每个程序都有由一组段组成。每个段都有名称和长度。逻辑地址空间是二维的地址空间。逻辑地址由两个元素组成：段号s|段内偏移d。,5.4.2分段存储管理系统的基本原理,进程的地址空间被划分成若干段，每个段定义一个完整逻辑意义的信息，段号从0开始编号。进程加载时，操作系统为所有段分配其所需内存，段与段之间不必连续，物理内存的管理采用分区式存储管理方法。,分段存储管理具体如下：逻辑分段段是一组逻辑信息的集合。将一个进程按照其不同的功能，分成若干个相对独立的段，为每个段命名，并编排段号。内存分配管理方法段为内存分配的基本单位，为每段分配连续的内存储存空间，每段的逻辑地址由0地址开始连续编址，段与段之间是离散的，物理内存的管理采用分区式存储管理方法。段表为了实现分段管理，系统为每个进程建立一个段表，用于描述组成进程地址空间的各个段在内存的物理位置，来实现进程的逻辑地址空间到内存存储空间的映射。段表的表项称为段描述子，一般包括：段号s、段长、段基址(baseaddress)等。,5.4.3分段存储管理地址变换机构,如图所示，为了完成进程逻辑地址到物理地址的映射，CPU会查找内存中的段表，由段号得到段的基址，加上段内偏移，得到实际的物理地址。,5.4.4段的共享,5.4.5分段与分页系统的区别,页帧是信息的物理单位，分页是系统管理的需要，以解决内存的外碎片问题；段是信息的逻辑单位，分段的目的是为了更好地满足用户的需要，但分段存储管理存在外碎片问题。页的大小是固定的，由系统硬件决定；段的长度是不固定的，大小由用户决定。分页系统进程的地址空间是一维的，即该地址空间是单一的线性地址空间，程序员只需利用一个标识符，即可表示一个地址；分段系统进程的地址空间是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内偏移。分页对于用户是透明，它仅仅用于对内存的管理；分段则对用户是可见的。分段存储管理可以利用段的共享来实现内存共享；分页存储管理较难实现内存共享。,5.4.6段页式存储管理,分页管理和分段管理各有所长，将分页与分段结合形成段页式存储管理技术。在段页式系统中，一个进程的地址空间被分成若干段，每段又被分成若干固定大小的页面。,9,段页式存储管理基本原理如下：进程按其逻辑意义分段。段内分页。内存实施分页存储管理，以页帧为单位分配内存。逻辑地址结构为三元组：段号s，页号p，偏移量d，V（s|p|d）,实现段页式存储管理需要两个重要的数据结构，即段表和页表。系统为每个进程建立一个段表。其段描述子如下：段号、页表始址、页表大小、存取控制、状态等。每个段建立一个页表。其页描述子如下：页号、帧号、访问位、修改位等。,2.段页式存储管理地址变换过程,如图所示段页式存储管理地址变换过程如下：从段表寄存器读取段表始址，找到段表。段号段表始址，得到段描述子地址。从段描述子读取页表始址，页号页表始址，得到页描述子地址。从页描述子读取帧号。由帧号f和偏移量拼成物理地址。在段页式存储管理中,CPU每次访问一个在内存中的操作数，需要要三次访问内存，第一次访问内存段表取得页表始址，第二次访问页表取得帧号，形成物理地址，第三次访问内存中的操作数。,12,段页式存储管理地址变换过程,5.5虚拟存储器,CPU执行的指令和数据必须在物理内存中第一种方法是将整个程序放进内存中第二种方法是将正在执行的部分程序放进内存中。覆盖技术允许程序部分装入，但是需要程序员做一些额外的工作。虚拟存储器（virtualmemory）技术允许程序部分装入内存，这种方案的一个很大的优点就是程序的逻辑地址空间可以比物理内存大。而且，虚拟存储器将内存抽象成一个巨大的、统一的存储空间，将用户看到的逻辑内存与物理内存分开，这种技术允许程序员不受内存存储的限制。,14,5.5.1局部性原理,时间局部性，一条指令的一次执行和下次执行，一个数据的一次访问和下次访问都集中在一个较短时期内。空间局部性，当前执行的指令和其邻近的几条指令，当前访问的数据和邻近的数据都集中在一个较小区域内。进程中有些部分是彼此互斥的，不是每次运行时都能执行到。,15,5.5.2虚拟存储器的基本原理,在进程装入时，不必将其全部装入内存，而只要将当前需要执行的部分页或段装入内存，就可以让进程执行。在进程执行过程中，如果需要执行的指令或访问的数据尚未在内存(称为缺页或缺段)，则由操作系统将相应的页或段调入内存，然后继续执行进程。操作系统可以将内存中暂时不使用的页或段调出，保存在外存上，从而腾出空间存放将要装入的进程以及将要调入的页或段。,所谓虚拟存储器就是将用户逻辑内存与物理内存分离，具有请求调入功能和置换功能，为用户提供了一个存储容量比实际内存大得多的存储器管理系统。,5.5.3虚拟存储器的分类虚拟存储器技术一般可以分为三类：请求分页存储管理请求分页存储管理在分页存储管理的基础上，增加了请求调页等功能。与分页存储管理不同，请求分页管理系统只需进程的部分页面调入内存即可以运行。请求分段存储管理请求分段存储管理在分段存储管理的基础上，增加了请求调段或段的动态链接等功能。地址空间中各程序段在运行时并不全部装入内存，而是调入一个或少数几个程序段运行，在运行过程中需要调用到哪段时，就根据该段长度在内存分配一个连续的分区给它使用。若内存中没有足够大的空闲分区，则考虑进行段的紧凑或将某段淘汰出去。这种存储管理技术称为请求分段存储管理。请求段页式存储管理。请求段页式存储管理是请求分页和请求分段存储管理的结合。请求段页式存储管理的内存分配单位是帧。逻辑地址是由段号、段内页号、页内偏移地址三部分组成的。在地址变换的过程中会产生缺段中断和缺页中断两种不同类型的中断。,5.5.4虚拟存储器的容量,一个虚拟存储器的容量由以下两个因素决定：虚拟存储器的容量受CPU的寻址能力的限制，CPU的寻址能力由计算机CPU地址总线结构确定的，它是影响虚拟存储器最大容量的重要参数。例如：某计算机CPU的地址总线长度为32位，则CPU可以寻址范围是0232-1，即4G。一般来说，虚拟存储器的容量由内存和外存对换区容量之和所确定；有些虚拟存储器技术还要考虑加上进程文件区的容量。很多教材认为“虚拟存储器的容量由内存和外存之和所确定”，这种说法是不正确的，外存的容量可能很大（如200G），不可能全部作为外存对换区，同时虚拟存储器的容量也受CPU的寻址能力的限制。,5.5.5虚拟存储器的特征,一次性和驻留性并非是进程运行所必需的条件，虚拟存储器主要特征如下：离散性。虚拟存储器必须建立在离散分配的基础上，在分页、分段、段页式存储管理的基础上才能实现虚拟存储器。多次性。基于局部性原理，虚拟存储器将一个进程分成多次调入内存，多次性是虚拟存储器最重要的特征。对换性。虚拟性。,20,5.5.6交换区策略、换入策略和置换策略,1.交换区策略2.页面换入策略请求换页(demandpaging)。预换页(prepaging)。3.置换策略固定分配局部置换(fixedallocation，localreplacement)。可变分配全局置换(variableallocation，globalreplacement)。可变分配局部置换(variableallocation，localreplacement)。,5.6请求分页存储管理,5.6.1请求分页存储管理的实现原理内存按分页管理。虚拟地址结构为：虚页号p|偏移量d。根据局部性原理，进程的部分页面装入内存即可运行，进程的全部页面均有机会获得到内存执行的机会。即将要访问的页面不在内存，由缺页中断机构就立即产生中断信号，将缺页装入内存。缺页中断机构由硬件和软件组成。进程运行需要内存页帧，如果内存没有空闲帧时，由页面置换算法将一些老页从内存中淘汰出局，为即将被调入的新页腾出空位。即老页与新页在内外存的对换。,5.6.2请求分页存储管理的实现机制,1页描述子的扩充在请求分页系统中，一般对页描述子进行如下扩充，除了页号对应的帧号外，还增加了状态位、修改位、访问字段、存取控制、外存地址等。状态位用于指示该页是否已经调入了内存，“1”表示该页在内存中，“0”该页不在内存中。若不在内存之中，则产生缺页中断。修改位表示该页调入内存后是否被修改过。“1”表示该页被修改过，“0”相反。访问字段用于记录本页在一定时间内被访问的次数，或记录最近已经有多长时间未被访问。存取控制审定访问权限。外存地址用于指出该页在外存对换区中的地址，供调入该页时使用。,2缺页中断机制在请求分页系统中，CPU硬件一定要提供对缺页中断的支持，根据页描述子中的状态位判断是否产生缺页中断。缺页中断是一个比较特殊的中断，这主要体现在以下两方面：在指令的执行期间产生和处理缺页中断信号。通常的CPU外部中断是在每条指令执行完毕后检查是否有中断请求到达。而缺页中断是在一条指令的执行期间发现要访问的指令和数据不在内存时产生和处理的。一条指令可以产生多个缺页中断。例如，有一条双操作数的指令，每个操作数都不在内存中，当这条指令执行时，将产生多个中断。CPU提供的硬件支持还要体现在当从中断处理进程返回时，能够正确执行产生缺页中断的指令。,3请求分页存储管理的地址变换流程图,4.6.3页面置换算法,页面在内外存之间来回替换叫抖动，抖动会引起不必要的额外开销。1先进先出算法先进先出算法（FIFO）的基本思想是先进入内存的页面，先被换出，总是先淘汰那些驻留在内存时间最长的页面。理由是：最先进入内存的页面不再被访问的可能性最大。可以通过队列来表示各页的装入时间先后。,2最佳置换算算法,最佳页面置换算法(Optimal，OPT)是淘汰永不使用的或是在最长时间内不再被访问的页面。就是说从内存中移出以后不再使用的页面，如无这样的页面，则选择以后最长时间内不需要访问的页，这就是最佳置换法。,3最近最久未使用置换算法,最近最久未使用置换算法(LeastRecentlyUsed，LRU)的基本思想是根据局部性原理，如果某一页被访问了，那么它很可能马上又被访问。反之，如果某一页很长时间没有被访问，那么最近也不太可能会被访问。其实质是，当需要置换一页时，选择在最近一段时间最久未使用的页面予以淘汰。,5.页面缓冲算法,页面缓冲算法(pagebuffering)是对FIFO算法的发展.通过建立置换页面的缓冲，从而有机会找回刚被置换的页面，从而减少系统I/O的开销。页面缓冲算法用FIFO算法选择被置换页，把被置换的页面放入两个链表之一。如果页面未被修改，就将其归入到空闲页面链表的末尾，否则将其归入已修改页面链表。,空闲页面和已修改页面仍在内存中停留一段时间，如果这些页面被再次访问，只需较小开销，就可以返还被访问的页面作为进程的内存页。需要调入新的物理页面时，将新页面内容读入到空闲页面链表的第一项所指的页面，然后将第一项删除。当已修改页面达到一定数目后，再将他们一起调出到外存，然后将他们归入空闲页面链表，这样能大大减少I/O操作的次数。该方法容易实现，性能较好，WindowNT内核系列操作系统就使用该方法。,6.时钟置换算法,时钟置换算法(ClockAlgorithm)需要为每一个装入内存的页面设置一个使用位(UseBit，简称为U位)，当某个页面被装入内存时，其U位被置为0，每当某个页面被进程引用时，相应的U位将被置为1。同时，系统还把置换范围内的所有页面通过链接指针组织成一个循环队列，并为该队列设置一个扫描指针。扫描指针用于记录上一次进行页面置换时被置换页面所在位置的下一个位置。当需要进行页面置换时，系统将移动扫描指针查找置换范围内一个U位为0的页面，即自上次置换以来未被使用过的页面。,31,如果当前扫描指针所指向的页面的U位为0，那么系统将把该页面作为被置换页面。并将扫描指针移到下一个页面位置，停止搜索。如果当前扫描指针所指向的页面的U位为1，那么系统将把该页面的U位设置为0，扫描指针移到下一个位置，继续搜索。如果该循环队列中所有页面的U位都为1，那么，扫描指针将移动一圈以后回到原处。这时，循环队列中的所有页面的U位都为0，选择淘汰扫描指针最初指向的页面，算法终止。可见，该算法中的扫描指针类似于时钟指针，进行页面置换时，该指针在页面组成的环行队列中逐位地移动，故形象地称之为Clock置换算法。,5.6.4工作集模型,1.工作集一个进程在时间t的工作集可以形式化的定义为：对于给定的访问序列选取定长的区间，落在工作集窗口中的页面集合称为工作集。WS（t）=在时间t-到t之间所访问的一串页面的集合其中，为工作集窗口尺寸。如图所示，工作集模型的例子中，=10