Windows NT Paging Algorithms

Question

I've been trying to figure out how the paging works inside Windows operating systems. I found a blog post from Mark Russovich back in 1998 about such memory management. He discusses the "Least Recently Used" algorithm.

The article is a little confusing as his explanation doesn't quite match up with its overview. For example, its overview is:

LRU replaces first those pages that processes have not accessed for the longest period of time

However, the explanation states states that it is judged purely on whether or not an accessed flag is set:

On a uniprocessor, if the Memory Manager finds a page with its Accessed flag set, the Memory Manager clears the flag and proceeds to the following pages, selecting for replacement the next page it finds with a cleared Accessed flag

Surely by this logic, there are no dates to compare, and so if there are multiple pages without an accessed flag, the MMU will pick the first one it finds (which might not necessarily be the "LEAST USED" one?

EDIT: http://windowsitpro.com/systems-management/inside-memory-management-part-2

Answer 1

Well, first, that article is quite old - it predates Windows 2000.

Second, Mark's description of the "clock" algorithm is incomplete. When the Mm finds an Accessed bit set in a PTE, it clears it. Fine so far. But if it finds the bit is already clear, it increments a counter in that page's working set list entry (WSLE). Thus higher counter values correspond to pages that were accessed longer ago.

There is no need to be so precise as to record timestamps.