This class manages how processes and threads are scheduled across processors. More...

#include <Scheduler.h>

Collaboration diagram for Scheduler:

Classes
class	ActivitySample

class	ProcessLease

struct	SystemActivity

Public Member Functions
bool	initialise (Process *pKernelProcess)

void	addThread (Thread *pThread, PerProcessorScheduler &PPSched)

void	removeThread (Thread *pThread)

bool	threadInSchedule (Thread *pThread)

void	addProcess (Process *pProcess)

void	removeProcess (Process *pProcess)

void	yield ()

void	rebindThread (Thread *thread, PerProcessorScheduler &scheduler)

SystemActivity	systemActivity ()

void	recordCpuTime (const Thread &thread, CpuTimeMode mode, Time::Timestamp elapsed)

void	sampleLoadAverage ()

void	requestLoadAverageSample ()

size_t	getNumProcesses ()

MUST_USE_RESULT bool	acquireProcess (ProcessLease &lease, size_t n)

MUST_USE_RESULT bool	acquireFirstProcessOfType (ProcessLease &lease, Process::ProcessType type)

MUST_USE_RESULT bool	acquireProcessById (ProcessLease &lease, size_t id)

MUST_USE_RESULT bool	acquireProcessByUserspaceId (ProcessLease &lease, size_t id)

MUST_USE_RESULT bool	acquireThreadByTaskId (Process::ThreadLease &lease, size_t id)

MUST_USE_RESULT bool	acquireProcess (ProcessLease &lease, Process *expected)

void	waitUntilProcessRemoved (Process *expected)

Process *	getChildProcess (Process *pParent, size_t n)

void	threadStatusChanged (Thread *pThread)

Process *	getKernelProcess () const

PerProcessorScheduler *	getBootstrapProcessorScheduler () const

Static Public Member Functions
static Scheduler &	instance ()

static CpuAffinityMask	onlineAffinity ()

static size_t	affinityBytes ()

static PerProcessorScheduler *	schedulerForCpu (size_t cpu)

Private Member Functions
bool	hasActiveSyscallLocked (Service_t service) const

	NOT_COPYABLE_OR_ASSIGNABLE (Scheduler)

size_t	reserveProcessId ()

void	releaseProcessLease (Process *process)

void	drainDeferredTimeAccounting ()

Static Private Member Functions
static void	releaseActivityEntry (Process process, Thread thread)

Private Attributes
Mutex	m_ActivityLock

uint64_t	m_NextActivityAttempt = 0

bool	m_ActivitySamplePending = false

LoadAverage	m_LoadAverage

Atomic< uint64_t >	m_UserNanoseconds

Atomic< uint64_t >	m_KernelNanoseconds

Atomic< uint64_t >	m_IdleNanoseconds

List< Process *, 0 >	m_Processes

Atomic< size_t >	m_NextPid

Tree< PerProcessorScheduler , List< Thread > * >	m_PTMap

Tree< Thread , PerProcessorScheduler >	m_TPMap

Process *	m_pKernelProcess

PerProcessorScheduler *	m_pBspScheduler

Spinlock	m_SchedulerLock

WaitQueue	m_ProcessRemovalWaiters

Static Private Attributes
static Scheduler	m_Instance

Friends
class	Process

class	PerProcessorScheduler

class	SyscallManager

Detailed Description

This class manages how processes and threads are scheduled across processors.

This is the "long term" scheduler - it load balances between processors and provides the interface for adding, listing and removing threads.

The load balancing is "lazy" in that the algorithm only runs on thread addition and removal.

Definition at line 50 of file Scheduler.h.

Constructor & Destructor Documentation

◆ Scheduler()

Scheduler::Scheduler ( )

private

Definition at line 98 of file Scheduler.cc.

Member Function Documentation

◆ acquireFirstProcessOfType()

bool Scheduler::acquireFirstProcessOfType	(	ProcessLease &	lease,
		Process::ProcessType	type
	)

Pins the first enumerated process with the requested concrete type.

Definition at line 301 of file Scheduler.cc.

