WO2024164369A1 - Resource-aware task allocation method for mixed-criticality partitioned real-time operating system - Google Patents

Abstract

Disclosed is a resource-aware task allocation method for a mixed-criticality partitioned real-time operating system, comprising: grouping tasks according to a resource access situation; according to the task grouping result, allocating high-criticality tasks under the condition that the allocation result is ensured to be schedulable in a high-criticality system mode; according to the task grouping result, allocating low-criticality tasks under the condition that the allocation result is ensured to be schedulable in a low-criticality system mode; and according to the allocated high-criticality tasks and low-criticality tasks, performing scheduling of system mode switching by using a task migration method so as to complete task allocation. The present invention can improve the overall schedulability of the system, and can be widely applied to the technical field of computers.

Description

Resource-aware task allocation method for mixed-criticality partitioned real-time operating systems Technical Field

The invention relates to the field of computer technology, in particular to a resource-aware task allocation method for a mixed-key partition real-time operating system.

Background Art

Mixed criticality systems are embedded real-time systems that perform multiple functions on the same computing platform and meet space, power and cost constraints. Such systems are widely used in automotive, aerospace and other industries. In such an integrated system, applications with different certification requirements and different importance (criticality) can coexist and share system resources. Mixed criticality systems must ensure that high-criticality tasks can be executed correctly and meet time constraints, while low-criticality tasks can be abandoned in certain circumstances to ensure the operation of high-criticality tasks. Mixed criticality systems usually have two system operation modes: low criticality and high criticality. The system starts running in low criticality mode. In this mode, low criticality tasks run together with high criticality tasks with the execution time in low criticality mode. When a task in the system times out, the system will switch to high criticality mode and suspend the low criticality task. At the same time, the high criticality task will run with a longer execution time.

In a multi-core mixed-criticality system, low-criticality tasks and high-criticality tasks share various resources on the platform, such as code segments, data, memory, IO devices, etc. In order to ensure the integrity and consistency of the data, tasks need to access these shared resources in a mutually exclusive manner with locks. The spin locks specified in the AUTOSAR standard are widely used to protect the computational correctness of shared resources. Real-time systems use a resource sharing protocol based on spin locks to manage access to shared resources and provide an upper bound on the time for tasks to wait for and execute shared resources. However, due to the application of spin locks, when tasks request the same resources on different processors, they will wait on their respective processors until they successfully obtain the requested resources. This phenomenon will bring high blocking time to tasks and seriously undermine the schedulability of the system.

In real-time systems, response time analysis is a mainstream schedulability analysis method. This method first predicts the worst-case response time of each task and then compares this value with the task deadline. At present, in the schedulability analysis of shared resource protocols based on spin locks, by analyzing the resource access blocking within a given time, three types of blocking time (direct spin blocking, indirect spin blocking, and arrival blocking) can be accurately constrained, providing an upper bound on the time for tasks to wait and execute shared resources. Fitting this time term to the response time analysis equation can provide more accurate analysis results.

In recent years, in order to reduce resource contention between processors in multi-processor systems, resource-aware task allocation methods have been developed. It has received widespread attention. The idea of this task allocation is to reduce contention by localizing shared resources, that is, to allocate tasks that access the same shared resource to the same core as much as possible. However, in mixed-criticality systems, there are few research works that design task allocation algorithms with resource awareness as the main direction. At the same time, the frequent shared resource access that is widely present in real systems leads to problems such as long task blocking time and poor system schedulability.

At present, the main problems of task allocation algorithms in mixed critical systems are as follows:

Existing research generally uses heuristic algorithms to assign tasks. The task assignment rules mainly consider task utilization and deadline, and usually only consider tasks at their highest critical level (i.e., maximum utilization), which will lead to pessimistic estimates of system utilization and thus reduce system schedulability.

Some studies have considered the utilization differences at multiple key levels, which can improve the overall schedulability of the system. However, none of the above solutions consider the impact of shared resource access, which results in the system being unschedulable due to excessive blocking delays during actual operation.

Summary of the invention

In view of this, an embodiment of the present invention provides a resource-aware task allocation method for a mixed-criticality partitioned real-time operating system to improve system schedulability.

An aspect of an embodiment of the present invention provides a resource-aware task allocation method for a mixed-criticality partitioned real-time operating system, comprising:

Group tasks according to resource access;

According to the result of task grouping, high-criticality tasks are assigned while ensuring that the assignment result is schedulable in the high-criticality system mode;

According to the result of task grouping, the low-criticality tasks are allocated while ensuring that the allocation results are schedulable in the low-criticality system mode;

According to the assigned high-criticality tasks and low-criticality tasks, the task migration method is used to schedule the system mode switching and complete the task allocation.

Optionally, grouping the tasks according to resource access conditions includes:

Sort the shared resources from largest to smallest according to the total number of accesses to obtain the resource sorting result;

Grouping tasks according to the resource sorting result;

According to the critical level of the task, each resource task group and independent task group obtained by division is further divided.

Optionally, grouping tasks according to the resource sorting result includes:

