Copy-on-Write
Creating a process used to mean duplicating everything it could see. Copy-on-write does not: both sides share the same pages, marked read-only, and a page is duplicated only when somebody writes to it. The saving is real and it is easy to overstate, so this page counts the pages and the faults instead of describing them.
New to processes and pages? Start here
A running program does not see the machine's memory directly. It sees its own address space, carved into fixed-size chunks called pages, and a table maps each of its pages onto somewhere real. Two programs can be pointed at the same real page without either one knowing.
When a program forks, it gets a child with an identical address space. Duplicating all of it would be enormous and often wasted: in the common fork-then-exec pattern the child immediately replaces the whole lot with a different program, though plenty of children keep what they inherited and go on using it. Copy-on-write points both at the same pages, marks them read-only, and lets the hardware trap the first write. This page counts what that saves and what it costs.
What a processor actually does
A processor fetches an instruction, works out what it says, does that one small thing, and moves to the next. Add these two numbers. Put this number there. If that number is zero, carry on somewhere else. That is the job, and it repeats a few billion times a second.
Everything that looks like cleverness is arrangement around that loop: keeping the next instruction ready before it is asked for, keeping recently used numbers close by, letting a slow part and a fast part work at once. The machines here are those arrangements, and most of them exist because one part of the machine is thousands of times slower than another.
The machine for this idea on its own is Stored Program, if you would rather press it than read about it.
Two processes, one copy of the memory
1 A forked address space, and a fixed script of reads and writes to put it through
A toy address space of 64 pages, forked, then put through a fixed script of reads and writes. The same script is run twice: once copying everything up front, once copying a page only when it is written.
2 The same script run twice, counting pages copied and faults taken by each strategy
| copy-on-write | copy everything at fork |
|---|
3 The address space left over: which pages had to be duplicated and which are still shared
The address space after the script has run. A filled cell is a page that had to be duplicated; an empty one is still shared with the other process.
copied still shared
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.
| claim | held | measured |
|---|---|---|
| every scenario ends with byte-identical memory either way | yes | 4 scenarios, parent and child pages compared one by one; copy-on-write is an accounting trick, not a change in what the program sees |
| pages copied plus pages still shared is always the whole space | yes | holds in every scenario, at 64 pages; a page is shared or private and there is no third state |
| fork-then-exec copies a handful of pages instead of all of them | yes | lazy copies 3 of 64 and takes 3 faults; eager copies 64, and the exec discards nearly all of them |
| when the child writes every page, copy-on-write is strictly worse | yes | both copy 64 pages, but lazy also takes 64 faults to get there and eager takes 0; the same copying plus a trap per page |
| a read never triggers a copy, because only a write is trapped | yes | 40 reads, 0 copy-on-write faults, 0 pages copied; the child reads the parent's memory directly. A page that is not resident still faults, but that is the ordinary kind and has nothing to do with sharing |
| the parent faults too, because after a fork neither side owns the page | yes | page 0 is faulted by the parent and page 2 by the child, and page 1 faults once across two writes: 3 faults for 6 accesses |
| only the first write to a page faults | yes | three writes to one page cost 1 fault and 1 copy; once private, a page stays private |
| nothing here is timed, and that is deliberate | yes | a page fault costs microseconds that depend on the processor, the page size and what else is resident, none of which a browser can measure; pages and faults are counted instead |
What is real here, and what is not
Nothing on this page is timed
A page fault costs microseconds that depend on the processor, the page size, and what else is resident in memory. A browser cannot measure any of that, so putting a number on it would be invention dressed as a measurement. Pages and faults are counted instead, and those counts are the part that holds on any machine.
The address space is 64 pages, which is not a real one
A real process has thousands of pages and a much less tidy access pattern. Sixty-four is small enough to draw and large enough that the ratio between three copied pages and the whole space is the ratio you would actually see. The shape of the answer is right; the scale is a model.
Copy-on-write is not always the better choice, and the page says so
When the child writes every page it ends up copying exactly as much as the eager strategy, and pays a trap per page on top. That scenario is one of the four here on purpose. An explanation that only shows fork-then-exec is selling the mechanism rather than explaining it.
The fault handler is drawn as one step, and it is not
Taking the trap, finding the page, allocating a fresh one, copying it, updating the tables and restarting the instruction are all separate work, and on a real system some of it is contended. This page treats a fault as a single counted event, which is enough to compare the two strategies and not enough to describe what an operating system actually does.
1972 is the TENEX paper, and TENEX did not invent this either
Copy-on-write is usually credited to 4.2BSD in 1983. Bobrow, Burchfiel, Murphy and Tomlinson describe it in the TENEX paper in Communications of the ACM for March 1972, eleven years earlier, and this page used to stop there. Murphy's own paper at the Fall Joint Computer Conference later that year does not: it says of copy-on-write access that “to our knowledge, this facility was first developed and used on the BBN-LISP system for the XDS-940”. So TENEX is where it is described, not where it began, and the earlier system is named by the man who built the later one.
What TENEX built it for was not fork
This page demonstrates copy-on-write through fork, because that is where most people meet it and because a child that replaces its address space is the clearest case of a saving. Murphy's paper introduces the facility for two other things entirely: programs that are not quite reentrant, which modify a little of their own code or initial data, and programs built on a large shared database that a few users need to change in a few places. His example of the second is BBN-LISP itself, over 100,000 words of compiled reentrant function code plus common list structure, where a user may legitimately need to redefine a function or insert a break point. Fork is a later use of a general page-sharing mechanism, not the thing it was designed around.
Which of these sources were actually read
The TENEX paper in Communications of the ACM is behind the ACM Digital Library's sign-in and has still not been read here; its title, authors, volume, pages and March 1972 date are confirmed against Crossref. Murphy's Storage organization and management in TENEX, from the Fall Joint Computer Conference of 1972, HAS been read, and reading it is what produced the two corrections above: the BBN-LISP attribution and what the facility was actually for. This ledger said for a while that the paper could not be reached, which was true of one paper and not of the other, and nobody had looked for the other. The Smith and Maguire measurements are cited for context and could not be fetched.
Sources
- Daniel G. Bobrow, Jerry D. Burchfiel, Daniel L. Murphy and Raymond S. Tomlinson, TENEX, a Paged Time Sharing System for the PDP-10, Communications of the ACM 15(3):135-143, March 1972.
- Jonathan M. Smith and Gerald Q. Maguire Jr., Effects of copy-on-write memory management on the response time of UNIX fork operations, Computing Systems 1(3), 1988.
- Daniel L. Murphy, Storage organization and management in TENEX, Proceedings of the Fall Joint Computer Conference, 1972, pp. 23–32, in the author's own transcription. Read here, and also checked against a scan of the printed pages. Its section on copy-on-write access is the source for the BBN-LISP attribution and for what the facility was built to do.
- Logical Art, the studio this belongs to.