Module III

Real Time Operating Systems: Structure and characteristics of Real Time Systems.
Task: Task states, Task synchronization -Semaphores- types.
Inter task communication mechanisms: message queues, pipes, event registers, signals.
Exceptions and interrupt handling.

Model Questions
1) Draw the state diagram of RTOS queue and explain.
2) What you mean by priority inversion in real time systems? How the operating system
manages this issue?
3) Draw the structure of a real time operating system and explain.
4) Differentiate between exceptions and interrupts. What are the different classifications of
exceptions
5) Explain how synchronization is achieved between different tasks in a real time operating
system
6) Describe any two inter task communication mechanisms in a real time operating systems.

Process/Task Synchronization in OS (Operating System)

When two or more process cooperates with each other, their order of execution must be
preserved otherwise there can be conflicts in their execution and inappropriate outputs can be
produced.

A cooperative process is the one which can affect the execution of other process or can be
affected by the execution of other process. Such processes need to be synchronized so that
their order of execution can be guaranteed.

The procedure involved in preserving the appropriate order of execution of cooperative

processes is known as Process Synchronization. There are various synchronization
mechanisms that are used to synchronize the processes.

Race Condition

A Race Condition typically occurs when two or more threads try to read, write and possibly
make the decisions based on the memory that they are accessing concurrently.

Critical Section

The regions of a program that try to access shared resources and may cause race conditions
are called critical section. To avoid race condition among the processes, we need to assure
that only one process at a time can execute within the critical section.

Critical Section Problem in OS (Operating System)

Critical Section is the part of a program which tries to access shared resources. That resource
may be any resource in a computer like a memory location, Data structure, CPU or any IO
device.

The critical section cannot be executed by more than one process at the same time; operating
system faces the difficulties in allowing and disallowing the processes from entering the
critical section.
The critical section problem is used to design a set of protocols which can ensure that the
Race condition among the processes will never arise.

In order to synchronize the cooperative processes, our main task is to solve the critical section
problem. We need to provide a solution in such a way that the following conditions can be
satisfied.

Requirements of Synchronization mechanisms

Primary

1. Mutual Exclusion

Our solution must provide mutual exclusion. By Mutual Exclusion, we mean that if
one process is executing inside critical section then the other process must not enter
in the critical section.

2. Progress

Progress means that if one process doesn't need to execute into critical section then it
should not stop other processes to get into the critical section.

Secondary

1. Bounded Waiting
 We should be able to predict the waiting time for every process to get into the critical
section. The process must not be endlessly waiting for getting into the critical section.

2. Architectural Neutrality

Our mechanism must be architectural natural. It means that if our solution is working
fine on one architecture then it should also run on the other ones as well.

Lock Variable

This is the simplest synchronization mechanism. This is a Software Mechanism implemented

in User mode. This is a busy waiting solution which can be used for more than two processes.

In this mechanism, a Lock variable lock is used. Two values of lock can be possible, either 0
or 1. Lock value 0 means that the critical section is vacant while the lock value 1 means that it
is occupied.

A process which wants to get into the critical section first checks the value of the lock
variable. If it is 0 then it sets the value of lock as 1 and enters into the critical section,
otherwise it waits.

**************************

Semaphores

Semaphores are integer variables that are used to solve the critical section problem by using
two atomic operations, wait and signal that are used for process synchronization.

 Wait
The wait operation decrements the value of its argument S, if it is positive. If S is
negative or zero, then no operation is performed.
 Signal
The signal operation increments the value of its argument S.

Characteristic of Semaphore
Here, are characteristic of a semaphore:

 It is a mechanism that can be used to provide synchronization of tasks.

 It is a low-level synchronization mechanism.
 Semaphore will always hold a non-negative integer value.
 Semaphore can be implemented using test operations and interrupts, which should be
executed using file descriptors.

Types of Semaphores
The two common kinds of semaphores are

 Counting semaphores
 Binary semaphores.

Counting Semaphores
This type of Semaphore uses a count that helps task to be acquired or released numerous
times. If the initial count = 0, the counting semaphore should be created in the unavailable
state.

However, If the count is > 0, the semaphore is created in the available state, and the number
of tokens it has equals to its count.

Binary Semaphores
The binary semaphores are quite similar to counting semaphores, but their value is restricted
to 0 and 1. In this type of semaphore, the wait operation works only if semaphore = 1, and the
signal operation succeeds when semaphore= 0. It is easy to implement than counting
semaphores.

Counting Semaphore vs. Binary Semaphore

Counting Semaphore Binary Semaphore

No mutual exclusion Mutual exclusion
Any integer value Value only 0 and 1
More than one slot Only one slot
Provide a set of Processes It has a mutual exclusion mechanism
Message Queues

In many applications there is a need for two or several tasks to be able to share data. This can
of course be done using a buffer protected by a semaphore, but many times it is much better
to use a message queue, as this also adds task synchronization and the possibility to queue the
data that another task does not have the possibility to handle at the moment.

What is a Message Queue?

A message queue is a buffer like object through which task and ISRs send and receive
messages to communicate and synchronize with data.