Starting from the first resource, if a task needs to request this resource, then add it to the task group corresponding to this resource; If the task has been added to a group, it will not be added to other task groups; tasks that do not request any resources will be treated as an independent group;

According to the critical level of the task, each resource task group and independent task group obtained by the division is further divided, including:

Each resource task group and independent task group is further divided to obtain a high-criticality task group and a low-criticality task group corresponding to each resource, as well as an independent high-criticality task group and an independent low-criticality task group.

Optionally, allocating high-criticality tasks according to the result of task grouping while ensuring that the allocation result is schedulable in the high-criticality system mode includes:

According to the result of task grouping, a high-criticality task group corresponding to each resource and an independent high-criticality group are obtained, and the tasks in the task group corresponding to each resource are sorted in ascending order according to the utilization rate under the high criticality;

Start traversing from the task group corresponding to the resource with the largest total number of accesses;

Sort the processors in ascending order according to utilization at the high criticality level;

Allocate tasks in the current task group in sequence, and assign tasks to the first schedulable processor in processor order until all tasks of the high-criticality task groups corresponding to all resources are assigned;

The tasks in the independent task group are sorted in descending order according to the utilization at the high criticality level. Before each independent task is assigned, the processors are sorted from small to large according to the utilization at the high criticality level and assigned to the first schedulable processor in processor order.

Optionally, the allocating low-criticality tasks according to the result of task grouping while ensuring that the allocation result is schedulable in the low-criticality system mode includes:

According to the result of task grouping, a low-criticality task group corresponding to each resource and an independent low-criticality task group are obtained, and the tasks in the task group corresponding to each resource are sorted in ascending order according to the utilization rate under the low criticality;

Start traversing from the task group corresponding to the resource with the largest total number of accesses;

Sort the processors, put the processors with high-criticality tasks accessing the current resources in front, and sort them in ascending order according to the utilization under low criticality, and sort the remaining processors in ascending order according to the utilization under low criticality;

Allocate tasks in the current task group in sequence, and assign tasks to the first schedulable processor in processor order until all low-criticality task groups corresponding to all resources are assigned tasks;

The tasks in the independent task group are sorted in descending order according to the utilization at the low criticality level. Before each independent task is assigned, the processors are sorted from small to large according to the utilization at the low criticality level, and the processors are traversed and assigned to the first schedulable processor.

Optionally, the scheduling of system mode switching using a task migration method according to the allocated high-criticality tasks and low-criticality tasks to complete task allocation includes:

Calculate the response time of each high-criticality task when switching modes, and check whether the response time of the task exceeds the deadline when switching modes;

When the response time of a task exceeds the deadline, check the timeout reasons of the task in turn until the task can be scheduled;

Complete the scheduling of all high-criticality tasks.

Optionally, when the response time of the task exceeds the deadline, checking the timeout reasons of the task in sequence until the task can be scheduled includes:

When the arrival blocking time of the high-criticality task during mode switching is greater than the arrival blocking time under the high-criticality level, obtain the resource that causes the maximum arrival blocking and perform the following steps:

If there is no high-criticality task accessing the resource on the processor to which the current task belongs, and only low-criticality tasks are accessing the resource: sort the processors, put the processors that can cause spin blocking for low-criticality tasks in the front, and sort the remaining processors from large to small according to the slack time; according to the processor order, migrate all low-criticality tasks accessing the resource on the processor to the first processor that can meet the conditions;

If a high-criticality task accesses the resource on the processor to which the current task belongs: all low-criticality tasks accessing the resource on the processor that blocks the task from reaching the resource will be attempted to be migrated to the processor to which the current task belongs;

If the current task is still not schedulable after executing the above steps, continue to execute the following steps:

If the resource access blocking time is greater than 0, traverse by resource number, check each processor in turn by processor number whether there is a low-criticality task accessing resources that causes spin blocking on the task, and migrate the low-criticality task accessing resources on the processor to the core where the current task is located; if this migration will not cause a new task timeout, execute the migration;

Stop when the current task is schedulable or all resources are traversed.

Another aspect of the embodiment of the present invention further provides a resource-aware task allocation device for a hybrid critical partitioned real-time operating system, comprising:

The first module is used to group tasks according to resource access;

The second module is used to allocate high-criticality tasks according to the result of task grouping while ensuring that the allocation result is schedulable in the high-criticality system mode;

The third module is used to allocate low-criticality tasks according to the result of task grouping while ensuring that the allocation result is schedulable in the low-criticality system mode;

The fourth module is used to schedule the system mode switching according to the assigned high-criticality tasks and low-criticality tasks using the task migration method to complete the task allocation.

Another aspect of an embodiment of the present invention further provides an electronic device, including a processor and a memory;

The memory is used to store programs;

The processor executes the program to implement the method described above.

Another aspect of the embodiments of the present invention further provides a computer-readable storage medium, wherein the storage medium stores a program, and the program is executed by a processor to implement the method described above.

The embodiment of the present invention also discloses a computer program product or a computer program, which includes a computer instruction stored in a computer-readable storage medium. A processor of a computer device can read the computer instruction from the computer-readable storage medium, and the processor executes the computer instruction, so that the computer device executes the above method.

