网络与分布式系统课件.pptx

《网络与分布式系统课件.pptx》由会员分享，可在线阅读，更多相关《网络与分布式系统课件.pptx（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、操作系统（第操作系统（第3 3版）版）第 8 章 网络与分布式处理第 8 章 网络与分布式处理8.1 8.1 分布式系统概述分布式系统概述8.2 8.2 网络服务器网络服务器8.3 8.3 分布式进程管理分布式进程管理8.4 8.4 进程迁移进程迁移8.5 8.5 分布式进程通信分布式进程通信8.6 8.6 分布式进程同步与互斥分布式进程同步与互斥 8.7 8.7 分布式进程死锁问题分布式进程死锁问题8.1 分布式系统概述q 分布式能力包括以下几个方面分布式能力包括以下几个方面 通信结构通信结构 、网络操作系统、网络操作系统 、分布式操作系统、分布式操作系统 q 通信结构通信结构 具有结构的一

2、组模块构成了通信结构具有结构的一组模块构成了通信结构 一个简单的通信结构一个简单的通信结构 通常，通信涉及三个方面：应用、计算机和网络通常，通信涉及三个方面：应用、计算机和网络 。因此，。因此，一个通信任务组织成相对独立的三层：网络存取层、传输层和一个通信任务组织成相对独立的三层：网络存取层、传输层和应用层：应用层：网络存取层负责的是计算机与其连接网络之间的数据交网络存取层负责的是计算机与其连接网络之间的数据交换换传输层为所有应用提供了可靠的传输机制传输层为所有应用提供了可靠的传输机制应用层包含了支持各用户应用所需的逻辑应用层包含了支持各用户应用所需的逻辑q 开放式系统互连通信结构开放式系统互

3、连通信结构 开放式系统互连开放式系统互连OSIOSI七层模型七层模型 物理层物理层 数据链路层数据链路层 网络层网络层 传输层传输层 会话层会话层 表示层表示层 应用层应用层8.1 分布式系统概述8.2 网络服务器q 服务器的结构服务器的结构 服务器与网络上的其它工作站服务器与网络上的其它工作站样，它有一个网络接口样，它有一个网络接口模块，该模块包括了与局域网交互所需的硬件和软件；用户模块，该模块包括了与局域网交互所需的硬件和软件；用户工作站也包括了一个网络接口。此外它还包含了与服务器通工作站也包括了一个网络接口。此外它还包含了与服务器通信的一些网络逻辑信的一些网络逻辑 这种结构的服务器功能强

4、，而且灵活，其功能表现在这种结构的服务器功能强，而且灵活，其功能表现在它可用于控制各种类型的资源它可用于控制各种类型的资源 q 磁盘和文件服务器磁盘和文件服务器 文件服务器文件服务器 对文件进行几种存储和管理、自动备份和恢复、用户流对文件进行几种存储和管理、自动备份和恢复、用户流动性动性 、与其它文件服务器进行连接、与其它文件服务器进行连接 磁盘服务器磁盘服务器 许多文件服务器只不过提供了一个中心磁盘设施，作为个人计许多文件服务器只不过提供了一个中心磁盘设施，作为个人计算机用户局部存储器的扩充，这样的系统有时叫磁盘服务器算机用户局部存储器的扩充，这样的系统有时叫磁盘服务器 文件高速缓冲存储器的

5、一致性问题文件高速缓冲存储器的一致性问题 问题的产生问题的产生 因为使用文件高速缓冲存储器保留最近存取的文件记录，减因为使用文件高速缓冲存储器保留最近存取的文件记录，减少对远程服务器必须进行的存取次数，致使有时产生文件高速缓少对远程服务器必须进行的存取次数，致使有时产生文件高速缓冲存储器的一致性问题冲存储器的一致性问题 解决办法解决办法 -最简单方法是对文件采用加锁技术，以防止多个客户机同最简单方法是对文件采用加锁技术，以防止多个客户机同时存取一个文件时存取一个文件 8.2 网络服务器 更有效的方法是允许任意多的进程同时打开一个文件读更有效的方法是允许任意多的进程同时打开一个文件读并创建各自的

