On 11/09/15 02:25, Cyrille Artho wrote:
Dear all,
Please let me try to clarify:
1. Our understanding so far was that upon lock release, the priority
instantly gets reverted back to the previous priority. This also
applies for nested locks, i.e., a higher priority gets reverted
(stepwise) when releasing locks and does NOT persist until the last
lock is released.
Yes.
2. The current implementation relies on ordering but could perhaps be
changed, although this would require some time. The time needed to
verify the model would also increase substantially because unordered
locking creates a lot of new possibilities. (It could take several
days to verify a reasonable subset of all behaviors on multiple
cores.)
Unfortunately we have unordered mutex usage, e.g. in Newlib.
3. We have a working SMP implementation but it is very complex. It
either has to use a lot of different locks or a global lock for some
of the code. We were not able to eliminate any locks (the model shows
that data races result if we try), so the current algorithm seems to
be very complex for a multi-processor setting.
I think with the thread lock it will be moderately easy to implement.
Its certainly not done in two weeks.
Other points:
4. We could add deadlock detection but it does NOT automatically come
with horizontal nesting (acquiring multiple locks). When acquiring
multiple locks, we check the availability of the next lock, but we do
not go down the entire lock chain. This could be implemented but would
cause additional overhead.
The general case deadlock detection is optional from my point of view,
but at operating system level (SMP locks) there must not be a deadlock.
5. Timeout is currently not supported but could be implemented
relatively easily, although it would again take time to verify the
change.
Timeouts may complicate the things a lot. I tried to get rid of them,
but they were desired by the community.
6. We could try to build a specialized data race detector RTEMS, to
show a data race in a version that uses too few locks. However,
building a data race detector that gives useful diagnostic information
takes some time. Adding data race detection that just outputs "data
race" when the common lock set is empty, is easier.
On Fri, Sep 11, 2015 at 9:14 AM, Saurabh Gadia <ga...@usc.edu> wrote:
Hi Sebastian,
Sorry for late reply. I was out of town and could not reply. I am bit
confused with above description which I need to get clarified:
1. replaced LIFO with sorted list: I don't change the mutex order to make
the list sorted. Instead I promote the priorities so that we don't need to
change position of mutex in the chain and the list without any swapping of
mutex in chain becomes sorted and valid.
2. I was confused with spsem03 test cases. So I created spsem04 test case
which demonstrates that our implementation supports horizontal
implementation. It has the same scenario of test case 3 but now we can say
that horizontal nesting works correctly. you can find all description about
this test cases on link below.
https://docs.google.com/document/d/1RM427RKSoyrZrchEcDIx4etmtWqrFArzRRLWqcU8RK0/edit?usp=sharing
3. Your mentioned example is definitely supported by the our implementation.
I also need clarification on ticket 2412:
1. Is there something wrong with problem description?
it says - "The allocator mutex is already owned, so the priority of the
low priority thread is raised to the priority of the high priority thread.
The memory allocation completes and the allocator mutex is released, since
the low priority thread still owns the file system instance mutex it
continues to execute with the high priority (the high priority thread is not
scheduled)"
Instead --> after releasing lock over allocator the low priority threads
priority will no longer be high as there is restoration of priority of on
mutex release. This is the behavior with our implementation. So low priority
thread will again be restored at its original priority after releasing
allocator lock.
I am not able to get what do we have to do in this ticket like what is the
problem we are trying to solve(objective, current behavior)
2. Our implementation is only for strict order mutex behavior and will not
work for unordered mutex operations. We will need complete different
implementation for unordered mutex operation.
3. Our SMP implementation has recursive mutex acquisition behavior for
supporting horizontal nesting? Will it be fine with RTEMS?
note: Cyrille please mention any other doubts if I have missed any.
Thanks,
Saurabh Gadia
On Sun, Sep 6, 2015 at 11:04 PM, Sebastian Huber
<sebastian.hu...@embedded-brains.de> wrote:
Hello Saurabh,
On 05/09/15 01:52, Saurabh Gadia wrote:
This is the patch for solving priority inversion problem for uniprocessor
architecture. It works correctly for all test cases on master. For 4.11 the
patch get applied cleanly but the branch does not compile because of some
rbtree error(unrelated to project). Github link:
https://github.com/saurabhgadia4/rtems/tree/nested-mutex
I reviewed your patch. Basically you replaced the LIFO list of priorities
with a sorted list? Does it work with timeouts and external priority changes
(e.g. task A blocks on a mutex owned by O, another task B raises the
priority of A, will this raise the priority of O?)
Since all tests pass, test sptests/spsem03 passes, which shows that your
implementation doesn't support horizontal nesting.
There is no deadlock detection.
Please have a look at:
https://devel.rtems.org/ticket/2412
I think the suggested implementation would even work on SMP systems quite
well.
--
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.hu...@embedded-brains.de
PGP : Public key available on request.
Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.
--
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.hu...@embedded-brains.de
PGP : Public key available on request.
Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.
_______________________________________________
devel mailing list
devel@rtems.org
http://lists.rtems.org/mailman/listinfo/devel