The embodiment of the present invention groups each task according to the resource access situation; according to the result of task grouping, high-key tasks are allocated while ensuring that the allocation result is schedulable in the high-key system mode; according to the result of task grouping, low-key tasks are allocated while ensuring that the allocation result is schedulable in the low-key system mode; according to the allocated high-key tasks and low-key tasks, a task migration method is used to schedule the system mode switching to complete the task allocation. The present invention can improve the overall schedulability of the system.

BRIEF DESCRIPTION OF THE DRAWINGS

In order to more clearly illustrate the technical solutions in the embodiments of the present application, the drawings required for use in the description of the embodiments will be briefly introduced below. Obviously, the drawings described below are only some embodiments of the present application. For ordinary technicians in this field, other drawings can be obtained based on these drawings without paying any creative work.

FIG. 1 is a flowchart of overall steps provided by an embodiment of the present invention.

DETAILED DESCRIPTION

In order to make the purpose, technical solution and advantages of the present application more clearly understood, the present application is further described in detail below in conjunction with the accompanying drawings and embodiments. It should be understood that the specific embodiments described herein are only used to explain the present application and are not used to limit the present application.

First, the related technical terms that may appear in the present invention are explained below:

Fixed-priority scheduling (FPS): A scheduling method in real-time systems. The priority of a task is statically assigned before the system runs and is fixed throughout the life cycle of the task. During system operation, tasks with higher priorities are scheduled to run first.

Semi-partitioned Scheme: A real-time scheduling scheme for multiple processors. The system statically assigns tasks to processors before running and schedules them independently on each processor. However, unlike full partitioning, semi-partitioned scheduling allows some tasks to be migrated to pre-specified processors under certain conditions.

Sporadic task model: A computing task with clear time constraints. The arrival of its jobs does not have a fixed period, but there is a minimum arrival interval. In the worst case, it can be regarded as a periodic task.

Shared resources: Hardware or software resources that multiple tasks can request simultaneously but must have exclusive access to. To ensure data integrity, each resource is protected by a specified lock. A task is allowed to access a resource only if it obtains the lock corresponding to the resource; if the resource is occupied, the task requesting the resource will wait until the resource is available again.

Schedulability: refers to the fact that all tasks in the system can be completed within the deadline.

Schedulability test: refers to a set of mathematical tools that can calculate the worst response time (i.e., from release to completion) of a task executed on a target system. The worst response time usually includes the worst time required for the task itself to execute (WCET), the interference time of local high priority tasks (local high priority interference), and the blocking time caused by the task accessing shared resources (specific explanation below).

Spin delay: In a multiprocessor system using a spin lock-based resource sharing protocol, a task on a remote processor accesses a resource, causing the task on the local processor to spin and wait for the resource. Direct spin delay refers to the situation where a task requesting a resource is directly interfered with by a remote task. Indirect spin delay refers to the situation where a low-priority task is transitively blocked by a high-priority task interfered with by a remote task.

Arrival blocking: In systems based on non-preemptive or priority boosting techniques, a high-priority task is blocked by local low-priority tasks because it cannot preempt it upon arrival.

In view of the problems existing in the prior art, the present invention proposes a task allocation method oriented to shared resources, which greatly reduces the blocking time of tasks accessing shared resources and improves the schedulability of the system.

Specifically, an aspect of an embodiment of the present invention provides a resource-aware task allocation method for a mixed-criticality partitioned real-time operating system, comprising:

Group tasks according to resource access;

According to the result of task grouping, high-criticality tasks are assigned while ensuring that the assignment result is schedulable in the high-criticality system mode;

According to the result of task grouping, the low-criticality tasks are allocated while ensuring that the allocation results are schedulable in the low-criticality system mode;

According to the assigned high-criticality tasks and low-criticality tasks, the task migration method is used to schedule the system mode switching and complete the task allocation.

Optionally, grouping the tasks according to resource access conditions includes:

Sort the shared resources from largest to smallest according to the total number of accesses to obtain the resource sorting result;

Grouping tasks according to the resource sorting result;

According to the critical level of the task, each resource task group and independent task group obtained by division is further divided.

Optionally, grouping tasks according to the resource sorting result includes:

Starting from the first resource, if a task needs to request the resource, it will be added to the task group corresponding to the resource; if the task has been added to the group, it will not be added to other task groups; tasks that do not request any resources will be treated as an independent group;

According to the critical level of the task, each resource task group and independent task group obtained by the division is further divided, including:

Each resource task group and independent task group is further divided to obtain a high-criticality task group and a low-criticality task group corresponding to each resource, as well as an independent high-criticality task group and an independent low-criticality task group.

Optionally, allocating high-criticality tasks according to the result of task grouping while ensuring that the allocation result is schedulable in the high-criticality system mode includes:

According to the result of task grouping, a high-criticality task group corresponding to each resource and an independent high-criticality group are obtained, and the tasks in the task group corresponding to each resource are sorted in ascending order according to the utilization rate under the high criticality;

Start traversing from the task group corresponding to the resource with the largest total number of accesses;

