0

In my app two components A and B, have their data and state based on the data and state of a 3rd component, component C:

  • Both A and B can change the data of component C.
  • Both A and B listen to changing of data of component C and react to it by re-computing their internal data and state.
  • A and B each run on their own thread.

What I am struggling with how to implement the scenario where both component A and B try to update C simultaneously and how to react to the changes while operation is in progress:

  1. A starts updating data on C
  2. B starts updating data on C. C has an internal lock which prevents updating data concurrently, so the operation needs to wait for A to complete first.
  3. A finishes updating data on C. C sends data change event to both A and B.
  4. B could start updating data on C, but at this point the data in C is in a different state than how it was when B started the operation. The operation might not make sense anymore now.

In step #3, where B received event from C, I am thinking that B should re-evaluates itself, it needs to recompute its data and state. But it should also cancel its data change operation it started in step #2.

The same situation can happen the other way around, component B can start operation first and component A is second.

This is the part I am struggling with, how to implement all this. Before talking about code, I will give even a more concrete example:

The UI shows an item on a screen for user to update. There's a component running on a background thread, which can update the same item because of device location change. Both the UI and location tracking components access the item repository, to update the item.

I am looking for some suggestions how to implement this.

I'm using .NET C#, so my solution is using classes specific to .NET. However, I didn't want to make this question specific to .NET, because the same question could apply to Java, and other languages\technologies as well.

One idea I have is to have both UI and location tracking each keep a CancellationTokenSource which they can cancel when they receive event from C:

CancellationTokenSource _cts;

void UpdateItem(Item item) {
   _cts = new CancellationTokenSource();

   try
   {       
      _itemRepo.UpdateItem(item, …, _cts.Token);
   }
   catch(OperationCancelled)
   {
      // re-evaluate state here
   }
}

void ItemRepo_DataChanged(object sender, EventArgs e)
{
   if(_cts != null) {
      _cts.Cancel();
   }
}

Do you see other ways to implement this?

Alternatively, are there any examples in frameworks or tools or even OSS projects I could take a look at?

2

C has an internal lock which prevents updating data concurrently, so the operation needs to wait for A to complete first.

This is the root of the problem: internal locking for updates and reads only makes the act of reading and writing the memory where C's value resides safe. It does nothing for situations like yours where one thread shouldn't act on data that another is about to render stale.

The simple case is where the calculation of C's new value is quick and you can lock C for its entire duration.

a():
    ...
    c.lock()
    current_c := c.get_value()
    new_c := quickly_calculate_new_c(current_c)
    // set_new_value() is assumed not to send notifications
    // if the new value isn't different than the old one.
    c.set_value(new_c)
    c.unlock()
    ...

B would have the same code with its own calculation for the new C. A's decisions based on the current value will be valid the entire time because its hold on the lock prevents other threads from acting on data that's about to be changed. B's decisions get the same protection.

One thing that's important to note about this is if there's nothing synchronous about the way A and B operate, A can't make decisions based on what B might do in the future. If A asks for C's lock and gets it, it means the state of C is the most up-to-date information available and should be used for making changes. Anything that has to wait for the lock in the meantime is a future action.

Your question implies that the calculation is a long-running process and should be aborted if a change to C would render it pointless. That being the case, the calculation has to be done cooperatively, aborting when doing it no longer makes sense:

a_update_c():

    // Hold the initial value for later.
    c.lock()
    old_c := c.get_value()
    c.unlock()

    if no_reason_to_change_c(old_c)
        return(OK)

    // Do the calculation of C's new value a bit at a time
    while do_part_of_new_c_calculation(old_c)
        if notified_by(c)
            c.lock()
            changed_c := c.get_value()
            c.unlock()
            if calcluation_is_pointless(old_c, changed_c)
                abort_new_c_calculation()
                return(TRY_AGAIN)

    new_c := result_of_new_c_calculation()

    c.lock()

    // If our assumptions are still valid, update C.  Since
    // C is locked, nothing else can change the value or
    // make decisions based on it while our own decision
    // and update are underway.
    if c.get_value() != old_c_value
        c.unlock()
        return(TRY_AGAIN)
    c.set_value(new_c_value)

    c.unlock()
    return(OK)

a():
    ...
    while a_update_c() != TRY_AGAIN
        null  // Do nothing; just loop.
    ...

There are more-elegant (and safer) ways to handle the locking and unlocking, but whether or not they're available to you depends on the language.

