Linux Kernel Scheduling Addition Notification : Hybrid Sleepers and Unfair scheduling

Linux Kernel Scheduling Addition Notification : Hybrid Sleepers and Unfair scheduling

[Mitchell Erblich]

Please note that this proposal is from this engineer and not from the company he works for.

This SHOULD also fulfills any legal notification of work done, but not submitted to the Linux Kernel.


Transfer of Information  : Notification & Proposal of Feasibility to Support System V Release 4 Defacto Standard Scheduling Extensions, etc within Linux
——————————-


SCHED_IA
	Over 10 years ago, System V Release 4 was enhanced with additional features by Sun Microsystems. One of the more minor extensions dealt with the subdivision of process’s scheduling characteristics and was known as he INTERACTIVE /IA scheduling class. This scheduling class was targeted to frequent sleepers, with the mouse icon being one the first processes/tasks..

	Linux has no explicit SCHED_IA scheduling policy, but does alter scheduling characteristics based on some sleep behavior (example: GENTLE_FAIR_SLEEPERS) within the fair share scheduling configuration option. Processes / tasks that are CPU bound that fit into a SLEEPER behavior can have a hybrid behavior over time where during any one scheduling period, it may consume its variable length allocated time. This can alter its expected short latency to be current / ONPROC. To simplify the implementation, it is suggested that SCHED_IA be a sub scheduling policy of SCHED_NORMAL. Shouldn’t an administrator be able to classify that the NORMAL long term behavior of a task, be one as a FIXED sleeper? 

	Thus, the first Proposal is to explicitly support the SCHED_IA scheduling policy within the Linux kernel. After kernel support, any application that has the same functionality as priocntl(1) then needs to be altered to support this new scheduling policy.


Note: Administrator in this context should be a task with a UID, EUID, GID, EGID, etc, that has the proper CAPABILITY to alter scheduling behavior.


SCHED_UNFAIR
		UNIX / Linux scheduling has in the most part attempts to achieve some level of process / task scheduling fairness within the Linux scheduler using the fair share scheduling class. Exceptions do exist, but are not being discussed below. In general this type of scheduling is acceptable in a generic implementation, but has weaknesses when UNIX / Linux is moved into a different environment. Many companies use UNIX / Linux in heavy networking environments where one or more tasks can infrequently attempt to consume more than its fair share in a window scheduling period.

		This proposal is to acknowledge that “nice” and a few other scheduling workarounds do no always suffice to allow this temporary inequality to exist. Yes, a cpumask could be set that allows only certain tasks to run on specific nodes, however the implied assumption is that they only infrequently need to have inequality / greater “time slice” than their fair share. A network protocol task example is a convergence task that needs to run until it is finished and until that happens needed routing changes will not occur. The time window in which all tasks need to be run, SHOULD not need this task in consecutive time windows, thus over longer periods of time, it still fulfills the fair scheduling policy. Again the proper CAPABILITY needs to be specified with the priocntl(1) like application as running many tasks per CPU COULD then effect the performance of the system.

		Thus, explicit support for a new SCHED_UNFAIR scheduling policy is proposed / suggested within the Linux kernel. Again it can be a sub scheduling policy of SCHED_NORMAL.

		If there is an expressed need / want for this type of functionality to be patched into a git, please inform this engineer if any additional information is to be provided since this minimal TOI document is more architecture / enhancement based and does not deal into any details as to a possible implementation of the above additional functionality.

Thank you,
		Mitchell Erblich
		UNIX Kernel Engineer

Re: Linux Kernel Scheduling Addition Notification : Hybrid Sleepers and Unfair scheduling

[Mike Galbraith]

On Wed, 2015-03-18 at 16:25 -0700, Mitchell Erblich wrote:

> 
> SCHED_IA
> 	Over 10 years ago, System V Release 4 was enhanced with additional
> features by Sun Microsystems. One of the more minor extensions dealt
> with the subdivision of process’s scheduling characteristics and was
> known as he INTERACTIVE /IA scheduling class. This scheduling class
> was targeted to frequent sleepers, with the mouse icon being one the
> first processes/tasks..
> 
> 	Linux has no explicit SCHED_IA scheduling policy, but does alter
> scheduling characteristics based on some sleep behavior (example:
> GENTLE_FAIR_SLEEPERS) within the fair share scheduling configuration
> option.

That's about fairness, it levels the playing field sleepers vs hogs.

>  Processes / tasks that are CPU bound that fit into a SLEEPER behavior
> can have a hybrid behavior over time where during any one scheduling
> period, it may consume its variable length allocated time. This can
> alter its expected short latency to be current / ONPROC. To simplify
> the implementation, it is suggested that SCHED_IA be a sub scheduling
> policy of SCHED_NORMAL. Shouldn’t an administrator be able to classify
> that the NORMAL long term behavior of a task, be one as a FIXED
> sleeper?

