Sunday, November 4, 2018

Pthread - Passing multiple variables to thread start function

We have already covered basics of threads, and then created, joined and detached threads.

Now, will check how to pass single or multiple variables to the thread function.

Will be covering the following topics.



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

The Argument to a thread function?


The thread start function can take only one argument of type void *. It is passed as the fourth argument in pthread_create() function.



Since it's type is void *, any data type can be typecasted and passed to the thread function. In thread function, again, it is typecasted back to its original type.

Care should be taken when using the same variable in multiple threads. The argument is either pointer or reference to a variable. Any change in one thread will be reflected in other threads.

To avoid such effect, copy the initial value into another non-pointer local variable and make changes into that. Another way is to allocate new memory for the function arguments.

Use mutex or any other locks for synchronized access, if you want the changes in one thread to be seen into other threads.

What is the meaning of void * type?


The data type void *  is a void pointer that has no associated data type with it. It can hold the address of any type and can be typecasted to any type. So, can pass any data type to the function by typecasting it.

Let's play with the arguments


Example 1:
In this example, passing the same local variable to the three threads. The difference is how it is accessed in the thread function. In thread_1 and thread_2, using a pointer variable to access the thread function argument. In thread_3, using a non-pointer local variable. The variable is changed in thread_1, it is visible in thread_2 and parent.
  • thread_1: Used (int *) to access the variable and then changed its value.
  • thread_2: Used (int *) to access the variable. Changes in thread_1 are visible in thread_2 
  • thread_3: Used (int) to access the variable. Changes in thread_1 are not visible in thread_3. 
  • parent: Changes done in thread_1 are visible in the parent.


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

void *thread_1(void *a)
{
        int *b = (int*)a;
        printf("thread_1 : b = %d\n", *b);
        sleep(1);
        *b = 10;
        printf("thread_1 : Changed value to b = %d\n", *b);
        return NULL;
}

void *thread_2(void *a)
{
        int *b = (int*)a;
        printf("thread_2 : b = %d\n", *b);
        sleep(2);
        printf("thread_2 : Used pointer to input argument. Getting the effect of changes in thread_1 b = %d\n", *b);
        return NULL;
}

void *thread_3(void *a)
{
        int b = *((int*)a);
        printf("thread_3 : b = %d\n", b);
        sleep(2);
        printf("thread_3 : Used local non-pointer variable, no change seen here b = %d\n", b);
        return NULL;
}

void *parentFunction(void *arg)
{
        pthread_t th_1, th_2, th_3;
        pthread_attr_t attr;
        int rc;
        volatile int a = 5;

        if(rc = pthread_create(&th_1, NULL, thread_1, (void *)&a))
        {
                printf("Failed to create thread, Error returned %d\n", rc);
        }

        if(rc = pthread_create(&th_2, NULL, thread_2, (void *)&a))
        {
                printf("Failed to create thread, Error returned %d\n", rc);
        }

        if(rc = pthread_create(&th_3, &attr, thread_3, (void *)&a))
        {
                printf("Failed to create thread, Error returned %d\n", rc);
        }
        sleep(2);
        printf("parent : Passed reference to variable to the thread function, Got changed value a = %d\n", a);
        pthread_join(th_1, NULL);
        pthread_join(th_2, NULL);
        pthread_join(th_3, NULL);
        printf("parent : Joined with threads ... exiting now\n");
        return NULL;
}


int main()
{
        pthread_t parent, joinable, detached1, detached2;
        int rc;

        if(rc = pthread_create(&parent, NULL, parentFunction, NULL))
        {
                printf("Failed to create thread, Error returned %d\n", rc);
                return rc;
        }

        pthread_join(parent, NULL);
        printf("Main thread: After joining parent thread ... exiting\n");
        return 0;
}

# Output of the above code

thread_1 : b = 5
thread_3 : b = 5
thread_2 : b = 5
thread_1 : Changed value to b = 10
parent : Passed reference to variable to the thread function, Got changed value a = 10
thread_2 : Used pointer to input argument. Getting the effect of changes in thread_1 b = 10
thread_3 : Used local non-pointer variable, no change seen here b = 5
parent : Joined with threads ... exiting now
Main thread: After joining parent thread ... exiting
                                                                         

This is happening because thread_1 and thread_2, the pointer used are pointing to the variable in the parent. Thus any change in thread_1 is visible in parent also. However, in thread_3, we are coping the variable to a non-pointer local variable. This variable is allocated in thread's stack. Any change to stack variable will not be visible to other threads.

