Participation in GSoC 2016

Gedare Bloom gedare at
Thu Mar 10 14:25:41 UTC 2016

Joel might answer about the state of the scheduling simulator.

I believe you eventually have to copy-paste your application into a
form, so it is better if you stick to plain text. I don't even know if
you can put images in. You may optionally link to a generated PDF,

On Thu, Mar 10, 2016 at 6:13 AM, Darshit Shah <darnir at> wrote:
> Hi,
> I've been a little busy with my semester end exams and other things
> recently. But I have spent time looking into the RTEMS Priority Scheduler
> with Processor Affinities and the paper mentioned in the trac ticket.
> At this point, I have a decent understanding of the paper and its algorithm
> and am looking into how we may implement it in RTEMS. To this end, I am
> looking for help / guidance.
>> This would be a good project. I would add a few steps to simply
>> implementing
>> it.
>> + Update the scheduling simulator since it is a lot easier to test using
>> that.
>>   It is also easier to ensure you keep the same behavior.
> This sounds like it would be in important part of the implementation of the
> paper. However, I do not know anything about the existing scheduling
> simulator. Any links to this and basic pointers on how I should go about
> extending it would be a great start. I'll incorporate this into my draft
> proposal as soon as I have a better idea of what needs to be done.
>> + Propose criteria for knowing if the new algorithm is really better for
>>   RTEMS than the old one. Evaluating algorithms for RTEMS use involves
>>   big-O of the algorithm, data space requirements (and big-O of that),
>>   global knowledge required, and maybe other factors.
> The new algorithm is almost definitely worse in time and space than the
> existing algorithm. Based on a preliminary analysis, it will be able to use
> the existing Priority Affinity Scheduler for the most part and add a O(|E|)
> complexity to each thread blocking and unblocking operation.  Here, E is the
> set of all processor affinity assignments, so it will approximately add an
> extra linear increase in scheduling overhead w.r.t.  the number of processes
> that use this scheduler.
> I haven't specifically looked into the space requirements, but it will be
> worse than the existing scheduler.
> However, the point to realize is that after these changes, more user
> programs that set processor affinities will be able to meet their deadlines
> as compared to the existing scheduler. This should happen despite the higher
> scheduling overheads.
>> + Testing on scheduling simulator and in RTEMS testsuite to ensure
>>   it is functionally identical to the current algorithm.
> Once again, some pointers tot he scheduling simulator would help me a lot.
>> If the algorithm is functionally identical to the current one and superior
>> in execution time/data requirements, then replacing it is a no brainer.
>> If there are trade-offs on when one is better than the other in real life,
>> then we will all have to characterize those.
> I was thinking more along the lines of writing a new scheduler instead of
> replacing the existing one. A PriorityStringAPA scheduler that pretty much
> reuses all the existing priority affinity scheduler code apart from the two
> operations. This is because, with some task sets where the affinity
> assignments are not too restrictive, the lower overheads of the existing
> scheduler may be preferred over the new one.
> I have also been writing my draft proposal for GSoC. A version is currently
> available on GDrive and a link has been put on on the student tracking page.
> However, I wanted to ask if sharing a PDF of the proposal would be possible.
> Since, I would be more comfortable in making the entire proposal in Latex
> and sharing the final PDF. If not, I can keep working on the proposal in
> Google Docs.
> --
> Thanking You,
> Darshit Shah

More information about the devel mailing list