一种多核实时操作系统多个就绪任务快速查找及调度方法

摘要

本发明公开一种多核实时操作系统就绪任务快速查找及调度方法，涉及计算机技术领域，本发明提出基于任务就绪表的多就绪高优先级任务快速查找方法，解决多核实时操作系统中就绪任务快速查找；基于有序表的可调度任务和可抢占内核查找方法，查找调度内核和快速调度任务到指定的内核；通过基于核间中断消息的核间调度请求的方法，内核在不需要重新查找就续表的情况下快速运行高优先级任务，解决实时多核系统中多高优先级就绪任务快速响应问题。基于事件触发同一优先级多任务调度，针对实时嵌入式系统中的同步任务组实时性要求，设计一种同一优先级多任务实现方法，解决实时系统中同步任务组的并行调度问题。

说明书

技术领域

本发明涉及嵌入式系统多核实时操作系统调度技术领域。

背景技术

随着微电子技术的发展，对称同构多核处理器(SMP-symmetrical  multi-processingprocessor)被广泛应用于嵌入式系统领域。随着信息技术， 尤其是通信技术和物联网技术的发展，实时嵌入式系统已经成为计算机系统的 主流。未来实时嵌入式系统的一个显著趋势就是应用复杂度将不断提高。例如 在通信领域，无论实在通信基础设施，还是在终端设备中，运算需求都在不断 提高。而这类系统对时间可预测性、高可信、低功耗等方面的苛刻要求也从未 降低。还有车联网领域，特别是智能车辆的发展，车辆互联及通信是未来车联 网的发展趋势。车载终端不仅需要处理车联网信息、车载媒体信息，还需要实 时处理车辆自身的传感信息，如视频监控、控制等。要同时完成如此多的功能， 满足实时性要求，传统的单核处理器已经无法解决上述矛盾。多核处理器在一 个芯片上集成多个处理核心，通过挖掘应用的任务级并行性和数据级并行性， 能够在单位功耗和体积上，提供更大的计算能力。因此，多核处理器应用于未 来的实时系统已经成为不可逆转的趋势。

随着多核处理器的发展，对软件开发有非常大的影响，而且核心的瓶颈在软件 上。只有与多核硬件相适应的软件，才能真正地发挥多核的性能。多核对软件 的要求包括对多核操作系统的要求和对应用软件的要求，特别是多核操作系统 的性能。在嵌入式系统中,随着多核处理器应用的日益广泛,一些主流的嵌入式 系统厂商也逐渐开始提供一些基于多处理器构架的实时操作系统解决方案。为 了充分利用处理器的性能，有很多嵌入式操作系统也提供了多核管理与调度的 功能，如Linux、Vxworks、QNX等操作系统。

多核嵌入式操作系统构架设计主要有两种：一种是主从式构架结构，另一种是 对称式构架结构。主从式多核操作系统根据多核处理器的功能把内核分成主核 和从核，由于从核中只有局部调度器，需要向主核请求处理，任务的激活与运 行需通过主核来进行调控，由主核决定任务的分配。这种结构的操作系统容易 造成从核在等待主核指令的过程中时间的浪费，降低了任务调度的实时性；同 时这种结构随着处理器核的增加，要求主核管理的资源、任务调度、事件处理、 通信管理等对象也增多，主核负载的增加，将导致主核不能实时有效处理这些 事件，成为性能提高的瓶颈。而对称式构架是采用相同的结构来设计操作系统， 每个处理器核中访问同一个操作系统内核，特别是在内核任务通信与同步、共 享资源管理等部分。这种结构的操作系统由于结构较单一，便于系统设计实现。 但是由于多个处理器访问同一个内核，需要互斥等待访问内核，降低了内核的 访问速度。

嵌入式实时操作系统对调度时间、任务响应速度都有较高的要求。就绪任 务，特别是实时性要求较高的任务要求较短的时间内的得到响应和调度。这就 要求调度算法具有简单快速的特点。当前支持多核处理器的实时操作系统并不 是很多，以Vxworks、QNX较为典型。Vxworks和QNX操作系统对SMP处理器的支持， 采用一个操作内核对多个处理器核进行管理，采用自旋锁防止访问冲突，这种 结构会造成多核处理器的访问内核时的互斥，降低了内核访问的并行性，从而 降低了多核的性能。随着处理器技术和存储器技术的发展，存储空间对于实时 操作系统来说不再是主要考虑的问题。

在多核实时操作系统中，多就绪任务的查找在高优先级任务的选择方法是 调度器设计的重点之一，如何快速的查找到就绪任务，触发调度内核的快速响 应并及时调度是多核实时操作系统调度器设计的重点。当前支持多核的嵌入式 操作系统大多采用主从式加队列的方式进行的，由一个主核管理整个系统任务， 在各个从核中建立局部队列。主核根据从核的负载情况动态地分配任务到从核 队列中，供从核运行。这种方法只适合于一般的非实时系统。对于实时操作系 统来说，需要快速响应优先级较高的任务，尽量减少等待时间。对于当前多核 实时操作系统的高优先级就绪任务查找方法，虽然大多算法复杂度为O(1)。但是 在查找过程中的实现步骤较多，随着任务的增加，其查找时间也随之上升。这 种方法对于一个要求较高的实时系统来说，调度时间具有不确定性。

