操作系统课件-第5章存储器管理.ppt

Chapter 5 存储管理,现代计算机系统中存储器通常由内存和外存组成。内部存储器（简称内存，或称主存primary storage）的管理是操作系统主要功能之一。内存区域一般被分为两大区域：系统区和用户区。系统区用于存放操作系统的内核程序和其它系统常驻程序，这些程序在系统初启时便装入系统区并一直驻留内存。对一个具体的计算机系统，系统区是固定的，一般占据内存的低地址部分。用户区用以存放用户程序和数据以及目态下运行的系统程序，它是用户进程可共享的内存区。存储管理方案：分区存储管理、页式存储管理、段式存储管理、段页式存储管理四种。,5.1 存储管理基本概念,物理内存是由系统实际提供的硬件存储单元（通常为字节）所组成。CPU可直接访问这些存储单元，因此，所有的程序指令和数据必须装入内存，才可得到执行。内存中所有的存储单元从0开始，依次编有一个编号，这个编号称为这个存储单元的内存地址或物理地址。CPU通过物理地址找到其中存放的要执行的指令或数据。内存的地址空间是一维的。内存的访问速度快，但其价格昂贵。计算机系统中实际的内存容量往往有限，不可能存入大量的程序与数据，只能暂时存放将要访问的进程的程序段和数据。而系统中大量的程序和数据存入价格较便宜的外部存储器中，待需要访问时，再将其调入内存。,虚拟存储空间又称为用户地址空间，它不考虑物理内存的大小和信息存放的实际位置，只规定每个进程中互相关连的信息的相对位置。与实际物理内存只有一个(单机系统中)，且被所有进程共享不一样，每个进程都拥有自己的虚拟存储空间，且虚拟存储空间的容量是受计算机的地址结构和寻址方式确定。例如，直接寻址时，如果CPU的有效地址长度是16位，其寻址范围为0到64K。,进程中的目标代码、数据等的虚拟地址组成的虚拟空间称为虚拟存储空间(Virtual memory)。源于程序如何在内存中存储：1）一种是由程序员在程序中直接给出要访问的数据或指令的物理地址；2）使用符号地址，通过地址变换机构 实现虚地址空间到物理地址空间的映射。,存储管理的主要任务,在多道的操作系统中，允许多个进程同时装入内存，通过进程的并发执行来提高CPU的利用率。于是如何将可用内存有效地分配给多个进程，如何让进程的存储容量要求大于可用内存的大进程得以运行，如何保护和共享内存的信息等等，对存储管理提出一系列要求。现代操作系统中，存储管理的目的是既要方便用户，又要有利于提高内存的利用率，因此，存储管理有如下四个主要的任务：,1内存分配内存分配是多道程序共存内存的基础，它要解决的是如何为多个程序划分内存空间，使各个程序在指定的那一部分内存空间里运行。为此，操作系统必须随时掌握内存空间每个单元的使用情况(空闲还是占用)；当有存贮申请时，根据需要选定分配区域，进行内存分配；如果占用者不再使用某个内存区域时，则及时收回。内存分配有静态分配和动态分配两种方式。静态分配是在目标模块装入内存时一次分配进程所需的内存空间，它不允许进程在运行过程中再申请内存空间；动态分配是在目标模块装入内存时分配进程所需的基本内存空间，并允许进程在运行过程中申请附加的内存空间。,2地址变换一般情况下，一个进程装入时分配到的内存空间和它的虚拟地址空间是不一致的。因此，当进程在运行时，其所要访问的指令或数据的实际物理地址和虚拟地址是不同的。显然，如果在进程装入或在它执行时，不对有关的地址部分加以相应的修改，将导致错误的结果。为了保证程序的正确执行，须将程序的虚拟地址转换为物理地址，完成由虚拟地址到物理地址的变换这一过程称为地址重定位或地址映射。虚拟地址空间的程序和数据经过地址重定位后，就变成可由CPU直接执行的绝对地址程序，其变换过程如图5-2所示。,按照重定位的方式，地址重定位可分为静态重定位和动态重定位两种方式：（1）静态地址重定位是在目标程序装入指定的内存区域时，由装配程序完成地址的变换。程序中涉及直接地址的每条指令都要进行这样的修改。优点是不需要硬件支持。缺点：1)程序装入内存后不能在内存中移动；2)程序必须装入连续的地址空间内，不利于程序的共享，也不能充分利用内存空间。,（2）动态地址重定位是指程序在执行的过程中，在CPU访问内存地址之前，由地址变换（硬件）机构来完成将要访问的指令或数据的逻辑地址到物理地址的转换。地址变换机构通常设置一个公用的基址寄存器BR（Base Register），它存放现行进程在内存空间的起始地址。当CPU经逻辑地址访问内存时，地址变换机构将自动把该逻辑地址加上BR中的地址而形成实际物理地址。显然，只要改变BR的内容，就可以改变程序在内存的存放空间。,由此可见，进行动态重定位的时机是在指令执行过程中，每次访问内存前动态地进行的。采取动态重定位可带来两个好处：（1）目标模块装入内存时无需任何修改，因而装入之后再搬迁也不会影响其正确运行，这对于后面将要介绍的存储器紧缩、解决碎片问题是极其有利的；（2）一个程序由多个相对独立的目标模块组成时，每个目标模块各装入一个存储区域，这些存储区域可以不是顺序相邻的，只要各个模块有自己对应的定位存储器就行。动态重定位技术所付出的代价是需要硬件支持。,3.内存信息的共享和保护(3种方法)内存信息的共享与保护也是内存管理的重要功能之一。在多道程序设计环境下，内存中的许多用户或系统程序和数据段可供不同的用户进程共享，这种资源共享将会提高内存的利用率。但是，反过来说，除了被允许共享的部分之外，又要限制各进程只在自己的存储区活动，各进程不能对别的进程的程序和数据段产生干扰和破坏，因此须对内存中的程序和数据段采取保护措施。,1）上下界保护法。上下界保护法是一种常用的硬件保护法。上下界存储保护技术要求为每个进程设置一对上下界寄存器。上下界寄存器中装有被保护程序和数据段的起始地址和终止地址。在程序执行过程中，在对内存进行访问操作时首先进行访址合法性检查，即检查经过重定位后的内存地址是否在上、下界寄存器所规定的范围之内，若在规定的范围之内，则访问是合法的，否则是非法的，并产生访址越界中断。,2）保护键法。保护键法为每一个被保护存储块分配一个单独的保护键，保护键可设置成对读写同时保护的，也可设置成只对读或写进行单项保护的。在程序状态字（PSW）中设置相应的保护键开关字节，对不同的进程，赋予不同的开关代码与被保护的存储块中的保护键相匹配。如果开关字中的代码与保护键匹配或存储块未受到保护，则允许访问该存储块，否则将产生访问出错中断。,3）界限寄存器与CPU的用户态或核心态工作方式相结合的保护方式。在这种保护模式下，用户态进程只能访问那些在界限寄存器所规定范围内的内存部分，而核心态进程则可以访问整个内存地址空间。UNIX系统就是采用的这种内存保护方式。,4内存扩充为了满足大量进程的存贮请求，内存管理应该能够实现在内存中存放尽可能多的用户进程，给它们分配得以运行的足够的内存空间，从而发挥整个系统的使用效率。但是，实际当中计算机的内存容量是有限的，这就要求计算机系统需要提供“扩充的内存”，以保证内存分配的需要。这种扩充不是指物理内存的扩充，而是指利用存储管理软件为用户程序提供一个比实际内存容量更大的逻辑存储空间，即所谓的虚拟存储技术。,5.2 分区式存储管理,分区式存储管理是满足多道程序设计的最简单的一种存储管理技术。分区的基本思想是将内存区域划分成若干个大小不等的区域，每个区域称为一个分区，每个分区存放一道进程对应的程序和数据，使进程在内存中占用一个连续的区域，而且进程只能在所在分区内运行。根据分区的方式，可分为固定式和可变式分区两类。,固定分区是指在用户进程装入之前，系统或系统操作员将用户空间划分为若干个固定大小的区域，每个进程占用一个分区，划分好的分区大小和个数在系统整个系统运行期间不会变化。因此，也称为静态分区。系统对内存的管理和控制通过数据结构分区说明表来实现的。分区说明表中的每个表项记载一个分区的特性，包括分区号、分区大小、分区起始地址和使用状态(已分配用1表示，空闲用0 表示)。内存的分配与释放、存储保护以及地址变换等都是通过分区说明表进行的。分区说明表存放在系统区内，不能由用户改动。,固定分区管理能使多个进程共享内存，具有数据结构简单，分配和回收算法容易实现等优点。但是，存在小进程占据大分区，造成内存浪费的碎片现象和可调入的进程大小受到分区大小限制等的问题。,可变分区是指在装入进程的过程中，根据进程的实际需要，建立分区，该分区的大小正好等于进程的大小。随着系统的运行，内存中的分区大小和个数都会发生变化，因此，又称为动态分区。系统初起时，内存中除操作系统区之外，其余内存空间为一个完整的大空闲区。当有进程要求装入运行时，从该空闲区中划分一块与进程大小一样的区域分配之。当系统运行一段时间后，随着一系列的分配与回收，原来的一整块大空闲区形成了若干个占用区和空闲区相间的布局。,为了实现分区分配，系统中必须配置相应的数据结构，用来描述空闲分区和已分配分区的情况，为分配提供依据。常用的数据结构有以下两种形式：（1）分区分配表。用于记录每个已分配分区的情况。每个分区占一个表目，表目中包括分区序号、分区始址及分区的大小等数据项。（2）空闲分区链（表）。为了实现对空闲分区的分配和链接，在每个分区的起始部分，设置一些用于控制分区分配的信息，以及用于链接各分区所用的前后指针；在分区尾部则设置一后向指针，通过前、后向链接指针，可将所有的空闲分区链接成一个双向链。,1,分区分配算法：1）首次适应算法。该算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止；然后再按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个满足要求的分区，则此次内存分配失败，返回。该算法倾向于优先利用内存中低址部分的空闲分区，从而保留了高址部分的大空闲区。这为以后到达的大进程分配大的内存空间创造了条件。其缺点是低址部分不断被划分，会留下许多难以利用的、很小的空闲分区，而每次查找又都是从低址部分开始，这无疑会增加查找可用空闲分区时的开销。,2,2）循环首次适应算法。该算法是由首次适应算法演变而成的。在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给进程。为实现该算法，应设置一起始查寻指针，用于指示下一次起始查寻的空闲分区，并采用循环查找方法，即如果最后一个（链尾）空闲分区的大小仍不能满足要求，则应返回到第一个空闲分区，比较其大小是否满足要求。找到后，应调整起始查寻指针。该算法能使内存中的空闲分区分布得更均匀，从而减少了查找空闲分区时的开销，但这样会缺乏大的空闲分区。,3）最坏适应算法。最坏适应算法要求空闲分区按其容量以从大到小的顺序形成一空闲分区链。分配时，先检查空闲区链中的第一个空闲分区，若它的大小小于所要求的分区的大小，则分配失败；否则从该分区中划出进程所要求大小的一块内存空间分配给申请分配的进程，余下的空闲区则重新排列后插入空闲区链。最坏适应算法的特点是，总是挑选满足进程要求的最大分区分配给进程，这样使分给进程后剩下的空闲区也比较大，也能装下其它的进程。但是由于最大的空闲区总是首先被分配而进行划分，当有大的进程到来时，其申请的存储空间往往不能得到满足。,4）最佳适应算法。所谓“最佳”是指每次为进程分配内存时，总是把能满足要求、又是最小的空闲分区分配给进程，避免“大材小用”。为了加速寻找，该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。这样，第一次找到的能满足要求的空闲区，必然是最佳的。孤立地看，最佳适应算法似乎是最佳的，然而在宏观上却不一定。因为每次分配后所切割下来的剩余部分总是最小的，这样，在存储器中会留下许多难以利用的小空闲区。,分配内存当一进程要求装入内存时，系统将利用某种分配算法，从空闲分区链（表）中找到所需大小的分区，为进程分配内存内存空间。假设请求的分区大小为u.size，空闲分区链中每个空闲分区的大小可表示为m.size。若m.sizeu.sizesize(size是事先规定的不再切割的剩余分区的大小)，说明多余部分太小，可不再切割，将整个分区分配给请求者；否则（即多余部分超过size），从该分区中按请求的大小划分出一块内存空间分配出去，余下的部分仍留在空闲分链中。然后，将分配区的首址返回给调用者。右图给出了分配流程。,当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链中找到相应的插入点，此时可能出现以下四种情况之一：,回收区既不与F1邻接，又不与F2邻接。这时应为回收区单独建立一新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。,优点：（1）实现了多个作业或进程对内存的共享，有助于多道程序设计，从而提高了系统的资源利用率。（2）该方法要求的硬件支持少，管理算法简单，因而实现容易。缺点：（1）内存利用率仍然不高。存在着严重的碎小空闲区（碎片）不能利用的问题。（2）作业或进程的大小受分区大小控制，除非配合采用覆盖和交换技术来实现内存的扩充。（3）难以实现各分区间的信息共享。,5.3 覆盖与交换技术,覆盖与交换技术是在多道环境下用来扩充内存的两种方法。覆盖技术主要用在早期的操作系统中，而交换技术则在现代操作系统中具有较强的生命力。下面主要介绍覆盖与交换技术的基本思想。,覆盖技术是基于这样一种思想出来的，即一个程序并不需要一开始就把它的全部指令和数据都装入内存后再执行。在单CPU系统中，每一时刻事实上只能执行一条指令。因此，不妨把程序划分为若干个功能上相对独立的程序段，按照程序的逻辑结构，让那些不会同时执行的程序段共享同一块内存区。通常，这些程序段都被保存在外存中，当有关程序段的先前程序段已经执行结束后，再把后续程序段调入内存覆盖前面的程序段。这使得用户看来，好像内存扩大了，从而达到了内存扩充的目的。,整个程序正文段被分为两个部分。一个是常驻内存部分，该部分与所有的被调用程序段有关，因而不能被覆盖。这一部分称为根程序。图5-11(b)中，程序段A是根程序。另一部分是覆盖部分，图5-11(b)中被分为两个覆盖区。其中，覆盖区0由程序段B，C共享，其大小为B，C中所要求容量最大者（50K）。覆盖区1为程序段F，D，E共享，其大小为F，D，E中所要求容量最大者（40 K）。这样，虽然该进程正文段所要求的内存空间中A（20K）+B（50K）+F（30K）+C（30K）+D（20K）+E（40K）=190K，但由于采用了覆盖技术，只需110K的内存空间即可开始执行。,覆盖技术要求程序员提供一个清楚的覆盖结构。即程序员必须完成把一个程序划分成不同的程序段，并规定好它们的执行和覆盖顺序的工作。操作系统根据程序员提供的覆盖结构来完成程序段之间的覆盖。一般来说，一个程序究竟可以划分为多少段，以及让其中的哪些程序共享哪一内存区只有程序员清楚。这就要求程序员既要清楚地了解程序所属进程的虚拟空间及各程序段所在虚拟空间的位置，又要求程序员懂得系统和内存的内部结构与地址划分，这样，加重了程序员的编程负担。因此只有对操作系统的虚拟空间和内部结构很熟悉的程序员才会使用覆盖技术。,广义地说，交换是指先将内存中暂时不运行的进程的某部分的程序或数据写入外存交换区，再从外存交换区中调入指定的进程的程序段或数据到内存中来，并让其执行的一种内存扩充技术。如果交换是以整个进程为单位，便称之为“整体交换”或“进程交换”。如果交换是以“页”或“段”为单位，则分别称为“页面交换”和“分段交换“。在具有交换功能的操作系统中，通常把外存中的一块存储区域划分出来，用来存放从内存中换出的暂时不运行的进程的程序段或数据，这块存储区域称之为交换区。为了提高换进换出的速度，交换区的分配采取的是连续分配方法。因此，对交换区的分配和回收，与动态分区式存储管理方案的方法类似。,与覆盖技术相比，交换技术对用户是透明的，交换不要求程序员给出程序段之间的覆盖结构，而且交换主要是在进程之间进行，而覆盖则主要在同一个作业或进程内进行。另外，覆盖只能覆盖那些与覆盖程序段无关的程序段。但交换技术需要较多的软硬件支持。,5.4页式存储管理,在分区式存储管理方案中，一个进程总占用一块连续的内存区域，因此产生了“碎片”问题。虽然采用拼接技术可以使零散的“碎片”连成一片，但要花费大量的处理机时间。为了更好地解决碎片问题，人们提出了另一种内存存储管理方案，即分页式存储管理方案。该管理方案将使一个进程可以存放在不连续的内存区域中。分页式存储管理方案分为两种：静态页面存储管理方案和动态页面存储管理方案。,1）静态页式存储管理（1）,1基本思想系统首先把内存的存储空间划分成若干个大小相等的小区域，每个小区域称之为页面或存储块，页面按0、1、2、3 的格式依次编号。同样，每个进程的虚拟地址空间也被分成若干个与页面大小相等的多个片段，称之为页，编号为0、1、2、3。分配内存时，进程的每一个页装入内存的一个存储块。同一进程的多个页可以分配在块号不连续的存储块内。静态页式存储管理又称为简单页式存储管理，它的特点是系统如能满足一个进程所要求的全部块数，此进程才能被装入内存，否则，不为它分配任何内存。,1）静态页式存储管理（2）,2数据结构在分页式存储管理方案中，系统使用了存储页面表、页表、请求表三种数据结构来实现虚拟地址到物理地址的变换，完成内存的分配和回收工作。(1)页表一个进程往往有多个页，而这些页在内存又可以不连续存放。那么，系统是如何知道进程的每一页分别存放在内存的哪一个页面呢？分散存放在内存中的进程又是如何正确运行的呢？为此，系统将进程装入内存时，就为每个进程建立一个对应的页表，用于记录一个进程在内存中的分配情况，同时还可利用页表实现逻辑地址到物理地址的变换。最简单的页表由页号与页面号组成。如图5-12所示。,1）静态页式存储管理（3）,(2)请求表为了确定各进程的页表在内存中的实际对应位置，以及每个进程所要求的页面数。系统建立了一张请求表。如图5-13所示，请求表中记录了每个进程的页表起始地址、进程的页表长度和进程所要求的存储块数，状态表示对应的进程是否已建立了相应的页表。在实际系统中请求表由所有进程的PCB对应的表项组成，也就是说，每个进程的PCB中记录着其相应的页表的起始地址和长度。,1）静态页式存储管理（4）,（3）存储页面表存储页面表也是整个系统一张，存储页面表指出内存各页面是否已被分配出去，以及未分配页面的总数。存储页面表也有两种构成方法，一种是在内存中划分一块固定区域，每个存储单元的每个比特位代表一个页面。如果该页面已被分配，则对应的比特位置为1，否则为0。这种方法称为位示图法。存储页面表的另一种构成办法是采用空闲页面链的方法。在空闲页面链中，队首页面的第一个单元和第二个单元分别放入空闲页面总数与指向第一个空闲页面的指针。其他页面的第一个单元则分别放入指向下一个空闲页面的指针。这样所有的空闲页面就链在了一起。空闲页面链的方法由于使用了空闲页面本身的单元存放指针，因此不占用额外的内存空间。,1）静态页式存储管理（5）,3分配与回收算法利用上述三种数据结构，页式存储管理的分配算法实现起来相对简单。分配程序按请求表给出进程所要求的页面数，检查存储页面表中是否有足够的空闲页面，如果没有，则本次分配无法实现。如果有，则首先建立页表，然后搜索出所要求的空闲页面，并将对应的页面号填入页表中。图5-15给出上述页面分配算法的流程图。静态页式存储管理的页面回收方法较为简单，当进程执行完成时，撤消对应的页表，并把页表中的各页面插入存储页面表的空闲链中。,1）静态页式存储管理（6）,4地址结构及地址变换静态页式存储管理的一个关键问题是地址变换，即怎样由利用页表将逻辑地址转换为物理地址的问题。为此，系统中必须设置地址变换机构（硬件系统）来完成地址的变换。（1）地址结构在学习利用页表是怎样完成地址变换之前，必须了解地址结构。在页式存储管理中，分页系统的地址变换机构自动把逻辑地址解释为两部分：高位部分为页号，低位部分为页内地址。因此，逻辑地址用一个数对（p，d）来表示，其中p表示逻辑地址所在的页号，d表示页内地址。d、p所占的位数取决于页的大小和有效地址长度。例如，假设计算机CPU有效地址为16位，且页大小为L1K。在地址变换时，分页系统的地变换机构自动把逻辑地址解释两部分：页号（6位）和页内相对地址d（10位）。如图5-16所示,1）静态页式存储管理（7）,1）静态页式存储管理（8）,由于静态页式存储管理要求每个进程在分配到所申请的全部页面后，才可装入内存得到执行。这使得进程的大小受到可用页面数的限制。而事实上，在一段时间内，CPU总是集中地访问程序中的某一部分。比如，含有局部变量、常用函数、循环语句的程序段，它们往往是经常被访问的部分，人们把这种现象称为局部性原理。这就使得我们可以为用户进程分配一定数量的内存页面就可使程序能正确的运行，为用户提供一个比实际内存更大的虚拟存储空间。由此，在静态页式存储管理的基础上产生了动态页式存储管理。,summary,2）动态页式存储管理（1）,1.基本思想 动态页式存储管理的基本思想是，当一个进程要求运行时，不是把整个进程的程序代码和数据全部装入内存，只需将当前要运行的那部分程序代码和数据所对应的页装入内存，便可启动运行。以后在进程运行的过程中，当需要访问某些页时，由系统自动地将需要的页从外存中调入内存。如果内存没有足够的空闲页面，将暂不运行的页调出内存，以便装入新的页。动态页式存储管理使得用户的程序空间不再受内存空间大小的限制。也即，系统从逻辑上可以为用户提供一个比实际更大的虚拟存储空间，从而实现了内存的逻辑扩充技术。为了区别内外存中的不同的页，通常把一个进程分配调入内存中的页称为“实页”，把在外存中页称为“虚页”。,2）动态页式存储管理（2）,动态页式存储管理中的程序地址空间的分页和地址变换与静态页式存储管理完全相同。但是，由于动态页式存储管理只给运行的进程分配必要的内存空间，因此，必然会产生两个问题：（1）当进程要访问的某个虚页可能不在内存，怎样来发现这种“缺页”情况，发现了怎么办？（2）当需要把某一虚页调入内存时，若此时内存中没有空闲块时，应该怎么处理？,2）动态页式存储管理（3）,2.页表为了知道哪些页调入内存，哪些还没有在内存，以及对页面的换进和换出进行控制，需扩充页表，扩充后的页表如下所示：其中各字段的说明如下：（1）驻留位：用于指示该页是否在内存。（2）访问位：用于记录本页在一段时间内被访问的次数，或记录本页最近有多长时间未被访问，供页换出时参考。（3）修改位：表示该页在调入内存后是否被修改过。由于内存中每一页在外存中都保留有一份副本，因此，若该页在内存中存放时未被修改过，则在置换该页时就不需要将该页写回到外存上，以减少系统启动外存的次数；若已被修改过，则必须将该页写回到外存上，以保证外存中所保留的始终是最新的副本。（4）外存地址：用于指出该页在外存中的地址，以便系统从外存中调入该页。,2）动态页式存储管理（4）,3.缺页中断机构当CPU需访问的页不在内存时，将发生缺页中断，这一过程由专门的硬件机构实现。如图5-19所示。当发生了缺页中断后CPU将转去执行相应的缺页中断处理过程。图5-19中的虚线下面给出了缺页中断的处理过程。当内存中没有空闲块时，系统将按照一定的淘汰算法（有关的淘汰算法将在下一节介绍），在内存中选择一页淘汰，将需要的虚页调入内存。,2）动态页式存储管理（5）,快表,2）动态页式存储管理（6）,页面大小 由于进程的地址空间被连续地划分成若干页，系统以页为单位分配内存，块与页等长。因此，除了一个进程中的最后一页可能不是一个页的大小，而产生“页内碎片”外，内存中不会存在不可利用的空闲页面。因此，静态页式存储管理解决了分区式存储管理的碎片问题。但是页面的大小选择也要恰当。选择最优的页面大小需要在几个相互冲突的因素之间折衷。如果页面太大，页式存储管理就退化为分区式存储管理，同时导致页内“碎片”过大。而页面太小，页表将占用内存空间太多。一个系统的页表占用内存的空间大小与虚存大小和页大小有关。如：一个进程的虚存大小为16兆，页大小为2K，则该进程的页面数为16*1024/2=8192（个）。若一个页表的表目占2个字节，那么页表占用内存的空间大小为8192*2/1024=16K。在动态页式存储管理中，如果页面太小，还要增加内外存交换次数。因此，在实际使用中考虑众多因素，大部分的计算机使用的页面大小在512个字节到64K之间。,2）动态页式存储管理（7）,1.优点（1）由于页式存储管理不要要求作业或进程的程序段和数据在内存中连续存放，从而有效地解决了内存的碎片问题，因此，可使内存得到有效的利用，有可能使更多的进程同时投入运行，进一步可提高处理机的利用率。（2）动态页式存储管理只要求每个进程部分装入便可运行，实现了内存的扩充技术。可为用户提供比实际内存更大的虚拟存储空间，使用户可利用的存储空间大大增加，有利于多道程序的组织，提高内存的利用率。2.缺点（1）要求有相应的硬件支持。例如，地址变换机构，缺页中断机构和页面的淘汰等。这些增加了计算机的成本；（2）增加了系统开销。如页面中断处理，表格的建立和管理，这些都需花费处理机时间，且表格还要占用一定的存储空间；（3）淘汰算法选择不当有可能会严重影响系统的使用效率。（4）虽然消除了碎片，但同时还存在页内碎片问题。,5.5页面淘汰算法,进程在运行过程中，若所访问的页不在内存时，必须把它们调入内存，但当内存空闲页面不足时，必须从内存中调出一页或多页，送到磁盘的交换区中，以便把需要的页调入内存。然而应该将内存中那些页调出内存，须根据一定的算法来确定。通常把选择要换出页的算法称为淘汰算法。而一个好的淘汰算法，应使缺页率尽可能小。在进行页面置换时，可采用全局和局部置换。局部置换指进程发生缺页时，只能从分配给该进程的内存页面中选择一页换出。全局置换是指进程发生缺页时，选择淘汰的页可能是内存中任一进程的页。,1）最佳（Optimal）淘汰算法（1）,1.基本思想 最佳淘汰算法是一种理想的淘汰算法，其选择将来不再使用或者在最远的将来才可能被使用的页淘汰。显然采用最佳淘汰算法可以保证得到最低的缺页率。但是实际上，当发生缺页时，操作系统根本没有办法知道每一个页面被访问将是什么时候，所以，最佳淘汰算法是不能实现的。尽管如此，该算法仍然有意义，它可作为衡量其它算法优劣的一个标准。,1）最佳（Optimal）淘汰算法（2）,例：假设一个进程P有8页，该进程执行过程中，访问页号的顺序是7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1。如果给进程P分配3个内存页面，哪么，采用最佳淘汰算法时，执行进程P将会发生多少次缺页中断？缺页率是多少？,9/20=0.45,2）先进先出（FIFO）淘汰算法（1）,1.基本思想 FIFO淘汰算法认为最先调入内存的页不再被访问的可能性要比其它页大，因而选择最先调入内存的页换出。实现FIFO算法比较简单，只需把各个已分配页面按分配时间顺序链接起来，组成FIFO队列，并设置一个指针，称为置换指针，使它指向FIFO队列队首页面。在选择一页淘汰时，总是淘汰置换指针指向的页，而把换进的页链接入FIFO队尾。,2）先进先出（FIFO）淘汰算法（2）,例：假设一个进程P有8页，该进程执行过程中，访问页号的顺序是7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1。如果给进程P分配3个内存页面，哪么，采用先进先出淘汰算法时，执行进程P将会发生多少次缺页中断？缺页率是多少？,15/20=？,2）先进先出（FIFO）淘汰算法（3）,FIFO算法容易实现，但是它所依据的理由与普遍的进程运行规律不符。它只适用于CPU按线性顺序访问地址空间的进程。而实际上，局部性原理知，大部分的时候，CPU不是按线性顺序访问地址空间的。比如，含有局部变量、常用函数、循环语句的页，虽然在内存中驻留了很久，但是它们往往是经常被访问的页。而FIFO算法可能使这些页刚刚被淘汰出去而又要立即被调回内存，从而使缺页率变大。FIFO算法的另一个缺点是它有一种陷阱现象。一般来说，对于任一作业或进程，如果给它分配的内存页面数越接近它所要求的页面数，则发生缺页的次数会越少。在极限情况下，这个推论是成立的。因为如果给一个进程分配了它所要求的全部页面，则不会发生缺页现象。但是，使用FIFO算法时，在未给进程或作业分配足它所要求的页面数时，有时会出现分配的页面数增多时，缺页的次数反而会增加的奇怪现象。这种现象被称为Belady现象。,2）先进先出（FIFO）淘汰算法（4）,例：假设一个进程P有8页，该进程执行过程中，访问页号的顺序是7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1。如果给进程P分配4个内存页面，哪么，采用先进先出淘汰算法时，执行进程P将会发生多少次缺页中断？缺页率是多少？,10/20=？,看下一个例子！,2）先进先出（FIFO）淘汰算法（5）,例：假设一个进程P1有5页，该进程执行过程中，访问页号的顺序是1，2，3，4，1，2，5，1，2，3，4，5。如果给进程P1分配3（4）个内存页面，采用FIFO淘汰算法时，进程P1在内存中的各页变换如下图所示。,9/12=？,10/12=？,3）最近最久未使用（LRU）淘汰算法（1）,1.基本思想 由于无法预知各个页面将来的访问情况，只能利用“最近的过去”作为“最远的将来”的近似。LRU（Least Recently Used）淘汰算法出发点是，如果某页很长时间未被访问，则它在最近一段时间内不会被访问。因此，LRU淘汰算法每次选择最近久未被访问的页淘汰。,3）最近最久未使用（LRU）淘汰算法（2）,例：假设一个进程P有8页，该进程执行过程中，访问页号的顺序是7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1。如果给进程P分配3个内存页面，哪么，采用先进先出淘汰算法时，执行进程P将会发生多少次缺页中断？缺页率是多少？,12/20=？,3）最近最久未使用（LRU）淘汰算法（3）,LRU虽然是一种较好的淘汰算法，但是完全实现LRU淘汰算法的代价比较大。为了实现LRU淘汰算法，需要一个存放内存中所有页面的链表，最近使用的页在表头，最久未使用的页在表尾。困难的是这个链表必须在每次访问页时都进行更新，以便在链表中找到最久未被访问的页，而将它移到表尾是一个非常费时的操作。,3）最近最久未使用（LRU）淘汰算法（4）,下面是用一些特殊的硬件实现LRU的方法。（1）寄存器法。为了记录某进程在内存中各页的访问情况，须为每个内存页面配置一个移位寄存器，可表示为：RRn-1 Rn-2R1 R2。当某一内存页面被访问时，将其对应的寄存器的Rn-1置为1，每隔一定时间将寄存器R中值右移一位。这样，当需要淘汰一页时，R中值最小的一页，就是最近最久未访问的页。例如，在图5-27所示中，某进程在内存中占用了6个内存页面，每页对应的寄存器R的R7R0的值表示一段时间间隔内该页被访问的情况。这里，第6页的值最小，因此，6页是最近最久未被访问的页，当发生缺页时，首选将它换出。,3）最近最久未使用（LRU）淘汰算法（5）,（2）栈可利用一个特殊的栈来保存当前使用的各个页号。每当进程访问某页时，便将该页的页号从栈中移出，将它压入栈顶。因此，栈顶始终是最近新被访问的页号，而栈底则是最近最久未使用的页。,4）LRU的近似方法（1）,（1）最近未使用NUR（Not Recently Used）算法。该算法是在淘汰某一页时，从那些最近一段时间内未被使用的页中任选一页淘汰。该算法认为，淘汰一个在最近一段时间内没有被访问的已被修改过的页要比淘汰一个被频繁访问的没有被修改过的页要好。实现此算法需在页表中增设两个状态位：访问位R与修改位M。R表示对应的页在最近一段时间内是否被访问过，M表示对应的页是否被修改过。一个进程启动时，所有的页对应的M与R都由系统设置为0。当某页被访问时，置其访问位为1，如果该页被修改过，则置其修改位M为1。系统周期性地（比如在每次时钟中断时）对所有引用位清零，以便把最近未被访问和被访问的页区别开来。这样，内存中可能有四种类型的页面：第1类：R0，M0，没有被访问过，没有被修改过，是最佳的淘汰页；第2类：R0，M1，没有被访问过，被修改过；第3类：R1，M0，被访问过，没有被修改过；第4类：R1，M1，被访问过，被修改过；当发生缺页时，依次从编号最小的非空类中随机的选择一页淘汰。NUR算法的优点是，易于实现和高效性。虽然它的性能不是最好的，但在实际中常常是够用的。,4）LRU的近似方法（2）,（2）最不经常使用NFU（Not Frequently Used）算法。该算法是在需要淘汰某一页时，选择到当前时间为止，被访问次数最少的那一页。这只需在页表中给每一页增设一个访问计数器即可实现。每当该页被访问时，访问计数器加1，而发生缺页时，则淘汰计数器值最小的那一页，并将所有的计数器清零。NFU算法的问题是，如果有两个页的计数器都是0，我们只能随机的选择一页淘汰，而在实际中，有可能一个页上次被访问是在9个周期以前，另一个页在1000个周期以前，而在NFU算法中却不能反映，结果是淘汰出去的可能是有用的页而不是不再使用的页。,5）抖动现象与工作集,在动态页式存储管理中，有可能出现这样的现象：对于刚刚被淘汰出去的页，进程可能马上又要访问它，故又需将它调入内存，因无空闲内存页面而又要淘汰另一页，而后者很可能是即将被访问的页。于是造成系统需要花费大量的时间忙于进行这种频繁的页面调换，从而无法完成用户所要求的工作。这种现象称之为“抖动现象”现象。那么，抖动现象的发生与什么有关？如何才能防止抖动现象的发生呢？,5）抖动现象与工作集,5）抖动现象与工作集,并发的进程数N的取值与系统为进程分配内存空间的大小有关。为进程分配的实页数越多，进程的缺页率就越小，但并发进程数也就越少，从而CPU利用率下降。为进程分配的实页数过少，进程的缺页率就会增大。可能导致系统发生抖动。从图中可见，如果一个进程占有的实页数能满足MjMMk，那么该进程就获得了有效运行所需的足够内存空间，缺页率将保持在合理的范围内。如果每个进程的实页数都能满足MjMMk，则内存中的并发进程数就是合理的。,5）抖动现象与工作集,总之，为防止系统抖动现象的发生，根本的办法是要控制系统中并发进程的数量以及为各个进程分配合理的实页数。既要使每个进程都有足够的内存空间，又要使系统中的并发进程数接近最佳值。目前，防止抖动现象的发生通常有两种方法：一种是选择好的淘汰算法，以减少缺页次数。好的淘汰算法，应当在置换页面时，尽可能选择暂时不用或永久不用的页，使内存中存放的是一个进程一段时间内所需的页。一种是扩大工作集。所谓工作集，是指进程在某个时间段里要访问的页的集合。如果能够预知进程在某段时间的工作集，并在此之前把该集合调入内存，至该段时间终了时，再将其在下一时间段时不需要访问的哪些页换出内存，这样就会可以减少页的交换。但是一个进程在某段时间内的工作集是很难确定的。事实上，由于各进程所包含的程序段多少，选用的淘汰算法等不一样，工作集的选择也不一样。通常采用的方法是，当进行页置换时，把缺页的进程锁住，不让其换出，而调入的页占据那些暂时得不到执行的进程所占据的内存区域，从而扩大缺页进程的工作集，为它分配更多的内存实页。,