[cgl_discussion] requirements for configurable Round Robin quantum and 1 ms tick

Eric.Chacron at alcatel.fr Eric.Chacron at alcatel.fr
Thu Aug 28 05:42:58 PDT 2003


I have a look on POSIX 1003.1 B.13 appendix on Execution scheduling and it
seems
O(1) RR scheduling policy is not at all POSIX-like as:

1) POSIX specifies that  "the traditional "nice" value does noyt affect the
SCHED_FIFO and SCHED_RR scheduling policies."
2) "realtime processes require that scheduling be fast and deterministic
..."
3) system-wide or process-wide quantum: .. " it appears that the prevailing
realtime practice
is for it to be a system-wide value".

Then if the rule with O(1) is my quantum is in [10 ms, 200 ms ] range
depending on
a) the initial scheduling priority of the process.
b) the nice value of the process.
would it be possible to comply with 1),  2) and 3)  ?

So i would propose adding a requirement at least to have a POSIX like
scheduling policy.

Eric
---------------------- Forwarded by Eric CHACRON/FR/ALCATEL on 08/28/2003
02:20 PM ---------------------------


Eric CHACRON
08/25/2003 04:46 PM

To:    George Anzinger <george at mvista.com>
cc:    cgl_discussion at osdl.org
Subject:    Re: [cgl_discussion] requirements for configurable Round Robin
       quantum and 1 ms tick  (Document link: Eric CHACRON)


>Which "today"?
Right, i used the default native scheduler from Linus in 2.4.18 sources.
But OK, let's switch to O(1) now as it can be used already in 2.4.


>#define MIN 10*HZ/1000
>#define MAX 300*HZ/1000
>
>slice = MIN + (MAX - MIN) * (MAX_PRIO-1-(p->static_prio))/(MAXUSER_PRI-1);

I have extracted from 2.6 :
44 /*
45  * Convert user-nice values [ -20 ... 0 ... 19 ]
46  * to static priority [ MAX_RT_PRIO..MAX_PRIO-1 ],
47  * and back.
48  */
49 #define NICE_TO_PRIO(nice)      (MAX_RT_PRIO + (nice) + 20)
50 #define PRIO_TO_NICE(prio)      ((prio) - MAX_RT_PRIO - 20)
51 #define TASK_NICE(p)            PRIO_TO_NICE((p)->static_prio)

53 /*
54  * 'User priority' is the nice value converted to something we
55  * can work with better when scaling various scheduler parameters,
56  * it's a [ 0 ... 39 ] range.
57  */
58 #define USER_PRIO(p)            ((p)-MAX_RT_PRIO)
59 #define TASK_USER_PRIO(p)       USER_PRIO((p)->static_prio)
60 #define MAX_USER_PRIO           (USER_PRIO(MAX_PRIO))
69 #define MIN_TIMESLICE           ( 10 * HZ / 1000)
70 #define MAX_TIMESLICE           (200 * HZ / 1000)

(4 #ifdef __KERNEL__
5 # define HZ             1000            /* Internal kernel timer frequency */
6 # define USER_HZ        100             /* .. some user interfaces are in "ticks" */
7 # define CLOCKS_PER_SEC (USER_HZ)       /* like times() */
8 #endif)

101  * Ie. nice +19 tasks can never get 'interactive' enough to be
102  * reinserted into the active array. And only heavily CPU-hog nice -20
103  * tasks will be expired. Default nice 0 tasks are somewhere between,
104  * it takes some effort for them to get interactive, but it's not
105  * too hard.
106  */
107

115 #define TASK_INTERACTIVE(p) \
116         ((p)->prio <= (p)->static_prio - DELTA(p))
117
/*
119  * BASE_TIMESLICE scales user-nice values [ -20 ... 19 ]
120  * to time slice values.
121  *
122  * The higher a thread's priority, the bigger timeslices
123  * it gets during one round of execution. But even the lowest
124  * priority thread gets MIN_TIMESLICE worth of execution time.
125  *
126  * task_timeslice() is the interface that is used by the scheduler.
127  */
128
129 #define BASE_TIMESLICE(p) (MIN_TIMESLICE + \
130         ((MAX_TIMESLICE - MIN_TIMESLICE) * (MAX_PRIO-1-(p)->static_prio)
/(MAX_USER_PRIO - 1)))

132 static inline unsigned int task_timeslice(task_t *p)
133 {
134         return BASE_TIMESLICE(p);
135 }

278
279 #define MAX_USER_RT_PRIO        100
280 #define MAX_RT_PRIO             MAX_USER_RT_PRIO
281
282 #define MAX_PRIO                (MAX_RT_PRIO + 40)


>The key is that p->static_prio is set by the nice call, so it is not a
>fixed interval at all, AND it seems to be independent of the actual
>rt-priority.

