《存储器管理》PPT课件.ppt

1第四章 存储器管理 齐鲁工业大学 理学院 鹿文鹏2第四章 存储器管理n n如何对存储器进行有效的管理，不仅影响到存储器的利用率，而且还对系统性能有重大影响n n存储器：内存（本章） 外存（第六章） 齐鲁工业大学 理学院 鹿文鹏3主要内容n nnew 存储器的层次结构n n4.1 程序的装入和链接 n n4.2 连续分配方式n n4.3 基本分页存储管理方式n n4.4 基本分段存储管理方式n n4.5 虚拟存储器的基本概念n n4.6 请求分页存储管理方式n n4.7 页面置换算法n n4.8 请求分段存储管理方式齐鲁工业大学 理学院 鹿文鹏4本章学习目标n n了解存储管理的研究对象和目的n n了解存储管理的基本功能和有关的基本概念n n掌握分页存储管理和分段存储管理的基本概念n n掌握请求分页和请求分段存储管理的基本原理齐鲁工业大学 理学院 鹿文鹏New 4.1存储器的层次结构n n1.多级存储器结构n n2.主存储器与寄存器n n3.高速缓存与磁盘缓存5齐鲁工业大学 理学院 鹿文鹏1.多级存储器结构寄存器寄存器高速缓存内存磁盘缓存磁盘可移动存储器6三层由快到慢寄存器与主存（前四者）由操作系统直接管理，可快速访问，称为可执行存储器。

后两者需要通过I/O访问齐鲁工业大学 理学院 鹿文鹏2.主存储器与寄存器n n1.主存储器–容量大小容量大小n n2.寄存器–速度与速度与CPUCPU完全协调完全协调–长度以字为单位长度以字为单位 ，几十至几百个，几十至几百个7齐鲁工业大学 理学院 鹿文鹏3.高速缓存和磁盘缓存n n高速缓存–局部性原理局部性原理–CPUCPU与内存之间与内存之间n n磁盘缓存–频频繁繁使使用用的的磁磁盘盘数数据据暂暂存存在在内内存存中中的的 磁磁盘盘高高速速缓存中缓存中8齐鲁工业大学 理学院 鹿文鹏9预备知识n n地址空间的概念n n1．内存空间(物理空间) 内内存存是是由由若若干干个个存存储储单单元元组组成成的的，，每每个个存存储储单单元的编号称为内存地址元的编号称为内存地址( (或物理地址或物理地址) )n n2．逻辑空间 经经过过汇汇编编或或编编译译后后形形成成目目标标程程序序是是以以0 0为为基基址址顺顺序序进进行行编编址址的的，，目目标标程程序序占占据据的的地地址址空空间间称称为为作作业业的的逻逻辑辑地地址址空空间间逻逻辑辑空空间间中中的的地地址址称称为为逻逻辑辑地地址址，，这是一个相对地址。

这是一个相对地址齐鲁工业大学 理学院 鹿文鹏104.1 程序的装入和链接n n为作业创建进程需将其装入内存要把程序装入内存，就要对程序进行编译和链接l l1. 编译 由编译程序把源程序翻译成若干个目标模块；l l2. 链接 由链接程序把目标模块以及相关的库函数链接在一起，形成完整的装入模块；l l3. 装入 由装入程序把装入模块装入内存齐鲁工业大学 理学院 鹿文鹏114.1.1 程序的装入n n将一个装入模块装入内存时，有三种方式：l绝对装入方式绝对装入方式l可重定位装入方式可重定位装入方式l动态运行时装入方式动态运行时装入方式关键在于将逻辑地址转换为物理地址的时机不同齐鲁工业大学 理学院 鹿文鹏121.绝对装入方式Absolute Loading Moden n若编译时知道程序将在内存的(起始)驻留地址，编译程序将产生绝对(物理)地址的目标代码 只适用单道程序环境n n装入模块不需再地址转换，直接装入内存n n绝对地址，即可在编译或汇编时给出，也可由程序员直接给出通常在程序中采用符号地址，在编译或汇编时，再将其转换为绝对地址齐鲁工业大学 理学院 鹿文鹏132.可重定位装入方式Relocation Loading Moden n多道程序环境下，各目标模块的起始地址均从0开始，程序中的其它地址都是相对于起始地址计算的，不是绝对的物理地址，编译程序无法预知目标模块应放于何处。

n n装入时，需根据内存当前的情况，将模块装入到内存的适当位置，存在一个逻辑地址空间到内存物理地址空间的转换过程（即重定位）齐鲁工业大学 理学院 鹿文鹏142.可重定位装入方式Relocation Loading Moden n逻辑地址与实际装入内存的物理地址会不同逻辑地址与实际装入内存的物理地址会不同Load 1,2500 的作用是把2500单元中的数据送至寄存器1在装入时，指令的地址会由原来的1000，变为11000，取数地址2500也会变为12500该例中，在装入时对目标程序中指令和数据的地址修改过程称为重定位该地址变换是在装入时一次完成的，不再改变，故称为静态重定位齐鲁工业大学 理学院 鹿文鹏153.动态运行时装入方式Dynamic Run-time Loadingn n把程序装入内存后，并不立即把装入模块中的逻辑地址转换为物理地址，仍是相对地址逻辑地址到物理地址的转换直到程序真正运行时才进行n n不仅允许装入模块装入到内存中的任何位置，而且允许程序在运行时在内存中移动动态重定位分区分配）齐鲁工业大学 理学院 鹿文鹏164.1.2 程序的链接n n根据链接时间的不同，可分为：l静态链接静态链接l装入时动态链接装入时动态链接l运行时动态链接运行时动态链接关键在于进行链接的时机齐鲁工业大学 理学院 鹿文鹏171.静态链接方式Static Linkingn n在程序运行之前把各目标模块及库函数链接成一个完整的装入模块，以后不再拆开。

n n装配时需解决两个问题：–(1)(1)对相对地址进行修改对相对地址进行修改–(2)(2)变换外部符号变换外部符号齐鲁工业大学 理学院 鹿文鹏18n n模模块块ABCABC在在链链接接前前其其内内部部地地址址均均是是相相对对于于起起始始地地址址0 0而言的n n链链接接成成一一个个装装入入模模块块后后，，BCBC的的首首地地址址分分别别变变成成了了L L和和L+ML+M，，这这就就需需要要修修改改BCBC中中的的相相对对地地址址，，将将其其全全部部加加上上L L或或L+ML+M；；对对于于ABCABC各各模模块块中中所所使使用用的的外外部部调调用用符符号号，，也也都都需需进进行行变变换换，，CALL CALL B B需需变变换换为为JSL LJSL L齐鲁工业大学 理学院 鹿文鹏192.装入时动态链接Load-time Dynamic Linkingn n编译的目标模块在装入内存时，边装入边链接n n即在装入一个目标模块时，若发生一个外部模块调用，将引起装入程序去找出相应的外部目标模块，并将它装入内存，还需修改目标模块中的相对地址齐鲁工业大学 理学院 鹿文鹏202.装入时动态链接Load-time Dynamic Linkingn n优点: VS 静态链接 1.便于修改和更新 各目标模块分开存放，便于修改或更新。

静态链接要修改或更新时，需重新打开装入模块，低效 2.便于实现对目标模块的共享 可将一个目标模块链接到几个应用模块，实现多个应用程序对该模块的共享静态链接，每个应用模块都必须含有该目标模块的完整拷贝，无法共享齐鲁工业大学 理学院 鹿文鹏213.运行时动态链接Run-time Dynamic Linkingn n把对某些模块的链接推迟到执行时进行n n在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并链接到调用者模块上n n优点：本次执行不需要的模块不链接可加快装入过程，而且节省内存空间齐鲁工业大学 理学院 鹿文鹏224.1 程序的装入和链接 小结n n程序的装入–绝对装入方式绝对装入方式–可重定位装入方式可重定位装入方式–动态运行时装入方式动态运行时装入方式n n程序的链接–静态链接方式静态链接方式–装入时动态链接装入时动态链接–运行时动态链接运行时动态链接齐鲁工业大学 理学院 鹿文鹏234.2 连续分配方式连续分配方式，指为一个用户程序分配一个连续的内存空间n n4.2.1 单一连续分区分配 n n4.2.2 固定分区分配n n4.2.3 动态分区分配n n4.2.4 动态重定位分区分配n n4.2.5 对换(Swapping) 齐鲁工业大学 理学院 鹿文鹏244.2.1 单一连续分区分配n n1.内存划分 (1)系统区 仅提供给OS使用，通常为内存中的低址部分 (2)用户区 单一分区，除系统区外的全部内存空间，只提供给用户使用n n2. 适用环境 只适用于单用户、单任务环境 ？齐鲁工业大学 理学院 鹿文鹏254.2.2 固定分区分配n n最早使用的一种可运行多道程序的存储管理方式。

n n将内存空间划分为若干个固定大小的区域，在每个分区中可以装入一道作业，当内存中划分成几个分区时，便允许几道作业并发运行；当有一个空闲分区时，便可从外存的后备队列中，选择一个适当大小的作业装入该分区；当该作业结束时，又可从后备队列中找出另一个作业调入该分区划分分区内存分配齐鲁工业大学 理学院 鹿文鹏261.划分分区的方法n n1. 分区大小相等使所有的内存分区大小相等适用于利用一台计算机去控制多个相同对象的场合缺乏灵活性n n2. 分区大小不等将内存区分为大小不等的多块，灵活性稍好，可根据程序的大小为之分配适当的分区齐鲁工业大学 理学院 鹿文鹏272.内存分配n n把分区按大小排队，并建立一个分区使用表分区表中记录各分区的起始地址、大小和状态n n分配内存时，检索分区表，如果存在大小合适且未分配的分区，就把其分配给相应的程序，然后置“已分配”标志；若未找到大小足够的分区，则拒绝为之分配内存齐鲁工业大学 理学院 鹿文鹏282.内存分配n n分分区区大大小小固固定定，，灵灵活活性性仍仍不不足足，，会会产产生生内内存存碎碎片片；；在某些用于控制相同对象的场合仍有一定应用在某些用于控制相同对象的场合仍有一定应用。

