Programming Memory Model Timeline

Memory models whole story is one repeated move: take away something the programmer could see, and give a promise in exchange. Flat addressing gave total visibility but zero protection. After that, every step trades a slice of visibility for protection, multiprogramming, or convenience.

Programming Memory Models Timeline

  • 1940's - 1950's | No OS, Flat & Absolute Addressing

    • Program addresses physical memory directly: 0 to N-1, no translation, no protection
    • Fine because only one job ran at a time — nothing else to protect the memory from
    • Machines: EDSAC, IBM 701 (batch, single-program execution)
    Resident Monitors as Automation (mid-to-late 1950s)

    Resident monitors (or batch monitors) facilitated small pieces of permanently-loaded code that automated the job-to-job hand-off and gave programmers a reusable library of I/O subroutines, so you didn’t have to write a card reader routine from scratch for new job.

    GM-NAA I/O (1956) , developed by General Motors and North American Aviation for the IBM 704, is typically cited as the first such system

  • Early 1960's | Base & Bound Relocation

    • Base register (adds to every address → relocation) + Limit register (fault if address exceeds it)
    • Solved two problems with minimal hardware:
      • Relocation: means no need to hardcode physical addresses at compile time
      • Protection: prevented one job from corrupting another’s memory
    • Program still sees one contiguous block, 0..N-1, from its own point of view
    • Machines: IBM 7094 (with CTSS at MIT), early Burroughs machines
    Base+bound needed a privilege mode to work at all

    Base+Bound required a privileged mode to be secure. Without CPU protection modes (e.g., Kernel vs. User), a user program could simply rewrite its own base/limit registers and break out of its allocated memory. Therefore, memory relocation and CPU privilege modes were born together—they are two sides of the same coin.

    Early implementations appeared in the MIT IBM 7094 modification for CTSS (1963) and the Atlas computer (1959–62). But it was the IBM System/360 (1964) that standardized this, formally introducing:

    • Supervisor state (kernel) vs. Problem state (user)
    • Privileged instructions (only the OS could run them)
    • Storage protection keys (hardware-enforced memory permissions)
  • 1959 - 1962 | Paging is Born — Atlas “One-Level Store”

    • Before Atlas: programmers manually wrote overlay sequences — code that shuttled data blocks between fast core and slow drum at the right moments.
    • Atlas automated this: programmer used plain addresses; hardware and software transparently moved fixed-size blocks (pages) between core and drum.
    • First real virtual-address vs. physical-address split — the idea everything after builds on
    • Paper: Kilburn et al., “One-Level Storage System,” 1962
    The replacement algorithm, and a naming footnote

    The eviction decision used a “learning algorithm”: it assumed every page was part of a loop, estimated each page’s cycle time from observed behavior, and predicted which page wouldn’t be needed again soonest. This was an early, hardware-driven ancestor of LRU.

    Also, the term “virtual memory” itself was not coined until 1965 (Corbató), applied retroactively to what Atlas had already been doing since 1962. At the time, it was simply called “one-level storage.

  • 1961 | Segments as Language Objects — Burroughs B5000

    • A different philosophy from Atlas: instead of hiding memory behind uniform hardware pages, every word carried a tag marking it as data or a descriptor, a hardware-protected pointer to a segment (procedure, array, etc.)
    • Descriptors had a presence bit: set meant in-core; clear meant on disk. Referencing a cleared descriptor auto-triggered a fault to bring it back, arguably the first commercial virtual memory implementation, built for a different reason than Atlas’s (language safety, not transparency)
    • Hardware did automatic bounds checking on every array access via descriptors; there was no assembler, i.e., all system software was written in an extended ALGOL
    • This seeded the idea of a “segment” as a programmer-meaningful unit rather than a meaningless fixed-size chuck — what Dennis formalized next
  • 1965 | Segmentation, Formalized

    • Atlas’s paging already gives a huge uniform address space, so why add segments? Because pages, being hardware-arbitrary, can’t express what a programmer actually cares about: sharing one copy of a library across processes at different logical addresses, giving different protection to code vs. data vs. stack, or letting a data structure grow independently of the heap around it
    • Dennis’s proposal: give each process several independent segments — one per procedure, one per data structure — each with its own base, length, and protection bits. Name space (addresses a program generates) is decoupled from memory space (where it physically lives)
    • Cost: an address is no longer one number, it’s (segment, offset) — a pointer storing only the offset is meaningless without knowing which segment it belongs to
    • Paper: Dennis, “Segmentation and the Design of Multiprogrammed Computer Systems,” JACM 1965
    This resurfaces as a pain point later

    This exact (segment, offset) problem is what reappears as near/far/huge pointers in 16-bit x86, two decades later — see the 1978-1985 entry below.

  • 1965 - 1969 | The Synthesis — Multics

    • Pure segmentation (variable sizes) reintroduced the fragmentation problem that paging solved; pure paging provided no natural unit for sharing or protection — a page is just a meaningless slice of bytes
    • Multics combined both: a process’s address space is a set of Dennis-style segments, and each segment is internally broken into Atlas-style fixed pages — (segment#, page#, offset)
    • This three-part addressing became the reference design for most later “serious” architectures; Intel’s 80286+80386 combination two decades later was a direct descendant
    • Paper: Daley & Dennis, “Virtual Memory, Processes, and Sharing in Multics,” CACM 1968
    Protection rings

    Multics also introduced hardware-enforced protection rings — a hierarchy of privilege levels (8, in Multics’s case) attached per-segment, generalizing the binary kernel/user split from CTSS and Atlas into a graded trust model. x86 protected mode still has 4 rings today, though most OSes only use 2 (ring 0 for kernel and ring 3 for user space, leaving the middle rings unused).

  • 1968 | Working Set Model

    • By 1968, paging hardware existed on multiple machines, but nobody had a rigorous theory for when to evict a page — get it wrong and you get thrashing: the OS spends more time paging things in and out than doing useful work, because it keeps evicting pages a process is about to need again
    • Denning formalized the observation that a running process only actively touches a small, slowly-shifting subset of its pages at any moment, aka its working set, and thrashing happens precisely when physical memory can’t hold every resident process’s working set simultaneously
    • This turned paging from a hardware trick into an OS policy problem — replacement algorithms, degree of multiprogramming, thrashing detection
    • Paper: Denning, “The Working Set Model for Program Behavior,” CACM 1968
    The theoretical benchmark for replacement algorithms

    Pair this with Belady’s 1966 IBM Systems Journal paper, “A Study of Replacement Algorithms for a Virtual-Storage Computer,” which defined the optimal replacement algorithm — often called MIN or OPT. This algorithm works as follows: when a page must be evicted, choose the page whose next use will occur farthest in the future (or never). This minimizes the total number of page faults.

    The catch: it is unimplementable in practice because it requires perfect knowledge of the future memory references of the running program—something no operating system can know.

    Despite being unrealizable, Belady’s OPT became the theoretical gold standard. Every practical replacement algorithm since — including the Clock algorithm (used in Unix), various LRU (Least Recently Used) approximations, working set-based policies, and Linux’s kswapd daemon — has been empirically measured against it. The goal of any good replacement algorithm is to approach OPT’s performance as closely as possible without requiring foresight. Belady’s paper thus gave the field a fixed target to aim for: the optimal, an unattainable but invaluable benchmark.

  • 1970's - 1980's | Unix Swings Back to Flat

    • Early Unix (PDP-11, early 1970s) deliberately gave programmers an almost-flat model again — one linear address space per process, fork/exec instead of Multics-style segment sharing
    • Multics’s generality had proven expensive to build and reason about, for benefits most programs never used — most programs don’t need Multics-grade segment sharing, they need one address space, protection between processes, and the illusion of more memory than physically exists; paging alone delivers that with far less complexity
    • This is why “flat virtual address space, paged underneath” is what nearly every OS still presents today
    • Hardware paging catches up: VAX-11/780 (1977), demand-paged VM in 3BSD (1979)
  • 1978 - 1985 | x86 Relearns the Lesson

    • 8086 (1978): segment:offset purely to let 16-bit registers reach a 20-bit (1MB) address space — an addressing trick, not Dennis-style protection, but it inherited all of segmentation’s pointer pain (near/far/huge pointers, manual segment arithmetic) without the protection benefit
    • 80286 (1982): real protected-mode segmentation — descriptor tables, privilege rings — genuinely Dennis/Multics-flavored, but still no paging
    • 80386 (1985): adds a paging unit underneath segmentation — the point x86 catches up to Multics’s segments-of-pages synthesis from two decades earlier
    • Once paging existed, OS designers set every segment’s base to 0 and limit to the max, making segmentation a no-op — exactly what Unix-style flat-address-space OSes did, keeping the segmentation hardware around only for backward compatibility
    • Fun fact: “segmentation fault” outlived segmentation — it’s almost always a page fault today
  • 1990's - now | Flat + Paged, Everywhere

    • 64-bit flat virtual address space per process; multi-level (now 5-level, since Intel Ice Lake 2019) page tables to keep page-table size sane over a huge address space; TLBs cache translations so the extra indirection paging introduces stays fast
    • None of what follows is a new model — these are features that only make sense because the address a program sees was decoupled from where memory physically lives, all the way back at Atlas:
    • Copy-on-write fork() shares physical pages between parent and child until either writes, then splits them — invisible without the virtual/physical split
    • mmap maps a file directly into a process’s virtual address space, letting the OS page it in on demand like any other memory
    • ASLR (address space layout randomization, mainstream via PaX/grsecurity in the early 2000s) and the NX/DEP bit (non-executable pages, mid-2000s) are security features that are only possible because virtual addresses can be shuffled and tagged independently of physical memory
Memory History Against Memory Model Timeline
Memory model eventYearMemory hardware in use at the time
Flat/absolute addressing1940s–50sMercury delay lines, magnetic core (from ~1953)
Base & bound (CTSS/Atlas)1959–63Magnetic core
Atlas one-level store (paging)1959–62Magnetic core (fast) + magnetic drum (slow, the “page-out” target)
B5000 segments1961Magnetic core
Dennis segmentation paper1965Magnetic core
Multics1965–69Magnetic core
Working set model1968Magnetic core — same year DRAM was patented, but not yet in any shipping machine
Unix flat model, VAX/3BSD1977–79Transitional — core still common, DRAM ramping up commercially
8086 / 80286 / 803861978–85DRAM (Intel had been shipping DRAM chips since the 1103 in 1970)