6、客户机高速缓存。但当有一个对服务器的请求是并创建各自的客户机高速缓存。但当有一个对服务器的请求是打开文件的写请求，而其它进程打开文件是读存取对，文件服打开文件的写请求，而其它进程打开文件是读存取对，文件服务器采取两个活动。务器采取两个活动。打印机服务器打印机服务器 打印机服务器可以处理许多用户工作站的打印请求。这不打印机服务器可以处理许多用户工作站的打印请求。这不仅可以节省打印费用，而且使得打印更加容易和打印速度更快仅可以节省打印费用，而且使得打印更加容易和打印速度更快 调制解调器服务器调制解调器服务器 当用户向服务器请求存取调制解调器并提供一个电话号码当用户向服务器请求存取调制解调器并提供一

7、个电话号码后，服务器启动调制解调器，拨号、并报告结果。如果呼叫成后，服务器启动调制解调器，拨号、并报告结果。如果呼叫成功，向用户提供一个连接。功，向用户提供一个连接。8.2 网络服务器8.3 分布式进程管理q 分布式互斥分布式互斥 互斥算法分类互斥算法分类 集中式算法集中式算法 算法：一个节点作为控制节点，控制对所有共享目标的算法：一个节点作为控制节点，控制对所有共享目标的存取。只有控制节点才能对资源分配进行决策；控制节点中集存取。只有控制节点才能对资源分配进行决策；控制节点中集中了所有必要信息，包括所有资源的标识和位置，以及每个资中了所有必要信息，包括所有资源的标识和位置，以及每个资源的分配

8、状态源的分配状态 优缺点：集中式互斥算法比较简单，容易实现，但如果优缺点：集中式互斥算法比较简单，容易实现，但如果控制节点失败了，互斥机制就无法实现；每个资源的分配和回控制节点失败了，互斥机制就无法实现；每个资源的分配和回收要求与控制节点交换信息，因此，控制节点可能变为瓶颈收要求与控制节点交换信息，因此，控制节点可能变为瓶颈 分布式算法分布式算法 特征：平均来讲，所有节点有着等量的信息。每个节点只特征：平均来讲，所有节点有着等量的信息。每个节点只有整个系统的一部分描述，且必须基于这个信息进行决策。所有整个系统的一部分描述，且必须基于这个信息进行决策。所有节点对于系统的最后决策有着完全相等的作用

9、。有节点对于系统的最后决策有着完全相等的作用。克服时钟同步困难所采用的一个常见方法克服时钟同步困难所采用的一个常见方法 分布式系统中的事件定序法分布式系统中的事件定序法8.3 分布式进程管理q 分布式算法分布式算法 Lamport分布式算法分布式算法 数据结构：数据结构：qj=(Release,0,j)j=1,n 使用的三类信息：使用的三类信息：(Request,Ti,i)表示进程表示进程Pi访问资源的请求信息。访问资源的请求信息。(Reply,Tj,j)表示在表示在Pj的控制下允许访问资源的信息。的控制下允许访问资源的信息。(Release,Tk,k)表示进程表示进程Pk释放先前分配给它的资

10、源释放先前分配给它的资源 8.3 分布式进程管理 算法描述：算法描述：当当Pi请求访问一个资源时，它泄放一个请求信息请求访问一个资源时，它泄放一个请求信息(Request,Ti,i)，时标，时标Ti是本地时钟的当前值，它把这个信息是本地时钟的当前值，它把这个信息放在它自己的数组项放在它自己的数组项qi中，并将这个信息发送给其它所有进程中，并将这个信息发送给其它所有进程 当当Pj接接收收到到信信息息(Request,Ti,i)，时时，它它把把这这个个信信息息放放在在它它自自己己的的数数组组qj中中，并并发发送送信信息息(Reply,Tj,j)给给其其它它所所有有进进程程 当下面两个条件成立时，当

11、下面两个条件成立时，PiPi可以访问一个资源：可以访问一个资源：在在数数组组q q中中，PiPi自自己己的的请请求求信信息息是是数数组组中中最最早早请请求求的的信信息息。由由于于信信息息在在所所有有节节点点的的顺顺序序是是一一致致的的，这这个个规规则则允允许许一一个个而而且且只有一个进程在任何时刻访问所请求的资源只有一个进程在任何时刻访问所请求的资源8.3 分布式进程管理 在本地数组中的所有其它信息比在本地数组中的所有其它信息比qiqi中的信息都晚一些。中的信息都晚一些。这保证这保证PiPi已了解了它的当前请求在所有请求之前已了解了它的当前请求在所有请求之前 进程进程PiPi释放资源时，它泄放

