操作系统设计与实现(第四章).ppt

《操作系统设计与实现(第四章).ppt》由会员分享，可在线阅读，更多相关《操作系统设计与实现(第四章).ppt（104页珍藏版）》请在三一办公上搜索。

1、操作系统设计与实现,第四章 存储器管理,一、存储器在操作系统中的地位是计算机不可缺少的部分，存在的方式也多种多样。对于操作者、程序设计者、系统开发者都希望能拥有无穷大的、高速的、内容不发生变化的存储器（不易丢失），最根本的还是能以很低的成本来使用。,由于技术的原因，我们无法满足我们的需求，因此，大部分的计算机都以一种层次结构来进行存储器的管理。,高速、价格昂贵、易失信息的Cache一般单位几百KB；中速、中等价格、易变化的RAM，一般单位为几百M；低速、低廉价格、不易丢失信息的磁盘，一般单位为G；,存储器层次结构,对于操作系统，它本身提供一个存储管理模块来管理它本身的这个层次性的存储器系统。M

2、emory manager,由操作系统协调这些存储器的使用重要性：直接存取要求内存速度尽量快到与CPU取指速度相匹配，大到能装下当前运行的程序与数据，否则CPU执行速度就会受到内存速度和容量的影响而得不到充分发挥。,内存：是由存储单元（字节或字）组成的一维连续的地址空间，简称内存空间。用来存放当前正在运行程序的代码及数据，是程序中指令本身地址所指的、亦即程序计数器所指的存储器。,可以分为：系统区：用于存放操作系统 用户区：用于装入并存放用户程序和数据。,操作系统存储管理目的-用户对内存的使用要求,1、充分利用内存，为多道程序并发执行提供存储基础；2、尽可能方便用户使用：自动装入用户程序；用户程

3、序中不必考虑硬件细节；3、系统能够解决程序空间比实际内存空间大的问题；4、程序在执行时可以动态伸缩；5、内存存取速度快；6、存储保护与安全；7、共享与通信；8、了解有关资源的使用状况；9、实现的性能和代价。,操作系统存储管理的任务前提:引入多道程序设计技术，满足用户要求,1.内存空间的管理、分配与回收,记录内存的使用情况 设置相应的内存分配表（见下页）（内存分配回收的依据）内存空间划分问题？静态或动态，等长或不等长,内存分配表 位示图表示法：用一位（bit）表示一个空闲页面（0：空闲，1：占用）；,空闲页面表：包括首页面号和页面个数，连续若干的页面作为一组登记在表中 空闲块表：空闲块首址和空闲

4、块长度，没有记录的区域即为进程所占用；空闲块链表：将所有的空闲块链成一个链表。,确定分配算法 实施内存分配 回收内存 分配回收方式:静态分配与动态分配,连续性；离散性 驻留性；交换性 一次性；多次性,2.存储共享,内存共享：两个或多个进程共用内存中相同区域 目的：节省内存空间，提高内存利用率 实现进程通信（数据共享）共享内容：代码共享，要求代码为纯代码 数据共享,3.存储保护与安全,保护目的：为多个程序共享内存提供保障,使在内存中的各道程序,只能访问它自己的区域，避免各道程序间相互干拢，特别是当一道程序发生错误时,不致于影响其他程序的运行。通常由硬件完成保护功能，由软件辅助实现。（特权指令不能

5、完成存储保护。）,存储保护,保护系统程序区不被用户侵犯;（有意或无意的）不允许用户程序读写不属于自己地址空间的数据;（系统区地址空间，其他用户程序的地址空间）,保护过程-防止地址越界,每个进程都有自己独立的进程空间，如果一个进程在运行时所产生的地址在其地址空间之外，则发生地址越界。即当程序要访问某个内存单元时，由硬件检查是否允许，如果允许则执行，否则产生地址越界中断，由操作系统进行相应处理。,一般由硬件提供一对寄存器：基址寄存器：存放起始地址 限长寄存器：存放长度（上界寄存器/下界寄存器）,保护过程-防止操作越权,对于允许多个进程共享的存储区域，每个进程都有自己的访问权限。如果一个进程对共享区

