CMSC433 Fall 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
/15
2. Short Answer
/55
3. Coding
/30
Total
/100
Page 1 / 11
1. True/False/Multiple Choice Questions [15 points]
1. T / F Suppose we have an Object class instance called object. A call to object.wait() have to happen after the current thread gains the intrinsic lock of object in order to avoid IllegalMonitorStateException.
2. T / F synchronized blocks in Java are NOT reentrant.
3. T / F Java volatile keyword guarantees that all threads see the latest updated
value for the variable.
4. T / F One java program cannot be thread-safe without the use of the
synchronized (…) {…} block.
5. T / F After you gain the lock from a Lock object called lock by calling lock.lock(), a call to the method lock.wait() releases that lock and blocks the current thread until a call to lock.signal() or lock.signalAll() by another thread wakes it up.
6. T / F If an object is effectively immutable, it is thread-safe.
7. In a ForkJoinPool when the worker threads retrieve tasks from deques, in what order are the tasks retrieved?
a. FIFO
b. LIFO
c. FILO
d. LIFO & FIFO
8. T / F Java’s synchronized statement will block if the thread executing it already holds the lock that is being acquired.
9. Threads have their own copy of ________ and _________. Processes have their own copy of ____________.
10. T / F
A. stack B. program counter C. heap
All writes to final fields are immediately visible.
Page 2 / 11
11. Given the following thread state transition graph, match (draw a line) the operations to the transitions.
1. Request a lock
2. sleep
3. wait
4. new Thread()
5. start()
Page 3 / 11
2. Short Answer [55 pts]
1. Suppose you are creating a new social network with many users. In order to handle the volume of all users, you decide to use multithreading to create user profiles concurrently. Below is the code for the UserProfile class, which represents each user’s profile, and allows the user to add another user to their friends list:
class UserProfile {
static int idCounter = 0;
int id; // an ID that is unique for each account
int[] friends;
int numFriends;
public UserProfile(int maxFriends) {
id = idCounter++;
friends = new int[maxFriends];
numFriends = 0;
}
public synchronized void makeFriends(UserProfile newFriend) {
synchronized (newFriend) {
if (numFriends == friends.length ||
newFriend.numFriends == newFriend.friends.length)
throw new TooManyFriendsException();
friends[numFriends++] = newFriend.id;
newFriend.friends[newFriend.numFriends++] = id;
}
} // end of method
} // end of class
a) [4 pts] Does the constructor have any problems? If so, describe a way to fix it. If not, explain why it is correct.
b) [4 pts] While concurrently running the makeFriends() method with different threads, our program encounters a deadlock. Explain how this can occur, and a strategy we can use to fix it.
Page 4 / 11
2. Inspect the following code and answer the questions.
public class User {
public static final List
public User() { allUsers.add(this); }
public List
List
otherUsers.remove(this);
return otherUsers;
} }
a) [4 pts] Do the “public static final” keywords before the field allUsers make such a field thread-safe? Please also briefly explain why.
b) [4 pts] Is there anything wrong about the static field allUsers after multiple threads call the constructor of the class for multiple times? And, if so, why is that? If there is nothing wrong, just write “Nothing wrong.” Otherwise, briefly describe what will go wrong and explain why.
c) [4 pts] ASSUME that we make modifications to fix the code, so that all other parts of the code except the instance method getOtherUsers() become thread-safe. Is the code inside getOtherUsers() posting any threat to the thread safety of the class? If “No,” just write “No.” Otherwise, please also explain why.
Page 5 / 11
3. [4 pts] Explain the differences between sleep() and wait().
4. [4 pts] Briefly explain how one could avoid deadlock caused by nested synchronized blocks.
5. Read the following code fragment and answer the questions.
public class SyncCounter {
Integer internalCounter;
public SyncCounter() {
internalCounter = Integer.valueOf(0);
}
public void count() {
synchronized (internalCounter) {
internalCounter += 1;
}
}
public int getCount() {
return internalCounter;
}
}
a) [4 pts] Is the method count() t hread-safe? Briefly explain your answer.
b) [4 pts] Assume that the method count() is thread-safe. Is the method getCount() thread-safe? Briefly explain your answer. (Please answer this question on the next page)
Page 6 / 11
(Please answer 2.5. b) here…)
6. Recall that in project 2, a customer waits for a seat, places an order, waits for the order, and leaves the restaurant. Usually, a static semaphore (in this case, Simulation.numberOfTablesAvailable) is used to ensure that the number of customers in the restaurant does not exceed its limit.
Suppose, now, that the customer has little patience. If the order is not ready within 2 seconds, the customer gives up waiting and leaves disappointed. The following code implements this, with logging and order placing omitted for simplicity. Simulation joins all customer threads and does not interrupt them.
// In Customer.java
public void run() {
try {
Simulation.numberOfTablesAvailable.acquire();
// Please Fill in the blank!
CountDownLatch waitForOrderToBeReady = new CountDownLatch(________);
// … place order …
// A cook will call waitForOrderToBeReady.countDown();
// when the order is complete
waitForOrderToBeReady.await(2, TimeUnit.SECONDS);
Simulation.numberOfTablesAvailable.release();
} catch (InterruptedException e) {
System.out.println(“Customer left because the order took too long!”);
}
}
a) [2 pts] Fill in the blank above.
b) [4 pts] Is the semaphore used properly? If so, explain how it achieves the goal. Otherwise, explain
any issue and how it can be fixed.
Page 7 / 11
7. [4 pts] Suppose you want to parallelize operations (insert/search/remove) in a binary search tree. Your friend suggests that you allow multiple threads to add elements in parallel, with each thread locking on the current element being used by that thread. Is your friend’s strategy suitable to use? Explain your answer.
8. [4 pts] Explain the difference between synchronizedMap and concurrentHashMap
9. [5 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); lock(T2,y); write(T2,y,4); write(T1,x,-1); unlock(T2,y); write(T2,x,1); write(T1,y,1)
Page 8 / 11
3. Coding [30 pts]
1.[12 pts] In the code fragment below, the ForkJoinProduct class computes the product of an array of BigInteger objects with the fork-join Framework. The compute() method multiplies the elements in a range of indices from the start to the end (be advised that start is inclusive, while end is not). If the range has 100 or fewer elements, it computes the product directly with a loop. Otherwise, it creates two sub-tasks for problems of half the size. It uses the fork() method to calculate the product of the left half in parallel while calculating the product of the right half in the current execution.
Please help complete the compute() method by filling the blanks below.
Note: 1. You do not have to know about the BigInteger class to complete this question.
2. This is the PRODUCT, not the SUM.
public class ForkJoinProduct extends RecursiveTask
private final BigInteger[] allNums;
private final int start, end;
public ForkJoinProduct(BigInteger[] allNums, int start, int end) {
this.allNums = allNums;
this.start = start;
this.end = end;
}
@Override
protected Long compute() {
/* Hint: new BigInteger(String val) initializes a BigInteger. */
BigInteger result = new BigInteger(“________”);
if(end – start <= ________) {
for (int i = ________________; ________________; ++i) {
/* Hint: bigInt.multiply(BigInteger val)
* returns the product of bigInt and val. */
result = result.multiply(________________________);
}
} else {
/* lf: left half.
* rt: right half.
* mid: the midpoint of the range.
* lfResult, rtResult: left and right results. * /
ForkJoinProduct lf, rt;
int mid, lfResult, rtResult;
mid = (start + end) / 2;
sub1 = new ________________________________________________________________;
sub2 = new ________________________________________________________________;
Page 9 / 11
________________________________________________________________;
rtResult = sub2.________________________________;
lfResult = sub1.________________________________;
result = lfResult.multiply(rtResult);
}
return result;
} // end of the compute method
} // end of class declaration
2.[12 pts] Implement the Semaphore class. A semaphore object is initialized with a number of permits. Clients can acquire permits by calling acquire(), and return permits by calling release(). When there is no permit left in the semaphore, acquire() blocks until one is available.
Note that a semaphore simply keeps track of a number of permits. Clients may return permits without acquiring one. At any point, it is possible for it to have more permits than what it initially has. If it is initialized with a negative number of permits, all acquire() calls block until enough permits have been added. This follows official Java documentation, and simplifies your task.
public class Semaphore {
private Integer permits;
// Add any variables you want to use here.
public Semaphore(Integer permits) {
}
public void acquire() {
} // code fragment continued on the next page
public void release() {
}
} // end of class declaration
Page 10 / 11
3.[6 pts] Implementation of the Philosopher in the dining philosophers problem is given below. This implementation can cause deadlock if all philosophers get the left fork (line 11), and wait for the right lock (line 12). One solution is to have 4 chairs only and allow maximum 4 philosophers to eat at any time. Modify the Philosopher such that at most 4 philosophers can sit down and eat together. You can rewrite your implementation or directly modify the following code.
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
class Philosopher implements Runnable {
private Object left, right;
public Philosopher(Object left, Object right) {
this.left = left;
this.right = right;
}
public void run() {
while(true) {
think();
synchronized(left) {
synchronized(right) {
eat();
} }
} }
Page 11 / 11