3

I am trying to understand how atomic operations work, particularly in Java.

Take AtomicInteger. The document says it is: "An int value that may be updated atomically." For example, one of the operations which is atomic for this class is:

/**
 * Atomically sets to the given value and returns the old value.
 *
 * @param newValue the new value
 * @return the previous value
 */
public final int getAndSet(int newValue) {
    return unsafe.getAndSetInt(this, valueOffset, newValue);
}

As per documentation, it is guaranteed that this would be an atomic operation. However, the actual method unsafe.getAndSetInt() would have at least a few lines to execute. How then is atomicity guaranteed?

For example, if Thread-A is currently executing this code, why can't this be preempted? As I understand it is OS's scheduler which will share the timeslice among other threads, how it gets decided if a Thread is executing some atomic method, then all instructions need to get executed.

Is this arrangement done at the OS level? Is there a contract between JVM, API Call, and OS that if a Thread executing someFoo() method (assuming atomic), then it is atomic, and needs to be completed by that Thread and without being preempted?

John Kugelman
  • 349,597
  • 67
  • 533
  • 578
CuriousMind
  • 8,301
  • 22
  • 65
  • 134
  • 1
    Look at its implementation (https://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/sun/misc/Unsafe.java#l1066) and you will notice that it guarantees this by doing a `while` loop until the value is actually set. See this question (https://stackoverflow.com/questions/32634280/how-does-compare-and-set-in-atomicinteger-works) what atomically actually means (e.g. in a multi-threaded Java application one thread is guaranteed to win). In practice these `Atomic*` objects are implemented in the JT via CPU "native" `CAS` instructions (citation needed) – roookeee Jun 14 '20 at 21:10
  • @roookeee: Thanks for your comment, why can't a Thread executing `while` loop be preempted? Even if it is `CAS`, there is bound to CPU time slicing, and the scheduler can evict any thread. What makes the atomic operation to be as "all or none". – CuriousMind Jun 14 '20 at 21:15
  • 1
    There's not necessarily a requirement to avoid preemption, and neither in a multiprocessor system is avoiding preemption necessarily sufficient. In an implementation built on compare-and-swap, the instruction is used in such a way that any instruction stream gets the lock or discovers the lock was already taken. – user13463803 Jun 14 '20 at 23:30

1 Answers1

2

On some architectures, there are instructions that are guaranteed to atomically read an old value and write a new one. Others use a pair of operations called 'load linked/conditional store' (ll/cs). A load-linked operation will load a value and configure hardware to watch for whether anything happens that might disturb it. The conditional store will write the value only if nothing has happened since the last load-linked that might have disturbed the value written, and if will indicate (e.g. by setting a register to 0 or 1) whether the store succeeded. If e.g. conditionalStore returns 1 when it succeeded, an exchange operation could be implemented as:

int exchange(int *ptr, int newValue)
{
  int oldValue;
  do
  {
    oldValue = loadLinked(ptr);
  } while (!conditionalStore(ptr, newValue);
  return oldValue;
}

If anything disturbs the indicated address between the linked load and conditional store, the conditional store will have no side effects other than returning zero. If that occurs, the loop will repeat the linked load and store conditional until the two operations manage to occur consecutively.

Note that many architectures guarantee that a store conditional will always report failure if a location was disturbed, but they generally don't promise to always report success when it hasn't. Depending upon the architecture, there might be many or few false positives, and the efficiency of an operation like the exchange may be affected by how many there are. For example, an implementation might cause a conditional store to fail any time another thread writes anything into the same cache line as the object being watched, even if that other thread writes a different object within that cache line. This could potentially degrade performance, but programs collectively could still make progress if the only thing that could cause a conditional store to fail would be a successful store on another thread. If the effect of two threads each doing a load linked and then each doing a conditional store would be that both stores would fail, it would be possible for threads to live-lock. That could be mitigated by adding random delays, but in most usage scenarios that wouldn't be necessary.

supercat
  • 77,689
  • 9
  • 166
  • 211
  • Thanks for your answer. So these "atomic" operations, are they implemented natively and with the support of underlying OS? To me, without any support from OS and hardware, how is it possible? I did look up for some info online, not able to find to help understand. – CuriousMind Jun 14 '20 at 21:24
  • 1
    @CuriousMind: On many platforms, they would be implemented using native instructions without the OS having to know or care about them. Other platforms may require the use of OS routines that e.g. disable interrupts, perform the operation, and re-enable interrupts. A JVM which targets a particular combination of hardware and OS will do whatever is necessary to support the operation on that target. – supercat Jun 14 '20 at 21:27
  • How does it ensure that scheduler won't preemptive the thread (executing an atomic operation)? Can't a scheduler preemptive a thread when it is in the middle of execution? – CuriousMind Jun 14 '20 at 21:30
  • @CuriousMind: Many operating systems have ways of temporarily disabling task switching. Even if such means are only available within the OS code itself, an OS could provide a function which disables task switching, performs an atomic operation, and then re-enables task switching afterward, and a JVM implementation that targets such an OS could use such a function if necessary. – supercat Jun 14 '20 at 21:50
  • 1
    Disabling task-switching or even disabling interrupts does not help you on a multiprocessor. Ultimately you need the hardware to provide a mechanism: at least one of atomic compare-and-swap, atomic exchange, atomic test-and-set, load-locked/store-conditional, or something similar. – user13463803 Jun 15 '20 at 00:00
  • 1
    @user13463803: On a multi-processor without other suitable mechanisms, a JVM implementation could specify that the OS may only run it on one core at a time (other cores could run other unrelated tasks). My key point was that the JVM is responsible for knowing what features the target platform offers and how to use them. – supercat Jun 15 '20 at 03:30
  • 1
    Is there in fact any multiple-processor system on which the JVM is implemented that does not provide at least one suitable MP-safe instruction? I conjecture not, because such a system is close to worthless for JVM and OS alike - any process requiring synchronization primitives, including user mode code, would have to be rescheduled on to the primary CPU. – user13463803 Jun 15 '20 at 12:27
  • 1
    @user13463803: The development of Dekker's and Peterson's algorithms, which can synthesize a mutex with nothing more than strongly-ordered loads and stores, would have been unnecessary if their target platforms supported operations like atomic test and set. For loosely-coupled multitasking, the ability to force a partial or full cache flush, and optionally simply bypass the cache for selected operations, would be sufficient, especially on platforms where the memory level which is shared among processors only takes a few cycles to access after a lower-level cache miss. – supercat Jun 15 '20 at 14:57