Hi everyone.
RIFS v3 has been released.
This version make a big change from RIFS v2(Algorithm).
Actually it solves problems that V2 left.
On my box I can play 320K MP3 music without any skipping(SMOOTH!).Also
I can shake my windows frequently.
1.latt benchmark
Parameters: min_wait=100ms, max_wait=500ms, clients=1
Entries logged: 108
Wakeup averages
-------------------------------------
Max 25 usec
Avg 10 usec
Stdev 2 usec
Stdev mean 0 usec
Work averages
-------------------------------------
Max 21183 usec
Avg 20129 usec
Stdev 246 usec
Stdev mean 24 usec
2.latt benchmark
Parameters: min_wait=100ms, max_wait=500ms, clients=1
Entries logged: 108
Wakeup averages
-------------------------------------
Max 22 usec
Avg 8 usec
Stdev 2 usec
Stdev mean 0 usec
Work averages
-------------------------------------
Max 20326 usec
Avg 20016 usec
Stdev 85 usec
Stdev mean 8 usec
~~~ :-)
Enjoy the interactive feels.
???ܽ????Դ????ĸо???
Chen
On Sat, May 26, 2012 at 9:38 PM, Chen <[email protected]> wrote:
> Hi everyone.
> RIFS v3 has been released.
> This version make a big change from RIFS v2(Algorithm).
> Actually it solves problems that V2 left.
> On my box I can play 320K MP3 music without any skipping(SMOOTH!).Also
> I can shake my windows frequently.
>
> 1.latt benchmark
> Parameters: min_wait=100ms, max_wait=500ms, clients=1
> Entries logged: 108
>
> Wakeup averages
> -------------------------------------
> Max 25 usec
> Avg 10 usec
> Stdev 2 usec
> Stdev mean 0 usec
>
> Work averages
> -------------------------------------
> Max 21183 usec
> Avg 20129 usec
> Stdev 246 usec
> Stdev mean 24 usec
>
>
> 2.latt benchmark
> Parameters: min_wait=100ms, max_wait=500ms, clients=1
> Entries logged: 108
>
> Wakeup averages
> -------------------------------------
> Max 22 usec
> Avg 8 usec
> Stdev 2 usec
> Stdev mean 0 usec
>
> Work averages
> -------------------------------------
> Max 20326 usec
> Avg 20016 usec
> Stdev 85 usec
> Stdev mean 8 usec
>
> ~~~ :-)
> Enjoy the interactive feels.
> ???ܽ????Դ????ĸо???
> Chen
Rotating priority for cpu intensive task does not exist anymore. :-)
On Sat, May 26, 2012 at 9:38 PM, Chen <[email protected]> wrote:
>
> RIFS v3 has been released.
>
It may help more if released in the diff format
Good Weekend
-hd
On Sun, May 27, 2012 at 10:41 AM, Chen <[email protected]> wrote:
> On Sun, May 27, 2012 at 10:33 AM, Chen <[email protected]> wrote:
>> Yes , it is a diff
>> 在 2012-5-27 上午9:08，"Hillf Danton" <[email protected]>写道：
>>
>>
>>>
>>> On Sat, May 26, 2012 at 9:38 PM, Chen <[email protected]> wrote:
>>> >
>>> > RIFS v3 has been released.
>>> >
>>>
>>> It may help more if released in the diff format
>>>
>>> Good Weekend
>>> -hd
>
> Now there is a new patch.It is a new V3 diff
> Also for the newest version of RIFS please visit
> http://code.google.com/p/rifs-scheduler/downloads/list to download.
> :-)
For all the version of RIFS, please visit:
http://code.google.com/p/rifs-scheduler/downloads/list
It is the github site(well I am preparing)
https://github.com/hi3766691/rifs-scheduler/
On 5/28/12, Chen <[email protected]> wrote:
> --- 3.3-sched-bfs-420.patch
> +++ rifs-v3-kernel3.3.x
> @@ -1,61 +1,7 @@
> -The Brain Fuck Scheduler v0.420 AKA smoking by Con Kolivas.
> -
> -A single shared runqueue O(n) strict fairness earliest deadline first
> design.
> -
> -Excellent throughput and latency for 1 to many CPUs on desktop and server
> -commodity hardware.
> -Not recommended for 4096 cpus.
> -
> -Scalability is optimal when your workload is equal to the number of CPUs
> on
> -bfs. ie you should ONLY do make -j4 on quad core, -j2 on dual core and so
> on.
> -
> -Features SCHED_IDLEPRIO and SCHED_ISO scheduling policies as well.
> -You do NOT need to use these policies for good performance, they are
> purely
> -optional for even better performance in extreme conditions.
> -
> -To run something idleprio, use schedtool like so:
> -
> -schedtool -D -e make -j4
> -
> -To run something isoprio, use schedtool like so:
> -
> -schedtool -I -e amarok
> -
> -Includes accurate sub-tick accounting of tasks so userspace reported
> -cpu usage may be very different if you have very short lived tasks.
> -
> --ck
> -
> -
> ----
> - Documentation/scheduler/sched-BFS.txt | 347 +
> - Documentation/sysctl/kernel.txt | 26
> - arch/powerpc/platforms/cell/spufs/sched.c | 5
> - arch/x86/Kconfig | 10
> - drivers/cpufreq/cpufreq.c | 7
> - drivers/cpufreq/cpufreq_conservative.c | 4
> - drivers/cpufreq/cpufreq_ondemand.c | 8
> - fs/proc/base.c | 2
> - include/linux/init_task.h | 64
> - include/linux/ioprio.h | 2
> - include/linux/jiffies.h | 2
> - include/linux/sched.h | 110
> - init/Kconfig | 16
> - init/main.c | 1
> - kernel/delayacct.c | 2
> - kernel/exit.c | 2
> - kernel/posix-cpu-timers.c | 12
> - kernel/sched/Makefile | 8
> - kernel/sched/bfs.c | 7251
> ++++++++++++++++++++++++++++++
> - kernel/sysctl.c | 31
> - lib/Kconfig.debug | 2
> - 21 files changed, 7865 insertions(+), 47 deletions(-)
> -
> -Index: linux-3.3-ck1/arch/powerpc/platforms/cell/spufs/sched.c
> -===================================================================
> ----
> linux-3.3-ck1.orig/arch/powerpc/platforms/cell/spufs/sched.c 2012-03-24
> 19:30:00.013420381 +1100
> -+++ linux-3.3-ck1/arch/powerpc/platforms/cell/spufs/sched.c 2012-03-24
> 19:30:29.038925740 +1100
> -@@ -63,11 +63,6 @@ static struct timer_list spusched_timer;
> +diff -ruN linux-3.3.5/arch/powerpc/platforms/cell/spufs/sched.c
> linux-3.3.5-RIFS-RC3-BRAIN-EATING/arch/powerpc/platforms/cell/spufs/sched.c
> +--- linux-3.3.5/arch/powerpc/platforms/cell/spufs/sched.c 2012-05-07
> 23:55:30.000000000 +0800
> ++++
> linux-3.3.5-RIFS-RC3-BRAIN-EATING/arch/powerpc/platforms/cell/spufs/sched.c 2012-05-19
> 22:04:37.000000000 +0800
> +@@ -63,11 +63,6 @@
> static struct timer_list spuloadavg_timer;
>
> /*
> @@ -67,363 +13,90 @@
> * Frequency of the spu scheduler tick. By default we do one SPU
> scheduler
> * tick for every 10 CPU scheduler ticks.
> */
> -Index: linux-3.3-ck1/Documentation/scheduler/sched-BFS.txt
> -===================================================================
> ---- /dev/null 1970-01-01 00:00:00.000000000 +0000
> -+++ linux-3.3-ck1/Documentation/scheduler/sched-BFS.txt 2012-03-24
> 19:30:29.038925740 +1100
> -@@ -0,0 +1,347 @@
> -+BFS - The Brain Fuck Scheduler by Con Kolivas.
> -+
> -+Goals.
> -+
> -+The goal of the Brain Fuck Scheduler, referred to as BFS from here on, is
> to
> -+completely do away with the complex designs of the past for the cpu
> process
> -+scheduler and instead implement one that is very simple in basic design.
> -+The main focus of BFS is to achieve excellent desktop interactivity and
> -+responsiveness without heuristics and tuning knobs that are difficult to
> -+understand, impossible to model and predict the effect of, and when tuned
> to
> -+one workload cause massive detriment to another.
> -+
> -+
> -+Design summary.
> -+
> -+BFS is best described as a single runqueue, O(n) lookup, earliest
> effective
> -+virtual deadline first design, loosely based on EEVDF (earliest
> eligible virtual
> -+deadline first) and my previous Staircase Deadline scheduler. Each
> component
> -+shall be described in order to understand the significance of, and
> reasoning for
> -+it. The codebase when the first stable version was released was
> approximately
> -+9000 lines less code than the existing mainline linux kernel scheduler
> (in
> -+2.6.31). This does not even take into account the removal of documentation
> and
> -+the cgroups code that is not used.
> -+
> -+Design reasoning.
> -+
> -+The single runqueue refers to the queued but not running processes for
> the
> -+entire system, regardless of the number of CPUs. The reason for going back
> to
> -+a single runqueue design is that once multiple runqueues are introduced,
> -+per-CPU or otherwise, there will be complex interactions as each runqueue
> will
> -+be responsible for the scheduling latency and fairness of the tasks
> only on its
> -+own runqueue, and to achieve fairness and low latency across
> multiple CPUs, any
> -+advantage in throughput of having CPU local tasks causes other
> disadvantages.
> -+This is due to requiring a very complex balancing system to at best
> achieve some
> -+semblance of fairness across CPUs and can only maintain relatively low
> latency
> -+for tasks bound to the same CPUs, not across them. To increase said
> fairness
> -+and latency across CPUs, the advantage of local runqueue locking, which
> makes
> -+for better scalability, is lost due to having to grab multiple locks.
> -+
> -+A significant feature of BFS is that all accounting is done purely
> based on CPU
> -+used and nowhere is sleep time used in any way to determine entitlement
> or
> -+interactivity. Interactivity "estimators" that use some kind of sleep/run
> -+algorithm are doomed to fail to detect all interactive tasks, and to
> falsely tag
> -+tasks that aren't interactive as being so. The reason for this is that it
> is
> -+close to impossible to determine that when a task is sleeping, whether it
> is
> -+doing it voluntarily, as in a userspace application waiting for input in
> the
> -+form of a mouse click or otherwise, or involuntarily, because it is
> waiting for
> -+another thread, process, I/O, kernel activity or whatever. Thus, such an
> -+estimator will introduce corner cases, and more heuristics will be
> required to
> -+cope with those corner cases, introducing more corner cases and failed
> -+interactivity detection and so on. Interactivity in BFS is built
> into the design
> -+by virtue of the fact that tasks that are waking up have not used up
> their quota
> -+of CPU time, and have earlier effective deadlines, thereby making it
> very likely
> -+they will preempt any CPU bound task of equivalent nice level. See below
> for
> -+more information on the virtual deadline mechanism. Even if they do
> not preempt
> -+a running task, because the rr interval is guaranteed to have a bound
> upper
> -+limit on how long a task will wait for, it will be scheduled within
> a timeframe
> -+that will not cause visible interface jitter.
> -+
> -+
> -+Design details.
> -+
> -+Task insertion.
> -+
> -+BFS inserts tasks into each relevant queue as an O(1) insertion into a
> double
> -+linked list. On insertion, *every* running queue is checked to see
> if the newly
> -+queued task can run on any idle queue, or preempt the lowest running
> task on the
> -+system. This is how the cross-CPU scheduling of BFS achieves
> significantly lower
> -+latency per extra CPU the system has. In this case the lookup is, in the
> worst
> -+case scenario, O(n) where n is the number of CPUs on the system.
> -+
> -+Data protection.
> -+
> -+BFS has one single lock protecting the process local data of every task in
> the
> -+global queue. Thus every insertion, removal and modification of task
> data in the
> -+global runqueue needs to grab the global lock. However, once a task
> is taken by
> -+a CPU, the CPU has its own local data copy of the running process'
> account
>
On Sun, May 27, 2012 at 6:49 PM, Hillf Danton <[email protected]> wrote:
> On Sun, May 27, 2012 at 10:41 AM, Chen <[email protected]> wrote:
>>
>> Now there is a new patch.It is a new V3 diff
>> Also for the newest version of RIFS please visit
>> http://code.google.com/p/rifs-scheduler/downloads/list to download.
>>
> Again you misread.
> Please post, on LKML if you like, the diff between bfs-420 and rifs-3, clear?
> -hd
This is the patch
On 28.05.2012, Chen wrote:
> This is the patch
What you posted is a patch on the BFS-4.20 patch (by Con Kolivas)
itself, and not a patch against an actual kernel tree. The output
has a format which is totally unreadable and disgusting,
and I can't apply it without tinkering with BFS first,
(which is designed for 3.3.x and needs a merge into 3.4.0 on top of that)
Could you please provide a clean patch which is based on one of the
current trees?
Besides, it seems to me that you are trying to reinvent the wheel
using a lot of pieces of Con's -ck patch..
Thanks,
Heinz.
On Mon, May 28, 2012 at 8:03 PM, Chen <[email protected]> wrote:
> This is not the regular patch!The regular one is on
> http://rifs-scheduler.googlecode.com
>
> 在 2012-5-28 下午7:39，"Heinz Diehl" <[email protected]>写道：
>
>> On 28.05.2012, Chen wrote:
>>
>> > This is the patch
>>
>> What you posted is a patch on the BFS-4.20 patch (by Con Kolivas)
>> itself, and not a patch against an actual kernel tree. The output
>> has a format which is totally unreadable and disgusting,
>> and I can't apply it without tinkering with BFS first,
>> (which is designed for 3.3.x and needs a merge into 3.4.0 on top of that)
>>
>> Could you please provide a clean patch which is based on one of the
>> current trees?
>>
>> Besides, it seems to me that you are trying to reinvent the wheel
>> using a lot of pieces of Con's -ck patch..
>>
>> Thanks,
>> Heinz.
>> --
>> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
>> the body of a message to [email protected]
>> More majordomo info at http://vger.kernel.org/majordomo-info.html
>> Please read the FAQ at http://www.tux.org/lkml/
This is a diff between bfs and rifs actually.
Also RIFS and BFS are different scheduler.
Former one use the algorithm I 've invented(O(1) implementation ),
latter one use EEVDF(O(n) implementation)