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.)

Answers


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

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


Need Your Help

realize Bitset function whose param is long

java bitset

The set() function of BitSet is set(int param).I am trying to realize Bitset function by sending a long type.Are there any API or tutorial? thanks.

Java fatal error SIGSEGV

java segmentation-fault sigsegv jvm-hotspot jvm-crash

I am getting an error message from the Java compiler that I don't understand. I've tested my code on OSX 10.6, 10.9, and Ubuntu 14.04, with both Java 6 and 7. When I run with the Eclipse debugger o...

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.