分布式.docx
- 文档编号:7333166
- 上传时间:2023-05-11
- 格式:DOCX
- 页数:23
- 大小:147.23KB
分布式.docx
《分布式.docx》由会员分享,可在线阅读,更多相关《分布式.docx(23页珍藏版)》请在冰点文库上搜索。
分布式
1.分布式系统的特征(也是设计目标):
资源共享、开放性、并发性、容错性、透明性。
2.在分布式系统中,当场点A上的一个进程希望同场点B上的另一个进程进行通信时,常用的发送策略有固定发送、虚拟线路和动态发送。
3.分布式计算机系统的共同特点是:
软硬件上结构具有模块性、工作方式上具有并行性、系统功能上具有协同自治性、对用户具有透明性和运行时具有健壮性。
4.8维超立方体结构中的2个结点,若其编号分别为10101010、01010011,则这2个结点间的距离为6。
5.若单个资源控制采用这样一种方式:
多个平等的管理机构采取一致原则对资源活动进行全面管理,则这种管理方式称为全分散管理方式;而集体资源控制管理方式可分为:
分管、部分合管和全合管。
6.在分布式逻辑时钟中,对于事件x,y,若x—>y不成立,则称x,y是并发事件或x||y。
对于事件x,y,x→y,y→x均不成立,则称x,y是相互对立的。
7.一个好的路径算法至少应该满足三个条件即:
完备性好、效率高和开销小。
8.在基于遗传算法和模拟退火算法的任务分配策略中,对一个给定的分配方案(n个处理机、m个任务),可用一个数据结构TA={S,R}来描述,其中S是一个m*log2(n)位2进制串。
9.对于负载平衡的双向主动算法,在系统高负载时应采用发送者主动激发,接收者主动接收方案,而在系统低负载时应采用发送者主动方案。
10.每个作业都有一定的属性,按功能可以把作业分为“计算“型和信息处理型。
(按形式分:
"交互式"和"后台")
11.分布式计算机系统与计算机网络、多处理机系统之间既有区别,也有关联;一般认为,计算机网络是分布式计算机系统的物质基础,而分布式计算机系统式计算机网络的一种高级发展形式。
而分布式计算机系统与多处理机系统之间的最大区别在于多处理机系统不具有以自治性为特征的分布式控制,强调在统一OS控制下实现整体控制和任务调度,全面并行性是其根本特征。
12.分布式程序设计的三个特点是分布性、通信性和坚定性。
最常用的分布式并行程序环境有Express、PVM和MPI。
13.8维超立方体结构中的2个结点,其编号分别为10001010、01010011,则这2个结点之间的距离为5。
14.并行算法应具有可划分性和过程的异步性。
15.分布式数据库可分为3种类型:
层次型、联邦型、综合型。
16.对于具有n个结点的单向环结构,其最大通信路径长度(即网络直径)为n-1。
17.分布式系统中的通信是以消息传递为基础,其基本通信机制可分为消息传递方式和远程过程调用;而远程求值是在远程过程调用基础上发展起来的,它不仅能够远程场地传送数据参数,还允许传送程序代码段。
18.系统的透明性事指系统的内部细节对用户是隐藏的,分布式系统的透明性主要包括这些方面:
(至少给出5种)位置透明性,迁移透明性,并发透明性,并行透明性,副本透明性。
19.在分布式系统中每个对象一般有两个名字(Name),一个是用户识别的文本名,一个是系统使用的内部名,
即系统标识符。
而常用的命名方案有绝对命名、相对命名和层次命名三种。
20.7维超立方体结构中的2个结点,其编号分别为1001010、0101011,则这两个结点之间的距离为3。
21.分布式事物有简单分布式事务与嵌套事务两种不同的结构。
22.任务分配追求的目标是IPC的极小化和负载平衡。
23.构成调度问题的基本元素有三个,即资源集、消费者集和调度程序。
24.分布式系统中的资源共享途径主要有:
数据迁移、计算迁移和作业迁移以及进城迁移。
25.给出两个具体的任务分配策略,如:
基于图论的分配策略,0-1程序设计策略、基于进化算法的策略。
一.问答题
1.左图是一个具有16结点的4度带弦环形网络,这是一个单向环,即沿着环或弦单向传送信件。
针对一个n个结点的4度带弦环形网络,
请问:
⑴与具有相同规模的简单单向环相比,分析该结构的优劣。
⑵给出一个无故障情况下的路径选择算法。
⑶修改⑵中给出的路径选择算法,
使该算法在出现一个故障的情况下仍能将信件送到。
答:
1)单向环主要特点是:
直接传输策略,没有传输控制、传输路径专用
主要缺点:
可靠性问题。
优点:
带弦的环形网络可提高系统的坚定性,
提高结点的度,从而缩短网络直径,增大等分宽度,达到提高速度的目的
2)与简单单向环类似,当一个节点接受到消息时,如果该节点是目标节点就进行处理。
如果不是往左(右)传递,路径选择方法:
求解|S-D|%4设余数为a,并且对|s-d|/4的结果取整,设为b,如果余数a为零,则选择走弦共b次。
如果余数为其他,则先走弦走b步后走a步弧。
3)、思想:
如果节点2故障,且环向右传递。
在向下传递时先判断下个节点是否故障,不故障就往下传递,如果故障就走弦,将消息传递到在节点二之前的节点上13上(回传),13按照弧传递两步到15后走弦到节点3!
2.对于4度带弦环形网络的分布式计算机系统,设计一个投标算法,并分析该算法的性能。
与上题思想类似
答:
1.资源申请者向所有资源管理者发送招标信息;
2.当一个节点接受到招标信息,如果本节点没有相关资源,往左(右)传递,路径选择方法:
求解|S-D|%4设余数为a,并且对|s-d|/4的结果取整,设为b,如果余数a为零,则选择走弦共b次。
如果余数为其他,则先走弦走b步后走a步弧。
3.如果本节点上有相关资源:
1)接受到的招标信息中没有投标内容,则在招标信息中加入本节点投标信息,转向步骤2;
2)接受的招标信息中有投标内容,则通过一定的算法将该投标内容与自身进行比较,取其优者写入,
转向步骤2;
4.资源申请者在收到自己发出的招标信息后,根据其中的投标信息向中标者发出申请;
5.中标者收到申请消息后将该申请加入自己的等待队列;并在实际分配时给申请者一个回复。
6.当资源使用完后,通知提供者收回资源。
算法性能:
该算法实现简单、直观,但需一定开销。
3.分布式系统中,文件的安全保密非常重要,在UFID设计上采用什么样的措施?
你是否有更好的办法?
答:
UFID与地址的作用不一样,它不包含拥有该文件的服务器在网络中的服务信息,也不包含文件在存储器的位置。
UFID定将文件组的标识符和文件的编号合起来构成UFID。
文件编号是整数,并创建一个文件,它就自增1,文件编号是不可重用的,保证了UFID的唯一性,在UFID中加入一个随机数字的额外字段可以有效地防止伪造,使得有效UFID的分布是稀疏的。
随机数字与相关文件存放在一起,展开文件服务据此可以检查存取文件请求的合法性。
再将允许字段与随机数进行加密一生成一个单独的37位数未加密的允许字段仍然保留,以便客户和服务器的程序通过检查,确定哪些权限包含在UFID中而XX对该字段的改变将使UFID无效。
4.服务器高速缓存和客户高速缓存的作用各是什么?
答:
服务器高速缓存通过在服务器节点的本地存储器中保留最近使用的块副本可以降低文件存取的开销。
也即避免了对同一磁盘块的反复存取,由此提高了文件服务器的性能。
客户高速缓存则减少了由于网络等待和服务器负载所造成的延迟,可以在客户机上高速缓存文件最近存取的块、文件属性以及文件条目,从而提高性能。
5.试分析发送者主动算法、接收者主动算法和双向主动算法,并对它们进行比较。
答:
发送者主动:
当一个站点超载时,它就尝试将任务发给一个轻载站点。
接收者主动:
当一个站点的任务队列长度小于阈值时,它就尝试从重载站点接收一个任务。
发送者主动
接收者主动
转移策略
阈值策略,当一站产生一个新任务,若任务队列长度超过阈值T,确定该站点为发送者
阈值策略:
当一个站点上有任务离开时,若任务队列长度小于阈值T,它就尝试从重载站点接收一个任务。
选择策略
选择新到达的任务作为要发送的任务
所有其它站点上的任务都可能成为接收对象。
定位策略
阈值定位策略:
根据被轮询站点任务队列长度,看是否超过阈值,若没有超过就转移到该站点。
阈值定位:
根据被轮询站点的任务队列长度,判断是否超过阈值,若超过九转移任务到站点i。
信息策略
要求驱动策略,一站点只有成为发送者时才能收集其它站点的信息
一个站点只有在成为接收者时才能收集其它站点的信息。
双向主动算法中,发送者和接收者都能转移任务,兼有两者的优点。
在系统负载低时,本算法中发送者主动算法容易发现轻载站点;系统负载较高时,接收者主动容易找到重载站点。
双向主动算法不足的是,系统负载较高时使用发送者主动易造成系统的不稳定性等。
较好的解决方法是采用自适应算法,合理地设置阈值,系统高负载是采用接收者主动,系统的负载时采用发送者主动。
6.简述分布式事务的两阶段提交协议,它与一阶段提交协议有何联系与区别。
后者是如何改进系统性能的?
嵌套事务的两阶段提交协议的注意要点是什么?
答:
在一个事务进行期间,除了当参与者参与事务时通知协调者外,协调者和参与者之间没有通信。
客户提交或终止一个事务的请求直接发送给协调者。
若客户请求AborTransanction,或者事务被其中某个台服务器终止,协调者立即通知参与者。
两阶段提交协议是在客户要求协调提交事务才开始被启用。
在两阶段的第一阶段,协调者询问所有参与者是否预备提交,而在第二阶段,它通知它们提交或中止事务。
若一台服务器可提交其相关的部分事务,它一旦预备提交就会同意。
两阶段提交协议由一个表决阶段和一个完成阶段构成。
共同点:
由于事务具有原子性,若事务的一部分被中止,则全部事务必须被中止。
区别:
一阶段提交协议当客户申请提交时,协议不允许服务器作出单向决定去中止事务。
限制服务器提交于之相关的部分事务的原因总的来说与并发控制方式有关。
两阶段提交协议允许任何服务器中止与之相关的部分。
改进:
在协议的第二阶段事务的每个服务器都执行联合决定,若任何一个服务器表决要中止,则必须是中止该事务。
若所有服务器表决要提交,则决定是提交该事务。
注意:
要保证所有的服务器都表决且都达成一致的决定。
要防备服务器故障,可将每个服务器与两阶段提交协议相关的信息保存到永久性存储器中。
7.针对2层多环结构设计一个最佳的投标算法,并分析该算法的性能。
该2层多环结构得主环上有m(>2)个节点,每个子环上有s(>2)个节点,整个环上有m*s个节点。
答:
1.资源申请者向所有资源管理者发送招标信息;
2.节点r接受到招标信息。
如果本节点没有相关资源,这时有两种情况:
1)r在子环上,即r/s–[r/s]>0,则将招标信息传往该环上的下一个节点r+1;
2)r在主环上,r/s–[r/s]=0:
a,如果目的节点在相应的子环上,0 b,如果目的节点在主环上,则沿主环传到下一个节点(rmodm)+s 3.如果本节点上有相关资源: 1)接受到的招标信息中没有投标内容,则在招标信息中加入本节点投标信息,转向步骤2; 2)接受的招标信息中有投标内容,则通过一定的算法将该投标内容与自身进行比较,取其优者写入, 转向步骤2; 4.资源申请者在收到自己发出的招标信息后,根据其中的投标信息向中标者发出申请; 5.中标者收到申请消息后将该申请加入自己的等待队列;并在实际分配时给申请者一个回复。 6.当资源使用完后,通知提供者收回资源。 算法性能: 该算法实现简单、直观,但需一定开销。 8.什么是带环的二叉树结构? 对于一个具有n个节点的带环的二叉树结构,请给出其网络的直径和系统的总接口数。 当n=20,节点4失效时,按路径算法给出结点3至结点9的信件传送路径。 答: 带环二叉树: 网络直径: 在n>=21的情况下,d=min{2[log2n]-δ,[(n–[n/2]+1)/2]} 系统总接口数 当n为偶数时,树根有4个接口,结点n/2只有2个接口,其它结点有3个结点,所以系统总接口数I=3n。 当n为奇数时,树根有4个接口,其它结点都有3个结点,所以系统总接口数I=3n+1。 路径算法 1)假设D=9,R0=3,结点4失效,传送路径为: 3→1 1→2 2→4→2 2→5 5→10 10→20 20→19 19→9 2)假设D=18,R0=2,结点8与9失效,传送路径为: 2→4 4→9→4 4→8→4 4→1 1→16 16→17 17→8→1717→18 9.举例说明负载平衡应包含哪些部分? 简单说明每一部分的情况。 答: 转移策略——确定参与者 确定一个结点应该是接受者、发送者,还是平载。 一般采用阈值策略。 设有阈值T1、T2,某结点的负载为T, 如果T 如果T>T2,该结点负载太重,应该是发送者; 如果T2≥T≥T1,则该结点为平载。 选择策略——选择发送的任务 从发送者结点选择一个任务。 最简单的策略是选择导致该结点成为发送者的新任务。 考虑的因素有: 1)转移开销小;2)被选择的任务足够大,与转移开销相比,是合适的。 定位策略——选择接受者 非集中式算法: 轮转搜索接受者(串行或者并行——广播)。 一般可用随机,阈值,最短三个方案,它们都需要限制轮询的次数。 信息策略——信息搜集决定如何收集系统中其他结点的状态信息。 11.什么是远程求值? 与远程过程调用相比,有何优越性。 答: 远程求值是在远程过程调用基础上发展起来的,同样适用c/s模型,它不仅能向远程场地传送数据参数,还允许传送程序代码段。 优越性: 1)在RPC机构中,每个结点所能提供的服务局限于结点所拥有的远程过程之中,而远程求值则打破这种限制;一个结点所支持的服务可以通过此结点所能提供给用户的操作和过程组合得到,具有较高灵活性。 2)RPC总是将数据传送到过程所在的场地,这是唯一的信息流向,故开销大,而远程求值则可以把处理这些数据的过程传送到所在场地进行,有效降低网络开销。 3)灵活的服务请求方式和多变的用户界面,能获得良好的通用性和较高的效率。 17.试分析任务分配和负载平衡的联系与区别。 答: 任务分配和负载平衡都是为了提高整个系统的性能。 负载平衡对系统中的负载情况进行动态调整,以尽量消除和减少系统中忙闲不均的现象,以提高系统的吞吐量。 因此,负载平衡又被称为负载共享。 任务分配追求的目标是IPC(InterprocessorCommunication)的极小化和负载平衡,这两者显然是一对矛盾。 努力调配各模块,使IMC(IntermoduleCommunication)和IPC最小,这称为最小IPC策略;另一方面是尽可能使负载平衡,这称为负载平衡策略。 10.RPC系统中,可能出现5种不同类型的问题,“服务器应答信息丢失”是其中之一,另外4种是什么? 试分析“服务器应答信息丢失”现象及其处理策略。 答: (1)客户机无法定位服务器 如服务器可能关闭。 解决办法是在出错时产生一个异常。 但并非所有的语言都有异常和信号处理程序(如Pascal)。 另外编写异常和信号处理程序破坏了透明性(RPC的目标是隐藏通信细节,使远程过程调用与本地过程调用一样)。 (2)客户机(发送给服务器的)请求信息丢 客户内核在发送请求时启动一个计时器。 若超时,内核重发消息。 若多次重发,仍没有应答消息,客户机会放弃请求并认为服务器已经关闭(如同“无法定位服务器”故障)。 (3)服务器(发送给客户机的)应答信息丢失 现象: Client无法确定此故障为: 请求信息丢失、应答信息丢失、Server太慢(传输延迟)、Server故障。 超时机制,内核重发消息。 操作能多次安全地重复执行而不产生危害: 解决: 每个请求携带一个顺序号,服务器只执行顺序号最小的请求。 (4)服务器(在收到请求后)崩溃现象: 由于client不能区分故障是执行请求后崩溃还是执行请求前崩溃。 三种解决方案: a.让client等待,超时重发,直到server重启,发回一个应答消息;策略: at-least-once,它保证RPC至少要执行一次,但也可能执行多次。 b.立即放弃并报告失败;策略: at-most-once,它保证RPC最多执行一次,但可能没有执行。 c.不做任何保证。 当server崩溃时,client得不到任何帮助和保证。 RPC可以不执行或执行多次。 (5)客户机(在发送请求后)崩溃现象: 在server应答之前,client崩溃。 此时,正在进行的某种计算却没有父进程接收计算结果,这种无用计算称为“orphan(孤儿)”。 解决方案: 再生: 将时间划分成连续编号的纪元(epochs)。 当一client重启时,它向所有机器广播一个消息,宣布一个新的纪元开始。 广播后,所有远程计算被终止。 13.介绍基于遗传算法和模拟退火算法的分布式任务分配策略的基本思想与主要内容。 答: 主要内容: 将遗传算法和模拟退火算法结合起来,寻找一个Cost最小的分配方案。 设 T={t1,t2,…,tm}——m个任务 P={P1,P2,…,Pn}——n个处理机 目标函数: 任务分配方案: TA={S,R}TaskAssignment 其中: R是一个由n个元素的数组,每个元素对应一个处理机,表示对分配给自己的任务的处理顺序。 S是一个有「log2n︱*m个二进制位的二进制串。 其中的每「log2n︱位为一节,第i节表示第i个任务ti被分配给那个处理机了。 主要思想: 1、给TA一个初值,计算出该初值对应的Cost; 2、对Temp=1000to1参数α=0.9,执行下列各步: a)对TA进行交叉繁殖、变异、复制处理; b)计算出新方案的Cost; c)计算两个Cost的差ΔCost; d)如果ΔCost<0则接受新的方案,否则 e)如果ΔCost>0则随机地在0,1之间取一个round: 如果exp 则保持原方案,否则留用新方案。 14.解释分布式系统异步进程通信模型中“超越”现象及其约束方式。 同步通信: 进程p发出消息后,等待进程q的应答,所以,进程q接收消息的顺序与p发送消息的顺序是相同的。 但是,同步通信限制了进程的并发性。 本题答案异步通信: 往往采用信箱技术。 进程p只将消息发到指定信箱,这样,p和q之间的通信可以通过一个逻辑通路(通道)来实现。 这虽然提高了进程的并发性,但是,后发的消息可能先到——称之为“超越”。 所谓超越就是说,mi、mj先后由p进程送出,但是mj却先于mi被q进程所接受,便称mj超越了mi。 按照对超越行为的约束的不同,通道可以被分成4种: 无限制: 可以任意超越;FIFO: 不允许发生超越; F通道: 对消息分类,不同的消息用有不同的超越权限。 t类(两端堵塞): 既不能超越别人,也不能被别人超越;(相当于2——FIFO) o类(普通型): 既可以超越别人,也可以被别人超越;(相当于1——无限制) b类(向后堵塞): 不可被后来者超越; f类(向前阻塞): 不可以超越先来者。 层次通道: 将通道分层,各层有自己的类型 较低层(号小)者优先级高 15.一个拥有n=i*j个节点组成的方阵结构(如图a,图略) 节点按行编号1、2、3….j、j+1….,i*j。 而一个拥有n=i*j*k个节点组成的则如图b所示。 简单立方体结构是由k个方阵结构迭加构成的,并将各层上对应的顶点连接起来。 第h层节点编号是第一层对应节点编号的h倍,即按行编号1*h,2*h,…,j*h,..,i*j*h。 请针对对应简单立方体结构,完成 (1)对其结构性能进行评价, (2)给出此结构的一种路径选择算法。 (3)它与拥有同样结点数的单向单环结构相比,有何优缺点? 答: (1)信息传输能力大,故障影响小,重构能力强,可供选择的通路多,几乎不会出现通讯瓶颈问题,结构可以递归,便于扩充,同样也便于分解为若干子结构。 (2)考虑一个n维超立方体,其中N=2^n个结点。 每个结点b用二进制编码为b=bn-1bn-2.....b1b0.姑开始结点可编码为s=sn-1sn-2....s1s0,目标结点编码为d=dn-1dn-2...d1d0.我们希望确定一条从s到d的路线,使得步数最少。 我们用I=1,2,......,n表示维数,第i维对应结点地址的第(i-1)位。 用v=vn-1vn-2...v1v0表示该路径中的任一结点,可通过以下算法确定一条唯一的路径: 1.对所有的n维(i=1,2,...,n),计算方向位ri=si-1⊕di-1.使维数i=1,v=s,并开始以下步骤: 2.如果ri=1,设置当前结点v为路径中的下一个结点,v⊕2^i-1,v=v⊕2^i-1;如果ri=0,跳过 3.如果i (3)优点: 平均通信路径短;信息传输能力大;故障影响小;重构能力强;可供选择的通路多,几乎不会出现通讯瓶颈问题;结构可以递归,便于扩充,同样也便于分解为若干子结构; 缺点: 结构复杂,搭建难度高。 16.分布式计算机系统中为什么要进行负载共享,负载共享策略应包括哪些方面。 试分析接受者主动算法与发送者主动算法,并对它们进行比较。 答: 原因: 负载共享有利于统筹管理分布式系统中的各种资源,便于利用共享信息及服务机制扩大局部分布系统的处理能力。 负载共享策略包括转移、选择、定位、信息策略。 发送者主动: 当一个站点超载时,它就尝试将任务发给一个轻载站点。 接收者主动: 当一个站点的任务队列长度小于阈值时,它就尝试从重载站点接收一个任务。 发送者主动 接收者主动 转移策略 阈值策略,当一站产生一个新任务,若任务队列长度超过阈值T,确定该站点为发送者 阈值策略: 当一个站点上有任务离开时,若任务队列长度小于阈值T,它就尝试从重载站点接收一个任务。 选择策略 选择新到达的任务作为要发送的任务 所有其它站点上的任务都可能成为接收对象。 定位策略 阈值定位策略: 根据被轮询站点任务队列长度,看是否超过阈值,若没有超过就转移到该站点。 阈值定位: 根据被轮询站点的任务队列长度,判断是否超过阈值,若超过九转移任务到站点i。 信息策略 要求驱动策略,一站点只有成为发送者时才能收集其它站点的信息 一个站点只有在成为接收者时才能收集其它站点的信息。 因此: 发送者主动算法适应于系统负载较低的情况---易发现轻载结点。 接受者主动算法适应于系统负载较重的情况---易发现重载结点。 19.总线控制的加权参数算法规则: ㈠在对总线的平等监视过程中,当某机判到总线闲时,转㈠; ㈡判到总线闲时,转㈠; ㈢检查本机“占总线位”失败次数N。 如果N 若忙,N+1→N转㈠;N>=n/2,则等待时间ti=t1(最小时间)后,再判总线闲否? 若忙,转㈠; ㈣将本机状态寄存器“占总线位”置位,即占用总线,并判本机是否“假占”总线? 若假占,则清“占总线位”,N+1→N,转㈠; ㈤占用总线。 请问: 该方式是否是分布管理式的? 分布管理式的算法应满足什么条件? 请分析上诉算法。 答: 是的。 其算法要满足: (1)在任一时刻,总线最多被一个进程占用; (2)按算法的协调,对总线使用不会产生饿死现象;(3)按算法的协调,对总线使用各机均处于平等地位,没有集中地控制者。 v性能评价: ①平均通信路径长度Lav=1,网络直径d=1;②任何时刻只允许一对结点进行通信,通信并行度为1; ③每个结点的通信接口数为1,全系统的通信接口总数为n;④结点间仅有一条通路
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 分布式