Electrical computers and digital processing systems: processing – Processing control – Context preserving (e.g. – context swapping – checkpointing,...
Reexamination Certificate
1997-07-08
2001-07-17
Pan, Daniel H. (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Context preserving (e.g., context swapping, checkpointing,...
C712S217000, C712S248000, C712S042000, C710S019000, C709S226000
Reexamination Certificate
active
06263425
ABSTRACT:
TECHNICAL FIELD
The present invention relates to a circuit that implements semaphores in a multiprocessor environment and, in particular, to such a circuit that does not rely on atomic test and set operations of the processor cores.
BACKGROUND
The use of single bit semaphores for signalling between computer implemented processes is well known. In general, a single bit semaphore is used in a scheme to prevent multiple processes from simultaneously accessing a single resource of a system. It is important that a single bit semaphore be accessible only in an “atomic” manner. That is, it must be guaranteed that a semaphore cannot be modified by a second process between the time that a first process reads the semaphore and potentially modifies the semaphore.
One conventional mechanism for guaranteeing such exclusivity of access includes the use of a “lock” signal. For example, the x86 family of processors provide a lock instruction that provides a serialization mechanism such that a resource (as represented by the semaphore) is restricted for use by the holder of the lock (i.e., the process that executed the lock instruction). In particular, executing a lock instruction causes a lock signal to be asserted. While the lock signal is asserted, no other process can access the semaphore. This exclusion is guaranteed by additional circuitry that stalls simultaneous access to the memory that holds the semaphore between the read and the write of the test and set operation.
While some processor architectures include the lock signal, other processors do not. With such processors, a similar mechanism may be implemented using a general purpose I/O signal assigned to generate the lock signal. It is also known to implement a lock mechanism using a dedicated hardware circuit, as disclosed by Dror in U.S. Pat. No. 5,276,886.
SUMMARY
In accordance with the present invention, a single bit semaphore circuit is provided. In accordance with the invention, each process that uses a particular single bit semaphore has associated with it semaphore interface circuitry.
The hardware semaphore is one bit wide. A first hardware circuit detects one of the processes is writing a new value to the semaphore and forces the hardware semaphore to the new value written. A plurality of second hardware circuits are provided. Each second hardware circuit is associated with a separate one of the plurality of processes. Each of the particular second hardware circuit includes a detecting circuit that detects the processor with which the particular second hardware circuit is associated is attempting to write the new value to the semaphore; and means responsive to the detecting circuit that provides the current value of the semaphore, before the write attempt, to an output of the second particular hardware circuit.
In operation, a process writes to the Set.i bit or Clear.i bit of the set and clear circuitry, respectively, associated with the process and then reads from the Test.i bit of the storage circuitry associated with the process. If the read value of the Test.i bit indicates that the Test.i bit was asserted before the write, then this indicates that the attempted “lock” of the semaphore by the process failed. Put another way, if the Test.i bit was asserted before the write, the semaphore is presently being controlled by another process. Similarly, if the Test.i bit was not asserted before the write, the semaphore is presently not being controlled by another process (and is now controlled by the setting process).
REFERENCES:
patent: 5276886 (1994-01-01), Dror
patent: 5367690 (1994-11-01), Schiffleger
patent: 5594880 (1997-01-01), Moyer et al.
National Semiconductor Corporation
Pan Daniel H.
Stallman & Pollock LLP
LandOfFree
Circuit that implements semaphores in a multiprocessor... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Circuit that implements semaphores in a multiprocessor..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Circuit that implements semaphores in a multiprocessor... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2464922