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.
  1. p = 1, c = 1, s = 1, b = 1.
  2. p > 0, c = p, s = 1, b = 1.
  3. p = 1, c = 4, s = 4, b = 4.
  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.