Deadlock when de-initializing instances with long-running threads

I'm uncertain which programming language you're using, but the following C# implementation is easily refactorable C++, Java, etc. - and should solve your problem if I understand it correctly. Find Benchmarks and the full implementation below the example section.

Example Usage

The following is a simple example of how to use the class. Instantiate and pass to all threads. Calls to CompareExchange and Exchange are atomic operations on the static 'long current' variable, which may be any stack based value type (e.g. struct) and has no size restrictions. A call to Cancel on any cancels all waits to Acquire across threads and throws AtomicCancellationException across threads to terminate and transition program flow to the catch blocks as illustrated in the example. See code comments for additional details:

//pass a reference to this class to all threads 
public class AtomicExample
{
    //static global variable being updated by all threads sequentially
    static long current = 0;

    //Instantiate Atomic<T> w/ desired struct type param       
    Atomic<long> _lock = new(); 
    
    public bool Atomic_CompareExchange(long value)
    {
        try
        {
            //updates the value atomically if not equal to current
            if (_lock.CompareExchange(ref current, value, current) == value)
                return true; //current == comparand, current = value
        }
        catch (AtomicCancellationException)
        {
            //threads awaiting spinlock terminated, cleanup and shutdown
        }

        return false; //current != comarand, current = current 
    }

    public long Atomic_Exchange(long value)
    {
        try
        {
            //updates the value atomically regardless of equality (i.e. CompareExchange above)
            return _lock.Exchange(ref current, value);
        }
        catch (AtomicCancellationException)
        {
            //thread was terminated cleanup and shutdown
        }
        
        return current;
    }
    // 1. terminates all waits to Acquire lock 
    // 2. transitions program flow to the catch blocks above on all threads
    public void Cancel()
    {
        _lock.Cancel();
    }
}

Benchmark

The following are BenchmarkDotNet comparisons between Interlocked and the Atomic implementation below. All benchmarks are 1M iterations with 2 competing threads. InterLocked doesn't support types > 8-bytes, which is why there is no head-to-head comp for Guid. In addition, Interlocked is a static class that is not intended to solve cross thread signaling and cancellation like Atomic<T>

• "InterLocked_..." - InterLocked.CompareExchange
• "Atomic..." - Atomic<T>.CompareExchange - implementation below
• "Lock..." - Atomic<T>.CompareExchange - modified to use lock{...}

|           Method |      Mean |     Error |    StdDev | Ratio | RatioSD |
|----------------- |----------:|----------:|----------:|------:|--------:|
| Interlocked_Long |  6.989 ms | 0.0541 ms | 0.0506 ms |  1.00 |    0.00 |
|      Atomic_Long |  9.566 ms | 0.0858 ms | 0.0761 ms |  1.37 |    0.01 |
|        Lock_Long | 19.020 ms | 0.0721 ms | 0.0563 ms |  2.72 |    0.02 |
|      Atomic_Guid | 76.644 ms | 1.0858 ms | 1.1151 ms | 10.98 |    0.15 |
|       Lock__Guid | 84.223 ms | 0.1813 ms | 0.1514 ms | 12.05 |    0.09 |

Implementation

[StructLayout(LayoutKind.Auto)]
/// <summary>Atomic<T> class supports attomic CompareExchange and Exchange opertaions
/// in and "Interlocked" thread-safe mannor supporting of any struct/value (stack based) type</summary>
public struct Atomic<T> where T : struct
{
    private AtomicSpinWait _lock = new();
    
    //constructor
    public Atomic() {}

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public T CompareExchange(ref T current, T value, T compareand)
    {
        _lock.Acquire();
        
        var sizeOf = Unsafe.SizeOf<T>();

        // Note: comparison of bytes with pointer implemented inside .Net's "CreateReadOnlySpan"
        // use pinned byte pointer and replace with iterator for C, C+++
        if (!MemoryMarshal.CreateReadOnlySpan(ref Unsafe.As<T, byte>(ref current), sizeOf).SequenceEqual(
            MemoryMarshal.CreateReadOnlySpan(ref Unsafe.As<T, byte>(ref compareand), sizeOf)))
            current = value;

        _lock.Release();

        return current;
    }

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public T Exchange(ref T location, T value)
    {
        _lock.Acquire();
        
        location = value;

        _lock.Release();

        return location;
    }
    
    public void Cancel() => _lock.Cancel();

    [StructLayout(LayoutKind.Auto)]
    private struct AtomicSpinWait
    {
        private volatile int _value;
        private volatile int _cancel = 0;

        public AtomicSpinWait() => _value = 0;

        // cancells all threads awaiting entry to acquire and throws AtomicCancellationException
        internal void Acquire()
        {
            for (var sw = new SpinWait(); CompareExchange(1, 0) == 1 && _cancel == 0; sw.SpinOnce()) ;
            if (_cancel == 1) throw new AtomicCancellationException();
        }

        internal void Release() => _value = 0;

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        private int CompareExchange(int value, int comparand)
            => Interlocked.CompareExchange(ref _value, value, comparand);

        public void Cancel() => Interlocked.Exchange(ref _cancel, 1);
    }
}

//Exception thrown terminating locks across threads waiting to Acquire() lock
public class AtomicCancellationException : Exception { }

//Refactor of Microsoft's SpinWait impl to make things simple
public struct SpinWait
{
    internal static readonly bool IsSingleProcessor = Environment.ProcessorCount == 1;
    internal static readonly int SpinCountforSpinBeforeWait = (IsSingleProcessor ? 1 : 35);

