<< Previous Article

In the previous article, we discussed about the kernel threads, wherein we discussed various aspects of threads such as creation, stopping, signalling and so on. Threads provide one of the ways to achieve multitasking in the kernel. While multitasking brings the definite improvement in the system performance, but it comes with its own side effects. So, what are the side effects of multitasking? How can we overcome these? Read on to get the answer to all these questions.

Concurrency Management

In order to achieve the optimized system performance, kernel provides the multitasking, where multiple threads can execute in parallel and thereby utilizing the CPU in optimum way. Though useful, but multitasking, if not implemented cautiously can lead to concurrency issues, which can be very difficult to handle. So, let’s take an example to understand the concurrency issues. Let’s say there are two threads – T1 and T2. Among them is the shared resource called A. Both the threads execute the code as below:

int function()
{
    A++;
    printf("Value of i is %d\n", i);
}

Just imagine, when the thread T1 was in the middle of modifying the variable, it was pre-empted and thread T2 started to execute and it tries to modify the variable A. So, what will be result? Inconsistent value of variable A. These kind of scenarios where multiple threads are contending for the same resources is called race condition. These bugs are easy to create, but difficult to debug.

So, what’s the best way to avoid the concurrency issues? One thing is to avoid the global variables. But, its not always possible to do so. As you know, hardware resources are in nature globally shared. So, in order to deal with such scenarios, kernel provides us the various synchronization mechanisms such as mutex, semaphores and so on.

Mutex

Mutex stands for MUTual EXclusion. Its a compartment with a single key. Whoever, enters inside the compartment, locks it and takes the key with him. By the time, if someone else tries to acquire the compartment, he will have to wait. Its only when he comes outside, gives the key, would the other person be able to enter inside. Similar is the thing with the mutex. If one thread of execution acquires the mutex lock, other threads trying to acquire the same lock would be blocked. Its only when the first thread releases the mutex lock, would the other thread be able to acquire it. Below are the data structures for mutex:

#include <linux/mutex.h>

struct mutex /* Mutex data structure */

// Mutex Initialization
// Statically
DEFINE_MUTEX(my_mutex);
// Dynamically
struct mutex my_mutex;
mutex_init(&my_mutex);

// Operations
void mutex_lock(&my_mutex);
void mutex_unlock(&my_mutex);
int mutex_lock_interruptible(&my_mutex);
int mutex_trylock(&my_mutex);

Here, there are two versions for lock – interruptible and uninterruptible. mutex_lock_interruptible()  puts the current process in TASK_INTERRUPTIBLE state. So, the current process sleeps until the state is changed to TASK_RUNNING. For the process in TASK_INTERRUPTIBLE, there are two possible events which may change the process state to TASK_RUNNING. First event is obviously, when the mutex is available and another thing is, if any signal is delivered to process. But, if the process is put into the TASK_UNINTERRUPTIBLE state, which is the case when we invoke mutex_lock(), the only event which can wake up the process is the availability of resource. In almost all the scenarios we use mutex_lock_interruptible().

Below is the simple example to demonstrate the usage of mutex.

static int thread_fn(void *unused)
{
    while (!kthread_should_stop())
    {
        counter++;
        printk(KERN_INFO "Job %d started\n", counter);
        get_random_bytes(&i, sizeof(i));
        ssleep(i % 5);
        printk(KERN_INFO "Job %d finished\n", counter);
    }
    printk(KERN_INFO "Thread Stopping\n");
    do_exit(0);
}

Here, we have global variable counter, which is being shared between two threads. Each thread increments the counter, prints the value and then sleeps for random number of seconds. This is obvious entity for race condition and can result into the corruption of variable counter. So, in order to protect the variable, we use the mutex as below:

#include <linux/mutex.h>

DEFINE_MUTEX(my_mutex);
static int counter = 0;

static int thread_fn(void *unused)
{
    while (!kthread_should_stop())
    {
        mutex_lock(&my_mutex);
        counter++;
        printk(KERN_INFO "Job %d started\n", counter);
        get_random_bytes(&i, sizeof(i));
        ssleep(i % 5);
        printk(KERN_INFO "Job %d finished\n", counter);
        mutex_unlock(&my_mutex);
    }
    printk(KERN_INFO "Thread Stopping\n");
    do_exit(0);
}

As seen in the above code, we declare a variable my_mutex of type struct mutex which protects the global variable counter. Thread will be able to access the variable only if it is not in use by another thread. In this way, mutex synchronizes the access to the global variable counter.

Semaphore

Semaphore is a counter. It is mostly used, when we need to maintain the count of the resources. Let’s say we want to implement the memory manager, where we need to maintain the count of available memory pages. To start with, say we have 10 pages, so the initial value of the semaphore will be 10.  So, if the thread 1 comes and asks for the 5 pages, we will decrement the value of semaphore to 5 (10 – 5). Likewise, say thread 2 asks for 5 pages, this will further decrement the semaphore value to 0 (5 – 5). At this point, if there is an another thread say thread 3 and asks for 3 pages, it will have to wait, since we don’t any pages left. Meanwhile, if the thread 1 is done with the pages, it will release 5 pages, which in turn will increment the semaphore value to 5 (0 + 5). This, in turn will unblock the thread-3, which will decrement the semaphore value to 2 (5 – 3). So, as you understand, there are two possible operations with the semaphore – increment and decrement. Accordingly, we have two APIs – up and down. Below are the data structures and APIs for semaphore.

#include <linux/semaphore.h>

struct semaphore /* Semaphore data structure */

// Initialization
// Statically
DEFINE_SEMAPHORE(my_sem);
// Dynamically
struct semaphore my_sem;
sema_init(&my_sem, val);

// Operations
void down((&sem);
int down_interruptible(&sem);
int down_trylock(&sem);
void up(&sem);

As with the mutex, we have two versions of down – interruptible and uninterruptible. Initialization function sema_init() takes two arguments – pointer to the struct semaphore and initial value of semaphore. If semaphore value is greater than 1, we call it as counting semaphore and if the value of semaphore is restricted to 1, it operates in way similar to mutex. The semaphore for which the maximum count value is 1, is called as binary semaphore. Below is example, where the mutex is replaced with a semaphore:

#include <linux/semaphore.h>

static struct my_sem;
static int counter = 0;

static int thread_fn(void *unused)
{
    while (!kthread_should_stop())
    {
        if (down_interruptible(&my_sem))
            break;
        counter++;
        printk(KERN_INFO "Job %d started\n", counter);
        get_random_bytes(&i, sizeof(i));
        ssleep(i % 5);
        printk(KERN_INFO "Job %d finished\n", counter);
        up(&my_sem);
    }
    printk(KERN_INFO "Thread Stopping\n");
    do_exit(0);
}

static int init_module(void)
{
    // Binary semaphore
    sema_init(&my_sem, 1);
}

The code is same as with mutex. It provides the synchronized access to the global variable counter.

Conclusion

In this article, we discussed two most commonly used synchronization mechanisms. As seen from the above examples, the synchronization achieved  with mutex, can be achieved with the binary semaphore as well. Apart from this, semaphore can also operate in counting mode. So, why do we need mutex at all? Also, can we use the semaphore in interrupt handler? To find the answers to these questions, stay tuned to my next article on concurrency management. Till then, good bye.

Next Article >>