任务调度的并行算法

如果给定一批任务,比如有500个任务,需要在尽可能快的时间内做完。

如果串行是肯定不行的。我们可以考虑并行策略,但是开了并行,怎么能够充分利用资源比较好呢。

这个问题在多年前做数据迁移的时候,逼得没办法,当时用shell写了一个算法,可以参考这一篇。

海量数据迁移之使用shell启用多个动态并行(r2笔记81天)

但是在自动化运维平台中,我希望这个操作能够更加通用,所以在程序端实现是极好的。

我先打算用Java来实现,然后转义为Python版本,已经写了大半部分,还没有调试好,就先不放出来了,我把我的思路说一下。

假设有下面的一些任务,第一位是序号,第二位是任务需要花费的时间。

假设分为4个并行,即4组执行任务,每组执行任务该如何分配呢。

(1, 10),

(2, 30),

(3, 20),

(4, 50),

(5, 60),

(6, 30),

(7, 20),

(8, 10),

(9, 20),

(10,50),

所以放眼任务调度的方向上,我们都希望并行,但是绝大多数情况下,并行的效果其实不好,一种最重建的情况就是前半段在并行,后半段基本在等待。

假设我们按照如下的思路来完成,前四个元素是每组的一个元素,然后每组查看累计值的最小值,然后依次加入后续的元素。按照这种方法,得到的任务安排如下:

1 10 60 70

2 30 20 20 70

3 20 30 50 100

4 50 10 60

明显这种方法有缺点,因为我们无法预知后续元素的大小,所以任务分配很不均匀。

所以我们需要排序,按照最大值,最小值的方式排序。

这样一来,最大的4个元素分别位列每组的第一个元素。然后依次取得每组累计值的最小值,加入后续的元素。

分配情况如下:

1 50 20 70

2 60 20 80

3 50 20 10 80

4 30 30 10 70

明显好很多。

原文发布于微信公众号 - 杨建荣的学习笔记(jianrong-notes)

原文发表时间:2018-04-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Golang语言社区

游戏AI设计经验分享——行为树研究

http://bbs.gameres.com/thread_493700.html

29830
来自专栏Golang语言社区

游戏AI设计经验分享——行为树研究

http://bbs.gameres.com/thread_493700.html

19200
来自专栏码生

Swift2转Swift3

接触swift 已经有一年多的时间了,由最初的OC代码转为 swift 代码,然后从 swift 2.3 转为 swift 3。每次的转换都感觉是将项目整个的翻...

17750
来自专栏追不上乌龟的兔子

JupyterLab——更具生产力的Jupyter环境

Jupyter源于Ipython Notebook,是使用Python(也有R、Julia、Node等其他语言的内核)进行代码演示、数据分析、可视化、教学的很好...

15.3K40
来自专栏数据分析

[数据清洗]- Pandas 清洗“脏”数据(二)

概要 了解数据 分析数据问题 清洗数据 整合代码 了解数据 在处理任何数据之前,我们的第一任务是理解数据以及数据是干什么用的。我们尝试去理解数据的列/行、记录、...

38740
来自专栏用户2442861的专栏

浅谈UML的概念和模型之UML九种图

http://blog.csdn.net/jiuqiyuliang/article/details/8552956

11410
来自专栏阿凯的Excel

或关系模糊匹配求均值(pandas插播版7)

上期用Excel的复杂函数解决了或关系模糊匹配求均值。本期和大家分享一下如何使用Python的Pandas解决该问题。 郑重说明:本期只是分享解决方案,且pan...

52780
来自专栏吉浦迅科技

DAY39:阅读扩展数据类型

15520
来自专栏祝威廉

Bug剖析篇-"Facebook 60TB+级的Apache Spark应用案例"

Facebook 60TB+级的Apache Spark应用案例,本来上周就准备看的,而且要求自己不能手机看,要在电脑上细细的看。然而终究是各种忙拖到了昨天晚上...

10040
来自专栏CDA数据分析师

三行Python代码,让数据预处理速度提高2到6倍

Python 是机器学习领域内的首选编程语言,它易于使用,也有很多出色的库来帮助你更快处理数据。但当我们面临大量数据时,一些问题就会显现……

21540

扫码关注云+社区

领取腾讯云代金券