Unit III

3.1 INTRODUCTION TO REAL TIME SYSTEMS

A real-time system is designed as an embedded component; it is called a real-time embedded
system.A single real-time application can be composed of both soft and hard real-time components. A
typical example of a hard real-time system is a nuclear reactor control system that must not only
detect failures, but must also respond quickly enough to prevent a meltdown.

Figure 3.1 Real Time System

 Examples of real-time systems include;
 Software for cruise missile
 Heads-up cockpit display
 Airline reservation system
 Industrial Process Control
 Banking ATM
 Real-time systems can also be found in many industries like;
 Defense systems
 Telecommunication systems
 Automotive control
 Signal processing systems
 Radar systems
 Automated manufacturing systems
 Air traffic control
 Satellite systems
 Electrical utilities
Real time processes may be classified as follows:
 Hard Real Time Tasks: A real time task is said to be hard if missing its deadline may cause
catastrophic consequences on the environment under control.

Page 1
  Soft Real Time Tasks: A real time task is said to be soft if meeting its deadline is desirable for
performance reasons, but missing its deadline does not cause serious damage to the environment and
does not jeopardize correct system behavior.
 Real-time embedded systems have a complex set of characteristics that distinguish them from other software
applications. Real-time embedded systems are driven by and must respond to real world events while
adhering to rigorous requirements imposed by the environment with which they interact. The correctness of
the system depends not only on the results of computations, but also on the time at which the results are
produced. The most important and complex characteristic of real-time application systems is that they must
receive and respond to a set of external stimuli within rigid and critical time constraints.
 However, many real-time systems cannot afford the delay incurred by lengthy interrupt service routines.
Hence, the processing logic for an external request is typically split into two portions: the portion that is
necessary to acknowledge the hardware request is handled in the interrupt service routine, whereas most of
the processing logic is separated into a so-called deferred task code. This exposes a limitation of the round-
robin architecture with interrupts: the processing order of those deferred task codes is still fixed at design
time due to the round-robin nature.
 In a high-performing real-time system, it may be necessary to process tasks how important or urgent they
are. Two dynamic queue-based architectures are then introduced: one is based on an FIFO queue and the
other employs a priority queue. However, regardless of the type of the task queue being used, once it is
adopted by a system, the queuing policy is fixed, and the whole system has to stick with it at run time. The
understanding of such a limitation helps us to further examine RTOS.
 Another design principle in real-time systems is predictability of the system behavior. Predictability depends
on the timing constraints of the real-time tasks identified or derived from the domain problem at hand. Thus
addressing priority inversion and resource deadlocks.
 There are two types of real-time systems: reactive and embedded. Reactive real-time system involves a
system that has constant interaction with its environment. (e.g. a pilot controlling an aircraft). An embedded
real-time system is used to control specialized hardware that is installed within a larger system. (e.g. a
microprocessor that controls the fuel-to-air mixture for automobiles).
Real-time events fall into one of the three categories: asynchronous, synchronous, or isochronous.
Asynchronous events are entirely unpredictable. For example, the event that a user makes a telephone call. As far as
the telephone company is concerned, the action of making a phone call cannot be predicted.
Synchronous events are predictable and occur with precise regularity if they are to occur. For example, the audio
and video in a movie take place in synchronous fashion.
Isochronous events occur with regularity within a given window of time. For example, audio bytes in a distributed
multimedia application must appear within window of time when the corresponding video stream arrives.
Isochronous is asub-class of asynchronous.

Page 2
The Characteristics are:
Large and Complex – Vary from a few hundred lines of assembler or c to 20 million lines of Ada
estimated for the space station freedom.
Manipulation of real numbers
Reliable and safe – embedded system typically control the environment in which they operate; failure to
control can result in loss of life, damage to environment or economic loss.
Concurrent control of separate system components –devices operate in parallel in the real-world; better
to model this parallelism by concurrent entities in the program.
Real-time Facilities
Interaction with hardware devices – need to be able to program devices in a reliable and abstract
way.
Efficient execution and the execution environment – We need to be able to predict with confidence the
worst case response times for systems; efficiency is important but predictability is essential.
3.1.1 Issues in Real Time Computing
In any real time application, the various control activities can be seen as members of a team acting together
to accomplish one common goal, which can be the control of a nuclear power plant or an aircraft. This means that
the tasks are not all independent and it is strictly necessary to support independent address spaces and a high degree
of predictability. Some very important properties that real time systems should have to support critical applications
are:
 Timeliness: Results have to be correct not only in their value but also in the time domain. As a
consequence, the operating system must provide specific kernel mechanisms for time management and
handling tasks with explicit time constraints and different criticalness.
 Design for Peak Load: Real time systems must not collapse when they are subject to peak load
conditions, so they must be designed to handle all anticipated scenarios.
 Predictability: To guarantee a minimum level of performance, the system must be able to predict the
consequence of any scheduling decision. If some task cannot be guaranteed within its time constraints,
the system must notify this fact in advance, so that alternative actions can be planned in order to cope
with the situation.
 Fault Tolerance: single hardware and software failures should not cause the system to crash. Thus,
critical components of real time systems have to be designed to be fault tolerant.
 Maintainability: the architecture of a real time system should be designed according to a modular
structure to ensure that possible system modifications are easy to perform.
3.1.2 Real Time Operating System:

Page 3
  An operating system (OS) is system software that manages hardware and software resources
and provides common services for computer programs. All computer programs excluding
firmware, require an operating system to function.
 The OS may be a bare-bone microkernel to ensure that input events are processed with
minimum overhead.
 Unix or Windows are operating systems that have been designed with no specific class of
applications in mind. These are robust, (like all terrain vehicles), but not suitable for real time
operations (say Formula 1 cars).
 Their performance in real-time domain would be like that of an all terrain vehicle on a formula
one race track. Note that the timeliness in response is crucial in real-time operations.
 General-purpose operating systems are designed to enhance throughput. Often it has
considerable leeway in responding to events. Also, within a service type, the general-purpose
OS cater to a very vast range of services.
 For example, just consider the print service. There is considerable leeway with regard to system
response time. Additionally, the printer service may cater to a vast category of print devices
which range from ink-jet to laser printing or from gray scale to color printing. In other words,
the service rendering code is long. Additionally, it caters to a large selection in printer devices.
This makes service rendering slow. Also, a few seconds of delay in printing matters very little,
if at all. Real-time operative environments
 Real-Time Operating System: An RTOS is an OS for response time-controlled and event-
controlled processes. It is very essential for large scale embedded systems. RTOS occupy little
space from 10 KB to 100KB The main task of a RTOS is to manage their sources of the
computer such that a particular operation executes in precisely the same amount of time every
time it occur.
 Software for a large number of small-scale embedded system use no RTOS and these functions
are incorporated into the application software. For small-scaled systems, RTOS‘s function can
be replaced by C. For example, instead of the memory allocation and de-allocation functions of
RTOS, the C function and free can be used. Software can directly handle inter-process
communication
 However, RTOS is essential when a common and effective way of handling of the hardware
source calls from the interrupts I/O management with devices, files, mailboxes becomes simple

Page 4
 using an RTOS Effectively scheduling and running and blocking of the tasks in cases of many
tasks and many more
 In conclusion, an RTOS may not be necessary in a small-scaled embedded system. An RTOS is
necessary when scheduling of multiple processes and devices is important.
All operating systems must provide three specific functions: −
 Task management
 Task scheduling
 Inter task communication
Rea-Time kernels must provide:
 Interrupt handling, guaranteed interrupt response
 Process management (Support for scheduling of real-time processes and preemptive scheduling)
 Inter process communication and synchronization.
 Time management.
 Memory management
 I/O support (Support for communication with peripheral devices via drivers)
 High speed data acquisition
 Resource management (User control of system resources)
 Error and exception handling
