四章节存储管理.ppt

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

1、第四章 存储管理,4.1 引言 4.2 存储管理的功能 4.3 实存管理 4.4虚拟存储器管理 4.5 碎片与抖动问题,存储管理是指存储器资源（主要指内存并涉及外存）的管理。 存储器资源的组织（如内存的组织方式） 地址变换（逻辑地址与物理地址的对应关系维护） 虚拟存储的调度算法,4.1 存储组织,存储器的功能是保存数据，存储器的发展方向是高速、大容量和小体积。 内存在访问速度方面的发展 硬盘技术在大容量方面的发展 存储组织是指在存储技术和CPU寻址技术许可的范围内组织合理的存储结构。 其依据是访问速度匹配关系、容量要求和价格。 “寄存器-内存-外存”结构 “寄存器-缓存-内存-外存”结构； 微

2、机中的存储层次组织： 访问速度越慢，容量越大，价格越便宜；,返回,存储层次结构,快速缓存： Data Cache TLB(Translation Lookaside Buffer) 内存：DRAM, SDRAM等； 外存：软盘、硬盘、光盘、磁带等；,4.2 存储管理的功能,存储分配和回收：分配和回收算法及相应的数据结构。 地址变换： 可执行文件生成中的链接技术 程序加载(装入)时的重定位技术 进程运行时硬件和软件的地址变换技术机构 存储共享和保护： 代码和数据共享 地址空间访问权限（读、写、执行） 存储器扩充：存储器的逻辑组织和物理组织；,4.2.1 内存的分配与回收,内存分配按分配的时机不同

3、，可分为静态存储方式和动态存储方式。 静态存储分配：指内存分配是在作业运行之前各目标模块连接后，把整个作业一次性全部装入内存，并在作业运行过程中，不允许作业再申请其它内存空间，或是在内存中移动位置。内存分配在作业运行前一次性完成。,动态存储分配：作业要求的基本内存空间是在目标模块装入内存时分配，但在作业运行过程中，允许作业申请附加的内存空间，或是在内存中移动，即分配工作可以在作业运行前及运行过程中逐步完成。 动态存储分配具有较大灵活性，内存利用率高。,4.2.2 地址重定位,重定位：把逻辑地址(编写程序时使用的地址)转变为内存的物理地址的过程,由操作系统中的装入程序loader来完成。,返回,

4、1. 逻辑地址、物理地址和地址映射,逻辑地址（相对地址，虚地址）：用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式。 其首地址为0，其余指令中的地址都相对于首地址来编址 不能用逻辑地址在内存中读取信息。 物理地址（绝对地址，实地址）：内存中存储单元的地址。物理地址可直接寻址。 地址映射：将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址。 当程序装入内存时, 操作系统要为该程序分配一个合适的内存空间，由于程序的逻辑地址与分配到内存物理地址不一致, 而CPU执行指令时，是按物理地址进行的，所以要进行地址转换。,逻辑地址、物理地址和地址映射,地址映射,300,Mov

5、R1 1200,1100,3456,2. 地址重定位,优点：不需硬件支持，可以装入有限多道程序 缺点：一个程序通常需要占用连续的内存空间，程序装入内存后不能移动，不易实现共享，内存利用率低。,地址重定位分为：静态地址重定位和动态地址重定位。 静态地址重定位：在可执行文件中，列出各个需要重定位的地址单元和相对地址值。当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后不再转换（一般在装入内存时由软件完成）。即：装入时根据所定位的内存地址去修改每个重定位地址项，添加相应偏移量。,可执行文件在内存中的重定位,说明：重定位表中列出所有修改的位置。如：重定位表的150表示相对地址150处的内

6、容为相对地址(即100为从0起头的相对位置)。在装入时，要依据重定位后的起头位置(2000)修改相对地址。 重定位修改：重定位表中的150-绝对地址2150(=2000+150) 内容修改：内容100变成2100(=100+2000)。,动态重定位,动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行,通过硬件机构来完成，硬件机构一般采用的是重定位寄存器，完成虚拟地址到实际内存地址的变换。因此， 装入内存后的所有地址都仍是相对地址。,动态重定位的实现,在每次进行存储器访问时，对取出的逻辑地址加上重定位寄存器的

