OSDev.org

Well, no. Early timesharing systems that swapped out whole processes *did* call that swapping.

First you had the systems running on hardware with no memory management at all, where there was only one userspace program in memory at a time, but the OS would write that program to disk and bring a new one in at every timeslice (which worked because timeslices were coarser and program sizes smaller than these days).

Then you had hardware with larger memory and segmented memory management, where each program got assigned one segment (or several), and the OS would still swap out entire programs, but only under memory pressure, not on every timestep.

Both of these were called swapping.

From there, you got to systems with paged memory management, which allowed just part of a process to be swapped out at a time, instead of the whole thing. Actually, segmented systems with multiple segments per program could do this too, but generally with less granularity and less flexibility about what you could actually do, depending somewhat on the exact architecture (the PDP-11 was better than the 286 in this regard, but neither was as good as hardware with actual paging).

Paging hardware allowed for leaps and bounds in what swapping could be used for, and so swapping that took advantage of this came to be called "paging".

The boundaries between these different stages were a bit fuzzy. One reason was that some systems had features that could be considered intermediate between two stages. 8086 segmentation, for example, expanded the address space and provided for easy relocation of code, but had no provision for protected memory, so it couldn't be used to trigger swap-in when an attempt was made to access a segment, so the 8086 fell more into the "no memory management" camp than the "segmented memory management" camp. The PDP-11s with memory management had a segmented memory management scheme with 8 segments per address space, so it was almost a paging system.

Another reason the boundaries were fuzzy is that the different form factors reached these stages at different times. Mainframes got to paged memory management while minicomputers were still in their infancy, and minicomputers were just getting to paged memory management as microcomputers took off. Furthermore, operating systems tended to lag the hardware somewhat: Unix/32v was the AT&T Vax port of Unix, but simply translated the memory management scheme Unix had used on the segmented PDP-11 to the paged Vax without actually making use of any of the new features that paging made available. And while robust paged operating systems for microcomputers appeared within a few years of paged hardware (NT, OS/2, Linux), Mac OS never transitioned away from being a single-address-space system until they transitioned to Unix with OS X, and while Windows did better, consumer versions of Windows still had core components that treated the system as one without memory management right up until XP came out (which was why Win16 and Win9x had a reputation for being burning piles of unstable manure).

Across *all* of these stages, at various times, there has been the concept of overlays. Overlays are the same *idea* as swapping, but they are distinguished from it in that overlays are managed by the application, not the OS (though the OS may contain facilities to assist applications in the use of overlays).

On very early systems with no memory management, or only segmented memory management, where the amount of memory available to applications tended to be limited by the actual amount of physical RAM available, programs used overlays to deal with working sets that did not fit in RAM.

Later on, even into the present day, on machines with more physical RAM than address space, or on paged systems where swap can be used to provide more backing store than the available address space, programs use overlays to deal with working sets larger than the address space. In this case, overlay data that has been "swapped" out of a process's address space may very well still be in RAM, just unmapped from the process's address space so that something else can be mapped in at the same address.

Many early microcomputers had only 64k of address space, so if the system had more than 64k of RAM, not all of it could be connected to the CPU at once, and in practice the limit was less than 64k because large portions of the address space were taken up by ROMs for system firmware or by things like video memory that couldn't be used arbitrarily. So these systems needed bank switching hardware to deal with large amounts of RAM, and programs needed to arrange themselves and their data into overlays that could be bank-switched out to allow other overlays, or ROMs, or video memory, etc, to be switched in.

The PC had a larger address space (1 megabyte, of which 640k was available freely to programs), so it took longer to run up against this, but when PC's started shipping with megabytes of memory, "expanded memory" was introduced, where an expansion card would bank switch a 64k window above the 640k line, which programs could use for overlays. A problem with this was that the memory on the bank switching cards was generally not mappable above 1M when a 286 CPU was operating in protected mode, so separate memory was needed for that. There was some software available that used the same ABI as the firmware on the expanded memory cards and swapped the expanded memory window to disk rather than bank switching in RAM, which gave the same effect with a performance penalty. When the 386 came out, though, the paging features of the 386 allowed emulating an expanded memory board in software at no performance cost (because a CPU with a paged MMU effectively *is* an expanded memory board, with the added benefits of being finer-grained, and allowing any page of memory to be bank switched to any page-aligned address).

