CMSC433 Spring 2019 Midterm Exam Print your name:_____________________________________________
Instructions
● Do not start this test until you are told to do so!
● You have 75 minutes to take this midterm.
● This exam has a total of 100 points, so allocate 45 seconds for each point.
● You may only use your own double-sided single page 8″x11″ cheat sheet. No other
notes or aids are allowed.
● Answer short answer questions concisely in 2-3 sentences. Longer answers are not
needed.
● For partial credit, show all of your work and clearly indicate your answers.
● Write neatly. Credit cannot be given for illegible answers.
Problems
Score
1.True/False
/18
2. Short Answer
/50
3. Coding
/32
Total
/100
1
1. True/False/Multiple Choice Questions [15 points]
(1) True False A program with a race condition will always produce incorrect results.
(2) True False If the release() method of a newly constructed semaphore is called before any thread ever calls the semaphore’s acquire() method, the release() method will have no effect.
(3) True False The get() method of a FutureTask does not guarantee that it can return a value immediately and as a result, it may block execution in some cases.
(4) True False An object’s intrinsic lock must be acquired before the wait(), notify(), and notifyAll() methods can be called on that object.
(5) True False A Java thread will enter the BLOCKED state if Thread.sleep(500) is called.
(6) True False A Java program will terminate once all user threads have terminated.
(7) True False The implementation of Java’s intrinsic locks ensures that threads gain access to the lock in FIFO (first in, first out) order.
(8) True False A sleeping thread does not release the locks it holds, while wait() releases the lock on the object that wait() is called on
(9) True False Fail-fast iterators can throw a ConcurrentModificationException if the underlying data structure is modified in the middle of iteration.
(10) True False start() method of Thread class can be overrideen.
(11) True False When intrinsic locks are nested, inner lock must be released before the outer lock.
(12) Within a process that is using multiple threads, identify if each of the following resources is shared between the threads, or if each thread gets its own copy (Circle your answer).
1) Stack
2) Heap
3) Program counter
4) Local variables
Shared / Shared / Shared /
Not Shared Not Shared Not Shared
Shared / Not Shared
2
(13) True False ThreadPoolExecutor is an implementation of ExecutorService in the Java standard library?
(14) True False A long (64-bit) variable could be written in two separate steps, so by default, there is no atomicity guarantee.
(15) True False Multiple threads that belong to one process can be executed on multiple network-connected computers.
3
2. Short Answer
1)[5 pts] What is the output of main()? Justify your answer. (and/or What is the problem with the code below? How would you fix it?)
public class MyThread extends Thread {
private static int count = 0;
public void run() {
synchronized(this) {
count++;
} }
public int getCount() {
return count;
} }
public static void main(String[] args) {
MyThread[] threads = new MyThread[10];
for (int i = 0; i < 10; ++i) {
threads[i] = new MyThread();
threads[i].start();
}
System.out.println(threads[0].getCount());
}
2. [4 pts]
Consider the following code used by a bank to transfer money between accounts:
public static void transfer(Account from, Account to, int amount) {
synchronized(from) {
} }
synchronized(to) {
from.money -= amount;
to.money += amount;
}
Identify an order of events that will cause the code to deadlock. What could you change to ensure this will not happen?
4
3. [4 pts]What is the difference between a reentrant and non-reentrant lock?
4. [5 pts] The code below uses a BlockingQueue to store a series of Integers and keeps track of the number of even Integers that it is storing in the queue. The queue’s put() method blocks until there is space to place the number into the queue. In this case, the queue has a capacity of 5. Similarly, the queue’s take() method blocks until there is a number to remove from the queue. In a multithreaded program where when one thread calls insert() and another thread calls remove(), sometimes the program hangs indefinitely. Describe one scenario that could cause this to happen.
Public class NumberManager {
private BlockingQueue
private volatile int numEvens = 0;
public synchronized void insert(int num) throws InterruptedException {
if ((num % 2) == 0) { numEvens++; }
q.put(num);
}
public synchronized int remove() throws InterruptedException {
int num = q.take();
if ((num % 2) == 0) { numEvens–; }
return num;
}
public synchronized int getNumEvens() { return numEvens; }
}
5
5. [4 pts] What does it mean for an Object to be confined to the stack?
6. [4 pts] What does the Thread.yield() method do?
7. [4 pts] Given the following event trace, are there any data races, and if so, what are they? Justify your answer.
R = read(T1,x,0); write(T2,x,1); lock(T2,y); write(T2,y,4); write(T1,x,-1);
unlock(T2,y); write(T1,y,1);
8. Risky Rimon has just learned about threads. But he has a problem. His favorite Backstreet Boys album is lost somewhere in his computer’s file system. He wants to write a program to find its location by recursively traversing the directories. At every directory, a thread checks the present files and spawns a new thread for each of the subdirectories, which check those, spawns new threads, and so on.
A) [3pts]ExplaintoRimonwhythisisanotagreatapproachtofindinghisbelovedalbum.
B) [4pts]Whatwouldbeabetterapproach?Thisapproachmustutilizethreadsandshould run quicker than a sequential search algorithm. Write one or two sentences.
6
9. [4 pts] Why do we use notifyall() instead of notify()?
10. [4 pts] Suppose this is a function from a class.
ConcurrentHashMap m = new ConcurrentHashMap()
public void insert(K key, V val) {
if (!m.containsKey(key)){
m.put(key, val)
} }
If this function is supposed to insert a value if and only if the key is absent from the hashmap, explain a problem with this code. If none, write none.
11. [5 pts] Assuming the locks below are shared between three methods, is there a scenario in a multithreaded program where a deadlock can happen? If so, briefly describe the execution sequence that causes a deadlock to happen. If a deadlock cannot happen, explain why that would be the case.
Method 1
synchronized (A) {
synchronized (B) {
synchronized (D) {
…
} }
}
Method 2
synchronized (B) {
synchronized (C) {
… }
}
Method 3
synchronized (C) {
synchronized (D) {
… }
}
7
3.Programming
1.[16 pts] During a project for your CMSC433 class, your evil instructors have barred you from using Java’s concurrent collections library. After complaining on Piazza, you decide to take matters into your own hands.
Implement the methods of a ConcurrentHashSet in the space below. Remember that a good ConcurrentHashSet, just like a ConcurrentHashMap, should use lock striping.
Your implementation only needs to handle Integer objects (don’t bother with generic types). For hashing, just use the built-in Object.hashCode() method. You may use a one-lock-per-bucket strategy. You only need to implement the methods below.
public class MyConcurrentHashSet {
private ArrayList
private int buckets;
public MyConcurrentHashSet(int buckets) {
this.buckets = buckets;
this.set = new ArrayList
for (int i = 0; i < buckets; ++i) {
this.set.add(new ArrayList
}
}
public void add(Integer o) {
int bucket = o.hashCode() % buckets;
}
8
} }
public void remove(Integer o) {
int bucket = o.hashCode() % buckets;
}
public int size() {
//size() only needs to be weakly consistent!
9
2. [16 pts] The FileResource class represents a file that can be read from and written to by using the read() and write() methods. This class is not thread safe so we decide to place it inside of a thread safe FileManager class to manage all the read and write requests to the file.
The skeleton for the FileManager class is given to you below, followed by further details. The constructor takes a FileResource that will be managed and the maximum number of threads that are allowed to read the file at once. You are responsible for implementing the safeRead() and safeWrite() methods of this class.
public class FileManager {
// the file being managed
private final FileResource file;
// the maximum number of readers that can read the file at once private final int maxReaders;
/* You may add additional fields if needed below */
public FileManager(FileResource file, int maxReaders) {
if (maxReaders < 2) {
throw new IllegalArgumentException(“Not enough readers”);
}
this.file = file;
this.maxReaders = maxReaders;
/* Initialize additional fields here if needed */
}
10
public void safeWrite(String newData) throws InterruptedException {
/* If needed, perform synchronization below */
file.write(newData);
/* If needed, perform clean up here */
}
public String safeRead() throws InterruptedException {
/* If needed, perform synchronization below */
String data = file.read();
/* If needed, perform clean up here before returning data */
return data;
} }
11
In your implementation, safeRead() and safeWrite() must meet the following constraints:
● If a writer thread is writing to the file by calling safeWrite(), then no other writers or readers should be allowed to access the file until the writer is done.
● If one or more reader threads are reading the file by calling safeRead(), then no writer should be allowed to write to the file until the readers are done.
● If no writer is writing, up to maxReaders threads should be able to read the file at the same time. Do not over synchronize the code such that only one reader can ever read.
● For example:
○ maxReaders=2
○ Reader1isreading
○ Writer1isblocked
○ Reader2arrivesafterwriter1.Reader2canread
○ Reader3arrivesanditisblockedbecausemaxReaders=2
○ Now,whenreader1finishesifreader2isstillreading,reader
3 should not access the file before writer 1.
○ Writer1writestothefile,andthenreader3readsfromthe
file.
● No execution sequence should produce a deadlock.
You can make the following assumptions:
● maxReaderswillalwaysbegreaterthanorequalto2.
● You do not need to write any import statements even if you use classes that require
them. You can assume that every class will be imported for you.
● None of the reader or writer threads will be starved and will each have the opportunity to
call the safeRead() or safeWrite() method.
You are allowed to add any additional fields that you think will be necessary to the class. Also, you are allowed to use any of the Java synchronizer classes that you have learned about, except for ReadWriteLock. The safeRead() and safeWrite() methods already call the read() and write() methods, so you are only responsible for adding the synchronization code.
12