计算机操作系统课件第4章存储器管理

1、存储器管理存储器管理内容提要内容提要存储器管理的相关概念存储器管理的相关概念连续分配方式连续分配方式分页式存储管理方式分页式存储管理方式分段式存储管理方式分段式存储管理方式虚拟存储器虚拟存储器请求分页式存储管理方式请求分页式存储管理方式页面置换算法页面置换算法请求分段式存储管理方式请求分段式存储管理方式存储器管理存储器管理存储器管理的对象包括内存和外存，主存储器管理的对象包括内存和外存，主要讨论的是内存要讨论的是内存计算机内存被划分成两部分：系统区和计算机内存被划分成两部分：系统区和用户区。存储器的管理主要是针对用户用户区。存储器的管理主要是针对用户区的分配和管理区的分配和管理存储器管理的目的

2、：一是方便用户使用，存储器管理的目的：一是方便用户使用，二是提高存储器的利用率二是提高存储器的利用率存储器管理的功能存储器管理的功能内存的分配与回收内存的分配与回收地址转换或重定位地址转换或重定位存储器的扩充存储器的扩充存储器共享和保护存储器共享和保护源程序从创建到执行的步骤源程序从创建到执行的步骤编编译译链链接接装装入入源程序从创建到执行的步骤源程序从创建到执行的步骤存储器管理的相关概念存储器管理的相关概念物理存储器中全部物理存储单元的集物理存储器中全部物理存储单元的集合所限定的空间称为合所限定的空间称为存储空间存储空间每个存储单元都有它自己的编号地址，每个存储单元都有它自己的编号地址，该地

3、址被称为该地址被称为绝对地址绝对地址，或，或物理地址物理地址，或实地址或实地址存储空间的大小由系统的硬件配置决存储空间的大小由系统的硬件配置决定定存储器管理的相关概念存储器管理的相关概念用户源程序经编译链接后形成的代码用户源程序经编译链接后形成的代码所限定的地址叫做该程序的所限定的地址叫做该程序的地址空间地址空间地址空间中每个单元的地址称为地址空间中每个单元的地址称为相对相对地址地址，或，或逻辑地址逻辑地址，或虚地址，或虚地址存储器管理的相关概念存储器管理的相关概念存储分配要解决的问题是多道程序之存储分配要解决的问题是多道程序之间如何共享主存的存储空间间如何共享主存的存储空间解决存储分配问题的

4、三种方式：直接解决存储分配问题的三种方式：直接存储分配方式、静态存储分配方式、存储分配方式、静态存储分配方式、动态存储分配方式动态存储分配方式存储器管理的相关概念存储器管理的相关概念把程序地址空间的逻辑地址转换为存储把程序地址空间的逻辑地址转换为存储空间的物理地址的工作叫做空间的物理地址的工作叫做地址重定位地址重定位，又叫又叫地址映射地址映射或地址变换或地址变换地址重定位分地址重定位分静态重定位静态重定位和和动态重定位动态重定位地址重定位的原因地址重定位的原因地址空间的逻辑地址往往与分配到的存地址空间的逻辑地址往往与分配到的存储空间的物理地址不一致，而且不能用储空间的物理地址不一致，而且不能用

5、逻辑地址在内存中读取信息逻辑地址在内存中读取信息处理机执行用户程序时，所要访问的程处理机执行用户程序时，所要访问的程序和数据地址必须是实际的物理地址序和数据地址必须是实际的物理地址静态地址重定位静态地址重定位静态地址重定位：地址转换工作是在程静态地址重定位：地址转换工作是在程序装入主存时，由静态重定位装入程序序装入主存时，由静态重定位装入程序集中一次完成集中一次完成无硬件变换机构无硬件变换机构为每个程序分配一个连续的存储区为每个程序分配一个连续的存储区在程序执行期间不能移动，主存利用率在程序执行期间不能移动，主存利用率低低不能做到程序和数据的共享不能做到程序和数据的共享静态地址重定位过程静态地

6、址重定位过程mov r1, 5001234osmov r1, 15001234010050059901000110015001599装入程序装入程序作业地址空间作业地址空间存储空间存储空间把程序装入起始地把程序装入起始地址为址为1000的内存区的内存区动态地址重定位动态地址重定位装入程序把程序和数据原样装入到已分装入程序把程序和数据原样装入到已分配的存储区中，然后把这个存储区的起配的存储区中，然后把这个存储区的起始地址送入重定位寄存器中。在程序执始地址送入重定位寄存器中。在程序执行时，再将相对地址转换成绝对地址行时，再将相对地址转换成绝对地址主存利用率高主存利用率高程序不必占有连续的存储空间程

