Synchronization Primitives in Linux

For softwares to leverage multi — core processors, they need to be multi threaded. Multi threading not only enables using a system’s resources more effectively, it also facilitates better code organisation, modularity (break complex tasks into smaller, manageable units) and scalability.

Multi threaded process however introduces race condition where the shared resources between multiple threads are inaccurately updated leading to undefined behaviour or much worse category of Use After Free bugs. Producer-Consumer models also require synchronization in updating the shared resources consistently.

What are Synchronization Primitives?

Synchronization primitives, generally kernel objects, control the access to shared resources such that only a single thread can read/ write to shared data at a time.
Synchronization in a a multi threaded process can be achieved via signalling, locking, combination of both or atomic variables.

• Signalling of an event : Kernel objects like semaphores can be used for signalling of an event, which in turn is used to synchronise access to shared resources.
• Locking : Critical section of code can be protected from race conditions via locking it. Only the thread owning the lock can execute the critical section while multiple threads can contest to acquire the locks. This introduces mutual exclusiveness to the resources common to several threads.
• Combination of locking and signalling : While locks protect critical resources from race conditions, signalling might be required for coordinated operations among various threads based on occurrence of an event. Combination of both locks and signals are used often to protect and synchronise event based operations.
• Atomic Variables : atomic variables are guaranteed to get updated without being interrupted, complex behind the scene mechanism is handled by the kernel. Such variables are always consistently modified across multiple threads.

Let’s take a closer look at signalling and locking sync primitives.

Semaphores

Semaphores are non — negative, atomic values. It is basically a signalling mechanism (not a lock) through which synchronization can be achieved, if used appropriately. A thread can proceed with execution past the semaphore only if the it’s value is non negative.
wait function is used for decrementing the semaphore’s value and a negative value puts the thread to sleep, into a waiting queue.
signal function increments the value of semaphore and signals threads waiting for it to be taken up next for execution.
Ownership : None. A semaphore can’t be owned by a thread, it’s just a non — negative number.
State : A thread waiting on a semaphore goes to sleep i.e blocked state without consuming CPU cycles.

Sample code of semaphore as sync primitive for updating shared resource (here val) accurately in multi threaded process.

#include <iostream>
#include <pthread.h>
#include <semaphore.h>

using namespace std;

sem_t sem;

void* thrFunc(void *arg){
        int *val = (int*)arg;
        for(int i = 0; i<10000; i++){
                sem_wait(&sem);
                (*val)++;
                sem_post(&sem);
        }
        return NULL;
}

int main(){
        pthread_t t1, t2;
        int val = 0;
        sem_init(&sem, 0, 1); //initialize semaphore with value one
        pthread_create(&t1, NULL, thrFunc, (void*)&val);
        pthread_create(&t2, NULL, thrFunc, (void*)&val);
        pthread_join(t1, NULL);
        pthread_join(t2, NULL);
        cout<<"Value : "<< val <<"\n";
        return 0;
}

Here, val is the common resource shared by thread one and two. Absence of a synchronization primitive will lead to race condition causing it’s value to be updated incorrectly.
Semaphore is initialised with value one (sem_init(&sem, 0, 1)) which allows the first thread (decrements sem value to zero with sem_wait) to proceed with shared resource val’s incrimination. Thread two which starts in parallel has to wait for the semaphore value to be non-negative (via thread one’s sem_post). This results in access and updates to shared resource to be in a synchronous manner.

Mutex

Mutex are simple kernel objects that act as locks. It has only two states 0 or 1 which represents unlocked or locked respectively.
Ownership : Mutex has a notion of ownerships.
Before entering critical section of code shared by multiple threads, locks need to be acquired. Only the thread having ownership to the lock can execute the critical section. Upon exit, the thread releases the lock and other contesting threads, now have a chance to acquire the lock.
State: A thread waiting on a mutex goes to sleep i.e blocked state without consuming CPU cycles.
Recursiveness : Mutex are recursive in nature i.e. they can be acquired recursively by the same. thread.

Sample code of mutex used as sync primitive for updating shared resource accurately.

#include <iostream>
#include <pthread.h>
#include <mutex>

using namespace std;

mutex mtx;

void* thrFunc(void *arg){
        int *val = (int*)arg;
        for(int i = 0; i<10000; i++){
                //mtx.lock(); //lock mutex 
                lock_guard<mutex> lock(mtx); // Automatically locks and unlocks
                (*val)++;
                //mtx.unlock(); //unlock mutex - error prone; use lock_guard instead
        }
}

int main(){
        pthread_t t1, t2;
        int val = 0;
        pthread_create(&t1, NULL, thrFunc, (void*)&val);
        pthread_create(&t2, NULL, thrFunc, (void*)&val);
        pthread_join(t1,NULL);
        pthread_join(t2,NULL);
        cout<<"Value : "<<val<<"\n";
}

