Concurrency

You will study about concurrency and the effects of concurrent programs in this lesson.

We'll cover the following

Another main theme of this course is concurrency. We use this conceptual term to refer to a host of problems that arise, and must be addressed, when working on many things at once (i.e., concurrently) in the same program. The problems of concurrency arose first within the operating system itself; as you can see in the examples on virtualization, the OS is juggling many things at once, first running one process, then another, and so forth. As it turns out, doing so leads to some deep and interesting problems.

Multi-threaded programs

Unfortunately, the problems of concurrency are no longer limited just to the OS itself. Indeed, modern multi-threaded programs exhibit the same problems. Let us demonstrate with an example of a multi-threaded program:

Press + to interact
#include <stdio.h>

#include <stdlib.h>

#include "common.h"

#include "common_threads.h"



volatile int counter = 0; 

int loops;



void *worker(void *arg) {

    int i;

    for (i = 0; i < loops; i++) {

	    counter++;

    }

    return NULL;

}



int main(int argc, char *argv[]) {

    if (argc != 2) { 

        fprintf(stderr, "usage: threads <loops>\n"); 

        exit(1); 

    } 

    loops = atoi(argv[1]);

    pthread_t p1, p2;

    printf("Initial value : %d\n", counter);

    Pthread_create(&p1, NULL, worker, NULL); 

    Pthread_create(&p2, NULL, worker, NULL);

    Pthread_join(p1, NULL);

    Pthread_join(p2, NULL);

    printf("Final value   : %d\n", counter);

    return 0;

}

Although you might not fully understand this example at the moment (and we’ll learn a lot more about it in later chapters, in the section of the course on concurrency), the basic idea is simple. The main program creates two threads using Pthread_create().

You can think of a thread as a function running within the same memory space as other functions, with more than one of them active at a time. In this example, each thread starts running in a routine called worker(), in which it simply increments a counter in a loop for loops number of times.

Running threads.c

Try running the code below!

#ifndef __common_threads_h__
#define __common_threads_h__

#include <pthread.h>
#include <assert.h>
#include <sched.h>

#ifdef __linux__
#include <semaphore.h>
#endif

#define Pthread_create(thread, attr, start_routine, arg) assert(pthread_create(thread, attr, start_routine, arg) == 0);
#define Pthread_join(thread, value_ptr)                  assert(pthread_join(thread, value_ptr) == 0);

#define Pthread_mutex_lock(m)                            assert(pthread_mutex_lock(m) == 0);
#define Pthread_mutex_unlock(m)                          assert(pthread_mutex_unlock(m) == 0);
#define Pthread_cond_signal(cond)                        assert(pthread_cond_signal(cond) == 0);
#define Pthread_cond_wait(cond, mutex)                   assert(pthread_cond_wait(cond, mutex) == 0);

#define Mutex_init(m)                                    assert(pthread_mutex_init(m, NULL) == 0);
#define Mutex_lock(m)                                    assert(pthread_mutex_lock(m) == 0);
#define Mutex_unlock(m)                                  assert(pthread_mutex_unlock(m) == 0);
#define Cond_init(cond)                                  assert(pthread_cond_init(cond, NULL) == 0);
#define Cond_signal(cond)                                assert(pthread_cond_signal(cond) == 0);
#define Cond_wait(cond, mutex)                           assert(pthread_cond_wait(cond, mutex) == 0);

#ifdef __linux__
#define Sem_init(sem, value)                             assert(sem_init(sem, 0, value) == 0);
#define Sem_wait(sem)                                    assert(sem_wait(sem) == 0);
#define Sem_post(sem)                                    assert(sem_post(sem) == 0);
#endif // __linux__

#endif // __common_threads_h__

Below is a transcript of what happens when we run this program with the input value for the variable loops set to 1000. The value of loops determines how many times each of the two workers will increment the shared counter in a loop. When the program is run with the value of loops set to 1000, what do you expect the final value of counter to be?

Press + to interact
prompt> gcc -o thread threads.c -Wall -pthread
prompt> ./thread 1000
Initial value : 0
Final value   : 2000

As you probably guessed, when the two threads are finished, the final value of the counter is 2000, as each thread incremented the counter 1000 times. Indeed, when the input value of loops is set to NN, we would expect the final output of the program to be 2N2N. But life is not so simple, as it turns out. Let’s run the same program, but with higher values for loops, and see what happens:

Press + to interact
prompt> ./thread 100000
Initial value : 0
Final value   : 143012          // huh??
prompt> ./thread 100000
Initial value : 0
Final value   : 137298          // what the??

In this run, when we gave an input value of 100,000, instead of getting a final value of 200,000, we instead first get 143,012. Then, when we run the program a second time, we not only again get the wrong value, but also a different value than the last time. In fact, if you run the program over and over with high values of loops, you may find that sometimes you even get the right answer! So, why is this happening?

As it turns out, the reason for these odd and unusual outcomes relate to how instructions are executed, which is one at a time. Unfortunately, a key part of the program above, where the shared counter is incremented, takes three instructions: one to load the value of the counter from memory into a register, one to increment it, and one to store it back into memory. Because these three instructions do not execute atomically (all at once), strange things can happen. It is this problem of concurrency that we will address in great detail in the second part of this course.

THE CRUX OF THE PROBLEM: HOW TO BUILD CORRECT CONCURRENT PROGRAMS

When there are many concurrently executing threads within the same memory space, how can we build a correctly working program? What primitives are needed from the OS? What mechanisms should be provided by the hardware? How can we use them to solve the problems of concurrency?

Create a free account to view this lesson.

Continue your learning journey with a 14-day free trial.

By signing up, you agree to Educative's Terms of Service and Privacy Policy