Re: [rtl] priority inversion..

[Victor Yodaiken <yodaiken@fsmlabs.com>]

On Mon, Jun 18, 2001 at 02:08:11PM +0700, Handy Madinata wrote:
> dear all,
> 
> I have questions about priority inversion condition in realtime system:
> 
> 1. Is it right that priority inversion condition will be a problem only if
> its duration is unbound


No:
	Suppose we have three tasks
	High priority needs to run every 70 microseconds, takes data from devices and queues it
	Medium priority interrupt driven task that takes 25 microseconds and must run within 75
	         microseconds of the interrupt.
	Low priority task scheduled to run every 500 microseconds that collects the 
           data queued by High and does something with it.

	   Supppose High does
	   		collect data /* takes 10 microseconds */
			get semaphore /* takes 5 microseconds */
			enq data    /* takes 10 microseconds */
			release semaphore /* 5 microseconds */

	Suppose Low does
			get semaphore /* takes 5 microseconds */
			deq data    /* takes 50 microseconds */
			release semaphore /* 5 microseconds */
			

	Suppose each context switch costs 6 microseconds - pretty fast.

	if Low takes the semaphore; High starts and blocks at once; 
	and then medium is woken by interrupt.
	       25us for Medium + 55 for Low -> High  fails

	      (even ignoring context switch costs)

	Note that this is exactly the kind of thing that will work well in testing and 
	only fail when you are standing near the production run of the 50 ton turbine 
	spinning at 10,000RPM,

	Suppose we turn on PIP.  To start
	we see that now Medium may die  from priority inversion:
	      Low takes semaphore; High starts and blocks; Medium is scheduled but
	      is now lower priority than Low;

	      55  for Low + 30 for high and Medium fails.
	      (even ignoring context switch costs)

	Also a rare case that may never happen in production if you are lucky.
	Let relax the timing on Medium, but also take into account that turning
	on PIP will increase semaphore operation times -let's say to 15 microseconds.
	Make Medium only need 120 microseconds from interrupt response.

	Now suppose
	   Low gets semaphore; Medium preempts; High preempts and blocks; Low runs; 

	   So we have 
		switch to start High 6us
		High runs collect 10 us
		High runs PIP sem-get and blocks  15us 
		switch to Low  6us
		Low runs and releases semaphore 65microseconds
		switch to high 6
		High runs to completion  25 us
		switch to medium 6 us
		-----------------------------------------
		Medium is delayed 133 us and fails. 

        
	The problem is that neither PIP nor PCP cure priority inversion, they simply
	cure certain cases of unbounded priority inversion. The design error in these 
	examples is not priority, it is that the low priority task can block the
	high priority task.  The correct fix is to either fix scheduling times so that
	the High and Low priority tasks never run at the same moment (hard), or
	use atomic operations or non-blocking queues to decouple the two threads



		
	RTLinux supports PCP, but I recommend it be used  with care.

	

		
	


> 
> 2. what is the differences beetwen pcp (priority ceiling protocol), its
> emulation, and pip (priority inheritance protocol) because they are same
> to me as all of them give the highest process' priority, that are blocked
> for a resource, to a process that have lock for that resource so that the
> process can't be preempted by any intermediate process.
> 
> 3. is it right that for rtlinux, priority inversion problem solutions are
> hacking and can cause another problems so leave that condition is better
> than solve them
> 
> thanks
> 
> -======================================-
>  Handy Madinata
>  students of departement of informatics
>  bandung insitut of technology
>  indonesia
> -======================================-
> 
> ----- End of forwarded message from owner-rtl@fsmlabs.com -----
> -- [rtl] ---
> To unsubscribe:
> echo "unsubscribe rtl" | mail majordomo@rtlinux.org OR
> echo "unsubscribe rtl <Your_email>" | mail majordomo@rtlinux.org
> --
> For more information on Real-Time Linux see:
> http://www.rtlinux.org/rtlinux/
> 
> 2. what is the differences beetwen pcp (priority ceiling protocol), its
> emulation, and pip (priority inheritance protocol) because they are same
> to me as all of them give the highest process' priority, that are blocked
> for a resource, to a process that have lock for that resource so that the
> process can't be preempted by any intermediate process.
> 
> 3. is it right that for rtlinux, priority inversion problem solutions are
> hacking and can cause another problems so leave that condition is better
> than solve them
> 
> thanks
> 
> -======================================-
>  Handy Madinata
>  students of departement of informatics
>  bandung insitut of technology
>  indonesia
> -======================================-
> 
> ----- End of forwarded message from owner-rtl@fsmlabs.com -----
> -- [rtl] ---
> To unsubscribe:
> echo "unsubscribe rtl" | mail majordomo@rtlinux.org OR
> echo "unsubscribe rtl <Your_email>" | mail majordomo@rtlinux.org
> --
> For more information on Real-Time Linux see:
> http://www.rtlinux.org/rtlinux/