== Background ==

- CPU: a machine which does nothing but execute instructions
- thread: a sequence of instructions, a schedulable entity
- scheduler: decides which threads to put on which CPUs, for how long

FreeBSD has two schedulers, ULE (new-ish, default) and 4BSD.  Sources in
sys/kern/sched_ule.c and sched_4bsd.c respectively.  They each implement the
sched_* interface.  Some code in sys/kern/kern_synch.c supports both schedulers.

== Topics ==

Context switching:
- when do we switch contexts, i.e., call mi_switch()?
- how do we pick a new thread?
- how does a thread get assigned to a CPU?

Thread lock:
- a special mutex pointed to by each thread
- when a thread is running, the thread lock points to the per-CPU thread queue's
  mutex
- when a thread is put to sleep, the thread is added to a queue (e.g., a
  sleepqueue or a turnstile), and the thread lock is atomically switched to that
  of the queue
  - then the thread switches off-CPU while holding that queue lock, and
    mi_switch() unlocks it

CPU topology:
- used by sched_pickcpu() to select a target CPU

Interactivity scoring

== Scheduler ticks ==

== Thread states ==

- enum td_states:
  INACTIVE:thread is being created or destroyed
  INHIBITED: thread can't run or has nothing to do
  CAN_RUN: thread is ready to be scheduled (no longer inhibited)
  RUNQ: scheduled to execute on a CPU in the future
  RUNNING: currently executing on a CPU

== Run queues ==

- struct runq
- array of lists of scheduled threads, sorted by priority
- in ULE, each CPU has three run queues, organized into struct tdq
- each tdq has a mutex

ULE runqueues:
- tdq_realtime: pick the highest priority thread and run it
- tdq_timeshare: round-robin scheduling, favouring higher-priority threads
- tdq_idle: always contains the idle thread

== Priority ranges ==

[0, 255] Full range, 0 is the highest priority.
- Not the priority range shown by top(1)/ps(1)!
  - Add PZERO (68) to get the real priority
- Ranges changed somewhat in 14.0, be careful when comparing with 13.x

Real time priority ranges (tdq_realtime):
  [0, 15]  ithreads, SWI threads
  - scheduled from interrupt handlers, typically run for short periods 
  - SWIs are used mostly during packet processing (see netisr(9))
  - FreeBSD 14.0 does timesharing within this band
  [16, 47] real time user threads
  - root only, priority set using special system calls (see rtprio(1))
  [48, 87] kernel thread priorities
  - used by kernel worker threads

Time-sharing priority ranges (tdq_timeshare):
  [88, 223] all non-realtime user threads
  - user threads may be temporarily scheduled as real-time threads while in the
    kernel, e.g., for priority propagation
  - ULE subdivides this range
    [88, 135] interactive threads (placed in tdq_realtime)
    - threads in this range spend much of their time asleep
    - well-behaved GUI applications, shells, network servers, ...
    - realtime threads can starve lower-priority threads, but to be classified
      as interactive, they must sleep
    [136, 223] batch threads
    - round-robin scheduling prevents starvation of low-priority threads
      [136, 203]
      - used for regular user threads 
      [204, 223]
      - used for niced processes/threads

Idle priorities (tdq_idle):
  [224, 255] all idle priority threads
  - one idle thread per CPU, used to put the CPU to sleep when there is no work
    to do; also performs work stealing in ULE
  - main loop is sched_idletd()
  - can be scheduled manually using idprio(1)