13

A useful way to do concurrent programming is, say, a Compare-And-Swap instruction, which really is two operations, executed one after the other, atomically. This was available on the IBM 370 and on the 68000 as CAS, (and on later x86's as cmpxchg, but not on the PDP-10 as far as I can tell.

The PDP-10 also allows an interrupt to occur part-way through one instruction, so there's no guarantee that even one instruction is atomic. Yet, they were sold and maintained in ASMP configurations, and in other multiprocessing topologies as well I expect, so there must have been ample support for it. How was it done in those days?

Improve this question
2
  • 1
    Interrupts partway through instruction - AFAIK, that was only possible during (a) instructions which inherently did multiple memory accesses, like BLT, and (b) effective address calculations, which happens before actual execution, so shouldn't be a problem to whatever is used for multiprocessor sync.
    – dave
    Aug 1, 2019 at 11:55
  • 6
    Standard pedant: the 68000 doesn't offer CAS; it was introduced with the 68020. The original offers only TAS — test and set.
    – Tommy
    Aug 1, 2019 at 12:08

3 Answers 3

Reset to default
12

Short Answer

It's done by use of the EXCHange instruction with interrupts disabled.

The Long Read

The PDP-10 also allows an interrupt to occur part-way through one instruction, so there's no guarantee that even one instruction is atomic.

Even the PDP-10 could disable interrupts.

How was it done in those days?

The old fashioned way of semaphores to protect the pointers to be exchanged, using the good old 3 step process.

  • Wait for semaphore to be unassigned
  • Acquire semaphore
  • Check if acquired; if not, restart.

To make this work, (only) basic memory access has to be atomic (*1).

There are in general three set of instructions used to do so

  • TS type instructions check a bit (byte) to be zero and set it if true. In either case a condition code is set to learn about success or not (*2).
    • TS on IBM 360, BSET on M68k or SBITL NS32K
  • Branch-And-Set instructions will test a bit for being set (cleared), branch if true, or set (clear) it if false. (*3)
    • BBSSI/BBCCI on DEC VAX machines
  • Exchange type instructions, which exchange a target bit/byte/word with a value in a private storage (usually a register).
    • EXCH on PDP-10, LOCK XCHG on x86 CPUs

The PDP-10 works here like the 8086 (or rather the other way around :)). To acquire a semaphore its value is first checked to signal 'free', then exchanged with a new (unique) value. If the exchange was successful (had to be checked) than carry on, else go on with error handling.

The mentioned CS (*4) is more than a basic function, but the luxury of combining the simplicity of TS with the ability to exchange whole words (addresses) at once, thus making it perfect for elegant and fast handling of linked list in multiprocessing/-processor environments.

*1 - Of course, it also has to be a basic access on the shared memory itself, no cache or alike inbetween.

*2 - TS (on the /360) is a quite nifty thing, as its function is outsourced to the memory controller and based on how core memory works. Reads on core are destructive, so content had to be written back within the same memory cycle, an otherwise never interrupted sequence. By having the test for zero done by logic in the memory controller, setting it to FF could be done within this cycle. It can't get more atomic than that.

By putting that part of the operation all the way down into the memory module, no locking was needed. It's like the perfect speed up by avoiding the costly operation at all. Of course, later, semiconductor based memory had to add a locking (and synchronisation) protocol, thus making TS as slow as a CS would be.

*3 - Strictly speaking Branch-And-Set instructions are a variation of TS where the branch according to the test result is already embedded in the test instruction, still I'd rather see them separate - much like the CS.

*4 - CS on /360, CAS on M68k, CMPXCHG on Intel x86. On RISC implementations this gets turned into two operations of Load-Link reading and marking a word to be exchanged and Store-Conditional to do the store if no other access has happened. The idea is to avoide RMW cycles. But to me it seams more of a cheap trick just handing down the problem to the memory controller (but without the elegance of the original TS) - thus adding quite some restrictions.

Improve this answer
2
  • 4
    I found this TOPS-10 SMP paper at bitsavers -- it's a dump from a DEC internal notes file and in turn is material from some book -- but it's light on nitty-gritty details.
    – dave
    Aug 2, 2019 at 12:07
  • It would be nice to see references to PDP-10 source code. Where exactly are those EXCH instructions?
    – Lars Brinkhoff
    Feb 26, 2020 at 7:42
5

