《操作系统原理》PPT课件.ppt

1,第二章 存储管理,2.1 存储管理基础 2.2 基本存储管理方法 2.3 可变分区存储管理方法 2.4 内存扩充技术 2.5 纯分页的存储管理 2.6 请求分页系统 2.7 段式存储管理 2.8 段页式存储管理 2.9 Linux存储管理,2,存储器可分为：内存储器和外存储器；内存储器：可以被CPU直接访问。外存储器：不可以被CPU直接访问，外存与CPU之间只能够在输入输出控制系统的管理下，进行信息交换。,3,2.1 存储管理基础,2.1.1 虚拟地址与物理地址,4,内存储器是由一个个存储单元组成，一个存储单元可存放若干个二进制的位（bit），8个二进制位被称为一个字节（Byte）。内存中的存储单元按一定顺序进行编号，每个单元所对应的编号，称为该单元的单元地址。物理地址（绝对地址，实地址）：内存中存储单元的地址。物理地址可直接寻址。逻辑地址（相对地址，虚地址）：用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式。其首地址为0，其余指令中的地址都相对于首地址来编址。不能用逻辑地址在内存中读取信息。,5,6,地址重定位,地址重定位（地址映射）：将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址。当程序装入内存时,操作系统要为该程序分配一个合适的内存空间，由于程序的逻辑地址与分配到内存物理地址不一致,而CPU执行指令时，是按物理地址进行的，所以要进行地址转换。,7,2.1.2 地址定位方式,1.固定定位方式,由程序员在编写程序时或由编译连接程序对源程序进行编译连接时，直接指定程序在执行时访问的实际存储器地址的方式称为固定定位方式。此种定位方式一般只适合于单板机或单用户系统。在多道程序环境下，应保证各个作业的地址互不重叠，这就比较困难了。,8,9,2.静态重定位方式,源程序经编译和连接后生成目标代码中的地址是以0为起始地址的相对地址。当需要执行时，由装入程序运行重定位程序模块，根据作业在本次分配到的内存起始地址，将可执行目标代码装到指定内存地址中，并修改所有有关地址部分的值。修改的方式是对每一个逻辑地址的值加上内存区首地址（或称基地址）值。,10,11,静态重定位的特点,（1）静态重定位是在程序运行之前完成地址重定位工作的；（2）静态重定位由软件实现，无须硬件提供支持；（3）实行静态重定位时，地址重定位工作是在程序装入时被一次集中完成的；（4）绝对地址空间里的目标程序与原相对地址空间里的目标程序面目已不相同，因为前者进行了地址调整；（5）实施静态重定位后，若用户程序在内存中做了移动，那么程序指令中的地址就不再反映所在的存储位置了，除非重新进行地址重定位。,12,3.动态重定位方式,采用动态重定位方式，将程序在装入内存时，不必修改程序的逻辑地址值，程序执行期间在访问内存之前，再实时地将逻辑地址变换成物理地址。动态重定位要靠硬件地址变换机构实现。当程序开始执行时，系统将程序在内存的起始地址送入地址变换机构中的基地址寄存器BR中。在执行指令时，若涉及到逻辑地址，则先将该地址送入虚拟地址寄存器 VR，再将BR 和 VR 中的值相加后送入地址寄存器 MR，并按 MR 中的值访问内存。（MR）=（BR）+（VR）,13,14,2.2 基本存储管理方法,2.2.1 单一连续分区存储管理,基本思想：内存分为两个区域：系统区，用户区。应用程序装入到用户区，可使用用户区全部空间。最简单，适用于单用户、单任务的OS；单用户系统在一段时间内，只有一个进程在内存。,15,特点,（1）系统总是把整个用户区分配给一个用户使用。（2）实际上，内存用户区又被分为“使用区”和“空闲区”两部分。在操作系统中，把分配给用户、但又未使用的区域称为“内部碎片”。（3）由于任何时刻内存的用户区中只有一个作业运行，因此这种系统只使用于单用户的情况。（4）进入内存的作业，独享系统中的所有资源，包括内存中的整个用户区。,16,特点,（5）由于整个用户区都分配给了一个用户使用，因此作业进入用户区后，没有移动的必要。采用这种存储分配策略时，将对用户程序实行静态重定位。（6）实行静态重定位，并不能阻止用户有意无意地通过不恰当地指令闯入操作系统所占用的存储区域，如何阻止对操作系统的侵扰，就是所谓的“存储保护”问题。用于存储保护的专用寄存器“界限寄存器”,17,存储保护过程：在用户态下，对内存的每一次访问，都要在硬件的控制下，与界限寄存器中的内容进行比较。一旦发现该访问的地址小于界限寄存器中的地址，就会产生“地址越界”中断，阻止这次访问的进行。优点：易于管理，便于用户的了解和使用。缺点：由于每次只能有一个作业进入内存，故它不适用于多道程序设计，整个系统的工作效率不高，资源利用率底下。只要作业比用户区小，那么在用户区里就会形成碎片，造成内存储器资源的浪费。若用户作业的相对地址空间比用户区大，那么该作业就无法运行。,18,2.2.2 固定分区存储管理,把内存区固定地划分为若干个大小相等（和不等）的连续分区。每个分区装一个且只能装一个作业，分区的划分原则一般由系统操作员或操作系统决定，分区一旦划分结束，在整个执行过程中每个分区的长度和内存的总分区个数将保持不变。分区大小相等：只适合于多个相同程序的并发执行（处理多个类型相同的对象）。分区大小不等：多个小分区、适量的中等分区、少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区。,19,固定分区(大小相同),固定分区(多种大小),20,内存分配,为了便于内存分配，通常将分区按大小进行排队，并为之建立一张分区说明表，其中各表项包括每个分区的起始地址、大小及状态（是否已分配）。当有一用户程序要装入时，由内存分配程序检索该表，从中找出一个能满足要求的、尚未分配的分区，将之分配给该应用程序，然后将该表项中的状态置为“已分配”；若未找到大小足够的分区，则拒绝为该用户程序分配内存。,21,22,地址重定位与存储保护,固定分区存储管理中，每个分区只允许装入一个作业，作业在运行期间没有必要移动自己的位置，因此，应该对程序实行静态重定位。在固定分区存储管理中，不仅要防止用户程序对操作系统形成的侵扰，也要防止用户程序与用户程序之间形成侵扰。因此必须在CPU中设置一对专用的寄存器，用于存储保护。将两个专用寄存器分别起名为“下界寄存器”和“上界寄存器”,23,存储保护过程,当进程调度程序调度某个作业进程运行时，就把该作业所在分区的低边界地址装入到低界限寄存器，高边界地址装入到高界限寄存器。作业运行时，对内存的每一次访问，都要在硬件的控制下，与两个界限寄存器中的内容进行比较。一旦发现该访问的地址小于界限寄存器中的地址，就会产生“地址越界”中断，阻止这次访问的进行。,24,固定分区存储管理的特点,（1）它是最简单的、具有“多道”色彩的存储管理方案。（2）当把一个分区分配给某个作业时，该作业的程序将一次性的全部被装入到分配给它的连续分区里。,25,优点：易于实现，开销小。缺点：内碎片造成浪费（小作业不能有效地利用分区空间。分区总数在系统生成时确定（固定），限制了并发执行的程序数目。如果到达作业的尺寸比任何一个分区的长度都大，那么它就无法得到运行。,固定分区方式的评价,26,2.3 可变分区存储管理,基本思想：内存不是预先划分好的，而是当作业装入时，根据作业的需求和内存空间的使用情况来决定是否分配。若有足够的空间，则按需要分割一部分分区给该进程否则令其等待主存空间优点：没有内碎片。缺点：有外碎片。,27,外部碎片问题,作业A(16KB),空闲区(236KB),空闲区(220KB),作业B(100KB),空闲区(120KB),作业C(70KB),空闲区(50KB),空闲区(100KB),作业D(75KB),空闲区(25KB),内碎片：占用分区之内未被利用的空间外碎片：占用分区之间难以利用的空闲分区（通常是小空闲分区）。,28,2.3.1 空闲存储区表,管理空闲内存区的数据结构可采用链接法和连续线性表格法。下面举一个连续线性表格管理空闲内存的方法，如采用链接法，就需要在表项中增加一个指向下一个空闲区的指针。每一个空闲分区用一个map结构管理：struct map unsigned m_size;/空闲分区的长度 char*m_addr;/空闲分区的起始地址;struct map coremapN;各个空闲分区按起始地址由低到高顺次登记在空闲存储区表中，m_size为0的表项是空白表项，它们集中在表的后部,29,在系统初始阶段，拥有一块很大的内存空白区，这时空闲存储区表coremap中只需有一项登记该空闲区。其余的coremap表项为空白项，即m_size皆为零。,30,以后随着很多作业的不断申请内存和释放内存，整个存储空间将出现许多大小不等的区域，存储区表和实际的内存空间就可能变成如图所示的情况。,31,2.3.2 首次适应算法,1.分配算法。采用首次适应法为作业分配大小为size的内存空间时，总是从表的起始端的低地址部分开始查找。当第一次找到大于或等于申请大小的空闲区时，就按所需大小分配给作业。如果分配后原空闲区还有剩余空间，就修改原存储区表项的 m_size 和 m_addr，使它记录余下的“零头”。如果作业所需空间正好等于该空闲区大小，那么该空闲区表项的m_size就成为0。接下来要删除表中这个“空洞”，即将随后的各非零表项依次上移一个位置,32,char*malloc(mp,size)struct map*mp;unsigned size;register char*a;register struct map*bp;for(bp=mp;bp-m_size;bp+)if(bp-m_size=size)a=bp-m_addr;bp-m_addr+=size;if(bp-m_size-=size)=0)do bp+;(bp-1)-m_addr=bp-m_addr;while(bp-1)-m_size=bp-m_size);return(a);return(0);,33,2.回收算法,当某一作业释放以前所分配到的内存时，就要将该内存区归还给系统，使其成为空闲区而可被其他作业使用。释放区与原空闲区相邻情况可归纳为如图所示的4种情况。,34,仅与前空闲区相连：合并前空闲区和释放区构成一块大的新空闲区，并修改空闲区表项。该空闲区的m_addr不变，仍为原前空闲区的首地址，修改表项的长度域m_size为原m_size 与释放区长度之和。与前空闲区和后空闲区都相连：将三块空闲区合并成一块空闲区。修改空闲区表中前空闲区表项，其起始地址m_addr仍为原前空闲区起始地址，其大小m_size等于三个空闲区长度之和，这块大的空闲区由前空闲区表项登记。接下来还要在空闲区表中删除后项，方法是将后项以下的非空白表项顺次上移一个位置。,35,仅与后空闲区相连：与后空闲区合并，使后空闲区表项的m_addr为释放区的起始地址，m_size为释放区与后空闲区的长度之和。与前、后空闲区皆不相连：在前、后空闲区表项中间插入一个新的表项，其 m_addr为释放区的起始地址，m_size为释放区的长度。为此，先要将后项及以下表项都下移一个位置,36,若采用首次适应法，则其分配算法简单且合并相邻空闲区也很容易。该算法的实质是尽可能利用存储区低地址部分的空闲区，而尽量在高地址部分保存较大的空闲区，以便一旦有分配大的空闲区的要求时，容易得到满足。其缺点是由于查找总是从表首开始，前面的空闲区往往被分割得很小，能满足分配要求的可能性较小，查找次数就较多。系统中作业越多，这个问题就越严重。,37,2.3.3 循环首次适应算法,把空闲表设计成顺序结构或链接结构的循环队列，各空闲区仍按地址从低到高的次序登记在空闲区的管理队列中。同时需要设置一个起始查找指针，指向循环队列中的一个空闲区表项。循环首次适应法分配时总是从起始查找指针所指的表项开始查找。第一次找到满足要求的空闲区时，就分配所需大小的空闲区，修改表项，并调整起始查找指针，使其指向队列中被分配的后面的那块空闲区。下次分配时就从新指向的那块空闲区开始查找。,38,2.3.3 循环首次适应算法,循环首次适应法的实质是起始查找指针所指的空闲区和其后的空闲区群常为较长时间未被分割过的空闲区，它们已合并成为大的空闲区可能性较大。比起首次适应法来，在没有增加多少代价的情况下却明显地提高了分配查找的速度。释放算法基本同首次适应法一样。首次适应法和循环首次适应法不仅可用于内存的分配和释放，也可用于进程图像交换的辅存空间的分配和释放，其管理空闲区的数据结构也相同。,39,2.3.4 最佳适应算法,所谓最佳适应算法就是在所有大于或等于要求分配长度的空闲分区中挑选一个最小的分区，在分割后，所余下的剩余存储区最小或等于零。因此，该算法的空闲区利用率高，较大的空闲区被保存下来。空闲存储区管理表的组织方法可以采用顺序结构，也可采用链接结构。如采用顺序结构，空闲分区按地址由小到大的顺序登记在表中，分配时需要搜索所有的空闲分区，以在其中挑出一个满足分配大小的最小的分区。此种管理结构的释放算法可用顺序结构的首次适应法。,40,2.3.4 最佳适应算法,当采用链接结构时，空闲区也可按由小到大的非递减次序排列。分配时总是从最小的第一项开始，这样第一次找到的满足条件的空闲区必定是最合适的。平均而言，只要搜索一半数目的空闲区表项就能找到最佳配合的空闲区，但寻找较大空闲区比较费时。采用按存储区大小排序的链接表会降低释放算法的效率。由于空闲区是按大小而不是按地址序号排序的，因此释放回收空闲区时要在整个链表上寻找地址相邻的前、后空闲区，合并后又要插入到合适的位置，因此释放算法比前两种算法耗时得多。,41,2.3.5 最差适应算法,最差适应法所分割的空闲存储区是所有空闲分区中的最大的一块。在实施最差适应法时，空闲区管理表项一般以m_size由大到小的次序组织成一个链接表，因此查找分割的总是最大的第一个空闲存储区。实现最差适应法时的空闲存储区表的组织方法一般都是采用按空闲块由大到小排序的链接表。采用按存储区大小顺序排列的链接表的形式虽然释放一个空闲块时速度较慢，但分配效率是一切算法中最高的一种。,42,可变分区存储管理的特点,（1）作业一次性的全部装入到一个连续的存储分区中。（2）分区是按照作业对存储的需求划分的，因此在可变分区管理中，不会出现内部碎片这样的存储浪费。（3）为了确保作业能够在内存中移动，要由硬件支持，实行指令地址的动态重定位。,43,可变分区存储管理的缺点,（1）仍然没有解决小内存运行大作业的问题。（2）虽然避免了内部碎片造成的存储浪费，但有可能出现极小的分区暂时分配不出去的情形，引起外部碎片。（3）为了形成大的分区，可变分区存储管理通过移动程序来达到分区合并的目的，然而程序的移动是很花费时间的，增加了系统在这方面的开销。,44,2.3.6 多重分区,可变分区存储管理算法是按作业对存储的需求分配存储区的，因而消除了固定分区内部的剩余碎片，但随着存储区的分配和释放过程的进行，在各个被分配出去的分区之间会存在很多的空闲区，这就是“外部碎片”。有时，当一个作业要装入运行，但分配不到一个够用的空闲分区，尽管这时内存中所有外部碎片的总和远大于作业所申请的空间。如采用“紧凑”技术重新安排内存中各个作业的位置，以使零碎的空闲区集中起来，这是一个极其耗时的过程，一般很少采用这种策略。,45,否,否,是,是,46,2.3.6 多重分区,有些系统采用多重分区技术，在作业的运行过程中可以申请附加的分区，以装入一个或多个子程序。新申请的空闲分区也无需与作业的现有分区相邻接。采用多重分区技术可以提高外部碎片的利用率，也便于多个作业共享分区的代码和数据，这只要在共享的作业中包含某个共享的分区即可。多重分区系统应当采用动态重定位技术，但存储管理的复杂性也增加了。为了实现存储保护，在多重分区系统中要设置多对界地址寄存器，以使现运行作业对每一个分区的访问都不会越界。,47,2.4 内存扩充技术,在基本的存储管理系统中，当一个作业的程序地址空间大于内存可用空间时，该作业就不能装入运行；当并发运行作业的程序地址空间总和大于内存可用空间时，多道程序设计的实现就会碰到很大的困难。内存扩充技术就是借助大容量的辅存在逻辑上实现内存的扩充，以解决内存容量不足的问题。,48,2.4.1 覆盖(overlay),引入：其目标是在较小的可用内存中运行较大的程序。原理：覆盖技术就是将一个大程序按程序的逻辑结构划分成若干个程序（或数据）段，并将不会同时执行，从而就不必同时装入内存的程序段分在一组内，该组称为覆盖段。这个覆盖段可分配到同一个称为覆盖区的存储区域。将程序的必要部分（常用功能）的代码和数据常驻内存；可选部分（不常用功能）在其他程序模块中实现，平时存放在外存中（覆盖文件），在需要用到时才装入到内存；不存在调用关系的模块不必同时装入到内存，从而可以相互覆盖。(即不同时用的模块可共用一个分区),49,注：另一种覆盖方法：(100K)A(20K)占一个分区：20K；B(50K)、D(20K)和E(40K)共用一个分区：50K；F(30K)和C(30K)共用一个分区：30K；,50,缺点：对用户不透明，增加了用户负担。编程时必须划分程序模块和确定程序模块之间的覆盖关系，增加编程复杂度。从外存装入覆盖文件，以时间延长来换取空间节省。覆盖不需要任何来自操作系统的特殊支持，由用户程序自己控制 所以，覆盖通常限于用在微机和其他内存容量有限的或缺乏对更先进技术的硬件支持的系统中,51,2.4.2 交换(swapping),引入：让单一连续分区存储管理能具有“多道”的效果。中心思想：将作业信息都存放在辅存上，根据单一连续分区存储管理的分配策略，每次只让其中一个进入内存投入运行，当运行中提出输入输出请求或分配的时间片用完时，就把这个程序从内存储器“换出”到辅存，把辅存里的另一个作业“换入”内存运行。这样从宏观上看，系统中同时就有几个作业处在运行之中。为了减少在主存和辅存间传输的数据量，可以只将原作业的一部分保存到辅存中去，只要释放的主存空间刚好够装入下一个运行作业就行。在以后的适当时间，作业移出的部分可装入到原来的存储区中继续运行下去。这种技术称之为交换技术，也叫“滚进滚出”,52,53,优点：增加并发运行的程序数目，并且给用户提供适当的响应时间；编写程序时不影响程序结构缺点：对换入和换出的控制增加处理机开销；程序整个地址空间都进行传送，没有考虑执行过程中地址访问的统计特性。,交换技术的优缺点,54,交换与覆盖的比较,与覆盖技术相比，交换技术不要求用户给出程序段之间的逻辑覆盖结构。交换发生在进程或作业之间，而覆盖发生在同一进程或作业内。覆盖只能覆盖那些与覆盖段无关的程序段。,55,2.4.3 虚拟存储器,在现代的计算机系统中，一个作业即使不全部装入主存，也同样能正确运行，因为：在一个程序中一般都有相当数量的出错处理子程序，在正常的运行过程中很少执行到这些程序；程序中一般都含有类似then和else的彼此互斥的部分，在程序的一次执行中往往只选择其中的一条路径执行；程序中的初始化部分一般只执行一次，初始化工作完成后，这些代码就没有存放在主存中的必要；,56,2.4.3 虚拟存储器,从运行的时间角度来分析，在一段时间内，作业一般不会执行到所有程序段的指令和存取绝大部分数据，它往往相对集中地访问某些区域中的指令和数据，这就是程序运行的“局部性原理”。在主存中可只装入最近经常要访问的某些区域的指令和数据，剩余部分就暂时不必装入，等到以后要访问到它们时再调入内存。如果主存较紧张，必要时可将已不大访问的信息调出内存，再执行调入操作。这样，程序运行时所需要的实际内存就可以远小于程序的虚拟地址空间。,57,由于作业的指令和数据可以存放在外存中，用户的程序就不受实际内存大小的限制，好像计算机系统向用户系统提供了容量极大的“主存”，而这个大容量的“主存”是靠存储管理的软件和硬件通过大容量的辅存作为后援存储器扩充而获得的，是程序设计员感觉到的，而实际上并不存在的存储器，故称虚拟存储器。采用虚拟存储器技术究竟可运行多大的程序呢？当然也不能无限大，它受到以下两个条件的限制。,58,指令地址字长的限制。地址字长决定了程序所能访问的虚拟地址空间的大小，如对于32位字长的地址字可构成4GB的虚拟地址空间。存放程序指令和数据的外存储器的大小，这种外存叫做交换设备，存放程序指令和数据的外存区域称为交换区。采用虚拟存储管理策略，在作业运行时就要由地址映像机构将程序的逻辑地址转换成内存的物理地址。此外，还要决定将虚拟地址空间中的哪一部分装入主存，装入主存的位置以及当主存中的空闲区不够时将哪一部分空间的内容调至交换区中。这些都是虚拟存储管理中要解决的新的技术问题。,59,2.5 纯分页的存储管理,可变分区存储管理：连续分配存储空间。分页式存储管理：打破了“连续”的禁锢，把对存储的管理大大推进了一步。分页式存储管理是将固定分区方法与动态重定位技术结合在一起的一种存储管理方案，它需要硬件的支持。,60,2.5.1 分页存储管理的基本思想,作业的虚拟地址空间划分成若干长度相等的页（page），也称虚页，每一个作业的虚页都从 0 开始编号。主存也划分成若干与虚页长度相等的页架（frame），也称页框或实页，主存的页架也从 0开始编号。程序装入时，每一个虚页装到主存中的一个页架中，这些页架可以是不连续的。需要CPU的硬件支持。,61,例：,62,把用户程序按逻辑页划分成大小相等的部分，称为页。从0开始编制页号，页内地址是相对于0编址,用户程序划分,例：页的大小为4K相对地址5188，对应数对（1，1092）；相对地址9200，对应数对（2，1008）。,63,2.5.2 地址变换,在分页系统中，页的大小都是2的整数次幂，这样分页地址中的地址结构如下：,31,12,11,0,虚拟地址字的页内偏移部分占据低n个二进制位，使2n刚好等于页的大小，这样安排便于硬件直接截取高位部分的页号和低位部分的页内偏移值。,64,例：,某系统的地址结构长为16位，相对地址3000的二进制位表示如下：,块尺寸1KB，对应数对（2，952）；块尺寸256字节，对应数对（11，184）。,65,程序的虚拟地址空间是连续的，但程序的虚页可以分配到主存中不连续的空闲页架中；故分页系统需要在主存中开辟一个页表区域来建立每一个作业的虚页号到内存的页架号之间的映射关系。系统还需要建立一个总页表来记录各个作业页表的起始地址和长度，并将当前运行进程的页表起始地址和长度存放在页表控制寄存器中。,66,每一个作业的页表空间可以是连续的，也可以是不连续的，但连续的页表空间管理方便，存取速度也快。连续的页表要分配的空间本身又相当于一个小分区，故可采用前面讨论的分区分配和释放算法。连续的页表空间同时也带来了页表分区之间的存储区碎片问题，但由于一个作业的页表空间比作业本身的程序和数据空间小得多，故这个问题相对来说并不严重,67,基本的地址变换机构,页表保存在内存中；硬件设置一个专用寄存器：“页表寄存器”每当进程调度时，把调度到进程的页表起始地址和页表长度（即页表表项的数目）放入寄存器中。,68,地址转换过程,1）由硬件自动将虚拟地址字分成虚页号和页内偏移两部分；2）由页表控制寄存器中页表起始地址和虚拟地址字中的虚页号查找页表，对应虚页号的页表表项地址为：页表起始地址+虚页号*页表表项长度；3）将页表中取出的页架号和虚拟地址字中的页内偏移值装入地址寄存器，根据地址寄存器中的地址值访问主存。页表控制寄存器中的“长度”起到存储保护的作用，每个相对地址中的页号都不能大于该长度，否则出错。,69,70,例,若在分页式存储管理中，建立了某个作业的页，块对应关系为：第0页放在第0块，第1页放在第3块，第2页放在第1块，如下所示。已知块的尺寸为1KB/块。求相对地址1023、1024、3000、所对应的绝对地址。,解：10231023 10243072 30001976,71,缺点,（1）页表放在内存，增加了系统在存储上的开销；（2）降低了CPU的访问速度。因为每次对某一地址的访问，首先要访问内存中的页表，形成绝对地址后，才能进行所需要的真正访问。,72,2.5.3 具有快表的地址变换机构,考虑到大多数程序在一次调度运行时，倾向于在少数页面中进行频繁的访问（这被称为程序的“局部性”原理），因此实际系统中的做法是采用内存页表与快速寄存器组相结合的解决方案，并且利用程序局部性原理，只用极少数几个快速寄存器来构成快速寄存器组，这时把快速寄存器组单独起名为“快表”，主存中的页表有时也称为慢表。,73,快表由CPU中的高速cache或联想寄存器构成。联想寄存器是一种按内容进行并行查找的一组快速寄存器，当在其输入端有一个输入值页号p时，在联想寄存器中存放页号为p的那一项就立即选中，并输出其变换值页架号 b。由于访问联想寄存器比访问主存快得多，故极大地提高了地址变换速度。,74,地址的映射,快表中存放的是页表内容的一部分。在进行地址变换时，变换机构根据虚拟地址字中的页号同时查找快表和慢表;一旦在快表中查到虚页号，就用输出的页架号和虚拟地址字中的偏移地址构造主存物理地址；否则，就用慢表中查到的页架号构造主存物理地址，同时还用慢表的该表项更新快表，这就可能需要按某一算法淘汰快表中某一表项，以便下次再访问该页的过程能在快表中进行。,75,76,由于成本关系，快表不可能做的很大，通常只存放16512个页表项，这对于中、小型作业来说，已有可能把全部页表项放在快表中，但对于大型作业，则只能将其一部分页表项放入其中。据统计，快表中如含有 8 个表项时，平均命中率为 85%，含有16 个表项时，平均命中率为97%，因此在配备联想寄存器的页式管理系统中，多一级地址变换不会明显减慢程序的执行速度。,77,2.5.4 空闲内存页的管理,在页式管理系统中，需要一张表记录主存中每个页的使用情况和当前空闲页的总数。由于主存页总数很多，且页的大小相等，故可用位图描述各页的状态。在位图中用一个二进制位对应于主存中的一个页，该位为0表示对应页空闲，为1表示对应页已分配。位图中每一个字节可表示8页的状态，如设页面大小为4KB，对于32MB的主存空间，只需要1KB大小的位表,78,位图,页框号字节号8位号字节号页框号/8；位号页框号8,79,在分配空闲页时，可一次取出位图中的一个字，如该字内容非全 1，即表示其中必对应有空闲页，接下来就可确定空闲页的位置。为了提高在位图上检索空闲页的速度，可在表头增设一个起始查找位置指针，位图中在起始查找指针之前的所有字（或字节）都不含有空闲位。另外，设置一个循环查找指针的算法也不错。释放算法很简单，只要在位图中的对应位上置0即可，但如设置起始查找指针，则可能要修改指针值。也可使用顺序或链接结构的栈来管理空闲页，栈中每一个单元指示一个空闲页。采用这种方法所需的存储空间比位图大许多，但分配空闲页时速度快很多。,80,分页式存储管理的特点,（1）内存事先被划分成相等尺寸的页框，它是进行存储分配的单位；（2）用户作业的相对地址空间按照页框的尺寸划分成页。（3）由于相对地址空间中的页可以进入内存中的任何一个空闲页框，并且分页式存储管理实行的是动态重定位，因此它打破了一个作业必须占据连续存储空间的限制，作业在不连续的存储区里，也能够得到正确的运行。,81,（1）平均每个作业要浪费半页大小的存储页。（2）作业虽然可以不占据连续的存储区，但是每次仍然要求一次全部进入内存。因此，如果作业很大，其存储需求大于内存，那么仍然存在小内存不能运行大作业的问题。,缺点,82,（补充）两级和多级页表,现代的大多数计算机系统，都支持非常大的逻辑地址空间(232264)。在这样的环境下，页表就变得非常大，要占用相当大的内存空间。例如，对于一个具有32位逻辑地址空间的分页系统，规定页面大小为4 KB即212 B，则在每个进程页表中的页表项可达1兆个之多。又因为每个页表项占用一个字节，故每个进程仅仅其页表就要占用1MB的内存空间，而且还要求是连续的。,83,（补充）两级和多级页表,可以采用这样两个方法来解决这一问题：采用离散分配方式来解决难以找到一块连续的大内存空间的问题：只将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入。,84,1.两级页表(Two-Level Page Table),对于要求连续的内存空间来存放页表的问题，可利用将页表进行分页，并离散的将各个页面分别存放在不同的物理块中的办法来加以解决，同样也要为离散分配的页表再建立一张页表，称为外层页表（Outer Page Table），在每个页表项中记录了页表页面的物理块号。,85,逻辑地址结构可描述如下：,86,两级页表结构,87,88,上述对页表施行离散分配的方法，虽然解决了对大页表无需大片存储空间的问题，但并未解决用较少的内存空间去存放大页表的问题。换言之，只用离散分配空间的办法并未减少页表所占用的内存空间。解决方法是把当前需要的一批页表项调入内存，以后再根据需要陆续调入。在采用两级页表结构的情况下，对于正在运行的进程，必须将其外层页表调入内存，而对页表则只需调入一页或几页。,89,2.多级页表 对于32位的机器，采用两级页表结构是合适的；但对于64位的机器，如果页面大小仍采用4 KB即212 B，那么还剩下52位，假定仍按物理块的大小(212位)来划分页表，则将余下的42位用于外层页号。此时在外层页表中可能有4096 G个页表项，要占用16384 GB的连续内存空间。必须采用多级页表，将外层页表再进行分页，也是将各分页离散地装入到不相邻接的物理块中，再利用第2级的外层页表来映射它们之间的关系。对于64位的计算机，如果要求它能支持2(=1844744 TB)规模的物理存储空间，则即使是采用三级页表结构也是难以办到的；而在当前的实际应用中也无此必要。,90,2.6 请求分页系统,虚拟存储器的引入,1.常规存储器管理方式的特征,一次性。作业在运行前一次性的全部装入内存。(2)驻留性。作业装入内存后，便一直驻留在内存中，直到作业运行结束。,91,2.6.1 请求分页的基本原理,其基本思想是对于每一个运行作业，只装入当前运行需要的一部分页面集合，该集合又称“工作集”。当作业运行时需要访问其他不在主存中的虚页时，硬件产生“缺页中断”，如主存资源紧张，可在原先装入主存的页面中选择一个或多个页，将其换出到辅存中，再把所需的页调入主存。请求式分页系统将主存和辅存这两级存储器融合成逻辑上统一的整体，故在这种系统中能运行比可用主存更大的作业或在相同容量的主存中并发运行更多的作业,92,与分页式存储管理的比较,相同点：(1)内存分成页框；(2)作业虚地址空间分虚页；(3)任一页可装入任一空闲页框；不同点：(1)作业全部进入外存，运行时，并不把整个作业全部装入，而是只装入目前要用的若干页；(2)运行过程中，虚地址转换为数对（页号，页内位移），根据页号查页表时，如果该页在内存，那么有真实的页框号与之对应，运行就能够进行下去。,93,与分页式存储管理的比较（续）,如果该页不在内存，那么无真实块号与之对应，表明“缺页”，运行无法继续下去，此时，就要根据该页的地址把它从外存调入，以保证程序运行。请求分页式：当程序运行中需要某一页时，再把它从辅存调入内存。,94,请求分页机构,在请求分页系统中控制这种能在主存和辅存间自动交换页面、对用户透明的机构称为虚拟存储系统的请求分页机构，该机构的主要功能如下。执行地址变换操作，将程序虚拟地址转化为物理地址，这部分工作由硬件实施。缺页时自动触发页面中断机构。缺页中断与普通的外设中断不同，一般中断只能在一条完整的指令执行结束后才能得到响应，而缺页中断可以发生在一条指令的执行中间，如果一条指令要访问多个页面（如对于间接访问指令和数据传送指令），还能引起多个缺页中断。缺页中断处理子程序，其中包括页面的调出和调入，这部分工作在软件控制下完成,95,在请求分页系统中，由于作业的虚页可能驻留在主存中，也可能驻留在辅存中。因此在页表中要扩充表项的内容，使之包含辅存地址，以便在发生缺页时请求分页机构可以将辅存中的虚页调入主存。这样，每一个页表项结构为：虚页号、内存页架号、辅存地址和状态。其中状态字段含有该页当前是在主存还是在辅存的标志。此外，在该字段中还可包括访问位和修改位等,地址变换,96,页表机制,（1）状态位P：用于指示该页是否已调入内存。（2）访问字段A：用于记录本页再一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，供选择换出页面时参考。（3）修改位M：表示该页在调入内存后是否被修改过。（4）外存地址：用于指出该页在外存的地址。,97,缺页中断机构,在地址映射过程中，在页表中发现所要访问的页不在内存，则产生缺页中断。操作系统接到此中断信号后，就调出缺页中断处理程序，根据页表中给出的外存地址，将该页调入内存，使作业继续运行下去。如果内存中有空闲页框，则分配一页，将新调入页装入内存，并修改页表中相应页表项目的驻留位及相应的内存页框号。若此时内存中没有空闲页框，则要淘汰某页，若该页在内存期间被修改过，则要将其写回外存。,98,CPU,页表始址 长度,页表控制寄存器,内存,越界中断,页表,快表,物理地址,缺页异常,地址变换机构,99,开始,页号页表长度,检索快表,？命中,访问页表,页在内存？,修改快表,修改访问位和修改位,形成物理地址,地址变换结束,地址越界,保留CPU现场,？内存满,选择一页换出,OS命令CPU从外存读缺页,启动I/O硬件,缺页中断处理,是,是,是,是,否,否,否,否,该页是否修改过？,从外存找到缺页,将该页写回外存,将一页从外存换入内存,修改页表,100,2.6.2 页面淘汰,页面淘汰问题（页面置换）：要从辅存上把需要的页面调入内存，但内存中已没有空闲页框可供分配使用，那么就必须从内存中选择一页，然后把它调出内存，以便为即将调入的页面让出块空间。页面置换是由缺页中断引起的，但是缺页中断不一定都引起页面置换。,101,页淘汰,在内存中选中了一个淘汰的页面，如果该页面在内存时未被修改过，那么就可以直接用调入的页面将其覆盖掉；如果该页面在内存时被修改过，那么就必须把它写回到磁盘。以便更新该页在辅存上的副本。一个页面的内容在内存时是否被修改过，这样的信息可以通过页表表目反映出来。,102,“抖动”或“颠簸”现象,抖动进程块频繁的换入换出 当操作系统取进一页时，它必须扔出一页。如果一块正好在将要被用到之前扔出，操作系统又不得不几乎立即把它取回来，太多的这类操作会导致“系统抖动”，处理器的大多数时间都用于交换页，而不是执行指令。改进抖动的许多复杂但有效的算法，从本质上看是，操作系统试图根据最近的历史来猜测在不远的将来最可能用到的页。,103,页面淘汰算法,功能：需要调入页面时，选择内存中哪个物理页面被置换。目标：把未来不再使用的或短期内较少使用的页面调出，通常只能在局部性原理指导下依据过去的统计数据进行预测。,104,页面走向,一个程序执行过程中页面的变化序列称为“页面走向”。,105,缺页中断率,假定一个作业运行的页面走向中涉及到的页面总数为A，其中有F次缺页，必须通过缺页中断把它们调入内存。我们定义：fF/A 称f为“缺页中断率”,106,1.最佳(Optimal)置换算法 最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。,107,假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1 进程运行时，先将7，0，1三个页面装入内存。以后，当进程要访问页面2时，将会产生缺页中断。此时OS根据最佳置换算法，将选择页面7予以淘汰。,108,2.先进先出(FIFO)页面置换算法,选择建立最早的页面被置换。可以通过链表来表示各页的建立时间先后。性能较差。较早调入的页往往是经常被访问的页，这些页在FIF