Homework 1
CMSC 433
Programming Language Technologies and Paradigms
Fall 2003
Due Wednesday November 26, 2003 at 6pm
Submission instructions are in Section 3.
The following are exercises to tighten your knowledge of concurrent
programming in Java. Write the answer to each problem in a separate text
file; e.g. for problem 1 you will write 1.txt, etc. Any java
code you write should also be included in the text file for the problem you
write it for. If you don't want to use ``ASCII graphics'' for problems 2
and 3, you can include separate .jpg files for your wait-graphs.
Use the name of the problem as the title, e.g. 2.jpg, or
3.1.jpg, 3.2.jpg, etc.
1 Background
Threads can be in one of four thread states: created (after
creation, but before calling start), runnable (either
running, or eligible to be run), blocked (waiting for some event
before execution can resume), and terminated (the thread is
finished). Threads can be blocked for many reasons, including waiting to
acquire a lock, waiting to be awakened with notify, waiting on I/O,
and sleeping for a fixed time.
All objects in Java can behave as locks. Each lock has three conceptual
fields: the current thread owner of the lock (if any), the
count of the times the owner has re-acquired the lock (0 if there
is no owner), and the wait-set, which is a list of threads
waiting on the lock, each paired with a count indicating the number
of times a thread had reacquired a lock before it started waiting. The
values of these three fields are called the lock state of a
particular lock.
2 Problems
- Problem 1
- Consider the classes BoundedBuffer and
Prob1. The latter class constructs two threads that insert
strings into a shared bounded buffer. Run the code to see what the output
looks like. Only one output sequence is possible (why?).
Assume that (1) the threads are run on a single processor, (2) t1
is scheduled first, and (3) the scheduler runs each thread until it blocks
before switching to the other thread. For each of the labelled program
points t1-1, t2-1, t1-2, etc. in
Prob1, describe (1) the thread state of each of the threads
t1 and t2, and (2) the lock state of the
BoundedBuffer objects buf1 and buf2.
- Problem 2
- Consider the interface Number which defines
integer-like numbers and a way to add them, and the classes
MyNatural and MyInteger, which implement
Number. The class Prob2 creates two threads that add
some shared Number objects. Feel free to run the program to see
its output.
This program can exhibit a deadlock. (1) Draw a wait-graph of the program
showing this deadlock. (2) Indicate which statements in the given classes
caused each thread to be blocked in this deadlocked state.
Finally, fix the program by modifying either MyNatural,
MyInteger, or both, to remove the deadlock. Do not introduce any
race conditions! You may not use a global lock; each Number must
have its own lock. Your solution can slightly modify the semantics of the
given program by only holding one lock at a time. For extra credit: you
can present a solution that holds two locks (as in the original program),
but is deadlock-free by enforcing a fixed ordering. This case should
enforce that two threads calling n.add(m) at the same time should
end up with n being n + 2*m.
For your submission, include in the 2.txt file the entire changed
Java file(s).
- Problem 3
- The class BoundedBuffer2 is the same as the
BoundedBuffer class, except that (1) it replaces occurrences of
notifyAll with notify; and (2) it replaces put
with putArray, which inserts the contents of an array into the
buffer, rather than a single item.
The class Prob3 has four variables, set by the command-line
flags: p is the number of producer threads, which insert a group of
items of size b into a single shared buffer; c is the number of
consumer threads, which each remove a single item of the shared buffer;
and s is the size of the buffer.
For simplicity, you may assume a single processor, but any possible legal
schedule. For each of the following values of these parameters, indicate
either (a) all of the tokens added to the buffer will be removed, and all
the threads will exit normally; or (b) that some number of the threads are
stuck in a blocking state before all tokens are removed from the buffer
(e.g., this can happen because of deadlock). For (a), be as precise as
possible---e.g. describe an invariant that the program maintains the
implies constant progress. For (b), write an execution trace that that
shows how threads will fail to exit normally. Refer to the threads as
C1 ... Cc for the consumers, and P1 ... Pp for the producers.
-
p = 1, c = 1, s = 1, b = 1.
- p > 0, c = p, s = 1, b = 1.
- p = 1, c = 4, s = 4, b = 4.
- p = 2, c = 4, s = 5, b = 2.
Hint: think about the kinds of threads that can be on the buffer's
wait-set, and what that implies with regard to deadlock.
- Problem 4
- The Eater class defines a variant of the famous
``dining philosophers problem'' (if you don't know what that is, look it
up on the web for fun). The idea is that in order to eat, each eater must
acquire a chair, then a plate, and then the food. The food is put on the
table by a separate chef thread (the main method of the
Eater class). After an Eater eats, it consumes the food and
gives up the chair and the plate. But: eating is all or nothing: if an
eater grabs the plate, and then the chair, but there is no food on the
table, it must release both and give someone else a chance.
The class that we have provided defines the chair and the plate as
Resources; to grab a resource, you set its gotIt flag to
true. Since resources are shared, setting this flag requires you hold the
Resource's lock. The food is a Consumable, and operates
similarly. Unfortunately, there is a problem with this class. (1)
Indicate the problem. (2) Sketch a way that you could fix the problem
without adding any new static or instance fields to the Eater
class. For extra credit, provide a complete implementation that fixes the
problem, without using busywaiting, and implements the above spec.
3 Submission Instructions
To submit your homework, put all of the relevant files (1.txt,
2.txt, etc.) into a directory hw1/ and then tar and gzip
this directory into the file hw1.tgz. On Linuxlab, starting from
the parent directory of hw1/ you would do
tar zcvf hw1.tgz hw1
Now, submit this file, hw1.tgz, using the submit system, using
project number "1a" as in
java -jar Submit.jar 1a hw1.tgz
(assuming your personal Submit.jar is in the same directory as your
hw1.tgz file).
This document was translated from LATEX by
HEVEA.