=========
Deadlocks
=========

* A deadlock occurs when two or more threads are each waiting on events (e.g. semaphores, resources, etc.) that only the other thread can release. A deadlock can formally be defined as follows: A set of processes is deadlocked if each process in the set is waiting for an event that only another process in the set can cause. Tanebaum/Woodhull
* Always take semaphores in the same order - If multiple semaphores are used by multiple threads, then they must be taken in the same order
* Always release in the opposite order taken - If you take SEMA, then SEMB, you release SEMB then SEMA
* Lots of Semaphores is a bad thing 
    
    * One for all data in the system 
    * One per major data structure or group 
    * One per type of data processing

What does a semaphore mean in a system?
========================================

A semaphore means whatever the designer says it means.

* When a designer adds a semaphore to a system she is really adding a 
  new set of programming rules.
* If we have a data structure D and add a semaphore SD to protect it,  
  we also need to add the programming rules for using the semaphore. In this case:
  Any code that reads or writes to data structure D shall first acquire semaphore SD.
* Only with this rule does the semaphore become meaningful and only when the rule is 
  followed does the data structure get protected.

Semaphore Deadlock examples
===========================

.. code-block:: c

    AcquireDataThread()
    {
       ...
       while (TRUE) 
       {
           newData = GetDataItem()
           PendSemaphore(pDatabaseSem)
           AddDatabase(newData)
           PostSemaphore(pDatabaseSem)  
       }
    }
    
    SendDataThread()
    {
       while(TRUE) 
       {
           PendSemaphore(pSerialPortSem)
           PendSemaphore(pDatabaseSem)
           if (new data in database) 
           {
               SendData()
           }
           PostSemaphore(pDatabaseSem)
           PostSemaphore(pSerialPortSem)
       }
    }

    AcquireThread()
    {  
       while (TRUE) 
       {
           newData = GetDataItem()
           PendSemaphore(pDatabaseSem)
           err = AddDatabase(newData)  // << A
           if (err) 
           {
              PendSemaphore(pSerialPortSem)
              SendMessage("Database full error")
              PostSemaphore(pSerialPortSem)             
           }
           PostSemaphore(pDatabaseSem)  
       }
    }
 
    SendThread()
    {  
       while(TRUE) 
       {
           PendSemaphore(pDatabaseSem)  // << B
           PendSemaphore(pSerialPortSem)
           if (new data in database) 
           {
               SendData()
           }
           PostSemaphore(pSerialPortSem)
           PostSemaphore(pDatabaseSem)
       }
    }


Threads at point A & B
======================

===============  ====================   ====================    ================    =================
Thread           Acquire Thread owns    Acquire Thread needs    Send Thread owns    Send Thread needs
ppDatabaseSem           X                                                                  X
ppSerialPortSem                                X                     X
===============  ====================   ====================    ================    =================

Semaphore Deadlock example solution
=========================================

.. code-block:: c

    AcquireThread() 
    { 
        //...
        while (TRUE) 
        { 
            newData = GetDataItem() 
            PendSemaphore(pDatabaseSem) 
            err = AddDatabase(newData) 
            if (err) 
            {
                PendSemaphore(pSerialPortSem)
                SendMessage("Database full error") 
            } 
            PostSemaphore(pSerialPortSem)
            PostSemaphore(pDatabaseSem)
    }
    
    SendThread() 
    { 
        //...
        while(TRUE) 
        {
            PendSemaphore(pDatabaseSem) 
            PendSemaphore(pSerialPortSem) 
            if (new data in database) 
            {
                SendData()
            }
            PostSemaphore(pSerialPortSem) 
            PostSemaphore(pDatabaseSem)
        }
    }