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,
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.
The implementation in this project will be based on POSIX semaphores. The three POSIX semaphore operations are,
The data structures that share information among threads are,
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 ;
} ;
Some data is common to all threads. The threads all start when the value of smurf_start_g is made non-zero. All threads can access this data cell because,
All threads access a common barrier structure through a pointer to the structure that is copied into the barrier field of every struct T_arg.
The barrier structure contains,
Some data is per-thread. The struct T_arg has the field smurf which is set to the particular smurf number.
Find in [repo]/class/proj3 the files,
The project requires that you complete the smurf() function in the in file smurf.c. The reference, header and helper files probably do not need changes. You might be editing the Makefile to ease your project development and test.
printf("smurf %d has finished task %d\n",t_arg->smurf,task) ;in the template, should remain, so that the required output is identical for all working programs.
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
The data structures in the project are slightly sophisticated, with struct's that contain pointers to other structures. Thinking through the data structure is good, but one can also just let the types guide you. Some people misrepresent C as a weakly typed language. Maybe they mean is that C supports unlimited coercion. The type system is clear and explicit, with exact rules that will help you find the right syntax.
For instance, the call to sem_post requires an argument of type sem_t *. Following syntax rules, you can figure out what to code:
I have made use of the equivalence of the component section operator which combines the indirection operator with the selection operator,
p->f is always the same as (*p).f (Harbison & Steele 7.4.2 p 149 2nd Ed., p 213 5th Ed.)
For simple programs the loader is almost invisible. It is combined by default with the compiler, and all that some younger people might know of the loader is the ‐l option that specifies libraries in some mysterious manner.
The compiler works with the loader to compile any dot-c's into dot-o's, and to search down libraries appearing as options. This is very importantly done left to right, and if you not name things in a good order, your load will fail.
Because both modules smurf and smurf-util will use functions in the pthread library, the option -lpthread is named to the right of both. To lean more about how this option binds to a library refer to man ldconfig. On AWS Ubuntu, the pthread library resolved to,
/lib/x86_64-linux-gnu/libpthread.aand was statically linked, as ldd smurf does not show a run-time dependency (on a .so).
author: burton rosenberg
created: 15 oct 2022
update: 16 oct 2022