Pthreads Overview

Here's a quick overview of the calls available to a programmer using Pthreads (both the standard Pthreads API and GNU extensions). It's intended to be as brief as possible while being (i) descriptive and (ii) not just a list of all the available calls. The links are to the relevant man pages on linux.die.net.

Note: The "NP" at the end of certain functions and macros stands for "non-portable". They are GNU extensions, accessed by e.g. #define-ing _GNU_SOURCE.

• Thread creation and attributes
• Thread operations
• Fork/thread termination handlers
• Thread termination and cancellation
• Signal operations
• Scheduling and CPU time/affinity
• Thread-specific data and one-time-only operations
• Locking mechanisms
• Mutexes
• Read/write locks
• Spin locks
• Memory barriers
• Condition variables

Thread creation and attributes

A thread is created with pthread_create(). Thread attributes can be specified when it is created with a pthread_attr_t structure, which gets initialized with pthread_attr_init() and destroyed with pthread_attr_destroy(). A copy of a thread's current attributes can be obtained with the GNU-specific pthread_getattr_np().

The pthread_attr_t can have the following operations performed on it:

• The thread's initial CPU affinity mask can be accessed/modified with pthread_attr_getaffinity_np() and pthread_attr_setaffinity_np().
• Whether the thread is detached or joinable can be accessed/modified with pthread_attr_getdetachstate() and pthread_attr_setdetachstate().
• The size of the guard area (area at the end of the stack that will generate a segmentation fault on access, to detect stack overflow) can be accessed/modified with pthread_attr_getguardsize() and pthread_attr_setguardsize() (but note that guard sizes are rounded up to page boundaries when applied).
• Whether the thread gets its scheduling policy and parameters (see the next two points) by inheriting them from the current thread or explicitly from the values set in the attribute structure can be accessed/modified with pthread_attr_getinheritsched() and pthread_attr_setinheritsched().
• The scheduling policy the new thread starts with (assuming it's been set to have this explicitly specified; see above) can be accessed/modified with pthread_attr_getschedpolicy() and pthread_attr_setschedpolicy().
• The scheduling parameters (i.e. priority, unless more parameters are added in future) the new thread starts with (assuming it's been set to have this explicitly specified; see above) can be accessed/modified with pthread_attr_getschedparam() and pthread_attr_setschedparam().
• Note: Only system-level contention is available on Linux. Whether the scheduling contention scope of the thread is at system-level (i.e. the thread's priority is compared with every other thread on the system when allocating CPU time) or process-level (i.e. the thread's priority is only compared with other threads in the process; the process itself must get CPU time before the scheduler decides if the thread deserves CPU time) can be accessed/modified by pthread_attr_getscope() and pthread_attr_setscope().
• If a thread needs to run with a stack with a specific location and size, this can be accessed/modified with pthread_attr_getstack() and pthread_attr_setstack(). The size alone can be accessed/modified with pthread_attr_getstacksize() and pthread_attr_setstacksize(). (The functions for accessing and modifying the address are pthread_attr_getstackaddr() and pthread_attr_setstackaddr(), but they are obsolete).

Thread operations

A thread can get its own ID via pthread_self(). Two thread IDs can be tested to see if they refer to the same thread with pthread_equal() (don't just use ==).

Fork/thread termination handlers

You can specify functions to be executed immediately before and after a call to fork() (in both parent and child) with pthread_atfork(). This is useful in e.g. a threaded library, since the child process a fork() creates only consists of a single thread.

Thread clean-up handlers (analogous to atexit()/on_exit()) can be registered/unregistered with pthread_cleanup_push() and pthread_cleanup_pop(). They will be called if the thread is cancelled or it exits using pthread_exit() (but not if it just returns from the thread routine).

If you're worried about asynchronous cancellation between pushing/popping clean-up handlers (and who isn't!) you can use the GNU-specific pthread_cleanup_push_defer_np() and pthread_cleanup_pop_restore_np() instead, which (i) set the thread cancellation type to deferred (see Thread termination) and (ii) restore the previous thread cancellation type, respectively.

Thread termination and cancellation

A thread can exit from a thread at any time using pthread_exit().

A thread that is joinable can be joined with pthread_join(), which will block until the thread has finished. A thread can be moved to the detached state with pthread_detach() (the reverse cannot be done). Normally, an attempt to join will block until the thread has finished, but this blocking behaviour can be avoided with the GNU-specific pthread_tryjoin_np() and pthread_timedjoin_np().

One primitive way of terminating a thread is to cancel it with pthread_cancel(). Whether the thread is able to be cancelled in this way can be controlled with pthread_setcancelstate(), and whether such a cancellation is deferred or delivered at a cancellation point can be controlled with pthread_setcanceltype(). Within a thread, an "artificial" cancellation point can be generated by calling pthread_testcancel().

Signal operations

A signal can be sent to a specific thread using pthread_kill() or pthread_sigqueue(), analogous to the normal kill() and sigqueue functions.

If you're using LinuxThreads (you'll probably know if you are; most systems are using the Native POSIX Thread Library now, for which this function is irrelevant) you can use pthread_kill_other_threads_np() to send SIGKILL to all other threads, usually to correct a deficiency whereby other threads are not terminated when calling one of the exec() family of functions.

The signal mask for a thread can be accessed/modified with pthread_sigmask(), which uses a sigset_t that can be manipulated with the usual sigsetops.

Scheduling and CPU time/affinity

The clock_t of a specific thread (e.g. for a call to clock_gettime()) can be accessed with pthread_getcpuclockid().

A thread's scheduling policy and parameters (i.e. priority) can be accessed/modified using pthread_setschedparam() and pthread_getschedparam(). The priority alone can be set using pthread_setschedprio(). The CPU can be released with pthread_yield(), which is analogous to sched_yield() but for an individual thread.

Note: This is irrelevant on Linux, and is ignored. The concurrency (a hint to the system about how many lower-level entities (e.g. kernel threads) to assign) of a process can be accessed/modified with pthread_getconcurrency() and pthread_setconcurrency().

The CPU affinity of a thread can be accessed/modified after creation with the GNU-specific pthread_getaffinity_np() and pthread_setaffinity_np().

Thread-specific data and one-time-only operations

Once-only initialization can be achieved using pthread_once(). This requires a pthread_once_t which is initialized by assignment from the PTHREAD_ONCE_INIT macro.

Thread-local data is provided through a pthread_key_t, which is initialized/freed using pthread_key_create() and pthread_key_delete(). The value can then be accessed/modified using pthread_getspecific() and pthread_setspecific().

Locking mechanisms

Pthreads provides three types of locking mechanism - mutexes, read/write locks and spin locks.

Mutexes

These are the most common types of lock, as well as the most flexible. They are also the only locks that can be used with condition variables.

A mutex is initialized/freed with pthread_mutex_init() and pthread_mutex_destroy(). You can also initialize a statically allocated mutex using the PTHREAD_MUTEX_INITIALIZER macro or, as GNU extensions, PTHREAD_RECURSIVE_MUTEX_INITIALIZER_NP, PTHREAD_ERRORCHECK_MUTEX_INITIALIZER_NP or PTHREAD_ADAPTIVE_MUTEX_INITIALIZER_NP.

Mutexes can optionally be initialized with attributes in the form of a pthread_mutexattr_t, initialized and freed using pthread_mutexattr_init() and pthread_mutexattr_destroy(). The pthread_mutexattr_t can have the following operations performed on it:

• The type of mutex used can be accessed/modified using pthread_mutexattr_gettype() and pthread_mutexattr_settype(). A mutex can be normal, error-checking (re-locking the mutex from the owning thread is an error) or recursive (relocking the mutex from the owning thread is fine).
• Whether a mutex can be used from multiple processes can be accessed/modified using pthread_mutexattr_getpshared() and pthread_mutexattr_setpshared().
• To prevent priority inversion, the behaviour of a thread's scheduling while a mutex is locked and/or blocking higher priority threads can be accessed/modified with pthread_mutexattr_getprotocol() and pthread_mutexattr_setprotocol(). The priority ceiling of a mutex can be accessed/modified with pthread_mutexattr_getprioceiling() and pthread_mutexattr_setprioceiling().

The priority ceiling of a thread can be accessed/modified after creation using pthread_mutex_getprioceiling() and pthread_mutex_setprioceiling(). Mutexes can be locked using any of pthread_mutex_lock(), pthread_mutex_timedlock() or pthread_mutex_trylock(). They can be unlocked with pthread_mutex_unlock().

Read/write locks

Read/write locks can provide performance benefits over mutexes since they allow any number of threads to access the protected resource with "read-only" behaviour, while granting exclusive access to threads that want to be able to modify the resource. They have some disadvantages over mutexes though, namely that they can't be configured to avoid priority inversion and they can't be used with condition variables.

A read/write lock is initialized/freed with pthread_rwlock_init() and pthread_rwlock_destroy(). You can initialize a statically allocated read/write lock with PTHREAD_RWLOCK_INITIALIZER or, as a GNU extension, PTHREAD_RWLOCK_WRITER_NONRECURSIVE_INITIALIZER_NP.

Read/write locks can optionally be initialized with attributes in the form of a pthread_rwlockattr_t, initialized and freed using pthread_rwlockattr_init() and pthread_rwlockattr_destroy().

Currently, the only attribute a read/write lock can be given is whether it can be used by multiple processes. This setting can be accessed/modified with pthread_rwlockattr_getpshared() and pthread_rwlockattr_setpshared().

A read lock can be obtained using one of pthread_rwlock_rdlock(), pthread_rwlock_timedrdlock() or pthread_rwlock_tryrdlock(). The corresponding functions for obtaining the write lock are pthread_rwlock_timedwrlock(), pthread_rwlock_trywrlock() and pthread_rwlock_wrlock(). The lock can be unlocked from either type of lock with pthread_rwlock_unlock().

Spin locks

These are the simplest form of locks, and are generally only used when you know that other threads will only be holding the locks for a short amount of time (e.g. not whilst performing blocking I/O).

A spin lock is initialized/freed with pthread_spin_init() andpthread_spin_destroy(). There is no associated attributes structure (but they can be made available to other processes upon initialization).

The functions for locking/unlocking a spin lock are pthread_spin_lock(), pthread_spin_trylock() and pthread_spin_unlock().

Memory barriers

These allow threads to synchronize at a pre-defined point of execution.

They are initialized and freed using pthread_barrier_init() and pthread_barrier_destroy().

A memory barrier can optionally be initialized with attributes in the form of a pthread_barrierattr_t, initialized and freed using pthread_barrierattr_init() and pthread_barrierattr_destroy().

Currently, the only attribute a memory barrier can be given is whether it can be used by multiple processes. This property can be accessed/modified using pthread_barrierattr_getpshared() andpthread_barrierattr_setpshared().

Once created, threads can synchronize at a barrier using pthread_barrier_wait(). There is no such thing as a "trywait" or "timedwait" function.

Condition variables

Condition variables can be used to signal changes in an application's state to other threads. They must be used with an associated pthread_mutex_t.

Condition variables are initialized/freed using pthread_cond_init() and pthread_cond_destroy().

A condition variable can optionally be initialized with attributes in the form of a pthread_condattr_t, initialized and freed using pthread_condattr_destroy() and pthread_condattr_init(). You can initialize a statically allocated condition variable using PTHREAD_COND_INITIALIZER.

Whether the condition variable is able to be used by multiple processes can be accessed/modified using pthread_condattr_getpshared() and pthread_condattr_setpshared().

The clock used (identified by a clockid_t) for timed waits on a condition variable can be accessed/modified using pthread_condattr_getclock() and pthread_condattr_setclock() (though it cannot be set to a CPU clock).

Threads can wait for changes in conditions using pthread_cond_timedwait() and pthread_cond_wait().

Threads can signal changes in conditions using pthread_cond_broadcast() and pthread_cond_signal().

Running a program and interacting with it.

Here's an example of a function, ccl_popen3(), that opens a program with the standard streams that you want to write to/read from open. It's from a while ago, I'll brush it up later (in theory).

Either way, ccl_popen3() is the money function, and main() demonstrates usage. Compiles on my machine with gcc popen3.c -o popen3 -std=gnu99 -Wall -Wextra -Werror.

#include <stdlib.h>
#include <unistd.h>

#define READ_END  0
#define WRITE_END 1
#define NENDS     2

#define OPEN_STDIN  (1 << STDIN_FILENO)
#define OPEN_STDOUT (1 << STDOUT_FILENO)
#define OPEN_STDERR (1 << STDERR_FILENO)
#define OPEN_ALL    (OPEN_STDIN | OPEN_STDOUT | OPEN_STDERR)
#define MAX_STREAMS 3



__attribute__((noreturn))
static void popen3_child(const char *exe,
                         char *const argv[],
                         int shell,
                         int streams,
                         int pipes[MAX_STREAMS][NENDS])
{
    for (int i = 0 ; i < MAX_STREAMS ; i++)
        if (streams & (1 << i)) {
            close(pipes[i][i == STDIN_FILENO ?
                           WRITE_END : READ_END]);
            if (dup2(pipes[i][i == STDIN_FILENO
                              ? READ_END : WRITE_END],
                     i) == -1)
                exit(127);
        }

    if (shell)
        execvp(exe, argv);
    else
        execv(exe, argv);

    /* Any return from execv()/execvp() is an error. */
    exit(127);
}

static void popen3_parent(int streams,
                          int fds[],
                          int pipes[][NENDS])
{
    for (int i = 0 ; i < MAX_STREAMS ; i++)
        if (streams & (1 << i)) {
            close(pipes[i][i == STDIN_FILENO ?
                           READ_END : WRITE_END]);
            fds[i] = pipes[i][i == STDIN_FILENO ?
                              WRITE_END : READ_END];
        }
}



/*
 * TODO: (i) different functions for child and parent, (ii)
 * close original pipe fd's.
 */
pid_t ccl_popen3(const char *exe,
                 char *const argv[],
                 int shell,
                 int streams,
                 int fds[])
{
    int pipes[MAX_STREAMS][NENDS] = {{-1, -1},
                                     {-1, -1},
                                     {-1, -1}};

    for (int i = 0 ; i < MAX_STREAMS ; i++)
        if ((streams & (1 << i)) && (pipe(pipes[i]) == -1))
            goto err;

    pid_t pid = fork();
    switch (pid) {
    case -1:  /* error */
        goto err;
    case 0:   /* child */
        popen3_child(exe, argv, shell, streams, pipes);
        break;
    default:  /* parent */
        popen3_parent(streams, fds, pipes);
        return pid;
    }

 err:
    for (int p = 0 ; p < MAX_STREAMS ; p++)
        for (int e = 0 ; e < NENDS ; e++)
            if (pipes[p][e] != -1)
                close(pipes[p][e]);

    return -1;
}



#include <poll.h>
#include <stdio.h>

void ccl_poll_input(int fds[3])
{
    struct pollfd pollfds[2] = {
        { .fd = fds[STDOUT_FILENO], .events = POLLIN },
        { .fd = fds[STDERR_FILENO], .events = POLLIN }
    };

    int running = 1;
    while (running) {
        int res = poll(pollfds, 2, -1);

        if (res == -1) {
            perror("poll()");
            exit(EXIT_FAILURE);
        }

        struct pollfd *pfd = pollfds;
        for (int i = 0 ; i < 2 ; i++, pfd++) {
            if (pfd->revents & (POLLERR | POLLNVAL)) {
                fprintf(stderr, "poll() error\n");
                exit(EXIT_FAILURE);
            }

            if (pfd->revents & (POLLIN | POLLHUP)) {
                char buf[1024];
                ssize_t nread = read(pfd->fd,
                                     buf, sizeof(buf) - 1);

                if (nread == -1) {
                    perror("read()");
                    exit(EXIT_FAILURE);
                }

                if (nread == 0) {
                    /* EOF */
                    running = 0;
                    break;
                }

                buf[nread] = '\0';
                printf(" Read from %d: \"%s\"\n",
                       pfd->fd, buf);
            }
        }
    }
}



#include <stdio.h>
#include <string.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <poll.h>

int main(void)
{
    int grep_fds[3];

    const char *exe = "/bin/grep";
    char *const argv[] =
      {"grep", "-h", "XX", "jkfdsl", "-", NULL};
    
    pid_t grep_pid =
      ccl_popen3(exe, argv, 0, OPEN_ALL, grep_fds);

    if (grep_pid == -1) {
        perror("ccl_popen3()");
        exit(EXIT_FAILURE);
    }

    /* Write some input to grep's standard input, and close
     * it. */
    const char *input = "abcd\ngg9XXp\nDqdXXpird\n";
    if (write(grep_fds[STDIN_FILENO], input, strlen(input))
        != (ssize_t)strlen(input)) {
        perror("write()");
        exit(EXIT_FAILURE);
    }
    close(grep_fds[STDIN_FILENO]);

    printf("out: %d, err: %d\n", grep_fds[STDOUT_FILENO],
           grep_fds[STDERR_FILENO]);

    struct pollfd pollfds[2] = {
        { .fd = grep_fds[STDOUT_FILENO], .events = POLLIN },
        { .fd = grep_fds[STDERR_FILENO], .events = POLLIN }
    };

    int running = 1;
    while (running) {
        int res = poll(pollfds, 2, -1);

        if (res == -1) {
            perror("poll()");
            exit(EXIT_FAILURE);
        }

        struct pollfd *pfd = pollfds;
        for (int i = 0 ; i < 2 ; i++, pfd++) {
            if (pfd->revents & (POLLERR | POLLNVAL)) {
                fprintf(stderr, "poll() error\n");
                exit(EXIT_FAILURE);
            }

            if (pfd->revents & (POLLIN | POLLHUP)) {
                char buf[1024];
                ssize_t nread = read(pfd->fd,
                                     buf, sizeof(buf) - 1);

                if (nread == -1) {
                    perror("read()");
                    exit(EXIT_FAILURE);
                }

                if (nread == 0) {
                    /* EOF */
                    running = 0;
                    break;
                }

                buf[nread] = '\0';
                printf(" Read from %d: \"%s\"\n",
                       pfd->fd, buf);
            }
        }
    }

    int grep_status;
    if (waitpid(grep_pid, &grep_status, 0) == -1) {
        perror("waitpid()");
        exit(EXIT_FAILURE);
    }

    if (WIFEXITED(grep_status))
        printf("grep exited with status %d\n",
               WEXITSTATUS(grep_status));
    else
        // TODO: This better.
        printf("grep terminated abnormally\n");
    return EXIT_SUCCESS;
}

C on Linux Kickstart

Overview

So, there are plenty of resources for learning how to program in C/C++ (see the end of this post) but here's a quick guide on how to get off to a good start with the practical matters. It's the sort of stuff I wish someone had pointed out to me when I started, since it would have made my life a lot easier.

While graphical IDE's may make your life easier for large projects, a knowledge of how the core tools used in making programs fit together is essential if you're going to go anywhere with your programming; where more complex tools let you down, you can pick yourself up if you know what they're doing behind the scenes. This is why this guide will start you off using the compiler on the command line.

The command line

If you're not already used to using the command line, have a look at this chapter of Introduction to Linux: A Hands On Guide. You'll need to get comfortable with moving around the file system, creating and listing the contents of directories, etc.

What to use & install

The two absolute essentials you'll need are (i) a text editor and (ii) a compiler. You might already be a fan of the text editors vi or emacs, both popular with programmers, but they can have a steep learning curve. If you've got a graphical Linux distribution it will have a default text editor that will doubtless have syntax highlighting (this makes certain parts of your source code stand out). The defaults for Gnome, Kde and Xfce are gedit, kate and mousepad respectively. So from the command-line, you can open e.g. the file program.c from a Gnome desktop by typing the following at a terminal:

    gedit program.c

As for a complier, by far the most popular option is GCC. On Debian/Ubuntu, you can install this, as well as all the development libraries you'll need, by installing the build-essential package (as root):

    apt-get install build-essential

On Fedora/Red Hat, the same effect can be achieved by:

    yum groupinstall "Development Tools" "Development Libraries"

If you have another distribution and you're not sure what to install, ask around; if you can compile the main.c program in the next section, you have what you need.

How to compile programs

To give us something to work with, open your text editor of choice, write the following into it (copy & paste if you like/you get errors) and save it as main.c:

#include <stdio.h>

int main()
{
    printf("hello world\n");
}

We won't go into what the statements mean (I'll leave that to the tutorials at the end of this post) but this gives us something practical to work with.
Now, you can't run this file directly, you first have to compile it into a file that you can. The simplest way to do this is:

    gcc main.c