作业2：30K作业1：112K齐鲁工业大学 理学院 鹿文鹏294.2.3 动态分区分配n n动态分区分配是根据进程的实际需要，动态地为之分配内存空间又称为可变分区分配n n示意图齐鲁工业大学 理学院 鹿文鹏30可变分区内存使用示意图齐鲁工业大学 理学院 鹿文鹏314.2.3 动态分区分配n n三个问题–分区分配中的数据结构分区分配中的数据结构–分区分配算法分区分配算法–分区分配操作分区分配操作齐鲁工业大学 理学院 鹿文鹏321.分区分配中的数据结构n n记录内存的使用情况，为分配提供依据n n(1)空闲分区表在系统中设置一张空闲分区表，用于记录每个空闲分区的情况每个空闲分区占一个表目，表目中包括分区序号、分区始址及分区的大小等数据项齐鲁工业大学 理学院 鹿文鹏331.分区分配中的数据结构n n(2)空闲分区链每个分区的起始部分，设置用于链接各分区的前向指针；在分区尾部设置一后向指针通过前、后向链接指针，可将所有的空闲分区链接成一个双向链前后向指针，大小，状态齐鲁工业大学 理学院 鹿文鹏342.分区分配算法n n按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业。

n n常用的三种分配算法：l首次适应算法首次适应算法l循环适应算法循环适应算法l最佳适应算法最佳适应算法齐鲁工业大学 理学院 鹿文鹏35(1)首次适应算法n n空空闲闲分分区区以以地地址址递递增增的的次次序序链链接接分分配配时时，，从从链链首首开开始始顺顺序序查查找找，，直直至至找找到到一一个个大大小小能能满满足足要要求求的的空空闲闲分分区区；；然然后后根根据据作作业业的的大大小小，，从从该该分分区区中中划划出出一一块块内内存存空空间间分分配配给给请请求求者者，，余余下下的的空空闲闲分分区区仍仍留留在在空闲链中空闲链中n n优优点点：：倾倾向向于于利利用用内内存存中中低低址址的的空空闲闲区区，，保保留留了了高高址址部部分分的的大大空空闲闲区区，，为为以以后后到到达达的的大大作作业业分分配配大大的的内存空间创造了条件内存空间创造了条件缺缺点点：：低低址址不不断断被被划划分分，，会会产产生生大大量量的的碎碎片片；；每每次次从低址开始查找，会增加查找可用空间的开销从低址开始查找，会增加查找可用空间的开销齐鲁工业大学 理学院 鹿文鹏36(1)首次适应算法图中采用的空闲分区链按地址由小到大的顺序对空闲分区进行组织，开始指向以40k为首址的空闲分区（其大小为46k，下一个空闲分区为始址为118k）。

作业5大小为36k齐鲁工业大学 理学院 鹿文鹏37(2)循环首次适应算法n n分分配配时时，，不不每每次次均均从从链链首首开开始始查查找找，，而而是是从从上上次次找找到到的的空空闲闲分分区区的的下下一一个个空空闲闲分分区区开开始始查查找找，，直直至至找找到到第第一一个个能能满满足足要要求求的的空空闲闲分分区区，，并并从从中中划划出出一一块块与请求的大小相等的内存空间分配给作业与请求的大小相等的内存空间分配给作业n n需需设设置置一一起起始始查查寻寻指指针针，，以以指指示示下下一一次次起起始始查查寻寻的的空空闲闲分分区区，，并并采采用用循循环环查查找找方方式式即即如如果果最最后后一一个个( (链链尾尾) )空空闲闲分分区区，，其其大大小小仍仍不不能能满满足足要要求求，，应应返返回回到到第第一一个个空空闲闲分分区区，，比比较较其其大大小小是是否否满满足足要要求求找找到后，应立即调整起始查寻指针到后，应立即调整起始查寻指针n n优优点点：：空空闲闲分分区区分分布布均均更更均均匀匀，，减减少少了了查查找找空空闲闲分分区的开销，但会导致缺乏大的空闲分区区的开销，但会导致缺乏大的空闲分区齐鲁工业大学 理学院 鹿文鹏38(3)最佳适应算法n n每每次次为为作作业业分分配配内内存存时时，，总总是是把把既既能能满满足足要要求求，，又又是是最最小小的的空空闲闲分分区区分分配配给给作作业业，，避避免免了了“ “大大材材小小用用” ”。

n n为为了了加加速速寻寻找找，，要要求求将将所所有有的的空空闲闲区区，，按按其其容容量量大大小小以以递递增增的的顺顺序序形形成成一一空空闲闲区区链链这这样样，，第第一一次次找找到的满足要求的空闲区，必然是最优的到的满足要求的空闲区，必然是最优的n n特特点点：：每每次次似似乎乎是是最最佳佳的的，，然然而而在在宏宏观观上上却却不不一一定定每每次次分分配配后后所所切切割割下下来来的的剩剩余余部部分分总总是是最最小小的的，，在在存储器中会留下许多这样难以利用的小空闲区存储器中会留下许多这样难以利用的小空闲区齐鲁工业大学 理学院 鹿文鹏39(3)最佳适应算法图中采用的空闲分区链按容量由小到大的顺序组织齐鲁工业大学 理学院 鹿文鹏403.分区分配操作(分配－回收)1)1)分配内存分配内存若若m.size-u.size<=sizem.size-u.size<=size，，说说明明多多余余部部分分太太小小，，可可不不再再切切割割，，将将整整个个分分区区分分配配给给请请求求者者；；否否则则，，从从该该分分区区中中划划分分出出与与请请求求的的大大小小相相等等的的内内存存空空间间分分配配出出去去，，余余下下的的部部分分仍仍留留在在空空闲闲分分区区链链或或空空闲闲分分区区表表中中。

最最后后，，将将分分配配区区的的首首址址返返回回给给调调用者m.size 空闲分区大小u.size 用户作业大小 齐鲁工业大学 理学院 鹿文鹏413.分区分配操作2)2)回收内存回收内存n n当当一一个个进进程程（（或或程程序序））释释放放其其所所占占内内存存区区时时，，系系统统将将首首先先检检查查回回收收区区是是否否与与其其它它空空闲闲区区相相邻邻，，若若相相邻邻则则合合并并成成一一个个空空闲闲区区，，否否则则，，将将回回收收区区插插入入空空闲闲分分区表（或空闲分区链）中的适当位置区表（或空闲分区链）中的适当位置n n回收情况：回收情况：–A. A. 只有前邻空闲区只有前邻空闲区–B. B. 只有后邻空闲区只有后邻空闲区–C. C. 既有前邻空闲区又有后邻空闲区既有前邻空闲区又有后邻空闲区–D. D. 没有邻接空闲区没有邻接空闲区根据不同情况，根据不同情况，A A、、B B、、C C有不同的合并策略有不同的合并策略齐鲁工业大学 理学院 鹿文鹏42回收内存示意图nA. 将R合并到f1，f1.addr；f1.size+R.size ->f1.sizeကnB. 将f2 合并到R ，R.addr；f2.size+R.size ->f2.sizeကnC. f1、R、f2合并到f1，f1.addr；f1.size+R.size+f2.size ->f1.size；撤消f2空闲区表项ကnD. R作为一个新空闲区，插入到空闲区表（链）的适当位置。

齐鲁工业大学 理学院 鹿文鹏434.2.4 动态重定位分区分配n n1.动态重定位的引入n n2.动态重定位的实现n n3.动态重定位分区分配算法齐鲁工业大学 理学院 鹿文鹏441.动态重定位的引入n n为为了了充充分分利利用用内内存存碎碎片片，，可可利利用用“ “紧紧凑凑” ”操操作作把把多多个个碎碎片片处处理理为为一一个个比比较大的分区，以便利用较大的分区，以便利用 n n经经过过紧紧凑凑后后的的某某些些用用户户程程序序在在内内存存中中的的位位置置发发生生了了变变化化，，此此时时需需对对程程序序和和数数据据的的地地址址加加以以修修改改（（变变换换）），，即即需需要要进进行重定位行重定位齐鲁工业大学 理学院 鹿文鹏452.动态重定位的实现n n采采用用动动态态运运行行时时装装入入方方式式，，地地址址转转换换推推迟迟到到程程序序指指令真正要执行时进行令真正要执行时进行n n为为避避免免影影响响速速度度，，必必须须有有硬硬件件地地址址变变换换机机构构的的支支持持（（重重定定位位寄寄存存器器）），，用用它它来来存存放放程程序序在在内内存存中中的的起起始始地地址址程程序序在在执执行行时时，，真真正正访访问问的的内内存存地地址址是是相相对地址与重定位寄存器中的地址相加而形成的对地址与重定位寄存器中的地址相加而形成的。

n n地地址址变变换换过过程程是是在在程程序序执执行行期期间间，，随随着着对对每每条条指指令令和数据的访问而自动进行的，故称为和数据的访问而自动进行的，故称为动态重定位动态重定位n n当当系系统统对对内内存存进进行行了了“ “紧紧凑凑” ”，，而而使使若若干干程程序序从从内内存存的的某某处处移移至至另另一一处处时时，，不不需需对对程程序序做做任任何何修修改改，，只只要要用用该该程程序序的的新新起起始始地地址址，，去去置置换换原原来来的的起起始始地地址即可齐鲁工业大学 理学院 鹿文鹏462.动态重定位的实现齐鲁工业大学 理学院 鹿文鹏473.动态重定位分区分配算法与动态分区分配算法基本相同，差别仅在于：增加了紧凑功能，在找不到足够大的空闲分区来满足用户需求时进行紧凑齐鲁工业大学 理学院 鹿文鹏483.动态重定位分区分配算法n n优点：解决了动态分区分配所引入的“内存零头”问题消除内存碎片，提高内存利用率n n缺点：提高硬件成本，紧凑时花费CPU时间齐鲁工业大学 理学院 鹿文鹏49动态重定位 VS 静态重定位n n静态重定位:当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后不再转换。

