Re: [RFC][PATCH] SCHED_EDF scheduling class

From: Raistlin
Date: Tuesday, September 22, 2009 - 3:30 am

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)

iEYEABECAAYFAkq4pzIACgkQk4XaBE3IOsTBYACfStQxKxkDhBBUjcCETzd5NBhl
fecAn3z26c+uCVQ0HKlh1HOnftAhwDFd
=c49e
-----END PGP SIGNATURE-----
From: Peter Zijlstra
Date: Tuesday, September 22, 2009 - 5:38 am

Yeah, I know, there's lots of interest in having a deadline scheduler.

One of the things we'll have to look at is removing all the EDF
assumptions from it.

I think we'll be wanting to do something like s/EDF/DEADLINE/
s/edf/deadline/ etc. on the code base to begin with.

I think the task model as exposed through sched_param_ex needs a little
more thought as well.

But anyway, I'm very glad to see the code.. and am hoping to have some
time myself to prod at the PI code to work with this.

--

From: Claudio Scordino
Date: Thursday, September 24, 2009 - 9:08 am

This is easy: we can give it whatever name you want :)

Are you suggesting to use "SCHED_DEADLINE" ?

Cheers,

                 Claudio

--

From: Claudio Scordino
Date: Tuesday, September 22, 2009 - 4:58 am

Hi Peter, hi all,

      note that the request of having an EDF scheduling class integrated 
in the mainline kernel does not come from academy, but comes from industry.

In particular, at least the following companies are interested in this 
feature:

