4

Lets we have following code(we will run it on single core CPU):

Runnable runnable1 = new Runnable() {
    @Override
    public void run() {
        System.out.println("runnable_1_1");
        System.out.println("runnable_1_2");
    }
};
Runnable runnable2 = new Runnable() {
    @Override
    public void run() {
        System.out.println("runnable_2_1");
        System.out.println("runnable_2_2");
    }
};
ExecutorService executorService = Executors.newSingleThreadExecutor(); // or Executors.newCachedThreadExecutor();
executorService.execute(runnable1);
executorService.execute(runnable2);
executorService.shutdown();

Is it theoretically possible that one task will be wedged to another and we will see output like this:

runnable_1_1
runnable_2_1
runnable_2_2
runnable_1_2

P.S.

Single thread executor is not mandatory for this example. Mandatory that we have only one CPU core

gstackoverflow
  • 36,709
  • 117
  • 359
  • 710

3 Answers3

4

This cannot be cleanly done on Java level for an arbitrary thread, as there are no non-deprecated methods to suspend it. All valid methods of control include the thread actively yielding.

However operating system itself normally has a scheduler that periodically suspends and resumes all running processes, allowing to have much more of them than the number of CPU cores available. Also, Java virtual machine normally does not run just as a single process (green threads belong to the past), there is one process per thread.

As a result, the operating system may suspend one thread for a short time, allowing to run another thread, or some other process outside Java virtual machine. The general answer is likely yes.

Community
  • 1
  • 1
Audrius Meškauskas
  • 20,936
  • 12
  • 75
  • 93
2

The number of CPUs doesn't matter when you're trying to reason about code on this level. In theory you could run the JVM on an OS that forces a context switch after every single program instruction. It would be mad and no OS does that, but how would you know just by looking at the Java code?

If it's a single thread executor, the answer is there will be no overlapping, and if it isn't a single thread executor, you can't prove there will be no overlapping.

To find the reason, we need to look at Chapter 17 of the JLS:

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.

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

The wait methods of class Object (§17.2.1) have lock and unlock actions associated with them; their happens-before relationships are defined by these associated actions.

It should be noted that the presence of a happens-before relationship between two actions does not necessarily imply that they have to take place in that order in an implementation. If the reordering produces results consistent with a legal execution, it is not illegal.

In the single thread executor case this is exactly what we get: the two runnables are actions of the same thread and one will be ahead of the other in program order. And though the last paragraph would allow reordering, reordering can't lead to visible differences in correctly synchronised code.

With multiple threads it's anybody's guess. There are only two things that are guaranteed:

  1. The first message from a thread will be printed before the second. (See above)
  2. And each line of the output will contain a full message from one of the threads, i.e. you'll never see a line of jumbled output. This is simply because PrintStream.println() is synchronised.

So that's the theory.

In practice, with most JVM implementations and operating systems, you'll probably never see an overlap with this exact code for the simple reason that the tasks you execute would take too little time to be interrupted. Make them run for minutes or hours though and you'll definitely see context switching between the two.

biziclop
  • 48,926
  • 12
  • 77
  • 104
1

[[ @biziclop's answer is right albeit long and confusing. ]]

Is it theoretically possible that one task will be wedged to another and we will see output like this:

Not in the code that you posted. You are submitting 2 jobs to a single threaded executor:

ExecutorService executorService = Executors.newSingleThreadExecutor();

This means that only 1 thread will be executing your 2 Runnables. When that 1st thread blocks the other Runnable is not executing so the output won't interleave. The 1st Runnable will need to complete before the 2nd Runnable is executed.

If you use the Executors.newCachedThreadExecutor();, then the 2 Runnables can be run concurrently and their output could interleave. In that case, the first Runnable might print out runnable_1_1 and then be time sliced so the the other thread can execute and display it's runnable_2_1, etc.. This is a race condition however and may be unlikely, but it's possible.

Single thread executor is not mandatory for this example. Mandatory that we have only one CPU core

As @biziclop mentions, the number of CPUs on your hardware does not matter. What matters is how many threads are in the run queue at any one point in time.

Gray
  • 115,027
  • 24
  • 293
  • 354