n n动态重定位:在程序运行过程中要访问数据时再进行地址变换由地址变换机构进行的地址变换，硬件上需要重定位寄存器的支持动态重定位分区分配VS动态分区分配相对而言，前者具有紧凑功能，需要重定位寄存器支持齐鲁工业大学 理学院 鹿文鹏504.2.5 对换(Swapping)n n1. 1.对换的引入对换的引入n n把把内内存存中中暂暂时时不不能能运运行行的的进进程程或或暂暂时时不不用用的的程程序序和和数数据据，，换换出出到到外外存存，，而而把把已已具具备备运运行行条条件件的的进进程程或或进进程程所所需需要要的的程程序序和和数数据据，，换换入入内内存存，，使使其其投投入入运运行行( (从而提高内存利用率从而提高内存利用率) )n n如如果果对对换换以以整整个个进进程程为为单单位位，，称称之之为为“ “整整体体对对换换” ”或或“ “进程对换进程对换” ”目的是为了解决内存紧张问题目的是为了解决内存紧张问题如如果果对对换换以以“ “页页” ”或或“ “段段” ”为为单单位位，，则则称称之之为为“ “页页面面对对换换” ”或或“ “分分段段对对换换” ”目目的的是是为为了了支支持持虚虚拟拟存存储系统储系统n n此此小小节节仅仅介介绍绍进进程程对对换换。

为为了了进进程程对对换换，，需需三三方方面面功能：对换空间的管理、进程的换出及换入功能：对换空间的管理、进程的换出及换入齐鲁工业大学 理学院 鹿文鹏512.对换空间的管理n n把外存分为文件区和对换区l l文件区：用于存放文件；为了提高空间的利用率，对其采用离散分配方式l l对换区：用于存放从内存换出的进程；因对换操作频繁，为提高进程换入换出速度，对其采用连续分配方式对换是在 内存与 外存的对换区之间进行）齐鲁工业大学 理学院 鹿文鹏522.对换空间的管理n n为了对对换区中的空闲盘块进行管理，在系统中应配置相应的数据结构，以记录外存的使用情况与内存在动态分区分配方式中所用的数据结构相似，同样可以用空闲分区表或空闲分区链n n对换空间的分配与回收，与动态分区分配方式中的内存分配与回收方法雷同其分配算法可以是首次适应算法、循环首次适应算法或最佳适应算法齐鲁工业大学 理学院 鹿文鹏533.进程的换出和换入n n进程换出：选择处于阻塞状态且优先级最低的进程作为换出进程，将其程序和数据传送到外存的对换区上，然后便可回收其所占用的内存空间，并对其PCB作相应修改n n进程换入：查找处于“就绪”状态但已换出的进程，将其中换出时间最久的进程作为换入进程，将其换入。

齐鲁工业大学 理学院 鹿文鹏544.2 连续分配方式 小结n n单一连续分配方式n n固定分区分配 分区使用表n n动态分区分配 –首次适应算法首次适应算法 循环首次适应算法循环首次适应算法 最佳适应算法最佳适应算法n n动态重定位分区分配–“ “紧凑紧凑” ” 动态重定位的实现（重定位寄存器）动态重定位的实现（重定位寄存器）n n对换齐鲁工业大学 理学院 鹿文鹏554.3 基本分页存储管理方式n n引入：连续分配方式会形成许多“碎片”，虽然可通过“紧凑”方法将碎片拼接成可用的大块空间，但须为此付出较大开销如果允许将一个进程直接分散地分配到许多不相邻接的分区中，就不必再进行“紧凑”基于这一思想而产生了离散分配方式，相异于4.2所述连续分配方式齐鲁工业大学 理学院 鹿文鹏564.3 基本分页存储管理方式n n分段存储管理方式 基本单位是段n n分页存储管理方式 基本单位是页n n基本的分页存储管理方式，要求把每个作业全部装入内存后方能运行不具备页面对换功能）n n4.3.1 页面和页表n n4.3.2 地址变换机构n n4.3.3 两级和多级页表齐鲁工业大学 理学院 鹿文鹏574.3.1 页面与页表n n1. 1.页面页面n n1)1)页面和物理块页面和物理块n n页页面面：：将将一一个个进进程程的的逻逻辑辑地地址址空空间间分分成成若若干干个个大大小小相等的片相等的片n n物物理理块块：：内内存存物物理理空空间间分分成成与与页页相相同同大大小小的的若若干干个个存储块存储块n n分分配配内内存存时时，，可可将将进进程程中中的的若若干干页页( (逻逻辑辑地地址址空空间间) )分别装入多个可以不相邻接的块分别装入多个可以不相邻接的块( (物理地址空间物理地址空间) )中中。

“ “页内碎片页内碎片” ”齐鲁工业大学 理学院 鹿文鹏581.页面n n2)页面大小n n页面大小应适中，且页面大小应为2的幂，一般为512B~8KBl l页面太小，减少了内存碎片，有利于提高内存利用率；但也会导致页面过多，页表过长l l页面太大，则会导致内存碎片较多齐鲁工业大学 理学院 鹿文鹏592.分页存储的地址结构n n两部分，前一部分为页号P (220);后一部分为位移量W，即页内地址 (212)n n从逻辑地址获得页号p和页内偏移dp=INT(A/L)d=[A] MOD LA——逻辑地址；L——页大小齐鲁工业大学 理学院 鹿文鹏602.地址结构齐鲁工业大学 理学院 鹿文鹏613.页表n n各页离散存储在任一物理块，系统需记录各页面对应的物理块n n系统为每个进程建立一张页面映射表，简称页表进程的所有页，依次在页表中有一页表项，其中记录了其对应的物理块号n n页表的作用是实现从页号到物理块号的地址映射查找页表，即可找到每页在内存中的物理块号齐鲁工业大学 理学院 鹿文鹏62页表的作用实现从页号到物理块号的地址映射实现从页号到物理块号的地址映射作业每页1K内存每块1K齐鲁工业大学 理学院 鹿文鹏634.3.2 地址变换机构n n功能：完成从逻辑地址（页号+页内地址）到物理地址的转换。

l( (页页与与物物理理块块的的大大小小完完全全一一致致，，故故) )页页内内地地址址和和内内存存物物理理块块中中的的物物理理地地址址是是一一一一对对应应的的，，无无需需再再转换转换l页页号号需需转转换换成成内内存存中中的的物物理理块块号号，，这这也也是是地地址址变换机构的实质需做的工作变换机构的实质需做的工作借助于页表完成借助于页表完成n n两种实现方法l基本的地址变换机构基本的地址变换机构l具有快表的地址变换机构具有快表的地址变换机构齐鲁工业大学 理学院 鹿文鹏641.基本的地址变换机构n n由于页表项的总数很多，不可能均用寄存器来实现，页表大多驻留在内存中n n需设置一个页表寄存器PTR（Page-Table Register），存放页表在内存的始址和页表的长度进程未执行时，这两个数据存于进程的PCB中；执行时，才将它们装入PTR齐鲁工业大学 理学院 鹿文鹏651.基本的地址变换机构n n地址变换过程：地址变换过程：l l1)1)分分页页地地址址变变换换机机构构自自动动将将有有效效地地址址分分为为页页号号和和页页内地址两部分内地址两部分，再以页号为索引去检索页表再以页号为索引去检索页表。

l l2)2)在在检检索索页页表表前前，，将将页页号号与与页页表表长长度度比比较较，，如如果果越越界则产生一越界中断，本次访问失败界则产生一越界中断，本次访问失败l l3)3)如如果果未未越越界界，，则则 页页表表始始址址+ +页页号号* *页页表表项项长长度度  得得到到该该页页号号在在页页表表中中的的位位置置，，从从中中可可得得到到该该页页的的物物理块号理块号，将之装入物理地址的物理块号部分将之装入物理地址的物理块号部分l l4)4)最最后后再再将将有有效效地地址址中中的的页页内内地地址址送送入入物物理理地地址址寄寄存器的块内地址中存器的块内地址中齐鲁工业大学 理学院 鹿文鹏66分页系统的地址变换机构齐鲁工业大学 理学院 鹿文鹏67分页系统的地址变换 实例逻辑地址为3BADH 页面大小为2KB页表寄存器齐鲁工业大学 理学院 鹿文鹏681.基本的地址变换机构n n一个问题？一个问题？n n页页表表是是存存放放在在内内存存中中的的，，这这使使CPUCPU每每次次要要存存取取一一个个数据时，都要两次访问内存数据时，都要两次访问内存n n第第一一次次是是访访问问内内存存中中的的页页表表，，从从中中找找到到该该页页的的物物理理块块号号，，将将此此块块号号与与页页内内偏偏移移量量WW拼拼接接以以形形成成物物理理地地址址；；第第二二次次访访问问内内存存时时，，才才是是从从第第一一步步所所得得地地址址中中获得所需数据获得所需数据( (或向此地址中写入数据或向此地址中写入数据) )。

n n将使计算机的处理速度降低近将使计算机的处理速度降低近1/21/2n n？？齐鲁工业大学 理学院 鹿文鹏692. 具有快表的地址变换机构n n增设一个具有并行查寻能力的特殊高速缓冲寄 存 器 ， 又 称 为 “联 想 寄 存 器”(Associative Memory)或 “快表”，用于存放当前访问的那些页表项意味着这些页表项不在存放在内存中）齐鲁工业大学 理学院 鹿文鹏702. 具有快表的地址变换机构n n地址变换过程：地址变换过程：l l在在CPUCPU给给出出有有效效地地址址后后，，由由地地址址变变换换机机构构自自动动地地将将页页号号P P送送入入高高速速缓缓冲冲存存储储器器（（快快表表）），，将将此此页页号号与与其中的页号进行比较其中的页号进行比较l l若若有有相相匹匹配配的的页页号号（（在在快快表表中中）），，直直接接读读出出其其所所对对应的物理块号，并送物理地址寄存器中应的物理块号，并送物理地址寄存器中l l若若没没有有匹匹配配的的，，还还需需访访问问内内存存中中的的页页表表找找到到后后，，把把对对应应的的物物理理块块号号送送地地址址寄寄存存器器；；也也将将此此页页表表项项存存入入快快表表中中。

