When is locking necessary
concurrency, consistency, java, multithreading
Solution
This is a fairly subtle question, not stupid at all.
Multiple threads that are reading a data structure concurrently may do so without synchronization, only if the data structure has been safely published. This is memory visibility issue, not a timing issue or race condition.
See section 3.5 of Goetz, et. al., Java Concurrency In Practice, for further discussion of the concept of safe publication. Section 3.5.4 on "Effectively Immutable Objects" seems applicable here, as the board becomes effectively immutable at a certain point, because it is never written to after it has reached the solved state.
Briefly, the writer threads and the reader threads must perform some memory-coordinating activity to ensure that the reader threads have a consistent view of what has been written. For example, the writer thread could write the sudoku board and then, while holding a lock, store a reference to the board in a static field. The reading threads could then load that reference, while holding the lock. Once they've done that, they are assured that all previous writes to the board are visible and consistent. After that, the reader threads may access the board structure freely, with no further synchronization.
There are other ways to coordinate memory visibility, such as writes/reads to a volatile variable or an `AtomicReference`. Use of higher-level concurrency constructs, such as latches or barriers, or submitting tasks to an `ExecutorService`, will also provide memory visibility guarantees.
UPDATE
Based on an exchange in the comments with Donal Fellows, I should also point out that the safe publication requirement also applies when getting results back from the reader threads. That is, once one of the reader threads has a result from its portion of the computation, it needs to publish that result somewhere so that it can be combined with the other reader threads' results. The same techniques can be used as before, such as locking/synchronization over a shared data structure, volatiles, etc. However, this is usually not necessary, since the results can be obtained from a `Future` returned by `ExecutorService.submit` or `invoke`. These constructs handle the safe publication requirements automatically, so the application doesn't have to deal with synchronization.
Problem
Ok, I know this may sound quite stupid (and I'm afraid it is), but I'm not completely satisfied with the answer I gave myself so I thought it was worth it asking it here. I'm dealing with an exercise about concurrency (in Java) which goes like this Given a solved Sudoku chart, determine, using a fixed number of threads running at the same time, whether the chart has been correctly solved, i.e. no violation of the canonical rules occur (a number must appear within its row, its column, and its block only once). Now my question is: since the threads only have to perform "reads", gathering infos from the chart and elaborating them somewhere else, couldn't they work without worrying about concurrency? Chart's state is always consistent since no "writes" are performed, hence it's never changed. Aren't locks/synchronized blocks/synchronized methods necessary if and only if there's a risk for resources' consistency to be lost? In other words, did I understand concurrency the right way?