Real-Time Computing System's Project

Group Members: Saransh Gupta & Jimit Doshi
Duration: March, 2014 - present

Fully Preemptive nxtOSEK Kernel.

Introduction

In real-time computing scenarios, we are concerned with logical as well as temporal accuracy of the results. While developing algorithms or performing schedulability analysis, preemption overheads are usually ignored even, though it's an operation that consumes finite amount of time. Preemption allows higher priority tasks to halt the lower priority tasks, though this need not be necessarily required to meet task deadlines. Our concern is not to get the results as soon as possible but soon enough to just meet the deadlines of all the tasks. Algorithms which meet deadlines and minimize preemptions in order to decrease overheads have been developed.

The nxtOSEK is a Real-Time Operating System for the AT91SAM7S256 ARM7TDMI controller, with capabilities of ANSI-C/C++ programmability. The nxtOSEK kernel cannot be used to demonstrate any such algorithm, since it does not support nested preemption. The task scheduling in the nxtOSEK kernel is governed by a 1ms ISR routine. When a higher priority task preempts a lower priority task, it has been observed that this 1ms ISR(and hence the task scheduler) is suppressed for the duration of execution of the higher priority task. This causes an equivalent shift in the release times of all the subsequent tasks and the entire timing behaviour of the nxtOSEK kernel is skewed.

The nxtOSEK kernel has been purposefully designed to prevent successive instances of preemption i.e. the kernel does not support a case where after one preemption event, while the preempting task is yet to finish its execution, it is preempted in turn by an even higher priority task. In this project, we attempted to resolve this by modifying the current kernel behavior. The article has been divided into five sections, Background, that explains the current kernel behavior and highlights the problem in it, Design, that encompasses the suggested modifications in the kernel, Implementation, depicting the changes done to achieve the goal, Validation, defines the test-cases used to test the modified kernel and Results,presenting the output of the modification.

Background

We describe below some of the relevant implementation details regarding nxtOSEK:
1. The currently running task's task ID is stored in runtsk.
2. schedtsk : This is the task that the scheduler evaluates as the highest priority task.
3. File structure :
- irq.s - Has the assembly routine for IRQ interrupt handler.
- cpu_support.s - Assembly routines to dispatch and preempt tasks.
- init.s - SWI ISR handler added here.

We present below a high level discussion of nxtOSEK's current algorithm to deal with preemption, it's limitations and our approach to resolve them. Let us first consider the default behavior of the nxtOSEK kernel and understand how it doesn't allow nested preemption. The nxtOSEK's kernel scheduler runs from a 1ms timer ISR. Every 1 ms the currently running task is interrupted and the scheduler runs to look for ready tasks based on the period of each task (for a typical periodic system). Accordingly, the highest priority task amongst all the ready tasks and the currently running task is evaluated and updated as schedtsk. Thereafter the kernel compares the values of schedtsk and runtsk. If they are the same, it implies that the currently running task is the highest priority task and no preemption is required. However, if they are different, then it is a case of preemption as a higher priority task than the current runtsk is now ready. Consider the simpler case of non-preemption first. If schedtsk and runtsk are equal, then scheduler has to return back to the interrupted task from the ISR directly and resume task execution from the point where it was interrupted. However in case of preemption, the higher priority task is run from the ISR itself i.e. the ISR is not `returned' as long as the higher priority task's execution is not completed. Thereafter, the execution control returns back to the pending ISR. From here, the ISR returns back to the preempted task to resume it's execution. Evidently, since the preempting higher priority task is run from the ISR itself, it leads to the following while it is being executed:
1. No kernel/scheduler calls while the higher priority task is running. This is because the current ISR routine (which runs the scheduler) has not 'returned' yet.
2. Nested preemption is not possible, as no new higher priority task shall be evaluated for readiness since the kernel itself is no longer running every 1 ms (assuming the more general case of the higher priority task having an execution time greater than 1ms).
3. Skewed (delayed) release times of all subsequent tasks as the scheduler is suspended for the execution time of the higher priority task.

Algorithm

Here we are providing just a high level pictture of the design. The details regarding the design as well the implementation along with the flowcharts can been seen in the Final Report attached below. After analyzing the original algorithm, we have come up with a new approach to allow nested preemptions. Summary of the new program flow:

1. We create 3 new data structures in the task control block as below:
- tcxb_spsr[] : To store the SPSR value of the interrupted task
- tcxb_lr[] : To store the return address of the interrupted task i.e. address of the location where a given tasks was preempted
- tcxb_preempt_flg []: Flag used to indicate preemption. Whenever a high priority task preempts a lower priority task, the high priority task's tcxb_preempt_flg is SET.

2. While running the kernel assembly code in ISR, if it is realized that (runtsk! = schedtsk), then we set the tcxb_preempt_flg[schedtsk] = 1. Also, the interrupted task's spsr and lr values are saved in its tcxb_spsr & tcxb_lr locations respectively. tcxb_pc of runtsk is set to ‘context_restore’.

3. After this, the 'int_return_preemption' code is run where the ISR is ‘returned’ to a high priority task. This is in contrast to the previous execution where the preempting task is run while still the ISR has not yet returned, which was the main reason why nested preemptions were not possible with that approach.

4. Subsequently, whenever the preempted task is scheduled again, first its context is restored from 'context_restore'. Thereafter, SPSR is restored and then pc is set to LR value.

Validation

In the Figure, the following test cases are discussed:
a. First is the case of preemption with two tasks where the low priority task(red) is preempted by the high priority(yellow) task at instant 5.
b. Second case depicts nested preemption where the medium priority(yellow) task preempts the low priority task(red) at instant 10 and is preempted by the high priority task(green) at instant 15.

Results & Open Points

I. The scheduler is no longer suppressed during the execution of high priority task. This is because the ISR is completed before the high priority task begins execution. Hence, even when the high priority task is executing the scheduler executes periodically at 1ms.
II. We weren't able to demonstrate successful return to the preempted task after the high priority task finishes its execution. Instead, we observed the controller getting reset after the completion of the higher priority task. We couldn't resolve this due to limited debug/simulation capabilities.

Acknowledgements

We would like to sincerely thank Dr. Frank Mueller for initiating the idea and continuously discussing our design. The suggestions provided by Dr. Mueller turned out to be fruitful in understanding the issue and designing its solution.

References

1. The nextOSEK webpage.
2. The OSEK specs.
3. Andrew N.~ Sloss, Dominic Symes, Chris Wright and John Rayfield, "ARM System Developer’s Guide".
4. SWI Instruction Handling.
5. SWI Instruction Handling-2.
6. ARM Assembly.
7. ARM Interrupt & Exception Handler.

Project Proposal
Project Interrim Report.
Project Interrim Report - 2.
Project Final Report.
Code Tar.