Proxy Execution in Android

Proxy Execution is a scheduling feature for the Linux kernel. This page covers why it's needed, how it works, guidance for updating vendor hooks, and details for validating that it's working.

Priority inversion issues

In Android, there are the concepts of foreground and background tasks. Ideally you want the foreground tasks the user is interacting with to be prioritized, and you want to make sure the background tasks don't interfere or interrupt foreground tasks. Additionally, you want to make sure you limit the amount of CPU and battery those background tasks can consume.

When using most mechanisms to constrain or restrict background tasks and prioritize foreground tasks, average latencies improve. But there is a side effect: outlier latencies increase. This might seem counterintuitive, but it's a well-understood issue called priority inversion.

Linux uses rt_mutex structs, which use priority inheritance to solve this problem. However, rt_mutex structs have limitations. They only help with RT tasks, which have a strict linear priority order. RT priorities are recommended only for trusted system apps because these priorities can be unsafe for third-party apps, making them unsuitable for prioritizing foreground apps over background ones.

rt_mutex structs aren't always used in the kernel (an exception is CONFIG_PREEMPT_RT), and normal in-kernel mutexes (and other common kernel locking primitives) can be a common source of priority inversion.

Upstream, there is no inheritance for rt_mutex structs for fair-class (SCHED_NORMAL/BATCH) waiters. The assumption is that with the fair class, all tasks get approximately equal runtime (ignoring the nice weighting), so priority inversion can't occur indefinitely.

While not indefinite, priority inversion can occur for long enough to be problematic, causing interactivity latencies (jank) and other delays.

Thus there is a need for a solution that:

• Provides inheritable priority across complex scheduling orderings (nested cgroups, vruntime, deadlines) where there might not be a linear priority order, so that it can work across all scheduler classes (deadline, realtime, fair, scx, and idle).
• Supports priority inheritance for locking primitives other than rt_mutex structs.

Generalized inheritance with Proxy Execution

Proxy Execution provides a generalized form of priority inheritance that supports in-kernel mutexes and rw_semaphore structs.

To illustrate this, consider a small benchmark that uses a foreground and background task that do the same file system operations in a directory, as well as some CPU spinner tasks to generate load. Measuring the latencies of the foreground task completing the operations shows a normal distribution of latencies, sometimes as high as 20 ms, when the background and spinner tasks are unconstrained.

When the test constrains the background and spinner tasks using cpu-cgroup cpu_shares (or weight), the average latency improves, but the worst-case outliers balloon to 120 ms due to priority inversion (where the background task holds a lock needed by the foreground task, and has to wait for it to be scheduled to proceed).

But with Proxy Execution, the test can constrain background tasks and improve the average latency of foreground tasks without the negative impact of priority inversion, because it provides priority inheritance.

Figure 1. Example latency histograms.

Many partners have developed their own vendor-hook-based workarounds to priority inversion. Proxy Execution can provide a common solution, bringing more ecosystem consistency for app developers, and reducing the amount of maintenance of out-of-tree debt required by partners. However, feedback is welcome regarding situations or cases where Proxy Execution needs extensions to match the partner-specific solutions.

Proxy Execution in the Android Common Kernel

While (as of Linux v6.19) Proxy Execution is partially upstream, the full Proxy Execution patch series has been included in multiple Android Common Kernels. The status of Proxy Execution in Android Common by version is:

Proxy Execution overview

In Proxy Execution, when a task blocks on a kernel mutex (or rw_semaphore), the waiter donates its time to the lock owner, so the owner can run and release the lock.

The first change is to leave mutex blocked tasks on the run queue. Note that the task is marked as blocked (using task->blocked_on), so it doesn't run if selected by the scheduler.

The second is called the split-context. With it, the scheduler uses two separate pointers, rq->curr and rq->donor. The rq->donor pointer is for scheduling accounting (that is, the task we charge the time against). The rq->curr pointer is the running task.

With Proxy Execution, the scheduler is treated as an opaque box, so it can pick the most important task to run out of the set of both runnable and mutex blocked tasks. If it picks a non-blocked task, both the rq->curr and rq->donor are set to the selected task from pick_next_task(), and the behavior is the same as without Proxy Execution.

If the scheduler selects a mutex-blocked task, pick_next_task() is used to set the rq->donor. Next, find_proxy_task() is called to look up the mutex owner and return the runnable owner task. If that mutex owner is blocked on another mutex, find_proxy_task() traverses the chain to find that mutex's owner. The scheduler sets the rq->curr pointer to the task returned by find_proxy_task(), and then runs it.

