操作系统原理与实例分析.ppt

《操作系统原理与实例分析.ppt》由会员分享，可在线阅读，更多相关《操作系统原理与实例分析.ppt（73页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、3.3 3.3 程序装入技术程序装入技术 可执行程序的生成步骤可执行程序的生成步骤图图3.10 3.10 高级程序处理过程高级程序处理过程源程序源程序目标模块目标模块编译编译库函数库函数装入模块装入模块链接链接编辑编辑执行执行目标模块目标模块内存内存可执行程序的装入可执行程序的装入？如何装入待执行的程序及其所需的数据？如何装入待执行的程序及其所需的数据？如何装入待执行的程序及其所需的数据？如何装入待执行的程序及其所需的数据？何时将程序的逻辑地址转换为物理地址何时将程序的逻辑地址转换为物理地址何时将程序的逻辑地址转换为物理地址何时将程序的逻辑地址转换为物理地址3 3 3 3种装入方式：绝对装入、

2、重定位装入和运行种装入方式：绝对装入、重定位装入和运行种装入方式：绝对装入、重定位装入和运行种装入方式：绝对装入、重定位装入和运行时动态装入。时动态装入。时动态装入。时动态装入。绝对装入绝对装入程序运行之前，按照程序的逻辑地址，程序运行之前，按照程序的逻辑地址，将程序和数据装入内存指定的地方。将程序和数据装入内存指定的地方。实现简单，无须进行逻辑地址到物理地实现简单，无须进行逻辑地址到物理地址的变换。址的变换。绝对装入绝对装入缺点：缺点：缺点：缺点：程序每次必须装入同一内存区；程序每次必须装入同一内存区；程序每次必须装入同一内存区；程序每次必须装入同一内存区；程序员必须事先了解内存的使用情况，

3、根据内程序员必须事先了解内存的使用情况，根据内程序员必须事先了解内存的使用情况，根据内程序员必须事先了解内存的使用情况，根据内存情况确定程序的逻辑地址；存情况确定程序的逻辑地址；存情况确定程序的逻辑地址；存情况确定程序的逻辑地址；程序的修改（增加或删除指令）将引起整个程程序的修改（增加或删除指令）将引起整个程程序的修改（增加或删除指令）将引起整个程程序的修改（增加或删除指令）将引起整个程序中指令地址的变动；序中指令地址的变动；序中指令地址的变动；序中指令地址的变动；程序中的所有存储引用，例如函数调用或过程程序中的所有存储引用，例如函数调用或过程程序中的所有存储引用，例如函数调用或过程程序中的所

4、有存储引用，例如函数调用或过程调用等，在装入之前都必须转换为物理地址，调用等，在装入之前都必须转换为物理地址，调用等，在装入之前都必须转换为物理地址，调用等，在装入之前都必须转换为物理地址，这不利于存储共享。这不利于存储共享。这不利于存储共享。这不利于存储共享。重定位装入重定位装入允允许许将将程程序序装装入入与与逻逻辑辑地地址址不不同同的的物物理理内内存存空空间间。即即程程序序可可以以装装入入到到内内存存的的任任何何位位置置，其其逻逻辑辑地地址址与与装装入入内内存存后后的的物物理地址无直接关系。理地址无直接关系。但但是是，必必须须进进行行地地址址映映射射，将将逻逻辑辑地地址址转换为物理地址。转

5、换为物理地址。静静态态重重定定位位技技术术：地地址址映映射射在在程程序序装装入入时进行，以后不再更改程序地址。时进行，以后不再更改程序地址。重定位装入重定位装入有有有有利利利利于于于于程程程程序序序序代代代代码码码码和和和和数数数数据据据据的的的的共共共共享享享享。因因因因为为为为装装装装入入入入程程程程序序序序时时时时，可可可可以以以以将将将将其其其其中中中中的的的的某某某某些些些些存存存存储储储储引引引引用用用用的的的的逻逻逻逻辑辑辑辑地地地地址址址址映映映映射为内存中已有的共享区的物理地址。射为内存中已有的共享区的物理地址。射为内存中已有的共享区的物理地址。射为内存中已有的共享区的物理地

6、址。但但但但是是是是，静静静静态态态态重重重重定定定定位位位位不不不不允允允允许许许许程程程程序序序序在在在在内内内内存存存存中中中中移移移移动动动动。这这这这不不不不便便便便于于于于进进进进程程程程交交交交换换换换和和和和紧紧紧紧凑凑凑凑拼拼拼拼接接接接操操操操作作作作，也也也也很很很很难难难难实实实实现现现现多多多多道道道道程程程程序序序序环环环环境境境境下下下下，多多多多个个个个程程程程序序序序同同同同时时时时装装装装入入入入内内内内存存存存的的的的要求。要求。要求。要求。故，重定位装入方式只适合于单道程序环境。故，重定位装入方式只适合于单道程序环境。故，重定位装入方式只适合于单道程序环

