CN101887383B - 一种进程实时调度方法 - Google Patents

Abstract

本发明实施例公开了一种进程实时调度方法，包括：步骤A、预先设置进程任务的价值值，任务的价值值应根据任务本身的价值在进程的优先级值与当前所有进程最大优先级值之间取一个值；步骤B、当进程任务的优先级相近或相等时，比较进程任务的价值值，优先运行价值大的任务；或者，当系统过载时也比较当前所有任务的价值值，运行价值值最大的进程任务，保证系统整体价值最大化和被维持在一个可接受的水平之上。通过实施本发明，通过引入基于价值的抢占阀值，既可以在系统过载情况下，系统能保证关键任务的及时完成，维持系统性能优雅地降级，不致出现系统失效甚至崩溃，最终达到便整个系统价值最大化，还可以减少因颠簸现象造成的资源浪费。

Description

一种进程实时调度方法

技术领域

本发明涉及计算机进程调度领域，具体涉及一种进程实时调度方法。

背景技术

随着Linux系统广泛应用于嵌入式系统、实时控制等领域，增强Linux内核的实时性变得尤为重要，而Linux内核的核心是调度策略，调度策略的优化及实时性改进的根本是调度算法，对实时调度算法的研究是实时领域的一个重要的研究领域。优先级驱动方式是实时系统调度最常见的一种方式，根据任务的特定信息给每个任务一个优先级，当系统需要进行调度时依据优先级选择下一个要运行的任务，保证系统公平、有效的响应完成任务。

实时调度策略可以分为三种：基于优先级的调度策略、基于时间驱动的调度策略和基于比例共享的调度策略。基于优先级的调度算法可以分为两种类型：静态优先级调度算法和动态优先级调度算法。最小裕度优先(Least Slack First)调度算法是实时系统中比较常见的动态优先级调度算法，它是对最早截至期优先(EDF)调度算法的改进。最早时限优先(EDF)算法是使用最多的一种动态优先级调度算法，该算法给就绪队列中的各个任务根据它们的截止期限(Deadline)来分配优先级，具有最近的截止期限的任务具有最高的优先级。

LSF在系统中为每一个任务设定松弛时间，系统优先执行具有最小松弛时间的任务。尽管在正常的系统负载下EDF算法和LSF算法表明了其最优性，但是在超载的情况下，系统不可能保证所有的任务都能够满足截止期，这时EDF或者LSF算法会出现性能急剧下降，可能导致不稳定由于错过重要任务最后期限。再者，截止期或者空闲时间任务不一定是最关键的，在过载的情况下系统无法保证关键任务的及时完成，从而系统性能不能优雅地降级，导致出现系统失效甚至崩溃。另外，在LSF算法中，当系统有一个以上最小裕度相近或者相等且是系统中具有最小裕度的任务时，系统会发生频繁的任务切换，即颠簸现象，会造成系统资源的浪费。

发明内容

本发明的目的在于提供一种进程实时调度方法，该算法能够保证在过载的情况下，支持系统性能优雅地降级，不致出现系统失效甚至崩溃，使系统整体价值被最大化和被维持在一个可接受的水平之上，同时减少颠簸现象造成的系统资源浪费。

为了达到上述目的，本发明实施例提供了一种进程实时调度方法，包括：

步骤A、预先设置进程任务的价值值，任务的价值值应根据任务本身的价值在进程的优先级值与当前所有进程最大优先级值之间取一个值；

步骤B、当进程任务的优先级相近或相等时，比较进程任务的价值值，优先运行价值大的任务；或者，当系统过载时也比较当前所有任务的价值值，运行价值值最大的进程任务，保证系统整体价值最大化和被维持在一个可接受的水平之上。

所述预先设置进程任务的价值值具体为：

在进程控制块task_struct中增加优先级相关属性：任务剩余执行时间Ct，任务提交时间Et，任务相对截至期限Dt，优先级值St，系统当前时间T，由优先级值定义公式得：St＝(Et+Dt)-Ct-T；

