(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 History
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.
More than Meets the Eye
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.
Generalization
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.
Hardware
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:
- Offering a program a seamless impresion of more memory than realy is available
- Giving paralell loaded programs each the impression of owning all memory
- Enabling each programm the ability to use fixed addresses (starting at 0)
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.
Software
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.