Real-Time Opera ng System (RTOS) based Embedded System Design 387

Real-Time Operating
System (RTOS) based
10 Embedded System
Design

LEARNING OBJECTIVES
LO 1 Understand the basics of an opera ng system and the need for an opera ng system
Learn the basic kernel services of an opera ng system
LO 2 Classify the types of opera ng systems
Learn the internals of Real-Time Opera ng System and the fundamentals of RTOS
based embedded firmware design
Learn about the different real- me kernels and the features that make a kernel
Real-Time
LO 3 Discuss tasks, processes and threads in the opera ng system context
Learn about the structure of a process, the different states of a process, process
life cycle and process management
Learn the concept of mul threading, thread standards and thread scheduling
LO 4 Understand the difference between mul processing and mul tasking
Learn about the different types of mul tasking (Co-opera ve, Preemp ve and
Non-preemp ve
LO 5 Describe the FCFS/FIFO, LCFS/LIFO, SJF and priority based task/process scheduling
Learn about the Shortest Remaining Time (SRT), Round Robin and priority based
preemp ve task/process scheduling
LO 6 Explain the different Inter Process Communica on (IPC) mechanisms used by tasks/
process to communicate and co-operate each other in a mul tasking environment
LO 7 Iden fy the RPC based Inter Process Communica on
Learn the different types of shared memory techniques (Pipes, memory mapped
object, etc.) for IPC
Learn the different types of message passing techniques (Message queue, mailbox,
signals, etc.) for IPC
LO 8 State the need for task synchronisa on in a mul tasking environment
Learn the different issues related to the accessing of a shared resource by mul ple
processes concurrently
388 Introduc on to Embedded Systems

Learn about ‘Racing’, ‘Starva on’, ‘Livelock’, ‘Deadlock’, ‘Dining Philosopher’s

Problem’, ‘Producer-Consumer/Bounded Buffer Problem’, ‘Readers-Writers
Problem’ and ‘Priority Inversion’
Learn about the ‘Priority Inheritance’ and ‘Priority Ceiling’ based Priority avoidance
mechanisms
Learn the need for task synchronisa on and the different mechanisms for task
synchronisa on in a mul tasking environment
Learn about mutual exclusion and the different policies for mutual exclusion
implementa on
Learn about semaphores, different types of semaphores, mutex, cri cal sec on
objects and events for task synchronisa on
LO 9 Analyse device drivers, their role in an opera ng system based embedded system
design, the structure of a device driver, and interrupt handling inside device drivers
LO 10 Discuss the different func onal and non-func onal requirements that need to be
addressed in the selec on of a Real-Time Opera ng System

In the previous chapter, we discussed about the Super loop based task execution model for firmware
execution. The super loop executes the tasks sequentially in the order in which the tasks are listed within the
loop. Here every task is repeated at regular intervals and the task execution is non-real time. As the number
of task increases, the time intervals at which a task gets serviced also increases. If some of the tasks involve
waiting for external events or I/O device usage, the task execution time also gets pushed off in accordance
with the ‘wait’ time consumed by the task. The priority in which a task is to be executed is fixed and is
determined by the task placement within the loop, in a super loop based execution. This type of firmware
execution is suited for embedded devices where response time for a task is not time critical. Typical examples
are electronic toys and video gaming devices. Here any response delay is acceptable and it will not create any
operational issues or potential hazards. Whereas certain applications demand time critical response to tasks/
events and any delay in the response may become catastrophic. Flight Control systems, Air bag control and
Anti-lock Brake System (ABS) systems for vehicles, Nuclear monitoring devices, etc. are typical examples
of applications/devices demanding time critical task response.
How the increasing need for time critical response for tasks/events is addressed in embedded applications?
Well the answer is
1. Assign priority to tasks and execute the high priority task when the task is ready to execute.
2. Dynamically change the priorities of tasks if required on a need basis.
3. Schedule the execution of tasks based on the priorities.
4. Switch the execution of task when a task is waiting for an external event or a system resource including
I/O device operation.
The introduction of operating system based firmware execution in embedded devices can address these
needs to a greater extent.
 Real-Time Opera ng System (RTOS) based Embedded System Design 389

10.1 OPERATING SYSTEM BASICS

The operating system acts as a bridge between the user applications/tasks and the
LO 1 Understand
underlying system resources through a set of system functionalities and services.
the basics of an
The OS manages the system resources and makes them available to the user
operating system
applications/tasks on a need basis. A normal computing system is a collection of
and the need for an
different I/O subsystems, working, and storage memory. The primary functions
operating system
of an operating system is
∑ Make the system convenient to use
∑ Organise and manage the system resources efficiently and correctly
Figure 10.1 gives an insight into the basic components of an operating system and their interfaces with
rest of the world.

User Applications
Application
programming
Memory management interface (API)
Kernel Services

Process management
Time management
File system management
I/O system management
Device driver
interface
Underlying hardware
Fig. 10.1 The Operating System Architecture

10.1.1 The Kernel

The kernel is the core of the operating system and is responsible for managing the system resources and the
communication among the hardware and other system services. Kernel acts as the abstraction layer between
system resources and user applications. Kernel contains a set of system libraries and services. For a general
purpose OS, the kernel contains different services for handling the following.
Process Management Process management deals with managing the processes/tasks. Process management
includes setting up the memory space for the process, loading the process’s code into the memory space,
allocating system resources, scheduling and managing the execution of the process, setting up and managing
the Process Control Block (PCB), Inter Process Communication and synchronisation, process termination/
deletion, etc. We will look into the description of process and process management in a later section of this
chapter.
Primary Memory Management The term primary memory refers to the volatile memory (RAM) where
processes are loaded and variables and shared data associated with each process are stored. The Memory
Management Unit (MMU) of the kernel is responsible for
∑ Keeping track of which part of the memory area is currently used by which process
∑ Allocating and De-allocating memory space on a need basis (Dynamic memory allocation).
390 Introduc on to Embedded Systems

File System Management File is a collection of related information. A file could be a program (source code
or executable), text files, image files, word documents, audio/video files, etc. Each of these files differ in the
kind of information they hold and the way in which the information is stored. The file operation is a useful
service provided by the OS. The file system management service of Kernel is responsible for
∑ The creation, deletion and alteration of files
∑ Creation, deletion and alteration of directories
∑ Saving of files in the secondary storage memory (e.g. Hard disk storage)
∑ Providing automatic allocation of file space based on the amount of free space available
∑ Providing a flexible naming convention for the files
The various file system management operations are OS dependent. For example, the kernel of Microsoft®
DOS OS supports a specific set of file system management operations and they are not the same as the file
system operations supported by UNIX Kernel.
I/O System (Device) Management Kernel is responsible for routing the I/O requests coming from different
user applications to the appropriate I/O devices of the system. In a well-structured OS, the direct accessing
of I/O devices are not allowed and the access to them are provided through a set of Application Programming
Interfaces (APIs) exposed by the kernel. The kernel maintains a list of all the I/O devices of the system. This
list may be available in advance, at the time of building the kernel. Some kernels, dynamically updates the
list of available devices as and when a new device is installed (e.g. Windows NT kernel keeps the list updated
when a new plug ‘n’ play USB device is attached to the system). The service ‘Device Manager’ (Name may
vary across different OS kernels) of the kernel is responsible for handling all I/O device related operations.
The kernel talks to the I/O device through a set of low-level systems calls, which are implemented in a
service, called device drivers. The device drivers are specific to a device or a class of devices. The Device
Manager is responsible for
∑ Loading and unloading of device drivers
∑ Exchanging information and the system specific control signals to and from the device
Secondary Storage Management The secondary storage management deals with managing the secondary
storage memory devices, if any, connected to the system. Secondary memory is used as backup medium for
programs and data since the main memory is volatile. In most of the systems, the secondary storage is kept in
disks (Hard Disk). The secondary storage management service of kernel deals with
∑ Disk storage allocation
∑ Disk scheduling (Time interval at which the disk is activated to backup data)
∑ Free Disk space management
Protec on Systems Most of the modern operating systems are designed in such a way to support multiple
users with different levels of access permissions (e.g. Windows 10 with user permissions like ‘Administrator’,
‘Standard’, ‘Restricted’, etc.). Protection deals with implementing the security policies to restrict the access
to both user and system resources by different applications or processes or users. In multiuser supported
operating systems, one user may not be allowed to view or modify the whole/portions of another user’s data
or profile details. In addition, some application may not be granted with permission to make use of some of
the system resources. This kind of protection is provided by the protection services running within the kernel.
Interrupt Handler Kernel provides handler mechanism for all external/internal interrupts generated by the
system.
These are some of the important services offered by the kernel of an operating system. It does not mean
that a kernel contains no more than components/services explained above. Depending on the type of the
 Real-Time Opera ng System (RTOS) based Embedded System Design 391

operating system, a kernel may contain lesser number of components/services or more number of components/
services. In addition to the components/services listed above, many operating systems offer a number of add-
on system components/services to the kernel. Network communication, network management, user-interface
graphics, timer services (delays, timeouts, etc.), error handler, database management, etc. are examples for
such components/services. Kernel exposes the interface to the various kernel applications/services, hosted by
kernel, to the user applications through a set of standard Application Programming Interfaces (APIs). User
applications can avail these API calls to access the various kernel application/services.
[Link] Kernel Space and User Space
As we discussed in the earlier section, the applications/services are classified into two categories, namely:
user applications and kernel applications. The program code corresponding to the kernel applications/services
are kept in a contiguous area (OS dependent) of primary (working) memory and is protected from the un-
authorised access by user programs/applications. The memory space at which the kernel code is located is
known as ‘Kernel Space’. Similarly, all user applications are loaded to a specific area of primary memory
and this memory area is referred as ‘User Space’. User space is the memory area where user applications
are loaded and executed. The partitioning of memory into kernel and user space is purely Operating System
dependent. Some OS implements this kind of partitioning and protection whereas some OS do not segregate
the kernel and user application code storage into two separate areas. In an operating system with virtual
memory support, the user applications are loaded into its corresponding virtual memory space with demand
paging technique; Meaning, the entire code for the user application need not be loaded to the main (primary)
memory at once; instead the user application code is split into different pages and these pages are loaded into
and out of the main memory area on a need basis. The act of loading the code into and out of the main memory
is termed as ‘Swapping’. Swapping happens between the main (primary) memory and secondary storage
memory. Each process run in its own virtual memory space and are not allowed accessing the memory space
corresponding to another processes, unless explicitly requested by the process. Each process will have certain
privilege levels on accessing the memory of other processes and based on the privilege settings, processes can
request kernel to map another process’s memory to its own or share through some other mechanism. Most
of the operating systems keep the kernel application code in main memory and it is not swapped out into the
secondary memory.
[Link] Monolithic Kernel and Microkernel
As we know, the kernel forms the heart of an operating system. Different approaches are adopted for building
an Operating System kernel. Based on the kernel design, kernels can be classified into ‘Monolithic’ and
‘Micro’.
Monolithic Kernel In monolithic kernel architecture, all
kernel services run in the kernel space. Here all kernel Applications
modules run within the same memory space under a
single kernel thread. The tight internal integration of
kernel modules in monolithic kernel architecture allows
the effective utilisation of the low-level features of the
underlying system. The major drawback of monolithic
kernel is that any error or failure in any one of the Monolithic kernel with all
kernel modules leads to the crashing of the entire kernel operating system services
application. LINUX, SOLARIS, MS-DOS kernels running in kernel space
are examples of monolithic kernel. The architecture
representation of a monolithic kernel is given in Fig. 10.2. Fig. 10.2 The Monolithic Kernel Model
392 Introduc on to Embedded Systems

Microkernel The microkernel design incorporates

only the essential set of Operating System services Servers (kernel
into the kernel. The rest of the Operating System services running Applications
services are implemented in programs known as in user space)
‘Servers’ which runs in user space. This provides a
highly modular design and OS-neutral abstraction to
the kernel. Memory management, process
management, timer systems and interrupt handlers
are the essential services, which forms the part of
Microkernel with essential
the microkernel. Mach, QNX, Minix 3 kernels are
services like memory
examples for microkernel. The architecture
management, process
representation of a microkernel is shown in management, timer system, etc...
Fig. 10.3.
Microkernel based design approach offers the
following benefits Fig. 10.3 The Microkernel model
∑ Robustness: If a problem is encountered in any
of the services, which runs as ‘Server’ application, the same can be reconfigured and re-started without
the need for re-starting the entire OS. Thus, this approach is highly useful for systems, which demands
high ‘availability’. Refer Chapter 3 to get an understanding of ‘availability’. Since the services which
run as ‘Servers’ are running on a different memory space, the chances of corruption of kernel services
are ideally zero.
∑ Configurability: Any services, which run as ‘Server’ application can be changed without the need to
restart the whole system. This makes the system dynamically configurable.

10.2 TYPES OF OPERATING SYSTEMS

LO 2 Classify the Depending on the type of kernel and kernel services, purpose and type of
types of operating computing systems where the OS is deployed and the responsiveness to
systems applications, Operating Systems are classified into different types.

10.2.1 General Purpose Operating System (GPOS)

The operating systems, which are deployed in general computing systems, are referred as General Purpose
Operating Systems (GPOS). The kernel of such an OS is more generalised and it contains all kinds of
services required for executing generic applications. General-purpose operating systems are often quite
non-deterministic in behaviour. Their services can inject random delays into application software and may
cause slow responsiveness of an application at unexpected times. GPOS are usually deployed in computing
systems where deterministic behaviour is not an important criterion. Personal Computer/Desktop system is
a typical example for a system where GPOSs are deployed. Windows 10/8.x/XP/MS-DOS etc are examples
for General Purpose Operating Systems.

10.2.2 Real-Time Operating System (RTOS)

There is no universal definition available for the term ‘Real-Time’ when it is used in conjunction with operating
systems. What ‘Real-Time’ means in Operating System context is still a debatable topic and there are many
definitions available. In a broad sense, ‘Real-Time’ implies deterministic timing behaviour. Deterministic
timing behaviour in RTOS context means the OS services consumes only known and expected amounts of
time regardless the number of services. A Real-Time Operating System or RTOS implements policies and
 Real-Time Opera ng System (RTOS) based Embedded System Design 393

rules concerning time-critical allocation of a system’s resources. The RTOS decides which applications should
run in which order and how much time needs to be allocated for each application. Predictable performance
is the hallmark of a well-designed RTOS. This is best achieved by the consistent application of policies and
rules. Policies guide the design of an RTOS. Rules implement those policies and resolve policy conflicts.
Windows Embedded Compact, QNX, VxWorks MicroC/OS-II etc are examples of Real Time Operating
Systems (RTOS).
[Link] The Real-Time Kernel
The kernel of a Real-Time Operating System is referred as Real. Time kernel. In complement to the
conventional OS kernel, the Real-Time kernel is highly specialised and it contains only the minimal set of
services required for running the user applications/tasks. The basic functions of a Real-Time kernel are listed
below:
∑ Task/Process management
∑ Task/Process scheduling
∑ Task/Process synchronisation
∑ Error/Exception handling
∑ Memory management
∑ Interrupt handling
∑ Time management
Task/Process management Deals with setting up the memory space for the tasks, loading the task’s
code into the memory space, allocating system resources, setting up a Task Control Block (TCB) for the
task and task/process termination/deletion. A Task Control Block (TCB) is used for holding the information
corresponding to a task. TCB usually contains the following set of information.
Task ID: Task Identification Number
Task State: The current state of the task (e.g. State = ‘Ready’ for a task which is ready to execute)
Task Type: Task type. Indicates what is the type for this task. The task can be a hard real time or soft real
time or background task.
Task Priority: Task priority (e.g. Task priority = 1 for task with priority = 1)
Task Context Pointer: Context pointer. Pointer for context saving
Task Memory Pointers: Pointers to the code memory, data memory and stack memory for the task
Task System Resource Pointers: Pointers to system resources (semaphores, mutex, etc.) used by the task
Task Pointers: Pointers to other TCBs (TCBs for preceding, next and waiting tasks)
Other Parameters: Other relevant task parameters
The parameters and implementation of the TCB is kernel dependent. The TCB parameters vary across
different kernels, based on the task management implementation. Task management service utilises the TCB
of a task in the following way
∑ Creates a TCB for a task on creating a task
∑ Delete/remove the TCB of a task when the task is terminated or deleted
∑ Reads the TCB to get the state of a task
∑ Update the TCB with updated parameters on need basis (e.g. on a context switch)
∑ Modify the TCB to change the priority of the task dynamically
Task/Process Scheduling Deals with sharing the CPU among various tasks/processes. A kernel application
called ‘Scheduler’ handles the task scheduling. Scheduler is nothing but an algorithm implementation, which
394 Introduc on to Embedded Systems

performs the efficient and optimal scheduling of tasks to provide a deterministic behaviour. We will discuss
the various types of scheduling in a later section of this chapter.
Task/Process Synchronisa on Deals with synchronising the concurrent access of a resource, which is
shared across multiple tasks and the communication between various tasks. We will discuss the various
synchronisation techniques and inter task /process communication in a later section of this chapter.
Error/Excep on Handling Deals with registering and handling the errors occurred/exceptions raised during
the execution of tasks. Insufficient memory, timeouts, deadlocks, deadline missing, bus error, divide by zero,
unknown instruction execution, etc. are examples of errors/exceptions. Errors/Exceptions can happen at the
kernel level services or at task level. Deadlock is an example for kernel level exception, whereas timeout is
an example for a task level exception. The OS kernel gives the information about the error in the form of a
system call (API). GetLastError() API provided by Windows CE/Embedded Compact RTOS is an example
for such a system call. Watchdog timer is a mechanism for handling the timeouts for tasks. Certain tasks may
involve the waiting of external events from devices. These tasks will wait infinitely when the external device
is not responding and the task will generate a hang-up behaviour. In order to avoid these types of scenarios,
a proper timeout mechanism should be implemented. A watchdog is normally used in such situations. The
watchdog will be loaded with the maximum expected wait time for the event and if the event is not triggered
within this wait time, the same is informed to the task and the task is timed out. If the event happens before
the timeout, the watchdog is resetted.
Memory Management Compared to the General Purpose Operating Systems, the memory management
function of an RTOS kernel is slightly different. In general, the memory allocation time increases
depending on the size of the block of memory needs to be allocated and the state of the allocated memory
block (initialised memory block consumes more allocation time than un-initialised memory block). Since
predictable timing and deterministic behaviour are the primary focus of an RTOS, RTOS achieves this
by compromising the effectiveness of memory allocation. RTOS makes use of ‘block’ based memory
allocation technique, instead of the usual dynamic memory allocation techniques used by the GPOS.
RTOS kernel uses blocks of fixed size of dynamic memory and the block is allocated for a task on a need
basis. The blocks are stored in a ‘Free Buffer Queue’. To achieve predictable timing and avoid the timing
overheads, most of the RTOS kernels allow tasks to access any of the memory blocks without any memory
protection. RTOS kernels assume that the whole design is proven correct and protection is unnecessary.
Some commercial RTOS kernels allow memory protection as optional and the kernel enters a fail-safe
mode when an illegal memory access occurs.
A few RTOS kernels implement Virtual Memory* concept for memory allocation if the system supports
secondary memory storage (like HDD and FLASH memory). In the ‘block’ based memory allocation, a block
of fixed memory is always allocated for tasks on need basis and it is taken as a unit. Hence, there will not
be any memory fragmentation issues. The memory allocation can be implemented as constant functions and
thereby it consumes fixed amount of time for memory allocation. This leaves the deterministic behaviour of
the RTOS kernel untouched. The ‘block’ memory concept avoids the garbage collection overhead also. (We
will explore this technique under the MicroC/OS-II kernel in a latter chapter).The ‘block’ based memory

* Virtual Memory is an imaginary memory supported by certain operating systems. Virtual memory expands the address space available
to a task beyond the actual physical memory (RAM) supported by the system. Virtual memory is implemented with the help of a
Memory Management Unit (MMU) and ‘memory paging’. The program memory for a task can be viewed as different pages and the
page corresponding to a piece of code that needs to be executed is loaded into the main physical memory (RAM). When a memory page
is no longer required, it is moved out to secondary storage memory and another page which contains the code snippet to be executed is
loaded into the main memory. This memory movement technique is known as demand paging. The MMU handles the demand paging
and converts the virtual address of a location in a page to corresponding physical address in the RAM.
 Real-Time Opera ng System (RTOS) based Embedded System Design 395

allocation achieves deterministic behaviour with the trade-of limited choice of memory chunk size and
suboptimal memory usage.
Interrupt Handling Deals with the handling of various types of interrupts. Interrupts provide Real-Time
behaviour to systems. Interrupts inform the processor that an external device or an associated task requires
immediate attention of the CPU. Interrupts can be either Synchronous or Asynchronous. Interrupts which
occurs in sync with the currently executing task is known as Synchronous interrupts. Usually the software
interrupts fall under the Synchronous Interrupt category. Divide by zero, memory segmentation error, etc. are
examples of synchronous interrupts. For synchronous interrupts, the interrupt handler runs in the same context
of the interrupting task. Asynchronous interrupts are interrupts, which occurs at any point of execution of any
task, and are not in sync with the currently executing task. The interrupts generated by external devices (by
asserting the interrupt line of the processor/controller to which the interrupt line of the device is connected)
connected to the processor/controller, timer overflow interrupts, serial data reception/ transmission interrupts,
etc. are examples for asynchronous interrupts. For asynchronous interrupts, the interrupt handler is usually
written as separate task (Depends on OS kernel implementation) and it runs in a different context. Hence,
a context switch happens while handling the asynchronous interrupts. Priority levels can be assigned to the
interrupts and each interrupts can be enabled or disabled individually. Most of the RTOS kernel implements
‘Nested Interrupts’ architecture. Interrupt nesting allows the pre-emption (interruption) of an Interrupt Service
Routine (ISR), servicing an interrupt, by a high priority interrupt.
Time Management Accurate time management is essential for providing precise time reference for all
applications. The time reference to kernel is provided by a high-resolution Real-Time Clock (RTC) hardware
chip (hardware timer). The hardware timer is programmed to interrupt the processor/controller at a fixed rate.
This timer interrupt is referred as ‘Timer tick’. The ‘Timer tick’ is taken as the timing reference by the kernel.
The ‘Timer tick’ interval may vary depending on the hardware timer. Usually the ‘Timer tick’ varies in the
microseconds range. The time parameters for tasks are expressed as the multiples of the ‘Timer tick’.
The System time is updated based on the ‘Timer tick’. If the System time register is 32 bits wide and the
‘Timer tick’ interval is 1 microsecond, the System time register will reset in
232 * 10–6/ (24 * 60 * 60) = 49700 Days = ~ 0.0497 Days = 1.19 Hours
If the ‘Timer tick’ interval is 1 millisecond, the system time register will reset in
232 * 10–3 / (24 * 60 * 60) = 497 Days = 49.7 Days = ~ 50 Days
The ‘Timer tick’ interrupt is handled by the ‘Timer Interrupt’ handler of kernel. The ‘Timer tick’ interrupt
can be utilised for implementing the following actions.
∑ Save the current context (Context of the currently executing task).
∑ Increment the System time register by one. Generate timing error and reset the System time register if
the timer tick count is greater than the maximum range available for System time register.
∑ Update the timers implemented in kernel (Increment or decrement the timer registers for each timer
depending on the count direction setting for each register. Increment registers with count direction
setting = ‘count up’ and decrement registers with count direction setting = ‘count down’).
∑ Activate the periodic tasks, which are in the idle state.
∑ Invoke the scheduler and schedule the tasks again based on the scheduling algorithm.
∑ Delete all the terminated tasks and their associated data structures (TCBs)
∑ Load the context for the first task in the ready queue. Due to the re-scheduling, the ready task might be
changed to a new one from the task, which was preempted by the ‘Timer Interrupt’ task.
Apart from these basic functions, some RTOS provide other functionalities also (Examples are file
management and network functions). Some RTOS kernel provides options for selecting the required kernel
396 Introduc on to Embedded Systems

functions at the time of building a kernel. The user can pick the required functions from the set of available
functions and compile the same to generate the kernel binary. Windows CE is a typical example for such an
RTOS. While building the target, the user can select the required components for the kernel.
[Link] Hard Real-Time
Real-Time Operating Systems that strictly adhere to the timing constraints for a task is referred as ‘Hard
Real-Time’ systems. A Hard Real-Time system must meet the deadlines for a task without any slippage.
Missing any deadline may produce catastrophic results for Hard Real-Time Systems, including permanent
data lose and irrecoverable damages to the system/users. Hard Real-Time systems emphasise the principle ‘A
late answer is a wrong answer’. A system can have several such tasks and the key to their correct operation
lies in scheduling them so that they meet their time constraints. Air bag control systems and Anti-lock Brake
Systems (ABS) of vehicles are typical examples for Hard Real-Time Systems. The Air bag control system
should be into action and deploy the air bags when the vehicle meets a severe accident. Ideally speaking, the
time for triggering the air bag deployment task, when an accident is sensed by the Air bag control system,
should be zero and the air bags should be deployed exactly within the time frame, which is predefined for
the air bag deployment task. Any delay in the deployment of the air bags makes the life of the passengers
under threat. When the air bag deployment task is triggered, the currently executing task must be pre-empted,
the air bag deployment task should be brought into execution, and the necessary I/O systems should be
made readily available for the air bag deployment task. To meet the strict deadline, the time between the
air bag deployment event triggering and start of the air bag deployment task execution should be minimum,
ideally zero. As a rule of thumb, Hard Real-Time Systems does not implement the virtual memory model for
handling the memory. This eliminates the delay in swapping in and out the code corresponding to the task
to and from the primary memory. In general, the presence of Human in the loop (HITL) for tasks introduces
unexpected delays in the task execution. Most of the Hard Real-Time Systems are automatic and does not
contain a ‘human in the loop’.
[Link] So Real-Time
Real-Time Operating System that does not guarantee meeting deadlines, but offer the best effort to meet the
deadline are referred as ‘Soft Real-Time’ systems. Missing deadlines for tasks are acceptable for a Soft Real-
time system if the frequency of deadline missing is within the compliance limit of the Quality of Service
(QoS). A Soft Real-Time system emphasises the principle ‘A late answer is an acceptable answer, but it could
have done bit faster’. Soft Real-Time systems most often have a ‘human in the loop (HITL)’. Automatic Teller
Machine (ATM) is a typical example for Soft-Real-Time System. If the ATM takes a few seconds more than
the ideal operation time, nothing fatal happens. An audio-video playback system is another example for Soft
Real-Time system. No potential damage arises if a sample comes late by fraction of a second, for playback.

10.3 TASKS, PROCESS AND THREADS

The term ‘task’ refers to something that needs to be done. In our day-to-day life,
LO 3 Discuss
we are bound to the execution of a number of tasks. The task can be the one
tasks, processes
assigned by our managers or the one assigned by our professors/teachers or the
and threads in the
one related to our personal or family needs. In addition, we will have an order of
operating system
priority and schedule/timeline for executing these tasks. In the operating system
context
context, a task is defined as the program in execution and the related information
maintained by the operating system for the program. Task is also known as ‘Job’ in the operating system
context. A program or part of it in execution is also called a ‘Process’. The terms ‘Task’, ‘Job’ and ‘Process’
refer to the same entity in the operating system context and most often they are used interchangeably.
 Real-Time Opera ng System (RTOS) based Embedded System Design 397

10.3.1 Process
A ‘Process’ is a program, or part of it, in execution. Process is also known as an instance of a program in
execution. Multiple instances of the same program can execute simultaneously. A process requires various
system resources like CPU for executing the process, memory for storing the code corresponding to the process
and associated variables, I/O devices for information exchange, etc. A process is sequential in execution.
[Link] The Structure of a Process
The concept of ‘Process’ leads to concurrent execution (pseudo parallelism) of tasks and thereby the efficient
utilisation of the CPU and other system resources. Concurrent execution is achieved through the sharing of
CPU among the processes. A process mimics a processor in properties and holds a set of registers, process
status, a Program Counter (PC) to point to the next executable instruction of the process, a stack for holding the
local variables associated with the process and the code corresponding to the process. This can be visualised
as shown in Fig. 10.4.
A process which inherits all the properties of the CPU can be considered as a virtual processor, awaiting
its turn to have its properties switched into the physical processor. When the process gets its turn, its registers
and the program counter register becomes mapped to the physical registers of the CPU. From a memory
perspective, the memory occupied by the process is segregated into three regions, namely, Stack memory,
Data memory and Code memory (Fig. 10.5).

Process
Stack Memory
Stack
(Stack pointer) Stack memory grows
downwards
Working registers
Data memory grows
Status registers upwards

Program counter (PC)

Data Memory

Code memory
corresponding to the
Process Code Memory

Fig. 10.4 Structure of a Process Fig. 10.5 Memory organisation of a Process

The ‘Stack’ memory holds all temporary data such as variables local to the process. Data memory holds
all global data for the process. The code memory contains the program code (instructions) corresponding
to the process. On loading a process into the main memory, a specific area of memory is allocated for the
process. The stack memory usually starts (OS Kernel implementation dependent) at the highest memory
address from the memory area allocated for the process. Say for example, the memory map of the memory
area allocated for the process is 2048 to 2100, the stack memory starts at address 2100 and grows downwards
to accommodate the variables local to the process.
398 Introduc on to Embedded Systems

[Link] Process States and State Transi on

The creation of a process to its termination is not
Created
a single step operation. The process traverses
through a series of states during its transition from
the newly created state to the terminated state. The Incepted into memory
cycle through which a process changes its state from
‘newly created’ to ‘execution completed’ is known
as ‘Process Life Cycle’. The various states through
Ready
which a process traverses through during a Process mple
tion
d
C o q u i r e
Life Cycle indicates the current status of the process I/O e Ac
sourc
r e d Re
with respect to time and also provides information on S h a

Scheduled for
Interrupted or
what it is allowed to do next. Figure 10.6 represents

Execution
Preempted
the various states associated with a process. Blocked
The state at which a process is being created is
referred as ‘Created State’. The Operating System Wait
Wait ing fo
recognises a process in the ‘Created State’ but no ing fo r I/O
r Sha
red R
resources are allocated to the process. The state, esour
ce Running
where a process is incepted into the memory and
awaiting the processor time for execution, is known
as ‘Ready State’. At this stage, the process is placed Execution Completion
in the ‘Ready list’ queue maintained by the OS.
The state where in the source code instructions
corresponding to the process is being executed is Completed
called ‘Running State’. Running state is the state
at which the process execution happens. ‘Blocked
State/Wait State’ refers to a state where a running Fig. 10.6 Process states and state transition representation
process is temporarily suspended from execution
and does not have immediate access to resources. The blocked state might be invoked by various conditions
like: the process enters a wait state for an event to occur (e.g. Waiting for user inputs such as keyboard input)
or waiting for getting access to a shared resource (will be discussed at a later section of this chapter). A state
where the process completes its execution is known as ‘Completed State’. The transition of a process from
one state to another is known as ‘State transition’. When a process changes its state from Ready to running
or from running to blocked or terminated or from blocked to running, the CPU allocation for the process may
also change.
It should be noted that the state representation for a process/task mentioned here is a generic representation.
The states associated with a task may be known with a different name or there may be more or less number
of states than the one explained here under different OS kernel. For example, under VxWorks’ kernel, the
tasks may be in either one or a specific combination of the states READY, PEND, DELAY and SUSPEND.
The PEND state represents a state where the task/process is blocked on waiting for I/O or system resource.
The DELAY state represents a state in which the task/process is sleeping and the SUSPEND state represents
a state where a task/process is temporarily suspended from execution and not available for execution. Under
MicroC/OS-II kernel, the tasks may be in one of the states, DORMANT, READY, RUNNING, WAITING
or INTERRUPTED. The DORMANT state represents the ‘Created’ state and WAITING state represents the
state in which a process waits for shared resource or I/O access. We will discuss about the states and state
transition for tasks under VxWorks and uC/OS-II kernel in a later chapter.
 Real-Time Opera ng System (RTOS) based Embedded System Design 399

[Link] Process Management

Process management deals with the creation of a process, setting up the memory space for the process, loading
the process’s code into the memory space, allocating system resources, setting up a Process Control Block
(PCB) for the process and process termination/deletion. For more details on Process Management, refer to the
section ‘Task/Process management’ given under the topic ‘The Real-Time Kernel’ of this chapter.

10.3.2 Threads
A thread is the primitive that can execute code. A
thread is a single sequential flow of control within Stack memory for Thread 1
a process. ‘Thread’ is also known as lightweight
process. A process can have many threads of Stack memory for Thread 2
Stack Memory
execution. Different threads, which are part of a for Process
process, share the same address space; meaning
they share the data memory, code memory and heap
memory area. Threads maintain their own thread
status (CPU register values), Program Counter (PC) Data memory for process
and stack. The memory model for a process and its
associated threads are given in Fig. 10.7. Code memory for process
[Link] The Concept of Mul threading
Fig. 10.7 Memory organisation of a Process and its
A process/task in embedded application may be a
associated Threads
complex or lengthy one and it may contain various
suboperations like getting input from I/O devices connected to the processor, performing some internal
calculations/operations, updating some I/O devices etc. If all the subfunctions of a task are executed in
sequence, the CPU utilisation may not be efficient. For example, if the process is waiting for a user input,
the CPU enters the wait state for the event, and the process execution also enters a wait state. Instead of this
single sequential execution of the whole process, if the task/process is split into different threads carrying
out the different subfunctionalities of the process, the CPU can be effectively utilised and when the thread
corresponding to the I/O operation enters the wait state, another threads which do not require the I/O event
for their operation can be switched into execution. This leads to more speedy execution of the process and
the efficient utilisation of the processor time and resources. The multithreaded architecture of a process can
be better visualised with the thread-process diagram shown in Fig. 10.8.
If the process is split into multiple threads, which executes a portion of the process, there will be a main
thread and rest of the threads will be created within the main thread. Use of multiple threads to execute a
process brings the following advantage.
∑ Better memory utilisation. Multiple threads of the same process share the address space for data
memory. This also reduces the complexity of inter thread communication since variables can be shared
across the threads.
∑ Since the process is split into different threads, when one thread enters a wait state, the CPU can be
utilised by other threads of the process that do not require the event, which the other thread is waiting,
for processing. This speeds up the execution of the process.
∑ Efficient CPU utilisation. The CPU is engaged all time.
400 Introduc on to Embedded Systems

Task/Process

Code memory

Data memory

Stack Stack Stack

Registers Registers Registers

Thread 1 Thread 2 Thread 3

void main (void) int ChildThread 1 int ChildThread 2
{ (void) (void)
//Create child { {
thread 1 //Do something //Do something
CreateThread (NULL,
1000,(LPTHREAD_STA
RT_ROUTINE ) } }
ChildThread 1,NULL,
0, &dwThreadID );
//Create child
thread 2
CreateThread (NULL,
1000,(LPTHREAD_STA
RT_ROUTINE )
ChildThread 2,NULL,
0, &dwThreadID );
}

