Prioritized Task Scheduling

Draft Community Group Report,

This version:
https://wicg.github.io/scheduling-apis/
Issue Tracking:
GitHub
Inline In Spec
Editor:
(Google)

Abstract

This specification defines APIs for scheduling and controlling prioritized tasks.

Status of this document

This specification was published by the Web Platform Incubator Community Group. It is not a W3C Standard nor is it on the W3C Standards Track. Please note that under the W3C Community Contributor License Agreement (CLA) there is a limited opt-out and other conditions apply. Learn more about W3C Community and Business Groups.

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 an "AbortError" DOMException 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 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.

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


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.

To create a scheduler task queue with TaskPriority priority:
  1. Let queue be a new scheduler task queue.

  2. Set queue’s priority to priority.

  3. Set queue’s tasks to a new empty set.

  4. 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. Processing Model

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:
  1. Let task be a new scheduler task.

  2. Set task’s enqueue order to enqueue order.

  3. Set task’s steps to steps.

  4. Set task’s source to source.

  5. Set task’s document to document.

  6. Set task’s script evaluation environment settings object set to a new empty set.

  7. Append task to queue’s tasks.

  8. 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, run the following steps:
  1. Let result be a new promise.

  2. Let signal be options["signal"] if options["signal"] exists, or otherwise null.

  3. If signal is not null and its aborted flag is set, then reject result with an "AbortError" DOMException and return result.

  4. Let priority be options["priority"] if options["priority"] exists, or otherwise null.

  5. Let queue be the result of selecting the scheduler task queue for scheduler given signal and priority.

  6. Let delay be options["delay"].

  7. If delay is greater than 0, then run these steps in parallel:

    1. Let global be the relevant global object for scheduler.

    2. If global is a Window object, wait until global’s associated Document has been fully active for a further delay milliseconds (not necessarily consecutively).

      Otherwise, global is a WorkerGlobalScope object; wait until delay milliseconds have passed with the worker not suspended (not necessarily consecutively).

    3. Wait until any invocations of this algorithm that had the same scheduler, that started before this one, and whose delay is equal to or less than this one’s, have completed.

    4. Optionally, wait a further implementation-defined length of time.

    5. Schedule a task to invoke a callback for scheduler given queue, signal, callback, and result.

  8. Otherwise, schedule a task to invoke a callback for scheduler given queue, signal, callback, and result.

  9. Return result.

We need to figure out exactly how we want to spec delayed tasks, and if we can refactor the timer spec to use a common method. As written, this uses steps 15–17 of the timer initialization steps algorithm, but there are a couple things we might want to change: (1) how to account for suspend? (2) how to account for current throttling techniques (see also this issue)?

To select the scheduler task queue for a Scheduler scheduler given an AbortSignal or null signal, and a TaskPriority or null priority:
  1. If priority is null and signal is not null and signal 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].

  2. 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:
  1. Let global be the relevant global object for scheduler.

  2. Let document be global’s associated Document if global is a Window object; otherwise null.

  3. Let enqueue order be scheduler’s next enqueue order.

  4. Increment scheduler’s next enqueue order by 1.

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

  6. If signal is not null, then add the following abort steps to it:

    1. Remove task from queue.

    2. Reject result with an "AbortError" DOMException.

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, run the following steps:
  1. Let queues be the result of getting the values of scheduler’s static priority task queue map.

  2. Extend queues with the result of getting the values of scheduler’s dynamic priority task queue map.

  3. Remove from queues any queue such that queue’s tasks do not contain a runnable scheduler task.

  4. 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:
  1. Let queues be the result of getting the runnable task queues for scheduler.

  2. If queues is empty return null.

  3. Remove from queues any queue such that queue’s priority is less than any other item of queues.

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

  5. 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:
  1. Let signal be a new TaskSignal object.

  2. Set signal’s priority to init["priority"].

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

[Exposed=(Window, Worker)]
interface TaskSignal : AbortSignal {
  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.

signal . priority

Returns the TaskPriority of the signal.

A TaskSignal object has an associated TaskPriority priority.

A TaskSignal object has an associated priority changing boolean, intially set to false.

A TaskSignal object has associated priority change algorithms, which is a set of algorithms, initialized to a new empty set. These algorithms are to be executed when its priority changing value is true.

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.

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

To signal priority change on a TaskSignal object signal, given a TaskPriority priority, run the following steps:
  1. If signal’s priority changing is true, then throw a "NotAllowedError" DOMException.