12、信息释放资源时，它泄放信息(Release,Ti,i)(Release,Ti,i)，把它，把它放在自己的数组中，并传送给其它所有进程放在自己的数组中，并传送给其它所有进程 当当PiPi接收到信息接收到信息(Release,Tj,j)(Release,Tj,j)时，它用这个信息置换时，它用这个信息置换qjqj的当前内容的当前内容 当当PiPi接收到接收到(Reply,Tj,j)(Reply,Tj,j)信息时，它用这个信息置换信息时，它用这个信息置换qjqj的当前内容的当前内容8.3 分布式进程管理 令牌传递法令牌传递法 令牌：令牌（令牌：令牌（tokentoken）是进程在任何时间持有的一个实体

13、，）是进程在任何时间持有的一个实体，持有令牌的进程不必请求许可权就可以进入它的临界区。当进程持有令牌的进程不必请求许可权就可以进入它的临界区。当进程离开它的临界区时，再将令牌传递给另一个进程离开它的临界区时，再将令牌传递给另一个进程 数据结构：这个算法需要两个数据结构。一个是被传递的数据结构：这个算法需要两个数据结构。一个是被传递的令牌，另一个是请求数组令牌，另一个是请求数组 算法描述：算法描述：算法的描述程序算法的描述程序 8.3 分布式进程管理8.4 进程迁移q 进程迁移进程迁移 定义定义 进程迁移是指，为了使进程在另一个机器上执行，源机器进程迁移是指，为了使进程在另一个机器上执行，源机器

14、向目标机传送足够数量的进程的状态信息向目标机传送足够数量的进程的状态信息 在分布式系统中，希望进程迁移的理由在分布式系统中，希望进程迁移的理由 负载均衡、通信性能的改善、可用性、利用专用的能力负载均衡、通信性能的改善、可用性、利用专用的能力q 进程迁移机制进程迁移机制 启动迁移启动迁移 由谁启动迁移将依赖于迁移设施要实现的目标由谁启动迁移将依赖于迁移设施要实现的目标 需要迁移哪些信息需要迁移哪些信息 当一个进程被迁移时，需要撤消源系统上的进程，并在目当一个进程被迁移时，需要撤消源系统上的进程，并在目标系统上创建它。这是一个进程的移动，而不是进程映像的复标系统上创建它。这是一个进程的移动，而不是

15、进程映像的复制制 迁移的两种策略：迁移进程的整个地址空间；仅迁移进程迁移的两种策略：迁移进程的整个地址空间；仅迁移进程在内存的那部分地址空间在内存的那部分地址空间 对尚未完成的信息和信号的考虑对尚未完成的信息和信号的考虑q 迁移处理迁移处理 在有些情况下，进程迁移由一个实体进行决策在有些情况下，进程迁移由一个实体进行决策 8.4 进程迁移8.5 分布式进程通信q信息传送机制信息传送机制 分布式信息传送的最普通的模型：客户机分布式信息传送的最普通的模型：客户机/服务器模型服务器模型 采用这种最简单的形式时，信息传送仅需要两个功能：采用这种最简单的形式时，信息传送仅需要两个功能：发送和接收发送和接

16、收q 远程过程调用远程过程调用 概念概念 远程过程调用是对信息传送基本模型的修改，允许不同远程过程调用是对信息传送基本模型的修改，允许不同机器上的程序使用简单的过程调用和返回方式进行交互对话机器上的程序使用简单的过程调用和返回方式进行交互对话 远程过程调用的一般结构远程过程调用的一般结构 命令格式命令格式 ：CALL P(xCALL P(x，y)y)P P是过程名字，是过程名字，x x为传送的变量，为传送的变量，y y是返回值参数是返回值参数 远程过程调用中涉及的几个设计问题远程过程调用中涉及的几个设计问题 参数传递问题参数传递问题 参数表示参数表示 客户机与服务器的结合客户机与服务器的结合8

