Comment by johnklos | Hacker News Reader

Comment by johnklos | Hacker News Reader

I think the 80386's final design benefitted tremendously from the Motorola 68000, then the m68020. Had Motorola not released a proper 32 bit CPU without compromises, it could be argued that Intel would've had yet another stop-gap after the 80286, which itself wasn't intended to be a proper successor to the 8086/8088.

As it is, the 80386 came with a number of compromises. For instance, there was no cache at all beyond a 16 byte instruction prefetch queue, whereas the m68020 had 256 bytes of instruction cache. There were no atomic instructions (LOCK wasn't useful for this), which is why many modern OSes support the 80486 but not the 80386. The fact that compatibility with the 8086 required real mode or VM86 meant that it took quite a long time before software started taking advantage of the 80386's new features.

It was an important chip, but it showed us early signs of what we've come to expect from Intel: attempts to create other markets at the expense of, or with the express desire to not compete with, the x86 (the iAPX 432 then, the Itanic twenty years later), the slapdash addition of "features", such as the additions to the 80286, which then were required to be included forevermore as legacy support, the rushing-to-catch-up when other vendors had features that everyone wanted (real, flat 32 bit support then, 64 bit support twenty years later).

Still, it's interesting history!

It was a 386 that Linus Torvalds wrote the first Linux kernel on, and support for the new features of the 386 from the start was one of the reasons Linux took off instantly.

Indeed! My first taste of Linux was Slackware on a 386

More info:

"It uses every conceivable feature of the 386 I could find, as it was also a project to teach me about the 386"

https://www.cs.cmu.edu/~awb/linux.history.html

Which is probably one reason why he worked at Transmeta for a while.

I'm sorry, but I had to. "Could someone please try to finger me from overseas".

Yeah, a free (as in freedom, but also as in beer) OS running on hardware that was, by then, commoditized, what's there not to like? No wonder Google and others jumped on it...

Not only Linux, all the current BSDs share a lot of “DNA” with 386BSD.

> 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.

Disabling 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.

cli

jmp far $-4

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).

I 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.

Lock-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).

Well 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.

I 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.

Again, 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.

An interrupt handler may use neither lock-based methods nor lock-free methods, because it may not remain stuck in a wait loop as required by the former and it may not use a CAS instrution as required by the latter, because any CAS instruction must be retried when it fails.

Therefore an interrupt handler must always own whatever data structures it writes into, so it may write them at any time.

Lock-free methods are not used inside interrupt handlers, but they are used by the code that reads what the interrupt handlers write. However this is the special case of single writer with one or more readers and this special case of lock-free access does not need compare-and-swap instructions or equivalents.

For some particular cases, like counters that are updated by interrupt handlers, the readers can detect corrupt values and retry the reading, while for other cases, when the interrupt handler updates a more complex data structure, that can be guarded, for example, by a counter that is incremented both before and after the updating, so that the readers may be able to detect when they have to retry the reading.

This special case of lock-free access does not need compare-and-swap, but, depending on the CPU memory access model, it may need store barriers a.k.a. store fences and load barriers a.k.a. load fences. Such lock-free access was trivial to implement on Intel 8086 or even earlier CPUs, because it does not even need atomic read-modify-write instructions.

Normally, when lock-free algorithms are discussed, it is assumed that there are multiple writers, when different algorithms are needed than for the single-writer case, and when CAS instructions or equivalents are needed.

There is no need for lock-free algorithms for avoiding deadlocks. The obvious solution to avoid deadlocks is to use a single lock protecting all shared data. Lock-free algorithms may provide a much better performance, but they are not necessary.

Moreover, even without lock-free methods, deadlocks may be avoided in most cases by reorganizing the shared data. Any program where it is necessary at any point to hold multiple locks, is suspect of having a bad data organization, because this should not normally happen.

You are right that wait-free algorithms by definition have guaranteed bounds, but unfortunately they are seldom applicable, otherwise concurrent programming would have been much easier.

> i.e. LOCK XCHG with the Intel mnemonics.

Didn't all XCHG with memory operands have an implicit LOCK prefix on Intel 8086?

Only since Intel 80286 (1982).

On Intel 8086/8088 and 80186/80188 an explicit LOCK prefix is required.

Reply on news.ycombinator.com