DCS资源管理ppt课件.ppt

分布并行处理技术 资源管理 资源管理 资源共享途径资源管理死锁 分布式系统中的资源共享途径 数据迁移 将数据取来用设结点A的用户向结点B存取数据 有两种实现办法 将整个文件传给A 用过后再回传给B 将文件中的实际需要部分传给A 用过后将修改部分传给B 讨论 两种办法各有自己的优势 这些优势与各种因素相关 与文件的大小及其所需要的数据所占的比例有关 与对此文件的访问次数有关 数据的一致性保证问题 异构数据之间数据格式的互换 分布式系统中的资源共享途径 计算迁移 将计算委托给对方RPC 串行消息 由相关节点的OS创建一个新的计算进程 完成相应的计算 并行 问题 存在连续迁移问题 系统需要有一定的机制加以解决 分布式系统中的资源共享途径 作业迁移 负载平衡大作业可以被分成若干个子作业 在不同场点上执行它的某一部分原因 负载平衡 作业 或子作业 可以分散到系统中以均衡系统的工作负载 提高计算速度 对特定 软 硬件 资源的需要 方法 显式 用户提出迁移地 系统执行隐式 系统决定 用户不管 分布式系统中的资源共享途径 进程迁移 资源管理 从单个资源与多个管理者的相互关系来考虑集中管理 专制 Autocratic 管理 单一管理者功能分布 分割 Partitioned 管理 权力划分 分工 学校各部门的分工 浮动 轮流 Successive 管理 轮流分散 民主 Democratic 管理 协调管理 资源管理 从多个资源与多个管理者的相互关系来考虑分管 每个资源属于一个管理者独立管理合管 每个资源由所有管理者共同管理部分合管 每个资源由若干管理者共同管理 资源管理 局部集中管理思想 资源按其分布由所在的结点集中管理 进程需要资源时向所在结点申请 本结点不能满足时 由系统向其它结点申请 适应对象 内存 键盘 显示器 属于各结点 逻辑上较独立 并发问题 按临界区处理 读者 写者 问题 读者优先 除非写者占有资源 否则可读 写者优先 一旦写者占有资源 读者等待 资源管理 分散式管理思想 一个资源由多个管理者协商管理 对一个资源的使用必须经过所有管理者同意 适应对象 具有多个副本的文件的读写 问题 管理复杂 通信开销大 资源管理 分级管理思想 对资源进行分类 一类用局部集中式管理 仅被本场地使用的资源 另一类用分散式管理 被多个场地使用的资源 问题 需要两套管理机制 分散式资源管理算法 算法思想 按照FCFS的策略协调控制对资源的使用 本算法与上一章介绍的改进的Lamport算法类似 用一个全局时间戳来对申请进行定序 算法描述 p申请资源r 向各个进程发消息Request T p r 并将它放入自己的申请队列 其中T为时间戳 其它进程q收到Request T p r 后 将其放入申请队列 若q当前未申请该资源 则立即给p发一个带时间戳的Reply 如果q也正在使用或者申请此资源 且时间戳先于T 则暂时不发Reply 分散式资源管理算法 算法描述 当下列条件成立时 p才可以获得申请的资源r在自己的申请队列中 Request T p r 中的T是最小的 p已经收到所有其它进程的同意答复 释放资源p从自己的申请队列中删除Request T p r 给所有的等待者发Release T p r 和带有时间戳的Reply q收到Release后 将Request T p r 从申请队列中删除 分散式资源管理算法 讨论 为什么每个进程都要维持一个申请队列 思想向分布式系统中问题求解的转化当进程p申请的是本地资源时 是否还需要执行上述过程 如何考虑进程优先级对申请资源的影响 招标算法 算法思想资源申请者按照招标的方式向系统中各个结点招标 各结点按照自己的情况投标 申请者评标 并选出中标者 算法描述资源申请者向其它所有结点广播招标消息 资源管理者接到消息后 若自己有此资源 则根据一定的方法算出的 标数 并向招标者投标 否则 发拒绝消息 申请者收到所有投标信后 根据一定的策略 选中标者 并直接向它发申请资源消息 中标者接到申请后 将其置入申请队列 并在可以分配所指资源时通知申请者 申请者使用完后 通知提供者收回资源 招标算法 讨论完成一次资源获得 正常情况下 共发2 n 1 2 2n条消息 该算法适应于便于广播消息的系统 如全互联 总线型系统 如果是共享通路结构的DCS 需要多少消息 标数x可以用下式进行计算 x c1a c2b其中a为目前待处理的申请的个数 b为招 投标双方的距离 c1 c2为常数系数 显然 标数越小 优势越大 只要发一封广播消息 共需1 n 1 2 n 2 招标算法 改进的算法描述资源申请者向其它所有结点广播招标消息 资源管理者接到消息后 若自己有此资源 则算出自己的 标数 并向招标者投标 否则 不发消息 申请者收到所有投标或者等待时间超过预定值T后 根据一定策略 选中标者 并直接向它发申请资源消息 中标者接到申请后 将其置入申请队列 并在可以分配所指资源时通知申请者 申请者使用完后 通知提供者收回资源 若申请者在发出申请后超时未获资源 则再向中标者发询问消息 若中标者无故障 则立即回复 若无回复消息 则重新广播招标消息 招标算法 讨论完成一次资源使用 共发 n 1 r 2 n r 2条消息 其中r是具有所申请资源的结点的个数 能否将规则1改为只向具有资源的r个结点发招标信 不能 局部知识 环形结构系统的招标算法 算法思想不是广播招标消息 而是沿着环传递此消息 在传递过程中 对投标者进行比较 并使消息中永远只含有当前最优投标者的描述 当此消息传回到发出者时 消息中给出的就是中标者 环形结构系统的招标算法 算法描述申请者向左 右 邻发招标消息 结点收到招标消息后 若本结点无此资源 则将消息下传 否则若此消息中没有投标内容 则将自己的投标内容加上 然后将消息下传 若此消息中有投标内容 则将自己的投标内容与之相比 优选其优者写在消息中 然后将消息下传 当申请者收到自己发出的招标消息后 从中获取中标者信息 并向他发出正式申请 中标者将申请消息放入等待队列 并在实际分配时给申请者一个回复 当资源使用完后 通知提供者收回资源 对于非环形的分布式系统 必须建立逻辑环结构 如何建 考虑哪些因素 死锁 单机系统中的死锁处理算法作适当修改后 可以用于分布式系统 如资源定序 拟一次申请 Banker等 若把死锁定义为一组相互通信或竞争资源的进程的依赖时间的永久阻塞状态 则隐含分布式死锁有两类 通信死锁p1试图给试图p2发消息 p2试图给p3发消息 p3试图给p1发消息 此时大家都无法得到适当的缓冲区 信道 或者都在等待对方回答而无法回答对方 资源死锁同单机 死锁模型 资源分配图G V E V P R 进程集合P p1 p2 pn 资源集合R r1 r2 rm 请求边 p r E p申请资源r 分配边 r p E r资源 的一个实例 由p占有 当请求边 p r 被满足后 该请求边马上就变成一条分配边 r p 死锁模型 进程等待图对资源分配图进行化简 取G P E 如果存在r p r r q E 则 p q E 此图称为进程等待图 一资源模型AND模型OR模型AND OR模型不受限模型 死锁处理 处理死锁问题的策略有很多种 其中最著名的四种策略是 鸵鸟算法 忽略问题 检测 允许死锁发生 在检测到后想办法恢复 预防 静态地使死锁在结构上是不可能发生的 避免 通过仔细地分配资源以避免死锁 死锁预防 Coffman1971年给出发生死锁的4个条件 1 互斥条件每个资源或者分配给一个进程 或者空闲 即 每个资源同一时刻只能被一个进程占有 2 保持与等待条件拥有资源的进程可以申请新的资源 3 非剥夺条件只可自愿释放 不可强行剥夺 4 循环等待条件系统中至少有一条构成循环的资源链 死锁预防 1 死锁预测法2 定序 全序 1 每个进程给定一个唯一的优先数 给每个进程赋予一个唯一的优先数 这个优先数被用于决定一个进程Pi是否等待另外一个进程Pj 例如 如果Pi具有比Pj更高的优先权 Pi可以等待Pj 否则PiRollback 问题 饥饿现象 优先级低者总被撤销 不一定导致死锁者也可能被撤销 2 每个进程给定一个全局时标 以全局时标为进程的优先数 随着运行时间的增加 进程的优先级不断提高 死锁预防 1 wait die方法 非抢占年老的等待年轻的 当一个进程Pi申请当前已由Pj占有的资源时 仅当Pi的时间戳小于Pj的时间戳 即Pi比Pj年长 时 让Pi等待 否则Pi回退 例如 设进程P1 P2 P3分别具有邮戳时间3 9和12 如果P1要求P2占用的资源 则P1等待 如果P3要求P2占用的资源 则P3回退 死锁预防 2 wound wait方法 抢占年老的剥夺年轻的占有的资源 当一个进程Pi申请当前已由Pj占有的资源时 如果Pi的时间戳大于Pj的时间戳 即Pi比Pj年轻 时 让Pi等待 否则Pj回退 例如 设进程P1 P2 P3分别具有邮戳时间3 9和12 如果P1要求P2所占用的资源 则将剥夺P2的资源给P1 P2回退 如果P3要求P2占用的资源 则P3等待 死锁预防 wait die方法与wound wait方法的比较 p p 申请q占有的资源 死锁的检测方法 基本假设 进程在整个系统内统一命名每个结点有一个局部等待图 Gk Vk Ek p q Ek p申请q占有结点k的资源 如果局部等待图中有环 则有死锁 所有的局部等待图的并有环是系统死锁的充要条件 集中式死锁检测算法 由一个专门的协调进程通过一个全局图来测试是否有死锁存在 这个全局图可以由2种方法来形成 各结点维持一个局部等待图 协调者维持一个全局等待图 需要 时更新 各结点维持一个局部等待图 仅在 需要 时由协调者根据这些局部等待图生成全局等待图 可能需要删除重复的边 需要 可有如下几种情况 当局部等待图变化时 周期性地 当协调者需要检测死锁时 集中式死锁检测算法 这个方法有时也可能造成不必要的撤离 某一条边被撤销后 系统又增加了一条边 由于消息的到达顺序可能与发送顺序不同而使检测者检测出实际不存在的环 在死锁期间 某一个进程因其它原因被撤销 导致死锁实际上已经不存在 层次式死锁检测算法 层次式死锁检测算法 每个结点管理自己的局部等待图 其中一部分结点被指定为控制者 这些控制者构成