This will produce a file called a.out. You can run this in the usual way (from where you are just after compiling, type ./a.out). If you like, you can specify the output file to be something different by using -o filename (e.g. gcc main.c -o main).

However, you will make your programming life easier if you never compile your programs like this; it will lead you down a bad path. When you compile programs like this, you will let GCC ignore many potentially dangerous practices. Luckily, GCC has a way to alert you to these in the form of its warning options - they control what situations GCC will warn you about, and what situations it will silently ignore. The defaults are pretty lax, and while they may be useful in compiling legacy code you know to work and just want to compile, when learning and/or writing new code, you want your compiler to be as strict as possible. There are an endless variety of options you can fine-tune this strictness to your heart's content if you like, but for now there are three that will serve you very well: -Wall, -Wextra and -Werror. The first two of these enable a group of common warnings, and the last turns all warnings (that would usually just cause the compiler to emit a message about the offending construct) into errors that cause the compiler to flat-out refuse to finish compiling your program until you've sorted the error out.

These warnings are there for a reason; use them. They will prevent you from making mistakes that will lead to bugs that will just needlessly waste your time. A quite common forum post from new programmers reads essentially "here's a program that doesn't work the way I expect - help!". At least 50% of the time, I can copy + paste the program and compile with -Wall -Wextra and the result will tell me what they've done wrong, without even having to look at their program. Why spend time searching for errors when you can let your compiler do it for you?

