Home > Articles > Operating Systems, Server > Linux/UNIX/Open Source

  • Print
  • + Share This
Like this article? We recommend

Like this article? We recommend

One for You, One for Me

So far, we’ve examined only the most basic form of concurrency—the worker-thread model, in which a background process is created to do some work and then return.

A lot of the time this approach can be useful, but more often you want your processes to communicate with each other. Shared memory is one way of doing this, but it has issues with consistency.

Many operations you’re likely to want involve a read > modify > write cycle. An example might be updating a counter. Consider what happens if you have two different processes updating the same counter at the same time:

  1. Process A reads the counter value of 1.
  2. Process B reads the counter value of 1.
  3. Process A updates the counter and writes 2.
  4. Process B updates the counter value and write 2.

The counter started at 1, was incremented twice, and now reads 2. This kind of bug can be very difficult to track down. Much of the time, your code may work; the two processes will be at different states and won’t try to update things at the same time.

The simplest solution is to put a lock around the shared memory. Each process will first try to acquire the lock and then perform the update. Our sequence thus becomes the following:

  1. Process A acquires the lock.
  2. Process B tries to acquire the lock, and enters a wait state.
  3. Process A loads the counter value of 1.
  4. Process A write the counter value of 1.
  5. Process A releases the lock.
  6. Process B wakes up with the lock.
  7. Process B loads the counter value of 1.
  8. Process B write the counter value of 1.
  9. Process B releases the lock.

The System V IPC mechanism used to implement locks of this nature is the semaphore, and the same holds with POSIX. A POSIX semaphore has the same semantics as a System V semaphore, so switching between them is easy, but the POSIX function syntax is more readable.

The kind of lock described here is often called a mutex (short for mutual exclusion). A semaphore is a more generalized form of a mutex. To understand semaphores, consider a bucket full of (semaphore) flags. Only people who have a flag in their hands are allowed to do something. When a person arrives, he or she grabs a flag from the bucket and does something. When finished, the person drops the flag back into the bucket. If someone else arrives while the bucket is empty, he sits and waits until a flag is available. If multiple people are waiting, they all grab at the first flag that arrives, but only one will get it. A mutex is a bucket of this nature that only contains one flag.

We use a set of five operations to interact with semaphores:

  • sem_open(2) creates a new semaphore, or opens one created by another process.
  • sem_close(2) tells the system that we’re done with a semaphore.
  • sem_post(2) puts a flag into the bucket.
  • sem_wait(2) retrieves a flag, blocking until one is available.
  • sem_trywait(2) retrieves a flag, failing if none is available.

The following code shows an implementation of the counter example:

#include <stdlib.h>
#include <stdio.h>
#include <sys/types.h>
#include <sys/mman.h>
#include <unistd.h>
#include <semaphore.h>



int main(void)
{
    //Counter in shared memory region:
    int * counter = mmap(0,
            sizeof(int),
            PROT_READ | PROT_WRITE,
              MAP_SHARED | MAP_ANON,
              -1,
            0);
    *counter = 0;
    //Semaphore for locking:
    sem_t * lock = sem_open("example_lock", O_CREAT | O_EXCL, 0600, 1);
    //Do the same thing in two processes
    fork();
    //Random number from 0-255
    unsigned int max = random() & 255;
    //Increment the counter max times
    for(unsigned int i=0; i<max ; i++)
    {
        sem_wait(lock);
        (*counter)++;
        sem_post(lock);
    }
    printf("Added %u to counter. Final value is: %d\n", max,*counter);
    return 0;
}

As before, a few things stop this example from being production-quality code. The semaphore operations are all interruptible by signals, so failing to check the return values for error conditions can have some nasty side effects.

Try commenting out the sem_wait and sem_post lines and then running the program again; you might be surprised by the results. On a single-processor machine, the chance of one of the processes being preempted in the middle of a read > increment > write sequence is very small. If you’re really lucky, your compiler might write the (*counter)++ operation as a set of instructions that are executed atomically.

  • + Share This
  • 🔖 Save To Your Account