Lock implementation using atomics

Question

I was recently given an interview and was asked to write my own lock implementation using atomics, but not necessary reentrant.

I didn't answer the question, but at home, I wrote this code. Please asses my implementation and suggest better solutions.

public class MyLock {
 AtomicBoolean locked = new AtomicBoolean(false);
 ThreadLocal<Boolean> threadLocal = new ThreadLocal();
 public void lock() {
 while (true) {
 if (locked.compareAndSet(false, true)) {
 threadLocal.set(true);
 return;
 }
 }
 }
 public void unLock() {
 if (threadLocal.get()) {
 locked.compareAndSet(true, false);
 threadLocal.set(false);
 }
 }
}
class Main {
 public static void main(String[] args) {
 MyLock myLock = new MyLock();
 for (int i=0;i<10;i++)
 new MyThread(myLock).start();
 }
}
class MyThread extends Thread {
 final MyLock myLock;
 MyThread(MyLock myLock) {
 this.myLock = myLock;
 }
 @Override public void run() {
 myLock.lock();
 System.out.println("start - " + Thread.currentThread().getName());
 try {
 Thread.sleep(5000);
 } catch (InterruptedException e) {
 e.printStackTrace(); //To change body of catch statement use File | Settings | File Templates.
 }
 System.out.println("finish - " + Thread.currentThread().getName());
 myLock.unLock();
 }
}

• markspace: Did your interview question also require that you not use wait(), notify() and synchronized ?

Answer 1

I think the main problem of your implementation is that lock() performs Busy waiting. This will cause a thread that is waiting to get the lock to repeatedly waste CPU-cycles by polling (multiple times in one time slot) whether the lock has been released.

Easiest fix for that is to perform a call to Thread.yield() after trying to acquire the lock. This will cause the thread to exit its time slot and therefore let the other threads do their work.

public void lock() {
 while (true) {
 if (locked.compareAndSet(false, true)) {
 threadLocal.set(true);
 return;
 }
 Thread.yield();
 }
}

Oh and I would rename the method unLock() to unlock() since it is an existing english word.

• maaartinus: Thread.yield() is not guaranteed to do anything at all. Sure, adding it is better than nothing. IIRC there's a CPU instruction designed for exactly this purpose and IIRC it's accessible from Java, but I can't recall its name.
• markspace: I don't think there's a CPU instruction for yeild. It's an OS call, because the OS must move this thread to the end of the ready list and execute another thread in its place (all of which as you point out is not guaranteed to actually do anything).

Answer 2

Your threadLocal prevents a thread from unlocking a lock taken by a different thread. That's not good, as there are legitimate uses for this scenario (some producer-consumer).

What I also dislike is silently ignoring the unlock request. If it's forbidden, then it should probably throw.

Anyway, you can what you did without any thread local just by using AtomicReference<Thread> (with the content being the locking thread, or null, if it's free).

//To change body of catch statement use File | Settings | File Templates.

Should I?