Timesharing on the MIT Weather Radar PDP-8/IX

I’m sure that by now you’ve seen plenty of weather radar images—high resolution digital images of what we might informally call rainfall intensity. I’m also sure you get the basics of radar—microwave pluses are transmitted in known and controllable directions, and echoes from objects such as planes, ships, and rain (and many other types) are received. The objects can be located in space using the known direction of the beam, and by multiplying the speed of light by half the elapsed time between transmission and reception to get range (half because it’s a round trip).

Let’s fill in some details to see what WR66 and WR73 were actually doing, what the PDP-8 interface did, what hardware and software signal processing was done, and what the rainfall intensity in those images you’ve seen actually means. We’ll see that measuring rainfall with radar is not at all like finding planes and ships, and that there’s a big difference between what a radar set can directly measure, what we’re trying to measure, and what we’d actually like to measure.

Unlike planes and ships, raindrops do not reflect microwaves because they are much smaller than the wavelength, 10 cm for WR66 and 5 cm for WR73. Instead the beam wiggles electrons in the drops, which causes a tiny amount of energy to be absorbed as heat and most to be reradiated in all directions, a process called scattering. The scattered energy is not directionally uniform, however—a significant amount, called backscatter, is radiated directly back towards the radar. Scattered power is proportional to the sixth power of the drop diameter, and inversely proportional to the fourth power of the wavelength, according to a formula derived in 1871 by Lord Rayleigh, who used it to explain why the sky is blue.

Frozen water is different. Snow backscatters much less power than raindrops. Hail is very different—hailstone diameter is no longer much smaller than wavelength, ice can act as a lens, and power radiated back to the radar can produce echoes much stronger than even severe rain.

The backscattering of a unit volume of space, called reflectivity and denoted by the symbol Z, is proportional to the sum of the sixth powers of the drop diameters in the space. If we define a reference value Z0 as the reflectivity of a one cubic meter volume containing a one-millimeter raindrop, we get dbZ = 10 log(Z/Z0). We use log ratio because reflectivity has enormous dynamic range, easily five orders of magnitude, and the radar receiver uses a log amplifier. We use decibels because we’re effectively dealing with power ratios. dbZ is what we’re trying to measure, and what the intensity scale in weather radar images actually is.

I say “trying to measure” because the only thing that the radar receiver can directly measure is power. Measured power is a function of:

  • transmitted power

  • antenna gain—how much power ends up in the desired direction, rather than off to the sides

  • reflectivity, i.e. dbZ

  • range according to an inverse square law if the volume of rain fills the beam, or inverse fourth power if it does not

  • attenuation of power caused by intervening rain absorbing some of the energy

Clearly one must accurately know the transmitted power and antenna properties. Range is easy, and I’ll say more about attenuation below. Speed was meticulous about radar calibration, monitoring transmitted power with a bolometer and periodically measuring antenna gain. I remember going up to a high floor of the old Hancock building in Boston across the river from the Green Building for antenna calibration. We used the old Hancock building because it was tall and you could open the windows. From the radar room the antenna would be moved in various directions, we’d record received power from the open window, and Speed would make a plot showing gain as a function of angle from beam center.

Attenuation is negligible at 10 cm, noticeable at 5 cm, and very significant at 3 cm. Airborne radar generally uses 3 cm because the dish is small enough to fit on the plane, but attenuation means that you can’t see very far into severe weather. At Weather Radar we’d study attenuation by comparing WR66 and WR73 returns when pointing in the same direction, and part of WR73 software signal processing tried to correct for attenuation.

With careful calibration we could get dbZ from measured power, but what we really wanted to measure was rainfall rate, e.g. mm/hour. The contribution to rainfall rate of a raindrop is proportional to drop volume, i.e. third power of diameter, times terminal fall velocity.

Fall velocity is very complex due to aerodynamics—drops deform into little parachute shapes. I remember encountering Speed in the stairwell on the 18th floor sending drops of various sizes down to the ground floor to measure fall velocity. I was surprised that it couldn’t just be computed from basic physics, and maybe it can be with today’s computers, but back then it was strictly empirical. He could determine velocity and drop size using a device called a disdrometer, invented by our Swiss colleagues Jurg Joss and Albert Waldvogel.

