Electrical computers and digital processing systems: memory – Storage accessing and control – Shared memory area
Reexamination Certificate
2000-10-27
2004-06-15
Bataille, Pierre-Michel (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Shared memory area
C711S168000, C711S170000, C710S244000, C709S241000
Reexamination Certificate
active
06751711
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 process rollback in a shared memory parallel processor environment.
BACKGROUND OF THE INVENTION
The rapid growth in 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 centres are intense. As is well known, most incumbent switching systems 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 to improve performance and permit the addition of new processor-intensive service features.
Parallel processor architectures are well known. However, the software written for such 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 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 when a shared memory parallel processor computing environment is used to execute code written for a single central control component, two processes can compete for a memory space in the shared memory. This competition is called blocking. Because rights to a memory space cannot be granted to more than one process at a time, one process must be “rolled back” while the other process is permitted to continue execution.
A shared memory control algorithm for mutual exclusion and rollback is described in U.S. Pat. No. 5,918,248, which issued on Jun. 29, 1999 to the Assignee. The patent describes a mechanism for permitting a shared memory single central control component parallel processing architecture to be used in place of a conventional system, without requiring code written for the conventional system to be rewritten. Exclusive Access and Shared Lead Access implementations are disclosed. A rollback mechanism is provided which permits all the actions of a task in progress to be undone. The memory locations of that parallel processor architecture include standard locations and shared read locations. Any task is granted read access to a shared read location, but only a single task is granted write access to a shared read location at any given time.
A prior art rollback mechanism designed by the Assignee uses three priority levels (
0
,
1
and
2
). When two processes compete for the same memory space, the process with the higher priority is permitted to continue execution and the process with the lower priority is rolled back. Initially, each process is assigned a default priority value of zero. When two processes having zero priority compete for a same memory space, the processes are executed on a first-in-first-out basis. The process that is rolled back then has its priority set at
1
. If the same process is rolled back a second time, due to competition with another priority
1
process, the priority of the process is set at
2
, which is the highest priority permitted. The scheduler ensures that only one priority
2
process is allowed to execute on the system at any one time. After the process has reached a commit point, the priority associated with the process is reset to zero.
While this algorithm represents a significant advance in the art, the rollback mechanism has not proven to support optimal performance. Performance is compromised for the principal reason that processes belonging to large classes are rolled back too often to meet their CPU time requirement.
It is therefore highly desirable to provide a method and system for rolling back 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 and systems for process rollback in a shared memory, parallel processor computing environment that enhances performance by ensuring that processes are rolled back in proportion to their allotted processing time.
In accordance with a first embodiment of the invention, there is provided a method for process rollback in a shared-memory parallel-processor computing environment in which the parallel processors are operated concurrently and each processor sequentially runs processes. In accordance with the method, when two processes compete for a memory space in the shared memory, one of the processes is rolled back. The process that is rolled back is the process that has a lower priority value, or if the two processes have the same priority value, the process that collided with an owner of the memory space is rolled back. A process collides with the owner of the memory space if it attempts to access the memory space when the owner has possession of the memory space.
When a process is rolled back, a new priority value is computed for the rolled-back process. The new priority value is computed for the rolled-back process by incrementing the processes priority value by a predetermined amount. If the two processes are members of different classes, the predetermined amount is preferably a priority value assigned to a class of which the rolled-back process is a member. If the two processes are members of the same class, the predetermined amount is preferably less than the priority value assigned to the class. When a process reaches a commit point, the priority value of the process is reset to a priority value assigned to the class of which the process is a member.
The priority value assigned to the class is preferably related to a proportion of processor time allocated to the class. The priority value may be directly proportional to the processor time allocated to the class, for example. In accordance with the first embodiment of the invention, the priority value of each process is stored in a process control block associated with the process.
The invention also provides a shared memory parallel processor system for executing processes concurrently, comprising means for storing a priority value associated with each process; means for determining which one of two processes is to be rolled back using the priority values associated with each of the two processes when the two processes compete for a memory space; and, means for computing a new priority value for the process that is rolled back.
The means for determining which process is to be rolled back, comprises means for selecting the process that has a lower priority value, when the two processes have different priority values; and, means for selecting the process that collided with an owner of the memory space, when the two processes have the same priority value. When a collision occurs because two processes compete for a memory space, the system determines a class of which each process is a member. The
(Ogilvy Renault)
Bataille Pierre-Michel
Nortel Networks Limited
Wood Max R.
LandOfFree
Methods and systems for process rollback 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 systems for process rollback in a shared memory..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and systems for process rollback in a shared memory... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3364902