I'm pretty sure that the KA-10 processor, the first of the PDP-10 processors, had a read-pause-write memory cycle that allowed retrieving and altering a memory location in an atomic operation. Otherwise, instructions like AOSE (Add One and Skip if Equal) would be vulnerable to interrupts. Edit: Also vulnerable to other processors.

Any instruction could be interrupted after it was fetched, but before it was executed. The program counter after the interrupt was dismissed would cause the instruction fetch to be repeated. Very few instructions could be interrupted "in the middle". The only ones that come to mind are ILDB, IDPB, and BLT. BLT, Block Transfer, could do thousands on memory cycles in the course of operation, and might update the referenced accumulator, or not, depending on interrupts. Also relevant is a processor flag called "First part done". This was used in the ILDB and IDPB instructions to prevent the byte pointer from being incremented twice, if it was interrupted in the middle.

In the TOPS-10 operating system, there was an operation called "requeuing a job" that took six instructions to accomplish, and interrupts were, in fact, turned off before requeuing a job, and turned back on after. The later VAX architecture had complex requeuing instructions to allow this kind of operation to be done atomically without disabling interrupts.

All of this is from memory, and I apologize for that. I wasn't able to back up the above claims from quick online searches. I have a TOPS-10 Monitor Internals Guide somewhere, but I haven't searched for it.

Edit: For the mechanics of transferring a job from one queue to another, you can read the TOPS-10 Monitor Internals Guide. The part I'm talking about is in section 6.2.1 Queue Transfers. Unfortunately, it doesn't show the six instructions I remember.
For a good discussion of semaphores, you might read the section on Shareable Resources.

Improve this answer
7
  • Ah, found this in the 1968 (KA10 era) Sys Ref Manual: To save time in an instruction that fetches an operand and then writes new data into the same location, the memory executes a read-pause-write cycle in which it performs only the read part initially and then completes the cycle when the processor supplies the new data. Presumably the "pause" when servicing processor A also prevents processor B from seeing the intermediate state of memory.
    – dave
    Aug 3, 2019 at 0:38
  • 1
    Ah yes. I overlooked the multiprocessor scenario completely, I was so focussed on interrupts. With more than one processor, concurrency control has to come from inside the memory.
    – Walter Mitty
    Aug 3, 2019 at 1:20
  • Yup - in a uniprocessor, the CPU logic can simply refrain from dispatching the interrupt halfway through (say) an AOSE instruction.
    – dave
    Aug 3, 2019 at 2:07
  • 1
    I think the PDP-10 has elements of both techniques in play. Read-pause-write memory cycles are crucial to semaphores in multiprocessors. Atomic instructions, and special features like first part done are useful for correct interrupt handling.
    – Walter Mitty
    Aug 3, 2019 at 11:31
  • 1
    Incidentally, the intermediate state on the memory location is 36 zero bits (plus parity). The read of core memory is destructive. The rewrite part of the cycle is needed within the memory controller, even when the CPU only wants to read.
    – Walter Mitty
    Aug 3, 2019 at 11:34
4

Digital Equipment Corporation designed the hardware for the AOSE (Add One and Skip if Equal) instruction so that NOTHING could interrupt it. Once that instruction started, it finished. Period. It was specifically intended for use as the hardware-based synchronization primitive.

There was a sentence in the processor reference manual that read something like "Since it takes several days at full speed to count through 36 bits, this is good enough."

Improve this answer
4
  • 3
    Found this in the 1982 Proc Ref manual, section 2.6, page 2-47. AOSE is especially useful in an interlock procedure in a multiprogramming environment. Suppose memory contains a routine that must be available to two processes but cannot be used by both at once. When one process finishes the routine it sets location LOCK to -1. Either process can then test the interlock and make it busy with no possibility of letting the other one in, as AOSE cannot be interrupted once it starts to modify the addressed location
    – dave
    Aug 12, 2019 at 23:11
  • 1
    And also as stated: Since it takes a long time to count to 2^36, it is alright to keep testing the lock.
    – dave
    Aug 12, 2019 at 23:12
  • Please consider editing your answer to add the extract from the manual (it's on bitsavers). It would be useful to add the exact code sequence used, which I omitted from my comment since it does not seem possible to get the desired layout in a comment.
    – dave
    Aug 12, 2019 at 23:14
  • FWIW, it's not stated that AOSE is the only possible sync primitive -- see previous discussion of read-pause-write memory cycle. But it does look like AOSE is the one actually used.
    – dave
    Aug 12, 2019 at 23:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .