The scheduler: which thread runs next, and the tick. More...

#include <core/system.h>
#include <core/panic.h>
#include <core/arch.h>
#include <sys/proc.h>
#include <sys/sched.h>
#include <sys/signal.h>
#include <ds/list.h>
#include <dev/random.h>
#include <sys/callout.h>
#include <fs/vfs.h>
#include <aquila/stat.h>

Functions
void	sched_cpu_tick (uint32_t period, int user)
	Charges a timer tick to the process that was running on this CPU.
void	sched_timer_tick (uint32_t period, int user)
	Runs the boot CPU's timer tick.
void	sched_alarm_get (struct proc proc, uint64_t value, uint64_t *interval)
	Reads what is left of a process's real time timer.
void	sched_alarm (struct proc proc, uint64_t value, uint64_t interval, uint64_t old_value, uint64_t *old_interval)
	Sets a process's real time timer, which setitimer() and alarm() use: the process gets SIGALRM once value ns have passed, then every interval ns.
void	sched_timer_cancel (struct thread *thread)
	Takes a thread off the list of threads waiting with a deadline, when it no longer waits (it was woken up, or killed).
int	sched_wait (struct waitq *waitq, uint64_t until)
	Puts the current thread to sleep on a wait queue until it is woken up, a signal ends the sleep, or a deadline passes.
int	sched_sleep (uint64_t until)
	Puts the current thread to sleep until a time comes, for nanosleep().
struct cpu *	sched_thread_cpu (struct thread *thread)
	Finds the CPU that is running a thread, if it's another CPU than this one.
void	sched_thread_kick (struct thread *thread)
	Makes a thread that runs on another CPU enter the kernel now, rather than at its next tick: a signal came for it, or it was killed.
void	sched_thread_killed (void)
	Ends the current thread, which was killed while it ran on this CPU (thread->killed).
static void	sched_cpu_wake (void)
	Wakes up an idle CPU to run a thread that just became ready.
void	sched_thread_ready (struct thread *thread)
	Puts a thread at the end of the ready list, to run in its turn.
void	sched_thread_wake (struct thread *thread)
	Makes a thread that was sleeping ready to run.
void	kernel_idle (void)
	Gives up the CPU when the current thread can't run anymore (it sleeps, or it exited): the next ready thread runs, or the CPU idles until an interrupt comes.
void	sched_idle_wakeup (void)
	Runs a ready thread now if an interrupt made one ready while this CPU was idle, rather than at the next tick.
void	sched_thread_spawn (struct thread *thread)
	Starts running a thread for the first time.
void	sched_init_spawn (struct proc *init)
	Starts the scheduler with the first process, init, and runs it.
void	schedule (void)
	Switches to the next ready thread.

Variables
static struct list	ready
struct cpu	cpus [CPUS_MAX]
int	cpus_count
static struct list	timed
static struct waitq	naps
static struct list	alarms
int	sched_urgent = 0
int	sched_running = 0

Detailed Description

The scheduler: which thread runs next, and the tick.

It is a round robin. The threads that are ready to run wait on one list, shared by every CPU, and run in turn, each for one tick at most. A thread that sleeps or exits gives its CPU to the next ready thread, and a CPU with nothing to run idles until an interrupt comes. See docs/kernel/processes.md.

Definition in file sched.c.

Function Documentation

◆ kernel_idle()

void kernel_idle ( void )

Gives up the CPU when the current thread can't run anymore (it sleeps, or it exited): the next ready thread runs, or the CPU idles until an interrupt comes.

It doesn't return to the caller.

Definition at line 332 of file sched.c.

References arch_idle(), kernel_idle(), ready, and schedule().

Referenced by __arch_cur_thread_kill(), arch_sleep(), kernel_idle(), and schedule().

◆ sched_alarm()

void sched_alarm	(	struct proc *	proc,
		uint64_t	value,
		uint64_t	interval,
		uint64_t *	old_value,
		uint64_t *	old_interval )

Sets a process's real time timer, which setitimer() and alarm() use: the process gets SIGALRM once value ns have passed, then every interval ns.

Parameters

