●●● ●●●● ●●●●● ●●●● 4.2分布式处理机分配算法 ●●0●● ●●●0 ●●●● 对于大多数用户来说,响应率比响应时间更重要。 其原因是: 考虑了大任务要比小任务花费更多时间这一情况。 ●例如: ●一个1秒的任务花了5秒,而一个1分钟的任务花 了70秒,从响应时间上看,前者好,但从响应率 上看,后者更好,因为5/1>70/60
4.2分布式处理机分配算法 对于大多数用户来说，响应率比响应时间更重要。 其原因是： 考虑了大任务要比小任务花费更多时间这一情况。 ⚫ 例如： ⚫ 一个1秒的任务花了5秒，而一个1分钟的任务花 了70秒，从响应时间上看，前者好，但从响应率 上看，后者更好，因为5/1>>70/60
●●● ●●●● ●●●●● ●●●● 4.2分布式处理机分配算法 ●●0●● ●●●0 考虑负载的分配方法: 局部和全局 局部负载分配处理单个处理器上的进程对时间片 (单元)的分配。全局负载分配首先进行进程对处 理器的分配,然后完成每个处理器内这些进程的局 部调度。 静态和动态(在全局类中) 静态负载分配中,进程对处理器的分配是在进程执 行以前的编译阶段完成的,而动态负载分配要到进 程在系统中执行时才做出分配。静态方法又叫做确 定性调度,而动态方法叫做负载平衡
4.2分布式处理机分配算法 考虑负载的分配方法： ⚫ 局部和全局 局部负载分配处理单个处理器上的进程对时间片 （单元）的分配。全局负载分配首先进行进程对处 理器的分配，然后完成每个处理器内这些进程的局 部调度。 ⚫ 静态和动态（在全局类中） 静态负载分配中，进程对处理器的分配是在进程执 行以前的编译阶段完成的，而动态负载分配要到进 程在系统中执行时才做出分配。静态方法又叫做确 定性调度，而动态方法叫做负载平衡
●●● ●●●● ●●●●● ●●●● 4.2分布式处理机分配算法 ●●0●● ●●●0 ●●●● ●最优和次优(在静态和动态两种类型中) 如果根据某种标准(例如,最小执行时间和最大系 统输出)可以取得最优分配,那么就可以认为这种 负载分配方法是最优的 般地,负载分配问题是№P完全问题。某些 情况下,次优方案(神经网络方法)也是可以接受 的。 ●有四类算法(对于最优的和次优的)被使用: 1)解空间枚举搜索、 2)图模型、 3)数学编程(例如0/1规划) 4)队列模型
4.2分布式处理机分配算法 ⚫ 最优和次优（在静态和动态两种类型中） 如果根据某种标准（例如，最小执行时间和最大系 统输出）可以取得最优分配，那么就可以认为这种 负载分配方法是最优的。 一般地，负载分配问题是NP完全问题。某些 情况下，次优方案（神经网络方法）也是可以接受 的。 ⚫ 有四类算法（对于最优的和次优的）被使用： 1）解空间枚举搜索、 2）图模型、 3）数学编程（例如0/1规划） 4）队列模型
●●● ●●●● ●●●●● ●●●● 4.2分布式处理机分配算法 ●●0●● ●●●0 ●●●● ●近似和启发式(在次优类型中) 在近似方法中,负载分配算法仅搜索一个解空 间的子集,当寻找到一个好的解时,终止执行 在启发式方法中,调度算法使用某些特殊参数, 能够近似地对真实系统建模
4.2分布式处理机分配算法 ⚫ 近似和启发式（在次优类型中） 在近似方法中，负载分配算法仅搜索一个解空 间的子集，当寻找到一个好的解时，终止执行 在启发式方法中，调度算法使用某些特殊参数， 能够近似地对真实系统建模
●●● ●●●● ●●●●● ●●●● 4.2分布式处理机分配算法 ●●0●● ●●●0 ●集中控制的和分散控制的(在动态类型中) 在分散控制中,分配决策工作被分配给不同的 处理器。在集中控制中,分配决策工作由一个处理 器完成 协作的和非协作的(对分散控制) 动态负载分配机制可以分成:协作的(分布式 对象间有协同操作)和非协作的(处理器独立做出 决策)
4.2分布式处理机分配算法 ⚫ 集中控制的和分散控制的（在动态类型中） 在分散控制中，分配决策工作被分配给不同的 处理器。在集中控制中，分配决策工作由一个处理 器完成。 ⚫ 协作的和非协作的（对分散控制） 动态负载分配机制可以分成：协作的（分布式 对象间有协同操作）和非协作的（处理器独立做出 决策）