When is locking necessary

Question 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.

Question 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! :)

Question 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.

Question 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.

Question 5

Scenario where Thread1 writes some data and then a bunch of threads need to read this data doesn't require locking if done properly. By properly I mean that your SUDOKU board is an immutable object, and by immutable object I mean:

State cannot be modified after construction
State is not actually modified via some reflection dark magic
All the fields are final
'this' reference does not escape during construction (this could happen if during construction you do something along the lines MyClass.instnce = this).

If you pass this object to the worker threads you are good to go. If your objects don't satisfy all these conditions you still may run into concurrency problems, in most cases it is due to the fact that JVM may reorder statements at will (for performance reasons), and it might reorder these statements in such a way that worker threads are launched before sudoku board was constructed.

Here is a very nice article about immutable objects.

Question 6

Abstract

For a thread to be guaranteed to observe the effects of a write to main memory, the write must happen-before the read. If write and read occur in different threads, that requires a synchronization action. The spec defines many different kinds of synchronization actions. One such action is executing a synchronized statement, but alternatives exist.

Details

The Java Language Specification writes:

Two actions can be ordered by a happens-before relationship. If one action happens-before another, then the first is visible to and ordered before the second.

and

More specifically, if two actions share a happens-before relationship, they do not necessarily have to appear to have happened in that order to any code with which they do not share a happens-before relationship. Writes in one thread that are in a data race with reads in another thread may, for example, appear to occur out of order to those reads.

In your case, you want the reading threads to solve the right sudoku. That is, the initialization of the sudoku object must be visible to the reading threads, and therefore the initialization must happen-before the reading threads read from the sudoku.

The spec defines happens-before as follows:

If we have two actions x and y, we write hb(x, y) to indicate that x happens-before y.

If x and y are actions of the same thread and x comes before y in program order, then hb(x, y).

There is a happens-before edge from the end of a constructor of an object to the start of a finalizer (§12.6) for that object.

If an action x synchronizes-with a following action y, then we also have hb(x, y).

If hb(x, y) and hb(y, z), then hb(x, z).

Since reading occurs in a different thread than writing (and not in a finalizer), we therefore need a synchronization action to establish that the write happens-before the read. The spec gives the following exhaustive list of synchronization actions:

An unlock action on monitor m synchronizes-with all subsequent lock actions on m (where "subsequent" is defined according to the synchronization order).

A write to a volatile variable v (§8.3.1.4) synchronizes-with all subsequent reads of v by any thread (where "subsequent" is defined according to the synchronization order).

An action that starts a thread synchronizes-with the first action in the thread it starts.

The write of the default value (zero, false, or null) to each variable synchronizes-with the first action in every thread. (Although it may seem a little strange to write a default value to a variable before the object containing the variable is allocated, conceptually every object is created at the start of the program with its default initialized values.)

The final action in a thread T1 synchronizes-with any action in another thread T2 that detects that T1 has terminated (T2 may accomplish this by calling T1.isAlive() or T1.join())

If thread T1 interrupts thread T2, the interrupt by T1 synchronizes-with any point where any other thread (including T2) determines that T2 has been interrupted (by having an InterruptedException thrown or by invoking Thread.interrupted or Thread.isInterrupted).

You can choose any of these methods to establish happens-before. In practice, starting the reading threads after the sudoku has been fully constructed is probably the easiest way.

Question 7

From my point of view, locking is necessary if you write and this writing takes a long time to complete due to say network latency or massive processing overhead. Otherwise it's pretty safe to leave the locking out.