On Apr 22, 2010, at 12:28 PM, Peter Zijlstra wrote:
quoted text
> 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:

quoted text
> /*
>  * 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:

quoted text
> 	/*
> 	 * 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:

quoted text
> 		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:

quoted text
> 		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
http://www.cs.unc.edu/~bbb




--
unsubscribe notice
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/