KR20130022976A - System and method for deadline based priority inheritance - Google Patents

Abstract

The present invention relates to a deadline based priority inheritance system and method thereof.
The present invention is directed to preventing " priority reversal " in a deadline-based Earliest Deadline First (EDF) scheduling system; Priority inheritance deadline-based scheduler continuously raises the priority of critical zones or server wait tasks at every clock tick; The highest priority of newly created standby task is continuously inherited by critical zone execution task or server task.

Description

Deadline-based priority inheritance system and its method {SYSTEM AND METHOD FOR DEADLINE BASED PRIORITY INHERITANCE}

The present invention relates to an embedded real-time operating system, and more particularly, to a deadline-based priority inheritance system and a method thereof in a real-time system.

1 is a structure of a distributed real-time object model time-triggered message-triggered object (TMO).

As shown in FIG. 1, the distributed real-time object model TMO (Time-triggered Message-triggered Object) is a model for oriented on time computing computing paradigm, and adheres to the time constraints given at design time when performing a thread in an object. This model guarantees processing within the deadline. Unlike the general object model, the TMO consists of a data store within the object and a member thread that controls this data, the SpM (Time-triggered Spontaneous Method) and SvM (Message-triggered Service Method). If the SpM is scheduled to be driven periodically by a given time condition (Autonomous Activation Condition) at the time of design to allow processing within the deadline, the SvM is driven on a deadline basis by a service request message from a remote or local node. do.

As an execution engine to support TMO, RT-eCos3.0 [2,3] developed by embedding deadline-based real-time scheduler function and distributed IPC function to support TMO in eCos3.0, an open source real-time embedded OS. have. RT-eCos3.0 provides deadline-based scheduling, but in the priority inheritance processing of mutex-locks, it dynamically adjusts the priority of lock wait threads that change dynamically as they approach the deadline rather than the conventional simple priority method. You need a system to inherit from. In other words, when a SpM or SvM accesses a data store within the same TMO object, it uses a mutex-lock. The traditional priority inheritance system uses one of the SpMs or SvMs that the mutex-lock entry thread queues to the mutex-lock. This method inherits the highest priority.

However, in the case of the RT-eCos3.0 TMO engine with deadline-based scheduling, the deadlines of the waiting SpMs or SvMs are getting closer, so that the priority of the threads must be changed, and they are executed with inherited priorities. Priority inheritance for threads must also continue. Of course, the deadline-based priority of the thread itself running with the lock must also be taken into account.

Hereinafter, a description will be given of a conventional operating system RT-eCos3.0 that provides a deadline-based scheduling to support TMO.

RT-eCos3.0 is a real-time embedded kernel with the eCos3.0 kernel, a small open source operating system for embedded systems, a TMO engine with deadline-based scheduler, SpM / SvM processing, and distributed IPC.

RT-eCos3.0 provides the following features for TMO-based distributed real-time object support:

-Provides deadline-based real-time scheduling of SpM and SvM with a precision of at least 30μs to 10ms depending on CPU performance;

-Provides on-time activation of SpM.

Provides a logical multicast IPC subsystem;

Provides real-time method SvM operation via remote and local messages;

Provide clock synchronization between distributed nodes;

-Provides TMO-based object-oriented programming method using TMOL (TMO Support Library).

Meanwhile, the conventional priority inheritance technique is used in the following two cases.

2 and 3 are block diagrams illustrating a conventional priority inheritance method. FIG. 2 is a view for explaining a conventional priority inheritance technique of the critical zone entry process by mutual exclusion. FIG. 3 is a diagram for explaining a conventional priority inheritance technique when starting server wait in a client-server model.

First, the conventional priority inheritance scheme of FIG. 2 assumes the following conditions: the priority of task B 200 is higher than the priority of task A 100; When task A 100 enters the critical body of water earlier than task B 200; The priority of task B 200 is inherited by task A 100.

The prioritized inheritance scheme of FIG. 2 is described in more detail as follows. That is, when task B 200 having high priority attempts to enter the critical area by mutual exclusion, if there is already entry task A 100 having a low priority in the critical area, the critical area is waited for entry. Inherit the high priority of task B 200 to a task that has already entered the critical zone so that it will not be deprived of schedules to other intermediate priority task C 300 by the Earliest Deadline First scheduler 400. "Priority reversal". At this time, it is referred to as "priority reversal" to deprive the schedule of another intermediate priority task as described above.

