Creating A Detached PThread using Thread Attribute

In some cases you neither need the child thread to return information to the
main thread nor want the main thread to wait for it. This behavior can be achieved by making the child thread a detached thread. A detached thread can be created by using the thread attribute or by using Posix thread method "pthread_detach". here we will discuss about the former case i.e using the thread attribute.

1. Init thread attribute:
A thread attribute can be init by following function:

int pthread_attr_init(pthread_attr_t *attr);

2. Functions for Detached state:
Below functions are used to set and get the detached state of a thread.

int pthread_attr_setdetachstate(pthread_attr_t *attr, int detachstate);
int pthread_attr_getdetachstate(const pthread_attr_t *attr, int *detachstate);

Parameter:
1. attr: Thread attribute to init.
2. detachstate: Flag to set the required thread state. It can take the vales of "PTHREAD_CREATE_JOINABLE" or "PTHREAD_CREATE_DETACHED". The default value to detachstate is "PTHREAD_CREATE_JOINABLE". When it is "PTHREAD_CREATE_DETACHED" it creates a detached thread.

3. Example:
Below is the program to create a detached thread using thread attribute. We'll call it detachedThread.c.
detachedThread.c

#include <stdio.h>  
#include <string.h>  
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>
#include <signal.h>

bool thread_finished = 0;

void* start_function(void* value)
{
    printf("%s is now entering the thread function.\n", (char*)value);
    sleep(4);
    thread_finished =1;
    printf("%s is now leaving the thread function.\n", (char*)value);
    pthread_exit(value);  
}

main()
{
    int res,err;
    pthread_attr_t attr;
    pthread_t thread1;

    res = pthread_attr_init(&attr);
    if (res != 0) {
        perror("Attribute init failed");
        exit(EXIT_FAILURE);
    }
    res = pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED);
    if (res != 0) {
        perror("Setting detached state failed");
        exit(EXIT_FAILURE);
    }

    res = pthread_create(&thread1, &attr, start_function, (void*)"Thread1");
    if (res != 0) {
        perror("Creation of thread failed");
        exit(EXIT_FAILURE);
    }

    while(!thread_finished) {
        printf("Waiting for thread1 to finish.\n");
        sleep(1);
    }

    printf("Child thread finished.\n");    
    pthread_attr_destroy(&attr);
}

When you compile and run the program, you'll see the output as:

Waiting for thread1 to finish.
Thread1 is now entering the thread function.
Waiting for thread1 to finish.
Waiting for thread1 to finish.
Waiting for thread1 to finish.
Thread1 is now leaving the thread function.
Child thread finished.

Getting the Posix Thread Id in Linux

In linux system gettid function used to get the thread ID. The TID is diffrent than PID.In a single-threaded process, the TID is equal to the PID. But in a multithreaded program, all threads belonging to same process have the same PID but each one has a unique TID. The TID generally reprsent the kernel thread id and is different from the thread ID returned by pthread_self(i.e. thread handle which is returned from pthread_create function).

Note that Glibc does not provide the function gettid(). So we will use the system call to get the TID. Let's create a simple program to see the use of gettid, getpid and pthread_self. We'll call this threadBasic.c.

threadBasic.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <sys/syscall.h>
#include <pthread.h>

pid_t gettid()
{
    pid_t tid = syscall (SYS_gettid);
}

void* start_function(void* value)
{
    pid_t tid = gettid();
    printf("Thread start function is running for: %u\n", (unsigned int)pthread_self());
    printf("The TID of thread is: %ld\n", (long int)tid);
    printf("PID of parent process is: %d\n", getpid());
    sleep(5);
    pthread_exit(value);
}

main()
{
    int res;
    pthread_t thread1, thread2;
    void* threadReturnValue;

    printf("PID of main process: %d\n", getpid());

    res = pthread_create(&thread1, NULL, start_function, "thread-one");
    if (res != 0) {
        perror("Creation of thread failed");
        exit(EXIT_FAILURE);
    }
    printf("Thread1 created with id: %u\n", (unsigned int)thread1);

    res = pthread_create(&thread2, NULL, start_function, "thread-two");
    if (res != 0) {
        perror("Creation of thread failed");
        exit(EXIT_FAILURE);
    }
    printf("Thread2 created with id: %u\n", (unsigned int)thread2);
 
    res = pthread_join(thread1, &threadReturnValue);
    if (res != 0) {
        perror("Joining of thread failed");
        exit(EXIT_FAILURE);
    }
    printf("%s joined.\n", (char*)threadReturnValue);

    res = pthread_join(thread2, &threadReturnValue);
    if (res != 0) {
        perror("Joining of thread failed");
        exit(EXIT_FAILURE);
    }
    printf("%s joined.\n", (char*)threadReturnValue);
}

