Deadlock in Single threaded application

Question

Can a single threaded application have a deadlock? If so, please provide an example.

Citriculture

Answer 1

Yes, a single-threaded application can deadlock if you have locks that are not re-entrant and a thread attempts to reacquire a lock that it owns already (like via a recursive call).

Edit: I see that the post has been tagged "Java"; I don't know if that was an update or if I missed it before, but in any case locks in Java ARE re-entrant, so you won't be able to deadlock a single-threaded application in this manner.

Mariomariology

Normally, that will result in some kind of error indicating that the thread already owns the lock. – Crucible

Wouldn't that depend on the platform? – Mariomariology

It could possibly lock up, but by definition of the term, this would not be deadlock. Admittedly I would probably call it deadlock for lack of a better word :) – Crucible

"...a single-threaded application can deadlock if you have threads..." -- sounds like a contradiction in terms. Single-threaded application, by definition, has no threads. – Kerley

@atzz: first of all, a single-threaded application has ONE thread, not none. Second of all, my post is clearly referring to whether threads can reacquire locks in the particular platform. Your downvote is ill-informed. – Mariomariology

Answer 2

Yes, if the application shares resources with another application it can be deadlocked.

Salvia

Good point. Whether this was the intended answer depends on the exact original wording, but as it is written here, that would be the best answer. – Crucible

Answer 3

It depends a little on how you interpret the question. If resources that are shared with other applications are involved, then yes. Without shared resources, no.

A deadlock is a situation wherein two or more competing actions are waiting for the other to finish, and thus neither ever does.

With a single thread, there is only one action, which can't compete with itself.

From Wikipedia:

Necessary conditions

There are four necessary and sufficient conditions for a deadlock to occur, known as the Coffman conditions from their first description in a 1971 article by E. G. Coffman.

1. Mutual exclusion condition: a resource that cannot be used by more than one process at a time
2. Hold and wait condition: processes already holding resources may request new resources
3. No preemption condition: No resource can be forcibly removed from a process holding it, resources can be released only by the explicit action of the process
4. Circular wait condition: two or more processes form a circular chain where each process waits for a resource that the next process in the chain holds

By this definition, two processes are required to consitute a deadlock.

Crucible

You do mean "in Java", right? Otherwise, MSDN disagrees with you. msdn.microsoft.com/en-us/library/ms792855.aspx – Mariomariology

I mean in Computer Science in general. – Crucible

And that link describes a scenario in which it can happen - do you disagree with it? – Mariomariology

@danben: I disagree in the sense that the case described shouldn't be called deadlock (by the quoted definition). As such, not mentioning the case is at the very least defendable, especially if there is a much simpler example of deadlock occurring. – Crucible

Well, if you insist on using that Wikipedia article as the authority on deadlocking, then you would also have to say that a single multithreaded Java application can never deadlock, because Wikipedia claims deadlock only occurs between two processes, and threads are not processes. At some point, it might be prudent to start questioning your definitions. – Mariomariology

Especially if they were authored in 1971. – Mariomariology

@danben: a thread is a process. The term process is used very loosely here, not as some kind of platform specific concept that you are referring to. – Crucible

Then how do you know which definitions should be interpreted strictly (deadlock) and which should be interpreted loosely (thread)? – Mariomariology

@danben: You're mixing things up again. The concept of a thread is a pretty strictly defined (albeit somewhat platform specific). I said the term process was used loosely in the definition of deadlock, from which you draw an invalid conclusion. Just because a horse is an animal, doesn't mean every animal is a horse :P – Crucible

A single thread can compete with itself. All that is necessary is a sequence of operations that contends for the same lock twice without releasing it, which is easy to accomplish if you have reentrant code (e.g. coroutines or async/await) and a sequence of calls that is nondeterministic or difficult to reason about. Deadlock is a phenomenon that occurs when performing tasks concurrently, regardless of whether you're actually utilizing parallelism or doing everything on a single thread. – Kirakiran

Answer 4

Thread A acquires resource 1, and tries to reacquire resource 1. Self looping situation.

Thread acquires lock1 -> run in the critical section -> tries to acquire lock1 -> infinite wait == self-deadlock. To solve this, you would need recursive locks.

Parasol

Answer 5

Yes, single threaded event-driven (non-blocking) app definitely can deadlock. Even without any OS synchronization primitives like mutexes and even without OS at all. In FSM(finite state machine) design deadlock is common error.

Suppose You have a serial device that can only be accessed by write(COMMAND) then read(RESP) pattern. So to access it concurrently You need some serialization technique. The simplest way is a queue. Here is a simplest implementation of such queue in Javascript:

function SharedResource() {
    var self = {
        queue_: [],
        
        acquire: function(on_sharedResource_ready) {
            var n = self.queue_.push(on_sharedResource_ready);
            if(n==1){ // first task
                on_sharedResource_ready();
            }
        },
    
        release: function() {
            if(self.queue_.length >= 1) {
                // Pop current task
                self.queue_.shift();
                
                // Exec the next task
                var next = self.queue_[0];
                if(next) {
                    next();
                }
            }else{
                throw 'SharedResource::release(): BUG - queue is empty';
            }
        },
    };
    
    return self;
}

We can use it in button_click event for example:

var serialPort1 = SharedResource();
var serialPort2 = SharedResource();

function button1_on_click(){
    log("button1_on_click(): Acquiring serial port 1");
    serialPort1.acquire(function(){
        log("button1 Serial port 1 acquired");
        setTimeout(function(){
            log("button1: Acquiring serial port 2");
            serialPort2.acquire(function(){
                log("button1 Serial port 2 acquired");
                // Simulate long time work with a ports
                setTimeout(on_work_with_serial_port_done, 2000);
            });
        }, 1000);
    });
    
    function on_work_with_serial_port_done(){
        log("button1 Releasing serial port 2");
        serialPort2.release();
        log("button1 Releasing serial port 1");
        serialPort1.release();
    }
}

function button2_on_click(){
    log("button2_on_click(): Acquiring serial port 2");
    serialPort2.acquire(function(){
        log("button2 Serial port 2 acquired");
        setTimeout(function(){
            log("button2: Acquiring serial port 1");
            serialPort1.acquire(function(){
                log("button2 Serial port 1 acquired");
                // Simulate long time work with a ports
                setTimeout(on_work_with_serial_port_done, 2000);
            });
        }, 1000);
    });
    
    function on_work_with_serial_port_done(){
        log("button2 Releasing serial port 1");
        serialPort1.release();
        log("button2 Releasing serial port 2");
        serialPort2.release();
    }
}

And the rest piece of code to bring it to work:

function getTime(){
    var today = new Date();
    var time = today.getHours() + ":" + today.getMinutes() + ":" + today.getSeconds();
    return time;
}

// simple logger
function log(text){
    var logdiv = document.getElementById('log');
    var br = document.createElement("br");
    var t = document.createTextNode(getTime()+ ": " + text);
    logdiv.appendChild(t);
    logdiv.appendChild(br);
}

// register event handlers
window.onload = function () {
    var btn1 = document.getElementById('button1');
    btn1.onclick = button1_on_click;
    
    var btn2 = document.getElementById('button2');
    btn2.onclick = button2_on_click;
};

<html><head><script src="deadlock.js"></script></head><body>
<input type="button" value="Do work1" id="button1">
<input type="button" value="Do work2" id="button2">
<div id="log"></div>
</body></html>

If we press button1 and after more than 1 second press button2 everything will work fine:

16:12:20: button1_on_click(): Acquiring serial port 1
16:12:20: button1 Serial port 1 acquired
16:12:21: button1: Acquiring serial port 2
16:12:21: button1 Serial port 2 acquired
16:12:21: button2_on_click(): Acquiring serial port 2
16:12:23: button1 Releasing serial port 2
16:12:23: button2 Serial port 2 acquired
16:12:23: button1 Releasing serial port 1
16:12:24: button2: Acquiring serial port 1
16:12:24: button2 Serial port 1 acquired
16:12:26: button2 Releasing serial port 1
16:12:26: button2 Releasing serial port 2

BUT if we press button1 then button2 quickly the app will deadlock and wont respond to button1 and button2 clicks anymore

16:14:28: button1_on_click(): Acquiring serial port 1
16:14:28: button1 Serial port 1 acquired
16:14:28: button2_on_click(): Acquiring serial port 2
16:14:28: button2 Serial port 2 acquired
16:14:29: button1: Acquiring serial port 2
16:14:29: button2: Acquiring serial port 1
16:14:41: button1_on_click(): Acquiring serial port 1
16:14:41: button2_on_click(): Acquiring serial port 2
16:14:41: button1_on_click(): Acquiring serial port 1
16:14:42: button2_on_click(): Acquiring serial port 2
16:14:42: button1_on_click(): Acquiring serial port 1
16:14:42: button2_on_click(): Acquiring serial port 2
16:14:45: button2_on_click(): Acquiring serial port 2
16:14:45: button2_on_click(): Acquiring serial port 2
16:14:46: button1_on_click(): Acquiring serial port 1
16:14:46: button1_on_click(): Acquiring serial port 1
16:14:47: button1_on_click(): Acquiring serial port 1

Of course our app still can process other events, eg button3. In multi-threaded app situation is exactly the same - when thread1 and thread2 deadlocked each other, thread3 can still do work.

Podium