Fall velocity is roughly proportional to the diameter of the drop, so that rainfall rate is roughly proportional to the sum of the fourth powers of the drops in a unit volume. Estimating rainfall rate from dbZ requires knowing the drop size distribution, and that’s the main reason the Joss- Waldvogel disdrometer was invented. Before that invention, radar meteorologists used specially treated paper that turned some color (purple?) when wet, leaving marks whose size could be catalogued by, you guessed it, grad students.

Drop size distribution depends on the nature of the storm and where in the world you are. Lots of empirical work has been done over the years to develop generally useful formulas to estimate rainfall rate from dbZ (the R-Z relation). Quite a bit of early (1950s), large disagreements between what was expected from measured distributions and what was measured by radar were due to miscalibration. Some of the best early work on R-Z was done with meticulous care by Polly and Speed.

One more thing to keep in mind—radar waves do not travel in a straight line. The index of refraction of the atmosphere depends on pressure, temperature, and humidity, and therefore changes with altitude. With typical atmospheric conditions a radar beam travels in a circular path whose radius is about 4/3 the radius of the earth. Under unusual conditions the beam can actually curve so much that it strikes the ground at substantial distances, generating ground echoes far from the radar. This is called anomalous propagation. If you’re looking at a radar image and notice patterns that look like the shape of topographic features, for example Cape Cod from a Boston-based radar, that’s anomalous propagation. Storms don’t accidentally look like that.

In addition to unusual atmospheric conditions, echoes can be returned from buildings, mountains, birds, insects, and the like. One was always advised to approach weather radar images with due skepticism of the cause, and Speed was famous for doing so. A strong echo from Mount Monadnock in New Hampshire always appeared on our PPI’s 100 km range ring, and seeing it gave confidence that radar azimuth and timing were correct.

The rainfall reflectivity of a given volume element varies rapidly with time due to various factors. The only way to get a useful measurement of dbZ is to average the signal at every point over a number of transmitted pulses. With very early weather radars, due to the limitations of 1950s electronics, this could only be done one point in space at a time using what was called a pulse integrator. Next came the analog sweep integrator, which used an analog delay line to integrate the signal along all ranges as the antenna moved in azimuth. The result was what was being photographed when I arrived in 1973.

By the early 1970s digital sweep integrators were being deployed. These sampled the signal in small increments called range bins, what today might be called pixels or voxels, and summed in each bin A/D converted samples. Typically 16 or 32 pulses would be summed in hardware and made available to software for further processing.

The Air Force digital integrator we inherited had 100 range bins, with spacing that could be programmed to 0.5, 1.0, or 2.0 nautical miles, equal to 0.93, 1.85, or 3.70 km. The integrator would start those 100 bins after skipping a programmable number of sample periods. It had a relay to choose what the Air Force thought was forward or side radar, and for us was WR66 or WR73. I can’t tell from the source code how many pulses it integrated (I was very naïve about comments), but I’m thinking 16.

At round trip speed of light, 0.5 nmi is 6.17 microsecs. That’s well within the capabilities of available sample-and-hold and successive approximation A/D converters of that era. Flash A/D converters hadn’t been developed yet, but weren’t needed.

Both radars had a 1 degree beam, often called a pencil beam. At 10 cm WR66 needed the 18 foot dish to get a beam that narrow; WR73 at 5 cm needed only 8 feet. During recording the radars would be swept in azimuth a rate of 1 degree per integration period, that is 1 degree per 16 pulses. We used a pulse repetition frequency (PRF) of 250 Hz, so 16 pulses is 64 ms, and the radar would sweep at 15.6 degrees/sec, or 23 seconds per rotation. Double those values for integrating 32 pulses. After a full rotation the radar could be stepped in elevation for 3D coverage. The PDP-8 could control both sweep speed and elevation.

PDP-8 software would dump the integrator to a memory buffer for further processing. When a radar is first selected, a noise level is determined by setting the integrator to 1 nmi samples, skipping 215 sample periods, and averaging the 50 most distant bins. Those 50 bins are beyond the range of any expected echo, partly due to curvature of the earth and partly to the inverse square power law. A noise threshold was established slightly above the measured noise level, and any range bin below this threshold during normal processing would be considered to be no echo.

