Electrical computers and digital processing systems: multicomput – Computer-to-computer session/connection establishing – Network resources access controlling
Reexamination Certificate
1998-08-28
2001-12-11
Meky, Moustafa M. (Department: 2153)
Electrical computers and digital processing systems: multicomput
Computer-to-computer session/connection establishing
Network resources access controlling
C709S241000
Reexamination Certificate
active
06330612
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to a method and apparatus for serializing access to a shared resource in an information handling system and, more particularly, to a method and apparatus for serializing access by a plurality of entities such as processors, processes or users to such a shared resource.
2. Description of the Related Art
In information handling systems, processors, applications or other entities frequently must access shared resources (files, memory regions and the like) that are potentially being simultaneously accessed by another entity. Such systems conventionally use lock managers to serialize access to a resource, ensuring that only a single entity accesses a resource at any one time. Such lock managers typically use a resource serialization variable (RSV) that is atomically tested and set to acquire a lock on the resource for the requester. Various instructions are available for implementing such atomic operations, such as Test and Set (TS), Compare and Swap (CS) and Compare Double and Swap (CDS) in an IBM S/390® environment.
In a lock manager that allows queuing of lock requests, an efficient mechanism is needed to ensure that queued waiters are given fair access to the lock. If a list of waiters is kept in the order in which they requested the lock, then the lock manager can do one of several things. First, it can preallocate storage for a maximum number of waiters. However, in systems with low contention, this wastes large amounts of storage. Second, a lock manager can allocate storage for each waiter as each request arrives. This has a tendency to fragment storage, though, reducing the effectiveness of the lock manager. What is desired, therefore, is a lock manager that conserves storage, as well as one that does not fragment storage.
BRIEF SUMMARY OF THE INVENTION
In general, the present invention contemplates a method and apparatus for serializing access by a plurality of entities to a shared resource in an information handling system in which there is defined a circular waiter list containing a plurality of entries, each of which corresponds to one of the entities and indicates whether the corresponding entity is a waiter for the resource, as well as a next waiter indicator (NWI) identifying one of the entities as a next waiter for the resource. Upon release of the resource by an entity previously accessing the resource, the lock manager grants access to the entity identified as a next waiter by the next waiter indicator and determines a new next waiter by scanning the entries in the waiter list beginning with the entry following that for the entity granted access to the resource.
The use of a next waiter indicator allows the lock to be granted in a fair manner while avoiding both storage fragmentation and wasted storage. The present invention, which uses the next waiter indicator, exhibits several desirable properties. In a system with low contention (i.e., never more than two waiters), the lock is always granted to waiters in the order in which the lock requests were received, since there is only one waiter other than the next waiter. In all cases, since a new next waiter is determined by scanning the entries in the waiter list beginning with the entry following that for the previous next waiter, no waiter can obtain the lock twice while other waiters have yet to receive the lock for a first time; this ensures fair access.
Further, since storage need be allocated only for the next waiter indicator and waiter list, storage utilization is minimized. Since these structures are fixed in size, fragmentation is avoided.
REFERENCES:
patent: 4965719 (1990-10-01), Shoens et al.
patent: 5734909 (1998-03-01), Bennett
patent: 5805900 (1998-09-01), Fagen et al.
patent: 5875342 (1999-02-01), Temple
patent: 5937199 (1999-08-01), Temple
patent: 6105049 (2000-08-01), Govindaraju et al.
patent: 6105050 (2000-08-01), Govindaraju et al.
patent: 6112222 (2000-08-01), Govindaraju et al.
patent: 6178421 (2001-01-01), Dahlen et al.
patent: 6185562 (2001-02-01), Dahlen et al.
Boonie Mark A.
Sutton Peter G.
Wilkinson Wendell W.
Yeh Phil Chi-Chung
International Business Machines - Corporation
Kinnaman, Jr. William A.
Meky Moustafa M.
LandOfFree
Method and apparatus for serializing access to a shared... 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 serializing access to a shared..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for serializing access to a shared... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2571274