7、内容，形成内存地址，重定位寄存器的内容是程序装入内存的起始地址。,优点： OS不要求将程序装入连续的内存空间，可以将一个程序分散存放于不连续的内存空间，内存中程序可以移动，有利于实现共享。 部分地装入程序 ，也便于作业共享同一程序副本。 缺点：需要硬件支持（通常是CPU），OS实现较复杂。它是虚拟存储的基础。,4.2.3 存储保护,在多道程序设计环境中，要保证各道程序只能在自己的存储区中活动，不能对别的程序产生干扰和破坏，不能破坏操作系统的内存区。 由于存储保护检查是针对每个存储访问操作进行的，必须由相应的处理器硬件机构支持。 存储保护的目的： 保护系统程序区不被用户侵犯（有意或无意的） 不允

8、许用户程序读写不属于自己地址空间的数据（系统区地址空间，其他用户程序的地址空间）,普遍采用的硬件界限寄存器保护法： （1）上、下界存储保护：是一种简单的存储保护技术。系统为每一个作业设置一对上、下界寄存器，分别用来存放当前运行作业在内存空间的上、下边界地址，来限制用户程序的活动范围。 （2）基址限长存储保护：系统为每个作业设一个基址寄存器和一个限长寄存器，基址寄存器存放该作业在内存的首址，限长寄存器存放该作业的长度。,对于存储保护除了防止越界外，还可对某一区域指定专门的保护。常见的对某一区域的保护方式有四种： （1）禁止做任何操作 （2）只执行 （3）只读 （4） 读/写,4.2.4 虚拟存储

9、器,内存不够用的矛盾。 作业全部装入内存造成浪费。 程序执行具有局部性规律。,返回,1. 问题的引出,在程序装入时，不必将其全部读入到内存，而只需将当前需要执行的部分页或段读入到内存，就可让程序开始执行。 在程序执行过程中，如果需执行的指令或访问的数据尚未在内存（称为缺页或缺段），则由处理器通知操作系统将相应的页或段调入到内存，然后继续执行程序。 另一方面，操作系统将内存中暂时不使用的页或段调出保存在外存上，从而腾出空间存放将要装入的程序以及将要调入的页或段。只需程序的一部分在内存就可执行。,返回,2. 虚拟存储的基本原理,3. 虚拟存储器定义,所谓虚拟存储器， 是指具有请求调入功能和置换功能

10、,能从逻辑上对内存容量加以扩充的一种存储器系统。其运行速度接近于内存速度，而每位的成本却又接近于外存。可见，虚拟存储技术是一种性能非常优越的存储器管理技术，故被广泛地应用于大、 中、 小型机器和微型机中。 在虚拟存储管理中,一般将硬盘作为外存,并且其逻辑地址空间大小与物理内存大小没有直接关系,由计算机系统的地址结构决定.,4. 引入虚拟存储技术的好处,大程序：可在较小的可用内存中执行较大的用户程序； 大的用户空间：提供给用户可用的虚拟内存空间通常大于物理内存(real memory) 并发：可在内存中容纳更多程序并发执行； 易于开发：不必影响编程时的程序结构,4.3 实存管理,实存管理与虚存管

11、理相对应，其特点是作业运行时，整个作业的逻辑地址空间必须全部装入内存，当作业尺寸大于主存可用空间时，该作业无法运行。常见的实存管理技术有固定分区存储管理、可变式分区存储管理和纯分页存储管理。 内存分为两个区域：系统区，用户区。系统区仅提供给OS使用，通常是放在内存的低址部分；用户区是指除系统区以外的全部内存空间， 提供给用户使用,应用程序装入到用户区，可使用用户区全部空间。,4.3.1 固定分区存储管理,基本思想：在作业未装入内存之前，就由操作员或操作系统把内存划分为若干个固定大小的存储区，除操作系统占用一个区外，其余区域为操作系统中多个用户共享，在系统运行期间，分区大小、数目都不变。 在固定

12、分区存储管理系统中，每个用户作业运行时可分配到一块足够大的区域，用户作业一次性装入到分配区，并限制只能在这个区中运行。 特点：适用于多道程序系统和分时系统 支持多个程序并发执行 难以进行内存分区的共享。 问题：可能存在内碎片和外碎片。 内碎片：占用分区之内未被利用的空间 外碎片：占用分区之间难以利用的空闲分区（通常是小空闲分区）。,为了进行分区的分配和回收，在固定分区存储管理系统中，有一张记录 内存配和使用情况的说明表，分区说明表用来记录各分区的起始地址、分区大小和分区分配状态。,固定分区分配中的分区表,优点：易于实现，开销小。 缺点： 内碎片造成浪费 分区总数固定，限制了并发执行的程序数目。

