The Scheduler. More...

Modules
	Program Loader
	Program loading and user stack management.

	Threads
	Thread of execution.

	Time subsystem
	System time and timers.

	Waiting subsystem
	Wait queue implementation.

Data Structures
struct	sched_queues_t
	Scheduling queues structure. More...

struct	sched_thread_ctx_t
	Per-thread scheduling context. More...

struct	sched_cpu_ctx_t
	Per-CPU scheduling context. More...

Enumerations
enum	schedule_flags_t { SCHED_NORMAL = 0 , SCHED_DIE = 1 << 0 }
	Scheduling flags. More...

Functions
void	sched_thread_ctx_init (sched_thread_ctx_t *ctx)
	Initializes a thread's scheduling context.

void	sched_cpu_ctx_init (sched_cpu_ctx_t ctx, cpu_t self)
	Initializes a CPU's scheduling context.

NORETURN void	sched_idle_loop (void)
	The idle loop for a CPU.

NORETURN void	sched_done_with_boot_thread (void)
	Specify that the boot thread is no longer needed.

uint64_t	sched_nanosleep (clock_t timeout)
	Puts the current thread to sleep.

bool	sched_is_idle (cpu_t *cpu)
	Checks if the CPU is idle.

thread_t *	sched_thread (void)
	Retrieves the currently running thread.

process_t *	sched_process (void)
	Retrieves the process of the currently running thread.

thread_t *	sched_thread_unsafe (void)
	Retrieves the currently running thread without disabling interrupts.

process_t *	sched_process_unsafe (void)
	Retrieves the process of the currently running thread without disabling interrupts.

_NORETURN void	sched_process_exit (uint64_t status)
	Exits the current process.

_NORETURN void	sched_thread_exit (void)
	Exits the current thread.

void	sched_yield (void)
	Yields the CPU to another thread.

void	sched_push (thread_t thread, cpu_t target)
	Pushes a thread onto a scheduling queue.

void	sched_push_new_thread (thread_t thread, thread_t parent)
	Pushes a newly created thread onto the scheduling queue.

void	sched_invoke (interrupt_frame_t frame, cpu_t self, schedule_flags_t flags)
	The main scheduling function.

Detailed Description

The Scheduler.

The scheduler used in Patchwork is loosely based of the Linux O(1) scheduler, so knowing how that scheduler works could be useful, here is an article about it https://litux.nl/mirror/kerneldevelopment/0672327201/ch04lev1sec2.html.

Enumeration Type Documentation

◆ schedule_flags_t

enum schedule_flags_t

Scheduling flags.

Flags that modify the behavior of the sched_invoke() function.

Enumerator
SCHED_NORMAL	No special flags.
SCHED_DIE	Kill and free the currently running thread.

Definition at line 274 of file sched.h.

Function Documentation

◆ sched_cpu_ctx_init()

void sched_cpu_ctx_init	(	sched_cpu_ctx_t *	ctx,
		cpu_t *	self
	)

Initializes a CPU's scheduling context.

Will also register the schedulers timer handler for the CPU.

Parameters

ctx	The `sched_cpu_ctx_t` structure to initialize.
self	The `cpu_t` structure associated with this scheduling context.

Definition at line 83 of file sched.c.

References sched_cpu_ctx_t::active, atomic_store, CPU_ID_BOOTSTRAP, interrupt_frame_t::cs, sched_cpu_ctx_t::expired, thread_t::frame, GDT_CS_RING0, GDT_SS_RING0, cpu_t::id, sched_cpu_ctx_t::idleThread, thread_t::kernelStack, sched_cpu_ctx_t::lock, lock_init(), NULL, sched_cpu_ctx_t::owner, panic(), process_get_kernel(), sched_cpu_ctx_t::queues, interrupt_frame_t::rflags, RFLAGS_ALWAYS_SET, RFLAGS_INTERRUPT_ENABLE, interrupt_frame_t::rip, interrupt_frame_t::rsp, sched_cpu_ctx_t::runThread, sched_idle_loop(), sched_queues_init(), sched_timer_handler(), interrupt_frame_t::ss, thread_new(), THREAD_RUNNING, cpu_t::timer, timer_subscribe(), and stack_pointer_t::top.

Referenced by cpu_init().

◆ sched_done_with_boot_thread()

NORETURN void sched_done_with_boot_thread ( void )

Specify that the boot thread is no longer needed.

The sched_done_with_boot_thread() function is called when the kernel has finished booting and the boot thread is no longer needed, instead of just discarding it, the boot thread becomes the idle thread of the bootstrap cpu.

Definition at line 121 of file sched.c.

References assert, CPU_ID_BOOTSTRAP, sched_thread_ctx_t::deadline, cpu_t::id, thread_t::id, sched_cpu_ctx_t::idleThread, thread_t::process, process_get_kernel(), sched_cpu_ctx_t::runThread, cpu_t::sched, thread_t::sched, sched_idle_loop(), smp_self_unsafe(), and timer_notify_self().

Referenced by kmain().

◆ sched_idle_loop()

