操作系统第四章课件

第四章

存储器管理第一节存储器的层次结构第二节

程序的装入和链接第三节

连续分配存储管理方式第四节对换（Swapping）第五节

基本分页存储管理方式第六节

基本分段存储管理方式第四章

存储器管理第一节存储器的层次结构序言存储器：主存（内存）、副存（外存）内存－进程、外存－文件内存管理：地址映射、内存分配与回收存储保护、内存扩充(虚拟内存)外存管理：文件管理序言存储器：主存（内存）、副存（外存）存储器的层次结构计算机对存储器的要求：1.要求存储器的访问速度能跟上处理机的运行速度。2.要求存储器具有非常大的容量。3.要求存储器的价格便宜。基于以上三个要求，目前计算机系统都采用了多层结构的存储器系统。存储器的层次结构计算机对存储器的要求：多层结构存储器系统1.存储器的多层结构通用计算机的存储器具有3层结构：由低到高分别为：辅存、主存、CPU寄存器。高档计算机的存储器结构分为：寄存器、高速缓存、主存储器、磁盘缓存、固定磁盘、可移动存储介质等6层。存储器的特点：层次越高，存储介质的访问速度越快，价格越高，容量越小。存储器管理系统负责管理内存，外存作为文件管理内容。2.可执行存储器指寄存器和主存储器特点：对可执行存储器访问速度快，对辅存的访问需要通过I/O设备，因此耗费的时间远高于可执行存储器，一般至少相差3个数量级。多层结构存储器系统主存储器与寄存器主存储器_内存用于保存进程运行时的程序和数据，又称为可执行存储器。CPU一般从主存中取出指令和数据分别存放于CPU中的指令寄存器和数据寄存器中，反之将寄存器数据存入主存中。主存早期容量为数10到数百KB，现在高达数10MB到数GB。但主存访问速度低，故引入了寄存器和高速缓存。寄存器寄存器的访问速度最快，与处理器运行速度相当，但价格非常昂贵，容量也很小。随着VLSI的发展，现在的微机系统中，寄存器数量已达到数10个到数百个。主存储器与寄存器主存储器_内存高速缓存和磁盘缓存1.高速缓存是现代计算机结构中的一个重要部件，介于寄存器和主存之间，用于备份主存中较常用的数据，以减少处理机对主存的访问次数，从而大幅提高程序执行速度。其容量远大于寄存器，从几10KB到几MB，其访问速度快于主存。特点：由于高速缓存的速度越高，价格越贵，故计算机系统会设置两个或多个高级缓存，一级缓存紧靠内存，速度最快，容量最小。2.磁盘缓存由于主存的访问速度远高于磁盘的访问速度，为了缓和两者间速度差异，设置了磁盘缓存，用于暂时存放频繁使用的一部分磁盘数据和信息，以减少访问磁盘的次数。特点：与高速缓存不同，磁盘缓存不是一种实际存在的存储器，而是利用主存中的一部分存储空间暂时存放磁盘信息。一个文件数据可能会出现在不同层次的存储器中：辅存—主存（磁盘缓存）高速缓存和磁盘缓存1.高速缓存程序的装入和链接用户提交的程序需要经过以下几个步骤才能被系统运行：1.编译2.链接3.装入程序的装入和链接用户提交的程序需要经过以下几个步骤才能被系统从源程序到程序执行编译：编译程序由编译程序（Compiler）将用户源代码编译成若干个目标模块。链接：链接程序由链接程序（Linker）将编译后形成的一组目标模块，以及它们所需要的库函数链接在一起，形成装入模块。装入：装入程序由装入程序（Loader）将装入模块复制到内存中。库汇编编译主子1子2目标模块链接程序装入模块库主子1子2装入程序内存库主子1子2从源程序到程序执行编译：编译程序库汇编主子1子2目标模块链接程序的装入就是把链接好的装入模块装入“内存”。装入方式绝对装入：只适用单道程序环境；装入内存的位置是可知的、固定的，故采用绝对装入方式，按照装入模块中的地址，将程序和数据装入内存，由于程序的逻辑地址与物理地址一致，故地址无需修改。程序中所使用的物理地址一般设置为在编译、汇编时再给出，此前由符号地址代替。可重定位装入（静态重定位）：适用于多道程序环境，存在很多的用户程序编译所形成的若干个目标模块，它们的起始地址都是从0开始的逻辑地址，可通过重定位方式装入内存合适的位置，但这会使装入模块的逻辑地址与实际装入内存后的物理地址不同，故需要对程序和数据的地址进行修改。动态运行时装入（动态重定位）：允许程序在运行时，在内存中移动位置。实际上，程序在内存中运行时，它在内存中的位置可能要经常改变。例如：在对换功能系统中，一个进程可能被多次换出，又多次换入。动态运行时装入程序：把装入模块装入内存后，并不立即把模块中的逻辑地址转换为物理地址，而是把这种地址转换推迟到程序真正要执行时才进行。程序的装入就是把链接好的装入模块装入“内存”。重定位的概念重定位概念：把程序装入内存时，修改程序中所有与地址有关的项。逻辑地址变换为物理地址。重定位的类型静态重定位：程序执行前，一次性，链接装入程序。动态重定位：处理机每次访问主存时，有动态地址变换机构（硬件）自动执行。