3.1.3 Features of Real time Operating System:
 A real-time OS should provide support for the creation, deletion and scheduling of multiple
processes
 A real-time OS must be able to response an event and take deterministic (well-defined in terms
of function and time) action based on the event.
 A real-time OS should support inter process communications via reliable and fast facilities, such
as semaphores, shared memory and message passing.
 A real-time system must be able to handle very high burst rates in high speed data acquisition
applications.
3.2 Structure of a Real Time System
The state of the controlled process and of the operating environment (e.g pressure, temperature,
speed and altitude) is acquired by sensors, which provides inputs to the controller, the real time computer. The
Data from each sensor depends on how quickly the measured parameters can change; it is usually less than
1Kb/second.

Page 5
3.2.1 Process Concepts
A process consists of executable program (codes), state of which is controlled by OS the state during
running of a process represented by process-status (running, blocked or finished), process structure—its data,
objects and resources and process control block (PCB).

Figure 3.2 Structure of a Real Time System

 Runs when it is scheduled to run by the OS (kernel).OS gives the control of the CPU on a process‗s
request (system call).
 Runs by executing the instructions and the continuous changes of its state takes Place as the program
counter (PC) changes.
 Process is that executing unit of computation, which is controlled by some process (of the OS) for a
scheduling mechanism that lets it execute on the CPU and by some process at OS for a resource
management mechanism that lets it use the system memory and other system resources such as network,
file, display or printer.
3.2.2 Application program can be said to consist of number of processes
Example - Mobile Phone Device embedded software
 Software highly complex.
 Number of functions, ISRs, processes threads, multiple physical and virtual device drivers, and
several program objects that must be concurrently processed on a single processor.
 Voice encoding and convoluting process─ the device captures the spoken words through a speaker
and generates the digital signals after analog to digital conversion, the digits are encoded and
convoluted using a CODEC,
 Modulating process,
 Display process,
 GUIs (graphic user interfaces), and
 Key input process ─ for provisioning of the user interrupts
Process Control Block
 A data structure having the information using which the OS controls the Process state.
 Stores in protected memory area of the kernel.
 Consists of the information about the process state

Page 6
Information about the process state at Process Control Block…
Process ID,
o process priority,
o Parent process (if any),
o child process (if any), and
o Address to the next process PCB which will run,
o Allocated program memory address blocks in physical memory and in secondary virtual) memory
for the process-codes,
o Allocated process-specific data address blocks
o Allocated process-heap (data generated during the program run) addresses,
o Allocated process-stack addresses for the functions called during running of the process,
o Allocated addresses of CPU register-save area as a process context represents by CPU registers,
which include the program counter and stack pointer
o Allocated addresses of CPU register-save area as a process context [Register-contents (define
process context) include the program counter and stack pointer contents]
o Process-state signal mask [when mask is set to 0 (active) the process is inhibited from running and
when reset to 1, the process is allowed to run],
o Signals (messages) dispatch table [process IPC functions],
o OS allocated resources‗ descriptors (for example, file descriptors for open files, device descriptors
for open (accessible) devices, device-buffer addresses and status, socket descriptor for open socket),
and Security restrictions and permissions.
Context
o Context loads into the CPU registers from memory when process starts running, and the registers save at
the addresses of register-save area on the context switch to another process
o The present CPU registers, which include program counter and stack pointer are called context
o When context saves on the PCB pointed process-stack and register-save area addresses, then the running
process stops.
o Other process context now loads and that process runs─ This means that the context has switched.
3.3 Threads and Tasks
3.3.1 Thread Concepts
o A thread consists of executable program (codes), state of which is controlled by OS,
o The state information─ thread-status (running, blocked, or finished), thread structure—its data, objects and a
subset of the process resources, and thread-stack. Considered a lightweight process and a process level
controlled entity. [Light weight means its running does not depend on system resources] .

Page 7
 Figure.3.3 Threads and Tasks

3.3.2 Process… Heavy Weight

• Process considered as a heavyweight process and a kernel-level controlled entity.
• Process thus can have codes in secondary memory from which the pages can be swapped into the
physical primary memory during running of the process. [Heavy weight means its running may depend
on system resources]
• May have process structure with the virtual memory map; file descriptors, user–ID, etc.
• Can have multiple threads, which share the process structure thread
• A process or sub-process within a process that has its own program counter, its own stack pointer and
stack, its own priority parameter for its scheduling by a thread scheduler
• Its variables that load into the processor registers on context switching.
• Has own signal mask at the kernel. Thread‗s signal mask
• When unmasked lets the thread activate and run.
• When masked, the thread is put into a queue of pending threads.
3.3.3 Thread‘s Stack
• A thread stack is at a memory address block allocated by the OS.
Application program can be said to consist of number of threads or Processes:
1. Multiprocessing OS
• A multiprocessing OS runs more than one processes.
• When a process consists of multiple threads, it is called multithreaded process.
• A thread can be considered as daughter process.
• A thread defines a minimum unit of a multithreaded process that an OS schedules On to the CPU and allocates
other system resources.
2.Thread parameters

Page 8
 • Each thread has independent parameters ID, priority, program counter, stack pointer, CPU registers and
its present status.
• Thread states─ starting, running, blocked (sleep) and finished
3. Thread’s stack
• When a function in a thread in OS is called, the calling function state is placed on the stack top.
• When there is return the calling function takes the state information from the stack top
• A data structure having the information using which the OS controls the thread state.
• Stores in protected memory area of the kernel.
• Consists of the information about the thread state
4. Thread and Task
• Thread is a concept used in Java or Unix.
• A thread can either be a sub-process within a process or a process within an application program.
• To schedule the multiple processes, there is the concept of forming thread groups and thread libraries.
• A task is a process and the OS does the multitasking.
• Task is a kernel-controlled entity while thread is a process-controlled entity.
• A thread does not call another thread to run. A task also does not directly call another task to run.
• Multithreading needs a thread-scheduler. Multitasking also needs a task-scheduler.
• There may or may not be task groups and task libraries in a given OS

3.3.4 Task and Task States

• An application program can also be said to be a program consisting of the tasks and task behaviors in
various states that are controlled by OS.
• A task is like a process or thread in an OS.
• Task─ term used for the process in the RTOSes for the embedded systems. For example, VxWorks and
μCOS-II are the RTOSes, which use the term task.
• A task consists of executable program (codes), state of which is controlled by OS, the state during
running of a task represented by information of process status (running, blocked, or finished),process-
structure—its data, objects and resources, and task control block (PCB).
• Runs when it is scheduled to run by the OS (kernel), which gives the control of the CPU on a task
request (system call) or a message., Runs by executing the instructions and the continuous changes of its
state takes place as the program counter (PC) changes.
• Task is that executing unit of computation, which is controlled by some process at the OS scheduling
mechanism, which lets it execute on the CPU and by some process at OS for a resource-management

Page 9
 mechanism that lets it use the system memory and other system-resources such as network, file, display
or printer.

Figure 3.4 Task and Task States

 The Tasks in embedded program is shown in figure 3.4 above.
• A task─ an independent process.
• No task can call another task. [It is unlike a C (or C++) function, which can call another function.]
• The task─ can send signal (s) or message(s) that can let another task run.
• The OS can only block a running task and let another task gain access of CPU to run the servicing
codes
3.3.5 Task States
(i) Idle state [Not attached or not registered]
(ii) Ready State [Attached or registered]
(iii) Running state
(iv) Blocked (waiting) state
(v) Delayed for a preset period

Figure 3.5 Task States

1.Idle (created) state

• The task has been created and memory allotted to its structure however, it is not ready and is not
schedulable by kernel.
2.Ready (Active) State
• The created task is ready and is schedulable by the kernel but not running at present as another higher
priority task is scheduled to run and gets the system resources at this instance.
3.Running state
• Executing the codes and getting the system resources at this instance. It will run till it needs some IPC
(input) or wait for an event or till it gets pre-empted by another higher priority task than this one.
4.Blocked (waiting) state

