From: Daniel Phillips <phillips@bonn-fries.net>
To: Alex Bligh - linux-kernel <linux-kernel@alex.org.uk>,
riel@conectiva.com.br, linux-kernel@vger.kernel.org
Cc: Alex Bligh - linux-kernel <linux-kernel@alex.org.uk>
Subject: Re: [RFC] Defragmentation proposal: preventative maintenance and cleanup [LONG]
Date: Fri, 7 Sep 2001 23:56:33 +0200 [thread overview]
Message-ID: <20010907214921Z16337-26183+212@humbolt.nl.linux.org> (raw)
In-Reply-To: <20010907062851Z16136-26184+30@humbolt.nl.linux.org> <1426827386.999856726@[169.254.198.40]>
In-Reply-To: <1426827386.999856726@[169.254.198.40]>
On September 7, 2001 10:58 am, Alex Bligh - linux-kernel wrote:
> Some comments in line - if you are modelling this, vital you
> understand the first!
>
> >> The buddy allocator will attempt (by looking at lowest order lists first)
> >> to allocate pages from fragmented areas first. Assuming pages are freed
> >> at random, this would act as a defragmentation process. However, if a
> >> system is taken to high utilization and back again to idle, the
> >> dispersion of persistent pages (for instance InactiveDirty pages)
> >> becomes great, and the buddy allocator performs poorly at coalescing
> >> blocks.
> >
> > It becomes effectively useless. The probability of all 8 pages of a given
> > 8 page unit being free when only 1% of memory is free is (1/100)**8 =
> > 1/(10**16).
>
> I thought that, then I tested & measured, and it simply isn't true.
> Your mathematical model is wrong.
Yes, a simple thought experiment show this. Suppose we start with an intial
state of every second 0 order page allocated. Now, the next 0 order
allocation must coalesce to a 1 order unit but the next allocate will come
from a half-allocated allocated unit. If we continue randomly in this way,
allocating one page and freeing one, we will eventually arrive at a state
where half the pages are in 1 order units and the other half are fully
allocated.
So, the fragmentation is far from uniformly random. This is going to require
deeper analysis. IMO, it's worth putting in the effort to get a handle on
this.
--
Daniel
next prev parent reply other threads:[~2001-09-07 21:49 UTC|newest]
Thread overview: 72+ messages / expand[flat|nested] mbox.gz Atom feed top
2001-08-28 3:36 page_launder() on 2.4.9/10 issue Marcelo Tosatti
2001-08-28 18:07 ` Daniel Phillips
2001-08-28 18:17 ` Linus Torvalds
2001-08-30 1:36 ` Daniel Phillips
2001-09-03 14:57 ` Marcelo Tosatti
2001-09-04 15:26 ` Jan Harkes
2001-09-04 15:24 ` Marcelo Tosatti
2001-09-04 17:14 ` Jan Harkes
2001-09-04 15:53 ` Marcelo Tosatti
2001-09-04 19:33 ` Daniel Phillips
2001-09-06 11:52 ` Rik van Riel
2001-09-06 12:31 ` Daniel Phillips
2001-09-06 12:32 ` Rik van Riel
2001-09-06 12:53 ` Daniel Phillips
2001-09-06 13:03 ` Rik van Riel
2001-09-06 13:18 ` Kurt Garloff
2001-09-06 13:23 ` Rik van Riel
2001-09-06 13:28 ` Alan Cox
2001-09-06 13:29 ` Rik van Riel
2001-09-06 16:45 ` Daniel Phillips
2001-09-06 16:57 ` Rik van Riel
2001-09-06 17:22 ` Daniel Phillips
2001-09-06 19:25 ` Rik van Riel
2001-09-06 19:45 ` Daniel Phillips
2001-09-06 19:52 ` Rik van Riel
2001-09-07 0:32 ` Kurt Garloff
2001-09-06 19:53 ` Mike Fedyk
2001-09-06 17:35 ` Mike Fedyk
2001-09-06 13:10 ` Stephan von Krawczynski
2001-09-06 13:23 ` Alex Bligh - linux-kernel
2001-09-06 13:54 ` M. Edward Borasky
2001-09-06 14:39 ` Alan Cox
2001-09-06 16:20 ` Victor Yodaiken
2001-09-06 17:33 ` Daniel Phillips
2001-09-06 13:42 ` Stephan von Krawczynski
2001-09-06 14:01 ` Alex Bligh - linux-kernel
2001-09-06 14:39 ` Stephan von Krawczynski
2001-09-06 15:02 ` Alex Bligh - linux-kernel
2001-09-06 15:07 ` Rik van Riel
[not found] ` <Pine.LNX.4.33L.0109061206020.31200-100000@imladris.rielhome.con ectiva>
2001-09-06 15:16 ` Alex Bligh - linux-kernel
2001-09-06 15:10 ` Stephan von Krawczynski
2001-09-06 15:18 ` Alex Bligh - linux-kernel
2001-09-06 17:34 ` Daniel Phillips
2001-09-06 17:32 ` Alex Bligh - linux-kernel
2001-09-06 17:51 ` Daniel Phillips
2001-09-06 21:01 ` [RFC] Defragmentation proposal: preventative maintenance and cleanup [LONG] Alex Bligh - linux-kernel
2001-09-07 6:35 ` Daniel Phillips
2001-09-07 8:58 ` Alex Bligh - linux-kernel
2001-09-07 9:15 ` Alex Bligh - linux-kernel
2001-09-07 9:28 ` Alex Bligh - linux-kernel
2001-09-07 21:38 ` Daniel Phillips
2001-09-07 21:56 ` Daniel Phillips [this message]
2001-09-07 12:30 ` page_launder() on 2.4.9/10 issue Stephan von Krawczynski
2001-09-04 16:27 ` Rik van Riel
2001-09-04 17:13 ` Jan Harkes
2001-09-04 15:56 ` Marcelo Tosatti
2001-09-04 17:54 ` Jan Harkes
2001-09-04 16:37 ` Marcelo Tosatti
2001-09-04 18:49 ` Alan Cox
2001-09-04 19:39 ` Jan Harkes
2001-09-04 20:25 ` Alan Cox
2001-09-06 11:23 ` Rik van Riel
2001-09-04 19:54 ` Andrea Arcangeli
2001-09-04 18:36 ` Marcelo Tosatti
2001-09-04 20:10 ` Daniel Phillips
2001-09-04 22:04 ` Andrea Arcangeli
2001-09-05 2:41 ` Daniel Phillips
2001-09-06 11:18 ` Rik van Riel
2001-09-04 17:35 ` Daniel Phillips
2001-09-04 20:43 ` Jan Harkes
2001-09-06 11:21 ` Rik van Riel
[not found] <20010907062851Z16136-26184+30@humbolt.nl.linux.org.suse.lists.linux.kernel>
[not found] ` <1426827386.999856726@[169.254.198.40].suse.lists.linux.kernel>
2001-09-07 9:34 ` [RFC] Defragmentation proposal: preventative maintenance and cleanup [LONG] Andi Kleen
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20010907214921Z16337-26183+212@humbolt.nl.linux.org \
--to=phillips@bonn-fries.net \
--cc=linux-kernel@alex.org.uk \
--cc=linux-kernel@vger.kernel.org \
--cc=riel@conectiva.com.br \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).