chapter4存储器管理jqj.ppt

《chapter4存储器管理jqj.ppt》由会员分享，可在线阅读，更多相关《chapter4存储器管理jqj.ppt（166页珍藏版）》请在三一文库上搜索。

1、1,第四章 存储器管理,存储器是计算机系统的重要组成部分。目前，存储器 仍然是一种宝贵资源。如何对它有效管理不仅影响到 存储器的利用率而且还对系统性能有重大影响。存储 器管理的主要对象是内存。 理想存储器：速度快；容量大；价格低。但目前无 法同时满足这三个条件。,2,4.1.1 多级存储结构,存储器的功能是保存数据，存储器的发展方向是高速、大容量和小体积。 存储组织是指在存储技术和CPU寻址技术许可的范围内组织合理的存储结构。 其依据是访问速度匹配关系、容量要求和价格 寄存器-内存-外存 结构 寄存器-缓存-内存-外存 结构 微机中的存储层次组织： 访问速度越慢，容量越大，价格越便宜 最佳状态

2、应是各层次的存储器都处于均衡的繁忙状态（如：缓存命中率正好使主存读写保持繁忙）,4.1 存储器的层次结构,3,存储器的层次结构 存储器在信息处理中占据重要位置。但是在现有技术下，任何一种存储装置，都无法同时从速度与容量两方面，满足用户的需求。实际上它们组成了一个速度由快到慢，容量由小到大的存储装置层次。 书P116 图4-1 存储层次示意,4,4.1.2.主存储器与寄存器,主存储器： 主存储器 (简称内存或主存) ，用于保存进程运行时的程序和数据，也称可执行存储器。 其容量从数十MB到数GB。CPU的控制部件只能从主存中取得指令和数据：数据从主存读取并将它们装入到寄存器中,或从寄存器存入到主存

3、。由于主存的访问速度远低于CPU执行指令速度,为缓和这一矛盾引入寄存器和高速缓存。 寄存器： CPU内部，访问速度最快，完全能与CPU协调工作，但价格十分昂贵，因此容量不可能做得很大。一般以字(word)为单位。寄存器的数目，对于当前的微机系统和大中型机，可能有几十个甚至上百个。,5,4.1.3 高速缓存和磁盘缓存,高速缓存Cache( 10-100ns) 容量大于或远大于寄存器，而比主存约小两到三个数量级，从几十KB到几MB； 其访问速度快于主存,为缓和内存和CPU速度上的矛盾而产生。 进程的程序和数据通常是存放在主存中，当使用时被临时复制到一个速度较快的高速缓存中。当CPU访问一组特定信息

4、时，首先检查它是否在高速缓存中,如果已存在，可直接从中读出以避免访问主存，否则再从主存中读出信息。 如大多数计算机有指令高速缓存，用来暂存下一 条要执行指令，若没有指令高速缓存， CPU将空等若干个周期，直到下一条指令从主存中取出。,6,磁盘缓存： 并不是一种实际存在的存储介质，是主存的一部分。即 利用主存中的存储空间，来暂存从磁盘中读出或写入的 信息。 由于目前磁盘的I/O速度远低于对主存的访问速度，因此 将频繁使用的一部分磁盘数据和信息， 暂时存放在磁盘 缓存中，可减少访问磁盘的次数。 由操作系统协调这些存储器的使用 一个文件的数据可能出现在存储器层次的不同级别中： 先存放在辅存中（如硬盘

5、）；当需要运行或被访问时， 就必须调入主存，也可以暂存在磁盘缓存中。,7,4.2 程序的装入和链接,8,图 4-2 对用户程序的处理步骤,程序在成为进程之前的准备工作 编辑：形成源文件（符号地址） 编译：形成目标模块（模块内符号地址解析） 链接：由多个目标模块或函数库生成可执行文件。 （模块间的符号地址解析） 装入：构造PCB，形成进程（使用物理地址）,完成 装入模块中的逻辑地址到物理地址的映射。,9,4.2.1 程序的装入,1. 绝对装入方式,装入程序按照装入模块中的地址，将程序和数据装入内存。 装入后由于程序中的逻辑地址与实际内存地址完全相同，故不 须对程序和数据的地址进行修改。,10,程

6、序中使用的绝对地址，可在编译或汇编时给出, 也可由程序员直接赋予。但要求程序员熟悉内存使用情况，而且一旦程序或数据被修改后，可能要改变程序中的所有地址。,优点：装入过程简单 缺点：只能将目标模块装入到内存中事先指定的位置。在多 道程序环境下，编译程序不可能预知所编译的目标模 块应放在内存的何处，因此只适用于单道程序环境。 过多依赖于硬件结构，不适于多道程序。,11,2. 可重定位装入方式(静态）,在多道程序环境下，所得到的目标模块的起始地址通常 是从0开始的， 程序中的其它地址也都是相对于起始地址计 算的。此时应采用可重定位装入方式，根据内存的当前情况， 将装入模块装入到内存的适当位置。 把在

7、装入时对目标模块中的指令和数据的地址的修改过 程称为重定位。又因为地址变换是在装入时一次完成的，以 后不再改变，故称为静态重定位。,12,图 4-3 作业装入内存时的情况,目标模块中的数字地址是逻辑地址，在装入时将其转换为物理地址。并且地址变换是一次完成的，之后不再改变。 优点：可将装入模块装入到内存中任何允许的位置，故可用于多道程序环境。可以装入有限的多道程序，不需要硬件的支持。 缺点：常占用连续的内存空间，程序装入后不能移动，不易实现共享。,13,3. 动态运行时装入方式-动态可重定位,动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地

8、址转换推迟到程序真正要执行时才进行。因此， 装入内存后的所有地址都仍是相对地址。 优点：可以移动，有利于实现共享，是虚拟存储实现的基础。,14,4.2.2 程序的链接,1.静态链接方式,源程序经过编译后，可得到一组目标模块，再利用链接 程序将这组目标模块链接，形成装入模块。 根据链接时间 不同，可分为三种：,在程序运行之前，先将各目标模块及所需的库函数， 链接成一个完整的装入模块，以后不再拆开。这种事先 进行链接的方式称为静态链接。,15,（1）对相对地址进行修改。 （2）将每个模块中所有的外部调用符号也都变换为相对地址。,16,2. 装入时动态链接,装入时动态链接方式有以下优点： 便于修改和

9、更新某个目标模块。 便于实现对目标模块的共享。,源程序经编译后所得的目标模块，是在装入内存时边装入 边链接的，即在装入一个目标模块时， 若发生一个外部模块 调用事件，将引起装入程序去找出相应的外部目标模块， 并 将它装入内存， 还要按照上图的方式修改目标模块中的相对 地址。,17,3. 运行时动态链接,将对某些模块的链接推迟到执行时才链接，即在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存，并把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。,18,4.3

10、 连续分配,连续分配方式，是指为一个用户程序分配一个连续的内存空间。 可分为： 单一连续分配 固定分区分配 动态分区分配 动态重定位分区分配,19,4.3.1 单一连续分配方式,在单道环境下，不管是单用户系统还是单道批处理系统，进程（作业）执行时除了系统占用一部分主存外，剩下的主存区域全部归它占用。主存可以划分为三部分： 系统区、用户区、空闲区。用户区是一个连续的存储区，所以又称单一连续区存储管理。 单用户系统在一段时间内，只有一个进程在内存，故内存分配管理十分简单，内存利用率低。内存分为两个区域，一个供操作系统使用，一个供用户使用。,20,单一连续区存储分配示意图,21,工作流程,单一连续区

11、分配采用静态分配和静态重定位方式，亦即作业或进程一旦进入主存，就一直等到它运行结束后才能释放主存。如下图所示的主存分配与回收法。并且由装入程序检查其绝对地址是否超越，即可达到保护系统的目的。,22,工作流程(续),23,单用户系统缺点,不支持多道。 主存利用率不高 程序全部装入，很少使用的程序部分也占用主存。 程序的运行受主存容量限制。,24,4.3.2 固定分区分配,是最简单的一种可运行多道程序的存储管理方式。 把内存分为一些大小相等或不等的分区，在每个分区中只装入一道作业，这样，把用户空间划分成为几个分区，便允许有几道作业并发运行。操作系统只占用其中一个分区。 适用于多道程序系统和分时系统

12、，支持多个程序并发执行，但难以进行内存分区的共享。,25,预先把可分配的主存空间分割成若干个连续区域，称为一个分区。每个分区的大小可以相同也可以不同，如图所示。但分区大小固定不变，每个分区装一个且只能装一个作业。 存储分配：如果有一个空闲区, 则分配给某个作业。,1.划分分区的方法,26,分区4 分区3 分区2 分区1 操作系统,多个等待队列,单个等待队列,分区4 分区3 分区2 分区1 操作系统,固定分区示意图,27,2.内存分配管理,固定分区使用表,设置内存分配表,20,28,3 固定分区分配优缺点,优点：易于实现，开销小。 缺点：内部碎片造成浪费，分区总数固定，限制 了并发执行的程序数目

13、。,29,4.3.3 动态分区分配（可变分区分配）,根据进程的实际需要，动态地为之分配内存空间。 在实现可变分区分配时，将涉及三个问题：分区分配中所用的数据结构、分区分配算法、分区的分配与回收 基本思想：内存不是预先划分好的，而是当作业装入时，根据作业需求和内存空间使用情况来决定是否分配内存：设置内存空闲块表记录了空闲区起始地址和长度 分区分配：动态分配 分区回收：当某一块归还后，前后空间合并，修改内存空闲块表,30,31,32,33,1. 分区分配中的数据结构,空闲分区表 (2) 空闲分区链 书P123,图 4-6 空闲链结构,34,0K,15K,38K,48K,68K,80K,110K,1

14、20K,空闲区表,已分配分区表,分区分配表：,分区分配表,35,0K,15K,38K,48K,68K,80K,110K,120K,空闲区表,已分配区表,85K,98K,36,2. 分区分配操作,1) 分配内存（系统利用某种分配算法从空闲分区链或表 中找到所需大小的分区的过程）,图 4-7 内存分配流程,空闲分区大小为m.size 请求分区大小为u.size,size是事先规定的不再切割的剩余分区的大小,37,2) 回收内存 （当进程运行完毕释放内存时，系统根据回收区的首址，从空闲分区链或表中找到相应的插入点， 将回收区插入到空闲分区链或表中适当位置。,回收区与插入点的前一个空闲分区F1相邻接

15、回收区与插入点的后一空闲分区F2相邻接 回收区与插入点的前、后两个分区相邻接 回收区既不与F1邻接，又不与F2邻接。 以上四种情况处理见书P125,38,3.可变分区分配算法,为把一个新作业装入内存，须按照一定的分配算法， 从空闲分区链或表中选出一分区分配给该作业。 动态内存分配有以下四种算法： 首次适应法 下次适应法（循环首次适应法） 最佳适应法 最坏适应法,39,分配：当进程申请大小为SIZE的内存时，系统从空闲区表的第一个表目开始查询，直到首次找到等于或大于SIZE的空闲区。从该区中划出大小为SIZE的分区分配给进程，余下的部分仍作为一个空闲区留在空闲分区链中，但要修改其首址和大小。,回

16、收：按释放区的首址，查询空闲分区链，若有与释放区相邻的空闲区，则合并到相邻的空闲区中，并修改该区的大小和首址，否则，把释放区作为一个新的空闲区，将其大小和首址按照首地址大小递增的顺序插入到空闲分区链中的适当位置。,要求空闲分区按首址递增的次序组织空闲分区链或表。,首次适应法,40,分析,注意：每次分配和回收后空闲分区链表都要按首址递增的次序排列。 首次适应法的优点： 释放某一存储区时，若与空闲区相邻则合并到相邻空闲分区中去，这种情况并不改变该区在表中的位置，只要修改其大小或首址。 这种算法是尽可能地利用低地址空间，从而保证高地址空间有较大的空闲区。 首次适应法的缺点： 低址部分不断被划分，会留

17、下许多难以利用的，很小的空闲分区称为碎片。 每次查找都是从低址部分开始，增加了查找时的开销。,41,下次适应法（循环首次适应法）,类似首次适应法。每次分区时，总是从上次查找结束的地方开始，找到一个足够大的空白区分配。 为实现该算法应设置一个起始查寻指针，用于下一次起始查寻的空闲分区，并采用循环查找方式，即如果链尾空闲分区的大小仍不能满足要是，则应返回到第一个空闲分区进行查寻。找到后，应调整起始查寻指针。 优点：使空闲分区分布更均匀从而减少了查找空闲分区的开销。 缺点：缺乏大的空闲分区。,42,最佳适应算法,每次为作业分配内存时，总是把能满足要求又是最小的空闲分区分配给作业。 要求将所有的空闲分

18、区按其容量从小到大的顺序形成一空闲分区链。 分配：当进程申请一个存储区时，系统从表头开始查找，当找到第一个满足要求的空闲区时，停止查找，并且这个空闲区是最佳的空闲区。 所谓最佳即选中的空闲区是满足要求的最小空闲区。 回收：按释放区的首址，查询空闲分区链，若有与释放区相邻的空闲区，则合并到相邻的空闲区中，并修改该区的大小和首址，否则，把释放区作为一个新的空闲区插入到空闲分区链中。 分配和回收后要对空闲分区链重新调整。,43,分析,优点： 系统中若存在一个与申请分区大小相等的空闲区，必定会被选中，而首次适应法则不一定。 若系统中不存在与申请分区大小相等的空闲区，则选中的空闲区是满足要求的最小空闲区