7、境。故，重定位装入方式只适合于单道程序环境。运行时动态装入运行时动态装入指指指指，程程程程序序序序的的的的地地地地址址址址转转转转换换换换不不不不是是是是在在在在装装装装入入入入时时时时进进进进行行行行，而而而而是是是是在程序运行时动态进行。在程序运行时动态进行。在程序运行时动态进行。在程序运行时动态进行。运运运运行行行行时时时时动动动动态态态态装装装装入入入入需需需需要要要要硬硬硬硬件件件件支支支支持持持持，即即即即重重重重定定定定位位位位寄寄寄寄存存存存器，用于保存程序在内存中的起始地址。器，用于保存程序在内存中的起始地址。器，用于保存程序在内存中的起始地址。器，用于保存程序在内存中的起始

8、地址。程程程程序序序序被被被被执执执执行行行行时时时时，通通通通过过过过重重重重定定定定位位位位寄寄寄寄存存存存器器器器内内内内的的的的起起起起始始始始物物物物理理理理地地地地址址址址和和和和指指指指令令令令或或或或数数数数据据据据的的的的逻逻逻逻辑辑辑辑地地地地址址址址计计计计算算算算其其其其物物物物理理理理地地地地址。址。址。址。运运运运行行行行时时时时动动动动态态态态装装装装入入入入有有有有利利利利于于于于多多多多道道道道程程程程序序序序环环环环境境境境下下下下，进进进进程程程程的换进的换进的换进的换进/换出及实现紧凑技术。换出及实现紧凑技术。换出及实现紧凑技术。换出及实现紧凑技术。可执

9、行程序的链接形成可执行程序的链接形成？目标模块如何链接成装入模块呢目标模块如何链接成装入模块呢静态链接静态链接动态链接动态链接：装入时动态链接和运行时动：装入时动态链接和运行时动态链接态链接 静态链接静态链接指指指指，程程程程序序序序被被被被装装装装入入入入内内内内存存存存之之之之前前前前，必必必必须须须须完完完完全全全全链链链链接接接接成成成成一一一一个个个个装装装装入入入入模模模模块块块块，将将将将其其其其中中中中的的的的存存存存储储储储引引引引用用用用全全全全部部部部转转转转换换换换为为为为相相相相对对对对地地地地址址址址跳跳跳跳转转转转语语语语句句句句。并并并并将将将将多多多多个个个个

10、目目目目标标标标模模模模块块块块链链链链接接接接成成成成为为为为一一一一个个个个模模模模块块块块，使使使使装装装装入入入入模模模模块块块块中中中中的的的的每每每每一一一一条条条条指指指指令令令令具具具具有有有有相相相相对于整个模块的第一条语句的逻辑地址。对于整个模块的第一条语句的逻辑地址。对于整个模块的第一条语句的逻辑地址。对于整个模块的第一条语句的逻辑地址。静态链接生成的装入模块可以采用重定位装入静态链接生成的装入模块可以采用重定位装入静态链接生成的装入模块可以采用重定位装入静态链接生成的装入模块可以采用重定位装入或运行时动态装入方式。或运行时动态装入方式。或运行时动态装入方式。或运行时动态

11、装入方式。静态链接需要花费大量的处理机时间。而其中静态链接需要花费大量的处理机时间。而其中静态链接需要花费大量的处理机时间。而其中静态链接需要花费大量的处理机时间。而其中的很多模块将不会运行，浪费存储空间和处理的很多模块将不会运行，浪费存储空间和处理的很多模块将不会运行，浪费存储空间和处理的很多模块将不会运行，浪费存储空间和处理机时间。机时间。机时间。机时间。链接链接图图3.11目标模块链接成装入模块目标模块链接成装入模块模块模块1ifx1thencallmm1elsecallmm2模块模块mm1模块模块mm2(a)目标模目标模块块模块模块1ifx1thenelse模块模块mm1模块模块mm2

12、(b)装入模装入模块块？执行？执行？执行？执行动态链接动态链接指指，不不用用事事先先链链接接所所有有目目标标模模块块形形成成一一个个完完备备的的装装入入模模块块，而而是是生生成成一一个个含含有有未未被被链链接接的的外外部部模模块块引引用用的的装装入入模模块块，这这些些外外部部模模块块可可以以在在装装入入时时链链接接，或或运运行时链接。行时链接。装入时动态链接装入时动态链接指指指指，当当当当系系系系统统统统装装装装入入入入含含含含有有有有未未未未链链链链接接接接的的的的外外外外部部部部模模模模块块块块引引引引用用用用的的的的装装装装入入入入模模模模块块块块时时时时，每每每每当当当当遇遇遇遇到到到