How to pass multiple variables to a thread?

To pass multiple arguments to the thread function, create a structure to group all the arguments. Pass a pointer to the structure as an argument to the thread start_routine.

Example 2:
In this example, passing multiple arguments to thread start function. Used structure dataStruct to encapsulate all the variables and sent its reference to the thread function.



#include <stdio.h>
#include <pthread.h>
#define thread_count (4)

typedef struct dataStruct
{
        int start;
        int end;
}dataStruct;

void *Data_output(void *d)
{
        dataStruct *D = (dataStruct *)d;
        printf("Thread id %lu: Start time %d, End time %d\n", pthread_self(),
                D->start, D->end);
}

int main()
{
     pthread_t thread_id[4];
     dataStruct D[4] = {{100, 200}, {300, 500}, {600, 700}, {800, 900}};
     int i;
     for (i = 0; i < thread_count ; i++)
     {
        pthread_create (&thread_id[i], NULL, Data_output, (void *) &D[i]);
     }

     for (i = 0; i < thread_count; i++)
     {
        pthread_join (thread_id[i], NULL);

     }

     return (0);
}

// Output of the above code
Thread id 140476141180672: Start time 100, End time 200
Thread id 140476132787968: Start time 300, End time 500
Thread id 140476124395264: Start time 600, End time 700
Thread id 140476116002560: Start time 800, End time 900


Global variables with multiple threads?

While using global variables, any change in one thread will be visible in other threads. To get predictable results needs to synchronize its access. Mutex or any other locks are needed for synchronization. Will cover this in the mutex blog.


Saturday, October 27, 2018

Pthread - Lets create, join and detach threads


We have already covered basics of threads. Now will create a thread, join it and see how to detach it? While exploring each topic will answer the doubts, like ...

  • What is the lifetime of a thread?
  • Joinable and detached threads?
  • Why joining a thread is necessary?
  • Is there any way to avoid joining a thread?
  • What is the main thread, is it different than other threads?
  • Is there any relation between parent and child thread?
       etc ....

There are some important, good to know points in extra bytes.


Create a thread:

The function call pthread_create() creates a new thread for the process. The new thread starts executing start_routine.


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



What is the lifetime of a thread?

We know that a process lifetime is the main function. Similarly, a thread's lifetime is the start_routine. Once the thread returns from start_routine, it terminates.

Similar to a process, there are other ways to terminate a thread.
  • pthread_exit(): Called by default when a thread returns from start routine. However, pthread_exit() can be called explicitly to terminate a thread.
  • pthread_cancel(): A thread can be cancelled using function pthread_cancel().
  • exit(): All the threads of a process terminate if any thread calls exit(). Similarly, all threads terminate if main thread returns or exits.
  • Signal: If a signal's action is to terminate the process, all threads of the process terminate.


 After termination, a thread can be joined by another thread(pthread_join()).

Joinable and detached threads

 A thread is created as joinable or detached. A joinable thread needs to be joined after termination. Detached thread should not be joined.

By default, a thread is created as joinable. For creating a detached thread, need to set thread attribute using pthread_attr_setdetachstate() and attribute value PTHREAD_CREATE_DETACHED.

Why join a thread?

Each thread uses some resources to perform the given work. Along with that, some system resources are used to maintain threads. These system resources are released after thread termination. Failure to release causes resource leakage. So, who releases these resources?

When a thread is created, the ownership of there resources is given back to the process. So, any thread can release the resources by calling pthread_join() for the target thread.

The caller of pthread_join() also waits for the target thread termination if not already terminated.

In general, parent thread joins the child threads.

The return value or status from a thread is accessed via pthread_join().

Is there a way to avoid joining a thread and still release the resources?

Yes, if it's a detached thread. For a detached thread, the ownership of thread resources is transferred to the thread itself. Once a detached thread terminates, its resources are released.

A thread can be created as detached thread OR a joinable thread can be detached by a call to pthread_detach().

Once a thread is detached, cannot be made joinable again.

A thread can detach itself.


    pthread_detach(pthread_self());




It is important to either call pthread_join or pthread_detach() for a thread. However, not both.

Main thread and child threads

The thread created with the process is called the main thread. The main thread is the parent for all the threads. It is responsible for process related cleanup. When the main thread terminates, all other threads also terminate.

