Sub.jam

Links
Experiments with Kernel 2.6 on a Hyperthreaded Pentium 4
Spinlocks and Semaphore
GCC-Inline-Assembly-HOWTO
Inline assembly for x86 in Linux
POSIX Threads Programming
Three classic examples in concurrency

Atomic operations
A simple "atomic increment and decrement" implementation. Adopted from Experiments with Kernel 2.6 on a Hyperthreaded Pentium 4 and Linux kernel source.

/* atomic.h */
static inline void atomic_inc(volatile int *addr)
{
       __asm__ __volatile__(
               "lock; incl %0\n\t"
               :"=m"(*addr)
               :"m"(*addr)
       );
}
  
static inline void atomic_dec(volatile int *addr)
{
      __asm__ __volatile__(
              "lock; decl %0\n\t"
              :"=m"(*addr)
              :"m"(*addr)
      );
}

Spinlocks
"A spin lock is a lock that can be held by at most one thread of execution. If a thread of execution attempts to acquire a spin lock while it is contended (already held), the thread busy loops - spins - waiting for the lock to become available. If the lock is not contended, the thread can immediately acquire the lock and continue."
--- From "Linux Kernel Development", page 137

The implementation of spinlocks is architecture dependent. Here is an example implementation from Professor Giorgio Ingargiola at Temple University.

#ifndef _SPINLOCK_H_
#define _SPINLOCK_H_

/* This code was extracted from the Linux Kernel */

#ifdef __SMP__
#define LOCK_PREFIX "lock ; "
#else
#define LOCK_PREFIX ""
#endif
struct __dummy { unsigned long a[100]; };
#define ADDR (*(volatile struct __dummy *) addr)


extern __inline__ int test_and_set_bit(int nr, volatile void * addr)
{
         int oldbit;
 
         __asm__ __volatile__( LOCK_PREFIX
                 "btsl %2,%1\n\tsbbl %0,%0"
                 :"=r" (oldbit),"=m" (ADDR)
                 :"Ir" (nr));
         return oldbit;
 }

/* This code was extracted from the Linux Kernel */

/* This implementation of spinlocks does not disable interrupts, so
   there is a danger of deadlocks. It uses busy waiting. It can be 
   used for mutual exclusion between processes. 
   The variable x below must be a pointer to a location in memory
   shared between the communicating processes
 */

#define spin_lock_init(x) {*x = 0;}
#define spin_lock(x) {while (test_and_set_bit(0,x));}
#define spin_unlock(x) {*x = 0;}

#endif

Semaphore
"Semaphores in Linux are sleeping locks. When a task attempts to acquire a semaphore that is already held, the semaphore places onto a wait queue and puts the task to sleep. The processor is then free to execute other code. When the processes holding the semaphore release the lock, one of the tasks on the wait queue is awakened so that it can then acquire the semaphore"
--- From "Linux Kernel Development", page 143


Test Programs
Adopted from book "Beginning Linux Programming".

/* concurrency example with atomic operation*/
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>
#include "atomic.h"

#define NTHREADS 5
#define NLOOPS 100000

void* thread_function( void* arg );
int count = 0;

int main()
{
    pthread_t mythread[NTHREADS];
    printf( "Number of processors: %ld\n", 
             sysconf( _SC_NPROCESSORS_ONLN ) );
    printf( "Creating %d threads (each increments Count %d times)\n",
            NTHREADS, NLOOPS );

    int i;  
    for (i=0; i<NTHREADS; i++) {
        if (pthread_create( &mythread[i], NULL, thread_function, NULL)) {
            printf( "*** Error creating thread ***\n" );
            exit( -1 );
        }
    }

    for (i=0; i<NTHREADS; i++) {
        if (pthread_join( mythread[i], NULL )) {
            printf( "*** Error joining thread ***\n" );
            exit( -2 );
        }
    }

    printf( "count: %d (should be %d)\n", count, NTHREADS*NLOOPS );
    return 0;
}

void* thread_function( void* arg )
{
    int n;
    for (n=0; n<NLOOPS; n++) {
        atomic_inc(&count);
    }
    return NULL;
}