Javascript, async, lock?

Question

I know async is not parallel but I bumped into a quite funny situation now.

async function magic(){
  /* some processing here */
  await async () => await prompt_for_user(); // 1st prompt
  await async () => await prompt_for_user(); // 2nd prompt
}

magic(); // first
magic(); // second
magic(); // third

From the program above, we could easily predicts that all prompts pops up together at the same time. I tried to solve it with a queue with the following implementation:

 const Queue = () => {
  let promise;
  return async (f) => {
    while(promise) await promise;
    promise = f();
    const res = await promises;
    promise = undefined;
    return res;
  };
};


const queue = Queue();
async function magic(){
  /* some processing here */
  await queue(async () => await prompt_for_user()); // 1st prompt
  await queue(async () => await prompt_for_user()); // 2nd prompt
}

magic(); // first
magic(); // second
magic(); // third

This stops the prompt from popping up all at a time. But there is a second problem:

So when the first magic() is called. A prompt first.1 is shown to the user. The program continues and the second magic() is called. Another prompt second.1 is awaiting for the first prompt to finish before showing up. Then the program continues, the third magic() is called and third.1 again awaits for first.1 to finish. When first.1 finishes, meaning the user have typed the value, second.1 will pop up first but I wish first.2 to pop up first.

I know one obvious solution would be await the magic one by one. But this would lose the asynchronous advantages that js gives us. If the processing is heavy in magic before prompting, it will take some time before prompting.

Idea?

Answer 1

Since I had trouble understanding your overall objective until you posted your semaphore answer, I'll define the question I'm attempting to answer as this.

1. You want to run a series of asynchronous operations with as much parallelism as possible (serialized the least amount necessary).
2. One or more operations may need to prompt the user for info.
3. All user prompts must be in precise serial order for how the code is ordered. So, the first function that is called and prompts must prompt first.
4. If that same function prompts more than once, all of its prompts must come before any others.
5. So basically, all the prompts must be serialized, but any other async stuff that comes before or after the prompts can run in parallel.
6. The best code will not "spin" or "poll" a flag, but will preserve CPU cycles for other operations by getting notified when something that is waiting is ready to run (one big principle behind promises).

Here's a scheme, modeled after the one you posted, but it uses a chain of promises (no spinning or polling a flag) to force serialization of the prompt() calls (anything between .start() and .end() calls while allowing all other operations to run in parallel. This should be a lot more efficient with CPU usage.

let Semaphore = (function() {
    // private data shared among all instances
    let sharedPromise = Promise.resolve();
    
    return class Sempaphore {
        constructor() {
            let priorP = sharedPromise;
            let resolver;
            
            // create our promise (to be resolved later)
            let newP = new Promise(resolve => {
                resolver = resolve;
            });
            
            // chain our position onto the sharedPromise to force serialization
            // of semaphores based on when the constructor is called
            sharedPromise = sharedPromise.then(() => {
                return newP;
            });
            
            // allow caller to wait on prior promise for its turn in the chain
            this.start = function() {
                return priorP;
            }
            
            // finish our promise to enable next caller in the chain to get notified
            this.end = function() {
                resolver();
            }
        }
    }
})();

// use random times to test our async better
function prompt(tag, n) {
  log(tag, 'input please: ', n);
  return new Promise((resolve) => {
    setTimeout(resolve, Math.floor(Math.random() * 1000) + 500);
  });
};

function log(...args) {
    if (!log.start) {
        log.start = Date.now();
    }
    let diff = ((Date.now() - log.start) / 1000).toFixed(3);
    console.log(diff + ": ", ...args);
}

function randomDelay(low = 500, high = 1000) {
  return new Promise((resolve) => {
    setTimeout(resolve, Math.floor(Math.random() * (high - low)) + low);
  });
}

async function magic1(tag){
  // declare semaphore before any async code to reserve your order for semaphored code below
  let s = new Semaphore();

  // whatever sync or async code you want here
  log(tag, 'do some busy async work 1a');
  await randomDelay(800, 1200);
  log(tag, 'do some busy work 1b');

  // start of our serialized critical section
  await s.start();
  await prompt(tag, 1);
  await prompt(tag, 2);
  s.end();
  // end of our serialized critical section

  // whatever sync or async code you want here
  log(tag, 'do more busy work 1c');
  await randomDelay();
}

