Transcript Section B MCA 404-AOS

SYLLABUS
Section B
• Real Time and Embedded Operating Systems:
– Introduction,
– Hardware Elements,
– Structure
•
•
•
•
Interrupt Driven,
Nanokernel,
Microkernel
and
Monolithic kernel based models.
– Scheduling –
• Periodic,
• Aperiodic
• Sporadic Tasks,
and
– Introduction to Energy Aware CPU Scheduling.
1
ASSIGNMENT #1: 16 JAN 2014
1.
2.
3.
4.
5.
1.
2.
3.
4.
SECTION B
What are the characteristics of Real Time and Embedded systems?
Describe Hardware Elements used in RE systems.
Describe structure of Real Time and Embedded (RE) operating systems clearly specifying difference
between Interrupt Driven, Nanokernel, Microkernel and Monolithic kernel based models.
Differentiate between Periodic, Aperiodic and Sporadic Tasks. What algorithms are available for
their scheduling?
Describe Energy Aware CPU Scheduling.
SECTION A
What do you understand by Multi-Processor and Distributed (MPD) systems? Describe Architecture
of Operating Systems for such systems.
How is Resource sharing and Load Balancing achieved in MPD systems?
What are the Design and Development Challenges in MPD Operating Systems?
Write short notes on:
a. Inter-process Communication in a typical MPD OS
b. Availability of resources in MPD systems.
c. Fault Tolerance in MPD systems
d. Logical Clock
e. Mutual Exclusion
f. Distributed File System
2
ADVANCED OPERATING SYSTEMS
MCA 404
3
SYLLABUS
4
SYLLABUS
Section B
• Real Time and Embedded Operating Systems:
– Introduction,
– Hardware Elements,
– Structure
•
•
•
•
Interrupt Driven,
Nanokernel,
Microkernel
and
Monolithic kernel based models.
– Scheduling –
• Periodic,
• Aperiodic
• Sporadic Tasks,
and
– Introduction to Energy Aware CPU Scheduling.
5
SYLLABUS
Section C
• Cluster and Grid Computing:
– Introduction to Cluster Computing and MOSIX OS,
– Introduction to the Grid,
– Grid Architecture,
• Computing Platforms:
–
–
–
–
Operating Systems and Network Interfaces,
Grid Monitoring and Scheduling,
Performance Analysis,
Case Studies.
6
SYLLABUS
Section D
• Cloud Computing:
–
–
–
–
–
–
–
–
Introduction to Cloud,
Cloud Building Blocks,
Cloud as IaaS, PaaS and SaaS,
Hardware and software virtualization,
Virtualization of OS
Hypervisor KVM,
SAN and
NAS back-end concepts.
• Mobile Computing:
– Introduction,
– Design Principles,
– Structure, Platform and Features of Mobile Operating Systems (Android, IOS,
Windows Mobile OS).
7
SYLLABUS
References:
• Sibsankar Haldar, Alex A. Arvind, “Operattng Systems”, Pearson
Education Inc.
• Tanenbaum and Van Steen, “Distributed systems: Principles and
Paradigms”, Pearson, 2007.
• M. L. Liu, “Distributed Computing: Principles and Applications”,
Addison Wesley, Pearson
• Maozhen Li, Mark Baker, “The Grid – Core Technologies”, John
Wiley & Sons 2005
8
9
SECTION B
10
SECTION B
• Real Time and Embedded Operating Systems:
11
8051 MICROCONTROLLER
12
8051 MICROCONTROLLER
• PDIP - Plastic Dual-in-Line Package
• CERDIP - Ceramic Dual-in-Line Package
13
8051 SCHEMATIC DIAGRAM
14
8051 SCHEMATIC DIAGRAM
15
COMPARISON OF 8051 FAMILY MEMBERS
Features
•
•
•
•
•
•
RAM (bytes)
ROM
Timers
Serial port
I/O pins
Interrupt sources
8051
8052
8031
128
4K
2
1
32
6
256
8K
3
1
32
8
128
0K
2
1
32
6
16
PSEN (Pin 29).
(Not used for AT89S52)
*OE: Output Enable • Program Store Enable. This is an output pin.
In an 8031 based system, in which an
external ROM holds the program code, this
pin is connected to the OE* pin of ROM.
• PSEN is not activated when the device is
executing out of internal Program Memory.
ALE/PROG (Pin 30). (Not used for AT89S52)
• Address Latch Enable. When connecting an
8031 to external memory, Port 0 provides
both Address and Data. It is connected to G
Pin (Pin 11, Latch Enable) of 74LS373 chip (D Latch).
• Not used for ATMEL 89S52.
EA/VPP (Programming Voltage, Pin 31).
• EA: External Access .
• When EA is held high (+5V) the CPU executes
out of internal Program Memory.
• Holding EA low (0V) forces the CPU to
execute out of external memory. In the
80C31, EA must be externally wired low.
• In the EPROM devices, this pin also receives
the programming supply voltage (VPP)
during EPROM programming.
17
• For AT89S52, it will be connected to Vcc.
Alternate Function of Port 3 Pins
• P3.0 Receive Data for serial port
communication.
• P3.1 Transmit Data for serial port
communication.
• P3.2
• P3.3
Receive External Interrupt 0.
Receive External Interrupt 1.
• P3.4
• P3.5
Timer 0 Interrupt (Internal)
Timer 1 Interrupt (Internal)
• P3.6 WR (Bar) Signals of external memory
connected in case of 8031.
• P3.7 RD (Bar) Signals of external memory
connected in case of 8031.
• 8051 Interrupts (Five).
– 2 external interrupts,
– 2 timer interrupts, and
– 1 serial interrupt.
18
SPECIAL FUNCTION REGISTERS OF 8051
•
•
•
•
•
•
•
•
•
•
•
•
•
•
SP: Stack Pointer;
DPL: Data Pointer Lower Byte; DPH: Data Pointer Higher Byte;
TCON: Timer Control; TMOD: Timer Mode;
TL0: Timer 0, Low Byte; TH0: Timer 0, Higher Byte
TL1: Timer 1, Low Byte; TH1: Timer 1, Higher Byte
SCON: Serial Communication; SBUF: Serial Buffer;
IE: Interrupt Enable
IP: Instruction Pointer
PSW: Program Status Word
ACC: Accumulator
B: Used by
MUL AB
and
DIV AB
P0: Port 0 internal buffer
P1: Port 1 internal buffer
P2: Port 2 internal buffer
P3: Port 3 internal buffer
19
EXAMPLE: ER
Real Time and Embedded Operating System (RTES or ER)
1. Writing Real Time and Embedded Operating System for 8051
Microcontroller.
a.
Write a simple operating system for 8051 microcontroller which is required
to monitor and control water level in a tank. If the water level falls below a
critical level, it should start the water pump automatically. If the level rises
above the top level, it should stop the motor.
b. Guidelines.
i.
ii.
iii.
iv.
v.
There would be two sensors. One for sensing lowest level and the other for
sensing highest level.
The sensors would be connected to two pins of a port. These pins/port would be
configured as input port.
These sensor pins would be checked in a loop for their status.
When the water level falls below the lowest level, another port pin, configured
as output pin, would be set to 1 (Say P2.1). This pin would be connected to an
electric relay. If both the sensors are off, give instruction SetB P2.1. which would
start the water pump.
When the water level increases above upper level, the pump is stopped by
20
another instruction: Clr P2.1
EXAMPLE: ER
Real Time and Embedded Operating System (RTES or ER)
1. Writing Real Time and Embedded Operating System for 8051
Microcontroller…
21
EXAMPLE: ER
Real Time and Embedded Operating System (RTES or ER)
1. Writing Real Time and Embedded Operating System for 8051
Microcontroller…
ORG 00
; Configure P1.1 and P1.2 as input pins
SetB
P1.1
SetB
P1.2
; Now they have high voltage. When water crosses these levels,
; the Sensors should send low voltage (0V) on these pins.
; Configure P2.1 as output pin
Clr
P2.1
; Relay should be wired such that
; it also stops the motor
Mainloop:
; Check Low level
CheckLowLevel:
22
EXAMPLE: ER
Real Time and Embedded Operating System (RTES or ER)
1. Writing Real Time and Embedded Operating System for 8051
Microcontroller…
Mainloop:
; Check Low level
CheckLowLevel:
JNB
P1.1,
CheckHighLevel ; P1.1 = 0, Water is above empty level
SetB
P2.1
; Tank is Empty , Start Water Pump
SJMP Checkgain
; Bypass High level checks.
; Let the pump keep running.
CheckHighLevel:
; If water is above low level, check upper level
JB
P1.2, Checkgain ; Water is below Top level
Clr
P2.1
; Tank is Full, Stop Water Pump
Checkagain:
SJmp Mainloop
END
23
Condition
High Level Sensor Low Level Sensor
Pin
Pin
Motor Relay Pin
Motor Status
Initialisation outside
Mainloop: Assume
initially Tank is Empty
Set it to High (1) : Set it to High (1):
Inactive
Inactive
Set it to Low (0)
Initially Stop
Motor
2
Enter Mainloop
Sensor indicates
below top level
Sensor indicates
below low level
Becomes High (1)
Motor Starts
3
Now Motor is Running High (1) : Inactive High (1): Inactive
Remains High (1)
Motor keeps
running
4
After sometime Low
level sensor gets
activated
Motor keeps
running
5
Water crosses Top
Level
Remains High (1): Becomes Low (0): Remains High (1)
Inactive
Active; Water
rises above Lower
level
Becomes Low (0): Remains Low (0): Becomes Low (0)
Active
Active
6
Water level falls with
Becomes High
usage. Falls below high (1): Inactive
level
7
Water Falls further
and goes below low
level
1.
Remains Low (0):
Active
Remains Low (0)
Remains High (1): Becomes High (1): Becomes High (1)
Inactive
Inactive
Motor Stops
Motor Remains
Off
Motor Starts
24
EXAMPLE: ER
Real Time and Embedded Operating System (RTES or ER)
2. Write an interrupt driven operating system to monitor and control
water level in a tank. Water level sensors would be wired on
external interrupt pins (P3.2 and P3.3).
25
EXAMPLE: ER
Real Time and Embedded Operating System (RTES or ER)
2. Write an interrupt driven operating system to monitor and control
water level in a tank. Water level sensors would be wired on
external interrupt pins (P3.2 and P3.3). Use low level sensor on
P3.2 (INT0) and High Level Sensor at Pin P3.3 (INT1). Configure
your OS for interrupt handling and write ISRs for the same.
26
VECTOR ADDRESS OF INTERRUPTS IN 8051
Interrupt Source
Vector address
Interrupt priority
• External Interrupt 0 –INT0
0003H
1
• Timer 0 Interrupt
000BH
2
• External Interrupt 1 –INT1
0013H
3
• Timer 1 Interrupt
001BH
4
• Serial Interrupt
0023H
5
27
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
• Steps in executing interrupts in the case of 8051 Series of
Microcontrollers:1.
2.
3.
4.
5.
6.
7.
Upon activation of an interrupt , the microcontroller finishes the instruction
it is executing and saves the address of the next instruction (Program
Counter (PC)) on the stack.
It also saves the current status of all the interrupts internally (ie not on the
stack).
It jumps to a fixed location in memory in accordance with the Interrupt
Vector Table.
If the ISR is only one or two instructions, these may be written there itself.
Generally, the ISR has many instructions. In such cases, a jump instruction is
placed at interrupt vector address.
The last instruction in the ISR is RETI (Return from Interrupt).
Upon executing RETI instruction, the microcontroller returns to the place
where it was interrupted. First it gets the Program Counter address from the
stack by popping the top two bytes of the stack into the PC. Then it starts to
execute from that address.
28
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
• Interrupts in 8051.
1.
2.
3.
4.
There are Six interrupts in 8051.
Reset. When the reset pin is activated, the 8051 jumps to address
location 0000. This is the power-up reset. Program execution starts from
address 0000.
Timer Interrupts (Two).
Two interrupts are set aside for the
timers, one for Timer 0 and the other for Timer 1. Memory locations 000BH
and 001BH in the interrupt vector table belong to Timer 0 and Timer 1
respectively.
External Hardware Interrupts (Two).
Pin No 12 (P3.2) and 13 (P3.3) in
Port 3 are for the external hardware interrupts. INT0 and INT1, respectively.
These external interrupts are also referred to as EX1 and EX2. Memory
locations 0003H and 0013H in the interrupt vector table are assigned to
INT0 and INT1 , respectively
Serial Communication Interrupt.
Serial communication has a
single interrupt that belongs to both receive and transfer. The interrupt
vector table location 0023H belongs to this interrupt.
29
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
•
•
•
•
•
•
RESET
INT 0:
Timer 0:
INT 1:
Timer 1:
Serial COM:
0000H
0003H
000BH
0013H
001BH
0023H
to
to
to
to
to
to
0002H
000AH
0012H
001AH
0022H
002AH
=
=
=
=
=
=
3 Bytes
8 Bytes
8 Bytes
8 Bytes
8 Bytes
8 Bytes
30
INTERRUPT HANDLING IN 8051
ORG
LJMP
0000H
MainLoop
; Long JMP is a three byte instruction with 16 Bit address
; ISR for Timer 0 to generate square wave
ORG
000BH ; This ISR is very small, It is written within 8 Bytes
RepeatThis:
CPL
P2.1
SJMP
RepeatThis
RETI
; Use RETI to return from ISR
; ISR for External Hardware Interrupt INT 1
ORG
0013H
LJMP
StartAlarm ; If the ISR is longer than 8 Bytes, jump to subroutine
RETI
ORG
0030H ; After vector table space
MainLoop:
; Keep waiting for interrupts in this loop
SJMP MainLoop ; Short JMP is a two byte instruction with Relative Address
StartAlarm:
SetB
…
RETI
END
P1.0
…
; Alarm circuit connected to P1.0
; Write more instructions here
; Use RETI to return from ISR
31
INSTRUCTION SET
32
INSTRUCTION SET
33
INSTRUCTION SET
34
INSTRUCTION SET
35
INSTRUCTION SET
36
EXTERNAL INTERRUPTS HANDLING IN 8051
• Let us understand the concept of interrupts, how interrupts work,
vector address, interrupt priority and how to write an ISR (interrupt
service routine).
• “Interruption” in English language means a deviation from the
normal routine.
• We know the processor is always busy executing some kind of
instructions.
• What if there occurs an urgent condition that we need to pause the
processor from its current activities for some time and make it
execute/do something else?
• Also we need to resume the processor back to its operations after
executing our “urgent condition”.
• To meet such a demand, 8051 micro controller has got a system
called “Interrupts”.
37
EXTERNAL INTERRUPTS HANDLING IN 8051
• An interrupt is usually a signal from the external world or a
command from the internal program (called software interrupt),
which forces the processor to pause its current activities and then
jump to another location to execute another set of predefined
activities.
• While doing so the processor will save its currents status and
location to a temporary storage area (to resume the current activities
after finishing the interrupt).
• The process of jumping to another location, after receiving the
interrupt signal is known as “servicing the interrupt”.
38
EXTERNAL INTERRUPTS HANDLING IN 8051
Interrupt sources
• In an 8051 micro controller there are
– 2 external interrupts,
– 2 timer interrupts, and
– 1 serial interrupt.
• External interrupts are – external interrupt 0(INT0) and external interrupt 1
(INT1).
• Timer interrupts are Timer 0 interrupt and Timer 1 interrupt.
• A serial interrupt is given for serial communication with the micro controller
(transmit and receive) .
• All these four interrupts, when evoked serve or execute a particular set of
predefined activities known as “Interrupt Service Routines”.
• It’s way of functioning is similar to the “subroutines” we write while developing a
complete program.
• In the case of 8051, the interrupt service routines(ISR) of each interrupt must
begin from a corresponding address in the program memory.
• This address from which an ISR begins is called the vector address of the
39
interrupt.
EXTERNAL INTERRUPTS HANDLING IN 8051
Interrupt Source
Vector address
Interrupt priority
• External Interrupt 0 –INT0
0003H
1
• Timer 0 Interrupt
000BH
2
• External Interrupt 1 –INT1
0013H
3
• Timer 1 Interrupt
001BH
4
• Serial Interrupt
0023H
5
40
EXTERNAL INTERRUPTS HANDLING IN 8051
Interrupt Priority
• All the 5 interrupts of 8051 have got different priorities.
• Interrupts are serviced according to it’s priority order.
• From the table above, you can see that INT0 has the highest priority
of 1 and Timer 0 comes next with priority value 2.
• The order of priority works like this – consider a case where two
interrupts are raised at the same time – one from INT0 and another
from Timer 1 interrupt. Now which one would be served first?
• In such a case, processor would serve the interrupt according to it’s
priority.
• In our case INT0 is of high priority (priority order 1)and Timer 1
interrupt is of low priority (priority order 4). So processor will
execute ISR of INTO first and then later, after finishing ISR of INT0,
processor will begin executing ISR of Timer 1 interrupt.
41
EXTERNAL INTERRUPTS HANDLING IN 8051
Interrupt Priority…
• From the figure above, you may note that INTO is an alternate
function P3.2 and INT1 is an alternate function of P3.3.
• A signal received at these pins will evoke the interrupts accordingly.
But not all signals will evoke the interrupt!
• The signal received at pins should be either a low level one or it
should be a falling edge signal to evoke the corresponding interrupt.
• However, to serve the interrupt upon receiving the signal at pins,
the man who programs 8051 should preprocess a few bits of three
SFRs namely TCON, IE and IP.
• Let’s examine them.
42
8051 TIMER CONTROL (TCON) SPECIAL FUNCTION REGISTER
43
http://www.circuitstoday.com/external-interrupts-handling-in-8051
8051 TIMER CONTROL (TCON) SPECIAL FUNCTION REGISTER
1. TCON is a bit addressable SFR.
2. Out of the 8 bits, only the lower 4 bits are concerned with external
interrupts.
3. The upper 4 bits deals with interrupts from Timers.
4. The lower four bits are TCON.0 (IT0), TCON.1 (IE0), TCON.2 (IT1)
and TCON.3 (IE1).
5. You can refer the figure given above for a better understanding.
6. Out of these 4 bits, bits 0 and 1 – that means – TCON.0 and TCON.1
are concerned with external interrupt 0 (INT0), where as bits 2 and
3 – TCON.2 and TCON.3 are concerned with external interrupt 1
(INT1).
7. Out of these bits only TCON.0 and TCON.2 are directly manipulated
by the programmer while dealing with an external interrupt.
8. Bits TCON.1 (IE0) and TCON.3 (IE1) are manipulated by the
44
processor itself.
8051 TIMER CONTROL (TCON) SPECIAL FUNCTION REGISTER
9. Bits TCON.1 (IE0) and TCON.3 (IE1) are manipulated by the processor
itself.
10. An external signal received at INTO would set the bit TCON.1 (also known
as IE0) and will be cleared by the processor itself, after it branches to the
corresponding ISR located at 0003H.
11. Similarly TCON.3 is set when an interrupt signal is received at INT1 and
would be cleared by processor after branching.
12. The other 2 bits TCON.0 and TCON.2 are used for selecting “type of
signal” received.
13. TCON.0 (or IT0) is set to 0 – if the interrupt at INT0 is to be evoked by a
low level signal.
14. If TCON.0 is set to high, then the interrupt at INT0 would be evoked by a
falling edge signal (high to low transition).
15. Same is the case with TCON.1 – if set to 0 then low level signal would
raise an interrupt at INT1 and if set to high, then a falling edge signal
would do the job.
45
8051 TIMER CONTROL (TCON) SPECIAL FUNCTION REGISTER
Bit Symbol
TCON Bit Function (Bit addressable as TCON.0 to TCON.7 , Direct Byte Address is 88h.)
7
TF1 Timer 1 Overflow flag. Set when timer rolls from all 1's to 0. Cleared when processor
vectors to execute interrupt service routine located at program address 001Bh.
6
5
4
TR1 Timer 1 run control bit. Set to 1 by program to enable timer to count; cleared to 0 by
program to halt timer.
TF0 Timer 0 Overflow flag. Set when timer rolls from all 1's to 0. Cleared when processor
vectors to execute interrupt service routine located at program address 000Bh.
3
TR0 Timer 0 run control bit. Set to 1 by program to enable timer to count; cleared to 0 by
program to halt timer.
IE1 External interrupt 1 Edge flag. Set to 1 when a high-to-low edge signal is received on port
3.3 (INT1). Cleared when processor vectors to interrupt service routine at program address
0013h. Not related to timer operations.
2
IT1
External interrupt 1 signal type control bit. Set to 1 by program to enable external interrupt
1 to be triggered by a falling edge signal. Set to 0 by program to enable a low-level signal on
external interrupt 1 to generate an interrupt.
1
IE0
External interrupt 0 Edge flag. Set to 1 when a high-to-low edge signal is received on port
3.2 (INT0). Cleared when processor vectors to interrupt service routine at program address
0003h. Not related to timer operations.
0
IT0
External interrupt 0 signal type control bit. Set to 1 by program to enable external interrupt
1 to be triggered by a falling edge signal. Set to 0 by program to enable a low-level signal on
external interrupt 0 to generate an interrupt.
46
47
http://www.circuitstoday.com/external-interrupts-handling-in-8051
8051 ITERRUPT ENABLE (IE) SPECIAL FUNCTION REGISTER
• There are 3 bits associated with external interrupts in IE – they are bits 0,
2 and 7.
• The main purpose of this SFR is to enable/disable different interrupts
based on whether it’s corresponding bits are set or not. Refer the figure
above.
• IE.7 – is known as global interrupt bit – which when set to ’0′ – disables all
kinds of interrupts in 8051.
• Only if this bit is set to ’1″, any kind of interrupt would be enabled in
8051.
• If this bit is set to 1, programmer can then individually enable or disable
all other interrupts INT0, INT1, Timer interrupts (0 and 1) and serial
interrupt.
• IE.0 – If set to ’1′ – it enables INT0 and if set to ’0′ – INT0 would be
disabled. So in order to enable external interrupt 0 (INT0) – IE.7 and IE.0
should be set to ’1′.
• IE.2 – Similar to IE.0 – IE.1 enables/disables external interrupt 1 (INT1).
48
8051 ITERRUPT ENABLE (IE) SPECIAL FUNCTION REGISTER
• There are 3 bits associated with external interrupts in IE – they are bits 0,
2 and 7.
• The main purpose of this SFR is to enable/disable different interrupts
based on whether it’s corresponding bits are set or not. Refer the figure
above.
• IE.7 – is known as global interrupt bit – which when set to ’0′ – disables all
kinds of interrupts in 8051.
• Only if this bit is set to ’1″, any kind of interrupt would be enabled in
8051.
• If this bit is set to 1, programmer can then individually enable or disable
all other interrupts INT0, INT1, Timer interrupts (0 and 1) and serial
interrupt.
• IE.0 – If set to ’1′ – it enables INT0 and if set to ’0′ – INT0 would be
disabled. So in order to enable external interrupt 0 (INT0) – IE.7 and IE.0
should be set to ’1′.
• IE.2 – Similar to IE.0 – IE.1 enables/disables external interrupt 1 (INT1).
49
8051 ITERRUPT PRIORITY (IP) SPECIAL FUNCTION REGISTER
50
8051 ITERRUPT PRIORITY (IP) SPECIAL FUNCTION REGISTER
• Basic function of this SFR is to set interrupt priority (IP).
• By default INT0 is of priority value 1 (which is the highest) and INT1
is of priority value 3 (which is lower than INT0).
• The programmer can alter this priority, if he wants!
• If IP.0 is set to ’0′ and then IP.2 is set to ’0′ – then the priority order
changes. INT1 will change to high priority and INT0 will change to
lower priority compared to INT1.
51
HOW TO WRITE AN ISR (INTERRUPT SERVICE ROUTINE)
• An ISR is just like any other subroutine we write inside a program, except for
the difference that an ISR must always end with a RETI instruction and not
with a RET instruction (as in the case of subroutines).
• An ISR when evoked, executes a certain lines of code that does some kind of
operations.
• It can be anything as defined by the programmer.
• The only condition is that the first line of ISR must begin from the
corresponding vector address. Vector address of INT0 is 0003H and that of
INT1 is 0013H.
• Note: In some cases the ISR will be too long that it wont be practical to write
all codes staring from 0003H or the other vector address.
• In such cases, ISR can be placed at any other location in program memory and
programmer must provide an unconditional jump to the starting address of
ISR from the corresponding vector address.
• Example:- The ISR of INT0 has been written from location 2000H. Now
programmer must place an instruction – ‘LJMP 2000H’ at the vector address
52
of INT0 – 0003H.
HOW TO WRITE AN ISR (INTERRUPT SERVICE ROUTINE)
Note:• Whenever an evoked interrupt is acknowledged and the processor
branches to its corresponding vector address, it automatically
disables the interrupt in IE register. This disabled interrupt would
only be re-enabled upon executing the RETI instruction placed
inside the ISR.
• That is the single reason, a programmer must use RETI inside an ISR
instead of RET instruction.
• Placing RET will also do the job of returning from interrupt routine
to main program (the calling program) but the RET instruction will
not re-enable the disabled interrupt in IE register.
• So if an RET is used, the interrupt would be permanently disabled
after its first serving of ISR (unless it is enabled again by the programmer at
some other part of the same program).
53
HOW TO WRITE AN ISR (INTERRUPT SERVICE ROUTINE)
• So in order to write an ISR for INT0, you have to keep in mind the
following things:1) Place the ISR for INT0 beginning from its vector address –
0003H. If the ISR is too long, place an unconditional jump from
0003H to the starting address of ISR (which is placed at some
other location of program memory). The ISR must end with a
RETI instruction.
2) Select the triggering signal type of interrupt by setting/clearing
TCON.0 bit. TCON.0=1 – means interrupt would be triggered by
a falling edge signal. TCON.0 =0 – means interrupt would be
triggered by a low level signal.
3) Set IE.0 =1 to enable the external interrupt 0 (INT0)
4) Set IE.7=1 to enable the global interrupt control bit.
5) Optionally, programmer can alter the priority of INT0 by
54
setting/clearing IP.0 (Note: This step is optional.)
HOW TO WRITE AN ISR (INTERRUPT SERVICE ROUTINE)
• Now when it comes to external interrupt 1 – INT1 – the processes
are all same, except for the change in bits that are to be
programmed.
1) Place the ISR in vector address of INT1 – 0013H. Or if the ISR is
long, place an LJMP at 0013H to the corresponding starting
address of ISR for INT1.
2) Triggering signal type is selected by setting/clearing TCON.2.
TCON.2 = 0 – triggered by low level signal. TCON.2 = 1 –
triggered by falling edge signal.
3) Set IE.2 = 1 to enable INT1
4) Set IE.7 =1 to enable global interrupt control bit.
5) Interrupt priority can be altered by changing value of IP.2
(optional). Refer the diagram of IP register given above.
55
56
HOW TO WRITE AN ISR (INTERRUPT SERVICE ROUTINE)
How to generate Software Interrupts in 8051?
• Software interrupts are nothing but an interrupt generated by a
program inside the controller.
• To generate an external interrupt, we need a signal input either at
INT0 or INT1 pin of the 8051 micro controller.
• We have seen that, when an interrupt signal is received at the INT0
pin, the TCON.1 bit would automatically get set and that is how the
processor knows an interrupt signal has been received at INT0 pin.
• When TCON.1 is set, processor would immediately acknowledge the
interrupt and branch to the corresponding ISR of INT0.
• While branching to the ISR, processor would also clear the TCON.1
bit. The same happens in the case of INT1 and the associated bit is
TCON.3.
57
HOW TO WRITE AN ISR (INTERRUPT SERVICE ROUTINE)
How to generate Software Interrupts in 8051?
• Now in order to generate a software interrupt, the programmer can
manipulate these bits TCON.1 and TCON.3 manually inside a
program.
• An instruction like ‘SETB TCON.1′ will activate the interrupt for INT0
(without any external signal at the INT0 pin) inside the controller.
• Now the processor will acknowledge the interrupt and branch to
the corresponding location of ISR for INT0 (vector address 0003H).
• After branching to ISR, the processor would clear the bit TCON.1.
• An instruction like ‘SETB TCON.3’ would activate the interrupt for
INT1 and processor would branch to ISR of INT1 located at vector
address 0013H.
• While branching it would automatically clear the bit TCON.3, so that
the programmer can activate the interrupt again inside a loop or
58
some other part of the program.
HOW TO WRITE AN ISR (INTERRUPT SERVICE ROUTINE)
ORG 00
END
59
HOW TO WRITE AN ISR (INTERRUPT SERVICE ROUTINE)
ORG 00
Mainloop:
NOP
SJMP Mainloop
END
60
HOW TO WRITE AN ISR (INTERRUPT SERVICE ROUTINE)
ORG 00
; Vector Address for INT0
ORG
0003H
LJMP
ISR_for_INT0
; Vector Address for TIMER0
ORG
000BH
LJMP
ISR_for_TIMER0
; Vector Address for INT1
ORG
0013H
LJMP
ISR_for_INT1
; Vector Address for TIMER1
ORG
001BH
LJMP
ISR_for_TIMER1
; Vector Address for Serial Communication Interrupt
ORG
0023H
LJMP
ISR_for_SerialCom
Mainloop:
NOP
SJMP
END
Mainloop
61
HOW TO WRITE AN ISR (INTERRUPT SERVICE ROUTINE)
ORG 00
ORG
LJMP
0003H
ISR_for_INT0
; Vector Address for INT0
ORG
LJMP
000BH
ISR_for_TIMER0
; Vector Address for TIMER0
ORG
LJMP
0013H
ISR_for_INT1
; Vector Address for INT1
ORG
LJMP
001BH
ISR_for_TIMER1
ORG
LJMP
0023H
ISR_for_SerialCom
NOP
SJMP
Mainloop
; Vector Address for TIMER1
; Vector Address for Serial Communication Interrupt
Mainloop:
END
62
HOW TO WRITE AN ISR (INTERRUPT SERVICE ROUTINE)
ORG 00
LJmp SetupInterrupts
ORG
LJMP
0003H
ISR_for_INT0
; Vector Address for INT0
ORG
LJMP
000BH
ISR_for_TIMER0
; Vector Address for TIMER0
ORG
LJMP
0013H
ISR_for_INT1
; Vector Address for INT1
ORG
LJMP
001BH
ISR_for_TIMER1
; Vector Address for TIMER1
ORG
0023H
LJMP
ISR_for_SerialCom
; Vector Address for Serial Communication Interrupt
SetupInterrupts:
MOV IE,#10000101B ;Enable External INT0 and INT1
Mainloop:
NOP
SJMP
END
Mainloop
63
HOW TO WRITE AN ISR (INTERRUPT SERVICE ROUTINE)
ORG 00
LJmp SetupInterrupts
ORG
LJMP
0003H
ISR_for_INT0
; Vector Address for INT0
ORG
LJMP
ORG
LJMP
ORG
LJMP
ORG
LJMP
000BH
ISR_for_TIMER0
; Vector Address for TIMER0
0013H
ISR_for_INT1 ; Vector Address for INT1
001BH
; Vector Address for TIMER1
ISR_for_TIMER1
0023H
ISR_for_SerialCom
; Vector Address for Serial Communication Interrupt
SetupInterrupts:
MOV IE, #10000101B ;Enable External INT0 and INT1
Mainloop:
NOP
SJMP
Mainloop
ISR_for_INT0:
SetB
RETI
ISR_for_INT1:
SetB
RETI
END
P1.0
P1.2
64
HOW TO WRITE AN ISR (INTERRUPT SERVICE ROUTINE)
ORG 00
LJmp SetupInterrupts
;Interrupt Vector Table
;
Interrupt Memory Location
Priority
;
INT0
0003H
;
TIMER0
000BH
;
INT1
0013H
;
TIMER1
001BH
;
SERIAL COMMUNICATION INTERRUPT
;
(8 Bytes from 0003 to 000A h)
(8 Bytes from 000B to 0012 h)
(8 Bytes from 0013 to 001A h)
(8 Bytes from 001B to 0022 h)
0023H
(8 Bytes from 0023 to 002A)
1
2
3
4
5
; Vector Address for INT0
ORG
0003H
LJMP
ISR_for_INT0
; Vector Address for TIMER0
ORG
000BH
LJMP
ISR_for_TIMER0
; Vector Address for INT1
ORG
0013H
LJMP
ISR_for_INT1
65
HOW TO WRITE AN ISR (INTERRUPT SERVICE ROUTINE)
ORG 00
LJmp SetupInterrupts
;Interrupt Vector Table
;
Interrupt Memory Location
Priority
;
INT0
0003H
;
TIMER0
000BH
;
INT1
0013H
;
TIMER1
001BH
;
SERIAL COMMUNICATION INTERRUPT
;
(8 Bytes from 0003 to 000A h)
(8 Bytes from 000B to 0012 h)
(8 Bytes from 0013 to 001A h)
(8 Bytes from 001B to 0022 h)
0023H
(8 Bytes from 0023 to 002A)
1
2
3
4
5
; Vector Address for INT0
ORG
0003H
LJMP
ISR_for_INT0
; Vector Address for TIMER0
ORG
000BH
LJMP
ISR_for_TIMER0
; Vector Address for INT1
ORG
0013H
LJMP
ISR_for_INT1
66
HOW TO WRITE AN ISR (INTERRUPT SERVICE ROUTINE)
; Vector Address for TIMER1
ORG
001BH
LJMP
ISR_for_TIMER1
; Vector Address for Serial Communication Interrupt
ORG
0023H
LJMP
ISR_for_SerialCom
;Main Initilazation
ORG 30H
SetupInterrupts:
; preprocess a few bits 3 SFR’s namely TCON, IE and IP
; 1. TCON Register is to be configured for enabling type of signal.
;
Let it remain with default values.
; 2. IE Register: Configure Interrupt Enable Register.
; Set Bit 0 for Enabling External Interrupt 0 or Clear it to disable
; Set Bit 2 for Enabling External Interrupt 1 or Clear it to disable
; Set Bit 7 to enable interrupts. Interrupts would be serviced only if Bit 7 = 1
;MOV IE,#10000100B
MOV IE,#10000101B
;Enable External INT1
;Enable External INT0 and INT1
67
HOW TO WRITE AN ISR (INTERRUPT SERVICE ROUTINE)
; 3. IP Register: Special Function Register IP is to be configured
;
for changing priority of interrupts.
;
Let it have default values
Mainloop:
NOP
SJMP
Mainloop
ISR_for_INT0:
SetB
RETI
P1.0
SetB
RETI
P1.1
SetB
RETI
P1.2
SetB
RETI
P1.3
SetB
RETI
P1.4
ISR_for_TIMER0:
ISR_for_INT1:
ISR_for_TIMER1:
ISR_for_SerialCom:
END
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
INTERRUPT HANDLING IN 8051
•
We shall consider two projects using microcontroller 8051:1.
2.
Security Alarm System: Real Time System
Temperature Controller for an Air Conditioner: Embedded System.
91
REAL TIME AND EMBEDDED OPERATING SYSTEMS
Introduction
• Real-time systems are special systems where timeliness of
responses to user/external requests plays a very crucial role, apart
from their logical correctness.
• Traditionally, real-time systems often referred to large, highpowered, expensive systems such as
– air-traffic control systems,
– defence and space command and control systems,
– space exploration systems,
– industrial process control systems,
– industrial robots,
– telecommunication systems,
– medical equipments,
92
– electricity distribution and power plant control systems.
REAL TIME AND EMBEDDED OPERATING SYSTEMS
Introduction…
•
•
•
As the use of computer-controlled systems has pervaded (extended
through) our daily life, real-time systems are no longer limited to
these large systems.
Devices such as mobile phones, PDAs, TVs, DVD players, cameras,
cars, fax machines, printers, refrigerators, dishwashers, wireless
routers, and entertainment machines, operate mostly in real-time
modes and, therefore, they too fall into the category of real-time
systems.
These systems/devices have one- or more programmable
computing elements.
93
REAL TIME AND EMBEDDED OPERATING SYSTEMS
Introduction…
• A recent study indicates that more than ninety per cent of
microprocessors are embedded in consumer products and other
real-time systems.
• The vast majority of these microprocessors are embedded in
equipment, machines, and appliances found in homes, workplaces,
automobiles, and carried by or implanted in humans, birds, and
animals.
• >>For many practical systems, real-time requirement and
embeddedness are two necessary- and, often, related aspects.
• Therefore, in such a context, a real-time system or an embedded
system is essentially the same. The term real-time emphasizes the
importance of the “timing” aspect of the system and the term
embeddedness the computing element embedded in the system as
94
the key unit, and whose resources are often limited.
REAL TIME AND EMBEDDED OPERATING SYSTEMS
Introduction…
• >>Although now the term real-time implies “fast enough” or “timebound”, in the beginning it was used to refer to the speed that
matched the speed of the original system being simulated.
• Almost all real time systems have one or more “embedded
computing elements”.
• Here the term embedded means a computing element is inserted
instead of implanted as an integral part of the system.
• In some systems, the presence of the embedded computing
element is not apparent to end users.
• The systems where programmable computing elements are
embedded inside, are generally referred to as embedded systems.
95
REAL TIME AND EMBEDDED OPERATING SYSTEMS
Introduction…
• Also, since most embedded systems operate under some level of
real-time requirements they are also real-time systems.
• Therefore, we do not make technical distinctions between a realtime system and an embedded system.
• We use both terms interchangeably, whichever suits the context
best, and often refer to them as RE systems.
• In the domain of RE systems, the term “task” is used to refer to
what in traditional computing systems is termed a process.
• Essentially, the execution of a process carries out the intended task.
Therefore, we use task in place of process in this chapter (Chapter
15).
• In RE systems, tasks can be scheduled (arranged) for execution.
96
REAL TIME AND EMBEDDED OPERATING SYSTEMS
Introduction…
• Programmable computing elements with associated software inside
a larger system form the embedded computing system.
• Likewise, programmable computing elements with associated
software inside a larger real-time system form the real-time
computing system.
• In any case, these computing elements are expected to operate in a
specialized manner to satisfy specific requirements of the larger
systems in which they are embedded.
• Since our focus is on the computing aspect, hereafter, unless
mentioned otherwise, a real-time (embedded) system essentially
refers to a real-time (embedded) computing system.
97
REAL TIME AND EMBEDDED OPERATING SYSTEMS
Introduction…
• Depending upon the application and its requirements, a computing
element in an RE system could be a general-purpose microprocessor
or a special-purpose microcontroller.
• Consequently, an RE system can be simple enough to include a small
specialized microcontroller or require massive parallel processors
with huge memory and computing power.
• The question of what actually constitutes an RE system, purely from
computing point of view, is debatable.
• We must first understand, at least to some extent, what constitutes
an RE system in order to understand the operating-system-specific
requirements of such systems.
• In this chapter, we first take a brief look at the characteristics and hardware
organization of typical RE systems. Then, we briefly discuss some of the
operating system structures, important issues, and solutions to such issues. 98
REAL TIME AND EMBEDDED OPERATING SYSTEMS
The Characteristics of an RE System
• Although opinions about what constitute an RE system can vary, it is
widely accepted that RE systems have some or all of the following
important characteristics.
1. Application-specific.
– Each real-time system is intended for a specific application.
– As mentioned earlier, real-time systems such as consumer
electronics, medical devices, transport systems, military systems,
etc., are designed for specific applications.
– The software for these systems must be tailor-made to suit the
applications.
99
REAL TIME AND EMBEDDED OPERATING SYSTEMS
The Characteristics of an RE System…
2. Timeliness (Real-time constraint).
– Most embedded systems interact with the environment through their
interfacing hardware components and, therefore, the components must
operate in a “real-time” frame to react in timely fashion to the physical
processes taking place in the environment.
– The term real-time means a time-bound response. Performance degradation
and/or system failure will occur if responses are not delivered within the
specified time.
– The systems are often “reactive” to respond to incoming events and change
states at their speed.
– A program in a real-time system must be both logically and temporally (of
limited time, related to time) correct.
– The real-time constraint of a task is specified in terms of a deadline—an
absolute or a relative time by when the task must complete.
– That is, real-time systems demand a limit on the response time.
100
REAL TIME AND EMBEDDED OPERATING SYSTEMS
The Characteristics of an RE System…
3. Dynamic behaviour.
– Due to unpredictable interactions with the environment and
other systems, the components of real-time systems often carry
a high level of concurrent activities.
– Many components interact with each other and compete for
resources.
– Asynchronous (not occurring at predetermined or regular intervals)
events are notified to the processor through interrupts and,
thus, interrupts are important for all real-time systems.
– Systems which have an interrupt mechanism are inherently
concurrent and, therefore, their behaviour is usually highly
dynamic.
101
REAL TIME AND EMBEDDED OPERATING SYSTEMS
The Characteristics of an RE System…
4. Reliability and fault tolerance.
– As RE systems often operate in life-or mission-critical situations,
they are expected to be highly reliable and fault tolerant.
– A system is reliable if a small number of failures do not seriously
impair its satisfactory operation.
– The measure of reliability depends on how often a system will
fail and when it indeed fails, how difficult it is to make the
system operational again.
– Fault tolerance is recognizing and handling such failures
systematically. It is the ability of the system to respond
gracefully to an unexpected failure situation.
– A reliable and fault tolerant system can respond to faults at
many levels ranging from stopping gracefully to continuing to
102
operate in a reduced capacity.
REAL TIME AND EMBEDDED OPERATING SYSTEMS
The Characteristics of an RE System…
4. Reliability and fault tolerance…
– A related factor is criticality, which is a measure of the cost of failure. A
system is called safety critical if human lives or the intactness of the facilities
or equipment directly depend on its correct timely operation.
– Based on the severity of the cost, real-time systems are classified into two
categories: hard and soft.
– Hard real-time systems must satisfy their timing and deadline constraints.
Otherwise, the system will fail.
– On the other hand, soft real-time systems can accept missing some deadline
constraints as long as they achieve their mission.
– Most practical systems fall in between the two.
– To assure high fault tolerance, some real-time systems are equipped with
redundant components and, hence, require added coordination between
those components.
103
REAL TIME AND EMBEDDED OPERATING SYSTEMS
The Characteristics of an RE System…
• ≫ The following excerpt from literature nicely captures the
importance of fault tolerance in real-time systems.
• “If the software had an error rate of 0.1%, then this would lead to
500 exceptions in surgeries per week and 18 airplane crashes per
day”.
• ≫ A hard real-time system is a special purpose system which
guarantees completion of real-time tasks within their deadlines.
104
REAL TIME AND EMBEDDED OPERATING SYSTEMS
The Characteristics of an RE System…
5. Limited Testing.
– For many systems, it is usually impossible or expensive to test
and debug the system with their actual complete environments.
– These systems rely on
• careful system specifications,
• systematic and comprehensive analysis and design,
• extensive runtime procedures for fault detection and
handling,
• testing of sub-systems, and
• simulation.
105
REAL TIME AND EMBEDDED OPERATING SYSTEMS
The Characteristics of an RE System…
6. Flexible Networking.
– Most embedded devices are increasingly expected to work
together by way of forming “ad-hoc networks” when needed.
– Typical examples are
• next generation building and factory automation systems,
• automated highways,
• advanced air traffic control,
• unmanned military vehicles and the like.
– Networking makes the timing assurance more complex, because
the combination of tasks involved when networked is not known
at the time of design of an individual device.
106
REAL TIME AND EMBEDDED OPERATING SYSTEMS
The Characteristics of an RE System…
7. Autonomy.
– Some embedded devices are required to function without
maintenance for long durations.
– For example,
• building automation systems,
• military equipment,
• and sensor networks deployed in forests and oceans
are required to operate for several years without maintenance
and human supervision.
107
REAL TIME AND EMBEDDED OPERATING SYSTEMS
The Characteristics of an RE System…
8. Interfacing.
– Unlike traditional computer systems that have standard user
interfaces such as keyboard, mouse, etc., embedded systems
come with a range of interface devices—from no interface at all
to many highly customizable interfaces.
– Interface devices include sensors, actuators, motors, switches,
display panels, communication links, signal converters, and so
forth.
– Unlike traditional computer systems where the processor is the
major unit, most embedded systems are I/O dominated systems.
– In addition, most real-time systems have one or more humans to
interact with and who control them.
– Human-machine interfaces must be carefully designed to avoid
108
human errors.
REAL TIME AND EMBEDDED OPERATING SYSTEMS
The Characteristics of an RE System…
9. Limited Resources.
– Most small, embedded devices are designed under space-,
weight-, and energy constraints imposed by the applications.
– Consequently, recent research on embedded systems has heavily
focused on resource limitations.
– Hence, in some sense, embedded systems are characterized as
the systems with limited memory, computing, and battery
power.
– Systems with restrictions of size and power are also referred to
in literature as small computers.
109
REAL TIME AND EMBEDDED OPERATING SYSTEMS
The Characteristics of an RE System…
• >> An embedded computer system is one of the components of a
larger system. The larger system may include other components
such as mechanical-, chemical-, and electrical devices. Further, such
systems are designed for specific purposes, and they usually require
the knowledge of the specific application for which they are
designed and operated under certain real-time constraints.
110
REAL TIME AND EMBEDDED OPERATING SYSTEMS
The Characteristics of an RE System…
• Concisely,
– systems with emphasis on real-time constraints are generally
referred to as real-time systems, and systems embedded with
computing elements are generally referred to as embedded
systems.
– A computing system embedded in these larger host systems
derives its name from its host, that is, either as real-time
computing system or embedded, depending on how the host
system is referred.
– In almost all cases. these systems typically have real-time
constraints, resource limitations, and one or more other
properties listed above. Therefore, real—time system and
embedded system typically refer to the same, and as mentioned
111
previously we call them RE systems.
REAL TIME AND EMBEDDED OPERATING SYSTEMS
The Characteristics of an RE System…
• Processors in RE systems must react to requirements of other
components in a timely manner. Other components may work
either independently or interactively and, therefore, most of these
systems are highly concurrent.
• To interact with environment, these systems come with various
types of interfaces.
• Liveness, timeliness, and fault-tolerance are fundamental aspects of
these systems.
• One of the essential characteristics of these systems is that, in
addition to logical correctness, they have to produce the results on
time.
112
REAL TIME AND EMBEDDED OPERATING SYSTEMS
• With this introduction to characteristics of RE systems, we identify
some important challenges of these systems and discuss some
popular approaches to deal with them from the “operating
systems” point of view.
• To understand the requirements of operating systems specific for RE
systems, we first discuss their hardware aspects.
113
SECTION B
• Real Time and Embedded Operating Systems:
– Introduction,
– Hardware Elements,
114
HARDWARE ELEMENTS
• From the various characteristics described above, it is obvious that
special purpose hardware elements are preferred over generalpurpose hardware elements to construct RE systems.
• In this section, we briefly review some typical hardware elements
that are used to construct computing elements in RE systems.
• First, we discuss individual elements such as
–
–
–
–
–
processor,
memory,
I/O device,
communication device,
and
other elements separately, and then show how they can be put together to
construct complete RE systems.
115
HARDWARE ELEMENTS
116
HARDWARE ELEMENTS
1. Processing Elements.
• The microprocessor is the key element in modern RE systems.
Central processing units (CPUs) are the brains of any computing
system, and in the early era, were designed combining several
integrated chips.
• A microprocessor is a programmable digital electronic component
that incorporates the functions of a CPU on a single-chip.
• Its functionality is characterized by a set of instructions that it
executes.
• Microprocessors are very efficient means to implement digital
systems and are available in varying levels of sophistication.
• Their uses range from simple home appliances to the largest
mainframe computers.
• Most embedded systems use special purpose microprocessors.117
HARDWARE ELEMENTS
1. Processing Elements…
• Embedded systems are used for numerous applications involving
analogue signals.
• Typical tasks include
– processing various sensor values from the environment,
– instrumentation,
– speech processing,
– telecommunications,
– and system control.
118
HARDWARE ELEMENTS
1. Processing Elements…
• In the past, such tasks were performed using analogue techniques
and subsequently were moved to digital techniques, called digital
signal processing.
• Digital signal processing involves intensive arithmetic calculations.
• To achieve high speed processing, the basic computing engine,
called Digital Signal Processor (DSP), is built around a high-speed
multiplier/accumulator combination.
• >> The first microprocessor Intel 4004, debuted (debut: to start; to arrive; first
appearance) in 1971, was designed for a calculator, which is an embedded device.
• >> Programming DSPs is a tedious task generally done in a low level, assembly or
closer to it. Its instructions are optimized to perform fast- and efficient
arithmetic, particularly floating point operations. The majority of programming
effort goes into ensuring proper decimal points and overflow issues.
119
HARDWARE ELEMENTS
1. Processing Elements…
• Many components in a real-time system are required to maintain
predictable performance irrespective of changing conditions in the
system.
• For example, components such as pumps, belts, and shafts are
expected to maintain a preset speed irrespective of changes in the
load on the system.
• DSP delivers the rapid response and accurate results required for
highly responsive control systems.
• In summary, processing elements are either specialized
microprocessors called microcontrollers or general purpose
microprocessors.
120
HARDWARE ELEMENTS
2. Memory Elements.
• Many types of memory devices are now available for embedded
computer systems.
• They can be classified as read-only memory (ROM), random access
memory (RAM), and hybrid memories.
• ROM is non-volatile and, therefore, retains its content even when
the power is switched off. It is usually fast for reading, but to write
on it requires special techniques.
• On the other hand, RAM is volatile and, therefore, retains its
content only when the power is on.
• As technology improved, the boundary between ROMs and RAMs
blurred and many recent versions of memory have attractive
properties of both.
121
HARDWARE ELEMENTS
Memory Elements…
• These new types of memories are known as hybrid memories.
Hybrid memories can be accessed (that is, read/written) like RAMs,
and retain their content without power like ROMs.
• >> Recent advancements in memory have narrowed the gap
between ROM and RAM technologies and paved the way for hybrid
memories.
• These memories can be read and written like RAMs, and like ROMs,
maintain their content without electrical power.
• Some hybrids are evolved from RAMs and the others from ROMs.
122
HARDWARE ELEMENTS
2. Memory Elements…
• In most embedded systems, the program execution environment is
generally dynamic (data values change constantly and tasks are often created,
executed, and removed from the systems).
• Also, since most large program codes and data are brought
piecemeal based on the current requirement and placed wherever
memory is available, RAMs are convenient for storing such general
data and performing tasks at runtime.
• RAM requires electrical power to retain its content. Content is lost
irretrievably when power is turned off.
• Based on the lifetime of the content during power-on, RAM can be
classified as static RAM (SRAM) and dynamic RAM (DRAM).
• SRAMs retain their content as long as the power is on and DRAM
retains content only for a short, duration (about 4 ms).
123
HARDWARE ELEMENTS
2. Memory Elements…
• A DRAM needs a controller to refresh its memory content
periodically.
• Dynamic random-access memory (DRAM) is a type of randomaccess memory that stores each bit of data in a separate capacitor
within an integrated circuit. The capacitor can be either charged or
discharged; these two states are taken to represent the two values
of a bit, conventionally called 0 and 1. Since capacitors leak charge,
the information eventually fades unless the capacitor charge is
refreshed periodically. Because of this refresh requirement, it is a
dynamic memory as opposed to SRAM and other static memory.
124
HARDWARE ELEMENTS
2. Memory Elements…
• A SRAM is fast and expensive compared to a DRAM. So, normal
systems tend to have a small SRAM for critical data and code and a
large DRAM to hold the rest of the code and data during execution.
Basic DRAMs are designed to issue memory operations sequentially,
and the synchronization is done by applying control signals
asynchronously, not by regular clock pulses. That is, in DRAMs, the
instruction for the next operation is issued after the completion of
the current operation.
• Synchronous DRAMs (SDRAMS) are synchronized with clock pulses
to respond to incoming operations.
• SDRAMs respond to the next operation before completing the
current operation, because they can accept operations synchronized
with clock pulses and need not wait for asynchronous control
signals. The purpose is to increase memory bandwidth.
125
HARDWARE ELEMENTS
2. Memory Elements…
• To increase the bandwidth further, memories are designed with
multiports through which data can be accessed simultaneously by
many agents, and are called mulliport memories.
• SRAMs have been improved and work with backup battery and such
classes of SRAMs are referred to as non-volatile RAMs (NVRAMs).
• When power is on, NVRAMs work like SRAMs and when power is
off, they automatically draw power from the battery backup.
• NVRAMs are more expensive than SRAMs.
• Since a majority of the code and, perhaps, some data too do not
change over time in most embedded systems, these systems make
extensive use of ROM memories to hold critical- and stable code
and data. Also, the code and relevant data must be retained even
when the power is off.
126
HARDWARE ELEMENTS
2. Memory Elements…
• Based on the technique employed to write and the number of times
it can be rewritten, ROMs can be classified into three families:
factory programmed (also Called masked ROM), programmable
ROM (PROM), and erasable-and programmable ROM (EPROM).
• Masked ROMs come with a particular code written (hardwired) in it and are
produced when large quantities of a single program are required for applications.
The contents of a masked ROM must be specified before production of the chip.
• The next family of ROMs is the PROM which, once fabricated, can be
programmed only once (also known as one-time programmable ROM (OTPROM)). After that, its content never changes.
• EPROM is the third family. It works same way as the PROM except that it can be
reprogrammed many times. Its content is erased with ultraviolet (UV) light and,
therefore, is often referred to as UV-EPROM. EPROMs required UV light to erase
their content before reprogramming which required electrical power.
127
HARDWARE ELEMENTS
2. Memory Elements…
• Electrically erasable and programmable ROMs (EEPROMs) use electricity
for both erasing and reprogramming. Again, these earlier EEPROM
memories required removal from the computer for reprogramming
(erasing and writing new programs) in the lab and needed nigh voltages
for reprogramming.
• The modern EEPROM, called flash memory, requires only low voltage for
reprogramming and, therefore, uses the standard system voltage for
reprogramming. This facilitates reprogramming inside a typical embedded
system.
• In the beginning, the entire flash memory needed to be erased for
reprogramming.
• Modern flash memories allow selective erasure of content in blocks for
reprogramming while other blocks are protected. Important- and stable
codes such as the boot-up code can be kept in protected blocks and the
remaining blocks used for updates and other programs.
128
HARDWARE ELEMENTS
3. Special I/O Devices.
• In addition to traditional I/O devices such as keyboard, mouse,
monitor, printer, communication channel, etc., RE systems often
come with a variety of other I/O components such as
– sensors,
– touch screens,
– radars,
– GPS,
– LED display panels.
• Particularly, most RE systems are connected to many action- or
activation devices, usually mechanical devices, to perform intended
functions of the system. These devices are collectively called
actuators.
129
HARDWARE ELEMENTS
Special I/O Devices…
• These varieties of I/O interfaces make the software design of RE
systems highly complex.
• >> Most embedded systems are not equipped with hard disks to
keep data safe. Flash memories replace hard disks in embedded
devices. Note that for historical reasons these hybrid memories are
referred to as ROM memories, although they are read-write random
access memories.
• >> RE systems may be divided into purely cyclic, mostly cyclic,
asynchronous but predictable and asynchronous and unpredictable,
based on the timing attributes of the tasks.
130
HARDWARE ELEMENTS
3. Special I/O Devices…
• Purely cyclic tasks are typically real-time monitoring and control
tasks.
• Mostly cyclic tasks are cyclic and usually have additional
responsibility to attend to occasional external events. Most process
control systems belong to this category.
• Applications such as multimedia, radar signal processing, and
surveillance although performing their tasks repetitively in a
predictable manner are not periodic.
• Most of the complex real-time systems such as intelligent control
systems usually do not fall into any of the above three categories
and, therefore, may be considered asynchronous and unpredictable
systems.
131
HARDWARE ELEMENTS
3. Special I/O Devices…
• >> Most embedded systems are I/O intensive. The system must
often provide deterministic response for non-deterministic events.
• Most RE systems use
– interrupt devices,
– real-time clocks,
– hardware timers,
– and watchdog timers.
• Real-time clocks provide accurate record of elapsed time.
• The software timers the operating systems provide are often not
accurate.
132
HARDWARE ELEMENTS
3. Special I/O Devices…
• Hardware timers are now used to provide accurate time support for
individual applications where software timers are not sufficient.
• Watchdog timers are used as the last line of defence against
program malfunction.
• When timeout occurs, it generates a non-maskable interrupt for a
recovery program. The recovery program then takes suitable
actions.
133
HARDWARE ELEMENTS
4. Communication and Other Elements.
• As in traditional computing systems. RE systems also use collections
of wires called buses for the CPU, the memory, and other devices
for communication. They communicate using suitably defined
protocols.
• Two standard interfaces dominantly are used to connect external
devices: parallel and serial communication interfaces.
• The system communicates with the external world through these
interfaces. To control the communications, special devices such as
the direct memory access (DMA) controller (for direct
communication between I/O devices and memory) and the
interrupt controller (for coordinated communication between CPU
and other devices) are used.
• Other basic devices used in RE systems include analogue to digital
converters (ADCs) and digital to analogue converter (DACs). 134
HARDWARE ELEMENTS
5. Real-time Embedded Hardware Systems.
• Using the elements discussed above, many types of RE systems can
be designed.
• Based on its use and sophistication, a programmable computing
device, built from these components, is called either a
microcontroller or a microcomputer.
• At a higher level, microcontrollers are designed for special purpose
computing and microcomputers are designed for general purpose
computing.
• Essentially, microcomputer means a computer with micro-processor
for its CPU. At a lower level, a computer has a CPU, a memory, I/O
devices, and busses for communication between the CPU, the
memory, and the I/O devices.
135
HARDWARE ELEMENTS
5. Real-time Embedded Hardware Systems …
• Many practical computers have other units such as timers, interrupt
controllers, device controllers, etc.
• The two popular architectures used for transfer of data and
instructions during execution are Von Neumann (or Princeton)
architecture and Harvard architecture.
• Von Neumann architecture uses one bus for both data and
instructions, while Harvard architecture uses separate buses.
• A RE system can use microcontrollers, microcomputers, or both.
• As integrated technology advances, more units such as timers, I/O
ports and interfaces, device controllers, and memories, and
memory management units (MMUs) are added into a single chip,
creating single-chip microcontrollers, and single-chip
microcomputers.
136
HARDWARE ELEMENTS
5. Real-time Embedded Hardware Systems …
• >> Von Neumann architecture has simplicity and generality whereas
Harvard architecture offers high throughput.
• Most DSPs use Harvard architecture and most microprocessors use
von Neumann architecture.
• Sophisticated single-chip microcontrollers are called system-on-chip
— an application-specific system design in a single chip. These
designs have both microprocessors and DSPs as their core elements.
• With this preamble to hardware, we now introduce the operating
systems for RE systems.
137
SECTION B
• Real Time and Embedded Operating Systems:
– Introduction,
– Hardware Elements,
– Structure
138
SECTION B
• Real Time and Embedded Operating Systems:
– Introduction,
– Hardware Elements,
– Structure
139
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
ORG
LJMP Initialisation
; Interrupts Section
ORG
0003H
LJMP
ISR_for_INT0
ORG
LJMP
; ….
0013H
ISR_for_INT1
ORG
0030H
; Bypass code for handling interrupts
; Initialisation section
Initialisation:
;…. Initialise various ports and registers, setup interrupts etc
MainLoop:
ISR_for_INT0:
Action1:
SetB
RET
; Code for sensing periodic inputs, random events may also be sensed in loop
; Conditional jumps
Acall
Action1
; Calling other subroutines based on sensed input
SJMP MainLoop
; Routines for servicing interrupts.
SETB
P2.1
RETI
; Other actions
P2.2
;.. Code here
END
140
141
Sections
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
ORG
LJMP Initialisation
; Bypass code for
handling interrupts
1. ORGIN (Begin)
and END for the complete
operating
system. Every
; Interrupts Section
line of code ORG
will be 0003H
inside this boundary unless routines from
LJMP
ISR_for_INT0
secondary storage
are
to be called.
2. Interrupts Section:
ORG
0013H
a. Defines origin
(address)
LJMP
ISR_for_INT1 for each hardware interrupt as per
Interrupt; ….Vector Table.
b. IncludesORG
Jump to
respective Interrupt
Routines (ISRs).
0030H
; InitialisationService
section
Initialisation:
3. Initialisation Section.
This part is outside operating system
;…. Initialise various ports and registers, setup interrupts etc
mainloop. Following initialisations are done here:MainLoop:
; Code
for sensing
periodic
events may also
be sensed in loop
a. Initialise
Input
ports
orinputs,
pinsrandom
for sensors
(temperature,
pressure,
; Conditional jumps
flow rate,
voltage,
current etc),
keypads (for user input) and
Acall
Action1
; Calling other subroutines based on sensed input
other inputs.
SJMP MainLoop
ISR_for_INT0:
for servicing interrupts.
b. Initialise Output ports or pins; Routines
for LCD,
LED or other output
SETB
P2.1
devices.RETI
Action1:
Other actions
c. Initialise other variables and ;data
structures.
SetB
P2.2
;.. Code here
d. Initialise
communication
parameters
RET
END
142
Sections
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
ORG
Initialisation
; Bypass code for handling interrupts
4. Main Loop LJMP
Section.
; Interrupts Section
a. RemainORG
in an endless
loop.
0003H
LJMP responds
ISR_for_INT0
b. Hardware
to interrupts while processor is waiting for
other inputs.
Code
for other inputs is here.
ORG
0013H
c. Depending
the input, the program calls corresponding
LJMP on ISR_for_INT1
; ….
action routines.
5. Interrupt Service
Routines.
There
is section
a separate routine for
ORG
0030H
; Initialisation
Initialisation:
servicing each interrupt.
;…. Initialise various ports and registers, setup interrupts etc
6.
Other Service Routines.
This section contains all other
MainLoop:
; Code for sensing periodic inputs, random events may also be sensed in loop
action subroutines.
Conditional jumps
7. User Input ;Acall
Routines.
These routines
contain code for action on
Action1
; Calling other subroutines based on sensed input
user inputs.SJMP
They
may be called by ISRs or from OS mainloop.
MainLoop
ISR_for_INT0:
; Routines for servicing interrupts.
SETB
RETI
P2.1
Action1:
; Other actions
SetB
RET
P2.2
END
;.. Code here
143
144
SYLLABUS
Real Time and Embedded Operating System (RTES or ER)
1. Writing Real Time and Embedded Operating System for 8051
Microcontroller.
a.
Write a simple operating system for 8051 microcontroller which is required
to monitor and control water level in a tank. If the water level falls below a
critical level, it should start the water pump automatically. If the level rises
above the top level, it should stop the motor.
b. Guidelines.
i.
ii.
iii.
iv.
v.
There would be two sensors. One for sensing lowest level and the other for
sensing highest level.
The sensors would be connected to two pins of a port. These pins/port would be
configured as input port.
These sensor pins would be checked in a loop for their status.
When the water level falls below the lowest level, another port pin, configured
as output pin, would be set to 1 (Say P2.1). This pin would be connected to an
electric relay. If both the sensors are off, give instruction SetB P2.1. which would
start the water pump.
When the water level increases above upper level, the pump is stopped by
145
another instruction: Clr P2.1
SYLLABUS
Real Time and Embedded Operating System (RTES or ER)
1. Writing Real Time and Embedded Operating System for 8051
Microcontroller…
146
SYLLABUS
Real Time and Embedded Operating System (RTES or ER)
1. Writing Real Time and Embedded Operating System for 8051
Microcontroller…
ORG 00
; Configure P1.1 and P1.2 as input pins
SetB
P1.1
SetB
P1.2
; Now they have high voltage. When water crosses these levels,
; the Sensors should send low voltage (0V) on these pins.
; Configure P2.1 as output pin
Clr
P2.1
; Relay should be wired such that
; it also stops the motor
Mainloop:
; Check Low level
CheckLowLevel:
147
SYLLABUS
Real Time and Embedded Operating System (RTES or ER)
1. Writing Real Time and Embedded Operating System for 8051
Microcontroller…
Mainloop:
; Check Low level
CheckLowLevel:
JNB
P1.1,
CheckHighLevel ; P1.1 = 0, Water is above empty level
SetB
P2.1
; Tank is Empty , Start Water Pump
SJMP CheckAgain
; Bypass High level checks.
; Let the pump keep running.
CheckHighLevel:
; If water is above low level, check upper level
JB
P1.2, CheckAgain
; Water is below Top level
Clr
P2.1
; Tank is Full, Stop Water Pump
CheckAagain:
SJmp Mainloop
END
148
Condition
High Level Sensor Low Level Sensor
Pin
Pin
Motor Relay Pin
Motor Status
Initialisation outside
Mainloop: Assume
initially Tank is Empty
Set it to High (1) : Set it to High (1):
Inactive
Inactive
Set it to Low (0)
Initially Stop
Motor
2
Enter Mainloop
Sensor indicates
below top level
Sensor indicates
below low level
Becomes High (1)
Motor Starts
3
Now Motor is Running High (1) : Inactive High (1): Inactive
Remains High (1)
Motor keeps
running
4
After sometime Low
level sensor gets
activated
Motor keeps
running
5
Water crosses Top
Level
Remains High (1): Becomes Low (0): Remains High (1)
Inactive
Active; Water
rises above Lower
level
Becomes Low (0): Remains Low (0): Becomes Low (0)
Active
Active
6
Water level falls with
Becomes High
usage. Falls below high (1): Inactive
level
7
Water Falls further
and goes below low
level
1.
Remains Low (0):
Active
Remains Low (0)
Remains High (1): Becomes High (1): Becomes High (1)
Inactive
Inactive
Motor Stops
Motor Remains
Off
Motor Starts
149
SYLLABUS
Real Time and Embedded Operating System (RTES or ER)
2. Write an interrupt driven operating system to monitor and control
water level in a tank. Water level sensors would be wired on
external interrupt pins (P3.2 and P3.3).
150
INTERRUPT DRIVEN OS FOR WATER TANK
ORG 00
LJMP
Initialise
; Bypass Interrupt Vector Table
; Vector Address for INT0 is 0003H
ORG
0003H
LJMP
ISR_for_INT0
; ISR: Abbreviation for Interrupt Service Routine
; Vector Address for INT1 is 0013H
ORG
0013H
LJMP
ISR_for_INT1
ORG 0030H
Initialise:
; Configure P3.2 and P3.3 as input pins
SetB
P3.2
; Interrupt pin
SetB
P3.3
; Normal Pin
; Now they have high voltage. When water crosses these levels,
; the Sensors should send low voltage (0V) on these pins.
; Configure P2.1 as output pin
Clr
P2.1
; Relay should be wired such that
; it also stops the motor
151
INTERRUPT DRIVEN OS FOR WATER TANK…
; Setup Interrupts
; preprocess a few bits of three SFR’s namely TCON, IE and IP
; 1. TCON Register is to be configured for enabling type of signal.
;
Let it remain with default values.
; 2. IE Register: Configure Interrupt Enable Register.
; Set Bit 0 for Enabling External Interrupt 0 or Clear it to disable
; Set Bit 2 for Enabling External Interrupt 1 or Clear it to disable
; Set Bit 7 to enable interrupts. Interrupts would be serviced only if Bit 7 = 1
;MOV IE, #10000001B
;MOV IE, #10000100B
MOV IE, #10000101B
;Enable External INT0
;Enable External INT1
;Enable External INT0 and INT1
; 3. IP Register: Special Function Register IP is to be configured
;
for changing priority of interrupts.
;
Let it have default values
Mainloop:
; Microcontroller keeps running in this loop.
; When an interrupt is received, its subroutine would be run.
NOP
SJmp Mainloop
152
INTERRUPT DRIVEN OS FOR WATER TANK…
Mainloop:
; Microcontroller keeps running in this loop.
; When an interrupt is received, its subroutine would be run.
NOP
SJmp Mainloop
ISR_for_INT0:
JNB P3.3, StopPump
; Interrupt Pin P3.3 indicates water is already above top
; Otherwise, water is lower than lowest level. Therefore Motor is to be started.
; Sensor and circuit should send a low voltage on P3.2
SetB
P2.1
SJMP
Done
StopPump:
CLR
P2.1
; Stop Pump
Done:
RETI
ISR_for_INT1:
; Water is higher than lowest level. Therefore Motor is to be stopped.
; Sensor and circuit should send a low voltage on P3.3
Clr
P2.1
RETI
END
153
ADD TIMER INTERRUPT
INTERRUPT DRIVEN OS FOR WATER TANK
ORG 00
LJMP
Initialise
; Vector Address for INT0
ORG
0003H
LJMP
ISR_for_INT0
; ISR: Abbreviation for Interrupt Service Routine
; Vector Address for Timer0
ORG
000BH
LJMP
ISR_for_Timer0
; ISR: Abbreviation for Interrupt Service Routine
; Vector Address for INT1
ORG
0013H
LJMP
ISR_for_INT1
ORG 0030H
Initialise:
; Configure P3.2 and P2.0 as input pins
SetB
P3.2
; Interrupt pin
SetB
P3.3
; Normal Pin
; Now they have high voltage. When water crosses these levels,
; the Sensors should send low voltage (0V) on these pins.
; Configure P2.1 as output pin
Clr
P2.1
; Relay should be wired such that
; it also stops the motor
INTERRUPT DRIVEN OS FOR WATER TANK…
; Setup Interrupts
; preprocess a few bits of three SFR’s namely TCON, IE and IP
; 1. TCON Register is to be configured for enabling type of signal.
;
Let it remain with default values.
; 2. IE Register: Configure Interrupt Enable Register.
; Set Bit 0 for Enabling External Interrupt 0 or Clear it to disable
; Set Bit 2 for Enabling External Interrupt 1 or Clear it to disable
; Set Bit 7 to enable interrupts. Interrupts would be serviced only if Bit 7 = 1
;MOV IE, #10000001B
;MOV IE, #10000100B
;MOV IE, #10000101B
MOV IE,#10000111B
;Enable External INT0
;Enable External INT1
;Enable External INT0 and INT1
;Enable INT0, Timer0 and INT1
; 3. IP Register: Special Function Register IP is to be configured
;
for changing priority of interrupts.
;
Let it have default values
Mainloop:
; Microcontroller keeps running in this loop.
; When an interrupt is received, its subroutine would be run.
NOP
SJmp Mainloop
INTERRUPT DRIVEN OS FOR WATER TANK…
Mainloop:
; Microcontroller keeps running in this loop.
; When an interrupt is received, its subroutine would be run.
NOP
;Set Timer0 parameters and Start Timer
MOV TMOD, #01H
; Set TMOD for Mode1: 16 Bit Timer Mode
MOV TH0, #0FFH
; Set values in Timer0 Register High byte
MOV TL0, #0F9H
; Set values in Timer0 Register Low byte
SETB TR0
; Start Timer 0 ->FFF9->FFFA->FFFB…->FFFF
; Assume Task further is a long job.
; Timer will keep running.
; After Timer 0 overflow, its interrupt would get activated.
NOP
NOP
NOP
NOP
NOP
NOP
NOP
NOP
NOP
NOP
SJmp Mainloop
INTERRUPT DRIVEN OS FOR WATER TANK…
Mainloop:
; Microcontroller keeps running in this loop.
; When an interrupt is received, its subroutine would be run.
NOP
SJmp Mainloop
ISR_for_INT0:
JNB P3.3, StopPump
; Water is lower than lowest level. Therefore Motor is to be started.
SetB
P2.1
; Sensor and circuit should send a low voltage on P3.1
SJMP
Done
StopPump:
CLR
P2.1
; Stop Pump
Done:
RETI
ISR_for_INT1:
; Water is higher than lowest level. Therefore Motor is to be stopped.
Clr
P2.1
; Sensor and circuit should send a low voltage on P3.2
RETI
INTERRUPT DRIVEN OS FOR WATER TANK…
ISR_for_Timer0:
; Stop Timer 0, Clear its Flag
Clr TR0
Clr TF0
; Action: ... Create a low to high pulse on P2.0
CLR P2.0
NOP
SetB P2.0
RETI
END
160
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
Operating Systems for RE Systems
• A general purpose computer has a relatively simple but powerful
architecture which interacts with the outside world through a small
set of well-defined I/O interfaces.
• Its hardware resources are well known and outside interactions are
not difficult to control.
• Operating systems for such general purpose computers are
widespread and relatively well understood.
• Since RE systems are special purpose systems and diverse, their
software including operating systems is often tailor-made, less
standardized, and, therefore, not all that well understood.
161
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
Operating Systems for RE Systems…
• Certainly, titles such as real-time operating system and embedded
operating system are often used in the computing world.
• However, due to the diverse nature of RE systems, there is no such
thing called a real-time operating system or embedded operating
system defined with all functionalities.
• However, some of the issues and functionalities of real-time
operating systems are studied well, usually in isolation, often under
the title of real-time and embedded operating systems.
• In recent times, the subject has gained more popularity and many
operating systems are released as either real-time or embedded
operating systems.
• Some of these systems are direct modifications of traditional
operating systems and others borrow key ideas from traditional
162
operating systems.
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
Operating Systems for RE Systems…
• Essentially, most RE systems are I/O dominated systems and are
often part of physical systems, and physical systems are intrinsically
concurrent and temporal (temporal: relating to or limited by time).
• In general-purpose systems, I/Os are usually dealt with well-defined
interrupt handling.
• Usually, I/O interfacing in RE systems involves both interrupt- and
exception handling.
• The exceptions introduced by the environment through I/O are hard
to visualize at the design stage but anyhow required to be
addressed properly.
• In the context of general purpose operating systems, exception
handling usually deals with detecting a set of well-defined internal
problems such as arithmetic and stack overflows, memory and array
163
bound violations. etc.
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
Operating Systems for RE Systems…
• Operating systems designed for RE systems, in addition, must deal
with external failures as well as their induced internal failures.
• Even improper handling of internal failures may lead to external
failures with serious consequences.
• Services provided by traditional non-real-time operating systems
have many similarities with the services provided by real-time and
embedded operating systems (REOS).
• The fundamental difference is the need for “deterministic” timing
behaviour in the case of real-time computing.
• Deterministic timing implies that operating systems should respond
to requests within a known- and expected amount of time.
• Non-deterministic behaviour is common in traditional operating
systems.
164
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
Operating Systems for RE Systems…
• Overall, it is hard to come up with a comprehensive answer to the
question of what is REOS.
• Perhaps, the simplest answer would be "an operating system
designed for RE systems".
• >> The most important activities in consumer electronics are:
(1) control driven — implemented by periodic tasks;
(2) data driven — audio, video, graphics applications; and
(3) Interactive - asynchronous event-based applications.
• >> An REOS is expected to support priorities, interrupts, timers,
concurrent executions, intertask communication, and predictable
synchronization, and mechanisms to assure bounded latencies, it
must be correct, reliable, and must assure safety.
165
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
Operating Systems for RE Systems…
• >> RE systems may be divided into
–
–
–
–
purely cyclic,
mostly cyclic,
asynchronous but predictable,
and asynchronous and unpredictable, based on the timing attributes of the
tasks.
• Purely cyclic tasks are typically real-time monitoring and control tasks.
• Mostly cyclic tasks are cyclic and usually have additional responsibility to attend
to occasional external events. Most process control systems belong to this
category. Applications such as multimedia, radar signal processing, and
surveillance although performing their tasks _ repetitively in a predictable
manner are not periodic. Most of the complex real- time systems such as
intelligent control systems usually do not fall into any of the above three
categories and, therefore, may be considered asynchronous and unpredictable
systems.
166
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
Operating Systems for RE Systems…
• However, it often refers to a collection of components or a design
approach for real-time software systems.
• Providing operating system support to a wide range of RE systems is
a complex task.
• RE systems use home-grown simple control software instead of
general purpose operating systems such as UNIX, Linux, and
Windows with added real-time supports.
• In relation to other types of operating systems such as batch- and
interactive operating systems, based on the speed of response as
the criterion, RE systems may be considered as systems where the
response is expected within a short but "definite" or “bounded”
time.
167
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
Operating Systems for RE Systems…
• In addition, these systems must facilitate ways to handle
unexpected errors, missed deadlines, inevitable failures, and may
operate under resource constraints.
• Many commercial real-time operating systems are available to run
on common processors and have sizable user base.
• They include
– Windows CE (Embedded Compact),
– LynxOS(The LynxOS RTOS is a Unix-like real-time operating system from
LynuxWorks),
– pSOS (Portable Software On Silicon is a real time operating system (RTOS),
created in about 1982 by Alfred Chao),
– Jbed (Jbed, a small, fast Java Virtual Machine for embedded real-time
systems, includes a complete real-time operating system.),
168
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
Operating Systems for RE Systems…
• They include
– …
– QNX (QNX is a commercial Unix-like real-time operating system, aimed
primarily at the embedded systems market.),
– VRTX (Versatile Real-Time Executive (VRTX) is a real-time operating system
developed and marketed by the company Mentor Graphics. VRTX is suitable
for both traditional board-based embedded systems and SoC (System on a
Chip) architectures.),
– Symbian (Symbian OS is an operating system for mobile phones primarily
used on Nokia advanced or data enabled smart phones. Symbian OS runs
exclusively on ARM processors),
– and VxWorks (VxWorks is a real-time operating system developed as
proprietary software by Wind River Systems of Alameda, California, USA. First
released in 1987, VxWorks is designed for use in embedded systems.).
169
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
Operating Systems for RE Systems…
• They all have many similarities and are generally conform to realtime POSIX API standard.
• POSIX, an acronym for "Portable Operating System Interface", is a family of
standards specified by the IEEE for maintaining compatibility between operating
systems. POSIX defines the application programming interface (API), along with
command line shells and utility interfaces, for software compatibility with
variants of Unix and other operating systems.
• Some design philosophies are:
– keep it simple and effective,
– provide effective interrupt handling,
– offer efficient scheduling and memory management,
– and provide mechanisms to solve task coordination issues.
170
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
Operating Systems for RE Systems…
• The approach of “one-size-fit-all" for RE systems cannot be the best
one for obvious reasons.
• Next, we look at some basic structures of REOS and then some of
the main components.
171
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
The Structure of REOS
• From the discussion so far, it is easy to infer that most REOSs are
interrupt-driven.
• Timers and peripherals (such as I/O, sensors, etc) trigger interrupts.
• Based on the source, interrupts play two crucial roles.
– In the case of timer interrupts, they mark the specific instants of
initiation and completion of certain time-critical tasks.
– Peripheral interrupts inform the CPU of some asynchronous
events, which usually require immediate attention for the
system to function properly.
172
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
The Structure of REOS …
• RE system's functionalities are traditionally abstracted into tasks,
and these tasks undergo various states such as ready (activated),
suspended; waiting, etc.
• These states are mostly managed by hardware interrupts.
• Again, RE systems vary from a simple controller to a complex
networked control system.
• Simple controller activities can be abstracted as tasks and then
managed through an interrupt handler, but not the complex
networked control systems.
• Here we review some popular models used to build real-time
software.
173
SECTION B
• Real Time and Embedded Operating Systems:
– Introduction,
– Hardware Elements,
– Structure
• Interrupt Driven,
174
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
1. A Basic Interrupt-driven Task Model.
• This is the simplest model and often used to design simple real-time
software.
• This model considers each system activity as a task and the code for
each task is written as an interrupt routine, also known as interrupt
service routine (ISR).
• The interfaces to boards and panels are written as interfacing
routines that can be used as ISRs.
• Then a simple control routine is used to coordinate their activities.
• Hardware timers are used to generate necessary interrupts during
execution.
175
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
1. A Basic Interrupt-driven Task Model…
• When an interrupt occurs, it is handled by the following steps.
1. The context of the current task is saved.
2. The interrupt is identified and its associated ISR is invoked.
3. The saved context is restored and the execution of the interrupted task is
resumed.
• ln some systems, lSRs are not preemptible, and in others lSRs can
be preempted by higher priority interrupts.
• If several interrupts are pending, then they are served in the order
according of their priorities.
• The key aspect of this model is that the tasks (lSRs) are designed
carefully for speed and predictability.
• The related approach of minimal operating system is called
exokernel-based design.
176
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
177
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
1. A Basic Interrupt-driven Task Model …
• Exokernel is an operating system kernel developed by the MIT
Parallel and Distributed Operating Systems group, and also a class
of similar operating systems.
•
The Massachusetts Institute of Technology (MIT) is a private research university in
Cambridge, Massachusetts known traditionally for research and education in the physical
sciences and engineering, and more recently in biology, economics, linguistics, and
management as well.
• The purpose is that the operating system should provide only very
basic support such as
– allocating resources to tasks,
– protecting tasks from each other,
– revoking access to resources, etc., (Revoke: To void or annul by recalling,
withdrawing, or reversing)
leaving the rest of the higher-level policies to the application developers.
178
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
1. A Basic Interrupt-driven Task Model …
• Above all, the operating system should not provide any service
abstractions by hiding all hardware resources from applications.
• This approach advocates
– application-level management of physical resources,
– and enables users to have custom abstractions where they can choose to
implement the level of abstraction they want.
• The advantage is superior performance, but it is hard to write
applications on exokernel-based systems.
179
180
SECTION B
• Real Time and Embedded Operating Systems:
– Introduction,
– Hardware Elements,
– Structure
• Interrupt Driven,
• Nanokernel,
181
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
2. The Nanokernel-based Model.
• In the previous model, the entire code involved in time- and
interrupt management must be developed from scratch.
• lt is a tedious job developing large applications.
• The nanokernel approach is considered the first step towards
providing software support for real-time application development
and execution.
• The term nanokernel is not standardized.
• However, the objective is to classify the tasks as
– regular and
– time-critical.
• Then, the time-critical tasks are handled through the interruptdriven technique as discussed above and the regular tasks are
handled through the kernel.
182
NANOKERNEL BASICS
Mainloop:
Input0:
JB
ACall
SJMP
; Assume P1 is configured as input port. It can receive 8 inputs.
; If user presses a key, the corresponding pin drops to 0 volt.
P1.0, Input1
; High voltage on a pin means no input, 0 means it has input.
Action0
NextRound
Input1:
JB
ACall
SJMP
P1.1, Input2
Action1
NextRound
Input2:
JB
ACall
SJMP
P1.2, NextRound
Action2
NextRound
NextRound:
SJmp Mainloop
183
NANOKERNEL BASICS
Mainloop:
; Assume P2 is configured as input port. It can receive 8 inputs.
Input0:
; If user presses a key, the corresponding pin drops to 0 volt.
JB
P2.0, Input1 ; High voltage on a pin means no input, 0 means it has input.
ACall
Action0
SJMP
NextRound
Input1:
JB
P2.1, Input2
ACall
Action1
SJMP
NextRound
Input2:
JB
P2.2, NextRound
ACall
Action2
SJMP
NextRound
NextRound:
SJmp Mainloop
Action0:
SetB
RET
; Assume P2 is configured as output port. A high voltage on a pin indicates alarm.
P2.0
; Raise Alarm0 or start Motor0 etc.
Action1:
SetB
RET
P2.1
; Raise Alarm1 or start Motor1
SetB
RET
END
P2.2
; Raise Alarm2 or start Motor2
Action2:
184
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
2. The Nanokernel-based Model…
• The kernel provides the following minimal set of services:
1.
2.
3.
task creation and deletion;
task scheduling;
timing and interrupt management.
• For the basic timing mechanism, the kernel uses a separate timer
(tick) interrupt routine.
• At a conceptual level, this model includes a hardware abstraction
layer for the (internal and external) devices.
• The design and implementation of this interface is entirely the
responsibility of the programmer.
• From a layered view,
– the kemel is in layer 1,
– the interfacing and interrupt software is in layer 2,
– and applications are in layer 3.
185
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
2. The Nanokernel-based Model…
• >> Interrupts enable hardware components to communicate their
requests effectively to the processor that eventually transfers the
control to the operating system to attend the requests.
• >> Real-time tasks must be kept simple, efficient, and error free.
• >> Exokernel, developed at MIT, is based on the philosophy that
applications know how to manage the system resources better than
operating systems do. Operating systems must be simple and
predictable, should be close enough to bare hardware, and support
only the multiplexing capability of resources among applications
securely.
186
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
The Nanokernel-based Model…
• >> The microkernel-based system is concerned with the design
approach, not necessarily meaning a smaller system in overall size.
The objective is to examine- and design operating systems from
both simplistic- and performance points of view.
187
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
188
MICROKERNEL VS MONOLITHIC KERNEL
• A monolithic kernel is a kernel where
– all services (file system, VFS, device drivers, etc)
as well as
– core functionality (scheduling, memory allocation, etc.)
are a tight knit group sharing the same space. This directly
opposes a microkernel.
• A microkernel prefers an approach where core
functionality is isolated from system services and device
drivers (which are basically just system services).
• VFS: Virtual File System. Linux has basic file system as Extt2, Extt3,
Ext4 etc. FAT32, NTFS etc are visible to linux through VFS.
189
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
Interrupt Handling
• For each interrupt, there is a fixed location in memory that holds
the address of its ISR. Fixed location has been set by the hardware.
Memory space available from this address is limited. Therefore,
only a jump instruction is written there by the programmer. A
complete subroutine is written starting at the new memory
location.
190
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
• Steps in executing interrupts in the case of 8051 Series of
Microcontrollers:1.
2.
3.
4.
5.
6.
7.
Upon activation of an interrupt , the microcontroller finishes the instruction
it is executing and saves the address of the next instruction (Program
Counter (PC)) on the stack.
It also saves the current status of all the interrupts internally (ie not on the
stack).
It jumps to a fixed location in memory in accordance with the Interrupt
Vector Table.
If the ISR is only one or two instructions, these may be written there itself.
Generally, the ISR has many instructions. In such cases, a jump instruction is
placed at interrupt vector address.
The last instruction in the ISR is RETI (Return from Interrupt).
Upon executing RETI instruction, the microcontroller returns to the place
where it was interrupted. First it gets the Program Counter address from the
stack by popping the top two bytes of the stack into the PC. Then it starts to
execute from that address.
191
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
• Interrupts in 8051.
1.
2.
3.
4.
There are Six interrupts in 8051.
Reset. When the reset pin is activated, the 8051 jumps to address
location 0000. This is the power-up reset. Program execution starts from
address 0000.
Timer Interrupts (Two).
Two interrupts are set aside for the
timers, one for Timer 0 and the other for Timer 1. Memory locations 000BH
and 001BH in the interrupt vector table belong to Timer 0 and Timer 1
respectively.
External Hardware Interrupts (Two).
Pin No 12 (P3.2) and 13 (P3.3) in
Port 3 are for the external hardware interrupts. INT0 and INT1, respectively.
These external interrupts are also referred to as EX1 and EX2. Memory
locations 0003H and 0013H in the interrupt vector table are assigned to
INT0 and INT1 , respectively
Serial Communication Interrupt.
Serial communication has a
single interrupt that belongs to both receive and transfer. The interrupt
vector table location 0023H belongs to this interrupt.
192
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
•
•
•
•
•
•
RESET
INT 0:
Timer 0:
INT 1:
Timer 1:
Serial COM:
0000H
0003H
000BH
0013H
001BH
0023H
to
to
to
to
to
to
0002H
000AH
0012H
001AH
0022H
002AH
=
=
=
=
=
=
3 Bytes
8 Bytes
8 Bytes
8 Bytes
8 Bytes
8 Bytes
193
INTERRUPT HANDLING IN 8051
ORG
LJMP
0000H
MainLoop
; ISR for Timer 0
ORG
000BH
CPL
P2.1
RETI
; Long JMP is a three byte instruction with 16 Bit address
to generate square wave
; This ISR is very small, It is written within 8 Bytes
; Use RETI to return from ISR
; ISR for External Hardware Interrupt INT 1
ORG
0013H
LJMP
StartAlarm ; If the ISR is longer than 8 Bytes, jump to subroutine
RETI
ORG
0030H ; After vector table space
MainLoop
; Keep waiting for interrupts in this loop
SJMP MainLoop ; Short JMP is a two byte instruction with Relative Address
StartAlarm:
SetB
;…
RETI
END
P1.0
…
; Alarm circuit connected to P1.0
; Write more instructions here
; Use RETI to return from ISR
194
195
SECTION B
• Real Time and Embedded Operating Systems:
– Introduction,
– Hardware Elements,
– Structure
• Interrupt Driven,
• Nanokernel,
• Microkernel
196
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
3. The Microkernel-based Model.
• This model is the next improvement over the nanokernel model.
• Essentially more functions are added to the kernel, and interfaces
for board devices is provided as a package called board support
package (BSP).
• At the kernel level, the following three additional functionalities are
provided:
1.
2.
3.
mechanisms such as semaphore and monitor are supported for process
synchronization; (a semaphore is a variable that is used for controlling access, by multiple
processes, to a common resource in a parallel programming or a multi user environment.)
primitives such as channel and mailbox are supported for inter-process
communication;
functions such as allocation and deallocation are supported for dynamic
memory allocation.
• The purpose of BSP is to minimize the effort involved in developing
197
interface software.
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
3. The Microkernel-based Model.
• At the kernel level, the following three additional functionalities are provided:
1.
mechanisms such as semaphore and monitor are supported for process
synchronization;
2. primitives such as channel and mailbox are supported for inter-process
communication;
3. functions such as allocation and deallocation are supported for dynamic memory
allocation.
• Semaphor.
A semaphore is a variable that is used for controlling access, by multiple
processes, to a common resource in a parallel programming or a multi user environment.
• Monitor.
Monitors are high-level programming language concepts that make mutual
exclusion of critical section “automatic” and therefore less error-prone. They require
compiler support.
•
Channel and Mailbox.
1. Channel.
Communication happens when a sender does put(Chan, Msg) and a
receiver does get(Chan). Obviously the receiver cannot proceed until the sender has
a message for it, but with channels the sender cannot proceed until the receiver asks
for the message.
2. Mailbox.
A mailbox is a variable which can be in two states: empty (when it
198
cannot be read), and full (when it cannot be written).
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
3. The Microkernel-based Model…
• The embedded operating system QNX (“Quick UNIX”) and Symbian
are microkeenel-based operating systems.
• Symbian has many layers with
–
–
–
–
a nanokemel for innermost layer,
the Symbian OS kernel for the next level,
then the microkernel servers,
and finally user applications in the
outermost layer.
• Symbian OS Design Rules
– User data is sacred
– User time is precious
– All resources are scarce
199
200
201
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
3. The Microkernel-based Model…
• The microkernel is a popular term now and, rather than offering a
policy, its objective is confined to offering only the basic
mechanisms necessary to implement the operating system policies.
• The terms nanokernel and picokernels were used to refer to kernels
smaller than the microkernel.
• With the above generic characterization of the microkernel, the
nanokernel, picokernel, and exokernel were subsumed (included)
by the microkernel paradigm.
• The plan was for the microkernel to implement the essential coreoperating system primitives so that the operating system services
could be implemented on the top of the kernel.
• However, this objective was not completely realized in most
implementations in practice.
202
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
3. The Microkernel-based Model…
• Typically, the functions such as
– task management,
– inter-task communication,
– task address space management,
– and hardware abstraction
are implemented in the kernel level.
• Other services are implemented on the next level to run usually at
the user level.
• The first conceptual breakthrough towards the real microkernel was
the external pager implemented in the Mach microkernel
developed at Carnegie Mellon University.
• In Mach, the kernel manages the physical- and virtual memory but
forwards page faults to specific user-level tasks called pagers.
203
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
3. The Microkernel-based Model…
• After a page fault, it is the pagers’ responsibility to bring the
corresponding page from the disk to the kemel space.
• The next conceptual step was the idea of handling interrupts as IPC
messages and including I/O ports in the address spaces.
• The kemel captures the interrupt, converts it into an IPC message,
and sends it to the appropriate user level process associated with
that interrupt to handle it.
• Usually, the device drivers are the intenupt handlers and are kept in
the user space.
204
SECTION B
• Real Time and Embedded Operating Systems:
– Introduction,
– Hardware Elements,
– Structure
•
•
•
•
Interrupt Driven,
Nanokernel,
Microkernel and
Monolithic kernel based models.
205
MICROKERNEL VS MONOLITHIC KERNEL
• A monolithic kernel is a kernel where
– all services (file system, VFS, device drivers, etc) as well as
– core functionality (scheduling, memory allocation, etc.)
are a tight knit group sharing the same space. This directly
opposes a microkernel.
• A microkernel prefers an approach where core
functionality is isolated from system services and device
drivers (which are basically just system services).
• VFS: Virtual File System. Linux has basic file system as Extt2, Extt3,
Ext4 etc. FAT32, NTFS etc are visible to linux through VFS.
206
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
4. The Monolithic-kernel-based Model.
• No standards exist for this model.
• Any design not following the above philosophies may be considered
under this model.
• Typically, added functionalities in this model are the following:
1. sophisticated CPU scheduling;
2. solutions for priority inversion issues;
3. improved memory management —allocation and protection
(isolating the applications software from the kernel by supporting the two
operating modes adding an isolation barrier between the individual tasks);
4. file handling;
5. graphics handling: and
6. networking.
207
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
4. The Monolithic-kernel-based Model…
• Generally, an operating system may be considered as its kernel with
the remaining part.
• In this model, since there is no separation within the operating
system as kernel and the remaining part, the entire operating
system may be viewed as a monolithic structure and hence referred
to as monolithic kernel based systems.
• RT-Linux is a monolithic kernel based real-time operating system
and Linux kernels are highly portable and easily configurable.
208
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
4. The Monolithic-kernel-based Model…
• In summary,
1. multitasking and preemption,
2. predictable performance and synchronization,
3. support for a range of priority levels and priority determination,
4. and bounded latency on task switching and interrupt handling
are some of the basic operating system requirements for real-time systems.
• With this introduction to REOS, we next focus on individual topics
such as
–
–
–
–
scheduling,
memory management,
synchronization,
and file systems.
209
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
4. The Monolithic-kernel-based Model…
• >> Despite the appeal and advantages of the microkemel paradigm,
it was not widely accepted until recently. Further, most of the
earlier microkemels were evolved from monolithic kemels and,
therefore, did not have many essential characteristics of the real
microkemel.
• >> Real-time software designers generally perceive separate kemel
spaces and separate process address spaces as disadvantageous for
time- critical applications.
210
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
4. The Monolithic-kernel-based Model…
• A monolithic kernel is an operating system architecture where the
entire operating system is working in kernel space and is alone in
supervisor mode.
• The monolithic model differs from other operating system
architectures (such as the microkernel architecture) in that it alone
defines a high-level virtual interface over computer hardware.
• A set of primitives or system calls implement all operating system
services such as process management, concurrency, and memory
management.
• Device drivers can be added to the kernel as modules.
211
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
4. The Monolithic-kernel-based Model…
Kernel Space
• System memory in Linux can be divided into two distinct regions:
kernel space and user space.
• Kernel space is where the kernel (i.e., the core of the operating
system) executes (i.e., runs) and provides its services.
• Memory consists of RAM (random access memory) cells, whose
contents can be accessed (i.e., read and written to) at extremely
high speeds but are retained only temporarily (i.e., while in use or,
at most, while the power supply remains on). Its purpose is to hold
programs and data that are currently in use and thereby serve as a
high speed intermediary between the CPU (central processing unit)
and the much slower storage, which most commonly consists of
one or more hard disk drives (HDDs).
212
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
4. The Monolithic-kernel-based Model…
User Space
• User space is that set of memory locations in which user processes (i.e.,
everything other than the kernel) run. A process is an executing instance of a
program.
• One of the roles of the kernel is to manage individual user processes within this
space and to prevent them from interfering with each other.
• Kernel space can be accessed by user processes only through the use of system
calls.
• System calls are requests in a Unix-like operating system by an active process for
a service performed by the kernel, such as input/output (I/O) or process creation.
• An active process is a process that is currently progressing in the CPU, as
contrasted with a process that is waiting for its next turn in the CPU.
• I/O is any program, operation or device that transfers data to or from a CPU and
to or from a peripheral device (such as disk drives, keyboards, mice and printers).
213
214
215
216
SECTION B
• Real Time and Embedded Operating Systems:
– Introduction,
– Hardware Elements,
– Structure
•
•
•
•
Interrupt Driven,
Nanokernel,
Microkernel and
Monolithic kernel based models.
– Scheduling:
217
SCHEDULING
CPU Scheduling
• Real-time task scheduling is one of the interesting topics and is
deeply studied in the context of real-time systems.
• The interest in the topic started with the seminal (related to origin or
seeds) work of Liu and Layland in 1973. Since then, many algorithms
have been proposed for real-time scheduling.
• Recently, the field is receiving renewed interest due to the
pervasiveness of embedded devices in the consumer market and
the advancement of technological innovations.
• Real-time task scheduling is an important responsibility of real-time
systems.
218
SCHEDULING
CPU Scheduling…
• Examples of real-time tasks include
– control of temperature in a chemical plant,
– collecting readings from sensor nodes periodically,
– monitoring systems for nuclear reactors, etc.
• Based on their importance, real-time tasks are usually prioritized.
219
SCHEDULING
CPU Scheduling…
• >>
• Priority is very important in REOS, and nothing should prevent the
execution of the highest priority tasks in the system.
• >>
• Ignoring context switch cost in task scheduling is not appropriate for
most modem systems.
• Real-time scheduling algorithms are generally preemptive, and
preemption introduces the context switch.
• In addition to the context switch, preemption also involves activities such
as processing interrupts, manipulating task queues, etc.
• This cost is significantly high if the system uses caches in single- or multilevels—and cache memory is used in almost all systems today.
220
SCHEDULING
CPU Scheduling…
• Since timely execution of these tasks is of paramount importance,
the real-time CPU scheduler must make sure that the tasks meet
their deadlines.
• Schedulability analysis is a fundamental aspect of real-time
scheduling. That is, checking whether a set of given tasks can be
executed in the system without missing the deadlines is crucial for
many life critical systems before the tasks are actually scheduled in
the system.
• A set of tasks is said to be schedulable if enough CPU time is
available to execute all these tasks before their deadlines.
• For this reason, scheduling in real-time systems is not the same as
scheduling in traditional operating systems.
221
SCHEDULING
CPU Scheduling…
• Each real-time task is assigned a priority and a deadline. Also, most
real-time tasks are executed periodically. Sometimes, execution
priorities are derived from deadlines and/or periods.
• Most real-time scheduling algorithms are “priority-based
preemptive scheduling”. This scheme allows only the highest
priority task among the ready tasks to run at any moment. When a
task with priority higher than currently running task becomes ready,
then the current task is preempted and the new higher priority task
is allowed to run immediately.
• The crux of these classes of algorithms is how these task priorities
are determined and when. Accordingly, real-time scheduling
algorithms can be classified into two categories:
– fixed (static) priority algorithms and
222
– dynamic priority algorithms.
SCHEDULING
• Earlier studies on real-time scheduling assumed a simple but
powerful model in which tasks are assumed to be periodic.
• For example, a task is designed to read a temperature sensor value
in a plant every 50 seconds or scan a security area every l0 seconds.
• These tasks are activated periodically to complete their missions. If
a task's relative activation time (period) is not known then it is a
non-periodic task.
• If a non-periodic task is either soft or has no deadline then it is
called aperiodic task.
• A non-periodic task with a hard deadline is called sporadic task
(sporadic: recurring in scattered and irregular or unpredictable instances).
• We start with scheduling of periodic tasks.
223
SCHEDULING PERIODIC TASKS
224
SCHEDULING PERIODIC TASKS
Scheduling Periodic Tasks
• The periodic task model is the simplest but sufficient for many
applications.
• The following assumptions are made for this system:
1.
2.
3.
4.
5.
All tasks run periodically on a single CPU.
Deadlines are at the end of their period. That is, for a period p, the
deadlines are at p, 2p, 3p, ….
The tasks are independent.
The execution time for each task is fixed.
The context switch time is ignored.
• Liu and Layland introduced two real-time scheduling algorithms,
called rat monotonic (RM) (increasing) and earliest deadline first (EDF),
in 1973.
• RM is a fixed priority scheduling algorithm which assigns higher
priorities to tasks with shorter periods (Higher frequency).
225
SCHEDULING PERIODIC TASKS
Scheduling Periodic Tasks…
• RM is a fixed priority scheduling algorithm which assigns higher
priorities to tasks with shorter periods (Higher Frequency).
• EDF (Earliest Deadline First) is a dynamic priority scheduling
algorithm which assigns higher priorities to tasks with the current
earliest deadline.
• It is easy to see that RM and EDF are simple, and they are proved to
be optimal in their respective classes.
• >>
• RM and EDF algorithms are widely studied and extensively
analyzed.
• Surprisingly, almost all other algorithms proposed in literature later
are only variations of these two basic algorithms.
226
SCHEDULING PERIODIC TASKS
Scheduling Periodic Tasks…
• RM is used for most practical applications.
• The reasons for favouring RM over EDF are based on the beliefs that
– RM is easier to implement,
– introduces lesser runtime overhead,
– is easier to analyze,
– more predictable in overloaded conditions,
– and has lesser jitter in task execution; the variation in task
execution delays is called jitter.
• >> If jitter occurs, many undesirable consequences may result in the
system. So, reducing jitter is one objective of real-time scheduling.
227
SCHEDULING PERIODIC TASKS
Scheduling Periodic Tasks…
1. Priority Scheduling Algorithm.
– The objective of priority scheduling algorithms is simply that:
• at any time, the scheduler selects the highest priority ready task; and
• the selected task runs until either it completes its execution for that
period or another task with priority higher than it becomes ready for
execution.
– An implementation scheme for a priority scheduler is described as follows.
• The scheduler maintains essentially two queues: ready queue and wait
queue.
• The ready queue contains tasks which are ready to run and the wait
queue contains tasks that have already run and are waiting for their next
period to start again.
• The ready queue is ordered by task priority and the wait queue is ordered
by the earliest start time.
228
SCHEDULING PERIODIC TASKS
Scheduling Periodic Tasks…
1. Priority Scheduling Algorithm…
• When the scheduler is invoked, it examines tasks in the wait queue to see
if any task should be moved to the ready queue at that point of time.
• Then it compares the head task at the ready queue to currently running
task.
• If the priority of the head task is higher than that of the running task, then
the scheduler invokes a context switch.
• The scheduler is invoked by an interrupt from either an external event or
a timer.
• The start time of a task might trigger a timer interrupt.
• Other efficient implementations are possible.
229
230
SCHEDULING PERIODIC TASKS
Scheduling Periodic Tasks…
2. Rate Monotonic Scheduling Algorithm.
– The crux (a vital, basic, decisive, or pivotal point) of the RM scheduling
algorithm lies in the way the priorities are computed.
– RM computes priorities based on task periods.
– A task with a shorter period has higher priority. That is, the task
with the higher rate of occurrences has higher priority, hence the
name rate monotonic.
– Since the period of each task is fixed, once their priorities are
computed and assigned in advance, the priorities stay static.
– For the following discussion, we use the notation T(e,p) to
denote a task T with execution requirement of e time units and
period p time units.
231
SCHEDULING PERIODIC TASKS
Scheduling Periodic Tasks…
2. Rate Monotonic Scheduling Algorithm.
We use the notation T(e,p) to denote
a task T with execution requirement of
e time units and period p time units
– Consider three periodic tasks T1(1,4), T2(2,5), and T3(3,10), as shown in
Figure 15.1. ( T1(1,4) means: execution time = 1 Unit, Periodicity every four units of time. )
– The down arrow indicates both the ending of the previous period and starting
of the new period.
– Tasks are activated at every starting period. According to RM, T1 has the
highest rate of 1/4 and, therefore, has the highest priority; T2 has the next
highest rate of 1/5 and, therefore, has the next higher priority; and T3 has the
lowest rate of 1/10 and hence has the lowest priority. All three tasks are
ready for execution at time 0.
232
SCHEDULING PERIODIC TASKS
Scheduling Periodic Tasks…
2. Rate Monotonic Scheduling Algorithm.
tasks T1(1,4), T2(2,5), and T3(3,10)
• >> In fixed priority scheduling, task priorities are assumed to be fixed throughout
the execution, Dynamic priority scheduling computes the priorities during
runtime.
.
1
4
2
7
5
.
.
3
6
8
• At time 0, since T1 has the highest priority, it starts its execution
and completes at time 1.
• At time 1, T2, the currently highest priority ready task, can start its
233
execution and completes it at time 3.
SCHEDULING PERIODIC TASKS
Scheduling Periodic Tasks…
2. Rate Monotonic Scheduling Algorithm.
•
.
1
4
2
tasks T1(1,4), T2(2,5), and T3(3,10)
7
5
.
.
3
6
8
• Now, at time 3, T3 can start its execution, but at time 4 the highest priority task
T1 will be again ready and that will preempt T3, and run until time 5.
•
Since T2 arrives at time 5, T3 has to wait until T2 completes its execution at time 7.
• Now, T3 can have 1 unit of execution at time 7 before T1 arrives at time 8.
• Then after T1 finishes at time 9, T3 can complete its execution for the first period
at time 10.
• In this example, T3 is preempted twice in its first period, but eventually
234
completes its execution on time.
235
RATE MONOTONIC SCHEDULING ALGORITHM
• Consider another example (Example 2).
• Three periodic tasks are T1(2,4), T2(2,6), and T3(3,12), as shown if Figure 15.2.
1
2
2
3
• According to RM, T1 has the highest priority: T2 has the next highest priority; and
the task T3 has the lowest priority.
• All three tasks are ready for execution at time 0.
• Now, in the time interval 0 to 12, T1 must execute 3 times, T2 must execute 2
times, and T3 must execute 1 time.
• So we need 6 (3x2=6) + 4 (2x2=4) + 3 (3x1=3) = 13 units of execution time in 12
units of real time, which is not possible.
236
RATE MONOTONIC SCHEDULING ALGORITHM
• Consider another example (Example 2)…
• Three periodic tasks are T1(2,4), T2(2,6), and T3(3,12), as shown if Figure 15.2.
.
.
.
• Another related metric is utilization that is computed as the sum of execution
ratios of the tasks.
• That is, in the above example, utilization is 2/4+2/6+ 3/12 = 13/12.
• If the utilization is above 100 per cent, the tasks cannot be scheduled to meet
deadlines. This is a necessary condition in theory, but not a sufficient condition.
• Therefore, these three tasks are not schedulable and some task, naturally the
lowest priority task, cannot meet its deadline.
237
RATE MONOTONIC SCHEDULING ALGORITHM
• Consider another example (Example 2)…
• Three periodic tasks are T1(2,4), T2(2,6), and T3(3,12), as shown if Figure 15.2.
/2
4
6
12
/2
2
3
6
/3
1
3
3
1
1
1
LCM=
2x2x3 x1
x1
x1 =
12
• Having less than 100 per cent utilization does not imply that the task set is
schedulable. It has to be verified practically.
• For a given task set, the least common multiplier aka LCM of all the task periods is
called the hyperperiod of the task set.
• For the task set shown in Figure 15.2, the hyperperiod is 12.
• Since all tasks will have their start times simultaneously at the beginning of the
next hyperperiod, the schedule just repeats itself in each hyperperiod. Therefore,
it is enough to verify task schedulability for one hyperperiod.
238
239
RATE MONOTONIC SCHEDULING ALGORITHM
Example 3 (Task Utilisation < 100% but Task Set Not Schedulable)
• Three periodic tasks are T1(1,3), T2(1,4), and T3(2,5), as shown if Figure 15.3.
LCM
=
3
4
5
3
x4
x5 = 60
• According to RM T1 has the highest priority; T2 has the next highest priority; and
T3 has the lowest priority.
• All three tasks are ready for execution at time 0.
• The hyperperiod for Example Task Set 3, illustrated in Figure 15.3, is 60, and task
utilization 1/3 + 1/4 + 2/5 = 0.9833.
• Although the utilization is 98.33 per cent, which is less than 100 per cent, this task
set is not schedulable under RM.
240
RATE MONOTONIC SCHEDULING ALGORITHM
• Consider the following example (Example 3)…
• Three periodic tasks are T1(1,3), T2(1,4), and T3(2,5), as shown if Figure 15.3.
1
T1(1,3)
.
5
T2(1,4)
.
?
T3(2,5)
4
2
3
LCM
=
3
4
5
3
x4
x5 = 60
.
• Tasks T1 and T2 take time intervals 0-1 and 1-2, and task T3 the time
interval 2-3, then T1 and T2 again take time intervals 3-4 and 4-5,
respectively.
• Now, T3, having executed for only 1 unit of time, misses its deadline
(it has to complete execution for 2 units of time before time 5) for
the first period.
241
SCHEDULING
Processor Utilisation Under RM Algorithm
• >>
• Processor utilization (U) for any feasible schedule under RM
generally decreases as the number of tasks (n) increases
U = n (21/n - 1)
• When the number of tasks increases, the CPU utilization reaches to
about 69 per cent.
• The theoretical limit of 69 per cent indicates that RM could waste as
much as about 31 per cent of CPU time.
• The next algorithm could bring down the CPU wastage time close to
0 percent.
242
243
SCHEDULING
Scheduling Periodic Tasks…
T1(1,3), T2(1,4), and T3(2,5)
3. Earliest-Deadline-First Scheduling Algorithm.
• The purpose of EDF is to assign priorities to tasks dynamically,
based on the current order of their deadlines.
• The highest-priority task is the one whose deadline is earliest.
• Clearly, the priorities must be recalculated at every scheduling
point.
• Similar to RM, at any moment, the highest priority task is executed,
but the priority of the task changes over time.
• We have shown that Example Task Set 3 is not schedulable under
RM.
• This task set is schedulable under EDF as shown below.
244
EXAMPLE: TASK SET UNSCHEDULABLE UNDER RM
• Non schedulable under RM…
• Three periodic tasks are T1(1,3), T2(1,4), and T3(2,5), as shown if Figure 15.3.
1
4
2
3
.
5
.
?
.
LCM
=
3
4
5
3
x4
x5 = 60
• The hyperperiod for Example Task Set 3, illustrated in Figure 15.3, is 60, and task
utilization 1/3 + 1/4 + 1/5 = 0.9833. Although the utilization is 98.33 per cent,
which is less than 100 per cent, this task set is not schedulable under RM.
• Tasks T1 and T2 take time intervals 0-1 and 1-2, and task T3 the time interval 2-3,
then T1 and T2 take again take time intervals 3-4 and 4-5, respectively.
• Now, T3, having executed for only 1 unit of time, misses its deadline (it has to
complete execution for 2 units of time before time 5) for the first period. 245
SCHEDULING
T1(1,3), T2(1,4), and T3(2,5)
3. Earliest-Deadline-First Scheduling Algorithm…
• This task set is NOT schedulable under RM as shown below.
1
4
2
3
.
5
.
?
.
• We shall now consider this task set with EDF.
• At any point of time, EDF schedules the task with the earliest
deadline.
• When two or more tasks have the same deadline, one task is
chosen randomly for scheduling.
• The hyperperiod (i.e., the LCM of 3, 4, and 5) for this example is24660.
247
SCHEDULING
T1(1,3), T2(1,4), and T3(2,5)
3. Earliest-Deadline-First Scheduling Algorithm…
• This task set is schedulable under EDF as shown below.
• Deadlines: Each task must finish within its period (last time unit must
start before next period).
• T1 has deadlines at 2 (3-1=2), 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35,
38, 41, 44, 47, 50, 53, 56, 59
• T2 has deadlines at 3 (4-1=3), 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47,
51, 55, 59
• T3 has deadlines at 4 (5-1=4), 9, 14, 19, 24, 29, 34, 39, 44, 49, 54, 59 248
SCHEDULING
T1(1,3), T2(1,4), and T3(2,5)
3. Earliest-Deadline-First Scheduling Algorithm…
• This task set is schedulable under EDF as shown below.
• T1 has deadlines at 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41,
44, 47, 50, 53, 56, 59
• T2 has deadlines at 3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59
• T3 has deadlines at 4, 9, 14, 19, 24, 29, 34, 39, 44, 49, 54, 59
• We use the notation S(T,t,d) to denote a task T that is Scheduled at
time t for the duration of d time units.
249
•T1 has deadlines at 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59
•T2 has deadlines at 3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59
•T3 has deadlines at 4, 9, 14, 19, 24, 29, 34, 39, 44, 49, 54, 59
.
Earliest-Deadline-First
Scheduling Algorithm…
T1(1,3), T2(1,4), and T3(2,5)
1
4
6
8
1
1
1
• This task
set is5 schedulable
under1 EDF1 as shown below.
9
2
1
3
7
10
10
2
• We use the notation S(T,t,d) to denote a task T that is Scheduled at time t for the
duration of d time units.
Deadline (DL)-2
3
4
5
7
8
250
•T1 has deadlines at 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59
•T2 has deadlines at 3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59
•T3 has deadlines at 4, 9, 14, 19, 24, 29, 34, 39, 44, 49, 54, 59
.
Earliest-Deadline-First
Scheduling Algorithm…
1
4
T1(1,3), T2(1,4), and T3(2,5)
6
8
1
1
1
• This task
set is5 schedulable
under1 EDF1 as shown below.
9
2
1
3
7
10
10
2
• We use the notation S(T,t,d) to denote a task T that is Scheduled at time t for the
duration of d time units.
DL-9
11
11
14
14
15
251
•T1 has deadlines at 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59
•T2 has deadlines at 3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51, 55, 59
•T3 has deadlines at 4, 9, 14, 19, 24, 29, 34, 39, 44, 49, 54, 59
.
Earliest-Deadline-First
Scheduling Algorithm…
1
4
T1(1,3), T2(1,4), and T3(2,5)
6
8
1
1
1
• This task
set is5 schedulable
under1 EDF1 as shown below.
9
2
1
3
7
10
10
2
• We use the notation S(T,t,d) to denote a task T that is Scheduled at time t for the
duration of d time units.
252
253
SCHEDULING
T1(1,3), T2(3,5)
3. Earliest-Deadline-First Scheduling Algorithm…
• Consider the next example for further comparison between RM and EDF.
• Two periodic tasks are T1(1,3) and T2(3,5).
• According to RM, T1 has higher priority than T2.
• The priorities change over time in EDF.
• Processor Utilisation:
U = 1/3 + 3/5 = 14/15 < 1
254
S(T,t,d) to denote a task T that is Scheduled at time t
for the duration of d time units.
SCHEDULING
T1(1,3), T2(3,5)
3. Earliest-Deadline-First Scheduling Algorithm…
• Consider the next example for further comparison between RM and EDF.
Periodicity T1: 0,3,6,9,12,…
• Two periodic tasks are T1(1,3) and T2(3,5).
Deadlines T1: 3,6,9,12,…
1
1
1
1
2
1
1
2
1
2
1
RM
Periodicity T2: 0,5,10,15,…
Deadlines T2: 5,10,15,…
1
3
->
1
2
1
1
EDF
• In RM, the schedule would be:
S(T1,0,1), S(T2,1,2), S(T1,3,1), S(T2,4,1), S(T2,5,1), S(T1,6,1),
S(T2,7,2), S(T1,9,1), S(T2,10,2), S(T1,12,1), S(T2,13,1), …
• In EDF, at time 0, the priority of T1 is higher than that of T2. The scheduler runs T1
in interval 0-1, runs T2 in interval 1-3. At this point T1 comes back. Since task T1
at this time has a deadline (at time 6) that is later than the deadline of task255
T2 (at
time 5), it would be more appropriate to continue T2.
S(T,t,d) to denote a task T that is Scheduled at time t
SCHEDULING
for the duration of d time
units.
T1(1,3), T2(3,5)
3. Earliest-Deadline-First Scheduling Algorithm…
• In addition, this would reduce one preemption.
Periodicity T1:
• So the schedule for EDF would be:
Deadlines T1:
1
1
1
1
2
1
1
2
1
2
1
0,3,6,9,12,…
3,6,9,12,…
Periodicity T2: 0,5,10,15,…
Deadlines T2: 5,10,15,…
1
3
->
1
2
1
1
1
1
1
1
2
3
• EDF. S(T1,0,1), S(T2,1,3), S(T1,4,1), S(T2,5,1), S(T1,6,1), S(T2,7,2),
S(T1,9,1), S(T2,10,3), S(T1,13,1), …
• The schedules are depicted in Figure 15.4, and we can see that the
time interval 14-15 is free and the schedule will repeat itself
starting from time 15, the beginning of the next hyperperiod. 256
SCHEDULING
RM vs EDF
• Traditionally RM is considered favourable over EDF.
• Recently, the validity of some of these acclaimed attractive
properties of RM have been questioned.
• In addition, it is observed that most of the advantages of RM over
EDF considered in literature are either very slim or incorrect when
the algorithms are compared with respect to their development
from scratch rather than developing on the top of a generic priority
based kernel.
• Some recent operating systems provide such support for the
development of user level schedulers.
257
SCHEDULING
RM vs EDF…
• One unattractive property of RM is that it experiences a large
number of preemptions compared to EDF and, therefore, introduces
high overhead. The undesirable preemption-related overhead may
cause
– higher processor overhead in real-time systems,
– high energy consumption in embedded systems, and
– may even make the task set unschedulable.
• In summary, it is clear that
– RM is simpler than EDF and
– RM experiences more preemptions than EDF.
• Now, the question is how to reduce the pre-emptions without
losing the simplicity of RM.
• The next algorithm is directed towards answering this question.
258
259
SCHEDULING
4. Activation Adjusted Scheduling Algorithm.
• Preemption of tasks occurs when a higher priority task is activated
during the execution of a lower priority task.
• Consequently, a lower priority task would experience more
preemptions as it stays longer in the ready queue.
• Therefore, to reduce preemptions, it is necessary to reduce the
lifetime of lower priority tasks waiting in the ready queue.
• One way to reduce the lifetime of lower priority tasks, if possible, is
to delay the activation of higher priority tasks. This would increase
the chance of lower priority tasks using the CPU as much as they
can and complete their executions quicker.
• The activation delays can be computed offline similar to computing
worst case response time and incorporated in the periods to arrive
at the “adjusted-activation” times.
260
SCHEDULING
4. Activation Adjusted Scheduling Algorithm…
• The actual computation of delay times is beyond the scope of this
discussion.
• Once the delays are computed offline and activation times are
adjusted, the remaining actions of the algorithm coincide with RM.
• This is the objective of the activation-adjusted scheduling
algorithm.
• We illustrate this idea using the following example.
• Three periodic tasks are T1(1,3), T2(3,9), and T3(2,12).
• According to RM, the priority order, from highest to lowest, is T1,
T2, and T3.
• This task set has hyperperiod 36 (LCM of 3,9,12=36).
261
SCHEDULING
T1(1,3), T2(3,9), and T3(2,12).
4. Activation Adjusted Scheduling Algorithm…
• The delay times computed for T1, T2 and T3 respectively are 2, 4,
and 0 (Only Higher priority tasks are to be delayed for execution).
• That is,
– task T1 can be activated at time 2, 5, 8, 11, … instead of at times
0, 3, 6, 9, …., (delayed by 2 time units) and
– T2 can be activated at times 4, 13, 22, 31, ... instead of at times
0, 9, 18, 27,… (delayed by 4 time units)
– There is no change in the activation time for task T3.
• Changes in activation times reduce the number of preemptions.
• We leave the analysis and computation of reduction in preemptions
for this example as an exercise.
• Next we look at some scheduling algorithm for the systems with
non periodic tasks.
262
T1(1,3), T2(3,9), and T3(2,12)
Hyperperiod = LCM of 3, 9, 12 = 36
Try Normal RM
• task T1 is activated at times 0, 3, 6, 9, ….,
• T2 can be activated at times 1, 10, 19, 28, ...
• T3 can be activated at 5, 14, 25, ….
and
1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
T
1
T
2
T
3
6 Preemptions
263
ADJUST ACTIVATION (START TIME)
T1(1,3), T2(3,9), and T3(2,12)
• task T1 can be activated at time 2, 5, 8, 11, … instead of at times 0, 3, 6, 9,
….,
(delayed by 2 time units) and
• T2 can be activated at times 4, 13, 22, 31, ... instead of at times 0, 9, 18, 27,…
(delayed by 4 time units)
• There is no change in the activation time for task T3: 0, 12, 24, 36, …..
1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
T
1
T
2
T
3
5 Preemptions
264
265
SCHEDULING APERIODIC AND SPORADIC TASKS
Scheduling Aperiodic and Sporadic Tasks
• A non-periodic task that is either soft* or has no deadline is called
an aperiodic task, and that which has a hard deadline is called a
sporadic task.
• These tasks are driven by asynchronous events.
• They could be driven by the environment in response to an external
event — or because of internal change of the system state.
• For example,
• an operator may want to read a specific value from the system or change to
manual drive for cruise (moving around slowly) control.
• Within the system an internal device might show some fault state requiring
operation mode change.
• Hard real-time systems must satisfy their timing and deadline constraints.
Otherwise, the system will fail.
• * On the other hand, soft real-time systems can accept missing some deadline
constraints as long as they achieve their mission.
266
SCHEDULING APERIODIC AND SPORADIC TASKS …
Scheduling Aperiodic and Sporadic Tasks…
• Consider a system that has periodic, aperiodic, and sporadic tasks.
• The ready tasks of each class are maintained in a separate queue.
• Assume that a periodic task scheduling algorithm is employed to
execute tasks from the periodic task queue.
• We will see how aperiodic and sporadic tasks are executed in this
environment.
• When a sporadic task becomes ready for execution, it is tested to
check whether the periodic tasks and other accepted sporadic tasks
can be completed without missing their deadlines.
• If so the new sporadic task is accepted. Otherwise, it is rejected
immediately.
267
SCHEDULING
Scheduling Aperiodic and Sporadic Tasks…
• Now the issue is how to schedule the accepted sporadic tasks.
• One of the simplest approaches to schedule the accepted sporadic
tasks is as follows.
• Transform the accepted sporadic tasks for the scheduling purpose at
that instance and then adapt the scheduler of the periodic tasks to
schedule these temporary periodic tasks along with regular periodic
tasks.
• Since aperiodic tasks can tolerate delayed execution, they need not
be rejected right away.
• The scheduler tries to complete the aperiodic tasks as soon as
possible without missing any deadline of the accepted sporadicand periodic tasks.
• There are many ways this can be achieved. Some are discussed in
268
next two subsections.
SCHEDULING
Scheduling Aperiodic and Sporadic Tasks…
1. Background Approach.
• This is the simplest approach in that it allows aperiodic tasks to run
only when periodic and sporadic task queues are empty.
• This approach produces the appropriate schedule, but the response
of aperiodic tasks may suffer unnecessary delay.
• Consider that RM is used for scheduling periodic tasks. An aperiodic
task T’ arrives for execution at time 96 which requires 3 units of
execution time.
• At that moment there are two periodic tasks T1(5,12) and T2(6,16)
that become ready for execution.
• The background approach will schedule T’ at time 107 (96+5+6=107)
after both T1 and T2 complete their executions.
269
BACKGROUND APPROACH
• There are Two periodic tasks T1(5,12) and T2(6,16) that
become ready for execution at time 96.
• T’ arrives for execution at time 96 which requires 3 units of
execution time.
• The background approach will schedule T’ at time 107
(96+5+6=107) after both T1 and T2 complete their
executions.
• Hyperperiod = LCM of 12 and 16 = 48
Time 48
Time 96
Time 144
T1
T2
T’
101 107
• 96+12 = 108. T1 can be delayed upto 108-5=103 or 96+16=112, T2 can be delayed upto
112-6=106.
270
• T’ can be started at 96 without causing any delay.
SCHEDULING
Scheduling Aperiodic and Sporadic Tasks…
1. Background Approach…
• Instead, T’ can be executed immediately at time 96 leaving enough
time for T1 and T2 to meet their deadlines.
• This would reduce the response time for T’ without causing any
deadline miss.
• Between T1 and T2, RM will schedule T1 first.
• So T2 can be delayed for a maximum of 10 units (that is, until at
time 106) so that it can run between 106 and 112 to meet the
deadline 112.
• In such a case, T1 can be delayed for 5 units (that is, until at time
101) so that it can run between 101 and 106, meeting the deadline
108.
271
SCHEDULING
Scheduling Aperiodic and Sporadic Tasks…
1. Background Approach…
• In the above example, tasks T1 and T2 can be delayed at least for 5
units of time without causing a deadline miss.
• The interval that each task can be delayed without causing deadline
miss is called the “slack time”.
• Slack time computation grows more involved as the number of
tasks increases.
• The algorithm which uses slack time to delay periodic- and sporadic
tasks and execute aperiodic tasks to shorten the response time is
called slack-stealing algorithm.
272
273
SCHEDULING
Scheduling Aperiodic and Sporadic Tasks…
2. Polling Approach.
• In this approach, a new task called periodic server with period p and
execution time e is created for the purpose of executing aperiodic
tasks.
• The periodic server behaves very similar to a periodic task for
scheduling purposes but is used only to execute aperiodic tasks.
• The simplest version of periodic server called “poller” or “polling
server” is invoked periodically to check (i.e., poll) the aperiodic task
queue.
• If the queue is empty, the polling server suspends itself
immediately and waits until the next polling period starts.
Otherwise, it executes aperiodic tasks for e time units or until the
aperiodic task queue becomes empty, whichever occurs sooner.
274
SCHEDULING
Scheduling Aperiodic and Sporadic Tasks…
2. Polling Approach…
• Here e is called the execution budget of the server and, for the
polling server, it is a fixed value. That is, it gets the same budget for
every polling period. The budget is the CPU time given to the
periodic server to execute aperiodic tasks.
• Based on the manner the budget value is changed—that is,
consumed and replenished—different periodic servers can be
constructed.
• In the case of the polling server, the budget is replenished at the
beginning of each polling period and is consumed for executing
aperiodic tasks.
• The unused budget is reset to 0 when the aperiodic task queue
becomes empty.
275
SCHEDULING
Scheduling Aperiodic and Sporadic Tasks…
2. Polling Approach…
• Consider a typical example of the polling server that has budget 10
when it starts its execution and finds the aperiodic task is empty.
Now, the budget is reset to 0 and its execution is suspended
immediately.
• Assume that, at this moment, an aperiodic task with execution
requirement 2 time units arrives at the aperiodic task queue.
• It has to wait for the next polling period and that will increase its
response time.
• The response time of aperiodic tasks could be shortened if the
budget is preserved when the queue is empty and the periodic
server allowed to execute later in the period if any aperiodic task
arrives. The algorithm with this approach is called budget276
preserving or bandwidth-preserving server.
SCHEDULING
Scheduling Aperiodic and Sporadic Tasks…
Variations
• The main components of periodic servers are the budget
consumption- and budget replenishment rules.
• We list some basic consumption and replenishment rules.
• Replenishment Rules:
• R1: The execution budget of the server is set to e at the beginning of
each period.
• Consumption Rules:
• C1: The budget is consumed at the rate of one per unit time when time
server executes. The budget is reset to 0 when it suspends itself.
• C2: The budget is consumed at the rate of one per unit time when the
server executes.
277
278
SCHEDULING
Variations …
• The polling server uses R1 and C1.
• The periodic server based on rules R1 and C2 is called deferrable
server.
• The difference is that in deferrable servers the unconsumed budget
is preserved until the end of the period.
• Recall the previous example given for polling server.
• The periodic server is invoked when the new aperiodic task arrives
and it then executes the aperiodic task.
• This might delay lower priority periodic tasks for longer than usual.
• A new class of algorithms called sporadic servers solves this
problem by ensuring that each sporadic server with period p and
budget e never demands more processor time than a periodic task
with the same period and execution time in any time interval. 279
SCHEDULING
Variations …
•
•
•
•
•
•
•
•
This is achieved by suitable consumption and replenishment rules.
The discussion of sporadic servers is beyond our.
There are many variations to the deferrable server.
One interesting variation is combining background approach with
it. That is, allow the deferrable server to execute aperiodic tasks
when the periodic task queue is empty.
Such servers are called background servers.
Another variation is lowering its priority when it suspends its
execution before the budget is exhausted.
When aperiodic task is ready to use its budget, it exchanges its
priority with a lower priority task. In that case, the priority of the
server is lowered but maintains its remaining budget.
This algorithm is called priority exchange algorithm.
280
SCHEDULING
Variations …
• So far we have addressed the scheduling issues among the tasks
with different priorities.
• The immediate question relates to the tasks of same priority.
• For such cases, most real-time systems use either the round robin
(RR) scheduling or the FIFO scheduling strategy.
• The main objective of the above scheduling algorithms is meeting
deadlines.
• As embedded devices are becoming increasingly common, battery
life is considered a crucial factor and task scheduling indeed plays
important role in battery life.
• Next, we will briefly look at energy saving aspects of CPU
scheduling.
281
SCHEDULING
Scheduling Aperiodic and Sporadic Tasks…
• >>
• Real-time POSIX compliant operating systems must support fixed
priority scheduling with at least 32 priority levels.
• It can choose either RR or FIFO for scheduling within the same
priority level.
• In addition, some tasks may be scheduled according to FIFO while
others are scheduled using RR.
• In principle, it can support EDF and other dynamic priority
algorithms.
282
283
SECTION B
• Real Time and Embedded Operating Systems:
– Introduction,
– Hardware Elements,
– Structure
•
•
•
•
Interrupt Driven,
Nanokernel,
Microkernel and
Monolithic kernel based models.
– Scheduling:
• Periodic,
284
SECTION B
• Real Time and Embedded Operating Systems:
– Introduction,
– Hardware Elements,
– Structure
•
•
•
•
Interrupt Driven,
Nanokernel,
Microkernel and
Monolithic kernel based models.
– Scheduling:
• Periodic,
• Aperiodic
285
SECTION B
• Real Time and Embedded Operating Systems:
– Introduction,
– Hardware Elements,
– Structure
•
•
•
•
Interrupt Driven,
Nanokernel,
Microkernel and
Monolithic kernel based models.
– Scheduling:
• Periodic,
• Aperiodic
and
• Sporadic Tasks,
286
SECTION B
• Real Time and Embedded Operating Systems:
– Introduction,
– Hardware Elements,
– Structure
•
•
•
•
Interrupt Driven,
Nanokernel,
Microkernel and
Monolithic kernel based models.
– Scheduling:
• Periodic,
• Aperiodic
and
• Sporadic Tasks,
– Introduction to Energy Aware CPU Scheduling.
287
ENERGY AWARE CPU SCHEDULING
Energy Aware CPU Scheduling
• With the extensive use of portable, battery-powered devices such
as PDAs, mobile phones, camcorders, PDAs everywhere (that is, in
homes, offices, cars, factories, hospitals, aeroplanes, etc.),
minimizing power/energy consumption in these devices is
becoming increasingly important.
• Power consumption is broadly classified into static and dynamic
consumption types.
• Static power consumption occurs due to standby- and leakage
currents, and dynamic power consumption due to switching- or
operational activities in the device.
• Since static power consumption increases when the device is
operated below a critical power level, such increases can be avoided
by always operating the device above the critical power level.
288
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
Energy Aware CPU Scheduling…
• Hence, at the operating level, power reduction strategies mainly
refer to reduction in dynamic power consumption by using suitable
processor scheduling algorithms.
• Recent technologies allow the CPU to operate in a range of voltage
supply.
• In these systems, processor energy consumption can be reduced by
reducing CPU voltage.
• However, such reduction in power necessitates the processor to run
at a slower speed.
• The techniques mainly employed by task-scheduling algorithms to
reduce dynamic power consumption are processor shutdown and
processor slowdown.
289
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
Energy Aware CPU Scheduling…
• Thus, the crux of designing an energy-efficient scheduling strategy is
to decide when to apply shutdown and slowdown and for how long.
• Shutting down the system and later waking up the processor
consumes considerable power.
• Therefore, shutdown is applied only when the processor is idle for a
period longer than a threshold value, which varies from system to
system.
• Slowdown involves many factors and, therefore, depends on the
effectiveness of the estimation of slowdown based on these factors.
• Another way to save energy is to avoid or reduce preemptions
whenever possible.
• Task preemption is an energy expensive activity.
290
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
Energy Aware CPU Scheduling…
• Task preemption is an energy expensive activity.
• Preemption introduces an immediate context switch and that
consumes energy.
• Context switch cost is significantly high if the system uses multiple
cache memories.
• A scheduling policy has greater influence on the lifetime of tasks in
the system.
• An increased lifetime of a task has direct impact on the number of
preemptions.
• Also, since all the necessary resources are generally active during
the lifetime of a task, the increased lifetime of the task leads to
increased energy consumption in the overall system.
291
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
Energy Aware CPU Scheduling…
• Hence, reducing the number of preemptions and average lifetime of
tasks would significantly reduce the energy consumption in the
overall system.
• The primary objective in this context is to reduce these two energyexpensive activities considerably to save energy.
• Accelerated-completion and delayed-preemption are two
preemption control techniques.
• The accelerated-completion technique tries to avoid preemptions
by adjusting the voltage/clock speed to higher than the lowest
possible values.
• The limitation in this algorithm is that it requires knowledge of the
task execution profile.
292
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
Energy Aware CPU Scheduling…
• The delayed-preemption technique tries to avoid preemptions by
delaying higher-priority tasks if a lower priority task is currently
running.
• This requires computing the slack and voltage/clock speed of the
interrupting task at each preemption point, which increases the
scheduler complexity and running time overhead.
• >> Although a context switch takes only a few microseconds, the
effective time- and energy overhead of a context switch is generally
high due to activities such as cache management, Translation Lookaside Buffers management, etc.
293
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
Energy Aware CPU Scheduling…
• Many energy savings techniques for fixed priority scheduling have
been studied recently.
• They all essentially involve dynamically changing the speed of the
processor by varying the clock frequency with the supply voltage.
• This is called dynamic voltage scaling technique.
• By changing the speed of the processor, the execution times of the
tasks can be increased or decreased.
• Decreasing speed has the danger of missing deadlines.
• Therefore, dynamic voltage scaling has to be incorporated into the
scheduling algorithm carefully without violating the timing
constraints of the applications.
• The aim is to adjust the voltage or to perform a shutdown based on
the current state.
294
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
Energy Aware CPU Scheduling…
• The simplest algorithm for the static priority is as follows.
• If the ready queue is empty and the upcoming idle time is greater
than the threshold value, then enter the processor into the
shutdown mode.
• A higher level description of an algorithm called low-energy earliest
deadline first (LEDF) for EDF, which uses the basic voltage scaling
technique, is given next.
295
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
Energy Aware CPU Scheduling…
LEDF()
{
while (ready queue is not empty)
{ Sort deadlines in ascending order;
Schedule task with earliest deadline;
If deadline can be met with lower speed, schedule at that speed;
If deadline can be met only with higher speed, schedule at that speed;
}
}
296
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
Energy Aware CPU Scheduling…
• In summary, the following techniques are used to design energyefficient scheduling algorithms:
1. operate the processor above critical speed;
2. slow down processor speed whenever idle time is expected
due to early completion of the task;
3. shutdown the processor for a sufficient period;
4. avoid preemption whenever possible.
297
298
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
• >> Suppose a task A is responsible for updating the values of wheeland wind
• 15.7 Task Synchronization We have seen that the CPU is a resource
shared by many tasks, but one 1 1 time. Like the CPU, there are
many other resources in the system that ha‘-e D1 be shared over
time. However, unlike the CPU, some of these resotrzzs cannot be
taken away from a task at any arbitrary time. In real-time systems,
any actions based on inconsistent values are if unacceptable. In this
example, F is a shared resource that has to be accev P-429 In realtime systems, any actions based on inconsistent values are often
unacceptable. In this example, F is a shared resource that has to be
accessed exclusively. How to share such exclusive resources among
many competing tasks is a task synchronization problem. Many
synchronization problems and their solutions for general systems
299
are discussed in Chapter 7. In this section, we focus on only one
STRUCTURE OF REAL TIME AND EMBEDDED OPERATING SYSTEMS
• 15.7.1 Resource Sharing and Priority Inversion Problem The solution
to priority inversion problems is to collectively deal with CPL‘
scheduling and resource scheduling. The simplest solution to the
priorit§ inversion problem is to disable interrupts during the access to
a shared resource. That is, CPU scheduling is disabled when a shared
resource is allocated. This solution has not been generally supported
for obvious reasons. The next simplest solution is by Mok (proposed
in his PhD thesis in 1983) called non-preenzprive critical section
(NPCS) protocol. The idea is P-431
• >> Although several people claimed the invention of priority
inversion problem, the problem was clearly defined by Lampson and
Redell in 1980. that when a task gets a shared resource its priority is
raised to the highest level (highest priority of all tasks in the system).
The advantage of NPCS protocol is its simplicity, as it does not require
the knowledge of the number of resources and requirements of
300
resources of the tasks. The obvious dis- advantage is that it blocks
all