You're working for a startup company Ginormous Data Inc. (GDI) that specializes in finding patterns in large amounts of data. For example, a big retailer might give GDI all the web visits and purchases made and all the credit reports they've inspected and records of all the phone calls to them, and GDI will then find patterns in the data that suggest which toys will be hot this Christmas season. The programs that GDI writes are mostly written in Java. They aren't perfect; they're just heuristics, and they're operating on incomplete and sometimes-inaccurate information. They do need to be fast, though, as your clients are trying to find patterns faster than their competition can, and are willing to put up with a few errors even if the results aren't perfect, so long as they get good-enough results quickly.
GDI regularly uses multithreading to speed up its applications, and many of GDI's programs operate on shared-memory representations of the state of a simulation. These states are updated safely, using Java's synchronized keyword, and this is known to be a bottleneck in the code. Your boss asks you what will happen if you remove the synchronized keyword. You reply, "It'll break the simulations." She responds, "So what? If it's just a small amount of breakage, that might be good enough. Or maybe you can substitute some other synchronization strategy that's less heavyweight, and that'll be good enough." She suggests that you look into this by measuring how often GDI's programs are likely to break if they switch to inadequate-but-faster synchronization methods, and also by looking into a safe technique that is faster than synchronized.
In some sense the first part of this assignment is the reverse of what software engineers traditionally do with multithreaded applications. Traditionally, they are worried about race conditions and insert enough synchronization so that the races become impossible. Here, though, you're deliberately trying to add races to the code in order to speed it up, and want to measure whether (and ideally, how badly) things will break if you do.
It should be noted that we are on thin ice here, so thin that some would argue we've gone over the edge. That's OK: we're experimenting! For more about the overall topic, please see: Boehm H-J, Adve SV. You don't know jack about shared variables or memory models. ACM Queue 2011 Dec;9(12):40. doi:10.1145/2076796.2088916.
Java synchronization is based on the Java memory model (JMM), which defines how an application can safely avoid data races when accessing shared memory. The JMM lets Java implementations optimize accesses by allowing more behaviors than the intuitive semantics where there is a global clock and actions by threads interleave in a schedule that assumes sequential consistency. On modern hardware, these intuitive semantics are often incorrect: for example, intraprocessor cache communication might be faster than memory, which means that a cached read can return a new value on one processor before an uncached read returns an old value on another. To allow this kind of optimization, first, the JMM says that two accesses to the same location conflict if they come from different threads, at least one is a write, and the location is not declared to be volatile; and second, the JMM says that behavior is well-defined to be data-race free (DRF) unless two conflicting accesses occur without synchronization in between.
The details for proving that a program is DRF can be tricky, as is optimizing a Java implementation with data-race freedom in mind. Not only have serious memory-synchronization bugs been found in Java implementations, occasionally bugs have been found in the JMM itself, and sometimes people have even announced bugs only to find out later that they weren't bugs after all. For more details about this, please see: Lochbihler A. Making the Java memory model safe [PDF]. ACM TOPLAS 2013 Dec;35(4):12. doi:10.1145/2518191. You needn't read all this paper, just the first eight pages or so—through the end of §1.1.3.
It's easy to write programs that break sequential consistency in Java. To model this, you will use a simple prototype that manages a data structure that represents an array of longs. Each array entry starts at zero. A state transition, called a swap, consists of subtracting 1 from one of the entries, and adding 1 to an entry – typically a different entry although the two entries can be the same in which case a swap does nothing. The sum of all the array entries should therefore remain zero; if it becomes nonzero, that indicates that one or more transitions weren't done correctly. The converse is not true: if the sum is zero it's still possible that some state transitions were done incorrectly. Still, this test is a reasonable way to check for errors in the simulation.
For an example of a simulation, see jmm.jar, a JAR file containing the simplified source code of a simulation. It contains the following interfaces and classes:
time timeout 3600 java UnsafeMemory Synchronized 8 100000000 5Here, the initial time tells the shell to give top-level real, user and system time. The timeout 3600 puts a 3600-second timeout on Java, helpful if your program mistakenly loops forever. Synchronized means to test the SynchronizedState implementation; 8 means to divide the work into 8 threads of roughly equal size; 100000000 means to do 100 million swap transitions total; and 5 says to use a state array of 5 entries. The output of this command should look something like this:
Total time 4.71665 s real, 5.14257 s CPU Average swap time 377.332 ns real, 51.4257 ns CPU real 0m4.843s user 0m5.248s sys 0m0.060sThe output says that from Java’s point of view the entire test took 4.71665 s in real time and 5.14257 s of CPU time (the latter can be greater than the former in multithreaded programs). It also says that a single swap by a single thread took an average of 377.332 ns of real time and 51.4257 ns of CPU time (the former should always be greater than the latter). From the Linux kernel’s point of view, the entire Java program consumed 4.843 s real time, 5.248 s user CPU time, and 0.060 s system CPU time.
Build and use a sequential-consistency-violating performance and reliability testing program, along the lines described below.
Do the following tasks and submit work that embodies your results.
To help think about your AcmeSafeState implementation, read Doug Lea's Using JDK 9 Memory Order Nodes, and you can look at the following packages and classes for other facts and ideas:
Write a report that contains the following explanations and discussions. Your report should be at least two and at most five pages long, using 10-point font in a two-column format on an 8½"×11" page, as suggested in the USENIX template mentioned in Resources for written reports and oral presentations.
Submit two files:
Do not put your name or student-ID into your submissions.