Fig. 10.8 Process with multi-threads

[Link] Thread Standards

Thread standards deal with the different standards available for thread creation and management. These
standards are utilised by the operating systems for thread creation and thread management. It is a set of thread
class libraries. The commonly available thread class libraries are explained below.
POSIX Threads POSIX stands for Portable Operating System Interface. The POSIX.4 standard deals with
the Real-Time extensions and POSIX.4a standard deals with thread extensions. The POSIX standard library
for thread creation and management is ‘Pthreads’. ‘Pthreads’ library defines the set of POSIX thread creation
and management functions in ‘C’ language.
The primitive
int pthread_create(pthread_t *new_thread_ID, const pthread_attr_t
*attribute, void * (*start_function)(void *), void *arguments);
creates a new thread for running the function start_ function. Here pthread_t is the handle to the newly
created thread and pthread_attr_t is the data type for holding the thread attributes. ‘start_function’ is the
 Real-Time Opera ng System (RTOS) based Embedded System Design 401

function the thread is going to execute and arguments is the arguments for ‘start_function’ (It is a void * in
the above example). On successful creation of a Pthread, pthread_create() associates the Thread Control
Block (TCB) corresponding to the newly created thread to the variable of type pthread_t (new_thread_ID in
our example).
The primitive
int pthread_join(pthread_t new_thread,void * *thread_status);
blocks the current thread and waits until the completion of the thread pointed by it (In this example new_
thread )
All the POSIX ‘thread calls’ returns an integer. A return value of zero indicates the success of the call. It
is always good to check the return value of each call.

Example 1
Write a multithreaded application to print “Hello I’m in main thread” from the main thread and “Hello I’m in
new thread” 5 times each, using the pthread_create() and pthread_join() POSIX primitives.
//Assumes the application is running on an OS where POSIX library is
//available
#include <pthread.h>
#include <stdlib.h>
#include <stdio.h>
//******************************************************************
//New thread function for printing “Hello I’m in new thread”
void *new_thread( void *thread_args )
{
int i, j;
for( j= 0; j < 5; j++ )
{
printf(“Hello I’m in new thread\n” );
//Wait for some time. Do nothing
//The following line of code can be replaced with
//OS supported delay function like sleep(), delay () etc…
for( i= 0; i < 10000; i++ );
}
return NULL;
}
//******************************************************************
//Start of main thread
int main( void )
{
int i, j;
pthread_t tcb;
//Create the new thread for executing new_thread function
if (pthread_create( &tcb, NULL, new_thread, NULL ))
{
//New thread creation failed
printf(“Error in creating new thread\n” );
402 Introduc on to Embedded Systems

return -1;
}
for( j= 0; j < 5; j++ )
{
printf(“Hello I’m in main thread\n” );
//Wait for some time. Do nothing
//The following line of code can be replaced with
//OS supported delay function like sleep(), delay etc…
for( i= 0; i < 10000; i++ );
}
if (pthread_join(tcb, NULL ))
{
//Thread join failed
printf(“Error in Thread join\n” );
return -1;
}
return 1;
}
You can compile this application using the gcc compiler. Examine the output to figure out the thread
execution switching. The lines printed will give an idea of the order in which the thread execution is switched
between. The pthread_join call forces the main thread to wait until the completion of the thread tcb, if the
main thread finishes the execution first.
The termination of a thread can happen in different ways. The thread can terminate either by completing
its execution (natural termination) or by a forced termination. In a natural termination, the thread completes
its execution and returns back to the main thread through a simple return or by executing the pthread_exit()
call. Forced termination can be achieved by the call pthread_cancel() or through the termination of the main
thread with exit or exec functions. pthread_cancel() call is used by a thread to terminate another thread.
pthread_exit() call is used by a thread to explicitly exit after it completes its work and is no longer required
to exist. If the main thread finishes before the threads it has created, and exits with pthread_exit(), the other
threads continue to execute. If the main thread uses exit call to exit the thread, all threads created by the main
thread is terminated forcefully. Exiting a thread with the call pthread_exit() will not perform a cleanup. It
will not close any files opened by the thread and files will remain in the open status even after the thread
terminates. Calling pthread_join at the end of the main thread is the best way to achieve synchronisation and
proper cleanup. The main thread, after finishing its task waits for the completion of other threads, which were
joined to it using the pthread_join call. With a pthread_join call, the main thread waits other threads, which
were joined to it, and finally merges to the single main thread. If a new thread spawned by the main thread
is still not joined to the main thread, it will be counted against the system’s maximum thread limit. Improper
cleanup will lead to the failure of new thread creation.
Win32 Threads Win32 threads are the threads supported by various flavours of Windows Operating
Systems. The Win32 Application Programming Interface (Win32 API) libraries provide the standard set of
Win32 thread creation and management functions. Win32 threads are created with the API
HANDLE CreateThread(LPSECURITY_ATTRIBUTES lpThreadAttributes,DWORD
dwStackSize, LPTHREAD_START_ROUTINE lpStartAddress, LPVOID lpParameter,
DWORD dwCreationFlags, LPDWORD lpThreadId );
 Real-Time Opera ng System (RTOS) based Embedded System Design 403

The parameter lpThreadAttributes defines the security attributes for the thread and dwStackSize defines the
stack size for the thread. These two parameters are not supported by the Windows CE/Embedded Compact
Real-Time Operating Systems and it should be kept as NULL and 0 respectively in a CreateThread API Call.
The other parameters are
lpStartAddress: Pointer to the function which is to be executed by the thread.
lpParameter: Parameter specifying an application-defined value that is passed to the thread routine.
dwCreationFlags: Defines the state of the thread when it is created. Usually it is kept as 0 or CREATE_
SUSPENDED implying the thread is created and kept at the suspended state.
lpThreadId: Pointer to a DWORD that receives the identifier for the thread.
On successful creation of the thread, CreateThread returns the handle to the thread and the thread
identifier.
The API GetCurrentThread(void) returns the handle of the current thread and GetCurrentThreadId(void)
returns its ID. GetThreadPriority (HANDLE hThread) API returns an integer value representing the current
priority of the thread whose handle is passed as hThread. Threads are always created with normal priority
(THREAD_PRIORITY_NORMAL. Refer MSDN documentation for the different thread priorities and their
meaning). SetThreadPriority (HANDLE hThread, int nPriority) API is used for setting the priority of a thread.
The first parameter to this function represents the thread handle and the second one the thread priority.
For Win32 threads, the normal thread termination happens when an exception occurs in the thread, or when
the thread’s execution is completed or when the primary thread or the process to which the thread is associated
is terminated. A thread can exit itself by calling the ExitThread (DWORD dwExitCode) API. The parameter
dwExitCode sets the exit code for thread termination. Calling ExitThread API frees all the resources utilised
by the thread. The exit code of a thread can be checked by other threads by calling the GetExitCodeThread
(HANDLE hThread, LPDWORD lpExitCode). TerminateThread (HANDLE hThread, DWORD dwExitCode)
API is used for terminating a thread from another thread. The handle hThread indicates which thread is
to be terminated and dwExitCode sets the exit code for the thread. This API will not execute the thread
termination and clean up code and may not free the resources occupied by the thread. TerminateThread is a
potentially dangerous call and it should not be used in normal conditions as a mechanism for terminating a
thread. Use this call only as a final choice. When a thread is terminated through TerminateThread method, the
system releases the thread’s initial stack and the thread will not get a chance to execute any user-mode code.
Also any dynamic link libraries (dlls) attached to the thread are not notified that the thread is terminating.
TerminateThread can lead to potential issues like: Non-releasing of the critical section object, any, owned
by the thread, non-releasing of heap lock, if the thread is allocating memory from the heap, inconsistencies
of the kernel32 state for the thread’s process if the thread was executing certain kernel32 call when it is
terminated, issues in shared dll functions, if the thread was manipulating the global state of a shared dll
when it is terminated etc. SuspendThread(HANDLE hThread) API can be used for suspending a thread
from execution provided the handle hThread possesses THREAD_SUSPEND_RESUME access right. If the
SuspendThread API call succeeds, the thread stops executing and increments its internal suspend count. The
thread becomes suspended if its suspend count is greater than zero. The SuspendThread function is primarily
designed for use by debuggers. One must be cautious in using this API for the reason it may cause deadlock
condition if the thread is suspended at a stage where it acquired a mutex or shared resource and another
thread tries to access the same. The ResumeThread(HANDLE hThread) API is used for resuming a suspended
thread. The ResumeThread API checks the suspend count of the specified thread. A suspend count of zero
indicates that the specified thread is not currently in the suspended mode. If the count is not zero, the count is
decremented by one and if the resulting count value is zero, the thread is resumed. The API Sleep (DWORD
404 Introduc on to Embedded Systems

dwMilliseconds) can be used for suspending a thread for the duration specified in milliseconds by the Sleep
function. The Sleep call is initiated by the thread.

Example 2
Write a multithreaded application using Win32 APIs to set up a counter in the main thread and secondary
thread to count from 0 to 10 and print the counts from both the threads. Put a delay of 500 ms in between the
successive printing in both the threads.
#include “stdafx.h”
#include “windows.h”
#include “stdio.h”
//******************************************************************
//Child thread
//******************************************************************
void ChildThread(void)
{
char i;
for (i = 0; i <= 10; ++i)
{
printf(“Executing Child Thread : Counter = %d\n”, i);
Sleep(500);
}
}
//******************************************************************
//Primary thread
//******************************************************************
int main(int argc, char* argv[])
{
HANDLE hThread;
DWORD dwThreadID;
char i;
hThread = CreateThread(NULL, 1000, (LPTHREAD_START_ROUTINE)ChildThread,
NULL, 0, &dwThreadID);
if (hThread == NULL)
{
printf(“Thread Creation Failed\nError No : %d\n”, GetLastError());
return 1;
}
for (i = 0; i <= 10; ++i)
{
printf(“Executing Main Thread : Counter = %d\n”, i);
Sleep(500);
}
return 0;
}
 Real-Time Opera ng System (RTOS) based Embedded System Design 405

To execute this program, create a new Win32 Console Application with Microsoft Visual Studio using
Visual C++ and add the above piece of code to it and compile. The output obtained on running this application
on a machine with Windows 10 operating system is given in Fig. 10.9.

Fig. 10.9 Output of the Win32 Multithreaded application

If you examine the output, you can see the switching between main and child threads. The output need not
be the same always. The output is purely dependent on the scheduling policies implemented by the windows
operating system for thread scheduling. You may get the same output or a different output each time you run
the application.
Java Threads Java threads are the threads supported by Java programming Language. The java thread
class ‘Thread’ is defined in the package ‘[Link]’. This package needs to be imported for using the thread
creation functions supported by the Java thread class. There are two ways of creating threads in Java: Either
by extending the base ‘Thread’ class or by implementing an interface. Extending the thread class allows
inheriting the methods and variables of the parent class (Thread class) only whereas interface allows a way
to achieve the requirements for a set of classes. The following piece of code illustrates the implementation of
Java threads with extending the thread base class ‘Thread’.
import [Link].*;
public class MyThread extends Thread
{
public void run()
{
[Link](“Hello from MyThread!”);
}
public static void main(String args[])
{
(new MyThread()).start();
}
}
406 Introduc on to Embedded Systems

The above piece of code creates a new class MyThread by extending the base class Thread. It also
overrides the run() method inherited from the base class with its own run() method. The run() method of
MyThread implements all the task for the MyThread thread. The method start() moves the thread to a pool
of threads waiting for their turn to be picked up for execution by the scheduler. The thread is said to be in the
‘Ready’ state at this stage. The scheduler picks the threads for execution from the pool based on the thread
priorities.
E.g. [Link]();
The output of the above piece of code when executed on Windows 10 platform is given in Fig. 10.10.

Fig. 10.10 Output of the Java Multithreaded application

Invoking the static method yield() voluntarily give up the execution of the thread and the thread is moved
to the pool of threads waiting to get their turn for execution, i.e. the thread enters the ‘Ready’ state.
E.g. [Link]();
The static method sleep() forces the thread to sleep for the duration mentioned by the sleep call, i.e. the
thread enters the ‘Suspend’ mode. Once the sleep period is expired, the thread is moved to the pool of threads
waiting to get their turn for execution, i.e. the thread enters the ‘Ready’ state. The method sleep() only
guarantees that the thread will sleep for the minimum period mentioned by the argument to the call. It will not
guarantee anything on the resume of the thread after the sleep period. It is dependent on the scheduler.
E.g. [Link](100); Sleep for 100 milliseconds.
Calling a thread Object’s wait() method causes the thread object to wait. The thread will remain in the
‘Wait’ state until another thread invokes the notify() or notifyAll() method of the thread object which is
waiting. The thread enters the ‘Blocked’ state when waiting for input from I/O devices or waiting for object
lock in case of accessing shared resources. The thread is moved to the ‘Ready’ state on receiving the I/O
input or on acquiring the object lock. The thread enters the ‘Finished/Dead’ state on completion of the task
assigned to it or when the stop() method is explicitly invoked. The thread may also enter this state if it is
terminated by an unrecoverable error condition.
For more information on Java threads, visit Sun Micro System’s tutorial on Threads, available at http://
[Link]/tutorial/applet/overview/[Link]
Summary So far we discussed about the various thread classes available for creation and management of
threads in a multithreaded system in a General Purpose Operating System’s perspective. From an RTOS
perspective, POSIX threads and Win32 threads are the most commonly used thread class libraries for thread
creation and management. Many non-standard, proprietary thread classes are also used by some proprietary
RTOS. Portable threads (Pth), a very portable POSIX/ANSI-C based library from GNU, may be the “next
generation” threads library. Pth provides non-preemptive priority based scheduling for multiple threads inside
event driven applications. Visit [Link] for more details on GNU Portable threads.
 Real-Time Opera ng System (RTOS) based Embedded System Design 407

[Link] Thread Pre-emp on

Thread pre-emption is the act of pre-empting the currently running thread (stopping the currently running thread
temporarily). Thread pre-emption ability is solely dependent on the Operating System. Thread pre-emption
is performed for sharing the CPU time among all the threads. The execution switching among threads are
known as ‘Thread context switching’. Thread context switching is dependent on the Operating system’s
scheduler and the type of the thread. When we say ‘Thread’, it falls into any one of the following types.
User Level Thread User level threads do not have kernel/Operating System support and they exist solely in
the running process. Even if a process contains multiple user level threads, the OS treats it as single thread
and will not switch the execution among the different threads of it. It is the responsibility of the process to
schedule each thread as and when required. In summary, user level threads of a process are non-preemptive
at thread level from OS perspective.
Kernel/System Level Thread Kernel level threads are individual units of execution, which the OS treats
as separate threads. The OS interrupts the execution of the currently running kernel thread and switches the
execution to another kernel thread based on the scheduling policies implemented by the OS. In summary
kernel level threads are pre-emptive.
For user level threads, the execution switching (thread context switching) happens only when the currently
executing user level thread is voluntarily blocked. Hence, no OS intervention and system calls are involved
in the context switching of user level threads. This makes context switching of user level threads very fast.
On the other hand, kernel level threads involve lots of kernel overhead and involve system calls for context
switching. However, kernel threads maintain a clear layer of abstraction and allow threads to use system calls
independently. There are many ways for binding user level threads with system/kernel level threads. The
following section gives an overview of various thread binding models.
Many-to-One Model Here many user level threads are mapped to a single kernel thread. In this model,
the kernel treats all user level threads as single thread and the execution switching among the user level
threads happens when a currently executing user level thread voluntarily blocks itself or relinquishes the
CPU. Solaris Green threads and GNU Portable Threads are examples for this. The ‘PThread’ example given
under the POSIX thread library section is an illustrative example for application with Many-to-One thread
model.
One-to-One Model In One-to-One model, each user level thread is bonded to a kernel/system level thread.
Windows NT and Linux threads are examples for One-to-One thread models. The modified ‘PThread’
example given under the ‘Thread Pre-emption’ section is an illustrative example for application with One-
to-One thread model.
Many-to-Many Model In this model many user level threads are allowed to be mapped to many kernel
threads. Windows NT/2000 with ThreadFibre package is an example for this.
[Link] Thread v/s Process
I hope, by now you got a reasonably good knowledge of process and threads. Now let us summarise the
properties of process and threads.
Thread Process
Thread is a single unit of execution and is part of process. Process is a program in execution and contains one or
more threads.
A thread does not have its own data memory and heap Process has its own code memory, data memory and stack
memory. It shares the data memory and heap memory with memory.
other threads of the same process.
408 Introduc on to Embedded Systems

A thread cannot live independently; it lives within the A process contains at least one thread.
process.
There can be multiple threads in a process. The first thread Threads within a process share the code, data and heap
(main thread) calls the main function and occupies the start memory. Each thread holds separate memory area for stack
of the stack memory of the process. (shares the total stack memory of the process).
Threads are very inexpensive to create Processes are very expensive to create. Involves many OS
overhead.
Context switching is inexpensive and fast Context switching is complex and involves lot of OS over-
head and is comparatively slower.
If a thread expires, its stack is reclaimed by the process. If a process dies, the resources allocated to it are reclaimed
by the OS and all the associated threads of the process
also dies.

10.4 MULTIPROCESSING AND MULTITASKING