同时，当前嵌入式操作系统支持的相同优先级多任务的方式都是基于时间 片方式，如Linux、Vxworks等。这种方法对于同一优先级任务的并行分时执行 可以达到很好的效果。但是对于实时系统来说，特别是多核处理器在实时系统 中的应用，以前不能并行处理的多任务同步就是通过事件来触发任务调度的。 这种方法没有考虑实时多核系统中同步任务组并行执行要求，特别是在机器人、 数控机床、发动机控制等领域中，常存在多种任务组，每个任务组基本上是由 外部事件触发调度，实时性要求高。这类任务可以在多核中得到并行执行。如 果采用时间轮转调度，达不到实时同步的效果。

发明内容

为了解决多核实时系统中单一操作系统内核并行访问的互斥和延迟问题， 本发明采用多主内核的操作系统架构。在这种架构中，每个内核都可以作为主 核对全局任务进行调度，每个处理器核访问属于自己的内核代码，不需要自旋 锁来防止内核访问冲突，有效地实现负载均衡、快速内核访问和任务的实时响 应问题。这种架构虽然不能解决总线访问的等待问题，但可以有效解决同一内 核访问的互斥等待问题。在此基础上，本发明设计了实时多核系统中多任务选 择及调度方法，实现任务的快速调度；并设计了一种基于事件触发调度的同一 优先级多任务调度算法，解决同步任务并行调度问题。

本发明解决上述技术问题的技术方案，提出一种基于多主调度模式的多核 实时操作系统就绪任务快速查找及调度方法，设置基于位图的任务就绪表表示 多核任务就绪状态，多个内核共同维护该任务就绪表，当多核任务运行时在任 务就绪表中的状态仍然为就绪状态。同时，本发明还设置了一个高优先级任务 就绪表用来存储下一次将要运行的高优先级任务，用内核-任务映射表保存当前 运行任务与内核的对应关系。每个内核在任务就绪表中一次性查找与内核个数 相同的高优先级就绪任务，在任务就绪表中读取就绪任务优先级，删除在任务 就绪表中该就绪任务优先级对应位的有效值，以内核个数相同的次数查找到与 内核个数相同的优先级任务顺序存储在高优先级任务就绪表中；多内核维护一 个任务就绪表，OS内核根据算法从高优先级任务就绪表与内核-任务映射表中找 出没有在内核-任务映射表中的高优先级任务作为调度任务和没有在高优先级任 务就绪表中的当前运行任务所在的内核作为被抢占内核，通过核间中断主动触 发相应的内核调度指定高优先级任务运行。为了解决同一优先级支持多个同步 任务，本发明通过设置一个结构体定义任务优先级，主要包括基本优先级核优 先级偏移量，优先级偏移量的值作为相同优先级的任务的次优先级。当任务就 绪表中基本优先级对应位有效时，通过查找基本优先级对应的优先级偏移量， 实现多核对同优先级同步多任务调度。

采用多主多OS内核结构，所有内核维护同一个任务调度列表及任务就绪表， 每个内核作为主核对任务就绪表进行修改，通过查表快速读取与内核个数相同 的就绪任务优先级值；比较读取的就绪任务优先级值与保存的当前运行任务优 先级值，获取需要调度的任务优先级和可以抢占的内核；内核寻找可调度任务 和可抢占内核，通过核间通信以消息的形式通知指定的内核调度指定的任务； 针对同步任务组根据基本优先级加优先级偏移量，基于事件触发调度同一优先 级多任务对应同一基本任务。所述通过查表快速读取与内核个数相同的就绪任 务优先级值具体为：拷贝基于位图的就绪表到指定的变量中，每查找一个高优 先级任务后，删除变量中已找到的优先级对应的位，再查找剩余就绪任务优先 级值，直至所有就绪任务优先级值查找完成。所述获取需要调度的任务优先级 和可以抢占的内核具体包括：建立“高优先级任务就绪表”和“内核-任务映射 表”两个优先级有序表按照优先级顺序分别存储当前查找到的高优先级任务的 优先级和当前运行任务优先级以及所在的内核编号，从高优先级任务就绪表中 取出一个任务，在内核-任务映射表中查找该任务是否已经运行，并以上一次查 找到的已运行任务优先级为起点开始查找下一个已经运行的任务优先级，逐步 减少查找次数，找出需要调度的任务和可以抢占内核。主核在找到需要调度的 任务及可以抢占的内核后，通过核间中断以消息的形式把需要调度的任务优先 级传送给指定抢占内核，主动触发指定内核快速调度运行指定的高优先级任务。 调度同一优先级多任务对应同一基本任务具体包括：在基本优先级中添加一个 优先级偏移量表示多个任务优先级，每个任务对应偏移量中一位。基于事件触 发的调度方法具体包括：根据优先级偏移量设置一个优先级多任务就绪变量记 录偏移量优先级对应任务的就绪状态，采用事件触发调度触发多任务调度同一 优先级对应的多个就绪任务。