NORETURN void sched_idle_loop ( void )

extern

The idle loop for a CPU.

The sched_idle_loop() function is the main loop where idle threads execute. The boot thread will eventually end up here to.

Referenced by sched_cpu_ctx_init(), sched_done_with_boot_thread(), and trampoline_after_jump().

◆ sched_invoke()

void sched_invoke	(	interrupt_frame_t *	frame,
		cpu_t *	self,
		schedule_flags_t	flags
	)

The main scheduling function.

Must be called in an interrupt context.

Parameters

frame	The current interrupt frame.
self	The currently running cpu.
flags	Scheduling flags.

Definition at line 480 of file sched.c.

References sched_cpu_ctx_t::active, sched_thread_ctx_t::actualPriority, assert, atomic_exchange, atomic_load, atomic_store, sched_thread_ctx_t::deadline, sched_cpu_ctx_t::expired, process_t::id, thread_t::id, sched_cpu_ctx_t::idleThread, sched_queues_t::length, sched_cpu_ctx_t::lock, lock_acquire(), lock_release(), LOG_DEBUG, next, NULL, panic(), PRIORITY_MIN, thread_t::process, sched_cpu_ctx_t::runThread, cpu_t::sched, thread_t::sched, sched_compute_actual_priority(), sched_compute_time_slice(), SCHED_DIE, sched_load_balance(), sched_queues_pop(), sched_queues_push(), sched_update_recent_idle_time(), thread_free(), thread_load(), THREAD_PRE_BLOCK, THREAD_READY, THREAD_RUNNING, thread_save(), THREAD_UNBLOCKING, timer_one_shot(), timer_uptime(), uptime(), and wait_block_finalize().

Referenced by exception_handler(), interrupt_handler(), note_interrupt_handler(), and sched_timer_handler().

◆ sched_is_idle()

bool sched_is_idle ( cpu_t * cpu )

Checks if the CPU is idle.

Parameters

cpu	The CPU to check.

Returns: true if the CPU is idle, false otherwise.

Definition at line 149 of file sched.c.

References sched_cpu_ctx_t::idleThread, sched_cpu_ctx_t::lock, LOCK_SCOPE, sched_cpu_ctx_t::runThread, and cpu_t::sched.

Referenced by statistics_cpu_read(), statistics_interrupt_begin(), and trampoline_c_entry().

◆ sched_nanosleep()

uint64_t sched_nanosleep ( clock_t timeout )

Puts the current thread to sleep.

Parameters

timeout The maximum time to sleep. If CLOCKS_NEVER, it sleeps forever.

Returns: On success, 0. On error, ERR and errno is set.

Definition at line 139 of file sched.c.

References sleepQueue, and WAIT_BLOCK_TIMEOUT.

Referenced by SYSCALL_DEFINE().

◆ sched_process()

process_t * sched_process ( void )

Retrieves the process of the currently running thread.

Will not increment the reference count of the returned process, as we consider the currently running thread to always be referencing its process.

Returns: The process of the currently running thread.

Definition at line 164 of file sched.c.

References NULL, thread_t::process, and sched_thread().

Referenced by const_one_mmap(), const_zero_mmap(), gop_mmap(), loader_spawn(), note_queue_write(), socket_new(), SYSCALL_DEFINE(), SYSCALL_DEFINE(), SYSCALL_DEFINE(), SYSCALL_DEFINE(), SYSCALL_DEFINE(), SYSCALL_DEFINE(), SYSCALL_DEFINE(), and SYSCALL_DEFINE().

◆ sched_process_exit()

_NORETURN void sched_process_exit ( uint64_t status )

Exits the current process.

The sched_process_exit() function terminates the currently executing process and all its threads. Note that this function will never return, instead it triggers an interrupt that kills the current thread.

Parameters

status The exit status of the process.

Definition at line 191 of file sched.c.

References INTERRUPT_DIE, NULL, panic(), thread_t::process, process_kill(), and sched_thread().

Referenced by loader_process_entry(), and SYSCALL_DEFINE().

◆ sched_process_unsafe()

process_t * sched_process_unsafe ( void )

Retrieves the process of the currently running thread without disabling interrupts.

Will not increment the reference count of the returned process, as we consider the currently running thread to always be referencing its process.

Returns: The process of the currently running thread.

Definition at line 180 of file sched.c.

References NULL, thread_t::process, and sched_thread_unsafe().

Referenced by shmem_mmap().

◆ sched_push()

void sched_push	(	thread_t *	thread,
		cpu_t *	target
	)

Pushes a thread onto a scheduling queue.

This will take ownership of the thread, so the caller should not deref it after calling this function as if a preemption occurs it could be freed by the time the function returns.

Parameters

thread	The thread to be pushed.
target	The target cpu that the thread should run on, can be `NULL` to specify the currently running cpu-

Definition at line 305 of file sched.c.