17、.5 分布式进程通信q 确定分布式系统的全局状态确定分布式系统的全局状态 全局状态和分布式瞬态全局状态和分布式瞬态 在紧藕合系统中所有的并发问题，如互斥、死锁和饿死等，在紧藕合系统中所有的并发问题，如互斥、死锁和饿死等，在分布式系统中也会遇到在分布式系统中也会遇到 由于网络传输的延迟，分布式系统的性质带来的时间滞后由于网络传输的延迟，分布式系统的性质带来的时间滞后使得所有与并发有关的问题复杂化使得所有与并发有关的问题复杂化 所谓所谓全局状态全局状态是一致的，是指如果接收信息的进程已记录是一致的，是指如果接收信息的进程已记录它接收到了信息的状态，那么，在发送信息的进程状态中应记它接收到了信息的状

18、态，那么，在发送信息的进程状态中应记录它发送了那个信息录它发送了那个信息 所谓所谓分布式瞬态分布式瞬态是指每个进程有一组状态的收集是指每个进程有一组状态的收集 8.5 分布式进程通信 分布式瞬态算法分布式瞬态算法 所谓所谓分布式瞬态算法分布式瞬态算法是指记录一致性全局状态在分布式系是指记录一致性全局状态在分布式系统中采用的方法。该算法假定，信息应按照其发送的顺序传送，统中采用的方法。该算法假定，信息应按照其发送的顺序传送，并且在传输过程中没有被丢失并且在传输过程中没有被丢失 。算法用了一个专用的控制信息。算法用了一个专用的控制信息marker marker 进程进程p p接收到接收到Q Q的的

19、markermarker后，执行：后，执行：1 1，进程，进程P P记录下它的局记录下它的局部状态部状态SP 2SP 2，记录从，记录从Q Q到到P P进入（进入（incomingincoming）通道的状态）通道的状态 3 3，进程进程P P沿着所有向外发出的通道传播这个沿着所有向外发出的通道传播这个markermarker给它的所有邻接给它的所有邻接进程进程 8.5 分布式进程通信 在记录它的状态之后的任何时间，若在记录它的状态之后的任何时间，若P P接收了另一个进入接收了另一个进入通道（如来自进程通道（如来自进程R R）的）的markermarker时，它执行如下：时，它执行如下：进进程

20、程P P记记录录从从R R到到P P的的通通道道状状态态。这这个个状状态态是是作作为为P P记记录录它它的的局局部部状状态态SPSP，开开始始到到它它接接收收到到来来自自R R的的markermarker时时信信息息序序列列而而记记录的。录的。一旦沿着每个进入通道都已收到了一旦沿着每个进入通道都已收到了markermarker，这个算法就在，这个算法就在进程进程P P终止终止 8.5 分布式进程通信 进程同步主要是指彼此合作的进程在共享资源上协调其进程同步主要是指彼此合作的进程在共享资源上协调其操作顺序。进程互斥则主要是指彼此竞争的进程严格按照次操作顺序。进程互斥则主要是指彼此竞争的进程严格按

21、照次序（排它性的）使用资源。序（排它性的）使用资源。8-6-1 8-6-1 事件定序法事件定序法-同步和互斥的分布式算法的基本操作是事件的时间定序。同步和互斥的分布式算法的基本操作是事件的时间定序。由于缺乏一个公共的时钟或同步局部时钟的方法，可以由于缺乏一个公共的时钟或同步局部时钟的方法，可以用下面的方法进行表达。用下面的方法进行表达。-当说系统当说系统i i中的事件中的事件a a出现在系统出现在系统j j中的事件中的事件b b之前（或之之前（或之后）时，希望网络中所有系统都能得出这个一致性的结后）时，希望网络中所有系统都能得出这个一致性的结论。但不幸的是，这种陈述是不精确的。论。但不幸的是，

22、这种陈述是不精确的。8.6 分布式进程同步与互斥-首先一个事件的实际出现与某个其他系统观察到它的时首先一个事件的实际出现与某个其他系统观察到它的时间之间可能有一个延迟；其次由于缺少同步设施，可能间之间可能有一个延迟；其次由于缺少同步设施，可能在不同系统上读出的时钟值不同。在不同系统上读出的时钟值不同。-为了克服上述两个问题造成的影响，为了克服上述两个问题造成的影响，LamportLamport建议采用建议采用时标方法为分布式系统中的事件定序。这个技术被广泛时标方法为分布式系统中的事件定序。这个技术被广泛地用在解决同步和互斥的分布式算法中。地用在解决同步和互斥的分布式算法中。-时标模式用来为传输

