CN107589993A - A kind of dynamic priority scheduling algorithm based on linux real time operating systems - Google Patents

Abstract

The invention relates to a dynamic priority scheduling algorithm based on a linux real-time operating system, which is characterized in that it comprises the following steps: when a real-time task is added to the task queue, the current recovery time is updated and the state of the current task is obtained, and the real-time task enters the cache memory module ; When the real-time task exceeds the limit, call the SLAD or BACKSLASH algorithm, and count in the cache memory module; otherwise call the EDF algorithm, and count in the cache memory module; the cache memory module calculates the frequency of the real-time task overrun in the set time period; According to the frequency of real-time tasks exceeding the limit, it is decided to directly schedule the SLAD or BACKSLASH algorithm, or schedule the EDF algorithm, and update the task priority and next recovery time. In this way, the advantages of the EDF algorithm are effectively used when dealing with normal task loads, which are easy to implement and occupy less processor resources.

Description

A dynamic priority scheduling algorithm based on linux real-time operating system

technical field

The invention belongs to the technical field of real-time operating systems, and in particular relates to a dynamic priority scheduling algorithm based on a linux real-time operating system.

Background technique

Among many real-time operating systems, Linux-based real-time operating systems are increasingly popular due to the open source code and the stability of Linux systems. But Linux itself is not a real real-time operating system. It must improve its real-time performance by making corresponding improvements to the Linux operating system, so that it has the real-time and reliability that meet the requirements of real-time systems.

The correct behavior of a real-time system depends not only on the correctness of the settlement result, but also on the time it takes to obtain this result. The fundamental properties of real-time systems are the determinism of task response time and the high throughput of system processing tasks. The application fields of real-time systems are very extensive, and different applications have different requirements for time determinism. Besides having to have deterministic response times, other important properties of real-time systems include concurrency, predictability, and reliability. Concurrency means that a real-time system must be able to handle multiple external inputs within a specified period of time. Predictability is essentially a guarantee of response time determinism. The nature of external input is concurrency and random distribution. Each input triggers the real-time system to generate corresponding actions, and the flow of these actions and the required processor time are predictable. Deterministic response times are only guaranteed in this case.

Real-time scheduling algorithm is the basic means for real-time systems to solve concurrency and ensure predictability. The real-time scheduling algorithm determines the processing sequence for the concurrent external input according to the scheduling strategy, and allocates system resources for each processing operation according to the sequence. Another main function of the real-time scheduling algorithm is to determine whether the existing resources of the system meet the time certainty of processing operations according to the schedulable conditions. Different from the general scheduling algorithm, the real-time scheduling algorithm first ensures that all ready processing operations can be completed before the specified time limit, and then processes as many external events as possible to improve the resource utilization of the system. How to improve the utilization of system resources on the premise of ensuring time determinism is a hot issue in the research of real-time scheduling algorithms.

The classic EDF (Earliest Deadline First) algorithm is a priority-based dynamic scheduling algorithm. Although this algorithm can ensure that there is no idle time for the processor before the deadline of a certain task cannot be met, so as possible Guaranteeing the real-time nature of task scheduling can theoretically optimize the schedulable load, but it cannot solve the overload problem. Once overload occurs, it will cause the CPU to spend a lot of time on scheduling, resulting in rapid performance degradation.

In addition, the EDF scheduling algorithm adopts a non-preemptive scheduling strategy. In the time slice allocated by the kernel to the real-time task, the real-time task can complete the task before the execution time arrives. In this way, other tasks cannot preempt the core in the spare time slice, and the CPU may be idle during this period of idle time, which will cause delays in real-time tasks. On the other hand, after a real-time task exceeds the task execution time and the task is not completed, it will continue to preempt the core with the current highest priority in the next cycle, which will cause the delay of the subsequent real-time task execution time, thus forming a "domino" The domino effect will cause multiple processes to exceed the deadline of the task, resulting in the collapse of the task system.