6、域的访问违反了权限规定，则发生操作越权。即读写保护。,4.内存“扩充”,通过虚拟存储技术实现 用户在编制程序时，不应该受内存容量限制，所以要采用一定技术来扩充内存的容量，使用户得到比实际内存容量大的多的内存空间。,内存“扩充”,具体实现是在硬件支持下，软硬件相互协作，将内存和外存结合起来统一使用。通过这种方法把内存扩充，使用户在编制程序时不受内存限制。,5.地址映射（地址重定位，地址变换）,逻辑地址（相对地址，虚地址）物理地址（绝对地址，实地址）地址映射,(1)逻辑地址（相对地址，虚地址）,用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式，其首地址为0，其余指令中的地址都

7、相对于首地址而编址。不能用逻辑地址在内存中读取信息。,(2)物理地址（绝对地址，实地址）内存中存储单元的地址，可直接寻址。,(3)地址映射,为了保证CPU执行指令时可正确访问存储单元，需将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址，这一过程称为地址映射。,*重定位和保护,多道程序导致了分区的产生，而分区也导致了新的问题，即程序的重新定位和保护。如果多个作业都是为某一个程序服务，当主程序调用这些作业的时候，就需要定位到这些作业，保证程序的运行（主函数和分别编译好的子函数）。这时，链接的时候，链接器按照我们的分区机制来定位程序。定位和保护的常见方法：,原因:当程序装入内存时,操作系统

8、要为该程序分配一个合适的内存空间，由于程序的逻辑地址与分配到内存物理地址不一致,而CPU执行指令时，是按物理地址进行的，所以要进行地址转换。,静态重定位,当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后不再转换（一般在装入内存时由软件完成）。,动态重定位,在程序运行过程中要访问数据时再进行地址变换（即在逐条指令执行时完成地址映射。一般为了提高效率，此工作由硬件地址映射机制来完成。硬件支持，软硬件结合完成）。硬件上需要一对寄存器的支持。,4.1 基本的内存管理,在运行时进程可以在内存和磁盘之间进行移动（交换和分页技术）的系统；运行时进程不能够移动的系统，较为简单。交换和分页技术的

9、目的是由于没有足够的主存来同时容纳所有的进程而被引入。随着硬件的发展，现有的良好的管理方案也会可能变成过时的技术而被淘汰。,4.1.1无交换和分页的单道程序,此方案是指同一个时刻和操作系统共享存储器。,对于A图，操作系统位于主存最底部的RAM，即随机存取存储器中，用户程序位于主存的上部。对于B图，操作系统位于主存最高端的只读存储器里（ROM）,（其实本身属于一种映像区域，映像了主板上的基本的输入输出系统）。对于C图，设备的驱动程序位于内存最高端的ROM中，操作系统的其余部分位于低端的RAM中，中间是用户的应用程序。如MS-DOS系统。对于IBM操作系统，系统位于ROM中的部分即为BIOS。,对

10、于这种方式，不管是哪一个图，操作系统每次把需要的程序从磁盘复制到存储器里并执行，当程序结束时，系统提示结束，当有新的命令时，系统加载新的程序到存储器中，覆盖原来的程序，继续新的执行。可以满足早期一般的小型的操作系统的需求，但随着硬件性能的提高，这种方式逐渐被淘汰。,4.1.2 固定分区的多道程序,对于常见的系统，我们希望能够支持更多的程序，当某个程序处于等待I/O的时候，可以让CPU为别的程序服务，来提高系统整体的性能。因此可以用划分分区的方法来同时加载多个程序，可以把主存分为几个大小不同的分区，根据程序的不同，来把他们加载到不同的分区中。而同时，程序也可按照单个输入队列的方式进行输入，也可以