多内核维护一个任务就绪表具体包括：每个处理器内核在内存中维护一个 操作系统内核镜像，同时维护本地内核相关的数据结构，在内核启动时只拷贝 本地内核相关的数据结构到指定的区域，所有内核访问共享数据结构时通过全 局自旋锁互斥访问，获得任务就绪表读写控制权的内核访问该全局任务就绪表， 通过自旋锁进行互斥，所有内核访问共同的任务代码，每个内核只能访问一个 任务代码，同时，每个内核维护一组本地的系统任务；所有内核维护一个共享 事件列表，一个内核通过事件列表读取和接收相应的事件；所有内核共同维护 一个“内核-任务映射”表，内核-任务映射表用于维护记录运行任务与内核的 关系。内核在调度任务时，把当前任务记录在该映射表中，在任务抢占时，内 核通过该映射表查找抢占的任务，在多内核镜像处理中，每个内核维护一个内 核本身的数据结构。设置位图式就绪表表示多核任务就绪状态具体包括：首先 设置一个与内核个数相等的数组作为高优先级就绪表存储高优先级；设置两个 临时变量分别用于存储高优先级就绪表的行和行对应列的值，然后拷贝高优先 级就绪表对应的行值到一个变量中；设置两个查找表，一个用来查找高优先级 任务行和列对应的值，一个用来查找行对应的位，查找查找表获得高优先级任 务对应的行值，将该行的值拷贝到局部变量中。对多主模式操作系统架构，采 用两个有序表分别存储当前查找到的高优先级任务的优先级，当前运行任务优 先级以及所在的内核编号，逐次比较方法找出需要调度的任务和可以抢占内核。 主核可以通过核间中断主动触发指定内核在不需要重新查找就绪表的情况下调 度运行新的高优先级任务，通过消息把需要调度的任务优先级及入口地址传送 给调度核

本发明技术方案中，基于就绪表的多就绪任务快速查找方法包括：（1）基 于任务就绪表的多就绪高优先级任务快速查找，只需要内核个数相同循环次数 就可以快速查找与内核相同个数的高优先级任务，解决多核实时操作系统中需 要调度的就绪任务快速查找问题。（2）基于有序表的可调度任务和可抢占内核 查找，针对实时嵌入式系统要求，在多主模式操作系统架构基础上，本发明设 计了一个高优先级就绪任务表用于保存当前查找到的高优先级任务的优先级， 同时还设计了内核-任务映射备份表按照任务优先级顺序保存当前运行任务优先 级以及所在的内核编号。根据高优先级任务就绪表和内核-任务映射表的任务优 先级的差异性，快速找出需要调度的任务和可以抢占内核。（3）基于核间中断 消息的核间调度请求，主核可以通过核间中断主动触发指定内核在不需要重新 查找就绪表的情况下快速调度运行新的高优先级任务，通过消息把需要调度的 任务优先级及入口地址等信息传送给调度核。解决实时多核系统中多高优先级 就绪任务调度快速响应问题。（4）基于事件触发同一优先级多任务调度，针对 实时嵌入式系统中的同步任务组实时性要求，设计一种同一优先级对应多任务 实现方法，并设计了基于事件触发的调度方法，解决实时系统中同步任务组的 并行调度问题。

本发明能有效地实现多核任务调度的就绪任务快速查找，任务调度的快速 响应，有效解决同步任务在多核中的快速调度问题。

附图说明

图1多主模式多核实时操作系统架构；

图2支持64个任务的任务就绪表位图示意；

图3多核中多就绪任务、可用内核查找及调度方法示意图。

具体实施方式

针对大多数同构多核处理器而言，没有自己独立的内存，数据和程序共享。 如何实现这些程序和数据的有效共享是多核操作系统的设计关键。由于是共享 内存和flash结构，为了避免访问的冲突，将存储空间划分为几个区域，每个区 域设定一个访问权限，规定访问的内核。

现在处理器的存储空间越来越大，存储空间对实时操作系统来说不是问题。 本发明中的操作系统内核架构总体上采用对称多主内核结构。在该架构中，每 个内核运行一个内核的镜像，而其他的功能如图形用户接口（GUI）、文件系统 (FS)、人机交互组件可以作为一个独立任务指定由不同的内核执行，避免这些功 能来回调度，而任务、系统启动、驱动等模块是共享模块。或者由主核负责管 理，其他处理器核都有一个操作系统OS内核的拷贝，这样可以避免同时访问同 一个内核排队的问题。这些OS内核共同维护全局任务队列和全局数据结构。整 个结构示意图如附图1所示。

在多主多核操作系统中，在系统启动时，拷贝多个OS内核镜像，每个处理器核 都可以通过访问自己的OS内核以主核的方式管理系统资源，实现任务的主动调 度，如附图1所示。OS内核个数多少是根据应用的具体要求进行配置的，可以 多个处理器核访问一个OS内核，也可以一个OS内核对应一个处理器核。除OS 内核外，其他软件（如GUI、FS、Drivers等）都可以作为共享资源来进行访问， 可以动态分配或者调度到不同的内核上运行，使各个核上的负载更加均衡。每 个OS内核都可以作为主内核进行全局资源管理和应用任务的调度，程序运行在 处理器核时，访问属于自己的那个OS内核，减少与其他处理器核发生访问冲突， 同时也减少了处理器核访问OS内核时的等待时间。

本发明申请的多主模式，在结构上采用多个OS内核维护一个全局任务列表。每 个OS内核在完成通信、互斥、同步或者中断等操作后均查看任务就绪表，按照 本发明提供的任务查找算法和调度方法进行任务调度，如果存在新的高优先级 就绪任务，则会主动触发其他内核在不用查找高优先级任务的情况下，快速调 度新的高优先级任务运行。解决多内核实时任务的被动调度和负载均衡问题， 提高系统实时性。具体实施步骤如下。