In response to the above problems, Lin and Brandt proposed the SLAD (SLACK Donation) algorithm and the BACKSLASH (BACK SLACK Donation) algorithm based on the ISM idea. The idea of ISM is to allocate real-time tasks to several service levels of the same level, and each service allocates CPU according to a certain ratio. If the real-time task on a service continues to run beyond the limit, the CPU of the service will be occupied and the service will be postponed. other real-time tasks on the This strategy does not consider the impact between tasks, and has a certain effect on reducing the deadline miss rate DMR (deadline miss ratio).

Although the SLAD and BACKSLASH algorithms can allow an over-budget task to better dynamically allocate the remaining time and borrow time slices from the next cycle during processing, this can solve the real-time task (overrun) overrun problem of the system. However, because there is a pre-judgment for time-limited tasks, it is necessary to decide whether to use dynamic allocation of remaining time and borrow time slices from the next cycle during processing. This will occupy the resources of the processor, when the real-time task is not frequently exceeded; this kind of scheduling is not efficient.

It can be known from the above that when the above two types of algorithms are applied to the Linux real-time operating system alone, they cannot meet the real-time and reliability requirements of the real-time system. This is the weak point in the prior art.

Contents of the invention

The object of the present invention is, aim at the problem that above-mentioned prior art exists, propose a kind of dynamic priority scheduling algorithm based on linux real-time operating system, to solve above-mentioned technical problem.

In order to achieve the above object, technical scheme of the present invention is:

A kind of dynamic priority scheduling algorithm based on linux real-time operating system, comprises the following steps:

When a real-time task is added to the task queue, the current release time is updated and the status of the current task is obtained, and the real-time task enters the cache memory module;

When the real-time task exceeds the limit, call the SLAD or BACKSLASH algorithm and count in the cache memory module; otherwise call the EDF algorithm and count in the cache memory module;

The cache memory module calculates the frequency of real-time tasks exceeding the limit within a set period of time; according to the frequency of real-time tasks exceeding the limit, it decides to directly schedule the SLAD or BACKSLASH algorithm, or schedule the EDF algorithm, and update the task priority and next recovery time.

The set time period is several working cycles.

Further, the algorithm also includes the following steps:

Select a task with the highest priority among all state tasks as the preemptive task, and select the task with the highest priority among the tasks in the effective state as the task that may be switched;

Judging that if the task that may be switched is the same as the preempting task, the next job scheduling time is set as the release time of the possible switching task, otherwise the release time of the possible switching task is compared with the release time of the preempting task, and the smaller value is used as the next job scheduling time;

Perform job switching.

Furthermore, the cache memory module sets a task expectation e, which is used to pre-judge the remaining time slices and possible borrowed time slices. When the task expectation is higher, the scheduling SLAD algorithm or BACKSLASH algorithm level is higher. ; The K _C coefficient is set for the expected e, which is used to adjust the expected e.

Further, 0 ≤ K _C ≤ 1, according to the probability of assigning the remaining time and borrowing time slice tasks in the set time, the dynamic allocation is done; if the above tasks do not occur at all within the set time, the value of this coefficient K _C will be It will take 0 and directly call the EDF algorithm.

Further, the formula for calculating the priority of the SLAD algorithm is:

vdeadline＝[t/p]*p+d formula (1)

The formula for calculating the priority of the BACKSLASH algorithm is:

vdeadline＝d _s,k -[(d _s,k -t)/p]*p formula (2)

Among them, t is the current time, p is the task period, d is the deadline in the task period, and the task with the smallest vdeadline has the highest priority.

Further, the schedulable conditions of the EDF algorithm task set are:

Task set τ={T ₁ , T ₂ ,…Tn}, where T _i =(e _i , d _i , p _i , r _i ), e _i represents the execution time in the cycle, d _i represents the completion of realization, p _i Indicates the period size, r _i indicates the initial release time of the task, that is, the time when the task is put into operation;

Where e _i , d _i , p _i are positive real numbers, and _ri is a non-negative real number; the task period is the same as the cut-off implementation, that is, when d _i = r _i ,