Second, the conventional priority inheritance scheme of FIG. 3 assumes the following conditions: the priority of client task B 700 is higher than the priority of server task A 600; When high priority client task B 700 is processing a request by sending a message to low priority server task A 600; Server task A 600 is in a message service, while client task B 700 is waiting for service termination of the server after sending a message; The priority of the client task B 700 is inherited by the server task A 600.

The prioritized inheritance scheme of FIG. 3 is described in more detail as follows. That is, when high priority client task B 700 is processing a request by sending a message to low priority server task A 600, task C 800 of another intermediate priority is made by EDF scheduler 400. In order not to deprive the server of the schedule (this is referred to as " priority reversal "), the server task A 600 inherits the high priority of the client task B 700.

However, the prioritized priority inheritance techniques of FIGS. 2 and 3 imply technical limitations that are not suitable for a deadline-based Earlyliest Deadline First (EDF) scheduling system in which the priority of waiting tasks is increased at a time based on the end deadline of task execution. Doing. That is, if the priority of the standby task continues to increase as the deadline arrives, the critical zone entry task (that is, task A 100 in FIG. 2) or the server task (that is, the server task ( Since the priority inherited to 600) is not the highest priority of the current waiting task, there is a technical problem that a "priority reversal" may occur, in which another schedule of higher middle priority is again deprived of a schedule.

Accordingly, an object of the present invention is to provide a deadline-based priority inheritance method so that priority reversal does not occur in the scheduling system with priority inheritance as described above.

In order to achieve the above object, the deadline-based priority inheritance method according to the present invention,

(A) a priority inheritance scheduler running every clock tick, driving tasks that have come to a cycle; (B) as the deadline arrives, the priority inheritance scheduler recalculating the priority of tasks based on the remaining deadline of each task; (C) inheriting the priority of the recalculated tasks to tasks running in a critical zone; .

Preferably, step (C) is

Selecting, by the priority inheritance scheduler, the highest priority of each queued task for each critical zone waiting queue;

And inheriting, by the priority inheritance scheduler, the selected highest priority to a task executing a critical section.

Preferably, step (B) is

The priority inheritance scheduler, as the deadline arrives,

Running; Critical zone waiting; Waiting for server to complete; The priority of all real-time tasks is recalculated based on the remaining deadlines.

Preferably, the priority inheritance EDF scheduler further comprises: selecting the highest priority of tasks waiting to complete the service for each server and inheriting the selected highest priority to the server task; do.

In addition, in order to achieve the above object, the deadline-based priority inheritance method according to the present invention,

 Priority Inheritance is a priority inheritance method in which the priority inheritance scheduler schedules every clock tick as the deadline arrives.

Recalculating priorities for tasks waiting on a critical zone waiting queue, or server waiting tasks;

Dynamically inheriting a highest priority among the priorities of the recalculated tasks to a task running in the critical zone or the server task.

In addition, in order to achieve the above object, the deadline-based priority inheritance method according to the present invention,

In the client-server model, a deadline-based priority inheritance method that inherits the highest priority of all tasks that send and wait for a service request message to the server.

Calculating a priority that is changed every clock tick by the priority inheritance scheduler as the deadline arrives;

Selecting the highest priority from the calculated priorities;

And inheriting the selected highest priority to a server task in a message service.

In addition, in order to achieve the above object, the deadline-based priority inheritance system according to the present invention,

Run tasks periodically;

Recalculate the priority of tasks every clock tick as the deadline arrives;

The priority of the recalculated tasks is increased to the priority of the tasks waiting to enter the critical zone or the priority of the tasks waiting to be terminated from the service of the server. And a priority inheritance deadline-based scheduler that performs an operation of inheriting the calculated task priority.

Preferably, the priority inheritance deadline based scheduler

A task driver for periodically driving tasks;

A task priority calculator that recalculates the priority of tasks every clock tick as the deadline arrives;

Selecting the highest priority from among the priorities of the recalculated tasks;

And a task priority inheritor that inherits the selected highest priority to a task executing in a critical region or a server task serving a message.

According to the present invention, when the priority of a critical zone or a server waiting task is continuously increased at every clock tick, the deadline-based task is continuously inherited by continuously inheriting the highest priority of the newly formed standby task to a critical zone execution task or a server task. The EDF scheduling system has an effect of preventing the "priority reversal" phenomenon.

1 is a structure of a distributed real-time object model time-triggered message-triggered object (TMO).
2 is a conventional priority inheritance technique, which is a view for explaining a conventional priority inheritance technique of the critical zone entry process by mutual exclusion.
FIG. 3 is a conventional priority inheritance scheme and illustrates a conventional priority inheritance technique at the start of server standby in the client-server model.
FIG. 4 is a diagram illustrating a deadline-based priority inheritance technique according to the intervention of the priority inheritance deadline first (EDF) scheduler in a critical zone entry process by mutual exclusion according to an embodiment of the present invention. .
FIG. 5 is a diagram illustrating a deadline-based priority inheritance technique according to an intervention of a priority inheritance EDF scheduler in the client-server model according to the present invention.
6 is a flowchart illustrating an operation of a priority inheritance EDF scheduler for deadline based priority inheritance according to an embodiment of the present invention.

The present invention is applied to a scheduling system. In particular, the present invention is applied to a scheduling system of a deadline-based priority inheritance method. However, the technical idea of the present invention may be applied to other technologies without being limited thereto.

As the inventive concept allows for various changes and numerous embodiments, particular embodiments will be illustrated in the drawings and described in detail in the written description. It should be understood, however, that the invention is not intended to be limited to the particular embodiments, but includes all modifications, equivalents, and alternatives falling within the spirit and scope of the invention.

Terms including ordinal numbers such as first and second may be used to describe various components, but the components are not limited by the terms. The terms are used only for the purpose of distinguishing one component from another. For example, without departing from the scope of the present invention, the first component may be referred to as a second component, and similarly, the second component may also be referred to as a first component. The term " and / or " includes any combination of a plurality of related listed items or any of a plurality of related listed yields.

When an element is referred to as being "connected" or "connected" to another element, it may be directly connected or connected to the other element, but other elements may be present in between. On the other hand, when an element is referred to as being "directly connected" or "directly connected" to another element, it should be understood that there are no other elements in between.

The terminology used in this application is used only to describe a specific embodiment and is not intended to limit the invention. Singular expressions include plural expressions unless the context clearly indicates otherwise. In this application, the terms "comprise" or "have" are intended to indicate that there is a feature, number, step, action, component, part, or combination thereof described on the specification, and one or more other features. It is to be understood that the present disclosure does not exclude the possibility of the presence or the addition of numbers, steps, operations, components, components, or a combination thereof.

Unless defined otherwise, all terms used herein, including technical or scientific terms, have the same meaning as commonly understood by one of ordinary skill in the art. Terms such as those defined in the commonly used dictionaries should be construed as having meanings consistent with the meanings in the context of the related art and shall not be construed in ideal or excessively formal meanings unless expressly defined in this application. Do not.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS Reference will now be made in detail to the preferred embodiments of the present invention, examples of which are illustrated in the accompanying drawings, wherein like reference numerals refer to the like elements throughout. The description will be omitted.

The basic idea of the present invention is to prevent "priority reversal" in a deadline-based Earliest Deadline First (EDF) scheduling system; Priority inheritance deadline-based scheduler continuously raises the priority of critical zones or server wait tasks at every clock tick; The highest priority of newly created standby task is continuously inherited by critical zone execution task or server task.

4 is a block diagram illustrating an operation of a deadline-based priority inheritance system according to an embodiment of the present invention. 4 is an embodiment of the technical limitations of the conventional priority inheritance scheme of FIG.

In FIG. 4, the priority of task B 200 is higher than the priority of task A 100; When task A 100 enters the critical body of water earlier than task B 200; When inheriting the priority of task B 200 to task A 100, task C 300 irrelevant to the critical zone is deprived of priority (ie, "priority reversal"), so that task B 200 's This is to prevent the phenomenon that priority is not inherited by task A (100). On the other hand, such "priority reversal" may occur as the priority of tasks changes as the deadline arrives.

The deadline-based priority inheritance system in mutual exclusion according to the embodiment of FIG. 4 includes a low priority task A (100) entering a critical zone and executing therein, and a high priority critical zone entry waiting task. B 200, a task C 300 of intermediate priority irrelevant to a critical zone, and a priority inheritance deadline based scheduler 500. Meanwhile, the priority inheritance deadline based scheduler 500 includes a periodic task driver 510, a task priority recalculator 520, and a critical zone execution task priority inheritor 530.

The priority inheritance deadline-based scheduler 500 performs the scheduling by the periodic task driver 510 every clock tick, and in particular, the task waiting in the critical zone to inherit the priority as the deadline arrives. Priority recalculator 520 recalculates the priority of the task. Then, the priority of the recalculated task is inherited by the task executing in the critical zone by the critical zone execution task priority inheritor 530.

As described above, the priority inheritance deadline-based scheduler 500 according to the present invention executes a task with a period that arrives every clock tick. Then, the priority inheritance deadline-based scheduler 500 recalculates the priority of all running tasks and the tasks due to the remaining end deadlines of the critical zone entry waiting and server shutdown waiting tasks as the deadline arrives. (Ie, task priority recalculator 520 performs). Priority Inheritance The deadline-based scheduler 500 newly inherits the highest priority of tasks waiting in each waiting queue for the waiting queues of all the critical zones to the tasks running in each critical zone. That is, priority inheritance deadline-based scheduler 500 inherits the priority of task B 200 waiting in the critical zone for the priority of the recalculated task, and also executes task A 100 running in the critical zone. ), So that the recalculated task priority is inherited (ie, performed by the critical zone execution task priority inheritor 520).

