Method and apparatus for locking and unlocking a semaphore

[0002] This application is a continuation of application Ser. No. 08/486,909, filed on Jun. 7, 1995, which was abandoned upon the filing hereof.

[0003] 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.

[0004] 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.

[0005] 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.

[0006] 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.

[0007] 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.

[0008] 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.

[0009] 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.

[0010] 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.

[0011] 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.

[0012] 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.

[0013] It is an object of the present invention to provide a method and apparatus for increasing the processing speed of a data processing system.

[0014] It is another object of the present invention to provide a method and apparatus for efficiently controlling semaphores.

[0015] 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.

[0016] 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.

[0017] 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.

[0018] 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.

[0019] For a more complete understanding of the present invention, and the advantages thereof, reference is now made to the following descriptions taken in conjunction with the accompanying drawings, in which:

[0020] FIG. 1 illustrates a data processing system embodying the present invention;

[0021] FIG. 2 is a flow chart showing the logical steps performed by a data processing system using semaphores in accordance with the present invention; and

[0022] FIG. 3 is an alternative embodiment of the data processing system of FIG. 1.

[0023] A representative hardware environment for practicing the present invention is depicted in FIG. 1, which illustrates a typical hardware configuration of a workstation in accordance with the present invention having two processors 10, 12 such as conventional microprocessors, connected via common processor interface bus 14 (hereafter “processor bus”) to a memory controller and input/output (“I/O”) bridge 16 (hereafter “memory controller”). Memory controller 16 is connected to random access memory (“RAM”) 18 and read only memory (“ROM”) 20 via memory bus 21 and to a number of other units via common I/O bus 22. The workstation shown in FIG. 1 also includes I/O adapter 24 for connecting peripheral devices such as disk units 26 and tape drives 28 to I/O bus 22, user interface adapter 30 for connecting keyboard 32, mouse 34, microphone 36, speaker 38, and/or other user interface devices such as a touch screen device (not shown) to bus 22, communication adapter 40 for connecting the workstation to a data processing network, and display adapter 42 for connecting bus 22 to display device 44. In the present discussion, any device on processor bus 14, memory bus 21 or I/O bus 22 which is capable of being locked by a semaphore is referred to as a “resource.”

[0024] CPUs 10, 12 can be any type of microprocessor. The only requirement is that the CPUs 10, 12 support address and data bus transfers with the capability to send address only transfers. Although FIG. 1 discloses a system with two CPUs 10, 12, the invention achieves utility in systems with any number of CPUs. In addition, the present invention works equally well in a data processing system with at least one multitasking processor. For purposes of this discussion, each process or task executing on a CPU 10, 12 is considered to be a separate “device.”

[0025] Processor bus 14 connects the CPUs 10, 12 to memory manager 16. A preferred embodiment of processor bus 14 is actually two separate busses, one carrying instructions and the other carrying data. An alternative embodiment of processor bus 14, however, is a single bus carrying instructions and data. As used herein, “instruction” refers to a binary word comprising an operation code and an address. “Data,” in contrast, refers to at least one word having any value. “Operation,” used alone, refers to a sequence of steps or instructions executed by the data processing system.

[0026] Memory manager 16 manages CPU 10, 12 requests to access RAM 18, ROM 20, or I/O bus 22. I/O bus 22 carries data transmitted among the various system devices. Like the processor bus 14, I/O bus 22 can be comprised of a single bus or dual busses. In addition, devices on I/O bus 22 can access RAM 18 or ROM 20 by sending requests to memory manager 16. Memory bus 21 transfers data between RAM 18, ROM 20 and memory controller 16.

[0027] In a preferred embodiment of the present invention, semaphores are managed by memory controller 16. Thus, CPUs 10, 12 or any other device request semaphore locks and unlocks by sending requests to memory controller 16. However, any system device can manage semaphores as long all devices needing semaphores can send requests to the proper device.

[0028] A semaphore, or lock variable, may be stored at a specific address within RAM 18 or another place in the data processing system, such as a register associated with a resource. Each semaphore is represented as a binary word. In a preferred embodiment, a semaphore value of 0 indicates that the resource is free, while a positive value indicates the resource is locked.

[0029] Each semaphore is associated with a specific resource, such as RAM 18, that can be locked. Semaphores are most commonly used by processes executing on CPUs 10, 12 to synchronize and coordinate access to RAM 18. In such a case, processes can use a semaphore to lock specific addresses within RAM 18. In addition, processes will frequently use semaphores to lock I/O devices 24-44. However, the present invention is not limited to only processes and can be implemented to allow any device in the data processing system to lock any resource.

[0030] FIG. 2 is a flow chart showing the steps performed by a data processing system using semaphores in accordance with the present invention. In the example of FIG. 2, CPU 10 is the device using the semaphore. At step 210, CPU 10 is executing a process that needs to enter a critical section requiring exclusive access to a resource. A critical section is a procedure that cannot be executed simultaneously by another process.

