<commit_before>.. _scheduling_v2:

Scheduling
##########

The kernel's priority-based scheduler allows an application's threads
to share the CPU.

Concepts
********

The scheduler determines which thread is allowed to execute
at any point in time; this thread is known as the **current thread**.

Whenever the scheduler changes the identity of the current thread,
or when execution of the current thread is replaced by an ISR,
the kernel first saves the current thread's CPU register values.
These register values get restored when the thread later resumes execution.


Scheduling Algorithm
====================

The kernel's scheduler selects the highest priority ready thread
to be the current thread. When multiple ready threads of the same priority
exist, the scheduler chooses the one that has been waiting longest.

.. note::
    Execution of ISRs takes precedence over thread execution,
    so the execution of the current thread may be replaced by an ISR
    at any time unless interrupts have been masked. This applies to both
    cooperative threads and preemptive threads.

Cooperative Time Slicing
========================

Once a cooperative thread becomes the current thread, it remains
the current thread until it performs an action that makes it unready.
Consequently, if a cooperative thread performs lengthy computations,
it may cause an unacceptable delay in the scheduling of other threads,
including those of higher priority and equal priority.


  .. image:: cooperative.svg
     :align: center

To overcome such problems, a cooperative thread can voluntarily relinquish
the CPU from time to time to permit other threads to execute.
A thread can relinquish the CPU in two ways:

* Calling :cpp:func:`k_yield()` puts the thread at the back of the scheduler's<commit_msg>doc: kernel: use kconfig documentation in main kernel doc<commit_after>.. _scheduling_v2:

Scheduling
##########

The kernel's priority-based scheduler allows an application's threads
to share the CPU.

Concepts
********

The scheduler determines which thread is allowed to execute
at any point in time; this thread is known as the **current thread**.

Whenever the scheduler changes the identity of the current thread,
or when execution of the current thread is replaced by an ISR,
the kernel first saves the current thread's CPU register values.
These register values get restored when the thread later resumes execution.


Scheduling Algorithm
====================

The kernel's scheduler selects the highest priority ready thread
to be the current thread. When multiple ready threads of the same priority
exist, the scheduler chooses the one that has been waiting longest.

.. note::
    Execution of ISRs takes precedence over thread execution,
    so the execution of the current thread may be replaced by an ISR
    at any time unless interrupts have been masked. This applies to both
    cooperative threads and preemptive threads.


The kernel can be built with one of several choices for the ready queue
implementation, offering different choices between code size, constant factor
runtime overhead and performance scaling when many threads are added.

* Simple linked-list ready queue (:option:`CONFIG_SCHED_DUMB`)

  The scheduler ready queue will be implemented as a simple unordered list, with
  very fast constant time performance for single threads and very low code size.
  This implementation should be selected on systems with constrained code size
  that will never see more than a small number (3, maybe) of runnable threads in
  the queue at any given time.  On most platforms (that are not otherwise using
  the red/black tree) this results in a savings of ~2k of code size.

* Red/black tree ready queue (:option:`CONFIG_SCHED_SCALABLE`)

  The scheduler ready queue will be implemented as a red/black tree.  This has
  rather slower constant-time insertion and removal overhead, and on most
  platforms (that are not otherwise using the red/black tree somewhere) requires
  an extra ~2kb of code. The resulting behavior will scale cleanly and
  quickly into the many thousands of threads.

  Use this for applications needing many concurrent runnable threads (> 20 or
  so).  Most applications won't need this ready queue implementation.

* Traditional multi-queue ready queue (:option:`CONFIG_SCHED_MULTIQ`)

  When selected, the scheduler ready queue will be implemented as the
  classic/textbook array of lists, one per priority (max 32 priorities).

  This corresponds to the scheduler algorithm used in Zephyr versions prior to
  1.12.

  It incurs only a tiny code size overhead vs. the "dumb" scheduler and runs in
  O(1) time in almost all circumstances with very low constant factor.  But it
  requires a fairly large RAM budget to store those list heads, and the limited
  features make it incompatible with features like deadline scheduling that
  need to sort threads more finely, and SMP affinity which need to traverse the
  list of threads.

  Typical applications with small numbers of runnable threads probably want the
  DUMB scheduler.


The wait_q abstraction used in IPC primitives to pend threads for later wakeup
shares the same backend data structure choices as the scheduler, and can use
the same options.

* Scalable wait_q implementation (:option:`CONFIG_WAITQ_SCALABLE`)

  When selected, the wait_q will be implemented with a balanced tree.  Choose
  this if you expect to have many threads waiting on individual primitives.
  There is a ~2kb code size increase over :option:`CONFIG_WAITQ_DUMB` (which may
  be shared with :option:`CONFIG_SCHED_SCALABLE`) if the red/black tree is not
  used elsewhere in the application, and pend/unpend operations on "small"
  queues will be somewhat slower (though this is not generally a performance
  path).

* Simple linked-list wait_q (:option:`CONFIG_WAITQ_DUMB`)

  When selected, the wait_q will be implemented with a doubly-linked list.
  Choose this if you expect to have only a few threads blocked on any single
  IPC primitive.

Cooperative Time Slicing
========================

Once a cooperative thread becomes the current thread, it remains
the current thread until it performs an action that makes it unready.
Consequently, if a cooperative thread performs lengthy computations,
it may cause an unacceptable delay in the scheduling of other threads,
including those of higher priority and equal priority.


  .. image:: cooperative.svg
     :align: center

To overcome such problems, a cooperative thread can voluntarily relinquish
the CPU from time to time to permit other threads to execute.
A thread can relinquish the CPU in two ways:

* Calling :cpp:func:`k_yield()` puts the thread at the back of the scheduler's
{'fraction_non_alphanumeric': 0.05286671630677588, 'fraction_numerical': 0.002084884586746091, 'mean_word_length': 4.482448979591837, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '3507644', 'n_tokens_mistral': 1677, 'n_tokens_neox': 1560, 'n_words': 964}