Walt Mankowski on 18 Apr 2016 14:15:52 -0700


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: [PLUG] >32K concurrent processes


Interesting. I hadn't heard that they'd changed the scheduling
algorithm. Wikipedia has a nice summary:

https://en.wikipedia.org/wiki/Completely_Fair_Scheduler

And here's what it has to say about the Deadline Scheduler:

https://en.wikipedia.org/wiki/Deadline_scheduler

Based on my reading of that, the CFS is responsible for scheduling
processes, while the DS schedules I/O.

To answer Rich's question, O(1) only refers to the time to choose the
next process. It's not constant time to add new processes to the run
queue. The overhead increases as the number of processes
increases. Even though it seems like it should be a simple round
robin, it's not. The processes are kept in a red-black tree that has
to be updated for every process switch.



On Mon, Apr 18, 2016 at 04:58:39PM -0400, Keith C. Perry wrote:
> For what its worth...
> 
> I see a number of mentioned about the O(1) scheduler.  Unless I'm missing something that replaced in the late 2.6 kernels with the CFS scheduler and later in 3.x's the Deadline scheduler, which is now the default (at least it is on Kubuntu 14.04 LTS- looking at Kernel 4.4.4 source that is still takes precedence if available).
> 
> ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ 
> Keith C. Perry, MS E.E. 
> Owner, DAO Technologies LLC 
> (O) +1.215.525.4165 x2033 
> (M) +1.215.432.5167 
> www.daotechnologies.com
> 
> ----- Original Message -----
> From: "Rich Freeman" <r-plug@thefreemanclan.net>
> To: "Philadelphia Linux User's Group Discussion List" <plug@lists.phillylinux.org>
> Sent: Monday, April 18, 2016 4:42:06 PM
> Subject: Re: [PLUG] >32K concurrent processes
> 
> On Mon, Apr 18, 2016 at 3:32 PM, Walt Mankowski <waltman@pobox.com> wrote:
> > Even with an O(1) scheduler I (and it seems many of the other posters
> > in this thread) would be concerned about performance and throughput
> > with that many processes. It seems to me that it's possible your
> > kernel could be spending a significant amount of time scheduling
> > processes.
> >
> 
> Why would a kernel spend any more time switching between 32,000
> processes than 2 processes?
> 
> Suppose I have one CPU core.  Suppose I have two processes that each
> have an infinite demand for cpu (just have them run loops or
> something).
> 
> The kernel is going to run one process for a timeslice.  Then it will
> task-switch to the other for a timeslice.  Then it will switch back,
> and so on.
> 
> If you have 32,000 processes all with the same demand what the kernel
> does is the same.  It runs each one in turn for a slice, then it
> switches.
> 
> In a single second you'll have the exact same number of task switches
> either way.  Granted, in one scenario it is back and forth between two
> processes, and the other it is moving around 32k of them round-robin.
> It might not get to all 32k processes in a second either, but it will
> still switch tasks the same number of times.  Since the scheduler is
> O(1) it will spend the same amount of time doing those switches as
> well.
> 
> This all assumes that memory use/etc remains constant, etc.
> 
> -- 
> Rich
> ___________________________________________________________________________
> Philadelphia Linux Users Group         --        http://www.phillylinux.org
> Announcements - http://lists.phillylinux.org/mailman/listinfo/plug-announce
> General Discussion  --   http://lists.phillylinux.org/mailman/listinfo/plug
> ___________________________________________________________________________
> Philadelphia Linux Users Group         --        http://www.phillylinux.org
> Announcements - http://lists.phillylinux.org/mailman/listinfo/plug-announce
> General Discussion  --   http://lists.phillylinux.org/mailman/listinfo/plug

Attachment: signature.asc
Description: PGP signature

___________________________________________________________________________
Philadelphia Linux Users Group         --        http://www.phillylinux.org
Announcements - http://lists.phillylinux.org/mailman/listinfo/plug-announce
General Discussion  --   http://lists.phillylinux.org/mailman/listinfo/plug