Programming Project 5
Threads & Synchronization
CS 441/541 – Fall 2019
Project Available Oct. 16
Component Points Due Date
(at 11:59 pm)
Proper use of Pthreads 10
Proper input/output 10
Problem solution 40
Style & Organization 10
Documentation 10
Write-up 10
Demo 10
Total 100 Nov. 17
Submission Group Canvas
Objectives
In this project, you’ll implement a novel synchronization problem as a way to learn how to construct a
solution to a problem using Pthreads and semaphores.
Packaging & handing in your project
You will turn in a single compressed archive of your completed project directory to Canvas. A template
project is available on BitBucket. You *MUST* use the provided semaphore library as it works more
reliably on various operating systems.
Deliverables
© Code written in a consistent style according to the Style Requirements handout.
© Properly parses the command line arguments.
© Properly displays the state of the code.
© Properly synchronizes access to shared variables in the system.
© Your program must never busy wait for an event to occur. If you need to cause a thread to wait then
it should do so using semaphores. Do not assume that the semaphore wait provides a proper queue
for the waiting threads (if you need such a concept).
© Make sure to seed the random number generator before using it. Seed the random number generator
before starting threads with the following command: srandom(time(NULL))
© You will need to put bounds on the random number generator by using the modulus operator on the
output: i = random()%LIMIT;
© To sleep for less than 1 full second you must use the usleep() command (instead of sleep()) to sleep for
some number of microseconds.
© When printing output to stdout you may notice that the output from multiple threads interleave them-
selves. To fix this problem you might consider creating a binary semaphore to protect calls to the
printf function so only one thread is printing to the console at a time.
© You must print out the parsed command line parameters before starting execution. If an optional
parameter is not supplied, then you must display the default value for that parameter.
© If the user provides an incorrect set of command line arguments to your program you must immediately
display an error message and a message describing the correct use of your program. After displaying
those messages your program will immediately exit.
CS 441/541 Programming Project 5 Page 2 of 6
1 The Finicky Voter Problem
An election polling station services a steady stream of voters throughout the day. Any given polling
station has a fixed number of voting booths available. A new voter law restricts the types of registered
voters that are allowed to vote at the same time. There are three types of registered voters: Republicans,
Independents, and Democrats. Republicans and Democrats should never be allowed to vote at the same
time. Independents can vote with either Republicans or Democrats (with the hope that doing so will turn
them to one side or the other).
You must implement a program that creates the requisite number of Republican, Independent, and
Democrat threads. Then use semaphores to synchronize the voting at the polling station. Each voter
thread should identify itself by political party and thread identifier whenever its state changes.
1.1 Requirements
The following are the base requirements for your program:
• Your program will take up to four arguments in the following order.
1. Number of voting booths at the polling station (positive integer greater than 0). This argument
is optional. The default value is 10.
2. Number of Republicans (positive integer greater than 0).This argument is optional. The
default value is 5.
3. Number of Democrats (positive integer greater than 0).This argument is optional. The default
value is 5.
4. Number of Independents (positive integer greater than 0).This argument is optional. The
default value is 5.
The voting booths and threads of each party must be allocated dynamically according to the values
determined by the command-line arguments.
• After starting all of the threads the threads must wait for the polling station to open up. The main
thread will wait for two whole seconds after creating the threads before opening the polling station.
Once the station opens then voters are allowed to lineup to vote.
• Each voter should print a message, identifying itself with its political party and identifier, as it:
– is waiting for the polling station to open
– enters the polling station and signs-in at the registration desk
– starts waiting on the first available voting booth
– enters a voting booth (identifying which voting booth it entered by number)
– leaves the voting booth and polling station
See the example for the expected formatting of the output.
• Immediately after entering the polling station the voter will need to sign-in at the voter registration
desk. Simulate the time to sign-in by sleeping the thread for a random amount of time between 0 and
50,000 microseconds.
• While in a voting booth, simulate the time to thoughtfully vote by sleeping the thread for a random
amount of time between 0 and 100,000 microseconds.
• Republican and Democrat voters cannot be waiting on a voting booth at the same time.
• Independent voters can wait on a voting booth with either Republicans or Democrats.
• If a voter is waiting it cannot be forced to wait for an indefinite amount of time before being allowed
to vote.
• If a series of Republicans start waiting to vote one after another, then the first Republican to start
waiting to vote should be the first to enter a voting booth followed by the second and so on. The same
rule applies to a series of Democrats or Independents waiting to vote.
• Whenever a thread changes state then the thread must display their political party, thread ID (integer
number between 0 and the number of that type of thread), the current state of the voting booths, and
new state. When they are voting (and only when they are voting) then the voting booth number that
CS 441/541 Programming Project 5 Page 3 of 6
they are occupying must also be printed. See the example for the expected formatting of the output.
Your output must match the formatting from the examples as exactly as possible (except where
determined by the interleaving of threads).
• The number of voting booths, and the number of voter threads in each party must be dynamically
allocated based upon the command line input, not have a fixed upper bound.
• The number of voting booths must be dynamically allocated based upon the command line input,
not have a fixed upper bound.
1.2 Special Section - Writing about your solution
Once you have completed your solution, in a special section within your documentation you must
answer the following questions, separately:
1. Describe your solution to the problem (in words, not in code).
2. Describe how your solution meets the goals of this part of the project, namely:
• How does your solution avoid deadlock?
• How does your solution prevent Republican and Democrat voters from waiting on a voting booth
at the same time?
• How is your solution “fair”? How are you defining “fairness” for this problem?
Some questions to consider when thinking about how to answer this question:
– Is it fair for Independent voters to cut in line ahead of other party-affiliated voters waiting
for a voting booth?
– What happens if a long line of Democrats start waiting to vote and a Republican shows up
late? Should the late Republican be able to vote before all of the Democrats have finished?
• How does your solution prevent starvation? How are you defining “starvation” for this problem?
• How do you balance fairness with resource utilization and throughput? How would you measure
this?
To receive the full points allotted for the written component you must provide a convincing argument as
to why your solution is correct both in design, and in the implementation of that design.
CS 441/541 Programming Project 5 Page 4 of 6
shell$ ./voter 5 3 3 3
Number of Voting Booths : 5
Number of Republican : 3
Number of Democrat : 3
Number of Independent : 3
-----------------------+-----------------------+--------------------------------
Republican 0 |-> [.][.][.][.][.] <-| Waiting for polling station to open...
Democrat 0 |-> [.][.][.][.][.] <-| Waiting for polling station to open...
Republican 1 |-> [.][.][.][.][.] <-| Waiting for polling station to open...
Republican 2 |-> [.][.][.][.][.] <-| Waiting for polling station to open...
Democrat 1 |-> [.][.][.][.][.] <-| Waiting for polling station to open...
Independent 0 |-> [.][.][.][.][.] <-| Waiting for polling station to open...
Independent 1 |-> [.][.][.][.][.] <-| Waiting for polling station to open...
Democrat 2 |-> [.][.][.][.][.] <-| Waiting for polling station to open...
Independent 2 |-> [.][.][.][.][.] <-| Waiting for polling station to open...
-----------------------+-----------------------+--------------------------------
Democrat 0 |-> [.][.][.][.][.] <-| Entering the polling station
Republican 0 |-> [.][.][.][.][.] <-| Entering the polling station
Republican 1 |-> [.][.][.][.][.] <-| Entering the polling station
Democrat 2 |-> [.][.][.][.][.] <-| Entering the polling station
Independent 0 |-> [.][.][.][.][.] <-| Entering the polling station
Republican 2 |-> [.][.][.][.][.] <-| Entering the polling station
Independent 1 |-> [.][.][.][.][.] <-| Entering the polling station
Democrat 1 |-> [.][.][.][.][.] <-| Entering the polling station
Independent 2 |-> [.][.][.][.][.] <-| Entering the polling station
Republican 1 |-> [.][.][.][.][.] <-| Waiting on a voting booth
Republican 1 in 0 |-> [R][.][.][.][.] <-| Voting!
Republican 1 |-> [.][.][.][.][.] <-| Leaving the polling station
Democrat 2 |-> [.][.][.][.][.] <-| Waiting on a voting booth
Democrat 2 in 0 |-> [D][.][.][.][.] <-| Voting!
Independent 2 |-> [D][.][.][.][.] <-| Waiting on a voting booth
Independent 2 in 1 |-> [D][I][.][.][.] <-| Voting!
Independent 1 |-> [D][I][.][.][.] <-| Waiting on a voting booth
Independent 1 in 2 |-> [D][I][I][.][.] <-| Voting!
Independent 0 |-> [D][I][I][.][.] <-| Waiting on a voting booth
Independent 0 in 3 |-> [D][I][I][I][.] <-| Voting!
Independent 2 |-> [D][.][I][I][.] <-| Leaving the polling station
Independent 1 |-> [D][.][.][I][.] <-| Leaving the polling station
Democrat 2 |-> [.][.][.][I][.] <-| Leaving the polling station
Republican 0 |-> [.][.][.][I][.] <-| Waiting on a voting booth
Republican 0 in 0 |-> [R][.][.][I][.] <-| Voting!
Republican 2 |-> [R][.][.][I][.] <-| Waiting on a voting booth
Republican 2 in 1 |-> [R][R][.][I][.] <-| Voting!
Republican 2 |-> [R][.][.][I][.] <-| Leaving the polling station
Republican 0 |-> [.][.][.][I][.] <-| Leaving the polling station
Democrat 1 |-> [.][.][.][I][.] <-| Waiting on a voting booth
Democrat 1 in 0 |-> [D][.][.][I][.] <-| Voting!
Democrat 0 |-> [D][.][.][I][.] <-| Waiting on a voting booth
Democrat 0 in 1 |-> [D][D][.][I][.] <-| Voting!
Democrat 1 |-> [.][D][.][I][.] <-| Leaving the polling station
Independent 0 |-> [.][D][.][.][.] <-| Leaving the polling station
Democrat 0 |-> [.][.][.][.][.] <-| Leaving the polling station
-----------------------+-----------------------+--------------------------------
CS 441/541 Programming Project 5 Page 5 of 6
shell$ ./voter 3 2 2 1
Number of Voting Booths : 3
Number of Republican : 2
Number of Democrat : 2
Number of Independent : 1
-----------------------+-----------------+--------------------------------
Democrat 0 |-> [.][.][.] <-| Waiting for polling station to open...
Republican 0 |-> [.][.][.] <-| Waiting for polling station to open...
Republican 1 |-> [.][.][.] <-| Waiting for polling station to open...
Independent 0 |-> [.][.][.] <-| Waiting for polling station to open...
Democrat 1 |-> [.][.][.] <-| Waiting for polling station to open...
-----------------------+-----------------+--------------------------------
Independent 0 |-> [.][.][.] <-| Entering the polling station
Democrat 1 |-> [.][.][.] <-| Entering the polling station
Democrat 0 |-> [.][.][.] <-| Entering the polling station
Republican 0 |-> [.][.][.] <-| Entering the polling station
Republican 1 |-> [.][.][.] <-| Entering the polling station
Democrat 0 |-> [.][.][.] <-| Waiting on a voting booth
Democrat 0 in 0 |-> [D][.][.] <-| Voting!
Democrat 1 |-> [D][.][.] <-| Waiting on a voting booth
Democrat 1 in 1 |-> [D][D][.] <-| Voting!
Independent 0 |-> [D][D][.] <-| Waiting on a voting booth
Independent 0 in 2 |-> [D][D][I] <-| Voting!
Democrat 0 |-> [.][D][I] <-| Leaving the polling station
Democrat 1 |-> [.][.][I] <-| Leaving the polling station
Republican 0 |-> [.][.][I] <-| Waiting on a voting booth
Republican 0 in 0 |-> [R][.][I] <-| Voting!
Republican 1 |-> [R][.][I] <-| Waiting on a voting booth
Republican 1 in 1 |-> [R][R][I] <-| Voting!
Republican 0 |-> [.][R][I] <-| Leaving the polling station
Independent 0 |-> [.][R][.] <-| Leaving the polling station
Republican 1 |-> [.][.][.] <-| Leaving the polling station
-----------------------+-----------------+--------------------------------
shell$ ./voter 2 4 4 2
Number of Voting Booths : 2
Number of Republican : 4
Number of Democrat : 4
Number of Independent : 2
-----------------------+--------------+--------------------------------
Republican 0 |-> [.][.] <-| Waiting for polling station to open...
Republican 2 |-> [.][.] <-| Waiting for polling station to open...
Democrat 0 |-> [.][.] <-| Waiting for polling station to open...
Republican 1 |-> [.][.] <-| Waiting for polling station to open...
Independent 0 |-> [.][.] <-| Waiting for polling station to open...
Democrat 1 |-> [.][.] <-| Waiting for polling station to open...
Democrat 2 |-> [.][.] <-| Waiting for polling station to open...
Republican 3 |-> [.][.] <-| Waiting for polling station to open...
Independent 1 |-> [.][.] <-| Waiting for polling station to open...
Democrat 3 |-> [.][.] <-| Waiting for polling station to open...
-----------------------+--------------+--------------------------------
Republican 0 |-> [.][.] <-| Entering the polling station
Republican 1 |-> [.][.] <-| Entering the polling station
Democrat 0 |-> [.][.] <-| Entering the polling station
Democrat 1 |-> [.][.] <-| Entering the polling station
Republican 2 |-> [.][.] <-| Entering the polling station
Democrat 2 |-> [.][.] <-| Entering the polling station
Republican 3 |-> [.][.] <-| Entering the polling station
CS 441/541 Programming Project 5 Page 6 of 6
Republican 1 |-> [.][.] <-| Waiting on a voting booth
Independent 1 |-> [.][.] <-| Entering the polling station
Republican 1 in 0 |-> [R][.] <-| Voting!
Democrat 3 |-> [R][.] <-| Entering the polling station
Independent 0 |-> [R][.] <-| Entering the polling station
Independent 0 |-> [R][.] <-| Waiting on a voting booth
Independent 0 in 1 |-> [R][I] <-| Voting!
Independent 1 |-> [R][I] <-| Waiting on a voting booth
Republican 1 |-> [.][I] <-| Leaving the polling station
Independent 1 in 0 |-> [I][I] <-| Voting!
Democrat 0 |-> [I][I] <-| Waiting on a voting booth
Independent 0 |-> [I][.] <-| Leaving the polling station
Democrat 0 in 1 |-> [I][D] <-| Voting!
Independent 1 |-> [.][D] <-| Leaving the polling station
Democrat 0 |-> [.][.] <-| Leaving the polling station
Republican 2 |-> [.][.] <-| Waiting on a voting booth
Republican 2 in 0 |-> [R][.] <-| Voting!
Republican 2 |-> [.][.] <-| Leaving the polling station
Democrat 2 |-> [.][.] <-| Waiting on a voting booth
Democrat 2 in 0 |-> [D][.] <-| Voting!
Democrat 2 |-> [.][.] <-| Leaving the polling station
Republican 0 |-> [.][.] <-| Waiting on a voting booth
Republican 0 in 0 |-> [R][.] <-| Voting!
Republican 3 |-> [R][.] <-| Waiting on a voting booth
Republican 3 in 1 |-> [R][R] <-| Voting!
Republican 0 |-> [.][R] <-| Leaving the polling station
Republican 3 |-> [.][.] <-| Leaving the polling station
Democrat 3 |-> [.][.] <-| Waiting on a voting booth
Democrat 3 in 0 |-> [D][.] <-| Voting!
Democrat 1 |-> [D][.] <-| Waiting on a voting booth
Democrat 1 in 1 |-> [D][D] <-| Voting!
Democrat 3 |-> [.][D] <-| Leaving the polling station
Democrat 1 |-> [.][.] <-| Leaving the polling station
-----------------------+--------------+--------------------------------
Additional Part for Graduate Students – Optional for Undergraduates
In the bonus folder, implement a solution to this problem adding a third party, Libertarians, who do not
vote with Democrats or Republicans, and vice-versa. Independents can continue to vote with members of
any party. In the special writing section, describe how you extended your previous solution to accommodate
this additional type of voter.
Testing
Testing is an important part of the software development life cycle. You must describe in your documen-
tation how you tested your project to ensure it met the requirements of the problem.
Note, that for synchronization problem just running the program one, twice, . . . , 100, . . . , 10,000 times
will not suffice to highlight all of the possible ways that the threads can be interwoven during execution.
Testing and debugging tend to be one of the greatest challenges to writing concurrent code because of this
reality.
Your documentation must discuss the testing methodology that you used used to validate that your
solution was valid in design and in the implementation of that design.