CN101465792B - 一种数据调度方法及装置 - Google Patents

Abstract

本发明公开了一种数据调度方法，用于对待传输的数据进行调度。所述方法包括下述步骤：1)为待传输数据设置时间戳属性PollSpan；2)根据数据的时间戳属性，生成原始数据队列；3)根据原始数据队列生成数据调度队列。此外，本发明还公开了一种数据调度装置，其包括：设置单元，用于为待传输数据设置时间戳属性PollSpan；原始数据队列生成单元，用于根据数据的时间戳属性，生成原始数据队列；以及数据调度队列生成单元，用于根据原始数据队列生成数据调度队列。本发明提供的数据调度方法和装置能够使每次调度/传输的数据量大致相同，以均衡系统资源，增加系统实际支持的数据量，并能够提高系统的资源利用率。

Description

一种数据调度方法及装置 

技术领域

本发明涉及数据处理领域，具体而言，涉及一种数据调度方法及数据调度装置。 

背景技术

在通信、软件设计等领域的“服务器端/客户端”的结构中，数据实时传输对系统的要求很高，既要保证在要求的时间内能够完成数据传输，又要最大限度地提高系统实际支持的数据量，而且还要保证较低的系统占用率以使系统稳定运行。 

在现有技术中，通常不对数据传输进行优化。这种情况下，为了保证对传输频率最高的数据进行实时传输，系统不得不工作在最高传输频率。然而，对于较低传输频率的数据而言，过高的传输频率是一种资源浪费。而且在现有技术中，为了保证数据传输的实时性，系统实际支持的数据量通常会比较低。此时，如果要增加系统实际支持的数据量，就会明显增加系统对计算机资源的占用率；如果要降低资源占用率，就不得不降低系统实际支持的数据量。这样，难以调和资源占用率和实际支持的数据量的关系。 

下面以一个例子来说明现有技术中如何进行数据实时传输。 

假定有10个数据需要实时更新，其中，要求每100ms更新一次的数据有3个，分别记为A1、A2和A3；每200ms更新一次的数据有4个，分别记为B1、B2、B3和B4；每300ms更新一次的数据有3个，分别记为C1、C2和C3。同时，假设系统每100ms最多能处理10个数据。 

在不对数据传输进行优化的情况下，系统进行数据传输时实际数据调度情况如表一所示，其中，“序号”表示第几次数据调度/传输，也就是第几个100ms；每一行“被传输的数据”表示每100ms中系统 所传输处理的数据。例如，在第1个100ms，数据A1至A3、B1至B4以及C1至C3均被传输；在第2个100ms，仅数据A1至A3被传输；在第3个100ms，数据A1至A3以及B1至B4被传输；在第4个100ms，数据A1至A3以及C1至C3被传输，……，这样便可以实现每100ms传输一次数据A1至A3，每200ms传输一次数据B 1至B4，每300ms传输一次数据C1至C3。 

表一：现有技术中数据传输调度列表 

通过上述描述可以看出，尽管现有技术中可以实现数据的实时传输，但是其不可避免地存在下述缺陷： 

其一，系统实际支持的数据量较少。由于现有技术中提供的数据调度方法未对数据的调度/传输进行优化，因此导致系统实际支持的数据量较少。以上述表一为例，最多只能支持10个数据。 

其二，系统资源利用率偏低。现有技术提供的数据传输调度方法中，有的时间段内数据传输量较大，而有的时间段内数据的传输量较小。这样，在数据传输量较小的时间段内，系统的资源利用率较低。 

其三，对资源的利用不均衡。在数据传输量较小的时间段内，系统的资源利用率较低；在数据传输量较大的时间段内，系统的资源利用率较高，也就是说，现有技术提供的数据传输调度方法占用系统资源时多时少，这不仅影响系统的稳定性，而且还浪费系统资源。 

发明内容

为解决上述技术问题，本发明提供了一种数据调度方法和数据调度装置，其能够使每次调度/传输的数据量大致相同，以均衡系统资源，增加系统实际支持的数据量，并能够提高系统的资源利用率。 