13、到一一一一个个个个外外外外部部部部模模模模块块块块引引引引用用用用，则则则则查查查查找找找找相相相相应应应应的的的的目目目目标标标标模模模模块块块块。将将将将其其其其装装装装入入入入内内内内存存存存，并并并并将将将将模模模模块块块块内内内内的的的的指指指指令令令令地地地地址址址址转转转转换换换换为为为为相相相相对对对对于于于于整整整整个个个个装装装装入入入入模模模模块块块块起起起起始地址的相对地址。始地址的相对地址。始地址的相对地址。始地址的相对地址。优优优优点点点点：有有有有利利利利于于于于目目目目标标标标模模模模块块块块的的的的更更更更新新新新与与与与升升升升级级级级；有有有有利利利利于于

14、于于代代代代码码码码共共共共享享享享；有有有有利利利利于于于于扩扩扩扩充充充充软软软软件件件件的的的的功功功功能能能能，可可可可以以以以将将将将扩扩扩扩充部分作为动态链接模块。充部分作为动态链接模块。充部分作为动态链接模块。充部分作为动态链接模块。但但但但是是是是，可可可可能能能能链链链链接接接接一一一一些些些些不不不不会会会会执执执执行行行行的的的的模模模模块块块块，浪浪浪浪费费费费存存存存储空间和处理机时间。储空间和处理机时间。储空间和处理机时间。储空间和处理机时间。运行时动态链接运行时动态链接指，外部模块引用直至程序执行时才装入内存，指，外部模块引用直至程序执行时才装入内存，指，外部模块

15、引用直至程序执行时才装入内存，指，外部模块引用直至程序执行时才装入内存，并链接到装入模块中，进行地址转换。并链接到装入模块中，进行地址转换。并链接到装入模块中，进行地址转换。并链接到装入模块中，进行地址转换。可以解决静态链接和装入时动态链接都面临的可以解决静态链接和装入时动态链接都面临的可以解决静态链接和装入时动态链接都面临的可以解决静态链接和装入时动态链接都面临的存储空间和处理机时间浪费问题，不需要执行存储空间和处理机时间浪费问题，不需要执行存储空间和处理机时间浪费问题，不需要执行存储空间和处理机时间浪费问题，不需要执行的模块就不会装入内存。的模块就不会装入内存。的模块就不会装入内存。的模块

16、就不会装入内存。广广广广泛泛泛泛用用用用于于于于事事事事务务务务处处处处理理理理系系系系统统统统，如如如如航航航航空空空空售售售售票票票票系系系系统统统统、银银银银行管理系统等。行管理系统等。行管理系统等。行管理系统等。操操操操作作作作系系系系统统统统自自自自身身身身的的的的一一一一些些些些特特特特殊殊殊殊处处处处理理理理例例例例程程程程，如如如如错错错错误误误误处处处处理例程，也无需事先全部装入内存。理例程，也无需事先全部装入内存。理例程，也无需事先全部装入内存。理例程，也无需事先全部装入内存。3.4 3.4 简单存储管理技术简单存储管理技术 简单存储简单存储相对于虚拟存储而言，指为了实现简

17、单，执行相对于虚拟存储而言，指为了实现简单，执行相对于虚拟存储而言，指为了实现简单，执行相对于虚拟存储而言，指为了实现简单，执行之前，操作系统必须将待执行的程序全部装入之前，操作系统必须将待执行的程序全部装入之前，操作系统必须将待执行的程序全部装入之前，操作系统必须将待执行的程序全部装入内存。内存。内存。内存。然而，现代操作系统大都支持虚拟存储功能，然而，现代操作系统大都支持虚拟存储功能，然而，现代操作系统大都支持虚拟存储功能，然而，现代操作系统大都支持虚拟存储功能，允许进程装入部分程序即可开始执行，其余部允许进程装入部分程序即可开始执行，其余部允许进程装入部分程序即可开始执行，其余部允许进程

18、装入部分程序即可开始执行，其余部分保留在外存。当执行所需的部分不在内存时，分保留在外存。当执行所需的部分不在内存时，分保留在外存。当执行所需的部分不在内存时，分保留在外存。当执行所需的部分不在内存时，中断进程执行，使之阻塞等待，直到相应部分中断进程执行，使之阻塞等待，直到相应部分中断进程执行，使之阻塞等待，直到相应部分中断进程执行，使之阻塞等待，直到相应部分装入内存。装入内存。装入内存。装入内存。？程序在内存中如何组织程序在内存中如何组织连连续续存存储储 :需需要要内内存存中中的的一一块块连连续续的的、足够大的分区足够大的分区。如如果果内内存存中中没没有有足足够够大大的的连连续续空空闲闲分分区