Nope, we definitely don't want a SCHED_IA class.

Your box can't tell if you're interacting or not even if you explicitly
define something as 'interactive'.  If I stare in fascination at an
eye-candy screen-saver, it becomes 'interactive'.  If I'm twiddling my
thumbs waiting for a kbuild whatever other CPU intensive job to finish,
that job becomes the 'interactive' thing of import.  The last thing I
want is to have to squabble with every crack-head programmer on the
planet who thinks his/her cool app should get special treatment.

You can't get there from here.
> 
> 	Thus, the first Proposal is to explicitly support the SCHED_IA
> scheduling policy within the Linux kernel. After kernel support, any
> application that has the same functionality as priocntl(1) then needs
> to be altered to support this new scheduling policy.
> 
> 
> Note: Administrator in this context should be a task with a UID, EUID,
> GID, EGID, etc, that has the proper CAPABILITY to alter scheduling
> behavior.

> 
> SCHED_UNFAIR

Snip.. we already have truckloads of bandwidth control.

	-Mike

Re: Linux Kernel Scheduling Addition Notification : Hybrid Sleepers and Unfair scheduling

[Mitchell Erblich]

On Mar 18, 2015, at 7:38 PM, Mike Galbraith <umgwanakikbuti@gmail.com> wrote:

> On Wed, 2015-03-18 at 16:25 -0700, Mitchell Erblich wrote:
> 
>> 
>> SCHED_IA
>> 	Over 10 years ago, System V Release 4 was enhanced with additional
>> features by Sun Microsystems. One of the more minor extensions dealt
>> with the subdivision of process’s scheduling characteristics and was
>> known as he INTERACTIVE /IA scheduling class. This scheduling class
>> was targeted to frequent sleepers, with the mouse icon being one the
>> first processes/tasks..
>> 
>> 	Linux has no explicit SCHED_IA scheduling policy, but does alter
>> scheduling characteristics based on some sleep behavior (example:
>> GENTLE_FAIR_SLEEPERS) within the fair share scheduling configuration
>> option.
> 
> That's about fairness, it levels the playing field sleepers vs hogs.
> 
>> Processes / tasks that are CPU bound that fit into a SLEEPER behavior
>> can have a hybrid behavior over time where during any one scheduling
>> period, it may consume its variable length allocated time. This can
>> alter its expected short latency to be current / ONPROC. To simplify
>> the implementation, it is suggested that SCHED_IA be a sub scheduling
>> policy of SCHED_NORMAL. Shouldn’t an administrator be able to classify
>> that the NORMAL long term behavior of a task, be one as a FIXED
>> sleeper?
> 
> Nope, we definitely don't want a SCHED_IA class.
> 
> Your box can't tell if you're interacting or not even if you explicitly
> define something as 'interactive'.  If I stare in fascination at an
> eye-candy screen-saver, it becomes 'interactive'.  If I'm twiddling my
> thumbs waiting for a kbuild whatever other CPU intensive job to finish,
> that job becomes the 'interactive' thing of import.  The last thing I
> want is to have to squabble with every crack-head programmer on the
> planet who thinks his/her cool app should get special treatment.
> 
> You can’t get there from here.

This proposal was ONLY to resolve the legal issue with public domain code of notification when a patch was not offered.…

	Any “crack-head programmer”  can still set if he has the CAPABILITY to change the scheduling policy to a RT-FIFO or RT-RR, to give the app special treatment… So, this proposal does not mitigate or change that treatment, assuming that the same CAPABILITY is checked.

	POSIX ONLY specifies RT tasks as creating a level of unfairness, where in some APPLICATION SPECIFIC uses of Linux, need to execute an infrequently executed more than what is currently FAIR. 

	So, the Linux scheduler ALREADY determines if a task slept during a time window and if it DIDN’T, it is penalized versus the tasks that did sleep.   It is effectively a dynamic scheduling behavior, where sometimes your interactive task did not fully sleep. Thus, why not still treat it as a IA task, because of the nature/functionality of the task??? 

	 If could be generating tones/music through the audio/speaker driver of the system and you want a consistent minimal latency,  else you generate warble on your music.  Thus, if an admin/task KNOWS that a task is essentially a INTERACTIVE, aka a mouse icon driver, audio driver, etc that if a admin or startup script has the CAPABILITY, then he can set to make sure that the INTERACTIVE task ALWAYS/CONSISTENTLY is treated as an INTERACTIVE task.

		Doing this change allows one or more tasks to BETTER behave the same independently of the number of tasks that are being scheduled during the time window and the number of CPUs/cores without any other special scheduling.

	This was a SVR4.x feature within the SunOS kernel and a number of other SVR4.x UNIX Kernels, that could be set via priocntl(1) (Linux does not support) or a start script.