In short, always compile your programs with at least -Wall -Werror - try it now with our main.c above:

    gcc main.c -o main -Wall -Werror

You'll notice I've not included -Wextra in the above command-line. -Wextra can be a bit harsh, especially on new programmers; use it to double-check a program that's not behaving as you expect, or for any code you hope to give to others (including posting it on a forum) for a thorough sanity-check first.

Dealing with error messages

There is one golden rule when dealing with error messages. At first you (like me) will probably ignore it, only to learn through bitter experience that it applies no matter how experienced you are. Luckily, it's very simple:

• Always deal with the very first error message emitted by the compiler.

The reason for this is quite simple: once the compiler sees something wrong, it's very likely that later things will make even less sense to it than they ordinarily would. So find the first error the compiler spots, fix it, then try recompiling. Often you will fix several error messages by fixing one actual error.

The error messages emitted by GCC are always in the format file:line[:position]: ERROR MESSAGE. If you've tried compiling the above main.c with -Wall you may have already seen the following:

    main.c:6:1: warning: control reaches end of non-void function

This lets us know that the error occurred in main.c on line 6 (and was estimated to be at character 1, but that's rarely useful). Exactly what this means you'll learn in time, but in this case we can fix this by turning main.c into:

#include <stdio.h>

int main()
{
    printf("hello world\n");
    return 0;
}

Try recompiling and you'll see no error message.

When you see an error message you don't understand, don't ignore it or start turning warning options off until it goes away. A quick copy-and-paste it into Google (leaving out any specifics like file names, function names and line numbers) will usually tell you exactly what's gone wrong:

    main.c:6:1: warning: control reaches end of non-void function

Where to go from here

There are several good introductions to programming in C on the web, my favourite being this one.

When you get stuck, forums can be invaluable - there is a Linux-specific forum with an active programming section here, and active forums for C and C++ programming here and here, respectively. You'll get good, fast responses if you include (i) code that demonstrates the problem you're having, (ii) what you think the code should do and (iii) what's going wrong.

Seeding Randomness

Note: This post is also a demonstration of a simple use of Pthread memory barriers.

Recently I read a discussion on choosing a suitable seed for srand() - ideally you want something random to seed srand() with, and one of the obvious suggestions was to use the current time. This lead me to wonder just how "good" a source of randomness the time is, and how likely two processes/threads are to find the time to be the same in practice.

The most coarse source of time is time(), which has a resolution of one second. Obviously, any program executed more often than every second is going to see the time to be the same as some other program.

Two much better functions in this respect are gettimeofday() and the newer clock_gettime(); they have a best resolution of one millisecond and one nanosecond, respectively (whether they actually have this resolution depends on your machine). But how likely are they to return the same time?

This being the sort of thing that keeps me up late into the night, I set up a program that attempts to spot two calls to one of these functions returning an identical time. My first attempt at just calling either one repeatedly and seeing whether the times were the same showed gettimeofday() frequently came out the same if called consecutively, whereas I couldn't get clock_gettime() to produce the same result twice. (Obviously since this is a practical (i.e. fudged) test, this result depends on my hardware, OS and possibly how my kernel is configured.) Anyway, undeterred I came up with a scheme using threads.

See the listing at the end of the program (with SYNC undefined) to see the attempt at just using raw threads. On my machine (stock Ubuntu 12.04 on a Core i5) with NUM_THREADS set to 300 (which was about as high as I could get it before getting memory allocation errors in pthread_create()) this program had to run 449 times (on average) to generate one run where only a single match for the time was found.

But we can do better than this. Creating a thread takes time - time during which the OS's unpredictable scheduling reigns supreme and with an iron fist, leading our threads to unpredictably diverge. We can force them all to synchronize at a point much closer to the call to get the time by using a Pthread memory barrier. We initialize the barrier with a count of NUM_THREADS, meaning any thread waiting at the barrier will wait until NUM_THREADS threads (i.e. all of our threads) are also waiting at the barrier before it is allowed to continue execution.* From here, there's a lot less logical "distance" to the clock_gettime() call, so we should be able to generate the same time more easily. The barriers in the listing at the end are enabled by passing the -DSYNC flag to gcc when compiling. Note that we get the time as soon as possible after getting past the barrier, and then check whether our barrier wait was successful, to keep the distance between getting past the barrier and getting the time as low as possible.

Using memory barriers, the number of runs we needed to make to get one match was reduced from 449 to 89. Using optimization (-O3) reduced this a little further to 62 times. So, my best attempt results in the same time being returned once every (at best) 62 * 300 = 18600 threads.

So, the conclusion? If I'm ever after high-quality random numbers for security purposes, I'll turn to /dev/random and/or /dev/urandom, but for any other application clock_gettime() is much simpler and should be more than enough for me.

/*
 * same.c
 *
 * See if we can get clock_gettime() to generate two times
 * that are the the same. Can be compiled with -DSYNC to use
 * a memory barrier in the thread to try and force the same
 * time to be retrieved.
 *
 * Compile with (where # is the number of threads you want):
 *
 *   $ gcc same.c -DNUM_THREADS=# [-DSYNC] -pthread -lrt
 *
 * Copyright (C) 2012 John Graham. This source code is
 * released into the public domain; you may use it as you
 * wish.
 */

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>

/* Array into which threads place their times. */
struct timespec times[NUM_THREADS];

#ifdef SYNC
/* Memory barrier at which threads sync (if applicable)
 * immediately before getting the time. */
pthread_barrier_t barrier;
#endif

void *thread(void *arg)
{
  /* Our argument is the index into 'times'. */
  intptr_t index = *(intptr_t *) arg;

#ifdef SYNC
  /* Wait at the barrier. This will block until all
   * threads are at the same point in their execution. */
  int pret = pthread_barrier_wait(&barrier);
#endif

  /* Get the time ASAP, *then* check the return value from
   * pthread_barrier_wait(). */
  if (clock_gettime(CLOCK_MONOTONIC, &times[index]) != 0) {
    perror("getting time");
    exit(EXIT_FAILURE);
  }
#ifdef SYNC
  if (pret != 0 && pret != PTHREAD_BARRIER_SERIAL_THREAD) {
    fprintf(stderr,
            "Waiting at barrier: %s\n", strerror(pret));
    exit(EXIT_FAILURE);
  }
#endif

  return NULL;
}

/* See if *any* of the entries in 'times' are identical. */
int compare_times(void)
{
  int nsame = 0;
  int i, j;
  for (i = 0; i < NUM_THREADS; i++)
    for (j = i + 1; j < NUM_THREADS; j++)
      if (times[i].tv_sec == times[j].tv_sec &&
          times[i].tv_nsec == times[j].tv_nsec)
        nsame++;
  return nsame;
}

int main()
{
  int i;   /* Generic index. */
  intptr_t nums[NUM_THREADS]; /* Indices to pass to
     * threads. */
  pthread_t threads[NUM_THREADS];

#ifdef SYNC
  if (pthread_barrier_init(&barrier,
                           NULL, NUM_THREADS) != 0) {
    perror("pthread_barrier_init()");
    exit(EXIT_FAILURE);
  }
#endif

  /* Start all our threads, initializing indices as we go
   * along. */
  for (i = 0; i < NUM_THREADS; i++) {
    nums[i] = i;
    if (pthread_create(&threads[i],
                       NULL, thread, &nums[i]) != 0) {
      perror("pthread_create()");
      exit(EXIT_FAILURE);
    }
  }

  /* Wait until all threads have finished. */
  for (i = 0; i < NUM_THREADS; i++) {
    if (pthread_join(threads[i], NULL) != 0) {
      perror("pthread_join()");
      exit(EXIT_FAILURE);
    }
  }

  int times = compare_times();
  printf("%d matches\n", times);
  return times;
}

* If you want a demonstration that the memory barrier is working, initialize it with a count of NUM_THREADS+1. Since this many threads will never wait on the barrier, every thread will sit and wait there indefinitely, doomed to spend the rest of their sad, sorry lives waiting for a thread that doesn't exist (it won't even wake up for EINTR, unless this kills the program).