19、区，但但存存在在总总量量足足够够的的独独立立小小分分区区，即即外外零零头头。系系统统要要么么拒拒绝绝分分配配空空间间，要要么么采采用用紧凑技术紧凑技术拼接外零头。拼接外零头。非非连连续续存存储储：允允许许进进程程的的程程序序和和数数据据分分别装在内存的不同分区中。别装在内存的不同分区中。必必须须登登记记一一个个进进程程分分到到的的所所有有分分区区的的位位置置、大大小小、使使用用情情况况（如如是是否否共共享享等等）等信息等信息。常常用用的的非非连连续续存存储储技技术术：分分页页存存储储技技术术、分段存储技术及其结合。分段存储技术及其结合。图图3.12 3.12 内存的内存的连续存储与非连续存储连

20、续存储与非连续存储OS进程进程P基地址基地址(a)a)连续存储连续存储进程进程P（2）OS进程进程P（1）进程进程P（n）进程的组成进程的组成基地址基地址长度长度P(1)2604200P(2)1240300P(n)6500300(b)b)非非连续存储连续存储连续存储管理连续存储管理 最简单的存储管理技术最简单的存储管理技术要求系统配置专门的硬件实现快速地址要求系统配置专门的硬件实现快速地址转换和存储保护。转换和存储保护。处理机硬件处理机硬件基址寄存器基址寄存器基址寄存器基址寄存器(Baseregister)Baseregister)界限寄存器界限寄存器界限寄存器界限寄存器(Boundsregi

21、ster)Boundsregister)连续存储管理连续存储管理 基址寄存器基址寄存器基址寄存器基址寄存器：存放当前执行进程所在分区的物：存放当前执行进程所在分区的物：存放当前执行进程所在分区的物：存放当前执行进程所在分区的物理存储单元的起始地址。理存储单元的起始地址。理存储单元的起始地址。理存储单元的起始地址。界限寄存器界限寄存器界限寄存器界限寄存器：存放当前执行进程所在分区最后：存放当前执行进程所在分区最后：存放当前执行进程所在分区最后：存放当前执行进程所在分区最后一个物理存储单元的地址，限定进程的执行范一个物理存储单元的地址，限定进程的执行范一个物理存储单元的地址，限定进程的执行范一个物

22、理存储单元的地址，限定进程的执行范围，保护其他进程不被非法访问。围，保护其他进程不被非法访问。围，保护其他进程不被非法访问。围，保护其他进程不被非法访问。基址寄存器和界限寄存器被多个进程共享，只基址寄存器和界限寄存器被多个进程共享，只基址寄存器和界限寄存器被多个进程共享，只基址寄存器和界限寄存器被多个进程共享，只有当前执行进程才使用它们。有当前执行进程才使用它们。有当前执行进程才使用它们。有当前执行进程才使用它们。装入时，进程分区的基地址值和分区的最后一装入时，进程分区的基地址值和分区的最后一装入时，进程分区的基地址值和分区的最后一装入时，进程分区的基地址值和分区的最后一个物理存储单元的地址值

23、，分别填入该进程个物理存储单元的地址值，分别填入该进程个物理存储单元的地址值，分别填入该进程个物理存储单元的地址值，分别填入该进程PCBPCBPCBPCB的相应字段中。的相应字段中。的相应字段中。的相应字段中。当进程被调度执行时，将当进程被调度执行时，将当进程被调度执行时，将当进程被调度执行时，将PCBPCBPCBPCB中对应的进程基中对应的进程基中对应的进程基中对应的进程基地址值写入基址寄存器中，并将进程获得的内地址值写入基址寄存器中，并将进程获得的内地址值写入基址寄存器中，并将进程获得的内地址值写入基址寄存器中，并将进程获得的内存分区最大地址值，填入界限寄存器中。存分区最大地址值，填入界限

24、寄存器中。存分区最大地址值，填入界限寄存器中。存分区最大地址值，填入界限寄存器中。当进程被交换出当进程被交换出当进程被交换出当进程被交换出/换入内存时，上述两个地址换入内存时，上述两个地址换入内存时，上述两个地址换入内存时，上述两个地址值也会发生改变。值也会发生改变。值也会发生改变。值也会发生改变。地址映射与存储保护地址映射与存储保护 逻辑地址转换成物理地址逻辑地址转换成物理地址逻辑地址转换成物理地址逻辑地址转换成物理地址 取基址寄存器中的值，加上逻辑地址值，生取基址寄存器中的值，加上逻辑地址值，生取基址寄存器中的值，加上逻辑地址值，生取基址寄存器中的值，加上逻辑地址值，生成一个物理地址成一个

25、物理地址成一个物理地址成一个物理地址 地址越界检查地址越界检查地址越界检查地址越界检查 取取取取界界界界限限限限寄寄寄寄存存存存器器器器中中中中的的的的值值值值，与与与与第第第第一一一一步步步步计计计计算算算算的的的的结结结结果果果果进进进进行行行行比比比比较较较较。如如如如果果果果生生生生成成成成的的的的物物物物理理理理地地地地址址址址超超超超出出出出了了了了界界界界限限限限范范范范围围围围，产产产产生生生生一一一一个个个个中中中中断断断断，报报报报告告告告地地地地址址址址越越越越界界界界。否否否否则则则则，继继继继续该指令的执行。续该指令的执行。续该指令的执行。续该指令的执行。程序部分程序

26、部分数据部分数据部分内存内存基址寄存器基址寄存器加法器加法器逻辑地址逻辑地址界限寄存器界限寄存器比较器比较器越界中断越界中断物理地址物理地址图图3.13连续存储管理的地址转换和越界检查连续存储管理的地址转换和越界检查 简单分页存储管理简单分页存储管理 连续存储：存在外零头，浪费存储空间。连续存储：存在外零头，浪费存储空间。“紧凑紧凑”需要系统额外开销。需要系统额外开销。非连续存储：允许将一个进程的程序和非连续存储：允许将一个进程的程序和数据离散存储在多个独立的分区中，消数据离散存储在多个独立的分区中，消除了外零头。除了外零头。基本原理基本原理 分分页页存存储储管管理理技技术术是是一一种种特特殊

27、殊的的固固定定分分区方法。区方法。系系统统事事先先将将物物理理内内存存划划分分成成许许多多尺尺寸寸相相等等的的页页框框(PageFrame)，并并将将进进程程分分割割成成许许多多大大小小相相同同的的页页面面(Page)，页页面面与与页框大小相同。页框大小相同。分区分区分区分区：进程的逻辑地址空间是连续的、一维的、：进程的逻辑地址空间是连续的、一维的、：进程的逻辑地址空间是连续的、一维的、：进程的逻辑地址空间是连续的、一维的、线性地址，进程的每一条指令和数据的地址相线性地址，进程的每一条指令和数据的地址相线性地址，进程的每一条指令和数据的地址相线性地址，进程的每一条指令和数据的地址相对于第一条语

28、句的地址而定。对于第一条语句的地址而定。对于第一条语句的地址而定。对于第一条语句的地址而定。分页分页分页分页：进程被分割成许多页面。每个页面内的：进程被分割成许多页面。每个页面内的：进程被分割成许多页面。每个页面内的：进程被分割成许多页面。每个页面内的指令和数据是连续的，它们的地址相对于其所指令和数据是连续的，它们的地址相对于其所指令和数据是连续的，它们的地址相对于其所指令和数据是连续的，它们的地址相对于其所属页的第一条语句的地址，称为属页的第一条语句的地址，称为属页的第一条语句的地址，称为属页的第一条语句的地址，称为页内偏移量页内偏移量页内偏移量页内偏移量。逻辑地址被分为两部分：逻辑地址被分

29、为两部分：逻辑地址被分为两部分：逻辑地址被分为两部分：页号页号页号页号和和和和页内偏移量页内偏移量页内偏移量页内偏移量 页号页号页内偏移量页内偏移量151090图图3.14分页管理的逻辑地址表示分页管理的逻辑地址表示当当一一个个进进程程被被装装入入物物理理内内存存时时，系系统统将将为为该该进进程程的的每每个个页页面面分分配配一一个个独独立立的的页页框。框。同同一一个个进进程程的的多多个个页页面面不不必必存存放放在在连连续续的多个页框中。的多个页框中。例如例如假设内存能提供假设内存能提供假设内存能提供假设内存能提供16161616个空闲页框，进程个空闲页框，进程个空闲页框，进程个空闲页框，进程P

30、1P1P1P1被分割被分割被分割被分割成成成成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号页框，如图号页框，如图号页框，如图号页框，如图3.153.153.153.15

31、(a)a)a)a)所所所所示。示。示。示。此时，进程此时，进程此时，进程此时，进程P4P4P4P4请求分配请求分配请求分配请求分配5 5 5 5个页框大小的存储空个页框大小的存储空个页框大小的存储空个页框大小的存储空间，但内存只有间，但内存只有间，但内存只有间，但内存只有3 3 3 3个空闲页框。于是，将暂时个空闲页框。于是，将暂时个空闲页框。于是，将暂时个空闲页框。于是，将暂时不运行的不运行的不运行的不运行的P2P2P2P2交换出内存，如图交换出内存，如图交换出内存，如图交换出内存，如图3.15(3.15(3.15(3.15(b)b)b)b)所示。所示。所示。所示。然后，再将然后，再将然后，

