This
Web Page Created with PageBreeze
Free Website
Builder
|
Writing multithreaded software is much different than
developing single threaded program because your software must be able to
manage shared access to its memory space. This might not sound too
challenging, but threads cause the complexity of your software to increase
very quickly. Before embarking on a multithreaded adventure you should
consider alternatives. Design
your software with synchronization in mind. Remember that your application
will require more that just C and C++ types and functions written using
object-oriented techniques. Problems with deadlocks and race conditions
are easy to run into and hard to find. You must be very careful not to
create a big mess. I worked for a company that had created such complexity
through the use of threads that no one wanted to touch certain parts of
the system because you could not tell what would happen.
When thinking about synchronization try using
charts and UML diagrams to get a clear picture of what your doing.
Resource | Thread_A | Thread_B ------------------------------------------------ Resource1 | Yes | No Resource2 | No | No Resource3 | Yes | Yes ------------------------------------------------- Because two of these threads call Resource3 you must be prepared to handle race conditions. Mutexes could be explained using the same type of chart: Resource | Thread_A | Thread_B ----------------------------------------- Mutex1 | Yes | Yes Mutex2 | Yes | No Mutex3 | Yes | Yes ------------------------------------------ Since Mutex1 and Mutex3 are used by Thread_A and Thread_B we must watch the ordering of our mutex locking. Deadlocks can easily occur by not knowing about how another thread is using resources. Having some way to view how your program threads are interacting with each other is important, especially when your design requires threads to intersect on different mutexes. Deadlocks are the result of one or more threads creating a circular sequence of locks. These sequences are not always recognized because, they could be several layers deep into the system and branching into many different logic paths. It's also necessary to build debugging mechanisms
into your software that catches abnormal behavior. Like the deadlocks and
race conditions. You'll need a function that wakes up every so many
seconds and checks the system's state. This could be a thread or a timer
interrupt that acts something like the scheduler does when it checks the
run-queue. Suggesting that a procedure be created that's something like a watchdog timer or scheduler may seem like a bit much, but I'm in the habit of doing this because it's something like a guard for your application that keeps you on track once you have a stable system. Complex systems are worth the extra effort, especially when someone's life could be on the line. An example of this sort of mechanism would be a C++ class type, created to track our mutexes states across a process. We could create our C++ class object to detect deadlocks at run time. Deadlocks can occur without locking the whole system so, parts of a process may continue to operate, handling request and so on. You could have a portion of your system locked until some condition in the program code branches to the locked resource, this could take days to occur in a large system with a complex business environment. After you design your software there will still be
things that you have to implement along the way because every single thing
can't be anticipated. Designing software is something like a business
plan. You have to check for and report on variances along the way. That
being said let's consider how a threaded application component will
operate. When programming in C++ on Unix you'll have to know C programming also, and be able to work with both programming languages. You'll need to use the proper header file for C and C++. Use extern "C" { header file... } around your C headers because C++ name mangling technique will cause your C function names to be mangled. So, do this: extern "C" { #include ... } I don't cover the header files to include here you
should have a manual on in-depth Unix programming to help you with this
article. A Mutex is a system object used to manage access to critical
sections of code. Don't mistaken mutexes for interrupt disabling.
Interrupts are used for hardware devices and software hook into these
interrupts to handle hardware request. When you disable interrupts you
stop the operating system itself from interrupting the code between the
disable and enable interrupts statements. Mutexes just stops other threads
from entering that section of code without a lock on the mutex. When a
thread need to perform some operation atomically they use the atomic data
types and functions provided by the Unix systems implementation. When
using threads it is extra important to understand how your datatypes are
stored and handled by the system so, pay careful attention to this factor.
The Mutex C++ class you might implement for debugging could look like
this:
class Mutex { public: Mutex(bool run_analyzer=false); ~Mutex(); void Lock(); void Unlock(); private: pthread_mutex_t mutex; pthread_t tid, locked_by,
analyzer_tid; static pthread_mutex m_lock; static vector sync_info is_locked; static vector sync_info is_waiting; static int analyzer; static void* scan_mutex_locks(void* arg); static vector<sync_info>::iterator thread_is_waiting(vector<sync_info>::iterator&); }; The class Mutex constructor and destructor should not do too much because we don't want to be to much overhead. I used two functions to replace the POSIX mutex locking and unlocking function, they are Unlock() and Lock() these encapsulate the mutex object and POSIX API functions giving the whole process one central point of access these POSIX functions. Our private data is only used by the class implementation itself. I have a mutex class member used for the call to pthread_mutex_lock() and pthread_mutex_unlock(). The static member vectors are declared without the brackets because this article would not save while they were present. These two vectors are used to hold the locked and waiting mutexes, and thus their names is_locked and is_waiting. They both hold sync_info structures. sync_info contains the thread's TID and the address of the Mutex object the thread used to access the mutex. Both vectors are static so, they will only be created once no matter how many Mutex objects are created and will have access to every mutex used in the process. Because,
class Mutex is where the functionality for the actual mutex monitoring
will be, any synchronization that is needed for this class must be
independent of the debugging features implemented for the rest of the
software. Class Mutex will contain it's own mutex object for handling
critical sections within its class member functions but, will not
participate in the mutex tracking itself. Also, we must take into account
the libraries that we use are probably not thread-safe, for example the
STL vectors will cause race conditions if not used with caution. This is
what the m_lock mutex member is used for. The m_lock mutex is a static
member because it must protect critical sections in all objects across the
process. This causes a lot of blocking in the program when the scanning is
in progress but, in a real application the analyzer thread will not run
all the time. In the code shown here the Mutex class will be used all the
time. There will be no switches included that allows the program to bypass
class Mutexes functionality.
You might decide to break some of the functionality
into member functions. This is what I decided to do when I created
thread_is_waiting(vector sync_info ::iterator& it). This function is
used to search for an item in the is_waiting vector. It simplify things
for me a bit. The real task of finding deadlocks is left to the
scan_mutex_locks() function. This function has a recursive algorithm:
Start: 1) Get next mutex object from the list. 2) Is it locked? 2.1) If yes, go to step 3. 2.2) If no, go to step 1. 3) Find the thread that locked it. 4) Is the thread that locked the mutex in step 3 waiting on a mutex? 4.1) If yes, go to step 5 4.2) If no, go to step 1 5) Get the mutex object the thread in step 4 is waiting on. 6) Is it the same mutex from step 1? 6.1) If yes, go to Deadlock. 6.2) If no, go to step 3. Deadlock: Do something to handle the deadlock. End. First we take a mutex from the list of locked mutexes. We already know that the mutex is locked because, it is in the is_locked vector of mutexes so, we go to the next step. The next step is to find out who locked it, this information is in the locked_by member of the Mutex class. The locked_by member is the pthread_t identifier of the thread that locked the mutex. A deadlock would be in effect if the thread that has the mutex is waiting on the same mutex or another mutex that in turn is waiting on the mutex we just referenced on the list of locked mutexes. For example, if the three conditions below are true a dealock is in effect: 1. Thread_A locked Mutex1 and waits on Mutex2 2. Thread_B locked Mutex2 and waits on Mutex3 3. Thread_C locked Mutex3 and waits on Mutex1 The deadlock in the above senerio occurs when Thread_C waits on Mutex1. Since Mutex1 is locked by Thread_A, Thread_C waits on Thread_A and Thread_A waits indirectly on Thread_C, forming a circular lock or deadlock. So, our next task is to see if that is the case. If it is we must handle the deadlock otherwise, we go back and do the previous steps, starting at step 3. The code used to implement the algorithm just examined is shown below in the next step. The rest of the class Mutex code will be posted on my website at www.engineerjames.com. Although it is possible to check for mutex
deadlocks using this technique, the deadlock must be in effect before this
thread is able to detect it. So, this is a run-time strategy for tracking
deadlocks not a design strategy.
void* Mutex::scan_mutex_locks(void *args) { while(true) { if(!pthread_mutex_try_lock(&m_lock) { deadlock=false; for(vector sync_info ::iterator it=is_locked.begin(); it!=is_locked.end(); it++)
/* Get next mutex from the list of locked_mutexes */
{ vector sync_info ::iterator current_item=it; long count=is_waiting.size(); for(vector sync_info ::iterator result=is_waiting.begin();;) { /* find out if the thread that has it locked is waitng on another thread */ result=thread_is_waiting(current_item); if(result==is_waiting.end() or !count) break; /* See if thread is waiting on itself and if it is, set the deadlock flag otherwise update
count and current_item and continue
doing
the
previous steps on the current_item. */ if(result->m->locked_by==it->m->locked_by) { deadlock=true; break; } current_item=result; count--; } if(deadlock) break; } pthread_mutex_unlock(&m_lock); } } } /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * /*Name: void Mutex::Unlock(pthread_t tid) /*Args: pthread_t tid, is the identifier of the thread that is unlocking /*the mutex. /*Descr: Unlock the mutex encapsulated inside this object and take the /*Mutex object off he is locked list. /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ void Mutex::Unlock(pthread_t tid) { pthread_mutex_lock(&m_lock); if(!pthread_equal(locked_by,tid)) { pthread_mutex_unlock(&m_lock); return; <br> } <br> sync_infosi(tid,this);<br> for(vectorsync_info::iteratorit=is_locked.begin();it!=is_locked.end();it++) if(*it==si) { Mutex::islocked.erase(it); break; } locked_by=0; pthread_mutex_unlock(&mutex); pthread_mutex_unlock(&m_lock); } The implementation of function that locks the mutex is shown in the next step. The function name is void Mutex::Lock(). /* * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
/*Name: void Mutex::Lock() /*Descr: Lock the mutex encapsulated within this object and put the /*Mutex object on the is_locked list after removing it from the /*is_waiting list. /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ void Mutex::Lock() { pushback_waiting_thread(); /* Add waiting thread to the is_waiting list */ pthread_thread_mutex_lock(&mutex); pthread_mutex_lock(&m_lock); tid=pthread_self(); locked_by=tid; sync_info si(tid,this); /* Find the thread on the is_waiting list that just locked the mutex and remove it */<br> for(vectorsync_info::iteratorit=Mutex::is_waiting.begin();it!=Mutex::is_waiting.end();it++) { if(si==*it) { Mutex::is_waiting.erase(it); break; } } /* Add the mutex that was just locked to the is_locked list. */ Mutex::is_locked.push_back(si); pthread_mutex_unlock(&m_lock); } /* Create some threads that use the Mutex class and try stepping through the thread that scans the mutexes. */ You can try the code at your own
risk. I take no responsiblity for any problems caused by using this code.
If you have any questions or comments feel free to send me an e-mail
at
jimsmith@engineerjames.com .
|
This
Web Page Created with PageBreeze
Free Website
Builder