java multi-thread acquire lock not working

Question

I'm trying to write a small snippet of code to lock and unlock a block of code. the acquire_lock and release_lock functions are as below:

    public static void acquire_lock(long timestamp) {
    synchronized(operations) {
        // put the timestamp into queue
        operations.add(timestamp);
        // check if the head of queue is current timestamp, if not,
        // this means there are some other operations ahead of current one
        // so current operation has to wait
        while (operations.peek() != timestamp) {
            try {
                operations.wait();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
}

public static void release_lock() {
    synchronized(operations) {
        // poll the finished operation out of queue
        // and wake up all waiting operations
        operations.poll();
        operations.notifyAll();
    }
}

But when I put this code into a test environment, it doesn't always work well, the whole test code is as below:

public class AcquireLockNotWork {

static int balance = 0;
static PriorityQueue<Long> operations = new PriorityQueue<Long>();

// withdraw money from balance
public static void withdraw(final int amt) {
    // get system time
    Long timestamp = System.nanoTime();
    Thread t = new Thread(new Runnable() {
        public void run() {
            // try to use acquire_lock to lock this piece of code
            acquire_lock(timestamp);
            try {       
                Thread.sleep(500);
                int holdings = balance;
                balance = holdings - amt;
                System.out.println("Withdrew " + amt + " from funds. Now at " + balance);
            } catch (Exception e) {
                e.printStackTrace();
            } finally {
                release_lock();
            }       
        }
    });
    t.start();
}

//put money into banlance
public static void deposit(int amt) {
    Thread t1 = new Thread(new Runnable() {
        public void run() {
            Long timestamp = System.nanoTime();
            acquire_lock(timestamp);
            int holdings = balance;
            balance = holdings + amt;
            System.out.println("deposit " + amt + ", balance: " + balance);
            release_lock();
        }
    });
    t1.start();
}

public static void acquire_lock(long timestamp) {
    synchronized(operations) {
        // put the timestamp into queue
        operations.add(timestamp);
        // check if the head of queue is current timestamp, if not,
        // this means there are some other operations ahead of current one
        // so current operation has to wait
        while (operations.peek() != timestamp) {
            try {
                operations.wait();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
}

public static void release_lock() {
    synchronized(operations) {
        // poll the finished operation out of queue
        // and wake up all waiting operations
        operations.poll();
        operations.notifyAll();
    }
}

public static void test1() {
    balance = 0;
    deposit(2000);
    withdraw(500);
    withdraw(1000);
}

public static void main(String[] args) {
    test1();
}
}

for a small number of times, the result will be like this:

deposit 2000, balance: 2000
Withdrew 500 from funds. Now at 500
Withdrew 1000 from funds. Now at 500

which means that the acquire_lock and release_lock function doesn't work well. It seems that the last two thread (withdrew 500 and withdrew 1000) has entered the block between acquire_lock() and release_lock() simultaneously, and it is not what I want. So what's wrong with the acquire_lock and release_lock function?

Answer 1

It is very tricky here. The anomalous happens because the latter thread enter the acquire_lock first. And when the earlier thread goes into the acquire_lock, it will not be blocked, because the code block the threads based on their timestamp. So the two thread go to the same protected code area.