Now when you compile and run the program, you will see:

gcc -o threadBasic threadBasic.c -lpthread
./threadBasic 
PID of main process: 4610
Thread1 created with id: 3078278000
Thread start function is running for: 3078278000
The TID of thread is: 4611
PID of parent process is: 4610
Thread start function is running for: 3069885296
The TID of thread is: 4612
Thread2 created with id: 3069885296
PID of parent process is: 4610
thread-one joined.
thread-two joined.

Explanation:

Posix Thread synchronization with Semaphore

In my previous post , we have seen how to synchronize threads with Mutex. In this post we will see how to synchronize threads using semaphore. Also we will undersatand semaphore in terms of POSIX and we'll not discuss about Linux system V semaphore (will discuss in another post).

In simple terms a semaphore can be thought of a variable with two operation: wait and signal. the wait operation decrement the counter where as the signal operation increment the counter.

1. Semaphore functions

int sem_init(sem_t *sem, int pshared, unsigned int value);

It initializes a semaphore pointed to by sem. The pshared param is used to specify the type of semaphore. If it's value is 0, then the semaphore is local to the current process. Otherwise, the semaphore may be shared between processes. The value param is used to give an initial value to semaphore.

int sem_wait(sem_t * sem);

The sem_wait function atomically decreases the value of the semaphore by one. So if you call sem_wait on a semaphore with a value of 2, then the value of semaphore will be decreased to 1. If you call sem_wait on a semaphore with a value of 0, then the thread will be blocked until some other thread has incremented the value to a positive number. If multiple threads are blocked waiting on a semaphore before some other thread increment the semaphore, then only one of them will get to decrement the semaphore and continue. The thread which will get the samaphore is decided by the system and the decesion making technique may vary from system to system i.e. it may be FIFO or may be based on some priority.

int sem_post(sem_t * sem);

The sem_post function atomically increases the value of the semaphore by one. It's the reverse of sem_wait.

It's worth noting that, I have used to term "atomically" with sem_wait and sem_post operation. Atomically means that if two threads simultaneously try to increase or decrease the value of a single semaphore by 1, they do not interfere with each other.

int sem_destroy(sem_t * sem);

It destroys the semaphore pointed to by sem.

2. Code Example:

There are a number of types of semaphore. But here we will use a binary semaphore. A binary semaphore takes only values of 0 or 1 and can be used like a mutex. In fact I have replaced the mutex functions from the example in the previous post , with the semaphore functions in the below example. We'll call it semaphore.c.

semaphore.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>

sem_t  smp;
int counter = 0;

void* start_function(void* value)
{
    printf("%s is now entering the thread function.\n", (char*)value);
    sem_wait(&smp);
    counter++;
    sleep(2);
    sem_post(&smp);
    printf("%s is now leaving the thread function.\n", (char*)value);
    printf("Value of counter is: %d\n", counter);
    pthread_exit(value);
}

main()
{
    int res;
    pthread_t thread1, thread2;

    sem_init(&smp, 0, 1);

    res = pthread_create(&thread1, NULL, start_function, "Thread1");
    if (res != 0) {
        perror("Creation of thread failed");
        exit(EXIT_FAILURE);
    }

    res = pthread_create(&thread2, NULL, start_function, "Thread2");
    if (res != 0) {
        perror("Creation of thread failed");
        exit(EXIT_FAILURE);
    }
 
    res = pthread_join(thread1, NULL);
    if (res != 0) {
        perror("Joining of thread failed");
        exit(EXIT_FAILURE);
    }

    res = pthread_join(thread2, NULL);
    if (res != 0) {
        perror("Joining of thread failed");
        exit(EXIT_FAILURE);
    }

    sem_destroy(&smp);
}

Now when you compile and run the program, you will see:

gcc -o semaphore semaphore.c -lpthread
./semaphore 
Thread1 is now entering the thread function.
Thread2 is now entering the thread function.
Thread1 is now leaving the thread function.
Value of counter is: 1
Thread2 is now leaving the thread function.
Value of counter is: 2

What will happen if we don't use semaphore? Try that out.

Posix Thread synchronization with Mutex

Mutex is a synchronization technique to protect shared resources. It can be thought of a lock, which is used to protect a resource. Similarly when one thread lock a region or piece of code (normally called critical section), then no other thread can access or execute the locked code.

Here we will use POSIX mutex API to see the use of mutex lock. Below are some important POSIX functions, that we will use in our example.

1. Init Mutex

int pthread_mutex_init(pthread_mutex_t *mutex, const pthrea. d_mutexattr_t *attr);

This function initializes a mutex pointed to by mutex. The pthread_mutexattr_t param is for specifying attribute for the mutex.

2. Lock,Unlock and Destroy

