I have two threads, one with id 0, and the other with id 1. Based on this information I tried to construct a lock, but it seems like it deadlocks, but I don't understand why, can someone please help me?

I tried to construct a scenario when this happens, but it is really difficult

  private int turn = 0;
  private boolean [] flag = new boolean [2];
   
  public void lock(int tid) {
    int other;
 
    other = (tid == 0) ? 1 : 0;

    flag[tid] = true;
    while (flag[other] == true) {
      if (turn == other) {
        flag[tid] = false;
        while (turn == other){}
        flag[tid] = true;
      }
    }
  }
 
  public void unlock(int tid) {
    //turn = 1-t;
    turn = (tid == 0) ? 1 : 0;
    flag[tid] = false;
  }

CodePudding user response：

Yup, this code is broken. It's.. a complicated topic. If you want to know more, dive into the Java Memory Model (JMM) - that's a term you can search the web form.

In basis, every field in a JVM has the following property, unless it is marked volatile:

• Any thread is free to make a local clone of this field, or not.
• The VM is free to sync these clones up, in arbitrary fashion, at any time. Could be in 5 seconds, could be in 5 years. The VM is free to do whatever it wants, the spec intentionally does not make many guarantees.
• To solve this problem, establish HB/HA (A Happens-Before/Happens-After relationship).

In other words, if 2 threads both look at the same field, and you haven't established HB/HA, your code is broken, and it's broken in a way that you can't reliably test for, because the JVM can do whatever it wants. This includes working as you expect during tests.

To establish HB/HA, you need volatile/synchronized, pretty much. There's a long list, though:

• x.start() is HB to the first line in that thread's HA.
• Exiting a synchronized(x) {} block is HB to the start of a synchronized (x) {} block, assuming both x's are pointing at the same object.
• Volatile access establishes HB/HA, but you can't really control in which direction.
• Note that many library calls, such as to ReadWriteLock and co, may well be synchronizing/using volatile under the hood, thus in passing establishing some form of HB/HA.
• "Natural" HB/HA: Within a single thread, a line executed earlier is HB to a line executed later. One might say 'duh' on this one.

Note that HB/HA doesn't actually mean they actually happen before. It merely means that it is not possible to observe the state as it was before the HB line from the HA line, other than by timing attacks. This usually doesn't matter.

The problem

Your code has two threads that both look at the same field, does not contain volatile or synchronized or otherwise establishes HB/HA anywhere, and doesn't use library calls that do so. Therefore, this code is broken.

The solution is to introduce that someplace. Not sure why you're rolling your own locks - the folks who wrote ReadWriteLock and friends in the java.util.concurrent package are pretty smart. There is zero chance you can do better than them, so just use that.