7、序不必占有连续的存储空间便于多用户共享同一程序便于多用户共享同一程序动态地址重定位过程动态地址重定位过程mov r1, 5001234osmov r1, 15001234010050059901000110015001599作业地址空间作业地址空间存储空间存储空间把程序装入起始地把程序装入起始地址为址为1000的内存区的内存区+1000重定位重定位寄存器寄存器程序的装入方式程序的装入方式绝对装入方式绝对装入方式可重定位方式可重定位方式动态运行时装入方式动态运行时装入方式连续分配方式连续分配方式 连续分配是指为一个用户程序分配连续分配是指为一个用户程序分配一个连续的内存空间，这种方式曾被广一个连

8、续的内存空间，这种方式曾被广泛地应用于早期的操作系统中。泛地应用于早期的操作系统中。连续分配的两种方式连续分配的两种方式单一连续分配方式单一连续分配方式分区式分配方式分区式分配方式连续分配方式的类型连续分配方式的类型连续分配连续分配单一连续分配存储管理单一连续分配存储管理分区管理分区管理固定分区存储管理固定分区存储管理动态分区存储管理动态分区存储管理单一连续分配方式单一连续分配方式一种最简单的存储管理方式一种最简单的存储管理方式只能用于单用户、单任务的操作系统中只能用于单用户、单任务的操作系统中在这种管理方式下，内存区分为在这种管理方式下，内存区分为系统区系统区和和用户区用户区两部分，系统区仅

9、供操作系统两部分，系统区仅供操作系统使用，用户区提供给用户使用使用，用户区提供给用户使用不支持虚拟存储方式不支持虚拟存储方式优点是管理简单，易于实现存储保护优点是管理简单，易于实现存储保护单一连续分配方式的缺点单一连续分配方式的缺点系统的存储空间浪费较大系统的存储空间浪费较大当正在执行的程序因等待某个事件，当正在执行的程序因等待某个事件，如等待外部设备输入数据，处理机就如等待外部设备输入数据，处理机就处于空闲状态处于空闲状态限制了用户程序和系统程序的可重入限制了用户程序和系统程序的可重入性，因而主存中的程序和数据不能被性，因而主存中的程序和数据不能被共享共享系统的外围设备也只有一个程序使用，系

10、统的外围设备也只有一个程序使用，因此外围设备的利用率低因此外围设备的利用率低地址映射和地址保护地址映射和地址保护cpu逻辑地址逻辑地址界限寄界限寄存器存器+重定位重定位寄存器寄存器内存内存物理地址物理地址地址错地址错是是否否分区存储管理思想分区存储管理思想 基本思想：将主存的用户可用区划分成基本思想：将主存的用户可用区划分成若干个大小不等的区域，每个进程占据若干个大小不等的区域，每个进程占据一个区域或多个区域，从而实现多道程一个区域或多个区域，从而实现多道程序设计环境下各并发进程共享主存空间序设计环境下各并发进程共享主存空间固定分区管理固定分区管理一种最简单的可运行多道程序的存储管一种最简单的

11、可运行多道程序的存储管理方式理方式将内存用户空间划分为若干个固定大小将内存用户空间划分为若干个固定大小的区域，每个分区只装入一道作业，这的区域，每个分区只装入一道作业，这样允许有几道作业并发运行样允许有几道作业并发运行当有空闲分区时，便可从外存的后备作当有空闲分区时，便可从外存的后备作业队列中选择一个适当大小的作业装入业队列中选择一个适当大小的作业装入该分区该分区分区的方法分区的方法分区大小相等：所有的内存分区大小相分区大小相等：所有的内存分区大小相等，缺点是缺乏灵活性等，缺点是缺乏灵活性分区大小不等：把内存区划分成含有多分区大小不等：把内存区划分成含有多个较小的分区、适量的中等分区及少量个较

12、小的分区、适量的中等分区及少量的大分区。这样，可根据程序的大小为的大分区。这样，可根据程序的大小为之分配适当的分区之分配适当的分区内存分配内存分配 为了便于内存分配，通常将这些为了便于内存分配，通常将这些分区根据它们的大小排队，并为之建分区根据它们的大小排队，并为之建立一张分区使用表。表项中包含每个立一张分区使用表。表项中包含每个分区的起始地址、大小及状态（是否分区的起始地址、大小及状态（是否已分配）。已分配）。固定分区使用表固定分区使用表分区号分区号大小大小(kb)地址地址(k)状态状态1234153050100304575125已分配已分配已分配已分配已分配已分配已分配已分配操作系统操作系