So, who can create a new thread?  The answer is, any thread can create a new thread. The thread hierarchy is not maintained by the process. Also, any thread can be joined by another thread. All the threads of a process are at the same level.




How to terminate the main thread but not other threads?

If the main thread is terminated using pthread_exit(), it will allow other threads to continue running. It keeps the main thread in zombie status. The drawback is you cannot get the return status of threads created by the main thread. Also, all process resources will be released when the process exits.

Example

In this example, we will create a parent thread and three child threads of type:
  • Joinable thread
  • Detached thread
  • A joinable thread which will be detached later.
We will see that even if parent exits, the child threads still continue to execute.

This shows that all the threads are peers and there is no parent-child relationship among them. The threads lifetime is not dependent on parent thread except if it is main thread. If main thread exits, all other threads also exit.


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

void *detachedFunction(void *)
{
        printf("detachedFunction %lu: Sleeping for 10 sec\n", pthread_self());
        sleep(10);
        printf("detachedFunction %lu: Came out of sleep\n", pthread_self());
        return NULL;
}

void *joinDetachedFunction(void *)
{
        pthread_detach(pthread_self());
        printf("joinDetachedFunction %lu: Sleeping for 10 sec\n", pthread_self());
        sleep(10);
        printf("joinDetachedFunction %lu: Came out of sleep\n", pthread_self());
        return NULL;
}

void *joinableFunction(void *)
{
        printf("joinableFunction %lu: Sleeping for 5 sec\n", pthread_self());
        sleep(5);
        printf("joinableFunction %lu: Came out of sleep\n", pthread_self());
        return NULL;
}

void *parentFunction(void *arg)
{
        pthread_t joinable, joinDetached, detached;
        pthread_attr_t attr;
        int rc;

        // Create a joinable thread
        if(rc = pthread_create(&joinable, NULL, joinableFunction, NULL))
        {
                printf("Failed to create thread, Error returned %d\n", rc);
        }

        // Create a joinable thread. We will detach it later
        if(rc = pthread_create(&joinDetached, NULL, joinDetachedFunction, NULL))
        {
                printf("Failed to create thread, Error returned %d\n", rc);
        }

        // Create a detached thread
        pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED);
        if(rc = pthread_create(&detached, &attr, detachedFunction, NULL))
        {
                printf("Failed to create thread, Error returned %d\n", rc);
        }
        printf("parent %lu: Waiting to join joinable thread %lu\n", pthread_self(), joinable);
        pthread_join(joinable, NULL);
        printf("parent %lu: Joined with joinable thread %lu\n", pthread_self(), joinable);
        return NULL;
}


int main()
{
        pthread_t parent, joinable, detached1, detached2;
        int rc;
        if(rc = pthread_create(&parent, NULL, parentFunction, NULL))
        {
                printf("Failed to create thread, Error returned %d\n", rc);
                return rc;
        }

        pthread_join(parent, NULL);
        printf("Main thread: After joining parent thread\n");
        sleep(20);
        printf("Main thread: After sleep\n");
        return 0;
}


The output of the above program shows that all thread continue to run even when parent thread terminates. Here parent thread is not the main thread.


parent 140582397703936: Waiting to join joinable thread 140582389311232
joinDetachedFunction 140582380918528: Sleeping for 10 sec
detachedFunction 140582372525824: Sleeping for 10 sec
joinableFunction 140582389311232: Sleeping for 10 sec

joinDetachedFunction 140582380918528: Came out of sleep
detachedFunction 140582372525824: Came out of sleep
joinableFunction 140582389311232: Came out of sleep
parent 140582397703936: Joined with joinable thread 140582389311232
Main thread: After joining parent thread
Main thread: After sleep


What factors decide the maximum number of threads for a process?

In Linux, max limit can be found using command "cat /proc/sys/kernel/threads-max". However, there are other factors also which decide the maximum number of threads per process:
  • Virtual address space which needs to fit the stack for all threads.
  • Scheduler overhead. All the threads need to be scheduled. It should not make the system very slow.
  • Max number of processes for the system

How many parallel threads actually run in a system?

The number of threads running in a system depends on following:
  • Number of CPU
  • Number of core per CPU
  • Number of threads which can run per core.
Number of parallel threads = number of CPU * number of core per CPU * number of threads per core

In general 2 threads run per core. Use the lscpu command in Linux to get information on CPU attributes.