23、的信息组成的事件定序。时标模式用来为传输的信息组成的事件定序。8.6 分布式进程同步与互斥图8-15 时标算法的执行情况8-6-2 8-6-2 分布式互斥分布式互斥 实施互斥的算法可以是集中式的，也可以是分布式的实施互斥的算法可以是集中式的，也可以是分布式的 集中式算法集中式算法-算法：一个节点作为控制节点，控制对所有共享目标算法：一个节点作为控制节点，控制对所有共享目标的存取。只有控制节点才能对资源分配进行决策；控制的存取。只有控制节点才能对资源分配进行决策；控制节点中集中了所有必要信息，包括所有资源的标识和位节点中集中了所有必要信息，包括所有资源的标识和位置，以及每个资源的分配状态置，以及

24、每个资源的分配状态 -优缺点：集中式互斥算法比较简单，容易实现，但如优缺点：集中式互斥算法比较简单，容易实现，但如果控制节点失败了，互斥机制就无法实现；每个资源的果控制节点失败了，互斥机制就无法实现；每个资源的分配和回收要求与控制节点交换信息，因此，控制节点分配和回收要求与控制节点交换信息，因此，控制节点可能变为瓶须可能变为瓶须8.6 分布式进程同步与互斥 分布式算法分布式算法特征：特征：-平均来讲，所有节点有着等量的信息平均来讲，所有节点有着等量的信息-每个节点只有整个系统的一部分描述，且必须基于这每个节点只有整个系统的一部分描述，且必须基于这个信息进行决策个信息进行决策-所有节点对于系统的

25、最后决策有着完全相等的作用所有节点对于系统的最后决策有着完全相等的作用 -一个节点失败了，一般不会导致整个系统崩溃一个节点失败了，一般不会导致整个系统崩溃-不存在系统范围的公共时钟来协调与时间有关的事件不存在系统范围的公共时钟来协调与时间有关的事件8.6 分布式进程同步与互斥8-6-3 8-6-3 分布式算法分布式算法 Lamport Lamport分布式算法分布式算法-数据结构：数据结构：qj=(Release,0,j)j=1,nqj=(Release,0,j)j=1,n-使用的三类信息：使用的三类信息：(Request,Ti,i)(Request,Ti,i)表示进程表示进程PiPi访问资源

26、的请求信息。访问资源的请求信息。(Reply,Tj,j)(Reply,Tj,j)表示在表示在PjPj的控制下允许访问资源的信息。的控制下允许访问资源的信息。(Release,Tk,k)(Release,Tk,k)表示进程表示进程PkPk释放先前分配给它的资源释放先前分配给它的资源 8.6 分布式进程同步与互斥-算法描述：算法描述：当当PiPi请求访问一个资源时，它泄放一个请求信息请求访问一个资源时，它泄放一个请求信息(Request,Ti,i)(Request,Ti,i)，时标，时标TiTi是本地时钟的当前值，它把这个信是本地时钟的当前值，它把这个信息放在它自己的数组项息放在它自己的数组项qi

27、qi中，并将这个信息发送给其它所中，并将这个信息发送给其它所有进程有进程 当当PjPj接接收收到到信信息息(Request,Ti,i)(Request,Ti,i)，时时，它它把把这这个个信信息息放放在在它它自自己己的的数数组组qjqj中中，并并发发送送信信息息(Reply,Tj,j)(Reply,Tj,j)给给其其它它所有进程所有进程8.6 分布式进程同步与互斥 当下面两个条件成立时，当下面两个条件成立时，PiPi可以访问一个资源：可以访问一个资源：在在数数组组q q中中，PiPi自自己己的的请请求求信信息息是是数数组组中中最最早早请请求求的的信信息息。由由于于信信息息在在所所有有节节点点的的

