Module 3

REAL TIME OPARATING SYSTEM CONCEPT

Architecture of Kernel

[1] Tasks and Tasks Scheduler

• The embedded software consists of number of tasks.
• The task object consists of its name, a unique ID, a priority, a stack and a Task Control
Block.
• The kernel has its own system tasks with priorities.
• These tasks are:
o Startup task
o Exception handling task
o Logging task
o Idle task
• Each task has to be assigned priority; and a mechanism for deciding which task will get
CPU time next has to be worked out. This is known as task scheduling.
 • Another important requirement is that one task should not corrupt the data of another
task.
• While scheduling the tasks, a number of issues as described below:
➢ Many tasks make calls to a function.
▪ Reentrant function.
▪ Non-reentrant function.
➢ Every task requires resources.
➢ Tasks may need to communicate data amongst themselves.

[1.1] Task States

• In an embedded system, each task has to do a specific job.
• Consider, an embedded system that obtain data from a serial port and converts the data
into Ethernet packets.

• A task can be in one of the following states:

➢ Running state - if it is being executed by the CPU
➢ Waiting state - if it is waiting for another event to occurs.
➢ Ready-to-Run state - if it is waiting in a queue for CPU time.
• Task stack
➢ Every task will have a stack.
[1.2] Task Scheduling
• Selecting the task which is to be executed at given point of time is known a task
scheduling.
• Task scheduling provides the decision power to multitasking.
• Depending on the requirement of the embedded system, the scheduling algorithm needs
to be chosen.
• Following scheduling algorithm:
[A] Preemptive Scheduling
▪ Round Robin Scheduling
▪ Priority Based Scheduling
[B] Non-preemptive Scheduling
▪ First In First Out Scheduling
▪ Last In First Out Scheduling
▪ Shortest Job First Scheduling

[A] Preemptive Scheduling:

• In case of Preemptive Scheduling, the higher priority task when enters the ready state
is immediately shifted to running state. Thus, if a task 𝑇1 is in running state has some
priority.
• The other tasks in ready state are of lower priority. If a task 𝑇2, enters into the running
state and has a priority higher than that of the task 𝑇1, then the task 𝑇2 will pre-empt the
task 𝑇1 and enter into the running state.
• Round Robin Scheduling: - In this case each task remains in the running state for a
predefined fixed time. An example of same is shown in the Figure. Some RTOS Kernel
allows user to configure time slice. Tasks in round robin scheduling executes for fixed
amount of time in the order as per their position in the 'Ready' queue.
[ The following information is only for understanding purpose:
How Round Robin scheduling works:
1. Tasks are placed in a circular queue.
2. The scheduler selects the first task in the queue.
3. The task is allowed to execute for a fixed amount of time (quantum).
4. If the task completes within the quantum, it is removed from the
system.
5. If not, it is moved to the end of the queue, and the scheduler selects the
next task.
6. This process repeats until all tasks are completed. ]

• Priority based Scheduling: - Priority based pre-emptive scheduling provides real-time

attention to high priority tasks. Thus, priority based preemptive scheduling is adopted
in real time systems who need to execute the high priority task instantly. Most of the
commercially available RTOSs make the use of preemptive priority-based scheduling
algorithm for task scheduling.

[B] Non preemptive Scheduling

• First in first out Scheduling: - As the name implies, the First In First Out (FIFO)
scheduling allocates CPU time to tasks based on the order in which they enter the
‘Ready’ queue. The first entered task gets the service first. This is a good algorithm for
an embedded system has to perform few small tasks all with small execution times.
FIFO scheduling is also known as First Come First Served (FCFS) where the task which
is put first into ‘Ready’ queue is serviced first.
• Last In First Out Scheduling: - The Last In First Out (LIFO) scheduling algorithm
also allocates CPU time as per the order in which tasks entered into the 'Ready' queue.
The last entered task gets service first. LIFO scheduling is also known as Last Come
First Served (LCFS) where task which is arrived last in the queue is serviced first.
• Shortest Job First Scheduling: - Shortest Job First (SIF) scheduling algorithm 'search'
the 'Ready' queue each time a task gives off its CPU time when either the task terminates
or enters the 'Wait' state for input/output or system resource to pick the task with
shortest (minimum) estimated completion/run time. In SJF, the task with shortest
estimated run time is selected first for execution, followed by next shortest estimated
run time task and so on. The average waiting time for a give set of task is less as
compared to other non-preemptive scheduling like FIFO. The major drawback of SJF
algorithm is that a task with estimated execution completion time is high may not get
CPU time for execution if more and more tasks with lower estimation execution time
enter the "Ready' queue This condition that dominates high estimated completion time
tasks is known as Starvation.
 • Priority Based Scheduling: - In non-preemtive priority-based scheduling, ‘Ready’