The beneficial effect of the present invention is that the cache memory module decides to directly schedule the SLAD or BACKSLASH algorithm according to the frequency of the overrun of the real-time task occurring within a period of time, and vice versa calls the EDF scheduling algorithm. In this way, the advantages of the EDF algorithm are effectively used when dealing with normal task loads, which are easy to implement and occupy less processor resources. When directly scheduling SLAD or BACKSLASH algorithms, it can efficiently handle the overrun problem of real-time tasks. The cache memory module sets the task expectation e, which is used to make a pre-judgment on the remaining time slices and possible borrowed time slices. When the expectation of this kind of task (allocation of remaining time and borrowing time slice) is higher, the scheduling SLAD or BACKSLASH algorithm level it gives is higher. Under normal circumstances, such tasks may not occur frequently. Therefore, a K _C coefficient is set for the expectation e, which is used to adjust the expectation e, and it is dynamically allocated according to the probability of such a task occurring in a period of time. When this task does not occur at all for a period of time, the value of this coefficient K _C will take 0. Thus, it is transferred to directly calling the EDF algorithm. It solves the overload problem that cannot be solved by traditional algorithms, and ensures the correctness and real-time performance of system scheduling, greatly improving the scheduling efficiency of the system.

In addition, the design principle of the present invention is reliable, the structure is simple, and has very wide application prospects.

It can be seen that, compared with the prior art, the present invention has outstanding substantive features and remarkable progress, and the beneficial effects of its implementation are also obvious.

Description of drawings

FIG. 1 is an algorithm flow chart of a dynamic priority scheduling algorithm based on a linux real-time operating system provided by the present invention.

detailed description

The present invention will be described in detail below with reference to the accompanying drawings and specific embodiments. The following embodiments are explanations of the present invention, but the present invention is not limited to the following embodiments.

As shown in Figure 1, a kind of dynamic priority scheduling algorithm based on linux real-time operating system provided by the present embodiment comprises the following steps:

When a real-time task is added to the task queue, the current release time is updated and the status of the current task is obtained, and the real-time task enters the cache memory module;

When the real-time task exceeds the limit, call the SLAD or BACKSLASH algorithm and count in the cache memory module; otherwise call the EDF algorithm and count in the cache memory module;

The cache memory module calculates the frequency of real-time tasks exceeding the limit within a set period of time; according to the frequency of real-time tasks exceeding the limit, it decides to directly schedule the SLAD or BACKSLASH algorithm, or schedule the EDF algorithm, and update the task priority and next recovery time. The set time period is several working cycles.

The specific steps of the task scheduling algorithm are as follows:

Step 31: When the real-time task is added to the task queue, update the current time release time to obtain the status of the current task, and the real-time task enters the cache memory module link K _C *e;

Step 32: According to the number of task overload and normal scheduling recorded in the cache, determine whether the real-time task exceeds the limit and select a method for updating the task priority;

Step 33: After updating the task priority, classify the tasks according to the working status of the tasks in this cycle. For the tasks that have not completed the work in one cycle, the state is set to active, and for the tasks that have completed the work in one cycle, the state is set to inactive;

Step 34: Select a task with the highest priority among all active state tasks as a possible switching task, and save it in the next variable, select a task with the highest priority among all state tasks as the preemptive task, and save it in In the preemptor variable, judge that if the variable next is equal to the variable preemptor, the next job scheduling time will set the variable preempt_time to the release time resume-time of the variable next, otherwise set the variable preempt_time to the release time resume-time of next and the release time of the preemptor Release time resume-time comparison, the smaller value is used as the next job scheduling time; perform job switching.

Options for updating task priorities include:

If the real-time task exceeds the limit, the SLAD algorithm is called to update the task priority, and the memory link is counted up; if the real-time task is not overrun, the EDF algorithm is called to update the task priority, and the memory link is counted up.

The cache memory module sets a task expectation e, which is used to pre-judge the remaining time slices and the time slices that may be borrowed. When the task expectation is higher, the scheduling SLAD level is higher; set a task expectation e The K _C coefficient is used to make an adjustment to the expected e.

0≤K _C ≤1, according to the probability of assigning the remaining time and the task of borrowing time slices according to the set time; if the above tasks do not occur at all within the set time, the value of this coefficient K _C will be 0 , call the EDF algorithm directly.

