Find the answer to your Linux question:
Results 1 to 3 of 3
WIth the O(N) scheduler it is well documented that there is separate run queue for each processor. Documentation for CFS only refers to a single red-black binary tree for all ...
Enjoy an ad free experience by logging in. Not a member yet? Register.
  1. #1
    Just Joined!
    Join Date
    Aug 2010
    Posts
    5

    CFS and Processor Affinity


    WIth the O(N) scheduler it is well documented that there is separate run queue for each processor. Documentation for CFS only refers to a single red-black binary tree for all processes.

    How does Linux with CFS deal with this?

  2. #2
    Just Joined!
    Join Date
    Mar 2009
    Location
    Norway
    Posts
    67
    First off, the old schedler is referred to as O(1), _not_ O(N).

    CFS is the current policy for handling tasks of SCHED_NORMAL and SCHED_BATCH. It manages the tasks in a balanced red-black tree, _one_per_core_. It uses the difference between the granted timeslice and actual spent time running on a CPU, so a task that has run for more than the allocated slice will be placed far to the right in the tree once you hit schedule(). So the CFS does not deal with a global runqueue at all (:

    As a sidenote, the O(1) scheduler is not completely gone. Or rather, the array for which the O(1) scheduler was famous for, is not gone. SCHED_RR and SCHED_FIFO is handled by sched_rt, and this policy still use an array of 100 slots to store a linked lists of rt-tasks that are currently runnable.

  3. #3
    Just Joined!
    Join Date
    Aug 2010
    Posts
    5
    Thanks, sorry for the O(N) slip.

    In all the O(1) write ups the queue pair for EACH core is highlighted. In the CFS write ups there never seems to be a mention of 1 RB tree for each core, so thanks for clarifying. Is the same criteria used for rebalancing the queues as in O(1) (rebalance on empty queue, etc)?

    I'm still having a bit of trouble with VRUNTIME. I understand that it updates at a rate mostly dependent on the process nice (factored into relative weight), the RB tree is sorted by VRUNTIME to the left., and left most process runs.

    What I am not clear on is if the VRUNTIME accumulates from process start and represents all its run time from the beginning, or if it is periodically reset.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •