Deep inspection of scheduler (2) -- computing next wake up time

Here, we are going to talk about the computation of the scheduler. As mentioned last blog, the next_wake is the essential variable that determines the next wake-up of the scheduler. So we will check where this variable is changed.

Code Segment 1 (next_wake is changed in the task scan):
        for (task_ID=0; task_ID < NRK_MAX_TASKS; task_ID++){
                ......
                if(nrk_task_TCB[task_ID].task_state == SUSPENDED){
                        ......          
                        if(nrk_task_TCB[task_ID].next_wakeup!=0 &&
                           nrk_task_TCB[task_ID].next_wakeup<next_wake )
next_wake=nrk_task_TCB[task_ID].next_wakeup;
                }
        }
From this segment, we conclude that next_wake is related with user-defined task's next wake-up time, since only user-defined task will have SUSPENDED task state and idle task won't. However, how's the next_wake changed?
Code Segment (in the task scanning loop)
        if( nrk_task_TCB[task_ID].task_ID!=NRK_IDLE_TASK_ID &&
             nrk_task_TCB[task_ID].task_state!=FINISHED ){
if(nrk_task_TCB[task_ID].next_wakeup >= _nrk_prev_timer_val)
nrk_task_TCB[task_ID].next_wakeup-=_nrk_prev_timer_val;
else 
nrk_task_TCB[task_ID].next_wakeup=0;
                ......
        }
The scenario described here by the code is that if the next_wakeup time line (which is defined initially by the nrk_create_taskset) is behind current task ending line plus 2ms, the next_wakeup time line should move forward by _nrk_prev_timer_val, otherwise, the task should be waken up immediately. Then the scheduler would execute this task soon. (Refer to last blog to see how does this happen)  However this may result in unexpected bugs if the next_wakeup is smaller than _nrk_prev_timer_val but not so much. Next blog would talk about these potential bugs in the scheduler.

Code Segment 2 (next_wake is changed in non-idle and idle tasks respectively):
In next executable non-idle task
  if(nrk_task_TCB[task_ID].cpu_reserve!=0 && 
            nrk_task_TCB[task_ID].cpu_remaining<MAX_SCHED_WAKEUP_TIME){
if(next_wake>nrk_task_TCB[task_ID].cpu_remaining)
next_wake=nrk_task_TCB[task_ID].cpu_remaining;
        }else{ 
if(next_wake>MAX_SCHED_WAKEUP_TIME)    
                        next_wake=MAX_SCHED_WAKEUP_TIME; 
}
Here, we know that next_wake is also related with task's cpu remaining time. First, we have to notice that task's cpu_reserve should be initialized to non-zero. And then we have to know that task_ID here is the highest priority task ID. Additionally, the next_wake here is the closest next wake-up time line. Therefore, the code segment here indicates that next wake-up time is not allowed to exceed the highest priority task's cpu remaining time. It means that if next executable task is not idle, it has to be interrupted by the scheduler at the moment that the highest priority task's cpu remaining time is consumed out. This is actually undesired wake-up and may result in unexpected bugs.  Next blog would talk about these potential bugs in the scheduler.