The terms multiprocessing and multitasking are a little confusing and sounds alike.
LO 4 Understand
In the operating system context multiprocessing describes the ability to execute
the difference
multiple processes simultaneously. Systems which are capable of performing
between
multiprocessing, are known as multiprocessor systems. Multiprocessor systems
multiprocessing
possess multiple CPUs and can execute multiple processes simultaneously.
and multitasking
The ability of the operating system to have multiple programs in memory,
which are ready for execution, is referred as multiprogramming. In a uniprocessor system, it is not possible
to execute multiple processes simultaneously. However, it is possible for a uniprocessor system to achieve
some degree of pseudo parallelism in the execution of multiple processes by switching the execution among
different processes. The ability of an operating system to hold multiple processes in memory and switch
the processor (CPU) from executing one process to another process is known as multitasking. Multitasking
creates the illusion of multiple tasks executing in parallel. Multitasking involves the switching of CPU from
executing one task to another. In an earlier section ‘The Structure of a Process’ of this chapter, we learned
that a Process is identical to the physical processor in the sense it has own register set which mirrors the
CPU registers, stack and Program Counter (PC). Hence, a ‘process’ is considered as a ‘Virtual processor’,
awaiting its turn to have its properties switched into the physical processor. In a multitasking environment,
when task/process switching happens, the virtual processor (task/process) gets its properties converted into
that of the physical processor. The switching of the virtual processor to physical processor is controlled by the
scheduler of the OS kernel. Whenever a CPU switching happens, the current context of execution should be
saved to retrieve it at a later point of time when the CPU executes the process, which is interrupted currently
due to execution switching. The context saving and retrieval is essential for resuming a process exactly from
the point where it was interrupted due to CPU switching. The act of switching CPU among the processes or
changing the current execution context is known as ‘Context switching’. The act of saving the current context
which contains the context details (Register details, memory details, system resource usage details, execution
details, etc.) for the currently running process at the time of CPU switching is known as ‘Context saving’.
The process of retrieving the saved context details for a process, which is going to be executed due to CPU
switching, is known as ‘Context retrieval’. Multitasking involves ‘Context switching’ (Fig. 10.11), ‘Context
saving’ and ‘Context retrieval’.
Toss Juggling The skilful object manipulation game is a classic real world example for the multitasking
illusion. The juggler uses a number of objects (balls, rings, etc.) and throws them up and catches them. At
 Real-Time Opera ng System (RTOS) based Embedded System Design 409

any point of time, he throws only one ball and catches only one per hand. However, the speed at which he is
switching the balls for throwing and catching creates the illusion, he is throwing and catching multiple balls
or using more than two hands ☺ simultaneously, to the spectators.

3. Reload Context for Process 2 from PCB1

3. Reload Context for Process 1 from PCB0

Idle

2. Perform other OS operations related to

2. Perform other OS operations related to

Execution switches to Process 2

Execution switches to Process 1

(Interrupt or System Call)

(Interrupt or System Call)

Running
1. Save Current context into PCB0

1. Save Current context into PCB1

‘Context Switching’

‘Context Switching’
Processes

Delay in execution of Delay in execution of

Process 2 happened Process 1 happened
due to ‘Context due to ‘Context
Switching’ Switching’
Process 2 Idle Running Waits in ‘Ready’ Queue

Process 1 Running Waits in ‘Ready’ Queue Idle Running

Time

Fig. 10.11 Context switching

10.4.1 Types of Multitasking

As we discussed earlier, multitasking involves the switching of execution among multiple tasks. Depending
on how the switching act is implemented, multitasking can be classified into different types. The following
section describes the various types of multitasking existing in the Operating System’s context.
[Link] Co-opera ve Mul tasking
Co-operative multitasking is the most primitive form of multitasking in which a task/process gets a chance to
execute only when the currently executing task/process voluntarily relinquishes the CPU. In this method, any
task/process can hold the CPU as much time as it wants. Since this type of implementation involves the mercy
of the tasks each other for getting the CPU time for execution, it is known as co-operative multitasking. If the
currently executing task is non-cooperative, the other tasks may have to wait for a long time to get the CPU.
[Link] Preemp ve Mul tasking
Preemptive multitasking ensures that every task/process gets a chance to execute. When and how much time
a process gets is dependent on the implementation of the preemptive scheduling. As the name indicates, in
preemptive multitasking, the currently running task/process is preempted to give a chance to other tasks/
process to execute. The preemption of task may be based on time slots or task/process priority.
[Link] Non-preemp ve Mul tasking
In non-preemptive multitasking, the process/task, which is currently given the CPU time, is allowed to
execute until it terminates (enters the ‘Completed’ state) or enters the ‘Blocked/Wait’ state, waiting for an I/O
410 Introduc on to Embedded Systems

or system resource. The co-operative and non-preemptive multitasking differs in their behaviour when they
are in the ‘Blocked/Wait’ state. In co-operative multitasking, the currently executing process/task need not
relinquish the CPU when it enters the ‘Blocked/Wait’ state, waiting for an I/O, or a shared resource access or
an event to occur whereas in non-preemptive multitasking the currently executing task relinquishes the CPU
when it waits for an I/O or system resource or an event to occur.

10.5 TASK SCHEDULING

As we already discussed, multitasking involves the execution switching among
LO 5 Describe the different tasks. There should be some mechanism in place to share the CPU
the FCFS/FIFO, among the different tasks and to decide which process/task is to be executed at a
LCFS/LIFO, SJF given point of time. Determining which task/process is to be executed at a given
and priority based point of time is known as task/process scheduling. Task scheduling forms the
task/process basis of multitasking. Scheduling policies forms the guidelines for determining
scheduling which task is to be executed when. The scheduling policies are implemented in an
algorithm and it is run by the kernel as a service. The kernel service/application,
which implements the scheduling algorithm, is known as ‘Scheduler’. The process scheduling decision may
take place when a process switches its state to
1. ‘Ready’ state from ‘Running’ state
2. ‘Blocked/Wait’ state from ‘Running’ state
3. ‘Ready’ state from ‘Blocked/Wait’ state
4. ‘Completed’ state
A process switches to ‘Ready’ state from the ‘Running’ state when it is preempted. Hence, the type of
scheduling in scenario 1 is pre-emptive. When a high priority process in the ‘Blocked/Wait’ state completes
its I/O and switches to the ‘Ready’ state, the scheduler picks it for execution if the scheduling policy used is
priority based preemptive. This is indicated by scenario 3. In preemptive/non-preemptive multitasking, the
process relinquishes the CPU when it enters the ‘Blocked/Wait’ state or the ‘Completed’ state and switching
of the CPU happens at this stage. Scheduling under scenario 2 can be either preemptive or non-preemptive.
Scheduling under scenario 4 can be preemptive, non-preemptive or co-operative.
The selection of a scheduling criterion/algorithm should consider the following factors:
CPU Utilisation: The scheduling algorithm should always make the CPU utilisation high. CPU utilisation is
a direct measure of how much percentage of the CPU is being utilised.
Throughput: This gives an indication of the number of processes executed per unit of time. The throughput
for a good scheduler should always be higher.
Turnaround Time: It is the amount of time taken by a process for completing its execution. It includes the
time spent by the process for waiting for the main memory, time spent in the ready queue, time spent on
completing the I/O operations, and the time spent in execution. The turnaround time should be a minimal for
a good scheduling algorithm.
Waiting Time: It is the amount of time spent by a process in the ‘Ready’ queue waiting to get the CPU time
for execution. The waiting time should be minimal for a good scheduling algorithm.
Response Time: It is the time elapsed between the submission of a process and the first response. For a good
scheduling algorithm, the response time should be as least as possible.
To summarise, a good scheduling algorithm has high CPU utilisation, minimum Turn Around Time
(TAT), maximum throughput and least response time.
 Real-Time Opera ng System (RTOS) based Embedded System Design 411

The Operating System maintains various queues† in connection with the CPU scheduling, and a process
passes through these queues during the course of its admittance to execution completion.
The various queues maintained by OS in association with CPU scheduling are:
Job Queue: Job queue contains all the processes in the system
Ready Queue: Contains all the processes, which are ready for execution and waiting for CPU to get their
turn for execution. The Ready queue is empty when there is no process ready for running.
Device Queue: Contains the set of processes, which are waiting for an I/O device.
A process migrates through all these queues during its journey from ‘Admitted’ to ‘Completed’ stage. The
following diagrammatic representation (Fig. 10.12) illustrates the transition of a process through the various
queues.

Fig. 10.12 Illustration of process transition through various queues

Based on the scheduling algorithm used, the scheduling can be classified into the following categories.

10.5.1 Non-preemptive Scheduling

Non-preemptive scheduling is employed in systems, which implement non-preemptive multitasking model.
In this scheduling type, the currently executing task/process is allowed to run until it terminates or enters the
‘Wait’ state waiting for an I/O or system resource. The various types of non-preemptive scheduling adopted
in task/process scheduling are listed below.

† Queue is a special kind of arrangement of a collection of objects. In the operating system context queue is considered as a buffer.
412 Introduc on to Embedded Systems

[Link] First-Come-First-Served (FCFS)/ FIFO Scheduling

As the name indicates, the First-Come-First-Served (FCFS) scheduling algorithm allocates CPU time to the
processes based on the order in which they enter the ‘Ready’ queue. The first entered process is serviced first.
It is same as any real world application where queue systems are used; e.g. Ticketing reservation system
where people need to stand in a queue and the first person standing in the queue is serviced first. FCFS
scheduling is also known as First In First Out (FIFO) where the process which is put first into the ‘Ready’
queue is serviced first.

Example 1
Three processes with process IDs P1, P2, P3 with estimated completion time 10, 5, 7 milliseconds respectively
enters the ready queue together in the order P1, P2, P3. Calculate the waiting time and Turn Around Time
(TAT) for each process and the average waiting time and Turn Around Time (Assuming there is no I/O
waiting for the processes).
The sequence of execution of the processes by the CPU is represented as

P1 P2 P3

0 10 15 22
10 5 7

Assuming the CPU is readily available at the time of arrival of P1, P1 starts executing without any waiting in
the ‘Ready’ queue. Hence the waiting time for P1 is zero. The waiting time for all processes are given as
Waiting Time for P1 = 0 ms (P1 starts executing first)
Waiting Time for P2 = 10 ms (P2 starts executing after completing P1)
Waiting Time for P3 = 15 ms (P3 starts executing after completing P1 and P2)
Average waiting time = (Waiting time for all processes) / No. of Processes
= (Waiting time for (P1+P2+P3)) / 3
= (0+10+15)/3 = 25/3
= 8.33 milliseconds
Turn Around Time (TAT) for P1 = 10 ms (Time spent in Ready Queue + Execution Time)
Turn Around Time (TAT) for P2 = 15 ms (-Do-)
Turn Around Time (TAT) for P3 = 22 ms (-Do-)
Average Turn Around Time = (Turn Around Time for all processes) / No. of Processes
= (Turn Around Time for (P1+P2+P3)) / 3
= (10+15+22)/3 = 47/3
= 15.66 milliseconds
Average Turn Around Time (TAT) is the sum of average waiting time and average execution time.
Average Execution Time = (Execution time for all processes)/No. of processes
= (Execution time for (P1+P2+P3))/3
= (10+5+7)/3 = 22/3
= 7.33
Average Turn Around Time = Average waiting time + Average execution time
= 8.33 + 7.33
= 15.66 milliseconds
 Real-Time Opera ng System (RTOS) based Embedded System Design 413

Example 2
Calculate the waiting time and Turn Around Time (TAT) for each process and the Average waiting time and
Turn Around Time (Assuming there is no I/O waiting for the processes) for the above example if the process
enters the ‘Ready’ queue together in the order P2, P1, P3.
The sequence of execution of the processes by the CPU is represented as

P2 P1 P3

0 5 15 22
5 10 7

Assuming the CPU is readily available at the time of arrival of P2, P2 starts executing without any waiting in
the ‘Ready’ queue. Hence the waiting time for P2 is zero. The waiting time for all processes is given as
Waiting Time for P2 = 0 ms (P2 starts executing first)
Waiting Time for P1 = 5 ms (P1 starts executing after completing P2)
Waiting Time for P3 = 15 ms (P3 starts executing after completing P2 and P1)
Average waiting time = (Waiting time for all processes) / No. of Processes
= (Waiting time for (P2+P1+P3)) / 3
= (0+5+15)/3 = 20/3
= 6.66 milliseconds
Turn Around Time (TAT) for P2 = 5 ms (Time spent in Ready Queue + Execution Time)
Turn Around Time (TAT) for P1 = 15 ms (-Do-)
Turn Around Time (TAT) for P3 = 22 ms (-Do-)
Average Turn Around Time = (Turn Around Time for all processes) / No. of Processes
= (Turn Around Time for (P2+P1+P3)) / 3
= (5+15+22)/3 = 42/3
= 14 milliseconds
The Average waiting time and Turn Around Time (TAT) depends on the order in which the processes
enter the ‘Ready’ queue, regardless there estimated completion time.
From the above two examples it is clear that the Average waiting time and Turn Around Time improve if
the process with shortest execution completion time is scheduled first.
The major drawback of FCFS algorithm is that it favours monopoly of process. A process, which does
not contain any I/O operation, continues its execution until it finishes its task. If the process contains any
I/O operation, the CPU is relinquished by the process. In general, FCFS favours CPU bound processes and
I/O bound processes may have to wait until the completion of CPU bound process, if the currently executing
process is a CPU bound process. This leads to poor device utilisation. The average waiting time is not
minimal for FCFS scheduling algorithm.
[Link] Last-Come-First Served (LCFS)/LIFO Scheduling
The Last-Come-First Served (LCFS) scheduling algorithm also allocates CPU time to the processes based
on the order in which they are entered in the ‘Ready’ queue. The last entered process is serviced first. LCFS
scheduling is also known as Last In First Out (LIFO) where the process, which is put last into the ‘Ready’
queue, is serviced first.