作业地址空间内存空间装入365LOAD1,2500500025001000365LOAD1,250015000125001000011000365LOAD1,1250015000125001000011000重定位的概念重定位装入365LOAD1,2500365LO链接方式静态链接：程序在运行之前，先将目标模块及其所需库函数链接成一个完整的装配模块，以后不再拆开。这种事先进行链接的方式即为静态链接方式。（1）对相对地址进行修改，将目标模块的相对地址修改为相应的装入模块相对地址；（2）变换外部的调用符号，将每个模块中所用的外部调用符号也都变换为装入模块中的相对地址。链接方式静态链接：程序在运行之前，先将目标模块及其所需库函数程序的链接链接：把一个程序相关的一组目标模块和系统调用模块（库函数）链接形成一个整体——装入模块的过程。具体工作：对相对地址的修改；变换外部调用符号。模块ACallB;Return;0L-1模块BCallC;Return;0M-1模块C……;Return;0N-1链接模块AJSR‘L’;Return;0L-1模块BJSR‘L+M’;Return;LL+M-1模块C……;Return;L+ML+M+N-1装入模块目标模块使用的都是相对地址，其起始地址都为0，每个模块中的地址都是相对于起始地址计算的。长度程序的链接链接：模块A0模块B0模块C0链接模块A0模块BL链接方式装入时动态链接：在将目标模块装入内存时，边装入边链接的链接方式，即在装入一个目标模块时，若发生一个外部模块调用事件，将引起装入程序去找出相应的外部目标模块，并将它装入内存，同时修改目标模块中的相对地址。优点：（1）便于修改和更新，由于各目标模块是分开存放的，所以要修改或更新各目标模块就很容易。（2）便于实现对目标模块的共享，在采用静态链接方式时，每个应用模块都必须含有其目标模块的拷贝，无法实现对目标模块的共享，但采用装入时动态链接的方式时，OS就很容易将一个目标模块链接到几个应用模块上，实现多个应用程序对该模块的共享。链接方式装入时动态链接：在将目标模块装入内存时，边装入边链接链接方式运行时动态链接：将对某些模块的链接推迟到程序执行时才进行。亦即，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块，并将之装入内存，将其链接到调用者模块上。优点：凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅能加快程序的装入过程，而且可节省大量的内存空间。链接方式运行时动态链接：将对某些模块的链接推迟到程序执行时才连续分配存储管理方式连续分配方式：为用户程序分配一个连续的内存空间，即程序中代码的逻辑地址相邻体现在内存空间分配时，物理地址的相邻。曾被广泛应用，且现在仍被采用。单一连续分配固定分区分配动态分区分配动态可重定位分区分配连续分配存储管理方式连续分配方式：为用户程序分配一个连续的内单一连续分配单一连续分配的基本思想把内存分为系统区和用户区，系统区供OS使用，通常放在内存的低址部分；系统区以外的全部内存空间是用户区，仅装有一道用户程序。单一连续分配的特点只能用于单用户、单任务的单道程序环境的OS中。软件简单，硬件要求低（可无需存储器保护措施）实例CP/M，MS-DOS，RT-11等单用户OSMS-DOS内存分区CP/M内存分配系统参数区BIOSCCPBDOS系统区系统区单一连续分配单一连续分配的基本思想系统参数区BIOSCCP固定分区分配在多道程序环境中，为了防止装入内存中的多个程序间互相干扰，于是将整个内存用户空间划分为若干个固定大小的区域，将每个分区中只装入一道作业，即为固定分区分配。1.划分分区的方法（划分为若干个固定大小的分区）分区大小相等：缺乏灵活性：当程序太小会造成内存空间浪费，当程序太大又无法满足其运行。比较适用于一台计算机同时控制多个相同对象的场合。分区大小不相等：较上种方法灵活，通常将内存划分为多个较小的分区、适量中等分区、少量大分区。2.内存分区分配分区使用表（MBT）：分区号、大小、分区起址、状态分区按内存空间大小排队当用户程序要装入时，由内存分配程序检索分区使用表，找到满足要求、尚未分配的分区，将之分配给它。固定分区分配在多道程序环境中，为了防止装入内存中的多个程序间固定分区分配区号/键大小起址状态18K512K正使用232K520K正使用332K552K未使用4128K584K未使用5512K712K正使用…………系统区分区1分区4分区5分区2分区3系统区作业3分区4作业2作业1分区3分区使用表固定分区分配区号/键大小起址状态18K512K正使用232动态分区分配可变分区分配思想分区的位置和大小都不固定，应作业的要求而设置，为之动态分配内存空间。动态分区分配的数据结构的两种形式：空闲分区表（用于记录每个空闲分区）、空闲分区链：用于实现对空闲分区的分配和链接，在每个分区的头部、尾部分别设置了前向、后向指针，形成了双向链表。分区号始址大小状态12012k空闲24032k空闲310064k空闲4220128k空闲前向后向指针指针N+2N+200分区大小分区状态动态分区分配可变分区分配思想分区号始址大小状态12012k空分区分配流程图分配内存分区大小与所需空间大小“匹配”：M.Size-U.Size≦Size（不再分割的小分区的尺寸）剩余部分挂接到空闲分区链（表）上。查找空闲分区链表第一项检索完否？m.size>u.size?m.size-u.size≦size?划出u.size大小的分区修改有关的数据结构返回将该分区从链表中移出继续检索下一个表项YYYNNN空闲状态分区分区分配流程图分配内存查找空闲分区链表第一项检索完否？m.s动态分区分配算法首次适应算法FF要求：空闲分区链以地址递增的次序链接每次从链首开始顺序查找第一个大小能满足要求的空闲分区，然后划分，余下的空闲分区仍留在空闲链中优先利用地址部分，保留高址部分的大空闲区碎片较多，每次从低址查找要增加查找的开销

