CN103309734A - Embedded task scheduling method based on priority grouping - Google Patents

Abstract

The embedded task scheduling method based on priority grouping involves the field of task scheduling in embedded systems, and solves the problem that the existing task scheduling method is cumbersome to operate, requires a large amount of calculation process and storage space, and consumes a lot of resources, which is not easy for developers to understand and understand. Modified question. The steps include: grouping N tasks according to priority; searching according to group priority from high to low, and retrieving the highest group with ready tasks, and obtaining the ready task with the highest priority as the task to be switched; Obtain information about tasks to be switched and perform task switching. The invention can be widely applied to task scheduling of embedded systems.

Description

Embedded Task Scheduling Method Based on Priority Grouping

technical field

The invention relates to the field of task scheduling in embedded systems.

Background technique

With the rapid development of software and hardware, the functions of modern embedded devices have become increasingly powerful. As the functions implemented by embedded devices become more and more complex, the traditional single-task model can no longer meet the needs. Therefore, an operating system is implemented in embedded devices, which manages resources and schedules various tasks uniformly through the operating system. For the embedded field, the operating system used is required to meet the requirements of good stability and fast response speed to deal with various situations that have strict requirements on time.

Task scheduling is one of the cores of the embedded operating system, and its main function is to select a ready task from multiple user tasks, and then transfer to the user task for execution. Task scheduling in embedded operating systems is generally based on priority scheduling, that is, each task will be given a priority according to its importance, and the scheduler in the embedded system will select the ready task with the highest priority to run. However, the existing task scheduling methods are cumbersome to operate and require a large amount of calculation process and storage space.

Contents of the invention

In order to solve the problem that the existing task scheduling method is cumbersome to operate, requires a large number of calculation processes and storage space, consumes a lot of resources, and is not easy for developers to understand and modify, and thus provides a task scheduling method based on priority grouping.

An embedded task scheduling method based on priority grouping, which includes the following steps:

Step 1: group N tasks according to priority; said N tasks are sorted according to priority level and divided into P priority groups, that is, each group a priority;

The tasks are sorted according to the level of priority from high to bottom or from low to high;

Step 2: Retrieve according to group priority from high to low, and retrieve the highest group with ready tasks, and obtain the ready task with the highest priority as the task to be switched;

The tasks are activated and terminated by activating tasks and terminating tasks, where:

Activation task, which is used to activate the priority task to make it a ready task;

Terminate task, which is used to terminate the ready task to make it an unready task;

Step 3: Obtain the task information to be switched and perform task switching.

The invention realizes the embedded task scheduling based on priority grouping. The invention has the advantages of high dispatching efficiency, small storage space, simple structure and the task dispatching method of the embedded real-time system which is suitable for changing task comparison. The method of the invention can save general search time and search times, and make the number of tasks that can be stored unlimited.

Fig. 1 is the flowchart of the embedded task scheduling method based on priority grouping of the present invention;

FIG. 2 is a flow chart of executing task switching described in Embodiment 3;

FIG. 3 is a flowchart of the activation task described in Embodiment 4;

Fig. 4 is a flow chart of terminating tasks described in Embodiment 5;

Fig. 5 is an example diagram of a scheduling model of a specific embodiment.

Detailed ways

Specific implementation mode 1, this specific implementation mode will be described with reference to FIG. 1 . An embedded task scheduling method based on priority grouping, which includes the following steps:

个优先级；Step 1: group N tasks according to priority; said N tasks are sorted according to priority level and divided into P priority groups, that is, each group

a priority;

The tasks are sorted according to the level of priority from high to bottom or from low to high;

Step 2: Retrieve according to group priority from high to low, and retrieve the highest group with ready tasks, and obtain the ready task with the highest priority as the task to be switched;

The tasks are activated and terminated by activating tasks and terminating tasks, where:

Activation task, which is used to activate the priority task to make it a ready task;

Terminate task, which is used to terminate the ready task to make it an unready task;

Step 3: Obtain the task information to be switched and perform task switching.

Embodiment 2. The difference between this embodiment and Embodiment 1 is step 3: obtaining task information to be switched including task status information, task context information and task control information;

Task status information, used to identify the task's own information;