19、，而不致于毁掉较大的空闲区。 缺点： 空闲区的大小一般与申请分区大小不相等，因此将其一分为二，留下来的空闲区一般情况下是很小的，以致无法使用。随着时间的推移，系统中的碎片会越来越多，从而造成存储区的大量浪费。,44,最坏适应法,要扫描整个空闲分区链，总是挑选一个最大的空闲区分割给进程使用。 要求空闲区按大小递减的顺序组织空闲区链。 分配：进程申请一个大小为SIZE的存储区时，总是检查空闲区表的第一个空闲区的大小是否大于或等于SIZE。若空闲区小于SIZE，则分配失败；否则从空闲区中分配SIZE的存储区给用户，然后修改和调整空闲区表。 回收：按释放区的首址，查询空闲分区链 ，若有与释放区相邻的空

20、闲区，则合并到相邻的空闲区中，并修改该区的大小和首址，否则，把释放区作为一个新的空闲区插入到空闲分区链中。,45,分析,最坏适应法看起来似乎有些荒唐，但在更加严密地考察 后，还是有它的优点： 当程序装入内存中最大的空闲区后，剩下的空闲区还可能相当大，还能装下较大的程序。 产生碎片的几率最小，对中、小作业有利。 查找效率很高。 缺点： 使存储器中缺乏大的空闲分区。,46,四种策略比较,上述四种算法均属于顺序搜索法。 上述四种放置策略各有利弊，到底哪种最好不能一概而论，而应针对具体作业序列来分析。 对于某一作业序列来说，某种算法能将该作业序列中所有作业安置完毕，那么我们说该算法对这一作业序列是合适

21、的。 对于某一算法而言，如它不能满足其中某一作业要求,则这一算法对该作业序列是不合适的。,47,例1：有作业序列：作业A要求18K；作业B要求25K，作业C要 求30K。系统中空闲区按三种算法组成的空闲分区链：,经分析可知：最佳适应法对这个作业序列是合适的，而 其它两种对该作业序列是不合适的。,48,快速适应算法：分类搜索法,将空闲分区根据容量大小进行分类，每类容量相同的所有空闲分区单独设立一个空闲分区链表，系统为多个这样的空闲链表设立一张管理索引表。 空闲分区的分类是根据进程常用的空间大小进行划分。 优点： 查找效率高，仅需要根据进程的长度，寻找到能容纳它的最小空闲分区链表，并取下第一块进行

22、分配即可。 不会对任何分区产生分割，所以能保留大的分区满足对大空间的需求，也不会产生任何碎片。 缺点： 分区归还主存时算法复杂，系统开销较大。 在分配分区时以进程为单位，一个分区只属于一个进程，空闲分区划分越细，浪费则越严重。是典型以空间换时间的做法。,49,4.3.4 伙伴系统,伙伴系统方式是弥补固定分区和动态分区不足的折中方式。 伙伴系统规定：无论已分配分区还是空闲分区，其大小均为2的k次幂; k为整数， 1 km，其中：21表示分配的最小分区的大小;2m表示分配的最大分区的大小;通常2m 是整个可分配内存的大小。 将空闲分区根据分区的大小进行分类，对每一类具有相同大小的所有空闲分区，单独

23、设立一个空闲分区双向链表。,50,分配过程-多次分割,设进程申请大小为n的空间 首先计算i，使2i-1n=2i 在空闲分区大小为2i的空闲分区链表中查找，找到则分配。否则，找2i+1的空闲分区链表，将分区一分为二：一个用于分配（2i）；一个挂到2i的链表上。若2i+1不存在，则找2i+2的分区， 将分区一分为二：一个用于分配（2i+1）；一个挂到2i+1的链表上，再将要分配的那个2i+1的分区一分为二，一个用于分配；一个挂到2i的分区链表上。,51,回收-合并分区,如果回收大小为2i的空闲分区时，已经存在2i的空闲分区，则将其与伙伴分区合并为2i+1的分区， 若2i+1也存在，再将其与伙伴分区

