diff options
Diffstat (limited to 'Documentation/scheduler')
| -rw-r--r-- | Documentation/scheduler/00-INDEX | 6 | ||||
| -rw-r--r-- | Documentation/scheduler/sched-arch.txt | 19 | ||||
| -rw-r--r-- | Documentation/scheduler/sched-bwc.txt | 122 | ||||
| -rw-r--r-- | Documentation/scheduler/sched-deadline.txt | 281 | ||||
| -rw-r--r-- | Documentation/scheduler/sched-design-CFS.txt | 78 | ||||
| -rw-r--r-- | Documentation/scheduler/sched-domains.txt | 38 | ||||
| -rw-r--r-- | Documentation/scheduler/sched-nice-design.txt | 2 | ||||
| -rw-r--r-- | Documentation/scheduler/sched-rt-group.txt | 30 | ||||
| -rw-r--r-- | Documentation/scheduler/sched-stats.txt | 34 |
9 files changed, 472 insertions, 138 deletions
diff --git a/Documentation/scheduler/00-INDEX b/Documentation/scheduler/00-INDEX index 3c00c9c3219..eccf7ad2e7f 100644 --- a/Documentation/scheduler/00-INDEX +++ b/Documentation/scheduler/00-INDEX @@ -2,13 +2,17 @@ - this file. sched-arch.txt - CPU Scheduler implementation hints for architecture specific code. +sched-bwc.txt + - CFS bandwidth control overview. sched-design-CFS.txt - - goals, design and implementation of the Complete Fair Scheduler. + - goals, design and implementation of the Completely Fair Scheduler. sched-domains.txt - information on scheduling domains. sched-nice-design.txt - How and why the scheduler's nice levels are implemented. sched-rt-group.txt - real-time group scheduling. +sched-deadline.txt + - deadline scheduling. sched-stats.txt - information on schedstats (Linux Scheduler Statistics). diff --git a/Documentation/scheduler/sched-arch.txt b/Documentation/scheduler/sched-arch.txt index d43dbcbd163..a2f27bbf2cb 100644 --- a/Documentation/scheduler/sched-arch.txt +++ b/Documentation/scheduler/sched-arch.txt @@ -8,7 +8,7 @@ Context switch By default, the switch_to arch function is called with the runqueue locked. This is usually not a problem unless switch_to may need to take the runqueue lock. This is usually due to a wake up operation in -the context switch. See arch/ia64/include/asm/system.h for an example. +the context switch. See arch/ia64/include/asm/switch_to.h for an example. To request the scheduler call switch_to with the runqueue unlocked, you must `#define __ARCH_WANT_UNLOCKED_CTXSW` in a header file @@ -17,16 +17,6 @@ you must `#define __ARCH_WANT_UNLOCKED_CTXSW` in a header file Unlocked context switches introduce only a very minor performance penalty to the core scheduler implementation in the CONFIG_SMP case. -2. Interrupt status -By default, the switch_to arch function is called with interrupts -disabled. Interrupts may be enabled over the call if it is likely to -introduce a significant interrupt latency by adding the line -`#define __ARCH_WANT_INTERRUPTS_ON_CTXSW` in the same place as for -unlocked context switches. This define also implies -`__ARCH_WANT_UNLOCKED_CTXSW`. See arch/arm/include/asm/system.h for an -example. - - CPU idle ======== Your cpu_idle routines need to obey the following rules: @@ -66,7 +56,7 @@ Your cpu_idle routines need to obey the following rules: barrier issued (followed by a test of need_resched with interrupts disabled, as explained in 3). -arch/i386/kernel/process.c has examples of both polling and +arch/x86/kernel/process.c has examples of both polling and sleeping idle functions. @@ -75,11 +65,6 @@ Possible arch/ problems Possible arch problems I found (and either tried to fix or didn't): -h8300 - Is such sleeping racy vs interrupts? (See #4a). - The H8/300 manual I found indicates yes, however disabling IRQs - over the sleep mean only NMIs can wake it up, so can't fix easily - without doing spin waiting. - ia64 - is safe_halt call racy vs interrupts? (does it sleep?) (See #4a) sh64 - Is sleeping racy vs interrupts? (See #4a) diff --git a/Documentation/scheduler/sched-bwc.txt b/Documentation/scheduler/sched-bwc.txt new file mode 100644 index 00000000000..f6b1873f68a --- /dev/null +++ b/Documentation/scheduler/sched-bwc.txt @@ -0,0 +1,122 @@ +CFS Bandwidth Control +===================== + +[ This document only discusses CPU bandwidth control for SCHED_NORMAL. + The SCHED_RT case is covered in Documentation/scheduler/sched-rt-group.txt ] + +CFS bandwidth control is a CONFIG_FAIR_GROUP_SCHED extension which allows the +specification of the maximum CPU bandwidth available to a group or hierarchy. + +The bandwidth allowed for a group is specified using a quota and period. Within +each given "period" (microseconds), a group is allowed to consume only up to +"quota" microseconds of CPU time. When the CPU bandwidth consumption of a +group exceeds this limit (for that period), the tasks belonging to its +hierarchy will be throttled and are not allowed to run again until the next +period. + +A group's unused runtime is globally tracked, being refreshed with quota units +above at each period boundary. As threads consume this bandwidth it is +transferred to cpu-local "silos" on a demand basis. The amount transferred +within each of these updates is tunable and described as the "slice". + +Management +---------- +Quota and period are managed within the cpu subsystem via cgroupfs. + +cpu.cfs_quota_us: the total available run-time within a period (in microseconds) +cpu.cfs_period_us: the length of a period (in microseconds) +cpu.stat: exports throttling statistics [explained further below] + +The default values are: + cpu.cfs_period_us=100ms + cpu.cfs_quota=-1 + +A value of -1 for cpu.cfs_quota_us indicates that the group does not have any +bandwidth restriction in place, such a group is described as an unconstrained +bandwidth group. This represents the traditional work-conserving behavior for +CFS. + +Writing any (valid) positive value(s) will enact the specified bandwidth limit. +The minimum quota allowed for the quota or period is 1ms. There is also an +upper bound on the period length of 1s. Additional restrictions exist when +bandwidth limits are used in a hierarchical fashion, these are explained in +more detail below. + +Writing any negative value to cpu.cfs_quota_us will remove the bandwidth limit +and return the group to an unconstrained state once more. + +Any updates to a group's bandwidth specification will result in it becoming +unthrottled if it is in a constrained state. + +System wide settings +-------------------- +For efficiency run-time is transferred between the global pool and CPU local +"silos" in a batch fashion. This greatly reduces global accounting pressure +on large systems. The amount transferred each time such an update is required +is described as the "slice". + +This is tunable via procfs: + /proc/sys/kernel/sched_cfs_bandwidth_slice_us (default=5ms) + +Larger slice values will reduce transfer overheads, while smaller values allow +for more fine-grained consumption. + +Statistics +---------- +A group's bandwidth statistics are exported via 3 fields in cpu.stat. + +cpu.stat: +- nr_periods: Number of enforcement intervals that have elapsed. +- nr_throttled: Number of times the group has been throttled/limited. +- throttled_time: The total time duration (in nanoseconds) for which entities + of the group have been throttled. + +This interface is read-only. + +Hierarchical considerations +--------------------------- +The interface enforces that an individual entity's bandwidth is always +attainable, that is: max(c_i) <= C. However, over-subscription in the +aggregate case is explicitly allowed to enable work-conserving semantics +within a hierarchy. + e.g. \Sum (c_i) may exceed C +[ Where C is the parent's bandwidth, and c_i its children ] + + +There are two ways in which a group may become throttled: + a. it fully consumes its own quota within a period + b. a parent's quota is fully consumed within its period + +In case b) above, even though the child may have runtime remaining it will not +be allowed to until the parent's runtime is refreshed. + +Examples +-------- +1. Limit a group to 1 CPU worth of runtime. + + If period is 250ms and quota is also 250ms, the group will get + 1 CPU worth of runtime every 250ms. + + # echo 250000 > cpu.cfs_quota_us /* quota = 250ms */ + # echo 250000 > cpu.cfs_period_us /* period = 250ms */ + +2. Limit a group to 2 CPUs worth of runtime on a multi-CPU machine. + + With 500ms period and 1000ms quota, the group can get 2 CPUs worth of + runtime every 500ms. + + # echo 1000000 > cpu.cfs_quota_us /* quota = 1000ms */ + # echo 500000 > cpu.cfs_period_us /* period = 500ms */ + + The larger period here allows for increased burst capacity. + +3. Limit a group to 20% of 1 CPU. + + With 50ms period, 10ms quota will be equivalent to 20% of 1 CPU. + + # echo 10000 > cpu.cfs_quota_us /* quota = 10ms */ + # echo 50000 > cpu.cfs_period_us /* period = 50ms */ + + By using a small period here we are ensuring a consistent latency + response at the expense of burst capacity. + diff --git a/Documentation/scheduler/sched-deadline.txt b/Documentation/scheduler/sched-deadline.txt new file mode 100644 index 00000000000..18adc92a6b3 --- /dev/null +++ b/Documentation/scheduler/sched-deadline.txt @@ -0,0 +1,281 @@ + Deadline Task Scheduling + ------------------------ + +CONTENTS +======== + + 0. WARNING + 1. Overview + 2. Scheduling algorithm + 3. Scheduling Real-Time Tasks + 4. Bandwidth management + 4.1 System-wide settings + 4.2 Task interface + 4.3 Default behavior + 5. Tasks CPU affinity + 5.1 SCHED_DEADLINE and cpusets HOWTO + 6. Future plans + + +0. WARNING +========== + + Fiddling with these settings can result in an unpredictable or even unstable + system behavior. As for -rt (group) scheduling, it is assumed that root users + know what they're doing. + + +1. Overview +=========== + + The SCHED_DEADLINE policy contained inside the sched_dl scheduling class is + basically an implementation of the Earliest Deadline First (EDF) scheduling + algorithm, augmented with a mechanism (called Constant Bandwidth Server, CBS) + that makes it possible to isolate the behavior of tasks between each other. + + +2. Scheduling algorithm +================== + + SCHED_DEADLINE uses three parameters, named "runtime", "period", and + "deadline" to schedule tasks. A SCHED_DEADLINE task is guaranteed to receive + "runtime" microseconds of execution time every "period" microseconds, and + these "runtime" microseconds are available within "deadline" microseconds + from the beginning of the period. In order to implement this behaviour, + every time the task wakes up, the scheduler computes a "scheduling deadline" + consistent with the guarantee (using the CBS[2,3] algorithm). Tasks are then + scheduled using EDF[1] on these scheduling deadlines (the task with the + smallest scheduling deadline is selected for execution). Notice that this + guaranteed is respected if a proper "admission control" strategy (see Section + "4. Bandwidth management") is used. + + Summing up, the CBS[2,3] algorithms assigns scheduling deadlines to tasks so + that each task runs for at most its runtime every period, avoiding any + interference between different tasks (bandwidth isolation), while the EDF[1] + algorithm selects the task with the smallest scheduling deadline as the one + to be executed first. Thanks to this feature, also tasks that do not + strictly comply with the "traditional" real-time task model (see Section 3) + can effectively use the new policy. + + In more details, the CBS algorithm assigns scheduling deadlines to + tasks in the following way: + + - Each SCHED_DEADLINE task is characterised by the "runtime", + "deadline", and "period" parameters; + + - The state of the task is described by a "scheduling deadline", and + a "current runtime". These two parameters are initially set to 0; + + - When a SCHED_DEADLINE task wakes up (becomes ready for execution), + the scheduler checks if + + current runtime runtime + ---------------------------------- > ---------------- + scheduling deadline - current time period + + then, if the scheduling deadline is smaller than the current time, or + this condition is verified, the scheduling deadline and the + current budget are re-initialised as + + scheduling deadline = current time + deadline + current runtime = runtime + + otherwise, the scheduling deadline and the current runtime are + left unchanged; + + - When a SCHED_DEADLINE task executes for an amount of time t, its + current runtime is decreased as + + current runtime = current runtime - t + + (technically, the runtime is decreased at every tick, or when the + task is descheduled / preempted); + + - When the current runtime becomes less or equal than 0, the task is + said to be "throttled" (also known as "depleted" in real-time literature) + and cannot be scheduled until its scheduling deadline. The "replenishment + time" for this task (see next item) is set to be equal to the current + value of the scheduling deadline; + + - When the current time is equal to the replenishment time of a + throttled task, the scheduling deadline and the current runtime are + updated as + + scheduling deadline = scheduling deadline + period + current runtime = current runtime + runtime + + +3. Scheduling Real-Time Tasks +============================= + + * BIG FAT WARNING ****************************************************** + * + * This section contains a (not-thorough) summary on classical deadline + * scheduling theory, and how it applies to SCHED_DEADLINE. + * The reader can "safely" skip to Section 4 if only interested in seeing + * how the scheduling policy can be used. Anyway, we strongly recommend + * to come back here and continue reading (once the urge for testing is + * satisfied :P) to be sure of fully understanding all technical details. + ************************************************************************ + + There are no limitations on what kind of task can exploit this new + scheduling discipline, even if it must be said that it is particularly + suited for periodic or sporadic real-time tasks that need guarantees on their + timing behavior, e.g., multimedia, streaming, control applications, etc. + + A typical real-time task is composed of a repetition of computation phases + (task instances, or jobs) which are activated on a periodic or sporadic + fashion. + Each job J_j (where J_j is the j^th job of the task) is characterised by an + arrival time r_j (the time when the job starts), an amount of computation + time c_j needed to finish the job, and a job absolute deadline d_j, which + is the time within which the job should be finished. The maximum execution + time max_j{c_j} is called "Worst Case Execution Time" (WCET) for the task. + A real-time task can be periodic with period P if r_{j+1} = r_j + P, or + sporadic with minimum inter-arrival time P is r_{j+1} >= r_j + P. Finally, + d_j = r_j + D, where D is the task's relative deadline. + + SCHED_DEADLINE can be used to schedule real-time tasks guaranteeing that + the jobs' deadlines of a task are respected. In order to do this, a task + must be scheduled by setting: + + - runtime >= WCET + - deadline = D + - period <= P + + IOW, if runtime >= WCET and if period is >= P, then the scheduling deadlines + and the absolute deadlines (d_j) coincide, so a proper admission control + allows to respect the jobs' absolute deadlines for this task (this is what is + called "hard schedulability property" and is an extension of Lemma 1 of [2]). + + References: + 1 - C. L. Liu and J. W. Layland. Scheduling algorithms for multiprogram- + ming in a hard-real-time environment. Journal of the Association for + Computing Machinery, 20(1), 1973. + 2 - L. Abeni , G. Buttazzo. Integrating Multimedia Applications in Hard + Real-Time Systems. Proceedings of the 19th IEEE Real-time Systems + Symposium, 1998. http://retis.sssup.it/~giorgio/paps/1998/rtss98-cbs.pdf + 3 - L. Abeni. Server Mechanisms for Multimedia Applications. ReTiS Lab + Technical Report. http://xoomer.virgilio.it/lucabe72/pubs/tr-98-01.ps + +4. Bandwidth management +======================= + + In order for the -deadline scheduling to be effective and useful, it is + important to have some method to keep the allocation of the available CPU + bandwidth to the tasks under control. + This is usually called "admission control" and if it is not performed at all, + no guarantee can be given on the actual scheduling of the -deadline tasks. + + Since when RT-throttling has been introduced each task group has a bandwidth + associated, calculated as a certain amount of runtime over a period. + Moreover, to make it possible to manipulate such bandwidth, readable/writable + controls have been added to both procfs (for system wide settings) and cgroupfs + (for per-group settings). + Therefore, the same interface is being used for controlling the bandwidth + distrubution to -deadline tasks. + + However, more discussion is needed in order to figure out how we want to manage + SCHED_DEADLINE bandwidth at the task group level. Therefore, SCHED_DEADLINE + uses (for now) a less sophisticated, but actually very sensible, mechanism to + ensure that a certain utilization cap is not overcome per each root_domain. + + Another main difference between deadline bandwidth management and RT-throttling + is that -deadline tasks have bandwidth on their own (while -rt ones don't!), + and thus we don't need an higher level throttling mechanism to enforce the + desired bandwidth. + +4.1 System wide settings +------------------------ + + The system wide settings are configured under the /proc virtual file system. + + For now the -rt knobs are used for dl admission control and the -deadline + runtime is accounted against the -rt runtime. We realise that this isn't + entirely desirable; however, it is better to have a small interface for now, + and be able to change it easily later. The ideal situation (see 5.) is to run + -rt tasks from a -deadline server; in which case the -rt bandwidth is a direct + subset of dl_bw. + + This means that, for a root_domain comprising M CPUs, -deadline tasks + can be created while the sum of their bandwidths stays below: + + M * (sched_rt_runtime_us / sched_rt_period_us) + + It is also possible to disable this bandwidth management logic, and + be thus free of oversubscribing the system up to any arbitrary level. + This is done by writing -1 in /proc/sys/kernel/sched_rt_runtime_us. + + +4.2 Task interface +------------------ + + Specifying a periodic/sporadic task that executes for a given amount of + runtime at each instance, and that is scheduled according to the urgency of + its own timing constraints needs, in general, a way of declaring: + - a (maximum/typical) instance execution time, + - a minimum interval between consecutive instances, + - a time constraint by which each instance must be completed. + + Therefore: + * a new struct sched_attr, containing all the necessary fields is + provided; + * the new scheduling related syscalls that manipulate it, i.e., + sched_setattr() and sched_getattr() are implemented. + + +4.3 Default behavior +--------------------- + + The default value for SCHED_DEADLINE bandwidth is to have rt_runtime equal to + 950000. With rt_period equal to 1000000, by default, it means that -deadline + tasks can use at most 95%, multiplied by the number of CPUs that compose the + root_domain, for each root_domain. + + A -deadline task cannot fork. + +5. Tasks CPU affinity +===================== + + -deadline tasks cannot have an affinity mask smaller that the entire + root_domain they are created on. However, affinities can be specified + through the cpuset facility (Documentation/cgroups/cpusets.txt). + +5.1 SCHED_DEADLINE and cpusets HOWTO +------------------------------------ + + An example of a simple configuration (pin a -deadline task to CPU0) + follows (rt-app is used to create a -deadline task). + + mkdir /dev/cpuset + mount -t cgroup -o cpuset cpuset /dev/cpuset + cd /dev/cpuset + mkdir cpu0 + echo 0 > cpu0/cpuset.cpus + echo 0 > cpu0/cpuset.mems + echo 1 > cpuset.cpu_exclusive + echo 0 > cpuset.sched_load_balance + echo 1 > cpu0/cpuset.cpu_exclusive + echo 1 > cpu0/cpuset.mem_exclusive + echo $$ > cpu0/tasks + rt-app -t 100000:10000:d:0 -D5 (it is now actually superfluous to specify + task affinity) + +6. Future plans +=============== + + Still missing: + + - refinements to deadline inheritance, especially regarding the possibility + of retaining bandwidth isolation among non-interacting tasks. This is + being studied from both theoretical and practical points of view, and + hopefully we should be able to produce some demonstrative code soon; + - (c)group based bandwidth management, and maybe scheduling; + - access control for non-root users (and related security concerns to + address), which is the best way to allow unprivileged use of the mechanisms + and how to prevent non-root users "cheat" the system? + + As already discussed, we are planning also to merge this work with the EDF + throttling patches [https://lkml.org/lkml/2010/2/23/239] but we still are in + the preliminary phases of the merge and we really seek feedback that would + help us decide on the direction it should take. diff --git a/Documentation/scheduler/sched-design-CFS.txt b/Documentation/scheduler/sched-design-CFS.txt index 6f33593e59e..f14f4930422 100644 --- a/Documentation/scheduler/sched-design-CFS.txt +++ b/Documentation/scheduler/sched-design-CFS.txt @@ -66,9 +66,7 @@ rq->cfs.load value, which is the sum of the weights of the tasks queued on the runqueue. CFS maintains a time-ordered rbtree, where all runnable tasks are sorted by the -p->se.vruntime key (there is a subtraction using rq->cfs.min_vruntime to -account for possible wraparounds). CFS picks the "leftmost" task from this -tree and sticks to it. +p->se.vruntime key. CFS picks the "leftmost" task from this tree and sticks to it. As the system progresses forwards, the executed tasks are put into the tree more and more to the right --- slowly but surely giving a chance for every task to become the "leftmost task" and thus get on the CPU within a deterministic @@ -130,7 +128,7 @@ CFS implements three scheduling policies: idle timer scheduler in order to avoid to get into priority inversion problems which would deadlock the machine. -SCHED_FIFO/_RR are implemented in sched_rt.c and are as specified by +SCHED_FIFO/_RR are implemented in sched/rt.c and are as specified by POSIX. The command chrt from util-linux-ng 2.13.1.1 can set all of these except @@ -145,9 +143,9 @@ Classes," an extensible hierarchy of scheduler modules. These modules encapsulate scheduling policy details and are handled by the scheduler core without the core code assuming too much about them. -sched_fair.c implements the CFS scheduler described above. +sched/fair.c implements the CFS scheduler described above. -sched_rt.c implements SCHED_FIFO and SCHED_RR semantics, in a simpler way than +sched/rt.c implements SCHED_FIFO and SCHED_RR semantics, in a simpler way than the previous vanilla scheduler did. It uses 100 runqueues (for all 100 RT priority levels, instead of 140 in the previous scheduler) and it needs no expired array. @@ -164,7 +162,7 @@ This is the (partial) list of the hooks: It puts the scheduling entity (task) into the red-black tree and increments the nr_running variable. - - dequeue_tree(...) + - dequeue_task(...) When a task is no longer runnable, this function is called to keep the corresponding scheduling entity out of the red-black tree. It decrements @@ -195,11 +193,6 @@ This is the (partial) list of the hooks: This function is mostly called from time tick functions; it might lead to process switch. This drives the running preemption. - - task_new(...) - - The core scheduler gives the scheduling module an opportunity to manage new - task startup. The CFS scheduling module uses it for group scheduling, while - the scheduling module for a real-time task does not use it. @@ -211,7 +204,7 @@ provide fair CPU time to each such task group. For example, it may be desirable to first provide fair CPU time to each user on the system and then to each task belonging to a user. -CONFIG_GROUP_SCHED strives to achieve exactly that. It lets tasks to be +CONFIG_CGROUP_SCHED strives to achieve exactly that. It lets tasks to be grouped and divides CPU time fairly among such groups. CONFIG_RT_GROUP_SCHED permits to group real-time (i.e., SCHED_FIFO and @@ -220,44 +213,18 @@ SCHED_RR) tasks. CONFIG_FAIR_GROUP_SCHED permits to group CFS (i.e., SCHED_NORMAL and SCHED_BATCH) tasks. -At present, there are two (mutually exclusive) mechanisms to group tasks for -CPU bandwidth control purposes: - - - Based on user id (CONFIG_USER_SCHED) - - With this option, tasks are grouped according to their user id. - - - Based on "cgroup" pseudo filesystem (CONFIG_CGROUP_SCHED) - - This options needs CONFIG_CGROUPS to be defined, and lets the administrator + These options need CONFIG_CGROUPS to be defined, and let the administrator create arbitrary groups of tasks, using the "cgroup" pseudo filesystem. See Documentation/cgroups/cgroups.txt for more information about this filesystem. -Only one of these options to group tasks can be chosen and not both. - -When CONFIG_USER_SCHED is defined, a directory is created in sysfs for each new -user and a "cpu_share" file is added in that directory. - - # cd /sys/kernel/uids - # cat 512/cpu_share # Display user 512's CPU share - 1024 - # echo 2048 > 512/cpu_share # Modify user 512's CPU share - # cat 512/cpu_share # Display user 512's CPU share - 2048 - # - -CPU bandwidth between two users is divided in the ratio of their CPU shares. -For example: if you would like user "root" to get twice the bandwidth of user -"guest," then set the cpu_share for both the users such that "root"'s cpu_share -is twice "guest"'s cpu_share. - -When CONFIG_CGROUP_SCHED is defined, a "cpu.shares" file is created for each +When CONFIG_FAIR_GROUP_SCHED is defined, a "cpu.shares" file is created for each group created using the pseudo filesystem. See example steps below to create task groups and modify their CPU share using the "cgroups" pseudo filesystem. - # mkdir /dev/cpuctl - # mount -t cgroup -ocpu none /dev/cpuctl - # cd /dev/cpuctl + # mount -t tmpfs cgroup_root /sys/fs/cgroup + # mkdir /sys/fs/cgroup/cpu + # mount -t cgroup -ocpu none /sys/fs/cgroup/cpu + # cd /sys/fs/cgroup/cpu # mkdir multimedia # create "multimedia" group of tasks # mkdir browser # create "browser" group of tasks @@ -273,24 +240,3 @@ task groups and modify their CPU share using the "cgroups" pseudo filesystem. # #Launch gmplayer (or your favourite movie player) # echo <movie_player_pid> > multimedia/tasks - -8. Implementation note: user namespaces - -User namespaces are intended to be hierarchical. But they are currently -only partially implemented. Each of those has ramifications for CFS. - -First, since user namespaces are hierarchical, the /sys/kernel/uids -presentation is inadequate. Eventually we will likely want to use sysfs -tagging to provide private views of /sys/kernel/uids within each user -namespace. - -Second, the hierarchical nature is intended to support completely -unprivileged use of user namespaces. So if using user groups, then -we want the users in a user namespace to be children of the user -who created it. - -That is currently unimplemented. So instead, every user in a new -user namespace will receive 1024 shares just like any user in the -initial user namespace. Note that at the moment creation of a new -user namespace requires each of CAP_SYS_ADMIN, CAP_SETUID, and -CAP_SETGID. diff --git a/Documentation/scheduler/sched-domains.txt b/Documentation/scheduler/sched-domains.txt index 373ceacc367..4af80b1c05a 100644 --- a/Documentation/scheduler/sched-domains.txt +++ b/Documentation/scheduler/sched-domains.txt @@ -1,8 +1,7 @@ -Each CPU has a "base" scheduling domain (struct sched_domain). These are -accessed via cpu_sched_domain(i) and this_sched_domain() macros. The domain +Each CPU has a "base" scheduling domain (struct sched_domain). The domain hierarchy is built from these base domains via the ->parent pointer. ->parent -MUST be NULL terminated, and domain structures should be per-CPU as they -are locklessly updated. +MUST be NULL terminated, and domain structures should be per-CPU as they are +locklessly updated. Each scheduling domain spans a number of CPUs (stored in the ->span field). A domain's span MUST be a superset of it child's span (this restriction could @@ -26,11 +25,26 @@ is treated as one entity. The load of a group is defined as the sum of the load of each of its member CPUs, and only when the load of a group becomes out of balance are tasks moved between groups. -In kernel/sched.c, rebalance_tick is run periodically on each CPU. This -function takes its CPU's base sched domain and checks to see if has reached -its rebalance interval. If so, then it will run load_balance on that domain. -rebalance_tick then checks the parent sched_domain (if it exists), and the -parent of the parent and so forth. +In kernel/sched/core.c, trigger_load_balance() is run periodically on each CPU +through scheduler_tick(). It raises a softirq after the next regularly scheduled +rebalancing event for the current runqueue has arrived. The actual load +balancing workhorse, run_rebalance_domains()->rebalance_domains(), is then run +in softirq context (SCHED_SOFTIRQ). + +The latter function takes two arguments: the current CPU and whether it was idle +at the time the scheduler_tick() happened and iterates over all sched domains +our CPU is on, starting from its base domain and going up the ->parent chain. +While doing that, it checks to see if the current domain has exhausted its +rebalance interval. If so, it runs load_balance() on that domain. It then checks +the parent sched_domain (if it exists), and the parent of the parent and so +forth. + +Initially, load_balance() finds the busiest group in the current sched domain. +If it succeeds, it looks for the busiest runqueue of all the CPUs' runqueues in +that group. If it manages to find such a runqueue, it locks both our initial +CPU's runqueue and the newly found busiest one and starts moving tasks from it +to our runqueue. The exact number of tasks amounts to an imbalance previously +computed while iterating over this sched domain's groups. *** Implementing sched domains *** The "base" domain will "span" the first level of the hierarchy. In the case @@ -47,12 +61,8 @@ The implementor should read comments in include/linux/sched.h: struct sched_domain fields, SD_FLAG_*, SD_*_INIT to get an idea of the specifics and what to tune. -For SMT, the architecture must define CONFIG_SCHED_SMT and provide a -cpumask_t cpu_sibling_map[NR_CPUS], where cpu_sibling_map[i] is the mask of -all "i"'s siblings as well as "i" itself. - Architectures may retain the regular override the default SD_*_INIT flags -while using the generic domain builder in kernel/sched.c if they wish to +while using the generic domain builder in kernel/sched/core.c if they wish to retain the traditional SMT->SMP->NUMA topology (or some subset of that). This can be done by #define'ing ARCH_HASH_SCHED_TUNE. diff --git a/Documentation/scheduler/sched-nice-design.txt b/Documentation/scheduler/sched-nice-design.txt index e2bae5a577e..3ac1e46d536 100644 --- a/Documentation/scheduler/sched-nice-design.txt +++ b/Documentation/scheduler/sched-nice-design.txt @@ -55,7 +55,7 @@ To sum it up: we always wanted to make nice levels more consistent, but within the constraints of HZ and jiffies and their nasty design level coupling to timeslices and granularity it was not really viable. -The second (less frequent but still periodically occuring) complaint +The second (less frequent but still periodically occurring) complaint about Linux's nice level support was its assymetry around the origo (which you can see demonstrated in the picture above), or more accurately: the fact that nice level behavior depended on the _absolute_ diff --git a/Documentation/scheduler/sched-rt-group.txt b/Documentation/scheduler/sched-rt-group.txt index 1df7f9cdab0..71b54d54998 100644 --- a/Documentation/scheduler/sched-rt-group.txt +++ b/Documentation/scheduler/sched-rt-group.txt @@ -73,7 +73,7 @@ The remaining CPU time will be used for user input and other tasks. Because realtime tasks have explicitly allocated the CPU time they need to perform their tasks, buffer underruns in the graphics or audio can be eliminated. -NOTE: the above example is not fully implemented as of yet (2.6.25). We still +NOTE: the above example is not fully implemented yet. We still lack an EDF scheduler to make non-uniform periods usable. @@ -126,28 +126,17 @@ priority! 2.3 Basis for grouping tasks ---------------------------- -There are two compile-time settings for allocating CPU bandwidth. These are -configured using the "Basis for grouping tasks" multiple choice menu under -General setup > Group CPU Scheduler: +Enabling CONFIG_RT_GROUP_SCHED lets you explicitly allocate real +CPU bandwidth to task groups. -a. CONFIG_USER_SCHED (aka "Basis for grouping tasks" = "user id") - -This lets you use the virtual files under -"/sys/kernel/uids/<uid>/cpu_rt_runtime_us" to control he CPU time reserved for -each user . - -The other option is: - -.o CONFIG_CGROUP_SCHED (aka "Basis for grouping tasks" = "Control groups") - -This uses the /cgroup virtual file system and "/cgroup/<cgroup>/cpu.rt_runtime_us" -to control the CPU time reserved for each control group instead. +This uses the cgroup virtual file system and "<cgroup>/cpu.rt_runtime_us" +to control the CPU time reserved for each control group. For more information on working with control groups, you should read Documentation/cgroups/cgroups.txt as well. -Group settings are checked against the following limits in order to keep the configuration -schedulable: +Group settings are checked against the following limits in order to keep the +configuration schedulable: \Sum_{i} runtime_{i} / global_period <= global_runtime / global_period @@ -160,8 +149,7 @@ For now, this can be simplified to just the following (but see Future plans): =============== There is work in progress to make the scheduling period for each group -("/sys/kernel/uids/<uid>/cpu_rt_period_us" or -"/cgroup/<cgroup>/cpu.rt_period_us" respectively) configurable as well. +("<cgroup>/cpu.rt_period_us") configurable as well. The constraint on the period is that a subgroup must have a smaller or equal period to its parent. But realistically its not very useful _yet_ @@ -189,7 +177,7 @@ Implementing SCHED_EDF might take a while to complete. Priority Inheritance is the biggest challenge as the current linux PI infrastructure is geared towards the limited static priority levels 0-99. With deadline scheduling you need to do deadline inheritance (since priority is inversely proportional to the -deadline delta (deadline - now). +deadline delta (deadline - now)). This means the whole PI machinery will have to be reworked - and that is one of the most complex pieces of code we have. diff --git a/Documentation/scheduler/sched-stats.txt b/Documentation/scheduler/sched-stats.txt index 01e69404ee5..8259b34a66a 100644 --- a/Documentation/scheduler/sched-stats.txt +++ b/Documentation/scheduler/sched-stats.txt @@ -1,3 +1,7 @@ +Version 15 of schedstats dropped counters for some sched_yield: +yld_exp_empty, yld_act_empty and yld_both_empty. Otherwise, it is +identical to version 14. + Version 14 of schedstats includes support for sched_domains, which hit the mainline kernel in 2.6.20 although it is identical to the stats from version 12 which was in the kernel from 2.6.13-2.6.19 (version 13 never saw a kernel @@ -28,32 +32,26 @@ to write their own scripts, the fields are described here. CPU statistics -------------- -cpu<N> 1 2 3 4 5 6 7 8 9 10 11 12 - -NOTE: In the sched_yield() statistics, the active queue is considered empty - if it has only one process in it, since obviously the process calling - sched_yield() is that process. +cpu<N> 1 2 3 4 5 6 7 8 9 -First four fields are sched_yield() statistics: - 1) # of times both the active and the expired queue were empty - 2) # of times just the active queue was empty - 3) # of times just the expired queue was empty - 4) # of times sched_yield() was called +First field is a sched_yield() statistic: + 1) # of times sched_yield() was called Next three are schedule() statistics: - 5) # of times we switched to the expired queue and reused it - 6) # of times schedule() was called - 7) # of times schedule() left the processor idle + 2) This field is a legacy array expiration count field used in the O(1) + scheduler. We kept it for ABI compatibility, but it is always set to zero. + 3) # of times schedule() was called + 4) # of times schedule() left the processor idle Next two are try_to_wake_up() statistics: - 8) # of times try_to_wake_up() was called - 9) # of times try_to_wake_up() was called to wake up the local cpu + 5) # of times try_to_wake_up() was called + 6) # of times try_to_wake_up() was called to wake up the local cpu Next three are statistics describing scheduling latency: - 10) sum of all time spent running by tasks on this processor (in jiffies) - 11) sum of all time spent waiting to run by tasks on this processor (in + 7) sum of all time spent running by tasks on this processor (in jiffies) + 8) sum of all time spent waiting to run by tasks on this processor (in jiffies) - 12) # of timeslices run on this cpu + 9) # of timeslices run on this cpu Domain statistics |