[concurrency-interest] Custom Lock

David Holmes dholmes@dltech.com.au
Thu, 8 Jan 2004 12:09:16 +1000


>     I felt pressured, so I'm releasing a prototype of a
> Lock that does priority invertion.

You mean a lock that tries to reduce, or bound priority inversion - in
this case by trying to use form of priority inheritance. The classic
algorithms for Priority Inversion Avoidance are Priority Inheritance
Protocol (PIP) and Priority Ceiling Protocol (PCP), though in practice
system tends to use PIP and a simpler form of PCP known as Priority
Ceiling Emulation Protocol.

> Please consider, only, the algoritm and what I had to do to
> get to it.

The simple algorithm for PIP assumes an environment where priorities
can not be changed by the application. It also assumes that only one
lock at a time may be held. In general Java and in the Real-Time
Specification for Java (RTSJ) neither of these assumptions hold and an
implementation of PIP is much more complex that what you outline. You
need a concept of base and active priority and you need full control
over all priority changes so that you can propagate inherited
priorities when needed, and restore priorities correctly when
releasing a lock.

Priority ceiling emulation is a bit simpler as transitivity has to be
factored in when you work out what the ceiling priorities are for each
lock, but you still need full control over priority changes.

> Why my needs are not meat: (although I'm not going to use
> the code above)
>     - There are pleanty compareAndSets or incAnd.. or decAnd, but no
> ifgreaterSet, ifsmallerSet and so on

Typically you read the current value atomically, perform the some
application logic based on the current value and finally set a new
value if the original hasn't changed ie.

  int curr = val.get();
  if (curr < threshHold)
     if (val.compareset(curr, f(curr))) ...
     else ...
     if (val.compareandset(curr, y(curr))) ...
     else ...

>     - AbstractQueuedSynchronizer doesn't hold its owner
> (and I did a terible job trying)

See ReentrantLock for an owned lock using AQS.

>     - Thread has no atomic operation with its Priority,

No it doesn't. setPriority is not even atomic with respect to
getPriority. You would need to control the thread types used and
redefine special purpose methods to manipulate priority the way you
want - but yu can't override the existing final methods. But even then
the VM can ignore your careful priority manipulations.

>     - no control over the Queu, please insert a non final
> class for the Queu node, so people can add behavior to it

As Doug mentioned AQS provides FIFO queuing. Trying to abstract out
the queueing from AQS is not practical because of its specialized
nature, hence you'd either have to use multiple AQS's as Doug
suggested or use the existing AQS as a model for building a
priority-queue version

Priority inversion avoidance in a JVM is not possible without some VM
support and characteristics. In particular without strict priority
preemptive scheduling, priority inversion avoidance techniques are a
waste of time.

For the record I have implemented PIP for an RTSJ implementation based
on user-level threads.

David Holmes