3 ms·
> There were no atomic instructions (/LOCK wasn't useful for this), which is why many modern OSes support the 80486 but not the 80386. Does the lack of atomics
by zozbot234 3y ago
> There were no atomic instructions (/LOCK wasn't useful for this), which is why many modern OSes support the 80486 but not the 80386.
Does the lack of atomics really matter, given that there was (AIUI) no SMP on the 386? You can always disable interrupts to make your operation 'atomic' in a uniprocessor context.
- jacquesm 3y agoDisabling interrupts is a privileged operation (you need IOPL for the ability to execute the cli or sti instructions). Atomics can work even outside of privileged code. Otherwise you could from any user program disable interrupts and give the operating system no chance to take back control. Xadd, cmpxchg, bts, btr and btc are all prefixable with lock to make them atomic.
- jhoechtl 3y agocli jmp far $-4
- adrian_b 3y agoAlready starting with 8086 all Intel x86 CPUs have been intended to be usable in SMP systems. Nevertheless, there have been very few SMP systems using early Intel CPUs, before 80486, mainly because those CPUs were still too weak in comparison with the contemporaneous mini-computers, and not even SMP would have made them competitive in performance, while the high price of SMP would have been incompatible with personal computers. Intel 80486 has been much more frequently used in SMP systems, not only because it had added the more convenient atomic fetch-and-add and compare-and-swap instructions, but because Intel had also provided for 80486 an APIC integrated circuit, i.e. a multi-processor interrupt controller, and also because 80486 was very fast and a SMP system using it was competitive with much more expensive computers. Intel 8086 was intended to be used in SMP systems by using the atomic swap instruction proposed by Dijkstra, i.e. LOCK XCHG with the Intel mnemonics. The atomic swap is good enough to implement any kind of concurrent programs, albeit at a lower performance and higher complexity than when the atomic instructions added by 80486 (LOCK XADD and LOCK CMPXCHG) and Pentium (LOCK CMPXCHG8B) are available. The 80386 has added atomic fetch-and-modify-bit instructions, which remain useful even today in wait-for-multiple-event scenarios (together with LZCNT, which can be used to get the highest-priority event that must be serviced).
- gpderetta 3y agoI don't think exchange is enough to implement all (or even most) lock-free/wait-free algorithms. CAS (i.e. lock cmpxchg), or an equivalent primitive in power, is needed. XCHG is enough to implement a mutex though, which is what most applications need.
- adrian_b 3y agoLock-free and wait-free algorithms are not necessary for any computing task. They are only a performance enhancement and they indeed require either compare-and-swap (simple and double) from the IBM System/370 (1973) (later used by Motorola MC68020, then simple compare-and-swap was added to 486 and double compare-and-swap to Pentium) or load-locked + store-conditional from the S-1 Advanced Architecture Processor (LLNL, 1987) (later used by MIPS, then by POWER, ARM and others). Moreover, even for improving the performance the lock-free and wait-free algorithms must be used with care, because they are based on optimistic assumptions that may fail to be true in many scenarios with heavily contended shared resources, when the performance of the algorithms based on mutual exclusion is actually higher and more predictable (with mutual exclusion it is easy to guarantee FIFO access to a shared resource, which ensures that the wait times are bounded and that at any moment there is at least one thread that does useful work instead of retrying failed accesses to the shared resource).
- gpderetta 3y agoWell you mention that you can implement all programs, I just wanted to clarify that there are indeed some algorithms that cannot be implemented. In any case this has nothing to do with performance, you might need lock-free algorithms for correctness when implementing some real-time systems or when you need code to be reentrant.
- adrian_b 3y agoI am curious to hear an example where a lock-free algorithm is needed for correctness, because I have never encountered any such case and this does not seem possible. Access to any kind of shared resource is always correct when only a single thread can access it. With mutual exclusion it is very easy to guarantee correctness due to serialized accesses. With lock-free algorithms concurrent accesses are possible and the algorithms must be carefully analyzed to demonstrate their correctness. Moreover, exactly in real-time systems is where lock-free algorithms are undesirable. Any pure lock-free algorithm must detect a transaction failure and retry it. There is no guarantee of success and no limit for the number of retries, so any hard real-time deadlines can be missed. Lock-free algorithms can be used in real-time systems only if they detect too many retries and then they fall back to lock-based algorithms before it is too late. The lock-free algorithms improve only the execution time of the typical case, but they increase the execution time for the worst case. For non-real-time applications the typical performance is more important, so lock-free algorithms are good, but for real-time applications the worst-case performance is the most important, which makes lock-free a.k.a. optimistic algorithms bad. Also neither mutual exclusion nor lock-free/wait-free algorithms have any problem with reentrancy when implemented correctly. Problems with reentrancy appear only in programs where there are mutable variables that are shared between threads and which should not have been shared (like when using some of the old standard C library functions). It is very common to have a very large number of threads that use reentrantly the same code that implements mutual exclusion for accessing some shared resource that is guarded by a lock.