并行体系结构(陈国良版)课后答案.pdf

《并行体系结构(陈国良版)课后答案.pdf》由会员分享，可在线阅读，更多相关《并行体系结构(陈国良版)课后答案.pdf（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 1指导思想指导思想要求学生理解高端并行计算机系统设计技术，高端MPP、DSM、CLUSTER 等大规模并行计算机的关键设计理论和实现技术，包括互连网络技术、存储架构和高可用技术等。为此，必须用适量的作业、习题，启发学生独立思考以及熟练掌握一些基础知识习题设计计划和基本技能。2 2作业安排作业安排本教材每一章都附有大量的习题，根据教学进度和学时，合理选择书上习题，以达到进一步加深理解课堂讲授的内容。每一章讲授结束，收一次作业，给出成绩，并作一次集体答疑，讲解作业中的共性问题。作业成绩记入总成绩内。第一章 绪论什么是并行计算机答：简单地讲，并行计算机就是由多个处理单元组成的计算机系统，这些处理

2、单元相互通信和协作，能快速高效求解大型的复杂的问题。简述 Flynn 分类法：答：根据指令流和数据流的多重性将计算机分为：】1）单指令单数据流 SISD2）单指令多数据流 SIMD3）多指令单数据流 MISD4）多指令多数据流 MIMD简述当代的并行机系统答：当代并行机系统主要有：1）并行向量机（PVP）2）3）对称多处理机（SMP）4）大规模并行处理机（MPP）5）6）分布式共享存储（DSM）处理机7）工作站机群（COW）为什么需要并行计算机答：1）加快计算速度2）提高计算精度；3）满足快速时效要求4）进行无法替代的模拟计算简述处理器并行度的发展趋势答：1）位级并行2）指令级并行3）线程级并

3、行简述 SIMD 阵列机的特点.答：1）它是使用资源重复的方法来开拓计算问题空间的并行性。2）所有的处理单元（PE）必须是同步的。3）阵列机的研究必须与并行算法紧密结合，这样才能提高效率。4）阵列机是一种专用的计算机，用于处理一些专门的问题。简述多计算机系统的演变答：分为三个阶段：1）1983-1987 年为第一代，代表机器有：Ipsc/1、Ameteks/14等。2）1988-1992 年为第二代，代表机器有：Paragon、Intel delta 等。3）1993-1997 年为第三代，代表机器有：MIT 的 J-machine。简述并行计算机的访存模型答：1）均匀存储访问模型（UMA）2

4、）非均匀存储访问模型（NUMA）3）全高速缓存存储访问模型（COMA）4）高速缓存一致性非均匀访问模型（CC-NUMA）简述均匀存储访问模型的特点答：1）物理存储器被所有处理器均匀共享。2）所有处理器访问任何存储字的时间相同。3）每台处理器可带私有高速缓存。4）外围设备也可以一定的形式共享。简述非均匀存储访问模型的特点答：1）被共享的存储器在物理上分布在所有的处理器中，其所有的本地存储器的集合构成了全局的地址空间。|2）处理器访问存储器的时间不一样。3）每台处理器可带私有高速缓存，外备也可以某种的形式共享。第二章 性能评测使用 40MHZ 主频的标量处理器执行一个典型测试程序，其所执行的指令数

5、及所需的周期数如表所示。试计算执行该程序的有效CPI、MIPS 速率及总的 CPU 执行时间。解：CPI=total cycles/total instructions=（45000*1+32000*2+15000*2+8000*2）/（45000+32000+15000+8000）=MIPS=时钟频率/(CPI*106)=(40*106)/*106)=CPU 执行时间=total cycles/时钟频率=欲在 40MHZ 主频的标量处理器上执行20 万条目标代码指令程序。假定该程序中含有4 种主要类型之指令，各指令所占的比例及CPI 数如表所示，试计算：在单处理机上执行该程序的平均CPI。由

6、所得结果，计算相应的MIPS 速率。解：（1）CPI=1*60%+2*18%+4*12%+8*10%=（2）MIPS=时钟频率/(CPI*106)=(40*106)/*106)=2.1 已知 SP2 并行计算机的通信开销表达式为：t（m）=46+（）m，试计算：渐近带宽 r=m12半峰值信息长度=提示：to=46s解：（1）渐近带宽 r=1/=S(2)半峰值消息长度 m1/2=to*r=46us*S=并行机性能评测的意义。答：意义有：1）发挥并行机长处，提高并行机的使用效率。2）减少用户购机盲目性，降低投资风险。3）改进系统结构设计，提高机器的性能。4）促进软/硬件结合，合理功能划分。5）优化

7、“结构-算法-应用”的最佳组合。6）提供客观、公正的评价并行机的标准。如何进行并行机性能评测答：1）机器级性能评测：CPU 和存储器的某些基本性能指标；并行和通信开销分析；并行机的可用性与好用性以及机器成本、价格与性/价比。2）算法级性能评测：加速比、效率、扩展性。3）程序级性能评测：Benchmark。简述 Gustafson定律的出发点答：1）对于很多大型计算，精度要求很高，即在此类应用中精度是个关键因素，而计算时间是固定不变的。此时为了提高精度，必须加大计算量，相应地亦必须增多处理器数才能维持时间不变。2）除非学术研究，在实际应用中没有必要固定工作负载而计算程序运行在不同数目的处理器上，

8、增多处理器必须相应地增大问题规模才有实际意义。已知一程序可并行代码占比例为80%，将其在有 10 个处理器的系统中运行，求其加速比并求其极限加速比并分析其结构带来的影响解：加速比=1/(20%+80%/10)=1/+=。极限加速比，即处理器个数无穷大的时候呈现的加速比=1/20%=5。这个极限加速比，换个角度说是，Amdahl 定律在很长一段时间影响了人们对开发并行计算机的信心，对于本例，因为就算你把处理器做到无穷也只能得到5 倍的加速比，同时有一点更明显，就是处理器数目增加到一定程度后，加速比的增长非常缓慢。简述影响加速的因素答：1）求解问题中的串行分量。2）并行处理器所引起的额外开销。:3

9、）加大的处理器数超过的算法的并发程度。为什么增加问题规模可以在一定程度提高加速答：1）较大的问题规模可提高较大的并发度。2）额外开销的增加可能慢于有效计算的增加。3）算法中串行分量的比例不是固定不变的。进行可扩放行研究的主要意义答：1）确定解决某类问题用某类并行算法和某类并行体系结构结合，可以有效的利用大量的处理器。2）对于运行于某种体系结构的并行机的某种算法当移到大规模处理机上的性能。3）对于某类固定规模的问题，确定在某类并行机上的最优处理器数目和最大的加速比。4）用于指导改进并行算法和并行体系结构，以使并行算法能尽可能充分利用可扩充的。大量的处理器。第三章 互连网络对于一颗 K 级二叉树（

10、根为 0 级，叶为 k-1 级），共有 N=2k-1 个节点，当推广至 m-元树时（即每个非叶节点有 m 个子节点）时，试写出总节点数N 的表达式。答：!推广至 M 元树时，k 级 M 元树总结点数 N 的表达式为：N=1+m1+m2+.+m（k-1）=(1-mk)*1/(1-m);二元胖树如图所示，此时所有非根节点均有2 个父节点。如果将图中的每个椭圆均视为单个节点，并且成对节点间的多条边视为一条边，则他实际上就是一个二叉树。试问：如果不管椭圆，只把小方块视为节点，则他从叶到根形成什么样的多级互联网络答：8 输入的完全混洗三级互联网络。四元胖树如图所示，试问：每个内节点有几个子节点和几个父节

11、点你知道那个机器使用了此种形式的胖树答：每个内节点有 4 个子节点，2 个父节点。CM-5 使用了此类胖树结构。试构造一个 N=64 的立方环网络，并将其直径和节点度与N=64 的超立方比较之，你的结论是什么答：AN=64 的立方环网络,为 4 立方环（将4 维超立方每个顶点以4 面体替代得到），直径d=9，节点度 n=4BN=64 的超立方网络，为六维超立方（将一个立方体分为8 个小立方，以每个小立方作为简单立方体的节点，互联成6 维超立方），直径 d=6，节点度 n=6一个 N=2k 个节点的 de Bruijin 网络如图所示，令ak1ak2ak3。a1a0，是一个节点的二进制表示，则该

12、节点可达如下两个节点：ak2ak3。a1a00，ak2ak3。a1a01。试问：该网络的直径和对剖宽度是多少答：N=2k 个节点的 de Bruijin 网络 直径 d=k 对剖宽带 w=2(k-1)￥一个 N=2n 个节点的洗牌交换网络如图所示。试问：此网络节点度=网络直径=网络对剖宽度=答：N=2n 个节点的洗牌交换网络，网络节点度为=2，网络直径=n-1，网络对剖宽度=4一个 N=（k+1）2k 个节点的蝶形网络如图所示。试问：此网络节点度=网络直径=网络对剖宽度=答：N=（k+1）2k 个节点的蝶形网络，网络节点度=4，网络直径=2*k，网络对剖宽度=2k对于如下列举的网络技术，用体系

13、结构描述，速率范围，电缆长度等填充下表中的各项。（提示：根据讨论的时间年限，每项可能是一个范围）答：网络技术Myrinet网络结构.带宽200MB/秒800Mbps铜线距离光纤距离25m500m专用机群互联网络HiPPI用于异构计算机和其外设的组网SCI?300m10km25m250Mbps8Gbps50m可扩展一致性接口，通常独立于拓扑结构多处理器和其外围设备之间，100Mbps800直连结构主要应用于因特网主干线中Mbps?10km光纤通信ATM25Mbps10GbpsFDDI采用双向光纤令牌环，所有结点联接在该环中如图所示，信包的片0，1，2，3 要分别去向目的地 A，B，C，D。此时片

14、0 占据信道 CB，片 1 占据信道 DC，片 2 占据信道 AD，片 3 占据信道 BA。试问：1）这将会发生什么现象100-200Mbps100m；2KM2）如果采用 X-Y选路策略，可避免上述现象吗为什么答：1）通路中形成环，发生死锁2）如果采用 X-Y策略则不会发生死锁。因为采用X-Y策略时其实质是对资源（这里是通道）进行按序分配（永远是x 方向优先于 y 方向，反方向路由是y 方向优先于 x 方向），因此根据死锁避免的原则判断，此时不会发生死锁。在二维网孔中，试构造一个与X-Y选路等价的查表路由。答：所构造路由表描述如下：1）每个节点包括两张路由表x 表和 y 表2）每个节点包含其以

15、后节点信息，如节点【1，2】x 表内容为:【2，2】【3，2】y 表内容为：【1，3】选路方法：节点路由时进行查表：先查x 表即进行 x 方向路由，如果查表能指明下一跳方向则直接进入下一跳。如果不能则继续查y 表，直到到达目的地。)第四章 对称多处理机系统参照图，试解释为什么采用 WT 策略进程从P2迁移到P1时，或采用 WB 策略将包含共享变量 X 的进程从P1迁移到P2时，会造成高速缓存的不一致。处理器P1P2P1P2P1P2高速缓存XXXXX总线共享存储器XXX迁移之前写通过写回图 进程迁移所造成的不一致性答：采用 WT 策略进程从P2迁移到P1后，P2写共享变量 X 为 X，并且更新主

16、存数据为X，此时P1共享变量值仍然为 X，与P2和主存 X不一致。采用 WB 策略进程从P1迁移到P2后，P1写共享变量 X 为 X，但此时P2缓存与主存变量值仍然为X，造车不一致。n1，b1=b2，且替换策略用 FIFO 来代替 LRU，试问包含性是否还是自然满足如果替换策略是随机替换呢答：如果采用 FIFO 替换策略包含性自然满足，因为L1 和 L2 都是 2 路组相联，FIFO 保证了L1 与 L2 在发生替换时会换出相同的缓存块，维护了包含性。如果采取随机替换策略，存在L1 与 L2 替换不是相同块的情况，故不满足包含性。，4.7 针对以下高速缓存情况，试给出一个使得高速缓存的包含性不

17、满足的内存存取序列L1 高速缓存容量 32 字节，2-路组相联，每个高速缓存块 8 个字节，使用 LRU 替换算法；L2 高速缓存容量 128 字节，4-路组相联，每个高速缓存块 8 个字节，使用 LRU 替换算法。答：假设 m1、m2、m3 块映射到一级 Cache 和二级 Cache 的同一组中，考虑如下内存存取序列 Rm1，Rm2，Rm1，Rm3，由 LRU 替换算法知道，当 Rm3执行后，L1 中被替换出的是 m2，L2 中被替换出的是 m1，此时 m1 块在 L1 却不在 L2 中，不满足包含性。4.84.9在中关于分事务总线的讨论中，依赖于处理器与高速缓存的接口，下面情况有可能发生

18、：一个使无效请求紧跟在数据响应之后，使得处理器还没有真正存取这个高速缓存块之前，该高速缓存块就被使无效了。为什么会发生这种情况，如何解决答：考虑如下情景：SMP 目录一致性协议中，核1 读缺失请求数据块 A，主存响应请求传送数据块 A 给核 1，同时核 2 对数据块 A 进行写操作，到主存中查得核 1 拥有副本，向核 1发使无效请求。如此，一个使无效请求紧跟在数据响应之后。解决方法，可以使每个核真正存取高速缓存块后向主存发回应，然后再允许其它对此块操作的使无效或其它请求。4.10 利用 LL-SC 操作实现一个 Test&Set操作。答：Test&Set：ll reg1,location/*L

19、oad-locked the location to reg1*/bnz reg1,lock/*if locatin was locked,try again*/mov reg2,1/*set reg2 1*/sc location,reg2/*store reg2 conditional into location*/4.114.12在 4.7.4 部分描述具有感觉反转的路障算法中，如果将Unlock 语句不放在 if 条件语句的每个分支中，而是紧接放在计数器增1 语句后，会发生什么问题为什么会发生这个问题答：再进入下一个路障时可能会发生计数器重新清0 现象，导致无法越过路障。考虑如下情景：

