[prev in list] [next in list] [prev in thread] [next in thread]
List: linux-rt
Subject: [rtl] Some ideas to improve the scheduler performance.
From: Ismael Ripoll <iripoll () disca ! upv ! es>
Date: 1998-12-23 9:43:03
[Download RAW message or body]
maryam moghaddas wrote:
>
> Hi
> Thanx for replying me back and being so concerned.
>
> I will go through what I have done on my project. I hope I'll be clear. If
> you have more questions please let me know.
>
> The two schedulers which were originally with the OS were the ones provided
> by Mr. Ripoll and Mr. Barabanov. Those two are periodic and event driven.
> The scheduler was preemptive too. What I wanted to test was something
> simpler, a non-preemptive bursty EDF scheduler. So it was possible that a
> group of tasks arrive all together or in a very short period of time.
> Based on this assumption I tried to wrote and tested to schemes for the
> scheduler: A task-based scheduler and a batch based scheduler.
> A task based scheduler is when the scheduler chooses a task as the best
> choice of EDF, it starts execution until completion( since it's non
> preemptive). After the task's execution is finished, the scheduler will
> check for task arrivals, if yes it will adds to the list of the tasks
> waiting for execution(batch) and apply EDF to the list(batch).;Otherwise it
> will chose the best EDF from that list
> (batch).
> In the batch based scheduler, the scheduler will not look for any new task
> arrivals until all the tasks in the batch have been executed. Of course the
> tasks are chosen for execution with EDF scheme. Mean while the tasks in the
> batch are executed it's possible that other tasks have been arrived. So
> that batch will start being executed after the previous one is finished.
> In both schemes above alot of time is spent on search for the best EDF
> choice.
> Then I decided to modify the schemes by sorting the batches. So the tasks
> will be inserted in on order to the batch upon arrival. In this case all
> the batches are sorted based on their deadlines on descending order and
> there is no need for search anymore.
> This had a great improvement on the scheduling.
> The schedulers were tested for set of 500 tasks and 1000 tasks, with
> different slack factors. And some neat results were obtained from the
> tests.
>
> Happy new year,
> I am looking forward to hear more from you...
> Maryam
>
> ----------
> > From: Jose Contreras <jcontrer@if.insa-lyon.fr>
> > To: maryam moghaddas <mshsaint@direct.ca>
> > Subject: Re: [rtl] A realtime project proposal
> > Date: 16 December 1998 01:30
> >
> > Hi Maryam,
> >
> > could you give more information on the EDF scheduler you developped? A
> > report, your memoire, something like that. Meme si le document est en
> > francais.
> >
> > I do my doctoral program at INSA de Lyon, at the Laboratoire
> > d'Ingenierie de l'Informatique Industrielle, and we are working on a
> > reflective architecture where scheduling is a key activity.
> >
> > I will comment your message with my prof, next friday.
> >
> > Keep in touch!
> >
> > Jose
> --- [rtl] ---
> To unsubscribe:
> echo "unsubscribe rtl" | mail majordomo@rtlinux.cs.nmt.edu OR
> echo "unsubscribe rtl <Your_email>" | mail majordomo@rtlinux.cs.nmt.edu
> ----
> For more information on Real-Time Linux see:
> http://www.rtlinux.org/~rtlinux/
Hi!:
Some ideas to improve the scheduler performance.
If there are a lot of tasks (it depends,.. but let's say more than 20)
then the implementation of the schedulers (static-prio and dynamic-prio)
is not efficient. In this case, each call to the scheduling function
takes O(n) operations (where "n" is the number of tasks)...
I know three possible implementations of a scheduler:
(1) An array of tasks and each time the scheduler is called the whole
array is consulted to find the next task (the task with the
closest deadline). Its computations cost is: O(n).
(2) Tasks are always keep in order of deadline (or priority).
The cost is: O(n*log(n))
(3) There are two operations to be performed at each scheduling point:
a) New tasks may be ready.
b) A winner task has to be selected (closest deadline).
There is a data structure that can be used to perform this
operations
very efficiently: The HEAP.
A heap is an ordered binary tree implemented inside a vector...
it is very easy to implement and the best is:
O(log(n)) To push (insert) an new element, i.e. a task into the active
queue.
O(1) To pop the task with the closets deadline.
Another heap can also be used to find the next preemption time.
Some time ago I used a heap to implement a EDF and RM simulator
to do extensive simulations...
A very ugly (dirty code) implementation of such schedulers in a
simulator tool can be found in:
http://bernia.disca.upv.es/~iripoll/publicaciones/research.html
Best regards.
--
Ismael Ripoll:
Universitat Politecnica de Valencia; Apdo 22012, 46071 Valencia, Spain
mailto:iripoll@disca.upv.es http://bernia.disca.upv.es/~iripoll
Tel: +34 6 3879 577 Fax: +34 6 3877 579
------------------------------------------------------------------------
* Hiroshima 45, Chernobyl 86, Winbugs 95. (What's next ?... Windogs 98
?)
* In an open world without walls and fences who needs Windows and Gates?
-----------------
--- [rtl] ---
To unsubscribe:
echo "unsubscribe rtl" | mail majordomo@rtlinux.cs.nmt.edu OR
echo "unsubscribe rtl <Your_email>" | mail majordomo@rtlinux.cs.nmt.edu
----
For more information on Real-Time Linux see:
http://www.rtlinux.org/~rtlinux/
[prev in list] [next in list] [prev in thread] [next in thread]