Page 10
 • Execution of task codes suspends after saving the needed parameters into its Context. It needs some
IPC (input) or it needs to wait for an event or wait for higher priority task to block to enable running
after blocking.
5. Deleted (finished) state
• Deleted Task─ The created task has memory de allotted to its structure. It frees the memory. Task has
to be re-created.
3.3.6 TASK PERIODICITY
An embedded system is generally designed to cater to a specific application, or a small number of applications.
Thus, it normally consists of a small set of tasks. For example, a monitoring system continuously monitors its
environment and takes appropriate actions based on inputs.
Such a system will generally consist of a set of tasks to be performed at some regular interval of time. However
there may be some other tasks which or not periodic in nature. Based on this periodicity property, tasks in a
system can be classified into three categories—periodic, sporadic and aperiodic. In the following section, we
describe the essential features of each of them.
3.3.7 PERIODIC TASKS
A periodic task repeats itself regularly after a certain fixed time interval. Such a task Ti can be characterized by
four factors—φi the phase, di the deadline, eithe execution time , and pi the periodicity. The phase (φi) identifies
the first time instant at which the tastTi occurs. For a particular occurrence of the task, the deadline di is the time
by which the task must be completed, relative to the start time. The actual time required to execute the task in the
worst case is ei, which must be smaller than di. Finally, pi identifies the periodicity of the task. Thus the task T i
can be represented by the four-tuple <φi ,di, ei , pi >. The situation has been shown in Fig. 6.3.
It may be noted that most of the task in the real-time embedded system are periodic in nature, parameters
of these tasks can be computed beforehand. It is the responsibility of the designer of the system to ensure the
availability of proper resources at these times so that each instances of a periodic task can complete before the
deadline. Sometimes, the deadline di is taken to be same as the periodicity pi, as no further instances of the task
ca arrive in between.

3.3.8SPORADIC TASKS
As the name suggests, a sporadic task can arrive at any instant of time. However, after the occurrence of one
instance, there is a minimum separation, only after which another instance of the task can arrive. Thus a sporadic
task can be represented by the three-tuple<ei ,gi,di> where eiis the worst case execution time of an instance of the
task, gi denotes the minimum separation between two consecutive instances of the task and d i is the relative
deadline. Examples of sporadic tasks are the interrupts which may be generated from different conditions, inside
or outside the system. The criticality level may vary. A fire-alarm occurs sporadically, however, it is very critical

Page 11
and be handled within a fixed time interval. On the other hand, an I/O device interrupt may not be that critical.
Figure 6.4 shows the behavior of a sporadic task with execution time e, deadline d and minimum separation
between two occurrences g. As shown in Fig. 5.4 the next instances of the task can arrive only after g time units
of the occurrence of the previous instance.
3.3.9 APERIODIC TASKS
Aperiodic task are similar to the sporadic ones in the sense that both types of tasks can arrive at any
random time. However, unlike sporadic tasks, there is no guarantee that another instances of the task will not
arrive before a minimum amount of time expires. That is, successive instances of aperiodic tasks may occur even
at consecutive time instants. Naturally, it is not possible to assign a tight deadline with these tasks. The deadline
can be expressed either as an average value or some statically expected value. In other sense, aperiodic tasks
have to be soft real-time ones, as successive occurrence of instances of aperiodic tasks may lead to missing
deadlines for some of them. These deadline misses can be tolerated by soft real-time tasks.
A typical example of aperiodic task is railway-reservation system. As booking is done over a large number of
terminals, there is no periodic gap between two such taks being initiated. At the same time, the deadline
requirement is also an expected value only about the average time needed to process the ticketing requests.
3.4 TASK SCHEDULING

The illusion that all the tasks are running concurrently is achieved by allowing each to have a share of the
processor time. This is the core functionality of a kernel. The way that time is allocated between tasks is termed
―scheduling‖.
The scheduler is the software that determines which task should be run next. The logic of the scheduler and the
mechanism that determines when it should be run is the scheduling algorithm. The intention here is to just give
sufficient introduction that you can understand what a given RTOS has to offer in this respect.
3.4.1 Run to Completion (RTC) Scheduler
RTC scheduling is very simplistic and uses minimal resources. It is, therefore, an ideal choice, if the
application‘s needs are fulfilled. Here is the timeline for a system using RTC scheduling:

Figure 3.6 Task Scheduling

The scheduler simply calls the top level function of each task in turn. That task has control of the CPU (interrupts
aside) until the top level function executes a return statement. If the RTOS supports task suspension, then any
tasks that are currently suspended are not run. This is a topic discussed below; see Task Suspend.

Page 12
The big advantages of an RTC scheduler, aside from its simplicity, are the need for just a single stack and the
portability of the code (as no assembly language is generally required). The downside is that a task can ―hog‖ the
CPU, so careful program design is required. Although each task is started ―from the top‖ each time it is
scheduled – unlike other kinds of schedulers which allow the code to continue from where it left off – greater
flexibility may be programmed by use of static ―state‖ variables, which determine the logic of each
sequential call.
3.4.2 Round Robin (RR) Scheduler
An RR scheduler is similar to RTC, but more flexible and, hence, more complex. In the same way, each task is
run in turn (allowing for task suspension), thus:

Figure 3.7 Round Robin (RR) Scheduler

However, with the RR scheduler, the task does not need to execute a return in the top level function. It can
relinquish the CPU at any time by making a call to the RTOS. This call results in the kernel saving the context
(all the registers – including stack pointer and program counter) and loading the context of the next task to be
run. With some RTOS-ES, the processor may be relinquished – and the task suspended – pending the availability
of a kernel resource. This is more sophisticated, but the principle is the same.
The greater flexibility of the RR scheduler comes from the ability for the tasks to continue from where they left
off without any accommodation in the application code. The price for this flexibility is more complex, less
portable code and the need for a separate stack for each task.
3.4.3 Time Slice (TS) Scheduler
A TS scheduler is the next step in complexity from RR. Time is divided into ―slots‖, with each task being
allowed to execute for the duration of its slot, thus:

Figure 3.8 Time Slice (TS) Scheduler

In addition to being able to relinquish the CPU voluntarily, a task is pre-empted by a scheduler call made from a
clock tick interrupt service routine. The idea of simply allocating each task a fixed time slice is very appealing –
for applications where it fits the requirements – as it is easy to understand and very predictable. The only
Page 13
downside of simple TS scheduling is the proportion of CPU time allocated to each task varies, depending upon
whether other tasks are suspended or relinquish part of their slots, thus:

Figure 3.8 Time Slice (TS) Scheduler with Clock Tick Interrupt Service Routine

A more predictable TS scheduler can be constructed if the concept of a ―background‖ task is introduced. The
idea, shown here, is for the background task to be run instead of any suspended tasks and to be allocated the
remaining slot time when a task relinquishes (or suspends itself).
Obviously the background task should not do any time-critical work, as the amount of CPU time it is allocated is
totally unpredictable – it may never be scheduled at all.
This design means that each task can predict when it will be scheduled again. For example, if you have 10ms
slots and 10 tasks, a task knows that, if it relinquishes, it will continue executing after 100ms. This can lead to
elegant timing loops in application tasks.
An RTOS may offer the possibility for different time slots for each task. This offers greater flexibility, but is just
as predictable as with fixed slot size. Another possibility is to allocate more than one slot to the same task, if you
want to increase its proportion of allocated processor time.
3.4.4 Priority Scheduler
Most RTOS-ES support Priority scheduling. The idea is simple: each task is allocated a priority and, at any
particular time, whichever task has the highest priority and is ―ready‖ is allocated the CPU, thus:

