A case for lease-based, utilitarian resource management on mobile devices

~ Adrian Colyer

A case for lease-based, utilitarian resource management on mobile devices Hu et al., ASPLOS’19

I’ve chosen another energy-related paper to end the week, addressing a problem many people can relate to: apps that drain your battery. LeaseOS borrows the concept of a lease from distributed systems, but with a rather nice twist, and is able to reduce power wastage by 92% with no disruption to application experience and no changes required to the apps themselves.

So about that twist. LeaseOS injects a transparent proxy between an app and a power-hungry OS resource. The app thinks it has control of the resource until it releases it, but under the covers the proxy is given a lease. In a traditional leasing scheme, it’s up to the borrower to request a lease extension. But here half the problem is that apps are requesting expensive resources they don’t really need. So instead the OS monitors how wisely the leased resource is being used. If an app is making good, legitimate use of the resource then the lease will be transparently extended. If it isn’t, it loses the underlying resource. How you tell whether or not an app is being a wise steward of a resource is an interesting question we’ll get into…

A severe type of defect developers frequently introduce in their apps is energy bugs that drain battery abnormally fast. For example, wakelock is a mechanism in Android for apps to instruct the OS to keep the CPU, screen, WiFi, radio, etc. on active state… State-of-the-art runtime techniques monitor app resource usage, and kill or throttle apps if the usage exceeds a threshold. But making heavy use of a resource does not necessarily imply misbehavior. There are legitimate scenarios where the usage is justified, e.g. for navigation or gaming.

Wasted energy

The underlying abstract model for resource usage in mobile OSes is an ask-use-release cycle. An app asks for (or tries to acquire) a resource, and assuming the resource is granted the app then uses the resource to do some work, before finally releasing it. If an app gets resources it doesn’t really need, or forgets to free thus holding onto resources much longer than it really needs, then this can place excessive drain on the battery. For example, the K-9 mail app on Android had a bug whereby it would enter an infinite retry loop when the network was disconnected or a mail server failed. For each retry, the app would acquire a wakelock, causing severe battery drain. The BetterWeather app had a similar energy failure mode when it couldn’t get a GPS signal (e.g., the phone was inside a building). It would keep searching non-stop, but never find a signal. The graph below is a one-hour trace from the BetterWeather app running on a Nexus phone inside a building.

The app spends about 60% of its time asking for a GPS lock which it never gets. Since the app doesn’t update it’s display without a location, all of this battery drain results in no benefit to the end user at all. BetterWeather is an example of misbehaviour in the ‘ask’ phase.

The K-9 mail case is an example of misbehaviour in the ‘use’ phase. You can see in the charts below that it is holding a wakelock for a long time, but not actively using it for most of that time (the CPU usage spikes on the bottom chart).

This ultralow utilization (< 1%) pattern is consistent across different phones and ecosystems in our experiments.

High utilisation does not necessarily mean things are good though. When disconnected from the network, K-9 mail had another failure mode in which use of the wakelock is even higher, but usage of the CPU is also high.

But the truth behind the chart is that the app is stuck in an exception loop of wakelock acquisition, network request, and error handling without making any progress. So the utility to the end user is zero.

(Un)wise stewards

The authors identify four different classes of energy misbehaviour, three of which can be detected automatically.

  • In Frequent Ask Behaviour (FAB), an app frequently tries to acquire a resource but rarely get its
  • In Long Holding Behaviour (LHB) an app is granted a resource and holds it for a long time but rarely uses it
  • In Low Utility Behaviour (LUB) an app uses the granted resource for a long time to do a lot of work, but most of the work is no use
  • In Excessive Use Behaviour (EUB) an app does a lot of useful work but incurs high overhead

Frequent ask behaviour can be identified through a low resource request success ratio (unsuccessful request time / total request time). Long holding behaviour can be identified through a low usage to hold time ratio (resource usage time / holding time), and low utility behaviour can be identified through a low utility rate (utility score / resource usage time). Excessive use behaviour is hard to separate from desired behaviour though.

The authors analyse 109 energy misbehaviour cases across 81 popular apps to determine the distribution of causes according to this classification.

All four types of misbehavior are prevalent. FAB, LHB, and LUB together occupy 58% of the studied cases while EUB occupies 31% of the cases. The majority (80%) of FAB, LHB, and LUB are due to clear programming mistakes (Bug), while the majority (77%) of EUB are due to design trade-offs (non-Bug).

Earn my trust

LeaseOS transparently creates leases when an app first access an object. During the lease term, the lease holder has the right to access the resource instance without approvals from the OS. At the end of the term, the OS decides whether or not to renew the lease.

If an app explicitly releases a resource, then the lease term is ended immediately. Otherwise LeaseOS examines the collected utility metrics when a lease expires. For normal behaviour, the lease is automatically extended. Under misbehaviour the lease enters a deferred state which extends the lease after some delay r. During the delay period the underlying resource is temporarily released to reduce wasteful energy consumption.

This continuous examine-renew model differentiates LeaseOS from other simple one-shot throttling solutions.

The statistics that LeaseOS collects to determine utility are particular to the resource type but all follow a pattern. For wakelock for example LeaseOS examines the ratio of CPU over wakelock holding time. For low-utility behaviour the definition may be app specific (and a cooperative developer can provide a utility callback), but some general heuristics still prove pretty useful, e.g. the frequency of exceptions raised.

Transparent lease proxies sit in front of protected resources and coordinate with a lease manager that gathers stats and makes expire-renew decisions.

For an app that legitimately tries to use a resource with an expired lease, the main difference it will see is a slowdown while the underlying resource is re-acquired. It’s also possible for the app to see e.g. I/O exceptions on network timeouts, but the app is already required to handle these.

There’s a trade-off between lease length (short leases can save more energy) and the lease management overhead. After some empirical experiments, LeaseOS sets the default lease term at 5 seconds, and the default deferred interval (r) at 25 seconds. If an app has been using resources efficiently, the lease manager increases the lease term, reverting back to the 5-second lease on any sign of misbehaviour.

Extra hours

The authors reproduce 20 energy bug cases from real-world apps and evaluate them under LeaseOS, the Android Doze mode, DefDroid (which uses simple throttling). Android’s Doze mode defers app background CPU and network activity when the device is unused for a long time, but is very conservative in when it triggers as it is a system-wide mode. For this experiment Doze mode is forced to kick-in through the command-line adb interface, otherwise it only takes effect in 8 cases.

LeaseOS can significantly reduce the wasted power consumption for all cases, achieving an average reduction ratio of 92%… For all of the cases we evaluated, LeaseOS did not introduce any negative usability impact.

Testing with apps that legitimately make heavy use of resources (RunKeeper, Spotify, and Haven), LeaseOS renews leases without any interruption, whereas under the pure throttling scheme all three apps experienced some disruption.

The overhead of LeaseOS itself is less than 1%.

An end-to-end test with one buggy GPS app in the system, playing music for 2 hours, watching YouTube for one hour, browsing for 30 minutes, and then keeping the phone on standby showed that Android ran out of battery after around 12 hours. With LeaseOS, the battery lasted for 15 hours.

You can find the LeaseOS source code at https://orderlab.io/LeaseOS