存储器管理存储器管理内容提要内容提要存储器管理的相关概念存储器管理的相关概念连续分配方式连续分配方式分页式存储管理方式分页式存储管理方式分段式存储管理方式分段式存储管理方式虚拟存储器虚拟存储器请求分页式存储管理方式请求分页式存储管理方式页面置换算法页面置换算法请求分段式存储管理方式请求分段式存储管理方式存储器管理存储器管理存储器管理的对象包括内存和外存，主存储器管理的对象包括内存和外存，主要讨论的是内存要讨论的是内存计算机内存被划分成两部分：系统区和计算机内存被划分成两部分：系统区和用户区。存储器的管理主要是针对用户用户区。存储器的管理主要是针对用户区的分配和管理区的分配和管理存储器管理的目的：一是方便用户使用，存储器管理的目的：一是方便用户使用，二是提高存储器的利用率二是提高存储器的利用率存储器管理的功能存储器管理的功能内存的分配与回收内存的分配与回收地址转换或重定位地址转换或重定位存储器的扩充存储器的扩充存储器共享和保护存储器共享和保护源程序从创建到执行的步骤源程序从创建到执行的步骤编编译译链链接接装装入入源程序从创建到执行的步骤源程序从创建到执行的步骤存储器管理的相关概念存储器管理的相关概念物理存储器中全部物理存储单元的集物理存储器中全部物理存储单元的集合所限定的空间称为合所限定的空间称为存储空间存储空间每个存储单元都有它自己的编号地址，每个存储单元都有它自己的编号地址，该地址被称为该地址被称为绝对地址绝对地址，或，或物理地址物理地址，或实地址或实地址存储空间的大小由系统的硬件配置决存储空间的大小由系统的硬件配置决定定存储器管理的相关概念存储器管理的相关概念用户源程序经编译链接后形成的代码用户源程序经编译链接后形成的代码所限定的地址叫做该程序的所限定的地址叫做该程序的地址空间地址空间地址空间中每个单元的地址称为地址空间中每个单元的地址称为相对相对地址地址，或，或逻辑地址逻辑地址，或虚地址，或虚地址存储器管理的相关概念存储器管理的相关概念存储分配要解决的问题是多道程序之存储分配要解决的问题是多道程序之间如何共享主存的存储空间间如何共享主存的存储空间解决存储分配问题的三种方式：直接解决存储分配问题的三种方式：直接存储分配方式、静态存储分配方式、存储分配方式、静态存储分配方式、动态存储分配方式动态存储分配方式存储器管理的相关概念存储器管理的相关概念把程序地址空间的逻辑地址转换为存储把程序地址空间的逻辑地址转换为存储空间的物理地址的工作叫做空间的物理地址的工作叫做地址重定位地址重定位，又叫又叫地址映射地址映射或地址变换或地址变换地址重定位分地址重定位分静态重定位静态重定位和和动态重定位动态重定位地址重定位的原因地址重定位的原因地址空间的逻辑地址往往与分配到的存地址空间的逻辑地址往往与分配到的存储空间的物理地址不一致，而且不能用储空间的物理地址不一致，而且不能用逻辑地址在内存中读取信息逻辑地址在内存中读取信息处理机执行用户程序时，所要访问的程处理机执行用户程序时，所要访问的程序和数据地址必须是实际的物理地址序和数据地址必须是实际的物理地址静态地址重定位静态地址重定位静态地址重定位：地址转换工作是在程静态地址重定位：地址转换工作是在程序装入主存时，由静态重定位装入程序序装入主存时，由静态重定位装入程序集中一次完成集中一次完成无硬件变换机构无硬件变换机构为每个程序分配一个连续的存储区为每个程序分配一个连续的存储区在程序执行期间不能移动，主存利用率在程序执行期间不能移动，主存利用率低低不能做到程序和数据的共享不能做到程序和数据的共享静态地址重定位过程静态地址重定位过程mov r1, 5001234OSmov r1, 15001234010050059901000110015001599装入程序装入程序作业地址空间作业地址空间存储空间存储空间把程序装入起始地把程序装入起始地址为址为1000的内存区的内存区动态地址重定位动态地址重定位装入程序把程序和数据原样装入到已分装入程序把程序和数据原样装入到已分配的存储区中，然后把这个存储区的起配的存储区中，然后把这个存储区的起始地址送入重定位寄存器中。在程序执始地址送入重定位寄存器中。在程序执行时，再将相对地址转换成绝对地址行时，再将相对地址转换成绝对地址主存利用率高主存利用率高程序不必占有连续的存储空间程序不必占有连续的存储空间便于多用户共享同一程序便于多用户共享同一程序动态地址重定位过程动态地址重定位过程mov r1, 5001234OSmov r1, 15001234010050059901000110015001599作业地址空间作业地址空间存储空间存储空间把程序装入起始地把程序装入起始地址为址为1000的内存区的内存区+1000重定位重定位寄存器寄存器程序的装入方式程序的装入方式绝对装入方式绝对装入方式可重定位方式可重定位方式动态运行时装入方式动态运行时装入方式连续分配方式连续分配方式 连续分配是指为一个用户程序分配连续分配是指为一个用户程序分配一个连续的内存空间，这种方式曾被广一个连续的内存空间，这种方式曾被广泛地应用于早期的操作系统中。泛地应用于早期的操作系统中。连续分配的两种方式连续分配的两种方式单一连续分配方式单一连续分配方式分区式分配方式分区式分配方式连续分配方式的类型连续分配方式的类型连续分配连续分配单一连续分配存储管理单一连续分配存储管理分区管理分区管理固定分区存储管理固定分区存储管理动态分区存储管理动态分区存储管理单一连续分配方式单一连续分配方式一种最简单的存储管理方式一种最简单的存储管理方式只能用于单用户、单任务的操作系统中只能用于单用户、单任务的操作系统中在这种管理方式下，内存区分为在这种管理方式下，内存区分为系统区系统区和和用户区用户区两部分，系统区仅供操作系统两部分，系统区仅供操作系统使用，用户区提供给用户使用使用，用户区提供给用户使用不支持虚拟存储方式不支持虚拟存储方式优点是管理简单，易于实现存储保护优点是管理简单，易于实现存储保护单一连续分配方式的缺点单一连续分配方式的缺点系统的存储空间浪费较大系统的存储空间浪费较大当正在执行的程序因等待某个事件，当正在执行的程序因等待某个事件，如等待外部设备输入数据，处理机就如等待外部设备输入数据，处理机就处于空闲状态处于空闲状态限制了用户程序和系统程序的可重入限制了用户程序和系统程序的可重入性，因而主存中的程序和数据不能被性，因而主存中的程序和数据不能被共享共享系统的外围设备也只有一个程序使用，系统的外围设备也只有一个程序使用，因此外围设备的利用率低因此外围设备的利用率低地址映射和地址保护地址映射和地址保护CPU逻辑地址逻辑地址界限寄界限寄存器存器+重定位重定位寄存器寄存器内存内存物理地址物理地址地址错地址错是是否否分区存储管理思想分区存储管理思想 基本思想：将主存的用户可用区划分成基本思想：将主存的用户可用区划分成若干个大小不等的区域，每个进程占据若干个大小不等的区域，每个进程占据一个区域或多个区域，从而实现多道程一个区域或多个区域，从而实现多道程序设计环境下各并发进程共享主存空间序设计环境下各并发进程共享主存空间固定分区管理固定分区管理一种最简单的可运行多道程序的存储管一种最简单的可运行多道程序的存储管理方式理方式将内存用户空间划分为若干个固定大小将内存用户空间划分为若干个固定大小的区域，每个分区只装入一道作业，这的区域，每个分区只装入一道作业，这样允许有几道作业并发运行样允许有几道作业并发运行当有空闲分区时，便可从外存的后备作当有空闲分区时，便可从外存的后备作业队列中选择一个适当大小的作业装入业队列中选择一个适当大小的作业装入该分区该分区分区的方法分区的方法分区大小相等：所有的内存分区大小相分区大小相等：所有的内存分区大小相等，缺点是缺乏灵活性等，缺点是缺乏灵活性分区大小不等：把内存区划分成含有多分区大小不等：把内存区划分成含有多个较小的分区、适量的中等分区及少量个较小的分区、适量的中等分区及少量的大分区。这样，可根据程序的大小为的大分区。这样，可根据程序的大小为之分配适当的分区之分配适当的分区内存分配内存分配 为了便于内存分配，通常将这些为了便于内存分配，通常将这些分区根据它们的大小排队，并为之建分区根据它们的大小排队，并为之建立一张分区使用表。表项中包含每个立一张分区使用表。表项中包含每个分区的起始地址、大小及状态（是否分区的起始地址、大小及状态（是否已分配）。已分配）。固定分区使用表固定分区使用表分区号分区号大小大小(KB)地址地址(K)状态状态1234153050100304575125已分配已分配已分配已分配已分配已分配已分配已分配操作系统操作系统作业作业A作业作业B作业作业C0125K45K75K30K连续分配方式的优缺点连续分配方式的优缺点优点：简单优点：简单缺点：内存利用不充分。因为作业的大缺点：内存利用不充分。因为作业的大小不可能刚好等于某个分区的大小，绝小不可能刚好等于某个分区的大小，绝大多数已分配的分区中，都有一部分存大多数已分配的分区中，都有一部分存储空间被浪费掉了，这个被浪费的空间储空间被浪费掉了，这个被浪费的空间叫做叫做内存碎片内存碎片动态分区分配动态分区分配系统初始化时，除了操作系统中常驻系统初始化时，除了操作系统中常驻主存部分以外，只存在一个空闲分区主存部分以外，只存在一个空闲分区分配程序根据进程的大小动态的划分分配程序根据进程的大小动态的划分分区分区特点是：各分区的大小是不定的；内特点是：各分区的大小是不定的；内存中分区的数目也是不定的。存中分区的数目也是不定的。动态分区分配中的数据结构动态分区分配中的数据结构空闲分区表，用来记录内存中每个空空闲分区表，用来记录内存中每个空闲分区的情况：包括分区序号，分区闲分区的情况：包括分区序号，分区始址，分区大小等数据项始址，分区大小等数据项空闲分区链，将所有的空闲分区链结空闲分区链，将所有的空闲分区链结成一个双向链表成一个双向链表分区分配算法分区分配算法首次适应算法首次适应算法FFFF循环首次适应算法循环首次适应算法最佳适应算法最佳适应算法首次适应算法首次适应算法 要求空闲分区按地址递增的次序排要求空闲分区按地址递增的次序排列。当进行内存分配时，从空闲区链链列。当进行内存分配时，从空闲区链链首开始顺序查找，直到找到第一个能满首开始顺序查找，直到找到第一个能满足其大小要求的空闲区为止。分一块给足其大小要求的空闲区为止。分一块给请求者，余下部分仍留在空闲链中。请求者，余下部分仍留在空闲链中。首次适应算法的特点首次适应算法的特点优先利用低地址部分的空闲分区，保优先利用低地址部分的空闲分区，保留了高地址部分的大空闲区留了高地址部分的大空闲区低地址端可能留下许多很小的空闲分低地址端可能留下许多很小的空闲分区，而每次查找是从低地址部分开始，区，而每次查找是从低地址部分开始，会增加查找开销会增加查找开销循环首次适应算法循环首次适应算法 由首次适应算法演化而来。在为进由首次适应算法演化而来。在为进程分配内存空间时，不再每次都从链首程分配内存空间时，不再每次都从链首开始查找，而是从上次找到的空闲分区开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直到找到的下一个空闲分区开始查找，直到找到一个能满足要求的空闲分区，从中划分一个能满足要求的空闲分区，从中划分出一块与请求大小相等的内存空间分配出一块与请求大小相等的内存空间分配给作业。给作业。循环首次适应算法的特点循环首次适应算法的特点使内存中的空闲分区分布得更均匀，使内存中的空闲分区分布得更均匀，从而减少了查找空闲分区时的开销从而减少了查找空闲分区时的开销缺乏大的空闲分区缺乏大的空闲分区最佳适应算法最佳适应算法 要扫描所有的空闲分区，以获得能要扫描所有的空闲分区，以获得能满足进程需求的且为最小的空闲区。如满足进程需求的且为最小的空闲区。如果该空闲分区大于作业的大小，则将剩果该空闲分区大于作业的大小，则将剩余空闲区仍留在空闲区链表中。可从小余空闲区仍留在空闲区链表中。可从小到大对空闲区排序，方便查找。到大对空闲区排序，方便查找。最佳适应算法的特点最佳适应算法的特点因为分配分区要查找整个链表，所以因为分配分区要查找整个链表，所以比首次适应算法效率低比首次适应算法效率低因为它可能把主存划分得更小，成为因为它可能把主存划分得更小，成为无用的碎片，所以它比首次适应要浪无用的碎片，所以它比首次适应要浪费更多的存储空间费更多的存储空间分区分配操作分区分配操作分配内存分配内存回收内存回收内存分配内存操作分配内存操作利用某种算法，从空闲分区中找到所利用某种算法，从空闲分区中找到所需大小的分区需大小的分区若找到的空闲分区和请求的分区的差若找到的空闲分区和请求的分区的差值大于事先规定的不再切割的剩余分值大于事先规定的不再切割的剩余分区的大小，则将空闲分区一分为二，区的大小，则将空闲分区一分为二，一部分分配给进程，另一部分仍作为一部分分配给进程，另一部分仍作为空闲区留在表中空闲区留在表中将分配区的首址返回给调用者将分配区的首址返回给调用者回收内存时遇到的情况回收内存时遇到的情况F1回收区回收区回收区回收区回收区回收区F1F2F2分区管理的优点分区管理的优点实现了多道程序共享主存实现了多道程序共享主存实现分区管理的系统设计相对简单，实现分区管理的系统设计相对简单，不需要更多的系统软硬件开销不需要更多的系统软硬件开销实现存储保护的手段也比较简单实现存储保护的手段也比较简单分区管理的缺点分区管理的缺点主存利用不够充分。系统中总有一部主存利用不够充分。系统中总有一部分存贮空间得不到利用，这部分被浪分存贮空间得不到利用，这部分被浪费的空间叫内存碎片费的空间叫内存碎片没有实现主存的扩充问题。没有实现主存的扩充问题。 当作业的当作业的地址空间大于存储空间时，作业无法地址空间大于存储空间时，作业无法运行。也即作业的地址空间受实际存运行。也即作业的地址空间受实际存储空间限制储空间限制可重定位分区分配原理可重定位分区分配原理 如果作业请求的存储空间大于系统如果作业请求的存储空间大于系统中任何一个分区，但小于这些分区容量中任何一个分区，但小于这些分区容量的总和时，利用动态重定位方法，移动的总和时，利用动态重定位方法，移动内存中的所有作业，使它们在内存相邻内存中的所有作业，使它们在内存相邻接。这样，我们不需要对作业做任何修接。这样，我们不需要对作业做任何修改，只要用该作业在内存的新起始地址，改，只要用该作业在内存的新起始地址，去置换原来的起始地址即可。去置换原来的起始地址即可。紧凑紧凑 这种通过移动内存中作业的位置，这种通过移动内存中作业的位置，把原来多个分散的小的空闲分区拼接成把原来多个分散的小的空闲分区拼接成一个大空闲分区的方法，称为一个大空闲分区的方法，称为“拼接拼接”或或“紧凑紧凑”。紧凑的示意图紧凑的示意图操作系统操作系统用户程序用户程序1用户程序用户程序2用户程序用户程序3用户程序用户程序410K30K14K26K操作系统操作系统用户程序用户程序1用户程序用户程序2用户程序用户程序3用户程序用户程序480K动态重定位的实现动态重定位的实现动态重定位分区分配算法动态重定位分区分配算法扩充内存扩充内存的方法的方法覆盖覆盖对换对换覆盖技术覆盖技术覆盖是指一个作业中的若干程序段或数覆盖是指一个作业中的若干程序段或数据段共享主存的某个区域据段共享主存的某个区域覆盖技术解决在小的存储空间运行大作覆盖技术解决在小的存储空间运行大作业的问题业的问题覆盖技术可以覆盖技术可以让那些不会同时执行的程让那些不会同时执行的程序段共用同一个主存区序段共用同一个主存区程序执行时，把不要求同时装入主存的程序执行时，把不要求同时装入主存的程序段组成一组，即程序段组成一组，即覆盖段覆盖段，并分配同，并分配同一个主存区（覆盖区）。覆盖段与覆盖一个主存区（覆盖区）。覆盖段与覆盖区一一对应。区一一对应。覆盖技术举例覆盖技术举例例：一个作业由六个程序段组成，下图给出了各程序段之间的逻辑调用关系。主程序主程序(30K)P1 (8K)P2 (10K)P11 (15K)P21 (20K)P22 (25K)内存分配的覆盖结构内存分配的覆盖结构OS主程序主程序 (30K)覆盖区覆盖区0 (10K)覆盖区覆盖区1 (25K)P1P2P11P21P22覆盖技术覆盖技术当执行程序引用当前尚未装入覆盖区的当执行程序引用当前尚未装入覆盖区的覆盖中的例程时，则调用覆盖管理控制覆盖中的例程时，则调用覆盖管理控制程序，请求将所需的覆盖段装入覆盖区程序，请求将所需的覆盖段装入覆盖区中，系统响应请求，并自动将所需覆盖中，系统响应请求，并自动将所需覆盖装入主存覆盖区中装入主存覆盖区中覆盖技术的关键是提供正确的覆盖结构。覆盖技术的关键是提供正确的覆盖结构。通常覆盖技术主要用于系统程序的主存通常覆盖技术主要用于系统程序的主存管理上管理上特点：打破了必须将一个作业的全部信特点：打破了必须将一个作业的全部信息装入主存后才能运行的限制息装入主存后才能运行的限制交换技术交换技术交换技术是指系统根据需要把主存中暂交换技术是指系统根据需要把主存中暂时不运行的某个时不运行的某个( (或某些或某些) )作业部分或全作业部分或全部移到外存，而把外存中的某个部移到外存，而把外存中的某个( (或某或某些些) )作业移到相应的主存，并使其投入作业移到相应的主存，并使其投入运行运行用辅存作为交换区，让多用户程序在较用辅存作为交换区，让多用户程序在较小的存储空间中通过不断地换入小的存储空间中通过不断地换入/ /换出换出而得到运行。而得到运行。交换的时机交换的时机作业的进程用完时间片或等待输入输出作业的进程用完时间片或等待输入输出作业要求扩充存贮而得不到满足时作业要求扩充存贮而得不到满足时交换技术的关键交换技术的关键设法减少每次交换的信息量。为此，常设法减少每次交换的信息量。为此，常将作业的副本保留在外存，每次换出时，将作业的副本保留在外存，每次换出时，仅换出那些修改过的信息即可仅换出那些修改过的信息即可交换主要是在作业或进程之间进行，而交换主要是在作业或进程之间进行，而覆盖则可以在同一个或不同作业间进行覆盖则可以在同一个或不同作业间进行交换打破了一个程序一旦进入主存便一交换打破了一个程序一旦进入主存便一直运行到结束的限制直运行到结束的限制离散分配方式的分类离散分配方式的分类分页存储管理分页存储管理分段存储管理分段存储管理段页式存储管理段页式存储管理分页存储管理方式分页存储管理方式在分区存储管理中，要求作业放在一个在分区存储管理中，要求作业放在一个连续的存储区域，因而会产生碎片连续的存储区域，因而会产生碎片要解决碎片问题，系统就要花费很高的要解决碎片问题，系统就要花费很高的代价去拼接它们代价去拼接它们页式存储管理的引入，是为了页式存储管理的引入，是为了解决碎片解决碎片问题问题实现原理实现原理 将一个进程的逻辑地址空间分成将一个进程的逻辑地址空间分成若干个大小相等的若干个大小相等的页页，同时把内存空，同时把内存空间以与页相等的大小划分为大小相等间以与页相等的大小划分为大小相等的内存块（物理块），这些内存块为的内存块（物理块），这些内存块为系统中的任何进程所共享。在为进程系统中的任何进程所共享。在为进程分配内存时，以块为单位将进程中的分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页接的物理块中。由于进程的最后一页经常装不满一块而形成了不可利用的经常装不满一块而形成了不可利用的碎片，称之为碎片，称之为“页内碎片页内碎片”。 页面和物理块页面和物理块页面：进程的逻辑地址空间分成若干个页面：进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各大小相等的片，称为页面或页，并为各页加以编号，从页加以编号，从0 0开始开始物理块：内存空间被分成与页面相同大物理块：内存空间被分成与页面相同大小的若干个存储块，称为物理块或内存小的若干个存储块，称为物理块或内存块，块， 也同样为它们加以编号，如也同样为它们加以编号，如0 0块、块、1 1块等等块等等页面大小页面大小 在分页系统中的页面其大小应适中。页在分页系统中的页面其大小应适中。页面若太小，一方面虽然可使内存碎片减小，面若太小，一方面虽然可使内存碎片减小，从而减少了内存碎片的总空间，从而减少了内存碎片的总空间， 有利于提高有利于提高内存利用率，但另一方面也会使每个进程占内存利用率，但另一方面也会使每个进程占用较多的页面，从而导致进程的页表过长，用较多的页面，从而导致进程的页表过长，占用大量内存；占用大量内存； 此外，还会降低页面换进换此外，还会降低页面换进换出的效率。然而，如果选择的页面较大，虽出的效率。然而，如果选择的页面较大，虽然可以减少页表的长度，提高页面换进换出然可以减少页表的长度，提高页面换进换出的速度，但却又会使页内碎片增大。因此，的速度，但却又会使页内碎片增大。因此，页面的大小应选择得适中，且页面大小应是页面的大小应选择得适中，且页面大小应是2 2的幂，通常为的幂，通常为512 B8 KB512 B8 KB。 页面地址结构页面地址结构分页地址结构如下：页页 号号 P位移量位移量W3112110 对某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按下式求得： 页表的结构页表的结构页号用户程序0页1页2页3页4页5页n页02132638459012345678910块号内存页表地址变换机构地址变换机构页表寄存器页表始址页表长度页号页内地址10b页表1逻辑地址L页号块号23物理地址越界中断地址变换举例地址变换举例页表寄存器50070100页表逻辑地址L每页大小1024内存地址：51024+100=5220012345657915131016500500+0=5005100快表和联想寄存器快表和联想寄存器为了提高存取速度，可在地址变换机构为了提高存取速度，可在地址变换机构中增设一个具有并行查找能力的高速缓中增设一个具有并行查找能力的高速缓冲寄存器组，又叫冲寄存器组，又叫联想存储器联想存储器，用来存，用来存放页表的一部分（放页表的一部分（快表快表）。）。联想存贮器的存取速度比主存高，但造联想存贮器的存取速度比主存高，但造价也高，只能少量采用。整个系统通常价也高，只能少量采用。整个系统通常只要用只要用8 81616个寄存器就可使程序执行个寄存器就可使程序执行速度大大提高。速度大大提高。快表的结构快表的结构页号块号访问位状态位访问位：指示该页最近是否被访问过。0表示没有被访问，1表示访问过；状态位：指示该寄存器是否被占用。0表示空闲，1表示占用。具有快表的地址变换机构具有快表的地址变换机构页表寄存器页表始址页表长度页号页内地址b页表逻辑地址L页号块号物理地址越界中断页号 块号b输输入入寄寄存存器器bd分段存储管理方式的引入分段存储管理方式的引入方便编程方便编程分段共享分段共享分段保护分段保护动态链接动态链接动态增长动态增长分段的原理分段的原理每个作业的地址空间按照程序自身的逻每个作业的地址空间按照程序自身的逻辑关系划分成若干段，每个段都有自己辑关系划分成若干段，每个段都有自己的段名的段名每个段的地址空间都是从每个段的地址空间都是从“0”0”开始编开始编址的一维地址空间址的一维地址空间作业的地址空间是二维地址空间作业的地址空间是二维地址空间每一个逻辑地址均由两部分组成：段号每一个逻辑地址均由两部分组成：段号和段内地址和段内地址段号段号段内地址段内地址段表段表分段系统的地址转换过程分段系统的地址转换过程分页和分段的主要区别分页和分段的主要区别页是信息的物理单位，段则是信息的页是信息的物理单位，段则是信息的逻辑单位；逻辑单位；页的大小固定且由系统硬件决定，段页的大小固定且由系统硬件决定，段的长度则不固定，大小取决于用户所的长度则不固定，大小取决于用户所编写的程序；编写的程序；分页的作业地址空间是一维的，而分分页的作业地址空间是一维的，而分段的作业地址空间是二维的。段的作业地址空间是二维的。分段系统的共享示意图分段系统的共享示意图在分段系统中，为实现共享，只需为文本编辑程在分段系统中，为实现共享，只需为文本编辑程序设置一个段表项，如下图：序设置一个段表项，如下图：进程进程1进程进程2段表段表段长段长基址基址editoreditorData 1Data 2editorData 1Data 21608016080804040240380240280380420可重入代码可重入代码 可重入代码，又称纯代码，是一可重入代码，又称纯代码，是一种允许多个进程同时访问的代码。为种允许多个进程同时访问的代码。为使各个进程执行的代码完全相同，绝使各个进程执行的代码完全相同，绝不允许可重入代码在执行中有任何改不允许可重入代码在执行中有任何改变。变。段页式存储管理原理段页式存储管理原理 段页式系统的基本原理是分段和段页式系统的基本原理是分段和分页原理的组合，即先将用户程序分分页原理的组合，即先将用户程序分为若干个段，把每个段分成若干个页，为若干个段，把每个段分成若干个页，并为每个段赋予一个段名。并为每个段赋予一个段名。作业地址空间和地址结构作业地址空间和地址结构主程序段主程序段子程序段子程序段数据段数据段段号段号段内页号段内页号页内地址页内地址04K8K12K15K16K04K8K8K4K010K12K利用段表和页表实现地址映射利用段表和页表实现地址映射地址变换机构地址变换机构存储管理遇到的两种情况存储管理遇到的两种情况作业很大，要求的内存空间超过了内存作业很大，要求的内存空间超过了内存总量，致使作业无法运行总量，致使作业无法运行大量作业要运行，内存容量不足以容纳大量作业要运行，内存容量不足以容纳所有作业，这时只能将少数作业装入内所有作业，这时只能将少数作业装入内存，其他大量作业留在外存上存，其他大量作业留在外存上局部性原理局部性原理 在一段时间，进程集中在一组子在一段时间，进程集中在一组子程序或循环中执行，导致所有的存储程序或循环中执行，导致所有的存储器访问局限于进程地址空间的一个固器访问局限于进程地址空间的一个固定子集（进程的工作集）。定子集（进程的工作集）。虚拟存储器的定义虚拟存储器的定义 虚拟存储器是指具有请求调入虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。存容量加以扩充的一种存储器系统。虚拟存储器的逻辑容量由内存和外虚拟存储器的逻辑容量由内存和外存之和来确定，其运行速度接近于存之和来确定，其运行速度接近于内存速度，而每位的成本接近于外内存速度，而每位的成本接近于外存。存。引入虚拟存储器的好处引入虚拟存储器的好处运行大程序运行大程序大的用户空间大的用户空间并发并发易于开发易于开发虚拟存储器的特征虚拟存储器的特征离散性离散性多次性多次性对换性对换性虚拟性虚拟性虚拟存储器的实现方式虚拟存储器的实现方式分页请求系统分页请求系统请求分段系统请求分段系统实现请求分页实现请求分页( (段段) )的硬件支持的硬件支持请求分页请求分页( (段段) )的页的页( (段段) ) 表机制表机制缺页缺页( (段段) )中断机构中断机构地址变换机构地址变换机构虚拟存储器的定义虚拟存储器的定义 请求分页存储管理方式是建立请求分页存储管理方式是建立在纯分页基础上的，是目前常用的在纯分页基础上的，是目前常用的一种实现虚拟存储器的方式。由于一种实现虚拟存储器的方式。由于它换进换出的基本单位是固定长度它换进换出的基本单位是固定长度的页面，所以请求分页管理方式实的页面，所以请求分页管理方式实现起来相对容易。现起来相对容易。页表机制页表机制 在请求分页系统中需要的主要数据结构仍然是页表。其基本作用是将用户地址空间的逻辑地址转换为内存空间的物理地址。页号页号 物理块号物理块号 状态位状态位P 访问字段访问字段A 修改位修改位M 外存地址外存地址实现请求分页实现请求分页( (段段) )的硬件支持的硬件支持 在请求分页系统中，每当要访问的在请求分页系统中，每当要访问的页面不在内存时，要产生一个缺页中断。页面不在内存时，要产生一个缺页中断。它是一种特殊的中断，主要表现在：它是一种特殊的中断，主要表现在：在指令执行期间产生和处理中断信号在指令执行期间产生和处理中断信号一条指令在执行期间，可产生多次缺页一条指令在执行期间，可产生多次缺页中断中断请求分页系统地址变换机构请求分页系统地址变换机构页面分配的三个问题页面分配的三个问题保证进程正常运行所需的最少物理块数保证进程正常运行所需的最少物理块数的确定的确定分配的物理块数是固定的还是可变的分配的物理块数是固定的还是可变的分配的物理块数是采取平均分配算法还分配的物理块数是采取平均分配算法还是根据进程大小按比例予以分配是根据进程大小按比例予以分配页面分配和置换策略页面分配和置换策略固定分配局部置换固定分配局部置换可变分配全局置换可变分配全局置换可变分配局部置换可变分配局部置换页面分配算法页面分配算法平均分配算法平均分配算法按比例分配算法按比例分配算法考虑优先权的分配算法考虑优先权的分配算法按比例分配算法按比例分配算法若系统中有若系统中有n个进程，每个进程的页面数为个进程，每个进程的页面数为Si，则，则系统中的页面数总和为：系统中的页面数总和为：又设系统中可用的物理块总数为又设系统中可用的物理块总数为m，则每个进程，则每个进程能分到的物理块数为能分到的物理块数为bi，则有：，则有：按比例分配算法按比例分配算法 在实际应用中，为了照顾重要的、紧迫的作在实际应用中，为了照顾重要的、紧迫的作业能尽快地完成，应为它分配较多的内存空间。业能尽快地完成，应为它分配较多的内存空间。通常采用的方法就是把内存可供分配的物理块分通常采用的方法就是把内存可供分配的物理块分为两部分：一部分按比例分配给各进程；另一部为两部分：一部分按比例分配给各进程；另一部分则根据各进程的优先权，分配给各进程。分则根据各进程的优先权，分配给各进程。何时调入页面何时调入页面 为了确定系统将进程运行时所缺的为了确定系统将进程运行时所缺的页面调入内存的时机，可采取两种策略：页面调入内存的时机，可采取两种策略：预调页策略预调页策略请求调页策略请求调页策略何处调入页面何处调入页面 在请求分页系统中，把外存分为在请求分页系统中，把外存分为两部分：一部分是文件区，用于存放两部分：一部分是文件区，用于存放文件；另一部分是对换区，用于存放文件；另一部分是对换区，用于存放对换页面。对换页面。页面置换算法页面置换算法 通常，把选择换出的页面的算法称为页面置通常，把选择换出的页面的算法称为页面置换算法换算法(Page-Replacement Algorithms)。置换。置换算法的好坏将直接影响系统的性能，不适当的算算法的好坏将直接影响系统的性能，不适当的算法可能导致进程发生法可能导致进程发生“抖动抖动”。 一个好的页面置换算法，应具有较低的页面一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访更换频率。从理论上讲，应将那些以后不再会访问的页面换出，或把那些在较长时间内不会再被问的页面换出，或把那些在较长时间内不会再被访问的页面调出。访问的页面调出。最佳置换算法最佳置换算法 最佳置换算法是由最佳置换算法是由BeladyBelady于于19661966年提出的一种理论上的算法。其选择年提出的一种理论上的算法。其选择的页面，将是永不使用的，或者是在的页面，将是永不使用的，或者是在最长时间内不再被访问的页面。最长时间内不再被访问的页面。 对于固定分配页面方式，采用最对于固定分配页面方式，采用最佳置换算法可保证获得最低的缺页率。佳置换算法可保证获得最低的缺页率。最佳页面置换算法举例最佳页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 最佳页面置换算法举例最佳页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：77 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 最佳页面置换算法举例最佳页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：707 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 最佳页面置换算法举例最佳页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：707 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 1最佳页面置换算法举例最佳页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：707 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 12最佳页面置换算法举例最佳页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：07 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 12最佳页面置换算法举例最佳页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：07 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 123最佳页面置换算法举例最佳页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：07 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 23最佳页面置换算法举例最佳页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：07 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 234最佳页面置换算法举例最佳页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 234最佳页面置换算法举例最佳页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 234最佳页面置换算法举例最佳页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 234 0最佳页面置换算法举例最佳页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 230最佳页面置换算法举例最佳页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 230最佳页面置换算法举例最佳页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 2301最佳页面置换算法举例最佳页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 201最佳页面置换算法举例最佳页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 201最佳页面置换算法举例最佳页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 201最佳页面置换算法举例最佳页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 2017最佳页面置换算法举例最佳页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 017最佳页面置换算法举例最佳页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 017先进先出页面置换算法先进先出页面置换算法 该算法总是淘汰最先进入内存的该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久页面，即选择在内存中驻留时间最久的页面予以淘汰。的页面予以淘汰。 该算法实现简单，将进入内存的该算法实现简单，将进入内存的进程按照先后次序链接成一个队列，进程按照先后次序链接成一个队列，设置一个替换指针，使它总是指向最设置一个替换指针，使它总是指向最老的页面。老的页面。先进先出页面置换算法举例先进先出页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 先进先出页面置换算法举例先进先出页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：77 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 先进先出页面置换算法举例先进先出页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：707 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 先进先出页面置换算法举例先进先出页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：707 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 1先进先出页面置换算法举例先进先出页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：707 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 12先进先出页面置换算法举例先进先出页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：07 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 12先进先出页面置换算法举例先进先出页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：07 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 123先进先出页面置换算法举例先进先出页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 1230先进先出页面置换算法举例先进先出页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 2304先进先出页面置换算法举例先进先出页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 4302先进先出页面置换算法举例先进先出页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 420 3先进先出页面置换算法举例先进先出页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 4230先进先出页面置换算法举例先进先出页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 023先进先出页面置换算法举例先进先出页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 023先进先出页面置换算法举例先进先出页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 0231先进先出页面置换算法举例先进先出页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 013 2先进先出页面置换算法举例先进先出页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 012先进先出页面置换算法举例先进先出页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 012先进先出页面置换算法举例先进先出页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 0127先进先出页面置换算法举例先进先出页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 7120先进先出页面置换算法举例先进先出页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 702 1最近最久未使用最近最久未使用LRU页面置换算法页面置换算法 LRULRU算法是选择最近最久未使用算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录页面上次面一个访问字段，用来记录页面上次被访问以来所经历的时间被访问以来所经历的时间t t。当须淘汰。当须淘汰一个页面时，选择现有页面中一个页面时，选择现有页面中t t值最大值最大的，即最近最久未使用的页面予以淘的，即最近最久未使用的页面予以淘汰。汰。LRULRU算法举例算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 LRULRU算法举例算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：77 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 LRULRU算法举例算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：707 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 LRULRU算法举例算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：707 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 1LRULRU算法举例算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：707 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 12LRULRU算法举例算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：07 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 12LRULRU算法举例算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：07 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 123LRULRU算法举例算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：07 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 32LRULRU算法举例算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：07 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 32 4LRULRU算法举例算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：07 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 342LRULRU算法举例算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：07 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 243LRULRU算法举例算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：37 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 24 0LRULRU算法举例算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：37 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 20LRULRU算法举例算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：37 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 20LRULRU算法举例算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：37 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 20 1LRULRU算法举例算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：37 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 21LRULRU算法举例算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：37 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 210LRULRU算法举例算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：07 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 217LRULRU算法举例算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：07 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 71LRULRU算法举例算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：07 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 71LRULRU算法需要解决的问题算法需要解决的问题LRULRU算法所要解决的问题是：算法所要解决的问题是：一个进程在内存中的各个页面各有多久一个进程在内存中的各个页面各有多久时间没有被访问时间没有被访问如何快速了解哪个页面是最近最久未使如何快速了解哪个页面是最近最久未使用的页面用的页面LRULRU算法所需的数据结构有寄存器和栈算法所需的数据结构有寄存器和栈简单简单Clock Clock 算法算法 利用利用ClockClock算法，为每页设置一位算法，为每页设置一位访问位，再将内存中所有页面都通过访问位，再将内存中所有页面都通过指针链成一个循环队列。当某页被访指针链成一个循环队列。当某页被访问时，其访问位被置问时，其访问位被置1 1。置换算法在选。置换算法在选择淘汰页面时，只需照择淘汰页面时，只需照FIFOFIFO算法检查算法检查其访问位。当检查到队列的最后一个其访问位。当检查到队列的最后一个页面后，再返回到队首检查第一个页页面后，再返回到队首检查第一个页面。面。ClockClock算法流程图算法流程图入口入口查寻指针前进一步，指查寻指针前进一步，指向下一个表目向下一个表目页面访问位页面访问位0?置页面访置页面访问位问位0选择该页面淘汰选择该页面淘汰返回返回是是否否改进型改进型Clock Clock 算法算法 在改进型在改进型ClockClock算法中，除须考虑算法中，除须考虑页面的使用情况外，还须再增加置换页面的使用情况外，还须再增加置换代价这一因素，算法将同时满足这两代价这一因素，算法将同时满足这两个条件的页面将首选淘汰的页面。个条件的页面将首选淘汰的页面。请求分段存储管理方式请求分段存储管理方式 其基本思想为：把作业的所有段其基本思想为：把作业的所有段的副本存放在外存中。当作业被调度的副本存放在外存中。当作业被调度运行时，首先把当前需要的段装入主运行时，首先把当前需要的段装入主存，在作业运行过程中，缺段时，再存，在作业运行过程中，缺段时，再将相应的段装入。将相应的段装入。请求分段的硬件支持请求分段的硬件支持 请求分段管理所需的主要数据结构为段表，请求分段管理所需的主要数据结构为段表，其主要结构如下：其主要结构如下：段名段名 段长段长段的段的基址基址存在存在位位p修修 改改字段字段M访访 问问字段字段A存取存取方式方式外存外存起址起址增补增补位位缺段中断机构缺段中断机构地址变换机构地址变换机构共享段表共享段表环保护机构环保护机构