Can priority inversion occur in Android

Priority inversion is a problem which can occur during scheduling of threads/processes, due to priorities associated with them.

Priority inversion is a problematic scenario in scheduling in which a high priority task is indirectly preempted by a medium priority task effectively "inverting" the relative priorities of the two tasks - Wikipedia

I wonder, can priority inversion happen in Android, as we know Android provide different processes with different priorities, see this post. Also we can create multiple threads (in activities and services) with different priorities, how they fit in this scenario? I saw an article which talks about Thread Scheduling in Android. If priority inversion has happened, how can we detect and avoid it?

When I was looking for answers to this question, I found this page by Android, which tells us how to avoid priority inversion in context of Android's audio system.

The Short Answer

Yes, priority inversion can occur in Android, as detailed in the link that you provided.

The Problem

Any system that allows tasks with different priorities to lock the same shared resource is vulnerable to priority inversion, unless steps are taken to prevent it. You mentioned threads and processes - in Android, state can be shared between both processes and threads, making them both vulnerable to priority inversion.

The main issue posed with priority inversion is that lower priority tasks are given less CPU cycles in which to execute. If a time-senstive high priority task is blocked by a low priority task, it may have to wait for an unacceptably long amount of time to execute and either cause a failure somewhere in your system or degrade user experience.

The Traditional Solution

The traditional solution to this is priority inheritance. With priority inheritance, the task (thread or process) that holds the shared resource will temporarily inherit the priority of the highest-priority task that is blocking on that resource. This solves the problem, since the low priority task will execute much more quickly, freeing up the resources for the time-sensitive task.

Futexes (fast user space mutexes) with this capability are available in the Linux Kernel. However, they are not available in the Android standard C library because of security concerns and because they involve large amounts of overhead.

The Android Solution

The Android Open Source Project recommends several different approaches to dealing with the priority inversion problem.

• "try lock" / lock with timeout - enforce some timeout period on how long the low-priority task can hold the mutex, making it more likely that the high-priority task can gain access in time. The drawback is if there are a sequence of unrelated low-priority tasks with a long cumulative time-out.
• In some cases, a mutex or other synchronization primitive can be replaced by the proper set of atomic operations, together with Symmetric Multiprocessing. A guide on this is provided here.
• You can also implement a lock-free single-reader, single-writer FIFO task queue. This is described here and here.

The basic theme common to all of these methods is to minimize the amount of locks on resources shared between high and low-priority rasks, or to mitigate their effects if they truly cannot be removed. Currently these techniques are all in use in Android to reduce priority inversion issues.

Detection

It is difficult to automatically detect priority inversion before it occurs. If you suspect it is occurring, you can test your hypothesis using tools such as systrace and ps -t -p to examine the amount of time your different processes spend executing and blocking. The best advice is to have a good understanding of the different parts of the system that you are dealing with, and of the problem of priority inversion.