Over the last few blogs we have written software which runs on the MicroBlaze and reads the XADC, to do this we have not used an operating system instead using a bare metal approach. However as we wish to develop more complex systems, we need to introduce an operating system, so over the next few blogs we will be looking at how we can do just that.
However first I think it is a good idea to talk a little about operating systems and real time operating systems in particular. What differentiates an RTOS from a generic operating system? An RTOS is deterministic, that means the response of the system will meet a defined deadline.
But does the system have to always meet these deadlines to be classed a real-time system?
Actually, no it does not.
There are three RTOS categories that address deadlines differently:
Hard RTOS – Missing a deadline is classified as a system failure.
Firm RTOS – Occasionally missing a deadline is acceptable and is not classified as a failure.
Soft RTOS – Missing a deadline simply reduces the usefulness of the results.
An RTOS operates around the concept of running tasks (sometimes called processes). Each of these tasks performs a required system function. For example, a task might read data from an interface or perform a calculation. A very simple real-time system may use just one task, but it is more likely that multiple tasks will be running on the processor at any one time. Switching between these tasks is referred to as “context switching” and requires that the RTOS saves the processor state for each task before the context switch starts the next task. The RTOS saves this processor state on a task stack.
Determining which task to run next is controlled by the RTOS kernel and this decision can be complicated—especially if we want to avoid deadlock where tasks lock each other out—but the two basic decision methods are:
Time sharing – Each task gets a dedicated time slot on the processor. Tasks with higher priority can have multiple time slots. Time slicing is controlled via a regular interrupt or timer. This method is often called Round Robin scheduling.
Event Driven – Tasks are only switched when a task finishes or when a higher priority task must be run. This method is often called pre-emptive scheduling
When two or more tasks want to share a resource— the XADC for example—it is possible that the tasks might request the resource at the same time. Resource access needs to be controlled to prevent contention and this is one of the operating system’s most important duties. Without the correct resource management, deadlock or starvation might occur.
Here are the definitions we’ll use for deadlock and starvation:
Deadlock – Occurs when a task holds a resource, cannot release it until the task completes, and is currently unable to complete because it requires another resource currently held by another task. If that second task requires a resource held by the first task, the system will never exit this deadlocked state. Deadlock is a bad situation for an RTOS to find itself in.
Starvation – Occurs when a task cannot run because the resources it needs are always allocated to another task. The task starves because of a lack of resources.
As you can imagine, much has been written on the subjects of deadlock and starvation over the years and there are many proposed solutions. For example, there’s Dekker’s algorithm, which was the first known correct solution to mutual exclusion. It is a shared-memory mechanism that does not require a special “test and set” instruction (but is therefore limited to managing two competing tasks) and is attributed to the Dutch mathematician Theodorus Dekker. The most commonly used method to handle deadlock is the use of semaphores, which commonly come into two types: binary semaphores and counting semaphores. A binary semaphore controls access to one resource—for example a hardware resource. Counting semaphores control access to a pool of identical, interchangeable resources such as memory buffers.
Typically each resource has a binary semaphore allocated to it. A requesting task will wait for the resource to become available before executing and once the task completes, it releases the resource. Binary semaphores commonly use WAIT and SIGNAL operations. A task will WAIT on a semaphore. When the resource is free, which could be immediately (or not), the operating system will give control of the resource to the task. When the task completes, it will SIGNAL completion and free the resource. However, if the resource is occupied when the task WAITs on the semaphore, the operating system suspends that task until the resource is free. The WAITing task might have to wait until the the currently executing task is finished with the resource or the WAIT might take longer if it is pre-empted by a higher priority task.
Introducing the concept of task priority also brings up the problem of priority inversion. There is a more flexible class of binary semaphores called mutex’s (the word “mutex” is an abbreviation for “mutual exclusion”) and these are often used by modern operating systems to prevent priority inversion.
Counting semaphores work in the same way as binary semaphores however they are used when more than one resource is available—data stores for instance. As each of the resources is allocated to requesting tasks, the count is reduced to show the number of free resources remaining. When the semaphore count reaches zero, there are no more resources available and any processes requesting one or more of these resources after the count reaches zero will be suspended until the requisite number of resources is released.
Tasks often need to communicate with each other and there are a number of methods to accomplish this. The simplest method is to use a data store managed with semaphores as described above. More complex communication methods include message queues.
When using message queues, a task that wishes to send information to another task POSTs a message to the queue. When a task wishes to receive a message from a queue, it PENDs on the queue. Message queues therefore work like FIFOs
Over the next few blogs we will look at using FreeRTOS and Micrium uc/OSiii
This is the last Arty blog of 2015 , so have a Merry Christmas and and a Happy New Year.