On segmented-memory minicomputers with constricted address spaces, like the memory-managed variants of the PDP-11, programs didn't have to share their address space with ROMs or device drivers (on the PDP-11, not even with the kernel, as it had its own set of segment registers and its own address space), but if they ran beyond the available address space, the OS often provided facilities for a program to request that a given module be unloaded and another loaded to the same address.

More recently, I've heard that 32-bit PAE versions of Windows include overlay system calls for programs that need more than 4 GiB, though that was mostly needed for servers and the 32/64-bit transition has been pretty much complete in that space for a while (even for consumer PCs it's mostly over, with Linux distributions starting to drop their 32-bit variants).

Even without OS support, however, overlays could be implemented by the application itself on a modern system by using something analogous to the combination of memfd_create() and mmap() on Linux (or even just mmaping files on disk, depending on the level of security from interference from other programs needed).

In summary, the difference between "swapping", "paging" and "overlays" is:

"Swapping" refers to the OS writing programs, or parts of programs out to disk in a manner that is transparent to the program involved except insofar as it affects timing (and insofar as access to the system clock is provided to programs, which has generally been the case historically, but may need to be reconsidered in the future for programs that don't absolutely need it to mitigate Specter/Meltdown type timing attacks). It can be used to refer to any such process, but the word is often used to designate non-paged swapping in contexts where paged and non-paged swapping are differentiated.

"Paging" refers to hardware features that provide fine-grained, whole-memory bank switching, generally with accompanying memory protection mechanisms. It also refers to operating systems making use of those features to isolate programs from each other, provide programs with a view of their address space that is independent from their location in physical memory, allow programs to share memory, swap data to disk when under memory pressure etc. It is furthermore used more narrowly to refer to specifically to paged swapping, sometimes as part of the concept of demand paging, wherein swapping occurs strictly in page-at-a-time increments, and files are generally not loaded into memory all at once, but just recorded to be mapped to a certain address in a process's address space and pulled in a page at a time when and if the program attempts to access each page.

"Overlays" are, basically, application-driven swapping. Unlike swapping proper, they are *not* transparent to the application, the application has to explicitly request that the OS flip overlays (or manipulate the hardware to flip overlays on MMU-less systems, or munmap the current overlay and mmap the new one on memory managed OSes with no direct support for overlays). If it doesn't it will access the overlay currently loaded at the address in question rather than the one it wants to access, whereas with swapping, what the application sees as loaded at a given address doesn't change; it's just that the application may be swapped out and not runnning, or the OS may need to fetch the data the application is attempting to access before allowing the application to continue.

you forgot to say, that it's called that only on Unix clones. on Windows, writing process' working set pages to disk is called paging (PAGEFILE.SYS - we all saw that thing).



only Intel calls this feature paging. there are also segments, so "paging" term makes sense (it mirrors the fact, that Intel finally discovered pages for themselves, when everybody has had it for a long time). ARM for example doesn't call it paging. as well as doesn't have segments (that could be used instead of pages). ARM calls it VMSA - virtual memory system architecture, and that architecture has only pages (and blocks, but it's not mutually exclusive, blocks are a "huge pages" equivalent). MIPS doesn't call it paging and I suspect POWER and SPARC don't either.

Personally, I don't like the term swapping in relation to paging out pages to the secondary storage, because it does not reflect the real nature of the process and is therefore misleading. it implies exchanging one process working set to another, it was like that in the far past but it's not like this now. just like with those teletypes. I don't see any teletypes, what all those ttys are refering to? (I bet, they are still there because they remind beardy unixoids about titties existence ).

but of course, since most people here are making Unix clones on Intel architecture, they will use that swapping for paging and paging for virtual memory.

That's because Windows has only ever swapped on systems with paged MMUs, and because "pagefile.sys" is the name used on NT, which never even ran (let alone swapped) on unpaged systems. The pagefile on DOS-kernel Win3 was called 386SPART.PAR or WIN386.SWP, and was called a "swap file" in the Windows help files, even though it, too, was implemented in terms of paging, and was only used on systems where paging was available.

A big part of the reason that Unix uses the term swapping is that early implementations ran on the PDP-7 and PDP-11/20, which had no memory management whatsoever.


only Intel calls this feature paging. there are also segments, so "paging" term makes sense (it mirrors the fact, that Intel finally discovered pages for themselves, when everybody has had it for a long time). ARM for example doesn't call it paging. as well as doesn't have segments (that could be used instead of pages). ARM calls it VMSA - virtual memory system architecture, and that architecture has only pages (and blocks, but it's not mutually exclusive, blocks are a "huge pages" equivalent). MIPS doesn't call it paging and I suspect POWER and SPARC don't either.[/quote[

When speaking generally, without reference to any particular architecture, it's called paging. And whatever ARM or MIPS call their virtual memory mechanisms, I don't think anybody involved with designing those mechanisms would dispute that they are paging mechanisms.



You're still exchanging *something in RAM* with *something on disk*, just at finer granularity.



Even "virtual memory" has multiple meanings: it can refer to paging or segmentation features on the CPU (or the combination of the two on architectures like x86), or to the process of swapping (usually paged swapping); the dialog used to configure the swap file on Win3 was titled "virtual memory".

"generally speaking" it's where? in intel manuals? how about the VMS name, what it meant? i wasn't there, but i heard, when this mechanism appeared, it was named "virtual memory". nowhere outside x86 it's refered as "paging". the emphasis that it's a "paging" mechanism makes no sense say on ARM - there is always one mechanism and nothing else, the memory is seen as a space of pages/frames both "physical" and "virtual", and the mapping (virtual memory system) is established between these only entities; there is no need to emphasize it's paging or framing or whatever, as there is nothing else, whereas x86 has yet segments, so it's either flat "paging" mapping or not so flat and "generally speaking" - oversofisticated "segmentation". basically that "paging enabled" means "oh, you don't want to use segments and want those "pages", here you go" and only there this term makes sense. on others, you just turn on MMU and configure stuff, you don't choose whether VM will be organized as "paged" or as "not exactly paged". yes, i am aware about mips kseg0/kseg1, but it's another story.


exactly I do NOT exchange something to something (as it was when it was swapping), I just throw contents of a page from RAM on disk, and the page in RAM becomes free, - that's why it's not swapping.

I am not going to fall into this needless argument about how one wants to call things, just tried to express my view on this, hopefully in short, not more. even if some think their terminology is "equaller than others". xD personally, i won't call paging swapping and it's enough. xD

It seems that the DPMI specification needs paging.

Also, paging is much more understandable if we implement it from the point of view of DPMI, and it also makes it possible to program externally or internally in terms of DPMI services for a start of memory management in a system.

DPMI can be extended for 64-bit paging if we define the same services for 64-bit.

It would make for compatibility with DPMI software in our OS and we would have to implement paging without errors, but it makes immediately obvious if we are doing so.

So DPMI is a real-world case of a program layer that truly needs paging for something useful.

Perhaps "needed" would be more accurate.

No, the DPMI spec explicitly allows functions related to paging to be unimplemented or implemented only as stubs, so as to allow DPMI to be implemented on 286s.

For example, in Operating Systems, Internals and Design Principles, by William Stallings.

And of course I'm not talking about the Intel manuals. I said "when speaking generally, without reference to any particular architecture".



"Virtual memory" can refer to *any* mechanism in which the addresses used by programs are not the physical addresses that the processor puts on the bus for those accesses. It can include segmentation schemes as well.



Systems that combine segmentation and paging are rare, but segmentation-only architectures have existed, and even if a particular architecture only uses one or the other, there is a need to have terms to distinguish the two in order to compare different architectures, and to let OS developers working on multiple platforms know what features they can expect to have on a given platform.

Most modern VM implementations are paging-only, so it's of less importance now than it was historically, but even when we get to an era when there are no extant architectures that implement segmentation, it will be useful to distinguish the two, so that when some CS student reinvents segmentation and thinks it's the greatest idea since sliced bread, his professor can shoot him down and say "That's called segmentation, it was popular in the past, but this is why we don't use it any more...".



Once paging was available on x86, almost everybody decided that they didn't want to use segmentation anymore, but turning on paging doesn't *necessarily* mean you don't want segmentation, nor does it disable segmentation, if you don't want to use segmentation you just set up the simplest workable segmentation scheme (and in long-mode you're forced into that segmentation scheme, but even then, you still need to define the relevant segments).

But it's *not* just when working with Intel that distinguishing between paging and segmentation makes sense, because, once again, you need to be able to compare architectures even if any given architecture only uses one or the other.



But one of the biggest reasons you'll be writing pages out to disk is that:

1) Some program accesses a page that was previously written out to disk
2) The access page faults because the page in question isn't in RAM.
3) Thus the page has to be loaded back into memory for the program to continue.
4) There's no free memory available to load the page into.
5) Thus we have to find a page in RAM to evict to disk.

