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

Efficient Serialized Control Block State Detection/Modification in Sparse Composite Arrays

IP.com Disclosure Number: IPCOM000083522D
Original Publication Date: 2005-Mar-01
Included in the Prior Art Database: 2005-Mar-01
Document File: 3 page(s) / 64K

Publishing Venue



A method for efficient detection of control block state changes in sparsely populated arrays of control blocks. By organizing control blocks of a given type into a composite array structure, where state indicators are a separate element of the same array containing the actual control blocks, a system can more efficiently monitor, or scan for, state changes associated with any given control block. Such a method is not sensitive to the presence or absence of control blocks in the array, only to changes in state, which can be sparse within the state indicators element of the array.

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

Page 1 of 3

Efficient Serialized Control Block State Detection /Modification in Sparse Composite Arrays

A method is described for efficient detection of control block state changes in sparsely populated arrays of control blocks. Computer systems commonly use control blocks to describe state associated with system resources. System resources such as disk devices will typically have multiple control blocks associated with them, e.g. time-out timers. An active system would change the state of these control blocks very frequently, which in a multiprocessing environment, can have significant performance implications depending on implementation. Using the case of disk device time-out timers as an example, processing of input/output associated with a given device would change the state of time-out timer control blocks by starting and stopping appropriate timers as necessary. The computer system as a whole, needs to track the total set of time-out timers, identifying which are started and checking for expiry of each. Some operating systems maintain all such watchdog timers in a kernel-owned linked list. At regular intervals, each disk time-out timer control block in the list is examined to determine, if started, whether it has expired. Serialization is required to add/remove timers from the linked list as well as to traverse the list. One difficulty with current implementations is the use of very coarse serialization (the whole list is locked/latched) associated with the list of control blocks. Another difficulty with current implementations is that they don't scale to large numbers of resources associated with these kinds of control blocks. This is amplified by the fact that there may be multiple such control blocks associated with each resource instance (e.g. disk device). Scalability is affected by large numbers of control blocks because the entire list is traversed periodically and each control block is checked in turn to determine if further processing is needed. The method described here organizes control blocks of a given type into a composite array structure containing a "control block state bitmap" and embedded control block instances. Each control block instance self-references it's state bitmap row and uses a mask to identify it's bit position in that row.

sb_row1 sb_row2




CB00: sb_mask = 0x01 addr(sb_row1) other data



sb_mask = 0x02 addr(sb_row1) other data

CB0 7:

sb_ mask = 0x80


Page 2 of 3

addr( sb_r ow1)

other data


sb_mask = 0x01 addr(sb_row2) other data


sb_mask = 0x02 addr(sb_row2) other data


CB1 7:

sb_ mask = 0x80 addr( sb_r ow2)

other data





The advantages of this structural organization of the control blocks and their state bits are:

  Scalability - 1.

Control blocks can be added by linking a newly allocated composite array to


the exiting chain of composite arrays.

Rather than examining every control block to determine potential for further


servicing, rows in the state bitmap that a...