但但如如果果快快表表已已满满，，则则将将一一个个老老的的且且已已被被认为不再需要的页表项换出认为不再需要的页表项换出齐鲁工业大学 理学院 鹿文鹏712. 具有快表的地址变换机构齐鲁工业大学 理学院 鹿文鹏73练习 例：有一页式系统，其页表存放在主存中：例：有一页式系统，其页表存放在主存中： ①①如如果果对对主主存存的的一一次次存存取取需需要要1.5 1.5 μs,μs,试试问问实现一次页面访问的存取时间是多少实现一次页面访问的存取时间是多少? ? ②②如如果果系系统统加加有有快快表表, ,平平均均命命中中率率为为85%,85%,当当页页表表项项在在快快表表中中时时, ,其其查查找找时时间间忽忽略略为为0, 0, 试问此时的存取时间是多少试问此时的存取时间是多少? ?齐鲁工业大学 理学院 鹿文鹏74练习答答答答：：：：若若若若页页页页表表表表存存存存放放放放在在在在主主主主存存存存中中中中，，，，则则则则要要要要实实实实现现现现一一一一次次次次页页页页面面面面访访访访问问问问需需需需两两两两次次次次访访访访问问问问主主主主存存存存：：：：一一一一次次次次是是是是访访访访问问问问页页页页表表表表，，，，确确确确定定定定所所所所存存存存取取取取页页页页面面面面的的的的物物物物理理理理地地地地址址址址（（（（称称称称为为为为定定定定位位位位））））。

第第第第二二二二次次次次才才才才根根根根据据据据该该该该地地地地址址址址存取页面数据存取页面数据存取页面数据存取页面数据 ■■■■页表在主存的存取访问时间页表在主存的存取访问时间页表在主存的存取访问时间页表在主存的存取访问时间 =1.5*2=3(=1.5*2=3(=1.5*2=3(=1.5*2=3(μsμsμsμs) ) ) ) ■■■■增加快表后的存取访问时间增加快表后的存取访问时间增加快表后的存取访问时间增加快表后的存取访问时间 =0.85*1.5+(1-0.85)*2*1.5=1.725(μs)=0.85*1.5+(1-0.85)*2*1.5=1.725(μs)=0.85*1.5+(1-0.85)*2*1.5=1.725(μs)=0.85*1.5+(1-0.85)*2*1.5=1.725(μs)齐鲁工业大学 理学院 鹿文鹏75练习n n某某某某存存存存储储储储器器器器的的的的用用用用户户户户编编编编程程程程空空空空间间间间共共共共32323232个个个个页页页页面面面面，，，，每每每每页页页页为为为为1KB1KB1KB1KB，，，，内内内内存存存存为为为为16KB16KB16KB16KB。

假假假假定定定定某某某某时时时时刻刻刻刻一一一一用用用用户户户户页页页页表表表表中中中中已调入内存的页面对应的物理块号如下表：已调入内存的页面对应的物理块号如下表：已调入内存的页面对应的物理块号如下表：已调入内存的页面对应的物理块号如下表：页号页号页号页号物理块号物理块号物理块号物理块号0 0 0 05 5 5 51 1 1 1101010102 2 2 24 4 4 43 3 3 37 7 7 7则逻辑地址则逻辑地址0A5C0A5C（（H H）所对应的物理地址为）所对应的物理地址为 ：：125C125C齐鲁工业大学 理学院 鹿文鹏76练习vv0A5C0A5C0A5C0A5C＝＝＝＝0000,100000,100000,100000,1010,0101,110010,0101,110010,0101,110010,0101,1100vv页号为页号为页号为页号为2 2 2 2，对应块号为，对应块号为，对应块号为，对应块号为4 4 4 4，有：，有：，有：，有：vv物理地址：物理地址：物理地址：物理地址：0001000100010001，，，，0000000010,0101,110010,0101,110010,0101,110010,0101,1100vv即：即：即：即：125C125C125C125C齐鲁工业大学 理学院 鹿文鹏774.3.3 两级和多级页表n n引入：计算机支持的逻辑地址空间非常大(232~264)，每个进程的页表项也非常庞大，需占据大量的连续内存空间，这显然不现实。

n n如何解决？1.采用离散分配方式－－解决需大量连续内存空间问题 (将页表再次进行分块)2.只将当前需要的部分页表项调入内存－－使页表需占用的内存减少齐鲁工业大学 理学院 鹿文鹏781.两级页表n n将页表进行分页，并离散地将各个页面分别存放在不同的物理块中，同时为离散的页表再建立一张页表，称为外层页表，其每个表项记录了页表分页的物理块号n n逻辑地址结构如下：齐鲁工业大学 理学院 鹿文鹏791.两级页表n n页内地址:12位，页面大小为212，4KBn n外层页内地址:10位，每个页表分页中最多可包含210个页表项（对应210个物理块）n n外层页号:10位，最多允许210个页表分页齐鲁工业大学 理学院 鹿文鹏80两级页表示意图外层页表的每个表项存放的是某页表分页的在内存中的物理块号页表(分页)的每个表项存放的是某页在内存中的物理块号可利用两级页表，实现逻辑地址到物理地址的转换这里只是物理块号，并不是内存单元的编号比如外层页号为1,外层页内地址也为1,寻址齐鲁工业大学 理学院 鹿文鹏81具有两级页表的地址变换n n外层页表寄存器，用于存放外层页表的始址外层页表寄存器，用于存放外层页表的始址d0d0n n1. 1.以以逻逻辑辑地地址址中中的的外外层层页页号号p1p1，，作作为为外外层层页页表表的的索索引引，，找找到到d0d0和和p1p1对对应应的的表表项项，，从从中中可可知知指指定定页页表表分分页页的的始始址址d1(d1(物物理理块号块号) )；；n n2. 2.以以外外部部页页内内地地址址p2p2，，作作为为指指定定页页内内分分页页的的索索引引，，找找到到d1d1和和p2p2对应的表项，从中可知该页在内存的物理块号对应的表项，从中可知该页在内存的物理块号b bn n3. 3.物物理理块块号号b b与与页页内内地地址址d d，，即即构构成成了了要要访访问问的的内内存存的的物物理理地地址。

址d0d1齐鲁工业大学 理学院 鹿文鹏82如何减少页表所占的内存空间n n上上述述离离散散分分配配空空间间的的办办法法只只解解决决了了大大页页表表无无需需大大片片连连续续存存储储空空间间的的问问题题，，并并未未减减少少页页表表所所占占的的内内存存空空间如何减少？间如何减少？n n只只把把当当前前需需要要的的一一些些页页表表项项调调入入内内存存，，以以后后再再根根据据需要陆续调入其它的需要陆续调入其它的n n在在采采用用两两级级页页表表的的情情况况下下，，需需把把外外层层页页表表全全部部调调入入内存，对于页表分页只需调入需要使用的内存，对于页表分页只需调入需要使用的在在外外层层页页表表的的表表项项中中，，需需增增设设一一个个状状态态位位，，表表示示相相应的页表分页是否已调入内存应的页表分页是否已调入内存 （请求分页存储，虚拟存储器中再作详细介绍）（请求分页存储，虚拟存储器中再作详细介绍）齐鲁工业大学 理学院 鹿文鹏832.多级页表n n对于64位机器，若采用两级页表，页内地址12位，外部页内地址10位，这时外部页号会达42位，每个表项占4个字节，就需要244B的连续内存空间显然无法接受。

n n采用多级页表，将外层页表再进行分页，将各分页离散地装入到不相邻接的物理块中，再利用第2级的外层页表来映射它们之间的关系齐鲁工业大学 理学院 鹿文鹏844.3 基本分页存储管理方式 小结n n页面、物理块与页表 n n分页地址结构： 页号＋页内地址n n地址变换机构 –基本的地址变换机构基本的地址变换机构–具有快表的地址变换机构具有快表的地址变换机构n n两级和多级页表齐鲁工业大学 理学院 鹿文鹏854.4 基本分段存储管理方式n n存储管理方式从固定分区到动态分区分配，进而到分页存储管理方式主要是为了提高内存的利用率 n n提出基本分段存储管理方式主要是为了满足用户（程序员）在编程和使用上的多方面的要求齐鲁工业大学 理学院 鹿文鹏864.4 基本分段存储管理方式n n4.4.1 分段存储管理方式的引入n n4.4.2 分段系统的基本原理n n4.4.3 信息共享n n4.4.4 段页式存储管理方式齐鲁工业大学 理学院 鹿文鹏874.4.1 分段存储管理方式的引入为了满足用户和程序的如下需要： 1)方便编程用户通常将作业按逻辑关系划分为若干段希望要访问的逻辑地址是由段名和段内偏移量决定。

2)信息共享实现共享是以信息的逻辑单位－段为基础的为实现段的共享，希望存储管理能与用户程序分段的组织方式相适应齐鲁工业大学 理学院 鹿文鹏884.4.1 分段存储管理方式的引入3)信息保护对信息的逻辑单位－段进行保护4)动态增长段在使用过程中可能会不断增长，唯有分段存储可较好解决该问题5)动态链接动态链接在运行时，只将主程序对应的目标程序段装入内存在需调用某些段时才将其装入，需要以段作为存储管理的单位齐鲁工业大学 理学院 鹿文鹏894.4.2 分段系统的基本原理n n1.分段n n2.段表n n3.地址变换机构齐鲁工业大学 理学院 鹿文鹏901.分段n n作业的地址空间被划分为若干个段，每个段用来定义一组逻辑信息，均从0开始编址，并采用一段连续的连续的地址空间n n段的长度由相应的逻辑信息组的长度决定，因而各段长度不等n n逻辑地址由段号和段内地址组成齐鲁工业大学 理学院 鹿文鹏912.段表n n进程的多个段被离散的放入内存不同位置n n为了能将物理内存与逻辑段地址对应起来，需为每个进程建立一张段映射表每个段在表中占有一个表项，记录了该段在内存中的始址和段的长度n n进程可通过查找段表，找到每个段对应的内存区，实现从逻辑段到物理内存区的映射。

