Is a data structure used only in a single thread always safe?

Question

I had a conversation with a few co-workers and the concept of thread safety for a data structure came up.

In this example, we have 2 threads: a main thread and a background thread.

For the following pseudo class:

class Foo {
  Array myArray;

  // Only ever called on the main thread
  // This method will call into the background thread
  // but when complete the onCompleteBlock will be called
  // on the main thread.
  function method1() {
    // do something to the array on main thread
    myArray.add('foo');
    callBackgroundThread(onComplete() {

       // onComplete callback is called on main thread
       // do something else to the array on the main thread
       myArray.add('bar');
    })
  }

  // only ever called on the main thread
  function method2() {
    // do some other stuff to the array on the main thread

    if (myArray.contains('bar') {
      myArray.remove('foo');
    }
  }
}

So in this example the class has an array as a data structure. Both methods are always guaranteed to be called on the main thread. Method1 calls a function that kicks off a background process, when that process is finished it calls back into the main thread.

Is this class, and the myArray data structure 'safe'?

I know this class is not thread safe as the myArray data structure is not protected by any synchronization. So if multiple threads did call method1 and method we would run into trouble. But any time myArray is used, it is used on the main thread.

1. One argument on why this might not be safe is that if the main thread is paused (like when we are in the background thread), it may not be resumed in the same place it left off, i.e. maybe an operation called method2() and that is where the main thread wakes up and resumes.

2. Another is that memory may have been swapped. Not sure what was meant by this.

To be fair, I did not fully understand either argument and thought that this class was fine since all variables were only accessed on the main thread. If either argument above is true can someone please help explain further? I thought that making sure to modify data on the same thread would be safe.

Answer 1

Whether a data structure is threadsafe or not is inherent to it's design, not to how it's used. So unless your class, wrapping an unsafe datastructure, can itself guarantee the integrity of its internal structures, it too is unsafe.

Using an unsafe structure within a single thread doesn't make the data structure safe, but it is using it safely. Semantics.

The two arguments you presented are absurd unless you program exclusively for 233 MHz Packard Bell computers or something equally terrible.

1. Pausing and resuming threads, with regards to execution flow, is an essentially transparent process. If threads would resume in seemingly random places, how could you possibly make anything work reliably? If a thread is paused right before I initialize some variables, and it resumes at a later point where the variables are used, the program is going to explode.
2. Essentially the same deal as before. If the OS decides to randomly shuffle your memory space, how are you going to get anything done?

Anyways the issue of thread-safety only comes into play when you have multiple threads within a single process.

Answer 2

Given that:

1. Array is not a thread safe data structure
2. myArray's methods are only ever called from Foo's methods or callbacks created by Foo
3. Foo's methods and the callbacks it creates are only run in the main thread
4. all Array methods preserves Array's class invariants
5. Foo has ownership of all the objects contained in myArray, and may lease them to background threads

Then what you are doing here must also preserve Array's class invariant. In other words, you won't get into situations like, for example, myArray thinks it has four objects in its internal length fields but actually only have three valid objects in the actual memory, or you enter Foo with myArray in the middle of shifting its internal objects around. In @whatsisname's word, you're using myArray safely.

However, it may not necessarily preserve Foo's class invariant. Currently, this is undecidable because you did not present enough context for me to determine Foo's invariants.

It may also not necessarily preserve the invariant of the objects contained in the array. If myArray contains only immutable or read only data, then it's trivial to conclude that the objects are also safe; but if myArray may contain mutable data, and the background thread may mutate the objects, then determining whether or not what you do here is safe is trickier, you'll have to do an ownership analysis to ensure that all mutable data there are only leased to one thread at a time (or if they objects can be leased to multiple threads, or that they synchronize their accesses)

Answer 3

Thread safe data structures come with overhead as usage needs to be synchronized so that only one thread is mutating the data at a time. Read access may also need to be synchronized.

Thread local data does not need to be thread safe as there is no thread contention for use of the data. Access to this data is safe, but not thread safe. It is generally best to avoid thread-safe objects for local data if an non-thread-safe alternative is available. This will avoid needlessly synchronizing access.

There are techniques for two threads to safely access certain types of data structures without synchronization. This requires clear responsibilities for the data. One use for this technique would be to maintain a ring buffer of work items passed from one thread to another.