1

This expands on "Deadlock in Single threaded application" on StackOverflow.

That question was not really conclusive and I think it better belongs here.

By the definition of a deadlock, is it technically possible to produce a deadlock by using just a single thread?

This is the definition of a deadlock according to Wikipedia:

A deadlock situation on a resource can arise if and only if all of the following conditions hold simultaneously in a system:

  1. Mutual exclusion: At least one resource must be held in a non-shareable mode. Otherwise, the processes would not be prevented from using the resource when necessary. Only one process can use the resource at any given instant of time.

  2. Hold and wait or resource holding: a process is currently holding at least one resource and requesting additional resources which are being held by other processes.

  3. No preemption: a resource can be released only voluntarily by the process holding it.
  4. Circular wait: each process must be waiting for a resource which is being held by another process, which in turn is waiting for the first process to release the resource.

I tried to create a deadlock with one thread in C#, where condition 4 may not literally be met, but it still looks like a deadlock to me. I am not posting this code since I know it would be off-topic for this site.

Improve this question
5
  • 3
    By creating your own process model you are effectively creating your own threading system. You already have multiple "threads". Commented Dec 2, 2018 at 21:30
  • @candied_orange is this really a process model? I could have named the class Process ResourceUser and it may not have occurred to you. Commented Dec 2, 2018 at 21:46
  • 3
    Regardless of what you call it it's the same problem. How do you think multiple threads are created on single core computers? Your just doing it yourself. Be advised that doing this isn't simple. Commented Dec 2, 2018 at 21:56
  • 1
    If your point is "hey look, deadlock is possible without explicitly asking for a new thread" then yes I totally agree. This is why even in single thread code I free resources in the opposite order they were allocated. Because I have no idea how weird things will get outside the bounds of my class. Commented Dec 2, 2018 at 22:17
  • 1
    Reviewing your code for deadlocks is off-topic, but I'll be happy to write you an answer for the top half and what's in the title. Commented Dec 2, 2018 at 22:40

3 Answers 3

Reset to default
4

"Deadlock" just means you have two actions that are each locking each other so that neither can proceed.

Obviously in order to have two things running at the same time you would normally need more than one "thread".

But a thread is just an abstract layer over the actual CPU. You can easily* write you own abstraction layer and create deadlocks in it without using the language's thread objects.

*not so easily if you want it to work well

lets do some pseudo code

List<string> t1; //instruction set one List<string> t2; //instruction set two public void Run() { while(1==1) { //attempt to run instructions one at a time, but timeout of they are 'locked' if(Execute(t1[i], timeout:1000)) { i++;} if(Execute(t2[j], timeout:1000)) { j++;} } }

Now if I have some t1 instructions create a lock A and then B but also have t2 attempt to lock B and then A. I will have a deadlock with no System.Threads

Improve this answer
1
  • Two or more: It probably almost never happens in practice, but you could, in theory, have three threads in a deadlock (A waiting for B while B waits for C while C waits for A), or even more. Commented Dec 3, 2018 at 2:38
5

Wikipedia's definition of a deadlock requires that there be multiple processes (or threads) holding the right set of resources for one to occur. This is a good base for a general discussion, but it overlooks the practical reality that some implementations of mutexes behave differently in the face of contention and don't care about that technicality.

The majority of operating systems that support threading conform to POSIX, which defines defines three types of mutexes:

First is the normal mutex, which is the classic implementation that will wait for an unlock no matter who locked it:

Mutex m(NORMAL) m.lock() m.lock()

The second call to lock() will wait on the thread that locked m to unlock it. Since it's the same thread, that will never happen and the thread will have effectively deadlocked itself. This is how to produce a deadlock within one thread, making what you ask about technically possible. Because of this hazard, development guidelines tend to recommend not using normal mutexes.

Second is the error-checking mutex, which averts self-deadlock by treating attempted re-locking as an error and returning control to the thread. The thread's code can decide to proceed if a second attempt is okay, but there's the danger that what made the second call could also call unlock() and leave critical part vulnerable to alteration by another thread. (That would be avoided by not unlocking if the lock failed because the mutex was already locked.)

Third is the recursive mutex, which keeps count of the number of times it was locked by the same thread and requires a corresponding number of unlocks before the mutex is released. That takes care of the multuple lock/unlock problem.

The POSIX documentation has a table of the behaviors of all three, and you'll notice that the behavior for relocking a normal mutex is explicitly that the thread should deadlock.

Improve this answer
1

Not in any interesting sense. There are an infinity of ways of writing code that doesn't halt. Deadlocks are a subset of those with some particularly interesting and pernicious effects, so they're worth distinguishing.

I don't know C#, but for your particular example, it looks like you have simply written an obfuscated infinitely recursive function. That is, it's really just a complicated way of calling

wait_untill_flag_is_true(boolean flag) { if (!flag) { wait_untill_flag_is_true(false); } } main() { wait_until_flag_is_true(false); }

This will run until the stack fills up. The recursive call is camouflaged behind the call to 'Invoke'.

Note that when executed on a single thread your program is completely deterministic and will always have the same result. The reason that deadlock is more subtle and interesting than other forms of non-halting code is that it can be stochastic. Sometimes the code may run correctly, and other times it will hang, depending on how the OS scheduled the execution of the threads.

As I say, I don't know C#, so it's possible that the call to 'Invoke' is providing some sort of multi-threading magic behind the scenes, in which case the comment by @candied_orange cis on target, and you've simply invented your own thread management API.

Improve this answer
6
  • That call to Invoke will just call the event handlers registered with += synchronously. No additional threads are involved in any way in my code example. Commented Dec 2, 2018 at 23:08
  • 1
    @bitbonk then you're stuck with my analysis that you've just gone the long way around to write an infinitely recursive function. Commented Dec 2, 2018 at 23:10
  • That makes sense. But, isn't a thread scheduler just a "obfuscated infinitely recursive function" too (or some sort of loop)? Just on a much lower level? Threads work on a single core CPU too. This seems to be the main point Ewan is making in his answer softwareengineering.stackexchange.com/a/382353/11332 Commented Dec 3, 2018 at 8:39
  • @bitbonk isn't a thread scheduler just a "obfuscated infinitely recursive function" By no means! The thread scheduler is starting, stoping, pausing, and switching thread which thread is running, depending on its algorithm for making sure that each thread gets a fair shot at the CPU. If your example code were running on multiple threads you'd find that sometimes it would hang because your third thread doesn't free the shared resource correctly, but sometime it might run correctly because the 1,2,4, and 5 threads might finish before the 3rd thread is ever run. so the deadlock wouldn't happen. Commented Dec 3, 2018 at 18:36
  • There are also deterministic deadlocks, e.g. simply by forgetting to release a shared resource. I would be able to emulate/reenact that with high level code without using more than one thread. Some sort of scheduler class would retry to call the the next instance of a process class in line in an endless loop. It can’t start it because the previous one never raised the finished event. Commented Dec 3, 2018 at 19:54

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.