11、按照多个输入队列的方式进行输入。,对于左图，由于作业的大小类似的时候，而且众多的作业大小都类似，而此时分区的大小固定，我们该选择合适大小的分区来运行这个作业，这样的话，类似的作业就被分到了一起，而那些与作业的大小不一致的分区，就必然会出现空闲状态，那些分到一起的进程却不得不等待，等待要分到内存空间。忙得忙，闲的闲。如分区一和分区三。,对于右图，所有的作业都被放入一个队列，每次当有分区被释放的时候，就从等待队列中寻找，最适合这个分区大小的进程，这样做是为了避免把大的分区分给那小的作业，免得资源被浪费，但这样却常常把小的作业推到了后面；但对于操作系统，我们做普通的要求就是简单的操作能被最快的反馈给

12、我们，即小的作业能够被最快的处理，因此，为了总能够满足用户的这个要求，一般要专门保证总有一个小的分区，专门来处理那些小的事件、作业，免得被大的作业抢去分区。或者通过加权来判断作业被推后的次数，到了一定的程度，就不再跳过而是立即执行。,4.2 交换,固定分区的方案在批处理系统中是种简单高效的方案，每一个作业都在队列中一直到被分配到某个分区，然后被执行完毕。只要能够放入内存，能够使CPU 繁忙，就能满足要求。,但在分时系统中，或者个人的PC中，这种方案就不太实际，会常常由于主存不够，需要把进程保存到磁盘，同样的，也需要常常动态地把进程从磁盘调入内存。这时就需要有新的技术，即交换技术(swappin

13、g)和虚拟内存技术的引入。,进程依次进入，并获得到自己所需要的内存空间，当某个进程执行完毕后便离开，它原来的占用的内存资源便得到释放，当新的进程到来的时候，又可以从这个被释放的空间中划分新的空间，因此主存的利用变得很高效。（理想上的）,g,上图中的内存分配与固定分区的不同，它是一种可变分区的内存分配，这时内存中的分区的数目和大小都是在随时随着进程的变化而变化的。实际上，内存空间在不断划分的时候，本身的分布也在变化的越来越复杂，越来越不便于管理。迫切需要一个机制去整理这个零碎的空间。即空闲区域的合并-内存紧缩。(低效的操作，耗时),*新的问题,如果根据进程需要给它分配内存，而且，进程运行的时候大

14、小不再变化，那么分配就简单，根据需要的大小分配即可；如果进程运行时，该进程的数据段增长，就需要分配新的内存，那进程所需的空间就开始变大，上图中，如果相邻区域是空洞，则直接分配给它，但如果是进程时？交换，将某一进程移出，但此时内存满了，磁盘交换分区也满了，某进程则必须等待或杀死。,*新问题的解决带来的矛盾：,多数的进程都需要动态的空间，且申请新的内存空间，频繁的交换导致大量的进程等待和时间开销。,*矛盾的解决,在每个进程申请空间的时候分配一些多余的内存空间；（A）或者对于具有两个可增长数据部分的进程，采用在进程的分区内分开放置的方式管理。（B）,4.2.1 使用位图的内存管理,由于操作系统需要对

15、内存进行分配管理和回收，所以，它必须很好地对内存进行跟踪，常用的是位图法和自由链表：,(a),对于位图方法，位图的大小与内存的大小和分配的单位的大小相关，内存不变时，被分配的单个单元越小，则位图就越大。位图的组织结构简单，便于管理，且占用的内存很小但也有缺陷：定位的速度受限，由于每个位图单元代表一个被分配的单元，所以连续性不强，对于某个需要几个分配单元大小的进程就很难快速在位图中找到这样连续的空间。故实际不很常用。,4.2.2 使用链表的内存管理,这种方法是通过一个链表来管理已经分配的和尚未分配的内存段，通过对链表的维护达到对内存的管理。这里的内存段可以使被某个进程所占用，也可以是个空洞，即尚

