CN-121979640-A - Multi-core hybrid real-time scheduling method and system based on job priority and ladder type resource recovery

CN121979640ACN 121979640 ACN121979640 ACN 121979640ACN-121979640-A

Abstract

The invention provides a multi-core hybrid real-time scheduling method and system based on job priority and ladder type resource recovery. The invention provides a dynamic scheduling mechanism of job priority, which is different from the traditional fixed priority, is based on a Markov state transition model and dynamically adjusts the priority according to the historical execution state of tasks, namely the continuous hit/miss times. The invention initiates a ladder-type resource recovery technology for the first time, abandons static resource reservation, generates ladder-type resource distribution through an offline analysis task execution form, and dynamically adjusts the core number in combination with an online progress. The invention realizes win-win of the hard/weak hard real-time task and the soft real-time task by backfilling the recovered idle resources to the soft real-time task in real time.

Inventors

LI SIZHAO
YAN BEIBEI
ZHU XIAOLI
WEI HAO
GUO ZHUJUN

Assignees

哈尔滨工程大学

Dates

Publication Date: 20260505
Application Date: 20260129

Claims (10)

1. The multi-core hybrid real-time scheduling method based on job level priority and ladder type resource recovery is characterized by comprising the following steps: Hybrid task modeling, defining weak hard real-time tasks The upper limit of the number of times of allowing missing deadlines in k continuous operation windows is m, and simultaneously, offline execution form analysis is carried out on the parallel DAG tasks to generate a ladder resource vector describing the change of the parallelism of the parallel DAG tasks along with the time; Dynamic adjustment of job priority, namely dynamically calculating the job priority based on the historical missing state of the weak and hard task when the weak and hard task runs, and balancing the load by reducing the priority in a safe state and resetting the priority in a critical state; step resource allocation and recovery, namely dynamically allocating cores for parallel tasks according to step resource vectors, and monitoring the number of active subtasks in real time to recover idle resources; And (3) closed loop feedback scheduling, namely backfilling the recovered cores to soft real-time tasks in real time, and analyzing and checking the safety of the system by expanding response time.
2. The method of claim 1, wherein the specific strategy for dynamic adjustment of job level priority employs a non-linear mapping strategy based on markov state transitions: linear decrementing logic when the task is in the "safe state" for continuous hit deadlines, job priority is formulated Setting, wherein As a reference priority level, In the form of a linear step size, Is the number of consecutive hits; reset recovery logic when a task is missing or is not available Approximation is made When entering the critical state, the priority resetting mechanism is triggered immediately to lift the current and subsequent operations to the highest critical priority Until the state is restored.
3. The method of claim 1, wherein the step of introducing a weakly hard constrained transformation prior to scheduling complicates Sliding window constrained equivalent conversion to a single "critical sequence" The system only needs to verify that Whether the worst response time under the sequence meets the cut-off time or not can be judged Whether the constraint is globally satisfied, thereby reducing the state space complexity of online scheduling.
4. The method of claim 1, wherein the step resource vector offline generation method comprises performing execution trace tracking on DAG parallel tasks, discretizing a task execution period into S stages, and generating a vector Resource allocation value for each phase Is strictly defined as Wherein To ensure the minimum number of cores required for critical path advancement at this stage, Is the maximum parallelism of this stage.
5. The method of claim 4, wherein the scheduler maintains an execution progress pointer for the task based on an online execution mechanism for the ladder resource allocation Step vector generated offline by real-time indexing When the task enters a new execution stage, the system checks the global free resource pool, and the CPU affinity mask is utilized to dynamically bind the task to the number of the tasks Instead of locking the largest resource over the entire lifecycle.
6. The method of claim 1, wherein the trigger criteria for resource reclamation establishes a hysteresis comparison mechanism that periodically samples the actual number of active sub-tasks of the parallel tasks by the system And only when the condition is satisfied And the state duration exceeds a preset hysteresis threshold When the resource recovery operation is triggered, the release is carried out Core-to-global pool to prevent frequent inter-core migration due to transient fluctuations, The number is currently assigned.
7. The method of claim 1, wherein the allocation logic of the idle resource backfill establishes a hierarchical backfill policy: A performance priority mode, wherein if the soft real-time task ready queue is not empty, the recovered core is immediately mapped to the soft real-time task, and the concurrency of the soft real-time task is expanded to improve the throughput; and in the energy efficiency priority mode, if the ready soft real-time task does not exist, the recovered idle core is placed in a C-state deep sleep state through a DVFS interface so as to reduce the dynamic power consumption of the system.
8. The method of claim 1, wherein the validation formula for response time analysis is extended using a modified iterative formula Calculating worst response time; Dynamic interference term Quantifying interference change of priority fluctuation of high-priority tasks caused by JLPS mechanisms on low-priority tasks; Recovering gain items And when the parallel task interference is calculated, deducting the calculation resources released by the stepwise recycling, and reducing the worst-case interference upper bound.
9. A multi-core hybrid real-time scheduling system implementing the method of any one of claims 1-8, the system comprising: an offline morphology parser to generate a ladder resource description file; Extended task control block TCB built-in for recording historical miss status Continuous hit count A register field of (2); The dynamic scheduling engine comprises JLPS priority computing units and Ladder-RAM resource allocation units; resource monitoring and recycling device for real-time monitoring And a kernel module performing core stripping and backfilling operations.
10. A computer readable storage medium storing computer instructions which, when executed by a processor, implement the steps of the method of any one of claims 1-8.

