Real-time scheduling

include/sch/rt_sched.h View source View on GitHub

Big Idea: Real-time scheduler load balancing

Real-time scheduler load balancing

Experimental

Audience: Realtime program writers and scheduler interested people
Author: axvon

Overview

Our realtime thread scheduling load balancing philosophy is based around this following “overarching theory statement”:

“Always pull, never push.”

Whenever load balancing occurs, there is always a “positive” party, and a “negative” party.

The positive party is the one which gets load removed, and the negative party is the one that gets load added.

Within realtime scheduling, some amount of non-determinism will always be present (e.g. the branch predictor decides to evict entries from its BTB, the cache misses a few times here and there, a spinlock is spun on for a few extra cycles).

Thus, our goal becomes NOT to completely remove non-determinism, as that becomes somewhat of an infeasible plumbing job, but rather, it is to minimize non-determinism and its harm.

Background

Realtime scheduler load balancing has long been a topic of great contention in realtime scheduling. Although EDF is a provably optimal algorithm on uniprocessor systems, its performance and optimality is varied on multiprocessor machines.

Summary

Load balancing in a realtime operating system that supports timesharing scheduling is inherently non-deterministic. The outcome of a load balance is almost entirely dependent on the various loads present on the different nodes and logical processors.

However, we can reduce this non-determinism by making the load balancing unidirectional, or in other words, only allowing one kind of migration.

There are two main kinds of load migration:

Pushing is when the positive party actively offloads its work onto the negative party, with the negative party not having any say in this matter.

Pulling is when the negative party actively takes work from the positive party, with the positive party not being able to do much regarding this action.

Within realtime scheduling, the impact of the non-determinism from pushing is clearly much more significant and harmful than pulling.

Imagine this: CPU0 is happily running its 3 realtime tasks

CPU1 is unhappily running its 9 realtime tasks

CPU0 is making its way through a long-running compute task, with 2 more interactive tasks in the queue

CPU1 is switching more rapidly between its 8 tasks

Then, all of a sudden, CPU1 context switches, and exclaims “I can’t take this anymore!”, and it pushes 3 of its tasks onto CPU0.

Now, CPU0 has had an influx of work, but it is still running its compute task. This brings a major problem:

“The work we just moved will have no guarantee that it is run”

And we can end up in this scenario:

CPU0 is happily running one of its 6 realtime tasks, but some new tasks are sitting in the queue expecting to be switched to, but that never happens.

CPU1 is now a bit less frustrated about its load, but now 3 tasks that were originally assigned to it are waiting in a runqueue, and it no longer is able to choose when those 3 tasks will get to run again, unless it tracks the affinity of each of the tasks that it was running and moves them back.

Now, compare this to pull-only policies: CPU0 is happily running its 3 realtime tasks

CPU1 is unhappily running its 9 realtime tasks

CPU0 context switches, and notices that CPU1 has some extra work it can take. It decides to pull it over, and then immediately run it.

Now, although CPU0 has had work added, this work is guaranteed runtime after the migration, potentially allowing it to complete early/giving it more CPU time.

