[go: up one dir, main page]

CN103309734A - 基于优先级分组的嵌入式任务调度方法 - Google Patents

基于优先级分组的嵌入式任务调度方法 Download PDF

Info

Publication number
CN103309734A
CN103309734A CN2013102503301A CN201310250330A CN103309734A CN 103309734 A CN103309734 A CN 103309734A CN 2013102503301 A CN2013102503301 A CN 2013102503301A CN 201310250330 A CN201310250330 A CN 201310250330A CN 103309734 A CN103309734 A CN 103309734A
Authority
CN
China
Prior art keywords
task
priority
ready
tasks
group
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
CN2013102503301A
Other languages
English (en)
Inventor
高会军
汪超
张世浩
于金泳
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Harbin Institute of Technology Shenzhen
Original Assignee
Harbin Institute of Technology Shenzhen
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Harbin Institute of Technology Shenzhen filed Critical Harbin Institute of Technology Shenzhen
Priority to CN2013102503301A priority Critical patent/CN103309734A/zh
Publication of CN103309734A publication Critical patent/CN103309734A/zh
Pending legal-status Critical Current

Links

Images

Landscapes

  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

基于优先级分组的嵌入式任务调度方法，涉及嵌入式系统中的任务调度领域，解决现有任务调度方法操作繁琐，需要大量的计算过程与存储空间，致使消耗资源大、不便于开发人员理解和修改的问题。包括步骤：将N个任务按优先级进行分组；按照组别优先级由高至低进行检索，并将有就绪任务的最高组别进行检索，获取具有最高优先级的就绪任务作为待切换任务；获取待切换任务信息并执行任务切换。本发明可广泛应用于嵌入式系统的任务调度。

Description

