When is locking necessary

Question

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?

Answer 1

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.

Answer 2

In my opinion your understanding is correct. Data corruption can only happen if any of the threads is writing on the data.

If you're 100% sure that no thread is writing, then it's safe to skip synchronization and locking...

EDIT: skipping locking in theses cases is the best practice! :)

Answer 3

No need of Synchronizing the file if it is read-only.Basically lock is applied to critical section.Critical section is ,where different threads accessing the shared memory concurrently. Since Synchronization makes program slow as no multiple threads access at same time so better not to use lock in case of read-only files.

Answer 4

Imagine you have a bunch of work to complete (check 9 rows, 9 columns, 9 blocks). If you want threads to complete this bunch of 27 units of work and if you want to complete the work without double work, then the threads would need to be synchronized. If on the other hand, you are happy to have threads that may perform a work unit that has been done by another thread, then you don't need to synchronize the threads.