Final ExamCMSC 433: Programming Language Technologies and ParadigmsDecember 16, 2010NameInstructionsImportant• Two times you may write Punt on any part of a question and receive five points. Thus ifyou punt a 10-point question, you will only receive 5 points for it.• Do not start until told to do so!Routine• This exam has 16 pages (including this one); make sure you have them all.• Pages 10 and 16 are blank, to use as scratch paper if you need it.• You have 120 minutes to complete the exam• The exam is worth 110 points. Allocate your time wisely: some hard questions are worthonly a few points, and some easy questions are worth a lot of points.• If you have a question, please raise your hand and wait for the instructor.• You may use the back of the exam sheets if you need extra space.• Write neatly and clearly indicate your answers.Question Points ScoreShort Answer 30Java Concurrency 30Erlang 25Erlang Servers & DSU 15Parallelization 10Total 110Enjoy your break!1. (Short Answer, 30 points)(a) (5 points) When writing a Java program you have the option of using one of two stylesof thread-safe collection: a concurrent collection, like ConcurrentHashMap, or asynchronized collection, like one returned from Collections.synchronizedMap. Givea benefit of each.A concurrent collection allows multiple threads to be reading/modifying it in parallel,whereas a synchronized collection does not. On the other hand, it is hard to makecompound operations atomic (e.g., of the flavor read-modify-write), since you cannotuse client-side locking.(b) (5 points) Give one reason why it is hard to test multithreaded programs.The main problem is nondeterminism from scheduling. For example, one run of theprogram might reveal a data race, but subsequent runs do not, making the bug hard totrack down.(c) (5 points) What problem does volatile solve?It solves the visibility problem. The Java Memory Model does not ensure sequentialconsistency, so an unsynchronized write to a field by one thread may not be seenby a subsequent read from that field from another thread. Using volatile restoressequential consistency for the given field.2(d) (5 points) MapReduce is inspired by functional programming, and the Map and Reduceare supposed to be “functional” or “not have side effects,” such as changing staticfields or writing output other than via Context. Give an advantage of this restriction.The results produced by a mapper or reducer are deterministic: they are purely a func-tion of the inputs. Therefore if a node running one of these tasks crashes it is easy torestart the computation on a different node, somewhere else.(e) (5 points) Is this class thread-safe? (Explain your answer for partial credit.)1 public class Utilities {2 public final int extra ;3 public Utilities ( int extra) { this. extra = extra ; }4 public int sum(int x, int y) { return x+y+extra; }5 public int product(int x, int y) { return x ∗ y ∗ extra ; }6 }Yes, because it is immutable.(f) (5 points) What is an advantage of using Executors instead of creating a new Threadfor each task you want to perform?It allows you to decouple the specification of tasks from the specification of resourcesto execute those tasks. Creating a thread each time allots one thread per task, allrunning in parallel. If you have many tasks and few processors, this could be veryexpensive (lots of context switching). Using an Executor, e.g., a thread pool, allowsyou to specify only as many threads as you have processors, and each thread canexecute a task one at a time, reducing overhead.32. (Java Concurrency, 30 points)Each of the next few pages contains a small program with at least two classes, one of whichis called TestCase. Consider what would happen when running TestCase.main(). If theprogram would terminate normally and always print the same answer, indicate that answer.Otherwise, indicate one or more of the following the things the program will do: (a) exhibita data race, (b) exhibit an atomicity violation, (c) exhibit a deadlock, (d) run forever, (e) printdifferent things on different runs.For full credit, briefly explain your answer (1-2 sentences). (You may want to use the backof the page.) Each problem is worth 5 points.Be careful: I am only interested in what will happen for executions of the given TestCase.main,not hypothetical ways in which the classes could be used.(a)1 public class Service implements Runnable {2 public static int liveThreads = 0;3 public static boolean done() { return liveThreads == 0; }4 public Service() { liveThreads++; }5 public void run() { liveThreads−−; }6 }78 public class TestCase {9 public static void main(String args []) {10 for ( int i=0;i<10;i++) {11 new Thread(new Service()).start();12 }13 while (! Service.done()) {} // do nothing14 System.out.println( ”done!”);15 }16 }Atomicity violation on liveThreads due to read-modify-write data races (in construc-tor and in run); as a result one of the updates might get lost, or a stale value may beread by main, so the program may not terminate.4(b)1 public class Logger {2 private ArrayList<String> records = new ArrayList<String>();3 // log an event4 public void add(String event) {5 synchronized (records) {6 records.add(event);7 }8 }9 // return (and remove) last event logged10 public String last () {11 synchronized (records) {12 int sz = records.size ();13 if (sz > 0) return records.remove(sz−1);14 else return null;15 }16 }17 }1819 public class TestCase {20 public static void main(String args []) {21 final Logger log = new Logger();22 log.add(”Hello” );23 // each thread tries to remove and print last event24 for ( int i=0;i<2;i++) {25 new Thread() {26 public void run() {27 String s = log. last ();28 if (s != null)29 System.out.println(s );30 }31 }. start ();32 }33 }34 }Deterministic outcome: prints “Hello” (not always printed from the same thread, butthat’s immaterial)5(c)1 public class NameServer {2 // location map: person (String) maps to their current location (String)3 public final ConcurrentHashMap<String,String> locations =4 new ConcurrentHashMap<String,String>();5 // Have two people trade places6 public void tradePlaces(String name1, String name2) {7 String loc1 = locations .get(name1);8 String loc2 = locations .get(name2);9 locations .put(name1,loc2);10 locations .put(name2,loc1);11 }12 }1314 public class TestCase {15 public static void main(String args []) throws InterruptedException {16 // sets initial locations17 final NameServer n = new
View Full Document
Unlocking...