基于优先级分组的嵌入式任务调度方法
技术领域
本发明涉及嵌入式系统中的任务调度领域。
背景技术
随着软硬件的快速发展，现代的嵌入式设备的功能变得日趋强大了。随着嵌入式设备所实现的功能越来越复杂，传统的单任务模型已经无法满足需求，于是在嵌入式设备中实现了操作系统，通过操作系统来统一对资源进行管理，调度各个任务。而对于嵌入式领域，都要求所采用的操作系统满足稳定性好，响应速度快，来应对各种对时间有着严格要求的情况。
任务调度作为嵌入式操作系统的核心之一，主要功能是从多个用户任务中选择一个就绪的任务，然后调转到用户任务执行。嵌入式操作系统中的任务调度一般是基于优先级进行调度，即每个任务会根据其重要程度的不同赋予一个优先级，嵌入式系统中的调度器会选择优先级最高的就绪任务运行。但现有任务调度方法操作繁琐，需要大量的计算过程与存储空间。
发明内容
本发明为了解决现有任务调度方法操作繁琐，需要大量的计算过程与存储空间，致使消耗资源大、不便于开发人员理解和修改的问题，从而提供一种基于优先级分组的任务调度方法。
基于优先级分组的嵌入式任务调度方法，它包括如下步骤：
步骤一：将N个任务按优先级进行分组；所述N个任务按优先级等级进行排序，分为P个优先级组，即每组个优先级；
所述任务进行排序按照优先级的等级从高到底排序或从低到高进行排序；
步骤二：按照组别优先级由高至低进行检索，并将有就绪任务的最高组别进行检索，获取具有最高优先级的就绪任务作为待切换任务；
所述任务通过激活任务和终止任务进行激活和终止，其中：
激活任务，用于激活优先级任务使其成为就绪任务；
终止任务，用于终止就绪任务使其成为未就绪任务；
步骤三：获取待切换任务信息并执行任务切换。
本发明实现了基于优先级分组的嵌入式任务调度。本发明调度效率高、存储空间小、结构简单且适于更改任务较量的嵌入式实时系统的任务调度方法。采用本发明所述方法能够节省一般的搜索时间与查找次数，使能够存储的任务数量无限制。
图1为本发明基于优先级分组的嵌入式任务调度方法的流程图；
图2为具体实施方式三所述执行任务切换的流程图；
图3为具体实施方式四所述激活任务的流程图；
图4为具体实施方式五所述终止任务的流程图；
图5为具体实施例的调度模型示例图。
具体实施方式
具体实施方式一，结合图1说明本具体实施方式。基于优先级分组的嵌入式任务调度方法，它包括如下步骤：
步骤一：将N个任务按优先级进行分组；所述N个任务按优先级等级进行排序，分为P个优先级组，即每组
Figure BDA00003392439400021
个优先级；
所述任务进行排序按照优先级的等级从高到底排序或从低到高进行排序；
步骤二：按照组别优先级由高至低进行检索，并将有就绪任务的最高组别进行检索，获取具有最高优先级的就绪任务作为待切换任务；
所述任务通过激活任务和终止任务进行激活和终止，其中：
激活任务，用于激活优先级任务使其成为就绪任务；
终止任务，用于终止就绪任务使其成为未就绪任务；
步骤三：获取待切换任务信息并执行任务切换。
具体实施方式二、本具体实施方式与具体实施方式一不同的是步骤三：获取待切换任务信息包括任务状态信息、任务上下文信息和任务控制信息；
任务状态信息，用于标识任务的自身信息；
任务上下文信息，用于保存调度过程中的现场信息；
任务控制信息，用于任务的调度和管理；
所述任务状态信息包括任务的优先级、任务的当前状态和任务类型；
所述任务上下文信息包括通用寄存器的内容、控制寄存器的内容、用户堆栈指针和内核堆栈指针；
所述任务控制信息包括任务调度的相关信息、任务间通信的相关信息和任务的资源使用情况信息。
具体实施方式三、结合图2说明本具体实施方式，本具体实施方式与具体实施方式二不同的是步骤三所述执行任务切换过程为：
步骤A1：用于获取任务切换开始信号的步骤；
步骤A2：用于关中断的步骤；
步骤A3：用于保存当前任务上下文信息
步骤A4：用于设置待切换任务为当前任务的步骤；
步骤A5：用于装入待切换任务上下文信息的步骤；
步骤A6：用于打开中断，执行任务切换的步骤。
具体实施方式四、结合图3说明本具体实施方式，本具体实施方式与具体实施方式一或三不同的是激活任务，用于激活优先级任务使其成为就绪任务过程为：
步骤B1：用于获取待激活任务的优先级的步骤；
步骤B2：用于判断任务优先级是否有效的步骤；若是则进入步骤B3，若否则退出过程；
步骤B3：用于将所述任务状态更改为就绪状态的步骤；
步骤B4：用于将所述任务放入优先级队列中的步骤；
步骤B5：用于判断所述任务优先级的编号是否大于其所在组的最高优先级；若是则进入步骤B6，若否则进入步骤B7；
步骤B6：用于更新所述任务所在组的最高优先级编号的步骤；
步骤B7：用于判断当前中断状态的步骤；若处于关中断则退出过程，若处于开中断则进行任务切换。
具体实施方式五、结合图4说明本具体实施方式，本具体实施方式与具体实施方式四不同的是所述终止任务，用于终止就绪任务使其成为未就绪任务过程为：
步骤C1：用于获取终止任务信号的步骤；
步骤C2：用于判断当前中断状态的步骤；若处于关中断则退出过程，若处于开中断则进入C3。
步骤C3：用于设置当前任务为挂起状态的步骤；
步骤C4：用于将当前任务从就绪队列中移出的步骤；
步骤C5：用于判断所述终止任务的优先级的编号是否大于其所在组的最高优先级；若是则进入步骤C6，否则进入步骤C7；
步骤C6：用于更新所述终止任务所在组的最高优先级编号的步骤；
步骤C7：用于进行任务切换的步骤。
本发明执行任务切换的平均代价为
Figure BDA00003392439400041
执行一次激活任务时的代价为一次比较操作，执行一次终止任务的平均代价为
Figure BDA00003392439400042
可知，系统进行调度任务所花费的总的代价为
Figure BDA00003392439400043
且当时，调度所花费的代价最小，而且随着系统中任务数量的减小，任务调度所需的代价减小。
结合图5说明具体实施例：
假设将任务按优先级进行编号，从0到63，编号越大，优先级越高，按编号从小到大将为8组，每组8个优先级。系统运行的某一时刻，优先级组7中就绪任务有56，57，58，59，其中就绪的最高优先级是59，优先级组6中没有就绪的优先级，然后依次确定每组的就绪任务中最高的优先级。
当系统中任务定时中断发生时，首先判断是否有就绪的任务，当没有就绪任务的情况下，运行空闲任务，当存在就绪任务时，开始选择具有最高优先级的任务。从优先级组高到低依次查看组中是否有就绪的任务。优先级组7中就绪的最高优先级是59.于是选择59为当前就绪的最高任务优先级号，根据任务调度相关机构找到59号任务的任务控制模块，调度器进行任务切换，开始执行59号任务定义的用户程序。
当激活一个任务优先级为43号任务时，43号任务属于优先级组5，原先优先级组5中最高优先级为42号任务，而此时43号任务比42号任务的优先级大，具有更高的优先级，于是更新优先级组5最高就绪优先级任务编号更新为43号。而当激活一个任务优先级为26号任务时，26号任务属于优先级组3，原优先级组3中最高优先级为31号任务，此时26号任务的优先级比31号任务优先级小，于是不更新优先级表。
当终止一个任务优先级为42的任务时，42号任务属于优先级组5，原先优先级组5中最高优先级为42号任务，此时终止的42号任务为优先级组5中最高优先级任务，此时需要找出本组中剩余就绪任务中具有最高优先级的任务，于是更新优先级组5最高就绪优先级任务编号。
把本发明基于优先级分组的嵌入式任务调度方法与μC/OS-II的调度算法进行比较：μC/OS-II是嵌入式领域一款优秀的操作系统，尤其在调度算法受人称道。由于μC/OS-II只支持64个固定优先级数目，所以在基于优先级分组的算法中将取N＝64，P＝8，比较结果如下：
Figure BDA00003392439400051
从对比可以看出，相比μC/OS-II调度算法，基于优先级分组调度算法节省了很大的空间，并且获得了很高的灵活性，而付出的时间代价确很少。而且在实际的应用中，使用的优先级数目一般不会超过64个，所以基于优先级分组的调度算法性能会非常的好。

