Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Lock-Free Chaining for Block-Scanning in Multiprocessing Environments

IP.com Disclosure Number: IPCOM000035356D
Original Publication Date: 1989-Jul-01
Included in the Prior Art Database: 2005-Jan-28
Document File: 3 page(s) / 29K

Publishing Venue

IBM

Related People

Cohen, PM: AUTHOR

Abstract

The programming chaining mechanism described in this article is applicable for situations where multiple tasks need to scan a chain of blocks and where there are more scans than deletions. It should also be unlikely for an element to be deleted during any particular scan. The mechanism avoids the need for any kind of locking of scans although a lock is still needed for deletion.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Lock-Free Chaining for Block-Scanning in Multiprocessing Environments

The programming chaining mechanism described in this article is applicable for situations where multiple tasks need to scan a chain of blocks and where there are more scans than deletions. It should also be unlikely for an element to be deleted during any particular scan. The mechanism avoids the need for any kind of locking of scans although a lock is still needed for deletion.

The mechanism also removes the need for synchronization between scanning and deletion operations on chains in a multiprocessing environment resulting in improved processing performance of the operating system especially where lock clashes were frequent. Adding to the chain (Fig. 1)

New elements should be inserted at the head of the chain requiring a programming lock or a Compare and Swap instruction. This will result in the elements being sorted in reverse chronological order. The last elements should be pointed at address 0 or at some other known address so that it can easily be identified. Deleting from the Chain (Fig. 2)

Elements can be deleted from anywhere in the chain, but they must be removed under a lock. The lock may be provided by a single task being responsible for deletions. Alternatively, a lock bit and a "Last in, First Out" delete queue can be provided. If the lock is found to be held by another task, the block to be deleted can simply be pushed onto the delete queue for deletion by the task which is holding the lock. A third option is just to use an ordinary exclusive lock and to assume that lock-clashes only occur sufficiently rarely for the overhead of an operating-system-wait to be negligible.

The deleted blocks should not be freed but kept for future re-use. A programming quick-cell mechanism can be used to manage them. There are two options that can be taken of deletion: 1.The element can be left with its chaining field retaining its current value and status fields indicating that it is free. 2. The chaining pointer can be set to 0 or whatever other value is used to indicated the trailing block that caused scans t...