Extra bytes

  • PID and TID for a thread? All threads of the process have the same PID. Each thread has unique TID. TID is also called lwp or SPID. It is a unique number assigned by the kernel to identify a thread. TID is same as PID for the main thread.
  • How to pass different data type to the start routine? The start_routine takes only one argument of type (void *). We can typecast any pointer type into void * so we can pass any type to the thread start function. But only one parameter can be passed.
  • How to pass multiple arguments to a thread function? Use structure to encapsulate all augments you wish to pass to thread start function. Pass pointer to structure to the thread start function.
  • Who will execute first, caller thread or newly created thread? We cannot determine which thread will be scheduled first unless real-time scheduling is used.
  • Thread ID returned by pthread_self and gettid: gettid() returns the unique number assigned to a thread by the kernel. This is unique across processes. The ID returned by pthread_self() is assigned by the thread implementation. Depending on the implementation, it may be unique across the processes or a unique number for a process.
  • Thread idThe pthread_create() call returns the reference to the thread ID of type pthread_t. The ownership of the thread ID is with the process for a joinable thread. It is used to do release thread resources when pthread_join() is called on thread termination. For a detached thread, the ownership is transferred to the thread, so that it can release the resources. 
  • Calling pthread_join() for a detached thread: will try to release the resources twice and not calling pthread_join() for the joinable thread will cause resource leakage. This is the reason, a joinable thread should always be joined and a detached thread should not be joined. 
  • Is there a function to wait for any thread? The pthread library does not specify any function which will wait for any thread termination. For a child processwaitpid() with -1 as pid,  waits for any terminated child process. There is no such function for threads.

Tuesday, October 16, 2018

Pthread - Lets understand threads

In this blog, I have explained some basic details about threads in Linux. It explains the doubts we have while working on threads, like:

  • What is a thread?
  • What are the per-thread attributes and why it is needed as per thread attributes?
  • Why a thread works like a process
  • What happens when a multi-threaded program runs on single core or multicore?
  • How to debug a multithreaded program?
And in extra bytes, some more information which is good to know while working on threads.

What is a thread?

A thread is a lightweight process within the scope of a processIt means, for a process, you can create multiple threads. Each thread can function same as a process, however, with much lesser overheads.

As there can be multiple threads in a process, it provided a way to support parallel processing for a process. There will be multiple units of work which can run in parallel or in a synchronous way depending on the requirement.

The Producer-consumer problem is a good example of synchronous communication between threads. In producer-consumer problem, once a producer has produced items then the consumer can consume it. Depending on the number of items and other constraints, it can be a combination of parallel processing and synchronization between producer and consumer threads.



The threads of a process share process address space, open files and global memory (data and heap segments). It provides some benefits over multiple processes:

  • Creating a thread is less expensive as compared to processes as each thread share same address space.
  • Context switch between threads(scheduling different threads to run) is faster as compared to processes. 
  • Sharing data between threads is much faster, as the data produced by one thread is immediately available to other threads.



Why thread works like a process?


In Linux, a thread is created using system call clone(2). Clone system call creates a new process; however, the newly created process shares some parts of the calling process.

So, in a way, a thread is a process, which shares some parts with its parent process.

