On Sat, Aug 9, 2014 at 6:04 AM, Mike Galbraith <umgwanakikb...@gmail.com> wrote:
> You are not going to convince me that it is cool to assign an imaginary > priority to a SCHED_FIFO class task, and still call the resulting mutant > a SCHED_FIFO class task. Those things have defines semantics. It is > not ok for a SCHED_FIFO task of a lower priority to completely ignore a > SCHED_FIFO task of a higher priority because it's part of an application > which has one or more wild cards I am not quite sure what you were trying to say by this, but I am grateful to you for expressing your perspective and arguments in this discussion. For one thing, it stimulated me to perform systematic review of the solution space/tree, square inch by square inch, resulting in exhaustive logical coverage of the solution space and thus an informal logical proof that there is no any uncovered subspace that might hold any undiscovered yet solution. Just so the results do not remain scattered, I will try to summarize and categorize the findings about available solutions to the general "critical section (or critical activity) preemption" problem category, and then draw a conclusion stemming from this summary. ********************** 1) Post-preemption solutions. (Such as priority inheritance or proxy execution, or even humble yield_to). By the time a post-preemption solution is engaged, a cost had already been paid, and further cost is paid to execute the solution. Sometimes this aggregate cost can be small and acceptable within the overall context of an application, sometimes it can be too high. Sometimes dependency chain cannot be expressed and thus post-preemption solution is not possible at all (other than just waiting for the scheduler to eventually resume the blocking thread and keeping paying the cost in the meanwhile). I won't be further enumerating this subcategory here and will focus instead on the space of preemption avoidance/deferral solutions. ********************** 2) Reduction in the incidence of thread preemption. There are chief ways to reduce the incidence of thread preemption. One way is by enlarging the scheduling quantum. Its simplistic use however may well backfire: if a lock holder is preempted while holding a lock (or thread executing non-lock-related critical activity is preempted while inside this activity) enlarged scheduling quantum would result in longer delay before the thread will get resumed. Therefore this measure if employed should really be coupled with one of post-preemption solutions. Another way is the reduction of thread preemption incidence due to another thread being woken up. Currently existing schemes of this kind (use of !WAKEUP_PREEMPTION or SCHED_BATCH) are indiscriminate and victimize woken up thread for the sake of executing thread regardless of whether the latter is inside a critical section or not, however means can be provided to refine this behavior and victimize the wakee only in case if currently executing thread is actually inside a critical section. (And also when the section is exited, to switch over to the postponed wakee ASAP). A variation on this theme is an attempt at mitigation of preemption effects via LAST_BUDDY. The extent to which this scheme will be effective or not is obviously determined by the following factors. First, the probability of thread preemption while it is holding a lock, which in turn is determined by: (a) Percentage of time a worker thread holds a lock (or executes non-lock related critical activity). It does not matter too much whether a thread enters a critical section one time, stays in it for a while and then exits or whether the thread enters and exits a critical section many times in a row staying within it each time only a for very short instant. What matters is the aggregate percentage of execution time a thread spends while inside a critical section. This yields a rough probability any random preemption of a thread (either through natural expiration of scheduling timeslice or due to the preemption by a wakee) will result in lock holder or other critical activity preemption. (b) To an extent, request handler execution time. Very short times (well under typical scheduling quantum) separated by voluntary yielding (such as when waiting on the queue to pick up the next processing request) would result in reduced preemption probability due to end-of-quantum events, however I won't be further considering this special case here. (It is also not a particularly good idea to use FIFO ordering for dequeueing of events or requests from a queue by worker threads, as opposed to LIFO ordering, as it negatively impacts cache locality and increases context switch probability.) (c) Reduction in preemption attempt frequency. That's where the impact of the discussed scheme comes in. With the scheme on, thread gets chiefly preempted on quantum expiration, but not intra-quantum in favor of wakee threads. The product of probabilities (a) and (c) determines how likely the thread is to be preempted while inside a critical section/activity. Second factor is the contention rate on a lock a preempted thread is holding (or dependency occurrence rate for non-lock-related critical activities). It defines whether the preemption is important in the aftermath of the pre-emption, i.e. how likely it is to lead to an actual blocking of other threads forward progress by the preemptee. Third factor is the cost of post-preemption recovery response, and whether such response is possible at all (i.e. whether dependency chain can be expressed at run time). Factor (c) depends on the frequency of the wakeups. If a worker thread performs multiple synchronous IO requests or other OS-level blocking operations within a timeslice, then probability of those completing within a buddy's timeslice is significant. Thus for example database engine with low cache pool size and not utilizing async processing model (akin to nginx or node.js models) may have high incidence of wakeups within a buddy's timeslice due to the completion of synchronous IO requests or other blocking waits. However a worker thread on the same database but configured with larger cache size (so IO rate is low), or a worker thread in in-memory database, or a worker thread in conventional database but utilizing async execution model will have low incidence of wakeups within a buddy's timeslice, and in those case the use of the discussed scheme won't make much improvement since all the improvement it could have produced is already "in". After any possible improvement yield from the discussed scheme is factored in, the residual remains about the preemption at the end of timeslice, with performance impact defined by the probability of preempted thread holding a lock or executing other critical activity, i.e. factor (a), contention rate (factor 2) and the cost of post-preemption recovery response (factor 3), and whether such response is possible at all. This situation can essentially be exemplified by a classic case of user-mode spinlock or hybrid spin-then-block lock discussed earlier (https://lkml.org/lkml/2014/8/2/130). If the product of listed factors is significant then the solution that attempts to reduce the incidence of preemption may be effective in this goal or not, but the residual cost still remains high and system responsiveness possibly choppy. If reliance on post-preemption solution [*] is impossible because the structure of the application does not allow to express the dependency chain at run time (due to the use of 3rd party components, legacy components, or components out of the scope of the project etc.), the inflicted cost may be particularly high. [*] Or in LAST_BUDDY case, if the wakee thread does not yield voluntarily very fast. The discussed solution (reduction in the incidence of thread preemption) also does not address those applications that have critical section of different importance, some highly critical and others moderately critical or of low criticality. Within the discussed solution scheme, there is no provisioning for multiple levels of protection of application threads relative to each other, nor relative to other threads in the system. This solution also does not support "urgent handoff" scenario, in which thread A sends to thread B a message requiring urgent processing, and thus a critical section in thread B is effectively initiated from the outside of the thread. (An example is virtual machine application in which VCPU thread sends an IPI interrupt to another VCPU thread, or virtual device handler sends an interrupt to a VCPU thread, an interrupt that requires prompt processing or a cost will be incurred.) ********************** 3) schedctl / preempt_delay / remaining_timeslice This solution allows a thread to get a temporary reprieve from preemption by another thread of similar scheduling policy. Protection interval can be specified explicitly (in proposed prempt_delay patch) or defaulted to a scheduling quantum (in Solaris/AIX schedctl), the purpose of the latter being to avoid a preemption of a critical section of sub-timeslice duration that was started close to the end of the timeslice. Another variation of the same theme is to let a thread know how much time it has before the expiration of the current timeslice. If the remaining time is insufficient to complete a critical section, thread can yield and execute the section when yield(...) returns, starting at the beginning of a new timeslice. (The obvious drawbacks of this latter approach being more frequent yields, scheduler calculations and context switches, more heavy reliance on the estimate of the critical section duration, and more difficult management of nested critical sections.) Three shared drawbacks/limitations of this kind of solutions: a) They do not support applications having critical sections with multiple levels of criticality, i.e. capability for section priority ranging relative to the context of the whole application nor other processes in the system. b) They do not support "urgent handoff" scenarios. c) An application may need to perform time-urgent processing without knowing in advance how long it will take. In the majority of cases the processing may be very short (a fraction of a scheduling timeslice), but occasionally may take longer (several timeslices). Preempt_delay does provide a way to address it, but schedctl and remaining_timeslice do not. ********************** 4) Conventional old-fashioned priority protection. Drawbacks: Potentially stronger interference with other tasks than in the solutions discussed earlier, but more importantly not confined to a "jail" well-manageable by system owner/administrator. Strengths: - efficient and well-defined intra-application preemption control - support for multiple levels of criticality for locks or time-urgent sections - support for urgent handoff ********************** 5) Scheduling based on a cost function expressing critical section information assigned at development time or dynamically collected at run time and representative of actual cost of preemption https://lkml.org/lkml/2014/8/6/593 https://lkml.org/lkml/2014/8/8/492 As discussed, not pragmatically attainable. ********************** 6) Using a scheduling class with the properties and controls matching the demands of the problem and relying on manual tuning of the system by its owner/administrator to balance the interference between multiple application to a relative degree desired by the administrator, while at the same time maintaining the applications inopportune preemption frequency (displayed in system statistics) within the bounds of an acceptable for the administrator. The system provides control and monitoring tools, but it is left up to the administrator to strike the balance between the applications which seems best to him. The description here https://lkml.org/lkml/2014/8/9/37 summarizes the requirements and outlines a comprehensive solution, but as formulated there (based on the assumption of adding a new scheduling class -- which is not really necessary, see below), requires high added complexity. ********************** This exhausts the solution space. Everything logically possible has been covered, and no other solution not falling into one of described categories can logically exist. There are certainly cases that can be satisfactorily addressed with options (1), (2) or (3), but there are also those that cannot. For those, the remaining options are (4) or (6) or do nothing. Which brings us back to option (6) ... At a closer look, option (6) as formulated in the original message is tantamount to creation of RT-like range sitting just below regular RT range but "caged" and better controllable, i.e. having additional controls vs. impact on other applications and also additional statistics. The creation of such range is where most of the complexity would have to come from if it were to be created indeed. The obvious question however is why to create separate "low RT-like" range instead of simply using low part of existing RT range, but with added controls and statistics. The most important control -- a limit on the aggregate time application's threads can spend in preemption-protected mode as the share (percentage) of overall system time -- is already implemented by RT, as rt_bandwidth of a task group. The following pieces are missing, but can be provided: a) Dynamic proportional scale-down of the bandwidths of multiple groups when their aggregate demand starts to exceed system-wide limit. b) When a group's RT use limit is exceeded, perhaps group's RT threads should be allowed to continue as SCHED_NORMAL threads, rather than being stalled till the next bandwidth period. c) Per-group statistics on denial of set_priority(RT) to the group's threads and on throttling of the group's threads because of the group exceeding its quota of RT use. This statistics should be accessible to administrative tools and to the application itself. d) [Non-essential:] Maximum duration a thread within a group can stay at elevated priority. This is merely a safeguard against the runaways threads and is not essential, as group's RT bandwidth control allows an administrator to take a corrective action. e) Finally, the last issue is how priority range of APP1 can be stacked against the priority range of APP2 and the latter against the priority range of APP3 and so on. The decision about their relative positioning is, by the definition of (6), a judgment call of a system administrator/owner. Making such judgment may be hard, but this difficulty is inherent in co-running multiple applications each further possibly having critical section of multiple levels of criticality. Option (5) would have helped to address this ranging/balancing issue but unfortunately it is not pragmatically/economically attainable. Thus the only recourse is to lay the decision on the shoulders of a system administrator, however there is a question of the supporting mechanisms an administrator can employ in making and implementing his decision. One instrument is monitoring tools as outlined in (c). The other is some way of fitting applications' priority ranges together. One possible approach could be to define cgroup-specific priority map mapping task priority levels between group-relative level scale and system-wide level scale. However maintaining multiple scales can be confusing and also cause ambiguity during reverse translation when performing get_priority(), so perhaps an easier and more straightforward way would be a requirement that a compliant application should simply define its priority levels in an editable configuration file, and perhaps also provide a method to reload this file if an administrator wants to perform a dynamic adjustment without restarting the application. ********************** Conclusion: I disagree with blanket indictment of the use of RT priority for the sake of managing critical or time-urgent sections as "subversion" of RT mechanism -- I do not see a rational argument for such a blanket indictment. The judicious use of RT matches the primary express purpose of the facilities intended to support the execution of critical sections: temporarily victimize lower-importance threads for the sake of higher-importance threads (with their relative importance being dynamic). However I do agree that a better controlled (including better manageable/tunable by system owner), "caged" use of "tamed" RT would be desirable. That's what option (6) would provide if implemented, and what can now be partially provided by option (4) + per-cgroup quota on rt_bandwidth. General conclusion of this overview is that solutions space for the overall issue of executing critical/time-urgent sections is fragmented (and even problem space itself is fragmented too). There is no single "holy grail" solution that would address all use cases and use modes. Given this, the right approach for an operating system would be to provide a set of alternative mechanisms that expose various solutions (some of which may also happen to be complementary in certain use cases) that in their entirety address the whole space of use cases, and then let an application developer and system owner decide between themselves which exact mechanisms are most suitable for a particular purpose. As for DPRIO in this context, DPRIO is a supplementary cost-reduction mechanism usable with options (4) and (6) in high-frequency scenarios. - Sergey -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