Task context information, used to save on-site information during the scheduling process;

Task control information for task scheduling and management;

The task status information includes the priority of the task, the current state of the task and the task type;

The task context information includes the contents of the general register, the contents of the control register, the user stack pointer and the kernel stack pointer;

The task control information includes task scheduling related information, inter-task communication related information and task resource usage information.

Specific embodiment three, this specific embodiment is described in conjunction with Fig. 2, the difference between this specific embodiment and specific embodiment two is that the execution task switching process described in step three is:

Step A1: a step for obtaining a task switching start signal;

Step A2: a step for disabling interrupts;

Step A3: Used to save the current task context information

Step A4: a step for setting the task to be switched as the current task;

Step A5: a step for loading the context information of the task to be switched;

Step A6: a step for enabling interrupts and performing task switching.

Embodiment 4. This embodiment is described in conjunction with FIG. 3. The difference between this embodiment and Embodiment 1 or 3 is the activation task, which is used to activate the priority task and make it a ready task process:

Step B1: a step for obtaining the priority of the task to be activated;

Step B2: a step for judging whether the task priority is valid; if so, enter step B3, otherwise exit the process;

Step B3: a step for changing the task state to a ready state;

Step B4: a step for putting the task into a priority queue;

Step B5: It is used to judge whether the number of the priority of the task is greater than the highest priority of the group it belongs to; if so, go to step B6, otherwise go to step B7;

Step B6: a step for updating the highest priority number of the group to which the task belongs;

Step B7: a step for judging the current interrupt state; if the interrupt is off, the process is exited, and if the interrupt is on, the task is switched.

Embodiment 5. This embodiment is described in conjunction with FIG. 4. The difference between this embodiment and Embodiment 4 is that the termination task is used to terminate the ready task and make it become an unready task. The process is as follows:

Step C1: a step for obtaining a task termination signal;

Step C2: a step for judging the current interrupt state; if the interrupt is off, exit the process, and if the interrupt is on, enter C3.

Step C3: a step for setting the current task as a pending state;

Step C4: a step for removing the current task from the ready queue;

Step C5: judging whether the number of the priority of the terminated task is greater than the highest priority of the group it belongs to; if so, go to step C6, otherwise go to step C7;

Step C6: a step for updating the highest priority number of the group to which the terminated task belongs;

Step C7: a step for performing task switching.

执行一次激活任务时的代价为一次比较操作，执行一次终止任务的平均代价为

可知，系统进行调度任务所花费的总的代价为

且当时，调度所花费的代价最小，而且随着系统中任务数量的减小，任务调度所需的代价减小。The average cost of performing task switching in the present invention is

The cost of executing an activation task is a comparison operation, and the average cost of executing a termination task is

It can be seen that the total cost for the system to schedule tasks is

And when When , the cost of scheduling is the smallest, and as the number of tasks in the system decreases, the cost of task scheduling decreases.

A specific embodiment is described in conjunction with Fig. 5:

Assume that the tasks are numbered according to the priority, from 0 to 63. The larger the number, the higher the priority. There will be 8 groups according to the number from small to large, and each group has 8 priorities. At a certain moment when the system is running, there are 56, 57, 58, and 59 ready tasks in priority group 7, among which the highest priority of ready is 59, and there is no ready priority in priority group 6, and then determine the ready tasks of each group in turn The highest priority among tasks.

When a task timing interrupt occurs in the system, it first judges whether there is a ready task. If there is no ready task, run the idle task. When there is a ready task, start to select the task with the highest priority. From the highest priority group to the lowest, check whether there are ready tasks in the group. The highest priority of the ready task in priority group 7 is 59. Therefore, 59 is selected as the highest priority number of the currently ready task, and the task control module of task 59 is found according to the task scheduling related organization, and the scheduler performs task switching and starts to execute task 59 Task-defined user programs.

When activating a task whose priority is task No. 43, task No. 43 belongs to priority group 5. Originally, the highest priority in priority group 5 was task No. 42. At this time, task No. 43 has a higher priority than task No. 42. It has a higher priority, so the update priority group 5 highest ready priority task number is updated to No. 43. When activating a task whose priority is task No. 26, task No. 26 belongs to priority group 3, and the highest priority in the original priority group 3 is task No. 31. At this time, the priority of task No. 26 is higher than that of task No. 31. Small, so the priority table is not updated.

