17.10

Example: Possible Swap

THREADS AND LOCKS

The thread may optionally

store

 the value of

a

 after the

assign

 has occurred. If

it does, then the

store

 action in turn requires a following

write

 action for

a

 by the

main memory.

The situation for the thread that calls

yon

 is similar, but with the roles of

a

 and

b

 exchanged.

The total set of actions may be pictured as follows:

hither

 thread

main memory

yon

 thread

read

b

read

a

load

b

load

a

use

b

use

a

assign

a

assign

b

[

store

a

]

[

store

b

]

[

write

a

]

[

write

b

]

Here an arrow from action

A

 to action

B

 indicates that

A

 must precede

B

.

In what order may the actions by the main memory occur? The only constraint

is that it is not possible both for the

write

 of

a

 to precede the

read

 of

a

 and for the

write

 of

b

 to precede the

read

 of

b

, because the causality arrows in the diagram

would form a loop so that an action would have to precede itself, which is not

allowed. Assuming that the optional

store

 and

write

 actions are to occur, there are

three possible orderings in which the main memory might legitimately perform its

actions. Let

ha

 and

hb

 be the working copies of

a

 and

b

 for the

hither

 thread, let

ya

 and

yb

 be the working copies for the

yon

 thread, and let

ma

 and

mb

 be the mas 

ter copies in main memory. Initially

ma=1

 and

mb=2

. Then the three possible

orderings of actions and the resulting states are as follows:

410