Figure 3.9 Priority Scheduler

The scheduler is run when any ―event‖ occurs (e.g. interrupt or certain kernel service calls) that may cause a
higher priority task being made ―ready‖. There are broadly three circumstances that might result in the scheduler
being run:

Page 14
  The task suspends itself; clearly the scheduler is required to determine which task to run next.
 The task readies another task (by means of an API call) of higher priority.
 An interrupt service routine (ISR) readies another task of higher priority. This could be an input/output
device ISR or it may be the result of the expiration of a timer (which are supported my many RTOS-ES
– we will look at them in detail in a future article).
The number of levels of priority varies (from 8 to many hundreds) and the significance of higher and lower
values differs; some RTOS-ES use priority 0 as highest, others as lowest.
Some RTOS-ES only allow a single task at each priority level; others permit multiple tasks at each level, which
complicates the associated data structures considerably. Many OS-ES allow task priorities to be changed at
runtime, which adds further complexity.
3.4.5 Composite Scheduler
We have looked at RTC, RR, TS and Priority schedulers, but many commercial RTOS products offer more
sophisticated schedulers, which have characteristics of more than one of these algorithms. For example, an
RTOS may support multiple tasks at each priority level and then use time slicing to divide time between multiple
ready tasks at the highest level.
1.Task States
At any one moment in time, just one task is actually running. Aside from CPU time spent running interrupt
service routines (more on that in the next article) or the scheduler, the ―current‖ task is the one whose code is
currently being executed and whose data is characterized by the current register values. There may be other tasks
that are ―ready‖ (to run) and these will be considered when the scheduler is executed. In a simple RTOS, using a
Run to Completion, Round Robin or Time Slice scheduler, this may be the whole story. But, more commonly,
and always with a Priority scheduler, tasks may also be in a ―suspended‖ state, which means that they are not
considered by the scheduler until they are resumed and made ―ready‖.
2.Task Suspend
Task suspension may be quite simple – a task suspends itself (by making an API call) or another task suspends it.
Another API call needs to be made by another task or ISR to resume the suspended task. This is an
―unconditional‖ or ―pure‖ suspend. Some OSes refer to a task as being ―asleep‖.
An RTOS may offer the facility for a task to suspend itself (go to sleep) for a specific period of time, at the end
of which it is resumed (by the system clock ISR, see below). This may be termed ―sleep suspend‖.
Another more complex suspend may be offered, if an RTOS supports ―blocking‖ API calls. Such a call permits
the task to request a service or resource, which it will receive immediately if it is available, otherwise it is
suspended until it is available. There may also be a timeout option whereby a task is resumed if the resource is
not available in a specific timeframe.

Page 15
3.Other Task States
Many RTOS-ES support other task states, but the definition of these and the terminology used varies.
Possibilities include a ―finished‖ state, which simply means that the task‘s outermost function has exited (either
by executing a return or just ending the outer function block). For a finished task to run again, it would probably
need to be reset in some way.
Another possibility is a ―terminated‖ state. This is like a pure suspend, except that the task must be reset to its
initial state in order to run again.
If an RTOS supports dynamic creation and deletion of tasks (see the next article), this implies another
possible task state: ―deleted‖.
3.4.6 Classification of Scheduling Algorithms
Based on the scheduling points,scheduling algorithms can be classified into the following categories:
1. Clock driven scheduling
2. Event driven scheduling
3. Hybrid scheduling

3.4.7 Clock driven scheduling

 Clock-driven is also called as static or off-line scheduling

 It is sufficient to have a hardware timer (no need for OS)
 Regularly spaced time instants are popular Schedule is computed off-line and stored for use at run-time
All parameters of hard real-time jobs are fixed and known
 Scheduling overhead during run time is minimal Complexity of the scheduling algorithm is not
important
 Good (optimal) off-line schedules can be found
 Disadvantage: No flexibility
 Applicable only when we know all about the system in advance Fixed set of tasks, fixed and known task
parameters and resource requirements
 Met by many safety-critical applications
 Easier to certify
For this case, we will consider the following periodic model:
 n periodic tasks τ1, . . . , τn; n is constant
 We assume the ―rest of world‖ model. τi is specified with tuple (φi ,Ti , Ci , Di),
 whereφi is task phase, Ti is task period, Ci is execution time of τi and Di is relative deadline.
 We will shorten this as (Ti , Ci , Di), if φi = 0 and as (Ti , Ci) if φi = 0 ∧Ti = Di .
 In addition, we consider aperiodic jobs released in arbitrary instants.

Page 16
  Later, we will look at sporadic tasks as well.
 We are interested in scheduling for one processor.

3.4.7 Schedule table:

 The scheduler will schedule periodic tasks according to a static schedule, which is computed offline and
stored in a table.
 Every element of the table specifies decision time and scheduled task. If no task is to be scheduled, the
special symbol × (idle) is stored there.
 We will look at a simple algorithm how to construct the schedule later.
 Note: This algorithm need not be highly efficient (it runs off-line). Aperiodic jobs can be scheduled at
idle intervals.
3.4.7 Rate-monotonic Scheduling:
Rate-monotonic scheduling (RMS) is a scheduling algorithm used in real-time operating
systems (RTOS) with a static-priority scheduling class. The static priorities are assigned according to the cycle
duration of the job, so shorter cycle duration results in a higher job priority. These operating systems are
generally preemptive and have deterministic guarantees with regard to response times. Rate monotonic analysis
is used in conjunction with those systems to provide scheduling guarantees for a particular application.
Rate-monotonic scheduling (RMS) is a scheduling algorithm used in real-time operating
systems (RTOS) with a static-priority scheduling class. The static priorities are assigned according to the cycle
duration of the job, so shorter cycle duration results in a higher job priority.
These operating systems are generally preemptive and have deterministic guarantees with regard to response
times. Rate monotonic analysis is used in conjunction with those systems to provide scheduling guarantees for a
particular application.
 A simple version of rate-monotonic analysis assumes that threads have the following properties:
 Deterministic deadlines are exactly equal to periods
 Static priorities (the task with the highest static priority that is runnable immediately preempts all other
tasks)
 Static priorities assigned according to the rate monotonic conventions (tasks with shorter
periods/deadlines are given higher priorities)
 Context switch times and other thread operations are free and have no impact on the model
The schedulability test for RMS is:

Let's consider a static priority scheduling algorithm. With two tasks, there are only two possibilities:

Page 17
Case 1: Priority(t1) > Priority(t2)
Case 2: Priority(t1) <(t2)
In Case 1, both tasks meet their respective deadlines. In Case 2, however, t 1 misses a deadline, despite 10% idle
time. This illustrates the importance of priority assignment.

Figure 3.10 Rate-monotonic Scheduling

The rate monotonic algorithm (RMA) is a procedure for assigning fixed priorities to tasks to maximize their
"schedulability." A task set is considered schedulable if all tasks meet all deadlines all the time. The algorithm is
simple:
Assign the priority of each task according to its period, so that the shorter the period the higher the priority.
In the example, the period of t1 is shorter than the period of t2. Following RMA's rule, we assign the higher
priority to t1. This corresponds to Case 1 in Figure 1, which is the priority assignment that succeeded in meeting
all deadlines.
RMA is the optimal fixed-priority algorithm. If a task set cannot be scheduled using the RMA algorithm, it
cannot be scheduled using any fixed-priority algorithm.
One major limitation of fixed-priority scheduling is that it is not always possible to fully utilize the CPU. Even
though RMA is the optimal fixed-priority scheme, it has a worst-case schedule bound of:
3.5 Earliest deadline first scheduling
Earliest deadline first (EDF) or least time to go is a dynamic scheduling algorithm used in real-time
operating systems to place processes in a priority queue. Whenever a scheduling event occurs (task finishes, new
task released, etc.) the queue will be searched for the process closest to its deadline. This process is the next to be
scheduled for execution.

