Best way to prevent race condition in multiple chr

问题:

1. Something requests a task
2. Something else pulls the task list out of storage, and checks if there are tasks there.
3. If there are tasks it removes one and the smaller "task list" is put back in storage.

Between steps 2 and 3 a race condition can occur if multiple requests occur, and the same task will be served twice.

Is the correct resolution to "lock" the "tasks table" while a single task is "checked out", to prevent any other requests?

What is the solution with the least performance impact, such as delay of execution, and how should it be implemented in javascript with chrome.storage API ?

Some code for example :

function decide_response ( ) {
    if(script.replay_type == "reissue") {
            function next_task( tasks ) {
                var no_tasks = (tasks.length == 0);
                if( no_tasks ) {
                    target_complete_responses.close_requester();
                }
                else {
                    var next_task = tasks.pop();
                    function notify_execute () {
                        target_complete_responses.notify_requester_execute( next_task );
                    }
                    setTable("tasks", tasks, notify_execute);
                }
            }
            getTable( "tasks", next_tasks );
    ...
    }
...
}

回答1:

I think you can manage without a lock by taking advantage of the fact that javascript is single-threaded within a context, even with the asynchronous chrome.storage API. As long as you're not using chrome.storage.sync, that is - if there may or may not be changes from the cloud I think all bets are off.

I would do something like this (written off the cuff, not tested, no error handling):

var getTask = (function() {
  // Private list of requests.
  var callbackQueue = [];

  // This function is called when chrome.storage.local.set() has
  // completed storing the updated task list.
  var tasksWritten = function(nComplete) {
    // Remove completed requests from the queue.
    callbackQueue = callbackQueue.slice(nComplete);

    // Handle any newly arrived requests.
    if (callbackQueue.length)
      chrome.storage.local.get('tasks', distributeTasks);
  };

  // This function is called via chrome.storage.local.get() with the
  // task list.
  var distributeTasks = function(items) {
    // Invoke callbacks with tasks.
    var tasks = items['tasks'];
    for (var i = 0; i < callbackQueue.length; ++i)
      callbackQueue[i](tasks[i] || null);

    // Update and store the task list. Pass the number of requests
    // handled as an argument to the set() handler because the queue
    // length may change by the time the handler is invoked.
    chrome.storage.local.set(
      { 'tasks': tasks.slice(callbackQueue.length) },
      function() {
        tasksWritten(callbackQueue.length);
      }
    );
  };

  // This is the public function task consumers call to get a new
  // task. The task is returned via the callback argument.
  return function(callback) {
    if (callbackQueue.push(callback) === 1)
      chrome.storage.local.get('tasks', distributeTasks);
  };
})();

This stores task requests from consumers as callbacks in a queue in local memory. When a new request arrives, the callback is added to the queue and the task list is fetched iff this is the only request in the queue. Otherwise we can assume that the queue is already being processed (this is an implicit lock that allows only one strand of execution to access the task list).

When the task list is fetched, tasks are distributed to requests. Note that there may be more than one request if more have arrived before the fetch completed. This code just passes null to a callback if there are more requests than tasks. To instead block requests until more tasks arrive, hold unused callbacks and restart request processing when tasks are added. If tasks can be dynamically produced as well as consumed, remember that race conditions will need to be prevented there as well but is not shown here.

It's important to prevent reading the task list again until the updated task list is stored. To accomplish this, requests aren't removed from the queue until the update is complete. Then we need to make sure to process any requests that arrived in the meantime (it's possible to short-circuit the call to chrome.storage.local.get() but I did it this way for simplicity).

This approach should be pretty efficient in the sense that it should minimize updates to the task list while still responding as quickly as possible. There is no explicit locking or waiting. If you have task consumers in other contexts, set up a chrome.extension message handler that calls the getTask() function.