<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<div class="moz-cite-prefix">On 4/25/2013 9:26 AM, yangwei weiyang
wrote:<br>
</div>
<blockquote
cite="mid:CALZ8wmrVvUMw6KsLGrovWpNUN4BO-YHXMFckJxUnEt+NnY9hpg@mail.gmail.com"
type="cite">
<div dir="ltr"><br>
<div class="gmail_extra">
<div class="gmail_quote">2013/4/25 Pavel Pisa <span dir="ltr"><<a
moz-do-not-send="true"
href="mailto:ppisa4lists@pikron.com" target="_blank">ppisa4lists@pikron.com</a>></span><br>
<blockquote class="gmail_quote" style="margin:0pt 0pt 0pt
0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex">
Hello Deng Hengyi,<br>
<div class="im"><br>
On Thursday 25 April 2013 07:27:20 wei.a.yang wrote:<br>
> Hi, Pavel. Thank you for your advice. And in my
former mail my proposal is<br>
> very similar with the mechanism in the Linux. But
the different is that I<br>
> use two min-heap instead of two plist because of
good algorithm complexity<br>
> of min-heap.<br>
<br>
</div>
It worth to evaluate what is better algorithm - RB-tree or
min-heap.<br>
RB tree allows to use "static" nodes which are part of the
task<br>
structure. The classic array base heap tree with 2n and
2n+1 children<br>
requires per queue array allocation and result in the
limited/compile<br>
time defined depth or requires reallocations. But may it
be you have<br>
other algorithm on mind.<br>
<div class="im"><br>
</div>
</blockquote>
<div>Yeah, now in my opinion the algorithm <span
id="result_box" class="" lang="en"><span class="">candidates
are RB tree and min-heap.<br>
</span></span></div>
<div><span id="result_box" class="" lang="en"><span class="">But
just as you said the disadvantage of min-heap is its
size allocation. So i will<br>
</span></span></div>
<div><span id="result_box" class="" lang="en"><span class="">evalutate
the two and select a more suitable for RTEMS. If you
have any more <br>
</span></span></div>
<div><span id="result_box" class="" lang="en"><span class="">better
way please comment freely.<br>
<br>
</span></span></div>
</div>
</div>
</div>
</blockquote>
Gedare and I have been discussing the idea of Thread Sets which are<br>
ordered by priority. We currently have three implementations of this<br>
functionality in RTEMS:<br>
<br>
+ Deterministic Priority Scheduler's bitmaps and FIFO set<br>
+ Simple Priority Scheduler single list<br>
+ Thread Queue Priority Blocking Block2N structure<br>
<br>
I would like to see these all use "classes" which implement the
Thread Set.<br>
The choice of which algorithm to use is determined by O(space) and
O(time).<br>
The decision can vary based on use case in RTEMS or application
requirements. <br>
<br>
If we need another set managed by another structure, that is fine.
But I<br>
think this set of helper classes is important to have. <br>
<br>
<blockquote
cite="mid:CALZ8wmrVvUMw6KsLGrovWpNUN4BO-YHXMFckJxUnEt+NnY9hpg@mail.gmail.com"
type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div> </div>
<blockquote class="gmail_quote" style="margin:0pt 0pt 0pt
0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex">
<div class="im">
> > I have done some testing of RTEMS and Linux PI
implementations.<br>
> > You can find my test code cor RTEMS classic
API<br>
> > and POSIX RTEMS and Linux in the repo<br>
><br>
> Good work. But I want to know the mechanism of
RTEMS test. You know there<br>
> are two PI algorithms in RTEMS. One is used by
default, the other one<br>
> should define __RTEMS_STRICT_ORDER_MUTEX__ to use
it. You test two<br>
> algorithms all?<br>
<br>
</div>
I have tested default one. The
__RTEMS_STRICT_ORDER_MUTEX__ should<br>
behave as expected but there is risk that some code/libray
we use<br>
does not access mutexes in the strict LIFO order.<br>
<br>
Best wishes,<br>
<br>
Pavel<br>
</blockquote>
</div>
<br>
<br clear="all">
<br>
-- <br>
Wei Yang<br>
Best Regards<br>
<br>
wei.a.yang at <a moz-do-not-send="true"
href="http://gmail.com" target="_blank">gmail.com</a> <br>
<br>
</div>
</div>
</blockquote>
<br>
<br>
<pre class="moz-signature" cols="72">--
Joel Sherrill, Ph.D. Director of Research & Development
<a class="moz-txt-link-abbreviated" href="mailto:joel.sherrill@OARcorp.com">joel.sherrill@OARcorp.com</a> On-Line Applications Research
Ask me about RTEMS: a free RTOS Huntsville AL 35805
Support Available (256) 722-9985 </pre>
</body>
</html>