Add priority inheritance implementation for Semaphores.
Introduce the support for the Priority Inheritance protocol (PI [1])
when using kernel semaphores. The aim of the protocol is to avvoid
the phenomenon known as priority inversion. This happens when a
high priority process blocks on a mutex/semaphore own by a low priority
one, which is then preempted by a third process, with priority in the
middle between the previous two and not using any semaphore. What
happens is, in fact, that the high priority process is delayed by
the medium priority one, and this is usually a bad thing... Feel
free to ask NASA [2] !!!
So, in case we have the following `process(prio)', sharing a couple of
semaphores:
> test1(2): Start.
> test2(3): Start.
> test3(4): Start.
> test4(5): Start.
> test6(7): Start.
> test7(8): Start.
> test8(9): Start.
And the following one, not using any semaphore at all.
> test5(6): Start.
Then without this commit, the finishing time of all the processes is as
follows:
> Main: I-O latency of 1 = 375ms
> Main: I-O latency of 2 = 374ms
> Main: I-O latency of 3 = 374ms
> Main: I-O latency of 4 = 373ms
> Main: I-O latency of 5 = 156ms
> Main: I-O latency of 6 = 372ms
> Main: I-O latency of 7 = 372ms
> Main: I-O latency of 8 = 371ms
With the protocol enabled we have:
> Main: I-O latency of 1 = 376ms
> Main: I-O latency of 2 = 376ms
> Main: I-O latency of 3 = 375ms
> Main: I-O latency of 4 = 375ms
> Main: I-O latency of 5 = 374ms
> Main: I-O latency of 6 = 217ms
> Main: I-O latency of 7 = 217ms
> Main: I-O latency of 8 = 216ms
As it is clear, in the non-PI enabled case, test5 'disturbs' the
processes with priority higher than 6, i.e., test{6,7,8}, by preventing
the lower priority processes that are owning the semaphore to run and
release it. On the other hand, when PI is on duty, the highest priority
processes are able to complete without being interrupted by test5,
thanks to the priority lending enacted by the protocol.
In order of making it possible to enable the implemented bits at
configure/compile time, the CONFIG_KERN_PRI_INHERIT switch has been
added, and it is part of cfg_proc.h, mainly because priority inheritance is
often considered a feature of the scheduler, more than of the blocking
mechanisms (but all this can be changed easily!).
Introduced for and only tested in emulation mode on x86.
[1] L. Sha, R. Rajkumar, and J. P. Lehoczky, "Priority Inheritance
Protocols: An Approach to Real-Time Synchronization". IEEE Transactions
on Computers 39 (9): 1175–1185.
[2] http://research.microsoft.com/en-us/um/people/mbj/Mars_Pathfinder/
Signed-off-by: Dario Faggioli <raistlin@linux.it>
git-svn-id: https://src.develer.com/svnoss/bertos/trunk@4908
38d2e660-2303-0410-9eaa-
f027e97ec537