保持Linux2.6内核的运行队列结构、候选任务的选取方式及实时任务优先级属性不变，按优先级从小到大依次排列同一优先级属性的实时任务；

在时钟中断子程序中增加对优先级值St的实时更新处理，即随着时钟周期增加任务剩余执行时间Ct，减小等待进程的优先级值St，也在时钟中断子程序中修改把价值值作为抢占阀值的候选任务的选取操作；

改进最小裕度优先LSF算法，修改内核代码并重新编译，完成改进算法在系统中的实现。

所述步骤B包括：

B11、获取各个进程任务的优先级时间，当优先级相同时截止期靠前的任务优先级越高；

B12：判断当前系统是否存在一个以上优先级相近或相同的任务，若不存在，表明系统任务不会发生颠簸现象，则进行步骤B18；

B13、判断相近或相同的优先级是否为当前系统最小优先级，若不是，则表明该任务不是最紧急任务，则进行步骤B18；

B14、判断相近或相同的优先级是否大于0，当优先级小于0时淘汰该任务，裕度大于等于0参与调度。

B15、获取这些优先级值相近或相同且其值大于等于0的任务的价值值；

B16、比较这些优先级相近或相同且其值大于等于0的任务的价值值；

B17、依据任务价值值的大小，依次抢占执行；

B18、执行最小裕度优先LSF调度。

所述步骤B包括：

B21、当由于进程主动进入休眠状态、某个进程允许被抢占CPU或从中断或系统调用返回到用户态等情况出现，调度时机带来，系统进入调度状态；

B22、通过调度算法进行系统调度；

B23、判断系统是否过载，若没有，维持现状执行；若是则按B24进行；

B24、比较优先级值相近或相同且其值大于等于0的任务的价值值；

B25、依据任务的价值值大小，具有最大价值值的任务优先抢占当前任务的CPU使用权，依次类推执行；

B26、判断系统是否恢复正常情况，若没有则跳到B24，以获取系统整体最大的价值值，若正常跳到B22，系统正常运行。本发明通过引入基于价值的抢占阀值，既可以在系统过载情况下，系统能保证关键任务的及时完成，维持系统性能优雅地降级，不致出现系统失效甚至崩溃，最终达到便整个系统价值最大化，还可以减少因颠簸现象造成的资源浪费。

本发明实施例通过引入基于价值的抢占阀值，既可以在系统过载情况下，系统能保证关键任务的及时完成，维持系统性能优雅地降级，不致出现系统失效甚至崩溃，最终达到便整个系统价值最大化，还可以减少因颠簸现象造成的资源浪费。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。

图1为本发明实施例中的进程实时调度方法流程图；

图2为本发明实施例中的预先设置进程任务的价值值方法流程图；

图3为本发明实施例中的改进所要实现的实时调度算法流程图；

图4为本发明实施例中的改进所要实现的实时调度算法另一流程图。

具体实施方式

本发明实施例中提供了一种进程实时调度方法，其首先通过任务的价值值确定：任务价值，即任务的关键性，该任务相对于任务集中其他任务的重要程度。把任务的价值值作为抢占阀值，是改进算法的关键。抢占阀值直接影响到任务切换的频率，也影响到任务截止期的错失率，还影响到CPU的有效利用率。如果任务的价值值大于当前所有进程最大优先级值，则调度算法退化为非抢占模型。若任务的价值值小于进程的裕度(优先级值)，则失去了赋予任务价值做法的意义。具体1的可以参阅图1中的流程图，包括：

S101：预先设置进程任务的价值值，任务的价值值应根据任务本身的价值在进程的优先级值与当前所有进程最大优先级值之间取一个值；

S102：当进程任务的优先级相近或相等时，比较进程任务的价值值，优先运行价值大的任务；或者，当系统过载时也比较当前所有任务的价值值，运行价值值最大的进程任务，保证系统整体价值最大化和被维持在一个可接受的水平之上。

