Deadlocks – Oh No !

Following my previous post about mutexes
I’ll get to the code straight away.

#include<stdio.h>
#include<pthread.h>


pthread_mutex_t lock1,lock2;



void* func1(void* data)
{

	
	pthread_mutex_lock(&lock1);
	sleep(1);
	pthread_mutex_lock(&lock2);
	printf("Function One\n");
	pthread_mutex_unlock(&lock1);
	pthread_mutex_unlock(&lock2);

	
}

void* func2(void* data)
{

	
	pthread_mutex_lock(&lock2);
	sleep(1);
	pthread_mutex_lock(&lock1);
	printf("Function Two\n");
	pthread_mutex_unlock(&lock1);
	pthread_mutex_unlock(&lock2);

	
}

void main()
{
	pthread_t t1,t2;
	pthread_mutex_init(&lock1, NULL);
	pthread_mutex_init(&lock2, NULL);
	pthread_create(&t1,NULL,func1,NULL);
	pthread_create(&t2,NULL,func2,NULL);
	pthread_join(t1,NULL);
	pthread_join(t2,NULL);
}

Output ??

Well there isn’t any output. The program runs forever without displaying anything. Here’s why : t1 locks lock1 and t2 locks lock2. After waiting for 1 second t1 tries to get lock2 and t2 tries to get lock1. But both lock1 and lock2 are never unlocked since none of the proceeds to unlock them.
One is waiting for the other and nothing ever happens. The Classic Problem of Circular wait, Alas ! It’s a DEADLOCK !!

OK ! So what now ?

Unlike Mutual Exclusion there is no utility to avoid deadlocks. The only way to avoid deadlocks is by being smart while programming. It’s entirely up to the programmer in most cases to avoid them.

Advertisements

Mutual Exclusion – The Curse of Threads

Ths is a direct sequel to my previous post about Threads.

Race Condition / Data Inconsistency ?

Threads. All seems well until you start exchanging data between threads. Data is mainly shared between threads through global variables. When 2 or more threads in the same  program access the same variable without being careful it leads to utter chaos, and there is no way to predict the state of variables . The following example illustrates

#include<stdio.h>
#include<pthread.h>


int num = 0;


void* square(void* data)
{

	while(1)
	{
		printf("The Number is %d\n",num);
		sleep(2);
		printf("And its square is %d\n",num*num);
		sleep(1);
	}
}

void* inc(void* data)
{
	while(1)
	{
		num++;
		sleep(1);
	}
}

void main()
{
	pthread_t t1,t2;
	pthread_create(&t1,NULL,square,NULL);
	pthread_create(&t2,NULL,inc,NULL);
	pthread_join(t1,NULL);
}

The output

The Number is 0
And its square is 4
The Number is 3
And its square is 25
The Number is 7
And its square is 64
The Number is 9
And its square is 121
The Number is 12
And its square is 196
The Number is 15
And its square is 289
The Number is 18
And its square is 400
The Number is 21
And its square is 529
The Number is 24
And its square is 676

Di section

So what’s happening here. t1 is given the job of displaying num, waiting for 1 second and then displaying the square. But by that time num is already modified by t2.
This illustrates a potential nightmare for programmers. If t1 was doing some other computation instead of sleep and again tried to access num there is no guarantee that it would remain the same.

Enter – The Mutex

Mutexes can be though of as a room that can be locked from the inside. If a room has been occupied and locked from the inside, another person trying to enter and lock the room has to wait.

The following program illustrates.

#include<stdio.h>
#include<pthread.h>


int num = 0;
pthread_mutex_t lock;

void* square(void* data)
{

	while(1)
	{
		pthread_mutex_lock(&lock);
		printf("The Number is %d\n",num);
		sleep(2);
		printf("And its square is %d\n",num*num);
		pthread_mutex_unlock(&lock);
		sleep(1);

	}
}

void* inc(void* data)
{
	while(1)
	{
		pthread_mutex_lock(&lock);
		num++;
		pthread_mutex_unlock(&lock);
		sleep(1);

	}
}

void main()
{
	pthread_t t1,t2;
	pthread_mutex_init(&lock, NULL);
	pthread_create(&t1,NULL,square,NULL);
	pthread_create(&t2,NULL,inc,NULL);
	pthread_join(t1,NULL);
}

The Output

The Number is 0
And its square is 0
The Number is 1
And its square is 1
The Number is 2
And its square is 4
The Number is 3
And its square is 9
The Number is 4
And its square is 16
The Number is 5
And its square is 25
The Number is 6
And its square is 36
The Number is 7
And its square is 49
The Number is 8
And its square is 64
The Number is 9
And its square is 81
The Number is 10
And its square is 100

Explanation

pthread_mutex_t lock;

Each mutex is a variable of type pthread_mutext_t.An important thing to remember is that mutexes must be declared in the scope of the variable you wish to protect. Since we are concerned with num which is global, our mutex lock is also global.

pthread_mutex_init(&lock, NULL);

All mutexes must be initialized with pthread_mutex_init. The first argument is a pointer to the mutex, The second argument is a pointer of type pthread_mutexattr_t.It specifies the type of the mutex. Since we have specified NULL the default type is used.

pthread_mutex_lock(&lock);

Acquires the lock .( Locks the room )

pthread_mutex_unlock(&lock);

Releases the lock . ( Unlocks the room and leaves )

