8-bit, limited register sets, multitasking, explained with paper cutouts, good stuff.
4 Likes
Well, duh, of course you can do multitasking on that. After all, it’s been done on a PDP-8, which is a far more limited machine than a Z80.
The main things you need are interrupts, and subroutines that support re-entrancy. The latter is easier if the instruction set does it, but it can be constructed if the instructions are unhelpful. You do need a way to find out th return address, which is why Dijkstra rejected the IBM 1620 (it doesn’t have a way to do that, and come to think of it, it doesn’t have interrupts either).
Don’t forget a MMU is needed, even a simple one that just swaps in 32K banks and a 8080 is ample.
Not swapping to disc would make it rather fast.
No it’s not. There are plenty of multitasking systems out there, especially real-time ones, that don’t use an MMU. The famous THE operating system, from 1964, is one example; so is the RSTS-11 timesharing system (DEC, 1973).
2 Likes
Those early machines were more proof of concept, than real mult-user use.
The concept of virtual memory does require hardware changes, and that I think is the
defining idea, for modern time sharing.
The Z80 really only had the speed factor with time sharing over the 8080.
The better 6089 did have time sharing, but a MMU was needed for the best performance with os/9 level 2.
I think you might be confusing several considerations there, @oldben. I agree with @pkoning (and many others) that an MMU is not necessary for multitasking. I’d go further, and allow even for multiuser, depending of course on the culture and the users and the usage.
One can of course have opinions about what’s better, or more convenient, or more performant, or more practical. But one needs to be careful in wording such things. There’s such a thing as being too brief. Being too brief can even appear confrontational - always consider your audience.
I was reading Dr, Dobb’s (vol 3?) on a 8080 multasking/multuser system, that used banked memory.
At that time CP/M was the main 8 bit OS, thus my foolish statement, as multi user was on my mind
rather than multasking.
? June/July vol 3
The purpose of this letter is to introduce UNIX for the
8080 microprocessor. The system is called CHAOS, an acroÂ
nym for Clairemont High ALTAIR Operating System.
The THE system was the primary production system at that university for 8 years or so. And RSTS was a successful timesharing system product for DEC. When I used it, the whole college ran on it. To call those “proof of concept” is flat out wrong.
Virtual memory usually depends on paging hardware, but not always. THE had virtual memory without hardware help; instead, the necessary magic was in the software.
It’s certainly true that multi-user systems are easier to build and more flexible when you have an MMU, and managing memory is easier with virtual memory. But that’s not the same as claiming they are required.
Ben, you might do some reading of computer literature 10-20 years older than Dr. Dobbs and friends. A lot of major innovation happened long before the beginning of the PC era.
A little difficult to Google THE, but here’s wikipedia to help us:
1 Like
Correct, it’s not multi-user. But the original discussion was about multi-tasking, which is related but different, and THE indeed is multi-tasking, one of the first OS to be so in fact. Dijkstra’s famous paper “The structure of the THE operating system” is still very much worth reading today.
There are of course many other examples for the point I made. RT-11 comes to mind, or any of the multi-tasking FORTH implementations (for example, Zeptoforth for the Raspberry Pico).
Some concepts explained.
1 Like
Oops, meant to link to my new side-thread on THE:
That virtual memory article is interesting. THE is another example like Burroughs mainframes that doesn’t have all three characteristics: it has pages and demand loading but not really relocation. And unlike most of them, the demand paging is a software function, arranged with help from the compiler – rather than relying on page fault exceptions generated by processor hardware.
1 Like
FWIW In around 1979 I wrote a real-time multitasking clone of CP/M in Assembler for use on Z80 boards controlling factory machinery.
I then used Mike Lehman’s amazing MT+ PASCAL to write the multi-task applications.
Mike (in the USA) generously gave hints on how to multi-task the floating point run-time library.
Interesting snippet : I had initially planned to convert Microsoft’s BASIC compiler runtimes for this job. I spoke to Bill Gates on the phone to discuss this, but he wanted £5000 in 1979 money … and he also was extremely brash and rude on the phone so that didn’t happen!
5 Likes
Thankfully someone did it. So much cross conflation of concepts above.
There are a few more basic ones yet which you would encounter on the way to making an OS and earlier concepts in history.
Multi-programmable.
Z80 context: When you first boot your new Z80 build, you will probably want a ROM and some contents in it. So, like an MCU, you can flash a FlashROM chip and every time you reset the CPU it will execute that single program. This is what came first.
Most early mainframes followed the single-program model well into the 60s. “Batch jobs” where setup and the computer was booted with that program, it read the punch cards, read/wrote the tape and dumped the output to the line printer and halted.
Probably one of the next things you would work on is something like:
LOAD “”
Or… in my case, I was a bit more brutal.
LOAD 0xaaaa
Load to address and receive the “tape like” stream over serial (from a python script in my case).
Now the computer is “Multi-programmable”. When running it can be given different programs which are not necessarily known about when it was built or booted.
This then steers you towards a “console” or “shell” where you can “load” and “run” applications which then return you back to the console. Still single execution, single task though.
I believe this began happening certainly by the time the concept of a Mainframe OS was developing as a “Task and IO” management system… which tangential was the origins of “Micro-controllers” in a larger form. Autonomous agents doing IO and Task prep and orchestration between distributed units. (in the days of Mini-Computers things like Z80s where being used as IO controllers).
“Multi-tasking” and “Multi-user” had a rather odd birth in the real world, prior to unix it was based on “needs must” and the tech available. Phone lines and serial connections from a “terminal” to a mainframe. Except you connected to a big switching bank and you waited “on hold” effectively for your N minute time slot. During that slot your terminal would execute on “a” CPU. When your slot ended your context was either destroyed or saved for your next slot. Your terminal literally got reconnected back to “on hold” and someone else got the same CPU execution.
aka “Time sharing”. What this ended up looking like was incredible. Because of the finite time, maximising it was important. So remote offices bought punch card readers and teletype machines to have everything ready to go automatically as soon as the slot opened.
In Universities where individual departments got to play with their own computers, the timesharing was far more “on demand”, so “logging in” came from the adminstrative requirement to log who was using the computer at that time. It wasn’t for security, just for logging and assigning time for internal billing. Well… of course that ended up being abused and so passwords where added… and here we are today, we can’t have nice things because we can’t trust anyone. Well done humanity.
Back in the 1980s and the hayday of the 8bit CPU and the Z80 though, where do you go next?
With “LOAD” … “RUN” you have basically what the spectrum et. al. had.
The next place I went was “System background” tasks that don’t run in the interrupt context. Having system code interleaving with user code and both able to interrupt each other is a baby step which matters as an OS has to keep track of many things while the user code is running. Being able to do so in a way that doesn’t clobber, glitch or lag out the user application takes a lot of thought which will help for “user side multi-tasking”.
The modern basis of multi-tasking is the “task scheduler”. It’s a process which runs on a fairly high frequency interrupt timer. The “Process list” is the list of things “running” on the system. Each one has a bit of memory assigned to it in “system land” which describes it. In Unix it’s the “Process descriptor”, along with memory for it’s “Context”, ie, CPU state, stack pointer, program counter etc.
In a very simple form, each time it runs it saves the currently exeuting CPU state, SP, PC, etc. Then it selects the “next runnable” process in the list, restores it CPU state/context and calls “JMP” back to that program.
This in itself would be useful, but it creates the foundations for features like: IPC, Signals, Traps, IOWait.
For example. Asides “Running”, “Suspended Runnable”, we can also have “Wait on IO” where that process will only be reselected if the signal it is waiting on has triggered. This is where multi-tasking begins to become very powerful in software. Long slow IO waits can be pushed to the OS to manage and allow other runnable tasks to use the CPU while processes wait.
All that does require a lot of work though. Instead of user applications, for example, configuring hardware interrupts directly, you need to wrap that in OS style code with routines etc so that it is not the user application waiting directly on the interrupt, but instead it has jumped to the OS code and said, “Take this off me, I am waiting on INTERRUPT VECTOR 48, wake me when it arrives.”
In user code this is just:
; Setup struct at SETUP address.
LD HL, SETUP
CALL os_register_vector_wait
The CALL gives the OS our current location (from the stack) for the PC to return to. It gets put on the “Signal wait list” and when a hardware interrupt is received by the OS, it will check that list, find our process waiting on vector 47 and if it matches it sets that process state back to “Suspended Runnable” whence the scheduler will give it execution at it’s next convenience.
All of this requires “trust” and is “single address space”. So there is nothing stopping user programs tampering or directly calling OS routines, or even tampering with OS memory and other processes memory.
That is where “virtual memory” comes into play. Here code uses virtual addresses which are then re-written into physical hardware addresses. This facilitates, in the first instance, memory segmentation between processes. The basic hardware process has the pyhsical address lines from the CPU MAR translated before being reissued by the MMU.
Can you do virtual memory with a Z80? Yes. But it’s going to require you either integrate an existing MMU to the Z80 or, more fun, use an FPGA. In it’s simpliest form, the FPGA is “primed” with a lookup table via UART or SPI or any IO protocol you choose. The lookup table might be the top 8 bits of the address, maping to a real hardware address on the other side. The other 8 bits pass through. The ability to write those tables from user code is going to be a limitation. The Z80 doesn’t have a way to prevent one part of code calling an IO read/write from any other.
An MMU can be done in discrete logic. If you take a fairly common “memory bank paging” circuit for swapping 16k blocks, you basically have a 4 page virtual memory. Yes, it’s useless on it’s own and maybe 256 byte or 512 byte pages might be better with an 8 bit lookup?
The short-comings are when you want to use virtual memory for full user/process based isolation and restrict access to the same mechanisms from user processes. So in the Z80 there is going to be little to no way to stop a user application giving its self a lookup in teh FPGA tables into OS private physical memory.
Moving up to the 68000 CPU though and a few features appear magically, it’s almost as if they knew what they needed, sark. “Supervisor mode” - providing a way to run restricted code in a safer way which can’t be directly accessed by user space. This provides you the way, up front, to keep user programs away from reprogramming the MMU/FPGA.
The other feature it adds is a “fully asynchronous transactional bus”. This allows the MMU to say “No.”. When a user application tries to access memory for which is has no lookup mapping, the MMU can pull the “BUS FAULT” pin on the 68k, which can trigger an interrupt into supervisor mode. This allows OS code to handle the “Address access violation” flow.
Again though the 68k itself lacks an important feature added in later models, “Restore”. The 68000 offers “Immediate retry” on bus fault, OR, switch to the supervisor code at which point you loose the CPU context. This prevents “memory paging to disk” and dynamic allocation which are common in modern systems.
In Linux, your application can access an address which the MMU has no page lookup for. It will raise an address exception with the CPU causing a exception/interrupt into the kernel space. The kernel will check if that memory (or file) page is currently mapped to disk. If it is, it will load it into a memory page and then restore the application where it left off, the instruction will be retried with context.
In the 68k (000) you don’t really have that option. You could try and preserve the application context, but I think there are hurdles. So, in the event of a “Address violation” with virtual memory ala 68000 the user process is terminated and evicted with a fatal error. No lazy load disk paging.
If you are not latency or performance constrained, you could make the “Context switch” responsible for syncing disk pages to memory before executing the process. If memory is constrainded this will be very slow though.
Once we get up into the 80286 era most of what is required in a modern Unix kernel is already there for full address space isolation, isolated OS private context. Advanced features since have been mostly focused around how to “cache” virtual memory and the constant tweaks to fill security holes.
I missed:
Terminal multiplexing with TDM. They made the timeslots are LOT shorter and multipled multiple terminals onto a single CPU, so the users perspecitive it was a fully working connection.
and
Memory segmentation. Before you get to virtual memory and you need multiple programs to execute, you can no longer expect user applications to know which address to use at compile time.
So memory segmentation was added along with “exe formats” to readdress applications into a provided “segment”. “Your process may use memory from 0x8000 to 0x9000” and the relocator would literally rewrite all the addresses in memory before executing it.
This is the origin of the Linux “SegFault” or “Memory segmentation fault”. When you get one of those today however it is a missnomer. Memory segmentation is no longer used, virtual memory is. However the error has never been updated to say, “Memory address violation” or “Virtual memory access error”. “Address not found”. Backward compatibility and so many scripts looking for “SegFault” is most likely why.
Easier options:
Collaborative multi-tasking.
Used in the likes of MIPS. Easy to implement. Places the handling of multi-tasking into the hands of the user applications.
The concept of “Yield”. User processes when they can spare the time can call “yield”. The “OS” simply let another application run until it then calls yield.
Obviously this really only works in systems that are deliberately tightly coupled, such as control loops and realtime control systems.
It can be made to work in a default Z80 hardware setup, it just takes a bit of library code to handle the process registrtation and the yield call.
A 8 bit mmu chip may still be found on ebay. The got-ya is that they are a 40 pin dip. 74ls610…74ls613.
1 Like