Example 1
Three processes with process IDs P1, P2, P3 with estimated completion time 10, 5, 7 milliseconds respectively
enters the ready queue together in the order P1, P2, P3 (Assume only P1 is present in the ‘Ready’ queue when
414 Introduc on to Embedded Systems

the scheduler picks it up and P2, P3 entered ‘Ready’ queue after that). Now a new process P4 with estimated
completion time 6 ms enters the ‘Ready’ queue after 5 ms of scheduling P1. Calculate the waiting time and
Turn Around Time (TAT) for each process and the Average waiting time and Turn Around Time (Assuming
there is no I/O waiting for the processes). Assume all the processes contain only CPU operation and no I/O
operations are involved.
Initially there is only P1 available in the Ready queue and the scheduling sequence will be P1, P3, P2. P4
enters the queue during the execution of P1 and becomes the last process entered the ‘Ready’ queue. Now the
order of execution changes to P1, P4, P3, and P2 as given below.

P1 P4 P3 P2

0 10 16 23 28
10 6 7 5

The waiting time for all the processes is given as

Waiting Time for P1 = 0 ms (P1 starts executing first)
Waiting Time for P4 = 5 ms (P4 starts executing after completing P1. But P4 arrived after 5 ms of execution of
P1. Hence its waiting time = Execution start time – Arrival Time = 10 – 5 = 5)
Waiting Time for P3 = 16 ms (P3 starts executing after completing P1 and P4)
Waiting Time for P2 = 23 ms (P2 starts executing after completing P1, P4 and P3)
Average waiting time = (Waiting time for all processes) / No. of Processes
= (Waiting time for (P1+P4+P3+P2)) / 4
= (0 + 5 + 16 + 23)/4 = 44/4
= 11 milliseconds
Turn Around Time (TAT) for P1 = 10 ms (Time spent in Ready Queue + Execution Time)
Turn Around Time (TAT) for P4 = 11 ms (Time spent in Ready Queue + Execution Time = (Execution
Start Time – Arrival Time) + Estimated Execution Time = (10
– 5) + 6 = 5 + 6)
Turn Around Time (TAT) for P3 = 23 ms (Time spent in Ready Queue + Execution Time)
Turn Around Time (TAT) for P2 = 28 ms (Time spent in Ready Queue + Execution Time)
Average Turn Around Time = (Turn Around Time for all processes) / No. of Processes
= (Turn Around Time for (P1+P4+P3+P2)) / 4
= (10+11+23+28)/4 = 72/4
= 18 milliseconds
LCFS scheduling is not optimal and it also possesses the same drawback as that of FCFS algorithm.
[Link] Shortest Job First (SJF) Scheduling
Shortest Job First (SJF) scheduling algorithm ‘sorts the ‘Ready’ queue’ each time a process relinquishes the
CPU (either the process terminates or enters the ‘Wait’ state waiting for I/O or system resource) to pick the
process with shortest (least) estimated completion/run time. In SJF, the process with the shortest estimated
run time is scheduled first, followed by the next shortest process, and so on.

Example 1
Three processes with process IDs P1, P2, P3 with estimated completion time 10, 5, 7 milliseconds respectively
enters the ready queue together. Calculate the waiting time and Turn Around Time (TAT) for each process
 Real-Time Opera ng System (RTOS) based Embedded System Design 415

and the Average waiting time and Turn Around Time (Assuming there is no I/O waiting for the processes) in
SJF algorithm.
The scheduler sorts the ‘Ready’ queue based on the shortest estimated completion time and schedules the
process with the least estimated completion time first and the next least one as second, and so on. The order
in which the processes are scheduled for execution is represented as

P2 P3 P1

0 5 12 22
5 7 10

The estimated execution time of P2 is the least (5 ms) followed by P3 (7 ms) and P1 (10 ms).
The waiting time for all processes are given as
Waiting Time for P2 = 0 ms (P2 starts executing first)
Waiting Time for P3 = 5 ms (P3 starts executing after completing P2)
Waiting Time for P1 = 12 ms (P1 starts executing after completing P2 and P3)
Average waiting time = (Waiting time for all processes) / No. of Processes
= (Waiting time for (P2+P3+P1)) / 3
= (0+5+12)/3 = 17/3
= 5.66 milliseconds
Turn Around Time (TAT) for P2 = 5 ms (Time spent in Ready Queue + Execution Time)
Turn Around Time (TAT) for P3 = 12 ms (-Do-)
Turn Around Time (TAT) for P1 = 22 ms (-Do-)
Average Turn Around Time = (Turn Around Time for all processes) / No. of Processes
= (Turn Around Time for (P2+P3+P1)) / 3
= (5+12+22)/3 = 39/3
= 13 milliseconds
Average Turn Around Time (TAT) is the sum of average waiting time and average execution time.
The average Execution time = (Execution time for all processes)/No. of processes
= (Execution time for (P1+P2+P3))/3
= (10+5+7)/3 = 22/3 = 7.33
Average Turn Around Time = Average Waiting time + Average Execution time
= 5.66 + 7.33
= 13 milliseconds
From this example, it is clear that the average waiting time and turn around time is much improved with the
SJF scheduling for the same processes when compared to the FCFS algorithm.

Example 2
Calculate the waiting time and Turn Around Time (TAT) for each process and the Average waiting time and
Turn Around Time for the above example if a new process P4 with estimated completion time 2 ms enters
the ‘Ready’ queue after 2 ms of execution of P2. Assume all the processes contain only CPU operation and
no I/O operations are involved.
At the beginning, there are only three processes (P1, P2 and P3) available in the ‘Ready’ queue and
the SJF scheduler picks up the process with the least execution completion time (In this example P2 with
416 Introduc on to Embedded Systems

execution completion time 5 ms) for scheduling. The execution sequence diagram for this is same as that of
Example 1.
Now process P4 with estimated execution completion time 2 ms enters the ‘Ready’ queue after 2 ms of
start of execution of P2. Since the SJF algorithm is non-preemptive and process P2 does not contain any I/O
operations, P2 continues its execution. After 5 ms of scheduling, P2 terminates and now the scheduler again
sorts the ‘Ready’ queue for process with least execution completion time. Since the execution completion
time for P4 (2 ms) is less than that of P3 (7 ms), which was supposed to be run after the completion of P2
as per the ‘Ready’ queue available at the beginning of execution scheduling, P4 is picked up for executing.
Due to the arrival of the process P4 with execution time 2 ms, the ‘Ready’ queue is re-sorted in the order P2,
P4, P3, P1. At the beginning it was P2, P3, P1. The execution sequence now changes as per the following
diagram

P2 P4 P3 P1

0 5 7 14 24
5 2 7 10

The waiting time for all the processes are given as

Waiting time for P2 = 0 ms (P2 starts executing first)
Waiting time for P4 = 3 ms (P4 starts executing after completing P2. But P4 arrived after 2 ms of execution
of P2. Hence its waiting time = Execution start time – Arrival Time = 5 – 2 = 3)
Waiting time for P3 = 7 ms (P3 starts executing after completing P2 and P4)
Waiting time for P1 = 14 ms (P1 starts executing after completing P2, P4 and P3)
Average waiting time = (Waiting time for all processes) / No. of Processes
= (Waiting time for (P2+P4+P3+P1)) / 4
= (0 + 3 + 7 + 14)/4 = 24/4
= 6 milliseconds
Turn Around Time (TAT) for P2 = 5 ms (Time spent in Ready Queue + Execution Time)
Turn Around Time (TAT) for P4 = 5 ms (Time spent in Ready Queue + Execution Time = (Execution Start
Time – Arrival Time) + Estimated Execution Time = (5 – 2) + 2
= 3 + 2)
Turn Around Time (TAT) for P3 = 14 ms (Time spent in Ready Queue + Execution Time)
Turn Around Time (TAT) for P1 = 24 ms (Time spent in Ready Queue + Execution Time)
Average Turn Around Time = (Turn Around Time for all Processes) / No. of Processes
= (Turn Around Time for (P2+P4+P3+P1)) / 4
= (5+5+14+24)/4 = 48/4
= 12 milliseconds
The average waiting time for a given set of process is minimal in SJF scheduling and so it is optimal
compared to other non-preemptive scheduling like FCFS. The major drawback of SJF algorithm is that
a process whose estimated execution completion time is high may not get a chance to execute if more
and more processes with least estimated execution time enters the ‘Ready’ queue before the process with
longest estimated execution time started its execution (In non-preemptive SJF ). This condition is known as
‘Starvation’. Another drawback of SJF is that it is difficult to know in advance the next shortest process in
the ‘Ready’ queue for scheduling since new processes with different estimated execution time keep entering
the ‘Ready’ queue at any point of time.
 Real-Time Opera ng System (RTOS) based Embedded System Design 417

[Link] Priority Based Scheduling

The Turn Around Time (TAT) and waiting time for processes in non-preemptive scheduling varies with the
type of scheduling algorithm. Priority based non-preemptive scheduling algorithm ensures that a process
with high priority is serviced at the earliest compared to other low priority processes in the ‘Ready’ queue.
The priority of a task/process can be indicated through various mechanisms. The Shortest Job First (SJF)
algorithm can be viewed as a priority based scheduling where each task is prioritised in the order of the
time required to complete the task. The lower the time required for completing a process the higher is its
priority in SJF algorithm. Another way of priority assigning is associating a priority to the task/process at
the time of creation of the task/process. The priority is a number ranging from 0 to the maximum priority
supported by the OS. The maximum level of priority is OS dependent. For Example, Windows CE supports
256 levels of priority (0 to 255 priority numbers). While creating the process/task, the priority can be assigned
to it. The priority number associated with a task/process is the direct indication of its priority. The priority
variation from high to low is represented by numbers from 0 to the maximum priority or by numbers from
maximum priority to 0. For Windows CE operating system a priority number 0 indicates the highest priority
and 255 indicates the lowest priority. This convention need not be universal and it depends on the kernel
level implementation of the priority structure. The non-preemptive priority based scheduler sorts the ‘Ready’
queue based on priority and picks the process with the highest level of priority for execution.

Example 1
Three processes with process IDs P1, P2, P3 with estimated completion time 10, 5, 7 milliseconds and priorities
0, 3, 2 (0—highest priority, 3—lowest priority) respectively enters the ready queue together. Calculate the
waiting time and Turn Around Time (TAT) for each process and the Average waiting time and Turn Around
Time (Assuming there is no I/O waiting for the processes) in priority based scheduling algorithm.
The scheduler sorts the ‘Ready’ queue based on the priority and schedules the process with the highest
priority (P1 with priority number 0) first and the next high priority process (P3 with priority number 2) as
second, and so on. The order in which the processes are scheduled for execution is represented as

P1 P3 P2

0 10 17 22
10 7 5

The waiting time for all the processes are given as

Waiting time for P1 = 0 ms (P1 starts executing first)
Waiting time for P3 = 10 ms (P3 starts executing after completing P1)
Waiting time for P2 = 17 ms (P2 starts executing after completing P1 and P3)
Average waiting time = (Waiting time for all processes) / No. of Processes
= (Waiting time for (P1+P3+P2)) / 3
= (0+10+17)/3 = 27/3
= 9 milliseconds
Turn Around Time (TAT) for P1 = 10 ms (Time spent in Ready Queue + Execution Time)
Turn Around Time (TAT) for P3 = 17 ms (-Do-)
Turn Around Time (TAT) for P2 = 22 ms (-Do-)
Average Turn Around Time = (Turn Around Time for all processes) / No. of Processes
418 Introduc on to Embedded Systems

= (Turn Around Time for (P1+P3+P2)) / 3

= (10+17+22)/3 = 49/3
= 16.33 milliseconds

Example 2
Calculate the waiting time and Turn Around Time (TAT) for each process and the Average waiting time and
Turn Around Time for the above example if a new process P4 with estimated completion time 6 ms and
priority 1 enters the ‘Ready’ queue after 5 ms of execution of P1. Assume all the processes contain only CPU
operation and no I/O operations are involved.
At the beginning, there are only three processes (P1, P2 and P3) available in the ‘Ready’ queue and the
scheduler picks up the process with the highest priority (In this example P1 with priority 0) for scheduling.
The execution sequence diagram for this is same as that of Example 1. Now process P4 with estimated
execution completion time 6 ms and priority 1 enters the ‘Ready’ queue after 5 ms of execution of P1. Since
the scheduling algorithm is non-preemptive and process P1 does not contain any I/O operations, P1 continues
its execution. After 10 ms of scheduling, P1 terminates and now the scheduler again sorts the ‘Ready’ queue
for process with highest priority. Since the priority for P4 (priority 1) is higher than that of P3 (priority 2),
which was supposed to be run after the completion of P1 as per the ‘Ready’ queue available at the beginning
of execution scheduling, P4 is picked up for executing. Due to the arrival of the process P4 with priority 1,
the ‘Ready’ queue is resorted in the order P1, P4, P3, P2. At the beginning it was P1, P3, P2. The execution
sequence now changes as per the following diagram

P1 P4 P3 P2

