Deadlock in Single threaded application

Can a single threaded application have a deadlock? 开发者_StackOverflowIf so, please provide an example.

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.

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

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.

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.

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.