16、未分配的区域。表的内容包括段的性质、开始地址、长度、长度和指向下一个表项的指针。这是一般，链表的组织都按照地址来排列，这样的进程切换会很直观，更有效的方法是采用双向链表来记录。但这时就需要对空洞进行处理。,对于某进程X结束的时候同邻居合并的四种方式,对于这种内存的组织和管理方法，我们需要讨论如何用合理的方法来为新创建的进程和新换进来的进程分配大小：*最简单的分配算法最先匹配算法（first fit）存储管理器沿内存段链表从头开始寻找足够的空间来装载进程，除非找到的这个区域的大小刚好和进程相同，否则就要把这个空间拆为两部分，一部分来装进程，另一部分依然为空。属于快速算法，搜索的开销很小。,*最先

17、匹配的变形下次匹配法（next fit）工作方式与首次适配相同，区别在于每次搜索完毕后记录当前的位置，下次搜索时从此处开始搜索。(缺点：较大的空闲分区不易保留）*最佳匹配算法（best fit）每次搜索整个链表中最适合该进程大小的内存空间，没有完全相同就寻找次之的；每次都要搜索整个链表故速度很慢，而且每次都可能拆分内存，而且生成的新的内存空间会很小。,*放弃最佳匹配算法采用最差匹配算法采用最差，即每次找最大的内存空间分给进程，这样就不会产生大量的极小的内存空洞，即被分开后剩余的那部分仍然足够大，可以继续被使用。对于这四种算法，都不是很有效的方法，如果把表示进程占用的内存段和表示空闲的内存段分开

18、放到两个链表中，这样检索效率会提高很多，但这样带来的新麻烦就是控制过程的复杂化和内存释放过程的延长，不得不把释放的内存从一个链表中清除再放到另一个中去。,*一些改进思路,*进程和空洞（空闲区）存放在两个链表中，针对最佳匹配算法的缺陷，将空洞的组织不按地址，而是按照大小来组织，这样就减小了搜索时的开销。*进程和空洞存放在两个链表中，用空洞本身来存放这个链表，第一个字存放空洞的大小，第二个字存放下一个空洞的地址。*快速匹配法，按照常见进程需要的空间大小设置单独的链表，这种算法就根据进程所需空间的大小快速在这些特殊的空洞链表中查找空内存。它需要将所有的空洞进行排序，即进程换出时的空洞合并判断。,4.

19、3 虚拟存储器,交换技术与覆盖技术是在多道环境下扩充内存的方法，用以解决在较小的存储空间中运行较大程序时遇到的矛盾。覆盖技术主要用在早期的操作系统中；交换技术被广泛用于小型分时系统中，交换技术的发展导致了虚存技术的出现。交换技术与覆盖技术共同点：进程的程序和数据主要放在外存，当前需要执行的部分放在内存，内外存之间进行信息交换。,覆盖：一个作业的若干程序段，或几个作业的某些部分共享某一个存储空间。把程序划分为若干个功能上相对独立的程序段，按照其自身的逻辑结构将那些不会同时执行的程序段共享同一块内存区域。程序段先保存在磁盘上，当有关程序段的前一部分执行结束，把后续程序段调入内存，覆盖前面的程序段（

20、内存“扩大”了）。一般要求作业各模块之间有明确的调用结构，程序员要向系统指明覆盖结构，然后又由操作系统完成自动覆盖。,缺点：对用户不透明，增加了用户负担。例子：目前这一技术用于小型系统中的系统程序的内存管理上，MS-DOS的启动过程中，多次使用覆盖技术；启动之后，用户程序区TPA的高端部分与COMMAND.COM暂驻模块也是一种覆盖结构。,虚拟存储器的基本思想是：程序、数据、堆栈的大小可以超过内存的大小，操作系统把程序当前使用的部分保留在内存，而把其它部分保存在磁盘上，并在需要时在内存和磁盘之间动态交换。虚拟存储器支持多道程序设计技术。,虚存：把内存与外存有机的结合起来使用，从而得到一个容量很

21、大的“内存”，这就是虚存。实现思想：当进程运行时，先将一部分程序装入内存，另一部分暂时留在外存，当要执行的指令不在内存时，由系统自动完成将它们从外存调入内存工作。,4.3.1 分页（虚拟页式存储管理）,在虚拟存储器系统中，内存管理单元负责地址的计算和重新定位。它是一组或一个芯片，完成地址映射的功能。,一方面，把物理内存划分为许多个固定大小的内存块，称为物理页面，或者是页框（page frame）另一方面，把虚拟地址空间也划分为大小相同的块，称为虚拟页面，或者简称为页面（page），页面的大小要求是2的整数次幂。,*隐含的问题：程序不知道实际的存储器的大小，由于页和页框的大小一样，则必然有些程序

22、中的地址是没有经过映射的，即虚拟存储器中有空页，他没有和实际的物理内存对应起来。虚页是否被对应了都专门有一位来存储这个信息。如：MOV REG,32780这时会发现在虚页8里没有对应的物理地址，这时MMU就无法处理此时的问题。这时的故障就叫做缺页故障。操作系统需要找到一个页框将其内容移到磁盘，把刚才需要引用的页取到这个页框中，并修改映射，然后重新启动刚才的指令。,MMU的内部结构及工作方法,110,在/不在内存,页表,虚地址8196,物理地址24580,4.3.2 页表（page table）,页表是用来索引页面的，通过判断页表的存在位，判断这个虚页在物理内存中是否有对应的页框，如果有，就直接

23、通过页表函数获得实际的物理地址定位物理内存，如果没有，就通知操作系统，引发中断，寻找空页框来装入这个虚页。,对于16位指令系统的一种方案,地址映射在实际应用中的问题：现代计算机的虚地址一般最少都32位，如果按照页面4K来处理，则对此系统来说，就是有 的页面大小，同时又有 个页表记录。而64位系统的更为庞大.即问题主要是页表的庞大导致了索引不再高效；另外，从虚地址到物理地址的映射的频繁执行，现有的庞大页表无法完成快速的查找定位.地址映射相应变慢。,问题的解决：一、利用硬件配合解决-CPU端 将页表装入寄存器中，避免进程运行时访问内存，对页表的检查也直观。但这样当页表大的时候，就要很多硬件寄存器来

24、存放，代价昂贵。每次进程切换时候都要装入内存中的页表，开销也会很大。二、另一种极端，全放入内存 这时的硬件开销就很小，只需要指向页表起始地址的寄存器即可。环境切换时，改变这个寄存器里的东西即可。但缺点是执行每条指令时都要一次或多次访问内存。故很少单纯使用。,*多级页表,为了不将庞大的页表全放内存，引入了多级页表技术：对于此例：32位虚地址分为了10位的PT1域，10位的PT2域，每个页的大小是12位。每一个进程都拥有自己的页表，即每个进程都可以拥有4G的虚存空间。当一个虚地址定位的时候，具体过程如下：,物理内存,当用户的页不在主存中，就会发生缺页故障，由操作系统完成换页的工作。,*页表分析,页

25、框号（物理页面号）：具体对应的物理内存的位置在/不在位（有效位）：表示是否会发生缺页保护位：表示此页所允许的操作（是只读、可读写、可执行）修改位：表示此页被修改的情况（上一次的操作）-dirty bit引用位：此页被访问的情况，页面替换算法的重要依据禁用缓存：特殊使用，保证数据的及时更新,4.3.3 TLB-关联存储器（转换后援存储器）,用硬件手段来解决庞大页表的问题。由于页表使用的不均匀性，小部分页表被大量频繁的使用，另一些则很少被使用，故专门用硬件TLB(Translation Lookaside Buffer)来存放常用的页号，并不停的保持TLB中页号的更新。工作时，当有虚地址需要转换时

26、，先到TLB中去作判断，如果不在TLB中，就去页表中查询，并在获得后更新TLB中的页号数据，淘汰一个条目，将其信息写回内存中的页表项，把新的条目加入；如果虚页号在TLB中，则判断保护情况，合法就直接取出使用，不用查询页表，不合法时，就出现保护故障。,用于加快页表查找的TLB,*软件TLB管理,现代很多大型操作系统的缺页故障不再由MMU处理，而是交给TLB，而TLB也是由操作系统装入的，因此，TLB的缺页故障比MMU的高得多，但通过设置TLB的大小，可以很有效提高页面的命中率，而此时MMU的设计就可以简化很多，从而使CPU可以更好地设计自己所需的其他部件。并且操作系统可以根据进程的性质，自动预装

27、进程可能需要的页面，这样，就使进程的缺页率大大减少。,4.3.4 反置页表（逆向页表）,对于64位计算机，如果页面大小仍然4K，此时页表项就变得更加庞大，不可能去管理好，故用了逆向的思路来处理：根据内存中的物理页面号来组织页表，用物理页面号来作为访问页表的索引，有多少个物理页面，就在页表中设置多少个页表项。这样，可节省大量的物理空间。弱点是虚地址到实际物理地址转换很困难，不能根据虚地址查物理地址，必须搜索整个页表，才能找到它所对应的物理页面号。,4.4 页面替换算法,页的置换算法：当发生缺页，而主存中已无空闲页架时，需选一页淘汰。选取淘汰页的方法叫页的置换算法。抖动：刚被淘汰出去的页，不久又被

28、访问，又需把它调入而将另一页淘汰出去，很可能又把刚调入的或很快要用的页淘汰出去了。如此反复更换页面，以至系统大部分机时花在页面的调度和传输上，系统的实际效率很低。这种现象称为“抖动”。缺页率：f=(缺页次数/访问页面总数)%常见的页面置换算法：最佳置换算法 OPT；先进先出置换算法FIFO；最近最少使用置换算法LRU；最近未使用置换算法NUR；工作集.,4.4.1 最佳置换算法 OPT（Optimum Strategy）,基本原则：淘汰在将来再也不被访问，或者是在最远的将来才能被访问的页。特点：无法预测作业将用到哪些页！所以此算法是无法实现的理论上的算法。例：某进程分配物理页面数为3，其运行期

29、间页面访问序列：A,B,C,D,A,B,E,A,B,C,D,E，分析其按照OPT算法进行页面置换时的缺页情况。（堆栈式算法）,最佳置换算法OPT,4.4.2最近未使用置换算法（Not used Recently）NUR,页表扩充：为每个页面设置两个硬件位访问位和修改位。访问位=0：该页尚未被访问过R:读写时设置=1：该页已经被访问过修改位=0：该页尚未被修改过 M:修改时设置=1：该页已经被修改过,即对应的四类情况为：*第0类：未被访问，没有被修改*第1类：未被访问，已被修改-（由第3类产生)*第2类：已被访问，没有被修改*第3类：被访问，被修改,4.4.3 先进先出置换算法FIFO(firs

30、t-in,first-out),基本原则：选择最早进入主存的页面淘汰。理由：最早进入的页面其不再使用的可能性比最近调入的页面要大。实现简单：把进入主存的各页面按进入主存的时间次序构成队列（链表或表格），总是淘汰队头的页面。缺点：只有按照线性顺序访问地址空间时才是理想的，否则效率不高。异常现象：对于一些特定的访问序列，随分配页架数增加，缺页频率反而增加！,先进先出置换算法FIFO,4.4.4 第二次机会页面替换算法,由于FIFO会把经常使用的页面换掉，人们对它进行了改进：对页面的引用位进行检查，来判断这个页的使用情况，如果未被引用，则替换掉此页，如果不为0，表示此页被使用过，则清除R位，并放入队