So we *are* exchanging something in RAM for something on disk, thus we are swapping.

Now, you could argue that sometimes you need to write pages out to disk because a program has allocated new pages (which, by definition, have never been on disk), and there's no free RAM to back the new pages with, so there's nothing to be exchanged, so we aren't "swapping", but:

1) This also applies to segmented swapping systems (when new segments are created or old ones are extended and there isn't free RAM to do so), and to MMU-less swapping systems (such as the case of fork() on Unix running on a PDP-11/20, where the parent process is written out to disk as if a process swap were occuring, but the child continues running from the parent's memory image).
2) The evicted pages will eventually need to be brought back into RAM, and if memory pressure hasn't been relieved by then, that will involve evicting other pages (thus, swapping).
3) I've never heard this distinction made, regardless of the type of hardware memory managment available (none, segmentation, paging). If stuff is being written out to the swap file/partition it's being "swapped out", and if it's being read in from the swap file/partition, it's being "swapped in", regardless of whether it's actually being exchanged with anything.

Now that I think about it, paging would be uniquely useful for copying ROMs into RAM and patching them. It couldn't be done fully transparently without it, without pages mapped totally outside the virtual space.

Also to get a fully standard hardware address space formatted for our system.

All this would be extremely useful now that there are machines with UEFI. We could patch or replace UEFI even if it's in ROM with something that is more standard like our BIOS for 16/32/64-bit by redirecting the UEFI code range with the same virtual addresses.

