开发者

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 da开发者_JAVA百科ta 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.)


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

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

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.


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

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

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