A message queue is a number of buffers of a fixed or maximum size that is controlled by the
RTOS and also a queue for tasks that are waiting for messages. The size and the number of
buffers are specified when the message queue is created. The queue for tasks waiting is used
for queuing up tasks that are waiting for messages to become available. Normally you can
specify when you create the message queue in which order that the tasks should be waiting,
either in FIFO or in priority order.

Any task can send a message to the message queue, and many times it can specified if the
message should be placed at the tail of message queue.

Any task can read a message from a message queue. If the message queue is empty the task
can decide if it wants to wait or not.

Usage of a Message Queue

A message queue is used to send data from an ISR or a task to another task. It is like a "Shoot
and forget" operation. The sending task or ISR sends the message and then hopes that another
task will receive it later on. The message queue also includes task synchronization in the way
that when a task sends a message and if there is a task waiting for messages from the message
queue, that task will also receive the message and then be unblocked. So there is no need to
inform the receiving task in another way about
the message.

one task (the producer task) is sending messages to a queue and another task (the consumer
task) is receiving messages.

Producer task wants or needs some kind of answer from the consumer task, e.g. the consumer
task has been asked to do some calculations or some formatting of data. Then a second queue
is added to which the consumer task can send the reply which then can be read by the
producer task.

If the consumer task only needs to signal to the producer task i.e. it does not need to send any
data, just signal that it is ready for the next message, then the second queue can be replaced
by a semaphore

In many applications there is a need for two or several tasks to be able to share data. This can
of course be done using a buffer protected by a semaphore, but many times it is much better
to use a message queue, as this also adds task synchronization and the possibility to queue the
data that another task does not have the possibility to handle at the moment.

What is a Message Queue?

A message queue is a number of buffers of a fixed or maximum size that is controlled by the
RTOS and also a queue for tasks that are waiting for messages. The size and the number of
buffers are specified when the message queue is created. The queue for tasks waiting is used
for queuing up tasks that are waiting for messages to become available. Normally you can
specify when you create the message queue in which order that the tasks should be waiting,
either in FIFO or in priority order.

Any task can send a message to the message queue, and many times it can specified if the
message should be placed at the tail of message queue or at the head of the message queue,
basically a possibility to give different messages different priority. Some RTOSs also have
the possibility to let a task decide if it wants to wait to send the message if the message queue
is already full. When the message is sent to the message queue, it is copied from the sending
task's buffer into a buffer that is controlled by the RTOS.

Any task can read a message from a message queue. If the message queue is empty the task
can decide if it wants to wait or not. When the message is received from the message queue, it
is copied from a buffer that is controlled by the RTOS to the receiving task's buffer. This
means that sending a message from one task to another task, the message has to be copied
twice, and this can of course be time consuming. So many times a message is just a pointer to
a buffer that holds the data.

Please notice that messages are sent to a queue, not to a task, and also received from a queue,
not from a task. But of course in many design it is obvious which tasks that are sending and
receiving the messages, but in some designs this may be decided during execution time.

Usage of a Message Queue

A message queue is used to send data from an ISR or a task to another task. It is like a "Shoot
and forget" operation. The sending task or ISR sends the message and then hopes that another
task will receive it later on. The message queue also includes task synchronization in the way
that when a task sends a message and if there is a task waiting for messages from the message
queue, that task will also receive the message and then be unblocked. So there is no need to
inform the receiving task in another way about
the message.

The RTOS does not care about what is the content of the message, it just copies the message
into one of its own buffers, and when a task wants to receive the message, then the message is
copied to the receiving task buffer. So the message can contain any type of data from the
complete set of data to a just a pointer to the data or sometimes just be a dummy message that
is simply used to unblock another task.

Design Examples
The most common design is that one task (the producer task) is sending messages to a queue
and another task (the consumer task) is receiving messages, see figure 1.

But sometimes the producer task wants or needs some kind of answer from the consumer task,
e.g. the consumer task has been asked to do some calculations or some formatting of data.
Then a second queue is added to which the consumer task can send the reply which then can
be read by the producer task, see figure 2.

If the consumer task only needs to signal to the producer task i.e. it does not need to send any
data, just signal that it is ready for the next message, then the second queue can be replaced
by a semaphore, see figure 3.
It is possible to have several tasks receiving messages from the same queue. It really does not
matter which task that really receives the message.

It is also possible for several tasks to send messages to the same queue, and there is only one
task receiving messages from that queue

If the clients need to receive any data back from the server, then the clients need to have a
separate queue for each client to which the server can send its reply.
 Inter Process Communication - Pipes
Pipe is a communication medium between two or more related or interrelated processes. It
can be either within one process or a communication between the child and the parent
processes. Communication can also be multi-level such as communication between the parent,
the child and the grand-child, etc. Communication is achieved by one process writing into the
pipe and other reading from the pipe. To achieve the pipe system call, create two files, one to
write into the file and another to read from the file.
Pipe mechanism can be viewed with a real-time scenario such as filling water with the pipe
into some container, say a bucket, and someone retrieving it, say with a mug. The filling
process is nothing but writing into the pipe and the reading process is nothing but retrieving
from the pipe.

