2-操作系统存储管理.ppt

操作系统存储管理,訾小超,Contents,存储管理的基本概念内存分配的各种算法虚拟存储器的基本概念页式存储管理请求分页多级页表段页式管理Linux的存储管理概述,（一）存储管理的基本概念,1-1为何需要进行存储管理内存是一种硬件资源，存储管理是操作系统的一种主要功能。内存是计算机程序运行的基础，只有将程序读到内存中才能运行。,1-2存储管理的目标利用率高，不会出现或较少出现内存浪费。访问效率高，内存地址定位速度快。访问接口使用方便。解决各进程的内存冲突，同时保证每个进程的存储区域不受干扰。保护自己的存储区域不受非法破坏。在需要的时候，能够方便实现各种形式的内存共享。,1-3地址的基本概念地址：为了便于程序访问内存，需要对内存进行编址，这样每个内存单元都会对应一个地址，程序按地址访问内存两种不同形式的地址：程序内部的符号地址。内存片上的地址。,符号地址、名地址：用变量名来表示访问的数据等。逻辑地址，又叫虚地址，相对地址一般从0开始编制，每个程序的地址空间是独立的绝对地址、物理地址、实地址。真正的内存地址,1-4地址重定位,图21地址变换过程,1-5固定定位方式,1-6动态重定位方式,采用动态重定位方法，程序在装入内存时不必修改程序的逻辑地址值。程序执行期间在访问内存之前，再即时地将逻辑地址变换成物理地址。浮动基地址+相对偏移地址：在执行指令时，若涉及到逻辑地址，则先将该地址送入虚地址寄存器VR，再将BR和VR中的值相加后送入地址寄存器MR，并按MR中的值访问内存。即（MR）=（BR）+（VR）,100,200,0,（二）内存分配的各种算法,2.2.1单一连续区存储管理采用这种存储管理方法，一个作业在运行时要独占整个用户区，当作业的地址空间小于用户区时，余下的内存部分不能利用，从而就白白浪费了。,2.2.2固定分区存储管理,为了支持多道程序设计，在系统初始化时就把存储空间划分成若干个分区，这些分区的大小可以不同，以支持不同的作业对内存大小需求的不同。采用固定分区管理方法，系统要建立如图2-6所示的分区说明表，用以记录每个分区的大小、起始地址和状态等信息。当一个作业需要装入内存运行时，系统就从分区表中找出一个最为合适的分区，分配给该作业。,分区号大小地址状态120K100K已分配240K120K已分配3100K160K未分配4200K260K已分配,操作系统,作业A,作业B,作业C,下界寄存器,上界寄存器,0,100K,160K,120K,图2-6分区说明表和内存分配情况,260K,缺点：对于要运行的作业必须预先申请所需的最大内存，有时比较难以做到，因为作业在运行中根据情况有时需要扩大对内存的需求。另一方面，作业所需内存的大小一般不会刚好接近某个分区大小，从而在一个分区中未被利用的部分就白白地浪费了。在固定分区管理系统中，为了防止用户程序之间的相互干扰以及用户程序对操作系统可能的侵扰，就需要在各分区设置下界（低地址）寄存器和上界（高地址）寄存器，以限制用户程序访问存储区的范围。,2.3可变分区存储管理2.3.1空闲存储区表,可变分区存储管理法并不预先将内存划分成分区，而是等到作业运行需要内存时就向系统申请，从空闲的内存区中“挖”一块出来，其大小等于作业所需内存大小，这样就不会产生“内零头”。管理空闲内存区的数据结构可采用链接法和连续线性表格法。,每一个空闲分区用一个map结构管理：structmapunsignedm_size;char*m_addr;structmapcoremapN;m_size是空闲分区的长度，m_addr是空闲区的起始地址。各个空闲分区按起始地址由低到高顺次登记在空闲存储区表中，m_size为0的表项是空白表目项，它们集中在表的后部。,在系统初始阶段，拥有一块很大的内存空白区，这时空闲存储区表coremap中只需有一项登记该空闲区，其余的coremap表项为空白项，即m_size皆为零。此时情况如图2-7所示。,0,1,N,m_size,m_addr,0,0,空闲区,内存,图2-7空闲分区表的初始状态,随着很多作业的不断申请内存和释放内存，整个存储空间将出现许多大小不等的区域，存储区表和实际的内存空间就可能变成如图2-8所示的情况。,m_size,m_addr,m_size,0,空闲区,内存,图2-8某一时刻空闲分区表的状态,m_addr,m_size,m_addr,已分配区,空闲区,空闲区,可变分区分配算法,可变分区分配算法算法前提：1）链表保存空闲分区，2）初始化：链表上只有一个空闲分区，这个空闲分区等于所有内存地址。3）暂时假定：链表上的空闲分区一直是按地址从低到高的顺序保存。,算法一：首次适应算法算法思想和过程：顺序扫描整个空闲分区链表，找到第一个比所申请内存大的空闲分区。如果所有分区都小于所申请的大小，返回失败把找到的分区一分为二，一块长度等于所申请的内存大小，另一块包含剩下的空间。前一块分配给相应的申请者，后一块如果长度大于零仍作为空闲分区挂在空闲分区链表上。,优缺点：在低地址部分，空闲区会被反复的细分，容易导致很小的碎片出现，这些小碎片可能得不到利用，造成浪费。在高地址部分，较大的空闲分区容易保存下来。回收算法效率高：能方便找到与所回收分区相邻的空闲分区，以执行合并算法。合并后，合适的插入位置也比较容易确定。使用场合：比较适用于各种类型的作业都有，作业长度相差比较大的运行环境。,算法二：循环首次适应算法将各空闲区按地址从低到高的次序组成循环链表。但每次扫描链表，不是从头开始，而是从上次分配查到那一块的后面开始扫描。回收算法：基本同首次算法，但由于是循环链表，不能仅仅通过表项的相邻关系判断是否能够合并。特点：比首次适应算法具有更高的分配速度。经过长时间的运行后，系统中可能比较多的中等大小的空闲块：很少小细碎片，也很少有很大的空闲块。比较适合：作业类型单一，所需空间长度相差不大的应用环境。,算法三：最佳适应算法算法思想和过程：扫描整个空闲分区链表，在所有比申请内存大的空闲分区中，确定一个最小的分区。如果所有分区都小于所申请的大小，返回失败把找到的分区一分为二，一块长度等于所申请的内存大小，另一块包含剩下的空间。前一块分配给相应的申请者，后一块仍作为空闲分区插入到空闲分区链表的合适位置。实现细节：为提高找到满足条件的最小分区的速度，空闲分区链表一般按块长从小到大的顺序组织。这样就不用扫描整个链表。,回收过程：扫描整个链表，发现与之相邻的空闲区合并后，需要按大小找到合适的插入位置。优缺点：优点：在内存比较宽松时，系统中可能会保留一些大的空闲分区，对后继的大作业运行比较有利。明显缺点：经过长时间的运行，系统中可能会出现一些长度极短（小到连运行最小的作业都不够）的空闲分区，这些小碎片除非有机会和其它相邻分区合并，否则不可能得到利用。效率：分配时，需要扫描两次空闲链表；一次用于查找，另一次用于将剩余空闲区插入到合适位置回收时，需要两次扫描链表，回收算法复杂，且耗时。使用场合：比较适用于作业长度差别相对较大的运行环境。,算法四：最差适应算法算法思想和过程：空闲分区链表按从大到小的顺序组织。若最大分区（链表头）小于所申请的大小，返回失败把最大分区一分为二，一块长度等于所申请的内存大小，另一块包含剩下的空间。前一块分配给相应的申请者，后一块仍作为空闲分区插入到空闲分区链表的合适位置。回收过程：扫描整个链表，发现与之相邻的空闲区合并后，需要按大小找到合适的插入位置。,优缺点：优点：系统中出现极小空闲分片的可能性比较小，不容易产生小碎片。明显缺点：长时间运行后，系统中基本上都是长度中等的空闲分区。系统中难以保留一些大空闲分区，对后继的大作业运行不利。效率：分配时：一次扫描链表。合并后，两次扫描链表。使用场合：比较适用于作业长度相差不大的运行环境。,四种算法对比：效率：以扫描链表的次数大致衡量，最佳（2+2）最差（1+2）首次（1+1）循环（1+1）小碎片产生的可能性：最佳首次循环最差后继大作业分配成功的可能性：最佳首次循环最差,2.3.6多重分区,背景：固定分区方式会出现分区内的零头；可变分区方式会出现小碎片；系统可能会出现：所有空闲分区的总和远大于所申请内存的长度，但每一块都不够。因此作业申请失败。,解决方案：基于作业移动的碎片：通过对已分配内存中作业的移动，使零碎的空闲区集中起来。缺点：移动算法比较费时，尤其对静态重地位技术而言，其移动作业的工作量更大。并不是所有作业都适合移动，正与外设交互的作业不便于移动。尤其是使用DMA通道的作业。改变作业的内存需求特性，让作业不再需求连续的单一存储区。,多重分区技术在作业运行过程中可申请附加的分区，而且无需与现有的分区相临。好处：便于大作业的执行。提高内存的利用率，使小碎片也可以利用起来。便于多作业间的内存共享。副作用：增加了存储管理的复杂度,2.4内存扩充技术,内存扩充背景CASE1：在一个时刻，系统只能有一个作业在运行（假定单处理器系统）。对多道程序设计而言，如果内存紧张，是不是可以考虑回收暂停的作业占有的内存？CASE2：对特大型作业，假定其要求的内存大于所有的物理内存，是不是这个作业不可能得到运行？,解决思路对CASE1采用交换技术：考虑把暂停的作业交换到磁盘上，待其真正要运行，再恢复执行现场。对CASE2采用同时部分装入：特大型作业的所有代码不可能同时执行，可以考虑把正在执行的区域先装入。换句话说，把暂时不用的部分换出。应用程序不透明方式-覆盖技术应用程序透明方式-虚拟存储技术,覆盖技术：将一个大程序按程序的逻辑结构划分成若干个程序（或数据）段，并将不会同时执行、从而就不必同时装入内存的程序段分在一组内，该组称为覆盖段。同个覆盖段中多个程序段分配到同一个称为覆盖区的存储区域。,MAIN(10K),A(30K),B(20K),C(30K),D(30K),E(40K),(a)一个程序的调用结构,(b)覆盖和覆盖段,图2-10覆盖管理,覆盖技术的实现关键：操作系统不知道程序的逻辑结构，也不可能自动划分覆盖段。需要应用程序员在设计程序就要规划好各个覆盖段。并用约定的描述语言，描述出覆盖段的划分，以及对每个覆盖段，何时执行特定程序段的调入和覆盖。并将该描述脚本按规定的方式提交给操作系统操作系统按描述脚本的要求，在规定的时间调入合适的程序段到覆盖段。,交换技术：覆盖技术用于一个作业的内部，交换技术用于不同的作业。任一时刻，主存中只保留一个完整的用户作业。当该作业的时间片用完或因等待某一事件而不能继续运行时，系统就挑选下一个作业进入主存运行。为减少交换的数据量，如果新作业的内存需求不大，可只交换出原作业的一部分交换技术对应用程序而言是透明的，无需程序员干预。,作业1,空闲区,(a),作业2,空闲区,(b),作业3,空闲区,(c),作业2,作业1,空闲区,(d),作业3,作业2,作业3,空闲区,(e),作业2,作业2,空闲区,(f),图2-11单一连续存储区的存储交换,虚拟存储器背景作业即使不全部装入主存也能正确运行的，因为：1.在一个程序中一般都有相当数量的出错处理子程序，在正常的运行过程中很少执行到这些程序。2.程序中一般都含有类似then和else的彼此互斥的部分，互斥的部分又可以调用自己的子程序，在程序的一次执行中往往只选择其中的一条路径执行。3.程序中的初始化部分一般只执行一次，初始化工作完成后这些代码就没有存放在主存中的必要。4.从运行的时间角度来分析，在一段时间内作业一般不会执行到所有程序段的指令和存取绝大部分数据，它往往相对集中地访问某些区域中的指令和数据，这就是程序运行的“局部性原理”。,虚拟存储器的基本原理思想：通过地址映射机构：完全隔离程序地址和实际的物理地址。在主存中只装入最近经常要访问或正需要访问的指令和数据，剩余部分就暂时不必装入，等到以后要访问到它们时再调入内存。因而运行程序所需内存可远小于程序的虚拟地址。用户的程序就不受实际内存大小的限制，好像计算机系统向用户系统提供了容量极大的“主存”，而这个大容量的“主存”是靠存储管理的软件和硬件,通过大容量的辅存作为后援存储器扩充而获得的，是程序设计员感觉到的，而实际上并不存在的“主存”，故称虚拟存储器。,程序虚拟地址,物理硬盘,换入换出,物理内存,地址映射,虚拟存储器的实现要点：需要OS，甚至是CPU支持地址映射，将逻辑地址转化为物理地址操作系统需要对程序虚拟地址空间对应的物理内存进行管理：装入、交换、调出，维护地址映射表等。虚拟存储器的大小限制：指令地址字长度的限制。存放程序指令和数据的外存储器的大小，这种设备叫做外围设备。存放程序指令和数据的外存区域称为交换区。虚拟地址空间不能大于内存和磁盘的容量之和。,2.5、纯分页式存储管理,导引：地址映射的基本方式一一自由映射：灵活，无任何零头地址映射表很大单一块的映射：无法解决单一大程序运行的问题二者的结合？,1、基本思想作业的虚拟地址空间划分为等长的块，每块称为虚页。虚拟地址-虚页号+页内偏移地址主存地址空间也划分为与虚页长度相等的块，每块称为实页。主存地址-实页号+页内偏移地址每个作业的每个虚页号-每个实页号页内偏移地址采用恒等方式映射,2、地址表示和分配地址表示在具体实现时，页的大小是2的幂次方。如Linux下80386为2的12次方（4096）。二进制表示的虚拟地址可解释为高位部分为页号，地位部分为页内偏移。页存储分配页是内存分配、内存保护的基本单位，虚拟地址空间若不能分成整页，零头即使一个字节也要再分一页。最后一页可能不满，存在“内零头”，可能会造成内存浪费。合适选取页的大小比较重要。,3、地址转换的实现指明虚页号和实页号的对应映射关系的表，称为页表。页表是存储在主存中的，通过初始地址来标示的。为了实现地址越界检查，需要记录页表的长度。页表长度和页大小成反比，页太大或太小都不合适。页表控制寄存器保存了当前进程的页表初始地址和页表长度。CPU中只有一个页表控制寄存器，只有占用CPU的进程才占有页表控制寄存器。进程切换时要同时切换相应的页表控制寄存器的值。,具体过程：从虚地址中获得虚页号和页内偏移；比较虚页号和页表长度，确定是否越界，若越界表明访问了非法地址，进行出错处理；通过查页表，获得实页号，计算出对应页的起始地址；页起始地址+页内偏移量，获得真正的物理地址。,a,L,p,d,页表控制寄存器,页表始址,页表长度,a,图2-12纯分页系统的地址变换机构,虚地址,页号,页内偏移,+,b,d,虚页号页架号01pb,4、快表背景：页表存储在主存中，每次执行指令时为实现地址转换，要多访问一次（多次）内存。内存速度远慢于CPU执行速度，内存访问是程序执行速度的瓶颈，多一次内存访问会明显减慢程序执行速度。思路：把页表项的副本同时保存在快表中快表对应CPU自带的高速Cache或寄存器组，访问速度远远大于内存。由于快表造价昂贵，容量小，不能把所有的页表项全部放到快表中。80486中可保存32个表项根据程序执行局部性的特点，即它在一定时间内总是经常访问某些页，若把对应的几个页表项记录快表中，相当比例的地址转换就能直接完成。,a,L,p,d,页表控制寄存器,地址寄存器,a,图,2-13,快表与地址变换,虚地址字,+,b,d,快表,p,b,b,慢表,快表方式下的地址转换：首先按虚页号查快表，若该页已登记在快表中，则由快表中登记的实页号和页内地址形成绝对地址。若快表中查不到对应页号，则再查主存中的页表而形成绝对地址，同时将该页登记到快表中。快表的维护：淘汰算法：快表满了，快表中又需要登记新页，需要淘汰旧的登记项。进程切换：同页表控制寄存器一样，也需要重新装载快表表项。,5、空闲内存页的管理位图方式：每个Bit表示一块的使用状态。0表示空闲，1表示已分配。空闲链表方式：用链结构表示空闲页。,6、请求分页系统,1、背景对装入内存的作业，有些页面不大经常使用，降低了主存的利用率。一些大作业无法同时装入内存。2、解决思路：在内存紧张时，有些内存页面不经常使用，把这些页面的内存保存到辅存中。待需要时，再重新装入该页面。请求分页机制：由操作系统自动实现页面的换出和换入，对用户完全透明。工作集：对一个作业而言，当前真正在内存中的页面构成的集合，称为工作集。,3、请求分页的软硬件基础在执行指令时，CPU地址转换要能判断出该页是否在内存中。页表项中应该有相应的标志位。地址转换机构在发现页在辅存中，要能够获得CPU的控制权。中断机制：中断处理子例程：实现页面的换入。如果内存紧张，要先换出一些页面。,在请求分页系统中，由于作业的虚页可能驻在主存中，也可能驻在辅存中，因此在页表中要扩充表项的内容，使之包括辅存地址，以便在发生缺省时请求分页机构可以将辅存中的虚页调入主存。这样，每一个页表项结构如下所示：虚页号实页号辅存地址状态其中状态字段含有该页当前是在主存还是在辅存的标志，此外，在该字段中还可包括访问位和修改位等。,4、页面淘汰的背景和目标背景：需要换入新页面时，内存紧张导致无法装入页面。需要淘汰哪些页呢？目标：尽量换出那些以后不再使用的页面。在尽可能长的时间内不使用的页面。避免“抖动”：刚换出，又要使用需要再换入。衡量指标：缺页中断次数/总的内存访问次数（缺页中断率）,5、最优淘汰算法原理：程序执行时访问页的页号序列构成了页面流；淘汰从当前时刻起在页面流中不再出现的页；如没有，则淘汰一个在页面流中最晚出现的页。缺点:可行差：在程序未往下执行时，OS不可能知道未来的页面流。用途：作为理论上的评价标准，用以鉴别其他淘汰算法的优劣,6、先进先出（FIFO）淘汰算法原理：总淘汰最先调入内存的页面。特点：实现简单。对于顺序执行为主的程序比较合适。对包含循环的程序可能产生“抖动”。如在执行N个页面大小循环语句段时，分配N-1个页架，则每访问下一个页时都将发生缺页中断。,7、最近最少使用淘汰算法原理：淘汰最近一段时间内使用频率最低的页面。实现基本思想：为每页面设置访问计数器，通过比较所有页的计数器值来确定淘汰的页面。为体现“最近”，定期对所有计数器清零，或减少。,实现方法一：矩阵法对n个页面设置n*n的矩阵。初始化时值全为0当K页被访问：硬件置k行的所有位为1；再置k列的所有位为0。二进制值为最小的一行所对应的页是最近最久不用的页。,实现方法二：年龄法用年龄表示最近使用的频率具体方法：每个页面对应一个年龄值，开始时，所有页年龄为相同值（如3）。当一页面被访问时，其年龄增加一个值（如3）。但年龄的最大值是一定的，如20。在淘汰页面时，选取年龄为0的淘汰。把其余页的年龄全部减1。Linux就采用这种淘汰算法。思考题：为何要设置年龄的最大值？,8、最久不使用淘汰算法（NRU）原理：淘汰最近一段时间内未曾访问过的某一页面即：查找哪个页面的最后一次访问离现在最久实现算法：队列法设置一个从中间可以出队的非严格意义上的队列，队列中的每一个单元对应于一个内存页。每次访问一个页面时将对应单元从队列中抽出，重新排到队尾去，淘汰的页从队列头取。因而：经常要访问的页总是排在靠近队列的尾部，而排在队首位置上的页就是最长时间没有被访问过的页。缺点：每一次页面访问，都要执行队列操作，用软件实现比较费时。,近似实现方法：每页面设置两个硬件位：访问位和修改位，当有访问和修改时自动设置这两位为1将内存页组成循环队列，并设置循环检测指针。检测过程：从指针指向的页开始，依次若两位均为0，选择该页淘汰若访问位1，修改位0，置访问位为0若访问位0，修改位1，置修改位为0若访问位1，修改位1，置访问位为0,9、影响淘汰页面选择的其它因素上述算法没有考虑页面换入换出的开销、内存使用情况。影响页面换入换出开销的因素包括：该页是否被修改过。该页辅存中是否已有副本。内存使用情况包括：用途：缓冲区？用户使用or核心使用？与外设通信中？实际的系统实现考虑了这些因素。,10、淘汰页面的范围选择策略：全局淘汰策略：从所有作业所占用的页面中选择。局图淘汰策略：从本作业所占用的页面中选择从效果上看：全局算法较好，可以在进程间动态分配页面。Linux系统采用全局淘汰策略。,7、多级页表,1、背景程序地址空间一般是由总线位数确定。32位总线的地址空间为232。程序地址空间巨大。对应的页表也占了很大的地址空间。假定：页大小为4096(212)字节，每个页表表项占4字节。一个进程的完整页表需要占：4*220个字节。需要占用4M的连续内存空间，比较可观。,2、多级页表的具体做法把整个页表进行分页,分成一张张小页表,每个小页表的大小与页框相同。对小页表顺序编号,允许小页表分散存放在不连续的页框中。为了进行索引查找,应该为这些小页表建一张页目录表（一级页表）,其表项指出小页表（二级页表）所在页框号及相关信息。逻辑地址结构有三部分组成：页目录号、页号和位移。,3、基于多级页表的地址转换：,Boffset,dirpageoffset,B,F,一级页表,二级页表,物理地址,逻辑地址,页目录表控制寄存器,4、多级页表的好处和缺陷：内存仅存放当前使用的小页表,其余暂时不用部分放在磁盘上,待用到时再行调入。小页表占用内存空间不必连续，可分散存放。地址转换时，CPU需要多访问一次内存：一次页目录表+一次小页表+目标内存访问。需要用快表来解决多一次内存访问的问题。,5、多级页表实例（Linux+X86）地址总线32位，程序地址空间232；页目录（10位）+页号（10位）+页内偏移（12位）页目录表中的每项4字节，正好占一页（4*210），永久在内存中。页目录表的表项中，含对应的二级页表是否在内存中的标志位。每个页表项占4字节，每个二级页表占一页。可以换入和换出。,页表项的格式：页面地址：12位D位：修改位，当该页程序修改后，应纪录,为淘汰做准备。A位：（读/写）引用位，凡对程序读写均置为已访问（accessed），淘汰时先找A=0的页面。P位：存在位，页面在内存时，P=1。U/S位：用户/管理员（User/Supervisor）位，若U/S=0，该页为一个管理员页面（OS页面），用户不能访问。R/W位：读/写（Read/Write）位，R/W=1时允许页修改；R