Prioritized Task Scheduling

1. Introduction

This section is non-normative.

Scheduling can be an important developer tool for improving website performance. Broadly speaking, there are two areas where scheduling can be impactful: user-percieved latency and responsiveness. Scheduling can improve user-perceived latency to the degree that lower priority work can be pushed off in favor of higher priority work that directly impacts quality of experience. For example, pushing off execution of certain 3P library scripts during page load can benefit the user by getting pixels to the screen faster. The same applies to prioritizing work associated with content within the viewport. For script running on the main thread, long tasks can negatively affect both input and visual responsiveness by blocking input and UI updates from running. Breaking up these tasks into smaller pieces and scheduling the chunks or task continuations is a proven approach that applications and framework developers use to improve responsiveness.

Userspace schedulers typically work by providing methods to schedule tasks and controlling when those tasks execute. Tasks usually have an associated priority, which in large part determines when the task will run, in relation to other tasks the scheduler controls. The scheduler typically operates by executing tasks for some amount of time (a scheduler quantum) before yielding control back to the browser. The scheduler resumes by scheduling a continuation task, e.g. a call to setTimeout() or postMessage().

While userspace schedulers have been successful, the situation could be improved with a centralized browser scheduler and better scheduling primitives. The priority system of a scheduler extends only as far as the scheduler’s reach. A consequence of this for userspace schedulers is that the UA generally has no knowledge of userspace task priorities. The one exception is if the scheduler uses requestIdleCallback() for some of its work, but this is limited to the lowest priority work. The same holds if there are multiple schedulers on the page, which is increasingly common. For example, an app might be built with a framework that has a schedueler (e.g. React), do some scheduling on its own, and even embed a feature that has a scheduler (e.g. an embedded map). The browser is the ideal coordination point since the browser has global information, and the event loop is responsible for running tasks.

Prioritization aside, the current primitives that userspace schedulers rely on are not ideal for modern use cases. setTimeout(0) is the canonical way to schedule a non-delayed task, but there are often minimum delay values (e.g. for nested tasks) which can lead to poor performance due to increased latency. A well-known workaround is to use postMessage() or a MessageChannel, but these APIs were not designed for scheduling, e.g. you cannot queue callbacks. requestIdleCallback() can be effective for some use cases, but this only applies to idle tasks and does not account for tasks whose priority can change, e.g. re-prioritizing off-screen content in response to user input, like scrolling.

This document introduces a new interface for developers to schedule and control prioritized tasks. The Scheduler interface exposes a postTask() method to schedule tasks, and the specification defines a number of TaskPriorities that control execution order. Additionally, a TaskController and its associated TaskSignal can be used to abort scheduled tasks and control their priorities.

2. Scheduling Tasks

2.1. Task Priorities

This spec formalizes three priorities to support scheduling tasks:

enum TaskPriority {
  "user-blocking",
  "user-visible",
  "background"
};

user-blocking is the highest priority, and is meant to be used for tasks that are blocking the user’s ability to interact with the page, such as rendering the core experience or responding to user input.

user-visible is the second highest priority, and is meant to be used for tasks that visible to the user but not necessarily blocking user actions, such as rendering secondary parts of the page. This is the default priority.

background is the lowest priority, and is meant to be used for tasks that are not time-critical, such as background log processing or initializing certain third party libraries.

Note: Tasks scheduled through a given Scheduler run in strict priority order, meaning the scheduler will always run "user-blocking" tasks before "user-visible" tasks, which in turn always run before "background" tasks.

TaskPriority p1 is less than TaskPriority p2 if p1 is less than p2 in the following total ordering: "background" < "user-visible" < "user-blocking"

2.2. The `Scheduler` Interface

dictionary SchedulerPostTaskOptions {
  AbortSignal signal;
  TaskPriority priority;
  [EnforceRange] unsigned long long delay = 0;
};

callback SchedulerPostTaskCallback = any ();

[Exposed=(Window, Worker)]
interface Scheduler {
  Promise<any> postTask(SchedulerPostTaskCallback callback,
                        optional SchedulerPostTaskOptions options = {});
};