>> 
>> 	Thus, the first Proposal is to explicitly support the SCHED_IA
>> scheduling policy within the Linux kernel. After kernel support, any
>> application that has the same functionality as priocntl(1) then needs
>> to be altered to support this new scheduling policy.
>> 
>> 
>> Note: Administrator in this context should be a task with a UID, EUID,
>> GID, EGID, etc, that has the proper CAPABILITY to alter scheduling
>> behavior.
> 
>> 
>> SCHED_UNFAIR
> 
> Snip.. we already have truckloads of bandwidth control.
> 
> 	-Mike
> 

	This is NOT bandwidth control..  Allocates an increase in its time slice versus other tasks…

	SCHED_UNFAIR pertains to a task that can sometimes run and consume a UN-fair number of CPU cycles. With the routing protocol OSPFv2/v3, a well known Link state task is specified by function, but regular tasks that INFREQUENTLY execute like a file system file check(fsck) becomes a boot bottleneck if it is actually doing work and isn’t able to do its work without a number of context switches. With this functionality more than a 30% or more latency decrease can occur, depending on the number of tasks contending for the time window.

		Yes, if a TASK_UNFAIR policy always executes in every time window, then the other tasks are treated unfairly, but as originally specified, it makes sense to allow the DR & BDR & DR-OTHERSs to execute this critical task ASAP, and change the routing table where necessary.

		For you NFS or TCP people that MUST flush your data ASAP to the destination, it would be detrimental (loss of more data) to NOT allow one task to temporally consume an UNFAIR number of cycles versus other application tasks. 

	The Linux scheduler generally tries to generate a level of scheduling fairness and SOMETIMES, you temporally don’t want FAIRNESS without resorting to pushing task to one of the two RT policies.

	Mitchell Erblich

Re: Linux Kernel Scheduling Addition Notification : Hybrid Sleepers and Unfair scheduling

[Mike Galbraith]

On Wed, 2015-03-18 at 20:43 -0700, Mitchell Erblich wrote:

> This proposal was ONLY to resolve the legal issue with public domain
> code of notification when a patch was not offered.…

Ah, so completely off topic here.. but then you knew that.  How rude.

	-Mike

Re: Linux Kernel Scheduling Addition Notification : Hybrid Sleepers and Unfair scheduling

[Mitchell Erblich]

Group,

		As a contractor or employee, the code that I write while being employed by them is owned by the company that I work for.

		It is then up to them / legal / management, etc  whether they offer that code implementation to kernel.org or a ISP,  insert it into their release,  or whatever….

		My notification is to say here is a minimal TOI, explain additionally where necessary, that I never saw a patch offered,  it exists, and I would be willing to repeat the code with a different implementation for FREE as an individual.

			If the code is within a networking area, then maybe a simple Request For Enhancement (RFE) that explains functionality, probably some minimal API, but the direction is NOT to offer an implementation of code.

		 Thus,,,,  is just a legal statement that needs repeating each and every time that make my offer.

			How rude is that?

		  Thus, Mike ,, your statement is totally uncalled for, inappropriate… and that being behind a email address does not excuse that.

		Mitchell Erblich
		Kernel Engineer
		


On Mar 18, 2015, at 8:59 PM, Mike Galbraith <umgwanakikbuti@gmail.com> wrote:

> On Wed, 2015-03-18 at 20:43 -0700, Mitchell Erblich wrote:
> 
>> This proposal was ONLY to resolve the legal issue with public domain
>> code of notification when a patch was not offered.…
> 
> Ah, so completely off topic here.. but then you knew that.  How rude.
> 
> 	-Mike
> 

Re: Linux Kernel Scheduling Addition Notification : Hybrid Sleepers and Unfair scheduling

[Mike Galbraith]

On Wed, 2015-03-18 at 21:32 -0700, Mitchell Erblich wrote:

(again, not one on topic word)

> 			How rude is that?

Shrug, s/rude/dense maybe.  Whatever.  Byebye.

	-Mike

Re: Linux Kernel Scheduling Addition Notification : Hybrid Sleepers and Unfair scheduling

[Theodore Ts'o]

There is no legal requirement for anyone to give notification when
they make changes to the Linux kernel.  There are some experimental
licenses that have such a requirement, but the Linux kernel is not
licensed under such a license.

If you are aware that a company has made modifications and is shipping
code (i.e., making copies as defined by local copyright law), then you
can certainly talk to people who are interested in enforcing the GPL.
But the LKML isn't a proper venue for such discussion.

Cheers,

						- Ted