CSC560: Design and Analysis of Real Time Systems

In this page we will describe how the RTOS determines the next task to run. It can handle two very important kind of tasks. They are:

1. periodic tasks, and
2. one-shot tasks.

Periodic tasks are repeated, e.g., once every 100 ms and often called time triggered tasks. One-shot tasks are performed once and often called event triggered. One shot tasks include interrupt handling, RTOS system calls, etc. These tasks are often very urgent, therefore, requires immediate attention from the CPU.

This RTOS implements fixed priority pre-emptive scheduling. Scheduling takes place:

• at an RTOS tick, and when
• a task voluntarily gives up the CPU,
• a system task is created,
• a system or an rr task waits for an event,
• a task (usually, an ISR) generates a signal for an event, and
• a task (usually a system or an rr task) finishes.

We explain this with the help of Figure 1. This RTOS runs a loop called kernel main loop. Inside the main loop user tasks are executed at an appropriate place (yellow rectangle). A currently running task generates an appropriate request to the kernel and gives up the CPU with a function call to any one of the Task_Next, Task_Terminate, Event_Wait, Event_Wait_Next. Note that Task_Terminate is automatically called when a task is finished; see Context Creation. In addition, the RTOS timer generates a signal at every 5 ms that also results in a call to the scheduler. An interrupt service routine may decide to generate a signal and enter the kernel instead of returning to the interrupted task. We will talk more about this in Section IPC.

static void kernel_main_loop()
{
	while(1){
		kernel_dispatch();
		exit_kernel();
		
		kernel_handle_request();
	}
}
				

The listing above shows the kernel_main_loop function. A context switch to a user task chosen by the scheduler takes place at the exit_kernel function. We will now explain what happens in the kernel handle request and kernel dispatch blocks.

Kernel handles task requests in the kernel_handle_request function. Many of these request handling results in the kernel_dispatch function to schedule a new task. These requests are:

• RTOS ticks,
• Task Next,
• Task Create System,
• Task Terminate,
• Event Wait (Next), and
• Event (Async) Signal.

The kernel returns the task resource to the dead pool queue when a task finishes. This queue maintains a list of free task resources. Resources for newly created tasks are provided from the head of this queue. Therefore, no dynamic memory allocation is needed. We will talk more about this in Section Memory Management. Notice that the Idle task never terminates.

We will now describe the main four blocks of this function.

At every 5 ms the RTOS generates a timer interrupt. The scheduler then needs to decide which task to pick next to give its share of the CPU. A running system task will continue to run until its completion. An RTOS tick will not pick any other task. Also, a running periodic task will not be pre-empted if the task has not exhausted its allowed number of RTOS ticks given by WCET (worst-case execution time). If a periodic task is still running after it has used up its allowed RTOS tick time the RTOS aborts with an appropriate error message and kernel trace. A running RR task is not pre-empted if it has not used up two RTOS ticks. It will be pre-empted and queued to the back of the rr_queue if it has been executed for two RTOS ticks. The kernel dispatcher will only select a task at an RTOS tick if the idle task was running at that moment or the running status of the current task has been changed by the kernel_request_handler to a non-running status (e.g., waiting, ready).

++current_ticks;
if (cur_task->task_level == RR && 
	cur_task->task_state == RUNNING)
{
	if (cur_task->remaining_ticks > 0){
		cur_task->remaining_ticks--;
	}
	
	if (cur_task->remaining_ticks == 0 && 
		cur_task->interrupted_time > 0)
	{
		cur_task->remaining_ticks = 1;
		cur_task->interrupted_time = 0;
	}else if (cur_task->remaining_ticks == 0){
		cur_task->task_state = READY;
		push_back(&rr_queue, cur_task);
	}
} else if (cur_task->task_level == PERIODIC && 
		cur_task->task_state == RUNNING)
{
	if (cur_task->remaining_ticks > 0){
		cur_task->remaining_ticks--;
	}
	if (cur_task->remaining_ticks == 0 && 
		cur_task->interrupted_time > 0)
	{
		cur_task->remaining_ticks = 1;
		cur_task->interrupted_time = 0;
	}else if (cur_task->remaining_ticks == 0){
		/* Error: Periodic task exceeded wcet */
		/* Hard REAL TIME */
		kernel_error = EXCEEDED_WCET;
		OS_Abort();
	}
}
temp = periodic_queue.head;
while (temp != NULL){
	//if (temp->time_to_arrive_ticks >0){
		temp->time_to_arrive_ticks--;
	//}
	temp = temp->next_task;
}
				

The listing above shows the code that gets executed when an RTOS tick occurs. We, next, describe what happens when a task volantarily gives up the CPU.

In this RTOS, a periodic task is defined with the following parameters:

• period,
• start time, and
• worst-case execution time,

with the condition that the worst-case execution time is smaller than the period. The following listing shows the function prototype that creates a periodic task.

int   Task_Create_Period(void (*f)(void), int arg, unsigned int period, unsigned int wcet, unsigned int start);				
				

Following listing shows how a periodic task is created with the function prototype. This periodic task has a period of 160 ms with worst-case execution time of 20 and starts at time 0.

void periodic_task_a(void){
	
	for (;;){
		/* task logic */
		
		
		/* relinquish the cpu */
		Task_Next();
	}
}

Task_Create_Period(periodic_task_a, 0, 160, 20, 0);			
			

System tasks (as well as RR tasks) are defined by only the task they need to perform. The function prototype for creating a system task is given below:

int   Task_Create_System(void (*f)(void), int arg);				
				

System tasks are scheduled as soon as they are ready. This results in immediate pre-emption behaviour when system tasks are created in low priority tasks. One consequence of this is that the system tasks usually finishes even before Task_Create_System returns.