0 10 16 23 28
10 6 7 5
The waiting time for all the processes are given as
Waiting time for P1 = 0 ms (P1 starts executing first)
Waiting time for P4 = 5 ms (P4 starts executing after completing P1. But P4 arrived after 5 ms of execution of
P1. Hence its waiting time = Execution start time – Arrival Time = 10 – 5 = 5)
Waiting time for P3 = 16 ms (P3 starts executing after completing P1 and P4)
Waiting time for P2 = 23 ms (P2 starts executing after completing P1, P4 and P3)
Average waiting time = (Waiting time for all processes) / No. of Processes
= (Waiting time for (P1+P4+P3+P2)) / 4
= (0 + 5 + 16 + 23)/4 = 44/4
= 11 milliseconds
Turn Around Time (TAT) for P1 = 10 ms (Time spent in Ready Queue + Execution Time)
Turn Around Time (TAT) for P4 = 11 ms (Time spent in Ready Queue + Execution
Time = (Execution Start Time – Arrival Time) + Estimated
Execution Time = (10 – 5) + 6 = 5 + 6)
Turn Around Time (TAT) for P3 = 23 ms (Time spent in Ready Queue + Execution Time)
Turn Around Time (TAT) for P2 = 28 ms (Time spent in Ready Queue + Execution Time)
Average Turn Around Time = (Turn Around Time for all processes) / No. of Processes
= (Turn Around Time for (P2 + P4 + P3 + P1)) / 4
= (10 + 11 + 23 + 28)/4 = 72/4
= 18 milliseconds
 Real-Time Opera ng System (RTOS) based Embedded System Design 419

Similar to SJF scheduling algorithm, non-preemptive priority based algorithm also possess the drawback
of ‘Starvation’ where a process whose priority is low may not get a chance to execute if more and more
processes with higher priorities enter the ‘Ready’ queue before the process with lower priority started its
execution. ‘Starvation’ can be effectively tackled in priority based non-preemptive scheduling by dynamically
raising the priority of the low priority task/process which is under starvation (waiting in the ready queue for a
longer time for getting the CPU time). The technique of gradually raising the priority of processes which are
waiting in the ‘Ready’ queue as time progresses, for preventing ‘Starvation’, is known as ‘Aging’.

10.5.2 Preemptive Scheduling

Preemptive scheduling is employed in systems, which implements preemptive multitasking model. In
preemptive scheduling, every task in the ‘Ready’ queue gets a chance to execute. When and how often each
process gets a chance to execute (gets the CPU time) is dependent on the type of preemptive scheduling algorithm
used for scheduling the processes. In this kind of scheduling, the scheduler can preempt (stop temporarily)
the currently executing task/process and select another task from the ‘Ready’ queue for execution. When to
pre-empt a task and which task is to be picked up from the ‘Ready’ queue for execution after preempting the
current task is purely dependent on the scheduling algorithm. A task which is preempted by the scheduler
is moved to the ‘Ready’ queue. The act of moving a ‘Running’ process/task into the ‘Ready’ queue by the
scheduler, without the processes requesting for it is known as ‘Preemption’. Preemptive scheduling can be
implemented in different approaches. The two important approaches adopted in preemptive scheduling are
time-based preemption and priority-based preemption. The various types of preemptive scheduling adopted
in task/process scheduling are explained below.
[Link] Preemp ve SJF Scheduling/Shortest Remaining Time (SRT)
The non-preemptive SJF scheduling algorithm sorts the ‘Ready’ queue only after completing the execution of
the current process or when the process enters ‘Wait’ state, whereas the preemptive SJF scheduling algorithm
sorts the ‘Ready’ queue when a new process enters the ‘Ready’ queue and checks whether the execution
time of the new process is shorter than the remaining of the total estimated time for the currently executing
process. If the execution time of the new process is less, the currently executing process is preempted and
the new process is scheduled for execution. Thus preemptive SJF scheduling always compares the execution
completion time (It is same as the remaining time for the new process) of a new process entered the ‘Ready’
queue with the remaining time for completion of the currently executing process and schedules the process
with shortest remaining time for execution. Preemptive SJF scheduling is also known as Shortest Remaining
Time (SRT) scheduling.
Now let us solve Example 2 given under the Non-preemptive SJF scheduling for preemptive SJF
scheduling. The problem statement and solution is explained in the following example.

Example 1
Three processes with process IDs P1, P2, P3 with estimated completion time 10, 5, 7 milliseconds respectively
enters the ready queue together. A new process P4 with estimated completion time 2 ms enters the ‘Ready’
queue after 2 ms. Assume all the processes contain only CPU operation and no I/O operations are involved.
At the beginning, there are only three processes (P1, P2 and P3) available in the ‘Ready’ queue and
the SRT scheduler picks up the process with the shortest remaining time for execution completion (In this
example, P2 with remaining time 5 ms) for scheduling. The execution sequence diagram for this is same as
that of example 1 under non-preemptive SJF scheduling.
Now process P4 with estimated execution completion time 2 ms enters the ‘Ready’ queue after 2 ms of
420 Introduc on to Embedded Systems

start of execution of P2. Since the SRT algorithm is preemptive, the remaining time for completion of process
P2 is checked with the remaining time for completion of process P4. The remaining time for completion of
P2 is 3 ms which is greater than that of the remaining time for completion of the newly entered process P4
(2 ms). Hence P2 is preempted and P4 is scheduled for execution. P4 continues its execution to finish since
there is no new process entered in the ‘Ready’ queue during its execution. After 2 ms of scheduling P4
terminates and now the scheduler again sorts the ‘Ready’ queue based on the remaining time for completion
of the processes present in the ‘Ready’ queue. Since the remaining time for P2 (3 ms), which is preempted
by P4 is less than that of the remaining time for other processes in the ‘Ready’ queue, P2 is scheduled for
execution. Due to the arrival of the process P4 with execution time 2 ms, the ‘Ready’ queue is re-sorted in
the order P2, P4, P2, P3, P1. At the beginning it was P2, P3, P1. The execution sequence now changes as per
the following diagram

P2 P4 P2 P3 P1

0 2 4 7 14 24
2 2 3 7 10

The waiting time for all the processes are given as

Waiting time for P2 = 0 ms + (4 – 2) ms = 2 ms (P2 starts executing first and is interrupted by P4 and has to
wait till the completion of P4 to get the next CPU slot)
Waiting time for P4 = 0 ms (P4 starts executing by preempting P2 since the execution time for completion
of P4 (2 ms) is less than that of the Remaining time for execution completion of P2
(Here it is 3 ms))
Waiting time for P3 = 7 ms (P3 starts executing after completing P4 and P2)
Waiting time for P1 = 14 ms (P1 starts executing after completing P4, P2 and P3)
Average waiting time = (Waiting time for all the processes) / No. of Processes
= (Waiting time for (P4+P2+P3+P1)) / 4
= (0 + 2 + 7 + 14)/4 = 23/4
= 5.75 milliseconds
Turn Around Time (TAT) for P2 = 7 ms (Time spent in Ready Queue + Execution Time)
Turn Around Time (TAT) for P4 = 2 ms (Time spent in Ready Queue + Execution Time = (Execution Start
Time – Arrival Time) + Estimated Execution Time = (2 – 2) + 2)
Turn Around Time (TAT) for P3 = 14 ms (Time spent in Ready Queue + Execution Time)
Turn Around Time (TAT) for P1 = 24 ms (Time spent in Ready Queue + Execution Time)
Average Turn Around Time = (Turn Around Time for all the processes) / No. of Processes
= (Turn Around Time for (P2+P4+P3+P1)) / 4
= (7+2+14+24)/4 = 47/4
= 11.75 milliseconds
Now let’s compare the Average Waiting time and Average Turn Around Time with that of the Average
waiting time and Average Turn Around Time for non-preemptive SJF scheduling (Refer to Example 2 given
under the section Non-preemptive SJF scheduling)
Average Waiting Time in non-preemptive SJF scheduling = 6 ms
Average Waiting Time in preemptive SJF scheduling = 5.75 ms
Average Turn Around Time in non-preemptive SJF scheduling = 12 ms
Average Turn Around Time in preemptive SJF scheduling = 11.75 ms
 Real-Time Opera ng System (RTOS) based Embedded System Design 421

This reveals that the Average waiting Time and Turn Around Time (TAT) improves significantly with
preemptive SJF scheduling.
[Link] Round Robin (RR) Scheduling
The term Round Robin is very popular among the sports and games activities. You might have heard about
‘Round Robin’ league or ‘Knock out’ league associated with any football or cricket tournament. In the ‘Round
Robin’ league each team in a group gets an equal chance to play against the rest of the teams in the same
group whereas in the ‘Knock out’ league the losing team in a match moves out of the tournament ☺.
In the process scheduling context also, ‘Round Robin’ brings the same message “Equal chance to all”.
In Round Robin scheduling, each process in the ‘Ready’ queue is executed for a pre-defined time slot. The
execution starts with picking up the first process in the ‘Ready’ queue (see Fig. 10.13). It is executed for a
pre-defined time and when the pre-defined time elapses or the process completes (before the pre-defined time
slice), the next process in the ‘Ready’ queue is selected for execution. This is repeated for all the processes
in the ‘Ready’ queue. Once each process in the ‘Ready’ queue is executed for the pre-defined time period,
the scheduler comes back and picks the first process in the ‘Ready’ queue again for execution. The sequence
is repeated. This reveals that the Round Robin scheduling is similar to the FCFS scheduling and the only
difference is that a time slice based preemption is added to switch the execution between the processes in
the ‘Ready’ queue. The ‘Ready’ queue can be considered as a circular queue in which the scheduler picks
up the first process for execution and moves to the next till the end of the queue and then comes back to the
beginning of the queue to pick up the first process.

Process 1

Execution Switch Execution Switch

Process 4 Process 2

Execution Switch
Execution Switch

Process 3

Fig. 10.13 Round Robin Scheduling

The time slice is provided by the timer tick feature of the time management unit of the OS kernel (Refer the
Time management section under the subtopic ‘The Real-Time kernel’ for more details on Timer tick). Time
slice is kernel dependent and it varies in the order of a few microseconds to milliseconds. Certain OS kernels
may allow the time slice as user configurable. Round Robin scheduling ensures that every process gets a fixed
amount of CPU time for execution. When the process gets its fixed time for execution is determined by the
422 Introduc on to Embedded Systems

FCFS policy (That is, a process entering the Ready queue first gets its fixed execution time first and so on…).
If a process terminates before the elapse of the time slice, the process releases the CPU voluntarily and the
next process in the queue is scheduled for execution by the scheduler. The implementation of RR scheduling
is kernel dependent. The following code snippet illustrates the RR scheduling implementation for RTX51
Tiny OS, an 8bit OS for 8051 microcontroller from Keil Software ([Link]), an ARM® Company.
#include <rtx51tny.h> /* Definitions for RTX51 Tiny */
int counter0;
int counter1;

job0 () _task_ 0 {
os_create_task (1); /* Mark task 1 as “ready” */

while (1) { /* Endless loop */

counter0++; /* Increment counter 0 */
}
}
job1 () _task_ 1 {
while (1) { /* Endless loop */
counter1++; /* Increment counter 1 */
}
}
RTX51 defines the tasks as simple C functions with void return type and void argument list. The attribute
_task_ is used for declaring a function as task. The general form of declaring a task is
void func (void) _task_ task_id
where func is the name of the task and task_id is the ID of the task. RTX51 supports up to 16 tasks and so
task_id varies from 0 to 15. All tasks should be implemented as endless loops.
The two tasks in this program are counter loops. RTX51 Tiny starts executing task 0 which is the function
named job0. This function creates another task called job1. After job0 executes for its time slice, RTX51
Tiny switches to job1. After job1 executes for its time slice, RTX51 Tiny switches back to job0. This process
is repeated forever.
Now let’s check how the RTX51 Tiny RR Scheduling can be implemented in an embedded device (A
smart card reader) which addresses the following requirements.
∑ Check the presence of a card
∑ Process the data received from the card
∑ Update the Display
∑ Check the serial port for command/data
∑ Process the data received from serial port
These four requirements can be considered as four tasks. Implement them as four RTX51 tasks as explained
below.
void check_card_task (void) _task_ 1
{
/* This task checks for the presence of a card */
/* Implement the necessary functionality here */
}
 Real-Time Opera ng System (RTOS) based Embedded System Design 423

void process_card_task (void) _task_ 2