The clone system call is used with different parameters to allow it to share virtual address space, open files and signals. Use “man 2 clone” for more information on this.
DESCRIPTION
       clone() creates a new process, in a manner similar to fork(2)
       .…

       Unlike  fork(2),  clone()  allows  the  child  process to share
       parts of its execution context with the calling process, such as
       the virtual address space, the table of file descriptors, and 
       the table  of  signal  handlers. (Note  that  on  this  manual
       page,  "calling  process" normally corresponds to "parent 
       process".  But see the description of CLONE_PARENT below.)

       One use of clone() is to implement threads: multiple flows of 
       control in a program that run concurrently in a shared address 
       space.

What happens when a multithreaded program runs on a single core or multicore systems?

Explaining here the basic concept need to understand for multithreading. 

Single core system

In a single core system, only one thread can run at a time. However, by slicing the time, it gives an impression that multiple threads are running concurrently.

So, in a single core system, multiple threads do not give any benefit on time and efficiency. The reason is,  we are running each thread sequentially one by one depending on scheduling algorithm used. Also adding an overhead of context switch between threads.

However, the time slice for each thread is very small. For end user, it appear as if multiple works are happening in parallel.

Multicore system

In a multicore system, multiple threads can run concurrently and result in parallel processing. More than one thread is scheduled and run at the same time. A multicore system actually gives the benefit of multithreading on time and efficiency.



Per Thread attributes


The threads execute in a similar manner as a process. To achieve this, each thread has few process attributes like the stack, program counter, and registers of its own.


  • Stack: Stack is needed for local variables. Same as a process, each thread has its own stack. It is needed for independent execution of threads.
  • Program counter and set of Registers: Program counter keeps the address of the next instruction to be executed. Each thread has its own program counter and registers, allow threads to execute instructions at runtime independent of the process.
  • Thread ID: Each thread is represented by a unique thread ID. Needed to identify the thread.
  • Signal Mask: Each thread has its own signal mask. This helps to deliver a signal to a particular thread. The important point is, all the threads share signal disposition. It means, signals are sent to a process(not thread) and it can be received by any thread. By masking a signal for other threads, we can design to receive signal by a particular thread.
  • Each thread has its own errno variable. If all the threads share the same errno, then an error in one thread will affect the functioning of other threads.
  • Alternate signal stack (sigaltstack(2))
  • Real-time scheduling policy and priority (sched(7))
Note: One important per-thread attribute is thread ID. Each thread is assigned a unique ID. It is assigned at the time of thread creation. This thread ID is used by other thread function to identify the thread.

Process attributes which are shared by all threads


Rest of the parameters are shared by all threads. It includes code segment, global memory(data and heap segments), open files, signal disposition. All threads have the same process ID, parent process ID, process group ID, user and group ID, current working directory etc.

Debugging a simple program


We will use a simple example to debug using GDB. Will check the thread information, switch between different threads and check thread's local variables.


  1 #include <stdio.h>
  2 #include <pthread.h>
  3 #include <errno.h>
  4 
  5 void *simpleFunction(void *);
  6 
  7 int main()
  8 {
  9         int rc, m  = 25;
 10         pthread_t th;
 11 
 12         printf("main: Creating thread\n");
 13         if(rc = pthread_create(&th, NULL, &simpleFunction, NULL))
 14         {
 15                 printf("Thread creation failed, return code %d, errno %d", rc, errno);
 16         }
 17         printf("main: After creating thread. Variable m = %dn", m);
 18 
 19         pthread_join(th, NULL);
 20         return 0;
 21 }
 22 
 23 void *simpleFunction(void *)
 24 {
 25         int i = 5, j = 10, k = 15;
 26         printf("simpleFunction: In thread start function\n");
 27         printf("Value of i = %d, j = %d, k = %d\n", i, j, k);
 28         return NULL;
 29  }



Compile and run

Compile the above program with "-g" and "-pthread" options.

g++ -g -pthread simple.c
Always use “-pthread” while compiling a program with threads. It not only compiles and links with the correct version of pthread library also adds any flags needed for pthread library.

-g option is used to debug using GDB.

Check threads with "ps" command and GDB

ps output shows threads created by the above program. 

root@xxxx-VirtualBox:~/pthread_tst/blog# ps -elfT |grep a.out
F S UID        PID  SPID  PPID  C PRI  NI ADDR SZ WCHAN  STIME TTY          TIME CMD
0 S root     13760 13760  2899  0  80   0 - 26941 poll_s 15:13 pts/1    00:00:00 gdb -q ./a.out
0 t root     13772 13772 13760  0  80   0 -  3722 ptrace 15:14 pts/1    00:00:00 ./a.out
1 t root     13772 13776 13760  0  80   0 -  3722 ptrace 15:14 pts/1    00:00:00 ./a.out


Two threads are running. The first column is Id, which shows the ID given by GDB. This is not thread ID.

Next to Thread is thread ID. For main thread its "0x7ffff7fdf740". The "*" indicates the current thread running. It shows the current instruction being executed by each thread.

(gdb) info threads
  Id   Target Id         Frame 
* 1    Thread 0x7ffff7fdf740 (LWP 13772) "a.out" main () at simple.c:17
  2    Thread 0x7ffff77c4700 (LWP 13776) "a.out" simpleFunction () at simple.c:25


Use the command "thread <Id>" to switch to the thread Id shown in the first column in the above output. 



(gdb) thread 1
[Switching to thread 1 (Thread 0x7ffff7fdf740 (LWP 13772))]
#0  main () at simple.c:17
17  printf("main: After creating thread. Variable m = %dn", m);

Some more output


[Switching to Thread 0x7ffff77c4700 (LWP 13776)]

Thread 2 "a.out" hit Breakpoint 2, simpleFunction () at simple.c:25
25  int i = 5, j = 10, k = 15;
(gdb) n
26  printf("simpleFunction: In thread start function\n");

# After few instuctions
(gdb) thread 1
[Switching to thread 1 (Thread 0x7ffff7fdf740 (LWP 13772))]
#0  0x00007ffff7bbed2d in __GI___pthread_timedjoin_ex (threadid=140737345505024, thread_return=0x0, abstime=0x0, 
    block=) at pthread_join_common.c:89
