OS Thread Scheduler and Java Thread

Most of time threads manipulation is limited to programming language. Even if this high abstraction is sufficient, it's also good to know what happens under-the-hood when a new thread is created in any programming language (Java in the case of this post).

This post contains a lot of definitions. Its first part focuses on general computer science definitions. The second part concerns Java and explains how Threads interact with OS threads. The last part shows some exploited concepts (priorities, yielding) through test cases.

Thread scheduler

Before going into details, let's define a thread. Officially it's a subdivision of a process (i.e. of the separate unit of execution in OS) that can be executed in parallel with other subdivisions. Thanks to it CPUs are able to execute different programs at the same time.

Threads aren't executed without any logic. They're manipulated by a thread scheduler that decides which thread is launched at given moment. The decision is made on several factors, depending on used method. To stay simple we can assume the existence of 2 scheduling strategies:

• non-preemptive scheduling: running task is executed till completion, as for example in the case of FIFO queue.
• preemptive scheduling: this strategy is more flexible than the previous one. It's because currently executed task can be interrupted and replaced by other task being until now in idle state. The interruption has place with the intention to resume stopped task later.

Preemptive scheduler brings some other interesting concepts. The first one is context switch. It corresponds to the situation when scheduler stops executed task and triggers the execution of another task. In this process scheduler consists on saving the state of interrupted process and loading the state of launched process. Context switch has an impact on execution time because it needs some time to make context operations on memory (saving stopped context, loading new one).

In general threads have assigned an execution priority that suggests CPU to launch some of them prior to others. It should mean that threads with low priority can be never executed, shouldn't it ? Yes, but scheduler has a protection against this behavior called thread starvation . The protection is called time slicing and is the 2nd interesting concept brought by preemptive scheduler. CPU gives some amount of execution time for each task (about 10-100 milliseconds) called time slice (aka quantum). If the task doesn't execute within this time, it's moved to the end of a queue with waiting tasks. It's replaced by the first task from the queue. So each replacement causes a context switch - if there are too many switches, it can really slow down the performances. In the other side, putting time slice too big would transform this round robin scheduling to FIFO queue.

Java Threads

How do Java Threads rely on previously described concepts ? In fact, most of JVMs use OS thread scheduler to manage constructed threads. By the past it was not true because of green threads .

Thus, threads in Java are executed as OS native threads. Each time when a new Thread instance is created, new OS thread is launched and is reclaimed when it terminates. Under-the-hood it's OS thread scheduler which manages Java Threads and dispatches them to available CPU.

Java Threads also have priority that almost match cleanly to OS threads priority. It's "almost" because Java offers only 10 priority levels (0-10, possibility to use constant priorities: MIN_PRIORITY [1], NORM_PRIORITY [5] and MAX_PRIORITY [10]) and a lot of OS have more than that. Normally Thread with higher priority will run in preference to lower priority. But it's not a gold rule because sometimes Thread with lower priority can be executed and with higher priority suspended. It can occur for example when Thread with high priority is making some blocking operation (such as I/O one). In such case, resources it held can be temporary granted to Thread with lower priority.

Working with Threads isn't cost free. Every time when a Thread is started and stopped, some CPU resources are used. A solution for that are thread pools - sets of long-living Threads. They're detailed in the post about Thread pools in Java concurrency.

Another Threads feature is yielding. It's a way to release used processor by Thread instance. It's executed through yield() instance method. But it's important to emphasize that it's only a hint to the thread scheduler that can ignore this information. Even if this method is available publicly in Thread API, its use is not encouraged:

// From Javadoc 
It is rarely appropriate to use this method. It may be useful 
for debugging or testing purposes, where it may help to reproduce
bugs due to race conditions. It may also be useful when designing
concurrency control constructs such as the ones in the
{@link java.util.concurrent.locks} package.

Scheduled threads examples

Below tests show some of concepts detailed previously (thread starvation protection, hint character of priority):

@Test
public void should_execute_all_threads_even_with_low_priority() throws InterruptedException {
  List<String> executedThreads = new ArrayList<>();
  // I have 8 CPUs, so I'll create 10 Threads
  // 8 with high priority, 2 with low priority
  for (int i = 1; i < 9; i++) {
    Thread thread = new Thread(new LongRunningTask(executedThreads));
    thread.setPriority(Thread.MAX_PRIORITY);
    thread.setName("HIGH_"+i);
    thread.start();
  }
  for (int i = 1; i < 3; i++) {
    Thread thread = new Thread(new LongRunningTask(executedThreads));
    thread.setPriority(Thread.MIN_PRIORITY);
    thread.setName("LOW_"+i);
    thread.start();
  }
  System.out.println("Stopping threads for 10 seconds");
  Thread.sleep(10_000L);

  assertThat(executedThreads).hasSize(10);
  assertThat(executedThreads).contains("HIGH_1", "HIGH_2", "HIGH_3", "HIGH_4", "HIGH_5", "HIGH_6",
    "HIGH_7", "HIGH_8", "LOW_1", "LOW_2");
}

