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

Looking for a better data engineering position and skills?

You have been working as a data engineer but feel stuck? You don't have any new challenges and are still writing the same jobs all over again? You have now different options. You can try to look for a new job, now or later, or learn from the others! "Become a Better Data Engineer" initiative is one of these places where you can find online learning resources where the theory meets the practice. They will help you prepare maybe for the next job, or at least, improve your current skillset without looking for something else.

👉 I'm interested in improving my data engineering skillset

See you there, Bartosz

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:

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.

Thread starvation

In multithreading compution the problem called thread starvation occurs when 1 or more threads can't get access to resources and remain blocked. It can have place for example: when thread with higher priority consumes all resources, exclusively one thread is working on synchronized block not allowing other threads to do the same.

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.

Green threads

Threads can be managed in different manners - either by kernel (OS) or by user space. Green threads (the name comes from the Sun's team working on threading feature, called Green Team) are threads manager by applications, son at user level. In the case of Java, they were managed by the JVM and not, as it's done in more recent versions, by OS. Java used Green Threads up to 1.3 release.

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.