Deeply understand the Java timed scheduling (Timer) mechanism

Introduction

When implementing the timing scheduling function, we often use third-party class libraries to complete it, such as: quartz, Spring Schedule, etc. Since version 1.3, JDK provides timer-based schedule function. In Timer, the execution of tasks is serial. While ensuring thread safety, this feature often brings some serious side effects, such as mutual influence between tasks and inefficient task execution. To solve these problems of Timer, JDK has provided scheduled scheduling functions based on ScheduledExecutorService starting from version 1.5.

In this section we mainly analyze the functions of Timer. Regarding the functions of ScheduledExecutorService, we will open a new article to explain it.

How to use

Timer needs to be used in conjunction with TimerTask to complete the scheduling function. Timer represents the scheduler, and TimerTask represents the task executed by the scheduler. There are two types of task scheduling: one-time scheduling and loop scheduling. Below, we use some examples to understand how they are used.

1. One-time schedule

public static void main(String[] args) {
  Timer timer = new Timer();
  TimerTask task = new TimerTask() {
    @Override public void run() {
      SimpleDateFormat format = new SimpleDateFormat("HH:mm:ss");
      ((scheduledExecutionTime()) + ", called");
    }
  };
  // Delay for one second, print once  // Printing results are as follows: 10:58:24, called  (task, 1000);
}

2. Loop Schedule - schedule()

public static void main(String[] args) {
  Timer timer = new Timer();
  TimerTask task = new TimerTask() {
    @Override public void run() {
      SimpleDateFormat format = new SimpleDateFormat("HH:mm:ss");
      ((scheduledExecutionTime()) + ", called");
    }
  };
  // Fixed time scheduling method, delayed by one second, and then printed once every second  // The printing results are as follows:  // 11:03:55, called
  // 11:03:56, called
  // 11:03:57, called
  // 11:03:58, called
  // 11:03:59, called
  // ...
  (task, 1000, 1000);
}

3. Loop Schedule - scheduleAtFixedRate()

public static void main(String[] args) {
  Timer timer = new Timer();
  TimerTask task = new TimerTask() {
    @Override public void run() {
      SimpleDateFormat format = new SimpleDateFormat("HH:mm:ss");
      ((scheduledExecutionTime()) + ", called");
    }
  };
  // Fixed-rate scheduling method, delayed by one second, and then printed once every second  // The printing results are as follows:  // 11:08:43, called
  // 11:08:44, called
  // 11:08:45, called
  // 11:08:46, called
  // 11:08:47, called
  // ...
  (task, 1000, 1000);
}

4. The difference between schedule() and scheduleAtFixedRate()

Judging from the results of 2 and 3, the results they achieved seem to be the same. Since the effects are the same, why should JDK be implemented in two methods? They should have something different!

Under normal circumstances, their effects are exactly the same. In exceptional cases - the task execution time is longer than the interval, and their effects are different.

schedule() method, the next execution time of the task is relative to the time when the last actual execution is completed, so the execution time will be continuously delayed
scheduleAtFixedRate() method, the next execution time of the task is relative to the last time when the execution was started, so the execution time will not be delayed
Since Timer is implemented internally through a single-threaded method, neither of these methods has thread safety problems

Let's first look at the exception effect of schedule():

public static void main(String[] args) {
  Timer timer = new Timer();
  TimerTask task = new TimerTask() {
    @Override public void run() {
      SimpleDateFormat format = new SimpleDateFormat("HH:mm:ss");
      try {
        (3000);
      } catch (InterruptedException e) {
        ();
      }
      ((scheduledExecutionTime()) + ", called");
    }
  };

  (task, 1000, 2000);
  // The execution results are as follows:  // 11:18:56, called
  // 11:18:59, called
  // 11:19:02, called
  // 11:19:05, called
  // 11:19:08, called
  // 11:19:11, called
}

Next, let's take a look at the exception effect of scheduleAtFixedRate():

public static void main(String[] args) {
  Timer timer = new Timer();
  TimerTask task = new TimerTask() {
    @Override public void run() {
      SimpleDateFormat format = new SimpleDateFormat("HH:mm:ss");
      try {
        (3000);
      } catch (InterruptedException e) {
        ();
      }
      ((scheduledExecutionTime()) + ", called");
    }
  };

  (task, 1000, 2000);
  // The execution results are as follows:  // 11:20:45, called
  // 11:20:47, called
  // 11:20:49, called
  // 11:20:51, called
  // 11:20:53, called
  // 11:20:55, called
}

