Can priority inversion occur in Android

7
votes

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.

1
javaandroidmultithreadingoperating-systempriority-inversion
That's nothing you should worry about. Roughly every system with priorities has that. But it only happens when you write "bad" code that requires that it's executed in a certain order / with certain priorities. Also the audio system link answers your question too ("attempts to avoid priority inversion") :) – zapl
Priority inversion usually do not occur due to bad code rather it depends on how scheduling is done by OS (or compiler in some languages) and it does concern developers, if a language guarantees that priority inversion will not occur than we don't have to worry about its avoidance/prevention etc – user4774371
You don't have to write code that competes concurrently for a shared resource - this is not the answer. In multi-threading threads/processes competes for shared resources that is inevitable but it can be managed using semaphores, locks etc. Actually that was not my actual question, we are discussing avoidance/prevention, my question was can priority inversion really happen in Android due to prorities associated to processes and threads – user4774371
"this is not the answer" hence I'm just commenting :) github.com/keesj/gomo/wiki/AndroidScheduling , groups.google.com/forum/#!msg/android-kernel/cL8OCVSXUuk/… has some details about the scheduling in Android. – zapl
@Oren thanks, you came up with an interring point. I agree different manufacturers may or many not have different version of Android OS, but it is very unlikely that they will have different OS kernels. Usually manufacturers tweak UI part of Android, and even if they have different kernels, each kernel will have same thread scheduling algorithm and thread priority levels, and these are the most important things which play their role in causing priority inversion. – user4774371

1 Answers

5
votes

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.