CN1737764A - Task Scheduling Method of Embedded Real-time Operating System Supporting OSEK Standard - Google Patents

Abstract

This invention relates to one task dispatching optimization method to support OSEK standard imbedded operation system, which comprises the following steps: a, analyzing each switch situations according to task situation; b, dividing the dispatching process into four steps: finding optimization task in the prepare task; storing the current operation task environment; demoting the CPU needle; restoring optimization task running environment; c, optimizing the dispatching strategy according to four steps covering situation into four types of strategy; d, selecting different dispatching strategy according to real dispatching situation.

Description

Task Scheduling Method of Embedded Real-time Operating System Supporting OSEK Standard

technical field

The invention relates to an embedded real-time operating system technology, and mainly relates to a task scheduling optimization method of an embedded operating system supporting the OSEK standard.

Background technique

With the rapid development of software and hardware technology, embedded operating systems have been applied to various fields, such as automatic control, transportation, aerospace and so on. The biggest difference between embedded real-time operating system (Real-Time Operating System, RTOS for short) and other common systems is to strictly satisfy the relationship between transactions and time. For example, the control part of large-scale equipment and the electronic control system of automobiles all require the real-time operating system adopted to be able to respond quickly and dispatch quickly to deal with various situations with strict time requirements.

Task scheduling is the core and most critical part of the embedded real-time operating system, and the scheduling efficiency directly affects the real-time performance of the RTOS. To measure the technology of an RTOS, the most important indicator is the scheduled task switching time T _s .

Most of the commercial real-time operating systems with a relatively high market share are multi-task real-time microkernel structures, and adopt a priority-based preemptive scheduling strategy. In various scheduling situations, call the same function to complete task switching. The real-time task scheduling method provided by the open source uC/OS-II is completed by using the scheduling function OSSched(). In OSSched(), first find the task with the highest priority, and then use the macro to call OS TASK_SW to complete the actual task switching process through the system soft interrupt, push the running environment of the suspended task into the stack, and then run the higher The execution context of the priority task is restored from the stack.

In fact, this is the work that needs to be done in the most complicated task switching situation, that is, the currently running task is interrupted, the running environment of the current task needs to be saved, and then switched to a previously running task, the original running environment needs to be restored, saved And restoring the running environment occupies most of the time of the whole task switching. For some simple scheduling points, such as ending the current task and then running the newly activated task, the process of saving and restoring the running environment is a waste. This is because ending a task means that the task has completed its function and does not need to save its running environment, while an activated task has just started running and has no previous running environment. This also shows that the unified scheduling is adopted regardless of the status of the switched tasks, which will greatly affect the scheduling efficiency of the embedded real-time operating system.

Contents of the invention

The purpose of the present invention is to provide a kind of task scheduling optimization method of the embedded operating system that supports OSEK standard for above-mentioned defect.

The scheme adopted by the present invention to solve its technical problems is: by analyzing in detail the task switching state of the operating system supporting the OSEK standard, subdividing the situation of different scheduling points, adopting a special scheduling strategy for each scheduling point, so that the task switching time is within Significantly reduced in most cases, greatly optimizing the timing performance of real-time operating systems.

The realization steps of the present invention are as follows:

1) Analyze various scheduling switching situations according to task status:

1.1), in the OSEK standard, according to the classification of task status, the system is divided into two situations: BCC1 (basic task) and ECC1 (extended task); among them, the task status in BCC1 includes three situations: running, ready, suspended, The task state in ECC1 includes four situations: running, ready, waiting, and suspended. The present invention subdivides the task ready state into an intermediate state and an initial state. The intermediate state is the state in which the task enters the ready state after half of the task is preempted or waiting for an event to occur. The initial state is that the task is activated from the suspension to the ready state. Or the ready state that the task enters directly when the system starts;

1.2), the scheduling situation under BCC1 is divided into the following three types:

Scheduling situation 1: The current task finishes running and enters the suspended state, and the high-priority task that is about to run is in the initial state; there is no need to save the current task running environment, and the next high-priority task can be run after directly performing operations such as pointer assignment;

Scheduling situation 2: The current task finishes running and enters the suspended state, and the high-priority task that is about to run is in the intermediate state; there is no need to save the current task running environment, and after performing operations such as pointer assignment, restore the running environment of the next high-priority task, and then run;

Scheduling situation 3: The current task is preempted and enters the ready state, and the high-priority to be run is the initial state; the high-priority task can be run after saving the current task running environment and performing operations such as pointer assignment.

