~dcoles/+junk/condition-example

/**
 * condition_example - Example of using condition variables
 *
 * Copyright (c) 2012, David Coles <coles.david@gmail.com>
 *
 * Permission is hereby granted, free of charge, to any person obtaining a 
 * copy of this software and associated documentation files (the "Software"), 
 * to deal in the Software without restriction, including without limitation 
 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 
 * and/or sell copies of the Software, and to permit persons to whom the 
 * Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in 
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 
 * DEALINGS IN THE SOFTWARE.
 */


// Expose POSIX1.2001/SUSv3 feature
#define _XOPEN_SOURCE 600

// Just some headers to get us started
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <pthread.h>


// Making things safer
// ===================

// Here we have a simple stack structure which is not thread safe.
#include "stack.h"

// Lets fix that by using a *mutex* (short for mutual exclusion) object to 
// prevent more than one thread messing with our stack.
// Mutexes are typically used to protect some sort of shared state to ensure 
// that the interaction between two threads never leave us in an inconsistent 
// state.

static pthread_mutex_t s_mutex = PTHREAD_MUTEX_INITIALIZER;

bool sstack_push(struct stack *s, int value)
{
    // Lock the mutex
    pthread_mutex_lock(&s_mutex);

    bool result = stack_push(s, value);

    // Unlock the mutex, THEN return the result (very important!)
    pthread_mutex_unlock(&s_mutex);
    return result;
}

bool sstack_pop(struct stack *s, int *value)
{
    // Lock the mutex
    pthread_mutex_lock(&s_mutex);

    bool result = stack_pop(s, value);

    // Unlock the mutex, THEN return the result (very important!)
    pthread_mutex_unlock(&s_mutex);
    return result;
}


// Much better! Now, provided we only use these functions we can't have a race 
// condition where two separate threads of execution can mess with the stack 
// at the same time.


// Test 1: A tight polling loop
// ============================

// Now here's a problem. What if one thread wants to read more items off the 
// stack than are available at that moment?

/**
 * Sleep for a random amount of time up to 100ms
 */
static void zzzz()
{
    static const int SLEEP_MAX = 100;
    int sleep_ms = (random()%SLEEP_MAX);
    usleep(sleep_ms*1000);
}

// How many items we want to read
static const int WANT = 10;

// Maximum size of our stack
static const int STACK_SIZE = 50;

// A very simple function
static int f(int x)
{
    return 42*x;
}

static void *test_1_reader(void *p_my_stack)
{
    // Get the stack passed when we created the thread
    struct stack *my_stack = (struct stack *)p_my_stack;

    for(int i=0; i<WANT; i++) {
        bool has_item = false;
        int value = 0;
        // 1st attempt. Lets just poll the stack, in other words we just keep 
        // trying to pop items until we succeed!
        while(!has_item) {
            printf("<- Trying to pop item #%d\n", i);
            has_item = sstack_pop(my_stack, &value);
        }
        printf("<- Got item #%d: %d\n", i, value);
    }

    // Required for the thread
    return NULL;
}

static void test_1()
{
    // Create a stack
    struct stack *my_stack = stack_new(STACK_SIZE);

    // Start the reader thread
    pthread_t reader;
    pthread_create(&reader, NULL, test_1_reader, my_stack);

    // Push items to our reader thread
    for(int i=0; i<WANT; i++) {
        int value = f(i);
        printf("-> Pushing item #%d: %d\n", i, value);
        sstack_push(my_stack, value);
        // And just for fun, lets sleep here for a random amount of time...
        zzzz();
    }

    // Wait for the reader to finish
    pthread_join(reader, NULL);
}

// Try running this program with an argument of 1 to see what happens!
// $ ./condition_example 1

// <('.'<)  <('.')>  (>'.')>

// Woah! That reader thread did a lot of work! Even on my crappy old laptop it 
// flooded my console with how many times we tried to pop items off the stack.
// What we've just written is called a *tight* or *busy* loop - we're doing a 
// lot of work even though we're not getting much done. Usually this isn't a 
// good thing since we eat up time which could be better used doing useful 
// things.  Lets see if we can do a bit better...


// Test 2: Sleeping
// ================

// Hmm... Let's see if we can fix that tight loop by sleeping for a little bit 
// of time between runs...

static void *test_2_reader(void *p_my_stack)
{
    // Get the stack passed when we created the thread
    struct stack *my_stack = (struct stack *)p_my_stack;

    for(int i=0; i<WANT; i++) {
        int value = 0;
        bool has_item = false;
        while(!has_item) {
        // 2nd attempt. We'll poll, but lets sleep a little between polls
            printf("<- Trying to pop item #%d\n", i);
            has_item = sstack_pop(my_stack, &value);
            usleep(50*1000); // 50ms
        }
        printf("<- Got item #%d: %d\n", i, value);
    }

    // Required for the thread
    return NULL;
}

// This is basically the same as before
static void test_2()
{
    // Create a stack
    struct stack *my_stack = stack_new(STACK_SIZE);

    // Start the reader thread
    pthread_t reader;
    pthread_create(&reader, NULL, test_2_reader, my_stack);

    // Push items to our reader thread
    for(int i=0; i<WANT; i++) {
        int value = f(i);
        printf("-> Pushing item #%d: %d\n", i, value);
        sstack_push(my_stack, value);
        // And just for fun, lets sleep here for a random amount of time...
        zzzz();
    }

    // Wait for the reader to finish
    pthread_join(reader, NULL);
}