During normal processing, after noise thresholding the bins would be corrected for the inverse square power law. Since we’re dealing with log power, this was done by simple addition using a memory-resident table. The bins would then be run-length compressed for writing to DECtape. Because most bins have no echo, the compression reduced the storage requirements substantially.

Both radars transmitted a 1 microsecond pulse, called the main bang. WR66 could put out a megawatt for that time, which is 250 watts average power at PRF 250. WR73 could do around 250 kW. The receiver was incredibly sensitive, capable of detecting returns at or below one picowatt. Since the transmitter and receiver shared the antenna and waveguide, the receiver had to be electronically isolated during the main bang to avoid being destroyed.

The integrator that Ken designed for GATE was far more sophisticated. It executed microcode instructions to allow variable-length bins and signal processing beyond just integration. We generally programmed it for 0.25 km bins in close, 0.5 km at mid range, and 1.0 km at far ranges. The bin sizes were set to approximately match the 1 degree beam spreading as a function of range. We experimented with various signal processing methods to distinguish high-variability rain echoes from low-variability ground clutter.

Sometime after I finally left the project n 1980, WR66 was augmented for doppler. This could be done because the klystron is a coherent amplifier, so the phase shift from pulse to pulse is stable and tiny phase shifts can be determined by suitable signal processing. Magnetrons are incoherent, so WR73 couldn’t be used for doppler. It’s fascinating to note that the doppler effect for electromagnetic radiation is caused by relativistic length contraction and time dilatation. You’d think that these effects are negligible at terrestrial speeds, and indeed they are very small, but detectable by electronics. The doppler signal processing was designed by Alan, a brilliant engineer and great colleague of mine in the later years.

Next up the PDP-8/IX. What, why, and how.

6 Likes

I’m particularly looking forward to read about the PDP-8/IX. Maybe it’s a special hardware modification, akin to MIT’s PDP-1/X. I’ll stay tuned.

1 Like

Excellent and fascinating physics background!

1 Like

In addition to my own memory, my sources for the post on radar meteorology include

Radar Observes the Weather by Louis J Battan, Anchor Books, 1962.

Chapter 4 Weather Radar at MIT, by Pauline M Austin and Spiros Geotis, in Radar in Meteorology, edited by David Atlas, American Meteorological Society, 1990.

RADAR PAL8 source code listing

3 Likes


In the Beach Boys Little Deuce Coupe, a hotrod enthusiast is excited to tell us how he modified his 1932 Ford Model 18. Its “flathead mill” (engine) had been “ported and relieved” and “stroked and bored”; “She’s got a competition clutch with the four on the floor; And she purrs like a kitten 'till the lake pipes roar”. He didn’t do this to get to work faster, or even to have “the fastest set of wheels in town”. He did it because he could, and for the emotional thrill of experiencing the result, ending his story with, “I get pushed out of shape and it’s hard to steer; When I get rubber in all four gears”.

Because I could, and for the emotional thrill of experiencing the result, goes a long way to explaining why I did what I’m about to describe. Sure, it was practical and very useful, but that alone wouldn’t have been enough. Timesharing was a big deal at MIT back then, with Multics and ITS and the PDP-1, and I wanted in on the action. But first I had to fix the PDP-8.

The first program I wrote to record radar data was called RDS, for Radar Data Storage. The name was totally lame, and I got better at naming later in my career.

RDS computed the noise thresholded, range normalized, run-length compressed rays, added a timestamp and radar position (azimuth and elevation), and appended the result to a large buffer for eventual writing to DECtape. It was an ordinary OS/8 application—interrupts off, polled I/O, and relying on OS/8 for the DECtape device driver and file system. A separate program would read the files and generate displays.

The meteorologists were thrilled. Finally we had recorded digital data, and the PDP-8 that had ben hauled up to the 18th floor and hooked up to the radars was no longer just taking up space in the radar room. The turnaround time between recording and display generation was much shorter than with film. One couldn’t generate displays for analysis while also recording, however, so on a stormy day the analysis would have to wait. But no one was complaining about that, or even imagining that anything could be done about it.

