User level scheduling of inter-communicating real-time tasks

Details User level scheduling of inter-communicating real-time tasks User level scheduling of inter-communicating real-time tasks

1999-01-28

2002-12-03

Banankhah, Majid (Department: 2156)

Electrical computers and digital processing systems: multicomput

Computer-to-computer data routing

Least weight routing

C709S241000, C709S241000

Reexamination Certificate

active

06490611

ABSTRACT:

FIELD OF THE INVENTION
This invention relates generally to multi-tasking computer systems, and more particularly, to user level scheduling of real-time tasks that inter-communicate over a network.
BACKGROUND OF THE INVENTION
It has become evident that real-time applications, such as process control, factory automation, and plant control are moving to use open, standard, commercially available, and more general purpose computers, operating systems (OS), and networks. In other words, users would prefer to implement their applications with low-cost and readily available off-the-shelf hardware and software components.
For example, users would like to replace expensive workstations with off-the-shelf PCs. Users would like to adopt standard PC operating systems for real-time control. There is also a lot of momentum toward using the Internet Protocol (IP) for control networks. As control and device-level networks, general purpose IP-based networks offer cost and support advantages over industrial field buses.
In addition, more and more desktop applications are starting to employ real-time elements, such as the presentation of continuous media, e.g., video streams, and the remote control of instruments and devices in distant learning environments. This potential for using general purpose components for a wide spectrum of real-time tasks has prompted many contemporary general purpose operating systems to offer some minimal degree of real-time scheduling and programming support.
However, there are still problems in trying to build distributed systems with real-time functionality using off-the-shelf hardware and software components. This is primarily due to the fact that off-the-shelf components are not necessarily designed with real-time functionality in mind. In particular, to realize end-to-end predictability, say, when a process on one computer sends data to a process on another computer over a network, there are several specific problems.
Real-time application requirements must be mapped into requirements imposed on the schedulable entities of the system, e.g., tasks. Predictable execution of the tasks must be ensured in the face of possible priority inversions, limited OS level real-time scheduling support, and limited number of priorities. Real-time and non real-time tasks must be integrated in the hardware environment.
In the prior art, scheduling support for integrating real-time and non real-time tasks has been done by either extending existing operating systems, or by virtualizing the underlying hardware to multiplex a real-time kernel with the operating system. These approaches have certain drawbacks. The first approach needs to modify the existing operating system. However, access to the source programs of the operating system might not always be available. With the second approach, it is difficult to support real-time and non real-time activities that are closely related, e.g., in the case where there are multiple execution threads associated with the process, and there is a need by the tasks to share a common address space.
The current generation of operating systems has produced versions that provide some support for real-time scheduling, such as non-degradable priorities, and real-time threads. Support for these scheduling functions is not present in the older generation of these operating systems. For example, Windows NT 4.0 provides a REALTIME class such that threads in this class have non-degradable priorities.
Executing threads in this class have precedence over timesharing threads. These newer OS versions also provide timers with one millisecond granularity, and periodic callback routines which can be used for real-time periodic tasks. Real-time applications require that tasks are scheduled, executed, and completed with predictable and bounded variability in time. In reality, predictability comes in different granularities.
At one end of the spectrum, the direct physical control of robots, devices and instruments by local loop controllers, embedded controllers and PLCs may require sub-millisecond to one millisecond delay bounds. Unfortunately, the effects of nondeterminism present in many operating systems make it impractical to design user level scheduling to support real-time tasks with sub-millisecond precision. These types of tasks are better served by real-time kernels.
At the other end of the spectrum, a maximum delay or deadline value of one second is good enough for a video-on-demand file server, or database transactions for financial tasks. These tasks can be directly built with existing operating system primitives.
In the middle of the spectrum, there is a large population of real-time tasks that can tolerate end-to-end roundtrip delay/response time in the tens to hundreds of milliseconds range. These tasks often involve the interaction between users and remote data collection, video monitoring, file accessing, and command issuing in order to view videos, monitor, and control devices at a distance.
In any case, there is a need for a system where users can specify real-time scheduling of activities even when the system is configured with standard off-the-shelf components that do not necessarily include real-time capabilities.
SUMMARY OF THE INVENTION
The invention provides a multi-tasking distributed computer system with user level scheduling of the transmission of real-time and non real-time messages. The real-time messages having predetermined timing deadlines. At least one writer task generates the real-time and non real-time messages. The messages can have multiple priority levels organized in a plurality of priority bands, for example four. The generated messages are stored in ring buffers of a reflective memory and are indexed by pointers stored in queue entries. Pointers in a fourth queue index the real-time messages having low priority levels. Pointers in a third queue index the non real-time messages. A first and second queue store pointers for indexing the high and highest priority real-time messages, respectively.
A dispatcher moves pointers from the fourth to the second queue in response to time-out signals. The time-out signals ensure that the timing deadlines are met. A data push agent transmits the messages indexed by the pointers in the queues according to the associated priority levels. A reader task receives the messages transmitted by the data pusher agent.
In one aspect of the invention, the writer and reader tasks execute on different nodes of the system, and the nodes are connected by a network.


REFERENCES:
patent: 4658351 (1987-04-01), Teng
patent: 5519867 (1996-05-01), Moeller et al.
Thomas Riechmann, Jürgen Kleinöder; “User-Level Scheduling with Kernel Threads;” Technical Report, TR-14-96-05; Friedrich Alexander University, Erlangen-Nürnberg, Germany; Jun. 1996.

Affiliated with

Also associated with

Rating

User level scheduling of inter-communicating real-time tasks does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with User level scheduling of inter-communicating real-time tasks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and User level scheduling of inter-communicating real-time tasks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2980767