为了将一个新作业装入内存中，须按照一定的分配算法，从空闲分区表中选出一分区给该作业，接下来将介绍四种传统的顺序式搜索算法：循环首次适应算法：对首次适应算法的演变，从上次找到的下一个空闲分区开始找要求：设置一个起始查找指针采用循环查找方式内存中的空闲分区分布更均匀减少了查找空闲分区始的开销缺乏大的空闲分区最佳适应算法要求：将所有的空闲分区按其容量从小到大的顺序形成一空闲分区链从链首开始查找第一个大小适合的空闲分区第一次找得的是最佳即最恰好适合的分区能够避免“大材小用”同时，空闲分区每次分配切割留下的剩余部分总是最小的，留下大量的难以利用的碎片回收操作较困难最坏适应算法要求：将所有的空闲分区按其容量从大到小的顺序形成一空闲分区链每次分配链首的第一个空闲分区每次利用是最大的分区，空闲分区每次分配切割留下的剩余部分总是最大的，避免留下大量的难以利用的碎片查询开销非常小但缺乏大空闲分区动态分区分配算法首次适应算法FF为了将一个新作业装动态分区分配算法分配算法比较几种算法各有利弊，到底哪种最好不能一概而论，而应针对具体作业序列来分析。对于某一作业序列来说，某种算法能将该作业序列中所有作业安置完毕，那么我们说该算法对这一作业序列是合适的。对于某一算法而言，如它不能立即满足某一要求，而其它算法却可以满足此要求，则这一算法对该作业序列是不合适的。动态分区分配算法分配算法比较例：有作业序列：作业A要求20K；作业B要求28K，作业C要求30K。要求画出系统中空闲区按照首次适应算法，最佳适应算法、最坏适应算法形成的三种空闲分区队列，然后分析哪种算法对该序列是合适的？经分析可知：最佳适应法对这个作业序列是合适的，而其它两种对该作业序列是不合适的。例：有作业序列：作业A要求20K；作业B要求28K，作业C要练习有作业序列：作业A要求21K；作业B要求25K，作业C要求30K，那种分配算法适合该作业序列？练习动态分区分配算法基于索引搜索的动态分区分配算法由于顺序搜索的动态分区分配算法比较适用于较小的系统。当系统很大时，为了提高搜索空闲分区的速度，采用基于索引搜索的动态分区分配算法：1.快速适应算法2.伙伴系统3.哈希算法动态分区分配算法基于索引搜索的动态分区分配算法快速适应算法又称为分类搜索算法，是将空闲分区根据容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，同时在内存中设立一张管理索引表，其中的每一个索引表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头指针。该算法搜索空闲分区步骤：1.根据进程的长度，从索引表中找到能容纳它的最小空闲区链表2.从链表中取下第一块进行分配即可。该算法不会对分区产生分割，因此不会产生碎片，查找效率高。缺点：为进程所分配的分区或多或少存在内存空间的浪费。快速适应算法又称为分类搜索算法，是将空闲分区根据容量大小进行伙伴系统该算法规定，无论已分配分区或空闲分区，其大小均为2的k次幂，通常整个可分配内存的大小为2的m次方。将它不断的划分，按照分区的大小进行分类，将相同大小的所有空闲分区，单独设立一个空闲分区双向链表，形成k个空闲分区链表。算法步骤：当需要为进程分配长度为n的存储空间：1.首先计算一个i值，使2i-1<n<=2i。2.然后若找到2i大小的空闲分区链表，则分配，否则将查找2i+1链表，若找到则把该分区分为两个相等的分区，这两个分区称为一对伙伴，其中一个分区用于分配，而把另一个分区加入大小为2i的空闲分区链表中，以此类推2的i+2空闲分区链表的分配。伙伴系统该算法规定，无论已分配分区或空闲分区，其大小均为2的哈希算法在上述分类搜索算法和伙伴系统算法中，都是将空闲分区根据分区大小进行分类，对于每一类具有相同大小的空闲分区，单独设立一个空闲分区链表。在为进程分配空间时，需要在一张管理索引表中查找所需空间大小所对应的表项，来找到一个空闲分区。这里面临一个问题，如果空闲分区分类较细，则相应的索引表项较多，那么会显著增加搜索索引表的表项的时间开销。为了解决这个问题，提出了哈希算法。哈希算法在上述分类搜索算法和伙伴系统算法中，都是将空闲分区根哈希算法哈希算法：利用哈希快速查找的优点，以及空闲分区在可利用空闲区表中的分布规律，建立哈希函数，构造一张以空闲分区大小为关键字的哈希表，该表的每个表项记录了一个对应的空闲分区链表表头指针。当进行空闲分区分配时，根据所需空闲分区大小，通过哈希函数计算，即得到在哈希表中的位置，从中得到相应的空闲分区链表，实现最佳分配策略。哈希算法哈希算法：利用哈希快速查找的优点，以及空闲分区在可利分区分配操作回收内存回收区与插入点的前一个空闲分区相邻接回收区与插入点的后一个空闲分区相邻接；回收区与插入点的前后两个空闲分区相邻接；回收区不与任何一个空闲分区相邻接；回收区F1……回收区F2……回收区F1F2……分区分配操作回收内存回收区F1……回收区F2……回收区F1F可重定位分区分配动态重定位的引入随着系统接收的作业的增加，内存中连续的大块分区不复存在，产生了大量的“碎片”。新的作业无法装入到每个“碎片”小分区上运行，但所有碎片的空间总和可能大于需求。通过“拼接”/“紧凑”/“紧缩”/“”澄清“来实现——”程序的浮动“/”

