Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1998-03-10
2002-08-06
Courtenay, III, St. John (Department: 2151)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C712S034000, C712S229000
Reexamination Certificate
active
06430593
ABSTRACT:
The present patent application is related to the following patent applications which are being filed simultaneously (and are hereby incorporated herein) and are assigned to the same entity, Motorola, Inc.: CR00193M, Method, Device and Article of Manufacture for Implementing a Real-Time Task Scheduling Accelerator, by Brett Louis Lindsley, Uri Dayan and Moshe Tarrab; CR00194M, Method, Device and Article of Manufacture for Specifying and Controlling a Task Switch from an External Device in a Multi-Tasking Preemptive Priority-Based Real-Time Operating System, by Brett Louis Lindsley and Ed Martinez; CR00195M, Method, Device and Article of Manufacture for Clearing Command Bits in a Task Scheduling Device for a Multi-Tasking Preemptive Priority-Based Real-Time Operating System, by Brett Louis Lindsley; and CR00196M, Method, Device and Article of Manufacture for Efficient Data Queuing Using Hardware Queue Pointers and a Software Interrupt Service Routine in a Multi-Tasking Preemptive Priority-Based Real-Time Operating System, by Brett Louis Lindsley.
FIELD OF THE INVENTION
The field of the invention relates to multiple task execution processors, in particular, a multi-task execution processor having a preemptive prioritized task scheduling system.
BACKGROUND OF THE INVENTION
Multi-tasking is the capability of a single processor to execute multiple tasks concurrently. A processor performs multi-tasking execution by switching between tasks using a defined set of multi-tasking rules. For theoretical reasons, real-time multi-tasking systems preferably use a set of rules where tasks are prioritized. Lower priority tasks can be preempted (forcibly switched) to execute a higher priority task if necessary. This “preemptive prioritized” system always executes the highest priority ready task.
A “task” is defined as an independent entity of computing. For example, where a computer system permits many users on different terminals access to the same processor, the computer system assigns a unique task to each user's computing (where each user's computing is unrelated to another user's computing). Generally, a task unit contains an entry for each task. Tasks are typically synchronized using “events” An event is used to indicate that an activity has taken place, such as data arrival, time-out, etc. Thus, an event may indicate execution of a task, an interrupt service routine or the like. Events are counted using semaphores. Semaphores synchronize the event producer and the event consumer as shown in
FIG. 2
, numeral
200
.
Events are generated by tasks
201
or interrupt service routines (ISRs)
202
. ISRs are not allowed to consume events because ISRs are not scheduled and execute outside of the normal task scheduling environment of the processor. However, ISRs are allowed to generate events to indicate the status of the cause of the interrupt.
A counting semaphore
203
allows a plurality of events to be generated without being lost. Similarly, a plurality of tasks may be waiting for the same event. When the semaphore counter is positive, it indicates events have been produced but no tasks are waiting for the events. When the semaphore counter is zero, it indicates no events have been generated and no tasks are waiting. When the semaphore counter is negative, it indicates there are no events generated but a plurality of tasks are waiting for the events. The process of generating an event to a semaphore is typically called “posting” the event
204
. The process of waiting for an event from a semaphore is typically called “pending” for the event
205
.
When an event is generated for a semaphore that has a list of tasks pending, the task
206
at the head of the list becomes ready for execution. At this time, the task scheduling function
207
must determine if this task should be selected for execution or if it should be put in a list with other ready tasks to be executed at a later time. This decision is based on the priority of the task that is currently executing compared to the priority of the task that has just become ready.
If the task that has just become ready is the same or lower priority than the currently executing task, the currently executing task continues executing. The new ready task is moved to a list to be executed at a later time.
If the task that has just become ready is a higher priority than the currently executing task, the currently executing task is preempted to allow the new ready task to execute. Thus, the highest priority ready task
208
is always selected for execution.
At some time, the currently executing task completes its computation and becomes inactive. A task becomes inactive by pending on a semaphore when the semaphore count is zero or negative. For example, a semaphore may represent data buffers that require processing. If the task that processes data buffers pends for the semaphore that represents data buffers, the task is synchronized to the data buffer generation. If data buffers are available, the semaphore count is greater than zero. Task pend requests on the semaphore allow the task to continue. If data buffers are not available, the semaphore count is less than or equal to zero. When the task pends on the semaphore with a count that is less than or equal to zero, the task does not have data for processing and will block execution.
At the point when a task pends on a semaphore with zero or negative count, the task that has made the request is not allowed to continue execution and must “block” The task scheduling function stops this task and selects another task s for execution. The task scheduling function looks at other ready tasks at the same or lower priorities to determine the next highest priority ready task. If a task is found, it is selected for execution. If a task is not found, the processor is put into an idle state until a task becomes ready.
Although the task selection process is easy to understand, in a practical environment this can lead to significant inefficiencies. For example, the following cause inefficiencies in a preemptive prioritized task scheduling system:
Each time a semaphore is processed, there is a potential for a task change. This causes the scheduling function to be called quite often when many times there is no change.
When a task pends for a semaphore and blocks, the scheduler must perform a search algorithm to determine the next ready task. If there are a large number of tasks and priority levels, this activity may be time-consuming.
The process of searching for a task may have variable timing making task scheduling functions non-deterministic.
The task scheduler must obtain control of the processor to switch tasks.
In a software task scheduling system, interrupt service routines typically require entry and exit code to flag interrupt usage and nesting. The flagging is typically used to call the scheduler to determine if the interrupt generated an event that may have changed execution. The use of entry and exit code consumes time and is undesirable when processing interrupts.
Solutions to the problems set forth above typically involve constraining the functionality of the scheduler. These constraints may include limiting the number of tasks, limiting the number of priority levels, limiting the number of tasks at each priority level, limiting the representation range of the semaphore counter, etc. It is undesirable to have such constraints in a system because such constraints may restrict the type of system that can be supported.
Thus, there is a need for a method, device and article of manufacture that optimizes real-time multi-tasking for a processor.
REFERENCES:
patent: 4964040 (1990-10-01), Wilcox
patent: 5125093 (1992-06-01), McFarland
patent: 5168566 (1992-12-01), Kuki et al.
patent: 5452452 (1995-09-01), Gaetner et al.
patent: 5465335 (1995-11-01), Anderson
patent: 5528513 (1996-06-01), Vaitzblit et al.
patent: 5652890 (1997-07-01), Foster et al.
patent: 5694604 (1997-12-01), Reiffin
patent: 5742825 (1998-04-01), Mathur et al.
patent: 5832262 (1998-11-01), Johnson et al.
patent: 6052580 (2000-04-
Courtenay III St. John
Motorola Inc.
Nguyen Van H.
LandOfFree
Method, device and article of manufacture for efficient task... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method, device and article of manufacture for efficient task..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method, device and article of manufacture for efficient task... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2894727