This lab is a tutorial on concurrent programming in Java. The knowledge and skills you acquire in this tutorial will be critical in upcoming labs.
See previous labs.
See previous labs.
This series of exercises is intended to serve as an introduction to writing concurrent programs in Java. In order to complete later labs, you must have a strong understanding of a few basic concepts.
For some of you, this may be your first experience with concurrency. Others of you may have had some exposure in previous courses (e.g., operating systems). Whether this is an introduction or a review, I hope you find this tutorial helpful.
Oracle, the company that maintains the Java language, has a very well written tutorial on concurrency. Please read the Java Concurrency Tutorial. Please read up to and including the section titled “Guarded Blocks.” Later parts of this tutorial will refer to specific sections of this tutorial.
You are expected to modify these files:
SynchronizedThreads.javaLockManagerDemo.javaZigZagThreads.javaYou are expected to read but not modify Deadlock.java.
Task 1 Read the tutorial on concurrency up to and including “Guarded Blocks.”
The SynchronizedThreads class demonstrates a simple program in which multiple threads (Incrementers) concurrently access a single shared object (a Counter). Review this code and make sure you understand it.
Run the main program see if the threads interfere with each other. Play around with the parameters. For example, if numThreads is 1, there should be no interference. Similarly if numAdds is 1 or a small number, you might not experience any interference.
Task 2 Prevent interference (aka race conditions) by modifying the code. You may wish to review the section of the Java tutorial on synchronization, especially the part on synchronization idioms.
There are at least two ways to prevent inference: one way modifies the Counter class; the other way leaves Counter unchanged and modifies the Incrementer class. Implement at least one way and complete questions 1 and 2 on the handout.
Check out the Deadlock example. This is copied directly from the corresponding section on deadlock in the Java tutorial.
Task 3. Explain the deadlock that happens in Deadlock in terms of locks and threads waiting on locks. The two threads in this case are alphonse and gaston. See the specific questions on the handout.
The LockManagerDemo is very similar to SynchronizedThreads except that concurrency is handled by a lock manager. The lock manager is a separate class that manages shared resources. Threads (such as Incrementer objects) that want to access shared objects (such as Counter) must ask the lock manager for a lock and then release it when done. The advantage of this is the nitty gritty details of lock management are encapsulated into a single class; all other classes like Incrementer and Counter don’t need to “worry” about these details.
Pay special attention to this example as you will implement something similar in an upcoming lab!
Task 4 Explain why acquireLock uses a synchronized statement inside the body of the method. In other words, why not just make the acquireLock method synchronized, just like releaseLock? Will this work? Why or why not? Record your answers in the writeup.
This implementation uses a busy wait: the thread keeps looping until it gets the lock. This can be wasteful because the thread uses up valuable CPU cycles waiting for the lock. To reduce wasteful CPU cycles, the thread goes to sleep for 1 millisecond each time throught the loop. But an even better way is to have the thread pause completely until the lock becomes available.
Task 5 Revise this code to use wait and notifyAll as illustrated in the Java tutorial.
While waiting and notifying is generally preferred, busy waiting can have its advantages in some cases. In an upcoming, you may find busy waiting makes it easier to detect deadlock (because each thread can keep track of how long it has been waiting).
Check out the ZigZagThreads class. The main method of this program spawns a bunch of Ziggers and then a bunch of Zaggers. Ziggers print this pattern
//////////
and Zaggers print this pattern
\\\\\\\\\\
If you run the code, you will probably see a bunch of zigs followed by a bunch of zags. This is not what we want. Instead, we want this pattern:
//////////
\\\\\\\\\\
//////////
\\\\\\\\\\
//////////
\\\\\\\\\\
...
Notice that before printing, both Ziggers and Zaggers must acquire a lock. Your task is to implement a lock manager that forces them to alternate, producing the desired pattern.
Task 6. Implement the lock manager in ZigZagThreads to achieve the desired pattern. Hint: the lock manager needs to keep track of two things. The first thing is whether someone has the lock (i.e., someone is busy printing). The second thing is whose turn it is (a Zigger or Zagger).
You might think this zig zag thing is a weird problem – and it kind of is – but in an upcoming lab, you will implement a lock manager for page objects that will actually bear some similarity to this problem. In particular, you will not only have to manage locks but you also have to make sure that the lock is granted to the appropriate thread. Here, Ziggers and Zaggers must “take turns”; in an upcoming lab, some threads will have higher priority than others and will be able to “cut in line” and acquire the lock first.
The milestone for this lab is to complete the above tasks and submit the writeup. (There are no unit tests.)
Please turn in your write up in class on Monday (11/5). Please be prepared to demo your code at the start of the following lab (11/6).