Scheduler

Overview

• The basic scheduling unit of the XWOS scheduler is the thread. MMU virtual memory and process are not currently supported;
• Each thread has its own independent stack memory, but all memory is visible to all threads, unless restrictions are added using an MPU;
• Each thread has a scheduling priority;
• The scheduler can freeze threads, supporting power management;
• Each CPU has its own independent scheduler. Threads can only be scheduled within their own CPU’s scheduler. If movement between CPUs is needed, a migration operation must be performed;

Priority

XWOS priorities are represented with the type xwpr_t:

• The smaller the value, the lower the priority; the larger the value, the higher the priority.
• For future extensibility, macros should be used instead of raw xwpr_t numeric values:
  • The minimum priority can be obtained via the macro XWOS_SKD_PRIORITY_RT_MIN.
  • The maximum priority can be obtained via the macro XWOS_SKD_PRIORITY_RT_MAX.
  • An invalid priority can be obtained via the macro XWOS_SKD_PRIORITY_RT_INVALID.
  • Other priorities should be calculated using the maximum and minimum priorities:
    • Lower priority via the macro XWOS_SKD_PRIORITY_DROP;
    • Raise priority via the macro XWOS_SKD_PRIORITY_RAISE.

Scheduling Algorithm

Data Types

• Each priority has a FIFO ready queue;
• A bitmap marks whether each priority queue is empty; the bit corresponding to a non-empty queue is set to 1, otherwise cleared to 0.

Scheduling Flow

• Define the operation fls: starting from the most significant bit, find the first bit set to 1 and return its index. If all bits are 0, return -1. This operation requires corresponding CPU instructions, e.g., ARM’s clz, DEC Alpha’s ctlz, x86’s lzcnt, PowerPC’s cntlz, etc.

• Flowchart

flowchart TB
    start --> fls
    fls --> idx
    idx --No--> idle
    idx --Yes--> q
    q --> t
    t --> skd
    skd --> e
    idle --> e

    start("Start")
    fls["idx = fls(bitmap)"]
    idx{"idx >= 0 ?"}
    idle["Schedule idle task"]
    q["Select ready queue for priority idx"]
    t["Select first thread from head of ready queue"]
    skd["Schedule selected thread"]
    e("End")

Starting the Scheduler

When the boot flow enters xwos_main(), the scheduler can be started by calling xwos_skd_start_lc(). At this point, the context will switch from boot to thread.

Preemption

The scheduler always selects the thread with the highest priority. Higher-priority threads can preempt lower-priority threads.

For threads with the same priority, the scheduler schedules them in FIFO order. Threads of the same priority cannot preempt each other.

Users can disable preemption: xwos_skd_dspmpt_lc(), and enable preemption: xwos_skd_enpmpt_lc().

Special Tasks in the Scheduler

Idle Task

• When there are no threads ready in the scheduler, the scheduler schedules the idle task;
• The idle task is special: it belongs to the lowest priority thread context, but cannot use any functions that cause sleeping or blocking.
• Users can hook user code in the idle task. Methods:
  • Define the config BRDCFG_XWSKD_IDLE_HOOK as 1 in the config file xwbd/board/cfg/board.h;
  • Define the function board_xwskd_idle_hook() and add user code inside it.

Bottom Half (BH) Task

• When the scheduler config XWOSCFG_SD_BH is set to 1, the scheduler reserves a highest priority thread for the system;
• The bottom half (BH) task is special: it belongs to thread context, but cannot use any functions that cause sleeping or blocking;
• The bottom half (BH) task can preempt any thread;
• When bottom half (BH) is enabled, the scheduler’s tick timer task runs within the bottom half (BH);
• XWOS’s bottom half (BH) is not fully developed yet and is currently only open for use by the tick timer task.

Users can disable bottom half (BH): xwos_skd_dsbh_lc(), and enable bottom half (BH): xwos_skd_enbh_lc().

Tick Timer Task

