基于多任务系统中防止低优先级任务饿死的方法

摘要

本发明涉及一种基于多任务系统中防止低优先级任务饿死的方法的技术方案，包括：为CPU中就绪队列中的每个任务添加对应的饥饿时间；当任意任务的饥饿时间达到饥饿阈值时，将其添加至饥饿任务队列；通过调度时钟对进入饥饿任务队列的任务按照优先度进行顺序执行。本发明的有益效果为：每个任务只有唯一的优先级，不会动态改变优先级，比较方便操作系统的管理；饿死的任务在时钟中断返回时，就能马上得到调度执行，不必等待下一个调度时间点，因此能被更及时地调度；不同优先级任务的饥饿时间阈值、饥饿队列的解饿阈值可动态配置，能灵活满足不同应用场景的需要。

说明书

技术领域

本发明涉及计算机领域，具体涉及了一种基于多任务系统中防止低优先级任务饿死的方法。

背景技术

随着计算机和电子技术的发展，多任务操作系统已成为IT领域不可缺少的组成部分，广泛应用于服务器、桌面电脑、嵌入式系统等领域。在中小型应用场景，比如嵌入式领域，基于优先级和时间片的操作系统仍然发挥着重要的作用，它们以代码精简、高实时性、功耗低等优点，持续受到各应用厂商的青睐。

参考图1，操作系统一个主要功能是进行任务调度，即根据实际运行的需要，管理各个任务，为其分配处理器资源。通常任务可分为三种状态：就绪状态、正在运行状态、等待资源状态。与此对应，系统中一般存在两种任务队列：就绪队列、等待队列。当任务被创建后，进入就绪队列中等待被调度运行；当任务被调度运行时，它从就绪队列中移出来，变成当前运行着的任务；当运行着的任务因为等待某些资源、或者主动休眠而挂起时，它进入等待队列。

参考图2的操作系统中的等待任务队列，传统方法是发现有任务因为得不到CPU资源而饿死时，暂时提升任务的优先级，使之与就绪队列中最高优先级的任务相同。这样在后面的调度过程中，该任务便有机会得到运行。等该任务下次调度运行完成之后，重新将其放入原先优先级的队列中。这种方法首先造成任务的优先级混乱，每个任务既有原始优先级，又有动态优先级，而且动态优先级是变化的，不利于操作系统的管理。其次，饿死的任务还是无法马上调度运行，必须等下一个调度时间点，最坏的情况下，要等待将近一个完整的任务时间片。再次，饿死的任务被调度执行后，会执行一个完整的时间片，这样导致其他高优先级的就绪任务无法及时调度运行，造成较长的调度延时，而这些高优先级任务往往是需要及时响应的任务，比如响应用户触摸屏操作的任务，因此宏观上看可能出现卡顿现象，影响系统体验。

发明内容

本发明的目的在于至少解决现有技术中存在的技术问题之一，提供了一种基于多任务系统中防止低优先级任务饿死的方法，实现了低人力消耗的游戏性能优化。

本发明的技术方案包括一种基于多任务系统中防止低优先级任务饿死的方法，其特征在于，该方法包括：

为CPU中就绪队列中的每个任务添加对应的饥饿时间；

当任意任务的饥饿时间达到饥饿阈值时，将其添加至饥饿任务队列；

通过调度时钟对进入饥饿任务队列的任务按照优先度进行顺序执行；

其中，所述饥饿时间随任务的等待时间进行递增。

根据所述的基于多任务系统中防止低优先级任务饿死的方法，其中调度时钟对进入饥饿任务队列的任务按照优先度进行顺序执行还包括：对每个任务的执行一个时间片，所述时间片被设置为一个时钟中断的周期，以及，所述时间片还可以自定义设置；将被执行过的任务添加至所述就绪队列。

根据所述的基于多任务系统中防止低优先级任务饿死的方法，其中该方法还包括：在所述调度时钟的每个调度时间点对所述饥饿队列进行遍历；若饥饿队列为空，执行正常调度，在下次调度时间点，从就绪队列中选取下一个任务运行；若饥饿队列不为空，则判断饥饿队列任务本次连续运行的总时间是否达到解饿阈值，若达到该阈值，则暂停所述饥饿队列中任务的运行，并运行所述就绪队列中的任务。

