EDF Scheduler

Collaboration diagram for EDF Scheduler:

Files
file	scheduleredfimpl.h
	EDF Scheduler Implementation.

Data Structures
struct	Scheduler_EDF_Context
struct	Scheduler_EDF_Node
	Scheduler node specialization for EDF schedulers. More...

Macros
#define	SCHEDULER_EDF_ENTRY_POINTS
	Entry points for the Earliest Deadline First Scheduler. More...
#define	SCHEDULER_EDF_PRIO_MSB   0x80000000
	This is just a most significant bit of Priority_Control type. More...

Enumerations
enum	Scheduler_EDF_Queue_state { SCHEDULER_EDF_QUEUE_STATE_NOT_PRESENTLY, SCHEDULER_EDF_QUEUE_STATE_YES, SCHEDULER_EDF_QUEUE_STATE_NEVER_HAS_BEEN }
	This enumeration distiguishes state of a thread with respect to the ready queue.

Functions
void	_Scheduler_EDF_Initialize (const Scheduler_Control *scheduler)
	Initialize EDF scheduler. More...
void	_Scheduler_EDF_Block (const Scheduler_Control *scheduler, Thread_Control *the_thread)
	Removes thread from ready queue. More...
void	_Scheduler_EDF_Schedule (const Scheduler_Control *scheduler, Thread_Control *the_thread)
	Sets the heir thread to be the next ready thread in the rbtree ready queue. More...
void	_Scheduler_EDF_Node_initialize (const Scheduler_Control *scheduler, Thread_Control *the_thread)
	Initializes an EDF specific scheduler node of the_thread. More...
void	_Scheduler_EDF_Update_priority (const Scheduler_Control *scheduler, Thread_Control *the_thread, Priority_Control new_priority)
	Updates position in the ready queue of the_thread. More...
Scheduler_Void_or_thread	_Scheduler_EDF_Unblock (const Scheduler_Control *scheduler, Thread_Control *the_thread)
	Adds the_thread to the scheduling decision. More...
Scheduler_Void_or_thread	_Scheduler_EDF_Change_priority (const Scheduler_Control *scheduler, Thread_Control *the_thread, Priority_Control new_priority, bool prepend_it)
Scheduler_Void_or_thread	_Scheduler_EDF_Yield (const Scheduler_Control *scheduler, Thread_Control *the_thread)
	invoked when a thread wishes to voluntarily transfer control of the processor to another thread with equal deadline. More...
int	_Scheduler_EDF_Priority_compare (Priority_Control p1, Priority_Control p2)
	Explicitly compare absolute dedlines (priorities) of threads. More...
void	_Scheduler_EDF_Release_job (const Scheduler_Control *scheduler, Thread_Control *the_thread, uint32_t deadline)
	Called when a new job of task is released. More...
RTEMS_INLINE_ROUTINE Scheduler_EDF_Context *	_Scheduler_EDF_Get_context (const Scheduler_Control *scheduler)
RTEMS_INLINE_ROUTINE Scheduler_EDF_Node *	_Scheduler_EDF_Thread_get_node (Thread_Control *the_thread)
RBTree_Compare_result	_Scheduler_EDF_Compare (const RBTree_Node *n1, const RBTree_Node *n2)
RTEMS_INLINE_ROUTINE void	_Scheduler_EDF_Enqueue (const Scheduler_Control *scheduler, Thread_Control *the_thread)
RTEMS_INLINE_ROUTINE void	_Scheduler_EDF_Extract (const Scheduler_Control *scheduler, Thread_Control *the_thread)
RTEMS_INLINE_ROUTINE void	_Scheduler_EDF_Schedule_body (const Scheduler_Control *scheduler, Thread_Control *the_thread, bool force_dispatch)

Detailed Description

Macro Definition Documentation

SCHEDULER_EDF_ENTRY_POINTS

#define SCHEDULER_EDF_ENTRY_POINTS

Value:

{ \
    _Scheduler_EDF_Initialize,       /* initialize entry point */ \
    _Scheduler_EDF_Schedule,         /* schedule entry point */ \
    _Scheduler_EDF_Yield,            /* yield entry point */ \
    _Scheduler_EDF_Block,            /* block entry point */ \
    _Scheduler_EDF_Unblock,          /* unblock entry point */ \
    _Scheduler_EDF_Change_priority,  /* change priority entry point */ \
    SCHEDULER_OPERATION_DEFAULT_ASK_FOR_HELP \
    _Scheduler_EDF_Node_initialize,  /* node initialize entry point */ \
    _Scheduler_default_Node_destroy, /* node destroy entry point */ \
    _Scheduler_EDF_Update_priority,  /* update priority entry point */ \
    _Scheduler_EDF_Priority_compare, /* compares two priorities */ \
    _Scheduler_EDF_Release_job,      /* new period of task */ \
    _Scheduler_default_Tick,         /* tick entry point */ \
    _Scheduler_default_Start_idle    /* start idle entry point */ \
    SCHEDULER_OPERATION_DEFAULT_GET_SET_AFFINITY \
  }