Sort the processors in ascending order according to utilization at the high criticality level;

Allocate tasks in the current task group in sequence, and assign tasks to the first schedulable processor in processor order until all tasks of the high-criticality task groups corresponding to all resources are assigned;

The tasks in the independent task group are sorted in descending order according to the utilization at the high criticality level. Before each independent task is assigned, the processors are sorted from small to large according to the utilization at the high criticality level and assigned to the first schedulable processor in processor order.

Optionally, the allocating low-criticality tasks according to the result of task grouping while ensuring that the allocation result is schedulable in the low-criticality system mode includes:

According to the result of task grouping, a low-criticality task group corresponding to each resource and an independent low-criticality task group are obtained, and the tasks in the task group corresponding to each resource are sorted in ascending order according to the utilization rate under the low criticality;

Start traversing from the task group corresponding to the resource with the largest total number of accesses;

Sort the processors, put the processors with high-criticality tasks accessing the current resources in front, and sort them in ascending order according to the utilization under low criticality, and sort the remaining processors in ascending order according to the utilization under low criticality;

Allocate tasks in the current task group in sequence, and assign tasks to the first schedulable processor in processor order until all low-criticality task groups corresponding to all resources are assigned tasks;

The tasks in the independent task group are sorted in descending order according to the utilization at the low criticality level. Before each independent task is assigned, the processors are sorted from small to large according to the utilization at the low criticality level, and the processors are traversed and assigned to the first schedulable processor.

Optionally, the scheduling of system mode switching using a task migration method according to the allocated high-criticality tasks and low-criticality tasks to complete task allocation includes:

Calculate the response time of each high-criticality task when switching modes, and check whether the response time of the task exceeds the deadline when switching modes;

When the response time of a task exceeds the deadline, check the timeout reasons of the task in turn until the task can be scheduled;

Complete the scheduling of all high-criticality tasks.

Optionally, when the response time of the task exceeds the deadline, checking the timeout reasons of the task in sequence until the task can be scheduled includes:

When the arrival blocking time of the high-criticality task during mode switching is greater than the arrival blocking time under the high-criticality level, obtain the resource that causes the maximum arrival blocking and perform the following steps:

If there is no high-criticality task accessing the resource on the processor to which the current task belongs, and only low-criticality tasks are accessing the resource: sort the processors, put the processors that can cause spin blocking for low-criticality tasks in the front, and sort the remaining processors from large to small according to the slack time; according to the processor order, migrate all low-criticality tasks accessing the resource on the processor to the first processor that can meet the conditions;

If a high-criticality task accesses the resource on the processor to which the current task belongs: all low-criticality tasks accessing the resource on the processor that blocks the task from reaching the resource will be attempted to be migrated to the processor to which the current task belongs;

If the current task is still not schedulable after executing the above steps, continue to execute the following steps:

If the resource access blocking time is greater than 0, traverse by resource number, check each processor in turn by processor number whether there is a low-criticality task accessing resources that causes spin blocking on the task, and migrate the low-criticality task accessing resources on the processor to the core where the current task is located; if this migration will not cause a new task timeout, execute the migration;

Stop when the current task is schedulable or all resources are traversed.

Another aspect of the embodiment of the present invention further provides a resource-aware task allocation device for a hybrid critical partitioned real-time operating system, comprising:

The first module is used to group tasks according to resource access;

The second module is used to allocate high-criticality tasks according to the result of task grouping while ensuring that the allocation result is schedulable in the high-criticality system mode;

The third module is used to allocate low-criticality tasks according to the result of task grouping while ensuring that the allocation result is schedulable in the low-criticality system mode;

The fourth module is used to schedule the system mode switching according to the assigned high-criticality tasks and low-criticality tasks using the task migration method to complete the task allocation.

Another aspect of an embodiment of the present invention further provides an electronic device, including a processor and a memory;

The memory is used to store programs;

The processor executes the program to implement the method described above.

Another aspect of the embodiment of the present invention further provides a computer-readable storage medium, wherein the storage medium stores a program. The program is executed by a processor to implement the above-mentioned method.

The embodiment of the present invention also discloses a computer program product or a computer program, which includes a computer instruction stored in a computer-readable storage medium. A processor of a computer device can read the computer instruction from the computer-readable storage medium, and the processor executes the computer instruction, so that the computer device executes the above method.

The specific implementation process of the present invention is described in detail below in conjunction with the accompanying drawings:

The present invention is based on a mixed-criticity system (Mixed-Criticality System) including two system execution modes (System Execution Mode, L∈{HI,LO}) of high criticality and low criticality. The system includes a group of identical processors Φ (symmetric multiprocessor) and a group of sporadic periodic tasks Γ (sporadic task). The system adopts a semi-partitioned fixed-priority scheme.

In the system, each task (represented by τ _i ) is defined by its period, deadline, worst-case execution time estimate, priority, criticality, allocation scheme, and migration scheme, namely Different from ordinary periodic tasks, the worst execution estimate of mixed critical tasks presents vector characteristics, that is, different worst time estimates exist in different system execution modes. The higher the level of system mode, the more conservative the task execution time will be ( _Ci (HI)> _Ci (LO)). The worst response time of the task in mode L is represented by _Ri (L), and the utilization of the task in mode L is represented by u _i processor The utilization rate under mode L is expressed as