20、第一次进入路障时，最后两个进入路障的进程分别为1、2。假设最后进入路障的进程为 2 进程，2 进程执行共享变量加一操作并解锁。然后2 进程执行一条 if 条件语句，此时由于某种原因换出或睡眠，而此时共享变量的值已经为p。如果 1 进程此时正执行 if 条件语句，则清零计数器，设置标志，其它进程越过路障。到目前为止没有出现问题，问题出现在下一次进入路障。进程再一次进入路障，此时会执行共享变量加一操作。如果此时2 进程被换入或被唤醒，会重新清零共享变量，使之前到达路障的进程的加一操作无效，导致无法越过路障。第五章 大规模并行处理机系统简述大规模并行处理机的定义，原理和优点答：并行处理机有时也称为阵

21、列处理机，它使用按地址访问的随机存储器，以单指令流多数据流方式工作，主要用于要求大量高速进行向量矩阵运算的应用领域。并行处理机的并行性来源于资源重复，它把大量相同的处理单元（PE）通过互联网络（ICN）连接起来，在统一的控制器（CU）控制下，对各自分配来的数据并行地完成同一条指令所规定的操作。PE 是不带指令控制部件的算术逻辑运算单元。并行处理机具有强大的向量运算能力，具有向量化功能的高级语言编译程序有助于提高并行处理机的通用性，减少编译时间。并行处理机有两种基本结构类型，请问是哪两种并作简单介绍。答：采用分布存储器的并行处理结构和采用集中式共享存储器的并行处理结构。分布式存储器的并行处理结构

