COPE-05 Asynchronism.indd
5
Asynchronism
Uwe R. Zimmer – The Australian National University
Computer Organisation & Program Execution 2021
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 255 of 487 (chapter 5: “Asynchronism” up to page 340)
References for this chapter
[Patterson17]
David A. Patterson & John L. Hennessy
Computer Organization and Design – The Hardware/Software Interface
Chapter 4 “The Processor”,
Chapter 6 “Parallel Processors from Client to Cloud”
ARM edition, Morgan Kaufmann 2017
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 256 of 487 (chapter 5: “Asynchronism” up to page 340)
Why?
How do you handle your communication fl ow?
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 257 of 487 (chapter 5: “Asynchronism” up to page 340)
Why?
How do you handle your communication fl ow?
Do you have times when you check certain communication?
Is certain communication interrupting you? – at any time?
Do you assign “importance levels” to your
communication channels/sources?
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 258 of 487 (chapter 5: “Asynchronism” up to page 340)
STM32L476 Discovery
CPU
… running its sequence
of machine instructions.
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 259 of 487 (chapter 5: “Asynchronism” up to page 340)
STM32L476 Discovery
CPU
… running its sequence
of machine instructions.
How to interact with
all the other devices
inside the
MCU
?
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 260 of 487 (chapter 5: “Asynchronism” up to page 340)
STM32L476 Discovery
Current meter to MCU
60 nA … 50 mA
U R Zi Th
Headphone jack
USB OTG
Multiplexed 24 bit
RD-DAConverter with
stereo power amp
Microphone
“9 axis” motion sensor
(underneath display):
3 axis accelerometer
3 axis gyroscope
3 axis magnetometer
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 261 of 487 (chapter 5: “Asynchronism” up to page 340)
STM32L476 Discovery
LCD
Joystick
Reset
OTG LEDs
Power
Debugger
state
User LEDs
Over current
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 262 of 487 (chapter 5: “Asynchronism” up to page 340)
STM32L476 Discovery
CPU
… running its sequence
of machine instructions.
How to interact with
all the other devices
inside the
MCU
?
… and then with all the
devices on the board?
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 263 of 487 (chapter 5: “Asynchronism” up to page 340)
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 263 of y 487 (chapter 5: “Asynchronism” up to page 340)7
STM32L476 Discovery
CPU
… running its sequence
of machine instructions.
How to interact with
all the other devices
inside the
MCU
?
… and then with all the
devices on the board?
and then with the
rest of the world
… which is
connected to the board?
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 264 of 487 (chapter 5: “Asynchronism” up to page 340)
Polling
Sequential machine instructions
All external devices need to be “checked” by asking for their status.
This should usually happen (semi-) regularly.
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 265 of 487 (chapter 5: “Asynchronism” up to page 340)
Polling
Sequential machine instructions
All external devices need to be “checked” by asking for their status.
This should usually happen (semi-) regularly.
This will lead to a loop of polling requests.
Maximal latencies can be calculated straight forward.
Simplicity of design (with small number of devices).
Fastest option with small number of devices (like: one).
All devices will need to wait their turn
… even if this device is the only one with new data!
The “main” program transforms into one large loop which can
be hard to handle in terms of scalable program design.
Events or data can be missed.
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 266 of 487 (chapter 5: “Asynchronism” up to page 340)
Processor Architectures
Interrupts
• One or multiple lines wired
directly into the sequencer
Required for:
Pre-emptive scheduling, Timer driven actions,
Transient hardware interactions, …
Usually preceded by an external logic
(“interrupt controller”) which accumu-
lates and encodes all external requests.
On interrupt (if unmasked):
• CPU stops normal sequencer fl ow.
• Lookup of interrupt handler’s address
• Current IP and state pushed onto stack.
• IP set to interrupt handler.
ALU
M
e
m
o
ry
Sequencer
Decoder
Code management
Registers
IP
SP
Flags
Data management
Int.
© 2021 Uwe R. Zimmer, The Australian National University page 267 of 487 (chapter 5: “Asynchronism” up to page 340)Bahia Honda Rail Bridge (Creative Commons Attribution-ShareAlike 3.0, Photography by MrX at English Wikipedia)
We successfully interrupted
a sequence of operations …
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 268 of 487 (chapter 5: “Asynchronism” up to page 340)
Interrupt processing
Stack
Code
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
FP
Base
Program
Interrupt handler
………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………
PC
SP
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 269 of 487 (chapter 5: “Asynchronism” up to page 340)
Interrupt processing
Stack
Code
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
FP
Base
SP
…
Program
Interrupt handler
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
PC
………
………………
………
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 270 of 487 (chapter 5: “Asynchronism” up to page 340)
Interrupt processing
Stack
Code
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
Base
SP
Push registers
Declare local variables
Program
Interrupt handler
PC
Registers
Local
variables
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 271 of 487 (chapter 5: “Asynchronism” up to page 340)
Interrupt processing
Stack
Code
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
Base
SP
Push registers
Declare local variables
Run handler code
.. do some I/O ..
.. or run some time
critical code ..
Program
Interrupt handler
PC
Registers
Local
variables
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 272 of 487 (chapter 5: “Asynchronism” up to page 340)
Interrupt processing
Stack
Code
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
Base
SP
Push registers
Declare local variables
Run handler code
.. do some I/O ..
.. or run some time
critical code ..
Remove local variables
Program
Interrupt handler
PC
Registers
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 273 of 487 (chapter 5: “Asynchronism” up to page 340)
Interrupt processing
Stack
Code
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
FP
Base
SP
Push registers
Declare local variables
Run handler code
.. do some I/O ..
.. or run some time
critical code ..
Remove local variables
Pop registers
Program
Interrupt handler
PC
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 274 of 487 (chapter 5: “Asynchronism” up to page 340)
Interrupt processing
Stack
Code
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
FP
Base
SP
Push registers
Declare local variables
Run handler code
.. do some I/O ..
.. or run some time
critical code ..
Remove local variables
Pop registers
Program
Interrupt handler
PC
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
page 274 of 487
Bahia Honda Rail Bridge (Creative Commons Attribution-
ShareAlike 3.0, Photography by MrX at English Wikipedia)
© 2021 Uwe R. Zimmer, The Australian National University page 275 of 487 (chapter 5: “Asynchronism” up to page 340)Bahia Honda Rail Bridge (Creative Commons Attribution-ShareAlike 3.0, Photography by MrX at English Wikipedia)
We successfully interrupted
a sequence of operations …
… and now the trick to
get to the other side.
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 276 of 487 (chapter 5: “Asynchronism” up to page 340)
Interrupt processing
Stack
Code
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
FP
Base
Program
Interrupt handler
………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………
PC
SP
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 277 of 487 (chapter 5: “Asynchronism” up to page 340)
Interrupt processing
Stack
Code
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
FP
Base
SP
…
Program
Interrupt handler
………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………
PC
Flags
PC
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 278 of 487 (chapter 5: “Asynchronism” up to page 340)
Interrupt processing
Stack
Code
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
FP
Base
SP
…
Program
Interrupt handler
………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………
PC
Flags
PC
The CPU
hardware (!)
did that,
before anything
was changed
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 279 of 487 (chapter 5: “Asynchronism” up to page 340)
Interrupt processing
Stack
Code
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
Base
SP
Push registers
Declare local variables
Program
Interrupt handler
………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………
PC
Flags
PC
Registers
Local
variables
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 280 of 487 (chapter 5: “Asynchronism” up to page 340)
Interrupt processing
Stack
Code
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
Base
SP
Push registers
Declare local variables
Run handler code
.. do some I/O ..
.. or run some time
critical code ..
Program
Interrupt handler
………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………
PC
Flags
PC
Registers
Local
variables
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 281 of 487 (chapter 5: “Asynchronism” up to page 340)
Interrupt processing
Stack
Code
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
Base
SP
Push registers
Declare local variables
Run handler code
.. do some I/O ..
.. or run some time
critical code ..
Remove local variables
Program
Interrupt handler
………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………
PC
Flags
PC
Registers
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 282 of 487 (chapter 5: “Asynchronism” up to page 340)
Interrupt processing
Stack
Code
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
FP
Base
SP
Push registers
Declare local variables
Run handler code
.. do some I/O ..
.. or run some time
critical code ..
Remove local variables
Pop registers
Program
Interrupt handler
………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………
PC
Flags
PC
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 283 of 487 (chapter 5: “Asynchronism” up to page 340)
Interrupt processing
Stack
Code
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
FP
Base
SP
Push registers
Declare local variables
Run handler code
.. do some I/O ..
.. or run some time
critical code ..
Remove local variables
Pop registers
Return from interrupt
Program
Interrupt handler
………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………
PC
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 284 of 487 (chapter 5: “Asynchronism” up to page 340)
Interrupt processing
Stack
Code
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
FP
Base
Program
Interrupt handler
………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………
PC
SP
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 285 of 487 (chapter 5: “Asynchronism” up to page 340)
Interrupt processing
Stack
Code
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
FP
Base
…
Program
Interrupt handler
………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………
PC
Flags
PC
Scratch
registers
SP
LR is loaded with a special value
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 286 of 487 (chapter 5: “Asynchronism” up to page 340)
Interrupt processing
Stack
Code
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
Base
SP
Clear interrupt flag
(Adjust priorities)
(Re-enable interrupt)
Program
Interrupt handler
………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………
PC
Flags
PC
Scratch
registers
FP
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 287 of 487 (chapter 5: “Asynchronism” up to page 340)
Interrupt processing
Stack
Code
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
Base
SP
Clear interrupt flag
(Adjust priorities)
(Re-enable interrupt)
Push other registers
Declare local variables
Program
Interrupt handler
………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………
PC
Flags
PC
Registers
Local
variables
Scratch
registers
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 288 of 487 (chapter 5: “Asynchronism” up to page 340)
Interrupt processing
Stack
Code
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
Base
SP
Program
Interrupt handler
………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………
PC
Flags
Registers
Local
variables
Scratch
registers
Clear interrupt flag
(Adjust priorities)
(Re-enable interrupt)
Push other registers
Declare local variables
Run handler code
.. do some I/O ..
.. or run some time
critical code ..
PC
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 289 of 487 (chapter 5: “Asynchronism” up to page 340)
Interrupt processing
Stack
Code
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
Base
SP
Program
Interrupt handler
………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………
PC
Flags
Scratch
registers
Clear interrupt flag
(Adjust priorities)
(Re-enable interrupt)
Push other registers
Declare local variables
Run handler code
.. do some I/O ..
.. or run some time
critical code ..
Remove local variables
Pop other registersPC
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 290 of 487 (chapter 5: “Asynchronism” up to page 340)
Interrupt processing
Stack
Code
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
Base
SP
Program
Interrupt handler
………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………
PC
Flags
Scratch
registers
Clear interrupt flag
(Adjust priorities)
(Re-enable interrupt)
Push other registers
Declare local variables
Run handler code
.. do some I/O ..
.. or run some time
critical code ..
Remove local variables
Pop other registers
Return (“bx lr”)
PC
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 291 of 487 (chapter 5: “Asynchronism” up to page 340)
Interrupt processing
Stack
Code
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
Base
Program
Interrupt handler
………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………
Clear interrupt flag
(Adjust priorities)
(Re-enable interrupt)
Push other registers
Declare local variables
Run handler code
.. do some I/O ..
.. or run some time
critical code ..
Remove local variables
Pop other registers
Return (“bx lr”)
PC
SP
FP
………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………
………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 292 of 487 (chapter 5: “Asynchronism” up to page 340)
Interrupt handler
Things to consider
Interrupt handler code can be interrupted as well.
Are you allowing to interrupt an interrupt handler with an
interrupt on the same priority level (e.g. the same interrupt)?
Can you overrun a stack with interrupt handlers?
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 293 of 487 (chapter 5: “Asynchronism” up to page 340)
Interrupt handler
Things to consider
Interrupt handler code can be interrupted as well.
Are you allowing to interrupt an interrupt handler with an
interrupt on the same priority level (e.g. the same interrupt)?
Can you overrun a stack with interrupt handlers?
Can we have one of those? Busy!
Do Not Disturb!
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 294 of 487 (chapter 5: “Asynchronism” up to page 340)
Multiple programs
If we can execute interrupt handler code
“concurrently” to our “main” program:
Can we then also have multiple “main” programs?
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 295 of 487 (chapter 5: “Asynchronism” up to page 340)
Context switch
Code Stack StackCode kdC d k
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
FP
Base
Process 1
Dispatcher
………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………
PC
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
Base
PID SP
PCB
…
Process 2
………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………
… …
PC
Flags
Registers
Context-
switch-
variables
PID
PCB
… … …
SP
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 296 of 487 (chapter 5: “Asynchronism” up to page 340)
Context switch
Code Stack StackCode kdC d k
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
FP
Base
SP
…Process 1
Dispatcher
………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
Base
PID SP
PCB
…
Process 2
………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………
… …
PC
Flags
PID
PCB
… … …
PC
Flags
Registers
Context-
switch-
variables
PC
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 297 of 487 (chapter 5: “Asynchronism” up to page 340)
Context switch
Code Stack StackCode kdC d k
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
Base
SP
Push registers
Declare local variables
Process 1
Dispatcher
………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
Base
PID SP
PCB
…
Process 2
………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………
… …
PC
Flags
PID
PCB
… … …
PC
Flags
Registers
Context-
switch-
variables
PC
Registers
Context-
switch-
variables
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 298 of 487 (chapter 5: “Asynchronism” up to page 340)
Context switch
Code Stack StackCode kdC d k
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
Base
SP
Push registers
Declare local variables
Store SP to PCB 1
Process 1
Dispatcher
………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
Base
PID SP
PCB
…
Process 2
………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………
… …
PC
Flags
PID SP
PCB
… … …
PC
Flags
Registers
Context-
switch-
variables
PC
Registers
Context-
switch-
variables
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 299 of 487 (chapter 5: “Asynchronism” up to page 340)
Context switch
Code Stack StackCode kdC d k
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
Base
SP
Push registers
Declare local variables
Store SP to PCB 1
Scheduler
Process 1
Dispatcher
………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
Base
PID SP
PCB
…
Process 2
………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………
… …
PC
Flags
PID SP
PCB
… … …
PC
Flags
Registers
Context-
switch-
variables
PC
Registers
Context-
switch-
variables
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 300 of 487 (chapter 5: “Asynchronism” up to page 340)
Context switch
Code Stack StackCode kdC d k
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
Base
Push registers
Declare local variables
Store SP to PCB 1
Scheduler
Load SP from PCB 2
Process 1
Dispatcher
………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
Base
PID
PCB
…
Process 2
………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………
… …
PC
Flags
PID SP
PCB
… … …
PC
Flags
Registers
Context-
switch-
variables
PC
Registers
Context-
switch-
variables
SP
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 301 of 487 (chapter 5: “Asynchronism” up to page 340)
Context switch
Code Stack StackCode kdC d k
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
Base
Push registers
Declare local variables
Store SP to PCB 1
Scheduler
Load SP from PCB 2
Remove local variables
Process 1
Dispatcher
………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
Base
PID
PCB
…
Process 2
………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………
… …
PC
Flags
PID SP
PCB
… … …
PC
Flags
PC
Registers
Context-
switch-
variables
SP
Registers
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 302 of 487 (chapter 5: “Asynchronism” up to page 340)
Context switch
Code Stack StackCode kdC d k
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
Base
Push registers
Declare local variables
Store SP to PCB 1
Scheduler
Load SP from PCB 2
Remove local variables
Pop registers
Process 1
Dispatcher
………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
FP
Base
PID
PCB
…
Process 2
………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………
… …
PC
Flags
PID SP
PCB
… … …
PC
Flags
PC
Registers
Context-
switch-
variables
SP
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 303 of 487 (chapter 5: “Asynchronism” up to page 340)
Context switch
Code Stack StackCode kdC d k
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
Base
Push registers
Declare local variables
Store SP to PCB 1
Scheduler
Load SP from PCB 2
Remove local variables
Pop registers
Return from interrupt
Process 1
Dispatcher
………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………
Return address
Context
Parameters
Global variables
Local variables
Return address
Context
Parameters
Local variables
FP
Base
PID
PCB
…
Process 2
………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………………
………
………
………
………
… …
PC
Flags
PID SP
PCB
… … …
PC
Registers
Context-
switch-
variables
SP
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 304 of 487 (chapter 5: “Asynchronism” up to page 340)
Multi-tasking and Contention
Anything else could go wrong?
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 305 of 487 (chapter 5: “Asynchronism” up to page 340)
Multi-tasking and Contention
Anything else could go wrong?
If there is neither communication nor contention
between concurrent parts
… all is easy … and boring.
What happens if concurrent programs share data?
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 306 of 487 (chapter 5: “Asynchronism” up to page 340)
Shared variables
Atomic load & store operations
Assumption 1: every individual base memory cell (word) load and store access is atomic
Assumption 2: there is no atomic combined load-store access
task body P1 is
begin
G := 1
G := G + G;
end P1;
task body P2 is
begin
G := 2
G := G + G;
end P2;
task body P3 is
begin
G := 3
G := G + G;
end P3;
What is the value of G ?
G : Natural := 0; — assumed to be mapped on a 1-word cell in memory
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 307 of 487 (chapter 5: “Asynchronism” up to page 340)
Shared variables
Atomic load & store operations
Assumption 1: every individual base memory cell (word) load and store access is atomic
Assumption 2: there is no atomic combined load-store access
ldr r4, =G
mov r1, #1
str r1, [r4]
ldr r2, [r4]
ldr r3, [r4]
add r1, r2, r3
str r1, [r4]
ldr r4, =G
mov r1, #2
str r1, [r4]
ldr r2, [r4]
ldr r3, [r4]
add r1, r2, r3
str r1, [r4]
ldr r4, =G
mov r1, #3
str r1, [r4]
ldr r2, [r4]
ldr r3, [r4]
add r1, r2, r3
str r1, [r4]
What is the value in memory cell G after all three programs complete?
G: .word 0x00000000
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 308 of 487 (chapter 5: “Asynchronism” up to page 340)
Shared variables
This is terrible!
Nobody is their right mind would analyse a program like that.
… are we missing something?
… is there an elegant way out?
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 309 of 487 (chapter 5: “Asynchronism” up to page 340)
Mutual exclusion … or the lack thereof
task body Enter is
begin
for i := 1 .. 100 loop
Count := Count + 1;
end loop;
end Enter;
task body Leave is
begin
for i := 1 .. 100 loop
Count := Count – 1;
end loop;
end Leave;
Count : Integer := 0;
What is the value of Count after both programs complete?
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 310 of 487 (chapter 5: “Asynchronism” up to page 340)
Mutual exclusion … or the lack thereof
ldr r4, =Count
mov r1, #1
for_enter:
cmp r1, #100
bgt end_for_enter
ldr r2, [r4]
add r2, #1
str r2, [r4]
add r1, #1
b for_enter
end_for_enter:
ldr r4, =Count
mov r1, #1
for_leave:
cmp r1, #100
bgt end_for_leave
ldr r2, [r4]
sub r2, #1
str r2, [r4]
add r1, #1
b for_leave
end_for_leave:
Count: .word 0x00000000
What is the value at address Count after both programs complete?
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 311 of 487 (chapter 5: “Asynchronism” up to page 340)
Mutual exclusion … or the lack thereof
ldr r4, =Count
mov r1, #1
for_enter:
cmp r1, #100
bgt end_for_enter
ldr r2, [r4]
add r2, #1
str r2, [r4]
add r1, #1
b for_enter
end_for_enter:
ldr r4, =Count
mov r1, #1
for_leave:
cmp r1, #100
bgt end_for_leave
ldr r2, [r4]
sub r2, #1
str r2, [r4]
add r1, #1
b for_leave
end_for_leave:
Count: .word 0x00000000
What is the value at address Count after both programs complete?
Critical section Critical section
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 312 of 487 (chapter 5: “Asynchronism” up to page 340)
Mutual exclusion … or the lack thereof
ldr r4, =Count
mov r1, #1
for_enter:
cmp r1, #100
bgt end_for_enter
enter_critical_fail:
ldrex r2, [r4] ; tag [r4] as exclusive
add r2, #1
strex r0, r2, [r4] ; only if untouched
cmp r0, #0
bne enter_critical_fail
add r1, #1
b for_enter
end_for_enter:
ldr r4, =Count
mov r1, #1
for_leave:
cmp r1, #100
bgt end_for_leave
leave_critical_fail:
ldrex r2, [r4] ; tag [r4] as exclusive
sub r2, #1
strex r0, r2, [r4] ; only if untouched
cmp r0, #0
bne leave_critical_fail
add r1, #1
b for_leave
end_for_leave:
Count: .word 0x00000000
What is the value at address Count after both programs complete?
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 313 of 487 (chapter 5: “Asynchronism” up to page 340)
Mutual exclusion … or the lack thereof
ldr r4, =Count
mov r1, #1
for_enter:
cmp r1, #100
bgt end_for_enter
enter_critical_fail:
ldrex r2, [r4] ; tag [r4] as exclusive
add r2, #1
strex r0, r2, [r4] ; only if untouched
cmp r0, #0
bne enter_critical_fail
add r1, #1
b for_enter
end_for_enter:
ldr r4, =Count
mov r1, #1
for_leave:
cmp r1, #100
bgt end_for_leave
leave_critical_fail:
ldrex r2, [r4] ; tag [r4] as exclusive
sub r2, #1
strex r0, r2, [r4] ; only if untouched
cmp r0, #0
bne leave_critical_fail
add r1, #1
b for_leave
end_for_leave:
Count: .word 0x00000000
What is the value at address Count after both programs complete?
as exclusive
cmp r
bbbbbbbgggggggtt en
leave_crit
ldrex rrrr
bgt
crcri
f
Any context switch
needs to clear
reservations
© 2021 Uwe R. Zimmer, The Australian National University page 314 of 487 (chapter 5: “Asynchronism” up to page 340)
ldr r4, =Count
mov r1, #1
for_enter:
cmp r1, #100
bgt end_for_enter
ldr r2, [r4]
add r2, #1
str r2, [r4]
add r1, #1
b for_enter
end_for_enter:
ldr r4, =Count
mov r1, #1
for_leave:
cmp r1, #100
bgt end_for_leave
ldr r2, [r4]
sub r2, #1
str r2, [r4]
add r1, #1
b for_leave
end_for_leave:
Count: .word 0x00000000
Critical section Critical section
Negotiate who goes fi rst
Indicate critical section completed
© 2021 Uwe R. Zimmer, The Australian National University page 315 of 487 (chapter 5: “Asynchronism” up to page 340)
ldr r3, =Lock
ldr r4, =Count
mov r1, #1
for_enter:
cmp r1, #100
bgt end_for_enter
fail_lock_enter:
ldr r0, [r3]
cmp r0, #0
bne fail_lock_enter ; if locked
ldr r2, [r4]
add r2, #1
str r2, [r4]
add r1, #1
b for_enter
end_for_enter:
ldr r3, =Lock
ldr r4, =Count
mov r1, #1
for_leave:
cmp r1, #100
bgt end_for_leave
fail_lock_leave:
ldr r0, [r3]
cmp r0, #0
bne fail_lock_leave ; if locked
ldr r2, [r4]
sub r2, #1
str r2, [r4]
add r1, #1
b for_leave
end_for_leave:
Count: .word 0x00000000
Lock: .word 0x00000000 ; #0 means unlocked
Critical section Critical section
© 2021 Uwe R. Zimmer, The Australian National University page 316 of 487 (chapter 5: “Asynchronism” up to page 340)
ldr r3, =Lock
ldr r4, =Count
mov r1, #1
for_enter:
cmp r1, #100
bgt end_for_enter
fail_lock_enter:
ldr r0, [r3]
cmp r0, #0
bne fail_lock_enter ; if locked
mov r0, #1 ; lock value
str r0, [r3] ; lock
ldr r2, [r4]
add r2, #1
str r2, [r4]
add r1, #1
b for_enter
end_for_enter:
ldr r3, =Lock
ldr r4, =Count
mov r1, #1
for_leave:
cmp r1, #100
bgt end_for_leave
fail_lock_leave:
ldr r0, [r3]
cmp r0, #0
bne fail_lock_leave ; if locked
mov r0, #1 ; lock value
str r0, [r3] ; lock
ldr r2, [r4]
sub r2, #1
str r2, [r4]
add r1, #1
b for_leave
end_for_leave:
Count: .word 0x00000000
Lock: .word 0x00000000 ; #0 means unlocked
Critical section Critical section
© 2021 Uwe R. Zimmer, The Australian National University page 317 of 487 (chapter 5: “Asynchronism” up to page 340)
ldr r3, =Lock
ldr r4, =Count
mov r1, #1
for_enter:
cmp r1, #100
bgt end_for_enter
fail_lock_enter:
ldrex r0, [r3]
cmp r0, #0
bne fail_lock_enter ; if locked
mov r0, #1 ; lock value
strex r5, r0, [r3] ; try lock
cmp r5, #0
bne fail_lock_enter ; if touched
dmb ; sync memory
ldr r2, [r4]
add r2, #1
str r2, [r4]
add r1, #1
b for_enter
end_for_enter:
ldr r3, =Lock
ldr r4, =Count
mov r1, #1
for_leave:
cmp r1, #100
bgt end_for_leave
fail_lock_leave:
ldrex r0, [r3]
cmp r0, #0
bne fail_lock_leave ; if locked
mov r0, #1 ; lock value
strex r5, r0, [r3] ; try lock
cmp r5, #0
bne fail_lock_leave ; if touched
dmb ; sync memory
ldr r2, [r4]
sub r2, #1
str r2, [r4]
add r1, #1
b for_leave
end_for_leave:
Count: .word 0x00000000
Lock: .word 0x00000000 ; #0 means unlocked
Critical section Critical section
for_leave:
cmp rrrrr11111,
bgt end_
fail lock lea
for_leav
r1
enend
Any context switch
needs to clear
reservations
© 2021 Uwe R. Zimmer, The Australian National University page 318 of 487 (chapter 5: “Asynchronism” up to page 340)
ldr r3, =Lock
ldr r4, =Count
mov r1, #1
for_enter:
cmp r1, #100
bgt end_for_enter
fail_lock_enter:
ldrex r0, [r3]
cmp r0, #0
bne fail_lock_enter ; if locked
mov r0, #1 ; lock value
strex r5, r0, [r3] ; try lock
cmp r5, #0
bne fail_lock_enter ; if touched
dmb ; sync memory
ldr r2, [r4]
add r2, #1
str r2, [r4]
dmb ; sync memory
mov r0, #0 ; unlock value
str r0, [r3] ; unlock
add r1, #1
b for_enter
end_for_enter:
ldr r3, =Lock
ldr r4, =Count
mov r1, #1
for_leave:
cmp r1, #100
bgt end_for_leave
fail_lock_leave:
ldrex r0, [r3]
cmp r0, #0
bne fail_lock_leave ; if locked
mov r0, #1 ; lock value
strex r5, r0, [r3] ; try lock
cmp r5, #0
bne fail_lock_leave ; if touched
dmb ; sync memory
ldr r2, [r4]
sub r2, #1
str r2, [r4]
dmb ; sync memory
mov r0, #0 ; unlock value
str r0, [r3] ; unlock
add r1, #1
b for_leave
end_for_leave:
Count: .word 0x00000000
Lock: .word 0x00000000 ; #0 means unlocked
Critical section Critical section
for_leave:
cmp rrrrr11111,
bgt end_
fail lock lea
for_leav
r1
enend
Any context switch
needs to clear
reservations
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 319 of 487 (chapter 5: “Asynchronism” up to page 340)
Mutual exclusion: atomic test-and-set operation
task body Pi is
L : Flag;
begin
loop
loop
[L := C; C := 1];
exit when L = 0;
—— change process
end loop;
—— critical_section_i;
C := 0;
end loop;
end Pi;
task body Pj is
L : Flag;
begin
loop
loop
[L := C; C := 1];
exit when L = 0;
—— change process
end loop;
—— critical_section_j;
C := 0;
end loop;
end Pj;
type Flag is Natural range 0..1; C : Flag := 0;
Does that work?
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 320 of 487 (chapter 5: “Asynchronism” up to page 340)
Mutual exclusion: atomic test-and-set operation
task body Pi is
L : Flag;
begin
loop
loop
[L := C; C := 1];
exit when L = 0;
—— change process
end loop;
—— critical_section_i;
C := 0;
end loop;
end Pi;
task body Pj is
L : Flag;
begin
loop
loop
[L := C; C := 1];
exit when L = 0;
—— change process
end loop;
—— critical_section_j;
C := 0;
end loop;
end Pj;
type Flag is Natural range 0..1; C : Flag := 0;
Mutual exclusion!, No deadlock!, No global live-lock!
Works for any dynamic number of processes.
Individual starvation possible! Busy waiting loops!
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 321 of 487 (chapter 5: “Asynchronism” up to page 340)
Mutual exclusion: atomic exchange operation
task body Pi is
L : Flag := 1;
begin
loop
loop
[Temp := L; L := C; C := Temp];
exit when L = 0;
—— change process
end loop;
—— critical_section_i;
L := 1; C := 0;
end loop;
end Pi;
task body Pj is
L : Flag := 1;
begin
loop
loop
[Temp := L; L := C; C := Temp];
exit when L = 0;
—— change process
end loop;
—— critical_section_j;
L := 1; C := 0;
end loop;
end Pj;
type Flag is Natural range 0..1; C : Flag := 0;
Does that work?
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 322 of 487 (chapter 5: “Asynchronism” up to page 340)
Mutual exclusion: atomic exchange operation
task body Pi is
L : Flag := 1;
begin
loop
loop
[Temp := L; L := C; C := Temp];
exit when L = 0;
—— change process
end loop;
—— critical_section_i;
L := 1; C := 0;
end loop;
end Pi;
task body Pj is
L : Flag := 1;
begin
loop
loop
[Temp := L; L := C; C := Temp];
exit when L = 0;
—— change process
end loop;
—— critical_section_j;
L := 1; C := 0;
end loop;
end Pj;
type Flag is Natural range 0..1; C : Flag := 0;
Mutual exclusion!, No deadlock!, No global live-lock!
Works for any dynamic number of processes.
Individual starvation possible! Busy waiting loops!
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 323 of 487 (chapter 5: “Asynchronism” up to page 340)
Mutual exclusion: memory cell reservation
task body Pi is
L : Flag;
begin
loop
loop
L :
R
=C; C :
T
= 1;
exit when Untouched and L = 0;
—— change process
end loop;
—— critical_section_i;
C := 0;
end loop;
end Pi;
task body Pj is
L : Flag;
begin
loop
loop
L :
R
=C; C :
T
= 1;
exit when Untouched and L = 0;
—— change process
end loop;
—— critical_section_j;
C := 0;
end loop;
end Pj;
type Flag is Natural range 0..1; C : Flag := 0;
Does that work?
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 324 of 487 (chapter 5: “Asynchronism” up to page 340)
Mutual exclusion: memory cell reservation
task body Pi is
L : Flag;
begin
loop
loop
L :
R
=C; C :
T
= 1;
exit when Untouched and L = 0;
—— change process
end loop;
—— critical_section_i;
C := 0;
end loop;
end Pi;
task body Pj is
L : Flag;
begin
loop
loop
L :
R
=C; C :
T
= 1;
exit when Untouched and L = 0;
—— change process
end loop;
—— critical_section_j;
C := 0;
end loop;
end Pj;
type Flag is Natural range 0..1; C : Flag := 0;
Mutual exclusion!, No deadlock!, No global live-lock!
Works for any dynamic number of processes.
Individual starvation possible! Busy waiting loops!
bbbeeegggggiin
loop
loop
L :
R
=C; C
begin
Any context switch
needs to clear
reservations
© 2021 Uwe R. Zimmer, The Australian National University page 325 of 487 (chapter 5: “Asynchronism” up to page 340)
ldr r3, =Lock
ldr r4, =Count
mov r1, #1
for_enter:
cmp r1, #100
bgt end_for_enter
fail_lock_enter:
ldrex r0, [r3]
cmp r0, #0
bne fail_lock_enter ; if locked
mov r0, #1 ; lock value
strex r5, r0, [r3] ; try lock
cmp r5, #0
bne fail_lock_enter ; if touched
dmb ; sync memory
ldr r2, [r4]
add r2, #1
str r2, [r4]
dmb ; sync memory
mov r0, #0 ; unlock value
str r0, [r3] ; unlock
add r1, #1
b for_enter
end_for_enter:
ldr r3, =Lock
ldr r4, =Count
mov r1, #1
for_leave:
cmp r1, #100
bgt end_for_leave
fail_lock_leave:
ldrex r0, [r3]
cmp r0, #0
bne fail_lock_leave ; if locked
mov r0, #1 ; lock value
strex r5, r0, [r3] ; try lock
cmp r5, #0
bne fail_lock_leave ; if touched
dmb ; sync memory
ldr r2, [r4]
sub r2, #1
str r2, [r4]
dmb ; sync memory
mov r0, #0 ; unlock value
str r0, [r3] ; unlock
add r1, #1
b for_leave
end_for_leave:
Count: .word 0x00000000
Lock: .word 0x00000000 ; #0 means unlocked
Critical section Critical section
for_leave:
cmp rrrrr11111,
bgt end_
fail lock lea
for_leav
r1
enend
Any context switch
needs to clear
reservations Asks for permission
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 326 of 487 (chapter 5: “Asynchronism” up to page 340)
Mutual exclusion … or the lack thereof
ldr r4, =Count
mov r1, #1
for_enter:
cmp r1, #100
bgt end_for_enter
enter_critical_fail:
ldrex r2, [r4] ; tag [r4] as exclusive
add r2, #1
strex r0, r2, [r4] ; only if untouched
cmp r0, #0
bne enter_critical_fail
add r1, #1
b for_enter
end_for_enter:
ldr r4, =Count
mov r1, #1
for_leave:
cmp r1, #100
bgt end_for_leave
leave_critical_fail:
ldrex r2, [r4] ; tag [r4] as exclusive
sub r2, #1
strex r0, r2, [r4] ; only if untouched
cmp r0, #0
bne leave_critical_fail
add r1, #1
b for_leave
end_for_leave:
Count: .word 0x00000000
What is the value at address Count after both programs complete?
as exclusive
cmp r
bbbbbbbgggggggtt en
leave_crit
ldrex rrrr
bgt
crcri
f
Any context switch
needs to clear
reservations
Asks for forgiveness
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 327 of 487 (chapter 5: “Asynchronism” up to page 340)
Beyond atomic hardware operations
Semaphores
Basic defi nition (Dijkstra 1968)
Assuming the following three conditions on a shared memory cell between processes:
• a set of processes agree on a variable S operating as a
fl ag to indicate synchronization conditions
• an atomic operation P on S — for ‘passeren’ (Dutch for ‘pass’):
P(S): [as soon as S > 0 then S := S – 1] this is a potentially delaying operation
• an atomic operation V on S — for ‘vrygeven’ (Dutch for ‘to release’):
V(S): [S := S + 1]
then the variable S is called a Semaphore.
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 328 of 487 (chapter 5: “Asynchronism” up to page 340)
Beyond atomic hardware operations
Semaphores
… as supplied by operating systems and runtime environments
• a set of processes P PN1f agree on a variable S operating
as a fl ag to indicate synchronization conditions
• an atomic operation Wait on S: (aka ‘Suspend_Until_True’, ‘sem_wait’, …)
Process Pi : Wait (S):
[if S > 0 then S := S – 1
else suspend Pi on S]
• an atomic operation Signal on S: (aka ‘Set_True’, ‘sem_post’, …)
Process Pi : Signal (S):
[if Pj7 suspended on S then release Pj
else S := S + 1]
then the variable S is called a Semaphore in a scheduling environment.
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 329 of 487 (chapter 5: “Asynchronism” up to page 340)
Beyond atomic hardware operations
Semaphores
Types of semaphores:
• Binary semaphores: restricted to [0, 1] or [False, True] resp.
Multiple V (Signal) calls have the same effect than a single call.
• Atomic hardware operations support binary semaphores.
• Binary semaphores are suffi cient to create all other semaphore forms.
• General semaphores (counting semaphores): non-negative number; (range lim-
ited by the system) P and V increment and decrement the semaphore by one.
• Quantity semaphores: The increment (and decrement) value for
the semaphore is specifi ed as a parameter with P and V.
All types of semaphores must be initialized:
often the number of processes which are allowed inside a critical section, i.e. ‘1’.
© 2021 Uwe R. Zimmer, The Australian National University page 330 of 487 (chapter 5: “Asynchronism” up to page 340)
ldr r3, =Semaphore
…
…
…
…
…
ldr r3, =Semaphore
…
…
…
…
…
Semaphore: .word 0x00000001
Critical section Critical section
signal (Semaphore) signal (Semaphore)
wait (Semaphore) wait (Semaphore)
© 2021 Uwe R. Zimmer, The Australian National University page 331 of 487 (chapter 5: “Asynchronism” up to page 340)
ldr r3, =Semaphore
…
wait_1:
ldr r0, [r3]
cmp r0, #0
beq wait_1 ; if Semaphore = 0
sub r0, #1 ; dec Semaphore
str r0, [r3] ; update
…
…
…
…
ldr r3, =Semaphore
…
wait_2:
ldr r0, [r3]
cmp r0, #0
beq wait_2 ; if Semaphore = 0
sub r0, #1 ; dec Semaphore
str r0, [r3] ; update
…
…
…
…
Semaphore: .word 0x00000001
Critical section Critical section
signal (Semaphore) signal (Semaphore)
© 2021 Uwe R. Zimmer, The Australian National University page 332 of 487 (chapter 5: “Asynchronism” up to page 340)
ldr r3, =Semaphore
…
wait_1:
ldrex r0, [r3]
cmp r0, #0
beq wait_1 ; if Semaphore = 0
sub r0, #1 ; dec Semaphore
strex r1, r0, [r3] ; try update
cmp r1, #0
bne wait_1 ; if touched
dmb ; sync memory
…
…
…
…
ldr r3, =Semaphore
…
wait_2:
ldrex r0, [r3]
cmp r0, #0
beq wait_2 ; if Semaphore = 0
sub r0, #1 ; dec Semaphore
strex r1, r0, [r3] ; try update
cmp r1, #0
bne wait_2 ; if touched
dmb ; sync memory
…
…
…
…
Semaphore: .word 0x00000001
Critical section Critical section
dr r3
…
wait_2:
ldrex r0
dlllllllllllllllllllllllllllllllll
Any context switch
needs to clear
reservations
signal (Semaphore) signal (Semaphore)
© 2021 Uwe R. Zimmer, The Australian National University page 333 of 487 (chapter 5: “Asynchronism” up to page 340)
ldr r3, =Semaphore
…
wait_1:
ldrex r0, [r3]
cmp r0, #0
beq wait_1 ; if Semaphore = 0
sub r0, #1 ; dec Semaphore
strex r1, r0, [r3] ; try update
cmp r1, #0
bne wait_1 ; if touched
dmb ; sync memory
…
…
…
ldr r0, [r3]
add r0, #1 ; inc Semaphore
str r0, [r3] ; update
…
ldr r3, =Semaphore
…
wait_2:
ldrex r0, [r3]
cmp r0, #0
beq wait_2 ; if Semaphore = 0
sub r0, #1 ; dec Semaphore
strex r1, r0, [r3] ; try update
cmp r1, #0
bne wait_2 ; if touched
dmb ; sync memory
…
…
…
ldr r0, [r3]
add r0, #1 ; inc Semaphore
str r0, [r3] ; update
…
Semaphore: .word 0x00000001
Critical section Critical section
© 2021 Uwe R. Zimmer, The Australian National University page 334 of 487 (chapter 5: “Asynchronism” up to page 340)
ldr r3, =Semaphore
…
wait_1:
ldrex r0, [r3]
cmp r0, #0
beq wait_1 ; if Semaphore = 0
sub r0, #1 ; dec Semaphore
strex r1, r0, [r3] ; try update
cmp r1, #0
bne wait_1 ; if touched
dmb ; sync memory
…
…
…
signal_1:
ldrex r0, [r3]
add r0, #1 ; inc Semaphore
strex r1, r0, [r3] ; try update
cmp r1, #0
bne signal_1 ; if touched
dmb ; sync memory
…
ldr r3, =Semaphore
…
wait_2:
ldrex r0, [r3]
cmp r0, #0
beq wait_2 ; if Semaphore = 0
sub r0, #1 ; dec Semaphore
strex r1, r0, [r3] ; try update
cmp r1, #0
bne wait_2 ; if touched
dmb ; sync memory
…
…
…
signal_2:
ldrex r0, [r3]
add r0, #1 ; inc Semaphore
strex r1, r0, [r3] ; try update
cmp r1, #0
bne signal_2 ; if touched
dmb ; sync memory
…
Semaphore: .word 0x00000001
Critical section Critical section
dr r3
…
wait_2:
ldrex r0
dlllllllllllllllllllllllllllllllll
Any context switch
needs to clear
reservations
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 335 of 487 (chapter 5: “Asynchronism” up to page 340)
Semaphores
S : Semaphore := 1;
task body Pi is
begin
loop
—— non_critical_section_i;
wait (S);
—— critical_section_i;
signal (S);
end loop;
end Pi;
task body Pj is
begin
loop
—— non_critical_section_j;
wait (S);
—— critical_section_j;
signal (S);
end loop;
end Pi;
Works?
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 336 of 487 (chapter 5: “Asynchronism” up to page 340)
Semaphores
S : Semaphore := 1;
task body Pi is
begin
loop
—— non_critical_section_i;
wait (S);
—— critical_section_i;
signal (S);
end loop;
end Pi;
task body Pj is
begin
loop
—— non_critical_section_j;
wait (S);
—— critical_section_j;
signal (S);
end loop;
end Pi;
Mutual exclusion!, No deadlock!, No global live-lock!
Works for any dynamic number of processes
Individual starvation possible!
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 337 of 487 (chapter 5: “Asynchronism” up to page 340)
Semaphores
S1, S2 : Semaphore := 1;
task body Pi is
begin
loop
—— non_critical_section_i;
wait (S1);
wait (S2);
—— critical_section_i;
signal (S2);
signal (S1);
end loop;
end Pi;
task body Pj is
begin
loop
—— non_critical_section_j;
wait (S2);
wait (S1);
—— critical_section_j;
signal (S1);
signal (S2);
end loop;
end Pi;
Works too?
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 338 of 487 (chapter 5: “Asynchronism” up to page 340)
Semaphores
S1, S2 : Semaphore := 1;
task body Pi is
begin
loop
—— non_critical_section_i;
wait (S1);
wait (S2);
—— critical_section_i;
signal (S2);
signal (S1);
end loop;
end Pi;
task body Pj is
begin
loop
—— non_critical_section_j;
wait (S2);
wait (S1);
—— critical_section_j;
signal (S1);
signal (S2);
end loop;
end Pi;
Mutual exclusion!, No global live-lock!
Works for any dynamic number of processes.
Individual starvation possible!
Deadlock possible!
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 339 of 487 (chapter 5: “Asynchronism” up to page 340)
Semaphores
S1, S2 : Semaphore := 1;
task body Pi is
begin
loop
—— non_critical_section_i;
wait (S1);
wait (S2);
—— critical_section_i;
signal (S2);
signal (S1);
end loop;
end Pi;
task body Pj is
begin
loop
—— non_critical_section_j;
wait (S2);
wait (S1);
—— critical_section_j;
signal (S1);
signal (S2);
end loop;
end Pi;
Mutual exclusion!, No global live-lock!
Works for any dynamic number of processes.
Individual starvation possible!
Deadlock possible!
Concurrent programming languages
offer higher abstraction and safer
synchronization mechanisms.
Asynchronism
© 2021 Uwe R. Zimmer, The Australian National University page 340 of 487 (chapter 5: “Asynchronism” up to page 340)
Aynchronism
• Interrupts & Exceptions
• Concept
• Hardware/Software interaction
• Recursive interrupts
• Concurrency & Synchronization
• Race conditions
• Synchronization
• Passing data
Summary