At the same time, the system also contains a set of shared resources protected by spin locks (the resource set is represented by R). For a resource in the system (represented by r ^k ), c ^k (L) represents the worst execution time estimate of executing r ^k at criticality level L, and it is also assumed that c ^k (HI)>c ^k (LO). represents the number of times task τ _i accesses resource r ^k during one run; function F(·) represents the set of resources accessed by a given task, and function G(·) represents the set of tasks that access a given resource. represents the task grouping corresponding to resource r ^k , Represents a grouping of tasks that do not request resources.

The mixed criticality model assumes that the system starts from a low criticality level and all tasks are scheduled with the budget under the low criticality level. In actual operation, when a task runs for longer than the budget under this mode, the system will switch to a high criticality level and suspend all low criticality tasks.

As shown in Figure 1, the present invention includes four core steps: first, tasks are grouped based on resource access conditions; then, high-criticality tasks are assigned first according to the results of task grouping and the assigned results are ensured to be schedulable in the high-criticality system mode; then, low-criticality tasks are assigned and the assigned results are ensured to be schedulable in the low-criticality system mode; finally, task migration method is used to ensure that the tasks are scheduled in the low-criticality system mode. Ensure the schedulability when the system mode switches.

The specific steps of the present invention are as follows:

Step 1: Group tasks:

Step 1.1: Sort the shared resources by the total number of accesses from largest to smallest, i.e.

Step 2.1: Group the tasks according to the resource order in step 1.1. Starting from the first resource, if a task needs to request the resource r ^k , then add the task group corresponding to the resource r ^k If a task has been added to a group, it will not be added to other task groups. Tasks that do not request task resources are treated as an independent group.

Step 3.1: Further divide each resource task group and independent task group according to the criticality level to obtain the high criticality task group corresponding to each resource r ^k and low criticality task groups and an independent high-criticality task force and an independent low-criticality task group

Step 2: Allocation of high-criticality tasks:

Step 2.1: Based on the task grouping (Algorithm 1), the high-criticality task group corresponding to each resource is obtained and a separate high-key group Sort the tasks in the task group corresponding to each resource in ascending order according to the utilization rate _ui (HI) at the high criticality level.

Step 2.2: Start traversing from the task group corresponding to the resource with the largest total number of accesses N ^k .

Step 2.3: Set the processor utilization to the highest criticality Sort from small to large (processors with less load can be assigned more tasks from the same task group);

Step 2.4: Allocate tasks in the current task group in sequence, and assign tasks to the first schedulable processor in processor order until the task allocation of the high-criticality task group corresponding to all resources is completed. The schedulability test uses the schedulability analysis under the high-criticality mode.

Repeat steps 2.3 and 2.4 until the task allocation of the high-criticality task groups corresponding to all resources is completed.

Step 2.5: The tasks in the independent task group are sorted in descending order according to the utilization u _i (HI) under the high criticality level. Before each independent task is assigned, the processors are sorted from small to large according to the utilization under the high criticality level, and assigned to the first schedulable processor in processor order. The schedulability test uses the schedulability analysis under the high criticality level mode.

Step 3: Allocation of low-criticality tasks:

Step 3.1: The low-criticality task group corresponding to each resource obtained based on the task grouping (Algorithm 1) and a separate low-criticality task force Sort the tasks in the task group corresponding to each resource in ascending order according to the utilization rate _ui (LO) at the low criticality level.

Step 3.2: Start traversing from the task group corresponding to the resource with the largest total number of accesses N ^k .

Step 3.3: Sort the processors. The processors with high-criticality tasks accessing the resource are sorted first and ranked according to the utilization of low-criticality tasks. Sort by small to large, and the remaining processors are sorted by utilization under low criticality Sort from smallest to largest.

Step 3.4: Allocate the tasks in the current task group in sequence, and assign the tasks to the first schedulable processor in processor order. The schedulability test uses the schedulability analysis in low criticality mode.

Repeat steps 3.3 and 3.4 until the task allocation of the low-criticality task groups corresponding to all resources is completed.

Step 3.5: The tasks in the independent task group are sorted in descending order according to the utilization u _i (LO) under the low criticality level. Before each independent task is assigned, the processors are sorted from small to large according to the utilization under the low criticality level, and the processors are traversed and assigned to the first schedulable processor. The schedulability test uses the schedulability analysis under the low criticality level mode.

Step 4: Task migration method when switching modes:

When a mixed-criticality system is running, if a task's running time exceeds the worst-case time estimate, the system mode will be upgraded (i.e., mode switching). After the upgrade, the low-criticality task will be suspended, and the high-criticality task will run with a more pessimistic worst-case time. Due to the existence of shared resources, in order to ensure the integrity of shared resources, when the system mode is switched, if a low-criticality task holds a shared resource, the task will be suspended after the current resource execution is completed. If the task does not occupy a shared resource, it will be suspended directly.

