CSE Roadmap

Common tier · about 5 hours · 6 parts

Part 5 of 6 · 4 min read

Copy-on-write

Copy-on-write

In plain words: Creating a process with fork (Level 1) appears to need a full copy of the parent's memory. For a parent with 1 GiB of data, copying would take about 130 ms at the copy speed measured on page 2 (7.8 GiB per second), and use another 1 GiB. Most children call exec almost at once and throw the copy away. Systems avoid the waste with copy-on-write (COW).

At fork, the kernel does not copy the pages. It copies the page table, so that the child's table points to the same frames as the parent's. Then it marks all these pages read-only in both tables, whatever their normal permission. Both processes run, and read the shared pages without any cost. When either process writes a page, the hardware traps (the page is read-only). The kernel sees that this is a COW page, allocates a new frame, copies the 4 KiB of that one page, maps the copy writable into the table of the writing process, and lets the write continue. Only the pages that are written are ever copied.

The test counted page faults with getrusage. The parent touched 1,000 pages. Then it forked, and the child first read all the pages and then wrote them:

Step Page faults
Parent: first touch of 1,000 pages 1,000
Parent: a second write to the same pages 0
Child: read all 1,000 pages after fork 0
Child: write all 1,000 pages 1,000
Parent: write all pages after the child has exited 1,000

The child's reads were free, since the pages were shared and readable. Each write cost one fault, which copied the page. The last row is a surprise: the parent also took 1,000 faults when it wrote after the child had exited. The pages in the parent's table had been marked read-only at fork, and stayed so until the first write, when the kernel found that nobody else shared the page and simply made it writable again, without copying. The count of faults was the same as for a copy, although no data was copied.

The effect on fork itself was measured by timing fork for a parent with different amounts of touched memory:

Memory touched by the parent Time of fork
1 MiB 0.05 ms
64 MiB 0.56 ms
512 MiB 3.70 ms
1,024 MiB 7.35 ms

The time grows with the size, but slowly: 1 GiB took 7.35 ms, against the 130 ms that copying the data would take. What grows is the copying of the page table (page 4), and the marking of pages. Without COW, fork of a large process would be many times slower.

Copy-on-write

Copy-on-write (COW) is a technique in which two processes share the same physical pages, marked read-only, after a fork, and a page is copied only when one of them writes to it.

Example: after fork, the child that only reads 1,000 pages causes 0 page faults and copies nothing, while writing them causes 1,000 faults and 1,000 copies.

Common mistake

fork does not copy the memory of the parent. After a fork and a write in the child, the parent's data does not change, because the child's write goes to its own copy of the page. Do not expect one process to see the other's changes unless the memory was mapped as shared.

Interview angle

"Why is fork fast?" It copies the page table, not the data, and marks all pages copy-on-write. A page is copied on the first write by either process. Add that a child that calls exec right away never copies anything.

Check yourself: 1. What does the kernel copy at fork, and what does it not copy? 2. Why did the child's reads cause no faults? 3. Why does a multithreaded program that forks often prefer exec in the child (Level 5, page 6)?

Words you will meet

Word Meaning
Segment A region for one part of a program, with its own base, size and permissions
Segment table The table of bases and limits for each segment
SIGSEGV The signal sent for an illegal memory access
Guard page A page with no permissions that catches an overflow
Shared page A frame mapped by more than one process
Rss The part of a process's memory that is in physical memory
Pss Rss with shared pages divided among their users
Copy-on-write Share pages after fork, and copy one when it is written
mprotect The call that changes the permissions of pages

Quick notes

  • A segment is a region of an address space that holds one logical part of a program, such as its code or its stack, with its own base, size and.
  • A segmentation fault is the error that occurs when a program accesses memory in a way the page table does not allow, for example by writing a read-only page or.
  • The proportional set size (Pss) of a process is the memory it uses counted so that each page shared among several processes is divided equally among them; the Pss of all processes adds up to the real memory in use.
  • Copy-on-write (COW) is a technique in which two processes share the same physical pages, marked read-only, after a fork, and a page is copied only when one of them writes to it.