CS计算机代考程序代写 concurrency arm COPE-05 Asynchronism.indd

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