When analyzing the worst response time (R _i ) of a task, we use a more pessimistic assumption to provide a safe worst response time bound. Specifically, when the mode is switched, the low-criticality task will run at the lowest priority and access all the resources it needs once before suspending. That is, for a low-criticality task τ _j , if r ^k ∈ F(τ _j ),

According to the high-criticality task allocation steps, we allocate high-criticality tasks while ensuring their schedulability in high-criticality mode, that is, R _i (HI) < D _i . When switching modes, low-criticality tasks accessing resources will block the operation of high-criticality tasks, resulting in some high-criticality tasks being unschedulable. We consider migrating low-criticality tasks to resolve their impact on high-criticality tasks during mode switching, thereby ensuring the schedulability of high-criticality tasks during mode switching.

First, determine whether the high-criticality task will time out after being interfered by the low-criticality task during mode switching.
R _i = R _i (HI) + I _i + B _i

Wherein, _Ii is the spin blocking time caused by the low-criticality task on the remote processor to _τi , and _Bi is the increased arrival blocking time suffered by _τi . Using the existing blocking time analysis method, the resource access blocking time _Ii and _Bi can be calculated.

For processor The blocking caused to task τ _i by the low-criticality task accessing resource r ^k , where ^FA (τ _i ) is the set of resources that may cause arrival blocking to task τ _i , and B _i (HI) is the arrival blocking time suffered by task τ _i in high-criticality mode.

The migration algorithm steps are as follows:

Step 4.1: Use _Ri = _Ri (HI) + _Ii + _Bi to calculate the response time _Ri of each high-criticality task during mode switching, and determine whether it exceeds the deadline _Di. Based on the updated _Ri , define the core slack time as

Step 4.2: If any task τ _i times out, check the reasons for its timeout one by one;

Step 4.2.1: If _Bi > 0, obtain the resource r ^k that causes the maximum arrival blockage _Bi and process it in two cases:

1) If there is no high-criticality task accessing the resource on the processor to which task τ _i belongs, and only low-criticality tasks are accessing the resource: sort the processors, and put the processors that can cause spin blocking for these low-criticality tasks in the front, and sort the remaining processors from large to small according to the slack time. In the order of processors, migrate all low-criticality tasks on the processor that access the resource r ^k to the first processor that can meet the conditions. The condition for migration is that there are no new timed-out tasks.

2) If there is a high-criticality task accessing the resource on the processor to which task τ _i belongs: all low-criticality tasks accessing the resource on the processor that blocks the task from reaching the resource will be attempted to be migrated to the processor to which task τ _i belongs. The migration is possible only if there are no new timed-out tasks.

Repeat step 4.2.1 until _Bi = 0 or _Ri < _Di. If the above migration is unsuccessful, proceed to step 4.2.2.

Step 4.2.2: If I _i > 0, traverse by resource number k and check each processor in turn by processor number m Is there a low-criticality task accessing resource r ^k that causes spin blocking for task τ _i , that is, if The processor Migrate the low-criticality tasks that access resource r ^k to the core where task τ _i is located. If this migration will not cause a new task timeout, perform the migration. Stop when task τ _i is schedulable (R _i <D _i ) or all resources have been traversed.

Step 4.3: If step 4.2 is completed and the task is schedulable, continue to execute step 4.2 until all high-criticality tasks are schedulable (R _i <D _i ).

In summary, compared with the prior art, the present invention has the following characteristics:

1. The solution takes into account the impact of shared resources and localizes the resources with fierce competition as much as possible, thereby reducing the resources between cores. Access conflicts can be avoided, task blocking time can be reduced, and the schedulability of the system can be improved.

2. During the allocation process, this scheme takes into account the worst running time of tasks at different critical levels in mixed critical systems (that is, tasks have different utilization rates at different critical levels, and the higher the critical level, the higher the utilization rate); it proposes a task allocation and migration method when switching between modes to ensure the schedulability of the system in all operating scenarios.

The present invention localizes the fiercely competitive shared resources through task allocation, reduces resource blocking time, and improves system schedulability. The present invention takes into account the criticality characteristics of the mixed criticality system, ensures the schedulability of each criticality mode during the allocation process, uses task migration to ensure the schedulability when switching modes, reasonably utilizes system capacity, and improves the overall schedulability of the system.

In some selectable embodiments, the function/operation mentioned in the block diagram may not occur in the order mentioned in the operation diagram. For example, depending on the function/operation involved, the two boxes shown in succession can actually be executed substantially simultaneously or the boxes can sometimes be executed in reverse order. In addition, the embodiment presented and described in the flow chart of the present invention is provided by way of example, for the purpose of providing a more comprehensive understanding of technology. The disclosed method is not limited to the operation and logic flow presented herein. Selectable embodiments are expected, wherein the order of various operations is changed and the sub-operation of a part for which is described as a larger operation is performed independently.