89 pthread_join_common.c: No such file or directory.
(gdb) thread 2
[Switching to thread 2 (Thread 0x7ffff77c4700 (LWP 13776))]
#0  simpleFunction () at simple.c:28
28  return NULL;



Extra bytes

  • pthread functions return value: Most thread functions return 0 on SUCCESS and return error number on failure. Note that thread functions do not set errno variable.
  • Each thread is a schedulable entity. In Linux, each thread is assigned a task structure. The task structure is a schedulable entity and gets its time quantum to be scheduled
  • Thread safe function: A thread-safe function is a function that can safely be called from multiple threads at the same time. When called from multiple threads at the same time, its result should not be affected.
  • Cancellation point: POSIX.1 specifies some functions as cancellation points. If a thread is canceled, its cancellation is deferred till it calls a function which is declared as cancellation point.
  • Signal disposition: For each signal number the disposition is set, which explains the action needs to take when a signal is delivered. It is called signal disposition. The signal disposition can either be SIG_IGN(Ignore signal), SIG_DFL(Take default action) or a programmer-defined function (a "signal handler"). All threads share signal disposition.

Monday, October 8, 2018

Pthread - Understanding deadlock

In this blog, we will understand deadlock in software applications. We will create deadlock using coding examples and analyze it. For coding examples, I have used pthreads in Ubuntu Linux.


What is deadlock


Deadlock is a situation when process1 has acquired resource1 and is waiting for resource2. At the same time, resource2 has been acquired by another process2 who is waiting for resource1. 

So, both the processes are holding one resource and waiting for the other resource. None of the processes is ready to release the already acquired resource. This is causing deadlock.


Image result for deadlock diagram



Deadlock can happen between processes or between threads of a process. We will be using both the terms for explaining the concept.

Deadlock happens when four conditions met

  • Circular wait for resources: It means a process/thread is holding a resource and trying to acquire another resource which is held by another process/thread.
  • Mutual exclusion: Mutual exclusion means resources are not shared. It can be owned by one process or one thread at a time.
  • Hold and wait: It means to hold a resource while waiting for another resource.
  • No pre-emption: It means the thread will not release the acquired resource until it finishes the task.

How to avoid deadlock

We can break any of the above four conditions to avoid deadlock.
  • No mutual exclusion for resources, which means resources can be shared between processes or threads.
  • No hold and wait. To implement this, need to ensure that only if all the required resources are available, allow a process/thread to proceed with acquiring the resources.
  • The circular wait is not allowed. This can be done by putting a check to ensure that wait for resources is making a circle.
  • Support pre-emption of resources. One way to implement this is if there is a delay in acquiring resources, release the already acquired resource.    

Deadlock symptoms

Deadlock happens when processes or threads are waiting for resources. What happens when a process/thread is waiting for a resource?

It goes into sleep. So, if there is a deadlock, the ps command output shows participating processes/threads in sleep and it remains in sleep for a prolonged period. The processes/threads may appear hung. The ps output shows thread's state as D or S if it's in sleep.
               D    uninterruptible sleep (usually IO)
               S    interruptible sleep (waiting for an event to complete)


Deadlock analysis with examples

We will create a deadlock and analyze it using two examples.  First with a producer-consumer example where the wrong placement of signal causes deadlock. In the second example, a wrong code block is causing all threads in wait.

Example 1: Producer-consumer example


