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

Minimizing Locking to Access Global Shared Data

IP.com Disclosure Number: IPCOM000114997D
Original Publication Date: 1995-Feb-01
Included in the Prior Art Database: 2005-Mar-30
Document File: 4 page(s) / 169K

Publishing Venue

IBM

Related People

Narayanaswami, C: AUTHOR

Abstract

Imagine a parallel environment supporting threads or cooperating processes (3). Each process (or thread (2)) may need to maintain information specific to the process which is accessible to any function invoked in the context of that process. Such situations occur commonly while implementing parallel libraries. One such example is the need for storing and retrieving thread specific data in the POSIX Pthreads (5). Another example that occurs in graphics libraries is when each thread requires a graphics context specific to that thread and is accessible from each rendering function invoked within that thread.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 35% of the total text.

Minimizing Locking to Access Global Shared Data

      Imagine a parallel environment supporting threads or
cooperating processes (3).  Each process (or thread (2)) may need to
maintain information specific to the process which is accessible to
any function invoked in the context of that process.  Such situations
occur commonly while implementing parallel libraries.  One such
example is the need for storing and retrieving thread specific data
in the POSIX Pthreads (5).  Another example that occurs in graphics
libraries is when each thread requires a graphics context specific to
that thread and is accessible from each rendering function invoked
within that thread.

      In such situations each parallel process (or thread) stores
data relevant to its process in a common area shared among all the
threads.  Usually a hash table (1) is used for this purpose because
fast access to the data is desired.  The Figure shows an example.  In
order to ensure data consistency, accesses to such data structures
are performed in critical sections, i.e., inside a section guarded by
a lock or a semaphore, e.g., with the lock() and unlock() functions.
For example no one is allowed to read the data when someone else is
modifying the data.  Otherwise the person reading the data may get a
wrong value.  So depending on the granularity of locking, either the
hash table itself may be locked, or buckets may be locked or
individual elements in the bucket may be locked.  Any form of locking
degrades performance since locking and unlocking are often very
expensive.  Costly synchronization may be necessary among several
processors (4).  Moreover, locks require additional space and have
other requirements such as being on cache line boundaries, etc.,
complicating data structures and leading to additional disadvantages.
This disclosure minimizes the above need for locking and unlocking a
special class of accesses.

      Some terms are defined which are required to explain the
algorithm.  For the purpose of our discussion the terms thread and
process may be used interchangeably.

      Each thread is identified by a unique id.  The id is used to
index into the hash table to access data that is specific to the
thread.  Several threads may index into the same bucket in the hash
table.

      Suppose there is a set of functions W in the parallel library
that have write access to thread specific information.  Let R be the
set of functions that have only read access to thread specific
information.  Finally, the frequency with which functions from R
occur is much higher than the frequency with which functions from W
occur.  It is often true the number of elements in W is much less
than that in R.

      Each thread stores its specific data (or a pointer to a block
of memory where such data is stored) in an element in the hash table.
As shown in the Figure, each element contains the id of the thread
that owns the element, a flag to indicate...