齐鲁工业大学 理学院 鹿文鹏92利用段表实现地址映射齐鲁工业大学 理学院 鹿文鹏933.地址变换机构段表寄存器存放段表始址和段表长度SL齐鲁工业大学 理学院 鹿文鹏94n n与分页系统一样，当段表放在内存中时，每访问一个数据，都须访问两次内存n n解决方法也类似，增设一个高速缓冲寄存器用于保存最近常用的段表项齐鲁工业大学 理学院 鹿文鹏954.分页和分段的主要区别n n分分页页是是出出于于系系统统管管理理的的需需要要，，分分段段是是出出于于用用户户应应用用的需要的需要– –一一条条指指令令或或一一个个操操作作数数可可能能会会跨跨越越两两个个页页的的分分界界处处，，而而不会跨越两个段的分界处不会跨越两个段的分界处n n页大小是系统固定的，而段大小则通常不固定页大小是系统固定的，而段大小则通常不固定n n逻辑地址表示：逻辑地址表示：– –分分页页是是一一维维地地址址空空间间，，各各个个模模块块在在链链接接时时组组织织成成同同一一个个地址空间；只利用一个标记符即可表示一个地址地址空间；只利用一个标记符即可表示一个地址– –分分段段是是二二维维地地址址空空间间，，各各个个模模块块在在链链接接时时可可以以每每个个段段组组织成一个地址空间；标识地址需给出段名和段内地址。

织成一个地址空间；标识地址需给出段名和段内地址n n通通常常段段比比页页大大，，因因而而段段表表比比页页表表短短，，可可以以缩缩短短查查找找时间，提高访问速度时间，提高访问速度齐鲁工业大学 理学院 鹿文鹏964.4.3 信息共享n n分段系统的突出优点，易于实现段的共享，即允许若干个进程共享一个或多个分段ØØ分页系统也可实现程序和数据的共享，但不如分段系统来得方便举例对比）n n可重入代码：一种允许多个进程同时访问（可被共享）的代码；不允许任何进程对它进行修改齐鲁工业大学 理学院 鹿文鹏974.4.3 信息共享n n例：多用户系统，可同时接纳40个用户，每个用户均可执行文本编辑程序文本编辑程序有160KB代码和40KB数据区，若代码为非可重入的，需要8000KB内存空间支持40个用户如果160KB程序代码为可重入的，则不论在分页还是在分段系统中该代码均可被 共 享 ， 此 时 所 需 内 存 空 间 为160+40*40=1760KB齐鲁工业大学 理学院 鹿文鹏984.4.3 信息共享n n分页系统中：假定每个页面大小为4KB，代码需占用40个页面，数据需占10页面每个用户进程的页表中均需建立相应的页表项。

n n如图:齐鲁工业大学 理学院 鹿文鹏99ed1ed1ed2ed2……ed40ed40data1data1……data10data1021212222……60606161……7070……ed1ed1ed2ed2……ed40ed40data1data1……data10data10data1data1……data10data10进程进程1进程进程2页表页表页表页表ed1ed1ed2ed2……ed40ed40data1data1……data10data1021212222……60607171……8080主存分页系统中共享editor，需建立比较复杂的页表021226061707180齐鲁工业大学 理学院 鹿文鹏100分段系统中共享editor示意editoreditordata1data1editoreditordata2data2段长段长段长段长基址基址基址基址16016080804040240240段长段长段长段长基址基址基址基址16016080804040380380editoreditordata1data1……data2data2进程2进程1在分段系统中，实现共享只需在每个进程的段表中为文本编辑程序代码段设置一个段表项，比分页系统简单的多。

齐鲁工业大学 理学院 鹿文鹏1024.4.4 段页式存储管理方式n n分页系统能有效地提高内存利用率，而分段系统则能很好地满足用户需要n n？n n段页式系统齐鲁工业大学 理学院 鹿文鹏1031.基本原理n n将分段和分页原理结合，先将用户程序分成若干个段，再把每个段分成若干个页，并为每一个段赋予一个段名n n段页式系统中，地址结构由段号、段内页号及页内地址三部分组成页齐鲁工业大学 理学院 鹿文鹏104利用段表和页表实现地址映射每个作业一张段表，每段一张页表先查段表，再查该段的页表，才能找到物理块号再将其与页内地址组合齐鲁工业大学 理学院 鹿文鹏1052.地址变换过程1.利用段表始址d0和段号s来求出该段所对应的段表项在段表中的位置，从中得到该段的页表始址d1；2.利用页表始址d1和段内页号P获得对应页的页表项位置，从中读出该页所在的物理块号P’；3.利用块号P’和页内地址d来构成物理地址齐鲁工业大学 理学院 鹿文鹏1072.地址变换过程n n段页式系统中，访问数据需三次访问内存第第一一次次访访问问内内存存中中的的段段表表，，取取得得页页表表始始址址；；第第二二次次访访问问内内存存的的页页表表，，取取得得该该页页的的物物理理块块号号，，并并与与页页内内地地址址一一起起组组成成实实际际的的物物理理地地址址；；第第三三次从物理地址中取出指令或数据。

次从物理地址中取出指令或数据n n为了避免每次均需三次访问，可在地址变换机构中增设一个高速缓冲寄存器，将常用的段表和页表存储在高速缓冲中齐鲁工业大学 理学院 鹿文鹏1084.4 基本分段存储管理方式 小结n n分段存储管理方式的引入 方便用户n n分段系统的基本原理» »分段系统的地址变换过程分段系统的地址变换过程» »段表始址段表始址+ +段号段号->->段的基址段的基址 与与 段内地址段内地址 结合结合->->物理地址物理地址n n信息共享» »分页系统分页系统 与与 分段系统的比较分段系统的比较n n段页式存储管理方式» »段段表表始始址址+ +段段号号->->页页表表始始址址 与与 页页号号 结结合合-> -> 页页面面对对应应的的物物理块号理块号 与与 页内地址页内地址 结合结合->->物理地址物理地址齐鲁工业大学 理学院 鹿文鹏1094.5 虚拟存储器的基本概念n n连续分配方式、基本分页、基本分段存储管理方式均需将一个作业全部装入内存后方能运行，这将导致大作业无法运行n n解决方法：–物理上增加内存容量物理上增加内存容量 有一定限制有一定限制–从从逻逻辑辑上上扩扩充充内内存存容容量量 此此即即虚虚拟拟存存储储器器所所要要解解决的主要问题决的主要问题齐鲁工业大学 理学院 鹿文鹏1104.5 虚拟存储器的基本概念n n4.5.1 虚拟存储器的引入n n4.5.2 虚拟存储器的实现方法n n4.5.3 虚拟存储器的特征齐鲁工业大学 理学院 鹿文鹏1114.5.1 虚拟存储器的引入n n1.常规存储器管理方式的特征–一次性：作业运行前需一次性全部装入内存一次性：作业运行前需一次性全部装入内存» »这可能导致大作业无法装入这可能导致大作业无法装入» »并非全部程序和数据都需用到，一次装入，浪费内存并非全部程序和数据都需用到，一次装入，浪费内存–驻留性：一旦装入便一直驻留内存直至作业结束驻留性：一旦装入便一直驻留内存直至作业结束» »不再运行的程序模块仍将占用宝贵的内存资源不再运行的程序模块仍将占用宝贵的内存资源n n一次性及驻留性是否是必需的？齐鲁工业大学 理学院 鹿文鹏1124.5.1 虚拟存储器的引入n n2.局部性原理n n程序执行时的特点：–程程序序执执行行时时，，除除少少部部分分转转移移和和过过程程调调用用指指令令外外，，大多仍是顺序执行的。

大多仍是顺序执行的–过过程程调调用用虽虽可可导导致致程程序序由由一一区区域域转转至至另另一一区区域域，，但但调调用用深深度度大大多多不不超超过过5 5程程序序在在一一段段时时间间内内都都局局部于这些过程的范围内执行部于这些过程的范围内执行–程序中存在循环结构，它们将多次执行程序中存在循环结构，它们将多次执行–程程序序中中对对数数据据结结构构的的处处理理，，往往往往局局限限于于较较小小的的范范围内围内齐鲁工业大学 理学院 鹿文鹏1134.5.1 虚拟存储器的引入n n2.局部性原理n n局部性的表现：–空空间间局局限限性性一一段段时时间间内内所所访访问问的的地地址址可可能能集集中中于一定的范围之内程序的顺序执行）于一定的范围之内程序的顺序执行）–时时间间局局限限性性某某条条指指令令或或数数据据可可能能被被再再次次执执行行或或访问循环操作）访问循环操作）n n根据局部性原理，程序在运行之前没有必要一次性全部装入，也没必要长期驻留内存齐鲁工业大学 理学院 鹿文鹏1144.5.1 虚拟存储器的引入n n引入虚拟存储器–基基于于局局部部性性原原理理，，程程序序可可仅仅将将需需运运行行的的部部分分页页或或段装入内存便可开始执行。

段装入内存便可开始执行–执执行行中中，，如如果果访访问问的的页页段段已已调调入入内内存存便便可可继继续续；；否否则则，，应应利利用用OSOS提提供供的的请请求求调调页页( (段段) )功功能能将将它它们们调入内存调入内存–若若此此时时内内存存已已满满，，应应利利用用页页( (段段) )置置换换功功能能，，将将暂暂时不用的调出，腾出地方调入需要的页时不用的调出，腾出地方调入需要的页( (段段) )–这这样样，，便便可可使使一一个个大大的的程程序序在在较较小小的的空空间间中中运运行行; ;也可使内存中同时装入更多的进程并发执行也可使内存中同时装入更多的进程并发执行齐鲁工业大学 理学院 鹿文鹏1154.5.1 虚拟存储器的引入n n3.虚拟存储器定义–具具有有请请求求调调入入功功能能和和置置换换功功能能，，能能从从逻逻辑辑上上对对内内存容量进行扩充存容量进行扩充的一种存储系统的一种存储系统–实质：以时间换空间，但时间牺牲不大实质：以时间换空间，但时间牺牲不大–虚拟大小由内存容量和外存容量之和决定虚拟大小由内存容量和外存容量之和决定齐鲁工业大学 理学院 鹿文鹏1164.5.2 虚拟存储器的实现方法n n虚拟存储器是建立在离散分配的存储管理方式基础上的。