But I could see that the 8 had plenty of idle cycles during recording. Running a competent command interpreter, recording app, and various display apps, all simultaneously sharing the CPU, was possible. That was my rationalization for doing what I wanted emotionally—timesharing. I asked no one for permission to spend my time that way, and I don’t think I even explained to anyone what I was up to.

I quickly realized that the PDP-8 instruction set was going to be a big problem. I was going to need to use multiple instances of various data structures, where a subroutine would be given the address of an instance and use it to access various elements of the structure. With only indirect addressing, the cost in time and space, and opportunities for bugs, was more than I could stand.

For example, consider a structure with elements A and B, and a subroutine that is passed the address of an instance of the struct in the AC. Suppose the subroutine needs the logical AND of A and B. Here is what the code might look like:

        TAD (A
        DCA PA
        TAD PA
        TAD (B-A
        DCA PB
        TAD I PA
        AND I PB
        …
PA,     0
PB,     0

That’s 11 words of memory (including the literals) and 16 memory cycles. And it’s not reentrant, although there were various hacks for fixing that problem. What I really needed was an index register (X), so I could write

    LDXC        / LOAD X AND CLEAR AC
    TAD X+A
    AND X+B

That’s just 3 words and 5 cycles, or if the address is passed in the index register, 2 words and 4 cycles. The PDP-8/IX would be a PDP-8 with an index register!

There were three problems to solve:

  1. How to load and read X. This would be easy, X would just be an I/O device.
  2. How to modify the instruction set, which would seem to have no unused opcodes or mode bits to work with.
  3. How to modify the CPU to add X for effective address calculation during defer or execute cycles.

What gave me the confidence to do this crazy thing were these factors:

  • There was an elegant solution to #2.
  • There was a surprisingly easy solution to #3.
  • The 8/I was made from TTL SSI, and by then I was reasonably competent and confident with digital electronics.
  • We had a great TTL lab, with parts, tools, supplies, oscilloscopes, etc.
  • The 8/I had a wire-wrapped backplane.
  • We had the 8/I schematics.
  • The R-series Flip Chips had some spare gates.
  • I wanted it.

Instruction Set Mods

On the PDP-8, I/O instructions were coded 6xxy (octal), where

  • 6 is the opcode for I/O
  • xx selects one of 64 devices for the operation
  • y is three separate bits, each typically enabling some action, where setting multiple bits enables each of the actions in sequence.

The 8/IX had a 12-bit index register and a 3-bit mode register. Here are the I/O instructions:

Opcode ASM Operation
66x1 LDX Load X from AC
66m2 SXM Set X mode to m
66x4 XCLA Clear AC
66x5 LDXC Load X, clear AC
66m3 LDX SXM Load X, set mode to m
66m7 LDXC SXM Load X, set mode to m, clear AC
6071 ISX Increment X, skip if 0
6072 RDX Load AC from X
6074 RXM Load AC bits 6-8 from mode, clear other bits

As you can see, 9 I/O device addresses were used, 6x and 07. I think I implemented the X register with 74LS169 up/down counters for the ISX instruction, but I don’t think I ended up using it. When I designed the system it wasn’t yet clear what all the usage patterns would be. From the source listing it seems that I used only three of the 8 modes, 0, 6, and 7. I don’t remember what the other modes did.

Mode Operation
0 Normal PDP-8 addressing, default on system reset
6 Any direct access to the second half of page 0 becomes relative to X, in the current instruction field. Addresses 01dd became X+dd.
7 Same as 6, except use the current data field.

The assembler symbol X was defined to be 0100. So, for example, TAD X+FOO would access memory location X+FOO, 0 <= FOO < 0100. TAD I X+FOO would access the memory location at the address held in location X+FOO. A key insight here is that 64 locations in the first half of page 0 was plenty, as long as you didn’t use page 0 literals, which the assembler put at the end of page 0. Furthermore, no data structure need be more than 64 words.

CPU Mods
Here is a grossly oversimplified data flow block diagram of the PDP-8/I CPU, suitable for present purposes:


The interface and register busses are wired-OR busses, common in older TTL designs before tri-state bus drivers were used. The blue arrows signify that the data lines can be either gated onto the bus or held at logic HIGH. This is why I/O transfers to the AC often OR the data with the AC. All data transfers go through the adder. For a straight transfer, the adder operand not participating in the transfer has no data gated onto its bus.

For effective address calculation, a 12-bit address is formed as follows:

PC bits 0-4 are gated onto the corresponding bits of the register bus if instruction register (IR) bit 4 is 1, to select either the current page or page 0. IR bits 5-11 are always gated on. The output of the adder is latched into the memory address register to begin the next memory cycle. So all I had to do to generate X+OFFSET is detect a direct address calculation cycle with IR bit 4 = 0 (page 0) and IR bit 5 = 1 (second half) in modes 6 and 7, and do this

  • gate the X register onto the I/O bus as if it’s an RDX instruction
  • gate off IR bit 5
  • force use of the current data field in mode 7

Very simple logic using the existing busses and adder!

I was quite nervous with the wire wrap gun and unwrapping tool in my hand ready to alter a CPU that did not belong to me, without any authorization to do so. But I went ahead and it worked. Phew.

Next up, finally, the RADAR timesharing system. I haven’t yet decided how I am going to organize the posts, or how many they will be.

6 Likes

Yes indeed! But a splendid idea.

You got lucky with that version of the pdp-8, that you could modify it that way.

Is you code preserved? I wager it would be an interesting exercise to add your PDP-8/IX modifications to an emulator - that part seems easy enough - and get your timesharing system up and running.

Yes, but lucky doesn’t begin to describe my great good fortune. In 1973 I was a shy, socially awkward kid, surrounded at MIT by some of the best engineering minds in the world, and also by students my age who had been programming for years in high school. I was the top math student in my New Jersey high school, but so was pretty much everyone else in theirs. I wrote previously that the PDP-1 room was intimidating, but so was the entire school. I wrote that code comes naturally to me, and indeed I have a gift for software engineering, but I did not know that back then. I had no idea what I might be able to do.

Weather Radar gave me practical experience that one simply cannot get in the classroom, and that I couldn’t get even during my grad school years at the AI Lab, as awesome and important as those four years were. Most important, it gave me confidence.

Just getting the job was a stroke of luck. I had worked the previous summer in a NJ department store, and I was desperate to do just about anything else. The EE department was moving from building 10 to its new facilities in buildings 36 and 38, and I figured there might be work available. I could help wire up lab benches maybe. So I found someone who seemed in charge and asked for a job, and he said yes. As I was walking away, happy that I’d found work, I just happened to turn my head and saw a notice on a bulletin board seeking a student to work at Weather Radar. That seemed like it might be more interesting than helping EE move, so I put on a collared shirt and tried to make my wannabe-hippie hairdo somewhat presentable. I met Speed and he asked me if I knew wire wrapping. I said no, but I knew how to solder. So they gave me a soldering test and I guess I passed.

1 Like

Yes, it would be easy to add to an emulator, but I have no machine-readable source. What I have is a PAL8 listing on old, fragile, specially treated, fan-fold paper. I suppose it could be scanned, but it would have to be a painful manual process because I don’t think a document feeder would work. Then I’d have to trust OCR to produce usable source code. I’d rather spend my retirement years goofing off with my wife.

The careful reader may wonder about my description of a wired-OR bus where data lines not gated onto the bus would be held at logic HIGH. Seems like an AND, not an OR. A wired-OR bus, however, was driven by TTL NAND gates with open-collector outputs, like the 7401. An open-collector output is an NPN transistor that can either pull the data line low (ground) or leave it open circuit for other devices to control. If no devices are pulling low, a single pullup resistor establishes logic HIGH on the line. Since NAND gates are used, the signals on the bus are inverted, so that LOW means 1 and HIGH means 0. NAND gates were used because they are the simplest, most basic TTL logic gate.

I fully understand, I and I wouldn’t suggest you put any significant amount of time into it. It would be nice if the paper listing could be preserved for posterity, but maybe it’s difficult if it’s fragile. I once arranged to meet someone bringing his listings and I set up a tripod with a camera to take pictures of ever page.

I’ve been studying the RADAR listing more carefully to refresh my memory about some of the timesharing details and I’ve discovered what the very useful index mode 4 does. It creates what might be called a global page 0 by providing direct access to field 0 page 0 from any field.

On a normal PDP-8, code has direct access to the current 128-word page (as determined by the PC) or the 128-word page 0, both in the current instruction field. Access to anywhere in any field is provided only by indirect addressing. Page 0 is intended to be a common area for the current instruction field, but there is no direct access common area for the whole memory space.

On the PDP-8/IX, mode 7 provides direct access to the current data field for index-relative addressing. Mode 4 makes all direct access to page 0 go to field 0. Direct addresses in the second half of page 0 are still index relative; direct addresses in the first half are not index relative but forced to field 0. Thus we can put system-wide common data in field 0 and have direct access to it.

My view of the history of stored program machines is that the most important architectural developments have been in address calculation, most notably the IBM 360 and the PDP-11. That’s a discussion for another topic, but suffice it to say that address calculation has a big impact on software architecture. The IX that I devised is something of a kludge, but an important one for what I was trying to do.

1 Like

2 posts were split to a new topic: The importance of the introduction of byte addressing

A stored program machine consists of a processor and an addressable memory. The processor is a finite state machine with two kinds of state—programmer visible and internal. For example, on the PDP-8 programmer visible includes AC, Link, PC, MQ, and instruction and data fields. Internal includes memory address and buffer registers, fetch/defer/execute cycle state, and others. Any stored program machine that can write to memory a complete snapshot of its programmer visible state, and can restore from memory that exact state, can support timesharing. The rest is details.

OK, you also need an interrupt system and a clock.

I don’t remember when I had this insight, whether it just occurred to me one day or whether I absorbed it from the ether at MIT. My memory is that it occurred to me, but I’m not sure my memory should be trusted. But once I grasped it, I knew I could write the code.

What I clearly learned from coursework and, most notably, from the PDP-1 Instruction Manual Part 4 – Multiprocessing is how the programmer interacts with such a system, and the terminology then in use. Fork, semaphores, Dijkstra’s P & V, critical races, character I/O, all that stuff. Once I learned how such a system is used, I knew how to fill in those pesky details.

I’ve been rethinking my previous response to Lars about preserving the code, and realized that, as much as the paper listing has sentimental value, a PDF would have concrete value. The timesharing kernel is 24 pages. So I carefully separated the fan-fold paper (printed 49 years ago) and manually scanned each page, then ran OCR. Here is the scanned kernel and here is the OCR version. I don’t know how accurate OCR is these days.

Over the next week or so I’ll post commentary on the various pieces in the kernel. We can have a nice yack about it.

3 Likes

Thank you. OCR accuracy is rather varied. I have often found that typing is less work, and I have done batches much larger than 24 pages. It can be a nice way of getting to know a program since you have to read every single line.

EDIT: I checked the OCR’ed PDF, and it’s very garbled. I have typed a few pages so far.

Yes, pretty garbled. I just used Adobe PDF OCR. Maybe someone has something better.

Questions and comments about the source code are welcome. Explanatory posts coming. More scanning coming next week.

(Uploaded with permission to the Internet Archive here - but as expected, the OCR there isn’t much good.)

The RADAR timesharing system was implemented by code in field 0, with radar-specific applications in fields 1 and 2. I called the field 0 code the Processor Management and Input/Output System (PMIO). You can see this name in the very first line of the source code, and PAL8 took the first 31 characters for the title it puts at the top of each page of the listing. I called it PMIO because I had learned in coursework that the purpose of an operating system is resource management, where resources include the processor, memory, and I/O devices. PMIO manages all of those things on the PDP-8.

The timesharing kernel that I posted is the core portion of PMIO and implements what I called processes, what today would be called threads. We’ll get to other parts of PMIO is subsequent posts.

Quoting from the MIT PDP-1 Multiprocessing, which I linked to in a previous post: The “thing” that runs around in a program executing it is called a virtual processor, or process.

Each process has a Process Control Block (PCB):

It contains:

  • a forward pointer for making lists and queues
  • a priority, further described below
  • a pointer to a list of working registers (WR), analogous to what today we’d call a stack frame
  • programmer-visible state

PCBs and WRs were allocated as needed on what we’d recognize as a conventional heap, using alloc and free routines in PMIO. I called this based storage after PL/1 terminology; you can see this in comments. You’ll notice for example page 0 “variables for based storage routines”, with names that start with AF for alloc/free. You’ll also notice with great amusement on listing page 2 “SBSSIZ=600”—the total size of the heap is only 6008 = 384 words!

The world was very small, slow, and expensive back then. The four fields of memory I had to work with were less than half the size of the level 1 data cache on my Raspberry Pi 5. The 8 executed a two-cycle instruction in 3 microsecs, during which time the quad-core superscalar ARM on the Pi 5 could do around 30,000 instructions, including 128-bit SIMD parallel ops. A base PDP-8, the lowest price computer in the world at the time, would have cost around $150,000 in 2026 dollars; the Pi 5 around $70.

Everything that I’m going to discuss below runs as part of the interrupt service system. In addition to the interrupt priority encoder we got from the Air Force, we got an interrupt mask (see the definitions on listing page 1-1). Most of interrupt service ran with interrupts on but every device masked off except DECtape, which needed immediate service (see listing page 4). We’ll get to the DECtape handler some other time.

Process priority looks like this:

Base priority and NTQ were established at process creation time by an argument to FORK. The I/O bit was established dynamically to distinguish processes that were judged to be either I/O bound or compute bound. When a process was scheduled to run it was given a time slice equal to 50(NTQ+1) milliseconds (NTQ means number of time quanta). If the process used all of its time slice without becoming blocked waiting for I/O, it was judged compute-bound and the I/O bit was cleared. If it became blocked before the time was used it was judged I/O-bound and the bit was set.

The dynamic priority of a process was bits 0 – 8, so that all I/O-bound processes had higher priority than all compute-bound ones.

Every process was in one of three states:

  • running
  • ready to run
  • blocked

The RUN variable on page 0 pointed to the running PCB, or null if none. The READY variable pointed to the list of ready PCBs, or null if none were ready. All blocked PCBs were found somewhere on the queue of a semaphore in field 0. Semaphores were for Dijkstra-style P & V operations, what Multiprocessing calls programmed queues. Every I/O device had an associated semaphore.

The subroutine CHPCB was the process scheduler. Its job was to place a PCB on a list (i.e. ready list or semaphore queue) in order of decreasing priority. An argument called HQ was passed in the AC to determine how to schedule PCBs with equal priority that may already be on the list—0 for after, 0010 for before.

When an interrupt occurred:

  • save the state of the running process
  • determine the highest priority device that raised the interrupt
  • mask off all interrupts except DECtape and turn interrupts back on
  • JMP to the handler for the device, which must
  • do device specific actions, including clearing the interrupt, and possibly removing the highest priority process from a semaphore and scheduling it on the ready list
  • enter the traffic controller, which
  • if no ready process has higher priority than the running process (if any), continue the running process
  • otherwise switch processes so that the highest priority process that is ready becomes running
  • restore the state of the running process and exit interrupt service
  • but if there is no running process enter a wait loop that tracks the idle time for periodic display

I can see two flaws in the system.

First, the PCB does not include the EAE step counter (SC). This would only affect the normalize instruction (NMI), which would cause a nasty bug if that instruction were used. Nasty because there would be a tiny but non-zero probability that the bug would be symptomatic, and those bugs are hell to find. NMI is generally used for floating point emulation, which I did not do, so it’s likely that I never used NMI. I don’t know if not including SC was an oversight or a deliberate choice, but if it was a choice then the absence of a comment saying so is a major sin.

Second, the judgement of I/O bound or compute bound is flawed because a process’s time slice is reset every time a process switch occurs. Thus a process may never make the desired transition from I/O bound to compute bound, depending on unrelated I/O activity. This was unavoidable because there was no way to read the current count in the interval timer and save it in the PCB. The evidence suggests that the interval timer did not come from DEC or the Air Force, rather I added it. If so I didn’t provide for reading the current count, bad on me.

More to come in subsequent posts. Questions and comments welcome.

4 Likes