  2. If signal’s priority equals priority then return.

  3. Set signal’s priority changing to true.

  4. Let previousPriority be signal’s priority.

  5. Set signal’s priority to priority.

  6. For each algorithm of signal’s priority change algorithms, run algorithm.

  7. Fire an event named prioritychange at signal using TaskPriorityChangeEvent, with its previousPriority attribute initialized to previousPriority.

  8. Set signal’s priority changing to false.

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 {
  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:

  1. Let queues be the set of the event loop's task queues that contain at least one runnable task.

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

  3. If schedulers and queues are both empty, skip to the microtasks step below.

Modify step 1 to read:

  1. Let taskQueue be one of the following, 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 invlove 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:

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.

Conformance

Document conventions

Conformance requirements are expressed with a combination of descriptive assertions and RFC 2119 terminology. The key words “MUST”, “MUST NOT”, “REQUIRED”, “SHALL”, “SHALL NOT”, “SHOULD”, “SHOULD NOT”, “RECOMMENDED”, “MAY”, and “OPTIONAL” in the normative parts of this document are to be interpreted as described in RFC 2119. However, for readability, these words do not appear in all uppercase letters in this specification.

All of the text of this specification is normative except sections explicitly marked as non-normative, examples, and notes. [RFC2119]

Examples in this specification are introduced with the words “for example” or are set apart from the normative text with class="example", like this:

This is an example of an informative example.

Informative notes begin with the word “Note” and are set apart from the normative text with class="note", like this:

Note, this is an informative note.

Conformant Algorithms

Requirements phrased in the imperative as part of algorithms (such as "strip any leading space characters" or "return false and abort these steps") are to be interpreted with the meaning of the key word ("must", "should", "may", etc) used in introducing the algorithm.

Conformance requirements phrased as algorithms or specific steps can be implemented in any manner, so long as the end result is equivalent. In particular, the algorithms defined in this specification are intended to be easy to understand and are not intended to be performant. Implementers are encouraged to optimize.

Index

Terms defined by this specification

Terms defined by reference

References

Normative References

[DOM]
Anne van Kesteren. DOM Standard. Living Standard. URL: https://dom.spec.whatwg.org/
[HTML]
Anne van Kesteren; et al. HTML Standard. Living Standard. URL: https://html.spec.whatwg.org/multipage/
[INFRA]
Anne van Kesteren; Domenic Denicola. Infra Standard. Living Standard. URL: https://infra.spec.whatwg.org/
[RFC2119]
S. Bradner. Key words for use in RFCs to Indicate Requirement Levels. March 1997. Best Current Practice. URL: https://datatracker.ietf.org/doc/html/rfc2119
[WebIDL]
Boris Zbarsky. Web IDL. URL: https://heycam.github.io/webidl/

Informative References

[REQUESTIDLECALLBACK]
Ross McIlroy; Ilya Grigorik. Cooperative Scheduling of Background Tasks. URL: https://w3c.github.io/requestidlecallback/

IDL Index

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

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 = {});
};

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

  readonly attribute TaskPriority previousPriority;
};

dictionary TaskPriorityChangeEventInit : EventInit {
  required TaskPriority previousPriority;
};

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

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

  undefined setPriority(TaskPriority priority);
};

[Exposed=(Window, Worker)]
interface TaskSignal : AbortSignal {
  readonly attribute TaskPriority priority;

  attribute EventHandler onprioritychange;
};

partial interface mixin WindowOrWorkerGlobalScope {
  readonly attribute Scheduler scheduler;
};

Issues Index

Would it be simpler to just use a timestamp here?
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.
We need to figure out exactly how we want to spec delayed tasks, and if we can refactor the timer spec to use a common method. As written, this uses steps 15–17 of the timer initialization steps algorithm, but there are a couple things we might want to change: (1) how to account for suspend? (2) how to account for current throttling techniques (see also this issue)?
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).
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 invlove a fair amount of refactoring.