What is priority inversion? how to fix it?


  • 1
    M

    What is priority inversion? how to fix it?


  • 7
    M

    Priority Inversion

    Shared resource needed by high priority processes are held by low priority processes, while low priority processes fail to get CPU usage. This makes the priority inversed(High priority waits for low priority.), and results in the situation that neither high priority process cannot execute normally(without resources) nor low priority cannot execute normally(without CPU).

    Solution

    Use "Priority Inheritance" to solve this situation. First, we allow low priority processes to inherit the priority of high priority processes, which makes low priority processes execute normally and exit and then release the resources. Thus, high priority process can get the resources they need and execute successfully.


  • 0
    J

    Common practice is to raise the priority before occupy the resource.


  • 0
    B

    When multiple processes shared common resources , i.e they are having a common critical section . Critical section where shared resources are present .
    Let take P1 process with low priority currently present in the Critical section, then new process P2 came with high priority , but we cannot context switch P1 with P2 as P1 is currently in Critical section .if we do so it may led to data inconsistency.
    To avoid this we use priority inversion i.e process currently in critical section will be given same same priority as process outside.


  • 4

    P0 > P1 > P2.

    P2 holds the resources need by P0. But P2 cannot get CPU usage due to low priority. As a result, P1 can be executed before P0, which is called "PRIORITY INVERSION"

    To solve this issue, usually we raise the priority of P2 to P0(inheritance) temporary to make sure that P2 can get CPU before P1.


  • 0
    A

    There are two types of threads: Kernel Threads and User level threads. A thread is an abstraction of a processor. There are different models of implementation of threads:

    One level model: Here the threads are implemented in the kernel.
    Two level model: Here the threads are implemented in user library.

    In one level model, all aspects of thread implementation are in the kernel that is all thread routines (like mutex lock) called by user code are system calls. For eg if thread calls pthread_create, it would be a system call. The kernel creates a kernel and user stack for this thread. Here each user thread is mapped one to one to a kernel thread.

    In two level model, user-level library is important. What an user level application perceives as a thread is implemented within user-level library code. Threads are completely implemented in the user mode. Now these threads can be mapped to a single kernel thread or some multiple kernel threads. Remember, thread is an abstraction for processors. So more kernel threads virtually means more processors.

    When User threads are mapped to kernel threads, it may be possible that the priority for user level and kernel level are different. This can cause priority inversion. One of the method to solve this is to make user level scheduler to somehow talk to kernel level scheduler.

    Another way to solve this problem is by making kernel level scheduler schedule user processes and implementing the threads completely in user space.


  • 0
    L
    This post is deleted!

  • 5
    C

    Priority inversion
    With static priority assignment a higher-priority task can be suspended waiting for a lower-priority task to perform some operation. The priorities of the tasks are being undermined. And the higher-priority task is said to be blocked, and the situation is known as priority inversion. In other words, critical shared resource required by tasks with higher priorities are held by the tasks with lower priorities and therefore the higher priority tasks have to wait until the lower priority tasks completed. The following figure show a typical case of priority inversion:
    0_1496435207446_1190df4d-a92b-4534-99f8-8bf312db1f6b-image.png
    we can see that higher priority task (L4) was blocked waiting for Q by lower priority task (L1) and it can only be executed until L1 finished and gave back the resource Q.
    Or if there is a critical section then the situation can be:
    0_1496435507259_cd11e33e-6496-4ef0-ad58-c19bc0b761a6-image.png
    Source of the figure: Chenyang Lu, Washington University Saint Louis

    Solutions
    Priority inversion results from using a fixed(static) priority scheme. It can be overcome by allowing a task to temporarily increase its priority to prevent it causing blocking.

    1. Priority inheritance: temporary priority is that of highest priority task that is being blocked
      0_1496435389052_2f12c6ac-1f73-4d04-873a-41eaf85a1220-image.png
    2. Immediate Ceiling Priority Inheritance
      Temporary priority depends on a priority associated with the locked resource, each resource has a static ceiling value defined, this is the maximum priority of all the tasks that use it. A task has a dynamic priority that is the maximum of its own static priority and the ceiling values of any resources it has blocked. (e.g. If the highest priority task to use resource Q has a priority of 4, then any task using Q will have a priority of 4 while it does so.)
      0_1496435401892_d94641a2-6f03-49d3-91a4-01857fe98af9-image.png

    And the comparison between those two methods can be found at:
    https://www.it.uu.se/edu/course/homepage/realtid/ht12/schedule/synchronization-resource-sharing.pdf


  • 1
    M

    @mai-hsuan

    Priority Inheritance is the cleanest way to solve a Priority Inversion situation. The OS handles priority changes in its code, automatically.

    An alternative solution in some cases is to use a "Priority Ceiling". An additional "Priority Ceiling" is assigned to threads so they can only be preempted by threads above the Priority Ceiling. All threads that share a resource then must have a priority at or below the Priority Ceiling.


  • 0
    M

    @mrEcen91
    Nice, it recalls me the things taught in the Real-time system class.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.