28、顺顺序序是是一一致致的的，这这个个规规则则允允许许一一个而且只有一个进程在任何时刻访问所请求的资源个而且只有一个进程在任何时刻访问所请求的资源 在本地数组中的所有其它信息比在本地数组中的所有其它信息比qiqi中的信息都晚一些。中的信息都晚一些。这保证这保证PiPi已了解了它的当前请求在所有请求之前已了解了它的当前请求在所有请求之前 进程进程PiPi释放资源时，它泄放信息释放资源时，它泄放信息(Release,Ti,i)(Release,Ti,i)，把，把它放在自己的数组中，并传送给其它所有进程它放在自己的数组中，并传送给其它所有进程 当当PiPi接收到信息接收到信息(Release,Tj,j)

29、(Release,Tj,j)时，它用这个信息置时，它用这个信息置换换qjqj的当前内容的当前内容 当当PiPi接收到接收到(Reply,Tj,j)(Reply,Tj,j)信息时，它用这个信息置换信息时，它用这个信息置换qjqj的当前内容的当前内容8.6 分布式进程同步与互斥 令牌传递法令牌传递法-令牌：令牌（令牌：令牌（tokentoken）是进程在任何时间持有的一个实）是进程在任何时间持有的一个实体，持有令牌的进程不必请求许可权就可以进入它的临体，持有令牌的进程不必请求许可权就可以进入它的临界区。当进程离开它的临界区时，再将令牌传递给另一界区。当进程离开它的临界区时，再将令牌传递给另一个进程

30、个进程-数据结构：这个算法需要两个数据结构。一个是被传数据结构：这个算法需要两个数据结构。一个是被传递的令牌，另一个是请求数组递的令牌，另一个是请求数组-算法描述算法描述8.6 分布式进程同步与互斥8.7 分布式进程死锁问题q 资源分配中的死锁资源分配中的死锁 在分布式系统中在分布式系统中,必须依据各节点的局部信息进行决策必须依据各节点的局部信息进行决策 死锁的预防死锁的预防 破坏环路等待条件破坏环路等待条件 破坏请求和保持条件破坏请求和保持条件 死锁的检测死锁的检测 系统是集中式的控制系统是集中式的控制：由于中心进程有一个完整的图形：由于中心进程有一个完整的图形描述，它负责死锁的检测。这个方

31、法需要很多的通信信息，而描述，它负责死锁的检测。这个方法需要很多的通信信息，而且，一旦中心节点故障，算法将不起作用。另外。可能检测到且，一旦中心节点故障，算法将不起作用。另外。可能检测到假死锁假死锁 8.7 分布式进程死锁问题 分层控制分层控制：所有节点组成一个树型结构，除叶节点外，：所有节点组成一个树型结构，除叶节点外，所有节点都要收集所有相关节点的有关资源分配的信息许在比所有节点都要收集所有相关节点的有关资源分配的信息许在比根节点低的各级上进行死锁检测根节点低的各级上进行死锁检测 分布式控制分布式控制：系统中的所有进程合作实现死锁的检测。：系统中的所有进程合作实现死锁的检测。为此，相互之间

32、必须交换相当多的时标信息。因此，系统开销为此，相互之间必须交换相当多的时标信息。因此，系统开销很大很大q 消息通信中的死锁消息通信中的死锁 相互等待相互等待 在消息通信中，当一组进程中的每个都正等待该组的另在消息通信中，当一组进程中的每个都正等待该组的另一个成员进程发送消息，而又没有消息正在传输时，死锁发生一个成员进程发送消息，而又没有消息正在传输时，死锁发生 集合集合S S中所有进程的死锁定义：中所有进程的死锁定义：1 1、集合、集合S S中的所有进程阻塞等待消息的到来。中的所有进程阻塞等待消息的到来。2 2、S S包含了集合包含了集合S S中所有进程的相关集。中所有进程的相关集。3 3、在

33、、在S S的各成员之间没有消息正在传递。的各成员之间没有消息正在传递。消息死锁和资源死锁的区别消息死锁和资源死锁的区别 破坏死锁方法：预防或检测破坏死锁方法：预防或检测 8.7 分布式进程死锁问题p经常不断地学习,你就什么都知道。你知道得越多,你就越有力量pStudy Constantly,And You Will Know Everything.The More You Know,The More Powerful You Will Be写在最后谢谢你的到来学习并没有结束，希望大家继续努力Learning Is Not Over.I Hope You Will Continue To Work Hard演讲人：XXXXXX 时 间：XX年XX月XX日