动态重定位“。OS区Job2Job4Job3Job1Job5Job6Job7“零头”碎片OS区Job2Job4Job3Job1Job5Job6Job7OS区Job2Job4Job3Job1Job5Job6Job7“零头”碎片紧凑可重定位分区分配动态重定位的引入OS区Job4Job3Job可重定位分区分配动态重定位的实现由于动态运行时装入方式是将相对地址转换为绝对地址的工作推迟到程序指令要真正执行时进行，为使地址转换不影响到指令的执行速度，需要有硬件地址变换机构的支持，即需在系统中增设一个重定位寄存器，用它来存放程序在内存中的起始地址。程序运行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。动态重定位：地址变换过程是在程序执行期间，随着每条指令或数据的访问自动进行的，故称为。处理机一侧存储器一侧作业J

内存365LOAD1,2500500025001000365LOAD1,2500150001250010000110002500相对地址10000重定位寄存器可重定位分区分配动态重定位的实现365LOAD1,2500优缺点分析优点：消除了“碎片”，提高了内存利用率，同时提高了系统效率。缺点：需要动态重定位“硬件”机构支持，增加了系统成本，并轻度降低了程序执行速度，“紧凑”处理增加了系统开销。可重定位分区分配算法动态重定位分区分配算法流程查找空闲分区链表找到可用分区？按动态分区方式进行分配修改有关的数据结构返回分区号及首址进行紧凑形成连续空闲区YYNN请求分配u.size分区空闲分区总和≥？修改有关的数据结构无法分配返回可重定位分区分配算法查找空闲分区链表找到可用分区？按动态分区对换（Swapping）早期，在单用户分时系统中出现的对换技术为：系统把所有的用户作业存放在磁盘上，每次只能调入一个作业进入内存，当该作业的一个时间片用完时，将它调至外存的后备队列上等待，再从后备队列上将另一个作业调入内存。多道环境下存在的问题：1.内存中大量的进程因事件未发生而被阻塞，但却占用了大量的内存空间。2.又存在许多的作业因内存空间的不足，一直驻留在外存上，而不能进入内存运行。这些都使得系统的吞吐量下降，造成了系统资源的浪费，为了解决这个问题，在系统中添加了对换设施。对换（Swapping）早期，在单用户分时系统中出现的对换技对换技术对换技术（Swapping）:用于解决内存不足的问题，改善内存利用率，提高系统吞吐量。指把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空间再把已具备运行条件的进程或进程所需要的程序和数据调入内存。对换的类型_根据每次对换时，所对换的程序或数据的数量，可将对换分为如下两类：如果对换是以整个进程为单位，便称之为“整体对换”或“进程对换”，广泛用于多道程序中，作为处理机中级调度。如果对换是以进程的一个“页面”或“分段”为单位进行的，则分别称之为“页面对换”或“分段对换”，又称为“部分对换”。这种对换方法是实现后面将介绍的请求分页和请求分段式存储管理的基础，其目的是为支持虚拟存储系统。对换技术对换技术（Swapping）:用于解决内存不足的问题进程对换技术进程对换技术（Swapping）对换的时机：创建新进程而内存不足时。对换空间的管理：外存分为文件区和对换区，前者存放文件，采用离散分配；后者存放换出的进程，采用连续分配，以提高进程换入、换出的对换速度。对换区空闲盘块管理中的数据结构：记录外存中对换区的空闲盘块的使用情况，使用空闲分区表－－包括对换区的首址及其大小分别用盘块号和盘块数表示。对换空间的分配与回收对换分区的分配：连续分配方式，因而对换空间的分配与回收与动态分区分配雷同。其分配算法可以是首次适应算法、循环首次适应算法、最佳适应算法。对换区的回收可分为：1.回收分区与插入点的前一个空闲分区F1相邻接；2.回收分区与插入点的后一个空闲分区F2相邻接；3.回收分区同时与插入点的前、后两个分区邻接；4.回收分区既不与F1邻接，又不与F2邻接。进程对换技术进程对换技术（Swapping）进程对换技术（Swapping）当一进程由于创建子进程而需要更多的内存空间，但又无足够的内存空间时，便调用对换进程。进程的换出：系统首先选择处于阻塞状态且优先级最低的进程作为换出进程，申请对换空间，然后启动磁盘，将该进程的程序和数据传送到磁盘的对换区上，并回收该进程占用的内存空间，修改该进程的PCB。进程的换入：找出“就绪”状态但已换出的进程，将其中换出时间最久的进程作为换入进程，将之换入，直至无可换入的进程或无可换出的进程或无足够内存换入进程为止，此时对换进程才停止。进程对换技术（Swapping）第五节

