Electrical computers and digital data processing systems: input/ – Access locking
Reexamination Certificate
1998-12-22
2002-11-12
Banankhah, Majid A. (Department: 2151)
Electrical computers and digital data processing systems: input/
Access locking
C709S241000, C710S240000, C710S241000, C710S244000, C710S260000, C710S263000
Reexamination Certificate
active
06480918
ABSTRACT:
FIELD OF THE INVENTION
This invention relates generally to multiprocessor computers that are comprised of a number of separate but interconnected processor nodes. More particularly, this invention relates to a method for efficiently granting a lock to requesting processors while maintaining fairness among the processor nodes.
BACKGROUND OF THE INVENTION
Multiprocessor computers by definition contain multiple processors that can execute multiple parts of a computer program or multiple distinct programs simultaneously, in a manner known as parallel computing. In general, multiprocessor computers execute multithreaded programs or multiple concurrent single-threaded programs faster than conventional single processor computers, such as personal computers (PCs), that must execute programs sequentially. The actual performance advantage is a function of a number of factors, including the degree to which parts of a multithreaded program and/or multiple distinct programs can be executed in parallel and the architecture of the particular multiprocessor computer at hand.
Multiprocessor computers may be classified by how they share information among the processors. Shared memory multiprocessor computers offer a common physical memory address space that all processors can access. Multiple processes or multiple threads within the same process can communicate through shared variables in memory that allow them to read or write to the same memory location in the computer. Message passing multiprocessor computers, in contrast, have a separate memory space for each processor, requiring processes in such a system to communicate through explicit messages to each other.
Shared memory multiprocessor computers may further be classified by how the memory is physically organized. In distributed shared memory (DSM) machines, the memory is divided into modules physically placed near each processor. Although all of the memory modules are globally accessible, a processor can access memory placed nearby faster than memory placed remotely. Because the memory access time differs based on memory location, distributed shared memory systems are also called non-uniform memory access (NUMA) machines. In centralized shared memory computers, on the other hand, the memory is physically in one location. Centralized shared memory computers are called uniform memory access (UMA) machines because the memory is equidistant in time from each of the processors. Both forms of memory organization typically use high-speed cache memory in conjunction with main memory to reduce execution time. An alternative form of memory organization in an UMA machine involves groups of processors sharing a cache. In such an arrangement, even though the memory is equidistant from all processors, data can circulate among the processors sharing a cache with lower latency than among processors not sharing a cache.
Multiprocessor computers with distributed shared memory are organized into nodes with one or more processors per node. Also included in the node are local memory for the processors, a remote cache for caching data obtained from memory in other nodes, and logic for linking the node with other nodes in the computer. A processor in a node communicates directly with the local memory and communicates indirectly with memory on other nodes through the node's remote cache.
For example, if the desired data is in local memory, a processor obtains the data directly from a block (or line) of local memory. But if the desired data is stored in memory in another node, the processor must access its remote cache to obtain the data. Further information on multiprocessor computer systems in general and NUMA machines in particular can be found in a number of works including
Computer Architecture: A Quantitative Approach
(2
nd
Ed. 1996), by D. Patterson and J. Hennessy, which is incorporated herein by reference.
Although the processors can often execute in parallel, it is sometimes desirable to restrict execution of certain tasks to a single processor. For example, two processors might execute program instructions to add one to a counter. Specifically, the instructions could be the following:
1. Read the counter into a register.
2. Add one to the register.
3. Write the register to the counter.
If two processors were to execute these instructions in parallel, the first processor might read the counter (e.g., “5”) and add one to it (resulting in “6”). Since the second processor is executing in parallel with the first processor, the second processor might also read the counter (still “5”) and add one to it (resulting in “6”). One of the processors would then write its register (containing a “6”) to the counter, and the other processor would do the same. Although two processors have executed instructions to add one to the counter, the counter is only one greater than its original value.
To avoid such an undesirable result, some computer systems provide a mechanism called a lock for protecting sections of programs. When a processor requests the lock, it is granted to that 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 designated section of a program; the processor then releases the lock when it is finished with the section. The section is thereby protected by the lock.
Accordingly, when a processor has acquired the lock, the processor is guaranteed that it is the sole processor executing the protected code.
To solve the add-one-to-a-counter scenario described above, both the first and the second processors would request the lock. Whichever processor first acquires the lock would then read the counter, increment the register, and write to the counter before releasing the lock. The remaining processor would have to wait until the first processor finishes, acquire the lock, perform its operations on the counter, and release the lock. In this way, the lock guarantees the counter is incremented twice if the instructions are run twice, even if processors running in parallel execute them.
Program instructions requiring exclusive execution are grouped into a section of program code called a critical section or critical region. Typically, the operating system handles the details of granting and releasing the lock associated with the critical section, but critical sections can also be implemented using user-level functions.
Accordingly, when code in a critical section is executing, the lock guarantees no other processors are executing the same code. To prevent the add-one-to-a-counter problem. in the above example, the program instructions for manipulating the counter could be grouped into a critical section.
Locks are useful for solving a wide variety of other problems such as restricting concurrent data structure access to a single processor to avoid data inconsistency. For more information on locks and related topics, see “Process Synchronization and Interprocess Communication” in
The Computer Science and Engineering Handbook
(1996) by A. Tucker, CRC Press, pages 1725-1746, which is incorporated herein by reference.
A typical scheme for managing lock requests is to use a first-come-first-served queued lock design. Under this design, the operating system grants a lock to the first requesting processor, queues subsequent requests by other processors until the first processor finishes with the lock, and grants the lock to processors waiting in the queue in order. However, a first-come-first-served scheme has certain drawbacks relating to performance.
For example, if the architecture of the multiprocessor system groups processors into nodes, communication latencies between processors in two different nodes are typically greater than that for processors in the same node. Accordingly, it is typically more expensive in terms of processing resources to move the lock from a processor in one node to a processor in another node. However, if a multiprocessor system implements a first-come-first-served queued lo
Closson Kevin A.
Malige Raghupathi
McKenney Paul E.
Banankhah Majid A.
Klarquist Sparkman Campbell & Leigh & Whinston, LLP
LandOfFree
Lingering locks with fairness control for multi-node... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Lingering locks with fairness control for multi-node..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lingering locks with fairness control for multi-node... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2980510