Page 18
 EDF is an optimal scheduling algorithm on preemptive uni-processors, in the following sense: if a
collection of independent jobs, each characterized by an arrival time, an execution requirement and a deadline,
can be scheduled (by any algorithm) in a way that ensures all the jobs complete by their deadline, the EDF will
schedule this collection of jobs so they all complete by their deadline.With scheduling periodic processes that
have deadlines equal to their periods, EDF has a utilization bound of 100%.

The schedulability test for EDF is given by U=∑Ci/Ti<=1 (where n ranging from i=1 to n)

Where Ci the worst-case computation-times of the n processes and the Ti are their respective inter-arrival periods
(assumed to be equal to the relative deadlines).

That is, EDF can guarantee that all deadlines are met provided that the total CPU utilization is not more
than 100%. Compared to fixed priority scheduling techniques like rate-monotonic scheduling, EDF can
guarantee all the deadlines in the system at higher loading.
However, when the system is overloaded, the set of processes that will miss deadlines is largely
unpredictable (it will be a function of the exact deadlines and time at which the overload occurs.) This is a
considerable disadvantage to a real time systems designer. The algorithm is also difficult to implement
in hardware and there is a tricky issue of representing deadlines in different ranges. If a modular arithmetic is
used to calculate future deadlines relative to now, the field storing a future relative deadline must accommodate
at least the value of the (("duration" {of the longest expected time to completion} * 2) + "now").
Therefore EDF is not commonly found in industrial real-time computer systems.

Instead, most real-time computer systems use fixed priority scheduling (usually rate-monotonic
scheduling). With fixed priorities, it is easy to predict that overload conditions will cause the low-priority
processes to miss deadlines, while the highest-priority process will still meet its deadline.There is a significant
body of research dealing with EDF scheduling in real-time computing; it is possible to calculate worst case
response times of processes in EDF, to deal with other types of processes than periodic processes and to use
servers to regulate overloads.
3.5.1 Inter Process Communication
Since processes needs to communicate frequently with other processes therefore, there is a need for a well-
structured communication, without using interrupts, among processes.
 Race Conditions
In operating systems, processes that are working together share some common storage (main memory, file etc.)
that each process can read and write. When two or more processes are reading or writing some shared data and
the final result depends on who runs precisely when, are called race conditions. Concurrently executing threads
that share data need to synchronize their operations and processing in order to avoid race condition on shared
data. Only one ‗customer‘ thread at a time should be allowed to examine and update the shared variable.
Race conditions are also possible in Operating Systems. If the ready queue is implemented as a linked list and if

Page 19
the ready queue is being manipulated during the handling of an interrupt, then interrupts must be disabled to
prevent another interrupt before the first one completes. If interrupts are not disabled than the linked list could
become corrupt.
 Critical Condition

Figure 3.11 Critical Section

The key to preventing trouble involving shared storage is find some way to prohibit more than one process from
reading and writing the shared data simultaneously. That part of the program where the shared memory is
accessed is called the Critical Section. To avoid race conditions and flawed results, one must identify codes in
Critical Sections in each thread.
The characteristic properties of the code that form a Critical Section are
 Codes that reference one or more variables in a ―read-update-write‖ fashion while any of those variables is
possibly being altered by another thread.
 Codes that alter one or more variables that are possibly being referenced in ―read-updata-write‖ fashion by
another thread.
 Codes use a data structure while any part of it is possibly being altered by another thread.
 Codes alter any part of a data structure while it is possibly in use by another thread.
Here, the important point is that when one process is executing shared modifiable data in its critical section,
no other process is to be allowed to execute in its critical section. Thus, the execution of critical sections by
the processes is mutually exclusive in time.
 Mutual Exclusion
A way of making sure that if one process is using a shared modifiable data, the other processes will be excluded
from doing the same thing.
Formally, while one process executes the shared variable, all other processes desiring to do so at the same time
moment should be kept waiting; when that process has finished executing the shared variable, one of the
processes waiting; while that process has finished executing the shared variable, one of the processes waiting to
do so should be allowed to proceed. In this fashion, each process executing the shared data (variables) excludes
all others from doing so simultaneously. This is called Mutual Exclusion. Note that mutual exclusion needs to be

Page 20
enforced only when processes access shared modifiable data - when processes are performing operations that do
not conflict with one another they should be allowed to proceed concurrently.
3.5.2 Mutual Exclusion Conditions
If we could arrange matters such that no two processes were ever in their critical sections simultaneously, we
could avoid race conditions. We need four conditions to hold to have a good solution for the critical section
problem (mutual exclusion).
 No two processes may at the same moment inside their critical sections.
 No assumptions are made about relative speeds of processes or number of CPUs.
 No process should outside its critical section should block other processes.
 No process should wait arbitrary long to enter its critical section.
3.5.3 Task and Data
Each task has its own private context, which includes the register values, a program counter, and a stack.
However, all other data - g1obal, static, initialized, uninitialized, and everything else - is shared among all of
the tasks in the system. The RTOS typically has its own private data structures, which are not available to
any of the tasks. Since you can share data variables among tasks, it is easy to move data from one task to
another: the two tasks need only have access to the same variables.
 You can easily accomplish this by having the two tasks in the same module in which the variables are
declared, or you can make the variables public in one of the tasks and declare them extern in the other.
1.Shared – Data Problems
 If we have two tasks sharing the same data, it could happen that one of this tasks will read the half-changed
data.
2. Reentrancy

Reentrant functions are functions that can be called by more than one task and that will always work
correctly even if the RTOS switches from one task to another in the middle of executing the function.
Apply three rules to decide if a function is reentrant:
1. A reentrant function may not use variables in a non-atomic way unless they are stored on the stack of
the task that called. the function or are otherwise the private variables of that task.
2. A reentrant function may not call any other functions that are not themselves reentrant.
3. A reentrant function may not use the hardware in a non-atomic way.
3.Semaphore
Semaphores are useful either for synchronizing execution of multiple tasks or for coordinating access to a shared
resource. The following examples and general discussions illustrate using different types of semaphores to
address common synchronization design requirements effectively, as listed:
 wait-and-signal synchronization,
 multiple-task wait-and-signal synchronization,

Page 21
  credit-tracking synchronization,
 single shared-resource-access synchronization,
 recursive shared-resource-access synchronization, and
 multiple shared-resource-access synchronization.
4.Wait-and-Signal Synchronization
Two tasks can communicate for the purpose of synchronization without exchanging data. For example, a binary
semaphore can be used between two tasks to coordinate the transfer of execution control, as shown in Figure
below.

Figure 3.12 Wait-and-signal synchronization between two tasks.

In this situation, the binary semaphore is initially unavailable (value of 0). tWaitTaskhas higher priority and runs
first. The task makes a request to acquire the semaphore but is blocked because the semaphore is unavailable.
This step gives the lower priority t SignalTaska chance to run; at some point, t SignalTaskreleases the binary
semaphore and unblocks t WaitTask.

tWaitTask's priority is higher than t SignalTask's priority, as soon as the semaphore is released, t
WaitTaskpreempts t SignalTaskand starts to execute.
5.Multiple-Task Wait-and-Signal Synchronization
When coordinating the synchronization of more than two tasks, use the flush operation on the task-waiting list of
a binary semaphore, as shown in Figure below.

Figure 3.13 Wait-and-signal synchronization between multiple tasks.

As in the previous case, the binary semaphore is initially unavailable (value of 0). The higher priority t
WaitTasks 1, 2, and 3 all do some processing; when they are done, they try to acquire the unavailable semaphore
and, as a result, block. This action gives t Signal Taska chance to complete its processing and execute a flush
command on the semaphore, effectively unblocking the three t Wait Tasks, as shown in Listing 2. Note that
similar code is used for t Wait Task 1, 2, and 3.

