synchronisation primitives for increment

Question

i am a begineer studying threads, i have a homework to solve a mutual exclusion problem with os161, to counts from 0 to 10000 by starting several threads that increment a common counter. i have no ideas how to use synchronisation primitives to improve it, please help.

#include <types.h>
#include <lib.h>
#include <test.h>
#include <thread.h>
#include <synch.h>

enum {
    NADDERS = 10,    /* the number of adder threads */
    NADDS   = 10000, /* the number of overall increments to perform */
};

/*
 * **********************************************************************
 * Declare the counter variable that all the adder() threads increment 
 *
 * Declaring it "volatile" instructs the compiler to always (re)read the
 * variable from memory and not optimise by removing memory references
 * and re-using the content of a register.
 */
volatile unsigned long int counter;


/*
 * Declare an array of adder counters to count per-thread
 * increments. These are used for printing statistics.
 */  
unsigned long int adder_counters[NADDERS];


/* We use a semaphore to wait for adder() threads to finish */
struct semaphore *finished;

/*
 * **********************************************************************
 * ADD YOUR OWN VARIABLES HERE AS NEEDED
 * **********************************************************************
 */

/*
 * adder()
 *
 *  Each adder thread simply keeps incrementing the counter until we
 *  hit the max value.
 *
 * **********************************************************************
 * YOU NEED TO INSERT SYNCHRONISATION PRIMITIVES APPROPRIATELY 
 * TO ENSURE COUNTING IS CORRECTLY PERFORMED.
 * **********************************************************************
 *
 * You should not re-write the existing code.
 *
 * * Only the correct number of increments are performed
 * * Ensure x+1 == x+1 
 * * Ensure that the statistics kept match the number of increments
 * * performed.
 *
 *
 */

static void adder(void * unusedpointer, unsigned long addernumber)
{
    unsigned long int a, b;
    int flag = 1;

    /*
     * Avoid unused variable warnings.
     */
    (void) unusedpointer; /* remove this line if variable is used */

    while (flag) {
        /* loop doing increments until we achieve the overall number
           of increments */

        a = counter;

        if (a < NADDS) {

            counter = counter + 1;

            b = counter;

            /* count the number of increments we perform  for statistics */
            adder_counters[addernumber]++;    

            /* check we are getting sane results */
            if (a + 1 != b) {
                kprintf("In thread %ld, %ld + 1 == %ld?\n", addernumber, a, b) ;
            }
        }
        else {
            flag = 0;
        }
    }

    /* signal the main thread we have finished and then exit */
    V(finished);

    thread_exit();
}

/*
 * math()
 *
 * This function:
 *
 * * Initialises the counter variables
 * * Creates a semaphore to wait for adder threads to complete
 * * Starts the define number of adder threads
 * * waits, prints statistics, cleans up, and exits
 */
int maths (int nargs, char ** args)
{
    int index, error;
    unsigned long int sum;

    /*
     * Avoid unused variable warnings.
     */

    (void) nargs;
    (void) args;

    /* create a semaphore to allow main thread to wait on workers */

    finished = sem_create("finished", 0);

    if (finished == NULL) {
        panic("maths: sem create failed");
    }

    /*
     * **********************************************************************
     * INSERT ANY INITIALISATION CODE YOU REQUIRE HERE
     * **********************************************************************
     */


    /*
     * Start NADDERS adder() threads.
     */


    kprintf("Starting %d adder threads\n", NADDERS);

    for (index = 0; index < NADDERS; index++) {

        error = thread_fork("adder thread", &adder, NULL, index, NULL);

        /*
         * panic() on error.
         */

        if (error) {
            panic("adder: thread_fork failed: %s\n", strerror(error));
        }
    }


    /* Wait until the adder threads complete */

    for (index = 0; index < NADDERS; index++) {
        P(finished);
    }

    kprintf("Adder threads performed %ld adds\n", counter);

    /* Print out some statistics */
    sum = 0;
    for (index = 0; index < NADDERS; index++) {
        sum += adder_counters[index];
        kprintf("Adder %d performed %ld increments.\n", 
                index, adder_counters[index]);
    }
    kprintf("The adders performed %ld increments overall\n", sum);

    /*
     * **********************************************************************
     * INSERT ANY CLEANUP CODE YOU REQUIRE HERE 
     * **********************************************************************
     */


    /* clean up the semaphore we allocated earlier */
    sem_destroy(finished);
    return 0;
}

Answer 1

Note that "counter = counter + 1" is not a atomic operation if counter lies in memory and marked as "volatile". So the add-by-one operation must be protected by some kind of mutex thing.

You can use os161's lock facility to protect the shared data among threads. The code may look like this:

// declare a global lock variable so every threads can access it
static struct lock* counter_lock;

// initialize the lock before you fork threads
counter_lock = lock_create("counter lock");

// when each thread tries to access the counter, use lock to protect it
lock_acquire(counter_lock);
counter++;
lock_release(counter_lock);

// destroy the lock after all threads are done
lock_destroy(counter_lock);

Of course, as a assignment, you must implement thess lock interfaces in /kern/thread/synch.c by yourself.

Answer 2

A couple of minor things;

1. don't use an enum for those values - use defines - an enum is for things of a similar type, e.g. fruits, error types, etc. Number of threads and number of increments are different.

2. volatile won't make any difference to anything - it merely instructs the compiler never to optimize reads away; but you're incrementing, so you're always going to read the variable before writing

And to the main question;

1. the easiest solution to this is an interlocked increment; the GCC instrincs offer such a function

Answer 3

Since you are a beginner in that domain, don't use the fancy stuff. Just protect your counter by a mutex and that is it.

// with static linkage somewhere
pthread_mutex_t countMut = PTHREAD_MUTEX_INITIALIZER;
size_t count = 0;

// in the functions
pthread_mutex_lock(&countMut);
++count;
pthread_mutex_unlock(&countMut);