1.基于任务就绪表的多就绪高优先级任务快速查找方法 在多核实时操作系统中，为了保证实时性，需要快速查找和选择高优先级 就绪任务抢占低优先级任务运行。主要包括两个方面：基于任务就绪表的多个 高优先级就绪任务查表选择和被抢占任务快速选择。本发明采用基于位图的任 务就绪表，设计一种根据任务就续表中的值然查表的多高优先级任务快速查找 方法。该方法通过内核个数相同次数快速查找与内核相同个数的优先级任务用 于调度。解决多核实时操作系统中就绪任务快速查找问题。

在单核操作系统中，高优先级任务可以通过位图方式设置任务优先级在任 务就绪表对应位为1来表示该任务就绪，设置为0的方式来表示该优先级任务 移除任务就绪表。本发明采用上述方法设置和移除任务的就绪位。运行任务的 就绪状态直到任务被挂起、退出或者删除时，才会从任务就绪表中移除。在此 基础上，本发明根据实时嵌入式系统的要求，设计一种快速查找与内核个数相 同的高优先级就绪任务优先级的方法。实施方式描述如下：

和单核处理器不同，在多核的多主模式中，每次最多可以选择内核个数相 等的任务调度抢占内核运行任务。根据多主调度模式要求，每个内核都可以作 为主核负责任务的调度，主核可以通知其他内核调度指定的任务。因此，内核 需要一次读取内核个数相同的高优先级就绪任务优先级。在查找过程中，为了 快速获得高优先级就绪任务的优先级，并且不重复读取任务就绪表和影响任务 就绪表的值，采用变量来拷贝任务就绪表的行和列对应值，然后通过查表方法 获取高优先级对应的行和列。事先计算任务就绪表行和列每个值对应的高优先 级的行和列值，存放到一个行和列值的查找表中，首先根据就绪表的行值查找 任务就绪表的高优先级所在的行号，然后在该行查找高优先级任务所在的列。

本发明中设置优先级越高时，其编号也越小。把就绪表位分别一个变量和一 个一维维数组表示，变量的每一位表示就绪表对应的行的状态，如果某一位为1 表示该位对应的这一行中至少有一个任务处于就绪；如果为0表示该位对应的 行没有处于就绪的任务。而一维数组用于表示某一行对应的列位，同样，当这 个一维数组的某个元素的某一列对应位为1时，表示该位对应的优先级任务就 绪，如果为0表示该任务处于非就绪状态。调度器就是通过这个就绪表来对任 务就绪状态进行设置的。当查找高优先级就绪任务时，先查找高优先级任务所 在的行，然后根据行号查找高优先级任务所在的列，通过行和列找到优先级任 务的优先级。假设操作系统支持的任务个数为2ⁿ，其中n为偶数。设某一任务 优先级所在的行和列分别为a、b，则任务优先级可以用公式（1）表示。

Prio=a<<(n/2)+b(1)

为了减少获取最高优先级的计算时间，我们事先计算出各种情况的优先级 值，然后采用查表方法获得行a和列b，再计算得到优先级值。我们设定优先级 支持的个数为2n，把就绪表中行值用OSRdyX表示，OSRdyX中每一位对应于 该行是否存在就绪的任务，如果为1表示存在就绪任务，如果为0表示不存在 就绪任务。就绪表某一行i对应的列值用OSRdyY[i]表示，每一位对应于该列是 否存在就绪的任务，如果为1表示列对应的任务就绪，如果为0表示该任务不 就绪。如附图2所示支持64个任务就绪表位图示意。如公式（2）所示，改变i 或者j的值，使行值OSRdyX除以2ⁱ或者列值OSRdyY[i]除以2^j等于奇数，i或 j为优先级所对应行或列的查表值，而OSRdyX或OSRdyY[i]为查表值所对应表 的index号，即位置编号。

其中OSRdyX＝a_n/2-1·2^n-1+a_n/2-2·2^n-2+…+a₀·2^n/2，a_i取0或 1,；OSRdyY[i]=b_n/2-1·2^n/2-1+b_n/2-2·2^n/2-2+…+b₀·2⁰，b_j取0或1。其中 i，j∈[0，n/2-1].

查找表建立后，就可以OSRdyX的值在查找表中直接查找到高优先级任务所在行 a，然后根据OSRdyY[a]的值在查找表中查找到高优先级所对应的列b的值，最 后根据公式（1）就可以得到高优先级任务的优先级。

根据该方法可以计算出行和列对应的查表值，然后把该值写入对应的查找 表，就绪表每一行或每一列对应共有个值。实例1是一个n=6时，根据公式

（2）计算出的查找表，其每行或每列对应256个值。

实例1：多个高优先级就绪任务查找表，OSUnMapTbl可用于查找就绪表中 最高优先级的行和列值。