n n为什么？–虚拟存储器虚拟存储器 请求调入请求调入 页面转换页面转换–若若采采用用连连续续分分配配方方式式，，一一次次性性将将全全部部数数据据调调入入，，无需虚拟存储无需虚拟存储n n实现的两种方式: 请求分页 请求分段齐鲁工业大学 理学院 鹿文鹏1171.分页请求系统n n在在分分页页系系统统的的基基础础上上，，增增加加了了请请求求调调页页功功能能和和页页面面置置换换功功能能 只只装装入入部部分分页页面面即即可可运运行行，，可可通通过过调调页页和和页页面面置置换换功功能能，，调调入入需需要要的的页页面面，，同同时时将将暂暂不不需要的换出需要的换出n n以页为单位置换以页为单位置换n n需硬件：需硬件：– –请求分页的页表机制请求分页的页表机制 – –缺页中断机构缺页中断机构– –地址变换机构地址变换机构n n需软件：需软件：– –实现请求调页的软件实现请求调页的软件– –实现页面置换的软件实现页面置换的软件齐鲁工业大学 理学院 鹿文鹏1182.请求分段系统n n在在分分段段系系统统的的基基础础上上，，增增加加了了请请求求调调段段及及分分段段置置换换功功能能。

只只装装入入部部分分段段即即可可运运行行，，可可通通过过调调段段和和段段置置换功能，调入需要的段，同时将暂不需要的调出换功能，调入需要的段，同时将暂不需要的调出n n以段为单位置换以段为单位置换n n需硬件：需硬件：– –请求分段的段表结构请求分段的段表结构– –缺段中断机构缺段中断机构– –地址变换机构地址变换机构n n需软件：请求调段和置换软件需软件：请求调段和置换软件齐鲁工业大学 理学院 鹿文鹏1194.5.3 虚拟存储器的特征n n1. 1.离散性：离散分配内存离散性：离散分配内存n n2. 2.多次性：多次装入多次性：多次装入n n3. 3.对换性：允许作业运行中进行换进换出对换性：允许作业运行中进行换进换出n n4. 4.虚拟性：从逻辑上扩充内存虚拟性：从逻辑上扩充内存n n虚虚拟拟性性以以多多次次性性和和对对换换性性为为基基础础，，而而多多次次性性和和对对换换性又必须建立在离散分配的基础上性又必须建立在离散分配的基础上n n最最本本质质的的特特征征是是离离散散性性，，在在此此基基础础上上又又形形成成了了多多次次性性和和对对换换性性，，所所表表现现出出来来的的最最重重要要的的特特征征是是------虚拟性虚拟性. . 齐鲁工业大学 理学院 鹿文鹏1204.5 虚拟存储器 小结n n虚拟存储器的引入–大作业小内存运行大作业小内存运行 局部性原理局部性原理–具有请求调入功能和置换功能，能从逻辑上扩充内存具有请求调入功能和置换功能，能从逻辑上扩充内存n n虚拟存储器的实现方法–分页请求系统分页请求系统请求分段系统请求分段系统n n虚拟存储器的特征–离散性离散性多次性多次性对换性对换性虚拟性虚拟性齐鲁工业大学 理学院 鹿文鹏1214.6 请求分页存储管理方式n n建立在基本分页基础上，为了支持虚拟存储器功能，而增加了请求调页功能和页面置换功能。

n n每次调入和换出的基本单位是固定长度的页齐鲁工业大学 理学院 鹿文鹏1224.6 请求分页存储管理方式n n4.6.1 请求分页中的硬件支持n n4.6.2 内存分配策略和分配算法n n4.6.3 调页策略齐鲁工业大学 理学院 鹿文鹏1234.6.1 请求分页中的硬件支持n n1.页表机制–由于应用程序只是一部分调入内存即只有部分页位于内存中，须在页表中增加若干项，供程序（数据）换进换出时参考页号页号页号页号物理块号物理块号物理块号物理块号状状状状态态态态位位位位P P P P访访访访问问问问字字字字段段段段A A A A修修修修改改改改位位位位M M M M外外外外存存存存地地地地址址址址P:是否已调入内存A:一段时间内使用的次数或多久未使用M:调入内存后是否修改过齐鲁工业大学 理学院 鹿文鹏1244.6.1 请求分页中的硬件支持n n2.缺页中断机构–当当访访问问的的页页不不在在内内存存中中时时便便产产生生缺缺页页中中断断，，请请求求OSOS将其调入将其调入–缺缺页页中中断断具具有有一一般般中中断断的的入入栈栈、、转转中中断断处处理理、、出栈等过程，但又其特殊性：出栈等过程，但又其特殊性：» »在在指指令令执执行行期期间间产产生生和和处处理理中中断断。

发发现现访访问问的的页页不不在在内存即产生；通常是在等到指令执行完毕后内存即产生；通常是在等到指令执行完毕后» »一条指令在执行期间，可能要产生多次中断如图）一条指令在执行期间，可能要产生多次中断如图）齐鲁工业大学 理学院 鹿文鹏125涉及6次缺页中断的指令页面654321齐鲁工业大学 理学院 鹿文鹏1264.6.1 请求分页中的硬件支持n n3. 3.地址变换机构地址变换机构n n大致步骤：大致步骤：– –1)1)在在地地址址变变换换时时，，首首先先检检索索快快表表，，试试图图从从中中找找到到要要访访问问的的页页如如找找到到，，修修改改其其访访问问位位；；对对于于“ “写写” ”指指令令，，还还要要设设置置修改位的值如未找到，则转修改位的值如未找到，则转3 3– –2)2)利利用用页页表表项项中中的的物物理理块块号号和和页页内内地地址址，，形形成成物物理理地地址址，，结束– –3)3)查查找找页页表表，，找找到到页页表表项项后后，，判判断断其其状状态态位位P P，，查查看看该该页页是是否否在在内内存存中中如如果果在在，，则则将将该该页页写写入入快快表表（（若若快快表表已已满满，，则则应应该该先先调调出出某某个个或或某某些些页页表表项项））。

如如果果不不在在，，则则产产生生缺缺页中断，由页中断，由OSOS从外存将该页调入内存返回从外存将该页调入内存返回1 1n n参图参图4-244-24齐鲁工业大学 理学院 鹿文鹏127齐鲁工业大学 理学院 鹿文鹏1284.6.2 内存分配策略和分配算法n n三个问题–最小物理块数的确定最小物理块数的确定–物理块的分配策略物理块的分配策略–物理块的分配算法物理块的分配算法齐鲁工业大学 理学院 鹿文鹏1291.最小物理块数的确定n n最小物理块数是指保证进程正常运行所需的最少物理块数n n与计算机的硬件机构有关，取决于指令的格式、功能和寻址方式–单单地地址址指指令令且且采采用用直直接接寻寻址址方方式式，，最最少少物物理理块块数为数为2 (2 (指令页面指令页面 数据页面数据页面) )–单地址指令且采用间接寻址方式，单地址指令且采用间接寻址方式， 3 3–多字节指令，多字节指令， 6 6 （幻灯片（幻灯片125125页）页）齐鲁工业大学 理学院 鹿文鹏1302.物理块的分配策略n n1)固定分配局部置换n n2)可变分配全局置换n n3)可变分配局部置换齐鲁工业大学 理学院 鹿文鹏1312.物理块的分配策略n n1)固定分配局部置换–每每个个进进程程分分配配固固定定数数目目的的物物理理块块数数，，在在整整个个运运行期间都不改变行期间都不改变–如如果果缺缺页页，，则则只只能能从从该该进进程程在在内内存存的的页页面面中中选选中一页，进行换出操作，然后再调入一页。

中一页，进行换出操作，然后再调入一页–特特点点：：为为每每个个进进程程分分配配多多少少页页是是合合适适的的值值难难以以确定此外，在对换时会浪费比较多的时间此外，在对换时会浪费比较多的时间齐鲁工业大学 理学院 鹿文鹏1322.物理块的分配策略n n2)可变分配全局置换–每每个个进进程程预预先先分分配配一一定定数数目目的的物物理理块块，，同同时时OSOS也也保保持持一一个个空空闲闲物物理理块块队队列列进进程程的的块块数数运运行时可能会有变化）行时可能会有变化）–当当缺缺页页时时，，首首先先将将对对OSOS所所占占有有的的空空闲闲块块进进行行分分配配，，从从而而增增加加各各进进程程的的物物理理块块数数当当OSOS的的空空闲闲块块全全部部用用完完，，将将引引起起换换出出操操作作换换出出的的页页可可能是任一进程的中的一页）能是任一进程的中的一页）齐鲁工业大学 理学院 鹿文鹏1332.物理块的分配策略n n3)可变分配局部置换–思思路路：：先先为为进进程程分分配配部部分分物物理理块块运运行行；；系系统统根根据据缺缺页页率率动动态态调调整整各各进进程程占占有有的的物物理理块块数数目目，，使使其其保保持持在在一一个个比比较较低低的的缺缺页页率率状状态态下下（（轻轻微微缺缺页页时时，，仅仅允允许许从从进进程程自自身身的的页页面面中中选选一一页页换换出出再再换换入入需需要要的的；；只只有有频频繁繁缺缺页页时时，，系系统统才才为为其分配附加的物理块）。

其分配附加的物理块）–特点：使大部分进程可以达到比较近似的性能特点：使大部分进程可以达到比较近似的性能齐鲁工业大学 理学院 鹿文鹏1343.物理块的分配算法－－针对固定分配策略－－针对固定分配策略n n平均分配算法–将物理块平均分配给各进程将物理块平均分配给各进程–未考虑进程本身的大小（页数有多有少）未考虑进程本身的大小（页数有多有少）n n按比例分配算法–根据进程大小按比例分配物理块根据进程大小按比例分配物理块– mm为物理块总数为物理块总数,S,S代表各进程页数之和代表各进程页数之和b b取整，且应大于最小物理块数取整，且应大于最小物理块数n n考虑优先权的分配算法–物物理理块块分分为为两两部部分分：：一一部部分分按按比比例例分分配配；；一一部部分分根据各进程优先权分配根据各进程优先权分配齐鲁工业大学 理学院 鹿文鹏1354.6.3 调页策略n n1.何时调入页面n n2.从何处调入页面n n3.页面调入过程齐鲁工业大学 理学院 鹿文鹏1361.何时调入页面n n根据将进程运行时所缺页面调入内存的时机–预调页策略预调页策略» »将将那那些些预预计计在在不不久久之之后后便便会会被被访访问问的的页页面面预预先先调调入入内内存存» »预测成功率仅约预测成功率仅约50%50%–请求调页策略请求调页策略» »在在运运行行中中，，发发现现要要访访问问的的页页面面不不在在内内存存中中，，便便提提出出请请求，由求，由OSOS将其调入将其调入» »每每次次仅仅能能调调入入一一页页，，增增加加了了磁磁盘盘的的启启动动频频率率，，系系统统开开销较大销较大齐鲁工业大学 理学院 鹿文鹏1372.从何处调入页面n n请请求求分分页页系系统统中中外外存存分分两两个个部部分分：：文文件件区区和和对对换换区区。