If no task is returned from find_proxy_task() (more on why this could happen follows), the __schedule() logic is restarted to pick another task.

Proxy Execution must handle several complications:

• In find_proxy_task(), if the lock is released while searching for the mutex owner, the function returns NULL and picks again.
• If the mutex-owning task is on a different CPU's run queue, find_proxy_task() dequeues the selected donor task from this run queue, and migrates it to the remote CPU's run queue. This allows the important task to be selected on that run queue to run the lock owner. This might seem counterintuitive (as opposed to migrating the owner to the donor's CPU), but the lock owner might be SMP-affined, such that it can't run on another CPU. The donor task doesn't run on the remote CPU; it only donates its time. There might be several donors waiting on the lock, so migrating them to the owner's CPU is possible, unlike migrating the owner when multiple waiters might be simultaneously on different CPUs. When the lock is released and the donor is woken up, Proxy Execution return-migrates the donor. This mechanism is similar to the mutex-blocked task being removed from a run queue and then restored when the lock is released and it's woken up.
• If the mutex owning task is sleeping (off the run queue), dequeue the selected donor task, add its task->blocked_node to the task->blocked_head list on the owner's task-struct, and return NULL to pick again. When the owner is woken up and returned to a run queue, add any waiting dequeued tasks on the owner's blocked_head list to the same run queue.
• There are a few transient edge cases (usually where a race has occurred) where the function returns NULL and forces the scheduler to pick again (see the find_proxy_task() logic for details).

If find_proxy_task() needs to migrate or dequeue a running task (on_cpu), find_proxy_task() returns rq->idle to run as rq->curr, but avoids clearing need_resched, so that __schedule() context switches to idle. This removes the current task from the CPU. Then when the CPU immediately re-enters __schedule(), find_proxy_task() can then migrate the task.

Another change is that when the lock is released and the waiting donor task is woken up, logic detects it was a blocked donor task and dequeues it from the run queue so the wakeup logic can work properly. Otherwise, the try_to_wake_up() logic might assume a task on the run queue was already woken, allowing a donor task to run on a CPU it wasn't allowed to run on.

The key changes for Proxy Execution are in the scheduler core. The mutex lock logic remains mostly the same as without Proxy Execution; the wait_list and its order are unmodified. The only exception with mutexes is that an explicit lock handoff to the donor is attempted when the owner releases the lock while being proxied (effectively rewarding the donor for its donation).

Guidance for converting vendor hooks

Partners often use the vendor hooks in the scheduler code to create their own solutions to optimize and resolve scheduling issues.

The concepts introduced in Proxy Execution, like split contexts, might confuse some of these vendor hook implementations. This page guides partners as they update their vendor hooks to avoid problems.

Adapting vendor hooks to work with Proxy Execution enables partners to deprecate their custom priority inversion solutions, reducing code maintenance.

Use these key points to handle the split contexts:

• From the scheduler's perspective, the purpose of pick_next_task() is to select the donor that most accounting is based on.
• Check for references to rq->curr, task_current(), and current in your vendor hook implementation.
• In general, the rq->donor or task_current_donor() is likely what should be used instead of rq->curr and task_current(). There are some exceptions where both are needed.

Pay attention to the semantic changes to prev and next:

• Before Proxy Execution, prev was rq->curr or current and next was the task to be switched to.
• With Proxy Execution, prev is aligned to the current rq->donor, because it was selected by pick_next_task() previously and was passed to set_next_task(). If you call put_prev_task(), use the rq->donor, not rq->curr or current.

Avoid migrating mutex blocked tasks:

• While mutex blocked tasks are kept on the run queue, avoid balancing or migrating blocked tasks (task_is_blocked()), as they might have been proxy-migrated to this CPU to act as a donor, and are immediately returned if migrated.

Avoid calling set_task_cpu() on rq->curr or rq->donor while proxying:

• Don't try to migrate rq->donor or rq->curr when they aren't the same. The two tasks need to stay on the same run queue as a pair; adding them individually to pushable lists or trying to migrate them separately crashes the kernel.

Be careful with rq_lock drops:

• The run queue rq_lock is needed for most operations that use a run queue structure. However, there are a number of places (like migrating to another run queue, or acquiring a pi_lock) where the run queue lock needs to be momentarily dropped and then re-acquired.
• Without Proxy Execution, in the __schedule() context, you can assume that rq->curr is stable even across run queue lock drops, as it's running on the CPU and the __schedule() context is the only thing that would change it. With Proxy Execution, rq->donor can change during a run queue lock drop, as it might have been woken up and return-migrated. Logic that depends on rq->donor prior to the run queue lock drop needs to revalidate or re-sample rq->donor after the run queue lock is reacquired.

Validate Proxy Execution on Android

The priority-inversion-demo tool has been ported to Android and can be found in the $ANDROID_TOP/system/extras/perf_tools/priority-inversion-demo/ directory.

In this example, the test system was booted with Proxy Execution disabled (sched_proxy_exec=false) to begin.

From the $ANDROID_TOP directory, run the test:

$ atest priority-inversion-demo
…
Test logs: /tmp/atest_result_jstultz/20260128_010833_6rd9n49a/log
…

Take note of the path to the results under the directory listed in the atest output Test logs line for results filenames that start with results-schedload-contention*:

$ ls /tmp/atest_result_jstultz/20260128_010833_6rd9n49a/log/stub/local_atest/inv_9976511134246300768/results-schedload-contention*
/tmp/atest_result_jstultz/20260128_010833_6rd9n49a/log/stub/local_atest/inv_9976511134246300768/results-schedload-contention.log_8613449191442473807.gz
/tmp/atest_result_jstultz/20260128_010833_6rd9n49a/log/stub/local_atest/inv_9976511134246300768/results-schedload-contention-throttled.log_2711867148783874668.gz

If you booted with sched_proxy_exec=false, enable Proxy Execution by running:

$ adb root
$ adb shell 'echo 1 > /sys/kernel/sched_proxy_exec/enable'

Run the test again:

$ atest priority-inversion-demo
…
Test logs: /tmp/atest_result_jstultz/20260128_011816_jz0c23qm/log
…

Again, take note of the path to the results under the directory listed in the atest output Test logs line for results filenames that start with results-schedload-contention*:

$ ls /tmp/atest_result_jstultz/20260128_011816_jz0c23qm/log/stub/local_atest/inv_17549283420540203764/results-schedload-contention*
/tmp/atest_result_jstultz/20260128_011816_jz0c23qm/log/stub/local_atest/inv_17549283420540203764/results-schedload-contention.log_11801850315328134210.gz
/tmp/atest_result_jstultz/20260128_011816_jz0c23qm/log/stub/local_atest/inv_17549283420540203764/results-schedload-contention-throttled.log_13816565259772866870.gz

Finally, generate statistics from both sets of logged results, using the file paths noted:

$ cd $ANDROID_TOP/system/extras/perf_tools/priority-inversion-demo/
$ ./hist.py /tmp/atest_result_jstultz/20260128_010833_6rd9n49a/log/stub/local_atest/inv_9976511134246300768/results-schedload-contention* /tmp/atest_result_jstultz/20260128_011816_jz0c23qm/log/stub/local_atest/inv_17549283420540203764/results-schedload-contention*
avg: 0.03888746236278515        med: 0.005127   max: 68.160035
avg: 0.010640975007993943       med: 0.005208   max: 240.471762
avg: 0.023518252005299903       med: 0.005087   max: 28.04008
avg: 0.00997385578938922        med: 0.005289   max: 7.999064

An example of the resulting chart (chart-split.png) is shown in Figure 2:

Figure 2. Generated latency histograms from tool.

Limitations of Proxy Execution

Proxy Execution is enabled for in-kernel mutexes (since android16-6.12) and in-kernel rw_semaphore structs (since android17-6.18). We want to broaden its use to other locking primitives where needed, using an iterative approach.

We plan to expand Proxy Execution to binder inheritance and futexes, but wider adoption is required before relying on its availability.

Disable Proxy Execution

If you can't get Proxy Execution working with your vendor hooks, you can boot with sched_proxy_exec=false to disable Proxy Execution.

More information

See related conference videos:

• Proxy Execution: When Priority Inheritance just won't do - OSPM23
• Proxy Execution: Continuing to push it forward - OSPM24
• Demystifying Proxy Execution - LPC24
• Tired of Proxy Execution talks? - OSPM25
• Can ProxyExec and sched_ext get along? - LPC25

Relevant upstream LKML patch submissions:

• Preparatory changes for Proxy Execution (merged upstream)
• Single RunQueue Proxy Execution (merged upstream)
• Donor Migration for Proxy Execution

Full Proxy Execution patch series applied to android17-6.18:

• Gerrit Submission for Proxy Execution