31、列最后，将它当作新的页面来对待，从而保证了经常使用的页面能够被保持下来。该算法其实就是查找从上一次检查以来没有引用过的页面，如果都被引用了，它就成了FIFO算法。,当在时间到了 20的时候，此时发生了页面故障，需要淘汰一个老的页面，首先对A页面进行判断，如果A页面的引用位是0，则A就被淘汰出去，要么被直接丢弃，要么被写回硬盘。如果引用位是1，A页面将被放入队列的尾部，同时它的引用位将被清零。,4.4.5 时钟页面替换算法,由于第二次机会算法需要在链表中移动页面，导致了不必要的开销，故用时钟页面替换算法来提高效率。,原理同第二次机会算法一样，但只是实现方法不一样而已。,4.4.6 最久最少使用页

32、面替换算法(LRU),基本原则：选择最近一段时间内最长时间没有被访问过的页面淘汰。基本理由：认为过去一段时间里不曾被访问过的页，在最近的将来也可能不再会被访问。实现困难：需为每个页设置一个特定单元，记录上次访问后到现在的时间量 t，并选择 t 最大的页淘汰。无论硬件还是软件实现开销都很大！,LRU的硬件实现：矩阵方法实现页面K被使用，则将K行全置1，然后，将K列全置0，如果需要淘汰的时候按照行来判断。访问次序为：0 1 2 3 2 1 0 3 2 3,4.4.7 软件仿真的LRU算法,用计数器跟踪每个页面被访问的频繁程度，被访问一次就将计数器累加一次，当发生需要淘汰页面的情况的时候，将计数器值