Page 22
6. Credit-Tracking Synchronization
Sometimes the rate at which the signaling task executes is higher than that of the signaled task. In this case, a
mechanism is needed to count each signaling occurrence. The counting semaphore provides just this facility.
With a counting semaphore, the signaling task can continue to execute and increment a count at its own pace,
while the wait task, when unblocked, executes at its own pace, as shown in Figure below.

Figure 3.14 Credit-tracking synchronization between two tasks.

Again, the counting semaphore's count is initially 0, making it unavailable. The lower priority t Wait Task tries
to acquire this semaphore but blocks until t Signal Task makes the semaphore available by performing a release
on it. Even then, t Wait Task will waits in the ready state until the higher priority t Signal Task eventually
relinquishes the CPU by making a blocking call or delaying itself, as shown in Listing 3.
Note that this credit-tracking mechanism is useful if t Signal Task releases semaphores in bursts, giving t Wait
Task the chance to catch up every once in a while.
Using this mechanism with an ISR that acts in a similar way to the signaling task can be quite useful. Interrupts
have higher priorities than tasks. Hence, an interrupt's associated higher priority ISR executes when the hardware
interrupt is triggered and typically offloads some work to a lower priority task waiting on a semaphore.
3.6 Single Shared-Resource-Access Synchronization
One of the more common uses of semaphores is to provide for mutually exclusive access to a shared resource. A
shared resource might be a memory location, a data structure, or an I/O device-essentially anything that might
have to be shared between two or more concurrent threads of execution. A semaphore can be used to serialize
access to a shared resource, as shown in Figure below.

Figure 3.15 Single shared-resource-access synchronization.

In this scenario, a binary semaphore is initially created in the available state (value = 1) and is used to protect the
shared resource. To access the shared resource, task 1 or 2 needs to first successfully acquire the binary
semaphore before reading from or writing to the shared resource.

Page 23
3.6.1 Recursive Shared-Resource-Access Synchronization
Sometimes a developer might want a task to access a shared resource recursively. This situation might exist if
Access Task calls Routine A that calls Routine B, and all three need access to the same shared resource, as
shown in Figure below.

Figure 3.16 Recursive shared- resource-access synchronization.

If a semaphore were used in this scenario, the task would end up blocking, causing a deadlock. When a routine is
called from a task, the routine effectively becomes a part of the task. When Routine A runs, therefore, it is
running as a part of Access Task. Routine A trying to acquire the semaphore is effectively the same as Access
Task trying to acquire the same semaphore. In this case, Access Task would end up blocking.

3.6.2 Multiple Shared-Resource-Access Synchronization

For cases in which multiple equivalent shared resources are used, a counting semaphore comes in handy, as
shown in Figure below.

Figure 3.17 Single shared-resource-access synchronization.

Note that this scenario does not work if the shared resources are not equivalent. The counting semaphore's count
is initially set to the number of equivalent shared resources: in this example, 2. As a result, the first two tasks
requesting a semaphore token are successful. However, the third task ends up blocking until one of the previous
two tasks releases a semaphore token, as shown in Listing 6. Note that similar code is used for t AccessTask 1, 2,
and 3.
Use of semaphore

Page 24
 Figure 3.18 Use of semaphore
 The Task A Requesting for taking semaphore with the Kernel or Operating System
 The kernel acknowledge and ask task A to take the semaphore
 During that time Task B is Blocked (which also uses the same semaphore)
 Task A Releases the semaphore, Event to the OS
 Task B starts running by taking the semaphor
Use of Multiple Semaphores

Figure 3.19 Use of Multiple Semaphores

 Two semaphores X and Y are used

 Task I, J and M share the semaphore X
 Task K and L Share the semaphore Y
 In the above diagram, the tasks J and M are waiting for taking the semaphore X as the
semaphore is locked by the Task J
 similarly, the other semaphore Y is been locked by Task L and hence Task K is waiting

3.7 Priority Inversion Problem:

Page 25
 Priority implies a more stringent deadline. In a priority-based, preemptive scheduling system, the kernel
schedules higher priority exists among tasks with different priorities.
 Consider the situation shown in Figure above, in which a higher priority task shares a resource with a lower
priority task. The higher priority task must wait when the lower priority task has locked the resource, even
though the higher priority task is eligible to run.
 tasks first and postpones lower priority tasks until either all of the higher priority tasks are completed or the
higher priority tasks voluntarily relinquish the CPU.
 Priority inversion occurs when task interdependency

Figure 3.20 Priority inversion example.

 As shown in Figure above, at time t1 the low-priority task (LP-task) locks the shared resource. The LP-task
continues until time t2 when the high-priority task (HP-task) becomes eligible to run. The scheduler
immediately preempts the LP-task and context-switches to the HP-task. The HP-task runs until time t3 when
it requires the shared resource. Because the resource is in the locked state, the HP-task must block and wait
for its release. At this point, the scheduler context-switches back to the LP-task. Priority inversion begins at
time t3. At time t4, the LP-task releases the shared resource, which triggers preemption and allows the HP-
task to resume execution. Priority inversion ends at time t4. The HP-task completes at time t5, which allows
the LP-task to resume execution and finally complete at time t6. The priority inversion shown in Figure above
is a bounded priority inversion.
 The duration of the low-priority task's holding time on the shared resource is known. It is possible for a
medium-priority task to preempt the low-priority task for an undetermined amount of time, which would
cause the high-priority task to wait indefinitely. This priority inversion scenario is called unbounded priority
inversion and is shown in Figure below.

Page 26
 Figure3.21 Unbounded priority inversion example
 As in the previous example, priority inversion takes place at time t3. The low-priority task (LP-task) executes
until time t4 when an unrelated medium-priority task (MP-task) preempts it. Because the MP-task does not
share resources with either the HP-task or the LP-task, the MP-task continues execution until it completes at
time t5. The duration between t4 and t5 is unknown because the duration depends on the nature of the MP-
task. In addition, any number of unrelated medium-priority tasks can execute during this period. These
unknown factors affect the interval and translate into unbounded priority inversion.
 Priority inversion results from resource synchronization among tasks of differing priorities. Priority inversion
cannot be avoided, but it can be minimized using resource access control protocols.
 A resource access control protocol is a set of rules that defines the conditions under which a resource can be
granted to a requesting task and governs the execution scheduling property of the task holding the resource.
 Access control protocols are discussed in the following sections. These access control protocols eliminate the
unbound priority inversion, and two of these protocols reduce the inversion time.
3.7.1 Priority Inheritance Protocol
 The Priority Inheritance Protocol is a resource access control protocol that raises the priority of a task, if that
task holds a resource being requested by a higher priority task, to the same priority level as the higher priority
task. This access control protocol follows the rules in Table shown below when a task T requests a resource
R.
Table 3.1 Priority Inheritance Protocol rules.

Rule # Description

1 If R is in use, T is blocked.

2 If R is free, R is allocated to T.

3 When a task of a higher priority requests the same resource, T's execution priority is raised to the
requesting task's priority level.

4 The task returns to its previous priority when it releases R.

3.7.2 Ceiling Priority Protocol

 In the ceiling priority protocol, the priority of every task is known, as are the resources required by every task.
For a given resource, the priority ceiling is the highest priority of all possible tasks that might require the
resource.
 For example, if a resource R is required by four tasks (T1 of priority 4, T2 of priority 9, T3 of priority 10, and
T4 of priority 8), the priority ceiling of R is 10, which is the highest priority of the four tasks.
Page 27
 This access control protocol follows the rules in Table shown belowwhen a task T requests a resource R.

Table 3.2 Ceiling priority protocol rules.

Rule # Description