13、 采用的数据结构：分区表记录分区的大小和使用情况,4.3.2 可变分区存储管理,在作业装入时，按其对内存空间的实际要求要求进行分配，每个分区的尺寸与进入它的作业大小相同。 优点：没有内碎片。 缺点：有外碎片。,在可变式存储管理中，常把空闲区组织成空闲分区表和空闲分区链表 。,空闲分区表。 空闲分区包括分区序号、分区起始地址、分区大小的数据，空闲分区表要占用一定数量的存储单元存放表，增加了系统开销。 (2) 空闲分区链表。 空闲分区链表的组织形式：在每个空闲分区的起始部分开辟出一个单元，存放一个链表指针和该分区的大小，链表指针指向下一个空闲分区。系统中用一个固定单元作为空闲分区链表的链表头指针，

14、指向第一块空闲分区首指针，最后一块空闲分区的链表指针存放链尾标志。链表按空闲分区在内存的位置顺序由小到大链接起来。空闲分区链表的组织时，空闲分区的信息放在空闲区内，不会额外增加系统开销。,1. 空闲分区的组织形式,2.内存的分配和回收,内存的分配 在可变式分区存储管理中，当作业要求一个Xk 大小的存储空间时，系统从链表头指针开始依次检索空闲区，找到第一个大于等于Xk的空间。若系统中所有空闲区都小于Xk，无法分配。若有空闲区等于Xk大小，则修改链表指针，取消该空闲块，并向用户返回该空闲区首地址。若该空闲区大于Xk，则将空闲区一分为二，一个为Xk，分给用户，另一个为余下部分，仍留在空闲分区链表中，

15、修改相应链表指针所指向的地址和空闲区大小。,分区释放算法：系统进行回收时，应该检查回收区与内存中前后空闲区是否相邻，若相邻，需要将相邻的空闲分区合并成一个空闲分区。若不相邻，应将空闲区插入到空闲区链表的适当位置。,分区回收,3. 分区分配算法,分区分配算法：寻找某个空闲分区，其大小需大于或等于程序的要求。若是大于要求，则将该分区分割成两个分区，其中一个分区为要求的大小并标记为“占用”，而另一个分区为余下部分并标记为“空闲”。分区的先后次序通常是从内存低端到高端。,返回,首次适应法(first-fit)：将空闲分区按照地址递增的顺序组织成空闲分区链.为作业分配内存时,系统根据作业大小, 从头查找

16、，找到符合要求的第一个分区，如果不等于分区大小，将其分为两部分，一部分给作业，另一部分仍留在空闲区链表中。 该算法的分配和释放的时间性能较好，较大的空闲分区可以被保留在内存高端。 但随着低端分区不断划分而产生较多小分区，每次分配时查找时间开销会增大。 最佳适应法(best-fit)：把空闲分区链表按照分区大小由小到大进行组织。当有作业申请内存时，扫描整个分区链,找到进程满足的最小分区(其大小与要求相差最小的空闲分区) 从个别来看，外碎片较小，但从整体来看，会形成较多外碎片。较大的空闲分区可以被保留。 回收一个分区时，为了把它插入到空闲区链表的合适位置，比较费时间。,最坏适应算法(worst-f

17、it)：把空闲区按大小递减的顺序组织成空闲区链表。当用户申请一个存储区时，检查空闲区链表的第一个空闲区是否满足要求，若不满足，分配失败；若满足，则将空闲分区分配给用户，然后修改和调整空闲区链表。 优点是：查询简单，每次分配的总是最大的空闲区。缺点是：基本不留下小空闲分区，但较大的空闲分区不被保留。,内存紧凑(compaction)：改变进程在内存中的位置，移动存储器中某些已分配分区中的信息，使分散在内存中的碎片能汇集成一片，能分配给其他进程使用。 增加了系统开销 影响了进程正常运行 需要重新定义内存地址,内存紧凑,4.可变式分区的地址重定位,可变式分区的地址重定位采用静态重定位，内存中不能再分

18、配利用的小碎片会越来越多。解决这个问题的办法就是采用紧凑技术，即把小碎片集中起来使之成为一个大的分区。实现的方法是移动各用户分区中的程序，是他们集中于内存的一端，而使碎片集中于另一端。从而将空闲的碎片连成一个较大的分区，共需求的作业使用。 可变式分区的地址重定位采用动态重定位，在执行内存分配时，如无足够大空闲块，可实现紧凑操作。,可变分区的存储保护采用基址限长存储保护方式。 可变分区存储管理的优点：可以有效解决固定式分区的内部碎片问题，能有效利用主存空间，提高多道程序对内存的共享。缺点是容易产生外部碎片问题，要解决外部碎片问题增加了计算机硬件成本。,4.3.3 分页存储管理,页式和段式存储管理

