Deep inspection of scheduler (1) -- scheduling flow

We leave two questions in last blog. We are gonna answer them here. First, we repeat the question:

1. How the scheduler knows or computes the next wake-up time for the idle and non-idle task?

2. How the scheduler tell the processor to wake up the non-idle task from the sleep mode? 

At first glance, we will see the following code at the end of scheduler:
Code Segment:
         ......
         _nrk_set_next_wakeup(next_wake); // scheduler would be called next_wake(ms) later
         ......
        nrk_start_high_ready_task(); // scheduler would start the ready task with the highest priority


Therefore, the essential thing in the scheduler is  the variable of next_wake which determines when the tasks would be scheduled again. Given this, we answer the first question by discussing about variable of next_wake and the second question by exploring how the task becomes the highest priority one.

The second question which refers to the scheduling flow may help us understanding the scheduler much more easily. Therefore, I am going to talk about the flow first.

Given that each task has to call nrk_wait_unit_next_period() at the end, we look into this method first and find that there are three important things that may be used in the scheduler (Explanation is made in the comments).
Code Segment:
        ......  
        nrk_cur_task_TCB->suspend_flag = 1; //current task is suspended
        ......

        timer += TIME_PAD; // timer records current OS timer value and TIME_PAD equals 2
        _nrk_prev_timer_val = timer; // used to compute next wake-up time in scheduler
        _nrk_set_next_wakeup (timer); // the scheduler would be called 2ms later
        ......

Then we look into the scheduler. The first thing scheduler does is to check the suspending flag of current task. If current task is suspended, the scheduler would remove the task from the ready queue that means once the user-defined task calls the scheduler it would be removed from the ready queue immediately.
Code Segment:
        if(nrk_cur_task_TCB->suspend_flag==1 && nrk_cur_task_TCB->task_state!=FINISHED){
                ......// here the task state would be changed
nrk_rem_from_readyQ(nrk_cur_task_TCB->task_ID);
}
Given the current non-idle task is removed, nrk_start_high_ready_task() would invoke other user-defined task if any. In the special case where there is only one user-defined task, this method would have to call the idle task which has the lowest priority by default.


Then, a new question may be raised intuitively: how would the scheduler add back the removed task to the ready queue? When continuing exploring the code, we find that the scheduler would scan all the tasks and in the scanning the removed task may be added back to the ready queue.
Code Segment:

        ......
        if (nrk_task_TCB[task_ID].task_state == SUSPENDED ) {
if (nrk_task_TCB[task_ID].next_wakeup == 0) {
                        ......
                        nrk_task_TCB[task_ID].suspend_flag=0;

                        if(nrk_task_TCB[task_ID].num_periods==1) {
                                ......
nrk_add_to_readyQ(task_ID);
}else{// if task has to wake up several period later, there is no need to add it back
                ......
                }
        }
Here, we can see that three conditions have to be satisfied before the task is added back to the ready queue. Intuitively, the task state must be SUSPENDED, since when the task calls the scheduler by nrk_wait_unit_next_period(), the  suspend_flag variable is set to 1 which would make task_state SUSPENDED at the beginning of the scheduler. And then the ready task should be waken up immediately, that is, next_wakeup would be 0. However, the next_wakeup variable does not count number of periods, so we have to check the number of periods and make sure that the task should wake up next period. Once the task is added back to the ready queue, nrk_start_high_ready_task() would decide which to be executed given that there are several tasks in the queue.


Generally, the scheduling flow goes like this,
1. Remove current task if it is suspended.
2. add task back to the ready queue if the task should be executed immediately (this process usually happens several scheduling rounds later)
3. start the highest priority task in the ready queue.

Though the process is simple, we have to determine when to wake up the scheduler. Waking up scheduler once is obviously not enough for adding task back to the ready queue, because when the scheduler is first called, its next_wakeup variable seldom becomes 0. As shown in Fig 1 on last blog, the scheduler would be called 3 times between the executions of one task.

Therefore, the first question has to be answered. We are gonna talk about it next blog.