1.3) For scheduling under ECC1, in addition to the above 1.2), add the following three:

Scheduling situation 4: The current task enters the waiting state, and the high-priority task that is about to run is in the intermediate state; after saving the running environment of the current task, performing pointer assignment and other operations, restore the running environment of the next high-priority task, and then run;

Scheduling situation 5: The current task enters the waiting state, and the high-priority task to be executed is the initial state; the high-priority task can be run after saving the current task running environment and performing operations such as pointer assignment;

Scheduling situation 6: The current task is preempted and enters the ready state, and the high-priority task to be run is in the intermediate state, and the task enters the intermediate state because the event it is waiting for occurs; save the current task running environment, perform pointer assignment, etc. After the operation, restore the running environment of the high-priority task and run again;

2), the scheduling process can be divided into the following four steps:

2.1), find the highest priority task in the ready task;

2.2), save the running environment of the current running task;

2.3), carry out CPU occupancy pointer assignment, that is, exchange CPU occupancy right;

2.4), restore the operating environment of the highest priority task;

3. According to the coverage of the four steps of the scheduling process, optimize the scheduling strategy, which is divided into the following four categories:

3.1), scheduling strategy A: the simplest case, only 2.1) and 2.3) of the scheduling process steps;

3.2), scheduling strategy B: in general, only 2.1), 2.2), 2.3) of the scheduling process steps are done;

3.3), scheduling strategy C: in general, only 2.1), 2.3), and 2.4) of the scheduling process steps are done;

3.4), scheduling strategy D: the most complicated situation, do 2.1), 2.2), 2.3), 2.4) of all scheduling process steps;

4. According to the actual scheduling situation when the task is running, different scheduling strategies are selected: the time T spent in the scheduling of each situation is different according to the selected strategy, D corresponds to the most T _SD , and A corresponds to T _SA At least, T _SB and T _SC corresponding to B and C are intermediate values.

Significant advantage of the present invention:

The task switching time of the unified function scheduling method is set as T _S . It can be seen intuitively from the analysis that the optimal scheduling strategy of the present invention involves less processes and has the following obvious advantages in scheduling time, which obviously optimizes the performance of system scheduling :

T _SA < T _S ,

T _SB <T _S ,

T _SC < T _S ,

And T _SD and T _S are basically the same.

Description of drawings

Figure 1 BCC1 basic task state transition diagram;

The refined BCC1 basic task state transition diagram of Fig. 2 of the present invention;

Figure 3 ECC1 extended task state transition diagram;

ECC1 extended task state transition diagram after refinement of Fig. 4 of the present invention;

Embodiment 1 of the present invention of Fig. 5;

Embodiment 2 of the present invention of Fig. 6;

Detailed ways

The invention will be further introduced below in conjunction with the accompanying drawings and two embodiments. The task scheduling optimization method of the embedded operating system supporting the OSEK standard, the implementation steps are as follows:

1. Carefully analyze various scheduling switching situations according to the task status.

In the OSEK standard, according to the different task status classifications, the system is divided into BCC1 (basic task) and ECC1 (extended task).

According to the OSEK standard, the task state in BCC1 includes three situations: running, ready, and suspended. Tasks in the running state refer to tasks that currently occupy the CPU. Tasks in the ready state are tasks that are ready to run and only wait for CPU time, or tasks that are preempted by other tasks after running halfway and are waiting for CPU time. Tasks in the suspended state A task is a task that has finished running by itself or has just been generated and is waiting to be activated.

The task state in ECC1 includes four situations: running, ready, waiting, and suspended. A wait state is a state in which a task is waiting for an event to occur. The other three states are the same as the case of BCC1.

The basic task state transition relationship of BCC1 is shown in Figure 1. The task ready state can be subdivided into intermediate state and initial state. The intermediate state is the state in which the task enters the ready state after it is preempted half way through its operation. The initial state is the state in which the task enters the ready state directly when the task is activated from suspend or when the system starts. The refined BCC1 task state transition relationship is shown in Figure 2.

Therefore, the scheduling situation under BCC1 can be divided into the following types: (RunningTask represents the currently running task, HighestTask represents the highest priority task that has been found, PCPUCur represents the pointer of the task currently occupying the CPU, PCPUCur points to RunningTask before scheduling)

Scheduling situation 1: RunningTask enters the suspended state after running, and HighestTask is in the initial state.

You don't need to save the running environment of the RunningTask, and you can run the HighestTask task body after directly performing operations such as assignment of PCPUCur (pointing PCPUCur to HighestTask). This is the simplest case, only assigning pointers, without saving or restoring the relevant operating environment.

Scheduling situation 2: RunningTask enters the suspended state after running, and HighestTask is in the intermediate state.

There is no need to save the running environment of RunningTask, after performing operations such as assignment of PCPUCur, restore the original running environment of HighestTask and continue running. This is a general situation, which requires the assignment of pointers to restore the relevant operating environment without saving the current operating environment.

Scheduling situation 3: RunningTask is preempted and enters the ready state, and HighestTask is in the initial state.

Save the RunningTask operating environment, and perform operations such as PCPUCur assignment to run the HighestTask task body. This is also a relatively general situation, which requires the assignment of pointers and the need to save the current operating environment, but does not need to restore the original operating environment.

In the case of ECC1, the extended task state transition relationship is shown in Figure 3. Similar to BCC1, the task ready state is divided into intermediate state and initial state. However, in addition to being preempted by the task, the intermediate state may also be caused by the waiting event of the task in the waiting state, and the task enters the ready state, which also belongs to the intermediate state. The refined ECC1 task state transition relationship is shown in Figure 4.

Because of the added waiting state, after analysis, we can know that in addition to the four existing scheduling situations under BCC1, there are three other situations in ECC1:

Scheduling situation 4: RunningTask enters the waiting state, and HighestTask is in the intermediate state.

Save the running environment of RunningTask, and after performing operations such as PCPUCur assignment, restore the original running environment of HighestTask and continue running. This is the most complicated scheduling situation, all three operations are required for pointer assignment, saving the current operating environment, and restoring the original operating environment.

Scheduling situation 5: RunningTask enters the waiting state, and HighestTask is in the initial state.

After saving the running environment of RunningTask and performing operations such as PCPUCur assignment, the function body can be run directly without restoring the running environment. This is the same as scheduling case 3 in terms of operational complexity.

Scheduling situation 6: RunningTask is preempted to enter the ready state, HighestTask is in the intermediate state, and HighestTask enters the intermediate state because the event it is waiting for occurs.

Save the running environment of RunningTask, and after performing operations such as PCPUCur assignment, restore the original running environment of HighestTask and continue running. This is the same as scheduling case 4 in terms of operational complexity, and is also the most complicated case.

2. Segment the scheduling process

Analyzing and synthesizing various situations, the scheduling process can be divided into the following four steps:

1. Find the highest priority task (HighestTask) in the ready task and prepare to switch (necessary step)

2. Save the running environment of the current running task (RunningTask) (optional step)

3. Perform pointer assignment of PCPUCur, that is, exchange CPU possession (necessary steps)

4. Restore the operating environment of the highest priority task (HighestTask) (optional step)

3. Classify scheduling strategies.

According to the coverage of the four steps of the scheduling process, the scheduling strategies are divided into the following four categories:

Scheduling strategy A: In the simplest case, only steps 1 and 3 of the scheduling process are performed.

Scheduling strategy B: In general, only do steps 1, 2, and 3 of the scheduling process.

Scheduling strategy C: In general, only do steps 1, 3, and 4 of the scheduling process.

Scheduling strategy D: In the most complicated case, do steps 1, 2, 3, and 4 of all scheduling processes.

4. Select an optimized scheduling strategy according to the actual scheduling situation when the task is running.

The time T spent in scheduling in each case varies according to the selected strategy. D corresponds to T _SD the most, A corresponds to T _SA the least, and B and C correspond to T _SB and T _SC as intermediate values.

Embodiment 1: as shown in Figure 5. The operating system in the BCC1 state adopts the full preemption method. There are three basic tasks, P1, P2, and P3, and the priorities are arranged from high to low, that is, P1 has the highest priority, P2 takes the second place, and P3 has the lowest priority.

The system starts at time t0. At this time, task P1 is suspended, P2 and P3 are ready, P2 has a higher priority and runs first, and P3 is in the initial state of the ready state. At time t1, the first scheduling occurs, the current task P2 finishes running, and the initial high-priority task P3 runs. This is the simplest scheduling situation, and the optimized scheduling strategy A is adopted.

