New Locking Strategy
Original Publication Date: 1996-Dec-01
Included in the Prior Art Database: 2005-Apr-06
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.
New Locking Strategy
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.
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.
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
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.
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
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...