From this example, we can see how using pull-only migration provides stricter, deterministic guarantees about whether or not a task will run after being migrated. This is the primary reason why we are choosing this paradigm, in addition to a slight improvement in when tasks get migrated (i.e. on the negative party’s side, an explicit call to yield the processor must be made for work to be added, as opposed to work pushing where the negative party can randomly get work added.

API

TODO

Errors

The modular realtime scheduler system of this kernel allows realtime schedulers to fail, and fails upwards. TODO

Context

The realtime scheduler exists under the broader scheduling and multitasking capabilities of this kernel, and exists in contrast to the primary timesharing scheduler which is detailed to a greater extent elsewhere.

Constraints

TODO

Internals

TODO

Strategy

TODO

Rationale

TODO

Structs

rt_slot_request

struct rt_slot_request (3 fields)

§ char *name

Debug

§ enum rt_slot_priority prio

§ int32_t mapped_to

-1 = none

rt_scheduler_blocklist_node

struct rt_scheduler_blocklist_node (2 fields)

§ struct list_node list

§ char *blocked_scheduler_name

rt_scheduler_percpu_permitted

struct rt_scheduler_percpu_permitted (3 fields)

§ enum rt_scheduler_capability allowed_capabilities

§ struct list_head blocklist

§ struct spinlock lock

rt_thread_summary

struct rt_thread_summary (5 fields)

This field exists as a “Summary of the summary”. It gives us a high level, obvious and simple (but somewhat inaccurate) indicator to motivate the core scheduler to read the other fields inside this structure. Its main role is for performance/quick summaries

§ enum rt_scheduler_status status

§ rt_weight_t weight

A “weight” of the load on the scheduler. A thread provides a base weight, and then this can be added or removed depending on properties of the thread

§ rt_weight_t weight_ewma

§ rt_urgency_t urgency

Urgency is separate from the weight of a thread. There can be a lot of threads on an RT scheduler, but they could all just be hitting their deadlines fine and doing a-OK, indicating that there is less of a need for migrations to happen away

§ rt_urgency_t urgency_ewma

rt_thread_summary_ext

struct rt_thread_summary_ext (2 fields)

§ struct rt_scheduler_static *source

The statically allocated variable, used to compare if two exts are from the same scheduler for decisionmaking bias

§ void *private

We DO NOT hardcode _ext fields into the main structure. All we can do is check if two rt_schedulers are using the same policy, and then allow them to coordinate internally IF AND ONLY IF that is the case.

rt_thread_shed_request

struct rt_thread_shed_request (4 fields)

Because we adopt a “Pull only” philosophy within load balancing, we use “shed requests” to allow RT schedulers to say “I have work, take it away from me”. These exist separate from summaries, as these will set a bit in a per-domain bitmap regarding the RT scheduler request statuses

§ bool on

Not always on

§ rt_urgency_t urgency

How much do we need to have things moved?

§ size_t threads_available

How many can we take away?

§ struct list_head threads

This is a “suggestion” list of threads to take. Notably, the amount of threads on this list does NOT HAVE TO match the threads_available. This gives us the ability to potentially say “Hey, we have X threads available, however, we do not know specifically which of these you might want to take.

(e.g. RR might just see that there are too many threads, and simply say “we have N too many”) Rule behind this: before anything is ever taken from threads, it MUST be verified that it can be taken.

Ideally, no pinned threads should end up here, however, if any do, (or if any incompatible cpu masks are here), they should absolutely not get pulled onto another domain

rt_scheduler_ops

struct rt_scheduler_ops (15 fields)

The rt_scheduler lock is held prior to calling these functions unless explicitly stated otherwise

§ rt_scheduler_static_fn on_load

RT scheduler initialization happens once at load/boot

§ rt_scheduler_static_fn on_unload

§ rt_scheduler_fn init

RT scheduler lock not held

§ rt_scheduler_fn destroy

Must be called AFTER the RT scheduler is not used

§ rt_scheduler_fn switch_in

scheduler switched in

§ rt_scheduler_fn switch_out

scheduler switched out

§ rt_scheduler_fn on_failure

Called when the RT scheduler fails. This is not intended to do much heavy lifting, and is meant to instead recover what can be recovered/log data

§ enum rt_scheduler_error (*migrate_twin)(struct rt_scheduler *self, struct rt_scheduler *other)

Two RT schedulers are deemed “twins” if they belong to the same rt_scheduler_static. This allows rt schedulers of the same type to make migration decisions, and make them better than what the core scheduler might be able to “guess/estimate”

Both locks are acquired

§ struct thread *(*pick_thread)( struct rt_scheduler *)

§ rt_scheduler_thread_fn add_thread

§ rt_scheduler_thread_fn remove_thread

§ struct rt_thread_summary_ext (*get_summary_ext)(struct rt_scheduler *)

§ rt_scheduler_fn on_tick

Use t->rt_list_node for this

§ void (*return_all_threads)(struct rt_scheduler *, struct list_head *)

§ rt_domain_id_t (*domain_id_for_cpu)(struct core *)

rt_ext_fn

struct rt_ext_fn (3 fields)

§ const char *name

§ uint32_t id

§ uintptr_t (*fn)(uintptr_t, uintptr_t)

rt_scheduler_mapping

struct rt_scheduler_mapping (8 fields)

Here is how we bind CPUs together within the realtime scheduler:

Basically, every realtime scheduler is expected to return a rt_domain_id_t for each struct core. Each rt_domain_id_t has exactly ONE mapping for which rt_scheduler it is bound to.

Whenever a thread wants to migrate to a given CPU, it doesn’t JUST check if the cpu mask is compatible with that CPU, but rather, with the mask of the rt_scheduler_mapping that that CPU is using for its rt_scheduler structure.

This gives us the ability to choose the granularity which we have our rt_schedulers operate at. We can make them global, we can make them per-node, per-socket, per-cpu, etc…

§ struct rbt_node tree_node

§ struct rt_scheduler_static *static_bptr

§ rt_domain_id_t id

§ struct cpu_mask members

§ struct cpu_mask active

Subset of members

§ struct rt_scheduler *rts

§ struct spinlock lock

§ void *data

rt_scheduler_static

struct rt_scheduler_static (15 fields)

§ struct list_node list_internal

§ struct rbt mappings_internal

“dynamic” object. nodes are dynamic, this is static

§ struct cpu_mask *active_mask_internal

Who is using us?

§ refcount_t refcount

§ struct work teardown_work

§ atomic(enum rt_scheduler_static_state) state

§ struct spinlock state_change_lock

§ const char *name

§ struct rt_scheduler_ops ops

§ enum rt_scheduler_topo_level topo_level

§ enum rt_scheduler_capability capabilities

§ size_t num_slot_requests

We use this to determine how many slot requests we should actually go through and fill

§ struct rt_slot_request slot_requests[RT_SCHEDULER_SLOTS_PER_THREAD]

§ size_t num_ext_fns

§ struct rt_ext_fn ext_fns[] cc_counted_by(num_ext_fns)

rt_scheduler

struct rt_scheduler (10 fields)

This is a structure that is allocated per-CPU at boot time.

Whenever a scheduler is swapped out, this entire thing is cleared/reset, and then another scheduler comes and populates it. This population is allowed to perform allocations and such, so it must take place inside of a DPC. Similarly, destruction happens in a DPC

§ struct list_node list

This is used to keep a global pool of rt_schedulers. We split this per-domain, and whenever a CPU switches into an rt_scheduler, it takes one out of the pool, and whenever a CPU no longer is using its own rt_scheduler, it puts it back into the pool

§ struct core *owner

We make one per-CPU. Who owns this one?

§ struct rt_scheduler_mapping *mapping_source

Used to look at what other CPUs can access this one

§ bool failed_internal

Used to temporarily indicate that the scheduler has FAIL_ASAP’d a function, but it just isn’t safe to fail the scheduler at the current moment (checked later)

§ struct rt_thread_summary summary

Summary of “What’s goin on?”

§ struct rt_thread_shed_request shed_request

§ struct log_site *log_site

This is used for the core scheduler to log general RT scheduler events to, like state transitions and such. The RT scheduler itself is also allowed to modify this, but it can also keep its own log_site

§ struct log_handle log_handle

Similarly, a structure that the core scheduler uses to log rt_scheduler changes and whatnot. Usable by the rt_scheduler itself, but the rt_scheduler can go and do what it likes

§ size_t thread_count

§ struct spinlock lock

This lock protects the rt_scheduler too, however RT schedulers themselves are free to do whatever internal locking they’d like (if that somehow becomes a thing they want to do?)

rt_scheduler_percpu

struct rt_scheduler_percpu (9 fields)

§ struct scheduler *scheduler

Backpointer for this CPU

§ struct rt_scheduler *born_with

§ struct rt_scheduler_mapping *active_mapping

§ struct rt_scheduler_percpu_permitted perms

§ struct semaphore switch_semaphore

This is how we synchronize switching the rt scheduler.

The technique is as follows: We initialize the switch_semaphore to 1.

When entering the switch routine, we first invoke semaphore_wait

Then, inside of the switch, we semaphore_wake

§ struct log_site *log_site

§ struct log_handle log_handle

§ atomic(enum rt_scheduler_error) switch_code

§ atomic(struct rt_scheduler_static *) switch_into

rt_global

struct rt_global (3 fields)

§ struct locked_list static_list

§ struct locked_list *sch_pool

one per domain

§ struct spinlock switch_lock

TODO

If someone can come up with a better solution, tell me

Enums

rt_scheduler_topo_level

enum rt_scheduler_topo_level (7 variants)

This enum exists for debug/info reasons. No actual operations are performed based on the topology level

§ RT_SCHEDULER_TOPO_SMT

Symmetric multiprocessing threads

§ RT_SCHEDULER_TOPO_CORE

SMTs under a core

§ RT_SCHEDULER_TOPO_NUMA

NUMA node

§ RT_SCHEDULER_TOPO_LLC

Last level cache (some processors have multiple L3 caches for a given physical processor)

§ RT_SCHEDULER_TOPO_PACKAGE

Physical processor in a socket

§ RT_SCHEDULER_TOPO_MACHINE

Whole machine

§ RT_SCHEDULER_TOPO_CUSTOM

Custom topology

rt_scheduler_status

enum rt_scheduler_status : uint16_t (4 variants)

rt_scheduler_status: 16 bit “bitflags”:

     ┌───────────────────────────┐
Bits │ 15..12  11..8  7..4  3..0 │
Use  │  AAAA    ****  **IT  D%%% │
     └───────────────────────────┘

D - Degraded performance observed T - Throttled I - CPU isolation A - Unused (Available) * - Unused (Unavailable) %%% - Overloaded amount bits

§ RT_SCHEDULER_STATUS_OK = 0

§ RT_SCHEDULER_STATUS_DEGRADED = 1 << 3

§ RT_SCHEDULER_STATUS_THROTTLED = 1 << 4

§ RT_SCHEDULER_STATUS_ISOLATED = 1 << 5

rt_scheduler_static_state

enum rt_scheduler_static_state (3 variants)

These are the primary instances of an RT scheduler module…

It can either be unloaded (inactive, default), or loaded (_static data structures allocated), or active (there exists an active instance of this rt_scheduler_static on some CPU

§ RT_SCHEDULER_STATIC_UNLOADED

No structures allocated

§ RT_SCHEDULER_STATIC_LOADED

Structures allocated, unused (this state doesn’t strictly need to exist for correctness purposes, but is very helpful in debugging and to allow one to unload unused rt_scheduler_statics

§ RT_SCHEDULER_STATIC_DESTROYING

Taking down. No one can “Grab a ref”

rt_slot_priority

enum rt_slot_priority (2 variants)

§ RT_SLOT_REQUIRED

Scheduler load will fail if this fails

§ RT_SLOT_OPTIONAL

Scheduler load will continue if this fails

Type Aliases

rt_domain_id_t

typedef size_t rt_domain_id_t

rt_weight_t

typedef int32_t rt_weight_t

rt_urgency_t

typedef fx32_32_t rt_urgency_t

This is a range from [-1, 1], where -1 means “Not urgent at all”, and 1 means “absolutely urgent, things keep missing, problems keep happening”…

rt_scheduler_fn

typedef enum rt_scheduler_error (*rt_scheduler_fn)(struct rt_scheduler * *)

rt_scheduler_static_fn

typedef enum rt_scheduler_error (*rt_scheduler_static_fn)(struct rt_scheduler_static * *)

rt_scheduler_thread_fn

typedef void (*rt_scheduler_thread_fn)(
    struct rt_scheduler * *,
    struct thread * *
)

Functions

rt_scheduler_boot_init

void rt_scheduler_boot_init(void)

rt_ext_fn_exec

enum rt_scheduler_error rt_ext_fn_exec(
    struct rt_scheduler_static *rts,
    char *name,
    uint32_t id,
    uintptr_t a,
    uintptr_t b
)

rt_load_scheduler_static

enum rt_scheduler_error rt_load_scheduler_static(struct rt_scheduler_static *rts)

rt_unload_scheduler_static

enum rt_scheduler_error rt_unload_scheduler_static(struct rt_scheduler_static *rts)

rt_scheduler_switch

void rt_scheduler_switch(void)

rt_scheduler_switch_cpu

enum rt_scheduler_error rt_scheduler_switch_cpu(
    size_t cpu,
    struct rt_scheduler_static *into
)

rt_slot_init

void rt_slot_init(size_t num_slots)

Variables

__log_handle_rt_sched

LOG_HANDLE_EXTERN(rt_sched) (1 declaration)

For generic logging

§ struct log_handle __log_handle_rt_sched

rt_wq

extern struct workqueue *rt_wq

rt_global

extern struct rt_global rt_global

Macros

rt_sched_log

#define rt_sched_log(lvl, fmt, ...)

Expansion

#define rt_sched_log(lvl, fmt, ...) \
    log(LOG_SITE(rt_sched), LOG_HANDLE(rt_sched), lvl, fmt, ##__VA_ARGS__)

rt_sched_err

#define rt_sched_err(fmt, ...)

Expansion

#define rt_sched_err(fmt, ...) rt_sched_log(LOG_ERROR, fmt, ##__VA_ARGS__)

rt_sched_warn

#define rt_sched_warn(fmt, ...)

Expansion

#define rt_sched_warn(fmt, ...) rt_sched_log(LOG_WARN, fmt, ##__VA_ARGS__)

rt_sched_info

#define rt_sched_info(fmt, ...)

Expansion

#define rt_sched_info(fmt, ...) rt_sched_log(LOG_INFO, fmt, ##__VA_ARGS__)

rt_sched_debug

#define rt_sched_debug(fmt, ...)

Expansion

#define rt_sched_debug(fmt, ...) rt_sched_log(LOG_DEBUG, fmt, ##__VA_ARGS__)

rt_sched_trace

#define rt_sched_trace(fmt, ...)

Expansion

#define rt_sched_trace(fmt, ...) rt_sched_log(LOG_TRACE, fmt, ##__VA_ARGS__)

RT_SCHEDULER_SLOTS_PER_THREAD

#define RT_SCHEDULER_SLOTS_PER_THREAD 8

We refer to these as “slots”. I could call them “reservations”, but much RT scheduling related work uses “reservation” to refer to time “slices” in static scheduling of tasks, and I don’t want to deal with odd name conflicts