About Me >>   Master's Degree >>   IT-600 - Operating Systems

SNHU - IT-600 - Operating Systems
Written by: Chris Bell - December, 2015

Operating Systems Deadlock Avoidance | Processes and Threads

Deadlock avoidance is important for TSI to configure so that their server can operate 24 hours per day, and so that customers can always access the website to make purchases during peak periods. Deadlocks happen when servers are busy processing multiple programs at the same time and when certain programs request the same threads. For example, two production employees start Job A and Job B that both require Tool 1 and Tool 2. Job A gets a hold of Tool 1 and requests Tool 2, however Job B already got a hold of Tool 2 and requests Tool 1. Both Job A and Job B are now in wait mode for another tool in which neither of them can get. That analogy relates to processes requesting threads to complete the entire process. Sometimes processes need the same threads that are never going to be available because neither process has all of the required threads to execute.

Luckily, there are algorithms that avoid deadlocks by initially waiting for all of the threads to be available before beginning the process. For example, Job A above wouldn't have grabbed Tool 1 until all of the necessary tools and parts were available, then it would grab all of them together. Another way to avoid the deadlock would be to grab the tools and parts one-by-one, but release them back if a duration of time has gone by. Perhaps Job A has held 3 of 4 tools needed for the job for 10 minutes, so the algorithm can now release them back to the shelf before the deadlock occurs. There are a few ways to solve the problem but some of the solutions create new problems as well.

Waiting for every necessary thread to be available before locking them in the mutex can be problematic because the amount of time is unknown and could actually be infinite. There might be one of five threads always being used by another process and never actually have all five available at the same time. As threads enter the mutex they are locked (pthread_mutex_lock()) and when they exit the mutex they are unlocked (pthread_mutex_unlock()). Once a thread is locked into a mutex it cannot be used elsewhere creating the opportunity for deadlocks. However, if the currently locked threads are in the mutex knowing that all threads are available then the process will finish, unlock, and make those threads available to other processes that need to be executed.

Holding and locking threads one-by-one for a predetermined amount of time will stop the deadlock from happening because those threads will be released if the rest aren't available and locked within that time period. Then the process of locking the needed threads can start over. QNX, a subsidiary of Black Berry says, "Only one thread may have the mutex locked at any given time. Threads attempting to lock an already locked mutex will block until the thread that owns the mutex unlocks it. When the thread unlocks the mutex, the highest-priority thread waiting to lock the mutex will unblock and become the new owner of the mutex. In this way, threads will sequence through a critical region in priority-order."

With the Hold and Wait deadlock avoidance in place, in the introduction example, Job A would have held Tool 1 and waited for Tool 2. Since Job B was already holding Tool 2 and requesting Tool 1 they would have gotten it to complete their job. Then Job A would request and hold all of their tools again until all of them are available.