4 ms·
Already 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 In
by adrian_b 3y ago
Already 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.
- gpderetta 3y agoAgain, nothing to do with performance. For example an interrupt handler (or a signal handler) that needs to modify some shared resource. It can't take a mutex or even a spin lock because it might be owned by the thread it just interrupted. There are ways around that of course, for example by having threads disable interrupts inside critical sections, but that's not always appropriate. Similarly, for realtime systems, if you have threads with different priorities accessing the same data, to avoid deadlocks you either need mutexes with priority inversion (which has its own share of issues) or you use lock free code. edit: in any case the point isn't that there are better ways to write a program. The point is that if you have a program that uses a CAS-based lock-free algorithm, porting it to 386 it is not just a matter of paying a performance penality, you might need to rewrite it to preserve correctness. edit2: > 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 wait-free algos have guaranteed bounds.
- cesarb 3y ago> i.e. LOCK XCHG with the Intel mnemonics. Didn't all XCHG with memory operands have an implicit LOCK prefix on Intel 8086?
- adrian_b 3y agoOnly since Intel 80286 (1982). On Intel 8086/8088 and 80186/80188 an explicit LOCK prefix is required.