Saturday, May 15, 2010
Blogger widget "Search this blog" not working
It seems the blogger widget "Search this blog" does not return any results; so many users have reported the issue to google, but this one is yet to be fixed. Meanwhile, you can try this one from Blogger Templates Designs. It works, you can find it in the sidebar of my other blog.
Sunday, April 4, 2010
Priority Inversion & Priority Inheritance
Came across the interesting concept of "Priority Inversion" & "Priority Inheritance" while going through the QNX documentation. Shall try to explain the concepts in simpler terms.
Usually in an OS, the scheulder would preempt a low priority job to give a high priority job a chance to run. However, in certain situtions it can be found that a high priority job is kept waiting for a low priority job to complete. This is referred to as "Priority inversion". The following example gives a better picture.
Lets consider two jobs Job A and Job C, such that Job A has higher priority among the two. The jobs are sharing a resource controlled by a lock, and lets say that presently Job A is waiting for Job C to unlock the resource. Note that upon unlocking, in the very first opportunity, the scheduler would preempt Job C and give the slot to Job A. Now lets introduce a third job - Job B, which has higher priority than Job C but lower priority than Job A. If Job B becomes ready to run which Job C was executing, the OS would preempt Job C in favor of Job B and Job C will not be able to run until Job B is complete (despite the point that the highest priority job Job A is waiting for Job C to unlock a shared resource). Thus, we see that a high priority job (Job A) is getting delayed (indirectly) because of a lower priority job (Job B). This scenario is referred to as "Priority Inversion".
In an RTOS, it is critical that this does not happen. One solution to this challenge, is referred to as "Priority Inheritance".
When the concept of priority inheritance is introduced to the above scenario, Job C would inherit the priorty of Job A for the duration Job A was waiting for Job C to unlock the shared resource. Thus, when the new JoB B is introduced, the scheduler sees that Job C is of higher priority than Job B and Job C would not be preempted in favor of Job B. Once Job C is executed, it releases the lock on the shared resources, immediately after which the system would preempt Job C in favor of Job A, and the priority of Job C would be restored to its original priority level (i.e. lower than that of Job B). Upon completion of Job A, the system would then run Job B and then finally Job C.
Usually in an OS, the scheulder would preempt a low priority job to give a high priority job a chance to run. However, in certain situtions it can be found that a high priority job is kept waiting for a low priority job to complete. This is referred to as "Priority inversion". The following example gives a better picture.
Lets consider two jobs Job A and Job C, such that Job A has higher priority among the two. The jobs are sharing a resource controlled by a lock, and lets say that presently Job A is waiting for Job C to unlock the resource. Note that upon unlocking, in the very first opportunity, the scheduler would preempt Job C and give the slot to Job A. Now lets introduce a third job - Job B, which has higher priority than Job C but lower priority than Job A. If Job B becomes ready to run which Job C was executing, the OS would preempt Job C in favor of Job B and Job C will not be able to run until Job B is complete (despite the point that the highest priority job Job A is waiting for Job C to unlock a shared resource). Thus, we see that a high priority job (Job A) is getting delayed (indirectly) because of a lower priority job (Job B). This scenario is referred to as "Priority Inversion".
In an RTOS, it is critical that this does not happen. One solution to this challenge, is referred to as "Priority Inheritance".
When the concept of priority inheritance is introduced to the above scenario, Job C would inherit the priorty of Job A for the duration Job A was waiting for Job C to unlock the shared resource. Thus, when the new JoB B is introduced, the scheduler sees that Job C is of higher priority than Job B and Job C would not be preempted in favor of Job B. Once Job C is executed, it releases the lock on the shared resources, immediately after which the system would preempt Job C in favor of Job A, and the priority of Job C would be restored to its original priority level (i.e. lower than that of Job B). Upon completion of Job A, the system would then run Job B and then finally Job C.
Subscribe to:
Posts (Atom)
