Overlay (programming)

In a general computing sense, overlaying means "the process of transferring a block of program code or other data into main memory, replacing what is already stored".^[1] Overlaying is a programming method that allows programs to be larger than the computer's main memory.^[2] An embedded system would normally use overlays because of the limitation of physical memory, which is internal memory for a system-on-chip, and the lack of virtual memory facilities.

Usage

Constructing an overlay program involves manually dividing a program into self-contained object code blocks called overlays or links, generally laid out in a tree structure.^[b] Sibling segments, those at the same depth level, share the same memory, called overlay region^[c] or destination region. An overlay manager, either part of the operating system or part of the overlay program, loads the required overlay from external memory into its destination region when it is needed; this may be automatic or via explicit code. Often linkers provide support for overlays.^[3]

Example

The following example shows the control statements that instruct the OS/360 Linkage Editor to link an overlay program containing a single region, indented to show structure (segment names are arbitrary):

 INCLUDE SYSLIB(MOD1)
 INCLUDE SYSLIB(MOD2)
 OVERLAY A
   INCLUDE SYSLIB(MOD3)
     OVERLAY AA
       INCLUDE SYSLIB(MOD4)
       INCLUDE SYSLIB(MOD5)
     OVERLAY AB
        INCLUDE SYSLIB(MOD6)
 OVERLAY B
    INCLUDE SYSLIB(MOD7)

                       +--------------+
                       | Root Segment |
                       | MOD1, MOD2   |
                       +--------------+
                               |
                    +----------+----------+
                    |                     |
             +-------------+       +-------------+
             |  Overlay A  |       |  Overlay B  |
             |  MOD3       |       |  MOD7       |
             +-------------+       +-------------+
                    |
           +--------+--------+
           |                 |
    +-------------+   +-------------+
    | Overlay AA  |   | Overlay AB  |
    | MOD4, MOD5  |   | MOD6        |
    +-------------+   +-------------+

These statements define a tree consisting of the permanently resident segment, called the root, and two overlays A and B which will be loaded following the end of MOD2. Overlay A itself consists of two overlay segments, AA, and AB. At execution time overlays A and B will both utilize the same memory locations; AA and AB will both utilize the same locations following the end of MOD3.

All the segments between the root and a given overlay segment are called a path.

Applications

As of 2015^[update], most business applications are intended to run on platforms with virtual memory. A developer on such a platform can design a program as if the memory constraint does not exist unless the program's working set exceeds the available physical memory. Most importantly, the architect can focus on the problem being solved without the added design difficulty of forcing the processing into steps constrained by the overlay size. Thus, the designer can use higher-level programming languages that do not allow the programmer much control over size (e.g. Java, C++, Smalltalk).

Still, overlays remain useful in embedded systems.^[4] Some low-cost processors used in embedded systems do not provide a memory management unit (MMU). In addition many embedded systems are real-time systems and overlays provide more determinate response-time than paging. For example, the Space Shuttle Primary Avionics System Software (PASS) uses programmed overlays.^[5]

Even on platforms with virtual memory, software components such as codecs may be decoupled to the point where they can be loaded in and out as needed.

Historical use

IBM introduced the concept of a chain job^[6] in FORTRAN II. The program had to explicitly call the CHAIN subroutine to load a new link, and the new link replaced all of the old link's storage except for the Fortran COMMON area.

IBM introduced more general overlay handling^[7] in IBSYS/IBJOB, including a tree structure and automatic loading of links as part of CALL processing.

In OS/360, IBM extended the overlay facility of IBLDR by allowing an overlay program to have independent overlay regions, each with its own overlay tree. OS/360 also had a simpler overlay system for transient SVC routines, using 1024-byte SVC transient areas.

In the home computer era overlays were popular because the operating system and many of the computer systems it ran on lacked virtual memory and had very little RAM by current standards: the original IBM PC had between 16K and 64K, depending on configuration. Overlays were a popular technique in Commodore BASIC to load graphics screens.^[2]

"Several DOS linkers in the 1980s supported [overlays] in a form nearly identical to that used 25 years earlier on mainframe computers."^[4]^[8] Binary files containing memory overlays had de facto standard extensions .OVL^[8] or .OVR^[9] (but also used numerical file extensions like .000, .001, etc. for subsequent files^[10]). This file type was used among others by WordStar^[11] (consisting of the main executable WS.COM and the overlay modules WSMSGS.OVR, WSOVLY1.OVR, MAILMERGE.OVR and SPELSTAR.OVR, where the "fat" overlay files were even binary identical in their ports for CP/M-86 and MS-DOS^[12]), dBase,^[13] and the Enable DOS office automation software package from Enable Software. Borland's Turbo Pascal^[14]^[15] and the GFA BASIC compiler were able to produce .OVL files.

Notes

^ This has nothing to do with the term region in MVT storage management.
^ In OS/360 and successors, there may be multiple regions^[a] each containing a complete overlay tree.
^ The nomenclature varies depending on the system, e.g., in OS/360 region refers to an entire overlay tree.

References