33、最小的页面淘汰掉即可。即软件的NFU(not frequently used)算法。弊端：可能会删掉有用的页面，而不是不再使用的页面。改进方案：计数器累加前先右移一位，R位累加到计数器的前端而不是后端。,4.5 分页系统中的设计问题,如何从整体把握分页模块的设计，各个细节在模型中的重要性和设计需求.,4.5.1 工作集模型,请调策略：根据需求将需要的页面调入内存中的工作方式称为请调；访问局部性：进程对页面访问的局部性，而且对于所有进程都有此特性；工作集：一个进程当前使用的页的集合叫做此进程的工作集。,颠簸：进程执行过程当中，一个隔几个指令就发生一次页面故障的程序称为在颠簸。指令执行通常需几个纳

34、秒，读入页面一般需要几十毫秒。进程在换出内存然后又被调入，这样的过程使得系统的性能花费在页面的移动上，由于每次装入的请调策略，使得开始执行的时候程序颠簸很厉害，故利用工作集的方法来解决这个问题。在一个进程运行之前就预先装入它的页面（工作集，这种方法称为工作集模型，这种技术也称为预先调入（prepaging）。,4.5.2 局部与全局分配策略,一直讨论的是某一个进程发生缺页故障，而实际上内存中存在的是多个进程的页面，当其中某个进程发生缺页故障的时候，实际的替换应该有很多种方法，即涉及到了对某个进程的页面替换还是对整个内存中页面的替换的问题。对于某个进程发生了缺页故障，替换页面时只从此进程拥有的页