19、是通过引入进程的逻辑地址，把进程地址空间与实际存储位置分离，从而增加存储管理的灵活性。分页存储管理的思想：可以将一个作业分配到几个不连续的区域内，从而不需要移动主存原有的信息，可以有效地解决碎片问题。,基本原理,1. 页面 (1) 页面和物理块 分页存储管理，是将一个进程的逻辑地址空间分成若干个大小相等的页，称为页面或页，并为各页加以编号，从0开始，如第0页、第1页等。程序加载时，分配其所需的所有页，这些页不必连续。需要CPU的硬件支持。相应地，也把内存空间分成与页面相同大小的若干个存储块，称为(物理)块或页框(frame)， 也同样为它们加以编号，如0块、1块等等。在为进程分配内存时，以块为

20、单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”。,分页式存储管理,(2) 页面大小 在分页系统中的页面其大小应适中。页面若太小，一方面虽然可使内存碎片减小，从而减少了内存碎片的总空间， 有利于提高内存利用率，但另一方面也会使每个进程占用较多的页面，从而导致进程的页表过长，占用大量内存； 此外，还会降低页面换进换出的效率。然而，如果选择的页面较大，虽然可以减少页表的长度，提高页面换进换出的速度，但却又会使页内碎片增大。因此，页面的大小应选择得适中，且页面大小应是2的幂，通常为512 B4MB。 小内碎片小；大

21、页表短，管理开销小，交换时对外存I/O效率高。,2.分页存储管理中存储块的分配和回收,当作业有存储分配请求时，可以根据逻辑地址的大小计算出需要的存储块，然后将空闲块分配给作业使用，记录空闲存储块的方法：位示图和链表法。,（1）位图法是用存储单元中的二进制位与存储块相对应，某位的值为0，表示对应的存储块空闲，其值为1，表示已分配。将这些二进制位组合在一块，就构成一张位图。 特点：方法简单查找空闲块费时，但回收比较简单。,（2）链表法 系统设定一个空闲块链表头指针指向链表的第一个空闲块，在每一个空闲块中包含下一个空闲块的指针信息。当用户申请内存时，根据链表头指针顺序分配，回收时，只需将该块插入表头

22、。,2. 地址结构,分页地址中的地址结构如下：,15,10,9,0,对某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按下式求得：,页表 用于记录进程的一个页面和对应的内存物理块号.借助于页表可以实现逻辑地址与物理地址之间的转换.,图 4-11 页表的作用,指令所给出地址分为两部分：逻辑页号，页内偏移地址查进程页表，得物理块号物理地址，把页表放入内存，存取一个数据至少要两次访问内存。,3. 地址变换机构,基本的地址变换机构,页式地址变换举例,快表,为缩短查找时间，可以将内存中的页表中最常用的页号和与之对应物理块号装入到关联存储器(TLB

23、, Translation Lookaside Buffer)，按内容查找(associative mapping)，即逻辑页号物理页号，和页表具有并行查找的能力。,具有快表的地址变换机构,将最近访问的页面的页表信息存放在高速缓存中,其中的页表就是快表.访问快表的速度远远大于访问内存中页表的速度.,存储保护,(1)进行地址变换时，产生的页号应小于页表长度，否则视为越界。 （2）在页表中增加存取控制和存储保护的信息，对每一个存储块，可允许四个保护方式：禁止做任何操作、只执行、只读 、读/写，当要访问某页时，先判断该页的存取控制和存储保护信息是否允许。,优点： 没有外碎片，每个内碎片不超过页大小。

24、 一个程序不必连续存放。 主存利用率高，内存分配和回收算法简单。 缺点： 程序全部装入内存。,分段存储管理方式的引入,引入分段存储管理方式， 主要是为了满足用户和程序员的下述一系列需要： 1) 方便编程 2) 信息共享 3) 信息保护 4) 动态增长 5) 动态链接,4.3.4 分段式存储管理,返回,页式管理是把内存视为一维线性空间；而段式管理是把内存视为二维空间，与进程逻辑相一致。每个作业由若干个逻辑分段组成，每一分段是一组逻辑意义完整的信息集合。,简单段式管理的基本原理,分段存储管理是以段为基本存储单位分配内存，每一段必须是连续的内存空间，将程序的地址空间划分为若干个段(segment)，