proc	the process
value	the time until the first SIGALRM, in ns; 0 disarms the timer
interval	the time between the next ones, in ns; 0 for none
old_value	if not NULL, set to what was left of the previous timer
old_interval	if not NULL, set to the previous timer's interval

Definition at line 144 of file sched.c.

References proc::alarm_at, proc::alarm_interval, proc::alarm_link, alarms, arch_rtime_ns(), interval, sched_alarm(), and sched_alarm_get().

Referenced by proc_kill(), sched_alarm(), scheduler_init(), and sys_setitimer().

◆ sched_alarm_get()

void sched_alarm_get	(	struct proc *	proc,
		uint64_t *	value,
		uint64_t *	interval )

Reads what is left of a process's real time timer.

Parameters

proc	the process
value	set to the time until it expires, in ns, or 0 if it isn't armed
interval	set to its interval, in ns, or 0 if it isn't armed or expires only once

Definition at line 121 of file sched.c.

References proc::alarm_at, proc::alarm_interval, proc::alarm_link, arch_rtime_ns(), interval, and sched_alarm_get().

Referenced by sched_alarm(), sched_alarm_get(), scheduler_init(), and sys_setitimer().

◆ sched_cpu_tick()

void sched_cpu_tick	(	uint32_t	period,
		int	user )

Charges a timer tick to the process that was running on this CPU.

It is called on every CPU's tick.

The time goes to the process's user time if the tick interrupted user mode, and to its system time otherwise. System calls run with interrupts disabled, so a tick during one waits until it returns, and most kernel time is charged as user time.

Parameters

period	the time since this CPU's previous tick, in ns
user	whether the tick interrupted user mode

Definition at line 54 of file sched.c.

References curproc, curthread, and sched_cpu_tick().

Referenced by sched_cpu_tick(), sched_timer_tick(), scheduler_init(), and x86_sched_handler().

◆ sched_cpu_wake()

void sched_cpu_wake ( void )

static

Wakes up an idle CPU to run a thread that just became ready.

If this CPU is the idle one, it is in an interrupt, and runs the thread on the way out of it (sched_idle_wakeup()).

Definition at line 276 of file sched.c.

References arch_cpu_kick(), cpus, cpus_count, cpu::idle, cpu::kicked, sched_cpu_wake(), and sched_running.

Referenced by sched_cpu_wake(), sched_thread_ready(), and sched_thread_wake().

◆ sched_idle_wakeup()

void sched_idle_wakeup ( void )

Runs a ready thread now if an interrupt made one ready while this CPU was idle, rather than at the next tick.

Without this, every disk request would wait for a tick.

Definition at line 347 of file sched.c.

References cpu::idle, ready, sched_idle_wakeup(), and schedule().

Referenced by aarch64_irq(), irq_dispatch(), sched_idle_wakeup(), and scheduler_init().

◆ sched_init_spawn()

void sched_init_spawn ( struct proc * init )

Starts the scheduler with the first process, init, and runs it.

It doesn't return.

Parameters

init	the first process, made by the caller

Definition at line 375 of file sched.c.

References arch_sched_init(), curthread, proc::cwd, queue::head, proc::mask, proc_init(), vnode::ref, RUNNABLE, sched_init_spawn(), sched_running, sched_thread_spawn(), session_new(), proc::threads, qnode::value, and vfs_root.

Referenced by kmain(), sched_init_spawn(), and scheduler_init().

◆ sched_sleep()

int sched_sleep ( uint64_t until )

Puts the current thread to sleep until a time comes, for nanosleep().

Parameters

until the time to wake up, in arch_rtime_ns() time

Returns: 0, or -ERESTARTSYS if a signal ended the sleep before then

Definition at line 212 of file sched.c.

References naps, sched_sleep(), and sched_wait().

Referenced by sched_sleep(), scheduler_init(), and sys_nanosleep().

◆ sched_thread_cpu()

struct cpu * sched_thread_cpu ( struct thread * thread )

Finds the CPU that is running a thread, if it's another CPU than this one.

Parameters

thread the thread

Returns: the CPU, or NULL if the thread isn't running on another CPU

