Overview  Package   Class  Use  Tree  Serialized  Deprecated  Index  Help 
 PREV CLASS   NEXT CLASS FRAMES    NO FRAMES    
SUMMARY: NESTED | FIELD | CONSTR | METHOD DETAIL: FIELD | CONSTR | METHOD

org.jikesrvm.scheduler
Class Lock

java.lang.Object
  extended by org.jikesrvm.scheduler.Lock
All Implemented Interfaces:
Constants, HeapLayoutConstants, ThinLockConstants, TIBLayoutConstants, SizeConstants
public final class Lock
extends Object
implements Constants

Lock provides RVM support for monitors and Java level synchronization.

This class may be decomposed into four sections:

  1. support for synchronization methods of java.lang.Object,
  2. heavy weight locking mechanism,
  3. management of heavy weight locks, and
  4. debugging and performance tuning support.

Requirement 1: It must be possible to lock an object when allocations are not allowed.

Requirement 2: After a lock has been obtained, the code of this class must return without allowing a thread switch. (The exception handler of the baseline compiler assumes that until lock() returns the lock has not been obtained.)

Section 1: support for Object.notify(), Object.notifyAll(), and Object.wait(). When these methods are called, the indicated object must be locked by the current thread.

Section 2: has two sections. Section 2a: locks (and unlocking) objects with heavy-weight locks associated with them. Section 2b: associates (and disassociates) heavy-weight locks with objects.

Section 3: Allocates (and frees) heavy weight locks consistent with Requirement 1.

Section 4: debugging and performance tuning stuff.

The following performance tuning issues have not yet been addressed adaquately:

  1. What to do if the attempt to lock an object fails? There are three choices: try again (busy-wait), yield and then try again, inflate the lock and yield to the heavy-weight lock's entering queue. Currently, yield n times, then inflate. (This seemed to be best for the portBOB benchmark on a 12-way AIX SMP in the Fall of '99.)
  2. When should a heavy-weight lock be deflated? Currently, deflation happens when the lock is unlocked with nothing on either of its queues. Probably better, would be to periodically (what period?) examine heavy-weight locks and deflate any that havn't been held for a while (how long?).
  3. How many heavy-weight locks are needed? and how should they be managed? Currently, each processor maintains a pool of free locks. When a lock is inflated by a processor it is taken from this pool and when a lock is deflated by a processor it gets added to the processors pool. Since inflation can happen on one processor and deflation on another, this can create an imbalance. It might be worth investigating a scheme for balancing these local pools.
  4. Is there any advantage to using the SpinLock.tryLock() method?