25、程序加载时，分配其所需的所有段（内存分区），这些段长度不一致且不必连续；物理内存的管理采用动态分区。需要CPU的硬件支持。,程序通过分段(segmentation)划分为多个模块，如代码段、数据段、共享段。 可以分别编写和编译 可以针对不同类型的段采取不同的保护 可以按段为单位来进行共享，包括通过动态链接进行代码共享 优点： 没有内碎片，外碎片可以通过内存紧缩来消除 便于改变进程占用空间的大小。 缺点： 进程全部装入内存。,返回,31 16 15 0,分段存储管理中的逻辑地址具有如下结构：,1. 段表,内存分配: 以段为单位分配,每段各占一块内存区,各段可以离散的放入内存.,2. 段表,地址变

26、换机构,页式管理和段式管理的比较,(1) 页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头， 提高内存的利用率。或者说，分页是出于系统管理的需要，分段是出于用户应用的需要。段则是信息的逻辑单位，它含有一组意义相对完整的信息。 分段的目的是为了能更好地满足用户的需要。一条指令或一个操作数可能会跨越两个页的分界处，而不会跨越两个段的分界处。,(2) 页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而在系统中只能有一种大小的页面；而段的长度却不固定， 决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。 (3)

27、逻辑地址表示： 分页的作业地址空间是一维的，各个模块在链接时必须组织成同一个地址空间；而分段的作业地址空间则是二维的，既需给出段名， 又需给出段内地址。,（4）分页的优点体现在内存空间的管理上，而分段的优点体现在地址空间的管理上。,4.4 虚拟存储器管理,内存不够用的矛盾。 作业全部装入内存造成浪费。 程序执行具有局部性规律。,返回,1. 问题的引出,虚拟存储器的基本思想：把内存和外存统一管理形成一级存储器，作业运行时，只把必须的一部分信息调入内存，其余部分仍放在外存，当需要时，由系统自动将其从外存调入内存。 程序局部性原理(principle of locality)：指在一段时间内，程序执

28、行过程中往往是集中地访问某一部分内存区域中的指令或数据。所以一个大的作业，只需要装入其中的一部分就可以正常运行。,返回,虚拟存储器定义,所谓虚拟存储器， 是指具有请求调入功能和置换功能， 能从逻辑上对内存容量加以扩充的一种存储器系统。其运行速度接近于内存速度，而每位的成本却又接近于外存。可见，虚拟存储技术是一种性能非常优越的存储器管理技术。 在虚拟存储管理中,一般将硬盘作为外存,并且其逻辑地址空间大小与物理内存大小没有直接关系,由计算机系统的地址结构决定.,引入虚拟存储技术的好处,大程序：可在较小的可用内存中执行较大的用户程序； 大的用户空间：提供给用户可用的虚拟内存空间通常大于物理内存(re

29、al memory) 并发：可在内存中容纳更多程序并发执行； 易于开发：与覆盖技术比较，不必影响编程时的程序结构,虚拟存储技术的特征,离散性：物理内存分配的不连续，虚拟地址空间使用的不连续（数据段和栈段之间的空闲空间，共享段和动态链接库占用的空间） 多次性:虚拟存储器在实现上需要将一个作业分多次装入内存运行 对换性：虚拟存储的调入和调出是对部分虚拟地址空间进行的； 虚拟性：通过物理内存和快速外存相结合，提供大范围的虚拟地址空间,从逻辑上扩充内存容量,4.4.1请求分页虚拟存储管理,基本思想：在进程开始执行之前，首先从外存将进程的一部分装入内存开始执行，在执行过程中若发现要访问的数据或指令不在内

30、存，便由硬件产生缺页中断信息，动态地装入相应的页面。当内存无空闲块或分配给该进程的物理块已用完，而有新的页面需要装入时，根据某种置换算法淘汰已在内存的某个页面，装入新的页面，进程继续运行。,动态地址重定位,请求分页中的硬件支持,1. 页表机制,需要在进程页表中添加若干项 状态位(present bit）：指示该页是否在内存，状态位为0，该页不在内存，状态位为1，该也在内存。 引用位 ：用于标志页面在内存时是否被访问；置换算法换出页面时作为参考 修改位(modified bit) ：指示该页调入内存是否被修改过。 外存地址：用于指出该页在外存的地址，供调入该页时使用。,在简单页式存储管理的基础上

31、，增加请求调页和页面置换功能。,请求分页存储管理中的地址重定位和缺页中断,由处理器的地址变换机构产生缺页中断，然后调用操作系统提供的中断处理例程。,缺页中断的特殊性,缺页中断的发生和处理在指令执行期间产生和进行处理，而不是在一条指令执行完毕之后。所缺的页面调入之后，重新执行被中断的指令。 一条指令的执行可能产生多次缺页中断,CPU都会及时处理。 发生缺页中断时应保存指令执行的中间结果。 对新分配的物理块应上锁，防止同一物理块分配给多个进程。,页面分配策略,操作系统为进程分配内存空间时，需要考虑的因素： （1）分配给一个进程的空间越小，内存中存放进程越多，减少进程交换时间。 （2）如果进程只有一

32、小部分在内存，缺页中断率会相当高。 （3）因为程序的局部性原理，分配给一个进程的主存超过一定限度后，再增加主存空间，也不会明显降低进程的缺页率。,在请页式系统中，可采用两种策略分配页框给进程：固定分配和可变分配。 固定分配：如果进程生命周期中，保持页框数固定不变，各进程平均分配，根据程序大小按比例分配，优先权。 可变分配：如果进程生命周期中，页框数目 发生变化，按照缺页率动态调整（高或低增大或减小常驻集），性能较好。增加算法运行的开销。,内存置换策略,全局替换 将分配给所有进程的内存块固定,让所有进程共享这些内存块.如果有页面需要换入内存,系统会从所有的进程中选择合适的页面换出内存。可以在运行

33、进程之间动态地分配页框。 局部替换 如果页面置换算法的作用局限于本进程，当进程有页面需要换入内存时，只能从当前需要的页面的进程中选择页面换出到外存。,常驻集大小和置换范围的配合： 常驻集指虚拟页式管理中给进程分配的物理页面数目。 固定分配+局部置换：这时的主要问题进程开始前要依据进程类型决定分配多少页面。多了会影响并发水平，少了会使缺页率过高。 可变分配+全局置换：这是采用较多的的一种分配和替换算法，这时OS会一直维持一定数目的空闲页面，添加到它的驻留集中，增加中断进程的主存空间，以降低缺页率，这时的主要问题是置换策略的选择，如何决定哪个进程的页面将被调出。较好的选择是页面缓冲算法。 可变分配

34、+局部置换：新进程装入主存时，根据应用类型、程序要求，分配一定数目的页框，可用请页式或预调式完成这个分配，当产生缺页中断时，从产生缺页中断的进程的驻留集中选一个页面替换，连续评价新进程的分配，增加或减少分配给进程的页框以改善系统的性能。,分页虚拟存储的调入策略、分配策略,请求页调入 (demand paging)：只调入发生缺页时所需的页面。 优点：容易实现。 缺点：对外存I/O次数多，开销较大 预先页调入 (prepaging)：在发生缺页需要调入某页时，一次调入该页以及相邻的几个页。 优点：提高调页的I/O效率。 缺点：基于预测，若调入的页在以后很少被访问，则效率低。常用于程序装入时的调页

35、。,返回,1. 调入策略 (fetch policy),调入策略确定在外存中的页面调入时机。在虚拟页式管理中有两种常用策略。,2. 从何处调入页面,在请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。通常，由于对换区是采用连续分配方式，而事件是采用离散分配方式，故对换区的磁盘I/O速度比文件区的高。这样，每当发生缺页请求时，系统应从何处将缺页调入内存，可分成如下三种情况： (1) 系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以提高调页速度。为此，在进程运行前， 需要将与该进程有关的文件，从文件区拷贝到对换区。,(2) 系统缺少足够的对换区空间，这时

36、凡是不会被修改的文件，都直接从文件区调入；而当换出这些页面时，由于它们未被修改而不必再将它们换出，以后再调入时，仍从文件区直接调入。但对于那些可能被修改的部分，在将它们换出时，便须调到对换区，以后需要时，再从对换区调入。 (3) UNIX方式。由于与进程有关的文件都放在文件区，故未运行过的页面，都应从文件区调入。而对于曾经运行过但又被换出的页面，由于是被放在对换区，因此在下次调入时，应从对换区调入。由于UNIX系统允许页面共享，因此，某进程所请求的页面有可能已被其它进程调入内存，此时也就无须再从对换区调入。,3. 页面调入过程 每当程序所要访问的页面未在内存时，便向CPU发出一缺页中断，中断处

37、理程序首先保留CPU环境，分析中断原因后， 转入缺页中断处理程序。该程序通过查找页表，得到该页在外存的物理块后， 如果此时内存能容纳新页，则启动磁盘I/O,将所缺的页调入内存，然后修改页表。如果内存已满，则须先按照某种置换算法从内存中选出一页准备换出；如果该页未被修改过，可不必将该页写回磁盘；但如果此页已被修改， 则必须将它写回磁盘，然后再把所缺的页调入内存， 并修改页表中的相应表项，置其存在位为“1”，并将此页表项写入快表中。在缺页调入内存后，利用修改后的页表，形成所要访问数据的物理地址，再去访问内存数据。,4.4.2页面置换算法,4.4.2.1 缺页率 4.4.2.2 页面置换算法,4.4

38、.2.1 缺页率(page fault rate),缺页率表示“缺页次数 / 内存访问次数”(比率)或“缺页的平均时间间隔的倒数”；是衡量页面置换算法的指标。 下面我们用到的是局部范围内的置换算法，即系统为每个作业规定最大的内存占有数，当已占满规定的内存块数而又有新页面调入时，就从自身空间中置换一个页面，不允许替换别的作业的页面。,4.4.2.2 页面置换算法,功能：需要调入页面时，选择内存中哪个物理页面被置换。 目标：把未来不再使用的或短期内较少使用的页面调出，通常只能在局部性原理指导下依据过去的统计数据进行预测。,返回,页面置换：把一个页面从内存调换到磁盘的对换区。,1. 最佳(Optim

39、al)置换算法 最佳置换算法所选择的被淘汰页面，选择“未来不再使用的”或“以后最长时间内不需要访问的页”或“在离当前最远位置上出现的”页面被置换。采用最佳置换算法，通常可保证获得最低的缺页率。 这是一种理想情况，是实际执行中无法预知的，因而不能实现。可用作性能评价的依据。,假定系统为某进程分配了三个物理块， 并考虑有以下的页面号引用串： 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予以淘汰。,2. 先进先出页面置换算法(F

40、IFO),选择最先进入内存或驻留时间最长的页面,应该首先被淘汰，性能较差。,进程P有5页程序访问页的顺序为：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5； 如果在内存中分配3个页面，则缺页情况如下：12次访问中有缺页9次；,如果在内存中分配4个页面，则缺页情况如下：12次访问中有缺页10次；,3. 最近最久未使用页面置换算法(LRU）,选择内存中最近一段时间最久未使用的页面被置换。这是局部性原理的合理近似，性能接近最佳算法。,LRU置换算法的硬件支持,(1) 计数器方式 为了记录某进程在内存中各页的使用情况，须为每个在内存中的进程的页表添加一项,用于记录该页已经使用过的

41、时间。每使用一次页面,逻辑时钟或计数器的内容被烤贝到页表时间记录中。,由于需要记录页面使用时间的先后关系，硬件开销太大,(2) 堆栈方式,用栈保存当前使用页面时栈的变化情况,把被访问的页面移到栈顶，于是栈底的是最久未使用页面。,4 Clock置换算法,1. 简单的Clock置换算法,2. 改进型Clock置换算法,由引用位R和修改位M可以组合成下面四种类型的页面： 1类(R=0, M=0): 表示该页最近既未被访问， 又未被修改， 是最佳淘汰页。 2类(R=0, M=1)： 表示该页最近未被访问， 但已被修改， 并不是很好的淘汰页。 3类(R=1, M=0)： 最近已被访问， 但未被修改， 该

42、页有可能再被访问。 4类(R=1, M=1): 最近已被访问且被修改， 该页可能再被访问。,其执行过程可分成以下三步： (1) 从指针所指示的当前位置开始， 扫描循环队列， 寻找R=0且M=0的第一类页面， 将所遇到的第一个页面作为所选中的淘汰页。 在第一次扫描期间不改变引用位R。 (2) 如果第一步失败，即查找一周后未遇到第一类页面， 则开始第二轮扫描，寻找R=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的引用位都置0。 (3) 如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的引用位复0。 然后重复第一步，如果仍

43、失败，必要时再重复第二步，此时就一定能找到被淘汰的页。,5. 置换算法举例,某程序在内存中分配三个页面，初始为空，页面走向为4，3，2，1，4，3，5，4，3，2，1，5。,缺页率的影响因素 页面大小： 页面很小页表大，页内碎片小，缺页率高 页面很大页表小，页内碎片大，缺页率低； 页面置换算法 程序设计的质量 设计程序时要求程序的局部化程度很高，这样缺页中断次数减少。 局部性原理包括时间局部化和空间局部化。 时间局部化：一条指令的一次执行和下次执行，一个数据的一次访问和下次访问都集中在一个较短时期内； 空间局部化：当前指令和邻近的几条指令，当前访问的数据和邻近的数据都集中在一个较小区域内。 分

44、配的内存块数： 数目越多缺页率越低。,4.4.3 请求分段存储管方式,在简单段式存储管理的基础上，增加请求调段和段置换功能。段式逻辑地址空间中的程序段在运行时并不全部装入内存，只是首先调入一个或若干个程序段运行，在运行过程中调用到哪段时，根据该段长度在内存分配一个连续的空间给他使用。若内存没有足够大的空闲分区，则考虑进行紧凑或将某些段淘汰出去。请求分段存储管理的内存分配也可采用最佳适应算法、首次适应法和最差适应算法。,返回,返回,31 16 15 0,分段存储管理中的逻辑地址具有如下结构：,段表,内存分配: 以段为单位分配,每段各占一块内存区,各段可以离散的放入内存.,段表,为了实现动态地址变

45、换和存储保护，系统为每一个作业建立一张段表。 需要在进程段表中添加若干项： 状态位：该程序段是否在内存； 引用位：该程序段最近是否被访问过； 改变位：该程序段在内存是否被修改过 存取权限：如读R，写W，执行E，增补位A； 起始地址：若该程序段在内存，存放该段在内存的起始地址;若该程序段在外存，存放该段在外存的起始地址。 地址变换和缺段中断：指令和操作数必定不会跨越在段边界上,请求分页和请求分段存储管理地址变换的区别,（1）请求分页存储管理的作业地址空间是一个单一的线性地址空间；而分段存储管理的作业地址空间是二维的地址空间。 （2）请求分页存储管理中，页面大小是固定的，对于分页活动，用户是不可见

46、的，分段存储管理中，段的大小是不定的，是信息的逻辑单位，用户是可见的。 （3）请求分页存储管理中，把程序地址分为页号P和页内位移量W是硬件完成的，分段存储管理中，把程序地址分成段号S和断内位移量d是逻辑功能。,段页式存储管理,段页式存储管理是目前使用较多的一种存储管理方式，它具备分页存储管理和分段存储管理的优点。 （1）作业地址空间进行段式管理，即将作业地址空间分成若干个逻辑段，每段都有自己的段名。 （2）每段内再分成若干个大小固定的页，每段都从0开始为自己的各页依次编写连续的页号。 （3）将内存空间分成若干个大小固定的物理块，对内存空间的分配是以物理块为单位的。 （4）作业的逻辑地址包括：段

47、号，页号，页内位移。,（5）为实现地址变换，段页式系统建立了段表和页表，系统为每个作业建立一张段表，并为每个段建立一张页表。地址变换：先查段表，再查该段的页表。 段页式存储管理中，若段表和页表都在内存，则访问内存中的某一条指令或数据，需要访问内存3次。,返回,4.5 碎片与抖动,解决碎片问题比较好的办法是采用分页技术，每个作业调入内存时，除最后一页可能会出现页内碎片，其余页不存在碎片问题。 抖动：在具有虚存的计算机，如果置换算法不当，就有可能出现某些页刚被置换出去又要马上访问的情况，因而要将其调入，而调回后不久又要被置换出去，这样不断反复，引起系统效率降低的一种现象。抖动问题与程序的执行特性有

48、关，也与置换算法有关。抖动现象可使整个的系统的页面置换非常频繁，以致大部分的机器时间花费在来回进行页面置换上，避免抖动现象最根本的方法是控制多道程序的道数，使得每个作业都有足够的内存空间可以使用，又不会影响处理机的利用率。,工作集策略,工作集是一个进程执行过程中所访问页面的集合，可用一个二元函数W(t, )表示 t是执行时刻； 是一个虚拟时间段，称为工作集窗口 (window size) | W(t, ) | 指工作集大小即页面数目；,1968年由Denning提出，引入工作集的目的是依据进程在过去的一段时间内访问的页面来调整常驻集大小。,驻留集,正确选择驻留集窗口大小： 窗口大小选择得过小，频繁产生缺页中断。 窗口大小选择得很大，失去了虚拟存储器的意义。,工作集：即在某段时间间隔内，进程实际要访问的页面的集合。,小结,引言：存储组织（层次），存储管理功能 重定位 固定分区存储管理、可变分区存储管理 页式和段式存储管理：原理，优缺点，数据结构，地址变换，分段的意义，两者比较 虚拟存储器： 局部性原理，虚拟存储器的原理 种类（虚拟页式、段式、段页式），缺页中断 置换策略,