22、中，每一个处理机都有自己的存储器，只要控制部件将并行处理的程序分配至各处理机，它们便能并行处理，各自从自己的存储器中取得信息。而共享存储多处理机结构中的存储器是集中共享的，由于多个处理机共享，在各处理机访问共享存储器时会发生竞争。因此，需采取措施尽可能避免竞争的发生。简单说明多计算机系统和多处理机系统的区别。答：他们虽然都属于多机系统但是他们区别在于：（1）多处理机是多台处理机组成的单机系统，多计算机是多台独立的计算机。（2）多处理机中各处理机逻辑上受同一的OS 控制，而多计算机的 OS 逻辑上独立.(3)多处理机间以单一数据，向量。数组和文件交互作用，多计算机经通道或者通信线路以数据传输的方

23、式进行。（4）多处理机作业，任务，指令，数据各级并行，多计算机多个作业并行。举例说明 MPP 的应用领域及其采用的关键技术。答：全球气候预报，基因工程，飞行动力学，海洋环流，流体动力学，超导建模，量子染色动力学，视觉。采用的关键技术有VLSI，可扩张技术，共享虚拟存储技术。$多处理机的主要特点包括答：（1）结构的灵活性。与SIMD 计算机相比，多处理机的结构具有较强的通用性，它可以同时对多个数组或多个标量数据进行不同的处理，这要求多处理机能够适应更为多样的算法，具有灵活多变的系统结构。2）程序并行性。并行处理机实现操作一级的并行，其并行性存在于指令内部，主要用来解决数组向量问题；而多处理机的并

