6.823计算机体系结构 习题集3 2002年春 学生每三人分成一个小组合作完成作业。每组只需要交一份该习盟的容案。在定课 程开始的时候，会布置作业。为了便于评分，各种习愿必须鞋立分类。参考蓉案一经发故， 我们将不再接收作业。 月思集#3 习题1：Cache性能优化 在本题中，你将探时几种常用的编译优化方法用于提高Ca©he性能， 习题1.A循环拌序 考察一个1B的直接映射的Cache,每行4字。对于下面两个用C语言写的福环、计算 一个616的矩库各元素累加和。《各元素均为32位的整型数) Loop A Loop B for(i=0:i<64:i++) for(=0:j<16:j++) for(j-0:j16;j+) for(i-0:i(64:i++) su+=A[i][j】 Sum-=A[i][j] 更阵A按行违续存储在内存中，和Cache行的边界一致。假定其它变量均是分配在寄存 器中，且只有读写Cace才沙及到师库元素， 计算运行oopA和l0ogd时Cache发生的不命中率。这两个值是香一样？解释为什么一 样或不一样。 习题1B1分换 作为计算大矩降时《Ca中装不下)是高Cche性能的一种手段，我们在第8讲讨论 过分块技术。这里是一个没有采用分块技术的N阶方阵乘的一个简单例子， for(i=0:1《N:i+) for(j 0;j N:j++) 《r0: far(k=0:k《N:k++) r=r+Y[i]k]2k][: x[i][i】·r: 1 r是寄存题 (1)技行排列是折矩阵的同一行在存站器中相临
6.823 计算机体系结构 习题集#3 2002 年 春 学生每三人分成一个小组合作完成作业。每组只需要交一份该习题的答案。在预定课 程开始的时候，会布置作业。为了便于评分，各种习题必须独立分类。参考答案一经发放， 我们将不再接收作业。 习题集#3 习题 1：Cache 性能优化 在本题中，你将探讨几种常用的编译优化方法用于提高 Cache 性能。 习题 1.A 循环排序 考察一个 1KB 的直接映射的 Cache，每行 4 字。对于下面两个用 C 语言写的循环、计算 一个 64*16 的矩阵各元素累加和。（各元素均为 32 位的整型数） Loop A Loop B for(i=0;i<64;i++) for(j=0;j<16;j++) for(j=0;j<16;j++) for(i=0;i<64;i++) sum+=A[i][j] sum+=A[i][j] 矩阵 A 按行连续存储在内存中，和 Cache 行的边界一致。假定其它变量均是分配在寄存 器中，且只有读写 Cache 才涉及到矩阵元素。 计算运行 Loop A 和 LoopB 时 Cache 发生的不命中率。这两个值是否一样？解释为什么一 样或不一样。 习题1.B：分块 作为计算大矩阵时（Cache 中装不下）提高 Cache 性能的一种手段，我们在第 8 讲讨论 过分块技术。这里是一个没有采用分块技术的 N 阶方阵乘的一个简单例子。 for(i = 0; i < N; i++) for(j = 0; j < N; j++) { r=0; for(k = 0; k < N; k++) { r = r + Y[i][k]*Z[k][j]; } X[i][j] = r; } r是寄存器 （1）按行排列是指矩阵的同一行在存储器中相临
下面是一个使用分块技术的的执行，B*块： for(jj 0:jj N:jj +B) rkk=0:k《N:kk+eB助 for(i=0:i《N:i++) for(j=jj:j<min(jj+B.N).j++) r=0 for(k kk:k nin(kk+B.N)ktt) r=r+Y[i][k]◆2kJ[]: x[i[U】+er田 为了看到分块是如何工作的，我们用替换策略来核抓Cac的行为，其中，N=4,=2, 全关联写分配ache,两字的行大小。假设矩阵和Cace行的边界是对齐的，而且编译不需对 读写再排序。对于两个矩阵相乘的执行，完成表1-1和表1-2，并说明党访月发生时Cache 内容的变化过程。当一个值发生变化时，把相匣的元素填在表中，或当Cche命中时，在相 应的地方填写阳1订。计算两种基于表中项的同执行的不金中率。 习题1C大块分块 Ben Bididdle正在用B部分的分块算法实现矩阵乘。他假设如果它能使两个最内的循环 算法运行时不发生Ce不命中、面非强制性不命中，他就应当脆得到一个合理的性能。 Bem的执行运行在UltraSPARC-l上，带一个直接陕射写直达不分配Cache,此时忽略冲 突未命中，如果Bem用B的分块技术，那么数据缓存必须多大？假设只有Cae读写涉及矩 阵的元素（即，其他变量分配在寄存器中）。 使用你的结果来计算B幅的执行可以选择的最大植，UltraSPARC-有一个I6KB的数据 Cache。 Bm的代码对30003000的矩阵进行运算，矩阵元素为32位的整形植，内存中按行存 放。他进行了一些核数。并且发现他的特殊数据放置和c配置间有一些冲突不命 中，但不是很多，因此没有过于关心。然面，当他在U世SPARC-】上使用最大块（你所计 算的》进行代码测试时，性能并不好，A认为月题可能出在T刀B上。 请解释T几B是怎么引起这个月题的。UltraSPARC-上的T几B是64行的全关联Ca: 页数是8K,用软件处理TLB未命中。你可以假设使用的是LRU替换策略。数据cahe是 虚报标签和虚凯索引
下面是一个使用分块技术的的执行，B*B块： for(jj = 0; jj < N; jj += B) for(kk = 0; kk < N; kk += B) for(i = 0; i < N; i++) for(j = jj; j < min(jj+B, N); j++) { r = 0; for(k = kk; k < min(kk+B, N); k++) { r = r + Y[i][k]*Z[k][j]; } X[i][j] += r; } 为了看到分块是如何工作的，我们用LRU替换策略来模拟Cache的行为，其中，N=4，B=2， 全关联写分配Cache，两字的行大小。假设矩阵和Cache行的边界是对齐的，而且编译不需对 读写再排序。对于两个矩阵相乘的执行，完成表 1-1 和表 1-2，并说明党访问发生时Cache 内容的变化过程。当一个值发生变化时，把相应的元素填在表中，或当Cache命中时，在相 应的地方填写HIT。计算两种基于表中项的同执行的不命中率。 习题 1.C 大块分块 Ben Bitdiddle 正在用 B 部分的分块算法实现矩阵乘。他假设如果它能使两个最内的循环 算法运行时不发生 Cache 不命中、而非强制性不命中，他就应当能得到一个合理的性能。 Ben 的执行运行在 UltraSPARC-I 上，带一个直接映射写直达不分配 Cache。此时忽略冲 突未命中，如果 Ben 用 B 的分块技术，那么数据缓存必须多大？假设只有 Cache 读写涉及矩 阵的元素（即，其他变量分配在寄存器中）。 使用你的结果来计算 Ben 的执行可以选择的最大值。UltraSPARC-I 有一个 16KB 的数据 Cache。 Ben 的代码对 3000*3000 的矩阵进行运算，矩阵元素为 32 位的整形值，内存中按行存 放。他进行了一些 cache 模拟，并且发现他的特殊数据放置和 cache 配置间有一些冲突不命 中，但不是很多，因此没有过于关心。然而，当他在 UltraSPARC-I 上使用最大块（你所计 算的）进行代码测试时，性能并不好。Alyssa 认为问题可能出在 TLB 上。 请解释 TLB 是怎么引起这个问题的。UltraSPARC-I 上的 TLB 是 64 行的全关联 Cache。 页数是 8K。用软件处理 TLB 未命中。你可以假设使用的是 LRU 替换策略。数据 cache 是 虚拟标签和虚拟索引
习题1D换一种思推 当草果机第一次在他们的机器里开始使用PowerPC处理器时，他们在公司范围内展开 了一次竟赛，看能写出最快的块移动(BlockMow)程序。这是个库程序，把若干个字节 从一个内存位置持舅到另一个位置。 前两名竟争者是一个微码程序员和一个计算机架构师，也们的块移动的实现是至今公司 里最快的。Bn在竿果公可里实习，并且看到了他们的代码。他注意到两个程序都用到了 PowerPC的dkz汇编指令，可以在一个周期执行，语意如下： debz rA.rB 如果包含由rHB)厅址的字节的块在数据cche里，该块中所有的字节清零. 如果该块不在数据C©he中，把该块分配于数据cae中，且不从内存区该块，。所有块 的字节清零。 B▣知道所以学生做完了习题集2，现在都是有经险的微码程序员或架构师。也也想在 革果公可得到提升，所以需要你的帮助。清解释db2是如何用于优化块移动程序的。还有 一个或许重要的信息是PowerPC处理器使用的是写分配cache. C Table 1-1:Matrix Mulltiply Without Blocking Line O Line 1 Line 2 Lire 3 Lie 4 0[9 互0[0 1.C Table 1-2:Matrix Mulnply With Blocking Line 0 Line 1 Line 2 0】1ala1mw1a 1 Y[oJo Yo1 HIT
习题 1.D 换一种思维 当苹果机第一次在他们的机器里开始使用 PowerPC 处理器时，他们在公司范围内展开 了一次竞赛，看谁能写出最快的块移动（BlockMove）程序。这是个库程序，把若干个字节 从一个内存位置拷贝到另一个位置。 前两名竞争者是一个微码程序员和一个计算机架构师。他们的块移动的实现是至今公司 里最快的。Ben 在苹果公司里实习，并且看到了他们的代码。他注意到两个程序都用到了 PowerPC 的 dcbz 汇编指令，可以在一个周期执行，语意如下： dcbz rA, rB 如果包含由 (rA)+(rB)寻址的字节的块在数据 cache 里，该块中所有的字节清零。 如果该块不在数据 Cache 中，把该块分配于数据 cache 中，且不从内存区该块，所有块 的字节清零。 Ben 知道所以学生做完了习题集 2，现在都是有经验的微码程序员或架构师。他也想在 苹果公司得到提升，所以需要你的帮助。清解释 dcbz 是如何用于优化块移动程序的。还有 一个或许重要的信息是 PowerPC 处理器使用的是写分配 cache
习题2：内存 习题2A 内存单元分配 Bca有一个C程序，其中的一个数组定文格式为unsigned int4I6],unsigned ir世为32 位。服设a〔0们[0]地址是0x0,a[0][1】地址是0x4。请展示数组元素是如同晚射到不同的内 存单元内的。每个内存单元是32位或4字节大小。 bank mumber(address bank width in bytes)MOD NumBaniks address within bank-address MOD mimber of bytes in bank Address within Bank BANK 0 BANK 1 BANK 2 BANK 3 BANK 4 0x00 afo:1o] 0x04 0需0日 0x0G日 0x10 014 0x18 0K1日 习愿2.B 交又内存 假设机器和cache性能有下面的描述： ·发送地址：4个时周期 ·访问一个字：24个时钟圆期 发送一个字的数据：4个时钟周期 每条指令访问12次内存 每条指令平均1.5个周期（三略eahe不命中） cache块大小：一个字 一个字的内存总线宽度 如果这个配置的不命中单是3%，那么这个系统的C是多少？ 如果我们把cache块的大小改成两个字，不命中率会降到2%。如果我们把cche块的 大小改成四个字，不衡中率会降到1%。那么对于两字的Ce块和双体交叉内存，C刊
习题 2：内存 习题 2.A 内存单元分配 Ben 有一个 C 程序，其中的一个数组定义格式为 unsigned int a[4][6]。unsigned int 为 32 位。假设 a[0][0]地址是 0x0，a[0][1]地址是 0x4。请展示数组元素是如何映射到不同的内 存单元内的。每个内存单元是 32 位或 4 字节大小。 习题2.B 交叉内存 假设机器和cache性能有下面的描述： z 发送地址：4个时钟周期 z 访问一个字：24个时钟周期 z 发送一个字的数据：4个时钟周期 z 每条指令访问1.2次内存 z 每条指令平均1.5个周期（忽略cache不命中） z cache块大小：一个字 z 一个字的内存总线宽度 如果这个配置的不命中率是 3%，那么这个系统的 CPI 是多少？ 如果我们把 cache 块的大小改成两个字，不命中率会降到 2%。如果我们把 cache 块的 大小改成四个字，不命中率会降到 1%。那么对于两字的 Cache 块和双体交叉内存， CPI
是多少？那么用四字Cae的块和四体内存，CP叫又是多少？较大的块的优点或缺点是什 么1 习题3：腹拟内存位 在这个问题中，我们考虑一个带简单虚拟内存增强的X执行。每个页表项会把一个虚 数页号(VP)肤射为一个物理页号(PW),除了页号的转换外，每个真表项还包含一些许 可/状态位。 Bit Name Bit Definition PPN/DBN Physical Page Number/Disk Block Number V(valid) 1 if the page table entry is valid 0 otherwise R(residenr) 1ihep2婴e is resider如ln2Bc.0Gham1s@ W (writable) 1 if the page is writable,0 otherwise U(used) 1 if the page has been accessed recently,0 otherwise M(modified) 1 if the page has been modified,0 ocherwise S(supervisor) 1 if the page is only accessible supervisor mode.0 ocberwise 卫B中的每个项有一个标记(g),匹配于VPW,和一个LB项有效位（注意，TLB 项有效位不是上面表中的V位)。如果TLB项有效，则TLB项有效位将置1。每个T几B项 中也包含上面给出的页表中所有域。 一个几B不命中(VW限所有有效位为1的项的标记均不匹配)产生一个异常，对于 一个B不命中，内核软件将重新把页表项装入几B,并将重新访问内存。（内核载件可以 修改几B中的一切，它一般按超级模式运行)如果被替换的项是有效的，那么内楼会把被 置换的TB项写回真表。 一且T几B和对应的项命中，硬件将设置5则位。类似地，当写页表发生时，(B项 中的》修改位将被设置。 所有来自B的异常（命中成未命中）由软件处理。例如，以下可能出现的异常 TLB不金中：VN果有效位为1的那些项的标记不匹配： 页表项无效：试图访问未对应物理地址的虚拟页： 写出情： 试图修改具读的页(W为0) 保护冲突 用户核式下试图访问一个按保护的页 页故障： 页未在内存。 (除十特别注意，者则异常在读和写的时候都可修发生)。 习愿3.A 一旦一个T1B项敲替换，我们军把整个项写日到页表中。Bn认为这是对内存带宽的浪 费。他认为只雷写回一部分数据位。对于每个位，解释他们为什么需要或不需要写回。 带着这种思想，通过后面的问题，我们米看看如何把每个B项实际需要的位数最小化， 习题3.B 如不喜欢TB设计，他认为B项的有效位应该取消，应该政变内核软件，确保所有 的几B项都有效。这是个好办法吗？解释这个设计的优点和缺点。 习题3，C A1yssa考虑了B如的方法并建议了一个不同的消除一个有效位的方案。她认为页表项有效 和TB项有效位可以合成一位
是多少？那么用四字 Cache 的块和四体内存，CPI 又是多少？较大的块的优点或缺点是什 么？ 习题 3：虚拟内存位 在这个问题中，我们考虑一个带简单虚拟内存增强的 DLX 执行。每个页表项会把一个虚 拟页号（VPN）映射为一个物理页号（PPN）。除了页号的转换外，每个页表项还包含一些许 可/状态位。 TLB 中的每个项有一个标记（tag），匹配于 VPN，和一个 TLB 项有效位（注意，TLB 项有效位不是上面表中的 V 位）。如果 TLB 项有效，则 TLB 项有效位将置 1。每个 TLB 项 中也包含上面给出的页表中所有域。 一个 TLB 不命中（VPN 跟所有有效位为 1 的项的标记均不匹配）产生一个异常。对于 一个 TLB 不命中，内核软件将重新把页表项装入 TLB，并将重新访问内存。（内核软件可以 修改 TLB 中的一切，它一般按超级模式运行）如果被替换的项是有效的，那么内核会把被 置换的 TLB 项写回页表。 一旦 TLB 和对应的项命中，硬件将设置 used 位。类似地，当写页表发生时，（TLB 项 中的）修改位将被设置。 所有来自 TLB 的异常（命中或未命中）由软件处理。例如，以下可能出现的异常： TLB 不命中： VPN 跟有效位为 1 的那些项的标记不匹配； 页表项无效： 试图访问未对应物理地址的虚拟页； 写出错： 试图修改只读的页（W 为 0） 保护冲突： 用户模式下试图访问一个被保护的页； 页故障： 页未在内存。 （除非特别注意，否则异常在读和写的时候都可能发生）。 习题 3.A 一旦一个 TLB 项被替换，我们都把整个项写回到页表中。Ben 认为这是对内存带宽的浪 费。他认为只需写回一部分数据位。对于每个位，解释他们为什么需要或不需要写回。 带着这种思想，通过后面的问题，我们来看看如何把每个 TLB 项实际需要的位数最小化。 习题 3.B Ben 不喜欢 TLB 设计。他认为 TLB 项的有效位应该取消，应该改变内核软件，确保所有 的 TLB 项都有效。这是个好办法吗？解释这个设计的优点和缺点。 习题 3.C Alyssa 考虑了 Ben 的方法并建议了一个不同的消除一个有效位的方案。她认为页表项有效 和 TLB 项有效位可以合成一位
替换后合成的有效位将包含页表项有效位的值。通过写回到页表，设置几B项中合成有 效位为无效，令TB项变为无效。 那么内核软件需要怎样改变，米使这种方案工作？B产生的异常如何变化？ 习题3.D 现在，dJet参与到这个项目里.他想维续保特B项有效位。但是，没有办法在每个T几B 项中有两个有效位《一个B项有效位，一个真表项有效位)。所以，他决定从B项中腹 葬页表有效位。 内核款件怎么改变可以使其根好地工作？TB产生的异常会有什么变化？ 习题3E 把你的答案与习题3C与3D的答案比较。那个方案有更好的性能？ 习题3F R位又怎样？我们能香把它从TB项中去除，而不对性修产生大的影响？简要解释之， 习题3.G 处理器有一个超级用户方式位。只要内核就件执行，这个位都置1。当usr代码执行 到，这个位不置1。部分us心r的虚拟地址空间只能由内核访问。页表中的超缓用户位用案 保护这个区域。如果用户塑要访问一个超级用户位为1的页，就会发生异常， BdJt不以为然。他决定取消TLB项中的超级用户位。请解释内核状件需要怎样变化， 使得我们仍燃可以有保护机制，并且内核可以通过虚拟内存系统访问这些页。 习题3H As网P Hacker认为Bn和Bud对这些位的要求有点过于欧毛求藏。但是仍然设计了 一个TLB项不需要M位和U位的方案。工作方式如下。如果在一次读的时候发生TB不 合中，那么从内存中读页表项并收入几B,但是。在这种情况下，W位经常被置为0。请 给出该方案其余部分工作的细节（写的时候会发生什么，什么时候项需要写回到内存。什么 时候页表中的U位和M位被修改等). 习愿4：6耐位虚报内存 Bm正在对使用64位内存地址的想法进行试验。 习愿4A 在只使用单缓页表的情况下，页表会有多大？假设每一页是4KB,每个页表项4个学 节，并且处理器是字节寻址。 习题4B Bm可读了最近的技术刊物，发现当前很多64位的[SAs只实现了部分大叔地址空间. 它们通常把虚数地址空间分制成以下三部分：一部分用于栈，一部分川于代码和堆数据，一 部分表使用
替换后合成的有效位将包含页表项有效位的值。通过写回到页表、设置 TLB 项中合成有 效位为无效，令 TLB 项变为无效。 那么内核软件需要怎样改变，来使这种方案工作？TLB 产生的异常如何变化？ 习题 3.D 现在，Bud Jet 参与到这个项目里。他想继续保持 TLB 项有效位。但是，没有办法在每个 TLB 项中有两个有效位（一个 TLB 项有效位，一个页表项有效位）。所以，他决定从 TLB 项中放 弃页表有效位。 内核软件怎么改变可以使其很好地工作？TLB 产生的异常会有什么变化？ 习题 3.E 把你的答案与习题 3.C 与 3.D 的答案比较。哪个方案有更好的性能？ 习题 3.F R 位又怎样？我们能否把它从 TLB 项中去除，而不对性能产生大的影响？简要解释之。 习题 3.G 处理器有一个超级用户方式位。只要内核软件执行，这个位都置 1。当 user 代码执行 时，这个位不置 1。部分 user 的虚拟地址空间只能由内核访问。页表中的超级用户位用来 保护这个区域。如果用户想要访问一个超级用户位为 1 的页，就会发生异常。 Bud Jet 不以为然，他决定取消 TLB 项中的超级用户位。请解释内核软件需要怎样变化， 使得我们仍然可以有保护机制，并且内核可以通过虚拟内存系统访问这些页。 习题 3.H Alyssa P. Hacker 认为 Ben 和 Bud 对这些位的要求有点过于吹毛求疵。但是仍然设计了 一个 TLB 项不需要 M 位和 U 位的方案。工作方式如下。如果在一次读的时候发生 TLB 不 命中，那么从内存中读页表项并放入 TLB。但是，在这种情况下，W 位经常被置为 0。请 给出该方案其余部分工作的细节（写的时候会发生什么，什么时候项需要写回到内存，什么 时候页表中的 U 位和 M 位被修改等）。 习题 4：64 位虚拟内存 Ben 正在对使用 64 位内存地址的想法进行试验。 习题 4.A 在只使用单级页表的情况下，页表会有多大？假设每一页是 4KB，每个页表项 4 个字 节，并且处理器是字节寻址。 习题 4.B Ben 阅读了最近的技术刊物，发现当前很多 64 位的 ISAs 只实现了部分大虚拟地址空间。 它们通常把虚拟地址空间分割成以下三部分：一部分用于栈，一部分用于代码和堆数据，一 部分未使用
OxErFFETETEYETFYET Reserved for Stack 0×8700000000000000 OxQQFFFFFFFFFFFFFE Reserved for Code and Heap 0x0000000000000000 在地址被送入虚拟内存系统前，通过一个特殊的电路来检测地址的高8位是全零还是全 一。如果它门不全相等。就设置无效虚拟内存地址陷讲位。此方案能有效地从虚报内存地址 中去除高7位，同时保留内存布局与未来实观大规模虑拟地址空间的设计兼容。 B如喜欢这个想法，但是想得到一个更便宜的虚报内存系统。他决定去除高22位，具 使用低2位素引虚拟内存。现在单级页表有多大？ 习题4.C B还是对页表的大小不满意，让你使一个用3级页表，把42位的地址转换成3个10 位的页索引和一个2位的页偏移量。如果页表开销定义为： 一个用户型序的贾表使用的物厘内用户代母。雄和栈使用的物密内存 3级分层方案可能的最小页表开销是多少？要记住，即使只使用一个T正，也要分配一 个完整的页表(1024个PT正)。假设物理内存是够大，设有页交换到硬盘， 3级分层方案可修的最大页表开精是多少？假设一个用户页一旦分配在内存，认为整个 页都有用。 习愿4D Alyssa P.Hacker对于该方案引起的虚数地址空间大洞非常不满。她决定使用一个哈希页 表。此外，这种机器使用64位的虚拟地址和4KB的页。硬件内存分页系统风有一个64行 的页表，每行含PTF,A小sm决定使用Xm0d64作为哈希函数来遗择行，其中X是VPN, 页表驻留在内存，且Aa的设计里没有TLB,所以每次读PT正藏香要一次内存访间。在 一次页表查询中，每行里的所有PT正依次查询。如果页表有一个缺项，陷启动际位，软件 处理程序会重新填充真表，平均每次填充需要10次内存访问的时间。 A5超运行一个很简单的基准数据。该基准数据在一个有2字节的数组上重复循环， 在连续地址顺序上一次读一字节。在稳定的情况下，用户程序读取每个字节平均需要执行多 少次内存访月？忽略指◆费取的内存业务，服设数组始于页边界，并且除了一个字节的内存 访问外，用户代码中没有其他的内存访问。 习题4E A5a现在决定给被哈希的内存分页系统添加一个单项的LB。在A山y✉的基准数据 中，用户每读取一个字节的平均内存访问次数是多少？
在地址被送入虚拟内存系统前，通过一个特殊的电路来检测地址的高 8 位是全零还是全 一。如果它们不全相等，就设置无效虚拟内存地址陷阱位。此方案能有效地从虚拟内存地址 中去除高 7 位，同时保留内存布局与未来实现大规模虚拟地址空间的设计兼容。 Ben 喜欢这个想法，但是想得到一个更便宜的虚拟内存系统。他决定去除高 22 位，只 使用低 42 位索引虚拟内存。现在单级页表有多大？ 习题 4.C Ben 还是对页表的大小不满意，让你使一个用 3 级页表，把 42 位的地址转换成 3 个 10 位的页索引和一个 12 位的页偏移量。如果页表开销定义为： 一个用户程序的页表使用的物理内存/用户代码、堆和栈使用的物理内存 3 级分层方案可能的最小页表开销是多少？要记住，即使只使用一个 PTE，也要分配一 个完整的页表（1024 个 PTEs）。假设物理内存足够大，没有页交换到硬盘。 3 级分层方案可能的最大页表开销是多少？假设一个用户页一旦分配在内存，认为整个 页都有用。 习题 4.D Alyssa P.Hacker 对于该方案引起的虚拟地址空间大洞非常不满。她决定使用一个哈希页 表。此外，这种机器使用 64 位的虚拟地址和 4KB 的页。硬件内存分页系统只有一个 64 行 的页表，每行含 8PTEs。Alyssa 决定使用 X mod 64 作为哈希函数来选择行，其中 X 是 VPN。 页表驻留在内存，且 Alyssa 的设计里没有 TLB，所以每次读 PTE 就需要一次内存访问。在 一次页表查询中，每行里的所有 PTEs 依次查询。如果页表有一个缺项，陷启动阱位，软件 处理程序会重新填充页表，平均每次填充需要 10 次内存访问的时间。 Alyssa 运行一个很简单的基准数据，该基准数据在一个有 221 字节的数组上重复循环， 在连续地址顺序上一次读一字节。在稳定的情况下，用户程序读取每个字节平均需要执行多 少次内存访问？忽略指令获取的内存业务，假设数组始于页边界，并且除了一个字节的内存 访问外，用户代码中没有其他的内存访问。 习题 4.E Alyssa 现在决定给被哈希的内存分页系统添加一个单项的 TLB。在 Alyssa 的基准数据 中，用户每读取一个字节的平均内存访问次数是多少？