Once these questions, and the issue of using MCS locking in SpinLock, have been investigated, then a larger performance issue comes into view. A number of different light-weight locking schemes have been proposed over the years (see last several OOPSLA's). It should be possible to implement each of them in RVM and compare their performance.

See Also:
Object, ThinLock, SpinLock

Nested Class Summary
private static class Lock.AppRunStartMonitor
          Initialize counts in preparation for gathering statistics
private static class Lock.ExitMonitor
          Report statistics at the end of execution.
 
Field Summary
protected  boolean active
          Is this lock currently being used?
private static int chunksAllocated
          The number of chunks in the spine that have been physically allocated
static int deflations
          Number of deflations
(package private)  ThreadQueue entering
          Queue for entering the lock, guarded by mutex.
private static Lock globalFreeLock
          A global lock free list head
private static int globalFreeLocks
          the number of locks held on the global free list.
private static int globalLocksAllocated
          the total number of allocation operations.
private static int globalLocksFreed
          the total number of free operations.
protected  int index
          This lock's index in the lock table
protected static int INITIAL_CHUNKS
          The number of chunks to allocate on startup
protected static int LOCK_CHUNK_MASK
          The mask used to get the chunk-level index
protected static int LOCK_CHUNK_SIZE
          The size of each chunk in the spine
protected static int LOCK_SPINE_SIZE
          The (fixed) number of entries in the lock table spine
private static SpinLock lockAllocationMutex
          Used during allocation of locks within the table.
protected  Object lockedObject
          The object being locked (if any).
static int lockOperations
          Number of lock operations
private static Lock[][] locks
          The table of locks.
protected static int LOG_LOCK_CHUNK_SIZE
          The log size of each chunk in the spine
protected static int MAX_LOCKS
          The maximum possible number of locks
 SpinLock mutex
          A spin lock to handle contention for the data structures of this lock.
private  Lock nextFreeLock
          The next free lock on the free lock list
private static int nextLockIndex
          The number of locks allocated (these may either be in use, on a global freelist, or on a thread's freelist.
protected  int ownerId
          The id of the thread that owns this lock (if any).
protected  int recursionCount
          The number of times the owning thread (if any) has acquired this lock.
static boolean STATS
          Control the gathering of statistics
private static boolean tentativeMicrolocking
          Should we give up or persist in the attempt to get a heavy-weight lock, if its mutex microlock is held by another procesor.
protected static boolean trace
          do debug tracing?
static int unlockOperations
          Number of unlock operations
(package private)  ThreadQueue waiting
          Queue for waiting on a notify, guarded by mutex as well.
 
Fields inherited from interface org.jikesrvm.Constants
NOT_REACHED, REFLECTION_FPRS_BITS, REFLECTION_FPRS_MASK, REFLECTION_GPRS_BITS, REFLECTION_GPRS_MASK
 
Fields inherited from interface org.jikesrvm.objectmodel.ThinLockConstants
TL_DEDICATED_U16_OFFSET, TL_DEDICATED_U16_SHIFT, TL_LOCK_COUNT_MASK, TL_LOCK_COUNT_SHIFT, TL_LOCK_COUNT_UNIT, TL_LOCK_ID_MASK, TL_LOCK_ID_SHIFT, TL_NUM_BITS_RC, TL_NUM_BITS_STAT, TL_NUM_BITS_TID, TL_STAT_BIASABLE, TL_STAT_FAT, TL_STAT_MASK, TL_STAT_SHIFT, TL_STAT_THIN, TL_THREAD_ID_MASK, TL_THREAD_ID_SHIFT, TL_UNLOCK_MASK
 
Fields inherited from interface org.jikesrvm.SizeConstants
BITS_IN_ADDRESS, BITS_IN_BOOLEAN, BITS_IN_BYTE, BITS_IN_CHAR, BITS_IN_DOUBLE, BITS_IN_EXTENT, BITS_IN_FLOAT, BITS_IN_INT, BITS_IN_LONG, BITS_IN_OFFSET, BITS_IN_PAGE, BITS_IN_SHORT, BITS_IN_WORD, BYTES_IN_ADDRESS, BYTES_IN_BOOLEAN, BYTES_IN_BYTE, BYTES_IN_CHAR, BYTES_IN_DOUBLE, BYTES_IN_EXTENT, BYTES_IN_FLOAT, BYTES_IN_INT, BYTES_IN_LONG, BYTES_IN_OFFSET, BYTES_IN_PAGE, BYTES_IN_SHORT, BYTES_IN_WORD, LOG_BITS_IN_ADDRESS, LOG_BITS_IN_BOOLEAN, LOG_BITS_IN_BYTE, LOG_BITS_IN_CHAR, LOG_BITS_IN_DOUBLE, LOG_BITS_IN_EXTENT, LOG_BITS_IN_FLOAT, LOG_BITS_IN_INT, LOG_BITS_IN_LONG, LOG_BITS_IN_OFFSET, LOG_BITS_IN_PAGE, LOG_BITS_IN_SHORT, LOG_BITS_IN_WORD, LOG_BYTES_IN_ADDRESS, LOG_BYTES_IN_BOOLEAN, LOG_BYTES_IN_BYTE, LOG_BYTES_IN_CHAR, LOG_BYTES_IN_DOUBLE, LOG_BYTES_IN_EXTENT, LOG_BYTES_IN_FLOAT, LOG_BYTES_IN_INT, LOG_BYTES_IN_LONG, LOG_BYTES_IN_OFFSET, LOG_BYTES_IN_PAGE, LOG_BYTES_IN_SHORT, LOG_BYTES_IN_WORD
 
Fields inherited from interface org.jikesrvm.objectmodel.TIBLayoutConstants
IMT_METHOD_SLOTS, NEEDS_DYNAMIC_LINK, TIB_ARRAY_ELEMENT_TIB_INDEX, TIB_DOES_IMPLEMENT_INDEX, TIB_FIRST_SPECIALIZED_METHOD_INDEX, TIB_FIRST_VIRTUAL_METHOD_INDEX, TIB_INTERFACE_DISPATCH_TABLE_INDEX, TIB_SUPERCLASS_IDS_INDEX, TIB_TYPE_INDEX
 
Fields inherited from interface org.jikesrvm.HeapLayoutConstants
BAD_MAP_COMPRESSION, BOOT_IMAGE_CODE_END, BOOT_IMAGE_CODE_SIZE, BOOT_IMAGE_CODE_START, BOOT_IMAGE_DATA_END, BOOT_IMAGE_DATA_SIZE, BOOT_IMAGE_DATA_START, BOOT_IMAGE_END, BOOT_IMAGE_RMAP_END, BOOT_IMAGE_RMAP_START, MAX_BOOT_IMAGE_RMAP_SIZE, MAXIMUM_MAPPABLE
 
Constructor Summary
Lock()
          A heavy weight lock to handle extreme contention and wait/notify synchronization.
 
Method Summary
static void addLock(Lock l)
          Add a lock to the lock table
(package private) static Lock allocate()
          Delivers up an unassigned heavy-weight lock.
static void boot()
          Set up callbacks to report statistics.
static int countLocksHeldByThread(int id)
          Count number of locks held by thread
private  void deflate(Object o, Offset lockOffset)
          Disassociates this heavy-weight lock from the indicated object.
private  void dump()
          Reports the state of a heavy-weight lock, via VM.sysWrite(org.jikesrvm.classloader.Atom).
protected  void dumpBlockedThreads()
          Dump threads blocked trying to get this lock
static void dumpLocks()
          Dump the lock table.
protected  void dumpWaitingThreads()
          Dump threads waiting to be notified on this lock
protected static void free(Lock l)
          Recycles an unused heavy-weight lock.
static Lock getLock(int id)
          Read a lock from the lock table by id.
 Object getLockedObject()
          Get the object that this lock is referring to.
 int getOwnerId()
          Get the thread id of the current owner of the lock.
 int getRecursionCount()
          Get the lock's recursion count.
static String getThreadState(RVMThread t)
          scan lock queues for thread and report its state
(package private) static void growLocks(int id)
          Grow the locks table by allocating a new spine chunk.
static void init()
          Sets up the data structures for holding heavy-weight locks.
protected  boolean isBlocked(RVMThread t)
          Is this lock blocking thread t?
protected  boolean isWaiting(RVMThread t)
          Is this thread t waiting on this lock?
 boolean lockHeavy(Object o)
          Acquires this heavy-weight lock on the indicated object.
 boolean lockHeavyLocked(Object o)
          Complete the task of acquiring the heavy lock, assuming that the mutex is already acquired (locked).
static int numLocks()
          Return the number of lock slots that have been allocated.
private static void raiseIllegalMonitorStateException(String msg, Object o)
           
(package private) static void returnLock(Lock l)
           
 void setLockedObject(Object o)
          Set the object that this lock is referring to.
 void setOwnerId(int id)
          Set the owner of a lock
 void setRecursionCount(int c)
          Update the lock's recursion count.
 void unlockHeavy(Object o)
          Releases this heavy-weight lock on the indicated object.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

trace

protected static final boolean trace
do debug tracing?

See Also:
Constant Field Values

STATS

public static final boolean STATS
Control the gathering of statistics

See Also:
Constant Field Values

LOCK_SPINE_SIZE

protected static final int LOCK_SPINE_SIZE
The (fixed) number of entries in the lock table spine

See Also:
Constant Field Values

LOG_LOCK_CHUNK_SIZE

protected static final int LOG_LOCK_CHUNK_SIZE
The log size of each chunk in the spine

See Also:
Constant Field Values

LOCK_CHUNK_SIZE

protected static final int LOCK_CHUNK_SIZE
The size of each chunk in the spine

See Also:
Constant Field Values

LOCK_CHUNK_MASK

protected static final int LOCK_CHUNK_MASK
The mask used to get the chunk-level index

See Also:
Constant Field Values

MAX_LOCKS

protected static final int MAX_LOCKS
The maximum possible number of locks

See Also:
Constant Field Values

INITIAL_CHUNKS

protected static final int INITIAL_CHUNKS
The number of chunks to allocate on startup

See Also:
Constant Field Values

tentativeMicrolocking

private static final boolean tentativeMicrolocking
Should we give up or persist in the attempt to get a heavy-weight lock, if its mutex microlock is held by another procesor.

See Also:
Constant Field Values

locks

private static Lock[][] locks
The table of locks.

lockAllocationMutex

private static final SpinLock lockAllocationMutex
Used during allocation of locks within the table.

chunksAllocated

private static int chunksAllocated
The number of chunks in the spine that have been physically allocated

nextLockIndex

private static int nextLockIndex
The number of locks allocated (these may either be in use, on a global freelist, or on a thread's freelist.

globalFreeLock

private static Lock globalFreeLock
A global lock free list head

globalFreeLocks

private static int globalFreeLocks
the number of locks held on the global free list.

globalLocksAllocated

private static int globalLocksAllocated
the total number of allocation operations.

globalLocksFreed

private static int globalLocksFreed
the total number of free operations.

lockOperations

public static int lockOperations
Number of lock operations

unlockOperations

public static int unlockOperations
Number of unlock operations

deflations

public static int deflations
Number of deflations

lockedObject

protected Object lockedObject
The object being locked (if any).

ownerId

protected int ownerId
The id of the thread that owns this lock (if any).

recursionCount

protected int recursionCount
The number of times the owning thread (if any) has acquired this lock.

mutex

public final SpinLock mutex
A spin lock to handle contention for the data structures of this lock.

active

protected boolean active
Is this lock currently being used?

nextFreeLock

private Lock nextFreeLock
The next free lock on the free lock list

index

protected int index
This lock's index in the lock table

entering

ThreadQueue entering
Queue for entering the lock, guarded by mutex.

waiting

ThreadQueue waiting
Queue for waiting on a notify, guarded by mutex as well.

Constructor Detail

Lock

public Lock()
A heavy weight lock to handle extreme contention and wait/notify synchronization.

Method Detail

lockHeavy

public boolean lockHeavy(Object o)
Acquires this heavy-weight lock on the indicated object.

Parameters:
o - the object to be locked
Returns:
true, if the lock succeeds; false, otherwise

lockHeavyLocked

public boolean lockHeavyLocked(Object o)
Complete the task of acquiring the heavy lock, assuming that the mutex is already acquired (locked).

raiseIllegalMonitorStateException

private static void raiseIllegalMonitorStateException(String msg,
                                                      Object o)

unlockHeavy

public void unlockHeavy(Object o)
Releases this heavy-weight lock on the indicated object.

Parameters:
o - the object to be unlocked

deflate

private void deflate(Object o,
                     Offset lockOffset)
Disassociates this heavy-weight lock from the indicated object. This lock is not held, nor are any threads on its queues. Note: the mutex for this lock is held when deflate is called.

Parameters:
o - the object from which this lock is to be disassociated

setOwnerId

public void setOwnerId(int id)
Set the owner of a lock

Parameters:
id - The thread id of the owner.

getOwnerId

public int getOwnerId()
Get the thread id of the current owner of the lock.

setRecursionCount

public void setRecursionCount(int c)
Update the lock's recursion count.

getRecursionCount

public int getRecursionCount()
Get the lock's recursion count.

setLockedObject

public void setLockedObject(Object o)
Set the object that this lock is referring to.

getLockedObject

public Object getLockedObject()
Get the object that this lock is referring to.

dumpBlockedThreads

protected void dumpBlockedThreads()
Dump threads blocked trying to get this lock

dumpWaitingThreads

protected void dumpWaitingThreads()
Dump threads waiting to be notified on this lock

dump

private void dump()
Reports the state of a heavy-weight lock, via VM.sysWrite(org.jikesrvm.classloader.Atom).

isBlocked

protected boolean isBlocked(RVMThread t)
Is this lock blocking thread t?

isWaiting

protected boolean isWaiting(RVMThread t)
Is this thread t waiting on this lock?

init

public static void init()
Sets up the data structures for holding heavy-weight locks.

allocate

static Lock allocate()
Delivers up an unassigned heavy-weight lock. Locks are allocated from processor specific regions or lists, so normally no synchronization is required to obtain a lock.

Collector threads cannot use heavy-weight locks.

Returns:
a free Lock; or null, if garbage collection is not enabled

free

protected static void free(Lock l)
Recycles an unused heavy-weight lock. Locks are deallocated to processor specific lists, so normally no synchronization is required to obtain or release a lock.

returnLock

static void returnLock(Lock l)

growLocks

static void growLocks(int id)
Grow the locks table by allocating a new spine chunk.

numLocks

public static int numLocks()
Return the number of lock slots that have been allocated. This provides the range of valid lock ids.

getLock

public static Lock getLock(int id)
Read a lock from the lock table by id.

Parameters:
id - The lock id
Returns:
The lock object.

addLock

public static void addLock(Lock l)
Add a lock to the lock table

Parameters:
l - The lock object

dumpLocks

public static void dumpLocks()
Dump the lock table.

countLocksHeldByThread

public static int countLocksHeldByThread(int id)
Count number of locks held by thread

Parameters:
id - the thread locking ID we're counting for
Returns:
number of locks held

getThreadState

public static String getThreadState(RVMThread t)
scan lock queues for thread and report its state

boot

public static void boot()
Set up callbacks to report statistics.

Overview  Package   Class  Use  Tree  Serialized  Deprecated  Index  Help 
 PREV CLASS   NEXT CLASS FRAMES    NO FRAMES    
SUMMARY: NESTED | FIELD | CONSTR | METHOD DETAIL: FIELD | CONSTR | METHOD