Browse Prior Art Database

A Method For Multiple Asynchronous Tasks to Update Slots in a Circular Table Without Locking

IP.com Disclosure Number: IPCOM000202171D
Publication Date: 2010-Dec-07
Document File: 2 page(s) / 25K

Publishing Venue

The IP.com Prior Art Database

Abstract

Disclosed is a method and system for creating a single chronological trace table to record events. The singularity of the table allows the asynchronous processes or tasks to interleave the events so that the chronology is preserved.

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

Page 01 of 2

A Method For Multiple Asynchronous Tasks to Update Slots in a Circular Table

A Method For Multiple Asynchronous Tasks to Update Slots in a Circular TableA Method For Multiple Asynchronous Tasks to Update Slots in a Circular Table

Without Locking

Without LockingWithout Locking

A method to create a single chronological trace table to record events is needed.

The obvious solution is to establish a semaphore or lock which is obtained by the process wishing to write an entry or entries into the table. Once the lock is obtained, the process writes its data into the table, updates, the control data, and releases the lock. The problem is that during the time the process holds the lock all other processes trying to write into the table have to wait. The resulting delay to those processed may impact overall system performance.

The disclosed solution is to use a counter and table size that allow a process to reserve slots in the table in one operation and to separate the writing of the data from the obtaining of the slots. This requires the use of an atomic instruction found on most digital computers commonly called Compare And Swap (CAS).

The method entails giving CAS three arguments: memory

_location, old

_value and

new

_value. Upon execution, CAS compares the contents of memory

_location to

old

_value. If they are equal, then it stores new

_value in memory

_location and returns

TRUE (success). If they are not equal, then it returns FALSE (failure)

without changing

the value of memory

_location. It is important that no other instructions can modify

memory

_location while CAS is being executed.

The pseudo code for using CAS is:

do

old

_value = *memory

_location

new

_value = old

_value + number

_of

_slots

_to

_reserve;

while not CAS(memory

_location, old

_value, new

_value)

When the loop exits, new

_value is the reserved for the process.

One problem with implementing a circular table is handling the logic to wrap the table b...