A Simple RTOS

This is a simple RTOS that supports pre-emptive multithreading, and interprocess synchronization using Events.

Note: Please don't edit the interface file "os.h".

Author:

Dr. Mantis Cheng

Date:

26 September 2007

GLOBAL ASSUMPTIONS

(ATMEL specific)

• Counter1 Timer and SWI interrupts are reserved.

• All runtime exceptions (where assumptions are violated) or other unrecoverable errors get handled by calling OS_Abort().
• Each valid entry in PPP[] must be non-zero except IDLE.
• All unspecified runtime errors have undefined behaviours, e.g., stack overflow.
• PPP[] cannot be modified once the application starts running.

SCHEDULING POLICY

There are three scheduling levels: SYSTEM, PERIODIC and RR. These levels are prioritized with SYSTEM being the highest, and RR being the lowest.

Preemption occurs immediately. Whenever preemption is feasible, it takes place instantly. As soon as a higher priority task becomes ready, it preempts all lower priority tasks.

SYSTEM TASKS

SYSTEM (level) tasks are FCFS; they run to completion, i.e., until they terminate, block or yield. Thus, they are non-preemptible, not even by other SYSTEM tasks. They should only be used for critical system level activities, e.g., error or fault recovery. Running too many SYSTEM tasks could affect the real time performance of all other low level tasks.

PERIODIC TASKS

PERIODIC tasks are scheduled based on a fixed cyclic scheduling plan; they are time-based. (See below about PPP[].) Since they are time-critical, they are NOT allowed to block (i.e., wait on an event). When a PERIODIC task is created, it is assigned a "name", a non-zero user-defined constant between 1 and MAXPROCESS. This name is fixed and can NEVER be changed again. No two PERIODIC tasks have the same name. All names are unique. Since tasks may terminate and be created again over time, the same name may be reused over time for different PERIODIC task instance.

The PPP[] array is essentially a linear representation of a Gantt diagram. It is an array of [Name1, Interval1, Name2, Interval 2, ... ]. The name of every PERIODIC task must appear in PPP[] array at least once, but may be more than once.

For example, if we create three PERIODIC tasks with names A, B and C out of three functions P(), Q() and R() respectively. Then, PPP[] = { A, 2, B, 3, A, 5, C, 1 } means executing A for 2 ticks, then B for 3 ticks, then A again for 5 ticks, then C for 1 tick, then A again, and so on. The total cycle time is 2+3+5+1=11 ticks. That is, within 11 ticks, A executes twice, B once and C once. If P() terminates, but the name A is later assigned to another function U(), then A will be executed again according to PPP[] order using U(). In a sense, PPP[] specifies at least a single execution cycle of all PERIODIC tasks. IDLE is a special PERIODIC task name, which means do nothing during this task's assigned interval.

A PERIODIC task may yield (calling Task_Next()) to relinquish the processor before its assigned interval. In this case, it has completed its current execution interval and is waiting for its next interval.

It is a runtime error if a PERIODIC task executes longer than the currently assigned interval. It is important NOT to underestimate the execution time requirement of a PERIODIC task. Choosing the appropriate execution order and intervals for all PERIODIC tasks is the responsibility of the Application Design Engineer(s), not our RTOS. Hence, all timing violations should be caught and then reported.

By specifying PPP[] and scheduling our PERIODIC tasks accordingly, we shall know precisely the execution "cycle" time of all such tasks, thus their best execution frequency/rate and response time. This is how we guarantee the predictability of timing and ordering all critical activities.

RR TASKS

RR tasks are scheduled in a round-robin fashion, i.e., each RR task runs for one TICK approximately and yields to the next RR task. They don't have any time critical schedule to follow, thus they share the processor cycles fairly.

RR tasks are allowed to run only when no PERIODIC or SYSTEM tasks are executing. When an RR task resumes after pre-emption, it re-enters its RR level at the end. When an RR task yields, or resumes after being unblocked, it re-enters its level at the end as well.

OS BOOTING

Our RTOS is compiled together with an application. It doesn't provide a "main()" function, which is a part of the application. By convention, the "main()" is the first function to be called by the C runtime code, "crt0.S". For our RTOS, we shall change this convention as follows:

1. OS_Init() is called from crt0.S as the very first C function to be executed instead of main().
2. Upon completion of OS_Init(), the application's main() is then created as the first and only SYSTEM level task.
3. In main(), the rest of the application tasks are then created.
4. In order for all other application tasks to run, our main() task must either terminate or block on an event. (For example, main() may become a "watchdog" task to reset the entire application.)

INTERPROCESS COMMUNICATION

Events are one-way synchronization signals. They don't have any "memory" (i.e., values); thus, they are NOT semaphores. Any SYSTEM or RR task may wait on an event; PERIODIC tasks MUST NOT wait on any event. However, any task may signal/broadcast an event. A waiting task is resumed when the associated event is signalled. All waiting tasks are resumed when the associated event is broadcasted. When an event is signalled (or broadcasted) but there are no waiting tasks, this is a no-op; hence, events have no memory.

---