《操作系统概论-3存储器管理》由会员分享，可在线阅读，更多相关《操作系统概论-3存储器管理（98页珍藏版）》请在金锄头文库上搜索。
1、第三章 存储管理操作系统概论1主要内容3.1计算机系统中的存储器3.2重定位3.3单用户连续存储管理3.4固定分区存储管理3.5可变分区存储管理3.6页式虚拟存储管理23.1 计算机系统中的存储器存储器storage,memmory能接收数据和保存数据、而且能根据命令提供这些数据的装置主存 系统区 (OS标准子程序)用户区(用户程序、数据)存储器的层次结构存储器的层次结构存储器主存储器和高速缓冲存储器辅存(外存)硬盘、光盘、磁带、软盘寄存器外存(secondary storage)DOS核心命令处理程序内存(primary storage)高速缓存(cache)寄存器(register)33.
2、1 计算机系统中的存储器存储器分成三个层次存储器分成三个层次主存储器（内存、主存）主存储器（内存、主存）处理机能直接访问的存储器。存储容量较大，存取速度也较快，存储单元以字节为单位进行编址。用来存放系统和用户的程序和数据，其存储方式是以新换旧，断电信息丢失。高速缓冲存储器高速缓冲存储器处理机能直接访问的存储器。存取速度快于主存，存储容量较小。用来存放主存中经常要被访问的信息。辅助存储器(外存、辅存)处理机不能直接访问的存储器。存储容量很大，可用来长期保存用户信息（如程序、数据、执行的结果等），但处理器不能直接读/写辅助存储器上的信息，必须在输入输出控制系统的管理下，才能够使辅助存储器与主存之间
3、相互传送信息。寄存器寄存器处理机能直接访问的存储器。存取速度最快，但容量小，一般每个寄存器只能存储一个字长的信息。用来存放临时的工作数据和控制信息。常用的寄存器主要有：指令寄存器、通用寄存器、控制寄存器等。寄存器不存在分配问题，但主存和辅存中经常存放多个程序和数据，会发生竞争的现象，因此要合理的分配和使用。43.1 计算机系统中的存储器存储管理的功能存储管理的功能对主存储器中的用户区域进行管理，包括：对主存储器中的用户区域进行管理，包括：(1)(1)地址转换地址转换 ( (地址映射、地址重定位地址映射、地址重定位) )把程序的逻辑地址变换为存储器的物理地址的过程。地址转换的方式有静态重定位和动
4、态重定位。 (2)(2)主存空间的分配与回收主存空间的分配与回收为多个程序分配内存空间，各程序在规定的那一部分内存空间里运行。程序运行完毕时，回收相应的内存空间。(3)(3)主存空间的主存空间的共享与保护共享与保护对OS以及各用户的信息提供保护措施。 (4)(4)主存空间的的扩充（提供虚拟存储技术）主存空间的的扩充（提供虚拟存储技术） 使用户程序的大小和结构不受主存容量和结构的限制，即使在用户程序比实际主存容量还要大的情况下，程序也能正确运行。存储器管理的基本目的存储器管理的基本目的是：充分发挥内存的利用率；为用户使用存储器提供方便。 53.2重定位重定位内存的物理组织内存的物理组织物理地址：
5、把内存分成若干个大小相等的存储单元，每个单元给一个编号，这个编号称为内存地址（物理地址、绝对地址、实地址），存储单元占8位，称作字节（byte）。物理地址空间：物理地址的集合称为物理地址空间（主存地址空间），它是一个一维的线性空间。63.2重定位重定位程序的逻辑结构程序的逻辑结构程序地址：用户编制程序时所用的地址（或称相对地址、逻辑地址、虚地址）。源程序经过汇编或编译后再经过链接形成程序的装配模块形式，即转换为相对地址编址形式，它是以0为基址顺序进行编址的。程序地址空间（相对地址空间、逻辑地址空间、虚地址空间）:是逻辑地址的集合，它的编址总是从0开始的，可以是一维线性空间，也可以是多维空间。7
6、3.2重定位重定位程序的逻辑结构程序的逻辑结构物理存储器的结构是个一维的线性空间，容量是有限的。用户程序结构：一维空间一维空间一个用户程序就是一个程序，并且程序和数据是不分离的；二维空间二维空间程序由主程序和若干个子程序（或函数）组成，并且程序与数据是分离的；n维空间维空间即一个大型程序，由一个主模块和多个子模块组成，其中，各子模块又由主程序和子程序（或函数）组成。用户程序的大小，可能比内存容量小，也可能比内存容量大，有时候要大得多。83.2重定位重定位程序的装入和链接程序的装入和链接在多道程序环境下，程序要运行必须为之创建进程，而创建进程的第一件事，就是要将程序和数据装入内存。如何将一个用户
7、源程序变为一个可在内存中执行的程序？通常要经过以下几步：(1)编译编译由编译程序（Compiler）将用户源代码编译成若干个目标模块（ObjectModule）；(2)链接链接由链接程序（Linker）将编译后形成的目标模块以及它们所需要的库函数，链接在一起，形成一个装入模块（LoadModule）；(3)装入装入由装入程序（Loader）将装入模块装入内存。93.2重定位重定位程序的链接程序的链接根据链接时间的不同，可把链接分成如下三种：1.静态链接(static-linking)2.装入时动态链接(dynamic-linking)3.运行时动态链接(dynamic-linking)103.
8、2重定位重定位程序的链接程序的链接 1. 1. 静态链接静态链接(static-linking)(static-linking)静态链接静态链接是在程序运行之前，先将目标模块及它们所需的库函数，链接成一个完整的装配模块，以后不再拆开。这种方式形成的一个完整的装入模块又称为可执行文件可执行文件。Module AModule Acall function10L-1Module BModule B0M-1function1().function1FModule AModule AJSR L+F0L-1Module BModule BLL+M-1function1().function1L+F113.
9、2重定位重定位程序的链接程序的链接2.2.装入时动态链接装入时动态链接(dynamic-linking)(dynamic-linking)将编译后所得的一组目标模块，在装入内存时边装入边进行链接。即在装入一个目标模块时，若发生一个外部模块调用事件，将引起装入程序去找出相应的外部目标模块，并将它装入内存，以及修改目标模块中的相对地址。通常被链接的共享代码称为动态链接库(DLL,Dynamic-LinkLibrary)或共享库(sharedlibrary)。123.2重定位重定位程序的链接程序的链接3.3.运行时动态链接运行时动态链接(dynamic-linking)(dynamic-linkin
10、g)将对某些模块的链接推迟到运行时才执行。即在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存，把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上。133.2重定位重定位程序的链接程序的链接动态链接的优缺点动态链接的优缺点优点：共享：多个进程可以共用一个DLL，节省内存，减少文件交换。部分装入：一个进程可以将多种操作分散在不同的DLL中实现，而只将当前操作相应的DLL装入内存。便于局部代码修改：即便于代码升级和代码重用；只要函数的接口参数（输入和输出）不变，则修改函数及其DLL，无需对可执行文件重新编译或链接。便于
11、运行环境适应：调用不同的DLL，就可以适应多种使用环境和提供不同功能。如：不同的显示卡只需厂商为其提供特定的DLL，而OS和应用程序不必修改。缺点：链接开销：增加了程序执行时的链接开销；管理开销：程序由多个文件组成，增加管理复杂度。143.2重定位重定位 程序的装入程序的装入一、绝对装入方式一、绝对装入方式(Absolute Loading Mode)绝对装入程序按照装入模块中的逻辑地址，将程序和数据装入内存。装入模块被装入内存后，由于装入模块中的逻辑地址与实际物理地址完全相同，因此不须对程序和数据的地址进行修改。优点：装入过程简单，不需要硬件的支持。缺点：只能将装入模块装入到内存中事先指定的
12、位置，因此只能用于单用户、单任务的操作系统，不适于多道程序系统(此环境下，编译程序不可能预知所编译的目标模块应放在内存的何处)。装入模块在系统中是不能做任何移动的，否则就会出错。153.2重定位重定位 程序的装入程序的装入二、可重定位装入方式二、可重定位装入方式(Relocation Loading Mode)（亦称静态地址重定位）（亦称静态地址重定位）由装入程序根据内存中当前的实际使用情况将装入模块装入到内存中某个适当位置。在程序装入内存时完成从逻辑地址到物理地址的转换。即装入程序将程序中的逻辑地址与本程序在内存中的起始地址相加得到正确的物理地址，将程序和数据装入内存。由于程序中的逻辑地址是
13、从0开始编址的，因此需要对程序中指令和数据的地址进行修改，这种由于一个作业装入到与其逻辑地址空间不一致的绝对地址空间，使得逻辑地址与绝对地址不同，而引起的对有关地址部分的调整，即逻辑地址转换成绝对地址的过程称为重定位重定位，也称为地址转换地址转换。可重定位装入方式是在装入一个作业的时候，把作业中的指令地址和数据地址全部一次性地转换成绝对地址，以后不再改变。故称为静态地址重定位静态地址重定位。163.2重定位重定位 程序的装入程序的装入二、可重定位装入方式二、可重定位装入方式(Relocation Loading Mode)（亦称静态地址重定位）（亦称静态地址重定位）优点：优点：实现简单，不需要
14、硬件的支持。缺点：缺点：程序一旦装入内存，移动就比较困难。有时间上的浪费。在程序装入内存时要将所有访问内存的地址转换成物理地址。173.2重定位重定位 程序的装入程序的装入三、动态运行时装入方式（三、动态运行时装入方式（Dynamic Run-Time LoadingDynamic Run-Time Loading） （亦称动态地址重定位）（亦称动态地址重定位）在程序运行时完成从逻辑地址到物理地址的转换，靠硬件地址变换机在程序运行时完成从逻辑地址到物理地址的转换，靠硬件地址变换机构实现。构实现。即装入程序在把程序(装入模块)装入内存后，并不立即把程序中的逻辑地址转换为物理地址，而是把这种地址转
15、换推迟到程序真正要执行时才进行。最简单的办法是利用一个基址基址( (重定位重定位) )寄存器寄存器。在程序实际运行前，由操作系统把程序在内存的起始地址送入基址寄存器。在程序运行期间，凡遇到访问内存的操作，就由硬件机制自动地把用户程序的逻辑地址与基址寄存器的内容相加，其和就是实际访问内存的有效地址。所谓动态重定位动态重定位是由软件和硬件相配合来实现的。地址重定位不再是装入的时候一次完成了，而是设置一个基址寄存器，装入作业的时候，将作业在主存区域的首地址放入到基址寄存器中。作业执行的时候，由硬件的地址转换机构动态地对地址进行转换，执行指令的时候，只要将逻辑地址加上基址寄存器的内容，就得到了绝对地址
16、。183.2重定位重定位 程序的装入程序的装入三、动态运行时装入方式（三、动态运行时装入方式（Dynamic Run-Time LoadingDynamic Run-Time Loading） （亦称动态地址重定位）（亦称动态地址重定位）193.2重定位重定位 程序的装入程序的装入三、动态运行时装入方式（三、动态运行时装入方式（Dynamic Run-Time LoadingDynamic Run-Time Loading） （亦称动态地址重定位）（亦称动态地址重定位）动态地址重定位是由硬件机制在程序执行时完成的，程序中不执行的模块就不做地址映射的工作，这样节省了CPU的时间。重定位寄存器的内
17、容由OS用特权指令来设置，比较灵活。动态地址重定位适合于多道程序运行环境，并且允许目标程序在内存中浮动。现代计算机系统中都采用动态地址映射技术。动态地址映射技术能满足以下目标：(1)具有给一个用户程序任意分配内存区的能力；(2)可实现虚拟存储；(3)具有重新分配的能力；(4)对于一个用户程序，可以分配到多个不同的存储区。203.2重定位重定位 静态地址重定位和动态地址重定位的区别静态地址重定位和动态地址重定位的区别静态重定位是在作业装入的时候一次完成，动态重定位是在作业执行时再实现的。静态重定位是软件支持的，动态重定位是硬件和软件合作实现的。静态重定位不能实现主存的移动，而动态重定位可以。动态
18、重定位还可能提供虚拟存储空间。213.3单用户连续存储管理单用户连续存储管理连续分配连续分配是指为一个用户程序分配一个连续的内存空间，有四种方式，即单用户连续分配方式单用户连续分配方式固定分区分配方式固定分区分配方式可变可变(动态动态)分区分配方式分区分配方式连续分配存储管理方式连续分配存储管理方式(分区存储管理分区存储管理)223.3单用户连续存储管理单用户连续存储管理单用户连续分配方式只能用于单道运行的计算机系统（单用户、单任务的操作系统）。原理原理：内存分为系统区和用户区。系统区仅提供给操作系统使用；用户区指除系统区以外的全部内存空间，都分配给一个作业使用，即在任何时刻主存储器中最多只有
19、一个作业在任何时刻主存储器中最多只有一个作业。等待装入主存储器的作业排成一个作业队列，当主存储器中等待装入主存储器的作业排成一个作业队列，当主存储器中无作业或一个作业执行结束，可允许作业队列中的一个作业无作业或一个作业执行结束，可允许作业队列中的一个作业装到主存储器。作业总是被装到由界限寄存器指示的用户区装到主存储器。作业总是被装到由界限寄存器指示的用户区的起始地址开始的区域。的起始地址开始的区域。233.3单用户连续存储管理单用户连续存储管理地址转换地址转换：采用静态地址重定位方式进行地址转换。地址重定位时，只要将指令或数据的逻辑地址加上界限寄存器指示的用户区的起始地址，就可以形成物理地址。
20、 存储保护存储保护：处理器设置一个界限寄存器，其内容为当前可供用户使用的主存区域的起始地址。处理器在执行指令时要检查界限地址指令的绝对地址最大地址若指令的绝对地址在规定的范围内，则可执行，否则产生一个“地址越界”中断事件，由操作系统进行处理，以达到存储保护的目的。243.4 3.4 固定分区存储管理固定分区存储管理( (分区大小、个数均固定分区大小、个数均固定) )固定分区存储管理适用于多道程序设计系统。原理：原理：把主存中可分配的用户区域预先划分成若干个连续区，每一个连续区称为一个分区，各个分区可以大小相等，也可以大小不等。一旦划分好后，主存中分区的个数和每个分区的大小就固定了。每个分区可以
21、装入一个作业，这样当内存划分成几个分区时，便允许几个作业并发运行，但不允许多个作业同时在一个分区中。当有一个分区空闲时，便可从外存的后备队列中，选择一个适当大小的作业装入该分区；当该作业运行结束时，又可从后备队列中找出另一个作业调入该分区。v分区大小相等：只适合于多个相同程序的并发执行（处理多个类型相同的对象）。v分区大小不等：多个小分区、适量的中等分区、少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区。253.4 3.4 固定分区存储管理固定分区存储管理( (分区大小、个数均固定分区大小、个数均固定) )原理（分配与回收）原理（分配与回收）为了便于内存分配，通常将这些分区根据它们
22、的大小进行排队，并为之建立一张分区分配表分区分配表。每个表项包括该分区的起始地址、长度（大小）及标志位(是否已分配，如”0“表示空闲；非”0“表示已分配)。分配：作业队列中有作业要装入分区，存储管理分配主存区域时，先查分区分配表，选择标志为”0“的分区。然后根据作业地址空间的长度与标志为”0“有分区的长度比较，当有适当大小的分区时，把作业装入该分区，且把作业名填到占用标志位上。如果没有适当大小的分区，则该分区暂时不能装入。即当有作业要装入分区时，由存储管理程序检索分区分配表，从中找出一个能满足要求的、尚未分配的分区，将它分配给该作业，然后修改分区使用表中的标志位为作业名；若找不到大小足够的分区
23、，则拒绝为该程序分配内存。回收：作业运行结束时，根据作业名查分区分配表，从占用标志位的记录可知该作业占用的分区，把该分区的占用标志置成”0“，表示该分区现在空闲了。263.4 3.4 固定分区存储管理固定分区存储管理( (分区大小、个数均固定分区大小、个数均固定) )地址转换地址转换：采用静态地址重定位方式进行地址转换。地址重定位时，只要将指令或数据的逻辑地址加上作业所在分区的起始地址，就可以形成物理地址。 存储保护存储保护：处理器设置一对寄存器，即上限寄存器和下限寄存器上限寄存器和下限寄存器，其内容为当前占用CPU运行的作业所在分区的上限地址和下限地址。当一个已经被装入主存的作业得到处理器运
24、行时，进程调度应记录当前运行作业所在的分区号，且把分区的上限地址和下限地址分别送上限寄存器和下限寄存器中。处理器在执行该作业的指令时要检查下限地址指令的绝对地址上限地址若指令的绝对地址在规定的范围内，则可执行，否则产生一个“地址越界”中断事件，由操作系统进行处理，以达到存储保护的目的。273.4 3.4 固定分区存储管理固定分区存储管理( (分区大小、个数均固定分区大小、个数均固定) )283.4 3.4 固定分区存储管理固定分区存储管理( (分区大小、个数均固定分区大小、个数均固定) )优点优点：固定分区方式是最简单的多道程序的存储管理方式，对微型机多用户系统，采用这种方式管理是适宜的。缺点
25、缺点：由于每个分区的大小固定，必然会造成存储空间的浪费，降低主存空间的利用率；而且，程序大小受分区空间大小的限制。为了提高主存空间的利用率，可以采用一定和措施（见P43-44）。293.4 3.4 固定分区存储管理固定分区存储管理( (分区大小、个数均固定分区大小、个数均固定) )例：某系统采用固定分区存储管理，内存空间为640KB，其中0地址到40K被系统占用，其他按分区大小相等的方法划为4个分区，则当有大小分别为7KB、90KB、30KB、20KB的作业进入内存时，浪费的内存为A、3KBB、450KBC、453KBD、147KB303.5 3.5 可变分区存储管理可变分区存储管理可变（动态
26、）分区分配是根据作业的实际需求量，动态地为之分配连续的内存空间，是在作业要求装入主存时，根据作业需要的主存空间大小和当时主存空间使用情况来决定是否为作业分配一个分区。原理：系统生成后，操作系统占用内存的一部分，一般在物理内存的开始处，比如，一个操作系统占20KB，装入系统后占用020KB的内存空间，整个用户区（剩下的部分）作为一个大的空闲区。当有作业要装入主存时，根据作业对主存空间的需要量，从空闲区中划出一个与作业长度一致的分区（一般是这个空闲区的低地址部分的区域）来装入作业，剩余部分仍为空闲区。313.5 3.5 可变分区存储管理可变分区存储管理当有作业完成后释放所占用的存储区。在系统运行的
27、过程中，系统中形成多个空闲的不连续的存储区，称主空闲。323.5 3.5 可变分区存储管理可变分区存储管理可变（动态）分区存储管理技术的实现：1、地址转换与存储保护2、可变分区存储管理的机构（数据结构）3、分区的分配和回收4、四种基本的分配算法(放置策略)333.5 3.5 可变分区存储管理可变分区存储管理一动态分区分配中的地址转换与存储保护一动态分区分配中的地址转换与存储保护地址转换地址转换：采用动态地址重定位方式进行地址转换，要有硬件的地址转换机构作支持。硬件设置两个专用的控制寄存器：基址寄存器（其内容为当前占用CPU运行的作业所占分区的起始地址）和限长寄存器（其内容为当前占用CPU运行的
28、作业所占分区的最大地址），以及一些加法线路、比较线路等。地址重定位时，由硬件的地址转换把逻辑地址转换成绝对地址，即将指令或数据的逻辑地址加上基址寄存器的内容，形成物理地址。 343.5 3.5 可变分区存储管理可变分区存储管理一动态分区分配中的地址转换与存储保护一动态分区分配中的地址转换与存储保护存储保护存储保护：当一个进程（或程序、作业）得到处理器运行时，进程调度便把该作业的所占分区的起始地址送入基址寄存器，把作业所占分区的最大地址送入限长寄存器，在该进程运行的过程中实现动态地址重定位。处理器在执行该作业的指令时要检查基址寄存器的内容指令的绝对地址限长寄存器的内容若指令的绝对地址在规定的范围
29、内，则可执行，否则产生一个“地址越界”中断事件，由操作系统进行处理，以达到存储保护的目的。353.5 3.5 可变分区存储管理可变分区存储管理二分区分配中的数据结构二分区分配中的数据结构 为了实现分区分配，系统中必须设置相应的数据结构，如已分配分区表和空闲分区表(或空闲分区链)，用来描述已分配分区和空闲分区的情况，记录内存的使用情况，为内存分配提供依据。363.5 3.5 可变分区存储管理可变分区存储管理二分区分配中的数据结构二分区分配中的数据结构空闲分区链在分区起始部分，设置一些控制分区分配的信息(分区大小和状态位)以及用于链接各分区的前向指针；在分区结尾部分，重复设置分区大小和状态位，另设
30、置一后向指针。通过前、后向链接指针，可将所有的空闲分区链接成一个双向链。当分区被分配出去后，把状态位由“0”改为“1”，此时前、后向指针无意义。373.5 3.5 可变分区存储管理可变分区存储管理三分区分配和回收三分区分配和回收38393.5 3.5 可变分区存储管理可变分区存储管理三分区分配和回收三分区分配和回收403.5 3.5 可变分区存储管理可变分区存储管理三分区分配和回收三分区分配和回收41423.5 3.5 可变分区存储管理可变分区存储管理四分区分配算法四分区分配算法分区分配和回收是对空闲分区表(或空闲分区链)数据结构进行相应的操作。教材上的分配算法是以空闲分区表的数据结构进行分配
31、。为把一个新作业装入内存，须按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业。注：1、分配算法中切割空闲区是从低地址开始的，例如，一个空闲区大小是100KB，首址是230KB，一申请者要求80KB，分配时将从230KB开始的80KB分配给申请者，剩下的部分仍作为一个空闲区，其首址是310KB，大小是20KB。2、门限值(事先规定的不再切割的剩余分区的大小)是切割空闲区后剩下的区域若小于门限值，就不切割该空闲区，统统分给申请者。433.5 3.5 可变分区存储管理可变分区存储管理四分区分配算法四分区分配算法空闲分区表的组织有两种方法：1、按空闲区大小的升序（降序）组织；2、按
32、空闲区首址升序（降序）组织。根据空闲分区表组织的方法的不同，有不同的分配算法(放置策略)：最先适应算法最先适应算法(FF)循环首次适应算法循环首次适应算法(CFF)最优适应算法最优适应算法(BF)最坏适应算法最坏适应算法( (WF)443.5 3.5 可变分区存储管理可变分区存储管理四分区分配算法四分区分配算法在最最先先（首首次次）适适应应算算法法中，空闲分区按地址递增的顺序形成空闲分区表，分配时从空闲分区表的第一个空闲分区开始向后扫描，直到找到第一个能满足需要的空闲分区为止；然后再按照作业的大小，从该分区中划出一块内存空间分配给作业，余下的空闲区仍留在空闲表中。优优点点：该算法倾向于优先利用
33、内存中低地址部分空闲区，从而保留了高地址部分大的空闲区，这会给以后到达的大作业分配大的内存空间创造条件。分区合并较简单。缺缺点点：低地址部分会留下许多难以利用的小空闲区（称为碎碎片片），而每次查找又都从低地址部分开始，增加了开销。45空闲分区链最先适应算法最先适应算法463.5 3.5 可变分区存储管理可变分区存储管理四分区分配算法四分区分配算法在循循环环首首次次适适应应算算法法中，空闲分区也按地址递增的顺序形成空闲分区表，分配时不是从空闲分区表的第一个空闲分区开始，而是从上一次找到的空闲分区的下一个空闲分区开始向后扫描，直到找到第一个能满足需要的空闲分区，从该分区中划出一块与请求大小相等的内
34、存空间分配给作业。为实现该算法，应设置一起始查找指针，用于指示下一次起始查寻的空闲分区，并采用循环查找方法。该算法可以使得小的空闲区均匀地分布在可用存储空间中，当回收时，与大的空闲区合并的机会增加。但保留大的空闲区的可能性减小了。473.5 3.5 可变分区存储管理可变分区存储管理四分区分配算法四分区分配算法在最最优优适适应应算算法法中，空闲分区按容量大小递增的顺序形成空闲分区表，分配时从空闲分区表的第一个空闲分区开始向后扫描，直到找到第一个能满足需要的空闲分区，很显然该分区是满足需要而且是最接近需要的空闲分区。(所谓最优是指每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业
35、。)该算法可以保留大的空闲区，但会留下许多小的空闲区（碎片）。而且空闲区回收也更复杂一些。48空闲分区链最优适应算法最优适应算法493.5 3.5 可变分区存储管理可变分区存储管理四分区分配算法四分区分配算法在最最坏坏( (差差) )适适应应算算法法中，空闲分区按容量大小递减的顺序形成空闲分区表，分配时直接从空闲分区表的第一个空闲分区中分配（不能满足需要则不分配）。如果第一个空闲分区不能满足需要，则再没有空闲分区能满足需要。该算法克服了最优适应算法留下许多小的碎片的不足，但保留大的空闲区的可能性减小了，而且空闲区回收也和最优适应算法一样复杂。50空闲分区链513.5 3.5 可变分区存储管理可
36、变分区存储管理四分区分配算法四分区分配算法这四种分配算法的优劣很难区分，要具体情况具体分析。例如：某时刻系统中有三个空闲区其大小和首址为：(35KB，100KB)、(12KB，156KB)、(28KB，200KB)有一作业系列：(JOB1，12KB)、(JOB2，30KB)、(JOB3，28KB)52最先适应算法最先适应算法最优适应算法最优适应算法533.5 3.5 可变分区存储管理可变分区存储管理3.5.3 3.5.3 移动移动( (拼接拼接) )技术技术（可重定位分区存储管理）可重定位分区存储管理）可变（动态）分区解决了固定分区空间浪费严重的问题。但在连续分配方式中必须把一个程序装人到一个
37、连续的内存空间，这样就会形成许多“碎片碎片”或“零头零头”(即不能被利用不连续的小空闲分区)。可通过移动移动内存中作业的方法将碎片拼接成一个可用的大块空间，以满足大作业的需要，这种方法也称为“拼拼接接”或“紧凑紧凑”。把作业从一个存储区域移到另一个存储区域的工作称为移动（拼接移动（拼接 、紧凑）、紧凑） 。紧凑后必须对移动了的程序或数据进行重定位。由此形成了“可重定位分区分配可重定位分区分配”。紧凑要移动大量信息花去不少处理机时间,代价很高。543.5 3.5 可变分区存储管理可变分区存储管理3.5.3 3.5.3 移动移动( (拼接拼接) )技术技术（可重定位分区存储管理）可重定位分区存储管
38、理）可重定位分区分配与可变（动态）分区分配基本上相同，差别仅在于：前者增加了移动（紧凑）功能，通常，在找不到足够大的空闲分区来满足用户需求时进行紧凑。553.5 3.5 可变分区存储管理可变分区存储管理3.5.3 3.5.3 移动移动( (拼接拼接) )技术技术（可重定位分区存储管理）可重定位分区存储管理）采用移动（拼接移动（拼接 、紧凑）、紧凑）技术的目的：集中分散的空闲区便于作业动态扩充主存采用移动（拼接移动（拼接 、紧凑）、紧凑）技术须注意的问题：移动会增加系统开销。移动是有条件的。56习题(1)对如图所示的内存情况(其中，阴影部分表示已占用块，空白部分表示空闲块)，若要申请一块40KB
39、的内存，对于最优适应分配策略给出分配区域的首地址是A、110KBB、190KBC、330KBD、410KB(2)在右图中，若若要申请一块40KB的内存，使首地址最大的分配策略是A、最先适应分配策略B、最优适应分配策略C、最坏适应分配策略D、单一连续区分配策略0KB100KB180KB190KB280KB330KB390KB410KB512KB-1B57习题(3)某动态分区存储管理系统，一时刻(系统刚把始址为130K的一小块内存分配出去)内存空闲分区情况如下表所示：序号分区大小(KB)分区始址(KB)18050275150355250490350有一作业申请50KB内存，系统把第2个空闲分区分配
40、给了该作业，则该系统采用的分区分配算法是A、最先适应算法B、最优适应算法C、循环首次适应算法D、其他算法58习题某系统采取可变分区存储管理技术，某时刻在内存有三个空闲分区，它们的首地址和大小分别是：空闲区1(100KB，10KB)，空闲区2(200KB，30KB)，空闲区3(300KB，15KB)。现有如下作业序列：作业1需求15KB，作业2需求16KB，作业1需求10KB。要求：(1)画出该时刻内存分配图。(2)用最先适应算法和最优适应算法画出此时的空闲区表结构。(3)画出用最先适应算法和最优适应算法对作业序列进行内存分配的过程。59覆盖和对换技术覆盖和对换技术 覆盖技术覆盖技术( (解决小
41、内存运行大作业解决小内存运行大作业) )覆覆盖盖技技术术是在程序运行过程中，把同一存储区在不同时刻分配给不同的程序段或数据段来共享的一种存储分配技术。其目标是在较小的可用内存中运行较大的程序。常用于多道程序系统，与分区存储管理配合使用。原原理理：一个程序的几个代码段或数据段，按照时间先后来占用公共的内存空间。将程序的必要部分（常用功能）的代码和数据常驻内存；可选部分（不常用功能）在其他程序模块中实现，平时存放在外存中（覆盖文件），在需要用到时才装入到内存；不存在调用关系的模块不必同时装入到内存，从而可以相互覆盖。(即不同时用的模块可共用一个分区)使用覆盖技术要求程序员必须小心地设计程序及其数据
42、结构，使得要覆盖的段（块）具有相对独立性，不存在直接联系或相互交叉访问。60覆盖和对换技术覆盖和对换技术 覆盖技术覆盖技术( (解决小内存运行大作业解决小内存运行大作业) )注：另一种覆盖方法：(100K)A(20K)占一个分区：20K；B(50K)、D(20K)和E(40K)共用一个分区：50K；F(30K)和C(30K)共用一个分区：30K；61覆盖和对换技术覆盖和对换技术 覆盖技术覆盖技术( (解决小内存运行大作业解决小内存运行大作业) )使用覆盖技术要求程序员编程时必须划分程序模块和确定程序模块之间的覆盖关系，使得要覆盖的段（块）具有相对独立性，不存在直接联系或相互交叉访问。增加了编程
43、的复杂度。从外存装入覆盖文件，以时间延长来换取空间节省。62覆盖和对换技术覆盖和对换技术 对换技术对换技术( (解决小内存实现分时系统解决小内存实现分时系统) ) 所谓“对换对换”是指把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据，调入内存。常用于多道程序系统或小型分时系统中。又称作“交换”或“滚进/滚出(roll-in/roll-out)”如果对换是以整个进程为单位，称为“整体对换整体对换”或或“进程对换进程对换”。如果对换是以“页”或“段”为单位，称为“页面对换页面对换”或或“分分段对换段对换”，又
44、统称为“部分对换部分对换”。在具有对换功能的OS中，通常把外存分为文件区和对换区。文件区用于存放文件；对换区用于存放从内存换出的进程。633.6 3.6 页式虚拟存储管理页式虚拟存储管理问题的提出：动态分区存储管理的主要问题是碎片问题。在采用动态分区存储管理的系统中，会形成一些非常小的分区，最终这些非常小的分区不能被系统中的任何用户（程序）利用而浪费。 造成这样问题的主要原因是用户程序装入内存时是整体装入的(连续分配方式)。为解决这个问题，产生了离散分配方式离散分配方式，即让作业分配到多个不连续的小存储空间中。如果离散分配的基本单位是页，则称为分页存储管理方式；如果离散分配的基本单位是段，则称
45、为分段存储管理方式。在分页存储管理方式中，如果不具备页面对换功能，则称为基本的分页存基本的分页存储管理方式储管理方式(或纯分页存储管理方式)，它不支持虚拟存储，要求把每个作业全部装入内存后才能运行。否则，称为分页虚拟存储管理方式分页虚拟存储管理方式。643.6 3.6 页式虚拟存储管理页式虚拟存储管理页式存储管理的基本原理页式存储管理的基本原理页式存储管理的基本思想页式存储管理的基本思想将一个进程的逻辑地址空间分成若干个大小相等的片逻辑地址空间分成若干个大小相等的片，称为页页（或称页面），并为各页加以编号，从0开始。相应地，也把内存空间分成与页面相同大小的存储块内存空间分成与页面相同大小的存储
46、块，称为(物理)块块（或称页框）,也同样为它们加以编号。在为进程分配内存时，以块为单位将进程中的若干个页分别装以块为单位将进程中的若干个页分别装入到多个可以不相邻的物理块中入到多个可以不相邻的物理块中，每页分配一块。系统为每个进程建立一张页面映射表页面映射表（简称页表页表），记录相应页在内存中对应的物理块号。由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称为“页内碎片”。页面大小应适中，且应是2的幂，通常为512B8KB。653.6 3.6 页式虚拟存储管理页式虚拟存储管理页式存储管理的基本原理页式存储管理的基本原理 分页存储管理方式中，逻逻辑辑地地址址由两部分组成：页号和页内地址
47、(位移量)。其格式为：3112 110页号P页内地址W 对某特定机器，其地址机构是一定的。若给定一个逻辑地址空间中地址为A，页面大小为L，则页号P和页内地址d可按下式求得：p = INT(A/L)d = A MOD L 例如，其系统的页面大小为1KB，设A=2170B，则由上式可以求得P2，d122。663.6 3.6 页式虚拟存储管理页式虚拟存储管理页式主存空间的分配与回收页式主存空间的分配与回收分页式存储管理把主存的可分配区域按页面大小分成若干块，主存空间按块为单位进行分配。用一张主主存存分分配配表表来记录已分配的块和沿未分配的块以及当前剩余的空闲块数。由于块的大小固定，故可用一张“位位示
48、示图图”来构成主存分配表。位示图的每一位与主存的一个块对应，用0/1表示对应块为空闲/已占用，用另一个字节记录当前剩余的空闲块数。见P53图3-17。分分配配：先查空闲块数能否满足作业要求。若不能满足，则作业不能装入。若能满足，则找出为“0”的一些位，置上占用标志“1”，从空闲块数中减去本次占用块数，按找到的位计算出对应的块号，作业可装到这些块中。位号对应的块号的计算公式为：块号字号字长位号回收：回收：根据归还的块号计算出该块在位示图中对应的位置，将占用标志改为“0”，再把归还块数加到空闲块数中。块号对应的字号、位号的计算公式为：字号块号/字长位号块号 mod字长673.6 3.6 页式虚拟存
49、储管理页式虚拟存储管理 3.6.3 3.6.3 页表和地址转换页表和地址转换在分页系统中，允许将进程的每一页离散地存储在内存的任一物理块中，为保证进程的正确运行，系统为每个进程建立一张页面映射表页面映射表(简称页表页表)。页页 号号块号块号页页 表表页页表表：由由( (逻逻辑辑) )页页号号和和( (物物理理) )块块号号组组成成，指指出出逻逻辑辑地地址址中中页页号号与与主主存存中中块块号号的的对对应关系应关系. . 页号页号-作业逻辑地址空间的页序号作业逻辑地址空间的页序号 块号块号-内存空间的块序号内存空间的块序号 683.6 3.6 页式虚拟存储管理页式虚拟存储管理 3.6.3 3.6.
50、3 页表和地址转换页表和地址转换在进程地址空间内的所有页，依次在页表中有一页表项，在进程地址空间内的所有页，依次在页表中有一页表项，记录相应页在内存中对应的物理块号。记录相应页在内存中对应的物理块号。693.6 3.6 页式虚拟存储管理页式虚拟存储管理3.6.3 3.6.3 页表和地址转换页表和地址转换地址转换地址转换：采用动态地址重定位方式进行地址转换，要有硬件的地址转换机构作支持。地址重定位时，由硬件的地址转换把逻辑地址转换成绝对地址，主要借助于页表来完成。页表大多驻留在内存中。在系统中设置一个页表寄存器PTR(Page-Table Register)，存放页表在内存中的始址和页表的长度。
51、地址转换方式地址转换方式： 基本的地址转换基本的地址转换具有快表的地址转换具有快表的地址转换703.6 3.6 页式虚拟存储管理页式虚拟存储管理3.6.3 3.6.3 页表和地址转换页表和地址转换1.1.基本的地址转换基本的地址转换当进程要访问某逻辑地址中的数据时，地址转换机构自动将逻辑地址分为页号和页内地址两部分。再以页号为索引去检索页表，得到该页的物理块号，把该物理块号与页内地址拼接成物理地址，完成地址转换过程。检索操作由硬件执行。在检索页表之前，把页号与页表长度相比较，若大于页表长度，则产生越界中断。 713.6 3.6 页式虚拟存储管理页式虚拟存储管理3.6.3 3.6.3 页表和地址
52、转换页表和地址转换2.2.具有快表的地址转换具有快表的地址转换由于页表是存放在内存中，这使CPU每访问一个数据（或一条指令）时，都必须两次访问内存。一次是访问页表，另一次才是所需要的数据（或指令）。大大降低了计算机的处理速度 。为解决这一问题，在地址转换机构中，增设一个具有并行查寻能力的特殊高速缓冲存储器联想存储器联想存储器。利用高速缓冲存储器存放页表的一部分（当前访问的那些页表项），把存放在高速缓冲存储器中的部分页表称为快快表表。快表用硬件实现，查快表可以不必占用一个访存周期。 723.6 3.6 页式虚拟存储管理页式虚拟存储管理3.6.3 3.6.3 页表和地址转换页表和地址转换2.2.具
53、有快表的地址转换具有快表的地址转换引入快表后的地址转换过程是引入快表后的地址转换过程是：在进行地址转换时，首先检索快表。若找到，则直接用快表中给出的物理块号与逻辑地址中的页内地址形成物理地址。若未找到，则应去内存中查找页表，此时应将该页的页表项写入快表（快表满时，调出一个页表项，然后写入），然后用页表中给出的物理块号与逻辑地址中的页内地址形成物理地址。 可以看出，当快表命中时，只有一次访存；当快表不命中时，仍然需要二次访存。所以，快表的命中率如何，对于等效访存时间有很大的影响。 733.6 3.6 页式虚拟存储管理页式虚拟存储管理3.6.4 3.6.4 页的共享与保护页的共享与保护u页式存储管
54、理有利于实现多个作业共享程序和数据。页式存储管理有利于实现多个作业共享程序和数据。u页的共享页的共享：在多道程序设计系统中，编译程序、编辑程序、：在多道程序设计系统中，编译程序、编辑程序、解释程序、公共子程序、公共数据等都是可共享的。这些解释程序、公共子程序、公共数据等都是可共享的。这些共享的信息在主存储器中只要保留一个副本。各作业共享共享的信息在主存储器中只要保留一个副本。各作业共享这些信息时可使它们各自的页表中有关表目指向共享信息这些信息时可使它们各自的页表中有关表目指向共享信息所在的主存块。所在的主存块。u共享信息的保护共享信息的保护：在页表中增加一些标志，指出该页信息：在页表中增加一些
55、标志，指出该页信息可读可读/ /写或只读或可执行，等等。写或只读或可执行，等等。743.6 3.6 页式虚拟存储管理页式虚拟存储管理3.6.5 3.6.5 虚拟存储器虚拟存储器虚拟存储器的基本概念虚拟存储器的基本概念常规存储器管理方式的特征：常规存储器管理方式的特征：一次性作业在运行前需一次性地全部装入内存。驻留性作业装入内存后，便一直驻留在内存中，直至作业运行结束。上述特征，使许多在程序运行中不用或暂不用的程序(数据)占据了大量的内存空间，使得一些需要运行的作业无法装入运行。753.6 3.6 页式虚拟存储管理页式虚拟存储管理3.6.5 3.6.5 虚拟存储器虚拟存储器虚拟存储器的基本概念虚
56、拟存储器的基本概念1968年，Denning. P提出局局部部性性原原理理：程序在执行时呈现出局部性规律，即在一较短时间内，程序的执行仅限于某个部分，相应地，它所访问的存储空间也局限于某个区域。局部性又表现为时间局部性和空间局部性。v时间局部性是指如果程序中的某条指令一旦执行，则不久以后该指令可能再次执行。如果某数据结构被访问，则不久以后该数据结构可能再次被访问。v空间局部性是指一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问。763.6 3.6 页式虚拟存储管理页式虚拟存储管理3.6.5 3.6.5 虚拟存储器虚拟存储器虚拟存储器的基本概念虚拟存储器的基本概念基于程序局部性
57、原理，一个作业在运行之前，没有必要全部装入内存，而仅将那些当前要运行的那部分页面或段先装入内存，就可以启动运行。这样就可以使一个较大的程序在较小的内存空间中运行，同时还可以装入更多的程序并发执行。从用户角度来看，该系统所具有的内存容量比实际内存容量大得多。通常把这样的存储器称为虚拟存储器。所谓虚拟存储器是指仅把作业的一部分装入内存便可运行作业的存储管理系统。它具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充。773.6 3.6 页式虚拟存储管理页式虚拟存储管理3.6.5 3.6.5 虚拟存储器虚拟存储器虚拟存储器的特征虚拟存储器的特征虚拟存储器最基本的特征是离散性，虚拟存储器的实现必须
58、建立在离散分配的存储管理方式的基础上。在此基础上又形成了多次性及对换性的特征。所表现出来的最重要的特征是虚拟性。v多次性指一个作业被分成多次调入内存运行。是虚拟存储器最重要的特征。v对换性指允许在作业的运行过程中进行换进、换出。v虚拟性指能够从逻辑上扩充内存容量，使用户看到的容量远大于实际内存容量。虚拟存储器的容量取决于主存与辅存的容量之和。一个虚拟存储器的最大容量是由计算机的地址结构和辅存的容量确定的。实现虚拟存储器应有一定的硬件基础，即应有相当容量的辅存、一定容量的主存和地址变换机构。 783.6 3.6 页式虚拟存储管理页式虚拟存储管理3.6.5 3.6.5 虚拟存储器虚拟存储器虚拟存储
59、器的实现方法虚拟存储器的实现方法1、请求分页存储管理方式当一个用户程序要调入内存时，不是将该程序全部装入内存，而是只装入部分页到内存，就可启动程序运行。在运行的过程中，如果发现要运行的程序或要访问数据不在内存，则向系统发出缺缺页中断请求页中断请求，系统在处理这个中断时，将外存中相应的页调入内存，该程序继续运行。当一些页调入内存时，若内存没有空闲空间，则利用页面置换功能页面置换功能，将内存中暂时不用的页面换出到外存上，再将这些要访问的页调入内存，该程序继续运行。2、请求分段存储管理方式类似于请求分页，以段为单位进行请求和置换。793.6 3.6 页式虚拟存储管理页式虚拟存储管理3.6.6 3.6
60、.6 页式虚拟存储管理的实现页式虚拟存储管理的实现硬件支持硬件支持 页号 物理块号状态位P访问字段A修改位M外存地址页表机制页表中除了有页号、物理块号两项外，还需要状态位、访问字段、修改位、外存地址等信息。状态位指示该页是否已调入内存。访问字段记录本页在一段时间内被访问的次数或本页最近已有多长时间未被访问。供选择换出页面时参考。修改位表示该页调入内存后是否被修改过。外存地址指示该页在外存的地址。803.6 3.6 页式虚拟存储管理页式虚拟存储管理3.6.6 3.6.6 页式虚拟存储管理的实现页式虚拟存储管理的实现硬件支持硬件支持缺页中断机构每当所要访问的页面不在内存时，便要产生缺页中断，请求操
61、作系统将所缺的页面调入内存。缺页中断与一般中断的区别，在于在指令的执行期间产生和处理缺页中断，而且一条指令执行期间，可能产生多次缺页中断。缺页中断的处理过程是，保留CPU现场；从外存中找到缺的页面；若内存已满，则选择一页换出；从外存读入缺页，写入内存，修改页表。 813.6 3.6 页式虚拟存储管理页式虚拟存储管理3.6.6 3.6.6 页式虚拟存储管理的实现页式虚拟存储管理的实现硬件支持硬件支持地址变换机构在进行地址变换时，首先检索快表。若找到，则直接用快表中给出的物理块号与逻辑地址中的页内地址形成物理地址。若未找到，则应去内存中查找页表(慢表)，将有两种可能。(1)若该页已调入内存，此时则
62、应将该页的页表项写人快表(快表满时，调出一个页表项，然后写入)，用页表中给出的物理块号与逻辑地址中的页内地址形成物理地址；(2)若该页未调入内存，则产生缺页中断，请求操作系统从外存中调入。82833.6 3.6 页式虚拟存储管理页式虚拟存储管理3.6.6 3.6.6 页式虚拟存储管理的实现页式虚拟存储管理的实现页面分配策略和分配算法页面分配策略和分配算法在为进程分配内存时，涉及到三个问题：最小物理块数的确定(2)物理块的分配策略(3)物理块的分配算法843.6 3.6 页式虚拟存储管理页式虚拟存储管理3.6.6 3.6.6 页式虚拟存储管理的实现页式虚拟存储管理的实现页面分配策略和分配算法页面
63、分配策略和分配算法最小物理块数的确定最小物理块数的确定最小物理块数能保证进程正常运行所需的最少物理块数。当系统为进程分配的物理块数少于此值时，进程将无法运行。它与计算机硬件结构有关，取决于指令的格式、功能和寻址方式。853.6 3.6 页式虚拟存储管理页式虚拟存储管理3.6.6 3.6.6 页式虚拟存储管理的实现页式虚拟存储管理的实现页面分配策略和分配算法页面分配策略和分配算法物理块的分配策略物理块的分配策略分配策略可以是固定分配和可变分配。置换策略可以是全局置换和局部置换。于是可以组合出三种策略：固定分配局部置换:为每个进程分配一固定块数的内存空间，缺页时从中选出一页进行淘汰。可变分配全局置
64、换：先为每个进程分配一定块数的内存空间，缺页时由系统从管理的空闲物理块队列中取出一块分配给该进程。当空闲物理块队列中的物理块用完时，OS才从系统中任一进程中选出一页进行淘汰。可变分配局部置换：先为每个进程分配一固定块数的内存空间，缺页时从中选出一页进行淘汰。但当某进程缺页频繁时系统再为该进程分配若干附加的空闲物理块，直到进程的缺页率减少到适当程度为止。 863.6 3.6 页式虚拟存储管理页式虚拟存储管理3.6.6 3.6.6 页式虚拟存储管理的实现页式虚拟存储管理的实现页面分配策略和分配算法页面分配策略和分配算法物理块的分配算法物理块的分配算法在采用固定分配策略时，物理块分配算法有：平均分配
65、算法：将系统中所有可供分配的物理块，平均分配给各个进程。按比例分配算法：根据进程的大小按比例分配物理块。考虑优先权的分配算法：将系统中所有可供分配的物理块分成两部分：一部分按比例分配给各进程；另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程。873.6 3.6 页式虚拟存储管理页式虚拟存储管理3.6.6 3.6.6 页式虚拟存储管理的实现页式虚拟存储管理的实现页面分配策略和分配算法页面分配策略和分配算法调页策略调页策略 1、预调页策略 系统根据作业(进程)运行的情况，预测哪些页将要运行，在其运行之前先行调入内存，这样在程序运行的过程中就不会出现缺页中断。这样方法从表面上看起来
66、很好，但系统无法预计系统中作业的运行情况，难以实现。2、请求调页策略 进程在执行的过程中，发现要执行的程序或处理的数据不在内存，向系统提出调入相应程序的请求，系统响应用户的请求，将其所需页面调入内存。883.6 3.6 页式虚拟存储管理页式虚拟存储管理3.6.6 3.6.6 页式虚拟存储管理的实现页式虚拟存储管理的实现页面调度算法页面调度算法当进程运行过程中，如果发现要访问的页面不在内存而需要把它们调入内存，但内存已无空闲空间时，为了保证进程能正常运行，系统必须从内存中调出(淘汰掉)一页程序或数据，送入外存对换区中。用来选择淘汰哪一页的规则叫做调度算法。最佳调度算法(理想调度算法)先进先出(F
67、IFO)页面调度算法 最近最久未使用(LRU)调度算法最近最不经常使用(LFU)调度算法893.6 3.6 页式虚拟存储管理页式虚拟存储管理3.6.6 3.6.6 页式虚拟存储管理的实现页式虚拟存储管理的实现页面调度算法页面调度算法缺页中断率缺页中断率假定程序p共有n页，而系统分配给它的内存只有m块(1mn)，并且以作业在执行的过程中页面置换的频率的高低来衡量算法的优劣。访问的页在内存，称访问成功，否则为失败。 a=s+fa:访问的总次数 s:访问成功的次数 f:访问失败的次数缺页中断率f=f/a 则有：ff(r,m,p) (r:调度算法)设作业执行中访问页面的总次数为A，其中有F次访问的页面
68、尚未装入主存，故产生了F次缺页中断。现定义缺页中断率为：f=F/A903.6 3.6 页式虚拟存储管理页式虚拟存储管理3.6.6 3.6.6 页式虚拟存储管理的实现页式虚拟存储管理的实现页面调度算法页面调度算法最佳调度算法最佳调度算法( (理想调度算法理想调度算法) )基本思想：选择永不使用或在未来最长时间内不再被访问的页面予以替换。该算法无法实现，只能作为其他算法的衡量标准。例：假如一个作业的页面走向为7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。系统分配给该作业的物理块数为3。 缺页中断率为：f=F/A=9/20=45%913.6 3.6 页式虚拟存储管理
69、页式虚拟存储管理3.6.6 3.6.6 页式虚拟存储管理的实现页式虚拟存储管理的实现页面调度算法页面调度算法先进先出先进先出(FIFO)(FIFO)页面调度算法页面调度算法 基本思想：选择在内存中驻留时间最久的页面予以替换。例：假如一个作业的页面走向为7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。系统分配给该作业的物理块数为3。缺页中断率为：f=F/A=15/20=75%923.6 3.6 页式虚拟存储管理页式虚拟存储管理3.6.6 3.6.6 页式虚拟存储管理的实现页式虚拟存储管理的实现页面调度算法页面调度算法最近最久未使用最近最久未使用(LRU)(LRU)
70、调度算法调度算法基本思想：选择过去最长时间未被访问的页面予以替换。例：假如一个作业的页面走向为7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。系统分配给该作业的物理块数为3。缺页中断率为：f=F/A=12/20=60%933.6 3.6 页式虚拟存储管理页式虚拟存储管理3.6.6 3.6.6 页式虚拟存储管理的实现页式虚拟存储管理的实现页面调度算法页面调度算法最近最不经常使用最近最不经常使用(LFU)(LFU)调度算法调度算法基本思想：选择过去被访问次数最少的页面予以替换。例：假如一个作业的页面走向为7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0
71、，1，7，0，1。系统分配给该作业的物理块数为3。缺页中断率为：943.6 3.6 页式虚拟存储管理页式虚拟存储管理3.6.6 3.6.6 页式虚拟存储管理的实现页式虚拟存储管理的实现页面调度算法页面调度算法抖动与工作集抖动与工作集在请求分页存储管理系统中，可能会出现这样的现象，即对于刚被替换出去的页，可能马上又要被访问，需要将它调入，因无空闲内存又要替换另一页，而后者可能是即将被访问的页。于是造成了系统需花费大量的时间忙于进行这种频繁的页面交换，致使系统的实际效率很低，严重时导致系统瘫痪。这种现象称为抖动（颠簸）现象抖动（颠簸）现象。防止抖动现象可以有多种办法，例如，采取局部替换策略、引入工
72、作集算法、挂起若干进程等。所谓工作集工作集是指在某段时间间隔里，进程实际要访问的页面的集合。引入虚拟存储器后，虽然程序只须有少量的内存就可以运行，但为了使程序有效运行，较少产生缺页，就必须使程序的工作集全部在内存中。95432143543215432143543215FIFO444111555LRU444111522233344422333444411222333122233335例例44在一个请求分页系统中，假如一个作业的页面走向为4，3，2，1，4，3，5，4，3，2，1，5。当分配给该作业的物理块数M分别是3和4时，分别采用LRU和FIFO页面替换算法，试计算在访问过程中所发生的缺页次数和缺页率。963.6 3.6 页式虚拟存储管理页式虚拟存储管理 3.6.7 3.6.7 多级页表多级页表9798