基本分页存储管理方式

由于采用连续分配方式会形成很多的碎片，虽然可以使用紧凑方法改善但开销太大，于是促使人们产生了分散分配方式的思想（如果将一个进程直接分散地装入到许多不相邻接的分区中，便可充分地利用内存空间）。根据离散分配时，所分配地址空间的单位不同，可将离散分配分为三种：1.分页存储管理方式。

2.分段存储管理方式。3.段页式存储管理方式。页面与页表地址变换机构两级和多级页表基本分页的特点第五节

基本分页存储管理方式由于采用连续页面与页表页面页面：分页存储管理将进程的逻辑地址分成若干个页并且按照顺序编号。物理块：相应把内存的物理地址空间分为若干个块加以编号。页面大小：选择适当的页面大小—一般为2n

范围：1KB~8KB分散分配方法：将程序划分成多个页并且分别装入到多个可以不相邻接的物理块中。分页地址的地址结构（对特定机器固定）

逻辑地址

物理地址页内地址：0-11，即页面大小为4K,页号P：12-31,即地址空间1M个页若给定一个逻辑地址空间中的地址为A,页面大小为L,则页号和页内地址？页表数据结构：页号、块号、存取控制项页表的作用：实现从页号到物理块号的地址映射。页号P位移量W物理块号P页内地址d页面与页表页面页号P位移量W物理块号P页内地址d页面与页表页面页面和物理块（页框/架）：顺序编号，页内碎片页面大小：2nBytes一般在：512B~8/32K地址结构

逻辑地址

物理地址页表数据结构：页号、块号、存取控制项页表的作用：实现从页号到物理块号的地址映射。页号P位移量W物理块号P页内地址d01234567891110内存第0页第1页第2页第3页第4页第5页第6页用户作业块号页号1051169453327120页表01234567891110内存第0页第1页第2页第3页第4页第5页第6页用户作业02K-1第2页（页长2K）02K-14号页架（页长2K）第0页第1页第2页第3页第4页第5页第6页第0页第1页第2页第3页第4页第5页第6页逻辑地址空间页面与页表页面页号P位移量W物理块号P页内地址d012345地址变换机构为了将用户地址空间中的逻辑地址转换为内存空间中的物理地址，在系统中必须设置地址变换机构。将逻辑地址中的页号转变为内存中的物理块号，需借助于页表。基本的地址变换机构页表存放在内存系统区的一个连续空间中；PCB和页表寄存器PTR中存有页表的首地址；查询页表：页表首地址+页号x表项长度；地址映射——从逻辑地址到物理地址的变换过程。具有快表的地址变换机构联想寄存器——并行查询；空间大小：几K到几百K，部分表项（16~512个）；快表与页表同时访问；地址映射过程。页表始址页表长度页表寄存器﹥页表块号页号5332712052018物理地址32018逻辑地址越界中断页表始址页表长度页表寄存器﹥页表块号页号5332712031250物理地址21250逻辑地址越界中断快表块号页号2051145320输入寄存器分析：

统计表明，从快表中找到所需页表项的机率达90％以上。同时，考虑到快表的速度是内存速度的数倍或数十倍，那么相对于内存速度，访问页表的时间可以忽略不计。也就是说页地址变换机构造成的速度损失达到了可接受的程度。地址变换机构为了将用户地址空间中的逻辑地址转换为内存空间中的例：设页长为1K，程序地址字长为16位，用户程序空间和页表如图。

硬件能自动分离出页号和页内地址，但我们只能通过计算才能得到。例：设页长为1K，程序地址字长为16位，用户程序空间和页表如两级和多级页表两级页表解决大页表占用大的连续存储空间的问题；将大页表进行分页，让每个页面大小与内存物理块大小相同（1024）然后按照离散分配的方式存放在不同的物理块中。此时也要再建立一个外层页表用于记录页表页面的物理块号。若地址空间为32位，页面大小为4K，一级页表有1MB的页表项，二级页表：外1KB页表，1KB项逻辑地址结构：

外层页号（P1）+外层页内地址(P2)+页内地址(d)多级页表外部页表块号页号321078110110页表分页11223120211130……01231121131011……外部页表外部页表寄存器物理地址外部页号P1外部页内地址P2逻辑地址页内地址d…………页表两级和多级页表两级页表外部页表块号页号32107811011基本分页的特点优点：存在页内碎片，但碎片相对较小，内存利用率较高；实现了离散分配，消除了程序浮动；便于存储访问控制，有利于代码共享。“可重入代码”——纯代码：执行中不可改变。缺点：需要专门的硬件支持，尤其“快表”；内存访问的效率下降。不足：不能实现真正的共享，不支持动态链接。基本分页的特点优点：第六节

