Electrical computers and digital data processing systems: input/ – Access locking
Reexamination Certificate
2000-12-19
2004-01-13
Auve, Glenn A. (Department: 2189)
Electrical computers and digital data processing systems: input/
Access locking
C709S241000
Reexamination Certificate
active
06678772
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
This invention relates to resource locking in computer systems and more specifically to a method of dynamically selecting an optimal lock mode. Both units within a central processing system and system-wide measurements are maintained, and based upon these measures an optimal locking mode is determined.
2. Description of the Prior Art
Multiprocessor systems contain multiple processors (also referred to herein as CPUs) that can execute multiple processes or multiple threads within a single process simultaneously in a manner known as parallel computing. In general, multiprocessor systems execute multiple processes or threads faster than conventional single processor systems, such as personal computer, that execute programs sequentially. The actual performance advantage is a function of a number of factors, including the degree to which parts of a multithreaded process and/or multiple distinct processes can be executed in parallel and the architecture of the particular multiprocessor system. The degree to which processes can be executed in parallel depends, in part, on the extent to which they compete for exclusive access to shared memory resources.
Shared memory multiprocessor systems offer a common physical memory address space that all processors can access. Multiple processes therein, or multiple threads within a process, can communicate through shared variables in memory which allow the processes to read or write to the same memory location in the computer system. Message passing multiprocessor systems, in contrast to shared memory systems, have a separate memory space for each processor. They require processes to communicate through explicit messages to each other.
The architecture of shared memory multiprocessor systems may be classified by how memory is physically organized. In distributed shared memory (DSM) machines, the memory is divided into modules physically placed near one or more processors, typically on a processor node. Although all of the memory modules are globally accessible, a processor can access local memory on its node faster than remote memory on other nodes. Because the memory access time differs based on memory locations, such systems are also called non-uniform memory access (NUMA) machines. In centralized shared memory machines, 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 in conjunction with main memory to reduce execution time.
The use of NUMA architecture to increase performance is not restricted to NUMA machines. A subset of processors in a UMA machine may share a cache. In such an arrangement, even though the memory is equidistant from all processors, data can circulate among the cache-sharing processors faster (i.e., with lower latency) than among the other processors in the machine. Algorithms that enhance the performance of NUMA machines can be applied to any multiprocessor system that has a subset of processors with lower latencies. These include not only the noted NUMA and shared cache machines, but also machines where multiple processors share a set of bus-interface logic as well as machines with interconnects that “fan out” (typically in hierarchical fashion) to the processors.
A significant issue in the design of multiprocessor systems is process synchronization. The degree to which processes can be executed in parallel depends in part on the extent to which they compete for exclusive access to shared memory resources. For example, if two processes A and B are executing in parallel, process B might have to wait for process A to write a value to a buffer before process B can access it. Otherwise, a race condition could occur, where process B might access the buffer while process A was part way through updating the buffer. To avoid conflicts, process synchronization mechanisms are provided to control the order of process execution. These mechanisms include mutual exclusion locks, condition variables, counting semaphores, and reader-writer locks. A mutual exclusion lock allows only the processor holding the lock to execute an associated action. When a processor requests a mutual exclusion lock, it is granted to that processor exclusively. Other processors desiring the lock must wait until the processor with the lock releases it. To address the buffer scenario described above, both processes would request the mutual exclusion lock before executing further. Whichever process first acquires the lock then updates (in the case of process A) or accesses (in the case of process B) the buffer. The other processor must wait until the first processor finishes and releases the lock. In this way, the lock guarantees that process B sees consistent information, even if processors running in parallel execute processes A and B.
For processes to be synchronized, instructions requiring exclusive access can be grouped into a critical section and associated with a lock. When a process is executing instructions in its critical section, a mutual exclusion lock guarantees no other processes are executing the same instructions. This is important where processes are attempting to change data. However, such a lock has the drawback in that it prohibits multiple processes from simultaneously executing instructions that only allow the processes to read data. A reader-writer lock, in contrast, allows multiple reading processes (“readers”) to access simultaneously a shared resource such as a database, while a writing process (“writer”) must have exclusive access to the database before performing any updates for consistency. A practical example of a situation appropriate for a reader-writer lock is a TCP/IP routing structure with many readers and an occasional update of the information. Recent implementations of reader-writer locks are described by Mellor-Crummey and Scott (MCS) in “Scalable Reader-Writer Synchronization for Shared-Memory Multiprocessors,”
Proceedings of the Third ACM SIGPLAN Symposium on Principles and Practices of Parallel Programming
, pages 106-113 (1991) and by Hseih and Weihl in “Scalable Reader-Writer Locks for Parallel Systems,”
Technical Report MIT/LCS/TR
-521 (November 1991).
The basic mechanics and structure of reader-writer locks are well known. In a typical lock, multiple readers may acquire the lock, but only if there are no active writers. Conversely, a writer may acquire the lock only if there are no active readers or another writer. When a reader releases the lock, it takes no action unless it is the last active reader; if so, it grants the lock to the next waiting writer. A centralized reader-writer lock mode is a formative of a reader-writer lock that uses a single data structure to control access to the lock. There are many implementations of this locking primitive. One of the simplest formative uses a set of counters guarded by a simple test-and-set spinlock. The counters count the number of readers holding the lock, the number of readers waiting for access to the lock, the number of writers holding the lock (which must be either one or zero), and the number of writers waiting on the lock. The readers and writers go through a decision process based upon the counter values. Accordingly, this mode is optimal for high update rates wherein read side critical sections are lengthy. The simple test and set lock is a form of an exclusive lock. Other types of exclusive locks include test and set; test and test and set; queued lock; ticket lock; and quad-aware lock.
A drawback of prior reader-writer locks is undesired memory contention, whereby multiple processors modify a single data structure in quick succession, possibly while other processors are spinning on said single data structure. The resulting cache misses can severely degrade performance. The drawback has been partially addressed in more recent locking schemes such as the ones described by Hseih and Weihl. Their static loc
Auve Glenn A.
International Businesss Machines Corporation
Lieberman & Brandsdorfer LLC
Vu Trisha
LandOfFree
Adaptive reader-writer lock does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Adaptive reader-writer lock, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive reader-writer lock will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3245105