What If Pages Can Be Written To…?
So now we've got to deal not just with demand-paging the program code, but dealing with the program data as well? Data that can change while the program is running?
Yes.
A Page Trace with Writes
We're going to extend our trace of ls to include all data written to memory except the stack (which is constantly read from and written to and thus likely to never be paged out). Our page trace has grown to 2376 steps.
Now, as well as a referenced bit for each page, we need a dirty bit. This bit is set whenever a page is written to. If a page is dirty, we can't discard it until we've first saved the data to disk. In our simulation, the color of the flag in the top-right corner of the frame is changed to red when a page is dirty. (If the referenced bit is cleared while the page is dirty, the flag sags right a bit until the page is written to disk, at which point the flag falls over.)
Hay! Read-only program data comes from the executable. But data might not have been loaded from anywhere, it might have just been zeros initially. So where are we going to write it?
-
We need some dedicated space on disk to write the data to. We'll call it the swap space.
Shouldn't that be called paging space?
Remember that early Unix systems didn't use paging, instead they swapped out the entire memory image of a process to disk. So it was called swap space. And the name stuck.
Meh. The 1970s are alive in Claremont.
Importantly, we have more to do when we clear the referenced bit. With the last example, we just flipped the bit. Now, if the page is dirty we need to write the page to disk before we can reuse the frame. (That said, despite the importance of this aspect, we won't include the time it takes to write to disk in our simulation. Typically, some time passes between when the referenced bit is cleared and when the page is actually replaced, so the delay caused by writing to disk is usually masked.)
Tweaking the Clock Algorithm
Although our auto-advancing clock algorithm would work in this case (and you can try it in the simulator below), we'll use this opportunity to show another variation on the clock algorithm, called the Two-Handed Clock. This algorithm has two pointers—one clock hand (red) performs page replacement, and the second clock hand (blue) clears the referenced bits.
So what's the difference?
-
In the auto-advancing clock, the clock advanced at a fixed rate. In the two-handed clock, the blue hand moves forward to clear the referenced bits to ensure that there are always a specified number of unreferenced pages in memory. So instead of constant-rate, the movement of the blue hand is ensuring a constant number of unreferenced pages.
-
So whenever a reference flag goes up anywhere, the blue hand has to knock down the next flag?
-
That's right.
Also, in the auto-advancing clock, because it only has one hand, the movement of the hand to clear flags also determines where we look when we need to replace a page. In contrast, with the two-handed clock, the movement of the blue hand to clear flags is independent of the movement of the red hand in evicting and replacing pages, so the blue hand doesn't affect where the next page replacement will happen.
Visualization of Page Replacement
Number of Frames10
Next Page: XX
Status: Message
Total page faults: 0
Disk Write Stalls: 0
You Experiment…
-
Meh. Looking at number of page faults, it seems like a bit of a wash. The two-handed clock and the auto-advancing clock are both close approximations of LRU. Although it might seem like there's an observable difference between the two clock algorithms, tweaking the parameters can flip the order of the two. So basically messing about with the settings trying to figure out the best one is just a waste of time.
-
I don't think it's a waste of time! Look at the number of writes to disk—the two-handed clock performs fewer writes to disk, at the cost of a few more page faults if you tweak the settings to get the best write performance. So it's another trade-off.
-
Hay! What's the deal with the aborted writes?
-
They happen when we try to save a page to disk, but before we're done, another write happens to that page, meaning that the data we were trying to save to disk is stale and the disk write should be aborted.
-
Instead of aborting writes, some systems will lock the page until the write is complete. But that will cause a stall because the process has to wait for the write to complete.
-
So are all the paging algorithms variations on the clock algorithm?
-
Actually, no. Let's look at one more…
(When logged in, completion status appears here.)