分布式操作系统2(1).ppt

Communication,Chapter2,第二章分布式系统的通信,分布式系统在资源管理，进程通信和系统结构等方面与单机OS有很大差别。1、单处理机系统进程间通信采用共享存储器，甚至最基本的同步形式，如信号量都要求一个字的内存是共享的。2、分布OS必须有一个单一的、全局的进程间通信机制(本地和全局);有一个全局的保护方案。因无共享主存，必须用消息传递同步原语,用RPC（remoteprocedurecall）代替单机共享变量同步原语(忙一等待和信号的P、V操作等)。,一、分层协议大多数应用软件依靠网络软件通信，并不直接与网络硬件打交道，网络软件统一规定了交换消息的格式和含义。亦称分层协议。分层协议：iso-osi,ieee803,atm异步传输模式，适用于分布式系统。1早期ISO提出的七层参考模型（1981年）物理层数据链路层网络层传输层会话层表示层应用层,LayeredProtocols(1),Layers,interfaces,andprotocolsintheOSImodel.,2-1,LayeredProtocols(2),Atypicalmessageasitappearsonthenetwork.,2-2,2TCP/IP互联网协议是为互联网开发的第一套协议，得到美国军方和NSF及政府机构的资助，它的开发成功，使位于107个国家的各种组织机构的3600多万台计算机互联成全球的因特网成为可能。TCP/IP五层参考模型：,物理层：,数据链路层：,物理层是用于传输信号0、1的。物理层协议讨论电气、机械、信号接口标准化问题。如RS-232-C是串行口通信线的标准。,将一些二进制位（串）组织到单元（帧）中，并检查每帧是否被正确的接收。（建立校验和、纠错的机制）。,消息,帧头,校验和（帧尾）,定义各种操作与参数（帧序号）,DataLinkLayer,Discussionbetweenareceiverandasenderinthedatalinklayer.,2-3,网络层：,从发送者到接收者有一些转发的接点，在转发处进行的最优路由选择是网络层的主要任务。,1、面向连接的网络层协议：X.252、面向非连接的网络层协议：IP,传输层：,传输层是整个协议层次的核心，其任务是为从源端机到目的机提供可靠的、价格合理的数据传输，而与当前使用的网络无关。,1、可靠的面向连接的传输协议：建立在X.25或IP上，如TCP(传输控制协议)。,TCP是一个可靠的面向连接的传输协议，将从一台计算机发出的字节流毫无差错地发往互联网上的其他计算机。（有流量控制功能）,2、不可靠的无连接的传输协议：UDP(用户数据报协议),UDP是一个不可靠的无连接的传输协议，用于不需要TCP的排序和流量控制能力，而是自己完成这些功能的应用程序。如传输语音或影像，（不会影响传输的速度）。,会话层：传输层的增强版，提供会话控制、跟踪以及同步。实际中并不应用。,表示层：可定义一些特殊的记录，使得内部表示方法不同的计算机间的相互通信变得很容易。,应用层：实际上只是公共事务遵循的一个杂项协议的集合。如：E-mail,FTP,Telnet等,数据链路+物理层,网络层,传输层,应用层,2.2异步传输模式网（ATM）,在最近20多年即69-90年代中，计算机在性能上已提高了许多数量级，而网络性能却没有大幅度的提高。,ARPANET1969创始时，56KB的通信线路；70年代末-80年代初，多采用1.5Mbps的T1通信线路;80年代-90年代,主干网发展成为45Mbps的T3网；Internet上的大多数传输线仍是T1或更慢的线路。,90年代新的发展是通信速度以155Mbps为最低标准的ATM技术出现给分布式系统带来巨大的冲击。,现代通信网中广泛使用的是电路交换和分组交换两种方式。电路交换方式适用于电话业务。分组交换适用于数据业务。而ATM信元中承载的是宽带综合业务，既有电话业务，又有数据业务，还有其他业务。ATM采用的是ATM交换方式，它是一种新的交换方式，它既像电话交换方式那样适用于电话业务，又像分组交换方式那样适用于数据业务，并且还能适用于其他业务。,通信网上的传输方式可分为同步传输方式(STM)和异步传输方式(ATM)两种。如ISDN用户线路上的2B+D，以及数字电话网中的数字复用等均属于同步传输方式，其特点是在由N路原始信号复合成的时分复用信号中，各路原始信号都是按一定时间间隔周期性出现，所以只要根据时间就可以确定现在是哪一路的原始信号。异步传输方式的各路原始信号不一定按照一定时间间隔周期性地出现，因而需要另外附加一个标志来表明某一段信息属于哪一段原始信号。例如采用在信元前附加信头的标志就是异步传输方式。,同步与异步传输,ATM高速主干网,能有较传输声音和视频数字信号的高速网络。ATM（AsynchronousTransferMode)异步传输模式网。目前有支持155Mbps，622Mbps等,ATM主干网络示例,ATM路由器,ATM路由器,ATM路由器,ATM高速主网,ATM工作站,FDDI网10Mbps,以太网10Mbps,令牌环网,ATM服务器,ATM服务器,ATM提供了一套网络用户服务，但与网络上传输的信息类型无关。这些服务由ATM协议参考模型定义。模型定义出对高层的服务和操作维护ATM网络所需的功能。,ATM物理层,ATM适配板插在计算机中，将信元流发送到线路上或光纤上。传输流必须是连续的。当没有数据可以逆行传送时就发送空信元。适配板在物理层上可采用SONET(SyncronousOpticalNETwork，同步光纤网)，将它的信元放入SONET帧的负载域上，优点是它和AT及T的固际传输系统以及其他使用SONET的载体相兼容。OC-1:基本的51.48Mbps通道称为OC-1;系统可能将发出一组n个OC-l帧来作为一个组,当它使用n个独立的OC-l通道和OC-nc(供连接用)组成一个高速通道时，可用OC-n来标识。OC-3:155.520Mbps,OC-12:622.080MbpsOC-48:2.5Gbps,ATM层,ATM的基本特征是信息的传输、复用和交换都是以信元(cell)为基本单位。按照CCITT的建议，每个信元的长度为53个字节，其中前面5个字节为信头，用来表示这个信元来自何处，到何处去，是什么类型等。后面48个字节是要在线路上传送的信息。由于ATM有信头，所以会有一部分线路传输能力用在信头上。因此，用户可以使用的传输速率将不是155.52Mbits，而是155.52Mbit/53*48=140Mbits。,ATM是定长度的信元，它可以适应用户不同速率分配的要求。例如，某用户要与A、B、C三个用户通信，其速率分别为20、40、60Mbits，这样在用户线路上每出现一个给A的信元，就会有两个给B的信元和三个给C的信元。由于上述三个通信用户合起来的速率是120Mbits，尚未达到155.52Mbits，因此线路还会有一些时间处于空闲状态。所以ATM可以非常灵活地适配各种不同速率的要求，用户几乎可以按任何方式把信道分割成任意多个不同速率的子信道。只要它们的速率之和不超过信道的总容量，即155.52Mbits就可以。,ATM适配层,在155Mbps速率下，每3us有一个信元到达。现在很少有CPU能够处理超过每秒300000次中断。因此需要一个机制以使计算机只发送包，而由ATM硬件将包拆分成信元并传送信元。信元在接收后被重新组装。每个包而不是每个信元产生一次中断。这种拆分和组装信元是适配层的工作。,在ATM信元头中只用了一位，常常为0，但在包的最后一个信元中置l。最后一个信元在最后8个字节中包含一个数据尾。在大多数情况下，一个包的结束和开始将有一些填充(用0)。当发现一个包结束位置位，就取出并处理数据尾。数据尾有四个域，前两个域每个域有1个字节长暂时末用，然后是2个字节的域给出包的长度，最后是4个字节的包检验和、填充字段和包尾。,ATM交换机,一个交换机有输入线、输出线和一个并行的交换结构将它们连接在一起。因为一个信元必须在3us(在OC-3)内完成交换，而且同一时间可以有和输入线数同样多的信元到达，所以并行交换是非常重要的。当一个信元到达以后，交换机检测其VPI和VCI域，再根据虚拟线路建立时存放在交换机内部的信息，将信元至正确的输出端口。在信元结构中，VPI和VCI是最重要的两部分。这两部分合起来构成了一个信元的路由信息，也就是这个信元从哪里来，到哪里去。ATM交换机就是根据各个信元上的VPIVCI来决定把它们送到哪一条线路上去。,在异步传递方式中，使用虚路径和虚通道的概念，也可以把一条通信线路划分成若干个子信道。例如在一条宽带ISDN用户线路上，要进行5个通信，其中到A地三个通信，到B地两个通信，这些通信里有电话通信，数据通信，图像通信等。可以用VPI=1表示向A地的通信，VPI=2表示向B地的通信。到A地的三个通信分别用VCI=4、VCI=5、VCI=6来代表，到B地的两个通信用VCI=5、VCI=6来表示。在线路上所有VPI=1的信元属于一个子信道，所有VPI=2的信元属于另一个子信道，一般把这两个子信道都叫做虚路径，每个虚路径还可划分为若干个虚通道。,VPI和VCI（virtualpath虚路径和virtualchannelidentifier虚通道）,例子就是2个虚路径和5个虚通道。,当两个信元从不同的输入线同时到达并希望从同一个输出口输出时，就产生了问题,一个方案是随机选取一个并转发它，而一直保留另一个信元。如果两个端口每一个都有对于同一目的地的信元流，就建立了大量的输入队列，阻塞其后欲想输出到空闲输出端口的信元，这个问题叫作线路前端阻塞。,一个不同的交换机设计是将信元拷贝到和输出缓冲区相联系的队列中，而不是保留在输入缓冲区中。这种万法消除了线路前端阻塞，且性能也较好。交换机也可以有一个缓冲池既用作输入缓冲又用作输出缓冲。还有另一个可能是在输入端有缓冲区，即使不能交换第一个信元，但也允许在线上交换第二个或第三个信元。,ATM对分布式系统的影晌,1、对于高速的广域分布式系统，在许多应用中的延时，特别是相互作用的应用中的延时需要新的协议和系统结构处理。2、另外一个问题是流量控制。一个选择是在交换机和适配器上设置大量的缓冲区，但这又会导致价格的上升。另一个可能的选择是进行速度控制，接收者和发送者达成协议决定发送者能以每秒多少位传输。3、处理滞后的另一种不同方法是发送一些位，然后停止发送进程，在等待回答时，运行其他进程。,一般的高速网络和ATM网络给分布式系统带来了机遇，但利用他们的优点并不简单。,2.3客户-服务器模式,客户-服务器模式（C/S）由一组协同进程组成，这组进程有服务器和为客户进程，他们都运行在相同的微内核中。C/S常以简单的面向非连接的请求/应答协议为基础,客户向服务器发出一个请求消息请求一些服务(如读文件块)，服务器完成后返回所要的数据或者给出一个错误码，指出工作未完成。,多层协议的报文要加多个报文头，使系统开销过大，对于基于局域网的分布式系统不合适，而客户/服务模式可以简单地利用面向非连接的请求/应答协议实现通信，既简单，又有效，无须建立连接和路由选择。常用于Internet上的是浏览器/web服务器/数据库服务器三层结构。,ClientsandServers,Generalinteractionbetweenaclientandaserver.,1.25,主要优点：1、简单。客户发出一个请求，得到一个应答。在使用之前无须建立连接也不用释放连接，应答消息就是对请求的确认。2、有效性。仅需要三层协议，因而也就更有效。物理层和数据链路层协议处理从客户机发送数据到服务器和接收返回的数据。以及第5层（会话层）是请求/应答协议，它定义了合法的请求集和对这些请求合法的应答集。,根据这种简单的结构，通信服务可以简化为由微内核提供的两个系统调用，一个是负责发送报文，一个是负责接受报文，这些系统调用可通过调用Send()和Receive()这两个库过程来实现。,AnExampleClientandServer(1),Theheader.hfileusedbytheclientandserver.,AnExampleClientandServer(2),Asampleserver.,AnExampleClientandServer(3),Aclientusingtheservertocopyafile.,1-27b,Client-ServerTCP,NormaloperationofTCP.TransactionalTCP.,2-4,2.3.3寻址,客户为了发送消息给服务器，它必须知道服务器的地址。如果在目的机器上有多个进程在运行怎么办?若用网络地址识别进程意味在每个机器上只能运行一个进程，有时这个限制并不致命，有时则是个重要的约束。一个可供选择的寻址系统是将消息传送给进程而不是计算机。地址由两部分名字:机器号和进程号，机器号用于使内核将消息正确地发送到适当的机器上，进程号用于使内核决定消息要给哪一个进程。,例如：伯克利的UNlX系统上，大部分通信采用这种方式，即用32位lnternet地址指定机器，给出16位数字用于本地ld字段。然而,cess(机器进程)寻址方式并不理想，特别是由于用户要知道服务器在哪，因此是不透明的，而透明性正是分布式系统设计的目标。,1、一个可选择的方法是给每个进程分配唯一的地址，而不确证其机器号。必须有一个中央控制地址分配器，只包含一个计数器。当接收到一个地址请求时，它返回计数器的当前值并将计数器自动加1。像这样的中央控制部件无法用于一个大的系统，因此应该避免。,C,S,1,2,客户,服务器,内核,1：请求243.02：给199.0的响应,199,243,图：机器进程编址方式,2、另一个分配进程标识号的方法是:让每个进程花相当大且专用的地址空间中选择自己的标识号，如64位二进制整数的空间。两个进程选择同一数字的可能性很小，系统平衡很好。怎么知道发送消息给哪-个机器呢?在支持广播的局域网中，发送者广播一个特殊的定位包，在网络上所有的机器均可收到，并查看地址是不是它们的，如是，则给出网络地址(机器号)。发送方内核使用这个地址并“记住”它，避免下一次再广播。,C,S,1,2,3,4,1:广播2：“我在这里”3：请求4：应答,图：带有广播的进程编址,客户,服务器,内核,3、尽管这种设计是透明的，甚至用了缓存，但广播给系统增加了额外的负担，其实可以用一台额外的机器提供高层的机器名和机器地址的映射来避免这种额外的负担。每次客户机运行，首先试图使用服务器，客户机发出一请求消息给名字服务器(nameserver)，问一个目前服务器所在的机器号，有了这个地址后，可以直接发送请求。,需要一个中间部件名字服务器。当然名字服务器可以复制，但这样做，带来了维护其数据一致性的问题。,C,S,4,3,NS,1,2,名字服务器,1：查找2：NS应答3：请求4：应答,图：通过名字服务器进行地址查询,234阻塞与非阻塞原语,一、阻塞原语(有时称为同步原语):当一个进程调用Send原语，它指定了目的地以及发送到该目的地的缓冲区数据。消息被传送时，发送的进程被阻塞(即挂起)。直到消息传送完毕，其后的指令才能继续执行。同样，调用receive时，直到一条消息被实际接收并放入由参数指定的缓冲区时才能返回控制权。在一条消息到达前，调用receive的进程被阻塞(即挂起)。,图：阻塞发送原语,二、非阻塞原语(有时叫异步原语)：如果send原语是非阻塞的，在发送消息前它立即将控制权返回给调用send的进程。调用发送的进程可以和消息传送并行运行，而不是让CPU空闲(设想没有其他进程可执行)。,主要的缺点：在消息被发送之前，发送者不能修改消息缓冲区。后继的进程在传输过程中覆盖该消息是很可怕的。更糟的是，发送的进程不知道传送何时进行，所以它无法知道什么时候重新使用缓冲区是安全的。,图：非阻塞发送原语,第一个解决方法是内核将消息拷贝到内部缓冲区，其后允许程继续执行。从发送者的观点看，这个方案和阻塞调用的相同:一但它获得控制权，就可以重新自由地使用缓冲区。当然，消息还没有被传送，所以发送者事实上并没有被它阻碍。这个方法的缺点是:每一个要传送的消息都要从用户区拷贝到内核区。对于许多网络接口，消息以后将被拷贝到硬件传输缓冲区，第一次拷贝显然被浪费了，额外的拷贝降低了系统的性能。,第二个解决方法是当消息被发送后，中断发送者并通知它缓冲区可用，这里不需要备份，节省了时间。尽管该方法高效且允评最大程度的并行化，但缺点大:基于中断的程序不易编写正确，无法调试不便。,如果仅有一个控制线稚可用，选择如下:(1)阻塞传送(CPU在数掂传输时空闲）；(2)使用拷贝非阻塞传送(CPU时间浪费在额外的拷贝上）；(3)使用中断的非阻塞传送(使编程困难)。在正常的情况下，第一种选择最好。虽然它不增加并行度，但容易理解和实现，而且不需要内核缓冲区，消息能更快地发送出去。如果某些应用中进程和传送需要重叠，则使用拷贝的非阻塞发送是最好的选择。,同步与异步原语：,一种观点认为：同步原语和异步原语的实质区别在于发送者在取回控制权后能否很快重新使用缓冲区，而不用害怕干扰发送。至于被发送的数据何时到达接收者则是另外一回事。,另种观点认为：同步原语指的是在接收者接收到消息并将确认消息返回给发送者之前阻塞发送者。即如果发送者被阻塞到接收者确认这条消息，则这是一个同步原语。如果发送者能在消息被拷贝或发送之前取回控制权，这个原语就是异步的。,2.3.5有缓冲和无缓冲原语,无缓冲原语，意味着将一个地址指定给一个特定进程，调用receive(addr,&m)告诉运行的机器内核，调用的进程正在监听地址addr,并且准备接收发送到那个地址的消息。m指出了一个消息缓冲区用于保存传送来的消息。当消息到来，调用接收原语的机器内核将消息拷贝到缓冲区，并解除该进程的阻塞。只要服务器在客户机调用send原语前调用receive原语，就运行良好。当发送比接收先发生，就会产生问题：服务器的内核如何知道它的哪一个进程在使用最近到达的消息中的地址，在哪里拷贝消息?,1、一个实现方案是丢弃消息，使客户机超时，并希望服务器在客户机传送前调用接收原语。这个方法很容易实现。但客户机(更可能的是客户机内核)可能在这以前己试了许多次。如果多次失败，客户机内核可能会放弃并错误地认为服务器损坏或者地址无效。如图（a）,2、让接收内核在短时间内保存到来的消息，以防receive原语可以很快完成。尽管这些方法减少了消息被丢掉的可能性，但需要缓冲区