queue sorts according to tasks priority and selects the task with the highest level of
priority for execution.

[2] INTERRUPT SERVICE ROUTINES (ISR)

• Interrupt is a hardware signal that informs the CPU that an important event occurred.
• When an interrupt occurs, CPU saves its context and jumps to the ISR.
• In real time operating systems, the interrupt latency, interrupt response time and the
interrupt recovery time are very important.

• Interrupt Latency
➢ The maximum time for which interrupts are disabled + time to start the
execution of the first instruction in the ISR is called interrupt latency.
• Interrupt Response Time
➢ Time between receipt of interrupt signal and starting the code that handles
the interrupt is called interrupt response time.
➢ In a preemptive kernel, response time = interrupt latency + time to save CPU
registers context.
• Interrupt Recovery Time
➢ Time required for CPU to return to the interrupted code/highest priority task is
called interrupt recovery time.
➢ In non-preemptive kernel, interrupt recovery time to restore the CPU context +
time to execute the return instruction from the interrupted instruction.
 o In preemptive kernel, interrupt recovery time to check whether a high priority
task is ready+ time to restore the CPU context + time to execute the return
instruction from the interrupted instruction.

[3] SEMAPHORES
• When multiple tasks are running, two or more tasks may need to share the same
resources.

• To access a shared resource, there should be as mechanism so that there is discipline.

This is known as resource synchronization.
• A mechanism that shows for task l to inform task 2 that it has done its job.
• This has to be done through well-defined procedure. This is known as task
synchronization.
 • Semaphore is a kernel object that is used for resource synchronization and task
synchronization.
• Suppose two tasks want to access a display. Display is shared resources. To control the
access, a semaphore is created.

• If a number of tasks have to access the same resources then the tasks are kept in a queue
and each task can acquire the semaphore one by one.

[4] MAILBOXES
• A mailbox object is just like your mailbox.
• A task can have a mailbox into which others can post a mail.
• To manage the mailbox object, the following function calls are provided in the
operating system API:
o Create a mailbox
o Delete a mailbox
o Query a mailbox
o Post a message in a mailbox
o Read a message from a mailbox
[5] MESSAGE QUEUES

• Message queue can be considered as an array of mailboxes.

• Some of the applications of message queue are: taking the input from a keyboard, to
display output, reading voltages from sensors data packet transmission in a network.
• In each application, a task or an ISR deposits the message in the message queue. Other
task can take the messages.
• At the time of creating a queue, the queue is given a name or ID, queue length, sending
task waiting list and receiving task waiting list.

• The following function are provided to manage the message queues:

1) Create a queue
2) Delete a queue
3) Flush a queue
4) Post a message in queue
5) Read a message from queue
6) Broadcast a message
7) Show queue information
8) Show queue waiting list

[6] PIPES
• A task can write into a pipe and the other task reads the data that comes out of the pipe.
• Task-to-task or ISR-to-task data transfer can take place using pipes.
• Pipes can be used for inter-task communication.
[7] EVENT REGISTERS
• A task has an event register in which the bits correspond to different events.
• Each bit in an event register can be used to obtain the status of an event.
• Each of the bits in the event register is an event flag.

[8] TIMERS
• Timers are used to measure the elapsed time of events.
• The kernel has to keep track of different times:
➢ A particular task may need to be executed periodically. A timer used to keep
track of the periodicity.
➢ A task may be waiting in a queue for an event to occur. If the event does not
occur for a specified time, it has to take the appropriate action.
➢ A task may be waiting in a queue for a shared resource. If the resource is not
available for a specified time, an appropriate action has to be taken.
• Timer management function calls:
1) Get time
2) Set time
3) Time
4) Reset timer
[9] MEMORY MANAGEMENT
• RTOS Kernel adopts slightly different approach for memory management than general
purpose operating system. In general, the memory allocation time depends on the size
of block of memory needs to be allocated and the state of the allocated memory block.
• Since predictable timing and deterministic behaviour are the primary goal of on RTOS,
RTOS achieves this by compromising the effective memory management techniques.
RTOS uses block-based memory allocation technique.
• On the other hand, General Purpose Operating System (GPOS) adopts dynamic
memory allocation techniques RTOS Kernel uses memory block of fixed size and
allocates memory block when needs.
• The blocks are stored in a memory pool. To achieve predictable timing and avoid the
timing overheads, most of the RTOS Kernel allows tasks to access any of the memory
blocks without any memory protection