If the lock you're using is reentrant, you can use the same lock and have get_value() and set_value() acquire it so simple transactions are guarantted safe without requiring the caller to surround it with a lock()/unlock().

The UI problem is a user experience problem, that being how to handle the data the user is interacting with changing during the interaction. That's probably been covered on UX.SE.

1

Monitor

From the abstract, the internal lock in C would work. That is usually the starting point.

Now, the problem is, both thread A and B get to the lock to write to C. A gets the lock. B waits. A updates the state of C. Now B wakes up, but the state has changed, what it was going to do is no longer valid.

B would have to read the state inside the lock. Why? Because if B reads the state outside of the lock, it may have changed for when it gets to the lock. Furthermore, if you do not use a lock to read the state - and depending on the structure of C - A or B could see a partially updated state. That is never good.

However, this lock exists inside of C. And if you have to read inside the lock, you would need to pass a callback to compute the updated state. And you would implement your retry logic with it too.

Note: In .NET, you can make the same behaviour as above using a SemaphoreSlim set to only let one thread enter. The advantage is that it will listen to CancellationToken. If you prefer that to retry logic.


Cooperative Locking

So, you have a lock, two threads want to enter, but only one gets it. The other one is waiting, wasting time.

And they are both passing callbacks to compute the update they want to make.

Ok, great. Store those callbacks in a thread-safe collection. Now, the thread that gets the lock can run them all, in order. And the thread that does not get the lock, can walk away knowing that the thread that got the lock will do the job.

As you can see, with this method, the update will always be done with the up to date version of the state. So, there is no need for cancellation. If you are clever with the thread-safe collection, the thread may even check if it has already placed a callback on it (and do nothing or replaced, depending on what you need).

Note: For that thread-safe collection, you can just use an array. Give each subscriber an index on the array.


Using a Read-Write Lock

Let us say, you do not like the cooperative locking idea. And you want to stick with retry logic.

Ok, let us see how a reader writer lock can help you… With it, you can have multiple threads reading the state simultaneously, and then they will upgrade to a writer lock when they need to update.

And for the retry logic... thread A and thread B are reading, both thread A and thread B want to upgrade to a write. One of them will succeed and the other one will fail. Let us say A did succeed. B is not stuck waiting, instead it got an exception. B has to request a read lock again, that will make the B wait until A completes the write. When B gets the reader lock the state has changed, so it has to read again.

.NET ReaderWriterLock has a timeout for upgrade. You can set the timeout for upgrade to 0 without any loss of functionality.


Atomic update

When C changes, it notifies A and B. In the notification, it can send a value state object that has copy C state along with a version object. Then A and B can work on this value state object and give it back to C to request an update.

Then C can follow a double check pattern on the version: if the version object is the same, try to get the lock. Inside the lock, check again if the version object is the same. If it is, update, if it is not, leave.

Furthermore, C can copy the received state to a local variable, and use interlocked operations to update the internal state from that copy in an atomic operation. This way avoiding the use of Monitor. Thus, the threads do not have to wait.

Note: Since we want to do use interlocked operations on the state, it should not be a value type. As an optimization, you can implement an object pool for the value state objects.

Notes:

  • Keep the most recent known state. Including the state you send if the update did succeed. The code that computes the updated state must read that most recent known state. This allows for multiple updates to happen between executions.
  • Is it expensive to compute the updated state? If it is, in the update process you need to insert checks to see if you got a newer state. No, CancellationToken buys you nothing in this case.
  • For now, the way C notifies A and B is by using simple C# events. In the threading context however, I realize this might not work, so it's another reason why this looks even more complicated. I'm still digesting your answer. ReaderWriterLock looks nice but I heard it has some stability issues: chabster.blogspot.com/2013/07/… chabster.blogspot.com/2013/12/… – Daniel Jun 3 '18 at 19:05
  • Regarding "Cooperative Locking": If I understand it correctly, you're suggesting multiplexing the threads? So that one thread runs both callbacks. But isn't still the same problem that if the first callback changes data, whatever the 2nd one is doing, it might be something which no longer applies, because the 1st callback changed C's data already? – Daniel Jun 3 '18 at 19:14
  • @Daniel Personally, I would not use ReaderWriterLock(Slim), I would go with the the Atomic update option. I may have interesting code for you: ReentrantReadWriteLock. Note: That is not in the nuget builds. I have some interesting stuff in the repository, including weak events and transactional memory. About cooperative locking: if the callbacks computes the new state, then they would be working with the result of the previous callback. Edit: you can make the previous state a param to the callback – Theraot Jun 3 '18 at 19:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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