Claims (5)

1.基于优先级分组的嵌入式任务调度方法，其特征在于它包括如下步骤：
步骤一：将N个任务按优先级进行分组；所述N个任务按优先级等级进行排序，分为P个优先级组，即每组
Figure FDA00003392439300011
个优先级；
所述任务进行排序按照优先级的等级从高到底排序或从低到高进行排序；
步骤二：按照组别优先级由高至低进行检索，并将有就绪任务的最高组别进行检索，获取具有最高优先级的就绪任务作为待切换任务；
所述任务通过激活任务和终止任务进行激活和终止，其中：
激活任务，用于激活优先级任务使其成为就绪任务；
终止任务，用于终止就绪任务使其成为未就绪任务；
步骤三：获取待切换任务信息并执行任务切换。
2.根据权利要求1所述的基于优先级分组的任务调度方法，其特征在于步骤三：获取待切换任务信息包括任务状态信息、任务上下文信息和任务控制信息；
任务状态信息，用于标识任务的自身信息；
任务上下文信息，用于保存调度过程中的现场信息；
任务控制信息，用于任务的调度和管理；
所述任务状态信息包括任务的优先级、任务的当前状态和任务类型；
所述任务上下文信息包括通用寄存器的内容、控制寄存器的内容、用户堆栈指针和内核堆栈指针；
所述任务控制信息包括任务调度的相关信息、任务间通信的相关信息和任务的资源使用情况信息。
3.根据权利要求2所述的基于优先级分组的任务调度方法，其特征在于步骤三所述执行任务切换过程为：
步骤A1：用于获取任务切换开始信号的步骤；
步骤A2：用于关中断的步骤；
步骤A3：用于保存当前任务上下文信息
步骤A4：用于设置待切换任务为当前任务的步骤；
步骤A5：用于装入待切换任务上下文信息的步骤；
步骤A6：用于打开中断，执行任务切换的步骤。
4.根据权利要求1或3所述的基于优先级分组的任务调度方法，其特征在于激活任务，用于激活优先级任务使其成为就绪任务过程为：
步骤B1：用于获取待激活任务的优先级的步骤；
步骤B2：用于判断任务优先级是否有效的步骤；若是则进入步骤B3，若否则退出过程；
步骤B3：用于将所述任务状态更改为就绪状态的步骤；
步骤B4：用于将所述任务放入优先级队列中的步骤；
步骤B5：用于判断所述任务优先级的编号是否大于其所在组的最高优先级；若是则进入步骤B6，若否则进入步骤B7；
步骤B6：用于更新所述任务所在组的最高优先级编号的步骤；
步骤B7：用于判断当前中断状态的步骤；若处于关中断则退出过程，若处于开中断则进行任务切换。
5.根据权利要求4所述的基于优先级分组的任务调度方法，其特征在于所述终止任务，用于终止就绪任务使其成为未就绪任务过程为：
步骤C1：用于获取终止任务信号的步骤；
步骤C2：用于判断当前中断状态的步骤；若处于关中断则退出过程，若处于开中断则进入C3。
步骤C3：用于设置当前任务为挂起状态的步骤；
步骤C4：用于将当前任务从就绪队列中移出的步骤；
步骤C5：用于判断所述终止任务的优先级的编号是否大于其所在组的最高优先级；若是则进入步骤C6，否则进入步骤C7；
步骤C6：用于更新所述终止任务所在组的最高优先级编号的步骤；
步骤C7：用于进行任务切换的步骤。
CN2013102503301A 2013-06-24 2013-06-24 基于优先级分组的嵌入式任务调度方法 Pending CN103309734A (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN2013102503301A CN103309734A (zh) 2013-06-24 2013-06-24 基于优先级分组的嵌入式任务调度方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN2013102503301A CN103309734A (zh) 2013-06-24 2013-06-24 基于优先级分组的嵌入式任务调度方法

Publications (1)

Publication Number Publication Date
CN103309734A true CN103309734A (zh) 2013-09-18

Family

ID=49134992

Family Applications (1)

Application Number Title Priority Date Filing Date
CN2013102503301A Pending CN103309734A (zh) 2013-06-24 2013-06-24 基于优先级分组的嵌入式任务调度方法

Country Status (1)

Country Link
CN (1) CN103309734A (zh)

Cited By (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN103914346A (zh) * 2013-12-16 2014-07-09 西北工业大学 一种基于分组的实时操作系统双优先级任务调度节能方法
CN104750556A (zh) * 2015-04-14 2015-07-01 浪潮电子信息产业股份有限公司 一种hpc集群作业调度方法及装置
WO2016165467A1 (zh) * 2015-09-16 2016-10-20 中兴通讯股份有限公司 基于业务流的任务调度方法及装置
CN107291542A (zh) * 2017-06-27 2017-10-24 北京优特捷信息技术有限公司 一种智能执行检索任务的方法及装置
CN109408208A (zh) * 2018-09-21 2019-03-01 深圳华大北斗科技有限公司 导航芯片的多任务处理方法、设备、系统以及存储介质
CN118025049A (zh) * 2024-04-15 2024-05-14 成都创科升电子科技有限责任公司 一种基于调度器的车辆电控件的控制方法、系统及车辆

Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2003186685A (ja) * 2001-09-21 2003-07-04 Lg Electronics Inc 実時間処理システムの過負荷制御方法
CN1490722A (zh) * 2003-09-19 2004-04-21 清华大学 基于PowerPC处理器结构的分级任务切换方法
CN101178664A (zh) * 2007-12-12 2008-05-14 北京中星微电子有限公司 实时操作系统中的任务调度方法及系统
CN102043667A (zh) * 2010-11-25 2011-05-04 深圳市科陆电子科技股份有限公司 一种嵌入式操作系统的任务调度方法
CN102063325A (zh) * 2011-01-06 2011-05-18 哈尔滨工业大学 一种嵌入51系列单片机的多任务实时操作系统的实现方法

Patent Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2003186685A (ja) * 2001-09-21 2003-07-04 Lg Electronics Inc 実時間処理システムの過負荷制御方法
CN1490722A (zh) * 2003-09-19 2004-04-21 清华大学 基于PowerPC处理器结构的分级任务切换方法
CN101178664A (zh) * 2007-12-12 2008-05-14 北京中星微电子有限公司 实时操作系统中的任务调度方法及系统
CN102043667A (zh) * 2010-11-25 2011-05-04 深圳市科陆电子科技股份有限公司 一种嵌入式操作系统的任务调度方法
CN102063325A (zh) * 2011-01-06 2011-05-18 哈尔滨工业大学 一种嵌入51系列单片机的多任务实时操作系统的实现方法

Cited By (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN103914346A (zh) * 2013-12-16 2014-07-09 西北工业大学 一种基于分组的实时操作系统双优先级任务调度节能方法
CN104750556A (zh) * 2015-04-14 2015-07-01 浪潮电子信息产业股份有限公司 一种hpc集群作业调度方法及装置
WO2016165467A1 (zh) * 2015-09-16 2016-10-20 中兴通讯股份有限公司 基于业务流的任务调度方法及装置
CN106547611A (zh) * 2015-09-16 2017-03-29 中兴通讯股份有限公司 基于业务流的任务调度方法及装置
CN107291542A (zh) * 2017-06-27 2017-10-24 北京优特捷信息技术有限公司 一种智能执行检索任务的方法及装置
CN107291542B (zh) * 2017-06-27 2020-09-15 北京优特捷信息技术有限公司 一种智能执行检索任务的方法及装置
CN109408208A (zh) * 2018-09-21 2019-03-01 深圳华大北斗科技有限公司 导航芯片的多任务处理方法、设备、系统以及存储介质
CN109408208B (zh) * 2018-09-21 2022-04-01 深圳华大北斗科技股份有限公司 导航芯片的多任务处理方法、设备、系统以及存储介质
CN118025049A (zh) * 2024-04-15 2024-05-14 成都创科升电子科技有限责任公司 一种基于调度器的车辆电控件的控制方法、系统及车辆

Similar Documents

Publication Publication Date Title
US9632822B2 (en) Multi-core device and multi-thread scheduling method thereof
CN104156264B (zh) 一种基于多gpu的基带信号处理任务并行实时调度方法
US8423799B2 (en) Managing accelerators of a computing environment
US9858115B2 (en) Task scheduling method for dispatching tasks based on computing power of different processor cores in heterogeneous multi-core processor system and related non-transitory computer readable medium
CN103309734A (zh) 基于优先级分组的嵌入式任务调度方法
KR20180053359A (ko) 다중-버전형 태스크들의 효율적 스케줄링
CN104199730B (zh) 一种基于同步i/o复用机制的单线程多任务处理方法
CN105893263B (zh) 一种测试任务调度方法
CN101887383B (zh) 一种进程实时调度方法
CN104199739B (zh) 一种基于负载均衡的推测式Hadoop调度方法
CN104536827A (zh) 一种数据调度方法和装置
CN102043667A (zh) 一种嵌入式操作系统的任务调度方法
US20150121387A1 (en) Task scheduling method for dispatching tasks based on computing power of different processor cores in heterogeneous multi-core system and related non-transitory computer readable medium
CN103064736B (zh) 任务处理装置及方法
CN102541642B (zh) 一种增强实时性能的任务管理方法
CN103488536B (zh) 任务调度方法、装置及操作系统
CN113495780A (zh) 任务调度方法、装置、存储介质及电子设备
CN103677997B (zh) 多核心装置以及其多线程调度方法
KR100959548B1 (ko) 인터럽트 스케줄링 방법
TW201541347A (zh) 多核心處理器系統及其排程方法
TW202101211A (zh) 中斷處理系統與中斷處理方法
CN103914346A (zh) 一种基于分组的实时操作系统双优先级任务调度节能方法
CN101968749B (zh) 虚拟机过度分配环境下的mpi消息接收方法
EP4035016B1 (en) Processor and interrupt controller therein
WO2024021475A1 (zh) 一种容器调度方法及装置

Legal Events

Date Code Title Description
C06 Publication
PB01 Publication
C10 Entry into substantive examination
SE01 Entry into force of request for substantive examination
C02 Deemed withdrawal of patent application after publication (patent law 2001)
WD01 Invention patent application deemed withdrawn after publication

Application publication date: 20130918