In addition, although the present invention is described in the context of functional modules, it should be understood that, unless otherwise specified, one or more of the functions and/or features described may be integrated into a single physical device and/or software module, or one or more functions and/or features may be implemented in separate physical devices or software modules. It is also understood that a detailed discussion of the actual implementation of each module is unnecessary for understanding the present invention. More specifically, in view of the properties, functions, and internal relationships of the various functional modules in the device disclosed herein, the actual implementation of the module will be understood within the conventional skills of the engineer. Therefore, those skilled in the art can implement the present invention set forth in the claims without excessive experimentation using ordinary techniques. It is also understood that the specific concepts disclosed are merely illustrative and are not intended to limit the scope of the present invention, which is determined by the full scope of the appended claims and their equivalents.

If the functions are implemented in the form of software functional units and sold or used as independent products, they can be stored in a computer-readable storage medium. Based on this understanding, the technical solution of the present invention, or the part that contributes to the prior art or the part of the technical solution, can be embodied in the form of a software product. The computer software product is stored in a storage medium, including several instructions for a computer device (which can be a personal computer, server, or network device, etc.) to perform all or part of the steps of the methods described in each embodiment of the present invention. The aforementioned storage media include: U disk, mobile hard disk, read-only memory (ROM, Read-Only Memory), random access memory (RAM, Random Access Memory), disk or optical disk, and other media that can store program codes.

The logic and/or steps represented in the flowchart or otherwise described herein, for example, may be considered to be used to implement An ordered list of executable instructions for a logical function may be embodied in any computer-readable medium for use by an instruction execution system, apparatus or device (e.g., a computer-based system, a system including a processor, or other system that can fetch instructions from an instruction execution system, apparatus or device and execute the instructions), or in conjunction with such instruction execution system, apparatus or device. For purposes of this specification, a "computer-readable medium" may be any device that can contain, store, communicate, propagate or transmit a program for use by an instruction execution system, apparatus or device, or in conjunction with such instruction execution system, apparatus or device.

More specific examples of computer-readable media (a non-exhaustive list) include the following: an electrical connection with one or more wires (electronic device), a portable computer disk case (magnetic device), a random access memory (RAM), a read-only memory (ROM), an erasable and programmable read-only memory (EPROM or flash memory), an optical fiber device, and a portable compact disk read-only memory (CDROM). In addition, the computer-readable medium may even be a paper or other suitable medium on which the program is printed, since the program may be obtained electronically, for example, by optically scanning the paper or other medium, followed by editing, deciphering or, if necessary, processing in another suitable manner, and then stored in a computer memory.

It should be understood that the various parts of the present invention can be implemented by hardware, software, firmware or a combination thereof. In the above-mentioned embodiments, a plurality of steps or methods can be implemented by software or firmware stored in a memory and executed by a suitable instruction execution system. For example, if implemented by hardware, as in another embodiment, it can be implemented by any one of the following technologies known in the art or their combination: a discrete logic circuit having a logic gate circuit for implementing a logic function for a data signal, a dedicated integrated circuit having a suitable combination of logic gate circuits, a programmable gate array (PGA), a field programmable gate array (FPGA), etc.

In the description of this specification, the description with reference to the terms "one embodiment", "some embodiments", "examples", "specific examples", or "some examples" means that the specific features, structures, materials or characteristics described in conjunction with the embodiment or example are included in at least one embodiment or example of the present invention. In this specification, the schematic representations of the above terms do not necessarily refer to the same embodiment or example. Moreover, the specific features, structures, materials or characteristics described may be combined in any one or more embodiments or examples in a suitable manner.

Although the embodiments of the present invention have been shown and described, it will be appreciated by those skilled in the art that various changes, modifications, substitutions and variations may be made to the embodiments without departing from the principles and spirit of the present invention, and that the scope of the present invention is defined by the claims and their equivalents.

The above is a specific description of the preferred implementation of the present invention, but the present invention is not limited to the described embodiments. Those skilled in the art may make various equivalent modifications or substitutions without violating the spirit of the present invention. These equivalent modifications or substitutions are all included in the scope defined by the claims of this application.

Claims (10)

