Re: Considerations on sched APIs under RT patch

Bjoern Brandenburg
2010-04-22T18:30:11Z

On Apr 22, 2010, at 12:28 PM, Peter Zijlstra wrote:
> On Thu, 2010-04-22 at 17:40 +0200, Primiano Tucci wrote:
>
>>> Its a well studied
>>> algorithm and even available in commercial SMP operating systems
>>
>> Can you cite me a commercial SMP system that supports
>> multicore/multiprocessor G-EDF?
>
> From: http://www.cs.unc.edu/~anderson/papers/rtlws09.pdf
>
> "Regarding the frequently voiced objections to G-
> EDF’s viability in a “real” system, it should be noted that
> xnu, the kernel underlying Apple’s multimedia-friendly
> OS X, has been relying on G-EDF to support real-time
> applications on multiprocessors for several years [5]."
>
> "[5] Apple Inc. xnu source code.
> http://opensource.apple.com/source/xnu/."

Since that reference is a bit coarse-grained, let me clarify by pointing out the actual implementation.

In particular, if you look at /usr/include/mach/thread_policy.h (on OS X, of course), you'll find:

> /*
> * THREAD_TIME_CONSTRAINT_POLICY:
> *
> * This scheduling mode is for threads which have real time
> * constraints on their execution.
> *
> * Parameters:
> *
> * period: This is the nominal amount of time between separate
> * processing arrivals, specified in absolute time units. A
> * value of 0 indicates that there is no inherent periodicity in
> * the computation.
> *
> * computation: This is the nominal amount of computation
> * time needed during a separate processing arrival, specified
> * in absolute time units.
> *
> * constraint: This is the maximum amount of real time that
> * may elapse from the start of a separate processing arrival
> * to the end of computation for logically correct functioning,
> * specified in absolute time units. Must be (>= computation).
> * Note that latency = (constraint - computation).
> *
> * preemptible: This indicates that the computation may be
> * interrupted, subject to the constraint specified above.
> */
>

I.e., THREAD_TIME_CONSTRAINT_POLICY implements the sporadic task model.

Global EDF is implemented in osfmk/kern/sched_prim.c (line numbers pertain to XNU 1504.3.12):

In line 473:

> /*
> * Calculate deadline for real-time threads.
> */
> if (thread->sched_mode & TH_MODE_REALTIME) {
> thread->realtime.deadline = mach_absolute_time();
> thread->realtime.deadline += thread->realtime.constraint;
> }

Further, in choose_processor() starting at line 26:

> if (thread->sched_pri >= BASEPRI_RTQUEUES) {
> /*
> * For an RT thread, iterate through active processors, first fit.
> */
> processor = (processor_t)queue_first(&cset->active_queue);
> while (!queue_end(&cset->active_queue, (queue_entry_t)processor)) {
> if (thread->sched_pri > processor->current_pri ||
> thread->realtime.deadline < processor->deadline)
> return (processor);

And in thread_setrun() at line 2482:

> if (thread->last_processor != PROCESSOR_NULL) {
> /*
> * Simple (last processor) affinity case.
> */
> processor = thread->last_processor;
> pset = processor->processor_set;
> pset_lock(pset);
>
> /*
> * Choose a different processor in certain cases.
> */
> if (thread->sched_pri >= BASEPRI_RTQUEUES) {
> /*
> * If the processor is executing an RT thread with
> * an earlier deadline, choose another.
> */
> if (thread->sched_pri <= processor->current_pri ||
> thread->realtime.deadline >= processor->deadline)
> processor = choose_processor(pset, PROCESSOR_NULL, thread);
> }
>

This Global EDF implementation might have been inherited from RT Mach, but I'm not sure about that.

In LITMUS^RT [1], we implement Global EDF a bit differently. Instead of iterating over all processors, we keep the processors in a max heap (ordered by deadline, with no RT task == infinity). The xnu variant may be beneficial if you only expect a few RT tasks at any time, whereas ours is based on the assumption that most processors will be scheduling RT tasks most of the time.

- Björn

[1] http://www.cs.unc.edu/~anderson/litmus-rt (The posted patch is horribly out of date; we'll have something more recent based on 2.6.32 up soon.)

---
Björn B. Brandenburg
Ph.D. Candidate
Dept. of Computer Science
University of North Carolina at Chapel Hill