操作系统——第十四课.ppt

第十四课　分布式进程管理 本课的主要问题 进程迁移问题 　1）迁移类型有哪些？ 　2）迁移的原因有哪些？ 　3）进程迁移机制是什么？ 　4）迁移协商是如何进行的？ 分布式全局状态与分布式瞬像是什么？ 分布式互斥问题？ 分布式死锁问题？ 14.1　进程迁移 分类 　1）数据迁移 　2）计算迁移 原因（动机） 　1）负载均分 　2）通信性能 　3）可用性 　4）特殊功能使用 进程迁移机制 进程迁移的启动 　1）以负载均衡为目标的系统，由监视系统负载的操作系统启动迁移模块 　2）以到达特定资源为目标的系统，由进程根据需要自我决定何时启动迁移 进程迁移内容 整体迁移： 　转移整个地址空间 预先复制： 　进程在复制自身到目标节点的同时仍在原点执行 仅迁移修改页： 　仅迁移在主存中修改了地址的页 基于引用的复制 　只有在引用某页时才迁移该页 刷新 　通过将“脏”页写回磁盘，通过磁盘访问进程 迁移中的消息处理 迁移过程中不接收消息 利用树型结构广播查询转发消息 设立原驻地代理转发消息 通过前指指针转发消息 设立邮箱转发消息 迁移协商 协商步骤书P460 14.2　分布式全局状态与瞬像 引入全局状态的原因 　一个简单例子（书P462　图14.3） 相关术语 　通道：两进程间消息传输的途径或方法 　状态：利用通道传递信息的进程附带的消息序列 　瞬像：从前一瞬像以来，经过通道的所有消息的记录 　全局状态：所有进程的组合状态 　分布式瞬像：一组进程的瞬像集合 14.3　分布式互斥 定义 　由于分布式中多个进程对临界资源的竞争所导致的在临界区内一次只允许一个进程执行的过程 分布式互斥应满足的条件 　同集中式数据处理的互斥条件 分布式互斥的解决 集中式算法 分布式算法 令牌环算法 集中式算法 基本思想：模拟单机系统，引入管理员对申请进入临界区的进程进行互斥操作 优点 　实现简单，保证了互斥 缺点 　它是集中式算法，管理员出错将导致系统失败 分布式算法 执行算法 　进程在要进入临界区前构造一条含临界区号、进程号和当前时间的消息并广播给其它进程 　一个进程收到请求后根据自身状态采取相应动作 　1）接收者不在临界区，也不想进入临界区，它回答OK 　2）接收者在临界区，它不回答，仅把请求加入等待队列 　3）接收者不在临界区，但想进入，它就比较自己申请的时间戳与消息的时间戳，如果消息的时间戳早，回答OK，否则将请求加入等待队列，不回答 基本思想 　一个进程进入临界区的惟一条件是它发出消息后能得到所有其它进程的回答，它退出临界区时，也会向所有其它进程发送OK消息 优点 　使用分布式算法，不存在管理员瓶颈 缺点 　必须知道所有进程，请求时间有明确的先后关系 令牌环算法 基本思想 　通过给每个进程指定一个序列号构成一个进程环，每个进程知道它前后进程的序列号，并给环中加一个令牌，令牌在环中传递，只有得到令牌的进程才能进入临界区 优点 　不会出现进程饿死 缺点 　令牌可能丢失，不易检测 14.4　分布式死锁 死锁的类型 　1）资源分配中的死锁 　2）消息通信中的死锁 死锁检测中的问题 　1）进程与资源的分布性 　2）时序的不确定性 　3）死锁的虚假性 　4）预防和解除死锁的多样性 资源分配中的死锁解决 死锁预防 　1）定义资源类型的线性顺序防止循环条件 　2）一次性分配给进程所有资源破坏持有等待条件 　3）“等待——死亡”算法与“死亡——等待”算法 死锁避免（不现实理由P476） 死锁检测 　1）中心式控制 　2）分布式控制 消息通信中的死锁解决 互斥等待 　一组进程中每个等待来自组中另一个成员的消息，利用资源死锁的预防与检测解决 消息缓冲区不可用性 　1）直接的存储转发死锁 　禁止所有缓冲区都用于某个单独链接 　2）间接的存储转发死锁 　使用结构化的缓冲池，按报文游历的步数保留在相应的级数，如一级填满，以后少于或等于该级的报文被丢弃 3）有限通道使用导致的死锁 　建立系统中每对进程间传递消息的上限来防止这种形式的死锁 * * 0 1 2 C 请求 OK 管理员 队列为空 0 1 2 C 管理员 请求 不回答 2 0 1 2 C 请求 OK 管理员 (a)进程1向管理员请求进入临界区得到许可 (b)进程2请求进入临界区,管理员不予回答 (c)进程1退出临界区,管理员向进程2发许可 0 1 2 0 1 2 0 1 2 8 8 12 12 OK OK OK 进入临界区 OK 进入临界区 分布式算法举例 (a)有两个进程要同时进入同一临界区 (b)进程0的时间戳较小，它进入 (c)进程0退出临界区，发送OK消息，进程2进入 0 2 4 9 7 1 6 5 8 3 网　络 6 7 8 9 0 1 2 3 4＊ 5 令牌持有者可进入临界区或传递令牌　 (a)网络上的无序进程