Note: The signal option can be either an AbortSignal or a TaskSignal, but is defined as an AbortSignal since it is a superclass of TaskSignal. For cases where the priority might change, a TaskSignal is needed. But for cases where only cancellation is needed, an AbortSignal would suffice, potentially making it easier to integrate the API into existing code that uses AbortSignals.

result = scheduler . postTask( callback, options )

Returns a promise that is fulfilled with the return value of callback, or rejected with the AbortSignal's abort reason if the task is aborted. If callback throws an error during execution, the promise returned by postTask() will be rejected with that error.

The task’s priority is determined by the combination of option’s priority and signal:

If option’s priority is specified, then that TaskPriority will be used to schedule the task, and the task’s priority is immutable.
Otherwise, if option’s signal is specified and is a TaskSignal object, then the task’s priority is determined by option’s signal's priority. In this case the task’s priority is dynamic, and can be changed by calling controller.setPriority() for the associated TaskController.
Otherwise, the task’s priority defaults to "user-visible".

If option’s signal is specified, then the signal is used by the Scheduler to determine if the task is aborted.

If option’s delay is specified and greater than 0, then the execution of the task will be delayed for at least delay milliseconds.

A Scheduler object has an associated static priority task queue map, which is a map from TaskPriority to scheduler task queue. This map is initialized to a new empty map.

A Scheduler object has an associated dynamic priority task queue map, which is a map from TaskSignal to scheduler task queue. This map is initialized to a new empty map.

Note: We implement dynamic prioritization by enqueuing tasks associated with a specific TaskSignal into the same scheduler task queue, and changing that queue’s priority in response to prioritychange events. The dynamic priority task queue map holds the scheduler task queues whose priorities can change, and the map key is the TaskSignal which all tasks in the queue are associated with.

The values of the static priority task queue map are scheduler task queues whose priorities do not change. Tasks with static priorities — those that were scheduled with an explicit priority option or a signal option that is null or is an AbortSignal — are placed in these queues, based on TaskPriority, which is the key for the map.

An alternative, and logicially equivalent implementation, would be to maintain a single per-TaskPriority scheduler task queue, and move tasks between scheduler task queues in response to a TaskSignal's priority changing, inserting based on enqueue order. This approach would simplify selecting the task queue of the next scheduler task, but make priority changes more complex.

A Scheduler object has a numeric next enqueue order which is initialized to 1.

Note: The next enqueue order is a strictly increasing number that is used to determine task execution order across scheduler task queues of the same TaskPriority within the same Scheduler. A logically equivalent alternative would be to place the next enqueue order on the event loop, since the only requirements are that the number be strictly increasing and not be repeated within a Scheduler.

Would it be simpler to just use a timestamp here?

The postTask(callback, options) method steps are to return the result of scheduling a postTask task for this given callback and options.

2.3. Definitions

A scheduler task is a task with an additional numeric enqueue order item, initially set to 0.

The following task sources are defined as scheduler task sources, and must only be used for scheduler tasks.

The posted task task source: This task source is used for tasks scheduled through postTask().

A scheduler task queue is a struct with the following items:

priority: A TaskPriority.
tasks: A set of scheduler tasks.

2.4. Processing Model

A scheduler task t1 is older than scheduler task t2 if t1’s enqueue order less than t2’s enqueue order.

To create a scheduler task queue with TaskPriority priority:

Let queue be a new scheduler task queue.
Set queue’s priority to priority.
Set queue’s tasks to a new empty set.
Return queue.

A scheduler task queue queue’s first runnable task is the first scheduler task in queue’s tasks that is runnable.

2.4.1. Queueing and Removing Scheduler Tasks

To queue a scheduler task on a scheduler task queue queue, which performs a series of steps steps, given a numeric enqueue order, a task source source, and a document document:

Let task be a new scheduler task.
Set task’s enqueue order to enqueue order.
Set task’s steps to steps.
Set task’s source to source.
Set task’s document to document.
Set task’s script evaluation environment settings object set to a new empty set.
Append task to queue’s tasks.
Return task.

We should consider refactoring the HTML spec to add a constructor for task. One problem is we need the new task to be a scheduler task rather than a task.

To remove a scheduler task task from scheduler task queue queue, remove task from queue’s tasks.

2.4.2. Scheduling Tasks

To schedule a postTask task for Scheduler scheduler given a SchedulerPostTaskCallback callback and SchedulerPostTaskOptions options:

Let result be a new promise.
Let signal be options["signal"] if options["signal"] exists, or otherwise null.
If signal is not null and it is aborted, then reject result with signal’s abort reason and return result.
Let priority be options["priority"] if options["priority"] exists, or otherwise null.
Let queue be the result of selecting the scheduler task queue for scheduler given signal and priority.
Let delay be options["delay"].
If delay is greater than 0, then run steps after a timeout given scheduler’s relevant global object, "scheduler-postTask", delay, and the following steps:
1. Schedule a task to invoke a callback for scheduler given queue, signal, callback, and result.
Otherwise, schedule a task to invoke a callback for scheduler given queue, signal, callback, and result.
Return result.

Run steps after a timeout doesn’t necessarily account for suspension; see whatwg/html#5925.

To select the scheduler task queue for a Scheduler scheduler given an AbortSignal or null signal, and a TaskPriority or null priority:

If priority is null, signal is not null and implements the TaskSignal interface, and signal has fixed priority, then set priority to signal’s priority.
If priority is null and signal is not null and implements the TaskSignal interface, then
1. If scheduler’s dynamic priority task queue map does not contain signal, then
  1. Let queue be the result of creating a scheduler task queue given signal’s priority.
  2. Set dynamic priority task queue map[signal] to queue.
  3. Add a priority change algorithm to signal that runs the following steps:
    1. Set queue’s priority to signal’s priority.
2. Return dynamic priority task queue map[signal].
Otherwise priority is used to determine the task queue:
1. If priority is null, set priority to "user-visible".
2. If scheduler’s static priority task queue map does not contain priority, then
  1. Let queue be the result of creating a scheduler task queue given priority.
  2. Set static priority task queue map[priority] to queue.
3. Return static priority task queue map[priority].

To schedule a task to invoke a callback for Scheduler scheduler given a scheduler task queue queue, an AbortSignal or null signal, a SchedulerPostTaskCallback callback, and a promise result:

Let global be the relevant global object for scheduler.
Let document be global’s associated Document if global is a Window object; otherwise null.
Let enqueue order be scheduler’s next enqueue order.
Increment scheduler’s next enqueue order by 1.
Let task be the result of queuing a scheduler task on queue given enqueue order, the posted task task source, and document, and that performs the following steps:
1. Let callback result be the result of invoking callback. If that threw an exception, then reject result with that, otherwise resolve result with callback result.
If signal is not null, then add the following abort steps to it:
1. Remove task from queue.
2. Reject result with signal’s abort reason.

Because this algorithm can be called from in parallel steps, parts of this and other algorithms are racy. Specifically, the next enqueue order should be updated atomically, and accessing the scheduler task queues should occur atomically. The latter also affects the event loop task queues (see this issue).

2.4.3. Selecting the Next Task to Run

A Scheduler scheduler has a runnable task if the result of getting the runnable task queues for scheduler is non-empty.

To get the runnable task queues for a Scheduler scheduler:

Let queues be the result of getting the values of scheduler’s static priority task queue map.
Extend queues with the result of getting the values of scheduler’s dynamic priority task queue map.
Remove from queues any queue such that queue’s tasks do not contain a runnable scheduler task.
Return queues.

The result of selecting the task queue of the next scheduler task for Scheduler scheduler is a set of scheduler tasks as defined by the following steps:

Let queues be the result of getting the runnable task queues for scheduler.
If queues is empty return null.
Remove from queues any queue such that queue’s priority is less than any other item of queues.
Let queue be the scheduler task queue in queues whose first runnable task is the oldest.
Two tasks cannot have the same age since enqueue order is unique.
Return queue’s tasks.

Note: The next task to run is the oldest, highest priority runnable scheduler task.

2.5. Examples

TODO(shaseley): Add examples.

3. Controlling Tasks

Tasks scheduled through the Scheduler interface can be controlled with a TaskController by passing the TaskSignal provided by controller.signal as the option when calling postTask(). The TaskController interface supports aborting and changing the priority of a task or group of tasks.

3.1. The `TaskPriorityChangeEvent` Interface

[Exposed=(Window, Worker)]
interface TaskPriorityChangeEvent : Event {
  constructor(DOMString type, TaskPriorityChangeEventInit priorityChangeEventInitDict);

  readonly attribute TaskPriority previousPriority;
};

dictionary TaskPriorityChangeEventInit : EventInit {
  required TaskPriority previousPriority;
};

event . previousPriority

Returns the TaskPriority of the corresponding TaskSignal prior to this prioritychange event.

The new TaskPriority can be read with event.target.priority.

The previousPriority getter steps are to return the value that the corresponding attribute was initialized to.

3.2. The `TaskController` Interface

dictionary TaskControllerInit {
  TaskPriority priority = "user-visible";
};

[Exposed=(Window,Worker)]
interface TaskController : AbortController {
  constructor(optional TaskControllerInit init = {});

  undefined setPriority(TaskPriority priority);
};

Note: TaskController's signal getter, which is inherited from AbortController, returns a TaskSignal object.

controller = new TaskController( init ): Returns a new TaskController whose signal is set to a newly created TaskSignal with its priority initialized to init’s priority.
controller . setPriority( priority ): Invoking this method will change the associated TaskSignal's priority, signal the priority change to any observers, and cause prioritychange events to be dispatched.

The new TaskController(init) constructor steps are:

Let signal be a new TaskSignal object.
Set signal’s priority to init["priority"].
Set this’s signal to signal.

The setPriority(priority) method steps are to signal priority change on this's signal given priority.

3.3. The `TaskSignal` Interface

dictionary TaskSignalAnyInit {
  (TaskPriority or TaskSignal) priority = "user-visible";
};

[Exposed=(Window, Worker)]
interface TaskSignal : AbortSignal {
  [NewObject] static TaskSignal _any(sequence<AbortSignal> signals, optional TaskSignalAnyInit init = {});

  readonly attribute TaskPriority priority;

  attribute EventHandler onprioritychange;
};

Note: TaskSignal inherits from AbortSignal and can be used in APIs that accept an AbortSignal. Additionally, postTask() accepts an AbortSignal, which can be useful if dynamic prioritization is not needed.

TaskSignal . any(signals, init): Returns a TaskSignal instance which will be aborted if any of signals is aborted. Its abort reason will be set to whichever one of signals caused it to be aborted. The signal’s priority will be determined by init’s priority, which can either be a fixed TaskPriority or a TaskSignal, in which case the new signal’s priority will change along with this signal.
signal . priority: Returns the TaskPriority of the signal.

A TaskSignal object has an associated priority (a TaskPriority).

A TaskSignal object has an associated priority changing (a boolean), which is intially set to false.

A TaskSignal object has associated priority change algorithms, (a set of algorithms that are to be executed when its priority changing value is true), which is initially empty.

A TaskSignal object has an associated source signal (a weak refernece to a TaskSignal that the object is dependent on for its priority), which is initially null.

A TaskSignal object has associated dependent signals (a weak set of TaskSignal objects that are dependent on the object for their priority), which is initially empty.

A TaskSignal object has an associated dependent (a boolean), which is initially false.

The priority getter steps are to return this's priority.

The onprioritychange attribute is an event handler IDL attribute for the onprioritychange event handler, whose event handler event type is prioritychange.

The static any(signals, init) method steps are to return the result of creating a dependent task signal from signals, init, and the current realm.

A TaskSignal has fixed priority if it is a dependent signal with a null source signal.

To add a priority change algorithm algorithm to a TaskSignal object signal, append algorithm to signal’s priority change algorithms.

To create a dependent task signal from a list of AbortSignal objects signals, a TaskSignalAnyInit init, and a realm:

Let resultSignal be the result of creating a dependent signal from signals using the TaskSignal interface and realm.
Set resultSignal’s dependent to true.
If init["priority"] is a TaskPriority, then:
1. Set resultSignal’s priority to init["priority"].
Otherwise:
1. Let sourceSignal be init["priority"].
2. Set resultSignal’s priority to sourceSignal’s priority.
3. If sourceSignal does not have fixed priority, then:
  1. If sourceSignal’s dependent is true, then set sourceSignal to sourceSignal’s source signal.
  2. Assert: sourceSignal is not dependent.
  3. Set resultSignal’s source signal to a weak reference to sourceSignal.
  4. Append resultSignal to sourceSignal’s dependent signals.
Return resultSignal.

To signal priority change on a TaskSignal object signal, given a TaskPriority priority:

If signal’s priority changing is true, then throw a "NotAllowedError" DOMException.
If signal’s priority equals priority then return.
Set signal’s priority changing to true.
Let previousPriority be signal’s priority.
Set signal’s priority to priority.
For each algorithm of signal’s priority change algorithms, run algorithm.
Fire an event named prioritychange at signal using TaskPriorityChangeEvent, with its previousPriority attribute initialized to previousPriority.
For each dependentSignal of signal’s dependent signals, signal priority change on dependentSignal with priority.
Set signal’s priority changing to false.

3.3.1. Garbage Collection

A dependent TaskSignal object must not be garbage collected while its source signal is non-null and it has registered event listeners for its prioritychange event or its priority change algorithms is non-empty.

3.4. Examples

TODO(shaseley): Add examples.

4. Modifications to Other Standards

4.1. The HTML Standard

4.1.1. `WindowOrWorkerGlobalScope`

Each object implementing the WindowOrWorkerGlobalScope mixin has a corresponding scheduler, which is initialized as a new Scheduler.

partial interface mixin WindowOrWorkerGlobalScope {
  [Replaceable] readonly attribute Scheduler scheduler;
};

The scheduler attribute’s getter steps are to return this's scheduler.

4.1.2. Event loop: definitions

Replace: For each event loop, every task source must be associated with a specific task queue.

With: For each event loop, every task source that is not a scheduler task source must be associated with a specific task queue.

4.1.3. Event loop: processing model

Add the following steps to the event loop processing steps, before step 1:

Let queues be the set of the event loop's task queues that contain at least one runnable task.
Let schedulers be the set of all Scheduler objects whose relevant agent’s event loop is this event loop and that have a runnable task.
If schedulers and queues are both empty, skip to the microtasks step below.

Modify step 1 to read:

Let taskQueue be one of the following, chosen in an implementation-defined manner:
- If queues is not empty, one of the task queues in queues, chosen in an implementation-defined manner.
- If schedulers is not empty, the result of selecting the task queue of the next scheduler task from one of the Schedulers in schedulers, chosen in an implementation-defined manner.

The taskQueue in this step will either be a set of tasks or a set of scheduler tasks. The steps that follow only remove an item, so they are roughly compatible. Ideally, there would be a common task queue interface that supports a pop() method that would return a plain task, but that would involve a fair amount of refactoring.

5. Security Considerations

This section is non-normative.

The main security consideration for the APIs defined in this specification is whether or not any information is potentially leaked between origins by timing-based side-channel attacks.

5.1. `postTask` as a High-Resolution Timing Source

This API cannot be used as a high-resolution timing source. Like setTimeout()'s timeout value, postTask()'s delay is expressed in whole milliseconds (the minimum non-zero delay being 1 ms), so callers cannot express any timing more precise than 1 ms. Further, since tasks are queued when their delay expires and not run instantly, the precision available to callers is further reduced.

5.2. Monitoring Another Origin’s Tasks

The second consideration is whether postTask() leaks any information about other origins' tasks. We consider an attacker running on one origin trying to obtain information about code executing in another origin (and hence in a separate event loop) that is scheduled in the same thread in a browser.

Because a thread within a UA can only run tasks from one event loop at a time, an attacker might be able to gain information about tasks running in another event loop by monitoring when their tasks run. For example, an attacker could flood the system with tasks and expect them to run consecutively; if there are large gaps in between, then the attacker could infer that another task ran, potentially in a different event loop. The information exposed in such a case would depend on implementation details, and implementations can reduce the amount of information as described below.

What Information Might Be Gained?
Concretely, an attacker would be able to detect when other tasks are executed by the browser by either flooding the system with tasks or by recursively scheduling tasks. This is a known attack that can be executed with existing APIs like postMessage(). The tasks that run instead of the attacker’s can be tasks in other event loops as well as other tasks in the attacker’s event loop, including internal UA tasks (e.g. garbage collection).

Assuming the attacker can determine with a high degree of probability that the task executing is in another event loop, then the question becomes what additional information can the attacker learn? Since inter-event-loop task selection is not specified, this information will be implementation-dependent and depends on how UAs order tasks between event loops. But UAs that use a prioritization scheme that treats event loops sharing a thread as a single event loop are vulnerable to exposing more information.