32、再将然后，再将P4P4P4P4装入装入装入装入4 4 4 4、5 5 5 5、6 6 6 6、13131313、14141414号页框，号页框，号页框，号页框，如图如图如图如图3.15(3.15(3.15(3.15(c)c)c)c)所示。所示。所示。所示。图图3.15进程装入到离散的页框中进程装入到离散的页框中0123456789101112131415P1.2P1.1P1.0P1.3P2.0P2.1P2.2P3.0P3.1P3.2P3.3P3.4P3.5页框号页框号内存内存(a)依次装入依次装入P1、P2、P3P1P2P3空闲空闲0123456789101112131415P1.2P1.1P

33、1.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数据结构：页表数据结构：页表页页表表：系系统统为为每每个个进进程程建建立立一一张张页页面面映映射表。射表。用用于于记记载载进进程程的的各各页页面面到到物物理理内内存存中中页页框的映射信息。框的映射信息。进进程程的的每每个个页页面面依依次次对对应应页页

34、表表中中的的一一个个表表项项，其其中中包包含含相相应应页页在在内内存存中中对对应应的的物理页框号和页面存取控制权限等字段。物理页框号和页面存取控制权限等字段。页号页号页框号页框号00112233进程进程P1页表页表页号页号页框号页框号0-1-2-进程进程P2页表页表页号页号页框号页框号071829310411512进程进程P3页表页表页号页号页框号页框号041526313414进程进程P4页表页表图图3.16进程进程P1、P2、P3、P4的页表的页表数据结构：页框表数据结构：页框表空闲页框表：登记系统中剩下的空闲页空闲页框表：登记系统中剩下的空闲页框情况框情况图图3.17空闲页框表空闲页框表1

35、51413地址变换地址变换硬件机制，实现逻辑地址到物理地址的转换硬件机制，实现逻辑地址到物理地址的转换硬件机制，实现逻辑地址到物理地址的转换硬件机制，实现逻辑地址到物理地址的转换分页系统中的地址变换过程如下：分页系统中的地址变换过程如下：分页系统中的地址变换过程如下：分页系统中的地址变换过程如下：（1 1 1 1）根根根根据据据据逻逻逻逻辑辑辑辑地地地地址址址址,计计计计算算算算出出出出页页页页号号号号和和和和页页页页内内内内偏移量；偏移量；偏移量；偏移量；（2 2 2 2）用用用用页页页页号号号号检检检检索索索索页页页页表表表表，查查查查找找找找指指指指定定定定页页页页面面面面对对对对应的页

36、框号；应的页框号；应的页框号；应的页框号；（3 3 3 3）根根根根据据据据页页页页框框框框号号号号和和和和页页页页内内内内偏偏偏偏移移移移量量量量，计计计计算算算算出出出出物理地址。物理地址。物理地址。物理地址。页表寄存器页表寄存器页页页页表表表表寄寄寄寄存存存存器器器器：实实实实现现现现快快快快速速速速地地地地址址址址映映映映射射射射，存存存存储储储储执执执执行行行行进进进进程的页表起始地址。程的页表起始地址。程的页表起始地址。程的页表起始地址。页表寄存器设置在处理机硬件中。页表寄存器设置在处理机硬件中。页表寄存器设置在处理机硬件中。页表寄存器设置在处理机硬件中。当当当当进进进进程程程程被

37、被被被创创创创建建建建时时时时，其其其其页页页页表表表表起起起起始始始始地地地地址址址址记记记记载载载载于于于于进进进进程程程程PCBPCBPCBPCB中。中。中。中。当当当当进进进进程程程程被被被被调调调调度度度度执执执执行行行行时时时时，页页页页表表表表的的的的起起起起始始始始地地地地址址址址将将将将从从从从该该该该进程的进程的进程的进程的PCBPCBPCBPCB中取出，并填入页表寄存器中。中取出，并填入页表寄存器中。中取出，并填入页表寄存器中。中取出，并填入页表寄存器中。进进进进行行行行地地地地址址址址变变变变换换换换时时时时，处处处处理理理理机机机机从从从从页页页页表表表表寄寄寄寄存存

38、存存器器器器中中中中查查查查找找找找页表的地址。页表的地址。页表的地址。页表的地址。页号页号 偏移量偏移量逻辑地址逻辑地址物理地址物理地址页框号页框号 偏移量偏移量页表寄存器页表寄存器页表起始地址页表起始地址内存内存页框号页框号页表页表地址转换地址转换程序程序+偏偏移移量量图图3.18分页系统的地址变换过程分页系统的地址变换过程页框页框大页表大页表 大逻辑地址空间，页表非常大，需要占大逻辑地址空间，页表非常大，需要占用相当大的内存空间。用相当大的内存空间。比如，比如，32位逻辑地址空间，假设页面大位逻辑地址空间，假设页面大小为小为4KB（212），），则则4GB（232）的逻辑的逻辑地址空间将

