Due 11:59pm, April 19, 2013
All files: p4.zip
- Files for command line submission (see "Submission" for usage)
In class, we developed an interpreter for a simple, multithreaded
programming language. That language includes thread creation,
(non-reentrant) locks, and wait/notify. In this project, you will
extend that interpreter to include a number of other useful
multithreading primitives. Note that while you will add these
features by modifying the interpreter, in practice many of these
features can be added by instead encoding them in terms of other
available features; e.g., reader/writer locks can be encoded using
When you finish this project, all of the different pieces you develop
should work together. Thus, if for a later part of the project you
need to modify some of the data structures for the project (e.g., what
a configuration is), you might need to then revisit an earlier part of
the project so that it works with the new data structure. However, if
you are careful about your program design, you should be able to
minimize any repeated work.
Important: To grade your project, we will create various
configurations and run your step function on them under certain
schedules. To make sure we can do this programmatically there are
some requirements and restrictions concerning how you carry out your
implementation; see the end of the project description, below.
Part 1. A new scheduler
In class, we developed two schedulers: one that runs each thread to
completion, and another that runs each thread one step and then
switches to the next available thread.
For this part of the project, write a function make_rr_sched_n n :
int -> scheduler that is similar to make_rr_sched
(supplied in the project code), but creates a scheduler that runs each
thread for n ticks (rather than 1 tick) before switching to
the next available thread. It should be the case
that make_rr_sched_n 1 returns a scheduler that behaves
identically to make_rr_sched ().
For purposes of this project, your scheduler should increment its tick
count for a thread id each time it returns that thread id, even if
that thread id is blocked from running. Again, this is sub-optimal
for scheduling in practice, but sufficient for purposes of this
Part 2. Better locking
In this part of the project, you will add three extensions to locks:
- Modify p4.ml so that the step function throws an exception if some
thread executes the command Release "lock", Wait
"lock", or NotifyAll "lock" but it does not
hold "lock". Hint: You will need to keep track of the owning thread
id for each lock held.
- Implement the TryAcquire(lock,lab) command, which tries
to acquire lock and, if successful, jumps to lab;
if not successful (i.e., the lock is already held by some other
thread), it falls through to the next statement, rather than blocking. Your
TryAcquire implementation should be made compatible with
reentrant locks, discussed next.
- In the implementation in p4.ml, locks are not reentrant: if the
same thread tries to acquire a lock it already holds, that thread
will deadlock. For this part of the project, you should change
the behavior of Acquire and Release so that locks
are reentrant, meaning (a) each lock may still only be held by at
most one thread; (b) a lock may be reacquired by the same thread
more than once; (c) a lock is released only when the thread that
holds it releases the lock the same number of times it acquired it.
For example, here is a sequence of Acquire
and Release commands along with a description of when the lock is
- Thread 1 - Acquire x - lock acquired by thread 1
- Thread 1 - Acquire x - lock still held by thread 1
- Thread 1 - Release x - lock still held by thread 1
- Thread 1 - Acquire x - lock still held by thread 1
- Thread 1 - Release x - lock still held by thread 1
- Thread 1 - Release x - lock released by thread 1
- Add support for reader/writer locks, as
follows. RdAcquire x acquires a lock x for
reading. Any number of threads can hold a read lock at
once. WrAcquire x acquires a lock x for writing.
Only one thread can hold a write lock at a time, and no other
thread can hold a read lock when a write lock is held.
Thus, RdAcquire x should block if a write lock on
x is already held, and WrAcquire x should block if
either a read or a write lock on x is already held.
releases either a reader or writer lock, and your interpreter should
raise an exception if a thread attempts to release a reader/writer
lock it does not hold. For this part of the
project, you can assume that reader/writer locks are disjoint from
regular locks, i.e., there will never be a case when
both Acquire x and Rd/WrAcquire x is called. Your
reader/writer locks should not be reentrant---the interpreter
should raise an exception if a thread tries to reacquire (as either read
or write) a reader/writer lock it already holds.
Part 3. More synchronization primitives
There are several other useful synchronization primitives aside from
locks. For this part of the project, you must implement the following:
- Barriers. Threads can use a barrier to ensure that all
threads conceptually reach some common point. Specifically, each
thread should block at a use of the command Barrier
until all threads are at a Barrier command; at that point,
the program counters of all threads should advance by one. For
example, suppose threads 1, 2, and 3 are running, and consider the
following sequence of commands:
You should only include threads that have not ended when deciding if
all threads have arrived at a barrier. Thus, if a thread ends when other
threads are waiting at a barrier, it might allow those threads to
proceed (assuming there are no other live threads not waiting at a barrier).
- Thread 1 - Barrier - Thread 1 blocks
- Thread 2 - Assign("x", ENum 3) - Thread 1 still blocked
- Thread 3 - Barrier - Threads 1 and 3 blocked
- Thread 2 - Barrier - Threads 1-3 unblocked, advance to next command
- Thread 2 - Barrier - Thread 2 blocked
- Thread 1 - Assign("x", ENum 4) - Thread 2 still blocked
- Thread 3 - Assign("y", Enum 5) - Thread 2 still blocked
- Thread 1 - Barrier - Threads 1 and 2 blocked
- Thread 3 - Barrier - Threads 1-3 unblocked, advance to next command
- Count down latches. A count down latch lets several
threads wait until some condition is achieved. A latch is created
in some thread with CreateLatch(s,e), where s is
the name of the latch and e evaluates to an integer that is
the initial count of the latch. (You may assume a latch is only
ever created once in a program, and is never created with a negative
count.) There are two possible operations
on latches: CountDown s decrements the count of the latch
by one if the count is positive (i.e., it will not decrement below zero),
and WaitLatch s causes the current thread to block
until the latch's count is zero. Note that, unlike wait and
notifyAll, there is no association between latches and locks---there
is no need to hold any particular lock to wait at or decrement a
latch. For example, here is a sequence of commands illustrating
count down latches:
The interpreter should raise an exception if CountDown or WaitLatch are used on a
latch that hasn't been created.
You need not handle the case when a latch with the same name is
created more than once (i.e., we will not test code such as
- Thread 1 - CreateLatch("latch", ENum 3)
- Thread 1 - WaitLatch("latch") - Thread 1 blocked, count is 3
- Thread 2 - CountDown("latch") - Thread 1 still blocked, count is 2
- Thread 3 - CountDown("latch") - Thread 1 still blocked, count is 1
- Thread 2 - CountDown("latch") - Thread 1 unblocked
- Thread 3 - CountDown("latch") - equivalent to Skip
- Semaphore. A sempahore conceptually represents a set of
permits to proceed. Initially, each semaphore contains zero
permits. RelSem s increments semaphore s's permit
count by one. AcqSem s decreases semaphore s's
permit count by one, blocking until a permit is available, i.e.,
until the semaphore's associated count is greater than zero. For
example, here is a sequence of commands illustrating semaphores:
Note that semaphores are not explicitly created---implicitly, all possible
semaphores exist with zero permits when the program starts.
- Thread 1 - RelSem("sem") - sem count is 1
- Thread 2 - RelSem("sem") - sem count is 2
- Thread 1 - AcqSem("sem") - sem count is 1
- Thread 1 - Assign("x", ENum 3) - sem count is 1
- Thread 1 - AcqSem("sem") - sem count is 0
- Thread 1 - AcqSem("sem") - Thread 1 blocks
- Thread 2 - Assign("y", ENum 4) - Thread 1 still blocked
- Thread 2 - RelSem("sem") - sem count is 1, thread 1 unblocks, when
it proceeds sem count is 0
Part 4. Deadlock detection (Optional!)
This part of the project is optional, for extra credit on this project.
Deadlock occurs when one or more threads are blocked and will
never be able to take another step. For example, consider the
following sequence of commands in two threads:
At the end of this sequence, threads 1 and 2 are deadlocked: thread 1
has lock A, and is waiting to acquire lock B, which is held by thread
2, which is waiting to acquire lock A. Neither thread can take a step
because each is blocked, and neither can become unblocked because they
are each waiting for the other thread to release the lock.
- Thread 1 - Acquire "A"
- Thread 2 - Acquire "B"
- Thread 1 - Acquire "B"
- Thread 2 - Acquire "A"
We can characterize this kind of deadlock more precisely as follows.
Imagine a graph whose nodes consist of the program's thread ids and
locks held under a partcular configuration c. For our
example above, the graph nodes are 1, 2, A, and B. Draw an edge from
a lock to a tid if that tid holds that lock. For our example, this
yields edges A->1 and B->2. Draw an edge from a tid to a lock if that
thread is trying to acquire that lock. For our example, this yields
edges 1->B and 2->A. Then c has a deadlock if the graph so
constructed has a cycle in it. For our example, the cycle is
For this part of the project, you must implement a function
deadlocked : program -> config -> bool that returns true if a
configuration is deadlocked according to the above definition, and
false otherwise. Note that you need only look for deadlock for mutual
exclusion locks with Acquire/Release; you don't need to check for
deadlock with Reader/Writer locks, wait/notify, etc.
Requirements on your
Here we describe some things you must and must not do in your
implementation so that we can properly test it.
- You may only change the type config. (You are
free to add additional types if you like.) Thus, you
must leave the types expr, mem, cmd,
pc, program, tid, lock,
waiter, and scheduler as is. Because you can't
change the type scheduler,
schedulers might be sub-optimal in that they might try running
threads that can't make progress because they're waiting for a
reader/writer lock or some other feature added to the project. That's
ok. If your step function is asked to step a thread
that can't make progress, it should return the same configuration it
was given as input.
- You must implement a function to_initial_config m pcs
that takes a memory and an array of program counter options, and
creates an appropriate initial configuration with that memory, program
counter, and no locks held, no threads waiting, no barriers activated,
etc. We will call this function to create the initial configurations
under which we test your step function.
- You must implement functions mem_of c and pcs_of
c, which return the memory and program counter option array from
a configuration. We will call these functions to verify that your
step function behaved correctly when asked to take a step.
You may either submit
over the web or under command line interface.
Submitting over the web
You only need to submit your p4.ml.
Submit your archive directly to the
by clicking on the submit link in the column "web submission".
Next, use the submit dialog to submit your p4.ml file directly.
Select your file using the "Browse" button,
then press the "Submit project!" button.
Submitting in command line interface
Make a new directory and copy your p4.ml that
directory. Download .submit and submit.jar in
Project Files to the same directory. Then run the following command
under that directory:
java -jar submit.jar
The first time you submit this way you will be asked to enter your
directory ID and password. All files in the directory (and its subdirectories) will then be put in a jar file and submitted to the submit server. If your submission is successful you will see the message:
Successful submission # received for project 5
The Campus Senate has adopted a policy asking students to include the
following statement on each assignment in every course: "I pledge on
my honor that I have not given or received any unauthorized assistance
on this assignment." Consequently your program is requested to
contain this pledge in a comment near the top.
Please carefully read the academic honesty section of the
course syllabus. Any evidence of impermissible cooperation on
projects, use of disallowed materials or resources, or unauthorized
use of computer accounts, will be submitted to the Student
Honor Council, which could result in an XF for the course, or
suspension or expulsion from the University. Be sure you understand
what you are and what you are not permitted to do in regards to
academic integrity when it comes to project assignments. These
policies apply to all students, and the Student Honor Council does not
consider lack of knowledge of the policies to be a defense for
violating them. Full information is found in the course
syllabus---please review it at this time.