为此，本发明的技术方案为：提供一种数据调度方法，用于对待传输的数据进行调度。所述方法包括下述步骤：1)为待传输数据设置时间戳属性PollSpan，即，根据系统的基准响应时间和待传输数据的响应时间，确定数据的PollSpan等级和取值范围，并根据数据的PollSpan等级和取值范围，为数据分配PollSpan初始值；其中，所述时间戳属性包括PollSpan等级、PollSpan取值范围、PollSpan初始值和PollSpan当前值，并且在数据传输过程中，PollSpan在其取值范围内以步长为1的步幅递减，且当PollSpan的值递减为0时自动回复到取值范围内的最大值，以在其取值范围内实现递减循环；2)根据数据的时间戳属性，生成原始数据队列；3)遍历整个原始数据队列，查找PollSpan值为1的所有数据；4)根据所获得的PollSpan值为1的数据，生成数据调度队列。 

其中，在所述步骤2)和步骤3)之间还包括下述步骤：21)判断是否在原始数据队列中添加或去除了数据，如果是，则转向步骤22)；如果否，则转入步骤3)；以及步骤22)在原始数据队列中查找与添加或去掉的数据同等级的所有数据，对这些数据重新分配PollSpan值，并转入步骤2)，以重新生成原始数据队列。 

其中，在所述步骤4)之后还包括这样的步骤：将原始数据队列中所有数据的PollSpan值减1，并转入步骤3)，以待下一次生成数据调度队列。 

作为本发明的另一个技术方案，还提供一种数据调度装置，用于对待传输的数据进行调度。所述数据调度装置包括设置单元、原始数据队列生成单元和数据调度队列生成单元。其中，所述设置单元用于为待传输数据设置时间戳属性PollSpan，所述时间戳属性包括PollSpan等级、PollSpan取值范围、PollSpan初始值和PollSpan当前值，并且在数据传输过程中，PollSpan在其取值范围内以步长为1的步幅递减，且 当PollSpan的值递减为0时自动回复到取值范围内的最大值，以在其取值范围内实现递减循环；所述设置单元具体包括：PollSpan等级设置子单元，其用于根据系统的基准响应时间和待传输数据的响应时间，确定数据的PollSpan等级；PollSpan取值范围设置子单元，其用于根据系统的基准响应时间和待传输数据的响应时间，确定数据的PollSpan的取值范围；以及PollSpan初始值设置子单元，其用于根据数据的PollSpan等级和取值范围，为数据分配PollSpan初始值。所述原始数据队列生成单元用于根据数据的时间戳属性，生成原始数据队列。所述数据调度队列生成单元用于根据原始数据队列生成数据调度队列，具体地，所述数据调度队列生成单元遍历整个原始数据队列，查找PollSpan值为1的所有数据，并根据这些PollSpan值为1的数据生成数据调度队列。 

其中，所述数据调度装置还包括数据量变化判定单元，用于判断是否在原始数据队列中添加或去除了数据，如果是，则在原始数据队列中查找与添加或去掉的数据同等级的所有数据，对这些数据重新分配PollSpan值，并请求原始数据队列生成单元重新生成原始数据队列；如果否，则请求数据调度队列生成单元生成数据调度队列。 

其中，所述数据调度队列生成单元在生成数据调度队列后，将原始数据队列中所有数据的PollSpan值减1，以待下一次根据PollSpan值为1的数据生成数据调度队列。 

相对于现有技术，本发明提供的数据调度方法及装置具有下述有益效果： 

其一，本发明提供的数据调度方法和装置中，通过为待传输数据设置时间戳属性PollSpan，来对数据调度方法进行优化，这样，对于相同等级的数据而言，可以在PollSpan的取值范围内大致均衡地分配各个数据的PollSpan初始值，并使PollSpan的当前值以该初始值为起点而在PollSpan的取值范围内循环，从而形成每一次数据传输所需的数据调度队列。因此，采用本发明提供的数据调度方法和装置可以使每次传输时系统资源的利用较为均衡。 