24、行性体现在指令外部，即表现在多个任务之间。3）并行任务派生。多处理机是多指令流操作方式，一个程序中就存在多个并发的程序段，需要专门的程序段来表示它们的并发关系以控制它们的并发执行，这称为并行任务派生。4）进程同步。并行处理机实现操作级的并行，所有处于活动状态的处理单元受一个控制器控制，同时执行共同的指令，工作自然同步；而多处理机实现指令、任务、程序级的并行，在同一时刻，不同的处理机执行着不同的指令，进程之间的数据相关和控制依赖决定了要采取一定的进程同步策略。在并行多处理机系统中的私有Cache会引起Cache中的内容相互之间以及与共享存储器之间互不相同的问题，即多处理机的Cache 一致性问题

25、。请问有哪些原因导致这个问题答：1）2）出现 Cache 一致性问题的原因主要有三个：共享可写的数据、进程迁移、I/O传输。共享可写数据引起的不一致性。比如 P1、P2 两台处理机各自的本地高速缓冲存储器 C1、C2 中都有共享存储器是 M 中某个数据 X 的拷贝，当P1 把 X 的值变成 X/后，如果P1 采用写通过策略，内存中的数据也变为X/，C2 中还是 X。如果通过写回策略，这是内存中还是X。在这两种情况下都会发生数据不一致性。2）进程迁移引起的数据不一致性。P1 中有共享数据X 的拷贝，某时刻 P1 进程把它修改为 X/并采用了写回策略，由于某种原因进程从 P1 迁移到了 P2 上，

26、它读取数据时得到 X，而这个 X 是“过时”的。3）I/O传输所造成的数据不一致性。假设 P1 和 P2 的本地缓存 C1、C2 中都有某数据 X 的拷贝，当I/O处理机将一个新的数据X/写入内存时，就导致了内存和Cache之间的数据不一致性。分别确定在下列两种计算机系统中，计算表达式所需的时间：s=A1*B1+A2*B2+A4*B4。a)有 4 个处理器的 SIMD 系统；b)有 4 个处理机的 MIMD系统。假设访存取指和取数的时间可以忽略不计；加法与乘法分别需要2 拍和 4 拍；在SIMD 和 MIMD系统中处理器（机）之间每进行一次数据传送的时间为1 拍；在 SIMD 系统中，PE 之

27、间采用线性环形互连拓扑，即每个 PE 与其左右两个相邻的 PE 直接相连，而在 MIMD 中每个 PE 都可以和其它 PE 有直接的的通路。答：假设 4 个 PE 分别为 PE0，PE1，PE2，PE3。利用 SIMD 计算机计算上述表达式，4 个乘法可以同时进行，用时=4 个时间单位；然后进行PE0 到 PE1，PE2 到 PE3 的数据传送，用时=1 个时间单位。在PE1 和 PE3 中形成部分和，用时=2 个时间单位。接着进行PE1 到 PE3 的部分和传送，用时=1*2=2 个时间单位。最后，在 PE3 中形成最终结果，用时=2 个时间单位。因此，利用 SIMD 计算机计算上述表达式总

28、共用时=4（乘法）+1（传送）+2（加法）+2（传送）+2（加法）=11 个时间单位。而利用MIMD 计算机计算上述表达式，除了在第二次传送节省 1 个时间单位以外，其他与SIMD 相同。因此用时=4（乘法）+1（传送）+2（加法）+1（传送）+2（加法）=10 个时间单位。假定有一个处理机台数为 p 的共享存储器多处理机系统。设 m 为典型处理机每条执行执行时间对全局存储器进行访问的平均次数。设 t 为共享存储器的平均存储时间，x 为使用本地存储器的单处理机 MIPS 速率，再假定在多处理机上执行 n 条指令。现在假设 p=32,m=,t=1s,要让多处理机的有效性能达到 56MIPS，需要

29、每台处理机的MIPS 效率是多少答：B试在含一个 PE 的 SISD 机和在含 n 个 PE 且连接成一线性环的 SIMD 机上计算下列求内积的表达式：其中 n=2ks Ai Bii1.n假设完成每次ADD 操作需要2 个单元时间，完成每次MULTIPLY操作需要4 个单位时间，沿双向环在相邻 PE 间移数需 1 个单位时间(1)SISD 计算机上计算 s 需要多少时间(2)SIMD 计算机上计算 s 需要多少时间(3)(4)SIMD 机计算 s 相对于 SISD 计算的加速比是多少答：(1)4n+2(n-1)(2)4 2k n1(3)(4)4n 2n 13 2k n如果一台 SIMD 计算机

