priority inheritance algorithms

[wei.a.yang]

在 2013-4-25，5:28，Pavel Pisa <ppisa4lists at pikron.com> 写道：

> Hello all,
> 
> It worth to read documentation about RT mutex in the Linux kernel
> 
> http://lxr.linux.no/#linux+v3.8.8/Documentation/rt-mutex-design.txt
> 
> The core mechanism for sorting waiters for given mutex is "plist"
> (priority based list). The other mechanism for priority inheritance/boost
> is PI chain/list.
> 
> http://lxr.linux.no/#linux+v3.8.8/Documentation/rt-mutex-design.txt#L214
> 
> The sorting of the waiters based on "plist" is far from to be O(1),
> use of RB-tree would be probably better for more waiters
> 
> linux-devel/include/linux/plist.h
> 
> * Based on simple lists (include/linux/list.h).
> *
> * This is a priority-sorted list of nodes; each node has a
> * priority from INT_MIN (highest) to INT_MAX (lowest).
> *
> * Addition is O(K), removal is O(1), change of priority of a node is
> * O(K) and K is the number of RT priority levels used in the system.
> * (1 <= K <= 99)
> *
> * This list is really a list of lists:
> *
> *  - The tier 1 list is the prio_list, different priority nodes.
> *
> *  - The tier 2 list is the node_list, serialized nodes.
> 
Hi, Pavel. Thank you for your advice. And in my former mail my proposal is very similar with the mechanism in the Linux. But the different is that I use two min-heap instead of two plist because of good algorithm complexity of min-heap. 
> 
> I have done some testing of RTEMS and Linux PI implementations.
> You can find my test code cor RTEMS classic API
> and POSIX RTEMS and Linux in the repo
> 
Good work. But I want to know the mechanism of RTEMS test. You know there are two PI algorithms in RTEMS. One is used by default, the other one should define __RTEMS_STRICT_ORDER_MUTEX__ to use it. You test two algorithms all?
> 
>  git clone git://rtime.felk.cvut.cz/rtems-devel.git
> 
>  rtems-devel/rtems-tests/prioinh_check
>       RTEMS classic
> 
>  rtems-devel/rtems-tests/prioinh_posix
>       POSIX version
> 
> To build for RTEMS, you need to specify platform. I.e.:
> 
>  cd rtems-devel/rtems-tests
>  echo RTEMS_MAKEFILE_PATH=/opt/rtems4.11/i386-rtems4.11/pc686 >config.target
> 
> To build for Linux, OMK Makefile.rules for Linux build can be used
> (See http://rtime.felk.cvut.cz/omk/) or simple
>  gcc -lpthread -lrt  prio_inherit_test.c
> 
> The output should look like this. Important part is to check
> that task "THI" obtains semaphore "SHI" immediately after
> Task "1" releases "SHI". That is order of the next two lines.
> 
>  1 going to release SHI
>  THI obtained SHI
> 
> The problem can be hidden on SMP system but on UP system it requires
> that task 1 priority is lowered imediattly after it releases SHI.
> The test on the SMP Linux system can use affinity to bind whole test
> on one CPU.
> 
> schedtool -a 1 -e ./prio_inherit_test
> 
> Then sequence should look like this
> 
> *** Starting up Task_1 ***
> THI created
> TMID created
> LO created
> 
> 1 obtained SLO
> 1 going to release RLO
> 1 obtained SHI
> 1 going to release RHI
> THI released (RHI)
> TLO released (RLO)
> 1 going to release RMID
> 1 going to release SHI
> THI obtained SHI
> THI going to release SHI
> THI released SHI
> MID released (RMID)
> MID going to sleep
> 1 going to release SLO
> 1 released both SHI and SLO
> 1 going to sleep
> TLO obtained SLO
> TLO going to release SLO
> TLO released SLO
> 
> 1 obtained SLO
> 1 going to release RLO
> 1 obtained SHI
> 1 going to release RHI
> THI released (RHI)
> TLO released (RLO)
> 1 going to release RMID
> 1 going to release SHI
> THI obtained SHI
> THI going to release SHI
> THI released SHI
> MID released (RMID)
> MID going to sleep
> 1 going to release SLO
> 1 released both SHI and SLO
> 1 going to sleep
> TLO obtained SLO
> TLO going to release SLO
> TLO released SLO
> 
> Order can varry on SMP system and possible priority adjustment
> problem can be hidden bu starting of THI on the different CPU.
> 
> *** Starting up Task_1 ***
> THI created
> TMID created
> LO created
> 
> 1 obtained SLO
> 1 going to release RLO
> 1 obtained SHI
> 1 going to release RHI
> TLO released (RLO)
> THI released (RHI)
> 1 going to release RMID
> MID released (RMID)
> 1 going to release SHI
> THI obtained SHI
> MID going to sleep
> 1 going to release SLO
> 1 released both SHI and SLO
> TLO obtained SLO
> THI going to release SHI
> THI released SHI
> 1 going to sleep
> TLO going to release SLO
> TLO released SLO
> 
> ...
> 1 obtained SLO
> 1 going to release RLO
> 1 obtained SHI
> 1 going to release RHI
> THI released (RHI)
> TLO released (RLO)
> 1 going to release RMID
> MID released (RMID)
> 1 going to release SHI
> THI obtained SHI
> MID going to sleep
> 1 going to release SLO
> 1 released both SHI and SLO
> TLO obtained SLO
> THI going to release SHI
> THI released SHI
> 1 going to sleep
> TLO going to release SLO
> TLO released SLO
> 
> Best wishes,
> 
>               Pavel
> 
> 
> 
>