<html><head><meta http-equiv="Content-Type" content="text/html charset=GB2312"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">Hi all, <div><br></div><div>About this issue there is a mail [1] which explains very clearly. Here i just give its basic background:</div><div><br></div><div>In RTEMS it implement two priority-inheritance algorithm, one is : the priority of inheritance task is not lowered until all the lock release which is used by default in RTEMS, the other one is : the priority of inheritance task is lowered in stack style when it release a lock which is implemented in RTEMS but not test. </div><div><br></div><div>The implementation of the later one have a restrict that the order of lock and unlock must be FILO, if not there will be some problem(by default the kernel will post some error). Actually this is not a general implementation and correct behavior of priority inherence. The correct way is that whenever the lock inherence is released the priority of the thread held lock should be set to the highest priority of the thread of remain held lock. And [1] also talk about the algorithmic complexity of the possible general implementation. Its summary is listed in the wiki [2]. </div><div><br></div><div>But in my option there is also a alternative method to implement the general algorithmic with O(log(n) ) and the size of usage is also acceptable. The data struct can use heap-sort to implement a priority-queuing with insert and delete O(log(n)) and min O(1). And then we can define the maximum depth of lock acquiring and maximum thread waiting for one lock. So that its size also can be reduce to a acceptable range. In this implementation two heap should be maintained: </div><div>1. one heap to store the list of threads that are blocked on a mutex, the highest priority thread can be find with O(1).</div><div>2. the other heap to store the highest priority threads waiting on one of the muteness that a specific process owns. </div><div><br></div><div>If a inherence mutex is released the highest priority threads among the second heap can be find easily. </div><div><br></div><div>This is just my preliminary ideas, if you have any comment please add freely. </div><div><br></div><div><br></div><div><br></div><div>1. <a href="http://www.rtems.com/ml/rtems-users/2009/may/msg00093.html">http://www.rtems.com/ml/rtems-users/2009/may/msg00093.html</a></div><div>2. <a href="http://www.rtems.org/wiki/index.php/RTEMS_Algorithmic_Complexity">http://www.rtems.org/wiki/index.php/RTEMS_Algorithmic_Complexity</a></div><div><br></div><div><br></div><div>在 2013-4-18，下午4:23，wei.a.yang <<a href="mailto:wei.a.yang@gmail.com">wei.a.yang@gmail.com</a>> 写道：<div><br class="Apple-interchange-newline"><blockquote type="cite"><meta http-equiv="content-type" content="text/html; charset=utf-8"><div dir="auto"><div><br></div><div>在 2013-4-18，11:54，Xi Yang <<a href="mailto:hiyangxi@gmail.com">hiyangxi@gmail.com</a>> 写道：<br><br></div><blockquote type="cite"><div dir="ltr">Hi Wei,<div><br></div><div style="">Sorry for late reply. </div><div style=""><br></div><div style=""><br></div><div><div class="gmail_extra"><div class="gmail_quote">On 17 April 2013 20:01, wei.a.yang <span dir="ltr"><<a href="mailto:wei.a.yang@gmail.com" target="_blank">wei.a.yang@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; position: static; z-index: auto; ">Hi all,<br>
<br>
My understand is that in RTEMS it implement two priority-inheritance algorithm, one is : the priority of inheritance task is not lowered until all the lock release which is used by default in RTEMS, the other one is : the priority of inheritance task is lowered in stack style when it release a lock which is implemented in RTEMS but not test.<br>
</blockquote><div><br></div><div style="">Yes, you are right. The strict order mutex is the one I implemented 6 years ago, and the implementation was wrong...</div><div><br></div><div> </div></div></div></div></div></blockquote>Hi Xi, thanks for your reply. And could you point where the implementation is wrong or any reference and example, if you know how to correct it that will be better. <br><blockquote type="cite"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; position: static; z-index: auto; ">
<br>
And the priority inheritance algorithm do not solved the deadlock automatically. So in the implement of stack priority inheritance define to avoid the deadlock situation. Is my understand right?<br>
</blockquote><div><br></div><div style="">No. The goal of STRICT ORDER MUTEX was to improve the scheduling. For example, task T1's priority is A, it gets two mutexs (M1, M2), and its priority is improved to B(after M1), then to C(after M2). By default, after T1 release M2, RTEMS does not change T1's priority, so T1 is keeping working on priority M2, which is not fair for other tasks.</div>
<div style=""><br></div><div style="">However, because STRICT ORDER MUTEX requires the application to acquire/release locks in FILO order, it may help applications to avoid the deadlock. But it was not designer for avoiding deadlock.</div>
<div style=""><br></div></div></div></div></blockquote>Yeah I know your mean. If the order is wrong it will return err and tell the app the order is wrong but it will not solve the deadlock.<div><br><blockquote type="cite"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div style="">Regards.</div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
在 2013-4-17，0:00，Joel Sherrill <<a href="mailto:joel.sherrill@oarcorp.com">joel.sherrill@oarcorp.com</a>> 写道：<br>
<br>
> Hi<br>
><br>
> Tthe first link I found was this:<br>
><br>
> <a href="http://stackoverflow.com/questions/108098/how-does-vxworks-deal-with-priority-inheritance" target="_blank">http://stackoverflow.com/questions/108098/how-does-vxworks-deal-with-priority-inheritance</a><br>
><br>
> Which explains the problem very well and how VxWorks changed<br>
> from the algorithm both RTEMS and VxWorks used to a stack<br>
> kind of algorithm.<br>
><br>
> I want RTEMS to have both and default to more correct.<br>
><br>
> The RTEMS code is ifdef'ed on __RTEMS_STRICT_ORDER_MUTEX__<br>
> and there really isn't a lot of code.<br>
<span class="HOEnZb"><font color="#888888">><br>
> --<br>
> Joel Sherrill, Ph.D. Director of Research & Development<br>
> <a href="mailto:joel.sherrill@OARcorp.com">joel.sherrill@OARcorp.com</a> On-Line Applications Research<br>
> Ask me about RTEMS: a free RTOS Huntsville AL 35805<br>
> Support Available (256) 722-9985<br>
><br>
</font></span></blockquote></div><br></div></div>
</blockquote></div></div></blockquote></div><br></div></body></html>