The formula for calculating the priority of the SLAD algorithm is:

vdeadline=[t/p]*p+d

Among them, t is the current time, p is the task period, d is the deadline in the task period, and the task with the smallest vdeadline has the highest priority.

The schedulable conditions for the EDF algorithm task set are:

Task set τ={T ₁ , T ₂ ,…Tn}, where T _i =(e _i , d _i , p _i , r _i ), e _i represents the execution time in the cycle, d _i represents the completion of realization, p _i Indicates the period size, r _i indicates the initial release time of the task, that is, the time when the task is put into operation;

Where e _i , d _i , p _i are positive real numbers, and _ri is a non-negative real number; the task period is the same as the cut-off implementation, that is, when d _i = r _i ,

The above disclosure is only a preferred embodiment of the present invention, but the present invention is not limited thereto, any non-creative changes that those skilled in the art can think of, and some improvements and modifications made without departing from the principle of the present invention , should fall within the protection scope of the present invention.

Claims (6)

1. a kind of dynamic priority scheduling algorithm based on linux real time operating systems, it is characterised in that comprise the following steps：

When real-time task adds task queue, update current release time and obtain the state of current task, real-time task is entered Enter to cache memory module；

When real-time task transfinites, SLAD or BACKSLASH algorithms are called, and counted in memory module is cached；Otherwise call EDF algorithms, and counted in memory module is cached；

Caching memory module calculates the frequency that real-time task transfinites in setting time section；The frequency to be transfinited according to real-time task determines SLAD or BACKSLASH algorithms, or scheduling EDF algorithms are directly dispatched, updates task priority and next recovery time.

2. a kind of dynamic priority scheduling algorithm based on linux real time operating systems according to claim 1, its feature It is, the algorithm is further comprising the steps of：

The task of a highest priority is chosen in all state tasks as task is seized, is selected in the task of effective status The task of highest priority is taken as may switching for task；

If judging, may the switching of the task is identical with task is seized, next time the job scheduling time be arranged to that task may be switched Release time, the release time that otherwise will likely switch task and the release time for seizing task compare, under smaller value is used as One-stop operation scheduling time；Carry out operation switching.

3. a kind of dynamic priority scheduling algorithm based on linux real time operating systems according to claim 2, its feature It is, caching memory module sets a task it is expected e, for the feelings to remaining timeslice and the timeslice that may be borrowed Condition does advance judgement, and when the expectation of task is higher, scheduling SLAD algorithms or BACKSLASH algorithm ranks are higher；To it is expected e There is provided K_CCoefficient, for it is expected that e makes regulation.

4. a kind of dynamic priority scheduling algorithm based on linux real time operating systems according to claim 3, its feature It is, 0≤K_C≤ 1, the probability that distribution remaining time occurs according to setting time and borrows the task of timeslice dynamically distributes； If above-mentioned this task, this COEFFICIENT K does not occur in setting time completely_CValue will take 0, directly invoke EDF algorithms.

5. a kind of dynamic priority scheduling algorithm based on linux real time operating systems according to claim 1, its feature It is,

SLAD algorithm priority calculation formula are：

Vdeadline=[t/p] * p+d formulas (1)

BACKSLASH algorithm priority calculation formula are：

Vdeadline=d_s,k-[(d_s,k- t)/p] * p formulas (2)

Wherein, t is current time, and p is the duty cycle, and d is deadline in the duty cycle, and vdeadline is minimum to be appointed Business highest priority.

6. a kind of dynamic priority scheduling algorithm based on linux real time operating systems according to claim 1, its feature It is,

The condition of EDF algorithm task-set schedulable is：

Task-set τ={ T₁,T₂... Tn }, wherein T_i=(e_i,d_i,p_i,r_i), e_iRepresent the execution time in the cycle, d_iRepresent Into realization, p_iRepresent cycle size, r_iThe initial release moment of the task is represented, i.e., at the time of task puts into operation；

Wherein e_i,d_i,p_iFor arithmetic number, r_iFor nonnegative real number；Duty cycle realizes identical, i.e. d with cut-off_i=r_iWhen,