// Producer
void *threadProducer(void *arg)
{
  int i;
  for(i = 0; i < loop; i++)
  {
        produce();
        sem_wait(&mtx);  // Continue if consumer is not consuming
        append();
        n++;
        if(n == 1) sem_post(&delay);    // Unblock consumer
        sem_post(&mtx);
  }
  printf("Producer DONE\n");
  return NULL;
}
// Consumer
void *threadConsumer(void *arg)
{
  int i;
  int tmp;
  sem_wait(&delay);
  for(i = 0; i < loop; i++)
  {
        sem_wait(&mtx);  // Continue if producer is not producing
        take();
        n--;
        if(n == 0 && i < loop - 1) sem_wait(&delay);
                                     // Block self if no data items
        consume();
        sem_post(&mtx);  // Signal done with consuming
  }
  printf("Consumer DONE\n");
  return NULL;
}
int main()
{
        sem_init(&mtx, 0, 1);
        sem_init(&delay, 0, 0);
        pthread_t prod, cons;

        pthread_create(&cons, NULL, threadConsumer, NULL);
        pthread_create(&prod, NULL, threadProducer, NULL);

        pthread_join(prod, NULL);
        pthread_join(cons, NULL);

        sem_destroy(&delay);
        sem_destroy(&mtx);
        return 0;
}

In the above example, the following sequence is creating deadlock:
  1. The mutexes mtx is initialized with 1 and delay with 0.
  2. The consumer is waiting in sem_wait(&delay);
  3. The producer produces one item and makes the value of mtx and delay to 1.
  4. The consumer is inside for loop and value of both semaphores is 0.
  5. Next the line "if(n == 0 && i < loop - 1) sem_wait(&delay);" causes wait in sem_wait()
  6. The producer is waiting in line "sem_wait(&mtx);" as mtx value is 0.
  7. Now both producer and consumer are in a deadlock.
To avoid deadlock, sem_post(&mtx) should be before sem_wait(&delay).


Ps output

All the three threads for process id 7113 are in sleep. It is shown by 'S' in the state option of ps output.


xxxx# ps -eflT|grep a.out
F S UID        PID  SPID  PPID  C PRI  NI ADDR SZ WCHAN  STIME TTY          TIME CMD
0 S root      7469  7469  2074  0  80   0 - 22155 futex_ 22:00 pts/0    00:00:00 ./a.out
1 S root      7469  7470  2074  0  80   0 - 22155 futex_ 22:00 pts/0    00:00:00 ./a.out
1 S root      7469  7471  2074  0  80   0 - 22155 futex_ 22:00 pts/0    00:00:00 ./a.out


GDB output

The first thread is in sleep while executing pthread_join() for the producer and consumer threads. Second and third threads are for producer and consumer. It is in sleep in executing sem_wait() statement.



(gdb) info thread
  Id   Target Id         Frame 
* 1    Thread 0x7ffff7fdf740 (LWP 7135) "a.out" 0x00007ffff7bbed2d in __GI___pthread_timedjoin_ex (
    threadid=140737337112320, thread_return=0x0, abstime=0x0, block=) at pthread_join_common.c:89
  2    Thread 0x7ffff77c4700 (LWP 7139) "a.out" 0x00007ffff7bc66d6 in futex_abstimed_wait_cancelable (private=0, 
    abstime=0x0, expected=0, futex_word=0x555555756060 ) at ../sysdeps/unix/sysv/linux/futex-internal.h:205
  3    Thread 0x7ffff6fc3700 (LWP 7140) "a.out" 0x00007ffff7bc66d6 in futex_abstimed_wait_cancelable (private=0, 
    abstime=0x0, expected=0, futex_word=0x555555756040 ) at ../sysdeps/unix/sysv/linux/futex-internal.h:205


Example 2: Wrong code block causing deadlock

In the below example, a wrong condition is causing all threads to enter into the wait.
The block "while (id != n)" may cause deadlock here. It's possible that all the threads might meet at condition "(id != n)" and result in wait. With no thread to signal, it will cause deadlock. 




void *func(void *v)
{
        int n = *((int*)v);
        int count = 0;
        while (count < 10)
        {
                pthread_mutex_lock(&token);
                while (id != n) // This block is causing deadlock
                {
                        printf("Its not my turn, n=%d id = %d\n",n, id);
                        pthread_cond_wait(&cond, &token);
                }
                count += 1;
                printf ("My turn! id= %d\n",n);
                printf("count %d\n", count);
                if (id == 3)
                      id = 0;
                else
                      id += 1;

                pthread_mutex_unlock(&token);
                pthread_cond_signal(&cond);
        }
        printf ("ID=%d has finished\n",n);
        return(NULL);
}