1 If R is in use, T is blocked.

2 If R is free, R is allocated to T. T's execution priority is raised to the priority ceiling of R if that is
higher. At any given time, T's execution priority equals the highest priority ceiling of all its held
resources.

3 T's priority is assigned the next-highest priority ceiling of another resource when the resource with the
highest priority ceiling is released.

4 The task returns to its assigned priority after it has released all resources.

3.7.2 Deadlocks
 Deadlock is the situation in which multiple concurrent threads of execution in a system are blocked
permanently because of resource requirements that can never be satisfied.
 Given that each resource is non pre-emptible and supports only exclusive access mode, Figure below depicts
a deadlock situation between two tasks.

Figure 3.22.Deadlock situation between two tasks.

 Figure above is a resource graph. An arrow labeled holds going from a resource to a task indicates that the
task currently holds (or owns) the resource. An arrow labeled wants going from a task to a resource indicates
that the task currently needs this resource to resume execution.
 In this example, task #1 wants the scanner while holding the printer. Task #1 cannot proceed until both the
printer and the scanner are in its possession. Task #2 wants the printer while holding the scanner. Task #2
cannot continue until it has the printer and the scanner. Because neither task #1 nor task #2 is willing to give
up what it already has, the two tasks are now deadlocked because neither can continue execution.
 As shown in Figure below, task T1 currently holds resource R1 (a printer), and T1 wants resource R2 (a
scanner). Task T2 holds resource R2 and wants resource R3 (a memory buffer). Similarly, task T3 holds

Page 28
 resource R3 and wants resource R1. It is easy to see the cycle, i.e., the circular-wait condition in this system.
The Tasks T1, T2, and T3, and resources R1, R2, and R3 comprise the deadlocked set. Note that in the system
in Figure below, one instance per resource type exists, i.e., there is one instance of R1, one instance of R2,
and one instance of R3.

Figure 3.23 Deadlock situations among three tasks.

 In this example, each task requires a single instance of a single resource type at any given time. Many
situations exist in which a task might require multiple instances of multiple types of resources. The formation
of deadlocks depends on how a task requests resources (formally known as a resource request model). The
deadlock detection algorithms are constructed according to the resource request models.
In general, there are four strategies of dealing with deadlock problem:
1. The Ostrich Approach - Just ignore the deadlock problem altogether.
2. Deadlock Detection and Recovery - Detect deadlock and, when it occurs, take steps to recover.
3. Deadlock Avoidance - Avoid deadlock by careful resource scheduling.
4. Deadlock Prevention - Prevent deadlock by resource scheduling so as to negate at least one of the
four conditions.
Shared data problem:
If there is a variable currently running under a task and there is an interrupt and some other task will be
taking the control of that variable. Since the variable is already used by other task, so there comes a shared
data problem.
The bugs encountered in the above process can be eliminated by means of following techniques
 use of volatile modifier – this declaration warns the compiler that certain variables can modify because
the ISR does not consider the fact that the variable is also shared with a calling function
 Reentrant function – part of a function that needs its complete execution before it can be interrupted.
This part is called the critical section.
 Put a shared variable in a circular queue – a function that requires the value of this variable always delete
it from the queue front and another function which inserts the value of this variable, always does so at
the queue back.

Page 29
  Disabling the interrupts before a critical section starts executing and enable the interrupts on its
completion. In this method, the high priority task or ISRs will be waiting because of the disabling of the
interrupts
 Semaphores- which is a nice option for shared data problems and it is efficient also.
Semaphore is a variable or abstract data type that is used for controlling access, by multiple processes, to a
common resource in a concurrent system such as a multiprogramming operating system.
Resource semaphores are used to regulate access to resources such as printers, critical code sections, and blocks
of memory. There are two types of resource semaphores:
1. Binary resource semaphore
2. Multiple resource semaphore
3.8 Binary resource semaphore
 A binary resource semaphore is used to control sharing a single resource between tasks. Its internal counter
can have only the values of 1 (available) and 0 (unavailable). A semaphore test passes if the count is 1, in
which case, the current task is allowed to proceed.
 If the count is 0, the semaphore test fails and the current task is en-queued in the semaphore‘s task wait list,
in priority order.
 When the semaphore is signaled, the first task (i.e. the longest-waiting, highest-priority task) is resumed, and
the internal semaphore count remains 0. If no task is waiting, the count is increased to 1. The following is an
example of using a binary resource semaphore:
TCB_PTR t2a, t3a; // tasks
SCB_PTR sbr; // binary resource semaphore
void Init(void) {
sbr = smx_SemCreate(RSRC, 1, "sbr");
t2a = smx_TaskCreate(t2a_main, Pri2, 500, NO_FLAGS, "t2a"); // 500 byte stack
t3a = smx_TaskCreate(t3a_main, Pri3, 500, NO_FLAGS, "t3a");
smx_TaskStart(t2a);
}
void t2a_main(void) {
if (smx_SemTest(sbr, TMO)) { // TMO = timeout in ticks
smx_TaskStart(t3a); // use resource here
smx_SemSignal(sbr);
}
else // deal with timeout or error
}
void t3a_main(void) {

Page 30
 if (smx_SemTest(sbr, TMO)) { // use resource here
smx_SemSignal(sbr);
}
else // deal with timeout or error
}
A binary resource semaphore does the same thing as a mutex, but it has the following shortcomings:
It cannot do priority inheritance to prevent unbounded priority inversions among tasks.
 If a task tests a semaphore that it already owns, it will be permanently blocked, as will all other tasks
waiting on the same semaphore or testing it later.
 The first defect may not be important in simple systems or if low-priority tasks do not share resources
with high-priority tasks. The second defect is obviously very serious.
 The fact that it is a software bug is not of much consolation it could occur in a rare, untested path, or be
introduced in a software update.
 To counter it, always specify timeouts on semaphore tests (e.g., TMO above) and test the return value,
as shown in the first example. In the case of a timeout or other error, SemTest() returns FALSE,
meaning that the test did not pass and the resource is not free.
3.8.1 Multiple resource semaphore
The multiple resource semaphore is a generalization of the binary resource semaphore, intended to regulate access
to multiple identical resources. It is commonly called a counting semaphore. This semaphore cannot be replaced
by a mutex because the latter can only control access to one resource. The following is an example of using a
multiple resource semaphore to control access to a block pool containing NUM blocks (for simplicity, timeouts
and return value testing have been omitted -- this is NOT recommended in real code):
TCB_PTR t2a, t3a; // tasks
PCB_PTR blk_pool; // block pool
SCB_PTR sr; // resource semaphore
#define NUM 10
#define SIZE 100
void Init(void) {
u8* p = (u8*)smx_HeapMalloc(NUM*SIZE);
sb_BlockPoolCreate(p, blk_pool, NUM, SIZE, "blk pool");
sr = smx_SemCreate(RSRC, NUM, "sr");
t2a = smx_TaskCreate(t2a_main, Pri2, 500, NO_FLAGS, "t2a");
t3a = smx_TaskCreate(t3a_main, Pri3, 500, NO_FLAGS, "t3a");
smx_TaskStart(t2a);
}

Page 31
 void t2a_main(void) {
u8* bp;
smx_SemTest(sr, INF);
bp = sb_BlockGet(blk_pool, 0));
smx_TaskStart(t3a); // use bp to access block
sb_BlockRel(blk_pool, bp, 0);
smx_SemSignal(sr);
}

void t3a_main(void) {
u8* bp;
smx_SemTest(sr, INF);
bp = sb_BlockGet(blk_pool, 0)); // use bp to access block
sb_BlockRel(blk_pool, bp, 0);
smx_SemSignal(sr);
}
This example is similar to the previous example, with small differences. The Init() function first creates a block
pool of NUM blocks. It then creates sr, but because NUM is used instead of 1, a multiple resource semaphore is
created, with a starting count of NUM.
 t2a tests sr and sr's counter is decremented to 9, which is greater than 0, so t2a is allowed to get a block. As