int pthread_mutex_lock(pthread_mutex_t *mutex);
int pthread_mutex_unlock(pthread_mutex_t *mutex);
int pthread_mutex_destroy(pthread_mutex_t *mutex);

The above functions are self-explanatory.

3. Points to remember while using mutex.

1. No thread should attempt to lock or unlock a mutex that has not been initialized.
2. The thread that locks a mutex must be the thread that unlocks it.
3. No thread should have the mutex locked when you destroy the mutex.
4. Never call pthread_mutex_lock on a mutex that it has already locked.

4. Code Example
We wiil create small and simple program to understand Mutex. We'll call it mutex.c
mutex.c

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

pthread_mutex_t  ml;
int counter = 0;

void* start_function(void* value)
{
    printf("%s is now entering the thread function.\n", (char*)value);
    pthread_mutex_lock(&ml);
    counter++;
    sleep(2);
    pthread_mutex_unlock(&ml);
    printf("%s is now leaving the thread function.\n", (char*)value);
    printf("Value of counter is: %d\n", counter);
    pthread_exit(value);
}

main()
{
    int res;
    pthread_t thread1, thread2;

    res = pthread_mutex_init(&ml, NULL);
    if (res != 0) {
        perror("Mutex Init failed.");
        exit(EXIT_FAILURE);
    }

    res = pthread_create(&thread1, NULL, start_function, "Thread1");
    if (res != 0) {
        perror("Creation of thread failed");
        exit(EXIT_FAILURE);
    }

    res = pthread_create(&thread2, NULL, start_function, "Thread2");
    if (res != 0) {
        perror("Creation of thread failed");
        exit(EXIT_FAILURE);
    }
 
    res = pthread_join(thread1, NULL);
    if (res != 0) {
        perror("Joining of thread failed");
        exit(EXIT_FAILURE);
    }

    res = pthread_join(thread2, NULL);
    if (res != 0) {
        perror("Joining of thread failed");
        exit(EXIT_FAILURE);
    }

    pthread_mutex_destroy(&ml);
}

Now when you compile and run the program, you will see:

gcc -o mutex mutex.c -lpthread
./mutex
Thread1 is now entering the thread function.
Thread2 is now entering the thread function.
Thread1 is now leaving the thread function.
Value of counter is: 1
Thread2 is now leaving the thread function.
Value of counter is: 2

The above progarm has a critical section of code, which increases the counter. And this piece of code can be executed by multiple threads simulataneously in a multi-threaded programming. So a mutex lock is used to protect it.

What will happen if we don't use mutex? Then the output will be:

./mutex 
Thread1 is now entering the thread function.
Thread2 is now entering the thread function.
Thread2 is now leaving the thread function.
Value of counter is: 2
Thread1 is now leaving the thread function.
Value of counter is: 2

This is not the output, which you have expected. So in a multi-threaded program if you don't protect critcal section, then the result is not guaranteed.

Binary Search Tree

A Binary Search Tree(BST) is a node-based binary tree data structure which has the following properties:
1. The left subtree of a node contains only nodes with keys less than the node's key.
2. The right subtree of a node contains only nodes with keys greater than the node's key.
3. Both the left and right subtrees must also be binary search trees.

One major advantage of binary search trees over other data structures is that the related sorting algorithms and search algorithms such as in-order traversal can be very efficient.

Example


Terms Used In BST
1. Node: An item that is stored in the tree.
2. Root: The top item in the tree (50 in above case)
3. Child: Node(s) under the current node.
4. Parent: The node that is present directly above the current node. (90 is the parent of 100 in above case).
5. Leaf : A node which has no children(20 is a leaf in the above case)

Searching in a BST
1. Start at the root node.
2. If the item that you are searching for is less than the root node, move to the left child of the root node, else if the item that you are searching for is more than the root node, move to the right child of the root node and if it is equal to the root node, then you have found the item that you are looking for :)
3. Now check to see if the item that you are searching for is equal to, less than or more than the new node that you are on. Again perform step 2.
4. Repeat this process until you find the item that you are looking for or until the node doesn't have a child on the correct branch, in which case the tree doesn't contain the item which you are looking for.

Code Example

bool BinarySearchTree::search(int val)
{
    Node *next = this->root();
    while (next != NULL) {
        if (val == next->value()) {
            return true;
        } else if (val < next->value()) {
            next = next->left();
        } else {
            next = next->right();
    }
}
    //Element not found
    return false;
}

Complexity
Average Case:
If we have a tree with n nodes, then with each step we halves the value n. So the number of steps the algorithm takes equals the number of times we can halve n. By definition, this is exactly log n. So the algorithm is of O(log n)

Best case : O(1)
Worst case: O(n)

Other Operations:
The other operations that are performed on a BST are:
1. Adding an item to a binary search tree (coming soon)
2. Deleting an item from a binary search tree (coming soon)