private static class LongRunningTask implements Runnable { 
  private List<String> taskContainer;

  private LongRunningTask(List<String> taskContainer) {
    this.taskContainer = taskContainer;
  }

  @Override
  public void run() {
    taskContainer.add(Thread.currentThread().getName());
    while (true) {
    }
  }
}

@Test
public void should_measure_execution_time_of_threads() throws InterruptedException {
  Map<String, List<Long>> executions = new HashMap<>();
  List<Thread> threads = new ArrayList<>();
  for (int i = 1; i < 15; i++) {
    int priority = Thread.MAX_PRIORITY;
    if (i > 8) {
      priority = Thread.MIN_PRIORITY;
    }
    String threadName = "thread_"+i+"_"+priority;
    List<Long> executionTimes = 
      new CopyOnWriteArrayList<>();
    executions.put(threadName, executionTimes);
    Thread thread = 
      new Thread(new LongRunningTimedTask(executionTimes));
    thread.setPriority(priority);
    thread.setName(threadName);
    thread.start();
    threads.add(thread);
  }

  System.out.println("Sleeping during 10 seconds");
  Thread.sleep(10_000L);
  // Stop all threads
  threads.forEach(thread -> thread.interrupt());

  List<Pair<String, Long>> totalExecutionTimeByThread = 
    new ArrayList<>();
  for (Map.Entry<String, List<Long>> execution : executions.entrySet()) {
    Pair<String, Long> pair = of(execution.getKey(),
      execution.getValue().stream().reduce(0L, (time1, time2) -> time1 + time2));
    totalExecutionTimeByThread.add(pair);
  }
  Collections.sort(totalExecutionTimeByThread, 
    (pair1, pair2) -> pair2.getValue().compareTo(pair1.getRight()));

  assertThat(totalExecutionTimeByThread).hasSize(14);
  // Normally high priority doesn't guarantee more resources
  // than low Thread priority
  Map<Boolean, List<Pair<String, Long>>> groupedExecutions = totalExecutionTimeByThread.stream()
    .collect(partitioningBy(pair -> pair.getKey().endsWith("_" + Thread.MIN_PRIORITY)));
  List<Pair<String, Long>> minPriorityExecutions = groupedExecutions.get(true);
  List<Pair<String, Long>> maxPriorityExecutions = groupedExecutions.get(false);
  System.out.println("minPriorityExecutions= " + minPriorityExecutions);
  System.out.println("maxPriorityExecutions= " + maxPriorityExecutions);
  long theLongestMinPriority = minPriorityExecutions.get(0).getRight();
  long highPriorityWorseThanTheLongestLower = maxPriorityExecutions.stream()
    .filter(highPriority -> theLongestMinPriority > highPriority.getRight()).count();
  System.out.println("The number of Threads with high priority executed shorter than the longest low priority " +
    " Thread: "+ highPriorityWorseThanTheLongestLower);
  assertThat(highPriorityWorseThanTheLongestLower).isGreaterThan(0);
}

private static class LongRunningTimedTask implements Runnable {

  private List<Long> executionTime;

  private LongRunningTimedTask(List<Long> executionTime) {
    this.executionTime = executionTime;
  }

  @Override
  public void run() {
    while (true) {
      long start = System.nanoTime();
      long stop = System.nanoTime();
      executionTime.add(stop-start);
      System.out.println("Executing "+Thread.currentThread().getName());
    }
  }
}

@Test
public void should_fail_on_setting_too_high_priority() {
  Thread thread = new Thread(() -> {});

  assertThatExceptionOfType(IllegalArgumentException.class)
    .isThrownBy(() -> thread.setPriority(Thread.MAX_PRIORITY+1));
}

This post tries to explain what happens when a Thread instance is created and started. The first part shows the main components used to execute threads in OS (thread scheduler) as well as related concepts (thread starvation, context switch). The second part describes how Thread execution is handled under-the-hood. The last part illustrates described points through learning tests and short video.