Project 2

Contents

The goal of project 2 is to implement, and test a priority based, preemptive, multithreaded real time operating system (RTOS). This is done on the same microcontroller as in project 1, the ATMega 2560. The RTOS will have similar features to the pthread library including mutexes and priority inheritence.

Arduino ATMega 2560

The ATMega 2560 is an Atmel 8-bit AVR RISC based microcontroller with 256 KB of flash memory and 8 KB of SDRAM running at 16MHz.

17-Bit Address Problem

AVR architectures store instructions in the flash part of memory. This memory is normally accessed by 2 byte words that are addressed with 16 bit addresses. This means the maximum amount of memory that can be addressed by 16 bits is 2*2^16 bytes, or 128 KB. Since the ATMega has 256 KB of flash, it uses extended addressing to address the upper part of memory. This means the CPU effectively uses a 17 bit address, with an extra bit stored in the EIND (extended indirect) register. The compiler then calls functions in memory using special instructions (like eijmp and eicall), that concatenate the EIND register with the 16 bit Z (r30 and r31) register that stores the the first 16 bits of the address. In order to fix the 17-bit address problem in the RTOS, the RTOS needs to store the EIND register when it saves a task's context, and restore the EIND register when it restores a task's context. Also when the workspace for a task is initialized, there needs to be a 3 byte (instead of a 2 byte) return address for the program counter. Context switching will be illustrated later, but these two fixes are shown below:

As you can see, the third byte is set to 0 when the task is initialized.

Booting, Context Switching, and the Kernel

When the RTOS boots, it makes a one-time call to OS_Init, which initializes the required memory for MAXTHREAD number of tasks, MAXMUTEX number of mutexes, and MAXEVENT number of events. The state of these 3 types of resources are all set to an inactive or dead state. The RTOS then creates a task called a_main. a_main is an application level function with the highest priority. It will run after the RTOS has finished booting and create any necessary tasks, mutexes, and events through system calls to the running RTOS. OS_Start is then called to change the state of the kernel to active. The kernel can then begin running by scheduling and dispatching the a_main task created earlier.

Two of the 16-bit PWM timers (Timer1 and Timer3) on the ATMega 2560 were used to control the flow of the RTOS. Both were configured in CTC (Clear Timer on Compare) mode with TOP values to control the rate at which their relative timer compare-vectors were set. Interrupt handlers were then created for the periodic interrupts that occurred. Timer1 fires an interrupt every 10 ms. Its corresponding Interrupt Service Routine (ISR) checks the SleepQueue to see if any task has finished sleeping and if so will move it back to the ReadyQueue. It also calls Task_Next so that tasks with the same priority are cooperatively sharing the CPU. Timer 3 is used as a real time clock to keep track of the amount of time that has passed since the RTOS booted. Timer3 fires an interrupt every second and increments a global overflow count. This timer is used to put tasks to sleep and wake them up using absolute time as discussed later in the Task Sleep section.

The kernel of the RTOS is itself a pseudo-task in that its context is saved to and restored from RAM in the same way as all of the processes. Its entire function body boils down to a switch statement that is invoked based on the current process's request to the kernel. This switch statement can be thought of as a way for the application to make system calls for the kernel to execute. Most of the kernel's switch statements call kernel-level functions that contain the actual implementation of task, mutex, and event actions. These functions are inaccessible to the application that is utilizing the RTOS, which gives the system a security buffer, in that the RTOS code itself cannot be compromised by a regular user. Any system call (request) to the kernel will disable interrupts. Interrupts will then remain disabled until the kernel exits.

A list of all kernel requests are given here:

• NONE
• CREATE
• NEXT
• SLEEP
• TERMINATE
• SUSPEND
• RESUME
• MUTEX_INIT
• MUTEX_LOCK
• MUTEX_UNLOCK
• EVENT_INIT
• EVENT_WAIT
• EVENT_SIGNAL