35、面中淘汰的方法叫做局部页面替换策略（其实对应的是在内存中为每个进程分配了固定的内存片断）；从内存中只关心页面的年龄来进行淘汰的方法叫做全局页面替换策略（其实对应于每个进程的页框数是可以变化的）。,Originalconfiguration,Local page replacement,Global page replacement,局部与全局的优劣性的比较：一般来说，全局比局部较优局部：当内存中有空页框的时候，仍然在自己固定的段内替换，会导致很高缺页率；工作集增大，颠簸变大，工作集变小，内存又会被浪费。全局：系统需要不断确定该给不同的进程多少页框，但是由于工作集变化的过快，跟踪年龄位也很难实现

36、。可以定期为当前进程平均分配同等页框，但进程的大小不同，这种分配仍不合理；也可按照进程大小来分配；或者为每个进程规定最小页框数，这样可保证每个进程都可以执行。,无论何种方案都是为了减少颠簸，因此需要将颠簸直接控制，可使用缺页率PFF算法（page fault frequency）：控制分配集的大小，什么时候应该增加，什么时候应该减少分配给进程的物理页面数。,A表示故障率过高，B表示故障率过低，过高表示页框太少，需要增加分配；过低表示页框过多，需要减少页框。,4.5.3 页面大小,页面大小的选择，会影响内存的利用率。内零头的产生：由于分页存储，且页面有大小，当一个页被写入了数据，就认为此页被使用

