Mutual Exclusion for N Asynchronous Threads

Question

I've got an asynchronous application, meaning that at any given time there can be N events. Is there a known algorithm for doing mutual exclusion for N threads, without hardcoding each thread to have an ID?

An example of needing this would be using Local Storage, which is non-transactional and thus not safe if the same page is opened in multiple tabs. Implementing mutex behavior with a shared worker could work around that limitation. — Vincent Scheib, Mar 20 '11 at 23:40

score 4 · Accepted Answer · answered Sep 12 '10 at 03:18

4

I don't think Javascript per se has object locking - because Javascript is basically single-threaded. You might be able to find a library or implementation that runs several threads of Javascript code - but are they all running in the same variable-space? They will need to communicate with each other somehow.

Assuming your multiple threads can share a static mutex variable somehow, and insofar as you assume '++' is considered an atomic operation for the system that is doing your threading, how about this?

int mutex = 0;
mutuallyExclusiveOperation(){
  succeed=false;
  while(!succeed){
    while(mutex>0){ sleep();  }
    m=mutex++;   //"Simultaneously" read and increment
    if(m>0)mutex--;
    else{
      doMutuallyExclusiveThing();
      succeed=true;
      mutex--;
    }
 }
}

answered Sep 12 '10 at 03:18

Sanjay Manohar

6,920
3
35
58

I can do a static variable no problem, my concern wasn't I wasn't sure that ++ _Was_ an atomic operation. Do you know if this is the case for JS? If that's true, this problem is (I believe), solvable. Your function looks like it does it correctly, actually. – Michael Sep 12 '10 at 04:37
As of today, chrome isn't anymore single threaded. Try this example, it will use 100% of your processor: http://jsfiddle.net/MTJ27/15/ – darkzangel Jul 31 '14 at 19:06
Can the code you provided be used as it is? I mean it's totally right and can be used in production mode? – Dec 19 '14 at 21:21
I expect the behaviour of `++` is dependent on which Javascript interpreter is used. If I were launching a spaceship with this code, I'd a) run a lot of heavily threaded tests on the specific browser to be used, and b) examine the interpreter code itself. If multiple instances of the interpreter are running in separate real OS threads, as @darkzagnel suggests, then maybe there's no hope of a foolproof solution, unless you can find a truly atomic JS read-write operation. – Sanjay Manohar Dec 20 '14 at 04:19
Actually, don't worry about mutex and stuff like that. Chrome is multithreaded only if you use worker and worker don't share their data with your code. You have to pass data to it using port and signal. Their don't have access to the dom, to the window, document or any other variable. – darkzangel Dec 28 '14 at 17:22
@darkzangel Chrome itself (meaning, a given tab of chrome) is still single-threaded, but when you create a Worker, you explicitely are creating a new thread (actually, it's more close to a new process, but whatev xD). – xDaizu Jun 23 '16 at 16:06

score 2 · Answer 2 · answered Sep 12 '10 at 03:28

2

JavaScript is generally single threaded, so you never have two pieces of code modifying the same data at the same time. You can use multiple threads in modern browsers using Web Workers, but they can only communicate by passing messages, not sharing memory, so you don't need to worry about mutual exclusion if you're using web workers.

answered Sep 12 '10 at 03:28

Brian Campbell

322,767
57
360
340

I'm actually utilizing web workers, but that's beside the point. My worry is if the onMessage function gets called twice. While it may be "single threaded", won't it thread the two calls to it intermittently, if they end up running in the same time period? – Michael Sep 12 '10 at 04:08
@Michael What resource are you trying to protect access to with your mutual exclusion? – Brian Campbell Sep 12 '10 at 04:13
Say I've got some global array, and I need to store something in it, and return the index of the item stored. Normally, I'd check the length, push it into the array, and return the length of the array. But if the second thread (that was called due to an asynchronous event) gets threaded between the getting of the array length, and pushing the new value onto the array, and does the same thing itself, the first function will return the wrong index. – Michael Sep 12 '10 at 04:41

score 1 · Answer 3 · edited Oct 26 '12 at 14:46

Can be single threaded but sometimes there is a problem when some user actions are running multiple threads that we would like to avoid (for ex. AJAX requests). If we would like to make a semaphore we can use a global variable. Anyways, I'm sure it shouldn't be done this way - I just don't know any better solution as I'm not involved in JS so much.

Hope it'll help you in some simple situations:

<html>

 <head>
  <script type="text/javascript">
        var magic_global;
        magic_global = true;

        function magic_switch() {
                magic_global = !magic_global;
        }
  </script>
 </head>

 <body>
        <a href="#" onclick="magic_switch();">switch Magic</a>
        <a href="#" onclick="alert(magic_global);">show the Magic</a>
 </body>

</html>

Mutual Exclusion for N Asynchronous Threads

3 Answers3

Linked