其二，由于本发明提供的数据调度方法和装置可以使每次传输时 系统资源的利用较为均衡，因此不会使传输数据量时多时少，从而提高系统资源的利用率。 

其三，由于本发明提供的数据调度方法和装置根据数据的时间戳属性，对相同等级的数据的调度次序进行配置，而无需像现有技术那样，在一次调度/传输过程中对相同等级的所有数据进行调度/传输，因此，可以增大系统实际支持的数据量。 

附图说明

图1是生成原始数据队列的流程示意图；以及 

图2是生成数据调度队列的流程示意图。 

具体实施方式

本发明的技术核心为：为每一个待传输/更新的数据设置时间戳属性，根据时间戳的等级和数值来确定并分配每一次调度传输的数据，使每次调度/传输的数据量大致相同，以均衡系统资源，增加系统实际支持的数据量，并提高系统的资源利用率。 

本发明提供的数据调度方法为每一个待传输的数据设置了时间戳属性，记为PollSpan。为便于该方法的实现，PollSpan的取值定义为不小于1的整数，至于其取值规则，可以参照下述说明。 

PollSpan以系统可以响应的最小反映时间(即，最小响应时间，以下称为基准响应时间)为基准1，其他响应时间(待传输数据的响应时间)为此时间的整数倍。下述表二为PollSpan取值范围的一个实例，其中基准响应时间为100ms。这样，当数据的响应时间在100-199ms之间时，其PollSpan的取值可以为1；当数据的响应时间在200-299ms之间时，其PollSpan的取值可以为1或2；当数据的响应时间在300-399ms之间时，其PollSpan的取值可以为1或2或3；以此类推。 

表二：PollSpan取值范围的实例 

对于某个数据而言，其PollSpan的最小值为1，其PollSpan的最大值称为该数据的PollSpan等级。通常，PollSpan的取值范围在1和其PollSpan等级之间。当PollSpan为1时，表示此数据需要更新；当PollSpan不为1时，表示此数据不需要更新。 

在数据传输过程中，PollSpan在其取值范围内递减循环，即，PollSpan的值以步长为1的步幅递减，并且当PollSpan的值递减为0时，自动回复到取值范围内的最大值。例如： 

若PollSpan的取值范围为1一3，则一个可能的循环是：21321321321321321…… 

若PollSpan的取值范围为1，则其循环是：1111111111111…… 

下面说明如何为数据设置PollSpan的初始值。设置初始值的目的，就是给每一个待传输更新的数据设置一个恰当的PollSpan初始值，以便以该初始值为起点并在PollSpan取值范围内进行循环递减，从而保证系统每次更新调度的数据量m基本不变。 

假设原始数据队列中PollSpan等级为1的数据有n1个，等级为2的数据有n2个，……，等级为n的数据有nn个，则平均每次需要更新的数据量如下述公式1所示： 

m＝n1+n2/2+……+nt/t+……+nn/n          (公式1) 

其中，m值理论上可以为整数，也可以为小数值，但是在实际传输时，其只能取整数，故而可以将公式1变型为下述公式2： 

M＝N1+N2+……+Nt+……+Nn                (公式2) 

其中，N1＝n1，N2＝n2/2，N3＝n3/3，……，Nn＝nn/n，并且M、 N1、N2……Nn均为整数。 

根据公式2，在每次数据调度/传输过程中，需要传输N1个PollSpan等级为1的数据、N2个等级为2的数据、Nt个等级为t的数据，……，以及Nn个等级为n的数据。 

下面以一个实例说明当m值为小数时，如何调度分配每次传输的数据量。假定计算得到m值为20.3，那么在实际传输过程中，可以在第一次传输时，传输20个数据，在第二次传输时，传输20个数据，在第三次传输时，传输21个数据，……，多次传输后，实际每次传输的数据量的平均值便接近于m的理论值。 

事实上，当原始数据队列生成之后，有可能需要再添加或去除数据，而使得某个等级的数据个数发生变化，例如，等级t的数据个数由nt变化为nt’，此时每次需要传输的数据量就由m个变为m’，并且公式1变型为下述公式3 