37、了，别的进程就不会再来用这个页面，因此，就产生了内碎片，且平均大小为 段数页面大小/2。,Eg：一个程序被分为八个部分执行，每部分需要4k的内存。页面大小为32k时，就分配了32k，16k时就分配了16k，4k时就分配了4k。页面过大，浪费即越大。过小的话，页表就变得庞大，装入时就使大量时间花在了寻道上，每次装入页面就耗费大量的时间。,4.6 分段,段式虚拟存储器，允许程序员把存储器看成多个地址空间或段组成，段的大小不等，且是动态变化的，通过分段就把原来一维的组织方式改变了，使得数据的组织更加具有逻辑性。例如，编译程序在编译过程中会建立许多表格：源文本、符号表等。,当各个部分在一维空间中增长的

38、时候，会进入到邻接块中，而且某一部分会增长迅速，填满自己的空间，而其他部分仍有大量空余空间。,这时在机器上提供多个相互独立的地址空间段，且段的长度会动态改变，这样就可以将上图改成下图的方式：,符号表,源正文,常量,语法树,调用栈,用户程序划分,按程序自身的逻辑关系划分为若干个程序段，每个程序段都有一个段名，且有一个段号。段号从0开始，每一段也从0开始编址，段内地址是连续的。,逻辑地址,段的特点：段的长度可以在运行期间进行改变，堆栈段的长度可以随着数据的压入进行增长，数据弹出时也同样减小。段是逻辑实体，并为程序员所知，段可以容纳一个过程或者一些数值变量，但每个段中的数据都相对单一。段是逻辑实体，

39、每部分的内容都相对单一，因此可以对不同的段进行不同的控制，如，某些段内容只许读，另一部分段内容只许执行等等。,段的特点：分段便于单独进行编译、链接，也同样便于修改，且重新编译时只需要编译需要修改的过程即可，不相关的过程也不会受到影响，也不要进行重新编译，因此总的开销也会变得很小。共享库的使用：由于段的实现，可以使多个进程共享同一部分数据或过程，节省了地址空间。,4.6.1 纯分段系统的实现,分段和分页的根本差别就是页定长而段非定长，所以系统在运行了一段时间以后，内存便变得混乱，被分为了很多块，有的是段，有的是空洞，我们称这种现象为跳棋盘或外碎片，由于空洞浪费了内存，故需要通过紧缩来解决。,4.

40、6.2 分段和分页结合,当段变得大的时候，我们也遇到了分页里的问题，即无法将整个段装入内存，因此又可以把这个段进行分页，每次把真正需要的页调入内存。,分页与分段的实例：MULTICS,为了实现分页和分段的共同的优点：分页：统一的页面大小，只用段的一部分时，并不用全部调入内存；分段：易于编程、模块化、保护和共享。,每个MULTICS程序都有一个段表，每个段对应一个段描述符，因为段表可能会很大，所以段表自己也是一个段并被分页，段描述符包含段是否在内存的标志，,段描述符,MULTICS的地址由两部分组成：段和段内地址 进行内存访问时，执行的算法是：1.由段号找段描述符；2.判断段的页表是否在内存中，如果在，就找到位置，如果不在，就发出段故障，如果违反保护要求就发出故障；3.检查所请求虚页的页表项，页面不在内存就发出一个页面故障，否则就从页表项中取出此页在主存中的起始地址；4.将偏移地址加到页的起始地址上得到主存地址；5.最后进行读或写操作。,