Participation in GSoC 2016

Darshit Shah darnir at
Thu Mar 10 11:13:57 UTC 2016


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 

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
>+ Update the scheduling simulator since it is a lot easier to test using
>   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 
>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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: not available
URL: <>

More information about the devel mailing list