39、被划分成地址空间将被划分成220个页面。个页面。大页表大页表 若采用一级页表，则其内将包含若采用一级页表，则其内将包含若采用一级页表，则其内将包含若采用一级页表，则其内将包含1 1兆（兆（兆（兆（2 22020）个）个）个）个页表项。若按字节寻址，一个页表项占页表项。若按字节寻址，一个页表项占页表项。若按字节寻址，一个页表项占页表项。若按字节寻址，一个页表项占4 4B B，则则则则一级页表需要占用一级页表需要占用一级页表需要占用一级页表需要占用4 4MBMB（2 22222）内存空间。内存空间。内存空间。内存空间。不可能将不可能将不可能将不可能将4 4MBMB的页表保存在一个连续区中。的页表保

40、存在一个连续区中。的页表保存在一个连续区中。的页表保存在一个连续区中。那么，如何处理大页表的存储与检索呢？那么，如何处理大页表的存储与检索呢？那么，如何处理大页表的存储与检索呢？那么，如何处理大页表的存储与检索呢？二级页表二级页表将一个大页表全部保存在内存中。将一个大页表全部保存在内存中。将一个大页表全部保存在内存中。将一个大页表全部保存在内存中。首先，将其分割，并离散地存储在内存的多个首先，将其分割，并离散地存储在内存的多个首先，将其分割，并离散地存储在内存的多个首先，将其分割，并离散地存储在内存的多个页框中。页框中。页框中。页框中。为之建立二级页表，记录被分割的各个页面存为之建立二级页表，

41、记录被分割的各个页面存为之建立二级页表，记录被分割的各个页面存为之建立二级页表，记录被分割的各个页面存储在哪些页框中，也称为外层页表（储在哪些页框中，也称为外层页表（储在哪些页框中，也称为外层页表（储在哪些页框中，也称为外层页表（OuterPageOuterPageTableTable）。）。）。）。对于对于对于对于4 4GBGB的进程，若采用二级页表，则对应的的进程，若采用二级页表，则对应的的进程，若采用二级页表，则对应的的进程，若采用二级页表，则对应的二级页表结构如图：二级页表结构如图：二级页表结构如图：二级页表结构如图：4GB的用户进程的用户进程4MB的一级页表的一级页表4KB的二级页表

42、的二级页表图图3.194GB进程的二级页表结构进程的二级页表结构多级页表多级页表对于某些机器，二级页表也可能非常大。可以对于某些机器，二级页表也可能非常大。可以对于某些机器，二级页表也可能非常大。可以对于某些机器，二级页表也可能非常大。可以采用多级页表，对外层页表再进行分页，将各采用多级页表，对外层页表再进行分页，将各采用多级页表，对外层页表再进行分页，将各采用多级页表，对外层页表再进行分页，将各个页面离散地存储到不相邻接的物理页框中个页面离散地存储到不相邻接的物理页框中个页面离散地存储到不相邻接的物理页框中个页面离散地存储到不相邻接的物理页框中虽然，对大页表而言，多级页表方法消除了对虽然，对

43、大页表而言，多级页表方法消除了对虽然，对大页表而言，多级页表方法消除了对虽然，对大页表而言，多级页表方法消除了对较大的连续内存空间的需要，但并未解决大页较大的连续内存空间的需要，但并未解决大页较大的连续内存空间的需要，但并未解决大页较大的连续内存空间的需要，但并未解决大页表占用较大的内存空间的问题，建立多及页表表占用较大的内存空间的问题，建立多及页表表占用较大的内存空间的问题，建立多及页表表占用较大的内存空间的问题，建立多及页表反而会增加额外的存储空间。反而会增加额外的存储空间。反而会增加额外的存储空间。反而会增加额外的存储空间。大页表大页表最好的解决办法是采用最好的解决办法是采用最好的解决办

44、法是采用最好的解决办法是采用虚拟存储技术虚拟存储技术虚拟存储技术虚拟存储技术，内存中，内存中，内存中，内存中仅装入页表的一部分。仅装入页表的一部分。仅装入页表的一部分。仅装入页表的一部分。即只将当前需要的部分页表项装入内存，其余即只将当前需要的部分页表项装入内存，其余即只将当前需要的部分页表项装入内存，其余即只将当前需要的部分页表项装入内存，其余页表项驻留在磁盘上，需要时再将它们装入内页表项驻留在磁盘上，需要时再将它们装入内页表项驻留在磁盘上，需要时再将它们装入内页表项驻留在磁盘上，需要时再将它们装入内存。存。存。存。若采用多级页表，对于正在运行的进程，必须若采用多级页表，对于正在运行的进程，