P3 runs until it activates P1. Because the priority of P1 is higher than that of P3, P3 is preempted, the second scheduling occurs at time t2, P3 enters the intermediate state of the ready state, and P1 runs. Because P3 has not finished running, it needs to save its context when it is preempted. P1 is activated directly from suspension and enters the ready state, so scheduling strategy B is adopted.

P1 has been running until the end, and the third scheduling occurs at time t3. Only P3 is currently in the ready task, and P3 gets the CPU and runs. Because P1 enters the suspended state after running, there is no need to save its running environment. However, P3 starts running from the intermediate state of the ready state, so it needs to restore its operating environment, so scheduling strategy C is adopted.

On the CME555 development board, the operating system using the unified scheduling function and the optimized scheduling strategy of the present invention is compared and run, and the CPU is MPC555 with a frequency of 40MHz. On the logic analyzer, using a sampling frequency of 100M, the task switching time at each moment is tested as shown in Table 1 below: Scheduling time Task switching time when unified scheduling function (us) After optimizing the scheduling strategy contrast effect Task switching time (us) Scheduling strategy t1 7.5 1 A T _SA is significantly smaller than T _S t2 7.5 4.5 B T _SB is significantly smaller than T _S t3 7.5 4.5 C T _SC is significantly smaller than T _S

Table 1

Embodiment 2: On the basis of Embodiment 1, look at Embodiment 2 again. As shown in Figure 6. Embodiment 2 is an operating system in the ECC1 state, which adopts the full preemption mode. There are three basic tasks, P4, P5, and P6, and the priorities are arranged from high to low, that is, P4 has the highest priority, P5 is the second, and P6 has the lowest priority. For simplicity of illustration, Example 2 only highlights the scheduling situation of the "waiting" state.

The system starts at time t0, task P4 is suspended at this time, P5 and P6 are both ready, P5 has the highest priority and runs first, and at this time P6 is in the initial state of the ready state. At time t1, the operation of P5 ends, the first scheduling occurs, and P6 runs, which is similar to the time t1 of instance 1, and the scheduling strategy A is adopted.

P6 runs until it activates P4. Because the priority of P4 is higher than that of P6, P6 is preempted, the second scheduling occurs at time t2, P6 enters the intermediate state of the ready state, and P4 runs. Similar to time t2 of Example 1, scheduling strategy B is adopted.

P4 runs until it waits for event 1. That is, the second scheduling occurs at time t3, P4 enters the waiting state, and P6 runs. Because P4 enters the waiting state but has not finished running, it needs to save its running environment. At the same time, P6 enters running from the intermediate state of the ready state, and also needs to restore the running environment, so the scheduling strategy D is adopted, which is the most complicated scheduling situation. .

P6 runs until it sets event 1. P4 enters the intermediate state of the ready state because the waiting event 1 occurs. Because P4 has a high priority, the third scheduling occurs at time t4, P6 is preempted and enters the intermediate state of the ready state, and P4 runs. Because the P6 operating environment needs to be saved, and P4 enters the running state from the waiting state to the ready state, and its operating environment needs to be restored, which is also the most complicated scheduling situation. Scheduling strategy D is adopted.

Also on the CME555 development board, compare and run the operating system using the unified scheduling function and the optimized scheduling strategy of the present invention.

The task switching time at each moment obtained from the test is shown in Table 2 below: Scheduling time Task switching time when unified scheduling function (us) After optimizing the scheduling strategy contrast effect Task switching time (us) Scheduling strategy t1 7.5 1 A T _SA is significantly smaller than T _S t2 7.5 4.5 B T _SB is significantly smaller than T _S t3 7.5 7.8 D. T _SD and T _S are basically the same t4 7.5 7.8 D. T _SD and T _S are basically the same

Table 2

Claims (4)

1, a kind of task scheduling optimization method of supporting the embedded OS of OSEK standard, it is characterized in that: performing step is as follows:

1), analyze all kinds of scheduling switch instances according to task status:

1.1), in the OSEK standard according to the difference of task status classification, system is divided into two kinds of situations of BCC1 (basic task), ECC1 (expansion task); Wherein the task status among the BCC1 comprises three kinds of situations: operation, ready, hang up, the task status among the ECC1 comprises four kinds of situations: operation, ready, wait for, hang up; The ready state of task is subdivided into intermediate state and initial state, promptly to be task run enter ready state to intermediate state after half incident of being seized or waiting for takes place, the ready state that initial state is task task directly enters when hang-up is activated into ready state or system start-up;