The author has always believed that practice is a better way to test the truth. The above example indirectly verifies our initial conjecture.

However, here comes another problem. Since Timer is implemented in a single thread, how does scheduleAtFixedRate output once every 2 seconds when the execution interval is 2 seconds and the task actually executes 3 seconds?

【Special attention】

This is actually a trick. It should be noted that the output value of the print method is generated by calling scheduledExecutionTime() , and this method does not necessarily mean the actual execution time of the task, but the time when the current task should be executed.

Source code reading

The author’s understanding of knowledge is that in addition to knowing the truth, he also needs to know the reason. Reading the source code is a powerful key to open the door to know why. In JDK, Timer is mainly composed of TimerTask, TaskQueue and TimerThread.

1. TimerTask

TimerTask represents the task executed by the task scheduler, inherits from Runnable, and maintains the status of the task internally. There are 4 states in total.

VIRGIN, English name is Virgin, means that the task has not been dispatched yet
SCHEDULED, has been scheduled, but has not been executed yet
EXECUTED, for tasks that have been executed once, it means that they have been executed; for tasks that have been executed repeatedly, this status is invalid.
CANCELLED, task cancelled

TimerTask also has the following member variables

nextExecutionTime, next execution time
period, the time interval for task execution. Positive numbers represent fixed rate; negative numbers represent fixed delay; 0 means only execution once

After analyzing the general functions, let’s take a look at its code.

/**
 * The state of this task, chosen from the constants below.
 */
int state = VIRGIN;

/**
 * This task has not yet been scheduled.
 */
static final int VIRGIN = 0;

/**
 * This task is scheduled for execution. If it is a non-repeating task,
 * it has not yet been executed.
 */
static final int SCHEDULED  = 1;

/**
 * This non-repeating task has already executed (or is currently
 * executing) and has not been cancelled.
 */
static final int EXECUTED  = 2;

/**
 * This task has been cancelled (with a call to ).
 */
static final int CANCELLED  = 3;

TimerTask has two operation methods

cancel() // Cancel the task
scheduledExecutionTime() // Get the task execution time

cancel() is relatively simple, mainly locking the current task and then changing the status to cancelled.

public boolean cancel() {
  synchronized(lock) {
    boolean result = (state == SCHEDULED);
    state = CANCELLED;
    return result;
  }
}

In scheduledExecutionTime(), the task execution time is calculated by subtracting the interval time from the next execution time.

public long scheduledExecutionTime() {
  synchronized(lock) {
    return (period < 0 ? nextExecutionTime + period
              : nextExecutionTime - period);
  }
}

2. TaskQueue

TaskQueue is a queue used to store tasks in Timer. It is implemented internally using the [minimum heap algorithm], and the task at the top of the heap will be executed first. Since the use of [Minimum Heap], it is extremely efficient to determine whether the execution time has reached. Let's see how it is implemented internally.

class TaskQueue {
  /**
    * Priority queue represented as a balanced binary heap: the two children
    * of queue[n] are queue[2*n] and queue[2*n+1]. The priority queue is
    * ordered on the nextExecutionTime field: The TimerTask with the lowest
    * nextExecutionTime is in queue[1] (assuming the queue is nonempty). For
    * each node n in the heap, and each descendant of n, d,
    * <= .
    *
    * Use arrays to store tasks
    */
  private TimerTask[] queue = new TimerTask[128];

  /**
    * The number of tasks in the priority queue. (The tasks are stored in
    * queue[1] up to queue[size]).
    *
    * Used to represent the number of tasks in the queue. It should be noted that the number of tasks does not equal the length of the array
    */
  private int size = 0;

  /**
   * Returns the number of tasks currently on the queue.
   */
  int size() {
    return size;
  }

  /**
    * Adds a new task to the priority queue.
    *
    * Add a task to the queue
    */
  void add(TimerTask task) {
    // Grow backing store if necessary
    // If the number of tasks exceeds the length of the array, dynamic expansion will be performed by copying the array    if (size + 1 == )
      queue = (queue, 2*);

    // Put the current task item into the queue    queue[++size] = task;
    // Adjust upwards to re-form a minimum heap    fixUp(size);
  }

  /**
    * Return the "head task" of the priority queue. (The head task is an
    * task with the lowest nextExecutionTime.)
    *
    * The first element of the queue is the first task to execute
    */
  TimerTask getMin() {
    return queue[1];
  }