30、和一台流水线处理机具有相同的计算性能，对构成它们的主要部件分别有什么要求答：一台具有 n 个处理单元的 SIMD 计算机与一台具有一条n 级流水线并且时钟周期为前者1/n 的流水线处理机的计算性能相当，两者均是每个时钟周期产生 n 个计算结果。但是，SIMD 计算机需要 n 倍的硬件（n 个处理单元），而流水线处理机中流水线部件的时钟速率要求比前者快n 倍，同时还需要存储器的带宽也是前者的n 倍。第六章 机群系统】试区分和例示下列关于机群的术语：1）专用机群和非专用机群；2）同构机群和异构机群；3）专用型机群和企业型机群。答：1）2）根据节点的拥有情况，分为专用机群和非专用机群，在专用机群中所

31、有的资源是共享的，并行应用可以在整个机群上运行，而在非专用机群中，全局应用通过窃取 CPU 时间获得运行，非专用机群中由于存在本地用户和远地用户对处理器的竞争，带来了进程迁移和负载平衡问题。3）根据节点的配置分为同构机群和异构机群，同构机群中各节点有相似的的体系，并且使用相同的操作系统，而异构机群中节点可以有不同的体系，运行的操作系统也可以不同。4）#5）专用型机群的特点是紧耦合的、同构的，通过一个前端系统进行集中式管理，常用来代替传统的大型超级计算机系统；而企业型机群是松耦合的，一般由异构节点构成，节点可以有多个属主，机群管理者对节点有有限的管理权。试解释和例示一下有关单一系统映像的术语：1

32、）单一文件层次结构；2）单一控制点；3）单一存储空间；4）单一进程空间；5）单一输入/输出和网络。答：1）用户进入系统后所见的文件系统是一个单一的文件和目录层次结构，该系统透明的将本地磁盘、全局磁盘和其他文件设备结合起来。2）整个机群可以从一个单一的节点对整个机群或某一单一的节点进行管理和控制。3）将机群中分布于各个节点的本地存储器实现为一个大的、集中式的存储器。4）所有的用户进程，不管它们驻留在哪个节点上，都属于一个单一的进程空间，并且共享一个统一的进程识别方案。5）单一输入/输出意味着任何节点均可访问多个外设。单一网络是任一节点能访问机群中的任一网络连接。%就 Solaris MC 系统回

33、答下列问题：1）Solaris MC 支持习题 中单一系统映像的哪些特征不支持哪些特征2）对那些 Solaris MC 支持的特征，解释一下Solaris MC 是如何解决的。答：1）支持单一文件层次结构、单一进程空间、单一网络和单一I/O 空间。不支持单一控制点和单一的存储空间。2）Solaris 使用了一个叫 PXFS 的全局文件系统 GFS。PXFS 文件系统的主要特点包括：单一系统映像、一致的语义及高性能。PXFS 通过在 VFS/vnode 接口上截取文件访问操作实现单一系统映像，保证了单一文件层次结构。Solaris MC 提供了一个全局进程标示符pid 可定位系统所有进程，一个进

34、程可以迁移到其他节点，但它的宿主节点中总记录有进程的当前位置，它通过在 Solaris 核心层上面增加一个全局进程以实现单一进程空间，每个节点有一个节点管理程序，每个本地进程有一个虚拟进程对象 vproc，vproc 保留每个父进程和子进程的信息，实现了全局进程的管理。单一网络和 I/O 空间通过一致设备命名技术和单一网络技术实现。举例解释并比较以下有关机群作业管理系统的术语：1）串行作业与并行作业；2）批处理作业与交互式作业；3）机群作业和外来作业；4）专用模式、空间共享模式、时间共享模式；5）独立调度与组调度。答：1）串行作业在单节点上运行，并行作业使用多个节点。2）批处理作业通常需要较多

35、的资源，如大量的内存和较长的CPU 时间，但不需要迅速的反应；交互式作业要求较快的周转时间，其输入输出直接指向终端设备，这些工作一般不需要大量资源，用户期望它们迅速得到执行而不必放入队列中。3）机群作业时通过使用 JMS 功能分布实现的用户作业，用户服务器位于任一主机节点，资源管理器跨越所有的机群节点。外来作业在JMS 之外生成的，如 NOW 上的一个工作站拥有者启动的外部作业，它不提交给JMS。4）专用模式：任一时候只有一个作业在机群上运行，任一时候也只有一个作业进程分配给一个节点。空间共享模式：多个作业可以在不重叠的节点区域上运行。时间共享模式：在专用模式和空间共享模式下，只有一个用户进程

