How does the enhanced second-chance algorithm has a preference to the changes that have been modified?

user_10402540 0
Viewed 694

I have been reading the textbook "Operating System Concepts, Edition 10 by Greg Gagne, Peter B. Galvin, Abraham Silberschatz"

The textbook first says the following about a modified bit on page 403 ...

"If the bit is set,we know that the page has been modified since it was read in from secondary storage. In this case, we must write the page to storage. If the modify bit is not set, however, the page has not been modified since it was read into memory. In this case, we need not write the memory page to storage: it is already there."

However later in the book, page 410-411 it seems to contradict...

"We can enhance the second-chance algorithm by considering the reference bit and the modify bit (described in Section 10.4.1) as an ordered pair. With these two bits, we have the following four possible classes:

1. (0, 0) neither recently used nor modified—best page to replace

2. (0, 1) not recently used but modified—not quite as good, because the page will need to be written out before replacement

3. (1, 0) recently used but clean—probably will be used again soon

4. (1, 1) recently used and modified—probably will be used again soon, and the page will be need to be written out to secondary storage before it can be replaced

Each page is in one of these four classes. When page replacement is called for, we use the same scheme as in the clock algorithm; but instead of examining whether the page to which we are pointing has the reference bit set to 1, we examine the class to which that page belongs. We replace the first page encountered in the lowest nonempty class. Notice that we may have to scan the circular queue several times before we find a page to be replaced. The major difference between this algorithm and the simpler clock algorithm is that here we give preference to those pages that have been modified in order to reduce the number of I/Os required."

If we are giving preference to pages that have been modified does that not mean that we are increasing the number of IO required? Because if the page has been modified then we need to write that change into the storage?

Sorry I'm confused how the enhanced second-chance algorithm is supposed to reduce the number of IO required.

Thank you.

operating-system algorithm
1 Answers

What I think they mean is the preference is to retain the modified pages in memory (although it reads somewhat confusingly to me).

This sentence:

We replace the first page encountered in the lowest nonempty class

And the ordering of the classes above it means that it would first discard a page that has not been used and not modified.

I would also read "in order to reduce the number of I/Os required" to be applied to the context of immediately needing to solve the issue of not having enough free memory. Usually this issue needs to be resolved as quickly as possible. When there's no write required, that's the quickest. If the OS can free enough pages from the first class to solve the immediate need, then that's a really good outcome.

Often OSs have a "lazy write" or "background write" process. The memory pages with the modified bit set are written to disk 'later' when the resources free up (or there are no unmodified pages available and more RAM is required). This is a major reason for shutting down properly and not pulling the power plug - there are probably many modified pages in memory waiting to be written to disk. So in the context of this paragraph, if the current need can be satisfied by releasing pages that haven't been modified, then the remaining pages may get written by the background write process at a later point.

It's interesting that class 2 is a higher preference than class 3. It would be quicker to solve the immediate problem (need more memory) by discarding something from class 3, because a write is not required. However the OS is predicting that it would be likely to need to read that memory again fairly shortly, and so it does not. There's probably some extremely complex algorithms involved in calculating just how recent "recently used" is. And it probably takes into account speed of the media that is being written to.

user_12542080
Related