13、统作业作业a作业作业b作业作业c0125k45k75k30k连续分配方式的优缺点连续分配方式的优缺点优点：简单优点：简单缺点：内存利用不充分。因为作业的大缺点：内存利用不充分。因为作业的大小不可能刚好等于某个分区的大小，绝小不可能刚好等于某个分区的大小，绝大多数已分配的分区中，都有一部分存大多数已分配的分区中，都有一部分存储空间被浪费掉了，这个被浪费的空间储空间被浪费掉了，这个被浪费的空间叫做叫做内存碎片内存碎片动态分区分配动态分区分配系统初始化时，除了操作系统中常驻系统初始化时，除了操作系统中常驻主存部分以外，只存在一个空闲分区主存部分以外，只存在一个空闲分区分配程序根据进程的大小动态的划分

14、分配程序根据进程的大小动态的划分分区分区特点是：各分区的大小是不定的；内特点是：各分区的大小是不定的；内存中分区的数目也是不定的。存中分区的数目也是不定的。动态分区分配中的数据结构动态分区分配中的数据结构空闲分区表，用来记录内存中每个空空闲分区表，用来记录内存中每个空闲分区的情况：包括分区序号，分区闲分区的情况：包括分区序号，分区始址，分区大小等数据项始址，分区大小等数据项空闲分区链，将所有的空闲分区链结空闲分区链，将所有的空闲分区链结成一个双向链表成一个双向链表分区分配算法分区分配算法首次适应算法首次适应算法ffff循环首次适应算法循环首次适应算法最佳适应算法最佳适应算法首次适应算法首次适应

15、算法 要求空闲分区按地址递增的次序排要求空闲分区按地址递增的次序排列。当进行内存分配时，从空闲区链链列。当进行内存分配时，从空闲区链链首开始顺序查找，直到找到第一个能满首开始顺序查找，直到找到第一个能满足其大小要求的空闲区为止。分一块给足其大小要求的空闲区为止。分一块给请求者，余下部分仍留在空闲链中。请求者，余下部分仍留在空闲链中。首次适应算法的特点首次适应算法的特点优先利用低地址部分的空闲分区，保优先利用低地址部分的空闲分区，保留了高地址部分的大空闲区留了高地址部分的大空闲区低地址端可能留下许多很小的空闲分低地址端可能留下许多很小的空闲分区，而每次查找是从低地址部分开始，区，而每次查找是从低

16、地址部分开始，会增加查找开销会增加查找开销循环首次适应算法循环首次适应算法 由首次适应算法演化而来。在为进由首次适应算法演化而来。在为进程分配内存空间时，不再每次都从链首程分配内存空间时，不再每次都从链首开始查找，而是从上次找到的空闲分区开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直到找到的下一个空闲分区开始查找，直到找到一个能满足要求的空闲分区，从中划分一个能满足要求的空闲分区，从中划分出一块与请求大小相等的内存空间分配出一块与请求大小相等的内存空间分配给作业。给作业。循环首次适应算法的特点循环首次适应算法的特点使内存中的空闲分区分布得更均匀，使内存中的空闲分区分布得更均匀，

17、从而减少了查找空闲分区时的开销从而减少了查找空闲分区时的开销缺乏大的空闲分区缺乏大的空闲分区最佳适应算法最佳适应算法 要扫描所有的空闲分区，以获得能要扫描所有的空闲分区，以获得能满足进程需求的且为最小的空闲区。如满足进程需求的且为最小的空闲区。如果该空闲分区大于作业的大小，则将剩果该空闲分区大于作业的大小，则将剩余空闲区仍留在空闲区链表中。可从小余空闲区仍留在空闲区链表中。可从小到大对空闲区排序，方便查找。到大对空闲区排序，方便查找。最佳适应算法的特点最佳适应算法的特点因为分配分区要查找整个链表，所以因为分配分区要查找整个链表，所以比首次适应算法效率低比首次适应算法效率低因为它可能把主存划分得

18、更小，成为因为它可能把主存划分得更小，成为无用的碎片，所以它比首次适应要浪无用的碎片，所以它比首次适应要浪费更多的存储空间费更多的存储空间分区分配操作分区分配操作分配内存分配内存回收内存回收内存分配内存操作分配内存操作利用某种算法，从空闲分区中找到所利用某种算法，从空闲分区中找到所需大小的分区需大小的分区若找到的空闲分区和请求的分区的差若找到的空闲分区和请求的分区的差值大于事先规定的不再切割的剩余分值大于事先规定的不再切割的剩余分区的大小，则将空闲分区一分为二，区的大小，则将空闲分区一分为二，一部分分配给进程，另一部分仍作为一部分分配给进程，另一部分仍作为空闲区留在表中空闲区留在表中将分配区的

