Condition Variable and Measure the Speed of Context Switching

December 27, 2010

The pthread tutorial https://computing.llnl.gov/tutorials/pthreads/#ConVarOverview gives a concise but clear description about condition variable:

  • While mutexes implement synchronization by controlling thread access to data, condition variables allow threads to synchronize based upon the actual value of data.
  • A condition variable is always used in conjunction with a mutex lock.

And a representative sequence for using condition variables is shown below.

https://computing.llnl.gov/tutorials/pthreads/#ConVarOverview

Two important points from above illustration:

  1. pthread_cond_wait unlocks the mutex so  another thread can have the chance to signal the condition variable.
  2. When signaled, pthread_cond_wait locks the mutex. (If the mutex is locked by another thread, pthread_cond_wait has to wait for the mutex before returning.)

To better understand condition variable, let us take a look at the answer to a Google interview question: how to measure the speed of context switch.  The answer was given in:

http://forum.codecall.net/c-c/31589-c-program-measures-speed-context-switch-unix-linux.html

Ah, UNIX stuff. Essentially you would create a function to alternate between persistant thread states, set lock and start/wakeup/sleep conditions plus a counter.

uint32_t COUNTER;
pthread_mutex_t LOCK;
pthread_mutex_t START;
pthread_cond_t CONDITION;
void * threads (void * unused) {
    pthread_mutex_lock(&START);
    pthread_mutex_unlock(&START);
    pthread_mutex_lock(&LOCK);
    if (COUNTER > 0) {
        pthread_cond_signal(&CONDITION);
    }
    for (;;) {
        COUNTER++;
        pthread_cond_wait(&CONDITION, &LOCK);
        pthread_cond_signal(&CONDITION);
    }
    pthread_mutex_unlock(&LOCK);
}

Next we create persistant threads t1 and t2 which are unlocked (awoken), and we roughly sleep one second to let them do their firing. (rough approximate of one second, granularity is different among platforms/clocks)

pthread_mutex_lock(&START);
    COUNTER = 0;
    pthread_create(&t1, NULL, threads, NULL);
    pthread_create(&t2, NULL, threads, NULL);
    pthread_detach(t1);
    pthread_detach(t2);
    myTime = tTimer();
    pthread_mutex_unlock(&START);
    sleep(1);
    // Lock both simulaneous threads
    pthread_mutex_lock(&LOCK);
    //Normalize the result in second precision
    myTime = tTimer() - myTime / 1000;
Here follows my explanation on how above code works:
At first, only one persistent thread (say t1) can lock LOCK, so t2 waits. t1 then fulfills the condition (COUNTER++) but waits.  Since the main thread sleeps once it lets persistent threads go, so only the other persistent thread (t2) can be waken up (one switching). t2 signals CONDITION, but t1 cannot wait right now because t2 holds LOCK, and t1′s wait invocation have to wait until t2 unlocks LOCK.  Therefore, t2 goes on increase COUNTER and waits.  Since the wait invocation unlocks LOCK, so t1 now wakes up and signals CONDITION.  Similarly, t2 cannot wake up right now but has to wait until t1 increase COUNTER and actively waits again.

Using C++ mutable Keyword

December 27, 2010

The keyword mutable is used to allow a particular data member of const object to be modified.

In this interesting post, two examples are given:

class Employee {
public:
    Employee(const std::string & name) 
        : _name(name), _access_count(0) { }
    void set_name(const std::string & name) {
        _name = name;
    }
    std::string get_name() const {
        _access_count++;
        return _name;
    }
    int get_access_count() const { return _access_count; }

private:
    std::string _name;
    mutable int _access_count;
};

As a more complex example, you might want to cache the results of an expensive operation:

class MathObject {
public:
    MathObject() : pi_cached(false) { }
    double pi() const {
        if( ! pi_cached ) {
            /* This is an insanely slow way to calculate pi. */
            pi = 4;
            for(long step = 3; step < 1000000000; step += 4) {
                pi += ((-4.0/(double)step) + (4.0/((double)step+2)));
            }
            pi_cached = true;
        }
        return pi;
    }
private:
    mutable bool pi_cached;
    mutable double pi;
};

Another example is the C++ encapsulation of a blocking queue, which is the intermediate between producers and consumers:

class BlockingQueue {
public:
    bool IsEmpty() const
    {
        MutexLocker locker(m_mutex);
        return m_queue.empty();
    } 
private:
    size_t m_max_elements;
    std::deque<T> m_queue;

    mutable Mutex m_mutex;
    ConditionVariable m_cond_not_empty;
    ConditionVariable m_cond_not_full;
};

POSIX Thread and Semaphore on Darwin and Cygwin

December 4, 2010

Darwin (here I mean Mac OS X up to 10.6.5) supports pthread and semaphore.  However, it is notable that only named semaphores (sem_open and sem_close) are supported, unnamed semaphores (sem_init and sem_destroy) are not.

Cygwin supports full pthread and semaphore.

To make your program compatible with both platforms, use the following macros (http://lists.apple.com/archives/darwin-kernel/2005/Dec/msg00022.html):

#include <unistd.h>

#if ((_POSIX_SEMAPHORES - 200112L) >= 0)
/* This platform fully supports POSIX semaphores */
#else
#if defined(__APPLE__)
/* This platform can support POSIX named semaphores, but not unnamed semaphores */
#else
/* this platform requires that I Google code for P/V semaphores and include it here */
#endif
#endif

Also, you need

#include <pthread.h>  // for POSIX thread mutex and condition variables
#include <semaphore.h>  // for POSIX semaphore

On both platforms, you can use g++ -lpthread to build programs using POSIX thread and semaphore.


Follow

Get every new post delivered to your Inbox.

Join 28 other followers