What is a deadlock? How does it differ from a race condition? How to avoid deadlock, including when it is impossible to determine the order of lock acquisition in advance?

Deadlock is a situation in a multithreaded application where two or more threads permanently block each other, waiting for resources held by others. As a result, none of the threads can continue work.

Difference from race condition:

• Deadlock is mutual blocking of threads, leading to a halt.
• Race condition is a race state where the outcome depends on the unpredictable order of thread execution, which can lead to errors.

To avoid deadlock, especially if the order of lock acquisition cannot be predetermined, the following approaches can be used:

1. Attempt to acquire with timeout or without blocking: use tryLock methods, which attempt to acquire a lock and, if unsuccessful, release already acquired resources and retry later.

2. Lock hierarchy: if possible, establish a strict order of resource acquisition to avoid cyclic waiting.

3. Use high-level constructs: for example, classes from the java.util.concurrent package, which minimize the risk of deadlock.

4. Lock-free design: use non-blocking algorithms and data structures.

Example with tryLock:

Lock lock1 = ...;
Lock lock2 = ...;

while (true) {
    if (lock1.tryLock()) {
        try {
            if (lock2.tryLock()) {
                try {
                    // work with resources
                    break;
                } finally {
                    lock2.unlock();
                }
            }
        } finally {
            lock1.unlock();
        }
    }
    // pause or other logic before retrying
}

This approach prevents mutual blocking, as threads do not wait indefinitely but retry acquiring locks.