A suggestion about working sets

["David L. Andre" <DLA@diamond.s4cc.symbolics.com>]

Thanks for your input.  On 3600-series computers, it is true that the
page replacement algorithm does not take into account any information
about activities using the pages, and it is true that in some cases this
hurts overall paging performance.  What to do about this is and has been
a subject of research within Symbolics, although I must confess not as
active a subject as I would have liked.  In any case, we are thinking
about paging problems and are working to improve overall paging
performance.  You will hopefully be seeing the fruit of this research in
a release after 7.2.

    Date: Fri, 6 Nov 87 07:13 EST
    From: Jeffrey Mark Siskind <Qobi@ZERMATT.LCS.MIT.EDU>

    In a discussion I once had with Michael Greenwald
    of Symbolics, I suggested that the lispm should implement
    some form of working set mechanism to keep the poor
    paging performance of one process from affecting another.
    He commented that this is hard when all processes share
    the same address space as ownership of storage is not
    meaningfull. While this is true, it is possible to make
    one assumption which is usually a good approximation
    of reality: Processes usually do not share data so
    an object belongs to the process that created it,
    at least for the purpose of determining the total
    storage in use by a process. Thus tagging objects
    with the process of their creator would allow two
    tallys to be kept per process, one: the total
    ammount of virtual memory in use by that process and,
    two: the total ammount of real memory in use by that
    process. Actually, these tallys would have to be
    updated both by storage allocation, GC, and paging.

First let me comment that your assumption that a global-replacement
algorithm hurts overall paging performance for multiprocess applications
is not always correct.  In fact, often the reverse is true.

Second, In most modern virtual-memory systems, the mapping between
virtual memory and physical memory is based on 1pages0, not objects.
(There are exeptions to this; I can send you references if you wish.)
Unless you are willing to slow down 1every memory reference0 by tagging
every word with a process, you should be talking about tagging pages.

Your assumption that processes usually do not share data is in fact
false on the 3600, even in most user programs.  The main reason is that
the "operating system", such as #'ASSOC, is used by many processors.
This operating system consists of much more data than you might expect.
Most operating systems solve the problem of who owns the operating
system or runtime libraries by partitioning them and treating them
specially.  However, in lisp this is difficult if not impossible to do,
since the line is so vague.

    The tallys would allow two additional types of firewalling
    that most conventional systems *DO* provide which
    the Symbolics *DOES NOT* (despite the claims about greater
    firewalling provided by the 3600 architecture).
    First, it would allow me to set a limit on the amount
    of virtual storage that a process can use. A process
    that exceeds this would signal an error (perhaps with
    a proceed option to increase that limit and continue)
    rather than allowing a run-away process to trash my
    machine with all of its valuable state in other
    processes. (It takes me over two hours to reboot my
    machine these days and load all of my environment.)
    Second, it would allow me to set working set guidlines
    for the pager and scheduler to increase performance of
    interactive tasks while still allowing background
    tasks to run. Often, I run many tasks at once, such
    as reading my Babyl file in Zmail (my Babyl file
    is over 4 megabytes long and takes an hour to read),
    running LaTeX in one Lisp Listener, running some
    Lisp program in another, and trying to edit a file
    in Zmacs. Although the preemptive schedular can (and
    presumably does) give a higher priority to the
    interactive task of editing, the thrashing caused by
    other proceeses paging and reducing the working set
    of the editor causes the editor to be painfully
    slow. If the working set of the higher priority tasks
    is made larger than lower priority ones, then they
    can page all they want, at a lower priority, without
    causing poor paging performance for my interactive
    task.

I fail to see how referencing too much memory will cause your machine to
be "trashed".  I think you're confusing memory references with storage
allocation.  If I'm right, then Symbolics provides exactly what you
want:  do the consing in an area created with the :SIZE option.  (What
the documentation doesn't tell you is that the number you give is
rounded up to the next multiple of 32768.)

As for working set guidelines, nothing exists like that on the 3600
because a process's working set exclusive of other processes is hard
enough to define, let alone measure.  However, individual processes can
control their own working sets effectively with facilities such as
PAGE-OUT-ARRAY and SCANNING-THROUGH-MEMORY.  

I agree that some sort of facility as you request would be nice, and we
have discussed several alternatives at Symbolics.

I also do not believe that a better multiprocessing paging strategy will
help you as much as you think.  Try doing similar operations on a VAX
running VMS, and your editor will be painfully slow as well.  Yet
VAX/VMS has many per-process paging controls, and can accurately limit
the working set of any process.  You cannot escape the fact that you are
doing more work with the same amount of resources.

    Now I know that the overhead of storing a pointer to
    the creating procees in each object would be large.
    But if we make another assumption that there are
    usually at most 15 (or 31) processes ever started
    in a lisp world from boot to reboot then only 4 or 5
    bits of tag need to be added to each object (or word).
    When that runs out the remaining code can be used as
    an overflow code indicating that the storage ower is
    anonymous. This method would require hardware not
    available in the 36xx architecture, but perhaps
    something like the area mechanism can be adapted
    to automatically have each process cons in a different
    area. I don't know if the I-machine architecture
    has the capability to support the ideas discussed
    here but perhaps the next machine (the J-machine?)
    could.

Such information could be kept by the paging system on a per-page basis
with no additional hardware or memory.  The only cost is a slight
reduction in the amount of working set available to applications.  How
to effectively use that information is the much more interesting
question.