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

New Locking Strategy

IP.com Disclosure Number: IPCOM000124021D
Original Publication Date: 1996-Dec-01
Included in the Prior Art Database: 2005-Apr-06
Document File: 2 page(s) / 90K

Publishing Venue

IBM

Related People

Browning, LM: AUTHOR

Abstract

Disclosed is a general locking technique that can be easily extended to a large number of critical sections. This new strategy has the potential for greatly increasing the scalability of an operating system in a simple and well understood manner. It has increased the performance of AIX* by roughly 30% when applied to a single critical subsystem.

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

New Locking Strategy

      Disclosed is a general locking technique that can be easily
extended to a large number of critical sections.  This new strategy
has the potential for greatly increasing the scalability of an
operating system in a simple and well understood manner.  It has
increased the performance of AIX* by roughly 30% when applied to a
single critical subsystem.

      This strategy is predicated on the fact that disabled critical
sections as a rule have to run through to completion on a single
processor.  They cannot be rescheduled in mid-stream on another
processor.  This seems to be the model used by most hardware vendors,
since the alternative would stress what is historically one of the
weaker links in such systems - random access memory.  Processors are
generally much faster than system memory.

      A corollary to this assumption is that it is impossible to get
a wrong or stale value from memory within a disabled critical
section, since all the data references within the critical section
are in a local memory cache.  In other words, locks are only needed
to protect the data from concurrent references made on another
processor.

      This invention describes a technique for splitting a single
disabled critical section based on the synchronous and asynchronous
nature of the data references within the critical section.  It is
particularly well adapted for state machines.

      In AIX, this strategy has been applied to control the thread
and process states.  It can be easily seen in the thread sleep and
wakeup primitives.  When a thread goes to sleep, it places itself on
an event list, changes its state to sleeping, and then calls the
dispatcher to choose another thread to run.  This is the synchronous
part of the algorithm, since the thread is changing its own context.
The asynchronous part is associated with the wakeup, since this is
usually driven by external events such as hardware interrupts.

      Therefore, lock A can be defined to protect adding the current
thread to the sleep list and changing its state to sleeping, and lock
B to protect the global data structures referenced in the dispatcher.
The wake-up operation would then have to take both locks A & B to
guarantee correctness.

      The motivation for this design is that it isolates the
dispatcher as a separate critical section and reduces the scope of
the lock that protects the dispatcher.  The number of cycles that the
lock is held is reduced because lock B is not held while the thread
is going to sleep.  The disadvantage is that locks A & B are both
required to serialize th...