根据所述的基于多任务系统中防止低优先级任务饿死的方法，其中解饿阈值被配置为：根据所述饥饿队列中的任务数量及饥饿阈值动态设置。

根据所述的基于多任务系统中防止低优先级任务饿死的方法，其中饥饿队列的任务以链表形式对不同优先级的任务进行存储，且所述饥饿队列中的任务的优先级无法被修改。

本发明的技术方案还包括一种基于多任务系统中防止低优先级任务饿死的装置，该装置包括存储器、处理器以及存储在所述存储器中并可在所述处理器上运行的计算机程序，其特征在于，所述处理器执行所述计算机程序时任一所述的方法步骤。

本发明的技术方案还包括一种计算机可读存储介质，所述计算机可读存储介质存储有计算机程序，其特征在于，所述计算机程序被处理器执行时实现任一所述的方法步骤。

本发明的有益效果为：每个任务只有唯一的优先级，不会动态改变优先级，比较方便操作系统的管理；饿死的任务在时钟中断返回时，就能马上得到调度执行，不必等待下一个调度时间点，因此能被更及时地调度；不同优先级任务的饥饿时间阈值、饥饿队列的解饿阈值可动态配置，能灵活满足不同应用场景的需要。

附图说明

下面结合附图和实施例对本发明进一步地说明；

图1所示为操作系统中就绪任务队列；

图2所示为操作系统中的等待队列；

图3所示为根据本发明实施方式的总体流程图；

图4所示为根据本发明实施方式的饥饿任务队列示意图；

图5所示为根据本发明实施方式的时钟中断中的任务调度流程图；

图6所示为根据本发明实施方式的装置图。

具体实施方式

本部分将详细描述本发明的具体实施例，本发明之较佳实施例在附图中示出，附图的作用在于用图形补充说明书文字部分的描述，使人能够直观地、形象地理解本发明的每个技术特征和整体技术方案，但其不能理解为对本发明保护范围的限制。

在本发明的描述中，若干的含义是一个或者多个，多个的含义是两个以上，大于、小于、超过等理解为不包括本数，以上、以下、以内等理解为包括本数。

在本发明的描述中，对方法步骤的连续标号是为了方便审查和理解，结合本发明的整体技术方案以及各个步骤之间的逻辑关系，调整步骤之间的实施顺序并不会影响本发明技术方案所达到的技术效果。

本发明的描述中，除非另有明确的限定，设置等词语应做广义理解，所属技术领域技术人员可以结合技术方案的具体内容合理确定上述词语在本发明中的具体含义。

术语解释：

SMP：Symmetrical Multi-Processor，对称式多处理器。指在一个计算机上汇集了一组处理器(CPU)，各CPU之间共享内存子系统和总线结构；

CPU：Central Processing Unit，即中央处理器，简称处理器；

CPU核心数：指芯片所包含的CPU处理器的个数；

多处理器：即多核、多处理器核、多CPU；

OS：Operating System操作系统；

Cache：即CPU内部的高速缓存；

Cache Line：即缓存行，是CPU高速缓存存取的最小单元。当Cache Line被CPU改写，且尚未更新到主存中时，称该Cache Line处于Dirty(脏)状态。

主存：即内存储器、主存储器、主存，用于暂时存放CPU的运输数据，断电后数据会丢失。

图3所示为根据本发明实施方式的总体流程图，该流程包括：为CPU中就绪队列中的每个任务添加对应的饥饿时间；当任意任务的饥饿时间达到饥饿阈值时，将其添加至饥饿任务队列；通过调度时钟对进入饥饿任务队列的任务按照优先度进行顺序执行。

