433 Final Exam Answers, May 20th1. (25 points) Bakery algorithm for first-in, first-out queuingThis question requires you to reimplement the OnePlaceBuffer interface we used in our first day quiz.However, if multiple threads block trying to c all take(), they should return in FIFO (first-in, first-out)order. Calls to put(Object o) do not have to complete in FIFO order. For our implementation, weare going to ignore and discard interrupts.package cmsc433;public interface OnePlaceBuffer {public Object take();public void put(Object o);}ANSWER:Here is my solution, based on the bakery algorithm:public class MyBuffer implements cmsc433.OnePlaceBuffer {private Object buf = null;private int nowServing = 0;private int nextNumber = 1;public synchronized Object take() {int myNumber = nextNumber++;while(nowServing != myNumber)try {wait();} catch(InterruptedException e) {}Object result = buf;buf = null;notifyAll();return result;}public synchronized void put(Object o) {while(buf != null)try {wait();} catch(InterruptedException e) {}buf = o;nowServing++;notifyAll();}}1A slightly different solution is:public class MyBuffer implements cmsc433.OnePlaceBuffer{private Object buf = null;private int nowServing = 0;private int nextNumber = 0;public synchronized Object take() {int myNumber = nextNumber++;while(buf == null || nowServing != myNumber)try {wait();} catch(InterruptedException e) {}Object result = buf;buf = null;nowServing++;notifyAll();return result;}public synchronized void put(Object o) {while(buf != null)try {wait();} catch(InterruptedException e) {}buf = o;notifyAll();}}Both of these solutions is fine. The only slight problem with it is that it uses notifyAll, and all of thewaiting threads have to check to see if their number has been called.Now, in class I said that this was usually not a problem in practice and no one would loose points inmy class for doing a notifyAll solution. However, several students tried a solution using a queue ofwaiting threads, perhaps to avoid waking up all threads. This is very difficult to get right. There areall sorts of potential problems involving issues such as subtle race conditions, holding locks on morethan one object, and deadlo ck.2However, for your enjoyment, here is my solution using a queue. In this solution, we only wake up onethread at a time.public class MyBuffer2 implements cmsc433.OnePlaceBuffer {static class Status {boolean ready = false;}private Object buf = null;private LinkedList queue = new LinkedList();public Object take() {Status s;synchronized (this) {if (buf != null && queue.isEmpty()) {Object result = buf;buf = null;notify();return result;}s = new Status();queue.addLast(s);}synchronized(s) {while (!s.ready)try {s.wait();} catch (InterruptedException e) {}}synchronized(this) {assert buf != null;Object result = buf;buf = null;notify();Status s2 = (Status) queue.removeFirst();assert s == s2;return result;}}public synchronized void put(Object o) {while(buf != null)try {wait();} catch (InterruptedException e) {}buf = o;if (!queue.isEmpty()) {Status first = (Status) queue.get(0);// holding two locks is OK because the locks are ordered// (we always get the Buffer lock before we get a Status// lock), and we don’t do a wait while holding two lockssynchronized(first) {first.ready = true;first.notify();}}}}32. (10 points) Iterating through collections in a multithreaded context.Assume you have a collection S which is accessed and updated by multiple threads (protected bysynchronization on S.Write a function foo() that iterates through all of the elements of S and invokes bar(Object o) oneach element of the collection.Note that a call to bar could take a while to perform.Discuss any particular advantages/disadvantages/features of your solution that a user of your codeshould b e aware of.ANSWER:Since a call to bar could take a while to perform, we don’t want to hold a lock on S for the durationof all the calls to bar. However, we are not going to p erform the calls to bar in parallel. This solutionmakes a copy of the collection before the iteration starts, and thus any changes to the collection duringthe iteration will not b e reflected in the iteration.void foo() {LinkedList lst;synchronized(S) {lst = new LinkedList(S);}for(Iterator i = lst.iterator(); i.hasNext(); )bar(i.next());}3. (10 points) XML. There are two basic approaches/APIs for dealing with XML documents. In class,we discussed these as the SAX and the DOM approaches. Briefly describe the differences and relativeadvantages/disadvantages of these approaches.ANSWER: The SAX approach essentially provides a visitor pattern over the XML tree. Callbacksare made at each internal and leaf node.The DOM approach generates a tree data structure representing the entire XML tree.The SAX approach can be more efficient, particular in terms of memory. However, the DOM approachallows arbitrary traversals and modifications of the tree.4. (5 points) Security. Why might you wish to restrict the machines and ports that untrusted code canconnect to?ANSWER: Because untrusted code might be run behind a firewall. Machines behind a firewall areoften not as secured as machines directly exposed to the internet, and often provide unsecured services.For example, untrusted code could problem local machines to see if any were vunerable to well-knownbut unfortunately common vunerabilities (such as Windows XP having a default administrator accountwith no password).5. (5 points) You’ve calculated/measured that the data structures in use by your program require 100+10nKbytes at any one time to handle n warehouses. Your program will be doing a reasonable amount ofmemory allocation (with some of the previously allocated memory becoming unreachable and thereforegarbage), so you need to worry about the cost of garbage collection.Assume you are using a standard stop-and-copy garbage collector. For 1000 warehouses, which numberis best estimate for the amount of heap memory your program would need to run in so that garbagecollection would be efficient? Explain your choice:• 10 Megabytes4• 15 Megabytes• 25 Megabytes• 50 MegabytesANSWER: 25 MegabytesYour date s tructures need 10.1 Megabytes of live memory. With a simple copying collector, you havetwo semispaces, each large enough to hold all of live memory and a little extra. So 25 Megabytes isenough, and 50 Megabytes is far more than you need.6. (10 points) Mix and matchFor each item in the left column, match it with the problem or domain in the right column
View Full Document
Unlocking...