  /**
    * Return the ith task in the priority queue, where i ranges from 1 (the
    * head task, which is returned by getMin) to the number of tasks on the
    * queue, inclusive.
    *
    * Get the element of the specified subscript for the queue
    */
  TimerTask get(int i) {
    return queue[i];
  }

  /**
    * Remove the head task from the priority queue.
    *
    * Remove the top element of the heap. After removal, you need to adjust downwards to re-form the minimum heap.
    */
  void removeMin() {
    queue[1] = queue[size];
    queue[size--] = null; // Drop extra reference to prevent memory leak
    fixDown(1);
  }

  /**
    * Removes the ith element from queue without regard for maintaining
    * the heap invariant. Recall that queue is one-based, so
    * 1 <= i <= size.
    *
    * Quickly remove the specified position element and will not re-adjust the heap
    */
  void quickRemove(int i) {
    assert i &lt;= size;

    queue[i] = queue[size];
    queue[size--] = null; // Drop extra ref to prevent memory leak
  }

  /**
    * Sets the nextExecutionTime associated with the head task to the
    * specified value, and adjusts priority queue accordingly.
    *
    * Reschedule, adjust downward to re-form the minimum heap
    */
  void rescheduleMin(long newTime) {
    queue[1].nextExecutionTime = newTime;
    fixDown(1);
  }

  /**
    * Returns true if the priority queue contains no elements.
    *
    * Is the queue empty?
    */
  boolean isEmpty() {
    return size==0;
  }

  /**
    * Removes all elements from the priority queue.
    *
    * Clear all elements in the queue
    */
  void clear() {
    // Null out task references to prevent memory leak
    for (int i=1; i&lt;=size; i++)
      queue[i] = null;

    size = 0;
  }

  /**
    * Establishes the heap invariant (described above) assuming the heap
    * satisfied the invariant except possible for the leaf-node indexed by k
    * (which may have a nextExecutionTime less than its parent's).
    *
    * This method functions by "promoting" queue[k] up the hierarchy
    * (by swapping it with its parent) repeatedly until queue[k]'s
    * nextExecutionTime is greater than or equal to that of its parent.
    *
    * Adjust upwards to re-form the minimum stack
    */
  private void fixUp(int k) {
    while (k &gt; 1) {
      int j = k &gt;&gt; 1;
      if (queue[j].nextExecutionTime &lt;= queue[k].nextExecutionTime)
        break;
      TimerTask tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp;
      k = j;
    }
  }

  /**
    * Establishes the heap invariant (described above) in the subtree
    * rooted at k, which is assumed to satisfy the heap invariant except
    * possible for node k itself (which may have a nextExecutionTime greater
    * than its children's).
    *
    * This method functions by "demoting" queue[k] down the hierarchy
    * (by swapping it with its smaller child) repeatedly until queue[k]'s
    * nextExecutionTime is less than or equal to those of its children.
    *
    * Adjust downwards to re-form the minimum heap
    */
  private void fixDown(int k) {
    int j;
    while ((j = k &lt;&lt; 1) &lt;= size &amp;&amp; j &gt; 0) {
      if (j &lt; size &amp;&amp;
        queue[j].nextExecutionTime &gt; queue[j+1].nextExecutionTime)
        j++; // j indexes smallest kid
      if (queue[k].nextExecutionTime &lt;= queue[j].nextExecutionTime)
        break;
      TimerTask tmp = queue[j]; queue[j] = queue[k]; queue[k] = tmp;
      k = j;
    }
  }

  /**
   * Establishes the heap invariant (described above) in the entire tree,
   * assuming nothing about the order of the elements prior to the call.
   */
  void heapify() {
    for (int i = size/2; i &gt;= 1; i--)
      fixDown(i);
  }
}

3. TimerThread

TimerThread acts as a member variable of Timer and acts as the scheduler's calibration color. Let’s first look at its construction method, which mainly serves to hold a task queue.

TimerThread(TaskQueue queue) {
   = queue;
}

Next, let’s take a look at the run() method, which is the entry for thread execution.

public void run() {
  try {
    mainLoop();
  } finally {
    // Someone killed this Thread, behave as if Timer cancelled
    synchronized(queue) {
      newTasksMayBeScheduled = false;
      (); // Eliminate obsolete references
    }
  }
}

The main logic is all in the mainLoop() method. After the mainLoop method is executed, the resource cleaning operation will be performed. Let's take a look at the mainLoop() method.

