Browse Prior Art Database

Lock-less Concurrent Dual Chaining of Control Structures

IP.com Disclosure Number: IPCOM000126443D
Original Publication Date: 2005-Jul-18
Included in the Prior Art Database: 2005-Jul-18
Document File: 1 page(s) / 40K

Publishing Venue

IBM

Abstract

The design required being able to chain a single element on two independent linked-list structures, however there was an additional requirement that NO lock be obtained to perform the linked list chain management. The solution involves creating new control structures that provide the equivalent function to the previous two linked-list implementation, that could be updated exclusively using zSeries provided atomic instructions, thereby avoiding the need for ANY lock to be obtained. The result of this restructuring significantly reduces the overall system overhead incurred by frequent dual chain updating.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 54% of the total text.

Page 1 of 1

Lock-less Concurrent Dual Chaining of Control Structures

The solution involves switching from a model where a single control structure was placed on two separate linked lists (i.e. two separate chain pointers existed within the control structure, one linking it to one anchor, and the other linking it to a different anchor), to a model where the control structure is pointed to by two anchoring arrays, with each array owned by a different interested party. The following steps are required to add a new control structure to both interested parties: 1) Increment a shared use count in the parent interested party control blocks to protect the parent anchor blocks from being deleted (this includes the anchoring array structures described above). Since the new control structure needs to be added to two interested parties, this must be performed twice, once for each anchor point. 2) Maintain a list of free array entries for each interested party. This free list processing is maintained using only atomic update instructions. Specifically, the free array entries themselves are maintained as a linked list that is updated with a CDS instruction as a push down stack. One array free array entry is obtained from both interested parties. 3) Update the control structure to contain the "pointers" to each of the obtained array entries, so that this control structure knows which array entries are to be freed when the control structure is to be removed from the interested party anchor...