●●● ●●●● ●●●●● ●●●● 4.2分布式处理机分配算法 ●●0●● ●●●0 ●●●● ●可预测系统ⅴs不可预测系统 在可预测系统中,可以通过合理的近似来事先得 到所有进程的信息。例如,在银行业、保险业、 民航定票系统中,每天的情况都基本相似,民航 根据经验可以预测到早春第一周周一的清晨大约 有多少人要从纽约去芝加哥,这样就保证了确定 式算法的可行性。 ●与可预测系统相反,有些系统的负载是完全无法 预测的。用户所做的工作每一个小时,甚至每 分钟都在动态地改变。在这种系统中的处理机分 配不能用一种在数学上确定的算法实现,而需要
4.2分布式处理机分配算法 ⚫ 可预测系统 vs 不可预测系统 ⚫ 在可预测系统中，可以通过合理的近似来事先得 到所有进程的信息。例如，在银行业、保险业、 民航定票系统中，每天的情况都基本相似，民航 根据经验可以预测到早春第一周周一的清晨大约 有多少人要从纽约去芝加哥，这样就保证了确定 式算法的可行性。 ⚫ 与可预测系统相反，有些系统的负载是完全无法 预测的。用户所做的工作每一个小时，甚至每一 分钟都在动态地改变。在这种系统中的处理机分 配不能用一种在数学上确定的算法实现，而需要
●●● ●●●● ●●●●● ●●●● 4.2分布式处理机分配算法 ●●0●● ●●●● ●●●● 使用一种称之为启发式的算法。 ●集中式算法需要将系统中所有的信息都收集到某个机 器上,这会造成系统不够鲁棒,并且该机器负载过于 沉重。因此,一般都采用分布式算法来实现处理机分 配。然而,一些集中式算法仍然被采用,原因是没有 相应的分布式算法来取代它
4.2分布式处理机分配算法 使用一种称之为启发式的算法。 ⚫ 集中式算法需要将系统中所有的信息都收集到某个机 器上，这会造成系统不够鲁棒，并且该机器负载过于 沉重。因此，一般都采用分布式算法来实现处理机分 配。然而，一些集中式算法仍然被采用，原因是没有 相应的分布式算法来取代它
●●● ●●●● ●●●●● ●●●● 4.2分布式处理机分配算法 ●●0●● ●●●0 第三个设计问题与前两个问题有关,是获得一个最优 解?还是一个可行的次优解? 般来说,采用集中式和分布式算法都能够得到最 优解,但得到最优解所花费的代价要比得到次优解 复杂得多。 ●此外,最优解需要收集更多的信息以及进行全面复 杂的处理。 ●对于大多数分布式系统来说,只要有一个启发、分 布、次优的处理机分配算法就可以了。因为,要获 得最优解实在是太难了
4.2分布式处理机分配算法 第三个设计问题与前两个问题有关，是获得一个最优 解？还是一个可行的次优解？ ⚫ 一般来说，采用集中式和分布式算法都能够得到最 优解，但得到最优解所花费的代价要比得到次优解 复杂得多。 ⚫ 此外，最优解需要收集更多的信息以及进行全面复 杂的处理。 ⚫ 对于大多数分布式系统来说，只要有一个启发、分 布、次优的处理机分配算法就可以了。因为，要获 得最优解实在是太难了
●●● ●●●● ●●●●● ●●●● 4.2分布式处理机分配算法 ●●0●● ●●●0 第四个设计问题与迁移策略有关: ●当一个新进程被创建时,系统需要决定它是否在仓 建它的机器上运行。若该机器繁忙,那这个新进程 就必须迁移到其它机器上去运行。 对于是根据本机局部信息还是全局信息来决定新进 程是否迁移,目前存在着两种学派 1)一种学派主张简单的局部算法:若机器的负 载低于某个阀值,那新进程就在本地机器上运行; 否则,就不允许该进程在本地上运行 2)另一种学派认为局部算法太武断了。最好在 决定新进程是否在本地机器上执行之前,先收集
4.2分布式处理机分配算法 第四个设计问题与迁移策略有关： ⚫ 当一个新进程被创建时，系统需要决定它是否在创 建它的机器上运行。若该机器繁忙，那这个新进程 就必须迁移到其它机器上去运行。 ⚫ 对于是根据本机局部信息还是全局信息来决定新进 程是否迁移，目前存在着两种学派。 1）一种学派主张简单的局部算法：若机器的负 载低于某个阀值，那新进程就在本地机器上运行； 否则，就不允许该进程在本地上运行。 2）另一种学派认为局部算法太武断了。最好在 决定新进程是否在本地机器上执行之前，先收集
●●● ●●●● ●●●●● ●●●● 4.2分布式处理机分配算法 ●●0●● ●●●● ●●●● 其它一些机器上的负载信息 比较: 局部算法简单,但远远达不到最优; 而全局算法需要付出巨大的代价来换取一个性能稍 微好一点的结果
4.2分布式处理机分配算法 其它一些机器上的负载信息。 ⚫ 比较： 局部算法简单，但远远达不到最优； 而全局算法需要付出巨大的代价来换取一个性能稍 微好一点的结果