Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1997-07-29
2003-03-04
Banankhah, Majid (Department: 2316)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
Reexamination Certificate
active
06529933
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
This invention is related in general to data processing systems and in specific to data processing systems using semaphores to enforce mutually exclusive access to resources.
BACKGROUND OF THE INVENTION
Multiprocessor data processing systems typically have a number of coordinated processes and devices that are working on a common task. These processes will often access shared resources, such as sections of memory or input/output devices. Each resource, however, can only be accessed by one process at a time. Therefore, the system must ensure that two processes do not simultaneously access the same resource.
Processes use semaphores, or lock variables, to coordinate and synchronize access to resources. A semaphore enforces mutual exclusion of a resource. Each resource has a corresponding semaphore. When a process requires access to a resource, it first checks the semaphore to determine whether the resource is available. If the resource is available, the process sets that resource's semaphore to indicate that it has exclusive access to that resource. Once the process is finished with the resource, it sets the semaphore to indicate that the resource is available.
Typically, a semaphore value of “0” indicates that the resource is free, while any other value indicates that the resource is locked. A process acquires a semaphore by using a series of instructions to perform an atomic “test and set lock” (“TSL”) operation. A TSL operation copies the semaphore and then sets it to a positive value. To release a resource, a process uses a “clear and invalidate” (“CI”) operation to set the semaphore to 0.
Prior art data processing systems required multiple bus transfers to perform either a TSL or CI operation. To perform a TSL operation, a process first sent a read instruction to a lock manager containing the address of the lock variable on the bus. Then, the lock manager sent a data transfer containing the value of the lock. Next, the process sent a write instruction containing the address of the lock. Finally, the process sent a data transfer containing the new value of the lock.
A CI operation also required multiple transfers. The process first sent an write instruction to the lock manager containing the address of the lock. Then, the process sent a data transfer containing the new lock value.
Sending multiple transfers to perform either a TSL or CI operation is inefficient. Each bus transfer sent by a process decreases the time the process has to perform other tasks. Likewise, the bus must complete the transfers, thereby decreasing the amount of other information that can be transferred.
In addition, a process had to ensure that no other process accessed the same semaphore during the atomic TSL operation. One technique to prevent access by another process was a bus lock pin, which allowed a process to perform back-to-back bus transfers. Another such technique was to let the process monitor the bus to detect any other access to the same semaphore address during the TSL operation.
However, each of the above techniques has undesirable consequences. The bus lock pin necessarily locks the bus, thereby temporarily disabling other processes and devices from using the bus. Similarly, bus monitoring requires additional logic for the device-bus interface. In addition, two processes could enter into a deadlock when trying to lock the same semaphore.
Therefore, there exists a need in the art for a method and apparatus for executing TSL and CI operations using fewer bus transfer per operation than the prior art. In addition, there exists a need in the art for a method and apparatus for executing an atomic TSL operation without locking or monitoring the bus.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide a method and apparatus for increasing the processing speed of a data processing system.
It is another object of the present invention to provide a method and apparatus for efficiently controlling semaphores.
It is yet another object of the present invention to provide a method and apparatus for testing and setting a semaphore using one address bus transfer and one data bus transfer.
It is yet another object of the present invention to provide a method and apparatus for clearing and invalidating a semaphore using only an address bus transfer.
These and other objectives of the present invention are met by a data processing system that automatically changes a semaphore in response to a test and set or clear and invalidate instruction. When a device desires to either test and set or clear and invalidate a semaphore, it transfers an instruction having a test and set or clear and invalidate operation code and the address of the semaphore over the bus. The device responsible for managing the semaphore receives the instruction and automatically changes the semaphore. Therefore, a device is only required to transfer the instruction to test and set or clear and invalidate the semaphore. Moreover, because the test and set operation requires only a single instruction transfer, special techniques are not necessary to insure exclusive access to the semaphore during the operation.
The foregoing has outlined rather broadly the features and technical advantages of the present invention in order that the detailed description of the invention that follows may be better understood. Additional features and advantages of the invention will be described hereinafter which form the subject of the claims of the invention. It should be appreciated by those skilled in the art that the conception and the specific embodiment disclosed may be readily utilized as a basis for modifying or designing other structures for carrying out the same purposes of the present invention. It should also be realized by those skilled in the art that such equivalent constructions do not depart from the spirit and scope of the invention as set forth in the appended claims.
REFERENCES:
patent: 4604683 (1986-08-01), Russ et al.
patent: 4630264 (1986-12-01), Wah et al.
patent: 4642630 (1987-02-01), Beckner et al.
patent: 5067071 (1991-11-01), Schanin et al.
patent: 5187790 (1993-02-01), East et al.
patent: 5237694 (1993-08-01), Horne et al.
patent: 5261108 (1993-11-01), Hayashi et al.
patent: 5276886 (1994-01-01), Dror
patent: 5289585 (1994-02-01), Kock et al.
patent: 5339443 (1994-08-01), Lockwood
patent: 5446910 (1995-08-01), Kennedy et al.
patent: 5485594 (1996-01-01), Foster
“An Introduction to operating systems” Harvey M. Dertel Addison-Wesley Publishing Company 1991.*
“Computer Architecture, A Quantitative Approach,” David A. Patterson and John L. Hennessy, pp. 471-474, 1990.
“Computer Organization & Design, The Hardware/Software Interface,” David A. Patterson and John L. Hennessy, pp. 614-616, 1990.
Montgomery Michael Edward
Sherman Kevin Lee
Banankhah Majid
Chadurjian Mark F.
LandOfFree
Method and apparatus for locking and unlocking a semaphore does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for locking and unlocking a semaphore, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for locking and unlocking a semaphore will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3003193