private void mainLoop() {
  // while dead loop  while (true) {
    try {
      TimerTask task;
      boolean taskFired;
      // Lock the queue to ensure that all tasks in a queue are executed serially      synchronized(queue) {
        // Wait for queue to become non-empty
        // Operation 1, the queue is empty, you need to wait for the new task to be scheduled, and then wait operation is performed.        while (() &amp;&amp; newTasksMayBeScheduled)
          ();
        // Here we judge whether the queue is empty again because [Operation 1] a task came in, and the task was cancelled (the `cancel` operation was performed).        // If the queue is empty again, then you need to exit the thread to avoid the loop being stuck        if (())
          break; // Queue is empty and will forever remain; die

        // Queue nonempty; look at first evt and do the right thing
        long currentTime, executionTime;
        // Take out the top heap element in the queue (the task with the smallest execution time next time)        task = ();
        // Locking the heap elements here is to ensure the visibility and atomicity of the task        synchronized() {
          // Cancelled tasks will no longer be executed and need to be removed from the queue          if ( == ) {
            ();
            continue; // No action required, poll queue again
          }
          // Get the current time of the system and the next time the task is executed          currentTime = ();
          executionTime = ;

          // The next time the task is executed <= the current time of the system, then execute this task (set the status flag `taskFired` to true)          if (taskFired = (executionTime&lt;=currentTime)) {
            // `peroid` is 0, which means that this task only needs to be executed once            if ( == 0) { // Non-repeating, remove
              ();
               = ;
            }
            // period is not 0, which means that this task needs to be executed repeatedly            // Here we reflect the difference between the `schedule()` method and `scheduleAtFixedRate()`            else { // Repeating task, reschedule
              (
               &lt;0 ? currentTime  - 
                      : executionTime + );
            }
          }
        }
        // The task is not triggered, the queue is suspended (with timeout time)        if (!taskFired) // Task hasn't yet fired; wait
          (executionTime - currentTime);
      }
      // The task is triggered to execute the task.  After execution, enter the next cycle      if (taskFired) // Task fired; run it, holding no locks
        ();
    } catch(InterruptedException e) {
    }
  }
}

4. Timer

Timer does the following through the constructor:

Fill in the various properties of the TimerThread object (such as thread name, whether to guard the thread)
Start the thread

/**
 * The timer thread.
 */
private final TimerThread thread = new TimerThread(queue);

public Timer(String name, boolean isDaemon) {
  (name);
  (isDaemon);
  ();
}

In Timer, there are only two schedule methods that are truly exposed to users, schedule() and scheduleAtFixedRate() , let's take a look.

public void schedule(TimerTask task, long delay) {
  if (delay < 0)
    throw new IllegalArgumentException("Negative delay.");
  sched(task, ()+delay, 0);
}

public void schedule(TimerTask task, Date time) {
  sched(task, (), 0);
}

public void schedule(TimerTask task, long delay, long period) {
  if (delay < 0)
    throw new IllegalArgumentException("Negative delay.");
  if (period <= 0)
    throw new IllegalArgumentException("Non-positive period.");
  sched(task, ()+delay, -period);
}

public void schedule(TimerTask task, Date firstTime, long period) {
  if (period <= 0)
    throw new IllegalArgumentException("Non-positive period.");
  sched(task, (), -period);
}

public void scheduleAtFixedRate(TimerTask task, long delay, long period) {
  if (delay < 0)
    throw new IllegalArgumentException("Negative delay.");
  if (period <= 0)
    throw new IllegalArgumentException("Non-positive period.");
  sched(task, ()+delay, period);
}

public void scheduleAtFixedRate(TimerTask task, Date firstTime,
                long period) {
  if (period <= 0)
    throw new IllegalArgumentException("Non-positive period.");
  sched(task, (), period);
}

From the above code we see the following points.

Both methods end up calling the sched() private method
schedule() passes in a negative period, scheduleAtFixedRate() passes in a positive period

Next, let's take a look at the sched() method.

