Add priority inheritance implementation for Semaphores.
authorlottaviano <lottaviano@38d2e660-2303-0410-9eaa-f027e97ec537>
Tue, 17 May 2011 14:08:03 +0000 (14:08 +0000)
committerlottaviano <lottaviano@38d2e660-2303-0410-9eaa-f027e97ec537>
Tue, 17 May 2011 14:08:03 +0000 (14:08 +0000)
commit1f49e719b93b94993073d3b4abf2108452f71d01
tree0f7401005b012fffe4932b446481da11f28b0e9d
parent454e0296b7831a0fea4f5364040e02b923f4dd6e
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
bertos/cfg/cfg_proc.h
bertos/kern/proc.c
bertos/kern/proc.h
bertos/kern/proc_p.h
bertos/kern/sem.c
bertos/kern/sem_test.c
bertos/struct/list.h
examples/demo/cfg/cfg_proc.h