Priority Scheduling

All active tasks have a priority from 0 (highest) to 10 (lowest). The task with the highest priority will be the task that runs next. If there are tasks with equal priority, they will execute cooperatively on a first-come-first-served basis.

The Dispatch function is the scheduler. Every time dispatch is called, it takes the highest priority task from the ReadyQueue and sets it to become the next running task. The scheduler always picks a task whose state is READY, and who is not suspended.

Tasks

Threads are represented by "tasks". Each task is represented by a process descriptor struct, which contains all location and state information about each task. In addition, each process descriptor contains a memory "workspace" of 256 bytes for storing the register values and return address for context-switching. Memory for MAXTHREAD number of processes is allocated upon initial booting of the RTOS. The struct has the following fields:

• DEAD
• READY
• RUNNING
• SLEEPING
• BLOCKED_ON_MUTEX
• WAITING
• TERMINATED

Task_Create is called with three parameters: the address of the function that is to run as the task, an integer value for the initial priority of the task, and an integer value for the task's initial arg. If the kernel is currently inactive, then Kernel_Create_Task will be called with these three parameters because we are already in the kernel (its booting process to be exact). Otherwise a context switch to the kernel will be initiated with the request to create a task. Upon hitting the CREATE case of the kernel, Kernel_Create_Task will immediately be called, which (if the MAXTHREAD hasn't been exceeded) locates an available DEAD process spot in the Process array that the new task can occupy. On finding this spot, Kernel_Create_Task_At is called with the original three parameters as well as the newly discovered free Process address. Kernel_Create_Task_At clears the contents of the new process' workspace, and inserts the address of the Task_Terminate function at the bottom of the stack (in case the task returns, so the process slot can be freed). Above this, it inserts the return address of the function, and then skips the stack-pointer ahead 34 bytes. The stack pointer needs to be moved ahead because when this task executes for the first time, the context switching code will attempt to pop registers 0 - 31, SREG, and EIND, so initial dummy values need to be in place. Finally, the process descriptor variables are initialized, the task is set to READY, and it is enqueued in the ReadyQueue.

Task_Next sets the kernel request to NEXT and enters the kernel. The kernel simply sets the state of the current process to READY, enqueues the current process into the ReadyQueue, and calls Dispatch.

Calling Task_GetArg will return the initial "arg" parameter that was given to a task at creation time.

Task_Suspend takes the process id to be suspended and assigns it to the current processes's pidAction variable. After also setting the process's kernel request to SUSPEND, it context-switches to the kernel, where it hits the SUSPEND case of the switch statement. From this case, Kernel_Suspend_Task is called, which either sets the "suspended" flag of the current process to 1 (if it is the current process that is to be suspended), or locates the target process using the pidAction variable and sets its suspended flag to 1. Upon returning to the kernel switch case, Dispatch is called if it was indeed the current process that was suspended. It is important to note that suspended tasks can changes states, can be woken up and moved to the ReadyQueue, can acquire mutexes if they were blocked on a mutex, but cannot become running until they are resumed.

Task_Resume also takes in a process id to be resumed. It looks up the process to be resumed, and sets its suspended flag to 0. If the resumed task has a higher priority then the running task, Dispatch is called to pre-empt it.

Calling Task_Sleep will add the TICKS parameter you pass to it to the current count of Timer 3 (converted to TICKS), counting any overflow (above 100 TICKS) in a special variable. It then enters the kernel with the TICKS and overflow set to when the task should be "woken up". The kernel simply enqueues the task into the SleepQueue and calls Dispatch.

A task can terminate itself by calling Task_Terminate. Termination is immediate, so the first action is to raise the priority of the terminating task to 0 (highest), and set the state to TERMINATED. Now all mutexes locked by this process can be released or given away if another task is waiting for them, then the state of the task is set to DEAD. Since tasks can only terminate themselves, there is no need to check any queues because the task is running.