^ "Oxford Dictionaries". 2015-11-26. Archived from the original on 2022-07-10. Retrieved 2022-07-10.
^ ^a ^b Butterfield, James "Jim", ed. (June 1986). "Part 4: Overlaying". Loading And Linking Commodore Programs. p. 74. Archived from the original on 2022-07-10. Retrieved 2022-07-10. This lets you run programs which are, in effect, much larger than the amount of memory in your computer. {{cite book}}: |magazine= ignored (help)
^ "The GNU Linker documentation: Overlay Description". 2008-06-03. Archived from the original on 2022-06-23. Retrieved 2022-07-10. [1]
^ ^a ^b Levine, John R. (2000). Linkers & Loaders. Morgan Kaufmann Publishers. p. 177. ISBN 1-55860-496-0. Archived from the original on 2022-04-06. Retrieved 2022-07-10. [2]
^ National Research Council (November 1993) [June 1993]. An Assessment of Space Shuttle Flight Software Development Processes (2 ed.). Washington, DC, USA: National Academy of Sciences, The National Academies Press. doi:10.17226/2222. hdl:2060/19930019745. ISBN 978-0-309-04880-4. LCCN 93-84549. Retrieved 2012-10-29. (208 pages)
^ "Chapter 12: The Chain Job" (PDF). IBM 7090/7094 Programming Systems – FORTRAN II Programming (PDF). Poughkeepsie, New York, USA: IBM Corporation. August 1963. pp. 34–35. Form C28-6054-4 File No. 7090-25. Archived (PDF) from the original on 2022-03-15. Retrieved 2022-07-10. {{cite book}}: |work= ignored (help) (52 pages)
^ IBM 7090/7094 Programming Systems – IBJOB Processor – Overlay feature of IBLDR (PDF) (1 ed.). Poughkeepsie, New York, USA: IBM Corporation. May 1963. Form C28-6331 File No. 7090-27. Archived (PDF) from the original on 2022-03-15. Retrieved 2021-12-26. {{cite book}}: |work= ignored (help) (8 pages)
^ ^a ^b Elliott, John C. (2012-06-05) [2000-01-02]. "PRL file format". seasip.info. Archived from the original on 2020-01-26. Retrieved 2020-01-26. […] A PRL file is a relocatable binary file, used by MP/M and CP/M Plus for various modules other than .COM files. The file format is also used for FID files on the Amstrad PCW. There are several file formats which use versions of PRL: SPR (System PRL), RSP (Resident System Process). LINK-80 can also produce OVL (overlay) files, which have a PRL header but are not relocatable. GSX drivers are in PRL format; so are Resident System Extensions (.RSX). […] [3]
^ Dohmen, Norbert (1990). "Platz schaffen durch Überlagern - Overlay-Strukturen in Turbo Pascal". mc (in German). Vol. 90, no. 12. pp. 124–130. Archived from the original on 2022-08-04. Retrieved 2022-08-04. [4]
^ Gavin, Bruce. "Create Program Overlays". In Pearson, Dave (ed.). Turbo Pascal - Norton Guide. v3. p. 149. Archived from the original on 2022-08-04. Retrieved 2022-08-04.
^ Mabbett, Alan (1985). Getting started with WordStar, MailMerge + SpellStar. Cambridge University Press. ISBN 0-521-31805-X.
^ Necasek, Michal (2018-01-30) [2018-01-28, 2018-01-26]. "WordStar Again". OS/2 Museum. Archived from the original on 2019-07-28. Retrieved 2019-07-28. […] The reason to suspect such difference is that version 3.2x also supported CP/M-86 (the overlays are identical between DOS and CP/M-86, only the main executable is different) […] the .OVR files are 100% identical between DOS and CP/M-86, with a flag (clearly shown in the WordStar 3.20 manual) switching between them at runtime […] the OS interface in WordStar is quite narrow and well abstracted […] the WordStar 3.2x overlays are 100% identical between the DOS and CP/M-86 versions. There is a runtime switch which chooses between calling INT 21h (DOS) and INT E0h (CP/M-86). WS.COM is not the same between DOS and CP/M-86, although it's probably not very different either. […]
^ Sidnam-Wright, Liz; Stevens, Brad, eds. (1990-07-31). "Ashton-Tate ships dBASE IV Version 1.1" (PDF). Torrance, California, USA: Ashton Tate. p. 2-2-2. Archived from the original (PDF) on 2017-04-04. Retrieved 2014-02-13. Version 1.1 has a new dynamic Memory Management System (dMMS) that handles overlays more efficiently: the product requires less memory, which results in more applications space availability. […] The product's lower memory requirements of only 450K of RAM provide improved network support because supplemental hardware memory is no longer required to support networks. […] By speeding up areas of dBASE IV that are overlay-dependent, the new dMMS improves performance when working at the Control Center and in programs that use menus and windows. (5 pages)
^ Herschel, Rudolf; Dieterich, Ernst-Wolfgang (2000). Turbo Pascal 7.0 (in German) (2 ed.). R. Oldenbourg Verlag [de]. p. 249. ISBN 3-486-25499-5.
^ Eßer, Hans-Georg (June 2009). "Chapter 6. Speicherverwaltung und Dateisysteme - Teil 5: Nicht-zusammenhängende Speicherzuordnung". Betriebssysteme I (PDF) (in German). Munich, Germany: Hochschule München. Archived (PDF) from the original on 2022-05-08. Retrieved 2014-02-13. (9 pages)