User level scheduling of inter-communicating real-time tasks

• US 6,490,611 B1
• Filed: 01/28/1999
• Issued: 12/03/2002
• Est. Priority Date: 01/28/1999
• Status: Expired due to Fees

• Current Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Inventors: González Gomez, Oscar J., Shen, Chia
• Primary Examiner(s): BANANKHAH, MAJID A
• Application Number:
  US09/239,583
• Time in Patent Office: 1,405 Days
• Field of Search: 709/100, 709/101, 709/102, 709/103, 709/104, 709/5, 709/322, 709/332, 710/200, 714/2
• US Class Current: 718/103
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic
• CPC Class Codes: G06F 9/544 Buffers; Shared memory; Pipes

Abstract

In a multi-tasking system a writer task generates real-time and non real-time messages having multiple priority levels in an ascending order arranged in a plurality of priority bands. The real-time messages have predetermined timing deadlines. A plurality of queues indexing the messages by pointers, there is one queue for each priority band. A dispatcher moves pointers from a lower priority queue to a higher priority queue in response to a time-out signal dependent on the timing deadline. A data push agent transmits the messages indexed by the pointers according to the multiple priority levels.

Claims

1. A multi-tasking system, comprising:

a writer task generating real-time and non real-time messages having multiple priority levels in an ascending order arranged in a plurality of priority bands, the real-time messages having predetermined timing deadlines;

a plurality of queues for indexing the messages using pointers, there being one queue for each priority band;

a dispatcher moving pointers from a lower priority queue to a higher priority queue in response to a time-out signal dependent on the timing deadline; and

a data push agent transmitting the messages indexed by the pointers according to the multiple priority levels.

2. The system of claim 1 including a reader task receiving the transmitted messages.

3. The system of claim 1 wherein there are four priority bands and a first, second, third and fourth queue, and the real-time messages are indexed by pointers in first, second, and fourth queue, and the non real-time messages are indexed by pointer in the third queue.

4. The system of claim 1 wherein the messages have a fixed size.

5. The system of claim 2 wherein the writer task and reader tasks execute on different computer systems connected by a network.

6. The system of claim 1 wherein the messages are stored in ring buffers of a reflective memory.

7. The system of claim 1 wherein each queue includes a flag to determine if the queue stores any messages.

8. The system of claim 3 wherein the time-out signal is activated by a callback facility of the dispatcher.

9. The system of claim 6 further including a manager for registering the writer and reader tasks and allocating the ring buffers.

10. The system of claim 1 wherein the non real-time messages are transmitted using round robin scheduling.

11. The system of claim 3 wherein synchronous blocking real-time messages are assigned to the first priority band, asynchronous non-blocking real-time messages are assigned to the second priority band, and non real-time messages are assigned to the third priority band.

12. The system of claim 1 including a profiler for collecting timing data while transmitting the messages.

13. A method for scheduling message transmission in a multi-tasking system, comprising the steps of:

generating real-time and non real-time messages having multiple priority levels in an ascending order arranged in a plurality of priority bands, the real-time messages having predetermined timing deadlines;

indexing the messages using pointers stored in queues, there being one queue for each priority band;

pointers from a lower priority queue to a higher priority queue in response to a time-out signal dependent on the timing deadline; and

transmitting the messages indexed by the pointers according to the multiple priority levels.