分布式OS讲稿-1

分布式操作系统DistributedOS,武汉大学计算机学院何炎祥yxhe,上课时间：周3，7-10节上课地点：1区计-204,教学参考书,1.DistributedOperatingSystems,AndrewS.Tanenbaum著，PrenticeHalli为进程编号，Ci为时戳2.每个进程都管理一个请求队列（RequestQueue:RQ）,存放按“=”定序的Request消息（初值为空）。,LamportsAlgorithm,该算法进出一次临界段需要3（n-1）条消息问题：1.所有参与这一活动的进程彼此要互相知道对方的名字或进程号；2.若参与这一活动的某进程故障，该算法就可能崩溃，即强健性不好，对此可考虑增加一条：某进程q在预定时间间隔内未收到回复消息，可假定该回复消息已收到。或者，在执行该算法时，有一守护进程监测系统中各进程的状态，若发现某进程故障，则通知其它进程不再向它发送任何消息，待故障修复后，再将其加入这一活动中。,思考题-1,验证该算法的正确性，即该算法是否能保证1）在任何时刻，最多只有一个进程位于临界段（安全性）；2）若位于临界段的进程在有限时间内退出临界段，则其它请求进入临界段的进程总会进入（可用性）。,Ricart2)它在CS中，退出时就将Token传给其左邻进程pi;3)它自己已发request消息，它就暂存左邻进程发来的request消息，一旦收到其右邻进程pj发来的Token，它自己先进入CS,退出时，再将Token传给其左邻进程pi。,思考题-3,1.其中的站点故障了怎么办？2.Token丢失了怎么办？3.若pi发出request消息后久未获得Token，该怎么处理？4.若引入时戳，该算法应做何改动？,适合于非环结构的Token传递方法,假定1.系统由n个站点组成，每个站点运行一个进程(P1,P2,Pn)；2.有一个与token相关的向量T=(T1,T2,Tn),每个Ti与进程Pi对应，用于记录进程Pi第i次进入临界段的时戳；2.每个进程都管理一个请求队列（RequestQueue:RQ）。,适合于非环结构的Token传递方法,该算法的特点,1.系统是非环结构的，持有token的进程可将它传递给系统中的任何进程；2.若无进程打算进入临界段，则token不必再系统中循环不断地传递；3.互斥得到保证；4.希望进入临界段的进程保证在有限时间内进入临界段。,分布式通信软件与通信协议,分布式系统中实现通信功能的这一部分软件统称为通信软件（communicationsoftware）位于不同机器上的进程进行通信时，必须遵循预定的规则和约定，这些规则和约定称为通信协议（communicationprotocol）只有遵守通信协议，网络与网络之间、站点与站点之间、进程与进程之间才能相互通信、协同、配合，避免出现混乱现象通信协议通常由语义、语法和变换规则三部分组成语义确定通信双方相互之间“讲什么”；语法确定通信双方相互之间“如何讲”；变换规则确定通信双方相互之间的应答关系。,通信协议可分为物理的（如信号的电压、宽度等）和逻辑的（如字符编码、信件格式等）。因此，通信协议分为物理层和逻辑层。逻辑层（高层）建立在物理层（低层）基础上。逻辑层和物理层还可分为若干层。通信协议采用层次结构设计是一种行之有效的方法ISO于81年推出网络系统结构7层参考模型“开放系统互联”模型（分为应用层、描述层、会话层、传输层、网络层、数据链路层、物理层），即OSI(OpenSystemInterconnections)。其中引入层次结构的概念，它包括1）将网络功能划分为许多层次，每一层上都有通信双方的约定和规则（称为同层协议）；2）相邻两层之间有相互衔接条件，也是一种约定和规则（称为接口-interface)接口可以是硬件，如机械或电子装置，也可以是软件，如数据格式的变换或地址的映射及接口程序等。,层次结构的优点,某层协议的修改、扩充不致影响其它层次。整个网络的协议是由各层次的协议组成的。参照这种参考模型进行网络标准化的结果就使得各系统之间是“开放”的，都可以互连、互通各层协议中较低层的协议通常用硬件实现，或由硬件和软件共同实现，而高层协议一般由软件实现。所有用于实现各层网络协议的软件称为网络软件OSI的高层协议已称为计算机网络中的重要研究课题，它也直接关系到分布式系统中通信机制的设计,分布式os的通信机制,分布式OS的通信机制以消息传递为基础，其基本通信机制主要分为两大类：“消息传递”和“远程过程调用”1.消息传递（messagepassing）消息：一条消息是进程间相互通信所传递的一个信息单位，它可以是定长的、变长的，也可以组织成报文、信件、消息包或帧的形式。消息传递原语：send,received,reply分别用于发送、接收和回复消息。分布式OS用这些原语实现进程间的通信和同步。,2.异步型通信原语（以send为例）Sender不等待receiver的回复就继续执行下去，又称“不等传递”（sendnowait),即允许sender任意超前于receiver，这就出现下面的特点：1）receiver接收的消息中反映的发送状态一般不是sender的当前状态；2）系统应有较大的缓冲区来存放业已发出但尚未处理的消息；3）sender与receiver可高度并行执行。3.同步型通信原语（以send为例）Sender总是等待receiver接收消息的回复后，两者同时继续执行下去，其特点为：1）sender和receiver在完成消息交换后，彼此基本知道对方的当前状态；2）无需大的缓冲区存放消息（可以没有）；3）实现容易，但效率较低。,同步消息传递机制特别适合于解决client-server类问题（例子）,Client方：提出服务请求，然后等待“服务完成”的消息，收到“服务完成”后，才继续执行下去Server方：可设计成下面的程序段whiletruedowaitingreceive(msg)process(msg)reply(ans)endofwhile,Client/server的同步表现在,1.Client发出request后就等待server的服务；2.仅当没有Client发来request时，server就等待；3.Client在收到server发来的“服务完成”消息后才继续其执行，从而完成client/server的同步。在设计server程序时，一般要求：1.Server应能响应多个并发的请求；2.Server在给Client发“应答”消息时，不应该被阻塞；3.某个Client故障不应影响Server的操作。,远程过程调用（RPC）,远程过程调用（RemoteProcedureCall）:指非本地站点间的过程调用，即调用者和被调用者不在同一站点上RPC的概念源自美国B.J.nelson的博士论文（1981），1989年ISO就将它作为计算机、终端用户、进程、计算机网络等的一种进行信息交换的标准规程RPC的实质：是实现OSI七层协议中“会话层”的功能，即在两个试图进行通信的站点间建立一条逻辑信道（进行会话连接），并利用这个信道交换信息。不再使用时，负责释放所建立的信道（七层协议即ISO于81年推出的网络系统结构七层参考模型，即“开放系统互连”OSIOpenSystemInterconnection的七层协议：应用层、描述层、会话层、传输层、网络层、数据链路层、物理层）,从语义角度：RPC使用“过程调用”方式实现通信，有类似于本地过程调用的语义，可向应用层和用户提供良好、习惯的接口从应用角度：由于过程可独立编程的特点，以及过程已作为编程中的一种基本构件，有利于分布式系统灵活的扩展服务功能，也有利于故障的局部化处理,RPC的通信模式,RPC的通信模式是基于client/server间相互通信模型的一种同步通信形式。它对client提供了远程过程的抽象，其底层消息传递操作对client时透明的在RPC中，client是请求服务的调用者CallerServer是执行client的请求而被调用的对象（被调用者）Callee它们之间的通信模式为：,这个模型中1.在任何时刻，client/server双方只有一个处于活跃状态；2.Client和server之间的通信是不对称的，其中*Client（Caller）是主动方，由它开始激活一次会话连接，并在server的配合下完成一次信息交换；*Server（Callee）是被动方，开始总是处于倾听状态，等待client的“调用请求”到达。,RPC的结构,1.RPC的组成Stub(client和server各一个)ControlpartTransferpartClientsStub的功能：1)调用时，将参数组装成消息形式;2)借助网络将这一消息发给通信系统；3)返回时，将“返回结果”拆卸成返回参数发送给通信系统。,ServersStub的功能：1）接收由ClientsStub发来的“调用消息”；2）将其拆卸成参数形式，然后调用指定过程；3）将“返回结果”组装成“应答消息”发送给通信系统。Controlpart:1）确定RPC消息的方向（发送or接收）；2）负责控制“Transferpart”进行消息的传递。Transferpart是RPC的最底层，主要作用为：1）提供对传递层协议的选择；2）建立/释放逻辑信道，并进行消息的发送/接收；3）管理RPC的消息缓冲区。,RPC的逻辑结构,ClientsStub与一个Client连接，它对于该client就像一个“server”。在调用时，它先截取client的远程调用命令后,利用通信网络向server方发“请求服务”的消息；返回时，它获取返回结果，返回到client，然后client继续执行下去ServersStub与一个Server连接，它对于该server就像一个“client”。在调用时，它收到远程调用请求后，产生一个本地调用，去执行被请求的远程过程（server）。返回时，它截取远程过程的返回结果，并形成返回消息发送出去,实现RPC的主要步骤,1）调用者（client）调用ClientsStub，后者为远程过程组装参数，然后，构成一个或多个网络消息；2）这些网络消息由ClientsStub发送给通信系统；3）借助网络协议发送出去；4）ServersStub等待ClientsStub的调用请求，从网络消息中提取参数并转换成所需格式；5）ServersStub执行一个本地过程调用，激活实际的服务程序，并将从ClientsStub发来的网络消息中收到的参数传递给此程序；6）所请求的服务程序完成后，返回到ServersStub；7）ServersStub对返回结果进行转换，并将它们拼装成一个或多个网络消息；8）这些网络消息借助网络协议和通信系统传回ClientsStub；9）ClientsStub从网络中获取这些网络消息；10）ClientsStub带返回结果返回到调用者（client）。,可以看出,上述步骤的主要作用是将Client得远程过程调用转化为对ClientsStub的调用，再转化为对Server得本地调用，所有中间过程的细节隐藏于双方的Stub中。显然1.由于ClientsStub的作用，使得Client可用常规过程调用方式去调用远程过程，从而实现了通信。2.由于ServersStub的作用，使得Server程序可以独立于调用者来编程，因而具有较大的灵活性。3.由于这两种Stub的作用，使得调用者就好像在本地站点上直接调用了所需的远程过程。4.双方Stub的作用是屏蔽网络的存在，在不同站点间构筑了一条通信信道，使得caller和callee就好像在单机系统一样。,RPC的语义,1.Atleastonce(至少一次）2.Atmostonce(至多一次）3.Exactlyonce(恰好一次）4.Lastofmany(最后一次),RPC的一些问题,1.参数传递方式2.RPC的参数缺乏在系统内异构机间通用的能力3.不便于利用广播功能4.缺乏在一次调用过程中多次获得返回结果的能力5.缺乏传递大数据量的能力,思考题-3,在实现RPC时，“调用者如何得知被调用者实际运行在哪个站点上”是一个必须要解决的问题，试问你如何解决此问题？,分布式系统的资源管理,系统中有多种资源，每种资源有多个设备，每个设备又可能有多种活动，而这些设备又分散在系统的多个站点上。因此，系统设置了多个管理者来管理这些设备，于是，形成了多个设备与多个管理者之间错综复杂的关系。两种观点一.从单个资源与多个管理者（RM)的关系出发，有4种管理方式1.集中式2.分割式3.轮流式4.分散式,二.从多个资源与多个管理者的相互关系出发，有3种管理方式1.集中式：一类资源由一个管理者来管理，它控制和管理该类全部资源。2.集中分布式：一类资源由多个管理者来管理，但每个具体资源只由一个管理者对其负责。3.完全分布式：一类资源存在多个管理者，而且该类中的每个资源都由这多个管理者通过协商方式共同管理。,投标算法（bidding）,1.申请者申请资源时，先广播招标消息；2.当一资源管理者收到这一招标消息后，若所在站点有所需资源，则它根据一定方法计算出“标数”，然后给申请者发一条投标消息；否则回复一条拒绝投标的消息；3.申请者收到所有的投标消息后，根据一定的策略选择一个投标者，并直接向它发一条申请资源的消息；4.收到此申请资源消息的管理者将申请者的名字排入其等待队列，并在可以分配该资源时，发消息通知资源申请者；5.资源申请者使用完资源后，通知资源的提供者回收该资源。,特点,1.不会出现饥饿现象；2.特别适合于共享通路结构。,分布式死锁处理,Coffmman曾指出：进程在使用可重用性资源时，产生死锁的4个必要条件1.资源的互斥使用性2.进程的占用并等待性3.资源的非抢占性4.进程的循环等待性解决死锁问题的方法1.死锁预防（deadlockprevention）2.死锁检测（deadlockdetection）3.死锁避免（deadlockavoidance）4.死锁恢复（deadlockrecovery）,资源分配图（resourceallocationgraph）业已证明：对于给定的资源分配图，若图中出现环路，则表明系统可能发生死锁。特别，若系统中的每类资源只有一个例示，则图中的环路表明系统已