Concurent Programming with Threads

Each thread associated with a process has its own stack, registers, condition codes, stack pointer, program counter and thread ID (TID). A thread context switch is faster than a process context switch.

Reaping Terminated Threads

pthread_join (pthread_t tid, void **thread_return);
The pthread_join function blocks until thread tid terminates and then reaps any memory resources held by the terminated thread.

Joinable Vs Detached Thread

A thread is either joinable or detached. A joinable thread can be reaped and killed by other threads. Its memory resources are NOT freed until it is reaped by another thread. A detached thread cannot be reaped or killed by other threads. Its memory resources are freed automatically by the system when it terminates. By default, threads are created joinable. Threads can detach themselves by call pthread_detach(pthread_self()).

Protecting Shared Variables with Semaphores

A semaphore, s, is a global variable with a nonnegative values can only be manipulated by two special operations, called P (to test) and V (increment):

• P(s): while (s <= 0) ; s-- ;
• V(s): s++;

A binary semaphore is often called mutex, which provides mutual exclusive access to the shared data.

Signaling with Semaphores

A classic example is producer-consumer interaction, which is common in real systems. For the producer-consumer interaction, we typically need two semaphores, called full and empty.

Producer:

P(empty);
write buffer;
V(full)

Consumer:

P(full)
read buffer;
V(empty)

-------------------------------------------------------------
Synchronizing Threads with Mutex and Condition Variables

Mutex is used to protect sharing and like a binary semaphore. And condition variables are used for signaling. To understand condition variables, we will take pthread as an example.

pthread_cond_init(pthread_cond_t * cond, pthread_condattr_t *attr);
pthread_cond_wait(pthread_cond_t * cond, pthread_mutex_t *mutex);
pthread_cond_signal(pthread_cond_t * cond);

Pthreads require that a mutex variable be associated with the condition variable cond, and that a call to pthread_cond_wait must always be protected by that mutex:

pthread_mutex_lock(&mutex);
pthread_cond_wait(&cond, &mutex);
pthread_mutex_unlock(&mutex);

some thread later indicates that the condition associated with cond has become true by making a call pthread_cond_signal(&cond), which wakes up exactly one of the waiting threads.

Reentrant Functions: DO NOT reference any shared data when they are called by multiple threads and thus they require no synchronization operations.

Other synchronization errors

Races: A race occurs when the correctness of a program depends on one thread reaching point x in its control flow before another thread reaches point y. A golden rule is that threaded programs must work correctly for any feasible trajectory in the progress graph.

Deadlock: a collection of threads are blocked, waiting for a condition that will never be true.

Synchonization Variables

From Threads Primer

Mutex, Semaphore, Condition variable

Mutex: Mutual exclusion lock is the simplest and most primitive synchronization variable. The first thread that locks the mutex gets ownership, and any subsequent attempts to lock it will fail, causing the calling thread to go to sleep.

Using Mutexes in the Different Libraries:

POSIX
pthread_mutex_lock(m)
...
pthread_mutex_unlock(m)

Win32
WaitForSingleObject(m)
...
ReleaseMutex(m)

Semaphore: A counting semaphore is a variable that you can increment arbitrarily high, but decrement only to zero. If the semaphore is greater than zero, the operation succeeds; if not, then the calling thread must go to sleep until a different thread increments it. A semaphore is useful for working with "train-like" objects, that is, objects where what you care about is whether there are either zero objects or more than zero. A semaphore is perfect for situations where you want to count things and have threads sleep when some limit is hit. A typical example is producer/consumer application.

Condition variable: The programmer is responsible for locking and unlocking the mutex, testing and changing the condition, and waking up sleepers. Otherwise, it is exactly like a semaphore. It works like this: A thread obtains a mutex and tests the condition under the mutex's protection. No other thread should alther any aspect of the condition without holding the mutex. If the condition is ture, your thread completes its task, relaesing the mutex when appropriate. If the condition is NOT true, the mutex is released for you, and your thread goes to sleep on the condition variable.

Synchronization Issues

A test and set instruction tests (or just loads into a register) a word from memory and sets it to some value (typically 1), all in one instruction with no possibility of anything happening in between the two halves. Because threads can be preempted at any time, between any two instructions. If the value target word was 0, then it gets set to 1 and you are considered to have ownership of the lock. If it already was 1, then it gets set to 1 and you don't have ownership. All synchronization is based upon the existance of this instruction!

--------------------
Critical Section||
--------------------

A critical section is a section of code that must be allowed to complete atomically with no interruption that affects its completion. We create critical sections by locking a lock, manipulating the data, then releasing the lock afterwards. The thread that is executing in the critical section may even lose its processor, but no other thread may enter the critical section.

Critical sections are typically made as short as possible and ofter carefully optimized because they can sigificantly affect the concurrency of the program.

Lock your shared data: All shared data must be protected by locks. Data structures which are passed to other threads and global variables are the obvious examples. All data structures that can be accessed by multiple threads are included. Static variables are included.

---------------------------------------

Protecting Shared Resources

----------------------
Mutual Exclusion||
----------------------

Enter mutal exclusion. Mutual exclusion is the method of serializing access to shared resources. You do not want a thread to be modifying a variable that is already in the process of being modified by another thread! Another scenario would be a dirty read where the value is in the process of being updated and another thread reads an old value.

Mutual exclusion (most often referred to as mutex) allows the programmer to "attach" locks to resources. If a thread wishes to modify or read a value from a shared resource, the thread must first gain the lock. Once it has the lock it may do what it wants with the shared resource while it has the lock because no other thread should have access to that variable. Once the thread finishes using the shared resource, it unlocks the mutex, which allows other threads to access the resource.

The code between the lock and unlock calls to the mutex, is referred to as the critical section. Minimizing time spent in the critical section allows for greater concurrency because it reduces the time other threads must wait to gain the lock. Therefore, it is important for a thread programmer to minimize critical sections.

-----------------------------
Problems with Mutexes ||
-----------------------------

1. Deadlock
2. Race
3. Priority inversion

An important problem associated with mutexes is the possibility of deadlock. A program can deadlock if two (or more) threads have stopped execution or are spinning permanently. The simplest deadlock situation: thread 1 locks lock A, thread 2 locks lock B, thread 1 wants lock B and thread 2 wants lock A. Instant deadlock. You can prevent deadlock by making sure threads acquire locks in an agreed order (lock ordering). Deadlock can also happen if threads do not unlock mutexes properly.

Race conditions occur when multiple threads share data and at least one of the threads accesses the data without going through a defined synchronization mechanism (Nichols 203). This could result in erroneous results even in an inconsistent manner which makes race conditions particularly difficult to debug. Library calls outside of your program's control are common culprits. Make sure you take steps within your program to enforce serial access to shared file descriptors and other external resources.

Another problem with mutexes is that contention for a mutex can lead to priority inversion. A higher priority thread can wait behind a lower priority thread if the lower priority thread holds a lock for which the higher priority thread is waiting. This can be eliminated/reduced by limiting the number of shared mutexes between different priority threads.

----------------
Semaphores||
----------------

Semaphores are another type of synchronization primitive that come in two flavors: binary and counting. Binary semaphores act much like mutexes, while counting semaphores can behave as recursive mutexes. Counting semaphores can be initialized to any arbitrary value which should depend on how many resources you have available for that particular shared data. Many threads can obtain the lock simultaneously until the limit is reached. This is referred to as lock depth.


References:
1. Threads Primer
2. http://vergil.chemistry.gatech.edu/resources/programming/threads.html

Multithread Programming Primer