INT8UconstOSUnMapTbl[256]={

0u,0u,1u,0u,2u,0u,1u,0u,3u,0u,1u,0u,2u,0u,1u,0u,/*0x00to0x0F*/

4u,0u,1u,0u,2u,0u,1u,0u,3u,0u,1u,0u,2u,0u,1u,0u,/*0x10to0x1F*/

5u,0u,1u,0u,2u,0u,1u,0u,3u,0u,1u,0u,2u,0u,1u,0u,/*0x20to0x2F*/

4u,0u,1u,0u,2u,0u,1u,0u,3u,0u,1u,0u,2u,0u,1u,0u,/*0x30to0x3F*/

6u,0u,1u,0u,2u,0u,1u,0u,3u,0u,1u,0u,2u,0u,1u,0u,/*0x40to0x4F*/

4u,0u,1u,0u,2u,0u,1u,0u,3u,0u,1u,0u,2u,0u,1u,0u,/*0x50to0x5F*/

5u,0u,1u,0u,2u,0u,1u,0u,3u,0u,1u,0u,2u,0u,1u,0u,/*0x60to0x6F*/

4u,0u,1u,0u,2u,0u,1u,0u,3u,0u,1u,0u,2u,0u,1u,0u,/*0x70to0x7F*/

7u,0u,1u,0u,2u,0u,1u,0u,3u,0u,1u,0u,2u,0u,1u,0u,/*0x80to0x8F*/

4u,0u,1u,0u,2u,0u,1u,0u,3u,0u,1u,0u,2u,0u,1u,0u,/*0x90to0x9F*/

5u,0u,1u,0u,2u,0u,1u,0u,3u,0u,1u,0u,2u,0u,1u,0u,/*0xA0to0xAF*/

4u,0u,1u,0u,2u,0u,1u,0u,3u,0u,1u,0u,2u,0u,1u,0u,/*0xB0to0xBF*/

6u,0u,1u,0u,2u,0u,1u,0u,3u,0u,1u,0u,2u,0u,1u,0u,/*0xC0to0xCF*/

4u,0u,1u,0u,2u,0u,1u,0u,3u,0u,1u,0u,2u,0u,1u,0u,/*0xD0to0xDF*/

5u,0u,1u,0u,2u,0u,1u,0u,3u,0u,1u,0u,2u,0u,1u,0u,/*0xE0to0xEF*/

4u,0u,1u,0u,2u,0u,1u,0u,3u,0u,1u,0u,2u,0u,1u,0u/*0xF0to0xFF*/

};

在多个优先级任务查找过程中，每一行中可能存在多个高优先级任务，因 此需要重复多次查询行中的高优先级。先根据行的值查找就绪表的高优先级所 在的行号a，然后在该行查找到高优先级任务所做的列b。通过公式（1）进行 优先级计算，这样就可以得到一个高优先级就绪任务的优先级。这样可以保证 每次高优先级就绪任务的查找时间相同，提高操作系统的稳定性。

具体查找过程描述如下：

为了在查找过程不影响任务就绪表的值，首先设置两个临时变量分别用于存 储任务就绪表的行和行对应列的值，然后拷贝任务就绪表对应的行值OSRdyX 到行变量中，然后通过查表找到高优先级任务所在行i；其次拷贝OSRdyY[i]到 列变量中，通过查表得到高优先级任务所在列j。

为了快速查找其他高优先级就绪任务，每一次查找完成后，设置行对应的 列变量中已经查找到的高优先级对应的列对应的位为0，表示该优先级已经查找 了，如果该行全部查找完成，则该行对应的行变量的位的值为0，表示该行已经 查找完，防止下一次重复查找到相同行的任务。这样，每查找到一个任务就从 就绪表对应的变量中删除相应的位，直到查找到内核个数相同的高优先级任务。 每查找一次，重新读取变量中高优先级所在的行和列值，跳过没有就绪任务的 位，直接读取出高优先级对应的行和列号，减少查找次数，达到快速查找的目 的。该方法总的查找次数与内核个数相同。

就绪任务查找算法具体实施步骤如下：

1）首先设计一个与内核个数相等的数组作为高优先级就绪表用以存储高优先 级，设计两个变量分别用于存储就续表的行和行对应列的值；

2）拷贝就绪表中的行变量到行变量；

3）通过查表获取最高优先级就绪任务所在行号；

4）比较行号是否超出范围，如果没有则进入下一步；

5）拷贝就绪表中对应的列变量到列变量；

6）通过查表获取该行最高优先级就绪任务所在列号；

7）从最高优先级所在的列开始查找；

8）计算通过查找到的行和列值计算优先级值，并存储在高优先级就绪表中；

9）高优先级就绪任务计数器加1；

10）比较高优先级任务数如果已经读满，如果已经读满，则退出循环，进入步 骤15），否则进入下一步；

11）置已经读取的列变量中对应的位为0，删除列变量中就绪状态；

12）比较当前列对应的局部变量是否为0，如果为0表示该列已经查找结束，跳 出循环，进入步骤13），否则进入步骤6）继续查找；

13）如果已经读满，则退出循环，进入步骤15，否则进入下一步；

14）置已经读取的行在行变量中对应的位为0，删除行变量中就绪状态，跳转至 步骤3）；

15）查找结束。

从整个步骤可以看出，该查找算法简单，通过查表方法查找任务只需要执 行内核个数相同的次数，查找次数不会因为任务增加而增加，查找速度快且时 间是固定的。参考实现见实例2。

实例2：从任务就绪表中读取内核个数相同的高优先级就绪任务优先级存 储在高优先级任务就绪表中。

os_rdy_x=OSRdyX;/*拷贝任务就绪表中的行值OSRdyX到变量os_rdy_x*/

i=OSUnMapTbl[os_rdy_x];/*获取最高优先级就绪任务所在行号*/

for(i;i=OSUnMapTbl[os_rdy_x];i<k)/*从最高优先级所在的行开始查找*/