综上所述，任务的价值值应根据任务本身的价值在进程的裕度(优先级值)与当前所有进程最大优先级值之间取一个值。每个任务除了按裕度分配优先级，还有一个价值值，从而构成一个双优先级系统。双优先级系统即当任务的富裕度相近或相等时，比较任务的价值值，优先运行价值大的任务，它可以减少颠簸现象造成的系统资源浪费。当系统过载时也比较当前所有任务的价值值，运行价值值最大的任务，保证系统整体价值最大化和被维持在一个可接受的水平之上；

具体的，参阅图2，关于预先设置进程任务的价值值实现步骤如下：

S201、在进程控制块task_struct中增加“裕度”相关属性：任务剩余执行时间℃t，任务提交时间Et，任务相对截至期限Dt，裕度值St，系统当前时间T。由裕度定义公式得：St＝(Et+Dt)-Ct-T。

S202、保持Linux2.6内核的运行队列结构、候选任务的选取方式及实时任务优先级属性不变，按裕度值从小到大依次排列同一优先级任务。

S203、在时钟中断子程序中增加对裕度值的实时更新处理，即随着时钟周期增加任务剩余执行时间Ct，减小等待进程的裕度值St，也在时钟中断子程序中修改把价值值作为抢占阀值的候选任务的选取操作。

S204、改进所要实现的实时调度算法，修改内核代码并重新编译，完成改进算法在系统中的实现。

参阅图3，关于S102中改进所要实现的实时调度算法，修改内核代码并重新编译，完成改进算法在系统中的实现，所提到的改进算法具体步骤实现如下：

S301，获取各个任务的富裕时间，即“裕度”，当裕度相同时截止期靠前的任务优先级越高。

S302，判断当前系统是否存在一个以上裕度相近或相同的任务，若不存在，表明系统任务不会发生颠簸现象，跳到S308，执行LSF调度。该步骤的目的是防止系统发生颠簸现象。

S303，判断该裕度是否为当前系统最小裕度，若不是，则表明该任务不是最紧急任务，跳到S308，执行LSF调度。

S304，判断该裕度是否大于0，当裕度小于0时淘汰该任务，裕度大于等于0参与调度。

S305，获取这些裕度相近或相同且其值大于等于0的任务的价值值，该价值值在确定如前诉述。

S306，比较这些裕度相近或相同且其值大于等于0的任务的价值值，该步骤的目的是保证系统整体价值被维持在一个可接受的水平。

S307，依据任务价值值的大小，依次抢占执行，保证价值值打的任务，即关键任务优先执行。

S308，执行LSF调度。

参见图4，图4是改进算法调度应用流程图，调度步骤如下：

S401，当由于进程主动进入休眠状态、某个进程允许被抢占CPU或从中断或系统调用返回到用户态等情况出现，调度时机带来，系统进入调度状态。

S402，上述改进的调度算法进行系统调度，改步骤可以保证系统减少颠簸现象的发生，节省系统资源。也可以保证系统整体价值被维持在一个可接受的水平。

S403，判断系统是否过载，若没有，维持现状执行。若是则进行S404，此步骤的目的是保证系统在系统过载的情况下向着整体价值最大化发展。

S404，比较这些裕度相近或相同且其值大于等于0的任务的价值值，该步骤的目的是保证系统整体价值被维持在一个可接受的水平。

S405，依据任务的价值值大小，具有最大价值值的任务优先抢占当前任务的CPU使用权，依次类推执行。

S406，判断系统是否恢复正常情况，若没有则跳到S404，以获取系统整体最大的价值值，若正常跳到S402，系统正常运行。

综上，本发明实施例通过引入基于价值的抢占阀值，既可以在系统过载情况下，系统能保证关键任务的及时完成，维持系统性能优雅地降级，不致出现系统失效甚至崩溃，最终达到便整个系统价值最大化，还可以减少因颠簸现象造成的资源浪费。