19、首址返回给调用者将分配区的首址返回给调用者回收内存时遇到的情况回收内存时遇到的情况f1回收区回收区回收区回收区回收区回收区f1f2f2分区管理的优点分区管理的优点实现了多道程序共享主存实现了多道程序共享主存实现分区管理的系统设计相对简单，实现分区管理的系统设计相对简单，不需要更多的系统软硬件开销不需要更多的系统软硬件开销实现存储保护的手段也比较简单实现存储保护的手段也比较简单分区管理的缺点分区管理的缺点主存利用不够充分。系统中总有一部主存利用不够充分。系统中总有一部分存贮空间得不到利用，这部分被浪分存贮空间得不到利用，这部分被浪费的空间叫内存碎片费的空间叫内存碎片没有实现主存的扩充问题。没有实

20、现主存的扩充问题。 当作业的当作业的地址空间大于存储空间时，作业无法地址空间大于存储空间时，作业无法运行。也即作业的地址空间受实际存运行。也即作业的地址空间受实际存储空间限制储空间限制可重定位分区分配原理可重定位分区分配原理 如果作业请求的存储空间大于系统如果作业请求的存储空间大于系统中任何一个分区，但小于这些分区容量中任何一个分区，但小于这些分区容量的总和时，利用动态重定位方法，移动的总和时，利用动态重定位方法，移动内存中的所有作业，使它们在内存相邻内存中的所有作业，使它们在内存相邻接。这样，我们不需要对作业做任何修接。这样，我们不需要对作业做任何修改，只要用该作业在内存的新起始地址，改，只

21、要用该作业在内存的新起始地址，去置换原来的起始地址即可。去置换原来的起始地址即可。紧凑紧凑 这种通过移动内存中作业的位置，这种通过移动内存中作业的位置，把原来多个分散的小的空闲分区拼接成把原来多个分散的小的空闲分区拼接成一个大空闲分区的方法，称为一个大空闲分区的方法，称为“拼接拼接”或或“紧凑紧凑”。紧凑的示意图紧凑的示意图操作系统操作系统用户程序用户程序1用户程序用户程序2用户程序用户程序3用户程序用户程序410k30k14k26k操作系统操作系统用户程序用户程序1用户程序用户程序2用户程序用户程序3用户程序用户程序480k动态重定位的实现动态重定位的实现load1,250036501002

22、50050002500相对地址10000重定位寄存器load1,250036510000101001250015000作业j处理机一侧存储器一侧主存动态重定位分区分配算法动态重定位分区分配算法请求分配u.size分区检索空闲分区链(表)找到大于u.size的可用区否?按动态分区方式进行分配修改有关的数据结构返回分区号及首批空闲分区总和u.size?进行紧凑形成连续空闲区修改有关的数据结构否是无法分配返回否扩充内存扩充内存的方法的方法覆盖覆盖对换对换覆盖技术覆盖技术覆盖是指一个作业中的若干程序段或数覆盖是指一个作业中的若干程序段或数据段共享主存的某个区域据段共享主存的某个区域覆盖技术解决在小的存

23、储空间运行大作覆盖技术解决在小的存储空间运行大作业的问题业的问题覆盖技术可以覆盖技术可以让那些不会同时执行的程让那些不会同时执行的程序段共用同一个主存区序段共用同一个主存区程序执行时，把不要求同时装入主存的程序执行时，把不要求同时装入主存的程序段组成一组，即程序段组成一组，即覆盖段覆盖段，并分配同，并分配同一个主存区（覆盖区）。覆盖段与覆盖一个主存区（覆盖区）。覆盖段与覆盖区一一对应。区一一对应。覆盖技术举例覆盖技术举例例：一个作业由六个程序段组成，下图给出了例：一个作业由六个程序段组成，下图给出了各程序段之间的逻辑调用关系。各程序段之间的逻辑调用关系。主程序主程序(30k)p1 (8k)p2

24、 (10k)p11 (15k)p21 (20k)p22 (25k)内存分配的覆盖结构内存分配的覆盖结构os主程序主程序 (30k)覆盖区覆盖区0 (10k)覆盖区覆盖区1 (25k)p1p2p11p21p22覆盖技术覆盖技术当执行程序引用当前尚未装入覆盖区的当执行程序引用当前尚未装入覆盖区的覆盖中的例程时，则调用覆盖管理控制覆盖中的例程时，则调用覆盖管理控制程序，请求将所需的覆盖段装入覆盖区程序，请求将所需的覆盖段装入覆盖区中，系统响应请求，并自动将所需覆盖中，系统响应请求，并自动将所需覆盖装入主存覆盖区中装入主存覆盖区中覆盖技术的关键是提供正确的覆盖结构。覆盖技术的关键是提供正确的覆盖结构。