References Spinlock::acquire(), List< T, nodePoolSize >::begin(), Process::beginExternalLease(), List< T, nodePoolSize >::end(), m_Processes, m_SchedulerLock, and Spinlock::release().

◆ acquireProcess() [1/2]

bool Scheduler::acquireProcess	(	ProcessLease &	lease,
		Process *	expected
	)

Pins an expected pointer only if it is still in enumeration.

Comparing the pointer under the scheduler lock does not dereference it, so callers can safely validate a parent/candidate pointer which may have been concurrently removed. Any previous lease is released; failure leaves lease empty.

Definition at line 317 of file Scheduler.cc.

References Spinlock::acquire(), List< T, nodePoolSize >::begin(), Process::beginExternalLease(), List< T, nodePoolSize >::end(), m_Processes, m_SchedulerLock, and Spinlock::release().

◆ acquireProcess() [2/2]

bool Scheduler::acquireProcess	(	ProcessLease &	lease,
		size_t	n
	)

Pins the n'th process currently in operation into lease. Any previous lease is released; failure leaves lease empty.

Definition at line 275 of file Scheduler.cc.

References Spinlock::acquire(), List< T, nodePoolSize >::begin(), Process::beginExternalLease(), List< T, nodePoolSize >::count(), List< T, nodePoolSize >::end(), m_Processes, m_SchedulerLock, and Spinlock::release().

Referenced by Process::beginTermination(), MemoryPressureProcessKiller::compact(), ThreadsCommand::execute(), X64VirtualAddressSpace::mapUnlocked(), Rtc::processElapsedTime(), and Process::publish().

Here is the caller graph for this function:

◆ acquireProcessById()

bool Scheduler::acquireProcessById	(	ProcessLease &	lease,
		size_t	id
	)

Pins the process with the given scheduler-assigned ID into lease. Any previous lease is released; failure leaves lease empty.

Definition at line 340 of file Scheduler.cc.

References Spinlock::acquire(), List< T, nodePoolSize >::begin(), Process::beginExternalLease(), List< T, nodePoolSize >::end(), Process::getId(), m_Processes, m_SchedulerLock, and Spinlock::release().

◆ acquireProcessByUserspaceId()

bool Scheduler::acquireProcessByUserspaceId	(	ProcessLease &	lease,
		size_t	id
	)

Definition at line 359 of file Scheduler.cc.

◆ acquireThreadByTaskId()

bool Scheduler::acquireThreadByTaskId	(	Process::ThreadLease &	lease,
		size_t	id
	)

Pins a Linux task without nesting scheduler and process enumeration locks.

Definition at line 378 of file Scheduler.cc.

References Spinlock::acquire(), List< T, nodePoolSize >::begin(), Process::beginExternalLease(), List< T, nodePoolSize >::end(), Process::getId(), m_Processes, m_SchedulerLock, and Spinlock::release().

◆ addProcess()

void Scheduler::addProcess ( Process * pProcess )

Adds a completely constructed process to enumeration.

Definition at line 213 of file Scheduler.cc.

References Spinlock::acquire(), m_Processes, m_SchedulerLock, List< T, nodePoolSize >::pushBack(), and Spinlock::release().

Referenced by Process::publish().

Here is the caller graph for this function:

◆ addThread()

void Scheduler::addThread	(	Thread *	pThread,
		PerProcessorScheduler &	PPSched
	)

Adds a thread to be load-balanced and accounted.

Parameters

pThread	The new thread.
PPSched	The per-processor scheduler the thread will start on.

Definition at line 140 of file Scheduler.cc.

References Spinlock::acquire(), ProcessorBase::index(), Tree< K, E >::insert(), m_SchedulerLock, m_TPMap, Spinlock::release(), and Thread::setScheduler().

Referenced by ProcessorThreadAllocator::addThread(), ProcessorThreadAllocator::addThread(), Thread::Thread(), and Thread::Thread().

Here is the caller graph for this function:

◆ affinityBytes()

size_t Scheduler::affinityBytes ( )

static

Definition at line 250 of file Scheduler.cc.

