《第三章存储管理》由会员分享，可在线阅读，更多相关《第三章存储管理（211页珍藏版）》请在金锄头文库上搜索。
1、第三章第三章存储管理存储管理内存内存OS外存外存外存外存本章要点本章要点存储管理的任务存储管理的任务存储管理的任务存储管理的任务 内存划分与分配技术内存划分与分配技术内存划分与分配技术内存划分与分配技术 程序装入技术程序装入技术程序装入技术程序装入技术 简单存储管理技术简单存储管理技术简单存储管理技术简单存储管理技术 虚拟存储管理技术虚拟存储管理技术虚拟存储管理技术虚拟存储管理技术 3.1 3.1 存储管理的任务存储管理的任务 存储分配存储分配 基本任务：管理内存空间的分配与回收基本任务：管理内存空间的分配与回收基本任务：管理内存空间的分配与回收基本任务：管理内存空间的分配与回收(1)(1)(
2、1)(1)分配基本内存空间分配基本内存空间分配基本内存空间分配基本内存空间 (2)(2)(2)(2)增加新的内存空间增加新的内存空间增加新的内存空间增加新的内存空间 动态申请或释放内存空间动态申请或释放内存空间动态申请或释放内存空间动态申请或释放内存空间 (3)(3)(3)(3)回收内存空间回收内存空间回收内存空间回收内存空间用于内存管理的数据结构用于内存管理的数据结构如位示图、空闲页框表等。如位示图、空闲页框表等。如位示图、空闲页框表等。如位示图、空闲页框表等。记记记记载载载载哪哪哪哪些些些些内内内内存存存存被被被被分分分分配配配配给给给给了了了了哪哪哪哪个个个个进进进进程程程程，哪哪哪哪些
3、些些些内内内内存存存存空间是空闲的等信息。空间是空闲的等信息。空间是空闲的等信息。空间是空闲的等信息。若若若若系系系系统统统统采采采采用用用用虚虚虚虚拟拟拟拟存存存存储储储储管管管管理理理理技技技技术术术术，还还还还需需需需要要要要登登登登记记记记进进进进程程程程的的的的程程程程序序序序和和和和数数数数据据据据中中中中，哪哪哪哪些些些些部部部部分分分分在在在在内内内内存存存存，哪哪哪哪些些些些部部部部分尚在外存等信息。分尚在外存等信息。分尚在外存等信息。分尚在外存等信息。这这这这些些些些数数数数据据据据结结结结构构构构自自自自身身身身需需需需要要要要占占占占用用用用一一一一定定定定的的的的内内
4、内内存存存存空空空空间间间间，也需要系统花费额外的时间进行维护。也需要系统花费额外的时间进行维护。也需要系统花费额外的时间进行维护。也需要系统花费额外的时间进行维护。存储分配步骤存储分配步骤首首先先，根根据据系系统统的的内内存存分分配配算算法法，在在空空闲闲的的内内存存分分区区中中寻寻找找到到一一块块满满足足进进程程需需要的内存空间，将其分配给进程。要的内存空间，将其分配给进程。然然后后，更更新新进进程程的的资资源源分分配配清清单单、内内存存分配情况清单等数据结构。分配情况清单等数据结构。内存的回收内存的回收更更新新相相应应的的数数据据结结构构，将将回回收收的的内内存存空空间标识为间标识为“空
5、闲可用空闲可用”就行了。就行了。？ 该内存空间是否可以被回收该内存空间是否可以被回收？ 被其他进程共享被其他进程共享？ 属于相应的进程属于相应的进程？ 与相临的空闲空间进行合并与相临的空闲空间进行合并地址映射地址映射 逻辑地址，或相对地址：一般从逻辑地址，或相对地址：一般从逻辑地址，或相对地址：一般从逻辑地址，或相对地址：一般从0 0 0 0开始编址开始编址开始编址开始编址 物理地址，或绝对地址：标识内存中的每个存储单元。物理地址，或绝对地址：标识内存中的每个存储单元。物理地址，或绝对地址：标识内存中的每个存储单元。物理地址，或绝对地址：标识内存中的每个存储单元。 图图3.1 3.1 进程执行
6、时的寻址进程执行时的寻址当前栈顶当前栈顶进程控制信息进程控制信息程序入口点程序入口点地址值增加地址值增加进程控制块进程控制块程序程序栈栈数据数据访问数据访问数据分支指令分支指令进程映像进程映像？逻辑地址逻辑地址高级语言或汇编语言使用符号地址：变高级语言或汇编语言使用符号地址：变量名或标号量名或标号源程序经过编译、链接以后，其中的符源程序经过编译、链接以后，其中的符号地址就会变成数字式的逻辑地址。号地址就会变成数字式的逻辑地址。编译编译/ /链接程序会自动计算每一个变量或链接程序会自动计算每一个变量或标号所对应的逻辑地址是多少。标号所对应的逻辑地址是多少。 静态映射：静态重定位静态映射：静态重定
7、位地地地地址址址址映映映映射射射射：程程程程序序序序装装装装入入入入内内内内存存存存以以以以后后后后，由由由由操操操操作作作作系系系系统统统统将将将将逻逻逻逻辑辑辑辑地地地地址址址址改改改改为为为为逻逻逻逻辑辑辑辑地地地地址址址址加加加加上上上上起起起起始始始始地地地地址址址址，得得得得到到到到实实实实际的物理地址。际的物理地址。际的物理地址。际的物理地址。重重重重定定定定位位位位(Relocation)(Relocation)：对对对对目目目目标标标标程程程程序序序序中中中中的的的的指指指指令令令令和和和和数数数数据地址进行修改的过程。据地址进行修改的过程。据地址进行修改的过程。据地址进行修
8、改的过程。静静静静态态态态映映映映射射射射实实实实现现现现简简简简单单单单。地地地地址址址址变变变变换换换换只只只只在在在在程程程程序序序序装装装装入入入入时时时时一次完成，程序运行时不再改变。一次完成，程序运行时不再改变。一次完成，程序运行时不再改变。一次完成，程序运行时不再改变。但但但但不不不不适适适适合合合合多多多多道道道道程程程程序序序序系系系系统统统统；不不不不允允允允许许许许系系系系统统统统执执执执行行行行内内内内存存存存的碎片整理；无法实现虚拟存储的碎片整理；无法实现虚拟存储的碎片整理；无法实现虚拟存储的碎片整理；无法实现虚拟存储动态映射：动态重定位动态映射：动态重定位操作系统将
9、程序装入内存以后，并不立即把目操作系统将程序装入内存以后，并不立即把目操作系统将程序装入内存以后，并不立即把目操作系统将程序装入内存以后，并不立即把目标程序中的逻辑地址转换为物理地址，而是在标程序中的逻辑地址转换为物理地址，而是在标程序中的逻辑地址转换为物理地址，而是在标程序中的逻辑地址转换为物理地址，而是在处理机执行每一条指令时进行地址转换。处理机执行每一条指令时进行地址转换。处理机执行每一条指令时进行地址转换。处理机执行每一条指令时进行地址转换。复杂且费时。复杂且费时。复杂且费时。复杂且费时。为了系统效率，处理机中设置了专门的高速硬为了系统效率，处理机中设置了专门的高速硬为了系统效率，处理
10、机中设置了专门的高速硬为了系统效率，处理机中设置了专门的高速硬件，自动完成地址转换，这样的硬件被称作地件，自动完成地址转换，这样的硬件被称作地件，自动完成地址转换，这样的硬件被称作地件，自动完成地址转换，这样的硬件被称作地址管理部件，如图址管理部件，如图址管理部件，如图址管理部件，如图3.23.23.23.2所示。所示。所示。所示。 CPUCPU地址管理部件地址管理部件程序指令程序指令物理地址物理地址地址总线地址总线逻辑地址逻辑地址图图3.2 CPU3.2 CPU中的地址管理部件工作示意图中的地址管理部件工作示意图存储保护存储保护防止地址越界，防止操作越权。防止地址越界，防止操作越权。防止地址
11、越界，防止操作越权。防止地址越界，防止操作越权。地地地地址址址址越越越越界界界界：进进进进程程程程访访访访问问问问不不不不属属属属于于于于自自自自己己己己的的的的地地地地址址址址空空空空间间间间，或或或或者者者者说说说说进进进进程程程程在在在在运运运运行行行行时时时时所所所所产产产产生生生生的的的的物物物物理理理理地地地地址址址址超超超超越越越越其其其其自身的地址空间范围。自身的地址空间范围。自身的地址空间范围。自身的地址空间范围。 可可可可能能能能侵侵侵侵犯犯犯犯其其其其他他他他用用用用户户户户进进进进程程程程空空空空间间间间，也也也也可可可可能能能能侵侵侵侵犯犯犯犯操操操操作系统的存储空间
12、作系统的存储空间作系统的存储空间作系统的存储空间操操操操作作作作越越越越权权权权：进进进进程程程程对对对对共共共共享享享享存存存存储储储储区区区区的的的的操操操操作作作作违违违违反反反反了了了了系系系系统规定的权限。统规定的权限。统规定的权限。统规定的权限。存储保护的实现存储保护的实现存储保护只能进程执行过程中动态地进行，不存储保护只能进程执行过程中动态地进行，不存储保护只能进程执行过程中动态地进行，不存储保护只能进程执行过程中动态地进行，不可能在运行前一次性静态完成。可能在运行前一次性静态完成。可能在运行前一次性静态完成。可能在运行前一次性静态完成。若采用动态映射动态计算物理地址，可能计算若
13、采用动态映射动态计算物理地址，可能计算若采用动态映射动态计算物理地址，可能计算若采用动态映射动态计算物理地址，可能计算出错误地址；若采用静态映射，进程执行过程出错误地址；若采用静态映射，进程执行过程出错误地址；若采用静态映射，进程执行过程出错误地址；若采用静态映射，进程执行过程中也可能出错，从而导致地址越界或操作越权。中也可能出错，从而导致地址越界或操作越权。中也可能出错，从而导致地址越界或操作越权。中也可能出错，从而导致地址越界或操作越权。为了提高系统效率，存储保护的主要工作必须为了提高系统效率，存储保护的主要工作必须为了提高系统效率，存储保护的主要工作必须为了提高系统效率，存储保护的主要工
14、作必须由高速的专用硬件来完成：在地址管理部件中。由高速的专用硬件来完成：在地址管理部件中。由高速的专用硬件来完成：在地址管理部件中。由高速的专用硬件来完成：在地址管理部件中。 存储共享存储共享为了进程通信和节约内存空间，两个或多个进为了进程通信和节约内存空间，两个或多个进为了进程通信和节约内存空间，两个或多个进为了进程通信和节约内存空间，两个或多个进程共用内存中相同的分区，即他们的物理空间程共用内存中相同的分区，即他们的物理空间程共用内存中相同的分区，即他们的物理空间程共用内存中相同的分区，即他们的物理空间有相交的部分。有相交的部分。有相交的部分。有相交的部分。可以共享进程的代码，也可以共享进
15、程数据。可以共享进程的代码，也可以共享进程数据。可以共享进程的代码，也可以共享进程数据。可以共享进程的代码，也可以共享进程数据。一般地，进程之间共享代码的目的主要是为了一般地，进程之间共享代码的目的主要是为了一般地，进程之间共享代码的目的主要是为了一般地，进程之间共享代码的目的主要是为了节约存储空间，共享数据的目的主要是为了实节约存储空间，共享数据的目的主要是为了实节约存储空间，共享数据的目的主要是为了实节约存储空间，共享数据的目的主要是为了实现进程间相互通信。现进程间相互通信。现进程间相互通信。现进程间相互通信。 PCB3数据数据代码代码PCB2代码代码数据数据PCB1数据数据代码代码进程进
16、程1进程进程2进程进程3图图3.3进程之间共享代码和数据进程之间共享代码和数据共享数据共享数据通过存储共享完成数据共享的过程：通过存储共享完成数据共享的过程：一个进程将数据写入共享存储区，一个进程将数据写入共享存储区，另一个进程从共享存储区中读出数据。另一个进程从共享存储区中读出数据。共享代码共享代码程序可重入：设计程序时，逻辑上将程序代码程序可重入：设计程序时，逻辑上将程序代码程序可重入：设计程序时，逻辑上将程序代码程序可重入：设计程序时，逻辑上将程序代码区和数据区分开。区和数据区分开。区和数据区分开。区和数据区分开。代码区不包含运行程序时需要改变的数据，被代码区不包含运行程序时需要改变的数
17、据，被代码区不包含运行程序时需要改变的数据，被代码区不包含运行程序时需要改变的数据，被处理的数据都放在独立的数据区。这样，进程处理的数据都放在独立的数据区。这样，进程处理的数据都放在独立的数据区。这样，进程处理的数据都放在独立的数据区。这样，进程执行过程中就不会改变代码部分的任何内容。执行过程中就不会改变代码部分的任何内容。执行过程中就不会改变代码部分的任何内容。执行过程中就不会改变代码部分的任何内容。数据区是单独的一个段、堆栈式动态申请的分数据区是单独的一个段、堆栈式动态申请的分数据区是单独的一个段、堆栈式动态申请的分数据区是单独的一个段、堆栈式动态申请的分区，或通过参数传递。区，或通过参数
18、传递。区，或通过参数传递。区，或通过参数传递。共享代码共享代码创建新进程时，不需要为该进程的代码部分另创建新进程时，不需要为该进程的代码部分另创建新进程时，不需要为该进程的代码部分另创建新进程时，不需要为该进程的代码部分另外申请内存空间，只需将该进程外申请内存空间，只需将该进程外申请内存空间，只需将该进程外申请内存空间，只需将该进程PCBPCBPCBPCB中的进程中的进程中的进程中的进程代码空间的地址指向已有的代码空间地址。代码空间的地址指向已有的代码空间地址。代码空间的地址指向已有的代码空间地址。代码空间的地址指向已有的代码空间地址。进程的数据区，要么等到操作系统为其分配相进程的数据区，要么
19、等到操作系统为其分配相进程的数据区，要么等到操作系统为其分配相进程的数据区，要么等到操作系统为其分配相应存储空间以后，将数据区地址填写在应存储空间以后，将数据区地址填写在应存储空间以后，将数据区地址填写在应存储空间以后，将数据区地址填写在PCBPCBPCBPCB中；中；中；中；要么由进程运行时向操作系统动态申请。要么由进程运行时向操作系统动态申请。要么由进程运行时向操作系统动态申请。要么由进程运行时向操作系统动态申请。 共享代码共享代码可可可可以以以以将将将将进进进进程程程程的的的的代代代代码码码码视视视视为为为为处处处处理理理理数数数数据据据据的的的的一一一一组组组组规规规规则则则则或或或或
20、公公公公式式式式，这这这这一一一一组组组组规规规规则则则则或或或或公公公公式式式式存存存存储储储储在在在在内内内内存存存存中中中中的的的的某某某某个个个个分区。分区。分区。分区。进进进进程程程程的的的的执执执执行行行行：利利利利用用用用这这这这一一一一组组组组规规规规则则则则或或或或公公公公式式式式来来来来完完完完成成成成数数数数据的运算。据的运算。据的运算。据的运算。多多多多个个个个进进进进程程程程共共共共享享享享代代代代码码码码：多多多多个个个个进进进进程程程程需需需需要要要要使使使使用用用用同同同同一一一一组组组组规则或公式处理不同的数据。规则或公式处理不同的数据。规则或公式处理不同的数
21、据。规则或公式处理不同的数据。PCBPCBPCBPCB：告告告告诉诉诉诉进进进进程程程程其其其其所所所所需需需需的的的的规规规规则则则则或或或或公公公公式式式式以以以以及及及及需需需需要要要要处理的数据存储在哪里，进程的进度等处理的数据存储在哪里，进程的进度等处理的数据存储在哪里，进程的进度等处理的数据存储在哪里，进程的进度等共享代码共享代码对对于于高高级级程程序序的的设设计计而而言言，只只要要相相应应的的编编译译程程序序支支持持可可重重入入的的程程序序设设计计，那那么么，设设计计程程序序时时就就不不需需要要考考虑虑程程序序的的可可重重入入问问题题，不不需需要要将将程程序序代代码码和和数数据据
22、严严格格分分开。开。编编译译程程序序在在编编译译时时，会会自自动动将将欲欲处处理理的的数数据据与与程程序序代代码码分分开开存存储储，以以保保证证代代码码部分是纯的、可重入的。部分是纯的、可重入的。存储扩充存储扩充 内存：速度快、容量小、价格贵内存：速度快、容量小、价格贵内存：速度快、容量小、价格贵内存：速度快、容量小、价格贵外存：容量大、速度慢、价格便宜外存：容量大、速度慢、价格便宜外存：容量大、速度慢、价格便宜外存：容量大、速度慢、价格便宜目目目目的的的的：在在在在多多多多道道道道程程程程序序序序系系系系统统统统中中中中能能能能运运运运行行行行更更更更多多多多、更更更更大大大大的的的的程序，
23、降低系统的造价，提高系统的性价比程序，降低系统的造价，提高系统的性价比程序，降低系统的造价，提高系统的性价比程序，降低系统的造价，提高系统的性价比存储扩充：采用软件手段，在硬件的配合下，存储扩充：采用软件手段，在硬件的配合下，存储扩充：采用软件手段，在硬件的配合下，存储扩充：采用软件手段，在硬件的配合下，将部分外存空间虚拟为内存空间，并将内存和将部分外存空间虚拟为内存空间，并将内存和将部分外存空间虚拟为内存空间，并将内存和将部分外存空间虚拟为内存空间，并将内存和外存有机地结合起来，得到一个容量相当于外外存有机地结合起来，得到一个容量相当于外外存有机地结合起来，得到一个容量相当于外外存有机地结合
24、起来，得到一个容量相当于外存、速度接近于内存、价格十分便宜的存、速度接近于内存、价格十分便宜的存、速度接近于内存、价格十分便宜的存、速度接近于内存、价格十分便宜的虚拟存虚拟存虚拟存虚拟存储系统储系统储系统储系统存储扩充存储扩充 虚拟存储系统在逻辑上对外是一个整体，虚拟存储系统在逻辑上对外是一个整体，用户感觉到系统提供了一个非常大的用户感觉到系统提供了一个非常大的“内存内存”空间。空间。操作系统负责完成内存与外存之间的透操作系统负责完成内存与外存之间的透明切换：进程运行时将需要的数据或代明切换：进程运行时将需要的数据或代码从外存装入内存，并将内存中暂时不码从外存装入内存，并将内存中暂时不用的部分
25、交换到外存。用的部分交换到外存。3.2 3.2 内存划分与分配技术内存划分与分配技术内存划分内存划分静态划分：划分预先进行，创建新进程静态划分：划分预先进行，创建新进程时，在内存中找到一个合适的分区分配时，在内存中找到一个合适的分区分配给它。给它。动态划分：系统初始化时，可以将整个动态划分：系统初始化时，可以将整个内存的用户区看作一个分区。创建新进内存的用户区看作一个分区。创建新进程时，根据进程申请的空间大小，在这程时，根据进程申请的空间大小，在这个分区中动态地为之划分一部分空间。个分区中动态地为之划分一部分空间。静态划分静态划分必必必必须须须须事事事事先先先先进进进进行行行行，一一一一旦旦旦
26、旦划划划划分分分分完完完完毕毕毕毕，分分分分区区区区的的的的大大大大小小小小和和和和数目将不再改变。数目将不再改变。数目将不再改变。数目将不再改变。可可可可以以以以划划划划分分分分：大大大大小小小小相相相相同同同同/ /不不不不同同同同的的的的分分分分区区区区，如如如如固固固固定定定定分分分分区区区区和分页。和分页。和分页。和分页。固固固固定定定定分分分分区区区区：根根根根据据据据系系系系统统统统管管管管理理理理员员员员的的的的经经经经验验验验和和和和一一一一些些些些统统统统计计计计规规规规律律律律，事事事事先先先先将将将将内内内内存存存存空空空空间间间间划划划划分分分分为为为为若若若若干干干
27、干个个个个固固固固定定定定大大大大小小小小的的的的分分分分区区区区，称称称称为为为为分分分分区区区区(Partitioning)(Partitioning)。当当当当进进进进程程程程申申申申请请请请存存存存储储储储空空空空间间间间时时时时，系系系系统统统统为为为为之之之之分分分分配配配配一一一一个个个个大大大大小小小小合合合合适适适适的的的的空空空空闲分区。闲分区。闲分区。闲分区。静态划分静态划分分分页页：特特殊殊的的静静态态分分区区，需需要要事事先先将将内内存存空空间间划划分分为为若若干干个个大大小小相相同同的的分分区区，称为页框，或帧（称为页框，或帧（frame）。）。当当进进程程申申请请
28、存存储储空空间间时时，系系统统可可以以为为之之分配多个空闲页框。分配多个空闲页框。8MB8MB8MB8MB8MB操作系统操作系统8MB(a)等长分区等长分区图图3.4固定分区划分固定分区划分固定分区：等长固定分区：等长固定分区：等长固定分区：等长所有分区的长度相同。所有分区的长度相同。所有分区的长度相同。所有分区的长度相同。优优优优点点点点：分分分分配配配配简简简简单单单单，只只只只要要要要进进进进程程程程大大大大小小小小不不不不超超超超过过过过分分分分区区区区大大大大小，就可以装到任何一个分区中运行。小，就可以装到任何一个分区中运行。小，就可以装到任何一个分区中运行。小，就可以装到任何一个分
29、区中运行。浪浪浪浪费费费费存存存存储储储储空空空空间间间间。若若若若进进进进程程程程申申申申请请请请的的的的存存存存储储储储空空空空间间间间很很很很小小小小，却却却却需需需需要要要要占占占占用用用用整整整整个个个个分分分分区区区区，分分分分区区区区内内内内存存存存在在在在不不不不可可可可用用用用的的的的浪浪浪浪费空间，称为内零头费空间，称为内零头费空间，称为内零头费空间，称为内零头（internalfragmentationinternalfragmentation）。）。）。）。无法运行超过分区大小的程序。无法运行超过分区大小的程序。无法运行超过分区大小的程序。无法运行超过分区大小的程序。无
30、法精确确定分区的大小。无法精确确定分区的大小。无法精确确定分区的大小。无法精确确定分区的大小。操作系统操作系统8MB2MB8MB4MB12MB20MB(b)异长分区异长分区图图3.4固定分区划分固定分区划分固定分区：异长固定分区：异长固定分区：异长固定分区：异长将内存空间划分为若干个长度不同的分将内存空间划分为若干个长度不同的分区，以适合于不同大小的进程需要区，以适合于不同大小的进程需要既提高存储空间的利用率、减少浪费，既提高存储空间的利用率、减少浪费，又使长进程能装入运行。又使长进程能装入运行。但是，确定每个分区的大小也是一件十但是，确定每个分区的大小也是一件十分困难的事情。分困难的事情。
31、固定分区固定分区管理简单，只需要建立一张分区使用表，登记管理简单，只需要建立一张分区使用表，登记管理简单，只需要建立一张分区使用表，登记管理简单，只需要建立一张分区使用表，登记分区的使用情况。（等长分区只需要标明分区分区的使用情况。（等长分区只需要标明分区分区的使用情况。（等长分区只需要标明分区分区的使用情况。（等长分区只需要标明分区状态是已分配，还是空闲）状态是已分配，还是空闲）状态是已分配，还是空闲）状态是已分配，还是空闲）分区号分区号分区号分区号( ( ( (可省略可省略可省略可省略) ) ) )大小大小大小大小起始地址起始地址起始地址起始地址状态状态状态状态1 1 1 12020202
32、040404040未分配未分配未分配未分配2 2 2 25050505060606060已分配已分配已分配已分配3 3 3 350505050110110110110未分配未分配未分配未分配4 4 4 4100100100100160160160160已分配已分配已分配已分配5 5 5 5200200200200260260260260已分配已分配已分配已分配固定分区：分配固定分区：分配首先，检索分区使用表，从中找出一个尚未分首先，检索分区使用表，从中找出一个尚未分首先，检索分区使用表，从中找出一个尚未分首先，检索分区使用表，从中找出一个尚未分配的、能满足大小且内零头最小的分区。配的、能满足大
33、小且内零头最小的分区。配的、能满足大小且内零头最小的分区。配的、能满足大小且内零头最小的分区。若分区使用表中的分区按从小到大的顺序排列，若分区使用表中的分区按从小到大的顺序排列，若分区使用表中的分区按从小到大的顺序排列，若分区使用表中的分区按从小到大的顺序排列，则分配时，从表中的第一个表项开始查找，找则分配时，从表中的第一个表项开始查找，找则分配时，从表中的第一个表项开始查找，找则分配时，从表中的第一个表项开始查找，找到的第一个尚未分配并满足大小的分区即是最到的第一个尚未分配并满足大小的分区即是最到的第一个尚未分配并满足大小的分区即是最到的第一个尚未分配并满足大小的分区即是最佳的分区。佳的分区
34、。佳的分区。佳的分区。将分区使用表中该分区的状态修改为已分配。将分区使用表中该分区的状态修改为已分配。将分区使用表中该分区的状态修改为已分配。将分区使用表中该分区的状态修改为已分配。若找不到大小足够的分区，则系统将拒绝运行若找不到大小足够的分区，则系统将拒绝运行若找不到大小足够的分区，则系统将拒绝运行若找不到大小足够的分区，则系统将拒绝运行该进程，或采用其它技术进行处理，如覆盖技该进程，或采用其它技术进行处理，如覆盖技该进程，或采用其它技术进行处理，如覆盖技该进程，或采用其它技术进行处理，如覆盖技术等。术等。术等。术等。 固定分区存在内零头，浪费存储空间：固定分区存在内零头，浪费存储空间：异长
35、分区较等长分区可以一定程度上提异长分区较等长分区可以一定程度上提高系统的性能，但并不能彻底解决问题。高系统的性能，但并不能彻底解决问题。 分页式划分分页式划分(Paging)为了提高内存资源的利用率，可以考虑将分区为了提高内存资源的利用率，可以考虑将分区为了提高内存资源的利用率，可以考虑将分区为了提高内存资源的利用率，可以考虑将分区长度缩小，减少内零头浪费的空间。长度缩小，减少内零头浪费的空间。长度缩小，减少内零头浪费的空间。长度缩小，减少内零头浪费的空间。但是，这样做必须有一个前提，即进程可以分但是，这样做必须有一个前提，即进程可以分但是，这样做必须有一个前提，即进程可以分但是，这样做必须有
36、一个前提，即进程可以分配若干不连续的存储空间。否则，小分区可能配若干不连续的存储空间。否则，小分区可能配若干不连续的存储空间。否则，小分区可能配若干不连续的存储空间。否则，小分区可能使更多的进程无法装入内存。使更多的进程无法装入内存。使更多的进程无法装入内存。使更多的进程无法装入内存。分页划分：系统预先将内存空间划分为若干较分页划分：系统预先将内存空间划分为若干较分页划分：系统预先将内存空间划分为若干较分页划分：系统预先将内存空间划分为若干较小的、固定大小的页框。小的、固定大小的页框。小的、固定大小的页框。小的、固定大小的页框。151515150 0 0 02 2 2 21 1 1 13 3
37、3 3内存内存内存内存页框号页框号页框号页框号图图图图3.5 3.5 3.5 3.5 分页式划分分页式划分分页式划分分页式划分分页式划分分页式划分(Paging)页框较小，有效地减少了内零头的浪费页框较小，有效地减少了内零头的浪费页框较小，有效地减少了内零头的浪费页框较小，有效地减少了内零头的浪费每个进程平均浪费每个进程平均浪费每个进程平均浪费每个进程平均浪费0.50.50.50.5页框大小。页框大小。页框大小。页框大小。页框大小固定，简化了存储分配。页框大小固定，简化了存储分配。页框大小固定，简化了存储分配。页框大小固定，简化了存储分配。需要记录内存页框的分配和使用情况：位示图、需要记录内存
38、页框的分配和使用情况：位示图、需要记录内存页框的分配和使用情况：位示图、需要记录内存页框的分配和使用情况：位示图、空闲页框表或空闲页框链表等。空闲页框表或空闲页框链表等。空闲页框表或空闲页框链表等。空闲页框表或空闲页框链表等。分页：数据结构分页：数据结构位位位位示示示示图图图图是是是是一一一一个个个个由由由由0 0、1 1构构构构成成成成的的的的向向向向量量量量，其其其其中中中中每每每每一一一一位位位位(bit)(bit)表表表表示示示示一一一一个个个个页页页页框框框框的的的的使使使使用用用用状状状状态态态态。一一一一般般般般规规规规定定定定，0 0表表表表示页框空闲，示页框空闲，示页框空闲，
39、示页框空闲，1 1表示页框已被分配。表示页框已被分配。表示页框已被分配。表示页框已被分配。假假假假定定定定存存存存储储储储空空空空间间间间被被被被划划划划分分分分为为为为n n个个个个页页页页框框框框，所所所所有有有有页页页页框框框框依依依依次次次次编编编编号号号号为为为为0,1,2,n-10,1,2,n-1，则则则则记记记记录录录录所所所所有有有有页页页页框框框框的的的的使使使使用用用用状态的位示图形如：状态的位示图形如：状态的位示图形如：状态的位示图形如：00000111011111111111000111100111110000011101111111111100011110011111
40、分页：数据结构分页：数据结构空闲页框表空闲页框表：以表格形式记载内存页框以表格形式记载内存页框的使用情况。的使用情况。显然，为每一个空闲页框设置一个表项显然，为每一个空闲页框设置一个表项是不合理的，这将导致页框表太大。是不合理的，这将导致页框表太大。可以为一组连续的空闲页框设置一个表可以为一组连续的空闲页框设置一个表项，其中主要包括：首页框号和页框个项，其中主要包括：首页框号和页框个数，如表数，如表3.23.2所示。所示。 分页：数据结构分页：数据结构表表3.2空闲页框表空闲页框表 首页框号首页框号首页框号首页框号页框个数页框个数页框个数页框个数505010010022022030303003
41、008080450450210210分页：数据结构分页：数据结构位示图和空闲页框表都需要占用专门的存储空位示图和空闲页框表都需要占用专门的存储空位示图和空闲页框表都需要占用专门的存储空位示图和空闲页框表都需要占用专门的存储空间间间间空闲页框链表空闲页框链表空闲页框链表空闲页框链表：是将内存中所有的空闲页框通：是将内存中所有的空闲页框通：是将内存中所有的空闲页框通：是将内存中所有的空闲页框通过其内的链接指针连成一个链表，系统只需要过其内的链接指针连成一个链表，系统只需要过其内的链接指针连成一个链表，系统只需要过其内的链接指针连成一个链表，系统只需要记录链表头的位置。记录链表头的位置。记录链表头的
42、位置。记录链表头的位置。为进程分配存储空间时，从链表头开始取所需为进程分配存储空间时，从链表头开始取所需为进程分配存储空间时，从链表头开始取所需为进程分配存储空间时，从链表头开始取所需的页框，同时更新链表头。的页框，同时更新链表头。的页框，同时更新链表头。的页框，同时更新链表头。回收进程释放的存储空间时，将新产生的空闲回收进程释放的存储空间时，将新产生的空闲回收进程释放的存储空间时，将新产生的空闲回收进程释放的存储空间时，将新产生的空闲页框链接到空闲页框链表中。页框链接到空闲页框链表中。页框链接到空闲页框链表中。页框链接到空闲页框链表中。 动态划分与分配算法动态划分与分配算法 静静静静态态态态
43、划划划划分分分分未未未未考考考考虑虑虑虑进进进进程程程程的的的的实实实实际际际际需需需需要要要要。无无无无论论论论是是是是固固固固定定定定分区，还是分页，都存在不同程度的内零头。分区，还是分页，都存在不同程度的内零头。分区，还是分页，都存在不同程度的内零头。分区，还是分页，都存在不同程度的内零头。动动动动态态态态划划划划分分分分：根根根根据据据据进进进进程程程程的的的的实实实实际际际际需需需需要要要要，动动动动态态态态地地地地划划划划分分分分内内内内存存存存空空空空间间间间，并并并并分分分分配配配配给给给给进进进进程程程程，彻彻彻彻底底底底解解解解决决决决了了了了内内内内零零零零头头头头问题。
44、问题。问题。问题。系系系系统统统统初初初初始始始始化化化化时时时时，内内内内存存存存用用用用户户户户区区区区就就就就是是是是一一一一个个个个大大大大分分分分区区区区。随随随随着着着着进进进进程程程程的的的的创创创创建建建建和和和和撤撤撤撤消消消消，内内内内存存存存被被被被动动动动态态态态划划划划分分分分成成成成若若若若干较小的分区。干较小的分区。干较小的分区。干较小的分区。动态划分与分配算法动态划分与分配算法 例如，例如，例如，例如，如图如图如图如图3.63.6有一个有一个有一个有一个128MB128MB的内存，其中操作系统自身占用的内存，其中操作系统自身占用的内存，其中操作系统自身占用的内存
45、，其中操作系统自身占用8MB8MB，剩下的，剩下的，剩下的，剩下的120MB120MB空间供用户进程使用。空间供用户进程使用。空间供用户进程使用。空间供用户进程使用。依次装入进程依次装入进程依次装入进程依次装入进程P1P1、P2P2、P3P3、P4P4、P5P5、P6P6，剩，剩，剩，剩下一个下一个下一个下一个10MB10MB的空闲分区。的空闲分区。的空闲分区。的空闲分区。一段时间之后，进程一段时间之后，进程一段时间之后，进程一段时间之后，进程P1P1、P3P3、P5P5执行结束，释执行结束，释执行结束，释执行结束，释放出放出放出放出3 3个空闲分区。内存中共有个空闲分区。内存中共有个空闲分区
46、。内存中共有个空闲分区。内存中共有4 4个空闲分区，个空闲分区，个空闲分区，个空闲分区，图图图图3.63.6动态划分内存空间的过程动态划分内存空间的过程动态划分内存空间的过程动态划分内存空间的过程(a)(a)分配之前分配之前分配之前分配之前OS8MBOS8MB120MB120MB(b)(b)分配之后分配之后分配之后分配之后OS8MBOS8MBP210MBP210MBP140MBP140MBP410MBP410MBP320MBP320MBP620MBP620MBP510MBP510MB10MB10MB(c)P1(c)P1、P3P3、P5P5结束结束结束结束OS8MBOS8MBP210MBP210
47、MBP410MBP410MBP620MBP620MB40MB40MB20MB20MB10MB10MB10MB10MB动态划分与分配算法动态划分与分配算法可可可可见见见见，动动动动态态态态分分分分区区区区的的的的分分分分区区区区长长长长度度度度和和和和数数数数目目目目都都都都是是是是可可可可变变变变的的的的。为为为为了了了了实实实实施施施施存存存存储储储储分分分分配配配配，系系系系统统统统必必必必须须须须维维维维护护护护一一一一张张张张空空空空闲闲闲闲分分分分区表，登记内存中的各个空闲分区。区表，登记内存中的各个空闲分区。区表，登记内存中的各个空闲分区。区表，登记内存中的各个空闲分区。空闲分区首
48、址空闲分区首址空闲分区首址空闲分区首址空闲分区长度空闲分区长度空闲分区长度空闲分区长度808012012027027040404004009090510510200200动态划分与分配算法动态划分与分配算法采采采采用用用用动动动动态态态态划划划划分分分分技技技技术术术术，为为为为进进进进程程程程分分分分配配配配存存存存储储储储空空空空间间间间的的的的过过过过程较复杂。程较复杂。程较复杂。程较复杂。当当当当系系系系统统统统中中中中有有有有多多多多个个个个满满满满足足足足进进进进程程程程大大大大小小小小的的的的空空空空闲闲闲闲分分分分区区区区时时时时，如何为进程选择一个分区合适的分区呢？如何为进程
49、选择一个分区合适的分区呢？如何为进程选择一个分区合适的分区呢？如何为进程选择一个分区合适的分区呢？目前几种较典型的分区分配方案：目前几种较典型的分区分配方案：目前几种较典型的分区分配方案：目前几种较典型的分区分配方案：首次适应算法首次适应算法(FFA：FirstFitAlgorithm)基基基基本本本本思思思思想想想想：总总总总是是是是从从从从内内内内存存存存的的的的某某某某一一一一端端端端（一一一一般般般般从从从从低低低低地地地地址址址址端端端端）开开开开始始始始查查查查找找找找，选选选选择择择择一一一一个个个个超超超超过过过过进进进进程程程程申申申申请请请请大大大大小小小小的空闲分区。的空
50、闲分区。的空闲分区。的空闲分区。为为为为此此此此，可可可可以以以以将将将将空空空空闲闲闲闲分分分分区区区区表表表表中中中中登登登登记记记记的的的的空空空空闲闲闲闲分分分分区区区区按按按按照照照照其其其其起起起起始始始始地地地地址址址址由由由由小小小小到到到到大大大大的的的的次次次次序序序序依依依依次次次次排排排排列列列列。系系系系统统统统查查查查找找找找空空空空闲闲闲闲分分分分区区区区时时时时，从从从从表表表表头头头头开开开开始始始始查查查查找找找找，取取取取第第第第一一一一个个个个满足要求的分区分配给进程。满足要求的分区分配给进程。满足要求的分区分配给进程。满足要求的分区分配给进程。首次适应
51、算法首次适应算法(FFA：FirstFitAlgorithm)若若若若找找找找到到到到的的的的空空空空闲闲闲闲分分分分区区区区恰恰恰恰好好好好与与与与进进进进程程程程申申申申请请请请的的的的存存存存储储储储空空空空间间间间大大大大小小小小相相相相等等等等，或或或或分分分分配配配配给给给给该该该该进进进进程程程程以以以以后后后后，仅仅仅仅剩剩剩剩下下下下一一一一个个个个非非非非常常常常小小小小的的的的空空空空间间间间（小小小小于于于于系系系系统统统统设设设设置置置置的的的的阈阈阈阈值值值值），则则则则将将将将该分区全部分配给申请进程。该分区全部分配给申请进程。该分区全部分配给申请进程。该分区全部
52、分配给申请进程。否否否否则则则则，系系系系统统统统将将将将该该该该分分分分区区区区划划划划分分分分为为为为两两两两个个个个分分分分区区区区，一一一一个个个个分分分分区区区区的的的的长长长长度度度度等等等等于于于于进进进进程程程程申申申申请请请请的的的的空空空空间间间间大大大大小小小小，并并并并将将将将其其其其分分分分配配配配给给给给申申申申请请请请进进进进程程程程。然然然然后后后后，将将将将另另另另一一一一个个个个子子子子分分分分区区区区链链链链接接接接到到到到空闲分区链表中。空闲分区链表中。空闲分区链表中。空闲分区链表中。首次适应算法首次适应算法(FFA：FirstFitAlgorithm)
53、优优点点：尽尽量量使使用用低低地地址址空空间间，因因而而在在高高地地址址的的空空间间可可能能会会保保留留较较大大的的空空闲闲分分区区。所所以以，大大进进程程申申请请的的存存储储空空间间大大都都能能在在高地址端得到满足。高地址端得到满足。缺缺点点：由由于于每每次次只只简简单单地地使使用用找找到到的的第第一一个个分分区区，结结果果可可能能导导致致将将较较大大的的空空闲闲分区不断地分割为较小的空闲分区。分区不断地分割为较小的空闲分区。外零头：紧凑外零头：紧凑动态划分技术解决了静态划分技术的内零头。动态划分技术解决了静态划分技术的内零头。动态划分技术解决了静态划分技术的内零头。动态划分技术解决了静态划
54、分技术的内零头。可可可可能能能能产产产产生生生生很很很很多多多多较较较较小小小小的的的的分分分分区区区区：外外外外零零零零头头头头(External(ExternalFragment)Fragment)。紧紧紧紧凑凑凑凑(Compaction)(Compaction)：把把把把内内内内存存存存中中中中的的的的所所所所有有有有空空空空闲闲闲闲分分分分区区区区拼拼拼拼接接接接成成成成一一一一个个个个较较较较大大大大的的的的空空空空闲闲闲闲分分分分区区区区。即即即即把把把把内内内内存存存存中中中中的的的的所所所所有有有有进进进进程程程程移移移移到到到到内内内内存存存存的的的的某某某某一一一一端端端端
55、；所所所所有有有有空空空空闲闲闲闲分分分分区区区区移移移移到到到到另一端另一端另一端另一端例例例例如如如如，将将将将如如如如图图图图3.7(a)3.7(a)所所所所示示示示的的的的内内内内存存存存空空空空间间间间进进进进行行行行紧紧紧紧凑凑凑凑以后的效果见图以后的效果见图以后的效果见图以后的效果见图3.83.8所示所示所示所示。图图3.8利用紧凑技术消除外零头利用紧凑技术消除外零头(a)紧凑之前紧凑之前24MB10MBOS8MBP716MBP210MBP410MBP610MB20MB10MB(b)紧凑以后紧凑以后64MBOS8MBP716MBP210MBP410MBP610MB下次适应算法下次
56、适应算法(NFA: Next-Fit Algorithm) 首次适应算法每次都从低地址端开始查找空闲首次适应算法每次都从低地址端开始查找空闲首次适应算法每次都从低地址端开始查找空闲首次适应算法每次都从低地址端开始查找空闲分区，总是频繁使用内存的某一端，某些大进分区，总是频繁使用内存的某一端，某些大进分区，总是频繁使用内存的某一端，某些大进分区，总是频繁使用内存的某一端，某些大进程申请的大分区需要很长时间才能在内存的另程申请的大分区需要很长时间才能在内存的另程申请的大分区需要很长时间才能在内存的另程申请的大分区需要很长时间才能在内存的另一端找到。一端找到。一端找到。一端找到。能否均衡使用整个内存
57、空间，加快大分区的查能否均衡使用整个内存空间，加快大分区的查能否均衡使用整个内存空间，加快大分区的查能否均衡使用整个内存空间，加快大分区的查找速度呢？找速度呢？找速度呢？找速度呢？下次适应算法能记住上次分配分区的位置，下下次适应算法能记住上次分配分区的位置，下下次适应算法能记住上次分配分区的位置，下下次适应算法能记住上次分配分区的位置，下一次实施分配时，从上一次的分配位置之后开一次实施分配时，从上一次的分配位置之后开一次实施分配时，从上一次的分配位置之后开一次实施分配时，从上一次的分配位置之后开始查找，选择一个大小足够的空闲分区。始查找，选择一个大小足够的空闲分区。始查找，选择一个大小足够的空
58、闲分区。始查找，选择一个大小足够的空闲分区。 下次适应算法下次适应算法(NFA: Next-Fit Algorithm)该算法常常会导致内存中缺乏大分区，该算法常常会导致内存中缺乏大分区，因为它会均衡地利用空闲分区，包括分因为它会均衡地利用空闲分区，包括分割较大的空闲分区。从而使得大进程无割较大的空闲分区。从而使得大进程无法装入内存运行。法装入内存运行。下次适应算法可能会导致大量的外零头，下次适应算法可能会导致大量的外零头，需要较频繁地实施紧凑操作。需要较频繁地实施紧凑操作。 最佳适应算法最佳适应算法(BFA：Best Fit Algorithm) 总是选择满足申请要求且长度最小的空闲分区。总
59、是选择满足申请要求且长度最小的空闲分区。总是选择满足申请要求且长度最小的空闲分区。总是选择满足申请要求且长度最小的空闲分区。为为为为了了了了提提提提高高高高查查查查找找找找效效效效率率率率，可可可可以以以以将将将将所所所所有有有有的的的的空空空空闲闲闲闲分分分分区区区区按按按按照照照照长长长长度度度度由由由由小小小小大大大大到到到到的的的的次次次次序序序序依依依依次次次次排排排排列列列列在在在在空空空空闲闲闲闲分分分分区区区区表表表表中。中。中。中。为为为为进进进进程程程程分分分分配配配配存存存存储储储储空空空空间间间间时时时时，从从从从表表表表头头头头开开开开始始始始查查查查找找找找，第第第
60、第一一一一个个个个满满满满足足足足进进进进程程程程申申申申请请请请存存存存储储储储空空空空间间间间大大大大小小小小的的的的分分分分区区区区就就就就是是是是最最最最适合的分区。适合的分区。适合的分区。适合的分区。最佳适应算法最佳适应算法(BFA：Best Fit Algorithm) 优点：尽量不分割大的空闲分区优点：尽量不分割大的空闲分区缺点：可能会形成大量较小的、难以再缺点：可能会形成大量较小的、难以再分配的分区分配的分区 大量的外零头。大量的外零头。最佳适应算法并非是最好的算法。最佳适应算法并非是最好的算法。 最差适应算法最差适应算法(WFA：WorstFitAlgorithm)选择满足申
61、请要求且长度最大的空闲分区，使选择满足申请要求且长度最大的空闲分区，使选择满足申请要求且长度最大的空闲分区，使选择满足申请要求且长度最大的空闲分区，使分割出来的剩余空闲分区较大。分割出来的剩余空闲分区较大。分割出来的剩余空闲分区较大。分割出来的剩余空闲分区较大。为了提高系统效率，可将系统中所有的空闲分为了提高系统效率，可将系统中所有的空闲分为了提高系统效率，可将系统中所有的空闲分为了提高系统效率，可将系统中所有的空闲分区按照长度由大到小的次序依次排列在空闲分区按照长度由大到小的次序依次排列在空闲分区按照长度由大到小的次序依次排列在空闲分区按照长度由大到小的次序依次排列在空闲分区表中。区表中。区
62、表中。区表中。为进程分配存储空间时，从表头开始查找，选为进程分配存储空间时，从表头开始查找，选为进程分配存储空间时，从表头开始查找，选为进程分配存储空间时，从表头开始查找，选择第一个满足进程需要的分区。择第一个满足进程需要的分区。择第一个满足进程需要的分区。择第一个满足进程需要的分区。如果第一个空闲分区小于进程申请空间的大小，如果第一个空闲分区小于进程申请空间的大小，如果第一个空闲分区小于进程申请空间的大小，如果第一个空闲分区小于进程申请空间的大小，则不能立即为进程分配存储空间。则不能立即为进程分配存储空间。则不能立即为进程分配存储空间。则不能立即为进程分配存储空间。最差适应算法最差适应算法(
63、WFA：WorstFitAlgorithm)优点：可以避免形成大量较小外零头，优点：可以避免形成大量较小外零头，优点：可以避免形成大量较小外零头，优点：可以避免形成大量较小外零头，但但但但它它它它总总总总是是是是分分分分割割割割大大大大的的的的空空空空闲闲闲闲分分分分区区区区。当当当当遇遇遇遇到到到到大大大大进进进进程程程程申申申申请大空间时，无法找到一个足够大的空闲分区。请大空间时，无法找到一个足够大的空闲分区。请大空间时，无法找到一个足够大的空闲分区。请大空间时，无法找到一个足够大的空闲分区。换换换换句句句句话话话话说说说说，在在在在大大大大进进进进程程程程面面面面前前前前，内内内内存存存
64、存中中中中所所所所谓谓谓谓的的的的较较较较大大大大空闲分区也是外零头了。空闲分区也是外零头了。空闲分区也是外零头了。空闲分区也是外零头了。例如例如当当系系统统进进行行到到如如图图3.6(c)所所示示的的情情形形时时，若若有有一一个个进进程程P7申申请请大大小小为为16MB的的存存储储空间。空间。分分别别采采用用上上述述4种种算算法法进进行行分分配配，如如图图所所示，分析结果。示，分析结果。图图图图3.73.7动态划分的动态划分的动态划分的动态划分的4 4种分配算法种分配算法种分配算法种分配算法(a)FFA(a)FFA或或或或 WFAWFA24MB24MB10MB10MBOS8MBOS8MBP7
65、16MBP716MBP210MBP210MBP410MBP410MBP610MBP610MB20MB20MB10MB10MB(b)NFA(b)NFA24MB24MB10MB10MBOS8MBOS8MBP716MBP716MBP210MBP210MBP410MBP410MBP610MBP610MB20MB20MB10MB10MB此次分此次分此次分此次分配位置配位置配位置配位置上次分上次分上次分上次分配位置配位置配位置配位置(c)BFA(c)BFA10MB10MBOS8MBOS8MBP210MBP210MBP716MBP716MBP410MBP410MBP610MBP610MB10MB10MB40
66、MB40MB4MB4MB伙伴系统伙伴系统(BuddySystem) 静态划分方案限制了系统中活跃进的数目。并静态划分方案限制了系统中活跃进的数目。并静态划分方案限制了系统中活跃进的数目。并静态划分方案限制了系统中活跃进的数目。并且，只能运行不超过分区大小的进程，如果进且，只能运行不超过分区大小的进程，如果进且，只能运行不超过分区大小的进程，如果进且，只能运行不超过分区大小的进程，如果进程远远小于分区大小，则内存空间的利用率非程远远小于分区大小，则内存空间的利用率非程远远小于分区大小，则内存空间的利用率非程远远小于分区大小，则内存空间的利用率非常低。常低。常低。常低。动态划分方案使存储管理复杂化
67、，并且需要系动态划分方案使存储管理复杂化，并且需要系动态划分方案使存储管理复杂化，并且需要系动态划分方案使存储管理复杂化，并且需要系统付出紧凑外零头的额外开销。统付出紧凑外零头的额外开销。统付出紧凑外零头的额外开销。统付出紧凑外零头的额外开销。伙伴系统：综合静态划分技术和动态划分技术伙伴系统：综合静态划分技术和动态划分技术伙伴系统：综合静态划分技术和动态划分技术伙伴系统：综合静态划分技术和动态划分技术的优点的优点的优点的优点伙伴系统内存的用户可用空间为伙伴系统内存的用户可用空间为伙伴系统内存的用户可用空间为伙伴系统内存的用户可用空间为2 2u u 。系统总是为进程分配大小为系统总是为进程分配大
68、小为系统总是为进程分配大小为系统总是为进程分配大小为2 2i i的一个空闲分区。的一个空闲分区。的一个空闲分区。的一个空闲分区。其中其中其中其中miUmiU，2 2mm是系统允许的最小分区尺寸。是系统允许的最小分区尺寸。是系统允许的最小分区尺寸。是系统允许的最小分区尺寸。如果进程申请的存储空间大小为如果进程申请的存储空间大小为如果进程申请的存储空间大小为如果进程申请的存储空间大小为k k，且，且，且，且2 2i-1i-1 kk22i i, ,则将整个则将整个则将整个则将整个2 2i i大小的分区分配给它。大小的分区分配给它。大小的分区分配给它。大小的分区分配给它。否则，该分区被分割成大小相等（
69、否则，该分区被分割成大小相等（否则，该分区被分割成大小相等（否则，该分区被分割成大小相等（ 2 2i-1i-1 ）的两）的两）的两）的两个分区。再判断个分区。再判断个分区。再判断个分区。再判断k k是否满足条件：是否满足条件：是否满足条件：是否满足条件：2 2i-2i-2k2内存空间，失败；内存空间，失败；内存空间，失败；内存空间，失败；若当前无尺寸为若当前无尺寸为若当前无尺寸为若当前无尺寸为2 2i i的空闲分区，则：的空闲分区，则：的空闲分区，则：的空闲分区，则：(1)(1)将将将将i i变变变变为为为为i+1i+1，查查查查找找找找一一一一个个个个尺尺尺尺寸寸寸寸为为为为2 2i+1i+
70、1的的的的空空空空闲闲闲闲分分分分区区区区。若存在，转若存在，转若存在，转若存在，转(2)(2)执行执行执行执行; ;否则，继续执行否则，继续执行否则，继续执行否则，继续执行(1)(1)；等分等分等分等分2 2i+1i+1空闲分区空闲分区空闲分区空闲分区: :产生两个产生两个产生两个产生两个2 2i i的伙伴分区；的伙伴分区；的伙伴分区；的伙伴分区； 把其中一个把其中一个把其中一个把其中一个2 2i i的伙伴分区作为空闲分区；的伙伴分区作为空闲分区；的伙伴分区作为空闲分区；的伙伴分区作为空闲分区；(4)(4)另一个另一个另一个另一个2 2i i 空闲分区分配给进程，结束。空闲分区分配给进程，结
71、束。空闲分区分配给进程，结束。空闲分区分配给进程，结束。伙伴系统存储空间的回收伙伴系统存储空间的回收 当当当当进进进进程程程程执执执执行行行行完完完完毕毕毕毕，释释释释放放放放一一一一个个个个尺尺尺尺寸寸寸寸为为为为2 2i i的的的的分分分分区区区区时时时时，系统用下面的算法回收该分区：系统用下面的算法回收该分区：系统用下面的算法回收该分区：系统用下面的算法回收该分区：如果被回收分区的伙伴分区非空闲，那么保留如果被回收分区的伙伴分区非空闲，那么保留如果被回收分区的伙伴分区非空闲，那么保留如果被回收分区的伙伴分区非空闲，那么保留该分区为一个独立的空闲分区，否则该分区为一个独立的空闲分区，否则该
72、分区为一个独立的空闲分区，否则该分区为一个独立的空闲分区，否则11 合合合合并并并并回回回回收收收收分分分分区区区区及及及及其其其其伙伙伙伙伴伴伴伴分分分分区区区区，从从从从而而而而得得得得到到到到一一一一个个个个尺寸为尺寸为尺寸为尺寸为2 2i+1i+1的空闲分区；的空闲分区；的空闲分区；的空闲分区；22系统再次调用本算法回收上一步得到的尺寸系统再次调用本算法回收上一步得到的尺寸系统再次调用本算法回收上一步得到的尺寸系统再次调用本算法回收上一步得到的尺寸为为为为2 2i+1i+1 的空闲分区。的空闲分区。的空闲分区。的空闲分区。 例如例如有进程有进程P1、P2、P3、P4、P5相继申请、相继
73、申请、释放空间。释放空间。系统分配、回收（合并）伙伴分区的过系统分配、回收（合并）伙伴分区的过程如图所示：程如图所示：P1申请申请100KBP2申请申请200KBP3申请申请120KBP4申请申请300KB系统初始状态系统初始状态P2、P3结束结束P5申请申请160KBP1执行结束执行结束P5执行结束执行结束P4执行结束执行结束1MBP1128KB256KB512KBP1128KBP2512KBP1P3P2512KBP1P3P2P4P1128KB256KBP4P1128KBP5P4256KBP5P4512KBP41MB图图3.9一个伙伴系统的内存分配与回收过程一个伙伴系统的内存分配与回收过程3
74、.3 3.3 程序装入技术程序装入技术 可执行程序的生成步骤可执行程序的生成步骤图图3.10 3.10 高级程序处理过程高级程序处理过程源程序源程序目标模块目标模块编译编译库函数库函数装入模块装入模块链接链接编辑编辑执行执行目标模块目标模块内存内存可执行程序的装入可执行程序的装入 ？如何装入待执行的程序及其所需的数据？如何装入待执行的程序及其所需的数据？如何装入待执行的程序及其所需的数据？如何装入待执行的程序及其所需的数据？ 何时将程序的逻辑地址转换为物理地址何时将程序的逻辑地址转换为物理地址何时将程序的逻辑地址转换为物理地址何时将程序的逻辑地址转换为物理地址3 3 3 3种装入方式：绝对装入
75、、重定位装入和运行种装入方式：绝对装入、重定位装入和运行种装入方式：绝对装入、重定位装入和运行种装入方式：绝对装入、重定位装入和运行时动态装入。时动态装入。时动态装入。时动态装入。 绝对装入绝对装入程序运行之前，按照程序的逻辑地址，程序运行之前，按照程序的逻辑地址，将程序和数据装入内存指定的地方。将程序和数据装入内存指定的地方。实现简单，无须进行逻辑地址到物理地实现简单，无须进行逻辑地址到物理地址的变换。址的变换。绝对装入绝对装入缺点：缺点：缺点：缺点：程序每次必须装入同一内存区；程序每次必须装入同一内存区；程序每次必须装入同一内存区；程序每次必须装入同一内存区；程序员必须事先了解内存的使用情
76、况，根据内程序员必须事先了解内存的使用情况，根据内程序员必须事先了解内存的使用情况，根据内程序员必须事先了解内存的使用情况，根据内存情况确定程序的逻辑地址；存情况确定程序的逻辑地址；存情况确定程序的逻辑地址；存情况确定程序的逻辑地址；程序的修改（增加或删除指令）将引起整个程程序的修改（增加或删除指令）将引起整个程程序的修改（增加或删除指令）将引起整个程程序的修改（增加或删除指令）将引起整个程序中指令地址的变动；序中指令地址的变动；序中指令地址的变动；序中指令地址的变动；程序中的所有存储引用，例如函数调用或过程程序中的所有存储引用，例如函数调用或过程程序中的所有存储引用，例如函数调用或过程程序中
77、的所有存储引用，例如函数调用或过程调用等，在装入之前都必须转换为物理地址，调用等，在装入之前都必须转换为物理地址，调用等，在装入之前都必须转换为物理地址，调用等，在装入之前都必须转换为物理地址，这不利于存储共享。这不利于存储共享。这不利于存储共享。这不利于存储共享。重定位装入重定位装入允允许许将将程程序序装装入入与与逻逻辑辑地地址址不不同同的的物物理理内内存存空空间间。即即程程序序可可以以装装入入到到内内存存的的任任何何位位置置，其其逻逻辑辑地地址址与与装装入入内内存存后后的的物物理地址无直接关系。理地址无直接关系。但但是是，必必须须进进行行地地址址映映射射，将将逻逻辑辑地地址址转换为物理地址
78、。转换为物理地址。静静态态重重定定位位技技术术：地地址址映映射射在在程程序序装装入入时进行，以后不再更改程序地址。时进行，以后不再更改程序地址。重定位装入重定位装入有有有有利利利利于于于于程程程程序序序序代代代代码码码码和和和和数数数数据据据据的的的的共共共共享享享享。因因因因为为为为装装装装入入入入程程程程序序序序时时时时，可可可可以以以以将将将将其其其其中中中中的的的的某某某某些些些些存存存存储储储储引引引引用用用用的的的的逻逻逻逻辑辑辑辑地地地地址址址址映映映映射为内存中已有的共享区的物理地址。射为内存中已有的共享区的物理地址。射为内存中已有的共享区的物理地址。射为内存中已有的共享区的物
79、理地址。但但但但是是是是，静静静静态态态态重重重重定定定定位位位位不不不不允允允允许许许许程程程程序序序序在在在在内内内内存存存存中中中中移移移移动动动动。这这这这不不不不便便便便于于于于进进进进程程程程交交交交换换换换和和和和紧紧紧紧凑凑凑凑拼拼拼拼接接接接操操操操作作作作，也也也也很很很很难难难难实实实实现现现现多多多多道道道道程程程程序序序序环环环环境境境境下下下下，多多多多个个个个程程程程序序序序同同同同时时时时装装装装入入入入内内内内存存存存的的的的要求。要求。要求。要求。故，重定位装入方式只适合于单道程序环境。故，重定位装入方式只适合于单道程序环境。故，重定位装入方式只适合于单道程
80、序环境。故，重定位装入方式只适合于单道程序环境。运行时动态装入运行时动态装入指指指指，程程程程序序序序的的的的地地地地址址址址转转转转换换换换不不不不是是是是在在在在装装装装入入入入时时时时进进进进行行行行，而而而而是是是是在程序运行时动态进行。在程序运行时动态进行。在程序运行时动态进行。在程序运行时动态进行。运运运运行行行行时时时时动动动动态态态态装装装装入入入入需需需需要要要要硬硬硬硬件件件件支支支支持持持持，即即即即重重重重定定定定位位位位寄寄寄寄存存存存器，用于保存程序在内存中的起始地址。器，用于保存程序在内存中的起始地址。器，用于保存程序在内存中的起始地址。器，用于保存程序在内存中的
81、起始地址。程程程程序序序序被被被被执执执执行行行行时时时时，通通通通过过过过重重重重定定定定位位位位寄寄寄寄存存存存器器器器内内内内的的的的起起起起始始始始物物物物理理理理地地地地址址址址和和和和指指指指令令令令或或或或数数数数据据据据的的的的逻逻逻逻辑辑辑辑地地地地址址址址计计计计算算算算其其其其物物物物理理理理地地地地址。址。址。址。运运运运行行行行时时时时动动动动态态态态装装装装入入入入有有有有利利利利于于于于多多多多道道道道程程程程序序序序环环环环境境境境下下下下，进进进进程程程程的换进的换进的换进的换进/ / / /换出及实现紧凑技术。换出及实现紧凑技术。换出及实现紧凑技术。换出及实
82、现紧凑技术。 可执行程序的链接形成可执行程序的链接形成 ？ 目标模块如何链接成装入模块呢目标模块如何链接成装入模块呢静态链接静态链接动态链接动态链接：装入时动态链接和运行时动：装入时动态链接和运行时动态链接态链接 静态链接静态链接指指指指，程程程程序序序序被被被被装装装装入入入入内内内内存存存存之之之之前前前前，必必必必须须须须完完完完全全全全链链链链接接接接成成成成一一一一个个个个装装装装入入入入模模模模块块块块，将将将将其其其其中中中中的的的的存存存存储储储储引引引引用用用用全全全全部部部部转转转转换换换换为为为为相相相相对对对对地地地地址址址址跳跳跳跳转转转转语语语语句句句句。并并并并将
83、将将将多多多多个个个个目目目目标标标标模模模模块块块块链链链链接接接接成成成成为为为为一一一一个个个个模模模模块块块块，使使使使装装装装入入入入模模模模块块块块中中中中的的的的每每每每一一一一条条条条指指指指令令令令具具具具有有有有相相相相对于整个模块的第一条语句的逻辑地址。对于整个模块的第一条语句的逻辑地址。对于整个模块的第一条语句的逻辑地址。对于整个模块的第一条语句的逻辑地址。静态链接生成的装入模块可以采用重定位装入静态链接生成的装入模块可以采用重定位装入静态链接生成的装入模块可以采用重定位装入静态链接生成的装入模块可以采用重定位装入或运行时动态装入方式。或运行时动态装入方式。或运行时动态
84、装入方式。或运行时动态装入方式。静态链接需要花费大量的处理机时间。而其中静态链接需要花费大量的处理机时间。而其中静态链接需要花费大量的处理机时间。而其中静态链接需要花费大量的处理机时间。而其中的很多模块将不会运行，浪费存储空间和处理的很多模块将不会运行，浪费存储空间和处理的很多模块将不会运行，浪费存储空间和处理的很多模块将不会运行，浪费存储空间和处理机时间。机时间。机时间。机时间。 链接链接图图3.11目标模块链接成装入模块目标模块链接成装入模块模块模块1ifx1thencallmm1elsecallmm2模块模块mm1模块模块mm2(a)目标模块目标模块模块模块1ifx1thenelse模块
85、模块mm1模块模块mm2(b)装入模块装入模块？执行？执行？执行？执行动态链接动态链接指指，不不用用事事先先链链接接所所有有目目标标模模块块形形成成一一个个完完备备的的装装入入模模块块，而而是是生生成成一一个个含含有有未未被被链链接接的的外外部部模模块块引引用用的的装装入入模模块块，这这些些外外部部模模块块可可以以在在装装入入时时链链接接，或或运运行时链接。行时链接。装入时动态链接装入时动态链接指指指指，当当当当系系系系统统统统装装装装入入入入含含含含有有有有未未未未链链链链接接接接的的的的外外外外部部部部模模模模块块块块引引引引用用用用的的的的装装装装入入入入模模模模块块块块时时时时，每每每
86、每当当当当遇遇遇遇到到到到一一一一个个个个外外外外部部部部模模模模块块块块引引引引用用用用，则则则则查查查查找找找找相相相相应应应应的的的的目目目目标标标标模模模模块块块块。将将将将其其其其装装装装入入入入内内内内存存存存，并并并并将将将将模模模模块块块块内内内内的的的的指指指指令令令令地地地地址址址址转转转转换换换换为为为为相相相相对对对对于于于于整整整整个个个个装装装装入入入入模模模模块块块块起起起起始地址的相对地址。始地址的相对地址。始地址的相对地址。始地址的相对地址。优优优优点点点点：有有有有利利利利于于于于目目目目标标标标模模模模块块块块的的的的更更更更新新新新与与与与升升升升级级级
87、级；有有有有利利利利于于于于代代代代码码码码共共共共享享享享；有有有有利利利利于于于于扩扩扩扩充充充充软软软软件件件件的的的的功功功功能能能能，可可可可以以以以将将将将扩扩扩扩充部分作为动态链接模块。充部分作为动态链接模块。充部分作为动态链接模块。充部分作为动态链接模块。但但但但是是是是，可可可可能能能能链链链链接接接接一一一一些些些些不不不不会会会会执执执执行行行行的的的的模模模模块块块块，浪浪浪浪费费费费存存存存储空间和处理机时间。储空间和处理机时间。储空间和处理机时间。储空间和处理机时间。运行时动态链接运行时动态链接指，外部模块引用直至程序执行时才装入内存，指，外部模块引用直至程序执行时
88、才装入内存，指，外部模块引用直至程序执行时才装入内存，指，外部模块引用直至程序执行时才装入内存，并链接到装入模块中，进行地址转换。并链接到装入模块中，进行地址转换。并链接到装入模块中，进行地址转换。并链接到装入模块中，进行地址转换。可以解决静态链接和装入时动态链接都面临的可以解决静态链接和装入时动态链接都面临的可以解决静态链接和装入时动态链接都面临的可以解决静态链接和装入时动态链接都面临的存储空间和处理机时间浪费问题，不需要执行存储空间和处理机时间浪费问题，不需要执行存储空间和处理机时间浪费问题，不需要执行存储空间和处理机时间浪费问题，不需要执行的模块就不会装入内存。的模块就不会装入内存。的模
89、块就不会装入内存。的模块就不会装入内存。广广广广泛泛泛泛用用用用于于于于事事事事务务务务处处处处理理理理系系系系统统统统，如如如如航航航航空空空空售售售售票票票票系系系系统统统统、银银银银行管理系统等。行管理系统等。行管理系统等。行管理系统等。操操操操作作作作系系系系统统统统自自自自身身身身的的的的一一一一些些些些特特特特殊殊殊殊处处处处理理理理例例例例程程程程，如如如如错错错错误误误误处处处处理例程，也无需事先全部装入内存。理例程，也无需事先全部装入内存。理例程，也无需事先全部装入内存。理例程，也无需事先全部装入内存。3.4 3.4 简单存储管理技术简单存储管理技术 简单存储简单存储相对于虚
90、拟存储而言，指为了实现简单，执行相对于虚拟存储而言，指为了实现简单，执行相对于虚拟存储而言，指为了实现简单，执行相对于虚拟存储而言，指为了实现简单，执行之前，操作系统必须将待执行的程序全部装入之前，操作系统必须将待执行的程序全部装入之前，操作系统必须将待执行的程序全部装入之前，操作系统必须将待执行的程序全部装入内存。内存。内存。内存。然而，现代操作系统大都支持虚拟存储功能，然而，现代操作系统大都支持虚拟存储功能，然而，现代操作系统大都支持虚拟存储功能，然而，现代操作系统大都支持虚拟存储功能，允许进程装入部分程序即可开始执行，其余部允许进程装入部分程序即可开始执行，其余部允许进程装入部分程序即可
91、开始执行，其余部允许进程装入部分程序即可开始执行，其余部分保留在外存。当执行所需的部分不在内存时，分保留在外存。当执行所需的部分不在内存时，分保留在外存。当执行所需的部分不在内存时，分保留在外存。当执行所需的部分不在内存时，中断进程执行，使之阻塞等待，直到相应部分中断进程执行，使之阻塞等待，直到相应部分中断进程执行，使之阻塞等待，直到相应部分中断进程执行，使之阻塞等待，直到相应部分装入内存。装入内存。装入内存。装入内存。？ 程序在内存中如何组织程序在内存中如何组织连连续续存存储储 : : 需需要要内内存存中中的的一一块块连连续续的的、足够大的分区。足够大的分区。如如果果内内存存中中没没有有足足
92、够够大大的的连连续续空空闲闲分分区区，但但存存在在总总量量足足够够的的独独立立小小分分区区，即即外外零零头头。系系统统要要么么拒拒绝绝分分配配空空间间，要要么么采采用用紧凑技术紧凑技术拼接外零头。拼接外零头。非非连连续续存存储储：允允许许进进程程的的程程序序和和数数据据分分别装在内存的不同分区中。别装在内存的不同分区中。必必须须登登记记一一个个进进程程分分到到的的所所有有分分区区的的位位置置、大大小小、使使用用情情况况（如如是是否否共共享享等等）等信息。等信息。常常用用的的非非连连续续存存储储技技术术：分分页页存存储储技技术术、分段存储技术及其结合。分段存储技术及其结合。图图3.12 3.12
93、 内存的内存的连续存储与非连续存储连续存储与非连续存储OS进程进程P基地址基地址(a)(a)连续存储连续存储进程进程P（2）OS进程进程P（1）进程进程P（n）进程的组成进程的组成基地址基地址长度长度P(1)2604200P(2)1240300P(n)6500300(b)(b)非非连续存储连续存储连续存储管理连续存储管理 最简单的存储管理技术最简单的存储管理技术要求系统配置专门的硬件实现快速地址要求系统配置专门的硬件实现快速地址转换和存储保护。转换和存储保护。处理机硬件处理机硬件基址寄存器基址寄存器基址寄存器基址寄存器(Baseregister)(Baseregister)界限寄存器界限寄存器
94、界限寄存器界限寄存器(Boundsregister)(Boundsregister)连续存储管理连续存储管理 基址寄存器基址寄存器基址寄存器基址寄存器：存放当前执行进程所在分区的物：存放当前执行进程所在分区的物：存放当前执行进程所在分区的物：存放当前执行进程所在分区的物理存储单元的起始地址。理存储单元的起始地址。理存储单元的起始地址。理存储单元的起始地址。 界限寄存器界限寄存器界限寄存器界限寄存器：存放当前执行进程所在分区最后：存放当前执行进程所在分区最后：存放当前执行进程所在分区最后：存放当前执行进程所在分区最后一个物理存储单元的地址，限定进程的执行范一个物理存储单元的地址，限定进程的执行范
95、一个物理存储单元的地址，限定进程的执行范一个物理存储单元的地址，限定进程的执行范围，保护其他进程不被非法访问。围，保护其他进程不被非法访问。围，保护其他进程不被非法访问。围，保护其他进程不被非法访问。基址寄存器和界限寄存器被多个进程共享，只基址寄存器和界限寄存器被多个进程共享，只基址寄存器和界限寄存器被多个进程共享，只基址寄存器和界限寄存器被多个进程共享，只有当前执行进程才使用它们。有当前执行进程才使用它们。有当前执行进程才使用它们。有当前执行进程才使用它们。 装入时，进程分区的基地址值和分区的最后一装入时，进程分区的基地址值和分区的最后一装入时，进程分区的基地址值和分区的最后一装入时，进程分
96、区的基地址值和分区的最后一个物理存储单元的地址值，分别填入该进程个物理存储单元的地址值，分别填入该进程个物理存储单元的地址值，分别填入该进程个物理存储单元的地址值，分别填入该进程PCBPCBPCBPCB的相应字段中。的相应字段中。的相应字段中。的相应字段中。当进程被调度执行时，将当进程被调度执行时，将当进程被调度执行时，将当进程被调度执行时，将PCBPCBPCBPCB中对应的进程基中对应的进程基中对应的进程基中对应的进程基地址值写入基址寄存器中，并将进程获得的内地址值写入基址寄存器中，并将进程获得的内地址值写入基址寄存器中，并将进程获得的内地址值写入基址寄存器中，并将进程获得的内存分区最大地址
97、值，填入界限寄存器中。存分区最大地址值，填入界限寄存器中。存分区最大地址值，填入界限寄存器中。存分区最大地址值，填入界限寄存器中。当进程被交换出当进程被交换出当进程被交换出当进程被交换出/ / / /换入内存时，上述两个地址换入内存时，上述两个地址换入内存时，上述两个地址换入内存时，上述两个地址值也会发生改变。值也会发生改变。值也会发生改变。值也会发生改变。 地址映射与存储保护地址映射与存储保护 逻辑地址转换成物理地址逻辑地址转换成物理地址逻辑地址转换成物理地址逻辑地址转换成物理地址 取基址寄存器中的值，加上逻辑地址值，生取基址寄存器中的值，加上逻辑地址值，生取基址寄存器中的值，加上逻辑地址值
98、，生取基址寄存器中的值，加上逻辑地址值，生成一个物理地址成一个物理地址成一个物理地址成一个物理地址 地址越界检查地址越界检查地址越界检查地址越界检查 取取取取界界界界限限限限寄寄寄寄存存存存器器器器中中中中的的的的值值值值，与与与与第第第第一一一一步步步步计计计计算算算算的的的的结结结结果果果果进进进进行行行行比比比比较较较较。如如如如果果果果生生生生成成成成的的的的物物物物理理理理地地地地址址址址超超超超出出出出了了了了界界界界限限限限范范范范围围围围，产产产产生生生生一一一一个个个个中中中中断断断断，报报报报告告告告地地地地址址址址越越越越界界界界。否否否否则则则则，继继继继续该指令的执行
99、。续该指令的执行。续该指令的执行。续该指令的执行。程序部分程序部分数据部分数据部分内存内存基址寄存器基址寄存器加法器加法器逻辑地址逻辑地址界限寄存器界限寄存器比较器比较器越界中断越界中断物理地址物理地址图图3.13连续存储管理的地址转换和越界检查连续存储管理的地址转换和越界检查 简单分页存储管理简单分页存储管理 连续存储：存在外零头，浪费存储空间。连续存储：存在外零头，浪费存储空间。“紧凑紧凑”需要系统额外开销。需要系统额外开销。非连续存储：允许将一个进程的程序和非连续存储：允许将一个进程的程序和数据离散存储在多个独立的分区中，消数据离散存储在多个独立的分区中，消除了外零头。除了外零头。基本原
100、理基本原理 分分页页存存储储管管理理技技术术是是一一种种特特殊殊的的固固定定分分区方法。区方法。系系统统事事先先将将物物理理内内存存划划分分成成许许多多尺尺寸寸相相等等的的页页框框(PageFrame)，并并将将进进程程分分割割成成许许多多大大小小相相同同的的页页面面(Page)，页页面面与与页框大小相同。页框大小相同。分区分区分区分区：进程的逻辑地址空间是连续的、一维的、：进程的逻辑地址空间是连续的、一维的、：进程的逻辑地址空间是连续的、一维的、：进程的逻辑地址空间是连续的、一维的、线性地址，进程的每一条指令和数据的地址相线性地址，进程的每一条指令和数据的地址相线性地址，进程的每一条指令和数
101、据的地址相线性地址，进程的每一条指令和数据的地址相对于第一条语句的地址而定。对于第一条语句的地址而定。对于第一条语句的地址而定。对于第一条语句的地址而定。分页分页分页分页：进程被分割成许多页面。每个页面内的：进程被分割成许多页面。每个页面内的：进程被分割成许多页面。每个页面内的：进程被分割成许多页面。每个页面内的指令和数据是连续的，它们的地址相对于其所指令和数据是连续的，它们的地址相对于其所指令和数据是连续的，它们的地址相对于其所指令和数据是连续的，它们的地址相对于其所属页的第一条语句的地址，称为属页的第一条语句的地址，称为属页的第一条语句的地址，称为属页的第一条语句的地址，称为页内偏移量页内
102、偏移量页内偏移量页内偏移量。逻辑地址被分为两部分：逻辑地址被分为两部分：逻辑地址被分为两部分：逻辑地址被分为两部分：页号页号页号页号和和和和页内偏移量页内偏移量页内偏移量页内偏移量 页号页号页内偏移量页内偏移量151090图图3.14分页管理的逻辑地址表示分页管理的逻辑地址表示当当一一个个进进程程被被装装入入物物理理内内存存时时，系系统统将将为为该该进进程程的的每每个个页页面面分分配配一一个个独独立立的的页页框。框。同同一一个个进进程程的的多多个个页页面面不不必必存存放放在在连连续续的多个页框中。的多个页框中。例如例如假设内存能提供假设内存能提供假设内存能提供假设内存能提供16161616个空
103、闲页框，进程个空闲页框，进程个空闲页框，进程个空闲页框，进程P1P1P1P1被分割被分割被分割被分割成成成成4 4 4 4个页面，装入内存中的个页面，装入内存中的个页面，装入内存中的个页面，装入内存中的0 0 0 0号至号至号至号至3 3 3 3号页框。进号页框。进号页框。进号页框。进程程程程P2P2P2P2被分割成被分割成被分割成被分割成3 3 3 3个页面，装入个页面，装入个页面，装入个页面，装入4 4 4 4号至号至号至号至6 6 6 6号页框。号页框。号页框。号页框。进程进程进程进程P3P3P3P3被装入被装入被装入被装入7 7 7 7号至号至号至号至12121212号页框，如图号页框
104、，如图号页框，如图号页框，如图3.15(a)3.15(a)3.15(a)3.15(a)所所所所示。示。示。示。此时，进程此时，进程此时，进程此时，进程P4P4P4P4请求分配请求分配请求分配请求分配5 5 5 5个页框大小的存储空个页框大小的存储空个页框大小的存储空个页框大小的存储空间，但内存只有间，但内存只有间，但内存只有间，但内存只有3 3 3 3个空闲页框。于是，将暂时个空闲页框。于是，将暂时个空闲页框。于是，将暂时个空闲页框。于是，将暂时不运行的不运行的不运行的不运行的P2P2P2P2交换出内存，如图交换出内存，如图交换出内存，如图交换出内存，如图3.15(b)3.15(b)3.15(
105、b)3.15(b)所示。所示。所示。所示。然后，再将然后，再将然后，再将然后，再将P4P4P4P4装入装入装入装入4 4 4 4、5 5 5 5、6 6 6 6、13131313、14141414号页框，号页框，号页框，号页框，如图如图如图如图3.15(c)3.15(c)3.15(c)3.15(c)所示。所示。所示。所示。 图图3.15进程装入到离散的页框中进程装入到离散的页框中0123456789101112131415P1.2P1.1P1.0P1.3P2.0P2.1P2.2P3.0P3.1P3.2P3.3P3.4P3.5页框号页框号内存内存(a)依次装入依次装入P1、P2、P3P1P2P3
106、空闲空闲0123456789101112131415P1.2P1.1P1.0P1.3P3.0P3.1P3.2P3.3P3.4P3.5页框号页框号内存内存(b)换出换出P2P1空闲空闲P3空闲空闲0123456789101112131415P1.2P1.1P1.0P1.3P4.0P4.1P4.2P3.0P3.1P3.2P3.3P3.4P3.5P4.3P4.4页框号页框号内存内存(c)装入装入P4P1P4P3空闲空闲P4数据结构：页表数据结构：页表页页表表：系系统统为为每每个个进进程程建建立立一一张张页页面面映映射表。射表。用用于于记记载载进进程程的的各各页页面面到到物物理理内内存存中中页页框的映
107、射信息。框的映射信息。进进程程的的每每个个页页面面依依次次对对应应页页表表中中的的一一个个表表项项，其其中中包包含含相相应应页页在在内内存存中中对对应应的的物理页框号和页面存取控制权限等字段。物理页框号和页面存取控制权限等字段。页号页号页框号页框号00112233进程进程P1页表页表页号页号页框号页框号0-1-2-进程进程P2页表页表页号页号页框号页框号071829310411512进程进程P3页表页表页号页号页框号页框号041526313414进程进程P4页表页表图图3.16进程进程P1、P2、P3、P4的页表的页表数据结构：页框表数据结构：页框表空闲页框表：登记系统中剩下的空闲页空闲页框表
108、：登记系统中剩下的空闲页框情况框情况图图3.17空闲页框表空闲页框表151413地址变换地址变换硬件机制，实现逻辑地址到物理地址的转换硬件机制，实现逻辑地址到物理地址的转换硬件机制，实现逻辑地址到物理地址的转换硬件机制，实现逻辑地址到物理地址的转换分页系统中的地址变换过程如下：分页系统中的地址变换过程如下：分页系统中的地址变换过程如下：分页系统中的地址变换过程如下：（1 1 1 1） 根据逻辑地址根据逻辑地址根据逻辑地址根据逻辑地址, , , ,计算出页号和页内偏移量；计算出页号和页内偏移量；计算出页号和页内偏移量；计算出页号和页内偏移量；（2 2 2 2） 用用用用页页页页号号号号检检检检索
109、索索索页页页页表表表表，查查查查找找找找指指指指定定定定页页页页面面面面对对对对应应应应的的的的页框号；页框号；页框号；页框号；（3 3 3 3） 根根根根据据据据页页页页框框框框号号号号和和和和页页页页内内内内偏偏偏偏移移移移量量量量，计计计计算算算算出出出出物物物物理理理理地址。地址。地址。地址。页表寄存器页表寄存器页页页页表表表表寄寄寄寄存存存存器器器器：实实实实现现现现快快快快速速速速地地地地址址址址映映映映射射射射，存存存存储储储储执执执执行行行行进进进进程的页表起始地址。程的页表起始地址。程的页表起始地址。程的页表起始地址。页表寄存器设置在处理机硬件中。页表寄存器设置在处理机硬件中
110、。页表寄存器设置在处理机硬件中。页表寄存器设置在处理机硬件中。当当当当进进进进程程程程被被被被创创创创建建建建时时时时，其其其其页页页页表表表表起起起起始始始始地地地地址址址址记记记记载载载载于于于于进进进进程程程程PCBPCBPCBPCB中。中。中。中。当当当当进进进进程程程程被被被被调调调调度度度度执执执执行行行行时时时时，页页页页表表表表的的的的起起起起始始始始地地地地址址址址将将将将从从从从该该该该进程的进程的进程的进程的PCBPCBPCBPCB中取出，并填入页表寄存器中。中取出，并填入页表寄存器中。中取出，并填入页表寄存器中。中取出，并填入页表寄存器中。进进进进行行行行地地地地址址址
111、址变变变变换换换换时时时时，处处处处理理理理机机机机从从从从页页页页表表表表寄寄寄寄存存存存器器器器中中中中查查查查找找找找页表的地址。页表的地址。页表的地址。页表的地址。页号页号 偏移量偏移量逻辑地址逻辑地址物理地址物理地址页框号页框号 偏移量偏移量页表寄存器页表寄存器页表起始地址页表起始地址内存内存页框号页框号页表页表地址转换地址转换程序程序+偏偏移移量量图图3.18分页系统的地址变换过程分页系统的地址变换过程页框页框大页表大页表 大逻辑地址空间，页表非常大，需要占大逻辑地址空间，页表非常大，需要占用相当大的内存空间。用相当大的内存空间。比如，比如，32位逻辑地址空间，假设页面大位逻辑地址
112、空间，假设页面大小为小为4KB（212），则），则4GB（232）的逻辑）的逻辑地址空间将被划分成地址空间将被划分成220个页面。个页面。大页表大页表 若采用一级页表，则其内将包含若采用一级页表，则其内将包含若采用一级页表，则其内将包含若采用一级页表，则其内将包含1 1兆（兆（兆（兆（2 22020）个）个）个）个页表项。若按字节寻址，一个页表项占页表项。若按字节寻址，一个页表项占页表项。若按字节寻址，一个页表项占页表项。若按字节寻址，一个页表项占4B4B，则，则，则，则一级页表需要占用一级页表需要占用一级页表需要占用一级页表需要占用4MB4MB（2 22222）内存空间。）内存空间。）内存空
113、间。）内存空间。不可能将不可能将不可能将不可能将4MB4MB的页表保存在一个连续区中。的页表保存在一个连续区中。的页表保存在一个连续区中。的页表保存在一个连续区中。那么，如何处理大页表的存储与检索呢？那么，如何处理大页表的存储与检索呢？那么，如何处理大页表的存储与检索呢？那么，如何处理大页表的存储与检索呢？ 二级页表二级页表将一个大页表全部保存在内存中。将一个大页表全部保存在内存中。将一个大页表全部保存在内存中。将一个大页表全部保存在内存中。首先，将其分割，并离散地存储在内存的多个首先，将其分割，并离散地存储在内存的多个首先，将其分割，并离散地存储在内存的多个首先，将其分割，并离散地存储在内存
114、的多个页框中。页框中。页框中。页框中。为之建立二级页表，记录被分割的各个页面存为之建立二级页表，记录被分割的各个页面存为之建立二级页表，记录被分割的各个页面存为之建立二级页表，记录被分割的各个页面存储在哪些页框中，也称为外层页表（储在哪些页框中，也称为外层页表（储在哪些页框中，也称为外层页表（储在哪些页框中，也称为外层页表（OuterOuterPageTablePageTable）。）。）。）。对于对于对于对于4GB4GB的进程，若采用二级页表，则对应的的进程，若采用二级页表，则对应的的进程，若采用二级页表，则对应的的进程，若采用二级页表，则对应的二级页表结构如图：二级页表结构如图：二级页表结
115、构如图：二级页表结构如图：4GB的用户进程的用户进程4MB的一级页表的一级页表4KB的二级页表的二级页表图图3.194GB进程的二级页表结构进程的二级页表结构多级页表多级页表对于某些机器，二级页表也可能非常大。可以对于某些机器，二级页表也可能非常大。可以对于某些机器，二级页表也可能非常大。可以对于某些机器，二级页表也可能非常大。可以采用多级页表，对外层页表再进行分页，将各采用多级页表，对外层页表再进行分页，将各采用多级页表，对外层页表再进行分页，将各采用多级页表，对外层页表再进行分页，将各个页面离散地存储到不相邻接的物理页框中个页面离散地存储到不相邻接的物理页框中个页面离散地存储到不相邻接的物
116、理页框中个页面离散地存储到不相邻接的物理页框中虽然，对大页表而言，多级页表方法消除了对虽然，对大页表而言，多级页表方法消除了对虽然，对大页表而言，多级页表方法消除了对虽然，对大页表而言，多级页表方法消除了对较大的连续内存空间的需要，但并未解决大页较大的连续内存空间的需要，但并未解决大页较大的连续内存空间的需要，但并未解决大页较大的连续内存空间的需要，但并未解决大页表占用较大的内存空间的问题，建立多及页表表占用较大的内存空间的问题，建立多及页表表占用较大的内存空间的问题，建立多及页表表占用较大的内存空间的问题，建立多及页表反而会增加额外的存储空间。反而会增加额外的存储空间。反而会增加额外的存储空
117、间。反而会增加额外的存储空间。大页表大页表最好的解决办法是采用最好的解决办法是采用最好的解决办法是采用最好的解决办法是采用虚拟存储技术虚拟存储技术虚拟存储技术虚拟存储技术，内存中，内存中，内存中，内存中仅装入页表的一部分。仅装入页表的一部分。仅装入页表的一部分。仅装入页表的一部分。即只将当前需要的部分页表项装入内存，其余即只将当前需要的部分页表项装入内存，其余即只将当前需要的部分页表项装入内存，其余即只将当前需要的部分页表项装入内存，其余页表项驻留在磁盘上，需要时再将它们装入内页表项驻留在磁盘上，需要时再将它们装入内页表项驻留在磁盘上，需要时再将它们装入内页表项驻留在磁盘上，需要时再将它们装入
118、内存。存。存。存。若采用多级页表，对于正在运行的进程，必须若采用多级页表，对于正在运行的进程，必须若采用多级页表，对于正在运行的进程，必须若采用多级页表，对于正在运行的进程，必须将其外层页表调入内存，而内层页表只需调入将其外层页表调入内存，而内层页表只需调入将其外层页表调入内存，而内层页表只需调入将其外层页表调入内存，而内层页表只需调入几页就可以了。几页就可以了。几页就可以了。几页就可以了。反置页表反置页表(InvertedPageTable)一般情况下，系统从进程的角度为每个进程建一般情况下，系统从进程的角度为每个进程建一般情况下，系统从进程的角度为每个进程建一般情况下，系统从进程的角度为每
119、个进程建立一张页表，页表的表项按页号排序。立一张页表，页表的表项按页号排序。立一张页表，页表的表项按页号排序。立一张页表，页表的表项按页号排序。这种方法可能导致一个大进程的页表太大，占这种方法可能导致一个大进程的页表太大，占这种方法可能导致一个大进程的页表太大，占这种方法可能导致一个大进程的页表太大，占据大量的内存空间。据大量的内存空间。据大量的内存空间。据大量的内存空间。反置页表反置页表反置页表反置页表：从内存的角度建立页表，整个系统：从内存的角度建立页表，整个系统：从内存的角度建立页表，整个系统：从内存的角度建立页表，整个系统只有一张页表。页表的表项基于内存中的每一只有一张页表。页表的表项
120、基于内存中的每一只有一张页表。页表的表项基于内存中的每一只有一张页表。页表的表项基于内存中的每一个物理页框设置，页表项按页框号的顺序排序。个物理页框设置，页表项按页框号的顺序排序。个物理页框设置，页表项按页框号的顺序排序。个物理页框设置，页表项按页框号的顺序排序。其中还必须包含页框对应的页号及其隶属进程其中还必须包含页框对应的页号及其隶属进程其中还必须包含页框对应的页号及其隶属进程其中还必须包含页框对应的页号及其隶属进程的标识符等信息。的标识符等信息。的标识符等信息。的标识符等信息。 反置页表反置页表通常，反置页表需要包含成千上万个表项，利通常，反置页表需要包含成千上万个表项，利通常，反置页表
121、需要包含成千上万个表项，利通常，反置页表需要包含成千上万个表项，利用进程用进程用进程用进程IDID和页号检索其中某一个表项的速度很和页号检索其中某一个表项的速度很和页号检索其中某一个表项的速度很和页号检索其中某一个表项的速度很慢。慢。慢。慢。可以根据进程可以根据进程可以根据进程可以根据进程IDID和页号构建和页号构建和页号构建和页号构建HashHash表。表。表。表。HashHash表表表表的每一项指向反置页表中的某一项。的每一项指向反置页表中的某一项。的每一项指向反置页表中的某一项。的每一项指向反置页表中的某一项。但是，可能会出现多个逻辑地址被映射到一个但是，可能会出现多个逻辑地址被映射到一
122、个但是，可能会出现多个逻辑地址被映射到一个但是，可能会出现多个逻辑地址被映射到一个HashHash表项的情况。需要通过链接指针将多个冲表项的情况。需要通过链接指针将多个冲表项的情况。需要通过链接指针将多个冲表项的情况。需要通过链接指针将多个冲突的映射链接起来。突的映射链接起来。突的映射链接起来。突的映射链接起来。一般，冲突的表项一般只有一项，或两项。一般，冲突的表项一般只有一项，或两项。一般，冲突的表项一般只有一项，或两项。一般，冲突的表项一般只有一项，或两项。 地址变换地址变换首先，以进程首先，以进程首先，以进程首先，以进程IDIDIDID和页号为参数，代入和页号为参数，代入和页号为参数，代
123、入和页号为参数，代入HashHashHashHash函数函数函数函数进行计算。进行计算。进行计算。进行计算。然后，根据计算结果，检索反置页表。若检索然后，根据计算结果，检索反置页表。若检索然后，根据计算结果，检索反置页表。若检索然后，根据计算结果，检索反置页表。若检索完整个反置页表都未找到与之匹配的表项，表完整个反置页表都未找到与之匹配的表项，表完整个反置页表都未找到与之匹配的表项，表完整个反置页表都未找到与之匹配的表项，表明此页尚未装入内存。明此页尚未装入内存。明此页尚未装入内存。明此页尚未装入内存。若系统支持虚拟存储技术，则产生请求调页中若系统支持虚拟存储技术，则产生请求调页中若系统支持虚
124、拟存储技术，则产生请求调页中若系统支持虚拟存储技术，则产生请求调页中断。若系统不支持虚拟存储技术，则表示地址断。若系统不支持虚拟存储技术，则表示地址断。若系统不支持虚拟存储技术，则表示地址断。若系统不支持虚拟存储技术，则表示地址出错。出错。出错。出错。当检索到反置页表中的对应表项时，将其中的当检索到反置页表中的对应表项时，将其中的当检索到反置页表中的对应表项时，将其中的当检索到反置页表中的对应表项时，将其中的页框号与逻辑地址中的偏移量相加，构成物理页框号与逻辑地址中的偏移量相加，构成物理页框号与逻辑地址中的偏移量相加，构成物理页框号与逻辑地址中的偏移量相加，构成物理地址。地址。地址。地址。 物
125、理地址物理地址偏移量偏移量页框号页框号逻辑地址逻辑地址偏移量偏移量页号页号HashHash表表页号页号 进程进程IDID指针指针页框号页框号反置页表反置页表图图3.20 3.20 利用反置页表进行地址变换利用反置页表进行地址变换 快表快表 分页系统：处理机每次存取指令或数据至少需分页系统：处理机每次存取指令或数据至少需分页系统：处理机每次存取指令或数据至少需分页系统：处理机每次存取指令或数据至少需要访问两次物理内存要访问两次物理内存要访问两次物理内存要访问两次物理内存第一次访问页表，第二次存取指令或数据第一次访问页表，第二次存取指令或数据第一次访问页表，第二次存取指令或数据第一次访问页表，第二
126、次存取指令或数据为了提高地址变换速度，为进程页表设置一个为了提高地址变换速度，为进程页表设置一个为了提高地址变换速度，为进程页表设置一个为了提高地址变换速度，为进程页表设置一个专用的高速缓冲存储器，称为快表、专用的高速缓冲存储器，称为快表、专用的高速缓冲存储器，称为快表、专用的高速缓冲存储器，称为快表、TLB(TranslationLookasideBuffer)TLB(TranslationLookasideBuffer)，或联想存，或联想存，或联想存，或联想存储器（储器（储器（储器（AssociativeMemoryAssociativeMemory） 快表的工作原理快表的工作原理快快快快
127、表表表表的的的的工工工工作作作作原原原原理理理理类类类类似似似似于于于于系系系系统统统统中中中中的的的的数数数数据据据据高高高高速速速速缓缓缓缓存存存存(cache)(cache)，其其其其中中中中专专专专门门门门保保保保存存存存当当当当前前前前进进进进程程程程最最最最近近近近访访访访问问问问过过过过的的的的一组页表项。一组页表项。一组页表项。一组页表项。根根根根据据据据局局局局部部部部性性性性原原原原理理理理，在在在在一一一一个个个个很很很很短短短短的的的的时时时时间间间间段段段段内内内内，程程程程序的执行总是局部于某一个范围。序的执行总是局部于某一个范围。序的执行总是局部于某一个范围。序的
128、执行总是局部于某一个范围。即即即即，进进进进程程程程最最最最近近近近访访访访问问问问过过过过的的的的页页页页面面面面在在在在不不不不久久久久的的的的将将将将来来来来还还还还可可可可能被访问。能被访问。能被访问。能被访问。分页系统地址转换分页系统地址转换通通通通过过过过根根根根据据据据逻逻逻逻辑辑辑辑地地地地址址址址中中中中的的的的页页页页号号号号，查查查查找找找找快快快快表表表表中中中中是是是是否否否否存在对应的页表项。存在对应的页表项。存在对应的页表项。存在对应的页表项。若若若若快快快快表表表表中中中中存存存存在在在在该该该该表表表表项项项项，称称称称为为为为命命命命中中中中（hithit）
129、，取取取取出出出出其其其其中中中中的的的的页页页页框框框框号号号号，加加加加上上上上页页页页内内内内偏偏偏偏移移移移量量量量，计计计计算算算算出出出出物物物物理理理理地址。地址。地址。地址。若若若若快快快快表表表表中中中中不不不不存存存存在在在在该该该该页页页页表表表表项项项项，称称称称为为为为命命命命中中中中失失失失败败败败，则则则则再再再再查查查查找找找找页页页页表表表表，找找找找到到到到逻逻逻逻辑辑辑辑地地地地址址址址中中中中指指指指定定定定页页页页号号号号对对对对应应应应的的的的页页页页框框框框号号号号。同同同同时时时时，更更更更新新新新快快快快表表表表，将将将将该该该该表表表表项项项
130、项插插插插入入入入快快快快表表表表中。并计算物理地址中。并计算物理地址中。并计算物理地址中。并计算物理地址图图3.21具有快表的分页系统地址变换过程具有快表的分页系统地址变换过程页号页号 偏移量偏移量逻辑地址逻辑地址物理地址物理地址页框号页框号 偏移量偏移量偏偏移移量量内存内存快表快表页框号页框号页表页表页框页框TLB命中命中命中失败命中失败页面与页框大小页面与页框大小分分页页系系统统中中，页页面面 = = 页页框框。页页框框的的大大小小由由计计算算机机的的硬硬件件逻逻辑辑定定义义。通通常常，页页框框的的大大小小是是2 2的的幂幂次次个个字字节节，且且常常在在512B512B（2 29 9）4
131、KB4KB（2 21212）之之间间，典典型型的的页页框框大大小为小为1KB1KB。将页框大小设置为将页框大小设置为2 2的幂次，可以简化处的幂次，可以简化处理机中地址变换硬件逻辑的设计与实现。理机中地址变换硬件逻辑的设计与实现。页面与页框大小页面与页框大小影影影影响响响响页页页页面面面面与与与与页页页页框框框框大大大大小小小小的的的的主主主主要要要要因因因因素素素素：页页页页内内内内零零零零头头头头、地址转换速度和页面交换效率。地址转换速度和页面交换效率。地址转换速度和页面交换效率。地址转换速度和页面交换效率。较较较较小小小小的的的的页页页页面面面面有有有有利利利利于于于于减减减减少少少少内
132、内内内零零零零头头头头，从从从从而而而而有有有有利利利利于于于于提提提提高高高高内内内内存存存存的的的的利利利利用用用用率率率率。然然然然而而而而，较较较较小小小小的的的的页页页页面面面面也也也也将将将将导导导导致致致致页页页页表表表表过过过过大大大大，从从从从而而而而降降降降低低低低处处处处理理理理机机机机访访访访问问问问页页页页表表表表时时时时的的的的命命命命中中中中率率率率(Hit Rate)(Hit Rate)(Hit Rate)(Hit Rate)。块块块块越越越越大大大大，内内内内/ / / /外外外外存存存存之之之之间间间间的的的的数数数数据据据据交交交交换换换换效效效效率率率率
133、越越越越高高高高。因因因因此此此此，对对对对于于于于支支支支持持持持交交交交换换换换技技技技术术术术的的的的系系系系统统统统，较较较较大大大大的的的的页页页页面面面面有利于提高页面换进有利于提高页面换进有利于提高页面换进有利于提高页面换进/ / / /换出内存的效率。换出内存的效率。换出内存的效率。换出内存的效率。对分页存储管理的评价对分页存储管理的评价彻彻彻彻底底底底消消消消除除除除了了了了外外外外零零零零头头头头, , , ,仅仅仅仅存存存存在在在在很很很很少少少少的的的的内内内内零零零零头头头头, , , , 提提提提高了内存利用率。高了内存利用率。高了内存利用率。高了内存利用率。分分分
134、分页页页页操操操操作作作作由由由由系系系系统统统统自自自自动动动动进进进进行行行行, , , ,一一一一个个个个页页页页面面面面不不不不能能能能实实实实现现现现某某某某种种种种逻逻逻逻辑辑辑辑功功功功能能能能。用用用用户户户户看看看看到到到到的的的的逻逻逻逻辑辑辑辑地地地地址址址址是是是是一一一一维维维维的的的的，无法调试执行其中的某个子程序或子函数。无法调试执行其中的某个子程序或子函数。无法调试执行其中的某个子程序或子函数。无法调试执行其中的某个子程序或子函数。采采采采用用用用分分分分页页页页技技技技术术术术不不不不易易易易于于于于实实实实现现现现存存存存储储储储共共共共享享享享，也也也也不
135、不不不便便便便于于于于程序的动态链接。程序的动态链接。程序的动态链接。程序的动态链接。简单分段存储管理简单分段存储管理 基基基基于于于于模模模模块块块块化化化化程程程程序序序序设设设设计计计计时时时时，常常常常常常常常需需需需要要要要将将将将一一一一个个个个大大大大任任任任务务务务划划划划分分分分成成成成若若若若干干干干相相相相对对对对独独独独立立立立的的的的子子子子任任任任务务务务，对对对对应应应应于于于于子子子子任任任任务编写子程序，称为段务编写子程序，称为段务编写子程序，称为段务编写子程序，称为段(Segment)(Segment)(Segment)(Segment)。每每每每个个个个子
136、子子子程程程程序序序序可可可可以以以以独独独独立立立立地地地地编编编编辑辑辑辑、编编编编译译译译、链链链链接接接接和和和和执执执执行。行。行。行。各各各各个个个个子子子子程程程程序序序序由由由由实实实实现现现现的的的的功功功功能能能能决决决决定定定定，长长长长度度度度各各各各不不不不相相相相同同同同。执执执执行行行行时时时时，根根根根据据据据实实实实际际际际需需需需要要要要，将将将将若若若若干干干干子子子子程程程程序序序序链链链链接接接接成成成成一个大程序。一个大程序。一个大程序。一个大程序。基本原理基本原理程序由若干逻辑段组成，每个段有自己的名字程序由若干逻辑段组成，每个段有自己的名字程序由
137、若干逻辑段组成，每个段有自己的名字程序由若干逻辑段组成，每个段有自己的名字和长度。程序的逻辑地址是由段名（段号）和和长度。程序的逻辑地址是由段名（段号）和和长度。程序的逻辑地址是由段名（段号）和和长度。程序的逻辑地址是由段名（段号）和段内偏移量决定。每个段的逻辑地址从段内偏移量决定。每个段的逻辑地址从段内偏移量决定。每个段的逻辑地址从段内偏移量决定。每个段的逻辑地址从0 0 0 0开始开始开始开始编址编址编址编址 段号段号段内偏移量段内偏移量151090图图3.22分段管理的逻辑地址表示分段管理的逻辑地址表示系系统统采采用用动动态态划划分分技技术术，将将物物理理内内存存动动态地划分成许多尺寸不
138、相等的分区。态地划分成许多尺寸不相等的分区。当当一一个个进进程程被被装装入入物物理理内内存存时时，系系统统将将为为该该进进程程的的每每一一段段独独立立地地分分配配一一个个分分区区。同同一一进进程程的的多多个个段段不不必必存存放放在在连连续续的的多多个分区中。个分区中。分段系统的基本数据结构分段系统的基本数据结构 段表段表段表段表 : :每个进程建立一个，用于描述进程的分每个进程建立一个，用于描述进程的分每个进程建立一个，用于描述进程的分每个进程建立一个，用于描述进程的分段情况，记载进程的各个段到物理内存中分区段情况，记载进程的各个段到物理内存中分区段情况，记载进程的各个段到物理内存中分区段情况
139、，记载进程的各个段到物理内存中分区的映射情况。其中包含段号、段长、段基址以的映射情况。其中包含段号、段长、段基址以的映射情况。其中包含段号、段长、段基址以的映射情况。其中包含段号、段长、段基址以及对本段的存取控制权限等信息。及对本段的存取控制权限等信息。及对本段的存取控制权限等信息。及对本段的存取控制权限等信息。空空空空闲闲闲闲分分分分区区区区表表表表 : :用用用用于于于于记记记记载载载载物物物物理理理理内内内内存存存存中中中中的的的的空空空空闲闲闲闲分分分分区区区区情况情况情况情况图图3.23分段存储示例分段存储示例P2.1P1.0P1.2P1.1P2.0(a)分段存储分段存储050010
140、0执行执行存取控制存取控制段基址段基址段长段长段号段号1200800只读只读22001000执行执行(b)进程进程P1的段表的段表01001200执行执行存取控制存取控制段基址段基址段长段长段号段号1200600执行执行(c)进程进程P2的段表的段表地址变换和存储保护地址变换和存储保护 （1 1）根根根根据据据据逻逻逻逻辑辑辑辑地地地地址址址址中中中中的的的的段段段段号号号号检检检检索索索索进进进进程程程程段段段段表表表表，获得指定段对应的段表项；获得指定段对应的段表项；获得指定段对应的段表项；获得指定段对应的段表项；（2 2）判判判判断断断断是是是是否否否否地地地地址址址址越越越越界界界界。
141、比比比比较较较较逻逻逻逻辑辑辑辑地地地地址址址址中中中中的的的的段段段段内内内内偏偏偏偏移移移移量量量量与与与与段段段段表表表表项项项项中中中中的的的的段段段段长长长长，若若若若超超超超过过过过段段段段的的的的长长长长度度度度，则则则则产产产产生生生生存存存存储储储储保保保保护护护护中中中中断断断断（该该该该中中中中断断断断将将将将由由由由操操操操作作作作系系系系统进行处理）；否则，转（统进行处理）；否则，转（统进行处理）；否则，转（统进行处理）；否则，转（3 3）；）；）；）；（3 3）把把把把逻逻逻逻辑辑辑辑地地地地址址址址中中中中的的的的段段段段内内内内偏偏偏偏移移移移量量量量与与与与段
142、段段段表表表表表表表表项项项项中中中中的段基址相加，从而得到物理地址。的段基址相加，从而得到物理地址。的段基址相加，从而得到物理地址。的段基址相加，从而得到物理地址。 段表寄存器段表寄存器段表同样被保存在物理内存中。段表同样被保存在物理内存中。段表同样被保存在物理内存中。段表同样被保存在物理内存中。段表寄存器段表寄存器段表寄存器段表寄存器 ：实现快速地址变换，用来存放实现快速地址变换，用来存放实现快速地址变换，用来存放实现快速地址变换，用来存放当前执行进程的段表在物理内存中的起始地址。当前执行进程的段表在物理内存中的起始地址。当前执行进程的段表在物理内存中的起始地址。当前执行进程的段表在物理内
143、存中的起始地址。当创建进程，将进程的程序和数据装入内存时，当创建进程，将进程的程序和数据装入内存时，当创建进程，将进程的程序和数据装入内存时，当创建进程，将进程的程序和数据装入内存时，系统为之建立段表，并将段表的起始地址填入系统为之建立段表，并将段表的起始地址填入系统为之建立段表，并将段表的起始地址填入系统为之建立段表，并将段表的起始地址填入进程的进程的进程的进程的PCBPCBPCBPCB中。中。中。中。当进程被调度执行时，取出其当进程被调度执行时，取出其当进程被调度执行时，取出其当进程被调度执行时，取出其PCBPCBPCBPCB中的段表首中的段表首中的段表首中的段表首址，填入段表寄存器中。址
144、，填入段表寄存器中。址，填入段表寄存器中。址，填入段表寄存器中。 图图3.24分段系统的地址变换过程分段系统的地址变换过程内存内存物理地址物理地址段基址段基址+偏移量偏移量偏偏移移量量段号段号 偏移量偏移量逻辑地址逻辑地址段表寄存器段表寄存器段表起始地址段表起始地址+段表段表段长段长 段基址段基址+越界越界判断判断中断中断越界越界正常正常段段段段分段系统的快表分段系统的快表在分段系统中，为了访问内存中的一条指令或在分段系统中，为了访问内存中的一条指令或在分段系统中，为了访问内存中的一条指令或在分段系统中，为了访问内存中的一条指令或数据，需要两次访问内存：数据，需要两次访问内存：数据，需要两次访
145、问内存：数据，需要两次访问内存： 第一次，访问内存中的段表，获得对应段的起始第一次，访问内存中的段表，获得对应段的起始第一次，访问内存中的段表，获得对应段的起始第一次，访问内存中的段表，获得对应段的起始地址。根据段的起始地址和段内偏移量，计算出物理地址。根据段的起始地址和段内偏移量，计算出物理地址。根据段的起始地址和段内偏移量，计算出物理地址。根据段的起始地址和段内偏移量，计算出物理地址。地址。地址。地址。 第二次，根据物理地址，访问对应存储单元的指第二次，根据物理地址，访问对应存储单元的指第二次，根据物理地址，访问对应存储单元的指第二次，根据物理地址，访问对应存储单元的指令或数据。令或数据。
146、令或数据。令或数据。为了提高处理机的效率，类似分页系统的快表，为了提高处理机的效率，类似分页系统的快表，为了提高处理机的效率，类似分页系统的快表，为了提高处理机的效率，类似分页系统的快表，可以为分段系统增加一个快表，用于保存最近可以为分段系统增加一个快表，用于保存最近可以为分段系统增加一个快表，用于保存最近可以为分段系统增加一个快表，用于保存最近使用过的段表项。使用过的段表项。使用过的段表项。使用过的段表项。 对分段系统的评价对分段系统的评价 有效消除了内零头，提高了存储利用率。有效消除了内零头，提高了存储利用率。有效消除了内零头，提高了存储利用率。有效消除了内零头，提高了存储利用率。允许子程
147、序独立编译和修改，而不需要重新编允许子程序独立编译和修改，而不需要重新编允许子程序独立编译和修改，而不需要重新编允许子程序独立编译和修改，而不需要重新编译或链接其它相关子程序。译或链接其它相关子程序。译或链接其它相关子程序。译或链接其它相关子程序。容易实现存储共享。容易实现存储共享。容易实现存储共享。容易实现存储共享。具有较高的安全保障。具有较高的安全保障。具有较高的安全保障。具有较高的安全保障。很容易满足程序段的动态增长需要很容易满足程序段的动态增长需要很容易满足程序段的动态增长需要很容易满足程序段的动态增长需要 。分页与分段技术的比较分页与分段技术的比较 都采用非连续存储，由地址映射实现地
148、址变换。都采用非连续存储，由地址映射实现地址变换。都采用非连续存储，由地址映射实现地址变换。都采用非连续存储，由地址映射实现地址变换。不同主要表现在：不同主要表现在：不同主要表现在：不同主要表现在：（1 1 1 1） 页是信息的物理单位，大小固定。段是信息的逻页是信息的物理单位，大小固定。段是信息的逻页是信息的物理单位，大小固定。段是信息的逻页是信息的物理单位，大小固定。段是信息的逻辑单位，各段的长度不固定。每一段都具有一定逻辑辑单位，各段的长度不固定。每一段都具有一定逻辑辑单位，各段的长度不固定。每一段都具有一定逻辑辑单位，各段的长度不固定。每一段都具有一定逻辑含义。含义。含义。含义。（2
149、2 2 2） 分页的地址空间是一维的，逻辑地址的划分由机分页的地址空间是一维的，逻辑地址的划分由机分页的地址空间是一维的，逻辑地址的划分由机分页的地址空间是一维的，逻辑地址的划分由机器硬件实现，对用户透明。分段的地址空间是二维或器硬件实现，对用户透明。分段的地址空间是二维或器硬件实现，对用户透明。分段的地址空间是二维或器硬件实现，对用户透明。分段的地址空间是二维或多维的，程序员知道段名和段内偏移量。多维的，程序员知道段名和段内偏移量。多维的，程序员知道段名和段内偏移量。多维的，程序员知道段名和段内偏移量。（3 3 3 3）分页活动源于系统管理物理内存的需要，在系统内）分页活动源于系统管理物理内
150、存的需要，在系统内）分页活动源于系统管理物理内存的需要，在系统内）分页活动源于系统管理物理内存的需要，在系统内部进行，由系统实施，用户看不见。分段活动源于用部进行，由系统实施，用户看不见。分段活动源于用部进行，由系统实施，用户看不见。分段活动源于用部进行，由系统实施，用户看不见。分段活动源于用户进行模块化程序设计的需要，在系统外部进行，由户进行模块化程序设计的需要，在系统外部进行，由户进行模块化程序设计的需要，在系统外部进行，由户进行模块化程序设计的需要，在系统外部进行，由用户实施，用户是知道的。用户实施，用户是知道的。用户实施，用户是知道的。用户实施，用户是知道的。 简单段页式存储管理简单段
151、页式存储管理 基本思想：采用分段方法组织用户程序，采用基本思想：采用分段方法组织用户程序，采用基本思想：采用分段方法组织用户程序，采用基本思想：采用分段方法组织用户程序，采用分页方法分配和管理内存。分页方法分配和管理内存。分页方法分配和管理内存。分页方法分配和管理内存。即，用户程序可以用模块化思想进行设计，一即，用户程序可以用模块化思想进行设计，一即，用户程序可以用模块化思想进行设计，一即，用户程序可以用模块化思想进行设计，一个用户序由若干段构成。系统将内存划分成固个用户序由若干段构成。系统将内存划分成固个用户序由若干段构成。系统将内存划分成固个用户序由若干段构成。系统将内存划分成固定大小的页
152、框，并将程序的每一段分割成若干定大小的页框，并将程序的每一段分割成若干定大小的页框，并将程序的每一段分割成若干定大小的页框，并将程序的每一段分割成若干页以后装入内存执行时。页以后装入内存执行时。页以后装入内存执行时。页以后装入内存执行时。逻辑地址逻辑地址在段页式系统中，进程的每一段被进一步分割在段页式系统中，进程的每一段被进一步分割在段页式系统中，进程的每一段被进一步分割在段页式系统中，进程的每一段被进一步分割成页面，段内代码和数据地址不再连续。成页面，段内代码和数据地址不再连续。成页面，段内代码和数据地址不再连续。成页面，段内代码和数据地址不再连续。逻辑地址由逻辑地址由逻辑地址由逻辑地址由3
153、 3部分组成：段号、段内页号、页部分组成：段号、段内页号、页部分组成：段号、段内页号、页部分组成：段号、段内页号、页内偏移量，如图内偏移量，如图内偏移量，如图内偏移量，如图段号段号段内页号段内页号页内偏移量页内偏移量图图3.25段页式系统的逻辑地址结构段页式系统的逻辑地址结构数据结构数据结构 用于管理的数据结构：段表、页表，如图用于管理的数据结构：段表、页表，如图用于管理的数据结构：段表、页表，如图用于管理的数据结构：段表、页表，如图图图3.26段页式系统的数据结构段页式系统的数据结构段段0段段1段段2用户程序用户程序段表段表03页表首址页表首址页表长度页表长度段号段号12内存内存OS0页号页
154、号 页框号页框号12页号页号 页框号页框号页表页表段表寄存器段表寄存器段表寄存器段表寄存器：加速地址变换，用于存放：加速地址变换，用于存放执行进程段表的起始地址。执行进程段表的起始地址。地址变换地址变换首先，从段表寄存器从获得进程段表的起始地首先，从段表寄存器从获得进程段表的起始地首先，从段表寄存器从获得进程段表的起始地首先，从段表寄存器从获得进程段表的起始地址，根据该地址，查找进程的段表。址，根据该地址，查找进程的段表。址，根据该地址，查找进程的段表。址，根据该地址，查找进程的段表。然后，根据逻辑地址指定的段号检索段表，找然后，根据逻辑地址指定的段号检索段表，找然后，根据逻辑地址指定的段号检
155、索段表，找然后，根据逻辑地址指定的段号检索段表，找到对应段的页表起始地址。到对应段的页表起始地址。到对应段的页表起始地址。到对应段的页表起始地址。再根据逻辑地址中指定的页号检索该页表，找再根据逻辑地址中指定的页号检索该页表，找再根据逻辑地址中指定的页号检索该页表，找再根据逻辑地址中指定的页号检索该页表，找到对应页所在的页框号。到对应页所在的页框号。到对应页所在的页框号。到对应页所在的页框号。最后，用页框号加上逻辑地址中指定的页内偏最后，用页框号加上逻辑地址中指定的页内偏最后，用页框号加上逻辑地址中指定的页内偏最后，用页框号加上逻辑地址中指定的页内偏移量，形成物理地址。移量，形成物理地址。移量，
156、形成物理地址。移量，形成物理地址。 图图3.27段页式系统的地址变换过程段页式系统的地址变换过程段表段表页表首址页表首址段号段号页内偏移量页内偏移量逻辑地址逻辑地址段内页号段内页号+物理地址物理地址页框号页框号+页内偏移量页内偏移量页表页表页框号页框号+偏偏移移量量内存内存页框页框页框页框页框页框段表寄存器段表寄存器段表起始地址段表起始地址快表快表第一次，访问段表，从中获得该段的页表首址；第一次，访问段表，从中获得该段的页表首址；第一次，访问段表，从中获得该段的页表首址；第一次，访问段表，从中获得该段的页表首址；第二次，访问页表，从中取出逻辑地址指定的第二次，访问页表，从中取出逻辑地址指定的第
157、二次，访问页表，从中取出逻辑地址指定的第二次，访问页表，从中取出逻辑地址指定的页面所在的页框号，并将该页框号和页内偏移页面所在的页框号，并将该页框号和页内偏移页面所在的页框号，并将该页框号和页内偏移页面所在的页框号，并将该页框号和页内偏移量相加，形成指令或数据的物理地址；量相加，形成指令或数据的物理地址；量相加，形成指令或数据的物理地址；量相加，形成指令或数据的物理地址；第三次访问内存，根据前面计算的物理地址，第三次访问内存，根据前面计算的物理地址，第三次访问内存，根据前面计算的物理地址，第三次访问内存，根据前面计算的物理地址，取出对应存储单元的指令或数据。取出对应存储单元的指令或数据。取出对
158、应存储单元的指令或数据。取出对应存储单元的指令或数据。可以在地址变换机构中增设一个高速缓冲寄存可以在地址变换机构中增设一个高速缓冲寄存可以在地址变换机构中增设一个高速缓冲寄存可以在地址变换机构中增设一个高速缓冲寄存器，其中保存最近使用过的页号及其所属的段器，其中保存最近使用过的页号及其所属的段器，其中保存最近使用过的页号及其所属的段器，其中保存最近使用过的页号及其所属的段号。号。号。号。具有快表的地址转换具有快表的地址转换首先，利用段号和页号检索该高速缓冲寄存器。首先，利用段号和页号检索该高速缓冲寄存器。首先，利用段号和页号检索该高速缓冲寄存器。首先，利用段号和页号检索该高速缓冲寄存器。若找到
159、匹配的表项，则可以从中获得相应页面若找到匹配的表项，则可以从中获得相应页面若找到匹配的表项，则可以从中获得相应页面若找到匹配的表项，则可以从中获得相应页面的页框号，加上页内偏移量，形成物理地址。的页框号，加上页内偏移量，形成物理地址。的页框号，加上页内偏移量，形成物理地址。的页框号，加上页内偏移量，形成物理地址。若该高速缓冲寄存器中未包含对应表项，则需若该高速缓冲寄存器中未包含对应表项，则需若该高速缓冲寄存器中未包含对应表项，则需若该高速缓冲寄存器中未包含对应表项，则需要访问段表及页表，计算出物理地址以后，从要访问段表及页表，计算出物理地址以后，从要访问段表及页表，计算出物理地址以后，从要访问
160、段表及页表，计算出物理地址以后，从相应存储单元获取指令或数据相应存储单元获取指令或数据相应存储单元获取指令或数据相应存储单元获取指令或数据。 对段页式存储管理方式的评价对段页式存储管理方式的评价 综合了分段和分页技术的优点，既能有效地利综合了分段和分页技术的优点，既能有效地利综合了分段和分页技术的优点，既能有效地利综合了分段和分页技术的优点，既能有效地利用存储空间，又能方便用户进行程序设计。用存储空间，又能方便用户进行程序设计。用存储空间，又能方便用户进行程序设计。用存储空间，又能方便用户进行程序设计。但是，实现段页式存储管理系统需要增加硬件但是，实现段页式存储管理系统需要增加硬件但是，实现段
161、页式存储管理系统需要增加硬件但是，实现段页式存储管理系统需要增加硬件成本，系统的复杂度和管理开销也大大增加。成本，系统的复杂度和管理开销也大大增加。成本，系统的复杂度和管理开销也大大增加。成本，系统的复杂度和管理开销也大大增加。因此，段页式存储管理技术适合于大、中型计因此，段页式存储管理技术适合于大、中型计因此，段页式存储管理技术适合于大、中型计因此，段页式存储管理技术适合于大、中型计算机系统，不太适合小型、微型计算机系统。算机系统，不太适合小型、微型计算机系统。算机系统，不太适合小型、微型计算机系统。算机系统，不太适合小型、微型计算机系统。3.5 3.5 虚拟存储管理技术虚拟存储管理技术 简
162、单存储：要求将一个进程所需的程序和数据简单存储：要求将一个进程所需的程序和数据简单存储：要求将一个进程所需的程序和数据简单存储：要求将一个进程所需的程序和数据全部装入内存方可执行。全部装入内存方可执行。全部装入内存方可执行。全部装入内存方可执行。这样的系统存在两个很严重的问题。这样的系统存在两个很严重的问题。这样的系统存在两个很严重的问题。这样的系统存在两个很严重的问题。其一，对于大进程，如果其所需内存空间超过了内存其一，对于大进程，如果其所需内存空间超过了内存其一，对于大进程，如果其所需内存空间超过了内存其一，对于大进程，如果其所需内存空间超过了内存的最大容量，则无法运行。的最大容量，则无法
163、运行。的最大容量，则无法运行。的最大容量，则无法运行。其二，对于多道程序系统，由于每一个进程需要全部其二，对于多道程序系统，由于每一个进程需要全部其二，对于多道程序系统，由于每一个进程需要全部其二，对于多道程序系统，由于每一个进程需要全部装入内存，使同时驻留内存的进程数量受到限制。虽装入内存，使同时驻留内存的进程数量受到限制。虽装入内存，使同时驻留内存的进程数量受到限制。虽装入内存，使同时驻留内存的进程数量受到限制。虽然也可以通过提高内存容量来解决，但是代价太高。然也可以通过提高内存容量来解决，但是代价太高。然也可以通过提高内存容量来解决，但是代价太高。然也可以通过提高内存容量来解决，但是代价
164、太高。如果能将一部分价格较低的外存空间当作内存如果能将一部分价格较低的外存空间当作内存如果能将一部分价格较低的外存空间当作内存如果能将一部分价格较低的外存空间当作内存使用，从逻辑上扩充内存容量。那么，将获得使用，从逻辑上扩充内存容量。那么，将获得使用，从逻辑上扩充内存容量。那么，将获得使用，从逻辑上扩充内存容量。那么，将获得更高的性价比。更高的性价比。更高的性价比。更高的性价比。虚拟存储技术的理论依据虚拟存储技术的理论依据 程程程程序序序序执执执执行行行行的的的的局局局局部部部部性性性性原原原原理理理理：程程程程序序序序的的的的执执执执行行行行总总总总是是是是呈呈呈呈现现现现局局局局部部部部性
165、性性性。即即即即，在在在在一一一一个个个个较较较较短短短短的的的的时时时时间间间间段段段段内内内内，程程程程序序序序的的的的执执执执行行行行仅仅仅仅限限限限于于于于某某某某个个个个部部部部分分分分；相相相相应应应应的的的的，它它它它所所所所访访访访问问问问的的的的存存存存储空间也局限于某个区域。储空间也局限于某个区域。储空间也局限于某个区域。储空间也局限于某个区域。因因因因此此此此，只只只只要要要要保保保保证证证证进进进进程程程程执执执执行行行行所所所所需需需需的的的的部部部部分分分分程程程程序序序序和和和和数数数数据驻留在内存，一段时间内进程都能顺利执行。据驻留在内存，一段时间内进程都能顺利
166、执行。据驻留在内存，一段时间内进程都能顺利执行。据驻留在内存，一段时间内进程都能顺利执行。实现虚拟存储的一般过程实现虚拟存储的一般过程 进程运行之前，仅需要将一部分页面或段装入进程运行之前，仅需要将一部分页面或段装入进程运行之前，仅需要将一部分页面或段装入进程运行之前，仅需要将一部分页面或段装入内存，便可启动运行，其余部分暂时保留在磁内存，便可启动运行，其余部分暂时保留在磁内存，便可启动运行，其余部分暂时保留在磁内存，便可启动运行，其余部分暂时保留在磁盘上。盘上。盘上。盘上。进程运行时，如果它所需要访问的页面（段）进程运行时，如果它所需要访问的页面（段）进程运行时，如果它所需要访问的页面（段）
167、进程运行时，如果它所需要访问的页面（段）已经装入内存，则可以继续执行下去；已经装入内存，则可以继续执行下去；已经装入内存，则可以继续执行下去；已经装入内存，则可以继续执行下去；如果其所需要访问的页面（段）尚未装入内存，如果其所需要访问的页面（段）尚未装入内存，如果其所需要访问的页面（段）尚未装入内存，如果其所需要访问的页面（段）尚未装入内存，则发生缺页（段）中断，进程阻塞。则发生缺页（段）中断，进程阻塞。则发生缺页（段）中断，进程阻塞。则发生缺页（段）中断，进程阻塞。此时，系统将启动请求调页（段）功能，将进此时，系统将启动请求调页（段）功能，将进此时，系统将启动请求调页（段）功能，将进此时，系
168、统将启动请求调页（段）功能，将进程所需的页（段）装入内存。程所需的页（段）装入内存。程所需的页（段）装入内存。程所需的页（段）装入内存。实现虚拟存储的一般过程实现虚拟存储的一般过程 如果当前内存已满，无法装入新的页如果当前内存已满，无法装入新的页（段），则还需要利用页（段）置换功（段），则还需要利用页（段）置换功能，将内存中暂时不用的页（段）交换能，将内存中暂时不用的页（段）交换到磁盘上，以腾出足够的内存空间。到磁盘上，以腾出足够的内存空间。再将进程所需的页（段）装入内存，唤再将进程所需的页（段）装入内存，唤醒阻塞的进程，使之重新参与调度执行。醒阻塞的进程，使之重新参与调度执行。 从外存装入页
169、从外存装入页/段段更新页更新页/段表段表交换页交换页/段段内存满内存满？是是否否缺页缺页/段中断段中断页页/段段在内存在内存是是否否进程执行进程执行图图3.28实现虚拟存储的典型过程实现虚拟存储的典型过程？什么是虚拟存储什么是虚拟存储通通通通过过过过系系系系统统统统提提提提供供供供的的的的缺缺缺缺页页页页/ / / /段段段段中中中中断断断断功功功功能能能能和和和和交交交交换换换换技技技技术术术术，动动动动态态态态装装装装入入入入进进进进程程程程的的的的程程程程序序序序代代代代码码码码和和和和数数数数据据据据，使使使使得得得得一一一一个个个个大大大大的的的的用用用用户户户户程程程程序序序序能能
170、能能在在在在一一一一个个个个相相相相对对对对较较较较小小小小的的的的内内内内存存存存空空空空间间间间中中中中运运运运行，也使得有限的内存能同时容纳更多的进程。行，也使得有限的内存能同时容纳更多的进程。行，也使得有限的内存能同时容纳更多的进程。行，也使得有限的内存能同时容纳更多的进程。习习习习惯惯惯惯上上上上，人人人人们们们们把把把把这这这这种种种种用用用用户户户户感感感感觉觉觉觉上上上上的的的的、由由由由实实实实际际际际内内内内存存存存和和和和部部部部分分分分外外外外存存存存共共共共同同同同构构构构成成成成的的的的存存存存储储储储空空空空间间间间称称称称为为为为虚虚虚虚拟拟拟拟存存存存储器储器
171、储器储器虚拟存储技术的技术支持虚拟存储技术的技术支持 首首先先，必必须须有有相相应应的的硬硬件件支支持持，用用以以实实现虚拟分页或虚拟分段存储管理。现虚拟分页或虚拟分段存储管理。其其次次，操操作作系系统统必必须须提提供供相相应应的的软软件件支支持持，管管理理页页或或段段在在内内存存和和外外存存之之间间的的移移动。动。虚拟存储的基本数据结构虚拟存储的基本数据结构 由于虚拟存储系统中，进程的程序代码和数据由于虚拟存储系统中，进程的程序代码和数据由于虚拟存储系统中，进程的程序代码和数据由于虚拟存储系统中，进程的程序代码和数据只有一部分在内存，另一部分保存在外存。只有一部分在内存，另一部分保存在外存。
172、只有一部分在内存，另一部分保存在外存。只有一部分在内存，另一部分保存在外存。在页在页在页在页/ / / /段表项中增加一个段表项中增加一个段表项中增加一个段表项中增加一个“ “存在存在存在存在” ”字段，其值字段，其值字段，其值字段，其值为为为为0 0 0 0或或或或1 1 1 1。增加一个增加一个增加一个增加一个“ “修改修改修改修改” ”字段，表明对应页字段，表明对应页字段，表明对应页字段，表明对应页/ / / /段自进段自进段自进段自进入内存以来是否被修改过。只有被修改过的页入内存以来是否被修改过。只有被修改过的页入内存以来是否被修改过。只有被修改过的页入内存以来是否被修改过。只有被修改
173、过的页/ / / /段才需要保存到外存，若需要将未修改过的段才需要保存到外存，若需要将未修改过的段才需要保存到外存，若需要将未修改过的段才需要保存到外存，若需要将未修改过的页页页页/ / / /段换出内存，只需要将新装入的页段换出内存，只需要将新装入的页段换出内存，只需要将新装入的页段换出内存，只需要将新装入的页/ / / /段直接段直接段直接段直接覆盖其存储区域，而不必将其内容保存到外存。覆盖其存储区域，而不必将其内容保存到外存。覆盖其存储区域，而不必将其内容保存到外存。覆盖其存储区域，而不必将其内容保存到外存。 图图3.29虚拟分页、分段及段页式存储系统的数据结构虚拟分页、分段及段页式存储
174、系统的数据结构页号页号页框号页框号存在存在修改修改其他控制其他控制(a)虚拟存储页表项虚拟存储页表项段号段号段长段长存在存在修改修改其他控制其他控制(b)虚拟存储段表项虚拟存储段表项段基址长段基址长(c)虚拟存储段页式系统的段表项和页表项虚拟存储段页式系统的段表项和页表项段号段号其他控制其他控制页表长度页表长度页表基址页表基址段表项段表项页号页号页框号页框号存在存在修改修改其他控制其他控制页表项页表项虚拟存储的好处虚拟存储的好处第第一一，可可以以运运行行大大程程序序，包包括括超超过过内内存存实际容量的大程序。实际容量的大程序。第第二二，可可以以在在有有限限的的物物理理内内存存中中运运行行更更多
175、多的的程程序序。多多道道程程序序系系统统的的度度不不再再受受到到物理内存空间的限制。物理内存空间的限制。虚拟存储的典型问题虚拟存储的典型问题抖动（抖动（thrashingthrashing）当当当当进进进进程程程程要要要要求求求求装装装装入入入入新新新新的的的的页页页页面面面面或或或或程程程程序序序序段段段段时时时时，如如如如果果果果当当当当前前前前没没没没有有有有足足足足够够够够的的的的空空空空闲闲闲闲空空空空间间间间，需需需需要要要要交交交交换换换换一一一一些些些些页页页页面面面面或或或或段段段段到到到到外外外外存存存存。如如如如果果果果被被被被交交交交换换换换出出出出去去去去的的的的页页
176、页页面面面面或或或或段段段段很很很很快快快快将将将将被进程使用，则又需要将其换入内存。被进程使用，则又需要将其换入内存。被进程使用，则又需要将其换入内存。被进程使用，则又需要将其换入内存。如如如如果果果果系系系系统统统统花花花花费费费费大大大大量量量量的的的的时时时时间间间间把把把把程程程程序序序序和和和和数数数数据据据据频频频频繁繁繁繁地地地地装装装装入入入入和和和和移移移移出出出出内内内内存存存存而而而而不不不不是是是是执执执执行行行行用用用用户户户户指指指指令令令令，那那那那么么么么，称称称称系系系系统统统统出出出出现现现现了了了了抖抖抖抖动动动动。出出出出现现现现抖抖抖抖动动动动现现现
177、现象象象象时时时时，系系系系统统统统显显显显得非常繁忙，但是吞吐量很低，甚至产出为零。得非常繁忙，但是吞吐量很低，甚至产出为零。得非常繁忙，但是吞吐量很低，甚至产出为零。得非常繁忙，但是吞吐量很低，甚至产出为零。根本原因：选择的页面或段不恰当。根本原因：选择的页面或段不恰当。根本原因：选择的页面或段不恰当。根本原因：选择的页面或段不恰当。虚拟存储分页技术虚拟存储分页技术 建立在简单分页存储管理系统之上，是建立在简单分页存储管理系统之上，是目前常用的一种虚拟存储管理技术。目前常用的一种虚拟存储管理技术。地址变换地址变换基于简单存储分页系统增加了某些功能，如产基于简单存储分页系统增加了某些功能，如
178、产基于简单存储分页系统增加了某些功能，如产基于简单存储分页系统增加了某些功能，如产生和处理缺页中断，以及从内存中换出页面等。生和处理缺页中断，以及从内存中换出页面等。生和处理缺页中断，以及从内存中换出页面等。生和处理缺页中断，以及从内存中换出页面等。进程执行时，首先通过根据逻辑地址中的页号，进程执行时，首先通过根据逻辑地址中的页号，进程执行时，首先通过根据逻辑地址中的页号，进程执行时，首先通过根据逻辑地址中的页号，查找查找查找查找快表快表快表快表中是否存在对应的页表项。若快表中中是否存在对应的页表项。若快表中中是否存在对应的页表项。若快表中中是否存在对应的页表项。若快表中不存在该页表项，则再查
179、找不存在该页表项，则再查找不存在该页表项，则再查找不存在该页表项，则再查找页表页表页表页表。检查对应的。检查对应的。检查对应的。检查对应的页面是否在内存中存在。若该页面页面是否在内存中存在。若该页面页面是否在内存中存在。若该页面页面是否在内存中存在。若该页面不在内存不在内存不在内存不在内存，启动启动启动启动缺页中断处理缺页中断处理缺页中断处理缺页中断处理例程，装入需要的页面，并例程，装入需要的页面，并例程，装入需要的页面，并例程，装入需要的页面，并更新页表和快表。若该页面已经在内存中，将更新页表和快表。若该页面已经在内存中，将更新页表和快表。若该页面已经在内存中，将更新页表和快表。若该页面已经
180、在内存中，将对应的页表项插入快表中，对应的页表项插入快表中，对应的页表项插入快表中，对应的页表项插入快表中，更新快表更新快表更新快表更新快表。若快表。若快表。若快表。若快表中存在该表项，则直接取出其中的中存在该表项，则直接取出其中的中存在该表项，则直接取出其中的中存在该表项，则直接取出其中的页框号，加页框号，加页框号，加页框号，加上页内偏移量，计算出物理地址上页内偏移量，计算出物理地址上页内偏移量，计算出物理地址上页内偏移量，计算出物理地址。 访问页表访问页表图图3.30虚拟存储分页系统地址变换过程虚拟存储分页系统地址变换过程物理地址物理地址页框号页框号 偏移量偏移量更新快表更新快表页号页号偏
181、移量偏移量逻辑地址逻辑地址检索快表检索快表是是否否是是否否换出页面换出页面处理机处理中断处理机处理中断是是否否处理机从外存取该页处理机从外存取该页将该页装入内存将该页装入内存更新页表更新页表缺页中断处理缺页中断处理？命中？命中？内存满？内存满？页在内存？页在内存缺页中断处理过程缺页中断处理过程（1 1 1 1）操作系统接收到进程产生的缺页中断信号，启动中）操作系统接收到进程产生的缺页中断信号，启动中）操作系统接收到进程产生的缺页中断信号，启动中）操作系统接收到进程产生的缺页中断信号，启动中断处理例程，保留处理机现场；断处理例程，保留处理机现场；断处理例程，保留处理机现场；断处理例程，保留处理机
182、现场；（2 2 2 2）操作系统通知处理机从外存读取指定的页面；）操作系统通知处理机从外存读取指定的页面；）操作系统通知处理机从外存读取指定的页面；）操作系统通知处理机从外存读取指定的页面；（3 3 3 3）处理机激活）处理机激活）处理机激活）处理机激活I/OI/OI/OI/O设备；设备；设备；设备；（4 4 4 4） 检查内存有无足够的空闲空间装入该页面？若有，检查内存有无足够的空闲空间装入该页面？若有，检查内存有无足够的空闲空间装入该页面？若有，检查内存有无足够的空闲空间装入该页面？若有，转（转（转（转（6 6 6 6），否则，执行（），否则，执行（），否则，执行（），否则，执行（5 5
183、5 5）；）；）；）；（5 5 5 5） 利用页面置换算法，选择内存中的某个页面，换利用页面置换算法，选择内存中的某个页面，换利用页面置换算法，选择内存中的某个页面，换利用页面置换算法，选择内存中的某个页面，换出内存；出内存；出内存；出内存；（6 6 6 6） 将指定页面从外存装入内存；将指定页面从外存装入内存；将指定页面从外存装入内存；将指定页面从外存装入内存；（7 7 7 7） 更新该进程的页表；更新该进程的页表；更新该进程的页表；更新该进程的页表；（8 8 8 8） 更新快表；更新快表；更新快表；更新快表；（9 9 9 9）计算物理地址。）计算物理地址。）计算物理地址。）计算物理地址。
184、虚拟存储分段技术虚拟存储分段技术 建立在简单存储分段系统基础上，利用动态分建立在简单存储分段系统基础上，利用动态分建立在简单存储分段系统基础上，利用动态分建立在简单存储分段系统基础上，利用动态分区技术分配存储空间，并以段作为交换的单位。区技术分配存储空间，并以段作为交换的单位。区技术分配存储空间，并以段作为交换的单位。区技术分配存储空间，并以段作为交换的单位。进程执行之前，系统为之分配几个必要的内存进程执行之前，系统为之分配几个必要的内存进程执行之前，系统为之分配几个必要的内存进程执行之前，系统为之分配几个必要的内存分区，每一个分区中装入一段。分区，每一个分区中装入一段。分区，每一个分区中装入
185、一段。分区，每一个分区中装入一段。当进程执行过程中，出现缺段中断时，操作系当进程执行过程中，出现缺段中断时，操作系当进程执行过程中，出现缺段中断时，操作系当进程执行过程中，出现缺段中断时，操作系统将为进程装入需要的程序段。统将为进程装入需要的程序段。统将为进程装入需要的程序段。统将为进程装入需要的程序段。虚拟存储分段：数据结构虚拟存储分段：数据结构 因此，需要修改段表，增加因此，需要修改段表，增加“存在存在”字字段和段和“修改修改”字段，分别标明对应段是字段，分别标明对应段是否存在于内存，以及内存中的段自装入否存在于内存，以及内存中的段自装入以来是否被修改过。以来是否被修改过。地址变换与存储保
186、护地址变换与存储保护在简单分段系统的地址变换机构基础上形成的。在简单分段系统的地址变换机构基础上形成的。在简单分段系统的地址变换机构基础上形成的。在简单分段系统的地址变换机构基础上形成的。 越界检查越界检查越界检查越界检查：可能产生一个地址越界中断，进入：可能产生一个地址越界中断，进入：可能产生一个地址越界中断，进入：可能产生一个地址越界中断，进入相应的中断处理例程执行。一般地，当地址越相应的中断处理例程执行。一般地，当地址越相应的中断处理例程执行。一般地，当地址越相应的中断处理例程执行。一般地，当地址越界中断处理完毕，该进程将异常结束。界中断处理完毕，该进程将异常结束。界中断处理完毕，该进程
187、将异常结束。界中断处理完毕，该进程将异常结束。操作合法性检查操作合法性检查操作合法性检查操作合法性检查：如果属于非法操作，产生非：如果属于非法操作，产生非：如果属于非法操作，产生非：如果属于非法操作，产生非法访问中断，这时也会让进程异常终止。法访问中断，这时也会让进程异常终止。法访问中断，这时也会让进程异常终止。法访问中断，这时也会让进程异常终止。缺段处理缺段处理缺段处理缺段处理：执行进程被阻塞。并产生一个中断：执行进程被阻塞。并产生一个中断：执行进程被阻塞。并产生一个中断：执行进程被阻塞。并产生一个中断信号，处理机执行缺段中断处理例程。信号，处理机执行缺段中断处理例程。信号，处理机执行缺段中
188、断处理例程。信号，处理机执行缺段中断处理例程。图图3.31虚拟存储分段系统地址变换过程虚拟存储分段系统地址变换过程物理地址物理地址段基址段基址 偏移量偏移量更新快表更新快表否否非法访问中断非法访问中断是是是是否否是是越界中断处理越界中断处理访问段表访问段表段号段号 偏移量偏移量逻辑地址逻辑地址检索快表检索快表否否是是缺段中断处理缺段中断处理否否更新段表更新段表？命中？命中？段在内存？段在内存？地址越界？地址越界？合法访问？合法访问图图3.31虚拟存储分段系统中的缺段中断的处理过程虚拟存储分段系统中的缺段中断的处理过程换出一个或几个段换出一个或几个段形成一个合适空闲区形成一个合适空闲区返回返回修
189、改段表、空闲分区表修改段表、空闲分区表从外存读入段从外存读入段s唤醒进程唤醒进程是是拼接外零头，形成拼接外零头，形成一个合适的空闲区一个合适的空闲区是是段段s不在内存不在内存阻塞执行进程阻塞执行进程内存中有合内存中有合适的空闲区适的空闲区吗？吗？否否空闲区容量空闲区容量总和能否满总和能否满足？足？否否虚拟存储段页式技术虚拟存储段页式技术 虚拟存储段页式系统中，程序和数据通常以页虚拟存储段页式系统中，程序和数据通常以页虚拟存储段页式系统中，程序和数据通常以页虚拟存储段页式系统中，程序和数据通常以页面为单位被系统装入和移出内存。面为单位被系统装入和移出内存。面为单位被系统装入和移出内存。面为单位被
190、系统装入和移出内存。因此，一般不需要在段表项中增加因此，一般不需要在段表项中增加因此，一般不需要在段表项中增加因此，一般不需要在段表项中增加“ “存在存在存在存在” ”字字字字段和段和段和段和“ “修改修改修改修改” ”字段，而将它们放在页表中。字段，而将它们放在页表中。字段，而将它们放在页表中。字段，而将它们放在页表中。段表中需要保留基于段的保护与存储共享等目段表中需要保留基于段的保护与存储共享等目段表中需要保留基于段的保护与存储共享等目段表中需要保留基于段的保护与存储共享等目的的存取控制信息，页表中设置基于页的控制的的存取控制信息，页表中设置基于页的控制的的存取控制信息，页表中设置基于页的
191、控制的的存取控制信息，页表中设置基于页的控制信息。信息。信息。信息。 地址变换地址变换首先，通过根据段号和页号，查找首先，通过根据段号和页号，查找首先，通过根据段号和页号，查找首先，通过根据段号和页号，查找快表快表快表快表中是否中是否中是否中是否存在对应的页表项。存在对应的页表项。存在对应的页表项。存在对应的页表项。若快表中不存在该页表项，则再查找若快表中不存在该页表项，则再查找若快表中不存在该页表项，则再查找若快表中不存在该页表项，则再查找段表段表段表段表。然。然。然。然后，检索段号对应的段表项，找到对应段的页后，检索段号对应的段表项，找到对应段的页后，检索段号对应的段表项，找到对应段的页后
192、，检索段号对应的段表项，找到对应段的页表起始地址。表起始地址。表起始地址。表起始地址。再根据页号检索该再根据页号检索该再根据页号检索该再根据页号检索该页表页表页表页表，检查对应页面是否在，检查对应页面是否在，检查对应页面是否在，检查对应页面是否在内存。若该页面内存。若该页面内存。若该页面内存。若该页面不在内存不在内存不在内存不在内存，启动，启动，启动，启动缺页中断缺页中断缺页中断缺页中断处理处理处理处理例程，装入需要的页面，并例程，装入需要的页面，并例程，装入需要的页面，并例程，装入需要的页面，并更新页表和快表更新页表和快表更新页表和快表更新页表和快表。若该页面已经在内存中，将对应的页表项插入
193、若该页面已经在内存中，将对应的页表项插入若该页面已经在内存中，将对应的页表项插入若该页面已经在内存中，将对应的页表项插入快表中，快表中，快表中，快表中，更新快表更新快表更新快表更新快表。若快表中存在该表项，则直接取出其中的若快表中存在该表项，则直接取出其中的若快表中存在该表项，则直接取出其中的若快表中存在该表项，则直接取出其中的页框页框页框页框号，加上页内偏移量，计算出物理地址号，加上页内偏移量，计算出物理地址号，加上页内偏移量，计算出物理地址号，加上页内偏移量，计算出物理地址。 图图3.32虚拟存储分页系统地址变换过程虚拟存储分页系统地址变换过程更新页表更新页表缺页中断处理缺页中断处理物理地
194、址物理地址页框号页框号偏移量偏移量更新快表更新快表是是否否访问段表访问段表访问页表访问页表检索快表检索快表段号段号页内偏移量页内偏移量逻辑地址逻辑地址段内页号段内页号否否是是？命中？命中？页在内存？页在内存虚拟存储系统的软件策略虚拟存储系统的软件策略现代操作系统几乎都采用虚拟存储管理系统现代操作系统几乎都采用虚拟存储管理系统现代操作系统几乎都采用虚拟存储管理系统现代操作系统几乎都采用虚拟存储管理系统一些特殊的操作系统和一些较老的操作系统没一些特殊的操作系统和一些较老的操作系统没一些特殊的操作系统和一些较老的操作系统没一些特殊的操作系统和一些较老的操作系统没有采用虚拟存储技术。例如，有采用虚拟存
195、储技术。例如，有采用虚拟存储技术。例如，有采用虚拟存储技术。例如，MS DOSMS DOSMS DOSMS DOS和早期的和早期的和早期的和早期的UNIXUNIXUNIXUNIX操作系统等。操作系统等。操作系统等。操作系统等。大多采用分段与分页相结合的段页式管理系统。大多采用分段与分页相结合的段页式管理系统。大多采用分段与分页相结合的段页式管理系统。大多采用分段与分页相结合的段页式管理系统。下面以分页存储管理为例，介绍虚拟存储系统下面以分页存储管理为例，介绍虚拟存储系统下面以分页存储管理为例，介绍虚拟存储系统下面以分页存储管理为例，介绍虚拟存储系统采用的软件策略。采用的软件策略。采用的软件策略
196、。采用的软件策略。虚拟存储系统的软件策略虚拟存储系统的软件策略驻留集管理驻留集管理(ResidentSetManagement)放置策略放置策略(PlacementPolicy)获取策略获取策略(FetchPolicy)置换策略置换策略(ReplacementPolicy)清除策略清除策略(CleaningPolicy)负载控制负载控制(LoadControl)驻留集管理驻留集管理 进进程程的的驻驻留留集集指指，虚虚拟拟存存储储系系统统中中，每每个个进进程程驻驻留留在在内内存存的的页页面面集集合合，或或进进程程分到的物理页框集合。分到的物理页框集合。驻驻留留集集管管理理主主要要解解决决的的问问
197、题题是是，系系统统应应当为每个活跃进程分配当为每个活跃进程分配多少个页框多少个页框。影响页框分配的主要因素影响页框分配的主要因素 分分配配给给每每个个活活跃跃进进程程的的页页框框数数越越少少，同同时时驻驻留留内内存存的的活活跃跃进进程程数数就就越越多多，进进程程调调度度程程序序能能调调度度就就绪绪进进程程的的概概率率就就越越大大。然然而而，这这将将导导致致进进程程发发生生缺缺页页中中断断的的概概率较大率较大；为为进进程程分分配配过过多多的的页页框框，并并不不能能显显著著地地降低其缺页中断率。降低其缺页中断率。 基本的驻留集管理策略基本的驻留集管理策略 固定分配策略固定分配策略(Fixed-Al
198、locationPolicy)可变分配策略可变分配策略(Variable-AllocationPolicy)固定分配策略固定分配策略为为每每个个进进程程分分配配固固定定数数量量的的页页框框。即即，每每个个活活跃跃进进程程的的驻驻留留集集尺尺寸寸在在运运行行期期间间固定不变固定不变。为进程分配为进程分配多少个多少个页框是合理的呢？页框是合理的呢？ 可可可可以以以以由由由由系系系系统统统统根根根根据据据据进进进进程程程程的的的的类类类类型型型型确确确确定定定定，也也也也可可可可以以以以由编程人员或系统管理员指定。由编程人员或系统管理员指定。由编程人员或系统管理员指定。由编程人员或系统管理员指定。可
199、变分配策略可变分配策略为为为为每每每每个个个个活活活活跃跃跃跃进进进进程程程程分分分分配配配配的的的的页页页页框框框框数数数数在在在在进进进进程程程程的的的的生生生生命命命命周周周周期期期期内内内内是是是是可可可可变变变变的的的的。即即即即，系系系系统统统统可可可可以以以以首首首首先先先先给给给给进进进进程程程程分分分分配配配配一一一一定定定定数数数数量量量量的的的的页页页页框框框框。进进进进程程程程运运运运行行行行期期期期间间间间，可可可可以以以以增增增增加加加加或或或或减少减少减少减少页框。页框。页框。页框。系统可以根据进程的系统可以根据进程的系统可以根据进程的系统可以根据进程的缺页率缺页
200、率缺页率缺页率调整进程的驻留集调整进程的驻留集调整进程的驻留集调整进程的驻留集。 当当当当进进进进程程程程的的的的缺缺缺缺页页页页率率率率很很很很高高高高时时时时，驻驻驻驻留留留留集集集集太太太太小小小小，需需需需要要要要增增增增加加加加页页页页框；框；框；框； 当当当当缺缺缺缺页页页页率率率率一一一一段段段段时时时时间间间间内内内内都都都都保保保保持持持持很很很很低低低低时时时时，可可可可以以以以在在在在不不不不会会会会明明明明显显显显增增增增加加加加进进进进程程程程缺缺缺缺页页页页率率率率的的的的前前前前提提提提下下下下，回回回回收收收收其其其其一一一一部部部部分分分分页页页页框框框框，减
201、减减减小进程的驻留集。小进程的驻留集。小进程的驻留集。小进程的驻留集。可变分配可变分配vs.固定分配固定分配可可可可变变变变分分分分配配配配策策策策略略略略比比比比固固固固定定定定分分分分配配配配策策策策略略略略更更更更灵灵灵灵活活活活，既既既既可可可可以以以以提高系统的吞吐量，又能保证内存的有效利用。提高系统的吞吐量，又能保证内存的有效利用。提高系统的吞吐量，又能保证内存的有效利用。提高系统的吞吐量，又能保证内存的有效利用。可可可可变变变变分分分分配配配配要要要要求求求求统统统统计计计计进进进进程程程程的的的的缺缺缺缺页页页页率率率率，增增增增加加加加系系系系统统统统额额额额外外外外开开开开
202、销销销销。而而而而准准准准确确确确判判判判断断断断进进进进程程程程缺缺缺缺页页页页率率率率的的的的高高高高低低低低，确确确确定定定定缺页率的阈值是非常困难的。缺页率的阈值是非常困难的。缺页率的阈值是非常困难的。缺页率的阈值是非常困难的。可可可可变变变变分分分分配配配配策策策策略略略略不不不不仅仅仅仅需需需需要要要要操操操操作作作作系系系系统统统统软软软软件件件件专专专专门门门门的的的的支支支支持，而且，还需要处理机平台提供的硬件支持持，而且，还需要处理机平台提供的硬件支持持，而且，还需要处理机平台提供的硬件支持持，而且，还需要处理机平台提供的硬件支持页面放置策略页面放置策略解解解解决决决决的的
203、的的问问问问题题题题：系系系系统统统统应应应应当当当当在在在在内内内内存存存存的的的的什什什什么么么么位位位位置置置置为为为为活活活活跃进程分配页框？跃进程分配页框？跃进程分配页框？跃进程分配页框？一一一一般般般般地地地地，对对对对于于于于一一一一个个个个分分分分页页页页系系系系统统统统或或或或段段段段页页页页式式式式系系系系统统统统，将将将将进程的一个页面装入哪一个页框进程的一个页面装入哪一个页框进程的一个页面装入哪一个页框进程的一个页面装入哪一个页框无关紧要无关紧要无关紧要无关紧要。对对对对于于于于分分分分段段段段系系系系统统统统，需需需需要要要要考考考考虑虑虑虑将将将将一一一一个个个个程
204、程程程序序序序段段段段装装装装入入入入哪哪哪哪一一一一个个个个合合合合适适适适的的的的分分分分区区区区中中中中，可可可可采采采采用用用用的的的的分分分分配配配配算算算算法法法法包包包包括括括括首首首首次次次次适适适适应应应应法法法法、下下下下次次次次适适适适应应应应法法法法、最最最最佳佳佳佳适适适适应应应应法法法法或或或或最最最最差差差差适适适适应法等。应法等。应法等。应法等。页面获取策略页面获取策略解解决决的的问问题题：系系统统应应当当在在何何时时把把一一个个页页面装入内存？面装入内存？请求调页请求调页(DemandPaging)预调页预调页(Prepaging)请求调页请求调页仅仅仅仅当当
205、当当进进进进程程程程执执执执行行行行过过过过程程程程中中中中，通通通通过过过过检检检检查查查查页页页页表表表表发发发发现现现现相相相相应应应应页面不在内存时，才装入该页面。页面不在内存时，才装入该页面。页面不在内存时，才装入该页面。页面不在内存时，才装入该页面。当当当当进进进进程程程程刚刚刚刚开开开开始始始始执执执执行行行行时时时时，由由由由于于于于预预预预先先先先未未未未装装装装入入入入进进进进程程程程的的的的页页页页面面面面，故故故故需需需需要要要要频频频频繁繁繁繁地地地地申申申申请请请请装装装装入入入入页页页页面面面面。执执执执行行行行一一一一段段段段时间以后，进程的缺页率将下降。时间以
206、后，进程的缺页率将下降。时间以后，进程的缺页率将下降。时间以后，进程的缺页率将下降。采采采采用用用用请请请请求求求求调调调调页页页页方方方方式式式式，一一一一次次次次装装装装入入入入请请请请求求求求的的的的一一一一个个个个页页页页面面面面，磁盘磁盘磁盘磁盘I/OI/O的启动频率较高，系统的开销较大。的启动频率较高，系统的开销较大。的启动频率较高，系统的开销较大。的启动频率较高，系统的开销较大。预调页方式预调页方式当进程创建时，预先为进程装入多个页面。当进程创建时，预先为进程装入多个页面。当进程创建时，预先为进程装入多个页面。当进程创建时，预先为进程装入多个页面。缺缺缺缺页页页页中中中中断断断断
207、时时时时，系系系系统统统统为为为为进进进进程程程程装装装装入入入入指指指指定定定定的的的的页页页页面面面面以以以以及及及及与之相临的多个页面。与之相临的多个页面。与之相临的多个页面。与之相临的多个页面。若若若若局局局局部部部部性性性性很很很很差差差差，预预预预先先先先装装装装入入入入的的的的很很很很多多多多页页页页面面面面不不不不会会会会很很很很快快快快被被被被引引引引用用用用，并并并并会会会会占占占占用用用用大大大大量量量量的的的的内内内内存存存存空空空空间间间间，反反反反而而而而降降降降低低低低系统的效率系统的效率系统的效率系统的效率页面置换策略页面置换策略 当当当当发发发发生生生生缺缺缺
208、缺页页页页中中中中断断断断且且且且无无无无足足足足够够够够的的的的内内内内存存存存空空空空间间间间时时时时，需需需需要要要要置换已有的某些（个）页面。置换已有的某些（个）页面。置换已有的某些（个）页面。置换已有的某些（个）页面。应该解决的基本问题：应该解决的基本问题：应该解决的基本问题：应该解决的基本问题： 当当当当系系系系统统统统欲欲欲欲把把把把一一一一个个个个页页页页面面面面装装装装入入入入内内内内存存存存时时时时，应应应应当当当当在在在在什么范围什么范围什么范围什么范围内判断已经没有空闲页框供分配？内判断已经没有空闲页框供分配？内判断已经没有空闲页框供分配？内判断已经没有空闲页框供分配？
209、 当当当当指指指指定定定定的的的的范范范范围围围围内内内内没没没没有有有有空空空空闲闲闲闲页页页页框框框框时时时时，应应应应当当当当从指定的范围内选择从指定的范围内选择从指定的范围内选择从指定的范围内选择哪个页面哪个页面哪个页面哪个页面移出内存？移出内存？移出内存？移出内存？ 局部置换策略局部置换策略可以采用可以采用局部置换局部置换或或全局置换全局置换策略。策略。局局部部置置换换：系系统统在在进进程程自自身身的的驻驻留留集集中中判判断断当当前前是是否否存存在在空空闲闲页页框框，并并在在其其中中进行置换。进行置换。全局置换策略全局置换策略在在整整个个内内存存空空间间内内判判断断有有无无空空闲闲页
210、页框框，并并允允许许从从其其它它进进程程的的驻驻留留集集中中选选择择一一个个页面换出内存。页面换出内存。分配模式分配模式vs.置换模式置换模式固定分配策略固定分配策略 局部置换策略局部置换策略 全局置换策略全局置换策略 可变分配策略可变分配策略可变分配策略可变分配策略+ +局部置换策略局部置换策略 即即即即可可可可增增增增加加加加或或或或减减减减少少少少分分分分配配配配给给给给每每每每个个个个活活活活跃跃跃跃进进进进程程程程的的的的页页页页框框框框数数数数；当当当当进进进进程程程程的的的的页页页页框框框框全全全全部部部部用用用用完完完完，而而而而需需需需要要要要装装装装入入入入一一一一个个个个
211、新新新新的的的的页页页页面面面面时时时时，系系系系统统统统将将将将在在在在该该该该进进进进程程程程的的的的当当当当前前前前驻驻驻驻留留留留集集集集中选择一个页面换出内存。中选择一个页面换出内存。中选择一个页面换出内存。中选择一个页面换出内存。 页面置换策略页面置换策略页页面面置置换换算算法法：在在指指定定的的置置换换范范围围内内，决定将哪一个页面换出内存。决定将哪一个页面换出内存。置置换换算算法法的的好好坏坏将将直直接接影影响响系系统统的的性性能能，不不适适当当的的置置换换算算法法可可能能导导致致系系统统出出现现“抖动抖动”现象。现象。常常用用的的页页面面置置换换算算法法：最最佳佳置置换换算算
212、法法、最最近近最最少少使使用用算算法法、先先进进先先出出算算法法和和时时钟算法等钟算法等最佳置换算法最佳置换算法(OptimalAlgorithm，OPT) 基基基基本本本本思思思思想想想想：被被被被置置置置换换换换的的的的页页页页面面面面是是是是将将将将来来来来不不不不再再再再访访访访问问问问，或或或或在最远的将来才被访问的页面。在最远的将来才被访问的页面。在最远的将来才被访问的页面。在最远的将来才被访问的页面。若若若若采采采采用用用用固固固固定定定定分分分分配配配配策策策策略略略略，最最最最佳佳佳佳置置置置换换换换算算算算法法法法可可可可以以以以保保保保证证证证系统的缺页率最低。系统的缺页
213、率最低。系统的缺页率最低。系统的缺页率最低。但但但但是是是是，无无无无法法法法预预预预知知知知一一一一个个个个进进进进程程程程在在在在内内内内存存存存的的的的若若若若干干干干页页页页面面面面中中中中，哪哪哪哪一一一一个个个个页页页页面面面面是是是是将将将将来来来来不不不不再再再再访访访访问问问问的的的的，甚甚甚甚至至至至最最最最长长长长时时时时间间间间内将不再被访问的，因而该算法是无法实现的。内将不再被访问的，因而该算法是无法实现的。内将不再被访问的，因而该算法是无法实现的。内将不再被访问的，因而该算法是无法实现的。该算法可以用于该算法可以用于该算法可以用于该算法可以用于评价其它置换算法评价其
214、它置换算法评价其它置换算法评价其它置换算法的性能。的性能。的性能。的性能。示例示例假假设设系系统统分分配配给给某某进进程程3个个页页框框，且且进进程程开始运行时，这开始运行时，这3个页框是空的。个页框是空的。考虑下列页面号引用序列：考虑下列页面号引用序列：2 2、3 3、2 2、1 1、5 5、2 2、4 4、5 5、3 3、2 2、5 5、2 222323231235235435435435235235235页面引用序列页面引用序列232152453252FFFFFF12次页面引用次页面引用6次缺页中断（次缺页中断（F和和F）3次页面置换（次页面置换（F）图图3.33采用采用OPT置换算法的
215、缺页中断与页面置换过程置换算法的缺页中断与页面置换过程据局部性原理，如果一个页面最近被访问过，据局部性原理，如果一个页面最近被访问过，据局部性原理，如果一个页面最近被访问过，据局部性原理，如果一个页面最近被访问过，那么，它将在不久的将来再次被访问。那么，它将在不久的将来再次被访问。那么，它将在不久的将来再次被访问。那么，它将在不久的将来再次被访问。如果一个页面已经很长时间未被访问过，则在如果一个页面已经很长时间未被访问过，则在如果一个页面已经很长时间未被访问过，则在如果一个页面已经很长时间未被访问过，则在很久的将来，它将不会被访问。很久的将来，它将不会被访问。很久的将来，它将不会被访问。很久的
216、将来，它将不会被访问。因此，可以根据页面的使用历史，判断其将来因此，可以根据页面的使用历史，判断其将来因此，可以根据页面的使用历史，判断其将来因此，可以根据页面的使用历史，判断其将来的行为。的行为。的行为。的行为。最近最少使用置换算法最近最少使用置换算法(LeastRecentlyUsedAlgorithm，LRU)LRULRU根据页面装入内存以后的使用情况，选择根据页面装入内存以后的使用情况，选择根据页面装入内存以后的使用情况，选择根据页面装入内存以后的使用情况，选择淘汰最近最久未被使用的一个页面。淘汰最近最久未被使用的一个页面。淘汰最近最久未被使用的一个页面。淘汰最近最久未被使用的一个页面
217、。该算法的性能接近该算法的性能接近该算法的性能接近该算法的性能接近OPTOPT算法，但实现较困难。算法，但实现较困难。算法，但实现较困难。算法，但实现较困难。一种方法：为每一个页面增加一个访问字段，一种方法：为每一个页面增加一个访问字段，一种方法：为每一个页面增加一个访问字段，一种方法：为每一个页面增加一个访问字段，用以标注该页最后一次被访问的时间。需要选用以标注该页最后一次被访问的时间。需要选用以标注该页最后一次被访问的时间。需要选用以标注该页最后一次被访问的时间。需要选择淘汰页面时，比较置换范围内的所有页面的择淘汰页面时，比较置换范围内的所有页面的择淘汰页面时，比较置换范围内的所有页面的择
218、淘汰页面时，比较置换范围内的所有页面的最后访问时间，选择访问时间最远的哪个页面。最后访问时间，选择访问时间最远的哪个页面。最后访问时间，选择访问时间最远的哪个页面。最后访问时间，选择访问时间最远的哪个页面。实现该方法的开销非常大，不易实现。实现该方法的开销非常大，不易实现。实现该方法的开销非常大，不易实现。实现该方法的开销非常大，不易实现。LRU置换算法的实现置换算法的实现另一种方法：将访问页面组织在一个堆另一种方法：将访问页面组织在一个堆栈中，最近访问的页面位于栈顶，栈底栈中，最近访问的页面位于栈顶，栈底的页面即是最久未被访问的。的页面即是最久未被访问的。实践证明，该方法的实现仍然很困难，实
219、践证明，该方法的实现仍然很困难，系统付出的代价也非常大。系统付出的代价也非常大。 22323231251251254254354352352352页面引用序列页面引用序列232152453252FFFFFFF12次页面引用次页面引用7次缺页中断（次缺页中断（F和和F）4次页面置换（次页面置换（F）图图3.34采用采用LRU置换算法的缺页中断与页面置换过程置换算法的缺页中断与页面置换过程先进先出置换算法先进先出置换算法(First-inFirst-outAlgorithm，FIFO)淘汰最先进入内存的页面，即选择在内淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。存中驻留时间最
220、久的页面予以淘汰。实现时，只需把一个进程已调入内存的实现时，只需把一个进程已调入内存的页面按先后次序链接成一个队列，并设页面按先后次序链接成一个队列，并设置一个指针，使它总是指向最老的页面。置一个指针，使它总是指向最老的页面。22323231531521524524324324354352页面引用序列页面引用序列232152453252FFFFFFFFF12次页面引用次页面引用9次缺页中断（次缺页中断（F和和F）6次页面置换（次页面置换（F）图图3.35采用采用FIFO置换算法的缺页中断与页面置换过程置换算法的缺页中断与页面置换过程先进先出置换算法先进先出置换算法(First-inFirst-
221、outAlgorithm，FIFO)该算法与进程实际的运行规律不相适应，该算法与进程实际的运行规律不相适应，进程中的某些程序代码或数据可能需要进程中的某些程序代码或数据可能需要高频使用，该算法将导致这种类型的页高频使用，该算法将导致这种类型的页面被反复地换进换出，从而降低系统性面被反复地换进换出，从而降低系统性能。能。Clock时钟置换算法时钟置换算法内存中的每个页面配置一个内存中的每个页面配置一个内存中的每个页面配置一个内存中的每个页面配置一个使用位使用位使用位使用位（U U位）；位）；位）；位）； 当页面装入内存时，或被引用时，其当页面装入内存时，或被引用时，其当页面装入内存时，或被引用时
222、，其当页面装入内存时，或被引用时，其U U位将被设位将被设位将被设位将被设置为置为置为置为1 1；系统将置换范围内的所有页面组成一系统将置换范围内的所有页面组成一系统将置换范围内的所有页面组成一系统将置换范围内的所有页面组成一 个循环队个循环队个循环队个循环队列，并为其设置一个列，并为其设置一个列，并为其设置一个列，并为其设置一个扫描指针扫描指针扫描指针扫描指针；未进行页面置换时，扫描指针总是指向上一次进未进行页面置换时，扫描指针总是指向上一次进未进行页面置换时，扫描指针总是指向上一次进未进行页面置换时，扫描指针总是指向上一次进行页面置换时被置换页面所在位置的下一个位置。行页面置换时被置换页面
223、所在位置的下一个位置。行页面置换时被置换页面所在位置的下一个位置。行页面置换时被置换页面所在位置的下一个位置。时钟置换算法（续）时钟置换算法（续） 当需要进行页面置换时，系统将移动扫描指针，搜索置换当需要进行页面置换时，系统将移动扫描指针，搜索置换当需要进行页面置换时，系统将移动扫描指针，搜索置换当需要进行页面置换时，系统将移动扫描指针，搜索置换范围内的各个页面，以便找到一个范围内的各个页面，以便找到一个范围内的各个页面，以便找到一个范围内的各个页面，以便找到一个U U位为位为位为位为0 0的页面：的页面：的页面：的页面： 如果当前扫描指针所指向的页面的如果当前扫描指针所指向的页面的如果当前扫
224、描指针所指向的页面的如果当前扫描指针所指向的页面的U U位为位为位为位为1 1，那么系统将把该页面，那么系统将把该页面，那么系统将把该页面，那么系统将把该页面的的的的U U位设置为位设置为位设置为位设置为0 0，同时把扫描指针移到下一个位置，继续搜索；，同时把扫描指针移到下一个位置，继续搜索；，同时把扫描指针移到下一个位置，继续搜索；，同时把扫描指针移到下一个位置，继续搜索； 如果当前扫描指针所指向的页面的如果当前扫描指针所指向的页面的如果当前扫描指针所指向的页面的如果当前扫描指针所指向的页面的U U位为位为位为位为0 0，那么系统将把该页面，那么系统将把该页面，那么系统将把该页面，那么系统将
225、把该页面作为被置换页面，同时把扫描指针移到下一个位置，停止搜索。作为被置换页面，同时把扫描指针移到下一个位置，停止搜索。作为被置换页面，同时把扫描指针移到下一个位置，停止搜索。作为被置换页面，同时把扫描指针移到下一个位置，停止搜索。页页6U=1页页123U=1页页30U=0页页616U=0页页77U=1页页24U=1页页110U=1页页16U=0页页76U=0.01234567n-1(b)用用77号页面替换号页面替换23号页面以后的情况号页面以后的情况页页6U=1页页123U=1页页30U=1页页616U=1页页23U=0页页24U=1页页110U=1页页16U=0页页76U=0.012345
226、67n-1(a)当前页面循环队列情况当前页面循环队列情况2*2*3*2*3*2*3*1*5*315*2*15*2*4*5*2*4*3*243*2*43*25*3*2*5*页面引用序列页面引用序列232152453252FFFFFFFF12次页面引用次页面引用8次缺页中断（次缺页中断（F和和F）5次页面置换（次页面置换（F）图图3.37采用采用Clock置换算法的缺页中断与页面置换过程置换算法的缺页中断与页面置换过程时钟置换算法的改进时钟置换算法的改进 系统把一个页面移出内存时，如果该页面驻留内存期间没有系统把一个页面移出内存时，如果该页面驻留内存期间没有系统把一个页面移出内存时，如果该页面驻留
227、内存期间没有系统把一个页面移出内存时，如果该页面驻留内存期间没有被修改过，那么不必把它写回辅存，否则系统必须把它写回被修改过，那么不必把它写回辅存，否则系统必须把它写回被修改过，那么不必把它写回辅存，否则系统必须把它写回被修改过，那么不必把它写回辅存，否则系统必须把它写回辅存。这表明，换出未修改过的页面比换出被修改过的页面辅存。这表明，换出未修改过的页面比换出被修改过的页面辅存。这表明，换出未修改过的页面比换出被修改过的页面辅存。这表明，换出未修改过的页面比换出被修改过的页面开销小。开销小。开销小。开销小。 显然，我们可以依据上述结论改进显然，我们可以依据上述结论改进显然，我们可以依据上述结论
228、改进显然，我们可以依据上述结论改进CLOCKCLOCK算法。改进后的算法。改进后的算法。改进后的算法。改进后的CLOCKCLOCK算法将在置换范围内算法将在置换范围内算法将在置换范围内算法将在置换范围内首选首选首选首选在最近没有被使用过、在在最近没有被使用过、在在最近没有被使用过、在在最近没有被使用过、在驻留内存期间没有被修改过的页面作为被置换页面。驻留内存期间没有被修改过的页面作为被置换页面。驻留内存期间没有被修改过的页面作为被置换页面。驻留内存期间没有被修改过的页面作为被置换页面。时钟置换算法的改进时钟置换算法的改进( (续续续续1)1) 为了改进为了改进为了改进为了改进CLOCKCLOC
229、K算法，系统将为内存的每个页面配置一个算法，系统将为内存的每个页面配置一个算法，系统将为内存的每个页面配置一个算法，系统将为内存的每个页面配置一个修改位修改位修改位修改位（简称为（简称为（简称为（简称为MM位）。位）。位）。位）。 改进后的改进后的改进后的改进后的CLOCKCLOCK算法在置换范围内选择被置换页面时将同算法在置换范围内选择被置换页面时将同算法在置换范围内选择被置换页面时将同算法在置换范围内选择被置换页面时将同时考虑时考虑时考虑时考虑U U位和位和位和位和MM位。位。位。位。 一个页面的一个页面的一个页面的一个页面的U U位与位与位与位与MM位共有四种组合：位共有四种组合：位共有
230、四种组合：位共有四种组合： U=0U=0，M=0M=0：最近没有被使用过，驻留内存期间也没有被修改过；：最近没有被使用过，驻留内存期间也没有被修改过；：最近没有被使用过，驻留内存期间也没有被修改过；：最近没有被使用过，驻留内存期间也没有被修改过； U=1U=1，M=0M=0：最近被使用过，但驻留内存期间没有被修改过；：最近被使用过，但驻留内存期间没有被修改过；：最近被使用过，但驻留内存期间没有被修改过；：最近被使用过，但驻留内存期间没有被修改过； U=0U=0，M=1M=1：最近没有被使用过，但驻留内存期间被修改过；：最近没有被使用过，但驻留内存期间被修改过；：最近没有被使用过，但驻留内存期间
231、被修改过；：最近没有被使用过，但驻留内存期间被修改过； U=1U=1，M=1M=1：最近被使用过，驻留内存期间也被修改过；：最近被使用过，驻留内存期间也被修改过；：最近被使用过，驻留内存期间也被修改过；：最近被使用过，驻留内存期间也被修改过；时钟置换算法的改进时钟置换算法的改进( (续续续续2)2) 改进后的改进后的改进后的改进后的 CLOCKCLOCK算法将按下列步骤选择被置换页面：算法将按下列步骤选择被置换页面：算法将按下列步骤选择被置换页面：算法将按下列步骤选择被置换页面：1 1、从扫描指针的当前位置开始，搜索、从扫描指针的当前位置开始，搜索、从扫描指针的当前位置开始，搜索、从扫描指针的
232、当前位置开始，搜索 U=0U=0且且且且 M=0M=0 的页面。的页面。的页面。的页面。此次搜索不会修改置换范围内的任何一个页面的此次搜索不会修改置换范围内的任何一个页面的此次搜索不会修改置换范围内的任何一个页面的此次搜索不会修改置换范围内的任何一个页面的U U位。若位。若位。若位。若找到第一个找到第一个找到第一个找到第一个U=0U=0且且且且M=0M=0的页面，则把该页面选作被置换页的页面，则把该页面选作被置换页的页面，则把该页面选作被置换页的页面，则把该页面选作被置换页面，终止算法。面，终止算法。面，终止算法。面，终止算法。2 2、如果第一步没有成功，、如果第一步没有成功，、如果第一步没有
233、成功，、如果第一步没有成功， 那么扫描指针将回到原位。那么扫描指针将回到原位。那么扫描指针将回到原位。那么扫描指针将回到原位。 再次再次再次再次搜索搜索搜索搜索U=0U=0但但但但M=1M=1的页面。如果遇到的页面。如果遇到的页面。如果遇到的页面。如果遇到U U位为位为位为位为1 1的页面，将其的页面，将其的页面，将其的页面，将其U U位修改为位修改为位修改为位修改为0 0。倘若找到第一个。倘若找到第一个。倘若找到第一个。倘若找到第一个U=0U=0但但但但M=1M=1的页面，将该页的页面，将该页的页面，将该页的页面，将该页面选作被置换页面，终止算法。面选作被置换页面，终止算法。面选作被置换页面
234、，终止算法。面选作被置换页面，终止算法。3 3、如果第二步也没有成功，、如果第二步也没有成功，、如果第二步也没有成功，、如果第二步也没有成功， 那么扫描指针将再次回到原位，那么扫描指针将再次回到原位，那么扫描指针将再次回到原位，那么扫描指针将再次回到原位，且置换范围内的所有页面的且置换范围内的所有页面的且置换范围内的所有页面的且置换范围内的所有页面的U U位均为位均为位均为位均为0 0。此时，算法将返。此时，算法将返。此时，算法将返。此时，算法将返回第一步继续执行。回第一步继续执行。回第一步继续执行。回第一步继续执行。页页10U=1M=0页页565U=1M=1页页20U=1M=0页页16U=1
235、M=1页页19U=0M=0页页566U=1M=0页页110U=1M=1页页111U=0M=1页页112U=0M=1.01234567n-1图图3.38改进型改进型clock算法：页面置换之前的情形算法：页面置换之前的情形页面清除策略页面清除策略 页页面面清清除除是是指指，将将由由页页面面置置换换算算法法选选择择的被修改的置换页面的被修改的置换页面保存到外存保存到外存。页页面面清清除除策策略略需需要要决决定定系系统统何何时时把把一一个个被置换页面写回外存。被置换页面写回外存。最最直直接接的的页页面面清清除除时时机机是是，只只有有当当一一个个页页被被选选中中作作为为置置换换页页时时，才才被被写写回
236、回外外存存，称之为称之为请求清除策略请求清除策略。若若若若被被被被选选选选中中中中的的的的置置置置换换换换页页页页面面面面自自自自进进进进入入入入内内内内存存存存以以以以来来来来被被被被修修修修改改改改过过过过，则则则则需需需需要要要要首首首首先先先先将将将将该该该该页页页页面面面面内内内内容容容容写写写写回回回回外外外外存存存存保保保保存存存存起起起起来来来来，然后，装入进程需要的新页内容。然后，装入进程需要的新页内容。然后，装入进程需要的新页内容。然后，装入进程需要的新页内容。可可可可见见见见，采采采采用用用用请请请请求求求求清清清清除除除除策策策策略略略略时时时时，写写写写出出出出一一一
237、一个个个个被被被被修修修修改改改改过过过过的的的的页页页页面面面面与与与与读读读读入入入入一一一一个个个个新新新新页页页页的的的的操操操操作作作作是是是是成成成成对对对对出出出出现现现现的的的的，而且，写出操作先于读入操作。而且，写出操作先于读入操作。而且，写出操作先于读入操作。而且，写出操作先于读入操作。所所所所以以以以，当当当当正正正正在在在在执执执执行行行行的的的的进进进进程程程程发发发发生生生生缺缺缺缺页页页页中中中中断断断断时时时时，需需需需要要要要阻阻阻阻塞塞塞塞等等等等待待待待一一一一个个个个页页页页面面面面的的的的写写写写出出出出和和和和另另另另一一一一个个个个页页页页面面面面
238、的的的的读读读读入，这可能降低处理机的使用效率。入，这可能降低处理机的使用效率。入，这可能降低处理机的使用效率。入，这可能降低处理机的使用效率。一一种种有有效效的的页页面面清清除除策策略略是是结结合合页页缓缓冲冲（PageBuffering）技术。）技术。当当发发生生缺缺页页中中断断时时，不不必必首首先先写写出出置置换换页页，然然后后读读入入新新页页。而而是是，将将被被选选中中的的置置换换页页暂暂时时保保留留在在内内存存的的一一个个缓缓冲冲区区，在在以以后后某某个个合合适适的的时时候候将将这这些些被被置置换换页页批量写出批量写出到外存。到外存。减少磁盘减少磁盘I/O的次数，提高处理机的效率。的
239、次数，提高处理机的效率。页缓冲技术的实现页缓冲技术的实现需要两个链表：需要两个链表：需要两个链表：需要两个链表：未修改页链表未修改页链表未修改页链表未修改页链表和和和和修改页链表修改页链表修改页链表修改页链表。当当当当选选选选中中中中一一一一个个个个被被被被修修修修改改改改过过过过的的的的页页页页作作作作为为为为置置置置换换换换页页页页时时时时，不不不不需需需需要要要要立立立立即即即即、真真真真正正正正地地地地将将将将其其其其写写写写出出出出到到到到外外外外存存存存，而而而而是是是是首首首首先先先先将将将将其其其其插插插插入入入入到到到到修修修修改改改改链链链链表表表表中中中中缓缓缓缓冲冲冲冲
240、存存存存储储储储。修修修修改改改改链链链链表表表表中中中中的的的的页页页页可可可可以以以以周周周周期期期期性性性性地地地地批批批批量量量量写写写写出出出出到到到到外外外外存存存存，并并并并移移移移到到到到未未未未修修修修改表中。改表中。改表中。改表中。未未未未修修修修改改改改表表表表链链链链接接接接被被被被选选选选中中中中的的的的未未未未修修修修改改改改置置置置换换换换页页页页，当当当当其其其其中中中中某某某某页页页页所所所所占占占占用用用用的的的的页页页页框框框框被被被被新新新新页页页页占占占占用用用用时时时时，新新新新页页页页的的的的内内内内容容容容覆盖置换页的内容，置换页被真正从内存清除
241、。覆盖置换页的内容，置换页被真正从内存清除。覆盖置换页的内容，置换页被真正从内存清除。覆盖置换页的内容，置换页被真正从内存清除。采采采采用用用用页页页页缓缓缓缓冲冲冲冲技技技技术术术术，当当当当需需需需要要要要读读读读入入入入一一一一个个个个新新新新页页页页时时时时，首首首首先先先先检检检检查查查查未未未未修修修修改改改改页页页页链链链链表表表表，若若若若该该该该表表表表非非非非空空空空，便便便便可可可可按按按按照照照照FIFOFIFO方方方方法法法法，将将将将该该该该链链链链表表表表头头头头指指指指向向向向的的的的第第第第一一一一个个个个页页页页面面面面占占占占用用用用的页框分配给新页。的页
242、框分配给新页。的页框分配给新页。的页框分配给新页。如如如如果果果果未未未未修修修修改改改改表表表表为为为为空空空空，检检检检查查查查修修修修改改改改页页页页链链链链表表表表，将将将将该该该该表表表表中中中中的的的的页页页页面面面面内内内内容容容容批批批批量量量量写写写写出出出出到到到到外外外外存存存存，并并并并将将将将这这这这些些些些页页页页移移移移到到到到未未未未修修修修改改改改表表表表中中中中，按按按按照照照照上上上上述述述述方方方方法法法法重重重重新新新新分分分分配配配配其其其其占占占占用用用用的页框。的页框。的页框。的页框。显显显显然然然然，采采采采用用用用页页页页缓缓缓缓冲冲冲冲技技
243、技技术术术术不不不不仅仅仅仅可可可可以以以以减减减减少少少少写写写写出出出出页页页页面面面面的的的的系系系系统统统统开开开开销销销销，而而而而且且且且可可可可以以以以减减减减少少少少读读读读入入入入页页页页面面面面的的的的开开开开销销销销。因因因因为为为为，当当当当进进进进程程程程再再再再次次次次访访访访问问问问页页页页面面面面缓缓缓缓冲冲冲冲区区区区的的的的页页页页面面面面时时时时，只只只只需需需需要要要要将将将将对对对对应应应应页页页页面面面面从从从从缓缓缓缓冲冲冲冲区区区区返返返返回回回回到到到到该该该该进进进进程程程程的的的的驻驻驻驻留集中，而无须从外存读入。留集中，而无须从外存读入。
244、留集中，而无须从外存读入。留集中，而无须从外存读入。负载控制负载控制 多多道道程程序序系系统统允允许许多多个个进进程程同同时时驻驻留留内内存，以提高系统吞吐量和资源利用率。存，以提高系统吞吐量和资源利用率。然然而而，如如果果同同时时驻驻留留内内存存的的进进程程数数量量太太多多，每每个个进进程程都都竞竞争争各各自自需需要要的的资资源源，反而会反而会降低系统效率降低系统效率。负载控制负载控制 如如如如果果果果内内内内存存存存中中中中进进进进程程程程太太太太多多多多，将将将将导导导导致致致致每每每每个个个个进进进进程程程程的的的的驻驻驻驻留留留留集集集集太太太太小小小小，发发发发生生生生缺缺缺缺页页
245、页页中中中中断断断断的的的的概概概概率率率率很很很很大大大大。相相相相应应应应地地地地，系统发生系统发生系统发生系统发生抖动的可能性就会很大抖动的可能性就会很大抖动的可能性就会很大抖动的可能性就会很大。如如如如果果果果在在在在内内内内存存存存中中中中保保保保持持持持太太太太少少少少的的的的活活活活动动动动进进进进程程程程，那那那那么么么么所所所所有有有有活活活活动动动动进进进进程程程程同同同同时时时时处处处处于于于于阻阻阻阻塞塞塞塞状状状状态态态态的的的的可可可可能能能能性性性性就就就就会会会会很很很很大大大大，从而从而从而从而降低处理机的利用率降低处理机的利用率降低处理机的利用率降低处理机的
246、利用率。负载控制主要解决系统应当保持负载控制主要解决系统应当保持负载控制主要解决系统应当保持负载控制主要解决系统应当保持多少个活动进多少个活动进多少个活动进多少个活动进程驻留在内存程驻留在内存程驻留在内存程驻留在内存的问题，即控制多道程序系统的的问题，即控制多道程序系统的的问题，即控制多道程序系统的的问题，即控制多道程序系统的度。度。度。度。当内存中的活动进程数当内存中的活动进程数当内存中的活动进程数当内存中的活动进程数太少时太少时太少时太少时，负载控制将，负载控制将，负载控制将，负载控制将增增增增加新进程加新进程加新进程加新进程或激活一些挂起进程进入内存；反之，或激活一些挂起进程进入内存；反
247、之，或激活一些挂起进程进入内存；反之，或激活一些挂起进程进入内存；反之，当内存中的进程数当内存中的进程数当内存中的进程数当内存中的进程数太多时太多时太多时太多时，负载控制将暂时挂，负载控制将暂时挂，负载控制将暂时挂，负载控制将暂时挂起一些进程，起一些进程，起一些进程，起一些进程，减少内存中的活动进程数减少内存中的活动进程数减少内存中的活动进程数减少内存中的活动进程数。处理机利用率与多道程序的度之间的关系如图处理机利用率与多道程序的度之间的关系如图处理机利用率与多道程序的度之间的关系如图处理机利用率与多道程序的度之间的关系如图3.393.393.393.39所示。所示。所示。所示。 多道程序的度
248、多道程序的度多道程序的度多道程序的度处处处处理理理理机机机机利利利利用用用用率率率率图图图图3.393.39处理机利用率与多道程序的度之间的关系处理机利用率与多道程序的度之间的关系处理机利用率与多道程序的度之间的关系处理机利用率与多道程序的度之间的关系如何判断系统的负载如何判断系统的负载 L=S准则准则通通通通过过过过调调调调整整整整多多多多道道道道程程程程序序序序的的的的度度度度，使使使使发发发发生生生生两两两两次次次次缺缺缺缺页页页页之之之之间间间间的的的的平平平平均均均均时时时时间间间间等等等等于于于于处处处处理理理理一一一一次次次次缺缺缺缺页页页页所所所所需需需需要要要要的的的的平平平
249、平均均均均时时时时间间间间。即即即即，平平平平均均均均地地地地，一一一一次次次次缺缺缺缺页页页页处处处处理理理理完完完完毕毕毕毕，再再再再发发发发生生生生下下下下一一一一次次次次缺缺缺缺页页页页。此此此此时时时时，处理机的利用率将达到最大。处理机的利用率将达到最大。处理机的利用率将达到最大。处理机的利用率将达到最大。50%准则准则当当当当分分分分页页页页设设设设备备备备的的的的利利利利用用用用率率率率保保保保持持持持在在在在50%50%左左左左右右右右时时时时，处处处处理理理理机机机机的的的的利利利利用率将达到最大。用率将达到最大。用率将达到最大。用率将达到最大。如何判断系统的负载如何判断系统
250、的负载如如如如果果果果系系系系统统统统使使使使用用用用基基基基于于于于CLOCKCLOCKCLOCKCLOCK置置置置换换换换算算算算法法法法的的的的全全全全局局局局置置置置换换换换策策策策略略略略，那那那那么么么么，可可可可以以以以通通通通过过过过监监监监视视视视扫扫扫扫描描描描指指指指针针针针的的的的移移移移动动动动速速速速率率率率来调整系统负载。来调整系统负载。来调整系统负载。来调整系统负载。如如如如果果果果扫扫扫扫描描描描指指指指针针针针的的的的移移移移动动动动速速速速率率率率低低低低于于于于某某某某个个个个给给给给定定定定的的的的阀阀阀阀值值值值，那那那那么么么么意意意意味味味味着着
251、着着近近近近期期期期页页页页面面面面失失失失败败败败的的的的次次次次数数数数较较较较少少少少或或或或者者者者近近近近期期期期没没没没有有有有被被被被引引引引用用用用的的的的页页页页面面面面数数数数较较较较多多多多；此此此此时时时时，系系系系统统统统可可可可以以以以放放放放心地心地心地心地增加增加增加增加驻留内存的活动进程数。驻留内存的活动进程数。驻留内存的活动进程数。驻留内存的活动进程数。如如如如果果果果扫扫扫扫描描描描指指指指针针针针的的的的移移移移动动动动速速速速率率率率超超超超出出出出某某某某个个个个给给给给定定定定的的的的阀阀阀阀值值值值，那那那那么么么么意意意意味味味味着着着着近近近
252、近期期期期页页页页面面面面失失失失败败败败的的的的次次次次数数数数较较较较多多多多或或或或者者者者近近近近期期期期没没没没有有有有被被被被引引引引用用用用的的的的页页页页面面面面数数数数较较较较少少少少；此此此此时时时时，系系系系统统统统应应应应当当当当减减减减少少少少驻留内存的活动进程数。驻留内存的活动进程数。驻留内存的活动进程数。驻留内存的活动进程数。可以挂起的进程可以挂起的进程 优先级最低的进程优先级最低的进程优先级最低的进程优先级最低的进程；缺缺缺缺页页页页进进进进程程程程 因因因因为为为为，发发发发生生生生缺缺缺缺页页页页中中中中断断断断的的的的进进进进程程程程处处处处于于于于阻阻阻
253、阻塞塞塞塞状状状状态态态态，暂暂暂暂时时时时不不不不需需需需要要要要竞竞竞竞争争争争处处处处理理理理机机机机的的的的使使使使用用用用权权权权。而而而而且且且且，挂挂挂挂起起起起一一一一个个个个缺缺缺缺页页页页进进进进程程程程时时时时，挂挂挂挂起起起起和和和和激激激激活活活活操操操操作作作作需需需需要的数据交换将消除页替换的开销；要的数据交换将消除页替换的开销；要的数据交换将消除页替换的开销；要的数据交换将消除页替换的开销；最最最最后后后后一一一一个个个个被被被被激激激激活活活活的的的的进进进进程程程程 因因因因为为为为，为为为为此此此此类类类类进进进进程程程程装装装装入的页面较少。将其挂起的开
254、销较小；入的页面较少。将其挂起的开销较小；入的页面较少。将其挂起的开销较小；入的页面较少。将其挂起的开销较小；可以挂起的进程可以挂起的进程 驻驻驻驻留留留留集集集集最最最最小小小小的的的的进进进进程程程程 将将将将该该该该类类类类进进进进程程程程挂挂挂挂起起起起以以以以后后后后，激激激激活所需的开销较小；活所需的开销较小；活所需的开销较小；活所需的开销较小；最最最最大大大大的的的的进进进进程程程程 挂挂挂挂起起起起最最最最大大大大的的的的进进进进程程程程将将将将获获获获得得得得最最最最多多多多的的的的内内内内存存存存空空空空间间间间，可可可可以以以以满满满满足足足足内内内内存存存存中中中中的的
255、的的进进进进程程程程申申申申请请请请空空空空闲闲闲闲页页页页框框框框的需要，使它们能尽快执行完成；的需要，使它们能尽快执行完成；的需要，使它们能尽快执行完成；的需要，使它们能尽快执行完成；剩剩剩剩余余余余执执执执行行行行时时时时间间间间最最最最多多多多的的的的进进进进程程程程 对对对对应应应应于于于于剩剩剩剩余余余余时时时时间间间间最最最最短短短短者者者者优优优优先先先先的的的的进进进进程程程程调调调调度度度度算算算算法法法法，将将将将剩剩剩剩余余余余执执执执行行行行时时时时间间间间最最最最多的进程挂起对其响应时间的影响不明显。多的进程挂起对其响应时间的影响不明显。多的进程挂起对其响应时间的影响不明显。多的进程挂起对其响应时间的影响不明显。
