Go Smurfs Project

A Smurf

Go Smurfs Project

by: burt rosenberg
at: october 2025

Overview

This project continues goals the exploration of concurrency and concurrency harnessing primitives.

We will be using a barrier construct to coordinate the completion of several tasks by our friendly cohort of Smurfs. Each Smurf carries out a sequence of tasks, which each Smurf taking a various amount of time for each task. However, all Smurfs must finish their first task before any Smurf begins its second task. And so on: all Smurfs must finish their i-th task before beginning their i+1-th task.

The barrier construction described in Allen B. Downey's The Little Book of Semaphores gives us the mechanism. It uses the class PV semaphore. The previous project gave exercises in the mutex and the condition variable upon which signal/wait can be performed. Here we look at semaphores, a concurrency primitive introduced as the PV semaphore by computer science Edgar Dijkstra in 1963 (see references).

The goals for this project are,

The PV semaphore, and the POSIX version.
The barrier pattern for concurrency.
Techniques of sharing data among threads in a single process space, including,
1. Common data: the data location is shared by all threads and,
2. Thread-local data: which have separate data locations for each thread.

POSIX semaphores

The implementation in this project will be based on POSIX semaphores. The three POSIX semaphore operations are,

sem_open to initialize the semaphore,
sem_wait to preform the P operation,
sem_post to perform the V operation.

The POSIX semaphore is defined slightly different than the classical PV semaphore. If a thread will wait on the semaphore, the classical PV semaphore decrements then waits whereas the POSIX semaphore waits then decrements. As a result, a count which could be associated to a POSIX semaphore is never negative.

Data structures


extern int smurf_start_g ;

struct Barrier {
	unsigned int count ;
	unsigned int n ;
 	sem_t * mutex ;
 	sem_t * turnstile ;
 	sem_t * turnstile2 ;
} ;

struct T_arg {
 	unsigned int smurf ;
 	unsigned int task_num ;
 	struct Barrier * barrier ;
} ;


  T_arg            Barrier
  
+-------+  +------>+-------+
|   1   |  |  +--->| count |
+-------+  |  |    +-------+
|   n   |  |  |    |   n   |
+-------+  |  |    +-------+        +-------+
|   *------+  |    |   *----------->| mutex |
+-------+     |    +-------+        +-------
              |    |  *---------+
+-------+     |    +-------+    |   +-------+
|   2   |     |    |  *------+  +-->| turn  |
+-------+     |    +-------+ |      +-------+          
|   n   |     |              |
+-------+     |              |      +-------+    
|   *---------+              +----->| turn2 |
+-------+                           +-------+    
          
    .
    .
    .

The data structures that share information among threads are,

The smurf_start_g global.
The struct Barrier which includes all variables to implement the barrier,
The struct T_arg which is the argument to the thread.

Globals

A global variable is in the common memory shared by all threads. The variable smurf_start_g is global.

It is shared by all threads.
The lifetime of this variable contains the lifetime of the thread.
The variable is in scope for the thread function.

Thread Common

All threads access a common struct Barrier structure. A pointer to the structure is copied into the barrier field of the struct T_arg.

The barrier structure contains,

The semaphore mutex to implement mutual exclusion on the data structure,
Semaphores turnstile and turnstile2 to implement the boundary,
The count value and the target value for count, n.

Thread Local

A new struct T_arg is allocated for each thread. The the field smurf has a thread local value, different for each thread.

The Objective

Implement the reusable barrier solution found in section 3.7.5 of Downey's book.

Implement this in the function void * smurf() in the file smurf-thread.c.

Except for the Makefile, the other files should not need changes.

Here is an example of the output. The left is a run from the template files as given in the class folder, your starting point. To the right is a completed solution. Depending on how the scheduler schedules your threads your milage may vary.


THE RESULT WITHOUT BARRIERS
---------------------------
Get ready, Smurfs!
3
2
1
GO SMURFS!!!
smurf 2 has finished task 1
smurf 5 has finished task 1
smurf 2 has finished task 2
smurf 3 has finished task 1
smurf 1 has finished task 1
smurf 2 has finished task 3
smurf 4 has finished task 1
smurf 5 has finished task 2
smurf 4 has finished task 2
smurf 3 has finished task 2
smurf 4 has finished task 3
smurf 2 has finished task 4
smurf 1 has finished task 2
smurf 5 has finished task 3
smurf 4 has finished task 4
smurf 3 has finished task 3
smurf 2 has finished task 5
smurf 4 has finished task 5
smurf 5 has finished task 4
smurf 1 has finished task 3
smurf 1 has finished task 4
smurf 1 has finished task 5
smurf 3 has finished task 4
smurf 3 has finished task 5
smurf 5 has finished task 5


THE RESULT WITH BARRIERS
------------------------
Get ready, Smurfs!
3
2
1
GO SMURFS!!!
smurf 2 has finished task 1
smurf 5 has finished task 1
smurf 3 has finished task 1
smurf 1 has finished task 1
smurf 4 has finished task 1
smurf 4 has finished task 2
smurf 2 has finished task 2
smurf 5 has finished task 2
smurf 3 has finished task 2
smurf 1 has finished task 2
smurf 4 has finished task 3
smurf 2 has finished task 3
smurf 5 has finished task 3
smurf 3 has finished task 3
smurf 1 has finished task 3
smurf 1 has finished task 4
smurf 4 has finished task 4
smurf 2 has finished task 4
smurf 5 has finished task 4
smurf 3 has finished task 4
smurf 3 has finished task 5
smurf 1 has finished task 5
smurf 4 has finished task 5
smurf 2 has finished task 5
smurf 5 has finished task 5

Man page

NAME
    smurf --- smurfs do their tasks
      
SYNOPSIS

    smurf [-v] [-k number-of-tasks] number-of-smurfs

DESCRIPTION

    A number of smurfs complete a number of tasks. All the smurfs must finish 
    the i-th task before any begin the i+1-th task. The amount of time a smurf 
    finishes a given task depends on both the smurf and the task.
 
OPTIONS

    -v verbose
    -k the number of tasks. The default is 5 tasks.
     
ARGUMENTS

    The number of smurfs.

OUTPUT
  
    The output for the non-verbose mode is given precisely in the template.
    
HISTORY

    New for csc421-231. Second offering csc421-261.
    MacOS does not support unnamed semaphores. Changed sem_init to sem_open.

References.

An early discussion of PV semaphores appears in Over de sequentialiteit van procesbeschrijvingen, EWD35 1963(?), (in english)
Another formulation form appears in Over Seinpalen, EWD74 1965(?), without translation.

This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.

author: burton rosenberg
created: 15 oct 2022
update: 19 oct 2025