自主望远镜调度算法探索

1、自主望远镜调度算法探索 李建 2011-11-12 贵阳Outline调度系统的作用影响望远镜调度的因素调度方法的分类“分配调度”方法评分因素及计算公式“分配调度”流程关于调度系统 调度系统是自主望远镜的重要部分 决定“自主化的程度” 观测任务安排；资源分配均衡 观测任务调度过程中，最小调度单元称为作业（job）影响望远镜调度的因素 外部因素 内部因素影响望远镜调度的因素 外因：观测时影响观测质量的客观因素 天气：雨、雪、雾、风 角度：纬度越高，穿过大气层的路径越小，大气层产生的散射和变形越小，观测结果最佳 月相 影响望远镜调度的因素 内因：影响作业队列顺序的内

2、部因素主要是“效率”和“政策” “效率”因素：优先处理天体目标在相同天区的观测任务，合并相似的观测任务，只执行一次观测计划，以减少望远镜的回转时间 “政策”因素：包括允许管理员绕过作业队列，并优先得到望远镜的观测响应调度方法的分类调度方法分类 四个不同的调度类型（ Thomas Granzer 2004）: 1)queue scheduling 队列调度 每个观测阶段为一个jobs清单，由robot顺序执行。 不可预知的延迟（如聚焦时间、快速定向时间、天气因素）就会使jobs丢失观测。 不能实时插入jobs，不能改写剩余的调度队列。调度方法分类 2）Critical Path Scheduli

3、ng 关键路径调度 这是一个尊重所有job依赖关系依赖关系的调度方式，确保最少的依赖的job先调度，多依赖的job后调度。天文观测很少有这样的依赖关系，很少使用这种方法，这不是一个合适的调度方法。3）Optimal Scheduling 优化调度 这种方法需要大量的计算，来建立一个合适的时间表，以创造一个最好的调度方式。但是，预先算好的调度表还是不能对不可预知的变化作出反应。调度方法分类 4）Dispatch Scheduling 分配调度 这种类型的调度器为每个作业（job）计算出一个分数（score），放在调度池（pool）中，每次选择分数最高的执行。 这种方法解决了不可预知的因素所带来的

4、影响，因为调度不是固定的。 然而，由于调度的不固定，预知robot下一步要做什么是很困难的。而且需要一个能够改变优先级的评分算法（scoring algorithm）。调度方法分类 Liverpool Telescope、STELLA、BRT项目采取了“分配调度”的方法 Hubble telescope 由于有一个更好的可以预见的环境，使用了“优化调度”的方法 改进的调度方式： 环状队列，双队列，多种调度方式结合关于“分配调度”方式分配调度程序需求 分配调度程序应满足以下要求： 所有等待处理的job，必须进行每隔几分钟进行评估、定分 每个job必须结合多种因素（factor）的评价、计算出唯一

5、的一个分数 因素有加权值，反应因素的重要程度。允许管理员控制每个因素的加权值 软件以模块化的方式来编写，这样在新增因素、删除旧的因素时scheduler能及时响应分配调度程序需求 当robot要求job时，scheduler不能有延迟 -job必须立刻准备好 在调度池内，设置为immediate标志的job，必须优先考虑分配望远镜时间，不论其分数有多少 scheduler应该准许手动模式加入特殊事件，系统管理员将分配job的观测时间。需要进行评分的因素（Score Factors） Score Factors 一些被确定为影响job的总体评分的因素： job目标达到天空中最高点的时刻 job目

6、标落入地平的时刻 job间的相对距离（是否可以和其它观测任务合并） job预先设置的优先级值 job要求的观测时间 job一直在等待观测的时间量Score Factor的计算公式Score Factor的计算公式Window merit(观测窗口因素值)一个计算score的示例布尔测试 对一个job执行scheduling算法以前，可以执行一系列布尔测试，可以减少计算时间 计算出目标的高度和方位角，是否满足？ Job是否过了观测时间？ 目标是否符合相机的操作范围？ 是否以正常（非特殊事件）的模式工作？分配调度流程示例上一次观测上一次观测任务完成任务完成从从request pool提提取一条任务请求取一条任务请求通过通过bool测试？测试？NY第第1个评个评分模块分模块第第2个评个评分模块分模块第第N个评个评分模块分模块分数加权求分数加权求和和完成所完成所有请求？有请求？选取最高分选取最高分的任务执行的任务执行NYScheduler小结 考虑到上述所有因素，调度过程是一项复杂的任务。完全考虑到所有的因素，和它们之间的冲突是不实际的； Scheduler是保证资源公平的分配一个最优化的解决方案； 是各方面因素的妥协的结果。 普