References sched_cpu_ctx_t::active, sched_thread_ctx_t::actualPriority, atomic_exchange, sched_cpu_ctx_t::lock, LOCK_SCOPE, NULL, panic(), cpu_t::sched, thread_t::sched, sched_compute_actual_priority(), sched_compute_time_slice(), sched_queues_push(), sched_should_notify(), sched_update_recent_idle_time(), smp_put(), smp_self(), THREAD_PARKED, THREAD_READY, THREAD_UNBLOCKING, timer_notify(), and timer_uptime().

Referenced by init_process_spawn(), wait_timer_handler(), wait_unblock(), and wait_unblock_thread().

◆ sched_push_new_thread()

void sched_push_new_thread	(	thread_t *	thread,
		thread_t *	parent
	)

Pushes a newly created thread onto the scheduling queue.

This will take ownership of the thread, so the caller should not deref it after calling this function as if a preemption occurs it could be freed by the time the function returns.

Parameters

thread	The thread to be pushed.
parent	The parent thread.

Definition at line 385 of file sched.c.

References sched_cpu_ctx_t::active, sched_thread_ctx_t::actualPriority, assert, atomic_exchange, sched_cpu_ctx_t::lock, LOCK_SCOPE, NULL, panic(), cpu_t::sched, thread_t::sched, sched_compute_actual_priority(), sched_compute_time_slice(), sched_find_least_loaded_cpu(), sched_queues_push(), sched_should_notify(), sched_update_recent_idle_time(), smp_put(), smp_self(), THREAD_PARKED, THREAD_READY, THREAD_UNBLOCKING, timer_notify(), and timer_uptime().

Referenced by SYSCALL_DEFINE(), and SYSCALL_DEFINE().

◆ sched_thread()

thread_t * sched_thread ( void )

Retrieves the currently running thread.

Returns: The currently running thread.

Definition at line 157 of file sched.c.

References sched_cpu_ctx_t::runThread, cpu_t::sched, smp_put(), and smp_self().

Referenced by _errno_get(), loader_process_entry(), mutex_acquire_timeout(), sched_process(), sched_process_exit(), SYSCALL_DEFINE(), SYSCALL_DEFINE(), SYSCALL_DEFINE(), SYSCALL_DEFINE(), SYSCALL_DEFINE(), SYSCALL_DEFINE(), SYSCALL_DEFINE(), SYSCALL_DEFINE(), SYSCALL_DEFINE(), SYSCALL_DEFINE(), SYSCALL_DEFINE(), SYSCALL_DEFINE(), SYSCALL_DEFINE(), SYSCALL_DEFINE(), SYSCALL_DEFINE(), SYSCALL_DEFINE(), SYSCALL_DEFINE(), SYSCALL_DEFINE(), and SYSCALL_DEFINE().

◆ sched_thread_ctx_init()

void sched_thread_ctx_init ( sched_thread_ctx_t * ctx )

Initializes a thread's scheduling context.

Parameters

ctx	The `sched_thread_ctx_t` structure to initialize.

Definition at line 69 of file sched.c.

References sched_thread_ctx_t::actualPriority, sched_thread_ctx_t::deadline, sched_thread_ctx_t::prevBlockCheck, sched_thread_ctx_t::recentBlockTime, and sched_thread_ctx_t::timeSlice.

Referenced by thread_init().

◆ sched_thread_exit()

_NORETURN void sched_thread_exit ( void )

Exits the current thread.

The sched_thread_exit() function terminates the currently executing thread. Note that this function will never return, instead it triggers an interrupt that kills the thread.

Definition at line 205 of file sched.c.

References INTERRUPT_DIE, NULL, and panic().

Referenced by SYSCALL_DEFINE().

◆ sched_thread_unsafe()

thread_t * sched_thread_unsafe ( void )

Retrieves the currently running thread without disabling interrupts.

Returns: The currently running thread.

Definition at line 175 of file sched.c.

References sched_cpu_ctx_t::runThread, cpu_t::sched, and smp_self_unsafe().

Referenced by exception_handler(), mutex_release(), note_interrupt_handler(), sched_process_unsafe(), syscall_handler(), thread_handle_page_fault(), and trampoline_c_entry().

◆ sched_yield()

void sched_yield ( void )

Yields the CPU to another thread.

The sched_yield() function voluntarily relinquishes the currently running threads time slice. Note that this does not actually schedule.

Definition at line 277 of file sched.c.

References sched_thread_ctx_t::deadline, sched_cpu_ctx_t::runThread, cpu_t::sched, thread_t::sched, smp_put(), and smp_self().

Referenced by SYSCALL_DEFINE().

Modules

Data Structures

Enumerations

Functions

Detailed Description

Enumeration Type Documentation

◆ schedule_flags_t

Function Documentation

◆ sched_cpu_ctx_init()

◆ sched_done_with_boot_thread()

◆ sched_idle_loop()

◆ sched_invoke()

◆ sched_is_idle()

◆ sched_nanosleep()

◆ sched_process()

◆ sched_process_exit()

◆ sched_process_unsafe()

◆ sched_push()

◆ sched_push_new_thread()

◆ sched_thread()

◆ sched_thread_ctx_init()

◆ sched_thread_exit()

◆ sched_thread_unsafe()

◆ sched_yield()