Entry points for the Earliest Deadline First Scheduler.

SCHEDULER_EDF_PRIO_MSB

#define SCHEDULER_EDF_PRIO_MSB   0x80000000

This is just a most significant bit of Priority_Control type.

It distinguishes threads which are deadline driven (priority represented by a lower number than SCHEDULER_EDF_PRIO_MSB) from those ones who do not have any deadlines and thus are considered background tasks.

Referenced by _Scheduler_EDF_Priority_compare(), and _Scheduler_EDF_Release_job().

Function Documentation

_Scheduler_EDF_Block()

void _Scheduler_EDF_Block	(	const Scheduler_Control *	scheduler,
		Thread_Control *	the_thread
	)

Removes thread from ready queue.

This routine removes the_thread from the scheduling decision, that is, removes it from the ready queue. It performs any necessary scheduling operations including the selection of a new heir thread.

Parameters

[in]	scheduler	The scheduler instance.
[in]	the_thread	is the thread to be blocked.

_Scheduler_EDF_Initialize()

void _Scheduler_EDF_Initialize

(

const Scheduler_Control *

scheduler

)

Initialize EDF scheduler.

This routine initializes the EDF scheduler.

Parameters

[in]

scheduler

The scheduler instance.

_Scheduler_EDF_Node_initialize()

void _Scheduler_EDF_Node_initialize	(	const Scheduler_Control *	scheduler,
		Thread_Control *	the_thread
	)

Initializes an EDF specific scheduler node of the_thread.

Parameters

[in]	scheduler	The scheduler instance.
[in]	the_thread	being initialized.

_Scheduler_EDF_Priority_compare()

int _Scheduler_EDF_Priority_compare	(	Priority_Control	p1,
		Priority_Control	p2
	)

Explicitly compare absolute dedlines (priorities) of threads.

This routine explicitly compares absolute dedlines (priorities) of threads. In case of EDF scheduling time overflow is taken into account.

Return values

>0	for p1 > p2; 0 for p1 == p2; <0 for p1 < p2.

References _Watchdog_Ticks_since_boot, and SCHEDULER_EDF_PRIO_MSB.

_Scheduler_EDF_Release_job()

void _Scheduler_EDF_Release_job	(	const Scheduler_Control *	scheduler,
		Thread_Control *	the_thread,
		uint32_t	deadline
	)

Called when a new job of task is released.

This routine is called when a new job of task is released. It is called only from Rate Monotonic manager in the beginning of new period.

Parameters

[in]	scheduler	The scheduler instance.
[in]	the_thread	is the owner of the job.
[in]	deadline	of the new job from now. If equal to 0, the job was cancelled or deleted, thus a running task has to be suspended.

References _Thread_Set_priority(), _Watchdog_Ticks_since_boot, Thread_Start_information::initial_priority, SCHEDULER_EDF_PRIO_MSB, and Thread_Control::Start.

_Scheduler_EDF_Schedule()

void _Scheduler_EDF_Schedule	(	const Scheduler_Control *	scheduler,
		Thread_Control *	the_thread
	)

Sets the heir thread to be the next ready thread in the rbtree ready queue.

This kernel routine sets the heir thread to be the next ready thread in the rbtree ready queue.

Parameters

[in]	scheduler	The scheduler instance.
[in]	the_thread	being scheduled.

_Scheduler_EDF_Unblock()

Scheduler_Void_or_thread _Scheduler_EDF_Unblock	(	const Scheduler_Control *	scheduler,
		Thread_Control *	the_thread
	)

Adds the_thread to the scheduling decision.

This routine adds the_thread to the scheduling decision, that is, adds it to the ready queue and updates any appropriate scheduling variables, for example the heir thread.

Parameters

[in]	scheduler	The scheduler instance.
[in]	the_thread	will be unblocked.

_Scheduler_EDF_Update_priority()

void _Scheduler_EDF_Update_priority	(	const Scheduler_Control *	scheduler,
		Thread_Control *	the_thread,
		Priority_Control	new_priority
	)

Updates position in the ready queue of the_thread.

This routine updates position in the ready queue of the_thread.

Parameters

[in]	scheduler	The scheduler instance.
[in]	the_thread	will have its scheduler specific information structure updated.
[in]	new_priority	is the desired new priority.

_Scheduler_EDF_Yield()

Scheduler_Void_or_thread _Scheduler_EDF_Yield	(	const Scheduler_Control *	scheduler,
		Thread_Control *	the_thread
	)

invoked when a thread wishes to voluntarily transfer control of the processor to another thread with equal deadline.

This routine is invoked when a thread wishes to voluntarily transfer control of the processor to another thread in the queue with equal deadline. This does not have to happen very often.

This routine will remove the specified THREAD from the ready queue and place it back. The rbtree ready queue is responsible for FIFO ordering in such a case.

Parameters

[in]	scheduler	The scheduler instance.
[in,out]	the_thread	The yielding thread.