This system call would create a pipe for one-way communication i.e., it creates two
descriptors, first one is connected to read from the pipe and other one is connected to write
into the pipe.

Algorithm
Step 1 − Create a pipe.
Step 2 − Send a message to the pipe.
Step 3 − Retrieve the message from the pipe and write it to the standard output.
Step 4 − Send another message to the pipe.
Step 5 − Retrieve the message from the pipe and write it to the standard output.

Two-way Communication Using Pipes

Pipe communication is viewed as only one-way communication i.e., either the parent process
writes and the child process reads or vice-versa but not both. However, what if both the parent
and the child needs to write and read from the pipes simultaneously, the solution is a two-way
communication using pipes. Two pipes are required to establish two-way communication.
Following are the steps to achieve two-way communication −
Step 1 − Create two pipes. First one is for the parent to write and child to read, say as pipe1.
Second one is for the child to write and parent to read, say as pipe2.
Step 2 − Create a child process.
Step 3 − Close unwanted ends as only one end is needed for each communication.
Step 4 − Close unwanted ends in the parent process, read end of pipe1 and write end of pipe2.
Step 5 − Close the unwanted ends in the child process, write end of pipe1 and read end of
pipe2.
Step 6 − Perform the communication as required.

Event Registers
RTOS provide a special register as part of each task’s control block. This register, called
an event register, is an object belonging to a task and consists of a group of binary event
flags used to track the occurrence of specific events. Depending on a given kernel’s
implementation of this mechanism, an event register can be 8-, 16-, or 32-bits wide, maybe
even more. Each bit in the event register is treated like a binary flag (also called an event flag)
and can be either set or cleared.

Through the event register, a task can check for the presence of particular events that can
control its execution. An external source, such as another task or an ISR, can set bits in the
event register to inform the task that a particular event has occurred.

Applications define the event associated with an event flag. This definition must be agreed
upon between the event sender and receiver using the event register.
 RTOS creates an event register control block as part of the task control block when creating
a task

The task specifies the set of events it wishes to receive. This set of events is maintained in
the wanted events register. Similarly, arrived events are kept in the received events register.
The task indicates a timeout to specify how long it wishes to wait for the arrival of certain
events. The kernel wakes up the task when this timeout has elapsed if no specified events
have arrived at the task.

Signals
A signal is a software interrupt that is generated when an event has occurred. It diverts the
signal receiver from its normal execution path and triggers the associated asynchronous
processing.
Essentially, signals notify tasks of events that occurred during the execution of other tasks or
ISRs. As with normal interrupts, these events are asynchronous to the notified task and do
not occur at any predetermined point in the task’s execution. The difference between a signal
and a normal interrupt is that signals are so-called software interrupts, which are generated
via the execution of some software within the system. By contrast, normal interrupts are
usually generated by the arrival of an interrupt signal on one of the CPU’s external pins. They
are not generated by software within the system but by external devices.

The number and type of signals defined is both system-dependent and RTOS-dependent. An
easy way to understand signals is to remember that each signal is associated with an event.
The event can be either unintentional, such as an illegal instruction encountered during
program execution, or the event may be intentional, such as a notification to one task from
another that it is about to terminate. While a task can specify the particular actions to
undertake when a signal arrives, the task has no control over when it receives signals.
Consequently, the signal arrivals often appear quite random.

When a signal arrives, the task is diverted from its normal execution path, and the
corresponding signal routine is invoked. The terms signal routine, signal
handler, asynchronous event handler, and asynchronous signal routine(ASR) are
interchangeable. Each signal is identified by an integer value, which is the signal
number or vector number.

Signal Operations

A task can catch a signal after the task has specified a handler for the signal. The catch
operation installs a handler for a particular signal. The kernel interrupts the task’s execution
upon the arrival of the signal, and the handler is invoked. The task can install the kernel-
supplied default handler, the default actions, for any signal. The task-installed handler has the
options of either processing the signal and returning control to the kernel or processing the
signal and passing control to the default handler for additional processing. Handling signals is
similar to handling hardware interrupts, and the nature of the ASR is similar to that of the
interrupt service routine.
Difference between Interrupt and Exception :

An interruption is a signal that is provided to the central processing unit (CPU) of the
computer from either an external device that is connected to the computer or a program that is
running on the system itself that requires the OS to intervene in the current process.

Both interrupts and exceptions are unanticipated events that can take place anywhere in the
system, the processor, or within a program and need the immediate attention of the central
processing unit (CPU). Both of these bring about an immediate halt to the ongoing flow of
instructions that are being carried out.

Interrupt Exception

These are Hardware interrupts. These are Software Interrupts.

Occurrences of hardware interrupts usually This is not a true case in terms of Exception.
disable other hardware interrupts.

These are asynchronous external requests for These are synchronous internal requests for
service (like keyboard or printer needs service). service based upon abnormal events (think of
illegal instructions, illegal address, overflow
etc).

Being asynchronous, interrupts can occur at any Being synchronous, exceptions occur when
place in the program. there is abnormal event in your program like,
divide by zero or illegal memory location.

These are normal events and shouldn’t interfere These are abnormal events and often result in
with the normal running of a computer. the termination of a program