A resource-aware task allocation method for a mixed-criticality partitioned real-time operating system, characterized by comprising: Group tasks according to resource access; According to the result of task grouping, high-criticality tasks are assigned while ensuring that the assignment result is schedulable in the high-criticality system mode; According to the result of task grouping, the low-criticality tasks are allocated while ensuring that the allocation results are schedulable in the low-criticality system mode; According to the assigned high-criticality tasks and low-criticality tasks, the task migration method is used to schedule the system mode switching and complete the task allocation. The resource-aware task allocation method for a mixed-criticality partitioned real-time operating system according to claim 1 is characterized in that the grouping of tasks according to resource access conditions comprises: Sort the shared resources from largest to smallest according to the total number of accesses to obtain the resource sorting result; Grouping tasks according to the resource sorting result; According to the critical level of the task, each resource task group and independent task group obtained by division is further divided. The resource-aware task allocation method for a mixed-criticality partitioned real-time operating system according to claim 2 is characterized in that: The grouping of tasks according to the resource sorting result includes: Starting from the first resource, if a task needs to request the resource, it will be added to the task group corresponding to the resource; if the task has been added to the group, it will not be added to other task groups; tasks that do not request any resources will be treated as an independent group; According to the critical level of the task, each resource task group and independent task group obtained by the division is further divided, including: Each resource task group and independent task group is further divided to obtain a high-criticality task group and a low-criticality task group corresponding to each resource, as well as an independent high-criticality task group and an independent low-criticality task group. The resource-aware task allocation method for a mixed-criticality partitioned real-time operating system according to claim 3 is characterized in that the high-criticality tasks are allocated based on the result of task grouping while ensuring that the allocation result is schedulable in the high-criticality system mode, comprising: According to the result of task grouping, a high-criticality task group corresponding to each resource and an independent high-criticality group are obtained, and the tasks in the task group corresponding to each resource are sorted in ascending order according to the utilization rate under the high criticality; Start traversing from the task group corresponding to the resource with the largest total number of accesses; Sort the processors in ascending order according to utilization at the high criticality level; Allocate tasks in the current task group in sequence, assigning tasks to the first schedulable processor in processor order until The task allocation to the high-criticality task groups corresponding to all resources is completed; The tasks in the independent task group are sorted in descending order according to the utilization at the high criticality level. Before each independent task is assigned, the processors are sorted from small to large according to the utilization at the high criticality level and assigned to the first schedulable processor in processor order. The resource-aware task allocation method for a mixed-criticality partitioned real-time operating system according to claim 3 is characterized in that the allocation of low-criticality tasks based on the result of task grouping while ensuring that the allocation result is schedulable in the low-criticality system mode comprises: According to the result of task grouping, a low-criticality task group corresponding to each resource and an independent low-criticality task group are obtained, and the tasks in the task group corresponding to each resource are sorted in ascending order according to the utilization rate under the low criticality; Start traversing from the task group corresponding to the resource with the largest total number of accesses; Sort the processors, put the processors with high-criticality tasks accessing the current resources in front, and sort them in ascending order according to the utilization under low criticality, and sort the remaining processors in ascending order according to the utilization under low criticality; Allocate tasks in the current task group in sequence, and assign tasks to the first schedulable processor in processor order until all low-criticality task groups corresponding to all resources are assigned tasks; The tasks in the independent task group are sorted in descending order according to the utilization at the low criticality level. Before each independent task is assigned, the processors are sorted from small to large according to the utilization at the low criticality level, and the processors are traversed and assigned to the first schedulable processor. The resource-aware task allocation method for a mixed-criticality partitioned real-time operating system according to claim 1 is characterized in that the system mode switching is scheduled using a task migration method according to the allocated high-criticality tasks and low-criticality tasks to complete the task allocation, comprising: Calculate the response time of each high-criticality task when switching modes, and check whether the response time of the task exceeds the deadline when switching modes; When the response time of a task exceeds the deadline, check the timeout reasons of the task in turn until the task can be scheduled; Complete the scheduling of all high-criticality tasks. The resource-aware task allocation method for a mixed-criticality partitioned real-time operating system according to claim 6 is characterized in that when the response time of a task exceeds the deadline, the timeout reasons of the task are checked in sequence until the task can be scheduled, comprising: When the arrival blocking time of the high-criticality task during mode switching is greater than the arrival blocking time under the high-criticality level, obtain the resource that causes the maximum arrival blocking and perform the following steps: If there is no high-criticality task accessing the resource on the processor to which the current task belongs, and only low-criticality tasks are accessing the resource: sort the processors, put the processors that can cause spin blocking for low-criticality tasks in front, and sort the remaining processors from large to small according to the slack time; according to the processor order, migrate all low-criticality tasks accessing the resource on the processor to the next processor. Move to the first processor that can satisfy the condition; If a high-criticality task accesses the resource on the processor to which the current task belongs: all low-criticality tasks accessing the resource on the processor that blocks the task from reaching the resource will be attempted to be migrated to the processor to which the current task belongs; If the current task is still not schedulable after executing the above steps, continue to execute the following steps: If the resource access blocking time is greater than 0, traverse by resource number, check each processor in turn by processor number whether there is a low-criticality task accessing resources that causes spin blocking on the task, and migrate the low-criticality task accessing resources on the processor to the core where the current task is located; if this migration will not cause a new task timeout, execute the migration; Stop when the current task is schedulable or all resources are traversed. A resource-aware task allocation device for a mixed-criticality partitioned real-time operating system, characterized by comprising: The first module is used to group tasks according to resource access; The second module is used to allocate high-criticality tasks according to the result of task grouping while ensuring that the allocation result is schedulable in the high-criticality system mode; The third module is used to allocate low-criticality tasks according to the result of task grouping while ensuring that the allocation result is schedulable in the low-criticality system mode; The fourth module is used to schedule the system mode switching according to the assigned high-criticality tasks and low-criticality tasks using the task migration method to complete the task allocation. An electronic device, characterized in that it comprises a processor and a memory; The memory is used to store programs; The processor executes the program to implement the method according to any one of claims 1 to 7. A computer-readable storage medium, characterized in that the storage medium stores a program, and the program is executed by a processor to implement the method according to any one of claims 1 to 7.