ToB企服应用市场:ToB评测及商务社交产业平台

标题: Max-Min算法 [打印本页]

作者: 自由的羽毛 时间: 2024-6-11 13:28
标题: Max-Min算法
任务调度算法，随着多核处理惩罚器的发展，带来了新的挑战。如何使用高效的任务调度策略使得多核处理惩罚器充分发挥性能，是急需解决的问题。动态任务调度是根据运行时的情况动态的将任务分配到对应的资源上，但是须要实时的收集体系计算资源、存储资源以及网络资源等信息，有一定的体系开销，不外相较于资源使用率的提拔，动态资源调度也是很故意义的。
经典的调度算法有：Min-Min调度算法、Max-Min调度算法、MCT最小完成时间、MET最小执行时间等算法。由于Max-Min算法来自于Min-Min算法，因此先介绍Min-Min算法，再介绍Max-Min算法。
Min-Min算法

Min-Min算法是一个传统的任务调度算法，焦点头脑是以最快的时间举行任务分配和处理惩罚，时间是唯一思量的权重。将任务调度随处理惩罚时间最短的资源上，包管任务完成时间最短。Min-Min算法是网格计算中紧张的任务调度策略之一。Min-Min算法紧张头脑如下：
假设网格情况是由 n个任务 T={T1，T2，…，Tn}和 m个资源 R={R1，R2，…，Rm}组成。当任务聚集不为空时，通过执行以下流程来使得任务聚集为空

对于任务聚集中的任意一个任务Ti，计算调度到所有资源R中的任务最小完成时间。假设在第k（k <= m)个资源上任务能最早完成，那么最小完成时间就是minTime = MCT(i, k)。就得到一个含有n个元素的以为数组minTime。
假设第i个元素是minTime数组中最小的，对应的资源为h，那么就把任务Ti分配到资源h上去。
从任务聚集中把任务Ti删除，再返回第1步。
任务调度聚集为空时，就竣事调度程序。

Min-Min算法存在一个很大的缺点，就是算法总是优先分配小任务、最快完成时间的任务，而忽略了网格资源的负载平衡，网格处于一个异构的情况中时，呆板的处理惩罚本领有大概会主导任务的调度策略，换句话说如果一个计算节点的计算本领凌驾其他所有节点，那么任务就会堆砌到这一个计算节点上，导致资源使用率低下。另外一个方面，由于对于每个任务都须要计算在对应资源下的完成时间，因此会有不小的体系开销，大量任务到来的情况下调度的时延大概会很长。
Max-Min算法

Max-Min算法与Min-Min算法很类似，只是将上述Min-Min算法流程中的选择minTime数组中最小的值改为选择最大的值，将在minTime数组中选择最大的值，比如说最大值对应的是maxTime = MCT(i, k)，就将任务i分配给资源k。
Max—Min算法的目的是为了最小化由于执行须要长执行时间的任务而导致的部分资源负载过大而部分资源空闲的非常负载不平衡的结果。因此在元任务是由许多短任务和少数长任务组成的情况下。Max—Min调度算法可以做到相对来说负载平衡。但是Max-Min算法也会造成完成时间较小的任务等候时间过长的问题，影响作业执行的服从，也有大概导致负载不平衡。
最大最小算法定义如下：

资源按照需求递增的顺序举行分配
不存在用户得到的资源凌驾自己的需求
未得到满意的用户等价的分享资源

思量用户聚集 1， …， n，分别有资源需求 x1，x2，…，xn。不失一般性，令资源需求满意 x1 <= x2 <= … <= xn。令服务用具有本领 C。那么，初始把 C/n 资源给需求最小的用户，这大概会凌驾用户 1 的需求，继承处理惩罚。该过程竣事时，每个用户得到的没有比自己要求更多，而且，如果其需求得不到满意，得到的资源也不会比其他用户得到的最多的资源还少。我们之所以称之为最大最小公平分配是由于我们最大化了资源得不到满意的用户最小分配的资源。
一个通俗的例子：有一四个用户的聚集，资源需求分别是 2，2.6，4，5，其资源总本领为 10，为其计算最大最小公平分配。
解决方法：通过几轮的计算来计算最大最小公平分配。第一轮，我们暂时将资源划分成 4 个巨细为 2.5 的。由于这凌驾了用户 1 的需求，这使得剩了 0.5 个均匀的分配给剩下的 3 个人资源，给予他们每个 2.66。这又凌驾了用户 2 的需求，所以拥有额外的 0.066… 来分配给剩下的两个用户，给予每个用户 2.5 + 0.66 … + 0.033… = 2.7。因此公平分配是：用户 1 得到 2，用户 2 得到 2.6，用户 3 和用户 4 每个都得到 2.7。
基于权重的Max-Min算法

上述假设是基于所有效户具有相同的权限来获取资源，偶尔间须要给一些用户更大的配额。比方，大概会给不同的用户 1, …, n 关联权重 w1, w2, …, wn，这反映了他们间的资源配额。通过定义带权的最大最小公平分配来扩展最大最小公平分配的概念以使其包含这样的权重：

资源按照需求递增的顺序举行分配，通过权重来举行尺度化
不存在用户得到凌驾自己需求的资源
未得到满意的用户按照权重均分获取资源

一个通俗的例子：有一四个用户的聚集，资源需求分别是 4，2，10，4，权重分别是 2.5，4，0.5，1，资源总本领是 16，为其计算最大最小公平分配。
解决办法 第一步是尺度化权重，将最小的权重设置为 1。这样权重聚集更新为 5，8，1，2。这样就假装须要的资源不是 4 份而是 5 + 8 + 1 + 2 = 16 份。因此将资源划分成 16 份。在资源分配的每一轮，按照权重的比例来划分资源，因此，在第一轮，计算C/n为16/16 = 1。在这一轮，用户分别得到 5，8，1，2单元的资源，用户1得到了 5 个资源，但是只须要 4，所以多了 1 个资源，同样的，用户 2 多了 6 个资源。用户 3 和用户 4 拖欠了，由于他们的配额低于需求。如今有 7 个单元的资源可以分配给用户 3 和用户 4。他们的权重分别是 1 和 2，最小的权重是 1，因此不须要对权重举行尺度化。给予用户 3 额外的 7 × 1/3 单元资源和用户 4 额外的 7 × 2/3 单元。这会导致用户 4 的配额达到了 2 + 7 × 2/3 = 6.666，凌驾了需求。所以将额外的 2.666 单元给用户 3，终极得到 1 + 7/3 + 2.666 = 6 单元。终极的分配是 4，2，6，4，这就是带权的最大最小公平分配。
参考：https://oldtang.com/109.html

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)