2
$\begingroup$

Is there a mutual exclusion or semaphore or locking algorithm that only relies on atomic reads and atomic writes of shared memory and can tolerate a delay in propagation of the written data between processes? I.e. if process A writes to shared memory, process B might not see the change for a while (but process A will see the change immediately).

It seems to me that this might be theoretically impossible if I don't have an upper bound on the delay, but if I do have such an upper bound, is there an algorithm that's a little more clever than just sticking busy-waits for the worst-case delay between the reads and writes of any other non-delay-tolerant algorithm?

(I'm trying to solve this problem: Cross-window synchronization (critical sections) in the browser)

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Two questions: first is what makes you believe you can do mutual exclusion without busy-waiting and without any primitives that are capable of kernel scheduling. Second is that all synchronization algortihms support some delay between CPUs, but its the ordering of memory operations that is essential to their operation. What sort of mechanics can you guarantee (i.e. Sequential Consistency or perhaps just Load-Load/Store-Store consistency) $\endgroup$
    – Cort Ammon
    Oct 24, 2015 at 0:26
  • $\begingroup$ @CortAmmon Some mutex algorithms can be turned into a non-blocking method that returns a boolean indicating whether the critical section was successfully entered or whether the entry needs to be retried (see here for an example). I would like to find an algorithm that allows this. Unfortunately, I don't have any strict ordering guarantees. If process A writes "Hello", it might take up to 200ms before processs B will read "Hello" rather than the previous value. $\endgroup$
    – Markus A.
    Oct 24, 2015 at 0:38
  • $\begingroup$ when you say atomic reads/writes. do you have anything like CAS, or any of the other atomic operations used to implement modern atomic code? Can you trust the other side to poll the memory on a regular basis and/or send the equivalent of interrupts to the other side? $\endgroup$
    – Cort Ammon
    Oct 24, 2015 at 0:46
  • $\begingroup$ @CortAmmon Unfortunately I don't have CAS or other atomic primitives (like increment-and-get or so). I can trust the other side to poll the memory regularly, though, and I have change-notifications that should arrive at the other side whenever something was modified (I guess these two are pretty much equivalent, though, since I could always just generate my own notification after a poll finds a change...). $\endgroup$
    – Markus A.
    Oct 24, 2015 at 0:53

1 Answer 1

Reset to default
2
$\begingroup$

If you don't have access to atomic primitives like CAS, you're going to have to depend on voluntary synchronization between the two halves. This means side A cannot proceed until side B has acknowledged that side A took the mutex.

Since we know nothing about the shared memory, we cannot assume that write to two seperate regions will be seen in order (some caches will change the order that writes present). We will have to assume that there is some atomic thing, like an int32. We're also going to have to assume that when you say atomic read and write, you never see tearing on the integer, and it's monotonic (if I numbered A's writes, and I've observed #13, I will never again see the #12 value that had been written).

If you do this, then just take one bit (say, the MSB) and use that as an ownership token over the communication used to handle locks. If it's a 1, it means A gets to write. If it's a 0, B gets to write. Whenever A sets it to a new value, the MSB is always 0, and when B sets it to a new value, the MSB is always 1. Now, with nothing but normal reads and writes, we can tell who has the "rights" to the communication channel.

Now the communication channel consists of the lower 31 bits. You can send anything you please across this, including requests to acquire or release a "mutex." If you want to acquire it, you simply have to wait for it to be your turn to read, send a "request mutex" message, and wait for the reply to say "mutex OK"

EDIT: From our chat discussion, it appears what is really needed is a lottery process to select a master thread, who then takes over the job of being the "kernel" that manages the mutual exclusions. All it needs is a way to detect when the master thread died, and elect a new master. This lets us split the problem up into a slow part, which is very robust, and a fast part that works as long as a master is present.

Improve this answer
$\endgroup$
11
  • $\begingroup$ That's a really neat idea. My problem with using it is that my processes are 100% identical and might start at the same exact time (two or more open tabs/windows of the same web-page). So, I don't have an implicit assignment as to which process is A and which one is B. Also, I can have more than two processes running, so to implement some kind of binary-tree or tournament to resolve mutex requests among all of them, I would need to enumerate the processes and assign to them their spot in the tree and such. $\endgroup$
    – Markus A.
    Oct 24, 2015 at 1:21
  • $\begingroup$ There are a class of algorithms that assign IDs to a network in an arbitrary order. However, if you don't have a single bit of information to start solving contention problems with, it's really hard to develop any. Timeouts may be your friend. One algorithm would be to look at a variable, see if it's 0. If it is, set it to some random value, wait 1 second, and observe it. If it's still your value, you "win" and get to act before setting the variable back to 0. Adding a second round of this would decrease the odds of a collision from two sides both getting the same random number $\endgroup$
    – Cort Ammon
    Oct 24, 2015 at 1:25
  • 1
    $\begingroup$ Looks like the very first algorithm in Lamport's Fast Mutual Exclusion Algorithm paper (page "2" (8)). Lamport goes on to say that the delay in the algorithm might need to be arbitrarily large in the face of multiple processes. I haven't wrapped my head around the question yet, whether that argument would also apply in my case, or, more specifically, given a certain maximum propagation-time and a certain maximum number of processes, what would be the minimum delay that would guarantee correct operation. $\endgroup$
    – Markus A.
    Oct 24, 2015 at 1:39
  • $\begingroup$ In his paper he develops algorithms next that replace the "arbitrary" delays with busy-waits. Is it possible to do this in my case also? $\endgroup$
    – Markus A.
    Oct 24, 2015 at 1:49
  • $\begingroup$ His makes two assumptions. one is that reads/writes from any one thread are ordered across all of the shared memory (which you can enforce if you have access to a memory barrier function, but its hard to guarantee without it), and the other key one is that each process has an id (i.e. A/B 1 or 2) $\endgroup$
    – Cort Ammon
    Oct 24, 2015 at 2:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.