{
/* This task processes the data received from the card */
/* Implement the necessary functionality here */
}
void check_serial_io_task (void) _task_ 3
{
/* This task checks for serial I/O */
/* Implement the necessary functionality here */
}
void process_serial_data_task (void) _task_ 4
{
/* This task processes the data received from the serial port */
/* Implement the necessary functionality here */
}
Now the tasks are created. Next step is scheduling the tasks. The following code snippet illustrates the
scheduling of tasks.
void startup_task (void) _task_ 0
{
os_create_task (1); /* Create check_card_task Task */
os_create_task (2); /* Create process_card_task Task */
os_create_task (3); /* Create serial_io_task Task */

os_create_task (4); /* Create serial_data_task Task */

os_delete_task (0); /* Delete the Startup Task */
}
The os_create_task (task_ID) RTX51 Tiny kernel call puts the task with task ID task_ID in the ‘Ready’
state. All the ready tasks begin their execution at the next available opportunity. RTX51 Tiny does not have
a main () function to begin the code execution; instead it starts with executing task 0. Task 0 is used for
creating other tasks. Once all the tasks are created, task 0 is stopped and removed from the task list with
the os_delete_task kernel call. The RR scheduler selects each task based on the time slice and continues the
execution. If we observe the tasks we can see that there is no point in executing the task process_card_task
(Task 2) without detecting a card and executing the task process_serial_data_task (Task 4) without receiving
some data in the serial port. In summary task 2 needs to be executed only when task 1 reports the presence
of a card and task 4 needs to be executed only when task 3 reports the arrival of data at serial port. So these
tasks (tasks 2 and 4) need to be put in the ‘Ready’ state only on satisfying these conditions. Till then these
tasks can be put in the ‘Wait’ state so that the RR scheduler will not pick them for scheduling and the RR
scheduling is effectively utilised among the other tasks. This can be achieved by implementing the wait and
notify mechanism in the related tasks. Task 2 can be coded in a way that it waits for the card present event
and task 1 signals the event ‘card detected’. In a similar fashion Task 4 can be coded in such a way that it
waits for the serial data received event and task 3 signals the reception of serial data on receiving serial data
from serial port. The following code snippet explains the same.
void check_card_task (void) _task_ 1
{
/* This task checks for the presence of a card */
424 Introduc on to Embedded Systems

/* Implement the necessary functionality here */

while (1)
{
//Function for checking the presence of card and card reading
//………………………………
if (card is present)
//Signal card detected to task 2
os_send_signal (2)
}
}

void process_card_task (void) _task_ 2

{
/* This task processes the data received from the card */
/* Implement the necessary functionality here */
while (1)
{
//Function for checking the signaling of card present event
os_wait1(K_SIG);
//Process card data
}
}

void check_serial_io_task (void) _task_ 3

{
/* This task checks for serial I/O */
/* Implement the necessary functionality here */
while (1)
{
//Function for checking the reception of serial data
//………………………………
if (data is received)
//Signal serial data reception to task 4
os_send_signal (4)
}
}

void process_serial_data_task (void) _task_ 4

{
/* This task processes the data received from the serial port */
/* Implement the necessary functionality here */
while (1)
{
//Function for checking the signaling of serial data received event
os_wait1(K_SIG);
//Process card data
}
}
 Real-Time Opera ng System (RTOS) based Embedded System Design 425

The os_send_signal (Task ID) kernel call sends a signal to task Task ID. If the specified task is already
waiting for a signal, this function call readies the task for execution but does not start it. The os_wait1
(event) kernel call halts the current task and waits for an event to occur. The event argument specifies the
event to wait for and may have only the value K_SIG which waits for a signal. RTX51 uses the Timer 0 of
8051 for time slice generation. The time slice can be configured by the user by changing the time slice related
parameters in the RTX51 Tiny OS configuration file CONF_TNY.A51 file which is located in the \Keil_v5\
C51\RtxTiny2\SourceCode\ folder. Configuration options in CONF_TNY.A51 allow users to:
∑ Specify the Timer Tick Interrupt Register Bank.
∑ Specify the Timer Tick Interval (in 8051 machine cycles).
∑ Specify user code to execute in the Timer Tick Interrupt.
∑ Specify the Round-Robin Timeout.
∑ Enable or disable Round-Robin Task Switching.
∑ Specify that your application includes long duration interrupts.
∑ Specify whether or not code banking is used.
∑ Define the top of the RTX51 Tiny stack.
∑ Specify the minimum stack space required.
∑ Specify code to execute in the event of a stack error.
∑ Define idle task operations.
The RTX51 kernel provides a set of task management functions for managing the tasks. At any point of
time each RTX51 task is exactly in any one of the following state.
Task State State Description
RUNNING The task that is currently running is in the RUNNING State. Only one task at a time may be
in this state. The os_running_task_id kernel call returns the task number (ID) of the currently
executing task.
READY Tasks which are ready to run are in the READY State. Once the Running task has completed
processing, RTX51 Tiny selects and starts the next Ready task. A task may be made ready im-
mediately (even if the task is waiting for a timeout or signal) by setting its ready flag using the
os_set_ready or isr_set_ready kernel functions.
WAITING Tasks which are waiting for an event are in the WAITING State. Once the event occurs, the task
is switched to the READY State. The os_wait function is used for placing a task in the WAITING
State.
DELETED Tasks which have not been started or tasks which have been deleted are in the DELETED State.
The os_delete_task routine places a task that has been started (with os_create_task) into the
DELETED State.
TIME-OUT Tasks which were interrupted by a Round-Robin Time-Out are in the TIME-OUT State. This state
is equivalent to the READY State for Round-Robin programs.

Refer the documentation available with RTX51 Tiny OS for more information on the various RTX51 task
management kernel functions and their usage.
RR scheduling with interrupts is a good choice for the design of comparatively less complex Real-Time
Embedded Systems. In this approach, the tasks which require less Real-Time attention can be scheduled with
Round Robin scheduling and the tasks which require Real-Time attention can be scheduled through Interrupt
Service Routines. RTX51 Tiny supports Interrupts with RR scheduling. For RTX51 the time slice for RR
scheduling is provided by the Timer interrupt and if the interrupt is of high priority than that of the timer
interrupt and if its service time (ISR) is longer than the timer tick interval, the RTX51 timer interrupt may
426 Introduc on to Embedded Systems

be interrupted by the ISR and it may be reentered by a subsequent RX51 Tiny timer interrupt. Hence proper
care must be taken to limit the ISR time within the timer tick interval or to protect the timer tick interrupt
code from reentrancy. Otherwise unexpected results may occur. The limitations of RR with interrupt generic
approach are the limited number of interrupts supported by embedded processors and the interrupt latency
happening due to the context switching overhead.
RR can also be used as technique for resolving the priority in scheduling among the tasks with same
level of priority. We will discuss about how RR scheduling can be used for resolving the priority among
equal tasks under the VxWorks kernel in a later chapter.

Example 1
Three processes with process IDs P1, P2, P3 with estimated completion time 6, 4, 2 milliseconds respectively,
enters the ready queue together in the order P1, P2, P3. Calculate the waiting time and Turn Around Time
(TAT) for each process and the Average waiting time and Turn Around Time (Assuming there is no I/O
waiting for the processes) in RR algorithm with Time slice = 2 ms.
The scheduler sorts the ‘Ready’ queue based on the FCFS policy and picks up the first process P1 from the
‘Ready’ queue and executes it for the time slice 2 ms. When the time slice is expired, P1 is preempted and P2
is scheduled for execution. The Time slice expires after 2ms of execution of P2. Now P2 is preempted and P3
is picked up for execution. P3 completes its execution within the time slice and the scheduler picks P1 again
for execution for the next time slice. This procedure is repeated till all the processes are serviced. The order
in which the processes are scheduled for execution is represented as

P1 P2 P3 P1 P2 P1

0 2 4 6 8 10 12
2 2 2 2 2 2

The waiting time for all the processes are given as

Waiting time for P1 = 0 + (6 – 2) + (10 – 8) = 0 + 4 + 2 = 6 ms
(P1 starts executing first and waits for two time slices to get execution back and again
1 time slice for getting CPU time)
Waiting time for P2 = (2 – 0) + (8 – 4) = 2 + 4 = 6 ms
(P2 starts executing after P1 executes for 1 time slice and waits for two time slices to
get the CPU time)
Waiting time for P3 = (4 – 0) = 4 ms
(P3 starts executing after completing the first time slices for P1 and P2 and completes
its execution in a single time slice)
Average waiting time = (Waiting time for all the processes) / No. of Processes
= (Waiting time for (P1 + P2 + P3)) / 3
= (6 + 6 + 4)/3 = 16/3
= 5.33 milliseconds
Turn Around Time (TAT) for P1 = 12 ms (Time spent in Ready Queue + Execution Time)
Turn Around Time (TAT) for P2 = 10 ms (-Do-)
Turn Around Time (TAT) for P3 = 6 ms (-Do-)
 Real-Time Opera ng System (RTOS) based Embedded System Design 427

Average Turn Around Time = (Turn Around Time for all the processes) / No. of Processes
= (Turn Around Time for (P1 + P2 + P3))/3
= (12 + 10 + 6)/3 = 28/3
= 9.33 milliseconds
Average Turn Around Time (TAT) is the sum of average waiting time and average execution time.
Average Execution time = (Execution time for all the process)/No. of processes
= (Execution time for (P1 + P2 + P3))/3
= (6 + 4 + 2)/3 = 12/3 = 4
Average Turn Around Time = Average Waiting time + Average Execution time
= 5.33 + 4
= 9.33 milliseconds
RR scheduling involves lot of overhead in maintaining the time slice information for every process which
is currently being executed.
[Link] Priority Based Scheduling
Priority based preemptive scheduling algorithm is same as that of the non-preemptive priority based
scheduling except for the switching of execution between tasks. In preemptive scheduling, any high priority
process entering the ‘Ready’ queue is immediately scheduled for execution whereas in the non-preemptive
scheduling any high priority process entering the ‘Ready’ queue is scheduled only after the currently executing
process completes its execution or only when it voluntarily relinquishes the CPU. The priority of a task/
process in preemptive scheduling is indicated in the same way as that of the mechanism adopted for non-
preemptive multitasking. Refer the non-preemptive priority based scheduling discussed in an earlier section
of this chapter for more details.

Example 1
Three processes with process IDs P1, P2, P3 with estimated completion time 10, 5, 7 milliseconds and
priorities 1, 3, 2 (0—highest priority, 3—lowest priority) respectively enters the ready queue together. A new
process P4 with estimated completion time 6 ms and priority 0 enters the ‘Ready’ queue after 5 ms of start of
execution of P1. Assume all the processes contain only CPU operation and no I/O operations are involved.
At the beginning, there are only three processes (P1, P2 and P3) available in the ‘Ready’ queue and the
scheduler picks up the process with the highest priority (In this example P1 with priority 1) for scheduling.
Now process P4 with estimated execution completion time 6 ms and priority 0 enters the ‘Ready’ queue
after 5 ms of start of execution of P1. Since the scheduling algorithm is preemptive, P1 is preempted by P4
and P4 runs to completion. After 6 ms of scheduling, P4 terminates and now the scheduler again sorts the
‘Ready’ queue for process with highest priority. Since the priority for P1 (priority 1), which is preempted
by P4 is higher than that of P3 (priority 2) and P2 ((priority 3), P1 is again picked up for execution by the
scheduler. Due to the arrival of the process P4 with priority 0, the ‘Ready’ queue is resorted in the order P1,
P4, P1, P3, P2. At the beginning it was P1, P3, P2. The execution sequence now changes as per the following
diagram

P1 P4 P1 P3 P2

0 5 11 16 23 28
5 6 5 7 5
428 Introduc on to Embedded Systems

The waiting time for all the processes are given as

Waiting time for P1 = 0 + (11 – 5) = 0 + 6 = 6 ms
(P1 starts executing first and gets preempted by P4 after 5 ms and again gets the CPU
time after completion of P4)
Waiting time for P4 = 0 ms
(P4 starts executing immediately on entering the ‘Ready’ queue, by preempting P1)
Waiting time for P3 = 16 ms (P3 starts executing after completing P1 and P4)
Waiting time for P2 = 23 ms (P2 starts executing after completing P1, P4 and P3)
Average waiting time = (Waiting time for all the processes) / No. of Processes
= (Waiting time for (P1+P4+P3+P2)) / 4
= (6 + 0 + 16 + 23)/4 = 45/4
= 11.25 milliseconds
Turn Around Time (TAT) for P1 = 16 ms (Time spent in Ready Queue + Execution Time)
Turn Around Time (TAT) for P4 = 6 ms
(Time spent in Ready Queue + Execution Time = (Execution Start Time – Arrival Time)
+ Estimated Execution Time = (5 – 5) + 6 = 0 + 6)
Turn Around Time (TAT) for P3 = 23 ms (Time spent in Ready Queue + Execution Time)
Turn Around Time (TAT) for P2 = 28 ms (Time spent in Ready Queue + Execution Time)
Average Turn Around Time = (Turn Around Time for all the processes) / No. of Processes
= (Turn Around Time for (P2 + P4 + P3 + P1)) / 4
= (16 + 6 + 23 + 28)/4 = 73/4
= 18.25 milliseconds
Priority based preemptive scheduling gives Real-Time attention to high priority tasks. Thus priority
based preemptive scheduling is adopted in systems which demands ‘Real-Time’ behaviour. Most of the
RTOSs make use of the preemptive priority based scheduling algorithm for process scheduling. Preemptive
priority based scheduling also possesses the same drawback of non-preemptive priority based scheduling–
‘Starvation’. This can be eliminated by the ‘Aging’ technique. Refer the section Non-preemptive priority
based scheduling for more details on ‘Starvation’ and ‘Aging’.

10.6 THREADS, PROCESSES AND SCHEDULING: LO 6 Explain the different

PUTTING THEM ALTOGETHER Inter Process Communication
(IPC) mechanisms used by
So far we discussed about threads, processes and process/thread tasks/process to communicate
scheduling. Now let us have a look at how these entities are addressed and co-operate each other in a
in a real world implementation. Let’s examine the following pieces multitasking environment
of code.
//******************************************************************
//Process 1
//******************************************************************
#include “stdafx.h”
#include <windows.h>
#include <stdio.h>
//******************************************************************
//Thread for executing Task
//******************************************************************
void Task(void) {
while (1)