资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,自主望远镜调度算法探索,李建,lijianlamost.org,2011-11-12,贵阳,Outline,调度系统的作用,影响望远镜调度的因素,调度方法的分类,“分配调度”方法,评分因素及计算公式,“分配调度”流程,关于调度系统,调度系统是自主望远镜的重要部分,决定“自主化的程度”,观测任务安排；资源分配均衡,观测任务调度过程中，最小调度单元称为作业（,job,）,影响望远镜调度的因素,外部因素,内部因素,影响望远镜调度的因素,外因：观测时影响观测质量的客观因素,天气：雨、雪、雾、风,角度：纬度越高，穿过大气层的路径越小，大气层产生的散射和变形越小，观测结果最佳,月相,影响望远镜调度的因素,内因：影响作业队列顺序的内部因素主要是“效率”和“政策”,“效率”因素：优先处理天体目标在相同天区的观测任务，合并相似的观测任务，只执行一次观测计划，以减少望远镜的回转时间,“政策”因素：包括允许管理员绕过作业队列，并优先得到望远镜的观测响应,调度方法的分类,调度方法分类,四个不同的调度类型（,Thomas Granzer 2004,）,:,1)queue scheduling,队列调度,每个观测阶段为一个,jobs,清单，由,robot,顺序执行。,不可预知的延迟（如聚焦时间、快速定向时间、天气因素）就会使,jobs,丢失观测。,不能实时插入,jobs,，不能改写剩余的调度队列。,调度方法分类,2,）,Critical Path Scheduling,关键路径调度,这是一个尊重所有,job,依赖关系,的调度方式，确保最少的依赖的,job,先调度，多依赖的,job,后调度。天文观测很少有这样的依赖关系，很少使用这种方法，这不是一个合适的调度方法。,3,）,Optimal Scheduling,优化调度,这种方法需要大量的计算，来建立一个合适的时间表，以创造一个最好的调度方式。但是，预先算好的调度表还是不能对不可预知的变化作出反应。,调度方法分类,4,）,Dispatch Scheduling,分配调度,这种类型的调度器为每个作业（,job,）计算出一个分数（,score,），放在调度池（,pool,）中，每次选择分数最高的执行。,这种方法解决了不可预知的因素所带来的影响，因为调度不是固定的。,然而，由于调度的不固定，预知,robot,下一步要做什么是很困难的。而且需要一个能够改变优先级的评分算法（,scoring algorithm,）。,调度方法分类,Liverpool Telescope,、,STELLA,、,BRT,项目采取了“分配调度”的方法,Hubble telescope,由于有一个更好的可以预见的环境，使用了“优化调度”的方法,改进的调度方式：,环状队列，双队列，多种调度方式结合,关于“分配调度”方式,分配调度程序需求,分配调度程序应满足以下要求：,所有等待处理的,job,，必须进行每,隔几分钟,进行评估、定分,每个,job,必须结合,多种因素,（,factor,）的评价、计算出唯一的一个分数,因素有,加权值,，反应因素的重要程度。允许管理员控制每个因素的加权值,软件以,模块化,的方式来编写，这样在新增因素、删除旧的因素时,scheduler,能及时响应,分配调度程序需求,当,robot,要求,job,时，,scheduler,不能有延迟,-job,必须立刻准备好,在调度池内，设置为,immediate,标志,的,job,，必须优先考虑分配望远镜时间，不论其分数有多少,scheduler,应该准许,手动模式,加入特殊事件，系统管理员将分配,job,的观测时间。,需要进行评分的因素（,Score Factors,）,Score Factors,一些被确定为影响,job,的总体评分的因素：,job,目标达到天空中最高点的时刻,job,目标落入地平的时刻,job,间的相对距离（是否可以和其它观测任务合并）,job,预先设置的优先级值,job,要求的观测时间,job,一直在等待观测的时间量,Score Factor,的计算公式,Score Factor,的计算公式,Window merit(,观测窗口因素值,),一个计算,score,的示例,布尔测试,对一个,job,执行,scheduling,算法以前，可以执行一系列布尔测试，可以减少计算时间,计算出目标的高度和方位角，是否满足？,Job,是否过了观测时间？,目标是否符合相机的操作范围？,是否以正常（非特殊事件）的模式工作？,分配调度流程示例,上一次观测任务完成,从,request pool,提取一条任务请求,通过,bool,测试？,N,Y,第,1,个评分模块,第,2,个评分模块,第,N,个评分模块,分数加权求和,完成所有请求？,选取最高分的任务执行,N,Y,Scheduler,小结,考虑到上述所有因素，调度过程是一项复杂的任务。完全考虑到所有的因素，和它们之间的冲突是不实际的；,Scheduler,是保证资源公平的分配一个,最优化的,解决方案；,是各方面因素的,妥协,的结果。,普通望远镜，由人来决策,自主望远镜，由计算机“决策”,BOOTES 4,RTS2,(Remote Telescope System,2nd Version),采用遗传算法最优化选取,分布式调度,一个实际的实现的例子,Thank You!,
展开阅读全文