before, t2a starts t3a, which immediately preempts. t3a tests sr and sr's counter is decremented to 8, so t3a is
also allowed to get a block and use it.
3.8. 2 Priority Inversion Problem and Deadlock Situations
When tasks share resources, as they often do, strange things can and will happen.
 Priority inversions can be particularly difficult to anticipate. Here's an introduction to priority
inversions and a pair of techniques you can use to avoid them.
 Most commercial real-time operating systems (RTOSes) employ a priority-based preemptive
scheduler. These systems assign each task a unique priority level. The scheduler ensures that of those
tasks that are ready to run, the one with the highest priority is always the task that is actually
running. To meet this goal, the scheduler may preempt a lower-priority task in mid-execution.
Because tasks share resources, events outside the scheduler's control can prevent the highest priority
ready task from running when it should.
 If this happens, a critical deadline could be missed, causing the system to fail. Priority inversion is
the term for a scenario in which the highest-priority ready task fails to run when it should.

Page 32
1.Resource sharing
 Tasks need to share resources to communicate and process data. This aspect of multi-threaded
programming is not specific to real-time or embedded systems.
 Any time two tasks share a resource, such as a memory buffer, in a system that employs a priority-based
scheduler, one of them will usually have a higher priority. The higher-priority task expects to be run as
soon as it is ready. However, if the lower-priority task is using their shared resource when the higher-
priority task becomes ready to run, the higher-priority task must wait for the lower-priority task to finish
with it.
 If the cumulative lockout times are too long, the resource-sharing scheme must be redesigned.
 Since worst-case delays resulting from the sharing of resources can be calculated at design time, the only
way they can affect the performance of the system is if no one properly accounts for them.
2. Priority inversions

Figure 3.24 Priority inversions

 The real trouble arises at run-time, when a medium-priority task preempts a lower-priority task using a
shared resource on which the higher-priority task is pending. If the higher-priority task is otherwise
ready to run, but a medium-priority task is currently running instead, a priority inversion is said to occur.
 The sequence of events leading to each reset began when the low-priority science task was preempted
by a couple of medium-priority tasks while it held a mutex related to the pipe.
 While the low-priority task was preempted, the high-priority bus distribution manager tried to send
more data to it over the same pipe. Because the mutex was still held by the science task, the bus
distribution manager was made to wait.
3.9 EVALUATING OPERATING SYSTEM PERFORMANCE:

The scheduling policy does not tell us all that we would like to know about the performance of a real system
running processes. Our analysis of scheduling policies makes some simplifying assumptions:

Page 33
  We have assumed that context switches require zero time. Although it is often reasonable to
neglect context switch time when it is much smaller than the process execution time, context
switching can add significant delay in some cases.
 We have assumed that we know the execution time of the processes. In fact, we learned in
Section 5.6 that program time is not a single number, but can be bounded by worst-case and
best-case execution times.
 We probably determined worst-case or best-case times for the processes in isolation. But, in fact,
they interact with each other in the cache. Cache conflicts among processes can drastically
degrade process execution time.
 The zero-time context switch assumption used in the analysis of RMS is not correct—we must execute
instructions to save and restore context, and we must execute additional instructions to implement the
scheduling policy. On the other hand, context switching can be implemented efficiently—context
switching need not kill performance.
 The effects of nonzero context switching time must be carefully analyzed in the context of a particular
implementation to be sure that the predictions of an ideal scheduling policy are sufficiently accurate.
 In most real-time operating systems, a context switch requires only a few hundred instructions, with only
slightly more overhead for a simple real-time scheduler like RMS. When the overhead time is very
small relative to the task periods, then the zero-time context switch assumption is often a reasonable
approximation. Problems are most likely to manifest themselves in the highest-rate processes, which
are often the most critical in any case.
Completely checking that all deadlines will be met with nonzero context switching time requires checking all
possible schedules for processes and including the context switch time at each preemption or process initiation.
However, assuming an average number of context switches per process and computing CPU utilization can
provide at least an estimate of how close the system is to CPU capacity.
3.10 OPTIMIZATION STRATEGIES FOR PROCESSES:

The RTOS and system architecture can use static and dynamic power management mechanisms to help
manage the system‘s power consumption. A power management policy [Ben00] is a strategy for determining
when to perform certain power management operations. A power management policy in general examines the
state of the system to determine when to take actions. However, the overall strategy embodied in the policy
should be designed based on the characteristics of the static and dynamic power management mechanisms.Going
into a low-power mode takes time; generally, the more that is shut off, the longer the delay incurred during
restart. Because power-down and power-up are not free, modes should be changed carefully. Determining when
to switch into and out of a power-up mode requires an analysis of the overall system activity.
 Avoiding a power-down mode can cost unnecessary power.
 Powering down too soon can cause severe performance penalties.
Page 34
Re-entering run mode typically costs a considerable amount of time. A straightforward method is to power up
the system when a request is received. This works as long as the delay in handling the request is acceptable. A
more sophisticated technique is predictive shutdown.
The goal is to predict when the next request will be made and to start the system just before that time, saving the
requestor the start-up time. In general, predictive shutdown techniques are probabilistic they make guesses about
activity patterns based on a probabilistic model of expected behavior. Because they rely on statistics, they may
not always correctly guess the time of the next activity.
This can cause two types of problems:
 The requestor may have to wait for an activity period. In the worst case, the requestor may not
make a deadline due to the delay incurred by system start-up.
 The system may restart itself when no activity is imminent. As a result, the system will waste
power.
Clearly, the choice of a good probabilistic model of service requests is important. The policy mechanism should
also not be too complex, since the power it consumes to make decisions is part of the total system power budget.
Several predictive techniques are possible. A very simple technique is to use fixed times. For instance, if the
system does not receive inputs during an interval of length Ton, it shuts down; a powered-down system waits for
a period Toff before returning to the power-on mode.
The choice of Toff and Ton must be determined by experimentation. Srivastava and Eustace [Sri94] found one
useful rule for graphics terminals. They plotted the observed idle time (Toff) of a graphics terminal versus the
immediately preceding active time (Ton).The result was an L-shaped distribution as illustrated in Figure 3.12. In
this distribution, the idle period after a long active period is usually very short, and the length of the idle period
after a short active period is uniformly distributed.

Based on this distribution, they proposed a shut down threshold that depended on the length of the last active
period—they shut down when the active period length was below a threshold, putting the system in the vertical
portion of the L distribution.
The Advanced Configuration and Power Interface (ACPI) is an open industry standard for power management
services. It is designed to be compatible with a wide variety of OSs. It was targeted initially to PCs. The role of
ACPI in the system is illustrated in Figure 3.13.

Page 35
 Figure 3.24 Advanced Configuration and Power Interface (ACPI)
ACPI provides some basic power management facilities and abstracts the hardware layer, the OS has its own
power management module that determines the policy, and the OS then uses ACPI to send the required controls
to the hardware and to observe the hardware‘s state as input to the power manager.
ACPI supports the following five basic global power states:
 G3, the mechanical off state, in which the system consumes no power.
 G2, the soft off state, which requires a full OS reboot to restore the machine to working condition. This
state has four substates:
 S1, a low wake-up latency state with no loss of system context;
 S2, a low wake-up latency state with a loss of CPU and system cache state;
 S3, a low wake-up latency state in which all system state except for main memory is lost; and
 S4, the lowest-power sleeping state, in which all devices are turned off.
 G1, the sleeping state, in which the system appears to be off and the time required to return to working
condition is inversely proportional to power consumption.
 G0, the working state, in which the system is fully usable.
 The legacy state, in which the system does not comply with ACPI.

Page 36