Abstract

As it is known, the main task of the RTS is to react in time to events at the site. Therefore, the establishment of some tasks sequence or mutual exclusion is an urgent problem for the RTS. The RTS of a rigid RT must ensure that each critical task is completed for all possible scenarios for its operation. Such guarantees can be provided on the basis of: exhaustive testing of all possible scenarios of the managed object behavior and control application programs (AP); a static schedule constructing; choosing a mathematically based dynamic planning algorithm. It is difficult to plan the work of dependent tasks, and its optimal solution requires large computational resources. This problem is solved by dividing the planning of tasks into two parts so that one part is performed in advance, before the RTS launch, and the second one, a more simple part, during the RTS operation. At planning, such time parameters of tasks are taken into account: a). Time points: release time - when there was a need to transfer control to the task (the time of the event); absolute deadline - the task must complete the next work; start time - when the task was started on the microprocessor (MP); Completion time - when the task has finished working by processing the event; b). Time parameters: relative deadline; execution time - the time when the task is executed while performing the next work; response time. A system of independent periodic problems is considered, where there may be aperiodic and sporadic problems as some special cases. It is shown that the static schedule for periodic tasks is a table which indicates what task has to be run for execution and at which point of time. Such a schedule is compiled on the interval of the hyperperiod. The scheduler periodically repeats the task execution sequence specified in the schedule. Schedulers usually work on interrupts from the timer, and tasks are AP called at the appropriate time by the interrupt handler. Such algorithms are used in high-reliability RTS. Two types of schedulers with dynamic priorities are considered: EDF (earliest dead-line first); LLF (least laxity first). Theorems / algorithms for their optimality are given. The notion of time reserve is explained. An example of a correct timetable is given. It is shown that in the analysis of planning algorithms, it is necessary to take into account the overhead costs for planning, by including them during the tasks execution. Dynamic planning with static priorities is considered: RMS (rate monotonic scheduling); DMS (deadline monotonic scheduling). An example of a schedule composed RMS and DMS planners is given. For the considered rules for priorities assigning, the statements / theorems of their optimality are given. Also, for systems with arbitrary relations between task periods, a sufficient, but not necessary, test / criterion for the feasibility testing of the RMS algorithm is given. Conclusions.The features of task scheduling in real-time systems, the conditions of the guaranteed completion of task times and task parameters; algorithms for static and dynamic scheduling; criteria/ the theorem of existence of planning objectives; examples are considered.

Authors and Affiliations