存储器的管理课件文本.ppt

第4章 存储器管理,本章学习目标 本章主要讲解了存储器管理的基本方式，剖析了Linux 操作系统对内存的管理模式。通过对本章学习，读者应该达到以下学习目标：重点掌握本章的基本概念，分页式存储管理技术和分段式存储管理技术，虚拟存储器的概念。理解段页式存储管理技术，虚存中的置换算法。了解Linux操作系统的存储管理技术。,第4章 存储器管理,1,教学内容,4.1 存储器管理概述4.2 连续分配存储管理方式4.3 分页存储管理方式 4.4 分段存储管理方式4.5 虚拟存储器的基本概念4.6 请求分页4.7 请求分段存储管理4.8 LINUX系统的内存管理方法 本章小结,2,4.1 存储器管理概述,4.1.1 存储器的层次图4.1所示就是存储器的体系结构。,第4章 存储器管理,3,4.1.2 用户程序的处理过程,用户程序处理分以下几个阶段：（1）编译。由编译程序将用户源代码编译成若干个目标模块。（2）链接。有链接程序将编译后形成的目标代码以及它们所需的库函数，链接在一起，形成一个装入模块。（3）装入。有装入程序将装入模块装入内存。处理过程示意图见4.2,第4章 存储器管理,4,第4章 存储器管理,5,1目标程序装入内存的方式,程序只有装入到内存后才能运行。装入方式分绝对装入方式、可重定位装入方式和动态运行时装入方式。（1）绝对装入方式 在编译时，如果知道程序将驻留在内存什么位置，那么编译程序将产生绝对地址的目标代码。绝对装入程序按照装入模块中的地址，将程序和数据装入内存。装入模块被装入内存后，不须对程序和数据的地址进行修改，程序中所使用的绝对地址，即可以在编译或汇编中给出，也可以有程序员直接给予。一般不让程序员给予地址，通常情况是在程序中采用符号地址，然后在编译或汇编时，将这些符号地址再转化为绝对地址。,第4章 存储器管理,6,（2）可重定位装入方式 又称静态重定位。是在程序执行之前，有操作系统的重定位装入程序完成。一般用于多道程序环境中，编译程序不能预知所编译的目标模块在内存什么地方。重定位程序根据装入程序的内存起始地址，直接修改所涉及到的逻辑地址，将内存的起始地址加上逻辑地址得到正确的内存地址。,第4章 存储器管理,7,第4章 存储器管理,8,（3）动态运行时的装入方式,又称动态重定位。是在程序执行期间进行的。一般说来，这种转换有专门的硬件机构来完成，通常采用一个重定位寄存器，每次进行存储访问时，对取出的逻辑地址加上重定位寄存器的内容，形成正确的内存地址。如图4.4所示.,第4章 存储器管理,9,第4章 存储器管理,10,2目标程序链接,链接程序的功能，是将经过编译或汇编后得到的一组目标模块以及它们所需要的库函数，装配成一个完整的装入模块。实现链接的方法有三种：静态链接、装入时动态链接和运行时动态链接。（1）静态链接 设编译后得到的三个目标模块A、B、C，它们的长度分别为L、M和N。程序链接示意图如图4.5所示。需要完成的工作是对相对地址进行修改，同时变换外部调用符号，将每个CALL语句改为跳转到某个相对地址，从而形成一个完整的装入模块，又称可执行文件。通常不再拆开，运行时可直接装入内存。这种事先进行链接，以后不再拆开的方式称为静态链接。,第4章 存储器管理,11,（2）装入时动态链接 用户源程序经编译后得到目标模块，是在装入内存时边装入边链接的。即在装入一个目标模块时，若发生一个外部模块调用时，将引起装入程序去找相应的外部目标模块，并将它装入内存。（3）运行时动态链接 装入时进行的链接虽然可以将整个模块装入到内存的任何地方，但装入摸块的结构是静态的。在程序执行期间装入模块是不可改变的，因为无法预知本次要运行哪个模块，只能将所有可能要运行的模块，在装入时全部链接在一起，使得每次执行的模块都相同。这样效率很低，因此采用运行时动态链接。在这种链接方式中，可将某些目标模块的链接，推迟到执行时才进行。即在执行过程中，若发现一个被调用模块尚未装入内存时，有OS去找该模块，将它装入内存，并把它链接到调用模块上。,第4章 存储器管理,12,第4章 存储器管理,13,4.2连续分配存储管理方式,连续分配是指为一个用户程序分配一个连续的内存空间，连续分配有两种：单道程序的连续分配和多道程序的连续分配。多道程序的连续分配又称为分区分配方式，它包括固定分区、动态分区和动态重定位分区三种。下面就是对各种连续存储管理的研究。,第4章 存储器管理,14,4.2.1 单道程序的连续分配,这是一种最简单的存储方式，只能用于单用户、单任务的操作系统。在这种存储方式中，内存分为两个分区：系统区和用户区。1系统区。仅供操作系统使用，一般驻留在低址部分，其中包括中断向量。,第4章 存储器管理,15,2用户区 操作系统以外的全部空间。其结构图如图4.6所示。,第4章 存储器管理,16,为了避免用户程序执行时访问了操作系统所占空间，应将用户程序的执行严格控制在用户区域。称之为存储保护，保护措施主要是有硬件实现。硬件提供界地址寄存器和越界检查机构。将操作系统所在空间的下界a存放在界地址寄存器中，用户程序执行时，每访问一次主存，越界检查机构便将访问主存的地址和界地址寄存器的值进行比较，若出界则报地址错。,第4章 存储器管理,17,第4章 存储器管理,18,4.2.2 固定分区分配方式,固定分区管理比较简单，本节仅以举例的方式说明其原理。设一个容量为32k的实际内存，分割成如下若干区域，如图所示。,这种分区分配方式在整个系统运行期间是不变的。在这种情况下，当为一个作业分配空间时，应该先判定它分在哪个区域比较合适，然后再进行分配。,第4章 存储器管理,19,4.2.3 动态分区分配,动态分区分配需要解决的问题有三个：（1）分区分配中所用的数据结构。（2）分区的分配算法。（3）分区的分配与回收操作。1分区分配中的数据结构。要实现分区分配，系统必须配置相应的数据结构，用来记录内存的使用情况。为分配提供依据。常用的数据结构有两种：,第4章 存储器管理,20,（1）空闲分区表其表的结构如图4.11所示：,第4章 存储器管理,21,（2）空闲分区链,为了实现对空闲分区的分配与链接，在每个分区的起始部分，设置一些用于控制分区分配的信息，以及用于链接各分区的前向指针：在分区尾部则设置一后向指针；然后形成一个双向链。其结构如图4.12所示。,如图4.12 空闲链结构,第4章 存储器管理,22,二、分区分配算法,为把一个新作业装入内存，须按照一定的分配算法，从空闲区表或空闲分区链中，选一个分区分配给该作业，目前常用以下三种分配算法：1首次适应算法 此算法可以在上述两种数据结构上实施，但通常要求自由块按始地址从小到大的顺序排序。当须分配空间时，总是从头开始查找，直到找到一个符合要求的自由块。,第4章 存储器管理,23,2最佳适应法 可以在上述两种数据结构上实施，但要求按自由块从小到大的顺序排序。分配从头开始查找，即从小端到大端的方向查找。直到找到第一个满足要求的自由块。显然，所能找到的自由块能满足要求的最小块。3最坏适应算法 数据结构和排序方法如上。当分配空间时不 是从小往大查，而是从大往小查，因此，所找到的自由块是所有自由块中最大者。,第4章 存储器管理,24,三、分区分配和回收,在动态分区存储管理方式中，主要操作是分配和回收内存。1分配内存 首先，系统利用某钟算法，从空闲区表中找到所需的分区。设请求的分区的大小为u.size,表中每个分区的大小可表为m.size。若m.size-u.sizesize(size是事先规定的不再切割的剩余分区的大小)，说明多余部分太小，可不再切割，将整个分区分给请求者；否则，从该分区中划分出与请求的大小相等的内存空间分配出去，余下的部分仍留在空闲分区链或空闲分区表中。最后，将分配的首地址返回给调用者。,第4章 存储器管理,25,2回收内存,回收分区的主要工作是：首先检查是否有临接的空闲区，如有则合并，使之成为一个连续的空闲区，而不是许多零散的小的部分；之后，修改有关的分区描述信息。一个回收分区邻接空闲区的情况有四种：如图4.13所示。第一种情况是回收分区r上邻的一个空闲区，此时应合并成为一个连续的空闲区，其始址为r上邻的空闲区始址，而大小为二者之和。第二种情况与r下面的空闲区相邻。直接合并。第三种情况是与上下空闲区相邻。将三个区域合并成一个连续的空闲区。第四种情况不和任何空闲区相邻，应建立一个新的空闲区，并加到自由主存队列中。,第4章 存储器管理,26,图4.13 内存回收时的情况,第4章 存储器管理,27,4.2.4 可重定位分区,1紧凑 在连续分配方式中，必须把一个系统程序或用户程序，装入到连续的内存空间中，如果在系统中若干个小的分区，其总容量大于要装入的程序，但由于它们不相连接，使该程序不能装入内存。例如图4.14(a)所示.，紧凑后如图4.14(b)所示。,第4章 存储器管理,28,第4章 存储器管理,29,2动态重定位,在该方式中，将程序中的相对地址转换为物理地址的工作被推迟到程序指令真正要执行时进行。因此，允许作业在运行过程中移动的技术，必须获得硬件地址变换机构的支持。即在系统增加一个重定位寄存器，用它来装入程序在内存中的起始地址。程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中地址相加而形成的。,第4章 存储器管理,30,第4章 存储器管理,31,3动态重定位分区分配算法,动态重定位分区分配算法，与动态分区分配算法基本相同；差别仅在于：在这种分配算法中，增加了“紧凑”功能，通常是找不到足够大的空闲区来满足用户的需要，进行“紧凑”。然后寻找合适的内存空间。,第4章 存储器管理,32,4.3 分页存储管理方式,页式系统应解决的问题 采用“紧凑”技术解决按区分配中存在的碎片问题，是以花费CPU时间为代价换来的。为了寻找解决碎片问题的新途径，人们很容易想到让程序不连续存放，例如，有一个作业要求投入运行，其程序的地址空间是3KB,而主存当前只有两个各为1KB和2KB的空闲区。显然各空闲区的大小比该程序的地址空间小，而总和却相同。这样就考虑将程序分开存放。放在不相邻的两个区域中。这正是分页的思想。在分页存储管理中，主存被分成一系列的块，程序的地址空间被分成一系列的页面。然后将页面存放在主存块中。为了便于实现动态地址变，一般主存的块和页面大小相等并为2的幂次。,第4章 存储器管理,33,分页存储管理的基本方法,一、页面和物理块 在分页存储管理中，将一个进程的逻辑地址空间分成若干个相等的片。称为页面或页。相应的，内存空间也分成与页相同的大小的若干个存储块，或称为物理块或页框。为它们从0开始依次编号。如图4.16所示。为进程分配内存时，以块为单位将进程中若干页分别装入不相接的块中。由于进程的最后一页经常装不满一块，而形成不可利用的碎片称为“页内碎片”。二、页表 在分页系统中，允许进程的每一页离散地存储在内存的任一物理块中，但系统应能保证进程的正确运行。即能在内存中找到每个页面所对应的物理块。为此系统又为每个进程建立一张页面映象表，简称页表。在进程地址空间的所有页内（0n），依次在页表中有一页表项，其中记录了相应页在内存中对应的物理块。见图的中间部分。可见页表的作用实现了从页号到物理块号的地址映象。即使在简单的分页系统中，也常在页表的表项中设置一存取控制字。用于对存储块中内容进行保护。,第4章 存储器管理,34,图4-16 页表,第4章 存储器管理,35,三、虚地址结构,如何利用页表进行地址变换，这和计算机所采用的地址结构有关。而地址结构又与所选择的页面尺寸有关。比如，当CPU给出的虚地址长度为32位，页面的大小为4kb时，在分区系统中的地址格式如图4.17所示。页号页内偏移量如图4-17 虚地址结构,第4章 存储器管理,36,四、页式地址变换,下面图4.18所示作业2程序中的一条指令的执行过程，来说明页式系统中的地址变换过程。程序的地址空间中第100号单元处有一条指令为“mov r1,2500”。这条指令在主存中的实际位置为2148号单元（第2块100号单元），而这条指令要取的数123在程序的地址空间中位于2500号单元（第2页的452号单元）处。它在主存中存于7620号单元（第7块452号单元）。假设页面大小为1kb，机器的地址长度为16位。,第4章 存储器管理,37,图4.18 页式系统地址变换结构,第4章 存储器管理,38,当作业2的相应进程在CPU上运行时，操作系统负责把该作业的页表在主存中的起始地址（a）送到页表起始地址寄存器中。以便在进程运行中进行地址变换时由它控制找到该作业的页表。当作业2的程序执行到指令“mov r1,2500”时，CPU给出的操作数地址为2500，首先由分页机构自动把它分成两部分，得到页号p=2,页内相对位移w=452。然后，根据页表始址寄存器指示的页表始地址，以页号为索引，找到第2页所对应的块号7。然后，将块号7和页内位移量w拼接在一起，就形成了访问主存的物理地址7620。这正是所取数123所在主存的实际位置。,第4章 存储器管理,39,五、快表,有一些系统将部分页表放在快速存储器中，其余部仍放在主存中。存放页表部分内容的快速存储器称相联存储器，也称为联想存储器。联想存储器中存放的部分页表称为“快表”。它的格式如图4.19所示。这样的联想存储器一般由8个16个单元组成。它们用来存放正在运行进程的当前最常用的页号和它相应的块号，并具有进行查找的能力和通常的执行过程一样，只要访问一次主存，就可以取出指令或存取数据。如果所需要查的页号和联想存储器中所有的页号不匹配，则地址变换过程还得通过主存中的页表进行。实采用联想存储器和主存中页表相结合的分页地址变换过程如图4.19所示。,第4章 存储器管理,40,图4-19 带有快表的分页地址变换,第4章 存储器管理,41,4.3.3 两级和多级页表,一、两级页表 针对难以找到大的存储空间以存放页表的问题，可利用页表进行分页的办法，使每个页面的大小与内存物理块的大小相同，并为它们编号。可以离散地将各个页面分别放在不同的物理块中，同样为每个离散的页面建立一张页表，称为外层页表。在每个页表项中记录物理块号。如图4.20所示。,第4章 存储器管理,42,图4-20 带有快表的分页地址变换,第4章 存储器管理,43,由图可以看出，在页表的每个表项中存放的是进程的某页在内存中的物理块号，如第0#页存放在1号物理块中，1#页存放在4#物理块中。而在外层页表的每个页表项中，所存放的是某页表分页的首址。如0#页表存放在第1011#物理块中。我们可以利用外层页表和页表这两级页表，来实现从进程的逻辑地址到内存地址的变换。,第4章 存储器管理,44,图4-21 具有两级页表的地址变换机构,第4章 存储器管理,45,为了地址变换实现，在地址机构中同样需要设置一个外层页表寄存器，用于存放外层页表的始址。并利用逻辑地址的外层页号，作为外层页表的索引。从中找到指定页表分页的首址。再利用P2作为指定页表分页的索引，找到指定的页表项。其中即含有该页在内存中的物理块号。用该块号和页内地址d即可构成访问内存的物理地址。图4.21即为两级页表的地址变换机构。,第4章 存储器管理,46,二、多级页表结构,对于32位的机器，采用两级页表的结构是合适的。但对于64位的机器，对于二级页表是否合适，需要简单的分析。如果页面大小仍采用4KB即212B,那么还剩52位，假定仍按物理块的大小（210位）来划分页表，则将所有剩余的42位用于外层页号。此时在外层页表中可能有4096G个页表项，即使按220位来划分页表。此时，每个页表分页将达1MB;外层页表仍有4G个页表项。要占用16GB的连续内存空间。可见，不论怎样划分，其结果都是不能接受的。,第4章 存储器管理,47,4.4 分段存储管理方式,分段系统的基本原理一、分段 在分段存储管理方式中，段是一组逻辑信息集合。例如，把作业按逻辑关系加以组织，划分成若干段，并按这些段来分配内存。这些段是主程序段MAIN，子程序段，数据段，和堆栈段等。每个段都有自己的名字和长度，为了实现简单，通常用一个段号来代替段名。每个段从0开始编号，并采用一段连续的地址空间，各段长度不同。,第4章 存储器管理,48,分段系统中的逻辑地址由段号s和段内偏移量w组成。其地址结构如图所示。,图4-22分段系统中的地址结构,第4章 存储器管理,49,二、分页和分段的主要区别,分页和分段存储管理系统虽然有很多地方相似，（1）页是信息的物理单位，分页是为了实现离散分配，提高内存利用率，便于系统管理；而段是信息的逻辑单位，每一段在逻辑上是相对完整的一组信息，如一个函数，一个过程，一个数组，分段是为了满足用户的需要。（2）分页式存储管理的作业的地址空间是一维的，地址从0开始编号一直到末尾，而分段式存储管理作业地址空间是二维的，要识别一个地址，除给了段内地址外，还必须给出段号。（3）页的长度由系统决定，是等长的。而段的长度是由具有相对完整意义上的信息长度决定。,第4章 存储器管理,50,三、基本原理,所谓分段管理，就是管理由若干段组成的作业，并且按分段来进行存储分配，由于分段的作业地址空间是二维的，所以分段的关键在于如何把分段的地址空间变成一维的地址空间。和分业管理一样，可以采用动态重定位技术进行地址转换。起初系统作业建立一张段表，每个表目至少有4个数据：段号，段长，内存始址和存取控制。其中，段长指明段的大小，内存始址指明该段在内存中的位置，存取控制说明对该段访问的限制（RWX）。段地址转换和分页地址转换得过程基本相同，其大致过程如图4.23所示：,第4章 存储器管理,51,图4-23 分段地址转换过程,第4章 存储器管理,52,（1）将逻辑地址分为两部分，段号s 和段内偏移量w。（2）将该进程的段表地址寄存器中的段表内存地址B与段号s 相加，得到该进程在段表中相应表项的索引值，从该表项中得到该段的长度以及该段在内存中的起始地址。（3）将段内地址d与该段的内存始址相加得到访问单元的内存地址。,第4章 存储器管理,53,信息共享,段是按逻辑意义来划分的，可以按名存取，所以，段式存储管理可以方便的实现内存的信息共享，并进行有效的内存保护。1段的共享 段的共享是指量各以上的作业，使用同一个子程序，在内存中只包含一个副本。具体的操作是在每个进程的段表中，用相应的表项指向共享段在内存中的起始地址即可。如图4.24所示。当用户进程或作业需要共享内存中某段的程序或数据时，则只要用户使用相同的名字，就可以在新的段表中填入已存在段的内存起始地址，并设置一定的访问权限，从而实现段的共享。当共享此段的某进程不再需要它时，应将该段释放，取消在该进程中共享段所对应的表项。,第4章 存储器管理,54,图4-25 分段系统中段的共享,第4章 存储器管理,55,2段的保护,在分段系统中，由于每个分段在逻辑上是独立的，因而比较容易实现信息保护。段的保护是为了实现段的共享和保证作业正常运行的一种措施。分段存储管理中的保护主要有地址越界保护和存取方式控制保护。地址越界保护是利用段表中的段长和逻辑地址中的段内相对地址相比较，如段内地址大于段长，则发出地址越界中断，系统会对段进行保护。,第4章 存储器管理,56,段页式存储管理方式,一、基本概念 段页式存储管理方便使用又提高了内存利用率，是目前用的较多的一种存储管理方式。它主要涉及到以下的概念：（1）等分内存。它把内存分成大小相等的内存快，称之为页。（2）作业或进程的空间。采用分段方式，按程序的逻辑关系把进程的地址空间分成若干段，每一段都又一个段名。（3）段内分页。按照内存的大小将各个段分成若干页。每段从0开始依次编以连续的页号。,第4章 存储器管理,57,（4）逻辑地址结构。一个逻辑地址由3部分构成，段号s、段内页号p和页内地址d，记做v=(s,p,d)，如图4.26所示。段号(s)段内页号(p)段内地址(d)图4-26 逻辑地址结构（5）内存分配。内存以页为单位分配给每个进程。,第4章 存储器管理,58,（6）段表、页表和段表地址寄存器。为了实现从逻辑地址到物理地址的转换，系统要为每个进程或作业建立一张段表，并且还要为该作业中的每一段建立一个页表。这样，作业段表的内容是页表长度和页表地址，为了指出运行作业的段表地址，系统有一个段表地址寄存器，它指出作业的段表长度和段表起始地址。图4.27 给出了段表、页表和内存的关系。,第4章 存储器管理,59,图4-27 利用段表和页表实现地址映射,第4章 存储器管理,60,在段页式存储管理系统中，面向物理实现的地址空间是页式划分的，而面向用户的地址空间是段式划分的，也就是说，用户程序被逻辑划分为若干段，每段又划分成若干页面，内存划分成对应大小的块，进程映像是以页为单位进行的，从而使逻辑上连续的段存入在分散内存块中,第4章 存储器管理,61,二、地址转换,在段页式系统中，一个程序首先被分成若干程序段，每一段赋予不同的分段标识符，然后，将每一段又分成若干个固定大小的页面。段页式系统中地址转换过程如图4.28所示。,第4章 存储器管理,62,图4-28 段页式系统中的地址转换机构,第4章 存储器管理,63,段页式系统中的地址转换过程大致如下：（1）首先利用段号s，将它与段长TL进行比较，若sTL，表示未越界。于是地址转换硬件将段表地址寄存器的内容和逻辑地址中的段号相加，得到访问该作业段表的入口地址。（2）将段表中的页表长度与逻辑地址中页号p进行比较，如果页号p大于页表长度，则发生中断，否则正常进行。（3）将该段的页表基地址与页号p相加，得到访问段s的页表和第p页的入口地址。,第4章 存储器管理,64,（4）从该页表的对应的表项中读出该页所在的物理块号f,再用块号f和页内地址d组成访问地址。（5）如果对应的页不在内存，则发生缺页中断，系统进行缺页中断处理，如果该段的页表不在内存中，则发生缺段中断，然后由系统为该段再内存建立页表。,第4章 存储器管理,65,三、管理算法,在地址转换过程中，软、硬件应密切配合，这在分页和分段式存储管理中已体现出来，段页式存储管理也是如此，如图4.29所示。,第4章 存储器管理,66,第4章 存储器管理,67,（1）链接障碍中断。这个模块的功能是实现动态链接。即给每个段一个段号，在相应的段表和现行调用表中，为其设置表目，并利用段号改造链接间接字。（2）缺段中断。这个模块的功能是在系统的现行分段表中，建立一个表目，并为调进的段建立一张页表，在其段表的相应表目中登记此页表的始址。（3）缺页中断。这个模块的功能是在内存中找出空闲的存储块，如果没有找到，则调用交换算法，交换内存中的页到外存，然后调进所页面到内存，并修改相应的页表表目。段页式存储管理是分段技术和分页技术的结合，因而，它具备了这些技术的综合优点，即提供了虚存的功能；又因为它以段为单位分配内存，所以无紧缩问题，也没有页外碎片的存在；另外，它便于处理变化的数据结构，段可以动态增长；它还便于共享和控制存取访问权限。,第4章 存储器管理,68,4.5 虚拟存储器的基本概念,虚拟存储器的引入一、局部性原理 早在1968年P.Denning就指出过，程序在执行时，将呈现出局部性规律，即在很短的时间内，程序的执行仅限于某个部分，相应的，它所访问的存储空间仅限于某个区域。他提出以下几个论点：（1）程序在执行时，除少部分的转移和过程调用外。大多数顺序执行。（2）过程调用将会使程序的执行轨迹从一部分区域转到另一部分区域。程序将在一段时间内在这些过程内运行。,第4章 存储器管理,69,（3）程序中存在许多循环结构，它们有少数指令组成，但多次执行。（4）中还包括许多对对数据结构的处理。但对数组进行操作，往往局限于很小的范围。局限性又表现在：（1）时间的局限性。即程序中某条指令一旦执行，不久又可能执行。某个数据结构被访问不久又可能被访问。（2）空间的局限性。一旦某个存储单元被访问，在不久后很快又会被访问。,二、虚拟存储器的定义,虚拟存储器，是指仅把作业的一部分装入内存便可以运行的虚拟存储系统。具体的说，所谓虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存空间进行扩充的一种存储器系统。其逻辑容量由内存和外存之和构成，运行速度接近于内存，成本接近于外存。可见，虚拟存储技术是一种性能非常优越的存储器管理技术。,第4章 存储器管理,71,虚拟存储器的实现方法及其特征,虚拟存储器的实现方法有两种，请求分页系统和请求分段系统两大类。一、请求分页系统 它是在分页系统的基础上，增加了请求调页的功能、页面置换功能所形成的页式虚拟存储系统。开始只是装入若干页的用户程序和数据，便可以启动运行，以后的运行中需要页时，再陆续将所需要的页调入。在请求调页和置换时，需要硬件的支持。1请求分页的页表支持。2缺页中断机构。3地址变换机构。,第4章 存储器管理,72,二、请求分段系统,这是分段系统的基础。增加了请求调段及分段置换功能。形成段式虚拟存储系统。它允许只装入部分程序和数据。然后开始启动。实现请求分段，同样需要硬件的支持。1请求分段的段表机制。2缺段中断机构。3地址变换机构。,第4章 存储器管理,73,三、虚拟存储器的特征,虚拟存储器的特征是离散性、多次性及对换性的特征。其所表现出来的最重要的特征是虚拟性。1离散性 离散性是指内存分配时采用离散分配的形式。没有离散性也就不可能实现虚拟存储器。因为如果采用连续分配的方式，需将作业装入到连续的内存区域，这样需要连续的一次性的申请一部分内存空间，以便将整个作业先后多次装入内存，一方面使一部分内存空间闲置，另一部分，也不可能使大作业运行在一个小的内存空间中。换言之，无法实现虚拟存储功能。只有采用离散分配方式，才能为它申请内存空间，以避免浪费内存空间。,第4章 存储器管理,74,2多次性 多次性是指一个作业被分成多次调入内存运行。作业在运行时没有必要一次装入。只须将当前运行的那部分程序和数据装入内存既可。以后需要哪部分调入即可。多次性是虚拟存储器最重要的特征。任何其它管理方式都不属于这一特征。3对换性 对换性是指允许在作业运行过程中换进换出。允许将暂时不用的程序和数据，从内存调至外存的对换区。以后需要时再从外存调到内存。4虚拟性 虚拟性是指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际的内存容量，这是虚拟存储器所表现出的最重要的特征，也是虚拟存储器最重要目标,第4章 存储器管理,75,4.6 请求分页,4.6.1 请求分页的实现1页表机制 分页系统中地址映象是通过页表实现的。在请求分页系统中，页表项包括下列信息,第4章 存储器管理,76,（1）状态位P。用于指示该页是否已调入内存。（2）访问字段A。用于记录本页在一段时间内被访问的次 数。或最近多长时间没被访问的次数。供置换算法换出页面时参考。（3）修改位M。表示该页在调入内存后是否被修改过。由于内存的每一页在外存都有备份，所以若修改过就将该页再写回外存。没修改过就无须写回。（4）外存.地址。用于指出该页在外存的地址。通常是物理块号。,第4章 存储器管理,77,2缺页中断机构,在请求分页系统中，若所访问的页不在主存，便产生一缺页中断。缺页中断和一般中断相比，有明显的区别，主要表现如下：（1）指令执行期间产生和处理中断信号。通常，CPU都是在一条指令执行完后，再去判断是否有中断。若有则响应中断，没有则执行下一条指令。（2）一条指令在执行期间，可能会产生多次中断。系统中的硬件应能保存多次中断的状态。并保证最后能返回到中断前的缺页中断的指令处，继续执行。缺页中断处理见流程图4.30。,第4章 存储器管理,78,第4章 存储器管理,79,3地址变换机构,请求分页系统中的地址变换机构是在分页系统的地址变换基础上，为实现虚拟存储器而增加某些功能而实现的。请求分页的地址变换过程如图4.31所示。,第4章 存储器管理,80,第4章 存储器管理,81,4.6.2.页面置换算法,1先进先出页面置换算法（FIFO）FIFO，即先进先出算法，这是一种最简单的置换算法。当需要置换一个页面时，总是置换最老即进入内存时间最长的那个页面。下例中，我们设某进程的最大页面数为3，则对于所示页面的走向，其页面失效的次数为15，页面失效率为3/4。FIFO 置换算法是易于理解和实行的。实行时，只要建立一个FIFO队列，并规定最新进入的页面总排在队列最前，而当需要置换时，总是把当前队尾的那个页面换掉。,第4章 存储器管理,82,然而，FIFO算法有可能产生异常现象。所谓异常，是指在相同的页面走向下当分给某一进程的页面数增多时，页面失效不但不降，反而增加这种情况。,第4章 存储器管理,83,2最近最久未使用页面置换算法（LRU）算法,该算法在出现缺页中断时，总是选择最近一段时间内，最长时间没有被访问过的页面，将它唤出外存。假定现有一进程所访问页面的页号序列为：4，7，0，7，1，0，1，2，1，2，6。随着进程的访问，栈中页面号的变化情况如图4.33所示，当访问页面6时，发生缺页，此时页面4是最近最久未被访问的页，应将它置换出内存。页面置换情况如下图所示。,84,3最佳置换算法（OPT）,最佳置换算法是一种理论上的理想算法。采用最佳置换算法可以保证最低的缺页率。例：已知页面走向为：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。系统为该作业分配三个内存块。求页面淘汰顺序。页面置换过程如图4-34所示。,85,4.7 请求分段存储管理4.7.1请求分段的实现,1段表机制 请求分段式管理中，用的主要数据结构是段表。段表结构如下：,第4章 存储器管理,86,在段表项中，除了段名，段长，段在内存的起始地址外，还增加了以下几项：（1）存取方式。用于标识本分段的存取属性是执行、只读还是可读可写。（2）访问字段A。其含义与请求分段的相应字段相同。用于记录被访问段的频率。（3）修改位M。表示该页进入内存后是否被修改过。（4）存在位P。指示本段是否已调入内存。（5）增补位。表示该段在运行过程中是否动态增长。（6）外存始址。指示本段在外存中的起始地址，即起始盘块号。,第4章 存储器管理,87,3缺段中断机构,在请求分段系统中，采用的是请求调段策略。每当进程要访问的段不在内存时，就产生缺页中断。缺段中断的处理：（1）判断虚段S不在内存（2）让请求进程处于阻塞状态（3）判断一下内存中是否有空闲区域（4）若有空闲区域，则从外存读入段S，修改段表和空闲区域表，唤醒请求进程，结束。（5）若没有空闲区域，判总的空闲区是否满足，若满足，则空闲区合并，调入段S，修改段表。若总的空闲区不够，则淘汰一个或几个段，形成一个合适的空闲区，再调入段S。缺段中断流程图如4.35所示：,第4章 存储器管理,88,第4章 存储器管理,89,3地址变换机构,请求分段系统的地址变换机构，是在分段系统地址变换的基础上形成的。当所要访问的段不在内存时。将所缺的段调入内存，并修改段表，再利用段表进行地址变换。变换过程如下：（1）有一个访问地址格式为S|w,其中S为段，w为偏移量。（2）若w的值大于段长，则进行越界中断处理。（3）若w的值小于段长，则检查是否是合法的存取方式，不是，则进行分段保护中断处理。（4）若其它两种情况合法，就判断S是否在主存，在，则修改访问位，形成主存的地址段的始址加上偏移量。,第4章 存储器管理,90,地址变换机构流程图如下所示：,第4章 存储器管理,91,共享与保护,分段存储管理便于实现分段的共享和保护。也简单的介绍了实现分段共享的方法。分段共享采用以下几种方法。1段表 为了实现分段共享，可在系统中配置一张段表，所有的共享段在段表中占一项。段表项的结构如图4-36所示。,第4章 存储器管理,92,图 4-36 共享段表,第4章 存储器管理,93,(1)共享进程计熟count 共享段仅为一个进程所需要。当进程不再需要该段时，可释放该段。并收回该段所占居的内存空间。为了记录有多少个进程需要共享该分段，特设置了一个整型变量count。(2)存取控制字段 对于一个共享段，应给不同的进程以不同的存取权限。例如，对于文件主，通常允许它读和写；而对其它进程，只允许读或执行。(3)段号 对于同一个共享段，不同的进程可以使用不同的段号去共享该段。,第4章 存储器管理,94,2共享段的分配与回收,（1）共享段的分配 由于共享段是供多个进程共享，因此，对共享段的内存分配方式和非共享段的内存分配方式是一样的。在分配共享段时，对第一个使用该段的进程，系统将该共享段调入内存，为共享段加一表项，填写有关表项，把 count加1.当其它的段想共享该段时，不再需要调入内存，只须加一表项，填入该共享段的物理地址；在共享段的段表中，填上进程名，存取控制，再执行count=count+1 操作，表明正有两个进程共享该段。（2）共享段的回收 当共享此段的某进程不再需要它时，该将该段释放。包括取消在该进程段表中共享该段所对应的表项。以及执行count:=count-1操作。若减1结果为0,则有该系统收回该共享段的物理地址。,第4章 存储器管理,95,3分段保护,在分段系统中，由于每个分段是独立的，因此比较容易实现信息保护。目前，采用以下几种方式保护信息。（1）越界检查 在段表寄存器中，存放段表长度信息；同样，在段表中也为每个段表设置段长字段，将逻辑地址空间的段号和段表长度进行比较，若等于或大于段表长度，则发出越界中断信号，其次还要检查段内地址是否等于或大于段长。若大于段长，将产生越界中断信号，从而保证进程有自己的地址空间。,第4章 存储器管理,96,（2）存取控制检查 在段表的每个表项中，设置一个存取控制字段，通常的访问方式有（a）只读。只允许程序对该段中的程序和数据进行访问。（b）只执行。只允许执行，但不允许读写。（c）读/写。允许程序对该段进行读写控制。不同的访问对象，赋予不同的权限。,97,(3)环保护机构 它是一种较完善的保护机构。在该机制中规定：低编号的环具有较高的优先权。OS居于0环内；某些重要的系统软件占据中间环。而一般的应用程序位于外环。程序访问和调用的规则遵循：（a）一个程序可以访问驻留在相同环或较低环中的数据。（b）一个程序可以调用驻留在相同环或高特权环中的服务。,第4章 存储器管理,98,4.8 Linux系统的内存管理方法,4.8.1 Linux的分页管理机制 在Linux中，每个用户进程都可以访问4GB的线性虚拟内存空间。其中从0到 3GB的虚拟地址空间是用户空间，用户进程可以直接对其进行访问。从3GB到4GB的虚拟内存地址空间为内核态空间，存放仅供内核态访问的代码和数据，用户态进程不可访问。所有的进程从3GB到4GB 的虚拟空间是一样的，有同样的页目录项，同样的页表，对应同样的物理内存段。Linux以此方式让内核态进程共享代码段和数据段。,99,内核态虚拟空间从3GB到3GB+4MB的一段，被映射到物理空间0到4MB。Linux 采用“按需调页”技术管理虚拟内存。标准Linux的虚存页表应为三级页表，依次为页目录（Pgd,page Directory）、中间页目录（PMD,page Middlie Directory）和页表(PTE,PageTable)。,100,虚存段的组织与管理,用户进程实际可申请的虚存空间为0至3GB。在用户进程创建时，已由系统调用fork()的执行函数do_fork()将内核的代码段和数据段映射到3GB以后的虚存空间，供内核态进程访问。所有进程的3GB到4GB的虚存空间的映象都是相同的。以此方式共享代码段和数据段。,101,4.8.3内存的共享和保护,Linux中内存共享以页表的形式实现，共享该页的各进程的页表表项直接指向共享页。这种结构不需要设立共享页表，节约内存的占用，但效率较低。当共享页状态发生变化时，共享该页的各进程的页表均需要修改，要多次访问页表。,102,物理空间管理,尽管Linux采用虚拟存储管理策略，有些申请仍然需要直接分配物理空间。例如，为刚创建的进程分配页目录，为装入进程的代码段分配空间，为I/O操作准备缓冲区等等。物理内存以页帧为单位，页帧的长度固定，等于页长，对于INT