Accordingly, as in the configuration of the embodiment of FIG. 4, the changing high priority of the critical zone wait task B 200 is not only at the critical zone wait start but also continuously by the priority inheritance deadline based scheduler 500. Inherited to task A (100) performing entry. That is, by the priority inheritance deadline-based scheduler 500 performed every clock tick, the priority of the critical zone waiting task B 200 is increased as the deadline is imminent, and the priority inheritance deadline-based scheduler 500 is performed. ) Will inherit the highest new priority among these critical zone wait tasks.

5 is a block diagram illustrating an operation of a deadline-based priority inheritance system according to an embodiment of the present invention. FIG. 5 is an embodiment in which the technical limitations of the conventional priority inheritance scheme of FIG. 2 are solved. FIG.

In FIG. 5, the priority of client task B 700 is higher than the priority of server task A 600; When high priority client task B 700 is processing a request by sending a message to low priority server task A 600; Server task A 600 is in a message service, while client task B 700 is waiting for service termination of the server after sending a message; When inheriting the priority of client task B 700 to server task A 600, server-independent task C 300 takes priority (i.e. " reversing priority ") than server task A 600. It is to prevent scheduling first.

That is, the deadline-based priority inheritance system in the client-server model according to the embodiment of FIG. 5 includes a low priority server task A 600 that is receiving a message from a client and is waiting to terminate a high priority service. Client task B 700, a general task C 800 of medium priority independent of client or server tasks, and priority inheritance deadline based scheduler 500. The priority inheritance deadline based scheduler 500 includes a periodic task driver 510, a task priority recalculator 520, and a server task priority inheritor 540.

