Spring 2026
The purpose of this assignment is to expand your knowledge of multithreaded programming by solving a classic problem in synchronization. In class we discussed the Dining Philsophers Problem, a pedagogical example introduced by Dijkstra in 1972. For this assignment you will address a somewhat more realistic (but only slightly newer), problem.
In 1978, C. A. R. (Tony) Hoare, one of the towering figures of programming language design (and winner of the 1980 Turing Award) published Communicating Sequential Processes (CSP), a notation for rich communication patterns in message-passing programs. In Hoare’s notation, a server process that is willing to receive from any of several clients uses a selection command with input guards to specify the possible communication partners. It waits until at least one of them is ready to send to it and then chooses from among them nondeterministically. Symmetrically, a client that is willing to send to any of several servers uses a command with output guards to specify its potential partners, one of which is chosen nondeterministically. (A single guarded command is actually allowed to include both input and output options.) Significantly, communication is synchronous: both sender and receiver must agree to the exchange, at the same time, forgoing interaction (at least for now) with their other potential partners. Each synchronous interaction is called a rendezvous.
CSP-style guarded commands were the inspiration for communication in
several programming languages—notably Ada and Go.
They also influenced the design of the Unix select system
call.  It’s not immediately clear, however, how to
“pair up” senders and receivers efficiently and fairly.
In practice, it turns out that servers selecting among clients is much
more common than clients selecting among servers, and most
systems—including Ada, Go, and Unix—have chosen to implement
input guards but not output guards.
(One-sided selection is easy to implement: a client commits to a
server, sends their request, and waits to be selected.)
But conservative choices by system designers didn’t stop researchers from looking for good implementations of fully general CSP! A flurry of potential algorithms were published in the 1980s. Your task for this assignment is to choose an algorithm and implement it in shared-memory C++. The result would be suitable for the run-time system of an enhanced version of Go, with output guards.
The first fully distributed (non-centralized) algorithm for CSP with output guards is due to Bernstein. Others include the work of Buckley and Silberschatz, Bagrodia, and Ramesh. All of these are message-based, and suitable for implementation across a physically distributed network: processes use an underlying (asynchronous) message-passing layer to coordinate their CSP-level synchronous communication. In 1987, Fujimoto and Feng published an algorithm that explicitly leverages shared memory for single-machine implementations. You could choose, for this assignment, to implement their solution. Personally, I would probably build a shared-memory version of Bagrodia’s solution: it’s simpler and more clearly explained, and can be made very efficient.
You should use your solution to
Assignment 1 as the base for this assignment.
To simplify testing of your code, please name your program
“csp”.
As in assignment 1, please
employ a Makefile to compile and link your
code. Be sure that “make clean” and
“make csp” work correctly.
When run, your program should create t threads, start them running at the same time, and arrange for each to execute roughly as follows (this is pseudocode):
while time has not expired
randomly select a set of k potential communication partners, S
rendezvous(S)
pause for u microseconds (in lieu of actual computation)
See the list of command-line arguments (below) for more on
t, k, and u.
Within the rendezvous routine, a thread should arrange to
communicate with exactly one of the potential partners in S.
Optionally (under control of a command-line argument; see below),
before either thread returns from the rendezvous
routine, each should print to stderr a log message
consisting of its thread id, the thread id of its partner, and a newline.
(You will need to use a global lock on the log routine to prevent
characters from different threads from interleaving.
During testing, you may find it helpful to redirect stderr
to a file.)
If your program is correct, both messages for a given rendezvous
in the log will appear after the messages for any previous
rendezvous of either partner and before the messages for any subsequent
rendezvous of either partner. This means that if you filter the log
through grep -w i, for some thread id
i, the messages for any given rendezvous should always be
adjacent.
For the purposes of the base assignment, we will not distinguish between senders and receivers; threads simply want to pair up and “communicate.” To avoid the possibility of deadlock, with each thread waiting for communication with a set of partners none of which has mutual interest, you should arrange for thread 1 to always be willing to communicate with everyone.
At the end of each test run, your program should calculate, for each thread
i, what percentage of its rendezvous operations ended up
partnering with each of its peers
j∉{1, i}.
For each thread, it should then calculate the standard deviation of
these percentages and the unsigned difference between the largest and
smallest percentages.
Finally, it should find the largest difference and the average standard
deviation across all threads, and print these two values to
stderr.
If your algorithm is fair, both values should be very close to zero in a
long program run.
Given that your goal in this assignment is “merely” to generate correct behavior while permitting concurrency and potentially ensuring fairness, we will not be measuring any sort of parallel speedup. If you are in CSC 458, however,
As in assignment 1, 258 students can fulfill the 458 requirements for extra credit.
To turn in your code, follow the turnin
directions. Be sure to include a good README.pdf
file. Among other things, you’ll want to provide a
narrative explanation of the pairing
algorithm you chose and, if you adapted it from a message-passing
algorithm in the literature, how you made it work in shared
memory.
If you have questions, post to the
discussion
group in Blackboard.
Your csp program should accept the following command-line
arguments:
-d num |
time to run, in seconds (default 3) |
-t num |
number of threads (default 16) |
-k num |
number of potential partners in each selection (default t/2) |
-u num |
μs delay between rendezvous in each thread (default 100) |
-l |
log each rendezvous if specified (otherwise don’t) |
You may find the standard getopt library helpful to
parse command-line parameters.
(Much better packages are available on the web, but getopt
should suffice for this project.)
To generate pseudo-random numbers (for building sets of potential
partners), I recommend the random_r library routine.
To better test your program, you may want to arrange for it to use a
different “seed” for the random number generator on every
run—e.g., by passing the time of day to
srandom_r.
To pause, a thread should call the Linux usleep function,
passing the value of the -u command-line argument.
If you choose to implement Bagrodia’s algorithm, you will want to
use shared memory in lieu of underlying asynchronous messages.
I recommend a t×t array, C of
“channel status” values, where
C[i, j] (i ≠ j)
indicates the status of communication between threads i and
j. Each value will indicate which thread currently has
what Bagrodia calls the “token” and whether it has refused
an interaction since receiving it.
I suggest storing the status of each thread in a separate array, so
changes to the status of a given thread can be made atomically (as
opposed to having to make a change to every associated channel value).
To allow you to distinguish not only between threads that are idle
(looking for a partner) and threads that are active (doing
something else—not looking for a partner) but also between
successive instances of these states, you may want the status of a
thread to be a serial number, where even means idle and odd
means active.
(If the “color” [fine-grain status] of a thread needs to be
visible to peers, you could use the two lowest order bits of
the serial number to differentiate among the four possible
colors.)
Note that if serial numbers are 64-bit numbers, they won’t overflow
in your lifetime.
You’ll want to use the alignas storage specifier in
C++ to ensure that the compiler allocates employs separate cache lines
for variables shared by separate sets of threads—thereby avoiding
false sharing (in which threads suffer logically unnecessary
cache misses because peers have modified disjoint parts of the same
line).
The possibility that threads may pause for significant time between attempted interactions means that one cannot send a “message” to a thread and be sure of a prompt reply. In a shared-memory implementation, however, one can attempt to retract a message that has been sent to an active (non-interested) peer. One might, for example, (1) check the status of a peer and, if it’s idle, (2) use a CAS to change the channel status of one’s communication with that peer; then (3) double-check the status of the peer. If the peer is now active, one can try to use a CAS to restore the channel status to its previous value. Meanwhile, it’s possible that the peer will have used a CAS to accept the message, allowing it to act. Because both threads use CAS, you can arrange for only one to succeed, and for both to tell what happened.
Inside your rendezvous routine, you will probably need to
actively poll the status of multiple communication channels.
In an initial version of your code (or even a final version, for 258),
you might poll the channels of all t−1 peers, so you can
refuse interaction with peers who are not among your current potential
partners. To ensure O(k)
work per rendezvous, however (as required
for 458), you may need to make your current set of potential partners
globally visible, so peers not in that set can avoid sending (or
can retract) any messages you would otherwise need to refuse
(the work of
Fujimoto
and Feng, mentioned above, does this.)
If you want to read a multi-word collection of data (e.g., the state of a thread, including its potential partner set) atomically and efficiently, you may want to consider using a sequence lock (described in Section 6.2 of Shared-Memory Synchronization). Alternatively, you could consider replacing the t×t array of channel status values with per-thread queues of incoming messages. Each queue, of course, would itself need to be properly synchronized.
When logging, one way to ensure that both threads log their rendezvous before either continues would be to have each perform the idle-to-active state transition for the other.
Back to the course home page
Last Change:
14 February 2026