@linguofreak, I meant, that calling that system "paging" is influenced by Intel and all those authors of course thought the "intel" way in the first place, since x86 is a dominant architecture, but the term itself is not good because it's not descriptive, which it's not a rare thing by itself and is pretty tolerable, what it worse - it collides with another phenomenon naming (that one, unix followers call "swapping"). this thread is a good example of the confusion. calling this two level addressing system "paging" is as useful and descriptive as calling the modern addressing scheme of disk sectors "blocking". "very" descriptive and "not a bit" confusing. the term "virtual memory system" on the other hand is neutral enough to be a good term for that. with farther rectifications of what exactly kind of it is used, where necessary. not that "virtual" makes a good fit here, but eh, not that bad as biasing towards the particular architecture and its naming quirks. I, personally, like to call "virtual" addresses "process(or)" addresses and "physical" addresses "system" addresses.


It would be at least a hint on "swapping" if it happened the way you depicted (because it would become a "swapping" only in the event of total free memory exhaustion), but it doesn't and we still not "swapping" anything. Starting with p. 4, it's not like it is. instead, consuming free pages and producing them are 2 separate processes separated in time and the system takes care to not let free pages exhaust entirely. pages for bringing content from disk are always taken from the free pages list. there are several states pages are in and there are lists when these pages reside. memory manager activities, say "processes", monitor areas of their responsibility and making sure the free pages list is never empty is one of them. the producing free pages process takes care of filling the free pages list timely, when the latter gets too short, not when it's totally exhausted. compared to what you depict, this at least means faster page fault handling (because slow disk operation (page out) has been done beforehand in the background, based on "the free list too short trigger", not when there is zero free pages :O).
so when a page fault happens and it's time to get content of this previously evicted page back in RAM, the page is taken from the free list. on the other end, pages for filling the free list are taken from the standby list - these are pages taken off of the process working set, but whose contents is still valid and yet - synchronized with its backing storage. these two processes don't happen one by one, they are loosely related, so, no it's not swapping. yet once. when page fault handling needs a page for bringing content back in RAM from disk, it takes page from the free list, always. no exchange happens. you don't evict content at this point. free list cannot be exhausted at 100% it's a catastrophic event, system won't proceed. for this not to happen, it monitors the length of the free list, and beforehand takes actions to not let that disaster happen. namely, it pulls off pages from the standby list. and filling the standby list is another MM activity - if the list is short, it fills it independently of what is happening in the free list - either by trimming working sets or by writing back dirty pages from modified pages list - dirty pages already pulled off of WSs, whose content is not synchronized with the backing storage. after cleaning pages, they go into standby list and when it's needed free list filling process may take them and farther up to finally satisfying the demand for allocation. of course, WS trimming, dirty page writing, - standby list feeding, and free list feeding happens beforehand, independently of each other and of the free list consumption, they are triggered by some thresholds on the appropriate lists. if you imagine this dynamics, you'll see - there is no exchanging, therefore no "swapping".