Path: utzoo!attcan!uunet!mcsun!ukc!dcl-cs!aber-cs!thor!pcg From: pcg@thor.cs.aber.ac.uk (Piercarlo Grandi) Newsgroups: comp.arch Subject: Re: Memory utilization & inter-process contention Message-ID: Date: 2 Sep 89 21:00:27 GMT References: <3332@blake.acs.washington.edu> <261500008@S34.Prime.COM> <2389@auspex.auspex.com> <3398@cbnewsh.ATT.COM> Sender: pcg@aber-cs.UUCP Organization: Coleg Prifysgol Cymru Lines: 89 In-reply-to: dwc@cbnewsh.ATT.COM's message of 28 Aug 89 22:35:15 GMT In article <3398@cbnewsh.ATT.COM> dwc@cbnewsh.ATT.COM (Malaclypse the Elder) writes: i've been doing work on demand paging for unix system v for quite some time [ ... ] it has been labeled "bad" by academia because of belady's "fifo anomaly" which showed that with fifo, there exist "some reference strings" in which having more memory will lead to more faults than with smaller allocations. now this is only my opinion, but i believe that it does not pay to worry about such situations as long as, in general, giving more memory leads to less page faults. and fifo does exhibit this trend. The non monotonicity of fifo is not terribly worrying. As long as you can show that it does not occur frequently. My own favorite page replacement policy is (local) page fault frequency, as it automatically balances the load between memory and and disc. The great advantage of ws over pff is that ws performance is not very sensitive to its parameters, so tuning is not difficult, while pff is not so lucky. Pff, by the way, is non monotonical. A very interesting, forgotten article by Dijkstra argues for essentially what is essentially pff. The argument is compelling; ws minimizes the space time integral, and pff balances the load between disc and memory. That is ws is optimal only if the configuration is optimally balanced for the job mix running on it, because the lowest space time integral gives the lowest cost only in that case. Example: assume that memory is scarce relatively to disc bandwidth; it may well pay to allow higher page fault rates, up to filling the disc bandwidth. Another interesting idea contained in Dijkstra's paper is that it would be nice, actually very very nice, if the hw had ways to cheaply calculate the page fault rate with one page more and one page less than those allocated to the current job. This would improve working set selection very much. however, the other "problem" is that based on some simulations with some reference strings, fifo seems not to do as well as lru. Fifo is bad because usage frequency does not really feed back, of course, and locality info is not exploited very well. anyway, in my studies, i have also come to the conclusion that a reference bit may not be that desirable anyway since you don't necessarily want to do a linear scan of all the page table entries of either a process (local stealing) or the system (global stealing) in order to find a page to steal. There are shortcuts. A paper I remember on SIGOPS detailed the design of the Univac 80 (IBM lookalike, ex RCA) ws pager. It tried hard to minimize such overheads, and to provide an efficient proxy to the true ws rule of time based victim selection. Seemed well done. Another interesting (old as well) paper seems to be that describing the VM ws pager done at Grenoble. The current situation is that clock pagers in BSD and system V are not nice. The BSD pager was designed very very well by an extremely competent person with a specialization in performance analysis of virtual memory; unfortunately it was developed on a machine with 512Kbytes. On today's machines with 8-16-32 Mbytes, a clock scan may take several minutes, making the well designed algorithm essentially useless. A good example of how unanticipated changes of scale make algorithms inappropriate. and there are people here who were looking at working set schedulers for system v that attempt to address the issues presented by the original poster. The system V pager also uses clock, with the same problem. Too bad that the system V pager interacts with one of the worst swappers around. I would really like AT&T to redesign the system V swapper. Even Bach says it stinks. but we have to re-engineer those ideas for sun's VM architecture which makes its system v debut in release 4 and it remains to be seen if those ideas are compatible with the VM architecture. I hope that system V.4 has a better pager and swapper. It is not true like many people assume that memory is infinite and all machines are single user, so paging essentially never occurs and swapping should never occur. On top of that, the SUN vm architecture is not the most smooth around; it was designed with the SUN hacker's principle in mind, "as long as it performs/works in some frequent enough cases, people will buy it". -- Piercarlo "Peter" Grandi | ARPA: pcg%cs.aber.ac.uk@nsfnet-relay.ac.uk Dept of CS, UCW Aberystwyth | UUCP: ...!mcvax!ukc!aber-cs!pcg Penglais, Aberystwyth SY23 3BZ, UK | INET: pcg@cs.aber.ac.uk