.328. 智能系统学报 第10卷 3)任务不可抢占。 Rate a Ct=】 Dataij (10)》 系统运行时首先将任务初始化，构造TDS,由于 0≤k≤m-1,0≤s≤m-1,0≤i<|Ta1 算法中大多计算只针对就绪任务，特别是任务分配 式中：PW代表任务T的等待时间所占优先级比重， 时，所以为了节约计算开销，算法初始化时会生成一 PC代表通信时间所占优先级比重，L为内核P:的 个就绪任务列表和一个等待任务列表。当内核P: 负载状态。t是当前时间，1-T表示任务T的等待时 任务队列长度ITLI≤l时，就向调度程序请求分 间，等待时间越长的任务优先级相对越高，同等条件 配任务，调度程序遍历就绪列表，计算相对于内核 下，调度程序优先调度等待时间长的任务，避免存在 P的优先级，选择优先级T值最大的任务分配到P 就绪任务长时间等待的“饥饿”现象，B是实时性因 上，重复执行此过程，直到内核P任务队列长度 子，用来调节等待时间在优先级中所占比重。C表 ITLI≥。若同时有多个内核请求任务分配，调度 示任务T,的通信时间，STDS算法假设同一内核内的 程序分配任务时需要响应这几个内核的请求，计算 任务通信开销忽略不计，C:值即任务T,与除内核P 优先级时需要计算相对于这几个内核的优先级，然 以外的其他内核P,上依赖任务通信的时间之和，用 后取最大值作为最终优先级，调度程序选择优先级 Daau表示，下标s即任务T,的T,属性值， 最大的任务分配到对应的内核。 jeTe+Rate. 值得注意的是在动态调度过程中，为了保证数 据实时有效，STDS算法在每个任务分配完成或执行 表示任务T分配给内核P。s-1 一表示平均通信 结束时对数据进行更新。当任务T分配给内核P m 后，需要将任务T对应数据项中的T置为k,此时内 时间，通信时间越小，PC值越大，优先级也相应越 核P负载也相应改变；当任务T执行完成时，如果 大，对于C4相同的任务，若任务的∑C。值较 任务T依赖任务T,需要将任务T的T值减1，若 0≤s≤m-1 大，则说明此任务如果分配到内核P上节省的通信 减1后T:=0,将任务T状态置为就绪态并从等待 开销更多，相应的其优先级也较高。在实际计算时， 列表移到就绪列表。为了降低复杂度节省时间， 因为任务T的依赖任务已经全部分配执行，所以若 STDS算法采用先记录再批量执行的方式，即在任务 分配在内核P:上，通信开销是个定值，因此PC.只 执行期间暂时将完成的任务编号记录，在任务调度 程序执行时批量更新数据：如果任务T执行完毕且 需计算一次。少尼 一反应了内核的负载状 所有依赖T的任务也执行完毕，就将任务T的信息 态，ITLI是内核P当前任务队列长度，当1TL:I= 从TDS中删除，从而释放内存节省空间。 lm时其值为0，从而T=0为最小值，则当前状态 如果就绪列表为空，调度程序不会响应内核的 下不能向内核P分派任务。在一次调度过程中，调 任务分配请求，当就绪列表和等待列表全为空时，说 度程序可能需要响应多个内核的调度请求，对于 明任务全部执行完毕，调度结束。 |TLI较小的内核，其L较大，从而实现优先将任务 STDS算法实现步骤： 分配到负载较轻的内核，并进而达到负载均衡效果。 Procedure STDS(SM,TDS,PL,TL)/*SM 综上所述，任务优先级值的计算，是对等待时 示处理器内核系统；TDS是所有任务信息；Pm是需 间、通信开销和内核负载3个因素综合考量的过程， 要分配任务的内核列表，T。是执行完毕但还未进 其结果可能不是单一因素中最优的，但一定是综合 行信息更新的任务列表*/ 考虑全部3种因素后最优的选择。 1)for each Te TL 2){Ta[]-T:; 3算法实现 3) for each T∈Ta 在上节中详细介绍了任务优先级的计算，本节 4) T←T-1;/*执行完毕的任务信息 将介绍STDS算法的具体实现过程。 更新，将其后继任务的依赖任务数量减一*/ 为了使任务调度算法得到较理想的实现，STDS /end for each Tie TLee * 算法的研究基于以下假设条件： 5)TLa助[]←-TDS;/*就绪任务放入就绪队列*/ 1)假设任务间的依赖关系固定不变： 6)for each TiTLready 2)同一内核上任务间通信开销忽略不计； 7){for each P&∈PiaＣｉｋ ＝ ｊ∈Ｔ∑ｉｄｄ＆＆ｓ≠ｋ Ｄａｔａｉ，ｊ Ｒａｔｅｓ，ｋ （１０） ０ ≤ ｋ ≤ ｍ － １，０ ≤ ｓ ≤ ｍ － １，０ ≤ ｉ ＜ ｜ ＴＬｉｓｔ ｜ 式中：ＰＷｉ代表任务 Ｔｉ的等待时间所占优先级比重， ＰＣｉｋ代表通信时间所占优先级比重，Ｌｋ为内核 Ｐｋ的 负载状态。 ｔ 是当前时间，ｔ－Ｔｉｔ表示任务 Ｔｉ的等待时 间，等待时间越长的任务优先级相对越高，同等条件 下，调度程序优先调度等待时间长的任务，避免存在 就绪任务长时间等待的“饥饿”现象， β 是实时性因 子，用来调节等待时间在优先级中所占比重。 Ｃｉｋ表 示任务 Ｔｉ的通信时间，ＳＴＤＳ 算法假设同一内核内的 任务通信开销忽略不计，Ｃｉｋ值即任务 Ｔｉ与除内核 Ｐｋ 以外的其他内核 Ｐｓ上依赖任务通信的时间之和，用 ｊ∈Ｔ∑ｉｄｄ＆＆ｓ≠ｋ Ｄａｔａｉ，ｊ Ｒａｔｅｓ，ｋ 表示，下标 ｓ 即任务 Ｔｊ的 Ｔｊｃ属性值， 表示任务 Ｔｊ分配给内核 Ｐｓ。 ０≤∑ｓ≤ｍ－１ Ｃｉｓ ｍ 表示平均通信 时间，通信时间越小，ＰＣｉｋ值越大，优先级也相应越 大，对于 Ｃｉｋ 相同的任务，若任务的 ０≤∑ｓ≤ｍ－１ Ｃｉｓ 值较 大，则说明此任务如果分配到内核 Ｐｋ上节省的通信 开销更多，相应的其优先级也较高。 在实际计算时， 因为任务 Ｔｉ的依赖任务已经全部分配执行，所以若 分配在内核 Ｐｋ上，通信开销是个定值，因此 ＰＣｉｋ只 需计算一次。 ｌ ｋ ＿ｍａｘ －｜ Ｔｌ ｋ ｜ ｌ ｋ＿ｍａｘ － ｌ ｋ＿ｍｉｎ 反应了内核的负载状 态， ｜ ＴＬｋ ｜ 是内核 Ｐｋ当前任务队列长度，当 ｜ ＴＬｋ ｜ ＝ ｌ ｋ＿ｍａｘ时其值为 ０，从而 Ｔｉｐｋ ＝ ０ 为最小值，则当前状态 下不能向内核 Ｐｋ分派任务。 在一次调度过程中，调 度程序可能需要响应多个内核的调度请求，对于 ｜ ＴＬｋ ｜较小的内核，其 Ｌｋ较大，从而实现优先将任务 分配到负载较轻的内核，并进而达到负载均衡效果。 综上所述，任务优先级值的计算，是对等待时 间、通信开销和内核负载 ３ 个因素综合考量的过程， 其结果可能不是单一因素中最优的，但一定是综合 考虑全部 ３ 种因素后最优的选择。 ３ 算法实现 在上节中详细介绍了任务优先级的计算，本节 将介绍 ＳＴＤＳ 算法的具体实现过程。 为了使任务调度算法得到较理想的实现，ＳＴＤＳ 算法的研究基于以下假设条件： １）假设任务间的依赖关系固定不变； ２）同一内核上任务间通信开销忽略不计； ３）任务不可抢占。 系统运行时首先将任务初始化，构造 ＴＤＳ，由于 算法中大多计算只针对就绪任务，特别是任务分配 时，所以为了节约计算开销，算法初始化时会生成一 个就绪任务列表和一个等待任务列表。 当内核 Ｐｋ 任务队列长度｜ Ｔｌ ｋ ｜ ≤ｌ ｋ＿ｍｉｎ时，就向调度程序请求分 配任务，调度程序遍历就绪列表，计算相对于内核 Ｐｋ的优先级，选择优先级 Ｔｉｐ值最大的任务分配到 Ｐｋ 上，重复执行此过程，直到内核 Ｐｋ 任务队列长度 ｜ Ｔｌ ｋ ｜≥ｌ ｋ。 若同时有多个内核请求任务分配，调度 程序分配任务时需要响应这几个内核的请求，计算 优先级时需要计算相对于这几个内核的优先级，然 后取最大值作为最终优先级，调度程序选择优先级 最大的任务分配到对应的内核。 值得注意的是在动态调度过程中，为了保证数 据实时有效，ＳＴＤＳ 算法在每个任务分配完成或执行 结束时对数据进行更新。 当任务 Ｔｉ分配给内核 Ｐｋ 后，需要将任务 Ｔｉ对应数据项中的 Ｔｉｃ置为 ｋ，此时内 核 Ｐｋ负载也相应改变；当任务 Ｔｉ执行完成时，如果 任务 Ｔｊ依赖任务 Ｔｉ，需要将任务 Ｔｊ的 Ｔｉｄｎ值减 １，若 减 １ 后 Ｔｉｄｎ ＝ ０，将任务 Ｔｊ状态置为就绪态并从等待 列表移到就绪列表。 为了降低复杂度节省时间， ＳＴＤＳ 算法采用先记录再批量执行的方式，即在任务 执行期间暂时将完成的任务编号记录，在任务调度 程序执行时批量更新数据；如果任务 Ｔｉ执行完毕且 所有依赖 Ｔｉ的任务也执行完毕，就将任务 Ｔｉ的信息 从 ＴＤＳ 中删除，从而释放内存节省空间。 如果就绪列表为空，调度程序不会响应内核的 任务分配请求，当就绪列表和等待列表全为空时，说 明任务全部执行完毕，调度结束。 ＳＴＤＳ 算法实现步骤： Ｐｒｏｃｅｄｕｒｅ ＳＴＤＳ（ＳＭ，ＴＤＳ， ＰＬｉｓｔ，ＴＬｅｘｅ ） ／ ∗ＳＭ 表 示处理器内核系统；ＴＤＳ 是所有任务信息； ＰＬｉｓｔ 是需 要分配任务的内核列表， ＴＬｅｘｅ 是执行完毕但还未进 行信息更新的任务列表∗／ １）｛ｆｏｒ ｅａｃｈ Ｔｉ∈ ＴＬｅｘｅ ２） ｛ Ｔｉａ ［］←Ｔｉ； ３） ｆｏｒ ｅａｃｈ Ｔｊ∈Ｔｉａ ４） Ｔｊｄｎ←Ｔｊｄｎ －１； ／ ∗执行完毕的任务信息 更新，将其后继任务的依赖任务数量减一∗／ ｝ ／ ∗ ｅｎｄ ｆｏｒ ｅａｃｈ Ｔｉ∈ ＴＬｅｘｅ ∗／ ５）ＴＬｒｅａｄｙ［］←ＴＤＳ；／ ∗就绪任务放入就绪队列∗／ ６） ｆｏｒ ｅａｃｈ Ｔｉ∈ＴＬｒｅａｄｙ ７）｛ ｆｏｒ ｅａｃｈ Ｐｋ∈ ＰＬｉｓｔ ·３２８· 智 能 系 统 学 报 第 １０ 卷