基本分段存储管理方式基本分段管理思想的引入基本原理地址变换分段与分页的主要区别信息共享段页式存储管理方式第六节

基本分段存储管理方式基本分段管理思想的引入分段存储管理思想的引入OS由单道向多道系统发展的同时，其存储管理方式便由单一连续分配发展到固定分区分配。为了能适应不同大小的用户程序要求，又从固定分区分配发展到动态分区分配。又为了提高内存的利用率，又从连续分配方式发展到离散分配方式——分页存储管理方式。为了满足用户在编程和使用上多方面的要求，又引入了分段存储管理方式，是当今所有存储管理方式的基础。分段存储管理思想的引入OS由单道向多道系统发展的同时，其存储分段存储管理思想的引入具体地说，分段存储管理方式符合用户和程序员如下多方面的需要：方便编程：用户将作业按逻辑分段，其中每个逻辑地址都是由段名（段号）和段内偏移量（段内地址）共同来决定，这不仅可以方便用户编程，也可以使程序非常直观：LOAD1，[A]|〈D〉；STORE1，[B]|〈C〉；将分段A中D单元内的值读入寄存器1。将寄存器1中的值存入B分段的C单元中。分段存储管理思想的引入具体地说，分段存储管理方式符合用户和程分段存储管理思想的引入信息共享：是以信息的逻辑单位（main函数、子函数、数据等逻辑关系）为基础，来实现对程序和数据的共享。信息保护：同样以信息的逻辑单位为基础，根据逻辑有效和方便地实现信息保护功能；例如我们希望子函数A仅允许进程执行，不允许读写操作，只需在该段上标上只执行标志即可。但是在分页系统中，函数A可能要占几个页面，其中第一页和最后一页还会装有其他程序段的数据，这些数据又允许进程读写，这就很难实现对页面统一保护。分段存储管理思想的引入信息共享：是以信息的逻辑单位（main分段存储管理思想的引入动态增长：分段存储管理方法能很好的应对数据段的动态增长。动态链接：针对目标模块运行时动态链接：系统只将真正要运行的目标程序装入内存，首先将主程序和需要用到的目标程序装入内存。这些目标程序和目标模块都是以逻辑段为单位的，所以分段存储管理方式非常适合动态链接。分段存储管理思想的引入动态增长：分段存储管理方法能很好的应对分段系统的基本原理在分段存储管理方式中，作业的地址空间被划分为若干个段，每段定义了一组逻辑信息，每段都是从0开始编址，并采用一个连续的地址空间。段的长度由相应的逻辑信息组的长度决定，因此各段长度不相等。分段系统中逻辑地址结构：二维地址（段号，段内地址）

3116150允许一个作业由64K个段，一个段的最大长度为64KB段表（段映射表）段号、段基地址（段在内存中的起址）、段长等段表寄存器：段表始址和段表长度利用段表实现逻辑段地址到物理地址的映射段号段内地址分段系统的基本原理在分段存储管理方式中，作业的地址空间被划分基本原理内存第0段第1段第2段第3段用户作业段表基址段长150K35K500K9K300K20K100K42K3210段号第0段第1段第2段第3段图.利用段表实现地址映射基本原理内存第0段第1段第2段第3段用户作业段表基址段长15地址变换及变换机构基本分段管理的地址变换与基本分页管理的变换机构和过程类似。段表寄存器存放段表的起始地址和段表长度；越界访问控制逻辑地址的段号与段表长度比较；段内地址与段表中保存的段长比较；段表始址段表长度段表寄存器﹥153705物理地址段号3105逻辑地址越界中断段表基址段长150K35K500K9K300K20K100K42K3210段号内存地址变换及变换机构基本分段管理的地址变换段表始址段表长度段表分段与分页的主要区别页是信息的物理单位，段是信息的逻辑单位，分页是系统管理的需要，分段是用户的需要；页的大小固定，由系统确定；段的大小动态变化，决定于用户编程的需要；分页系统中的逻辑地址空间是一维的，分段系统中的是二维的。分页系统中不易实现“共享”和“动态链接”，分段则很容易。分段与分页的主要区别页是信息的物理单位，段是信息的逻辑单位，信息共享假设一个多用户系统，可同时接纳40个用户，每个用户都执行一个文本编辑程序。如果编辑程序包括160KB编辑代码区，40KB数据区，则需要约8MB内存空间，若160KB是可重入的，则该代码能被共享，故就只需（160+40*40）KB内存空间。在分页系统中，假定页面为4KB，则编辑代码段划分为40个页面，对应40个页表项，数据区划分为10个页面，对应10个页表项。1.分页系统中对程序和数据的共享信息共享假设一个多用户系统，可同时接纳40个用户，每个用户都信息共享内存段表基址段长180K100K300K20K100K42K210段号第0段Job1数据用户1编辑进程……第0段Job2数据用户2编辑进程……基址段长380K30K300K20K100K42K210段号第0段Job1数据……Job2数据2.分段系统中程序和数据的共享使实现共享变得非常容易信息共享内存段表基址段长180K100K300K20K100基本分段的特点优点：便于动态申请内存管理和使用统一化便于共享便于动态链接缺点：产生碎片思考：与动态分区存储管理方案的相同点与不同点？基本分段的特点优点：段号S段内页号P页内地址W段页式存储管理方式基本思想结合分页和分段技术；发挥出分页和分段管理方式各自的优点。原理对内存进行分页（物理块/页架）；对用户作业先分段，各段再分页。地址结构与地址变换段号、段内页号、页内地址三部分段表和页表主程序段数据段子程序段段号S段内页号P页内地址W段页式存储管理方式基本思想主程序段段表始址段表长度段表寄存器逻辑地址页号P页内地址段号S﹥段表块号块内地址物理地址越界中断页表xxxx2xxxx1xxxx0页表始址段号210页表始址段号……段表始址段表长度段表13021110页表始址页表长度状态段号段表寄存器页表03121110存储块号状态页号页表1110存储块号状态页号段号，段内页号，页内地址段表始址段表长度段表寄存器逻辑地址页号P页内地址段号S﹥段表段页式存储管理的特点段页式存储管理的优缺点同时具备分段和分页管理的优点：分散存储，内存利用率较高；便于代码或数据共享，支持动态链接等。访问效率下降：一次访问转换成了三次访问。1.访问内存中的段表，从中取得页表始址。2.访问内存中的页表，从中取出物理块号并与页内地址一起构成数据的物理地址。3.根据物理地址从内存中取出数据。通过在地址变换机构中增设一个高速缓冲寄存器来解决速度问题。段页式存储管理的特点段页式存储管理的优缺点第五章

