Can invert priority in Android

Question

Priority inversion is a problem that may arise when scheduling threads / processes due to their associated priorities.

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

I wonder if priority inversion can happen in Android, since we know that Android provides different processes with different priorities, see this post . We can also create multiple threads (in actions and services) with different priorities, how do they fit into this scenario? I saw an article that talks about Thread Scheduling in Android . If priority inversion occurs, how can we detect and avoid it?

When I was looking for answers to this question, I found this Android page that says how to avoid priority inversion in the context of the Android audio system.

Answer 1

Short answer

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

Problem

Any system that allows tasks with different priorities to block the same shared resource is vulnerable to priority inversion, unless steps are taken to prevent this. You mentioned topics and processes - in Android, the state can be divided between processes and threads, which makes them vulnerable to priority inversion.

The main problem with priority inversion is that tasks with lower priority are given fewer CPU cycles to complete. If a high-priority task with a time limit is blocked by a low-priority task, it may have to wait an unacceptably long amount of time to complete and either cause a crash somewhere in your system or degrade the user’s work.

Traditional solution

The traditional solution for this is priority inheritance . In priority inheritance, a task (thread or process) that contains a shared resource temporarily inherits the priority of the task with the highest priority that blocks this resource. This solves the problem since a low priority task will run much faster, freeing up resources for a time sensitive task.

Futexes (user space mutexes) with this feature are available in the Linux kernel. However, they are not available in the standard Android C library due to security issues and because they involve large amounts of overhead.

Android solution

The open source Android project recommends several different approaches to solving the issue of priority inversion.

• "try lock" / lock with timeout - force use of a certain timeout period in how long the low priority task can hold the mutex, which makes it more likely to get a high priority task in time. The disadvantage is that there is a sequence of unrelated tasks with low priority with a long accumulated timeout.
• In some cases, a mutex or other synchronization primitive can be replaced by an appropriate set of atomic operations along with Symmetric Multiprocessing. This guide is provided here .
• You can also implement a standalone single-user read queue with a single FIFO reader. It is described here and here .

The main theme common to all these methods is to minimize the number of locks on resources shared between high and low priority races, or to mitigate their effects if they really cannot be removed. These methods are currently used by Android to reduce priority inversion problems.

Detection

It is difficult to automatically detect a priority inversion before it occurs. If you suspect this is happening, you can test your hypothesis with tools like systrace and ps -t -p to find out how much time your different processes spend executing and blocking. The best advice is a good understanding of the various parts of the system you are dealing with and the problems of priority inversion.