Re: New patch for Linux

Re: New patch for Linux

[Yair Wiseman]

[-- Attachment #1: Type: text/plain, Size: 3625 bytes --]

Dear Peter,

Thanks for your quick response. Our patch is indeed an extension of the LRU-token approach. I am a friend of Song
Jiang who wrote the LRU-token and continued his approach; however unlike his approach we suggest to block some
processes on thrashing. Blocking some processes because of an IO as you mentioned in your email can sometimes help,
but sometimes cannot help, so it is not enough. LRU-token approach works on multi-processors, so I do not see a major
difference why our approach cannot work. The change in the scheduler will take effect just when the calculation is
done. The working set is calculated by the resident size (RSS) of a process which is quite close to the working set if
the system is on memory pressure.

I am attaching again my paper.

Thanks again for your comments,

-Yair.
-------------------------------------------------------------------------
Dr. Yair Wiseman, Ph.D.
Computer Science Department
Bar-Ilan University
Ramat-Gan 52900
Israel
Tel: 972-3-5317015
Fax: 972-3-7384056
http://www.cs.biu.ac.il/~wiseman

>From the keyboard of Peter Zijlstra
> On Thu, 2009-08-06 at 11:14 +0300, Yair Wiseman wrote:
>> Dear Peter Zijlstra,
>>
>> We would like to suggest our patch to Linux scheduler. I am attaching
>> our paper about it. Can you please consider it?
>
> You seem to have based your work on 2.6.9 which is completely
> unrepresentative for a current (2.6.30) Linux kernel. Both the scheduler
> and the page reclaim infrastructure have undergone significant rewrites
> since.
>
> The scheduler is now a Proportional Fair Scheduler and the Page Reclaim
> bits have been split into two, using SEQ for anonymous pages and the old
> double CLOCK like LRU for file pages.
>
> Still, non of that seems to invalidate your proposal in the conceptual
> way.
>
> However, your proposal seems flawed in a significant way, it assumes a
> global state -- being able to bin-pack all processes' working set size
> into memory.
>
> [ with the minor nit that its terribly hard to determine the working set
> size for a process ]
>
> Linux needs to support large CC-NUMA machines (the currently largest
> know single system image machine to run Linux had 4096 CPUs), which
> renders any such scheme pointless.
>
> [ I might have mis-understood or missed a detail, for I only read the
> paper in a brief way -- please correct me when I seem to mis-represent
> your ideas ]
>
>
> Now work on anti-thrashing is interesting, and I do encourage you to
> continue. However I would urge you to look at ways that scale per-cpu or
> per-node. That is, look at distributed algorithms that work on local
> state but converge to this global goal without the severe
> synchronization costs.
>
>
> Personally I don't think we need to modify the task scheduler, since
> processes blocked on (swap) IO aren't runnable, so by managing the
> contention on the IO devices and simply not serving pages for some
> you'll end up with the same result.
>
> This could be an extension of the LRU-token approach.
>
> Note that this doesn't restrict itself to swap but can also be regular
> file based paging which is not always considered but can be the
> predominant trashing cause for many workloads (databases).
>
>
> I thank you for sharing your research, and maybe we can continue this
> discussion. If you are indeed interested in further communication with
> me, or I would urge, the Linux community at large, I would recommend
> including the linux-mm <linux-mm@kvack.org> (Memory Management) mailing
> list, Rik van Riel <riel@redhat.com> and Johannes Weiner
> <hannes@cmpxchg.org>.
>
> Kind regards,
>
> Peter
>

[-- Attachment #2: computer2006.pdf --]
[-- Type: application/pdf, Size: 187334 bytes --]

Re: New patch for Linux

[Rik van Riel]

Yair Wiseman wrote:

> Thanks for your quick response. Our patch is indeed an extension
 > of the LRU-token approach.

The paper looks very promising, but I have a few questions.

First, why is a 1 second medium timeslice enough when processes
on modern systems are often hundreds of megabytes in size?

In one second, a disk can handle about 100 seeks, which corresponds
to 100 truly random swapin IOs. I see that a lot of the testing in
your paper was done with smaller processes on smaller memory systems,
which makes me very curious about how your algorithm will perform on
systems with larger processes.

Second, where can we get the patch? :)

The URL in the first page of the paper appears to no longer exist.

-- 
All rights reversed.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: New patch for Linux

[Yair Wiseman]

Dear Rik van Riel,

Thanks for your comments. You indeed have a point. We used 128MB of RAM which is VERY small, so one second would be
enough; therefore I agree that your remark about the small quantum is correct - a common nowadays RAM is larger and
the quantum should be longer.

The first author of the paper was an MSc student of me and the code was at his home-page, but when he left the
university his directory was removed. We tried to find his code and we found just the code of 2.4.20. I put it at:
http://u.cs.biu.ac.il/~wiseman/moses.html

Thanks for considering our patch,

-Yair.
-------------------------------------------------------------------------
Dr. Yair Wiseman, Ph.D.
Computer Science Department
Bar-Ilan University
Ramat-Gan 52900
Israel
Tel: 972-3-5317015
Fax: 972-3-7384056
http://www.cs.biu.ac.il/~wiseman

>From the keyboard of Rik van Riel
> Yair Wiseman wrote:
>
>> Thanks for your quick response. Our patch is indeed an extension
>  > of the LRU-token approach.
>
> The paper looks very promising, but I have a few questions.
>
> First, why is a 1 second medium timeslice enough when processes
> on modern systems are often hundreds of megabytes in size?
>
> In one second, a disk can handle about 100 seeks, which corresponds
> to 100 truly random swapin IOs. I see that a lot of the testing in
> your paper was done with smaller processes on smaller memory systems,
> which makes me very curious about how your algorithm will perform on
> systems with larger processes.
>
> Second, where can we get the patch? :)
>
> The URL in the first page of the paper appears to no longer exist.
>
> --
> All rights reversed.
>