    private int _count;

    public int Count { get; internal set; }

    public bool NextSpinWillYield
    {
        get
        {
            if (_count < 10)
            {
                return IsSingleProcessor;
            }
            return true;
        }
    }

    public void SpinOnce()
    {
        SpinOnceCore(20);
    }

    public void SpinOnce(int sleep1Threshold)
    {
        if (sleep1Threshold < -1)
        {
            throw new ArgumentOutOfRangeException("sleep1Threshold: " + sleep1Threshold);
        }
        if (sleep1Threshold >= 0 && sleep1Threshold < 10)
        {
            sleep1Threshold = 10;
        }
        SpinOnceCore(sleep1Threshold);
    }
    private void SpinOnceCore(int sleep1Threshold)
    {
        if ((_count >= 10 && ((_count >= sleep1Threshold && sleep1Threshold >= 0) || (_count - 10) % 2 == 0)) || IsSingleProcessor)
        {
            if (_count >= sleep1Threshold && sleep1Threshold >= 0)
            {
                Thread.Sleep(1);
            }
            else
            {
                int num = ((_count >= 10) ? ((_count - 10) / 2) : _count);
                if (num % 5 == 4)
                {
                    Thread.Sleep(0);
                }
                else
                {
                    Thread.Yield();
                }
            }
        }
        else
        {
            int num2 = 7;
            if (_count <= 30 && 1 << _count < num2)
            {
                num2 = 1 << _count;
            }
            Thread.SpinWait(num2);
        }
        _count = ((_count == int.MaxValue) ? 10 : (_count + 1));
    }
    public void Reset()
    {
        _count = 0;
    }
}

I'm not sure what the question is - a coding pattern for shutting down threads or avoiding deadlock while doing so. I can only appeal to authority on the latter.

Coffman, Elphick, and Shoshani in "System Deadlocks," Computing Surveys, Vol. 3, No 2, June 1971 PP 71-76 stated the following four necessary conditions that must be in effect for a deadlock to exist.

1. Mutual exclusion
2. Wait for
3. No preemption
4. Circular wait

Remove any one of those conditions and you can't deadlock. If you're looking for an authoritative answer on how to handle your circumstance, there isn't enough detail in your question to make a specific recommendation. Maybe you don't care about reasons for deadlock, but I'll use these conditions to give context to a few solutions. I'll also tell you what I do for the simple case of a class that has long running threads.

1. Removing mutual-exclusion - if state is only being read and not written, a read/write lock can be used and when acquired for read, there is no mutual exclusion with other readers.
2. Removing wait-for - if the condition being check has not been met, release and reacquire the mutex allowing other threads to acquire and modify state until the condition you're waiting for has been met. This is what a condition variable does for you (e.g., pthread_condition). It allows you to wait for some condition to be true (e.g., number of running threads is 0) while not holding the mutex that guards the state you're waiting to change.
3. Allowing preemption - I've never seen an O/S mechanism to directly support this. You need locks that can be canceled - database do this.
4. Removing circular-wait - this is usually how deadlock is avoided. The classic method is by controlling the order locks are grabbed. When grabbing more than one lock always grab them in the same order. However, best is to not hold more than one lock at a time using finer grained locks. The answer from Rachid K. does this. The class mutex protects the stop flag and a new lock in the form of a barrier protects its own state.

Another choice is to not use the class mutex at all for the stop flag and use Burak Serdar's suggestion of an atomic. There the cpu is doing the locking to ensure consistent access. Atomics also can't be part of a circular-wait because the locking/unlocking is all hidden from your code.

Or you can keep the single class lock and implement your own barrier to remove the wait-for condition. The class mutex can protect both the stop flag and an active thread count. The condition variable allows you to wait while not holding the class mutex yet its still used to protect the class state when written and read. If you're using a pthread_condition, when you call pthread_cond_wait() you supply both the condition variable and the mutex you're holding - the o/s will release the mutex before putting your thread to sleep and reacquire it when it's woken back up. Other threads can acquire the class lock, modify the active thread count, call pthread_cond_signal to wake up the waiting thread and then release the class lock. The de-initialize code will wake up holding the lock again and recheck if the condition has been satisfied (i.e., the count is now zero).

FWIW: The way I handle this (when using pthreads) is an atomic stop flag and calling pthread_join() to wait for each thread to exit. No mutex's are directly involved, partly because my classes and threads are constructed to not require a class level lock on shutdown. I'm skipping over the details on how I get the threads to check the stop flag - that varies widely based on what the thread is for and may involve their own locks.

Regardless, I think that if you can, join is the way to go because it is simple. I don't know of any threading library in any language that doesn't support blocking on a thread until it exits. In unmanaged languages, if you can join, it's often required to so to avoid leaking resources. The join call does the per thread resource clean up. With pthreads, after you call pthread_detach() you can't join and the exiting thread then does its own clean up.

It is possible to use a barrier to set up a rendez-vous that all the threads reach before ending.
At the beginning of the mutual exclusion region a stop flag is checked/set. If the flag is set, the running thread releases the mutex to go out of the mutual exclusion region and calls pthread_barrier_wait(). At one moment all the threads will have reached the barrier (i.e. barrier counter drops to 0) and the last one will get the PTHREAD_BARRIER_SERIAL_THREAD return code after which it will do the cleanup of the data structures.
The latter supposes that the number of running threads is known at the time the barrier is initialized (count parameter passed to pthread_barrier_init()) and that the running threads regularly enter the mutual exclusion region to check the stop flag.