1. ERICSSON AB (http://www.ericsson.com)

2. Evidence Srl (http://www.evidence.eu.com): who implemented the code

3. AKAtech (http://www.akatech.ch)

4. Qprel (http://www.qprel.com)

5. Tertium technology (http://www.tertiumtechnology.com)

6. M2Tech (http://www.m2tech.biz)


Then, there are _also_ some universities and research centers:

1. Scuola Sant'Anna, Italy

2. University of Pisa, Italy

3. Lunds Universitet, Lund, Sweden

4. Technical University Kaiserslautern, Germany

5. Ecole Polytechnique Federale de Lausanne, Swiss

But I guess there are other companies and institutions interested, out 
there...

Cheers,

            Claudio
--

From: Daniel Walker
Date: Tuesday, September 22, 2009 - 6:24 am

You've got some type of encoding corruption in your patch,

+       else {
+               if (!edf_task(p))
+                       p->sched_class =3D &fair_sched_class;
+               else
+                       p->sched_class =3D &edf_sched_class;
+       }
=20
        p->prio =3D prio;
=20

See the =20 , and =3D above.. I'm not sure exactly how that gets into
patches ;( We require utf8 encodings , some people can handle the stuff
above but most scripts and the patch command won't be able to. I realize
this is an RFC , so the next time you submit this try to make it utf8 ..

Daniel

--

From: Raistlin
Date: Tuesday, September 22, 2009 - 7:01 am

diff --git a/arch/arm/include/asm/unistd.h b/arch/arm/include/asm/unistd.h
index 89f7ead..e851625 100644
--- a/arch/arm/include/asm/unistd.h
+++ b/arch/arm/include/asm/unistd.h
@@ -391,6 +391,9 @@
 #define __NR_pwritev			(__NR_SYSCALL_BASE+362)
 #define __NR_rt_tgsigqueueinfo		(__NR_SYSCALL_BASE+363)
 #define __NR_perf_event_open		(__NR_SYSCALL_BASE+364)
+#define __NR_sched_setscheduler_ex	(__NR_SYSCALL_BASE+365)
+#define __NR_sched_setparam_ex		(__NR_SYSCALL_BASE+366)
+#define __NR_sched_getparam_ex		(__NR_SYSCALL_BASE+367)
 
 /*
  * The following SWIs are ARM private.
diff --git a/arch/arm/kernel/calls.S b/arch/arm/kernel/calls.S
index fafce1b..42ad362 100644
--- a/arch/arm/kernel/calls.S
+++ b/arch/arm/kernel/calls.S
@@ -374,6 +374,9 @@
 		CALL(sys_pwritev)
 		CALL(sys_rt_tgsigqueueinfo)
 		CALL(sys_perf_event_open)
+/* 365 */	CALL(sys_sched_setscheduler_ex)
+		CALL(sys_sched_setparam_ex)
+		CALL(sys_sched_getparam_ex)
 #ifndef syscalls_counted
 .equ syscalls_padding, ((NR_syscalls + 3) & ~3) - NR_syscalls
 #define syscalls_counted
diff --git a/arch/x86/ia32/ia32entry.S b/arch/x86/ia32/ia32entry.S
index 74619c4..fde92c2 100644
--- a/arch/x86/ia32/ia32entry.S
+++ b/arch/x86/ia32/ia32entry.S
@@ -832,4 +832,7 @@ ia32_sys_call_table:
 	.quad compat_sys_pwritev
 	.quad compat_sys_rt_tgsigqueueinfo	/* 335 */
 	.quad sys_perf_event_open
+	.quad sys_sched_setscheduler_ex
+	.quad sys_sched_setparam_ex
+	.quad sys_sched_getparam_ex
 ia32_syscall_end:
diff --git a/arch/x86/include/asm/unistd_32.h b/arch/x86/include/asm/unistd_32.h
index 6fb3c20..a83163f 100644
--- a/arch/x86/include/asm/unistd_32.h
+++ b/arch/x86/include/asm/unistd_32.h
@@ -342,6 +342,9 @@
 #define __NR_pwritev		334
 #define __NR_rt_tgsigqueueinfo	335
 #define __NR_perf_event_open	336
+#define __NR_sched_setscheduler_ex	337
+#define __NR_sched_setparam_ex	338
+#define __NR_sched_getparam_ex	339
 
 #ifdef __KERNEL__
 
diff --git a/arch/x86/include/asm/unistd_64.h ...
From: Daniel Walker
Date: Tuesday, September 22, 2009 - 7:02 am

Your using git already , why not use git-format-patch and
git-send-email ?

Daniel

--

From: Peter Zijlstra
Date: Tuesday, September 22, 2009 - 9:42 am

Don't worry, they are fine.

--

From: Ingo Molnar
Date: Tuesday, September 22, 2009 - 12:11 pm

Yes - i was able to save and apply the patch just fine too:

earth4:~/tip> q push
Applying patch patches/sched_edf-scheduling-class.patch
patching file arch/arm/include/asm/unistd.h
patching file arch/arm/kernel/calls.S
patching file arch/x86/ia32/ia32entry.S
patching file arch/x86/include/asm/unistd_32.h
patching file arch/x86/include/asm/unistd_64.h
patching file arch/x86/kernel/syscall_table_32.S
patching file include/linux/sched.h
Hunk #3 succeeded at 165 (offset 4 lines).
Hunk #5 succeeded at 1205 (offset 23 lines).
Hunk #7 succeeded at 1609 (offset 22 lines).
patching file include/linux/syscalls.h
patching file init/Kconfig
patching file kernel/fork.c
Hunk #1 succeeded at 1223 (offset 20 lines).
patching file kernel/sched.c
Hunk #14 succeeded at 6099 (offset 12 lines).
Hunk #16 succeeded at 6287 (offset 12 lines).
Hunk #18 succeeded at 6339 (offset 12 lines).
Hunk #20 succeeded at 6376 (offset 12 lines).
Hunk #22 succeeded at 6486 (offset 12 lines).
Hunk #24 succeeded at 6540 (offset 12 lines).
Hunk #26 succeeded at 6609 (offset 12 lines).
Hunk #28 succeeded at 6704 (offset 12 lines).
Hunk #30 succeeded at 9547 (offset 12 lines).
Hunk #32 succeeded at 9636 (offset 12 lines).
Hunk #34 succeeded at 9747 (offset 12 lines).
Hunk #36 succeeded at 10218 (offset 12 lines).
Hunk #38 succeeded at 10277 (offset 12 lines).
Hunk #40 succeeded at 10750 (offset 12 lines).
Hunk #42 succeeded at 10838 (offset 12 lines).
patching file kernel/sched_debug.c
patching file kernel/sched_edf.c
patching file kernel/sched_fair.c
patching file kernel/sched_rt.c
patching file kernel/trace/trace_sched_wakeup.c

Now at patch patches/sched_edf-scheduling-class.patch

Daniel is a kind of self-elected joker-bot on lkml, running checkpatch 
out of .procmailrc and annoying people with trivial comments, 
distracting from the real discussion. Raistlin, feel free to ignore him 
in the future.

	Ingo
--

From: Daniel Walker
Date: Tuesday, September 22, 2009 - 5:51 pm

You want to talk about it constructively or not? I'll stop sending those
emails if it's actually negative , but I don't think it is..

Daniel

--

From: Joe Perches
Date: Tuesday, September 22, 2009 - 6:01 pm

Hi Daniel.

I think it'd be more helpful if instead of merely sending
a "hah! checkpatch failure!" email you send the submitter
a gentler nudge and a fixed patch.

cheers, Joe


--

From: Daniel Walker
Date: Tuesday, September 22, 2009 - 6:11 pm

I don't say "hah!" like I caught you or something .. I could try to
soften the emails further so that's not the feeling .. As far as sending
fixed patches to people it's not really feasible due to the number of
patches I would have to send out.. The other issues is that if I send a
corrected patch I could become responsible for that persons patch
instead of them .. I could send out delta patches, however, I don't want
people to rely on me to fix these issues.. Ideally people would correct
them prior to sending the patches out..

Daniel

--

From: Andy Isaacson
Date: Wednesday, September 23, 2009 - 12:24 pm

I'd rather see 10% coverage with useful patches than 100% coverage of
"there is some problem in this patch but I can't be bothered to say


Sure, and checkpatch is useful for that -- and more helper scripts to
automate the process would be helpful.  For example, extending "git
send-email" to have an optional "warn about checkpatch failures" would
be a useful addition, especially if it's not too annoying.  (I find the
current checkpatch output somewhat annoying, so just including that
wouldn't be great IMO.)

I would strongly recommend that you redistribute the effort you're
putting in, and only send messages where you have non-trivial input to
the development process.  For example, saying "This patch has checkpatch
errors.  Please fix the indentation and the EXPORT_SYMBOL errors, and
move function declarations to foo.h" would be much much more useful than
"it looks like you have a few style issues".

Let's go through a few of your recent checkpatch messages:


Patch <1252870707-4824-5-git-send-email-felipe.contreras@gmail.com> is a
strict improvement on the existing code, and changing the comma spacing
on just these two lines to silence checkpatch would make the file
inconsistent.  Changing all 12 functionlike #defines in this file would
be outside the purview of this patch.  You could have done the robotlike
patch and fixed the issue in this file in the time it would have taken
to do this analysis, and then you would have seen that the file has far
worse issues than the trivial ones checkpatch flagged in Felipe's patch.

Verdict: useless.


Joe is correct in his response, in this case the "error" from checkpatch
is ignorable.  Your responses in <1252467842.14793.66.camel@desktop> and
<1252466482.14793.60.camel@desktop> are dismissive of exactly the
concerns people are raising here, and you badly misstate your case when
without apologizing when your mistake was pointed out.

Verdict: useless, and abrasive in your response to correction.

Message-Id: ...
From: Daniel Walker
Date: Thursday, September 24, 2009 - 7:58 am

Your kind of putting words in my mouth here.. I can be bothered to say
what the errors are, but most people have the tool already. The errors

Yeah, git integration would be nice if it doesn't already exist. I've
never seen that feature tho. git does have a warn on trailing whitespace

I could do that.. However, my main annoyance is the style issues. Many
of the patches that I have commented on I've reviewed to find other
issues that could be solved, but often times other than the style issues

At the time, I didn't think people should use the style consistent with
the file. For instance, if you touch a line you should be responsible
for the clean up on that line.. However, I've since stopped asking
people to do that since it could be overwhelming, and there's many times
when people do automatic regex changes which have nothing to do with any

I was dismissive here, however I still do think those lines deserved the
clean up.. The lines where being altered enough to expose a checkpatch
bug due to the attribute (I later submitted a fix for checkpatch) ..
Also realize that the patch touched several architectures, and it was
attached to a larger patch set which I think would have been the perfect

I hesitated to send it .. It's often difficult to justify sometimes, but

I did read the errors, not all of them however.. Indentation issues can
cause some different types of checkpatch output, which to me didn't
initially point to a mailer problem .. This patch was totally worthless

Are we talking about the same email from Paul? I had already sent him
some other checkpatch output in another thread, and he thanked for
catching it. So in this case I assumed he wouldn't mine. So I don't feel

I usually go by the number of errors I find when I start saying "We" ..
I don't know Lennart at all, and there was no disrespect intended .. I
still think going by the number of errors I find is appropriate, however

I don't see anything abrasive in that email .. Infact I think your
re-write ...
From: Pavel Machek
Date: Wednesday, September 30, 2009 - 5:06 am

Well, so pick the worst offenders, only. That will also nicely reduce
ammount of distraction on  the list.
								Pavel

-- 
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html
--

From: Ingo Molnar
Date: Wednesday, September 23, 2009 - 5:22 am

He should consider not sending them at all. It's up to maintainers and 
the developers involved with that code whether the small details that 
checkpatch flags are important or not at a given point in the patch 
cycle.

For example i use checkpatch all the time and i think it's a fantastic 
tool, still i dont want another nuisance layer on lkml interfering with 
the patch flow.

If a patch gets so far in the patch cycle that i'm thinking about 
merging it, i might fix the checkpatch failures myself (often they are 
trivial), and i might warn frequent contributors about repeat patterns 
of small uncleanlinesses - or i might bounce the patch back to the 
contributor. I also ignore certain classes of checkpatch warnings.

What Daniel is doing is basically a semi-mandatory checkpatch layer on 
lkml and that's both a distraction and harmful as well. We dont need a 
"checkpatch police" on lkml. We want an open, reasonable, human driven 
patch process with very little buerocracy and no buerocrats.

	Ingo
--

From: Daniel Walker
Date: Wednesday, September 23, 2009 - 7:43 am

I think short term you might be right, that it is a nuisance to deal
with these issues.. However, these are real code comments which is what
this list is designed for.. Long term I don't think I will be sending
many of these emails at all, in fact I've only been doing this 3 weeks
and I can already see a drop off in the number of errors that I'm
finding.. It's like advertising, as soon as people start seeing a lot of
checkpatch related emails, they start to remember to use the tool.

Not to mention that automated code review (in mass) is useful .. Our
eyes can miss things, and having a massively used tool that checks for
all the common problems that we encounter is a good thing.. For
instance, checkpatch already found a locked semaphore, and a mutex type
semaphore in the "Target_Core_Mod ConfigFS infrastructure", which I'm
sure no one would want to enter the kernel, but had been missed. It also
found one real code defect, 

http://lkml.indiana.edu/hypermail/linux/kernel/0909.1/00129.html

The more we use the tool the better the tool becomes, and the more real
problems can be caught prior to code inclusion ..

I could have a higher threshold for when these errors become note
worthy, and I've been struggling with that since I started doing this..
I don't think not commenting at all would be a good thing..

Daniel

--

From: Pavel Machek
Date: Wednesday, September 30, 2009 - 5:04 am

Getting you 'have misplaced parenthesis' feedback on a bugfix, on a
file thatt has 1001 checkpatch problems, and when the patch does not
actually introduce the problem... certainly is unwelcome.

What about simply avoiding the mails when the file being changed
already has checkpatch problems?
									Pavel 

-- 
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html
--

From: Raistlin
Date: Wednesday, September 23, 2009 - 12:03 am

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)

iEYEABECAAYFAkq5yCsACgkQk4XaBE3IOsRekACcDhRR08UwN0vVvi9FyjDeUg5t
kbgAnAp2A9EuN1hXDvQC/q/qutlc2K7j
=IqrX
-----END PGP SIGNATURE-----
From: Steven Rostedt
Date: Wednesday, September 23, 2009 - 2:39 pm

Hmm, I use evolution with no issues with patches. I just set it to 
Preformatted (from Normal), and then hit "Insert->Text File ..." and it 
inlines quite nicely.

/me says this while sending via pine ;-)

-- Steve

--

From: GeunSik Lim
Date: Wednesday, September 23, 2009 - 5:58 pm

Me too.
I also evolution(ver.2.8.0) with no issues like Steven.
For example,
1) select "Preformat" select form in Compse Message window.
2) and then, hit "Insert - Test File ... "



-- 
Regards,
GeunSik Lim ( Samsung Electronics )
Blog : http://blog.naver.com/invain/
e-Mail: geunsik.lim@samsung.com
           leemgs@gmail.com , leemgs1@gmail.com
--

--

From: Peter Zijlstra
Date: Tuesday, September 22, 2009 - 9:38 am

Daniel, welcome to my kill-file.

--

From: Jonathan Corbet
Date: Tuesday, September 22, 2009 - 4:39 pm

On Tue, 22 Sep 2009 06:24:38 -0700

I could swear we talked about quoted-printable before.  You really need
a new mailer.  Even evolution (which you seem to be using) should
really be able to handle this.

jon
--

From: Daniel Walker
Date: Tuesday, September 22, 2009 - 4:55 pm

We did .. It's not my mailer, it's my scripts .. I read a little of
wikipedia on this and it says it's a MIME encoding..

http://en.wikipedia.org/wiki/Quoted-printable

So it's like a mime encoded patch instead of plain ascii encoded
patch .. I don't think we should all have to parse this stuff out, we
should just be getting utf8 encodings which covers everything we use in
the kernel AFAIK ..

Daniel

--

From: Jonathan Corbet
Date: Tuesday, September 22, 2009 - 5:06 pm

On Tue, 22 Sep 2009 16:55:39 -0700

I have scripts that handle email as well.  But I wrote them in a
scripting language which has modules to cope with standard-compliant
email, and I have no trouble with other transfer encodings at all.  You
really need to do the same.  Better you fix your scripts than
continually demanding that the rest of the development community
conform to your restrictive requirements.

Daniel, I believe that you are really trying to help make the kernel
better.  But I fear that you may be having the opposite effect by
discouraging contributions from others.  Please consider taking a step
back and thinking about your interactions and the nature of your
efforts; I think you may find that there are more productive and
encouraging ways for you to contribute.

Thanks,

jon
--

From: Daniel Walker
Date: Tuesday, September 22, 2009 - 5:40 pm

"restrictive requirements" ? I mean don't blame me for that .. It's in
Documentation/email-clients.txt .. The selected norm is UTF8 , and I
don't disagree with that. After researching it that is what we should be
using. At the same time, I'm not demanding anything of anyone , I'm
simply asking nicely for the submitter to check what they are doing..

My scripts may not handle it which is fine. I just wouldn't likely end

I am trying to make the kernel (or community) better, but my motivation
is purely my own (as it often is with people on this list) ..

I don't see the effects your indicating, discouraging contributions .. I
think if anything I'm helping people to get to a place where they can
contribute in a comfortable way without worrying about things like
checkpatch .. I think the problem most submitters have on this list is
that no one tells them they are doing something wrong so they don't
correct it. I clearly recall submitting my first several patches
copy-and-pasted which got either ignored , or caused a maintainer lots
of pain .. Had I been told earlier that it was a problem I would have
corrected it immediately (and been happy to have been notified about
it)..

discouraging contributions is more something that happens when you get
the responses I got earlier in this thread..

Daniel

--

From: Avi Kivity
Date: Wednesday, September 23, 2009 - 4:46 am

Look at the context.  Here we have a new scheduling class introduced out 
of the blue.  The discussion should be around whether it makes sense; if 
it does, whether the design is good or not; if it is, whether the code 
is maintainable or not, if that passes, whether there are bugs in the 
code or not.  Until we've decided that Linux needs this scheduling class 
and that this patchset is well designed and written, spelling errors are 

That's probably intentional.  Whitespace fixes have their place but not 
at this stage in a patch's lifecycle.

-- 
error compiling committee.c: too many arguments to function

--

From: Ingo Molnar
Date: Wednesday, September 23, 2009 - 5:25 am

Exactly. What might make sense is to scan linux-next for new commits 
that show serious cleanliness trouble - and send fix patches to the 
parties involved. That's a real effort and brings the code forward.

	Ingo
--

From: Daniel Walker
Date: Wednesday, September 23, 2009 - 7:50 am

Often times when a patch is at youngest that when you want to catch
these issues .. This EDF patch will likely get submitted more than
twice. If you catch all the minor problems first you will not be dealing
with them later when it comes time to include the code.

In this case the author is not totally aware of how to submit this
code.. I don't think it's at all inappropriate to comment on that. His
next submission will likely be much cleaner and nicer. It may even speed
up the inclusion process since he'll be more easily able to submit the
code (with practice and comments from us).

Daniel



--

From: Avi Kivity
Date: Wednesday, September 23, 2009 - 7:58 am

Not true, you want to address the major issues first.  What's the point 
of fixing whitespace if the whole approach is rejected? if it has to 

Give people some credit.

-- 
error compiling committee.c: too many arguments to function

--

From: Daniel Walker
Date: Wednesday, September 23, 2009 - 8:08 am

I'm not sure why your fixated on whitespace , but thinking about it more
I don't think it matters .. If you fix whitespace or major issues first,
it doesn't matter .. All the issues have to eventually get fixed .. Not
to mentioned that LKML is not something you could remotely control in

What do you mean?

Daniel

--

From: Avi Kivity
Date: Wednesday, September 23, 2009 - 8:12 am

A technical issue is that if you rewrite the code the whitespace fix 
becomes irrelevant.  But more important is that it's a distraction when 

If he's able to write a scheduling class, he'll pick up the coding style 
when it becomes relevant.

-- 
error compiling committee.c: too many arguments to function

--

From: Daniel Walker
Date: Wednesday, September 23, 2009 - 8:24 am

It's not irrelevant, since a person doing that rewrite will be
conscience of whitespace during the re-write ..

The same with general coding style, if someone does a rewrite who has
been alerted to checkpatch problems they will likely use it themselves

There's plenty of large projects that never get off the ground cause
people don't follow the coding style, or don't write clean code.. Take a
look at the staging tree there's plenty of large dirty projects in
there.

Daniel 

--

From: Pavel Machek
Date: Wednesday, September 30, 2009 - 5:05 am

You  want to deal with them later, because many patches end up  in
trashcan...

Now, Ingo's idea of scanning -next (and fixing it) sounds sane...

								Pavel
-- 
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html
--

From: Linus Walleij
Date: Tuesday, September 22, 2009 - 1:55 pm

Hi Raistlin,

it's great fun to see this scheduler materialize, I was present at the
workshop in Kaiserslautern and waited for the code since. What I'm
interested in getting a briefing on right now is what practical use EDF
schedulers have, since I think this is what many people will ask for.

I think actually the answers are the same as when I asked at Meld
(of all places) what HRtimers are actually for. And I I got the non-all
inclusive answer that they're for Flight simulators.
Which is obviously in the domain of automatic control.
http://en.wikipedia.org/wiki/Automatic_control

So one application of HRTimers has been to trigger events in
userspace programs, especially when your dealing with issues
related to automatic control. Automatic control is also
mentioned throughout this patch. (Yes, I know HRtimers
have other great uses also, especially in-kernel, those will
remain.)

I am very interested in if you or someone else
could elaborate on the relation between HRtimers and deadline
scheduling. To my untrained mind it looks like HRtimers will
fire events to your task in a very precise manner, but
you cannot currently guarantee that they will then proceed to
process their target task in time (meet a deadline).

I'm under the impression that some people currently use
some periodic HRtimers (through either the timerfd_create system
call I guess, or POSIX timer_create(CLOCK_REALTIME_HR...)
timers combined with some SHED_FIFO or so to achieve the same
thing a deadline scheduler would do, but since SCHED_FIFO cannot
really guarantee that this will work, you simply underutilize
the system a bit, add the CONFIG_PREEMPT_RT patch so the
timers are not blocked by things like slow interrupthandlers or
starvation (priority inversion) and then hope for the best. It turns
out to work. You measure on the system and it has the desired
"hard realtime" characteristics.

Do people do such things? I haven't seen those applications,
they all tend to be closed-source really. I would ...
From: Raistlin
Date: Wednesday, September 23, 2009 - 6:00 am

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)

iEYEABECAAYFAkq6G9sACgkQk4XaBE3IOsSffACffAlQFq/1v+l3CiUWr2mui1go
7H4AnRRCNE1SzDmVnfdJ2wZarb6EsZS2
=PI8A
-----END PGP SIGNATURE-----
From: Claudio Scordino
Date: Wednesday, September 23, 2009 - 6:22 am

Hi Linus,


Yes. With HRT you have timing measures with a higher resolution than 
using normal timers. This means that everything in the system runs more 
precisely, and latencies are reduced.

However, "how" it runs, depends on the scheduling algorithm, which is 
the part of the kernel that at any instant chooses which task must be 
executed. Our scheduling class introduces the chance of ordering tasks 
execution in a further manner, that is according to the Earliest 
Deadline First (EDF) algorithm. Therefore, after the patch is applied, a 
new scheduling policy is available for scheduling tasks. Consider that 
old policies (sched_fair and sched_rt) still remain, and you are not 
forced to use EDF ordering. This way, if you don't use EDF tasks, the 

Let's take a step back. The problem in real-time scheduling is to find 
an order of scheduling tasks so that each of them meets its deadlines. 
This way, you get determinism and predictability (i.e., you can trust 
that your tasks will be executed at the "right" instant of time).
Several scheduling algorithms exist to generate different orders of 
execution that ensure this property.

In particular, several differences exist between fixed priority and 
dynamic priority algorithms (like SCHED_EDF). In my opinion, the most 
relevant is the following one.

Suppose you have a single processor and a set composed by periodic 
real-time tasks, each one characterized by an amount of execution time 
("budget") that must be executed every "period". This way, the deadline 
for each task is equal to the end of its current period.

The sum of (budget/period) of all tasks is usually called "bandwidth".

Using fixed priority schedulers, you need a quite complicated equation 
to understand if it is possible to guarantee the deadlines of every 
task. This equation must be re-computed each time you change a budget or 
period of some task.
Even worse, depending on the task set, it may happen that the bandwidth 
must be lower than 100% ...
From: Linus Walleij
Date: Wednesday, September 23, 2009 - 7:08 am

Hi Claudio, thanks for the detailed answer!


This must be under the assumption that all code running in the system
is preemtible, is it not? Which means, negligible or close to negligible
non-preemptible code.

How much as we might like it to be, that is not (yet) the situation
with the Linux kernel, far off.

So we will still very much need the CONFIG_PREEMPT_RT patch
to get closer to that ideal situation, and we still need to get rid of
the BKL.

Well I guess you aldready know that, but take it as a note to
the bystanders of this discussion, which are plenty.

Now I ought to write fewer mails and look into solving that little
problem... You don't happen to know if we can have a EU FP7
project sponsored to rid out the BKL and switch and test drivers
en masse to use threaded interrupt handlers do you? ;-)

Linus Walleij
--

From: Raistlin
Date: Wednesday, September 23, 2009 - 7:45 am

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)

iEYEABECAAYFAkq6NHQACgkQk4XaBE3IOsSpMQCfcaUtGtLeAs8R+w2AnMM+mD7K
GmAAn2VRVhHyaH4kilOKix/B5KUrIYgo
=9wDp
-----END PGP SIGNATURE-----
From: Linus Walleij
Date: Wednesday, September 23, 2009 - 5:33 am

Hi Raistlin,

I have trouble compiling the (mainline) kernel for ARM u300_defconfig with the
sched-edf patches:

In file included from /home/linus/src/linux-trees/linux-2.6/kernel/sched.c:1856:
/home/linus/src/linux-trees/linux-2.6/kernel/sched_edf.c: In function
'pick_next_task_edf':
/home/linus/src/linux-trees/linux-2.6/kernel/sched_edf.c:435: error:
implicit declaration of function 'hrtick_enabled'

The hrtick_enabled() function is a static in sched.c, and should be visible
in sched_edf.c since it's #include:ed into sched.c so I'm pretty confused
about this one.

Could it be that I'm using a too bleeding edge compiler? This is a
arm-none-eabi-gcc (Sourcery G++ Lite 2008q3-66) 4.3.2
i.e. a CodeSourcery custom compiler, what are you using for ARM builds
in Pisa?

/home/linus/src/linux-trees/linux-2.6/kernel/sched.c: In function
'__setscheduler_ex':
/home/linus/src/linux-trees/linux-2.6/kernel/sched.c:6318: error:
'struct sched_edf_entity' has no member named 'bw'
/home/linus/src/linux-trees/linux-2.6/kernel/sched.c:6318: error:
implicit declaration of function 'to_ratio'

This is another thing: the code in struct sched_edf_entity only compiles
in the field bw if you have CONFIG_EDF_GROUP_SCHED, but the
code in sched.c __setscheduler_ex() use it no matter whether that's
configured or not.

This patch fixes it.

diff --git a/kernel/sched.c b/kernel/sched.c
index b41fc65..9ce89d4 100644
--- a/kernel/sched.c
+++ b/kernel/sched.c
@@ -6315,8 +6315,10 @@ __setscheduler_ex(struct rq *rq, struct
task_struct *p, int policy,

        edf_se->runtime_max = timespec_to_ns(&param_ex->sched_runtime);
        edf_se->period = timespec_to_ns(&param_ex->sched_period);
+#ifdef CONFIG_EDF_GROUP_SCHED
        edf_se->bw = to_ratio(timespec_to_ns(&param_ex->sched_period),
                              timespec_to_ns(&param_ex->sched_runtime));
+#endif

        edf_se->runtime = edf_se->runtime_max;

Yours,
Linus Walleij
--

From: Linus Walleij
Date: Wednesday, September 23, 2009 - 5:50 am

Nah, no complex explanations... it's just compiled out but still used,
here's another patch:

diff --git a/kernel/sched_edf.c b/kernel/sched_edf.c
index cdec433..198ad6b 100644
--- a/kernel/sched_edf.c
+++ b/kernel/sched_edf.c
@@ -431,9 +431,11 @@ struct task_struct *pick_next_task_edf(struct rq *rq)
        BUG_ON(!edf_se);

        p = edf_task_of(edf_se);
-       p->se.exec_start = rq->clock;
+       p->se.exec_start = rq->clock
+#ifdef CONFIG_SCHED_HRTICK
        if (hrtick_enabled(rq))
                start_hrtick_edf(rq, p);
+#endif

        return p;
 }

Yours,
Linus Walleij
--

From: Raistlin
Date: Wednesday, September 23, 2009 - 6:30 am

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)

