When a task is created,the thread corresponding to the task is created and set in a DORMANT mode.
When user calls rtems_task_create, the function calls _Thread_Initialize() which eventually sets the state of the thread to the DORMANT state:
the_thread->current_state = STATES_DORMANT;
where the STATES_DORMANT is defined as:
/** This macro corresponds to a task being created but not yet started. */
#define STATES_DORMANT 0x80000000
_Thread_Initialize() also calls the scheduler operation corresponding to initializing a node.
After this, when task is started, the thread and the node corresponding to the thread are unblocked
The node is unblocked since it was set (threadinitialize.c -> … -> schedulersmpimpl.h) in the blocked state while it was intialized for the thread at the time of task creation.
rtems_task_start calls the function _Thread_Start which calls _Thread_Clear_state_locked with STATES_ALL_SET which changes the state of the thread to STATES_READY by clearing ( See threadclearstate.c then _States_Clear which is called with the parameters 0x80000000 and all 1s, so eventually all the bits are zeroed) all the bits of the state of thread.
_Thread_Start also calls _Scheduler_Unblock which acquires the lock on scheduler context (so that no other code tries to use the scheduler operations at the same time) and calls the unblock operation. Note that the unblock operation of a scheduler is one of its entry point operation, which means that the unblock function corresponding to the scheduler would be called, which for example would be _Scheduler_EDF_SMP_Unblock for EDF SMP Scheduler.
This is the how a task starts using the scheduler to get scheduled on a processor!
Now, most (all) of the SMP schedulers (ex. EDF SMP) in RTEMS use the functions defined in schedulersmpimpl.h since by using those functions the SMP schedulers can efficiently support the thread helping protocols (read more about it here) defined by Prof. Burns.
So, when we continue the path of a thread getting scheduled on a processor, unblock operation for EDF SMP is _Scheduler_EDF_SMP_Unblock() which calls _Scheduler_SMP_Unblock.
The _Scheduler_SMP_Unblock calls _Scheduler_Unblock_node which sets the state of the thread to THREAD_SCHEDULER_READY, and then the _Scheduler_SMP_Unblock calls the EDF_SMP_enqueue which calls the _Scheduler_SMP_Enqueue function.
The _Scheduler_SMP_Enqueue function calls the get_lowest_function() of the scheduler to find the lowest scheduled scheduler node that our newly arrived thread could replace.
So, this justifies the selection of _Scheduler_strong_APA_Get_lowest_scheduled as the place where we would implement our BFS algorithm for task arrival (Paper page 5) since we are trying to find a node with the lowest priority (maximum priority number) that we could replace. We can write recursive code to find the eligible node on an eligible processor that can be shifted to accomodate this node/thread (according to the paper).
After getting the lowest priority eligible node that can be replaced, we check if the lowest priority node has a higher priority than our current newly arrived thread. In case it has a higher priority, we set the node state to ready and initiate (initiated in the calling function of _Scheduler_SMP_Enqueue) ask for help for the node (since the node is ready but waiting for execution and would benefit from executing on some other eligible processor).
In the other case where our thread has a higher priority than the lowest priority eligible node, the function _Scheduler_SMP_Enqueue_to_scheduled is called by passing the lowest scheduled node and our current node and thread as parameters to enqueue the current node of the newly arrived thread in the chain of scheduled nodes.
Inside _Scheduler_SMP_Enqueue_to_scheduled, our newly arrived thread preempts the processor of the lowest ready node and the processor is allocated to the newly arrived thread.
Now, moving on to the second algorithm from the paper, BFS Algorithm for task departure.
When a task is suspended/blocked by calling rtems_task_suspend, we are basically asking the task to leave the cpu and give way to a higher priority task. So this gives us a hint that the alogorithm from the paper must be implemented somewhere in the call stack of the rtems_task_suspend function.
rtems_task_suspend sets the state of the thread corresponding to the task as STATES_SUSPENDED. Eventually while setting the state of the thread, if the previous state of the thread was READY (note that task can be ready, waiting or suspended. A ready task progress further when the thread corresponding to it is allocated a CPU ), the _Scheduler_Block function is called.
After locking the scheduler context, the _Scheduler_Block function calls the block function corresponding to the entry point function block of the scheduler that is being used.
For EDF SMP scheduler, the _Scheduler_EDF_SMP_Block simply calls the _Scheduler_SMP_Block. The latter function removes the node from the chain of scheduled list and schedules the highest ready node eligible to run on the processor that our blocked node was running on.
The _Scheduler_SMP_Schedule_highest_ready calls the get_highest_ready function implemented by our scheduler (like EDF SMP or Strong APA) while passing the scheduler context and the node that we have blocked as parameters so that we get a scheduler node with the highest priority ready to run on the processor that our newly blocked node was running on.
This justifies the choice of get_highest_ready() as the function to be chosen to implement the BFS Algorithm for task departure, as it exactly resembles the description of the function in the paper: We have an empty processor (since a task just left) and we are trying to find a task to schedule on that processor.
After that, we allocate the processor to the highest ready eligible node.
Whoow!
Such a long post. Thanks for staying with me 🙂
Richi's Journey with rtems 