第九章网络与分布式操作系统

第九章网络与分布式操作系统由于网络操作系统与分布式操作系统所采用的技术大多是相通的，帮将它们入在一起介绍。9.1计算机网络一、网络的概念：计算机网络是利用通信设备和通信线路，将地理上分散而且有相对独立功能的多个计算机系统，按照某种原则相互连接在一起构成的计算机体系，它是计算机技术和通信技术相结合的产物。二、网络组成：1、组成：独立计算机、通信处理机、通信线路。2.结点:网络中的主机及所附带的外部设备,也叫站点。三、网络分类：（一）按网络覆盖的地理范围，可将网络分为局域网和广域网、城域网。（二）按照入网计算机的统一性分为：同构网络和异构网络1、同构网络：在分布式操作系统中常采用同构网络因为进程的动态迁移要求迁出站点与迁入站点具有相同或兼容的硬件环境。2、异构网络：由不同类型的机器所构成的计算机网络。在大型网络操作系统中，常采用异构网络，因为它对入网机器的类型没有任何限制。四、网络的拓扑：网络系统中的各个站点在物理上的联结方式。每种拓扑结构各有优点、缺点，对拓扑结构的评估常用以下标准：1、基本成本：将系统中各站点联结起来所花费的代价。2、通信成本：把一个信息由站点A传送到站点B的距离3、可靠性：如果一个通信链或站点失效，是否影响基余站点之间的通信。（一）全联通拓朴结构：每个站点都直接与其它站点相连，这种结构的代价是昂贵的，因系统中任两个站点之间必须有直接的通信链。*基本成本高，按站点数成平方地增长。*传送速度快，因任两站点间的信息传送仅涉及一条通信链*可靠性高，因仅当所有通信链都失效时，系统割裂。（二）部分互联结构：1、仅在一部分站点之间存在通信链，因而基本成本较低。2、通信速度慢，由消息的传递可能要经过几个中间站点。3、可靠性较差。（三）层次结构：除根站点外，每个站点均有唯一的父亲和若干个儿子1、基本成本低2、通信时往往要涉及几个节点3、除叶站点外，任何一个站点的失效将把网络分割为几个互不相交的子树。（四）星型结构：1、基本成本与站点数成线性比例关系2、通信成本较低因一个站点与另一个站点之间的通信至多仅需两步。3、可靠性差:一方面中心站点可能成为系统的瓶颈，另一方面，中心站点一旦失效，网络瘫痪。（五）环形结构（六）总线结构9.2通信与协议1、OSI：由ISO制订的开放系统参考模型OSI成为网络通信的标准，逻辑上，不同主机的各层之间能相互通信（对等通信）。2、协议：不同主机相同层次间对等的通信规则称为协议，K层之间的对等通信协议称为K层协议。在实现时，信息自发送站点由上层向下层传递，横向止于物理层，最后在接收站点自下层至上层纵向传递。发送站点的每一层均对信息做某种处理，加上一个“头”，然后向下层传播，接收站点的每一层将对应的“头”去掉。3、OSI中，各层协议主要功能：（1）物理层：负责两个站点之间字位流的传输。（2）链路层，负责提供传输错误的恢复功能（3）网络层：负责将消息分解为传输单位，并选择路径。（4）传输层：负责站点之间的消息传送。（5）会话层：负责进程间通信。（6）表示层：负责数据转换。（7）应用层：负责提供用户界面。9.3计算机模型一、数据迁移：当处于站点A的用户想要存取驻留于站点B的数据（文件）时，系统有两种方式：（1）将整个文件都传送给站点A,此后对文件的访问便成为局部的了，当用户A不再需要该文件时，它便被送回到站点B。（2）仅将文件的一部分传送到A，如果以后还需要，再传送另一部分，当站点A用户不再需要该文件时，将其修改部分传送回站点B。二、计算迁移在某些环境中，迁移计算比迁移数据效果更好例如：设站点A处的进程P要使用站点B处的文件，它不是将B处的文件取过来，而是执行一个远程过程调用，以调用一个在B点已定义好的过程，该过程可对P所需的文件进行适当计算，然后将结果发送给进程P。另一种方法是：进程P发一个消息到站点B，然后由站点B处的操作系统创建一个代理进程Q，其功能是执行P所指定的任务，当Q完成使命后，通过消息将结果送给P，此法允许P、Q在不同站点并行。三、作业迁移当一个作业到达时，它可以全部或部分地在不同站点处执行，其优点是：1、负载平衡：作业或作业步可以在网上分布以均衡工作负载，2、计算加速：如果一个作业可以划分为若干子作业，这些子作业可以在不同站点处并行执行，则整个作业的处理时间能被缩短。3、硬件优选：有些作业可能只适合于在专用处理机上运行，例如矩际求逆。4、软件优选：有的作业可能需要某些站点处的特别软件，而该软件不适合迁移，或迁移开销比作业开销大。四、进程迁移：进程迁移是将正运行于某站点处理的进程迁移到另一站点，由于在迁移时刻进程已经在原站点运行了一段时间，迁移时不仅需要迁移其代码和数据，还应迁移与进程有关的数据结构，即进程控制块，进程迁移的目的是实现负载平衡。9.4事件定序即确定两个事件发生的先后次序关系，这在集中或紧耦合系统中是容易做到的，因系统中只有一个公共内存和一个实时时钟；然而在网络和分布式系统中，没有公共内存和实时时钟，要确定事件发生的次序有时是不可能的，网络或分布式系统中的“前发生”关系只是一种偏序（非自反）。一、前发生关系：1、进程内的事件：由于一个进程用的程序是有序的而且在各自的处理机上运行，故一个进程内的所有事件是有序的。2、前发生关系：（1）如果A和B是同一进程内部的事件，而且A在B前执行，则AB（2）如果A是一个由某一进程发送消息的事件，B是由另一进程接收该消息的事件，则AB；（消息只有在被发送后才能被接收）。（3）如果AB且BC，则有AC.由于一个事件不可能在其本身之前发生，因而关系“”是非自反的偏序。如果两事件A和B之间不存在“”关系，则二者可以并发执行，且它们之间无因果关系。例：三个进程P、Q、R，它们在不同处理机上运行，图中圆圈表示事件，箭头表示进程间的消息传送，由图可知：(参见备课本)二、全序关系：为了确定两事件发生的次序，或者需要一个公共时钟，或需要完全同步的时钟，在网络和分布式系统中很难实现：1、定义：（在不使用物理时钟前提下定义前发生关系）全序要求：对于事件A和B，如果AB，则A的邮戳时间应小于B的邮戳时间。2、在分布式和网络中实现上述全序要求方法：在每个进程内部定义一个逻辑时钟LCi；它给同一进程内的各事件赋予不同的数：某一事件的逻辑时钟值就是它的时间邮戳，在一进程内部，逻辑时钟可以保证：如果事件A在事件B之前发生，则有Lci(A)Lci(B).在不同的进程之间此法行不通。例：设两个进程P1和P2相互通信，假设P1于Lci(A)=200时发送消息给P2（事件A），而P2于Lci(B)=190时接收到此消息(事件B)，显然违反定义。解决上述矛盾的方法是：进程在接受到一个消息时，而且该消息的邮戳时间比接收进程的邮戳时间当前值还大时，接收进程推进他的逻辑时钟。具体地，如果进程P接到一个邮戳时间为t的消息(事件B)，Lci(B)t,则她推进其时钟，使Lci(B)=t+1。9.5进程互斥为了解决网络和分布式系统中互斥问题，必须提供类似信号灯的同步机构。为简单起见，这里只讨论二值信号灯的实现（相当于锁），由于网络和分布式系统中的互斥所涉及的进程可能位于不同站点，它们之间没有公共内存，因此比较复杂，这里假设共有n个处理机，所有处理机依次编号为1—N，每个处理机中仅有一个进程，且进程与处理机具有相同编号。一、集中方式：1、基本思想：系统中有一个进程负责协调对于临界区的进入。每一个要求进入临界区的进程都必须发送一个请求给协调者进程，仅当收到协调者进程的回答信号后，它才能进入自己的临界区；当一个进程退出临界区时，也需发送一个释放信号给协调者进程，然后继续执行。当收到一个请求消息时，协调者进程需考查是否有某些进程正在其临界区内，若无，协调者进程发送一个回答消息给请求进程，否则请求进程需排队等待，若协调者进程收到一个释放消息，则它给等待队列中的某一进程发送回答信号允许它进入其临界区。2、特点：（1）无死锁（2）如协调者进程是公平的，如FCS,则不会发生“饿死”现象。（3）每次进入临界区需三个消息：请求、回答、释放.二、分布方式：1、方法：当一个进程P要进入其临界区时。它产生一个新的时间邮戳TS，并发送一个Request(P,TS)给所有其它进程，当某个进程接收到此消息时它可能立即回答（如果它当前不在其临界区内）；也可能延迟回答（如果它当前正在其临界区内）。一个收到系统中所有进程回答信号的进程可以进入它的临界区，当一个进程退出其临界区后，它需要给所有向它发来请求消息的进程发送回答消息。2、进程作出立即回答或延迟回答的决定因素：（1）如果进程正在它的临界区内，延迟回答（2）如果一个进程不想进入特的临界区，立即回答;(2)如果一个进程想进入但尚未进入它的临界区，该进程考查所有保存的请求表，此表用于保存该进程已收到但尚未回答的消息，并将当前收到的REQUEST(P,TS)消息中的TS与该表中所有消息的TS作比较，如果这个TS比表中所有消息的TS都小,则立即回答进程P，否则REQUEST被加到等待表中3、上述算法特性：（1）可实现互斥（2）确保无死锁（3）无“饿死“情况（4）每次进入临界区需2（N-1）个消息。三、标志传递方式：1、方法：该法仅适用于逻辑拓朴结构为环形的系统，为实现互斥，系统中有一个标志。它作为特殊类型的消息在系统中环行。当一个进程接收到这个标志后，它就可以进入其临界区，并扣留这个标志；当它退出临界区之后，标志才被释放，并沿环路继续绕行，如果一个接收到标志的进程并不想进入其临界区，只需放行此标志。2、此法特点：（1）可实现互斥。因系统中只有一个标志，则最多只有一个进程在其临界区内。（2）无“饿死”情况（在单向环形系统中）（3）两种失效情况：一是如果标志丢失，则应能发现并选择一个进程产生新标志。二是如果一个进程夭折了，则逻辑环断裂，此时系统应能重构一个新的逻辑环。9.6进程同步与进程通信在网络与分布式系统中，同步机制与通信机制通常结合在一起:通信可以同步进行，也可以异步进行，对于前者，通信伴随着同步；对于后者，通信不伴随同步。当通信信息量为零时，进程之间便可以实现单一的同步。同步与通信机制常分为两类，消息传递和远程过程调用。一、消息传递：消息传递分为同步和异步两类，前者需等待接收者的回答后继续，后者不需等待来自接收者的回答。（一）同步消息传递：1、需提供以下系统调用命令：（1）发送命令：send（接收者、消息、回答）将消息发送到指定的接收者，然后挂起，等待来自接收者的回答，之后继续。（2）接收命令：receive（发送者、消息），等待接收来自发送进程的消息。（3）回答命令：reply（发送者，回答），将回答信息传给发送进程，使之继续执行。2、异步消息传递的形式(高等教育出版社《操作系统教程》周长林P219)(一)异步消息传递：1、所需系统调用命令：(1)发送命令：send（接收者，消息/回答），将消息或回答发害给接收者，然后继续。(2)接收命令：receive（发送者，消息/回答），由发送者处接收消息或回答，然后继续2、进程间异步消息传递形式：利用发送命令与接收命令可在任意时刻实现同步要求：(P219)二、远程过程调用：与一般的过程调用相比较，远程过程调用的突出特点是调用者与被调用者分别属于不同进程，它们均是主动体，而且二者常运行于网络或分布式系统中不同站点上，这带来如下问题：(1)在本地过程调用中，调用参数及返回结果一般通过堆栈在调用者与被调用者之间传递；而在远程调用中，调用参数与结果通常作为消息在调用者之间传递；(2)在本地过程调用中，调用过程与被调用过程同时存在，并且属于同一地址空间，而在远程过程调中，调用者与被调用者有不同的生存期，而且通常无公共存储区域。(一)远程过程调用形式(P220图10-12)方法：调用进程称作顾客进程，被调用进程称为服务进程，顾客进程调用服务进程中的过程，调用参数以消息的形式由调用者传送给被调用者,调用者挂起，被调用者执行相应的过程，执行完毕将返回值以消息形式传送给调用者，然后二者分别继续。(二)远程过程调用的实现：在