iEYEABECAAYFAkq6IusACgkQk4XaBE3IOsT/LgCgl57LDUgYKPwhlgT1feS6hJwa
BVoAn2D777GCqAimHCA2NustKoiWAEi2
=wKfb
-----END PGP SIGNATURE-----
From: roel kluin
Date: Tuesday, September 29, 2009 - 11:15 am

shouldn't the NULL test be moved upwards, to prevent a dereference of
a NULL pointer? Also I notice that `timespec_to_ns(&param_ex->sched_period)'
is called twice, maybe gcc does this but can't we do something like

        if (edf_policy(policy)) {
                if (param_ex == NULL || param_ex->sched_priority != 0)
                        return -EINVAL;
                s64 psp = timespec_to_ns(&param_ex->sched_period);
                if (psp == 0 || psp < timespec_to_ns(&param_ex->sched_runtime))
                        return -EINVAL;
        }

Roel
--

From: Raistlin
Date: Wednesday, September 30, 2009 - 8:59 am

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)

iEYEABECAAYFAkrDgEYACgkQk4XaBE3IOsSkqQCgrCN5GvlT4XQO4BDrR9IxwxzP
jeEAoI77kXq+0hVyqOqct4Ts0GMIciDT
=LTU0
-----END PGP SIGNATURE-----
From: GeunSik Lim
Date: Wednesday, September 23, 2009 - 5:34 pm

Hi Raistlin,

Thank you for challenge to support EDF on Linux 2.6 in private.

You have to modify  git address of schedtool-edf at
http://www.evidence.eu.com/sched_edf.html correctly.

before) git clone git://feanor.sssup.it/sched-tool-edf.git
after   ) git clone git://feanor.sssup.it/schedtool-edf.git

----- http://www.evidence.eu.com/sched_edf.html
---------------------------------
Usage with schedtool

 To easily test SCHED_EDF you can use our modified version of
schedtool as explained below.
For instance, to run a simple yes program with period 100000us and
budget 25000us, just type the following commands:

git clone git://feanor.sssup.it/sched-tool-edf.git * <-- Here, change
to schedtool-edf.git
cd schedtool-edf
make
./schedtool -E -d 100000 -b 25000 -a 0 -e yes > /dev/null &



-- 
Regards,
GeunSik Lim ( Samsung Electronics )
Blog : http://blog.naver.com/invain/
e-Mail: geunsik.lim@samsung.com
           leemgs@gmail.com , leemgs1@gmail.com
--

--

From: Raistlin
Date: Wednesday, September 23, 2009 - 11:08 pm

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)

iEYEABECAAYFAkq7DNMACgkQk4XaBE3IOsSMpgCdFpdFayo7j4lwRtTy91gQJ7eP
KeEAoKQeewX1hZF4IPreC9nzEtyx+aw4
=QSqU
-----END PGP SIGNATURE-----
From: Claudio Scordino
Date: Thursday, September 24, 2009 - 2:11 am

Fixed.

Many thanks,

             Claudio

--