Abstract

In Operating System implementations, page thrashing - extreme overhead due to management of memory pages - is considered a big problem. In the paged segmented models that are currently used in Operating Systems like Windows XP, Linux, BSD, Solaris, etc., algorithms like the Clock algorithm are used to best approximate the LRU (Least Recently Used) algorithm to find a replacement for pages quickly. The intent of this research is to patch a flaw seemingly inherent in the Clock algorithm that will cause unnecessary thrashing overhead when large numbers of processes are called.

More Information

• The supposed flaw in the Clock algorithm is not that it doesn't work, but that the algorithm requires more than one pass through the master page table for an INTERRUPT. This master page table could be very large, and the overhead associated with such an operation with numerous timeouts and incoming processes should be disasterous.
• The traditional Clock algorithm should work quickly for any master page table that is not full of references (ie has a used bit), but may result in a maximum of 2 full passes of operations on the master page table, in possibly uncached memory references. If the used bit is set on every reference, which will happen eventually in a system under full usage, then the algorithm goes through the entire master table looking for a cleared used bit on the first pass. After not finding anything, the algorithm then commences a second pass to look for a set used bit and a cleared modified bit (the next easiest case to deal with). If the master page table consisted of nothing but set used and cleared bits, the traditional Clock algorithm would thus have two full passes through the table before forcing a used, modified page out of memory. It also seems likely that the last operations/checks on the end of the MPT could push the first MPT references out of cache memory, thus forcing the 2nd pass to perform in the same memory access time constraints (bad). Basically, the second pass would have to fetch the MPT references from main memory again, even though a reference was already used during this same interrupt!
• Proposed solution:
  1. Force algorithm into a worst case of only 1 pass of operations through the master page table or at least force it to look at the known cached references to perform both checks for cleared and dirty bits.
  2. Have instruction implemented into hardware that checks for a used bit and a dirty bit (if no other used / not dirty has been found) throughout table. If no instruction can be implemented (this would be fastest), we should be able to implement a software version that would still save time during heavy usage interrupts because both checks would be performed on the same cached memory block (actually this could be a simple register lookup (like eax) which would be on die in the fastest access memory on chip.)
     • Instruction would use one register (ebx?) to hold index of not used / not dirty entry
     • Instruction would use one register (eax?) to hold index of used / not dirty entry
     • Instruction would stop once ebx is filled or one revolution has occurred
  3. If the instruction filled the ebx register, then simply use that page.
  4. Else If the instruction filled the eax register, then use that page.
  5. Else use the current index (since instruction finished at first entry, this is a clock algorithm without a second pass)
  6. Behavior of instruction
     1. set eax and ebx to FFFFFFFF
     2. Loop through page table
        1. Check if entry is not used
           1. if yes, then fill ebx with not used entry (we're assuming not used / dirty either doesn't exist or is preferred over any used pages) and stop
           2. if no, if eax is not filled, then if entry is not dirty, fill eax

        Note: you could save effort by moving to a separate loop that does not check for (2) if eax is filled.

Downloads

None at this time.

Idea's birth: 4/7/2005 | Webpage creation: 4/11/2005 | Last Update: 11/10/2005

James Edmondson Home Page