Electrical computers and digital processing systems: memory – Storage accessing and control – Control technique
Reexamination Certificate
2000-12-15
2003-01-28
Lane, Jack A. (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Control technique
C711S156000
Reexamination Certificate
active
06513100
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to computer programming. More particularly the invention relates to fast referencing of a reference counted item.
BACKGROUND
Reference counting is employed in memory management systems. A reference counted item keeps a count of how many references there are thereto. Items to which there are no references may be reclaimed as available memory. Reference counts are typically begun at a count of one, incremented by one for each reference added, and decremented by one for each reference removed. In such a system, when a reference count falls to zero, the item is no longer required and may be recycled, thus freeing associated memory. Maintaining an accurate reference count is important to memory management. For example, if a reference count indicated that there were no references to an item, and there was an application referring to the reference counted item, and the reference counted item was deleted, then the application could experience an “unresolved pointer” problem, or the application could be reading memory that no longer represented the item associated with the application. By way of further illustration, if a reference count indicated that there were references to an item, but there was no entity referring to that item, then the item would not be reclaimed, and the system with which the reference counted item was associated could suffer from a “memory leak” problem. Thus, it is important to ensure that reference counts are accurately maintained. Therefore, reference counts are frequently protected by locks, which facilitate only one entity accessing a reference count at one time, which mitigates unresolved pointer and memory leak problems. But the locking mechanism creates contention problems, when, for example, two or more entities seek to acquire the lock at the same point in time. Entities other than the entity that acquired the lock must wait, which negatively impacts system performance.
Operating systems, multi-threaded applications, and servers, for example, often maintain data structures with which changeable sub-data is associated. For example, a user of a computer system may have a profile, which includes a set of access rights (e.g. can read files, cannot write files). To access the sub-data, (e.g. the access rights) a conventional reference counting method acquires a lock protecting the pointer to the sub-data, fetches the pointer to the sub-data, increments the reference count associated with the sub-data and then releases the lock. Thus, locking and unlocking operations are employed for each access of the sub-data, which slows down processing of such operating systems, multi-threaded applications and servers, for example, due to the contention problem described above. As the number of concurrent processors accessing the sub-data increases, the performance of the conventional lock, fetch, increment, release lock method declines rapidly as more entities contend for the lock. Such a method is particularly wasteful of system resources (e.g. cpu cycles) when the sub-data is frequently read but rarely changed.
Thus, a system and method for fast referencing a reference counted item where the performance of the method does not decline so rapidly is required.
SUMMARY
The following presents a simplified summary of the invention in order to provide a basic understanding of some aspects of the invention. This summary is not an extensive overview of the invention. It is intended to neither identify key or critical elements of the invention nor delineate the scope of the invention. Its sole purpose is to present some concepts of the invention in a simplified form as a prelude to the more detailed description that is presented later.
The present invention provides a system and method for fast referencing a reference counted item to facilitate performance of multi-threaded applications and/or systems employing concurrent processors. In the present invention, a fast referencing item establishes a reference count in the reference counted item to a value greater than one, establishes a pointer to the reference counted item and stores a local value associated with the reference count, known as a fast reference count (FRC). The initial FRC value is greater than the number of referencing items referencing the reference counted item.
By establishing the number of references in the reference counted item at more than one, the referencing item can be viewed as having acquired more than one reference. The “extra” references are then available to subsequent items seeking a reference to the reference counted item, and under certain conditions, such subsequent acquiring items will not be required to acquire a lock, change the reference count and release the lock. Rather, the subsequent acquiring items may examine the number of references available in the fast referencing item and acquire (e.g. “steal/borrow”) one or more of the “extra” references. When acquiring a reference using this method, an atomic operation (e.g. InterlockedCompareExchange( )) is employed to change the FRC in the fast referencing item to facilitate maintaining an accurate count of the references to the reference counted item. A fast referencing item that acquires more than one reference, can itself be examined for available references and can have one or more of its available references acquired.
The FRC may be stored in a variable, or in one or more bits in the pointer. Such bits may be available if, for example, the reference counted item is located in a memory area where items are aligned on eight byte boundaries (freeing, for example, the low order three bits of the pointer), or if other bits in the pointer are available. The bits employed to store the FRC may be contiguous in the pointer, or they may be distributed throughout the pointer.
The system and method thus facilitates obtaining references to a reference counted item without employing a locking algorithm wherein a lock is acquired, a reference is acquired and the lock is released. Thus, performance degradation due to contention problems that arise when multiple entities are seeking to acquire the lock to the reference counted item is mitigated.
REFERENCES:
Richard Anstee, et al.; “Low Discrepancy Allocation of Two-Dimensional Data”, Foundations of Information and Knowledge Systems. First International Symposium, FoLKS 2000., vol. 1762, 2000, p. 1-12.
Onodera, T., et al.; “A Study of Locking Objects with Bimodal Fields”, SIGPLAN Notices, vol. 34, No. 10, Oct. 1999, p. 223-237.
Alperns, B., et al.; “The Jalapeno Virtual Machine”, IBM Systems Journal, vol. 39, No. 1,2000, p. 211-236.
Amin & Turocy LLP
Lane Jack A.
Microsoft Corporation
LandOfFree
System and method for fast referencing a reference counted item does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for fast referencing a reference counted item, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for fast referencing a reference counted item will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3044783