Electrical computers and digital processing systems: virtual mac – Task management or control – Process scheduling
Reexamination Certificate
2000-12-29
2004-11-16
Follansbee, John (Department: 2154)
Electrical computers and digital processing systems: virtual mac
Task management or control
Process scheduling
C718S102000, C718S103000, C718S107000
Reexamination Certificate
active
06820263
ABSTRACT:
CROSS-REFERENCE TO RELATED APPLICATIONS
This is the first application filed for the present invention.
MICROFICHE APPENDIX
Not applicable.
TECHNICAL FIELD
This invention relates, in general, to shared memory systems for use in parallel processing environments and, in particular, to methods and systems for time management in a shared memory parallel processor environment.
BACKGROUND OF THE INVENTION
The rapid growth of the Public Switched Telephone Network (PSTN), especially the rapid expansion of service features has strained the processing capacity of incumbent switching equipment. This is particularly the case in wireless telephony environments where messaging loads between mobile switching centers are great. As is well known, most incumbent switching equipment in the PSTN have processing architectures that are based on a single central control component that is responsible for all top level processing in the system. Such single-central-control-component-architectures provide the advantage to application programmers of some simplification with respect to resource control, flow control and inter-process communication. However, single-central-control-component-architectures are subject to serious bottlenecks, due principally to the fact that each process is dependent on the capacity of the single core processor. There has therefore been an acute interest in developing parallel processor control for incumbent switching systems in order to improve performance and permit the addition of new processor-intensive service features.
Parallel processor architectures are well known. However, the software written for parallel processor architectures is specifically designed to avoid processor conflicts while accessing shared resources, such as shared memory. This is accomplished by providing exclusive access to the shared memories using software semaphores or methods for locking memory access buses, and the like. However, incumbent switching systems in the PSTN were typically written for a central control component, and, in many cases, it is not economically feasible to rewrite the application code for a parallel processor architecture. Aside from the complexity of such a rewrite, the time and cost incurred to complete such a task is generally considered to be prohibitive.
It is known in the art that a shared memory parallel processor computing environment requires time management in order to ensure that any given process or class of processes is not permitted to monopolize processor time to the exclusion of other processes. It is also known that the time management must ensure that adequate processing time is allocated to system-critical processes, such as payload processes. Time management is therefore a critical aspect of the control of a shared memory parallel processor computing environment.
A time management algorithm for a shared memory parallel processor computing environment designed and implemented by the Assignee operated on the basis of timed hardware interrupts. At each interrupt, a timer queue was shuffled and process execution on each of the parallel processors was controlled. This is a common model of time management implemented in many prior art computing machines. One problem with time management based on-timed interrupts is that each interrupt consumes a certain proportion of system resources. If the interrupts are executed on a timed schedule, then at least some of the interrupts are invariably executed unnecessarily. Thus, system resources are wasted. Furthermore, in order to manage computing resources using timed interrupts, unnecessary operations are performed at each interrupt in order to ensure that processes do not monopolize resources. For example, each time an interrupt occurs, a status of a process being executed by each processor must be verified to ensure that the process has not used more than its share of computing resources. This occurs even if the process has just been started.
While the timed interrupt represents a viable approach to time management in a shared memory parallel processor computing environment, it is not an optimal one because it fails to utilize system resources in a most efficient way.
It is therefore highly desirable to provide a method and system for time management processes in a shared memory, parallel processor computing environment that enhances performance by ensuring that access to computing resources is optimized.
SUMMARY OF THE INVENTION
It is therefore an object of the invention to provide methods for time management in a shared memory parallel processing computing environment.
It is a further object of the invention to provide a shared memory parallel processor computing machine with improved time management for process execution and timer queue management.
The invention therefore provides a method of managing execution time in a shared memory parallel processor computing environment in which a plurality of independent processors execute processes simultaneously. The method comprises steps of: defining a plurality of process classes and assigning each process to be executed to a one of the process classes; defining an execution time slice for each of the process classes; and permitting a process to be executed by a one of the processors without interruption until the execution time slice associated with the process class has expired.
The method further comprises a step of enabling processes of at least one of the process classes to call a lock procedure during execution, which permits the process to continue to be executed without interrupt for a predefined period of time after the time slice associated with the process class has expired. The at least one process is also enabled to call an unlock procedure to permit execution of the process to be terminated before the predefined period of time has expired. The predefined lock period may be an integer multiple of the time slice associated with the process class. Preferably, the lock procedure may be called repeatedly by the same process in order to simplify programming and accounting.
The invention further provides a method of managing a timer queue in a shared memory parallel processor computing environment in which a plurality of independent processors execute processes simultaneously, the timer queue being used to queue processes in a wait state until a predetermined process removal time has expired, the method comprising steps of: defining a variable for storing a time at which a next process is to be removed from the timer queue; periodically examining the variable without generating a system interrupt to determine whether the time stored in the variable is less than or equal to an instant system time; removing each process from the timer queue which has an associated removal time that is less than or equal to the instant system time; and re-computing a time at which a next process is to be removed from the timer queue, and storing the re-computed time in the variable. Adding new processes to the timer queue further comprises steps of: computing a delay time specified by the process to be added to the queue; comparing the computed delay time with the time stored in the variable; if the computed delay time is less than the delay time stored in the variable, replacing the delay time stored in the variable; and adding the process to the timer queue.
The invention further provides a shared memory parallel processor computing machine in which a plurality of independent processors simultaneously execute processes, comprising: means for associating each process to be executed with a process class that defines rights and priorities associated with the process; means for associating an execution time slice with each of the process classes; and means for monitoring a process during execution to permit the process to be executed by a one of the processors without interruption until the execution time slice associated with the process class has expired. The means for permitting a process to be executed without interruption preferably comprises a time slice counter that is initiali
(Ogilvy Renault)
Follansbee John
Nortel Networks Limited
Patel Ashok B.
Wood Max R.
LandOfFree
Methods and system for time management in a shared memory... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and system for time management in a shared memory..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and system for time management in a shared memory... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3355634