45、必须若采用多级页表，对于正在运行的进程，必须若采用多级页表，对于正在运行的进程，必须将其外层页表调入内存，而内层页表只需调入将其外层页表调入内存，而内层页表只需调入将其外层页表调入内存，而内层页表只需调入将其外层页表调入内存，而内层页表只需调入几页就可以了。几页就可以了。几页就可以了。几页就可以了。反置页表反置页表(InvertedPageTable)一般情况下，系统从进程的角度为每个进程建一般情况下，系统从进程的角度为每个进程建一般情况下，系统从进程的角度为每个进程建一般情况下，系统从进程的角度为每个进程建立一张页表，页表的表项按页号排序。立一张页表，页表的表项按页号排序。立一张页表，页表的

46、表项按页号排序。立一张页表，页表的表项按页号排序。这种方法可能导致一个大进程的页表太大，占这种方法可能导致一个大进程的页表太大，占这种方法可能导致一个大进程的页表太大，占这种方法可能导致一个大进程的页表太大，占据大量的内存空间。据大量的内存空间。据大量的内存空间。据大量的内存空间。反置页表反置页表反置页表反置页表：从内存的角度建立页表，整个系统：从内存的角度建立页表，整个系统：从内存的角度建立页表，整个系统：从内存的角度建立页表，整个系统只有一张页表。页表的表项基于内存中的每一只有一张页表。页表的表项基于内存中的每一只有一张页表。页表的表项基于内存中的每一只有一张页表。页表的表项基于内存中的每

47、一个物理页框设置，页表项按页框号的顺序排序。个物理页框设置，页表项按页框号的顺序排序。个物理页框设置，页表项按页框号的顺序排序。个物理页框设置，页表项按页框号的顺序排序。其中还必须包含页框对应的页号及其隶属进程其中还必须包含页框对应的页号及其隶属进程其中还必须包含页框对应的页号及其隶属进程其中还必须包含页框对应的页号及其隶属进程的标识符等信息。的标识符等信息。的标识符等信息。的标识符等信息。反置页表反置页表通常，反置页表需要包含成千上万个表项，利通常，反置页表需要包含成千上万个表项，利通常，反置页表需要包含成千上万个表项，利通常，反置页表需要包含成千上万个表项，利用进程用进程用进程用进程IDI

48、D和页号检索其中某一个表项的速度很和页号检索其中某一个表项的速度很和页号检索其中某一个表项的速度很和页号检索其中某一个表项的速度很慢。慢。慢。慢。可以根据进程可以根据进程可以根据进程可以根据进程IDID和页号构建和页号构建和页号构建和页号构建HashHash表。表。表。表。HashHash表表表表的每一项指向反置页表中的某一项。的每一项指向反置页表中的某一项。的每一项指向反置页表中的某一项。的每一项指向反置页表中的某一项。但是，可能会出现多个逻辑地址被映射到一个但是，可能会出现多个逻辑地址被映射到一个但是，可能会出现多个逻辑地址被映射到一个但是，可能会出现多个逻辑地址被映射到一个HashHas

49、h表项的情况。需要通过链接指针将多个冲表项的情况。需要通过链接指针将多个冲表项的情况。需要通过链接指针将多个冲表项的情况。需要通过链接指针将多个冲突的映射链接起来。突的映射链接起来。突的映射链接起来。突的映射链接起来。一般，冲突的表项一般只有一项，或两项。一般，冲突的表项一般只有一项，或两项。一般，冲突的表项一般只有一项，或两项。一般，冲突的表项一般只有一项，或两项。地址变换地址变换首先，以进程首先，以进程首先，以进程首先，以进程IDIDIDID和页号为参数，代入和页号为参数，代入和页号为参数，代入和页号为参数，代入HashHashHashHash函数函数函数函数进行计算。进行计算。进行计算。

50、进行计算。然后，根据计算结果，检索反置页表。若检索然后，根据计算结果，检索反置页表。若检索然后，根据计算结果，检索反置页表。若检索然后，根据计算结果，检索反置页表。若检索完整个反置页表都未找到与之匹配的表项，表完整个反置页表都未找到与之匹配的表项，表完整个反置页表都未找到与之匹配的表项，表完整个反置页表都未找到与之匹配的表项，表明此页尚未装入内存。明此页尚未装入内存。明此页尚未装入内存。明此页尚未装入内存。若系统支持虚拟存储技术，则产生请求调页中若系统支持虚拟存储技术，则产生请求调页中若系统支持虚拟存储技术，则产生请求调页中若系统支持虚拟存储技术，则产生请求调页中断。若系统不支持虚拟存储技术，