24、合并为2i+2的空闲分区，依次类推。,52,4.3.5 哈希算法,利用哈希快速查找的优点，尽快地找到合适空闲分区链表的位置。 根据空闲分区在可利用空间表中的分布规律，建立哈希函数，构造一张以空闲分区大小为关键字的哈希表,每一个表项记录一个对应的空闲分区表表头指针。 分配过程即通过哈希函数计算得到哈希表中的位置，实现最佳分配策略。,53,碎片问题,经过一段时间的分配回收后，内存中存在很多很小的空闲块。它们每一个都很小，不足以满足分配要求；但其总和满足分配要求。这些空闲块被称为外部碎片。 造成存储资源的浪费。 碎片问题的解决 紧凑技术：通过在内存移动程序，将所有小的空闲区域合并为大的空闲区域(紧缩

25、技术，紧致技术，浮动技术，搬家技术)。,54,4.3.6 可重定位分区分配,1. 动态重定位的引入,经过紧凑后的某些用户程序在内存中的位置发生了变化，此时若不对程序和数据的地址加以修改，则程序将无法执行。因此每次紧凑后，都必须对移动了的程序或数据进行重定位。,55,2. 动态重定位的实现,地址变换过程是在程序执行期间，随着对每条指令或数据的访问自动进行的， 故称为动态重定位。 当系统对内存进行了紧凑而使程序从内存的某处移至另一处时，不需对程序 做任何修改，只须用该程序在内存的新起始地址，去置换原来的起始地址。,为使地址转换不影响指令执行速度，必须有地址变换的硬件即增设一个重定位寄存器，存放程序

26、(数据)在内存中的起始地址。 程序执行时真正访问的内存地址=相对地址+寄存器中地址,56,3. 动态重定位分区分配算法,图 4-11 动态分区分配算法流程图,57,4.可重定位分区的优缺点,优点：解决了可变分区分配所引入的“外零头”问题，消除内存碎片，提高内存利用率。 缺点：提高硬件成本，紧凑时花费CPU时间。,58,4.3.7 对换(Swapping),对换：把内存中暂时不能运行的进程或暂时不用的程序和数据调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据调入内存。 对换是提高内存利用率的有效措施。 优点：增加并发运行的程序数目，并且给用户提供适当的响应时

27、间；编写程序时不影响程序结构。 缺点：对换入和换出的控制增加处理机开销。,59,60,对换空间的管理 把外存分为文件区和对换区。前者用于存放文件，后者用于存放从内存换出的进程。 为了能对对换区中的空闲盘块进行管理，在系统中应配置相应的数据结构，以记录外存的使用情况。其形式与内存在动态分区分配方式中所用数据结构相似，即同样可以用空闲分区表或空闲分区链。在空闲分区表中的每个表目中应包含两项， 即对换区的首址及其大小，它们的单位是盘块号和盘块数。 由于对换区的分配时采用连续分配方式，因而对换空间的分配与回收，与动态分区方式时的内存分配与回收方法相同。,61,进程的换出与换入,系统首先选择处于阻塞状态

28、且优先级最低的进程作为换出进程，然后启动盘块，将该进程的程序和数据传送到磁盘的对换区上。若传送过程未出现错误，便可回收该进程所占用的内存空间，并对该进程的进程控制块做相应的修改。 系统应定时地查看所有进程的状态，从中找出“就绪”状态但已换出的进程，将其中换出时间(换出到磁盘上)最久的进程作为换入进程，将之换入。 直至已无可换入的进程或无可换出的进程为止。,62,覆盖（补充）,覆盖：“覆盖”管理，就是把一个大的程序划分成一系列的覆盖，每个覆盖是一个相对独立的 程序单位。把程序执行时并不要求同时装入主 存的覆盖组成一组，称其为覆盖段，这个覆盖 段被分配到同一个存储区域。这个存储区域称 之为覆盖区，

29、它与覆盖段一一对应。 缺点：编程时必须划分程序模块和确定程序模 块之间的覆盖关系，增加编程复杂度。从外存 装入覆盖文件，以时间延长来换取空间节省。,63,覆盖(补充),引入：其目标是在较小的可用内存中运行较大的程序。常用于多道程序系统，与分区存储管理配合使用。 原理：一个程序的几个代码段或数据段，按照时间先后来占用公共的内存空间。 将程序的必要部分（常用功能）的代码和数据常驻内存； 可选部分（不常用功能）在其他程序模块中实现，平时存放在外存中（覆盖文件），在需要用到时才装入到内存； 不存在调用关系的模块不必同时装入到内存，从而可以相互覆盖。(即不同时用的模块可共用一个分区),64,注：另一种覆

30、盖方法：(100K) A(20K)占一个分区：20K； B(50K)、D(20K)、E(40K)共用一个分区：50K； F(30K)、C(30K)共用一个分区：30K；,覆盖技术,65,4.4 基本分页存储管理方式,连续分配方式会形成许多碎片，虽然可通过紧凑方法将许多 碎片拼接成可用的大块空间，但须付出很大开销。 如果允许将一个进程直接分散地装入到许多不相邻接的分区 中，则无须再紧凑。基于这一思想而产生了离散分配方式。 如果离散分配的基本单位是页，则称为分页存储管理方式。 如果离散分配的基本单位是段，则称为分段存储管理方式。,4.4.1 页式存储管理的引入,66,分页：将一个进程的逻辑地址空间

