时间：2022-11-20 20:30:01 | 来源：信息时代
时间：2022-11-20 20:30:01 来源：信息时代
数据流调度 : 对数据流操作的执行顺序,可分成任务调度与任务内操作符的调度。数据流任务调度是指根据一定的算法,从目前数据流管理系统中的一批连续查询任务或一次性查询任务中,选出若干个任务,分配必要的资源,如内存空间、外部设备等,为它们建立相应任务进程(或线程),最后把这些任务的程序调入内存,等待调度程序去调度执行。数据流操作符调度是指根据一定的算法,将查询任务分解成一系列的操作并排定一定的执行顺序进行调度执行。
数据流任务调度的目标是使任务运行最大限度地发挥各种资源的利用率,并保持系统内的各种活动充分运行。
数据流系统的调度直接关系到查询计划的执行和资源的分配,是数据流系统的核心问题之一。在实施过程中,系统为达到各种性能指标的要求会发生冲突(例如较小的响应时间必然要求较大的内存),所以对实际系统而言,寻找各种指标的平衡至关重要。具体的数据流管理系统会根据数据流的特点和需达到的目的,以部分牺牲其他性能为代价,选取其中的一个或一部分性能作为主要衡量指标。在许多数据流应用中,对系统的实时性要求较高,这一点与其他的实时系统相同。同时与其他的实时系统任务相比,数据流系统任务具有以下特点: 调度任务之间可能存在依赖关系; 调度任务之间可能共享滑动窗口; 调度任务可能存在不可抢占区; 调度任务可能是一次性的任务,也可能是连续周期性的任务; 连续周期性的任务的每个周期需要的处理时间因滑动窗口规模的变化可能并不相同。
目前,数据流系统常用的调度算法有:
(1)先进先出调度(FIFO):按到达顺序处理每一个元组,在一个元组处理完成之后才会考虑下一个元组。FIFO策略在元组的最小化响应时间方面起到很好的作用。但它没有考虑运算符的选择率,对突发的数据流没有适应性,容易造成数据流元组的堆积,从而占用系统大量的内存资源。
(2)环调度(round-robin): 在所有的运算符之间循环。每个运算符运行一个固定的时间片,直到时间终止或队列为空时停止。循环调度不会出现运算符的饥饿状态,但它与FIFO一样对于爆发性的数据流没有适应性。
(3)贪心调度(greedy): 在贪心调度策略中,每一个运算符有一个静态的优先级(1-s)/t,其中,s为选择率,t为运算符处理一个元组的时间。这一策略考虑了运算符的选择率,按优先级来调度运算符,尽量使高选择率的运算符优先,这样可以减少内存占用,但它的问题是没有考虑路径中运算符之间的位置关系,使得输出延迟很大。例如,假设有一快速且高选择率的运算符H跟随在几个很小选择率的运算符之后,虽然运算符H比它前面的运算符有更高的优先级,然而,在很多时刻里H无法被调度,因为它的输入队列是空的,造成运算符的饥饿状态。
(4)链调度(chain):是在贪心算法的基础上考虑了运算符的位置关系,解决了具有高优先级的运算符的饥饿问题。但链调度只是单独关注如何最小化运行时内存的最大使用量,忽略了输出延迟这一重要方面。在输入数据流爆发期间,链表要遭受元组的饥饿,即链表更喜欢操作那些落在低包络线上最大斜率段的新元组,而忽略了系统中落在不太陡峭斜率段的更早的元组,从而导致这些元组的高延迟。虽然最小化运行时内存的使用量是很重要的,但许多数据流应用系统也要求对输入流的响应时间应在指定的时间间隔内。
(5)基于Eddy的调度: 使用的调度规则类似于STREAM系统中的贪心调度,但是,Eddy调度的是元组,而不是运算符的执行。数据进入Eddy,Eddy发送元组到运算符,运算符作为一个独立的线程而执行,其结果再返回给Eddy,元组被所有运算符处理后,Eddy将其输出。Eddy的目的是最大化吞吐量,不像STREAM关心的是队列的大小。
(6) 多级调度: 在Aurora系统中,若干个box组合成一个superbox作为调度和执行的基本单元。系统采用两级调度,第一级调度决定哪些superbox被调度,第二级调度决定superbox内部box的执行次序。第一级调度有静态调度和动态调度两种,目前以静态调度为主,可以通过各种调度算法(如round-robin)来实现。第二级调度采用三种调度策略:基于最大吞吐量的调度、基于最小延迟的调度和基于最小内存消耗的调度。在Aurora系统中,由于大规模、高动态的系统特征和调度的粒度等方面因素,寻找最优的调度方法是十分困难的,因此启发式方法常常是很有效的。
(7)其他算法: Q.Jiang和S.Chakravarthy提出了一种基于算子路径的进度安排策略PCS(path capacity scheduling),通过为具有最大能力处理的路径安排进度的方式来达到最小化响应时间的目的,进而提出了segment scheduling策略,通过将算子路径分解为若干片断,在处理占用空间控制方面取得了较好的效果。
目前针对数据流实时任务调度算法的研究还不多,因此,参考传统实时系统中单调速率(rate monotonic,RM)、截止期最早最优先(earliest deadline first,EDF)、空闲时间最短最优先(least slack first,LSF)、最早放行最优先、可达截止期最早最优先、价值最高最优先(highest value first,HVF)、价值密度最大最优先(highest value density first,HVDF)等调度策略算法,结合数据流负载模型以及连续查询优化技术、过载调整技术,设计支持QoS最大化的实时任务调度算法是数据流调度算法研究的方向之一。
在线咨询