The priority inheritance deadline-based scheduler 500 according to the present invention executes a task with a period that arrives every clock tick. Then, the priority inheritance deadline-based scheduler 500 recalculates the priority of all running tasks and the tasks due to the remaining end deadlines of the critical zone entry waiting and server shutdown waiting tasks as the deadline arrives. do. Priority Inheritance The deadline-based scheduler 500 newly inherits the highest priority of tasks waiting in each waiting queue for the waiting queues of all the critical zones to the tasks running in each critical zone. That is, the priority inheritance deadline-based scheduler 500 raises the priority of the recalculated task to the priority of the client task B 700 that is waiting to terminate the service of the server, and also the server task A 100 that is in the message service. ) Also inherits the recalculated task priority. That is, the priority inheritance deadline-based scheduler 500 continuously changes (or recalculates) the priority as the deadline arrives, and inherits the changed priority to the server task A 600.

At this time, the task priority recalculator 520 recalculates the priority as the deadline arrives. The server task priority inheritor 540 transfers the priority calculated by the task priority recalculator 520 to the client task B 700 waiting for service termination of the server after the message is transmitted. The priority is increased and the server task A 600 in message service is also operated (or controlled) so that the priority of the client task B whose priority is increased is inherited.

Accordingly, as shown in the configuration of the embodiment of FIG. 5, the high priority of the client task B 700 which is waiting for service termination is not only at the time of transmission of the service request message, but also continuously by the priority inheritance deadline-based scheduler 500. Inherited by A 600. That is, the priority of the waiting client tasks is increased by the deadline imminent by the deadline-based scheduler 500 performed every clock tick, and the priority inheritance deadline-based scheduler 500 is a server having such server waiting tasks. The task's priority will continue to be inherited by the new highest priority of server wait tasks.