• Operating system kernels typically include a timer that generates periodic tick (or beat) interrupts;
• The tick timer task is the periodic task executed in this timer interrupt;
• If the bottom half (BH) task is configured as 1, the tick timer task runs inside the bottom half (BH) task;
• If the bottom half (BH) task is configured as 0, the tick timer task runs in interrupt context;
• Users can hook their own code in the tick timer task. Methods:
  • Define the config BRDCFG_XWSKD_SYSHWT_HOOK as 1 in the config file board_dir/cfg/board.h;
  • Define the function board_xwskd_syshwt_hook() and add user code inside it.

Scheduler Interrupts

Context Switch Interrupt

• An interrupt used by the scheduler to switch the currently executing thread.
• Interrupt priority: lowest.
• Users can hook their own code during context switch:
  • Before the context switch begins:
    • Define the config BRDCFG_XWSKD_PRE_SWCX_HOOK as 1 in the config file board_dir/cfg/board.h;
    • Define the hook function board_thd_preinit_hook().
  • After the context switch begins:
    • Define the config BRDCFG_XWSKD_POST_SWCX_HOOK as 1 in the config file board_dir/cfg/board.h;
    • Define the hook function board_thd_postinit_hook().

Tick Timer Interrupt

• A timer interrupt used to generate periodic tick (or beat) interrupts. The tick timer task is triggered by this interrupt.
• Interrupt priority: context switch interrupt <= tick timer interrupt <= scheduler service interrupt.

Scheduler Service Interrupt

• A software interrupt (softirq) used to execute special scheduler operations, including:
  • Scheduler suspend xwosplcb_skd_suspend_lic()
  • Thread exit xwosplcb_thd_exit_lic()
  • Thread freeze xwosplcb_thd_freeze_lic()
  • Thread migration xwosplcb_thd_immigrate_lic() and xwosplcb_thd_outmigrate_lic()
• Interrupt priority: context switch interrupt <= tick timer interrupt <= scheduler service interrupt.

Hardware Timer

• The XWOS kernel requires each CPU to have a private tick timer that generates interrupts at a fixed frequency;
• Typically configured as 1000 Hz. Refer to the config XWOSCFG_SYSHWT_PERIOD in the config file xwbd/board/cfg/xwos.h;
• XWOS’s tick timer produces three variables:
  • tickcount tick count
    • At each tick timer interrupt, tickcount increments by 1;
    • tickcount indicates how many tick timer interrupts have occurred;
    • tickcount is a per-CPU variable; whichever CPU the code runs on, the tickcount of that CPU is accessed;
    • The current CPU’s tickcount can be obtained via CAPI xwtm_nowtc().
  • timetick system time
    • The XWOS kernel uses nanoseconds (ns) as the basic unit of time. Assuming a ticker frequency of 1000 Hz, tickcount increases once every 1 ms, i.e., every 1 ms it increases by 1000000;
    • The relationship between timetick and tickcount is: timetick = tickcount * 1000000;
    • timetick is a per-CPU variable; whichever CPU the code runs on, the timetick of that CPU is accessed;
    • The current CPU’s timetick can be obtained via CAPI xwtm_now().
    • timestamp system timestamp
    • timestamp is the system timestamp in nanoseconds;
    • timestamp is obtained by calculating how much time remains until the next tick timer interrupt and adding it to timetick. Its precision is determined by the SOC’s main frequency and the counter’s bit width;
    • timestamp is a per-CPU variable; whichever CPU the code runs on, the timestamp of that CPU is accessed;
    • The current CPU’s timestamp can be obtained via CAPI xwtm_nowts().

Timeout Management

Time Tree

In the XWOS kernel, every object that requires timeout management (threads, software timers) is organized into the time tree as a time tree node. A time tree node contains a timeout system time point. Each time the scheduler enters the tick timer task, it checks whether any nodes in the time tree have timed out. In the time tree, all nodes’ system time points are in the future. The node that times out first is always the one with the smallest system time point. Therefore, the timeout problem of the time tree is a problem of finding the minimum value. XWOS uses a red-black tree to solve this minimum value problem, so this algorithm is called the time tree.