31、分成若干个大小相等的片，称为页或页面，并为各页加以编号，从0开始，如第0页、第1页等。 块：把内存空间分成与页面相同大小的若干存储块，称为(物理)块或页框。也同样为各块加以编号，如0#块、1#块等。 内存分配：在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。逻辑上相邻的页，物理块不一定相邻。 页内碎片：由于进程的最后一页经常装不满一块而形成了不可利用的碎片。 页面大小：页面的大小应选择适中，且页面大小应是2的幂,通常为512 B8 KB。,4.4.2 页面与页表,67,68,69,页表：列出了进程的逻辑地址与其在内存中的物理地址间的对应关系。 一个页表中包

32、含若干个表目，表目的自然序号对应进程中的页号，表目中的块号是该页对应的物理块号。 页表的作用是实现从页号到物理块号的地址映射。 在配备了页表后，进程执行时，通过查找该表，即可找到每页在内存中的物理块号。,70,分页管理中页与页框的对应系示意图,71,(每个进程对应一个页表）,72,地址结构,分页地址中的地址结构如下：,含有两部分：前一部分是页号P； 后一部分是位移量W(或称为页内地址)。 图中地址长度为32位： 011位为页内地址，共212个可用地址，按字节编址，则每页的大小为4KB； 1231位为页号，共220个可用地址，地址空间最多允 许有1M页。,73,对某特定机器，其地址结构是一定的。

33、则所有进程最多可分多少页，每个页面的大小是一定的并相同的。 若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按下式求得：,例如：某系统的页面大小为1KB,设A=2170B，则由上式可以求得P=2,d=122,74,4.4.3 地址变换机构,1. 基本的地址变换机构,图 4-13分页系统的地址变换机构,75,2.具有快表的地址变换机构,由于页表是存放在内存中的，这使cpu在每存取一个数据时，都要两次访问内存：第一次是访问内存中的页表，从中找到指定页的物理块号，再将块号与页内地址拼接以形成物理地址。第二次访问内存才是从第一次所得物理地址中读或写数据。因此采用这种方式将使计

34、算机的处理速度降低近1/2。 为了解决这个问题人们采用一组硬件寄存器，存放当前访问过的页的页描述子形成快表；每次访问内存时，首先查找快表，若找到所需的页描述子，则快速形成物理地址。否则从页表中查找后形成物理地址，同时把页描述子写入快表。如果设计得当，快表的命中率可以很高。,76,具有快表的地址变换机构,图 4-14 具有快表的地址变换机构,77,课堂练习,已知：页面大小为1k，求逻辑地址 2500， 3200，0A5CH，094EH 对应的物理地址。 思考：若页面大小为4K呢？,解：逻辑地址2500对应的： 页号：P=2500/1024=2 页内地址：d=2500 mod 1024 =452

35、搜索页表得知：页号为2对应物理块号是5 因为页面大小与物理块大小是相等的，所以物理块的大小也为1k 又因为页内地址与物理块内地址是一一对应的 所以逻辑地址2500对应的物理地址为： 51024 + 452 =5572 该块的起始地址 物理块内地址,78,解：逻辑地址0A5CH为十六进制数，转换为二进制为： 0000 1010 0101 1100 已知页面大小为1k=210，所以页内地址为后10位：10 0101 1100 所以页号为前6位： 0000 10 转换为十进制为：2 搜索页表得知：页号为2对应物理块号是5， 将物理块号5转换为二进制为： 000101 又因为页内地址与物理块内地址是一

36、一对应的 所以逻辑地址0A5CH 对应的物理地址为： 0001 0110 0101 1100 1 6 5 C,79,4.4.4 两级和多级页表,现代的大多数计算机系统，都支持非常大的逻辑地址空间(232264)。页表就变得非常大，要占用相当大的内存空间。可采用两个方法来解决这一问题： 采用离散分配方式来解决难以找到一块连续的大内存空间的问题： 只将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入。,80,1. 两级页表,逻辑地址结构可描述如下：,81,图 4-15两级页表结构,82,页目录地址,目录位移,页表位移,页位移,虚拟地址,页表地址,. . .,页目录（每进程一个

37、）,块号,. . .,页表,代码或数据,. . .,内存块,二级页表结构及地址映射,+,+,83,多级页表,为缩短查找时间，多级页表中的每级都可以装 入到快表 （即页表的高速缓存）中，并按照cache 的原理进行更新。 多级页表结构中，指令所给出的地址除偏移地 址之外的各部分全是各级页表的页表号或页号 ，而各级页表中记录的全是物理页号，指向下级页表或真正的被访问页。,84,85,4.5 基本分段存储管理方式,86,4.5.1 分段式存储管理的引入,在分页存储系统中，作业的地址空间是一维线性的(只须 给出一个逻辑地址)，这破坏了程序内部天然的逻辑信息结构, 造成共享、保护的困难。 引入分段存储管

38、理方式， 主要是为了满足用户和程序员 的下述需要： 1) 方便编程 2) 信息共享 3) 信息保护 4) 动态增长 5) 动态链接,87,分段存储管理,分段地址空间：一个段可定义为一组逻辑信息，每个作业的地址空间是由一些分段构成的，每段都有自己的名字，且都是一段连续的地址空间。,88,汇编过程中将原程序分成逻辑上的二段 data segment a db ? b db ? c db ? string db c=$ data ends code segment main proc far assume cs:code,ds:data,es:data start: push ds sub ax,a

