[Click] CPU scheduling -> make elements interruptable.

[Beyers Cronje]

Interesting subject. As Roman pointed out each scheduled task will run
through the entire push/pull path before it returns and would probably take
some effort to implement timeslices with task interruption support.

The following is just a thought and might not be a viable option. One way to
do this would probably be between push()/pull() calls. Have an intermediate
function (lets call it prePush() ) per element that's executed before each
element's push() function. prePush() can then check if the allocated
forwarding path has exceeded it's timeslice. If it has it will store a
global pointer for this push/pull path and return without continuing,
effectively ending the scheduled task. Once the task is scheduled again it
can either continue where it left off using this global pointer, or start a
new push/pull process. The reason for prePush will make life easier updating
existing element code.

To illustrate:

Operation now:
Element1::run_task() -> Element2::push() -> Element3::push() .....

Proposed:
Element1::run_task() -> Element2::prepush() -> Element2::push() ->
Element3::prepush() -> Element3::push() ......

Say timeslice ends in Element3::prepush() the the next task schedule path
will look like this:
Element1::run_task() -> Element3::prepush() -> Element3::push() ......

Beyers

On 6/28/07, Roman Chertov <rchertov at purdue.edu> wrote:
>
> In Click you have one or more threads of execution.  Most of the
> elements in Click are agnostic and do not generate any tasks themselves.
>   When an element like a Queue/PollDevice/ToDevice schedules a task and
> a packet is available, then this task will run through the entire chain
> of elements until it gets into another Queue/PollDevice/ToDevice
> element.  (Click SMP paper). So in order to what you are proposing, you
> would have to interrupt a Click thread in the middle of execution of
> some task and then to start a new one.  (obviously you have to remember
> the state so that you can come back).  I don't think this would be easy
> to do, as I don't think the executing threads (RouterThread) are
> designed to be interrupted.
>
> Hopefully Eddie will shine more light on this.
>
> Roman
>
> Egi, Norbert wrote:
> > Hi,
> >
> > We are using Click for desinging a shared forwarding engine with
> separate forwarding paths (chain of elements) per customer. The customers
> share all the NICs, so after the packets are polled out from the NIC's queue
> a Classifier demultiplexes them by emitting them to the proper forwarding
> path. Our intention is to provide a fair CPU scheduling for each of the
> forwarding paths. The stride scheduling algorithm, implemented in Click,
> would be a perfect solution for our problem, but after checking the source
> code and the available documents I found out that the algorithm hasn't been
> implemented completely as it was proposed. If I understand it correctly from
> the source and its comments, there is no such thing like "quantums" (i.e.
> a discrete time slice when the scheduled task is entitled to use the CPU)
> and I guess that's the main reason while the operation of the elements can
> not be interrupted.
> >
> > In the first comment of lib/task.cc it's mentioned that this may be
> addressed in the future, so I was wondering whether anyone is working on it
> and I may jump in and help or just could someone provide information on how
> to make elements interruptable the fastest way extending the current version
> of the code.
> >
> > Regards,
> > Norbert
> >
> > _______________________________________________
> > click mailing list
> > click at amsterdam.lcs.mit.edu
> > https://amsterdam.lcs.mit.edu/mailman/listinfo/click
> >
>
> _______________________________________________
> click mailing list
> click at amsterdam.lcs.mit.edu
> https://amsterdam.lcs.mit.edu/mailman/listinfo/click
>