Final ExamCMSC 433Programming Language Technologies and ParadigmsSpring 2009May 18, 2009GuidelinesPut your name on each page before starting the exam. Write your answers directly on the exam sheets,using the back of the page as necessary. If you finish with more than 15 minutes left in the class, thenbring your exam to the front when you are finished and leave the class as quietly as possible. Otherwise,please stay in your seat until the end.If you have a question, raise your hand and the proctor will come to you. Note, that he will notanswer general questions. If you feel an exam question assumes something that is not written, write itdown on your exam sheet. Barring some unforeseen and egregious error, however, you shouldn’t needto do this at all, so be careful when making assumptions.NOTE: There are quite a few questions to answer. Get started right away. Read each questioncarefully and answer the question that has been asked. Budget your time wisely. If you can’t answer aquestion in a few minutes, move on and come back to the difficult question later. Do not get boggeddown on a single question.Question Points Score1 92 163 104 155 206 107 20Total 1001. Short answers (9 points). Give very short (1 to 2 sentences for each issue) answers to the followingquestions. Longer responses to these questions will not be read.(a) Synchronization in Java serves three functions: visibility, ordering, atomicity. Briefly explaineach function.Answer:Answer: i. Atomicity. Al lows operation to be done without interference from otherthreads. ii. Visibility. Signals when values will be updated across threads iii. Or-dering. Allows programmers to ensure that an operation A occurs before operationB(b) In the context of Java monitors, briefly define “barging”. Answer:Barging occurs when a thread waiting for a lock outside the monitor gets the lockbefore a signaled thread inside the monitor reacquires the lock.(c) In class we compared threads to events. Provide one strength and one weakness of threads.Provide one strength and one weakness of events.Answer:Threads: Pro - allow use of multiple CPUs Con - locking can negatively affect per-formanceEvents: Pro - run fast on single CPU because no context switches needed Con - can’thave long running handlers22. Java Concurrency (16 points). Consider the following program which is meant to implement athread-safe 1-slot buffer.public class OneSlotBuffer {private boolean isFull = false;private int val;void put(int i) {while (isFull) {}; // busy loopsynchronized (this) {val = i;isFull = true;}}int take() {while (!isFull) {}; // busy loopsynchronized (this) {isFull = false;return val;}}public static void main(String[] args) {final OneSlotBuffer p = new OneSlotBuffer();// 3 THREADS CALL PUT AND TAKE ON P (see below).....}}(1) Although this program is intended to follow normal buffer semantics, under some circumstancesa single data item can be read multiple times from the buffer.Assuming 3 threads that loop forever, each one calling only p.put() or only p.take(). Provide asmallest program trace you can that shows how the above program can fail.In describing your program trace, first briefly describe your 3 threads (i.e., do they put or take).Then create a table showing the steps executed by each thread. Be explicit in showing each step.Your presentation should interleave the steps so that only one thread takes a step on each line inthe table.(2) This program might also deadlock. Give a short description how this might happen.3Answer:1) T1 does put()T2,T3 do take()T1 does exits put - isFull is trueT2 and T3 exit busy loopT2 acquires lock and completesT3 acquires lock and completes2) This question w as not counted in your grades.Access to isFull is unsynchronized. T1 could set isFull to true, but this change might notbe seen by T2 or T3.43. Deadlock (10 points). The following program acquires locks on a se t of resources. Once all locksare acquired a Runnable command is executed. The main method shows how the class is intendedto work. Unfortunately, this program is not thread safe and may deadlock. Produce an alternativemain() method and give an execution trace showing how it can lead to deadlock.public class ResourceMgr {Runnable comm;ResourceMgr (Runnable comm) {this.comm = comm;}public class Resource {public synchronized void acquire(List<Resource> rest) {if (rest.size() > 0) {(rest.remove(0)).acquire(rest);} elsecomm.run();}}public static void main(String[] args) {ResourceMgr bb = new ResourceMgr(new Runnable () {public void run () {}});// bb.new Resource() makes a new Resource inside bbfinal ResourceMgr.Resource r1 = bb.new Resource();final ResourceMgr.Resource r2 = bb.new Resource();final ResourceMgr.Resource r3 = bb.new Resource();List <Resource> resList = new ArrayList<Resource> ();resList.add(r2);resList.add(r3);r1.acquire(resList);}}5Answer:public static void main(String[] args) {ResourceMgr bb = new ResourceMgr(new Runnable() {public void run() {}});final ResourceMgr.Resource r1 = bb.new Resource();final ResourceMgr.Resource r2 = bb.new Resource();final List<Resource> resList1 = new ArrayList<Resource>();resList1.add(r2);final List<Resource> resList2 = new ArrayList<Resource>();resList2.add(r1);Executor executor = Executors.newCachedThreadPool();executor.execute(new Runnable() {public void run() {r1.acquire(resList1);}});executor.execute(new Runnable() {public void run() {r3.acquire(resList2);}});}64. Optimistic Retry (15 p oints). Suppose your application needs to keep an up to date count of thenumber of threads using a resource and needs to do lengthy computations whenever a thread startsor stops using the resource (you will ignore these lengthy computations in your answer, however).Supp ose further that you want to minimize overal locking time. Fill in the following code snippetsthat implement the Optimistic Retry strategy when threads start and stop using the resource.You may not add any synchronized blocks beyond that provided by numInside() and commit()methods.class Resource {protected Integer numCust = 0;public synchronized Integer numInside() {return numCust;}// FILL IN THE NEXT 3 METHODS ON FOLLOWING PAGEprivate synchronized boolean commit(Integer assumed, Integer desired);public void enter();public void exit()public static void main(String[] args) throws InterruptedException {final Resource r1 = new Resource();ExecutorService executor = Executors.newCachedThreadPool();Runnable r = new Runnable() {public void run() {r1.enter();/* Use
View Full Document
Unlocking...