Re: Comments on the KSE option

Matthew Dillon wrote:
>: I think the notion of fairness is orthogonal to M:N threading.  M:N is about 
>: efficiently representing user threading to kernel space, as well as avoiding 
>: kernel involvement in user context switches when not needed.  Fairness is 
>: about how the kernel allocates time slices to user processes/threads. 
>: Fairness can be implemented for both 1:1 and M:N, with the primary differences 
>: being in bookkeeping.
> 
>     Yes, this is precisely what I mean.  Very well said.

Agreed.

>     What we are talking about here is primarily algorithmic complexity
>     and physical resource limitations (e.g. like kernel memory).  Having
>     the kernel scheduler only deal with (N) threads, where N is limited by
>     the number of physical cpus, is a far easier problem for the kernel
>     to solve in all respects then having the kernel deal with (M*N)
>     individual threads.

Yes.  A userspace program would like to assume that it can have as many 
parallel threads of execution as it wants to have, but the kernel only needs 
to schedule N of them at a time from the set of runnable tasks.

Most of the debate comes from whether userland threads are counted in M, or 
only userland processes.

>     I personally see no reason why a program
>     couldn't have 10,000 threads, or 100,000 threads, or a million threads,
>     but the kernel is the wrong place to try to manage them if your system
>     only has N cpus (N=2,4,8,16,32, etc).  You have to ask yourself, what
>     exactly is the kernel accomplishing trying to manage all those threads
>     for a single application when it only has N cpu contexts to work with
>     anyhow?

Well, it is solving the same problem that the kernel needs to solve when 
someone sets up a web hosting machine with a hundred jails (or a thousand), 
times anywhere from ten to 200+ preforked httpd processes.

>  The answer is: The kernel should only have to worry about the
>  N cpu contexts and kernel memory reosurces for those contexts.

Yes.  Of course, counting N is becoming more complicated with Hyperthreading 
and multi-CPU cores...and expected values of N are becoming much larger.

>     (2) Just because the POSIX scheduler implements all sorts of different
>     scopes and priority schemes says NOTHING AT ALL about how programs
>     operating under such a scheduler should be apportioned cpu relative
>     to OTHER PROGRAMS WHICH ARE INDEPENDANTLY RUNNING ON THE SYSTEM.

At one point, Mach attempted to solve this by putting all of the 
(system-scope) threads spawned by a particular user into bins (called 
thread_groups, task_group?, IIRC), creating a list, and putting each runnable 
kernel thread into a separate individual bin, and then allocating each of the 
N available units of CPU execution one at a time onto a bin by selecting the 
(non-blocked) thread in that bin with the highest priority.

One would attempt to sort this list by priority, where the priority of a bin 
initially is the priority of the most important runnable thread contained in 
the thread_group; by putting high-priority bins first (ie, kernel ISRs after 
an interrupt, so as to minimize latency), and then tasks owned by the 
superuser, or user tasks have been granted the privilege to create their own 
thread_group to run at higher priority (ie, "soft realtime"), and then normal 
user processes, and then "idle taskgroups", which get placed behind everything 
else and only run on a CPU if there is no runnable thread anywhere.

Once a bin has been granted a unit of CPU time, it is removed from the head of 
the list; if this particular bin still contains runnable threads it's priority 
is reduced temporarily (if it is not privileged like an ISR or a realtime 
task) so that it will appended at or towards the end of the list.

>  POSIX
>     is an abstraction (or virtualization out of available resources),
>     just like everything else.  If you try to treat it as a hard requirement
>     the only result will be a broken system that might happily run everything
>     else into the ground and stop allowing root ssh logins in order to 
>     accomodate a badly written POSIX program.  There are many third party
>     applications that set POSIX priorities, in particular realtime
>     priorities, that I'd rather they not actually use.

OK.  So what administrative interface would you like to use to restrict this?

Or, did you really mean that you don't believe the kernel should even have the 
capability to honor realtime priority?

Does this still apply if the user is your grandparents and the realtime task 
is a DVD viewer?  Go ahead.  Explain to grandma that you'd prefer her movie to 
skip so you can run SSHd reliably.  :-)

I've always thought that Unix should be configured with a safety to avoid 
footshooting, but if the administrator flips the safety, aims straight down, 
and fires, that they (or privileged userland processes which have asked for 
the gun and flipped the safety to "realtime") are allowed to shoot themselves.

>     All a program can ever really do when requesting POSIX scheduling 
>     resources is compete against itself.  It is the system operator, at a
>     higher level, that must control how those resources compete with 
>     other programs.  That should be clear to everyone it is so obvious.
> 
>     It is a whole lot easier for the kernel to give the system operator
>     this power if the kernel scheduler does not have to juggle thousands
>     of threads.  It is very easy to write a scheduler for threaded
>     applications when the most you have to deal with is N threads
>     (N=ncpus) per application.

Whether a process can create additional KSEs (ie, can create threads in the 
system scope) or whether it is restricted to using only process scope should 
be an administrative tunable, just as whether or not realtime priority is allowed.

Given the timesharing orientation that many people find desirable about Unix, 
it seems entirely reasonable to ship the system with threads defaulting to 
process scope and limited so that realtime is not enabled by default...

>     Now lets consider programs which fork() instead of thread.  The argument
>     that threading is equivalent to forking from a management standpoint
>     is just plain silly.  From a design standpoint, programmers are very
>     well aware of the resources required to fork(), and consequently
>     per-fork tasks are generally much, MUCH better understood by system
>     operators in the management context then per-thread tasks.  per-thread
>     tasks tend to be opaque...  you never know how a threaded program might
>     be written.  You just cannot treat the two as equivalent or even close
>     to equivalent.

...However, if system scope is not forbidden, the kernel ought to be optimized 
to handle threaded Apache-2 just the same way it treats the classic preforked 
child process model.  The kernel ought to be willing to run separate threads 
within an individual process like a threaded Apache or a threaded Java at the 
same time on separate CPUs.

-- 
-Chuck