Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1998-06-30
2002-12-24
Banankhah, Majid A. (Department: 2156)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000
Reexamination Certificate
active
06499048
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to program controlled apparatus which is capable of executing multiple processes. The processes can include operating system processes, for example.
In machines for processing multiple processes (e.g. multiple threads) and multi-processor machines, the threads and/or processes can act independently on the ‘real state’ of the machine. Where reference is made to the ‘real state’ this is to be understood to encompass the programmer visible state, subject to certain constraints. Thus it includes the content of a fixed set of registers, including the program counter and main memory, but excludes transitory elements such as caches and intermediate pipeline values. The ‘real state’ includes all data required for context switching between processes plus, for example, operating system status data.
The separate threads or processors may not progress at the same pace, and the relative progress of the multiple threads or multiple processors need not be related. Imagine two processes in each of two separate compared processor sets initially have the same real state. If both of the processes of each processing set need a new resource, say a page of memory, they will act to acquire the page from a pool of spare pages held in the real state. Consider a situation where, in a first processing set PUA, one processor P
0
is slightly faster and acquires the next page. In a second processing set PUB, P
1
is slightly faster and acquires the next page. The real states of the processing sets have diverged, never to re-converge. In a single processor system, lockstep operation depends on the deterministic delivery of interrupts. In a multiple processor system, lockstep operation also depends on the internal details of core operations (i.e., operations on the real state not involving I/O).
Accordingly, an aim of the invention is to enable deterministic or equivalent operating of multiple processes, or multiple processors of a multi-processing system.
SUMMARY OF THE INVENTION
Particular and preferred aspects of the invention are set out in the accompanying independent and dependent claims. Combinations of features from the dependent claims may be combined with features of the independent claims as appropriate and not merely as explicitly set out in the claims.
In accordance with one aspect of the invention, there is provided a program controlled apparatus comprising at least one execution unit for executing multiple programmed processes and a mutual exclusion primitive (mutex) ordering mechanism controlling the ordering of mutex ownership to provide deterministic execution of the processes.
By controlling the order of mutex ownership, it is possible to control the execution of the processes to achieve deterministic execution therefor. This can enable fault tolerance to be built into many multi-process (multi-threaded) processing environments including, for example, networked fault tolerant systems.
A mutex processor can be operable to monitor mutex registers for determining mutex ownership. By controlling the access to the mutex registers, that is the ownership thereof, a deterministic ordering of mutex processing can be achieved.
The mutex registers can be configured as sets of mutex request registers and mutex release registers.
The invention finds application, for example, to a single processor configured to process multiple threads, or processes concurrently. The processes could, for example, be operating system processes. The invention also finds application to a plurality of processing units, each configured to process at least one thread. A monitor unit can be connected to the processing units for monitoring equivalent operation of the processors. Each processing unit may be configured to process multiple threads concurrently. The invention also finds application to apparatus comprising a plurality of processing sets, where each processing set comprises a plurality of processors. A monitor unit can be provided for monitoring equivalent operation of the processing sets, the monitor unit comprising the mutex ordering mechanism.
In accordance with another aspect of the invention, there is provided computing apparatus including a plurality of processing sets, wherein at least a first processing set is operable asynchronously of a second processing set. At least one resource for each of the processing sets is shared by the processors of the processing set. A mutex ordering mechanism is provided which is configured to ensure equivalent ordering of mutexes for the processing sets for controlling access by processors of respective processing sets to the respective resources, thereby to enable deterministic operation of the processing sets.
The mutex ordering mechanism can be formed from a monitor connected to receive I/O operations output from the processing sets, the monitor further being operable to synchronise operation of first and second processing sets by signalling the processing sets on receipt of output I/O operations indicative of a plurality of the processing sets being at equivalent stage of processing.
The monitor is operable to compare I/O operations for determining equivalent operating of the processing sets. The monitor can include a voter for determining equivalent ordering of I/O operations and common mutex storage accessed by voted I/O operations. The monitor comprises a mutex manager which can include a mutex start register and a mutex stop register per processing set. The mutex manager could also be provided with multiple sets of mutex start registers and a hash mechanism for accessing a mutex list for an I/O cycle.
In accordance with another aspect of the invention, there is provided a method of providing deterministic execution of multiple processes, the method comprising:
executing the processes; and
controlling the ordering of mutexes to provide deterministic execution of the processes.
In accordance with yet a further aspect of the invention, there is provided a method of providing deterministic operation of an asynchronous multi-processor computer system, the method comprising:
ordering mutexes for access to system resources; and
operating the processors in accordance with the ordering of the mutexes.
REFERENCES:
patent: 5598562 (1997-01-01), Cutler et al.
patent: 5727203 (1998-03-01), Hapner
patent: 6003061 (1999-12-01), Jones et al.
patent: 6029190 (2000-02-01), Oliver
patent: 6246668 (2001-06-01), Kusyk
patent: 6247143 (2001-06-01), Williams
patent: 6282701 (2001-08-01), Wygodny et al.
patent: 6301676 (2001-10-01), Kumar et al.
Banankhah Majid A.
Kivlin B. Noäl
LandOfFree
Control of multiple computer processes using a mutual... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Control of multiple computer processes using a mutual..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Control of multiple computer processes using a mutual... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2986339