[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
A suggestion about working sets
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
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?)
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