1page.title=Avoiding Priority Inversion 2@jd:body 3 4<!-- 5 Copyright 2013 The Android Open Source Project 6 7 Licensed under the Apache License, Version 2.0 (the "License"); 8 you may not use this file except in compliance with the License. 9 You may obtain a copy of the License at 10 11 http://www.apache.org/licenses/LICENSE-2.0 12 13 Unless required by applicable law or agreed to in writing, software 14 distributed under the License is distributed on an "AS IS" BASIS, 15 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 16 See the License for the specific language governing permissions and 17 limitations under the License. 18--> 19<div id="qv-wrapper"> 20 <div id="qv"> 21 <h2>In this document</h2> 22 <ol id="auto-toc"> 23 </ol> 24 </div> 25</div> 26 27<p> 28This article explains how the Android's audio system attempts to avoid 29priority inversion, as of the Android 4.1 release, 30and highlights techniques that you can use too. 31</p> 32 33<p> 34These techniques may be useful to developers of high-performance 35audio apps, OEMs, and SoC providers who are implementing an audio 36HAL. Please note implementing these techniques is not 37guaranteed to prevent glitches or other failures, particularly if 38used outside of the audio context. 39Your results may vary, and you should conduct your own 40evaluation and testing. 41</p> 42 43<h2 id="background">Background</h2> 44 45<p> 46The Android AudioFlinger audio server and AudioTrack/AudioRecord 47client implementation are being re-architected to reduce latency. 48This work started in Android 4.1, continued in 4.2 and 4.3, and now more 49improvements exist in version 4.4. 50</p> 51 52<p> 53To achieve this lower latency, many changes were needed throughout the system. One 54important change is to assign CPU resources to time-critical 55threads with a more predictable scheduling policy. Reliable scheduling 56allows the audio buffer sizes and counts to be reduced while still 57avoiding artifacts due to underruns. 58</p> 59 60<h2 id="priorityInversion">Priority inversion</h2> 61 62<p> 63<a href="http://en.wikipedia.org/wiki/Priority_inversion">Priority inversion</a> 64is a classic failure mode of real-time systems, 65where a higher-priority task is blocked for an unbounded time waiting 66for a lower-priority task to release a resource such as (shared 67state protected by) a 68<a href="http://en.wikipedia.org/wiki/Mutual_exclusion">mutex</a>. 69</p> 70 71<p> 72In an audio system, priority inversion typically manifests as a 73<a href="http://en.wikipedia.org/wiki/Glitch">glitch</a> 74(click, pop, dropout), 75<a href="http://en.wikipedia.org/wiki/Max_Headroom_(character)">repeated audio</a> 76when circular buffers 77are used, or delay in responding to a command. 78</p> 79 80<p> 81In the Android audio implementation, priority inversion is most 82likely to occur in these places. And so you should focus your attention here: 83</p> 84 85<ul> 86 87<li> 88between normal mixer thread and fast mixer thread in AudioFlinger 89</li> 90 91<li> 92between application callback thread for a fast AudioTrack and 93fast mixer thread (they both have elevated priority, but slightly 94different priorities) 95</li> 96 97<li> 98within the audio Hardware Abstraction Layer (HAL) implementation, e.g. for telephony or echo cancellation 99</li> 100 101<li> 102within the audio driver in kernel 103</li> 104 105<li> 106between AudioTrack callback thread and other app threads (this is out of our control) 107</li> 108 109</ul> 110 111<p> 112As of this writing, reduced latency for AudioRecord is planned but 113not yet implemented. The likely priority inversion spots will be 114similar to those for AudioTrack. 115</p> 116 117<h2 id="commonSolutions">Common solutions</h2> 118 119<p> 120The typical solutions include: 121</p> 122 123<ul> 124 125<li> 126disabling interrupts 127</li> 128 129<li> 130priority inheritance mutexes 131</li> 132 133</ul> 134 135<p> 136Disabling interrupts is not feasible in Linux user space, and does 137not work for Symmetric Multi-Processors (SMP). 138</p> 139 140 141<p> 142Priority inheritance 143<a href="http://en.wikipedia.org/wiki/Futex">futexes</a> 144(fast user-space mutexes) are available 145in Linux kernel, but are not currently exposed by the Android C 146runtime library 147<a href="http://en.wikipedia.org/wiki/Bionic_(software)">Bionic</a>. 148They are not used in the audio system because they are relatively heavyweight, 149and because they rely on a trusted client. 150</p> 151 152<h2 id="androidTechniques">Techniques used by Android</h2> 153 154<p> 155Experiments started with "try lock" and lock with timeout. These are 156non-blocking and bounded blocking variants of the mutex lock 157operation. Try lock and lock with timeout worked fairly well but were 158susceptible to a couple of obscure failure modes: the 159server was not guaranteed to be able to access the shared state if 160the client happened to be busy, and the cumulative timeout could 161be too long if there was a long sequence of unrelated locks that 162all timed out. 163</p> 164 165 166<p> 167We also use 168<a href="http://en.wikipedia.org/wiki/Linearizability">atomic operations</a> 169such as: 170</p> 171 172<ul> 173<li>increment</li> 174<li>bitwise "or"</li> 175<li>bitwise "and"</li> 176</ul> 177 178<p> 179All of these return the previous value and include the necessary 180SMP barriers. The disadvantage is they can require unbounded retries. 181In practice, we've found that the retries are not a problem. 182</p> 183 184<p class="note"><strong>Note:</strong> Atomic operations and their interactions with memory barriers 185are notoriously badly misunderstood and used incorrectly. We include these methods 186here for completeness but recommend you also read the article 187<a href="https://developer.android.com/training/articles/smp.html"> 188SMP Primer for Android</a> 189for further information. 190</p> 191 192<p> 193We still have and use most of the above tools, and have recently 194added these techniques: 195</p> 196 197<ul> 198 199<li> 200Use non-blocking single-reader single-writer 201<a href="http://en.wikipedia.org/wiki/Circular_buffer">FIFO queues</a> 202for data. 203</li> 204 205<li> 206Try to 207<i>copy</i> 208state rather than 209<i>share</i> 210state between high- and 211low-priority modules. 212</li> 213 214<li> 215When state does need to be shared, limit the state to the 216maximum-size 217<a href="http://en.wikipedia.org/wiki/Word_(computer_architecture)">word</a> 218that can be accessed atomically in one-bus operation 219without retries. 220</li> 221 222<li> 223For complex multi-word state, use a state queue. A state queue 224is basically just a non-blocking single-reader single-writer FIFO 225queue used for state rather than data, except the writer collapses 226adjacent pushes into a single push. 227</li> 228 229<li> 230Pay attention to 231<a href="http://en.wikipedia.org/wiki/Memory_barrier">memory barriers</a> 232for SMP correctness. 233</li> 234 235<li> 236<a href="http://en.wikipedia.org/wiki/Trust,_but_verify">Trust, but verify</a>. 237When sharing 238<i>state</i> 239between processes, don't 240assume that the state is well-formed. For example, check that indices 241are within bounds. This verification isn't needed between threads 242in the same process, between mutual trusting processes (which 243typically have the same UID). It's also unnecessary for shared 244<i>data</i> 245such as PCM audio where a corruption is inconsequential. 246</li> 247 248</ul> 249 250<h2 id="nonBlockingAlgorithms">Non-blocking algorithms</h2> 251 252<p> 253<a href="http://en.wikipedia.org/wiki/Non-blocking_algorithm">Non-blocking algorithms</a> 254have been a subject of much recent study. 255But with the exception of single-reader single-writer FIFO queues, 256we've found them to be complex and error-prone. 257</p> 258 259<p> 260Starting in Android 4.2, you can find our non-blocking, 261single-reader/writer classes in these locations: 262</p> 263 264<ul> 265 266<li> 267frameworks/av/include/media/nbaio/ 268</li> 269 270<li> 271frameworks/av/media/libnbaio/ 272</li> 273 274<li> 275frameworks/av/services/audioflinger/StateQueue* 276</li> 277 278</ul> 279 280<p> 281These were designed specifically for AudioFlinger and are not 282general-purpose. Non-blocking algorithms are notorious for being 283difficult to debug. You can look at this code as a model. But be 284aware there may be bugs, and the classes are not guaranteed to be 285suitable for other purposes. 286</p> 287 288<p> 289For developers, some of the sample OpenSL ES application code should be updated to 290use non-blocking algorithms or reference a non-Android open source library. 291</p> 292 293<h2 id="tools">Tools</h2> 294 295<p> 296To the best of our knowledge, there are no automatic tools for 297finding priority inversion, especially before it happens. Some 298research static code analysis tools are capable of finding priority 299inversions if able to access the entire codebase. Of course, if 300arbitrary user code is involved (as it is here for the application) 301or is a large codebase (as for the Linux kernel and device drivers), 302static analysis may be impractical. The most important thing is to 303read the code very carefully and get a good grasp on the entire 304system and the interactions. Tools such as 305<a href="http://developer.android.com/tools/help/systrace.html">systrace</a> 306and 307<code>ps -t -p</code> 308are useful for seeing priority inversion after it occurs, but do 309not tell you in advance. 310</p> 311 312<h2 id="aFinalWord">A final word</h2> 313 314<p> 315After all of this discussion, don't be afraid of mutexes. Mutexes 316are your friend for ordinary use, when used and implemented correctly 317in ordinary non-time-critical use cases. But between high- and 318low-priority tasks and in time-sensitive systems mutexes are more 319likely to cause trouble. 320</p> 321 322