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

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

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)
    }
}