Index
A
Abstraction layer, operating system, 421–442
FreeRTOS implementation, 430–436
multiplatform application, 436–440
object oriented interface, 423–436
Accessing I/O registers, 12–15
Acquiring images from camera device, 28–42
synchronous read from camera device, 29–34
Active to passive wait, 121–125
ADC. See Analog-to-digital converter
Address resolution protocol, 223
Adeos, Linux real-time extensions, 412–414
Adeos pipeline, Xenomai domains, 414
Aliasing phenomena, 478
Analog low-pass filter, 471, 479
Analog-to-digital converter, 89
Aperiodic tasks, response time, schedulability analysis, 324–330
API. See Application programming interface
Application programming interface, 4, 12, 23, 26–27, 159, 191, 412, 421
ARP. See Address resolution protocol
Asynchronous message passing, 155
Asynchronous message transfer, 146
B
Binary semaphores, FreeRTOS, 207–208, 388
mutual exclusion semaphores, 207–213
BIOS. See Basic input/output system
Bitmask, protection, 172
Blocked state, 73, 123, 139, 337
Blocking, task interactions, 333–360
immediate priority ceiling, task scheduling with, 357
priority ceiling protocol, 348–353
priority inheritance, task scheduling with, 356
priority inheritance protocol, 337–348
priority inversion problem, 334–337
schedulability analysis, 353–359
transitive priority inheritance, 346
unbounded priority inversion, 335
task scheduling with, 355
Blocking times, 358, 369, 371–372
Brinch Hansen monitor, 138
Butterworth filter, third-order, 473–475
C
Camera device, images from
data streaming from camera device, 37–42
Case study, vision control, 11–62
acquiring images from camera device, 28–42
synchronous read from camera device, 29–34
camera device, images from
data streaming from camera device, 37–42
circular shape
sample image, 56
code reduction, 47
device capability configuration parameters, 28
edge pixels, matrix from, 57
Hough transform, 54
image format definition, 28
input output on computers, 12–22
accessing I/O registers, 12–15
interrupt sequence, 19
interrupt vector number, 18–20, 24–25
input/output operations, 22–26
Linux input/output abstraction, 26–27
mask of devices to be monitored for exceptions, 33
memory mapped I/O, bus architecture for, 14
number of involved devices, 33
page table translation to map, 38
PCI buses, bus architecture with, 16
read device mask, 33
register allocation, 48
SCSI bus, bus architecture with, 16
separate I/O bus, bus architecture with, 13
static variable, sharing data via, 37
virtual address translation, 36
virtual memory address translation, 35
voting matrix from edge pixels, 57
wait timeout specification, 33
write device mask, 33
Choosing sampling frequency, 478
Circular buffers, 480
Circular shape
sample image, 56
Circular wait condition, 90
Code reduction, 47
analog-to-digital converter, 89
circular wait, 83
conditions, 83
defined, 83
hold and wait, 83
reusable resources, 80
FreeRTOS, interprocess communication primitives, 191–218
binary semaphores, 207–208, 388
main message-queue related primitives, 200
mutex semaphores, 207
relative vs. absolute time delays, 215
semaphore creation/deletion primitives, 208
semaphore manipulation primitives, 210
task-related primitives, 192
time-related primitives, 213
lock, wait-free communication, 239–262
concurrent read, write operations, opposite orders, 250
lock-free object, universal construction pseudocode, 260
lock-free solution C-like code, 252
memory management, faulty, race condition, object access, 258
overwriting, copying object during, 259
readers/writer problem, 251–254
retry loops, 241
sequential object implementation, into lock-free implementation, 256
universal constructions, 254–262
machine-dependent optimization
destination, 221
source, 221
network communication, 219–238
address resolution protocol, 223
distributed data, 219
Ethernet network frame, 224
frame splitting, 222
interframe gap, 221
packet length, 221
preamble, start frame identifier, 221
single point of failure, 219
transmission error management, 222
POSIX/Linux, interprocess communication primitives, 159–190
Linux, signal events defined in, 187
marge matrix summation execution time, 167
processes, interprocess communication among, 180–187
programming model, 189
protection bitmask, 172
real-time concurrent programming, 63–78
components, 68
multicore systems, 64, 312–313, 406
multiprocessor, 64, 108, 116, 242, 312, 362, 406
multiprogramming, 64–66, 69, 77, 105, 192, 216
process state components, 76
shared variables, interprocess communication, 103–140
active to passive wait, 121–125
Brinch Hansen monitor, 138
concurrently incrementing shared variable, 106
condition variables, 133, 138, 159, 175–177, 179–180, 189–190
difficulty of semaphore use, 131
hardware-assisted lock variables, 113–116
information hiding, 132
lock variables, 113
mutual exclusion, 130
passive wait, 124
Peterson’s software-based mutual exclusion, 117
POSIX approach, 137
process state diagram transitions, 127
race condition elimination, 136
semaphore to enforce mutual
exclusion, 128
software-based mutual exclusion, 116–121
sockets, TCP/IP sockets, 225–232
vision control, case study, 11–62
accessing I/O registers, 12–15
acquiring images from camera device, 28–42
code reduction, 47
data streaming from camera device, 37–42
device capability configuration parameters, 28
Hough transform, 54
image format definition, 28
input output on computers, 12–22
input/output operations, 22–26
interrupt sequence, 19
interrupt vector number, 18–20, 24–25
Linux input/output abstraction, 26–27
mask of devices to be monitored for exceptions, 33
memory mapped I/O, bus architecture for, 14
number of involved devices, 33
page table translation to map, 38
PCI buses, bus architecture with, 16
read device mask, 33
register allocation, 48
sample image, 56
separate I/O bus, bus architecture with, 13
static variable, sharing data via, 37
synchronous read from camera device, 29–34
virtual address translation, 36
virtual memory address translation, 35
voting matrix from edge pixels, 57
wait timeout specification, 33
write device mask, 33
Concurrent read, write operations, opposite orders, 250
Concurrently incrementing shared variable, 106
Condition synchronization, 130, 139–140
semaphores, 130
Condition variables, 133, 138, 159, 175–177, 179–180, 189–190
Consumable resource, 80
Context switch, FreeRTOS, task scheduler, 375–383
Control theory, digital signal processing, 443–484
digital low-pass filter, 462–483
aliasing phenomena, 478
Butterworth filter, third-order, 473–475
circular buffers, 480
Fourier transform, 462–466, 475
signal to noise ratio, 482–483
implementing transfer function, 455–461
multiple inputs, outputs, 461
system properties, transfer function, 452–455
transfer functions, Laplace domain, 450–452
zeroes, tank-pump system, 454
Copying object during overwriting, 259
Counting semaphores, 180, 207, 212, 388
mutual exclusion semaphores, 207–213
Critical instant theorem, self-suspension, 362–365
Cyclic executive, real-time scheduling, 265–278
scheduling task set, 271
task execution, 270
large execution time
splitting tasks with, 276
major, minor cycle length, 272–273
real-time scheduling
algorithms, 269
analysis methods, 268
schedule scheduling task set, small major cycle, 274
D
Daisy chain configuration, 18
Data buffer, 32
Data streaming from camera device, 37–42
Deadline monotonic priority assignment, schedulability analysis, 327
Deadline monotonic scheduling, schedulability analysis, 328
Deadlock, 4, 79–102, 131, 177, 348, 350–351
analog-to-digital converter, 89
circular wait, 83
conditions, 83
defined, 83
detection and recovery algorithm, 101
hold and wait, 83
graph, 84
reusable resources, 80
Degree of concurrency, 111
Device capability configuration parameters, 28
Digital low-pass filter, 462–483
aliasing phenomena, 478
Butterworth filter, third-order, 473–475
circular buffers, 480
third-order Butterworth filter, 475
signal to noise ratio, 482–483
Digital signal processing, control theory, 443–484
digital low-pass filter, 462–483
aliasing phenomena, 478
Butterworth filter, third-order, 473–475
circular buffers, 480
Fourier transform, 462–466, 475
signal to noise ratio, 482–483
implementing transfer function, 455–461
multiple inputs, outputs, 461
system properties, transfer function, 452–455
transfer functions, Laplace domain, 450–452
zeroes, tank-pump system, 454
Dimension of buffer, 32
Direct blocking, 340–341, 347, 365, 367
Direct vs. indirect naming scheme, 143
Distributed data, 219
DM. See Deadline monotonic
Dual-kernel approach, Linux real-time extensions, 412–419
E
Earliest deadline first, 6, 279, 283, 292, 295, 308, 330, 417
EDF. See Earliest deadline first
Edge pixels, matrix from, 57
Ethernet network frame, 224
Extended rendezvous, 148
Extra interference, 363–364, 370, 372
F
First in first out, 80, 168–169, 183, 202, 281, 403, 417
Fixed, variable task priority, 280–283
general purpose operating systems, 281–283
third-order Butterworth filter, 475
Frame splitting, 222
context switch, task scheduler, 375–383
datstructure, 385
message queue, 386
new architecture, porting FreeRTOS to, 389–400
stack layout during FreeRTOS context switch, ARM cortex-M3 architecture, 395
synchronization primitives, 383–389
task control block, 378
xQUEUE fields with different meaning, 388
interprocess communication primitives, 191–218
absolute time delays, 215
binary semaphores, 207–208, 388
main message-queue related primitives, 200
mutex semaphores, 207
mutual exclusion semaphores, 207–213
relative vs. absolute time delays, 215
semaphore creation/deletion primitives, 208
semaphore manipulation primitives, 210
task-related primitives, 192
time-related primitives, 213
operating system abstraction layer, 430–436
Full priority inheritance, 419
G
GNU General Public License, 192
H
Hardware-assisted lock variables, 113–116
Hold and wait condition, 88, 132
Hough transform, 54
I
Image format definition, 28
Immediate priority ceiling, task scheduling with, task interactions, blocking, 357
Input output on computers, 12–22
accessing I/O registers, 12–15
interrupt sequence, 19
interrupt vector number, 18–20, 24–25
Input/output operations, 22–26
Linux input/output abstraction, 26–27
Interframe gap, 221
Internal structure, FreeRTOS, 375–400
context switch, task scheduler, 375–383
message queue, 386
datstructure, 385
new architecture, porting FreeRTOS to, 389–400
stack layout during FreeRTOS context switch, ARM cortex-M3 architecture, 395
synchronization primitives, 383–389
task control block, 378
xQUEUE fields with different meaning, 388
Interprocess communication, shared variables, 103–140
active to passive wait, 121–125
Brinch Hansen monitor, 138
concurrently incrementing shared variable, 106
condition synchronization semaphores, 130
condition variables, 133, 138, 159, 175–177, 179–180, 189–190
hardware-assisted lock variables, 113–116
lock variables, 113
difficulty of semaphore use, 131
information hiding, 132
mutual exclusion, 130
passive wait, 124
Peterson’s software-based mutual exclusion, 117
POSIX approach, 137
process state diagram transitions, 127
race condition elimination, 136
semaphore primitives, 127
semaphore to enforce mutual exclusion, 128
software-based mutual exclusion, 116–121
Interprocess communication message passing, 141–158
asynchronous message passing, 155
asynchronous message transfer, 146
data representation, 152
direct vs. indirect naming scheme, 143
message structure, contents, 151–153
producer-consumer problem, message passing, 153–156
message transfer, 148
send primitive, 142
synchronization model, 145–150
synchronous message transfer, 147
Interrupt acknowledge cycle, 18–19, 24
Interrupt sequence, 19
Interrupt service routine, 17–20, 22, 24, 197, 392, 402, 406
Interrupt vector number, 18–20, 24–25
ISR. See Interrupt service routine
IVN. See Interrupt vector number
J
K
Kernel mode, 23–25, 37, 406–408
Kernel preemption, Linux real-time extensions, 406–409, 411
L
Lamport’s bakery algorithm, 121
Large execution time
splitting tasks with, 276
input/output abstraction, 26–27
operating system abstraction layer, 424–430
signal events defined in, 187
Linux/POSIX, interprocess communication primitives, 159–190
Linux, signal events defined in, 187
marge matrix summation execution time, 167
interprocess communication among, 180–187
programming model, 189
protection bitmask, 172
Linux real-time extensions, 401–420
adaptive priority ceiling, 419
kernel preemption, 406–409, 411
non-preemptible kernel sections, latency from, 408
PREEMPT_RT Linux patch, 409–412
rate monotonic scheduling, 417
real time application interface, 416–419
components, 418
layers, 417
round robin, 417
scheduling policies, 417
domains, Adeos pipeline, 414
layers, 415
implementing transfer function, 455–461
multiple inputs, outputs, 461
system properties, transfer function, 452–455
transfer functions, Laplace domain, 450–452
zeroes, tank-pump system, 454
Lock, wait-free communication, 239–262
concurrent read, write operations, opposite orders, 250
lock-free object, universal construction pseudocode, 260
memory management, faulty, race condition, object access, 258
overwriting, copying object during, 259
readers/writer problem, 251–254
lock-free solution C-like code, 252
retry loops, 241
sequential object implementation, into lock-free implementation, 256
universal constructions, 254–262
Lock-based synchronization protocol, 111
Lock variables, 113
M
Machine-dependent optimization, 48–49
destination, 221
source, 221
Main message-queue related primitives, FreeRTOS, 200
MAR. See Memory address register
Mask of devices to be monitored for exceptions, 33
Matrix from edge pixels, 57
Memory address register, 21
Memory management, faulty, race condition, object access, 258
Memory management unit, 76, 191, 405
Memory mapped I/O, bus architecture for, 14
Memory protection unit, 76, 193, 380
Message structure, contents, 151–153
MMU. See Memory management unit
difficulty of semaphore use, 131
information hiding, 132
MPU. See Memory protection unit
Multicore systems, parallelism, 64, 312–313, 406
Multiprocessor, parallelism, 64, 108, 116, 242, 312, 362, 406
Multiprogramming, parallelism, 64–66, 69, 77, 105, 192, 216
Multithreading, 1, 11, 63, 75–77
process state components, 76
Mutex semaphores, FreeRTOS, 207
Mutual exclusion, 130
Mutual exclusion semaphores, FreeRTOS, 207–213
N
Network communication, 219–238
address resolution protocol, 223
distributed data, 219
Ethernet network frame, 224
frame splitting, 222
interframe gap, 221
machine-dependent optimization
destination, 221
source, 221
packet length, 221
preamble, start frame identifier, 221
preamble and start frame identifier, 221
single point of failure, 219
transmission error management, 222
New architecture, porting FreeRTOS to, 389–400
Non-preemptible kernel sections, Linux real-time extensions, latency from, 408
Number of involved devices, 33
O
Open systems interconnection, 220
Operating system abstraction layer, 421–442
FreeRTOS implementation, 430–436
multiplatform application, 436–440
object oriented interface, 423–436
OSI. See Open systems interconnection
Overwriting, copying object during, 259
P
multicore systems, 64, 312–313, 406
multiprocessor, 64, 108, 116, 242, 312, 362, 406
multiprogramming, 64–66, 69, 77, 105, 192, 216
Passive wait, 71, 73–74, 103, 121, 124–125, 139
PCI buses, bus architecture with, 16
Peterson’s software-based mutual exclusion, 117
Poles, transfer function, tank-pump system, 454
Porting FreeRTOS to new architecture, 389–400
POSIX/Linux, interprocess communication primitives, 159–190
Linux, signal events defined in, 187
marge matrix summation execution time, 167
interprocess communication among, 180–187
programming model, 189
protection bitmask, 172
Preamble, start frame identifier, 221
Preemption, kernel, Linux real-time extensions, 411
PREEMPT_RT Linux patch, Linux real-time extensions, 409–412
Priority ceiling
Linux real-time extensions, 419
Priority ceiling protocol, task interactions, blocking, 348–353
Priority inheritance, task interactions, blocking, task scheduling with, 356
Priority inheritance protocol, task interactions, blocking, 337–348
Priority inversion problem, task interactions, blocking, 334–337
Privileged instructions, 23
components, 68
transitions, 127
interprocess communication among, 180–187
Processor, defined, 69
Producer-consumer problem, message passing, 153–156
Program, defined, 69
Programming model, 189
Protection bitmask, 172
Pseudo parallelism, 64
Push-through blocking, 340–342, 344, 346, 349, 357
Q
R
Race conditions, 103–112, 123, 133–137, 139, 179, 239, 257–259
Rate monotonic optimality, 283–291
earliest deadline first scheduler, 292
priority assignment, 284
proof of rate monotonic optimality, 285–291
Read device mask, 33
Real-time, task-based scheduling, 279–294
fixed, variable task priority, 280–283
general purpose operating systems, 281–283
rate monotonic optimality, 283–291
earliest deadline first scheduler, 292
priority assignment, 284
proof of rate monotonic optimality, 285–291
Real time application interface, 416
Linux real-time extensions, 416–419
components, 418
layers, 417
Real-time concurrent programming, 63–78
process state components, 76
multicore systems, 64, 312–313, 406
multiprocessor, 64, 108, 116, 242, 312, 362, 406
multiprogramming, 64–66, 69, 77, 105, 192, 216
components, 68
algorithms, 269
analysis methods, 268
major, minor cycle length, 272–273
scheduling task set, 271
task execution, 270
large execution time
splitting tasks with, 276
major, minor cycle length, 272–273
real-time, task-based scheduling, 279–294
fixed, variable task priority, 280–283
rate monotonic optimality, 283–291
response time analysis, schedulability analysis, 315–332
deadline monotonic priority assignment, 327
deadline monotonic scheduling, 328
worst-case execution time, computing, 321–324
schedule scheduling task set, small major cycle, 274
self-suspension, schedulability analysis, 361–372
critical instant theorem, self-suspension, 362–365
response time extension, 369–372
self-suspension, 363
task interaction, self-suspension, 365–369
task interactions, blocking, 333–360
immediate priority ceiling, task scheduling with, 357
priority ceiling protocol, 348–353
priority inheritance, task scheduling with, 356
priority inheritance protocol, 337–348
priority inversion problem, 334–337
schedulability analysis, 353–359
transitive priority inheritance, 346
unbounded priority inversion, 335
utilization, schedulability analysis, 295–314
overflow, sample task set, 309
processor utilization, 296–298
schedulability condition, 298
schedulability test, earliest deadline first, 306–311
sufficient schedulability test for rate monotonic, 298–306
Recursive mutex semaphores, 207
Register allocation, 48
Relative time delays vs. absolute time delays, FreeRTOS, interprocess communication primitives, 215
message transfer, 148
Resource allocation graph, 79, 84–86, 98
Response time analysis, 315, 354, 367
schedulability analysis, 315–332
deadline monotonic priority assignment, 327
deadline monotonic scheduling, 328
worst-case execution time, computing, 321–324
Response time extension, 369–372
Retry loops, 241
RM. See Rate monotonic
RTA. See Response time analysis
RTAI. See Real time application interface
S
Schedulability analysis
deadline monotonic priority assignment, 327
deadline monotonic scheduling, 328
worst-case execution time, computing, 321–324
overflow, sample task set, 309
processor utilization, 296–298
schedulability condition, 298
schedulability test, earliest deadline first, 306–311
sufficient schedulability test, rate monotonic, 298–306
Schedule scheduling task set, small major cycle, 274
Scheduling task set, cyclic executive, 271
SCSI bus, bus architecture with, 16
Self-suspension
schedulability analysis, 361–372
blocking, 365
critical instant theorem, self-suspension, 362–365
response time extension, 369–372
self-suspension, 363
task interaction, self-suspension, 365–369
Semaphore, to enforce mutual exclusion, 128
Semaphore creation/deletion primitives, FreeRTOS, 208
Semaphore manipulation primitives, FreeRTOS, interprocess communication primitives, 210
Semaphore primitives, 127
Send primitive, 142
Separate I/O bus, bus architecture with, 13
Sequential object implementation, into lock-free implementation, 256
Sequential process, parallelism, 64–65
Shared variables, interprocess communication, 103–140
active to passive wait, 121–125
Brinch Hansen monitor, 138
concurrently incrementing shared variable, 106
condition synchronization semaphores, 130
condition variables, 133, 138, 159, 175–177, 179–180, 189–190
hardware-assisted lock variables, 113–116
lock variables, 113
difficulty of semaphore use, 131
information hiding, 132
mutual exclusion, 130
passive wait, 124
Peterson’s software-based mutual exclusion, 117
POSIX approach, 137
process state diagram transitions, 127
race condition elimination, 136
semaphore primitives, 127
semaphore to enforce mutual exclusion, 128
software-based mutual exclusion, 116–121
Signal events defined in Linux, 187
Signal to noise ratio, 482–483
Single-input and single-output, 461
Single point of failure, 219
SISO systems. See Single-input and single-output
Software-based mutual exclusion, 116–121
Splitting tasks, large execution time, 276
Sporadic tasks, schedulability analysis, 324–330
Stack layout during FreeRTOS context switch, ARM cortex-M3 architecture, 395
Stack pointer, 76, 160, 162, 379–382, 395–398, 405–406, 417
Start frame identifier, 221
Static variable, sharing data via, 37
Sufficient schedulability test, rate monotonic, 298–306
Supervisor mode, 23
Synchronization, 141
Synchronization model, 145–150
Synchronization primitives, FreeRTOS, 383–389
Synchronization semaphores, 130, 133, 138, 212, 268
Synchronous message transfer, 147
T
implementing transfer function, 455–461
multiple inputs, outputs, 461
system properties, transfer function, 452–455
transfer functions, Laplace domain, 450–452
zeroes, tank-pump system, 454
Task control block, 375, 378–379
Task interactions, blocking, 333–360
immediate priority ceiling, task scheduling with, 357
priority ceiling protocol, 348–353
priority inheritance, task scheduling with, 356
priority inheritance protocol, 337–348
priority inversion problem, 334–337
schedulability analysis, 353–359
transitive priority inheritance, 346
unbounded priority inversion, 335
task scheduling with, 355
TCB. See Task control block
Third-order Butterworth filter, 473–475
FreeRTOS, interprocess communication primitives, 192–199
Throughput, 5, 13, 220, 266–267, 282, 322–323, 405, 479
Time-related primitives, FreeRTOS, interprocess communication primitives, 213
Transitive priority inheritance, task interactions, blocking, 346
Transmission error management, 222
U
Unbounded priority inversion, task interactions, blocking, 335, 355
Universal constructions, 254–262
Unsuitable process interleavings may produce incorrect results, 67
Utilization, schedulability analysis, 295–314
overflow, sample task set, 309
processor utilization, 296–298
schedulability condition, 298
schedulability test, earliest deadline first, 306–311
sufficient schedulability test for rate monotonic, 298–306
V
Virtual address translation, 36
address translation, 35
Vision control, case study, 11–62
acquiring images from camera device, 28–42
synchronous read from camera device, 29–34
camera device, images from
data streaming from camera device, 37–42
circular shape
sample image, 56
code reduction, 47
device capability configuration parameters, 28
edge pixels, matrix from, 57
Hough transform, 54
image format definition, 28
input output on computers, 12–22
accessing I/O registers, 12–15
interrupt sequence, 19
interrupt vector number, 18–20, 24–25
input/output operations, 22–26
Linux input/output abstraction, 26–27
mask of devices to be monitored for exceptions, 33
memory mapped I/O, bus architecture for, 14
number of involved devices, 33
page table translation to map, 38
PCI buses, bus architecture with, 16
read device mask, 33
register allocation, 48
SCSI bus, bus architecture with, 16
separate I/O bus, bus architecture with, 13
static variable, sharing data via, 37
virtual address translation, 36
virtual memory address translation, 35
voting matrix from edge pixels, 57
wait timeout specification, 33
write device mask, 33
von Neumann architecture, 104
Voting matrix from edge pixels, 57
vTaskDelay, vTaskDelayUntil, 215
vTaskDelayUntil, 215
W
Wait-free communication, 5, 239–241, 243, 245, 247, 249, 251, 253, 255, 257, 259, 261–262
concurrent read, write operations, opposite orders, 250
lock-free object, universal construction pseudocode, 260
memory management, faulty, race condition, object access, 258
overwriting, copying object during, 259
readers/writer problem, 251–254
lock-free solution C-like code, 252
retry loops, 241
sequential object implementation, into lock-free implementation, 256
universal constructions, 254–262
Wait timeout specification, 33
Word count register, 21
Worst-case blocking time, 199, 240, 341, 343–344, 347–348, 351–352, 354, 359, 361, 365, 368–370
Worst-case execution time, schedulability analysis, 321–324
Write device mask, 33
X
Xenomai, Linux real-time extensions, 414–416
domains, Adeos pipeline, 414
layers, 415
xQUEUE fields, different meaning, FreeRTOS, 388
Y
Z
Zeroes, poles, transfer function, tank-pump system, 454