Mutexes and Priority Inheritence

A mutex is a resource that acts like a binary semaphore which tasks can lock and unlock. A mutex has 3 properties of ownership, recursiveness, and inheritence. All mutexes are stores in an array called Mutexes, and respresented by a struct with the fields: m (id), state, owner, and lockCount. A mutex has 3 states: DISABLED, FREE, and LOCKED.

When a mutex is initialized, the lockCount is set to 0, the state is set to FREE, the id is set to a number from 0 - 15, and the owner is set to NULL.

When a task calls Mutex_Lock(m), if the mutex is free, then the state is set to LOCKED, the lockCount is set to 1, and the owner is set to the calling tasks id. If the mutex is locked, and the calling task is the owner, then the lockCount is incremented as mutexes allow recursive locks. This does mean it must be unlocked the right number of times to become free. And if the mutex is locked and the calling task is not the owner, its state becomes BLOCKED_ON_MUTEX and it enters the WaitingQueue. When this happens, if the task that became blocked has a higher priority then the task with the mutex, the task with the mutex inherits the higher priority for the duration that it holds the mutex. This is a solution to the priority inversion problem where the high priority task could be pre-empted by a medium priority task. The WaitingQueue functions as a first-come-first-served queue.

When a task calls Mutex_Unlock(m), If the lockCount is greater than 1, then it is decremented by one. If the lockCount is 1, and nobody is waiting on it, then the state it set to FREE, the owner is set to NULL, and the lockCount is set to 0. If the lockCount is 1, and there is a task waiting on the mutex, then in order to prevent barging, the lockCount will stay at 1, the state will stay locked, but ownership will be transferred to the task that is blocked on that mutex (and put back into the ready queue). The priority of the unlocking task will also be set back down to its original priority if it had inherited a higher priority. A task that is currently terminating may wish to unlock its mutexes, and if the state of the unlocking task is TERMINATED, all mutexes will be immediately unlocked, or have ownership transferred with lockCounts being set back to 1.

Events

An event is a resource that tasks can wait on and signal. An event has 3 states: INACTIVE, UNSIGNALLED, and SIGNALLED. Only one task can wait on an event at a time. An event is represented by a struct with the fields state, e (id) and p (for the process that is waiting on the event if any). The structs are all stored in an array called Events.

When initialized, the state it set to UNSIGNALLED, the id e is set to a number from 0 - 15, and p is set to NULL.