◆ drainDeferredTimeAccounting()

void Scheduler::drainDeferredTimeAccounting ( )

private

Drains every currently enumerated Process's timer-accounting batch. The caller is an ordinary per-processor accounting worker.

Definition at line 190 of file Scheduler.cc.

References Spinlock::acquire(), List< T, nodePoolSize >::begin(), Vector< T >::begin(), Process::beginExternalLease(), Vector< T >::count(), Process::drainDeferredTimeAccounting(), List< T, nodePoolSize >::end(), Vector< T >::end(), Process::endExternalLease(), getNumProcesses(), m_Processes, m_SchedulerLock, Vector< T >::pushBack(), Spinlock::release(), and Vector< T >::size().

◆ getBootstrapProcessorScheduler()

PerProcessorScheduler * Scheduler::getBootstrapProcessorScheduler ( ) const

inline

Definition at line 199 of file Scheduler.h.

◆ getChildProcess()

Process * Scheduler::getChildProcess	(	Process *	pParent,
		size_t	n
	)

Returns the n'th direct child of a process.

The caller must hold the parent's child-state guard so the returned Process pointer remains valid.

Definition at line 435 of file Scheduler.cc.

References Spinlock::acquire(), List< T, nodePoolSize >::begin(), List< T, nodePoolSize >::end(), Process::getParent(), m_Processes, m_SchedulerLock, and Spinlock::release().

Referenced by Process::beginTermination().

Here is the caller graph for this function:

◆ getKernelProcess()

Process * Scheduler::getKernelProcess ( ) const

inline

Definition at line 195 of file Scheduler.h.

◆ getNumProcesses()

size_t Scheduler::getNumProcesses ( )

Returns the number of processes currently in operation.

Definition at line 268 of file Scheduler.cc.

References Spinlock::acquire(), List< T, nodePoolSize >::count(), m_Processes, m_SchedulerLock, and Spinlock::release().

Referenced by MemoryPressureProcessKiller::compact(), drainDeferredTimeAccounting(), ThreadsCommand::execute(), X64VirtualAddressSpace::mapUnlocked(), and Rtc::processElapsedTime().

Here is the caller graph for this function:

◆ hasActiveSyscallLocked()

bool Scheduler::hasActiveSyscallLocked ( Service_t service ) const

private

Caller holds m_SchedulerLock; never follows stack-owned callback records.

Definition at line 169 of file Scheduler.cc.

References Tree< K, E >::begin(), Tree< K, E >::end(), and m_TPMap.

◆ initialise()

bool Scheduler::initialise ( Process * pKernelProcess )

Initialises the scheduler.

Definition at line 113 of file Scheduler.cc.

References Vector< T >::end(), ProcessorBase::getCount(), ProcessorBase::information(), m_pBspScheduler, m_pKernelProcess, ProcessorBase::m_ProcessorInformation, List< T, nodePoolSize >::pushBack(), and ProcessorThreadAllocator::setAlgorithm().

◆ instance()

static Scheduler & Scheduler::instance ( )

inlinestatic

Get the instance of the scheduler

Definition at line 96 of file Scheduler.h.

Referenced by RequestQueue::addRequest(), Process::addThread(), ProcessorThreadAllocator::addThread(), ProcessorThreadAllocator::addThread(), Process::beginTermination(), MemoryPressureProcessKiller::compact(), File::dataChanged(), IrqHandlerRegistry::dispatchThreaded(), Rtc::drainRemoteAlarmDispatch(), ThreadsCommand::execute(), KernelElf::executeModules(), TextIO::initialise(), Rtc::initialise3(), Ps2Controller::irq(), PosixSubsystem::kill(), InputManager::mainThread(), X64VirtualAddressSpace::mapUnlocked(), Process::prepareForDestruction(), Rtc::processElapsedTime(), Process::publish(), Process::publishTerminationStatus(), Thread::publishTimeAccounting(), UsbInterruptInHandle::reset(), Process::resume(), PosixSubsystem::sendSignal(), Thread::setUnwindState(), IntervalTimer::signal(), Thread::start(), RequestQueue::startWorker(), UsbHub::suppressConnectionChanges(), Process::suspendInternal(), KernelCoreSyscallManager::syscall(), Thread::Thread(), Thread::Thread(), PerProcessorScheduler::timer(), KernelElf::unloadModules(), IrqHandlerRegistry::unregisterHandler(), KernelElf::waitForModulesToLoad(), Process::waitUntilTerminationReapableForTerminalCoordinator(), RequestQueue::work(), and Thread::~Thread().