虚拟存储器_页面置换算法虚拟存储器的引入虚拟存储器的定义物理上不存在，但可以使用（访问）；允许作业部分装入，需要时再临时装入所需的部分，直到作业退出，某些部分也有可能没被装入过。虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。第五章

虚拟存储器_页面置换算法虚拟存储器的引入虚拟存储器的特征离散性：离散存储多次性一个作业被分成多次调入内存运行；对换性允许在作业的运行过程中进行换进、换出；虚拟性能从逻辑上扩充内存容量，使用户“看到”的内存容量远大于实际大小。该特征是以上两个特征为基础的。虚拟存储器的特征离散性：离散存储内存分配策略和分配算法具体的物理块（页架）的分配策略固定分配局部置换：进程占据的内存页架数不变；缺页时，只能与该进程在内存的页面置换；由进程类型、程序员或程序管理员确定每个进程分得的物理块数但分配时，难于确定某个进程的页架数。可变分配全局置换：最易实现，空闲页架由OS管理－空闲物理块队列先为每个进程分配一定的物理块缺页时，由系统从空闲物理块队列中取一块当空闲物理块完时，便与内存中的一页置换，该页可能是任一进程中的页可变分配局部置换根据进程类型或程序员的要求，为每个进程先分配一定数目的物理块缺页时，只与该进程在内存的一页置换当进程缺页率较高或较低时，能由OS对其占据的页架数加以调整内存分配策略和分配算法具体的物理块（页架）的分配策略可变分配内存分配策略和分配算法物理块的分配算法平均分配算法将系统中所有可供分配的页架，平均分配给各个进程。按比例分配算法根据进程的大小按比例分配页架的算法。考虑优先权的分配算法优先权高的一次分得的页架数多。内存分配策略和分配算法物理块的分配算法调页策略何时调入页面的问题预调页策略：通常运用于首次调入内存时预先调入若干个预计在不久后将执行的页面预测不准：约为50％请求调页策略：进程运行中发生缺页现象时每次仅调入一页，系统开销大，增加了磁盘I/O的启动频率从何处调入页面的问题外存分为：“文件区”和“对换区”系统有足够的对换空间：进程的所有文件都从文件区复制到对换区系统缺少足够对换空间：不被修改的文件始终直接从文件区调入；可能被修改的部分在换出时须调到对换区，以后需要时均从对换区调入UNIX方式：第一次运行到的页面都从文件区调入，被换出的页面放在对换区，下次调入就从对换区调入，对于已在内存的共享页面无须调入页面的调入过程响应缺页中断→保存CPU环境→查找页表（快表）→得到该页在外存中的块号→启动磁盘IO读入；如果内存已满，先置换，再调入；最后修改页表（快表）对应项的内容。调页策略何时调入页面的问题从何处调入页面的问题页面的调入过程第七节

页面置换算法最佳置换算法先进先出FIFO算法最近最久未使用（LRU）置换算法最少使用（LFU）置换算法页面缓冲置换算法第七节