25、通常覆盖技术主要用于系统程序的主存通常覆盖技术主要用于系统程序的主存管理上管理上特点：打破了必须将一个作业的全部信特点：打破了必须将一个作业的全部信息装入主存后才能运行的限制息装入主存后才能运行的限制交换技术交换技术交换技术是指系统根据需要把主存中暂交换技术是指系统根据需要把主存中暂时不运行的某个时不运行的某个( (或某些或某些) )作业部分或全作业部分或全部移到外存，而把外存中的某个部移到外存，而把外存中的某个( (或某或某些些) )作业移到相应的主存，并使其投入作业移到相应的主存，并使其投入运行运行用辅存作为交换区，让多用户程序在较用辅存作为交换区，让多用户程序在较小的存储空间中通过不断地

26、换入小的存储空间中通过不断地换入/ /换出换出而得到运行。而得到运行。交换的时机交换的时机作业的进程用完时间片或等待输入输出作业的进程用完时间片或等待输入输出作业要求扩充存贮而得不到满足时作业要求扩充存贮而得不到满足时交换技术的关键交换技术的关键设法减少每次交换的信息量。为此，常设法减少每次交换的信息量。为此，常将作业的副本保留在外存，每次换出时，将作业的副本保留在外存，每次换出时，仅换出那些修改过的信息即可仅换出那些修改过的信息即可交换主要是在作业或进程之间进行，而交换主要是在作业或进程之间进行，而覆盖则可以在同一个或不同作业间进行覆盖则可以在同一个或不同作业间进行交换打破了一个程序一旦进入

27、主存便一交换打破了一个程序一旦进入主存便一直运行到结束的限制直运行到结束的限制离散分配方式的分类离散分配方式的分类分页存储管理分页存储管理分段存储管理分段存储管理段页式存储管理段页式存储管理分页存储管理方式分页存储管理方式在分区存储管理中，要求作业放在一个在分区存储管理中，要求作业放在一个连续的存储区域，因而会产生碎片连续的存储区域，因而会产生碎片要解决碎片问题，系统就要花费很高的要解决碎片问题，系统就要花费很高的代价去拼接它们代价去拼接它们页式存储管理的引入，是为了页式存储管理的引入，是为了解决碎片解决碎片问题问题实现原理实现原理 将一个进程的逻辑地址空间分成将一个进程的逻辑地址空间分成若干

28、个大小相等的若干个大小相等的页页，同时把内存空，同时把内存空间以与页相等的大小划分为大小相等间以与页相等的大小划分为大小相等的内存块（物理块），这些内存块为的内存块（物理块），这些内存块为系统中的任何进程所共享。在为进程系统中的任何进程所共享。在为进程分配内存时，以块为单位将进程中的分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页接的物理块中。由于进程的最后一页经常装不满一块而形成了不可利用的经常装不满一块而形成了不可利用的碎片，称之为碎片，称之为“页内碎片页内碎片”。 页面和物理块页面和物理块页面：进程的逻辑地址

29、空间分成若干个页面：进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各大小相等的片，称为页面或页，并为各页加以编号，从页加以编号，从0 0开始开始物理块：内存空间被分成与页面相同大物理块：内存空间被分成与页面相同大小的若干个存储块，称为物理块或内存小的若干个存储块，称为物理块或内存块，块， 也同样为它们加以编号，如也同样为它们加以编号，如0 0块、块、1 1块等等块等等页面大小页面大小 在分页系统中的页面其大小应适中。页在分页系统中的页面其大小应适中。页面若太小，一方面虽然可使内存碎片减小，面若太小，一方面虽然可使内存碎片减小，从而减少了内存碎片的总空间，从而减少了内存碎片的总空间

30、， 有利于提高有利于提高内存利用率，但另一方面也会使每个进程占内存利用率，但另一方面也会使每个进程占用较多的页面，从而导致进程的页表过长，用较多的页面，从而导致进程的页表过长，占用大量内存；占用大量内存； 此外，还会降低页面换进换此外，还会降低页面换进换出的效率。然而，如果选择的页面较大，虽出的效率。然而，如果选择的页面较大，虽然可以减少页表的长度，提高页面换进换出然可以减少页表的长度，提高页面换进换出的速度，但却又会使页内碎片增大。因此，的速度，但却又会使页内碎片增大。因此，页面的大小应选择得适中，且页面大小应是页面的大小应选择得适中，且页面大小应是2 2的幂，通常为的幂，通常为512 b8

31、 kb512 b8 kb。 页面地址结构页面地址结构分页地址结构如下：分页地址结构如下：页页 号号 p位移量位移量w3112110 对某特定机器，其地址结构是一定的。对某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为若给定一个逻辑地址空间中的地址为a a，页，页面的大小为面的大小为l l，则页号，则页号p p和页内地址和页内地址d d可按下可按下式求得：式求得： modladlaintp页表的结构页表的结构页号页号用户程序用户程序0 0页页1 1页页2 2页页3 3页页4 4页页5 5页页n n页页0 02 21 13 32 26 63 38 84 45 59 90 01 12