Note that mutex are typically not used for signalling, i.e they only protect the shared resource by allowing / preventing access to them and don’t notify completion of an event.
For situations where notifying of an event is also required, condition variables are used in combination with mutex.

Condition Variables

Condition Variables allow a thread to wait until completion of an event protected by a mutex.
condition variable wait releases mutex if held, puts the thread to sleep and wakes up either on spurious wake (described below) or upon occurrence of event for which it is waiting on. It then acquires the mutex and continues with execution.

#include <iostream>
#include <pthread.h>
#include <mutex>

using namespace std;

pthread_mutex_t mtx;
pthread_cond_t cv;

int value = 0;

void* producer(void *arg){
        int *valInc = (int*)arg;
        pthread_mutex_lock(&mtx);
        value += *valInc;
        cout<< "Value incremented to : "<< value << "\n" ;
        pthread_mutex_unlock(&mtx);
        pthread_cond_broadcast(&cv);
        return NULL;
}

void* consumer(void *arg){
        int *valDec = (int*)arg;
        while( value == 0 ){
                pthread_cond_wait(&cv , &mtx);
        }
        if( value >= *valDec ){
                value -= *valDec;
                cout<< "Value decremented to : "<< value << "\n";
        }else{
                cout<< "Requested value cannot be decremented.\n";
        }
        return NULL;
}


int main(){
        if(pthread_mutex_init(&mtx,0))
                exit(EXIT_FAILURE);
        if(pthread_cond_init(&cv,0))
                exit(EXIT_FAILURE);
        pthread_t t1, t2;
        int consume = 10;
        int increment = 100;
        pthread_create(&t1, NULL, &consumer, (void*)&consume);
        pthread_create(&t2, NULL, &producer, (void*)&increment);
        pthread_join(t1, NULL);
        pthread_join(t2, NULL);
                 
        return 0;
}

Note : Spurious wake ups can occur. A spurious wakeup occurs when a thread wakes up from waiting on a condition variable but finds that the condition is still unsatisfied. This happens when there are multiple threads waiting for the same event. Between the time thread is signalled for an event occurrence and ready to run, another signal has executed and changed the condition.
To avoid acting upon spurious wake ups, cond waits are always part of while loop that checks for the condition as opposed to using if statement.

Get Priii’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Spin locks

Spin locks are the type of locks that protect critical section and put other threads trying to acquire it on a busy wait. The threads waiting to acquire spin locks spin in place i.e they consume CPU cycle as opposed to mutex where the threads waiting go to blocked state / sleep.

Such locks are required :

• In situations where the cost of using scheduler to put/wake a process from sleep state is higher than the cost of few cycles that spinlock is expected to last.
• Interrupt handlers need synchronization primitives but they can not be rescheduled on Linux. Since interrupt handlers are not able to sleep, spin lock keep them active without going to sleep while contesting for resources.

Recursiveness : Spin locks are not recursive in nature. Attempts to acquire them recursively will lead to deadlock.

A common concern across implementing locks (in the kernel) is that updating lock’s value itself has to be atomic to protect it against race condition. It is atomically done via CAS (Compare and Set) and TAS (Test and Set) mechanism.

Compare and Set :

cas(int *p, int old, int new){
   if (*p != old)
     return false;
   *p = new
   return true;
}

Implementing mutex with CAS

while(!CAS(mutex, 0 , 1 )); //wait while mutex = 1

• If mutex value is 0, it means it’s not acquired yet. CAS function sets the mutex’s to value of 1 atomically and returns true.
• If mutex is 1, mutex cannot be acquired right now, wait for it to be zero, which will lead to above operation.

Similarly Test and Set can also be used

tas(int *lock){
   oldValue = *lock
   *lock = true;
   return oldValue
}

While the synchronization primitives are kernel objects which takes care of updating it atomically in fool proof way, their usage is ultimately upto the developer.

Following usages of locks leads to deadlock which can be as the name suggests deadly.

• Wrong order
  In a multi threaded process, mutex when acquired in opposite order to as it’s released goes into deadlock. It creates a circular dependency making the threads waiting for each other to release the mutex and hence go into deadlock.
• Fork and sync primitives
  Mutex have ownerships which means only a thread that has acquired a mutex can release it.
  Consider a situation of a multi threaded process. A thread acquires a mutex and in parallel another thread has executed fork. As a multi threaded process when forked only inherits the thread that has called fork, the child process doesn’t inherit the ownership of the mutex. Now if the child process has a section which needs lock, it goes into deadlock.
  Some mitigations to avoid the above situation are :
• Always call exec() in child after a fork.
• pthread implementation takes care of this issue by providing pthread_atfork. It declares a set of handlers that are called before and after a fork in parent and child process. Mutex can be identified and released before forking in these handlers.

That was a long read! Hope you enjoyed the article!