In idle task

        if(next_wake>NRK_SLEEP_WAKEUP_TIME) {
if(next_wake-NRK_SLEEP_WAKEUP_TIME
                    <MAX_SCHED_WAKEUP_TIME){
if(next_wake-NRK_SLEEP_WAKEUP_TIME
                            <NRK_SLEEP_WAKEUP_TIME)
next_wake=NRK_SLEEP_WAKEUP_TIME-1;
else
next_wake=next_wake-NRK_SLEEP_WAKEUP_TIME;
}else if(next_wake>NRK_SLEEP_WAKEUP_TIME
                            +MAX_SCHED_WAKEUP_TIME
next_wake=MAX_SCHED_WAKEUP_TIME;
else 
next_wake=MAX_SCHED_WAKEUP_TIME
                                           -NRK_SLEEP_WAKEUP_TIME;
}
Since idle task has the lowest priority, we don't need to worry about that some other task would preempt it. We see that next_wake has to be larger than 10ms (which is represented by NRK_SLEEP_WAKEUP_TIME), otherwise next_wake is determined by Code Segment 1. Once the condition is satisfied, the scheduler would wake up 10ms before the closest next user-defined task. (because next_wake is determined by Code Segment 1 before) Therefore, we see that idle task plays a role here in making the processor sleep deep, just as mentioned before in last blog.

Generally, the computation here includes:
1. computes all the next_wakeups of tasks and pick the closest one as the next_wake which determines the next wake-up time of the scheduler.
2. Get the highest priority task ID (task_ID).
3. (1) If the task_ID indicates a non-idle task and cpu_reserve is initialized as non-zero, next_wake is set to cpu_remaining. (2) If the task_ID indicates an idle task, next_wake is 10ms before the closest next user-defined task.
4. _nrk_set_next_wakeup(next_wake) starts next round of scheduling.

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.

Notes about task execution and scheduler

Before talking about task scheduler, I am gonna inspect how the task is executed first.

How the task progresses?

First, you need to initialize the system by calling  nrk_init() where an idle task is created. The idle task is used in task scheduler for making tasks sleep deep (I will talk about it later in the scheduler section). And then you should create the task by calling nrk_create_taskset(), where task period, priority, CPU reserved time etc. are defined and especially the user-defined task is pushed into the task stack.

And then, nrk_start() starts executing all the tasks in the task stack. In nrk_start(), you should pay attention to two methods -- nrk_target_start() and nrk_start_high_ready_task(). nrk_target_start() (defined in nrk_cpu.c) initializes timers (very important to the system because all the tasks are executed based on the timer) and nrk_start_high_ready_task() starts the ready task with the highest priority though it is defined hardware specific assembly file. Initially, all the tasks are ready so the task with the highest priority would be executed first.

Since the task is started, the processor would process the task. There are two points required high attention. 1. Task should not exceed the period defined before. 2. At the end of the task, nrk_wait_until_next_period() (defined in nrk_task.c) must be called. This method would bring you into the task scheduler.

How the scheduler works?

In nrk_wait_until_next_period(), the task scheduler would be called 2ms after the task finishes its job.
Code segment:

      ......
      timer += TIME_PAD; // TIMER_PAD = 2 and timer = nrk_os_timer_get();
      _nrk_prev_timer_val = timer;
      _nrk_set_next_wakeup (timer);
      ......
      _nrk_wait_for_scheduler ();
      ......

_nrk_prev_timer_val records task execution time plus 2ms and this value would be used in the scheduler to calculate next wake-up time. (we will talk about the computation in next blog) _nrk_set_next_wakeup (timer) would make the OS timer generate an interrupt 2ms later. _nrk_wait_for_scheduler () would make the task into the sleep mode. It should be noticed that the sleep mode is not the most power-saved. The deep sleep which indeed saves power would be made by the task scheduler.

However, the scheduler is hardware, namely timer, triggered. Looking into nrk_task.c, you would find that _nrk_scheduler() is called in the _nrk_timer_tick() which is called by the interrupt caused by the timer. That is to say, it is not the _nrk_wait_for_scheduler () trigger the scheduler but instead the _nrk_set_next_wakeup (timer).

Once the scheduler is on work, the idle task defined in  nrk_init() is used for making the process into deep sleep. Figure 1 shows it.

Fig 1

The yellow line indicates the task execution time. The purple line indicates the scheduler execution time. And the green line indicates the sleep mode time. It is obvious that the scheduler is called three times between two periods of the task. Actually, the processor calls the idle task at the first. The scheduler determines to start the task again at the second time since the scope shows that the processor enters the sleep mode again which is executed in the user-defined task. And the scheduler finally decides to start the task immediately since the task should start its new period. And also, you can see that during the first two callings the processor is not in the sleep mode. Actually, at that time, processor is in deep sleep. 

There would be two questions about the scheduler.

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?

Notes about timer configuration

To test how the timer works, we design a task with period of 50ms and execution time of 20.5ms.
First let's see two screen shots from the scope. The orange line indicates the execution time. The green line indicates the sleep time. And the purple line indicates the task scheduler is called.

Fig. 1 unexpected result

Fig. 2 expected result

From these two figures, we can conclude that task is not activated in time in the figure 1 and it seems that task is overdue the first wake-up time and the OS timer  wraps back to the wake-up point. (timer counts to 255, back to 0 and then to the wake-up time)

Then let's look at the code. The first figure is using code as following,

Code segment:      _nrk_os_timer_set(24);

                               nrk_wait_until_next_period();

And the second figure is using code as following,

Code segment:      _nrk_os_timer_set(24);

                               do {

                                    NOP();

                               } while (--timeout); // timeout is initialized as 200

                               nrk_wait_until_next_period();

We can see the only difference between these two segments is the delay used by the second one which gives us the expected result. How does this happen? We have to look up what the data sheet says about the timer.

Firstly, the timer is working under the CTC mode. In CTC mode the counter is cleared to zero when

the counter value (TCNTn) matches either the OCRnA. In nano-rk, _nrk_set_next_wakeup() is used for setting OCRnA and  _nrk_set_os_timer() is used for setting TCNTn. So the OS timer starts from 0 and an interrupt happens once it reaches the value of OCRnA. What if the OS timer is manually set to a value that may be larger than OCRnA? 

The data sheet says: "Writing to the TCNTn Register blocks (removes) the Compare Match on the following timer clock. Modifying the counter (TCNTn) while the counter is running, introduces a risk of missing a Compare Match between TCNTn and the OCRnA Registers." (Page 121) Once a match is missing, the counter would wrap back to the match which means unexpected 255ms may be introduced just as Fig 1 shows.

Then the question is why the code works fine when a loop is introduced? The data sheet says: "When writing to one of the registers TCNTn, OCRnX, or TCCRnX, the value is transferred to a temporary register, and latched after two positive edges on TOSC1." So when _nrk_os_timer_set(24) is called, the value of timer is not immediately set to 24 (which is verified by observing the minicom). However, in nrk_wait_until_next_period() the first wake-up time is set to 2ms after current timer value. Therefore, the next wake-up time is unfortunately set to 22ms which is in advance of 24ms. A match is missed and thus figure 1 is the output which is undesired.

Getting started

Going to start writing technical document here