Simple Embedded Operating System and C Implementation
1. Abbreviation
DSP – Digital Signal Processing
OS – Operating System
NPS – Non-Preemptive (Cooperative) Scheduling
PS – Preemptive Scheduling
RAM – Random Access Memory
ROM – Read Only Memory
CRC – Cyclic Redundancy Check
2. Introduction
To implement a particular algorithm (for example a DSP algorithm) for a microprocessor, we need an operating system (OS). In this article I want to describe a very simple OS that will require minimal code and microprocessor resources: RAM, ROM, processor time. One of the main function of the OS is task scheduling. I will consider the simplest option – this is non-preemptive (cooperative) scheduling (NPS). In this case each subsequent task can start only after the end of the previous one and there is no possibility of interrupting the current task based on the priority or the need to start another task in time. It is necessary to ensure that the task does not take longer time than the allowed time. On the other hand in such a system we can easily use global variables without fear that the previous task has not yet finished processing with the data.
Figure 1-1: Simple Operating System
A simple operating system can be imagined as a monitor program that executes periodic (as well as non-periodic) tasks. See the Figure 1-1. Periodic tasks start after a certain period of time, for example, every 50ms. Non-periodic tasks start only after some event, for example, after ADC data collection a non-periodic data processing task is started. The monitor should also perform safety control, for example: Watch Dog Timer Service, check RAM, ROM and so on. In this article I will only consider the task scheduling function.
2. Time Scheduling Organization
To start periodic tasks we need a timer that informs the system that the next fixed period of time has ended. Let’s call this time period time tick. For example choose the time tick = 25ms. The OS shall be got a information from the timer every 25ms. For it the demo SW SimpleOS.c/h uses the function:
uint8 IsNextTimeTickOver(void);
The function is returned TRUE if the time tick is over and FALSE if the time tick is not ready. After the time tick expires the OS will increment the counter:
uint8 os_counter;
The system shall search first bit in the counter which has the value 1, and depending on the bit number the OS starts the corresponding task. See the Table 2-1.
Table 2-1: Periodic Task Scheduling. Note: x – is value 0 or 1
Note: The example has 8 periodic tasks. If you need to define a larger number of tasks then can be used a counter with a more bits size.
Now calculate the time slot for each task. For it as an example consider all the values of low nibbel (0000…1111) of the os_counter and its corresponding tasks
0000 No Task
0001 Task1
0010 Task2
0011 Task1
0100 Task3
0101 Task1
0110 Task2
0111 Task1
1000 Task4
1001 Task1
1010 Task2
1011 Task1
1100 Task3
1101 Task1
1110 Task2
1111 Task1
See the Figure 2-1.
Figure 2-1: Periodic Task Scheduling
Obviously the Task_n has a time slot:
In our example: TimeTick = 25ms, then:
Task1: 2 x 25ms = 50ms
Task2: 4 x 25ms = 100ms
Task3: 8 x 25ms = 200ms
Task4: 16 x 25ms = 400ms
…
Task8: 256 x 25ms = 6.4s
The described algorithm is implemented in the ‘void IncrementCounterAndStartPeriodicTasks(void);’
Now let’s go back to the ‘IsNextTimeTickOver( )’ and describe one of its possible implementations. See the Figure 2-2.
Figure 2-2: Realization of the IsNextTimeTickOver( ) Function
Timer interrupt is executed every time tick and interrupt sets tickFlag=TRUE. The ‘IsNextTimeTickOver( )’ function checks the tickFlag. If the flag is set then the function resets this flag and returns TRUE, otherwise the function returns FALSE.
Other implementations of the ‘IsNextTimeTickOver( )’ function are also possible. For example a function can read the current timer value and calculate itself when the next time tick event will take place.
3. Non-Periodic Task
To support nonperiodic tasks the ‘nonperiodicTaskState’ structure is used. See the SimpleOS.c/h.
typedef struct nonperiodic_task_struct
{
uint8 flag;
func_ptr task_ptr;
} nonperiodic_task_s;
nonperiodic_task_s nonperiodicTaskState;
To execute for example the task:
void nonPeriodicTask(void)
{
// working functions
}
Need to initialize the ‘nonperiodicTaskState’ structure:
nonperiodicTaskState.task_ptr = nonPeriodicTask; /* task name */
nonperiodicTaskState.flag = TRUE; /* the task shall be executed */
Next in the main loop OS in ‘main( )’ function:
/* Check the next Tick Time */
while (FALSE == IsNextTimeTickOver())
{
/* Check the nonperiodic task */
if(FALSE != nonperiodicTaskState.flag)
{/* The nonperiodic task is in the queue */
/* Start the nonperiodic task */
nonperiodicTaskState.task_ptr();
/* Clear the queue */
nonperiodicTaskState.flag = FALSE;
nonperiodicTaskState.task_ptr = NULL;
}
}
While waiting for the next time tick the OS will start this non-periodic task.
4. General Comments and Conclusions
The OS is implemented in the ‘int main(void)’ function, which uses an infinite ‘while(TRUE)’ loop. See the SimpleOS.c/h
while(TRUE)
{/* Endless loop */
/* Check the next Tick Time */
while (FALSE == IsNextTimeTickOver())
{
/* Check the nonperiodic task */
if(FALSE != nonperiodicTaskState.flag)
{/* The nonperiodic task is in the queue */
/* Start the nonperiodic task */
nonperiodicTaskState.task_ptr();
/* Clear the queue */
nonperiodicTaskState.flag = FALSE;
nonperiodicTaskState.task_ptr = NULL;
}
}
/* Start the next periodic task */
IncrementCounterAndStartPeriodicTasks();
/* Safety Functions */
// WatchdogTimerService();
// …
}
This loop contains waiting for the next time tick: ‘while (FALSE == IsNextTimeTickOver ())’ and after it the function ‘ IncrementCounterAndStartPeriodicTasks()’ starts the next periodic task. While waiting for the time tick, a non-periodic task can be started.
SW allows to activate and deactivate any periodic task using the task arrays:
func_ptr periodicTaskTable[periodic_task_number];
To activate task k:
periodicTaskTable[k] = PeriodicTask_k;
or can be used a macro:
PERIODIC_TASK_ACTIVATION(PeriodicTask_k,task_k_nmb);
To deactivate task k:
periodicTaskTable[k] = NULL;
or can be used a macro:
PERIODIC_TASK_DEACTIVATION(k);
The initialization function: ‘OsInitialization( )’ activates the all 8 periodic tasks with the ‘PeriodicTask1()’,…, ‘PeriodicTask8( )’.
It is important to check that each task takes less time than the time tick, since each next task starts after the time tick. See the Figure 2-1.
For the reliability of the OS it is recommended to implement some Safety functions:
-
Watch Dog Timer;
-
RAM Test;
-
ROM Test, for example cyclic CRC check;
-
Stack overflow/underflow check;
-
Task sequence check;
-
and so on …