{

os_rdy_y=OSRdyY[i];/*拷贝任务就绪表中对应的列值OSRdyY[i]到 变量os_rdy_y*/

j=OSUnMapTbl[os_rdy_y];/*在有就绪任务的行中查找该行最高优先 级就绪任务所在列号*/

for(j;j=OSUnMapTbl[os_rdy_y];j<k)/*从最高优先级所在的列开始查找*/

{

OSHighPrioRdyTbl[n]=i<<3+j;/*计算优先级，并存储在高优先级任 务就绪表中*/

n++;/*高优先级就绪任务计数器加1*/

if(n==CORE_NUMBER)break;/*如果已经读满，则退出循环*/

os_rdy_y&=～OSOffSetMapTbl[j+1];/*置已经读取的列在os_rdy_y中 对应的位为0*/

if(os_rdy_y==0)break;}

if(n==CORE_NUMBER)break;/*如果已经读满，则退出循环*/

os_rdy_x&=～OSOffSetMapTbl[i+1];/*置已经读取的行在os_rdy_x中

}对应的位为0*/

从整个步骤可以看出，该查找算法简单，通过查表方法查找任务只需要执 行内核个数相同的次数，查找次数不会因为任务增加而增加，查找速度快且时 间是固定的。

2.基于有序表的可调度任务和可抢占内核查找方法

通过上面提到的高优先级任务查找算法可以快速查找到需要高优先级就绪 任务。由于当前运行任务也可能在查找到的高优先级就绪任务中，需要找出新 的就绪任务抢占没有在高优先级就绪任务中的运行任务调度执行。为了便于操 作比较，本发明设计了一个高优先级就绪任务表用于保存当前查找到的高优先 级任务的优先级，同时还设计了内核-任务映射备份表用于保存当前运行任务优 先级以及所在的内核编号，两个表虽然在名称上不同，但为了便于内容拷贝， 其表结构组成是相同的。首先选择与内核个数相同的高优先级任务，然后和用 以记录在处理器内核中运行的任务优先级的内核-任务映射备份表进行比较，看 高优先级就绪表中哪些任务没有运行和内核-任务映射备份表中哪些正在运行的 任务没有在高优先级就绪表中。由于高优先级就绪表中的任务是下一次调度的 任务，用前面一组选出的任务抢占后面一组选出任务调度运行，其他运行任务 保持不变。这样通过比较高优先级就绪任务表与内核-任务映射表中的当前运行 任务优先级的不同，快速找出没有在内核-任务映射表中的高优先级任务和没有 在高优先级就绪表中的当前运行任务所在的内核，然后通过核间中断主动触发 相应的内核调度指定高优先级任务运行。主要包括三个主要环节：一是快速查 找调度可调度任务和可抢占内核，二是快速调度指定任务，三是更新映射表。

因为在建立高优先级就绪表时，当前正在运行的任务也在就续表中有效的。 因此，高优先级就绪表中可能也存在正在运行的优先级。在新的高优先级就绪 表和上一次的相比存在三种情况：一是全部都是不同的高优先级，二是部分优 先级是新的，三是全部都是正在运行的任务。

在查找到的高优先级列表中，先前的内核-任务映射表中存储的是上一次的 高优先级，如果其中有任务优先级不在当前高优先级就绪表中，则有可能优先 级任务可能已经运行结束，或者被挂起了，或者优先级低于新的优先级，表示 这些优先级任务不在本次调度之列。因此，只需要需要挑选出没有在内核-任务 映射表中的任务，同时挑选出内核-任务映射表中没有在当前就绪表中的优先级 所对应的内核，就可以进行多核调度。为了更快地进行比较，两个表都按优先 级从高到底进行排列。下面是比较算法步骤：

1)首先在高优先级就绪表中从最低优先级开始选取优先级和内核-任务映射表 的最低优先级进行比较。

2)如果优先级相同，则记录该优先级在内核-任务映射表中的位置，通过该位置 可以获得对应的优先级及内核号，说明该任务已经在运行中，不需要重新调度， 并设置不可调度内核标志。把内核-任务映射表中比较位置调整为下一个高优先 级任务所在位置，在未比较完高优先级就绪表中的优先级的情况下，该位置的 也是下一次在内核-任务映射表中开始比较的位置。因为，此时高优先级就绪表 中的其他任务优先级肯定高于内核-任务映射表中找到的当前任务优先级，这样 可以减少比较次数。跳转到步骤4）。

3)如果不相等，再从内核-任务映射表中取更高优先级进行比较。如果比较完内 核-任务映射表中的所有优先级都没有找到和高就绪表中当前优先级相等的优先 级，则表示从高就绪表取出来比较的优先级不在内核-任务映射表中，是新的任 务，应该被调度，并记录该优先级在高就绪表中的位置，设置任务可以调度标 志。

4)循环步骤1）-3），直到所有优先级被比较完或者内核-任务映射表位置已经 比较完。

5)然后从高优先级就绪表中依次选取设置有可调度标志的任务调度到内核-任 务映射表中设置为可用标志的内核中运行，同时拷贝运行调度任务的内核编号 到高优先级就绪表中被调度任务对应位置，直至所有新任务被调度完成。

6)然后拷贝高优先级就绪表到内核-任务映射表中以备下一次调度比较。

我们采用附图3的实例来进行说明。优先级数值越大，优先级越低。先从高优 先级就绪表中取出最低优先级9和内核-任务映射表中的最高优先级5开始比较， 当比较到优先级9时，停止比较，并记录当前内核不能被占用，同时将内核编 号填写到高优先级就绪表中优先级9对应的内核位置。高优先级就绪表中的任 务优先级8就从内核-任务映射表中的优先级7比较到优先级5就可以了，只需 要比较两次，发现没有相等的优先级，设置任务可以调度标志。优先级7和6 采用相同的比较方法。