[0031] At step 212, CPU 10 attempts to obtain a resource lock by executing a test and set lock (“TSL”) operation on the desired resource's semaphore. When CPU 10 executes a TSL operation, it sends a processor bus instruction transfer to memory controller 16 containing a TSL operation code and an address. Then, at step 214, memory controller 16 determines from the operation code that it should read the current value of the semaphore at the specified address, send that value back to CPU 10, and then set the semaphore to a positive value.

[0032] After CPU 10 receives the value of the semaphore from memory controller 16, CPU 10 checks the value to determine whether the semaphore was 0 and, therefore, the resource was free (step 216). In such a case, CPU 10 can execute its critical section because it now has a lock on the resource (step 218).

[0033] If the value is positive at step 216, then another device already has the semaphore for the desired resource. In that case, CPU 10 will typically sit in a loop and spin-wait for the resource. That is, CPU 10 will loop back to step 212 and repeatedly execute TSL operations until it acquires the semaphore lock.

[0034] After CPU 10 has completed its critical section (step 218), it releases, or unlocks, the semaphore. To unlock the semaphore, CPU 10 executes a clear and invalidate operation (“CI”). This operation causes CPU 10 to send a processor bus 14 instruction transfer to memory controller 16 containing a CI operation code and an address (step 220). Then, memory controller 16 determines from the operation code that it should clear the semaphore at the specified address. At step 222, memory controller 16 releases the semaphore lock by clearing the memory location specified in the bus transfer.

[0035] It is important to note that memory controller 16 automatically changes the value of the semaphore in response to only an instruction transfer from CPU 10. That is, CPU 10 only transfers an operation code and an address to memory controller 16. CPU 10 does not send a data transfer to memory controller 16 indicating the value to place in the semaphore. Instead, memory controller 16 automatically sets the semaphore to 0 or a positive value, depending on the instruction it receives.

[0036] FIG. 3 shows an alternative embodiment of the interface between the CPUs 10, 12 and memory controller 16. This embodiment is identical to the data processing system of FIG. 1, except that each CPU 10, 12 has an associated high speed memory cache 310, 312. Each cache 310, 312 holds copies of data found at memory addresses in main memory (RAM 18) recently accessed by its associated CPU 10, 12. This data can include semaphores. Each cache 310, 312 is managed by an associated cache controller 314, 316 which can be within or external to the CPU 10, 12. When a CPU 10, 12 seeks to access a cached memory address, the cache controller 314, 316 retrieves the data from the memory cache 310, 312. Thus, memory controller 16 is not involved in the memory access.

[0037] In the embodiment of FIG. 3, memory controller 16 and the cache controllers 314, 316 work together to ensure coherency between the cached memory 310, 312 and RAM 18. Techniques for maintaining cache coherency are well known in the prior art.

[0038] When CPU 10, for example, desires to lock a semaphore, cache controller 314 determines whether the semaphore is already within cache 310. If it is, cache controller 314 performs the TSL operation on the semaphore in its cache 310. If the semaphore has already been locked by another device, CPU 10 can spin-wait on the local copy of the semaphore, thereby reducing processor bus 14 traffic.

[0039] If the semaphore is not already within cache 310, cache controller 314 sends a TSL instruction transfer on bus 14. Then, memory controller 16 reads the current value of the semaphore, sends that value back to cache controller 314, and then sets the semaphore to a positive value. The cache controller 314 sends the value received on to CPU 10 and stores a positive value in cache 310. For a multitasking processor, this process insures that another process running on CPU 10 will get the correct value of the semaphore when it reads the value from cache 310.

[0040] CPU 10 checks the value received from cache controller 314 to determine whether the semaphore was 0, indicating the resource was free. If the semaphore has already been locked by another device, CPU 10 will spin-wait on its local copy of the semaphore, thereby reducing processor bus 14 traffic.

[0041] When CPU 10 desires to unlock the semaphore, cache controller 314 determines whether the semaphore is still in its cache 310. If so, and if cache controller 314 has an exclusive copy, then it will clear the semaphore in its cache, and no processor bus transfer is required. If the semaphore is no longer in cache 310, then cache controller 314 sends a CI instruction transfer on bus 14. In response, memory controller 16 clears the semaphore. The other cache controller 316 detects the CI instruction on processor bus 14 and checks to see if it has a copy of the semaphore. If so, and the cache line is not modified, then cache controller 316 invalidates its own cached copy or clears its own copy of the semaphore.

[0042] Although the present invention and its advantages have been described in detail, it should be understood that various changes, substitutions and alterations can be made herein without departing from the spirit and scope of the invention as defined by the appended claims.