操作系统原理_方敏_存储管理

《操作系统、实验》第五章存储管理操作系统课程组第2页内容回顾死锁的检测永久性资源的死锁检测资源分配图死锁定理临时资源的死锁检测死锁的解除重新启动撤销进程剥夺资源进程回退第3页一、概述计算机的存储体系结构计算机为什么要使用存储器？——冯•诺依曼原理为什么要进行存储管理？存储器一直以来都是较为珍贵的系统资源，需要合理使用。程序的逻辑空间和实际的物理空间不甚相同，需要进行映射。第4页一、概述存储结构层次访问速度频度成本容量第5页一、概述存储管理的目的使得用户和用户程序不涉及内存物理的细节。自动完成用户程序的装入。提高内存的利用率。解决内存速度与CPU速度不匹配的问题。实现内存共享。方便使用者，有效利用存储资源，提高系统工作效率。第6页一、概述存储管理的任务在现代操作系统中，存储管理的主要任务有以下几个方面：地址变换(地址再定位)存储资源的分配和回收存储共享和保护存储器扩充①覆盖技术②交换技术第7页二、地址重定位基本概念程序符号地址/名地址编译0101010010110101010101101010目标文件逻辑地址/相对地址虚拟地址/程序地址加载内存物理地址/绝对地址定义：当程序被装入内存时，程序的逻辑地址被转换成内存的物理地址，这一过程称为地址重定位(由内存管理单元(MMU)完成)。第8页二、地址重定位常见的地址重定位技术绝对装入(Absoluteloading)/固定地址再定位程序的地址再定位是在程序执行之前被确定的，也就是在编译连接时直接生成实际存储器地址(物理地址)。在此，程序地址空间和内存地址空间是一一对应的。优点：装入过程简单。缺点：与硬件的结构过于密切，缺乏灵活性。0101010010110101010101101010目标文件加载内存逻辑地址物理地址一一对应例如：单片机，MS-DOS中.com格式程序。第9页二、地址重定位可重定位装入(RelocatableLoading)即指程序装入内存时，由于程序的逻辑地址和物理地址不一致，由逻辑地址到物理地址的映射过程。分类①静态再定位：指地址定位时修改程序的逻辑地址值，完成定位后，在程序的执行期间地址将不再发生变化。特点：在程序执行之前进行地址再定位。优点：无需硬件支持，容易实现。早期的操作系统中大多数都采用这种方法。缺点：必须分配连续的存储区域；执行期间不能扩充存储空间，也不能在内存中移动，内存利用率低，不便于共享。……LOADA2003456逻辑地址空间…………0100200300……LOADA12003456物理地址空间…………1000110012001300……第10页二、地址重定位动态再定位：程序在装入内存时，不修改程序的逻辑地址值，程序在访问物理内存之前，再实时地将逻辑地址转换成物理地址。……LOADA2003456逻辑地址空间…………0100200300200VR1000BR……LOADA2003456物理地址空间…………0110012001300……BR:基址寄存器，存放程序的起始地址VR:变址寄存器，存放需要变换的逻辑地址第11页二、地址重定位优点：①程序在执行期间可以换入和换出内存，可以解决内存紧张状态；②可以在内存中移动——把内存中的碎片集中起来，可以充分利用空间；③不必给程序分配连续的内存空间，可以较好的利用较小的内存块；④若干用户可以共享同一程序，实现共享。缺点：需要附加的硬件支持，实现存储管理的软件算法比较复杂。第12页三、分区存储管理方案存储管理方案分类从操作系统的发展历史来看，存储管理主要有以下几种方案：分区存储管理方案。要求连续分配存储空间，且程序要一次性全部装入内存。简单，但是有比较严重的内碎块和外碎块。段式存储管理方案。不要求连续分配存储空间，段和段之间可以不连续，但程序需要一次性全部装入内存。有比较严重的外碎块。页式存储管理方案。是一种不连续存储管理方案，也需要一次性全部装入内存。在逻辑地址空间和物理地址空间都采用分页的思想。缺点是每一个作业的最后一页有内碎块。第13页三、分区存储管理方案段页式存储管理方案。是一种不连续存储方案，段式存储管理和页式存储管理的结合。克服了纯分页和纯分段存储管理思想的缺点。交换技术和覆盖技术。虚拟存储管理方案。第14页三、分区存储管理方案分区存储管理：是一种连续分配存储空间的管理方式。曾被广泛地应用于1960～1970年代的操作系统中。思想：把内存分为一些大小相等或不等的分区(Partition)，装入时每个应用程序占用一个或几个分区，操作系统占用其中一个分区。适用于多道程序系统和分时系统，支持多个程序并发执行。分类单一连续分区存储管理固定分区管理可变分区管理第15页操作系统用户区操作系统分配给用户作业的空间00xFFF...三、分区存储管理方案单一连续分区存储管理特点：一次只能装入一个程序，程序独占整个用户区，如果程序小于用户区，则剩余的空间浪费，如果大于，则无法装入。优点：简单，适用于单用户、单任务的操作系统，不需要复杂的硬件支持。缺点：一个作业运行时要占用整个内存地址空间，对内存造成了很大的浪费，不支持大作业。第16页三、分区存储管理方案固定分区管理支持多道程序技术实现方法：操作系统0100K120K160K260K初始化内存空间分区状态表程序A(30K)程序A已分配内碎片：指占用分区之内未被利用的空间。第17页三、分区存储管理方案特点：内存中同时可以容纳多道程序；程序必须连续存放，且要一次全部装入。优点：比单一连续分配方法，内存的利用率提高了；可以支持多道程序；实现简单，开销小。缺点：作业必须预先能够估计自己要占用多大的内存空间，有时候这是难以做到的；存在内碎片，造成存储空间的浪费；分区总数固定，限制了并发执行的程序数目。第18页三、分区存储管理方案可变分区(DynamicPartitioning)思想：预先不划分内存，当作业需要时向系统申请，系统从其中挖出一块给该作业，其大小等于作业所需内存的大小，然后将剩下的部分再作为空表块，给下一次分配使用。OSJob1Job2Job4Job3Q:如何管理这些空闲区？m_sizem_addrm_sizem_addrm_sizem_addrm_sizem_addr0…线性表格法m_sizem_addrm_sizem_addr链接法Job5第19页三、分区存储管理方案分区分配算法最先适应算法(first-fit)分配方法：将所有的空闲分区按照地址递增的顺序排列，按照分区的先后次序，从头开始查找，符合要求的第一个分区就是要找的分区。OSJob2Job4Job5m_sizem_addrm_sizem_addrm_sizem_addr0…第20页三、分区存储管理方案释放方法OSJob2Job4Job5前空闲区释放区后空闲区前空闲区释放区后空闲区前空闲区释放区后空闲区前空闲区释放区后空闲区（a）（b）（c）（d）规则：相邻合并，否则插入第21页三、分区存储管理方案优点：①分配策略简单。②尽可能利用存储区低地址的空闲区，而在高地址部分保存较大的空闲区，容易满足大作业。③在释放内存分区时，如果有相邻的空白区就进行合并，使其成为一个较大的空白区。缺点：①查找总是从表首开始，因此前面的空闲区往往被分割得很小时，查找次数增大。②会产生外碎片(指占用的分区之间难以利用的空闲分区)，这些碎片散布在存储器的各处，不能集中使用，因而降低了存储器的利用率。第22页三、分区存储管理方案下次适应算法(next-fit，循环最先适应算法)分配方法：按分区的先后次序，从上次分配的分区起查找，到最后分区时再回到开头，符合要求的第一个分区就是找到的分区。释放方法：同于最先适应算法。优点：使空闲分区分布得更均匀，提高了分配查找的速度。缺点：较大的空闲分区不易保留。第23页三、分区存储管理方案最佳适应算法(best-fit)分配方法：将所有的空闲分区按照其容量递增的顺序排列，当要求分配一个空白分区时，由小到大进行查找，找到最合适的分配。释放方法：在整个链表上搜索地址相邻的空闲区，合并后，再插入到合适的位置。优点：①分配后所剩余的空白块会最小，较大的空闲分区会被保留。②平均，只要查找一半的表格便能找到最佳适应的空白区；③如果有一个空白区的容量正好满足要求，则它必被选中。缺点：空白区一般不可能恰好满足要求，在分配之后的剩余部分通常非常小，以致小到无法使用，会形成较多外碎片。第24页三、分区存储管理方案最坏适应算法(worst-fit)分配方法：与最佳适应算法相反，将所有的空白分区按容量递减的的顺序排列，最前面的最大的空闲分区就是找到的分区。释放方法：同于最佳适应算法(best-fit)优点：分配的时候，只需查找一次，就可以成功，分配的算法很快。缺点：最后剩余的分区会越来越小，不会保留较大的空闲分区，无法运行大程序。第25页三、分区存储管理方案可再定位式分区又称浮动分区分配，是解决碎片问题的简单而有效的办法。基本思想：移动所有被分配的分区，使之成为一个连续区域，而留下一个较大的空白区。OS作作1(8K)作作4(24K)作作5(128K)作作6(256K)OS作作1(8K)作作4(24K)作作5(128K)作作6(256K)OS作作1(8K)作作4(24K)作作7(256K)作作5(128K)作作6(256K)作作7(256KB)“靠拢”或“紧凑”Q:程序地址的再定位？第26页提出原因四、页式存储管理分区存储管理方案要求作业存储时必须连续存放OSJob1Job3Job2Job4Job5页式存储管理方案解决作业不连续存放的问题第27页逻辑地址空间01K2K3K4K四、页式存储管理基本原理物理地址空间0100K101K102K103K104K105K106K107K108K109KOS012345678实页/主页0123虚页：大小相同，常为2的整数幂。2031Q:如何记录和管理这种映射关系？第28页四、页式存储管理页面变换表(Pagemanagementtable)是一种特殊的数据结构用途：记录每一个作业的虚页号到物理内存中页号之间的映射关系。每一个作业都拥有一个自己的页面变换表。结构：0虚页号3实页号162135…………Job1Job2总页表…………起始地址长度…作业ID…SL页表控制寄存器起始地址长度第29页四、页式存储管理物理地址空间OS012345678逻辑地址空间0123203101K2K3K4K0100K101K102K103K104K105K106K107K108K109K虚页号实页号03162135LOADA逻辑地址…………3页号页内偏移量1001345…………3K3100第30页四、页式存储管理地址变换过程S页表长度页表起始地址＋03162135虚页号实页号页表控制寄存器LS5100地址寄存器3页内偏移量页号逻辑地址100Q:为了取出一个数据，系统需要访问内存几次？第31页四、页式存储管理快表由一组联想寄存器(TLB,TranslationLookasideBuffer)组成。联想寄存器：一种按内容进行并行查找的快速寄存器，访问速度比主存快得多。原理：第32页四、页式存储管理……P页表基址寄存器D＋…………………………虚拟地址字快表SL……………………B…………………………………………………………PB……………………BD地址寄存器页表经常要访问的页表表项。第33页四、页式存储管理空闲内存页的管理位示图0/10/1………80/1…0/10/1001…bitbyteQ:内存大小：256M，每页4K，位示图有多大？第34页四、页式存储管理优点没有外碎片，每个内碎片不超过页大小。程序不必连续存放。主要缺点：程序要一次全部装入内存才能执行。采用动态地址变换机构会增加计算机的成本和降低处理机的速度。各种数据结构(页表，空闲页表)要占用一定的内存空间，而且系统要花费一定的时间来建立和管理这些表格。依然存在内碎片。第35