1. 14 8月, 2011 14 次提交
    • P
      sched: Introduce primitives to account for CFS bandwidth tracking · ab84d31e
      Paul Turner 提交于
      In this patch we introduce the notion of CFS bandwidth, partitioned into
      globally unassigned bandwidth, and locally claimed bandwidth.
      
       - The global bandwidth is per task_group, it represents a pool of unclaimed
         bandwidth that cfs_rqs can allocate from.
       - The local bandwidth is tracked per-cfs_rq, this represents allotments from
         the global pool bandwidth assigned to a specific cpu.
      
      Bandwidth is managed via cgroupfs, adding two new interfaces to the cpu subsystem:
       - cpu.cfs_period_us : the bandwidth period in usecs
       - cpu.cfs_quota_us : the cpu bandwidth (in usecs) that this tg will be allowed
         to consume over period above.
      Signed-off-by: NPaul Turner <pjt@google.com>
      Signed-off-by: NNikhil Rao <ncrao@google.com>
      Signed-off-by: NBharata B Rao <bharata@linux.vnet.ibm.com>
      Reviewed-by: NHidetoshi Seto <seto.hidetoshi@jp.fujitsu.com>
      Signed-off-by: NPeter Zijlstra <a.p.zijlstra@chello.nl>
      Link: http://lkml.kernel.org/r/20110721184756.972636699@google.comSigned-off-by: NIngo Molnar <mingo@elte.hu>
      ab84d31e
    • P
      sched: Implement hierarchical task accounting for SCHED_OTHER · 953bfcd1
      Paul Turner 提交于
      Introduce hierarchical task accounting for the group scheduling case in CFS, as
      well as promoting the responsibility for maintaining rq->nr_running to the
      scheduling classes.
      
      The primary motivation for this is that with scheduling classes supporting
      bandwidth throttling it is possible for entities participating in throttled
      sub-trees to not have root visible changes in rq->nr_running across activate
      and de-activate operations.  This in turn leads to incorrect idle and
      weight-per-task load balance decisions.
      
      This also allows us to make a small fixlet to the fastpath in pick_next_task()
      under group scheduling.
      
      Note: this issue also exists with the existing sched_rt throttling mechanism.
      This patch does not address that.
      Signed-off-by: NPaul Turner <pjt@google.com>
      Reviewed-by: NHidetoshi Seto <seto.hidetoshi@jp.fujitsu.com>
      Signed-off-by: NPeter Zijlstra <a.p.zijlstra@chello.nl>
      Link: http://lkml.kernel.org/r/20110721184756.878333391@google.comSigned-off-by: NIngo Molnar <mingo@elte.hu>
      953bfcd1
    • Y
      sched/cpupri: Remove cpupri->pri_active · 5710f15b
      Yong Zhang 提交于
      Since [sched/cpupri: Remove the vec->lock], member pri_active
      of struct cpupri is not needed any more, just remove it. Also
      clean stuff related to it.
      Signed-off-by: NYong Zhang <yong.zhang0@gmail.com>
      Signed-off-by: NPeter Zijlstra <a.p.zijlstra@chello.nl>
      Link: http://lkml.kernel.org/r/20110806001004.GA2207@zhySigned-off-by: NIngo Molnar <mingo@elte.hu>
      5710f15b
    • S
      sched/cpupri: Fix memory barriers for vec updates to always be in order · d473750b
      Steven Rostedt 提交于
      [ This patch actually compiles. Thanks to Mike Galbraith for pointing
      that out. I compiled and booted this patch with no issues. ]
      
      Re-examining the cpupri patch, I see there's a possible race because the
      update of the two priorities vec->counts are not protected by a memory
      barrier.
      
      When a RT runqueue is overloaded and wants to push an RT task to another
      runqueue, it scans the RT priority vectors in a loop from lowest
      priority to highest.
      
      When we queue or dequeue an RT task that changes a runqueue's highest
      priority task, we update the vectors to show that a runqueue is rated at
      a different priority. To do this, we first set the new priority mask,
      and increment the vec->count, and then set the old priority mask by
      decrementing the vec->count.
      
      If we are lowering the runqueue's RT priority rating, it will trigger a
      RT pull, and we do not care if we miss pushing to this runqueue or not.
      
      But if we raise the priority, but the priority is still lower than an RT
      task that is looking to be pushed, we must make sure that this runqueue
      is still seen by the push algorithm (the loop).
      
      Because the loop reads from lowest to highest, and the new priority is
      set before the old one is cleared, we will either see the new or old
      priority set and the vector will be checked.
      
      But! Since there's no memory barrier between the updates of the two, the
      old count may be decremented first before the new count is incremented.
      This means the loop may see the old count of zero and skip it, and also
      the new count of zero before it was updated. A possible runqueue that
      the RT task could move to could be missed.
      
      A conditional memory barrier is placed between the vec->count updates
      and is only called when both updates are done.
      
      The smp_wmb() has also been changed to smp_mb__before_atomic_inc/dec(),
      as they are not needed by archs that already synchronize
      atomic_inc/dec().
      
      The smp_rmb() has been moved to be called at every iteration of the loop
      so that the race between seeing the two updates is visible by each
      iteration of the loop, as an arch is free to optimize the reading of
      memory of the counters in the loop.
      Signed-off-by: NSteven Rostedt <rostedt@goodmis.org>
      Signed-off-by: NPeter Zijlstra <a.p.zijlstra@chello.nl>
      Cc: Nick Piggin <npiggin@kernel.dk>
      Cc: Linus Torvalds <torvalds@linux-foundation.org>
      Link: http://lkml.kernel.org/r/1312547269.18583.194.camel@gandalf.stny.rr.comSigned-off-by: NIngo Molnar <mingo@elte.hu>
      d473750b
    • S
      sched/cpupri: Remove the vec->lock · c92211d9
      Steven Rostedt 提交于
      sched/cpupri: Remove the vec->lock
      
      The cpupri vec->lock has been showing up as a top contention
      lately. This is because of the RT push/pull logic takes an
      agressive approach for migrating RT tasks. The cpupri logic is
      in place to improve the performance of the push/pull when dealing
      with large number CPU machines.
      
      The problem though is a vec->lock is required, where a vec is a
      global per RT priority structure. That is, if there are lots of
      RT tasks at the same priority, every time they are added or removed
      from the RT queue, this global vec->lock is taken. Now that more
      kernel threads are becoming RT (RCU boost and threaded interrupts)
      this is becoming much more of an issue.
      
      There are two variables that are being synced by the vec->lock.
      The cpupri bitmask, and the vec->counter. The cpupri bitmask
      is one bit per priority. If a RT priority vec has a process queued,
      then the vec->count is > 0 and the cpupri bitmask is set for that
      RT priority.
      
      If the cpupri bitmask gets out of sync with the vec->counter, we could
      end up pushing a low proirity RT task to a high priority queue.
      That RT task that could have run immediately could be queued on a
      run queue with a higher priority task indefinitely.
      
      The solution is not to use the cpupri bitmask and just look at the
      vec->count directly when doing a pull. The cpupri bitmask is just
      a fast way to scan the RT priorities when a pull is made. Instead
      of using the bitmask, and just examine all RT priorities, and
      look at the vec->counts, we could eliminate the vec->lock. The
      scan of RT tasks is to find a run queue that we can push an RT task
      to, and we do not push to a high priority queue, thus the scan only
      needs to go from 1 to RT task->prio, and not all 100 RT priorities.
      
      The push algorithm, which does the scan of RT priorities (and
      scan of the bitmask) only happens when we have an overloaded RT run
      queue (more than one RT task queued). The grabbing of the vec->lock
      happens every time any RT task is queued or dequeued on the run
      queue for that priority. The slowing down of the scan by not using
      a bitmask is negligible by the speed up of removing the vec->lock
      contention, and replacing it with an atomic counter and memory barrier.
      
      To prove this, I wrote a patch that times both the loop and the code
      that grabs the vec->locks. I passed the patches to various people
      (and companies) to test and show the results. I let everyone choose
      their own load to test, giving different loads on the system,
      for various different setups.
      
      Here's some of the results: (snipping to a few CPUs to not make
      this change log huge, but the results were consistent across
      the entire system).
      
      System 1 (24 CPUs)
      
      Before patch:
      CPU:    Name    Count   Max     Min     Average Total
      ----    ----    -----   ---     ---     ------- -----
      [...]
      cpu 20: loop    3057    1.766   0.061   0.642   1963.170
              vec     6782949 90.469  0.089   0.414   2811760.503
      cpu 21: loop    2617    1.723   0.062   0.641   1679.074
              vec     6782810 90.499  0.089   0.291   1978499.900
      cpu 22: loop    2212    1.863   0.063   0.699   1547.160
              vec     6767244 85.685  0.089   0.435   2949676.898
      cpu 23: loop    2320    2.013   0.062   0.594   1380.265
              vec     6781694 87.923  0.088   0.431   2928538.224
      
      After patch:
      cpu 20: loop    2078    1.579   0.061   0.533   1108.006
              vec     6164555 5.704   0.060   0.143   885185.809
      cpu 21: loop    2268    1.712   0.065   0.575   1305.248
              vec     6153376 5.558   0.060   0.187   1154960.469
      cpu 22: loop    1542    1.639   0.095   0.533   823.249
              vec     6156510 5.720   0.060   0.190   1172727.232
      cpu 23: loop    1650    1.733   0.068   0.545   900.781
              vec     6170784 5.533   0.060   0.167   1034287.953
      
      All times are in microseconds. The 'loop' is the amount of time spent
      doing the loop across the priorities (before patch uses bitmask).
      the 'vec' is the amount of time in the code that requires grabbing
      the vec->lock. The second patch just does not have the vec lock, but
      encompasses the same code.
      
      Amazingly the loop code even went down on average. The vec code went
      from .5 down to .18, that's more than half the time spent!
      
      Note, more than one test was run, but they all had the same results.
      
      System 2 (64 CPUs)
      
      Before patch:
      CPU:    Name    Count   Max     Min     Average Total
      ----    ----    -----   ---     ---     ------- -----
      cpu 60: loop    0       0       0       0       0
              vec     5410840 277.954 0.084   0.782   4232895.727
      cpu 61: loop    0       0       0       0       0
              vec     4915648 188.399 0.084   0.570   2803220.301
      cpu 62: loop    0       0       0       0       0
              vec     5356076 276.417 0.085   0.786   4214544.548
      cpu 63: loop    0       0       0       0       0
              vec     4891837 170.531 0.085   0.799   3910948.833
      
      After patch:
      cpu 60: loop    0       0       0       0       0
              vec     5365118 5.080   0.021   0.063   340490.267
      cpu 61: loop    0       0       0       0       0
              vec     4898590 1.757   0.019   0.071   347903.615
      cpu 62: loop    0       0       0       0       0
              vec     5737130 3.067   0.021   0.119   687108.734
      cpu 63: loop    0       0       0       0       0
              vec     4903228 1.822   0.021   0.071   348506.477
      
      The test run during the measurement did not have any (very few,
      from other CPUs) RT tasks pushing. But this shows that it helped
      out tremendously with the contention, as the contention happens
      because the vec->lock is taken only on queuing at an RT priority,
      and different CPUs that queue tasks at the same priority will
      have contention.
      
      I tested on my own 4 CPU machine with the following results:
      
      Before patch:
      CPU:    Name    Count   Max     Min     Average Total
      ----    ----    -----   ---     ---     ------- -----
      cpu 0:  loop    2377    1.489   0.158   0.588   1398.395
              vec     4484    770.146 2.301   4.396   19711.755
      cpu 1:  loop    2169    1.962   0.160   0.576   1250.110
              vec     4425    152.769 2.297   4.030   17834.228
      cpu 2:  loop    2324    1.749   0.155   0.559   1299.799
              vec     4368    779.632 2.325   4.665   20379.268
      cpu 3:  loop    2325    1.629   0.157   0.561   1306.113
              vec     4650    408.782 2.394   4.348   20222.577
      
      After patch:
      CPU:    Name    Count   Max     Min     Average Total
      ----    ----    -----   ---     ---     ------- -----
      cpu 0:  loop    2121    1.616   0.113   0.636   1349.189
              vec     4303    1.151   0.225   0.421   1811.966
      cpu 1:  loop    2130    1.638   0.178   0.644   1372.927
              vec     4627    1.379   0.235   0.428   1983.648
      cpu 2:  loop    2056    1.464   0.165   0.637   1310.141
              vec     4471    1.311   0.217   0.433   1937.927
      cpu 3:  loop    2154    1.481   0.162   0.601   1295.083
              vec     4236    1.253   0.230   0.425   1803.008
      
      This was running my migrate.c code that can be found at:
      http://lwn.net/Articles/425763/
      
      The migrate code does stress the RT tasks a bit. This shows that
      the loop did increase a little after the patch, but not by much.
      The vec code dropped dramatically. From 4.3us down to .42us.
      That's a 10x improvement!
      Tested-by: NMike Galbraith <mgalbraith@suse.de>
      Tested-by: NLuis Claudio R. Gonçalves <lgoncalv@redhat.com>
      Tested-by: Matthew Hank Sabins<msabins@linux.vnet.ibm.com>
      Signed-off-by: NSteven Rostedt <rostedt@goodmis.org>
      Reviewed-by: NGregory Haskins <gregory.haskins@gmail.com>
      Acked-by: NHillf Danton <dhillf@gmail.com>
      Signed-off-by: NPeter Zijlstra <a.p.zijlstra@chello.nl>
      Cc: Chris Mason <chris.mason@oracle.com>
      Link: http://lkml.kernel.org/r/1312317372.18583.101.camel@gandalf.stny.rr.comSigned-off-by: NIngo Molnar <mingo@elte.hu>
      c92211d9
    • S
      sched: Use pushable_tasks to determine next highest prio · 5181f4a4
      Steven Rostedt 提交于
      Hillf Danton proposed a patch (see link) that cleaned up the
      sched_rt code that calculates the priority of the next highest priority
      task to be used in finding run queues to pull from.
      
      His patch removed the calculating of the next prio to just use the current
      prio when deteriming if we should examine a run queue to pull from. The problem
      with his patch was that it caused more false checks. Because we check a run
      queue for pushable tasks if the current priority of that run queue is higher
      in priority than the task about to run on our run queue. But after grabbing
      the locks and doing the real check, we find that there may not be a task
      that has a higher prio task to pull. Thus the locks were taken with nothing to
      do.
      
      I added some trace_printks() to record when and how many times the run queue
      locks were taken to check for pullable tasks, compared to how many times we
      pulled a task.
      
      With the current method, it was:
      
        3806 locks taken vs 2812 pulled tasks
      
      With Hillf's patch:
      
        6728 locks taken vs 2804 pulled tasks
      
      The number of times locks were taken to pull a task went up almost double with
      no more success rate.
      
      But his patch did get me thinking. When we look at the priority of the highest
      task to consider taking the locks to do a pull, a failure to pull can be one
      of the following: (in order of most likely)
      
       o RT task was pushed off already between the check and taking the lock
       o Waiting RT task can not be migrated
       o RT task's CPU affinity does not include the target run queue's CPU
       o RT task's priority changed between the check and taking the lock
      
      And with Hillf's patch, the thing that caused most of the failures, is
      the RT task to pull was not at the right priority to pull (not greater than
      the current RT task priority on the target run queue).
      
      Most of the above cases we can't help. But the current method does not check
      if the next highest prio RT task can be migrated or not, and if it can not,
      we still grab the locks to do the test (we don't find out about this fact until
      after we have the locks). I thought about this case, and realized that the
      pushable task plist that is maintained only holds RT tasks that can migrate.
      If we move the calculating of the next highest prio task from the inc/dec_rt_task()
      functions into the queuing of the pushable tasks, then we only measure the
      priorities of those tasks that we push, and we get this basically for free.
      
      Not only does this patch make the code a little more efficient, it cleans it
      up and makes it a little simpler.
      
      Thanks to Hillf Danton for inspiring me on this patch.
      Signed-off-by: NSteven Rostedt <rostedt@goodmis.org>
      Signed-off-by: NPeter Zijlstra <a.p.zijlstra@chello.nl>
      Cc: Hillf Danton <dhillf@gmail.com>
      Cc: Gregory Haskins <ghaskins@novell.com>
      Link: http://lkml.kernel.org/r/BANLkTimQ67180HxCx5vgMqumqw1EkFh3qg@mail.gmail.comSigned-off-by: NIngo Molnar <mingo@elte.hu>
      5181f4a4
    • S
      sched: Balance RT tasks when forked as well · c37495fd
      Steven Rostedt 提交于
      When a new task is woken, the code to balance the RT task is currently
      skipped in the select_task_rq() call. But it will be pushed if the rq
      is currently overloaded with RT tasks anyway. The issue is that we
      already queued the task, and if it does get pushed, it will have to
      be dequeued and requeued on the new run queue. The advantage with
      pushing it first is that we avoid this requeuing as we are pushing it
      off before the task is ever queued.
      
      See commit 318e0893 ("sched: pre-route RT tasks on wakeup")
      for more details.
      
      The return of select_task_rq() when it is not a wake up has also been
      changed to return task_cpu() instead of smp_processor_id(). This is more
      of a sanity because the current only other user of select_task_rq()
      besides wake ups, is an exec, where task_cpu() should also be the same
      as smp_processor_id(). But if it is used for other purposes, lets keep
      the task on the same CPU. Why would we mant to migrate it to the current
      CPU?
      Signed-off-by: NSteven Rostedt <rostedt@goodmis.org>
      Signed-off-by: NPeter Zijlstra <a.p.zijlstra@chello.nl>
      Cc: Hillf Danton <dhillf@gmail.com>
      Link: http://lkml.kernel.org/r/20110617015919.832743148@goodmis.orgSigned-off-by: NIngo Molnar <mingo@elte.hu>
      c37495fd
    • H
      sched: Remove resetting exec_start in put_prev_task_rt() · 1812a643
      Hillf Danton 提交于
      There's no reason to clean the exec_start in put_prev_task_rt() as it is reset
      when the task gets back to the run queue. This saves us doing a store() in the
      fast path.
      Signed-off-by: NHillf Danton <dhillf@gmail.com>
      Signed-off-by: NSteven Rostedt <rostedt@goodmis.org>
      Signed-off-by: NPeter Zijlstra <a.p.zijlstra@chello.nl>
      Cc: Mike Galbraith <efault@gmx.de>
      Cc: Yong Zhang <yong.zhang0@gmail.com>
      Link: http://lkml.kernel.org/r/BANLkTimqWD=q6YnSDi-v9y=LMWecgEzEWg@mail.gmail.comSigned-off-by: NIngo Molnar <mingo@elte.hu>
      1812a643
    • H
      sched, rt: Fix rq->rt.pushable_tasks bug in push_rt_task() · 311e800e
      Hillf Danton 提交于
      Do not call dequeue_pushable_task() when failing to push an eligible
      task, as it remains pushable, merely not at this particular moment.
      Signed-off-by: NHillf Danton <dhillf@gmail.com>
      Signed-off-by: NMike Galbraith <mgalbraith@gmx.de>
      Signed-off-by: NSteven Rostedt <rostedt@goodmis.org>
      Signed-off-by: NPeter Zijlstra <a.p.zijlstra@chello.nl>
      Cc: Yong Zhang <yong.zhang0@gmail.com>
      Link: http://lkml.kernel.org/r/1306895385.4791.26.camel@marge.simson.netSigned-off-by: NIngo Molnar <mingo@elte.hu>
      311e800e
    • H
      sched: Remove noop in lowest_flag_domain() · 08354716
      Hillf Danton 提交于
      Checking for the validity of sd is removed, since it is already
      checked by the for_each_domain macro.
      Signed-off-by: NHillf Danton <dhillf@gmail.com>
      Signed-off-by: NSteven Rostedt <rostedt@goodmis.org>
      Signed-off-by: NPeter Zijlstra <a.p.zijlstra@chello.nl>
      Link: http://lkml.kernel.org/r/BANLkTimT+Tut-3TshCDm-NiLLXrOznibNA@mail.gmail.comSigned-off-by: NIngo Molnar <mingo@elte.hu>
      08354716
    • H
      sched: Remove noop in next_prio() · 67d95538
      Hillf Danton 提交于
      When computing the next priority for a given run-queue, the check for
      RT priority of the task determined by the pick_next_highest_task_rt()
      function could be removed, since only RT tasks are returned by the
      function.
      Reviewed-by: NYong Zhang <yong.zhang0@gmail.com>
      Signed-off-by: NHillf Danton <dhillf@gmail.com>
      Signed-off-by: NSteven Rostedt <rostedt@goodmis.org>
      Signed-off-by: NPeter Zijlstra <a.p.zijlstra@chello.nl>
      Link: http://lkml.kernel.org/r/BANLkTimxmWiof9s5AvS3v_0X+sMiE=0x5g@mail.gmail.comSigned-off-by: NIngo Molnar <mingo@elte.hu>
      67d95538
    • M
      sched: fix broken SCHED_RESET_ON_FORK handling · c350a04e
      Mike Galbraith 提交于
      Setting child->prio = current->normal_prio _after_ SCHED_RESET_ON_FORK has
      been handled for an RT parent gives birth to a deranged mutant child with
      non-RT policy, but RT prio and sched_class.
      
      Move PI leakage protection up, always set priorities and weight, and if the
      child is leaving RT class, reset rt_priority to the proper value.
      Signed-off-by: NMike Galbraith <efault@gmx.de>
      Signed-off-by: NPeter Zijlstra <a.p.zijlstra@chello.nl>
      Link: http://lkml.kernel.org/r/1311779695.8691.2.camel@marge.simson.netSigned-off-by: NIngo Molnar <mingo@elte.hu>
      c350a04e
    • Y
      sched: Kill WAKEUP_PREEMPT · 2c2efaed
      Yong Zhang 提交于
      Remove the WAKEUP_PREEMPT feature, disabling it doesn't make any sense
      and its outlived its use by a long long while.
      Signed-off-by: NYong Zhang <yong.zhang0@gmail.com>
      Acked-by: NMike Galbraith <efault@gmx.de>
      Signed-off-by: NPeter Zijlstra <a.p.zijlstra@chello.nl>
      Link: http://lkml.kernel.org/r/20110729082033.GB12106@zhySigned-off-by: NIngo Molnar <mingo@elte.hu>
      2c2efaed
    • J
      sched: Remove rq->avg_load_per_task · e2b245f8
      Jan H. Schönherr 提交于
      Since commit a2d47777 ("sched: fix stale value in average load per task")
      the variable rq->avg_load_per_task is no longer required. Remove it.
      Signed-off-by: NJan H. Schönherr <schnhrr@cs.tu-berlin.de>
      Signed-off-by: NPeter Zijlstra <a.p.zijlstra@chello.nl>
      Link: http://lkml.kernel.org/r/1312189408-17172-1-git-send-email-schnhrr@cs.tu-berlin.deSigned-off-by: NIngo Molnar <mingo@elte.hu>
      e2b245f8
  2. 12 8月, 2011 8 次提交
  3. 11 8月, 2011 6 次提交
  4. 10 8月, 2011 12 次提交