async function magic2(tag){
  let s = new Semaphore();
  log(tag, 'do some busy async work 2a');
  // this delay purposely causes magic2 async delay to be shorter 
  // than magic1 for testing purposes
  await randomDelay(100, 750);
  log(tag, 'do some busy work 2b');
  await s.start();
  await prompt(tag, 3);
  await prompt(tag, 4);
  s.end();
  log(tag, 'do more busy work 2c');
  await randomDelay();
}

Promise.all([
    magic1("magic1a"),
    magic1("magic1b"),
    magic2("magic2a"),
    magic2("magic2b")
]).then(() => {
    log("all done");
}).catch(err => {
    log("err: ", err);
});

And here's some sample output (output will vary slightly because of random async delays done for testing purposes). But, input calls will always be in exactly the same order:

0.000:  magic1a do some busy async work 1a
0.003:  magic1b do some busy async work 1a
0.004:  magic2a do some busy async work 2a
0.004:  magic2b do some busy async work 2a
0.600:  magic2b do some busy work 2b
0.721:  magic2a do some busy work 2b
0.829:  magic1b do some busy work 1b
1.060:  magic1a do some busy work 1b
1.061:  magic1a input please:  1
2.179:  magic1a input please:  2
2.860:  magic1a do more busy work 1c
2.862:  magic1b input please:  1
3.738:  magic1b input please:  2
4.500:  magic1b do more busy work 1c
4.502:  magic2a input please:  3
5.845:  magic2a input please:  4
6.497:  magic2a do more busy work 2c
6.498:  magic2b input please:  3
7.516:  magic2b input please:  4
8.136:  magic2b do more busy work 2c
9.097:  all done

Some explanation:

1. Where you put let s = new Sempaphore(); in the code is where you this function to "put itself in line" for serialization so something that hasn't already put itself in line have it's critical section be forced to come after this function's critical section. This "reserves" a spot in line, but doesn't actually start a critical section yet. This is important if you have other indeterminate async code that runs before the critical section. You need to reserve your place in line before now before your async code, but not actual wait for the place in line until right before the critical section.

2. Where you put await s.start(); in the function is where you want it to actually wait for your spot in line for a critical section.

3. Where you put s.end() is the end of your critical section (allowing other critical sections to now also run when its their turn).

4. This demo shows async code running both before and after the critical sections of prompts. That code can run in parallel with other things.

5. Non-input related async operations can be interleaved between input prompts even in the same critical section (by design). Only input prompts are forced to be serialized.

Answer 2

So after testing for a while, finally I got an answer! Inspired by the concept of semaphore, I have created the following:

const Semaphore = (n) => ({
  n,
  async down(){
    while(this.n <= 0) await this.wait();
    this.n--;
  },
  up(){
    this.n++;
  },
  async wait(){
    if(this.n <= 0) return await new Promise((res, req) => {
      setImmediate(async () => res(await this.wait()))
    });
    return;
  },
});

const prompt = (n) => {
  console.log('input please: ' + n);
  return new Promise((res, rej) => {
    setTimeout(() => res(), 3000)
  });
};

const semaphore = Semaphore(1);

async function magic1(){
  console.log('do some busy work 1');
  await semaphore.down();
  await prompt(1);
  await prompt(2);
  semaphore.up();
}

async function magic2(){
  console.log('do some busy work 2');
  await semaphore.down();
  await prompt(3);
  await prompt(4);
  semaphore.up();
}

magic1();
magic1();
magic2();
magic2();

Result:

do some busy work 1
do some busy work 1
do some busy work 2
do some busy work 2
input please: 1
input please: 2
input please: 1
input please: 2
input please: 3
input please: 4
input please: 3
input please: 4

This semaphore essentially busy waits if n == 0. Although I call it busy wait, it actually doesn't because setImmediate will allow other functions in the event loop to execute! This implementation is the best and elegant working solution that I have come to so far.

Sometimes, it will say [1,2] [3,4] [1,2] [3,4]. But that's ok! It's asynchronous!