6

我正在编写一个 python 应用程序，它使用 OpenStack 为学生提供对有限数量的虚拟机的访问。

学生可以现在或将来进行预订。

我需要将随时安排的虚拟机数量限制为 X，同时在插槽/预留可用的情况下仍允许学生预留 vm。

保留对象如下所示（sqlalchemy）。我会知道所请求的预订的开始时间和时长，此时我需要检查现有的预订，看看在所请求的时间段内是否有太多的预订。*_job 字段是 APScheduler 作业的名称。

class Reservation(Entity):
    student = ManyToOne('Student', required=True)
    class_id = ManyToOne('Class', required=True)
    image = ManyToOne('Image', required=True)
    # openstack image id filled in once the instance is started
    instance_id = Field(UnicodeText)

    # apscheduler jobs
    stop_instance_job = Field(UnicodeText)
    start_instance_job = Field(UnicodeText)
    warn_reservation_ending_job = Field(UnicodeText)
    check_instance_job = Field(UnicodeText)

关于在哪里寻找调度算法或类似的例子的任何指针？我什至不清楚要搜索什么...

谢谢。

4

1 回答 1

2

您应该查找基于网格的调度程序。通常调度程序不知道真正的执行时间（或资源使用时间），并且使用复杂的启发式方法来猜测问题需要多长时间（请参阅网格调度程序上的此类启发式方法，网址为：PDF 下载 描述基于网格的调度）。使用基本网格来表示一段时间内的工作负载的更简单方法很可能满足您的需求。Python 没有我所知道的任何很棒的网格对象库（虽然我之前在 C++ 和 Python 中实现了一些，但它们并不太难）。您应该查看 numpy 包，以便更轻松地解释多维对象——它可以很容易地模拟或实现网格。

Msw 提到了 Dijkstra 的银行家算法，这是一种作业调度形式 - 但是您的问题更关心未来状态而不是当前状态，并且您可以准确预测（知道真正的价值）任务时间。因此，您在注册作业时填写的 T（时间步长）乘 N（资源数量 - 可能只是 1）乘 M（最大资源保留）网格就足够了。确定是否可以在特定时隙中安排特定作业是 O(task_length * M) 检查网格的子部分 (start, stop)x(required_resources)x(1,M) 是否有空时隙。

为特定工作（选择开始时间）找到合适的位置是一项更困难的任务，可以通过修改后的 Dijkstra 算法或任何标准调度程序来实现（msw 的评论对于此任务比对时间段能力检查更有帮助） . 请注意，许多在线调度程序内容是特定于操作系统进程调度的，它更关心操作类型（I/O 与否）以及花费比预期更长的时间而不是抽象资源使用的惩罚。因此，谷歌搜索调度程序通常会为您提供 Linux 调度程序实现，而不是针对任意数据的技术。尝试查找最短作业调度程序，当解释时，这些调度程序通常更简单且对操作系统任务的依赖程度更低。

于 2012-08-01T18:05:28.757 回答