m’＝n1+n2/2+……+nt’/t+……+nn/n         (公式3) 

M’＝N1+N2+……+Nt’+……+Nn               (公式4) 

其中，M’为当等级为t的数据个数发生变化时，每次需要传输的实际数据数量。 

因为M值又等于原始数据队列中所有PollSpan当前值为1的数据的个数，所以原始数据队列中每增加或减少一个数据，就需要根据上述公式1对现有的原始数据队列中的所有数据的PollSpan当前值进行计算，以获得新的数据传输数量M’。 

例如，现有的原始数据队列中仅有一个PollSpan等级为2的数据，记为B1，其当前的PollSpan值为1。此时，系统增加了一个PollSpan等级为2的数据B2，那么B2当前的PollSpan值应该为2，而不是1，这样才能保证每次传输的PollSpan等级为2的数据量n2/2＝2/2＝1，并且每个数据都得到了及时的传输。 

对比公式1和公式3，可以看到不同PollSpan等级之间的数据不会互相影响，因此当原始数据队列中仅仅是PollSpan等级为t的数据量发生变化时，只需要修改所有PollSpan等级为t的数据的PollSpan值即可，而无需对原始数据队列中的全部数据进行修改，这样，可以 大大减少需要修改的数据量，减轻系统负担。 

下面结合附图对本发明提供的数据传输方法进行详细说明。 

首先，结合图1说明如何生成原始数据队列。 

步骤110，根据系统的基准响应时间和待传输数据的响应时间，确定数据的PollSpan等级和取值范围。 

步骤120，初始化第一个数据，即，根据该数据的PollSpan等级和取值范围，为该数据分配PollSpan初始值。 

步骤130，根据数据的PollSpan值，生成原始数据队列。 

步骤140，判断是否添加或去除数据，如果是，则转向步骤150；如果否，则转入步骤160。 

步骤150，遍历原始数据队列中所有数据的PollSpan等级，找出与添加或去掉的数据同等级的所有数据，并重新分配他们的PollSpan值，以使m值保持稳定。而后转入步骤130，以重新生成原始数据队列。 

步骤160，结束生成原始数据队列的过程。 

接下来，结合图2说明如何生成数据调度队列。 

步骤210，遍历整个原始数据队列，查找PollSpan值为1的所有数据。 

步骤220，根据在步骤210获得的PollSpan值为1的数据，生成数据调度队列。 

步骤230，将原始数据队列中所有数据的PollSpan值减1，并转入步骤210，以待下一次生成数据调度队列。 

每一次生成数据调度队列后，在其后的每一次数据传输/更新中，根据该数据调度队列而对这些数据进行传输/更新。 

下面，结合表三说明采用本发明提供的数据调度方法后，系统实际进行数据调度的情况。类似于表一所示现有技术，假定有10个数据需要实时传输/更新，并且系统每100ms最多能处理10个数据，其中，要求每100ms更新一次的数据有3个，分别记为A1、A2和A3；每200ms更新一次的数据有4个，分别记为B1、B2、B3和B4；每300ms更新一次的数据有3个，分别记为C1、C2和C3。 

首先，根据图1所示流程生成原始数据队列，如表三所示。 

在表三中，数据A1、A2和A3的更新频率为100ms，他们的PollSpan等级为1，并且取值范围为1；数据B1、B2、B3和B4的更新频率为200ms，他们的PollSpan等级为2，并且取值范围为1，2；数据C1、C2和C3的更新频率为300ms，他们的PollSpan等级为3，并且取值范围为1，2，3。 

为每一个数据设置PollSpan初值，例如，数据A1、A2、A3、B1、B2和C1的PollSpan初值设置为1，数据B3、B4和C2的PollSpan初值设置为2，数据C3的PollSpan初值设置为3。 

