priority inheritance algorithms

[Pavel Pisa]

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.

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

  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