一般应当尽量使用对换区来调入页面一般应当尽量使用对换区来调入页面n n对于不同情况，采用不同的策略：对于不同情况，采用不同的策略：– –系系统统有有足足够够的的对对换换空空间间 全全部部由由对对换换区区调调入入，，事事先先需需将将有有数据从文件区拷贝到对换区数据从文件区拷贝到对换区– –系系统统对对换换空空间间不不足足 凡凡是是不不会会被被修修改改的的文文件件都都直直接接从从文文件件区区调调入入，，换换出出时时不不必必再再改改动动文文件件区区；；对对于于需需修修改改的的部部分分，，换出时便调到对换区，需要时再从对换区调入换出时便调到对换区，需要时再从对换区调入– –UNIXUNIX的的调调入入方方式式 未未运运行行过过的的页页面面均均从从文文件件区区调调入入；；对对于于曾曾经经运运行行过过但但又又被被换换出出的的页页面面放放在在对对换换区区，，以以后后从从对对换换区调入齐鲁工业大学 理学院 鹿文鹏1383.页面调入过程进程需要的页面不在内存，引起缺页中断进程需要的页面不在内存，引起缺页中断中断处理程序保留现场环境，转入缺页中断处理程序中断处理程序保留现场环境，转入缺页中断处理程序中断处理程序如何调入页面中断处理程序如何调入页面？？1. 1.中中断断处处理理程程序序查查找找页页表表，，得得到到对对应应的的外外存存物物理理块块号号。

如如果果内内存存有有空空闲闲，，则则启启动动磁磁盘盘操操作作，，将将所所缺缺的的页页面面读读入入，，并修改页表否则，即内存无空闲时，转并修改页表否则，即内存无空闲时，转2 22. 2.执执行行置置换换算算法法，，选选出出要要换换出出的的页页面面（（如如果果该该页页修修改改过过，，应应将将其其写写入入磁磁盘盘））然然后后将将所所缺缺页页调调入入内内存存，，修修改改相相应应表表项，将其状态位设为项，将其状态位设为"1""1"，并放入快表并放入快表3. 3.利用修改后的页表，形成物理地址，访问内存数据利用修改后的页表，形成物理地址，访问内存数据齐鲁工业大学 理学院 鹿文鹏1394.6 请求分页存储管理方式 小结n n请求分页中的硬件支持请求分页中的硬件支持– –页表机制页表机制缺页中断机构缺页中断机构地址变换机构地址变换机构n n内存分配策略和分配算法内存分配策略和分配算法– –最小物理块的确定最小物理块的确定– –物理块的分配策略物理块的分配策略» »固定分配局部置换固定分配局部置换 可变分配全局置换可变分配全局置换 可变分配局部置换可变分配局部置换– –物理块分配算法物理块分配算法» »平均分配平均分配 按比例分配按比例分配 考虑优先权的分配考虑优先权的分配n n调页策略调页策略– –何时调入（预调、请求）何时调入（预调、请求） 从何处调入（对换区）从何处调入（对换区）– –页面调入过程（内存是否有空闲）页面调入过程（内存是否有空闲）齐鲁工业大学 理学院 鹿文鹏1404.7 页面置换算法n n请求分页存储管理方式，若访问的页面不在内存，且内存已无空闲空间时，需首先从内存中调出一页程序或数据，然后调入。

n n需根据一定的算法来确定将哪个页面调出，此算法即页面置换算法，用来选择需调出的页面n n理论目标：减少对换量，具有较低的页面更换频率应优先将那些以后不再访问或较长时间内不再访问的页面调出齐鲁工业大学 理学院 鹿文鹏1414.7 页面置换算法n n4.7.1 最佳置换算法和先进先出置换算法n n4.7.2 最近最久未使用(LRU)置换算法n n4.7.3 Clock置换算法n n4.7.4 其它置换算法具体7种齐鲁工业大学 理学院 鹿文鹏1424.7.1 最佳置换算法和先进先出置换算法n n1.最佳置换算法理论上的算法，其所选择的被淘汰页将是以后永不使用，或者是最长时间内不再被访问的页无法预知页面被访问的次序，无法实现，但可用来评价其它算法齐鲁工业大学 理学院 鹿文鹏1431.最佳置换算法每次选择最长时间内不再访问的页面调出内存 “向后看”缺页次数为6，缺页率6/12＝50%齐鲁工业大学 理学院 鹿文鹏1442. 先进先出(FIFO)页面置换算法n n最早出现的置换算法n n总是淘汰最先进入内存的页面n n实现简单，只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个替换指针（总是指向最老的页面）n n该算法不能保证经常使用的页面不被淘汰，会导致缺页率较高。

齐鲁工业大学 理学院 鹿文鹏1452. 先进先出(FIFO)页面置换算法每次选择最早进入的页面调出内存缺页次数为9，缺页率9/12＝75%齐鲁工业大学 理学院 鹿文鹏1464.7.2 最近最久未使用(LRU)置换算法n n1.算法描述 Least Recently Usedl l根据页面调入内存后的使用情况进行决策，利用“最近的过去”作为“最近的将来”的近似，选择最近最久未使用的页面予以淘汰l l为每个页面设置一个访问字段，记录一个页面自上次被访问以来所经历的时间t齐鲁工业大学 理学院 鹿文鹏1471.LRU算法描述每次选择最近最久未使用的页面调出内存 “向前看”缺页次数为7，缺页率7/12＝58.3%齐鲁工业大学 理学院 鹿文鹏1482.LRU置换算法的硬件支持n nLRU算法为了记录哪一页是最近最久未使用的页面，需要以下两类硬件之一支持–寄存器寄存器–栈栈齐鲁工业大学 理学院 鹿文鹏1491)寄存器n n为每个在内存中的页面配置一个n位移位寄存器， R=Rn-1Rn-2Rn-3…R2R1R0n n定时将所有寄存器右移一位（其值将会减小） ；当进程访问某页时，便将该页相应寄存器的最高位Rn-1置1 （其值将会增大 ） 。

n n最久未访问的页面对应的寄存器的值肯定最小，据此可找到要淘汰的页面齐鲁工业大学 理学院 鹿文鹏1501)寄存器齐鲁工业大学 理学院 鹿文鹏1512)栈n n利用一个特殊的栈来记录页面的使用次序n n当进程访问某页时，将其从栈中移出压入“栈顶”；换出时，将“栈底”换出n n这样可以保证：栈顶总是最新被访问页面的页号，而栈底则是最近最久未使用页面的页号齐鲁工业大学 理学院 鹿文鹏1522)栈n n进程访问页面的序列为：4,7,0,7,1,0,1,2,1,2,6栈栈的的变变化化情情况况访问6时缺页将栈底换出齐鲁工业大学 理学院 鹿文鹏1534.7.3 Clock置换算法n nLRU算法较好，但硬件要求较高，在实际应用中多采用其近似算法，Clock算法是其中一种n n1.简单的Clock置换算法n n2.改进型Clock置换算法齐鲁工业大学 理学院 鹿文鹏1541.简单的Clock置换算法n n内存中所有页面通过链接指针形成一个循环队列n n每页有一个使用访问位(use bit)，若该页被访问则置其use bit=1n n缺页置换时采用一个指针，从当前指针位置开始按地址依次检查各页：–寻找寻找use bit=0use bit=0的页面作为被置换页的页面作为被置换页–指指针针经经过过的的user user bit=1bit=1的的页页都都修修改改user user bit=0,bit=0,暂暂不不换出换出n n最后指针停留在被置换页的下一个页。