39、x push ax mov ax,data mov ds,ax mov es,ax,mov a,1 mov b,2 mov al,a add al,b mov c,al lea dx,string mov ah,09 int 21h add c,30h mov dl,c mov ah,2 int 21h mov dl,0ah int 21h mov dl,0dh int 21h ret end start main endp code ends,高级语言程序编译分二个阶段：1.汇编2.目标文件 例： c = a + b,所以分段方式 已得到许多编译程序的支持.编译程序能自动根据源程序情况而 产

40、生若干个段。 装入程序将装入所有段，并为每个段赋予一个段号。,89,90,4.5.2 分段系统的基本原理,1.分段,作业的地址空间被划分为若干个段，每个段定义一组逻辑 信息。 每个段都有自己的名字。通常可用一个段号来代替段名。 每个段都从0开始编址，并采用一段连续的地址空间。 段的长度由相应的逻辑信息组的长度决定，因而各段长度 不等。 整个作业的地址空间由于是分成多个段，因而是二维的， 其逻辑地址由段号（段名）和段内地址所组成。,91,分段地址中的地址具有如下结构：,含有两部分：前一部分是段号； 后一部分是段内地址 图中地址长度为32位： 015位为段内地址，共216个可用地址，按字节编址，则

41、每个段的最大长度为64KB。 1631位为段号，共216个可用地址，地址空间最多允 许有64K，所以允许一个作业最长有64K个段。,92,2.段表,在分段式管理系统中，为每个分段分配一个连续的分区，而进程中的各个段可以离散地移入内存不同的分区中。 为了能从物理内存中找出每个逻辑段所对应的位置， 为每个进程建立一张段映射表，简称段表。 每个段在表中占有一个表项，记录了该段的段长和段在内存中的起始地址。 每一个进程设置一个段表,存放在内存,属于进程的现场信息。 段表用于实现从逻辑段到物理内存区的映射。 配置了段表，执行中的进程可通过查找段表找到每个段所对应的内存区。,93,它记录了段号，段首址和段

42、长之间的关系。,94,分段管理中作业i与段表、存储空间的关系,95,段表的硬件支持,系统设置一对寄存器： 段表始址寄存器：用于保存正在运行进程的段表的始址。 段表长度寄存器：用于保存正在运行进程的段表的长度。,96,3. 地址变换机构,图 4-18 分段系统的地址变换过程,97,与分页系统一样，当段表放在内存时，每存取一个数据，都要访问两次内存，从而降低了访问速度。解决方法和分页类似，再增设一个联想寄存器，用于保存最近常用的段表项，称为快表。,98,Cl,Cb,+,段号S 段内地址d,比较,比较,b + d,段表,S= Cl,快表,物理地址,段表始址寄存器,段表长度寄存器,逻辑地址,L,b,.

43、,.,.,S,L,b,地址越界,d=L,d=L,有快表的地址映射及存储保护机制,地址越界,地址越界,比较,99,4. 分页和分段的比较,相同点： 两者均用离散分配方式，且均通过地址映射机构实现地址转换。 不同点： 分页是出于系统管理的需要，分段是出于用户应用的需要。 一条指令或一个操作数可能会跨越两个页的分界处，而不会跨越两个段的分界处。 页大小是系统固定的，而段大小则通常不固定。 逻辑地址表示： 分页是一维的，各个模块在链接时必须组织成同一个地址空间。 分段是二维的，各个模块在链接时可以每个段组织成一个地址空间。 通常段比页大，因而段表比页表短，可以缩短查找时间提高访问速度。,100,页式管