Definition at line 229 of file sched.c.

References cpus, cpus_count, NULL, and sched_thread_cpu().

Referenced by proc_threads_end(), sched_thread_cpu(), sched_thread_kick(), and scheduler_init().

◆ sched_thread_kick()

void sched_thread_kick ( struct thread * thread )

Makes a thread that runs on another CPU enter the kernel now, rather than at its next tick: a signal came for it, or it was killed.

Parameters

thread the thread

Definition at line 244 of file sched.c.

References arch_cpu_kick(), sched_thread_cpu(), and sched_thread_kick().

Referenced by proc_threads_end(), sched_thread_kick(), scheduler_init(), and signal_to().

◆ sched_thread_killed()

void sched_thread_killed ( void )

Ends the current thread, which was killed while it ran on this CPU (thread->killed).

If its process lives on (an exec() ended the thread), the thread leaves it and wakes up the exec() that waits for it (proc_threads_exec()). It doesn't return.

Definition at line 258 of file sched.c.

References arch_cur_thread_kill(), curthread, NULL, thread::owner, sched_thread_killed(), proc::thread_join, proc::threads, and waitq_wakeup().

Referenced by __x86_irq_handler(), __x86_isr(), aarch64_irq(), aarch64_sync(), sched_thread_killed(), and scheduler_init().

◆ sched_thread_ready()

void sched_thread_ready ( struct thread * thread )

Puts a thread at the end of the ready list, to run in its turn.

Parameters

thread the thread, which must be on no other list

Definition at line 298 of file sched.c.

References ready, thread::run_link, sched_cpu_wake(), and sched_thread_ready().

Referenced by kthread_create(), sched_thread_ready(), sched_thread_wake(), schedule(), scheduler_init(), sys_fork(), and sys_thread_create().

◆ sched_thread_spawn()

void sched_thread_spawn ( struct thread * thread )

Starts running a thread for the first time.

It doesn't return.

Parameters

thread the thread, which has never run

Definition at line 361 of file sched.c.

References arch_thread_spawn(), sched_thread_spawn(), and thread::spawned.

Referenced by sched_init_spawn(), sched_thread_spawn(), schedule(), scheduler_init(), and sys_execve().

◆ sched_thread_wake()

void sched_thread_wake ( struct thread * thread )

Makes a thread that was sleeping ready to run.