• A leftmost pointer points to the minimum value, allowing direct and fast retrieval of the minimum value from leftmost upon timeout, with a time complexity of O(1);
• After timeout, leftmost is removed from the red-black tree. According to the properties of a binary tree, the next leftmost is the right child (i.e., successor) of the former. If the successor of the former is a leaf, the next leftmost must be the parent node of the former, with an algorithmic time complexity of O(1);
• Removing leftmost is a high-frequency operation in the system, but since leftmost lacks a left subtree, and according to the properties of the red-black tree, the right subtree cannot be too complex either, meaning that the cost of rebalancing the red-black tree after removing leftmost is not too high;
• The insert operation requires traversing the tree, with a time complexity of O(logn);
• Red-black trees do not allow nodes with equal keys, so nodes with the same system time point form a linked list. When a timeout occurs, they are all woken up.

Unified Form of Timeout Functions

All XWOS CAPI functions with timeout management end with the suffix _to, and the timeout parameter is xwtm_t to:

/* Sleep */
xwer_t xwos_cthd_sleep_to(xwtm_t to);

/* Wait semaphore */
xwer_t xwos_sem_wait_to(struct xwos_sem * sem, xwtm_t to);

/* Wait condition variable */
xwer_t xwos_cond_wait_to(struct xwos_cond * cond,
                         union xwlk_ulock lock, xwsq_t lktype,
                         void * lkdata, xwtm_t to, xwsq_t * lkst);

/* Wait mutex */
xwer_t xwos_mtx_lock_to(struct xwos_mtx * mtx, xwtm_t to);


/* Wait event flag */
xwer_t xwos_flg_wait_to(struct xwos_flg * flg, xwsq_t trigger, xwsq_t action,
                        xwbmp_t origin[], xwbmp_t msk[],
                        xwtm_t to);

/* Wait signal selector */
xwer_t xwos_sel_select_to(struct xwos_sel * sel, xwbmp_t msk[], xwbmp_t trg[], xwtm_t to);

/* Wait thread barrier */
xwer_t xwos_br_wait_to(struct xwos_br * br, xwsq_t pos, xwbmp_t sync[], xwtm_t to);

The parameter to indicates the future time point at which the thread expects to be woken up.

When a user implements an interface with timeout functionality and finds that multiple CAPI with timeout functionality need to be called within it, worse still, these CAPI may internally call other CAPI with timeout functionality.

Calculating how much time each CAPI has spent and subtracting it from the timeout period is clearly difficult to implement. The simplest approach is to focus only on the result, i.e., only caring about at what future time point to wake up. Pass this future time point down through internal CAPI. Regardless of how many layers these CAPI with timeout functionality are called, as long as a timeout occurs, wake up.

For example:

xwer_t my_api(..., xwtm_t to)
{
        xwer_t rc;

        ...omitted...
        rc = xwos_mtx_lock_to(mtx, to);
        ...omitted...
        rc = xwos_sem_wait_to(sem, to);
        ...omitted...
        return rc;
}

No matter how much time xwos_mtx_lock_to() has waited, it will not affect xwos_sem_wait_to() waking up at the time point to. When xwos_mtx_lock_to() has used up all the time, to becomes a past time point, and xwos_sem_wait_to() returns -ETIMEDOUT immediately.

Getting the Context

XWOS provides the CAPI xwos_skd_get_context_lc() to obtain the context:

• XWOS_SKD_CONTEXT_INIT_EXIT : Initialization and deinitialization
• XWOS_SKD_CONTEXT_THD : Thread
• XWOS_SKD_CONTEXT_ISR : Interrupt
• XWOS_SKD_CONTEXT_BH : Bottom half (BH)
• XWOS_SKD_CONTEXT_IDLE : Idle task

Pausing and Continuing the Scheduler

• xwos_skd_pause_lc() : Pause the local CPU scheduler

  • Pausing the scheduler involves several operations:
    • 1. Disable preemption of the local CPU scheduler;
    • 2. Disable bottom half (BH) of the local CPU scheduler;
    • 3. Shut down the local CPU’s system tick timer.

• xwos_skd_continue_lc() : Continue running the local CPU scheduler

  • Continuing the scheduler involves several operations:
    • 1. Start the local CPU’s system tick timer;
    • 2. Enable bottom half (BH) of the local CPU scheduler;
    • 3. Enable preemption of the local CPU scheduler.

CAPI Reference

• Header <xwos/osal/skd.h>
• Header <xwos/osal/time.h>