private void sched(TimerTask task, long time, long period) {
  // 1. `time` cannot be a check for negative numbers  if (time &lt; 0)
    throw new IllegalArgumentException("Illegal execution time.");

  // Constrain value of period sufficiently to prevent numeric
  // overflow while still being effectively infinitely large.
  // 2. `period` cannot exceed `Long.MAX_VALUE >> 1`  if ((period) &gt; (Long.MAX_VALUE &gt;&gt; 1))
    period &gt;&gt;= 1;

  synchronized(queue) {
    // 3. When Timer is cancelled, it cannot be scheduled    if (!)
      throw new IllegalStateException("Timer already cancelled.");

    // 4. Lock the task, and then set the next execution time, execution cycle and task status of the task to ensure that task scheduling and task cancellation are thread-safe    synchronized() {
      if ( != )
        throw new IllegalStateException(
          "Task already scheduled or cancelled");
       = time;
       = period;
       = ;
    }
    // 5. Add tasks to queue    (task);
    // 6. If the heap top element in the queue is the current task, wake up the queue and let `TimerThread` perform task scheduling    if (() == task)
      ();
  }
}

The sched() method goes through the following steps:

time cannot be a check for negative numbers
period cannot exceed Long.MAX_VALUE >> 1
When Timer is cancelled, it cannot be scheduled
Lock the task, and then set the next execution time, execution cycle and task status of the task to ensure that task scheduling and task cancellation are thread-safe.
Add tasks to queue
If the heap top element in the queue is the current task, wake up the queue so that TimerThread can perform task scheduling

[Note]: We need to pay special attention to point 6. Why does the heap top element wake up the queue only when it is the current task? The reason is the meaning represented by the heap top element, that is, the heap top element represents the task to be executed closest to the current time!

[Example 1]: If the current time is 1 second, there is a task A in the queue that needs to be executed in 3 seconds, and the newly added task B needs to be executed in 5 seconds. At this time, because TimerThread has wait(timeout) operation, it will wake up by itself when the time comes. Therefore, for performance considerations, there is no need to wake up during the sched() operation.

[Example 2]: If the current time is 1 second, there is a task A in the queue that needs to be executed in 3 seconds, and the newly added task B needs to be executed in 2 seconds. At this time, if the wake-up operation is not performed in sched(), task A will be executed in 3 seconds. Since task B needs to be executed in 2 seconds, the time it should be executed has passed, which causes problems.

Task scheduling method sched() After analysis, we continue to analyze other methods. Let’s first look at cancel() , which is used to cancel the execution of Timer.

public void cancel() {
  synchronized(queue) {
     = false;
    ();
    (); // In case queue was already empty.
  }
}

Judging from the above source code analysis, this method does the following:

Set the newTasksMayBeScheduled mark to false for TimerThread
Clear the queue
Wake up queue

Sometimes, there may be multiple TimerTasks in one Timer. If we just cancel a few of the TimerTasks, not all of them, we also need to clean the Timer in addition to executing the cancel() method call to the TimerTask. The cleaning method here is purge() . Let's take a look at its implementation logic.

public int purge() {
   int result = 0;

   synchronized(queue) {
     // 1. Iterate through all tasks. If the task is canceled, remove it from the queue. Remove the number and add one operation     for (int i = (); i &gt; 0; i--) {
       if ((i).state == ) {
         (i);
         result++;
       }
     }
     // 2. Reform the queue into the minimum heap     if (result != 0)
       ();
   }

   return result;
 }

5. Waiting for queue

Through the analysis of the previous source code, we see that the wake-up of the queue exists in the following places:

()
()
()

The first and second points have actually been analyzed, let’s take a look at the third point.

private final Object threadReaper = new Object() {
  protected void finalize() throws Throwable {
    synchronized(queue) {
       = false;
      (); // In case queue is empty.
    }
  }
};

This method is used to wake up the task queue in the GC phase, which is often forgotten by readers.

So, let's look back and think about why this code is needed?

When we analyze TimerThread, we see that if the Timer is not scheduled after it is created, it will keep waiting, thus falling into a fake death state. To avoid this, concurrency master Doug Lea witfully thought of setting the status tag newTasksMayBeScheduled in finalize() and performing a wake-up operation on the task queue (()) to rescue TimerThread from the dead loop.

Summarize

First, this article demonstrates how Timer is used, and then analyzes the differences and connections between the scheduling methods schedule() and scheduleAtFixedRate().

Then, in order to deepen our understanding of Timer, we conducted in-depth analysis by reading the source code. It can be seen that its internal implementation is very clever and well-considered.

However, because of the characteristics of Timer serial execution, its application under high concurrency is limited. Later, we will analyze in-depth how task scheduling is implemented in high concurrency and distributed environments. Let's wait and see~

The above is all the content of this article. I hope it will be helpful to everyone's study and I hope everyone will support me more.