多核处理器中混合关键级任务可调度及半分区划分算法  

Research on Hybrid Critical-Level Task Scheduling and Semi-Partition Algorithm in Multi-Core Processor

作　　者：朱嘉炜 冒航 张凤登[1] ZHU Jiawei;MAO Hang;ZHANG Fengdeng(School of Optical-Electrical&Computer Engineering,University of Shanghai for Science and Technology,Shanghai 200093,China)

机构地区：[1]上海理工大学光电信息与计算机工程学院,上海200093

出　　处：《电子科技》2024年第3期1-9,共9页Electronic Science and Technology

基　　金：国家自然科学基金(71840003);上海市自然科学基金(15ZR1429300)。

摘　　要：当前,多数多处理机中混合关键级任务可调度性分析以及半分区调度算法均针对单核利用率展开研究。但由于多核系统任务调度复杂性较高,现有研究结果存在各处理器负载不均衡以及任务可调度性不理想等问题。针对该问题,文中将动态需求边界函数(Dynamic Demand Boundary Function,DDBF)的应用范围扩展至多核处理器系统。根据半分区划分调度算法对DDBF改进,并加入了结转作业和前接作业分析提出了SDDBF(Super Dynamic Demand Boundary Function),可更精确地计算与利用资源。文中基于SDDBF提出了SDA(Stepper Dispatch Algorithm)可调度性分析法与半分区划分算法MCWF(Mixed-Criticality Worist First)。仿真结果表明,相较于AMC(Adaptive Mixed Criticality)、AMC-max以及XU算法,SDA可调度性分析判定提升了5%~10%,相较于WF_MY(Worst First_My)、WF_NEW(Worst First_New)算法,MCWF可使系统在任意关键等级下的CPU(Central Processing Unit)负载具有更良好的均衡性能。At present,the schedulability analysis of mixed critical level tasks and semi-partition scheduling algorithms in most multiprocessors are focused on single-core utilization.However,due to the high complexity of task scheduling in multi-core systems,the existing research results have some problems,such as unbalanced load of each processor and unsatisfactory task schedulability.To solve this problem,the application scope of Dynamic Demand Boundary Function(DDBF)is extended to multi-core processor system in this study.DDBF is improved based on half-partition scheduling algorithm,and SDDBF(Super Dynamic Demand Boundary Function)is proposed by adding forward job and forward job analysis,which can calculate and utilize resources more accurately.Based on SDDBF,the schedulability analysis method of SDA(Stepper Dispatch Algorithm)and semi-partition algorithm MCWF(Mixed-Criticality Worist First)are proposed.The simulation results show that compared with AMC(Adaptive Mixed Criticality),AMC-MAX and XU algorithms,the schedulability analysis of SDA can be improved by 5%~10%.Compared with WF_MY(Worst First_My)and WF_NEW(Worst First_New)algorithms,MCWF makes the system have better CPU(Central Processing Unit)load balancing performance at any critical level.

关 键 词：混合关键级系统 半分区划分算法 多核平台 任务调度 动态需求边界 可调度性分析 实时系统 负载均衡 

分 类 号：TP316.2[自动化与计算机技术—计算机软件与理论]