页面置换算法最佳置换算法页面置换算法在进程运行过程中，若其所要访问的页面不在内存，但内存已无空闲空间时，为保证该进程能正常运行，系统必须从内存中调出一页程序或数据送到磁盘的对换区中。但应将哪个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法。一个好的页面置换算法应具有较低的页面更换频率。页面置换算法在进程运行过程中，若其所要访问的页面不在内存，但最佳置换（OPT）算法选择以后永远（相比之下，最长时间）不会被使用的页淘汰出去。特点：理论上，性能最佳；实际上，无法实现；通常只用在研究其它算法时，做参考评价。最佳置换（OPT）算法选择以后永远（相比之下，最长时间）不会例假定系统未某进程分配了三个物理块号，有以下的页面号引用串（为了简便起见，假设采用的是最佳置换算法策略）70120304230321201701777220000113缺页中断9次，置换6次例假定系统未某进程分配了三个物理块号，有以下的页面号引用串（先进先出FIFO选择最先进入系统的页淘汰出去特点：实现简单与进程实际的运行不相适应先进先出FIFO选择最先进入系统的页淘汰出去例假定系统未某进程分配了三个物理块号，有以下的页面号引用串（为了简便起见，假设采用的是FIFO先进先出置换策略）页的位置不表示页的真实存储地址，仅为了表示即将淘汰页的方便70120304230321201701701223701127001缺页15次，置换12次例假定系统未某进程分配了三个物理块号，有以下的页面号引用串（最近最久未使用（LRU）置换算法选择最近最久未被使用（访问）的页淘汰出去。特点：性能较好，实现复杂，需要硬件支持（每页配置一个寄存器、栈），增加系统负担。最近最久未使用（LRU）置换算法选择最近最久未被使用（访问）LRU的硬件支持寄存器系统为每页设置一个移位寄存器R，每当访问这一页时，将该页对应的寄存器R最高位置1，以后每个时间间隔将所有的R右移一位，当淘汰一页时就选择R值最小的页。也就是说R值越小，其对应的页就是最久未使用的页。显然，R的位数越多越精确。但系统硬件成本也就越高。栈设置一个特殊的栈保存当前使用的各个页面的页面号；当一个页面被访问时，首先检查栈中是否有与刚压入栈顶的页号相同的，若有，则从栈中抽出；最后就将它的页号压入栈顶。这样可保证栈中无相同的页号。当系统要淘汰一页时，总是从栈底取出一个页号淘汰，即淘汰的页是最久未使用的。LRU的硬件支持寄存器栈例假定系统为某进程分配了三个物理块号，有以下的页面号引用串（为了简便起见，假设采用的是最近最久未使用LRU策略）70120304230321201701701237010702

栈缺页12次，置换9次例假定系统为某进程分配了三个物理块号，有以下的页面号引用串（例某程序在内存中分配三个块，访问页的走向为4，3，2，1，4，3，5，4，3，2，1，5，按FIFO、LRU、OPT算法分别计算缺页次数，置换次数？假设开始时所有页均不在内存例某程序在内存中分配三个块，访问页的走向为4，3，2，1，4FIFO4，3，2，1，4，3，5，4，3，2，1，5432143555211432143335224321444355缺页9次，置换6次FIFO4，3，2，1，4，3，5，4，3，2，LRU4，3，2，1，4，3，5，4，3，2，1，5432143543215432143543214321435432缺页10次，置换7次LRU4，3，2，1，4，3，5，4，3，2，1OPT4，3，2，1，4，3，5，4，3，2，1，5444444444222333333333112111555555缺页7次，置换4次OPT4，3，2，1，4，3，5，4，3，2，1练习

某程序在内存中分配4个块，访问页的顺序为4，3，2，1，4，3，5，4，3，2，1，5，按LRU、OPT算法分别计算缺页次数，置换次数？假设开始时所有页均不在内存练习 某程序在内存中分配4个块，访问页的顺序为4，3，2，1LRU4，3，2，1，4，3，5，4，3，2，1，5432143543215432143543214321435432432111543缺页中断8次LRU4，3，2，1，4，3，5，4，3，2，1，54321OPT4，3，2，1，4，3，5，4，3，2，1，5444444444411333333333332222222222111555555缺页中断6次OPT4，3，2，1，4，3，5，4，3，2，1，54444FIFO置换算法的异常

有一虚拟存储系统，采用先进先出的页面淘汰算法。在内存中为每个进程分配3块。进程执行时使用页号的顺序为432143543215(1)

该进程运行时总共出现几次缺页。(2)

若每个进程在内存有4块，又将产生几次缺页。FIFO置换算法的异常 有一虚拟存储系统，采用先进先出的页面M=34，3，2，1，4，3，5，4，3，2，1，5432143555211432143335224321444355缺页9次，置换6次M=34，3，2，1，4，3，5，4，3，2，1M=44，3，2，1，4，3，5，4，3，2，1，5432111543215432221543214333215432444321543缺页10次，置换6次FIFO页面淘汰算法会产生异常现象（Belady现象），即：当分配给进程的物理页面数增加时，缺页次数反而增加M=44，3，2，1，4，3，5，4，3，2，1，54321影响缺页次数的因素分配给进程的物理块数页面的大小编程方法页面置换算法影响缺页次数的因素分配给进程的物理块数例内存分配一物理块，初始时矩阵数据均不在内存；页面大小为128个整数；矩阵A128X128按行存放。下面两个程序执行时访问数据将分别会产生多少次缺页中断？程序1：forj:=1to128fori:=1to128A[i,j]:=0;程序2：fo