计算机操作系统-第9章分布式操作系统.pptVIP

9.3分布式系统的死锁 9.3.3 分布式死锁检测 1、集中式的死锁检测 尽管每台机器都有一幅资源图以描述自己所拥有的进程和资源，但仍旧会有一台中心机器拥有整个系统(所有资源图的集合)的资源图。当协调者检测到了环路时，它就中止一个进程以解决死锁。 书中的图9-5给出一个解决方法。尽管这种方法消除了假死锁，但是它需要全局时间，而且开销很大。另外，其他的一些消除假死锁的方法也很困难。 9.3分布式系统的死锁 9.3分布式系统的死锁 2、分布式的死锁检测 一个典型的算法，Ckandy-Misra-Haas算法(Chandy等，1983)。该算法允许进程—次请求多个资源(如锁)而不是一次一个。通过允许多个请求同时进行使得事务的增长阶段可观地加速。该模型的这种变化的结果使得一个进程可以同时等待两个或多个进程。 在图9-6中，我们给出了一种改进的资源图，图中只给出进程。每条弧穿过—个资源，但为简单起见将资源从图中删除了。 9.3分布式系统的死锁 9.3分布式系统的死锁 可以有不同的方法打破死锁。一种方法是使最初发送探测消息的进程自杀。然而如果有多个进程同时调用了此算法那就会出现问题。例如在图9-6中假设进程0到6同时阻塞，而且都初始化了探测消息。那么每个进程最终都会发现死锁，并且因此而自杀，然而这是不必要的。中止掉一个进程就足够了。 另一种算法是将每个进程的标识符添加到探测消息的末尾，这样当它返回到最初的发送者时完整的环路就可以列出来了。 9.3分布式系统的死锁 9.3.4 分布式死锁预防 死锁预防是由细致的系统设计构成的，因此死锁从结构上来说是不可能的。不同的技术包括在某一时刻只允许进程占有一个资源，要求进程在初始阶段请求所有资源，当进程请求新资源时必须先释放所有资源。 在拥有全局时间和原子事务的分布式系统中，另外两种实用的算法也是可能的。这两种算法都是基于在一个事务开始时给它分配一个全局时间戳的思想。 Lamport的算法有效地保证了时间戳是唯一的(通过使用进程号)。 9.3分布式系统的死锁 图(a)中，一个较老的进程想得到一个被新进程占用的资源。图(b)中，—个新进程想得到被较老进程占用的资源。一种情况应该允许进程等待，另一种情况应该中止进程。假设标记(a)为中止(b)为等待。这种算法称为等-死算法(wait-die)。 9.3分布式系统的死锁 图9-8中的情况，允许抢先的存在。图9-8(a)而不是图9-8(b)被标记为抢先，标记图9-8(b)为等待。这种算法称为伤-等算法(wound-wait) 9.4 分布式系统的负载分配 9.4.1 基本概念 负载 所谓负载是指处理机上的用户进程尚未完成的工作量。主要包括进程的计算开销和通信开销。在多处理机系统中，对节点机上系统资源的负载度量，称为负载指标。以向量形式表示的某一节点机的各项负载指标，称为负载向量，它描述的是某一节点机的负载情况。以矩阵形式表示的各节点机负载向量的集合，称为负载矩阵，用以描述整个系统的负载情况。 9.4 分布式系统的负载分配 负载向量 负载向量所描述的内容，是任务分配的依据，其定义必须准确、完备和有效。负载向量可以包括多种负载指标。大多数任务分配算法采用单个负载指标作为负载向量，其中选择节点机就绪队列长度的颇多。 负载分配 分布式系统提供了巨大的处理能力。然而，为了实现和充分利用这种能力，需要优良的资源分配方案。 负载分配是分布式系统的资源管理模块，它主要是合理和透明地在处理器之间重新分配系统负载，以达到系统的综合性能最优。 负载分配大致可分为静态和动态两类。 9.4 分布式系统的负载分配 任务划分 一个给定任务划分的粒度定义是任务分解中影响通信开销的所有单元的平均尺度。算法可以分成细粒度、中粒度和粗粒度。 如果数据单元(即粒度)小，这种算法就是细粒度。如果数据单元大，算法就是粗粒度介于细粒度和粗粒度之间的就是中粒度。粒度太大，就会降低并行度，因为潜在并行任务可能被划分进同一个任务而分配给一个处理器。粒度太小，进程切换和通信的开销就会增加。 任务划分的一个主要目标就是尽可能消除处理器间通信引起的开销。 9.4 分布式系统的负载分配 负载平衡 为了描述节点机上负载的轻重程度，我们使用负载阀值进行衡量。负载阀值是节点机负载的界限值，其下界为T1，上界为T2，且T1≤T2。我们有如下的定义。 轻载：当节点机的负载小于T1时，该节点机为轻载； 重载：当节点机的负载大于T2时，该节点机为重载； 适载：当节点机负载大于T1而小于T2时，该节点机为适载； 空载：当节点机负载为0时，该节点机为空载。 负载平衡：是指系统中的