36、分配给一个节点，但是所有的系统进程或监护程序仍在同一个节点上运行。5）独立调度：各节点 OS 进行自己的调度，但这会显著损坏并行作业的性能，因为并行作业的进程间需要交互。组调度：将并行作业的所有进程一起调度。一个进程激活时，所有进程都被激活。、针对 LSF 回答下列问题：1）对 LSF 的四种作业类型各举一个例子；2）举一个例子说明外来作业；3）对一个有 1000 个服务器的机群，为什么 LSF 负载分配机制优于：1 整个机群只有一个 LIM或者 2 所有 LIM 都是主机说明原因。答：1）交互式：用户使用 lshosts 命令就可以列出每个服务器节点的静态资源，实现交互。批处理：lsbatc

37、h 实用程序允许通过 LSF 提交、监控和执行批处理作业。串行：用户一旦进入lstcsh shell，发送的每条命令自动在最适合的节点上执行。并行：lsmake 实用程序是 UNIXmake 实用程序时一个并行版本，允许在多个节点同时处理一个Makefile。2）；3）不通过 LSF 执行的称为外来作业。例如执行一些本地作业：字处理，web 网络浏览等。4）机群的服务器数目太多，如果只采用一个 LIM 会导致 LIM 的负责过重，不能及时的处理响应所有服务器的请求和分派所有机群作业；如果采用 2 会导致 LIM 之间相互交换负载信息过多，导致网络通信量过大。为什么在分布式文件系统中，UNIX

38、语义难以实现有哪些放松的文件共享语义采用放松的文件共享语义会有一些什么缺点答：在 UNIX 语义中，一个修改过的块应该立刻被所有其他应用程序见到。然而分布式的文件系统中，多个节点可能存放了同一文件块的拷贝，当其中一个节点修改文件可的拷贝时，其他节点不能立刻就知道，这就使得UNIX 语义难以实现。放松的文件共享语义有：对话语义、类事物语义、不可改变的共享文件语义等。采用放松的文件共享语义要求应用程序员修改程序代码，以适用这种新的语义，这就增加了程序员的负担。试解释在机群并行文件系统中，为什么采用软件RAID、高速缓存机制和预取能够提高文件系统性能。答：软件 RAID 是文件系统负责分布数据和维护

39、容错级别，能够和RAID5 有一样的性能，实现机群磁盘间的数据分布，提高了 I/O 系统的传输带宽。高速缓存是将应用程序要取的块放在CACHE 中，根据局部性原理，应用程序可以基本上从 CACHE 中读取数据块，而不要通过读取内存或硬盘，提高了读取速度。预取是在真正读取数据块之前就将这些数据块读入内存，这也提高了 I/O 性能，改善了文件系统性能。讨论并行文件系统协作化高速缓存的基本技术前提是什么这个前提有什么意义答：基本技术前提是互联网络的速度很快，一个节点需要的文件块在其他节点的缓存中，那么就不需要从磁盘读，而是直接从其他节点的缓存中读出。这个前提的意义是可以提高系统的性能，使得节点间的协

40、作化缓存变得更有意义。：回答以下关于 Berkeley NOW项目的问题：1）Berkeley NOW项目支持单一系统映像的哪几个方面即单入口点、单文件层次结构、单控制点、单存储空间、单进程空间哪个的哪几项并解释如何支持。2）解释 Berkeley NOW项目用来提高性能的四个结构特征。3）解释 Berkeley NOW项目和 SP 机群四个体系结构的差异，并讨论各自的优点。答：1）通过用户级整个机群软件GLUNIX，提供单一系统映像。开发了一种新的无服务器网络文件系统 xFS，以支持单一文件层次结构。2）3）主动消息通信协议，支持有效的通信；机群软件 GLUNIX 提供单一的系统映像、资源管

41、理和可用性；xFS 支持可扩放性和单一文件层次结构的高可用性；软件框架 WebOS构筑高可用性、渐增可扩放性。4）SP 机群的体系结构特征：每个节点都是 RS/600 工作站，并有自己的局部磁盘；每个节点内驻留一个完整的 AIX；各节点通过其 I/O 总线连接到专门设计的多级高速网络；尽量使用标准工作站部件。这样的优点是简单性和灵活性。考虑 xFS，并回答下列问题：1）解释 xFS 和集中式文件服务器的两个不同点，并讨论各自的优点；2）解释 xFS 用来提高可用性的主要技术；3）解释 xFS 用来减轻小写问题的主要技术。（答：1）无服务器文件系统 xFS 将文件服务的功能分布到机器的所有节点上

