Implementing distributed reference counters in a multiprocessor computer ensures a fair allocation of memory to each of the CPUs and quads in the system. The distributed reference counter tracks the limits of the value in each CPU, each quad, a global value and the maximum cache count allowed while mitigating a cache overflow error. The cache count is dynamically varied based upon a desired level of cache value in a node and a CPU. By modifying the fields of the data structure of the distributed reference counter to accept 64 bit integers, both the cache and target values of the data structure may be combined into one 64 bit integer. The upper 32 bits represent the cache value and the lower 32 bits represent the target value. This modified data structure now allows for both the target and cache values to be atomically manipulated as a single quantity, thereby reducing the possibility of a cache overflow situation.
We present a methodology for transforming concurrent data structure implementations that depend on garbage collection to equivalent implementations that do not. Assuming the existence of garbage collection makes it easier to design implementations of concurrent data structures, particularly because it eliminates the well-known ABA problem. However, this assumption limits their applicability. Our results demonstrate that, for a significant class of data structures, designers can first tackle the easier problem of an implementation that does depend on garbage collection, and then apply our methodology to achieve a garbage-collection-independent implementation. Our methodology is based on the well-known reference counting technique, and employs the double compare-and-swap operation.
A technique for realtime-safe detection of a grace period for deferring the destruction of a shared data element until pre-existing references to the data element have been removed. A per-processor read/write lock is established for each of one or more processors. When reading a shared data element at a processor, the processor's read/write lock is acquired for reading, the shared data element is referenced, and the read/write lock that was acquired for reading is released. When starting a new grace period, all of the read/write locks are acquired for writing, a new grace period is started, and all of the read/write locks are released.
A technique for realtime-safe detection of a grace period for deferring the destruction of a shared data element until pre-existing references to the data element have been removed. A pair of counters is established for each of one or more processors. A global counter selector determines which counter of each per-processor counter pair is a current counter. When reading a shared data element at a processor, the processor's current counter is incremented. Following counter incrementation, the processor's counter pair is tested for reversal to ensure that the incremented counter is still the current counter. If a counter reversal has occurred, such that the incremented counter is no longer current, the processor's other counter is incremented. Following referencing of the shared data element, any counter that remains incremented is decremented. Following an update to the shared data element wherein a pre-update version of the element is maintained, the global counter selector is switched to establish a new current counter of each per-processor counter pair. The non-current counter of each per-processor counter pair is tested for zero. The shared data element's pre-update version is destroyed upon the non-current counter of each per-processor counter pair being zero.
