我正在寻找适合以下问题的算法:
有多台计算机(确切数字未知)。每台计算机从某个中心队列中提取作业,完成作业,然后提取下一个作业。作业是由某些用户组生成的。有些用户提交了很多作业,有些提交了一点。作业消耗的cpu时间相等(不是真的,只是近似值)。
调度作业时,中心队列应该是公平的。而且,提交了大量作业的用户应该拥有最少的资源共享。
我正在为这个计划寻找一个好的算法。
考虑了两位候选人:
类似hadoop的公平调度程序。这里的问题是:当集群大小未知时,在哪里可以获得最小的共享?
与每个用户关联一些惩罚。计划用户作业时增加惩罚。使用将作业调度给用户的概率作为 1 - (normalized penalty)
. 这有点像步幅安排,但我找不到任何好的解释。
2条答案
按热度按时间js4nwp541#
您可以尝试使用自适应计算的torque资源管理和maui批处理作业调度软件。毛伊岛的政策足够灵活,以满足您的需要。它支持回填、可配置的作业和用户优先级以及资源预留。
mzsu5hc02#
当我实现一个非常类似的job runner(对于生产系统)时,我让每个服务器随机选择jobtypes。这是我的推理--
一个用户的作业过多不应影响其他用户运行作业的机会(用户公平性)
一个作业类型的过剩不应影响其他作业类型运行的机会(用户作业和作业公平性)
如果一个用户只有一个jobtype等待运行,那么所有服务器都应该运行这些作业(没有浪费容量)
系统应该“公平”地运行作业,即与等待用户和作业类型的数量成比例,而不是与总等待作业成比例(一个作业类型的大容量不应导致调度有利于它)(作业类型公平)
服务器的数量可能会有所不同,而且事先不知道
调度程序知道等待的作业、作业类型和用户元数据,但不知道作业数据(即用户名、作业名称和计数,但不知道有效负载)
我还希望每个服务器都是独立的,可以自主地安排自己的工作,而不必知道其他服务器的情况
我确定的解决方案是通过{user,jobtype}属性元组跟踪等待的作业,并让每个调度步骤随机选择5个元组,然后从每个元组中最多运行10个作业。选定的作业已入围,将由下一个可用的运行程序运行。每当释放容量以运行更多作业时(因为作业已完成或由于无法运行的次要限制),都会运行另一个调度步骤以获取更多的工作。
工作被原子锁定作为被获取的一部分;这些锁阻止它们再次被获取或参与进一步的调度决策。如果它们无法运行,它们将被解锁,从而有效地将它们返回到池中。锁超时,因此运行它们的服务器负责保持锁的刷新(如果服务器崩溃,其他服务器将超时其锁,并将拿起并运行它启动但未完成的作业)
在我的用例中,我希望具有作业a.1、a.2、a.3和b.1的用户a和b各获得25%的资源(尽管这意味着用户a获得75%的资源,而用户b获得25%)。在四个元组中随机选择,概率收敛到25%。
如果您希望用户a和b的资源各占一半,并且a的a.1、a.2和a.3与b的b.1的份额相等,则可以运行两级调度程序,随机选择用户并从这些用户中选择作业。这将在用户之间平均分配资源,在每个用户的作业中在作业类型之间平均分配资源。
大量特定工作类型的工作需要很长时间才能全部完成,但情况总是这样。通过跨用户和作业类型进行选择,作业处理的响应性不会受到不利影响。
有很多次要的限制,可以添加(例如,不超过5个电话每秒到linkedin),但以上是系统的核心。