本领域普通技术人员可以理解上述实施例的各种方法中的全部或部分步骤是可以通过程序来指令相关的硬件来完成，该程序可以存储于一计算机可读存储介质中，存储介质可以包括：只读存储器(ROM，Read Only Memory)、随机存取存储器(RAM，Random Access Memory)、磁盘或光盘等。

以上对本发明实施例所提供的一种数字家庭的地理信息的可视可听化方法，进行了详细介绍，本文中应用了具体个例对本发明的原理及实施方式进行了阐述，以上实施例的说明只是用于帮助理解本发明的方法及其核心思想；同时，对于本领域的一般技术人员，依据本发明的思想，在具体实施方式及应用范围上均会有改变之处，综上所述，本说明书内容不应理解为对本发明的限制。

Claims (3)

1.一种进程实时调度方法，其特征在于，包括： 

步骤A、预先设置进程任务的价值值，任务的价值值应根据任务本身的价值在进程的优先级值与当前所有进程最大优先级值之间取一个值； 

步骤B、当进程任务的优先级相近或相等时，比较进程任务的价值值，优先运行价值大的任务；或者，当系统过载时也比较当前所有任务的价值值，运行价值值最大的进程任务，保证系统整体价值最大化和被维持在一个可接受的水平之上； 

所述预先设置进程任务的价值值具体为： 

在进程控制块task_struct中增加优先级相关属性：任务剩余执行时间Ct，任务提交时间Et，任务相对截至期限Dt，优先级值St，系统当前时间T，由优先级值定义公式得：St＝(Et+Dt)-Ct-T； 

保持Linux2.6内核的运行队列结构、候选任务的选取方式及实时任务优先级属性不变，按优先级从小到大依次排列同一优先级属性的实时任务； 

在时钟中断子程序中增加对优先级值St的实时更新处理，即随着时钟周期增加任务剩余执行时间Ct，减小等待进程的优先级值St，也在时钟中断子程序中修改把价值值作为抢占阀值的候选任务的选取操作； 

改进最小裕度优先LSF算法，修改内核代码并重新编译，完成改进算法在系统中的实现。 

2.如权利要求1所述的方法，其特征在于，所述步骤B包括： 

B11、获取各个进程任务的优先级时间，当优先级相同时截止期靠前的任务优先级越高； 

B12：判断当前系统是否存在一个以上优先级相近或相同的任务，若不存在，表明系统任务不会发生颠簸现象，则进行步骤B18； 

B13、判断相近或相同的优先级是否为当前系统最小优先级，若不是，则表明该任务不是最紧急任务，则进行步骤B18； 

B14、判断相近或相同的优先级是否大于0，当优先级小于0时淘汰该任务，裕度大于等于0参与调度；

B15、获取这些优先级值相近或相同且其值大于等于0的任务的价值值； 

B16、比较这些优先级相近或相同且其值大于等于0的任务的价值值； 

B17、依据任务价值值的大小，依次抢占执行； 

B18、执行最小裕度优先LSF调度。 

3.如权利要求1所述的方法，其特征在于，所述步骤B包括： 

B21、当由于进程主动进入休眠状态、某个进程允许被抢占CPU或从中断或系统调用返回到用户态等情况出现，调度时机带来，系统进入调度状态； 

B22、通过调度算法进行系统调度； 

B23、判断系统是否过载，若没有，维持现状执行；若是则按B24进行； 

B24、比较优先级值相近或相同且其值大于等于0的任务的价值值； 

B25、依据任务的价值值大小，具有最大价值值的任务优先抢占当前任务的CPU使用权，依次类推执行； 

B26、判断系统是否恢复正常情况，若没有则跳到B24，以获取系统整体最大的价值值，若正常跳到B22，系统正常运行。 

Images