Here is the caller graph for this function:

◆ onlineAffinity()

CpuAffinityMask Scheduler::onlineAffinity ( )

static

Definition at line 241 of file Scheduler.cc.

◆ rebindThread()

void Scheduler::rebindThread	(	Thread *	thread,
		PerProcessorScheduler &	scheduler
	)

Definition at line 260 of file Scheduler.cc.

◆ recordCpuTime()

void Scheduler::recordCpuTime	(	const Thread &	thread,
		CpuTimeMode	mode,
		Time::Timestamp	elapsed
	)

Records one interval after Thread has attributed it to its owner.

Definition at line 52 of file Scheduler-system-info.cc.

References Thread::getScheduler().

Referenced by Thread::publishTimeAccounting().

Here is the caller graph for this function:

◆ releaseActivityEntry()

void Scheduler::releaseActivityEntry	(	Process *	process,
		Thread *	thread
	)

staticprivate

Definition at line 26 of file Scheduler-system-info.cc.

◆ releaseProcessLease()

void Scheduler::releaseProcessLease ( Process * process )

private

Releases a lease through Scheduler's Process friendship.

Definition at line 186 of file Scheduler.cc.

References Process::endExternalLease().

◆ removeProcess()

void Scheduler::removeProcess ( Process * pProcess )

Removes a process.

Note: This is purely for enumeration purposes.

Definition at line 219 of file Scheduler.cc.

References Spinlock::acquire(), List< T, nodePoolSize >::begin(), Process::closeExternalLeaseAdmission(), List< T, nodePoolSize >::end(), List< T, nodePoolSize >::erase(), m_Processes, m_ProcessRemovalWaiters, m_SchedulerLock, and Spinlock::release().

Referenced by Process::prepareForDestruction().

Here is the caller graph for this function:

◆ removeThread()

void Scheduler::removeThread ( Thread * pThread )

Removes a thread from being load-balanced and accounted.

Definition at line 152 of file Scheduler.cc.

References Spinlock::acquire(), Tree< K, E >::lookup(), m_SchedulerLock, m_TPMap, Spinlock::release(), and Tree< K, E >::remove().

Referenced by Thread::~Thread().

Here is the caller graph for this function:

◆ requestLoadAverageSample()

void Scheduler::requestLoadAverageSample ( )

Coalesces the next due load sample from a scheduler tick.

Definition at line 63 of file Scheduler-system-info.cc.

References ProcessorBase::information().

Referenced by PerProcessorScheduler::timer().

Here is the caller graph for this function:

◆ reserveProcessId()

size_t Scheduler::reserveProcessId ( )

private

Reserves an ID without making a partially built Process visible.

Definition at line 178 of file Scheduler.cc.

References m_NextPid.

Referenced by Process::addThread().

Here is the caller graph for this function:

◆ sampleLoadAverage()

void Scheduler::sampleLoadAverage ( )

Called by an ordinary accounting worker after its batch is complete.

Definition at line 72 of file Scheduler-system-info.cc.

References Tree< K, E >::begin(), Process::beginExternalLease(), Thread::beginExternalLease(), Tree< K, E >::count(), Tree< K, E >::end(), Thread::getParent(), Thread::getStatus(), ProcessorBase::information(), Thread::m_Lock, m_SchedulerLock, and m_TPMap.

◆ schedulerForCpu()

PerProcessorScheduler * Scheduler::schedulerForCpu ( size_t cpu )

static

Definition at line 255 of file Scheduler.cc.

◆ systemActivity()

