Browse Prior Art Database

Low Overhead Scheduler for High Performance SW Systems

IP.com Disclosure Number: IPCOM000131674D
Published in the IP.com Journal: Volume 5 Issue 11B (2005-12-10)
Included in the Prior Art Database: 2005-Dec-10
Document File: 3 page(s) / 40K

Publishing Venue

Siemens

Related People

Juergen Carstens: CONTACT

Abstract

A problem with real time systems in general and communication systems in particular is to coordinate the execution of several tasks. These tasks can be categorized into three types: Time driven tasks are invoked regularly, at pre-determined time intervals. Event driven tasks are invoked based upon the occurrence of certain events. And lastly, background processing tasks e.g. book keeping should be mentioned. To manage the case of several tasks being ready for execution at the same time, associated priority levels are assigned to each task. This priority scheme may either be static or change dynamically to adapt correctly to new situations, e.g. when a low priority task which has not been activated for a long period of time becomes urgent. Up to now, the dominating technique is the use of schedulers that are part of the operating system. They follow certain scheduling schemes to determine which task will run at what point in time. The problem with those scheduling systems is the fact that they entail a considerable amount of overhead which consists of task switching time in addition to the time needed to resolve the priorities of the various tasks. Another problem is the fact that the scheduling is not deterministic, which leads to the issue of analyzing the multitasking behavior to avoid deadlocks. This can be challenging. Furthermore, the technique submits execution according to a certain policy that may only be optimized by programming certain parameters. A system designer has to rely on the optimization done by the OS vendors and the programming of the scheduling policy parameters. Also, the debugging of such a non-deterministic system is usually a difficult issue. Therefore, it is an inadequate solution for system designers.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 28% of the total text.

Page 1 of 3

S

Low Overhead Scheduler for High Performance SW Systems

Idea: Shlomi Tsur, IL-Seabridge; Ilya Vershkov, IL-Seabridge

A problem with real time systems in general and communication systems in particular is to coordinate the execution of several tasks. These tasks can be categorized into three types: Time driven tasks are invoked regularly, at pre-determined time intervals. Event driven tasks are invoked based upon the occurrence of certain events. And lastly, background processing tasks e.g. book keeping should be mentioned. To manage the case of several tasks being ready for execution at the same time, associated priority levels are assigned to each task. This priority scheme may either be static or change dynamically to adapt correctly to new situations, e.g. when a low priority task which has not been activated for a long period of time becomes urgent.

Up to now, the dominating technique is the use of schedulers that are part of the operating system. They follow certain scheduling schemes to determine which task will run at what point in time. The problem with those scheduling systems is the fact that they entail a considerable amount of overhead which consists of task switching time in addition to the time needed to resolve the priorities of the various tasks. Another problem is the fact that the scheduling is not deterministic, which leads to the issue of analyzing the multitasking behavior to avoid deadlocks. This can be challenging. Furthermore, the technique submits execution according to a certain policy that may only be optimized by programming certain parameters. A system designer has to rely on the optimization done by the OS vendors and the programming of the scheduling policy parameters. Also, the debugging of such a non-deterministic system is usually a difficult issue. Therefore, it is an inadequate solution for system designers.

The proposed Scheduler was invented for real time communication systems, where response time is not critical (around 100 ms) and the number of tasks with different priorities is typically below 20. It handles both time driven and event driven tasks and provides flexibility of the priority scheme. The functioning will be explained in the following. To make the understanding easier, the functions controlled by the Scheduler will be referred to as "tasks", although they are not handled by the operating system and, in fact they are functions, called by and returning to the Scheduler. Another simplification for this description is the idea of each function being assigned a different priority (whereas in reality several tasks share same priorities). The priorities of the tasks are numbered from 0 (lowest priority) to n. n is equal to the number of priorities excluding task 0. To simplify the implementation we use a decoded form of the priorities above zero. I.e. a priority "i" is represented by a binary number that contains a 1 at its bit set "i". Examples are 8 (binary 1000) which represents the...