Re: [ECOS] how to implement EDF scheduling in eCos

[Nick Garnett <nickg at ecoscentric dot com>]

Andrew Lunn <andrew@lunn.ch> writes:

> On Thu, Oct 20, 2005 at 06:30:00PM +0530, Sasanka Sarkar wrote:
> > hi
> >     My intention is to implement EDF scheduling in eCos.Currently eCos
> > is having the scheduling like BitMap,Multilevel ,lottery.Exactly the
> > same way I also want to add a new scheduling EDF.Now could anyone tell
> > me how to do it?
> 
> OK. back from googling. Earliest Deadline First.
> 
> What i don't see is how Earliest Deadline First fits a thread
> model. Threads are at the heart of eCos. How can you give a deadline
> to a thread? You have to give a deadline to an event or action. "This
> action must be completed by time X."
> 
> Could you explain this a bit more, how you see EDF and threads combined.

In theory this would be done by making threads wait until their start
time and running an EDF scheduler on the set of available
threads. We even have the start of an EDF API in kapi.h:

/* Deadline scheduling control (optional) */

void cyg_thread_deadline_wait( 
    cyg_tick_count_t    start_time,             /* abs earliest start time   */
    cyg_tick_count_t    run_time,               /* worst case execution time */
    cyg_tick_count_t    deadline                /* absolute deadline         */
) __THROW; 

Any thread calling this will wait until the start_time and then expect
to receive run_time ticks of execution time before the deadline time
is reached. Execution is given to the thread by returning from this
function and it signals the completion of its execution by calling it
again.

However, that function is incomplete. What is missing is any kind of
policing of the values allowed. The scheduler needs to determine that
the requested run_time is available between the start_time and the
deadline and reject the call if it is not. This calculation can be
quite complicated.

Most EDF systems are split into two parts, and off-line analysis tool
that detemines that the schedule is possible, and a runtime scheduler
that simply executes the schedule according to the EDF rules.


So, eCos was designed with the idea that an EDF scheduler was a
possibility. The scheduler is deliberately separate from the basic
thread mechanisms so such a thing could be done. However, as far as
implementing an EDF scheduler in eCos now is concerned, I suspect that
dependencies on having a straightforward prioritized scheduler are a
little too ingrained in the code. It might be possible to get just
the kernel running with EDF, so long as things like mutex priority
inheritance are disabled. Obviously POSIX will not work, and the
TCP/IP stack is unlikely. Other subsystems will probably either work
fine, if they don't do anything with threads, or fail miserably.



-- 
Nick Garnett                                eCos Kernel Architect
http://www.ecoscentric.com           The eCos and RedBoot experts
>>>> Visit us at stand 230 at The Embedded Systems Show 2005 <<<<
>>>> Oct 19-20 NEC, Birmingham, UK http://www.embedded.co.uk <<<<


-- 
Before posting, please read the FAQ: http://ecos.sourceware.org/fom/ecos
and search the list archive: http://ecos.sourceware.org/ml/ecos-discuss