Scheduler::SystemActivity Scheduler::systemActivity ( )

Definition at line 33 of file Scheduler-system-info.cc.

◆ threadInSchedule()

bool Scheduler::threadInSchedule ( Thread * pThread )

Whether a thread is entered into the scheduler at all.

Definition at line 162 of file Scheduler.cc.

References Spinlock::acquire(), Tree< K, E >::lookup(), m_SchedulerLock, m_TPMap, and Spinlock::release().

◆ threadStatusChanged()

void Scheduler::threadStatusChanged ( Thread * pThread )

Definition at line 453 of file Scheduler.cc.

◆ waitUntilProcessRemoved()

void Scheduler::waitUntilProcessRemoved ( Process * expected )

Completion barrier for deferred deletion after enumeration removal.

Definition at line 412 of file Scheduler.cc.

References Spinlock::acquire(), List< T, nodePoolSize >::begin(), List< T, nodePoolSize >::end(), m_Processes, m_ProcessRemovalWaiters, m_SchedulerLock, and Spinlock::release().

◆ yield()

void Scheduler::yield ( )

Causes a manual reschedule.

Definition at line 236 of file Scheduler.cc.

References ProcessorBase::information().

Referenced by RequestQueue::addRequest(), File::dataChanged(), IrqHandlerRegistry::dispatchThreaded(), Rtc::drainRemoteAlarmDispatch(), KernelElf::executeModules(), Ps2Controller::irq(), PosixSubsystem::kill(), InputManager::mainThread(), UsbInterruptInHandle::reset(), PosixSubsystem::sendSignal(), RequestQueue::startWorker(), UsbHub::suppressConnectionChanges(), KernelCoreSyscallManager::syscall(), KernelElf::unloadModules(), IrqHandlerRegistry::unregisterHandler(), KernelElf::waitForModulesToLoad(), Process::waitUntilTerminationReapableForTerminalCoordinator(), and RequestQueue::work().

Here is the caller graph for this function:

Friends And Related Symbol Documentation

◆ PerProcessorScheduler

friend class PerProcessorScheduler

friend

Definition at line 205 of file Scheduler.h.

◆ Process

friend class Process

friend

Definition at line 204 of file Scheduler.h.

◆ SyscallManager

friend class SyscallManager

friend

Definition at line 206 of file Scheduler.h.

Member Data Documentation

◆ m_ActivityLock

Mutex Scheduler::m_ActivityLock

private

Definition at line 228 of file Scheduler.h.

◆ m_ActivitySamplePending

bool Scheduler::m_ActivitySamplePending = false

private

Definition at line 230 of file Scheduler.h.

◆ m_IdleNanoseconds

Atomic<uint64_t> Scheduler::m_IdleNanoseconds

private

Definition at line 234 of file Scheduler.h.

◆ m_Instance

Scheduler Scheduler::m_Instance

staticprivate

The Scheduler instance.

Definition at line 237 of file Scheduler.h.

◆ m_KernelNanoseconds

Atomic<uint64_t> Scheduler::m_KernelNanoseconds

private

Definition at line 233 of file Scheduler.h.

◆ m_LoadAverage

LoadAverage Scheduler::m_LoadAverage

private

Definition at line 231 of file Scheduler.h.

◆ m_NextActivityAttempt

uint64_t Scheduler::m_NextActivityAttempt = 0

private

Definition at line 229 of file Scheduler.h.

◆ m_NextPid

Atomic<size_t> Scheduler::m_NextPid

private

The next available process ID.

Definition at line 243 of file Scheduler.h.

Referenced by reserveProcessId().

◆ m_pBspScheduler

PerProcessorScheduler* Scheduler::m_pBspScheduler

private

Pointer to the BSP's scheduler.

This may be necessary for threads that need to depend on e.g. interrupts that are only coming to the BSP, and having them run on a different CPU means they cannot control things like IRQs being enabled (not good).

Definition at line 261 of file Scheduler.h.

Referenced by initialise().

◆ m_pKernelProcess

Process* Scheduler::m_pKernelProcess

private

Pointer to the kernel process.