32、 23 34 45 56 67 78 89 91010块号块号内存内存页表页表地址变换机构地址变换机构页表寄存器页表寄存器页表始址页表始址页表长度页表长度页号页号页内地址页内地址1 10 0b b页表页表1 1逻辑地址逻辑地址l l页号页号块号块号2 23 3物理地址物理地址越界中断越界中断地址变换举例地址变换举例页表寄存器页表寄存器5005007 70 0100100页表页表逻辑地址逻辑地址l l每页大小每页大小10241024内存地址：内存地址：5 51024+100=52201024+100=52200 01 12 23 34 45 56 65 57 79 915151313101016

33、16500500500+0=500500+0=5005 5100100快表和联想寄存器快表和联想寄存器为了提高存取速度，可在地址变换机构为了提高存取速度，可在地址变换机构中增设一个具有并行查找能力的高速缓中增设一个具有并行查找能力的高速缓冲寄存器组，又叫冲寄存器组，又叫联想存储器联想存储器，用来存，用来存放页表的一部分（放页表的一部分（快表快表）。）。联想存贮器的存取速度比主存高，但造联想存贮器的存取速度比主存高，但造价也高，只能少量采用。整个系统通常价也高，只能少量采用。整个系统通常只要用只要用8 81616个寄存器就可使程序执行个寄存器就可使程序执行速度大大提高。速度大大提高。快表的结构快

34、表的结构页号页号块号块号访问位访问位状态位状态位访问位：指示该页最近是否被访问过。访问位：指示该页最近是否被访问过。0 0表表示没有被访问，示没有被访问，1 1表示访问过；表示访问过；状态位：指示该寄存器是否被占用。状态位：指示该寄存器是否被占用。0 0表示表示空闲，空闲，1 1表示占用。表示占用。具有快表的地址变换机构具有快表的地址变换机构页表寄存器页表寄存器页表始址页表始址页表长度页表长度页号页号页内地址页内地址b b页表页表逻辑地址逻辑地址l l页号页号块号块号物理地址物理地址越界中断越界中断页号页号 块号块号b b输入寄存器输入寄存器b bd d分段存储管理方式的引入分段存储管理方式的

35、引入方便编程方便编程分段共享分段共享分段保护分段保护动态链接动态链接动态增长动态增长分段的原理分段的原理每个作业的地址空间按照程序自身的逻每个作业的地址空间按照程序自身的逻辑关系划分成若干段，每个段都有自己辑关系划分成若干段，每个段都有自己的段名的段名每个段的地址空间都是从每个段的地址空间都是从“0”0”开始编开始编址的一维地址空间址的一维地址空间作业的地址空间是二维地址空间作业的地址空间是二维地址空间每一个逻辑地址均由两部分组成：段号每一个逻辑地址均由两部分组成：段号和段内地址和段内地址段号段号段内地址段内地址段表段表作业空间(main) 0030k(x) 1020k(d) 2015k(s)

36、 3010k30k20k15k10k40k80k120k150k段长 基址段号(main) 030k(x) 120k(d) 215k(s) 310k040k80k120k150k段表内存空间0123分段系统的地址转换过程分段系统的地址转换过程控制寄存器段表始址段表长度2100段号s越界1 k段长600段号01236 k4 k5002008 k9200基址位移量w82928k82928692主存物理地址有效地址分页和分段的主要区别分页和分段的主要区别页是信息的物理单位，段则是信息的页是信息的物理单位，段则是信息的逻辑单位；逻辑单位；页的大小固定且由系统硬件决定，段页的大小固定且由系统硬件决定，段

37、的长度则不固定，大小取决于用户所的长度则不固定，大小取决于用户所编写的程序；编写的程序；分页的作业地址空间是一维的，而分分页的作业地址空间是一维的，而分段的作业地址空间是二维的。段的作业地址空间是二维的。分段系统的共享示意图分段系统的共享示意图在分段系统中，为实现共享，只需为文本编辑程在分段系统中，为实现共享，只需为文本编辑程序设置一个段表项，如下图：序设置一个段表项，如下图：进程进程1进程进程2段表段表段长段长基址基址editoreditordata 1data 2editordata 1data 21608016080804040240380240280380420可重入代码可重入代码 可

