Re: pageable page tables

Re: pageable page tables

[Rik van Riel]

On Wed, 10 Dec 1997, Pavel Machek wrote:

> > > > > Simple task might be 'memory priorities'. Something like priorities
> > > > > for scheduler but for memory. (I tried to implement them, and they
> > > > > gave <1% performance gain ;-), but I have interface to set such
> > > > > parameter if you want to play).
> > > > 
> > > > sounds rather good... (swapout-priorities??)
> > > 
> > > But proved to be pretty ineffective. I came to this idea when I
> > > realized that to cook machine, running 100 processes will not hurt too
> > > much. But running 10 processes, 50 megabytes each will cook almost
> > > anything...

... this is where things started falling into place :)

> > I think it will be more of a scheduling issue...
> > Suspending low-priority, background jobs for a minute
> > (in turn) will make swapping / running possible again
> > (even without changes to the swapping code).
> > 
> > To do this, we could create a new scheduling class: SCHED_BG
> > Processes in this class are run:
> > - one at a time (possibly two??)
> > - for LONG slices, getting longer after each slice (a'la CTSS)
> 
> What is CTSS?

Central (?) Time Sharing System... From somewhere in
the '60s... It had the following properties:
- no VM, only one process could be loaded at the same time
- if you want to switch to another process, you'd have to
  swap the current one out and the other one in 
  --> extremely slow task switching
- it was a multi-user system
- with some people using it for _long_ computations
- so they came up with the following solution:
  - a process starts with a timeslice of length 1
  - every following time, the length of the slice get's
    doubled (and the process get's scheduled less often)
  - if the process is interactive (ie. keyboard input)
    the process is moved to the highest (short ts) class

> > - so only one of them has to be in memory...
> > - at a lower priority than interactive jobs.
> > - CPU time and memory used by these processes aren't charged
> >   when user quota's are inforced... this should encourage users
> >   to run large jobs (and even medium compiles) as SCHED_BG jobs
> 
> Not sure this is good idea.

Many systems use something like NQS for large jobs, but
this would be a nice scheme for 'medium' jobs. The
machine at our school, for instance, has a 5minute CPU
limit (per process)...
Doing a large compile (glibc :-) on such a machine would
not only fail, but it would also annoy other users. This
SCHED_BG scheme doesn't really load the rest of the system...
> 
> > about the time-slicing:
> > - the SCHED_BG process is run when no interactive process is
> >   runnable
> > - it starts with a 1 second slice, followed by 2, 4, 8, 16, 
> >   and longer timeslices (in order to reduce swapping).
> > - these slices are only interrupted by:
> >   - an interactive process wanting the CPU
> >   - blocking on a resource
>       ~~~~~~~~~~~~~~~~~~~~~~
> Bad idea. If that jobs read disks (sometime), they will lose their
> (extremely long) timeslice. (BTW page fault requiring swap-in is also
> blocking on a resource. 

Uh, that's not what I meant to say... If it blocks on a
resource, and the wainting time is too high (and there's
enough memory, and idle time) you could wake up another
process... Of course the slice won't end...

> > - the SCHED_BG processes can run together/in parrallel when
> >   available memory is above a certain threshold (then they
> >   can receive 'normal' timeslices)
> > 
> > And when free memory stays below free_pages_low for more
> > than 5 seconds, we can choose to have even normal processes
> > queued for some time (in order to reduce paging)

someone else have an opinion on this?

Rik.
+-----------------------------+------------------------------+
| For Linux mm-patches, go to | "I'm busy managing memory.." |
| my homepage (via LinuxHQ).  | H.H.vanRiel@fys.ruu.nl       |
| ...submissions welcome...   | http://www.fys.ruu.nl/~riel/ |
+-----------------------------+------------------------------+

Re: pageable page tables

[Pavel Machek]

Hi!

> > Not sure this is good idea.
> 
> Many systems use something like NQS for large jobs, but
> this would be a nice scheme for 'medium' jobs. The
> machine at our school, for instance, has a 5minute CPU
> limit (per process)...
> Doing a large compile (glibc :-) on such a machine would
> not only fail, but it would also annoy other users. This
> SCHED_BG scheme doesn't really load the rest of the system...

No, it would not fail, as no single process eats 5 minutes. And even
with SCHED_BG you would load rest of the system: you would load disk
subsystem. Often, disk subsystem is more important than CPU.

> > > And when free memory stays below free_pages_low for more
> > > than 5 seconds, we can choose to have even normal processes
> > > queued for some time (in order to reduce paging)
> 
> someone else have an opinion on this?

Too many heuristics?

								Pavel
-- 
I'm really pavel@atrey.karlin.mff.cuni.cz. 	   Pavel
Look at http://atrey.karlin.mff.cuni.cz/~pavel/ ;-).

Re: pageable page tables

[Pavel Machek]

Hi!

> > No, it would not fail, as no single process eats 5 minutes. And even
> > with SCHED_BG you would load rest of the system: you would load disk
> > subsystem. Often, disk subsystem is more important than CPU.
> 
> This is exactly the place where SCHED_BG works. By
> suspending all but one of the jobs, a heavy multi-user
> machine only has to worry about the interactive jobs,
> and the disk I/O of _one_ SCHED_BG job...

Disk I/O of one job is just enough to make machine pretty annoying for
interactive use. Try make dep on background. (And: I assume that
usualy there will be <=1 SCHED_BG job.)

								Pavel

-- 
I'm really pavel@atrey.karlin.mff.cuni.cz. 	   Pavel
Look at http://atrey.karlin.mff.cuni.cz/~pavel/ ;-).

Re: SCHED_BG

[Rik van Riel]

On Thu, 18 Dec 1997, Pavel Machek wrote:

> > > No, it would not fail, as no single process eats 5 minutes. And even
> > > with SCHED_BG you would load rest of the system: you would load disk
> > > subsystem. Often, disk subsystem is more important than CPU.
> > 
> > This is exactly the place where SCHED_BG works. By
> > suspending all but one of the jobs, a heavy multi-user
> > machine only has to worry about the interactive jobs,
> > and the disk I/O of _one_ SCHED_BG job...
> 
> Disk I/O of one job is just enough to make machine pretty annoying for
> interactive use. Try make dep on background. (And: I assume that
> usualy there will be <=1 SCHED_BG job.)

Not on a multi-user machine...

And: on my machine (3 disks) I can run several makes before
it becomes annoying (about 5). That's quite good considering
the fact that I only have 24megs of RAM (just 4 more than you,
Pavel)

And when I get the other disks back (one broke, so I get two
smaller ones in return:), my system will run even slicker...
It's all a matter of strategic placement of your files...

Maybe you should also read the Multiple-Disk-HOWTO or 
Partioning-HOWTO, or whatever it's called this week :)

My mmap-age patch will also help quite a bit...

Rik.
+-----------------------------+------------------------------+
| For Linux mm-patches, go to | "I'm busy managing memory.." |
| my homepage (via LinuxHQ).  | H.H.vanRiel@fys.ruu.nl       |
| ...submissions welcome...   | http://www.fys.ruu.nl/~riel/ |
+-----------------------------+------------------------------+

Re: pageable page tables

[Benjamin LaHaise]

---Forwarded---
Date: Thu, 18 Dec 1997 00:02:43 +0100 (MET)
From: Rik van Riel <H.H.vanRiel@fys.ruu.nl>
X-Sender: riel@mirkwood.dummy.home
Reply-To: H.H.vanRiel@fys.ruu.nl
To: Pavel Machek <pavel@Elf.mj.gts.cz>
cc: linux-mm@kvack.org
Subject: Re: pageable page tables
In-Reply-To: <19971217221425.30735@Elf.mj.gts.cz>
Message-ID: <Pine.LNX.3.91.971218000000.887A-100000@mirkwood.dummy.home>
Approved: ObHack@localhost
Organization: none
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII

On Wed, 17 Dec 1997, Pavel Machek wrote:

> No, it would not fail, as no single process eats 5 minutes. And even
> with SCHED_BG you would load rest of the system: you would load disk
> subsystem. Often, disk subsystem is more important than CPU.

This is exactly the place where SCHED_BG works. By
suspending all but one of the jobs, a heavy multi-user
machine only has to worry about the interactive jobs,
and the disk I/O of _one_ SCHED_BG job...

> > > > And when free memory stays below free_pages_low for more
> > > > than 5 seconds, we can choose to have even normal processes
> > > > queued for some time (in order to reduce paging)
> 
> Too many heuristics?

That doesn't really matter if they aren't used very
often... We only have to check the free memory from
swap_tick (we already do) and call a special routine
for suspending / waking up the SCHED_BG jobs

Rik.
+-----------------------------+------------------------------+
| For Linux mm-patches, go to | "I'm busy managing memory.." |
| my homepage (via LinuxHQ).  | H.H.vanRiel@fys.ruu.nl       |
| ...submissions welcome...   | http://www.fys.ruu.nl/~riel/ |
+-----------------------------+------------------------------+

Re: pageable page tables

[Rik van Riel]

On Tue, 9 Dec 1997, Pavel Machek wrote:

> > > Simple task might be 'memory priorities'. Something like priorities
> > > for scheduler but for memory. (I tried to implement them, and they
> > > gave <1% performance gain ;-), but I have interface to set such
> > > parameter if you want to play).
> > 
> > sounds rather good... (swapout-priorities??)
> 
> But proved to be pretty ineffective. I came to this idea when I
> realized that to cook machine, running 100 processes will not hurt too
> much. But running 10 processes, 50 megabytes each will cook almost
> anything...

what about:

if (page->age - p->mem_priority)
	exit 0 / goto next;
else {
	get_rid_of(page);
	and_dont_show_your_face_again_for_some_time(page);
}

effectively putting the program to sleep if:
- this page faults again soon
- memory is still tight

hmm, just an idea...

Rik.

--
Send Linux memory-management wishes to me: I'm currently looking
for something to hack...

Re: pageable page tables

[Rik van Riel]

On Tue, 9 Dec 1997, Pavel Machek wrote:

> Hi!
> 
> > > Simple task might be 'memory priorities'. Something like priorities
> > > for scheduler but for memory. (I tried to implement them, and they
> > > gave <1% performance gain ;-), but I have interface to set such
> > > parameter if you want to play).
> > 
> > sounds rather good... (swapout-priorities??)
> 
> But proved to be pretty ineffective. I came to this idea when I
> realized that to cook machine, running 100 processes will not hurt too
> much. But running 10 processes, 50 megabytes each will cook almost
> anything...

I think it will be more of a scheduling issue...
Suspending low-priority, background jobs for a minute
(in turn) will make swapping / running possible again
(even without changes to the swapping code).

To do this, we could create a new scheduling class: SCHED_BG
Processes in this class are run:
- one at a time (possibly two??)
- for LONG slices, getting longer after each slice (a'la CTSS)
- so only one of them has to be in memory...
- at a lower priority than interactive jobs.
- CPU time and memory used by these processes aren't charged
  when user quota's are inforced... this should encourage users
  to run large jobs (and even medium compiles) as SCHED_BG jobs

about the time-slicing:
- the SCHED_BG process is run when no interactive process is
  runnable
- it starts with a 1 second slice, followed by 2, 4, 8, 16, 
  and longer timeslices (in order to reduce swapping).
- these slices are only interrupted by:
  - an interactive process wanting the CPU
  - blocking on a resource
  - another SCHED_BG process is woken up
- after the timeslice is over, the process is put to sleep
  for a duration of: last_timeslice * nr_background_processes
- when no background process is running/runnable, the next
  SCHED_BG process to be woken up is made runnable
- the SCHED_BG processes can run together/in parrallel when
  available memory is above a certain threshold (then they
  can receive 'normal' timeslices)

And when free memory stays below free_pages_low for more
than 5 seconds, we can choose to have even normal processes
queued for some time (in order to reduce paging)

Where Do You Want Us To Take You Today ? (tm)

Rik.

--
Send Linux memory-management wishes to me: I'm currently looking
for something to hack...

Re: pageable page tables

[Chris Evans]

On Thu, 27 Nov 1997, Alan Cox wrote:

> > Then we would also need per-user accounting...
> > All-in-all however it's a very good idea.
> > 
> > (linux-kernel guys, would this break compatibility/POSIX or
> > whatever thing)
> 
> No it wouldnt.. There - something for you to hack 8)

Perhaps more importantly, _before_ per user stuff is defined then
implemented, the existing RLIMIT_* should be verified for correctness, and
checks made that these limits can't be circumvented.

In particular, RLIMIT_RSS is not implemented. Setting such a limit,
however, fails silently.

Chris

Re: pageable page tables

[Alan Cox]

> Then we would also need per-user accounting...
> All-in-all however it's a very good idea.
> 
> (linux-kernel guys, would this break compatibility/POSIX or
> whatever thing)

No it wouldnt.. There - something for you to hack 8)

Re: pageable page tables

[Rik van Riel]

On Wed, 26 Nov 1997, Joel Gallun wrote:

> Wouldn't it be better to charge this against their ulimit? I'd rather not
> have the overhead of pageable page tables on a machine with no untrusted
> shell users (which I suspect is the majority of linux systems).

Then we would also need per-user accounting...
All-in-all however it's a very good idea.

(linux-kernel guys, would this break compatibility/POSIX or
whatever thing)

Rik.

ps: f-ups to linux-mm only.
----------
Send Linux memory-management wishes to me: I'm currently looking
for something to hack...