From: oreillym@tartarus.uwa.edu.au (Michael O'Reilly) Subject: Re: .97 (new buffer allocation code) Date: 5 Aug 1992 02:32:48 GMT
davidsen@ariel.crd.GE.COM (william E Davidsen) writes:
: In article <1992Aug4.035247.5999@uniwa.uwa.edu.au>, oreillym@tartarus.uwa.edu.au (Michael O'Reilly) writes:
:
: | One thing that would improve things as well is doing pageing before it
: | is needed.
: |
: | i.e. if the buffer drops below Y buffers, and there is less than Z free
: | pages, it starts useing a standard clock algorithm to page least
: | recently used pages to disk.
: | This would fit in very nicely in the idle process. (which
: | currently just busy waits)
:
: I believe that there might be a good case for having an additional
: state for pages instead of two. Currently pages are in use, or free, or
: i/o buffers. One method which seems to offer room for a lot of
: improvement is to have a additional state for pages near the end of the
: LRU list. By unmapping those pages from all processes but not freeing
: them immediately, you get the chance to see if they are really in use,
: by getting a page fault and remapping them, and putting them back at
: the top of the LRU list.
The 386 chip has a feature that lets you acomplish the same idea without
any fancy schemes like that. The basic idea is that when a page is
accessed for the first time, a bit is set in the page tables. WHen it is
written, a different bit is set.
So the way to do this is to clear all the bits, and then cycle through
doing.
is bit set?
yes -> clear it and go to next
no -> it can be swapped, swap it and move on.
This is a standard pageing algorithm, that has the really nice advantage
that the amount of swapping is purely dependant on the speed at whch you
cycle through the pages.
: This really is a savings, since if you fully released the page you would
: have to unmap (same), write it out if dirty (improved), read it back in
: (improved), and remap it (same). On the other hand, if the page is not
: active any more, when space gets tight you just write it out or release
: it. It is true that on a system with everything in memory, but just
: barely, this could result in a bit of overhead due to marking and
: unmarking pages, and therefore the number marked should be tunable,
: preferably by the kernel at runtime, based on the ratio of program size
: to physical memory, physical page fault rate, etc.
From what I understand here, you are trying to find a set of pages that
are being used, but are still mapped. Correct me if I am wrong , but
trhat is what the above algorithm uses.
: The benefit of this is that you tend to concentrate physical i/o on
: pages which are not going to be needed again, rather than pages which
: have been in memory for a long time.
There isn't actually a LRU list for pages. Only for buffers. Buffers get
moved to the start of the list every time they are accessed. Pages get
free'ed when the process useing them exits, or when the kernel runs out
of memory and starts swapping. (in 0.97. 0.97a uses a slightly different
scheme). The above algorithm achives swapping the set of pages that
haven't been accessed in some time T without actually haveing to use a
list.
: bill davidsen, GE Corp. R&D Center; Box 8; Schenectady NY 12345
: I admit that when I was in school I wrote COBOL. But I didn't compile.