操作系统(Windows与Linux)5——存储管理PPT学习课件

,1,第5章存储管理,存储管理是对主存（又称内存）的管理。内存：处理机可以直接存取指令和数据的存储器，是进程得以运行的重要物质基础，是计算机中的一种宝贵而紧俏的资源。近年，随着硬件技术和生产水平的迅速发展，内存的成本迅速下降，容量一直不断扩大，仍不能满足各种软件对存储空间急剧增长的需求。对内存的有效管理和有效使用，是现代操作系统十分重要的问题。,2,第5章存储管理,本章要点：5.1存储管理的基本概念5.2连续分配方式5.3离散分配方式5.4虚拟存储器5.5案例：Linux存储管理5.6例题分析5.7本章小结,3,5.1存储管理的基本概念,知识点：5.1.1存储管理的功能5.1.2存储器管理方式5.1.3地址重定位,返回,4,5.1.1存储管理的功能,内存资源不足：单道程序阶段，已经意识到存储资源不足，开始研究如何从逻辑上扩充内存空间。多道程序出现后，这个问题更为突出，且提出如何使每道程序都能在不受干扰的环境中运行，并能尽量提高存储器的利用率。为对主存进行有效的管理，存储管理应具有以下功能：内存的分配和回收：为每道程序分配内存空间，由操作系统完成主存储器空间的分配和管理，使程序员摆脱程序设计的麻烦，提高编程效率；回收系统或用户释放的存储区。提高存储器的利用率：分配内存空间时，尽量减少不可用的存储空间（“零头”），允许正在运行程序申请附加内存空间，使多道程序能动态地共享主存。,5,地址映射：把进程地址空间中使用的逻辑地址变换成存储空间中的物理地址的过程。目标程序限定的地址范围称该程序的地址空间，是程序访问信息时用到的一系列地址单元的集合，地址空间中的地址是逻辑地址。内存空间是内存中物理地址的集合。两者不一致。地址映射一般需要硬件或软件的配合。存储保护：确保进入主存的每道程序都在自己的内存空间运行，互不干扰。既要防止一道程序由于错误破坏其他程序，也要防止破坏系统程序。保护一般由硬件和软件配合完成。扩充主存容量：借助虚拟存储技术或其他自动覆盖技术，为用户提供比主存空间大的地址空间，实现扩充主存容量的目的。“提高存储器的利用率”和“更好地满足用户需求”，是存储管理方式不断发展的推动力。,返回,5.1.1存储管理的功能,6,5.1.2存储器管理方式,一般有以下几种分配方式：1.连续分配方式为一个系统或用户程序分配一个连续的空间。有以下两种方式：单一连续分配方式单道程序的一种存储管理方式，内存中仅驻留一道程序，整个用户区为一个用户独占。不适用于多道程序。分区分配方式可用于多道程序设计的较简单的存储管理方式。把内存划分为若干分区，操作系统占用一个分区，其余每个分区容纳一个进程。分区分配方式可以进一步分为两种：固定分区分配：将内存用户区划分为若干个固定大小的区域，每个区域中驻留一道程序；动态分区分配：根据用户程序大小，动态地对内存进行划分，各分区大小不定，内存划分为多个分区，数目可变。,7,2.离散分配方式为减少连续分配产生的碎片，提高存储器的利用率，引入离散分配方式。可将一个用户程序离散地分配到内存中多个不相邻接的区域中。,5.1.2存储器管理方式,8,离散分配方式有三种：分页存储管理：用户程序的地址空间划分成若干个固定大小的称为“页”的区域，相应将内存空间分成若干个物理块，页和块大小相等。可将用户程序的任一页放入内存的任一块中，实现离散分配，且内存中的碎片大小不会超过一页。分段存储管理：用户程序的地址空间分成若干个大小不等的段，每段可以定义一组相对完整的逻辑信息。存储分配时，以段为单位，这些段在内存中可以不相邻。段页式存储管理：分页和分段两种存储管理方式结合的产物，发挥两者优点，既提高存储器利用率，又能满足用户要求。,返回,5.1.2存储器管理方式,9,5.1.3地址重定位,1.重定位及相关概念用汇编语言或高级语言编写程序时，通过符号名访问某单元。程序中由符号名组成的空间称为名空间。一个应用程序编译后，形成若干个目标程序，目标程序再经过链接形成可装入程序，即转换为相对地址编址形式。这些程序中地址都是以“0”为基址顺序编址。由这些地址形成的地址范围称为地址空间，其中的地址称为逻辑地址或相对地址。存储空间是主存中一系列存储信息的物理单元的集合，其中的地址称为物理地址或绝对地址。即地址空间是逻辑地址的集合；存储空间是物理地址的集合。一个是虚的概念，一个是实的物体。一个编译好的程序保存在自己的地址空间中，需要在计算机上运行时才装入存储空间。,10,一个程序在装入时分配到的存储空间与其地址空间不一致。程序运行时要访问的指令、数据的实际地址和地址空间中的地址不同。若在程序装入或运行时不对有关地址部分加以修改，将导致错误的结果。把一个相对地址空间的程序装入到物理地址空间时，由于两个空间不一致而需要进行的地址变换，称地址重定位或地址映射。地址变换过程，把程序地址空间中使用的逻辑地址变换为存储空间中的物理地址的过程。,5.1.3地址重定位,11,根据地址变换持续的时间及采用技术的不同，可以把重定位分为静态重定位和动态重定位两类。静态重定位程序运行前，由链接装入程序进行重定位。即：在程序装入主存同时，将程序中逻辑地址转换为物理地址。特点：无需增加硬件地址变换机构。要求为每个程序分配一个连续的存储区；程序执行期间不移动，难以做到程序和数据的共享。,5.1.3地址重定位,12,静态重定位的实现：操作系统为程序分配一个以某地址为起始地址的连续内存区域，重定位时，将程序中指令或操作数的逻辑地址加上该起始地址，即可得到物理地址。例：图5-1，程序装到从1000开始的内存区域中，物理地址为逻辑地址值加上1000。,图5-1静态重定位程序装入示例,5.1.3地址重定位,13,动态重定位程序执行过程中，每当访问指令或数据，将被访问程序或数据的逻辑地址转换为物理地址。重定位过程在程序执行期间随指令执行逐步完成。一种允许程序在执行过程中在内存中移动的技术，必须获得硬件地址变换机构的支持，在系统中增加一个重定位寄存器，用来装入程序在内存中的起始地址。程序执行时，真正访问内存的地址是有效地址与重定位寄存器中的地址相加形成。,5.1.3地址重定位,14,动态重定位的原理：图5-2。特点：可以将程序分配到不连续的存储区中；程序运行前，可以只装入部分代码即投入运行；程序运行期间，根据需要动态申请分配内存；为便于程序段共享，可提供一个比主存空间大得多的地址空间。动态重定位需要附加的硬件支持，实现存储管理的软件算法比较复杂。,5.1.3地址重定位,15,图5-2动态重定位示意图,返回,5.1.3地址重定位,16,关系,地址重定位的方式+存储管理方式：内存分配方式是紧密相关的。,17,5.2连续分配方式,知识点：5.2.1单一连续分配5.2.2分区存储管理5.2.3覆盖与交换,返回,18,5.2.1单一连续分配,应用环境：单一连续分配是最简单的一种存储管理方式，只能用于单用户、单任务的操作系统。使用方法：将内存分为两个存储区，一个存储区仅供操作系统使用（系统区），其余全部内存空间供用户使用（用户区）。主要采用静态分配方式，进程一旦进入内存，直到执行结束后才释放内存。主要特点：管理简单，只需很少软件和硬件支持，便于用户了解和使用。优缺点：单用户采用，内存只装入一道进程运行，各类资源利用率不高。,19,图5-3单一连续分配,返回,5.2.1单一连续分配,20,5.2.2分区存储管理,分区存储管理是满足多道程序设计的一种最简单的存储管理方法，把内存划分为若干分区，操作系统占用一个分区外，其余每个分区容纳一个进程。1.固定分区分配特点：内存空间划分为若干个固定大小的区域，每个区域边界不能改变。主要划分方式：各分区大小相等和分区的大小不等。每个区域中驻留一道程序。,21,表5-1分区说明表,5.2.2分区存储管理,22,5.2.2分区存储管理,使用方式：根据各分区大小排队，建立一张分区说明表（表5-1），记录分区数目及每个分区的起始地址、大小及状态（是否已分配）。用户程序装入时，内存分配程序检索该表，找出一个能满足要求、尚未分配的分区分配，修改分区说明表中该分区表项的状态；若找不到大小足够的分区，拒绝为分配内存。,23,优缺点：进程的大小不一定与某个分区大小相等，绝大多数已分配的分区中都有一部分存储空间被浪费。固定分区分配管理方法主存不能得到充分利用。,图5-4固定分区分配,5.2.2分区存储管理,24,5.2.2分区存储管理,25,2.动态分区分配（可变分区分配）根据进程大小动态划分分区，使分区的大小正好适应进程需要。各分区大小不定，内存中分区数目不定。进程进入系统前，根据进程大小申请所需存储容量，由系统实施分配。为了管理主存分区的分配情况，建立两张表，除分区说明表外，还有内存空闲分区表，登记内存中空闲分区的位置、大小等信息。有进程申请内存分区时，按一定分配算法从空闲分区表（或空闲分区链）中选出一个大于等于该进程所需容量的分区分配。若该分区大于进程所需容量，剩余的较小空白区仍留在空闲分区表中，并对空闲分区表进行相应修改。一个进程完成后，所占用的分区释放，变成空白区，并与邻接的空白区合并。,5.2.2分区存储管理,26,2.动态分区分配例子：,5.2.2分区存储管理,27,2.动态分区分配特点：可变式分区的存储管理方式由两个特点：第一个特点是分区个数是可变的，且分区大小也不是固定的；第二个特点是内存中分布着个数和大小都是变化的自由分区和碎片，这些自由分区有些可能相当大，有些则相当小。,5.2.2分区存储管理,28,2.动态分区分配可变式分区存储管理所用的基本数据结构：为实现可变分区的管理，可以采用两张表格记录内存分区的情况，其中一张表格记录已分配区的信息，另一张表格记录空闲分区的信息，如图所示。表格中状态为“空表目”表示表示该表目中没有登记分区的信息，当需要表目来登记分区信息时，可使用状态为“空表目”的表目。可变分区的分区管理也广泛采用空闲区链的方法。即把每个分区的起始若干各自接分为两部分：前一部分作为链指针，指向下一空闲区的起始地址；后一部分指出本空闲区的大小。系统中用一固定单元作为链的头指针，指向第一空闲区的起始地址。最后一个空闲区的链指针中存放链尾标志（如0）。这样使用链指针把所有空闲分区链接在一起，构成一条空闲区链，如图所示。,5.2.2分区存储管理,29,2.动态分区分配可变式分区存储管理所用的基本数据结构：,5.2.2分区存储管理,分区表,空闲块链,30,常用分配算法（四种）：首次适应算法要求：空闲分区按地址递增的次序排列。内存分配时，从空闲分区表（或空闲分区链）首开始顺序查找，直到找到第一个能满足大小要求的空闲分区为止。根据进程大小从该分区划出一块内存空间分配，余下空闲分区仍留在空闲分区表（或空闲分区链）中。特点：优先利用内存低地址部分的空闲分区，保留高地址部分的大空闲区。低地址部分不断被划分，低地址端留下许多难以利用的很小的空闲分区；每次查找从低地址部分开始，增加了查找可用空闲分区的开销。,5.2.2分区存储管理,31,循环首次适应算法由首次适应算法演变来。分配内存空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到第一个能满足大小要求的空闲分区为止。根据进程大小从该分区中划出一块内存空间分配，余下空闲分区仍留在空闲分区表（或空闲分区链）中。特点：存储空间的利用更均衡，不致使小的空闲区集中在存储区的一端，但导致缺乏大的空闲分区。,5.2.2分区存储管理,32,最佳适应算法“最佳”指每次分配内存时总是把既满足要求，又是最小的空闲区分配给进程，避免了“大材小用”。为了快速查找到合适的空闲区，要求所有空闲区按大小递增的顺序排列。查找时，从空闲分区表首开始查找，找到的第一个能满足大小要求的空闲分区。若找到的空闲分区大于进程的大小，切割剩余空闲区仍留在空闲分区表中。特点：若存在与进程大小一致的空闲分区，必然被选中；若不存在与进程大小一致的空闲分区，只划分比进程稍大的空闲分区，保留大的空闲区。空闲区一般不可能正好和进程申请的内存空间大小一样，分割成两部分时，使剩下的空闲区非常小，在存储器中留下许多难以利用的小空闲区。,5.2.2分区存储管理,33,最坏适应算法要求：空闲分区按大小递减次序排列。内存分配时，先检查空闲分区表（或空闲分区链）中第一个空闲分区，若第一个空闲分区小于要求的大小，分配失败；否则从该空闲分区中划出进程大小的一块内存空间分配，余下空闲分区仍留在空闲分区表（或空闲分区链）中。特点：总是挑选满足要求的最大的分区分配，剩下的空闲区比较大，也能装下其他进程。由于最大的空闲区总是首先被分配而划分，大进程到来时，存储空间的申请往往得不到满足。,5.2.2分区存储管理,34,可变式分区分配算法：,5.2.2分区存储管理,35,可变式分区释放算法：,5.2.2分区存储管理,36,可变式分区中的存储保护与重定位：保护：界地址法重定位：动态重定位,5.2.2分区存储管理,37,可变式分区中的存储保护与重定位：可变分区的存储保护可使用“界地址法”，也可以使用一对基址、限长寄存器，其道理也与使用一对上、下界地址寄存器的道理相同，但基址寄存器还可以起到定位寄存器的作用。可变分区采用动态重定位的方式实现重定位，这样即使移动内存中的作业使得其基地址发生变化，作业的执行也不会受到影响。图中给出了存储保护和地址重定位的关系。,5.2.2分区存储管理,38,可变分区方式的优缺点：优点：由于采用了拼接和移动技术，内存中不再有不能使用的碎片，从而能有效地利用主存空间，提高多道程序系统的多道程度，从而也提高了对处理机和外设的利用率。缺点：作业大小依然受内存容量的限制；对碎片问题的解决需要以增加系统开销为代价；由于作业需要连续存放，使得内存的共享问题不好解决。,5.2.2分区存储管理,39,动态分区分配需要解决的问题有三个：（1）分区分配中所用的数据结构。（2）分区的分配算法。（3）分区的分配与回收操作。,5.2.2分区存储管理,40,动态分区分配需要解决的问题有三个：回收操作：回收分区的主要工作是：首先检查是否有临接的空闲区，如有则合并，使之成为一个连续的空闲区，而不是许多零散的小的部分；之后，修改有关的分区描述信息。一个回收分区邻接空闲区的情况有四种：如图4.13所示。第一种情况是回收分区r上邻的一个空闲区，此时应合并成为一个连续的空闲区，其始址为r上邻的空闲区始址，而大小为二者之和。第二种情况与r下面的空闲区相邻。直接合并。第三种情况是与上下空闲区相邻。将三个区域合并成一个连续的空闲区。第四种情况不和任何空闲区相邻，应建立一个新的空闲区，并加到自由主存队列中。,5.2.2分区存储管理,41,动态分区分配需要解决的问题有三个：回收操作：,5.2.2分区存储管理,42,3.碎片问题与拼接技术分区存储管理实现了多道程序设计，同时也产生了一个非常严重的问题即碎片问题。碎片：内存中无法被利用的小的空闲区。分区存储管理方式下，系统运行一段时间后，内存中碎片占据相当数量的空间，甚至当一个进程申请一定数量的主存时，虽然空闲区总和大于进程申请的容量，但没有单个空闲区可以装下该进程。解决办法之一：采用拼接（紧缩、紧凑）技术。拼接：移动存储器中所有已分配区到主存的一端，使分散的空闲区连成一个大的空闲区。,5.2.2分区存储管理,43,3.碎片问题与拼接技术：,5.2.2分区存储管理,44,拼接技术有一个拼接的时机问题，有两种解决方案。方案一：某个分区回收时立即进行拼接，使主存中总是只有一个连续的空闲区。拼接费时间，频率过高使系统开销加大。方案二：找不到足够大的空闲区且空闲区的存储容量可以满足进程要求时拼接。拼接频率相对较小，空闲区的管理稍为复杂些。,返回,5.2.2分区存储管理,45,5.2.3覆盖与交换,扩充内存的方法：覆盖与交换技术是在多道程序环境下扩充内存的两种方法。应用覆盖技术主要用在早期操作系统；交换技术在现代操作系统仍使用；,46,5.2.3覆盖与交换,1覆盖技术覆盖：程序中若干程序段或数据段按时间先后使用内存某个区域。实现方法：将程序必要部分的代码和数据常驻内存，可选覆盖部分平时存放在外存(覆盖段)，需要时才装入内存。不存在调用关系的模块不必同时装入到内存，从而可以相互覆盖。每个覆盖段是一个相对独立的程序段，执行时不要求同时装入内存的一系列覆盖段组成一组（覆盖段组），将一个覆盖段组分配到同一个存储区域，覆盖段按照时间先后使用该存储区域。作用：覆盖(Overlay)技术可以在较小的可用内存中运行较大的程序。,47,图5-5覆盖段组示意图,5.2.3覆盖与交换,A-20k,B-50k,F-30k,C-30k,D-20k,E-40k,D-20k,E-40k,B-50k,F-30k,48,例：某进程的程序由A，B，C，D，E，F等6个程序段组成。调用关系：图5-5。程序段A只调用程序段B和C，程序段B只调用程序段F，程序段C只调用D和E。即B不会调用C，C也不会调用B。解决方法：程序段A常驻内存，程序段B和程序段C无需同时在内存中。按图分配程序段的调入。进程正文段所需要内存空间：A(20K)+B(50K)+F(30K)+C(30K)+D(20K)+E(40K)190K采用覆盖技术后，只需要100K内存空间即可。,5.2.3覆盖与交换,49,优缺点：要求用户清楚地了解程序结构，指定各程序段调入内存的先后次序，以及内存中可以覆盖掉的程序段位置等，必须在编程时划分程序模块，确定模块之间覆盖关系，增加了编程复杂度；需要从外存装入覆盖文件，以时间延长换取空间节省。应用：早期采用的简单的扩充主存的技术，用户负担重，程序段最大长度内存容量限制。覆盖技术目前已不再普遍使用。,5.2.3覆盖与交换,50,2交换技术含义：多个进程并发执行时，将暂时不能执行的进程送到外存中，获得空闲内存空间装入新的进程，或读入保存在外存中需要执行的进程。交换又称“对换”。特点：交换单位为整个进程的地址空间。应用：常用于多道程序系统或小型分时系统，与分区式存储管理配合使用。,返回,5.2.3覆盖与交换,51,2交换技术优点：可以增加并发运行进程的数目，给用户提供适当的响应时间。缺点：交换技术存在不足，如控制换入和换出增加处理机开销，进程整个地址空间都进行对换。比较：与覆盖技术相比，不要求程序员给出程序段之间的覆盖结构，不影响程序结构。交换技术主要在进程间进行，覆盖技术主要在同进程内进行。改进：传统交换技术的交换单位为整个进程。如果交换单位为进程的一部分，内存利用率将进一步提升。,返回,5.2.3覆盖与交换,52,分区分配方式会形成许多“碎片”，尽管通过拼接技术可以解决碎片问题，但花费代价很高。离散分配方式允许将一个进程直接分散地分配到许多不相邻的分区中，不必再进行拼接。,5.3离散分配方式,返回,53,知识点：页式存储管理段式存储管理段页式存储管理,5.3离散分配方式,返回,54,页式系统应解决的问题：采用“紧凑”技术解决按区分配中存在的碎片问题，是以花费CPU时间为代价换来的。为了寻找解决碎片问题的新途径，人们很容易想到让程序不连续存放，例如，有一个作业要求投入运行，其程序的地址空间是3KB,而主存当前只有两个各为1KB和2KB的空闲区。显然各空闲区的大小比该程序的地址空间小，而总和却相同。这样就考虑将程序分开存放。放在不相邻的两个区域中。这正是分页的思想。在分页存储管理中，主存被分成一系列的块，程序的地址空间被分成一系列的页面。然后将页面存放在主存块中。为了便于实现动态地址变，一般主存的块和页面大小相等并为2的幂次。,5.3.1页式存储管理,55,1.页式存储管理的实现思想：用户进程的地址空间划分成若干个大小相等的区域，称为页或页面。相应将主存存储空间分成与页大小相等的区域，称块或物理块或页框。页的大小与块的大小完全相同。为进程分配存储空间时，以块为单位分配，可以将进程的任意一页放到主存任意一个块中。调度进程运行时，必须将进程所有页面一次调入主存，若主存没有足够的物理块，进程等待。例如：一个作业若有n个页，那么就为它分配n个块，每页装入一块。通常作业的最后一页不满，但是也分配一块。分页式管理分配给作业的块不要求是相互邻接的，即块间的地址可以是不连续的，但是块内地址连续，块的大小固定。,5.3.1页式存储管理,56,页式存储管理内存分配示例：,5.3.1页式存储管理,57,页表：,5.3.1页式存储管理,用户程序,0页,1页,2页,3页,4页,5页,n页,内存,0块,1块,2块,3块,4块,5块,6块,7块,8块,9块,10块,2块,3块,6块,8块,9块,58,页表：,5.3.1页式存储管理,用户程序,0页,1页,2页,3页,4页,5页,n页,内存,0块,1块,2块,3块,4块,5块,6块,7块,8块,9块,10块,2块,3块,6块,8块,9块,2页,3页,6页,8页,9页,块号,0页,1页,2页,3页,4页,5页,n页,页号,页表,对应项,59,在分页系统中，允许进程的每一页离散地存储在内存的任一物理块中，但系统应能保证进程的正确运行。即能在内存中找到每个页面所对应的物理块。为此系统又为每个进程建立一张页面映象表，简称页表。在进程地址空间的所有页内（0n），依次在页表中有一页表项，其中记录了相应页在内存中对应的物理块。见图的中间部分。页表的作用：实现了从页号到物理块号的地址映象。即使在简单的分页系统中，也常在页表的表项中设置一存取控制字。用于对存储块中内容进行保护。,5.3.1页式存储管理,60,目的：为便于在内存中找到进程每个页对应的物理块，系统为每个进程建立一张页面映象表，简称页表。位置：页表一般放在内存中。表项：进程地址空间内每一页与页表中一个表项对应，记录相应页在内存中对应的物理块号（图5-6）。,5.3.1页式存储管理,61,作业的逻辑地址空间一般是一个从零开始的一维线性地址空间，但是通常块和页的大小是2的幂，如1K、2K、4K字节等，所以作业的逻辑地址可以解释为由两部分组成：页号页内偏移例如：学号：目的是反过来用身份证号：目的是反过来用,5.3.1页式存储管理,62,页内偏移范围与内存块的大小有关，页号的范围还取决于逻辑地址的位数。例如：若地址寄存器的长度为16位，块的大小为1K字节，则页内偏移变化范围为01023（即11024-1）字节，这需要10位来进行描述，剩下的6位就是用来描述页号，其范围是063（即26-1），地址结构如下：151090页号P页内偏移W,5.3.1页式存储管理,63,对逻辑地址的解释与理解：如何利用页表进行地址变换，找到子令或数据的物理地址，这和计算机所采用的地址结构有关。而地址结构又与所选择的页面尺寸有关。比如，当CPU给出的虚地址长度为32位，页面的大小为4kb时，在分区系统中的地址格式如图所示：页号页内偏移量：,5.3.1页式存储管理,4kb=22210=212,页内偏移量占12位,0,11,12,31,页号占20位,32-12=20,64,小结：目的：为便于在内存中找到进程每个页对应的物理块，系统为每个进程建立一张页面映象表，简称页表。进程地址空间内每一页与页表中一个表项对应，记录相应页在内存中对应的物理块号（图5-6）。位置：页表一般放在内存中。逻辑地址包含两部分：页号P，页内位移W。两部分构成的地址长度为16位。其中，09位页内地址（每页1K）；1015位页号，地址空间最多允许64项。作业的逻辑地址到物理地址的变换是通过页表来实现的，即动态地址重定位是通过页表来实现的。,页式存储管理系统中的逻辑地址结构如下：,5.3.1页式存储管理,65,图5-6页表的作用,5.3.1页式存储管理,66,含义：页号：指定在页表中的位置，页号为几即在页表中的第几个页表项（加1）。即：用页号索引页表，可以得到这一页在内存中的物理块号。页内偏移量：在页内的位置，因为页与块是一样大，因此也代表在块内的位置，即：页内的相对位置与块内的相对位置是相同的。,页式存储管理系统中的逻辑地址结构如下：,5.3.1页式存储管理,67,5.3.1页式存储管理,页式系统地址变换结构,2148,7620,10242+100=2048+100=2148,10247+452=7168+452=7620,2500=2048+452,0100=0000+100,68,5.3.1页式存储管理,假设页面大小为1kb，机器的地址长度为16位。下面以图所示作业2程序中的一条指令的执行过程，来说明页式系统中的地址变换过程。程序的地址空间中第100号单元处有一条指令为“movr1,2500”。这条指令在主存中的实际位置为2148号单元（第2块452号单元），而这条指令要取的数123在程序的地址空间中位于2500号单元（第2页的452号单元）处。它在主存中存于7620号单元（第7块452号单元）。,69,5.3.1页式存储管理,当作业2的相应进程在CPU上运行时，操作系统负责把该作业的页表在主存中的起始地址（a）送到页表起始地址寄存器中。以便在进程运行中进行地址变换时由它控制找到该作业的页表。当作业2的程序执行到指令“movr1,2500”时，CPU给出的操作数地址为2500，首先由分页机构自动把它分成两部分，得到页号p=2,页内相对位移w=452。然后，根据页表始址寄存器指示的页表始地址，以页号为索引，找到第2页所对应的块号7。然后，将块号7和页内位移量w拼接在一起，就形成了访问主存的物理地址7620。这正是所取数123所在主存的实际位置。,70,5.3.1页式存储管理,8,71,5.3.1页式存储管理,页表是每个作业一张，正在运行的作业的页表的起始地址和页表长度要装入页表控制寄存器。上面的地址变换是借助硬件的地址变换结构来实现的。地址变换关系如下：页表起始地址=（页表控制寄存器）页表中页号为P的表目地址=（页表控制寄存器）+页表表目长度P，由此获得对应的内存块号P。物理地址=P块长+页内偏移W由图上例子可见，虽然作业被存放在若干个不连续的块中，但在作业执行中总是能按确切的地址进行存取。,72,2.地址变换过程：进程访问某个逻辑地址中的数据时，分页地址变换机构自动将逻辑地址分为页号和页内位移两部分，再以页号为索引检索页表。检索前，先将页号与页表长度比较，若页号超过页表长度，表示本次访问的地址已超越进程的地址空间，系统产生地址越界中断。若页访问合法，由页表起始地址和页号计算相应页表项位置，得到该页物理块号。将块号与逻辑地址中的页内位移拼接，形成访问主存的物理地址。图5-7：页式存储管理系统中的地址变换过程。假定页面大小1K字节，逻辑地址1148=（11024+124）页号为1，页内地址为124。由页表知，第1页对应物理块号为3。将块号3与页内地址124拼接（31024+124=3196），得到物理地址3196。,5.3.1页式存储管理,73,图5-7页式存储管理系统的地址变换过程,5.3.1页式存储管理,74,3.联想存储器：页表存放在内存中。由地址变换过程可知，若页表全部放在主存，存取一个数据或一条指令至少访问两次主存。第一次访问页表，确定物理地址；第二次根据地址存取数据或指令。这种方法比通常执行指令速度慢一倍。为提高查表速度，可在地址变换机构中增设一个具有并行查找能力的高速缓冲存储器（联想存储器或快表），页表放在这个高速缓冲存储器中。高速缓冲存储器一般是半导体存储器，工作周期与CPU大致相同，造价较高。为降低成本，在快表中存放正在运行进程当前访问的页表项，页表其余部分存放在内存中。,5.3.1页式存储管理,75,5.3.1页式存储管理,快表：由于需要利用页表进行地址变换，而页表存放在内存，所以在按给定的逻辑地址进行一次读/写时，必须两次访问内存，即第一次访问内存中的页表，第二次读/写相应的内存单元，这使得存取速度下降。为了提高存取速度，改进的办法是采用比内存速度快得多的高速存储器来存放常用页的页表，这个快速页表称为快表。高速存储器是比内存存取速度快得多，但是价格也更高的存储器，故一般是小容量的。快表是页表的一部分存放在高速存储器中的一个副本。有一些系统将部分页表放在快速存储器中，其余部仍放在主存中。存放页表部分内容的快速存储器称相联存储器，也称为联想存储器。联想存储器中存放的部分页表称为“快表”。它的格式如下图所示。这样的联想存储器一般由8个16个单元组成。它们用来存放正在运行进程的当前最常用的页号和它相应的块号，并具有进行查找的能力和通常的执行过程一样，只要访问一次主存，就可以取出指令或存取数据。如果所需要查的页号和联想存储器中所有的页号不匹配，则地址变换过程还得通过主存中的页表进行。采用联想存储器和主存中页表相结合的分页地址变换过程如图所示。,76,5.3.1页式存储管理,77,5.3.1页式存储管理,78,5.3.1页式存储管理,引入快表后的地址变换过程：CPU给出逻辑地址后，地址变换机构自动将页号与联想存储器中所有页号并行比较，有匹配页号，表示要访问的页表项在联想存储器中，取出该页对应块号与页内地址拼接形成物理地址。若联想存储器中所有页号与查找页号不匹配，还需访问主存中的页表。查找同时进行，一旦在联想存储器中发现要查找的页号，立即停止内存中页表查找。若地址变换在查找内存中页表完成，应将这次查到的页表项存入联想存储器；若联想存储器已满，须按某种原则淘汰一个表项以腾出位置。这种方案只要用816个表项的联想存储器，即可从联想存储器中找到所需页号的概率达到90%左右。,79,5.3.1页式存储管理,两级和多级页表：两级页表：针对难以找到大的存储空间以存放页表的问题，可利用页表进行分页的办法，使每个页面的大小与内存物理块的大小相同，并为它们编号。可以离散地将各个页面分别放在不同的物理块中，同样为每个离散的页面建立一张页表，称为外层页表。在每个页表项中记录物理块号。如下图所示。,80,5.3.1页式存储管理,分页地址变换,81,5.3.1页式存储管理,由图可以看出，在页表的每个表项中存放的是进程的某页在内存中的物理块号，如第0#页存放在1号物理块中，1#页存放在4#物理块中。而在外层页表的每个页表项中，所存放的是某页表分页的首址。如0#页表存放在第1011#物理块中。可以利用外层页表和页表这两级页表，来实现从进程的逻辑地址到内存地址的变换。,82,5.3.1页式存储管理,具有两级页表的地址变换机构,83,5.3.1页式存储管理,为了地址变换实现，在地址机构中同样需要设置一个外层页表寄存器，用于存放外层页表的始址。并利用逻辑地址的外层页号，作为外层页表的索引。从中找到指定页表分页的首址。再利用P2作为指定页表分页的索引，找到指定的页表项。其中即含有该页在内存中的物理块号。用该块号和页内地址d即可构成访问内存的物理地址。上图即为两级页表的地址变换机构。,84,5.3.1页式存储管理,多级页表结构：对于32位的机器，采用两级页表的结构是合适的。但对于64位的机器，对于二级页表是否合适，需要简单的分析。如果页面大小仍采用4KB即212B,那么还剩52位，假定仍按物理块的大小（210位）来划分页表，则将所有剩余的42位用于外层页号。此时在外层页表中可能有4096G个页表项，即使按220位来划分页表。此时，每个页表分页将达1MB;外层页表仍有4G个页表项。要占用16GB的连续内存空间。可见，不论怎样划分，其结果都是不能接受的。,85,4.页的共享与保护多道程序系统中，数据共享是重要的。页式管理系统中，实现共享的方法是使共享用户地址空间中的页指向相同的块号。,5.3.1页式存储管理,86,4.页的共享与保护页式管理系统中实现共享比段式管理系统困难。原因：页式系统将进程的地址空间划分成页面对用户透明，同时，进程的地址空间是线性连续的。当系统将进程的地址空间分成大小相同的页面时，被共享的部分不一定被包含在一个完整的页面中。使不应共享的数据也被共享了，不利于保密。各进程的地址空间被划分成页的过程中，共享部分的起始单元在各自页面中的页内地址不同，共享比较困难。,5.3.1页式存储管理,87,5.3.1页式存储管理,页式管理可以为内存提供两种保护方式：地址越界保护：由地址变换机构中页表长度的值和要访问的逻辑地址相比较完成；通过页表中的访问控制信息对内存信息提供保护。例如：在页表中设置一个存取控制字段，根据页面使用情况将该字段定义为读、写、执行等权限。地址变换时，不仅从页表相应表项得到该页对应块号，还检查本次操作与存取控制字段允许的操作是否相符，若不相符，由硬件捕获并发出保护性中断。,88,5.3.1页式存储管理,5.页式存储管理系统的特点：不要求进程的程序和数据段在内存中连续存放，有效地解决碎片问题；要求硬件支持，增加了成本；消除了碎片，但每个进程最后一页内总有部分空间得不到利用。进程的地址空间仍受主存实际容量的限制。,返回,89,从固定分区到可变分区，再到分页系统，主要为了提高内存利用率。各种存储管理方式都是提供线性连续的地址空间，通常，一个程序由多个程序段和数据段组成，编译链接程序按一维线性地址排列，给程序及数据共享带来困难。段式存储管理方式能较好解决，还能实现分段保护和动态链接。,5.3.2段式存储管理,90,5.3.2段式存储管理,段的概念：在分页存储管理中，虽然将用户作业分页，但是提供给用户作业使用的逻辑地址都是一维线性地址。这与物理内存的地址形式是相同的，但与程序的逻辑结构却大不相同。通常，用户在实际问题的处理中，往往出现模块化程序，例如一个程序往往有一个主程序段、若干子程序段、若干数据段和工作区段所组成，它们基本上是以段为单位出现，每个段具有完整的逻辑意义。为了与程序的这种逻辑结构相适应，提出了将程序逻辑地址空间按模块分段组织管理的思想，即分段存储管理。分段存储管理以段为单位来管理内存，能更有效地利用内存，并且便于用户使用。,91,5.3.2段式存储管理,段的概念：在分段存储管理中，每个作业的地址空间都按照作业本身的内在逻辑，划分成若干段，即每个段是一组逻辑上完整的程序或数据。每一个段有一个名字，即段名。段名通常由用户给出。作业程序经编译连接后，段名转换为段号。段号与段号之间无先后顺序关系，例如可把一个作业划分为四个段：主程序段、子程序段、数据段、工作区段。每段是一个首地址为零、连续的线性地址空间，并可根据需要而动态增长。对作业地址空间的访问既要给出段名，还要给出段内地址。,92,5.3.2段式存储管理,段的概念：每个作业的逻辑地址空间是二维的，逻辑地址包含两部分：段号S和段内地址W。举例：CallX|#转向段名为X的子程序入口点Y。Load1，A|6#将段名为A的数组中第6个元素值读到寄存器1中Store1，B|#将寄存器1的值存入段名B段内地址为C的单元中以上指令中的段名X、A、B以及入口名Y、段内地址符号C等经编译程序和连接程序编译连接后转换为机器内部可识别的段号和段内单元号。例如如果X对应的段号为3，对应的段内单元地址为50的话，CALLX|可被编译成CALL3|。,93,5.3.2段式存储管理,段的概念：段式管理的基本原理：在分段存储管理中，内存分配的单位是段。每段分配一个连续的内存区域，而各段之间可以分配不连续的内存区域。由于段的长度是不同的，所以分配给每个段的内存区域的长度是不同的。在分段存储管理方式中，每段分配一个连续的内存区域，由于各段长度不同，这些区域的大小也就不一。因此，对于段的内存的管理采用可变式分区内存管理的方式，分配与释放算法与可变式分区的内存分配与释放算法相同。,94,1.段式存储管理的实现思想：段的概念：具有完整的逻辑意义的程序的单位。进程地址空间由若干个逻辑分段组成，每个分段是一组逻辑意义完整的信息集合，每段都有名字，每段都是首地址为0的连续一维地址空间。整个进程的地址空间是二维的。图5-8：分段地址空间示例。基本原理：在分段存储管理中，内存分配的单位是段。每段分配一个连续的内存区域，而各段之间可以分配不连续的内存区域。段式存储管理以段为单位分配内存，每段分配一个连续内存区，各段之间不要求连续。内存的分配与回收类似于动态分区分配。,5.3.2段式存储管理,95,图5-8分段地址空间,5.3.2段式存储管理,96,段式存储管理系统中，进程地址空间二维。地址结构包括段号和段内位移两部分，形式：段号S从0开始的连续正整数。段号长度和段内位移长度确定后，一个进程地址空间允许的最大段数和各段的长度确定。例：段号长度为8，段内位移的长度为16，一个进程最多可有256段，最大段长为64K字节。段式存储管理以段为单位分配内存，每段分配一个连续的内存区域。各段长度不等，这些存储区大小也不相等，同一进程包含的各段之间不要求连续。,5.3.2段式存储管理,97,段表：段表：每个作业一张，基本内容包括段号、段长和段的内存起始地址。与页式存储管理类似，为实现逻辑地址到物理地址变换，系统为每个进程建立一个段表，每个表项描述一个分段信息，至少应包括段号、段长和该段的主存起始地址。地址变换：利用段表实现动态重定位。,5.3.2段式存储管理,98,2.地址变换过程：为实现从进程逻辑地址到物理地址的转换，设置段表寄存器，存放段表起始地址和段表长度。地址变换时，将逻辑地址中段号与段表长度比较，若段号超过段表长度，段号超界，产生越界中断信号；若未越界，根据段表起始地址和段号计算对应段表项位置，读出该段在内存中的起始地址，再检查段内地址是否超过段长，若超过，发出越界中断信号；若未越界，将段的起始地址与段内位移相加，得到物理地址。为提高内存访问速度，可以用快表。图5-9：段式系统的地址变换过程。,5.3.2段式存储管理,99,5.3.2段式存储管理,段式方式地址变换示例：,D的段内偏移100,段的起始地址5460加段内偏移100=5460+100=5560,得到1234,100,5.3.2段式存储管理,段式地址变换过程举例说明：某作业经过编译连接后，其MAIN段、X段、A段、B段的段号分别是0、1、2、3，A段的单元的段内地址是100。在图中，给出了该作业的段表的结构以及该作业的各段在内存中的存放情况。现在该作业被调度到处理器运行，其段表起始地址和长度装入段表控制寄存器。当运行到指令LOAD1，A|时，需要进行地址变换以便访问内存单元。（1）系统查找段表得到2号段（即A段）的起始地址是5460；（2）将该段的起始地址与段内地址相加，即5460+100=5560；（3）以物理地址5560去访问内存单元，取得要得到的数据1234。以上通过段表实现地址变换的过程是借助硬件来自动完成的。与分页管理类似，分段管理每访问一次内存数据也需要两次寻址，即对段表的访问和对内存块地址的访问。,101,图5-9段式系统的地址变换过程,5.3.2段式存储管理,102,3.段的共享与保护段是按逻辑意义来划分的，可以按名存取，所以，段式存储管理可以方便的实现内存的信息共享，并进行有效的内存保护。段的共享：段式系统中实现分段共享的方法：两个进程段表中相应表项都指向被共享过程的同一个物理副本。段的共享是指量各以上的作业，使用同一个子程序，在内存中只包含一个副本。具体的操作是在每个进程的段表中，用相应的表项指向共享段在内存中的起始地址即可。当用户进程或作业需要共享内存中某段的程序或数据时，则只要用户使用相同的名字，就可以在新的段表中填入已存在段的内存起始地址，并设置一定的访问权限，从而实现段的共享。当共享此段的某进程不再需要它时，应将该段释放，取消在该进程中共享段所对应的表项。多道程序下，必须注意共享段中信息的保护。一个进程正从共享段中读取数据时，必须防止另一个进程修改该段中数据。多数共享系统中，程序分成过程区和数据区。不能修改的过程称为纯过程或可重入过程，可以和不能修改的数据共享，可修改的程序和数据不能共享。,5.3.2段式存储管理,103,5.3.2段式存储管理,分段系统中段的共享,104,3.段的共享与保护段的保护：在分段系统中，由于每个分段在逻辑上是独立的，因而比较容易实现信息保护。段的保护是为了实现段的共享和保证作业正常运行的一种措施。段式管理主要有两种保护方法：地址越界保护法，存取控制保护法。地址越界保护法：段表寄存器中段表长度与逻辑地址中段号比较，段号超界产生越界中断；再用段表项中段长与逻辑地址中段内位移比较，段内位移大于段长，产生越界中断。在允许段动态增长系统中，允许段内位移大于段长。段表中应设置相应的增补位，以指示该段是否允许动态增长。段的存取控制：,5.3.2段式存储管理,105,4.段式管理的特点：与页式管理和分区管理相比，段长可根据需要动态增长，便于对具有完整逻辑功能的信息段共享，便于实现动态链接。每个分段是一组有意义的信息或具有独立功能的程序段，段的地址空间二维，可以在进程运行过程中调用一个程序段或数据段时再进行链接。比其他几种方式要求更多硬件支持，提高硬件成本。在内存空闲区管理方式上与分区式管理相同，存在碎片问题。每段长度受内存可用空闲区大小的限制。,5.3.2段式存储管理,106,5.分页和分段的主要区别：分页和分段存储管理系统虽然有很多地方相似，（1）页是信息的物理单位，分页是为了实现离散分配，提高内存利用率，便于系统管理；而段是信息的逻辑单位，每一段在逻辑上是相对完整的一组信息，如一个函数，一个过程，一个数组，分段是为了满足用户的需要。（2）分页式存储管理的作业的地址空间是一维的，地址从0开始编号一直到末尾，而分段式存储管理作业地址空间是二维的，要识别一个地址，除给了段内地址外，还必须给出段号。（3）页的长度由系统决定，是等长的。而段的长度是由具有相对完整意义上的信息长度决定。,返回,5.3.2段式存储管理,107,5.3.3段页式存储管理,基本概念：段页式存储管理方便使用又提高了内存利用率，是目前用的较多的一种存储管理方式。它主要涉及到以下的概念：（1）等分内存。它把内存分成大小相等的内存快，称之为页。（2）作业或进程的空间。采用分段方式，按程序的逻辑关系把进程的地址空间分成若干段，每一段都又一个段名。（3）段内分页。按照内存的大小将各个段分成若干页。每段从0开始依次编以连续的页号。（4）内存分配。内存以页为单位分配给每个进程。,108,页式系统能有效提高内存利用率，段式系统能反映程序的逻辑结构并有利于段的共享。两种存储管理方式结合起来，形成段页式存储管理方式。段页式存储管理系统中，进程地址空间先分成若干个逻辑分段，每段有段号；将每一段分成若干大小固定的页。主存空间管理与页式管理一样，分成若干个和页面大小相