参考图4，其中任务a、b、c及d处于不同的饥饿队列，本发明的技术方案每个任务增加一个描述饥饿程度的变量，称为饥饿时间。当任务进入就绪队列时，将饥饿时间清0，此后若任务没有及时得到调度执行，其饥饿时间会不断增大。当增大到某一设定值后，该任务处于饿死状态，需要立刻调度执行。这个设定的值称为饥饿阈值，不同优先级任务的饥饿阈值不一样。优先级越高，对饥饿状态的忍受度越低，其饥饿阈值也越小。

若系统中多个任务处于饿死状态，那么优先级高的任务自然要优先执行，此时通过饥饿队列来管理这些饿死状态的任务。与就绪队列类似，不同优先级分别对应一个链表，上面是所有该优先级的饿死状态的任务。

图5所示为根据本发明实施方式的时钟中断中的任务调度流程图，具体描述如下：

参考图5，当系统非常繁忙时，饥饿队列任务数可能瞬时较多，此时若等饥饿队列的所有任务调度一遍，再执行就绪队列的任务，就可能导致就绪队列中新的任务被饿死。因此会设定一个时间阈值，每次处理饥饿队列的任务时，总时间不能超过这个阈值，将该阈值称为解饿阈值。当饥饿队列处理时间超出解饿阈值时，将暂停饥饿任务的调度，转而去调度就绪队列的任务。通过这样的方式，既保证了饿死的任务能被及时调度，又能保证就绪队列的任务能得到及时调度，防止产生新的饿死任务。

系统时钟中断的处理流程中，会跟踪任务的饥饿情况，并根据需要对饥饿队列中的任务进行调度。

首先，对就绪队列中的所有任务的等待时间进行递增，当有新的任务等待时间超过该优先级任务对应的饥饿时间阈值时，将该任务添加到饥饿队列。然后判断饥饿队列，若为空，说明没有任务处于饿死状态，则执行正常调度，即在下次调度时间点，从就绪队列中选取下一个任务运行。

若饥饿队列不为空，则判断饥饿队列任务本次连续运行的总时间是否达到了解饿阈值。若达到该阈值，说明此时饥饿队列任务的运行时间过长，需要暂停一下，让就绪队列中的任务有机会运行。因此在下次调度时间点，不能再调度饥饿队列中的任务，而要调度就绪队列中的任务运行。若饥饿队列任务连续运行的总时间未达到解饿阈值，则不必等下个调度点，而是在中断返回之前，就从饥饿队列中选取任务运行。如前文所述，饥饿队列中每个任务每次只允许运行一段比较小的时间片，因此通常不会对就绪队列任务的调度造成较大影响。

解饿阈值的设定，需要以饥饿队列中任务个数的统计信息为依据。如果设置过大，碰到饥饿队列任务很多的情况，就可能导致就绪队列中任务等待时间过长，出现新的任务饿死现象；如果设置过小，可能无法及时将饥饿队列任务全部调度完成，导致饥饿队列一直有任务在，也影响了就绪队列的调度。实际可根据场景需要，动态设置解饿阈值。

对比可知，按本发明的技术方案，每个任务只有唯一的优先级，不会动态改变优先级，比较方便操作系统的管理。其次，饿死的任务在时钟中断返回时，就能马上得到调度执行，不必等待下一个调度时间点，因此能被更及时地调度。另外，饥饿队列中各任务一次运行的时间较少，因此不会对就绪队列的调度产生大的影响。同时，不同优先级任务的饥饿时间阈值、饥饿队列的解饿阈值可动态配置，能灵活满足不同应用场景的需要。

图6所示为根据本发明实施方式的装置图。装置包括存储器100及处理器200，其中处理器200存储有计算机程序，计算机程序用于执行：为CPU中就绪队列中的每个任务添加对应的饥饿时间；当任意任务的饥饿时间达到饥饿阈值时，将其添加至饥饿任务队列；通过调度时钟对进入饥饿任务队列的任务按照优先度进行顺序执行。其中，存储器100用于存储数据。

上面结合附图对本发明实施例作了详细说明，但是本发明不限于上述实施例，在技术领域普通技术人员所具备的知识范围内，还可以在不脱离本发明宗旨的前提下做出各种变化。