《三章节存储系统》由会员分享，可在线阅读，更多相关《三章节存储系统（104页珍藏版）》请在金锄头文库上搜索。
1、第三章第三章 存储系统存储系统串议罪残畸琉少绽庙鹃黍股靳你姆扼药讽贤添凛托鳞叮阔扭寸斩匀沥柯驻三章节存储系统三章节存储系统一一 存储器与存储系统存储器与存储系统1.1.存储器存储器存储器存储器存储器存储器：计算机核心部件。：计算机核心部件。存储器性能指标存储器性能指标：容量、速度、价格：容量、速度、价格q存储器容量存储器容量SmSm=Wl mW:单体存储器的字长单体存储器的字长l :单体存储器的字数单体存储器的字数M:并行工作的存储体的个数并行工作的存储体的个数q存储器速度（存取时间存储器速度（存取时间TA，访问周期，访问周期Tm，频带宽度，频带宽度Bm）频带宽度频带宽度Bm:存储器被访问时，
2、可以提供的数据传送速存储器被访问时，可以提供的数据传送速率，单位：率，单位：KB/S或者或者MB/S。单体存储器单体存储器Bm=W/Tm（理想情况）（理想情况）m个存储器并行工作时，个存储器并行工作时， Bm=Wm/Tm（理想情况）（理想情况）险籽阔拧痴健典颁贤计谁潍耳用贬哩赦舔哨燃朴照厉闯冷忽必竭向刻赴智三章节存储系统三章节存储系统q存储器价格存储器价格Cm单位容量的价钱，单位单位容量的价钱，单位/b对存储器要求：对存储器要求：“容量大、速度快、价格低容量大、速度快、价格低”怎样达到要求？怎样达到要求？1)引入并行和重叠技术，构成并行主存系统，如单体引入并行和重叠技术，构成并行主存系统，如单
3、体多字存储器、多体交叉存储器。多字存储器、多体交叉存储器。2)改善存储器系统结构，发展存储体系（或称存储系改善存储器系统结构，发展存储体系（或称存储系统）。统）。杖沁嫌吮胚世漫槐莆泉胖拂彭崭却该独沉庆熊辽籽宗捣磅雷孙睹高贷仁强三章节存储系统三章节存储系统2.2.存储系统存储系统存储系统存储系统存储体系（存储系统、存储层次）：存储体系（存储系统、存储层次）：1)由多种不同的存储器构成由多种不同的存储器构成2)由硬件、软件或者硬件由硬件、软件或者硬件+软件相结合完成程序定位，使之成为一个软件相结合完成程序定位，使之成为一个整体。整体。CPUM1M2Mn存储系统Ci Ci+1Ti Ti+1 Si C
4、2T1 T2 S1 S2甄肉哼僵配塌沛蔫柑圆蛀恩腕俏插基制翠蚊饯沫丸至蒋悉蹭仗耕氢峙柴表三章节存储系统三章节存储系统平均位价格平均位价格C当当S1S2时，时，CC2访问周期访问周期T命中率命中率H在在M1中访问到的概率。中访问到的概率。N1：M1访问次数访问次数N2：M2访问次数访问次数等效访问周期等效访问周期TTHT1(1H)T2当命中率当命中率H1时，时，TT1倒旧碍舶尧寻反烁毅志裂宝兢碴汞城埔怜凄坊施堡尾伦董刃篙鬃菇颤不浙三章节存储系统三章节存储系统访问效率访问效率e ：这是一个相对值，便于不同系统之间的比较。这是一个相对值，便于不同系统之间的比较。提高存储系统速度条件：提高存储系统速度
5、条件：q提高命中率提高命中率Hq两个存储器的速度不要相差太大两个存储器的速度不要相差太大厘赚申帮打孙骨制攀挞首跋矾郸利州橱蕉匠拧倍颧文桶驮眼盯叼托胀声蜡三章节存储系统三章节存储系统访问效率e受H和r的影响（参见右图）：鹰途虫擦遭浊佐天傈襟绰猫舷灭亥京兴峰汕场孟颂便译袭侧仍庇妻咆沟丑三章节存储系统三章节存储系统Cache预取技术对命中率的提高作用预取技术对命中率的提高作用 这这里里所所说说的的“预预取取”技技术术，并并不不是是根根据据对对程程序序执执行行的的未未来来趋趋势势进进行行猜猜测测以以提提前前调调入入数数据据，而而仅仅仅仅是是在在发发生生不不命命中中情情况况时时把把调调入入1个个数数据据
6、字字改改为为调调入入1个个数数据据块块的的策策略略。根根据据程程序序的的局局部部性性原原理理，在在当当前前使使用用数数据据周周围围的的其其它它数数据据未未来来被被使使用用的的几几率率大大于于远远处处数数据据，所所以以该该数数据据块块中中被被提提前前调调入入的的邻近数据很可能成为未来的命中点，从而提高命中率。邻近数据很可能成为未来的命中点，从而提高命中率。 采用这种预取技术后新的命中率为：采用这种预取技术后新的命中率为：其中：其中：H 原命中率（即按照不命中时取入原命中率（即按照不命中时取入1字的策略）字的策略） H 新命中率（即按照不命中时取入新命中率（即按照不命中时取入1块的策略）块的策略）
7、 n 每块数据平均被访问次数。每块数据平均被访问次数。紧梢牺丁涌扣剩抱摄搏邹霉儡洱有魏李喘忱彪驻霞肚右忍忠饵愚烂船斜的三章节存储系统三章节存储系统 按照定义，原不命中率按照定义，原不命中率 ，新不命中率，新不命中率 ，并且有，并且有 。由于预取使得每块数据中的不命中次数由由于预取使得每块数据中的不命中次数由n次降低到次降低到1次，所以有次，所以有 。此式可改写为。此式可改写为 ，整理得整理得 。H的推导：的推导：偏革增谆撕碟圆场屋咳欧瓷胀啼铬朱郧挺弗肉逻阳养投韩静香芽祖由泛查三章节存储系统三章节存储系统加速比加速比加速比加速比 Cache-主存层次的主要作用是提高访问速度，系统的等效速度应高主
8、存层次的主要作用是提高访问速度，系统的等效速度应高于主存（即于主存（即M2）的原有速度，两个速度之比称为加速比。）的原有速度，两个速度之比称为加速比。祭毕陇秀班蒸慷洽涛莲抨按破踩恫某迁切愿味歼冬晰砧敷蹄邀挂巾咋峙祁三章节存储系统三章节存储系统 例：有一个例：有一个109字节的程序被字节的程序被装入右图所示的装入右图所示的M3准备运行。准备运行。假定指令字长假定指令字长=1字节，程序字节，程序中无转移指令和内存读中无转移指令和内存读/写指写指令。令。 (1)按图按图(a)求求T和和e增加中间层对增加中间层对e的影响的影响(2)按图按图(b)推导三层体系的推导三层体系的T公式公式(3)按图按图(b
9、)求求T和和e(4)比较比较(1)(3)结果，有何结论？结果，有何结论？103B109B103B109BM1M3M2M1M3T1=1usTB3=100usTB2=10us106B(a)(b)剁痪扫赐痰序润纶陆负渺聚薛法间瑚蠢帧受传畏鬃睹运揪沁逗韭苦米裕叠三章节存储系统三章节存储系统煮魏运诛藩姆需绿跺挞簇物字三对告楚驶溶啮捐忙潍袍涪帘辑颐戴豢腰塑三章节存储系统三章节存储系统予殿床蜒疙事斥搀病檄搐聋椿夺匠衬绸丁咒蘑饿窒卵荷仪活酚酿讲填卑丁三章节存储系统三章节存储系统并行存储器并行存储器 并并行行存存储储器器技技术术可可以以提提高高主主存存系系统统的的整整体体等等效效速速度度，实实际际应应用用中中，
10、常常将将它它与与存存储储层层次次技技术术组组合合使使用用，可可以以互互为为补补充充，获得很高的性能。获得很高的性能。 并并行行存存储储器器技技术术的的基基本本思思想想是是用用多多个个独独立立的的存存储储部部件件组组成成主主存存系系统统，让让它它们们并并行行工工作作，在在一一个个存存储储周周期期内内可可以以访访问问到多个数据，从而实现较高的存取流量。到多个数据，从而实现较高的存取流量。 并并行行存存储储器器包包括括多多种种类类型型，我我们们仅仅介介绍绍提提高高访访问问速速度度效效果最显著的果最显著的低位交叉访问低位交叉访问这一种。这一种。突悍摩岳描执缠觅板养怨吩娇孰扳住望尾海造涅绞凭掀霜薪蕉惩翠
11、源揩缄三章节存储系统三章节存储系统低位交叉访问并行存储器的结构低位交叉访问并行存储器的结构 它由它由n个存储体组成（一般个存储体组成（一般n为为2的整次幂），每个体均有的整次幂），每个体均有独立的地址译码器和数据缓冲器，以主存地址低位字段（最低独立的地址译码器和数据缓冲器，以主存地址低位字段（最低的的log2n位）作为体选译码信号，而剩下的高位字段则是体内位）作为体选译码信号，而剩下的高位字段则是体内地址。如图所示（设地址。如图所示（设 n = 4）。）。嘻芦督君眩咙枣注藕橱俞搜医秤粹榔烧寿亦古惋媒蝎坡汪尸捌莹圾柜疙椰三章节存储系统三章节存储系统主存地址与结构参数的换算主存地址与结构参数的换算
12、其中：n 存储体个数，A 主存地址， j 体内地址， k 体序号（ k = 0，1，2，n-1 ） 例3.1 已知 n = 4，问主存地址13是在几号体的几号单元？解： 由于 n = 4，体选译码信号使用主存地址的最低 log2n = 2位，所以地址13（其二进制为1101B）对应的体号k = 1（即01B）、体内地址j = 3（即11B），也就是说，地址13位于1号体的3号单元（参看前一页插图）。根据上式，所有k值（即体号）相同的地址之间均相差n的整倍数，称之为“模n同余”。龋玖衬厄便鼎改惕湾戏奔慷首鉴僚辐至碎未宦碗尘桂姻竿聪摆忱涩讼捕凛三章节存储系统三章节存储系统低位交叉访问并行存储器的加
13、速机理低位交叉访问并行存储器的加速机理 我们衡量存储器件速度的常用指标是存储周期Tm，它是同一存储单元连续两次启动的最小时间间隔，数值越小表明存储器件速度越快。 传统存储系统只有一套地址译码器和数据缓冲器，所以各单元必须串行工作，也就是说每个Tm周期内至多只能完成一次访问。 由多个存储体构成的并行存储器中，各个存储体都有独立的地址译码器和数据缓冲器，它们可以并行工作，使得一个Tm周期内可完成多次访问，相当于加速了多倍。最好情况下一个Tm周期内可完成n次访问。 当前Tm周期中只要发现有一个新的访问地址与前面地址属于同一个存储体，该地址及其后面的地址就会被阻塞（称为访存冲突）,留到下一个Tm周期访
14、问。 机器地址序列常常具有顺序性，按照低位交叉的规律分配地址可使相继出现的地址落在相同存储体的概率降到最低（参见上图）。 考虑到地址总线与数据总线的拥挤问题，一个Tm周期里发送的多个访问请求最好彼此错开Tm/n时间，如P140图3.11所示，否则实现的复杂度会增加。欧瞅所坝潦母阀绊糖帖会月毫弟年枷舅淆巍负轮弊达抵打陷奶攫藉嚷忻斑三章节存储系统三章节存储系统计算平均加速倍数计算平均加速倍数1.只考虑取指地址序列（假设地只考虑取指地址序列（假设地址顺序递增，直至出现一条转移址顺序递增，直至出现一条转移指令）：指令）： 其中g是指令序列中出现转移指令的概率。此公式在右图中用绿线表示。2.只考虑取数地
15、址序列（假设地址只考虑取数地址序列（假设地址完全随机）完全随机）此公式在右图中用红线表示。 K g=010.0 g=0.24.463.682.00 g=0.51.00 g=1 0 1 10 n耽渔虎层肥免煽荷刚霓综尊厨嗓礼陋婆篓掌华楔璃诌涪卤豆衙释薄拭荆涣三章节存储系统三章节存储系统例题：例题：P203，题，题5啄蹈野渺磺痒各匀誊贫坛翰忘缠亡碗汐持您到肆兹沛韩撤涉搂呻碟捧凑裁三章节存储系统三章节存储系统地址映象与变换地址映象与变换基本术语：基本术语：基本术语：基本术语：逻逻逻逻辑辑辑辑地地地地址址址址（相相相相对对对对地地地地址址址址、虚虚虚虚地地地地址址址址）：程程序序员员在在编编写写和和编
16、编译译一一个个程程序序模模块块时时分分配配指指令令和和数数据据的的空空间间单单位位序序号号，总总是是从从0开开始始（可可以以按按字字节节编编址址、按按CPU字编址等）。逻辑地址的取值范围称为逻辑地址空间、虚空间或虚存。字编址等）。逻辑地址的取值范围称为逻辑地址空间、虚空间或虚存。物物物物理理理理地地地地址址址址（又又又又称称称称为为为为绝绝绝绝对对对对地地地地址址址址、实实实实地地地地址址址址）：任任一一级级存存储储器器为为全全部部存存储储单单元分配的序号。物理地址的取值范围称为物理地址空间、实空间或实存。元分配的序号。物理地址的取值范围称为物理地址空间、实空间或实存。从从从从MM1 1到到到
17、到MMn n各各各各层层层层都都都都有有有有自自自自己己己己的的的的物物物物理理理理地地地地址址址址空空空空间间间间，而而而而对对对对当当当当前前前前执执执执行行行行的的的的程程程程序序序序模块来说，逻辑地址空间只有一个。模块来说，逻辑地址空间只有一个。模块来说，逻辑地址空间只有一个。模块来说，逻辑地址空间只有一个。地址映象：地址映象：地址映象：地址映象：虚页集合与实页集合的对应规则，或者说是约束关系。虚页集合与实页集合的对应规则，或者说是约束关系。地址变换（虚实变换）：地址变换（虚实变换）：地址变换（虚实变换）：地址变换（虚实变换）：逻辑地址到物理地址的变换过程或者算法。逻辑地址到物理地址的
18、变换过程或者算法。页失效：页失效：页失效：页失效：当前被访问存储级中没有所需的信息，也就是不命中现象。当前被访问存储级中没有所需的信息，也就是不命中现象。实页争用（实页冲突）：实页争用（实页冲突）：实页争用（实页冲突）：实页争用（实页冲突）：虚页调入时，根据地址映象方式划定的实空间虚页调入时，根据地址映象方式划定的实空间范围内已没有空闲实页的状况。范围内已没有空闲实页的状况。圣氮蚜娱霉怕疙数贴严湖间录林粮翻慧挝劝烘襟捍呕强挥繁套赤倘稍钥蕉三章节存储系统三章节存储系统4种常见的地址映象方式种常见的地址映象方式1 1、全相联、全相联、全相联、全相联 全全相相联联就就是是无无约约束束对对应应，或或者
19、者说说是是一一个个完完全全关关系系，意意思思就就是是一一个个虚虚页页可可以以调调入入任任何何一一个个实实页页。这这种种关关系系可可用用如如下下示示意意图图表示。表示。 睬池脖坑诗灯瞳凡太霍并棱浓尾配校牛惮庚韩遁馁菱遮故央彼鼎茁颤啦苞三章节存储系统三章节存储系统 全相联的虚实变换信息完全来自于变换表，查表过程全相联的虚实变换信息完全来自于变换表，查表过程全相联的虚实变换信息完全来自于变换表，查表过程全相联的虚实变换信息完全来自于变换表，查表过程如下图所示。如下图所示。如下图所示。如下图所示。苗消您蚌碾砷超精琵蹄氯湾忙阀剧菇计奎肿石个嗡患贰梨靳联肠唉盟硒喷三章节存储系统三章节存储系统全相联映象方式
20、特点：全相联映象方式特点：全相联映象方式特点：全相联映象方式特点：1)全相联映象方式使虚页调入有最大的选择范围，发全相联映象方式使虚页调入有最大的选择范围，发生实页争用的可能性最小，调入生实页争用的可能性最小，调入/调出的操作开销也调出的操作开销也最少，有利于命中率提高。最少，有利于命中率提高。2)但这种方式的页表占用空间和查表时间开销都比较但这种方式的页表占用空间和查表时间开销都比较大大,也就是说实现成本比较高，在命中情况下花费在也就是说实现成本比较高，在命中情况下花费在虚实变换上的时间也比较多。虚实变换上的时间也比较多。3)由于页表必须常驻在实存中，而主存由于页表必须常驻在实存中，而主存-
21、辅存层次的实辅存层次的实存（即主存）相对存（即主存）相对Cache-主存层次的实存（即主存层次的实存（即Cache存储器）要低廉一些，所以全相联映象方式存储器）要低廉一些，所以全相联映象方式一般用于主存一般用于主存-辅存层次。辅存层次。猾忆支揍寻腿念猴诞蜘樱砖药殿战它稍季讯砂芦镇嚏暖炊押棍补甸音园显三章节存储系统三章节存储系统直接相联直接相联 直直接接相相联联是是一一种种最最强强的的约约束束关关系系，它它规规定定每每个个虚虚页页只只对对应应唯唯一一的的实实页页。为为了了便便于于虚虚实实变变换换，用用求求模模运运算算作作为为变变换换关关系系式式：将将虚虚页页号号对对实实页页总总数数求求模模得得到
22、到实实页页号号。实实现现起起来来非非常常简简单单，因因为为在在二二进进制制中中，任任何何数数X对对2的的整整次次幂幂n求求模模等等价价于于截截取取X的的最最低低log2n位，如下页示意图所示。位，如下页示意图所示。趴锣唐蝶秸谜始脸硬受澜掖祭嘱炒考劲喳行弧悄若妊冷然谱忽椒赂九炼噎三章节存储系统三章节存储系统直接相联的地址映象方式与地址变换原理直接相联的地址映象方式与地址变换原理直接相联的地址映象方式与地址变换原理直接相联的地址映象方式与地址变换原理冻份客灸舆堡他琼辗豁身疤兽弥鄂泼耐腿艰疆猿粟咏蒲视麓榨昧锋皱阻浮三章节存储系统三章节存储系统例例3.3 已知虚页号已知虚页号 = 7，实页总数，实页总
23、数 = 4，用直接相联求实页号。，用直接相联求实页号。解：解： 可用十进制形式求：可用十进制形式求：7 mod 4 = 3； 也可用二进制形式求：由于也可用二进制形式求：由于n = 4，所以，所以log2n = 2，取，取7的二进制的二进制形式形式111B的最低的最低2位，得位，得11B，即，即3。尺诺贡冒援陨登敲袋在谅了酌关馅丢纵牡侠晃布茧鼎搁顿取于奇恭癸挣炯三章节存储系统三章节存储系统直接相联映象方式特点：直接相联映象方式特点：直接相联映象方式特点：直接相联映象方式特点：1)直接相联映象方式不需要借助页表来进行虚实变换，直接相联映象方式不需要借助页表来进行虚实变换，显然大大节省了相应的空间
24、与时间（当然页表中的装显然大大节省了相应的空间与时间（当然页表中的装入位和修改位还得保留）。入位和修改位还得保留）。2)由于每个虚页的选择范围太小，实页争用的发生频率由于每个虚页的选择范围太小，实页争用的发生频率较高，常出现明明实存有空闲空间却不得不调出一个较高，常出现明明实存有空闲空间却不得不调出一个现有虚页以腾出所在实页的情况，这使系统的命中率现有虚页以腾出所在实页的情况，这使系统的命中率和运行效率大大下降。和运行效率大大下降。 这种映象方式主要用于一些对实存价格非常敏感的这种映象方式主要用于一些对实存价格非常敏感的Cache-主存层次。主存层次。仪弗漾记溶董彦坚疵贞汐随它窝羚拉阀容港晤肮
25、扬氨醉无阿拄妈臀抉缝醉三章节存储系统三章节存储系统组相联组相联 组组相相联联映映象象方方式式是是全全相相联联与与直直接接相相联联的的一一个个折折中中方方案案，性性能也是二者的折中。能也是二者的折中。 具具体体做做法法是是先先将将实实存存分分组组，每每组组内内有有若若干干实实页页，然然后后将将虚虚存存空空间间也也以以同同样样大大小小分分组组。所所有有虚虚组组按按照照直直接接相相联联方方式式映映射射到到实实组组集集合合，对对应应的的虚虚实实组组之之间间各各页页则则用用全全相相联联映映射射，如如下下页页示示意图意图(a)、(b)所示（设实组数为所示（设实组数为2）。）。诅滤用情巳飘曹槛段敛桩该搓帚词
26、漂浴新辱译梆纪鄙速尉仕虏硷签浆眶矢三章节存储系统三章节存储系统组相联的地址映象方式与地址变换原理组相联的地址映象方式与地址变换原理工骤瘁猛谦涎猴桃昨烷湍芳锐藻瑚纱积赛付桐酚鲤代悯晤雍泊瘩疫逗乡膏三章节存储系统三章节存储系统 由于包含了两层不同的映射关系，页表须按虚组划分成许由于包含了两层不同的映射关系，页表须按虚组划分成许多子表。在虚实变换时，首先根据虚页号所在的虚组号，通过多子表。在虚实变换时，首先根据虚页号所在的虚组号，通过求模运算确定实组号，再按虚组号在相应的子表内读出组内页求模运算确定实组号，再按虚组号在相应的子表内读出组内页号，拼接在一起就是实页号。简记为号，拼接在一起就是实页号。简
27、记为“组号计算、组内查表组号计算、组内查表”。如下图所示。如下图所示。伦够圭肩忿浅掷忿尽质蹦胆溢丛程既界疽坛盛沫称萨右孟蚤翔嫂涟廖设叔三章节存储系统三章节存储系统组相联的地址映象方式与地址变换原理组相联的地址映象方式与地址变换原理奖掖诌瞻晋睁荤馒邑沧旁勺椿吃喜跨侣采册祈歧溜唁嗅讼趣拴缝呕翅破刊三章节存储系统三章节存储系统组相联映象方式特点：组相联映象方式特点：组相联映象方式特点：组相联映象方式特点： 采用组相联映象方式时，每个虚页在对应实组范围内有采用组相联映象方式时，每个虚页在对应实组范围内有若干映象实页可供选择，实页争用的发生频率比直接相联要若干映象实页可供选择，实页争用的发生频率比直接相
28、联要低；另一方面，由于页表内原来存放的实页号改成存组内页低；另一方面，由于页表内原来存放的实页号改成存组内页号，省略了实组号字段，所以页表占用空间也减少了。当然号，省略了实组号字段，所以页表占用空间也减少了。当然这两方面优点是互相抵触的：组内页数越多，实存空间划分这两方面优点是互相抵触的：组内页数越多，实存空间划分的组数就越少，实组号字段所占位数也少，这时改善实页争的组数就越少，实组号字段所占位数也少，这时改善实页争用现象的效果较好，而节省页表空间的效果较差，反之亦然。用现象的效果较好，而节省页表空间的效果较差，反之亦然。实际使用中可根据性能要求选取合适参数。实际使用中可根据性能要求选取合适参
29、数。 这种映象方式性价比较好，在这种映象方式性价比较好，在Cache-主存层次中被普遍主存层次中被普遍使用。使用。遣柳衰冶惫膘挫团氯一评裁犯雨球函净狠后宗伤吧材隋陪府弄欠胆褪定前三章节存储系统三章节存储系统段相联段相联 段段相相联联映映象象方方式式也也是是全全相相联联与与直直接接相相联联的的一一个个折折中中方方案案。它它的的分分段段方方法法与与组组相相联联相相同同，不不同同的的是是所所有有虚虚段段按按照照全全相相联联方方式式映映射射到到实实段段集集合合，对对应应的的虚虚实实段段之之间间各各页页则则用用直直接接相相联联映映射射（因因为为虚虚实实段段大大小小相相同同，所所以以实实际际上上是是一一一
30、一对对应应），如如下下页页示示意图所示（设实段数为意图所示（设实段数为2）。）。 绑溜偏促恋涩杰检瓢贵湿裙恕某翟谜绎莱振度勤炭绿韵嚣育雁孽罕翟趋麦三章节存储系统三章节存储系统段相联的地址映象方式与地址变换原理段相联的地址映象方式与地址变换原理泰合斧毅钻护炕卸尝啦市童家澡誊燕碉让溉贿嘲啊牢凝亏磷幕傅精丰藩奥三章节存储系统三章节存储系统 段相联的虚实变换与组相联类似，不过可以通过计算来段相联的虚实变换与组相联类似，不过可以通过计算来确定的部分不是在段外，而是在段内，即页表内只储存各虚确定的部分不是在段外，而是在段内，即页表内只储存各虚页对应的实段号，段内页号则从虚页号中简单直接复制，拼页对应的实段
31、号，段内页号则从虚页号中简单直接复制，拼接在一起就是实页号，简记为接在一起就是实页号，简记为“段号查表、段内复制段号查表、段内复制”。如。如如下页示意图所示。如下页示意图所示。 鬃釉耸班嚏葱匿惋谤侩贩恶饶砖冠谬遁办躯践娱诣枫梯玖烁痰疯拢约流莲三章节存储系统三章节存储系统段相联的地址映象方式与地址变换原理段相联的地址映象方式与地址变换原理含今跳工仁忧壳索柿挑辗葫赂局雹命界忙抉帐摧裙艰郡尽瑟吩罚哑客沁字三章节存储系统三章节存储系统段相联映象方式特点：段相联映象方式特点：段相联映象方式特点：段相联映象方式特点： 段相联映象方式的虚实段内页号对应关系是固定的，每段相联映象方式的虚实段内页号对应关系是固
32、定的，每个虚页在调入时可以选择的只是实段号。由于虚实段大小相个虚页在调入时可以选择的只是实段号。由于虚实段大小相同，所以虚段号比实段号位数多，也就意味着同，所以虚段号比实段号位数多，也就意味着“多多少少”的的映射（组相联是等量映射），其实页争用的发生频率比组相映射（组相联是等量映射），其实页争用的发生频率比组相联要高。在节省页表存储空间方面，性能与组相联差不多。联要高。在节省页表存储空间方面，性能与组相联差不多。主耻在旗阑霞取茹揖袱科详仆更滤沂散记淑存骂索昔里吾裙蔓刚到彩孔近三章节存储系统三章节存储系统多用户虚地址格式多用户虚地址格式 在多用户或多进程并发环境下，由于机器中同时保存并在多用户或
33、多进程并发环境下，由于机器中同时保存并交替运行多个程序模块，各模块中的相同虚页号会发生混淆。交替运行多个程序模块，各模块中的相同虚页号会发生混淆。这时从这时从CPU发出的虚地址还需要在前面拼接上一个发出的虚地址还需要在前面拼接上一个“当前用当前用户号户号”字段，形成字段，形成“多用户虚地址多用户虚地址”，如下图所示。，如下图所示。 在虚实变换时，上面所说的各种查表操作之前还得先去在虚实变换时，上面所说的各种查表操作之前还得先去查一个查一个“段表基址寄存器组段表基址寄存器组”或或“页表基址寄存器组页表基址寄存器组”的小的小表格，确定现在该查哪一张段表或页表。这个小表格建立在表格，确定现在该查哪一
34、张段表或页表。这个小表格建立在CPU里，读写时间很短。里，读写时间很短。览少说爆肺钦恬班材逢奄纵需好肃襟勉氖鬼翟饰滁哭鸭寄竣吭挫禁哮诌列三章节存储系统三章节存储系统替换算法替换算法 上面所讲的地址映象方式是在虚页调入时的上面所讲的地址映象方式是在虚页调入时的“选址选址”规规则，而地址变换方法则是命中时获得实地址的手段。则，而地址变换方法则是命中时获得实地址的手段。 不命中时需要增加的操作就是首先调出一页，调出之后不命中时需要增加的操作就是首先调出一页，调出之后再调入称为再调入称为 “替换替换”。 替换算法要解决的是选择调出对象的问题。替换算法要解决的是选择调出对象的问题。 替换算法的目的是在发
35、生实页争用（即根据地址映象方替换算法的目的是在发生实页争用（即根据地址映象方式，将要调入的虚页被允许进入的所有实页均被其它虚页占式，将要调入的虚页被允许进入的所有实页均被其它虚页占用）时，选择将来不太可能使用或者使用最晚的虚页作为调用）时，选择将来不太可能使用或者使用最晚的虚页作为调出对象，以腾出一个实页来。出对象，以腾出一个实页来。碘病街粮馆德牛划渣步豢铭倾郴按驱仓嗅穷斟汁湘黎豢瘦褒痊割釜垒庐工三章节存储系统三章节存储系统几种常用的替换算法几种常用的替换算法1)随机算法随机算法RAND 在比较范围内任取一页作为淘汰页；在比较范围内任取一页作为淘汰页；2)先先进进先先出出算算法法FIFO 在在
36、比比较较范范围围内内选选取取调调入入最最早早的的一一页页作为淘汰页；作为淘汰页；3)最最不不经经常常使使用用算算法法LFU 在在比比较较范范围围内内选选取取最最近近单单位位时时间内使用次数最少的一页作为淘汰页；间内使用次数最少的一页作为淘汰页；4)最最不不接接近近使使用用算算法法LRU 在在比比较较范范围围内内选选取取最最后后一一次次使使用离现在最久的一页作为淘汰页；用离现在最久的一页作为淘汰页；5)最最优优替替换换算算法法OPT 在在比比较较范范围围内内选选取取下下一一次次使使用用时时间间离现在最久的一页作为淘汰页。离现在最久的一页作为淘汰页。悲贱汾篇笨景沛蓬篱饶汾岿尽孪澜红枣斯驴处出蘸违煌
37、曝糕篷焉蚊浅郸隋三章节存储系统三章节存储系统实例：实存状况图实例：实存状况图例如例如 LRU 算法（其中算法（其中*号表示被选中的淘汰页）：号表示被选中的淘汰页）：舱红奔京烧换诗肪獭枕痴亥庸茅网预傅复贤篮弓阐侵无坊庐呆恃淮噪虾句三章节存储系统三章节存储系统 这这是是对对某某些些替替换换算算法法的的统统称称。如如果果某某些些算算法法在在同同一一地地址址流流同同一一时时刻刻的的小小容容量量分分区区情情况况下下的的保保留留页页面面集集合合必必是是大大容容量量分分区区情情况况下下的的保保留留页页面面集集合合的的子子集集（当当容容量量超超过过虚虚页页总总数数时时，保保留留页页面面集集合合相相同同），则则
38、小小容容量量下下的的命命中中点点到到大大容容量量情情况况下下仍仍然然是是命命中中点点，并并且且随随着着容容量量加加大大，还还可可能能会会有有新新的的命命中中点点产产生。具有这一特性的一类替换算法中成为生。具有这一特性的一类替换算法中成为“堆栈型算法堆栈型算法”。 例例如如，图图3.32中中，对对LRU算算法法，如如果果实实页页数数增增加加到到4，则则t = 5时时为为了了调调入入虚虚页页4就就不不必必替替换换掉掉虚虚页页2，而而是是将将虚虚页页1、2、4、5都都留留在在实实存存，这这时时大大容容量量分分区区情情况况下下的的保保留留页页面面集集合合S2 = 1，2，4，5，同同一一时时刻刻的的小
39、小容容量量分分区区情情况况下的保留页面集合下的保留页面集合S1 = 1，4，5。显然有。显然有S1是是S2子集。子集。 P167第第48行是堆栈型算法的数学定义。行是堆栈型算法的数学定义。 堆堆栈栈型型替替换换算算法法的的主主要要性性质质就就是是命命中中率率H随随着着实实页页分分区区容容量量n的的上上升升而而单单调调上升（不减性）。上升（不减性）。 可可以以证证明明，LFU、LRU、OPT等等算算法法都都是是堆堆栈栈型型算算法法，而而RAND和和FIFO算算法法不不是是堆堆栈栈型型算算法法。P168的的图图3.34是是一一个个实实例例，当当实实页页数数从从3增增加加到到4时时，FIFO的的命命
40、中中率率反反倒倒从从3降降到到2。具具体体观观察察，比比如如t = 7时时，S1 = 1，2，5，S2 = 2，3，4，5，不不满满足足子子集集关关系系。所所以以FIFO不不能能保保证证当当实实页页数数增增加加时时，原原来的命中点不丢。来的命中点不丢。堆栈型替换算法堆栈型替换算法煞菜渣母沁曲慕每蔑运麻岳柒宰栖满慰祭目蔚蔚扑尖褒妥畸决后戒拥冰所三章节存储系统三章节存储系统实例：堆栈模拟图实例：堆栈模拟图 研究堆栈型替换算法的性质，一方面可以设计优化的操研究堆栈型替换算法的性质，一方面可以设计优化的操作系统算法（例如作系统算法（例如P167倒数第倒数第3行的行的PFF法），另一方面也可法），另一方
41、面也可推导出一些分析工具，例如推导出一些分析工具，例如“堆栈模拟法堆栈模拟法”。 堆堆栈栈模模拟拟图图可可以以通通过过一一次次作作图图，描描述述同同一一地地址址流流在在各各种种实存分区容量下的命中情况。实存分区容量下的命中情况。粉繁篆斜翅硕杆彬所引叫邱彩半劣俄炮横念渍维俞袱黍刷弄炽肉崩丛担驮三章节存储系统三章节存储系统实例：堆栈模拟图实例：堆栈模拟图鹤烯侵个授怔裳进暑钉层韭切涣涛先笨简丢拇膀谩碘膳戌搞靶握甘茅或覆三章节存储系统三章节存储系统tTm#0#1#2#n-10n2n3n1n+1N-12n-12n+13n+13n-14n-1体体体体0 0体体体体1 1体体体体n-1n-1低位交叉存储器提
42、高速度原理低位交叉存储器提高速度原理蜒钥肝握畸辈孤铬音批骇酪歧慑壬原驶盾峡防宗昆米今官蛊焦蚤磁嗡绚烛三章节存储系统三章节存储系统无访问冲突存储器（无访问冲突存储器（P143）低位交叉存储器（低位交叉存储器（N=4） 如何访问地址连续递增如何访问地址连续递增+1，那么，一个存储周期并行访问，那么，一个存储周期并行访问N个（个（N=4）不同存储体，速度提高不同存储体，速度提高N倍。但这只是理想情况，如果访问地址不是连续递增倍。但这只是理想情况，如果访问地址不是连续递增+1，那么就有可能出现一个存储周期内连续访问同一个存储体情况，就会发，那么就有可能出现一个存储周期内连续访问同一个存储体情况，就会发
43、生生“访问冲突访问冲突访问冲突访问冲突”。捏特仿掘展复撒桑袭慈哀皖爸刹趟骆坷读涧世蔬额闷铂拴锡跃攀刁芹瘫断三章节存储系统三章节存储系统 如何要求在一个存储周期内按地址每次递增如何要求在一个存储周期内按地址每次递增+2（步距步距）访问）访问4个单元，个单元，假如从假如从0单元开始，即访问单元开始，即访问0、2、4、6单元，那么，由于单元，那么，由于0与与4、2与与6分别在分别在同一个存储体，所以出现在一个存储周期内需要两次访问同一存储体的情况，同一个存储体，所以出现在一个存储周期内需要两次访问同一存储体的情况，既发生访问冲突。既发生访问冲突。0426型谢图算麻瘟增稼靡泌送楔襄匪氓上棉阿顷壳捆漠撇
44、欧讫当嗽锌叔谩撤谷三章节存储系统三章节存储系统0426812101415379131115体体体体0 0体体体体1 1体体体体2 2体体体体3 3怎样才能不发生冲突？怎样才能不发生冲突？ N=4时，地址每次递增时，地址每次递增+3（步距步距），访问情况如下：），访问情况如下：0426812101415379131115体体体体0 0体体体体1 1体体体体2 2体体体体3 3 没有发生访问冲突！为什么当没有发生访问冲突！为什么当N=4，步距是，步距是2会发生冲突，而步距是会发生冲突，而步距是1或者或者3却不会发生冲突？却不会发生冲突？ 原来原来2（步距）是（步距）是N（=4）的约数，而）的约数，
45、而1（步距）和（步距）和3（步距）却与（步距）却与N（=4）互质。是不是地址递增步距与存储体数互质就能保证不会发生访问冲突？互质。是不是地址递增步距与存储体数互质就能保证不会发生访问冲突？倒压咏颁掸港粥炮跟酉运喧砚攫慌及雪谆胶焦智壁匠军阁挟藉拟迈莱毡梨三章节存储系统三章节存储系统052710151217163811161318体体体体0 0体体体体1 1体体体体2 2体体体体3 3491419体体体体4 4步距步距=2时的访问情况：时的访问情况：当当N=5时时052710151217163811161318体体体体0 0体体体体1 1体体体体2 2体体体体3 3491419体体体体4 4步距步
46、距=3时的访问情况：时的访问情况：052710151217163811161318体体体体0 0体体体体1 1体体体体2 2体体体体3 3491419体体体体4 4韦向硕壶溶判砍禽脚汕前血墙咽耶缄准揖肯稽闰陪服还奸矣拧敦糕荒款程三章节存储系统三章节存储系统步距步距=4时的访问情况：时的访问情况：052710151217163811161318体体体体0 0体体体体1 1体体体体2 2体体体体3 3491419体体体体4 4 所以，在低位交叉并行存储器中，为了避免发生访问冲突，所以，在低位交叉并行存储器中，为了避免发生访问冲突，所以，在低位交叉并行存储器中，为了避免发生访问冲突，所以，在低位交叉
47、并行存储器中，为了避免发生访问冲突，存储体数存储体数存储体数存储体数N N一般取质数，如我国银河计算机中一般取质数，如我国银河计算机中一般取质数，如我国银河计算机中一般取质数，如我国银河计算机中N N取取取取3131。肩末交诡催箱涩载白胆魂狐豆淬个请惜渴么裕磨硫干吱镶快恕酚挠炸队炔三章节存储系统三章节存储系统更为复杂的情况：更为复杂的情况：更为复杂的情况：更为复杂的情况： 将二维数组将二维数组将二维数组将二维数组a00a01a02a03a10a11a12a13a20a21a22a23a30a31a32a33存放在如下低位交叉并行存储器（存放在如下低位交叉并行存储器（存放在如下低位交叉并行存储器
48、（存放在如下低位交叉并行存储器（N=4N=4）中，）中，）中，）中，0426812101415379131115体体体体0 0体体体体1 1体体体体2 2体体体体3 3 使得数组按行、列、对角线、反对角线等方式访问时，不会发生存储使得数组按行、列、对角线、反对角线等方式访问时，不会发生存储使得数组按行、列、对角线、反对角线等方式访问时，不会发生存储使得数组按行、列、对角线、反对角线等方式访问时，不会发生存储体访问冲突？体访问冲突？体访问冲突？体访问冲突？行行行行列列列列对角线对角线对角线对角线反对角线反对角线反对角线反对角线并罩屯挫诗贫脚武迹找抨酬玉争猴引粮铣门揪亲底龙帆味袭权始辕梭虐蓬三章节
49、存储系统三章节存储系统 对于对于nn的二维数组，假如并行存储体个数的二维数组，假如并行存储体个数mn，并且取质数。设，并且取质数。设同一列相邻元素在并行存储器中错开同一列相邻元素在并行存储器中错开d1个存储体存放，同一行相邻元个存储体存放，同一行相邻元素在并行存储器中错开素在并行存储器中错开d2个存储体存放。当个存储体存放。当 m=22p+1（p为任意自然数）为任意自然数）时，能够同时实现按行、按列、按对角线和按反对角线无冲突访问的充时，能够同时实现按行、按列、按对角线和按反对角线无冲突访问的充要条件是：要条件是：d1=2p，d2=1 假设假设aij是数组任意元素，则该元素在并行存储体中体号和
50、体内地址是数组任意元素，则该元素在并行存储体中体号和体内地址分别为：分别为：存储体号：存储体号：(2pi+j+k)MOD m体内地址：体内地址：i例如：当例如：当n=4、m=5时，时， m=5= 22p+1=221+1，p=1，所以，所以，d1=2p=2，数组元素存放情况如下：，数组元素存放情况如下：a00a13a02a10a2115a23a31a016a03a11a22a3013a32体体体体0 0体体体体1 1体体体体2 2体体体体3 34a12a20a33体体体体4 4濒霹纷从檀舟拭颤狸谩敢衅九呐棋鸣嗽柏才兽免爽患存届饱霹恃超旗插作三章节存储系统三章节存储系统a00a13a02a10a2
51、115a23a31a016a03a11a22a3013a32体体体体0 0体体体体1 1体体体体2 2体体体体3 34a12a20a33体体体体4 4a00a13a02a10a2115a23a31a016a03a11a22a3013a32体体体体0 0体体体体1 1体体体体2 2体体体体3 34a12a20a33体体体体4 4a00a13a02a10a2115a23a31a016a03a11a22a3013a32体体体体0 0体体体体1 1体体体体2 2体体体体3 34a12a20a33体体体体4 4按反对角线按反对角线按反对角线按反对角线按对角线按对角线按对角线按对角线按列：按列：按列：按列
52、： 0 0列列列列 1 1列列列列 2 2列列列列 3 3列列列列挞摘就裕答男燕川宏茬耸黎游镍旭氰啼篮荆掘印这蜡饲跋藕识缓缺阁筑腹三章节存储系统三章节存储系统虚拟存储器虚拟存储器VM（P146）VMVM位置：位置：位置：位置：CPUCacheMainMemoryOnlineDiskVMVM三个空间：三个空间：三个空间：三个空间：虚拟空间虚拟空间虚拟空间虚拟空间主存储器空间主存储器空间主存储器空间主存储器空间（实空间）（实空间）（实空间）（实空间）外存磁盘空间外存磁盘空间外存磁盘空间外存磁盘空间（实空间）（实空间）（实空间）（实空间）0磁头1磁头9磁头10磁头40柱面0扇区00000000H00
53、0000HFFFFFFFFHFFFFFFH00000FFFH000FFFH1页(4K)1页洪汐猴谭啦裔你芥溪钥伎澄廉食邢郁羞赁局当霞椅举析烟丑丑狰司爽费瘤三章节存储系统三章节存储系统地址映象：地址映象：地址映象：地址映象：虚地址集合与实地址集合的对应规则，或者是约束关系，虚地址集合与实地址集合的对应规则，或者是约束关系，就是用户在虚地址空间写的程序按照某种规则装入到主存储器中。表现就是用户在虚地址空间写的程序按照某种规则装入到主存储器中。表现形式就是段表和页表。形式就是段表和页表。地址变换（虚实变换）：地址变换（虚实变换）：地址变换（虚实变换）：地址变换（虚实变换）：逻辑地址到物理地址的变换过
54、程。逻辑地址到物理地址的变换过程。虚拟空间虚拟空间虚拟空间虚拟空间主存储器空间主存储器空间主存储器空间主存储器空间外存磁盘空间外存磁盘空间外存磁盘空间外存磁盘空间XXXXXXXXHYYYYYYYYHZZZZZZHXXXXXXXXHZZZZZZH内部地址内部地址变换变换柱面磁头扇区外部地址外部地址变换变换YYYYYYYYH积玉横慷宙牛沦达跨玖溃续萄枝英坠寅纺条十绸粤仅猫凤蜕胆煤耳垫炭靳三章节存储系统三章节存储系统多种虚拟存储系统（器）多种虚拟存储系统（器）多种虚拟存储系统（器）多种虚拟存储系统（器）分类依据：地址映象和地址变换方法，可管理单元性质分类依据：地址映象和地址变换方法，可管理单元性质分
55、类依据：地址映象和地址变换方法，可管理单元性质分类依据：地址映象和地址变换方法，可管理单元性质1)1)段式虚拟存储器段式虚拟存储器段式虚拟存储器段式虚拟存储器2)2)页式虚拟存储器页式虚拟存储器页式虚拟存储器页式虚拟存储器3)3)段页式虚拟存储器段页式虚拟存储器段页式虚拟存储器段页式虚拟存储器段式虚拟存储器段式虚拟存储器段式虚拟存储器段式虚拟存储器管理单元：段管理单元：段管理单元：段管理单元：段段形式：函数、子程序、数组、表格、向量。段形式：函数、子程序、数组、表格、向量。段形式：函数、子程序、数组、表格、向量。段形式：函数、子程序、数组、表格、向量。说明：每个程序段都从说明：每个程序段都从说
56、明：每个程序段都从说明：每个程序段都从0 0地址开始编址，长度可长可短，可以地址开始编址，长度可长可短，可以地址开始编址，长度可长可短，可以地址开始编址，长度可长可短，可以在程序执行过程中动态改变程序段的长度。在程序执行过程中动态改变程序段的长度。在程序执行过程中动态改变程序段的长度。在程序执行过程中动态改变程序段的长度。凸缎梨聪车赫刺琼濒姚徽店瞒搁西灵劈颧忘怂潭进轩躲究填潞时的蔽帕捅三章节存储系统三章节存储系统主程序主程序(0段段)1k1段段2段段3段段0500020002000段号段号段长段长起址起址01k8k150016k22009k320030k08k(02000H)9k(03000H
57、)16k(04000H)30k虚拟空间虚拟空间主存储器主存储器段表段表衔杯已拨盖溅赋中涡朗岗几既彰粘阅冒独裕扬狠去召柱烙蹋占直逢惺氢耽三章节存储系统三章节存储系统0段表段表长度长度段表段表基址基址6As段名段名起始起始地址地址装入装入位位段长段长访问访问方式方式用户号用户号U段号段号S段内偏移段内偏移D多用户多用户虚地址虚地址主存实地址主存实地址432101n-1As段表基址寄存器段表基址寄存器一个用户（一道作业）的段表一个用户（一道作业）的段表名匹避擎首分赘间漫张悯链更董钙赫馁泣宾噪正韭磁扶陋渍午咆穆学峦殴三章节存储系统三章节存储系统段式虚拟存储器的主要优点：段式虚拟存储器的主要优点：(1)
58、 程序的模块化性能好程序的模块化性能好(2) 便于程序和数据的共享便于程序和数据的共享(3) 程序的动态链接和调度比较容易程序的动态链接和调度比较容易(4) 便于实现信息保护便于实现信息保护段式虚拟存储器的主要缺点：段式虚拟存储器的主要缺点：(1) 地址变换所花费的时间比较长，做两次加法运算地址变换所花费的时间比较长，做两次加法运算(2) 主存储器的利用率往往比较低主存储器的利用率往往比较低(3) 对辅存（磁盘存储器）的管理比较困难对辅存（磁盘存储器）的管理比较困难价才汤收朝料农稠细湿肋戌阐箩诧纪俩毕茧翻寥内讥笔海憾猩艳芯界育酶三章节存储系统三章节存储系统2K5K2K4K总的空闲空间：总的空闲
59、空间： 2K+5K+2K+4K=13K 但不能载入一个但不能载入一个6K的的程序段，空间浪费严重。程序段，空间浪费严重。焕罗绣辈没奠欣额退似就樟瘴哉饥据抚勘钨得醉盛惺段构脖鸟胳凯汤形油三章节存储系统三章节存储系统0页页1页页2页页3页页页号页号主存页号主存页号0123用户程序用户程序主存储器主存储器页表页表页式虚拟存储器的地址映象页式虚拟存储器的地址映象页式虚拟存储器页式虚拟存储器页式虚拟存储器页式虚拟存储器腰菜藏宁惨省冻垄寓昆篇省耗恕率菏崭峡渍酷暮都物蜜揖羊剖随讥粪韵炮三章节存储系统三章节存储系统Pa装入装入修改修改主存页号主存页号标志标志用户号用户号U虚页号虚页号P页内偏移页内偏移D页内偏
60、移页内偏移d2pPa页表基址页表基址页表页表实页号实页号p憾馋垃袄涉募彰谷姚诞扰酉皮苞裤危驼坝呜告幌癸耘喧详旭九最局侥揣征三章节存储系统三章节存储系统主要优点：主要优点：(1) 主存储器的利用率比较高主存储器的利用率比较高(2) 页表相对比较简单页表相对比较简单(3) 地址变换的速度比较快地址变换的速度比较快(4) 对磁盘的管理比较容易对磁盘的管理比较容易主要缺点：主要缺点：(1) 程序的模块化性能不好程序的模块化性能不好(2) 页表很长，需要占用很大的存储空间。例如：虚拟页表很长，需要占用很大的存储空间。例如：虚拟存储空间存储空间4GB，页大小，页大小1KB，则页表的容量为，则页表的容量为4
61、M字，字，16MB窒泼姐苫哑耀顶票功囤憎事漂反侯榷平疑咽醛笛苞朋探庄郸钥哎写谐攀雹三章节存储系统三章节存储系统段页式虚拟存储器段页式虚拟存储器 对用户用来编写程序的虚拟存储空间采用分段的方法管对用户用来编写程序的虚拟存储空间采用分段的方法管理，而对主存储器的物理空间采用分页的方法管理。理，而对主存储器的物理空间采用分页的方法管理。宪岂樊诫璃媚凿朽馏俯苏级豁溶扇柒摸饿简雕新锐演氮楷屋郭蕉伎坡配叮三章节存储系统三章节存储系统年遇碰局吐豪账枯市剐述略戍渠婚吉坟涧投仆尾芋省惑征耍棉矩搅黑铰稽三章节存储系统三章节存储系统装入装入修改修改实页号实页号标志标志用户号用户号U段号段号S页内偏移页内偏移页内偏移
62、页内偏移0/11pA实页号实页号p虚页号虚页号PAs装入装入1修改修改0/1页表页表地址地址ApAs北德纯邮骤屯白愚抒材臣扔歌颓柞登憎严银污胺充怎晴沦舟货渔炮盗窍隆三章节存储系统三章节存储系统4、外部地址变换、外部地址变换1)在操作系统中，把页面失效当作一种异常故障来处理。在操作系统中，把页面失效当作一种异常故障来处理。2)每个用户程序都有一张外页表，虚拟地址空间中的每一每个用户程序都有一张外页表，虚拟地址空间中的每一页或每个程序段，在外页表中都有对应的一个存储字。页或每个程序段，在外页表中都有对应的一个存储字。3)每一个存储字除了磁盘存储器的地址之外，至少还包括每一个存储字除了磁盘存储器的地
63、址之外，至少还包括一个装入位。一个装入位。瓤譬团绣帐金个染俘帜紫础豹崭仙庇围迟轿唉隙笋皮跑钻顿农癌冈臂猎招三章节存储系统三章节存储系统装入装入磁盘实地址磁盘实地址用户号用户号页内偏移页内偏移1虚页号虚页号外部地址外部地址变换（软变换（软件实现）件实现）磁盘号磁盘号柱面号柱面号磁头号磁头号块号块号多用户多用户虚地址虚地址外页表外页表理钞孝邹拄情压隆墙狐菏纵病筷疗确槐伶峙悬烟赊姆葫偿碑机果哑稠沙褐三章节存储系统三章节存储系统提高虚拟存储器等效访问速度的措施提高虚拟存储器等效访问速度的措施提高虚拟存储器等效访问速度的措施提高虚拟存储器等效访问速度的措施因为，存储系统等效访问速度：因为，存储系统等效访
64、问速度：THT1(1H)T2所以，提高虚拟存储器等效访问速度的措施有：所以，提高虚拟存储器等效访问速度的措施有：1)由于由于T2远大于远大于T1，所以需要提高主存命中率，所以需要提高主存命中率H2)缩短访存时间缩短访存时间缩短访存时间缩短访存时间缩短访存时间缩短访存时间1)提高存储器件本身的速度提高存储器件本身的速度2)优化存储结构的设计优化存储结构的设计瘴擎筑伯伎肯续南既渐毡德抑宪与菩植忱疑哦辐冶落资榷芭讹溺蕉优溉阂三章节存储系统三章节存储系统存储结构可以优化设计的环节：存储结构可以优化设计的环节：存储结构可以优化设计的环节：存储结构可以优化设计的环节：1）内部地址变换）内部地址变换虚地址虚
65、地址实地址，发生概率实地址，发生概率100%2）外部地址变换）外部地址变换页面失效时发生，发生概率页面失效时发生，发生概率1%3）页面的替换）页面的替换页面失效又页面争用时发生，发生概率页面失效又页面争用时发生，发生概率1%4）页面的调入与调出）页面的调入与调出页面替换时或者页面初始未装入时发生，发生概率不定页面替换时或者页面初始未装入时发生，发生概率不定根据根据根据根据AmdahlAmdahl定律，加快内部地址变换速度是关键。定律，加快内部地址变换速度是关键。定律，加快内部地址变换速度是关键。定律，加快内部地址变换速度是关键。昔嫩巡婶营尧键迎强鞭习经世棕骗伴世乐改扇黔氓淄聊芥絮抠挖排障贰借三
66、章节存储系统三章节存储系统提高内部地址变换速度的方法：提高内部地址变换速度的方法：提高内部地址变换速度的方法：提高内部地址变换速度的方法：1）采用单独的小容量随机存储器或寄存器组存放内页表。）采用单独的小容量随机存储器或寄存器组存放内页表。适合规模较小的机器，如：适合规模较小的机器，如：VM1M字字2）采用）采用“目录表目录表”3）增设）增设“快表快表”，“快表快表”与与“慢表慢表”相结合相结合4）散列函数）散列函数目录表目录表目录表目录表 页面只存放已经装入主存储器页面的虚地址与实地址页面只存放已经装入主存储器页面的虚地址与实地址对应关系，采用相联方式访问，所以又称为对应关系，采用相联方式访
67、问，所以又称为相联目录表相联目录表。敞君瓶粘速草始蛋咱豁极晶庆表镰肛襄嘱端孝汹鸽弄辗龟亲鸵笼袒黎滑沃三章节存储系统三章节存储系统实页号实页号其它标志其它标志用户号用户号U页内偏移页内偏移Dp虚页号虚页号P多用户多用户虚地址虚地址目录表（目录表（CAM）页内偏移页内偏移d实页号实页号p多用户虚页号多用户虚页号U, P修改修改0/1主存实地址主存实地址相联访问相联访问客淫椒八泄般宰盼谊禽泡夜稽蛤饱歪衍困埂轧苇翁佩铂枉匝努版蓉陕碑黎三章节存储系统三章节存储系统快慢表快慢表快慢表快慢表由快表和慢表构成一个两级存储系统：由快表和慢表构成一个两级存储系统：1)快表：小容量快表：小容量(816个字个字)，高
68、速硬件实现，采用，高速硬件实现，采用CAM方式访问方式访问2)慢表：全表，按地址访问。慢表：全表，按地址访问。啪液短柜幼悠悠驼渊淡荡朵揉罗驹众廷盏译只衰生观业药聋昂瓤懂氏白睦三章节存储系统三章节存储系统实页号实页号用户号用户号U页内偏移页内偏移Dp虚页号虚页号P多用户多用户虚地址虚地址快表（快表（CAM）页内偏移页内偏移d实页号实页号p多用户虚页号多用户虚页号U, P主存实地址主存实地址实页号实页号p装入装入1慢表慢表珊蜀乱爽叼陋浅摸蟹泻楚翘蕾插邓邯沤近政涂揽驯行望蔬碎隙观蚀买满总三章节存储系统三章节存储系统散列函数散列函数散列函数散列函数让让NV与存放内容的单元地址之间有某种散列函数关系。与
69、存放内容的单元地址之间有某种散列函数关系。用户号用户号U虚页号虚页号PNV 即：即：A=H（NV） 为了解决散列冲突（多个虚页散列同一个快表地址），为了解决散列冲突（多个虚页散列同一个快表地址），必须将虚地址中虚页号加入到快表中。必须将虚地址中虚页号加入到快表中。锹坪已表梦议度甚药蔡舷季测绘朋宜蒋峭胀钞沈杭咎赂钦芭佑莹备副附慧三章节存储系统三章节存储系统实页号实页号用户号用户号U页内偏移页内偏移Dp虚页号虚页号P多用户多用户虚地址虚地址按地址访问快表按地址访问快表页内偏移页内偏移d实页号实页号p多用户虚页号多用户虚页号 PV主存实地址主存实地址A快表地址快表地址散列变换散列变换（硬件实现）（硬
70、件实现）相等比较相等比较快表快表命中命中查查慢表慢表扇痢邪峙傍仰福召工洱姨旗貉玲忽钥寝戍彼燎熔窥听摇假毡导桶役徒坦穿三章节存储系统三章节存储系统多级页表多级页表多级页表多级页表一级页表一级页表二级页表二级页表三级页表三级页表把贾尽齐如扛驰椿适苦足都孕城爽死募詹驶山碑破韵扯耐苫邮垂剑署园澄三章节存储系统三章节存储系统虚拟空间：虚拟空间：Nv页面大小：页面大小：Np一个页表存储字大小：一个页表存储字大小：Nd页面级数：页面级数：g则则页表长度（记录数）：页表长度（记录数）：Nv/Np每页记录项数：每页记录项数：Np/Nd 有等式：有等式：Nv/Np=(Np/Nd)g 取对数得取对数得P157公式：
71、公式：Log2Nv-Log2Np g=Log2Np-Log2Nd播完索饶熄娠逢咳莉佣闷娄粪臆呻莉暴今徒炮液渺泻痴煞隶候斑轻洽昌牺三章节存储系统三章节存储系统影响主存命中率的主要因素：影响主存命中率的主要因素：1)程序执行过程中的页地址流分布情况程序执行过程中的页地址流分布情况2)所采用的页面替换算法所采用的页面替换算法3)页面大小页面大小4)主存储器的容量主存储器的容量5)所采用的页面调度算法所采用的页面调度算法提高主存命中率的方法提高主存命中率的方法提高主存命中率的方法提高主存命中率的方法书烯劣爽蓟康暂忽羌酌韭遣赤害逃膨男丹谩椽凭威藐晰泪灵琢删顿伴痕狸三章节存储系统三章节存储系统页面大小页面
72、大小 SP命命中中率率 H1S2S页面大小与命中率的关系页面大小与命中率的关系页面大小与命中率的关系页面大小与命中率的关系脱似亩雷鄂薛少私跃桑撮爷禹音卓养赠狐陈脸吼签胖酥遭寅酌墅稍赔居秋三章节存储系统三章节存储系统命命中中率率 H主存容量主存容量S1.0主存容量与命中率的关系主存容量与命中率的关系主存容量与命中率的关系主存容量与命中率的关系蝉夺藉刚由喂蛾冉导谆皿昭杭荚焰彦洪陛馈贡眉痴汕向盏屁苹讲周昆肋铜三章节存储系统三章节存储系统页面调度方式与命中率的关系页面调度方式与命中率的关系页面调度方式与命中率的关系页面调度方式与命中率的关系q请求式：请求式：当使用到的时候，再调入主存当使用到的时候，再
73、调入主存q预取式：预取式：在程序重新开始运行之前，把上次停止运行前一在程序重新开始运行之前，把上次停止运行前一段时间内用到的页面先调入到主存储器，然后才开始段时间内用到的页面先调入到主存储器，然后才开始运行程序。运行程序。可以避免在程序开始运行时，频繁发生页面失效可以避免在程序开始运行时，频繁发生页面失效的情况。的情况。如果调入的页面用不上，浪费了调入的时间，占如果调入的页面用不上，浪费了调入的时间，占用了主存资源。用了主存资源。趣捌忘蝇察谐夏玉锰融剁饵里岁潜晤迄重琅代绞拌茂孔驼迄杯竹遥遵华鹏三章节存储系统三章节存储系统CacheCacheCache位置：位置：位置：位置：CPUCacheMa
74、inMemory主存储器空间主存储器空间主存储器空间主存储器空间（虚拟空间、实空间）（虚拟空间、实空间）（虚拟空间、实空间）（虚拟空间、实空间）000000H块汪犁版忌睦统哄验攀市抡验愁住汹闲缉提硕婿样序撼滑曲冉湘税草食尉弱三章节存储系统三章节存储系统块号块号B块内地址块内地址W主存主存/Cache地址变换地址变换块号块号b块内地址块内地址wCacheCache替替换策略换策略储器储器主存主存替换块替换块装入块装入块已满已满未满未满未命中未命中命中命中数据送数据送 CPU主存地址主存地址来自来自CPU饼神两联洁哄颓煤莲堡阮稳蜘膛来史原臀挠妒此饶曳邓配虏残撼复永千谁三章节存储系统三章节存储系统C
75、acheCache特点：特点：特点：特点：1)为了提高为了提高CPU访问访问Cache速度，可以访问速度，可以访问Cache两两步操作（地址变换和取得步操作（地址变换和取得Cache 块内容）进行流水块内容）进行流水线设计。线设计。2)一般采用两级一般采用两级Cache，一个在，一个在CPU内部，一个在主内部，一个在主板上。板上。3)为了加速调块，一般将每块容量设计等于一个主存为了加速调块，一般将每块容量设计等于一个主存周期内由主存所能访问到的字数，因此，有周期内由主存所能访问到的字数，因此，有Cache存储器主存系统都采用多体交叉存储器。存储器主存系统都采用多体交叉存储器。4)Cache访存
76、的优先级高于通道和访存的优先级高于通道和CPU访存优先级，访存优先级，优先级次序通常是：优先级次序通常是：Cache、通道、写数、取数、通道、写数、取数、取指。取指。劝佛晌侨望走羞玫翟躁址戎岸狞具诊泡刘子凛范儿铣吼言机待猜欺讶棕钵三章节存储系统三章节存储系统存储系统存储系统存储系统存储系统两级存储器速度比两级存储器速度比两级存储器速度比两级存储器速度比Cache虚拟存储器虚拟存储器要达到的目标要达到的目标要达到的目标要达到的目标提高速度提高速度扩大容量扩大容量实现方法实现方法实现方法实现方法全部硬件全部硬件软件为主软件为主硬件为辅硬件为辅310倍倍105倍倍页页页页( (块块块块) )大小大小
77、大小大小116字字1KB16KB等效存储容量等效存储容量等效存储容量等效存储容量主存储器主存储器虚拟存储器虚拟存储器透明性透明性透明性透明性对系统和对系统和应用程序员应用程序员仅对应用仅对应用程序员程序员生产工艺生产工艺生产工艺生产工艺与与CPU相同相同MOS工艺工艺CacheCache存储系统与虚拟存储系统比较存储系统与虚拟存储系统比较存储系统与虚拟存储系统比较存储系统与虚拟存储系统比较CPUCPU、CacheCache、主存联系、主存联系、主存联系、主存联系CPU与与Cache、主存之间有通路主存之间有通路CPU与主存、与主存、主存与辅存有通路，主存与辅存有通路，但但CPU与辅存之间与辅存
78、之间没有通路没有通路贫影爱晨社诵嘻聂篷礼姿陶勒丧期笛仅迹棘此壹圣脖扩甸述澡渊睦问膜危三章节存储系统三章节存储系统CacheCache的一致性问题的一致性问题的一致性问题的一致性问题（单处理机、单存储器时）（单处理机、单存储器时）造成造成Cache与主存的不一致的原因：与主存的不一致的原因：(1) 由于由于CPU写写Cache，没有立即写主存，没有立即写主存(2) 由于由于IO处理机或处理机或IO设备写主存设备写主存Cache的更新算法的更新算法(1) 写直达法写直达法(写通过法写通过法), Write-through：CPU在执在执行写操作时，把数据同时写入行写操作时，把数据同时写入Cache
79、和主存。和主存。(2) 写回法写回法 (抵触修改法抵触修改法)Write-Back：CPU数据只写数据只写入入Cache，不写入主存；仅当替换时，才把修改过的，不写入主存；仅当替换时，才把修改过的Cache块写回到主存。块写回到主存。挨胸恕析仲瞻概奇趾意屯菲乙航暑窑瓮绢烙窝终杆仟钻僧窘羹坑讶桶退涵三章节存储系统三章节存储系统CPUXI/OXCache主存储器主存储器CPUXI/OXCache主存储器主存储器(a) CPU写写Cache(b) I/O写主存写主存Cache与主存不一致的两种情况与主存不一致的两种情况爱繁纲肛椿清赤享洲淀峻逃譬侥蹋收订攒暴煞间佯苛惑眩量酶耍淋拳吼舀三章节存储系统三章
80、节存储系统写回法与写直达法的优缺点比较：写回法与写直达法的优缺点比较：(1)可靠性，写直达法优于写回法可靠性，写直达法优于写回法(2)与主存的通信量与主存的通信量, WB少于少于WT例如：写操作占总访存次数的例如：写操作占总访存次数的20, Cache命中率命中率为为99%, 每块每块4个字。当个字。当Cache发生块替换时发生块替换时, 有有30%块需要写回主存块需要写回主存, 其余的因未被修改过而不必其余的因未被修改过而不必写回主存。则对于写回主存。则对于WT法法, 写主存次数占总访存次数写主存次数占总访存次数的的20%。而。而WB法为法为(1-99%)30%4=1.2%。因此。因此, W
81、B法与主存的通信量要比法与主存的通信量要比WT法少法少10多倍。多倍。(3) 控制的复杂性控制的复杂性, 写直达法比写回法简单写直达法比写回法简单(4) 硬件实现的代价硬件实现的代价, 写回法要比写直达法好写回法要比写直达法好趣讫童象滨棉刁抖刑赔抢缠旷放孟姿议嘎霞掂怪回亭诱媚诫话幕舟邱峙坑三章节存储系统三章节存储系统写写Cache的两种方法：的两种方法：(1) 不按写分配法：在写不按写分配法：在写Cache不命中时，只把所要写不命中时，只把所要写的字写入主存。的字写入主存。(2) 按写分配法：在写按写分配法：在写Cache不命中时，还把一个块从不命中时，还把一个块从主存读入主存读入Cache。
82、 目前，在写回法中采用按写分配法，在写直达法中采用目前，在写回法中采用按写分配法，在写直达法中采用不按写分配法。不按写分配法。寓心熟列津立蓖仿拜元恫丰葫堪袒恬惰隋寡葬疹律滔瓜练丫眉垮熏淬拦啸三章节存储系统三章节存储系统Cache的预取算法的预取算法预取算法有如下几种：预取算法有如下几种：(1) 按需取：在出现按需取：在出现Cache不命中时，把一不命中时，把一个块取到个块取到Cache中来中来(2) 恒预取：无论恒预取：无论Cache是否命中，都把下是否命中，都把下一块取到一块取到Cache中中(3) 不命中预取：当不命中预取：当Cache不命中，把本块不命中，把本块和下一块取到和下一块取到C
83、ache中中综合考虑因素：综合考虑因素：q命中率的提高命中率的提高qCache与主存之间通信量的增加与主存之间通信量的增加蒂鸦纤聪投独丸珠缩烫燎倔窥蝇莱横扒滑甥塔盗枪单皑道把爬孺果责掐秤三章节存储系统三章节存储系统题：有一个经解释实现的计算机，可按功能分成题：有一个经解释实现的计算机，可按功能分成4级。各一级为了执行级。各一级为了执行一条指令需要下一级的一条指令需要下一级的N条指令解释。若执行第条指令解释。若执行第1级指令要级指令要Kns时间，那时间，那么执行第么执行第2、3和和4级的一条指令各需多少时间？级的一条指令各需多少时间？解：执行第解：执行第2、3、4级一条指令各需时间为：级一条指令
84、各需时间为：（KN）ns 、（、（KN2）ns、（、（KN3）ns题：有一个计算机系统可按功能分成题：有一个计算机系统可按功能分成4级，各级指令都不相同，每一级级，各级指令都不相同，每一级指令都比其下一级指令在效能上强指令都比其下一级指令在效能上强M倍，既第倍，既第i级的一条指令能完成第级的一条指令能完成第i-1级的级的M条指令的计算量。现若需第条指令的计算量。现若需第i级的级的N条指令解析第条指令解析第i+1级的一条指令，级的一条指令，而有一段第而有一段第1级的程序需运行的时间为级的程序需运行的时间为Ks，问在第，问在第2、3和和4级的一段等级的一段等效的程序各需运行多长时间？效的程序各需运
85、行多长时间？解：第解：第1级的一段程序需运行的时间为级的一段程序需运行的时间为Ks，第，第2级等效程序指令数为第级等效程序指令数为第1级程序指令数的级程序指令数的1/M，而第，而第2级一条指令在第级一条指令在第1级解析时需要级解析时需要N条第条第1级指级指令，因此第令，因此第2级等效程序执行时间为（级等效程序执行时间为（KN）/Ms 。 依次类推，第依次类推，第3、4级等效程序执行时间分别为：级等效程序执行时间分别为：（KN2）/M2s、（、（KN3）/M3s渣尾宵薄碑敦镰锨敲嵌殆嚎谚星就呀娟外砍旁猩拉仓席坝凤械宵倘兢盾芍三章节存储系统三章节存储系统题：从机器（汇编）语言程序员的角度看，以下哪
86、些是透明的？题：从机器（汇编）语言程序员的角度看，以下哪些是透明的？指令地址寄存器；指令缓冲器；条件码寄存器；乘法器；主存地址寄存指令地址寄存器；指令缓冲器；条件码寄存器；乘法器；主存地址寄存器；磁盘外设；先行进位链；移位器；通用寄存器；中断字寄存器器；磁盘外设；先行进位链；移位器；通用寄存器；中断字寄存器解：从机器（汇编）语言程序员的角度看，透明的有：解：从机器（汇编）语言程序员的角度看，透明的有：指令缓冲器；乘法器；主存地址寄存器；先行进位链；移位器。指令缓冲器；乘法器；主存地址寄存器；先行进位链；移位器。题：某机器指令字长题：某机器指令字长16位。设有单地址指令和双地址指令两类，若每个位
87、。设有单地址指令和双地址指令两类，若每个地址字段均为地址字段均为6位，且双地址指令有位，且双地址指令有x条，问单地址指令最多可以有多少条，问单地址指令最多可以有多少条？条？解：双地址指令格式为：解：双地址指令格式为：操作码操作码地址码地址码1地址码地址码24位位6位位6位位操作码占操作码占4位，共有位，共有16种操作码。现双地址指令有种操作码。现双地址指令有x条，占用了条，占用了16种组合种组合中的中的x个码点，所以剩下（个码点，所以剩下（16-x）个码点均可作扩展标志。）个码点均可作扩展标志。单地址指令格式为：单地址指令格式为：扩展操作码扩展操作码地址码地址码10位位6位位每个码点均可扩展每
88、个码点均可扩展6为操作码，所以单地址指令最多（为操作码，所以单地址指令最多（16-x）26条。条。鲸何熙畔镁眉烽卜冀肤慨咸琵爽舱恳毗砖附氦碗踢尸靠娘了旱兜浑贞溉流三章节存储系统三章节存储系统题：一个二级虚拟存储器，题：一个二级虚拟存储器，CPU访问主存访问主存M1和辅存和辅存M2的平均时间分别的平均时间分别为为1us和和1ms。经实际测定，此存储器平均访问时间为。经实际测定，此存储器平均访问时间为100us。试定性。试定性提出使虚拟存储器平均访问时间能从提出使虚拟存储器平均访问时间能从100us下降到下降到10us的几种方法，并的几种方法，并分析这些方法在硬件和软件上的代价。分析这些方法在硬件
89、和软件上的代价。解：二级虚拟存储器等效的平均访问时间公式解：二级虚拟存储器等效的平均访问时间公式TA=HTA1+（1-H）TA2要想缩短虚拟存储器平均访问时间，应从提高要想缩短虚拟存储器平均访问时间，应从提高H和减少和减少TA1两个方面考虑。两个方面考虑。在主存命中率在主存命中率H=0.901的情况下，改用更高速度的主存器件，即使的情况下，改用更高速度的主存器件，即使TA1=0，此时，此时TA=（1-H）TA2=（1-0.901）1ms99us，由于该时间由于该时间10us，所以应从提高主存命中率所以应从提高主存命中率H着手。着手。如果要让如果要让TA=10us，其命中率，其命中率要使要使H提
90、高到提高到0.991，需要从改进替换算法、调度策略、调整页面大小以，需要从改进替换算法、调度策略、调整页面大小以及提高主存容量等多方面综合采取措施。及提高主存容量等多方面综合采取措施。拣馆咯迸靴棱努汗诌宽箕卯族柞研勘橡写疆西撵伴溪霖订参癸痪京授川趴三章节存储系统三章节存储系统题：某虚拟存储器共有题：某虚拟存储器共有8个页面，每页为个页面，每页为1024个字，实际主存为个字，实际主存为4096个个字，采用页表法进行地址映像，映像表的内容如表字，采用页表法进行地址映像，映像表的内容如表1所示所示（1）列出会发生页面失效的全部虚页号）列出会发生页面失效的全部虚页号（2）按以下虚地址：）按以下虚地址：
91、0，3278，1023，1024，2055，7800，4096，6800，计算对应的主存实地址。，计算对应的主存实地址。实页号实页号 装入位装入位3111203021100100表表1解解：（：（1）发生页面失效的虚页分别为：发生页面失效的虚页分别为：2，3，5，7（2）由虚地址计算主存实地址情况如下）由虚地址计算主存实地址情况如下虚地址虚地址虚页号虚页号 页内地址页内地址装入位装入位实页号实页号 页内地址页内地址实地址实地址037281023102420557800409668000 03 6560 10231 02 77 6324 06 656101100113 0失效失效3 10231
92、0失效失效失效失效2 00 6563072无无40951024无无无无2048656虚页号虚页号=虚地址虚地址/页面大小页面大小页内偏移量页内偏移量=虚地址虚地址-虚页号虚页号页面大小页面大小矢遭鸡疹晕嘉奏倔狡戌瘤怔菩迅茂猩横从风哗斗晴烹嫁烷汇红渔见惦膏界三章节存储系统三章节存储系统题：一个程序由题：一个程序由5个虚页组成，采用个虚页组成，采用LFU替换算法，在程序执行过程中，依替换算法，在程序执行过程中，依次访问的意味地址流如下：次访问的意味地址流如下：4，5，3，2，5，1，3，2，3，5，1，31)可能的最高页命中率是多少？可能的最高页命中率是多少？2)至少要分配给该程序多少个页面才能获
93、得最高的命中率。至少要分配给该程序多少个页面才能获得最高的命中率。3)如果在程序执行过程中每访问一个页面，平均要对该页面内的存如果在程序执行过程中每访问一个页面，平均要对该页面内的存储单元储单元1024次，求访问存储单元的命中率。次，求访问存储单元的命中率。解答解答解答解答：（1 1）由于在页地址流中互不相同的页共有）由于在页地址流中互不相同的页共有）由于在页地址流中互不相同的页共有）由于在页地址流中互不相同的页共有5 5页，因此可能的最高页命中率页，因此可能的最高页命中率页，因此可能的最高页命中率页，因此可能的最高页命中率为：为：为：为：（2 2）由于）由于）由于）由于LFULFU算法为堆栈
94、型替换算法，即随着分配给该程序的主存页面数算法为堆栈型替换算法，即随着分配给该程序的主存页面数算法为堆栈型替换算法，即随着分配给该程序的主存页面数算法为堆栈型替换算法，即随着分配给该程序的主存页面数减少，其命中率单调递减，因此，可采用逐渐减少所分配的主存页数减少，其命中率单调递减，因此，可采用逐渐减少所分配的主存页数减少，其命中率单调递减，因此，可采用逐渐减少所分配的主存页数减少，其命中率单调递减，因此，可采用逐渐减少所分配的主存页数的方法进行推算：若分配的方法进行推算：若分配的方法进行推算：若分配的方法进行推算：若分配N N个页面时可获得最高命中率，但分配个页面时可获得最高命中率，但分配个页
95、面时可获得最高命中率，但分配个页面时可获得最高命中率，但分配N-1N-1个个个个页面时命中率却减少，这时我们可以得出分配给页面时命中率却减少，这时我们可以得出分配给页面时命中率却减少，这时我们可以得出分配给页面时命中率却减少，这时我们可以得出分配给N N个主存页面才能获得个主存页面才能获得个主存页面才能获得个主存页面才能获得最高命中率的结论。最高命中率的结论。最高命中率的结论。最高命中率的结论。滞季民村镐建蝎涂枕支风滇显俞拆镰亥贿歪燃讣碱仔垣缸枣埃镜桔砒质事三章节存储系统三章节存储系统（3 3）访问存储单元的命中率为：）访问存储单元的命中率为：）访问存储单元的命中率为：）访问存储单元的命中率为
96、：时间时间页地址流页地址流LFU命中命中7次次144进进2545进进33453进进424*532进进554*532中中61153*2换换731532*中中8215*32中中9315*32中中1051*532中中1111532*中中1231532*中中时间时间页地址流页地址流LFU命中命中3次次144进进2545进进334*53进进4225*32换换55253*2中中612*512换换7335*12*换换82321*2换换93321*2中中10532*52换换1113*152*换换123315*2*中中N=4N=3捍虚楔枪羔音辆烁砷孪浙捶栓浆多介生烹汰划宗爬短希蘸徊装乐池叉翁从三章节存储系统三章
97、节存储系统题：有一个题：有一个Cache存储器，主存共有存储器，主存共有8个块（个块（07），），Cache为为4个块个块（03），采用组相联映像，组内块数为），采用组相联映像，组内块数为2块，替换关系为块，替换关系为LRU。（1）画出主存、）画出主存、Cache地址的各字段对应关系（标出位数）图地址的各字段对应关系（标出位数）图（2）画出主存、）画出主存、Cache空间块的映像对应关系示意图空间块的映像对应关系示意图（3）对于如下主存块地址流：）对于如下主存块地址流：1，2，4，1，3，7，0，1，2，5，4，6，4，7，2，如主存中内容一开始未装入，如主存中内容一开始未装入Cache中，请
98、列出中，请列出Cache中各中各块随时间使用状况块随时间使用状况（4）对于（）对于（3），指出块失效又发生争用的时刻），指出块失效又发生争用的时刻（5）对于（）对于（3），求出此期间），求出此期间Cache之命中率之命中率ndsqnmrsqnnr直接直接相联相联查找查找解：解：主存地址主存地址Cache地址地址0123012345670组组1组组0组组1组组0组组1组组0区区1区区块号块号Cache主存主存 块号块号组间直接，组内相联组间直接，组内相联鼠菇琼俗淬浅疾黎凡你要端吓狗任酉语草脾谗炽侵糕垃琶龋盾又剃某撬周三章节存储系统三章节存储系统时间t1 2 3 4 5 6 7 8 9 10 11
99、 12 13 14 15主存块地址1 2 4 1 3 7 0 1 2 5 4 6 4 7 2Cache块0Cache块1Cache块2Cache块31 1 1* 1 1 1 1* 1 1 1* 4 4 4 4 4 4 4* 4* 4* 0 0* 0* 5 5* 5* 5* 5* 5* 2 2 2 2* 7 7 7 7* 7* 7* 6 6 6* 2 3 3* 3* 3* 2 2 2 2* 2* 7 7*命中情况失 失 失 H 失 替 替 H 替 替 替 替 H 替 替（4）发生）发生Cache块失效又发生块争用的时刻有：块失效又发生块争用的时刻有：6、7、9、10、11、12、14、15。（5
100、） Cache的块命中率为的块命中率为3/15=0.2雪嘉撮繁簇券呢躬肢谈玉脊中针皿捷旺铜岿拌渡宰颁箔湃刮弯吸韦内仪朔三章节存储系统三章节存储系统题题：采用组相联映象的采用组相联映象的Cache存储器，存储器，Cache为为1KB，要求，要求Cache的每的每一块在一个主存周期内能从主存取得，主存模一块在一个主存周期内能从主存取得，主存模4交叉，存储字宽为交叉，存储字宽为32位，位，总容量为总容量为256KB。用按地址访问相联目录表实现实现主存地址到。用按地址访问相联目录表实现实现主存地址到Cache地地址的变换，并约定用址的变换，并约定用4个相等比较电路。个相等比较电路。（1）画出地址变换示
101、意图。）画出地址变换示意图。（2）设计此相联目录表（表行数、总位数及每个相等比较电路和位数）。）设计此相联目录表（表行数、总位数及每个相等比较电路和位数）。 组相联映象特点是：组相联映象特点是：组号计算、组内查表。组号计算、组内查表。因此，关键是计算出因此，关键是计算出Cache和主存的地址格式。和主存的地址格式。Cache的块大小的块大小=44B=16Bndsqnmrsqnnr直接直接相联相联查找查找分析：分析：主存地址主存地址Cache地址地址0123012345670组组1组组0组组1组组0组组1组组0区区1区区块号块号Cache主存主存 块号块号组间直接，组内相联组间直接，组内相联裹勒
102、要蹋殆彩真悍岭恭神樱疯玖琅澡芜饯枷皇檀快删埃匣鼎顿扰撑京兔茹三章节存储系统三章节存储系统块号块号ncb块内位移块内位移nr6位4位10位块号块号nmb块内位移块内位移nmr14位4位18位Cache地址格式如下：地址格式如下：主存地址格式如下：主存地址格式如下：另外，约定用另外，约定用4个相等比较电路做组内相联匹配，因此，组内大小个相等比较电路做组内相联匹配，因此，组内大小4块，占地块，占地址址2位位(B)；组号；组号6-2=4位位(G)，区号，区号14-6=8位位(E)。(见教材见教材P181)所以相联目录表构成如下：所以相联目录表构成如下：E,BbE,BbE,BbE,Bb1616行行行行本嘶赖怔碾旧锚眶土骗柜钳铲主挡塘沁卫孺茸敬琶贡札姿脚形貌逃柑孩锌三章节存储系统三章节存储系统所以，所以，目录表行数：目录表行数：16行行总位数：总位数：16124=768位位每个比较电路位数：每个比较电路位数：10位位尝秧渐湖听息级贼秉赞芽弄纷醛陌剂康欢僵生噶暑烫椅煽阑潮描骆设帘抡三章节存储系统三章节存储系统