然后，根据图2所示流程生成数据调度队列。具体地，根据PollSpan的当前值为1的数据，生成每一次数据调度和传输的数据调度队列。例如，在第1个100ms，数据A1至A3、数据B1和B2以及数据C1被调度和传输；在第2个100ms，数据A1至A3、数据B3和B4以及数据C2被调度和传输；在第3个100ms，数据A1至A3、数据B 1和B2以及数据C3被调度和传输；在第4个100ms，数据A1至A3、数据B3和B4以及数据C1被调度和传输，……，这样便可以实现每100ms传输一次数据A1至A3，每200ms传输一次数据B 1至B4，每300ms传输一次数据C1至C3。 

表三：本发明中数据传输调度列表 

[0076] 从上述表三可以看出，每次调度和传输数据时，被调度和传输的数据量较为均衡，均为6个，这不会使数据传输时多时少，增加了系统的稳定性。 

另外，比较表一和表三发现，当原始数据队列中PollSpan等级为1的数据为3个、PollSpan等级为2的数据为4个以及PollSpan等级为3的数据为3个时，若采用表一所示现有技术中的调度方法，则系统最多只能调度和传输这10个数据，而不能再向原始数据队列中添加数据；然而，若采用本发明提供的调度方法，可以向原始数据队列中添加数据，例如，再添加4个PollSpan等级为2的数据以及6个PollSpan等级为3的数据，这样，系统实际支持的数据量可达20个(即，3个PollSpan等级为1的数据，8个PollSpan等级为2的数据，9个PollSpan等级为1的数据)，这种情况下，系统实际支持的数据量比采用表一所示调度方法时提高了一倍，从而使系统资源得到充分利用。 

下面详细说明系统实际支持的数据量的范围。 

假设原始数据队列中PollSpan等级为1的数据有n1个，等级为2的数据有n2个，……，等级为n的数据有nn个，则系统可以传输的最大数据量(sum)＝n1/1+n2/2+n3/3…+nn/n. 

此时，系统可以支持的最大数据量(t)＝n1+n2+n3+…+nn 

考虑下述两种极端情况：即，第一种情况，原始数据队列中的数据全是等级为1的数据，则此时系统实际支持的数据量最小，为t＝1*sum＝sum；第二种情况，原始数据队列中的数据全是等级为n的数据，则此时系统实际支持的数据量最大，为t＝n*sum。 

综合上面的情况，可以得出这样的结论：系统可以支持的最大数据量(t)＜＝n*sum。 

此外，本发明还提供了一种数据调度的装置，其包括设置单元、原始数据队列生成单元和数据调度队列生成单元。 

其中，设置单元用于为待传输数据设置时间戳属性PollSpan。所述时间戳属性包括PollSpan等级、PollSpan取值范围、PollSpan初始值和PollSpan当前值。设置单元具体包括：PollSpan等级设置子单元，用于根据系统的基准响应时间和待传输数据的响应时间，确定数据的 PollSpan等级；PollSpan取值范围设置子单元，用于根据系统的基准响应时间和待传输数据的响应时间，确定数据的PollSpan的取值范围；PollSpan初始值设置子单元，用于根据数据的PollSpan等级和取值范围，为数据分配PollSpan初始值。 

原始数据队列生成单元，用于根据数据的时间戳属性，生成原始数据队列。 

数据调度队列生成单元，用于根据原始数据队列生成数据调度队列。具体地，数据调度队列生成单元遍历整个原始数据队列，查找PollSpan值为1的所有数据，并根据这些PollSpan值为1的数据生成数据调度队列。通常，数据调度队列生成单元在生成数据调度队列后，将原始数据队列中所有数据的PollSpan值减1，以待下一次根据PollSpan值为1的数据生成数据调度队列。 

此外，本发明提供的数据调度装置还包括数据量变化判定单元，用于判断是否在原始数据队列中添加或去除了数据，如果是，则在原始数据队列中查找与添加或去掉的数据同等级的所有数据，对这些数据重新分配PollSpan值，并请求原始数据队列生成单元重新生成原始数据队列；如果否，则请求数据调度队列生成单元生成数据调度队列。 

