Assignment 10 Synchronization

CPSC 213 – Assignment 10
Synchronization

After an 8-hour, no-penalty, grace period, no late assignments accepted.
Part 2: Thursday, April 4, 11:59pm
After an 72-hour, no-penalty, grace period (i.e., until Sunday, April 7, 11:59 pm),
no late assignments accepted.
Goal
The goal of this assignment is to give you experience writing concurrent programs. Writing
concurrent code that works correctly is hard. Debugging concurrent code that doesn’t work
correctly is much harder. These skills are becoming increasing important. This assignment
introduces you to this set of challenges by having you solve a number of small isolated
concurrency problems and then larger concurrent programming problems.
What to Do
In Part 1, you will solve some simple, isolated concurrency problems and one larger problem, the
classic bounded-buffer, producer-consumer problem.
In Part 2, you will solve two additional, well-know concurrency problems using uthreads,
mutexes and condition variables and then solve the bounded-buffer problem from Part 1 (and the
others from this part for Bonus) using semaphores. The first is a well known problem and the
second is our variation of somewhat-less well-know problem from a wonderful free book called
The Little Book of Semaphores by Allen B. Downey. You can download the book if you like, but
it is not necessary (and probably not that helpful) for this assignment. While these problems are
toys, they were designed to model specific types of real-world synchronization problems that
show up in real concurrent systems such as operating systems and video games, etc.
For each part, your program will consist of a solution to the concurrency puzzle and a test
harness that creates a set of threads and instruments your code to collect information that you can
use to convince yourself (and us) that you have implemented the problem correctly. Bugs will
either be in the form of incorrect results (i.e., violating the stated constraints) or deadlock (i.e.,
your program hangs). The problems are kept as simple as possible.
The code you need for this assignment is in www.ugrad.cs.ubc.ca/~cs213/cur/assignments/a10/
code.zip. There you will find the complete uthread package, including the implementation of
monitors and condition variables and semaphores. You will also find a Makefile that you will
use to build the various parts of this assignment and skeleton files for each of the questions with
some parts implemented for you and some parts, listed as TODO, left for you.
NOTE: Synchronization bugs introduce non-determinism into programs, which means that they
may produce different results each time they are run, even on the exact same input. This also
means that a program with a synchronization bug might execute correctly sometimes and so to
be sure that your a program is bug free it is necessary to execute it many times. You must do
take this step when testing your code for this assignment. The Unix command-line shells
provides ways to automate this task; you might find it useful to investigate how to do this.
For example, in tcsh (i.e., the tee shell) you can type this to execute the program q1 100 times.
repeat 100 ./q1
And in the bash shell:
for n in {1..4}; do ./q1; done
Part 1
Question 1.1: Simple Thread Ordering with Join [5%]
Modify the program part1/q1.c by adding calls to uthread_join (and making no other
changes) so that it always prints the lines “zero” to “three” in order; i.e., its output must
always be the following.
zero
one
two
three
------
Question 1.2: Simple Mutual Exclusion [5%]
Modify the program part1/q2.c to use a mutex so that the program is free of race conditions
(i.e., so that you have guaranteed mutual exclusion for all critical sections in the code) and thus
that it always prints “cnt = 0” when it terminates.
Question 1.3: Simple Thread Rendezvous at a Barrier [5%]
Modify the program part1/q3.c to use a mutex and zero or more condition variables so that
every thread prints “a” before any thread prints “b”. This type of synchronization is called a
barrier and we say that threads all rendezvous at the barrier before any are allowed to continue
past it. Your solution must work for any value of NUM_THREADS. For example, for 3 threads
your program must always output the following.
a
a
a
b
b
b
------
Question 1.4: Thread Ordering with Condition Variables [5%]
Modify the program part1/q4.c to use a mutex and one or more condition variables to order
the threads to produce the same output as your solution to Question 1.1. You solution must use
condition variables to order the threads and it must never deadlock. A correct solution must
consider the issue illustrated by Question 1.3 and also the constraints on the ordering of calls to
signal and wait.
Question 1.5: Producer Consumer [10%]
General Description of the Problem
The producer-consumer problem is a classic. This problem uses a set of threads that add and
remove things from a shared, bounded-size resource pool. Some threads are producers that add
items to the pool and some are consumers that remove items.
Video streaming applications, for example, typically consist of two processes connected by a
shared buffer. The producer fetches video frames from a file or the network, decodes them and
adds them to the buffer. The consumer fetches the decoded frames from the buffer at a
designated rate (e.g., 60 frames per second) and delivers them to the graphics system to be
displayed. The buffer is needed because these two processes do not necessarily run at the same
rate. The producer will sometimes be fast and sometimes slow (depending on network
performance or video-scene complexity). On average it is faster than the consumer, but
sometimes it’s slower.
There are two synchronization issues. First, the resource pool is a shared resource access by
multiple threads and thus the producer and consumer code that accesses it are critical sections.
Synchronization is needed to ensure mutual exclusion for these critical sections.
The second type of synchronization is between producers and consumers. The resource pool has
finite size and so producers must sometimes wait for a consumer to free space in the pool, before
adding new items. Similarly, consumers may sometimes find the pool empty and thus have to
wait for producers to replenish the pool.
What to do
Examine the program part1/pc.c. To keep things simple, the shared resource pool in this
program is just a single integer called items. Set the initial value of items to 0. To add an
item to the pool, increment items by 1. To remove an item, decrement items by 1.
Modify the program this program to use a mutex and condition variables so that the program is
race free and that it satisfies the constraint that 0 <= items <= MAX_ITEMS.
Your code must ensure that items is never less than 0 nor more than MAX_ITEMS. Consumers
may have to wait until there is an item to consume and producers may have to wait until there is
room for a new item. In both cases, implement this waiting using condition variables.
Test your solution with two consumer and two producer threads and the number of processors set
to 4; this is already done for you in pc.c.
Testing
To test your solution, run a large number of iterations of each thread. There are assert
statement(s) in the code that ensure the constraint 0 <= items <= MAX_ITEMS is never
violated; if it is the program will crash.
The program also maintains a histogram of the values that items takes on that prints when the
program terminates. The program prints the histogram when it terminates to give you a window
into what happened during the execution. A correct implementation will have a sort of random
distribution across the values of items, weighted a bit to lower values; and it will be different
each time you run your program. The sum of the counts in the histogram must equal the total
number of changes made to items (i.e., the total number of producer and consumer steps); the
final assert statement checks this constraint.
As with every question in this assignment, run your solution many times to ensure that it
complete correctly each time.
Part 2
Question 2.1: The Cigarette Smokers Problem [30%]
The cigarette smokers problem is a classic synchronization problem, posed by Suhas Patil in
1971. In this problem there are four actors, each represented by a thread, and three resources
required to construct and smoke a cigarette: tobacco, paper, and matches. One of the actors is
the agent and the other three are smokers. The agent has an infinite supply of all of the
resources. Each smoker has an infinite supply of one resource and nothing else; each smoker
possesses a different resource.
The three smoker threads loop attempting to smoke, which requires that they obtain one unit of
both of the resources they do not possess. The agent loops repeatedly, randomly choosing two
ingredients to make available to smokers. Each time the agent does this, one of the three
smokers should be able to achieve its heath-destroying goal. For example, if the agent chose
paper and matches, then the tobacco-possessing smoker can consume these two items, combined
with its own supply of tobacco, to smoke.
This is a simple model of a general resource-management problem that operating systems deal
with in many forms. To ensure that it captures that real problem correctly, the agent has a few
additional constraints placed on it.
The agent is only allowed to communicate by signalling the availability of a resource using a
condition variable. It is not permitted to disclose resource availability in any other way; i.e.,
smokers can not ask the agent what is available. In addition, the agent is not permitted to know
anything about the resource needs of smokers; i.e., the agent can not wakeup a smoker directly.
Finally, each time the agent makes two resources available, it must wait on a condition variable
for a smoker to smoke before it can make any additional resources available.
The problem is tricky because when the agent makes two items available, every smoker thread
can use one of them, but only one can use both. If you aren’t careful, you might create a solution
that results in deadlock. For example, if the agent makes paper and matches available, both the
paper and the matches smokers want one of these, but neither will be able to smoke because
neither has tobacco. But, if either of them does wake up and consume a resource, that will
prevent the tobacco thread from begin able to smoke and thus also prevent the agent from
waking up to deliver additional resources. If this happens, the system is deadlocked; no thread
will be able to make further progress.
Requirements
Implement a deadlock-free solution to the cigarette smokers problem in a C program called
smoke.c; start from the provided file, part2/smoke.c. Use uthreads initialized to use a
single processor (or more if you like).
Create four threads: one for the agent and one for each type of smoker. The agent thread should
loop through a set of iterations. In each iteration it chooses two resources randomly, signals their
condition variables, and then waits on a condition variable that smokers signal when they are
able to smoke. When smoker threads are unable to run they must be waiting on a condition
variable. When a smoker wakes up to find both of the resources it needs, it signals the agent and
goes back to waiting for the next chance to smoke.
The agent must use exactly four condition variables: one for each resource and one to wait for
smokers. The agent must indicate that a resource is available by calling signal on that resource’s
condition variables exactly once. There is no other way for any other part of the system to know
which resources are currently available. The code for the agent is provided for you. You do not
need to change this code, but you can. Just be sure you follow the rules we have just outlined.
You may find it useful to create other threads and add additional condition variables. It is
perfectly fine to do so as long as you follow the constraints imposed on the agent thread. For
example, notice that we have not said how the smokers wait other than to say that they wait on
some condition variable.
To generate a random number in C you can use the procedure random() that is declared in
<stdlib.h. It gives you a random integer. You if want a random number between 0 and N,
one way to do that is to use the modulus operator; i.e., random() % N. This procedure returns
random numbers starting with a seed value. Every time you run your program it will by default
use the same seed and so calls to random() will produce the same sequence of random
numbers. That is fine.
Testing
The most common problem with attempts to solve this problem is deadlock. The simplest way
to diagnose this problem initially is to use printf statements in the agent and smokers that tell
you what each is doing. A printf just before and just after every statement that could block
(e.g., every wait) is probably a good idea. If the printing stops before the program does, you
have a deadlock and the last few strings printed should tell you where. Start with one iteration
of the agent. Get that to work, then try more than one.
Be sure that the strings you print with printf end with a new line character (i.e., “\n”),
because printf does not actually print until it sees this character or the program terminates. If
you print without the newline and then your program deadlocks, you will not see the string
printed and you will be confused about where the program deadlocked.
Once you think you’ve got this working, you’ll want to remove the printf’s so that you can
drive the problem through a large number of iterations without being bombarded with output.
One way to do this is to use the C Preprocessor to surround each of your printf statements
with a #ifdef directive like this:
#ifdef VERBOSE
printf (“Tobacco smoker is smoking.\n”);
#endif
A better way — though the more you do with macros the trickier it can get — is to define a
macro called VERBOSE_PRINT that is a printf if VERBOSE is defined and the empty
statement otherwise. To do this, include the following macro definition at the beginning of your
program.
#ifdef VERBOSE
#define VERBOSE_PRINT(S, ...) printf (S, ##__VA_ARGS__);
#else
#define VERBOSE_PRINT(S, ...) ;
#endif
And then use the macro instead of printf for debugging statements, like this:
VERBOSE_PRINT (“Tobacco smoker is smoking.\n”);
In either case you can now selectively define the VERBOSE macro when you compile your
program to turn diagnostic printf’s on or off.
To turn them on (the program now prints all of the debugging statements)):
gcc -D VERBOSE -std=gnu11 -o smoke smoke.c uthread.c uthread_mutex_cond.c -pthread
To turn them off (the program now prints no debugging statements):
gcc -std=gnu11 -o smoke smoke.c uthread.c uthread_mutex_cond.c -pthread
Testing
Test your program by driving the agent through a large set of iterations. Instrument the agent to
count the expected times each smokers should smoke and instrument each smoker to count the
number of times that each does smoke. Compare these to ensure they match and print them
when the program terminates.
Question 2.2: The Lilliputian Endianness Well Problem [30%]
As has been documented, a great schism befell the land of Lilliput some generations ago when,
following an egg-eating tragedy involving the emperor’s son, it was decreed that all eggs be
eaten small-end first from that time forth — the big end being a far too dangerous place to
commence egg ingestion. But, sadly, as often happens with imperial decrees, some in the
kingdom remained steadfastly committed to the traditional big-end-first manner of eating and as
time passed the endianness schism grew deeper and the risk of conflict more profound.
In the present day, a peace-keeping arrangement has been established that separates Lilliput into
two endianness halves so that the people never risk meeting someone with a different point of
view on the whole egg thing. There is but one problem. Lilliput has only a single well from
which all souls must get their drinking water. A protocol has therefore been established to
control access to the well. It being important to understand the protocol to complete this
question, I will tell it to you now.
There exists a gatekeeper who controls access to the area surrounding the well. The gatekeeper
grants access in such a way as to ensure two things. First, it must never be the case that people
of opposing endianness are at the well at the same time, to avoid the untold calamity that would
surely unfold should either side be confronted with views they don’t share (there is a separate
protocol for social media, but that is of no importance to the gatekeeper). Second, no more than
three people can be in the well area at the same time (a fire-code thing).
The gatekeeper, being noble and fair, ensures that people waiting for water eventually get to use
the well and that their waiting times are roughly uniform, provided that the people at the well
leave on a regular basis. The gatekeeper is also bit of a technocrat and so wants the well to
operate efficiently (i.e., at high capacity), even if this means there’s a bit of queue jumping (i.e.,
sometimes people can enter the well ahead of someone who has been waiting longer than them).
Finally the gatekeeper is wise and has thus devised an exquisite technique to balance the tradeoff
between fairness and efficiency.
Now, it has fallen to you to simulate the Lilliputian well using threads, mutexes, and condition
variables. Every person is a thread. The well is a critical section protected by a mutex. The
gatekeeper is a procedure that each thread calls when attempting to enter the well and when
leaving. When a thread is unable to enter the well it waits on a condition variable. When a
thread leaves the well it delivers whatever signals are necessary to wakeup the thread or threads
that are allowed to enter when it leaves.
Requirements
Implement a solution to the Endianness Well problem in a C program called well.c; start from
the provided file, part2/well.c. Use uthreads initialized to use a single processor (or more
if you like). Use mutexes for mutual exclusion and condition variable for thread signalling.
Create N threads and assign each a randomly chosen endianness. Threads should loop attempting
to enter the well a large, fixed number of times. When a thread is in the well, it should call
uthread_yield() a total of N times and then exit the well. It should then call
uthread_yield() at least another N times before attempting to enter the well again. The
program terminates when every thread has entered the well the specified number of times.
Experiment with different values of N, starting with small numbers while debugging and ending
with a number that is at least twenty.
Testing
Test your program with N=20 and each thread performing a least 100 iterations to ensure that the
two well-occupancy constraints are never violated using an assert statement. Count the
number of times that each of the following occupancy conditions occur: one big endian, two big,
three big, one little, two little, and three little. Print these numbers when the program terminates.
Implement a counter that is incremented each time a thread enters the well. For each thread
entering the well, record the value of the counter when it starts waiting and the value when it
enters the well. Subtract these two numbers to determine the thread’s waiting time and record
this information in a histogram like this.
if (waitingTime < WAITING_HISTOGRAM_SIZE)
waitingHistogram [waitingTime] ++;
else
waitingHistogramOverflow ++;
Declare a large histogram array of size WAITING_HISTOGRAM_SIZE. Print the histogram
and the overflow bucket when the program terminates. If you access the histogram or other test
data from multiple threads be sure to guarantee mutual exclusion for these critical sections.
You will notice that no matter how hard you try to make this fair, if you have enough people
trying to get into the well at the same time, you can’t make it fair for everyone. You will see that
people occasionally end up waiting much longer than it seems they should. The problem is that
there is an inherent unfairness with wait. This is the same problem we’ve seen in class: a race
between the awoken thread re-entering the critical section when returning from wait and a new
thread calling lock to enter.
To see what is happening in this case, let’s assume there is a long queue of people waiting on a
condition variable. When signal is called indicating that a well position is available, the
thread that has been waiting the longest is awoken. This is fair as ensured by the fact that the
condition-variable waiter queue is a fifo. However, if some other thread that has not been
waiting at all is, at this very moment, trying to get into the critical section and it beats the
awoken thread into the critical section, then it may get that thread’s position in the well,
bypassing the awoken thread and every thread on the waiter queue. When this happens the
awoken thread must wait again; and it does this by moving all the way to the back of the waiter
queue. In our case the budger is the thread that just left the well and that just turned around and
tried to get back in again, sometimes succeeding to budge to the front of the line, grabbing the
space it just vacated and forcing that poor sucker it just woke up to go to the back of the line.
The purpose of the uthread_yield() loop after exiting the well is to minimize how often
this situation occurs. You won’t see it happen often. But, it will happen often enough that a few
threads occasionally end up waiting a very long time to get into the well. You might experiment
with calling uthread_yield() more times after leaving the well (or less) and see how this
affects fairness. Resolving this unfairness is tricky and not necessary for this assignment.
Question 2.3: Producer Consumer with Semaphores [10%]
Re-implement Question 1.5 using semaphores by modifying part1/pc.c to use semaphores
for all synchronization. Place your solution in a file named pc_sem.c. Your solution must not
use anything from the uthread_mutex / uthread_cond API.
Bonus 2.4: Endianness Well with Semaphores [20%]
Re-implement Question 2.2 using semaphores as the only synchronization primitive and place
your solution in the file well_sem.c; start from the provided file (or your solution to Question
4).
Notice what happens to the unfairness problem we saw with wait in Question 4 that caused
threads to occasionally lose their place in line and end up waiting a very long time to get into the
well. Explain the difference you see and say why semaphores are different, placing your answer
in the file BONUS.txt.
What to Hand In
Use the handin program.
You will handin parts 1 and two separately.
The assignment directory for Part 1 is ~/cs213/a10part1. It should contain the following
plain-text files.
1. PARTNER.txt containing your partner’s CS login id and nothing else (i.e., the 4- or 5-
digit id in the form a0z1). Your partner should not submit anything.
2. The files: q1.c, q2.c, q3.c, and pc.c. These should stored directly in the a10part1
directory and not in a subdirectory.
The assignment directory for Part 2 is ~/cs213/a10part2. It should contain the following
plain-text files.
1. PARTNER.txt containing your partner’s CS login id and nothing else (i.e., the 4- or 5-
digit id in the form a0z1). Your partner should not submit anything.
2. The files smoke.c, well.c, pc_sem.c and, if you did the bonus question,
well_sem.c and BONUS.txt.