6 is a flowchart illustrating an operation of a deadline-based priority inheritance method according to an embodiment of the present invention.

As shown in Figures 4 and 5, embodiments of the present invention apply to deadline based priority inheritance in two cases. As shown in the embodiments of FIGS. 4 and 5, the priority inheritance early deadline first (EDF) scheduler according to the present invention, as compared to the conventional EDF scheduler of FIGS. It contains the operations that perform server priority inheritance and the components that perform them.

The priority inheritance EDF scheduler according to the present invention operates every clock tick to perform an operation of inheriting a priority that is recalculated according to the deadline. That is, referring to FIG. 6, the priority inheritance EDF scheduler drives a task in which a period arrives (S610).

The priority inheritance EDF scheduler is: i) running; ii) being in a critical zone atmosphere; iii) waiting for server completion; Priorities of all real-time tasks are recalculated based on the remaining deadlines (S620).

Priority Inheritance The EDF scheduler selects the highest priority of the tasks waiting in the queue for each critical zone waiting queue, and newly inherits the selected highest priority to the critical zone running task (S630). .

Subsequently, the priority inheritance EDF scheduler selects the highest priority of tasks waiting to complete the corresponding service for each server and newly inherits it to the server task (S640).

While the present invention has been particularly shown and described with reference to exemplary embodiments thereof, it is to be understood that the invention is not limited to the disclosed embodiments, but, on the contrary, is intended to cover various modifications and equivalent arrangements included within the spirit and scope of the appended claims. will be. Accordingly, the true scope of the present invention should be determined by the technical idea of the appended claims.

Claims (8)

(A) a priority inheritance scheduler running every clock tick, driving tasks that have come to a cycle;
(B) as the deadline arrives, the priority inheritance scheduler recalculating the priority of tasks based on the remaining deadline of each task;
(C) inheriting the priority of the recalculated tasks to tasks running in a critical zone; Deadline-based priority inheritance method characterized in that it comprises a. The method of claim 1, wherein step (C)
Selecting, by the priority inheritance scheduler, the highest priority of each queued task for each critical zone waiting queue;
And inheriting, by the priority inheritance scheduler, the selected highest priority to a task executing a critical zone. The method of claim 1, wherein step (B)
The priority inheritance scheduler, as the deadline arrives,
Running; Critical zone waiting; Waiting for server to complete; Deadline-based priority inheritance method characterized in that the priority of all the real-time tasks are recalculated based on the remaining deadline. The method of claim 1, wherein
The priority inheritance EDF scheduler, selecting the highest priority of each task waiting to complete the service for each server, and inheriting the selected highest priority to the server task; characterized in that the deadline-based Priority Inheritance Method. Priority Inheritance is a priority inheritance method in which the priority inheritance scheduler schedules every clock tick as the deadline arrives.
Recalculating priorities for tasks waiting on a critical zone waiting queue, or server waiting tasks;
And dynamically inheriting a highest priority among the priorities of the recalculated tasks to a task running in the critical zone or the server task. In the client-server model, a deadline-based priority inheritance method that inherits the highest priority of all tasks that send and wait for a service request message to the server.
Calculating a priority that is changed every clock tick by the priority inheritance scheduler as the deadline arrives;
Selecting the highest priority from the calculated priorities;
And inheriting the selected highest priority to a server task in a message service. Run tasks periodically;
Recalculate the priority of tasks every clock tick as the deadline arrives;
The priority of the recalculated tasks is increased to the priority of the tasks waiting to enter the critical zone or the priority of the tasks waiting to be terminated from the service of the server. And a priority inheritance deadline-based scheduler that performs an operation of inheriting the calculated task priority. 8. The system of claim 7, wherein the priority inheritance deadline based scheduler
A task driver for periodically driving tasks;
A task priority calculator that recalculates the priority of tasks every clock tick as the deadline arrives;
Selecting the highest priority from among the priorities of the recalculated tasks;
And a task priority inheritor for inheriting the selected highest priority to a task executing in a critical section or a server task serving a message.

Images