42、，xFS 中所有的服务器和客户的功能由分散的所有节点实现之。这与集中文件服务器的中央存储、中央缓存、中央管理不同。xFS 的优点是采用分布式管理和协同文件缓存以及冗余磁盘阵列，这提高了系统的可用性以及 I/O 的性能和吞吐量。集中式文件服务器会减少缓存的不一致性，管理简单。2）xFS 提高可用性的主要技术是采用廉价冗余磁盘阵列RAID。无工作站文件系统能用来生成软件 RAID，以提高性能和高可用性。现在xFS 使用单奇偶校验磁盘条。一个文件数据块在多个存储服务器节点上按条划分，在另一个节点上有奇偶校验块。如果一个节点失效，失效磁盘的内容，可利用其余盘和奇偶盘之异或操作重建之。3）xFS 使用日

43、志条的方法解决小写问题：每个用户首先将写接合到各用户的日志上；然后此日志采用日志段提交给磁盘，每个段系由K-1 个日志片组成，它与奇偶校验片以道送给 K 个存储服务器。第七章 分布式共享存储系统什么是分布式共享存储系统，它相对于共享存储系统与分布式系统有哪些优点中央服务器顾客发送数据请求接收请求接收应答执行数据访问，发送应答迁移算法顾客如果高速缓存行不在本地，则确定位置，发送请求接收回答，访问数据接收请求，发送高速缓存行远程主机现假设报文数量不会导致网络阻塞，服务员的阻塞没有严重到能够极大地延迟远程进程访问，访问本地数据的代价与远程访问代价相比微不足道，报文传递也是可靠的。试分析两种算法的适合

44、情况。答：中央服务器算法，每次顾客发送数据请求到中央服务器，地址计算简单，适合多个顾客频繁轮流读写。迁移算法每次确定位置需要一定开销，适用于单个顾客频繁对数据读写，因为访问数据总是被迁移到访问节点里。下面是运行在一个硬件维护高速缓存一致性的多处理机上的程序段，假设所有值初始为 0。P1P2P3P4A=1U=AW=AA=2V=AX=A只有一个共享变量 A，假设一个用户知道所有高速缓存拷贝的地址并且可直接对(不需要和目录节点协商)拷贝进行更新，假设采用写更新协议。试构造出一个写原子性被违背的情况：说明产生的结果违背了顺序一致性；答：如果进程 P1 首先对含有共享变量A 的数据块进行写操作，进程 P

45、2、P3 执行 U=A 和 W=A，分别将 U、W 置为 1。此时 P4 对共享变量 A 进行写操作，并且同时更新 P1、P2、P3 中的值，此后 P2、P3 再执行 V=A，X=A，此时V 与 X 被置为了 2。对于进程2 来说，结果违背了顺序一致性。参照下述代码段：问：000000 是不是 PARM 一致性内存模型的合法输出解释原因说明顺序一致性与 PARM 一致性区别a=1;b=1;c=1;Print(b,c);Print(a,c);Print(a,b);(a)P1(b)P2(c)P3答：在 PARM 一致性内存模型下，000000 是合法输出，因为 PARM 不关注存储相关性，即同一进

46、程程序序可以优化，这样各进程先执行打印完再执行赋值则出现如上情况。顺序一致性与 PARM一致性的区别就是于是否关注存储相关性。有两个并行的过程 P1、P2（如下图所示），在顺序一致性模型下，试列出所有可能的6 种语句交错执行顺序，使两进程不可能同时被kill。a=1;b=1;if(b=0)kill(P2);if(a=0)kill(P1);(P1)(P2)答：（1）a=1;if(a=0)kill(P1);b=1;if(b=0)kill(P2);(2)a=1;b=1;if(a=0)kill(P1);if(b=0)kill(P2);(3)b=1;if(a=0)kill(P1);a=1;if(b=0)kill(P2);(4)b=1;if(a=0)kill(P1);if(b=0)kill(P2);a=1;(5)a=1;if(a=0)kill(P1);if(b=0)kill(P2);(6)if(a=0)kill(P1);if(b=0)kill(P2);a=1;b=1;b=1;分析以上 6 种情况，在满足顺序一致性模型前提下，不会存在 P1、P2 同时被 KILL 的情况。