比较完成后，根据结果记录表分别选出可调度优先级对应的任务调度到可 用的内核运行。同时将内核编号拷贝到高优先级任务就绪表中。

3.基于核间中断消息的核间调度请求

在找到需要调度的任务和可以抢占的处理器核后，需要比较主核是否就是 被抢占的内核，如果本地调度器比较该内核与当前正在调度处理的内核相同， 则进行本地调度。如果不相同则将需要调度的任务优先级通过核间中断通信的 方式快速将调度信息传递给将要调度该任务的内核。调度信息应该包括调度请 求和需要调度的任务优先级，避免从核再次查找调度任务。

在设计中可以设计一个使能调度标志用于记录是否是其他内核传递使能调 度核间中断。该内核接收到核间中断信息后，判断是否是要求调度信息，如果 是，读出任务优先级并传递给内核高优先级全局变量，并设置调度使能标志。 中断退出后进行任务调度，在任务调度器中比较是否调度使能标志有效，如果 有效，设置使能调度标志为无效，然后直接进行调度，不需要重新查找高优先 级。

通过这种查找方法，可以减少可调度任务和可用内核的查找次数，减少了 高优先级就绪任务的等待时间和内核查找就续表的时间，同时通过核间中断实 现了每个内核可以进行全局调度的功能，解决主从式结构中主核调度瓶颈问题。

4.基于事件触发同一优先级多任务调度方法

多核处理器使任务并行运行成为可能。对于实时多核嵌入式操作系统来说， 如何主动设置并行任务，便于操作系统调度还是很难做到。本发明设计一种基 于事件触发的同一优先级多任务调度方法，提供用于一个并行任务组设置的接 口。用户可以通过设置多个任务为同一优先级，同一优先级任务不能相互抢占。 事件可以同时触发同一优先级任务就绪，也可以独立触发单个任务就绪。内核 在调度时根据优先级调度任务到不同的内核中运行。

当前嵌入式操作系统中支持同一优先级多任务的调度都是采用时间片轮转 法进行的。在嵌入式实时系统中，某些任务存在关联关系，实时性要求相同， 但是需要事件触发调度。基于时间片轮转调度策略不能满足实时系统的需要， 特别是多核处理器中同步多任务的要求。因此，本发明针对实时嵌入式系统中 的实时性要求，设计一种基于事件触发的同一优先级多任务调度方法。

通过对一个优先级增加一个优先级偏移量用来表示相同优先级的不同编 号。如实例3所示，可以设置一个结构体定义优先级、基本优先级、优先级偏 移量，便于调度区分。基本优先级用于不同优先级任务的查找，偏移量用于相 同优先级的查找。当某个基本优先级对应任务为1个时，偏移量为0，否则偏移 量大于零。优先级偏移量的每一位对应一个任务。为了减少相同优先级任务总 的完成时间，本发明把偏移量的值作为相同优先级的任务的次优先级，采用查 表方法查找偏移量的任务调度。提供给用户一个设置相同优先级调度顺序的接 口，用户可以把实时性更高的相同优先级任务的偏移量设置更小，或者把执行 时间长的任务优先级偏移量设置更小，以便于更早调度。偏移量对应就绪任务 查找与就绪状态的设置和移除都是通过查表方法实现，可以快速操作。

实例3：支持多任务的优先级结构

