Results

[Gedare Bloom]

Since this thread got migrated to devel a bit prematurely, I'll
back-stop some of the details and how I understand the state of this
project.

Saurabh is working toward solving https://devel.rtems.org/ticket/2124
(so yes there is a ticket already, and it  should be referenced by
patches accordingly). As a first step he has proposed a modified way
to step-down inherited priorities when multiple mutexes are acquired
simultaneously by one thread and contended by others, i.e. nested
mutex access. We wanted assurance the proposal is sound, so we had him
implement a model of the current thread synchronization of RTEMS
within a Java-based model-checking framework, called Java Path Finder,
or JPF. His model shows the existing error with the current
STRICT_ORDER option, and then does not show a problem using his
proposed method for solving nested mutex acquisition.

However, validating the proposed method apparently required adding a
global lock around the two linked lists that are used in Saurabh's
proposed solution. My intuition is that the global lock to protect
these lists is not a big problem for uniprocessor, and for SMP we
should prefer to find other solutions at any rate. The lists should
not be long, and we should be able to find their bounds. One list is
bounded by the number of mutexes a thread may hold, and the other by
the number of threads that may contend a specific mutex.

Saurabh et al, please correct me if I got the above wrong!
-Gedare

On Fri, Jun 26, 2015 at 2:33 AM, Sebastian Huber
<sebastian.huber at embedded-brains.de> wrote:
>
>
> On 26/06/15 02:33, Saurabh Gadia wrote:
>>
>> @joel: It essentially means finding out the highest priority thread (or
>> ceiling) of any remaining mutex held, right?
>> If you are talking this in context of nested mutex problem --->
>> We never go and find the highest priority thread waiting on held mutex.
>> Inversely highest priority thread will recursively make changes to top of
>> stack of held mutexes by the holder. We don't search.
>>
>> Thanks,
>>
>> Saurabh Gadia
>>
>> On Thu, Jun 25, 2015 at 5:27 PM, Joel Sherrill <joel.sherrill at oarcorp.com
>> <mailto:joel.sherrill at oarcorp.com>> wrote:
>>
>>
>>
>>     On June 25, 2015 7:23:06 PM CDT, Cyrille Artho
>>     <cyrille.artho at gmail.com <mailto:cyrille.artho at gmail.com>> wrote:
>>
> [...]
>>
>>
>>     >(2) Is a fix using a global lock acceptable? Correctness-wise
>>     it's the
>>     >safest thing, but of course performance-wise it's a bottleneck.
>>
> [...]
>
> If you use the global lock for the uncontested mutex case, then this is not
> acceptable. If you use a global lock once you must block, then it might be
> acceptable, but this solution is not scalable. I am not sure what you are
> actually working on, it would be nice to discuss and present more on this
> mailing list. Maybe even open a ticket, e.g. something similar to
> https://devel.rtems.org/ticket/2271. This way it is possible to relate
> commits to a general concept discussion.
>
> For SMP there is a ready to use locking protocol capable to replace the
> priority inheritance mutexes:
>
> @inproceedings{OMIP,
>   author="Brandenburg, Björn B.",
>   title="A Fully Preemptive Multiprocessor Semaphore Protocol for
> Latency-Sensitive Real-Time Applications",
>   booktitle="Proceedings of the 25th Euromicro Conference on Real-Time
> Systems (ECRTS 2013)",
>   pages="292-302",
>   year="2013",
>   url="http://www.mpi-sws.org/~bbb/papers/pdf/ecrts13b.pdf",
> }
>
> Implementing support for nested resources is very complex if you don't
> simplify like it was done for the current priority inheritance protocol in
> RTEMS. If you want it more general, then you have to pay for this in terms
> of additional memory space and time. The big issue is that you have to merge
> and split dependency trees. A tree merge can be done in O(log(n)) with a
> binomial heap, but the split operation will be probably not better than
> O(n). On SMP with partitioned/clustered scheduling you have to keep in mind
> that priority values of different partitions are not comparable.
>
> --
> Sebastian Huber, embedded brains GmbH
>
> Address : Dornierstr. 4, D-82178 Puchheim, Germany
> Phone   : +49 89 189 47 41-16
> Fax     : +49 89 189 47 41-09
> E-Mail  : sebastian.huber at embedded-brains.de
> PGP     : Public key available on request.
>
> Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.
>
> _______________________________________________
> devel mailing list
> devel at rtems.org
> http://lists.rtems.org/mailman/listinfo/devel