Transcript Real-Time Kernels - Computer Science & Engineering

HW/SW Interface
Operating Systems Design and
Implementation
Foreground/Background
Systems
• Often referred to as super-loops
ISR
Infinite loop
calling modules
ISR
Interruption
occurred
Background
(task level)
Foreground
(interrupt level)
Handle
Asynchronous
Events
ISR
Interrupt Service Routines
• Handle critical operations
– can take longer than they should
– make data available for background
routines
• processing of such information is referred to
task-level response
Example: EFI System
(Electronic Fuel Injection)
• What are the components?
Air-flow meter
Injectors
Water temperature sensor
ECU
O2 sensor
Distributor sensors
High pressure fuel pump
manifold sensor
EFI System
• How does it work?
– fundamentally, it manages three
necessities to start and maintain operation
of a gasoline engine
• fuel
• spark
• air
EFI System
• What happen to the EFI system when
you start a car?
• What happen to the EFI system when
you drive a car?
Dissecting EFI System
• Tasks
• ISRs
EFI System
• Critical section (atomic or indivisible)
– any possible critical regions in our tasks?
• Mutual exclusion?
• Reentrant code?
– functions can be used by multiple tasks
without causing data corruption
• Priority inversion problem?
Priority Inversion
• Assume task 3 has lower priority than
task 1.
– Task 1 is doing I/O so Task 3 gets to run
– Task 3 is in the middle of accessing a
shared resource (obtain semaphore)
– Task 1 finishes so it preempts Task 3
– Task 1 wants to access the same resource
but can’t since Task 3 has the semaphore
Priority Inversion
• In this scenario, the priority of Task 1 is
reduced to that of Task 3.
• What is a good solution?
Priority Inheritance
Priority Inversion
• Priority Inheritance
– Task 1 is doing I/O so Task 3 gets to run
– Task 3 is in the middle of accessing a shared
resource (obtain semaphore)
– Task 1 finishes so it preempts Task 3
– Task 1 wants to access the same resource but
can’t since Task 3 has the semaphore; thus the
kernel raises the priority of Task 3 to the same as
Task 1
– Task 3 gets to finish and releases the resource.
The priority is reset to the original value
– Task 1 is selected if it still has the highest priority
Assigning Task Priority
• Rate monotonic scheduling
– tasks with the highest rate of execution are given
the highest priority
• Assume all tasks are periodic
• Tasks do not synchronize with another, share resources,
and exchange data
• Preemptive scheduling is used
1
Ei
 T  n(2 n 1)
i
i
Assigning Task Priority
Number of Tasks
1
2
3
4
5
…
-
n(21/n - 1)
1
0.82
0.77
0.75
0.74
0.69
Providing Mutual Exclusion
• Disabling interrupt
• Test and Set operation
– hardware support (TSL operation)
• Disabling scheduler
• Semaphores
– how is semaphore implemented?
Disabling Interrupt
• X86
– CLI (disable interrupt)
– STI (enable interrupt)
Busy Waiting
Busy Waiting
Semaphore
• Is a type that has a counter and a delay
queue
– require OS support as processes in the
delay queue are blocked
– implementation often requires other
primitive support (disabling interrupt, etc.)
Semaphore
Procedure DOWN( S : semaphore):
Downb(mutex)
S := S - 1
If (S < 0) then
up b(mutex)
downb(delay)
endif
up b(mutex)
end DOWN
procedure UP( S : semaphore):
downb(mutex)
S := S + 1
if (S  0) then
up b(delay)
else
up b(mutex)
endif
end UP
assumes the existence of binary semaphore operations
upb and downb implemented with a test-and-set
instruction and busy waiting
Intertask Communication
• Message mailbox
• Message queues
– often use to process interrupt
Interrupts
• A hardware mechanism used to notify the
CPU that asynchronous events have
occurred
• Upon completion, the programs return to:
– background for a foreground/background system
– the interrupted task for non-premptive kernel
– the higest priority task ready to run for premptive
kernel
Example: Interrupt in NIOS
IE bit to enabling interrupt
IPRI bits for priority
MISC bits for interrupt control
Source of Exceptions (NIOS)
• External Hardware interrupt Sources
– External logic for producing the 6-bits interrupt
number & asserting the IRQ input pin is automatically
generated by the SOPC builder and is included in the
Peripheral Bus Module (PBM).
• Internal Exception Sources
– 2 sources of internal exceptions
• Register window-overflow, Register window-underflow
• Direct Software Exceptions
– Software can request that control be transferred to an
exception handler by issuing a TRAP instruction.
External Hardware Interrupts
• Active-high interrupt signal: irq
– Level sensitive
– Sampled synchronously at the rising edge of Nios clock
– Should stay asserted until the interrupt is acknowledged
by software
• 6-bit Input Interrupt Number:
irq_number[5:0]
– Identifies the highest priority interrupt currently
requested
• Highest priority = 0
• Lowest priority = 63
(irq #0 to #15 are reserved)
External Hardware Interrupts
• Nios will process the indicated
exception if
– IE= 1 – i.e. external interrupts & internal
exceptions are enabled, AND
– The interrupt number is smaller (lower or
equal) than the IPRI field value
Internal Hardware Interrupts
Interrupt Service Routine
Handler
nr_installuserisr( int trapNumber,
void *ISRProcedure,
int context)
trapNumber is the exception number to be associated with a
service routine
ISRProcedure is a routine which has a prototype of
typedef void (*Nios_isrhandlerproc) (int context);
context is a value that will be passed to the routine specified by
isrProcedure
ISR Handler
• This routine installs an interrupt service
routine for a specific exception number
• If nr_installuserisr() is used to set up the
exception handler, then the exception
handler can be an ordinary C routine
ISR
Process
Memory
Main Program
Restore
Context
ISR
Save
Context
• Interrupt occurs
• Current state is saved
(Context)
• ISR address is retrieved
from the vector table
based on the interrupt
number
• Jump to ISR routine
Runs to completion
Vector Table
• Context is restored
• Program resumes
ISR Implementation
Specify your # IRQ
Declare your IRQ
subroutines
ROM
instruction
Update the ISR
vector table
@irq_subroutine 0
…
@clock_adj_ISR
@RealTime_ISR
…
@irq_subroutine 63
Vector Table
stack
RAM
0xFFFF
…
0xFF0F
0xFF0E
…
0xFFC0
Write your IRQ
Subroutine
Interrupt Example
• UART (Universal Asynchronous
Receiver Transmitter)
– Transferring data between processor and
I/O devices
– Handle one 8-bit data at a time
• Transfer in parallel between UART and
Processor and in bit-serial between I/O device
and UART
JTAG UART
Used to provide a connection between a Nios II
processor and the host computer connected to
the DE 2 board
JTAG UART
• Data and control registers accessed by Nios
II as memory locations
# of char remaining in
the read FIFO
available space
in write FIFO
read valid
read/write data
from FIFOs
read/write/JTAG
pending
read/write
interrupt enable
JTAG UART
QuickTime™ and a
TIFF (Uncompressed) decompressor
are needed to see this picture.
JTAG UART
• Polling vs. Interrupt