Synchronize a program with semaphores

Question

Together with a colleague, I have the task to synchronize a "handwritten" C program using semaphores. the task was to move 1 in an int[4] field round-robin with the other entries being 0.

#include "workers.h"
#include "semaphores.h"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <errno.h>





//-----------------------------------------------------------------------------
// global variables (all volatile!)
//-----------------------------------------------------------------------------

#define SIZE 4

volatile int ring[4];
volatile int von_position;
volatile int nach_position;
volatile semaphore semaphoren[4];
//-----------------------------------------------------------------------------
// call text_setup() once before starting the test
//-----------------------------------------------------------------------------

void test_setup(void) {
  printf("Test Setup\n");
for(int i= 0; i<4; i++){
  semaphoren[i] = sem_init(1);
}
von_position = 0;
nach_position = 1;
  readers=0; // maximal 1 (nicht veraendern!)
  writers=4; // maximal 19 
}

//-----------------------------------------------------------------------------
// test_end() is called after all workers have finished
//-----------------------------------------------------------------------------

void test_end(void) {
    for(int i = 0; i<4; i++){
        printf("%i ", ring[i]);
}

}

//-----------------------------------------------------------------------------
// those 4 workers execute in parallel
//-----------------------------------------------------------------------------

void writer(long my_id) {
for(int i =0; i<500; i++){
    sem_p(semaphoren[my_id]);
    printf("Writer %i :, %i>%i \n",(int) my_id, von_position, nach_position); // ***
    ring[von_position] = 0;
    ring[nach_position] = 1;
    sem_v(semaphoren[my_id]);
    if(von_position == 3){von_position = 0;}
    else von_position ++;
    if(nach_position == 3) {nach_position = 0;}
    else nach_position ++;

}

}

void reader(long my_id) {
}

That has been derived from an old ring buffer program given to us. It uses 4 "writer" processes.

Problem is that when finished, there is always a single one in the array, but in ca. 10 out of 500 runs we get intermediately output of the printf() (*** in the code) like 3 > 0, in the next line 0 < 2 or so.

Tried much, but no success, so far.

Hope I get a few good tips

Answer 1

This program reads and writes concurrently to shared non-atomic variables. It thus exhibits race conditions, and its behavior is undefined according to the C-standard. Assuming you changed volatile to _Atomic, and exchanged all loads/stores to the atomic variables with atomic_load_explicit(x, memory_order_seq_cst)/atomic_store_explicit(x, memory_order_seq_cst), your

void writer(long my_id)
{
  for(int i =0; i<500; i++)
  {
    sem_p(semaphoren[my_id]);
    printf("Writer %i :, %i>%i \n",(int) my_id, von_position, nach_position); 
    ring[von_position] = 0;
    ring[nach_position] = 1;
    sem_v(semaphoren[my_id]);
    if(von_position == 3){von_position = 0;}
    else von_position ++;
    if(nach_position == 3) {nach_position = 0;}
    else nach_position ++;
  }
}

could still be interrupted between the sem_v() and the first if(), between the if() and the else, and so forth. In particular, the first writer() can be interrupted after incrementing von_position (modulo 4), and before incrementing nach_position. Thus the next writer would see von_position == nach_position, and if that writer is interrupted in the same place, the next writer will see von_position > nach_position, and so forth.

Practically, you should move the sem_v() to the end of the loop.

Answer 2

The example code does not "move" a 1, instead it just stores 0's and 1's. My guess is that the threads are supposed move elements in a synchronized manner. Thread 0 moves from ring[0] to ring[1], thread 1 moves from ring[1] to ring[2], ... thread 3 moves from ring[3] to ring[0]. The threads can all read and all write in parallel, but synchronization is needed to prevent conflicts between reading and writing. Using 4 semaphores seems like a simple way to implement this.