// Try running this program with an argument of 2 to see what happens!
// $ ./condition_example 2

// ... ~ ... ~ ...  ><((('>

// Well this is certainly better than the last time. At least this time I 
// haven't pegged a CPU core to 100% and flooded your terminal with several 
// hundred lines of useless text! There's only a couple of unsuccessful pops.
// How well does this technique work? Well it's pretty simple and if the time 
// you spend sleeping is close to time between items being pushed it's pretty 
// efficient. But if you sleep too long your program will run too long and if 
// you don't sleep long enough it almost is as bad as our first case. Hmmm...


// Test 3: Conditional Love
// ========================

// Wouldn't it be nice if our reader thread could sleep for exactly as long as 
// it took for an item to be pushed. Thankfully there is a solution - it's 
// called a *Condition variable*!

// A condition variable allows a thread to sleep until it's woken up when a 
// another thread notifies it of an interesting state. For this reason's 
// always associated with a mutex.

// Lets create a condition variable that will be signaled whenever our stack 
// is not empty...

static pthread_cond_t s_cond_not_empty = PTHREAD_COND_INITIALIZER;

// We're also going to modify our thread-safe stack functions a bit...

static bool sstack_push_and_signal(struct stack *s, int value)
{
    // Lock the mutex
    pthread_mutex_lock(&s_mutex);

    bool result = stack_push(s, value);

    // Signal that the stack is not empty
    pthread_cond_signal(&s_cond_not_empty);

    // Unlock the mutex, THEN return the result (very important!)
    pthread_mutex_unlock(&s_mutex);
    return result;
}

static void sstack_pop_or_wait(struct stack *s, int *value)
{
    // Lock the mutex
    pthread_mutex_lock(&s_mutex);

    // Lets check if the stack is not empty
    while(!s->size > 0) {
        // If it is we'll wait until another thread wakes us when it's not
        pthread_cond_wait(&s_cond_not_empty, &s_mutex);
    }

    // We can now pop from the since we waited until it wasn't empty
    bool result = stack_pop(s, value);
    assert(result);

    // Unlock the mutex
    pthread_mutex_unlock(&s_mutex);
    // Since we wait until we get a value we always succeed
}

static void *test_3_reader(void *p_my_stack)
{
    // Get the stack passed when we created the thread
    struct stack *my_stack = (struct stack *)p_my_stack;

    for(int i=0; i<WANT; i++) {
        int value = 0;
        // 3nd attempt. Notice this time we don't have to retry since 
        // sstack_pop_or_wait will always return an item.
        printf("<- Trying to pop item #%d\n", i);
        sstack_pop_or_wait(my_stack, &value);
        printf("<- Got item #%d: %d\n", i, value);
    }

    // Required for the thread
    return NULL;
}

// This is basically the same as before
static void test_3()
{
    // Create a stack
    struct stack *my_stack = stack_new(STACK_SIZE);

    // Start the reader thread
    pthread_t reader;
    pthread_create(&reader, NULL, test_3_reader, my_stack);

    // Push items to our reader thread
    for(int i=0; i<WANT; i++) {
        int value = f(i);
        printf("-> Pushing item #%d: %d\n", i, value);
        sstack_push_and_signal(my_stack, value);
        // And just for fun, lets sleep here for a random amount of time...
        zzzz();
    }

    // Wait for the reader to finish
    pthread_join(reader, NULL);
}

// Try running this program with an argument of 2 to see what happens!
// $ ./condition_example 3

// -_-'

// Wow! Look at that. As soon as the writer pushes a value on to the stack the 
// reader immediately wakes up and prints it out. Even with that pesky random 
// sleep in there.

// Now I cheated a bit by making the stack size far bigger than it needed to 
// be. An exercise for the reader would be to extend this stack so that 
// push_and_signal would use another condition variable to check the stack is 
// not full.


// Thanks for reading :)


// Below here is just the boring main function that parses arguments and then 
// calls our function.

static void print_usage()
{
    fprintf(stderr, "USAGE: condition_example N\n");
    fprintf(stderr, "\tN=1: Tight loop\n");
    fprintf(stderr, "\tN=2: Polling with sleep\n");
    fprintf(stderr, "\tN=3: Using condition variables\n");
}

int main(int argc, char* argv[])
{
    // Use a fixed RNG seed to get reproducible results
    srandom(0xdeadbeef);

    if(argc > 1) {
        char* test = argv[1];

        if(strcmp(test, "1") == 0) {
            printf("Starting 1st Test: Tight Loop\n");
            test_1();
            printf("Done!\n");
        } else if(strcmp(test, "2") == 0) {
            printf("Starting 2nd Test: Polling with sleep\n");
            test_2();
            printf("Done!\n");
        } else if(strcmp(test, "3") == 0) {
            printf("Starting 3rd Test: Using condition variables\n");
            test_3();
            printf("Done!\n");
        } else {
            // Any other value
            fprintf(stderr, "'%s' is not a valid test.\n\n", test);
            print_usage();
        }
    } else {
        fprintf(stderr, "No test selected.\n\n");
        print_usage();
    }

    return 0;
}

// That's all folks!