When terminating a task with a task priority of 42, task No. 42 belongs to priority group 5, and the highest priority in priority group 5 is task No. 42. At this time, the terminated task No. 42 is the highest priority in priority group 5. In this case, it is necessary to find out the task with the highest priority among the remaining ready tasks in this group, so update the number of the task with the highest ready priority in priority group 5.

Comparing the embedded task scheduling method based on priority grouping of the present invention with the scheduling algorithm of μC/OS-II: μC/OS-II is an excellent operating system in the embedded field, especially in the scheduling algorithm. Since μC/OS-II only supports 64 fixed priority numbers, N=64 and P=8 will be taken in the algorithm based on priority grouping, and the comparison results are as follows:

It can be seen from the comparison that compared with the μC/OS-II scheduling algorithm, the priority-based packet scheduling algorithm saves a lot of space and obtains high flexibility, but the time cost is indeed very small. Moreover, in practical applications, the number of priorities used generally does not exceed 64, so the performance of the scheduling algorithm based on priority grouping will be very good.

Claims (5)

1. based on the embedded task scheduling method of priority grouping, it is characterized in that it comprises the steps: Step 1: group N tasks according to priority; said N tasks are sorted according to priority level and divided into P priority groups, that is, each group

a priority; The tasks are sorted according to the level of priority from high to bottom or from low to high; Step 2: Retrieve according to group priority from high to low, and retrieve the highest group with ready tasks, and obtain the ready task with the highest priority as the task to be switched; The tasks are activated and terminated by activating tasks and terminating tasks, where: Activation task, which is used to activate the priority task to make it a ready task; Terminate task, which is used to terminate the ready task to make it an unready task; Step 3: Obtain the task information to be switched and perform task switching. 2. The task scheduling method based on priority grouping according to claim 1, characterized in that step 3: obtaining task information to be switched includes task status information, task context information and task control information; Task status information, used to identify the task's own information; Task context information, used to save on-site information during the scheduling process; Task control information for task scheduling and management; The task status information includes the priority of the task, the current state of the task and the task type; The task context information includes the contents of the general register, the contents of the control register, the user stack pointer and the kernel stack pointer; The task control information includes task scheduling related information, inter-task communication related information and task resource usage information. 3. The task scheduling method based on priority grouping according to claim 2, characterized in that the execution task switching process described in step 3 is: Step A1: a step for obtaining a task switching start signal; Step A2: a step for disabling interrupts; Step A3: Used to save the current task context information Step A4: a step for setting the task to be switched as the current task; Step A5: a step for loading the context information of the task to be switched; Step A6: a step for enabling interrupts and performing task switching. 4. according to claim 1 or 3 described task scheduling methods based on priority grouping, it is characterized in that activation task is used to activate priority task and make it become ready task process as: Step B1: a step for obtaining the priority of the task to be activated; Step B2: a step for judging whether the task priority is valid; if so, enter step B3, otherwise exit the process; Step B3: a step for changing the task state to a ready state; Step B4: a step for putting the task into a priority queue; Step B5: It is used to judge whether the number of the priority of the task is greater than the highest priority of the group it belongs to; if so, go to step B6, otherwise go to step B7; Step B6: a step for updating the highest priority number of the group to which the task belongs; Step B7: a step for judging the current interrupt state; if the interrupt is off, the process is exited, and if the interrupt is on, the task is switched. 5. The task scheduling method based on priority grouping according to claim 4, characterized in that the termination task is used to terminate the ready task and make it become an unready task process as follows: Step C1: a step for obtaining a task termination signal; Step C2: a step for judging the current interrupt state; if the interrupt is off, exit the process, and if the interrupt is on, enter C3. Step C3: a step for setting the current task as a pending state; Step C4: a step for removing the current task from the ready queue; Step C5: judging whether the number of the priority of the terminated task is greater than the highest priority of the group it belongs to; if so, go to step C6, otherwise go to step C7; Step C6: a step for updating the highest priority number of the group to which the terminated task belongs; Step C7: a step for performing task switching.

Images