Difference between outcome of using mutex/spinlock/semaphore in this deadlock situation?

Question

I'm not sure if my answers to the following exercise is correct:

Suppose the program is run with two threads. Further suppose that the following sequence of events occurs:

   Time  Thread 0                  Thread 1
   0     pthread_mutex_lock(&mut0) pthread_mutex_lock(&mut1)
   1     pthread_mutex_lock(&mut1) pthread_mutex_lock(&mut0)

b. Would this be a problem if the program used busy-waiting (with two flag variables) instead of mutexes?

c. Would this be a problem if the program used semaphores instead of mutexes?

Are the outcomes for this not the exact same in that they'd result in a deadlock? For b) if we use a spinlock, the outcome would look something like this, right? (Let flag0 = flag1 = 1)

    Time    Thread 0              Thread 1
    0       flag0--;              flag1--;
    1       while(flag1 == 0);    while(flag2 == 0);

For c) I'm assuming they're referring to a binary semaphore, which is effectively the same thing as a mutex so it'd also result in deadlock.

Is there a mistake in my reasoning? My answers seem suspiciously simple but I don't see how spinlock/semaphores would change anything

Answer 1

Thread 1 locks a mutex - the semantics is 1. that nobody will be able to lock that mutex successfully until thread 1 unlocks the mutex, and 2. That thread 1 won’t be able to lock the mutex if some other thread has locked it and hasn’t unlocked it.

If you want to reproduce that semantics, no matter how, then you will have a deadlock. It is unavoidable with the semantics.

The best you can do is to have a function like “trylock” which either performs an uncontested lock and returns true, or detects that the mutex is locked and returns false. You can avoid the deadlock this way, but you don’t have the same semantics. One of the threads has to give up and unlock the first mutex it locked after carefully undoing whatever it did after the first lock.

So busy waiting or using a semaphore may avoid the deadlock (I didn’t even check), but they can’t solve your programming problem.