需要指出的是，对于一个系统而言，其所允许的支持数据量(简称为“允许支持数据量”)由系统本身性能决定，而且，其所允许的每一次传输的数据量(简称为“允许传输数据量”)同样也由系统本身性能决定。这样，上文所说的系统实际支持的数据量必定小于允许支持数据量。 

可以理解的是，以上实施方式仅仅是为了说明本发明的原理而采用的示例性实施方式，然而本发明并不局限于此。对于本领域内的普通技术人员而言，在不脱离本发明的精神和实质的情况下，可以做出各种变型和改进，这些变型和改进也视为本发明的保护范围。 

Claims (6)

1.一种数据调度方法，用于对待传输的数据进行调度，其特征在于，所述方法包括下述步骤：

1)为待传输数据设置时间戳属性PollSpan，即，根据系统的基准响应时间和待传输数据的响应时间，确定数据的PollSpan等级和取值范围，并根据数据的PollSpan等级和取值范围，为数据分配PollSpan初始值；其中，所述时间戳属性包括PollSpan等级、PollSpan取值范围、PollSpan初始值和PollSpan当前值，并且在数据传输过程中，PollSpan在其取值范围内以步长为1的步幅递减，且当PollSpan的值递减为0时自动回复到取值范围内的最大值，以在其取值范围内实现递减循环；

2)根据数据的时间戳属性，生成原始数据队列；

3)遍历整个原始数据队列，查找PollSpan值为1的所有数据；

4)根据所获得的PollSpan值为1的数据，生成数据调度队列。

2.根据权利要求1所述的数据调度方法，其特征在于，在所述步骤2)和步骤3)之间还包括下述步骤：

21)判断是否在原始数据队列中添加或去除了数据，如果是，则转向步骤22)；如果否，则转入步骤3)；

22)在原始数据队列中查找与添加或去掉的数据同等级的所有数据，对这些数据重新分配PollSpan值，并转入步骤2)，以重新生成原始数据队列。

3.根据权利要求1或2所述的数据调度方法，其特征在于，在所述步骤4)之后还包括这样的步骤：将原始数据队列中所有数据的PollSpan值减1，并转入步骤3)，以待下一次生成数据调度队列。

4.一种数据调度装置，用于对待传输的数据进行调度，其特征在于包括：设置单元、原始数据队列生成单元和数据调度队列生成单元，其中

所述设置单元为待传输数据设置时间戳属性PollSpan，所述时间戳属性包括PollSpan等级、PollSpan取值范围、PollSpan初始值和PollSpan当前值，并且在数据传输过程中，PollSpan在其取值范围内以步长为1的步幅递减，且当PollSpan的值递减为0时自动回复到取值范围内的最大值，以在其取值范围内实现递减循环；所述设置单元具体包括；

PollSpan等级设置子单元，用于根据系统的基准响应时间和待传输数据的响应时间，确定数据的PollSpan等级；

PollSpan取值范围设置子单元，用于根据系统的基准响应时间和待传输数据的响应时间，确定数据的PollSpan的取值范围；以及

PollSpan初始值设置子单元，用于根据数据的PollSpan等级和取值范围，为数据分配PollSpan初始值；

所述原始数据队列生成单元根据数据的时间戳属性，生成原始数据队列；以及

所述数据调度队列生成单元遍历整个原始数据队列，查找PollSpan值为1的所有数据，并根据这些PollSpan值为1的数据生成数据调度队列。

5.根据权利要求4所述的数据调度装置，其特征在于，还包括数据量变化判定单元，用于判断是否在原始数据队列中添加或去除了数据，如果是，则在原始数据队列中查找与添加或去掉的数据同等级的所有数据，对这些数据重新分配PollSpan值，并请求原始数据队列生成单元重新生成原始数据队列；如果否，则请求数据调度队列生成单元生成数据调度队列。

6.根据权利要求4或5所述的数据调度装置，其特征在于，所述数据调度队列生成单元在生成数据调度队列后，将原始数据队列中所有数据的PollSpan值减1，以待下一次根据PollSpan值为1的数据生成数据调度队列。

Images