--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: New patch for Linux

[Rik van Riel]

Yair Wiseman wrote:
> We tried to find his code and we found just the code of 2.4.20. I put it at:
> http://u.cs.biu.ac.il/~wiseman/moses.html
> 
> Thanks for considering our patch,

Ummm no.  It's for an ancient version of Linux and not even a
patch.  There really isn't a whole lot to consider, beyond an
idea - which you admitted may not even work well on systems
with larger amounts of memory.

-- 
All rights reversed.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: New patch for Linux

[Yair Wiseman]

It will work for larger amounts of memory. We just have to choose a longer time slice. I will try to find a newer
version, but I do not see the difference in this case. We just suggest to replace the LRU-token approach.

-Yair.
-------------------------------------------------------------------------
Dr. Yair Wiseman, Ph.D.
Computer Science Department
Bar-Ilan University
Ramat-Gan 52900
Israel
Tel: 972-3-5317015
Fax: 972-3-7384056
http://www.cs.biu.ac.il/~wiseman

>From the keyboard of Rik van Riel
> Yair Wiseman wrote:
>> We tried to find his code and we found just the code of 2.4.20. I put it at:
>> http://u.cs.biu.ac.il/~wiseman/moses.html
>>
>> Thanks for considering our patch,
>
> Ummm no.  It's for an ancient version of Linux and not even a
> patch.  There really isn't a whole lot to consider, beyond an
> idea - which you admitted may not even work well on systems
> with larger amounts of memory.
>
> --
> All rights reversed.
>


--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: New patch for Linux

[Rik van Riel]

Yair Wiseman wrote:
> It will work for larger amounts of memory. We just have to choose a longer time slice.

Sounds simple, but in practice you will run into the fact that users
don't really mind a 1 second latency during thrashing, but the 1 minute
(or more) latencies that may be required for this scheme to scale to
very large memory systems may be totally unacceptable.

> I will try to find a newer
> version, but I do not see the difference in this case.
 > We just suggest to replace the LRU-token approach.

I have no problem with replacing the LRU-token, if we can find
something that is shown to work better.  BSD style process
suspension has been tried many times on Linux and it never seemed
to work right.

Maybe your approach can be made to automatically work right on
machines of all memory sizes, but it would be good to demonstrate
that before committing to such a change.

-- 
All rights reversed.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: New patch for Linux

[Yair Wiseman]

We discussed interactive processes in sections 4.5 and 5.5 of our paper and show that it works well, so there is no
problem to have even slice time of one minute.

-Yair.
-------------------------------------------------------------------------
Dr. Yair Wiseman, Ph.D.
Computer Science Department
Bar-Ilan University
Ramat-Gan 52900
Israel
Tel: 972-3-5317015
Fax: 972-3-7384056
http://www.cs.biu.ac.il/~wiseman


>From the keyboard of Rik van Riel
> Yair Wiseman wrote:
>> It will work for larger amounts of memory. We just have to choose a longer time slice.
>
> Sounds simple, but in practice you will run into the fact that users
> don't really mind a 1 second latency during thrashing, but the 1 minute
> (or more) latencies that may be required for this scheme to scale to
> very large memory systems may be totally unacceptable.
>
>> I will try to find a newer
>> version, but I do not see the difference in this case.
>  > We just suggest to replace the LRU-token approach.
>
> I have no problem with replacing the LRU-token, if we can find
> something that is shown to work better.  BSD style process
> suspension has been tried many times on Linux and it never seemed
> to work right.
>
> Maybe your approach can be made to automatically work right on
> machines of all memory sizes, but it would be good to demonstrate
> that before committing to such a change.
>
> --
> All rights reversed.
>


--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: New patch for Linux

[Rik van Riel]

Yair Wiseman wrote:
> We discussed interactive processes in sections 4.5 and 5.5 of our paper and show that it works well, so there is no
> problem to have even slice time of one minute.

Makes sense.  Do you, or any of your students or colleagues,
have plans to forward port the code to the current upstream
kernel?

-- 
All rights reversed.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

FW: New patch for Linux

[Yair Wiseman]

Hi Moses,

How are you doing?

I had a discussion with Rik van Riel from Linux about the patch you had written for your MSc thesis. Rik would be
happy to have a more update version than we have at:
http://u.cs.biu.ac.il/~wiseman/moses.html

Can you please send us such a version?

Thanks,

-Yair.
-------------------------------------------------------------------------
Dr. Yair Wiseman, Ph.D.
Computer Science Department
Bar-Ilan University
Ramat-Gan 52900
Israel
Tel: 972-3-5317015
Fax: 972-3-7384056
http://www.cs.biu.ac.il/~wiseman

>From the keyboard of Rik van Riel
> Yair Wiseman wrote:
>> We discussed interactive processes in sections 4.5 and 5.5 of our paper and show that it works well, so there is no
>> problem to have even slice time of one minute.
>
> Makes sense.  Do you, or any of your students or colleagues,
> have plans to forward port the code to the current upstream
> kernel?
>
> --
> All rights reversed.
>


--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>