A Method For Multiple Asynchronous Tasks to Update Slots in a Circular Table Without Locking
Publication Date: 2010-Dec-07
The IP.com Prior Art Database
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.
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 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
_value. Upon execution, CAS compares the contents of memory
_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)
the value of memory
_location. It is important that no other instructions can modify
_location while CAS is being executed.
The pseudo code for using CAS is:
_value = *memory
_value = old
_value + number
while not CAS(memory
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...