Description

Multi-core hybrid real-time scheduling method and system based on job priority and ladder type resource recovery Technical Field The invention relates to the technical fields of spacecraft guidance, autopilot and industrial control, in particular to a multi-core hybrid real-time scheduling method and system based on job priority and stepped resource recovery. Background In a multi-core real-time system, task scheduling needs to be balanced between 'time limit guarantee' and 'resource utilization rate'. The traditional Hard real-time scheduling (RM, EDF) aims at zero miss, cores are statically allocated according to worst execution time (WCET), so that a large amount of computation resources are idle under average load, the global RM/EDF can improve the utilization rate, but the miss rate of weak Hard real-time (Weakly-Hard) tasks is rapidly increased under high load, and the later idle cores cannot be recovered by static allocation of parallel Directed Acyclic Graph (DAG) tasks, so that the resource waste is particularly obvious. 2022, Vreman et al proposed a "Weakly-hard. Jl" global fixed priority framework, which introduced weak hard constraints (m-k model) into schedulability analysis for the first time, but did not consider job level dynamic priorities, and the miss rate still reached 3.8%. In 2023 He et al, IEEETCAD, give "priority allocation within conditional DAG task", parallelism is improved by critical path internal priority, however resources cannot be recovered once allocated, experiments show that resource reservation is excessive by 37%. 2024, Moyano et al proposed "Job-LevelPriorityClasses" global scheduling, set Job priority class for weak and hard tasks, and the miss rate was reduced to 2.1%, but static thresholds were adopted between priority classes, which could not be adjusted on line with execution form, and cores were still pre-allocated to parallel tasks according to maximum parallelism, and recovery rate was 0. In the same year, liang et al propose "DAG response time optimization of mutual exclusion execution perception" in DAC, interference is reduced through offline parsing, however, in the online stage, no resource recovery mechanism exists, the soft real-time task completion rate is only 71.5%, and a large number of idle cores are in C-State and cannot be reused. In summary, the following drawbacks are common in the prior art: 1. the priority of the weak-hard task is static or semi-static, and the miss rate is increased steeply along with the increase of the load; 2. the parallel DAG tasks are distributed to cores at one time according to the maximum parallelism of a key path, the cores cannot be recovered when the parallelism is reduced in the later execution period, and the resource reservation is excessive by 30% -50%; 3. due to the lack of a cooperative mechanism of 'job level dynamic priority' and 'stepped resource recovery', when three tasks of hard real time, weak hard real time and soft real time are mixed and deployed, the schedulable rate, the resource utilization rate and the soft real time completion rate of the system cannot be simultaneously improved; 4. The schedulability analysis is still based on the assumption of fixed priority and maximum resource demand, and interference reduction caused by priority lifting and resource recovery cannot be reflected online, so that analysis results are too conservative, and resources are further wasted. Disclosure of Invention The invention aims to solve the problems in the prior art and provides a multi-core mixed real-time scheduling method and system based on job level priority and ladder type resource recovery. The invention is oriented to spacecraft guidance, autopilot, industrial control and other hard real-time multi-core SoCs, is used for the mixed deployment scene of weak hard and soft real-time tasks, and can obviously improve the resource utilization rate and reduce the task miss rate. The invention is realized by the following technical scheme, and provides a multi-core mixed real-time scheduling method based on job level priority and ladder type resource recovery, which comprises the following steps: Hybrid task modeling, defining weak hard real-time tasks The upper limit of the number of times of allowing missing deadlines in k continuous operation windows is m, and simultaneously, offline execution form analysis is carried out on the parallel DAG tasks to generate a ladder resource vector describing the change of the parallelism of the parallel DAG tasks along with the time; Dynamic adjustment of job priority, namely dynamically calculating the job priority based on the historical missing state of the weak and hard task when the weak and hard task runs, and balancing the load by reducing the priority in a safe state and resetting the priority in a critical state; step resource allocation and recovery, namely dynamically allocating cores for parallel tasks according to step resource vectors, and monitoring the num