177   void scheduler_tick(...

1220         if (unlikely(rt_task(p))) {
1221                 /*
1222                  * RR tasks need a special form of timeslice management.
1223                  * FIFO tasks have no timeslices.
1224                  */
1225                 if ((p->policy == SCHED_RR) && !--p->time_slice) {  ##########################
1226                         p->time_slice = task_timeslice(p);
1227                         p->first_time_slice = 0;
1228                         set_tsk_need_resched(p);
1229
1230                         /* put it at the end of the queue: */
1231                         dequeue_task(p, rq->active);
1232                         enqueue_task(p, rq->active);
1233                 }
1234                 goto out_unlock;
1235         }
1236         if (!--p->time_slice) {                                    ##########################
1237                 dequeue_task(p, rq->active);
1238                 set_tsk_need_resched(p);
1239                 p->prio = effective_prio(p);
1240                 p->time_slice = task_timeslice(p);
1241                 p->first_time_slice = 0;
1242
1243                 if (!TASK_INTERACTIVE(p) || EXPIRED_STARVING(rq)) {
1244                         if (!rq->expired_timestamp)
1245                                 rq->expired_timestamp = jiffies;
1246                         enqueue_task(p, rq->expired);
1247                 } else
1248                         enqueue_task(p, rq->active);
1249         }

63 #define INIT_TASK(tsk)  \
64 {                                                                       \
...
70         .prio           = MAX_PRIO-20,                                  \
71         .static_prio    = MAX_PRIO-20,                                  \  ##########################

>I haven't done all the math, but, it seems clear that the min. slice
>is 10ms.  If MAX is right, it would seem that the max is 200ms.

Ok for the min (for a maximum stat_prio) , but let's take the mean value
too:
i think it is 100 ms if i use MAX_PRIO -20 for static_prio.
And for the max the function will return:  20 ==> 200 ms that's OK.


>What, I think, needs to be exported is some info on just what slice
>you get given a particular nice value.

Yes that will be good to have the function with x= nice , y = slice on a
drawing.

So if i try to summarize with O(1):
1) the RR quantum is whithin : [10ms, 200ms] using whatever a 10 ms or 1 ms
tick.
2) the RR quantum mean value could be 100 ms ( to be confirmed by you)
3) the quantum changes upon nice request .

"My requirement" now is to have a fine grain static quantum for RT application
that needs let say to schedule every 10 or 1 ms using RR class.
It's different than the current implementation.

>The 2.6 kernel is doing this.  It is not an easy thing to do if its to
>be done correctly.  There are very real issues with the PIT interrupt
>source not being able to hit the 1ms mark with enough precision to
>satisfy ntp requirements.

Ok, that's a good point to be explored. But the min quantum in that implementation
seems to mee to remain equal to 10 ms.  Why not 1 ms ?

>> Is'it compatible with kernel maximum latency ? ( remenber that some
>> application runs whithout any disk and without
>> related sources of latency like fork+ exec ...)
>
>I suspect that it has little to do with latency, save for the effect
>on the cache of the interrupts.

Maybe for implemntation point of view this has little to do.
But imagine you want 1 ms quantum for a set of threads, and your
application
relies on that scheduling for RT purpose. Then you would like too
to have no latency of several ms in that case.





George Anzinger <george at mvista.com> on 08/21/2003 06:56:11 AM

To:    Eric CHACRON/FR/ALCATEL at ALCATEL
cc:    cgl_discussion at osdl.org
Subject:    Re: [cgl_discussion] requirements for configurable Round Robin
       quantum and 1 ms tick


Eric.Chacron at alcatel.fr wrote:
> Today some applications need to use Real Time process with Round Robin
> policy.
>
> Today the quantum seems to be defined by a constant value as 20 x the
tick
> value.

Which "today"?  In the O(1) scheduler the slice (in ticks) is define
something like this:

#define MIN 10*HZ/1000
#define MAX 300*HZ/1000

slice = MIN + (MAX - MIN) * (MAX_PRIO-1-(p->static_prio))/(MAXUSER_PRI-1);

(say that 10 times quickly :)

The key is that p->static_prio is set by the nice call, so it is not a
fixed interval at all, AND it seems to be independent of the actual
rt-priority.

I haven't done all the math, but, it seems clear that the min. slice
is 10ms.  If MAX is right, it would seem that the max is 200ms.

What, I think, needs to be exported is some info on just what slice
you get given a particular nice value.


> Then if i use a 10ms tick the quantum is equal to 200 ms. This seems too
> large.
>
> A second requirement could be to enable a 1 ms tick period for the timer
> interrupt on Intel Pentium architectures.

The 2.6 kernel is doing this.  It is not an easy thing to do if its to
be done correctly.  There are very real issues with the PIT interrupt
source not being able to hit the 1ms mark with enough precision to
satisfy ntp requirements.

> Is'it compatible with kernel maximum latency ? ( remenber that some
> application runs whithout any disk and without
> related sources of latency like fork+ exec ...)

I suspect that it has little to do with latency, save for the effect
on the cache of the interrupts.
>
> I would like to have the feed-back from everyone who's interrested in the
> question and also from Montavista
> as ther could be some link with low latency and RT scheduler for the
second
> point.

--
George Anzinger   george at mvista.com
High-res-timers:  http://sourceforge.net/projects/high-res-timers/
Preemption patch: http://www.kernel.org/pub/linux/kernel/people/rml












More information about the cgl_discussion mailing list