1.2), the scheduling situation under BCC1 is divided into following three kinds:

Scheduling situation 1: the current task end of run enters suspended state, and the high-priority task that is about to operation is an initial state; Need not preserve current task running environment, directly carry out operation such as pointer assignment after, can move back one high-priority task;

Scheduling situation 2: the current task end of run enters suspended state, and the high-priority task that is about to operation is an intermediate state; Need not preserve current task running environment, carry out operation such as pointer assignment after, recover the running environment of back one high-priority task, rerun;

Scheduling situation 3: current task is seized enters ready state, and the high priority that is about to operation is an initial state; Preserve current task running environment, carry out to move high-priority task after the operation such as pointer assignment.

1.3), the scheduling situation under ECC1, except that above-mentioned 1.2), add following three kinds again:

Scheduling situation 4: current task enters waiting status, and the high-priority task that is about to operation is an intermediate state; Preserve current task running environment, carry out operation such as pointer assignment after, recover the running environment of back one high-priority task, rerun;

Scheduling situation 5: current task enters waiting status, and the high-priority task that is about to operation is an initial state; Preserve current task running environment, carry out to move high-priority task after the operation such as pointer assignment;

Scheduling situation 6: current task is seized enters ready state, the high-priority task that is about to operation is an intermediate state, and this task is to have entered intermediate state because the incident of its wait has taken place, preserve current task running environment, after carrying out operation such as pointer assignment, recover the running environment of high-priority task, rerun;

2), can be divided into following four steps to scheduling process:

2.1), in ready task, find the task of limit priority;

2.2), preserve the running environment of current operation task;

2.3), carry out CPU and take pointer assignment, promptly exchange the CPU right of possession corporeal right;

2.4), recover the running environment of limit priority task;

3), according to the coverage condition of four steps of scheduling process, the Optimization Dispatching strategy is divided into following four classes:

3.1), scheduling strategy A: simple scenario, only do the scheduling process step 2.1), 2.3);

3.2), scheduling strategy B: generalized case, only do the scheduling process step 2.1), 2.2), 2.3);

3.3), scheduling strategy C: generalized case, only do the scheduling process step 2.1), 2.3), 2.4);

3.4), scheduling strategy D: complex situations, do whole scheduling process steps 2.1), 2.2), 2.3), 2.4);

4), the difference of actual schedule situation during according to task run, select different scheduling strategies for use: the dispatching office consumed time T of every kind of situation is different different according to selected strategy, the T of D correspondence _SDAt most, the T of A correspondence _SAMinimum, the T of B and C correspondence _SB, T _SCBe intermediate value.

2, the task scheduling optimization method of the embedded OS of support according to claim 1 OSEK standard is characterized in that: the state of task be divided into operation, ready, hang up, four kinds of waits.The task of running status is meant the task of the current CPU of taking, the task of ready state be carried out operation prepare, only etc. CPU time task or move half back by other task preemption, again in the task of waiting for CPU time, the task of suspended state be voluntarily end of run or just produced and etc. task to be activated; The task of waiting status is the task of waiting for that a certain incident takes place.Ready state is subdivided into intermediate state and initial state again.The task of attitude and initial state is different to the environment requirement of resuming operation because mediate, and these two kinds of different states were optimized when scheduling strategy switched at task.For the task of initial state, directly remove the step of the environment that resumes operation, thereby reduce the time of scheduling, improve performance.

3, the task scheduling optimization method of the embedded OS of support OSEK standard according to claim 1, it is characterized in that: operating system adopts the mode of seizing entirely, so the task switching point does not occur over just after the task run end, when also occurring in the task preemption low priority task of high priority.These two kinds of scheduling situations also are different to the requirement that whether needs to preserve current operation task running environment.When task run finishes to dispatch, because finished all operations, so do not need to preserve its running environment.And being seized of task is not also finished all operations, needs to continue in due course operation, so system need preserve running environment for it.

4, the task scheduling optimization method of the embedded OS of support OSEK standard according to claim 1 is characterized in that: OSEK standard code, the task status under the ECC1 operating system have a kind of waiting status that is.Task enters waiting status because waiting for the generation of some incidents, initiatively abandons CPU, and follow-up reforwarding row takes place waiting event.Wait for the scheduling that takes place because of task, the task of entering waiting status is not finished all operations yet, need continue operation after the incident of waiting for takes place, so system also will preserve running environment for it.

Images