Question: Someone might want to look up the term priority inversion and describe how it might be relevant here.
althalus
An example is if there are three tasks, T0(highest priority),T1,T2(lowest priority).
It is possible that T2 is set to execute first and it locks a resource R0 during its execution.
After an amount of time, T0 might preempt T2 and start executing. During its execution, it might try to access R1. However, since R1 is already locked by T2, T0 will stop executing and the next highest priority task, T1, will start execution.
If a blocking algorithm allows one thread(T2) to prevent other threads(T0) from completing operations on a shared data structure, the example above shows how the priority of the tasks is inverted since the lock causes T1 to execute before T0 has finished.
Richard
@althalus Thank you for your explanation. Maybe this can be solved by preventing preemption while T2 is in a "locked" state. Assuming that the "locked" instructions are not much, it's worthwhile waiting for T2 finishing the critical section. Otherwise, suppose there are many tasks with priority between T0 and T2, then T0 will be waiting for really a long time.
Richard
Another question, what does "spinning" in this slide mean?
TanXiaoFengSheng
@Above, spinning means the thread waiting for the lock is occupying the CPU
TanXiaoFengSheng
@Richard, the issue is the scheduler has no idea whether a thread is in its critical section, which is a semantics in application level.
Richard
@TanXiaoFengSheng, I'm not sure, but can we define a lock that can prevent preemption?
rajul
@Richard well one possible way to prevent priority inversion is to use a priority inheritance mechanism. The basic idea being that when you grab a lock your priority is elevated to a higher priority and you go back to original priority on releasing a lock. This idea can be used along with your scheduler policy to prevent preemption of a thread in critical section.
ArbitorOfTheFountain
There are several methods to avoid priority inversion (especially important in realtime systems, which we don't cover too much in this course). Like you mentioned priority inheritance is one method. Priority ceiling is a simpler-to-implement scheme where tasks holding a lock are elevated to the "ceiling" priority to ensure they release their locks before a higher priority task might need them. Finally there is Random Boosting, which is used in our (very much NOT real-time) friend Microsoft Windows: https://en.wikipedia.org/wiki/Random_boosting
cyl
There is a story in 1997 NASA. The priority inversion happened during the mission on Mars.
Complement for "priority inheritance mechanism": Once the thread get a lock, its priority will be raised to highest priority among other threads that MAY grab this lock, too. As a result, priority inversion won't happen and other more-higher priority threads won't be influenced (it will preempt the lock-holder because its priority is higher than all threads that may hold this lock).
leis1
In short:
priority inversion: task with lower priority from programmer's perspective is processed first.
Why it's relevant here? Just as Kayvon mentioned in the lecture, one may have
10 threads racing for one lock and thread 0 hold the lock currently. We want thread 0 to run and release lock therefore other threads could proceed But due to many reasons, thread 0 may be swapped out/slow/crashed. Therefore other threads is running or spinning before thread 0 is chosen and run. In that case, this would be a priority inversion.
Question: Someone might want to look up the term priority inversion and describe how it might be relevant here.
An example is if there are three tasks, T0(highest priority),T1,T2(lowest priority). It is possible that T2 is set to execute first and it locks a resource R0 during its execution. After an amount of time, T0 might preempt T2 and start executing. During its execution, it might try to access R1. However, since R1 is already locked by T2, T0 will stop executing and the next highest priority task, T1, will start execution.
If a blocking algorithm allows one thread(T2) to prevent other threads(T0) from completing operations on a shared data structure, the example above shows how the priority of the tasks is inverted since the lock causes T1 to execute before T0 has finished.
@althalus Thank you for your explanation. Maybe this can be solved by preventing preemption while T2 is in a "locked" state. Assuming that the "locked" instructions are not much, it's worthwhile waiting for T2 finishing the critical section. Otherwise, suppose there are many tasks with priority between T0 and T2, then T0 will be waiting for really a long time.
Another question, what does "spinning" in this slide mean?
@Above, spinning means the thread waiting for the lock is occupying the CPU
@Richard, the issue is the scheduler has no idea whether a thread is in its critical section, which is a semantics in application level.
@TanXiaoFengSheng, I'm not sure, but can we define a lock that can prevent preemption?
@Richard well one possible way to prevent priority inversion is to use a priority inheritance mechanism. The basic idea being that when you grab a lock your priority is elevated to a higher priority and you go back to original priority on releasing a lock. This idea can be used along with your scheduler policy to prevent preemption of a thread in critical section.
There are several methods to avoid priority inversion (especially important in realtime systems, which we don't cover too much in this course). Like you mentioned priority inheritance is one method. Priority ceiling is a simpler-to-implement scheme where tasks holding a lock are elevated to the "ceiling" priority to ensure they release their locks before a higher priority task might need them. Finally there is Random Boosting, which is used in our (very much NOT real-time) friend Microsoft Windows: https://en.wikipedia.org/wiki/Random_boosting
There is a story in 1997 NASA. The priority inversion happened during the mission on Mars.
youtube
Complement for "priority inheritance mechanism": Once the thread get a lock, its priority will be raised to highest priority among other threads that MAY grab this lock, too. As a result, priority inversion won't happen and other more-higher priority threads won't be influenced (it will preempt the lock-holder because its priority is higher than all threads that may hold this lock).
In short:
priority inversion: task with lower priority from programmer's perspective is processed first.
Why it's relevant here? Just as Kayvon mentioned in the lecture, one may have 10 threads racing for one lock and thread 0 hold the lock currently. We want thread 0 to run and release lock therefore other threads could proceed But due to many reasons, thread 0 may be swapped out/slow/crashed. Therefore other threads is running or spinning before thread 0 is chosen and run. In that case, this would be a priority inversion.