How does caching, paging, virtual memory, and OS all tie together for UNIX copy-on-write?

Question

In my OS course, the instructor mentioned the following: In UNIX if a parent process creates a new child ("fork") then the child is an exact duplicate of the parent. This means its memory space is a copy of the parent's.

Now if the child process immediately calls "exec", it replaces its own memory space with that of a new program. This means that time spent in copying the parent's memory space is wasted.

So, UNIX has a solution copy-on-write. That is when a child is created the pages of the parent are shared with the child, they are also marked "copy-on-write". So, as long as both are solely reading the page one memory space is shared between the two. But when either of them attempts to modify a page, a new copy is made for that page and page is modified.

So, given this explanation, I have a few questions. Most of them are concerned with the boundary where the software ends and the hardware starts.

1. When a new process is being created, there is a trap to the OS. And the OS does what it does to create a new process. Now, if the pages are marked "copy-on-write" then what happens to the pages of the parent process that were already in cache?

   They are evicted, right?

2. What I particularly don't understand is if the child process tries to write to some page that is still being shared between the parent and child, how will the copy happen?

   From the perspective of the CPU (hardware) that is executing the child process, it makes a write request. There are two cases here: either there was a cache miss, or a cache hit (the page was (at some time) during a read request loaded into the cache).

   If it was a cache hit then wouldn't the hardware just write to that page in the cache disregarding the "copy-on-write" policy of the OS? How would the OS ensure that "copy-on-write" is respected here?

   If it was a cache miss then the request goes to the page table and the page address is retrieved but the question remains the same.

   Since UNIX is not designed for a specfic hardware, how would it ensure that "copy-on-write" is actually happening? Or is there some hardware support to perform something like this? I looked into cache locking but I don't think that can be used here.

Can someone please explain this?

Thank you!

Answer 1

It seems like your understanding of the matter is pretty good. You are just missing one tiny trick: Make the pages read-only.

When the OS forks the process, it maps the parent's pages also into the child, AND sets the pages to read-only. Before doing that, it also has to remember what the pages were set to before, for reasons we will see soon.

Now, since the pages are set read-only, every attempt to write to the page, from either the parent or the child, will raise an "illegal write" error exception which is trapped by the OS. The OS copies the page, sets both the old and the new page to be writeable, and everything works as we expect it to: pages that are never written are shared, pages that are written are copied lazily at the first attempt to write to them.

And if we immediately exec after the fork, then we completely re-map the child to a different address space and set the pages back to their original read/write status. Which means the only overhead we have for fork + exec is mapping the address space for the child twice and changing the accessibility of the pages to read-only and then back to the original. But we never copy anything, which is what we want to achieve.

There's some small wrinkles to it, but that is the gist of it.

One of the small wrinkles is that the page may not be intended to be writeable in the first place. That's why we have to remember what the status was before we made it read-only: if it is meant to be read-only and was read-only the whole time, we should of course not copy it and make it writeable, but instead treat this like we would treat any other illegal write, which usually means terminating the process with an error code.

Another small wrinkle is that we only looked at the special case of a parent and a single child. But, of course, a parent can fork multiple children, and each child again can fork multiple times, and so on. So, we need to do something a little more sophisticated here, namely, we need to keep a reference counter for each page, telling us how many processes are sharing this page right now. When we copy the page, we decrement the reference pointer of the old page by one and create the new page with a reference counter of one. Only pages with a reference counter of one can be writeable.

This gets again more complicated when we consider shared pages, i.e. pages that are meant to be written by more than one process.

The other small (and some of them maybe not so small) wrinkles are performance-related. For example, the question: at what point does it become more efficient to just copy the whole thing instead of trapping, copying a little bit, trapping again, copying a little bit, and so on and so forth.

But this is unrelated to the basic semantics of the operation. On the fundamental level, the basic trick is really just this: make the pages read-only and trap the illegal write error exception that will occur if either parent or child process tries to write to the page.