In this article we will see an example of Java ReentrantLock example, the internal data structure and algorithms used.
As the name suggests a ReentrantLock is a lock that may be acquired by the same thread multiple times. If a thread trying to acquire the lock is not the same as the thread that already owns the lock then the attempt will either fail or block. If the operation is time scoped, then the attempt to acquire the lock will fail if the specified waiting time elapsed. You can also read more about ReentrantLock here.
ReentrantLock Example
A thread acquires the lock if it is not acquired by any other thread yet. Once acquired, it set the internal hold state to one and the current thread becomes the lock owner.
ReentrantLock lock = new ReentrantLock(); lock.lock();
Class AcquireLockRunnable
is a Runnable
which acquires the lock, does nothing and then releases the lock.
private static class AcquireLockRunnable implements Runnable { public void run() { ... lock.lock(); ... Thread.sleep(5000); ... } finally { lock.unlock(); } } }
In the below example, the first thread acquires the lock.
Thread firstThread = new Thread(new AcquireLockRunnable(), "FirstThread"); firstThread.start(); Thread.sleep(1000);
Any attempt by the other threads that follow only gets blocked.
for (int i = 2; i < 9; i++) { Thread t = new Thread(new AcquireLockRunnable(), "OtherThreads(" + (i - 1) + ")"); t.start(); }
Since no other thread has held the lock yet, the first thread that tried, manages to own it and the internal lock hold count gets set to one.
We allow the first thread to sleep for a bit longer than the other threads so that the lock stays with the first thread.
ReentrantLockExample:
package com.javarticles.threads; import java.util.concurrent.atomic.AtomicInteger; import java.util.concurrent.locks.ReentrantLock; public class ReentrantLockExample { private static ReentrantLock lock = new ReentrantLock(); private static AtomicInteger counter = new AtomicInteger(0); public static void main(String[] args) throws InterruptedException { Thread firstThread = new Thread(new AcquireLockRunnable(), "FirstThread"); firstThread.start(); Thread.sleep(1000); for (int i = 2; i < 9; i++) { Thread t = new Thread(new AcquireLockRunnable(), "OtherThreads(" + (i - 1) + ")"); t.start(); } } private static void print(String tag, String p) { System.out.println(Thread.currentThread().getName() + ": " + tag + ": " + p); } private static class AcquireLockRunnable implements Runnable { public void run() { counter.incrementAndGet(); print("AcquireLockRunnable", "try lock"); lock.lock(); print("AcquireLockRunnable", "got lock"); try { if (counter.get() == 1) { Thread.sleep(5000); } else { Thread.sleep(1000); } } catch (InterruptedException e) { e.printStackTrace(); } finally { lock.unlock(); print("AcquireLockRunnable", "unlocked"); } } } }
The other threads trying to acquire the lock fail and get added to a queue. The thread associated is then disabled for thread scheduling purposes and lies suspended until it is signaled by a release from the thread owning the lock after which it will make another attempt to acquire the lock. When the thread releases the lock, it will unblock the immediate successor in the waiting queue.
If during the time of attempt some other thread acquires the lock then it will again be block. It may go through repeated blocking and unblocking till it acquires the lock in which case it will be removed from the waiting queue and will be promoted as the head of the queue.
Output:
FirstThread: AcquireLockRunnable: try lock FirstThread: AcquireLockRunnable: got lock OtherThreads(1): AcquireLockRunnable: try lock OtherThreads(3): AcquireLockRunnable: try lock OtherThreads(2): AcquireLockRunnable: try lock OtherThreads(5): AcquireLockRunnable: try lock OtherThreads(6): AcquireLockRunnable: try lock OtherThreads(7): AcquireLockRunnable: try lock OtherThreads(4): AcquireLockRunnable: try lock FirstThread: AcquireLockRunnable: unlocked OtherThreads(3): AcquireLockRunnable: got lock OtherThreads(3): AcquireLockRunnable: unlocked OtherThreads(2): AcquireLockRunnable: got lock OtherThreads(2): AcquireLockRunnable: unlocked OtherThreads(1): AcquireLockRunnable: got lock OtherThreads(1): AcquireLockRunnable: unlocked OtherThreads(5): AcquireLockRunnable: got lock OtherThreads(5): AcquireLockRunnable: unlocked OtherThreads(6): AcquireLockRunnable: got lock OtherThreads(7): AcquireLockRunnable: got lock OtherThreads(6): AcquireLockRunnable: unlocked OtherThreads(7): AcquireLockRunnable: unlocked OtherThreads(4): AcquireLockRunnable: got lock OtherThreads(4): AcquireLockRunnable: unlocked
ReentrantLock Recursive Example
If a thread is trying to acquire a lock already owned by some other thread then it is guaranteed to fail but if the owning thread is trying to acquire the same lock once again, its internal hold count will be incremented by one.
ReentrantLockRecursiveLockExample:
package com.javarticles.threads; import java.util.concurrent.locks.ReentrantLock; public class ReentrantLockRecursiveLockExample { private static ReentrantLock lock = new ReentrantLock(); public static void main(String[] args) throws InterruptedException { Thread firstThread = new Thread(new RecursiveLocksRunnable(), "FirstThread"); firstThread.start(); Thread secondThread = new Thread(new AcquireLockRunnable(), "SecondThread" ); secondThread.start(); } private static void print(String tag, String p) { System.out.println(Thread.currentThread().getName() + ": " + tag + ": " + p); } private static class RecursiveLocksRunnable implements Runnable { int level = 0; public void run() { try { someMethod(); } catch (InterruptedException e) { e.printStackTrace(); } } private void someMethod() throws InterruptedException { level++; print("RecursiveLocksRunnable.someMethod", "try lock(" + level + ")"); lock.lock(); print("RecursiveLocksRunnable.someMethod", "got lock(" + level + ")"); try { if (level <= 3) { someMethod(); if (level == 2) { Thread.sleep(1000); } } else { Thread.sleep(1000); } } finally { print("RecursiveLocksRunnable.someMethod", "release lock(" + level + ")"); lock.unlock(); print("RecursiveLocksRunnable.someMethod", "lock(" + level + ") released"); level--; } } } private static class AcquireLockRunnable implements Runnable { public void run() { print("AcquireLockRunnable", "try lock"); lock.lock(); print("AcquireLockRunnable", "got lock"); try { try { Thread.sleep(10000); } catch (InterruptedException e) { e.printStackTrace(); } } finally { lock.unlock(); print("AcquireLockRunnable", "unlocked"); } } } }
Output:
FirstThread: RecursiveLocksRunnable.someMethod: try lock(1) FirstThread: RecursiveLocksRunnable.someMethod: got lock(1) FirstThread: RecursiveLocksRunnable.someMethod: try lock(2) FirstThread: RecursiveLocksRunnable.someMethod: got lock(2) FirstThread: RecursiveLocksRunnable.someMethod: try lock(3) FirstThread: RecursiveLocksRunnable.someMethod: got lock(3) FirstThread: RecursiveLocksRunnable.someMethod: try lock(4) FirstThread: RecursiveLocksRunnable.someMethod: got lock(4) SecondThread: AcquireLockRunnable: try lock FirstThread: RecursiveLocksRunnable.someMethod: release lock(4) FirstThread: RecursiveLocksRunnable.someMethod: lock(4) released FirstThread: RecursiveLocksRunnable.someMethod: release lock(3) FirstThread: RecursiveLocksRunnable.someMethod: lock(3) released FirstThread: RecursiveLocksRunnable.someMethod: release lock(2) FirstThread: RecursiveLocksRunnable.someMethod: lock(2) released FirstThread: RecursiveLocksRunnable.someMethod: release lock(1) FirstThread: RecursiveLocksRunnable.someMethod: lock(1) released SecondThread: AcquireLockRunnable: got lock SecondThread: AcquireLockRunnable: unlocked
Add to waiting queue
When the second thread fails to acquire lock as the lock is already acquired by the first thread then it adds itself to the waiting node linked list at the end of the list.
Try acquiring lock for the queued thread
After the thread adds itself to the waiting node linked list, it will still try acquiring lock in exclusive uninterruptible mode.
If the thread trying to acquire lock is not the successor to the header node then it won’t be able to acquire the lock. It will still not be parked yet and the predecessor’s status field will be checked to figure out whether the status represents the correct state.
Park the thread if lock not acquired
The thread that is trying to acquire lock will check if the node that it is associated to is next to the header node. If not there are chances that the there may be few canceled nodes between the head and the node being inspected. If the node is not next to header, we need to recheck this after removing the canceled nodes.
In order to avoid this kind of check again and again, a status field is maintained. Any node which is going to get parked must have its previous node’s wait status set to -1 which indicates that the current node being parked needs to be ‘Signaled’ as soon as its predecessor node is going to get released. Caller will need to retry to make sure it cannot acquire and its previous node’s status is set to a state representing ‘Signal’ before parking.
Release the lock
We release the lock using lock.unlock
. If the current thread owns the lock the hold count is decremented. If the hold count becomes zero then the lock is released. If the current thread is not the owner of this lock then IllegalMonitorStateException
is thrown. Assuming the current thread is the owner of the lock, below algorithm takes place during the release of the lock.
Download the source code
This was an example about ReentrantLock, internal data structures and the algorithms used.