It is helpful to think about the set of potential tasks that a UA might choose instead of the attacker’s, which corresponds to the information gained. When an attacker floods the system with tasks, the set of possible tasks would be anything the UA deems to be higher priority at that moment. This could be the result of a static prioritization scheme, e.g. input is always highest priority, network is second highest, etc., or this could be more dynamic, e.g. the UA occasionally chooses to run tasks from other task sources depending on how long they’ve been starved. Using a dynamic scheme increases the set of potential task which in turn decreases the fidelity of the information.

postTask() supports prioritization for tasks scheduled with it. How these tasks are interleaved with other task sources is also implementation-dependent, however it might be possible for an attacker to further reduce the set of potential tasks that can run instead of its own by leveraging this priority. For example, if a UA uses a simple static prioritization scheme spanning all event loops in a thread, then using user-blocking postTask() tasks instead of postMessage() tasks might decrease this set, depending on their relative prioritization and what is between.

What Mitigations are Possible?
There are mitigations that implementers can consider to minimize the risk:

Where possible, isolate cross-origin event loops by running them in different threads. This type of attack depends on the event loops sharing a thread.
Use an inter-event-loop scheduling policy that is not strictly based on priority. For example, an implementation might use round-robin or fair-scheduling between event loops to prevent leaking information about task priority. Another possibility is to ensure lower priority tasks are periodically cycled in to prevent inferring priority information.

6. Privacy Considerations

This section is non-normative.

We have evaluated the APIs defined in this specification from a privacy perspective and do not believe there to be any privacy considerations.

Prioritized Task Scheduling

Abstract

Status of this document

1. Introduction

2. Scheduling Tasks

2.1. Task Priorities

2.2. The `Scheduler` Interface

2.3. Definitions

2.4. Processing Model

2.4.1. Queueing and Removing Scheduler Tasks

2.4.2. Scheduling Tasks

2.4.3. Selecting the Next Task to Run

2.5. Examples

3. Controlling Tasks

3.1. The `TaskPriorityChangeEvent` Interface

3.2. The `TaskController` Interface

3.3. The `TaskSignal` Interface

3.3.1. Garbage Collection

3.4. Examples

4. Modifications to Other Standards

4.1. The HTML Standard

4.1.1. `WindowOrWorkerGlobalScope`

4.1.2. Event loop: definitions

4.1.3. Event loop: processing model

5. Security Considerations

5.1. `postTask` as a High-Resolution Timing Source

5.2. Monitoring Another Origin’s Tasks

6. Privacy Considerations

Conformance

Document conventions

Index

Terms defined by this specification

Terms defined by reference

References

Normative References

Informative References

IDL Index

Issues Index

Prioritized Task Scheduling

Abstract

Status of this document

1. Introduction

2. Scheduling Tasks

2.1. Task Priorities

2.2. The Scheduler Interface

2.3. Definitions

2.4. Processing Model

2.4.1. Queueing and Removing Scheduler Tasks

2.4.2. Scheduling Tasks

2.4.3. Selecting the Next Task to Run

2.5. Examples

3. Controlling Tasks

3.1. The TaskPriorityChangeEvent Interface

3.2. The TaskController Interface

3.3. The TaskSignal Interface

3.3.1. Garbage Collection

3.4. Examples

4. Modifications to Other Standards

4.1. The HTML Standard

4.1.1. WindowOrWorkerGlobalScope

4.1.2. Event loop: definitions

4.1.3. Event loop: processing model

5. Security Considerations

5.1. postTask as a High-Resolution Timing Source

5.2. Monitoring Another Origin’s Tasks

6. Privacy Considerations

Conformance

Document conventions

Index

Terms defined by this specification

Terms defined by reference

References

Normative References

Informative References

IDL Index

Issues Index

2.2. The `Scheduler` Interface

3.1. The `TaskPriorityChangeEvent` Interface

3.2. The `TaskController` Interface

3.3. The `TaskSignal` Interface

4.1.1. `WindowOrWorkerGlobalScope`

5.1. `postTask` as a High-Resolution Timing Source