Here’s how it works

Before t1 tries to print the value of num it acquires the lock by calling pthread_mutex_lock. At this point even if t2 want to increment num it is made to wait when it calls pthread_mutex_lock. Only after t1 has called pthread_mutex_unlock t2 gets access to num and increments it.

Same goes for t2, When t2 is incrementing after calling pthread_mutex_lock t2 is made to wait when it calls pthread_mutex_lock. t1 only proceeds when t2 calls pthread_mutex_unlock.

In this way only one of t1 and t2 get to use num.

Data Inconsistency is avoided. Problem Solved !

Multi-threading poses yet one final major problem, Deadlocks, more about it here

Pthread Tutorial – Simplified

Threads – What are they ?

Threads are often described as light-weight processes. They can work like two or more processes sharing the same address space ie they will work independently like processes but can share the same global variables.They are mostly used when two tasks can be done independently without depending much on each other.As an example your IM client might launch one thread for each conversation ( if I am talking to A and B, the two conversations are totally computationally independent from each other ).

Hello Threads !

 
Lets get down to business. A simple thread hello world. I’ll explain only the important parts.

#include<stdio.h>
#include<pthread.h>

void* say_hello(void* data)
{
	char *str;
	str = (char*)data;
	while(1)
	{
		printf("%s\n",str);
		sleep(1);
	}
}

void main()
{
	pthread_t t1,t2;

	pthread_create(&t1,NULL,say_hello,"hello from 1");
	pthread_create(&t2,NULL,say_hello,"hello from 2");
	pthread_join(t1,NULL);
}

 

Explanation

Compile and run the above code with

gcc thread.c -o thread -lpthread

The –lpthread at the end to link the pthread library

#include<pthread.h>

The default threading library in Linux. pthread stands for POSIX threads. Include it to enable thread support for your C program

void* say_hello(void* data)
{
	char *str;
	str = (char*)data;
	while(1)
	{
		printf("%s\n",str);
		sleep(1);
	}
}

Each thread executes a function. In this case the function prototype is predefined. The function needs to have a void* pointer as argument and must return a void* pointer ( void* can be interpreted as a pointer to anything ).
The function converts the data pointer to a string pointer str and runs a while loop to print it,the sleep function pauses the thread for 1 second as specified. Needless to say that the function never returns.

pthread_t t1,t2;

pthread_t is a data type that holds information about threads. Each thread requires one pthread_t variable

pthread_create(&t1,NULL,say_hello,"hello from 1");

The above function creates a thread. Lets look at the prototype

int pthread_create(pthread_t *thread, const pthread_attr_t *attr,void *(*start_routine)(void*), void *arg);

thread
is a pthread_t variable in our case t1 and t2.
attr
is a variable of type pthread_attr_t, if specified it holds details about the thread, like scheduling policy, stack size etc. Since we have specified NULL the thread runs with default parameters.
start_routine
is the function the thread executes. In our case it is the ever so friendly say_hello function.
arg
is a void pointer which points to any data type. This same pointer is passes to the start_routine function when it is called. In our case the strings hello from 1/hello from 2 are passed to the say_hello function in the data variable.

pthread_join(t1,NULL);

pthread_joinwaits for the thread specifies in the first argument to exit, which in our case doesn’t happen, so the program runs forever, unless you interrupt it with Ctrl-C etc.

The second argument is a pointer to the variable specified by pthread_exit in case the thread calls the function to exit. Since it is NULL, it is ignored.

The idea behind threads

It is easy to visualize how threads on modern CPUs with multiple cores can work. If there are 2 threads and 2 cores, one core gets one thread.But , hey !! Hang on a second . Threads have been existing since before Multi-Core CPUs became common. So can two threads run on just 1 CPU.

The answer is, they don’t. One CPU runs only one thread at a time, but it switches between them so fast, that we don’t notice. But one particular advantage is, while one thread is waiting for an event ( like hard disk to be ready to read a file ),it doesn’t need the CPU. And the other threads( if they want ) can happily claim the CPU.

Also note that one a Single Core CPU two threads which only do computations ( CPU bound threads ) are practically useless. Getting the job done from 2 threads simultaneously will approximately be same as gettting one job done after another.

The following example illustrates one CPU and one I/O bound thread.

#include<stdio.h>
#include<pthread.h>

void* say_hello(void* data)
{
	char *str;
	str = (char*)data;
	while(1)
	{
		printf("%s\n",str);
		usleep(1);
	}
}

void* open_file(void* data)
{
	char *str;
	str = (char*)data;
	printf("Opening File\n");
	FILE* f = fopen(str,"w");
	fclose(f);
	printf("Closing File\n");
}

void main()
{
	pthread_t t1,t2;

	pthread_create(&t1,NULL,open_file,"hello.txt");
	pthread_create(&t2,NULL,say_hello,"The CPU is mine now :D");
	pthread_join(t1,NULL);
}

usleep pauses the calling thread for the specified time in microseconds

Here is the output incase you are too lazy !

Opening File
The CPU is mine now 😀
The CPU is mine now 😀
Closing File

while t1 opens a file ,t2 is pretty happy to claim the CPU.

Finally

Many people don’t consider you as a serious programer unless you know about threads. But threads can be a blessing in disguise if not used properly. Their worst curse is Data Inconsistency. I will highlight it in my next post here