44、理与段式管理的比较,101,4.5.3 信息共享,图 4-19 分页系统中共享editor的示意图,102,图 4-20 分段系统中共享editor的示意图,103,分段管理的优缺点,优点： 没有内碎片，外碎片可以通过内存紧缩来消除。 便于改变进程占用空间的大小。 缺点： 在辅存中管理不定长度的分段比较困难。 分段的最大尺寸受到主存可用空间的限制。 思考： 与可变分区存储管理方案的相同点与不同点？,104,4.5.4 段页式存储管理,将分页与分段各取所长：既有分段系统的便于实现、分段可共享、易于保护、可动态链接的优点，又具有分页系统便于解决外部碎片问题的优点。,105,基本思想： 用分段方法来

45、分配和管理虚拟存储器，而用分页方法来分配和管理实存储器。,106,实现原理,一个程序首先被分成若干程序段，每一段赋予不同的分段标识符，然后，对每一分段又分成若干个固定大小的页面。 地址结构：S+P+W S：段号 P：页号 W：页内位移量,107,108,4.6 虚拟存储器的基本概念,问题的提出： 有的作业很大，所要求内存空间超过了内存总容量, 作业不能全部被装入内存。 有大量作业要求运行，但由于内存容量不足，只能 将少数作业装入内存让它们先运行，而将其他大量 作业留在外存等待。 以上原因均由于内存容量不够大。 解决方法： 从物理上增加内存，受机器自身及成本的限制。 从逻辑上扩充内存，这正是虚拟

46、存储技术所要解决 的基本问题。,1 虚拟存储器的引入,109,虚拟存储器的基本思想： 程序、数据、堆栈的大小可以超过内存的大小，操作系统把程序当前使用的部分保留在内存，而把其它部分保存在磁盘上，并在需要时在内存和磁盘之间动态交换。 虚拟存储器支持多道程序技术。,110,2 虚拟存储器,具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的存储器系统。 其逻辑容量由内存容量和外存容量之和所决定。其运行速度接近于内存，而每位的成本却又接近于外存。 虚拟存储器就是一个地址空间，且具有比实际内存大得多的容量。,111,对用户：指令地址部分所限定的比实存大得多的地址实间。 对系统：借助于各种表格机构

47、，体现虚拟空间。,112,程序局部性原理： 在一段时间内一个程序的执行往往呈现出高度的局部性，表现在时间与空间两方面： 时间局部性： 一条指令被执行了，则在不久的将来它可能再被执行。 空间局部性： 若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被使用。,3 局部性原理,113,4 虚拟存储器基本原理,在程序装入时，不必将其全部读入到内存， 而只需将当前需要执行的部分页或段读入到内存 ，就可让程序开始执行。 在程序执行过程中， 如果需执行的指令或访问的数据尚未在内存（称为缺页或缺段）， 则由处理器通知OS将相应的页或段调入到内 存，然后继续执行程序。 另一方面，OS将内存中暂时

48、不使用的页或段调出保存在外存上，从而腾出空间存放将要装入的程序以及将要调入的页或段-具有请求调入和置换功能，只需程序的一部分在内存就可执行，对于动态链接库也可以请求调入。,114,优点,可在较小的可用内存中执行较大的用户程序； 可在内存中容纳更多程序并发执行； 不必影响编程时的程序结构 (与覆盖技术比较)； 提供给用户可用的虚拟内存空间通常大于物理内存(real memory)。,115,虚拟内存大于物理内存的示意图,116,5 虚拟存储技术特征,离散性：物理内存分配的不连续，虚拟地址空间使用的不连续 ( 数据段和栈段之间的空闲空间， 共享段和动态链接库占用的空间 )。 多次性。 对换性：与交

49、换的比较：调入和调出是对部分虚拟地址空间进行。 虚拟性：通过物理内存和快速外存相结合，提供大范围的虚拟地址空间。 范围大，但占用容量不超过物理内存和外存交换区 容量之和。占用容量包括：进程地址空间中的各个段，操作系统代码。,117,6 虚拟存储器的容量,一个虚拟存储器的最大容量由计算机的地址结构确定。如：若CPU的有效地址长度为32位，则程序可以寻址范围是0(232)-1 ，即虚存最大容量为 4GB。 虚拟存储器的容量与主存的实际大小没有直接关系，而由主存与辅存的容量之和所确定。,118,119,7 虚拟存储器的实现方法,请求分页系统 虚拟内存通常采用的方法。 在分页系统基础上， 增加了请求调页功能和页面置换功能。允许只装入少数页面的程序(及数据)便启