In this example, to avoid deadlock, need to put a check so that all threads are not in wait.


Ps output

Ps output shows all threads in sleep as shown by state S for all threads of process id 7361.


xxxx# ps -eflT|grep a.out
F S UID        PID  SPID  PPID  C PRI  NI ADDR SZ WCHAN  STIME TTY          TIME CMD
0 S root      7361  7361  7152  0  80   0 - 26253 futex_ 18:44 pts/2    00:00:00 ./a.out
1 S root      7361  7362  7152  0  80   0 - 26253 futex_ 18:44 pts/2    00:00:00 ./a.out
1 S root      7361  7363  7152  0  80   0 - 26253 futex_ 18:44 pts/2    00:00:00 ./a.out
1 S root      7361  7364  7152  0  80   0 - 26253 futex_ 18:44 pts/2    00:00:00 ./a.out
1 S root      7361  7365  7152  0  80   0 - 26253 futex_ 18:44 pts/2    00:00:00 ./a.out



GDB output

The main thread is waiting at pthread_join(). Rest of the threads are waiting at futex_wait_cancelable() which is called by pthread_cond_wait().



(gdb) info threads
  Id   Target Id         Frame 
* 1    Thread 0x7ffff7fdf740 (LWP 7324) "a.out" 0x00007ffff7bbed2d in __GI___pthread_timedjoin_ex (
    threadid=140737345505024, thread_return=0x0, abstime=0x0, block=) at pthread_join_common.c:89
  2    Thread 0x7ffff77c4700 (LWP 7328) "a.out" 0x00007ffff7bc39f3 in futex_wait_cancelable (private=, 
    expected=0, futex_word=0x5555557560cc ) at ../sysdeps/unix/sysv/linux/futex-internal.h:88
  3    Thread 0x7ffff6fc3700 (LWP 7329) "a.out" 0x00007ffff7bc39f3 in futex_wait_cancelable (private=, 
    expected=0, futex_word=0x5555557560c8 ) at ../sysdeps/unix/sysv/linux/futex-internal.h:88
  4    Thread 0x7ffff67c2700 (LWP 7330) "a.out" 0x00007ffff7bc39f3 in futex_wait_cancelable (private=, 
    expected=0, futex_word=0x5555557560cc ) at ../sysdeps/unix/sysv/linux/futex-internal.h:88
  5    Thread 0x7ffff5fc1700 (LWP 7331) "a.out" 0x00007ffff7bc39f3 in futex_wait_cancelable (private=, 
    expected=0, futex_word=0x5555557560cc ) at ../sysdeps/unix/sysv/linux/futex-internal.h:88



Extra bytes

GDB output shows that Semaphore, mutex and condition variables are created using futex (fast userspace mutex).

Friday, October 5, 2018

Pthread - thread id

When a thread is created using pthread_create(), a unique thread ID is assigned to the newly created thread. This thread ID is used by other thread functions to identify the thread. pthread_self() function returns the same id of the thread.
man 3 pthread_self
man 3 pthread_create
For pthread_create(), the first argument is of type pthread_t. It is assigned with the ID of the newly created thread. The abstract type of pthread_t is implementation dependent. It may be int, unsigned long int or in some implementation a structure having information about the thread.

A snippet from the man page of pthread_create.
Before returning, a successful call to pthread_create() stores the ID of the new thread in the buffer pointed to by thread; this identifier is used to refer to the thread in subsequent calls to other pthread functions.
pthread_self returns the same ID, what pthread_create stores in the first argument "thread"
       int pthread_create(pthread_t *thread, const pthread_attr_t *attr,
                          void *(*start_routine) (void *), void *arg);
       pthread_t pthread_self(void);
In my system pthread_t type is "unsigned long int"
/usr/include/x86_64-linux-gnu/bits/pthreadtypes.h:typedef unsigned long int pthread_t;
In the following example, the value returned by pthread_self() and th1 are same.
// main function:
    pthread_t th1;

    if(rc1 = pthread_create(&th1, NULL, &functionC1, NULL))
    {
           printf("Thread creation failed, return code %d, errno %d", rc1, errno);
    }
    printf("Printing thread id %lu\n", th1);

// Thread function: 
    void *functionC1(void *)
    {
            printf("In thread function Printing thread id %lu\n", pthread_self());
    }

    Output:
    Printing thread id 140429554910976
    In thread function Printing thread id 140429554910976