Definition at line 252 of file Scheduler.h.

Referenced by initialise().

◆ m_Processes

List<Process*, 0> Scheduler::m_Processes

private

All the processes currently in operation, for enumeration purposes.

Definition at line 240 of file Scheduler.h.

Referenced by acquireFirstProcessOfType(), acquireProcess(), acquireProcess(), acquireProcessById(), acquireThreadByTaskId(), addProcess(), drainDeferredTimeAccounting(), getChildProcess(), getNumProcesses(), removeProcess(), and waitUntilProcessRemoved().

◆ m_ProcessRemovalWaiters

WaitQueue Scheduler::m_ProcessRemovalWaiters

private

Wakes lifecycle waiters after a Process leaves enumeration.

Definition at line 268 of file Scheduler.h.

Referenced by removeProcess(), and waitUntilProcessRemoved().

◆ m_PTMap

Tree<PerProcessorScheduler*, List<Thread*>*> Scheduler::m_PTMap

private

Map of processor->thread mappings, for load-balance accounting.

Definition at line 246 of file Scheduler.h.

◆ m_SchedulerLock

Spinlock Scheduler::m_SchedulerLock

private

Main scheduler lock for modifying internal structures.

Definition at line 264 of file Scheduler.h.

Referenced by acquireFirstProcessOfType(), acquireProcess(), acquireProcess(), acquireProcessById(), acquireThreadByTaskId(), addProcess(), addThread(), drainDeferredTimeAccounting(), getChildProcess(), getNumProcesses(), removeProcess(), removeThread(), sampleLoadAverage(), threadInSchedule(), and waitUntilProcessRemoved().

◆ m_TPMap

Tree<Thread*, PerProcessorScheduler*> Scheduler::m_TPMap

private

Map of thread->processor mappings.

Definition at line 249 of file Scheduler.h.

Referenced by addThread(), hasActiveSyscallLocked(), removeThread(), sampleLoadAverage(), and threadInSchedule().

◆ m_UserNanoseconds

Atomic<uint64_t> Scheduler::m_UserNanoseconds

private

Definition at line 232 of file Scheduler.h.

The documentation for this class was generated from the following files:

Classes

Public Member Functions

Static Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Static Private Attributes

Friends

Detailed Description

Constructor & Destructor Documentation

◆ Scheduler()

Member Function Documentation

◆ acquireFirstProcessOfType()

◆ acquireProcess() [1/2]

◆ acquireProcess() [2/2]

◆ acquireProcessById()

◆ acquireProcessByUserspaceId()

◆ acquireThreadByTaskId()

◆ addProcess()

◆ addThread()

◆ affinityBytes()

◆ drainDeferredTimeAccounting()

◆ getBootstrapProcessorScheduler()

◆ getChildProcess()

◆ getKernelProcess()

◆ getNumProcesses()

◆ hasActiveSyscallLocked()

◆ initialise()

◆ instance()

◆ onlineAffinity()

◆ rebindThread()

◆ recordCpuTime()

◆ releaseActivityEntry()

◆ releaseProcessLease()

◆ removeProcess()

◆ removeThread()

◆ requestLoadAverageSample()

◆ reserveProcessId()

◆ sampleLoadAverage()

◆ schedulerForCpu()

◆ systemActivity()

◆ threadInSchedule()

◆ threadStatusChanged()

◆ waitUntilProcessRemoved()

◆ yield()

Friends And Related Symbol Documentation

◆ PerProcessorScheduler

◆ Process

◆ SyscallManager

Member Data Documentation

◆ m_ActivityLock

◆ m_ActivitySamplePending

◆ m_IdleNanoseconds

◆ m_Instance

◆ m_KernelNanoseconds

◆ m_LoadAverage

◆ m_NextActivityAttempt

◆ m_NextPid

◆ m_pBspScheduler

◆ m_pKernelProcess

◆ m_Processes

◆ m_ProcessRemovalWaiters

◆ m_PTMap

◆ m_SchedulerLock

◆ m_TPMap

◆ m_UserNanoseconds