When I was a kid, I always loved toying with compilers, assemblers, and virtual machines. But it’s been years since I’ve had a chance. Since I’m stuck inside with the shelter-in-place order, I figured I’d dive in. Where to begin?
Let’s design a CPU!
This seems like a good place to start. But what kind of CPU? I’d love to learn more about operating systems (I’ve always wanted to try my hand at writing a minimal one), so let’s design a CPU that’s at least somewhat like a “real” CPU. But simplified, idealized, so we’re not spending all of our time dealing with the 40+ years of cruft that has accumulated in x86, say.
If you’ve picked up the specification for Intel® 64, you’re stronger than me – it must weigh 60 pounds! This sort of machine is called a “complex instruction set computer” – “complex” indicating the sheer number of instructions, addressing modes, and so on.
Instead, let’s keep things simple, and design a “reduced instruction set computer”, or RISC. We’ll use a somewhat minimal instruction set – though not theoretically minimal – that gets at the heart of what a computer actually does.
For instance, we’ll want to be able to be able to add numbers, and subtract them. And read and write memory, say, and execute branches. But unlike x86 and its various extensions, we won’t have an instruction to copy an entire data buffer, or to “compare and exchange 8 bytes”.
Registers for a register-based machine
Virtual machines are often stack machines, e.g. the Java VM. Stack-based machines are very elegant and admit a very natural implementation. So a stack-machine might seem a good fit.
But most of the architectures I might hypothetically want to write an operating system for are not stack-machines; they’re register machines. Register machines come with their own benefits and challenges – for instance, if you are generating code for a register machine, you must be sure to keep track of which registers you are using when compiling a particular function, a process called “register allocation”.
So since I’m not going anywhere, and since, while I am building a virtual machine, I would like to build something similar to a physical machine, and since it sounds fun… we’ll design a register machine.
Crafting Interpreters by Robert Nystrom has a wonderful section on designing and implementing a stack-based virtual machine (for executing a program language) if you are interested in delving more deeply into these interesting machines.
Memory for a Von Neumann machine
x86 and many other popular architectures are “Von Neumann” machines – which is to say, their code and data live in the same memory. This is in contrast to a “Harvard” architecture, in which code and data live in separate spaces. While you might not have bumped into such an architecture on your PC, in fact the popular Arduino is based on a microcontroller that implements a “modified” Harvard architecture – “modified” in that, while data memory is indeed distinct from code, special instructions are available that can read code, too. Since we’re trying to keep things “realistic” we’ll take the Von Neumann approach.
In terms of how much memory our machine will have, there’s an important consideration to attend to first: if we are going to use our memory, we must address it.
You might have heard of machines being “64-bit”, perhaps because they provide for access to a 64-bit memory address space. Or maybe you’ve understood “64-bit” to refer to “native” integers being 64 bits long. I actually wasn’t sure what specific part of the architecture “64-bit” is intended to characterize, so I went looking and apparently it can refer to all of those things, and more.
Anyway, I was hoping to implement a 64-bit machine, since that’s what my computer is… but, we’re implementing the virtual machine in JS. Sadly, there isn’t native support for 64-bit integers in JS, and I don’t want to muck about with anything else. So we’ll go with a 32-bit only machine – fortunately I don’t think we’ll run out of space.
What do I mean by “only”? I mean that the smallest addressable or usable value will be 32 bits – our “byte” will be 32-bits long. That means registers will always hold 32-bit values, memory will conceptually consist of an array of 32-bit values, and so on. If you need access to octets you’ll need to do some bit-twiddling. This will dramatically limit the complexity of the machine.
Finally, like a “real” machine, we’ll want to be able to interact with a variety of peripherals,
like, say, a screen, or a hard drive! But I don’t want to “cheat”, and add an instruction
print_string, say… Instead, let’s design a system that can support an
arbitrary collection of peripherals, and use that system to implement video output and
Ok, that seems like a good place to start. Let’s go!