38、重入代码，又称纯代码，是一可重入代码，又称纯代码，是一种允许多个进程同时访问的代码。为种允许多个进程同时访问的代码。为使各个进程执行的代码完全相同，绝使各个进程执行的代码完全相同，绝不允许可重入代码在执行中有任何改不允许可重入代码在执行中有任何改变。变。段页式存储管理原理段页式存储管理原理 段页式系统的基本原理是分段和段页式系统的基本原理是分段和分页原理的组合，即先将用户程序分分页原理的组合，即先将用户程序分为若干个段，把每个段分成若干个页，为若干个段，把每个段分成若干个页，并为每个段赋予一个段名。并为每个段赋予一个段名。作业地址空间和地址结构作业地址空间和地址结构主程序段主程序段子程序段子程

39、序段数据段数据段段号段号段内页号段内页号页内地址页内地址04k8k12k15k16k04k8k8k4k010k12k利用段表和页表实现地址映射利用段表和页表实现地址映射段号 状态 页表大小页表始址0111213041页号 状态 存储块#0111213041操作系统主存页表段表段表大小段表始址段表寄存器地址变换机构地址变换机构段表寄存器段表始址段表长度段号s页号p段超长段表0123页内地址页表0123b块号 b块内地址页表始址页表长度存储管理遇到的两种情况存储管理遇到的两种情况作业很大，要求的内存空间超过了内存作业很大，要求的内存空间超过了内存总量，致使作业无法运行总量，致使作业无法运行大量作业

40、要运行，内存容量不足以容纳大量作业要运行，内存容量不足以容纳所有作业，这时只能将少数作业装入内所有作业，这时只能将少数作业装入内存，其他大量作业留在外存上存，其他大量作业留在外存上局部性原理局部性原理 在一段时间，进程集中在一组子在一段时间，进程集中在一组子程序或循环中执行，导致所有的存储程序或循环中执行，导致所有的存储器访问局限于进程地址空间的一个固器访问局限于进程地址空间的一个固定子集（进程的工作集）。定子集（进程的工作集）。虚拟存储器的定义虚拟存储器的定义 虚拟存储器是指具有请求调入虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内功能和置换功能，能从逻辑上对内存容量加以扩充的一种

41、存储器系统。存容量加以扩充的一种存储器系统。虚拟存储器的逻辑容量由内存和外虚拟存储器的逻辑容量由内存和外存之和来确定，其运行速度接近于存之和来确定，其运行速度接近于内存速度，而每位的成本接近于外内存速度，而每位的成本接近于外存。存。引入虚拟存储器的好处引入虚拟存储器的好处运行大程序运行大程序大的用户空间大的用户空间并发并发易于开发易于开发虚拟存储器的特征虚拟存储器的特征离散性离散性多次性多次性对换性对换性虚拟性虚拟性虚拟存储器的实现方式虚拟存储器的实现方式分页请求系统分页请求系统请求分段系统请求分段系统实现请求分页实现请求分页( (段段) )的硬件支持的硬件支持请求分页请求分页( (段段) )

42、的页的页( (段段) ) 表机制表机制缺页缺页( (段段) )中断机构中断机构地址变换机构地址变换机构虚拟存储器的定义虚拟存储器的定义 请求分页存储管理方式是建立请求分页存储管理方式是建立在纯分页基础上的，是目前常用的在纯分页基础上的，是目前常用的一种实现虚拟存储器的方式。由于一种实现虚拟存储器的方式。由于它换进换出的基本单位是固定长度它换进换出的基本单位是固定长度的页面，所以请求分页管理方式实的页面，所以请求分页管理方式实现起来相对容易。现起来相对容易。页表机制页表机制 在请求分页系统中需要的主要数据结构仍然在请求分页系统中需要的主要数据结构仍然是页表。其基本作用是将用户地址空间的逻辑地是页

43、表。其基本作用是将用户地址空间的逻辑地址转换为内存空间的物理地址。址转换为内存空间的物理地址。页号页号 物理块号物理块号 状态位状态位p 访问字段访问字段a 修改位修改位m 外存地址外存地址实现请求分页实现请求分页( (段段) )的硬件支持的硬件支持 在请求分页系统中，每当要访问的在请求分页系统中，每当要访问的页面不在内存时，要产生一个缺页中断。页面不在内存时，要产生一个缺页中断。它是一种特殊的中断，主要表现在：它是一种特殊的中断，主要表现在： 在指令执行期间产生和处理中断信号在指令执行期间产生和处理中断信号 一条指令在执行期间，可产生多次缺页一条指令在执行期间，可产生多次缺页中断中断请求分页

44、系统地址变换机构请求分页系统地址变换机构缺页中断处理保留 cpu 现场从外存中找到缺页内存满否？选择一页换出该页被修改否？将该页写回外存os 命令 cpu 从外存读缺页启动 i/o 硬件将一页从外存换入内存修改页表否是是否页表项在快表中？cpu 检索快表访问页表否页在内存？修改访问位和修改位形成物理地址地址变换结束否页号页表长度?开始程序请求访问一页产生缺页中断请求调页修改快表是越界中断是是页面分配的三个问题页面分配的三个问题保证进程正常运行所需的最少物理块数保证进程正常运行所需的最少物理块数的确定的确定分配的物理块数是固定的还是可变的分配的物理块数是固定的还是可变的分配的物理块数是采取平均分

45、配算法还分配的物理块数是采取平均分配算法还是根据进程大小按比例予以分配是根据进程大小按比例予以分配页面分配和置换策略页面分配和置换策略固定分配局部置换固定分配局部置换可变分配全局置换可变分配全局置换可变分配局部置换可变分配局部置换页面分配算法页面分配算法平均分配算法平均分配算法按比例分配算法按比例分配算法考虑优先权的分配算法考虑优先权的分配算法按比例分配算法按比例分配算法若系统中有若系统中有n个进程，每个进程的页面数为个进程，每个进程的页面数为si，则，则系统中的页面数总和为：系统中的页面数总和为：又设系统中可用的物理块总数为又设系统中可用的物理块总数为m，则每个进程，则每个进程能分到的物理块

46、数为能分到的物理块数为bi，则有：，则有：按比例分配算法按比例分配算法 在实际应用中，为了照顾重要的、紧迫的作在实际应用中，为了照顾重要的、紧迫的作业能尽快地完成，应为它分配较多的内存空间。业能尽快地完成，应为它分配较多的内存空间。通常采用的方法就是把内存可供分配的物理块分通常采用的方法就是把内存可供分配的物理块分为两部分：一部分按比例分配给各进程；另一部为两部分：一部分按比例分配给各进程；另一部分则根据各进程的优先权，分配给各进程。分则根据各进程的优先权，分配给各进程。何时调入页面何时调入页面 为了确定系统将进程运行时所缺的为了确定系统将进程运行时所缺的页面调入内存的时机，可采取两种策略：页

47、面调入内存的时机，可采取两种策略： 预调页策略预调页策略 请求调页策略请求调页策略何处调入页面何处调入页面 在请求分页系统中，把外存分为在请求分页系统中，把外存分为两部分：一部分是文件区，用于存放两部分：一部分是文件区，用于存放文件；另一部分是对换区，用于存放文件；另一部分是对换区，用于存放对换页面。对换页面。页面置换算法页面置换算法 通常，把选择换出的页面的算法称为页面置通常，把选择换出的页面的算法称为页面置换算法换算法(page-replacement algorithms)。置换。置换算法的好坏将直接影响系统的性能，不适当的算算法的好坏将直接影响系统的性能，不适当的算法可能导致进程发生法

48、可能导致进程发生“抖动抖动”。 一个好的页面置换算法，应具有较低的页面一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访更换频率。从理论上讲，应将那些以后不再会访问的页面换出，或把那些在较长时间内不会再被问的页面换出，或把那些在较长时间内不会再被访问的页面调出。访问的页面调出。最佳置换算法最佳置换算法 最佳置换算法是由最佳置换算法是由beladybelady于于19661966年提出的一种理论上的算法。其选择年提出的一种理论上的算法。其选择的页面，将是永不使用的，或者是在的页面，将是永不使用的，或者是在最长时间内不再被访问的页面。最长时间内不再被访问的页面。 对于

49、固定分配页面方式，采用最对于固定分配页面方式，采用最佳置换算法可保证获得最低的缺页率。佳置换算法可保证获得最低的缺页率。最佳页面置换算法举例最佳页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：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

50、 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最佳页面置换算法举例最佳页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定

51、系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：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

52、 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最佳页面置换算法举

53、例最佳页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：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最佳页面置换算法举例最佳页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，

54、并考虑有以下的页面号引用串：虑有以下的页面号引用串：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

55、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最佳页面置换算法举例最佳页面置换算法举例 假定系

56、统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：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最佳页面置换算法举例最佳页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑

57、有以下的页面号引用串：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

58、0 1 017先进先出页面置换算法先进先出页面置换算法 该算法总是淘汰最先进入内存的该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久页面，即选择在内存中驻留时间最久的页面予以淘汰。的页面予以淘汰。 该算法实现简单，将进入内存的该算法实现简单，将进入内存的进程按照先后次序链接成一个队列，进程按照先后次序链接成一个队列，设置一个替换指针，使它总是指向最设置一个替换指针，使它总是指向最老的页面。老的页面。先进先出页面置换算法举例先进先出页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：7 0 1

59、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 先进先出页面置换算

60、法举例先进先出页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：虑有以下的页面号引用串：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先进先出页面置换算法举例先进先出页面置换算法举例 假定系统为某进程分配了三个物理块，并考假定系统