Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1997-07-03
2002-06-18
Banankhah, Majid A. (Department: 2151)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C701S045000, C701S048000
Reexamination Certificate
active
06408324
ABSTRACT:
TECHNICAL FIELD
The present invention is generally directed to an operating system and a method of a computer, and is particularly directed to a system and a method in which a kernel controls execution of a plurality of processes.
BACKGROUND OF THE INVENTION
Computer data processors execute tasks to process events which arise. Single processor systems handle parallel execution of tasks for several processes via a multitasking approach. Multitasking is the execution of several tasks concurrently or in parallel. The tasks are executed logically at the same time, even though they may not be executed physically at the same time.
Within a computer, a multitasking operation is controlled by an executive or kernel of an operating system. The kernel acts as an interface between the central processing unit (hereinafter referred to as “CPU”) and the tasks to be executed. The kernel schedules the execution of the tasks such that the CPU is shared between all of the tasks in the system. Accordingly, the kernel controls which task has “possession” of the CPU.
Possession of the CPU by a task such that the task is executed (run) is determined on the basis of priority and readiness levels assigned to each task. In general, the CPU continues to execute a task toward completion until another, higher priority, task “requests” to use the CPU. The running task is interrupted and “suspended”, and the higher priority task is allowed to run. Interruption of a task may occur many times. When the higher priority tasks are eventually completed, the CPU is voluntarily surrendered. Accordingly, even though a lower priority task may be suspended many times before its completion, the task is eventually completed.
Tasks have several states. An active task is one that has control of the CPU and is being executed. Only one task is active at any given time on a multitasking CPU. An inactive task is one not being executed and which is not waiting to be executed (i.e., no events to process). A ready task is one which is waiting for CPU time (i.e., suspended or otherwise waiting to be executed). Upon occurrence of an event (e.g., generated by another task or by hardware), an associated task is upgraded to either the ready state or the active state, depending upon its priority. The kernel maintains a dynamic list or queue to organize the ready tasks so that they are executed in accordance with their priority.
Interruption of an active task by a higher priority task, such that the higher priority task becomes active, is referred to as context switching. This type of system is known in the art as an interrupt system. Context switching requires that the particulars (e.g., variables, etc.) of the interrupted task be saved to registers or another memory device such that the particulars may be restored at a later time when the task again becomes active. Thus, sufficient memory space needs to be provided. Also, the kernel frequently reviews whether a higher priority task has changed from an inactive state to a ready state (i.e., waiting to be executed) and thus should interrupt the currently active task. Accordingly, the throughput (i.e., the number of tasks executed per time period) of an interrupt-type system is limited by the associated functions of continuous priority review and context switching.
SUMMARY OF THE INVENTION
The present invention provides a multi-tasking, non-interrupt operating system for controlling performance of a plurality of processes. Means define a plurality of event queues. Each of the event queues corresponds to a process to be performed and has a priority. Means place events to be processed into the event queues. Each event queue which has at least one event to be processed is an active queue. Means search the event queues for an active queue having the highest priority. Means retrieve from the highest priority active queue an event for processing.
Means dispatch the retrieved event to a state of the process corresponding to the highest priority active queue. The state is at least a portion of the corresponding process and is associated with the processing of the retrieved event. Means cause execution of the state of the corresponding process for processing the retrieved event. The execution is not interrupted by any activity within the event queues. Means halt further performance of the corresponding process by not proceeding to another state of the corresponding process until the dispatch means dispatches a retrieved event to another state of the corresponding process.
The present invention further provides a method for controlling performance of a plurality of processes with a multitasking operating system. A plurality of event queues are defined. Each of the event queues corresponds to a process and has a priority. Events to be processed are placed into the event queues. Each event queue which has at least one event to be processed is an active queue. The event queues are searched for an active event queue which has the highest priority. An event for processing is retrieved from the highest priority active event queue.
The retrieved event is dispatched to a state of the process corresponding to the highest priority active event queue. The state is at least a portion of the corresponding process and is associated with the processing of the retrieved event. The state of the corresponding process is caused to be executed to process the retrieved event. The execution is not interrupted because of any activity within the event queues. Further performance of the corresponding process is halted by not proceeding to another state of the corresponding process until a retrieved event is dispatched to another state of the corresponding process.
REFERENCES:
patent: 4965716 (1990-10-01), Sweeney
patent: 5012409 (1991-04-01), Fletcher et al.
patent: 5046041 (1991-09-01), Lecocq et al.
patent: 5465335 (1995-11-01), Anderson
patent: 5555415 (1996-09-01), Allen
patent: 5627745 (1997-05-01), Flood
patent: 5870582 (1999-02-01), Cheong et al.
patent: 5938708 (1999-08-01), Wallace et al.
Rönngren et al; A Comparative Study of Parallel & Sequential Priority Queue Algorithims ACM Transactors on Modeling & Computer Simulation v.7, n 2 pp. 157-209, Apr. 1997.*
Lee Schruber, “Modeling Priority Queues with Entity Lists : A Sigma Tutorial” Proceedings of 1992 Winter Simulation Conference pp. 380-384, 1992.*
Allen et al., Extending the statechart formalism:event scheduling and diposition, OOPSLA '95.*
Atlee et al, State-based checking of event-driven system requirements, ACM Dec. 1991.
Karolak Dale Walter
Wallace Jon Kelly
Banankhah Majid A.
Tarolli, Sundheim, Covell Tummino & Szabo L.L.P.
TRW Inc.
LandOfFree
Operating system having a non-interrupt cooperative... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Operating system having a non-interrupt cooperative..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Operating system having a non-interrupt cooperative... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2961108