Suppose you have a program that is 218 words long. However you are using a 16 bit machine and have 216 words of RAM. (The RAM is directly addressed by the CPU). On the other hand, you have unlimited 'slow' storage where the full program can reside. How do you place in RAM the portions of your program that are currently needed (since you can't fit the whole thing)?
How did retro computers achieve this? Is it substantially different from the modern approach (if so how)?
The method depends on whether you have the address space or not, regardless of the RAM limitation.
If you already have a 32-bit address space, but simply not much RAM, then the answer is virtual memory. Virtual memory is generally processor supported: the processor traps accesses to memory that isn't present, and allows the operating system to perform a swap (to/from disc) — to perhaps flush something to disc in order to allow something else to be loaded.
However, given the statement of having 216 words of RAM, we will assume we do have only a 16-bit address space. Here, the concepts here are:
These will allow you to keep your resident code to a minimum. I remember using an overlay linker on the HP/1000 that took all night to compute the overlays. It would even duplicate small functions in the call tree into different overlay segments so that it would not have to switch overlays. Such mechanisms preclude function pointer comparison, but that was not really an issue with the languages back then.
Fundamentally, overlays keep a common base portion of code, and swap out the remainder as needed. They must use an some additional state (usually another word) for holding return address on the stack; the mechanism may have to perform a segment swap on return as well as on call.
However, no way overlays will get you to 232 sizes; they merely condense the code section so you have some more room for data within your existing (16-bit) address space.
The HP/1000 had a 15-bit address space (words, not bytes). Using microcode to offer an extend addressing of 32-bit pointers, it would map 32-bit addresses into the last of several pages in the 16-bit address space. So, the 15-bit address space memory would look something like this:
+-------------------------------------------+
| code... | data... |mp-1|mp-2|
+-------------------------------------------+
The code was as much as needed by the maximum size of the compressed overlays. The data for global fixed data.
Mp-1 and mp-2 are smaller chunks — 2 pages each in case data crossed over a page boundary, where a page is ~1024 words or so. The 2 pages ensured that after a mapping at least 1k was accessible.
The HP/1000 was a microprogrammed machine, and in the later days had special microcoded instructions to map a 32-bit address/pointer into either the mp-1 area (2k) or the mp-2 area (also 2k). After using the mapping instructions, then you could write code that would transfer or compute — all using 15-bit addressing — between regular "data..." and data in mp-1 and/or mp-2.
These microcoded mapping instructions would consume a 32-bit pointer (in the 16-bit A & 16-bit B registers) and return you a 16-bit pointer (in the A register) to the item of interest (after mapping that into either mp-1 or mp-2 by the choice of opcode).
So, at the cost of 4 pages (4k) of 15-bit address space, you could access 232 bytes using the mappings. Oh, and also the cost of inserting a mapping instruction before a 15-bit address space load or store. And further of maintaining 32-bit pointers, but you would have those sizes anyway with any other scheme supporting larger addressing.
I don't recall how virtual memory applied but I believe that would have been included along with the mappings, to access even more memory than both address space and real memory as well.
Typically, if your program needs 232 bytes, most of that will be data. So, for a 16-bit computer, overlays get you into the range of 64k-128k or more of code, and 32-bit extended pointer mappings get you to very large data/heap sizes.
Other computer systems have also had extended pointers, e.g. the 80286 could access up to 1MB on a 16-bit architecture. They used segment registers to complement 16-bit pointers. You could use them in 2 different ways.
The first is to hold the segment registers fixed, with one pointing to code, one to data, one to heap, and one to stack. You could then have 64k of code and maybe 64k the rest; or maybe 64k of each global data, heap, and stack, but that compromised the runtime model, since the language would have to simply know a priori where a 16-bit pointer referred (easy with code vs. data but not so easy with global data vs. heap vs. stack). Usually you could get 128k programs out of that arrangement, sometimes a bit more.
The other approach uses constant remapping similar to the HP/1000 where the segment registers are reloaded as needed from 32-bit pointers used by the program.
(Uiuiui - according to the rules this question should be out of scope as too broad, but lets give it a try.)
How did retro computers achieve this? Is it substantially different from the modern approach (if so how)?
As with any such broad question yes and no :))
This calls for a lengthy definition phase.
The very first didn't even bother to distingush much between 'slow' and fast memory, as the 'slow' device was it. Either because all RAM except registers was drum memory (like Zuse's Z22) (*1) or part of the adress space was drum (Univac 1103).
In fact, many early machines didn't have direct accessible external storage at all. For example a Univac 9200 (*2) only had punch card I/O and a printer.
The first thing that got rare wasn't programm space but data RAM. Keep in mind, a punch card is already 80 bytes, and a mere 100 of them kept in memory is about 8 KiB. Quite a lot for early computers, resulting in a need to handle them on some fast way without enough memory. Early disks (*3) weren't so much used for permanent data storage, but temporary work files. They were small and way too expensive to be wasted for things that could be read from tape (*4).
Data too large to be handled at once would be moved in and out under program controll. Either as records or blocks.
Ofc, even back then there where tasks to complicated to fit into available memory. There are baisicly two methods to handle this:
and
Both can be used for data or programs, although chaining is usually more associated with programs.
Chaining is the most simple way of runing a task too large to fit into memory at once. It gets split up in a series of (somewhat) independant programs that get run after each other. A batch file is eventually the most simple way of chaning. Early on Mainfram OS did support more sophistiveted ways of chaining where successive parts got loaded into the same memory while keeping exverything but the newly loaded section intact, thus able to share data. Unix' idea of pipeing streams thru programms is somewhat of an inbetween here.
As with mainframes before, early micro also supported chaining beyond a batch. Beside sinply loading a follow up programm (via LOAD), Apple's Integer BASIC ofered a CHAIN command, where another BASIC programm could be loaded to replace the existing, while all variables where kept intact. Applesoft was missing that feature, but programers soon developed some replacement code.
Unix like environments usually offer some kind of EXEC function to implement chaining. While often called an overlay mechanism, it's strictly just chaining, as the whole program gets replaced.
Overlays on the other hand are a way where a program keeps running but exchanges parts of the code or data on an as-needed base. This can be large potions, like a word processor loading a spell checker or mail merger overlay, like MicroPro's WordStar did. Or smaller parts like a single function. Ofc, loading each function seperatly when needed may prove inperformant compared to loading bundles of functions.
Overlays are mostly a programing issue and support is done by the programming environment in use. A common feature of all overlay techniques is that there is a predefined memory area where the overlay gets loaded. There can be more than one overlay area, and ofc. more than one overlay per area. Overlays can be used with data as well. Data overlays may need to be copied back to the extended storage before the overlay area can be reused.
Dynamic Linking can be seen as a special way to handle overlays. Especially when an unlink feature is offered. Unlike simple overlays memory can be used less wasteful with a thigher packing. Also the linker may offer recursive linking to handle dependencies. Where overlays (usually) need to be placed at a specific address when copied into RAM, dynamic liked modules can occupy any address - and with unlink available, a different address each time it is used even within a single program run.
On a more generalized way there are two techiques to handle the management of an extended storege
and
For Swaping programm and data areas of an application are organized in segments with each segment being a a unit to be moved out to extended storage or in from such. They can be of varying size. While most OS with swaping support only use these segments to organize a program (like code, data, stack, heap) and copy them in (or out) all at once, it can also be used as a way for programs to organize their overlays, but hand over thee management to some OS functionality.
Unlike simple overlays segments can end up at a diffent address after beign copyed out and in again.
Pageing in contrast splits up the memory (or a part thereof) in equal sized pages. Needed content (data or program) is moeved from background into RAM when needed. Unlike overlays, it's not done accoring to some module size, but as a (single or multiple) page. Also, much like with swaping, a page may end up ona different RAM address each time it is brought into RAM.
Pageing is (much like swaping) often seen as synonym for virtual memory, but thats not strictly true. While virtual memory does need pageing, pageing doesn't need virtual memory.
It need to be noted, that all of the mechanics discussed so far are not dependant on any hardware (beside I/O from/to the background story). But as usual special hardware and/or the right CPU structure can simplify this a lot.
For example a machine with register relative addressing (and sufficient registers) can handle all access (and thus calls) to dynamic areas with loading a register with a base address, allowing hasse free access (aka no address relocation needed) to a segment/overlay/page no matter what the actual load address is, and if it's changed.
Another way can be banking hardware. This was especially popular with early (micro) computers (*5), when RAM became less expensive, but address space limited usage. Here a section of the (limited) CPU address space is reserved to map in segments form a (usually larger) background RAM. It's much like overlay's in hardware. To make one available to the CPU address space no lengthy copy operation is needed, but at simple change of address handling. Depending on the machine several such sections may exist, or even the whole address Space may be made up from such assignable areas.
For all these methods a good book keeping is needed to manage what overlays are in RAM/address space and thus direct accessible, or need to be moved in. This can be done via an intermediate layer, or due programm structure - which brings us to the software part.
Or wait, a short interlude about virtual addressing might be right here:
Many answer this question reflex like with some reference to virtual memory, but the question is explicit not about such a system. Still, for this issue we need to remember that the sollllllution we commonly refer to as virtual memory is about threeseperate issues:
While the first is somewhat similarto the background of the question, none realy touches it, as all assume an address space equal or larger than existing RAM.
Oh, and on a historic side note, IBM originally refused to add virtual memory to their /360. After all, who in his right mind wants to slow down an expensive high performance computer to about half its thruput? An engineer would never think of this - only mathematicians do.
How do you place in RAM the portions of your program that are currently needed (since you can't fit the whole thing)?
I assume your question is about how to handle this in programming - as hardwarewise it's just ordinary I/O.
At the core overlay programming is just redefinition of the address space in use. Think of overlays as of a UNION in C - or a redefinition in Assembler. One memory area where symbols for different data structures (and programs are nothign but data - with entry points as their elements). As long as only the elements with data loaded are accsses everythign is fine. Much like a union` with a float and a string - either definition sould only be used accoring to what is inside. In C such a union would often have a type associated, so an access function may first check the type before itnerpreting the data. For overlays it's much the same.
It's all about book keeping. In general there are two ways: By structure or by checking (managed).
By Structure. One way to handle it are strict hirarchical programm structures. Each module only calls specific modules within a tree, and none of them calls any module outside his branch. Here no locking or checking is needed, as there is no way to screw up module order. This method is best for overlays with a large scope and rather closed functionality.
The already mentioned WordStar is a great example here, as when, for example, the spellchecker (SPELSTAR.OVL) is called, its modul gets loaded and takes over control until the job is finished. It will never call the form letter function (MAILMRGE.OVL) function or vice versa. When it comes to
By Checking - or managed. Here each call of a function in an overlay (except the one the caller is residing in) is preceded by a check if the target overlay is already loaded (and where). If yes, the function gets called, if no, an overlay loader function gets called and then the desired function. It might be handy to have this in some static module that never gets overwriten.
This may sound rather complicated, and it is, but with functions of sufficient size the overhead gets acceptable. For sure it's better than not having a certain functionality.
A great optimization is to make all (inter-) overlay calls indirect via a central management table. Each (external) callable function gets a number (or name) assigned. A central table is made up for all (callable) functions of all overlays. In the begining all entries are filled with the address of a management function. Whenever an overlay is loaded, all containing function entry points are copied into their table positions, when it gets unloaded, the entries are again filled with that management function.
Now calling a function is no longer done as name(...) but rather as table[name](...) (*6). If the overlay is already loaded the function gets called right away, all overhead is reduced to an indexed pointer load. If the needed overlay is not loaded it calls the management function which now can determinate the overlay to be loaded, find a free memory location, or unload another overlay to free space, load the overlay and dispatches the call.
And yes, this is exactly what one may call late binding :))
All of this makes the overlay management nicely hideen while still performin well ... ofc, only as much as the calling structure allows. Two functions in different overlays calling each other can trash this quite fast. It all comes down to a proper organized programm structure and sufficient overlay areas/space.
In fact, it shows again - and quite well - that a tidy structure will usually outperform any fancy hardware in a given context.
*1 - Z22/23 had an optional 'fast' memory as core of a few hundret bytes.
*2 - An IBM /360 clone, lower End of the Univac 9000 line)
*3 - And before them tapes. Yes, card data was read in, wtiten out onto tapes and processed in random from there.
*4 - Until the end of the 1970s it wasn't uncommon for mainframes to boot the OS from tape and use disks only for temporary data.
*5 - All the way from the Apple II's Language Card to LIM-Memory on PCs.
*6 - C alike syntax used for simplicity.
In the beginning there was the Turing machine which did not have RAM in the way we recognize RAM today. You could look at it as a state register and all the stuff was done on the tape by a self-rewriting program (just a set of rules really). So that was the first principle of running a program bigger than RAM (using an external storage medium).
A 16 bit machine does not mean you get a 16 bit address space. For example 8 bit CPUs like Z80, I8080 have a 16 bit address space. So you need to look at how many bits your address bus has got and not how many bits your computer is.
Back in the days programmers knew how to program efficiently (as they had no other choice). So the programs were not that big that they would not fit into RAM. How ever with time and added data like sound and graphics and complexity of games some games were bigger than the RAM space.
So what was done was that app was divided into functional blocks (in games, into levels and main menu) and you needed to reload the program from storage on each transition between those parts. IIRC ZX games like North&South R-Type Myth used this technique. As the storage was usually MG tape this was very uncomfortable (as it needed user interaction) especially if your tape did not have a counter. Also the load times were IIRC ~35KByte/5min so you would need to wait a lot just to return to the menu or something.
With more and more demands on the RAM size some 8-bit computers with 16-bit address buses (64 KB) started to use more memory (80 KB, 128 KB, 192 KB) and that was used by paging it into a specific address space. So you got one configuration IO-mapped register which decided which chunk of memory is placed where. For example this was used in ZX128, Didaktik Gamma.
With faster and more automated storage media like FDD and HDD the same could be done with storage directly. Paging with storage was called swapping (maybe you remember the swap file on windows).
With the need for multi tasking and memory protection the newer processors came up with the virtual memory which in a nutshell can programaticaly remap "any" physical address space to "any" virtual address space, according to the memory mapping rules of the used architecture. That is, however, far from my field of expertise and you should read Erik Eidt's answer.
The sad thing is that with the increased RAM and storage capacity the programmers got really lazy and now our OS is 15-50 GByte which is nonsense as there is not that much data and surely not relevant code. There are 1GB profi app exe files out there (without any sound or textures) too.
Another drawback of this devolution is that programs that ran fine on 386 once has new counterparts that do the same job but need a CPU 1000x times faster (I am talking about text of course as in graphics the job is not the same).
There were two basic approaches to this. I've implemented both. Both rely on swapping data between RAM and backing storage (typically disk) as it is required.
Application level
Many moons ago I wrote a raytracing system for DOS. Because it could not hold all the necessary image and spacial data in RAM at once, it would load/save one row at a time.
Word processors did this too, for very large documents. Older operating systems like DOS were not sophisticated enough to assist the application, so they had to implement their own custom schemes.
This is extremely rare these days, because now almost every OS does it automatically.
OS level
The OS can use a memory management unit (MMU) to intercept memory accesses to certain address ranges. Depending on the MMU there can be limitations such as detection only being down to a 4k page level, rather than individual bytes.
The MMU can trigger an interrupt, a special CPU feature where the currently executing code is halted and a special interrupt handler routine is run. The OS provides this routine and uses it to halt the running application while data is loaded from disk.
MMUs were not common in home computers until the 1990s, as they are somewhat expensive and complex devices.
The Macintosh 128kb is a machine with 2^16 words of RAM: words are 16-bit on the 68000. After a fashion, it can run software designed for a machine with 2^18 words of RAM — software designed primarily for the Macintosh 512kb. It has no MMU. It is an interesting case study because its mechanisms are documented in detail, and that documentation is easily accessible.
The primary approach is a specific implementation of overlays, as code segments, which are handled by the jump table as described from the bottom of Page II-60, which is Page 628 in the PDF.
Code is partitioned into segments of at most 32kb in size. Only relative addressing modes are permitted, so any segment can be loaded anywhere. A segment contains some subset of the application's functionality. When it wants to jump to a routine that is in a different segment it actually jumps to that routine's entry in the jump table. At any time the jump table will contain either a jump to the actual code fragment, if loaded, or else a jump to the segment loader, if unloaded.
It is implied but not particularly explicit that segments are placed onto the heap like any other piece of data.
The mechanism for heap handling is described from Page I-71, which is Page 81 of the linked PDF. It's not quite as relevant, but:
For most dynamic allocations, it uses two levels of indirection. You own a reference that you can use to ask where the allocated memory is. This differs from hardware virtual memory beyond merely that you're handling the extra indirection in software in that indirection is per allocated area, not per page — the mapping happens once per allocated area and then everything following that is physically contiguous, which potentially allows a few more bytes to be scraped upon a compaction.
A caller can instead request non-relocatable memory, in which case its address will never change and you can always assume the physical address is the same as the last time you asked. You're being a bad citizen, but the option is there. You can also mark memory as purgeable, which gives the system the option of simply throwing it away if total available memory becomes constrained.
So the main special feature for fitting more into less is purgeable memory. It's data you'd like to keep around, but could do without if you had to.
So, in net, the fixed memory requirements for your program are:
I make that at most 64kb for the jump table plus one segment of code; the display is a bit more than 21kb and the OS is likely taking up a bit more space but is primarily ROM based so not as much as you might fear. The original Macintosh is (overwhelmingly) single tasking. So you need to keep your working data set sufficiently far below about 40kb.
The same segment loading system is used for all other program resources, and was commonly used for Macintosh filetypes so your documents needn't fit into that space, subject to the same partitioning rules.
This also partly explains why the 512kb Macintosh was considered so much better than the original: given the fixed costs of your jump table and the display file, you're actually increasing the amount of working space by a factor much larger than four.
The 99/4A with expansion box had 48k of RAM.
The hardware didn't have any answers large programs you just ran out of memory.
However, most software developers, divided there programs into modules.
For example, a calendar program.
You start out, and enter all the details about the basic calendars. It saved that to a file.
Program 2 launches read the file.
It allows you to enter text into each day, but has lag time where it saves and loads its information.
The data you entered was saved to a file, and then the main program was re-executed.
The picture selection program was too big to be loaded with the other software, so it too allow you to select a pictures, but then saved the information to a file.
When the whole calendar was done, and you want to print it.....You guessed it ... save the entire calendar data was saved to disk, and the print module was loaded.
They tried to make the program as seamless as possible but the giant load times were a dead give away what was happening.
That and ........
Even games had up to 6 ROM chips which were swapped between, and bits and pieces were loaded, as needed, from each ROM.
If you consider old 8086 and 286 PC as retrocomputers (even if they had 20-bits addreses), then expanded memory ( https://en.wikipedia.org/wiki/Expanded_memory ) and extended memory ( https://en.wikipedia.org/wiki/Extended_memory ) may be of interest.
Extended memory was used for compatibility with old design and used switching processor to 32-bit mode, copying some bytes from/to "unreachable" memory and then switch back to 20-bits mode and continue runing old programs.
Expanded memory was totally other kind - there was a place in adress space (4 blocks of 16KB forming 64KB), where external card (with some memory on the card) could be placed. Sending some values to the card the card then "swap in" (mapped) some part of its internal memory. It allowed for storing as much as 32MB of data/program there on machine able address just 1MB at all.
I wrote some program, that lived there in full (except 120 bytes, mainly header, which allowed it to use it from "normal memory") - the pages actually in EMS was paged away, my program was paged in, used 2 windows for program code (and swapped like 60KB there, 4 pages) and other 2 windows for data (in total over 300KB, again swapped in on demand) and on finish it again swaped the old context there, waiting to next call. This way I used only 120 bytes of conventional memory, but was able to run 60KB program with 300+KB data invisibly from the "normal program", I was supporting. (which took nearly all conventional memory just to run and there was a lot of problems to run it under DOS, as no big drivers could be loaded, otherwise the program would just crashed from insufficient memory).
It was a lot of pointer managing in C, but it made the main program run 2x faster on the main loop, which took couple of hours (as my program precompiled the computation instead of interperting it in the main). (It would run much faster, if there would not be the need to use the main for database access). Wrote it around 1990, computed salaries for big company upto like 2003 or so).
Another interesting case was BBC Micro with 6502 main processor and 32KB of RAM (video took 1K..22K depending of mode), which was later able to get "coprocessor" Z80 with 64KB RAM (and CP/M OS), where main program was run on Z80 with ovehelming 60KB RAM free (4K for system) still using the finest 22KB graphic mode of 6502 and all of its periferials (keyboard, mouse, joystick, disketes ...)