齐鲁工业大学 理学院 鹿文鹏1551.简单的Clock置换算法齐鲁工业大学 理学院 鹿文鹏1562.改进型Clock置换算法n n该算法中，除考虑页面的最近使用情况外，还须再增加一个因素－－置换代价n n在页面换出时，如果该页修改过，便须将它重新写回磁盘，相对于未修改过的页面，其置换代价就高齐鲁工业大学 理学院 鹿文鹏1572.改进型Clock置换算法n n选择页面时，尽量选择既未使用又没有修改的页面选择页面时，尽量选择既未使用又没有修改的页面n n页面（访问位页面（访问位A A，修改位，修改位MM）有四种不同情形：）有四种不同情形：ØØ1 1类类(A=0,M=0(A=0,M=0）既未访问，又没有修改，最佳淘汰页）既未访问，又没有修改，最佳淘汰页ØØ2 2类类(A=0,M=1(A=0,M=1））最最近近未未访访问问，，但但已已被被修修改改，，效效率率低低的的淘淘汰页汰页ØØ3 3类类(A=1,M=0(A=1,M=0）被访问，但没有修改，可能再次被访问）被访问，但没有修改，可能再次被访问ØØ4 4类类(A=1,M=1(A=1,M=1）既被访问，又有修改）既被访问，又有修改淘汰页优先选择前两类，实在没有才考虑后两类淘汰页优先选择前两类，实在没有才考虑后两类齐鲁工业大学 理学院 鹿文鹏1582.改进型Clock置换算法n n执行过程：执行过程：ØØ（（1 1））指指针针从从当当前前位位置置开开始始，，开开始始第第一一轮轮扫扫描描循循环环队队列列，，寻寻找找未未访访问问且且没没有有修修改改过过的的页页面面（（第第1 1类类页页面面）），，找到则可换出。

找到则可换出ØØ（（2 2））如如果果找找不不到到，，则则开开始始第第二二轮轮扫扫描描，，寻寻找找未未访访问问但但修修改改过过的的页页面面（（第第2 2类类页页面面）），，并并且且每每经经过过一一个个页页面面时时，，将将其其访访问问位位A A设设置置为为0 0（（未未访访问问））如如果果找找到到一一个第个第2 2类页面，则可换出类页面，则可换出ØØ（（3 3））如如果果仍仍旧旧未未找找到到合合适适的的换换出出页页面面，，则则此此时时指指针针回回到到初初始始位位置置，，且且所所有有页页面面其其访访问问位位A A置置为为0 0再再转转回回（（1 1））继继续续工工作作，，这这时时肯肯定定可可以以经经由由前前两两步步找找到到换换出出页面n n可有效减少磁盘可有效减少磁盘I/OI/O操作，但算法本身开销有所增大操作，但算法本身开销有所增大齐鲁工业大学 理学院 鹿文鹏1594.7.4 其它置换算法n n1.最少使用(LFU: Least Frequently Used)置换算法n n2.页 面 缓 冲 算 法 (PBA: Page Buffering Algorithm)齐鲁工业大学 理学院 鹿文鹏1601.最少使用置换算法LFUn n目目的的：：选选择择到到当当前前时时间间为为止止被被访访问问次次数数最最少少的的页页面面被置换；被置换；n n实实现现方方法法1 1：：每每页页设设置置访访问问计计数数器器，，每每当当页页面面被被访访问问时时，，该该页页面面的的访访问问计计数数器器加加1 1；；发发生生缺缺页页中中断断时时，，淘淘汰汰计计数数值值最最小小的的页页面面；；因因页页面面访访问问次次数数可可能能极极多多，，要求计数器容量极大，此法不可行。

要求计数器容量极大，此法不可行n n实实现现方方法法2 2：：类类似似于于LRULRU算算法法，，每每个个页页面面设设立立n n位位移移位位寄寄存存器器：：被被访访问问时时左左边边最最高高位位置置1 1，，定定期期右右移移并并且且最最高高位位补补0 0，，这这样样，，在在最最近近一一段段时时间间内内时时用用最最少少的页面将是的页面将是ΣRiΣRi最小的页最小的页齐鲁工业大学 理学院 鹿文鹏1612.页面缓冲算法PBAn n对FIFO算法的发展，通过被置换页面的缓冲，有机会找回刚被置换的页面；n n被置换页面的选择和处理：由操作系统中专门的页面置换进程，用FIFO算法选择被置换页，把被置换的页面放入内存中的两个链表（空闲页面链表和已修改页面链表）之一：–如如果果页页面面未未被被修修改改，，就就将将其其归归入入到到空空闲闲页页面面链链表的末尾表的末尾–否则将其归入到已修改页面链表否则将其归入到已修改页面链表齐鲁工业大学 理学院 鹿文鹏1622.页面缓冲算法n n这种算法被换出的页面，链接在空闲页面链表和已修改页面链表中，仍留在内存中当进程再访问时，只需花费较小的开销当修改的页面数目达到一定值时，再将它们成批回写到磁盘上。

从而显著减少磁盘的I/O操作次数齐鲁工业大学 理学院 鹿文鹏1634.7 页面置换算法　小结n n最佳置换算法最佳置换算法– –淘汰以后永不再使用或最长时间内不再使用的页淘汰以后永不再使用或最长时间内不再使用的页n n先进先出页面置换算法先进先出页面置换算法– –淘汰最先进入内存的页面　　向前看淘汰最先进入内存的页面　　向前看n n最近最久未使用置换算法最近最久未使用置换算法– –选择最近最久未使用的页选择最近最久未使用的页– –需硬件支持：移位寄存器　栈需硬件支持：移位寄存器　栈n nClockClock置换算法置换算法 　　简单的　改进的　　简单的　改进的n n最少使用置换算法最少使用置换算法n n页面缓冲算法页面缓冲算法齐鲁工业大学 理学院 鹿文鹏1644.8 请求分段存储管理方式n n请求分页系统建立的虚拟存储器，是以页面为单位进行换入、换出操作的n n在请求分段系统中实现的虚拟存储器，以分段为单位进行换入和换出n n程序在运行之前，只需要装入必要的若干个分段即可运行当访问的分段不在内存时，可由OS将所缺少的段调入内存ØØ4.8.1 请求分段中的硬件支持ØØ4.8.2 分段的共享与保护齐鲁工业大学 理学院 鹿文鹏1654.8.1 请求分段中的硬件支持n n类似请求分页系统，硬件支持需:ØØ段表机制ØØ缺段中断机构ØØ地址变换机构齐鲁工业大学 理学院 鹿文鹏1661.段表机制n n存取方式：标记本段存取属性(读写执行)n n访问字段A：记录本段使用的频繁程度n n修改位：是否在调入内存后做过修改n n存在位：本段是否装入内存n n增补位：该段是否动态增长过，在请求页式中没有该位n n外存地址：本段在外存中的起始地址齐鲁工业大学 理学院 鹿文鹏1672.缺段中断机构n n发发现现所所要要访访问问的的段段未未调调入入内内存存时时，，由由缺缺段段中中断断机机构构产产生生一一缺缺段段中中断断信信号号，，进进入入OSOS后后由由缺缺段段中中断断处处理理程序将所需段调入内存。

程序将所需段调入内存n n特特点点：：可可在在指指令令的的执执行行期期间间产产生生和和处处理理中中断断；；一一条条指令执行时，可产生多次中断类似缺页中断）指令执行时，可产生多次中断类似缺页中断）n n独处之处：独处之处：– –指令和操作数必定不会跨越在段边界上指令和操作数必定不会跨越在段边界上（段是信息逻辑单位）（段是信息逻辑单位）– –调入一个段可能要淘汰几个内存中的段调入一个段可能要淘汰几个内存中的段（段长不一致）（段长不一致）– –由于段的长度是不固定的，处理比缺页系统复杂由于段的长度是不固定的，处理比缺页系统复杂齐鲁工业大学 理学院 鹿文鹏1682.缺段中断机构齐鲁工业大学 理学院 鹿文鹏1693.地址变换机构n n若发现所要访问的段不在内存，需先将所缺的段调入内存，并修改段表，然后才能再利用段表进行地址变换齐鲁工业大学 理学院 鹿文鹏1703.地址变换机构S:段号W:段内地址段齐鲁工业大学 理学院 鹿文鹏1714.8.2 分段的共享和保护n n1.共享段表n n2.共享段的分配与回收n n3.分段保护齐鲁工业大学 理学院 鹿文鹏1721.共享段表n n为实现段的共享，配置一张共享段表，所有的共享段均占有一表项。

n n表项中记录了共享段的段名、段长等信息，并记录有共享此分段的每个进程的情况段名段名段名段名段长段长段长段长内存地址内存地址内存地址内存地址状态状态状态状态外存地址外存地址外存地址外存地址共享进程计数共享进程计数共享进程计数共享进程计数状态状态状态状态进程名进程名进程名进程名进程号进程号进程号进程号段号段号段号段号存取控制存取控制存取控制存取控制………………齐鲁工业大学 理学院 鹿文鹏1731.共享段表n n部分新增段表项说明：ØØ1.共享进程计数记录了多少个进程在共享该分段仅当所有共享该段的进程均不需要它时，才能由系统回收该段占用的内存ØØ2.存取控制字段对于共享段，不同进程应该赋予不同的存取权限ØØ3.段号不同的进程可以使用不同的段号来访问相同的共享段齐鲁工业大学 理学院 鹿文鹏1742.共享段的分配与回收n n1)分配ØØa.第一个请求的进程，由系统分配一物理区，调入共享段；同时将该区始址存入请求进程的段表中；还须在共享段表中增加一表项，填写有关数据，并置count=1ØØb.以后的请求进程，在自己段表中增加一项，填入共享段的物理地址；同时在共享段表项中，填上请求进程的信息，并做count = count+1齐鲁工业大学 理学院 鹿文鹏1752.共享段的分配与回收n n2)共享段的回收ØØ共享此段的进程不需要该段时，应将其释放，撤消其段表中关于该共享段的数据项，同时做count = count –1ØØ如果count = 0，则将该共享段回收；否则只是取消该进程在共享段表中的有关信息齐鲁工业大学 理学院 鹿文鹏1763.分段保护n n1)越界检查n n在进行存储访问时，要将逻辑地址的段号与段表长度进行比较，如果超出则发生越界中断信号；其次，将段内地址与段表中该段的长度进行比较，如果有效才进行转换，否则产生越界中断信号。

齐鲁工业大学 理学院 鹿文鹏1773.分段保护n n2)存取控制检查n n在段表的每个表项中，设置一个“存取控制”字段，用于规定对该段的访问权限通常的访问方式有：ØØ只读：只允许用户对该段内信息进行读操作ØØ只执行：用户可以执行该段程序，但是即不准读也不准写ØØ读/写：允许进程对该段进行读写访问齐鲁工业大学 理学院 鹿文鹏1783.分段保护n n3)环保护机构n n思想：将所有的程序分成不同的级别，分别放置在不同的环上内环（编号小，在内侧）的程序具有高优先权，外环的程序优先权低n n操作系统核心安排在0环内；重要程序和操作系统服务安排在中间环；一般应用程序安排在外环齐鲁工业大学 理学院 鹿文鹏179环保护机构n n一个程序可以直接访问在相同环或低优先级环（比自身相对靠外的环）上的数据 内环可访问外环数据内环可访问外环数据内环可访问外环数据内环可访问外环数据ØØ一个程序访问高优先级（比自己靠内的环）时，通过系统调用方式实现 外环可请求内环服务外环可请求内环服务外环可请求内环服务外环可请求内环服务齐鲁工业大学 理学院 鹿文鹏180环保护机构内环可访问外环数据外环可请求内环服务齐鲁工业大学 理学院 鹿文鹏1814.8 请求分段存储管理方式 小结n n请求分段中的硬件支持–段表机制段表机制缺段中断机构缺段中断机构地址变换机构地址变换机构n n分段的共享与保护–共享段表（共享进程计数、存取控制字段、段号）共享段表（共享进程计数、存取控制字段、段号）–共享段的分配与回收共享段的分配与回收n n分段保护–越界检查越界检查–存取控制检查存取控制检查–环保护机构环保护机构齐鲁工业大学 理学院 鹿文鹏182第四章 存储器管理n n4.1 程序的装入和链接 n n4.2 连续分配方式n n4.3 基本分页存储管理方式n n4.4 基本分段存储管理方式n n4.5 虚拟存储器的基本概念n n4.6 请求分页存储管理方式n n4.7 页面置换算法n n4.8 请求分段存储管理方式齐鲁工业大学 理学院 鹿文鹏183作业n n1.图4-26 图4-27 图4-28 图4-30n n2.P143 26。