Apparatus and methods for scheduling and performing tasks

Details Apparatus and methods for scheduling and performing tasks Apparatus and methods for scheduling and performing tasks

2000-02-29

2004-06-29

An, Meng-Al T. (Department: 2127)

Electrical computers and digital processing systems: virtual mac

Task management or control

Process scheduling

C718S100000, C718S104000, C718S103000, C718S107000, C710S240000, C710S243000

Reexamination Certificate

active

06757897

ABSTRACT:

BACKGROUND OF THE INVENTION
A typical computer system includes, among other components, a processing unit (i.e., microprocessor or Central Processing Unit—CPU) that is responsible for performing, executing or interpreting a number of different tasks or processes which process data in some manner within the system. By way of example, a networked data communications device such a router or switch may include a processor that performs a primary task of transferring data in packets, cells, frames or other units between various network interfaces or ports in the data communications device. Besides the primary data transfer task, the processor may also need to perform other tasks such as protocol processing, statistics gathering, fault monitoring/handling, and so forth. While the main purpose of the processor in the data communications device is to perform the data transfer task to transfer data through a network, the device must allow the processor to perform each of the other tasks from time to time and each task may have a different level or class of importance or priority with respect to the other tasks.
Typically, a computer system that performs multiple tasks also includes an operating system that incorporates a task scheduler algorithm, routine, procedure or process. The task scheduler is generally responsible for determining the priority, class or importance of each task and for selecting and scheduling various tasks for performance and initiating the tasks on the processor in a time sliced or multiplexed manner based on the priorities of the various tasks. As an example, perhaps the processor in the data communications device only needs to perform a statistics computation task occasionally and should only perform such a task during low priority situations (e.g., situations that can allow for interruptions). The statistics computation task may have a lower assigned priority than, for example, the data transfer task which carries out the main purpose of the device of transferring data. The task scheduler may thus schedule the statistics task for performance less frequently than the data transfer task. Conversely, the processor may need to perform a fault or exception handling task only occasionally and for only a brief period of time, but when such a task is required, it is essential that the device perform it immediately in response to a condition such as a network fault to prevent a loss of data, interruption of network service or complete device failure. The fault handling task may thus have the highest assigned priority of any task. As such, when a fault occurs that must be handled by the fault handler task, the task scheduler in the operating system will schedule the fault handling task for performance over all other tasks including the data transfer task.
Some implementations of computerized devices provide multiple processors to perform different tasks or groups of tasks at the same time, one task per processor. Other arrangements provide a single processor which is responsible for performing all of the required tasks in the device. In either case, when more than one task can be performed on a processor, prior art task scheduling algorithms generally divide up a total amount of available processing cycles or processor time available on the processing unit between the various tasks that must be performed. This is typically called time slicing or time division multiplexing (TDM). Under the general theory of operation of operating systems that use prior art task scheduler algorithms, each task will execute using a segment of processor time to which that task is assigned. The task scheduler may adjust time segments assigned to tasks based on priorities of those tasks. A common example of a prior art task scheduling algorithm is called the “Round Robin” algorithm. A task scheduler within an operating system that uses round robin generally divides a block of time representing a total amount of available processor time into equal time slices and designates or assigns one time slice to each task that is to be performed. The task scheduler then allows the processing unit to execute the first task during the first time slice. When the task scheduler detects that the first time slice for the first task is complete (i.e., has elapsed), the task scheduler removes the first task from execution and places it at the end of a queue of tasks that are ready to execute and then allows the next (i.e., the second) task to execute during its assigned time slice. This process repeats for each task to be performed, hence the name round robin. A version of the round robin task scheduling algorithm that takes priorities into account may, for example, increase the size of a time slice assigned to higher priority tasks and may decrease the time slices provided to lower priority tasks.
Another prior art task scheduling technique is called “First-In-First-Out” or FIFO. Using FIFO, a task scheduler places tasks that are ready for execution into a FIFO queue. The order in which the task scheduler enters a task determines when that task performs in relation to other tasks. The processor may perform the task at the head of the queue (or the next ready task) until either the task completes, or is blocked for an event such as an input/output interrupt. At that point, the processor begins performance of the next task in the ready queue. Thus in FIFO scheduling, there is no particular fixed time slice or number of cycles for which a particular task is performed.
A third example of a prior art task scheduling algorithm is called “priority based pre-emptive scheduling.” In a priority based approach, the task scheduler assigns a relative priority to each task that the processor must perform based upon various factors such as how critical the task is to the operation of the computerized device. The task scheduler generally schedules tasks that are ready to perform based upon the relative task priorities. Thus, if three tasks indicate that they are each available to perform on the processing unit, the priority based task scheduler will generally select the task with the highest priority for performance. The task scheduler may select a task for performance from two or more tasks with equivalent priorities, for example, based on a round robin approach used for multiple tasks that share the same priority. This allows the processor to execute equal priority tasks for equal amounts of time.
In most computer systems, various events can cause a task to be blocked during performance. By way of example, a disk drive experiencing disk latency may cause a task to be blocked while waiting for data. The task scheduler can remove the blocked task from a ready queue or adjust the task's status to “waiting.” During the period of blocking, the task scheduler is able to instruct the processor to execute other tasks. When the disk drive is ready with the data for the waiting task, the disk drive processor can signal the processor via an interrupt, for example. The task scheduler can detect this condition and stop the current task from performance in order to have the processor resume performance of the waiting or blocked task by moving it back to the ready queue and setting the task's status to “ready.” Priority or pre-emptive scheduling allows tasks to execute based on their priorities and is designed to allow a device to perform tasks of high priority in favor of tasks having lower priorities.
SUMMARY OF THE INVENTION
Prior art implementations of task scheduling algorithms suffer from a number of deficiencies. Generally, these deficiencies arise since system designers typically design and create prior art operating systems for general purpose uses. In other words, the designers employ prior art task scheduling algorithms in computer devices to handle a wide range performance scenarios that can vary from use to use of the particular computer device into which they are incorporated. However, when operating systems employ prior art task scheduling techniques for performance of highly specialized applications and/or in hi

Affiliated with

Also associated with

Rating

Apparatus and methods for scheduling and performing 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 Apparatus and methods for scheduling and performing tasks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and methods for scheduling and performing tasks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3354025