CODEWITHSUNDEEP
design-patternsconcurrency
Jason S
Jason S

Reputation: 189786

Literature/documentation on two cooperating processes using a flag for lock-free shared memory

Is there any other documentation/discussion about the following design pattern (I'm not sure what it is called) from a well-known source? I'm almost 100% sure that the following will manage data safely between two (not more than two) processes, but would feel much better if I could find some more detailed information on why it works from a reputable source.

Suppose I have two processes A and B that are executing in parallel. They share the following data structure (in pseudo-C code):

struct Shared
{
    bool ownedByA
    Otherstuff otherstuff;
}

I can use the following pair of state machines to manage this shared data safely:

A:

state A.A (data is owned by A), entered on startup:
    read/modify/write "otherstuff"
    when done, goto A.Adone

state A.Adone
    set ownedByA to false
    goto state A.B

state A.B (data is owned by B):
    if ownedByA is true, goto state A.A
    otherwise stay in state A.B

B:

state B.A (data is owned by A), entered on startup:
    if ownedByA is false, goto state B.B
    otherwise stay in state B.A

state B.B (data is owned by B):
    read/modify/write "otherstuff"
    when done, go to B.Bdone

state B.Bdone:
    set ownedByA to true
    goto state B.A

We must ensure A.A's writes to "otherstuff" and A.Adone's write to ownedByA are in strict sequence ordering w/r/t memory visibility. Similarly for B.B and B.Bdone.

at startup:

1. Initialize ownedByA to true, A to the A.A state, B to the B.A state
2. start running state machines 
(ensure that 1. happens-before 2.)

Upvotes: 2

Views: 223

Answers (2)

Nick Dandoulakis
Nick Dandoulakis

Reputation: 43130

You can try Th. J. Dekker's solution, mentioned by E. W. Dijkstra in his EWD1303 paper. alt text

And then something profound and lovely happened. By analyzing by what structure of argument the proof obligations could be met, the numerical mathematician Th.J. Dekker designed within a few hours
the above solution together with its correctness argument, and this settled the contest.
In the above solution, the pair "c1,c2" implements the mutual exclusion, while "turn" has been introduced to resolve the tie when the two processes simultaneously try to enter their critical sections.

Upvotes: 1

nanda
nanda

Reputation: 24788

Maybe that's a Dining philosophers problem with only two philosophers and one fork.

http://en.wikipedia.org/wiki/Dining_philosophers_problem

Upvotes: 1

Related Questions