When a task calls Event_Wait(e), the task will be blocked if nothing else is waiting on the event and if the event has not yet been signalled (The task's state will be changed to WAITING). If the event has already been signalled, then the event's state will be set back to UNSIGNALLED and the calling task will continue to execute. Tasks that are in the WAITING state are enqueued back into the ReadyQueue but will never be dispatched until their state is set back to READY. If a different task is already waiting on the event, then the calling task will continue to execute.

Any running task can signal an event. If a task is waiting on that event, the waiting task's state is set back to READY and the event's state goes back to UNSIGNALLED. If no task is waiting on the event, then the state of the event is simply set to SIGNALLED as events record one signal and drop any subsequent signals.

Error Handling

The RTOS can recover from a number of errors. These errors and the RTOS behavior are described in the following table:

Some errors can occur that will require the RTOS to be rebooted. These include:

RTOS testing was conducted using a USB logic analyzer. Testing was split into 6 distinct categories. These cateogories are the initial tests provided by Daniel, Task Termination, Suspension and Resumption, Sleeping, Mutexes and Priority Inheritence, and Events. Each category has multiple tests that attempt to isolate a specific piece of functionality. The tests provide good coverage of all the features implemented and give us reliability in our RTOS.

Initial Tests

Please note that for tests 1-3: Channel 0 is used as the trigger, and Channel 1 corresponds to P1, Channel 2 to P2, and channel 3 to P3.
And for test 4: Channel 0 corresponds to P0, Channel 1 to P1, Channel 2 to P2, Channel 3 to P3, and Channel 4 to the trigger.

Task Termination

Test 1 has Channel 0 as the trigger, Channel 1 as P1, Channel 2 as P2, and Channel 3 as P3.
Test 2 has Channel 0 as the trigger, Channel 1 as P1 - P14, Channel 2 as P15, and Channel 3 as P16.

The message sequence chart is shown here:

The message sequence chart is shown here:

Mutexes

Channel 0 is the trigger, Channel 1 is P1, Channel 2 is P2, Channel 3 is P3 (if existant).

The message sequence chart is shown here:

The message sequence chart is shown here:

The message sequence chart is shown here:

The message sequence chart is shown here:

The message sequence chart is shown here:

The message sequence chart is shown here:

Task Sleep

The message sequence chart is shown here:

Suspend & Resume

Channel 0 is the trigger, Channel 1 is P1, and Channel 2 is P2.

The message sequence chart is shown here:

The message sequence chart is shown here:

Events

Channel 0 corresponds to the trigger, Channel 1 to P1, and Channel 2 to P2

The message sequence chart is shown here:

The message sequence chart is shown here:

The message sequence chart is shown here:

Performance measurements were collected using a USB logic analyzer and setting a pin high when entering the specific piece of code to be instrumented. The pin would then be set low when the desired piece of code had finished executing. The following sections show the logic analyzer outputs and measured times:

The boot time refers to the amount of time it takes for the RTOS to initialize and start.

The dispatch time refers precisely to the dispatch function discussed above and measures the amount of time it takes to select a new task from the ReadyQueue to run. The context switching time is the time it takes to save the current context onto the stack, and restore a new context back into the registers. The time is the same for entering the kernel, or leaving the kernel.

The worst case interrupt disabled time is measured as the longest time interrupts are disabled. This happens when a call to Task_Create occurs. We enter the kernel, create the task, and return back to the original task (if the original task still has the highest priority).

The following table shows the average times for each of the actions that can take place on a task:

The following table shows the average times for each of the actions that can take place on a mutex:

The following table shows the average times for each of the actions that can take place on an event:

Improve Interrupt Service Routine

Currently the interrupt service routine (ISR) fires every 10 ms to check the SleepQueue and potentially dispatch a new task. Currently if a new task is dispatched, the ISR does not finish its execution and leaves a return address on the stack. One improvement to this is to instead use the eijmp (extended indirect jump) instruction to leave the ISR and enter the kernel without leaving a return address on the stack. This would slightly improve performance and make sure the ISR finishes its execution.

Reduce CPU Power Consumption

A way to improve the battery life of any applicaiton running on this RTOS is to put the CPU into a low power mode if there is no task to execute. This can be done using the AVR sleep library. The idea would be to find a way to estimate how long the CPU plans to be idle, and if it was worth it, sleep for that amount of time. Calculations would have to be performed to detemine the overhead of putting the CPU to sleep and waking it up. With that information, an informed decision could be made to sleep the CPU if it is going to be idle for more than t milliseconds.

Improving Core RTOS Performance

Other cleanup and improvements for this RTOS include improving the queue data structure. Currently, either one of dequeue or enqueue is an O(n) operation, while the other is O(1). They can both be made O(1) operations by revising the queueing/dequeueing strategy or using a hash table instead.

The goal going forward is to incorporate the RTOS designed and implemented here into project 3 which will see the successful completion of a roomba tank. The work above shows that the RTOS is functional, passes a wide range of test cases with maximum coverage, has good performance, and gives us confidence going into project 3.

• The ATMega 2560 Datasheet is available here.
• The Atmel AVR 8-bit instruction set is available here.

Initial Test 1 Zoomed Captures

Initial Test 2 Zoomed Captures

Initial Test 3 Zoomed Captures

Initial Test 4 Zoomed Captures

Download the project 2 source code here.