An urgent thread (thread->urgent, the network's) goes ahead of the others, and runs as soon as the interrupt that woke it returns.

Parameters

thread the thread that was woken up

Definition at line 315 of file sched.c.

References ready, thread::run_link, sched_cpu_wake(), sched_thread_ready(), sched_thread_wake(), sched_urgent, and thread::urgent.

Referenced by sched_thread_wake(), scheduler_init(), thread_wakeup(), and waitq_wakeup_nopoll().

◆ sched_timer_cancel()

void sched_timer_cancel ( struct thread * thread )

Takes a thread off the list of threads waiting with a deadline, when it no longer waits (it was woken up, or killed).

Parameters

thread the thread

Definition at line 173 of file sched.c.

References sched_timer_cancel(), and thread::timer_link.

Referenced by proc_threads_end(), sched_timer_cancel(), sched_timer_tick(), sched_wait(), and scheduler_init().

◆ sched_timer_tick()

void sched_timer_tick	(	uint32_t	period,
		int	user )

Runs the boot CPU's timer tick.

Besides charging the tick (as on every CPU), it runs the callouts that are due, wakes up the threads whose deadline has passed, and sends SIGALRM to the processes whose real time timer has expired.

Parameters

period	the time since the previous tick, in ns
user	whether the tick interrupted user mode

Definition at line 74 of file sched.c.

References proc::alarm_at, proc::alarm_interval, proc::alarm_link, alarms, arch_cycles(), arch_rtime_ns(), callout_run(), list_entry, list_for, random_add(), sched_cpu_tick(), sched_timer_cancel(), sched_timer_tick(), signal_proc_send(), thread::sleep_until, thread_wakeup(), timed, and thread::timer_link.

Referenced by sched_tick(), sched_timer_tick(), scheduler_init(), and x86_sched_handler().

◆ sched_wait()

int sched_wait	(	struct waitq *	waitq,
		uint64_t	until )

Puts the current thread to sleep on a wait queue until it is woken up, a signal ends the sleep, or a deadline passes.

Parameters

waitq	the wait queue to sleep on
until	the deadline, in arch_rtime_ns() time, or 0 for none

Returns: 0 if the thread was woken up, 1 if the deadline passed, or -ERESTARTSYS if a signal ended the sleep

Definition at line 187 of file sched.c.

References arch_rtime_ns(), curthread, sched_timer_cancel(), sched_wait(), timed, and waitq_sleep().

Referenced by net_main(), posix_file_read(), sched_sleep(), sched_wait(), scheduler_init(), socket_inet_recv(), socket_tcp_accept(), socket_tcp_connect(), socket_tcp_recv(), socket_tcp_send(), sys_poll(), and sys_select().

◆ schedule()

void schedule ( void )

Switches to the next ready thread.

The running thread, if there is one, goes to the end of the ready list; if no thread is ready, the CPU idles. It returns, in the thread that was running, once that thread is chosen again.

Definition at line 400 of file sched.c.

References arch_thread_switch(), curthread, kernel_idle(), list_entry, ready, thread::run_link, sched_thread_ready(), sched_thread_spawn(), sched_urgent, and schedule().

Referenced by aarch64_irq(), aarch64_preempt(), irq_dispatch(), kernel_idle(), sched_idle_wakeup(), schedule(), and scheduler_init().

Variable Documentation

◆ alarms

struct list alarms

static

Definition at line 40 of file sched.c.

Referenced by sched_alarm(), and sched_timer_tick().

◆ cpus

struct cpu cpus[CPUS_MAX]

Definition at line 28 of file sched.c.

Referenced by aarch64_init(), arch_interrupts_info(), arch_sched_init(), arch_thread_kill(), sched_cpu_wake(), sched_thread_cpu(), tlb_shootdown(), x86_apic_setup(), x86_cpu_init(), and x86_smp_init().

◆ cpus_count

int cpus_count

Definition at line 29 of file sched.c.

Referenced by aarch64_init(), arch_interrupts_info(), arch_sched_init(), arch_thread_kill(), sched_cpu_wake(), sched_thread_cpu(), tlb_shootdown(), x86_cpu_init(), and x86_smp_init().

◆ naps

struct waitq naps

static

Definition at line 36 of file sched.c.

Referenced by sched_sleep().

◆ ready

struct list ready

static

Definition at line 25 of file sched.c.

Referenced by kernel_idle(), sched_idle_wakeup(), sched_thread_ready(), sched_thread_wake(), schedule(), and signal_take().

◆ sched_running

int sched_running = 0

Definition at line 367 of file sched.c.

Referenced by channel_acquire(), dma_transfer(), sched_cpu_wake(), and sched_init_spawn().

◆ sched_urgent

int sched_urgent = 0

Definition at line 306 of file sched.c.

Referenced by aarch64_irq(), arch_syscall(), arch_syscall(), irq_dispatch(), sched_thread_wake(), schedule(), and scheduler_init().

◆ timed

struct list timed

static

Definition at line 33 of file sched.c.

Referenced by sched_timer_tick(), and sched_wait().

Functions

Variables

Detailed Description

Function Documentation

◆ kernel_idle()

◆ sched_alarm()

◆ sched_alarm_get()

◆ sched_cpu_tick()

◆ sched_cpu_wake()

◆ sched_idle_wakeup()

◆ sched_init_spawn()

◆ sched_sleep()

◆ sched_thread_cpu()

◆ sched_thread_kick()

◆ sched_thread_killed()

◆ sched_thread_ready()

◆ sched_thread_spawn()

◆ sched_thread_wake()

◆ sched_timer_cancel()

◆ sched_timer_tick()

◆ sched_wait()

◆ schedule()

Variable Documentation

◆ alarms

◆ cpus

◆ cpus_count

◆ naps

◆ ready

◆ sched_running

◆ sched_urgent

◆ timed