Electrical computers and digital processing systems: memory – Storage accessing and control – Shared memory area
Reexamination Certificate
2002-05-21
2004-08-17
Sparks, Donald (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Shared memory area
C711S151000, C710S200000, C710S220000, C710S240000, C710S241000, C710S244000, C707S793000, C707S793000
Reexamination Certificate
active
06779090
ABSTRACT:
BACKGROUND OF INVENTION
This invention relates generally to computer systems that have shared memory, and more particularly to locks for such shared memory.
There are many different types of multi-processor computer systems. A symmetric multi-processor (SMP) system includes a number of processors that share a common memory. SMP systems provide scalability. As needs dictate, additional processors can be added. SMP systems usually range from two to thirty-two or more processors. One processor generally boots the system and loads the SMP operating system, which brings the other processors online. Without partitioning, there is only one instance of the operating system and one coherent shared memory space. The operating system uses the processors as a pool of processing resources, all executing simultaneously, where each processor either processes data or is in an idle loop waiting to perform a task. SMP systems increase in speed whenever processes can be overlapped.
A massively parallel processor (MPP) system can use thousands or more processors. MPP systems use a different programming paradigm than the more common SMP systems. In an MPP system, each processor contains its own memory and copy of the operating system and application. Each subsystem communicates with the others through a high-speed interconnect. To use an MPP system effectively, an information-processing problem should be breakable into pieces that can be solved simultaneously. For example, in scientific environments, certain simulations and mathematical problems can be split apart and each part processed at the same time.
A non-uniform memory access (NUMA) system is a multi-processing system in which memory is separated into distinct banks. NUMA systems are similar to SMP systems. In SMP systems, however, all processors access a common memory at the same speed. By comparison, in a NUMA system, memory on the same processor board, or in the same building block, as the processor is accessed faster than memory on other processor boards, or in other building blocks. That is, local memory is accessed faster than distant shared memory. NUMA systems generally scale better to higher numbers of processors than SMP systems. The term building block is used herein in a general manner, and encompasses a separable grouping of processor(s), other hardware, such as memory, and software that can communicate with other building blocks. As used herein, it is synonymous with the term node, but not with the term partition, in that the processors of a node may be partitioned over two or more partitions.
Nearly any type of multi-processor computer system has at least some memory that is shared among the separate processors. Where the shared memory is remote to a given processor, because, for instance, it resides on a different building block than the processor, the memory may also be locally cached to improve performance. In any case, locking should be used to enable orderly access to and modification of the shared data, as may be stored in memory sections, such as memory lines. When a processor requests a lock on a memory section, if no other processor is using the memory section, it is granted to the requesting processor exclusively. Other processors desiring the lock must wait until the processor with the lock releases it. A common arrangement is to require possession of a particular lock before allowing access to a given section of memory, where the processor releases the lock when it is finished with the memory section.
One type of lock is the spin lock. A spin lock can control access to a memory section. A typical spin lock implementation has two phases. In a spin phase, the waiting computational agents, or threads, spin on a cached copy of a single global lock variable. There is usually a one-to-one correspondence between running computational agents, or threads, and processors. However, one computational agent may alternatively encompass two, three or more processors as well. A computational agent is thus used herein in a general sense, and can encompass one or more processors, computer program modules, threads, and so on. In a compete phase, the waiting computational agents all try to atomically modify the lock variable from the available to the held state. The agent that succeeds has control of the lock, and the others go back to the spin phase. The transition from the spin phase to the compete phase is usually initiated when the lock holder releases the lock by marking the lock variable as available.
Spin locks have two primary advantages. They usually require only a few instructions to implement, and they are easily designed to be interruptible. The main disadvantage of spin locks, however, is that they do not scale well. The compete phase in particular can cause significant contention on the system buses when a large number of computational simultaneously attempt to acquire the lock. Spin locks are thus suitable only for lightly contended locks. Additionally, since the locks are not necessarily granted in a first-in, first-out (FIFO) order, spin locks are typically not fair. One or more of the computational agents may ultimately find themselves starved. Such agents, that is, may have to wait a prolonged period of time to obtain access to a lock, even while other agents repeatedly obtain access to the lock. For these and other reasons, therefore, there is a need for the present invention.
SUMMARY OF INVENTION
The invention relates to a spin lock for shared memory. A method of the invention first attempts to set a lock flag for a lock on a memory section. If the method successfully sets the lock flag, the lock on the memory section is held so that the memory section may be processed. Upon being ready to release the lock on the memory section, and in response to determining that one or more units are spinning for the lock on the memory section, the method first selects one of these spinning units. The method then resets a spin flag for the selected unit. If no units are spinning for the lock, however, the method resets the lock flag for the lock.
A system of the invention includes a number of computational agents, a memory shared by the computational agents, and a number of locks. The memory has a number of memory sections. Each lock relates to a corresponding memory section and includes a lock flag and a number of spin flags. The lock flag indicates whether one of the computational agents has locked the corresponding memory section. The spin flags correspond to a number of units to which the agents are assigned. Each spin flag indicates whether at least one of the agents assigned to the unit corresponding to the flag is waiting for the lock.
An article of manufacture of the invention includes a computer-readable medium and means in the medium. The means in the medium is for releasing a lock on a memory section by selecting one of one or more units spinning for the lock, and for releasing a spin flag for the selected unit. Other features and advantages of the invention will become apparent from the following detailed description of the presently preferred embodiment of the invention, taken in conjunction with the accompanying drawings.
REFERENCES:
patent: 5832484 (1998-11-01), Sankaran et al.
patent: 6473819 (2002-10-01), Jackson et al.
patent: 6480918 (2002-11-01), McKenney et al.
patent: 6546443 (2003-04-01), Kakivaya et al.
U.S. patent application Ser. No. 09/883,417, Browning et al., filed Apr. 12, 2001.
U.S. patent application Ser. No. 09/753,062, Rajamony et al., filed Dec. 28, 2000.
Irwin, III William L.
McKenney Paul E.
Sivasubramanian Swaminathan
Stultz John G.
Law Offices of Michael Dryja
Sparks Donald
Truong Bao Q
LandOfFree
Spinlock for 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 Spinlock for shared memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spinlock for shared memory will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3305031