typedefstructos_task_prio{

INT8Ubaseprio;//基本优先级，类型可以根据支持的任务数确定

INT8Uoffset;//优先级偏移量，类型可以根据支持的任务数确定，

//每一位对应一个任务}OS_TASK_PRIO;

偏移量可以配置最大数目，可以是8，也可以是16。在操作系统中设计一 个就绪变量数组来记录优先级偏移量任务对应的就绪状态，如实例4所示，对 应于该优先级变量的偏移量。

实例4：设计一个与基本优先级相对应的偏移量就续表

INT8UOSSamePrioTskRdy[OS_LOWEST_PRIO+1u];/*定义优先级偏移 量对应任务就绪表*/

具有相同优先级的多任务调度过程如下：

在任务就绪表中的优先级为基本优先级，当优先级偏移量中有一个以上任 务就绪时，基本优先级对应就绪表中的位置1，表示有任务就绪。在任务调度过 程中，调度器首先根据多核调度算法从任务就绪表中查找就绪任务的基本优先 级。找到基本优先级后，比较优先级偏移量看是否为0，如果为0表示该优先级 只有一个任务对应；如果不为0，表示该优先级对应多个任务。优先级偏移量为 0时，在任务就绪表中查找下一个就绪任务；当优先级偏移量不为0时，通过查 表在偏移量就续表中依次查找就绪任务的优先级偏移量值。

当高优先级就任务查找完成后，需要将这些相同优先级任务调度到合适的 处理器核上。其选择方法和前面提到的方法一样，只是在任务优先级比较的过 程中，如果两个任务的基本优先级相同时，还需要比较其优先级偏移量，如果 表中没有找到相等的优先级任务，则调度执行。内核的选择方法和前面的一样。

该调度算法结合前面的多内核并行调度，可以使相同优先级任务并行执行， 大大提高实时性。以下举例说明：

在发明中设置了两个映射表用于在设置或者删除就绪位时快速查询。一个 表OSOffSetMapTbl用来根据优先级偏移量查找在就绪变量中对应的位，用来设 置任务就绪，操作方式如实例5所示。如果偏移量变量的值为0，表示该优先级 只有一个任务对应；如果不为0，表示有多个任务对应该优先级。表中的值1、 2、4、8、16、32、64、128分别对应于优先级偏移量1、2、3、4、5、6、7、8。 对于不同的优先级存在不同的任务个数，设置偏移量0选项的目的是为了减少 调度时对非多任务优先级的处理步骤。

实例5：偏移量对应位查找表及就绪设置方法

INT8U const OSOffSetMapTbl[9]={0,1,2,4,8,16,32,64,128};

OSSamePrioTskRdy[prio.baseprio]|=OSOffSetMapTbl[prio.offset];

另外一个用来根据就绪变量的值查找高优先级任务的优先级偏移量，用于 调度时查找高优先级任务时配合主优先级一起使用，每次查找高优先级偏移量 对应任务调度。

在调度过程中，我们统一采用从低偏移量调度到高偏移量优先级的顺序， 减少调度复杂度。如果需要设置调度顺序，用户可以人为地将需要更早调度的 任务的偏移量值设置小一些。根据这个调度方法，我们设计一个一个查找表， 把每个偏移量值对应的最小偏移量值计算出存储在该表中，便于调度时快速找 到调度任务。就绪任务优先级偏移量查找表与操作方式如实例6所示。

和前面的查找表计算方法一样，把公式稍作修改如公式（3），就可以采用 公式（3）计算每种偏移量对应的最小偏移。

如当offset=55时，其在偏移量对应的二进制值为00100111，可以知道其最 小的优先级偏移值为1，通过公式（3）也能很快确定，把该值填写到表中的55 所对应的位置。如果需要对查找优先级偏移量对应的位，则通过查找表 OSOffSetMapTbl就能很快得出。这样就可以对偏移量对应的优先级任务的偏移 量就绪表进行操作，如实例6所示。

实例6：8个任务对应同一个优先级时，高优先级就绪任务偏移量的查找

方法，已知高优先级任务的基本优先级为prio。

INT8UconstOSUnOffSetMapTbl[256]={

0u,1u,2u,1u,4u,1u,2u,1u,8u,1u,2u,1u,4u,1u,2u,1u,/*0x00to0x0F*/

16u,1u,2u,1u,4u,1u,2u,1u,8u,1u,2u,1u,4u,1u,2u,1u,/*0x10to0x1F*/

32u,1u,2u,1u,4u,1u,2u,1u,8u,1u,2u,1u,4u,1u,2u,1u,/*0x20to0x2F*/

16u,1u,2u,1u,4u,1u,2u,1u,8u,1u,2u,1u,4u,1u,2u,1u,/*0x30to0x3F*/

64u,1u,2u,1u,4u,1u,2u,1u,8u,1u,2u,1u,4u,1u,2u,1u,/*0x40to0x4F*/

16u,1u,2u,1u,4u,1u,2u,1u,8u,1u,2u,1u,4u,1u,2u,1u,/*0x50to0x5F*/

32u,1u,2u,1u,4u,1u,2u,1u,8u,1u,2u,1u,4u,1u,2u,1u,/*0x60to0x6F*/

16u,1u,2u,1u,4u,1u,2u,1u,8u,1u,2u,1u,4u,1u,2u,1u,/*0x70to0x7F*/

128u,1u,2u,1u,4u,1u,2u,1u,8u,1u,2u,1u,4u,1u,2u,1u,/*0x80to0x8F*/

16u,1u,2u,1u,4u,1u,2u,1u,8u,1u,2u,1u,4u,1u,2u,1u,/*0x90to0x9F*/

32u,1u,2u,1u,4u,1u,2u,1u,8u,1u,2u,1u,4u,1u,2u,1u,/*0xA0to0xAF*/

16u,1u,2u,1u,4u,1u,2u,1u,8u,1u,2u,1u,4u,1u,2u,1u,/*0xB0to0xBF*/

64u,1u,2u,1u,4u,1u,2u,1u,8u,1u,2u,1u,4u,1u,2u,1u,/*0xC0to0xCF*/

16u,1u,2u,1u,4u,1u,2u,1u,8u,1u,2u,1u,4u,1u,2u,1u,/*0xD0to0xDF*/

32u,1u,2u,1u,4u,1u,2u,1u,8u,1u,2u,1u,4u,1u,2u,1u,/*0xE0to0xEF*/

16u,1u,2u,1u,4u,1u,2u,1u,8u,1u,2u,1u,4u,1u,2u,1u/*0xF0to0xFF*/

};

prio.offset=OSUnOffSetMapTbl[OSSamePrioTskRdy[prio.baseprio]];/*查表读取高优 先级偏移量*/

OSSamePrioTskRdy[prio.baseprio]&=～OSOffSetMapTbl[prio.offset];/*从任务就绪表 中删除偏移量对应任务就绪状态*/

如果设置8个任务对应同一个优先级，那么这个偏移量对应就绪表设置8 位，如果是16个则设置为16位。对应的查找表值也需要根据任务个数按照公 式（3）重新计算其查找值。

该方法提供了基于事件触发的同优先级多任务调度，采用查表方法快速查 找就绪任务，调度就绪任务时查找时间不会因为就绪任务的增加而增加，实现 了实时内核对同优先级多任务快速调度。