I really don’t understand how complex programs like compilers and browsers have come to an existence.
From little what I know about 8086, it resembles a digital abacus in a way that we can set, push and do all the fancy magic with registers and store them in memories using buttons.
For the like of me, I cannot figure out how an OS was created out of thin air? Do they keep pushing, adding and popping registers back in the day to create OS or compiler? What about the TTY? Was there no such thing as booting? What about file systems? Partitions? How did any of that even work in the first place?
You must log in or register to comment.
I don’t know the details of the history of the first compiler or the first os or how various others were created. But here are some thoughts on how it could be done.
Let’s start with a simple computer based on, say, a Motorola 6809 since I’m sorta kinda familiar with that since it is the CPU in my Hero Jr vintage robot. Let’s call our computer the Orange.
First how does it run a program at all? Well, on reset, the first thing it does is loads a 16 bit address from the two highest bytes in memory ($FFFE - $FFFF) into the Program Counter. It will then execute the machine instruction at that new address.
So if you could somehow load a program into memory, starting at some address ($D000, say), and also load the address value into $fffe-$ffff the computer will run your program on reset.
One way to do that is to design your new computer with a PROM chip (a “read only memory” that is easy to write to, once) which occupies memory from address $d000-$ffff. That is, when the CPU reads from $fffe-ffff it is reading from the PROM rather than from RAM.
To write your program, you would write it in assembly language and use an assembler to convert to machine code (just a sequence of data bytes). Except we don’t have an assembler yet. So let’s do it by hand on paper. CPU manufacturers provide info needed to do it by hand.
By the way, we don’t have something to program the PROM yet. Let’s start with building a machine whose sole purpose is to burn an EEPROM. We need it to have switches on the front (like a PDP8e). You use the switches to enter data 8 bits at a time into any 16 bit address. Let’s say it has an 8 switch data input, and 16 switch address input. Also it has Store and Program switches. You can design the hardware with digital logic chips that will do as follows:
- When Store is pressed copy the specified data into the specified RAM address
- When Program is pressed, copy your program from RAM into the eeprom.
- When Run is pressed, run the program starting at the specified address.
I’m leaving out some implementation details for simplicity.
Eventually we want to use our Orange to write, save, and load files, assemble programs, and run machine code generated by assembled programs.
So we need devices for storage (floppy? Tape drive?) and serial UART. Skipping over hardware details, we need software to use the devices. We need to read commands from the terminal, display stuff to the terminal. The commands might include SAVE, LOAD, STORE and RUN. Each command is implemented in software. All this software can go into the PROM and offer these capabilities on reset, similar to 80s home computers like the Commodore 64.
Once we have written, assembled and programmed our PROM to do that, now we have a rudimentary operating system that handles simple input and output. Maybe also add some useful functions that users can call from their own program.
We could make life easier on ourselves and write an assembler and a simple file editor that we can use to write assembly language files. Then we can save the assembly file and run the assembler to create a file of machine code. We can save these new programs to storage. And now we can use those to more quickly write more complex things.
We can add a PROM burner to our list of devices and add the capability to burn programs from memory to a new PROM. We can use that to more conveniently update the PROM on our Orange computer.
It will be easier to write a BASIC interpreter now. Or a compiler. Now you can develop more complex programs quickly. You can rewrite parts of your assembly code in a higher level language so it is easier to maintain.
Maybe you outgrow your computer and want to make an Orange II with a new CPU, more power, memory, etc. well, you already have the first computer so you can develop the ROM code for the new computer using the first computer. You can make a cross assembler and cross compiler. Wire software on the Orange that spits out machine code specific to the Orange II CPU.
That makes a lot of sense - and for some reason, it bought back some of the stuff I was taught in CS, which I had forgotten. Speaking about filesystem, should I consider it a type of a program similar to a database - as in, the way how it uses a program to read data stored in some binary file to read, write and index stuff? Or is that a wrong way to look into it?
Good question about filesystem. Let me think… yeah, probably think about it as a kind of database, but more like an API for a database that keeps track of file names, file sizes, where the files are stored on the storage device.
It’s a collection of functions to do useful things like create, read, write, rename files, and list files available.
It is an abstraction layer on top of the storage device functions.
If we created tape storage, like on a Commodore 64, we wouldn’t have a filesystem. Our functions would just write or read a sequence of bytes from wherever the tape was, currently.
With no filesystem, the user has to remember where on the tape the programs are stored (using the tape counter), what the program was (jupiter lander or tic tac toe or whatever), and keep track of what sections of the tape are free. Back in the day I kept this written down in a notebook. It was a pain.
A filesystem would do this for us. But instead of a sequential storage device like tape, we need to create a random access, block storage device. We’ll make a floppy drive.
We will divide the storage capacity (100KB, say) into blocks–sets of bytes–of 1KB each. So each disk will have 100 blocks.The drive will read or write to any specified block on command. We can say “read block 7; read block 73; write block 2”. Any order. Doesn’t matter.
Let’s call our filesystem SimpleFS (SFS). SFS will keep track of the list of files, the names of each file, where those files are stored, how long the files are, what blocks are free on the disk, etc.
Keeping this dead simple, SFS reserves Block 0 for the list of files (aka file catalog) and for maintaining a list of free blocks. We can use the first 100 bytes to represent the free/used status of the corresponding 100 blocks on disk where 0 represents free and non-zero means used. So if byte 5 is 1 then block 5 has been filled with data.
The remaining bytes contain the file catalog. Each catalog entry contains a 10 character file name, the file size (16-bit) in 2 bytes, and the starting block # of the file. SFS will only store files in contiguous blocks.
So now we can write our SFS functions.
- FORMAT will initialize the storage by writing 110000…0 to the block map to show it is empty and formatted with only block 0 and occupied. And it writes 0’s to the catalog, block 1, to zero it out.
- DELETE will clear out the catalog entry corresponding to the specified file name, by setting the starting block to zero.
- LIST sequentially reads the list of files out of the catalog displaying name and size, skipping over directory entries with a 0 starting block.
- RENAME would change the name of the specified file in the catalog to the new specified name.
- LOAD would read the specified file from disk into the specified memory location. So LOAD(“myfile”,$1200) would go to disk, find the catalog entry for “myfile”, find out how many bytes to read in, the starting block #, and then read from those blocks into memory.
- SAVE writes a sequence of N bytes from RAM to the disk, creating a file with the specified filename. So, you’d call SAVE(“myfile”, 73, $1200) to save 73 bytes starting at hex addr $1200 to a file called “myfile”. You can imagine that this function would have to find a free directory entry, find a series of 73 free blocks on disk, copy data to said blocks, then update the block map and the catalog entry.
You can imagine some flaws with this simplistic design. For example, requiring all the file blocks to be contiguous is rather limiting. Imagine if you want to append to a file but there’s no space available after the last block?
So you might want to eventually redesign SFS to be able to keep a list of non-contiguous blocks. There are various ways to do it. Since the directory is fixed, maybe you create a new data structure that contains a 0-terminated list of blocks. You refactor your functions to be able to use a non-contiguous set of blocks with this new data structure. And maybe you need a DEFRAGMENT function to reduce fragmentation that will result.
Having only a flat directory kind of sucks too, so you could redesign it so that you could have subdirectories, each with their own file catalog. Then add functions to deal with path names, change directories, etc.
Also, it kind of sucks having to know ahead of time how many bytes your program occupies. So instead, lets make it look more like unix. We use an OPEN and CLOSE function. Open can be used to write or read or append to a file. We don’t have to know the file size, just write bytes one at a time.
We can then revise our editor to read our program a byte at a time from the filesystem and save it a byte at a time to the filesystem. And we can revise our assembler to read the assembly file, bytewise, and output the machine code directly to disk one byte at a time. The SFS can figure out how to update the size data in the catalog and manage which blocks get used.
Another flaw is that if any of these save operations are interrupted before they’re done, we’re going to lose data and have a mess. So we probably need to figure out a way to reduce the potential damage and a way to repair the filesystem.
Anyway, hopefully this gives you some ideas of how this stuff can be done.
I’m vaguely familiar with how some of the classic filesystems work, like DOS FAT, Apple II’s DOS (I forget what it was called), C64’s disk OS (which if I’m not mistaken was actually programmed on the very intelligent but expensive 1541 disk drives), Minix/Linux-sorta-kinda as taught in some of my CompE classes.
Wow, so by this, one could assume that there’s a lot of technical debt. And it’s almost impossible to keep track of each and every part that goes into a modern OS. Right now I do not have the luxury to play with RISC-V, but maybe in the near future, I’ll be buying one of their boards to learn hardware in depth.
Based on your comment about technical debt, I should clarify.
My descriptions aren’t historical at all. They’re just meant to show how it might be possible for you to do this as a personal project. I felt like that might kind of “scratch the itch” of your original question.
The actual history of operating systems is fairly complex with many companies having developed them independently over time, but perhaps borrowing concepts from previous operating systems and academic papers.
For example, Windows NT was built more or less from scratch. However, I think I read that a couple things are inspired by prior work of the devs on VAX/VMS.
But yeah modern operating systems are pretty complex. Too much for any one person to fully and perfectly keep track of.
Having written all this I think it would be cool to develop the process I described into a series of courses where you learn how computers work, hands on, from discrete transistor logic to logic chips to ICs and building an old school 8-bit computer, all the way up to writing the OS.
So early computers usually got their instructions from two switches. You would start with switch A low and then set switch B to the first bit to load into memory. Then set A high to read B into memory. Set A low and then change B to the second bit you wanted to load. Then set A high to read it into memory. Repeat for each bit in your program. Then hit the run switch.
This takes a lot of time and is prone to errors. So you automate it by using a punch card store the bits in your program on paper and auto flip A as you move the card through the reader and replace B with a optical switch reading the light that passes through hole in the punch card or not depending on the value of the bit.
Now you have reusable pieces of code you can feed in. You find there are some common starter cards that everybody always uses first to setup basic functionality. To speed up load time by not having to feed the same stack of cards in at the start you move their content onto a bunch of magnetic coils and change the hardware to first load that into memory when turned on and then start reading cards. That’s your early bios.
Improve the capacity of system over many years and you have a system that dumps a chunk of the memory onto a sweeping electron beam and by altering that memory you can change the screen the beam is hitting. Giving you a display. Add stuff to take input from a keyboard and you can give command much faster.
Write code that does common tasks and listens to the keyboard so for example when you type flush it clears all memory outside a protected area where these macros are stored. Make enough of these and you have the beginnings of an os.
For a programming language you design the language and then in assembly write programs that parse text and according to the rules of the language generate assembly code that does what the higher language says that instruction should do.
Once you have that you can start writing a second compiler for your language but this time you write that compiler in your new language. One of the major milestones of a language is when it can compile a compiler written in it’s own language.
Now that we have other programming languages the first compiler is usually written in another language and then rewritten in the new language. So the C compiler was written in PDP11 and the Java compiler was written in C. Now the Java compiler is written in Java though the runtime is still in C with I think some C++ depending on the target platform.
I’ve glossed over a lot but this should give you a basic idea. A lot of tedious work at first that gets more and more automated as you go on.
What about the existence of the “shell” utility? I know that Unix has the
shprogram, but before the OS-era, this wasn’t the case, right? When and how was it implemented? Is there any example of a computer before the shell era?Not op but…
The shell is nothing but a program that reads input and parses commands and then does the things asked and print output.
That’s not really all that different from a Commodore 64 in concept. You could type in commands to load / save / run other programs.
I’m glossing over a lot here. :)
I will add that Unix is a multitasking, multi user operating system which adds complexity and a lot more to explain. :)
Anyway I’m pretty sure the very first electronic computers were single user and may not have had more modern input/output like terminals or CRT display & keyboard.
Sounds like you need to take a class in computers 101, this is all covered in the basic computer science classes. I’m sure there are more qualified people here to explain it. But I know I had to “learn” all that long ago in the before before times.
